frequent pattern analysis


frequent pattern analysis
frequent pattern/itemset:在data set中常出現的頻率
ex:a set of item,subsequences,substructures
目地:找出資料固定的規則
應用:basket data analysis,cross-marketing(市場交互情形),catalog design(產品搭配的設計),...等


基本概念
找出x,y的minimum support和confidence
support:x,y同時發生的比率
confidence x=>y: x發生時,y發生的比例

主要步驟
1.find all frequent itemset:
frequently需大於minimum support
2.generate strong association rule from the frequent itemset
需滿足minimum support和minimum confidence
(option)3.correlation analysis for association rule

................................................................................................................................
 
1.find all frequent itemset

常見的scalable mining method如下
apriori:簡單的方法,但耗時,因為要比較candidate,而且要一直scan
FPgrowth:計算快速,因為不用產生candidate,而且scan僅需一次
vertical data format approach:將欄與列轉換,方法簡單,比apriori快

.....

apriori
方法致如下
1.scan:計算每個itemset support,得到Cn
2.compare:各itemset(candidate) support和mini support比較,以得到Ln
3.根據Ln產生Cn+1
4.重覆1-3直到結束

apriori做法範例
id: items
a: 1,2,5
b: 2,4
c: 2,3
d: 1,2,4
e: 1,3
f: 2,3
g: 1,3
h: 1,2,3,5
i: 1,2,3
itemset mini support=2,or 22%(=2/9)
產生l3如下
 C1:scan
itemset : sup
1 : 6 
2 : 7
3 : 6
4 : 2 
5 : 2 
L1:大於min sup之candidate
itemset : sup
1 : 6 
2 : 7
3 : 6
4 : 2 
5 : 2 
generate C2
itemset
1,2
1,3
1,4
1,5
2,3
2,4
2,5
3,4
3,5
4,5  
 C2:scan
itemset : sup
1,2 : 4
1,3 : 4
1,4 : 1(小於min support)
1,5 : 2
2,3 : 4
2,4 : 2
2,5 : 2 
3,4 : 0(小於min support)
3,5 : 1(小於min support)
4,5 : 0(小於min support) 
L2:大於min sup之candidate
itemset : sup
1,2 : 4
1,3 : 4
1,5 : 2
2,3 : 4
2,4 : 2
2,5 : 2 
generate C3
itemset
1,2,3
1,2,5
1,3,5(因3,5:1所以不用)
2,3,5(因3,5:1所以不用)
2,3,4(因3,4:0所以不用)
2,4,5(因4,5:0所以不用)  
C3:scan
itemset : sup
1,2,3 : 2
1,2,5 : 2  
L3:大於min sup之candidate
itemset : sup
1,2,3 : 2
1,2,5 : 2 
generage C4
itemset
1,2,3,5  
C4:scan
itemset : sup
1,2,3,5: 1(小於min support)  
L4:大於min sup之candidate
itemset : sup 
so
L3 {1,2,5*2} {1,2,3*2}
L2 {2,5*2},{1,5*2},{2,4*2} ,{2,3*4},{1,3*4},{1,2*4} 

.....

FPgrowth
方法大致如下
1,compute support and sort by support
2,refresh by step1 result
3,create tree by step2 result
4,conditional pattern base => frequent patterns generated

FPgrowth做法範例
id: items
a: 1,2,5
b: 2,4
c: 2,3
d: 1,2,4
e: 1,3
f: 2,3
g: 1,3
h: 1,2,3,5
i: 1,2,3
itemset mini support=2,or 22%(=2/9)

1
compute support(若有小於support則將他排除) and sort by support
itemset : sup
2 : 7
1 : 6
3 : 6
4 : 2
5 : 2

2
refresh by step1 result
a: 2,1,5
b: 2,4
c: 2,3
d: 2,1,4
e: 1,3
f: 2,3
g: 1,3
h: 2,1,3,5
i: 2,1,3

3
create tree by step2 result
null
|_2(7)
| |_1(4) (1 base 2*1)
| | |_5(1) [a=2,1,5] (5 base 2,1*1)
| | |_3(2) [i=2,1,3] (3 base 2,1*2)
| | | |_5(1) [h=2,1,3,5] (5 base 2,1,3*1)
| | | 
| | |_4(1) [d=2,1,4] (4 base 2,1*1)
| | 
| |_3(2) [c,f=2,3] (3 base 2*2)
| |_4(1) [b=2,4] (4 base 2*1)
| 
|_1(2)
 |_3(2) [g,e=1,3] (3 base 1*2)


4
conditional pattern base => frequent patterns generated
5 ((2,1*1),(2,1,3*1)) => {2,5*2},{1,5*2},{2,1,5*2} //{3,5*1} 小於mini sup
4 ((2,1*1),(2*1)) => {2,4*2} //{2,1*1} 小於mini sup
3 ((2,1*2),(2*2),(1*2)) => {2,3*4},{1,3*4},{2,1,3*2}
1 (2*4) => {2,1*4}

so
L3 {2,1,5*2} {2,1,3*2}
L2 {2,5*2},{1,5*2},{2,4*2} ,{2,3*4},{1,3*4},{2,1*4}

.....

vertical data format approach
方法大致如下
1欄列轉換
2將前一步驟未小於min support的值做組合並交集

vertical data format approach做法範例
id: items
a: 1,2,5
b: 2,4
c: 2,3
d: 1,2,4
e: 1,3
f: 2,3
g: 1,3
h: 1,2,3,5
i: 1,2,3
itemset mini support=2,or 22%(=2/9)

1
欄列轉換
itemset : sup
1:a,d,e,g,h,i
2:a,b,c,d,f,h,i
3:c,e,f,g,h,i
4:b,d
5:a,h

2
將前一步驟未小於min support的值做組合並交集
12:a,h,i
13:e,g,h,i
14:d  (小於min support)
15:a,h
23:c,f,h,i
24:b,d
25:a,h

34:  (小於min support)
35:h (小於min support)
45:  (小於min support)

3
將前一步驟未小於min support的值做組合並交集
1,2,3:h,i
1,2,5:a,h

1,3,5:h (因3,5:0所以不用)
2,3,4: (因3,4:0所以不用)
2,3,5: (因3,5:0所以不用)
2,4,5: (因4,5:0所以不用)

so
L3 {2,1,5*2} {2,1,3*2}
L2 {2,5*2},{1,5*2},{2,4*2} ,{2,3*4},{1,3*4},{2,1*4}

 

...........................................................................................................................

 

2.generate strong association rule from the frequent itemset
x=>y(confidence): confidence=x發生時,y發生的比例

 

做法範例(if confidence threshold is 70%,support as above)
{2,5*2} 2=>5(2/7) ; 5=>2(2/2=100%>70%) 
{1,5*2} 1=>5(2/6) ; 5=>1(2/2 =100%>70%)
{2,4*2} 2=>4(2/7) ; 4=>2(2/2=100%>70%)
{2,3*4} 2=>3(4/7) ; 3=>2(4/6)
{1,3*4} 1=>3(4/6) ; 3=>1(4/6)
{2,1*4} 1=>2(4/6) ; 2=>1(4/7)
{2,1,5*2}
 1^2=>5(2/4=50%)
 1^5=>2(2/2=100%>70%)
 2^5=>1(2/2=100%>70%)
 1=>2^5(2/6=33%)
 2=>1^5(2/7=29%)
 5=>1^2(2/2=100%>70%)
{2,1,3*2}
 1^2=>3 ,
 1^3=>2
 2^3=>1 ,
 1=>2^3 ,
 2=>1^3 ,
 3=>1^2 ,

結果可寫成以下
x=>y(support,confidence)
5=>2(40%,100%) 
5=>1(40%,100%)
4=>2(40%,100%)

 

............................................

找出各種association rules
常見有以下
mining multilevel association,
mining multidimensional association
mining quantitave association
mining interesting correlation patterns


mining multilevel association,
各層support計算方式主要分為兩種
 uniform support:每一層都用相同的support
 reduced support:越下層用越少的support
ex:第一層virus[sup=10%],第二層可分為file virus[sup=4%]和boot virus[sup=6%]
uniform support=5%,則第二層file virus[sup=4%]則不被找到
reduced support,第一層=5%,第二層=3%,即可全部找到

mining multidimensional association
主要分兩種rule
inter-dimension association rules(no repeated) ex:age(20-30)^job(student)=>buy(coke)
hybrid-dimension association rule(repeated) ex:age(20-30)^buy(pizza)=>buy(coke)

mining quantitave association
1將數值先切割成各段
2找出association
ex:age(20)^income(10-20k)=>buy(pc)

............................................................................................................................

 

(option)3.correlation analysis for association rule 

 

只靠support及confidence有時不夠,因此有時會加correlation
ex:
假設在10000筆購買記錄中,買computer有6000人,買lcd有7500人,兩者同時買有4000人
且min support=30%,min confidence=60%
假如發現以下association rule
buy(computer)=>buy(lcd)[support=40%,confidence=66%]
買computer的人,會有66%買lcd
但是因為根據購買記錄可以看到,買lcd機率為75%,所以該association rule沒有幫助

 

常見的correlation measures有
chi-squre
lift
all_conf,較適合用於association rule
coh,較適合用於association rule


假設virus和p2p的contingency table如下
 virus no virus sum 
p2p  v,p (100) !v,p (200 ) p (300)
no p2p  v,!p (300) !v,!p (400) !p (700)
 sum v (400)  !v (600) total (1000)

lift(A,B)=p(A交集B)/p(A)*p(B)
lift(v,p)=(v,p/total)/((v/total)*(p/total))=(100/1000)/((400/1000)*(300/1000))=0.83
lift(v,!p)=(v,!p/total)/((v/total)*(!p/total))=(300/1000)/((400/1000)*(700/1000))=1.07

all_conf(X)=sup(X)/max_item_sup(X)
all_conf(v)=v,p/max(v)=100/max(400,300)=100/400=0.25
小於0.5,表示不獨立

coh(x)=sup(X)/|universe(X)|
coh(v)=v,p/(v,p+!v,p+v,!p)=100/100+300+200=100/600=0.20
小於0.5,表示不獨立

cosine =(100/1000) /(sqrt(400/1000)+sqrt(300/1000))=0.0847


ps:
在min support方面
virus,p2p = 100/1000=10%
virus = 400/1000 =40%
p2p = 300/1000=30%
ps:
在min confidence方面
virus=>p2p( 100/400=25% )
p2p=>virus(100/300 =33%)

2012-12-16 18:14:50發表 2013-01-20 18:35:49修改   

數據分析

程式開發
計算機組織與結構
資料結構與演算法
Database and MySql
manage tool
windows
unix-like
linux service
network
network layer3
network layer2
network WAN
network service
作業系統
數位鑑識
資訊安全解決方案
資訊安全威脅
Cisco security
Cisco network
Cisco layer3
Cisco layer2



  登入      [牛的大腦] | [單字我朋友] Powered by systw.net