計算機等級考試中的關聯規則挖掘

曾 旭

（遵義醫學院醫學信息工程系,貴州遵義 563003）

數據挖掘是從大量數據中發現有趣模式,其中數據可以存放在數據庫、數據倉庫或其他信息庫中。這是一個年輕的跨學科領域,源于諸如數據庫系統、數據倉庫、統計學、機器學習、數據可視化、信息檢索和高性能計算。其他有貢獻的領域包括神經網絡、模式識別、空間數據分析、圖像數據庫、信號處理和許多應用領域,如商務、經濟學和生物信息學[1]。

數據挖掘的類型很多,如總結規則挖掘、關聯規則挖掘、分類規則挖掘、聚類規則挖掘、預測分析、趨勢分析和偏差分析等。其中關聯規則挖掘時近幾年研究較多應用最為廣泛的應用[2]。

1 基本術語

關聯規則的概念是由Agrawal等[3]提出的,是數據之間一種簡單實用的規則,是指數據對象之間的相互依賴關系[4]。關聯規則挖掘是從數據中挖掘出滿足一定條件的依賴性關系。關聯規則挖掘的主要對象是事務數據,是形如“X?Y,支持度=s%,置信度=c%”的規則。

1.1 置信度

全體事務集D中支持物品集X的事務中,有c%的事物同時也支持物品Y,則 c%稱為關聯規則X?Y的置信度,置信度表示規則的強度,用confidence（X?Y）,其中,最小置信度用min-conf表示。

1.2 支持度

全體事務集D中有s%的事務同時支持物品集X和Y,則稱s%為關聯規則X?Y的支持度,支持度表示規則的頻度,用support（X?Y）表示,其中最小支持度用min-sup表示。support（X?Y）=P（X∪Y）

1.3 頻繁項集

物品集X的支持度support（X）不小于最小支持度min-sup,則稱 X為頻繁項集。支持度和置信度均大于給定的閾值的規則稱為強規則,數據挖掘主要是關于強規則的挖掘。通常的關聯規則可以用如下數學模型描述:I={i1,i2,…,in}為數據項集,D為全體事務集合,每個事務 T有一個唯一標識Tid,對數據項集X?I,Y?I,稱X包含于Y,當且僅當X?Y。關聯規則形式:（X?Y,support（X?Y）=s%,confidence（X?Y）=c%）,這里X?I,Y?I且X∩Y=Φ,X稱為規則的條件,Y稱為規則的結果。關聯規則挖掘的一般步驟:

（1）找出事務數據庫中所有頻繁項集

（2）用頻繁項集產生強關聯規則,即:對于每個頻繁項集X,如Y?X,Y≠Φ,且confidence（Y?（X-Y）≥min-conf）,構成關聯規則 Y?（X-Y）。

這兩步中,第二步最容易,挖掘關聯規則的總體性能由第一步決定。下面介紹經典的頻繁項集算法Apriori算法。

Apriori算法使用一種稱作逐層搜索的迭代方法,k-項集用于探索（k+1）-項集。首先,找出候選1-項集C1,由 C1生成頻繁1-項集L1;利用頻繁1-項集L1生成候選2-項集 C2,由 C2生成頻繁2-項集L2;如此下去,直到不能找到頻繁k-項集。找每個 Lk需掃描一次數據庫。

2 關聯規則對評分結果的分析

將上述關聯規則的挖掘算法應用于遵義醫學院計算機等級考試評分系統中,根據該?，F有的考試數據可以獲得一些關聯規則?，F以2010級臨床專業全體440名學生的考試數據為例,采用Apriori算法進行選擇題、Windows操作題、打字題、Word操作題、Excel操作題和網絡操作題共6個屬性間的關聯規則的挖掘。具體數據整理成表1,共包含440條相關記錄。由于篇幅關系,文中只列出原表的基本結構和表中的部分數據,如表1所示。

表1 計算機等級考試原始數據

2.1 數據預處理

為了更好的進行關聯規則分析,需對數據進行概化,概化過程遵循的原則是:將得分率低于0.6的題概化不合格,否則概化為合格。具體處理方法如下:

選擇題概化規則:分段概化為 A0（小于12分）,A1（12-20分）。

Windows操作題概化規則:分段概化為B0（小于6分）,B1（6-10分）。

打字題概化規則:分段概化為C0（小于9分）,C1（9-15分）。

Word操作題概化規則:分段概化為D0（小于15分）,D1（15-25分）。

Excel操作題概化規則:分段概化為E0（小于12分）,E1（12-20分）。

網絡操作題概化規則:分段概化為F0（小于6分）,F1（6-10分）。

由關聯規則的概念,Apriori算法的規則和概化后的結果,可得出項目集合為:

{A0 、A1 、B0 、B1 、C0 、C1 、D0 、D1 、E0 、E1 、F0 、F1}

表2 計算機等級考試概化后數據

2.2 關聯規則挖掘過程

現對表2用Apriori算法找出所有頻繁項集,設min-sup=30%,可得候選1-項集C1,如表3所示。

表3 候選1-項集 C1

由候選1-項集C1可得頻繁1-項集L1,如表4所示。

表4 頻繁1-項集 L1

由頻繁1-項集L1可得候選2-項集C2,如表5所示。

表5 候選2-項集 C2

由候選2-項集C2可得頻繁2-項集L2,如表6所示。

表6 頻繁2-項集 L2

由頻繁2-項集L2可得候選3-項集C3,如表7所示。

表7 候選3-項集 C3

由候選3-項集C3可得頻繁3-項集L3,如表8所示。

表8 頻繁3-項集 L3

由頻繁3-項集L3可得候選4-項集C4,如表9所示。

表9 候選4-項集 C4

由候選4-項集C4可得頻繁4-項集L4,如表10所示。

2.3 關聯規則挖掘結果分析

從眾多頻繁項集中,可以發現比較有代表性的兩項:支持度為42.5%的A1 B1 C1 F1以及支持度為37.5%的D0 E0,這兩項頻繁項集的置信度如下:

（A1 B1 C1）?F1,confidence=187/231=81.0%

（A1 B1 F1）?C1,confidence=187/198=94.4%

（A1 C1 F1）?B1,confidence=187/198=94.4%

（B1 C1 F1）?A1,confidence=187/242=77.3%

（D0）?E0,confidence=165/264=62.5%

（E0）?D0,confidence=165/286=57.7%

在設置最小置信度min-conf=30%,最小支持度min-sup=60%的前提下,以上7條規則中前6條形成強規則。即:選擇題、Windows操作題、打字題、網絡操作題的合格情況是相互關聯的,考生在對這4種題型的把握過程中能夠相互促進和提高。另外,Word操作題和Excel操作題的不合格情況是存在關聯的,考生若對Word操作題存在欠缺,那么同時也會對Excel操作題存在欠缺。

表10 頻繁4-項集 L4

3 結束語

對考生的計算機等級考試中各類題型的得分情況進行關聯規則挖掘后所得到的結果能夠幫助考生在學習過程中更注重題型之間的相關性并明確自己可能存在缺欠,便于查漏補缺。與此同時,教師也可在后繼教學過程中重點把握各類題型的相關性,幫助學生重點把握丟分環節并順利通過考試以提升過級率。此結論對考生和教師來說均具有一定的指導性。

[1] RICHARD J ROIGER,MICHAEL W GEATZ.數據挖掘教程[M].北京:清華大學出版社,2003.

[2] JIAWEI HAN,MICHELINE KAMBER.范明,孟小峰等譯.數據挖掘:概念與技術[M].北京:機械工業出版社,2001.

[3] 張瑤,陳高云.數據挖掘技術在試卷分析中的應用[J].西南民族大學學報,2008,34（4）:839-842.

[4] 陳輝,向偉忠.關聯規則挖掘在教師教學評價系統中的應用[J].南華大學學報,2005,19（1）:104-108.

[5] 接勵,王虹.高校人事管理信息心中的關聯規則挖掘[J].天津師范大學學報,2004,24（2）:64-66.

[6] 胡可云,田鳳占.數據挖掘理論與應用[M].北京:清華大學出版社,2008.

[7] 周賢善,杜友福.高置信度關聯規則的挖掘[J].計算機工程與應用,2010,46（24）:151-154.

[8] 張云濤,于治樓.關聯規則中頻繁項集高效挖掘的研究[J].計算機工程與應用,2011,47（3）:139-141.

[9] 馬青霞,李廣水.頻繁模式挖掘進展及典型應用[J].計算機工程與應用,2011,47（15）:138-143.