李龍龍，何東健，王美麗

(1．陜西工業(yè)職業(yè)技術(shù)學院 信息工程學院,陜西 咸陽 712000；2．西北農(nóng)林科技大學 機械與電子工程學院,陜西 楊凌 712100；3.英國諾丁漢大學 計算機學院,英國 諾丁漢郡 NG81BB；4．西北農(nóng)林科技大學 信息工程學院,陜西 楊凌 712100)

模糊半監(jiān)督加權(quán)聚類算法的有效性評價研究

李龍龍1,2,3，何東健2，王美麗4

(1．陜西工業(yè)職業(yè)技術(shù)學院 信息工程學院,陜西 咸陽 712000；2．西北農(nóng)林科技大學 機械與電子工程學院,陜西 楊凌 712100；3.英國諾丁漢大學 計算機學院,英國 諾丁漢郡 NG81BB；4．西北農(nóng)林科技大學 信息工程學院,陜西 楊凌 712100)

鑒于最佳聚類數(shù)在提高聚類算法性能并擴大其應用領(lǐng)域方面的重要性，為了有效解決聚類算法中最佳聚類數(shù)的確定問題，解決傳統(tǒng)的聚類分析算法常常需要人為預先指定聚類數(shù)的缺點，文中提出一種新型模糊半監(jiān)督加權(quán)聚類算法。首先使用該算法對實測數(shù)據(jù)進行聚類，獲取聚類結(jié)果。隨后采用4種模糊聚類有效性評價算法依次對不同聚類數(shù)下的聚類結(jié)果進行聚類分析，最終通過不同聚類評價結(jié)果的對比分析得到實驗數(shù)據(jù)的最佳聚類數(shù)。自測數(shù)據(jù)集的相關(guān)實驗結(jié)果表明，不同的聚類有效性評價算法具有不同的優(yōu)缺點，選擇合適的聚類評價算法能夠有效地解決最佳聚類數(shù)的確定問題，并能夠有效提高實測數(shù)據(jù)的聚類識別率。

聚類有效性;半監(jiān)督聚類;算法評估;成對約束;最佳聚類數(shù)

0 引 言

作為一種機器學習、數(shù)據(jù)挖掘領(lǐng)域中常見的數(shù)據(jù)分析手段和工具[1]，聚類分析的目標是尋找并發(fā)現(xiàn)隱含在輸入數(shù)據(jù)集中具有相似特征的數(shù)據(jù)集，即稱為簇的元素集合[2]。而聚類問題由于沒有事先定義的分類模型或?qū)嵗齺肀砻鞑煌氐暮畏N聚類結(jié)果是符合預期的，加之分類結(jié)果的不可預知性，使得傳統(tǒng)聚類算法的評價多來自猜測和假設(shè)[3]。如何對一個聚類結(jié)果及其有效性進行較為全面客觀的評判，是一個既復雜又十分困難的技術(shù)難題。

常見的聚類評價算法有內(nèi)部評價法、外部評價法、相對評價法[4-5]及模糊聚類有效性評價法[4-6]等。其中，內(nèi)部和外部評價法都基于計算復雜度較高的統(tǒng)計測試，其有效性指標是用來衡量輸入數(shù)據(jù)集與事先已知結(jié)構(gòu)的匹配程度。相對評價法則旨在探索某一聚類算法在特定的假設(shè)及參數(shù)下能夠獲得的最佳聚類結(jié)果。對于模糊聚類算法而言，模糊聚類有效性評價法則是其最有效的評價算法。而在現(xiàn)有聚類評價算法中，有些聚類有效性評價指數(shù)能夠求出最佳聚類數(shù)[6-9]，從而有效解決聚類預設(shè)參數(shù)中聚類數(shù)的確定問題。

考慮到不同聚類評價算法的適用范圍，文中給出一種特征加權(quán)的模糊半監(jiān)督聚類算法(SFFD)[10]。該算法基于完全自適應距離函數(shù)、特征加權(quán)[11-12]和成對約束構(gòu)建統(tǒng)一目標函數(shù)，用來搜索成對約束下的最優(yōu)原型參數(shù)及最優(yōu)特征權(quán)集。同時，給出四種模糊聚類有效性評價算法，通過不同算法對SFFD算法進行有效性評價，進而得出不同輸入數(shù)據(jù)集的最佳聚類數(shù)，從而確定聚類過程中的聚類數(shù)。

1 特征加權(quán)的模糊半監(jiān)督聚類算法

SFFD算法旨在搜索成對約束下的最優(yōu)模型參數(shù)和最優(yōu)特征權(quán)重集合，其主要算法的公式如下所述。

(1)聚類之間的距離公式：采用內(nèi)積范式Ai來檢測數(shù)據(jù)集中不同聚類的幾何形狀。

(1)

(3)

式中，ci為聚類均值，是實例i對于聚類j的隸屬度。

(2)特征權(quán)值vik可以表示如下：

(3)引入成對約束并采用拉格朗日乘數(shù)法進行推導，可以得到算法的目標函數(shù)：

(8)

(9)

(4)SFFD算法的實例隸屬度值可以表示為：

(10)

(11)

其中：M為must-link約束集；ζ為cannot-link約束集。

2 模糊聚類評價算法

為了更為準確地獲取輸入數(shù)據(jù)集的聚類數(shù)，可以人為設(shè)定不同的聚類數(shù)并采用不同的聚類有效性算法對獲得的模糊分割矩陣的優(yōu)劣進行評估，進而得到最佳聚類數(shù)。由于現(xiàn)有評價算法各自有不同的缺陷，單一的評價算法無法獲得較為可靠的結(jié)果，因此，給出了四種不同的聚類結(jié)果評價算法來進行綜合評價：

(1)分配系數(shù)(PC)：由Bezdek等[13]給出定義，用來測量不同聚類之間的重疊程度：

(12)

式中：N為輸入數(shù)據(jù)集中的實例數(shù)目；c為聚類數(shù)；μij為數(shù)據(jù)點j對于聚類i的隸屬度。

當聚類數(shù)為最佳聚類數(shù)的時候，該系數(shù)為其所有取值的最大值。該系數(shù)的缺陷是其取值會隨著聚類數(shù)c的減少而單調(diào)遞減，并且其與輸入數(shù)據(jù)集結(jié)構(gòu)之間的關(guān)系較為松散。

(2)分類熵(CE)：該系數(shù)與PC類似，其常用來測量聚類分割的模糊性：

(13)

該系數(shù)取值會隨著聚類數(shù)c的增加而單調(diào)遞增，并且其與初始輸入數(shù)據(jù)集的關(guān)系不是很密切。

(3)分割指數(shù)(SC)：是指聚類緊密度之和與其間距的比率。該系數(shù)是一種基于模糊基數(shù)(模糊集的勢)的單簇聚類有效性之和[14]：

(14)

當聚類數(shù)為最佳值時，該系數(shù)取其最小值。

(4)謝和貝尼指數(shù)(XB)：該系數(shù)可表示為聚類內(nèi)全變差與聚類間距的比率[15]，公式如下：

當其取值為最小值時，聚類數(shù)為最佳。

3 實驗結(jié)果

3.1 數(shù)據(jù)介紹

為了分析不同的模糊聚類有效性評價算法在確定輸入數(shù)據(jù)集最佳聚類數(shù)上的優(yōu)缺點，并檢測文中算法在實際應用中的效果，采集了10種樹木在不同時期的160張葉片的照片，每張照片獲取其Margin、Shape、Texture及Combination特征作為不同的輸入數(shù)據(jù)集，這些數(shù)據(jù)集中的數(shù)據(jù)均以數(shù)值形式存在，其結(jié)構(gòu)如表1所示。

表1 文中采用的數(shù)據(jù)集

3.2 最佳聚類數(shù)的確定

通常大多數(shù)聚類算法需要用戶預先輸入希望產(chǎn)生的聚類數(shù)，這就會人為地產(chǎn)生誤差且使得結(jié)果具有一定的主觀性。為了測試確定不同輸入數(shù)據(jù)集的最佳聚類數(shù)，分別使用Margin、Shape、Texture及Combination等測試數(shù)據(jù)作為輸入數(shù)據(jù)集，聚類數(shù)c的預設(shè)范圍為2～20，采用指數(shù)PC、CE、SC和XB對其SFFD聚類結(jié)果進行有效性評價分析，結(jié)果如圖1所示。

圖1為不同特征輸入數(shù)據(jù)集在SFFD聚類算法下4種聚類評價指數(shù)的變化曲線。其中，SFFD算法的標記數(shù)據(jù)為30%。從Margin數(shù)據(jù)集下各指數(shù)的曲線變化趨勢可以看出，PC指數(shù)在c=9時急速下跌，CE指數(shù)在c=8時快速上升，SC指數(shù)在c=11時處于谷底，而此時XB指數(shù)的局部最小值也是11，由于SC指數(shù)的可靠性較高，綜合評估后得出最佳聚類數(shù)為11；同樣的方法進行分析可知，Shape數(shù)據(jù)集下的最優(yōu)聚類數(shù)為c=10，而Texture數(shù)據(jù)集下同樣當c=10時聚類效果最好，Combination數(shù)據(jù)集的評價結(jié)果同樣是c=10。由于不同的特征數(shù)據(jù)集均來自于同一組樹葉照片，因此，通過對4種輸入數(shù)據(jù)集下的聚類結(jié)果進行模糊聚類有效性評價分析可知，該組照片的最佳聚類數(shù)為10，由于實驗照片來自于10種不同的葉片圖像，故該聚類評價分析結(jié)果符合研究實際。

圖1 不同指數(shù)下的最佳聚類數(shù)

不同特征數(shù)據(jù)集的實驗結(jié)果表明：文中聚類有效性評價算法是一種行之有效的確定聚類數(shù)的途徑。

4 結(jié)束語

文中提出一種特征加權(quán)的半監(jiān)督聚類算法,并對該算法在不同模糊聚類有效性評價算法下的聚類結(jié)果進行分析。實驗結(jié)果表明，綜合不同的聚類有效性評價結(jié)果，能夠有效得出輸入數(shù)據(jù)集的最佳聚類數(shù)，從而解決大部分聚類算法中聚類數(shù)的確定問題，具有良好的應用前景。

[1] 許海洋,汪國安,王萬森.模糊聚類分析在數(shù)據(jù)挖掘中的應用研究[J].計算機工程與應用,2005,41(17):177-179.

[2] 高新波,謝維信.模糊聚類理論發(fā)展及應用的研究進展[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] 張惟皎,劉春煌,李芳玉.聚類質(zhì)量的評價方法[J].計算機工程,2005,31(20):10-12.

[6] 李 潔,高新波,焦李成.一種基于修正劃分模糊度的聚類有效性函數(shù)[J].系統(tǒng)工程與電子技術(shù),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] 李龍龍,王美麗.基于加權(quán)二叉樹的自適應遺傳算法研究[J].計算機技術(shù)與發(fā)展,2010,20(11):95-99.

[12] 李 潔,高新波,焦李成.基于特征加權(quán)的模糊聚類新算法[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”高技術(shù)發(fā)展計劃項目(2013AA10230402)；國家自然科學基金資助項目(61402374)；陜西工院科研項目(ZK11-34)

李龍龍(1983-)，男，講師，博士，英國訪問學者，研究方向為智能化檢測與技術(shù)、智能信息系統(tǒng)；何東健，教授，博士生導師，研究方向為智能化檢測與控制、農(nóng)業(yè)信息技術(shù)等。

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