连续值属性约简算法改进

唐寅 闵凉宇

【摘要】目前存在的基于粗糙集理论的属性约简算法多数只适用于离散型数据。而在现实工作中，不仅有符号、类别等离散型数据，更有大量的连续型或实型数据，甚至二者的混合。传统的离散化过程并不能保存属性在数值上的差异，造成了一定程度的信息损失。本文提出一种将模糊聚类和粗糙集相结合的属性约简算法，从而避免了实型数据的离散化。

【关键词】数据 粗糙集 属性约简算法

一、连续值决策表的属性约简

连续值决策表的属性约简主要分为两部分：一，将模糊聚类引入到对象划分中，解决粗糙集在连续数值属性处理上的局限性，同时获得满足一定依赖度要求的Q型模糊聚类最佳参数λQ及对应实例序对（xi，xj）λ，本文将这部分称之为基于模糊聚类和粗糙集的连续型决策表对象离散化；二，对条件属性进行R型模糊聚类，获得期望数目的聚类，并从中选出符合依赖度要求的属性子集即为一个可接受的属性约简。

（一）连续型决策表对象离散化

通过Q型模糊聚类，我们将实型属性的模糊性转化为实例对象的模糊性，依据对象间的模糊近似程度，实现对象的离散化。Q型模糊聚类的最终结果取决于决策类对全部条件属性的依赖度，在数据充分的情况下，可认为这一依赖度的值为1。我们可以获得Q型模糊聚类的最佳参数λQ，及其对应的实例序对（xi，xj）λ。如果属性子集P是条件属性C相对于D的一个合理约简，属性子集P表达的对象模糊相似关系应最大程度地保持条件属性C表达的对象间模糊相似关系。那么序对（xi，xj）λ？劬（i，j）在属性子集P的模糊相似矩阵FMP中，同样具有划分对象的作用。FMP（i，j）是模糊相似关系FMP中，使得分类满足依赖度要求的对象间相似度最低要求。算法如下：

输入：一个实型决策表S=（U，CUD，V，f）。输出：Q型模糊聚类最佳参数λQ及其序对（xi，xj）λ。Step1.决策表数据预处理：补缺、去重等；Step2.计算实例对象间的模糊相似矩阵FMC；Step3.运用直接聚类法进行对象划分，聚类参数λ，得到划分类Uλ；Step4.计算决策类对划分类的依赖度γλ（D），若γλ（D）=θ，转至Step5；否则，调整参数λ，转至Step3；Step5.得到最佳聚类参数λQ，计算其相应序对（xi，xj）λ；对序对（xi，xj）λ的数据行进行再次噪声检查，如果存在多组不受噪声干扰的序对，则从中任选一组；Step6.本部分算法结束，输出最佳聚类参数λQ和相应序对（xi，xj）λ。

（二）连续值属性约简

本文用R型模糊聚类将相似度贴近的属性聚为一类，并从每一类中选择代表性的属性构成属性子集，并以该子集的依赖度是否接近决策属性对全部条件属性的依赖度为标准判断该属性子集是否合理。定义1 设实型决策表S=（U，CUD），条件属性C满足依赖度阈值的最佳聚类参数为λQ，对应序对为（xi，xj）λ，则属性子集P是C相对于D的属性约简：

FMP为基于属性子集P的对象间模糊相似矩阵。

在基于粗糙集的启发式属性约简算法中，往往约简的结果无法由预期控制。而在实际属性约简的工作中，人们通常对约简属性的数目有一个心理预期。同样地，在连续值决策表中也可以运用这种思路求得一个符合预期的可接受属性约简。具体分为以下三个步骤：一，以预期属性数目为主导，对条件属性进行聚类。二，对聚类结果进行属性组合。应当优先选择每一类中平均相似度最大的属性进入属性子集。可以获得一个由最具代表性的属性构成的属性子集P。三，计算属性子集依赖度。基于属性子集计算对象间模糊相似关系FMP，以FMP（i，j）（其中，（i，j）=（xi，xj）λ）为聚类的阈值，得到论域对象的划分，从而获得依赖度γp（D，FMP（i，j））。如果其依赖度满足：

其中，ρ为一接近0的正数，则说明属性子集P为C的一个可接受约简。如果>ρ，说明算法不能满足预期属性规模的属性约简，此时应当调整属性规模预期或选择其它算法。

二、实证

以数据集A（见附录A）的数据为例，说明本部分属性约简过程。在A的决策表S=（U，SUD）中，条件属性集C={c1，c2，…，c7}，设定期望属性数目为z=3。Step1.计算条件属性的模糊相似矩阵FMR7×7。由于案例数据为时间序列，因此选择模糊相似关系为：

Step2.基于FMR，应用直接聚类法对条件属性进行划分，记为Rλ；并以|Rλ=z|为聚类终止条件。Step3.计算每一类中，属性之间的平均相似度：

Step4.构建属性子集，R0.73{1}中的最佳代表属性为c2，R0.73{2}中的最佳代表属性为c4，R0.73{3}中的最佳代表属性为c5。所以，属性子集P={c2，c4，c5}

Step5.计算决策属性对属性子集P的依赖度：γp（D，FMP（（xi，xj）λ））。我们得到（xi，xj）λ=（x14，x15），γc（D，λQ）=0.35。计算基于P的实例对象间的模糊相似关系FMP20×20，ρ的设置不应太小。依赖接近度为0.1，说明约简前后的正域波动为两个对象，是可以接受的。因此，P={c2，c4，c5}是全部条件属性C相对于D的一个可接受约简。事实上，基于全部条件属性C的实例对象的聚类结果：

在两组分类中，只有{6，18}在U_P中发生了合并。这说明，属性子集P不仅较好地继承了条件属性C的划分能力，对其中相对于决策属性的分类能力，更是很好地保留。该种算法可以适用于连续型、离散型以及二者混合的数据类型。

参考文献

[1]Chen Y，Zhu Q，Xu H.Finding rough set reducts with fish swarm algorithm[J].Knowledge-Based Systems，2015，81：22-29.

[2]唐孝，舒兰.基于粒计算的属性约简改进算法[J].计算机科学，2014（32）.

[3]张吉洋，冯长焕.加权模糊相似矩阵的构造[J].统计与决策，2014（20）.

作者简介：唐寅（1991-），男，汉族，贵州金沙人，首都经济贸易大学学生，硕士学位，研究方向：电子商务。