| 1 |
1
데이터를 저장한 데이터베이스에 대해, 컴퓨터로 상기 데이터를 스캔하여 마이닝하는 방법으로서,(a) 가중화 빈도수 트리(Weighted Support-Tree)를 생성하는 단계;(b) 상기 데이터베이스에서 트랜잭션 데이터베이스를 상기 가중화 빈도수 트리에 적용하는 단계;(c) 상기 가중화 빈도수 트리에서, 상기 트랜잭션 데이터베이스 내의 아이템들의 가중화 빈도수가 마이닝 조건에 의해 자동 설정되는 상위 K번째보다 작은 아이템을 제거하는 단계; 및(d) 상기 가중화 빈도수 트리에 패턴 성장기법을 적용하는 단계를 포함하여 진행되는 것을 특징으로 하는 상위 K개의 중요 패턴들을 마이닝 하는 방법
|
| 2 |
2
제1항에 있어서, 상기 가중화 빈도수 트리는 압축된 형태의 트리 구조로서, 루트로부터 각 노드들은 가중화된 빈도수가 커지는 형태로 구성되고, 상기 트리 구조 옆에는 트랜잭션 안에 있는 아이템들의 빈도수 및 가중치와, 상기 트리에서 같은 아이템을 가지는 노드들을 포인팅하는 링크들로 구성된 헤더 테이블이 구비되어 있는 것을 특징으로 하는 상위 K개의 중요 패턴들을 마이닝 하는 방법
|
| 3 |
3
제1항에 있어서,상기 단계 (a)는,상기 데이터베이스에서 트랜잭션 데이터베이스를 스캔하여 읽는 단계;상기 트랜잭션 데이터베이스에서 각 트랜잭션 내에 있는 아이템들을 가중화 빈도수 순서의 오름차순이나 내림차순으로 정렬하는 단계;상기 트랜잭션 내의 정렬된 아이템들은 순차적으로 전역 가중화 빈도수 트리에 트리의 루트부터 대응되는 노드로의 경로를 따라서 삽입하는 단계;상기 삽입된 아이템이 기존 노드 아이템인지 판별하는 단계;상기 판별결과, 기존 노드 아이템이 아니면 그 노드안의 아이템의 빈도수가 계산되어 새로운 노드를 생성하고, 상기 판별결과 상기 가중화 빈도수 트리에서 기존의 노드 아이템이 이용된 것이면 그 노드 안에서 아이템의 빈도수를 1씩 증대시키는 단계;상기 새로운 노드 생성과 상기 노드의 빈도수를 1씩 증대시킨 후에는 상기 각각의 트리삽입 단계로 진입하여 반복적으로 상기의 처리과정들을 수행하는 단계를 포함하는 것을 특징으로 하는 상위 K개의 중요 패턴들을 마이닝 하는 방법
|
| 4 |
4
제1항에 있어서,상기 단계 (b)는,상기 아이템의 가중화 빈도수가 러프-컷오프(Rough-cutoff) 보다 작은 아이템을 제거하는 단계,상기 트랜잭션을 상기 가중화 빈도수 오름차순과 내림차순으로 정렬하여 상기 가중화 빈도수 트리에 루트로부터 대응되는 노드로의 경로에 따라서 삽입하는 단계를 통하여 진행하는 것을 특징으로 하는 상위 K개의 중요 패턴들을 마이닝 하는 방법
|
| 5 |
5
제1항에 있어서,상기 단계 (c)는,(c-1) 상기 러프-컷오프(Rough-cutoff) 방식을 이용하여 상기 상위 K개의 중요 패턴을 마이닝할 때 상기 러프-컷오프보다 작은 아이템을 제거하고,(c-2) 터프-컷오프(Tough-cutoff) 방식을 이용하여 로컬 트리를 생성할 때 최대 가중화 빈도수가 상기 터프-컷오프보다 작은 패턴들을 모두 제거하는 방법을 사용하는 것을 특징으로 하는 상위 K개의 중요 패턴들을 마이닝 하는 방법
|
| 6 |
6
제5항에 있어서,상기 단계 (c-1)은,상기 데이터베이스에서 트랜잭션 데이터베이스를 스캔하여 읽는 단계;상기 데이터베이스 내의 각 트랜잭션 내에 있는 아이템들을 가중화 빈도수 오름차순인 경우 가중화 빈도수가 커지는 순으로 정렬하고, 빈도수 내림차순인 경우 가중화 빈도수가 작아지는 순으로 정렬하는 단계;상기 러프-컷오프(rough-cutoff)를 계산하는 단계;상기 러프-컷오프(Rough-cutoff) 조건을 통과한 아이템들만을 전역 또는 지역 가중화 빈도수 트리에 삽입하는 단계를 특징으로 하는 상위 K개의 중요 패턴들을 마이닝 하는 방법
|
| 7 |
7
제1항에 있어서,상기 단계 (d)는,상기 가중화 빈도수 트리의 형태가 싱글 패스(path)인지 판별하는 단계,상기 판별결과, 상기 트리가 싱글 패스이면, 경로의 아이템의 집합을 모두 만들어 상기 터프-컷오프(Tough-cutoff)보다 큰 아이템을 상위 K개의 아이템에 추가하는 단계,상기 판별결과, 상기 트리가 싱글 패스가 아니면, 가중화 빈도수가 가장 큰 리프 노드부터 루트방향으로 순회(traversal)를 하는 단계,상기 헤더 테이블에서 선택된 아이템의 링크 노드를 따라 연결된 노드에서 상기 트리의 루트까지 상향식으로 탐색을 하거나 상기 연결된 노드에서 상기 트리의 리프까지 BFS(Breadth First Search)방식과 DFS(Depth First Search) 방식을 이용하여 하향식으로 탐색하는 단계,상기 탐색된 경로의 아이템들을 하나의 조건적 트랜잭션으로 만들어서, 가장 작은 초기 상기 터프-컷오프(Tough-cutoff)보다 작은 아이템을 조건적 트랜잭션에서 제거하는 단계,상기 터프-컷오프 방식으로 최적화된 조건적 데이터베이스를 구축한 후, 구축된 상기 조건적 데이터베이스를 스캔하여 로컬 가중화 빈도수 트리를 생성하는 단계,상기 생성된 로컬 가중화 빈도수 트리를 상기 패턴 성장기법을 이용하여 반복적으로 진행하는 단계를 특징으로 하는 상위 K개의 중요 패턴들을 마이닝 하는 방법
|
| 8 |
8
제7항에 있어서, 상기 가중화 빈도수 트리를 상기 BFS(Breadth First Search)방식과 상기 DFS(Depth First Search) 방식을 이용하여 하향식으로 탐색하는 단계는, 함수의 재귀 호출을 이용하여 진행하며, 상기 BFS방식은 상기 트리의 형제 노드를 먼저 호출하는 방식으로 탐색하고, 상기 DFS방식은 상기 트리의 자식 노드를 먼저 호출하는 방식으로 탐색하는 것을 특징으로 하는 상위 K개의 중요 패턴들을 마이닝 하는 방법
|
| 9 |
9
제7항에 있어서, 상기 가중화 빈도수 트리를 상기 BFS(Breadth First Search)방식과 상기 DFS(Depth First Search) 방식을 이용하여 하향식으로 탐색하는 단계는, 상기 함수의 반복자를 이용하며, 상기 BFS방식은 큐를 이용하여 자식 노드의 주소를 저장하여 사용하고, 상기 DFS방식은 스택을 이용하는데, 상기 스택에는 상기 자식 노드의 주소가 하나씩 삽입되고 현재까지 탐색된 노드의 아이템이 기록되어 있는 것을 특징으로 하는 상위 K개의 중요 패턴들을 마이닝 하는 방법
|
| 10 |
10
제7항 내지 제9항의 어느 한 항에 있어서, 상기 조건적 데이터베이스의 구축은, 상기 리프 노드에 도달하거나 상기 자식 노드의 빈도수 합이 현재 노드의 빈도수 합보다 작으면 하나의 경로로 인식하여 구축되는 것을 특징으로 하는 상위 K개의 중요 패턴들을 마이닝 하는 방법
|
