基于結(jié)構(gòu)系數(shù)的K-means 初始聚類中心選擇算法*

李漢波 魏福義 張嘉龍 劉志偉 黃 杰 方月宜

（華南農(nóng)業(yè)大學(xué)數(shù)學(xué)與信息學(xué)院 廣州 510642）

1 引言

聚類分析是數(shù)據(jù)挖掘中的一個(gè)重要研究領(lǐng)域。聚類算法是衡量數(shù)據(jù)相似性的典型算法，它以“物以類聚”的思想，在文檔分析、圖像壓縮［1］、特征提取、圖像分割等領(lǐng)域得到廣泛的應(yīng)用。Mac-Queen 于1967 年首次提出K-means算法，它基于樣本間相似度對(duì)數(shù)據(jù)進(jìn)行劃分，具有聚類效果好和收斂速度快等特點(diǎn)，屬硬聚類算法［2］。傳統(tǒng)K-means算法隨機(jī)選取初始聚類中心會(huì)導(dǎo)致聚類結(jié)果不穩(wěn)定［3］。為了削弱初始聚類中心選取的隨機(jī)性對(duì)聚類結(jié)果不穩(wěn)定的影響，研究確定初始聚類中心的有效方法具有重要意義。

一個(gè)好的聚類算法具備各類中包含的樣本點(diǎn)彼此相似，并且聚類中心在空間分布上盡量分散［4］的特征，這樣才能更好地讓每一類體現(xiàn)不同于其他類的特性。確定聚類中心和數(shù)據(jù)分類問(wèn)題一直是大數(shù)據(jù)研究的熱點(diǎn)內(nèi)容［5～12］。文獻(xiàn)［13］運(yùn)用了相異度的概念，通過(guò)構(gòu)造相異度矩陣，選取K 個(gè)與其他樣本相異度較低且聚類個(gè)數(shù)最多的樣本作為初始聚類中心，該算法削弱了傳統(tǒng)算法對(duì)初始聚類中心的敏感性，在傳統(tǒng)算法的基礎(chǔ)上具有更高的分類準(zhǔn)確率。文獻(xiàn)［14］在文獻(xiàn)［13］的基礎(chǔ)上增加了一個(gè)判斷，當(dāng)最大相異度參數(shù)不唯一時(shí)，提出了一種合理選取最大相異度參數(shù)值的解決方案，改進(jìn)算法與文獻(xiàn)［13］的算法在準(zhǔn)確率和迭代次數(shù)方面有所優(yōu)化。而文獻(xiàn)［15］提出了一種基于最大距離中位數(shù)及誤差平方和（SSE）的自適應(yīng)改進(jìn)算法，通過(guò)SSE變化趨勢(shì)決定終止聚類或繼續(xù)簇的分裂。本文算法基于文獻(xiàn)［13］的相異度概念，定義一個(gè)可變鄰域參數(shù)τ，從最小結(jié)構(gòu)系數(shù)開(kāi)始，按結(jié)構(gòu)系數(shù)遞增的順序?qū)ふ页跏季垲愔行?，直到找到K 個(gè)初始聚類中心。本文實(shí)驗(yàn)表明：采用新方法構(gòu)造的算法相比文獻(xiàn)［13］、文獻(xiàn)［14］以及文獻(xiàn)［15］具有更高的準(zhǔn)確率和更少的迭代次數(shù)。

2 改進(jìn)的選取初始聚類中心算法

首先給出基于相異度的四個(gè)新概念，在此基礎(chǔ)上推導(dǎo)改進(jìn)的K-means 選取初始聚類中心的新方法，最后得到基于結(jié)構(gòu)系數(shù)的新算法。

2.1 基本概念

設(shè)待聚類樣本數(shù)據(jù)：X={x1，x2，x3，…，xn}，其中xi={xi1，xi2，xi3，…，xim}，n為數(shù)據(jù)集中的樣本數(shù)，m為樣本屬性的個(gè)數(shù)。

采用三個(gè)步驟計(jì)算樣本間相異度并構(gòu)造相異度矩陣［13］：

3）構(gòu)造相異度矩陣：

記Ri={ri1，ri2，…，rii-1，rii+1，…，rin}，其 中i=1，2，…，n。

定義1 對(duì)于樣本xi和鄰域參數(shù)τ，從Ri中任意取τ-1個(gè)元素求和，和最小的值稱為樣本xi的τ鄰域的結(jié)構(gòu)系數(shù)，記為D（τ，x）i。

定義3 對(duì)于樣本集X={x1，x2，x3，…，xn}，集合{D(τ，x1)，D(τ，x2)，…，D(τ，xn)}稱為對(duì)應(yīng)參數(shù)τ的結(jié)構(gòu)系數(shù)集合，記為M（τ）。

由定義2 和定義4 可知，最小結(jié)構(gòu)系數(shù)D（τ）對(duì)應(yīng)含有τ個(gè)樣本最密集的鄰域。對(duì)于樣本集X，若要選取K個(gè)聚類中心，則，其中表示數(shù)取下整。

2.2 算法思想

本文從τ=出發(fā)，計(jì)算并確定D（τ）及其對(duì)應(yīng)的鄰域U（τ，x）i，逐步尋找初始聚類中心。

遴選K個(gè)初始聚類中心的方法：

1）首先采用三個(gè)步驟構(gòu)造出相異度矩陣，以及計(jì)算鄰域的結(jié)構(gòu)系數(shù)集合M（τ）；

2）計(jì)算M（τ）的最小結(jié)構(gòu)系數(shù)D（τ），其對(duì)應(yīng)的樣本不妨設(shè)為xi，將樣本xi作為第一個(gè)初始聚類中心，同時(shí)標(biāo)記其鄰域U（τ，x）i的內(nèi)點(diǎn)，并將其結(jié)構(gòu)系數(shù)都設(shè)置為∞，記新的結(jié)構(gòu)系數(shù)集合為M（1τ）；

3）選取M（1τ）中最小結(jié)構(gòu)系數(shù)D（τ），其對(duì)應(yīng)的樣本不妨設(shè)為xj，將樣本xj作為候選點(diǎn)。若鄰域U（τ，x）j的內(nèi)點(diǎn)均沒(méi)有被標(biāo)記，則選取xj作為下一個(gè)初始聚類中心，并標(biāo)記其所有內(nèi)點(diǎn)，同時(shí)將內(nèi)點(diǎn)的結(jié)構(gòu)系數(shù)設(shè)置為∞。否則，將D（τ，x）j設(shè)為∞，隨后選取M（1τ）中最小的元素對(duì)應(yīng)的樣本作為候選點(diǎn)；

4）反復(fù)進(jìn)行以上判斷直至所有樣本的結(jié)構(gòu)系數(shù)都為∞，此時(shí)得到的初始聚類中心個(gè)數(shù)記為l0；

5）若l0≥K，則選擇前K 個(gè)候選點(diǎn)為初始聚類中心；若l0＜K，則清空初始聚類中心和內(nèi)點(diǎn)標(biāo)記；

6）縮小鄰域參數(shù)τ，循環(huán)以上方法，直到選出K個(gè)初始聚類中心。

根據(jù)以上分析，得到算法的流程圖如圖1 所示。

圖1 算法流程圖

3 實(shí)驗(yàn)結(jié)果與分析

以常用的五個(gè)UCI數(shù)據(jù)集為實(shí)驗(yàn)數(shù)據(jù)，將本文算法與文獻(xiàn)［5］、文獻(xiàn)［6］和文獻(xiàn)［7］的算法進(jìn)行對(duì)比實(shí)驗(yàn)，驗(yàn)證新算法的有效性。

3.1 實(shí)驗(yàn)數(shù)據(jù)集

UCI 數(shù)據(jù)集作為標(biāo)準(zhǔn)數(shù)據(jù)集，經(jīng)常用于測(cè)試機(jī)器學(xué)習(xí)算法的性能，為了驗(yàn)證以上算法選取初始聚類中心的有效性，本文采用UCI 數(shù)據(jù)集中的Diabetes 數(shù)據(jù)集、Iris 數(shù)據(jù)集、Harbeman 數(shù)據(jù)集、Wine 數(shù)據(jù)集和Seed 數(shù)據(jù)集作為實(shí)驗(yàn)數(shù)據(jù)集，數(shù)據(jù)集詳細(xì)信息如表1所示。

表1 實(shí)驗(yàn)數(shù)據(jù)集描述信息

由于Diabetes 數(shù)據(jù)集、Haberman 數(shù)據(jù)集和Wine 數(shù)據(jù)集各維度屬性取值范圍差異較大，先對(duì)這三個(gè)數(shù)據(jù)集進(jìn)行零-均值規(guī)范化，以便消除屬性差異對(duì)聚類性能的影響。對(duì)于每一維度屬性，有如下計(jì)算公式：

3.2 聚類效果評(píng)價(jià)指標(biāo)

衡量聚類算法性能的評(píng)價(jià)指標(biāo)有許多種，本文選用準(zhǔn)確度和迭代次數(shù)作為判定聚類算法性能優(yōu)劣的指標(biāo)。設(shè)數(shù)據(jù)要求分為K 類，則準(zhǔn)確度的計(jì)算公式［14］如下：

其中n 為樣本總量，αi表示被正確劃分為第i 類的樣本數(shù)量，MP值越接近1，表示聚類效果越好。

對(duì)于數(shù)據(jù)集要求分為K 類，在保證準(zhǔn)確度前提下，迭代次數(shù)越少越好。

3.3 實(shí)驗(yàn)結(jié)果和分析

表2～表6 分別是文獻(xiàn)［13］、［14］、［15］算法和本文算法在5個(gè)UCI數(shù)據(jù)集上的對(duì)比實(shí)驗(yàn)。

表2 Diabetes數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果

表3 Iris數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果

表4 Haberman數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果

表5 Wine數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果

表6 算法在Seed數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果

在Diabetes 數(shù)據(jù)集中，使用本文算法改進(jìn)的K-means算法的準(zhǔn)確率最高，為71.35%。雖然在迭代次數(shù)方面略微高于文獻(xiàn)［14］算法，但與文獻(xiàn)［13］算法持平。由此可見(jiàn)，本文算法對(duì)于Diabetes 數(shù)據(jù)集聚類性能具有改良效果。

對(duì)于Iris 數(shù)據(jù)集，本文算法的準(zhǔn)確率為89.33%，準(zhǔn)確率效果與文獻(xiàn)［13］、［14］、［15］的算法持平。在迭代次數(shù)方面，本文算法與文獻(xiàn)［13］算法性能相同，相比文獻(xiàn)［15］迭代次數(shù)減少3 次，但略遜于文獻(xiàn)［14］算法。

在Haberman 數(shù)據(jù)集中，雖然本文算法在準(zhǔn)確度方面略低于文獻(xiàn)［14］算法，但略高于文獻(xiàn)［13］算法。且本文算法的迭代次數(shù)為5，均低于文獻(xiàn)［13］和文獻(xiàn)［14］算法的迭代次數(shù)。

在Wine 數(shù)據(jù)集中，本文算法在準(zhǔn)確度方面略遜于文獻(xiàn)［13］、［14］算法，但相對(duì)于文獻(xiàn)［13］、［14］算法，本文算法的迭代次數(shù)較小，收斂速度快。因此，本文算法對(duì)于Wine 數(shù)據(jù)集的改進(jìn)性能可以接受。

在Seed 數(shù)據(jù)集中，對(duì)比于文獻(xiàn)［15］算法，本文算法能取得相同的準(zhǔn)確率，且本文算法的迭代次數(shù)為3，遠(yuǎn)低于文獻(xiàn)［15］算法。

由表2～表6 的實(shí)驗(yàn)結(jié)果可見(jiàn)，相比于文獻(xiàn)［13］、［14］、［15］算法，本文算法均能取得較為良好的聚類效果。

4 結(jié)語(yǔ)

K-means算法應(yīng)用廣泛，但由于其選取初始聚類中心的隨機(jī)性，會(huì)導(dǎo)致聚類結(jié)果不穩(wěn)定。針對(duì)這一缺陷，本文提出鄰域及其結(jié)構(gòu)系數(shù)的概念，在充分考慮數(shù)據(jù)集的整體分布后，結(jié)合數(shù)據(jù)集的局部密集程度和樣本的相異度這兩個(gè)性質(zhì)，選取周?chē)芗潭容^大且相距較遠(yuǎn)的樣本作為初始聚類中心，采用依次縮小鄰域的方法，逐個(gè)找出K 個(gè)不同的初始聚類中心。同時(shí)，本文給出了一種數(shù)據(jù)聚類新方法，不僅得到數(shù)據(jù)集的K 個(gè)初始聚類中心，而且還得到了li=(i=0，1，…，q-1)個(gè)初始聚類中心及其對(duì)應(yīng)的數(shù)據(jù)分類。

實(shí)驗(yàn)結(jié)果表明，新方法有效地削弱了傳統(tǒng)K-means算法選取初始聚類中心的盲目性，改進(jìn)后的算法提高了準(zhǔn)確度和減少了迭代次數(shù)，具有準(zhǔn)確性高和收斂速度快的聚類效果。