改進的方差優化初始中心的K-medoids算法

張曉濱，母玉雪

(西安工程大學 計算機科學學院，陜西 西安 710600)

0 引 言

聚類分析是機器學習領域的一項關鍵技術，也是最重要的數據分析方法之一，在模式識別、圖像分割、信息檢索、疾病診斷、決策支持等方面有廣泛的應用[1-2]。常見的聚類算法總體上可細分為：劃分法、網格法、層次法、密度法與基于模型法[3-5]五大類別。聚類通過獲取給定數據集的內在屬性，將數據集劃分為多個類簇，使得同一類簇中的樣本相似度較大，不同類簇中的樣本相似性相對較小，然后把給定數據集樣本依據固有信息分別開，從而揭示數據樣本集的初始分布。

基于劃分的聚類方法首先通過預先指定初始聚類中心和聚類數目，采用迭代重定位技術反復迭代運算，使樣本在劃分類簇間移動，當目標函數的誤差值達到收斂效果時，才獲得最終的聚類結果。K-means算法與K-medoids算法是比較典型的基于劃分下的無監督聚類算法，和K-means算法相比而言，K-medoids算法克服了對孤立點敏感的缺陷，有著較強的準確性和魯棒性。為解決K-medoids算法初始化敏感、易陷入局部最優解等問題，提出了一系列K-medoids的改進算法[6-15]。Park等人[7]首次提出快速K-medoids聚類算法，通過改良初始聚類中心的選擇方式與聚類中心點的更新，縮短了聚類時間．然而該算法在選取初始聚類中心時，樣本密度的定義較為復雜，計算較為耗時，且未充分考慮到數據空間關系和數據集自身分布，使得初始聚類中心有可能位于同一個類簇。文獻[8]利用密度信息產生初始聚類中心，但是犧牲了時間復雜度去換取較好的搜索性能，以求達到聚類性能提高的效果。文獻[9]提出以方差作為樣本分布密集程度的度量標準，分別以樣本間距離均值和標準差為鄰域半徑，解決了鄰域半徑需要人為給定調節系數的缺陷，但是均值和標準差容易受到異常值影響，即鄰域半徑并非為最佳鄰域半徑。文獻[10]提出了局部方差概念，引入了近鄰概念定義樣本的局部方差，但是近鄰值需要人為給定，由于數據集大小不一，且屬性各不相同，最佳鄰域值不易選取。文獻[12]提出了一種基于距離不等式的K-medoids聚類算法，但是算法復雜度較高。

針對傳統K-medoids算法和方差優化初始聚類中心K-medoids算法的潛在不足，文中改進了樣本密度的定義，并利用最大距離乘積法，選取樣本密度較高且距離較遠的K個樣本為初始聚類中心。在更新簇類中心時，根據樣本密度原則逐步擴大搜索范圍，代替了傳統的隨機選取，在保證聚類質量的條件下提高了聚類速度。通過在UCI數據集的實驗，證明了該算法的有效性。

1 傳統K-medoids算法及其改進

1.1 基本概念與定義

假設包含N個樣本的數據集X={x1,x2,…,xi,…,xN}，對于其中任一樣本xi，類簇數目為K，即X={C1,C2,…,CK},O={o1,o2,…,oK}為類簇中心樣本集合，其中K

定義1：任意兩個樣本xi和xj間的距離采用歐幾里得距離，則

(1)

定義2：數據標準化(normalization)不僅能夠加快梯度下降求最優解的速度，還有可能提高數據精度。線性數據標準化是對原始數據的一種線性變化，使得結果映射到[0,1]范圍內。轉換函數為：

(2)

其中，max是樣本數據的最大值，min是樣本數據的最小值。

定義3：樣本xi的全局方差定義為：

(3)

1.2 傳統K-medoids聚類算法

典型的K-medoids算法描述為：

輸入：含有N個樣本的數據集X={x1,x2,…,xi,…,xN}，類簇的數目K；

輸出：K個最優簇集合。

處理流程

Step1：隨機選取K個樣本數據{o1,o2,…,oK}作為初始聚類中心。

Step2：分配樣本。根據式(1)計算剩余樣本點到聚類中心的距離，并將其劃分到離它最近的聚類中心點所代表的類簇。

Step4：重復執行Step2和Step3，直到每個類簇不再發生變化。

Step5：輸出劃分的K個類簇。

1.3 Num-近鄰方差優化初始中心的K-medoids算法

文獻[10]算法是把方差當作樣本分布密度的度量值，選取離xi最近的Num個樣本計算Num-近鄰局部方差，選擇方差最小的樣本xsort(k)當作第一個初始聚類中心，計算樣本標準差stdsort(k)，并將stdsort(k)作為鄰域半徑，計算xsort(k)鄰域Neighborsort(k)，在樣本集中去除Neighborsort(k)，再選取剩余樣本集中方差最小的樣本作為聚類中心，直至選夠K個。該算法被稱為SD(standard-deviation as radius of neighborhood)算法，主要的改進點在于初始聚類中心的選擇上，解決了初始聚類中心可能位于同一類簇中心的缺陷。

2 文中算法

2.1 算法的改進思想

通常使用方差來衡量各個數據樣本點及其均值之間的偏離程度，如果數據分布比較分散，則方差相對較大，亦說明數據對象的波動相對較嚴重。根據方差的定義可知，一個數據樣本集下方差最小的樣本常常處于數據集的中心區域，或者是樣本分布較為集中的區域。文中所提算法兼顧考慮到樣本密度和其樣本集的空間距離特征，表現優良的初始簇類中心點不僅需要所在區域樣本數量較多，而且還應該有良好的獨立性，各個中心點應該彼此分散而不集中，相互距離應該較遠，才能使得各個簇類中心點盡可能代表不同的類簇。

初始聚類中心選取基本思路：首先，計算樣本的全局方差，并按照數值大小升序排序，將前K2個低方差樣本存入候選聚類中心集合P中；然后依照最大距離乘積法，從集合P中選取K個方差值較小且相對分散的初始中心存入聚類中心集合O，使得O={o1,o2,…,oK}。將選取好的集合O作為初始聚類中心點。文中所提算法既保證初始聚類中心處在樣本分布的密集區域，還保證了初始聚類中心處于不同的類簇，從而擺脫了對人為賦值的依賴。

2.2 算法的具體描述

輸入：含有N個樣本的數據集X={x1,x2,…,xi,…,xN}，類簇的數目K；

輸出：K個最優簇集合。

處理流程

Step1：利用轉換函數式(2)對樣本進行數據標準化。

Step2：初始聚類中心的選取。假設候選初始聚類中心集合P和初始聚類中心集合O均為空集。

Step2.1：利用式(1)計算各個樣本間的距離，并根據式(3)計算各個樣本的全局方差，并將方差值最小的前K2個樣本加入高密度點集合P,P={p1,p2,…,pK2}，集合P為候選初始聚類中心點集合。

Step2.2：根據式(1)和式(3)，首先從集合P中選取方差值最小的樣本pi作為第一個初始聚類中心o1，然后在集合P中選取距離o1最遠的點pj作為第二個初始聚類中心o2，并將o1、o2加入到初始聚類中心O中，即O=O∪{o1,o2}。

Step2.3：在集合P中選取滿足條件max(d(pm,o1)×d(pm,o2))的數據對象pm作為第三個初始簇類中心o3加入集合O中。

Step2.4：重復執行步驟Step2.3，直到集合O中的初始聚類中心個數等同于K，即初始聚類中心集O={o1,o2,…,oK}。

Step3：分配樣本。根據式(1)計算剩余樣本點到聚類中心的距離，并將其劃分到離它最近的聚類中心點所代表的類簇。

Step4：更新類簇中心。對于非中心點orandom的選取，先對樣本分布密度即方差大小進行排序，從簇內開始查找，按照平方差函數值減少原則，用orandom代替oj，逐步將搜索更新范圍擴大至所有非中心點。更新每個簇的中心點。

Step5：重復執行Step3和Step4，直到每個類簇不再發生變化。

3 實驗結果與分析

為了測試文中所提算法的性能，分別采用傳統K-medoids算法、快速K-medoids算法、文獻[10]算法和文中算法在UCI機器學習數據集上進行了實驗，實驗環境為操作系統Windows 10，4 GB內存，Matlab應用軟件。

實驗所采用的數據集為UCI機器學習數據庫中經常用來測試聚類算法性能的數據集，數據集的描述如表1所示。

表1 實驗數據描述

實驗結果均為四種聚類算法分別聚類運行60次所得到的平均值，具體如圖1和圖2所示。

圖1 選取初始聚類中心耗時

圖2 聚類算法總耗時

由圖1可知，在選取初始聚類中心時，文中算法耗時高于傳統K-medoids算法，低于快速K-medoids算法和文獻[10]算法。因為傳統K-medoids算法是隨機選取，并不需要額外的計算，所以耗時較少，且在各個不同大小的數據集中差別不大；文中算法改進了樣本密度的衡量標準，簡化了選取步驟，所以會略低于快速K-medoids算法和文獻[10]算法。

由圖2可知，文中算法的聚類總耗時要低于傳統K-medoids算法、快速K-medoids算法和文獻[10]算法。主要原因是傳統K-medoids算法在初始聚類中心選擇時有很大的隨機性，導致迭代次數多，從而總耗時多；快速K-medoids算法選取的初始聚類中心點有很大可能處在同一個類簇下，容易導致初始聚類中心過于集中；文獻[10]算法在鄰域半徑的計算上容易受噪音數據影響，導致鄰域半徑很難達到最佳。文中算法在初始時給出聚類中心點的大概位置，而選取的聚類中心在保證分散性的條件下，更具備代表性，因此減少了后期的迭代次數，提高了運算效率，降低了聚類算法總耗時。

各個算法的聚類性能評價指標分別采用Rand指數、Jaccard系數、Adjusted Rand Index指數、F-measure和聚類準確率來衡量。前三個指標是在正確分類信息已明確的條件下對聚類性能評價的有效指標。其中，Rand指數能夠衡量聚類結果和原始數據集樣本分布的同一性，Jaccard系數則可以衡量實現正確聚類的樣本占聚類前或聚類后在同一個類簇樣本的比例，Adjusted Rand Index指數越大，則說明實現正確聚類的樣本對越多，而聚類效果也越好，它的上界為1。由圖3可知，文中算法在各方面表現較優于傳統K-medoids算法、快速K-medoids算法和文獻[10]算法，在不需要主觀參數的情況下取得了較好的實驗效果，提高了聚類的性能。

圖3 UCI數據集的聚類結果對比

4 結束語

綜上所述，在現有K-medoids算法不足的條件下，提出了一種改良的K-medoids聚類的優化算法。通過引入全局方差，并與最大距離乘積法相結合，優化了K-medoids聚類算法的初始聚類中心的選取，有效避免了初始化敏感的問題；同時改進了聚類時間和聚類性能。通過將該算法在數據集上進行測試，驗證了算法的有效性。