一種蟻群聚類優(yōu)化算法在成績管理中的應(yīng)用

薛景

摘 要： 學(xué)生成績是評價學(xué)生是否掌握好所學(xué)知識的重要指標(biāo)。傳統(tǒng)的方法是基于絕對分?jǐn)?shù)的評價，這種方法存在一定的缺陷，不能充分反映學(xué)生原始成績中蘊(yùn)涵的信息。本文提出了一種蟻群聚類優(yōu)化算法，并用于高職高專的信息技術(shù)課程成績管理當(dāng)中。旨在挖掘成績背后的信息，供教學(xué)參考，教務(wù)支持。

關(guān)鍵詞： 蟻群； 聚類分析； 成績評價

中圖分類號： TP391 文獻(xiàn)標(biāo)志碼： A 文章編號： 1671-2153（2016）05-0095-03

1 問題提出

隨著蟻群算法研究的不斷深入，人們發(fā)現(xiàn)在某些方面采用蟻群模型進(jìn)行聚類分析會更接近于實際的聚類問題。通過模擬蟻群的行為，人們提出了很多基于蟻群的聚類分析模型[1]。Lumer和Faieta將蟻群聚類的基本模型推廣應(yīng)用到數(shù)據(jù)分析，提出了LF算法[2]。作為蟻群聚類算法的標(biāo)準(zhǔn)算法，LF算法在很多領(lǐng)域得到了廣泛的應(yīng)用。

在傳統(tǒng)的LF算法中，未搬運(yùn)東西的螞蟻碰到對象時會以某個概率拾起它，而帶有對象的螞蟻遇到空單元時會以某個概率放下它。拾起和放下行為均依賴于當(dāng)前對象和其領(lǐng)域?qū)ο笾g的相似度。數(shù)據(jù)對象在空間的分布狀態(tài)將影響聚類結(jié)果[3]。

傳統(tǒng)的LF算法中容易遇到以下問題：

（1）螞蟻在二維平面上的運(yùn)動是完全隨機(jī)的，如果運(yùn)動到無對象區(qū)域，則無太大意義；并且當(dāng)蟻群規(guī)模較大時，對象很難在較短時間內(nèi)找到合適的鄰域，導(dǎo)致聚類效果不準(zhǔn)確或不明顯。

（2）該算法容易出現(xiàn)停滯現(xiàn)象，即迭代到了一定程度后，可能出現(xiàn)局部最優(yōu)解，導(dǎo)致更合適的對象不能被拾起。

2 帶有記憶的蟻群聚類算法

基于上述問題，本文提出了一種蟻群聚類優(yōu)化算法。與傳統(tǒng)LF算法的區(qū)別主要有以下兩點。

區(qū)別之一是，通過建立“歷史位置記憶庫”，記錄所有螞蟻放下數(shù)據(jù)的位置，供所有的螞蟻進(jìn)行比較。初始時“歷史位置記憶庫”中內(nèi)容為空，螞蟻走完一步或經(jīng)歷一條完整路徑后，要對記憶庫進(jìn)行更新處理。這樣經(jīng)過不斷的迭代更新，蟻群最終會找到最優(yōu)路徑[4]。通過設(shè)置“歷史位置記憶庫”，可以減少螞蟻運(yùn)動中的隨機(jī)性，從而達(dá)到縮短搜索時間，提高聚類效率的目的。

鑒于原函數(shù)中當(dāng)對象Oi和Oj水平偏離很大時，d（Oi，Oj）不能很好的反映出真實的相似度，所以調(diào)整后函數(shù)中設(shè)置了參數(shù)μ，μ為全部對象歐氏空間距離的平均值，d（Oi，Oj）/μ則反映了對象Oi和Oj相對于總體空間距離的偏離程度。通過此調(diào)整，以期改進(jìn)原函數(shù)中存在的問題。

改進(jìn)后的算法流程圖如圖1所示。

改進(jìn)后的算法描述如下：

輸入：待聚類的數(shù)據(jù)集。

輸出：聚類結(jié)果。

（1）初始化蟻群，螞蟻數(shù)記為N，最大迭代次數(shù)記為M。

（2）將所有待聚類的數(shù)據(jù)隨機(jī)分配到二維網(wǎng)格單位中。

（3）初始時，螞蟻空載，隨機(jī)選擇一個數(shù)據(jù)對象，并初始化“歷史位置記憶庫”，置為空。

（4）For i=1，2，…，M

For j=1，2，…，N

計算數(shù)據(jù)的平均相似性：

以一只螞蟻為例，計算拾起概率PP。若PP大于隨機(jī)概率，則螞蟻拾起數(shù)據(jù)，并將自身的狀態(tài)記為負(fù)載；若PP小于隨機(jī)概率，則隨機(jī)選擇另一個數(shù)據(jù)對象。將螞蟻拾起的數(shù)據(jù)與“歷史位置記憶庫”中的數(shù)據(jù)進(jìn)行比較，計算放下概率Pd，若Pd小于隨機(jī)概率，則隨機(jī)選擇一個無數(shù)據(jù)的網(wǎng)格單位，繼續(xù)判斷若Pd小于隨機(jī)概率，直至最終放下數(shù)據(jù)，更新“歷史位置記憶庫”，螞蟻狀態(tài)記為卸載。

如一個數(shù)據(jù)對象的鄰域個數(shù)小于某個常數(shù)，則記為孤立點；否則，給該數(shù)據(jù)對象和其領(lǐng)域?qū)ο蠓峙湎嗤木垲愋蛄刑枴?/p>

3 實 驗

學(xué)生成績在整個教學(xué)管理活動中，起著很好的指示作用[5]。本文選擇揚(yáng)州市職業(yè)大學(xué)2015級105名學(xué)生的信息技術(shù)課程成績進(jìn)行聚類分析。該課程屬于高職高專院校的公共課課程，考試采用機(jī)考，考試題型和分值設(shè)置如下：第一項，選擇題和填空題50題，計50分；第二項，操作題，主要是WORD，EXCEL，POWERPOINT三個軟件的實際操作，計50分，滿分100分。部分?jǐn)?shù)據(jù)樣本如表1所示。

傳統(tǒng)的學(xué)生成績標(biāo)準(zhǔn)主要是根據(jù)分?jǐn)?shù)線進(jìn)行劃分。90～100分為優(yōu)秀，80～90分（不含90）為良好，70～80分（不含80）為中等，60～70分（不含70）為及格，0～60分（不含60）為不及格。

先將105學(xué)生的信息技術(shù)考試成績作為數(shù)據(jù)樣本，按照傳統(tǒng)等級標(biāo)準(zhǔn)進(jìn)行統(tǒng)計，結(jié)果轉(zhuǎn)換成折線圖，如圖2所示。

由圖2可以看出，成績分布沒有呈正態(tài)分布，優(yōu)秀和良好比率較低，說明本次考試對學(xué)生而言難度較大。再將105名學(xué)生的成績數(shù)據(jù)作為輸入，使用改進(jìn)的蟻群聚類算法進(jìn)行聚類，進(jìn)行多次聚類后，結(jié)果如表2所示。在表2的基礎(chǔ)上，將最后的四類歸并，歸類后的統(tǒng)計結(jié)果，如圖3所示。

根據(jù)圖3的折線圖可看出，學(xué)生成績的分布基本呈正態(tài)分布趨勢，即兩頭低，中間高，左右基本對稱。這樣的聚類模型更加符合實際情況。

4 結(jié) 論

本文在標(biāo)準(zhǔn)蟻群聚類算法的基礎(chǔ)上，提出了優(yōu)化算法。經(jīng)實驗驗證，相對于傳統(tǒng)的評價標(biāo)準(zhǔn)，改進(jìn)后的聚類結(jié)果呈正態(tài)分布趨勢，更符合實際的應(yīng)用情況。聚類所得的評價結(jié)果，也可為教學(xué)人員制定有針對性的教學(xué)策略提供有利的依據(jù)。

參考文獻(xiàn)：

[1] HOE KM，LAIWK，TAIT S. Homogenous ants for documents similarity modeling and categorization. Proceedings of the 3th International Workshop on Ant Algorithms[C]. LNCS，2002：256-261.

[2] WU B，SHI Z. A clustering algorithm based on swarm intelligence[A]//Proceedings IEEE international conferences on info-tech & info-net proceeding[C]. Beijing，2001：58-66.

[3] 姜云龍. 面向日志分類的蟻群聚類算法研究[D]. 上海：華東理工大學(xué)，2014.

[4] 段海濱. 蟻群算法原理及其應(yīng)用[M]. 北京：科學(xué)出版社，2005：34-35.

[5] 周穎. 基于蟻群算法的聚類分析在學(xué)生成績中的研究[D]. 南昌：南昌大學(xué)，2015.

Abstract： Student achievement is an important indicator to evaluate whether students master the knowledge they have learned. Traditional approach is based on the absolute scores of the evaluation， this method has some shortcomings， does not fully reflect the achievements of students in the original implication of information. This paper presents an ant colony clustering algorithm， which is used in the management of information technology course in higher vocational colleges.Aims to dig the information behind the results for teaching reference， academic support.

Keywords： cluster analysis； ant algorithm； performance evaluation

（責(zé)任編輯：徐興華）