李 峰，李明祥 ，張宇敬

1.河北金融學(xué)院 信息管理與工程系，河北 保定 071051

2.河北省高校智慧金融應(yīng)用技術(shù)研發(fā)中心，河北 保定 071051

1 引言

近些年，非監(jiān)督學(xué)習(xí)情況下的數(shù)據(jù)聚類分析研究不僅在理論上取得了長足的發(fā)展，如文獻(xiàn)中提到的ET-SSE[1]、OLDStream[2]、k-MS[3]、SDPC[4]及最小誤差平方和K-means初始聚類中心優(yōu)化[5]等算法，并且還廣泛應(yīng)用于圖形圖像處理[6]、文本分析[7]、視頻處理[8]、網(wǎng)絡(luò)輿情分析[9]、交通導(dǎo)航和各類推薦系統(tǒng)等各個(gè)領(lǐng)域。K-means 模型是最基本和最重要的聚類算法之一。該模型在歐幾里得空間定義了包含n個(gè)向量元素的數(shù)據(jù)集D={d1,d2,…,dn}，目的是把n個(gè)向量元素分配到k組不同的聚類簇中S={S1,S2,…,Sk}，其目標(biāo)函數(shù)是：

其中S代表聚類結(jié)果，Cost(Si)表示聚類簇Si中所有數(shù)據(jù)點(diǎn)到聚類中心的距離平方之和，表示為：

其中dis(d,Ci)表示數(shù)據(jù)點(diǎn)d與Ci的距離，Ci表示聚類簇Si的中心。為了使目標(biāo)函數(shù)Cost(S)的取值最小，K-means算法的基本執(zhí)行過程為：第一步，隨機(jī)選取k個(gè)點(diǎn)作為聚類中心的初值；第二步，把數(shù)據(jù)集中的n個(gè)數(shù)據(jù)分配到最近的聚類中；第三步，更新每個(gè)聚類的中心；第四步，重復(fù)執(zhí)行第二步和第三步直到目標(biāo)函數(shù)趨于收斂為止。雖然K-means算法是一個(gè)高效的算法，但是它依賴初始化中心的選擇，好的聚類中心初值能夠提高聚類的速度和聚類的效果。因此，很多關(guān)于聚類中心初始化的算法就被提了出來。

Arthur等人[10]提出的K-means++算法是從數(shù)據(jù)集中隨機(jī)選取一個(gè)數(shù)據(jù)作為第一個(gè)聚類的中心，之后第i個(gè)聚類中心的選取，滿足下列概率條件：

其中，dis(d)表示數(shù)據(jù)點(diǎn)到最近中心的距離。該方法認(rèn)為初始聚類中心應(yīng)該離的越遠(yuǎn)越好，這樣就可能會把相鄰的多個(gè)小聚類當(dāng)成一個(gè)龐大的聚類進(jìn)行處理，影響聚類的精確度。

Chowdhury等人[11]提出的Seed Point Selection algorithm算法，通過使用具有距離約束條件的像素強(qiáng)度的聯(lián)合概率最大化概念來選擇種子點(diǎn)。此方法雖然優(yōu)化了聚類中心的選擇，但由于最優(yōu)聚類數(shù)是基于7個(gè)不同的聚類有效性指數(shù)的組合來確定的，所以該算法的計(jì)算過程相對比較復(fù)雜，在最終的聚類效率上會有一定的損失。

Tzortzis 等人[12]提出的 MinMax 版本的K-means模型改變了目標(biāo)函數(shù)，利用最大的簇內(nèi)方差εmax代替Cost(S)作為潛在的目標(biāo)函數(shù)。該方法會根據(jù)他們的方差為聚類分配權(quán)重，通過迭代過程不斷更新權(quán)重和聚類中心，避免了大方差聚類的出現(xiàn)。如果絕對的限制大方差聚類的出現(xiàn)，在一些實(shí)際應(yīng)用中可能會造成聚類效果的誤差，從而引起數(shù)據(jù)分析的結(jié)果不夠準(zhǔn)確。

此外，除了以上關(guān)于選擇聚類中心初值的算法，還有關(guān)于提高K-means 聚類速度的算法也被提了出來。通過特征選擇或特征提取能夠降低數(shù)據(jù)集的維度從而提高K-means聚類的速度。特征選擇不同于特征提取，特征選擇是選擇一個(gè)小的輸入特征子集；而對于特征提取，則是基于輸入數(shù)據(jù)集重新構(gòu)建新的人工特征。這些機(jī)制均可以在很大程度上提高K-means的聚類速度[13-14]。

Elkan 等人[15]提出利用三角不等式提高K-means 聚類的速度，減少了K-means內(nèi)部循環(huán)的計(jì)算。由于在通用的K-means 中，每個(gè)數(shù)據(jù)點(diǎn)和中心之間的距離被計(jì)算，并且每個(gè)數(shù)據(jù)點(diǎn)被分配到其最近的中心；而使用三角不等式，通過忽略來自某些中心的數(shù)據(jù)點(diǎn)的一些距離計(jì)算，保留一些額外信息來加速這個(gè)循環(huán)。當(dāng)在數(shù)據(jù)規(guī)模不變且聚類數(shù)量增多的情況下，由于每個(gè)聚類可忽略的數(shù)據(jù)點(diǎn)減少，從而導(dǎo)致在提升聚類速度方面有所降低。

Lai 等人[16]提出一種過濾算法，利用中心變化來加速聚類過程。該算法將聚類劃分為靜態(tài)和動(dòng)態(tài)兩種，然后通過從動(dòng)態(tài)聚類中心集中查找每個(gè)節(jié)點(diǎn)的候選者來降低計(jì)算復(fù)雜性。雖然使用了一種簇位移信息的技術(shù)排除K-D 樹中所有節(jié)點(diǎn)不可能的聚類中心，但隨著樹中節(jié)點(diǎn)規(guī)模的增大，這種排除技術(shù)會影響整個(gè)聚類速度。

在聚類數(shù)量增多的情況下，以上方法都有一定的局限性，于是提出了一種局部迭代的快速K-means聚類算法PIFKM+?（Partial Iterative FastK-Means plus-minus）。該算法借鑒了I-K-means?+[17]算法的聚類分割和聚類刪除的思想，優(yōu)化了其算法，在已有聚類的基礎(chǔ)上，在每次迭代過程中，首先依據(jù)聚類成本最大和聚類標(biāo)簽為可分割這兩個(gè)條件選擇能夠被分割的聚類Si（+），然后依據(jù)聚類成本最小和聚類標(biāo)簽為可刪除這兩個(gè)條件選擇能夠被刪除的聚類Sj（?），最后對這些聚類以及鄰居聚類進(jìn)行局部聚類更新，降低了算法的時(shí)間復(fù)雜度，提高了算法的執(zhí)行效率和聚類的精確性。圖1（a）展示的是K-means聚類效果，圖1（b）展示的是PIFKM+?算法的聚類效果，把圖（a）中圓圈部分進(jìn)行了聚類分割，方形部分進(jìn)行了聚類刪除。

2 算法的相關(guān)定義

2.1 基本概念

在參考I-K-means?+的基礎(chǔ)上，對文中用到的一些相關(guān)術(shù)語做出了定義。

圖1（a） K-means的聚類結(jié)果

圖1（b） PIFKM+-的聚類結(jié)果

聚類的分割：當(dāng)一個(gè)聚類簇Si中所有數(shù)據(jù)點(diǎn)到該聚類中心Ci的距離平方之和Cost(Si)很大，并且聚類簇Si沒有被標(biāo)記為不能分割時(shí)，從中任選一點(diǎn)作為第二個(gè)中心，然后圍繞這兩個(gè)中心重新聚類并更新Ci和，直到目標(biāo)函數(shù)Cost(Si)和收斂為止，如圖2所示。

圖2（a） 分割之前的聚類簇

圖2（b） 分割之后的聚類簇

聚類的刪除：當(dāng)一個(gè)聚類簇Sj的距離平方之和Cost(Sj)很小，并且沒有被標(biāo)識為不能刪除，同時(shí)還存在一個(gè)強(qiáng)鄰居Sk時(shí)，可以刪除其聚類中心Cj并把Sj中的數(shù)據(jù)點(diǎn)合并到Sk里，然后再更新Sk的中心Ck，直到目標(biāo)函數(shù)Cost(Sk)收斂為止，如圖3所示。

圖3（a） 刪除之前的聚類簇

圖3（b） 刪除之后的聚類簇

聚類的鄰居：聚類Si是聚類Sj的鄰居，當(dāng)且僅當(dāng)聚類Sj中的數(shù)據(jù)點(diǎn)P，它的第一最近中心是Cj，而第二最近中心是Ci。

雖然聚類Si是聚類Sj的鄰居，但反過來不一定成立，并且一個(gè)聚類可以有多個(gè)鄰居。所以聚類的鄰居是非對稱的，是一對多的關(guān)系。

聚類的強(qiáng)鄰居：兩個(gè)聚類是強(qiáng)鄰居關(guān)系，當(dāng)且僅當(dāng)兩個(gè)聚類互為鄰居。

如果一個(gè)聚類是在當(dāng)前階段通過分割其他聚類而得到的，那么在下次迭代過程中這個(gè)聚類以及它的強(qiáng)鄰居都不能被刪除。同理，如果一個(gè)聚類在當(dāng)前階段被刪除，那么在下次迭代過程中，它的強(qiáng)鄰居就不能被分割。

可能受影響的點(diǎn)：在局部聚類的過程中，當(dāng)且僅當(dāng)數(shù)據(jù)點(diǎn)P的第一或者第二最近中心是Ci時(shí)，數(shù)據(jù)點(diǎn)P才是聚類中心Ci的可能受影響點(diǎn)。

2.2 相關(guān)定義

在迭代過程中對兩個(gè)聚類簇進(jìn)行分割刪除之前，必須找到合適的對象，才能使得PIFKM+?算法的聚類成本小于傳統(tǒng)的K-means。文中算法均采用公式（1）作為統(tǒng)一的聚類成本函數(shù)。

定義1 用Cost-(Si)表示分割聚類簇Si所減少的聚類成本。如果聚類簇Si被分割成和兩個(gè)聚類簇，那么Cost-(Si)就可以表示為聚類簇Si的成本減去和兩個(gè)聚類簇的成本，即：

下面對Cost-(Si) 進(jìn)行估算，由于Cost(Si) 是已知的，所以只需要計(jì)算兩個(gè)值就可以得到Cost-(Si)的值。聚類簇Si中，每個(gè)數(shù)據(jù)點(diǎn)與聚類中心Ci的平均距離可以表示為：

其中，|Si|表示聚類簇Si中數(shù)據(jù)的個(gè)數(shù)。假設(shè)Si被分割之后，數(shù)據(jù)點(diǎn)被平均分配到兩個(gè)新的聚類簇中，即：

把公式（6）和（7）代入公式（3）得：

定義2 用Cost+(Sj)表示刪除聚類簇Sj所增加的聚類成本。如果聚類簇Sj被刪除，那么它的數(shù)據(jù)點(diǎn)會被合并到它的強(qiáng)鄰居中。因此Cost+(Sj)可以近似表示為：

其中，Ck是聚類簇Sj中數(shù)據(jù)點(diǎn)的第二最近中心點(diǎn)。

推論在PIFKM+?算法的局部迭代聚類過程中，符合分割和刪除條件的一對聚類簇，必須滿足條件：

證明使Cost(S)表示K-means聚類的成本，Cost(S')表示經(jīng)過聚類簇的分割刪除之后的聚類成本。因?yàn)镾i被分割之后，聚類成本減少了，而Sj被刪除之后，聚類成本又增加了，所以Cost(S')=Cost(S)-Cost-(Si)+Cost+(Sj)。要使不等式Cost(S')

3 PIFKM+-算法

3.1 算法思想

PIFKM+?是在傳統(tǒng)K-means 聚類[18-19]的基礎(chǔ)上，通過一個(gè)局部迭代程序不斷地尋找那些能夠被分割的聚類簇和能夠被刪除的聚類簇，并對受影響的數(shù)據(jù)進(jìn)行重新聚類處理的算法實(shí)現(xiàn)，目的是在聚類數(shù)量增多的情況下，降低算法的時(shí)間復(fù)雜度，進(jìn)一步提高聚類的效率和聚類結(jié)果的精確度。如圖4 給出了PIFKM+?算法的基本執(zhí)行過程。

圖4 PIFKM+?算法流程圖

3.2 P-K-means算法

P-K-means 算法是傳統(tǒng)K-means 的一種強(qiáng)化版本，僅適用于可能受影響的點(diǎn)。在PIFKM+?的聚類分割刪除階段中，只有一部分聚類簇被更改，因此P-K-means僅應(yīng)用于整體解決方案的局部聚類。例如，在圖5 中，PIFKM+?在聚類分割刪除階段，確定應(yīng)該刪除聚類簇S8，并且應(yīng)該分割聚類簇S3。所謂刪除S8，并沒有真的刪除，只是把中心C8的位置改變?yōu)榫垲惔豐3中的一個(gè)隨機(jī)點(diǎn)。PIFKM+?算法通過只處理受影響的點(diǎn)并忽略其他未受影響的點(diǎn)來加速重新聚類過程。下面給出P-K-means算法在此例的基本執(zhí)行過程。

圖5 PIFKM+?的聚類分割刪除階段

假設(shè)算法已經(jīng)找到了一對分割刪除聚類簇S3和S8，并且知道S3將被分割，S8將被刪除：

步驟1 定義集合AC、APc、APs和ADc，均初始化為空集。

步驟2ADc={C9}#C9為C8的強(qiáng)鄰居聚類中心。

步驟3APc←C8被所在聚類受影響的數(shù)據(jù)點(diǎn)和ADc包含中心所在聚類受影響的數(shù)據(jù)點(diǎn)。

步驟4C8←取聚類簇S3中的一個(gè)隨機(jī)數(shù)據(jù)點(diǎn)。

步驟5AC={C3}?{C8}。

步驟6APs←AC所有中心所在聚類受影響的數(shù)據(jù)點(diǎn)。

步驟7 通過集合APc包含的數(shù)據(jù)點(diǎn)，更新集合ADc包含的中心。

步驟8 通過集合APs包含的數(shù)據(jù)點(diǎn)，不斷更新集合AC包含的中心，直到這些中心收斂為止。

步驟9 程序運(yùn)行結(jié)束。

3.3 PIFKM+?執(zhí)行過程

這一部分描述了PIFKM+?算法的完整執(zhí)行過程，其中詳細(xì)介紹了尋找分割刪除聚類對的滿足條件。

步驟1 應(yīng)用K-means 算法對原有數(shù)據(jù)集進(jìn)行聚類處理，得到聚類的成本Cost(S) 和聚類的解決方案S={S1,S2,…,Sk}以及各聚類中心。

步驟2 初始化計(jì)數(shù)變量count=0。

步驟3 在解決方案S中，選擇Cost-(Si)最大的聚類簇Si，并且該簇沒有被標(biāo)記為不可分。如果沒有符合條件的簇，程序結(jié)束。

步驟4 如果k2 以上聚類簇的Cost-(?) 比Si的Cost-(Si)值大，程序結(jié)束。

步驟5 在解決方案S中，選擇一個(gè)可以被刪除的聚類簇Sj，需要滿足以下條件：

（1）Sj沒有被標(biāo)記為不可刪除；

（2）Si≠Sj；

（3）Si和Sj不是強(qiáng)鄰居；

（4）Cost+(Sj)最??；

（5）Cost-(Si)>Cost+(Sj)。

如果沒有符合條件的簇，程序結(jié)束。

步驟6 如果k2 以上聚類簇的Cost+(?) 比Sj的Cost+(Sj)值小，程序結(jié)束。

步驟7 應(yīng)用P-K-means 算法執(zhí)行聚類的分割刪除操作，然后更新解決方案S，得到最新的解決方案S'。

步驟8 在解決方案S'中，標(biāo)記聚類簇Si和Sj不能移除；把Sj之前的強(qiáng)鄰居標(biāo)記為不能分割。

步驟9 保存最新解決方案S=S'。

步驟10count=count+1。

步驟11 如果變量count值小于k2，跳轉(zhuǎn)到步驟3。

步驟12 程序結(jié)束。

3.4 PIFKM+?與傳統(tǒng)K-mean的性能比較

傳統(tǒng)K-means 算法的聚類結(jié)果對于聚類中心初值的選擇有很大的敏感性。如果聚類中心初值選擇合適，其聚類成本較低，收斂性較好；反之，聚類成本較高，收斂性較差。而PIFKM+?算法是在傳統(tǒng)的K-means 聚類結(jié)果的基礎(chǔ)上，把那些能夠被分割的聚類成本較大的聚類進(jìn)行分割，把能夠被刪除的聚類成本很小的聚類進(jìn)行刪除（合并），最終使得聚類的總成本小于傳統(tǒng)的K-means 聚類成本，從而達(dá)到進(jìn)一步優(yōu)化聚類效果，降低聚類總成本，提高聚類結(jié)果收斂性的效果。

4 實(shí)驗(yàn)測試及結(jié)果分析

為了驗(yàn)證PIFKM+?算法的聚類效果、高效率性和可行性，使用大規(guī)模仿真數(shù)據(jù)和真實(shí)數(shù)據(jù)進(jìn)行了實(shí)驗(yàn)，同時(shí)對 PIFKM+?與K-means[20]、K-means++[21]兩種算法在聚類效果和運(yùn)行效率上進(jìn)行了對比。所有的算法均采用Python3.6 編碼實(shí)現(xiàn)，整個(gè)實(shí)驗(yàn)在Spyder 集成開發(fā)環(huán)境下進(jìn)行測試，實(shí)驗(yàn)平臺配置為雙核i7處理器，8 GB內(nèi)存，64位Windows 7操作系統(tǒng)。

實(shí)驗(yàn)使用的仿真數(shù)據(jù)集一共包含6組：Data1～Data6，通過Python 的scikit-learn 庫生成。為了便于各種算法聚類效果的可視化，這6 組數(shù)據(jù)集包含的均是二維數(shù)據(jù)，區(qū)別在于不同的聚類個(gè)數(shù)和數(shù)據(jù)量。

真實(shí)數(shù)據(jù)集一共包含3 組，均來自UCI Machine Learning Repository 網(wǎng)站，具體地址 http：//archive.ics.uci.edu/ml/datasets.html。測試數(shù)據(jù)集的詳細(xì)信息描述如表1所示。

表1 實(shí)驗(yàn)數(shù)據(jù)集

4.1 仿真數(shù)據(jù)集測試結(jié)果

如表2，列出了參與測試的算法在仿真數(shù)據(jù)集上所得到的運(yùn)行結(jié)果。對于聚類最終成本Cost而言，PIFKM+?的聚類效果明顯優(yōu)于K-means 和K-means++兩種算法。

對于各算法的運(yùn)行時(shí)間，由于PIFKM+?算法是在K-means聚類的基礎(chǔ)上進(jìn)行進(jìn)一步的優(yōu)化處理，所以在全部的數(shù)據(jù)集上，PIFKM+?算法比K-means 算法的運(yùn)行時(shí)間慢一些，但是在某些數(shù)據(jù)集上的運(yùn)行時(shí)間要比K-means++算法快。為了進(jìn)一步對3種算法進(jìn)行評估，可以從簇內(nèi)的稠密程度和簇間的離散程度來評估聚類的效果。在實(shí)驗(yàn)過程中采用了Calinski-Harabasz（CH）[19]指標(biāo)，該指標(biāo)值越大說明聚類效果越好，如表3所示。

實(shí)驗(yàn)結(jié)果表明，PIFKM+?算法的聚類效果完全優(yōu)于K-means和K-means++的聚類效果。PIFKM+?可以在損失較小速度的情況下提高聚類的效果，降低了聚類的成本。圖6～11顯示了各種算法在6組仿真數(shù)據(jù)集上的聚類效果。

表2 在仿真數(shù)據(jù)集上聚類總成本和聚類總時(shí)間

表3 在仿真數(shù)據(jù)集上Calinski-Harabasz（CH）指標(biāo)統(tǒng)計(jì)結(jié)果

圖6 Data1上3種算法的聚類結(jié)果

圖7 Data2上3種算法的聚類結(jié)果

圖8 Data3上3種算法的聚類結(jié)果

圖9 Data4上3種算法的聚類結(jié)果

圖10 Data5上3種算法的聚類結(jié)果

圖11 Data6上3種算法的聚類結(jié)果

4.2 真實(shí)數(shù)據(jù)集測試結(jié)果

如表4，列出了PIFKM+?算法以及參與測試比較的K-means和K-means++算法在3組真實(shí)數(shù)據(jù)集上所得到的運(yùn)行結(jié)果，包含了聚類總成本、聚類總時(shí)間以及相應(yīng)的比值。PIFKM+?算法的平均運(yùn)行時(shí)間是K-means算法的1.35 倍；PIFKM+?算法的平均聚類成本是K-means 算法的0.94 倍。而與K-means++算法相比，PIFKM+?算法的平均運(yùn)行時(shí)間是K-means++算法的1.07 倍；PIFKM+?算法的平均聚類成本是K-means++算法的0.96 倍。經(jīng)過以上統(tǒng)計(jì)分析，表明了PIFKM+?算法可以在損失較小速度的情況下進(jìn)一步提高聚類的效果。

如表5是通過Calinski-Harabasz（CH）[19]指標(biāo)對參與比較測試的3種算法進(jìn)行聚類效果的評估，指標(biāo)值越大說明聚類效果越好。從實(shí)驗(yàn)結(jié)果可看出，PIFKM+?算法在 Letter-Recognition 和 Anuran Calls（MFCCs）兩個(gè)數(shù)據(jù)集上的聚類效果與K-means 和K-means++算法相比，分別平均提高12.5%和9%。這說明對于聚類數(shù)量增多的數(shù)據(jù)集，PIFKM+?算法的聚類性能優(yōu)于傳統(tǒng)的K-means算法。

表4 在真實(shí)數(shù)據(jù)集上聚類總成本和聚類總時(shí)間

表5 在真實(shí)數(shù)據(jù)集上Calinski-Harabasz（CH）指標(biāo)統(tǒng)計(jì)結(jié)果

圖12 Letter-Recognition上3種算法的聚類結(jié)果

圖13 Wholesale Customers上3種算法的聚類結(jié)果

圖14 MFCCs上3種算法的聚類結(jié)果

由于3 組真實(shí)數(shù)據(jù)的維數(shù)很大不能直接展示聚類效果，為了更好地展示真實(shí)數(shù)據(jù)的聚類效果，實(shí)驗(yàn)過程中先通過主成分分析方法（PCA）對3 組真實(shí)數(shù)據(jù)進(jìn)行了降維處理再聚類，經(jīng)過實(shí)驗(yàn)對比發(fā)現(xiàn)三維聚類效果要略優(yōu)于二維聚類效果，如圖12～14展示的是各種算法在真實(shí)數(shù)據(jù)集上三維空間的聚類效果。

5 結(jié)論

為了解決K-means 算法在聚類數(shù)量增多的情況下因不能選擇合適的聚類中心初值而影響聚類效果這一問題，提出了一種局部迭代的快速K-means 聚類算法（PIFKM+?）。該算法在K-means聚類的基礎(chǔ)上，不斷地尋找能夠被分割和能夠被刪除的聚類簇，并對受影響的局部數(shù)據(jù)進(jìn)行重新聚類處理以此提高聚類的效果。PIFKM+?算法在面對聚類數(shù)量眾多的情況下，具有能夠快速更新聚類、對聚類中心初值不敏感并能夠提高聚類精確度等優(yōu)勢。下一步的工作重點(diǎn)有兩個(gè)：一是如何快速尋找能夠被分割和刪除的聚類對；二是如何加快對局部聚類的更新處理，從而進(jìn)一步提高聚類的速度和效果。

致謝感謝教育部《高等學(xué)校青年骨干教師國內(nèi)訪問學(xué)者項(xiàng)目》所提供的在天津大學(xué)訪學(xué)的機(jī)會，感謝天津大學(xué)智能與計(jì)算學(xué)部的廖士中教授對我研究工作的指導(dǎo)和幫助。