Data Mining Association Analysis: Basic Concepts and Algorithms Lecture Notes for Chapter 7 1
Contents 범주형 / 연속형속성처리 2
10 범주형 / 연속형속성 지금까지 asymmetric binary variables 에대한연관분석을공부함 이제 categorical / continuous attribute 에적용필요함 Session Id Country Session Length (sec) Number of Web Pages viewed Gender Browser Type Buy 1 USA 982 8 Male IE No 2 China 811 10 Female Netscape No 3 USA 2125 45 Female Mozilla Yes 4 Germany 596 4 Male IE Yes 5 Australia 123 9 Male Mozilla No Example of Association Rule: {Number of Pages [5,10) (Browser=Mozilla)} {Buy = No}
범주형 / 연속형속성 실제연관규칙이적용되는데이터베이스레코드는범주형혹은연속형속성이많음 범주형속성 (Categorical Attributes) 속성의값이범주 (category) 로나타나는경우를일컬음 예제 : 성별, 전공, 특기 연속형속성 (Continuous Attributes) 속성의값이숫자로나타나는경우를일컬음 예제 : 나이, 몸무게, 연봉 Page 4
범주형속성처리 범주형속성을 Asymmetric binary 변수로변환함 Binary variable has only two states: 0 or 1 A binary variable is symmetric if both of its states are equally valuable, that is, there is no preference on which outcome should be coded as 1. A binary variable is asymmetric if the outcome of the states are not equally important, such as positive or negative outcomes of a disease test. Introduce a new item for each distinct attribute-value pair Example: replace Browser Type attribute with Browser Type = Internet Explorer Browser Type = Mozilla Browser Type = Mozilla Page 5
범주형속성처리예제 Page 6
범주형속성처리 주요이슈 만일, 범주형속성이매우많은값을가진다면? Example: attribute country has more than 200 possible values 많은속성값은매우적은 support 값을가질수있음 해결책 : Aggregate the low-support attribute values 만약속성값분포가한쪽으로심하게편향되었다면 ( highly skewed)? Example: 95% of the visitors have Buy = No. Most of the items will be associated with (Buy=No) item 해결책 : 매우빈발한항목은 drop 함. 즉, 매우많은빈도수를가지는항목은새로운정보를가지지않기때문
연속형속성처리 데이터에는당연히연속형속성도있음 예 : Age [21,35) Salary [70k,120k) Buy Salary [70k,120k) Buy Age: =28, =4 연속형속성을처리하는방법 이산화기반 (Discretization-based) 방법 통계기반 (Statistics-based) 방법 Non-discretization 기법 Min-Apriori 기법 Page 8
연속형속성처리예제 Page 9
이산화 (Discretization) 기반방법 이산화기반방법에는 Unsupervised 방법과 supervised 방법존재함 비감독 (unsupervised) 방법 Equal-width binning Equal-depth binning Clustering 감독 (supervised) 방법 Page 10
이산화 (Discretization) 기반방법 Size of the discretized intervals affect support & confidence {Refund = No, (Income = $51,250)} {Cheat = No} {Refund = No, (60K Income 80K)} {Cheat = No} {Refund = No, (0K Income 1B)} {Cheat = No} If intervals too small may not have enough support If intervals too large may not have enough confidence Potential solution: use all possible intervals
이산화 (Discretization) 기반방법 Execution time 만약범위가 k 구간으로나눠진다면 k(k-1)/2 의이진항목들이모든가능한구간을나타내기위해생성되어야함 많은비용소비됨 Too many rules {Refund = No, (Income = $51,250)} {Cheat = No} {Refund = No, (51K Income 52K)} {Cheat = No} {Refund = No, (50K Income 60K)} {Cheat = No}
통계기반방법, Min-Apriori 기법 통계기반방법 정량적연관규칙은모집단의통계적특성을추론하는데사용가능 연관규칙의결론부가통계적속성 ( 평균, 표준편차등 ) 을갖는연속형속성으로나타남 예제 : Salary [70k,120k) Buy Age: =28, =4 Min-Apriori 기법 ( 비이산화방법 ) 연속형속성들중에서연관성을찾는방법 단어들사이의연관성등 Page 13
통계기반방법 사례 : Browser=Mozilla Buy=Yes Age: =23 연관규칙의결론부는통계적속성을가짐 mean, median, standard deviation, etc. 규칙생성방법 : 먼저, target variable 를정한후, 이를나머지데이터와별도로생각함 분리된 나머지데이터 에대해서 frequent itemset 을찾음 나머지데이터 로부터찾은 frequent itemset 을사용하여, target variable 에대한통계적속성을찾음 {Annual Income > $100K, Shop Online = Yes} Age: Mean = 38 이규칙은인터넷사용자의연수입이 10 만달러보다많고정기적으로온라인쇼핑을하는사람의평균나이는 38 세라는것을말함 해당연관규칙의정당성을확인하기위해통계테스트수행 ( 가설검증등 )
통계기반방법 연관규칙유용성테스트 연관규칙에포함되는트랜잭션으로부터계산된통계량이해당규칙에포함되지않은트랜잭션으로부터계산된것과다른경우에만해당연관규칙은유용함 Compare the statistics for segment of population covered by the rule vs segment of population not covered by the rule: 통계적가설검증 (Statistical hypothesis testing): 귀무가설 (Null hypothesis): H0: = + A B: μ vs. ഥA B: μ 대립가설 (Alternative hypothesis): H1: > + Z has zero mean and variance 1 under null hypothesis A 는 frequent itemset, B 는연속형 target 속성 n1 은 A 를지지하는트랜잭션수, n2 는 A 를지지하지않는트랜잭션수 s1 은 A 를지지하는트랜잭션중에서 B 에대한표준편자, s2 는 A 를지지하지않는트랜잭션중에서 B 에대한표준편차 Z ' 2 2 s1 s2 n n 1 2
통계기반방법 통계적가설검증 ( 계속 ) A B: μ vs. ഥA B: μ μ 와 μ 의차이가어떤사용자 ~ 지정된임계값 보다더큰가? 를검사함 통계적가설검증에서귀무가설과대립가설, 두개의반대되는명제가주어짐 ( 일반적으로귀무가설을기각하고대립가설을채택하기위해선귀무가설이잘못되었다는것을입증함 ) 데이터로부터수집된증거에근거하여가설검증은위두개의가설중에서어느것이수락되어야하는지를결정함 이경우, μ < μ 을가정하면, 귀무가설 H0: μ = μ + 이며, 대립가설 H1: μ > μ + 임. 여기서어느가설이수락되어야하는지를결정하기위해아래의 Z 통계량을계산함 Z ' 2 2 s1 s2 n n 1 2 Z 는평균 0 과분산 1 을갖는표준정규분포 계산된 Z 의값은기각값 (critical value) Za 와대조 / 비교함. 기각값은신뢰도수준에따라결정됨 만약 Z > Za 이면귀무가설기각됨 위의정량적연관규칙은유용하다고결론내림 아니면, 평균에서차이가통계적으로유의미하다는것을보여주기위한충분한증거가데이터에없음을의미함
통계기반방법 사례 : 연관규칙 : Browser=Mozilla Buy=Yes Age: =23 Rule is interesting if difference between and is greater than 5 years (i.e., = 5) For r, suppose n1 = 50, s1 = 3.5 For r (complement): n2 = 250, s2 = 6.5 Z ' 2 2 s1 s2 n n 1 2 30 23 5 2 2 3.5 6.5 50 250 3.11 For 1-sided test at 95% confidence level, critical Z-value for rejecting null hypothesis is 1.64. Since Z is greater than 1.64, r is an interesting rule
Min-Apriori (Han et al) Data set 이연속형속성 (continuous attribute) 을가지는경우에적용가능 특히연속형속성들간의연관성을찾고자하는경우사용 사례 : 텍스트문서에서단어연관성을찾는문제 문서 - 단어행렬 (Document-term matrix) 에서각엔트리는주어진문서에서나타나는단어의정규화빈도수카운트값을의미함 TID W1 W2 W3 W4 W5 D1 2 2 0 0 1 D2 0 0 1 2 2 D3 2 3 0 0 0 D4 0 0 1 0 1 D5 1 1 1 0 2 W1 and W2 tends to appear together in the same document
Min-Apriori 아래의 문서 - 단어행렬 을다음과같이변경함 위 문서 - 단어행렬 을 0/1 matrix 로변형한후, 기존의알고리즘적용 기존의알고리즘은 binary variable 에적용되는것이었음 단어간연관성을찾고자함 TID W1 W2 W3 W4 W5 D1 2 2 0 0 1 D2 0 0 1 2 2 D3 2 3 0 0 0 D4 0 0 1 0 1 D5 1 1 1 0 2
Min-Apriori 단어간연관성찾을수있음 If we simply sum up its frequency, support count will be greater than total number of documents! Normalize the word vectors e.g., using L 1 norm Each word has a support equals to 1.0 TID W1 W2 W3 W4 W5 D1 2 2 0 0 1 D2 0 0 1 2 2 D3 2 3 0 0 0 D4 0 0 1 0 1 D5 1 1 1 0 2 Normalize TID W1 W2 W3 W4 W5 D1 0.40 0.33 0.00 0.00 0.17 D2 0.00 0.00 0.33 1.00 0.33 D3 0.40 0.50 0.00 0.00 0.00 D4 0.00 0.00 0.33 0.00 0.17 D5 0.20 0.17 0.33 0.00 0.33 각 word 갯수로 normalize 함
Min-Apriori New definition of support: sup( C ) mind( i, j) i T j C TID W1 W2 W3 W4 W5 D1 0.40 0.33 0.00 0.00 0.17 D2 0.00 0.00 0.33 1.00 0.33 D3 0.40 0.50 0.00 0.00 0.00 D4 0.00 0.00 0.33 0.00 0.17 D5 0.20 0.17 0.33 0.00 0.33 Example: Sup(W1,W2,W3) D1 = min (0.40, 0.33, 0.00) + min(0.00, 0.00, 0.33) + +min(0.20, 0.17, 0.33) = 0 + 0 + 0 + 0 + 0.17 = 0.17 D5 D2
Min-Apriori Min-Apriori에서의정의된지지도척도는문서에서단어연관성을찾는데적합한아래의특성가짐 한단어의정규화지지도가증가함에따라지지도는단조형증가 그단어를포함하는문서개수가증가함에따라지지도단조형증가 지지도는비단조형특성가짐 예를들어 itemset {A,B} 와 {A,B,C} 가있다면, min({a,b}) >= min({a,b,c}) 이므로 s({a,b}) >= s({a,b,c}) 임 (itemset에속한단어수가증가하면최소값을찾기때문에지지도는감소할수밖에없음 )
Anti-monotone property of Support Example: TID W1 W2 W3 W4 W5 D1 0.40 0.33 0.00 0.00 0.17 D2 0.00 0.00 0.33 1.00 0.33 D3 0.40 0.50 0.00 0.00 0.00 D4 0.00 0.00 0.33 0.00 0.17 D5 0.20 0.17 0.33 0.00 0.33 Sup(W1) = 0.4 + 0 + 0.4 + 0 + 0.2 = 1 Sup(W1, W2) = 0.33 + 0 + 0.4 + 0 + 0.17 = 0.9 Sup(W1, W2, W3) = 0 + 0 + 0 + 0 + 0.17 = 0.17 Itemset 에속한단어증가시 support 값줄어드는특성확인
Contents 다단계연관규칙 24
개념계층 (Concept Hierarchy) 개념계층 : 특정한영역에서정의된여러개체들또는개념들의다중계층조직임. Concept hierarchy 는 specific 한데이터가상위레벨에서추상화되므로분류에서의미가있을수있음 주로, is-a 관계를구성하는 taxonomy 형식을가짐 Milk 는 food 의한종류. DVD 는 electronics 의한종류등 개념계층은 directed acyclic graph 로표현됨 Page 25
개념계층 (Concept Hierarchy) 개념계층을연관분석에사용하는경우의주된특성 ( 장단점 ) 계층의더낮은레벨에있는항목들은어떤 frequent itemset 을나타내기위해충분한 support 를가지지않을수도있다. 개념계층을사용하지않으면이들의유용한패턴을놓칠수있음 그런데, 개념계층의상위레벨규칙은유용하지않을수도있음. 예를들어, (electronics food) 는고객의실구매성향에대한정보를주지않음 Page 26
다단계연관규칙마이닝 (1/4) 개념계층을연관분석에사용하는경우의주된특성 ( 장단점 ) 더높은레벨에있는항목들은더낮은레벨에있는항목보다더높은지지도를가지는경향있음 이에, 만약지지도임계값을너무높게두면단지높은레벨항목들을수반하는패턴만추출됨 개념계층의도입은더많은항목과더넓은트랜잭션을다루는일이되므로연관분석알고리즘의계산시간을늘임 개념계층의도입에의해중복된규칙들이산출될수있음 Page 27
다단계연관규칙마이닝 (2/4) 기본성질 : 개념계층에의해지지도 / 신뢰도는어떻게변하나? If then (X1 Y1) minsup, and X is parent of X1, Y is parent of Y1 (X Y1) minsup, (X1 Y) minsup, (X Y) minsup If then conf(x1 Y1) minconf conf(x1 Y) minconf ( X1 Y1) conf ( X1 Y1) ( X1) ( X1 Y) conf ( X1 Y) ( X1) Page 28
다단계연관규칙마이닝 (3/4) 접근법 1 상위계층의항목들을각트랜잭션에추가하고, 기존알고리즘을사용하여연관룰을만든다 예제 Original Transaction: {skim milk, wheat bread} Augmented Transaction: {skim milk, wheat bread, milk, bread, food} 이슈 상위계층항목은다른항목들에비해서높은지지도카운트를가짐 만일, 주어진지지도 threshopld( 즉, min supp) 가낮다면너무많은규칙들이생성될 것이다. 즉, 트랜잭션의차원이높아지는문제가있음 Page 29
다단계연관규칙마이닝 (4/4) 접근법 2 먼저최상위계층에서빈발항목집합을생성한후, 다음으로그아래계층에서빈발항목집합을생성 위과정을 만족할만한정도의의미있는규칙 을찾을때까지반복한다. 이슈 많은 I/O가필요하여마이닝시간이무척많이걸리게된다. 교차-단계의연관규칙을찾지못할수있다. ( 예를들어, 가정부는상위계층, 결론부는하위계층인연관규칙을찾지못할수있다.) Page 30
Contents 순차패턴 31
시퀀스데이터 (Sequence Data) Row 에주어진시간에특정객체와연관된사건발생을기록함 Page 32
시퀀스데이터예제 Page 33
시퀀스의정의 시퀀스란원소 ( 혹은트랜잭션 ) 들의순서리스트이다. (A sequence is an ordered list of elements (transactions)) 각원소는사건 ( 혹은항목 ) 들의모임을포함한다 각원소는특정시간혹은장소를속성으로가질수있다. 시퀀스의길이 s 는시퀀스에포함된원소의개수이다. ( s = the number of elements of the sequence s) k-시퀀스 (k-sequence) 란 k개사건 ( 항목 ) 을포함하는시퀀스이다. (A k-sequence is a sequence that contains k events (items)) Page 34
시퀀스의예제 웹시퀀스 (Web Sequence) < {Homepage} {Electronics} {Digital Cameras} {Canon Digital Camera} {Shopping Cart} {Order Confirmation} {Return to Shopping} > 도서관에서대여된책들의순서 <{Fellowship of the Ring} {The Two Towers} {Return of the King}> Page 35
서브시퀀스정의와순차패턴 시퀀스내에포함된시퀀스를서브시퀀스라부른다. Definition: A sequence <a1 a2 an> is contained in another sequence <b1 b2 bm> (m n) if there exist integers i1 < i2 < < in such that a1 bi1, a2 bi1,, an bin 서브시퀀스 w의지지도는 w를포함하는시퀀스의비율을나타냄 (The support of a subsequence w is defined as the fraction of data sequences that contain w) 순차패턴 (sequential pattern) 는빈발서브시퀀스 ( 지지도가 minsup 이상인서브시퀀스 ) 를의미함 (A sequential pattern is a frequent subsequence (i.e., a subsequence whose support is minsup) Page 36
순차패턴마이닝정의 다음이주어졌을때 시퀀스들로구성된데이터베이스 사용자가제시한최소지지도 minsup 다음작업을수행하라. 지지도가 minsup 이상인모든서브시퀀스를찾아라. Page 37
순차패턴마이닝예제 Page 38
순차패턴마이닝방법 Apriori 원리를활용 Page 39
시간제약요건 ms: Maximum span The maximum allowed time difference between the earliest event and the latest event in the entire sequence. ng: Min-gap The minimum allowed time difference between two consecutive elements in a sequence xg: Maxgap The maximum allowed time difference between two consecutive elements in a sequence ws: Window Size The maximum allowed time difference of the latest and earliest occurrences of events in any element of a sequential pattern. If, ws=0 all events in the same element of a pattern must occur simultaneously Page 40