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

2015-07-18陈燕云肖坤楠邱建林

电脑知识与技术 2015年12期

陈燕云　肖坤楠　邱建林

摘要：将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]，计算价值函数。如果它小于某个确定的阀值，或它相对上次价值函数值的改变量小于某个阀值，则算法停止。