Apriori算法在高職院校貧困生認定工作中的應用

曹路舟

（池州職業技術學院 信息技術系，安徽 池州 247000）

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

1 關聯規則挖掘算法

1.1 關聯規則的基本概念

關聯規則[3]的挖掘問題可以用下面的形式來描述:

令I={i1，i2，…，in}為一個項目集。令D為一任務相關數據構成的事務數據庫，每個事務T是一項目集且TI。每個事務T都與一個被稱作TID的標識符相關聯。令A為一個項目集，當且僅當AT時事務T包含A。關聯規則的表示形式為AB，其中AI，BI，且 A∩B=。關聯規則AB以支持度S包含事務集D，其中S表示事務集D中包含A∪B的事務占有的事務百分比，即概率P(A∪B)。關聯規則AB是以置信度C包含事務集D，其中C表示事務集D中既包含A事務同時又包含B事務的百分比，即條件概率P(A|B)。表達式如下：

1.2 關聯規則的主要算法

關聯規則的算法主要有Apriori[5]算法，FP-growth[6]算法，以及一些在此基礎上改進的算法。由于Apriori算法屬于單維、單層、布爾關聯規則，思路比較簡單，以遞歸統計為基礎，通過剪枝生成頻繁集，所以該算法得以廣泛使用。

1.3 Apriori算法

Apriori算法挖掘數據可以分為兩個階段：

第一階段：全部的頻繁項目集通過循環迭代識別，并保留滿足支持度不小于用戶預設的最小支持度要求的頻繁項目集。

第二階段：從求出的頻繁項目集中挖掘出置信度不小于用戶預設的最小置信度的規則。

算法描述：

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

（1）求出頻繁1-項集L1

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

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

（4）經過一趟掃描事物數據庫D，求出候選項目集Ck中每個項目集的支持度，這被稱為計數步。

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

重復操作（2）～（5），直到沒有新的頻繁項目集生成時結束。Apriori算法能夠求出滿足最小支持度的所有的頻繁項目集。

算法實現[4]：

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

2 Apriori算法在貧困生認定中的應用

2.1 貧困生認定前的數據準備

2.1.1 數據準備 為了選出滿足資助條件的經濟困難學生，我們需要對所有申請資助的學生的信息進行匯總，得到與家庭經濟困難學生認定有關的信息表有：

學生基本情況表（學號，姓名，性別，出生年月，民族，系，專業，年級，個人特長，入學前戶口，孤殘，單親，烈士子女，健康狀況，家庭人口數，家庭年收入，家庭通訊地址）。

家庭成員情況表（姓名，年齡，與學生關系，職業，工作單位，健康狀況）。

家庭困難認定申請表（學號，姓名，系，專業，年級，班，家庭人均年收入申請理由）。

成績表（學號，姓名，系，班級，課程名，成績）。

校園一卡通月消費情況表（卡號、學號，姓名，性別，出生年月，月消費金額）。

助學貸款情況表（學號、姓名、系、專業、年級、班、貸款金額(元)、貸款期限(月)、貸款利率)。

由于這些表來源于各個部門，每個部門所做的數據表的形式不一定一樣，于是我們利用sql server 2005中的數據轉換服務，把這些形式不一的表都轉換成數據庫中的表，使形式統一起來。如圖1所示：

圖1 貧困生認定因素關系圖

接著以圖1中各表的數據作為源數據，提取與貧困生認定有關的字段進行下一輪分析，去掉對后面分析無作用的字段，再進行適當的格式化轉換，做好數據挖掘的前期準備工作。提取有關字段后得學生基本信息表如表1所示：

表1 學生基本信息表

2.1.2 數據預處理 因為關聯規則算法只能處理離散型數據而不能直接處理連續型數值數據，因此我們先要離散化連續型數值數據，離散化后對應的屬性及值域關系如表2所示：

表2 屬性與值域對應表

然后將表的值域部分通過設定的項目代碼編輯對應生成表3：

表3 屬性與項目代碼對應表

再對事務數據集進行轉換，得到表4：

表4 轉換后的事物數據庫表

2.2 數據挖掘結果及分析

2.2.1 挖掘關聯規則 本次挖掘設定最小支持度是5%，最小置信度是50%。使用Apriori算法對處理后數據進行挖掘后，得到如表5的部分關聯規則（這里只考慮無補考的同學）：

表5 關聯規則結果表

2.2.2 規則理解和評估

（1）規則理解

針對表5，選擇其中的兩幾條關聯規則加以解釋：

規則3：月消費金額<=300，城鎮戶口，父母失業=>一般困難（置信度=75.15%），這條規則表明城鎮里同學在父母雙失業的情況下，月消費金額不高于300元的同學，申請一般困難的置信度為75.15%，可信度較高；

規則6：月消費金額<200，農村戶口，單親，上學人數=2，申請了助學貸款=>特別困難（置信度=100%），這條規則表明，有兄弟姐妹在上學而且是單親的同時申請了助學貸款，月消費水平也在200元以下的農村同學，申請特別困難時的置信度為100%，非?？尚?。

（2）評估

對全校學生進行數據挖掘生成關聯規則后，保留超過最小置信度50%的同學信息，同時與學校實際貧困生資助系統中的貧困生信息作比較如表6：

表6 算法挖掘出的貧困生與資助系統的貧困對照表

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

3 結束語

本論文以全體學生的數據為源數據，使用經典的Apriori算法進行數據挖掘，找出數據間的關聯規則，再通過這些關聯規則來指導學校學生管理部門盡量做到公平的進行貧困生認定，有一定的現實意義，然而關聯規則挖掘技術只是數據挖掘技術中的一種，而且每種挖掘技術的挖掘效率也不盡相同，如何選擇一個好的挖掘算法來提高挖掘的效率是將來研究的主要方向。

[1]紀希禹.數據挖掘技術應用實例[M].北京:機械工業出版社，2009.

[2]王珊，薩師煊.數據庫系統概論[M].北京:高等教育出版社，2010.

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

[4]李劍.數據挖掘技術在學生助學系統中的應用[D].南京:東南大學，2009.

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