基于粗糙集改進Apriori算法在高校貧困生認定中的應用

樊偉 劉紅 匡亞茹

摘要：為增強困難學生認定的準確度，該文從粗糙集理論思想通過屬性約簡，得到關鍵屬性集合，建立決策信息表，利用改進的Apriori算法對決策條件屬性數(shù)據(jù)分析，給出頻繁項集;通過對部分貧困生數(shù)據(jù)實驗驗證，得出該算法在一定程度上保證貧困生認定的準確度。

關鍵詞：粗糙集;Apriori算法;屬性約簡;數(shù)據(jù)挖掘;貧困生認定

中圖分類號：TP391.9? ? ? 文獻標識碼：A

文章編號：1009-3044（2019）21-0003-04

開放科學（資源服務）標識碼（OSID）：

Abstract： In order to enhance the accuracy of the identification of difficult students， this paper gets the key attribute set from the rough set theory thought through attribute reduction， establishes the decision information table， uses the improved Apriori algorithm to analyze the decision condition attribute data， gives the frequent item set， and through the experimental verification of some poor students ' data， It is concluded that the algorithm ensures the accuracy of the identification of poor students to a certain extent.

Key words： rough sets; Apriori algorithm; Apriori algorithm; teaching quality evaluation; Data mining; poor student identification

1 背景

貧困生的認定是高校學生工作的重要組成部分，國家和地方政府推出一系列舉措幫扶每個貧困生，制定一系列的量化標準。如何認定貧困生，把助學金用到真正學校幫助的學生身上。認定工作完成學生資助工作首要任務，是學校實施各項資助措施的依據(jù)[1]。本文提出了基于粗糙集的屬性依賴度對屬性進行約簡的算法，利用核心屬性數(shù)據(jù)，再通過改進的Apriori算法對決策屬性數(shù)據(jù)分析，總結(jié)出頻繁項集;大大減少讀取數(shù)據(jù)庫的次數(shù)，防止候選項集大量產(chǎn)生，降低了關聯(lián)規(guī)則挖掘的時間復雜度，提高對貧困生認定的效率。

2 設計思路

2.1 設計流程

該算法的設計思想分兩步走：首先運用屬性約簡算法對全校Excel統(tǒng)計的貧困生數(shù)據(jù)進行約簡，將約簡后的決策信息表導入進Access數(shù)據(jù)庫;再通過改進的Apriori算法對決策信息進行關聯(lián)規(guī)則的數(shù)據(jù)分析，從而產(chǎn)生頻繁項集。算法流程圖1如下：

2.2 粗糙集基本理論

粗糙集理論是處理模糊和不確定信息的數(shù)學工具，在1982年由波蘭科學家Z.Pawlak提出，其主要思想是在保留分類能力的前提下進行數(shù)據(jù)化簡，識別并分析數(shù)據(jù)之間依賴關系。目前在機器學習、過程控制、決策分析等領域應用廣泛。屬性約簡是粗糙集理論中研究重要課題，更多學者提出改進約簡算法[3]。屬性約簡基于Rough集理論的知識獲取，主要是通過對原始決策表的約簡，在保持決策表決策屬性和條件屬性之間的依賴關系不發(fā)生變化的前提下對決策表刪除不相關或不重要的屬性。

定義1 形式上，四元組[S=（U，A，V，f）]是一個信息系統(tǒng)，其中[A=C?D]，[U={x1，x2，???，xn}]，[U]中的每個[xi（1≤i≤n）]稱為一個對象，[A=C?D]是屬性的非空有限集合，[C={c1，c2，???，cm}]是條件屬性集合，[D={d1，d2，???，dk}]是決策屬性集合，且[C?D=?]，[C≠?]，[D≠?];其中，[V=a∈AVa，Va]是屬性a的值域;[f：?a∈A，x∈U，f（x，a）∈Va]，一般簡記為[S=（U，A）]，則這樣的知識表達系統(tǒng)為決策表。

定義2 令[R]為一族等價關系，[r∈R]，如果[ind（R）=ind（R-{r}）]，則稱[r]為[R]中不必要的;否則稱[r]為[R]中必要的。

設[Q?P]。如果[Q]是獨立的，且[ind（Q）=ind（P）]，則稱[Q]為[P]的一個約簡。[P]中所有必要的原始關系構(gòu)成集合稱為[P]的核，記做[core（P）]。

核與約簡有如下關系：[core（P）=?red（P）] ，其中[red（P）]表示[P]的所有約簡[5]。

定義 3 假設[P]和[Q]是集合[U]上的等價關系，正域、負域、邊界域定義如下：

正域：[posp（Q）=X∈U/QPX];

負域：[NEGp（Q）=X∈U/QPX];

邊界域：[BNDp（Q）=X∈U/QPX-X∈U/QPX]。

定義4 令[K=（U，A）]為一知識庫，且[P，Q∈R]當[k=rp（Q）=|posp（Q）|/|U|]稱知識[Q]是[k]度依賴于知識[P]的，記作[p?kQ]。當[k=1]時，我們稱[Q]完全依賴于[P];當[0

2.3 改進的Apriori算法

Apriori算法是經(jīng)典的挖掘頻繁項集和關聯(lián)規(guī)則的數(shù)據(jù)挖掘算法，使用頻繁項集性質(zhì)的先驗性質(zhì)進行逐層搜索的迭代方法。在計算過程中多次讀取數(shù)據(jù)庫，需對項集剪枝。針對Apriori算法在計算中產(chǎn)生大量的候選項集和對數(shù)據(jù)庫的讀取時有較大的I/O開銷等問題[6]，提出了利用鏈表建立數(shù)據(jù)模型，鏈表包括分項集頭結(jié)點、項結(jié)點、事務結(jié)點三種結(jié)點。 如圖2所示對數(shù)據(jù)庫只需掃描一次，這樣避免在Apriori 算法中多次掃描數(shù)據(jù)庫，大大減少了對I/O開銷。鏈表的兄弟結(jié)點從左到右依照子集支持度的遞增順序排列，由1-項集產(chǎn)生較少的候選2-項集，由2-項集再產(chǎn)生更少的候選3-項集，大大提升內(nèi)核的匯聚能力。

3 算法在高校貧困生認定中驗證

在網(wǎng)絡信息化高度發(fā)展的當代，對貧困生的認定應從多方面入手來進行界定，定量和定性相結(jié)合的認定標準，對貧困生的基本信息進行匯總，相關信息表如下：

學生基本信息表（學號，姓名，性別，出生年月，民族，身份證號碼，政治面貌，院系，專業(yè)，年級，個人愛好，孤殘，單親，烈士子女，健康狀況，家庭人口數(shù)，家庭年收入，已參加勤工儉學，家庭地址）。

家庭成員登記表（姓名，年齡，與學生關系，職業(yè)，工作單位，健康狀況，學號）。

貧困生認定申請表（學號，姓名，院系，專業(yè)，年級，班級，家庭人均年收入，申請理由）。

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

校園一卡通月消費明細表（卡號、學號，姓名，性別，月消費金額）。

助學貸款登記表（學號、姓名、院系、專業(yè)、年級、班、貸款金額（元） [7]。

對上述數(shù)據(jù)表等信息進行匯總分析，得到反映學生是否貧困的基本因素（a1：是否申請貧困;a2：是否補考;a3：戶籍;a4：家庭人口;a5：月生活費用;a6：是否抽煙喝酒;a7：貸款金額; a8：兄弟姐妹上學人數(shù);a9：烈士子女;a10：家庭人均月收入;a11：危重病人;a12：單親或孤殘，a13：父母職業(yè);a14：是否貧困地區(qū)），構(gòu)成原始信息決策表的條件屬性[C]。現(xiàn)抽取某高校17級15名學生相關信息構(gòu)成的論域[U={x1，x2，???，x15}]，認定學生是否為貧困結(jié)果：貧困和不貧困，即得決策屬性集[D]。

為了方便運用粗糙集算法對上述數(shù)據(jù)進行數(shù)據(jù)約簡，對連續(xù)型數(shù)值數(shù)據(jù)進行離散化，如貸款金額、月消費金額等屬性，用數(shù)字編號各屬性值：

調(diào)整最小支持度為25%，最小置信度為80%，利用改進的Apriori算法生成頻繁項集，如表6所示：

對生成的10條規(guī)則加以分析得出：

規(guī)則1：月生活費用>500，說明該生月生活費在500元以上，雖是農(nóng)村戶口，家庭人口在6人以下，家中有2人上學，父母務農(nóng)，貧困生認定的可信度在56.17%。

規(guī)則4：月生活費用<=500，說明該生月生活費在500元以下，雖是城鎮(zhèn)戶口，但父母失業(yè)，低保，貧困認定的可信度為87.23%。

規(guī)則7：月生活費用<350，說明該生單親，農(nóng)村戶口，上學人數(shù)有2人，家庭負擔較重，申請過助學貸款，貧困生認定的可信度為100%。

規(guī)則9：月生活費用<350，說明該生月生活費用在350元以下，雖城鎮(zhèn)戶口，單親，但是烈士子女，符合重點優(yōu)撫對象，貧困生認定的可信度為100%。

4 結(jié)束語

本文提出基于粗糙集理論的屬性依賴度的屬性約簡方法引入到經(jīng)典的Apriori算法的改進工作中減少對數(shù)據(jù)庫的掃描次數(shù)及產(chǎn)生大量的候選項集的問題，對貧困生信息的認定實驗中驗證了該方法能有效地進行數(shù)據(jù)約簡和關聯(lián)規(guī)則挖掘，能提高高校貧困生認定的效率。

參考文獻：

[1] 丁桂蘭， 周艷華. 高校貧困生認定的現(xiàn)實困境與對策思考[J]. 教育與職業(yè)， 2010（9）： 33-35.

[2] 白華， 徐英. 高校貧困生資助績效評價指標體系設計[J]. 黑龍江高教研究， 2016（6）： 116-120.

[3] 張文東， 李明壯， 等. 基于粗糙集理論的屬性約簡算法[J]. 計算機工程與設計， 2008（11）： 5795-5797.

[4] 楊沛， 袁莎， 等. 一種改進的基于依賴度的屬性約簡算法[J]. 云南民族大學學報， 2011（11）： 504-507.

[5] 陳鑫影. 粗糙集在企業(yè)信息系統(tǒng)中的應用[J]. 商場現(xiàn)代化， 2007（11）： 36.

[6] 周玲元， 段隆振. 改進的 Apriori 算法在高校圖書推薦服務中的應用研究[J]. 圖書館學研究， 2013（2）： 89-91.

[7] 曹路舟. Apriori算法在高職院校貧困生認定工作中的應用[J]. 池州學院學報， 2012（12）： 9-11.

[8] 申靜， 王華彪. 高校貧困生認定的困境與對策[J]. 學校黨建與思想教育， 2012（3）： 50-51.

[9] 胡善忠， 徐怡. 多粒度粗糙集粒度約簡的高效算法[J]. 計算機應用， 2017（37）： 3392-3398.

[10] 喻瑛， 楊崢， 王偉杰. 基于分布式計算模式的兩種屬性約簡算法[J]. 計算機技術與發(fā)展， 2018（1）： 28-32.

【通聯(lián)編輯：謝媛媛】