基于粗集的频率约简与动态约简对不一致表分类的方法
摘 要：针对不一致决策表对于信息分类精度与稳定性的不利影响，提出基于粗集理论的利用不同形式频率约简与动态约简技术相结合的信息分类方法。首先利用频率约简对不一致决策表进行一致性处理，然后利用动态约简技术对获取的一致决策表进行分类。通过测试系统计算表明，充分结合两者的优良特性，在不损失数据信息前提下，提高了不一致决策表的分类精度和稳定性。
关键字：不一致决策表；分类；动态约简；频率约简；粗糙集
中图法分类号：TP301.6 文献标识码：A DOI：10.3969/j.issn.1003-6970.2013.06.015
0 引言
粗糙集（rough set）理论是波兰学者Pawlak提出来的研究不精确、不确定性知识的表达、学习和归纳方法的数学工具，已广泛地应用于机器学习、知识获取、决策分析、数据挖掘、专家系统、决策支持系统、归纳推理、矛盾归结、模式识别等领域。运用Rough集理论对决策表进行约简或分类时，常会遇到两种决策表，即一致决策表和不一致决策表。由于从一致决策表中得到的决策规则都是确定的，而来自于不一致决策表的规则却存在着不确定性（即规则可能有着多个决策值或可能将新对象归类到多个决策类中），这严重影响了决策知识和对象分类的正确性。然而，由于数据采集的定义、规范以及操作等方面的原因，所得到的决策表常常是不一致的。如何消除或尽量降低不一致决策表在知识发现和数据挖掘中的负面影响，成了信息系统知识提取的重要研究问题。
文献[1]中提出，将不一致决策表分化为完全一致决策表和完全不一致决策表，采用完全一致决策表进行数据分析，这与文献[2]中提出的数据清洗方法类似。这两种方法从决策表中去掉了不一致对象，从而损失了隐含在这些对象之中的知识信息。文献[3]中，引入条件属性矩阵，定义了多种形式的频率约简（即分配约简、分布约简和最大分布约简），通过定义相应的决策矩阵，并通过条件属性矩阵与决策矩阵的计算提取相应决策规则，充分利用了系统所蕴含的信息。利用频率约简，提高了通过不一致决策表进行约简或信息分类的精确性；但产生约简的方法是标准的Rough集方法，对于新对象的分类不总是足够充分的（参看[4，5]），因为该方法没有考虑到部分的约简可能是混乱、不规则的，对于决策表随机采样的子表而言常常是不稳定的。为了提高决策表约简和分类的稳定性，文献[4，5]中提出了动态约简理论，通过随机产生众多基于决策表的子表，并在子表基础上计算约简结合，最后采用权重法来分类新对象。
本文提出利用上述不同形式频率约简与动态约简技术相结合的信息分类方法，来求取不一致决策表相应的决策约简和解决对象分类的冲突问题，从而获得较高的分类精度和分类稳定性。在该方法的基本计算流程基础上，研制了基于JAVA的RoughTool处理系统，并利用经典数据经行了测试与验证。
1 基本理论研究
经典的Rough集理论是建立在对象空间的等价类之上，采用上近似、下近似和边界的概念来分析对象空间中不能由等价关系定义的子集的性质，是一种利用三值逻辑处理不精确或不完全信息的形式化方法。在此对经典Rough不作累述，仅对频率约简与动态约简相关理论进行归纳与分析。
1.1 不一致决策表
称是一个决策系统（或决策表），其中是非空有限对象集合，是非空有限条件属性集合，为非空有限决策属性集合。当为单元素集合时，将决策系统写为。
决策表，若则称是一致的，否则是不一致的。其中表示属性集定义在上等价类。
从一致决策表中得到的决策规则都是确定的，而从不一致决策表中得到的规则是不确定。
1.2 决策表的频率约简
不一致决策表的基本特征是不满足。文献[3]中通过在Rough集中引入概率统计理论，研究Rough成员函数的统计特性，基于规则前件与后件在决策表中出现的频率，提出了几种约简形式，在不损失数据信息的情况下将不一致表转化为相应的一致表，从而给出了一个在不一致决策表上应用Rough集理论进行数据挖掘和分类的解决方案。
1.2.1 _约简
决策表，属性子集，令为其扩展决策函数，其中。显然，当都为1时，是一致的，否则是不一致的。在不一致表的条件下，对应于的规则可表示为：。
，是一个_决策约简，当且仅当是一致决策表的一个约简。
1.2.2 _约简
决策表，属性子集，定义Rough成员函数为：。令规则的自信度为
则表示以自信度归类到。最后令
，是一个_约简，当且仅当是来一致决策表的一个约简。
通过令阀值，获得对应不同取值[0，1]的_约简形式。如令对应的一致表为。
1.2.3 _约简
的决策值序列为，Rough成员分布函数，则得到
其中对于每一向量有一个_决策规则。
，是一个_约简，当且仅当是来一致决策表的一个约简。
采用上述多种形式的频率约简方法可以得到基于不一致决策表的约简集合，利用该约简集的规则对新对象分类时，可以采用权重分类法，进行计算后，将新对象归类到最可信的决策类中。
1.3 决策表的动态约简
通过上述频率约简概念将不一致表转化为对应形式的一致表后，为了进一步提高信息分类的精度和稳定性，文献[4，5]中给出了动态约简技术。动态约简通过对决策表进行大规模随机抽取的子表产生一个约简集合，并在此基础上采用权重法来分类新对象。动态约简从某种程度上来说是最稳定的约简，因为他们在决策表随机采样的子表中具有最大的出现概率。
1.3.1 动态约简的定义
决策表，为通过大规模随机对象抽取产生的所有子表集合。，则的_拓广动态约简定义为：
，
其中表示的约简集合。进一步定义
为拓广动态约简的稳定因子。通过调节稳定因子，我们可以选取那些满足某一稳定阀值的动态约简，从而增加了约简的稳定性和可靠性。
1.3.2 动态约简的计算方法
1）计算给定决策表的子表集合。利用给定的百分比系数（子表的对象数 / 原始表的对象数）例如：50%、60%等等，从原始表中随机的抽取行，每一百分比可以抽取一定数目的子表，如10个。为了满足使该过程能产生最优的分类未知对象的能力，实践证明[4，5，6]，产生子表集应满足下面两个条件：
①百分比系数尽量大，
②子表总个数应≥300。
2）计算子表集的所有约简集。
3）利用稳定系数选取满足设定阀值的约简集。
4）计算每一约简的约简域。
5）利用约简及约简域求取决策规则
2 频率约简与动态约简组合分类方法
根据上述数学模型及定义，针对不一致决策表对于信息分类精度与稳定性的不利影响，本文利用不同形式的频率约简与动态约简技术相结合的来对信息进行分类的方法。主要分为两个处理过程：
1）利用多种形式的频率约简技术将不一致决策表进行一致性处理。
2）利用动态约简技术对上步中获取的一致决策表进行约简和分类计算。
2.1 算法总体流程
采用频率约简与动态约简组合分类算法的总体处理流程图如图1所示。
2.2 RoughTools分析系统
根据上述算法总体流程图，研制了基于粗糙集理论、频率约简以及动态约简理论的分析工具系统RoughTools。该系统在JAVA环境下开发，主要完成以下功能：
1）数据输入输出。
①读取或输出给定用于分析的决策表，并进行关于对象、属性等的各种统计；
②读取或输出各种中间结果数据，例如约简集、规则集等。
2）基于Rough理论的分析模块。
①计算给定属性集合的等价类；
②计算上、下近似以及边界；
③判断表的一致性；
④计算不一致决策表的、、的一致决策表；
⑤利用不分明矩阵求取决策表的约简（穷尽法、覆盖法等）；
⑥利用、、的一致决策表形式，计算各形式的频率约简；
⑦计算给定阀值动态约简。
3）对象分类。利用权重分类法以及动态规则强度等协商机制对给定的对象集合分类，计算分类精度。
3 测试及分析
为了验证采用频率约简与动态约简组合分类不一致决策表方法的有效性，在RoughTools分析工具的基础上，进行了两组测试。
1）比较数据清洗（简写为CUT），单独的、、约简，以及组合、、约简（简写为__）方法对不一致决策表分类的精度。
本测试采用著名的Monk问题1所提供的数据，该数据由训练集（124个对象）和测试集（432的对象）组成，包括6个条件属性和1个决策属性（两个决策类）。由于原始数据表是一致的，为了用于研究，我们从数据中随机的删去两列（两个属性），使其成为不一致决策表。分类测试结果见表1。
从表1可以看到：
①无论是对训练集分类还是对测试集分类，数据清洗方法的分类精度明显低于其他处理方法，显然不一致决策表中蕴藏的信息对计算决策规则是至关重要的，所以利用频率约简技术对于不一致决策表能够获得更高的分类精度。
②组合使用、、约简共同计算最终约简集的分类方法要比单独使用其中一种方法获得的分类精度高，这说明权重分类技术在平衡不同形式约简分类技术上中获得了成功。
2）比较仅使用__方法和将__与动态约简相结合的方法对不一致决策表分类的精度。
本测试中，采用Monk问题1、问题3以及ROSETTA示例的Cleveland医疗数据，同样采用如测试1中的方法将数据转化为不一致决策表。在计算动态约简过程中，对训练数据集按如下方法随机地选取子表：
①子表对象为训练集对象的比例为 90%， 91%，92%，93%，94%，95%，96%，97%，98%，99%，
②每一比例选取30个子表，总共300个子表。
由文献[7]可知上述动态约简子表的选取方法不仅从子表规模上是足够的，而且其获得的动态约简也更为稳定。测试结果见表2。
显然应用动态约简技术后，所得到的分类精度获得了更进一步的提高。
4 结论
本文针对不一致决策表，利用文献[3]中提出的基于频率意义定义的多种决策约简形式，组合动态约简理论（参见[4，5]），充分结合两种约简方法的优良特性，求取约简并进行对象分类。该方法充分利用了不一致决策表所蕴涵的信息，获得了较高的分类精度和稳定性，是一种处理不一致决策表的有效方法。
参考文献
[1]刘清. Rough集及Rough推理[M]. 北京：科学出版社，2001，9.
[2]谭天乐，宋执环，李平. 信息系统数据清洗、规则提取的矩阵计算[J]. 信息与控制， 2003， 32（4）： 289-294.
[3]Lech Polkowski，Shusaku Tsumoto，Tsau Y.Lin. Rough set methods and application：new developments in knowledge discovery in information systems[M]. Physica-Verlag Heidelberg，2000，235-285
[4] Bazan J.， Skowron A. and Synak， P. Dynamic reducts as a tool for extracting laws from decisions tables[M]. in： Z. W. Ras， M. Zemankova （eds.）， Proceedings of the Eighth Symposium on Methodologies for Intelligent Systems Charlotte， NC， October 16-19， Lecture Notes in Artificial Intelligence 869， Springer-Verlag （1994）， 346-355.
[5]Jan G. Bazan. A comparison of dynamic and non-dynamic rough set methods for extracting laws from decision tables[M]. in：Rough sets in knowledge discovery. Heidelberg： Physica-verlag （1998） 321-365
[6]JAN G. BAZAN. Dynamic reducts and statistical inference[J]. In： Proceedings of the Sixth International Conference， Information Processing and Management of Uncertainty in Knowledge- Based Systems （IPMU’96）， July 1-5， Granada， Spain （1996） 2 1147-1152
[7]JAROSLAW STEPANIUK. Knowledge discovery by application of rough set models[M]. in： Lech Polkowski，Shusaku Tsumoto，Tsau Y.Lin， Rough set methods and application： new developments in knowledge discovery in information systems。Physica-Verlag Heidelberg， 2000， 173-174.
[8]黄兵，周献中. 不一致决策表中规则提取的矩阵算法[J]. 系统工程与电子技术， 2005， 27（3）： 441-445
[9]王国胤.决策表核属性的计算方法[J].计算机学报， 2003（5）：611-615.
[10]刘亚波，胡陈勇，刘大有.基于粗糙集的识别矩阵值简式求取算法DMBVR[J].吉林大学学报（理学版）， 2004，42（2）：221-225.
[11]鄂旭，高学东，武森，张秋月.信息表中不完备数据的填补方法[J].北京科技大学学报，2005，27（3）：364-366.
[12]ROSETTA—A Rough Set Toolkit for Analysis of Data， M Kierczak et al[CP/DK]. [2009-5-19]. http：//.cn/qkpdf/ranj/ranj201306/ranj20130615-2.pdf" style="color:red" target="_blank">原版全文