摘要：簡要地介紹了關(guān)聯(lián)規(guī)則，通過對(duì)關(guān)聯(lián)分析的經(jīng)典算法-Apriori算法的分析，發(fā)現(xiàn)了經(jīng)典算法Apriori算法的缺陷，給出了改進(jìn)的關(guān)聯(lián)規(guī)則算法FARM_New算法和基于篩選壓縮的Apriori挖掘算。并將其應(yīng)用到教學(xué)質(zhì)量評(píng)估系統(tǒng)中進(jìn)行對(duì)比分析。

關(guān)鍵詞：數(shù)據(jù)挖掘；關(guān)聯(lián)規(guī)則；教學(xué)質(zhì)量評(píng)估系統(tǒng)

中圖分類號(hào)：TP311文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044(2008)09-11580-03

Study and Application of Association Rule Mining in Database

LIU Xiao-na

(Shenyang Normal University ， Institute for Scientific Information Software，Shenyang 110034，China)

Abstract: This text briefly introduce association rule.By analyzing the application of classic Apriori algorithm， Apriori algorithm is found that it has some disadvantages. And then FARM_NEW algorithm and the Apriori algorithm of riddling compression those improving the association rule algorithm are proposed. They are applied to teaching quality assessment system system， and are contrast and analysis.

Key words: date mining; association rule; teaching quality assessment system

1 引言

隨著數(shù)字化校園的建設(shè)，高校教學(xué)評(píng)估已經(jīng)越來越受到重視，教學(xué)質(zhì)量評(píng)估系統(tǒng)也應(yīng)運(yùn)而生。目前全國高校都在面臨著學(xué)校招生人數(shù)不斷擴(kuò)大的局面，高校的管理工作、特別是教學(xué)管理工作將會(huì)變得非常繁重的復(fù)雜。因此隨著教學(xué)規(guī)模的擴(kuò)大，教學(xué)質(zhì)量的評(píng)估得作用越來越明顯，但其信息量變得十分龐大，這時(shí)利用數(shù)據(jù)挖掘技術(shù)，將針對(duì)已有海量教學(xué)信息進(jìn)行有效的知識(shí)發(fā)現(xiàn)，為管理者提供有益的幫助。教學(xué)評(píng)估系統(tǒng)包括基本信息管理、學(xué)生系統(tǒng)、課程系統(tǒng)、教師管理、教學(xué)計(jì)劃、成績管理、課程評(píng)分等系統(tǒng)，涉及教學(xué)管理的各個(gè)環(huán)節(jié)。由于教學(xué)質(zhì)量評(píng)估系統(tǒng)自己的特殊性，其數(shù)據(jù)挖掘采用關(guān)聯(lián)規(guī)則挖掘。

2 數(shù)據(jù)挖掘及模糊關(guān)聯(lián)規(guī)則

2.1 數(shù)據(jù)挖掘

數(shù)據(jù)挖掘是20世紀(jì)80年代后期興起的學(xué)科，指從數(shù)據(jù)中獲取正確、新穎、有潛在應(yīng)用價(jià)值和最終可理解模式的非平凡的過程。簡單地說，數(shù)據(jù)挖掘就是從大型數(shù)據(jù)庫或數(shù)據(jù)倉庫中儲(chǔ)存的大量的、不完整的、有噪聲的數(shù)據(jù)中發(fā)現(xiàn)潛在的、有價(jià)值的、有趣知識(shí)的過程。提取的知識(shí)一般可以表示為概念、規(guī)則、規(guī)律、模式等形式。

2.2 模糊關(guān)聯(lián)規(guī)則

定義1：設(shè)I={i1，i2，…，in}是由n個(gè)不同的項(xiàng)目組成的項(xiàng)目集。給定一個(gè)數(shù)據(jù)庫D，其中的每一個(gè)記錄T是I中一組項(xiàng)目集合(T是I的數(shù)據(jù)項(xiàng)子集)，即T#8838;I，T有一個(gè)唯一的標(biāo)識(shí)符TID。若集合X#8838;I且X#8838;T，則稱記錄T包含集合X。

定義2：設(shè)R={rl，r2，…，rk}是由k個(gè)不同的模糊區(qū)間組成的集合。若A={al，a2，…，ap}#8838;R，則稱A為R中一組模糊區(qū)間。

定義3：uA(X)=Λuaj(xi)表示集合X對(duì)區(qū)間A的隸屬程度，其中每一個(gè)xj在A中都有唯一的aj與之相對(duì)應(yīng)，uaj(xi)表示屬性值xi對(duì)區(qū)間aj的隸屬程度。

定義4：一條模糊關(guān)聯(lián)規(guī)則就是形如X_A#8658;Y_B的蘊(yùn)涵式，其中X#8838;I，Y#8838;I，X∩Y=Φ，A#8838;R，B#8838;R，ai、bj分別是xi、yj對(duì)應(yīng)的模糊區(qū)間。

3 經(jīng)典模糊關(guān)聯(lián)規(guī)則算法及改進(jìn)算法

3.1 經(jīng)典算法——Apriori算法

Apriori算法的基本思想是首先找出所有的頻繁項(xiàng)集，這些項(xiàng)集出現(xiàn)的頻繁性至少和預(yù)定義的最小支持度一樣。然后由頻繁項(xiàng)集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則，這些規(guī)則必須滿足最小支持度和最小可信度。

Apriori算法的性質(zhì)是頻繁項(xiàng)集的所有非空子集必定是頻繁的，或者說非頻繁項(xiàng)集的所有超集必定是非頻繁的。即若存在項(xiàng)集I不是頻繁的，滿足P(I)

產(chǎn)生頻繁項(xiàng)集的過程主要分為連接和剪枝兩步：

連接步驟：為了發(fā)現(xiàn)Lk，可以將Lk-1中兩個(gè)項(xiàng)集相連接以獲得一個(gè)Lk的候選集合Ck。設(shè)l1和l2為Lk-1中的兩個(gè)項(xiàng)集（元素），記號(hào)li[j]表示li中的第j個(gè)項(xiàng)。為方便起見，假設(shè)交易數(shù)據(jù)庫中各交易記錄中各項(xiàng)均已按字典排序。若Lk-1的連接操作記為Lk-1#1051719;Lk-1，它表示若l1和l2中的前(k－2)項(xiàng)是相同的，則Lk-1中l(wèi)1和l2的內(nèi)容就可以連接到一起。

剪枝步驟：Ck是Lk的一個(gè)超集，其中的各元素（項(xiàng)集）不一定都是頻繁項(xiàng)集，但所有的頻繁k_項(xiàng)集一定都在Ck中，即有Lk#8838;Ck。掃描一遍數(shù)據(jù)庫就可以決定Ck中每個(gè)候選項(xiàng)集（元素）的支持頻度，并由此獲得Lk中各個(gè)元素（頻繁k_項(xiàng)集）。所有頻度不小于最小支持度的候選項(xiàng)集就是屬于Lk的頻繁項(xiàng)集。然而由于Ck中的候選項(xiàng)集很多，如此操作所涉及的計(jì)算量（運(yùn)算時(shí)間）是非常大的，為了減少Ck的大小，就需要利用Apriori性質(zhì)，因而也就可以將其從中刪去。Apriori算法有些缺陷，如它需要對(duì)事物數(shù)據(jù)庫進(jìn)行多次掃描，這就對(duì)I/O的負(fù)載能力提出了一定的要求；并且這種算法可能產(chǎn)上龐大的候選集，這就對(duì)時(shí)間和內(nèi)存存儲(chǔ)空間是一種挑戰(zhàn)。

3.2 Apriori算法的改進(jìn)算法——FARM_New算法

此改進(jìn)算法是由Srikant、Hong、程繼華等提出的，F(xiàn)ARM_New算法主要步驟如下：

(1)按照預(yù)定義的分類方法，將祖先加到相應(yīng)的事務(wù)結(jié)點(diǎn)之上。

(2)掃描數(shù)據(jù)庫D，產(chǎn)生候選項(xiàng)集，如果項(xiàng)的出現(xiàn)次數(shù)≥min_sup，該項(xiàng)集成為頻繁項(xiàng)集。首先產(chǎn)生頻繁1-項(xiàng)集，然后產(chǎn)生候選2-項(xiàng)集，這個(gè)過程直至產(chǎn)生所有的頻繁項(xiàng)集時(shí)結(jié)束。

(3)引入在第2階段產(chǎn)生的所有可能的關(guān)聯(lián)規(guī)則。計(jì)算這些規(guī)則的置信度，如果滿足置信度閾值，則將其保留，否則予以刪除。

(4)通過以下3個(gè)閾值條件篩選，將不符合興趣度條件的關(guān)聯(lián)規(guī)則移去，將符合條件的興趣規(guī)則輸出：這條規(guī)則的父規(guī)則沒有滿足條件（在預(yù)定義的分類規(guī)則中用該項(xiàng)的父結(jié)點(diǎn)替換該項(xiàng)得到）；必須滿足最小支持度閾值；必須滿足最小置信度閾值。

FARM_New算法相對(duì)于Apriori算法的一些缺陷有所改進(jìn)。采用模式的支持事務(wù)集合的比較方法代替了Apriori算法的模式匹配，節(jié)約了存儲(chǔ)模糊項(xiàng)集和模糊頻繁項(xiàng)集的內(nèi)存占用，從而提高了挖掘算法的性能；對(duì)非終點(diǎn)項(xiàng)進(jìn)行處理，從而提高了挖掘規(guī)則的精確性；算法所構(gòu)造的頻繁模糊模式，是由預(yù)定義在屬性上的模糊概念組成，使得交叉層的關(guān)聯(lián)規(guī)則挖掘可以很容易地從上述范圍內(nèi)找到。

3.3 Apriori算法的改進(jìn)算法——基于篩選壓縮的Apriori算法

由于Apriori算法需要對(duì)事物數(shù)據(jù)庫進(jìn)行多次掃描，這一缺陷通過采樣的方法可以將掃描次數(shù)降到一次到兩次，這就大大降低了I/O的代價(jià)。一個(gè)完整的數(shù)據(jù)集對(duì)于獲取可靠的結(jié)論至關(guān)重要，但這并不是完全必需的。因?yàn)橥暾臄?shù)據(jù)集往往有更多的數(shù)據(jù)冗余，I/O操作代價(jià)昂貴，存在的一些不穩(wěn)定性，降低算法效率。

引入了數(shù)據(jù)刪除技術(shù)及壓縮來提高Apriori挖掘算法對(duì)大型數(shù)據(jù)庫挖掘的效率和適應(yīng)能力，得到的基于篩選壓縮的Apriori挖掘算法。篩選壓縮的Apriori挖掘算法的基礎(chǔ)數(shù)據(jù)刪除與壓縮技術(shù)的基本性質(zhì)如下：

(a)對(duì)于已知規(guī)模的事務(wù)數(shù)據(jù)庫D，任意一個(gè)項(xiàng)集I的出現(xiàn)支持度與規(guī)模小于I的事務(wù)無關(guān)。所以可以刪除規(guī)模小于I的事務(wù)記錄。

(b)由于不包含任何k_項(xiàng)集的事務(wù)不可能包含任何一個(gè)(k+1)_頻繁項(xiàng)集。因此在生成(k+1)_頻繁項(xiàng)集之前對(duì)這樣的事務(wù)記錄進(jìn)行刪除操作，以便來減少下次掃描事務(wù)數(shù)據(jù)庫的次數(shù)。

基于篩選壓縮的Apriori挖掘算法的基本步驟如下：

第一步：初始化數(shù)據(jù)庫，根據(jù)條件初始化數(shù)據(jù)庫（條件可以是時(shí)間段、種類、品種等）。

第二步：掃描事務(wù)數(shù)據(jù)庫，從中找出所有的項(xiàng)集長度為k=1的項(xiàng)的支持度，形成原始的頻繁項(xiàng)集，生成臨時(shí)表table_1。

第三步：刪除操作，刪除事務(wù)數(shù)據(jù)庫中所有的項(xiàng)集長度小于k的事務(wù)。以及刪除事務(wù)數(shù)據(jù)庫中所有的不包含任何k-項(xiàng)頻繁項(xiàng)集的事務(wù)。

第四步：對(duì)k_頻繁關(guān)聯(lián)項(xiàng)集進(jìn)行連接操作，以生成(k+1)_項(xiàng)頻繁關(guān)聯(lián)項(xiàng)集。以k-項(xiàng)頻繁關(guān)聯(lián)項(xiàng)集為基礎(chǔ)，k項(xiàng)集的其它項(xiàng)集的最后一項(xiàng)依次添加進(jìn)table_2和刪除。進(jìn)行判斷，產(chǎn)生(k+1)_項(xiàng)頻繁關(guān)聯(lián)項(xiàng)集。（該過程有兩重嵌套循環(huán)）

(1)取生成的候選項(xiàng)集中（長度為k）第i=1個(gè)項(xiàng)集。

(2)取第j=i+1項(xiàng)集且最后一項(xiàng)與第i個(gè)項(xiàng)集最后一項(xiàng)不同的項(xiàng)合并成k+1項(xiàng)添加進(jìn)臨時(shí)表table_2中，生成了(k+1)_項(xiàng)集，并計(jì)算其支持度。若支持度大于最小支持度min-supp；且置信度大于最小置信度min-conf，則生成了第一個(gè)頻繁關(guān)聯(lián)項(xiàng)，保存該頻繁關(guān)聯(lián)項(xiàng)。

(3)j=j+1，若j為k_項(xiàng)集最后一個(gè)記錄則轉(zhuǎn)到(4)，否則轉(zhuǎn)(2)。

(4)i=i+1，若i為k_項(xiàng)集最后一個(gè)記錄則轉(zhuǎn)到(5)，否則轉(zhuǎn)(2)。

(5)所有符合條件的k+1項(xiàng)集生成，則table_2為k+1相關(guān)聯(lián)項(xiàng)，根據(jù)需要可對(duì)其進(jìn)行保存。

第五步：k=k+1；把table_2賦給bable_1，依次重復(fù)執(zhí)行第三步，直到k項(xiàng)集為空集時(shí)終結(jié)。

4 關(guān)聯(lián)規(guī)則算法在教學(xué)質(zhì)量評(píng)估系統(tǒng)中應(yīng)用比較

將上述Apriori挖掘算法和基于篩選壓縮的Apriori算法采用C++語言實(shí)現(xiàn)。為了測試算法的性能，采用的數(shù)據(jù)是教學(xué)質(zhì)量評(píng)估系統(tǒng)所提供的某系學(xué)生的對(duì)港等數(shù)學(xué)這門課的評(píng)價(jià)信息數(shù)據(jù)作為實(shí)驗(yàn)測試數(shù)據(jù)。

通過測試，得出了兩種算法輸出的項(xiàng)集都是頻繁的，并且算法輸出了所有的頻繁項(xiàng)集，這就說明兩種算法都是可行的，正確的。

我們用上面提供的數(shù)據(jù)分別對(duì)Apriori與基于篩選壓縮的Apriori算法這兩個(gè)算法針對(duì)不同支持度的執(zhí)行時(shí)間進(jìn)行實(shí)驗(yàn)，這里所用的合成數(shù)據(jù)包含105個(gè)事務(wù)，每個(gè)事務(wù)的平均長度為10，每個(gè)最大潛在頻繁項(xiàng)集的平均長度為4。實(shí)驗(yàn)結(jié)果可以看出，針對(duì)不同的支持度，基于篩選壓縮的Apriori算法的執(zhí)行時(shí)間要比Apriori算法的執(zhí)行時(shí)間快。而且改進(jìn)后的算法的執(zhí)行時(shí)間與Apriori算法相比的優(yōu)越性在支持度較小時(shí)更加明顯，其原因與隨著支持度的減小，候選項(xiàng)集逐漸增大有關(guān)。

通過以上對(duì)Apriori算法和改進(jìn)的Apriori算法的使用分析，可以看出改進(jìn)的Apriori算法不僅減少了掃描數(shù)據(jù)庫的次數(shù)，而且減少了生成頻繁項(xiàng)目集的候選項(xiàng)目集，很大程度上提高了算法的效率。

5 結(jié)束語

隨著高校數(shù)據(jù)庫的不斷增大，如何將數(shù)據(jù)挖掘技術(shù)更好地應(yīng)用到高校教學(xué)系統(tǒng)中，成為一個(gè)擺在我們面前的實(shí)際問題。本文通過對(duì)傳統(tǒng)Apriori算法的分析，找出其缺陷，提出了改進(jìn)的算法——FARM_New算法和基于篩選壓縮的Apriori挖掘算法。但從教學(xué)質(zhì)量評(píng)估系統(tǒng)中挖掘出來的規(guī)則數(shù)量非常大，不同的應(yīng)用背量、不同的挖掘目的，對(duì)挖掘結(jié)果有不同的要求，所以這兩種算法還有很多有待于我們完善的地方。

參考文獻(xiàn)：

[1] Jiawei Han，Micheline Kamber.數(shù)據(jù)挖掘：概念與技術(shù)[M]. 北京: 機(jī)械工業(yè)出版社，2001.

[2] Cubero， J C， Medina J M. Pons O. Rules discovery in fuzzy relational databases[A]. In: Conference of the North American Fuzyy Information Processing Society[C]. Maryland: IEEE Computer Society Press， 1995:414-419.

[3] Ruan D， Kerre E E. Fuzzy implication operators and generalized fuzzy method of cases [J]. Fuzzy Sets and systems， 1993 :54(1):23-38.

[4] Klir GJ， Yuan B. Fuzzy sets and fuzzy logic2theory and applications[M]. New Jersey : Prentice Hall， 1995.

[5] 周劍雄，王明哲. 基于關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘技術(shù)的快速算法[J].計(jì)算機(jī)工程，2003:48-92.

[6] 范明，孟小峰. 數(shù)據(jù)挖掘概念與技術(shù)[M].北京:機(jī)械工業(yè)出版社，2002.

[7] 康曉東，等. 基于數(shù)據(jù)倉庫的數(shù)據(jù)挖掘技術(shù)[M].北京:機(jī)械工業(yè)出版社.2004.

[8] 邵峰晶，于忠清. 數(shù)據(jù)挖掘原理與算法[M].北京:中國水利水電出版社.2003.

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文。”