数据挖掘中的关联分析.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,关联分析中各种属性的处理,知识回顾,1.,分类属性的处理,1.1,概念介绍,1.2,处理方法,1.3,分类属性二元化的不足,2.,连续属性的处理,2.1,基于离散化的方法,2.1,基于统计学的方法,2.3,基于非离散化的方法,关联规则挖掘假定输入数据由称作项的二元属性组成。还假定项在事物中出现比不出现更重要。这样，项被看作非对称的二元属性，且只有频繁模式才被认为是有趣的。,例：,6-2,购物篮数据的二元,0/1,表示,TID,面包,牛奶,尿布,啤酒,鸡蛋,可乐,1,1,1,0,0,0,0,2,1,0,1,11,0,3,0,1,1,1,0,1,4,1,1,1,1,0,0,5,1,1,1,0,0,1,从上述的购物篮数据中，我们可得出,尿布,啤酒,这一有趣的规则。,这一频繁项集的得出，我们可以运用：,Apriori,算法、,Hash,树法、,FP,增长算法等等。,关于该规则的支持度和置信度的计算如下：,上面规则的支持度,s=,尿布、啤酒,支持度计数,/,事物个数,=3/5=0.6,上面规则的置信度,c=,尿布、啤酒,支持度计数,/,尿布,支持度计数,=3/4=0.75,1,、处理分类属性,性别,文化程度,州,家庭计算机,网上聊天,网上购物,关注隐私,女,研究生,伊利诺伊,是,是,是,是,男,大学,加利福尼亚,否,否,否,否,男,研究生,密歇根,是,是,是,是,女,大学,弗吉尼亚,否,否,是,是,女,研究生,加利福尼亚,是,否,否,是,男,大学,明尼苏达,是,是,是,是,男,大学,阿拉斯加,是,是,是,否,男,高中,俄勒冈,是,否,否,否,女,研究生,得克萨斯,否,是,否,否,1.1,概念介绍,上面的因特网调查数据中，像性别、家庭计算机、网上聊天、网上购物和关注隐私这些属性，我们称为,对称二元属性,；而像文化程度、州称之为,标称属性,。,1.2,处理方法,对于对称二元属性，可以转化成一对二元属性如：性别分为,男,和,女,，而对于标称属性，则可以用多个二元项取代，例如：,文化程度,=,大学,文化程度,=,研究生,，文化程度,=,高中,。,通过这样将分类属性和对称二元属性转化成“项”之后，我们就可以如下二元化后的调查数据：,男,女,文化程度,=,研究生,文化程度,=,大学,关注隐私,=,是,关注隐私,=,否,0,1,1,0,1,0,1,0,0,1,0,1,1,0,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0,1,0,0,1,1,0,1,0,0,1,0,1,1,0,0,0,0,1,0,1,1,0,0,1,使用关联分析，从上表挖掘出的信息是：,网上购物,=,是,关注隐私,=,是,1.2,分类属性二元化的不足,利用二元化后的数据进行关联分析时，需要注意以下几点：,（,1,）有些属性值可能不够频繁，不能成为频繁模式的一部分。这个问题主要出在标称属性上，如例子中的州名这一属性。若不加处理的将其用多个二元项取代，计算量将会过大，不太实际。所以实际做法是，将相关的属性值分组，形成少数类别。例如，每个州名都可以用对应的地理区域如中西部、太平洋西北部、西南部和东海岸取代。另一种可能性是，将不太频繁的属性值聚合成一个称作其他的类别。,（,2,）某些属性的频率可能比其他属性高很多，容易产生冗余模式。例如，假定,85%,的被调查人都有家庭计算机。如果为每个频繁出现在数据中的属性值创建一个二元项，我们可能产生许多冗余模式，如下面的例子所示：,家庭计算机,=,是，网上购物,=,是,关注隐私,=,是,（,3,）尽管每个事物的宽度与原始数据中属性个数相同，但是计算时间可能增加，特别是当新创建的项变成频繁项时。这是因为需要更多时间处理由这些项产生的候选集。减少计算时间的一种方法是，避免产生包含多个来自同一属性的项的候选项集。例如，我们不必产生诸如州,=X,，州,=Y,，,的候选项集，因为该项集的支持度计数为零。,2,、处理连续属性,性别,年龄,年收入,每周上网小时数,E-mail,帐号数,关注隐私,女,26,90K,20,4,是,男,51,135K,10,2,否,男,29,80K,10,3,是,女,45,120K,15,3,是,女,31,95K,20,5,是,男,25,55K,25,5,是,男,37,100K,10,1,否,男,41,65K,8,2,否,女,26,85K,12,1,否,上表是具有连续属性的因特网调查数据，如年龄、年收入、每周上网小时数、,e-mail,账号数就是,连续属性,。,对连续属性数据进行关联分析的方法具体有,（,1,）基于离散化的方法，（,2,）基于统计学的方法，（,3,）非离散化方法。,2.1,基于离散化的方法,所谓离散化就是将连续属性的邻近值分组，形成有限个区间。例如，年龄属性可以划分成如下区间：年龄,12,16),，年龄,16,20),，年龄,20,24),，,，年龄,56,60),其中，,a,，,b),代表包含,a,但不包含,b的区间。离散的区间可以映射到非对称的二元属性，使得可以使用已有的关联分析算法,下表是二元化分类属性和连续属性后的因特网调查数据,男,女,年龄,网上聊天,=,是（,s=30%,，,c=57.7%,）,R2,：,年龄,36,60)-,网上聊天,=,否（,s=28%,，,c=58.3%,）,尽管它们有较高的支持度，但是较宽的区间导致两个规则的置信度都低于最小置信度阈值。其结果是，离散化之后，两个模式都失去了。,（,2,）,如果区间太窄，则可能因为缺乏支持度丢失某些模式,。例如，如果区间宽度为,4,岁，则,R1,被分裂成如下两个子规则。,R11,：年龄,16,20)-,网上聊天,=,是（,s=4.4c=84.6%,）,R12,：,年龄,36,60)-,网上聊天,=,否（,s=4.4%,，,c=78.6%,）,由于两个子规则都低于最小支持度阈值，离散化后,R1,丢失了。同理，规则,R2,被分裂成,4,个子规则，也因,4,个子规则的支持度都低于最小支持度阈值而丢失。,如果区间宽度是,8,岁，则规则,R2,被分裂成如下两个子规则。,R21,：,年龄,44,52)-,网上聊天,=,否（,s=8.4%,，,c=70%,）,R22,：,年龄,52,60)-,网上聊天,=,否（,s=8.4%,，,c=70%,）,由于,R21,和,R22,都有足够的支持度和置信度，,R2,可以通过聚合两个子规则而恢复。与此同时，,R1,被分裂成如下两个子规则。,R11,：年龄,12,20)-,网上聊天,=,是（,s=9.2%,，,c=60.5%,）,R12,：,年龄,20,28)-,网上聊天,=,是（,s=9.2%,，,c=60.0%,）,不像,R2,，我们不能通过聚合两个子规则来恢复,R1,，因为两个字规则的置信度都低于阈值。处理这些问题的一个方法是，考虑邻近区间的每种可能的分组。例如，我们可以以宽度,4,岁开始，将临近的区间合并成较宽的区间，,年龄,12,16,），,年龄,12,20,），,，,年龄,12,60,），,年龄,16,20,），,年龄,16,24,）等等。这种方法能够检测出,R1,和R2,是强规则。然而，这也导致如下计算问题。,（,1,）,计算开销非常大,。如果值域被划分成,k,个区间，则必须创建,k,（,k-1,）,/2,个二元项来代表所有可能的区间。此外，如果对应于区间,a,，,b),的项是频繁的，则包含,a,，,b),的区间对应的所有项也必然是频繁的。因此，这种方法可能产生过多的候选和频繁项集。为了处理这些问题，可以使用最大支持度阈值，防止创建对应于非常宽的区间的项，并减少项集的数量。,（,2,）,提取许多冗余规则,。例如，考虑下面的规则对：,R3,：,年龄,16,20,），性别,=,男,-,网上聊天,=,是,R4,：,年龄,16,24,），性别,=,男,-,网上聊天,=,是,2.1,基于统计学的方法,需指定用于刻画有趣总体段特性的目标属性，保留目标属性，对其余属性进行二元化，产生频繁项集时，对目标属性在每个段内的分布进行汇总。例：对因特网用户的年龄求平均值得到,年收入,$100K,，网上购物,=,是,-,年龄：均值,=38,这一有趣规则。,方法：假设检验。,实施（针对上面规则）：先对一些符号进行说明，设,u,是满足规则的事物中的年龄的均值，,u,是不满足规则的事物中的年龄的均值。,用户可接受的年龄差（若年龄差小于,，认为无差异）,n1,是满足规则的事物个数，,n2,是不满足规则的事物个数；,s1,是满足规则的事务中年龄的标准差，,s2,是不满足规则的事务中年龄的标准差。,2.3,基于非离散化的方法,文档,word1,word2,word3,word4,word5,word6,文档,1,0.3,0.6,0,0,0,0.2,文档,2,0.1,0.2,0,0,0,0.2,文档,3,0.4,0.2,0.7,0,0,0.2,文档,4,0.2,0,0.3,0,0,0.1,文档,5,0,0,0,1.0,1.0,0.3,对所有文档的平均规范化频率求和,S(word1,，,word2)=(0.3+0.6)/2+(0.1+0.2)/2+(0.4+0.2)/2+(0.2+0)/2=1,，该方法求得的所有支持度都为,1,，无法得出有趣的模式。,运用另一种发现词关联的方法称为,min-,Apriori,。,S(word1,，,word2)=min(0.3+0.6)+min(0.1+0.2)+min(0.4+0.2)+min(0.2+0)=0.6,END,Thank you,