数据挖掘Chapter7

数据挖掘导论Pang-ningTan,MichaelStieinbach,andVipinKumar著PearsonEducationLTD.范明等译人民邮电出版社第7章关联分析：高级概念2019年10月21日星期一数据挖掘导论3多维关联规则单维规则:buys(X,“milk”)buys(X,“bread”)通常表示成milkbread多维规则:维或谓词2维间关联规则(不含重复谓词)sex(X,“男”)income(X,“40K-49K”)buys(X,“iPhone”)或{sex=“男”,income=“40K-49K”}iPhone混合维关联规则(含重复谓词)age(X,“19-25”)buys(X,“popcorn”)buys(X,“coke”)多维关联规则提供了更精细的分析2019年10月21日星期一数据挖掘导论4多维关联规则规则sex(X,“男”)income(X,“40K-49K”)buys(X,“iPhone”)是形如{Sex=“男”,income=“40-49K”,iPhone}的频繁模式产生的这里，Sex=“男”和income=“40-49K”都是“项”，它们是属性-值对由这样的频繁模式产生关联规则的方法与前面并无本质差别把诸如sex=“男”和income=“40-49K”的属性-值对看作项，可以使用Apriori算法或FP-Growth算法挖掘形如{sex=“男”，income=“40-49K”，iPhone}的频繁模式sex是分类（二元）属性，income是连续属性如何处理它们？7.1处理分类属性2019年10月21日星期一数据挖掘导论6例例：因特网调查数据包含对称二元属性：性别、家庭计算机、网上聊天、网上购物和关注隐私还包括标称属性：文化程度和州{网上购物=是}→{关注隐私=是}性别文化程度州家庭计算机网上聊天网上购物关注隐私女男男女女男男男女…研究生大学研究生大学研究生大学大学高中研究生…伊利诺伊加利福尼亚密歇根弗吉尼亚加利福尼亚明尼苏达阿拉斯加俄勒冈得克萨斯…是否是否是是是是否…是否是否否是是否是…是否是是否是是否否…是否是是是是否否否…2019年10月21日星期一数据挖掘导论7处理分类属性如何处理分类属性把分类属性转换成一组非对称的二元属性方法对每个不同的属性-值对，引进一个新的“项”例：标称属性文化程度可以用三个二元项取代：文化程度=大学，文化程度=研究生，文化程度=高中对称二元属性性别可以转换成一对二元项：男、女2019年10月21日星期一数据挖掘导论8处理分类属性：例例：二元化分类属性和对称二元属性后的因特网调查数据表头是“项”每行看作一个事务，列值为1，对应的项出现在该事务中例如，第一行的事务为{女,…,关注隐私=是}男女文化程度=研究生文化程度=大学…关注隐私=是关注隐私=否011001110…100110001…101010001…010101100……………………………101111000…010000111…2019年10月21日星期一数据挖掘导论9处理分类属性:问题可能的问题1属性具有过多的可能值例如:属性“州”可能多达50个值其中某些属性值的支持度很低可能的解决方案:聚集低支持度的属性值例:弗吉尼亚加利福尼亚纽约马萨诸塞德克萨斯俄勒冈明尼苏达佛罗里达俄亥俄密歇根伊利诺伊其他2019年10月21日星期一数据挖掘导论10处理分类属性:问题(续)可能的问题2属性值的分布高度倾斜例如:85%的被调查人都有家庭计算机可能产生如下规则{家庭计算机=是,网上购物=是}→{关注隐私=是}这个规则可能是冗余的，它不如下面的规则一般{网上购物=是}→{关注隐私=是}可能的解决方案：删除高频率的项7.2处理连续属性2019年10月21日星期一数据挖掘导论12例因特网调查数据可能还包含连续属性挖掘连续属性可能揭示数据的内在联系，如年收入超过$120K的用户属于45～60年龄组拥有超过3个email账号并且每周上网超过15小时的用户通常关注个人隐私包含连续属性的关联规则通常称作量化关联规则（quantitativeassociationrule）性别…年龄年收入每周上网小时数email账号数关注隐私女男男女女男男男女……………………………265129453125374126…90K135K80K120K95K55K100K65K85K…20101015202510812…423355121…是否是是是是否否否…2019年10月21日星期一数据挖掘导论13基于离散化的方法基本思想将连续属性的邻近值分组，形成有限个区间例如，年龄属性可以划分成如下区间：年龄[12,16),年龄[16,20),年龄[20,24),...,年龄[56,60)例：因特网调查数据男女…年龄13年龄[13,21)年龄[21,30)…关注隐私=是关注隐私=是011001110…100110001……………………………000000000…000000000…101001001……………………………101111000…010000111…2019年10月21日星期一数据挖掘导论14离散化的问题数据中隐含两个强规则：R1：年龄[16,24)→网上聊天=是（s=8.8%,c=81.5%）R2：年龄[44,60)→网上聊天=否（s=16.8%,c=70%）最小支持度阈值5%，最小置信度阈值65%问题：如何确定区间宽度如果区间太宽，则可能因为缺乏置信度而丢失某些模式例如，当区间宽度为24岁时，R1和R2被如下规则所取代：R1’：年龄[12,36)→网上聊天=是（s=30%,c=57.7%）R2’：年龄[36,60)→网上聊天=否（s=28%,c=58.3%）它们不满足最小置信度2019年10月21日星期一数据挖掘导论15离散化的问题(续)如果区间太窄，则可能因为缺乏支持度而丢失某些模式例如，如果区间宽度为4岁，则R1被分裂成如下两个子规则R11：年龄[16,20)→网上聊天=是（s=4.4%,c=84.6%）R12：年龄[20,24)→网上聊天=是（s=4.4%,c=78.6%）它们不满足最小支持度类似地，R2被分解成4个不满足最小支持度的规则可能的处理方法考虑邻近区间的每种可能的分组例如，我们可以以宽度4岁开始，将近邻的区间合并成较宽的区间，年龄[12,16),年龄[12,20),...,年龄[12,60),年龄[16,20),年龄[16,24)等等2019年10月21日星期一数据挖掘导论16离散化的问题(续)运行时间Ifintervalscontainnvalues,thereareonaverageO(n2)possiblerangesToomanyrules例如，考虑下面的规则对：R3：{年龄[16..20),性别=男}→{网上聊天=是}R4：{年龄[16..24),性别=男}→{网上聊天=是}R4是R3的泛化2019年10月21日星期一数据挖掘导论17基于统计学的方法量化关联规则可以用来推断总体的统计性质例如，假定我们希望根据表7-1和表7-3提供的数据，找出因特网用户特定组群的平均年龄例如，找出如下规则{年收入＞$100K,网上购物=是}年龄：均值=38男女文化程度=研究生文化程度=大学…关注隐私=是关注隐私=否011001110…100110001…101010001…010101100……………………………101111000…010000111…表7-12019年10月21日星期一数据挖掘导论18基于统计学的方法表7-3性别…年龄年收入每周上网小时数email账号数关注隐私女男男女女男男男女……………………………265129453125374126…90K135K80K120K95K55K100K65K85K…20101015202510812…423355121…是否是是是是否否否…2019年10月21日星期一数据挖掘导论19非离散化方法在有些应用中，感兴趣的是连续属性之间的关联，而不是连续属性的离散区间之间的关联例：文档数据库包括多个文档，用文档-词矩阵(Document-termmatrix)表示我们关心的是文档中词的关联,如“数据”与“挖掘”的关联不是关心词频区间（例如，“数据[1,4]”和“挖掘[2,3]”）之间的关联一种可能的方法将文档-词矩阵变换成0/1矩阵丢失词频信息TIDW1W2W3W4W5D122001D200122D323000D400101D5111022019年10月21日星期一数据挖掘导论20Min-Apriori的方法规范化文档-词矩阵每个词的支持度和为1TIDW1W2W3W4W5D122001D200122D323000D400101D511102TIDW1W2W3W4W5D10.400.330.000.000.17D20.000.000.331.000.33D30.400.500.000.000.00D40.000.000.330.000.17D50.200.170.330.000.33Normalize2019年10月21日星期一数据挖掘导论21Min-Apriori的方法定义词集合X的支持度例：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TiXjjiDX),(min)sup(TIDW1W2W3W4W5D10.400.330.000.000.17D20.000.000.331.000.33D30.400.500.000.000.00D40.000.000.330.000.17D50.200.170.330.000.332019年10月21日星期一数据挖掘导论22Min-Apriori的方法min-Apriori中定义的支持度具有如下期望性质支持度随词的规范化频率增加而单调递增支持度随包含该词的文档个数增加而单调递增支持度具有反单调性例如，考虑一对项集{A,B}和{A,B,C}由于min({A,B})≥min({A,B,C})，从而s({A,B})≥s({A,B,C})。因此，支持度随项集中词数的增加而单调递减使用新的支持度定义，可以修改标准Apriori算法，来发现词之间的关联7.3处理概念分层2019年10月21日星期一数据挖掘导论24多层关联规则FoodBreadMilkSkim2%ElectronicsComputersHomeDesktopLaptopWheatWhiteForemostKempsDVDTVPrinterScannerAccessory2019年10月21日星期一数据挖掘导论25多层关联规则为什么考虑概念分层?位于层次结构较下层的项可能没有足够的支持度,从而不在任何频繁项集中出现在概念分层的较低层发现的规则倾向于过于特殊例,skimmilkwhitebread,2%milkwheatbread,skimmilkwheatbread,etc都是milk和bread之间的关联2019年10月21日星期一数据挖掘导论26多层关联规则Approach1:ExtendcurrentassociationruleformulationbyaugmentingeachtransactionwithhigherlevelitemsExampleOriginalTransaction:{skimmilk,wheatbread}AugmentedTransaction:{skimmilk,wheatbread,milk,bread,food}Issues:Itemsthatresideathigherlevelshavemuchhighersupportcountsifsu