關(guān)聯(lián)分析計(jì)算支持度計(jì)數(shù)關(guān)聯(lián)分析原理

規(guī)則

事務(wù)關(guān)聯(lián)規(guī)則頻繁項(xiàng)集2關(guān)聯(lián)分析原理

規(guī)則

事務(wù)關(guān)聯(lián)規(guī)則頻繁項(xiàng)集

候選項(xiàng)集

3幾個(gè)問題產(chǎn)生候選項(xiàng)集計(jì)算支持度用事務(wù)去逐個(gè)統(tǒng)計(jì)候選項(xiàng)集枚舉各事務(wù)中的項(xiàng)集并計(jì)數(shù)利用Hash樹計(jì)數(shù)4用事務(wù)去逐個(gè)統(tǒng)計(jì)候選項(xiàng)集事務(wù)候選項(xiàng)集支持度計(jì)數(shù)NWM5枚舉各事務(wù)中的項(xiàng)集并計(jì)數(shù)

6

枚舉各事務(wù)中的項(xiàng)集并計(jì)數(shù)7利用Hash樹計(jì)算支持度Hash樹7807%2=1插入249%2=1沖突，249%3=0插入1073%2=1沖突，1073%3=2插入658%2=0插入930%2=0沖突，930%3=0插入2272%2=0沖突，2272%3=1插入8544%2=0沖突，8544%3=0沖突，8544%5=4插入1878%2=0沖突，1878%3=0沖突，1878%5=3插入8923%2=1沖突，8923%3=1插入8709%2=1沖突，8709%3=0沖突，8709%5=4插入root010102344165878079301878854489238709107324922728散列樹n%2n%3n%5Hash樹原理【質(zhì)數(shù)分辨定理】選取任意n個(gè)互不相同的質(zhì)數(shù)：P1<P2<……<Pn-1<Pn(n∈N)，定義設(shè)m≤k1<k2<m+M

（m，k1，k2∈N

），那么對(duì)于任意的i∈[1，n]，(k1

modPi)=(k2modPi)不可能總成立。簡單地說就是：n

個(gè)不同的質(zhì)數(shù)可以“分辨”的連續(xù)整數(shù)的個(gè)數(shù)和他們的乘積相等?！胺直妗本褪侵高@些連續(xù)的整數(shù)不可能有完全相同的余數(shù)序列。例如：從2起的連續(xù)質(zhì)數(shù)，連續(xù)10個(gè)質(zhì)數(shù)就可以分辨大約M(10)=2

3

5

7

11

13

17

19

23

29=6464693230個(gè)數(shù)，已經(jīng)超過計(jì)算機(jī)中常用整數(shù)（32bit）的表達(dá)范圍。9根據(jù)頻繁項(xiàng)集（例如F2）產(chǎn)生候選3-項(xiàng)集（Fk-1xFk-1）建立起候選項(xiàng)集Hash樹遍歷事務(wù)T在樹中散列事務(wù)項(xiàng)t匹配的候選項(xiàng)集支持度計(jì)數(shù)+1計(jì)算支持度10候選項(xiàng)集

-{

-{

}

-{

}

-{

}

-{

}

-{

}123237137127267236

-{

}

-{

}

-{

}367{

}候選項(xiàng)集Hash樹計(jì)算支持度【例】利用Hash樹計(jì)算支持度計(jì)數(shù)11候選4-項(xiàng)集:{1235},{1236},{1256},{1356},{2356}候選3-項(xiàng)集:{123},{125},{126},{135},{136},{156},{235},{236},{256},{356}計(jì)算支持度【例】利用Hash樹計(jì)算支持度計(jì)數(shù)12Hash樹1,4,72,5,83,6,9Hash函數(shù)：h(p)=p

mod3事務(wù)中，項(xiàng)集為{1,2,3,4,5,6}計(jì)算支持度【例】利用Hash樹計(jì)算支持度計(jì)數(shù)1231-{23}{123}12-{3}候選3-項(xiàng)集:{123},{125},{126},{135},{136},{156},{235},{236},{256},{356}{1

23}由候選3-項(xiàng)集生成Hash樹結(jié)構(gòu)13Hash樹1,4,72,5,83,6,9計(jì)算支持度【例】利用Hash樹計(jì)算支持度計(jì)數(shù)Hash樹1,4,72,5,83,6,91231-{23}{123}12-{3}1-{25}{125}12-{5}125候選3-項(xiàng)集:{123},{125},{126},{135},{136},{156},{235},{236},{256},{356}由候選3-項(xiàng)集生成Hash樹結(jié)構(gòu){1

25}14計(jì)算支持度【例】利用Hash樹計(jì)算支持度計(jì)數(shù)Hash樹1,4,72,5,83,6,91231-{23}{123}12-{3}1-{25}{125}12-{5}1251-{26}{126}12-{6}126候選3-項(xiàng)集:{123},{125},{126},{135},{136},{156},{235},{236},{256},{356}由候選3-項(xiàng)集生成Hash樹結(jié)構(gòu){126}15計(jì)算支持度【例】利用Hash樹計(jì)算支持度計(jì)數(shù)Hash樹1,4,72,5,83,6,91231251-{26}{126}12-{6}1261-{35}{135}13-{5}135候選3-項(xiàng)集:{123},{125},{126},{135},{136},{156},{235},{236},{256},{356}由候選3-項(xiàng)集生成Hash樹結(jié)構(gòu){135}16{135}{136}1-{35}計(jì)算支持度【例】利用Hash樹計(jì)算支持度計(jì)數(shù)Hash樹1,4,72,5,83,6,91231251261-{35}13513-{5}12-{6}1-{36}13-{6}136候選3-項(xiàng)集:{123},{125},{126},{135},{136},{156},{235},{236},{256},{356}由候選3-項(xiàng)集生成Hash樹結(jié)構(gòu){136}17計(jì)算支持度【例】利用Hash樹計(jì)算支持度計(jì)數(shù)Hash樹1,4,72,5,8

3,6,92-{3456}3-{456}35-{6}356 12323-{456}1-{23456}{123456}23525623625-{6}12-{3456}13-{456}12613512513615615-{6}候選3-項(xiàng)集:{123},{125},{126},{135},{136},{156},{235},{236},{256},{356}由候選3-項(xiàng)集生成Hash樹結(jié)構(gòu){356}18計(jì)算支持度【例】利用Hash樹計(jì)算支持度計(jì)數(shù)Hash樹1,4,72,5,83,6,923-{456}1-{23456}root2-{3456}3-{456}12-{3456}13-{456}123235135125136 156256 23612615-{6}25-{6}35-{6}356 {13

46}事務(wù)數(shù)據(jù)項(xiàng)t按照同樣的規(guī)則進(jìn)行散列，如果能夠到達(dá)葉結(jié)點(diǎn)中的候選項(xiàng)集，則對(duì)其支持度計(jì)數(shù)加1。1-{3

46}13-{46}136 {3

46}3-{46}{46}19計(jì)算支持度【例】利用Hash樹計(jì)算支持度計(jì)數(shù)Hash樹1,4,72,5,83,6,92-{3456}3-{456}345項(xiàng){1},{2},{3},{4},{5},{6}構(gòu)成3-項(xiàng)集的Hash樹結(jié)構(gòu)34-{56}346 35-{6}356 45-{6}45612323-{456}4-{56}1241-{23456}{123456}13423525623614-{56}14523424-{56}24524625-{6}12-{3456}13-{456}12613512513615614615-{6}20計(jì)算支持度【例】利用Hash樹計(jì)算支持度計(jì)數(shù)123613561235Hash樹1,4,72,5,83,6,91256123-{456}2356235-{6}135-{6}125-{6}12-{3456}13-{456}23-{456}1-{23456}{123456}2-{3456}候選4-項(xiàng)集:{1235},{1236},{1256},{1356},{2356}由候選4-項(xiàng)集生成Hash樹結(jié)構(gòu)21計(jì)算支持度【例】利用Hash樹計(jì)算支持度計(jì)數(shù)123613561235Hash樹1,4,72,5,83,6,91256123-{456}2356235-{6}135-{6}125-{6}12-{3456}13-{456}23-{456}1-{23456}2-{3456}root{12356}{2356}123612352356事務(wù)數(shù)據(jù)項(xiàng)t按照同樣的規(guī)則進(jìn)行散列，如果能夠到達(dá)葉結(jié)點(diǎn)中的候選項(xiàng)集，則對(duì)其支持度計(jì)數(shù)加1。{356}22計(jì)算支持度【例】利用Hash樹計(jì)算支持度計(jì)數(shù)12361356123523451245Hash樹1,4,72,5,83,6,9項(xiàng){1},{2},{3},{4},{5},{6}構(gòu)成的4-項(xiàng)集Hash樹結(jié)構(gòu)123412461256123-{456}134513461456234623562456235-{6}134-{56}135-{6}145-{6}245-{6}124-{56}125-{6}234-{56}12-{3456}13-{456}14-{56}24-{56}23-{456}1-{23456}{123456}2-{3456}3-{456}3

4-{56}345-{6}345623

K-候選項(xiàng)集Hash樹Hash樹1,4,72,5,83,6,924123