一种改进的粗糙集聚类算法

王一萍++孙明

摘要：针对传统通聚类算法大都是研究非重叠、无法解决现实普遍存在的重叠聚类现象的问题，提出一种改进的粗糙k-means聚类算法。并将这Lingas提出的k-means聚类算法与本文算法应用到林业数据集中进行比较。测试结果证明，改进后的方法聚类效果较好，在整个范围内都能提供有意义的结果。

关键词：聚类 粗糙集 重叠

中图分类号：TP313；G642.0 文献标识码：A 文章编号：1007-9416（2014）08-0134-02

聚类分析[1]属非监督性模式识别，是数据挖掘等领域广泛应用算法，如商业、生物等行业。聚类是按某相似性度量法将有相似特征样本归为一类，使类内相似度大，类之间差异大。已有聚类算法大都是研究非重叠问题，但现实中重叠聚类现象很普通，如社会网络中基于个人兴趣、职业等聚集，很多人同属几个聚集；代谢网络中基于功能聚集，有些蛋白质同属几个功能小组等。Steve Gregory提出模糊重叠聚类[6]，但事先需隶属度函数确定每个数据属于各个聚集，建立样本对于类别不确定性的描述。Lingas等人提出了粗糙k-means算法，但边界域中节点受初始设置阈值和重复因子影响较大，基于此，笔者通过改进的粗糙k-means来克服此缺点。

1 粗糙聚类算法

加拿大学者Lingas将RS理论[2]-[4]引入K-均值聚类，提出了RSK-均值算法。引入RS 的3条公理，（1）1个数据对象至多属1个聚类和下近似；（2）属1个聚类下近似成员同时也是这个聚类上近似成员；（3）如1个数据对象不隶属于何1个聚类下近似，则它一定至少是2个聚类上近似成员。笔者采用的变量如下。

粗糙集聚类算法描述如下：

第1步：初始化，设置聚集数K和阈值。随机分配k个数据对象作为聚集下近似对象，由上面公理3得这个对象也属该聚集的上近似。然后将其余N-k个数据分配到1个离其最近的聚类中。

第2步：计算每个聚集新的质心。质心计算（均值函数）为公式（1）。

和是聚集下近似和边界域的权重。

第3步：将数据对象分配到聚集的近似集中。对于Xn确定离它最近的质心，使用公式（2）将数据分配到聚集的上近似中。使用公式（3）确定质心，对于给定阈值，求集合T。

如果不空，则除距离很近外，距离T中任意t对应的也很近，则；否则，。

第4步：检查算法的收敛性，即聚类是否变化。如果没有收敛继续第2步，否则算法结束。

2 改进的粗糙K-means算法

本文在Lingas提出的粗糙k-means算法上做了修改，使用相对阈值代替Lingas的K-means中的绝对阈值。算法步骤如下。

第1步：初始化。随机分配每个数据到1个下近似中，由RS公理2得此数据也属同一聚类上近似。

第2步：使用公式4计算每个聚集的新的均值。

第3步：为使每个聚集下近似至少有1个成员，即有：，由前公理2得，将每个数据对象分配到近似集中，1）最能代表1个集群的数据对象分配到它的上下近似中。

（1）计算所有对象与各个聚集的离，找到数据对象和聚集，使得距离聚集最近，则将数据分配到聚集的下近似和上近似中。计算过程中使用公式5：

（2）如果在（a）中有还有一些聚集没有被分配到数据对象，即聚集的下近似为空，则返回（a）继续将离每个聚集最近的1个数据分配到其下近似中，否则继续第3）步。

（3）将剩余 N-k个数据对象，利用公式（2）确定离它最近的质心，将分配到聚集的上近似中。（3）确定是否有聚集，它的质心和的距离与和的距离的比在事先规定的阈值范围内，即满足公式（6）。

如不空，则说明除离近，距离中任何对应质心也很近，所以将分到聚集上近似中；否则，属于的下近似。

第4步：检查算法是否收敛，如不收敛，则继续执行第（3）步，否则结束。

3 实验

对本文算法进行测试，与Lingas等人的算法在DBI结果进行比较。实验中选择wl=0.7、wu=0.3。

数据源来源于知识发现数据源网的林业数据，它描述30×30米区域森林覆盖类型。有581012条记录含54个属性，10个数值变量，其余为二进制型，数值中有1个属性描述7种森林植被类型（如云杉、杨木等）。对数据进行预处理，从中随机选择2345个记录及10个数值属性，设置集群数为7，表示森林覆盖类型。数据归一化为[0，1]。设重复因子r=50，imax=500。

聚类结果分析：Lingas等人算法选择=0.0，…，0.0125时，提供了有意义结果，如图1描述。图中显示边界区数据对象对的依赖性。高的重复因子r对于较大值将导致稳定最优值，但算法所需时间显著增加，同时算法收敛性也下降。相比之下，本文聚类算法在整个范围内都能提供有意义的结果，边界区域的对象数从0到2338（见图2）。

一般改进的算法也表示DBI值略有改善，如图3所示。值得注意是，Lingas算法对于边界域中有大量数据对象时，由于大的使算法的收敛性降低。且重复因子r能导致更好DBI，但是以降低效率作为代价的。

4 结语

笔者提出一些方案。通过引入一个改进的粗糙k-means，在森林数据集上成功测试验证了本文算法的有效性。

参考文献

[1]聂舟，程远国.一种基于平均相对偏差的聚类算法[J].兵工自动化，2008，27（8）：32-34.

[2]Pawlak Z.Rough Sets[J].Journal of Information and ComputerSciences，1982，11（5）：145-172.

[3]胡云，苗夺谦，王睿智等.一种基于粗糙k均值的双聚类算法[J].计算机科学，2007，34（11）：174-177.

[4]郑超，苗夺谦，王睿智.基于密度加权的粗糙k均值聚类改进算法[J].计算机科学，2009，36（3）：220-222.endprint

摘要：针对传统通聚类算法大都是研究非重叠、无法解决现实普遍存在的重叠聚类现象的问题，提出一种改进的粗糙k-means聚类算法。并将这Lingas提出的k-means聚类算法与本文算法应用到林业数据集中进行比较。测试结果证明，改进后的方法聚类效果较好，在整个范围内都能提供有意义的结果。

关键词：聚类 粗糙集 重叠

中图分类号：TP313；G642.0 文献标识码：A 文章编号：1007-9416（2014）08-0134-02

聚类分析[1]属非监督性模式识别，是数据挖掘等领域广泛应用算法，如商业、生物等行业。聚类是按某相似性度量法将有相似特征样本归为一类，使类内相似度大，类之间差异大。已有聚类算法大都是研究非重叠问题，但现实中重叠聚类现象很普通，如社会网络中基于个人兴趣、职业等聚集，很多人同属几个聚集；代谢网络中基于功能聚集，有些蛋白质同属几个功能小组等。Steve Gregory提出模糊重叠聚类[6]，但事先需隶属度函数确定每个数据属于各个聚集，建立样本对于类别不确定性的描述。Lingas等人提出了粗糙k-means算法，但边界域中节点受初始设置阈值和重复因子影响较大，基于此，笔者通过改进的粗糙k-means来克服此缺点。

1 粗糙聚类算法

加拿大学者Lingas将RS理论[2]-[4]引入K-均值聚类，提出了RSK-均值算法。引入RS 的3条公理，（1）1个数据对象至多属1个聚类和下近似；（2）属1个聚类下近似成员同时也是这个聚类上近似成员；（3）如1个数据对象不隶属于何1个聚类下近似，则它一定至少是2个聚类上近似成员。笔者采用的变量如下。

粗糙集聚类算法描述如下：

第1步：初始化，设置聚集数K和阈值。随机分配k个数据对象作为聚集下近似对象，由上面公理3得这个对象也属该聚集的上近似。然后将其余N-k个数据分配到1个离其最近的聚类中。

第2步：计算每个聚集新的质心。质心计算（均值函数）为公式（1）。

和是聚集下近似和边界域的权重。

第3步：将数据对象分配到聚集的近似集中。对于Xn确定离它最近的质心，使用公式（2）将数据分配到聚集的上近似中。使用公式（3）确定质心，对于给定阈值，求集合T。

如果不空，则除距离很近外，距离T中任意t对应的也很近，则；否则，。

第4步：检查算法的收敛性，即聚类是否变化。如果没有收敛继续第2步，否则算法结束。

2 改进的粗糙K-means算法

本文在Lingas提出的粗糙k-means算法上做了修改，使用相对阈值代替Lingas的K-means中的绝对阈值。算法步骤如下。

第1步：初始化。随机分配每个数据到1个下近似中，由RS公理2得此数据也属同一聚类上近似。

第2步：使用公式4计算每个聚集的新的均值。

第3步：为使每个聚集下近似至少有1个成员，即有：，由前公理2得，将每个数据对象分配到近似集中，1）最能代表1个集群的数据对象分配到它的上下近似中。

（1）计算所有对象与各个聚集的离，找到数据对象和聚集，使得距离聚集最近，则将数据分配到聚集的下近似和上近似中。计算过程中使用公式5：

（2）如果在（a）中有还有一些聚集没有被分配到数据对象，即聚集的下近似为空，则返回（a）继续将离每个聚集最近的1个数据分配到其下近似中，否则继续第3）步。

（3）将剩余 N-k个数据对象，利用公式（2）确定离它最近的质心，将分配到聚集的上近似中。（3）确定是否有聚集，它的质心和的距离与和的距离的比在事先规定的阈值范围内，即满足公式（6）。

如不空，则说明除离近，距离中任何对应质心也很近，所以将分到聚集上近似中；否则，属于的下近似。

第4步：检查算法是否收敛，如不收敛，则继续执行第（3）步，否则结束。

3 实验

对本文算法进行测试，与Lingas等人的算法在DBI结果进行比较。实验中选择wl=0.7、wu=0.3。

数据源来源于知识发现数据源网的林业数据，它描述30×30米区域森林覆盖类型。有581012条记录含54个属性，10个数值变量，其余为二进制型，数值中有1个属性描述7种森林植被类型（如云杉、杨木等）。对数据进行预处理，从中随机选择2345个记录及10个数值属性，设置集群数为7，表示森林覆盖类型。数据归一化为[0，1]。设重复因子r=50，imax=500。

聚类结果分析：Lingas等人算法选择=0.0，…，0.0125时，提供了有意义结果，如图1描述。图中显示边界区数据对象对的依赖性。高的重复因子r对于较大值将导致稳定最优值，但算法所需时间显著增加，同时算法收敛性也下降。相比之下，本文聚类算法在整个范围内都能提供有意义的结果，边界区域的对象数从0到2338（见图2）。

一般改进的算法也表示DBI值略有改善，如图3所示。值得注意是，Lingas算法对于边界域中有大量数据对象时，由于大的使算法的收敛性降低。且重复因子r能导致更好DBI，但是以降低效率作为代价的。

4 结语

笔者提出一些方案。通过引入一个改进的粗糙k-means，在森林数据集上成功测试验证了本文算法的有效性。

参考文献

[1]聂舟，程远国.一种基于平均相对偏差的聚类算法[J].兵工自动化，2008，27（8）：32-34.

[2]Pawlak Z.Rough Sets[J].Journal of Information and ComputerSciences，1982，11（5）：145-172.

[3]胡云，苗夺谦，王睿智等.一种基于粗糙k均值的双聚类算法[J].计算机科学，2007，34（11）：174-177.

[4]郑超，苗夺谦，王睿智.基于密度加权的粗糙k均值聚类改进算法[J].计算机科学，2009，36（3）：220-222.endprint

摘要：针对传统通聚类算法大都是研究非重叠、无法解决现实普遍存在的重叠聚类现象的问题，提出一种改进的粗糙k-means聚类算法。并将这Lingas提出的k-means聚类算法与本文算法应用到林业数据集中进行比较。测试结果证明，改进后的方法聚类效果较好，在整个范围内都能提供有意义的结果。

关键词：聚类 粗糙集 重叠

中图分类号：TP313；G642.0 文献标识码：A 文章编号：1007-9416（2014）08-0134-02

聚类分析[1]属非监督性模式识别，是数据挖掘等领域广泛应用算法，如商业、生物等行业。聚类是按某相似性度量法将有相似特征样本归为一类，使类内相似度大，类之间差异大。已有聚类算法大都是研究非重叠问题，但现实中重叠聚类现象很普通，如社会网络中基于个人兴趣、职业等聚集，很多人同属几个聚集；代谢网络中基于功能聚集，有些蛋白质同属几个功能小组等。Steve Gregory提出模糊重叠聚类[6]，但事先需隶属度函数确定每个数据属于各个聚集，建立样本对于类别不确定性的描述。Lingas等人提出了粗糙k-means算法，但边界域中节点受初始设置阈值和重复因子影响较大，基于此，笔者通过改进的粗糙k-means来克服此缺点。

1 粗糙聚类算法

加拿大学者Lingas将RS理论[2]-[4]引入K-均值聚类，提出了RSK-均值算法。引入RS 的3条公理，（1）1个数据对象至多属1个聚类和下近似；（2）属1个聚类下近似成员同时也是这个聚类上近似成员；（3）如1个数据对象不隶属于何1个聚类下近似，则它一定至少是2个聚类上近似成员。笔者采用的变量如下。

粗糙集聚类算法描述如下：

第1步：初始化，设置聚集数K和阈值。随机分配k个数据对象作为聚集下近似对象，由上面公理3得这个对象也属该聚集的上近似。然后将其余N-k个数据分配到1个离其最近的聚类中。

第2步：计算每个聚集新的质心。质心计算（均值函数）为公式（1）。

和是聚集下近似和边界域的权重。

第3步：将数据对象分配到聚集的近似集中。对于Xn确定离它最近的质心，使用公式（2）将数据分配到聚集的上近似中。使用公式（3）确定质心，对于给定阈值，求集合T。

如果不空，则除距离很近外，距离T中任意t对应的也很近，则；否则，。

第4步：检查算法的收敛性，即聚类是否变化。如果没有收敛继续第2步，否则算法结束。

2 改进的粗糙K-means算法

本文在Lingas提出的粗糙k-means算法上做了修改，使用相对阈值代替Lingas的K-means中的绝对阈值。算法步骤如下。

第1步：初始化。随机分配每个数据到1个下近似中，由RS公理2得此数据也属同一聚类上近似。

第2步：使用公式4计算每个聚集的新的均值。

第3步：为使每个聚集下近似至少有1个成员，即有：，由前公理2得，将每个数据对象分配到近似集中，1）最能代表1个集群的数据对象分配到它的上下近似中。

（1）计算所有对象与各个聚集的离，找到数据对象和聚集，使得距离聚集最近，则将数据分配到聚集的下近似和上近似中。计算过程中使用公式5：

（2）如果在（a）中有还有一些聚集没有被分配到数据对象，即聚集的下近似为空，则返回（a）继续将离每个聚集最近的1个数据分配到其下近似中，否则继续第3）步。

（3）将剩余 N-k个数据对象，利用公式（2）确定离它最近的质心，将分配到聚集的上近似中。（3）确定是否有聚集，它的质心和的距离与和的距离的比在事先规定的阈值范围内，即满足公式（6）。

如不空，则说明除离近，距离中任何对应质心也很近，所以将分到聚集上近似中；否则，属于的下近似。

第4步：检查算法是否收敛，如不收敛，则继续执行第（3）步，否则结束。

3 实验

对本文算法进行测试，与Lingas等人的算法在DBI结果进行比较。实验中选择wl=0.7、wu=0.3。

数据源来源于知识发现数据源网的林业数据，它描述30×30米区域森林覆盖类型。有581012条记录含54个属性，10个数值变量，其余为二进制型，数值中有1个属性描述7种森林植被类型（如云杉、杨木等）。对数据进行预处理，从中随机选择2345个记录及10个数值属性，设置集群数为7，表示森林覆盖类型。数据归一化为[0，1]。设重复因子r=50，imax=500。

聚类结果分析：Lingas等人算法选择=0.0，…，0.0125时，提供了有意义结果，如图1描述。图中显示边界区数据对象对的依赖性。高的重复因子r对于较大值将导致稳定最优值，但算法所需时间显著增加，同时算法收敛性也下降。相比之下，本文聚类算法在整个范围内都能提供有意义的结果，边界区域的对象数从0到2338（见图2）。

一般改进的算法也表示DBI值略有改善，如图3所示。值得注意是，Lingas算法对于边界域中有大量数据对象时，由于大的使算法的收敛性降低。且重复因子r能导致更好DBI，但是以降低效率作为代价的。

4 结语

笔者提出一些方案。通过引入一个改进的粗糙k-means，在森林数据集上成功测试验证了本文算法的有效性。

参考文献

[1]聂舟，程远国.一种基于平均相对偏差的聚类算法[J].兵工自动化，2008，27（8）：32-34.

[2]Pawlak Z.Rough Sets[J].Journal of Information and ComputerSciences，1982，11（5）：145-172.

[3]胡云，苗夺谦，王睿智等.一种基于粗糙k均值的双聚类算法[J].计算机科学，2007，34（11）：174-177.

[4]郑超，苗夺谦，王睿智.基于密度加权的粗糙k均值聚类改进算法[J].计算机科学，2009，36（3）：220-222.endprint