향상도를 고려한 다차원 순차 패턴 마이닝 = Multi-dimensional Sequential Pattern Mining Based on the Lift

다국어 초록 (Multilingual Abstract)

Data mining is to look for useful but hidden information in a huge volume of data through direct or indirection refining processes, namely, to analyze and identify relations among data and meaningful patterns or rules. Among several data mining techniques, association rule mining is to find out mutual relevancies among purchased items and to establish association rules based on predefined support and confidence.
In particular, sequential pattern mining adopts additionally the concept of time and finds out mutual relevancies among items with the lapse of time. Sequential pattern mining extracts large sequences among sequences satisfying the minimum support defined by the user and finds out the maximal sequence among the large sequences.
A new stream of researches, multi-dimensional sequential pattern mining is an association rule mining which is applicable to data composed of a set of multi -dimensional items and the sequence of the items together. First, the multi -dimensional item set includes information on the known characteristics of customers or objects without sequence, and the sequential pattern includes information on goods purchased or pages visited by customers in sequential order. It identifies patterns in the above two parts simultaneously. Existing methods of multi-dimensional sequential pattern mining have a problem that they recognize only frequent association rules in multi-dimensional item sets. However, multi-dimensional characteristics are determined according to other facts like sex of the customers, their ages groups, etc, so we cannot say only frequent items are meaningful for the multi-dimensional parts. Instead it is reasonable to assume that the patterns for the multi-dimensional items are meaningful when they occur relatively more frequent or less frequent in a subset compared with the whole data set regardless of marginal support for those items.
The purpose of this study is to propose a new multi-dimensional sequential pattern mining algorithm to handle the problem mentioned above for the multi-dimensional part of the data. The proposed L-PSFP algorithm is a new algorithm based on the lift of relative frequency for multi-dimensional item sets in the subset of data with minimum support for the sequential parts. This method first distinguishes a subset satisfying frequent sequential patterns identified in the stage of sequential pattern mining, and is looking for a set of multi-dimensional items which occur relatively more frequent or less frequent in that subset compared with the whole data set. And we found that it is same as finding multi-dimensional items which have lifts far from 1.
L-PSFP algorithm would be useful in that it enables us to find multi -dimensional patterns that are relatively more frequent or less frequent in the subset satisfying a frequent sequential pattern compared with the whole data set instead of finding only multi-dimensional items with marginally frequent.

목차 (Table of Contents)

• 목차 = ⅰ
• 제1장 서론 = 1
• 제2장 연관 규칙 마이닝 = 5
• 2.1 연관 규칙 마이닝의 개요 = 5
• 2.2 연관 규칙 마이닝 알고리즘 = 8
• 2.2.1 Apriori = 9
• 2.2.2 분할(Partition) = 11
• 2.2.3 FP-growth (Frequent Patterns by pattern fragment Growth) = 12
• 제3장 순차 패턴 마이닝 = 14
• 3.1 순차 패턴 마이닝의 개요 = 14
• 3.2 순차 패턴 마이닝 알고리즘 = 17
• 3.2.1 Apriori-like 방법 = 17
• 1. AprioriAll = 17
• 2. GSP(Generalized Sequential Patterns) = 18
• 3.2.2 Pattern-Growth 방법 = 20
• 1. FreeSpan (Frequent Pattern-Projected Sequential PAtterN mining) = 20
• 2. PrefixSpan (Prefix-projected Sequential PAtterN mining) = 22
• 3.2.3 기타 방법 = 23
• 1. SPADE (Sequential PAttern Discovery using Equivalence classes) = 23
• 2. PSP (Prefix tree for Sequential Patterns) = 27
• 제4장 다차원 순차 패턴 마이닝 = 29
• 4.1 다차원 순차 패턴 마이닝의 개요 = 29
• 4.2 다차원 순차 패턴 마이닝 알고리즘 = 30
• 4.2.1 Uniseq = 31
• 4.2.2 Dim-Seq = 34
• 4.2.3 Seq-Dim = 35
• 4.2.4 PSFP(PrefixSpan with FP-growth) = 35
• 제5장 새로운 다차원 순차 패턴 마이닝 방법 = 42
• 5.1 향상도를 고려한 새로운 방법의 개요 = 43
• 5.2 L-PSFP 알고리즘 = 46
• 5.3 L-PSFP 알고리즘의 예제 = 49
• 제6장 결론 = 58
• 참고문헌 = 59
• 부록. L-PSFP 알고리즘을 실행하는 방법 = 63