程鈴鈁 陳黎飛 賴曉燕

摘? 要： 聚類分析是數(shù)據(jù)挖掘中重要的研究課題，在信息過(guò)濾、生物信息學(xué)，醫(yī)學(xué)等領(lǐng)域得到廣泛應(yīng)用。本課題著重于自上而下的子空間聚類方法，主要原因是當(dāng)前主要的此型算法都是以K-means或K-modes為基礎(chǔ)的，在均勻效應(yīng)的影響下，不平衡數(shù)據(jù)的問(wèn)題是現(xiàn)有的軟子空間算法不能有效聚類的，所以提出了一種基于劃分的不平衡數(shù)據(jù)軟子空間聚類新算法。所提算法提高了不平衡數(shù)據(jù)的聚類精度，在生物信息學(xué)和臨床醫(yī)學(xué)等領(lǐng)域具有一定的理論意義和實(shí)際應(yīng)用價(jià)值。

關(guān)鍵詞： 聚類分析;子空間聚類;不平衡數(shù)據(jù);聚類精度

【Abstract】： Cluster analysis is an important research topic in data mining. It is widely used in information filtering， bioinformatics， medicine and other fields. This topic focuses on the top-down subspace clustering method. The main reason is that the current major algorithms are based on K-means or K-modes. Under the influence of uniform effects， the problem of unbalanced data The existing soft subspace algorithm cannot be effectively clustered， so a new algorithm based on partitioning unbalanced data soft subspace clustering is proposed. The proposed algorithm improves the clustering accuracy of unbalanced data， and has certain theoretical significance and practical application value in the fields of bioinformatics and clinical medicine.

【Key words】： Cluster analysis; Subspace clustering; Unbalanced data; Clustering accuracy

0? 引言

數(shù)據(jù)挖掘領(lǐng)域的重要研究方法之一是聚類，由于聚類分析具有無(wú)監(jiān)督學(xué)習(xí)性，所以在眾多領(lǐng)域的得到應(yīng)用，包括醫(yī)學(xué)、生物信息、Web日志分析以及金融交易等等。本文是針對(duì)在臨床上的應(yīng)用，我們通常要在手術(shù)后最快的預(yù)測(cè)該病人是否可以正常愈合以便為后續(xù)的護(hù)理工作提供更好的決策支持。然而，許多臨床藥物產(chǎn)生的數(shù)據(jù)通常是不平衡的。顯然這些數(shù)據(jù)是混合數(shù)據(jù)，這是我們面臨的第一個(gè)問(wèn)題。同時(shí)我們還發(fā)現(xiàn)在采集的這些混合數(shù)據(jù)中，不是每個(gè)特征對(duì)我們最后進(jìn)行區(qū)分病人是否能夠正常愈合都是重要的，其中有的特征是不重要的，這樣一來(lái)，我們面對(duì)的第二個(gè)問(wèn)題就是特征如何選擇的問(wèn)題。最后，在實(shí)際的臨床應(yīng)用中，大多數(shù)病人都是可以正常愈合的，只有少數(shù)的病人不能夠正常愈合，在數(shù)據(jù)挖掘中，我們將大部分可以正常愈合的人群看做一個(gè)類，不能正常愈合的看做另外一個(gè)類，很明顯兩大類的數(shù)量上具有較大差異，所以我們面對(duì)的第三個(gè)問(wèn)題就是類不平衡的問(wèn)題。 我們將以上3個(gè)問(wèn)題歸納起來(lái)稱其為不平衡子空間的聚類的問(wèn)題。這在臨床醫(yī)學(xué)應(yīng)用中是非常有意義的。

子空間聚類是可以識(shí)別和生成與每個(gè)集群類相關(guān)聯(lián)的一組特征（或?qū)傩裕┮孕纬梢蕾囉诩旱淖涌臻g。目前的子空間算法有兩種：自下而上的和自上而下的方法。自上而下方法是在整個(gè)空間范圍為每個(gè)候選聚類計(jì)算最佳子空間。實(shí)際上，這種類型的當(dāng)前主要算法基于K均值或K-模式。其研究思想是在原本的算法中增加為每個(gè)屬性的增加一個(gè)特征權(quán)重。這構(gòu)造了目標(biāo)集群類的軟子空間。 許多實(shí)際應(yīng)用產(chǎn)生的數(shù)據(jù)通常是不平衡的[2]。 反例對(duì)應(yīng)于那些沒(méi)有患病的人，樣本量相對(duì)較大; 基于以上內(nèi)容本文提出了一種“雙加權(quán)”方法，稱為 BWIC（ Bi- Weighting for Imbalanced data Clustering）不平衡數(shù)據(jù)軟聚類算法。

1? 國(guó)內(nèi)外研究動(dòng)態(tài)

20世紀(jì)30年代，Driver 和 Kroeber 第一次提出聚類分析的思想，并將其運(yùn)用到人類學(xué)的研究領(lǐng)域。在之后的幾年，Robert Tryon在心理學(xué)領(lǐng)域繼續(xù)使用了聚類分析。在接下來(lái)的70年中，聚類分析方法已被廣泛開發(fā)并應(yīng)用于許多領(lǐng)域。新提出的算法對(duì)低維空間數(shù)據(jù)集的聚類具有良好的效果。隨著信息時(shí)代快節(jié)奏的發(fā)展，人們更多的開始研究互聯(lián)網(wǎng)、人臉文檔等高維數(shù)據(jù)，這個(gè)時(shí)候大家發(fā)現(xiàn)傳統(tǒng)的聚類算法已經(jīng)沒(méi)有辦法較好的處理這些數(shù)據(jù)了。Aggarwal在1998年第一次提出子空間聚類之后，闡述了高維數(shù)據(jù)的尺寸冗余，局部相關(guān)性和稀疏性[1]。

在視頻處理、圖形分割等超高維數(shù)據(jù)問(wèn)題方面，可惜的是子空間聚類不能給我們較好的結(jié)果。但是，對(duì)于處理高維數(shù)據(jù)有較好的效果主要是由于其算法的目標(biāo)函數(shù)都是在歐氏距離度量的基礎(chǔ)上展開研究的。2009年，一種基于自表示模型的稀疏子空間聚類子空間聚類算法誕生了，在之后自適應(yīng)的k-means 型軟子空間聚類算法出現(xiàn)了，它是由陳黎飛等提出的。次算法需要首先設(shè)置一些全局的關(guān)鍵參數(shù)，在沒(méi)有考慮子空間優(yōu)化問(wèn)題前提下，通過(guò)新的軟子空間聚類優(yōu)化目標(biāo)函數(shù)最小化了子空間的簇內(nèi)緊湊度，同時(shí)最大化了每個(gè)簇類所在的投影子空間[3]。

2? 相關(guān)工作

雙加權(quán)方法可以為每個(gè)群集提供反映其重要性的權(quán)重，賦予各個(gè)屬性一個(gè)特征權(quán)重，用來(lái)衡量聚類和測(cè)量屬性之間的相關(guān)性。另一方面，實(shí)際數(shù)據(jù)通常與不同類型的屬性混合，例如數(shù)字和分類。導(dǎo)致他們對(duì)這兩個(gè)重量的“不平衡”貢獻(xiàn)。與K-Means軟子空間算法相比較，該算法提高了不平衡數(shù)據(jù)的聚類精度。我們可以在手術(shù)后最快的預(yù)測(cè)該病人是否可以正常愈合以便為后續(xù)的護(hù)理工作提供更好的決策支持。

2.1? 屬性平衡的距離度量

3? 數(shù)據(jù)集和實(shí)驗(yàn)設(shè)置

該實(shí)驗(yàn)使用了五個(gè)常用的UCI數(shù)據(jù)集，表1中的Hypothyroid（甲狀腺功能低下者）、Heart（心臟疾病數(shù)據(jù)）是由數(shù)值型數(shù)據(jù)和類屬型數(shù)據(jù)混合組成的，而其他的三個(gè)數(shù)據(jù)集單純只含有類屬型屬性，首先前提對(duì)所有數(shù)據(jù)中的所有數(shù)值型屬性都預(yù)先做了[0，1]規(guī)范化處理。此次實(shí)驗(yàn)是對(duì)各種算法聚類復(fù)雜類型數(shù)據(jù)的性能的驗(yàn)證。

所有樣本數(shù)據(jù)都含“不平衡”的性質(zhì)，由表1看到，甲狀腺功能低下者Hypothyroid的數(shù)據(jù)可以分為三組，分別是Hyperfunction超功能、Normal正常和Subnormal次正常表示），最多數(shù)據(jù)的一組有3489個(gè)樣本，而最小的只有94個(gè)對(duì)象。再有Soybean數(shù)據(jù)中包含10個(gè)樣本數(shù)據(jù)的有3組，然而第4各組卻有18個(gè)樣本，分別用D1～D4表示。還有數(shù)據(jù)集Splice里的每個(gè)對(duì)象，都是61個(gè)核苷酸序列（位點(diǎn)編號(hào)從-30到+ 30），將其分為三組：EI、IE和Neither，對(duì)象數(shù)分別為768、768和1656;

另外兩組數(shù)據(jù)集Mushroom、Heart中，盡管各組樣本個(gè)數(shù)較接近，但卻有明顯的正負(fù)例子的區(qū)別，Heart數(shù)據(jù)集可分為“Presence（有心臟疾?。焙虯bsence（無(wú)心臟疾?。眱煞N，Mushroom分為“Edible（可食用蘑菇）”和“Poisonous（有毒蘑菇）”兩種。使用這些數(shù)據(jù)集的原因就是，在實(shí)際的臨床應(yīng)用中，許多臨床藥物產(chǎn)生的數(shù)據(jù)通常是不平衡的。由于這些數(shù)據(jù)是混合數(shù)據(jù)所以實(shí)驗(yàn)數(shù)據(jù)集這樣安排就是為了解決面臨的第一個(gè)問(wèn)題。同時(shí)還解決了前文中提出的第三個(gè)問(wèn)題，實(shí)際臨床實(shí)驗(yàn)中，大多數(shù)病人都是可以正常愈合的，只有少數(shù)的病人不能夠正常愈合，在數(shù)據(jù)挖掘中，我們將大部分可以正常愈合的人群看做一個(gè)類，不能正常愈合的看做另外一個(gè)類，很明顯兩大類的數(shù)量上具有較大差異。

該實(shí)驗(yàn)過(guò)程中使用聚類類屬型數(shù)據(jù)的K-Modes算法[8-9]（以下簡(jiǎn)稱為KM）為基準(zhǔn)算法。為了增加對(duì)比性，另外選用一種較新的KM改進(jìn)型算法：基于互補(bǔ)熵的特征加權(quán)重KM算法（以下簡(jiǎn)稱為WKM），作為對(duì)比算法。

3.1? 聚類結(jié)果

通過(guò)調(diào)用BWIC算法聚類每個(gè)數(shù)據(jù)集各20次，分別根據(jù)式（9）計(jì)算反映結(jié)果質(zhì)量的Silhouette值，再計(jì)算平均的Silhouette值。實(shí)驗(yàn)結(jié)果表明（見(jiàn)表2）BWIC算法在五個(gè)數(shù)據(jù)集中都取得了較好的聚類結(jié)果。由于使用了局部特征加權(quán)技術(shù)，WKM算法表現(xiàn)出比傳統(tǒng)的KM算法更高的性能。表2也顯示，WKP算法的性能多數(shù)情況勝過(guò)MKP，其部分原因在于WKP使用了（全局）特征加權(quán)技術(shù)[7]，可以在聚類過(guò)程中識(shí)別各屬性對(duì)簇類的重要性，進(jìn)行子空間聚類。相較而言，由于在特征加權(quán)基礎(chǔ)上增加了簇類權(quán)重的識(shí)別功能，BWIC算法的聚類結(jié)果顯得更為準(zhǔn)確，尤其在樣本分布顯著不平衡的Splice和Hypothyroid數(shù)據(jù)集上，例如，在Splice數(shù)據(jù)集上，BWIC算法的平均MacroF1指標(biāo)和MicroF1指標(biāo)都超出對(duì)比算法近50%。

3.2? 權(quán)重計(jì)算結(jié)果

為檢驗(yàn)BWIC算法“雙加權(quán)”方法的性能，從表3可以得出BWIC算法在每個(gè)數(shù)據(jù)集學(xué)習(xí)得到的簇類權(quán)重。從表中不難發(fā)現(xiàn)，輸出的權(quán)重值與簇的重要性相關(guān)，這樣一來(lái)就解決了我們?cè)谖闹星懊嫣岬降牡诙€(gè)特征如何選擇的問(wèn)題，因?yàn)樵趯?shí)際的臨床實(shí)驗(yàn)中，采集的這些混合數(shù)據(jù)中，不是每個(gè)特征對(duì)我們最后進(jìn)行區(qū)分病人是否能夠正常愈合都是重要的，其中有的特征是不重要的，有的特征是重要的。

通過(guò)3種混合型數(shù)據(jù)聚類算法BWIC、WKP和MKP在兩個(gè)約簡(jiǎn)數(shù)據(jù)集上的聚類性能指標(biāo)值來(lái)看，表中的符號(hào)↓表示指標(biāo)值下降的情況。如表所示， MacroF1和MicroF1兩個(gè)指標(biāo)值都出現(xiàn)了不同程度的下降。

以上結(jié)果表明，BWIC算法的“雙加權(quán)”可以得到較為準(zhǔn)確的結(jié)果，尤其是在不平衡數(shù)據(jù)子空間聚類時(shí)[11]。

4? 結(jié)論

本文通過(guò)提出的新的算法-雙加權(quán)方法，即給予每個(gè)簇一個(gè)反映其重要性的權(quán)重（簇權(quán)重（cluster- weight）），為衡量屬性與簇類之間的相關(guān)性，給予我們每個(gè)屬性一個(gè)特征權(quán)重（feature-weight）。另一方面，現(xiàn)實(shí)生活中的數(shù)據(jù)不可能是單一類型的，而是由數(shù)值型和類屬型不同類型的屬性混合組成的，導(dǎo)致它們對(duì)兩種權(quán)重產(chǎn)生“不平衡”的貢獻(xiàn)。依據(jù)在實(shí)際應(yīng)用數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)，結(jié)果表明提出的新算法能夠?yàn)椴黄胶鈹?shù)據(jù)中的簇類學(xué)習(xí)提供更準(zhǔn)確的軟子空間;與現(xiàn)有的軟子空間算法相比，新提出的BWIC算法提高了不平衡數(shù)據(jù)的聚類精度，我們可以在手術(shù)后最快的預(yù)測(cè)該病人是否可以正常愈合以便為后續(xù)的護(hù)理工作提供更好的決策支持，未來(lái)不僅可以在臨床上得到廣泛的應(yīng)用，在其他的病種分析中也可以得到應(yīng)用，這將是非常有意義的。

參考文獻(xiàn)

[1]AGGRAWAL C C， Data mining： The textbook， Springer， 2015.

[2]陳黎飛， 郭躬德， 姜青山， 自適應(yīng)的軟子空間聚類算法， 軟件學(xué)報(bào)， 21（10）： 2513-2523， 2010.

[3]HUANG J Z， NG M K， RONG H， LI Z， Automated variable weighting in k-means type clustering [J]. IEEE Transactions

on Pattern Analysis and Machine Intelligence， 27（5）： 657- 668， 2005.

[4]CHEN L， WANG S， WANG K， ZHU J， Soft subspace clustering of categorical data with probabilistic distance[J]. Pattern Recognition， 51： 322-332， 2016.

[5]CAO F， JIANG J， LI D， ZHAO X. A weighting k-modes algorithm for subspace clustering of categorical data [J]. Neurocomputing， 108： 23-30， 2013.

[6]MACQUEEN J. Some methods for classification and analysis of multivariate observation[C]//Proceedings of the 5th Berkley Symposium on Mathematical Statistics and Probability， Berkeley： University of California Press， 1967： 281-297.

[7]HUANG Z， NG M. A note on k-modes clustering[J]. Journal of Classification， 20（2）： 257-261， 2003.

[8]李仁侃， 葉東毅. 粗糙K-Modes聚類算法[J]. 計(jì)算機(jī)應(yīng)用， 31（1）： 97-100， 2011.

[9]梁吉業(yè)， 白亮， 曹付元. 基于新的距離度量的K-Modes 聚類算法[J]. 計(jì)算機(jī)研究與發(fā)展， 47（10）： 1749-1755， 2010.

[10]ZHOU K， YANG S. Exploring the uniform effect of FCM clustering： A data distribution perspective [J]. Knowledge- Based Systems， 96： 76-83， 2016.

[11]HE H， GARCIA E A. Learning from Imbalanced Data[J]. IEEE Transactions on Knowledge and Data Engineering， 21（9）： 1263-1284， 2009.