6. 데이터 마이닝 - Association Analysis(1)

1. Association Rule Mining

 1. Association Rule Mining이란 Transactions의 집단에서 특정 항목의 발생을 예상할 수 있는 Rule을 찾는 것이다.

 2. Example

 3. 용어 : 2. Example의 왼쪽 사진을 보자

▪ 항목집합(Itemset) : 사진의 record처럼 Item의 집단(ex : { Bread, Milk } )이다.
    - record에 속하는 item의 개수에 따라 k-itemset이라고 부른다. 

    - 2번째 record는 4-itemset이다.

▪ Itemset의 Support Count : 특정 Item 집합을 포함하고 있는 Transaction(Record)의 수 

▪ Itemset의 Support  : 전체 Transaction 중 해당 Item 집합을 포함하고 있는 Transaction의 비율이다.

    - 예 : s{Eggs} = 1/5 = 0.2, s({Milk, Bread, Diaper}) = 2/5

▪ 빈발항목집합(Frequent Itemset) : 지지도가 주어진 임계치인 minimum support보다 큰 항목집합 
    - 만약 minsup = 0.3이라면, {Eggs}은 빈발하지 않으며, {Milk, Bread, Diaper}은 빈발함

 4. 연관규칙(Association Rule)

▪ 정의 : X와 Y가 항목집합 일때, X -> Y 형태로 나타나는 함축 표현(implication expression)

    - 예 : { Milk, Diaper } -> { Bread }

▪ 연관 규칙의 지지도(Support) : 전체 Transaction 중 X와 Y를 2개를 모두 포함하고 있는 Transaction 비율

    - 예 : { Milk, Diaper } -> { Bread } 의 itemset은 { Milk, Diaper, Bread }이다. 해당 itemset을 포함하고 있는 Transaction은 총 5개중 2개이며 2/5이다.

    - 규칙이 얼마나 중요하며, 유용한지 알 수 있으며 낮은 지지도의 규칙은 우연이라고 볼 수 있다.

▪ 연관 규칙의 신뢰도(Confidence) : X를 포함한 Transaction 중 Y를 포함하는 Transaction의 비율

    - { Milk, Diaper }를 포함하는 Transaction은 3개, { Milk, Diaper, Bread }를 포함하는 Transaction은 2개 임으로 2/3이 된다.

    - 규칙이 얼마나 신뢰성이 있는지 알 수 있다.

▪ Association Rule Mining의 목적은 Minimum Support Threshold 값과 Minimum Confidence Threshold 값을 넘기는 모든 Rule을 찾는 것이다.

 4. Brute-force 접근법(Approach)

① 모든 Association Rule을 찾는다.

② Rule의 Support값과 Confidence 값을 계산한다.

③ 임계치를 넘지 못하는 Rule을 제거한다.

 5. Brute-force 접근법의 문제점 

▪ 아래와 같은 Rule은 모두 같은 Itemset인 { Milk, Diaper, Beer }에서 파생된 Rule이다.

▪ 같은 Itemset에서 파생된 Rule은 Support값이 같지만 Confidence 값은 다르다.

▪ 위와 같은 이유 때문에 Support와 Confidence를 분리하여 Mining을 하여야 한다.

 6. 2단계 접근법

① Minimum Support Threshold보다 큰 빈발 항목 집합을 생성한다.

② 생성한 빈발 항목집합을 각각 2개의 항복집합으로 분리하여 Minimum Confidence Threshold보다 큰 Rule들을 모두 도출한다.

2. Frequent Itemset Generation

 1. 원소가 d개가 있는 Set으로 만들 수 있는 Subset의 개수는 개이다. 해당 Subset 중에서 최소 Support보다 큰 Subset은 빈발 항목 집합이라 한다. 최대 빈발 항목 집합의 개수는 아무것도 없는 Subset을 제외한 -1개이다. 

 2. d개의 항목(Item)이 주어졌을 때

 3. Frequent Itemset 생성에 대한 Brute-force 접근법

① 전체 항목(Item)에 대한 만들 수 있는 Itemset을 생성한다.

② 각각의 Transaction으로 생성할 수 있는 Itemset을 체크한다. 

▪ 복잡도 : O(NWM)

    - N : Record 또는 Transaction 개수

    - W : Transaction 중 최대 item 개수

    - d : 모든 item 개수

    - M : Candidate frequent itemset : 

 4. Frequent Itemset 생성 전략

▪ Candidate(M)의 수를 줄인다.

▪ Transaction(N)의 수를 줄인다.

▪ Candidate와 Transaction의 비교(MN) 횟수를 줄인다.

3. Candidate를 줄이는 법

 1. Apriori Principle

▪ 어떤 항목(Item)집합이 빈발하다면, 그 항목 집합의 모든 부분집합도 빈발함

 ▪ 예 : {Milk, Bread, Diaper}가 빈발 항목집합이면, 이의 부분집합인 {Milk, Bread}, {Bread, Diaper} 등도 빈발 항목집합이다.

 ▪ 어떤 항목집합의 지지도는 그 부분집합들의 지지도를 넘을 수 없다. ( = 부분집합의 지지도가 더 크다.)

▪ 이는 지지도가 anti-monotone 성질을 가지기 때문이다. (a > b -> f(a) < f(b))

▪ 항목 집합 생성 시, 특정 subset이 최소 support를 못 넘기면 해당 subset의 superset을 생성할 필요가 없다.

 2. Example

▪ 최적화 없이 모든 Itemset을 구하면 6개의 item이 있기 때문에 아래와 같다.

▪ Apriori 원리를 이용하면 3-Itemset까지 생성할 수 있으며 각각 6개, 6개 1개 총 13개가 생성된다. 

▪ 비교를 하기위해 3-Itemset까지 모든 Itemset을 생성하면 위의 식에서 6까지가 아닌 3까지 더 해서 총 41개가 생성된다.

4. Transaction과 Candidate 비교 횟수를 줄이는 법

 1. Candidate가 항목으로 만들 수 있는 모든 Subset을 가질때 해당 Subset 중 빈발 항목을 찾기위해 각 Candidate Itemset의 Support 값을 계산한다. Support 값을 계산하기 위해서는 각각의 Candidate와 Transaction DB에 있는 모든 Transaction을 비교해야한다. 그러기엔 너무 계산량이 많다.

▪ Candidate의 숫자가 매우 많다.

▪ 하나의 Transaction에 포함되는 Candidate는 복수개이다.

 2. 모든 Candidate를 Hash Structure에 저장하여 좀 더 빠르게 비교할 수 있도록 한다.

▪ Hash Tree의 Leaf Node에는 Itemset의 리스트와 회수(count)가 저장된다.

▪ Hash Tree의 Inter Node에는 Hash Table이 저장된다.

▪ Hash Function은 Transaction이 제시되었을 때 모든 Candidate를 출력해 준다.

 3. Transaction t ={1,2,3,5,6}에 속한 3-itemset을 모두 열거하는 체계적 방법 

5. Hash Tree를 이용한 Support Count 구하는 예

 1. 항목은 1~9 총 9개가 있으며 길이가 3인 Candidate Itemset은 아래와 같이 15개 있다고 가정해보자.

▪ {1 4 5}, {1 2 4}, {4 5 7}, {1 2 5}, {4 5 8}, {1 5 9}, {1 3 6}, {2 3 4}, {5 6 7}, {3 4 5}, {3 5 6}, {3 5 7}, {6 8 9}, {3 6 7}, {3 6 8}

▪ Hash Function

 2. Candidates를 가지고 Hash Function에 맞추어 Hash Tree를 작성한다. 

▪ Tree의 Level에 따라 Hash function이 적용되는 Itemset 내부의 Item 위치가 달라진다.

 3. 입력된 Transaction을 Hash Function을 이용해서 방문해야할 Leaf Node를 찾는다.

 4. 방문한 Leaf Node에서 일치하는 Candidate만 Count를 증가시킨다.