데이터전처리 Data Preprocessing
09 연관분석 (Association Analysis)
목차 1. 연관규칙 2. 빈발항목집합생성 3. 연관규칙생성 4. 빈발항목집합표현 5. 연관패턴평가 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 3
1. 연관규칙
연관규칙마이닝 트랜잭션집합이주어지면, 트랜잭션에서다른항목들의발생을기반으로항목의발생을예측하는규칙찾기 시장-바구니거래Market-Basket transactions TID Items 1 Bread, Milk 2 Bread, Diaper, Beer, Eggs 3 Milk, Diaper, Beer, Coke 4 Bread, Milk, Diaper, Beer 5 Bread, Milk, Diaper, Coke 연관규칙의예 {Diaper} {Beer}, {Milk, Bread} {Eggs,Coke}, {Beer, Bread} {Milk}, 함축 Implication 은공동출현을의미하며, 인과관계 causality 를의미하지않음 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 5
정의 : 빈발항목집합Frequent Itemset 항목집합 Itemset 하나이상의항목모음 예 : {Milk, Bread, Diaper} k- 항목집합 k-itemset : k 개항목들이포함된항목집합 지지횟수 Support count ( ) 항목집합의출현빈도 예 : ({Milk, Bread, Diaper}) = 2 TID Items 1 Bread, Milk 2 Bread, Diaper, Beer, Eggs 3 Milk, Diaper, Beer, Coke 4 Bread, Milk, Diaper, Beer 5 Bread, Milk, Diaper, Coke 지지도 Support 항목집합을포함하는트랜잭션의비율 예 : s({milk, Bread, Diaper}) = 2/5 빈발항목집합Frequent Itemset minsup 임계값보다크거나같은항목집합 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 6
정의 : 연관규칙Association Rule 연관규칙Association Rule X Y 형식의함축적표현식, 여기서 X 와 Y 는항목집합 예제 : {Milk, Diaper} {Beer} 규칙평가척도Rule Evaluation Metrics 지지도 Support (s): X 와 Y 모두를포함하는트랜잭션의비율 신뢰도 Confidence (c): X 가포함된트랜잭션에서 Y 에있는항목이나타나는빈도측정 TID Items 1 Bread, Milk 2 Bread, Diaper, Beer, Eggs 3 Milk, Diaper, Beer, Coke 4 Bread, Milk, Diaper, Beer 5 Bread, Milk, Diaper, Coke 예제 : Milk, Diaper Beer s = c = σ Milk, Diaper, Beer T σ Milk, Diaper, Beer σ Milk, Diaper = 2 5 = 0.4 = 2 3 = 0.67 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 7
연관규칙마이닝작업 트랜잭션집합 T 가주어질때, 연관규칙마이닝의목표는다음조건을갖는모든규칙을찾는것 support minsup 임계값 confidence minconf 임계값 무차별대입접근 Brute-force approach : 가능한모든연관규칙나열 각규칙에대한지지도와신뢰도계산 minsup 와 minconf 임계값에포함안된규칙삭제 계산금지Computationally prohibitive 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 8
계산복잡도 주어진 d 개의고유항목 : 총항목집합의수 = 2 d 가능한연관규칙의전체수 : d 1 R = k=1 d k = 3 d 2 d+1 + 1 d k j=1 만약 d = 6 이면, R = 602 규칙 d k j 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 9
마이닝연관규칙 규칙예제 : {Milk,Diaper} {Beer} (s=0.4, c=0.67) {Milk,Beer} {Diaper} (s=0.4, c=1.0) {Diaper,Beer} {Milk} (s=0.4, c=0.67) {Beer} {Milk,Diaper} (s=0.4, c=0.67) {Diaper} {Milk,Beer} (s=0.4, c=0.5) {Milk} {Diaper,Beer} (s=0.4, c=0.5) TID Items 1 Bread, Milk 2 Bread, Diaper, Beer, Eggs 3 Milk, Diaper, Beer, Coke 4 Bread, Milk, Diaper, Beer 5 Bread, Milk, Diaper, Coke 관찰 Observations : 위에모든규칙은동일한항목집합 {Milk, Diaper, Beer} 의이진분할binary partitioning 같은항목집합에서비롯된규칙은동일한지지도를갖지만다른신뢰도를가질수있음 따라서, 지지도와신뢰도요구사항을분리할수있음 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 10
마이닝연관규칙 2 단계접근 : 빈발항목집합생성 : support minsup 인모든항목집합생성 규칙생성 : 각빈발항목집합에서높은신뢰규칙생성, 여기서각규칙은빈발항목집합의이진분할 빈발항목집합생성은여전히계산적으로비용이높음 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 11
2. 빈발항목집합생성
빈발항목집합생성 null A B C D E AB AC AD AE BC BD BE CD CE DE ABC ABD ABE ACD ACE ADE BCD BCE BDE CDE ABCD ABCE ABDE ACDE BCDE ABCDE d 개의항목이주어지면, 가능한후보항목집합이 2 d 개 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 13
빈발항목집합생성 무차별대입접근 Brute-force approach : 격자의각항목집합은빈발항목집합후보 데이터베이스를스캔하여각후보의지지횟수계산 모든후보와각트랜잭션을매치 복잡도 ~ O(NMw) => M = 2 d 이므로비쌈 N Transactions TID Items 1 Bread, Milk 2 Bread, Diaper, Beer, Eggs 3 Milk, Diaper, Beer, Coke 4 Bread, Milk, Diaper, Beer 5 Bread, Milk, Diaper, Coke w List of Candidates M 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 14
빈발항목집합생성전략 후보수감소 (M) 완전한검색 : M=2 d 가지치기 pruning 기술을사용하여 M 을감소 트랜잭션수감소 (N) 항목집합의크기가커짐에따라 N 의크기감소 DHP 및수직기반마이닝알고리즘이사용됨 비교횟수감소 (NM) 효율적인데이터구조를사용하여후보또는트랜잭션저장 모든트랜잭션과모든후보들을매치할필요는없음 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 15
후보수감소 Apriori 원리 : 항목집합이빈발하게있는경우모든부분집합도빈발해야함 Apriori 원리는다음과같은지지도값특성에따라유지 항목집합의지지도는부분집합의지지도를결코초과하지않음 지지도의안티-모노톤 anti-monotone 특성으로알려져있음 X, Y : ( X Y ) s( X ) s( Y ) 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 16
Apriori 원리설명 null A B C D E AB AC AD AE BC BD BE CD CE DE 빈번하지않게발견 ABC ABD ABE ACD ACE ADE BCD BCE BDE CDE ABCD ABCE ABDE ACDE BCDE 제거된상위집합 ABCDE 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 17
Apriori 원리설명 TID Items 1 Bread, Milk 2 Beer, Bread, Diaper, Eggs 3 Beer, Coke, Diaper, Milk 4 Beer, Bread, Diaper, Milk 5 Bread, Coke, Diaper, Milk Items (1-itemsets) Item Count Bread 4 Coke 2 Milk 4 Beer 3 Diaper 4 Eggs 1 최소지지도 Minimum Support = 3 만약모든하위집합이고려되면, 6C 1 + 6 C 2 + 6 C 3 6 + 15 + 20 = 41 지지도기반가지치기 support-based pruning, 6 + 6 + 4 = 16 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 18
Apriori 원리설명 TID Items 1 Bread, Milk 2 Beer, Bread, Diaper, Eggs 3 Beer, Coke, Diaper, Milk 4 Beer, Bread, Diaper, Milk 5 Bread, Coke, Diaper, Milk Items (1-itemsets) Item Count Bread 4 Coke 2 Milk 4 Beer 3 Diaper 4 Eggs 1 최소지지도 Minimum Support = 3 만약모든하위집합이고려되면, 6C 1 + 6 C 2 + 6 C 3 6 + 15 + 20 = 41 지지도기반가지치기 support-based pruning, 6 + 6 + 4 = 16 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 19
Apriori 원리설명 Item Count Bread 4 Coke 2 Milk 4 Beer 3 Diaper 4 Eggs 1 최소지지도 Minimum Support = 3 만약모든하위집합이고려되면, 6C 1 + 6 C 2 + 6 C 3 6 + 15 + 20 = 41 지지도기반가지치기 support-based pruning, 6 + 6 + 4 = 16 Items (1-itemsets) Itemset {Bread,Milk} {Bread,Beer} {Bread,Diaper} {Milk,Beer} {Milk,Diaper} {Beer,Diaper} Pairs (2-itemsets) (Coke 또는 Eggs 가포함된후보들을생성할필요없음 ) 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 20
Apriori 원리설명 Item Count Bread 4 Coke 2 Milk 4 Beer 3 Diaper 4 Eggs 1 최소지지도 Minimum Support = 3 만약모든하위집합이고려되면, 6C 1 + 6 C 2 + 6 C 3 6 + 15 + 20 = 41 지지도기반가지치기 support-based pruning, 6 + 6 + 4 = 16 Items (1-itemsets) Itemset Count {Bread,Milk} 3 {Bread,Beer} 2 {Bread,Diaper} 3 {Milk,Beer} 2 {Milk,Diaper} 3 {Beer,Diaper} 3 Pairs (2-itemsets) (Coke 또는 Eggs 가포함된후보들을생성할필요없음 ) 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 21
Apriori 원리설명 Item Count Bread 4 Coke 2 Milk 4 Beer 3 Diaper 4 Eggs 1 최소지지도 Minimum Support = 3 만약모든하위집합이고려되면, 6C 1 + 6 C 2 + 6 C 3 6 + 15 + 20 = 41 지지도기반가지치기 support-based pruning, 6 + 6 + 4 = 16 Items (1-itemsets) Itemset Count {Bread,Milk} 3 {Bread,Beer} 2 {Bread,Diaper} 3 {Milk,Beer} 2 {Milk,Diaper} 3 {Beer,Diaper} 3 Itemset {Beer, Diaper, Milk} {Beer,Bread, Diaper} {Bread, Diaper, Milk} {Beer, Bread, Milk} Pairs (2-itemsets) (Coke 또는 Eggs 가포함된후보들을생성할필요없음 ) Triplets (3-itemsets) 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 22
Apriori 원리설명 Item Count Bread 4 Coke 2 Milk 4 Beer 3 Diaper 4 Eggs 1 최소지지도 Minimum Support = 3 만약모든하위집합이고려되면, 6C 1 + 6 C 2 + 6 C 3 6 + 15 + 20 = 41 지지도기반가지치기 support-based pruning, 6 + 6 + 4 = 16 6 + 6 + 1 + 13 Items (1-itemsets) Itemset Count {Bread,Milk} 3 {Bread,Beer} 2 {Bread,Diaper} 3 {Milk,Beer} 2 {Milk,Diaper} 3 {Beer,Diaper} 3 Itemset {Beer, Diaper, Milk} {Beer,Bread, Diaper} {Bread, Diaper, Milk} {Beer, Bread, Milk} Pairs (2-itemsets) (Coke 또는 Eggs 가포함된후보들을생성할필요없음 ) Triplets (3-itemsets) Count 2 2 2 1 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 23
Apriori 알고리즘 F k : 빈발 k- 항목집합 L k : 후보 k- 항목집합 1. k=1 2. F 1 = { 빈발 1- 항목집합 } 생성 3. F k 가없을때까지반복 후보생성 Candidate Generation : F k 에서 L k+1 생성 후보가지치기 Candidate Pruning : 빈발하지않는길이가 k 인부분집합을포함한 L k+1 에있는후보항목집합을가지치기 지지도계산 Support Counting : DB 를스캔하여 L k+1 의각후보지지도계산 후보제거 Candidate Elimination : L k+1 에서빈발하지않는후보제거, frequent => F k+1 인것만남김 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 24
후보생성 Candidate Generation : 무차별대입방법Brute-force method 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 25
후보생성 Candidate Generation : F k-1 and F 1 항목집합합병 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 26
후보생성 Candidate Generation : F k-1 x F k-1 방법 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 27
후보생성 Candidate Generation : F k-1 x F k-1 방법 첫번째 (k-2) 항목이동일한경우두개의빈발 (k-1) 항목집합을병합 F 3 = {ABC,ABD,ABE,ACD,BCD,BDE,CDE} Merge(ABC, ABD) = ABCD Merge(ABC, ABE) = ABCE Merge(ABD, ABE) = ABDE 길이 2 대신길이 1 의접두사 prefix 만공유하므로 (ABD, ACD) 는병합하지않음 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 28
후보제거Candidate Pruning F 3 = {ABC,ABD,ABE,ACD,BCD,BDE,CDE} 빈발 3- 항목집합의집합 L 4 = {ABCD,ABCE,ABDE} 이전에생성된 4- 항목집합후보의집합 후보가지치기 ACE와 BCE가빈발하지않으므로 ABCE 가지치기 ADE가빈발하지않으므로 ABDE 가지치기 후보가지치기후 : L 4 = {ABCD} 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 29
대체 F k-1 x F k-1 방법 첫번째항목의마지막 (k-2) 항목이두번째항목의첫번째 (k-2) 항목과동일한경우두개의빈발 (k-1)- 항목집합을병합 F 3 = {ABC,ABD,ABE,ACD,BCD,BDE,CDE} Merge(ABC, BCD) = ABCD Merge(ABD, BDE) = ABDE Merge(ACD, CDE) = ACDE Merge(BCD, CDE) = BCDE 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 30
대체 F k-1 x F k-1 방법을위한후보제거 F 3 = {ABC,ABD,ABE,ACD,BCD,BDE,CDE} 는빈발 3- 항목집합의집합 L 4 = {ABCD,ABDE,ACDE,BCDE} 이전에생성된 4- 항목집합후보의집합 후보가지치기 ADE가빈발하지않으므로 ABDE 가지치기 ACE와 ADE가빈발하지않으므로 ACDE 가지치기 BCE 때문에 BCDE 가지치기 후보가지치기후 : L 4 = {ABCD} 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 31
Apriori 원리설명 Item Count Bread 4 Coke 2 Milk 4 Beer 3 Diaper 4 Eggs 1 최소지지도 Minimum Support = 3 만약모든하위집합이고려되면, Items (1-itemsets) Itemset Count {Bread,Milk} 3 {Bread,Beer} 2 {Bread,Diaper} 3 {Milk,Beer} 2 {Milk,Diaper} 3 {Beer,Diaper} 3 Itemset Pairs (2-itemsets) (Coke 또는 Eggs 가포함된후보들을생성할필요없음 ) Triplets (3-itemsets) Count 6C 1 + 6 C 2 + 6 C 3 6 + 15 + 20 = 41 {Bread, Diaper, Milk} 2 지지도기반가지치기 support-based pruning, 6 + 6 + 1 + 13 후보생성을위해 F k-1 xf k-1 방법을사용하면하나의 3-항목집합만생성. 이는지지도계산단계후에제거 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 32
후보항목집합의지지도계산 트랜잭션데이터베이스스캔으로각후보항목집합의지지도결정 모든트랜잭션에대해모든후보항목집합을일치시켜야함 ( 매우비싼연산 ) TID Items 1 Bread, Milk 2 Beer, Bread, Diaper, Eggs 3 Beer, Coke, Diaper, Milk 4 Beer, Bread, Diaper, Milk 5 Bread, Coke, Diaper, Milk Itemset { Beer, Diaper, Milk} { Beer,Bread,Diaper} {Bread, Diaper, Milk} { Beer, Bread, Milk} 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 33
후보항목집합의지지도계산 비교횟수를줄이기위해, 후보항목집합을해시구조에저장 모든후보에대해각트랜잭션을대조하는대신에해시버킷에포함된후보와대조 Transactions Hash Structure N TID Items 1 Bread, Milk 2 Bread, Diaper, Beer, Eggs 3 Milk, Diaper, Beer, Coke 4 Bread, Milk, Diaper, Beer 5 Bread, Milk, Diaper, Coke k Buckets 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 34
지지도계산 : 예제 길이 3 의후보항목집합 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} 트랜잭션 (1,2,3,5,6) 에서얼마나많은항목집합을지원할까? Level 1 Level 2 Transaction, t 1 2 3 5 6 1 2 3 5 6 2 3 5 6 1 2 3 5 6 1 3 5 6 1 5 6 2 3 5 6 2 5 6 3 5 6 3 5 6 1 2 3 1 2 5 1 2 6 1 3 5 1 3 6 1 5 6 2 3 5 2 3 6 2 5 6 3 5 6 Level 3 Subsets of 3 items 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 35
해시트리를사용한지지도계산 길이 3 의후보항목집합 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} 필요요소 해시함수 최대리프크기 : 리프노드에저장된항목집합의최대개수 ( 후보항목집합수가최대리프크기를초과하는경우노드분할 ) 해시함수 1,4,7 3,6,9 2,5,8 1 4 5 1 2 4 4 5 7 1 2 5 4 5 8 2 3 4 5 6 7 1 3 6 1 5 9 3 4 5 3 5 6 3 5 7 6 8 9 3 6 7 3 6 8 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 36
해시트리를사용한지지도계산 해시함수 후보해시트리 1,4,7 3,6,9 2,5,8 1, 4, 또는 7 해시 1 4 5 1 3 6 1 2 4 1 2 5 1 5 9 4 5 7 4 5 8 2 3 4 5 6 7 3 4 5 3 5 6 3 5 7 6 8 9 3 6 7 3 6 8 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 37
해시트리를사용한지지도계산 해시함수 후보해시트리 1,4,7 3,6,9 2,5,8 2, 5, 또는 8 해시 1 4 5 1 3 6 1 2 4 1 2 5 1 5 9 4 5 7 4 5 8 2 3 4 5 6 7 3 4 5 3 5 6 3 5 7 6 8 9 3 6 7 3 6 8 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 38
해시트리를사용한지지도계산 해시함수 후보해시트리 1,4,7 3,6,9 2,5,8 3, 6, 또는 9 해시 1 4 5 1 3 6 1 2 4 1 2 5 1 5 9 4 5 7 4 5 8 2 3 4 5 6 7 3 4 5 3 5 6 3 5 7 6 8 9 3 6 7 3 6 8 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 39
해시트리를사용한지지도계산 1 2 3 5 6 트랜잭션 해시함수 1 + 2 3 5 6 2 + 3 5 6 1,4,7 3,6,9 3 + 5 6 2,5,8 2 3 4 5 6 7 1 4 5 1 3 6 1 2 4 1 2 5 1 5 9 4 5 7 4 5 8 3 4 5 3 5 6 3 6 7 3 5 7 3 6 8 6 8 9 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 40
해시트리를사용한지지도계산 1 2 3 5 6 트랜잭션 해시함수 1 2 + 1 3 + 3 5 6 5 6 1 + 2 3 5 6 2 + 3 5 6 3 + 5 6 1,4,7 2,5,8 3,6,9 1 5 + 6 2 3 4 5 6 7 1 4 5 1 3 6 1 2 4 1 2 5 1 5 9 4 5 7 4 5 8 3 4 5 3 5 6 3 6 7 3 5 7 3 6 8 6 8 9 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 41
해시트리를사용한지지도계산 1 2 3 5 6 트랜잭션 해시함수 1 2 + 1 3 + 3 5 6 5 6 1 + 2 3 5 6 2 + 3 5 6 3 + 5 6 1,4,7 2,5,8 3,6,9 1 5 + 6 2 3 4 5 6 7 1 4 5 1 3 6 1 2 4 1 2 5 1 5 9 4 5 7 4 5 8 3 4 5 3 5 6 3 5 7 6 8 9 3 6 7 3 6 8 15개후보중에서 11개와트랜잭션매치 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 42
3. 연관규칙생성
규칙생성 빈발항목집합 L 이주어지면, f L f 가최소지지도요구사항을만족하도록비어있지않은모든부분집합 f L 을찾음 {A,B,C,D} 가빈발항목집합일때, 후보규칙 : ABC D, ABD C, ACD B, BCD A, A BCD, B ACD, C ABD, D ABC AB CD, AC BD, AD BC, BC AD, BD AC, CD AB, L = k 이면, 2k 2 개의후보결합규칙 (L 과 L 무시 ) 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 44
규칙생성 일반적으로신뢰도에는안티 - 모노톤 anti-monotone 속성이없음 c(abc D) 는 c(ab D) 보다크거나작을수있음 그러나동일항항목집합으로부터생성된규칙의신뢰도에는안티 - 모노톤속성이있음 예 : {A,B,C,D} 는빈발 4- 항목집합이라가정 : c(abc D) c(ab CD) c(a BCD) 신뢰도는규칙의 RHS 에있는항목의수와관련하여안티 - 모노톤 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 45
Apriori 알고리즘을위한규칙생성 규칙의격자 ABCD=>{ } 낮은신뢰규칙 BCD=>A ACD=>B ABD=>C ABC=>D CD=>AB BD=>AC BC=>AD AD=>BC AC=>BD AB=>CD 가지치기된규칙 D=>ABC C=>ABD B=>ACD A=>BCD 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 46
Apriori 복잡성에영향을미치는요인 최소지지도임계값선택 지지도임계값을낮추면항목집합의빈도가높아짐 후보의수와빈발항목집합의최대길이를증가시킬수있음 데이터집합의차원 ( 항목의수 ) 각항목의지지도횟수를저장하는데더많은공간필요 빈발항목의수가증가하면, 계산및입출력비용도증가할수있음 데이터베이스크기 Apriori 가다중패스 multiple passes 를하기때문에알고리즘의실행시간이트랜잭션의수에따라증가할수있음 평균트랜잭션너비 밀집한데이터집합과함께트랜잭션너비증가 빈발항목집합과해시트리의순회를증가시킬수있음 ( 트랜잭션의부분집합수는너비에따라증가 ) 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 47
Apriori 복잡성에영향을미치는요인 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 48
4. 빈발항목집합표현
빈발항목집합의간결한표현 일부항목집합은상위집합 supersets 과동일한지지도를가지기때문에중복 TID A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 15 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 빈발항목집합의수 간결한표현이필요 = 10 = 3 10 k 1 k 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 50
최대빈발항목집합Maximal Frequent Itemset 항목집합은자주발생하고바로자기상위집합의어느것도빈번하지않은경우최대빈도 null Maximal Itemsets A B C D E AB AC AD AE BC BD BE CD CE DE ABC ABD ABE ACD ACE ADE BCD BCE BDE CDE ABCD ABCE ABDE ACDE BCDE Infrequent Itemsets ABCD E Border 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 51
이데이터의최대빈발항목집합은무엇인가? TID A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 15 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 Minimum support threshold = 5 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 52
실제예제 Transactions 1 2 3 4 5 6 7 8 9 10 Items A B C D E F G H I J 지지도임계값 (by count) : 5 빈발항목집합 :? 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 53
실제예제 Transactions 1 2 3 4 5 6 7 8 9 10 Items A B C D E F G H I J 지지도임계값 (by count) : 5 빈발항목집합 : {F} 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 54
실제예제 Transactions 1 2 3 4 5 6 7 8 9 10 Items A B C D E F G H I J 지지도임계값 (by count) : 5 빈발항목집합 : {F} 지지도임계값 (by count) : 4 빈발항목집합 :? 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 55
실제예제 Transactions 1 2 3 4 5 6 7 8 9 10 Items A B C D E F G H I J 지지도임계값 (by count) : 5 빈발항목집합 : {F} 지지도임계값 (by count) : 4 빈발항목집합 : {E},{F},{E,F},{J} 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 56
실제예제 Transactions 1 2 3 4 5 6 7 8 9 10 Items A B C D E F G H I J 지지도임계값 (by count) : 5 빈발항목집합 : {F} 지지도임계값 (by count) : 4 빈발항목집합 : {E},{F},{E,F},{J} 지지도임계값 (by count) : 3 빈발항목집합 :? 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 57
실제예제 Transactions 1 2 3 4 5 6 7 8 9 10 Items A B C D E F G H I J 지지도임계값 (by count) : 5 빈발항목집합 : {F} 지지도임계값 (by count) : 4 빈발항목집합 : {E},{F},{E,F},{J} 지지도임계값 (by count) : 3 빈발항목집합 : {C,D,E,F}+{J} 의모든부분집합 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 58
실제예제 Transactions 1 2 3 4 5 6 7 8 9 10 Items A B C D E F G H I J 지지도임계값 (by count) : 5 빈발항목집합 : {F} 최대항목집합 :? 지지도임계값 (by count) : 4 빈발항목집합 : {E},{F},{E,F},{J} 최대항목집합 :? 지지도임계값 (by count) : 3 빈발항목집합 : {C,D,E,F}+{J} 의모든부분집합최대항목집합 :? 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 59
실제예제 Transactions 1 2 3 4 5 6 7 8 9 10 Items A B C D E F G H I J 지지도임계값 (by count) : 5 빈발항목집합 : {F} 최대항목집합 : {F} 지지도임계값 (by count) : 4 빈발항목집합 : {E},{F},{E,F},{J} 최대항목집합 :? 지지도임계값 (by count) : 3 빈발항목집합 : {C,D,E,F}+{J} 의모든부분집합최대항목집합 :? 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 60
실제예제 Transactions 1 2 3 4 5 6 7 8 9 10 Items A B C D E F G H I J 지지도임계값 (by count) : 5 빈발항목집합 : {F} 최대항목집합 : {F} 지지도임계값 (by count) : 4 빈발항목집합 : {E},{F},{E,F},{J} 최대항목집합 : {E,F},{J} 지지도임계값 (by count) : 3 빈발항목집합 : {C,D,E,F}+{J} 의모든부분집합최대항목집합 :? 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 61
실제예제 Transactions 1 2 3 4 5 6 7 8 9 10 Items A B C D E F G H I J 지지도임계값 (by count) : 5 빈발항목집합 : {F} 최대항목집합 : {F} 지지도임계값 (by count) : 4 빈발항목집합 : {E},{F},{E,F},{J} 최대항목집합 : {E,F},{J} 지지도임계값 (by count) : 3 빈발항목집합 : {C,D,E,F}+{J} 의모든부분집합최대항목집합 : {C,D,E,F},{J} 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 62
실제예제 Transactions 1 2 3 4 5 6 7 8 9 10 Items A B C D E F G H I J 지지도임계값 (by count) : 5 최대항목집합 : {A}, {B}, {C} 지지도임계값 (by count) : 4 최대항목집합 : {A,B},{A,C},{B,C} 지지도임계값 (by count) : 3 최대항목집합 : {A,B,C} 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 63
닫힌항목집합Closed Itemset 항목집합 X 의상위집합중어느것도 X 와동일한지지도횟수를가지지않으면, 항목집합 X 는닫혀있음 직접상위집합중적어도하나이상에 X 의지지도횟수를가지면 X 는닫히지않음 TID Items 1 {A,B} 2 {B,C,D} 3 {A,B,C,D} 4 {A,B,D} 5 {A,B,C,D} Itemset Support {A} 4 {B} 5 {C} 3 {D} 4 {A,B} 4 {A,C} 2 {A,D} 3 {B,C} 3 {B,D} 4 {C,D} 3 Itemset Support {A,B,C} 2 {A,B,D} 3 {A,C,D} 2 {B,C,D} 2 {A,B,C,D} 2 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 64
최대 Maximal vs 닫힌항목집합Closed Itemsets TID Items 1 ABC 2 ABCD 3 BCE 4 ACDE 5 DE null Transaction Ids 124 123 1234 245 345 A B C D E 12 124 24 4 123 2 3 24 34 45 AB AC AD AE BC BD BE CD CE DE 12 2 24 4 4 2 3 4 ABC ABD ABE ACD ACE ADE BCD BCE BDE CDE 2 4 ABCD ABCE ABDE ACDE BCDE Not supported by any transactions ABCDE 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 65
최대 Maximal vs 닫힌항목집합Closed Itemsets Minimum support = 2 null Closed but not maximal 124 123 1234 245 345 A B C D E Closed and maximal 12 124 24 4 123 2 3 24 34 45 AB AC AD AE BC BD BE CD CE DE 12 2 24 4 4 2 3 4 ABC ABD ABE ACD ACE ADE BCD BCE BDE CDE 2 4 ABCD ABCE ABDE ACDE BCDE # Closed = 9 # Maximal = 4 ABCDE 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 66
이데이터의닫힌항목집합은무엇인가? TID A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 15 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 67
예제 1 Transactions Items 1 2 3 4 A B C D E F G H I J Itemsets {C} 3 {D} 2 {C,D} 2 Support (counts) Closed itemsets 5 6 7 8 9 10 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 68
예제 1 Transactions Items 1 2 3 4 A B C D E F G H I J Itemsets Support (counts) {C} 3 {D} 2 {C,D} 2 Closed itemsets 5 6 7 8 9 10 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 69
예제 2 Transactions Items 1 2 3 4 5 6 7 8 A B C D E F G H I J Itemsets {C} 3 {D} 2 {E} 2 {C,D} 2 {C,E} 2 {D,E} 2 {C,D,E} 2 Support (counts) Closed itemsets 9 10 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 70
예제 2 Transactions Items 1 2 3 4 5 6 7 8 A B C D E F G H I J Itemsets Support (counts) {C} 3 {D} 2 {E} 2 {C,D} 2 {C,E} 2 {D,E} 2 {C,D,E} 2 Closed itemsets 9 10 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 71
예제 3 Transactions 1 2 3 4 5 6 7 8 9 10 Items A B C D E F G H I J Closed itemsets: {C,D,E,F}, {C,F} 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 72
예제 4 Transactions 1 2 3 4 5 6 7 8 9 10 Items A B C D E F G H I J Closed itemsets: {C,D,E,F}, {C}, {F} 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 73
최대 Maximal vs 닫힌항목집합Closed Itemsets Frequent Itemsets Closed Frequent Itemsets Maximal Frequent Itemsets 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 74
예제질문 트랜잭션데이터집합 ( 어두운셀은트랜잭션에서항목이있음을나타냄 ) 과 20% 지지도임계값이주어진다면, 다음질문에답하시오 각데이터집합의빈항목집합의수? 어떤데이터집합이가장자주항목집합을생성하나? 어떤데이터집합이가장빈번하게항목집합을생성하나? 어떤데이터집합이최대지지도가가장높은빈발항목집합을생성하나? 어떤데이터집합이다양한지원수준 ( 즉, 20% 에서 70% 이상까지범위의지지도를갖는항목을포함하는항목집합 ) 을포함하는빈발항목집합을생성하나? 각데이터집합에대한최대빈발항목집합의수? 어떤데이터집합이최대빈발항목집합을생성하나? 각데이터집합에대해닫힌빈발항목집합의수? 어떤데이터집합이닫힌빈발항목집합을가장많이생성하나? 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 75
5. 연관패턴평가
패턴평가Pattern Evaluation 연관규칙알고리즘은많은수의규칙을생성할수있음 유용성척도 Interestingness Measures 를사용하여패턴을잘라내거나순위를매길수있음 원래공식에서사용된유일한척도는지지도와신뢰도 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 77
유용성척도 Interestingness Measures 계산 주어진 X Y 또는 {X,Y}, 유용성을계산하는데필요한정보는분할표 contingency table 에서얻을수있음 분할표 Y Y X f 11 f 10 f 1+ X f 01 f 00 f o+ f +1 f +0 N f 11 : support of X and Y f 10 : support of X and Y f 01 : support of X and Y f 00 : support of X and Y 다양한측정값을정의하는데사용 support, confidence, Gini, entropy, etc. 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 78
신뢰도의결점 Custo mers Tea Coffee C1 0 1 C2 1 0 C3 1 1 C4 1 0 Association Rule: Tea Coffee Coffee Coffee Tea 15 5 20 Tea 75 5 80 90 10 100 Confidence P(Coffee Tea) = 15/20 = 0.75 Confidence > 50%, 차를마시는사람들은커피를마시지않는것보다커피를마시는경향이있음을의미 규칙은합리적으로보임 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 79
신뢰도의결점 Coffee Coffee Tea 15 5 20 Tea 75 5 80 90 10 100 Association Rule: Tea Coffee Confidence= P(Coffee Tea) = 15/20 = 0.75 그러나 P(Coffee) = 0.9, 이는사람이차를마시는것이사람이커피를마실가능성을줄인다는것을의미 P(Coffee Tea) ` = 75/80 = 0.9375 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 80
연관규칙측정 우리가정말로원하는규칙은무엇인가? 신뢰도 (X Y) 는충분히높아야함 X 를사는사람들이 Y 를사지않는것보다 Y 를살가능성을높이기위해 신뢰도 (X Y) > 지지도 (Y) 그렇지않으면규칙 X가실제로동일한트랜잭션에서항목 Y를가질기회를줄이므로규칙이오해가됨 이제한을포착하는어떤측정이있는가? 답변 : 많이있음 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 81
통계적독립성Statistical Independence 기준 confidence(x Y) = support(y) 는다음과같음 : P(Y X) = P(Y) P(X,Y) = P(X) P(Y) If P(X,Y) > P(X) P(Y) : X & Y 는양의상관관계가있음 If P(X,Y) < P(X) P(Y) : X & Y 는음의상관관계가있음 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 82
통계적의존성을고려한측정 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 83 )] ( )[1 ( )] ( )[1 ( ) ( ) ( ), ( ) ( ) ( ), ( ) ( ) ( ), ( ) ( ) ( Y P Y P X P X P Y P X P Y X P coefficient Y P X P Y X P PS Y P X P Y X P Interest Y P X Y P Lift = = = = 항목집합에관심이있는동안리프트 lift 가규칙에사용
예제 : Lift/Interest Coffee Coffee Tea 15 5 20 Tea 75 5 80 90 10 100 Association Rule: Tea Coffee 신뢰도 = P(Coffee Tea) = 0.75 그러나 P(Coffee) = 0.9 Lift = 0.75/0.9= 0.8333 (< 1, 따라서부정적으로연관됨 ) 그래서가지치기를위해 confidence/lift를사용하는것으로충분한가? 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 84
Lift 또는 Interest Y Y X 10 0 10 X 0 90 90 10 90 100 Y Y X 90 0 90 X 0 10 10 90 10 100 0.1 Lift = = 10 0.9 Lift = = 1. 11 (0.1)(0.1) (0.9)(0.9) 통계적독립성 : If P(X,Y)=P(X)P(Y) => Lift = 1 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 85
문헌에제시된많은측정법 데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 86
데이터전처리 (Data Preprocessing) - 09 연관분석 (Association Analysis) 87