陳偉++李紅++王維

摘要：聚類是數(shù)據(jù)挖掘核心技術(shù)之一，是一門新興的學(xué)科。聚類技術(shù)要使一個(gè)類簇內(nèi)的實(shí)體是相似的，不同類簇的實(shí)體是相異的。從聚類研究現(xiàn)狀談起， 描述聚類概念和分類方法，介紹K-means算法的思想，并利用K-mean算法實(shí)現(xiàn)了iris數(shù)據(jù)集的分類，完成相關(guān)測(cè)試和實(shí)驗(yàn)驗(yàn)證。

關(guān)鍵詞：聚類分析；K-Means算法；數(shù)據(jù)挖掘

中圖分類號(hào)：TP301.6 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2017）10-0118-02

聚類是數(shù)據(jù)挖掘技術(shù)中一個(gè)非常重要的分支，它是在沒有任何先驗(yàn)知識(shí)的前提下，從海量數(shù)據(jù)中提取出有價(jià)值的、未知的數(shù)據(jù)。實(shí)現(xiàn)滿足要求的簇的集合。

1 聚類分析研究現(xiàn)狀

聚類分析是一個(gè)將數(shù)據(jù)集劃分成若干個(gè)子集的過程，并使同一集合內(nèi)的數(shù)據(jù)對(duì)象具有較高的相似度，而不同集合中的數(shù)據(jù)對(duì)象不相似。國(guó)內(nèi)外對(duì)聚類分析的研究已經(jīng)有很多年，學(xué)者們研究的主要內(nèi)容是基于距離的聚類分析，K-Medoids算法、K-Means算法以及其他的聚類算法的挖掘工具在眾多的統(tǒng)計(jì)軟件或者系統(tǒng)中得到廣泛的應(yīng)用。

1967年，MacQueen首次提出K均值聚類算法（K-means算法）。迄今為止，很多聚類任務(wù)都選擇該經(jīng)典算法。該算法的核心思想是找出K個(gè)聚類中心、，…，，使得每一個(gè)數(shù)據(jù)點(diǎn)和與其最近的聚類中心的平方距離和被最小化。

1998年，Huang為克服K-Means算法僅適合于數(shù)值屬性數(shù)據(jù)聚類的局限性，提出了一種適合分類屬性數(shù)據(jù)聚類的K-Modes算法，該算法對(duì)K-Means算法進(jìn)行了3點(diǎn)擴(kuò)展：引入了處理分類對(duì)象的新的相異性度量方法，使用modes代替means，并在聚類過程中使用基于頻度的方法修正modes，以使聚類代價(jià)函數(shù)值最小。

2002年，Sun等人將Bradley等人的迭代初始點(diǎn)集求精算法應(yīng)用于K-Modes算法。盡管Huang的K-Modes算法能夠聚類分類數(shù)據(jù)，但它需要預(yù)先決定或隨機(jī)選擇類的初始modes，并且初始modes的差異常常會(huì)導(dǎo)致截然不同的聚類結(jié)果。文中，Sun等人給出了一個(gè)關(guān)于應(yīng)用Bradley等人的迭代初始點(diǎn)求精算法于K-Modes聚類的實(shí)驗(yàn)研究。

2010年，李衛(wèi)平[7]提出對(duì)K-Means算法進(jìn)行改進(jìn)。他針對(duì)K-Means算法對(duì)初值的依賴性，基于最小生成樹原理選擇聚類中心進(jìn)行聚類。根據(jù)尋找最優(yōu)初值的思想提出了一種改進(jìn)K-Means算法，并將卡斯克魯爾算法以及貪心算法的思想引入到K-Means算法中。

2 聚類分析算法

2.1 劃分法

K-MEANS算法、K-Medoids算法是典型的劃分法（partitioning methods）。算法的處理思路基本是：給定一個(gè)類庫D，D中含有N個(gè)數(shù)據(jù)對(duì)象，用戶輸入需要獲得的類簇個(gè)數(shù)K，將類庫D中N個(gè)數(shù)據(jù)對(duì)象劃分成K個(gè)分組或者簇，然后通過迭代的方式更新簇的中心，當(dāng)整體的差異收斂時(shí)結(jié)束處理過程。使得簇內(nèi)的相似度更高（更相似），簇間的相異性更高（差異更大）。

劃分法的代表算法有：K-Medoids算法、CLARANS算法、K-Means算法。

2.2 層次法

對(duì)給定的數(shù)據(jù)，進(jìn)行層次分解，直到某種條件滿足。層次法構(gòu)建聚類的方法有分為兩種：

（1）凝聚層次法（自底向上法）：首先將類庫中的每一個(gè)數(shù)據(jù)劃分每一個(gè)單獨(dú)的類，通過遞歸的方法，將相似的或者相近的類合并成為一個(gè)類，最后使得一個(gè)類中所包含的數(shù)據(jù)或者分類結(jié)果滿足某種條件。

（2）分裂層次法（自頂向上法）：開始將所有的對(duì)象劃分成為一個(gè)類，然后將總類劃分成為若干個(gè)子類，接著在劃分出子類的子類，一直迭代劃分，直到獲得滿意的聚類結(jié)構(gòu)。

2.3 基于密度的方法

基于密度的方法是假定每個(gè)簇中的數(shù)據(jù)對(duì)象點(diǎn)是按照一個(gè)特定的概率分布繪制的，數(shù)據(jù)的整體分布被假設(shè)成為幾個(gè)分布的混合體，這種方法是識(shí)別出簇以及他們的分布函數(shù)?；诿芏确椒ǖ乃枷耄簩?duì)于一個(gè)給定的簇，這個(gè)簇持續(xù)的增長(zhǎng)，直至周圍的密度（對(duì)象的數(shù)目或者說是數(shù)據(jù)點(diǎn)的數(shù)目）大于一個(gè)閥值時(shí)為止。

2.4 基于模型的方法

基于模型的方法（model-basedmethods）給每一個(gè)聚類假定一個(gè)模型，然后試圖去尋找能很好的滿足這個(gè)模型的數(shù)據(jù)集。該方法識(shí)別對(duì)象的組別，可以很快地發(fā)現(xiàn)每個(gè)組的特征描述，每組代表一個(gè)概念或者是一個(gè)類。最常用的方法有決策樹和神經(jīng)網(wǎng)絡(luò)法。

2.5 基于網(wǎng)格的方法

基于網(wǎng)格的方法（grid-basedmethods）是將所有的數(shù)據(jù)劃分為若干個(gè)有限數(shù)據(jù)細(xì)胞單元格，從而形成一個(gè)可以進(jìn)行聚類操作的網(wǎng)格結(jié)構(gòu)，這樣的分割，是所有的數(shù)據(jù)對(duì)象都可以在數(shù)據(jù)網(wǎng)絡(luò)格上進(jìn)行操作，和原始數(shù)據(jù)本身無關(guān)?；诰W(wǎng)絡(luò)的方法最主要的優(yōu)點(diǎn)是其快速的處理速度。

基于網(wǎng)格的方法的主要算法有：STING算法、CLIQUE算法、WAVE-CLUSTER算法。

3 K-means算法

K-means算法是根據(jù)聚類中的均值進(jìn)行聚類劃分的聚類算法。

輸入：聚類個(gè)數(shù)，以及包含個(gè)數(shù)據(jù)對(duì)象的數(shù)據(jù)；

輸出：滿足方差最小標(biāo)準(zhǔn)的個(gè)聚類；

處理流程：

Step1：從個(gè)數(shù)據(jù)對(duì)象任意選擇個(gè)對(duì)象作為初始聚類中心；

Step2：循環(huán)Step 3到Step 4直到每個(gè)聚類不再發(fā)生變化為止；

Step3：根據(jù)每個(gè)聚類對(duì)象的均值（中心對(duì)象），計(jì)算每個(gè)對(duì)象與這些中心對(duì)象的距離，并根據(jù)最小距離重新對(duì)相應(yīng)對(duì)象進(jìn)行劃分；

Step4：重新計(jì)算每個(gè)（有變化）聚類的均值（中心對(duì)象）k-means算法的工作過程說明如下：首先從個(gè)數(shù)據(jù)對(duì)象任意選擇個(gè)對(duì)象作為初始聚類中心，而對(duì)于所剩下的其它對(duì)象，則根據(jù)它們與這些聚類中心的相似度（距離），分別將它們分配給與其最相似的（聚類中心所代表的）聚類；然后，再計(jì)算每個(gè)所獲新聚類的聚類中心（該聚類中所有對(duì)象的均值），不斷重復(fù)這一過程直到標(biāo)準(zhǔn)測(cè)度函數(shù)開始收斂為止。一般都采用均方差作為標(biāo)準(zhǔn)測(cè)度函數(shù)，具體定義如下：

（公式1.1）

（：數(shù)據(jù)庫中所有對(duì)象的均方差和；：對(duì)象的空間中的一個(gè)點(diǎn)；：聚類的均值（和均是多維的））

4 改進(jìn)K-means算法

二分K-均值算法的偽代碼形式如下：

將所有的點(diǎn)看成一個(gè)簇。

當(dāng)簇?cái)?shù)目小于K時(shí)。

對(duì)于每一個(gè)簇：

計(jì)算總誤差。

在給定的簇上面進(jìn)行K-均值聚類（k=3）。

計(jì)算將該簇一分為二的總誤差。

選擇使得誤差最小的那個(gè)簇進(jìn)行劃分操作。

5 算法實(shí)現(xiàn)與分析

Iris數(shù)據(jù)集是以鳶尾花的花瓣長(zhǎng)度、花瓣寬度、花萼長(zhǎng)度、花萼寬度作為數(shù)據(jù)源，數(shù)據(jù)集中包含了150個(gè)數(shù)據(jù)對(duì)象，由3種不同類型的鳶尾花的50個(gè)樣本數(shù)據(jù)構(gòu)成。

根據(jù)上述K-Means算法在IRIS數(shù)據(jù)集中的應(yīng)用，可得到兩個(gè)結(jié)論：

（1）初始均值設(shè)置的不同會(huì)影響迭代的次數(shù)以及各次迭代所產(chǎn)生的聚類中心，但它不會(huì)影響最后的分類結(jié)果。

（2）數(shù)據(jù)的輸入順序不同，同樣影響迭代次數(shù)，而對(duì)聚類結(jié)果沒有太大的影響。

（3）采用二分K-Means算法，避免了局部最優(yōu)的結(jié)果的出現(xiàn)。

通過改進(jìn)K-means算法實(shí)現(xiàn)中離群點(diǎn)的設(shè)置、K值等可以提高K-means算法的執(zhí)行效果。

參考文獻(xiàn)

[1]孟海東，宋飛燕，宋宇辰.面向復(fù)雜簇的聚類算法研究與實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用與軟件，2008，10：162-165.

[2]張琳，陳燕，汲業(yè)，張金松.一種基于密度的k-means算法研究[J].計(jì)算機(jī)應(yīng)用與軟件，2011，28（11）：4073-4085.

[3]李曼，趙松林.K—means聚類算法分析應(yīng)用研究[J].魅力中國(guó)，2011，（7）：243-243.

[4]李衛(wèi)平.對(duì)k-means聚類算法的改進(jìn)研究[J].中國(guó)西部科技，2010，（24）：49-50.

[5]王娟.一種高效的K-means聚類算法[J].科技信息，2012，（25）：168-168.endprint