基于最大期望的初始聚類中心選擇算法

廉文娟，史丹丹，安其立，賈 斌

（山東科技大學計算機科學與工程學院，山東 青島 266590）

0 引言

聚類是機器學習中重要的組成部分，是一種研究分類問題的統計分析方法，廣泛應用于文本[1]，圖像[2]，音頻等領域。K-means算法為聚類算法中的硬聚類算法，是典型的基于原型的目標函數聚類方法的代表。它的基本思想是，通過迭代方式尋找 K個簇的一種劃分方案，使得聚類結果對應的代價函數最小。算法中采用歐式距離作為相似度測量，代價函數為各個樣本距離所屬簇中心點的誤差平方和（Sum of Squared Error, SSE）。但是K-Means方法有幾個缺點，包括確定初始的聚類中心初始值是隨機的，以及距離模型用于確定數據之間的相似性，而傳統距離模型對每個數據屬性的影響相同。K-means++在此基礎上，利用初始樣本點到整體樣本的距離，基于概率化的選擇計算出下一個初始聚類中心，對于同樣問題的解決方法國內外有利用密度[3]、區域密度[4]以及排序劃分[7]的優化計算方法；文獻[7]-[11]分別采用不同的方法計算初始樣本中心，其中文獻[7]和文獻[11]分別采用了加權局部方差和自確定簇數和聚類中心的方法；文獻[9]采用余弦距離作為度量標準確定最優簇中心，針對計算過程中迭代次數，計算耗時以及整體聚類效果；文獻[12]研究了一種基于改進 k-均值和距離最小二乘法的穩健蘋果檢測與重構方法；文獻[13]結合主成分分析（PCA）和快速質心分析來嘗試提高 K-Means的性能估計（RCE）。本文針對樣本初始中心利用最大期望一次估算全部初始聚類中心位置，在后續迭代求解過程中有效減少迭代次數，降低時間開銷，提高了整體聚類效果。不同的是，文獻[15]中是根據目標預測狀態選擇初始聚類中心點。文中首先介紹了傳統K-Means++算法的原理和流程，然后針對K-Means++算法的缺點，提出了基于最大期望估算初始聚類中心聚類算法。最后，根據當前研究的熱點問題，提出對K-Means算法未來研究方向的展望。

1 K-means++算法

1.1 K-means++

在判斷初始聚類中心時，K-means++參照K-means算法在其基礎上給出了在整體樣本中利用概率化選擇初始的聚類中心之間的相互距離盡可能地遠的方法，很大程度解決了原始K-means極易陷入局部最優的困境以及由于 k-means算法需要隨機地確定初始聚類中心的原因，導致不同的聚類中心可能導致完全不同的聚類結果的缺陷。

k-means++算法的核心思想是：假設已經選取了n個初始聚類中心（0＜ n＜k），則在選取第n+1個聚類中心時，聚類當前n個聚類中心越遠的點會有更高的概率被選為第 n +1個聚類中心。在選取第一個聚類中心（n = 1 ）時同樣通過隨機的方法。

k-means++算法的實現步驟，如下：

Step 1：從數據集中隨機選取一個樣本點作為初始聚類中心 c1;

Step 2：首先計算每個樣本與當前已有聚類中心之間的最短距離（即最近的聚類中心的距離），用D（ x）表示；接著計算每個樣本點被選為下一個聚類出下一個聚類中心；

Step 3：重復第2步知道選擇出K個聚類中心；

Step 4：針對數據集中的每個樣本ix，計算它到K個聚類中心的距離并將其分到距離最小的聚類中心所對應的類中；

Step 5：針對每個類別ic，重新計算它到聚類中Step 6：重復第4步和第5步直到聚類中心的位置不再變化；

在 k-means++算法中，并不是直接選擇距離最遠的點作為新的簇中心，只是讓這樣的點被選做簇中心的概率更大而已。

1.2 K-means++損失計算

對于具有相同方差的高斯分布，簇 C = ｛ c1, c2,… ,ci｝,樣本 X = ｛ x1, x2,… , xn｝，均值為 μ，標準差用σ表示，方差為 σ2。高斯混合分布下整體樣本似然函數：

ln L（θ）是 L （θ）的增函數， ln L（θ）與 L （θ）在同一點處達到最大值，對似然函數 L （θ）取對數，轉為求解對數似然方程，定義為：

對于計算簇內一點到各樣本間距離總和最小，式（2）的即為整個迭代過程中的損失函數的核心表示。

（2）為關于μ的偏導，對于本高斯混合分布下簇內樣本中心的計算方法，即為每次新簇樣本中心。

1.3 初始樣本中心選擇

概率化選擇是 K-means++算法計算初始樣本中心的核心算法，設 D = ｛ d1, d2,… dn｝為全部樣本到現有聚類中心的距離，定義下一個初始樣本中心為

其中分布下，根據概率能夠被正確選擇為臨近真正聚類中心點的概率并不是很高，這不僅要以后來的迭代計算來不停校正中心點的位置，而且容易陷入局部最優，從而影響計算效率和最終效果。

1.4 EM算法

EM 算法是一類很好的優化算法，核心算法是一組迭代計算。迭代分為兩部分，即E步和M步，兩互為輸入輸交替計算。由于EM算法的收斂性并不能保證全局最優，因此常對EM算法進行隨機初始化并多次運行，選擇對數似然最大的迭代輸出結果[8]。

EM算法的迭代過程如下：

首先，初始隨機選擇各參數的值。然后，重復下述倆步，直到收斂。

E步驟。計算當前的參數，計算每個點由某個分模型生成的概率。

M步驟。使用E步驟估計出的概率，來改進每個分模型的均值，方差和權重。

2 基于期望最大值的初始中心估算方法

通過計算得到合適瞭望樣本，以瞭望樣本的角度獲得全部樣本與瞭望樣本間距離，根據距離估算可能的初始聚類中心，一次獲得全部聚類中心并作為迭代計算的開始，逐步獲得更精確的聚類中心。其過程為，根據樣本 X = ｛ x1, x2,… , xn｝，簇數k，瞭望長度ξ，丟棄因子c。首先計算瞭望樣本，瞭望值結合瞭望長度ξ給出實際瞭望樣本值o；然后基于瞭望樣本計算整體樣本下的距離值D，根據距離分布調整瞭望長度ξ，再計算并更新丟棄因子c下新的距離D。利用最大期望算法估計高斯混合分布下距離數據中參數μ的取值，計算μ在D中的最鄰近位置，返回對應位置的樣本編號更新初始聚類中心。最后以現有初始聚類中心開始聚類，首先計算樣本歸屬再計算樣本歸屬關心下新的聚類中心，重復計算直到收斂或達到某一次數。

算法如下：

算法

輸入：樣本集 X = ｛ x1, x2,… , xn｝，簇數k，瞭望長度ξ，丟棄因子c。

輸出：簇劃分 C = ｛c1, c2,… ,ck｝

過程：

1. 從D中隨機選擇k個樣本作為初始均值向量 ｛μ1, μ2,… ,μk｝

2. repeat

3. 隨機選擇瞭望樣本o

4. for j = 1,2,… ,mdo

5. 計算其余樣本到瞭望樣本的距離，根據距離估算初始聚類中心 c1；

6. 結合瞭望長度ξ給出實際瞭望樣本值o;

7. 計算整體樣本下的距離值D，根據距離分布調整瞭望長度，再計算并更新丟棄因子c下新的距離D；

8. 計算μ在D中的最鄰近位置，返回對應位置的樣本編號更新初始聚類中心；

2.1 均值計算過程

設簇1,2,…,k服從均值不同，方差相同的高斯分布，基于歐式距離計算得到全部樣本點到現有聚類中心的距離 D = ｛ d1, d2,… dn｝，可知距離D服從高斯混合分布，如圖1。

圖1 簇為4時初始中心與樣本的距離分布Fig.1 The distance between the initial center and the sample when the cluster is 4

在方差一定得情況下各簇內均值不同，設總樣本 為 N = ｛ x1, x2,… ,xn｝， xi表 示 為 一 個 k +1元 組＜xi, zi1, zi2,… ,zik＞，元組元素只有一個取 1，其余的為0。且此處 zi1到 zik為隱藏變量，為未知，對任意 zij被選擇的概率相等，即：

由高斯混合分布的一般定義，似然函數及其參數：

σ2, … ,σ2,}，隨之定義與觀測數據有關的隱變量：2k Z→X，令隱變量的后驗分布q（ Z）表示服從高斯混合分布聚類中每個數據來源于第 c ∈ ｛ 1, 2, … ,k ｝個分布的概率，π為高斯分布的混合比例，k為參與混合的分布總數則因變量有離散取值 Z = ｛ z1, z2,… ,zk｝。

E步：使用假設和觀測數據估計概率分布

M步：對E步輸出的隱變量后驗分布計算模型參數，得到優化問題的計算框架

重復以上兩步直至收斂，得參數 μ1, μ2,… ,μk的估計值。

2.2 定義瞭望樣本

瞭望樣本作為觀測整體樣本的哨兵為整體樣本距離計算提供較好的計算角度，減少距離重疊提高距離分布清晰度，瞭望樣本定義為：

其中n為樣本維度， m ax （ Xk）為k維時樣本中最大的值，ξ為瞭望長度。

2.3 局部降噪

對于部分不規則樣本帶來的噪聲干擾，可選擇的引入丟棄因子c,（ c ∈ ［ 0,1）），將距離過近和距離太遠的數據以適當比例置零，降低離群點對整體聚類的影響，同時提高正常樣本中聚類中心被正確選擇的概率，定義：

其中c為丟棄因子，1cd-為去噪后的樣本距離。

3 結果分析

為了驗證算法有效性，實驗采用高斯混合分布下2000個方差0.3的樣本數據，參考均一性和完整，利用v-measure作為衡量指標：

其中h為均一性，表示一個簇中只包含一個類別的樣本；c為完整性，表示同類樣本被歸類到同一簇中。多次聚類效果對比如下，圖2圖3分別為K-means++和EMK-means++。

通過實驗可知，多次聚類達到 v-measure指標1.0的成功次數比K-means++為0.78，EMK-means++為 0.89，后者明顯降低了陷入局部最優概率，提升了整體聚類效果。

圖2 K-means++Fig.2 K-means++

圖3 EMK-means++Fig.3 EMK-means++

4 結束語

本文提出了一種基于最大期望估算初始樣本中心的聚類算法，結合瞭望值估算高斯混合分布下距離數據的初始樣本中心，為后續迭代計算提供了較可靠的樣本中心位置，降低了迭代次數和時間開銷，提高計算效率，提升了整體聚類效果。本文的局限性主要在方法對于數據的分布，瞭望樣本的選取以及部分參數初值的設定較為敏感，這也是下一步的主要研究內容。