《数据挖掘原理与应用 第2版 》课件 5.3关联分析-计算支持度计数

关联分析计算支持度计数关联分析原理

规则

事务关联规则频繁项集2关联分析原理

规则

事务关联规则频繁项集

候选项集

3几个问题产生候选项集计算支持度用事务去逐个统计候选项集枚举各事务中的项集并计数利用Hash树计数4用事务去逐个统计候选项集事务候选项集支持度计数NWM5枚举各事务中的项集并计数

6

枚举各事务中的项集并计数7利用Hash树计算支持度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树原理【质数分辨定理】选取任意n个互不相同的质数：P1<P2<……<Pn-1<Pn(n∈N)，定义设m≤k1<k2<m+M

（m，k1，k2∈N

），那么对于任意的i∈[1，n]，(k1

modPi)=(k2modPi)不可能总成立。简单地说就是：n

个不同的质数可以“分辨”的连续整数的个数和他们的乘积相等。“分辨”就是指这些连续的整数不可能有完全相同的余数序列。例如：从2起的连续质数，连续10个质数就可以分辨大约M(10)=2

3

5

7

11

13

17

19

23

29=6464693230个数，已经超过计算机中常用整数（32bit）的表达范围。9根据频繁项集（例如F2）产生候选3-项集（Fk-1xFk-1）建立起候选项集Hash树遍历事务T在树中散列事务项t匹配的候选项集支持度计数+1计算支持度10候选项集

-{

-{

}

-{

}

-{

}

-{

}

-{

}123237137127267236

-{

}

-{

}

-{

}367{

}候选项集Hash树计算支持度【例】利用Hash树计算支持度计数11候选4-项集:{1235},{1236},{1256},{1356},{2356}候选3-项集:{123},{125},{126},{135},{136},{156},{235},{236},{256},{356}计算支持度【例】利用Hash树计算支持度计数12Hash树1,4,72,5,83,6,9Hash函数：h(p)=p

mod3事务中，项集为{1,2,3,4,5,6}计算支持度【例】利用Hash树计算支持度计数1231-{23}{123}12-{3}候选3-项集:{123},{125},{126},{135},{136},{156},{235},{236},{256},{356}{1

23}由候选3-项集生成Hash树结构13Hash树1,4,72,5,83,6,9计算支持度【例】利用Hash树计算支持度计数Hash树1,4,72,5,83,6,91231-{23}{123}12-{3}1-{25}{125}12-{5}125候选3-项集:{123},{125},{126},{135},{136},{156},{235},{236},{256},{356}由候选3-项集生成Hash树结构{1

25}14计算支持度【例】利用Hash树计算支持度计数Hash树1,4,72,5,83,6,91231-{23}{123}12-{3}1-{25}{125}12-{5}1251-{26}{126}12-{6}126候选3-项集:{123},{125},{126},{135},{136},{156},{235},{236},{256},{356}由候选3-项集生成Hash树结构{126}15计算支持度【例】利用Hash树计算支持度计数Hash树1,4,72,5,83,6,91231251-{26}{126}12-{6}1261-{35}{135}13-{5}135候选3-项集:{123},{125},{126},{135},{136},{156},{235},{236},{256},{356}由候选3-项集生成Hash树结构{135}16{135}{136}1-{35}计算支持度【例】利用Hash树计算支持度计数Hash树1,4,72,5,83,6,91231251261-{35}13513-{5}12-{6}1-{36}13-{6}136候选3-项集:{123},{125},{126},{135},{136},{156},{235},{236},{256},{356}由候选3-项集生成Hash树结构{136}17计算支持度【例】利用Hash树计算支持度计数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-项集:{123},{125},{126},{135},{136},{156},{235},{236},{256},{356}由候选3-项集生成Hash树结构{356}18计算支持度【例】利用Hash树计算支持度计数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}事务数据项t按照同样的规则进行散列，如果能够到达叶结点中的候选项集，则对其支持度计数加1。1-{3

46}13-{46}136 {3

46}3-{46}{46}19计算支持度【例】利用Hash树计算支持度计数Hash树1,4,72,5,83,6,92-{3456}3-{456}345项{1},{2},{3},{4},{5},{6}构成3-项集的Hash树结构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计算支持度【例】利用Hash树计算支持度计数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-项集:{1235},{1236},{1256},{1356},{2356}由候选4-项集生成Hash树结构21计算支持度【例】利用Hash树计算支持度计数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事务数据项t按照同样的规则进行散列，如果能够到达叶结点中的候选项集，则对其支持度计数加1。{356}22计算支持度【例】利用Hash树计算支持度计数12361356123523451245Hash树1,4,72,5,83,6,9项{1},{2},{3},{4},{5},{6}构成的4-项集Hash树结构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-候选项集Hash树Hash树1,4,72,5,83,6,924123