决策表属性集分解的等价性研究
传统的数据挖掘和知识归纳方法在决策表分析和处理中得到了较好的应用,但是随着数据规模的不断扩大,许多大型决策表含有大量的属性和对象,结构复杂,给数据分析和处理带来不少困难,计算复杂度上升,规则质量和分类精度下降。
属性数量的庞大是造成大型决策表分析困难的主要原因之一,从属性集的角度对决策表进行分解是一种有效的数据转换方法。通过属性集的分解得到的子决策表规模较小且更易于处理,可以减少每次处理的数据量,提高数据分析的效率和质量。分解前后决策分类的等价性是影响决策表分解质量的关键因素,在分解过程中要力求保证决策等价、信息无损,因此有必要建立分解前后决策等价性的判断标准。
1决策表属性集分解
决策表是一种将条件属性和决策属性区分开来的知识表示系统,由对象集、条件属性集和决策属性集组成,是信息系统的一种特殊情况,为数据集中的规则推导和知识发现提供基础。它可以表示为一个四元组:T=(U,R,V,f)。其中:论域U是对象的集合,R=C∪D是属性集合,子集C和子集D分别是条件属性集与决策属性集,V=∪a∈RVa是属性值的集合,Va表示属性a的值域,f: U×A→V是指定U中对象的属性值的函数。
数据量的不断增大使得许多现有的数据分析方法受到限制,在实际应用中表现为计算复杂度上升,而规则质量和分类精度降低。决策表数据分析中的主要困难之一来自于属性数量的增长,随着属性集的不断扩大,为了建立有效的分类模型,训练集中所需的对象数呈指数级增长,归纳算法的搜索空间也随之扩大,增大了在决策表中进行盲目的知识发现、得到无用分类规则的可能性。另外,根据最短描述长度原理(minimum description length principle,MDLP)[1],分类规则前件中属性过多将影响规则质量,不利于新对象的分类,而属性较少的分类模型更易于理解,适合于用户驱动的数据挖掘过程。针对决策表的复杂性,首先考虑对属性集的处理,力求减小属性集的规模。
目前,对多属性决策表大多采用属性约简方法[2],在保持分类决策不变的前提下删除决策表中的冗余属性,从而减小属性集的规模,其中一些算法取得了较好的效果。但属性约简技术仍存在以下弊端:某些决策表中必要的条件属性很多,经过约简后的属性集可能仍然庞大;约简算法的结果依赖于训练集中对象的数量,若对象较少,约简的质量将受到影响;另外,某些约简算法对于大型决策表效率较低,计算复杂度高。
针对决策表属性集的复杂性和属性约简等技术存在的问题,对决策表进行属性集分解是一种较好的处理方法[3]。其基本思想是将决策表的条件属性集分解为若干子集,它们分别与决策属性构成一个决策子表,所有条件属性子集构成原条件属性集的一个覆盖。对于决策表T=(U,C∪{d},V,f),T的一次属性集分解将产生N个子表的集合,每个子表表示为Ti=(U,Ci∪{d},V, f),i∈{1,…,N}。其中:CiC,且∪i∈{1,…,N}Ci=C。
分解完成后,对原决策表的分析处理,转换为在各子表上分别进行局部规则归纳和推导,然后将它们综合起来的过程。对于不同的决策子表,可以使用相同的归纳学习方法,也可以使用不同的方法,分别得到各子表对应的子规则库,子规则库在学习或分类过程中融合,为新对象的分类提供支持。
决策表的属性集分解减少了每次处理的数据量,使得适合普通决策表的算法也能适用于复杂的大型决策表,各子表之间可以进行并行计算,减小时间复杂度,提高数据分析的效率。通过分解还能增强数据挖掘过程的可理解性和透明度,发现属性之间隐含的关系,采用小样本数据建模的方式提高规则质量和分类精度。
在基于决策表属性集分解的学习和分类过程中,数据分析的效率和质量与分解方法密切相关。目前出现的一些属性集分解方法,如文献[4]提出的根据属性类型的分解方法、文献[5]提出的基于函数分解的方法、文献[6]提出的属性集分解及贝叶斯合成方法等,在原理和特性上存在差异,在实际应用中须根据给定问题的具体情况和数据本身的特点,选择合适的分解方法提高计算效率和分类质量。
2分解的决策等价性判断
对大型决策表进行分解的目的是在规模相对较小的子决策表中建立模型获取知识,通过局部的规则推导降低数据分析过程的复杂度。当对新对象进行分类时,综合局部知识得到决策结果,其中的关键是各子表得到的规则库能相互协作[7],即综合不同的子规则库对同一对象进行分类时,得到的决策结果不会与原决策值产生矛盾。
分解的决策等价性是指通过原决策表归纳所得的决策结果与分解后综合各子表局部规则得到的决策结果相同。属性集分解过程中,由于子决策表属性个数减少,仅由部分条件属性推导的规则可能出现泛化,增大了分类决策的不确定性。决策表的属性集分解方法应保证分解前后的决策等价和信息无损,避免决策表分解对分类结果带来的不确定性。
3强等价判断标准
分解的弱等价条件仅保证了决策表论域中所有对象分解前后的决策等价性,而上述强等价条件在决策表样本集的取值空间下进行判断,不仅保证了原决策表中所有对象分解前后决策等价,而且考虑了不包含于原决策表中,但是能够由决策子表局部分类的对象,更加严格地限定了分解过程中决策等价性的条件。强等价条件比弱等价条件更为全面、完备,进一步避免了使用子表决策带来的不确定性。
4结束语
属性集的分解是处理大型决策表复杂特性,提高数据分析效率和质量的有效手段,分解前后决策的等价性是影响决策表分解质量的关键因素,在分解过程中要力求保证决策等价。通过定义局部决策函数,提出了基于决策表论域的弱等价条件和部分等价条件,针对弱等价性判断标准的局限性,进一步提出了决策表样本集取值空间上的强等价条件,从更加严格的层次保证了分解过程中的决策等价性。通过决策等价条件对决策表属性集分解进行考察,可判断分解前后决策分类是否一致,减小子表决策存在的不确定性,避免分解带来的信息损失和分类结果的矛盾。