Continuous Pattern Mining Using the FCPGrowth Algorithm in Trajectory Data Warehouse 요약

Continuous Pattern Mining Using the FCPGrowth Algorithm in Trajectory Data Warehouse

Marcin Gorawhki and Pawel Jureczek

Abstract

1) 이 논문은 FCP-Tree 인덱스 구조를 보여주고 FCPGrowth라는 새로운 알고리즘을 보여주기 위한 논문이다.

2) FCPGrowth는 새로운 알고리즘으로 경로 데이터 웨어하우스에서 연속적인 패턴의 마이닝을 위한 알고리즘이다.

3) FCP-Tree는 종합적인 트리로 같은 노드들에서 비슷한 연속적인 것들을 저장한다.

4) FCPGrowth의 특징은 recursion level의 중간단계의 트리들을 구성할 필요가 없다. 따라서 적은 용량의 메모리만 요구.

5) FCPGrowth는 최초로 생성될 때 연속적인 입력을 드문요소들로 분할한다. 따라서 구조가 촘촘해진다.

1. Introduction

1) Frequent Pattern 마이닝은 반복적인 상황을 발견하기 위해서 많은 응용프로그램에서 사용하고있다.

2) FCPGrowth 알고리즘은 물체들의 자주 그리고 연속적인 경로들을 감지한다. 그리고 이것은 물체의 행동들에 대한 세부적인 분석을 위해 사용된다.

3) 이전에 연속적인 패턴을 마이닝하는 여러 알고리즘이 존재했지만 이러한 기존의 기술보다 FCPGrowth 알고리즘이 하나의 시퀀스가 요소들의 반복성을 포함하지 않기 때문에 recursive call에서 prefix tree를 만들 필요가 없다.

2, Continuous Sequential Patterns

이 논문에서는 다음을 추정한다.

1) 각 요소는 한 시퀀스에서 한번 발생한다. 예를 들어서 시쿼스 A-> B-> A-> C 는 A가 두번 발생했으므로 적합하지 않은 것이다. 이러한 가정은 엄격하지는 않다. 물체의 이동 경로상에서 단복되는 요소들을 포함하는 일은 거의 존재하지 않는데 예를 들어서 자동차를 타고 여행한다고 할 때 여행자들은 네비게이션을 통해서 가장 짧은 경로를 선택할 것이기 때문이다.

2) regular grid를 위한 흥미있는 지역들의 continuous sequence들의 분석을 하기 위해서 저자들은 시퀀스의 continuity를 지키기를 원한다.

3. FCP-Tree Index and FCPGrowth Algorithm

1)

4. Pseudocodes

생략

5. Experiments

1) Generating Network-Based Moving Objects라는 프레임워크를 통해 경로를 생성했다.

2) FCPGrowth의 성능을 알아보기 위해 VAES 알고리즘을 사용하여 서로 비교하였다.

3) 모든 알고리즘은 자바로 작성되었고, 코드를 돌린 컴퓨터의 성능은 인텔 코어 듀오 E6550 2.33GHz와 4GB RAM이 었으며 윈도우7 상에서 돌렸다.

4) Fig5는 경로의 수와 최소 support minsup의 수치가 달라짐에 따라 두 알고리즘의 러닝타임을 비교한 표이다.

5) Fig6는 FCPGrowth 알고리즘의 구체적인 성능을 보여주는 표이다.

6) 결과를 보면 항상 FCPGrowth 알고리즘은 VAES 알고리즘보다 더 좋은 성능을 보여준다.

7) 두 알고리즘 모두 시퀀스의 숫자가 증가하면 러닝타임이 증가한다.

8) FCPGrowth 알고리즘의 경우 이러한 현상은 FCP-Tree에 삽입 되어져야 하는 시퀀스의 수가 증가하기 때문이다.

9) FCPGrowth 알고리즘 VAES 알고리즘보다 좋은 원인은 FCP-Tree에서 시퀀스의 집합 때문이다.

6. Conclusion

1) 이 논문에서는 FCP-Tree 구조에 기반한 연속적인 패턴 마이닝을 위한 FCPGrowth 알고리즘을 보여주었다.

2) FCPGrowth와 VAES 알고리즘과의 성능 비교를 했다.

3) 미래 과제로는 새로운 질문에 대해 연구해 볼 생각이며, 이 생각은 최대 그리고 닫혀진 패턴을 마이닝하는 것이다.

4) 또한 데이터의 업데이트를 보조하는 FCP-Tree의 버젼을 사용할 것이다.