초록

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

대용량의 데이터베이스에서 최소지지도를 만족하는 항목들의 집합을 빈발 항목집합이라고 한다. 이전에 연구된 대부분의 빈발 항목집합 생성 알고리즘들은 후보 항목집합들을 생성하고 이들 중에서 조건을 만족하는 빈발 항목집합들을 생성하는 과정을 수행하였다. 그러나 이러한 알고리즘들은 모든 k(k$\geq$1)-빈발 항목집합들을 생성하기까지 k를 하나씩 증가하면서 반복적으로 수행되기 때문에 많은 컴퓨팅 시간을 필요로 한다. 본 논문에서는 후보 항목집합들을 생성하지 않고 빈발 항목집합들을 생성할 수 있는 DFG 알고리즘을 제안한다. 각각의 k-빈발 항목집합들에는 데이터베이스의 모든 정보들이 포함되어 있고 하나의 빈발 항목집합은 한 트랜잭션에 존재한다. 본 논문에서는 이러한 성질을 이용하여 먼저 2-빈발 항목집합들을 생성한다. 그리고 2-빈발 항목집합들에 존재하는 한 항목과 나머지 항목들에 대한 매트릭스를 구성하여 최소지지도를 만족하는 빈발 항목집합들을 생성하게 된다. 제안하는 알고리즘은 불필요한 후보 항목집합들을 생성하지 않고 한 번의 데이터베이스 스캔만으로 빈발 항목집합들을 생성할 수 있다.

대용량의 데이터베이스에서 최소지지도를 만족하는 항목들의 집합을 빈발 항목집합이라고 한다. 이전에 연구된 대부분의 빈발 항목집합 생성 알고리즘들은 후보 항목집합들을 생성하고 이들 중에서 조건을 만족하는 빈발 항목집합들을 생성하는 과정을 수행하였다. 그러나 이러한 알고리즘들은 모든 k(k$\geq$1)-빈발 항목집합들을 생성하기까지 k를 하나씩 증가하면서 반복적으로 수행되기 때문에 많은 컴퓨팅 시간을 필요로 한다. 본 논문에서는 후보 항목집합들을 생성하지 않고 빈발 항목집합들을 생성할 수 있는 DFG 알고리즘을 제안한다. 각각의 k-빈발 항목집합들에는 데이터베이스의 모든 정보들이 포함되어 있고 하나의 빈발 항목집합은 한 트랜잭션에 존재한다. 본 논문에서는 이러한 성질을 이용하여 먼저 2-빈발 항목집합들을 생성한다. 그리고 2-빈발 항목집합들에 존재하는 한 항목과 나머지 항목들에 대한 매트릭스를 구성하여 최소지지도를 만족하는 빈발 항목집합들을 생성하게 된다. 제안하는 알고리즘은 불필요한 후보 항목집합들을 생성하지 않고 한 번의 데이터베이스 스캔만으로 빈발 항목집합들을 생성할 수 있다.

AI 본문요약

엑셀 다운로드 AI-Helper

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

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

문제 정의

• 본 논문에서는 1-빈발 항목집합으로부터 최종 k-빈발 항목집합들을 생성하기까지 기존의 순차적인 항법을 따르지 않고 빈발 항목집합들을 생성할 수 있는 DFG(Di「ect Frequent itemsets Generation) 알고리즘을 제안한다. 빈발 항목집합들은 다믐과 같은 특성을 가진다[2].
• 본 논문에서는 방대한 데이터베이스에 있는 항목들 중에서 빈발 항목집합을 효율적으로 생성하기 위한 DFG 알고리즘을 제안하였다. 임의의 k-빈발 항목집합들은 모든 빈발 항목집합들에 대한 정보들을 저장하고 있다는 성질을 이용하여 한 번의 데이터베이스 스캔으로 해쉬 테이블을 생성하고 압축된 정보인 2-빈발 항목집합들을 생성한다.

가설 설정

• 예를 들면, {B, C, E}는 TID 200과 300인 트 랜잭션에 존재한다. 두 개의 트랜잭션에서 {B, C, E}로 생 성할 수 있는 2-부분집합의 버켓에는 카운트가 2로 누적되고 단지 TID 300의 A 항목과 나머지 {B, C, E}에 대한 버켓만 생성될 것이다.

제안 방법

• 앞 에서 설명한 것처럼 각 k-빈발 항목집합들은 데이터베이스 에서 생성할 수 있는 모든 빈말 항목집합들에 대한 정보들 을 가지고 았다. 그러므로 본 논문에서는 메모리 오버헤드 가 상대적으로 적은 2-빈발 항목집합을 생성한다.
• 본 논문에서는 이러한 성질을 이용하여 먼저 2- 빈발 항목집합들을 생성한다. 그리고 2-빈발 항목집합들의 부분집합인 각 항목들에 대해 매트릭스를 형성하여 최소지 지도를 만족하는 빈발 항목집합들을 생성한다.
• 본 논문에서는 이러한 성질을 이용하여 2-빈발 항목집합들을 생성한다. 그리고 2-빈발 항목집합들을 이루고 있는 각 빈발 항목들에 대해서 한 항목과 나머지 항목들에 대한 매트릭스를 생성하고 그 매트릭스에서 빈발 항목집합들을 생성하게 된다.
• 예에서 볼 수 있듯이 1, 2 그리고 3-빈 할 항목집합들은 모두 중복된 정보들을 가지고 있음을 알 수 있다. 본 논문에서는 이러한 성질을 이용하여 먼저 2- 빈발 항목집합들을 생성한다. 그리고 2-빈발 항목집합들의 부분집합인 각 항목들에 대해 매트릭스를 형성하여 최소지 지도를 만족하는 빈발 항목집합들을 생성한다.

이론/모형

• 지금까지 빈발항목집합을 찾기 위한 다양한 연관 규칙 탐사 알고리즘들이 제시되 었다[1, 2, 3, 4, 5, 6]. [1]에서 제안된 Apriori 와 [2]에서 제얀된 DHP 알고리즘 같은 기존에 제안된 애부분의 알 고리즘들은 휴리스틱(heuristic) 방법을 사용했다. 즉, k- 후보 항목집합이 존재한다고 할 때, k(k之1)-후보 항독집 합이 최소지지도를 만족하면 k-빈발 항목집합이 된다, 그리고 더 이상의 후보 항목집합들이 생성되지 않을 때까지 이 과정은 반복 수행된다.
• 별도의 비 교연산이나 후보 항목집합들을 생성하지 않기 때문에 적은 컴퓨팅 비용으로 2-빈발 항목집합들을 생성할 수 있다. 모든 빈발 항목집합들을 해쉬 기법을 사용하여 생성한다. 면 알고리즘 수행 시간은 기존의 알고리즘보다 훨씬 적은 시간에 생성할 수 있을 것이다.

성능/효과

• 다시 말하면 빈발 항목집합은 하나의 트랜잭션에 반드시 존재한다는 것이다. 세 번째 특성은 잉의의 k-빈발 항독잡합 들이 있을 패, 데이터베이스에서 생성하고자하는 모든 빈발 항목집합들의 정보가 k-빈발 항목집합들에 포함되어 있다는 것이다. 위의 세 가지 성질은 다음의 예에서 찾아볼 수 았다.
• 첫 번째 특성은 빈발 항목집합들의 부분집합들 또한 최소 지지도률 만족한다는 것이고, 두 번째 특성은 임의의한 빈발 항목집합은 한 트랜잭션의 부분집합이라는 것이다. 다시 말하면 빈발 항목집합은 하나의 트랜잭션에 반드시 존재한다는 것이다.

후속연구

• 이는 2-빈발 항목집합들만을 사용하므로 생성하꼬자 원하는 빈발 항목집합들에 대한 모든 정보들을 추출할 수 있지만 여기에 의미 없는 항목들이 포함될 수 있다. 향후에는 이러한 이미 없는 항목 들을 전지할 수 있는 방법에 대한 연구가 진행되어야 하겠다.

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

이 논문을 인용한 문헌

더보기