王義武，楊余旺

南京理工大學(xué) 計算機(jī)科學(xué)與工程學(xué)院，南京210094

1 引言

K-means作為經(jīng)典的劃分聚類算法，簡潔、高效、快速的特點使其在圖像分割、推薦系統(tǒng)、數(shù)據(jù)挖掘等領(lǐng)域有著廣泛的應(yīng)用。在K-means迭代的過程中，將每一個數(shù)據(jù)劃歸到距離最近的簇中，更新簇中心并作為下一次迭代的中心點，不斷重復(fù)這一過程直到收斂，可以知道，算法每一次迭代都需要計算所有數(shù)據(jù)點和全部聚類中心之間的距離。隨著數(shù)據(jù)量的急劇增加和業(yè)務(wù)場景的多樣化，對K-means也提出了更加嚴(yán)格的要求，經(jīng)典的K-means 算法難以支撐PB 級別數(shù)據(jù)處理下的性能要求，如何加快算法處理過程，在最少的時間內(nèi)得出有效結(jié)果顯得越來越重要。

針對K-means的過程的不同處理，有多種加速收斂方法。如文獻(xiàn)[1]利用Elkan 三角判定思想對聚類中心點進(jìn)行篩選，只對最可能的若干中心點計算距離，從而節(jié)約大量的時間消耗；文獻(xiàn)[2-3]通過引入kd 樹，初始聚類中心從多維數(shù)據(jù)某一維的區(qū)間等間隔集中選取，以及在數(shù)據(jù)對象分配過程中采用剪枝策略來提高算法的運(yùn)行效率。文獻(xiàn)[4]利用馬爾可夫鏈可用于有效地近似K-means++的中心點選擇過程，但不要求對數(shù)據(jù)分布，僅遍歷一次數(shù)據(jù)集就可找出K 個聚類中心。除此之外，常用的方法還有Mini Batch抽樣、PCA降維等，均可以降低K-means達(dá)到收斂時所需計算量。

本文空間投影的思想，利用變換矩陣將特征劃分為聚類空間和噪聲空間，且相對于原始空間，聚類空間信息密度更高，維度更小，從而使得K-means降低每次計算距離的時間消耗，并且可以達(dá)到降維和特征篩選的效果[5-6]。

2 相關(guān)概念

為了更好地對算法進(jìn)行描述，做出以下約定。

對于類別U，其中心點第j 維度的計算公式[7]為：

n 為類U 的數(shù)據(jù)個數(shù)，Xij為Xi第j 維數(shù)據(jù)。

歐氏距離的計算公式[8]為：

其中，Xi,Xj表示數(shù)據(jù)集中的m 維的數(shù)據(jù)對象，k 表示維度。

本文使用到符號[9-10]如表1所示。

表1 符號約定

對于簇i，其散布矩陣Si計算公式為：

對于總體數(shù)據(jù)，其散布矩陣SS計算公式為：

3 AC K-means

3.1 損失函數(shù)

在傳統(tǒng)K-means算法中，損失函數(shù)為誤差平方和函數(shù)，計算方式如下：

其中，X 為簇Ci中的元素，Ui為簇Ci的中心，k 為簇的個數(shù)，在K-means迭代的過程中，尋求使得Jc達(dá)到最小的情況。在AC K-means的算法思想中，數(shù)據(jù)的部分維度就可以用來刻畫所有的數(shù)據(jù)結(jié)構(gòu)，可以將數(shù)據(jù)的維度分為兩個子空間，一個是m 維子空間（聚類空間），其包含了所有的結(jié)構(gòu)信息，余下的d-m 維空間（噪聲空間），不包含任何有用的聚類結(jié)構(gòu)信息。

為了獲取有價值的空間信息，降低無用信息對聚類性能的影響，將原始數(shù)據(jù)映射為不同的兩個子空間，進(jìn)行了如下的轉(zhuǎn)換。

假設(shè)有正交矩陣V，使用其對原始d 維空間進(jìn)行映射，得到變換后的d 個特征，前m 個特征對應(yīng)聚類空間[11]，最后的(d-m)個特征對應(yīng)噪聲空間。為此將進(jìn)行投影來達(dá)到空間轉(zhuǎn)換的目的：

其中，Im表示m×m 的單位矩陣，0d-m,m表示(d-m)×m的零矩陣。

因此可將傳統(tǒng)K-means中誤差平方和函數(shù)可擴(kuò)展為：

Jc由兩個部分組成，前者代表了聚類空間的信息，包含了原始空間的特征，另一個代表了噪聲空間的信息，所要做的就是使得噪聲空間的結(jié)構(gòu)信息盡量小，聚類空間的信息盡量大，達(dá)到兩者的平衡。通過優(yōu)化這個目標(biāo)函數(shù)，可以找到K-means在最優(yōu)子空間下的最優(yōu)解[12-13]。

將數(shù)據(jù)投影為聚類空間和噪聲空間后，不再通過原維度下的歐氏距離計算距離，而是使用聚類空間的投影，即在子空間內(nèi)找出最近中心點。比較的公式如下：

在算法開始時首先需要對隨機(jī)正交矩陣V 進(jìn)行初始化，這里可以通過任一矩陣的奇異值分解獲得，Pc矩陣中的m 可參考設(shè)為d/2。

在每次迭代中，保持V、m 和Ui的值是固定的，并將每個數(shù)據(jù)點分配到在聚類空間距離最小的簇，從而使得聚類空間形式下的損失函數(shù)最小化[14]。

3.2 參數(shù)更新

K-means算法中，每一次迭代后僅對中心點進(jìn)行更新，在而在AC K-means中，由于存在正交矩陣V、聚類空間維度m、Si等未知參數(shù)，所以在算法執(zhí)行過程中也需要對其進(jìn)行更新，下面使用到的符號和表1中的約定意義相同。

對于簇的中心點仍采用傳統(tǒng)K-means 中的更新方法，參考公式（1）。下面將給出正交矩陣V 的更新方式。

首先固定聚類空間維度m 的值，這里取為d/2，在AC K-means算法中，損失函數(shù)為：

可以把Jc最小化變?yōu)榫仃囂卣髦捣纸鈫栴}。

利用散布矩可簡化為：

根據(jù)矩陣知識，對任意矩陣Z，滿足：Tr( PCP CTZ )=，則公式（9）可以繼續(xù)進(jìn)行如下化簡：

對于正交矩陣V,Tr(VTSSV )為常數(shù)（Tr表示矩陣的跡）。

從PC的定義可知，的左上方是一個m×m的單位矩陣，其余元素的值為0。且僅PC與m 相關(guān)，V的估計不受m 的影響，損失函數(shù)被轉(zhuǎn)化為求矩陣跡的最小值。

3.3 算法整體設(shè)計

本文的初始中心與K 值的設(shè)定和傳統(tǒng)K-means保持一致，使用隨機(jī)采樣的方法獲得；在聚類空間內(nèi)，各個維度仍然是數(shù)值型變量，所以可使用歐氏距離作為相似性度量方式。對于每一個樣本根據(jù)聚類空間的投影找出并劃入最近的簇中，同時對隨機(jī)正交矩陣和聚類空間信息進(jìn)行更新用于下一次迭代，當(dāng)所有數(shù)據(jù)都被取樣或者滿足一定條件，算法停止。

以下是改進(jìn)后算法整體細(xì)節(jié)框架。

輸入：數(shù)據(jù)集S；n 個初始聚類中心Ui,i ∈[1,n]。

輸出：k 個類；正交矩陣V；聚類空間維度m。

1.初始化隨機(jī)正交矩陣V；

2.初始化聚類空間維度d；

3.計算數(shù)據(jù)集S 的中心US；

4.計算數(shù)據(jù)集S 的散布矩陣SS；

5.repeat

6.Cj←?

7.?x ∈S：

9.Cj←Cj∪{x}

10.?i ∈[1,k]：

15.until convergence

算法核心包括聚類空間投影、找出最近的簇、參數(shù)更新。其中S 是樣本數(shù)據(jù)；V 為隨機(jī)正交矩陣；m 初始值設(shè)置為d/2，因為并沒有掌握數(shù)據(jù)的先驗信息，對聚類空間的維度并不了解，所以這一值不能選擇得過大或者過小，否則會對數(shù)據(jù)間相似度的計算造成影響，但隨著每一次迭代的進(jìn)行，都會對m 動態(tài)更新；利用在樣本子空間內(nèi)找出最近的簇；解出矩陣的特征向量對V 進(jìn)行更新，這里要求按照特征值由小到大將特征向量排序。

4 實驗結(jié)果與分析

4.1 實驗環(huán)境和數(shù)據(jù)集

實驗環(huán)境為Intel Core i5 2.5 GHz，8 GB RAM，實驗數(shù)據(jù)采用UCI數(shù)據(jù)集和部分人工數(shù)據(jù)集，標(biāo)準(zhǔn)數(shù)據(jù)集用于驗證各聚類算法的效果，make_blobs生成的人工數(shù)據(jù)集用于比較算法性能在時間上的差異。

實驗選用的UCI數(shù)據(jù)集信息如表2所示。

表2 UCI數(shù)據(jù)集

4.2 聚類對比實驗

先將PCA、ICA、LDA 分別應(yīng)用在4 個數(shù)據(jù)上：Iris、Seeds、Forest Types、Connectionist Bench，對數(shù)據(jù)進(jìn)行降維，n components 統(tǒng)一設(shè)置為2；隨后使用K-means算法對降維后的數(shù)據(jù)聚類，統(tǒng)計在各個數(shù)據(jù)集上的準(zhǔn)確率(P)、召回率(R)、F-measure(F)。同時計算AC Kmeans在數(shù)據(jù)集上的聚類效果。得到的F-measure值如表3所示。

表3 為各算法在數(shù)據(jù)集上的聚類結(jié)果，準(zhǔn)確率方面，AC K-means 在Forest Types、Connectionist Bench得分最高，在Iris、Seeds上分別略低于PCA K-means和LDA K-means算法；召回率方面，AC K-means在Iris、Seeds 上效果好于其他算法，另外兩個數(shù)據(jù)集上排名第二、第三；F-measure 方面，AC K-means 在Iris、Seeds、Forest Types 三個數(shù)據(jù)集上取得了較好的成績，且Fmeasure值均在0.83以上，說明算法是穩(wěn)定且高效的。

為了直觀對比AC K-means算法的聚類效果，這里使用PCA K-means與其對比。

從圖1 到圖4 的實驗結(jié)果能夠得出，在新的空間投影方法下，原始數(shù)據(jù)空間被良好地分割，相對于PCA降維，改進(jìn)后算法能夠更好地將重要的特征與非重要的特征分開，并且特征位置越靠前的重要性越高，包含的信息也越豐富。

表3 F-measure值

圖1 Iris數(shù)據(jù)集上聚類效果對比

圖2 Seeds數(shù)據(jù)集聚類效果對比

圖3 Connectionist Bench數(shù)據(jù)集上聚類效果對比

圖4 Forest Types數(shù)據(jù)集上聚類效果對比

圖5 表現(xiàn)了聚類時間隨數(shù)據(jù)量變化的趨勢，隨著數(shù)據(jù)量的增加，算法完成所需要時間幾乎呈線性變化，其中PCA K-means 算法在各個數(shù)據(jù)量上需要時間均最多，LDA K-means耗時略小于ICA K-means，AC Kmeans 花費(fèi)時間最少，這是由于，經(jīng)過不同的降維處理后得到的低維數(shù)據(jù)的結(jié)構(gòu)是不同的，PCA作為無監(jiān)督方法，尋找方差最大的投影方向或者說保留不存在相關(guān)性的特征，并不考慮數(shù)據(jù)間實際的類別信息，而ICA 相較于PCA要求更加嚴(yán)格，希望輸出的屬性盡量獨立；LDA是有監(jiān)督的降維方法，其目標(biāo)利用散布矩陣實現(xiàn)降維后類間距離最大，類內(nèi)距離最小，對于實驗中的數(shù)據(jù)集可以很好地保留其數(shù)據(jù)分布特征，因此收斂速度也更快；AC K-means在迭代的過程中，最近中心點的搜索次數(shù)相對較少且數(shù)據(jù)維度合理，計算所花時間最少。

圖5 時間隨數(shù)據(jù)量變化

5 結(jié)束語

本文中AC K-means 算法在四個UCI 標(biāo)準(zhǔn)數(shù)據(jù)集上均取得了較好的聚類效果，整體優(yōu)于傳統(tǒng)的先降維再聚類的方法；同時與PCA K-means對比實驗可以看出，AC K-means可以很好地進(jìn)行特征篩選和轉(zhuǎn)化，保留了有效空間信息，并用于下一次迭代。針對不同數(shù)據(jù)量和聚類中心數(shù)的樣本，AC K-means的收斂時間明顯低于實驗中其他算法，說明了本文所提算法具有良好的計算性能，相較于PCA等降維方法，本文提出的算法使用場景相對廣闊，在聚類空間結(jié)構(gòu)不明顯的情況下，也能較好工作，且不需要類別等先驗信息；當(dāng)然也存在不足之處，AC K-means的核心思想是用部分空間結(jié)構(gòu)刻畫數(shù)據(jù)信息，當(dāng)特征維度高且稀疏時，算法不一定能夠找到最優(yōu)子空間，這也是需要進(jìn)一步優(yōu)化的方向。