KR100382296B1 - 온라인 데이터베이스 마이닝 - Google Patents

Abstract

사전처리 스테이지에 이은 온라인 규칙 발생 스테이지의 두 스테이지를 가지는 양적 관련 규칙의 온라인 마이닝에 관한 컴퓨터 방법이 제공된다. 전제부 속성들간의 관계를 조직화하여 계층적으로 배치된 다차원 인덱싱 구조를 생성하기 위하여 데이터를 사전처리하므로써 정의되는 사전처리 스테이지에 의해 계산상 필요한 노력이 감소된다. 결과적인 구조는 양적 관련 규칙의 발생과 관련된 제2 스테이지인 온라인 처리의 수행을 용이하게 한다. 제2 스테이지인인 온라인 규칙 발생에서는 먼저 규칙에 대응하는 데이터에서 영역을 알아내므로써 사전처리 스테이지에 의해 생성된 다차원 인덱스 구조를 사용하고, 그후, 규칙 셋의 계층적 표현을 주기 위해 관심있는 영역들을 신중하게 결합하기 위한 병합 트리를 생성하는 병합 단계를 사용한다. 그후, 병합 트리를 사용하여 실제로 규칙을 발생한다.

Description

온라인 데이터베이스 마이닝{ONLINE DATABASE MINING}

데이터베이스에서 지식 발견이라고도 알려진 데이터 마이닝은 데이터베이스 연구에 대한 새로운 영역으로 알려져 왔다. 전자 포맷으로 저장된 데이터의 양은 지난 20년에 걸쳐 극적으로 증가해왔다. 판매시점 장치 또는 원격 감지 장치와 같은 전자 데이터 수집 장치의 사용의 증가로 인하여 사용가능한 데이터가 폭발적으로 많아졌다. 데이터 저장이 보다 쉬워지고 상당량의 처리능력이 사용가능하게 됨에 따라 사업 분야에 보다 큰 매력을 지니게 되었으며, 더욱 더 감소된 비용으로 데이터 저장 자원을 사용할 수 있게 되었다.

데이터 축적에 보다 큰 관심이 집중됨에 따라, 상보적으로 이 가치있는 자원을 어떻게 활용할 것인가에 대한 관심도 일어났다. 사업 분야에서는 저장된 데이터를 사용할 수 있는 판정자가 유용한 통찰력을 가질 수 있는 것으로 인식되어 왔다. 바 코드 회사로부터의 데이터 또는 카탈로그 회사로부터의 판매 데이터를 사용하므로써, 고객의 구매 행동에 대한 유용한 정보를 얻을 수 있다. 다른 것들중에서 예를 들면, 소매상인은 이렇게 얻은 정보를 사용하여 수퍼마켓의 선반에 놓을 물품들을 결정하거나 혹은 훌륭하게 목표된 마켓팅 프로그램을 설계할 수 있다. 적절한 분석 기법을 사용하여 데이터로부터 다수의 의미있는 통찰력을 발견해낼 수 있다. 가장 일반적인 관점에서, 데이터 마이닝은 데이터 집합에서 패턴 및 규칙성을 발견하기 위해 소프트웨어 기법의 사용 및 데이터 분석과 관련있다. 데이터 마이닝의 목적은 데이터에서 인식할 수 있는 패턴 및 경향을 분류해 내고, 이들 패턴으로부터 관련 규칙을 추론해내는 데 있다.

데이터 마이닝 기술은 상당량의 데이터상의 집중적인 계산에 의해 특징지워진다. 큰 데이터베이스는 100만 레코드이상으로 구성된 것으로 정의될 수 있다. 전형적인 응용에서, 단말 사용자는 "콜라를 구입하는 고객의 75%가 또한 콘칩을 산다" (여기서 75%는 규칙의 신뢰율(confidence factor)을 지칭)와 같은 관련 규칙을 테스트할 것이다. 이 규칙의 서포트(support)는 콜라와 콘칩의 모두를 포함하는 트랙잭션의 퍼센트이다.

종래기술에서는 온라인 마이닝 문제를 다루지 않았고, 대신에 아이템셋 접근방안(an itemset approach)에 관심이 있었다. 이 아이템셋 접근방안의 심각한 단점은 사용자가 상이한 값의 서포트 및 신뢰성에서 관련 규칙에 대한 데이터베이스를 테스트하므로, 기가바이트 차수일 수 있는 데이터베이스상에서 다수의 패스(pass)를 행해야 한다는 데 있다. 상당히 큰 데이터베이스에서, 이것은 소정 환경에서 상당량의 I/O과 관련될 수 있고, 온라인 질의에 대해 수용할 수 없는 응답 횟수를 이끌어 낼 수 있다. 사용자는 얼마나 많은 규칙이 소정 레벨의 서포트 및 신뢰성을 만족시켜야 하는 지를 선험적으로 추측하기가 어려우므로 데이터베이스상에 다수의질의를 행해야 한다. 전형적으로 사용자는 단지 몇몇 규칙에만 관심있을 수도 있다. 사용자는 규칙을 마이닝하기 위하여 최소 서포트 및 최소 신뢰성의 적절한 레벨을 알아내기 위해 다수번 질의를 실행할 필요가 있을 수 있으므로 이것은 모든 문제를 보다 어렵게 만든다. 환언하면, 마이닝 관련 규칙의 문제는 트랜잭션 데이터베이스로부터 유용한 사업 정보를 수집할 수 있을 때까지 반복된 질의로써 상당한 수동 매개변수 조정을 필요로 할 수 있다는 것이다. 따라서, 전술한 마이닝의 처리 방법은 수용할 수 없는 응답 시간을 이끄는 대규모 디스크 I/O 또는 계산의 결과로 인해 반복되는 온라인 질의에 적합하지 않다. 데이터 마이닝의 능력을 인터넷으로 확장하기 위해서는 아이템셋 접근방안의 배치 지향 방법보다는 오히려 동적 온라인 방법을 필요로 한다.

발명이 이루고자 하는 기술적 과제

따라서, 본 발명은 양적 관련 규칙(quantitative association rules)을 제공하기 위한 다수의 양적 및 분류별 아이템(quantitative and categorical items)을 제각기 가진 다수의 레코드를 가지는 큰 데이터베이스를 온라인 마이닝(online mining)하는 방법을 제공하는 데, 본 발명의 방법은,가) 최소 신뢰성(minimun confidence)의 사용자 정의 값, 최소 서포트(minimun support)의 사용자 정의값, 그리고, 상기 양적 및/또는 분류별 아이템에 의해 표현되는 전제부(antecedent) 및 결론부(consequent) 속성을 포함한 사용자 질의를 수신하는 단계와,나) 전제부 데이터를 다수의 인덱스 노드를 포함하는 인덱스 트리로 계층적으로 사전저장하므로써 상기 전제부 및 결론부 속성간의 관계를 조직화하는 단계로서, 각 인덱스 노드는 각 사용자 질의 결론부 속성에 대한 실제 서포트 및 신뢰성을 나타내는 제1 및 제2 값을 가지는 상기 조직화 단계와,다) 상기 사용자 질의 전제부 속성 범위에 대응하는 전제부 속성을 가지며, 상기 최소 신뢰성의 사용자 정의 값과 적어도 동일한 신뢰성 및, 상기 최소 서포트의 사용자 정의 값과 적어도 동일한 서포트값을 가지는 노드들을 분리시키기 위하여, 상기 인덱스 트리의 모든 인덱스 노드를 검색하므로써 상기 사용자 질의에 응답하여 상기 사전저장된 데이터로부터 응답을 도출해 내는 단계를 포함하는 데이터베이스의 온라인 마이닝 방법에 관한 것이다.

바람직한 실시예에서, 상기 응답은 하나 또는 그이상의 양적 관련 규칙, 각 규칙과 관련된 실제 신뢰성값, 각 규칙과 관련된 실제 서포트값 및, 각 규칙과 관련된 관심 레벨을 포함하고, 상기 하나 또는 그이상의 양적 관련 규칙은 관심있는 규칙만으로 구성된다(예를 들면, 그들의 계산된 관심 레벨은 상기 사용자 정의 관심 레벨과 적어도 동일하다).

편리하고 효과적인 관심 레벨의 정의는 제1 및 제2 계산 비율이 최소로서 정의되는 것이고, 상기 제1 비율은 상기 실제 신뢰성을 기대되는 신뢰성으로써 제산하여 정의되고, 제2 비율은 상기 실제 서포트를 기대되는 서포트로써 제산하여 정의되고, 상기 기대되는 신뢰성 및 서포트는 통계상 독립적이라는 추정을 근거로 계산된다.

바람직한 실시예에서, 상기 전제부 속성은 분류별 및 양적 속성으로 구성되고, 상기 양적 속성은 하부 및 상부 경계로 구성된 범위에 의해 정의된다.

바람직하게, 상기 조직화 단계는 상기 전제부 데이터를 인덱스 트리로 계층적으로 분할하는 단계를 포함하고, 상기 인덱스 트리는 다수의 인덱스 노드를 포함하며, 전제부 데이터를 인덱스 트리로 계층적으로 분할하는 상기 단계는,

가) 상기 인덱스 트리의 각 인덱스 노드에 상기 실제 서포트를 나타내는 제1값을 저장하는 단계와,

나) 상기 인덱스 트리의 각 인덱스 노드에 각 사용자 질의 결론부 속성에 대한 발생 빈도를 나타내는 제2 값을 저장하는 단계를 포함한다.

이러한 실시예에서, 상기 도출단계는,

가) 상기 사용자 질의 전제부 속성 범위에 대응하는 전제부 속성 범위를 가진 노드들을 분리시키기 위하여 상기 인덱스 트리의 모든 인덱스 노드를 검색하고,

나) 단계 가)에서 위치된 노드로부터, 상기 최소 신뢰성의 사용자 정의 값과 적어도 동일한 결론부 속성을 가진 노드를 선택하고,

다) 단계 나)에 위치된 노드로부터, 상기 병합 트리를 건설하므로써 효과적으로 구현될 수 있다.

바람직하게, 상기 건설 단계는 의미없는 노드들을 삭제하고, 다른 노드들을 결합하여 상기 병합 트리를 생성하는 단계를 더 포함하고, 상기 의미없는 노드는 상기 최소 신뢰성의 사용자 정의 값과 적어도 동일한 대응하는 계산값의 신뢰성을 가지지 않는 노드이다. 상기 병합 트리는 단일 결론부 속성 또는 다수의 결론부 속성에 대해 건설될 수 있다.

일 바람직한 실시예에서, 상기 수신 단계는,

상기 최소 서포트의 사용자 정의 값, 상기 최소 신뢰성의 사용자 정의 값, 상기 사용자 정의값의 관심, 그리고, 전제부 및 결론부 조건을 포함한 사용자 질의를 포함한 데이터를 컴퓨터에 입력하는 단계를 포함하고, 상기 전제부 및 결론부 조건은 다수의 양적 및 분류별 속성을 더 포함하고,

상기 조직화 단계 및 사전저장 단계는,

하나 또는 그 이상의 차원으로 구성된 인덱스 트리를 메모리에 구성하는 단계와, 상기 인덱스 트리로부터 미병합 규칙 트리를 메모리에 구성하고 상기 미병합 규칙 트리로부터 병합 규칙 트리를 구성하는 단계를 포함하고, 각 차원은 상기 전제부 조건에 포함된 사용자 제공 양적 속성들중의 하나에 의해 정의되고, 상기 인덱스 트리는 다수의 인덱스 노드로 구성되고, 상기 인덱스 노드는 다수의 데이터 레코드로 구성되고,

상기 도출 단계는,

상기 사용자 질의를 만족시키며 상기 최소 서포트와 적어도 동일한 서포트 및, 상기 최소 신뢰성과 적어도 동일한 신뢰성을 가지는 인덱스 노드로부터 하나 또는 그이상의 양적 관련 규칙을 발생하는 단계와,

상기 발생 단계로부터의 상기 양적 관련 규칙, 각 발생된 양적 관련 규칙과 관련된 실제 신뢰성값, 각 발생된 양적 관련 규칙과 관련된 서포트값, 각 발생된 양적 관련 규칙과 관련된 관심 레벨의 값으로 구성되는 사용자 출력 데이터를 디스플레이하는 단계를 포함한다.

바람직하게, 인덱스 트리를 구성하는 상기 단계는,

하나 또는 그이상의 차원의 이진 인덱스 트리를 구성하는 단계로서, 각 차원은 상기 사용자 제공 양적 전제부 속성들중의 하나에 의해 정의되는 상기 단계와, 각 인덱스 노드에 상기 서포트 레벨 및 신뢰성 레벨을 저장하는 단계를 포함한다.

또한, 미병합 규칙 트리를 구성하는 상기 단계는,

상기 인덱스 트리의 각 노드를 검색하는 단계와,

상기 사용자 명시 결론부 조건을 만족시키는 규칙을 포함하고, 상기 최소 신뢰성의 사용자 정의 값과 적어도 동일한 신뢰성 및, 상기 최소 서포트의 사용자 정의 값과 적어도 동일한 서포트값을 가지는 노드를 선택하는 단계를 포함하는 것이 바람직하다. 후자인 선택 단계는,

포인터를 구성하는 단계와,

상기 포인터를 상기 인덱스 트리에서의 루트 노드로 동등시하는 단계와,

상기 포인터와 관련된 각 노드를 리스트에 추가시키는 단계와,

상기 사용자 명시 전제부 속성의 매개변수내에 전부 포함된 전제부 속성, 상기 사용자 정의한 최소 서포트와 적어도 동일한 최소 서포트값을 가진, 상기 포인터에 의해 지시되는 상기 노드의 모든 자식들을 상기 리스트에 추가시키는 단계와,

상기 포인터에 의해 지시되는 상기 노드에 저장된 상기 데이터 레코드가 상기 사용자 명시 결론부 조건과 적어도 동일한 가와, 상기 사용자 정의 최소 신뢰성과 적어도 동일한 신뢰성을 가지는 가를 결정하는 단계와,

상기 결론부 조건과 관련된 양적 관련 규칙을 발생하는 단계와,

이전 단계의 조건이 만족되지 않을 때, 상기 리스트로부터 상기 노드를 삭제하는 단계와,

상기 리스트가 비었는 지를 판정하는 단계와,

상기 리스트가 빈 경우에는 종료하고, 상기 리스트가 비지 않은 경우에는 상기 인덱스 트리의 다음 노드로 상기 포인터를 동등시하고, 상기 포인터와 관련된 노드를 상기 리스트에 추가시키는 상기 단계로부터 위의 단계를 반복하는 단계를 포함한다.

병합 규칙 트리를 건설하는 상기 단계는,

가) 후위로 상기 병합 규칙 트리의 각 노드를 순회하는 단계와,

나)

1) 상기 각 사용자 정의 결론부 속성값이 상기 노드에 저장된 상기 결론부 속성값 보다 큰지의 여부를 결정하고,

2) 상기 1)의 조건이 만족될 때, 상기 병합 규칙 트리에 상기 노드를 보존하고,

3) 상기 1)의 조건이 만족되지 않고 상기 노드가 관련된 자노드(child nodes)를 가지지 않을 때, 상기 병합 규칙 트리로부터 상기 노드를 삭제하고,

4) 상기 1)의 조건이 만족되지 않고 상기 노드가 하나의 자노드를 가질 때, 상기 삭제된 노드의 조상 노드와 자노드를 직접 관련시키고,

5) 상기 1)의 조건이 만족되지 않을 때, 상기 결론부 속성의 범위를 조정하므로써

상기 미병합 규칙 트리에서 포함 또는 배제에 대하여 각 순회 노드를 평가하는 단계를 포함하고, 상기 평가 단계는 후위로 모든 노드가 순회될 때 까지 반복되는 것이 바람직하다.본 발명은 또한, 양적 관련 규칙을 제공하기 위한 다수의 양적 및 분류별 아이템을 제각기 가진 다수의 레코드를 가지는 큰 데이터베이스를 온라인 마이닝하는 장치에 있어서,최소 신뢰성의 사용자 정의 값, 최소 서포트의 사용자 정의 값, 그리고, 상기 양적 및/또는 분류별 아이템에 의해 표현되는 전제부 및 결론부 속성을 포함한 사용자 질의를 수신하는 수신하기 위한 수단과,전제부 데이터를 다수의 인덱스 노드를 포함하는 인덱스 트리로 계층적으로 사전저장하므로써 상기 전제부 및 결론부 속성간의 관계를 조직화하기 위한 수단으로서, 각 인덱스 노드는 각 사용자 질의 결론부 속성에 대한 실제 서포트 및 신뢰성을 나타내는 제1 및 제2 값을 가지는 상기 수단과,상기 사용자 질의 전제부 속성 범위에 대응하는 전제부 속성을 가지며, 상기 최소 신뢰성의 사용자 정의 값과 적어도 동일한 신뢰성과 상기 최소 서포트의 사용자 정의 값과 적어도 동일한 서포트값을 가지는 노드들을 분리시키기 위하여, 상기 인덱스 트리의 모든 인덱스 노드를 검색하므로써 상기 사용자 질의에 응답하여 상기 사전저장된 데이터로부터 응답을 도출해 내기 위한 수단을 포함한다.

또다른 양상으로부터 알 수 있는 바와 같이, 본 발명은 또한 양적 관련 규칙을 제공하기 위한 다수의 양적 및 분류별 아이템을 제각기 가진 다수의 레코드를 가지는 큰 데이터베이스의 온라인 마이닝의 컴퓨터 수행 처리를 제공하는 데, 이는,

최소 서포트의 사용자 정의 값, 최소 신뢰성의 사용자 정의 값, 사용자 정의 값의 관심, 그리고, 전제부 및 결론부 조건을 포함한 사용자 질의를 포함한 데이터를 컴퓨터에 입력하는 단계로서, 상기 전제부 및 결론부 조건은 다수의 양적 및 분류별 속성을 더 포함하는 상기 단계와,

하나 또는 그이상의 차원으로 구성된 인덱스 트리를 메모리에 구성하는 단계로서, 각 차원은 상기 전제부 조건에 포함된 상기 사용자 제공 양적 속성중의 하나에 의해 정의되고, 상기 인덱스 트리는 다수의 인덱스 노드로 구성되고, 상기 인덱스 노드는 다수의 데이터 레코드로 이루어지는 상기 단계와,

다수의 데이터 레코드로 이루어진 상기 다수의 인덱스 노드로 구성되는 상기 인덱스 트리로부터 미병합 규칙 트리를 메모리에 구성하는 단계와,

다수의 레코드로 이루어진 상기 다수의 인덱스 노드로 구성되는 상기 미병합 트리로부터 병합 트리를 메모리에서 구성하는 단계와,

상기 사용자 질의를 만족시키고, 상기 최소 서포트와 적어도 동일한 서포트 및, 상기 최소 신뢰성과 적어도 동일한 신뢰성을 가진, 인덱스 노드로부터 하나 또는 그이상의 양적 관련 규칙을 발생하는 단계와,

상기 발생 단계로부터의 상기 양적 관련 규칙, 각 발생된 양적 관련 규칙과 관련된 실제 신뢰성값, 각 발생된 양적 관련 규칙과 관련된 서포트값, 각 발생된 양적 관련 규칙과 관련된 관심 레벨값으로 구성되는 사용자 출력 데이터를 디스플레이하는 단계를 포함한다.

바람직하게, 미병합 규칙 트리를 구성하는 단계는 상기 인덱스 트리의 각 노드를 검색하는 단계와, 적절한 노드를 선택하는 단계를 포함하고, 상기 노드를 선택하는 단계는,

1) 포인터를 구성하는 단계와,

2) 상기 포인터를 상기 인덱스 트리에서의 루트 노드로 동등시하는 단계와,

3) 상기 포인터와 관련된 각 노드를 리스트에 추가시키는 단계와,

4) 상기 사용자 명시 전제부 속성의 매개변수내에 전부 포함된 전제부 속성, 상기 사용자 정의한 최소 서포트와 적어도 동일한 최소 서포트값을 가진, 상기 포인터에 의해 지시되는 상기 노드의 모든 자식들을 상기 리스트에 추가시키는 단계와,

5) 상기 포인터에 의해 지시되는 상기 노드에 저장된 상기 데이터 레코드가 상기 사용자 명시 결론부 조건과 적어도 동일한 가와, 상기 사용자 정의 최소 신뢰성과 적어도 동일한 신뢰성을 가지는 가를 결정하는 단계와,

6)상기 결론부 조건과 관련된 양적 관련 규칙을 발생하는 단계와,

7) 이전 단계의 조건이 만족되지 않을 때, 상기 리스트로부터 상기 노드를 삭제하는 단계와,

8) 상기 리스트가 비었는 지를 판정하는 단계와,

9) 상기 리스트가 빈 경우에는 종료하는 단계와,

10) 단계 9)의 조건이 만족되지 않을 때, 상기 인덱스 트리의 다음 노드로 상기 포인터를 동등시하는 단계와,

11) 단계 9)의 조건이 만족되지 않을 때 단계 3) 내지 단계 9)를 반복하는 단계를 포함한다.

바람직하게, 병합 규칙 트리를 건설하는 상기 단계는,

가) 후위로 상기 병합 규칙 트리의 각 노드를 순회하는 단계와,

나)

1) 상기 각 사용자 정의 결론부 속성값이 상기 노드에 저장된 상기 결론부 속성값 보다 큰지의 여부를 결정하고,

2) 상기 1)의 조건이 만족될 때, 상기 병합 규칙 트리에 상기 노드를 보존하고,

3) 상기 1)의 조건이 만족되지 않고 상기 노드가 관련된 자노드를 가지지 않을 때, 상기 병합 규칙 트리로부터 상기 노드를 삭제하고,

4) 상기 1)의 조건이 만족되지 않고 상기 노드가 하나의 자노드를 가질 때, 상기 삭제된 노드의 조상 노드와 자노드를 직접 관련시키고,

5) 상기 1)의 조건이 만족되지 않을 때, 상기 결론부 속성의 범위를 조정하고,

6) 상기 4)의 조건이 만족될 때 상기 삭제된 노드의 조상 노드와 자노드를 직접 관련시키는 단계와,

7) 후위로 모든 노드를 순회할 때 까지, 단계 1) 내지 6)을 반복하므로써

상기 미병합 규칙 트리에서 포함 또는 배제에 대하여 각 순회 노드를 평가하는 단계를 포함한다.

본 명세서에 기술된 계산상 효율적 접근방안은 데이터베이스상의 온라인 질의가 양적 관련 규칙의 온라인 마이닝의 효율적인 수행으로 인하여, 예언자로서 서포트 및 신뢰성의 사용자 제공 레벨을 활용하여 관련 규칙의 세기를 평가할 수 있게 하고, 새로운 양적 관련 규칙을 발견할 수 있게 한다. 관련 규칙은 그의 두 구성요소 부분은 전제부 및 결론부 부분들간에 소정의 상호관계가 존재한다고 제안하는 조건 문장으로서 일반적으로 정의될 수 있다. 양적 관련 규칙에 있어서, 전제부 및 결론부 양적 관련 규칙은 양적 및 분류별 속성의 소정의 사용자 명시된 결합으로부터 구성된다. 제안된 규칙에 따라, 사용자는 사용자에 대한 관심의 신뢰성 및 서포트 레벨, 관심 레벨로서 언급된 값을 나타내는 세 부가적인 입력을 제공한다. 이들 입력은 사용자에 의해 제안된 규칙의 세기를 표시하고(사용자 질의), 환언하면, 사용자 질의에 의해 정의된 전제부 및 결론부간의 제안된 상호관계의 세기를 표시한다.

이러한 접근방안을 수행하기 위하여, 온라인 규칙 발생 단계에 이어서 다차원 인덱싱 구조를 생성하기 위하여 데이터를 분할하는 데 전제부 속성을 활용하므로써 원래 데이터를 사전처리하기 위한 방법이 기술된다. 효과적으로 데이터를 인덱스 구조로 사전처리하므로서, 거의 순시적인 응답 시간을 가진 반복된 온라인 질의를 응답하기에 적합한 형태로 배치된다. 일단 생성되면, 인덱싱 구조에서는 데이터베이스상에서 다수번 패스를 할 필요가 없다. 인덱싱 구조는 이전 기법에 비해 상당한 성능 이점을 생성한다. 온라인 처리를 출력 크기에 비례하는 복잡도를 가진 그래프 이론상 검색 알고리즘을 적용하므로써 행할 수 있는 방식으로 인덱싱 구조(사전처리된 데이터)를 저장한다. 이것은 응답 시간이라는 점에서 거의 순시적이고, 과도한 양의 I/O 또는 계산을 최소화시키는 온라인 알고리즘의 결과이다.

본 발명은 큰 데이타베이스에서 데이터 종속성에 대한 온라인 검색에 관한 것이다(데이터 마이닝).

도 1은 컴퓨터 네트워크를 전반적으로 도시하는 도면이다.

도 2는 도 2a 및 도 2b에 도시된 두 스테이지로 구성되는 데이터 마이닝 방법을 전반적으로 도시하는 도면으로, 도 2a는 사전처리 스테이지를 도시하고, 도 2b는 알고리즘의 온라인 스테이지를 도시한다.

도 3은 인덱스 트리가 전제부 셋을 사용하여 어떻게 구성되는 지를 상세히 기술하는 도면이다. 도 2(a)의 단계(75)의 확장일 수 있다.

도 4는 미병합 규칙 트리가 인덱스 트리로부터 어떻게 발생되는 지를 상세히 도시하는 도면이다. 도 2(b)의 단계(100)의 확장일 수 있다.

도 5는 병합 규칙 트리가 미병합 규칙 트리로부터 어떻게 건설되는 지를 도시하는 도면이다.

도 6은 소정의 사용자 명시 관심 레벨 r에서 병합 규칙 트리로부터 양적 관계 규칙이 어떻게 발생되는 지를 도시하는 도면이다.

이제, 본 발명에 따르는 양적 관련 규칙의 온라인 데이터 마이닝 방법을 첨부된 도면을 참조하여 단지 예로써 상세히 기술할 것이다.

통상적인 데이터베이스 질의는 "롱 섬 영역에 대하여 1995년 1월에 오렌지 쥬스의 판매는 어떠했는 가?"와 같은 단순한 질문을 포함한다. 이와 대조적으로, 데이터 마이닝은 데이터에서 인식가능한 패턴 및 경향을 뽑아내려고 시도하고, 이들 패턴으로부터 규칙을 추론한다. 이들 규칙으로써, 사용자는 소정 관련된 사업 또는 과학 영역에서 판정을 지지, 검토 및 검사할 수 있다. 예를 들면, 아이템의 큰 콜렉션을 가진 수퍼마켓을 고려하자. 동작과 관련된 전형적인 사업 판정은 무엇을 판매할 것인가, 어떻게 쿠폰을 디자인 할것인가 및, 이득을 최대화하기 위해 상품을 선반에 어떻게 배치할 것인가 등과 관계있다. 지난 트랜잭션 데이터를 분석하는 것은 이러한 판정의 질을 향상시키기 위하여 일반적으로 사용되는 접근방안이다. 현대 기술로 전-트랜잭션 원리로 구입한 아이템을 저장하는 소위 바스켓 데이터(basket data)를 저장할 수 있게 되었다. 조직화는 상당량의 이러한 데이터를 수집한다. 소정의 최소 명시된 신뢰성을 가진 아이템 셋들간의 관련 규칙에 대하여 바스켓 데이터형 트랜잭션의 큰 콜렉션을 "마이닝"하는 것 중의 하나가 문제가 된다. 각각이 아이템 셋인 트랜잭션 셋이 주어지면, 관련 규칙은 형식 X => Y 로 표현되고, 여기서 X 및 Y는 아이템 셋이다. 관련 규칙의 예는 "맥주를 포함하는 트랜잭션의 30%가 또한 냅킨을 포함하고, 모든 트랜잭션이 2%가 이들 아이템을 모두 포함한다"이다. 여기서 30%는 규칙의 신뢰성으로 불려지며, 2%는 규칙의 서포트이다.

이러한 관련 규칙의 또다른 예는 빵 및 버터를 구매하는 고객 트랜잭션의 90%가 또한 우유를 구입한다는 문장이다. 이 규칙의 전제부 X는 빵 및 버터로 구성되고, 결론부 Y는 우유만으로 구성된다. 90%는 규칙의 신뢰율이다. 예를 들면, 상점이 배겔(bagels) 판매를 중지하는 경우에 가장 큰 영향을 받는 제품을 결정하는 데 도울 수 있는 전제부에서 "배겔"을 가지는 모든 규칙을 발견하는 것이 바람직할 수 있다.

원래 트랜잭션 셋 D가 주어지면, 마이닝 관련 규칙의 문제는 사용자 명시 최소 서포트(minsupport, s) 및 최소 신뢰성(minconfidence, c)보다 큰 서포트 및 신뢰성을 가지는 모든 규칙을 발견하는 데 있다. 통상적으로, 규칙 X => Y의 서포트는 고객 트랜잭션의 퍼센트 또는 X 및 Y 아이템셋의 모두를 포함하는 일반화된 데이터베이스에서 튜플이다. 보다 형식적인 수학 용어에서, 규칙 X => Y는 Y를 포함한 X를 포함하는 트랜잭션의 퍼센트로서 정의된다. 혹은 보다 형식적으로, 규칙 X => Y는 X를 포함한 D에서 트랜잭션의 c%가 또한 Y를 포함하는 경우에 트랜잭션 셋 D에서 신뢰성 c를 가진다. 따라서, 규칙이 90% 신뢰성을 가지는 경우에, X를 포함한 트랜잭션의 90%가 또한 Y를 포함한다는 것을 의미한다.

전술한 바와 같이, 관련 규칙은 형식 X => Y의 표현이다. 아이템셋 X 및 Y 가

X = [우유 치즈 버터]

Y = [달걀 햄]

으로 각각 정의되는 경우,

규칙은 다음과 같이 번역될 수 있다:

규칙: X => Y, 트랜잭션에서 우유, 치즈 및 버터의 발생이 주어지면, 소정의정의된 서포트 및 신뢰성 레벨내에 동일한 트랜잭션에서 달걀 및 햄이 나타날 가능성은 얼마인가.

규칙의 서포트 및 신뢰성은 집합적으로 규칙의 세기를 정의한다. 사용자가 그의 세기를 테스트하기 위해 이러한 시스템에 규칙을 부여할 수 있는 다수의 방식이 있다. 그러나, 이러한 시스템이 지원할 수 있는 온라인 질의의 종류의 대표적인 비포함 리스트는 다음을 포함한다.

(1) 소정 레벨의 최소서포트 및 최소신뢰성 위의 모든 관련 규칙을 발견.

(2) 소정 레벨의 최소서포트 및 최소신뢰성에서, 전제부에서 아이템셋 X를 가지는 모든 관련 규칙을 발견.

(3) 소정 레벨의 최소서포트 및 최소신뢰성에서, 전제부에서 아이템셋 Y를 가지는 모든 관련 규칙을 발견.

(4) 소정 레벨의 최소서포트 및 최소신뢰성에서, 전제부 및 결론부 사이에서 전제부 또는 결론부 또는 분산된 아이템셋 Y를 가지는 모든 관련 규칙을 발견.

(5) 위의 경우(1), (2), (3), (4)중의 어느 한 경우에서 관련 규칙/아이템셋의 수를 발견.

(6) 최소서포트 레벨에서, 아이템셋 Z를 포함하는 정확히 k 아이템셋이 존재하게 하기.

본 방법은 각종 양적 및 분류별 속성에 의해 정의되는 원래 트랜잭션셋 D로 구성되는 큰 데이터베이스로부터 양적 규칙을 발견하기 위해 일반적 관련 규칙을 발견하는 방법을 특수화한다.

예를 들면, 일반적 마켓팅 조사에 대한 전형적인 양적/분류별 데이터베이스는 고객 특성 및 선호도의 소정 조합을 각각이 반영하는 일련의 레코드로 구성된다;

Record (1) = age=21, sex=male, homeower=no

Record (2) = age=43, sex=male, homeowner=yes

Record (3) = age=55, sex=female, homeowner=no

일반적으로, 양적 관련 규칙은 다음 형식의 조건이다;

일반적 규칙:

x1[l1..u1],x2[l2..u2]..xk[lk..uk] Y1=c1, Y2=c2..Yr=cr => Z1=z1,Z2=z2

여기서, X1, X2,..Xk는 양적 전제부 속성에 대응하고, Y1, Y2,..Yr 및 C는 분류별 전제부 속성에 대응한다. 여기서, [l1..u1],[l2..u2],..[lk..uk]는 다양한 양적 속성에 대한 범위에 대응한다. Z1 및 Z2는 다수의 결론부 조건에 대응한다.

본 방법은 사용자가 전제부/결론부 쌍의 형태로 사용자 질의로서 지칭되는 제안된 규칙을 가진 세 입력을 제공하도록 요구한다. 제안된 규칙에 부가적으로, 사용자는 제안된 규칙(사용자 질의)의 세기를 테스트하기 위하여 최소 필요한 신뢰성(minconfidence=c) 및 최소 필요한 서포트(minsupport=s)에 대한 값을 제공한다.

최소 신뢰성 및 최소 서포트는 일반적 관련 규칙을 발견함에 따라 양적 관련 규칙의 발견에 적절하다. 전형적이 사용자 입력의 예는:

예 A: 전형적인 사용자 입력

1. 사용자는 테스트할 제안된 규칙을 제공한다(질의)

전제부 조건 결론부 조건

Age[20-40], Salary[100k-200k], Sex=Female => Cars=2

2. 사용자는 Minconfidence, c로서 지칭되는, 제안된 규칙에 대한 신뢰성 값을 제공한다.

Minconfidence = 50%

3. 사용자는 Minsupport, s로서 지칭되는, 제안된 규칙에 대한 서포트 값을 제공한다.

Minsupport = 10%

도 1은 본 발명의 방법의 구조에 대한 전반적인 설명이다. 네트워크(35)를 통해 사전처리된 데이터를 액세스할 수 있는 다수 클라이언트(40)가 있다고 가정한다. 사전처리된 데이터는 서버(5)에 상주한다. 사전처리된 데이터(20)와 함께 서버 단말기에서 캐시(25)가 있을 수 있다. 사전처리뿐 아니라 온라인 처리가 CPU(10)에서 발생된다. 또한, 데이터가 디스크에 저장된 경우에 디스크(15)가 제공된다.

본 발명의 방법은 사전처리 스테이지에 이은 온라인 처리 스테이지의 두 스테이지를 포함한다. 도 2는 알고리즘에 대한 사전처리 스테이지 뿐 아니라 온라인 스테이지(규칙 발생 단계)의 전반적인 설명을 도시한다. 사전처리 스테이지는 이진 인덱스 트리 구조의 구성과 관련있는 데, 도 2a의 단계(75) 및 도 3(a)의 관련된 상세한 설명을 참조한다. 인덱스 트리 구조는 다차원 데이터상의 인덱스에 대한 수단으로 사용되는 본 기술분야에 잘 알려진 공간 데이터 구조이다. 종래기술에서 관련 작업은 구트만, 에이의 ACM SIGMOD 칸퍼런스 회보, A dynamic Index Struturefor Spatial Searching.에서 알 수 있다. 본 발명의 방법에서, 온라인 질의를 수행하는 데 이 인덱스 트리 구조물상의 변경을 사용한다. 데이터를 분할하는 데 전제부 속성을 활용하여 다차원 인덱싱 구조를 생성한다. 인덱싱 구조는 2레벨 구조로서, 보다 높은 레벨 노드는 많아야 두 연속 노드와 관련있고, 보다 낮은 레벨 노드는 둘 이상의 연속 노드를 가질 수 있다. 인덱싱 구조의 구성은 효과적인 온라인 데이터 마이닝을 수행하는 데 중요하다. 키 장점은 사용자 질의에 응답하는 데 필요한 디스크 I/O 양을 최소화하는 데 있다.

도 3(b)는 인덱스 트리의 형태로, 컴퓨터 메모리에 저장된 인덱싱 구조의 그래픽 아날로그를 도시한다. 인덱스 트리는 다차원 데이터에 대해 인덱스하는 데 사용되는 잘 알려진 공간 데이터 구조이다. 온라인 질의시에 사용자에 의해 명시된 특정한 양적 속성에 의해 정의되는 각 차원에 대해 컴퓨터 메모리에서 개별 인덱스 구조가 생성될 것이다. 도 3(b)는 전제부 조건, "Age" 및 그와 관련된 결론부 조건, "FirstTimeBuyer"를 나타내는 인덱스 트리 구조의 특정 예이다. 인덱스 트리의 개념을 더욱 명확히 하기 위하여, 도 3(b)는 아래의 예에서 "Age" 차원을 나타낼 수 있다:

예 B: 샘플 사용자 질의

전제부 조건 결론부 조건

Salary[40k-85k], Age[0-100] => FirstTimeBuyer

일반적으로, 전제부 및 결론부 조건을 포함하는 양적 및 분류별 속성의 결합 또는 양에 관해 제한이 없다.

도 3(b)에서, 인덱스 트리 구조의 루트 노드는 사용자 명시한 양적 속성 Age[0-100]를 정의한다. 트리의 연속된 노드의 각각은 또한, 트리 계층의 상부로 부터 바닥으로 범위 제한이 점점 좁아지는 양적 속성 Age를 나타낸다. 예를 들면, Age[0-100]에 대한 루트 노드로의 이진 후임자는 Age[0-45] 및 Age[45-100]이다. 본 발명의 방법은 관심이 되는 신뢰성 및 서포트 레벨을 나타내는 인덱스 트리의 각 노드에 두 부분의 데이터를 저장한다. 예를 들면, 도 3(b)를 참조하면, 루트 노드에서 두 부분의 데이터가 다음으로 저장된다;

1. 신뢰성 레벨 = 50%

2. 서포트 레벨 = 원래 데이터베이스로 입력되는 데이터 함수

이들은 사용자 질의에 대한 신뢰성 및 서포트를 루트 노드에서 정의한다(전제부/결론부 쌍),

Age[0-100] => FirstTimebuyer

도 3(a)는 도 2에서 단계(75)로서 도시된 알고리즘의 사전처리 스테이지의 상세한 흐름도이다. 이 스테이지의 처리 단계는 이진 인덱스 트리 구조를 발생하는 것과, 구조물의 각 노드에 결론부 속성에 대한 서포트 및 신뢰성 레벨을 저장하는 것, 이어서, 인덱스 트리가 사용가능한 메모리에 들어맞도록 보장하기 위해 구조의 하부 레벨상에서 압축 알고리즘을 활용하는 것과 관련있다. 단계(300)는 사전처리 스테이지로의 진입 지점이다. 단계(310)는 이진 인덱스 트리를 발생하기 위해 이진화 알고리즘을 사용하는 처리 단계를 구현하기 위한 소프트웨어를 나타낸다. 이진화 단계는 종래기술인 1997년, 공간 데이터베이스의 심포지움, 아가르왈 씨. 씨.,울프 제이., 유 피. 에스., 에펠만 엠. 에이의 S-Tree: An efficient index tree for multidimensional index trees에서 거론되었다. 그러나, 본 발명의 방법은 적어도 하나의 양상에서 종래기술과 다르다. 단계(315)에서, 인덱스 노드의 엔트리가 조직화되는 방식은 결론부 속성의 각 값에 대한 서포트 레벨 및 신뢰성 레벨이 구조의 각 노드에 저장된다는 점에서 고유하다. 단계(320)는 보다 낮은 레벨 인덱스 노드를 단일 노드로 압축시키기 위하여 소프트웨어 압축 알고리즘을 활용하는 처리 단계를 나타낸다.

도 4(a)는 도 2(b)에 단계(100)로 도시된 인덱스 트리로부터 미병합 규칙 트리를 발생하기 위하여 사용되는 주된 검색 알고리즘의 상세한 흐름도이다. 이 알고리즘은 입력으로서 minconfedence c 및 minsuppoer s에 대한 사용자 명시값, 질의박스(Querybox) Q 및 하나 또는 그이상의 우측면값, Z1=z1, Z2=z2으로 구성되는 사용자 질의에 대한 사용자 명시값을 입력으로 요구한다. 질의박스는 사용자 질의의 전제부 부분 또는 좌측을 표기하기 위한 단지 기술적인 항이다. 질의박스의 의미를 보다 명확히 하기 위하여, 아래의 예 C는 본 발명의 방법에서 입력으로 온라인 사용자에게 요구한다.

예 C: 전형적인 사용자 입력

사용자는 명시한다:

(1.) 최소 신뢰성 값, [minconfidence, c]

(2.) 최소 서포트 값, [minsupport, s]

또한, 온라인 사용자에게 (전제부/결론부) 쌍, 항목 34의 형태로 사용자 질의(제안된 규칙)를 입력하도록 요구한다.

(3.) 질의박스, "Q" [전제부]

(4.) Z1=z1, Z2=z2 등..[결론부]

항목 3의 질의박스는 후속되는 예로써 더 설명되며, 일반적으로 양적 및 분류별 속성의 결합으로 구성될 수 있다. 항목 4인 결론부 속성은 하나 또는 그이상의 분류별 속성으로 구성될 수 있다.

[예 1]: 이 사용자 명시된 질의는 Age 및 Lefthandedness의 2차원을 가진 전제부 조건인 질의박스, 그리고 단일 분류별 결론부 조건인, asmoker으로 구성된다.

질의박스

Age[0-24], Lefthanded ==> asmoker

[예 2]: 이 사용자 명시된 질의는 Heigth 및 Income의 2 차원을 가진 전제부 조건인 질의 박스와, 다수의 결론부 조건으로 구성된다.

질의박스

Height[5-7],Income[10k-40k] ==> owensahome,owensacar

[예 3]: 사용자 명시 질의는 단일 차원인 Age를 가진 전제부 조건인 질의 박스와, 단일 결론부 조건으로 구성된다.

질의박스

Age[10-43] ==> asmoker

예 C는 사용자가 입력으로서 무엇을 방법에 제공했는 가에 대한 일반적인 개념을 기술한다. 아래의 예 D는 전술한 예 2에서 사용자 질의를 사용하여 전형적인입력/출력 결과가 무엇처럼 보이는 가의 대표적인 예를 제공한다:

예 D: 전형적인 사용자 입력

사용자는 입력으로서 명시한다:

1. minconfidence= .50

2. minsupport = .4

3. querybox(antecedent condition) = Height[5-7],Income[10k-40k]

4. consequent condition of interest = ownsahome=1,owensacar=1

항목 (34)로부터 형성된 사용자 질의는:

Height[5-7],Income[10k-40k] ==> ownsahome,owensacar

결과적인 출력:발생 규칙

Height[5.5 - 6.2],Income[13k - 27.4k] ==> ownsahome=1,owensacar=1

일반적으로, 출력은 생각한 바 대로 규칙을 발생하지 않거나 혹은 한 규칙을 발생하거나 혹은 다수의 규칙을 발생할 수 있다. 전술한 예에서 단일 규칙이 발생되었다. 발생된 규칙은 사용자 명시 신뢰성 및 서포트 레벨 0.5 및 0.4에서 사용자 질의(전제부/결론부 쌍)를 만족시킨다.

도 4(a)에서 정의된 인덱스 트리로부터의 비병합 규칙 트리를 발생하기 위한 알고리즘은 인덱스 트리에서 모든 노드를 하나씩 검색하므로써 진행된다. 단계(400)는 주된 검색 알고리즘으로의 진입 지점이다. 단계(410)는 인덱스 트리의 루트 노드에 대한 포인터 Currentnode를 설정하는 처리 단계를 나타낸다. 포인터 Currentnode는 항상, 알고리즘이 현재 검색중인 인덱스 트리의 특정 노드를 가리킬 것이다. 단계(420)는 검색 알고리즘에 의해 스캔되기에 적격한 노드로 간주되는 노드 셋으로서 리스트(LIST)를 정의한다. 리스트는 단계(420)에서 루트 노드만을 포함하도록 초기화된다. 단계(430)는 사용자 제공 입력값 minsupport s와 적어도 동일한 서포트를 가지며 질의박스 Q와 교차하는, Currentnode에 의해 지시되는 노드의 모든 자노드를 리스트에 추가하는 처리 단계를 나타낸다. 자노드와 관련된 모든 전제부 조건이 질의박스에 의해 정의된 전제부 조건내에 전부 포함될 때, 자노드는 질의박스 Q와 교차한다고 말한다. 단계(440)는 CurrentNode에 포함된 개별 데이터 레코드가 적어도 시간의 c 퍼센트에서 결론부 조건, Z1=z1 및 Z2=z2를 만족시키는 지의 여부를 판정하는 판정 단계이다. 단계(440)의 조건이 만족되면, 알고리즘은 단계(445)로 넘어간다. 단계(445)는 우측인 결론부 조건상의 속성 셋에 대응하는 규칙을 발생한다. 단계(450)는 단계(440, 445)를 뒤이어서, 리스트로부터 Currentnode에 의해 현재 지시되는 노드를 삭제하고, 포인터 Currentnode를 리스트에 포함된 다음 노드로 설정하는 처리 단계를 나타낸다. 단계(460)는 리스트가 비었는 지를 결정하고, 조건이 충족될 때 알고리즘을 종료한다. 그렇지 않으면, 알고리즘은 단계(430)로 복귀하고, 포인터 Currentnode에 의해 현재 지시되는 노드에 대한 단계를 반복한다. 알고리즘의 종료시에, 미병합 규칙 트리는 사용자 명시 최소 서포트 minsupport s를 만족시키는 입력 인덱스 트리에서 모든 노드로 구성되는 출력이다.

도 5(a)는 미병합 규칙 트리로부터 병합 규칙 트리를 구성하는 처리를 기술하는 상세한 흐름도이다. 흐름도에 의해 기술되는 알고리즘은 미병합 규칙 트리를 압축하여 규칙의 계층적 표현을 얻는 다. 미병합 규칙 트리는 각 노드에서 노드가 의미있는 가에 대한 결정을 행하는 제1 깊이 우선 검색 순서로 순회된다. 의미있는 노드란 이와 관련된 규칙을 가지는 노드로 정의된다. 규칙은 미병합 규칙 트리가 생성되었을 때 노드와 관련될 수도 있고 혹은 관련되지 않을 수도 있다. 의미있는 노드와 의미없는 노드 간의 구분을 명확히 하기 위하여, 의미있는 노드가 노드(1, 2, 4)에 대응하는 미병합 규칙 트리인 도 4(b)를 다시 참조한다. 모든 의미있는 노드는 병합 규칙 트리에 보존된다. 노드가 의미없는 것으로 판정되면, 알고리즘은 이 노드를 제거하거나 혹은 소정 조건이 충족될 때 다수의 자노드들을 단일노드로 병합시킨다.

단계(500)는 알고리즘으로의 진입 지점을 나타낸다. 단계(510)는 미병합 규칙 트리가 깊이 우선 검색 순서로 순회됨을 확인하기 위한 처리 단계를 구현하기 위한 소프트웨어를 나타낸다. 단계(515)는 깊이 우선 순회로 미병합 규칙 트리에서 다음 노드로의 진행 단계를 나타낸다. 단계(520)는 현 규칙 노드가 의미있는 노드인지를 결정하는 판정 단계를 나타낸다. 현재 노드가 의미있는 노드로 판정될 때 단계(530)로 분기된다. 그렇지 않으면, 알고리즘은 단계(540)로 분기하여 노드를 의미없는 것으로 분류한다. 단계(540)는 의미없는 노드가 자노드를 가지는 지의 여부를 판정하는 판정 단계이다. 의미없는 노드가 자노드를 가지지 않는 경우, 단계(550)로 분기가 행해진다. 단계(550)는 현 의미없는 노드를 삭제하는 처리 단계를 나타낸다. 이와 달리, 단계(540)에서 현재 노드가 자노드를 가지는 것으로 판정되면, 단계(560)로 분기가 행해질 것이다. 단계(560)는 현재 의미없는 노드가 하나 또는 그이상의 자노드를 가지는 지를 결정하기 위한 판정 단계이다. 현재 노드가 하나의 자노드만을 가지는 경우, 단계(570)로 분기가 행해진다. 단계(570)는 현재 노드를 삭제하고, 인덱스 트리에서 삭제된 의미없는 노드의 부노드(parent node) 및 자노드들을 함께 직접 연결시키는 처리 단계를 구현하기 위한 소프트웨어를 나타낸다. 이와 달리, 현재 노드가 다수의 자노드를 가지는 것으로 발견되는 경우에, 분기는 단계(580)로 행해진다. 단계(580)는 두 자노드의 최소 경계 직사각형(minimun bounding rectangle)이 의미없는 부노드의 최소 경계 직사각형 보다 큰 지의 여부를 결정하는 판정 단계이다. 최소 경계 직사각형은 각 자노드에 대한 양적 속성의 상부 경계 및 하부 경계(범위)에 의해 정의된다. 자노드의 범위들이 결합되어 부 노드의 범위보다 넓어지면 병합이 발생된다. 예를 들어, 자노드가 다음과 같이 정의된 경우,

child node 1 - age[10-20]

child node 2 - age[30-40]

그리고, 대응하는 부노드가 다음과 같이 정의된 경우,

parent node - age[10-30]

자노드 속성 범위의 결합이 부노드에 의해 명시된 범위[10-30] 보다 넓은 결합된 범위 [10-40]를 이끌어내므로, 이 예에서 병합이 발생된다.

두 자노드의 최소 경계 직사각형이 부노드의 최소 경계 직사각형을 초과하는 경우, 단계(590)로 분기된다. 단계(590)는 부노드의 최소 경계 직사각형을 두 자노드의 최소 경계 직사각형이 되도록 조정하는 처리 단계를 수행하기 위한 소프트웨어를 나타낸다. 판정 단계(600)로 분기하여,트리에서 더이상의 순회할 노드가 있는 지의 여부를 결정한다. 더이상 순회할 노드가 없는 경우에 종료 단계(610)로 분기하고, 그렇지 않은 경우, 나머지 인덱스 트리에 대해 처리 단계(490-515)를 반복한다.

도 6은 사용자 명시 관심 레벨 r에서 규칙을 정의하기 위하여 입력으로서 항병 규칙 트리를 사용하는 처리를 기술하는 상세한 흐름도이다. 병합 규칙 트리를 깊이 우선 순서로 순회한다. 단계(616)는 흐름도로의 진입 지점이다. 사용자는 관심 레벨을 나타내는 r에 대한 입력값을 명시한다. 단계(618)는 깊이 우선 순서로 병합 규칙 트리에서 다음 노드를 선택하는 것을 나타낸다. 단계(620)는 그들중의 임의 노드가 현재 노드의 1/r과 적어도 동일한 신뢰성 값을 가지는 지의 여부를 결정하기 위하여 관심의 대상인 현재 노드의 모든 조상 노드를 조사하는 것을 나타내는 판정 단계이다. 조건이 참일 때 단계(630)로의 분기가 이루어질 것이다. 단계(630)는 현재 노드와 관련된 규칙을 잘라내는 것을 나타낸다. 단계(620)에서의 조건이 충족되지 않으면, 단계(640)로 분기한다. 단계(640)는 병합 규칙 트리에서 평가할 노드가 남아있는 지의 여부를 결정하는 판정 단계이다. 처리 단계는 평가할 부가적인 노드가 있는 경우에 반복될 것이며, 그렇지 않으면, 처리는 이 지점에서 종료된다.

따라서, 요약하면, 양적 관련 규칙을 발견하기 위하여 데이터 아이템의 데이터 마이닝하는 온라인 방법을 제공할 수 있는 데, 여기서, 데이터 아이템은 다양한 종류의 양적 및 분류별 속성을 포함한다.

Claims (22)

1. 양적 연관 규칙(quantitative association rules)을 제공하기 위한 다수의 양적 및 분류별 아이템(quantitative and categorical items)을 제각기 가진 다수의 레코드를 가지는 큰 데이터베이스를 온라인 마이닝(online mining)하는 방법에 있어서,

   가) 전제부(antecedent)와 결론부(consequent) 속성을 포함하는 사용자 질의를 수신하는 단계와,

   나) 상기 전제부와 결론부 속성 사이의 관계를 조직화하는 단계와,

   다) 상기 전제부 속성 사이의 관계를 정의하는 데이터와 상기 결론부 속성에 관련된 데이터를 사전저장하는 단계와,

   라) 상기 사용자 질의에 응답하여 사전저장된 데이터로부터 하나 이상의 양적 연관 규칙을 도출하는 단계

   를 포함하는 데이터베이스 온라인 마이닝 방법.
2. 제 1 항에 있어서,

   하나 이상의 양적 연관 규칙, 각 규칙과 연관된 실제 신뢰성 값, 각 규칙과 연관된 실제 서포트 값, 각 규칙과 연관된 관심 레벨을 사용자에게 디스플레이하는 단계를 더 포함하는 데이터베이스 온라인 마이닝 방법.
3. 제 2 항에 있어서,

   상기 양적 연관 규칙은 관심있는 규칙만을 포함하고,

   상기 관심 있는 규칙은 그 계산된 관심 레벨이 사용자가 정의한 관심 레벨과 적어도 동일한 규칙을 포함하는

   데이터베이스 온라인 마이닝 방법.
4. 제 3 항에 있어서,

   상기 관심 레벨은 계산된 제 1 및 제 2 비율 중 최소값으로 정의되고,

   상기 제 1 비율은 상기 실제 신뢰성을 기대 신뢰성(an expected confidence)으로 나눈 값으로 정의되며,

   제 2 비율은 상기 실제 서포트를 기대 서포트로 나눈 값으로 정의되고,

   상기 기대 신뢰성 및 서포트는 통계상 독립적이라는 가정을 근거로 계산된 값인

   데이터베이스 온라인 마이닝 방법.
5. 제 1 항에 있어서,

   상기 전제부 속성은 분류별 속성과 양적 속성으로 구성되는 데이터베이스 온라인 마이닝 방법.
6. 제 5 항에 있어서,

   상기 양적 속성은 하부 및 상부 경계로 이루어진 범위에 의해 더 정의되는 데이터베이스 온라인 마이닝 방법.
7. 제 1 항에 있어서,

   상기 조직화 단계 나)는 상기 전제부 데이터를 인덱스 트리(an index tree)로 계층적으로 구획(partitioning)하고, 상기 인덱스 트리는 다수의 인덱스 노드를 포함하는 데이터베이스 온라인 마이닝 방법.
8. 제 7 항에 있어서,

   상기 구획 단계는

   ㉮ 상기 인덱스 트리의 각 인덱스 노드에 상기 실제 서포트를 나타내는 제 1 값을 저장하는 단계와,

   ㉯ 상기 인덱스 트리의 각 인덱스 노드에 각각의 사용자 질의 결론부 속성에 대한 발생 빈도를 나타내는 제 2 값을 저장하는 단계

   를 포함하는 데이터베이스 온라인 마이닝 방법.
9. 제 1 항에 있어서,

   상기 도출 단계 라)는

   ㉮ 상기 인덱스 트리의 모든 인덱스 노드를 검색하여 그 전제부 속성 범위가 상기 사용자 질의 전제부 속성 범위에 대응하는 노드들을 분리하는 단계와,

   ㉯ 상기 단계 ㉮의 기준을 만족시키는 노드들 중 그 결론부 속성이 사용자가 정의한 최소 신뢰성 값과 적어도 동일한 것을 선택하는 단계와,

   ㉰ 상기 단계 ㉮와 ㉯의 기준을 만족시키는 노드들로부터 병합 트리(a merge tree)를 구축하는 단계

   를 더 포함하는 데이터베이스 온라인 마이닝 방법.
10. 제 9 항에 있어서,

    상기 구축 단계 ㉰는 의미없는 노드들을 삭제하고 나머지 노드들을 조합하여 상기 병합 트리를 생성하는 단계를 더 포함하는 데이터베이스 온라인 마이닝 방법.
11. 제 10 항에 있어서,

    상기 의미없는 노드는 상기 사용자가 정의한 최소 신뢰성 값과 적어도 동일한 계산된 대응 신뢰성 값을 갖지 않는 노드인 데이터베이스 온라인 마이닝 방법.
12. 제 10 항에 있어서,

    상기 병합 트리는 하나 또는 다수의 결론부 속성에 대해 구축될 수 있는 데이터베이스 온라인 마이닝 방법.
13. 양적 연관 규칙을 제공하기 위한 다수의 양적 및 분류별 아이템을 제각기 가진 다수의 레코드를 가지는 큰 데이터베이스를 온라인 마이닝하는 컴퓨터로 실행가능한 방법에 있어서,

    가) 사용자가 정의한 최소 서포트 값, 사용자가 정의한 최소 신뢰성 값, 사용자가 정의한 관심 값, 사용자 질의 - 상기 사용자 질의는 전제부 및 결론부 조건을 포함하고, 상기 전제부 및 결론부 조건은 다수의 양적 및 분류별 속성을 포함함 - 를 포함하는 데이터를 수신하는 단계와,

    나) 하나 이상의 차원으로 이루어진 인덱스 트리를 메모리 내에 구축하는 단계 - 각 차원은 양적 속성 중 하나에 의해 정의되고, 상기 인덱스 트리는 다수의 인덱스 노드를 포함하며, 상기 인덱스 노드는 다수의 데이터 레코드를 더 포함함 - 와,

    다) 상기 인덱스 트리로부터 비병합 규칙 트리(an unmerged rule tree)를 메모리 내에 구축하는 단계와,

    라) 상기 비병합 규칙 트리로부터 병합 규칙 트리를 메모리 내에 구축하는 단계와,

    마) 상기 사용자 질의를 만족시키고 그 서포트가 상기 최소 서보트와 적어도 동일하며, 그 신뢰성이 상기 최소 신뢰성과 적어도 동일한 인덱스 노드로부터 하나 이상의 양적 연관 규칙을 발생시키는 단계와,

    바) 상기 발생 단계 마)로부터의 상기 양적 연관 규칙과, 각각의 발생된 양적 연관 규칙과 연관된 실제 신뢰성 값과, 각각의 발생된 양적 연관 규칙과 연관된 서포트 값과, 각각의 발생된 양적 연관 규칙과 연관된 관심 레벨 값을 포함하는 출력 데이터를 사용자에게 디스플레이하는 단계

    를 포함하는 데이터베이스 온라인 마이닝 방법
14. 제 13 항에 있어서,

    상기 양적 연관 규칙 발생 단계 마)는 상기 사용자 질의가 상호작용에 의해 수정되어 상기 연관 규칙을 더 정의하도록 반복되는 데이터 베이스 온라인 마이닝 방법.
15. 양적 연관 규칙을 제공하기 위한 다수의 양적 및 분류별 아이템을 제각기 가진 다수의 레코드를 가지는 큰 데이터베이스를 온라인 마이닝하는 장치에 있어서,

    사용자가 정의한 최소 신뢰성 값, 사용자가 정의한 최소 서포트 값, 상기 양적 및/또는 분류별 아이템에 의해 표현되는 전제부 및 결론부 속성을 포함하는 사용자 질의를 수신하는 수단과,

    전제부 데이터를 다수의 인덱스 노드를 포함하는 인덱스 트리로 계층적으로 사전저장함으로써 상기 전제부 및 결론부 속성 사이의 관계를 조직화하는 수단 - 각 인덱스 노드는 각 사용자 질의 결론부 속성에 대한 실제 서포트 및 신뢰성을 나타내는 제 1 및 제 2 값을 가짐 - 과,

    상기 인덱스 트리의 모든 인덱스 노드를 검색하여 상기 사용자 질의 전제부 속성 범위에 대응하는 전제부 속성과 상기 사용자가 정의한 최소 신뢰성 값과 적어도 동일한 신뢰성 및 상기 사용자가 정의한 최소 서포트 값과 적어도 동일한 서포트값을 가지는 노드들을 분리함으로써 상기 사용자 질의에 응답하여 상기 사전저장된 데이터로부터 응답을 도출하는 수단

    을 포함하는 데이터베이스 온라인 마이닝 장치.
16. 삭제
17. 삭제
18. 삭제
19. 삭제
20. 제 13 항에 있어서,

    상기 인덱스 트리 구축 단계 나)는

    ㉮ 상기 인덱스 트리의 각 노드를 검색하는 단계와,

    ㉯ 사용자 고유의 결론부 조건을 만족시키는 규칙을 포함하고, 상기 사용자가 정의한 최소 신뢰성 값과 적어도 동일한 신뢰성 값 및 상기 사용자가 정의한 최소 서포트 값과 적어도 동일한 서포트 값을 갖는 노드를 선택하는 단계

    를 포함하는 데이터 베이스 온라인 마이닝 방법.
21. 제 1 항에 있어서,

    상기 수신 단계 가)는 사용자가 정의한 최소 신뢰성 값, 사용자가 정의한 최소 서포트 값, 사용자가 정의한 관심 레벨 값 중 하나 이상을 수신하는 단계를 더 포함하는 데이터 베이스 온라인 마이닝 방법.
22. 제 21 항에 있어서,

    상기 도출 단계 라)는 상기 사용자 질의를 만족시키고, 상기 최소 서포트 값, 상기 최소 신뢰성 값, 상기 관심 레벨 값 중 상기 하나 이상을 포함하는 하나 이상의 양적 연관 규칙을 도출하는 단계를 포함하는 데이터 베이스 온라인 마이닝 방법.