完全加權正負關聯規(guī)則挖掘及其在教育數據中的應用

余 如,朱朝陽,黃名選

(1. 廣西教育學院 黨政辦, 廣西 南寧 530023；2. 廣西教育學院 數計系, 廣西 南寧 530023)

關聯規(guī)則挖掘是數據挖掘研究中的一個重要分支，具有極廣泛的應用前景，已經成為一個日益流行而重要的研究熱點。現有的正負關聯規(guī)則挖掘研究可以分為項無加權正負關聯規(guī)則挖掘、項加權正負關聯規(guī)則挖掘以及項完全加權正負關聯規(guī)則挖掘等3類。

項無加權正負關聯規(guī)則挖掘只考慮項集在數據庫中出現的頻度，將數據庫中各個項目以平等一致的方式處理，不考慮項集在數據庫及各個事務中的重要性，其典型的挖掘算法是1993年Agrawal 提出的Apriori算法[1]。此后在Apriori算法的基礎上，出現了一些改進的挖掘算法，例如,FP-growth算法[2]等。1997年，Brin等首次提出關聯規(guī)則中存在否定關系[3]，2004年，Wu等提出一種有效的挖掘正負關聯規(guī)則算法[4]。近幾年來，學者們從不同角度和方法提出了有效的正負關聯規(guī)則挖掘算法[5-8]。

項加權正負關聯規(guī)則挖掘更關注數據庫中各個項目之間具有不同的權值，項權值在事務數據庫中固定不變，例如，超市里商家更關注的是利潤高的商品的模式挖掘，根據其利潤高低給每個商品賦予不同的權值。1998年以來，項加權關聯規(guī)則挖掘技術得到了廣泛的重視和研究，其典型的算法有1998年Cai等提出的MINWAL算法[9]，以及Nagaraju、Tanden等提出的加權關聯規(guī)則挖掘算法[10-12]等。項加權負關聯規(guī)則挖掘在2008年以后得到了更多的關注，一些典型的加權正負關聯規(guī)則挖掘算法[13-15]被提出。加權負關聯規(guī)則和加權正關聯規(guī)則一樣具有同等的重要性，在期望有利因素出現時，是否存在不利因素，通過負關聯規(guī)則分析可以發(fā)現各種可能不利因素。

現有項加權正負關聯規(guī)則挖掘雖然重視數據庫中各項目之間具有不同權值，但該權值通常由用戶根據各項目的重要程度設定，相對數據庫中各個事務記錄固定不變。然而，客觀世界中，存在著大量完全加權數據，其項目權值不是由用戶設定，而是分布在數據庫的各個事務記錄中，其權值隨事務記錄的不同而變化。例如，文本數據庫中各個特征詞在不同的文檔記錄中具有不同的權值。把項權值隨著事務記錄不同而變化的數據叫完全加權數據，也叫矩陣加權數據。面對著海量完全加權數據，現有加權正負關聯規(guī)則挖掘技術不再適用。2003年，譚義紅等提出了完全加權關聯規(guī)則挖掘算法[15]，隨后，一些改進算法[16]相繼被提出，有效地解決了完全加權關聯規(guī)則的挖掘，但還解決不了完全加權負關聯規(guī)則挖掘問題。然而，完全加權負關聯規(guī)則與其正規(guī)則一樣具有同等的重要性，在web海量信息處理、文本分類和聚類、信息檢索、跨語言信息檢索、查詢擴展等領域具有重要的應用價值。針對上述問題，本文提出了一種新的基于概率比和興趣度的完全加權正負關聯規(guī)則挖掘算法，給出與其相關的概念和定理，并探討算法在教育數據和文本數據中的應用。算法以概率比代替?zhèn)鹘y的置信度，采用支持度—概率比-興趣度架構衡量完全加權正負關聯規(guī)則，獲得很好的挖掘效果。與現有無加權正負關聯規(guī)則挖掘算法比較，本文提出的算法更有效、更合理，具有較高的理論價值和應用前景。

1 基本概念

設D={d1,d2,…,dn}是完全加權數據庫，di(1≤i≤n)表示D中的第i條事務記錄，I={i1,i2,…,im}表示D中所有項目集合,ij(1≤j≤m)表示D中第j個項目，w[di][ij] (1≤i≤n, 1≤j≤m)表示項目ij在事務記錄di中的權值，顯然，項目ij的權值分布在不同的事務記錄中，隨著不同的記錄而變化，如果ijdi，則ij在該事務記錄di的權值w[di][ij]=0。

對于完全加權數據庫D，設I1,I2是其項集I的兩個子項集，I1?I，I2?I且，I1∩I2=，參照傳統的支持度和置信度概念，給出如下基本定義。

定義1(完全加權項集支持度:all-weighted support,簡稱awsup)[15]

完全加權負關聯規(guī)則支持度的計算公式如式(2)至式(5)：

定義2(完全加權概率比： all-weighted probability ratio,簡稱awPR) PR模型[4]是用條件概率和先驗概率的比值來表達p(I2|I1)相對p(I2)的遞增程度，如式(6)所示。

本文采用完全加權概率比(awPR)代替?zhèn)鹘y的置信度對完全加權正負關聯規(guī)則進行評價，完全加權正負關聯規(guī)則的awPR計算公式如式(7)至式(10)所示。

定義3(完全加權興趣度： all-weighted interest，簡稱awInt) 興趣度的度量被廣泛應用于關聯規(guī)則的評價，從概率論角度考察興趣度，它反映了關聯規(guī)則前件和后件的關系和密切程度。本文采用基于概率論的興趣度模型對完全加權正負關聯規(guī)則進行評價，挖掘出有趣的完全加權正負關聯規(guī)則。參照文獻[13]的興趣度公式，給出如下完全加權關聯規(guī)則(I1→I2)的興趣度公式,即式(11)。

定理設(I1,I2)是完全加權項集，如果正關聯規(guī)則I1→I2是有趣的，那么其負關聯規(guī)則I1→I2，I1→I2和I1→I2也是有趣的，即存在：

awInt(I1→I2)=awInt(I1→I2)=awInt(I1→I2)=awInt(I1→I2)

證明：

因為：awInt.(I1→I2)

=|awsup(I1∪I2)-awsup(I1)awsup(I2)|

=|awsup(I1)awsup(I2)-awsup(I1∪I2)|

=awInt.(I1→I2)

awInt.(I1→I2)

=|awsup(I1∪I2)-awsup(I1)awsup(I2)|

=|awsup(I1)awsup(I2)-awsup(I1∪I2)|

=awInt.(I1→I2)

awInt(I1→I2)

=|awsup(I1∪I2)-awsup(I1)awsup(I2)|

=|awsup(I1∪I2)-awsup(I1)awsup(I2)|

=awInt.(I1→I2)

所以，I1→I2和I1→I2，I1→I2以及I1→I2的興趣度是一樣的，表明了如果正關聯規(guī)則I1→I2是有趣的，同樣可以知道，I1→I2，I1→I2以及I1→I2也是有趣的。

定義4(有趣的完全加權強正關聯規(guī)則) 如果正關聯規(guī)則(I1→I2)滿足以下5個條件，就稱為完全加權強正關聯規(guī)則I1→I2： (1)awsup(I1)≥minaws；(2)awsup(I2)≥minaws；(3)awsup(I1∪I2)≥minaws；(4)awPR(I1→I2)≥minawc;(5) awInt(I1→I2)≥minawInt，其中，minaws，minawc和minInt分別為最小完全加權支持度閾值，最小完全加權置信度閾值和最小完全加權興趣度閾值。

定義5(有趣的完全加權強負關聯規(guī)則) 如果完全加權負關聯規(guī)則(I1→I2)滿足以下5個條件，就稱為完全加權強負關聯規(guī)則I1→I2： (1)awsup(I1)≥minaws；(2)awsup(I2)≥minaws；(3)awsup(I1∪I2)≥minaws；(4)awPR(I1→I2)≥minawc;(5) awInt(I1→I2)≥minInt。

2 基于概率比和興趣度的完全加權正負關聯規(guī)則挖掘算法

2.1 完全加權正負關聯規(guī)則的評價標準及其規(guī)則挖掘策略

傳統的關聯規(guī)則挖掘中，支持度—置信度架構作為關聯規(guī)則的評價標準，其缺點是該評價方式導致虛假的、冗余的、無效的規(guī)則出現，也很容易出現相互矛盾的規(guī)則。為此，支持度—置信度—相關度架構[14]被提出作為評價正負規(guī)則的標準，有效地避免了相互矛盾的規(guī)則，然而，這種評價也避免不了一些無趣的、甚至無效的規(guī)則出現。針對該問題，本文提出采用支持度—概率比—興趣度架構作為完全加權正負關聯規(guī)則的評價標準。概率比是用條件概率和先驗概率的比值來表達p(I2|I1)相對p(I2)的遞增程度，能很好地區(qū)分正負關聯規(guī)則。興趣度能有效地衡量關聯規(guī)則的有效性，若興趣度awInt>=minawInt(最小加權興趣度閾值)，則該完全加權關聯規(guī)則是有趣的，有意義的，反之沒有意義。

基于支持度-概率比-興趣度架構的完全加權關聯規(guī)則挖掘策略是： 設I是完全加權項集，I1和I2是I的子集，I1∪I2?I,I1∩I2=，最小完全加權支持度閾值(minaws), 最小完全加權PR閾值 (minawc)和最小完全加權興趣度閾值(minawInt)都大于0并且由用戶指定，awsup(I1)≥minaws,awsup(I2)≥minaws，則，

(1) 如果awsup(I1∪I2)≥minaws,awPR(I1→I2)≥minawc, awInt(I1→I2)≥minawInt, 那么I1→I2是個有趣的完全加權強正關聯規(guī)則。

(2) 如果awsup(I1∪I2)≥minaws,awPR(I1→I2)≥minawc, awInt(I1→I2)≥minawInt, 那么I1→I2是個有趣的完全加權強負關聯規(guī)則。

(3) 如果awsup(I1∪I2)≥minaws,awPR(I1→I2)≥minawc, awInt(I1→I2)≥minawInt, 那么I1→I2是個有趣的完全加權強負關聯規(guī)則。

(4) 如果awsup(I1∪I2)≥minaws,awPR(I1→I2)≥minawc, awInt(I1→I2)≥minawInt, 那么I1→I2是個有趣的完全加權強負關聯規(guī)則。

2.2 算法基本思想

首先對完全加權數據進行預處理，構建完全加權數據庫(awDatabase)和特征詞項目庫;然后，對awDatabase數據庫挖掘完全加權頻繁1-項集和負1-項集，從2-項集起，利用k-項集的k-支持期望[15](k≥2)和最小完全加權支持度閾值，通過逐層搜索的方法產生頻繁k-項集和負k-項集；最后，采用支持度-概率比-興趣度架構對關聯規(guī)則進行評價，從頻繁項集和負項集中挖掘完全加權正負關聯規(guī)則。

2.3 算法設計

算法： Mining both Positive and Negative All-weighted Association rules Based on Probability Ratio and Interest (簡稱MPNAWARofPRI)

輸入： awD： 完全加權數據，minaws： 最小完全加權支持度閾值，

minawc： 最小完全加權PR閾值，minawInt： 最小完全加權興趣度閾值。

輸出： 完全加權正負關聯規(guī)則。

Begin

1) 將完全加權數據awD進行預處理，構建完全加權數據庫(awDatabase)和特征詞庫。

2) 從awDatabase中提取完全加權候選1-項集(awC1)，累加awC1在awDatabase中的權值及其支持數，計算其支持度和完全加權2-項集的2-支持期望，根據awC1的支持度與最小完全加權支持度閾值minaws比較得到完全加權頻繁1-項集和負1-項集。

3)awCi-1(i≥2)進行Apriori連接[1]生成完全加權候選i-項集awCi。

4) 在awCi中提取含有i-支持期望的(i-1)-項集的并且其支持度大于0的候選i-項集作為完全加權負i-項集，同時刪除awCi中含有i-支持期望的(i-1)-項集的所有候選i-項集。

5) 如果awCi不空，計算其支持度及其候選i-項集的i-支持期望的，同時刪除其支持數為0的候選i-項集。

6) 根據候選i-項集awCi的支持度與minaws比較，獲得完全加權頻繁i-項集和負i-項集。

7) i加1，重復3)到6)步，直到awCi為空，挖掘結束，轉入8)步。

8) 對于完全加權頻繁項集或負項集中的每一個項集Item，若存在每一個項集(I1∪I2)=Item，(I1∩I2)=,awsup(I1)≥minaws，awsup(I2)≥minaws，則，

① 如果awsup(I1∪I2)≥minaws,awPR(I1→I2)≥minawc, awInt(I1→I2)≥minawInt, 則得出完全加權正關聯規(guī)則I1→I2。

② 如果awsup(I1∪I2)≥minaws,awPR(I1→I2)≥minawc, awInt(I1→I2)≥minawInt, 則得出完全加權強負關聯規(guī)則I1→I2。

③ 如果awsup(I1∪I2)≥minaws,awPR(I1→I2)≥minawc, awInt(I1→I2)≥minawInt,則得出完全加權強負關聯規(guī)則I1→I2。

④ 如果awsup(I1∪I2)≥minaws,awPR(I1→I2)≥minawc, awInt(I1→I2)≥minawInt, 則得出完全加權強負關聯規(guī)則I1→I2。

9) 輸出完全加權正負關聯規(guī)則(I1→I2，I1→I2，I1→I2，I1→I2)。

End.

3 實驗設計及其結果分析

3.1 實驗設計及其結果

為了驗證本文MPNAWARofPRI算法的有效性，探討其在教育信息化數據關聯模式控制中的應用，采用文本數據(數據測試集1)和真實的教育數據(數據測試集2)作為實驗數據測試集。

數據測試集1： 從網上下載730篇文檔作為實驗用的完全加權文本數據測試集。對測試集1進行預處理，即分詞、去停用詞和提取特征詞并計算權值，建立基于向量空間的完全加權數據庫和完全加權特征詞項目庫。預處理后數據集參數如下： 總文檔數為720，總特征詞數為563，以一個特征詞作為一條記錄，完全加權數據庫總記錄數為175 608， 每篇文檔平均特征詞數量為243個；將特征詞文檔頻率(即出現該特征詞的文檔篇數)不小于13的特征詞提取出來構建完全加權特征詞項目庫，供實驗中挖掘關聯規(guī)則用，完全加權特征詞項目庫的特征詞數為50，其文檔頻率最高為155，最低是13。

數據測試集2： 主要驗證本文算法對教育信息化數據關聯模式挖掘的有效性，實驗數據來源于本校教務真實的課程考試成績數據。選擇歷屆畢業(yè)生在校學習成績?yōu)閿祿y試集2。把課程作為項目，課程成績作為項目權值，將成績權值規(guī)范化為0到1之間，將每個學生信息作為一個事務記錄，構建學生信息數據庫和課程項目庫。數據測試集2參數如下： 課程項目總個數是121，學生總數為2 000人，即事務記錄數為2 000。

將基于相關性的項無加權正負關聯規(guī)則挖掘算法[7]作為對比算法(即MPNARForQE算法, 進行該算法的實驗時，將查詢詞設計為空集)，與本文MPNAWARofPRI算法進行挖掘性能比較，分完全加權支持度閾值變化、置信度閾值變化以及興趣度閾值變化等三種情況進行實驗，實驗結果如下。

(1) 完全加權興趣度和置信度不變，在不同完全加權支持度閾值下兩種算法挖掘的關聯規(guī)則數量比較，結果如表1和表2所示。

表1 在不同完全加權支持度閾值下關聯規(guī)則數量比較(測試集1)(minawc=0.000 5, minawInt=0.000 1,項目總數=50)

表2 在不同完全加權支持度閾值下關聯規(guī)則數量比較(測試集2)(minawc=0.5, minawInt=0.1,項目總數=50)

(2) 完全加權支持度閾值和興趣度閾值不變，在不同的最小完全加權置信度閾值下兩種算法挖掘的關聯規(guī)則數量比較，結果如表3和表4所示。

(3) 完全加權支持度閾值和置信度閾值不變，在不同完全加權興趣度閾值下本文算法挖掘的關聯規(guī)則數量比較，結果如表5和表6所示。

表3 在不同的最小完全加權置信度閾值下關聯規(guī)則數量比較(測試集1)(minaws=0.005, minawInt=0.001,項目總數=50)

表4 在不同完全加權置信度閾值下關聯規(guī)則數量比較(測試集2)(minaws=0.3, minawInt=0.1,項目總數=50)

表5 在不同興趣度閾值下本文算法挖掘的關聯規(guī)則數量比較(測試集1) (minaws=0.005, minawc =0.0005,項目總數=50)

3.2 實驗結果分析

從表1和表2可知，在不同最小完全加權支持度閾值下，本文MPNAWARofPRI算法挖掘文本數據的正負關聯規(guī)則數量比對比算法挖掘的數量少，其中，文本數據正關聯規(guī)則的數量平均下降70.08%，教育數據正關聯規(guī)則的數量平均下降49.09%，文本數據負關聯規(guī)則,A→B的數量平均下降71.97%，文本數據負關聯規(guī)則A→B和A→B的數量分別平均下降51.75%和46.44%，教育數據負關聯規(guī)則A→B的數量平均下降74.44%。

表6 在不同興趣度閾值下本文算法挖掘的關聯規(guī)則數量比較(測試集2) (minaws=0.3, minawc =0.5,項目總數=50)

從表3和表4看出，在不同的最小完全加權置信度閾值下，與對比算法比較，本文算法挖掘的正負關聯規(guī)則數量也大幅度下降，特別是負關聯規(guī)則數量下降幅度比較大，其中，文本數據正關聯規(guī)則數量平均下降66.10%，而教育數據正關聯規(guī)則數量僅下降7.86%，文本數據負關聯規(guī)則A→B的數量平均下降73.29%，A→B和A→B的數量分別平均下降87.86%和90.74%，教育數據負關聯規(guī)則A→B數量下降幅度也比較大，達66.72%。表5和表6表明，隨著完全加權興趣度閾值的增大，本文算法挖掘的教育數據正負關聯規(guī)則以及文本數據負關聯規(guī)則的數量也逐步減少，而文本數據正關聯規(guī)則數量變化不大。

表2、4和6的結果表明，本文MPNAWARofPRI算法和對比算法對教育數據測試集的挖掘只得到正關聯規(guī)則A→B和形如A→B的負關聯規(guī)則，沒有挖掘出形如A→B和A→B的負規(guī)則。實驗結果說明了2種挖掘算法是有效的、合理的，主要原因是： 教育數據是由各個課程項目組成的學生記錄集合，項目權值(即課程成績)分布均勻并且其值比較大，而且項目在每個學生信息記錄出現的頻度都很高，挖掘出的頻繁項集較多，而非頻繁項集(即負項集)很少，這樣挖掘出的正關聯規(guī)則A→B和形如A→B的負關聯規(guī)則就較多，形如A→B和A→B的負規(guī)則出現很少，甚至沒有。例如，挖掘出關聯規(guī)則“英語語法→英語翻譯”(說明學好《英語語法》課程就能學好《英語翻譯》課程)、“英語口語→旅游英語”(說明學不好《英語口語》課程就很難學好《旅游英語》課程)是合理的，如果挖掘出負關聯規(guī)則“英語語法→英語翻譯”(說明學不好《英語語法》就能學好《英語翻譯》課程)、“英語口語→旅游英語”(說明學好了《英語口語》就學不好《旅游英語》課程)，那就不合理了。

實驗結果表明，與現有無加權正負關聯規(guī)則挖掘算法比較，本文提出的基于概率比和興趣度的完全加權正負關聯規(guī)則挖掘算法更有效、更合理，挖掘出的正負關聯規(guī)則數量少得多。其主要原因是本文算法不僅考慮項目的頻度，還考慮項目在各個事務記錄中具有不同的權值，更重要的是本文算法采用完全加權支持度—概率比—興趣度的關聯規(guī)則評價標準，避免了那些無效的、無趣的規(guī)則出現，規(guī)則數量就變少了。對比算法只考慮項目出現的頻度，沒有考慮項集在數據庫中各個事務記錄具有不同的重要性，這樣的處理是不合理的，因而挖掘出無效的規(guī)則也會增多。另外，對比算法采用支持度—置信度—相關度架構評價關聯規(guī)則，雖然避免了互相矛盾的規(guī)則出現，但很難避免那些無趣的規(guī)則產生，因此，對比算法挖掘出的規(guī)則比本文算法挖掘的多得多，和實驗結果是一致的。

4 結論

針對現有加權正負關聯規(guī)則挖掘算法不能適用完全加權數據挖掘的缺陷，本文提出了一種新的基于概率比和興趣度的完全加權正負關聯規(guī)則挖掘算法(即MPNAWARofPRI算法)，給出與其相關的概念和定理，有效地解決了完全加權數據挖掘問題，同時探討了算法在教育數據和文本數據中的應用，取得了有價值的研究成果。該算法以概率比代替?zhèn)鹘y的置信度，采用支持度—概率比—興趣度架構衡量完全加權正負關聯規(guī)則，獲得很好的挖掘效果。實驗結果表明，本文提出的算法是有效的，在文本分類和聚類、信息檢索、跨語言信息檢索、查詢擴展等領域有很高的應用價值。

[1] R Agrawal,T Imielinski,A Swami. Mining association rules between sets of items in large database[C]//Proceeding of the 1993 ACM SIGMOD International Conference on Management of Data, Washington D.C.,1993: 207-216.

[2] J Han, J Pei, Y Yin. Mining frequent patterns without candidate generation[R]. Technical Report TR-99-12, Computing Science Technical Report, Simon Fraser University, 1999(10).

[3] Sergey Brin, Rajeev Motwani, Craig Silverstein. Beyond market baskets: generalizing association rules to correlations[C]//Proceedings of the 1997 ACM SIGMOD international conference on Management of data. Tucson, Arizona. 1997. UAS:ACM press, 1997: 265-276.

[4] Xindong Wu, Chengqi Zhang, Shichao Zhang. Efficient Mining of Both Positive and Negative Association Rules[J].ACM Transactions on Information Systems, 2004,22(3): 381-405.

[5] Hong Li,Xuegang Hu. Efficient Mining of Strong Negative Association Rules in Multi-Database[C]//Procceedings of the International Conference on Computational Intelligence and Software Engineering, 2009.

[6] B Ramasubbareddy, A Govardhan， A Ramamohanreddy. Mining Positive and Negative Association Rules[C]//Procceedings of the IEEE ICSE 2010, Hefei, China, August 2010.

[7] 黃名選,朱家安,陳燕紅.面向查詢擴展的詞間正負關聯規(guī)則挖掘算法[J].計算機工程與應用,2011,47(26):151-155，

[8] David Taniar, Wenny Rahayu,et al.Mining Hierarchical Negative Association Rules[J].International Journal of Computational Intelligence Systems, 2012,5(3): 434-451.

[9] C H Cai, A da, W C Fu, et al. Mining Association Rules with Weighted Items [C]// Proceedings of IEEE International database Engineering and Application Symposiums, 1998: 68-77.

[10] He Jiang,Yuanyuan Zhao. Mining Positive and Negative Association Rules with Weighted Items[C]//Proceedings of the DCABES2008,China,2008:450-454.

[11] Russel Pears， Yun Sing Koh.Weighted Association Rule Mining Using Particle Swarm Optimization[C]//Proceedings of the PAKDD 2011 Workshops, LNAI 7104, pringer-Verlag Berlin Heidelberg 2012，2012:327-338.

[12] Jun Tan. Weighted Association Rules Mining Algorithm Research[J].Applied Mechanics and Materials,Volumes 241-244,2013(241-244)： 1598-1601.

[13] H Jiang,Y Y Zhao, X J Dong. Mining Positive and Negative Weighted Association Rules from Frequent Itemsets Based on Interest[C]//Proceedings of the 2008 International Symposium on Computational Intelligence and Design, IEEE Computer Society, 2008: 242-245.

[14] Y Y Zhao, H Jiang, R Geng, et al. Mining Weighted Negative Association Rules Based on Correlation from Infrequent Items[C]//Proceedings of the 2009 International Conference on Advanced Computer Control, IEEE Computer Society, 2009: 270-273.

[15] He Jiang, Xiumei Luan, Xiangjun Dong. Mining Weighted Negative Association Rules from Infrequent Itemsets Based on Multiple Supports[C]//Proceedings of the 2012 International Conference on Industrial Control and Electronics Engineering, IEEE Computer Society, 2012:89-92.

[15] 譚義紅,林亞平.向量空間模型完全加權關聯規(guī)則的挖掘[J].計算機工程與應用,2003(13):208-211.

[16] 黃名選,嚴小衛(wèi),張師超. 基于文本庫的完全加權詞間關聯規(guī)則挖掘算法[J].廣西師范大學學報,2007,25(4):24-27.