{"id":457,"date":"2012-12-16T20:03:00","date_gmt":"2012-12-16T12:03:00","guid":{"rendered":"http:\/\/note.systw.net\/note\/?p=457"},"modified":"2023-11-02T20:05:09","modified_gmt":"2023-11-02T12:05:09","slug":"frequent-pattern-analysis","status":"publish","type":"post","link":"https:\/\/systw.net\/note\/archives\/457","title":{"rendered":"Frequent Pattern Analysis"},"content":{"rendered":"\n

frequent pattern analysis<\/strong>
frequent pattern\/itemset:\u5728data set\u4e2d\u5e38\u51fa\u73fe\u7684\u983b\u7387
ex:a set of item,subsequences,substructures
\u76ee\u5730:\u627e\u51fa\u8cc7\u6599\u56fa\u5b9a\u7684\u898f\u5247
\u61c9\u7528:basket data analysis,cross-marketing(\u5e02\u5834\u4ea4\u4e92\u60c5\u5f62),catalog design(\u7522\u54c1\u642d\u914d\u7684\u8a2d\u8a08),…\u7b49<\/p>\n\n\n\n


\u57fa\u672c\u6982\u5ff5<\/strong>
\u627e\u51fax,y\u7684minimum support\u548cconfidence
support:x,y\u540c\u6642\u767c\u751f\u7684\u6bd4\u7387
confidence x=>y: x\u767c\u751f\u6642,y\u767c\u751f\u7684\u6bd4\u4f8b<\/p>\n\n\n\n

\u4e3b\u8981\u6b65\u9a5f
1.find all frequent itemset:<\/strong>
frequently\u9700\u5927\u65bcminimum support
2.generate strong association rule from the frequent itemset<\/strong>
\u9700\u6eff\u8db3minimum support\u548cminimum confidence
(option)3.correlation analysis for association rule<\/strong><\/p>\n\n\n\n

………………………………………………………………………………………………………………..<\/p>\n\n\n\n

1.find all frequent itemset<\/strong><\/h2>\n\n\n\n

\u5e38\u898b\u7684scalable mining method\u5982\u4e0b
apriori:\u7c21\u55ae\u7684\u65b9\u6cd5,\u4f46\u8017\u6642,\u56e0\u70ba\u8981\u6bd4\u8f03candidate,\u800c\u4e14\u8981\u4e00\u76f4scan
FPgrowth:\u8a08\u7b97\u5feb\u901f,\u56e0\u70ba\u4e0d\u7528\u7522\u751fcandidate,\u800c\u4e14scan\u50c5\u9700\u4e00\u6b21
vertical data format approach:\u5c07\u6b04\u8207\u5217\u8f49\u63db,\u65b9\u6cd5\u7c21\u55ae,\u6bd4apriori\u5feb<\/p>\n\n\n\n

…..<\/p>\n\n\n\n

apriori<\/strong>
\u65b9\u6cd5\u81f4\u5982\u4e0b
1.scan:\u8a08\u7b97\u6bcf\u500bitemset support,\u5f97\u5230Cn
2.compare:\u5404itemset(candidate) support\u548cmini support\u6bd4\u8f03,\u4ee5\u5f97\u5230Ln
3.\u6839\u64daLn\u7522\u751fCn+1
4.\u91cd\u89861-3\u76f4\u5230\u7d50\u675f<\/p>\n\n\n\n

apriori\u505a\u6cd5\u7bc4\u4f8b
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)
\u7522\u751fl3\u5982\u4e0b<\/p>\n\n\n\n

 <\/td>C1:scan
itemset : sup
1 : 6 
2 : 7
3 : 6
4 : 2 
5 : 2 <\/td>		L1:\u5927\u65bcmin sup\u4e4bcandidate
itemset : sup
1 : 6 
2 : 7
3 : 6
4 : 2 
5 : 2 <\/td><\/tr>
generate C2
itemset
1,2
1,3
1,4
1,5
2,3
2,4
2,5
3,4
3,5
4,5  <\/td>		 C2:scan
itemset : sup
1,2 : 4
1,3 : 4
1,4 : 1(\u5c0f\u65bcmin support)
1,5 : 2
2,3 : 4
2,4 : 2
2,5 : 2 
3,4 : 0(\u5c0f\u65bcmin support)
3,5 : 1(\u5c0f\u65bcmin support)
4,5 : 0(\u5c0f\u65bcmin support) <\/td>		L2:\u5927\u65bcmin sup\u4e4bcandidate
itemset : sup
1,2 : 4
1,3 : 4
1,5 : 2
2,3 : 4
2,4 : 2
2,5 : 2 <\/td><\/tr>
generate C3
itemset
1,2,3
1,2,5
1,3,5(\u56e03,5:1\u6240\u4ee5\u4e0d\u7528)
2,3,5(\u56e03,5:1\u6240\u4ee5\u4e0d\u7528)
2,3,4(\u56e03,4:0\u6240\u4ee5\u4e0d\u7528)
2,4,5(\u56e04,5:0\u6240\u4ee5\u4e0d\u7528)  <\/td>		C3:scan
itemset : sup
1,2,3 : 2
1,2,5 : 2  <\/td>		L3:\u5927\u65bcmin sup\u4e4bcandidate
itemset : sup
1,2,3 : 2
1,2,5 : 2 <\/td><\/tr>
generage C4
itemset
1,2,3,5  <\/td>		C4:scan
itemset : sup
1,2,3,5: 1(\u5c0f\u65bcmin support)  <\/td>		L4:\u5927\u65bcmin sup\u4e4bcandidate
itemset : sup <\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

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} <\/p>\n\n\n\n

…..<\/p>\n\n\n\n

FPgrowth<\/strong>
\u65b9\u6cd5\u5927\u81f4\u5982\u4e0b
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<\/p>\n\n\n\n

FPgrowth\u505a\u6cd5\u7bc4\u4f8b
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)<\/p>\n\n\n\n

1
compute support(\u82e5\u6709\u5c0f\u65bcsupport\u5247\u5c07\u4ed6\u6392\u9664) and sort by support
itemset : sup
2 : 7
1 : 6
3 : 6
4 : 2
5 : 2<\/p>\n\n\n\n

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<\/p>\n\n\n\n

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


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} \u5c0f\u65bcmini sup
4 ((2,1*1),(2*1)) => {2,4*2} \/\/{2,1*1} \u5c0f\u65bcmini 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}<\/p>\n\n\n\n

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}<\/p>\n\n\n\n

…..<\/p>\n\n\n\n

vertical data format approach<\/strong>
\u65b9\u6cd5\u5927\u81f4\u5982\u4e0b
1\u6b04\u5217\u8f49\u63db
2\u5c07\u524d\u4e00\u6b65\u9a5f\u672a\u5c0f\u65bcmin support\u7684\u503c\u505a\u7d44\u5408\u4e26\u4ea4\u96c6<\/p>\n\n\n\n

vertical data format approach\u505a\u6cd5\u7bc4\u4f8b
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)<\/p>\n\n\n\n

1
\u6b04\u5217\u8f49\u63db
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<\/p>\n\n\n\n

2
\u5c07\u524d\u4e00\u6b65\u9a5f\u672a\u5c0f\u65bcmin support\u7684\u503c\u505a\u7d44\u5408\u4e26\u4ea4\u96c6
12:a,h,i<\/strong>
13:e,g,h,i<\/strong>
14:d\u3000\u3000(\u5c0f\u65bcmin support)
15:a,h
23:c,f,h,i
24:b,d
25:a,h<\/strong>
34:\u3000\u3000(\u5c0f\u65bcmin support)
35:h (\u5c0f\u65bcmin support)
45:\u3000\u3000(\u5c0f\u65bcmin support)<\/p>\n\n\n\n

3
\u5c07\u524d\u4e00\u6b65\u9a5f\u672a\u5c0f\u65bcmin support\u7684\u503c\u505a\u7d44\u5408\u4e26\u4ea4\u96c6
1,2,3:h,i
1,2,5:a,h<\/strong>
1,3,5:h (\u56e03,5:0\u6240\u4ee5\u4e0d\u7528)
2,3,4: (\u56e03,4:0\u6240\u4ee5\u4e0d\u7528)
2,3,5: (\u56e03,5:0\u6240\u4ee5\u4e0d\u7528)
2,4,5: (\u56e04,5:0\u6240\u4ee5\u4e0d\u7528)<\/p>\n\n\n\n

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}<\/p>\n\n\n\n

……………………………………………………………………………………………………………<\/p>\n\n\n\n

2.generate strong association rule from the frequent itemset<\/strong><\/h2>\n\n\n\n

x=>y(confidence): confidence=x\u767c\u751f\u6642,y\u767c\u751f\u7684\u6bd4\u4f8b<\/p>\n\n\n\n

\u505a\u6cd5\u7bc4\u4f8b(if confidence threshold is 70%,support as above)
{2,5*2} 2=>5(2\/7) ; 5=>2(2\/2=100%>70%)<\/strong>\u3000
{1,5*2} 1=>5(2\/6) ; 5=>1(2\/2 =100%>70%)<\/strong>
{2,4*2} 2=>4(2\/7) ; 4=>2(2\/2=100%>70%)<\/strong>
{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}
\u30001^2=>5(2\/4=50%)
\u30001^5=>2(2\/2=100%>70%)<\/strong>
\u30002^5=>1(2\/2=100%>70%)<\/strong>
\u30001=>2^5(2\/6=33%)
\u30002=>1^5(2\/7=29%)
\u30005=>1^2(2\/2=100%>70%)<\/strong>
{2,1,3*2}
\u30001^2=>3 ,
\u30001^3=>2
\u30002^3=>1 ,
\u30001=>2^3 ,
\u30002=>1^3 ,
\u30003=>1^2 ,<\/p>\n\n\n\n

\u7d50\u679c\u53ef\u5beb\u6210\u4ee5\u4e0b
x=>y(support,confidence)
5=>2(40%,100%)\u3000
5=>1(40%,100%)
4=>2(40%,100%)<\/strong><\/p>\n\n\n\n

……………………………………..<\/p>\n\n\n\n

\u627e\u51fa\u5404\u7a2eassociation rules<\/strong>
\u5e38\u898b\u6709\u4ee5\u4e0b
mining multilevel association,
mining multidimensional association
mining quantitave association
mining interesting correlation patterns<\/p>\n\n\n\n


mining multilevel association,<\/strong>
\u5404\u5c64support\u8a08\u7b97\u65b9\u5f0f\u4e3b\u8981\u5206\u70ba\u5169\u7a2e
\u3000uniform support:\u6bcf\u4e00\u5c64\u90fd\u7528\u76f8\u540c\u7684support
\u3000reduced support:\u8d8a\u4e0b\u5c64\u7528\u8d8a\u5c11\u7684support
ex:\u7b2c\u4e00\u5c64virus[sup=10%],\u7b2c\u4e8c\u5c64\u53ef\u5206\u70bafile virus[sup=4%]\u548cboot virus[sup=6%]
uniform support=5%,\u5247\u7b2c\u4e8c\u5c64file virus[sup=4%]\u5247\u4e0d\u88ab\u627e\u5230
reduced support,\u7b2c\u4e00\u5c64=5%,\u7b2c\u4e8c\u5c64=3%,\u5373\u53ef\u5168\u90e8\u627e\u5230<\/p>\n\n\n\n

mining multidimensional association<\/strong>
\u4e3b\u8981\u5206\u5169\u7a2erule
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)<\/p>\n\n\n\n

mining quantitave association<\/strong>
1\u5c07\u6578\u503c\u5148\u5207\u5272\u6210\u5404\u6bb5
2\u627e\u51faassociation
ex:age(20)^income(10-20k)=>buy(pc)<\/p>\n\n\n\n

…………………………………………………………………………………………………………….<\/p>\n\n\n\n

(option)3.correlation analysis for association rule <\/strong><\/h2>\n\n\n\n

\u53ea\u9760support\u53caconfidence\u6709\u6642\u4e0d\u5920,\u56e0\u6b64\u6709\u6642\u6703\u52a0correlation
ex:
\u5047\u8a2d\u572810000\u7b46\u8cfc\u8cb7\u8a18\u9304\u4e2d,\u8cb7computer\u67096000\u4eba,\u8cb7lcd\u67097500\u4eba,\u5169\u8005\u540c\u6642\u8cb7\u67094000\u4eba
\u4e14min support=30%,min confidence=60%
\u5047\u5982\u767c\u73fe\u4ee5\u4e0bassociation rule
buy(computer)=>buy(lcd)[support=40%,confidence=66%]
\u8cb7computer\u7684\u4eba,\u6703\u670966%\u8cb7lcd
\u4f46\u662f\u56e0\u70ba\u6839\u64da\u8cfc\u8cb7\u8a18\u9304\u53ef\u4ee5\u770b\u5230,\u8cb7lcd\u6a5f\u7387\u70ba75\uff05,\u6240\u4ee5\u8a72association rule\u6c92\u6709\u5e6b\u52a9<\/p>\n\n\n\n

\u5e38\u898b\u7684correlation measures\u6709<\/strong>
chi-squre
lift
all_conf,\u8f03\u9069\u5408\u7528\u65bcassociation rule
coh,\u8f03\u9069\u5408\u7528\u65bcassociation rule<\/p>\n\n\n\n


\u5047\u8a2dvirus\u548cp2p\u7684contingency table\u5982\u4e0b<\/p>\n\n\n\n

 <\/td>virus <\/td>no virus <\/td>sum <\/td><\/tr>
p2p <\/td> v,p (100)<\/td> !v,p (200 )<\/td> p (300)<\/td><\/tr>
no p2p <\/td> v,!p (300)<\/td> !v,!p (400)<\/td> !p (700)<\/td><\/tr>
 sum<\/td> v (400) <\/td> !v (600)<\/td> total (1000)<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

lift(A,B)=p(A\u4ea4\u96c6B)\/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<\/p>\n\n\n\n

all_conf(X)=sup(X)\/max_item_sup(X)
all_conf(v)=v,p\/max(v)=100\/max(400,300)=100\/400=0.25
\u5c0f\u65bc0.5,\u8868\u793a\u4e0d\u7368\u7acb<\/p>\n\n\n\n

coh(x)=sup(X)\/|universe(X)|
coh(v)=v,p\/(v,p+!v,p+v,!p)=100\/100+300+200=100\/600=0.20
\u5c0f\u65bc0.5,\u8868\u793a\u4e0d\u7368\u7acb<\/p>\n\n\n\n

cosine =(100\/1000) \/(sqrt(400\/1000)+sqrt(300\/1000))=0.0847<\/p>\n\n\n\n


ps:
\u5728min support\u65b9\u9762
virus,p2p = 100\/1000=10%
virus = 400\/1000 =40%
p2p = 300\/1000=30%
ps:
\u5728min confidence\u65b9\u9762
virus=>p2p( 100\/400=25% )
p2p=>virus(100\/300 =33%)<\/p>\n","protected":false},"excerpt":{"rendered":"

frequent pattern analysisfrequ …<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"fifu_image_url":"","fifu_image_alt":"","_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[13],"tags":[],"class_list":["post-457","post","type-post","status-publish","format-standard","hentry","category-dataanalysis"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/posts\/457","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/comments?post=457"}],"version-history":[{"count":0,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/posts\/457\/revisions"}],"wp:attachment":[{"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/media?parent=457"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/categories?post=457"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/tags?post=457"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}