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

【關鍵詞】模擬退火算法 數據挖掘 K-means聚類 學生成績

【中圖分類號】G 【文獻標識碼】A

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

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

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

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

一、模擬退火算法概述

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

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

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

二、聚類

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

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

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

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

三、改進模擬退火算法在K-means聚類中的應用

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

（一）目標函數。根據誤差平方和準則函數JC，就能夠將聚類進行劃分，將其劃分為離散距離和Js，而公式表示如下：

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

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

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

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

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

改進K-means聚類算法的過程如下：

1.使用K-means聚類算法進行聚類分析，得到一系列的結果，將這個結果當作初始解，這樣可以得到目標函數值。

2.將本次運算中的溫度初始化成為目標函數值。

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

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

5.計算兩個函數之間的差值。

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

7.結束運算。

算法描述如下：

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

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

1 初始化：

T0=Jd；

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

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

S=a（PN）；

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

2 改進模擬退火算法獲取初始聚類中心：

While（100*n>0）

Begin

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

begin

num=0；

while（num

Begin

選取離聚類中心最遠的實體，重新劃分，得到新的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）； //更新聚類中心

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

四、實驗

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

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

表1 數據集截取片段示意圖

專業(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

計算機網路 6.4 7.3 6.8 6.2

計算機網絡 6.9 6.8 7.2 6.2

計算機網絡 6.3 7.3 8.3 7.5

計算機網路 7.1 6.0 7.8 6.5

計算機網絡 8.2 6.8 8.0 7.3

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表2 兩種算法數值對比結果

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

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

模擬退火K-means 77.5000% 113.1462

其正確率和Min-Jd結果如表2。

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

圖2 兩種算法的適應度函數對比

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

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

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

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

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

五、小結

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

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

【參考文獻】

[1]梅方權.中國農業(yè)信息化建設的前景展望[J].計算機與農業(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]李健，宋立新.模擬退火改進 K 均值算法在鏡頭聚類中的應用[J].哈爾濱理工大學學報，2010（6）

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

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

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

[8]劉劍.改進聚類分析算法及其在成績分析中的應用研究[D].大連：大連交通大學，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].計算機科學，2010（6）

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

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

[14]陶術松，陳興蜀，尹學淵.基于數據挖掘的未知幀結構識別[J].四川大學學報（工程科學版），2014（S1）

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

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

（責編 王 一）