二次冪耦合的K-means聚類算法研究

相益萱，姜 合，潘品臣，孫聰慧

齊魯工業大學（山東省科學院）計算機科學與技術學院，濟南250353

所謂數據挖掘就是從大型的數據庫中提取有趣的、非凡的、蘊含的、先前未知的以及潛在有用的信息或者模式，隨著科技的發展，數據挖掘成為當下用戶從大量的數據中提取出來有效信息的手段，并且衍生出了很多分支，其中又以K-means[1]聚類算法作為經典的聚類分析算法。K-means聚類：即是一種無監督的問題，將相似的東西分到一組，不相似的盡量遠離。它具有快速、簡單的特點，同時它也受初始中心的選擇隨機性和離群點的干擾可能導致聚類不佳，但是即使存在上述問題，并不影響它被廣泛地應用在各個行業的領域。

針對K-means算法存在的問題，許多學者提出一些解決辦法，袁方等[2]為了消除傳統K-means算法對初始聚類中心敏感問題，提出一種優化初始聚類中心的方法，通過計算每個數據對象所在的區域密度，選擇相互距離最遠K個處于高密度區域的點作為初始聚類中心，以提高聚類的效果。另外張靖等[3]為了提高聚類穩定性并降低時間復雜度，提出了基于個體輪廓系數自適應地選取優秀樣本以確定初始聚類中心的改進K-means算法。鄒臣嵩等[4]解決了傳統K-means 算法聚類結果隨機性大、穩定性差，以及最大距離乘積法迭代次數多、運算耗時長等問題，提出一種基于最大距離積與最小距離之和的協同K聚類改進算法。行艷妮等[5]為了能夠及時了解Spark 環境下經典聚類算法K-means 的最新研究進展，把握K-means算法當前的研究熱點和方向，針對K-means 算法的初始中心點優化研究進行綜述。靳雁霞等[6]針對粒子群優化算法容易陷入局部最優且K-mean 算法受聚類數及初始聚類中心的選取影響較大，提出了一種改進的簡化均值粒子群K-means優化聚類算法（ISMPSO-AKM）。徐慧君等[7]由于傳統的協同過濾算法存在數據稀疏、可擴展性弱和用戶興趣度偏移等問題，算法運行效率和預測精度偏低。針對上述問題，提出一種改進的Mini BatchK-means 時間權重推薦算法，唐東凱等[8]針對K-means算法對初始聚類中心和離群點敏感的缺點，提出了一種優化初始聚類中心的改進K-means 算法。王義武等[9]為了加快K-means 計算速度和尋找最優聚類子空間提出空間投影在K-means算法中的研究與應用，同類型算法在準確度和計算時間方面都得到了大幅提升。王建仁等[10]針對手肘法在確定k值的過程中存在的“肘點”位置不明確問題，提出了一種改進的k值選擇算法能更加快速且準確地確定k值。洪敏等[11]針對K-means 聚類結果會受到初始類中心的問題。研究了不同的初始中心選擇方法對K-means型多視圖聚類算法的影響，并提出一種基于采樣的主動式初始中心選擇方法，在聚類精度和效率上取得了較好的折衷。

到目前為止，已公開發表了近千種K-means聚類方法，但是大部分都考慮的是數據之間沒有關系，彼此相互獨立，互相不影響，然而事實上數據之間存在著一些顯著性或者隱藏性的耦合關系，基于這個想法，2011 年操龍兵教授提出了非獨立同分布[12]的理論，考慮無論是大數據還是小數據，都要去權衡它們屬性的異構（Heterogeneity）和耦合關系（Coupling Relationships），關注它們數據的類型、屬性、數據源，考慮它們之間比較復雜的關系、層次、類型等，即非獨立同分布性。基于這個思想操龍兵[13]等人又提出非監督學習中的耦合名義相似性，另外在實際應用中，由離散變量和數值變量組成的異構依賴屬性隨處可見，于是基于這樣的背景，Wang 等[14]提出了混合數據的耦合相互依賴屬性分析。另外Li等通過引入用戶與物品之間的非獨立同分布耦合關系提出了一種新的通用耦合矩陣分解模型（CMF）[15]，在推薦系統應用方面進行了研究。Wang等[16]針對耦合聚類集成，在基本集群和對象之間包含耦合關系聚類系統中基簇與對象之間的依賴關系，并提出了一個耦合聚類系統的框架能夠有效地捕獲嵌入在基簇和對象中的交互，具有更高的聚類精度和穩定性，這也得到了統計分析的支持。

潘品臣等[17]利用非獨立同分布，并且結合了雙領域思想對Min_max方法進行選點優化，既將屬性與對象之間的潛在關系挖掘出來，又在選點上避免選到離群點，以提高聚類效果，但是也有局限性，在考慮耦合關系時僅僅考慮到1次冪，在選取第一個初始點的時候是隨機的，而且優化后的Min_max 選點可能出現緊湊的情況，所以會導致聚類效果提升相對有限，本文是在之前該課題研究基礎上做出的改進。在挖掘潛在關系的時候考慮到2次冪的情況（具體詳見2.1節），并且在對于K-means聚類算法的改進中，提出了一個新的求解密度參數的方法，在傳統的求密度參數過程中考慮的是全部點之間的距離求平均值作為平均半徑，這樣的計算方法比較粗略，本文通過每次考慮一個點與其他點之間的距離和以此求平均值（具體過程詳見2.2 節），最后發現在最優高密度區域通過聚類迭代方法選取初始中心點后有一定的效果（具體過程詳見3.1節），經過實驗分析，在非獨立同分布下二次冪耦合的聚類迭代方法在準確率、迭代次數、聚類效果上都有一定的提高，基于以上提出了二次冪耦合的K-means 聚類算法研究（Study onk-means clustering algorithm of quadratic power coupling，Q-CKmeans）。

1 K-means算法

K-means算法是由MacQueen提出的基于劃分的一種比較流行的算法之一，下面簡單介紹該算法的工作流程：

（1）首先從原始的數據中隨機初始化選擇M個初始聚類中心；計算每個其他的點到這M個點之間的距離，得到M個距離后，根據距離大小將剩余點分配給M個簇，計算每個簇內的質心，將質心作為新的初始聚類中心。

（2）將質心作為新的初始聚類中心后，再遍歷其他點到質心之間的距離進而求得新的質心，兩者進行比較。

（3）循環步驟（2）直到質心不再發生變化。

這里本文用平方誤差和作為判斷條件，如公式（1）：

其中，M表示已知需要聚類的個數，m表示每個簇內樣本總個數，Pij中i表示i個簇，j表示簇內第j個樣本，Ci代表的是第i個簇的質心。

2 Q-C-Kmeans算法

首先將數據集的對象設置為uk,k屬于(1,L),L代表樣本個數，屬性列設為ai,i屬于(1,n),n表示屬性的列數，然后本文利用修改后皮爾森相關系數，這是由于皮爾森只描述了變量之間具有連續屬性的線性關系，但是這樣是不全面的，因此希望將n個連續屬性以2維展開，然后通過研究每兩個更新屬性之間的相關性來揭示連續屬性之間的耦合關系，這種方法也滿足LI 等[18]思想，以便于能夠更好地表達出它的耦合關系。

2.1 生成屬性間具有平方交互關系的數據集

在這里利用Blood部分數據集為例，介紹非獨立同分布的平方交互關系，如下是UCI中Blood數據集的一個片段，6個對象，其中4個屬性分別表示R（最近一次捐款的月份），F（捐款次數-捐款總數），M（金錢-捐血總數），T（時間-第一次捐款后的月數），最后一列代表是否獻血的二元變量（1 表示獻血，0 表示不獻血）分為兩類，具體如表1。

表1 Blood數據片段

將屬性進行平方如表2所示，經過擴展后得到新的屬性表，捕獲連續屬性的內部耦合和屬性間外部耦合交互關系，將ai與aj之間的皮爾森相關系數計算出來，如公式（2）：

表2 二次冪后的Blood數據片段

本文將ai和aj代表不同的屬性列，L為數據集中所有個數，fi(u)是ai對應的所有屬性值，fi(u)是屬性aj對應的所有屬性值，μj是aj這一屬性列的對應均值，然后考慮p_value值檢驗屬性之間不相關的假設。修改后的皮爾森相關系數如公式（3）：

2.1.1 內部耦合屬性的計算方法

2.1.2 外耦合屬性的計算方法

2.1.3 對象的耦合表示

F代表屬性列的最高次冪，其中⊕代表Hadamard 積，?表示矩陣乘積。

λ具體值為：

其中，λ表示一個1×F的向量。如表3 所示是經過Zsorce 歸一化后的結果（保留了小數點后3 位數）具體的實驗結果不用四舍五入。

表3 二次冪耦合后的Blood數據片段

2.2 密度參數和聚類迭代選點思想

本文針對之前該課題存在的一些不足做出改進，其中構建密度參數的方法最初的來源是賴玉霞等[19]的密度思想，經過參數調整后得到最優的高密度區域，以及根據最大距離積[20]的選點盡可能分散的思想，提出一種聚類迭代的方法，在高密度區域選取密度最大點作為初始點，相比本團隊潘品臣的方法中隨機性選擇第一個點會更加穩定，本文將距離高密度區域中初始點最遠的點作為第二個點，將前兩個點進行聚類迭代產生兩個質心之后，選取距離兩個質心最遠的點作為第三個點，以此類推，由于聚類迭代的過程中會產生簇，本文考慮到如果一個簇已經存在了質心，則同一簇中其他點到質心的距離相對較小，那么選擇同一聚類中的其他點作為下一個初始聚類中心的機會就會很小，因此選擇距離最遠的點，目的使得選點盡可能分散，相比本團隊之前提出的優化后的Min_max 方法避免了可能出現選點緊湊的情況，以達到較好的聚類效果。另外本文采用的是歐幾里德距離來計算方法，以下是相關步驟。

定義1 歐式距離

首先本文假設一共有L個樣本x1,x2,…,xL,首先計算每個xi樣本，i∈(1,L),與其他樣本xj,j∈(1,L)之間的距離distance[xi,xi],其中j不等于i。

步驟1 首先設置一個新的集合D1，用來放置每一個點的密度大小，先取出第一個樣本xi（這里的xi一次取一個值），計算xi與其他點xj之間的距離，其中j∈(1,L)，用distance(i)表示如公式（8）：

在得到一個集合D1后，求出D1的平均值MEAN_D1,計算在xi周圍的點在以MEAN_D1 為半徑的內部點的個數作為參考值，具體方式見公式（9）：

得到第一個點的密度大小MIDU(X1)，重復步驟一直到得到全部的點的密度MIDU(Xi)，其中i取(1,L),將密度參數放入，然后求得MIDU(Xi)的均值，如公式（10）：

步驟2 創建一個E集合，用來放置滿足大于AvgMIDU一定倍數的xi的樣本，這些樣本組成高密度區域的點集合E，如公式（11）：

2.3 選取初始中心點

本文在初始中心點的選擇上提供了一種聚類迭代的方法，具體的方式如下所示。

Begin：數據樣本集L，聚類的個數K

Over：輸出K個聚類的中心點M

First：將密度最大的點設置為第一個初始聚類中心點M1

Second：首先進行遍歷，計算高密度區域中距離M1的每一個點xi，計算它們之間的距離，將離M1 最遠的點設置為第二個初始聚類中心點M2。如圖1所示。

圖1 選取兩個初始中心點

假設圖1是高密度區域，其中M1、M2 分別代表已經確定的兩個初始聚類中心點。

Third：以這兩個點作為中心，然后根據中心與其他點之間的距離，生成兩個簇，先求得兩個簇的聚類質心C1,C2 在高密度領域求距離到這兩個聚類中心點的最遠的點，設置為第三個初始聚類中心點，如公式（12）所示：

其中，m代表高密度區域內樣本點的個數。如圖2 所示，其中C1、C2 分別代表以M1 和M2 為中心，聚類后的質心，在高密度區域中選擇距離C1 和C2 最遠點作為第三個聚類中心點M3。直線表示兩點之間的距離。

圖2 選取三個初始中心點

如果需要分離到四個簇，則先求得前面三個選定聚類中心點的聚類中心，并且在高密度區域的選擇距離這三個點的最遠處的點作為第四個點，如公式（13）所示：

這個過程會一直進行下去，直到初始集群中心的數量等于預定義的集群數量M。最后，將K-means算法應用于M個初始中心點，使得初始中心點的選擇盡可能分散。

2.4 算法描述

綜上所述3個過程，接下來，給出算法的具體描述。

Begin：樣本數據集L，聚類個數M

Over：得到聚類的M個簇

First：對于樣本數據集L，依照2.1節中的計算過程，首先對樣本數據集的每一列進行平方，然后計算得到新數據集每一列的屬性相關系數（具體公式詳見2.1 節），使得能夠反映連續屬性的全局耦合關系。

Second：根據2.2節中提供求解新密度的方式，得到相應的密度值參數，以及各自的半徑平均值，通過調整兩個參數得到一個相對合理的高密度的領域。

Third：在高密度的區域，選取密度最大的點作為第一個樣本點，選取距離密度最大的點作為第二個點，剩下的點利用聚類迭代后的選點方法進行選點，直到選擇的中心點滿足M個點。

Fourth：將得到的點帶入改進的算法。

3 仿真實驗

實驗環境硬件：Intel?CoreTMi7-6700CPU@ 3.40GHz，8 GB 的內存；Python3.6，Pycharm2017。實驗采用的數據集：本文選用UCI 中的Parkinsons、Blood、Planning、Vertebal數據集，如表4所示。

表4 測試數據集的信息

本文主要是在文獻[17]基礎上進行的改進，同時本文選用3個比較經典方法，文獻[4]、文獻[19]以及文獻[20]作為參照，主要是三個對比：在非獨立同分布下和獨立同分布下進行分別比較，非獨立同分布下進行比較，以及在獨立同分布下進行比較，以此來說明算法的有效性。

3.1 驗證聚類準確率的提升

本文的參數選擇是通過調整在公式（9）中的α和公式（11）中的β，在實驗中本文算法的參數α和β的變化范圍都是0～1，參數每次增加0.05來尋找最佳的聚類結果。參數α β的設置上本文建議大致趨向于0.1，0.4，0.9的選擇，具體分析（見3.1.1節），表5～8中的N-precision代表在非獨立同分布下二次冪耦合的本文算法和經過非獨立同分布的一次冪的耦合后利用文獻[19]的Min_max 方法、文獻[20]中最大距離積方法、文獻[4]中的MSDCC 方法，以及文獻[17]中的優化后的MIN_max方法進行計算，本文分別在四個數據集上進行比較以此來說明Q-C-Kmeans 算法的有效性，另外precision 代表在獨立同分布下的本文聚類迭代方法和文獻[19]、文獻[20]、文獻[4]、文獻[17]中各個方法的準確率比較，上述算法的結果都是進行10次實驗后取平均值得到的。

表5 Blood數據集上的實驗結果

如表5所示在本文的Q-C-Kmeans算法中參數設置為α=0.4,β=0.9,本文利用在非獨立同分布下一次冪的方法將數據集處理完后，繼續用文獻[17]、文獻[4]、文獻[19]、文獻[20]方法進行比較，發現同樣在非獨立下二次冪的算法的準確率相比其他的文獻算法提升了3.1%左右。體現出非獨立同分布下的二次冪的優越性。另外很明顯非獨立同分布下相比獨立同分布下的各個數據集的準確率相應地提高3%、1.6%、1.6%、1.7%、1.5%，體現了非獨立同分布的優越性，另外在獨立同分布下，α=0.9,β=0.4 分別提高1.7%、1.7%、1.8%、1.6%。這說明本文的聚類迭代方法相對于文獻[17]中優化后的Min_max方法、文獻[19]中的MIN_max方法、文獻[4]中的MSDCC 方法、文獻[20]中的最大距離積的方法在Blood數據集上準確率的優勢，表明本文的方法是可行的。

如表6 所示參數設置為α=0.9,β=0.6 時本文的QC-Kmeans 算法準確率相比其他文獻分別提升了2.9%、2.6%、3.1%、2.6%左右，說明了二次冪相對于一次冪的優越性，同樣在非獨立同分布下準確率相比獨立同分布下的準確率也要高，相應提高了6.6%、5.8%、5.9%、6.3%，體現了非獨立同分布的優越性，在獨立同分布下的本文將參數設置為α=0.2,β=0.7,本文對于初始中心點的優化方法相比獨立同分布下的其他方法也分別提高2.1%、1.1%、2.8%、2.6%左右，這說明Q-C-Kmeans中的聚類迭代方法要優于文獻[17]、文獻[20]、文獻[19]以及文獻[4]中的方法，表明聚類迭代的思路是有效的。

表6 Parkinsons數據集上的實驗結果

如表7所示參數設置為α=0.1,β=0.8 時本文的QC-Kmeans在非獨立的二次冪的處理之后準確率相比文獻[17]、文獻[4]、文獻[19]、文獻[20]方法在非獨立同分布下的一次冪準確率分別提升18.3%、17.6%、18.1%，17.6%，提升非常明顯，更加說明了本文非獨立同分布下二次冪耦合的有效性，另外本文的聚類迭代算法獨立情況下參數設置α=0.8,β=0.1,本文算法的結果相比其他文獻的結果分別提升了1.2%、1.6%、1.1%、0%，說明本文聚類迭代的思想的有效性，非獨立同分布的相對于獨立同分布的結果提高了17.6%、0.5%、1.6%、0.6%、0%。體現了非獨立同分布的有效性。

表7 Planning數據集上的實驗結果

如表8所示參數設置為α=0.3,β=0.9,本文的Q-CKmeans在非獨立同分布下的二次冪耦合相比非獨立同分布的一次冪分別提升了12.5%、13.9%、13.3%、14.9%，在獨立同分布下中本文設置參數為α=0.95,β=0.15，但是發現獨立同分布所給的方法相比非獨立同分布高，說明了非獨立同分布并不是對于全部的數據集有效，但是本文提出的聚類迭代的方法相對于獨立同分布下的其他文獻也是有效的，分別提高10.9%、9.6%、12.9%、0.3%。

表8 Vertebal數據集上的實驗結果

圖3 中可以看出在非獨立同分布下二次冪耦合的聚類迭代算法相對于非獨立同分布下一次冪耦合的文獻[17]、文獻[20]、文獻[4]、文獻[19]中所用的方法，在Parkinsons、Blood、Planning、Vertebal 數據集上有很明顯的提升，這主要是得益于本文二次冪的耦合能夠更好地將數據之間的潛在關系更好地挖掘出來，從圖4 中看出，在獨立情況下比較，本文的聚類迭代算法相較于文獻[17]、文獻[20]、文獻[4]、文獻[19]中的方法在Blood、Parkinsons、Planning、Vertebal數據集上準確率也有相對比較明顯的提升，這得益于本文算法的有效性、合理性。

圖3 非獨立同分布下準確率的對比

圖4 獨立同分布下準確率的對比

3.1.1 參數的選擇

如圖5從整體上分析聚類迭代算法的參數選擇，橫坐標表示參數α、β所選的值，縱坐標表示出現的次數，如圖5分析數據集整體在0.1、0.4、0.9的次數比較多，但是本文所實驗的數據集只有4個，并未在大量數據集進行驗證，相對性根據實驗結果給出的參數選擇建議在0.1、0.4、0.9附近。

圖5 次數比較

3.1.2 復雜度的分析

本文用算法的時間復雜度來說明算法運算量，其中m為數值屬性的維度，n為樣本數目，k表示聚類數目，t表示K-means迭代次數。

本文算法在非獨立同分布下二次冪的內耦合時間復雜度為O(nm2)，外耦合的時間復雜度為O(mn)，對象耦合的時間復雜度為O(mn)，數據歸一化的時間復雜度為O(n)，在算法上求解密度參數的時間復雜度為O(mn)，構建高密度的區域的時間復雜度為O(n)，聚類迭代的時間復雜度O(n),K-means 算法O(knt)，所以本文的QC-Kmeans 算法整體上的時間復雜度為O(nm(m+3))+O(n(2+kt))。

在不考慮非獨立同分布的前提下本文算法的時間復雜度與文獻[20]、文獻[19]、文獻[17]基本上是同一級別的。

3.2 聚類分析對比

在實驗中對非獨立同分布下的文獻[4]、文獻[17]、文獻[20]中的方法在四個數據集進行驗證分析，實驗結果10 次取平均值，本文用聚類的平方誤差和判斷聚類效果，聚類的平方誤差和越小，就說明聚類的效果越好，由于Parkinsons、Vertebal與其他兩個數據集的范圍相差比較大，所以分成3 個圖比較，如圖6～圖8，另外迭代次數越小，表明收斂的速度快，具體比較如圖9所示。

圖6 Blood和Planning的聚類效果

圖7 Parkinsons的聚類效果

圖8 Vertebal的聚類效果

如圖6、圖7 所示，非獨立分布下二次冪耦合的文獻[4]、文獻[20]、文獻[17]中的方法在Blood、Planning、Parkinsons 數據集上，能夠有效地降低聚類的平方誤差和，這得益于非獨立同分布的二次冪耦合的有效性，另外整體趨勢從左往右依次減少，驗證本文聚類迭代方法的有效性，說明了相對于最大距離積[20]的方法、文獻[4]的方法，以及文獻[17]中優化后的Min_max 選點方法，在非獨立同分布下，本文算法聚類效果提高，另外迭代的次數如圖9所示，本文方法在Blood、Parkinsons、Planning數據集上迭代的次數是最小的，即收斂的速度最快，說明了本文的Q-C-Kmeans算法在收斂性上的有效性。

如圖8所示，本文的Q-C-Kmeans算法相比文獻[4]、文獻[20]、文獻[17]中的方法在Vertebal數據集聚類效果不佳，出現這種情況的原因，在數據集相同的前提下，主要考慮到數據本身存在離群點的影響，因為本文的方法在處理完數據集后只是對于選點進行的優化，使得初始選點不會選到離群點，但是離群點依然存在，選點的不同會引起質心的位置不同，而誤差和又是以簇中其他點與質心的整體差作為評價標準的，所以一旦簇中的離群點相對較多，質心與簇中其他點之間距離相對較大，可能會導致聚類的誤差和變大，綜合考慮是該數據集的本身離群點影響，雖然出現上述問題，如圖9所示，但是在迭代次數上本文算法最小，收斂速度也是最快的，所以本文方法在多分類的數據集上也是有一定效果的。

在運行時間上比較如圖10，由于本文的Q-C-Kmeans算法需要優先處理數據集，為了統一標準所以都是在非獨立同分布下二次冪進行的比較，本文也是10 次取平均值，整體上在非獨立同分布下，本文的Q-C-Kmeans算法的運行時間雖然略大于其他文獻中的方法，但是相對來說合理，另外本文的Q-C-Kmeans 算法的運行時間跟初始中心選點個數、數據集的大小有一定的關系，本文所選的數據集的類別個數比較少，導致聚類迭代的次數比較少，數量上不是很大，所以運行時間相對來說合理。

圖10 運行時間的比較

綜合分析Q-C-Kmeans算法在二分類的Blood、Parkinsons、Planning的數據集效果比較好，在準確率、聚類效果，以及收斂速度上都是最佳的，考慮到由于離群點的影響，導致本文方法相比之前的算法在Vertebal 的三分類數據集上的聚類效果不佳，但是在收斂性以及準確性上本文方法有一定的優越性。整體上分析本文的QC-Kmeans算法是可行性的。

4 結束語

本文主要是針對于文獻[17]的一種改進，針對文獻[17]算法的最初選取中心點的隨機性，以及在非噪聲領域利用Min_max的方法，可能出現其他選點緊湊的情況，容易陷入局部最優，聚類不穩定，最終影響聚類效果，經過研究之后提出了二次冪耦合的K-means聚類算法研究（Q-C-Kmeans），相對于文獻[17]，利用二次冪的思想可以將獨立同分布下數據中隱含的信息更好地挖掘出來，本文又提出一種新的求解密度參數的方法，在最優高密度區域避免離群點的影響，同時提供聚類迭代的思想使得選點較遠，克服文獻[17]可能出現選點緊湊的問題，另外初始選取密度最大的點，很好地解決了文獻[17]最初選取中心點的選點隨機性問題，使得聚類穩定，實驗表明，相比之前的研究有了新的進展，在二分類數據集的準確率上，聚類效果、收斂速度有很明顯的提高，另外發現了多分類的數據集上可能會因為數據集的離群點的影響，引起聚類的效果不佳，但是整體上來說本文的Q-C-Kmeans算法還是有效的、可行的，另外本課題將會在混合型數據進一步研究，希望今后可以應用到相應的領域。