그래프 구조를 이용한 효율적인 연관규칙분석 알고리즘
Using a Graph Structure for an efficient Association Rule Mining Algorithm
- 주제(키워드) Data Mining , Association Rule , Graph Structure , Transaction Grouping , Node Reuse
- 발행기관 고려대학교 대학원
- 지도교수 서용무
- 발행년도 2010
- 학위수여년월 2010. 2
- 학위구분 석사
- 학과 일반대학원 경영학과
- 세부전공 MIS 전공
- 원문페이지 44 p
- 실제URI http://www.dcollection.net/handler/korea/000000021683
- 본문언어 한국어
- 제출원본 000045592172
초록/요약
1990년대 초반 데이터마이닝 방법론이 등장한 이후 현재까지 정확성과 신속성을 향상시 키기 위한 기법들이 꾸준히 연구되고 있다. 본 연구에서는 데이터마이닝 방법론 중 하나인 연관규칙분석 과정에서 그래프 구조를 사용하여 작업 수행 시간을 최소화하였다. 본 연구에 서 제시한 알고리즘의 특징은 다음과 같다. 첫째, 데이터베이스 스캐닝을 하여 연관규칙을 찾는데 필요한 모든 정보를 그래프에 저장하였다. 둘째, 트랜잭션 그룹핑을 통해 동일한 레 코드 값에 대한 접근 횟수를 최소화하였다. 셋째, 동일한 데이터에서 파라미터의 값만 변경 하여 새로 연관규칙을 찾으려 하는 경우, 기 생성된 노드의 데이터를 재사용함으로써 연관 규칙을 찾는 시간을 최소화하였다. 넷째, 빈발항목집합을 찾는 과정에서 후보항목집합의 생 성을 배제하였다. 마지막으로, 알고리즘의 성능을 측정하기 위하여 전통적인 연관규칙분석 방법인 Apriori Algorithm과 메모리 기반의 데이터 클러스터링 방법을 사용한 Clusterbased Association Rule Algorithm을 구현하여 비교한 결과, 본 연구에서 제시한 알고리즘 이 기존 연구보다 효율성이 높게 나타남을 확인하였다.
more목차
I. 서 론 …………………………………………… 6
II. 연구배경 …………………………………………… 8
2-1. 연관규칙분석 ……… 8
2-2. 연관규칙분석 알고리즘의 신속성 ……… 8
2-3. 연관규칙분석 알고리즘의 정확성 ……… 10
2-4. 규칙에 포함된 일반화 수준에 따른 연관규칙분석 알고리즘 ……… 10
2-5. 신속성 향상을 위한 본 연구의 특징 ……… 11
III. 트랜잭션 그룹핑 …………………………………………… 12
IV. 그래프 구조 …………………………………………… 14
V. Smart Algorithm …………………………………………… 16
5-1. Algorithm 1: 데이터마이닝을 처음 시도한 경우 ……… 17
5-2. Algorithm 2: Min_sup 값을 이전 min_sup 값보다 작게 조정한 경우 ……… 18
5-3. Algorithm 3: Min_sup 값을 이전 min_sup 값보다 크게 설정한 경우 ……… 19
VI. Smart Algorithm을 적용한 예제 …………………………………………… 20
6-1. 데이터베이스를 스캐닝하여 그래프 구조 생성하기 ……… 20
6-2. 기존에 생성된 그래프 구조에 노드 추가 생성하기 ……… 26
6-3. 그래프 구조에서 조건에 만족하는 빈발항목집합만 출력하기 ……… 27
VII. 알고리즘의 성능 비교 …………………………………………… 29
7-1. 첫 번째 실험 그룹의 알고리즘 테스트 결과와 트랜잭션 그룹 분석 ……… 29
7-2. 두 번째 실험 그룹의 알고리즘 테스트 결과와 트랜잭션 그룹 분석 ……… 31
7-3. Apriori, CBAR, Smart Algorithm 비교 ……… 32
7-4. 데이터마이닝의 반복 수행에 따른 시간 효율성 비교 ……… 34
7-5. 데이터마이닝을 통해 얻은 규칙 분석 ……… 35
VIII. 결 론 …………………………………………… 36
참고문헌 …………………………………………… 37
부 록 …………………………………………… 40
