張硯雪

摘要：隨著數(shù)據(jù)挖掘技術(shù)的興起，各種應(yīng)用于關(guān)聯(lián)規(guī)則挖掘的算法也逐漸被關(guān)注。在數(shù)據(jù)庫中除了能對數(shù)據(jù)的進(jìn)行錄入、查詢、統(tǒng)計(jì)等簡單功能應(yīng)用，也能幫助用戶發(fā)現(xiàn)大量數(shù)據(jù)中存在的各種有用的信息以及數(shù)據(jù)之間的關(guān)聯(lián)性，幫助用戶分析出其中有價(jià)值的信息，從而實(shí)現(xiàn)其中的商業(yè)價(jià)值。關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘領(lǐng)域的一個(gè)重要研究分支，其經(jīng)典算法-Aprior算法被廣泛采用，本文針對Aprior算法的局限性，將遺傳算法應(yīng)用在關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘中進(jìn)行分析并以某高校新生入學(xué)調(diào)查表中數(shù)據(jù)為例，挖掘出學(xué)校的環(huán)境、就業(yè)情況、校園社團(tuán)活動(dòng)、食堂用餐標(biāo)準(zhǔn)等因素與學(xué)生生源地情況及學(xué)生中學(xué)水平之間的相關(guān)聯(lián)系，可以幫助高校在招生咨詢和宣傳中有所側(cè)重，對不同地區(qū)的學(xué)生采取不同的宣傳方式和宣傳內(nèi)容，來進(jìn)一步擴(kuò)大學(xué)校的招生規(guī)模。

關(guān)鍵詞：遺傳算法；數(shù)據(jù)挖掘；關(guān)聯(lián)規(guī)則；招生宣傳

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2015）15-0181-02

Abstract： With the rise of data mining technology， various applied to association rule mining algorithms have gradually been concerned. In addition to the data in the database will be entry， query， statistics and other simple functional applications， but also to help users find the relevance of the presence of large amounts of data in a variety of useful information and data between， to help users analyze the valuable information， in order to achieve one of the commercial value. Association rules is an important research branch of data mining， which is the classical algorithm -Aprior algorithms are widely used， the limitations of this article for Aprior algorithm， genetic algorithm in association rule data mining for analysis and survey of a university freshmen the data， for example， to dig out the relevant contact the school environment， employment， campus community activities， canteen standards and other factors with students and student high school students to the situation between the level that can be focused on helping college admissions consulting and publicity for students in different regions to take a different form of publicity and promotional content， to further expand the enrollment of the school.

Key words： Genetic Algorithms；Data Mining；Association Rule；Admissions publicity

1 引言

1.1 數(shù)據(jù)挖掘

數(shù)據(jù)挖掘技術(shù)一般是指從海量數(shù)據(jù)中自動(dòng)搜索隱藏于其中的有著特殊關(guān)聯(lián)性的信息的過程。主要有數(shù)據(jù)準(zhǔn)備、規(guī)律尋找和規(guī)律表示3個(gè)步驟。數(shù)據(jù)挖掘的任務(wù)有關(guān)聯(lián)規(guī)則分析、分類分析、聚類分析、異常分析、特異群組分析以及演變分析等。其中的關(guān)聯(lián)規(guī)則分析具有很多商業(yè)價(jià)值，被廣泛的研究和應(yīng)用。

1.2 關(guān)聯(lián)規(guī)則

關(guān)聯(lián)規(guī)則是數(shù)據(jù)庫中存在的一類重要的可被發(fā)現(xiàn)的知識。如果兩個(gè)或多個(gè)變量的取值之間存在某些規(guī)律性，就稱為關(guān)聯(lián)。關(guān)聯(lián)分為簡單關(guān)聯(lián)、時(shí)序關(guān)聯(lián)和因果關(guān)聯(lián)。關(guān)聯(lián)規(guī)則分析的目的是找出數(shù)據(jù)庫中隱藏的關(guān)聯(lián)性。人們有時(shí)并不知道數(shù)據(jù)庫中數(shù)據(jù)的關(guān)聯(lián)函數(shù)，因此關(guān)聯(lián)分析生成的規(guī)則帶有一定可信度。關(guān)聯(lián)規(guī)則挖掘發(fā)現(xiàn)海量數(shù)據(jù)中屬性之間有趣的關(guān)聯(lián)或一定規(guī)律。

1.3 遺傳算法

遺傳算法是計(jì)算數(shù)學(xué)中用于解決最佳化的一種進(jìn)化算法。進(jìn)化算法最初是能過研究了進(jìn)化生物學(xué)中的一些現(xiàn)象而發(fā)展起來的，這些現(xiàn)象包括了遺傳、突變、自然選擇以及雜交等。遺傳算法一般用一種計(jì)算機(jī)模擬來實(shí)現(xiàn)。對于某個(gè)最優(yōu)化問題，一定數(shù)量個(gè)體的抽象表示（稱為染色體）的種群向更優(yōu)的個(gè)體進(jìn)化。

2 基于遺傳算法的關(guān)聯(lián)規(guī)則挖掘

2.1 學(xué)生入學(xué)調(diào)查數(shù)據(jù)進(jìn)行遺傳算法的編碼方法

行遺傳算法編碼是應(yīng)用遺傳算法時(shí)要解決的主要問題，也是設(shè)計(jì)遺傳算法的一個(gè)關(guān)鍵步驟。編碼方法選擇影響到交叉算子、變異算子等遺傳算子的運(yùn)算方法，在很大程度上決定了遺傳進(jìn)化的效率。時(shí)至今日人們已經(jīng)提出了許多種不同的編碼方法。本文采用實(shí)數(shù)數(shù)組的編碼方案，因?yàn)槠渚邆洳粌H簡單、通用、魯棒性強(qiáng)，適于并行分布處理等之外還方便了遺傳算子的操作。在采用數(shù)組編碼后的交叉、變異等操作實(shí)際上就成了對數(shù)組中數(shù)據(jù)進(jìn)行操作，在本文中，我們把學(xué)生調(diào)查情況全部讀入數(shù)據(jù)庫，對一些屬性進(jìn)行合并，并適當(dāng)對一些屬性進(jìn)行刪除，重新建立了一個(gè)學(xué)生基本信息與學(xué)生調(diào)查信息數(shù)據(jù)庫，如下表所示：

由于采用的是實(shí)數(shù)數(shù)組編碼，其中一條規(guī)則就是一條實(shí)數(shù)編碼串，又分為兩個(gè)部分：規(guī)則的屬性部分和規(guī)則類別，比如1131240=>122，所以我們要將屬性值也用數(shù)值型來表示。例如如下幾個(gè)表。

學(xué)生所在中學(xué)性質(zhì)，分為兩種情況，普通高中，職業(yè)高中，分別為其編碼0，1。同時(shí)將分?jǐn)?shù)等級等其它特征進(jìn)行編碼，在這里不一一列表。

結(jié)論屬性表為分就業(yè)情況、校園環(huán)境、食堂消費(fèi)水平、專業(yè)設(shè)置、校園文化五個(gè)表，表3為就業(yè)率注重情況表。

經(jīng)過分析，編號和年齡屬性與我們發(fā)現(xiàn)的關(guān)聯(lián)知識沒有關(guān)系，而性別屬性也與我們發(fā)現(xiàn)的關(guān)聯(lián)知識相關(guān)度不大，因此我們省略不用。

2.2 遺傳算法的運(yùn)行參數(shù)設(shè)定

遺傳算法參數(shù)包括種群規(guī)模M、變量個(gè)數(shù)L、交叉概率Pc、變異概率Pm以及運(yùn)算的終止進(jìn)化代數(shù)T。參數(shù)的設(shè)定對算法的運(yùn)行性能有著很大的影響，所以取值一定要認(rèn)真。

2.2.1 種群規(guī)模M

種群規(guī)模M表示數(shù)據(jù)群體中所含調(diào)查個(gè)體的全部數(shù)量。其取值一定要適當(dāng)，當(dāng)數(shù)值太小時(shí)，遺傳算法的運(yùn)算速度提高了，但反映不出群體的多樣式，也推理不出有價(jià)值的結(jié)論，造成遺傳算法的早熟；而當(dāng)M的取值太大時(shí)，遺傳算法的運(yùn)行效率會相應(yīng)降低。所以，我們要綜合這兩個(gè)方面來考慮M的取值。本例中選取初始群體的規(guī)模為100.

2.2.2 變量個(gè)數(shù)L

變量個(gè)數(shù)與所用的編碼方法有關(guān)。本文采用的實(shí)數(shù)數(shù)組的編碼方案，變量個(gè)數(shù)等于數(shù)據(jù)庫中相關(guān)字段的數(shù)量。根據(jù)分析，我們設(shè)定變量個(gè)數(shù)L為10。

2.2.3 變異概率P1

變異概率決定了物種的多樣性。如果取值過大，有可能很多比較好的模式被破壞，使遺傳算法的性能于隨機(jī)搜索算法的性能類似；若取值過小，則變異操作產(chǎn)生新個(gè)體抑制遺傳算法早熟現(xiàn)象的能力會較差。本例中， P1取為0.04。

2.2.4 交叉概率P2

交叉概率的選取一般為較大的值?？墒侨绻^大，就會破壞群體中的優(yōu)良模式。若取值過小，產(chǎn)生新個(gè)體的速度就會變慢。在本例中我們?nèi)≈?.8。

2.2.5 終止代數(shù) T

終止代數(shù)T是指表示遺傳算法運(yùn)行結(jié)束條件的一個(gè)參數(shù)，它表示算法要進(jìn)行到滿足指定進(jìn)化代數(shù)后就停止，并將當(dāng)前群體中產(chǎn)生的最佳個(gè)體作為最優(yōu)結(jié)論進(jìn)行輸出。在本例中，我們所要得到的是一個(gè)滿足給定閾值的規(guī)則集合，而并不是求最優(yōu)解，所以終止代數(shù)是經(jīng)過幾代運(yùn)算后，當(dāng)沒有小于給定閾值的規(guī)則產(chǎn)生時(shí)，系統(tǒng)運(yùn)行就停止。

2.3 用遺傳算法提取關(guān)聯(lián)規(guī)則

算法如下：

Step1：初始化

（1） 隨機(jī)產(chǎn)生一個(gè)初始種群P={A1，A2，…..An}；

（2） 輸入用戶給定的支持度S，可信度C，興趣度I；

Step2：進(jìn)行選擇

（1） 計(jì)算目前種群P中的個(gè)體適應(yīng)度：f（A）=S/S；

（2） 根據(jù)f（A）對個(gè)體進(jìn)行篩選：若大于1，則保留個(gè)體進(jìn)行產(chǎn)生下一代，否則刪除個(gè)體，并計(jì)算出保留下的個(gè)體數(shù)M；

Step3：若M

Step4：對交配池T和后代O進(jìn)行初始化。

Step5：將當(dāng)前種群中的所有個(gè)體都復(fù)制到交配池中；

Step6：隨機(jī)從T中選擇個(gè)體A和A，按照概率Pc進(jìn)行交叉；

Step7：在當(dāng)前種群P中選擇M個(gè)個(gè)體按照概率Pc進(jìn)行變異；

Step8：判斷是否終止條件；

Step9：利用置信度和興趣度進(jìn)行規(guī)則的提取。

3 發(fā)現(xiàn)的規(guī)則

根據(jù)以上的算法，我們在新生信息和調(diào)查信息數(shù)據(jù)庫中發(fā)現(xiàn)部分有價(jià)值的關(guān)聯(lián)規(guī)則如下：

規(guī)則1：學(xué)生生源地為縣級及以下地區(qū)、普通高中畢業(yè)，并且分?jǐn)?shù)中等的學(xué)生，非常注重學(xué)校的專業(yè)水平和就業(yè)水平對校園文化和學(xué)校環(huán)境感興趣情況一般。

規(guī)則2：學(xué)生生源地為一級城市、職業(yè)高中，并且分?jǐn)?shù)較低的同學(xué)，非常注重學(xué)生的環(huán)境和校園文化對專業(yè)水平比較重視對專升本情況感興趣一般。

規(guī)則3：學(xué)生生普通高中畢業(yè)，分?jǐn)?shù)較高，非常注重專升本情況及學(xué)校的專業(yè)水平對就業(yè)水平比較感興趣，對校園文化感興趣情況一般。

以上對好多規(guī)則進(jìn)行了省略，總之，此挖掘算法在大專院校對外招生宣傳側(cè)重方向上起了很大的作用，挖掘出了學(xué)生生源地、畢業(yè)院校、成績等級等因素與所關(guān)心學(xué)校的各種情況之間的潛在關(guān)聯(lián)。

4 結(jié)束語

本文對遺傳算法在關(guān)聯(lián)規(guī)則提取方面的應(yīng)用進(jìn)行了初步的分析，還有許多問題需要進(jìn)一步地去學(xué)習(xí)和探討。文中所采用的掘算法主要考慮了兩個(gè)稱作支持度和可信度的閾值，但近來的研究表明： 在現(xiàn)實(shí)應(yīng)用中只考慮這兩個(gè)閾值是不夠的，可能會產(chǎn)生錯(cuò)誤的規(guī)則。在高校中，基本關(guān)聯(lián)規(guī)則的挖掘算法還可以應(yīng)用在學(xué)生心理分析、貧困生選取等其他方面， 都會具有很好的實(shí)用價(jià)值.

參考文獻(xiàn)：

[1] 薛慧君.基于遺傳算法的關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘的應(yīng)用研究[D].天津：天津大學(xué)，2006，06

[2] 許珂 劉希玉.基于遺傳算法的關(guān)聯(lián)規(guī)則挖掘方法及應(yīng)用[J].重慶工學(xué)院學(xué)報(bào)，2007年，7：132-133

[3] 肖冬榮. 基于遺傳算法的關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘[J].通信技術(shù)，2010（1）：205-207

[4] 何小東 劉衛(wèi)國，數(shù)據(jù)挖掘中關(guān)聯(lián)規(guī)則挖掘算法比較研究[J]，計(jì)算機(jī)工程與設(shè)計(jì)，2005，5（5）：1265-1268.