초록

용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

순차 패턴을 찾는 것은 데이타 마이닝 응용분야에서 중요한 문제이다. 기존의 순차 패턴 마이닝 알고리즘들은 아이템으로만 이루어진 순차 패턴만을 취급하였으나 Apriori-QSP에서는 새롭게 퀀터티 정보에 대한 처리의 개념을 도입하였다. 전채 순차 패턴을 찾는 알고리즘들은 너비 우선 탐색과 깊이 우선 탐색 기법으로 분류할 수 있는데, 이러한 분류에서 Apriori-QSP알고리즘은 너비 우선 탐색 기법으로 분류할 수 있다. 본 논문에서는 퀀터티 정보를 처리하는 깊이 우선 탐색 기법을 제안하였다. Apriori-QSP에서 제안되었던 후보패턴 생성에 대한 필터링파 샘플링 기법을 깊이 우선 탐색의 탐색 기법으로 적용하였으며, 다양한 실험 결과들이 깊이 우선 탐색에서도 이러한 기법이 효율적임을 보여 주고 있다. 또한 길이가 긴 순차 패턴 마이닝의 경우 너비우선 탐색에 비해 향상된 성능을 보임을 확인하였다.

순차 패턴을 찾는 것은 데이타 마이닝 응용분야에서 중요한 문제이다. 기존의 순차 패턴 마이닝 알고리즘들은 아이템으로만 이루어진 순차 패턴만을 취급하였으나 Apriori-QSP에서는 새롭게 퀀터티 정보에 대한 처리의 개념을 도입하였다. 전채 순차 패턴을 찾는 알고리즘들은 너비 우선 탐색과 깊이 우선 탐색 기법으로 분류할 수 있는데, 이러한 분류에서 Apriori-QSP알고리즘은 너비 우선 탐색 기법으로 분류할 수 있다. 본 논문에서는 퀀터티 정보를 처리하는 깊이 우선 탐색 기법을 제안하였다. Apriori-QSP에서 제안되었던 후보패턴 생성에 대한 필터링파 샘플링 기법을 깊이 우선 탐색의 탐색 기법으로 적용하였으며, 다양한 실험 결과들이 깊이 우선 탐색에서도 이러한 기법이 효율적임을 보여 주고 있다. 또한 길이가 긴 순차 패턴 마이닝의 경우 너비우선 탐색에 비해 향상된 성능을 보임을 확인하였다.

AI 본문요약

엑셀 다운로드 AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

• 연구 주제
• 연구 방법
• 연구 결과

문제 정의

• 길이가 1인 순차 패턴 단위로 재귀적 호출이 일어나는 Level-by-Level의 경우를 생각해 보자. 순차 패턴 /의 아이템 을 로 나타내기로 하자.
• 퀀터티가 있는 순차 패턴을 찾는 깊이 우선 알고리즘으로 PrefixSpan 알고리즘의 초보적인 확장 알고리즘은 재귀적 호출의 수를 크게 늘리게 되어 결과적으로 수행 시간도 크게 중가하였다. 따라서 결과를 얻는 데에 필요한 재귀적 호출의 수를 줄임으로써 수행 시간을 개선할 수 있는 방법을 제안하였다. 즉, 여과 과정(filtered counting)과 샘플링 기반 알고리즘(sampling based algorithm) 이라는 아이디어를 사용하여 최대의 패턴이 될 수 없는 재귀적 호출들을 미리 전지함으로써 알고리즘의 수행속도를 매우 개선하였다.
• 마지막으로 본 논문에서 제시한 알고리즘과 Apriori-All 알고리즘과의 수행 시간에 관한 비교 결과률 살펴보자. 그림 2는 Repetition Level을 변화시키면서 알고리즘 간의 성능의 변화를 살펴본 그래프이다.
• 본 논문에서는 기존의 깊이 우선 순차 패턴 마이닝을 확장하여 퀀터티 정보까지도 포함한 깊이 우선 순차 패턴 마이닝 알고리즘을 제시하였다. 이러한 갚이 우선 순차 패턴 마이닝 알고리즘 온 륵히 길이가 긴 순차 패턴에 대한 검색의 경우 너비 우선 탐색 기법에 비해 좋은 성능을 보인다.

제안 방법

• 따라서 결과를 얻는 데에 필요한 재귀적 호출의 수를 줄임으로써 수행 시간을 개선할 수 있는 방법을 제안하였다. 즉, 여과 과정(filtered counting)과 샘플링 기반 알고리즘(sampling based algorithm) 이라는 아이디어를 사용하여 최대의 패턴이 될 수 없는 재귀적 호출들을 미리 전지함으로써 알고리즘의 수행속도를 매우 개선하였다.

대상 데이터

• 모든 실험은 LINUX 운영체제에 메모리 512MB인 Pen- tium4PC에서 실행되었다,
• 합성 데이타를 만드는 데에는 Apriori-QSP[4]에서와 동일한 데이터 생성기률 사용하였다. 본 논문에서 사용된 실험 데이타들온 시퀀스당 평균 트랜잭션 수 10, 트랜잭션당 평균 아이템 수 2.5, 총 아이템 수 100,000개의 파라미터로 생성 된데이타들이다.

이론/모형

• 합성 데이타를 만드는 데에는 Apriori-QSP[4]에서와 동일한 데이터 생성기률 사용하였다. 본 논문에서 사용된 실험 데이타들온 시퀀스당 평균 트랜잭션 수 10, 트랜잭션당 평균 아이템 수 2.

성능/효과

• 그림 2는 Repetition Level을 변화시키면서 알고리즘 간의 성능의 변화를 살펴본 그래프이다. Repetition Level이 커질수록 순차 패턴의 길이가 길어지며, 순차 패턴의 길이가 길어질수록 점차 PrefixSpan-Allo] 더욱 좋은 성능을 보임을 확인할 수 있다.
• 그림 1은 각각의 알고리즘들의 최소 지지도별 수행속도를 보여준다. 본 논문에서 제시하는 아이디어의 유무에 따른 수행 시간의 차이는 최소 지지도가 낮아질수록 더욱 커짐을 알 수 있다.
• 실험결과를 통해 본 논문이 제시하는 알고리즘이 초보적으로 확장된 알고리즘에 비해 50% 이상의 수행 시간 단축을 보여준다는 사실을 알 수 있으며, 길이가 긴 순차 패턴의 경우 Apriori-All보다 뛰어난 성능을 보임을 확인할 수 있다.
• 퀀터티가 있는 순차 패턴을 찾는 깊이 우선 알고리즘으로 PrefixSpan 알고리즘의 초보적인 확장 알고리즘은 재귀적 호출의 수를 크게 늘리게 되어 결과적으로 수행 시간도 크게 중가하였다. 따라서 결과를 얻는 데에 필요한 재귀적 호출의 수를 줄임으로써 수행 시간을 개선할 수 있는 방법을 제안하였다.

본문요약 정보가 도움이 되었나요? 예 아니오 제출

이 논문을 인용한 문헌

더보기