[논문]데이터베이스에서 빈발패턴의 추출을 위한 메모리 향상기법

박인규

doi:10.7236/jiibc.2019.19.2.127

데이터베이스에서 빈발패턴의 추출을 위한 메모리 향상기법
Memory Improvement Method for Extraction of Frequent Patterns in DataBase 원문보기

The journal of the institute of internet, broadcasting and communication : JIIBC, v.19 no.2, 2019년, pp.127 - 133

초록
AI-Helper

지금까지의 빈발 항목 추출에서는 FP-Tree에 대한 순회와 패턴의 탐색이 필수적인 과정이기 때문에 마이닝 데이터를 트리에 저장하는데 공간이 필요하고 탐색하는데 CPU시간이 필요하기 마련이다. 이러한 단점을 극복하기 위하여 본 논문에서는 조건부 FP-Tree의 의존하지 않고 트랜잭션 데이터의 각 항목들의 위치 정보를 부여하여 트랜잭션 데이터를 2차원의 위치정보 Look-Up테이블로 변환하여 시간과 공간적인 접근성을 용이하게 한다. 또한 항목과 항목의 위치에 대한 매핑배열을 병행하여 시간 복잡도를 줄이는 방법을 고려하는 알고리즘을 제안한다. 실험 결과를 통하여 제안된 방법은 FIMI 저장소 웹 사이트에서 얻은 데이터 세트를 기반으로 많은 실행 시간과 메모리 사용을 줄일 수 있음을 보였다.

Abstract ▼ AI-Helper

Since frequent item extraction so far requires searching for patterns and traversal for the FP-Tree, it is more likely to store the mining data in a tree and thus CPU time is required for its searching. In order to overcome these drawbacks, in this paper, we provide each item with its location identification of transaction data without relying on conditional FP-Tree and convert transaction data into 2-dimensional position information look-up table, resulting in the facilitation of time and spatial accessibility. We propose an algorithm that considers the mapping scheme between the location of items and items that guarantees the linear time complexity. Experimental results show that the proposed method can reduce many execution time and memory usage based on the data set obtained from the FIMI repository website.

주제어

표/그림 (24)

그림 그림 1. 헤데 테이블과 FP-Tree Fig. 1. Header table and FP-Tree
그림 그림 2.“D”로 끝나는 경로 Fig. 2. Paths ending in“C”
그림 그림 3. “C”에 대한 조건부 FP-Tree Fig. 3. Conditional FP-Tree for surffix “C”
표 표 1. 트랜잭션과 항목의 위치 Table 1. Transaction and locations of items
표 표 2. 새로운 헤더테이블 Table 2. New header table
표 표 3. 조건부패턴베이스에 의한 패턴마이닝 Table 3. Mining patterns by conditional pattern base
표 표 4. 트랜잭션의 Look-Up Array Table 4. Look-Up table of transaction
표 표 5. Look-Up Array을 위한 FP-Array Table 5. FP-Array for Look-Up Array
표 표 6.“E”로 끝나는 경로 Table 6. Paths ending in“E”
표 표 7. 헤더테이블 Table 7. header table
표 표 8.“E”의 FP-Array Table 8. FP-Array of“E”
표 표 9.“E”의 빈발패턴 Table 9. Frequent items of“E”
표 표 10.“CE”로 끝나는 경로 Table 10. Paths ending in“CE”
표 표 11. 헤더테이블 Table 11. header table
표 표 12.“DE”로 끝나는 경로 Table 12. Paths ending in“DE”
표 표 13. 헤더테이블 Table 13. header table
표 표 14.“AE”로 끝나는 경로 Table 14. Paths ending in“AE”
표 표 15. 헤더테이블 Table 15. header table
표 표 16. 데이터 집합의 특징 Table 16. The characteristics of Datasets
그림 그림 4. retail 데이터의 실행시간 Fig. 4. Execution time on dataset retail
그림 그림 5. chess 데이터의 실행시간 Fig. 5. Execution time on dataset chess
그림 그림 8. connect 데이터의 메인 메모리 사용량 Fig. 8. Main memory usages on dataset connect
그림 그림 6. T1014D100K 데이터의 실행시간 Fig. 6. Execution time on dataset T1014D100K
그림 그림 9. chess 데이터의 메인 메모리 사용량 Fig. 9. Main memory usages on dataset chess

AI 본문요약
AI-Helper

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

문제 정의

. 본 논문에서는 조건부 FP-Tree를 생성하지 않고 빈발 항목을 추출하기 위한 FP-Tree를 Look-Up Array로 변 형한 알고리즘을 제안한다. 먼저 데이터베이스를 스캔하여 모든 빈발한 항목을 찾고 두 번째 스캔은 각 트랜잭션의 빈발한 항목을 FP-Tree용 Look-Up 테이블을 생성하 고 항목과 항목의 위치정보를 FP-Array에 매핑한다.

제안 방법

기 수행된 실험에 따르면 CPU 시간의 거의 80%가 FP-Tree를 탐색하는 시간이다. FP-Tree를 탐색하는 시간과 조건부 FP-Tree를 구성하는 과정을 Look-Up 테이블을 이용하여 시간과 공간의 제약을 극복하는 방법을 제안한다.
FP-Tree의 생성과 순회와 탐색에 의존하지 않고 Look-Up과 FP-Array 배열의 접근을 통하여 메모리의 효율성을 지향하는 알고리즘을 제안하였다. 제안된 방법은 배열 기반의 새로운 데이터 구조를 사용하여 조건부 FP-Tree의 많은 후보군을 만들지 않고 빈발 항목을 추출한다.
또한 지지도에 따라서 트랜잭션의 항목을 내림차순으로 정렬한다. 각 노드는 FP-Tree에서와같이 노드 위치를 나타내기 위해 NodeID라는 특정 식별자를 표 4와 같이 부여하여 NodeID의 배열로 구성된 각각의 경로를 Look-Up Array를 구성한다. Look-Up Array에 접근하기 위하여 FP-Array을 표 5와 같이 운영한다.
먼저 데이터베이스를 스캔하여 모든 빈발한 항목을 찾고 두 번째 스캔은 각 트랜잭션의 빈발한 항목을 FP-Tree용 Look-Up 테이블을 생성하 고 항목과 항목의 위치정보를 FP-Array에 매핑한다. 따라서 조건부 FP-Tree의 많은 후보를 발생하는 대신 FP-Tree 탐색이 아닌 배열을 기반으로 조건부 FP-Tree에 해당하는 후보를 생성하는 새로운 데이터 구조를 제안한다.
FP-Tree의 생성과 순회와 탐색에 의존하지 않고 Look-Up과 FP-Array 배열의 접근을 통하여 메모리의 효율성을 지향하는 알고리즘을 제안하였다. 제안된 방법은 배열 기반의 새로운 데이터 구조를 사용하여 조건부 FP-Tree의 많은 후보군을 만들지 않고 빈발 항목을 추출한다. 실험을 FIMI 저장소 웹 사이트의 많은 합성 및 실제 데이터 세트에 적용한 결과, 반복적으로 다수의 조건부 FP-Tree를 생성하는 대신 Look-Up Array를 순회하기 위한 배열을 사용하기 때문에 배열의 접근성과 메모리의 사용량을 고려할 때 실행 시간과 메모리 사용을 줄이기 위한 대안으로 효과적임을 보였다.
제안하는 알고리즘은 FP-Growth처럼 헤더 테이블의 상향 탐색을 통하여 수행된다. 주어진 데이터 세트의 트랜잭션을 스캔하여 각 항목의 지지도를 계산하여 내림차 순으로 헤더 테이블을 작성한다.
제안하는 알고리즘은 FP-Growth처럼 헤더 테이블의 상향 탐색을 통하여 수행된다. 주어진 데이터 세트의 트랜잭션을 스캔하여 각 항목의 지지도를 계산하여 내림차 순으로 헤더 테이블을 작성한다. 또한 지지도에 따라서 트랜잭션의 항목을 내림차순으로 정렬한다.

성능/효과

min_sup이 8을 초과하면 FP-Growth 및 FP-Growth+ 와 비슷하다. CT-PRO와는 매우 양호하고 FP-Growth*은 다른 접근 방식에 비해 최고의 실행 시간을 보였다. 메모리 사용량에 대한 비교 결과는 그림 7～그림 9에 나타나 있다.
그림 4에서 제안된 방법의 계산 시간은 FP-Growth의 실행 시간보다 작다. min_sup이 4이면, FP-Growth2는 FP-Growth 방법과 비교하여 49 %의 향상을 보였다. 이 백분율은 min_sup이 20이 될 때까지 min_sup의 값이 증가할 때 점차적으로 감소한다.
또한 FP-Growth2는 FP-Tree를 생성하지 않고 Look-Up 테이블을 접근하는 방법으로 탐색하기 떄문에 기 때문에 FP-Growth+ 방법보다 빠르다. 데이터 세트 T10I4D100K의 경우에 FP-Growth2는 메모리 소비를 30%에서 80%로 줄일 수 있었다. 그림 9는 FP-Growth2가 가장 우수함을 보여준다.
제안된 방법은 배열 기반의 새로운 데이터 구조를 사용하여 조건부 FP-Tree의 많은 후보군을 만들지 않고 빈발 항목을 추출한다. 실험을 FIMI 저장소 웹 사이트의 많은 합성 및 실제 데이터 세트에 적용한 결과, 반복적으로 다수의 조건부 FP-Tree를 생성하는 대신 Look-Up Array를 순회하기 위한 배열을 사용하기 때문에 배열의 접근성과 메모리의 사용량을 고려할 때 실행 시간과 메모리 사용을 줄이기 위한 대안으로 효과적임을 보였다.

질의응답

핵심어	질문	논문에서 추출한 답변
	지금까지의 빈발 항목 추출에서 나타나는 단점은?	지금까지의 빈발 항목 추출에서는 FP-Tree에 대한 순회와 패턴의 탐색이 필수적인 과정이기 때문에 마이닝 데이터를 트리에 저장하는데 공간이 필요하고 탐색하는데 CPU시간이 필요하기 마련이다. 이러한 단점을 극복하기 위하여 본 논문에서는 조건부 FP-Tree의 의존하지 않고 트랜잭션 데이터의 각 항목들의 위치 정보를 부여하여 트랜잭션 데이터를 2차원의 위치정보 Look-Up테이블로 변환하여 시간과 공간적인 접근성을 용이하게 한다.
	Look-Up과 FP-Array 배열을 통한 알고리즘의 장점은?	또한 항목과 항목의 위치에 대한 매핑배열을 병행하여 시간 복잡도를 줄이는 방법을 고려하는 알고리즘을 제안한다. 실험 결과를 통하여 제안된 방법은 FIMI 저장소 웹 사이트에서 얻은 데이터 세트를 기반으로 많은 실행 시간과 메모리 사용을 줄일 수 있음을 보였다.
	연관 규칙 마이닝이란?	연관 규칙 마이닝 (Association Rule Mining)은 데이터 마이닝과 지식 발견의 주요한 기능으로 트랜잭션 데이터베이스의 항목들 사이의 상관관계를 나타낸다. 이러한 관계의 응용 분야는 로그인 분석, 침입 탐지를 비롯하여 많은 분야에 적용될 수 있다.

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증