鄧玉芳，張繼福

(太原科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，山西 太原 030024)

0 引 言

聚類(lèi)分析是數(shù)據(jù)挖掘[1]、模式識(shí)別[2]等領(lǐng)域的重要研究?jī)?nèi)容之一，在識(shí)別數(shù)據(jù)的內(nèi)在結(jié)構(gòu)方面具有重要的作用[3]，并已廣泛地應(yīng)用在金融分析、疾病診斷、假新聞檢測(cè)[4]、農(nóng)業(yè)災(zāi)害預(yù)測(cè)等實(shí)際問(wèn)題中。聚類(lèi)分析是一種常用的無(wú)監(jiān)督數(shù)據(jù)挖掘方法[5]，可將數(shù)據(jù)集劃分成若干個(gè)簇，目標(biāo)是使在同一個(gè)簇里的數(shù)據(jù)相似度盡可能得高，不同的簇之間的數(shù)據(jù)相似度盡可能得低，由此根據(jù)數(shù)據(jù)信息將數(shù)據(jù)劃分為若干簇，揭示數(shù)據(jù)的原始分布。K-medoids算法[6]是一類(lèi)基于劃分的聚類(lèi)分析方法，具有對(duì)孤立點(diǎn)敏感度低和良好的魯棒性等優(yōu)點(diǎn),并已得到了廣泛應(yīng)用。

目前，大多數(shù)K-medoids聚類(lèi)算法，由于初始聚類(lèi)中心點(diǎn)的選取和中心點(diǎn)迭代更新等原因，存在著聚類(lèi)精度和效率較低,且需要額外設(shè)置參數(shù)等不足。文中利用標(biāo)準(zhǔn)差選擇候選初始聚類(lèi)中心，給出了一種K-medoids聚類(lèi)分析算法。該算法首先利用標(biāo)準(zhǔn)差定義了初始中心點(diǎn)候選集度量公式，有效地避免密集程度較低的樣本點(diǎn),尤其是孤立點(diǎn)作為初始聚類(lèi)中心；其次采用從兩個(gè)初始中心點(diǎn)逐步增加中心點(diǎn)直到K個(gè)中心點(diǎn)的方式，從初始中心點(diǎn)候選集中確定初始中心點(diǎn)，避免初始中心點(diǎn)選擇在同一個(gè)聚類(lèi)簇；然后按照將數(shù)據(jù)樣本歸屬于最近的中心點(diǎn)的原則，形成初始聚類(lèi)簇；再次更新聚類(lèi)中心點(diǎn)，直到與上一次的聚類(lèi)誤差平方和相同，形成聚類(lèi)簇；最后采用UCI數(shù)據(jù)集和人工數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，驗(yàn)證了該聚類(lèi)算法的有效性。

1 相關(guān)工作

聚類(lèi)分析是將數(shù)據(jù)集劃分成若干個(gè)簇，在簇里的數(shù)據(jù)對(duì)象的相似度盡可能高，不同簇之間的數(shù)據(jù)對(duì)象的相似度盡可能低。常用的聚類(lèi)分析算法大致分為：基于劃分的方法、基于密度的方法、基于層次的方法、基于網(wǎng)格的方法、基于模型的方法[7]，以及基于子空間的方法[8-10]。K-medoids算法由于是以簇中心的實(shí)際樣本對(duì)象作為簇中心點(diǎn)，從而有效地降低了對(duì)于噪聲數(shù)據(jù)和孤立點(diǎn)的敏感性。K-medoids聚類(lèi)算法在選擇初始中心點(diǎn)時(shí)，有可能選為離散點(diǎn)或異常點(diǎn)，容易使聚類(lèi)過(guò)程陷入局部極值，同時(shí)也需要不斷地迭代更新聚類(lèi)中心點(diǎn)，因此聚類(lèi)效果和效率較差。

K-medoids聚類(lèi)算法經(jīng)典的PAM算法思想是：選取數(shù)據(jù)集中實(shí)際樣本對(duì)象來(lái)代表類(lèi)簇中心，首先隨機(jī)選擇K個(gè)初始中心點(diǎn)，將剩余的所有非中心點(diǎn)樣本分配到與其最為相似的聚類(lèi)簇中，計(jì)算聚類(lèi)代價(jià)函數(shù)。其次選取一個(gè)非中心點(diǎn)樣本作為新的中心點(diǎn)替換原來(lái)的中心點(diǎn)，然后計(jì)算替換中心點(diǎn)后的聚類(lèi)代價(jià)函數(shù)，如果聚類(lèi)代價(jià)函數(shù)減少，則由新的中心點(diǎn)替換原來(lái)的中心點(diǎn)，形成新的K個(gè)中心點(diǎn)，按此方式不斷地進(jìn)行中心點(diǎn)的迭代更新，直到聚類(lèi)代價(jià)函數(shù)不再降低，沒(méi)有可以替換的中心點(diǎn)為止。目前K-medoids聚類(lèi)分析的研究成果主要集中在如下三方面。

(1)初始聚類(lèi)中心點(diǎn)選取。

Park等人提出了快速K-medoids算法[11]，按照密度排序，采用前K個(gè)樣本點(diǎn)作為初始中心點(diǎn)。在更新中心點(diǎn)時(shí)采用了K-means，相比PAM算法在計(jì)算量上有所降低，在效率上有所提高。但是因?yàn)椴捎玫倪x取初始中心點(diǎn)的方式會(huì)導(dǎo)致選取的初始中心點(diǎn)可能在一個(gè)聚類(lèi)簇，因此不能很好地選擇出分布在不同簇的初始中心點(diǎn)，使得聚類(lèi)效果的準(zhǔn)確性不高。馬箐等人提出了基于粒計(jì)算的K-medoids聚類(lèi)算法，采用了粒度概念[12]，該聚類(lèi)算法給出了新的樣本相似度函數(shù)，并定義了類(lèi)簇中心，利用等價(jià)關(guān)系產(chǎn)生粒子，然后依據(jù)粒子包含樣本的數(shù)據(jù)量大小來(lái)定義粒子密度，最后選擇密度較大的前K個(gè)粒子的中心樣本點(diǎn)作為K-medoids聚類(lèi)算法的初始聚類(lèi)中心，改進(jìn)K-medoids聚類(lèi)算法的初始中心隨機(jī)選取對(duì)聚類(lèi)結(jié)果的影響，從而提高K-medoids聚類(lèi)算法的效率。謝娟英等人[13]提出了密度峰值優(yōu)化初始中心的K-medoids聚類(lèi)算法，該聚類(lèi)算法首先需要做出決策圖，然后根據(jù)決策圖來(lái)確定初始中心點(diǎn)，但是同樣也會(huì)出現(xiàn)初始中心點(diǎn)選擇在同一個(gè)簇的情況。Yu等人[14]提出了INCK聚類(lèi)算法，該聚類(lèi)算法從部分符合要求的數(shù)據(jù)樣本中確定聚類(lèi)中心，提高了聚類(lèi)結(jié)果的準(zhǔn)確性，但是在找尋符合要求的樣本時(shí)存在參數(shù)的選取問(wèn)題，而參數(shù)的選取會(huì)影響聚類(lèi)結(jié)果的準(zhǔn)確性。為此，文中定義了新的初始中心點(diǎn)候選集，在原始數(shù)據(jù)上進(jìn)行聚類(lèi)。

(2)迭代更新聚類(lèi)中心點(diǎn)。

Chu等人[15]推導(dǎo)了一個(gè)新的不等式，該不等式可用于最近鄰搜索問(wèn)題。提出了基于新不等式，先前的中心點(diǎn)指標(biāo)，內(nèi)存利用，三角形不等式準(zhǔn)則和部分距離搜索的四種基于K-medoids算法的搜索策略。顏宏文等人[16]提出了基于寬度優(yōu)先搜索的K-medoids聚類(lèi)算法。該算法利用粒計(jì)算初始化獲取K個(gè)有效粒子，從粒子中選出K個(gè)中心點(diǎn)作為初始中心點(diǎn)。之后分別對(duì)K個(gè)粒子中的對(duì)象建立以中心點(diǎn)為根節(jié)點(diǎn)的相似對(duì)象二叉樹(shù)，通過(guò)寬度優(yōu)先搜索遍歷二叉樹(shù)迭代出最優(yōu)中心點(diǎn)。宋紅海等人[17]提出了基于優(yōu)化粒計(jì)算下微粒子動(dòng)態(tài)搜索的K-medoids聚類(lèi)算法。該算法是在優(yōu)化的粒計(jì)算前提下，提出了基于微粒子動(dòng)態(tài)搜索策略，以初始中心點(diǎn)作為基點(diǎn)，形成一個(gè)微粒子，在微粒子內(nèi)部，采用離中心點(diǎn)先近后遠(yuǎn)的原則進(jìn)行搜索，有效地縮小搜索范圍，提高了聚類(lèi)準(zhǔn)確率。余冬華等人[18]提出的SPAM算法中在總結(jié)的三角不等式的基礎(chǔ)上提出了2個(gè)加速定理，其中一個(gè)定理適用于一次交換一個(gè)中心點(diǎn)的情況，另一個(gè)加速定理是第一個(gè)定理的擴(kuò)展，可適用于一次交換多個(gè)中心點(diǎn)的情況。同時(shí)SPAM算法存儲(chǔ)樣本到其聚類(lèi)中心的距離和中心點(diǎn)之間的距離，以提高效率。

(3)聚類(lèi)分析的并行化。

在處理海量數(shù)據(jù)信息時(shí)面臨的內(nèi)存容量和CPU處理速度的問(wèn)題上通常采用并行化來(lái)處理。Jiang等人[19]實(shí)現(xiàn)了基于Hadoop分布式計(jì)算平臺(tái)上的K-medoids聚類(lèi)。每個(gè)提交的作業(yè)都有許多迭代的MapReduce程序，在Map階段每個(gè)樣本被分到距離中心最相似的那個(gè)簇。在comebine階段計(jì)算每個(gè)簇的中心點(diǎn)，在reduce階段計(jì)算新的中心點(diǎn)。當(dāng)新中心點(diǎn)和原來(lái)的中心點(diǎn)相同時(shí)停止迭代。Zhao等人[20]通過(guò)引入Canopy算法和Max-Min距離算法改進(jìn)了原始的K-Medoids算法，并選擇了K個(gè)點(diǎn)作為聚類(lèi)的初始中心。然后使用MapReduce計(jì)算框架來(lái)并行化算法，改進(jìn)的聚類(lèi)算法不僅具有良好的加速性能，而且提高了聚類(lèi)的準(zhǔn)確性和收斂性，在處理大規(guī)模數(shù)據(jù)方面具有很大的性能優(yōu)勢(shì)。賴(lài)向陽(yáng)等人提出了一種MapReduce架構(gòu)下基于遺傳算法的K-Medoids聚類(lèi)[21]。利用遺傳算法的種群進(jìn)化特點(diǎn)來(lái)改進(jìn)K-Medoids算法的初始中心敏感的問(wèn)題,然后將遺傳K-Medoids算法再結(jié)合MapReduce并行，提高算法效率。王永貴等人提出了一種基于Hadoop的高效K-Medoids并行算法[22]。該算法通過(guò)改進(jìn)初始中心點(diǎn)選擇和中心點(diǎn)替換策略這兩個(gè)方面提高聚類(lèi)精度。利用Hadoop計(jì)算平臺(tái)結(jié)合基于Top K的并行隨機(jī)抽樣策略，實(shí)現(xiàn)了高效穩(wěn)定的K-Medoids并行算法，之后又通過(guò)調(diào)整Hadoop平臺(tái)，實(shí)現(xiàn)了算法的進(jìn)一步優(yōu)化。

綜上所述，近些年來(lái)很多研究者都對(duì)聚類(lèi)分析做了一定的研究。K-medoids算法作為一種基于劃分的聚類(lèi)分析方法，以實(shí)際樣本點(diǎn)作為簇中心點(diǎn)，從而有效地降低了對(duì)于噪聲數(shù)據(jù)和孤立點(diǎn)的敏感性，具有良好的魯棒性。但是在選擇初始中心點(diǎn)時(shí)，有可能選為離散點(diǎn)或異常點(diǎn)，使得聚類(lèi)準(zhǔn)確性不高。迭代更新中心點(diǎn)需要大量距離計(jì)算，使得聚類(lèi)效率較低。

2 基本概念

聚類(lèi)分析任務(wù)是將給定數(shù)據(jù)集劃分成多個(gè)簇，使簇中的數(shù)據(jù)對(duì)象盡可能相似，不同的簇之間的數(shù)據(jù)對(duì)象差異性大，可采用歐氏距離來(lái)衡量數(shù)據(jù)對(duì)象之間的相似性[23]。假設(shè)數(shù)據(jù)集X={x1,x2,…,xn}，樣本數(shù)為n，每個(gè)樣本的維數(shù)是p，第i個(gè)樣本的第a個(gè)屬性值表示為xia。參照文獻(xiàn)[13]兩個(gè)樣本間的歐氏距離，給出樣本xi與xj之間的歐氏距離，公式如下：

(1)

其中，d(xi,xj)表示樣本xi與xj的距離，i=1,2,…,n,j=1,2,…,n。

參照文獻(xiàn)[14]，聚類(lèi)誤差平方和、數(shù)據(jù)集的標(biāo)準(zhǔn)差和每個(gè)樣本的標(biāo)準(zhǔn)差公式分別定義如下：

(2)

其中，oi表示第i個(gè)簇的簇中心點(diǎn)，ci表示第i個(gè)簇，而x是屬于第i個(gè)簇的樣本點(diǎn)。數(shù)據(jù)集的標(biāo)準(zhǔn)差定義如下：

(3)

每個(gè)樣本的標(biāo)準(zhǔn)差公式如下：

(4)

其中，vi就是每個(gè)樣本的標(biāo)準(zhǔn)差值。

3 基于標(biāo)準(zhǔn)差的K-medoids聚類(lèi)分析

3.1 初始中心點(diǎn)候選集

K-medoids聚類(lèi)算法中初始中心點(diǎn)的選取影響最終的聚類(lèi)結(jié)果。初始中心點(diǎn)選擇在接近最終聚類(lèi)中心點(diǎn)區(qū)域時(shí)，聚類(lèi)結(jié)果的準(zhǔn)確性相對(duì)較高且迭代更新中心點(diǎn)的次數(shù)較少。當(dāng)初始中心點(diǎn)選擇為嚴(yán)重偏離最終聚類(lèi)中心區(qū)域的樣本或者孤立點(diǎn)時(shí)，聚類(lèi)過(guò)程容易陷入局部極值，聚類(lèi)結(jié)果準(zhǔn)確性較低且迭代更新中心點(diǎn)的次數(shù)較多。在K-medoids聚類(lèi)算法中，初始中心點(diǎn)選擇已成為提高聚類(lèi)分析效果和效率的關(guān)鍵因素。

標(biāo)準(zhǔn)差在概率統(tǒng)計(jì)中最常使用統(tǒng)計(jì)分布程度上的測(cè)量，標(biāo)準(zhǔn)差定義為方差的算術(shù)平方根，反映數(shù)據(jù)的離散程度。標(biāo)準(zhǔn)差越小，反映數(shù)據(jù)分布比較密集，標(biāo)準(zhǔn)差越大，反映數(shù)據(jù)分布比較離散。聚類(lèi)中心點(diǎn)的密集程度是較高的，所以中心點(diǎn)樣本的標(biāo)準(zhǔn)差相對(duì)是較小的。相反的孤立點(diǎn)樣本的密集度是較低的，孤立點(diǎn)樣本的標(biāo)準(zhǔn)差相對(duì)是較大的。對(duì)于上一章節(jié)給定的數(shù)據(jù)集X，依據(jù)式(3)和式(4)，將每個(gè)樣本xi的標(biāo)準(zhǔn)差vi與整體數(shù)據(jù)集的標(biāo)準(zhǔn)差v進(jìn)行比較，當(dāng)vi小于v時(shí),表明xi在分布密集程度相對(duì)較高的區(qū)域，因而成為聚類(lèi)中心點(diǎn)的可能性要大；當(dāng)vi大于v，表明xi在分布密集程度相對(duì)較低的區(qū)域，因而成為初始中心點(diǎn)的可能性要低。但是不能排除當(dāng)vi略大于v時(shí)，樣本xi是中心點(diǎn)的可能性，所以以大于v的所有樣本的平均標(biāo)準(zhǔn)差作為初始中心點(diǎn)候選集的上界。從而既可以使密集程度較大的樣本點(diǎn)在初始中心點(diǎn)候選集內(nèi)，又可以使離散程度不太大的樣本點(diǎn)也在初始中心點(diǎn)候選集里。

為了避免孤立點(diǎn)或者密集度較低的樣本點(diǎn)被選為初始中心點(diǎn)，同時(shí)也為了使初始中心點(diǎn)被選為密集度較大的樣本點(diǎn)，定義了初始中心點(diǎn)候選集，以進(jìn)一步提高聚類(lèi)的效果和效率。當(dāng)樣本的標(biāo)準(zhǔn)差小于超出數(shù)據(jù)集標(biāo)準(zhǔn)差的所有樣本的平均標(biāo)準(zhǔn)差時(shí)，該樣本點(diǎn)就有可能是初始中心點(diǎn)，初始中心點(diǎn)候選集sm的定義如下：

sm={xi|vi≤v',i=1,2,…,n}

(5)

其中，v'是vi大于v的所有vi的均值。

在K-medoids聚類(lèi)分析中，不必從全部數(shù)據(jù)對(duì)象中選擇初始中心點(diǎn)，僅從初始中心點(diǎn)候選集中選擇即可，從而有效地提高了聚類(lèi)中心點(diǎn)選取效率和效果。

3.2 聚類(lèi)分析

在K-medoids聚類(lèi)算法中，初始中心點(diǎn)選擇尤為重要。在初始中心點(diǎn)的選取上，為了避免選取到孤立點(diǎn)作為初始中心點(diǎn)，同時(shí)又為了選取到密集程度較大的樣本點(diǎn)作為初始中心點(diǎn)，文中利用式(5)定義的初始中心點(diǎn)候選集，從初始中心點(diǎn)候選集選取初始中心點(diǎn)，并迭代更新，其聚類(lèi)過(guò)程參考INCK聚類(lèi)算法由如下兩步來(lái)實(shí)現(xiàn)。

首先在初始中心點(diǎn)候選集中選取兩個(gè)初始中心點(diǎn)，并迭代更新兩個(gè)初始中心點(diǎn)。在選擇第一個(gè)初始中心點(diǎn)o1時(shí)，選取距離到所有樣本點(diǎn)距離之和最小的樣本點(diǎn)作為中心點(diǎn),公式如下：

(6)

其中，樣本xi到所有樣本點(diǎn)的距離之和di的公式如下：

(7)

第二個(gè)初始中心點(diǎn)o2的選取為初始中心點(diǎn)候選集中距離第一個(gè)初始中心點(diǎn)最遠(yuǎn)的樣本點(diǎn)，使初始中心點(diǎn)盡可能地選擇在不同的聚類(lèi)簇中，避免出現(xiàn)在同一聚類(lèi)簇里，公式如下:

(8)

然后按照就近原則聚類(lèi)，把所有的樣本點(diǎn)歸屬于距離最近的中心點(diǎn)，計(jì)算聚類(lèi)誤差平方和，之后更新每個(gè)簇中心，使每個(gè)簇內(nèi)新中心點(diǎn)距離其簇中所有樣本的距離之和最小，公式如下：

(9)

其中，cj表示第j個(gè)聚類(lèi)簇，xl要和xi一樣是屬于cj，如果xl不屬于cj，則不將其與xi的距離算在內(nèi)。用新中心點(diǎn)代替原中心點(diǎn)，然后聚類(lèi)計(jì)算聚類(lèi)誤差平方和，若與上一次聚類(lèi)誤差平方和一樣則不再更新中心點(diǎn)，否則繼續(xù)更新中心點(diǎn)。

其次從初始中心點(diǎn)候選集中，選取其余的k-2個(gè)初始中心點(diǎn)。假設(shè)已經(jīng)得到g(2≤g

(10)

(11)

然后聚類(lèi)迭代更新中心點(diǎn)。按此方式逐步增加初始中心點(diǎn)直到確定k個(gè)中心點(diǎn)，并得到最終聚類(lèi)結(jié)果。

3.3 聚類(lèi)分析算法

根據(jù)上一小節(jié)聚類(lèi)分析的基本思想，基于標(biāo)準(zhǔn)差的K-medoids聚類(lèi)分析算法偽代碼描述如下所示。

算法1:SDK聚類(lèi)算法(standard-deviation-based K-medoids clustering algorithm)

輸入:數(shù)據(jù)集X,簇?cái)?shù)k

輸出:k個(gè)聚類(lèi)簇

(1)sm=getsm()

(2)fori=1 tondo

(3) forj=1 tondo

(4)根據(jù)式(7)得到di

(5) end for

(6)end for

(7)fori=1 tosdo

(8)根據(jù)式(6)得到第一個(gè)初始中心點(diǎn)o1，s為初始中心點(diǎn)候選集大小

(9)end for

(10)fori=1 tosdo

(11)根據(jù)式(8)得到第二個(gè)初始中心點(diǎn)o2

(12)end for

(13)Cluster()

(14)fori=1 tondo

(15)按照式(2)計(jì)算聚類(lèi)誤差平方和E

(16)end for

(17)Update();

(18)ifk>2 then

(19) forg=2 tok-1 do

(20) forj=1 tosdo

(21)根據(jù)式(10)和式(11)得到第g+1個(gè)初始中心點(diǎn)

(22) end for

(23) Cluster();

(24) forh=1 tondo

(25)按照式(2)計(jì)算聚類(lèi)誤差平方和E

(26) end for

(27) Update();

(28) end for

(29)end if

算法2：getsm()

輸入:數(shù)據(jù)集X

輸出:初始中心點(diǎn)候選集sm

(1)fori=1 tondo

(2) forj=itondo

(3)計(jì)算得到樣本間距離d(xi,xj)

(4) end for

(5)end for

(6)fori=1 topdo

(7) forj=1 tondo

(9) end for

(10)end for

(11)fori=1 tondo

(12)根據(jù)式(3)得到數(shù)據(jù)集標(biāo)準(zhǔn)差v

(13)end for

(14)fori=1 tondo

(15) forj=1 tondo

(16)根據(jù)式(4)得到每個(gè)樣本點(diǎn)的標(biāo)準(zhǔn)差值vi

(17) end for

(18)end for

(19)fori=1 tondo

(20)根據(jù)式(5)得到sm；

(21)end for

算法3:Update()

輸入:g個(gè)中心點(diǎn)

輸出:更新后的g個(gè)中心點(diǎn)和g個(gè)聚類(lèi)簇

(1)While true do

(2) fori=1 tondo

(3) forj=1 tondo

(4)按照式(9)找到更新后的中心點(diǎn)

(5) end for

(6) end for

(7) Cluster();

(8) forh=1 tondo

(9)按照式(2)計(jì)算聚類(lèi)誤差平方和newE

(10) end for

(11) if newE==E then

(12) break;

(13) else

(14) E=newE

(15) end if

(16)end while

算法4:Cluster()

輸入:g個(gè)中心點(diǎn)

輸出:g個(gè)聚類(lèi)簇

(1) fori=1 tondo

(2)d=d(xi,o1)

(3) setlabeli=1

(4) forj=2 tokdo

(5) newd=d(xi,oj)

(6) if newd

(7) setlabeli=j

(8)d=newd

(9) end if

(10) end for

(11) end for

3.4 時(shí)間復(fù)雜度分析

在SDK聚類(lèi)算法中，由算法2計(jì)算樣本間距離的時(shí)間復(fù)雜度是o(n2)，計(jì)算均值的時(shí)間復(fù)雜度是o(np)，計(jì)算數(shù)據(jù)集的標(biāo)準(zhǔn)差的時(shí)間復(fù)雜度是o(n)，計(jì)算所有樣本的標(biāo)準(zhǔn)差的時(shí)間復(fù)雜度是o(n2)，計(jì)算初始中心點(diǎn)候選集的時(shí)間復(fù)雜度是o(n)，在算法1中計(jì)算di的時(shí)間復(fù)雜度是o(n2)，選取初始中心點(diǎn)的時(shí)間復(fù)雜度是o(ks)。在算法4中，樣本聚類(lèi)的時(shí)間復(fù)雜度為o(nk)，因此整體的聚類(lèi)時(shí)間復(fù)雜度是o(nk2)，在算法3中，假設(shè)更新中心點(diǎn)的最大迭代次數(shù)是t次，則更新中心點(diǎn)的時(shí)間復(fù)雜度是o(tn2)，所以整體的更新中心點(diǎn)的時(shí)間復(fù)雜度為o(tkn2)，因此SDK聚類(lèi)算法的整體的時(shí)間復(fù)雜度是o(n2+np+n+n2+n+n2+ks+nk2+tkn2)，最終時(shí)間復(fù)雜度表示為o(n2+tkn2+nk2)。

4 實(shí)驗(yàn)結(jié)果及相關(guān)分析

實(shí)驗(yàn)環(huán)境：Intel(R) Core(TM) i5-8265U CPU，8 G內(nèi)存，windows10操作系統(tǒng)，eclipse作為開(kāi)發(fā)平臺(tái)，采用java語(yǔ)言實(shí)現(xiàn)SDK聚類(lèi)算法。文中為驗(yàn)證SDK聚類(lèi)算法的準(zhǔn)確性以及魯棒性，選用SPAM聚類(lèi)算法,INCK聚類(lèi)算法和經(jīng)典的聚類(lèi)算法k-means[24]在UCI數(shù)據(jù)集和人工數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)驗(yàn)證。在對(duì)準(zhǔn)確性的驗(yàn)證上采用了Rand指數(shù)還有F-measure值這兩個(gè)評(píng)價(jià)指標(biāo)。在驗(yàn)證SDK聚類(lèi)算法的聚類(lèi)效率時(shí)，與同樣是K-medoids聚類(lèi)算法的SPAM聚類(lèi)算法、INCK聚類(lèi)算法進(jìn)行實(shí)驗(yàn)對(duì)比。在實(shí)驗(yàn)中SDK聚類(lèi)算法、SPAM聚類(lèi)算法以及經(jīng)典k-means聚類(lèi)算法的參數(shù)只需要k值，INCK聚類(lèi)算法除了需要設(shè)定參數(shù)k值外，還需要一個(gè)額外的參數(shù)λ。

4.1 數(shù)據(jù)集

文中在實(shí)驗(yàn)中采用了UCI數(shù)據(jù)集，用來(lái)分析比較不同聚類(lèi)算法的準(zhǔn)確性和效率。在實(shí)驗(yàn)中采用的所有數(shù)據(jù)集的名稱(chēng),數(shù)據(jù)的樣本數(shù),樣本屬性個(gè)數(shù)和真實(shí)的簇?cái)?shù)如表1所示，其中sensor表示的是sensor_readings_24數(shù)據(jù)集。同時(shí)為了實(shí)驗(yàn)分析聚類(lèi)算法的魯棒性，采用了Matlab工具，隨機(jī)生成了5組符合正態(tài)分布的人工數(shù)據(jù)集。在每組數(shù)據(jù)集分為4類(lèi)，每類(lèi)有500個(gè)數(shù)據(jù)樣本，屬性維度是10維的基礎(chǔ)上，分別增加15%、20%、25%、30%、35%的噪聲數(shù)據(jù)，從而形成5組人工數(shù)據(jù)集。表2為生成人工數(shù)據(jù)集的各種具體參數(shù)。按照表2給出的參數(shù)，隨機(jī)生成了5組人工數(shù)據(jù)集，生成的5組人工數(shù)據(jù)集的具體的樣本數(shù)，屬性個(gè)數(shù)以及真實(shí)的簇?cái)?shù)如表3所示。

表1 UCI數(shù)據(jù)集

表2 生成人工數(shù)據(jù)集的參數(shù)

表3 人工數(shù)據(jù)集

續(xù)表3

4.2 初始中心點(diǎn)候選集

在SDK聚類(lèi)算法中，由于采用了初始中心點(diǎn)候選集，所以聚類(lèi)初始中心點(diǎn)選擇不必從全部的數(shù)據(jù)樣本中去確定，并且更為準(zhǔn)確且有效。在實(shí)驗(yàn)驗(yàn)證中各個(gè)數(shù)據(jù)集的初始中心點(diǎn)候選集的樣本個(gè)數(shù)如表4所示。

表4 初始中心點(diǎn)候選集

由表4可以看出，在實(shí)驗(yàn)中采用的所有數(shù)據(jù)集的初始中心點(diǎn)候選集樣本數(shù)相較于原來(lái)整體數(shù)據(jù)集都減少了，從而在確定初始中心點(diǎn)時(shí)，不必從全體數(shù)據(jù)中尋找，減少了計(jì)算量，有效地提高了聚類(lèi)效率。

4.3 聚類(lèi)精度

為了驗(yàn)證SDK聚類(lèi)算法的聚類(lèi)效果，實(shí)驗(yàn)采用SDK聚類(lèi)算法與SPAM聚類(lèi)算法和INCK聚類(lèi)算法以及k-means聚類(lèi)算法在UCI數(shù)據(jù)集上進(jìn)行了聚類(lèi)精度的實(shí)驗(yàn)對(duì)比，其中實(shí)驗(yàn)結(jié)果數(shù)據(jù)采用了各算法運(yùn)行10次的平均值。

從圖1和圖2的結(jié)果可以看出，無(wú)論是Rand指數(shù)還是F-measure值，表現(xiàn)最好的是SDK聚類(lèi)算法，因此整體上，聚類(lèi)的準(zhǔn)確性最高的是SDK聚類(lèi)算法。SDK聚類(lèi)算法的聚類(lèi)準(zhǔn)確性相對(duì)較好主要是因?yàn)樵趯?duì)初始中心點(diǎn)的選取上，避免了選取孤立點(diǎn)為初始中心點(diǎn)，同時(shí)又盡可能地避免選取的初始中心點(diǎn)在同一個(gè)簇的情況，并且使初始中心點(diǎn)選在密集度相對(duì)較高的樣本上,因而聚類(lèi)準(zhǔn)確性上表現(xiàn)較好。

圖1 真實(shí)數(shù)據(jù)集上Rand指數(shù)的值

圖2 真實(shí)數(shù)據(jù)集上F-measure的值

4.4 聚類(lèi)效率

采用表1所示的UCI數(shù)據(jù)集，與同樣是K-medoids算法的SPAM聚類(lèi)算法和INCK聚類(lèi)算法進(jìn)行實(shí)驗(yàn)對(duì)比，驗(yàn)證SDK聚類(lèi)算法的效率。實(shí)驗(yàn)結(jié)果如表5所示，其中取10次運(yùn)行結(jié)果的平均值作為實(shí)驗(yàn)結(jié)果。

由表5可知，SDK聚類(lèi)算法效率是最高的，而SPAM聚類(lèi)算法效率是最差的，INCK聚類(lèi)算法的效率居中。其主要原因是SDK聚類(lèi)算法采用了初始中心點(diǎn)候選集的方式，確定中心點(diǎn)的時(shí)候不必從全部樣本中選擇，在更新中心點(diǎn)時(shí)和INCK聚類(lèi)算法一樣采用了快速K-medoids的方式，而SPAM聚類(lèi)算法采用的是PAM聚類(lèi)算法的中心點(diǎn)更新方式，從全部數(shù)據(jù)樣本中查找中心點(diǎn)，所以SDK聚類(lèi)算法在計(jì)算量上相對(duì)減少。除此之外，SDK聚類(lèi)算法和INCK聚類(lèi)算法采用了存儲(chǔ)樣本之間距離的方式，之后用到直接調(diào)用即可。SPAM聚類(lèi)算法雖然也采用存儲(chǔ)距離的方式，但是只存儲(chǔ)樣本點(diǎn)到其中心點(diǎn)的距離和中心點(diǎn)之間的距離，在之后用到其他兩個(gè)樣本之間的距離時(shí)都要重新計(jì)算。因此SDK聚類(lèi)算法和INCK聚類(lèi)算法都減少了不必要的距離的重復(fù)計(jì)算，而SPAM聚類(lèi)算法需要重復(fù)計(jì)算距離。所以整體上SDK聚類(lèi)算法和INCK聚類(lèi)算法的效率都要比SPAM聚類(lèi)算法要高，而文中SDK聚類(lèi)算法的效率是最高的。

表5 聚類(lèi)算法運(yùn)行時(shí)間 s

4.5 聚類(lèi)魯棒性

為了驗(yàn)證SDK聚類(lèi)算法的魯棒性，采用表3所示的人工數(shù)據(jù)集，將SDK聚類(lèi)算法，SPAM聚類(lèi)算法,INCK聚類(lèi)算法和k-means聚類(lèi)算法進(jìn)行了實(shí)驗(yàn)對(duì)比分析，其中實(shí)驗(yàn)結(jié)果選取了各算法運(yùn)行10次結(jié)果的平均值。表6是Rand指數(shù)的實(shí)驗(yàn)結(jié)果，表7是F-measure的實(shí)驗(yàn)結(jié)果。

表6 人工數(shù)據(jù)集上的Rand指數(shù)

表7 人工數(shù)據(jù)集上的F-measure

從表6和表7可知，在4個(gè)聚類(lèi)算法中，SDK聚類(lèi)算法和SPAM聚類(lèi)算法的魯棒性表現(xiàn)相近且表現(xiàn)較好，INCK聚類(lèi)算法的魯棒性是最差的。SDK聚類(lèi)算法的魯棒性保持良好的主要原因是SDK聚類(lèi)算法采用了初始中心點(diǎn)候選集，在選取中心點(diǎn)的時(shí)候，盡量避免不合適的數(shù)據(jù)被選為中心點(diǎn)。

5 結(jié)束語(yǔ)

利用了標(biāo)準(zhǔn)差反映數(shù)據(jù)分布離散程度的原理，定義了初始中心點(diǎn)候選集，從初始中心點(diǎn)候選集中選取初始中心點(diǎn)，避免孤立點(diǎn)或者密集度較低的樣本點(diǎn)被選為初始中心點(diǎn)，同時(shí)也使初始中心點(diǎn)選為密集度較大的樣本點(diǎn)。在UCI數(shù)據(jù)集及人工數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)驗(yàn)證，其實(shí)驗(yàn)結(jié)果驗(yàn)證了該算法的有效性。下一步的工作主要是對(duì)SDK聚類(lèi)算法的并行化。