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

薛景

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

關(guān)鍵詞： 蟻群； 聚類(lèi)分析； 成績(jī)?cè)u(píng)價(jià)

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

1 問(wèn)題提出

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

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

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

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

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

2 帶有記憶的蟻群聚類(lèi)算法

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

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

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

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

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

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

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

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

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

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

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

For j=1，2，…，N

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

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

如一個(gè)數(shù)據(jù)對(duì)象的鄰域個(gè)數(shù)小于某個(gè)常數(shù)，則記為孤立點(diǎn)；否則，給該數(shù)據(jù)對(duì)象和其領(lǐng)域?qū)ο蠓峙湎嗤木垲?lèi)序列號(hào)。

3 實(shí) 驗(yàn)

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

傳統(tǒng)的學(xué)生成績(jī)標(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ù)考試成績(jī)作為數(shù)據(jù)樣本，按照傳統(tǒng)等級(jí)標(biāo)準(zhǔn)進(jìn)行統(tǒng)計(jì)，結(jié)果轉(zhuǎn)換成折線圖，如圖2所示。

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

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

4 結(jié) 論

本文在標(biāo)準(zhǔn)蟻群聚類(lèi)算法的基礎(chǔ)上，提出了優(yōu)化算法。經(jīng)實(shí)驗(yàn)驗(yàn)證，相對(duì)于傳統(tǒng)的評(píng)價(jià)標(biāo)準(zhǔn)，改進(jìn)后的聚類(lèi)結(jié)果呈正態(tài)分布趨勢(shì)，更符合實(shí)際的應(yīng)用情況。聚類(lèi)所得的評(píng)價(jià)結(jié)果，也可為教學(xué)人員制定有針對(duì)性的教學(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] 姜云龍. 面向日志分類(lèi)的蟻群聚類(lèi)算法研究[D]. 上海：華東理工大學(xué)，2014.

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

[5] 周穎. 基于蟻群算法的聚類(lèi)分析在學(xué)生成績(jī)中的研究[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é)任編輯：徐興華）