模糊半监督加权聚类算法的有效性评价研究

李龙龙，何东健，王美丽

(1．陕西工业职业技术学院 信息工程学院,陕西 咸阳 712000；2．西北农林科技大学 机械与电子工程学院,陕西 杨凌 712100；3.英国诺丁汉大学 计算机学院,英国 诺丁汉郡 NG81BB；4．西北农林科技大学 信息工程学院,陕西 杨凌 712100)

模糊半监督加权聚类算法的有效性评价研究

李龙龙1,2,3，何东健2，王美丽4

(1．陕西工业职业技术学院 信息工程学院,陕西 咸阳 712000；2．西北农林科技大学 机械与电子工程学院,陕西 杨凌 712100；3.英国诺丁汉大学 计算机学院,英国 诺丁汉郡 NG81BB；4．西北农林科技大学 信息工程学院,陕西 杨凌 712100)

鉴于最佳聚类数在提高聚类算法性能并扩大其应用领域方面的重要性，为了有效解决聚类算法中最佳聚类数的确定问题，解决传统的聚类分析算法常常需要人为预先指定聚类数的缺点，文中提出一种新型模糊半监督加权聚类算法。首先使用该算法对实测数据进行聚类，获取聚类结果。随后采用4种模糊聚类有效性评价算法依次对不同聚类数下的聚类结果进行聚类分析，最终通过不同聚类评价结果的对比分析得到实验数据的最佳聚类数。自测数据集的相关实验结果表明，不同的聚类有效性评价算法具有不同的优缺点，选择合适的聚类评价算法能够有效地解决最佳聚类数的确定问题，并能够有效提高实测数据的聚类识别率。

聚类有效性;半监督聚类;算法评估;成对约束;最佳聚类数

0 引 言

作为一种机器学习、数据挖掘领域中常见的数据分析手段和工具[1]，聚类分析的目标是寻找并发现隐含在输入数据集中具有相似特征的数据集，即称为簇的元素集合[2]。而聚类问题由于没有事先定义的分类模型或实例来表明不同元素的何种聚类结果是符合预期的，加之分类结果的不可预知性，使得传统聚类算法的评价多来自猜测和假设[3]。如何对一个聚类结果及其有效性进行较为全面客观的评判，是一个既复杂又十分困难的技术难题。

常见的聚类评价算法有内部评价法、外部评价法、相对评价法[4-5]及模糊聚类有效性评价法[4-6]等。其中，内部和外部评价法都基于计算复杂度较高的统计测试，其有效性指标是用来衡量输入数据集与事先已知结构的匹配程度。相对评价法则旨在探索某一聚类算法在特定的假设及参数下能够获得的最佳聚类结果。对于模糊聚类算法而言，模糊聚类有效性评价法则是其最有效的评价算法。而在现有聚类评价算法中，有些聚类有效性评价指数能够求出最佳聚类数[6-9]，从而有效解决聚类预设参数中聚类数的确定问题。

考虑到不同聚类评价算法的适用范围，文中给出一种特征加权的模糊半监督聚类算法(SFFD)[10]。该算法基于完全自适应距离函数、特征加权[11-12]和成对约束构建统一目标函数，用来搜索成对约束下的最优原型参数及最优特征权集。同时，给出四种模糊聚类有效性评价算法，通过不同算法对SFFD算法进行有效性评价，进而得出不同输入数据集的最佳聚类数，从而确定聚类过程中的聚类数。

1 特征加权的模糊半监督聚类算法

SFFD算法旨在搜索成对约束下的最优模型参数和最优特征权重集合，其主要算法的公式如下所述。

(1)聚类之间的距离公式：采用内积范式Ai来检测数据集中不同聚类的几何形状。

(1)

(3)

式中，ci为聚类均值，是实例i对于聚类j的隶属度。

(2)特征权值vik可以表示如下：

(3)引入成对约束并采用拉格朗日乘数法进行推导，可以得到算法的目标函数：

(8)

(9)

(4)SFFD算法的实例隶属度值可以表示为：

(10)

(11)

其中：M为must-link约束集；ζ为cannot-link约束集。

2 模糊聚类评价算法

为了更为准确地获取输入数据集的聚类数，可以人为设定不同的聚类数并采用不同的聚类有效性算法对获得的模糊分割矩阵的优劣进行评估，进而得到最佳聚类数。由于现有评价算法各自有不同的缺陷，单一的评价算法无法获得较为可靠的结果，因此，给出了四种不同的聚类结果评价算法来进行综合评价：

(1)分配系数(PC)：由Bezdek等[13]给出定义，用来测量不同聚类之间的重叠程度：

(12)

式中：N为输入数据集中的实例数目；c为聚类数；μij为数据点j对于聚类i的隶属度。

当聚类数为最佳聚类数的时候，该系数为其所有取值的最大值。该系数的缺陷是其取值会随着聚类数c的减少而单调递减，并且其与输入数据集结构之间的关系较为松散。

(2)分类熵(CE)：该系数与PC类似，其常用来测量聚类分割的模糊性：

(13)

该系数取值会随着聚类数c的增加而单调递增，并且其与初始输入数据集的关系不是很密切。

(3)分割指数(SC)：是指聚类紧密度之和与其间距的比率。该系数是一种基于模糊基数(模糊集的势)的单簇聚类有效性之和[14]：

(14)

当聚类数为最佳值时，该系数取其最小值。

(4)谢和贝尼指数(XB)：该系数可表示为聚类内全变差与聚类间距的比率[15]，公式如下：

当其取值为最小值时，聚类数为最佳。

3 实验结果

3.1 数据介绍

为了分析不同的模糊聚类有效性评价算法在确定输入数据集最佳聚类数上的优缺点，并检测文中算法在实际应用中的效果，采集了10种树木在不同时期的160张叶片的照片，每张照片获取其Margin、Shape、Texture及Combination特征作为不同的输入数据集，这些数据集中的数据均以数值形式存在，其结构如表1所示。

表1 文中采用的数据集

3.2 最佳聚类数的确定

通常大多数聚类算法需要用户预先输入希望产生的聚类数，这就会人为地产生误差且使得结果具有一定的主观性。为了测试确定不同输入数据集的最佳聚类数，分别使用Margin、Shape、Texture及Combination等测试数据作为输入数据集，聚类数c的预设范围为2～20，采用指数PC、CE、SC和XB对其SFFD聚类结果进行有效性评价分析，结果如图1所示。

图1为不同特征输入数据集在SFFD聚类算法下4种聚类评价指数的变化曲线。其中，SFFD算法的标记数据为30%。从Margin数据集下各指数的曲线变化趋势可以看出，PC指数在c=9时急速下跌，CE指数在c=8时快速上升，SC指数在c=11时处于谷底，而此时XB指数的局部最小值也是11，由于SC指数的可靠性较高，综合评估后得出最佳聚类数为11；同样的方法进行分析可知，Shape数据集下的最优聚类数为c=10，而Texture数据集下同样当c=10时聚类效果最好，Combination数据集的评价结果同样是c=10。由于不同的特征数据集均来自于同一组树叶照片，因此，通过对4种输入数据集下的聚类结果进行模糊聚类有效性评价分析可知，该组照片的最佳聚类数为10，由于实验照片来自于10种不同的叶片图像，故该聚类评价分析结果符合研究实际。

图1 不同指数下的最佳聚类数

不同特征数据集的实验结果表明：文中聚类有效性评价算法是一种行之有效的确定聚类数的途径。

4 结束语

文中提出一种特征加权的半监督聚类算法,并对该算法在不同模糊聚类有效性评价算法下的聚类结果进行分析。实验结果表明，综合不同的聚类有效性评价结果，能够有效得出输入数据集的最佳聚类数，从而解决大部分聚类算法中聚类数的确定问题，具有良好的应用前景。

[1] 许海洋,汪国安,王万森.模糊聚类分析在数据挖掘中的应用研究[J].计算机工程与应用,2005,41(17):177-179.

[2] 高新波,谢维信.模糊聚类理论发展及应用的研究进展[J].科学通报,1999,44(21):2241-2251.

[3] 高新波.模糊聚类分析及其应用[M].西安:西安电子科技大学出版社,2004:113-119.

[4]HalkidiM,BatistakisY,VazirgiannisM.Onclusteringvalidationtechniques[J].IntelligentInformationSystems,2001,17(2-3):107-145.

[5] 张惟皎,刘春煌,李芳玉.聚类质量的评价方法[J].计算机工程,2005,31(20):10-12.

[6] 李 洁,高新波,焦李成.一种基于修正划分模糊度的聚类有效性函数[J].系统工程与电子技术,2005,27(4):723-726.

[7]RessomH,WangD,NatarajanP.Adaptivedoubleself-organizingmapsforclusteringgeneexpressionprofiles[J].NeuralNetworks,2003,16(5-6):633-640.

[8]WuSitao,ChowTWS.Self-organizing-mapbasedclusteringusingalocalclusteringvalidityindex[J].NeuralProcessingLetters,2003,17(3):253-271.

[9]WuSitao,ChowTWS.Clusteringoftheself-organizingmapusingaclusteringvalidityindexbasedoninter-clusterandintra-clusterdensity[J].PatternRecognition,2004,37(2):175-188.

[10]LiLonglong,JonathanG,HeDongjian,etal.Semi-supervisedfuzzyclusteringwithfeaturediscrimination[J].PlosOne,2015,10(9):e0131160.

[11] 李龙龙,王美丽.基于加权二叉树的自适应遗传算法研究[J].计算机技术与发展,2010,20(11):95-99.

[12] 李 洁,高新波,焦李成.基于特征加权的模糊聚类新算法[J].电子学报,2006,34(1):89-92.

[13]BezdekJC.Patternrecognitionwithfuzzyobjectivefunctionalgorithms[M].[s.l.]:Springer,1983.

[14]BensaidAM,HallLO,BezdekJC,etal.Validity-guided(re)clusteringwithapplicationstoimagesegmentation[J].IEEETransactionsonFuzzySystems,1996,4(2):112-123.

[15]XieXLL,BeniG.Avaliditymeasureforfuzzyclustering[J].IEEETransactionsonPatternAnalysisandMachineIntelligence,1991,13(8):841-847.

Study of Clustering Validity Evaluation on Semi-supervised Clustering Algorithm with Feature Discrimination

LI Long-long1,2,3,HE Dong-jian2,WANG Mei-li4

(1．College of Information Engineering,Shaanxi Polytechnic Institute,Xianyan 712000,China；2．College of Mechanical & Electronic Engineering,Northwest A & F University,Yangling 712100,China；3.School of Computer Science,University of Nottingham,Nottingham NG81BB,UK；4．College of Information Engineering,Northwest A & F University,Yangling 712100,China)

As the optimal clustering number has great importance in improving the performance of clustering algorithm and expanding the algorithm’s application area,in order to solve the problem of the determination of the optimal clustering number for clustering algorithms effectively and settle the problem that the traditional clustering algorithm often requires prespecified number of clustering,a novel semi-supervised fuzzy clustering algorithm with feature discrimination (SFFD) is proposed.Firstly,it is used to obtain the clustering result of the measured data,and then four kinds of fuzzy clustering validity evaluation algorithm are adopted for clustering analysis under different clustering number.Finally,by the comparative analysis of various validity evaluation algorithm with experimental data the optimal clustering number was obtained.The experiment based on self-test datasets shows that various clustering validity evaluation algorithm has both the advantages and disadvantages,making a good choice for the clustering validity evaluation algorithm can effectively handle the problem of the determination of the optimal clustering number and enhance the recognition rate effectively for the measured data.

clustering validity;semi-supervised clustering;algorithm evaluation;pairwise constraints;optimal clustering number

2015-08-07

2015-11-11

时间：2016-05-05

国家“863”高技术发展计划项目(2013AA10230402)；国家自然科学基金资助项目(61402374)；陕西工院科研项目(ZK11-34)

李龙龙(1983-)，男，讲师，博士，英国访问学者，研究方向为智能化检测与技术、智能信息系统；何东健，教授，博士生导师，研究方向为智能化检测与控制、农业信息技术等。

http://www.cnki.net/kcms/detail/61.1450.TP.20160505.0828.066.html

TP182

A

1673-629X(2016)06-0065-04

10.3969/j.issn.1673-629X.2016.06.014