基于聚类与粒化度量的高效决策表约简

李敏 杨亚锋 李丽红

摘要：属性约简是粗糙集理论的核心内容之一，传统的属性约简每次只考虑去掉一个属性后对原来知识系统的影响，或者利用区分函数进行约简，但是当数据集较大时，区分函数范式转换获得解集具有一定的困难性，降低约简效率。针对决策系统的属性约简与高效决策的粒度选择问题，将粒化度量和聚类相结合，由聚类结果选择粒结构，再由粒化度量得到各粒结构的重要度，从而进行属性约简。考虑同时去掉多个属性，提高了效率;最后结合实例验证此方法约简与利用区分矩阵的方法约简结果一致。

关键词：属性约简;粒化;粒化重要度;区分矩阵

中图分类号：TP18        文献标识码：A

文章编号：1009-3044（2019）26-0246-03

开放科学（资源服务）标识码（OSID）：

随着现实世界中不确定信息的不断增加，粗糙集[1]、模糊集等这些处理不精确、不一致，不完整信息的数学工具受到越来越多人的关注，粗糙集理论是利用属性约简、信息熵[2]等概念来确定信息表达系统中差别属性的重要性 ，简化知识表达空间，并从数据中挖掘特征规则，通常是通过删除冗余属性来实现的。粒计算方法是以粒为求解问题的基本单位，人类在处理大量复杂信息时，由于人类认知能力有限，往往会把大量复杂信息按其各自特征和性能将其划分为若干较为简单的块，每个被分出来的块就被看成是一个粒，这样处理信息的过程就称为信息粒化，自1979年Zadeh提出信息粒度之后，研究人员便对信息粒度化的思想产生了浓厚的兴趣，其中将粒化问题与属性约简相结合，从相关实际问题的研究背景出发，提出了多种信息系统属性约简的方法。史进玲，张倩倩，徐久成提出了多粒度决策系统属性约简的最优粒度选择[3];朱红，丁世飞在基于属性区分能力和AP聚类的基础上，给出了属性粒化的方法[4];将二进制粒与粒计算结合，陈玉明等人提出了基于二进制粒与粒计算的属性约简[5];文献[6-10]给出了基于粒计算，多粒度和邻域熵下的属性约简。近年来，知识粒度作为一种新的属性约简方式受到研究人员们的关注，因此本文采用二进制粒对决策表进行粒化，计算属性之间的相对依赖度及距离进行聚类;然后根据聚类结果选择粒结构，计算不同粒结构下的粒集，再由粒化度量得到各粒结构的重要度，进行属性约简，最后结合实例验证方法的合理性。

1 基本知识

1.1属性约简相关概念

粗糙集中由于知识库里的属性并不是同等重要的，甚至其中某些属性是冗余的，不利于分析问题，因此使得属性约简成为粗糙集理论比较重要的内容，有着广泛的应用价值，属性约简即在保持知识库分类能力不变的条件下，删除其中不相关或不重要的属性。

1.2 属性粒化相关概念

为了更好地剖析和解决复杂的问题，粒计算将其抽象化为简单的问题，信息粒在我们实际生活中普遍存在，抽象概括了现实问题。粒化是将总体分解为部分，信息粒化反映了人類如何处理和存储信息。

3 实例分析

例：给定一个决策表[S=（U，A，V，f）]：其中对象集合[U={1，2，3，4，5}]，条件属性集[A={a，b，c，d}]，决策属性为[D]，如表1所示。试化简该决策表，并求出约简。

第三步：根据属性之间的相对依赖度，计算属性之间的距离，并根据距离关系进行聚类。

计算属性[a]与其他属性之间的距离之和为[ab+ac+ad≈3.0115]，同理属性[b]与其它属性距离之和为3.5804，属性[c]与其它属性距离之和为4.0048，属性[d]与其它属性距离之和为2.7268。根据距离关系，将属性聚类为两类：[{a，d}]、[{c，b}]。

第六步：通过区分矩阵的方法验证合理性

依据决策表可以得到对应的区分矩阵，如表所示：

得到该决策系统的属性约简集合也为[{a，b}]或[{b，d}]，从而验证了此方法的合理性。

4 结论

以往的决策表属性约简的研究有基于信息熵、博弈论、区分矩阵等进行的，但是大多都基于等价关系给出，这种单一的方法不符合大数据时代所要求的效率问题。因此针对以上不足，本文基于粒化度量与属性重要度考虑同时去掉多个属性，为属性约简开辟了新的途径，使得约简更加高效;本文所提出的算法中如果决策表里有新增加的属性，只需计算该属性与其他属性的依赖程度和距离，重新考虑聚类，再计算粒化度量和粒化重要度进行约简即可，同时也适用于动态约简，比传统的约简算法节省了时间。

本文只是以一个简单实例给出了可以多个属性同时约简的新方法，依然还有很多值得提高的地方，比如是否可以找到更合适的属性聚类的方法与粒化度量结合，或者大数据时代何时选用这种方法等问题，这需要我们以后继续深入研究，给出更加合理有效的约简算法。

参考文献：

[1] 刘保相.粗糙集对分析理论与决策模型[M].北京：科学出版社，2010：11-55.

[2] 于迎春.覆盖粗糙集中基于信息熵的几个定义[J].商业文化，2012（2）：344.

[3] 史进玲，张倩倩，徐久成.多粒度决策系统属性约简的最优粒度选择[J].计算机科学，2018，45（2）：153-156.

[4] 朱红，丁世飞.基于属性区分能力和AP聚类的属性粒化方法[J].计算机科学，2016，43（2）：95-97.

[5] 陈玉明，苗夺谦，焦娜.基于二进制粒与粒计算的属性约简.广西师范大学学报（自然科学版），2008，26（2）：81-84.

[6] 胡清华，于达仁，谢宗霞.基于邻域粒化和粗糙逼近的数值属性约简[J].软件学报，2008，19（3）：640-649.

[7] 杨田，伍秀华，王玉芳.覆盖粗糙集属性约简的新算法[J].模糊系统与数学，2013，27（2）：183-190.

[8] 许晴媛，李进金，张燕兰.覆盖决策信息系统的约简[J].山东大学学报 （理学版），2010，45（1）：89-93.

[9] 谭安辉，李进金，吴伟志. 多粒度粗糙集和覆盖粗糙集间的近似与约简关系[J].模式识别与人工智能2016，29（8）：691-697.

[10] 张小红，裴道武，代建华.模糊数学与rough集理论[M].北京：清华大学出版社，2013：264-265.

[11] 秦克云，敬思惠.决策系统基于不可区分关系及区分关系的约简[J].计算机科学，2018，45（6）：247-250.

[12] 顾沈明，万雅虹，吴伟志，等.多粒度决策系统的局部最优粒度选择[J].南京大学学报（自然科学），2016，52（2）：280-288.

【通联编辑：唐一东】