模糊半監督加權聚類算法的有效性評價研究

李龍龍，何東健，王美麗

(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