一種非獨立同分布下K-means算法的初始中心優(yōu)化方法

潘品臣，姜 合，呂奕錕

(齊魯工業(yè)大學(山東省科學院) 計算機科學與技術學院 ，濟南 250353)

1 引 言

聚類算法是數(shù)據(jù)挖掘中重要的研究內(nèi)容之一，它是一個將物理或抽象對象的集合分組為由類似的對象組成的多個類的分析過程.基本的聚類方法包括：基于劃分的方法、基于層次的方法、基于密度的方法、基于網(wǎng)絡的方法以及基于模型的方法等等[1].K-means算法最早由MacQueen提出的[2]，是典型的基于劃分的聚類算法之一，它具有簡單、快速的優(yōu)點.但是，傳統(tǒng)K-means算法也存在著一些缺陷，其中最主要的便是對于初始中心點的選取比較敏感，不當?shù)倪x擇容易陷入局部最優(yōu)且聚類結果準確率低.針對這一缺陷，很多研究者提出了改進的方法，例如：Likas等人提出了一種全局K-means算法[3]，它是一種增量式的聚類算法，通過一個確定的全局搜索過程，每次動態(tài)地添加一個聚類中心，從合適的初始位置執(zhí)行K-means算法.袁方等人為了消除K-means算法對初始聚類中心點選擇上的敏感性，提出了一種優(yōu)化聚類中心的方法[4]，此方法計算每個數(shù)據(jù)對象所在區(qū)域的密度，選擇相互距離最遠的k個處于高密度區(qū)域的點作為初始聚類中心.翟東海等人針對聚類時容易出現(xiàn)局部最優(yōu)、聚類結果不穩(wěn)定、總迭代次數(shù)較多等問題，提出了最大距離法[5]來選取初始簇中心.邢長征等人針對現(xiàn)有的基于密度優(yōu)化初始聚類中心的方法在聚類中心的搜索范圍大、消耗時間久以及聚類結果對孤立點敏感等問題，提出了一種基于平均密度優(yōu)化初始聚類中心的adk-means算法[6].鄒臣嵩等人提出了一種基于最大距離積與最小距離之和的協(xié)同K聚類算法[7]，該方法解決了傳統(tǒng)K-means算法聚類結果隨機性大、穩(wěn)定性差，以及最大距離乘積法迭代次數(shù)多、運算時間長等問題.唐東凱等人針對K-means算法對初始聚類中心和離群點敏感的缺點，提出了一種優(yōu)化初始聚類中心的改進K-means算法[8]，該方法首先計算數(shù)據(jù)集中每個對象的離群因子并進行升序排序，使得中心點的位置靠前，然后引入取樣因子，從而得到候選初始中心點集，最后利用Max_min方法的思想在候選初始中心點集上選取k個聚類初始中心.

目前對于初始中心點的改進都是建立在獨立同分布基礎上進行的，然而數(shù)據(jù)中的屬性之間或多或少會存在相互作用和關系，是非獨立同分布的.非獨立同分布思想最早是由Cao在2011年提出的[9].隨后又有不少研究者將此思想應用于不同方面，例如：Wang等人在無監(jiān)督學習中提出了耦合名義上的相似性度量來代替?zhèn)鹘y(tǒng)的歐式距離度量[10]，但這僅限于類別型數(shù)據(jù)集.Liu等人分別對不平衡數(shù)據(jù)下的混合耦合KNN算法、不平衡分類數(shù)據(jù)的模糊耦合KNN算法以及用于多標簽分類的耦合KNN算法進行了研究[11-13].Li等人提出了一種新的通用耦合矩陣分解模型(CMF)[14]，通過引入用戶與物品之間的非獨立同分布耦合關系在推薦系統(tǒng)應用方面進行了研究.Jian等人為無監(jiān)督學習定義了一個耦合度量相似度(CMS)[15]，它靈活地捕獲了從值到屬性到對象的異構耦合關系，能夠靈活地適應獨立同分布和非獨立同分布下的數(shù)據(jù)，但其主要研究對象還是類別型數(shù)據(jù)集.

在上述文獻中有的解決了K-means算法隨機選取初始中心點的問題，但卻忽略了噪聲點對結果的影響；有的避免了噪聲點的影響，但忽略了屬性之間存在的交互關系.本文在非獨立同分布下提出了一種基于雙領域思想和Min_max方法相結合的優(yōu)化K-means初始中心選擇的方法，(即K-means algorithm based on Dual Domain idea and Min_max method within Non- Independent and Identically Distribution context，簡稱NonIID-DDMMK-means算法).數(shù)值數(shù)據(jù)可以基本表示為一個信息表的格式[16]，其中每一列表示為指定的“屬性”，每一行表示為指定的“對象”.鑒于此，本文首先考慮屬性之間的相互作用關系，利用Pearson相關系數(shù)公式計算每一列本身和其他列之間的相關系數(shù)[17]，即不同屬性之間的交互關系.然后將屬性之間的交互關系映射于原始數(shù)據(jù)每一行的對象之間，形成一個能夠體現(xiàn)屬性交互關系的新的數(shù)據(jù)集.最后利用雙領域思想對Min_max方法進行優(yōu)化，即在高密度領域選取第一個初始中心點，在非噪聲點領域利用Min_max方法的思想選取其它初始中心點來解決初始中心點敏感的缺陷，并且能夠減少迭代次數(shù)，提高聚類效果.

2 K-means算法

K-means算法是聚類分析中最常用的基于劃分的算法之一，已經(jīng)在許多行業(yè)領域得到很好的應用，該算法的執(zhí)行流程是：

1)隨機地在將要聚類的數(shù)據(jù)集中選擇k個數(shù)據(jù)對象作為初始聚類中心，這里的k代表類簇數(shù)目.

2)遍歷數(shù)據(jù)集中剩余的每個對象，根據(jù)相似度來決定每一個數(shù)據(jù)對象應該被分配到哪一個簇中，將每個對象分配到與其相似度最大的簇中.這里的相似性度量通常使用歐式距離來表示，兩個對象之間的距離越小說明它們之間的相似度越大.

3)重新計算每一個簇的中心點，將每一個簇的均值作為新的中心點.

4)重復執(zhí)行步驟2、步驟3，直到準則函數(shù)收斂，準則函數(shù)見公式(1).

(1)

這里的準則函數(shù)通常使用聚類誤差平方和，其中，k為簇的個數(shù)，m為簇中對象的總個數(shù)，Oij是第i簇的第j個數(shù)據(jù)對象，Ci是第i簇的均值中心.

3 NonIID-DDMMK-means算法

NonIID-DDMMK-means算法對于初始聚類中心點的選取主要分為三個過程：

1)利用修改后的Pearson相關系數(shù)公式計算每一列屬性之間的相關系數(shù)，即屬性之間的交互關系.并將屬性之間的交互關系映射于原始數(shù)據(jù)集的對象之間從而形成一個能夠體現(xiàn)屬性間交互關系的新的數(shù)據(jù)集；

2)利用密度參數(shù)的思想，計算出數(shù)據(jù)集中的高密度領域和非噪聲點領域.其中，高密度領域用來對Min_max方法在第一個點的選擇上進行確認，非噪聲點領域用來對Min_max方法在其他點的選擇上進行約束；

3)根據(jù)Min_max方法在雙領域中選取初始聚類中心點.下面分別對這三個過程進行介紹.

3.1 形成屬性間具有交互關系的數(shù)據(jù)集

之前的大部分研究都是在獨立同分布基礎上進行的.然而在現(xiàn)實的數(shù)據(jù)中，屬性之間或多或少都會存在一些相互作用，傳統(tǒng)的K-means算法忽略了這些交互關系.下面對屬性間的交互關系進行形式化表示，并舉例說明.

前面提到數(shù)值數(shù)據(jù)可以基本表示為一個信息表的格式，本文選取Iris數(shù)據(jù)集中的一個片段為例，6個對象具有4個屬性(即萼片長度a1，萼片寬度a2，花瓣長度a3，花瓣寬度a4)，分為三類，具體信息如表1所示.

表1 鳶尾花數(shù)據(jù)片段TTable 1 Data fragment T of Iris

第1步.構建新的Pearson相關系數(shù)公式

研究變量之間的交互作用的一種傳統(tǒng)方法是通過Pearson相關系數(shù)測試變量之間的線性關系[17，18].因此，本文利用Pearson相關系數(shù)公式來計算屬性之間的交互關系，計算公式見公式(2).

(2)

其中，am和an為不同的屬性列，U為數(shù)據(jù)集中的對象個數(shù)，fm(u)為屬性am對應的所有屬性值，μm為屬性am下所有屬性值的均值.

但是，這里主要考慮屬性之間的重要的交互關系而不是涉及所有的這些關系.因此基于p值越小相關性越顯著的原則，對原本公式進行了修正，這里選用統(tǒng)計學中常用的0.05作為p值得劃分點，修正后的公式見公式(3).

(3)

第2步.計算屬性間的交互關系

由第1步得到屬性間修正后的公式(3)，進而計算出不同屬性之間的相關系數(shù)為：

α(a1|a2，a3，a4)=(0.000 0.000 0.814)

α(a2|a1，a3，a4)=(0.000 0.000 0.000)

α(a3|a1，a2，a4)=(0.000 0.000 0.976)

α(a4|a1，a2，a3)=(0.814 0.000 0.976)

可以看出就數(shù)據(jù)片段T而言，屬性a2和其他屬性之間的相關系數(shù)為0，即無顯著相關，屬性a1和屬性a3之間也無顯著相關.

第3步.將交互關系映射到原始數(shù)據(jù)集

由第2步得到不同屬性之間的相關系數(shù)后，利用公式將屬性之間的相關系數(shù)映射到對象之間，即映射到原始數(shù)據(jù)集上，具體公式見公式(4).

(4)

其中，fm(u)為屬性am對應的所有屬性值，ω為數(shù)據(jù)集中特征屬性的個數(shù)，α(m|ni)表示屬性am和屬性ani之間的相關系數(shù)，即New_Cor(am，ani).

表2 新鳶尾花數(shù)據(jù)片段TcTable 2 New data fragment Tc of Iris

將第2步計算出來的屬性間的相關系數(shù)，利用公式(4)映射到原始數(shù)據(jù)集的對象之間，形成一個能夠體現(xiàn)屬性交互關系的新數(shù)據(jù)集Tc，具體結果如表2所示.

3.2 生成高密度領域和非噪聲領域

傳統(tǒng)K-means算法隨機地選擇初始聚類中心，對于中心點的選取比較敏感，容易陷入局部最優(yōu)且準確率低.Min_max方法降低了對初始聚類中心的敏感性，提高了聚類結果的準確率.但是，Min_max方法在第一個初始聚類中心點選擇上依然是隨機的，可能因選到離群點而影響準確率和迭代次數(shù).針對這個問題，賴玉霞等人通過設定高密度區(qū)域[19]，然后在區(qū)域內(nèi)利用Min_max方法來選取初始中心點，這樣能夠很好解決第一個點選到離群點的問題.但是這樣得到的點過于稠密，容易造成聚類沖突，從而降低了聚類結果的質(zhì)量.熊忠陽等人針對這一問題，提出了一種最大距離積法[20]，能夠在高密度領域內(nèi)選點更加合理分散，但始終基于高密度領域，所以對于聚類效果的提升還是相對有限.本文僅僅在高密度領域內(nèi)選取第一個點，并且為了避免后面的選點也會因Min_max方法的思想而選到噪聲點，所以又設立了一個非噪聲領域，有效避免了噪聲點的選擇，具體步驟如下：

第1步.密度計算

數(shù)據(jù)集中對象的密度即以每個對象為圓心，以數(shù)據(jù)集中任意兩點間距離的平均值為半徑的圓內(nèi)包含其它對象的個數(shù).包含的個數(shù)越多，說明該對象的密度越大.

這里的半徑為對象間距離總和除以從數(shù)據(jù)集中任意取兩個對象的所有排序次序，具體公式見公式(5).

(5)

其中，N為數(shù)據(jù)集的總個數(shù)，d(Oi，Oj)為對象Oi和對象Oj的歐式距離.

而對象Oi的密度為：以Oi為圓心，以avgDist為半徑的圓內(nèi)(含圓上)所包含的對象的個數(shù)，即滿足條件d(Oi，Oj)≤α×avgDist時，則說明對象Oj在以Oi為圓心的圓內(nèi)，具體密度公式見公式(6).

(6)

第2步.生成高密度領域

高密度領域即高于平均密度一定倍數(shù)的數(shù)據(jù)對象組成的集合.在第1步中可以根據(jù)公式(5)和公式(6)計算出不同對象的密度，平均密度avgDens即以所有對象為圓心的圓內(nèi)(含圓上)包含的對象的個數(shù)除以數(shù)據(jù)集中對象的總個數(shù)，具體公式見公式(7).

(7)

根據(jù)公式(7)計算出的數(shù)據(jù)集中對象的平均密度，可以定義高于平均密度η倍的數(shù)據(jù)對象組成的集合為高密度領域，這里的η為高密度領域的調(diào)節(jié)系數(shù)，一般η≥1.

第3步.生成非噪聲領域

非噪聲領域即數(shù)據(jù)集中排除噪聲點(離群點)的領域，這里根據(jù)第2步中公式(7)計算出的平均密度，定義低于平均密度ε倍的數(shù)據(jù)對象組成的集合為噪聲點，這里的ε為噪聲點調(diào)節(jié)系數(shù)，一般0<ε<1.

3.3 選取初始中心點

NonIID-DDMMK-means算法在初始中心點的選擇上主要是基于Min_max方法的思想，該方法的大體過程如下所示.

Input：數(shù)據(jù)集O，聚類個數(shù)K

Output：K個初始聚類中心點C

Step1.從數(shù)據(jù)集中隨機找一個點O1作為第一個初始中心點C1，即C1=O1；

Step2.遍歷數(shù)據(jù)集中的其他對象，分別計算各個樣本點與第一個初始中心點C1的距離，找到一個距離C1最遠的點O2作為第二個初始中心點C2；

Step3.遍歷剩余的所有對象，分別計算它們與C1和C2的距離，記為di1和di2.令其中較小值為min(di1，di2)，并將較小值都存入集合D中.接著，計算集合D中所有距離的最大值為max(min(di1，di2))，記為O3；

Step4.重復上面的操作，直到找到K個初始中心點.

可以發(fā)現(xiàn)Min_max方法在第一個點的選擇上依然是隨機的.針對這一問題，本文在高密度領域中對第一個初始聚類中心進行確認，這里并不是選取高密度領域內(nèi)密度最大的點作為第一個初始聚類中心點，而是選擇高密度領域內(nèi)距離樣本集中心最遠的點作為第一個初始聚類中心點，這樣的選點更加符合聚類分布的特點.樣本集的中心即樣本中所有對象的均值，具體見公式(8).

(8)

在第一個初始聚類中心確認之后，使用Min_max方法對剩余的點進行選取，這里本文設立了一個非噪聲領域，不僅可以防止選到的點為噪聲點而影響聚類結果的情況，也可以防止所有的點都在高密度領域內(nèi)選取，而導致的選點過于稠密，容易造成聚類沖突，從而降低了聚類結果的質(zhì)量等問題的發(fā)生.

3.4 NonIID-DDMMK-means算法描述

綜合上述3個過程，下面給出NonIID-DDMMK-means算法的整體描述：

Input：數(shù)據(jù)集O，聚類個數(shù)K

Output：完成聚類的K個簇

Step1.對數(shù)據(jù)集O，根據(jù)3.1小節(jié)中的計算過程來計算每一列屬性之間的相關系數(shù)，并映射到數(shù)據(jù)集的對象之間，形成新的能夠體現(xiàn)屬性間交互關系的數(shù)據(jù)集.

Step2.將得到的數(shù)據(jù)集按照3.2小節(jié)中的步驟來計算出它的平均密度，并調(diào)節(jié)η和ε的值來生成合適的高密度領域和非噪聲領域.

Step3.按照3.3小節(jié)中的思想，在高密度領域中選取一個距離樣本集中心最遠的點作為第一個初始中心點，然后在非噪聲領域使用Min_max方法選擇其它初始中心點，從而得到K個初始聚類中心.

Step4.從Step 3中得到的初始中心點出發(fā)，執(zhí)行K-means算法，得到聚類結果.

4 實驗結果與分析

實驗環(huán)境：硬件：Intel(R)Core(TM)i7-6700 CPU@3.40GHz，8GB的內(nèi)存；軟件：VirtualBox虛擬機(Linux系統(tǒng))，集成開發(fā)軟件Python3.6，Pycharm2017.實驗采用的數(shù)據(jù)集：本文選用UCI中的Iris、Parkinsons、Blood數(shù)據(jù)集.

表3 測試數(shù)據(jù)集信息Table 3 Details of test data

在獨立同分布下采用傳統(tǒng)K-means算法(OR-K)，原始Min_max方法(OR-MMK)以及文獻[5-7]中的算法對三個數(shù)據(jù)集進行聚類測試.在非獨立同分布下采用傳統(tǒng)K-means算法(CR-K)，原始Min_max方法(CR-MMK)，文獻[5,19,20]中的方法以及本文算法(CR-DDMMK)對三個數(shù)據(jù)集進行聚類測試.為提高數(shù)據(jù)可比性，在進行聚類測試之前，我們對原始數(shù)據(jù)集T和具有交互關系的數(shù)據(jù)集Tc的每一列進行歸一化，這里采用Z-Score標準化.其中Iris、Parkinsons、Blood數(shù)據(jù)集的信息特征如表3所示.

4.1 驗證聚類準確率的提升

實驗中對獨立同分布下的OR-K算法、OR-MMK算法以及文獻[5-7]中的算法和非獨立同分布下的CR-K算法、CR-MMK算法以及本文的CR-DDMMK算法在三個數(shù)據(jù)集上進行驗證比較，這里本文取20次實驗的平均值，具體結果如圖1所示.

圖1 聚類準確率對比Fig.1 Contrast of clustering accuracy

從圖1中可以看出非獨立同分布下的聚類準確率整體要高于獨立同分布下的結果.其中，Iris數(shù)據(jù)集在非獨立同分布下的CR-K算法低于獨立同分布下的OR-MMK算法以及文獻[5-7]中的算法主要是因為其受初始中心點影響較大，不當?shù)某跏贾行狞c可能會導致聚類結果準確率較差.為了進一步的驗證，本文對Iris數(shù)據(jù)集下的OR-K算法和CR-K算法進行詳細對比，具體如表4所示.

表4 兩種算法在Iris數(shù)據(jù)集上的結果Table 4 Results of the two algorithms on the Iris data set

從表4中可以看出Iris數(shù)據(jù)確實受初始中心點的影響較大，不僅如此，還可以看出在獨立同分布下的OR-K算法的準確率上限為84.67%，而非獨立用分布下的CR-K算法的準確率上限為93.33%，這也證實了非獨立同分布思想的有效性.并且本文的在非獨立同分布下對Min_max方法進行優(yōu)化的NonIID-DDMMK-means算法在準確率上較CR-MMK算法也有一定的提升.

對于Parkinsons和Blood數(shù)據(jù)集，從圖1中可以看出其受初始聚類中心的影響相對較小，獨立同分布下的OR-MMK算法和文獻[5-7]中的算法對于聚類準確率的提升效果不明顯，而非獨立同分布下的CR-K算法和CR-MMK算法以及本文算法都較OR-K算法有一個大幅的提升，這主要得益于非獨立同分布思想的有效性.并且可以發(fā)現(xiàn)本文算法較CR-MMK算法在這兩個數(shù)據(jù)集中同樣有進一步的提升，這也證實了本文算法的有效性.

4.2 驗證聚類效果的提升

實驗中對非獨立同分布下的CR-K算法、文獻[19,20]中的方法以及本文算法在非獨立同分布下的三個數(shù)據(jù)集上進行驗證比較，取20次實驗的平均值，聚類平方誤差和越小說明聚類效果越佳.由于Iris數(shù)據(jù)集與其它兩個數(shù)據(jù)集的數(shù)值范圍相差較大，所以將其分開展示，具體如圖2-圖3所示.

圖2 Iris聚類效果對比Fig.2 Contrast of clustering effect on Iris圖3 Parkinsons和Blood聚類效果對比Fig.3 Contrast of clustering effect on Parkinsons and Blood

從圖2中可以看出，在非獨立同分布下的Iris數(shù)據(jù)集中用文獻[19,20]中的方法能夠有效降低聚類平方誤差和，提升聚類效果.同時，驗證了文獻[20]中的方法較文獻[19]的確有所提升，但是選點還是有些稠密，因此可以發(fā)現(xiàn)本文的算法在使用雙領域思想后能夠較文獻[20]有更進一步的提升.

從圖3中可以看出，在非獨立同分布下的Parkinsons和Blood數(shù)據(jù)集中用文獻[19，20]中的方法同樣能夠降低聚類平方誤差和.其中，文獻[19]方法和文獻[20]方法得出來的值是一樣的，這主要是因為這兩個數(shù)據(jù)集的初始聚類中心點的個數(shù)為2，兩個文獻中的方法在取前兩個初始點時的思想是相同的.在這兩個數(shù)據(jù)集中，本文的算法較前兩者仍然有進一步的提升，這也驗證了雙領域思想對于聚類效果提升方面的有效性.

4.3 驗證運算效率的提升

實驗中對非獨立同分布下的CR-K算法、CR-MMK算法、文獻[5]和文獻[19]中的方法以及本文算法在非獨立同分布下的三個數(shù)據(jù)集上進行驗證比較，取20次實驗的平均值，迭代次數(shù)越少說明運算效率越高，具體結果如圖4所示.

圖4 迭代次數(shù)對比Fig.4 Contrast of iteration number

從圖4中可以發(fā)現(xiàn)，在Iris數(shù)據(jù)集中迭代次數(shù)整體呈一個下降趨勢，但是在Parkinsons和Blood數(shù)據(jù)集中，CR-MMK算法、文獻[5]和文獻[19]中的方法較最初的CR-K算法有一些波動，這主要是因為Min_max方法以及最大距離的方法在取第二個點時很容易取到噪聲點，并且過于稠密的初始中心點也會影響運算效率.而本文的方法設立了雙領域，并在第一個初始中心點的選擇上更加符合聚類分布的特點，所以迭代次數(shù)要更少，運算效率更高.

5 結 論

針對傳統(tǒng)K-means算法在進行數(shù)據(jù)聚類時，往往忽略了數(shù)據(jù)集中屬性之間的交互關系以及其對初始中心點的選取比較敏感，不當?shù)倪x入容易導致局部最優(yōu)、聚類不穩(wěn)點、收斂速度慢等問題，本文提出了一種非獨立同分布下基于雙領域思想和Min_max方法相結合的優(yōu)化K-means初始中心選擇的方法.該方法首先通過修改后的Pearson相關系數(shù)公式來計算不同屬性之間的交互關系并映射到原始數(shù)據(jù)集的對象之間，從而形成能夠體現(xiàn)交互關系的新數(shù)據(jù)集.然后通過設立雙領域來避免選到噪聲點以及選點過于稠密等問題.最后利用優(yōu)化后的Min_max方法找到全部初始中心點并完成聚類.實驗表明，本文提出的NonIID-DDMMK-means算法具有較高的準確率、較好的聚類效果以及相對較少的迭代次數(shù).因此，本文提出的非獨立同分布下的聚類算法是有效的，可行的.