基于遺傳算法的學生信息關聯規則挖掘研究

摘要：該文結合具體的學生信息數據庫，把遺傳算法理論應用到關聯規則的數據挖掘中。通過特定的編碼設計，適應度函數構造，數據庫處理，遺傳算法的參數設置，得到有用的規則，有助于教師對學生的科學管理和指導，提高教學的質量和素質，為其余課程或學生數據庫的挖掘起到拋磚引玉的作用。

關鍵詞：數據挖掘；遺傳算法；關聯規則

中圖分類號：TP18文獻標識碼：A文章編號：1009-3044(2008)34-1747-02

Mining Students Information with Association Rules Based on Genetic Algorithm

CHEN Jian-cheng1，2， TU Ang-yan3， XU Xue-gui2

(1.Software Institute of Tongji University， Shanghai 200092， China; 2. Department of Computer， Zhejiang Industry Polytechnic College， Shaoxing 312000， China; 3. Center of Computer， Shaoxing University， Shaoxing 312000， China)

Abstract: This paper describes the application of genetic algorithms to the data mining association rules with specific student information database. Through specific coding design， structuring fitness function， processing database， setting genetic algorithm’s parameters，many useful rules are found. This helps teachers manage and guide students scientifically. It can improve the quality of teaching and the accomplishs， and play the roles of using the little to get the big for the other courses or students database mining.

Key words: data mining; genetic algorithm; association rule

1 引言

遺傳算法在解決問題時以混沌、隨機和非線性為典型特征，為其他科學技術或難以解決的復雜問題提供新的計算模型。遺傳算法是有效解決大量數據中嘈雜無序的特征的有效方法之一。遺傳算法是模擬自然進化的通用全局搜索算法，避免了搜索過程中局部最優解，用在規則發現方面，有希望發現真正有用的規則。

關聯規則Apriori算法的核心思想是發現最大項目集，這個過程是全局的搜索過程，而遺傳算法是一種全局最優算法，將遺傳算法用在規則的發現和提取方面能夠發現真正有用的規則。本文將遺傳算法應用到關聯規則的提取方面，結合具體的學生成績數據庫系統的應用實例，將常見的二進制編碼轉換為實數編碼，對適應度函數進行構造，得到一些有用的規則，并將其應用于學生的培養和教育，便于教師有針對性地對學生進行科學的管理和指導，有助于科學教學及今后的教改方向，從而提高教學質量和教師素養。

2 遺傳算法中的個體表示

2.1 編碼方法

應用遺傳算法進行規則開采，編碼是要首先解決的問題，也是遺傳算法的關鍵步驟，直接影響遺傳算法的運行效率。

實數數組的元素個數與事務數據庫中的字段個數對應，實數數組的元素值則代表了字段的屬性值，如表1所示。

用一個元組為N的數組來表示如表1所示的個體編碼，A[1]表示字段A，A[2]表示字段B，……，A[N]表示字段N；各屬性值用數值型的值表示，各字段的屬性值在各自不同的范圍內取值，如字段A的屬性值在[A1，AL1]之間取值，字段B的屬性值在[B1，BL2]之間取值，……，字段N的屬性值在[N1，NLN]之間取值。由于處理后的數據庫的屬性值大于零，則用與所在字段的屬性值的編碼長度等長的由“0”組成的字符串表示，表示此屬性與其他的屬性無關聯。

表1所示的數據庫的個體編碼如下所示：

■

用實數編碼，不僅編碼簡單、易于實現，而且也便于遺傳算子的操作，編碼后的遺傳算子的操作變成了對數組的操作。

2.2 適應度函數的構造

適應度函數是遺傳操作中進行選擇操作的唯一依據，使算法避免了隨機的盲目搜索，它的設計好壞直接影響GA的性能和效率。關聯規則中支持度的大小衡量了規則的重要性，支持度越大，規則越重要，反之，規則不重要?？尚哦仁菍﹃P聯規則準確度的衡量，對可信度很高而支持度很低的關聯規則，由于該規則使用的機會很少而顯得不重要。因此，在適應度函數的構造中，采用這樣的方法：先根據支持度篩選規則，再在滿足最小支持度的規則中確定它的關聯程度和關聯性。適應度函數的形式定義如下所示：

■

其中，s'為經過GA形成的一條新規則的支持度，s為用戶給定的支持度的閾值，當ri為符合要求的規則時，它的適應度函數值大于1，值Vs表示被選中，否則在下一代中規則造淘汰，用Vd表示。

3 應用實例

3.1 數據庫的數據處理

本文采用的是學生信息數據庫。數據庫的各字段說明如表3所示。

學年的取值范圍為[1，4]，分別表示大一、大二、大三和大四四個年級，性別編碼，男：1，女：2，添加科目性質一列：屬性值為：偏文用1表示，中性用2表示，偏理用3表示，偏藝術（如健美操、演奏系列、繪畫系列）用4表示。

3.2 遺傳算法中的參數設置

GA中需要選擇的運行參數主要有個體編碼串的長度L、群體大小M、交叉概率Pc、變異概率Pm、終止代數T等。這些參數設置對算法的運行性能影響較大，下面進行具體分析：

1) 編碼串長度L。編碼的長度與所用的編碼的方法有關。本文使用的是浮點數編碼，編碼串長度L與決策變量的個數相等。在本文中，我們要找的是表2中的八個字段之間的關聯，編碼的長度為8。

2) 群體的大小M。群體的大小M對算法的影響很大，若 M 較小，雖可提高遺傳算法的運算速度，卻降低了群體的多樣性，會引起早熟現象的發生；相反M的值較大，則遺傳算法的運行效率降低。權衡利弊，且本例有的決策變量的取值范圍很大，因此初始種群的個數取100。

3) 交叉概率Pc。交叉操作是遺傳算法中產生新個體的主要方法，交叉概率取值過大會破壞群體中的優良模式，對進化運算不利；取值過小，產生新個體的速度減慢。在本例中，有的決策變量的取值范圍很大，把交叉概率取較大的值0.8。

4) 變異概率Pm。變異使得群體保持它的多樣性，變異概率取值過大，雖能夠產生較多的新個體，可能會破壞優良的模式，使得遺傳算法的性能近似于隨機搜索算法的性能；取值過小，無法保持群體的多樣性，且易出現早熟現象。與前面參數類似，考慮到有的決策變量的取值范圍很大，變異概率取較大的值為0.05。

5) 終止代數T。終止代數是GA運行到指定的進化代數之后停止運行，將當前群體的最佳個體作為最優解輸出，是GA運行結束條件的一個參數。在本例中，求的是滿足用戶給定閾值的規則，最后輸出的解是一個符合要求的規則的集合，根據適應度函數以及遺傳算子選擇出的規則表示的是所有具有關聯性的屬性，但無法分辨出具體是如何關聯的。但包含的所有規則中未必每條規則符合可信度要求，因此需對規則進行篩選，對符合最低可信度閾值的規則輸出，否則丟棄。

3.3 算法設計

利用下面的算法對數據庫的數據進行規則提取：

Step1：初始化的過程包括下列兩個過程：

隨機生成一個初始群體P={a1，a2，…，am}；(m=100)

獲取用戶給定的支持度s，可信度c；

Step2：對當前種群P中的每一個個體計算適應度值，f(ai)=s'/s(i=1，2，…，m)；根據適應度值對個體進行篩選，若f(ai)>0則保留該規則進入下一代，否則刪除并淘汰該規則，并計算保留下來的個體數n。

n=0(初始化)

For i=1 to m do

If f(ai)>0 then

n=n+1

reserve 該規則

else

discard 該規則

end if

end for；

Step3: if n < m then

隨機生成m-n個個體

else

跳過Step3這一步

end if

Step4: 初始化交配池pond和后代offspring（下轉第1754頁）

（上接第1748頁）

pond=Ф

offspring=Ф

Step5:復制

For i =1 tomdo

pond=pond ∪ ai(將當前種群中的所有個體復制到交配池)

End for

Step6: 交叉

For i =1 tom/2do

隨機地從交配池pond中選擇兩個個體aid和aim作為父本和母本，按照交叉概率Pc進行交叉

pond=pond –{aid，aim}

offspring=Offspring ∪{ aid，aim按照交叉概率Pc交叉的后代}

End for

Step7: 變異：在當前種群中按照變異概率Pm選擇Pm×m個個體進行變異操作。

Step8: 終止條件判定：

與終值代數T進行比較，若符合終止條件，則終止并輸出最優解，否則跳到Step2。

Step9: 進行規則提取。

3.4 結論

根據以上算法，在上述的學生數據庫中發現部分關聯規則如下：

<0108700>?圯<60001>（1.30%support，2.33%confidence）

<0108700>?圯<50001>（1.30%support，62.79%confidence）

<0108700>?圯<40001>（1.30%support，30.23%confidence）

<0108700>?圯<20001>（1.30%support，0%confidence）

<0108700>?圯<60009>（1.30%support，0%confidence）

<0108700>?圯<50009>（1.30%support，62.16%confidence）

<0108700>?圯<40009>（1.30%support，37.84%confidence）

<0108700>?圯<20009>（1.30%support，0%confidence）

規則表明偏文（編碼為1）的課程鄧小平理論（課程編碼為87），文科班中文師范00級01班（班級編碼為01），優秀（編碼為6）為2.33%，良好（編碼為5）為62.79%，中等（編碼為4）30.23%；理科班數學教育00級02班（班級編碼為09），優秀為0%，良好為62.16%，中等為37.84%，兩個班不及格均為0%情況。

對偏文的課程，文科班的成績相對好一些，但并不突出，這里需要說明的是雖然是同一偏文的課程，但考試的要求并不同，文科班的要求較高一些，考試的難度相對高一些。對中性科目文科班的成績較理科班的成績有很大的突出。

4 小結

本文結合學生信息數據庫對關聯規則的挖掘算法進行了探討，提出將遺傳算法應用于關聯規則的提取。使用了實數數組的編碼方法，方便了交叉、變異和選擇算子的操作；根據不同的專業性質、年級、科目性質、課程、選修情況、學分、性別與成績的關系，對學生成績數據庫進行數據挖掘，發現有用的知識，用同樣的方法，對不同內容的學生資料數據庫進行關聯規則的數據挖掘，并把它們應用到學生的培養和教育上去，教師可以根據各種題型的失分多少發現學生的薄弱環節，從而加強薄弱環節的教育；發現某些基礎學科和另外一些難度較大的學科的關聯性，通過加強某些基礎學科的教學來提高另外一些難度較大的學科的學習成績，這有助于教師對學生的科學管理，進行有針對性地科學指導，提高教學的質量和素質；可以根據某些課程的優秀情況判斷學生以后的就業去向，從而加強某些課程的教育。

參考文獻：

[1] Davis L.Handbook of genetic algorithms[M].New York:Van Nostrand，1991.

[2] 陳明，王靜，沈理.基于遺傳算法的Fuzzy規則自動獲取的研究[J].軟件學報，2000，11(1):85-90.

[3] 遺傳學編寫組.遺傳學[M].北京:中國大百科全書出版社，1983.

[4] 王小平，曹立明，著.遺傳算法——理論、應用與軟件實現[M].西安:西安交通大學出版社，2002.

[5] 唐飛，滕弘飛，孫治國，等.十進制編碼遺傳算法的模式定理研究[J].小型微型計算機系統，2000，21(4):364-367.