您好, 访客   登录/注册

基于属性关联度的辅助分类模型

来源:用户上传      作者:

  摘 要:提高分类器覆盖率是显露模式分类中的重要内容。通过降低支持度的方法来提升覆盖率,将会大大增加算法时间开销。在CAEP分类模型基础上,分别使用关联分析中常用的卡方检验、置信度和比值比策略,对分类模型中无法被覆盖的事务进行辅助分类。在UCI数据集合下进行对比实验,结果表明,采用了关联分析辅助策略分类模型的分类准确率均有所提升,且额外消耗的时间较少。
  关键词:分类; 显露模式; 卡方检验; 置信度; 比值比
  DOIDOI:10.11907/rjdk.151484
  中图分类号:TP301 文献标识码:A 文章编号:1672-7800(2015)007-0048-04
  0 引言
  显露模式[1-2]分类方法中,模式的选择或者精简是最重要的环节,而模式选择中的一个重要指标,就是模式集合对于测试事务的覆盖率[3-4]。一个覆盖率过低的模式集合,对于分类算法来说,其性能和意义都将大打折扣。解决上述问题,目前有两种主流方案:①降低模式挖掘门槛,即降低支持度[5]、增长率等参数的阈值,挖掘出数量更多、覆盖更全面的模式集合;②采用MDL原则[3],在模式选择阶段选择出覆盖率更好、鲁棒性更好的模式。对于部分数据集合,即使采用降低支持度阈值等方法,也会产生分类模型的覆盖率不足、分类准确率低的情况。其可能的原因是,该数据集合存在分类信息散、特征比较模糊[6]等特点。分类器支持度阈值较高时,模式数量较少,覆盖率较低;当支持度阈值很低时,容易引入噪音模式,影响分类准确率,时间复杂度更高。
  模式的支持度在不同数据集合之间存在显著差异,称为显露模式。在特征明晰的数据集合中,挖掘出拥有高增长率值的显露模式,为分类提供更加确切的信息。在特征比较模糊的数据集合中,显露模式整体的增长率阈值较低,难以描述数据集合之间的特征差异。
  针对分类器的覆盖率问题,本文基于关联分析特性,提出了基于属性关联度的快速辅助分类方法。关联分析方法,能够更大程度地挖掘特征模糊数据集合中属性之间的关联程度,其鲁棒性和适用范围都较好。
  1 基于卡方的属性关联度
  1.1 卡方独立性检验
  卡方检验[7]是以χ2分布为基础的一种常用检验方法,其目的在于监测观察频数与期望频数的差别,下面以简单的例子来说明卡方检验的具体方法。表1为二维的条件概率表,其中变量X和Y是两个不同的二值属性,即X和Y有且仅有两种取值,如:X=0, X=1;Y=0,Y=1。表中的nij满足i, j∈{0,1},表示属性X=i和属性Y=j在数据集合中共现的次数为nij次。ni.表示属性X=i出现的总次数,ni. = ni0 + ni1;同理,n.j表示属性Y=i出现的总次数,n.j = n0j + n1j。
  定义1属性独立性:设X和Y是数据集合D中的属性,如果满足条件P(XY )= P(X ) *P(Y ),则称属性X与属性Y相互独立,否则二者相关。
  定义2属性期望值:期望描绘的是随机变量的平均取值,属性期望值公式如下:
  E(nij)=ni.n*n.jn*n(1)
  卡方独立性检验能够通过观察频数与期望频数的差别,计算属性变量间的独立性大小。卡方值越高,表明属性之间的独立性越小,反之,属性间独立的可能性越大。假设两个属性X和Y独立,计算X和Y属性的卡方值,χ2(X,Y) > 3.84,查表可知,当α=0.5时,拥有95%的置信度区间拒绝该假设成立,也就是说,X和Y独立的可能性仅有5%。
  定义3属性间独立性检验:对于属性X和Y的卡方估计值χ2(X,Y),计算公式如下:
  χ2=∑1i=0∑1j=0(nij-E(nij))2E(nij)(2)
  1.2 卡方评分值归一化
  使用属性与目标类别之间的卡方值作为评分依据,对测试事务分类。由于不同数据集合间的规模不同,个别属性的卡方值较大。如果按照普通累加的方式,很容易出现以偏概全的情况,单个属性决定了事务所属的类别。本文对卡方值进一步处理,采用BaseScore参数伪归一化的方法,降低因为个别属性卡方值过高或者过低带来的评分倾斜。
  本文提出一种新的归一化方法,具体步骤如下:①累加当前属性X与各个类别属性Y的卡方值,Base(Y )=(χ2(X,Y );②计算属性X与每个类别Y的关联程度的权重,Weight(X,Y ) = χ2(X,Y ) / Base(Y )。卡方聚集评分公式如下:
  score(t,C)=∑X∈tweight(X,C)(3)
  算法1为计算条件属性与目标属性之间的卡方值,对卡方值进行归一化,过程见表2。
  2 基于置信度的属性关联度
  置信度(confidence)不仅是数理统计分析中的重要概念,也是规则模式挖掘中的重要参数,具有很强的数理统计意义。拥有高置信度的规则或是模式,能够更加准确、直观地刻画出变量之间内在的概率关系。许多分类模型均采用了置信度这一参数作为规则权值的主要参数,如CBA、CMAR、CPAR等。
  如果测试事务t中的某个属性有较高的置信度划分到指定类别中,则这个属性出现在该类别中的几率比较大。同理,如果测试事务t中的多个属性拥有较高的置信度划分到指定类别中,那么这个事务出现在该类别中的可能性就较大。因此,使用每个属性置信度累加来评判事务所属类别具有一定意义。定义4 置信度评分函数:给定测试事务t以及类别C,计算事务t在类别C中的评分方法如下:
  score(t,C)=∑X∈tconf(X)(4)
  其中,X表示测试事务t中的一个属性,累加t中的所有属性与类别C的置信度,得到该事务属于类别t的可信度。考虑到所有的置信度都在[0,1]的区间范围内,所以无需对数据归一化。最后,将测试事务划分到评分最高的类别中。   3 基于比值比的属性关联度
  比值比(oddsRatio)[8]作为一种测量属性间关联程度的方法广泛运用在关联规则挖掘和分类领域。通过对比的方法,能够准确度量不同数据、不同类别间存在的细微差异,同时也能够对变量属性间的独立性进行判断和检测。
  定义5比值比:给定两个属性X和Y,两者间的比值比j的计算公式如下:
  oddsRatio(X,Y)=supp(XY)*supp(XY)supp(XY)*supp(XY)(5)
  表3为比值比表,其中supp函数表示项集在数据集合中出现的次数。如果oddsRatio(X,Y ) = 0,说明X和Y单独出现,暗含了X和Y互斥;如果oddsRatio(X,Y ) = 1,那么说明X在Y=0和Y=1的两种条件下出现的概率相当,即X与Y无关联关系,相互独立。当oddsRatio(X,Y ) ≠ 1,表明属性X和Y之间存在某种关联关系。
  定义6比值比评分函数:对于给定的事务t,在类别C中评分规则如下:
  score(t,C)=∑X∈toddsRatio(X,C)(6)
  其中,X表示测试事务t中的属性,累加所有属性与类别属性C的oddsRatio值,作为该事务在类别C中的得分。由于比值比的结果区间是[0,+∞],因此,有必要对oddsRatio值进行归一化操作,其归一化方法同卡方检验中的归一化方法相同。算法2中描述了使用比值比评分算法计算属性之间比值比以及归一化过程,其返回值为比值比的表结构。
  4 实验结果分析
  在CAEP分类模型基础上,分别使用卡方检测、条件概率、比值比3种关联分析方法实验,对CAEP分类器无法覆盖的测试事务,进行二次快速分类。为了验证该辅助方法是否有效提升分类的准确率,选用UCI机器学习数据库中的9个数据集进行实验比较。实验中分类准确率均采用十字交叉验证(ten-fold cross-validation)方法,且都在相同的支持度、增长率参数条件下获得。本次实验使用Windows 7 操作系统(32位),Inter i3-2100CPU,3.1GHz,内存4.00GB。
  4.1 分类准确率比较
  实验使用的数据集合未被CAEP分类模型完全覆盖。如表5所示,在CAEP算法的基础上使用了3种关联分析方法对未覆盖事务进行二次分类。表中标记为粗体的数据表示其分类结果高于CAEP模型分类结果。表中9个数据集合,使用卡方检验、置信度和比值比方法辅助CAEP分类模型分类,其分类准确率均有所提升,尤其针对类别数量较多的letRcog、nursery、yeast等数据集合,效果更加明显。CAEP将未覆盖的测试事务划分到默认类别中,当类别数量变多时,会降低默认分类的准确率。卡方、置信度和比值比等方法获取的部分有效信息,对分类有一定程度的促进作用。
  4.2 辅助分类时间开销
  使用的关联分析方法,均作为CAEP分类器的第二级辅助分类手段,其中一个重要原因在于,避免降低支持度阈值所带来的大量时间开销。
  3种关联分析方法的时间复杂度分析:假设数据D有n个属性,m个类别。对于卡方独立性检测,若计算一次卡方值的时间复杂度为x,则所有属性与类别间χ2值的时间复杂度为O(n*m*x)。对于置信度而言,若计算一次置信度的时间复杂度为c,则计算整个训练集合中,属性与类别间置信度值的时间复杂度为O(n*m*c)。假设比值比计算的时间复杂度为r, 则计算整个训练集合中属性与类别间oddsRatio值的时间复杂度为O(n*m*r)。在分类阶段,3种方法均相同,即对测试事务t(长度为w)中的属性遍历一次,时间复杂度为O(w)。因此,3种方法唯一的差别在公式的计算方面。根据公式复杂度给出如下排序O(x)>O(r)>O(c),因此,使用卡方独立检验法的时间复杂度略高于其余两种方法。
  表7给出了3种关联分析方法在分类过程中的时间开销。从表中数据可看出,使用卡方独立检验方法的算法耗时较长,置信度和比值比方法的时间开销相当。即便如次,3种方法的时间开销也是相当小的,其平均时间开销均小于5ms,对整个分类算法而言,几乎可以忽略不计。因此,使用上述3种附加分类策略,不影响分类器性能。
  5 结语
  针对CAEP分类器对于部分数据集合覆盖率低、分类准确率不高的情况,本文提出了3种基于关联分析的策略,辅助CAEP分类器对未被覆盖事务进行二次分类。实验结果表明:使用卡方检测、置信度和比值比这3种关联分析方法作为CAEP分类器的辅助分类策略,能够有效提升分类准确率,时间开销小,基本不影响算法的整体性能。
  参考文献:
  [1] 范明, 刘孟旭, 赵红领. 一种基于基本显露模式的分类算法[J]. 计算机科学, 2004, 31(11): 211-214.
  [2] GUOZHU DONG, XIUZHEN ZHANG.CAEP:classification by aggregation emerging patterns[J].Discovery Science , 1999(5):265-368..
  [3] HAN J, KAMBER M. 数据挖掘概念与技术[M]. 范明, 孟小峰, 译. 北京:机械工业出版社,2004:162-164.
  [4] 段磊, 唐常杰,GUOZHU DONG,等. 基于显露模式的对比挖掘研究及应用进展[J]. 计算机应用, 2012, 32(2): 304-308.
  [5] 朱慧云, 陈森发, 曹杰, 等. 一种新的变化挖掘显露模式及其挖掘算法[J]. 信息与控制, 2013, 42(3): 153-158.
  [6] 李丹. 基于JEP的癌症分类算法研究[D].长沙: 湖南大学, 2011.
  [7] ZHOU JIN,JIUYONG LI. Discovery of causal rules using partial association[C].2012 IEEE 12th International Conference on Data Mining, 2012: 309-318.
  [8] JIUYONG LI, THUC DUY LE, LIN LIU,et al.Mining causal association rules[C].2013 IEEE 13th International Conference on Data Mining Workshops, 2013: 114-123.
  (责任编辑:杜能钢)
转载注明来源:https://www.xzbu.com/8/view-11728147.htm