一种基于聚类划分的并行粗糙集属性值约简算法

陈燕云　肖坤楠　邱建林

摘要：将MATLAB模糊工具箱和粗糙集数据处理工具Rosetta结合在一起使用，提出一种基于模糊C聚类划分的并行粗糙集属性值约简算法，将数据集划分到一个个子系统中处理，大大提高了约简的效率。采用聚类算法进行划分，将相似度高的规则放到一个簇中，便于约简，同时由于不同簇的相异程度较高，可以采用直接合并的方式进行全局选择。

关键词：粗糙集；属性值约简；聚类；并行

中图法分类号：TP18 文献标识码：A 文章编号：1009-3044（2015）12-0176-03

A Parallel Rough Set Attribute Value Reduction Algorithm Based on Clustering Partition

CHEN Yan-yun1 ，XIAO Kun-nan1， QIU jian-lin2

（1.Nantong University Engineering Training Center， Nantong 226019，China；2.College of Computer Science and Technology， Nantong University， Nantong 226019，China）

Abstract： Adopt the parallel idea into rough set attribute value reduction， diving the data set into several sub-systems and processing at the same time， which greatly improve the reduction efficiency. Using clustering division to put the high similarity rules into a cluster to reduce easily， meanwhile， the difference between different clusters contributes to merger directly in global section. Apply the algorithm to corn breeding and it performs better.

Key words： rough set； attribute value reduction； clustering； parallel

粗糙集是由波兰科学家Z.Pawlak[1]提出的一种处理不确定、不精确、不完整信息的新的数据挖掘工具，并从中发现隐含的知识，揭示潜在的信息。与人工智能领域其他一些处理不确定问题的数学工具相比，粗糙集有着它自身的优点。比如统计理论需要知道数据先验概率、模糊集理论需要知道隶属函数等，而粗糙集无需提供问题所需处理的数据集合之外的任何先验信息，避免了带入人为的模糊性，从而更具客观性，这一优点也决定它成为分析不精确系统的一种理想方法。

约简是粗糙集理论的核心问题，可以作为大规模数据集处理的预处理工具，为进一步的数据挖掘工作做准备。约简包括属性约简和属性值约简。属性约简是删除冗余的或不重要的属性，是一个横向约简，目前关于粗糙集属性约简的研究已经比较成熟。但属性约简后的数据集还不是最简的，属性值约简实际就是除去多余的属性值，用较少的条件属性来区分每个决策类，从而得到最简的规则集。目前已经提出了一些属性值约简算法，比较经典的是文献[2]，它根据删除某个属性值后决策表出现的不同状况标记不同的符号，并对不同的符号用不同的处理方法，从而删除冗余的记录。此外，还有黄燕等[3]提出的基于相似矩阵的约简算法，以及张学斌等[4]提出的启发式的属性值约简算法等等。

本文在常规属性值约简算法的基础上，用并行的思想来处理约简。决策表的每一行代表一条规则，采用基于聚类的划分思想，将相似度较高的规则放到一个簇中，这样容易产生冗余或矛盾，并且由于簇与簇之间的相异度较大，因而在全局选择时，就将个子系统约简后的规则之间合并得到最终结果。

1 基础知识

定义1：知识表达系统S可以表示为四元组，即S=（U， A， V， f）。其中，U是一个有限的非空集合，称为论域；A=[C?D]是属性集合，C是条件属性，D为决策属性，[C?D=φ，V=a∈AVa]，性值的集合；f ： U [×]A [→]V 是一个信息函数，它为每个对象赋予一个信息值。在粗糙集理论中，知识表达系统又被称为信息系统，通常用S=（U，A）表示[2]。

定义2：设S=（U，A）为一信息系统，[B?A]，则不可分辨关系表示如下：

[IND（B）=（x，y）∈U×U|?b∈B，f（x，b）=f（y，b）]

若[（x，y）∈IND（B）]，则称[x]和[y]是B不可区分的，即相对于B是不可分辨的。不可分辨关系又称为等价关系。对于[x∈U]，它的B等价类定义为[[x]B=y∈U|（x，y）∈IND（B）]，[U/IND（B）=X1，X2…，XK]表示关系[IND（B）]在U上的等价类族，简记为[UB]。

定义3：对于任意的[x?U，B?A]， X 的 B下近似集和 B上近似集分别描述为：

[B（X）=?x∈U：IB（x）?X]

[B（X）=?x∈U：IB（x）?X≠φ]

集合X的B边界域为：[BNB（X）=B（X）-B（X）]

[B（X）]是由那些根据B判断一定属于X的U中元素组成的集合；[B（X）]是那些根据B判断可能属于X的U中的元素组成的集合；而那些根据B判断可能属于但又不能完全肯定属于X的对象所组成的集合称为边界域。

另外，正域、负域定义如下：

正域：[POSB（X）=BX]；

负域：[NEGB（X）=BX]。

定义4：粗糙度是表示知识的不完全程度，由等价关系B定义集合X的粗糙度为：

[ρB（X）=1-B（X）B（X）]

其中[X≠φ，X]表示集合X的基数，显然有[0≤ρR（X）≤1]。

2 基于模糊聚类划分的并行粗糙集属性值约简算法

2.1 划分策略

对于并行约简来说，最终的约简是建立在对子表进行并行计算的基础上实现的，因此，如何划分子表是并行约简的前提，并且划分策略的好坏将直接影响到最终并行约简的结果。找到一种高效、易实现、兼顾精准性的子表划分策略一直都是并行计算研究工作的重点。

本文将采用基于聚类的划分思想，将将相似度较高的规则放到一个簇中，这样容易产生冗余和矛盾，便于约简，另外由于簇与簇之间的相异度较大，因而在全局选择时，就将个子系统约简后的规则之间合并得到最终结果。这里的聚类算法我们选择模糊C均值聚类，算法对于满足正态分布的数据聚类效果会很好，但对孤立点是敏感的。不过我们这里只是进行划分，聚类的效果不用特别精确。我们可以采用MATLAB模糊工具箱中的聚类函数直接处理数据。用到的几个函数如下：

[center， U， obj_fcn]=fcm （data， cluster_n）；

maxU=max（U）；

index1=find（U（1，：）==max U）； %查看第一类别的元素

……；

Index n=find（U（n，：）==max U）；

其中：data为给定数据集，cluster_n为用户提供的聚类中心的个数，center为迭代以后得到的聚类中旬，U为所有数据点对聚类中心的隶属度函数矩阵，obj_fcn为迭代计算过程中的变化值。

2.2 基于模糊聚类划分的并行粗糙集属性约简算法

输入：决策系统[S=（U，C?D，V，f）]；

输出：约简后的决策规则。

1） 用值在0，1间的随机数初始化隶属矩阵U，使其满足式[i=1cuij=1，?j=1，2，…，n]

2） 用式[ci=j=1nuijmxjj=1nuijm]计算c个聚类中心[ci]，i=1，…，c。

3） 根据[J（U，c1，…，cc）=i=1cJi=i=1cjnuijmdij2]，计算价值函数。如果它小于某个确定的阀值，或它相对上次价值函数值的改变量小于某个阀值，则算法停止。

4） 用[uij=1k=1c（dijdkj）2/（m-1）]计算新的U矩阵。返回步骤2

5） 并行地在各类别中进行属性值约简；

6） 将各值约简后的规则合并，去除冗余得整体的最终约简。

本文的模糊C均值聚类算法采用MATLAB模糊工具箱里的FCM函数进行处理，而属性值约简在粗糙集数据处理软件Rosetta上进行。

3 实例分析

实例选用属性约简后的南通市2006年年终汇总（Y组）玉米样本集（表1）为例，实现粗糙集属性值约简算法的应用。该样本集包括51个玉米样本和9个重要属性，分别是生育期、株高、穗高、穗长、穗粗、千粒重、穗行数、行粒数、小区产量。其中前面八个是条件属性，区产量为决策属性。

1） 如果采用对该数据集直接进行属性值约简，得到的结果如表2。

2） 我们采用并行处理方法：① 用MATLAB得到的聚类结果如表3。

②各类簇分别进行属性值约简最终合并的规则如表4。

3） 实验结果分析

将实例最后的约简结果与不进行划分而直接属性约简的结果进行对照分析可以看到，并行处理结果无论在规则的数量上减少了，并且在规模上有了很大的压缩，这说明，该数据集得到了较好的数据挖掘，得到了大量数据中最为关键的知识，并行方法的运用是切实有效的。

4 结束语

粗糙集理论已经被证明是十分有效的工具，它在工业、商业等领域都已经成功运用，本文采用并行粗糙集属性约简方法来处理农业领域的玉米品种资源数据，为后续步骤中选育优良品种提供了有效支持。最后这样一个并行的处理方式将便于增量式管理，可以新增加的样本可以的单独作为一个簇参与处理，因而它将发挥更大的作用。

参考文献：

[1] Pawlak Z. Rough Set [J]. International Journal of Information and Computer Science， 1982，11（5）： 314-356.

[2] 常犁云，王国胤， 吴渝. 一种基于Rough Set理论的属性约简及规则提取方法[J].软件学报， 1999， 10（11）： 1206-1211.

[3] 黄艳， 沈维燕. 基于粗集理论的属性值约简算法研究[J]. 金陵科技学院学报， 2009， 25（4）： 29-32.

[4] 张学斌， 丁晓明. 一种基于关联规则的属性值约简算法[J]. 西南师范大学学报， 2005， 30（3）： 440-443.