程鈴鈁 陳黎飛 賴曉燕

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

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

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

1? 國內(nèi)外研究動態(tài)

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

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

2? 相關(guān)工作

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

2.1? 屬性平衡的距離度量

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

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

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

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

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

3.1? 聚類結(jié)果

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

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

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

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

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

4? 結(jié)論

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

參考文獻(xiàn)

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

[2]陳黎飛， 郭躬德， 姜青山， 自適應(yīng)的軟子空間聚類算法， 軟件學(xué)報， 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ī)應(yīng)用， 31（1）： 97-100， 2011.

[9]梁吉業(yè)， 白亮， 曹付元. 基于新的距離度量的K-Modes 聚類算法[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.