一種基于屬性加權的快速聚類算法?

趙國偉 蔡江輝 楊海峰 荀亞玲

（太原科技大學計算機科學與技術學院 太原 030024）

1 引言

聚類分析［1～3］是數據挖掘中重要的無監(jiān)督學習技術之一，與監(jiān)督學習不同的是待處理的樣本數據集中沒有包含樣本分類相關信息。聚類是把數據集中的對象劃分成多個簇的過程，被廣泛應用于市場研究、圖像分割、網絡安全及模式分類等眾多新興領域中。

K-means是一種經典的基于劃分的聚類方法，由于其具有簡單性和高效性被廣泛運用于解決各種現實問題，例如文本分析、圖像聚類、社區(qū)發(fā)現等［4］。此外，K-means采用距離作為相似性的評價指標，所以在處理數值型數據時能夠更好地體現聚類在幾何和統(tǒng)計上的意義。但是，常用的距離度量方法并沒有對樣本數據集各屬性的內部結構以及其影響聚類劃分的情況進行詳細分析，即在對樣本數據集進行劃分時將數據所有屬性的重要程度視為相同或者根據經驗知識對屬性的重要程度進行加權后再計算樣本間的相似性。這樣計算的距離并沒有準確地反映數據間的相似性或因為經驗知識不全面而產生誤差，從而影響聚類的劃分結果。針對傳統(tǒng)K-means沒有考慮屬性重要程度的問題，本文提出了一種改進K-means算法，即FAWK。該算法定義了一個可以在領域知識未知的情況下區(qū)分數據屬性重要程度的離散度函數，基于離散度函數提出了一種屬性特征加權的距離度量方法，即AW（Attribute Weighting Distance）。在AW的基礎上結合K-means算法思想提出了FAWK。

2 相關研究

經典K-means是一種簡單有效的數據挖掘技術，其主要通過兩個迭代步驟進行聚類：其一，根據目前數據劃分情況來確定聚類中心；其二，根據劃分標準對數據對象進行重新劃分。

經典K-means常采用歐式距離作為數據劃分的標準，然而歐式距離并沒有考慮數據屬性對聚類劃分的影響程度，因此科學研究者們對屬性的重要程度進行分析并提出了不同形式的相似度度量方法來衡量數據對象的相似性。文獻［4］通過最大化子空間內各簇中心與其他簇的數據對象的加權距離提出了一種集成簇內和簇間距離的加權K-means（KICIC）。文 獻［5］提 出 了 一 種 新 的L2-Norm正則化加權的K-means（l2WK）。該算法首先提出了一個子空間K-means聚類框架，然后對數據屬性特征進行L2-Norm調整來排除部分噪音屬性的影響，最后通過優(yōu)化加權K-means的目標函數來判斷算法是否收斂。文獻［6］從數據對象的屬性出發(fā)，通過屬性偏離概率估量函數來確定數據屬性的權重值并結合歐式距離提出了一種改進的加權歐式距離聚類算法（WEDK）。

以上算法在聚類過程中都側重于數據屬性的分析，卻忽略了歐式距離本身的缺陷。因此，文獻［7］針對函數型數據提出了一種新的基于導數信息距離的函數K-means（DIFK），實驗結果證明了該算法的實用性和有效性。文獻［8］提出了一種新的點對點距離度量的改進K-means（SK）。該方法定義了一個基于S散度的S距離（SD）來替換傳統(tǒng)的歐式距離。實驗結果顯示該算法不僅適用于群集分布不規(guī)則數據還加快了聚類收斂速度。

選擇合適的相似性度量對于揭示給定數據集中的自然分組是非常重要的，但是在對于K-means而言，初始中心的隨機選擇也將直接影響聚類結果的好壞。針對這一問題，文獻［9］提出了一種空間密度相似性度量的K-means（SSMK）。該算法將可伸縮空間密度的相似性作為聚類劃分標準，并結合密度和距離來選擇初始聚類中心。此外該算法還構造了一種基于空間密度相似性的簇中心迭代模型來克服均值簇中心的缺陷。文獻［10］根據簇類中心密度較高且方差較小的特點來干預初始聚類中心的選擇，提出了一種最小方差優(yōu)化初始聚類中心的K-means（MDK）。文獻［11］提出了一種基于加權局部方差的密度計算方法，并利用改進的最大最小法啟發(fā)式地選擇初始中心點（WLVK）。實驗結果證明該算法提高了聚類的效果，但是該算法具有較高的時間和空間復雜度。

此外，針對K-means根據經驗值設置K的問題，文獻［12］結合聚合距離參數和戴維森堡丁指數（DBI）提出了基于聚合距離參數的改進K-means（IADCK）；文獻［13］提出了一種基于加權密度的最大最小距離的改進K-means（KWDM），該算法定義了準則函數來確定聚類的最優(yōu)簇數K。雖然實驗結果證明了IADCK和KWDM算法的有效性，但在初始聚類中心的選擇和K值的確定過程帶來了大量的時間開銷。

3 算法思想

3.1 AW（Attribute Weighting Distance）

數據對象的信息主要存儲在其屬性上，因此數據的屬性在數據挖掘中對數據的知識發(fā)現有不可替代的作用。然而不同的屬性對知識的發(fā)現影響程度不同，尤其在K-means中，數據屬性對聚類劃分過程的影響更為明顯。本文提出的AW是一種根據數據屬性對聚類劃分的影響程度不同來進行數據對象間相似度度量的方法。

在統(tǒng)計學常用平均值和標準差評價一組數值型數據的集中趨勢和分散程度。然而多數真實數據集的不同屬性在取值范圍和取值單位上不相同，這時標準差不適合比較兩組或多組不同尺度和不同量綱數據的離散程度。因此本文定義了離散度函數來解決這一問題，它可以在領域知識未知的情況下區(qū)分數據屬性的重要程度。

定義1設數據集為二元組＜D，X>，其中D=｛di|i=1，2，3，…，n｝為記錄集，di為單個數據對象；X=｛xij|j=1，2，3，…，m｝為屬性集，xij為單個數據對象的屬性特征，xij表示數據對象di的第j維屬性特征，則數據集＜D，X>中的第j維屬性的均值與標準差如式（1）、式（2）所示：

定義2離散度函數（Discrete Function，DF）表示屬性的離散程度如式（3）所示：

其中，如果μj=0且σj≠0，則|σj/μj|=σj；如果μj=0且σj=0，則DFj=0；DFj∈［0，1］。數據屬性的DF值越大表示該屬性值的集合的分布越離散，則該屬性對聚類的劃分過程影響程度越大，反之越小。DFj=0表示數據集＜D，X＞中的第j個屬性離散程度為0，即在聚類過程中第j個屬性可以忽略不計，此時可將其刪除來降低算法的時間和空間開銷。

基于各屬性的離散程度，計算數據屬性間的相似度如式（4）所示。樣本間的相似度為各屬性間的距離求和所得，其表達式如式（5）所示。

在式（4）和（5）中，p∈｛1，2，…，n｝、q∈｛1，2，…，n｝且p≠q。Djpq表示樣本p和樣本q第j維屬性的相似度，AWpq表示樣本p和樣本q的相似度距離，其中xpj和xqj分別表示樣本p和樣本q的第j維屬性。

3.2 FAWK算法描述

基于傳統(tǒng)K-means的基本原理，結合3.1節(jié)提出的相似度度量方法，本文提出了FAWK算法。該算法的基本思想是先根據式（3）計算每維數據屬性特征的DF值，然后隨機選擇K個樣本點作為初始聚類中心，并根據式（5）進行初次數據劃分；根據劃分結果更新聚類中心，并對劃分結果進行分析判斷，檢測是否達到迭代截止條件；反復執(zhí)行，直到算法滿足迭代截止條件時聚類完成。

3.3 時間復雜度分析

K-means算法的時間復雜度為O（lKnm），其中l(wèi)為算法的迭代次數，K為簇的數目，n是所有對象的數目，m是對象所包含的屬性的數目。FAWK的時間開銷主要有兩部分組成，其一是數據屬性離散程度計算帶來的時間消耗，該部分的時間復雜度為O（nm）；其二是聚類劃分過程的時間開銷，這部分的時間復雜度為O（lKnm）。因此，整個算法的時間復雜度為O（lKnm）。本文所涉及的幾種聚類算法的時間復雜度匯總表如表1所示。

表1 算法時間復雜度匯總表

4 實驗結果與分析

為驗證FAWK算法的有效性，本文首先將FAWK在不同的UCI數據集上進行實驗，并與傳統(tǒng)K-means［14］、K-means++［14］、DPC［15］、DBSCAN［16］、AGNES［17］、IADCK［12］、KWDM［13］、MDK［10］和WLVK［11］共9個不同的聚類算法進行實驗對比分析。其次，將本文提出的AW方法與歐式距離（ED）、加權歐式距離（WED）、夾角余弦距離（ACD）、切比雪夫距離（CD）和SD［8］五種用于聚類算法的相似度度量方法進實驗測試與分析。最后，以LAMOST項目作為應用背景進行算法驗證。

4.1 UCI數據集實驗分析

本文選取了UCI數據庫中的8個標準數據集作為實驗測試數據。8個數據集的相關信息匯總表如表2所示。

對于任何一種算法的驗證都需要對其進行合理的綜合評價，基于不同的算法，會有不同的評價方法或評價指標。本文用基于聚類結果的準確率（AC）對實驗結果進行評價。AC指的是聚類結果中預測正確的樣本占總樣本的比。各聚類算法在不同數據集上獨立實驗的聚類結果準確率統(tǒng)計如圖1所示。

圖2展示了基于不同相似度度量方法的K-means在8個UCI標準數據集上獨立實驗的聚類結果準確率。結合圖1和圖2，可以發(fā)現FAWK的大部分實驗結果優(yōu)于其他幾種聚類算法，僅有少部分實驗結果不是最優(yōu)，但其也并不是最差的，因此圖1和圖2的實驗結果證明了本文所提算法的有效性。

表2 實驗中使用的數據集信息匯總表

圖1 10個聚類算法在不同數據集上的準確率統(tǒng)計圖

圖2 基于不同相似度度量方法的K-means算法的準確率統(tǒng)計圖

圖3分別統(tǒng)計了各算法在不同的數據集上獨立運行十次的平均時間消耗情況。圖3中的子圖（a）展示了各算法對六個數據量相差較小且總量相對較小的數據進行聚類實驗的平均運行時間；子圖（b）和子圖（c）展示了各算法在兩個數據量相對較大的數據集HTRU2和Wireless上實驗測試的平均運行時間。分析圖3可以發(fā)現FAWK運行時間與其他幾種算法相比較快，尤其在Pima、Wireless和HTRU2數據集上本文算法的運行時間與其他算法對比優(yōu)勢更加明顯。

圖4統(tǒng)計了基于不同相似度度量方法的K-means在8個標準數據集上獨立運行十次的平均迭代次數。圖4顯示，本文所提方法的平均迭代次數少于其他幾種相似度計算方法，說明本文所提方法能很好地反映數據間的相似度，減少了算法的迭代次數，加快了聚類的收斂速度。結合圖4和圖2可以發(fā)現將加權歐式距離作為K-means算法聚類過程的劃分標準對Soybean-small數據集進行實驗測試的平均迭代次數為2，聚類結果的準確率為36.17%，由此可知該聚類過程陷入了局部最優(yōu)。

圖3 各算法在不同UCI數據集上的運行時間統(tǒng)計圖

4.2 恒星光譜數據實驗分析

為了驗證本文所提出聚類方法的實用性，從LAMOST DR5［18～19］中隨機選取SNR大于等于40的A、F和G類恒星光譜數據組成光譜數據集進行實驗測試與分析。由于原始數據的Flux都超過3000維且不是標準數據，所以在進行實驗前先使用最大最小方法［20］對光譜數據進行歸一化，并根據哈佛分類系統(tǒng)的恒星分類依據以及恒星天體光譜研究領域專家的經驗和意見，選定恒星中普遍存在的28個元素的吸收線周圍最近鄰的三維Flux數據來構造數據總量為1000、2000、5000、10000和50000共五個不同量級吸收線特征集進行聚類實驗分析。

圖5為光譜數據集的聚類結果準確率統(tǒng)計圖，圖中垂直于縱坐標的實線為輔助線。從圖5中可以發(fā)現在不同量級的光譜數據集上FAWK聚類結果的AC保持相對穩(wěn)定且優(yōu)于其他幾種算法，說明其具有一定的實用性。

圖5 恒星光譜數據的聚類結果統(tǒng)計圖

圖6展示了各算法在不同量級的恒星光譜數據集上獨立運行十次的平均時間消耗情況。圖6中橫坐標為不同量級的光譜數據集，縱坐標為平均運行時間。圖6中子圖為矩形框中折線的局部放大圖。

圖6 各算法在恒星光譜數據集上的運行時間

分析圖6可以發(fā)現FAWK在光譜數據集上的平均運行時間與K-means相接近且優(yōu)于其他幾種聚類算法，隨著數據量的增加本文算法的運行時間與其他算法對比優(yōu)勢明顯增加。由3.3小節(jié)可知本文算法的時間開銷相比傳統(tǒng)K-means增加了第一部分數據屬性離散程度計算帶來的時間消耗，但是結合圖3和圖6可以發(fā)現FAWK與傳統(tǒng)K-means的平均運行時間近似相等，出現這種情況的原因主要有兩方面：其一，傳統(tǒng)K-means采用歐式距離來度量樣本間的相似性，本文所提算法采用加權屬性求和作為樣本間的相似度度量方法，而本文算法在計算樣本間相似度時的時間開銷要小于計算歐式距離所帶來的時間開銷；其二，本文所提的AW方法減少了算法的迭代次數，加快了聚類過程的收斂速度。因此，FAWK雖然在離散程度計算過程增加了一定的時間開銷，但是其整體算法的運行時間與傳統(tǒng)K-means的運行時間相接近且低于其他幾種聚類算法。

5 結語

聚類是一種重要的無監(jiān)督學習方法，它以數據為基礎通過學習數據中的信息來實現分組，而屬性特征是構成數據樣本的基本單元，是數據信息最原始的載體，不同的屬性在取值范圍、分布情況和重要程度上存在一定的差異。為解決聚類樣本的各屬性對聚類結果影響程度存在差異的問題，本文融合K-means提出一種基于屬性加權的快速K-means算法。該算法通過離散度函數來分析和量化不同數據屬性的重要程度；然后結合各屬性的重要程度定義了新的相似度計算方法作為K-means算法的聚類劃分標準。在UCI和LAMOST數據集上的實驗結果證明了本文算法的有效性和實用性。此外，本文提出的AW是一種度量數據樣本間相似性的計算方法，接下來將進一步對其擴展研究以適用于不同的聚類算法。