樊偉 劉紅 匡亞茹

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

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

中圖分類號：TP391.9? ? ? 文獻(xiàn)標(biāo)識碼：A

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

開放科學(xué)（資源服務(wù)）標(biāo)識碼（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 背景

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

2 設(shè)計思路

2.1 設(shè)計流程

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

2.2 粗糙集基本理論

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

定義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）]，則這樣的知識表達(dá)系統(tǒng)為決策表。

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

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

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

定義 3 假設(shè)[P]和[Q]是集合[U]上的等價關(guān)系，正域、負(fù)域、邊界域定義如下：

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

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

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

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

2.3 改進(jìn)的Apriori算法

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

3 算法在高校貧困生認(rèn)定中驗證

在網(wǎng)絡(luò)信息化高度發(fā)展的當(dāng)代，對貧困生的認(rèn)定應(yīng)從多方面入手來進(jìn)行界定，定量和定性相結(jié)合的認(rèn)定標(biāo)準(zhǔn)，對貧困生的基本信息進(jìn)行匯總，相關(guān)信息表如下：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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

參考文獻(xiàn)：

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

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

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

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

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

[6] 周玲元， 段隆振. 改進(jìn)的 Apriori 算法在高校圖書推薦服務(wù)中的應(yīng)用研究[J]. 圖書館學(xué)研究， 2013（2）： 89-91.

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

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

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

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

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