초록

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

연관규칙 탐사기법은 거래(사건) 속에 포함된 품목(항목)간의 연관관계를 발견하고자 할 때 사용하는 기법이며, 독특한 형태의 자료구조를 사용하는 다양한 연관규칙 알고리즘들이 제안되었다. 다양한 특성을 갖는 대용량의 데이터에 대해 효율적으로 연관규칙 탐사를 수행하기 위해서는 저장공간과 실행시간을 모두 고려해야 한다. 본 논문에서는 후보항목집합 발생과정 없이 압축빈발항목집합과 동적링크집합을 이용하여 저장공간 축소와 실행시간 개선을 동시에 고려한 연관규칙 알고리즘을 제안하며, 그 우수성을 증명하기 위해 연관규칙 탐사의 대표적인 자료 구조인 FP-struct, H-Struct와의 저장공간 비교 및 이들 저장구조를 사용하는 FP-growth, H-mine 알고리즘과의 실행시간을 비교한다.

연관규칙 탐사기법은 거래(사건) 속에 포함된 품목(항목)간의 연관관계를 발견하고자 할 때 사용하는 기법이며, 독특한 형태의 자료구조를 사용하는 다양한 연관규칙 알고리즘들이 제안되었다. 다양한 특성을 갖는 대용량의 데이터에 대해 효율적으로 연관규칙 탐사를 수행하기 위해서는 저장공간과 실행시간을 모두 고려해야 한다. 본 논문에서는 후보항목집합 발생과정 없이 압축빈발항목집합과 동적링크집합을 이용하여 저장공간 축소와 실행시간 개선을 동시에 고려한 연관규칙 알고리즘을 제안하며, 그 우수성을 증명하기 위해 연관규칙 탐사의 대표적인 자료 구조인 FP-struct, H-Struct와의 저장공간 비교 및 이들 저장구조를 사용하는 FP-growth, H-mine 알고리즘과의 실행시간을 비교한다.

AI 본문요약

엑셀 다운로드 AI-Helper

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

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

문제 정의

• 본 논문에서 제안한 FUSION 연관규칙 알고리즘은 저 장공간 축소와 실행시간 개선을 동시에 고려하기 위해 제안되었다. 실행시간 개선을 위해 후보항목집합 발생과 정 없이 2번의 트랜잭션 데이터베이스 스캔을 통해 빈발 항목집합을 발견하며, 같은 항목들로 구성된 Frequent Projection에 대해 같은 저장공간을 사용함으로서 검색 횟수의 감소와 저장공간 축소 효과를 얻을 수 있다.
• 본 논문에서는 후보항목집합 발생과정 없이 압축빈발 항목집합과 동적링크집합을 이용하여 저장공간 축소와 실행시간 개선을 고려한 연관규칙 알고리즘을 제안하였다. 웹 환경등에서 실시간으로 연관 규칙 탐사를 수행하기 위해서는 고속의 연관 규칙 알고리즘이 필요하며, 특히 대용량 데이터에 대해 적은 저장공간을 사용하여 연관규칙을 수행할 경우, 보다 많은 양의 데이터를 메모리 상에서 처리할 수 있기 때문에, 저장공간의 축소가 실행 속도의 향상에 직접적인 영향을 줄 수 있다.

제안 방법

• 실험에 사용된 FP-growth, H-mine, FUSION 알고리즘은 모두 비 Apriori계 알고리즘들로써 JAVA로 구현하였고, 실험 데이터 이에 대해 저장공간 크기와 실행속도를 실험하였다. 본 실험은 450MHz Pentium, 192Mem, 40G hard disk로 구성된 PC에서 이루어졌다.
• 그러므로 대용량 데이터에 대해 고속으로 연관규칙 탐사를 수행하기 위해서는 저장공간과 실행 시간을 동시에 고려한 알고리즘이 필요하다. 이를 위해 본 논문에서는 후보 빈발항목집합 발생과정 없이 압축빈발항목집합과 동적링크집합을 이용하여 저 장공간 축소와 실행시간 개선을 동시에 고려한 연관 규칙 알고리즘을 제안한다.

대상 데이터

• 실험에 사용된 FP-growth, H-mine, FUSION 알고리즘은 모두 비 Apriori계 알고리즘들로써 JAVA로 구현하였고, 실험 데이터 이에 대해 저장공간 크기와 실행속도를 실험하였다. 본 실험은 450MHz Pentium, 192Mem, 40G hard disk로 구성된 PC에서 이루어졌다.
• 실험 데이터는 백화점 거래데이터를 사용하였으며, 표1 은 실험 데이터 특성을 나타낸다.

성능/효과

• 2개의 Frequent Projection (f, c, a, m, "가 같은 저 장 공간을 사용하고 있으며, 각 항목 사이에 불필요한 링크공간이 없음을 확인할 수 있다. 'f'에 대한 빈발항목 집합 탐사를 하면서 두 번째 아이템인 'c, 에 대한 링크를 헤더테이블에 추가하여 'f'에 대한 탐사가 끝난 후, bactracking 작업 없이 'c'에 대한 완전한 링크 정보를 얻을 수 있고, '“의 링크 집합을 헤더테이블로부터 제거하여 임시 저장공간의 확대를 방지한다.
• 본 논문에서 제안한 FUSION 연관규칙 알고리즘은 저 장공간 축소와 실행시간 개선을 동시에 고려하기 위해 제안되었다. 실행시간 개선을 위해 후보항목집합 발생과 정 없이 2번의 트랜잭션 데이터베이스 스캔을 통해 빈발 항목집합을 발견하며, 같은 항목들로 구성된 Frequent Projection에 대해 같은 저장공간을 사용함으로서 검색 횟수의 감소와 저장공간 축소 효과를 얻을 수 있다. 또 한 빈발항목집합 발견시 사용되는 동적링크집합을 임시 구조인 헤더테이블에 포함시켜 사용하지 않는 링크공간 으로 인한 저장공간의 낭비를 제거하였다.
• 그림4는 지지도 임계치 변화에 대한 각 알고리즘의 저 장공간 크기 결과를 나타내고 있다. 실험 결과 전 구간에 걸쳐 FUSION-struct가 가장 적은 저장공간을 사용하고, 지지도 임계치가 높아질수록 데이터가 상대적으로 dense해짐에 따라 지지도 임계치 약 0.4%를 기점으로 FP-struct가 H-struct보다 적은 양의 저장공간을 사용하고 있음을 확인 할 수 있다.
• 그림5는 지지도 임계치 변화에 대한 각 알고리즘의 실행속도 결과를 나타내고 있다. 실험 결과 전 구간에 걸쳐 FUSIONo] 가장 빠른 실행 속도를 보이며, 지지도 임계치가 낮아질수록 데이터가 상대적으로 sparse해짐에 따라, FP-growth와의 차이가 점점 커지는 것을 확인할 수 있다. H-mine은 FP-growth에 비해 적은 차이를 보이고 있지만, 그림4에서 FUSION-struct가 H-struct에 비해 뚜렷한 저장공간 축소효과가 있음을 확인할 수 있다.

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

이 논문을 인용한 문헌

더보기