决策表属性集分解的等价性研究摘要：论述了决策表属性集分解的概念和必要性，对分解中的决策等价性问题进行分析，提出了决策表论域上的弱等价条件和部分等价条件，并针对弱等价性判断标准的局限性，进一步提出了决策表样本集取值空间上的强等价条件，使得决策等价性的判断标准更为完备。??关键词：决策表；分解；等价性；属性集??：TP391文献标志码：A：1001－3695(2007)08－0067－03??传统的数据挖掘和知识归纳方法在决策表分析和处理中得到了较好的应用，但是随着数据规模的不断扩大，许多大型决策表含有大量的属性和对象，结构复杂，给数据分析和处理带来不少困难，计算复杂度上升，规则质量和分类精度下降。??属性数量的庞大是造成大型决策表分析困难的主要原因之一，从属性集的角度对决策表进行分解是一种有效的数据转换方法。通过属性集的分解得到的子决策表规模较小且更易于处理，可以减少每次处理的数据量，提高数据分析的效率和质量。分解前后决策分类的等价性是影响决策表分解质量的关键因素，在分解过程中要力求保证决策等价、信息无损，因此有必要建立分解前后决策等价性的判断标准。??1决策表属性集分解??决策表是一种将条件属性和决策属性区分开来的知识表示系统，由对象集、条件属性集和决策属性集组成，是信息系统的一种特殊情况，为数据集中的规则推导和知识发现提供基础。它可以表示为一个四元组：??T=(U,R,V,f)。其中：论域U是对象的集合，R=C∪D是属性集合，子集C和子集D分别是条件属性集与决策属性集，V=∪a∈RV??a是属性值的集合，V??a表示属性a的值域，f:U×A→V是指定U??中对象的属性值的函数。??数据量的不断增大使得许多现有的数据分析方法受到限制，在实际应用中表现为计算复杂度上升，而规则质量和分类精度降低。决策表数据分析中的主要困难之一来自于属性数量的增长，随着属性集的不断扩大，为了建立有效的分类模型，训练集中所需的对象数呈指数级增长，归纳算法的搜索空间也随之扩大，增大了在决策表中进行盲目的知识发现、得到无用分类规则的可能性。另外，根据最短描述长度原理(minimumdescriptionlengthprinciple，MDLP)[1]，分类规则前件中属性过多将影响规则质量，不利于新对象的分类，而属性较少的分类模型更易于理解，适合于用户驱动的数据挖掘过程。针对决策表的复杂性，首先考虑对属性集的处理，力求减小属性集的规模。目前，对多属性决策表大多采用属性约简方法[2]，在保持分类决策不变的前提下删除决策表中的冗余属性，从而减小属性集的规模，其中一些算法取得了较好的效果。但属性约简技术仍存在以下弊端：某些决策表中必要的条件属性很多，经过约简后的属性集可能仍然庞大；约简算法的结果依赖于训练集中对象的数量，若对象较少，约简的质量将受到影响；另外，某些约简算法对于大型决策表效率较低，计算复杂度高。??针对决策表属性集的复杂性和属性约简等技术存在的问题，对决策表进行属性集分解是一种较好的处理方法[3]。其基本思想是将决策表的条件属性集分解为若干子集，它们分别与决策属性构成一个决策子表，所有条件属性子集构成原条件属性集的一个覆盖。对于决策表??T=(U,C∪{d},V,f)，T的一次属性集分解将产生N个子表的集合，每个子表表示为??---本文来源于网络，仅供参考，勿照抄，如有侵权请联系删除---T??i=(U,C??i∪{d},V,f)，i∈{1,…,N}。其中：C??i??C，且∪i∈{1,…,N}??C??i=C。????分解完成后，对原决策表的分析处理，转换为在各子表上分别进行局部规则归纳和推导，然后将它们综合起来的过程。对于不同的决策子表，可以使用相同的归纳学习方法，也可以使用不同的方法，分别得到各子表对应的子规则库，子规则库在学习或分类过程中融合，为新对象的分类提供支持。??决策表的属性集分解减少了每次处理的数据量，使得适合普通决策表的算法也能适用于复杂的大型决策表，各子表之间可以进行并行计算，减小时间复杂度，提高数据分析的效率。通过分解还能增强数据挖掘过程的可理解性和透明度，发现属性之间隐含的关系，采用小样本数据建模的方式提高规则质量和分类精度。??在基于决策表属性集分解的...