Apriori算法在高職院校貧困生認(rèn)定工作中的應(yīng)用

曹路舟

（池州職業(yè)技術(shù)學(xué)院 信息技術(shù)系，安徽 池州 247000）

為了更好的完成貧困生資助工作，減輕貧困生認(rèn)定過程中的工作壓力，廣義上的數(shù)據(jù)挖掘就是指知識(shí)發(fā)現(xiàn)[1]。它是從大量數(shù)據(jù)中發(fā)現(xiàn)并提取隱藏在內(nèi)的、人們事先不知道的、但又可能有價(jià)值的信息和知識(shí)一種新技術(shù)[2]。狹義的數(shù)據(jù)挖掘只是知識(shí)發(fā)現(xiàn)過程中的一個(gè)重要步驟，是知識(shí)發(fā)現(xiàn)過程中一個(gè)最核心的環(huán)節(jié)，通過這個(gè)環(huán)節(jié)可以發(fā)現(xiàn)需要的模式。關(guān)聯(lián)規(guī)則挖掘技術(shù)是最常用的技術(shù)之一，本論文通過對(duì)我校所有在校生的基本信息進(jìn)行數(shù)據(jù)分析，并利用這些數(shù)據(jù)采用經(jīng)典的Apriori算法進(jìn)行數(shù)據(jù)挖掘，找出其中的部分?jǐn)?shù)據(jù)之間內(nèi)在的關(guān)聯(lián)，從而提高貧困生認(rèn)定工作的效率。

1 關(guān)聯(lián)規(guī)則挖掘算法

1.1 關(guān)聯(lián)規(guī)則的基本概念

關(guān)聯(lián)規(guī)則[3]的挖掘問題可以用下面的形式來描述:

令I(lǐng)={i1，i2，…，in}為一個(gè)項(xiàng)目集。令D為一任務(wù)相關(guān)數(shù)據(jù)構(gòu)成的事務(wù)數(shù)據(jù)庫，每個(gè)事務(wù)T是一項(xiàng)目集且TI。每個(gè)事務(wù)T都與一個(gè)被稱作TID的標(biāo)識(shí)符相關(guān)聯(lián)。令A(yù)為一個(gè)項(xiàng)目集，當(dāng)且僅當(dāng)AT時(shí)事務(wù)T包含A。關(guān)聯(lián)規(guī)則的表示形式為AB，其中AI，BI，且 A∩B=。關(guān)聯(lián)規(guī)則AB以支持度S包含事務(wù)集D，其中S表示事務(wù)集D中包含A∪B的事務(wù)占有的事務(wù)百分比，即概率P(A∪B)。關(guān)聯(lián)規(guī)則AB是以置信度C包含事務(wù)集D，其中C表示事務(wù)集D中既包含A事務(wù)同時(shí)又包含B事務(wù)的百分比，即條件概率P(A|B)。表達(dá)式如下：

1.2 關(guān)聯(lián)規(guī)則的主要算法

關(guān)聯(lián)規(guī)則的算法主要有Apriori[5]算法，F(xiàn)P-growth[6]算法，以及一些在此基礎(chǔ)上改進(jìn)的算法。由于Apriori算法屬于單維、單層、布爾關(guān)聯(lián)規(guī)則，思路比較簡單，以遞歸統(tǒng)計(jì)為基礎(chǔ)，通過剪枝生成頻繁集，所以該算法得以廣泛使用。

1.3 Apriori算法

Apriori算法挖掘數(shù)據(jù)可以分為兩個(gè)階段：

第一階段：全部的頻繁項(xiàng)目集通過循環(huán)迭代識(shí)別，并保留滿足支持度不小于用戶預(yù)設(shè)的最小支持度要求的頻繁項(xiàng)目集。

第二階段：從求出的頻繁項(xiàng)目集中挖掘出置信度不小于用戶預(yù)設(shè)的最小置信度的規(guī)則。

算法描述：

數(shù)據(jù)顯示，2017年四川省完成地區(qū)生產(chǎn)總值3.70萬億元。其中，成都以1.39萬億元，占比達(dá)到37%，可謂遙遙領(lǐng)先。排行第二的綿陽GDP總量為2074.8億元，成為四川首個(gè)跨過2000億門檻的地級(jí)市。德陽、宜賓、南充則緊隨其后，逼近2000億大關(guān)。在“1500億”一檔的瀘州、達(dá)州、樂山差距并不大。

（1）求出頻繁1-項(xiàng)集L1

（2）求頻繁k-項(xiàng)集Lk，先求出一個(gè)候選頻繁k項(xiàng)集Ck。Ck可以由JOIN計(jì)算獲得，這被稱為連接步。 如果 r，s∈Lk-1，r={r1，r2，…rk-2，rk-1}，s={s1，s2，…，sk-2，sk-1}，而且當(dāng) 1≤i＜k-1 時(shí)，ri=si，當(dāng) i=k-1 時(shí)，rk-1≠sk-1，則 r∪s={r1，r2，…，rk-2，rk-1，sk-1}是 Ck這個(gè)集合中的元素，頻繁k項(xiàng)集的有可能部分來自于候選頻繁k項(xiàng)集的集合Ck之中。

（3）由于候選項(xiàng)目集Ck是頻繁項(xiàng)目集Lk的超集，這樣Ck中部分元素就有可能不是頻繁的。Apriori算法從Ck中去掉所有非頻繁的 （k-1）-項(xiàng)集，通過剪枝思想使Ck的規(guī)模降低。

（4）經(jīng)過一趟掃描事物數(shù)據(jù)庫D，求出候選項(xiàng)目集Ck中每個(gè)項(xiàng)目集的支持度，這被稱為計(jì)數(shù)步。

（5）去掉Ck中不滿足最小支持度的項(xiàng)目集，這樣頻繁k-項(xiàng)集Lk就產(chǎn)生了。

重復(fù)操作（2）～（5），直到?jīng)]有新的頻繁項(xiàng)目集生成時(shí)結(jié)束。Apriori算法能夠求出滿足最小支持度的所有的頻繁項(xiàng)目集。

算法實(shí)現(xiàn)[4]：

其中D是事務(wù)數(shù)據(jù)庫，min_sup是最小支持度，算法 Apriori_gen(Lk-1，min_sup)的功能是：由頻繁項(xiàng)集Lk-1連接生成一個(gè)超集Ck作為候選頻繁項(xiàng)集。

2 Apriori算法在貧困生認(rèn)定中的應(yīng)用

2.1 貧困生認(rèn)定前的數(shù)據(jù)準(zhǔn)備

2.1.1 數(shù)據(jù)準(zhǔn)備 為了選出滿足資助條件的經(jīng)濟(jì)困難學(xué)生，我們需要對(duì)所有申請(qǐng)資助的學(xué)生的信息進(jìn)行匯總，得到與家庭經(jīng)濟(jì)困難學(xué)生認(rèn)定有關(guān)的信息表有：

學(xué)生基本情況表（學(xué)號(hào)，姓名，性別，出生年月，民族，系，專業(yè)，年級(jí)，個(gè)人特長，入學(xué)前戶口，孤殘，單親，烈士子女，健康狀況，家庭人口數(shù)，家庭年收入，家庭通訊地址）。

家庭成員情況表（姓名，年齡，與學(xué)生關(guān)系，職業(yè)，工作單位，健康狀況）。

家庭困難認(rèn)定申請(qǐng)表（學(xué)號(hào)，姓名，系，專業(yè)，年級(jí)，班，家庭人均年收入申請(qǐng)理由）。

成績表（學(xué)號(hào)，姓名，系，班級(jí)，課程名，成績）。

校園一卡通月消費(fèi)情況表（卡號(hào)、學(xué)號(hào)，姓名，性別，出生年月，月消費(fèi)金額）。

助學(xué)貸款情況表（學(xué)號(hào)、姓名、系、專業(yè)、年級(jí)、班、貸款金額(元)、貸款期限(月)、貸款利率)。

由于這些表來源于各個(gè)部門，每個(gè)部門所做的數(shù)據(jù)表的形式不一定一樣，于是我們利用sql server 2005中的數(shù)據(jù)轉(zhuǎn)換服務(wù)，把這些形式不一的表都轉(zhuǎn)換成數(shù)據(jù)庫中的表，使形式統(tǒng)一起來。如圖1所示：

圖1 貧困生認(rèn)定因素關(guān)系圖

接著以圖1中各表的數(shù)據(jù)作為源數(shù)據(jù)，提取與貧困生認(rèn)定有關(guān)的字段進(jìn)行下一輪分析，去掉對(duì)后面分析無作用的字段，再進(jìn)行適當(dāng)?shù)母袷交D(zhuǎn)換，做好數(shù)據(jù)挖掘的前期準(zhǔn)備工作。提取有關(guān)字段后得學(xué)生基本信息表如表1所示：

表1 學(xué)生基本信息表

2.1.2 數(shù)據(jù)預(yù)處理 因?yàn)殛P(guān)聯(lián)規(guī)則算法只能處理離散型數(shù)據(jù)而不能直接處理連續(xù)型數(shù)值數(shù)據(jù)，因此我們先要離散化連續(xù)型數(shù)值數(shù)據(jù)，離散化后對(duì)應(yīng)的屬性及值域關(guān)系如表2所示：

表2 屬性與值域?qū)?yīng)表

然后將表的值域部分通過設(shè)定的項(xiàng)目代碼編輯對(duì)應(yīng)生成表3：

表3 屬性與項(xiàng)目代碼對(duì)應(yīng)表

再對(duì)事務(wù)數(shù)據(jù)集進(jìn)行轉(zhuǎn)換，得到表4：

表4 轉(zhuǎn)換后的事物數(shù)據(jù)庫表

2.2 數(shù)據(jù)挖掘結(jié)果及分析

2.2.1 挖掘關(guān)聯(lián)規(guī)則 本次挖掘設(shè)定最小支持度是5%，最小置信度是50%。使用Apriori算法對(duì)處理后數(shù)據(jù)進(jìn)行挖掘后，得到如表5的部分關(guān)聯(lián)規(guī)則（這里只考慮無補(bǔ)考的同學(xué)）：

表5 關(guān)聯(lián)規(guī)則結(jié)果表

2.2.2 規(guī)則理解和評(píng)估

（1）規(guī)則理解

針對(duì)表5，選擇其中的兩幾條關(guān)聯(lián)規(guī)則加以解釋：

規(guī)則3：月消費(fèi)金額<=300，城鎮(zhèn)戶口，父母失業(yè)=>一般困難（置信度=75.15%），這條規(guī)則表明城鎮(zhèn)里同學(xué)在父母雙失業(yè)的情況下，月消費(fèi)金額不高于300元的同學(xué)，申請(qǐng)一般困難的置信度為75.15%，可信度較高；

規(guī)則6：月消費(fèi)金額<200，農(nóng)村戶口，單親，上學(xué)人數(shù)=2，申請(qǐng)了助學(xué)貸款=>特別困難（置信度=100%），這條規(guī)則表明，有兄弟姐妹在上學(xué)而且是單親的同時(shí)申請(qǐng)了助學(xué)貸款，月消費(fèi)水平也在200元以下的農(nóng)村同學(xué)，申請(qǐng)?zhí)貏e困難時(shí)的置信度為100%，非常可信。

（2）評(píng)估

對(duì)全校學(xué)生進(jìn)行數(shù)據(jù)挖掘生成關(guān)聯(lián)規(guī)則后，保留超過最小置信度50%的同學(xué)信息，同時(shí)與學(xué)校實(shí)際貧困生資助系統(tǒng)中的貧困生信息作比較如表6：

表6 算法挖掘出的貧困生與資助系統(tǒng)的貧困對(duì)照表

對(duì)表6進(jìn)行統(tǒng)計(jì)得知：使用Apriori算法挖掘出的貧困生人數(shù)為1415人，而我校實(shí)際貧困生資助系統(tǒng)中的貧困生總?cè)藬?shù)為1667人，這說明使用Apriori算法挖掘出的同學(xué)有將近85%的人在實(shí)際貧困生資助系統(tǒng)中，該算法針對(duì)這次的貧困生的數(shù)據(jù)挖掘效率約為85%，而不是100%。產(chǎn)生這種結(jié)果的原因有多種可能：（1）關(guān)聯(lián)規(guī)則并不代表因果關(guān)系，只是反映了一個(gè)客觀現(xiàn)象；（2）處理的數(shù)據(jù)并不代表全面，完全真實(shí)；（3）在進(jìn)行數(shù)據(jù)處理時(shí)并沒有考慮到所有的實(shí)際情況，盡管如此，通過以上分析，還是能夠在一定程度上反映了貧困生的認(rèn)定與學(xué)習(xí)成績、貸款、消費(fèi)水平以及家庭情況等之間的關(guān)系規(guī)律，可為貧困生的評(píng)定工作提供一定的依據(jù)，給決策者提供幫助。

3 結(jié)束語

本論文以全體學(xué)生的數(shù)據(jù)為源數(shù)據(jù)，使用經(jīng)典的Apriori算法進(jìn)行數(shù)據(jù)挖掘，找出數(shù)據(jù)間的關(guān)聯(lián)規(guī)則，再通過這些關(guān)聯(lián)規(guī)則來指導(dǎo)學(xué)校學(xué)生管理部門盡量做到公平的進(jìn)行貧困生認(rèn)定，有一定的現(xiàn)實(shí)意義，然而關(guān)聯(lián)規(guī)則挖掘技術(shù)只是數(shù)據(jù)挖掘技術(shù)中的一種，而且每種挖掘技術(shù)的挖掘效率也不盡相同，如何選擇一個(gè)好的挖掘算法來提高挖掘的效率是將來研究的主要方向。

[1]紀(jì)希禹.數(shù)據(jù)挖掘技術(shù)應(yīng)用實(shí)例[M].北京:機(jī)械工業(yè)出版社，2009.

[2]王珊，薩師煊.數(shù)據(jù)庫系統(tǒng)概論[M].北京:高等教育出版社，2010.

[3]JiaweiHan，Micheline Kamber.Data Mining Conceptsand Techniques[M].北京:高等教育出版社，2001.

[4]李劍.數(shù)據(jù)挖掘技術(shù)在學(xué)生助學(xué)系統(tǒng)中的應(yīng)用[D].南京:東南大學(xué)，2009.

[5]Jiawei Han，Micheline Kamber.數(shù)據(jù)挖掘概念與技術(shù)[M].范明，孟小峰，等，譯.北京：機(jī)械工業(yè)出版社，2001.