[국내논문]PPFP(Push and Pop Frequent Pattern Mining): 빅데이터 패턴 분석을 위한 새로운 빈발 패턴 마이닝 방법 PPFP(Push and Pop Frequent Pattern Mining): A Novel Frequent Pattern Mining Method for Bigdata Frequent Pattern Mining원문보기
현존하는 빈발 패턴 마이닝 방법은 대부분 시간 효율성을 목표로 하고, 물리적 메모리 사용에 매우 의존적이다. 하지만 빅데이터 시대가 도래함에 따라 실제 세상의 데이터베이스는 급속도로 증가하고 있으며, 그에 따라 기존의 방법으로 현실적인 거대한 양의 데이터를 마이닝하기에 물리적 메모리 공간이 부족한 실정이다. 이러한 문제를 해결하기 위해, 빈발 패턴 마이닝의 메모리 의존성을 줄이기 위한 보조저장장치 기반의 연구들이 진행되었으나, 메모리 기반의 방법들에 비해 처리 시간이 너무 많이 소비된다는 한계가 있었다. 따라서 확장성을 가지며, 기존의 디스크 기반의 방법들에 비해 시간효율성을 높인 새로운 빈발 패턴 마이닝이 필요하게 되었다. 본 논문에서는 빅데이터로부터 빈도 아이템 집합들을 마이닝하기 위해 메모리와 디스크를 함께 사용하는 스택 기반의 새로운 접근법인 PPFP 알고리즘을 제안하였다. PPFP는 빈발 패턴 마이닝 접근법 중 가장 인기 있고 효율적인 접근법 중 하나인 FP-growth를 기반으로 하고 있다. PPFP 마이닝 방법은 다음과 같이 두 단계로 진행된다. (1) IFP-tree 구축: FP-tree를 생성한 후, 새로운 인덱스 번호 부여 방법으로 FP-tree의 각 노드에 인덱스 번호를 부여하고, 이 인덱스 번호가 부여된 FP-tree(IFP-tree)를 테이블로 변환하여(IFP-table) 디스크에 저장한다. (2) PPFP 알고리즘을 이용한 빈발 패턴 마이닝: 스택 기반의 PUSH-POP 방식으로 패턴을 확장시켜 나가며 빈발 패턴을 마이닝한다. 이러한 방식을 통해 메모리 기반의 방법에 비해 반복적으로 많은 시간이 소모되는 연산에 매우 적은 양의 메모리를 활용하여 확장성과 함께 시간효율성 또한 향상시킬 수 있었다. 그리고 기존의 연구 방법들과 비교 실험을 통해 새로운 알고리즘의 성능을 증명하였다.
현존하는 빈발 패턴 마이닝 방법은 대부분 시간 효율성을 목표로 하고, 물리적 메모리 사용에 매우 의존적이다. 하지만 빅데이터 시대가 도래함에 따라 실제 세상의 데이터베이스는 급속도로 증가하고 있으며, 그에 따라 기존의 방법으로 현실적인 거대한 양의 데이터를 마이닝하기에 물리적 메모리 공간이 부족한 실정이다. 이러한 문제를 해결하기 위해, 빈발 패턴 마이닝의 메모리 의존성을 줄이기 위한 보조저장장치 기반의 연구들이 진행되었으나, 메모리 기반의 방법들에 비해 처리 시간이 너무 많이 소비된다는 한계가 있었다. 따라서 확장성을 가지며, 기존의 디스크 기반의 방법들에 비해 시간효율성을 높인 새로운 빈발 패턴 마이닝이 필요하게 되었다. 본 논문에서는 빅데이터로부터 빈도 아이템 집합들을 마이닝하기 위해 메모리와 디스크를 함께 사용하는 스택 기반의 새로운 접근법인 PPFP 알고리즘을 제안하였다. PPFP는 빈발 패턴 마이닝 접근법 중 가장 인기 있고 효율적인 접근법 중 하나인 FP-growth를 기반으로 하고 있다. PPFP 마이닝 방법은 다음과 같이 두 단계로 진행된다. (1) IFP-tree 구축: FP-tree를 생성한 후, 새로운 인덱스 번호 부여 방법으로 FP-tree의 각 노드에 인덱스 번호를 부여하고, 이 인덱스 번호가 부여된 FP-tree(IFP-tree)를 테이블로 변환하여(IFP-table) 디스크에 저장한다. (2) PPFP 알고리즘을 이용한 빈발 패턴 마이닝: 스택 기반의 PUSH-POP 방식으로 패턴을 확장시켜 나가며 빈발 패턴을 마이닝한다. 이러한 방식을 통해 메모리 기반의 방법에 비해 반복적으로 많은 시간이 소모되는 연산에 매우 적은 양의 메모리를 활용하여 확장성과 함께 시간효율성 또한 향상시킬 수 있었다. 그리고 기존의 연구 방법들과 비교 실험을 통해 새로운 알고리즘의 성능을 증명하였다.
Most of existing frequent pattern mining methods address time efficiency and greatly rely on the primary memory. However, in the era of big data, the size of real-world databases to mined is exponentially increasing, and hence the primary memory is not sufficient enough to mine for frequent patterns...
Most of existing frequent pattern mining methods address time efficiency and greatly rely on the primary memory. However, in the era of big data, the size of real-world databases to mined is exponentially increasing, and hence the primary memory is not sufficient enough to mine for frequent patterns from large real-world data sets. To solve this problem, there are some researches for frequent pattern mining method based on disk, but the processing time compared to the memory based methods took very time consuming. There are some researches to improve scalability of frequent pattern mining, but their processes are very time consuming compare to the memory based methods. In this paper, we present PPFP as a novel disk-based approach for mining frequent itemset from big data; and hence we reduced the main memory size bottleneck. PPFP algorithm is based on FP-growth method which is one of the most popular and efficient frequent pattern mining approaches. The mining with PPFP consists of two setps. (1) Constructing an IFP-tree: After construct FP-tree, we assign index number for each node in FP-tree with novel index numbering method, and then insert the indexed FP-tree (IFP-tree) into disk as IFP-table. (2) Mining frequent patterns with PPFP: Mine frequent patterns by expending patterns using stack based PUSH-POP method (PPFP method). Through this new approach, by using a very small amount of memory for recursive and time consuming operation in mining process, we improved the scalability and time efficiency of the frequent pattern mining. And the reported test results demonstrate them.
Most of existing frequent pattern mining methods address time efficiency and greatly rely on the primary memory. However, in the era of big data, the size of real-world databases to mined is exponentially increasing, and hence the primary memory is not sufficient enough to mine for frequent patterns from large real-world data sets. To solve this problem, there are some researches for frequent pattern mining method based on disk, but the processing time compared to the memory based methods took very time consuming. There are some researches to improve scalability of frequent pattern mining, but their processes are very time consuming compare to the memory based methods. In this paper, we present PPFP as a novel disk-based approach for mining frequent itemset from big data; and hence we reduced the main memory size bottleneck. PPFP algorithm is based on FP-growth method which is one of the most popular and efficient frequent pattern mining approaches. The mining with PPFP consists of two setps. (1) Constructing an IFP-tree: After construct FP-tree, we assign index number for each node in FP-tree with novel index numbering method, and then insert the indexed FP-tree (IFP-tree) into disk as IFP-table. (2) Mining frequent patterns with PPFP: Mine frequent patterns by expending patterns using stack based PUSH-POP method (PPFP method). Through this new approach, by using a very small amount of memory for recursive and time consuming operation in mining process, we improved the scalability and time efficiency of the frequent pattern mining. And the reported test results demonstrate them.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
본 논문에서는 메모리를 적절히 활용하며 RDBMS에서 스택을 이용하여, 기존의 보조기억장치를 활용해 확장성을 높인 방법들에 비해 확장성은 유지하며 시간효율성을 향상시킨 새로운 빈발 패턴 마이닝 알고리즘을 제시하고, 실험을 통해 그 성능을 증명하였다.
빈발 패턴 마이닝 문제가 제기된 이래로, 대부분의 빈발 패턴 마이닝 알고리즘들은 메모리 의존적으로 마이닝 속도와 정확성을 높이는 것을 목표로 하였다. 하지만 빅데이터 시대가 도래하며, 현실적으로 거대한 양의 마이닝을 처리하기에 인 메모리(in-memory) 기반의 알고리즘들은 한계가 있다.
하지만 빅데이터 시대가 도래하며, 현실적으로 거대한 양의 마이닝을 처리하기에 인 메모리(in-memory) 기반의 알고리즘들은 한계가 있다. SQL 기반의 빈발 패턴 마이닝은 빈발 패턴 마이닝의 시간 효율성과 정확성을 향상시키기 위한 이전의 연구들과는 차별되게 확장성(scalability)을 향상시키기 위한 연구를 진행하였다. [15]의 연구는 기존의 빈발 패턴 마이닝에서 크게 이슈가 되던 FP-growth를 RDBMS에 통합시키는 방법을 제시하였다.
이러한 물리적 메모리 공간의 한계를 극복하기 위해 SQL기반의 빈발 패턴 마이닝 방법이 제시되었으나, 확장성 측면에서는 만족할 만한 성능을 보이지만 기존의 메모리 기반의 방법들에 월등히 많은 시간이 소비되기 때문에 실효성이 없어 보인다. 따라서 본 논문에서는 메모리와 RDBMS를 적절히 활용하여 SQL기반의 방법에 비해 시간효율성을 높이고 FP-growth 방법에 비해 확장성을 높인 새로운 빈발 패턴 마이닝 방법을 제시한다.
이 장에서는 앞서 구축한 IFP-table을 이용하여 반복적인 조건부 FP-tree의 생성 없이 빈발 패턴을 마이닝하는 방법에 대해 알아본다. PPFP 알고리즘은 본 논문에서 제시하는 빈발 패턴 마이닝 기법이다.
제안 방법
이 장에서는 본 논문의 새로운 알고리즘을 제시하기에 앞서 기존의 빈발 패턴 마이닝 기법 중 현재 가장 활발히 연구되어 있는 FP-growth 알고리즘과, 메모리 기반의 여타 빈발 패턴 마이닝 방법의 한계를 극복하기 위해 연구된 RDBMS 기반의 빈발 패턴 마이닝 방법인 SQL기반의 FP-growth방법에 대해 살펴본다.
두 번째 단계는 FP-tree를 이용하여 패턴을 마이닝하는 단계이다. 길이가 1인 패턴(최초의 접미 패턴)들로부터 시작하여 그것의 조건부 패턴 베이스(conditional pattern base)만을 고려하여 그것의 조건부 FP-tree(conditional FP-tree)를 반복적으로 생성하며 패턴을 찾아낸다.
FP-Tree는 단 두 번의 데이터베이스 스캔만으로 빈발 패턴 트리를 생성한다. 첫 번째 데이터베이스 스캔을 통해 각 아이템들의 빈발횟수를 카운트하여 아이템의 우선순위를 결정한다. 두 번째 데이터베이스 스캔을 통해 입력되는 각 아이템 집합을 빈발횟수를 이용하여 빈도수의 역순으로 정렬하며 트리를 구성한다.
첫 번째 데이터베이스 스캔을 통해 각 아이템들의 빈발횟수를 카운트하여 아이템의 우선순위를 결정한다. 두 번째 데이터베이스 스캔을 통해 입력되는 각 아이템 집합을 빈발횟수를 이용하여 빈도수의 역순으로 정렬하며 트리를 구성한다.
첫 번째 DB 스캔을 통해 트랜잭션 데이터베이스 내의 모든 아이템들의 빈도수를 계산하여 빈도수의 역순으로 정렬시켜 빈발 아이템 리스트를 생성한다. Table 1의 전체 트랜잭션 내 빈발 아이템 리스트(frequent items list) L은<(T:4), (E:4), (K:3), (J:3), (S:2)>가 된다.
PB-ai 테이블을 생성하기 위해 먼저 table FP 테이블에서 아이템이 ai인 행 (TID, count, path)들을 검색한다. 검색 결과의 각 행에 대해 우선 TID를 1로 하고, path를 각각의 아이템으로 분류하여 PB-ai테이블에 저장한다. 이렇게 만들어진 PB-ai 테이블이 만약 단일경로로 구성되어 있다면 그 조합을 패턴으로 찾아내고, 아니라면 해당 PB-ai를 이용하여 table FP를 만들 때 사용했던 알고리즘인 Pseudo Code 3을 이용하여 조건부 FP-ai 트리인 ConFP-ai를 생성한다.
현실적인 빅데이터를 마이닝하기 위해 우리는 PPFP라는 스택을 기반으로 한 새로운 빈발 패턴 마이닝 알고리즘을 제시하였다.
하지만 단순히 FP-tree를 테이블화 시킨 것만으로는 테이블 상에서 특정 패턴의 하위 집합의 범위를 구하기 어렵다. 이를 위해 우리는 새로운 인덱스 번호 부여 방법을 사용하여 FP-tree의 각 노드에 인덱스 번호를 부여함으로써 FP-tree를 디스크상에 저장한 후에도 간단히 특정 패턴의 하위 경로 집합을 구할 수 있도록 하였다.
PPFP 마이닝 방법을 위해 FP-tree의 특정 노드, 혹은 특정 패턴의 하위 경로를 모두 구할 수 있도록 인덱스 번호가 부여되어야 한다. 이를 위해 우리는 FP-tree의 각 노드에 현재 인덱스 번호를 의미하는 C-Index (Current Index Number)와 현재 노드를 포함한 하위 집합 노드의 시작 인덱스를 의미하는 L-Index (Lowest Index Number)를 부여한다. Fig.
3의 헤더 테이블 내에 존재하는 빈발 아이템 리스트를 CFP-stack에 입력한다. 그 후 푸쉬 팝(Push-Pop) 방식의 빈발 패턴 마이닝을 반복적으로 실행한다. 푸쉬 팝 방식의 첫 번째로 우선 CFP-stack의 가장 마지막에 입력된 아이템인 [S:2]를 POP한다.
그리고 IFP-table 검색을 통해 [K:3]의 하위 빈발 아이템들을 가져와 최소지지도 이상의 아이템만을 선택하여 조건부 패턴 베이스(Conditional pattern base)를 생성한다.
실험은 크게 두 가지로 진행하였다. 우선 확장성 측면에서 PPFP의 성능 비교를 위해 PPFP 알고리즘과 FP-growth를 사용하여 마이닝할 때의 메모리 소비량에 대한 비교 실험을 진행하였다. 그리고 시간효율성 측면의 성능 비교를 위해 보조기억장치를 활용하는 PPFP와 SQL기반의 FP-growth 방법으로 마이닝했을 때 처리 시간에 대해 비교하고, 메모리기반의 FP-growth와의 처리 시간에 대한 비교 실험 또한 함께 진행하였다.
우선 확장성 측면에서 PPFP의 성능 비교를 위해 PPFP 알고리즘과 FP-growth를 사용하여 마이닝할 때의 메모리 소비량에 대한 비교 실험을 진행하였다. 그리고 시간효율성 측면의 성능 비교를 위해 보조기억장치를 활용하는 PPFP와 SQL기반의 FP-growth 방법으로 마이닝했을 때 처리 시간에 대해 비교하고, 메모리기반의 FP-growth와의 처리 시간에 대한 비교 실험 또한 함께 진행하였다.
첫 번째 실험은 PPFP의 확장성에 대한 성능 검증을 위하여 FP-growth와 PPFP의 메모리 사용량 비교 분석 실험이다. 실험 데이터는 T40I10D100K 데이터 집합을 사용하여 최소지지도를 0.
첫 번째 실험은 PPFP의 확장성에 대한 성능 검증을 위하여 FP-growth와 PPFP의 메모리 사용량 비교 분석 실험이다. 실험 데이터는 T40I10D100K 데이터 집합을 사용하여 최소지지도를 0.8%를 기준으로 0.1%씩 증가시켜가며 마이닝하는데 소비되는 메모리량(Mbyte)을 측정하였다. Fig.
실험을 통해 PPFP 알고리즘과 SQL기반의 FPgrowth방법의 마이닝 처리 시간을 비교하여 보조기억장치를 활용하여 빈발 패턴을 마이닝하는 방법에서 PPFP알고리즘의 시간효율성을 비교 분석하였다. 실험에는 T25I10D10K 데이터 집합을 사용하여 최소지지도를 1%부터 10%까지 1%씩 증가시켜가며 실험하였다. 실험 결과는 Fig.
다음은 PPFP 알고리즘과 메모리 기반의 마이닝 방법인 FP-growth의 시간효율성 비교 실험이다. 실험을 위해 T10I4D100K, T25I10D10K, T25I20D100K의 세 데이터 집합을 사용하였고, 최소지지도를 0.
다음은 PPFP 알고리즘과 메모리 기반의 마이닝 방법인 FP-growth의 시간효율성 비교 실험이다. 실험을 위해 T10I4D100K, T25I10D10K, T25I20D100K의 세 데이터 집합을 사용하였고, 최소지지도를 0.5%부터 1%까지 0.1%씩 증가시켜가며 PPFP와 FP-growth 알고리즘을 이용하여 마이닝하는데 소비되는 시간을 기록하였다. Fig.
이에 대한 성능 개선을 위해 현재 데이터베이스의 이점인 다중트랜잭션 환경을 이용하고, 멀티코어 환경에서 HDD 대신 SSD를 사용하여 성능을 향상시키는 실험을 진행하고 있다. 이러한 실험을 통해 FP-growth에 비해 떨어지는 시간 효율성을 개선시킬 수 있을 것이라 여겨진다.
대상 데이터
5GHz CPU와 DDR3 2G 메모리, HDD가 장착되고 윈도우7 32bit professional K 운영체제를 사용하는 컴퓨터에서 진행되었다. 데이터베이스는 오라클 11g Express Edition으로, 데이터베이스는 별도의 튜닝 없이 일반 SQL과 Table index만을 사용하여 실험하였다. 또한 데이터베이스의 경우 다중 접속을 이용한 다중 처리가 가능하지만, 실험을 위하여 한 번에 하나의 트랜잭션만 처리하도록 제한하였다.
실험에 사용된 데이터 집합(Data set)은 FP-Growth의 논문실험에서 사용된 IBM Almaden Quest research group의 generator를 이용하여 생성된 것이다. 이는 일반적으로 데이터 마이닝 논문의 실험을 위해 가장 널리 사용되는 데이터 집합으로 TxxIyyDzzzK 속성을 설정하며 실험에 적합한 데이터 집합을 생성할 수 있다.
데이터처리
두 번째 실험은 PPFP 알고리즘의 시간효율성과 관련된 실험이다. 실험을 통해 PPFP 알고리즘과 SQL기반의 FPgrowth방법의 마이닝 처리 시간을 비교하여 보조기억장치를 활용하여 빈발 패턴을 마이닝하는 방법에서 PPFP알고리즘의 시간효율성을 비교 분석하였다. 실험에는 T25I10D10K 데이터 집합을 사용하여 최소지지도를 1%부터 10%까지 1%씩 증가시켜가며 실험하였다.
이론/모형
PPFP 빈발 패턴 마이닝을 위해 트랜잭션 데이터베이스를 압축시켜 필요한 정보만을 가지는 압축된 데이터 구조가 필요하다. 이를 위해 우리는 현재 가장 인기 있는 압축된 데이터 구조 중 하나인 FP-tree를 이용하였다. FP-tree는 압축된 데이터 정보를 가지고 있는 정교한 트리 구조일 뿐만 아니라, 트리 구성 시 최소지지도를 만족시키지 못하는 아이템들을 가지치기하여 불필요한 검색 영역을 줄일 수 있다.
성능/효과
현재 가장 널이 사용되는 빈발 패턴 마이닝 방법 중 하나인 FP-growth를 RDBMS를 기반으로 통합한 이 연구는 기존의 시간효율성만 고려한 방법들과 차별성을 보인다. 트랜잭션 데이터베이스를 SQL을 이용해 테이블상에 트리 구조를 평면적으로 구현하고, 그렇게 만들어진 FP 테이블을 SQL을 이용하여 빈발 패턴을 마이닝하여 빈발 패턴 마이닝의 공간적인 제약을 줄여주었다.
앞서 살펴본 바와 같이 FP-growth는 시간 효율성 측면에서 매우 뛰어난 성능을 보인다. 뿐만 아니라 기존의 Apriori 방식의 방대한 양의 후보 집합을 생성하는 방법들에 비해 확장성 측면에서도 좋은 성능을 보여준다. 하지만 FP-growth 과정에서 빈발 패턴을 마이닝하기 위해 메모리상에 조건부 패턴 트리를 누적하여 상주시켜야 하기 때문에 빅데이터의경우 물리적 메모리의 한계로 인해 마이닝이 어려울 수 있다.
예제를 통해 살펴본 바와 같이, FP-growth가 FP-tree를 이용해 조건부 패턴 베이스를 생성한 후 이를 이용하여 조건부 FP-tree를 메모리상에 쌓아 나가며 빈발 패턴을 구하는 반면, PPFP는 IFP-table에서 SQL을 통해 조건부 패턴 베이스를 구해 스택에 PUSH한 후 하나씩 POP해 나가며 빈발 패턴을 구하고 있다. IFP-table에만 존재하는 새로운 인덱스 방식으로 트리를 테이블화 하였기에 테이블에 존재하는 트리 정보로 하위 테이블을 구해내는 것이 가능해졌다.
7에서와 같이 PPFP방식은 SQL기반의 방식에 비해 매우 좋은 시간효율성을 보이고 있다. 최소지지도가 1%인 경우 PPFP에 비해 SQL기반의 방식이 100배 이상의 시간이 소비되고, 10%의 경우 200배 이상의 차이를 보였다.
실험 결과에서 보이는 바와 같이, PPFP 알고리즘이 기존의 보조기억장치를 활용한 방법들에 비해 빠른 성능을 보이지만 메모리 기반의 FP-Growth에 비해서는 많은 시간이 소비되는 것을 볼 수 있다. 하지만 PPFP 알고리즘의 경우 최소지지도가 증가함에 따라 처리시간이 급격히 줄어드는 것을 볼 수 있다.
PPFP 알고리즘은 메모리와 보조기억장치를 적절히 활용 하여 기존에 메모리 의존적인 알고리즘들에 비해 확장성을 높이고, 또한 보조기억장치만을 활용한 방법들에 비해 시간효율성을 높인 새로운 빈도 패턴 마이닝 방법이다. 실험을 통해 기존의 메모리 의존성이 높은 FP-growth에 비해 PPFP 알고리즘이 확장성이 높다는 것과, 기존의 보조기억장치를 활용한 SQL 기반의 FP-growth 방식에 비해 시간효율성이 좋다는 것 역시 확인할 수 있었다.
하지만, 기존의 보조기억장치를 활용한 방법들에 비해 시간적인 비용을 줄이는데 일조하였으나, 여전히 FP-growth에 비해 시간효율성이 떨어지는 것을 볼 수 있었다.
후속연구
이에 대한 성능 개선을 위해 현재 데이터베이스의 이점인 다중트랜잭션 환경을 이용하고, 멀티코어 환경에서 HDD 대신 SSD를 사용하여 성능을 향상시키는 실험을 진행하고 있다. 이러한 실험을 통해 FP-growth에 비해 떨어지는 시간 효율성을 개선시킬 수 있을 것이라 여겨진다.
질의응답
핵심어
질문
논문에서 추출한 답변
FP-growth란 무엇인가?
FP-growth는 Apriori 기반의 방법들에서 비용이 많이 드는 후보 집합의 생성을 피하기 위해 만든 접근법으로, 그 이전의 연구에 비해 매우 빠른 속도로 빈발 패턴을 마이닝할 수 있다. FP-growth에 있어서 FP-tree는 트랜잭션 데이터베이스의 빈번하지 않은 아이템들을 우선 가지치기한 후 데이터를 압축시켜 주기 때문에 FP-growth를 진행할 영역을 줄여 주고, 단 두 번의 스캔으로 트리를 구성하여 반복적인 데이터 베이스 스캔 비용을 줄여준다.
FP-tree를 이용하면 어떤 방식으로 빈발 패턴을 추출하는가?
주어진 FP-tree를 이용하면 분할-정복 방식으로 빈발 패턴을 추출할 수 있다. 이 단계는 길이가 1인 패턴(헤더 테이블에 존재하는 단일 아이템에 해당하는 패턴)으로부터 시작하여 그것의 조건부 패턴 베이스(conditional pattern base, 해당 패턴을 하위 패턴으로 포함하여 함께 발생하는 아이템들의 집합으로 구성된 부분 데이터베이스)를 생성하여 그 조건부 FP-tree(conditional FP-tree)를 생성하여 재귀적으로 패턴을 구해내는 방법이다.
FP-growth는 어떤 단계로 구성되는가?
FP-growth는 두 단계로 구성된다. 첫 번째 단계는 FP-tree 를 생성하는 것이다. FP-tree는 효율적인 빈발 패턴 마이닝을 위해 트랜잭션 데이터베이스 내의 빈발 아이템 집합들을좀 더 압축시켜 FP-tree(a frequent pattern tree)라 불리는 새로운 데이터 구조에 저장하는 것이다. 두 번째 단계는 FP-tree를 이용하여 패턴을 마이닝하는 단계이다. 길이가 1인 패턴(최초의 접미 패턴)들로부터 시작하여 그것의 조건부 패턴 베이스(conditional pattern base)만을 고려하여 그것의 조건부 FP-tree(conditional FP-tree)를 반복적으로 생성하며 패턴을 찾아낸다.
참고문헌 (18)
R. Agrawal, T. Imieliski, and A. Swami, "Mining association rules between sets of items in large databases," in Proc. ACM SIGMOD Int. Conf. Manage. Data, pp.207-216, 1993.
R. Agrawal and R. Srikant, "Fast algorithms for mining association rules in large databases," in Proc. Int. Conf. Very Large Data Bases, pp.487-499, 1994.
A. Amir, R. Feldman, and R. Kashi, "A new and versatile method for association generation," Inf. Syst., Vol.22, No.6/7, pp.333-347, Sep.-Nov., 1997.
M. El-Hajj and O. R. Zaiane, "COFI approach for mining frequent item-sets revisited," in Proc. ACM SIGMOD Workshop Res. Issues Data Mining Knowl. Discovery, New York, pp.70-75, 2004.
W. Cheung and O. R. Zaiane, "Incremental mining of frequent patterns without candidate generation or support constraint," in Proc. IEEE Int. Conf. Database Eng. Appl., Los Alamitos, CA, pp.111-116, 2003.
C. K.-S. Leung, Q. I. Khan, and T. Hoque, "Cantree: A tree structure for efficient incremental mining of frequent patterns," in Proc. IEEE Int. Conf. Data Mining, Los Alamitos, CA, pp.274-308, 2005.
C. K. -S. Leung and Q. I. Khan, "DSTree: A Tree Structure for the Mining of Frequent Sets from Data Streams," in Proc. IEEE ICDM, pp.928-932, 2006.
J. H. Lee, "IRFP-tree: Intersection Rule Based FP-tree," KIPS Transaction on Software and Data Engineering, Vol. 5, Issue 3, pp.155-164, 2016.
J.-L. Koh and S.-F. Shieh, "An efficient approach for maintaining association rules based on adjusting FP-tree structures," in Proc. DASFAA, Springer-Verlag, Berlin Heidelberg New York, pp.417-424, 2004.
G. Liu, H. Lu, J. X. Yu, W. Wang, and X. Xiao, "AFOPT: An efficient implementation of pattern growth approach," in Proc. FIMI, 2003.
M. Adan and R. Alhajj, "DRFP-tree: Disc-resident frequent pattern tree," Appl. Intell., Vol.30, No.2, pp.207-216, 2009.
M. Adan and R. Alhajj, "A Bounded and Adaptive Memory-Based Approach to Mine Frequent Patterns From Very Large Databases," IEEE Transactions on Systems, Man, and Cybernetics, Part B, Vol.41, Issue 1, pp.154-172, 2011.
X. Shang, K.-U. Sattler, and I. Geist, "SQL Based Frequent Pattern Mining with FP-growth," in INAP/WLP, pp.32-46, 2005.
B. Goethals, "Memory issues in frequent itemset mining," in Proc. ACM SAC, pp.530-534, 2004.
R. Vaarandi, "A breadth-first algorithm for mining frequent patterns from event logs," in Proc. IEEE INTELLCOMM, pp.293-308, 2004.
G. Buehrer, S. Parthasarathy, and A. Ghoting, "Out-of-core frequent pattern mining on a commodity PC," in Proc. 12th ACM SIGKDD Int. Conf. KDD, pp.86-95, 2006.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.