曾 新，楊 健，張 鑫，陶安玲

（大理大學(xué)數(shù)學(xué)與計(jì)算機(jī)學(xué)院，云南大理 671003）

Steinhaus（1955年）、Lloyd（1957年）、Ball&Hall（1965年）和McQueen（1967年）分別從不同的學(xué)科研究領(lǐng)域提出了K-means聚類算法，同時(shí)，McQueen總結(jié)了 Cox〔1〕、Fisher〔2〕、Sebestyen〔3〕等的研究成果，給出了K-means算法的執(zhí)行步驟，并利用數(shù)學(xué)方法進(jìn)行了理論論證。

聚類是一個(gè)將整體的數(shù)據(jù)對象劃分為以類或簇存在的包含局部數(shù)據(jù)對象的過程〔4〕。聚類的目標(biāo)是使得同一個(gè)簇中的對象之間具有較高的相似度，而不同簇中的對象相似度盡可能低。聚類分析是數(shù)據(jù)挖掘領(lǐng)域重要的研究內(nèi)容之一〔5-6〕，到目前為止，專家學(xué)者基于不同的思想提出了多種聚類算法，大致可以歸納為以下幾類〔7〕：基于劃分的算法、基于網(wǎng)格的方法、基于密度的方法、基于模型的方法和高維數(shù)據(jù)的方法，并廣泛應(yīng)用于機(jī)器學(xué)習(xí)、人工智能、圖像處理和模式識別等熱點(diǎn)研究領(lǐng)域。

由于聚類中心點(diǎn)的選取、簇的個(gè)數(shù)K和異常點(diǎn)等因素對聚類結(jié)果的影響較大，Kaufman等〔8〕提出利用數(shù)據(jù)點(diǎn)的局部密度計(jì)算出K-means聚類算法的K個(gè)初始聚類中心，減小隨機(jī)聚類中心對聚類結(jié)果的影響；針對K-means聚類算法是以確定的類數(shù)K為前提對數(shù)據(jù)集進(jìn)行聚類，而通常聚類數(shù)未知的問題，周世兵等〔9-10〕提出最佳聚類數(shù)的確定方法；Wang等〔11〕采用神經(jīng)網(wǎng)絡(luò)算法進(jìn)行K-means聚類算法初始聚類中心的選擇，得到了較好的聚類效果；謝娟英等〔12〕采用全局方差計(jì)算樣本的領(lǐng)域密度，選擇方差小且相距一定距離的樣本作為初始中心點(diǎn)；蔡宇浩等〔13〕針對初始簇中心的隨機(jī)性問題，提出加權(quán)局部方差度量樣本的密度，以便更好地發(fā)現(xiàn)密度高的樣本，并利用改進(jìn)的最大最小法，啟發(fā)式地選擇簇初始中心點(diǎn)；為了提高傳統(tǒng)K-means聚類算法的準(zhǔn)確性，王宏杰等〔14〕提出一種結(jié)合初始中心優(yōu)化和特征加權(quán)的改進(jìn)K-means聚類算法；針對傳統(tǒng)K-means算法需要人為指定簇的個(gè)數(shù)和對初始中心點(diǎn)的選取比較敏感等不足，萬靜等〔15〕提出基于可變網(wǎng)格優(yōu)化的K-means聚類算法，通過可變網(wǎng)格劃分解決了初始中心點(diǎn)不具代表性的問題并排除了噪聲干擾問題。

1 K-means聚類算法

1.1 K-means聚類算法的收斂函數(shù)K-means聚類算法是一種基于劃分的聚類算法，具有思路簡潔、收斂速度快等特點(diǎn)，該算法能夠?qū)⒁粋€(gè)含有n個(gè)數(shù)據(jù)點(diǎn)的數(shù)據(jù)集劃分為K個(gè)類簇，使得同一簇內(nèi)的數(shù)據(jù)點(diǎn)相似度高，而簇間的數(shù)據(jù)點(diǎn)相似度低。

K-means聚類算法的收斂函數(shù)〔16〕如下：

對于給定的一個(gè)包含n個(gè)d維數(shù)據(jù)點(diǎn)的數(shù)據(jù)集X={x1,x2,…,xi,…,xn}，其中xi∈Rd，K表示整個(gè)數(shù)據(jù)集經(jīng)過K-means聚類算法被劃分為數(shù)據(jù)子集的數(shù)目，K個(gè)數(shù)據(jù)子集表示為C={ }ck,k=1,2,…,K，其中每個(gè)劃分代表一個(gè)類ck，每個(gè)類ck有一個(gè)類中心μk。采用歐幾里得距離作為不同數(shù)據(jù)點(diǎn)間的相似度和距離判斷的標(biāo)準(zhǔn)，計(jì)算ck類內(nèi)各點(diǎn)到聚類中心μk的距離平方和DisSum( )ck，見公式（1）：

將收斂函數(shù)DisSum()C展開，見公式（3）：

1.2 K-means聚類算法本文應(yīng)用K-means聚類算法的基本思想如下：

從包含有n個(gè)數(shù)據(jù)點(diǎn)的數(shù)據(jù)集中隨機(jī)選取K( )K=3個(gè)數(shù)據(jù)點(diǎn)作為初始聚類中心點(diǎn)，然后采用歐幾里得公式計(jì)算出每個(gè)數(shù)據(jù)點(diǎn)到K個(gè)聚類中心點(diǎn)的距離，并將數(shù)據(jù)點(diǎn)歸類到離其最近的聚類中心點(diǎn)所在的類當(dāng)中，當(dāng)所有的數(shù)據(jù)點(diǎn)歸類完成以后，分別計(jì)算出每個(gè)類中數(shù)據(jù)點(diǎn)的均值，將類均值作為新的類中心，并重新進(jìn)行聚類，如此不斷循環(huán)，直到前后兩次聚類中心點(diǎn)相同，則聚類結(jié)束。

通過對算法進(jìn)行分析可以發(fā)現(xiàn)，K-means聚類算法的時(shí)間復(fù)雜度是O( )nKt，其中n是樣本數(shù)，K是聚類數(shù)，t是迭代次數(shù)( )K≤t,t≤n，具有可伸縮性和高效率。對于產(chǎn)生類內(nèi)緊密、類間疏離的聚類結(jié)果，具有較好聚類效果。

2 基于K-means算法的優(yōu)秀班集體評選方法

2.1 傳統(tǒng)評選方法存在的弊端傳統(tǒng)的優(yōu)秀班集體遴選方法是將評價(jià)班集體的相關(guān)屬性值進(jìn)行簡單求和，并取總和較大的前K個(gè)班級作為優(yōu)秀班集體，但是評價(jià)一個(gè)班級是否優(yōu)秀的屬性很多，例如：黨員人數(shù)、大學(xué)英語四六級考試的過級率、計(jì)算機(jī)等級考試的過級率、獲得文明宿舍的次數(shù)、參加各類文體活動獲獎(jiǎng)情況和社會實(shí)踐的效果等等。因此，對評價(jià)班集體的相關(guān)屬性值進(jìn)行簡單的求和，可能會導(dǎo)致某些班集體在某一方面的表現(xiàn)很突出而成為優(yōu)秀班集體，而其他均衡發(fā)展的班級可能會喪失成為優(yōu)秀班集體的機(jī)會，同時(shí)，受到年級的限制，部分低年級的班級屬性值較小或?yàn)榭?，對班級的評價(jià)影響較大，例如：大學(xué)一、二年級的班級黨員人數(shù)基本為空，而大學(xué)英語四六級考試的過級率和計(jì)算機(jī)等級考試的過級率也可能低于大學(xué)三、四年級的班級等。

例1 大理大學(xué)數(shù)學(xué)與計(jì)算機(jī)學(xué)院評選優(yōu)秀班集體的主要參考屬性有黨員人數(shù)、大學(xué)英語四六級考試過級率、計(jì)算機(jī)等級考試過級率、文明宿舍得分、科研立項(xiàng)獲獎(jiǎng)和各類文體活動獲獎(jiǎng)等，部分年級和班級參評數(shù)據(jù)見表1。其中，2015jil、2015tx、2015tj、2015sx分別表示2015級計(jì)科1班、2015級通信班、2015級統(tǒng)計(jì)班、2015級數(shù)學(xué)班。

表1 班集體參評數(shù)據(jù)

從表1中可以分析出：①如果按照總分排名進(jìn)行優(yōu)秀班集體的評選，那么2015級數(shù)學(xué)班在文體活動方面成績更加突出，將獲得優(yōu)秀班集體稱號，但是從評選班集體的屬性值均衡度來說，2015級通信班和2015級統(tǒng)計(jì)班的發(fā)展更加全面，因此采用屬性值簡單求和的方式評選優(yōu)秀班集體并不利于班集體的整體發(fā)展，與培養(yǎng)全面發(fā)展人才的理念存在差異；②2015級、2016級和2017級采用了相同的班級評價(jià)屬性和評價(jià)方法，受到年級的限制，2016級和2017級的某些班級屬性值較小或?yàn)榭眨瑢Π嗉壴u價(jià)影響較大。而通過分年級選取均衡發(fā)展的班集體作為種子數(shù)據(jù)點(diǎn)，然后以種子數(shù)據(jù)點(diǎn)為中心進(jìn)行聚類，直到類中心不發(fā)生改變，這種聚類方式可以有效改善傳統(tǒng)評選方式存在的弊端。

2.2 基于K-means算法的優(yōu)秀班集體評選方法首先將真實(shí)數(shù)據(jù)集按年級進(jìn)行劃分，分別得到2015級、2016級和2017級各班級的參評數(shù)據(jù)，然后從3個(gè)年級的數(shù)據(jù)集當(dāng)中分別選取所有屬性取值較平均的班級（均衡發(fā)展班級）、若干屬性取值較大的班級（偏離發(fā)展班級）和大多數(shù)屬性取值較小的班級（最差發(fā)展班級）作為初始聚類的中心，按K-means聚類算法的執(zhí)行過程，將各年級的數(shù)據(jù)集分別聚為3類，最后將均衡發(fā)展的類內(nèi)的班級作為本年級的優(yōu)秀班集體。具體的實(shí)現(xiàn)過程如下。

2015級各班級的參評數(shù)據(jù)見表2。其中，2015xx表示2015級信息班。對2015級班集體相關(guān)屬性取值進(jìn)行分析，分別選取2015tx、2015sx和2015ji1作為均衡發(fā)展、偏離發(fā)展和最差發(fā)展班級的初始聚類中心點(diǎn)，通過實(shí)驗(yàn)得到基于K-means算法的聚類結(jié)果見表3，聚類方法與傳統(tǒng)方法的優(yōu)秀班集體結(jié)果對比見表4。

表2 2015級各班參評數(shù)據(jù)

表3 聚類結(jié)果

表4 優(yōu)秀班集體對比

2016級各班級的參評數(shù)據(jù)見表5。對2016級班集體相關(guān)屬性取值進(jìn)行分析，分別選取2016sx、2016xx和2016ji1作為均衡發(fā)展、偏離發(fā)展和最差發(fā)展班級的初始聚類中心點(diǎn)，通過實(shí)驗(yàn)得到基于K-means算法的聚類結(jié)果見表6，聚類方法與傳統(tǒng)方法的優(yōu)秀班集體結(jié)果對比見表7。

表5 2016級各班參評數(shù)據(jù)

表6 聚類結(jié)果

表7 優(yōu)秀班集體對比

2017級各班級的參評數(shù)據(jù)見表8。對2017級班集體相關(guān)屬性取值進(jìn)行分析，分別選取2017tx、2017xx和2017ji1作為均衡發(fā)展、偏離發(fā)展和最差發(fā)展班級的初始聚類中心點(diǎn)，通過實(shí)驗(yàn)得到基于K-means算法的聚類結(jié)果見表9，聚類方法與傳統(tǒng)方法的優(yōu)秀班集體結(jié)果對比見表10。

表8 2017級各班參評數(shù)據(jù)

表9 聚類結(jié)果

表10 優(yōu)秀班集體對比

從3個(gè)年級分別采用基于K-means算法的評選方法和傳統(tǒng)評選方法的結(jié)果對比表中可以分析出：基于K-means算法的評選結(jié)果與傳統(tǒng)評選結(jié)果存在部分重疊的情況，是因?yàn)椴糠职嗉壊粌H總分高，而且班級各屬性值都較均衡，同時(shí)可以說明，新的優(yōu)秀班集體評選方法，在傳統(tǒng)評選方法的基礎(chǔ)上兼顧了班級各項(xiàng)評價(jià)屬性的均衡發(fā)展。

最后將3個(gè)年級的數(shù)據(jù)進(jìn)行合并，利用基于K-means算法的評選方法和傳統(tǒng)評選方法的結(jié)果對比。見表11。

表11 優(yōu)秀班集體對比

從表11中可以看出：基于K-means算法的評選方法得到的結(jié)果都是2015級的班級，這是因?yàn)槠淠昙壿^高，評價(jià)班級的相關(guān)屬性基本都有取值，而傳統(tǒng)評選方法得到的結(jié)果也基本都是較高年級的班級，同時(shí)，其存在部分屬性取值較高的、發(fā)展失衡的情況。因此，采用基于K-means算法的優(yōu)秀班集體評選方法，選取不同年級內(nèi)均衡發(fā)展的優(yōu)秀班集體，比傳統(tǒng)評選方法更合理。

3 總結(jié)

基于K-means算法的優(yōu)秀班集體評選方法，在選取均衡發(fā)展的班集體作為種子數(shù)據(jù)點(diǎn)后，將種子數(shù)據(jù)點(diǎn)作為聚類的初始中心，采用K-means聚類算法進(jìn)行聚類，直到類中心不發(fā)生改變或前后兩次收斂函數(shù)值之差小于給定閾值，則聚類結(jié)束，并將種子數(shù)據(jù)點(diǎn)所在的類內(nèi)的所有數(shù)據(jù)點(diǎn)作為優(yōu)秀班集體。采用K-means聚類算法“類內(nèi)緊密、類間疏離”的特點(diǎn)進(jìn)行優(yōu)秀班集體的評選，能夠?qū)⒕獍l(fā)展的班集體聚在同一類，解決了傳統(tǒng)評選方式中班集體因?yàn)槟骋环矫姹憩F(xiàn)突出而被評為優(yōu)秀的弊端。