數據庫中關聯規則挖掘研究與應用

摘要：簡要地介紹了關聯規則，通過對關聯分析的經典算法-Apriori算法的分析，發現了經典算法Apriori算法的缺陷，給出了改進的關聯規則算法FARM_New算法和基于篩選壓縮的Apriori挖掘算。并將其應用到教學質量評估系統中進行對比分析。

關鍵詞：數據挖掘；關聯規則；教學質量評估系統

中圖分類號：TP311文獻標識碼：A 文章編號：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 引言

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

2 數據挖掘及模糊關聯規則

2.1 數據挖掘

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

2.2 模糊關聯規則

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

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

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

定義4：一條模糊關聯規則就是形如X_A#8658;Y_B的蘊涵式，其中X#8838;I，Y#8838;I，X∩Y=Φ，A#8838;R，B#8838;R，ai、bj分別是xi、yj對應的模糊區間。

3 經典模糊關聯規則算法及改進算法

3.1 經典算法——Apriori算法

Apriori算法的基本思想是首先找出所有的頻繁項集，這些項集出現的頻繁性至少和預定義的最小支持度一樣。然后由頻繁項集產生強關聯規則，這些規則必須滿足最小支持度和最小可信度。

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

產生頻繁項集的過程主要分為連接和剪枝兩步：

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

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

3.2 Apriori算法的改進算法——FARM_New算法

此改進算法是由Srikant、Hong、程繼華等提出的，FARM_New算法主要步驟如下：

(1)按照預定義的分類方法，將祖先加到相應的事務結點之上。

(2)掃描數據庫D，產生候選項集，如果項的出現次數≥min_sup，該項集成為頻繁項集。首先產生頻繁1-項集，然后產生候選2-項集，這個過程直至產生所有的頻繁項集時結束。

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

(4)通過以下3個閾值條件篩選，將不符合興趣度條件的關聯規則移去，將符合條件的興趣規則輸出：這條規則的父規則沒有滿足條件（在預定義的分類規則中用該項的父結點替換該項得到）；必須滿足最小支持度閾值；必須滿足最小置信度閾值。

FARM_New算法相對于Apriori算法的一些缺陷有所改進。采用模式的支持事務集合的比較方法代替了Apriori算法的模式匹配，節約了存儲模糊項集和模糊頻繁項集的內存占用，從而提高了挖掘算法的性能；對非終點項進行處理，從而提高了挖掘規則的精確性；算法所構造的頻繁模糊模式，是由預定義在屬性上的模糊概念組成，使得交叉層的關聯規則挖掘可以很容易地從上述范圍內找到。

3.3 Apriori算法的改進算法——基于篩選壓縮的Apriori算法

由于Apriori算法需要對事物數據庫進行多次掃描，這一缺陷通過采樣的方法可以將掃描次數降到一次到兩次，這就大大降低了I/O的代價。一個完整的數據集對于獲取可靠的結論至關重要，但這并不是完全必需的。因為完整的數據集往往有更多的數據冗余，I/O操作代價昂貴，存在的一些不穩定性，降低算法效率。

引入了數據刪除技術及壓縮來提高Apriori挖掘算法對大型數據庫挖掘的效率和適應能力，得到的基于篩選壓縮的Apriori挖掘算法。篩選壓縮的Apriori挖掘算法的基礎數據刪除與壓縮技術的基本性質如下：

(a)對于已知規模的事務數據庫D，任意一個項集I的出現支持度與規模小于I的事務無關。所以可以刪除規模小于I的事務記錄。

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

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

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

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

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

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

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

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

(3)j=j+1，若j為k_項集最后一個記錄則轉到(4)，否則轉(2)。

(4)i=i+1，若i為k_項集最后一個記錄則轉到(5)，否則轉(2)。

(5)所有符合條件的k+1項集生成，則table_2為k+1相關聯項，根據需要可對其進行保存。

第五步：k=k+1；把table_2賦給bable_1，依次重復執行第三步，直到k項集為空集時終結。

4 關聯規則算法在教學質量評估系統中應用比較

將上述Apriori挖掘算法和基于篩選壓縮的Apriori算法采用C++語言實現。為了測試算法的性能，采用的數據是教學質量評估系統所提供的某系學生的對港等數學這門課的評價信息數據作為實驗測試數據。

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

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

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

5 結束語

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

參考文獻：

[1] Jiawei Han，Micheline Kamber.數據挖掘：概念與技術[M]. 北京: 機械工業出版社，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] 周劍雄，王明哲. 基于關聯規則的數據挖掘技術的快速算法[J].計算機工程，2003:48-92.

[6] 范明，孟小峰. 數據挖掘概念與技術[M].北京:機械工業出版社，2002.

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

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

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。”