改進(jìn)模擬退火算法的K—means聚類方法在學(xué)生成績上的應(yīng)用

【摘 要】本文以學(xué)生管理系統(tǒng)中學(xué)生的成績作為測試集，提出一種新的基于改進(jìn)模擬退火的k-means算法的評價函數(shù)，挖掘?qū)W生成績中的有效數(shù)據(jù)，用改進(jìn)前后的算法來解決最優(yōu)問題。實驗證明改進(jìn)模擬退火的k-means聚類算法收斂效果要優(yōu)于傳統(tǒng)的K-means算法，具有更好的聚類性能，其算法更加高效。

【關(guān)鍵詞】模擬退火算法 數(shù)據(jù)挖掘 K-means聚類 學(xué)生成績

【中圖分類號】G 【文獻(xiàn)標(biāo)識碼】A

【文章編號】0450-9889（2017）08C-0149-04

聚類（Clustering）是一種重要的數(shù)據(jù)分析手段，常用于數(shù)據(jù)挖掘領(lǐng)域，其主要用于實現(xiàn)對數(shù)據(jù)的深層次分析。它已經(jīng)廣泛應(yīng)用于圖像處理、模式識別、生物信息學(xué)等各個領(lǐng)域。K-means算法是數(shù)據(jù)挖掘中聚類問題的重要算法之一，也是現(xiàn)在公認(rèn)的最有前景的數(shù)據(jù)分析算法。然而，由于隨機初始聚類中心的選取，因此聚類算法得不到全局最優(yōu)解，并且收斂時間過長，影響分類的效果，會導(dǎo)致聚類結(jié)果的極不穩(wěn)定。

1953年，Metropolis等人提出一種基于概率的算法——模擬退火算法（Simulated Annealing）。利用模擬退火算法采用啟發(fā)式搜索初始聚類中心，再結(jié)合K-means算法，可以解決局部最優(yōu)解優(yōu)解的問題；同時減少了迭代次數(shù)，提高了聚類劃分的質(zhì)量，讓數(shù)據(jù)分析更科學(xué)化。

早已有一些學(xué)者研究模擬退火K-means聚類算法，并提出了一系列具有進(jìn)步意義的觀點，將其投入到實際應(yīng)用中。李健等學(xué)者也進(jìn)行了這一類研究，并將其跟鏡頭聚類相結(jié)合，進(jìn)行了拓展性應(yīng)用分析；陳慧萍等人將其跟UCI機器學(xué)習(xí)數(shù)據(jù)結(jié)合，提高了機器的運算能力；陳明等人將模擬退火K-means聚類算法跟多波段圖像相結(jié)合，發(fā)現(xiàn)模擬退火K-means聚類算法能夠從多波段圖像中提取有價值的信息，提高對采集的數(shù)據(jù)的運算能力。本文以學(xué)生管理系統(tǒng)中學(xué)生的成績作為測試集，提出一種新的基于改進(jìn)模擬退火的K-means算法的評價函數(shù)，挖掘?qū)W生成績中的有效數(shù)據(jù)，更準(zhǔn)確地體現(xiàn)聚類的類內(nèi)間距和類間間距，從而促進(jìn)教學(xué)質(zhì)量的提高。

一、模擬退火算法概述

模擬退火算法的基本思想最開始來源于固體物質(zhì)退火學(xué)說中，其做法為：先加熱某個物體，讓其升溫到一定的溫度。當(dāng)溫度足夠高時再進(jìn)行緩慢降溫。在使用模擬退火K-means聚類算法優(yōu)化問題的時候，往往能夠?qū)?nèi)能E轉(zhuǎn)化為我們需要的目標(biāo)函數(shù)值f，也能夠?qū)⒃谶@個過程中的溫度T轉(zhuǎn)化為控制參數(shù)t，這樣可以推算得到優(yōu)化方法：先計算初始解與t，對解實施迭代，之后體系的t不斷地減小，控制體系的溫度T降低，當(dāng)體系的控制參數(shù)t降到最低值的時候，我們就能夠得到一個最優(yōu)解，該數(shù)值也就是本次計算的理想數(shù)值。

模擬退火算法性質(zhì)上屬于啟發(fā)式隨機算法，相對于過去使用的算法來說，該種算法運算簡單，應(yīng)用范圍廣，計算起來比較容易，運算效率快，而且不容易受到初始條件的約束。從理論層面上來看，利用該種算法是能夠獲得最優(yōu)解的，而且也有人證明該種方法計算得到最優(yōu)解的概率為100%，同時該種方法也能夠進(jìn)行大規(guī)模運算量的操作，提高了人們對數(shù)據(jù)的分析能力。

模擬退火算法也有很多缺點，比如說當(dāng)參數(shù)變化的時候，其運算結(jié)果也會發(fā)生變化?？刂企w系的溫度T衰減參數(shù)若是選擇的不好，或者是退火過程的收斂速度太慢，都會影響到解的精確性，影響了我們計算獲得最優(yōu)解。

二、聚類

聚類（Clustering）是一種重要的數(shù)據(jù)分析手段，常用于數(shù)據(jù)挖掘領(lǐng)域（Data Mining），其主要用于實現(xiàn)對數(shù)據(jù)的深層次分析。而K-means聚類算法又是聚類數(shù)據(jù)分析中最主要的一種，也是目前最科學(xué)化的一種算法。K-means聚類算法最早是Steinhaus（1955）、Loyd（1957）、Ball&Hall（1965）和McQueen（1967）在其相應(yīng)的研究領(lǐng)域提出的。K-means聚類算法運算效率高、計算方法漸變、運算應(yīng)用范圍廣，這些都讓K-means聚類算法在諸多領(lǐng)域得到了應(yīng)用，比如信息技術(shù)領(lǐng)域、醫(yī)學(xué)領(lǐng)域、決策科學(xué)領(lǐng)域等，都展現(xiàn)出了K-means聚類算法的應(yīng)用價值。

K-means聚類算法的優(yōu)勢在于能夠找到該類準(zhǔn)則下的最小k個劃分，而這類算法的結(jié)合能力好，比較容易實現(xiàn)，同時各項指標(biāo)也都發(fā)現(xiàn)K-means聚類算法具有很多優(yōu)勢，比如收斂能力強、運算效率高等。在K-means聚類算法中，如果各類之間區(qū)別明顯，同時數(shù)據(jù)分布也比較密集，則使用K-means聚類算法處理數(shù)據(jù)能夠得到最佳結(jié)果。若是處理一些大規(guī)模的數(shù)據(jù)，K-means聚類算法也能夠很好地實現(xiàn)對數(shù)據(jù)的處理，不僅處理效率高，而且伸縮性較好。在K-means聚類算法中，算法的復(fù)雜度是O（nkm）。這三個字母有著不同的含義，n的含義是對象的數(shù)目，k的含義是聚類數(shù)目，m的含義是迭代次數(shù)。這三個指標(biāo)的大小規(guī)律為k和m的數(shù)值一般要比n小很多。

然而，K-means聚類算法的應(yīng)用范圍也比較窄，主要是因為以下幾個缺陷：一是最初的劃分會顯著影響最后的數(shù)據(jù)分析結(jié)果；二是k需要提前設(shè)定，無法自動生成或者是自動調(diào)整；三是無法用在一些非凸面形狀的類運算中，也無法用在一些大小差別很大的類運算中；四是孤立點或噪聲會影響到K-means聚類算法的運算結(jié)果；五是該類算法停止于局部最優(yōu)解。

整體來看，“容易陷入局部最優(yōu)解”正是模擬退火算法致力于解決的問題。

三、改進(jìn)模擬退火算法在K-means聚類中的應(yīng)用

基于模擬退火算法的K-means聚類方法的參數(shù)選擇如下：

（一）目標(biāo)函數(shù)。根據(jù)誤差平方和準(zhǔn)則函數(shù)JC，就能夠?qū)⒕垲愡M(jìn)行劃分，將其劃分為離散距離和Js，而公式表示如下：

上述公式是這C個類的聚類中心，計算出樣本的均值，計算公式如下：

在這里我們可以推算得到樣本跟聚類中心的距離，其他指標(biāo)的運算方式如下。

（二）初始溫度。在設(shè)定初始溫度的時候，應(yīng)該設(shè)定一個相對較高的數(shù)值，這樣對于一些運算得到的解都是可以接受的，但是若是溫度設(shè)定過高也是沒有意義的。最佳運算方法為，選擇K-means聚類算法得到的結(jié)果作為本次研究的初始結(jié)果，而可以得到T0=Jd。但是需要注意的是，K-means聚類算法的K是用隨機方法得出的。

（三）擾動方法。通過對之前求算獲得的解進(jìn)行擾動，可以產(chǎn)生新的解。一般來說，最佳方式就是K-means聚類算法單個樣本擾動：將所有的聚類樣本從所屬于的類別中取出，將其放入到另一個類別中，形成一個全新的聚類方案。

（四）退火過程。具體做法為先乘以一個系數(shù)，也就是T（t）=aT（t-1），在上述公式中，a可能是介于0到1之間的任意值，而a數(shù)值越大，則退火時間也就越長，a數(shù)值越小，則退火時間也就越短；因此最好是選擇a數(shù)值最大的退火方案，這樣得到的數(shù)值解是我們需要的解。

改進(jìn)K-means聚類算法的過程如下：

1.使用K-means聚類算法進(jìn)行聚類分析，得到一系列的結(jié)果，將這個結(jié)果當(dāng)作初始解，這樣可以得到目標(biāo)函數(shù)值。

2.將本次運算中的溫度初始化成為目標(biāo)函數(shù)值。

3.任意選擇溫度t，反復(fù)進(jìn)行4-6步的運算操作，直到得到的溫度低于某個給定數(shù)值為止，終止4-6步的運算操作，進(jìn)行第七步運算。

4.因為聚類狀態(tài)是在某個范圍內(nèi)進(jìn)行波動的，將樣本從某一類轉(zhuǎn)移到另一類，是可以推算得到目標(biāo)函數(shù)的。

5.計算兩個函數(shù)之間的差值。

6.根據(jù)該算法的接受規(guī)則，若是差值≤0，則認(rèn)為新算出來的數(shù)值是可以接受的；否則新算出來的數(shù)值是否可以接受以概率p來接受，并且返回到運算的第三步。

7.結(jié)束運算。

算法描述如下：

輸入：x={x1，x2，…，xi}，y j =（y1，y2，…，yi）屬于R50，聚類個數(shù)N

輸出：最優(yōu)的聚類劃分的聚類中心S={a1，a2，…，aN}

1 初始化：

T0=Jd；

PN=Random_partition（x）； //隨機劃分x

Purity（Ω，C） object = Purity（Ω，C）（PN）； // Purity（Ω，C） object 為算法的評價函數(shù)，具體計算方法詳見5.4節(jié)。

S=a（PN）；

Purity（Ω，C）best= Purity（Ω，C）object； // Purity（Ω，C）best為搜索中最優(yōu)解的目標(biāo)函數(shù)的取值。

2 改進(jìn)模擬退火算法獲取初始聚類中心：

While（100*n>0）

Begin

for（loop=N；loop>=1；loop--）

begin

num=0；

while（num

Begin

選取離聚類中心最遠(yuǎn)的實體，重新劃分，得到新的PN

S=a（PN）； //S是模擬退火算法搜索過程中搜索到的聚類中心；

Purity（Ω，C） object = Purity（Ω，C）（PN）；

Δf= Purity（Ω，C） object- Purity（Ω，C） object；

if（Δf>0）

{ PN =PN；

Purity（Ω，C） object = Purity（Ω，C）（PN）；

S=S；

if（Purity（Ω，C）best> Purity（Ω，C）object））{ num=0；}

else{ num++；}}

else

{ if（random[0，1]<=min（1，exp[-（Δf）/ T0]））

{ PN =PN； S=S；}}

End

End

T（t） = a T（t-1）； //退火過程

End

3 Pk=K-means（x，S，k）； //運行K-means

S=a（Pk）； //更新聚類中心

改進(jìn)模擬退火算法共有三個循環(huán)，第一層循環(huán)是模擬退火降溫過程；中間循環(huán)是使用變換規(guī)則產(chǎn)生新解；最內(nèi)層循環(huán)是維持初始數(shù)據(jù)的穩(wěn)定。此算法將采用隨機插入法產(chǎn)生新解，以概率的方式接受較差的解，從而能夠跳出局部最優(yōu)解，獲得全局近似的最優(yōu)解，從而得到的初始聚類中心接近于最優(yōu)的聚類中心。再將此初始聚類中心進(jìn)行聚類進(jìn)行劃分，克服了初始階段K-means的盲目性，解決了K-means算法初始聚類中心敏感性問題，同時減少了迭代次數(shù)，提高了效率。而且模擬退火階段屬于橫向搜索，會得到相對較優(yōu)的聚類劃分，對收斂標(biāo)準(zhǔn)要求較低，減少了時間復(fù)雜度；K-means算法階段屬于縱向搜索，容易得到最優(yōu)的聚類劃分，但收斂標(biāo)準(zhǔn)要求較高。利用模擬退火算法得到的初始聚類中心接近最優(yōu)的聚類劃分，需要較少的迭代次數(shù)就能收斂，同時降低了K-means算法的時間復(fù)雜度。

四、實驗

（一）實驗環(huán)境。硬件環(huán)境：CPU為P4 2.4GHz，內(nèi)存為8GB，軟件Matlab7.0。數(shù)據(jù)采用KDD cup_99。

（二）學(xué)生成績數(shù)據(jù)描述。本實驗中進(jìn)行運算的數(shù)據(jù)來自廣西政法管理干部學(xué)院的教務(wù)系統(tǒng)，只選擇了信息工程系學(xué)生成績。將學(xué)生成績數(shù)據(jù)集分為150組，信息工程系總共有2個專業(yè)，這兩個專業(yè)一個是司法信息專業(yè)，還有一個是計算機網(wǎng)絡(luò)專業(yè)。平均每個專業(yè)有50個樣本，計算統(tǒng)計的四門學(xué)科為：C語言、VB、JAVAR，VB+SQL。為了方便數(shù)據(jù)處理，本次運算的滿分為10分。

表1 數(shù)據(jù)集截取片段示意圖

專業(yè) C VB JAVA VB+SQL

司法信息 6.2 8.2 5.5 3.0

司法信息 6.9 6.3 5.8 3.6

司法信息 4.8 7.3 4.2 3.6

司法信息 7.0 7.3 7.2 5.2

計算機網(wǎng)路 6.4 7.3 6.8 6.2

計算機網(wǎng)絡(luò) 6.9 6.8 7.2 6.2

計算機網(wǎng)絡(luò) 6.3 7.3 8.3 7.5

計算機網(wǎng)路 7.1 6.0 7.8 6.5

計算機網(wǎng)絡(luò) 8.2 6.8 8.0 7.3

（三）改進(jìn)K-means聚類解決學(xué)生成績挖掘問題的必要性。整體來看，對學(xué)生的成績處理比較容易，使用傳統(tǒng)的K-means聚類方法就能夠直接運算得到結(jié)論，但是實際運算的時候發(fā)現(xiàn)并非如此，主要歸結(jié)為如下原因：

1.傳統(tǒng)的K-means聚類方法中，初始值非常重要，但是要計算學(xué)生成績則很難找到一種合適的初始值選取方法。若是選擇的初始值數(shù)值有偏差的話，則很難通過傳統(tǒng)的K-means聚類方法得到最優(yōu)解，計算結(jié)果跟我們需要的存在差距。

2.因為學(xué)生的考試成績呈現(xiàn)出連續(xù)分布的規(guī)律，成績跨度大，樣本上數(shù)量多，使用傳統(tǒng)的K-means聚類方法難以分析這些數(shù)據(jù)。

3.雖然學(xué)生成績信息是很直觀，但是如何提取有用信息其實不是很容易。因為每一類學(xué)生中都存在著至少一名學(xué)生，這些學(xué)生的成績有可能很好，也有可能很差，在而分析成績的好壞不屬于唯一信息。

上述實驗結(jié)果可以幫助我們印證本文的分析結(jié)論：傳統(tǒng)的K-means聚類方法分析學(xué)生的數(shù)據(jù)能力較差，分析結(jié)果不是很理想，因此使用改進(jìn)K-means聚類算法能夠提高結(jié)果的準(zhǔn)確性，對我們分析學(xué)生成績數(shù)據(jù)很有幫助，同時能夠克服局部最優(yōu)值的影響，從而更加接近全局最優(yōu)解。

（四）算法評價標(biāo)準(zhǔn)。本文從多個角度作為切入點，來探討改進(jìn)K-means聚類算法的質(zhì)量，首先我們使用Purity方法評估改進(jìn)K-means聚類算法的正確率。

Purity方法是一種效率高、運算簡單的方法，其運算理念如下：

這里的含義是改進(jìn)K-means聚類算法的聚類集合，的含義是第k個聚類集合。而代表的是改進(jìn)K-means聚類算法的樣本集合，Cj代表的是第j個樣本。上述體系中，N代表的是樣本總數(shù)。

比如，我們計算得到的最優(yōu)解數(shù)值為，而系統(tǒng)輸出的聚類結(jié)果為，這樣推算得到的分類正確的個體數(shù)值為1、2、5、7、8，這樣可以推算得到正確率為（5/8=）62.5%。

Purity方法的優(yōu)點在于操作方便，其數(shù)值在0-100%之間波動：若是結(jié)果完全錯誤，則Purity方法數(shù)值為0；若是結(jié)果完全正確，則Purity方法數(shù)值為100%。因此，Purity方法得出的結(jié)果簡單明了，方便將這些結(jié)果進(jìn)行比較，但是Purity方法的缺陷也是很明顯的，使用該種方法聚類比較分散，因此得到的Purity數(shù)值一般都比較高，比如本次樣本中的學(xué)生成績，若是使用Purity方法還是比較可靠的。

其次，我們還得到了適應(yīng)度函數(shù)Min-Jd，能夠看出系統(tǒng)的收斂性是多少。

此外，使用收斂曲線衡量收斂速度。曲線比較陡峭，則表示系統(tǒng)的收斂速度也就越好，計算效果也越好。

（五）實驗結(jié)果及結(jié)論。在分析學(xué)生成績之前，現(xiàn)將學(xué)生的成績按照考試科目分為若干個類簇，接著使用模擬退火的K-means聚類算法提高算法的穩(wěn)定性，歸納出每個學(xué)科的特點，這樣有利于提高運算效率，還有利于提高運算結(jié)果的正確率。

在該類方法中，T0設(shè)置為Jd，而a=0.99。

表2 兩種算法數(shù)值對比結(jié)果

聚類算法 聚類正確率（Purity） Min-Jd

傳統(tǒng)K-means算法 64.0000% 142.5174

模擬退火K-means 77.5000% 113.1462

其正確率和Min-Jd結(jié)果如表2。

圖1 兩種K-means算法聚類正確率對比

圖2 兩種算法的適應(yīng)度函數(shù)對比

經(jīng)過上述分析我們發(fā)現(xiàn)，傳統(tǒng)的K-means算法效果不是很好，正確率不高，而使用了改進(jìn)的K-means算法之后，正確率提高到了77.5%，Min-Jd從約142.5降到了約113.1。

為了更好地評估這兩種算法的效果，我們繪制了收斂曲線，用來評估兩種算法的科學(xué)性。

圖3 兩種聚類方法的收斂曲線對比

從收斂效果曲線我們發(fā)現(xiàn)，兩種算法中，模擬退火的K-means聚類算法收斂性要更好一些。

著眼于學(xué)生成績信息的挖掘，在實際學(xué)生成績信息數(shù)據(jù)評估中，使用模擬退火的K-means聚類算法進(jìn)行聚類。仿真實驗采用實際的學(xué)生成績數(shù)據(jù)信息。不同程度上改進(jìn)了傳統(tǒng)K-means聚類方法的性能，而且基于模擬退火的K-means聚類算法優(yōu)勢也很明顯：運算簡單，適用范圍廣。

五、小結(jié)

本文對模擬退火算法和K-means聚類方法進(jìn)行了詳細(xì)的總結(jié)，并歸納總結(jié)了所有關(guān)于模擬退火的K-means聚類算法的資料，提出了現(xiàn)有研究的不足，并根據(jù)現(xiàn)實提出了改進(jìn)措施。本次研究的模擬退火的K-means聚類算法要比傳統(tǒng)算法更有優(yōu)勢，科學(xué)合理，適用范圍更廣，能夠科學(xué)地體現(xiàn)出學(xué)生對課程的掌握程度，教師也可以根據(jù)評估結(jié)果，查看學(xué)生的薄弱點，改進(jìn)教學(xué)方法。

但是，隨著大數(shù)據(jù)時代的到來，云計算登上了歷史的舞臺，而計算功能也變得日益強大，在這種運算背景下，支持種群規(guī)模也變得日益強大，迭代次數(shù)也提高了很多。在運算能力越來越強的時代中，如何結(jié)合云技術(shù)、并行計算技術(shù)，設(shè)計出一個合理的聚類方法，讓數(shù)據(jù)運算能力大大提高，解決我們切實需要的問題，是未來研究發(fā)展趨勢，也是現(xiàn)在討論的最熱門的一個話題。

【參考文獻(xiàn)】

[1]梅方權(quán).中國農(nóng)業(yè)信息化建設(shè)的前景展望[J].計算機與農(nóng)業(yè)，1997（3）

[2]Wikipedia：K-means clustering[EB/OL].https：//en.wikipedia.org/wiki/K-means_clustering

[3]楊忠明，黃道，王行愚.基于模擬退火的動態(tài)聚類算法[J].控制與決策，1997（12）

[4]李健，宋立新.模擬退火改進(jìn) K 均值算法在鏡頭聚類中的應(yīng)用[J].哈爾濱理工大學(xué)學(xué)報，2010（6）

[5]陳慧萍，賀會景，陳嵐峰，等.基于模擬退火思想的優(yōu)化 k-means 算法[J].河海大學(xué)常州分校學(xué)報，2006（4）

[6]陳明，王行風(fēng)，韓冰，等.基于模擬退火的k-means分類算法優(yōu)化研究[EB/OL].（2011-08-27）[2016-01-01]. http：//www.paper.edu.cn/html/releasepaper/2011/08/277/

[7]史峰，王輝，胡斐，等.智能算法[M].北京：北京航空航天大學(xué)出版社，2011

[8]劉劍.改進(jìn)聚類分析算法及其在成績分析中的應(yīng)用研究[D].大連：大連交通大學(xué)，2008

[9]Anil K J.Data clustering：50 years beyond K-Means[J].Pattern Recognition Letters，2010（8）

[10]劉寒梅，張鵬.基于模擬退火算法對 K-means 聚類算法的優(yōu)化[J].中國西部科技，2013（6）

[11]胡艷維，秦拯，張忠志.基于模擬退火與 K 均值聚類的入侵檢測算法[J].計算機科學(xué)，2010（6）

[12]李健，宋立新.模擬退火改進(jìn) K 均值算法在鏡頭聚類中的應(yīng)用[J]，哈爾濱理工大學(xué)學(xué)報，2010（6）

[13]李梓，于海濤，賈美娟.基于改進(jìn)模擬退火的優(yōu)化K-means算法[J]，計算機工程與應(yīng)用，2012（24）

[14]陶術(shù)松，陳興蜀，尹學(xué)淵.基于數(shù)據(jù)挖掘的未知幀結(jié)構(gòu)識別[J].四川大學(xué)學(xué)報（工程科學(xué)版），2014（S1）

【基金項目】廣西重點研發(fā)計劃項目“基于北斗多功能信息采集與監(jiān)控終端的智能物流管理系統(tǒng)研發(fā)”（桂科AB16380351）；2016年廣西教育廳教學(xué)改革立項項目“基于翻轉(zhuǎn)課堂的C語言教學(xué)探索與研究”（GXGZJG2016B097）；國家自然基金：廣西職業(yè)教育教學(xué)改革立項項目“基于增強現(xiàn)實與3D打印信息技術(shù)的職業(yè)教育人機互動教學(xué)模式研究”（JG15B09）

【作者簡介】左倪娜（1983— ），女，碩士，廣西政法管理干部學(xué)院信息工程系講師，研究方向：計算機軟件編程及大數(shù)據(jù)分析。

（責(zé)編 王 一）