- 희소 데이터 집합에서 효율적인 빈발 항목집합 탐사 기법
- ㆍ 저자명
- 박인창,장중혁,이원석,Park. In-Chang,Chang. Joong-Hyuk,Lee. Won-Suk
- ㆍ 간행물명
- 정보처리학회논문지. The KIPS transactions. Part D. Part D
- ㆍ 권/호정보
- 2005년|6호|pp.817-828 (12 pages)
- ㆍ 발행정보
- 한국정보처리학회
- ㆍ 파일정보
- 정기간행물| PDF텍스트
- ㆍ 주제분야
- 기타
빈발 항목집합 마이닝 분야의 주된 연구 주제는 수행과정에서의 메모리 사용량을 줄이고 짧은 수행 시간에 마이닝 결과 집합을 얻는 것으로서, 빈발항목 탐색을 위한 다수의 방법들은 Apriori 알고리즘에 기반을 둔 다중 탐색 방법들이다. 또한 최대 빈발 패턴의 길이가 길어질수록 마이닝 수행 시간이 급격히 증가되는 단점을 가진다. 이를 극복하기 위해서 이전의 연구에서 마이닝 수행 시간을 단축하기 위한 다양한 방법들이 제안되었다. 하지만, 다수의 이들 방법들은 희소 데이터 집합에서는 다소 비효율적인 성능을 나타낸다. 본 논문에서도 효율적인 빈발항목 탐색 방법을 제안하였다. 먼저 빈발항목 탐색을 위한 새로운 트리 구조인 $L_2$-tree 구조를 제안하였으며, 더불어 $L_2$-tree를 이용하여 빈발 항목집합을 탐색하는 $L_2$-traverse 알고리즘을 제안하였다. $L_2$-traverse 구조는 길이가 2인 빈발 항목집합 $L_2$에 기반하여 생성되는 것으로서 크기가 매우 작으며, 이를 활용한 $L_2$-traverse 알고리즘은 $L_2$-tree를 단순히 한번 탐색함으로써 전체 빈발 항목집합을 빠른 시간에 구한다. 또한 수행 시간을 보다 단축할 수 있는 방법으로 길이가 3인 빈발 항목집합 $L_3$가 될 수 없는 $L_2$ 패턴들을 미리 제거하는 $C_3$-traverse 알고리즘도 제안하였다. 다양한 실험을 통해 제안된 방법들은 특히 $L_2$가 상대적으로 적은 희소 데이터 집합 환경일 때 기존의 다른 방법들보다 우수함을 검증하였다.였고, 링크 경쟁을 완화함으로써 보다 균일한 링크 사용을 나타냈고, 링크 획득 실패로 인한 지 연시간을 감소시켰다. 프로그램 구동 시뮬레이션을 통한 성능 검증 결과, 논문에서 제시한 동적경로 설정 방법은 기존 정적 경로 설정 방법에 비해 링크점유시간 편차가 $1{~}10\%$ 낮게 나타났고, 링크의 획득 실패 횟수가 ${~}3\%$ 감소하였으며, 그 결과 $1{~}6\%$의 수행 시간 감소를 나타냈다.기간이 경과함에 따라 그러한 영향은 거의 없어지는 것으로 나타났다. 수술 직후의 좌 우측 평균 고관절 등급은 각각 $2.7pml.1,;2.7pm0.9$ (n=36) 이었다. 수술 직후와 2, 4, 8, 12, 24주 후의 고관절 등급이 수술 전에 비하여 유의적으로 개선된 것을 확인하였다.(P<0.01). 수술 후 정기적인 검사 시에 측정한 Norberg angle, percentage of femoral head coverage도 수술 전과 비교해 유의성 있게 증가하였다(P<0.01). 변형 3중 골반 절골술 직후의 평균 골반직경은 수술 전의 골반직경보다 유의적으로 증가하였으며(P<0.01)(n=36) 수술 후 평균 9.3L2.7주에 절골선 유합이 종료되었다(n=21). 반면 편측 3중 골반 절골술을 실시한 경우에는 수술 후 골반경이 수술 전과 비교해 증가하지 않았다. 변형 3중 골반 절골술후에 장액종 형성(1마리), 스크류 변위(4마리), 스크류 부러짐(1마리), 편측성 신경마비(1마리) 등의 부작용이 발생하였다. 이상의 결과를 토대로, 변형 3중 골반 절골술은 개의 고관절 이형성의 효과적인 치료 방법이라 사료된다.테로이드 의존성 미세변화형 신증후군의 치료에서는 스테로이드 의존성
The main research problems in a mining frequent itemsets are reducing memory usage and processing time of the mining process, and most of the previous algorithms for finding frequent itemsets are based on an Apriori-property, and they are multi-scan algorithms. Moreover, their processing time are greatly increased as the length of a maximal frequent itemset. To overcome this drawback, another approaches had been actively proposed in previous researches to reduce the processing time. However, they are not efficient on a sparse .data set This paper proposed an efficient mining algorithm for finding frequent itemsets. A novel tree structure, called an $L_2$-tree, was proposed int, and an efficient mining algorithm of frequent itemsets using $L_2$-tree, called an $L_2$-traverse algorithm was also proposed. An $L_2$-tree is constructed from $L_2$, i.e., a set of frequent itemsets of size 2, and an $L_2$-traverse algorithm can find its mining result in a short time by traversing the $L_2$-tree once. To reduce the processing more, this paper also proposed an optimized algorithm $C_3$-traverse, which removes previously an itemset in $L_2$ not to be a frequent itemsets of size 3. Through various experiments, it was verified that the proposed algorithms were efficient in a sparse data set.