計(jì)算機(jī)等級(jí)考試中的關(guān)聯(lián)規(guī)則挖掘

曾 旭

（遵義醫(yī)學(xué)院醫(yī)學(xué)信息工程系,貴州遵義 563003）

數(shù)據(jù)挖掘是從大量數(shù)據(jù)中發(fā)現(xiàn)有趣模式,其中數(shù)據(jù)可以存放在數(shù)據(jù)庫(kù)、數(shù)據(jù)倉(cāng)庫(kù)或其他信息庫(kù)中。這是一個(gè)年輕的跨學(xué)科領(lǐng)域,源于諸如數(shù)據(jù)庫(kù)系統(tǒng)、數(shù)據(jù)倉(cāng)庫(kù)、統(tǒng)計(jì)學(xué)、機(jī)器學(xué)習(xí)、數(shù)據(jù)可視化、信息檢索和高性能計(jì)算。其他有貢獻(xiàn)的領(lǐng)域包括神經(jīng)網(wǎng)絡(luò)、模式識(shí)別、空間數(shù)據(jù)分析、圖像數(shù)據(jù)庫(kù)、信號(hào)處理和許多應(yīng)用領(lǐng)域,如商務(wù)、經(jīng)濟(jì)學(xué)和生物信息學(xué)[1]。

數(shù)據(jù)挖掘的類型很多,如總結(jié)規(guī)則挖掘、關(guān)聯(lián)規(guī)則挖掘、分類規(guī)則挖掘、聚類規(guī)則挖掘、預(yù)測(cè)分析、趨勢(shì)分析和偏差分析等。其中關(guān)聯(lián)規(guī)則挖掘時(shí)近幾年研究較多應(yīng)用最為廣泛的應(yīng)用[2]。

1 基本術(shù)語(yǔ)

關(guān)聯(lián)規(guī)則的概念是由Agrawal等[3]提出的,是數(shù)據(jù)之間一種簡(jiǎn)單實(shí)用的規(guī)則,是指數(shù)據(jù)對(duì)象之間的相互依賴關(guān)系[4]。關(guān)聯(lián)規(guī)則挖掘是從數(shù)據(jù)中挖掘出滿足一定條件的依賴性關(guān)系。關(guān)聯(lián)規(guī)則挖掘的主要對(duì)象是事務(wù)數(shù)據(jù),是形如“X?Y,支持度=s%,置信度=c%”的規(guī)則。

1.1 置信度

全體事務(wù)集D中支持物品集X的事務(wù)中,有c%的事物同時(shí)也支持物品Y,則 c%稱為關(guān)聯(lián)規(guī)則X?Y的置信度,置信度表示規(guī)則的強(qiáng)度,用confidence（X?Y）,其中,最小置信度用min-conf表示。

1.2 支持度

全體事務(wù)集D中有s%的事務(wù)同時(shí)支持物品集X和Y,則稱s%為關(guān)聯(lián)規(guī)則X?Y的支持度,支持度表示規(guī)則的頻度,用support（X?Y）表示,其中最小支持度用min-sup表示。support（X?Y）=P（X∪Y）

1.3 頻繁項(xiàng)集

物品集X的支持度support（X）不小于最小支持度min-sup,則稱 X為頻繁項(xiàng)集。支持度和置信度均大于給定的閾值的規(guī)則稱為強(qiáng)規(guī)則,數(shù)據(jù)挖掘主要是關(guān)于強(qiáng)規(guī)則的挖掘。通常的關(guān)聯(lián)規(guī)則可以用如下數(shù)學(xué)模型描述:I={i1,i2,…,in}為數(shù)據(jù)項(xiàng)集,D為全體事務(wù)集合,每個(gè)事務(wù) T有一個(gè)唯一標(biāo)識(shí)Tid,對(duì)數(shù)據(jù)項(xiàng)集X?I,Y?I,稱X包含于Y,當(dāng)且僅當(dāng)X?Y。關(guān)聯(lián)規(guī)則形式:（X?Y,support（X?Y）=s%,confidence（X?Y）=c%）,這里X?I,Y?I且X∩Y=Φ,X稱為規(guī)則的條件,Y稱為規(guī)則的結(jié)果。關(guān)聯(lián)規(guī)則挖掘的一般步驟:

（1）找出事務(wù)數(shù)據(jù)庫(kù)中所有頻繁項(xiàng)集

（2）用頻繁項(xiàng)集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則,即:對(duì)于每個(gè)頻繁項(xiàng)集X,如Y?X,Y≠Φ,且confidence（Y?（X-Y）≥min-conf）,構(gòu)成關(guān)聯(lián)規(guī)則 Y?（X-Y）。

這兩步中,第二步最容易,挖掘關(guān)聯(lián)規(guī)則的總體性能由第一步?jīng)Q定。下面介紹經(jīng)典的頻繁項(xiàng)集算法Apriori算法。

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

2 關(guān)聯(lián)規(guī)則對(duì)評(píng)分結(jié)果的分析

將上述關(guān)聯(lián)規(guī)則的挖掘算法應(yīng)用于遵義醫(yī)學(xué)院計(jì)算機(jī)等級(jí)考試評(píng)分系統(tǒng)中,根據(jù)該?，F(xiàn)有的考試數(shù)據(jù)可以獲得一些關(guān)聯(lián)規(guī)則。現(xiàn)以2010級(jí)臨床專業(yè)全體440名學(xué)生的考試數(shù)據(jù)為例,采用Apriori算法進(jìn)行選擇題、Windows操作題、打字題、Word操作題、Excel操作題和網(wǎng)絡(luò)操作題共6個(gè)屬性間的關(guān)聯(lián)規(guī)則的挖掘。具體數(shù)據(jù)整理成表1,共包含440條相關(guān)記錄。由于篇幅關(guān)系,文中只列出原表的基本結(jié)構(gòu)和表中的部分?jǐn)?shù)據(jù),如表1所示。

表1 計(jì)算機(jī)等級(jí)考試原始數(shù)據(jù)

2.1 數(shù)據(jù)預(yù)處理

為了更好的進(jìn)行關(guān)聯(lián)規(guī)則分析,需對(duì)數(shù)據(jù)進(jìn)行概化,概化過程遵循的原則是:將得分率低于0.6的題概化不合格,否則概化為合格。具體處理方法如下:

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

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

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

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

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

網(wǎng)絡(luò)操作題概化規(guī)則:分段概化為F0（小于6分）,F1（6-10分）。

由關(guān)聯(lián)規(guī)則的概念,Apriori算法的規(guī)則和概化后的結(jié)果,可得出項(xiàng)目集合為:

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

表2 計(jì)算機(jī)等級(jí)考試概化后數(shù)據(jù)

2.2 關(guān)聯(lián)規(guī)則挖掘過程

現(xiàn)對(duì)表2用Apriori算法找出所有頻繁項(xiàng)集,設(shè)min-sup=30%,可得候選1-項(xiàng)集C1,如表3所示。

表3 候選1-項(xiàng)集 C1

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

表4 頻繁1-項(xiàng)集 L1

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

表5 候選2-項(xiàng)集 C2

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

表6 頻繁2-項(xiàng)集 L2

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

表7 候選3-項(xiàng)集 C3

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

表8 頻繁3-項(xiàng)集 L3

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

表9 候選4-項(xiàng)集 C4

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

2.3 關(guān)聯(lián)規(guī)則挖掘結(jié)果分析

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

（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%

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

表10 頻繁4-項(xiàng)集 L4

3 結(jié)束語(yǔ)

對(duì)考生的計(jì)算機(jī)等級(jí)考試中各類題型的得分情況進(jìn)行關(guān)聯(lián)規(guī)則挖掘后所得到的結(jié)果能夠幫助考生在學(xué)習(xí)過程中更注重題型之間的相關(guān)性并明確自己可能存在缺欠,便于查漏補(bǔ)缺。與此同時(shí),教師也可在后繼教學(xué)過程中重點(diǎn)把握各類題型的相關(guān)性,幫助學(xué)生重點(diǎn)把握丟分環(huán)節(jié)并順利通過考試以提升過級(jí)率。此結(jié)論對(duì)考生和教師來(lái)說(shuō)均具有一定的指導(dǎo)性。

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

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

[3] 張瑤,陳高云.數(shù)據(jù)挖掘技術(shù)在試卷分析中的應(yīng)用[J].西南民族大學(xué)學(xué)報(bào),2008,34（4）:839-842.

[4] 陳輝,向偉忠.關(guān)聯(lián)規(guī)則挖掘在教師教學(xué)評(píng)價(jià)系統(tǒng)中的應(yīng)用[J].南華大學(xué)學(xué)報(bào),2005,19（1）:104-108.

[5] 接勵(lì),王虹.高校人事管理信息心中的關(guān)聯(lián)規(guī)則挖掘[J].天津師范大學(xué)學(xué)報(bào),2004,24（2）:64-66.

[6] 胡可云,田鳳占.數(shù)據(jù)挖掘理論與應(yīng)用[M].北京:清華大學(xué)出版社,2008.

[7] 周賢善,杜友福.高置信度關(guān)聯(lián)規(guī)則的挖掘[J].計(jì)算機(jī)工程與應(yīng)用,2010,46（24）:151-154.

[8] 張?jiān)茲?于治樓.關(guān)聯(lián)規(guī)則中頻繁項(xiàng)集高效挖掘的研究[J].計(jì)算機(jī)工程與應(yīng)用,2011,47（3）:139-141.

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