喀什大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 岳珊 雍巧玲

考慮到K-means 聚類(lèi)算法在聚類(lèi)過(guò)程中同等地看待每個(gè)特征維度、簇心的初始選取是隨機(jī)的等問(wèn)題，采用優(yōu)化K-means 算法SVD-Kmeans。首先對(duì)高維樣本數(shù)據(jù)采用奇異值分解方法，在最大限度保證原始樣本數(shù)據(jù)特征的前提下進(jìn)行降維處理，每個(gè)樣本降維后得到一個(gè)二維指標(biāo)值，再使用初始簇心求解模型確定初始簇心的選取，最后通過(guò)K-means 算法進(jìn)行聚類(lèi)求解，形成最終模型。通過(guò)在同一數(shù)據(jù)集上實(shí)驗(yàn)發(fā)現(xiàn)，采用SVDKmeans 算法相較傳統(tǒng)K-means 聚類(lèi)算法準(zhǔn)確率提高34.24%左右。

K-means 聚類(lèi)算法是由J.B.MacQueen 提出，該算法是一種迭代求解的聚類(lèi)分析算法，該算法具有原理簡(jiǎn)單、容易實(shí)現(xiàn)、可理解性較強(qiáng)等優(yōu)勢(shì)，但也存在容易出現(xiàn)局部最優(yōu)、聚類(lèi)效果依賴(lài)于聚類(lèi)中心的初始化等問(wèn)題。

基于此，學(xué)者們從兩方面進(jìn)行改進(jìn)優(yōu)化，一方面使用該算法與其他算法混合使用[1-3]；另一方面從優(yōu)化算法本身上下功夫，如目前使用較多的K-means++算法[4-8]、二分K-means 算法[9-13]等。然而，這幾種優(yōu)化方案雖然解決了簇心數(shù)量確定、減少算法時(shí)間、防止局部最優(yōu)等問(wèn)題，但仍然不可避免地存在實(shí)驗(yàn)之初隨機(jī)選擇一個(gè)樣本點(diǎn)作為第一個(gè)初始化的聚類(lèi)中心的問(wèn)題。

基于以上考慮，本文首先對(duì)高維數(shù)據(jù)進(jìn)行降維處理，解決算法同等看待每個(gè)特征維度的缺陷，再使用簇心求解模型首先確定兩個(gè)簇心的初始位置，最后使用K-means算法對(duì)樣本進(jìn)行聚類(lèi)操作，通過(guò)以上操作，有效地避免了實(shí)驗(yàn)之初簇心隨機(jī)選取和K 值不確定的問(wèn)題。

1 K-means 算法研究

K-means 算法能夠在不知道任何樣本標(biāo)簽的情況下，通過(guò)數(shù)據(jù)之間的內(nèi)在關(guān)系將樣本分為若干個(gè)類(lèi)別，使得相同類(lèi)別樣本之間的相似度高，不同類(lèi)別之間的樣本相似度低。

通過(guò)迭代的方式尋找k 個(gè)簇的劃分方案，使得聚類(lèi)結(jié)果對(duì)應(yīng)的代價(jià)函數(shù)最小，如式（1）所示：

其中，xi代表第i個(gè)樣本，ci是xi所屬的簇，μci代表簇對(duì)應(yīng)的中心(即均值)，N是樣本總數(shù)。

2 原始數(shù)據(jù)處理

選用機(jī)器學(xué)習(xí)MLP 填充方法對(duì)數(shù)據(jù)集中的缺失值進(jìn)行填充，應(yīng)用擬合與分類(lèi)思想，將不含缺失值的行作為訓(xùn)練樣本的輸入和標(biāo)簽，缺失值的行(不含缺失值的部分)作為測(cè)試樣本的輸出，缺失值即是測(cè)試樣本的待預(yù)測(cè)標(biāo)簽，填充結(jié)果如圖1 所示。

圖1 缺失信息填充Fig.1 Missing information filling

此次試驗(yàn)共填充177 名乘客的年齡信息，其中縱坐標(biāo)代表乘客的年齡，通過(guò)結(jié)果分析發(fā)現(xiàn)大部分年齡集中在20 ～30 歲之間。

3 SVD-Kmeans 算法

3.1 降維處理

輸入：N 個(gè)樣本。

輸出：一個(gè)N×R 矩陣。

（1）對(duì)高維矩陣進(jìn)行奇異值分解得到矩陣V，如式（2）所示：

（2）以矩陣V 的前D列作為降維矩陣，用高維矩陣和V '做矩陣乘法，實(shí)現(xiàn)降維，如式（3）所示：

3.2 簇心求解模型

3.2.1 模型假設(shè)

（1）簇心作用強(qiáng)度向其四周等強(qiáng)度擴(kuò)散；

（2）簇心作用強(qiáng)度服從擴(kuò)散定律，即單位時(shí)間影響單位法向量的面積與它的強(qiáng)度梯度成正比。

3.2.2 模型建立

將簇心起作用的時(shí)刻記為t=0，簇心點(diǎn)首先選為坐標(biāo)原點(diǎn)。時(shí)刻t無(wú)窮空間中任一點(diǎn)(x,y)的強(qiáng)度記為C(x,y,t)。根據(jù)假設(shè)2，單位時(shí)間通過(guò)單位法向面積的強(qiáng)度擴(kuò)散面積，如式（4）所示：

k為擴(kuò)散系數(shù)，grad表示梯度，負(fù)號(hào)表示由濃度高向濃度低的地方擴(kuò)散?？疾榭臻g域Ω，Ω 的體積為V，包圍Ω 的曲面為S，S的外法線向量為n，則在[t,t+Δt]內(nèi)通過(guò)Ω 的強(qiáng)度如式（5）所示：

而Ω 內(nèi)強(qiáng)度的增量如式（6）所示：

質(zhì)量守恒定律如式（7）所示：

將數(shù)據(jù)集中所有數(shù)據(jù)作為簇心，求解每個(gè)點(diǎn)的擴(kuò)散強(qiáng)度和擴(kuò)散增量，最大的兩個(gè)即為本次實(shí)驗(yàn)的初始簇心。

3.3 聚類(lèi)算法

輸入：N 組樣本數(shù)據(jù)。

輸出：待分類(lèi)樣本所對(duì)應(yīng)的分類(lèi)結(jié)果。

（1）使用簇心求解模型求解出的兩個(gè)初始簇心，記為μ1，μ2。

（2）計(jì)算每個(gè)樣本xi到各個(gè)簇心的距離，將其分配到與它距離最近的簇。

（3）對(duì)于每個(gè)簇，利用該簇中的樣本重新計(jì)算該簇的中心(即均值向量)。

（4）重復(fù)迭代上面2 ～3 步驟T 次，若聚類(lèi)結(jié)果保持不變，則結(jié)束。

4 實(shí)驗(yàn)介紹

通過(guò)奇異值分解方法盡可能多的保留原始樣本的數(shù)據(jù)特征得到降維后的矩陣，在本實(shí)驗(yàn)中，N=94，M=49，D=2。本次實(shí)驗(yàn)各奇異值的貢獻(xiàn)率如下所示:

第1 個(gè)奇異值的累積貢獻(xiàn)率是：0.20299414497066245

第2 個(gè)奇異值的累積貢獻(xiàn)率是：0.4010049338627624

第3 個(gè)奇異值的累積貢獻(xiàn)率是：0.5514842977877248

第4 個(gè)奇異值的累積貢獻(xiàn)率是：0.6884462710597125

第5 個(gè)奇異值的累積貢獻(xiàn)率是：0.8034632384325324

第6 個(gè)奇異值的累積貢獻(xiàn)率是：0.9120410189148603

第7 個(gè)奇異值的累積貢獻(xiàn)率是：1.0

奇異矩陣為：

降維后的數(shù)據(jù)結(jié)構(gòu)如圖2 所示。

圖2 降維結(jié)果Fig.2 Dimension reduction results

根據(jù)數(shù)據(jù)集特征可知最終確定出2 個(gè)簇心，根據(jù)簇心公式確定簇心后，使用K-means 方法進(jìn)行聚類(lèi)，如圖3 所示。

圖3 優(yōu)化K-means 算法聚類(lèi)結(jié)果Fig.3 Optimize K-means algorithm clustering results

在同一數(shù)據(jù)集上分別進(jìn)行K-means 算法和SVDKmeans 算法聚類(lèi)研究，計(jì)算兩種算法聚類(lèi)準(zhǔn)確率如圖4所示。

圖4 兩種算法準(zhǔn)確率對(duì)比Fig.4 Comparison of accuracy between two algorithms

經(jīng)過(guò)對(duì)比實(shí)驗(yàn)發(fā)現(xiàn)，傳統(tǒng)K-means 算法的準(zhǔn)確率為0.3557800224466891，SVD-Kmeans 算法的準(zhǔn)確率為0.6980920314253648。

5 結(jié)論

通過(guò)在數(shù)據(jù)集進(jìn)行K-means 聚類(lèi)算法優(yōu)化研究，發(fā)現(xiàn)當(dāng)直接使用K-means 算法進(jìn)行聚類(lèi)時(shí)，準(zhǔn)確率只有35.57%，考慮到K-means 算法自身存在的問(wèn)題，提出優(yōu)化K-means 算法模型SVD-Kmeans。首先使用奇異值分解方法對(duì)數(shù)據(jù)對(duì)象進(jìn)行降維處理，再使用簇心求解模型確定出兩個(gè)初始簇心，然后使用傳統(tǒng)K-means 算法進(jìn)行聚類(lèi)研究，通過(guò)在同一數(shù)據(jù)集上再次使用，發(fā)現(xiàn)本模型的準(zhǔn)確率得到大幅度提升。