基于關聯規(guī)則與相似度的數據挖掘算法研究

李 英， 湯 庸

(華南師范大學計算機學院, 廣州 510631)

數據挖掘作為全球范圍內快速興起的一門交叉學科，結合了多個領域技術，包括數理統(tǒng)計、數據庫技術、人工智能和機器學習等領域的理論和技術. 一般意義上，數據挖掘的分析方法主要有人工神經網絡法、決策樹法、分類分析法、聚類分析法、關聯規(guī)則分析法和序列模式分析法等，針對不同領域的具體業(yè)務問題，選擇合適的分析方法可以得到更加有效的結果.

關聯規(guī)則分析是在數據集中找出各項之間的關聯關系的分析方法[1]，是數據挖掘中最活躍的研究方法之一. 1994年，AGRAWAL和SRIKANT[2]提出了基于頻繁集模式生成關聯規(guī)則的Apriori算法. 由于Apriori算法存在反復掃描數據庫的缺點, 許多學者在提升關聯規(guī)則算法效率以及不同應用領域進行了大量研究. 如：提出了對比規(guī)則集模式的SCR-Apriori算法，通過將模式結構的知識引入Apriori算法，顯著地縮減了待分析頻繁項集的搜索空間[3]；在傳統(tǒng)關聯規(guī)則支持度和置信度的基礎上，在領域數據中增加效用度和有趣度來消除關聯冗余，有助于挖掘出有效的關聯規(guī)則[4]；提出基于項權值排序的加權關聯規(guī)則挖掘算法，可用于各種語言的信息檢索，以改善檢索性能[5]；提出了基于權值向量矩陣約簡的Apriori算法，通過不斷約簡矩陣結構、降低源數據和候選項集規(guī)模，提高了運算效率[6]；對基于MapReduce模型的Apriori算法進行了改進，減少了數據庫掃描次數，且并行計算頻繁項集，提高了算法的效率[7]；綜合利用Word2Vec和K-means算法等技術，提出了一種無監(jiān)督Apriori學習算法來分析和挖掘地質大數據中的關聯規(guī)則，有效地挖掘礦床數據中的潛在關系和規(guī)律[8]；提出了基于層次分析法(AHP)和混合 Apriori-Genetic 的模型挖掘交通事故成因，提高挖掘的準確性[9]；提出一種具備自適應能力的規(guī)則生成框架來自動生成關聯規(guī)則，從而更好地識別未知網絡攻擊[10].

隨著教育信息化不斷發(fā)展，教育領域數據爆炸式增長，針對教育領域的數據挖掘也成為當前數據挖掘研究的一個新熱點. 應用不同的數據挖掘方法，可以更好地輔助學校進行合理的決策. 如：采用改進關聯規(guī)則挖掘算法，設計融合關聯規(guī)則挖掘算法的信息化教學管理系統(tǒng)，從系統(tǒng)數據庫內挖掘用戶各方面教育信息關聯數據[11]；利用Apriori算法挖掘出來的規(guī)則，結合最近鄰居算法，有效地預測學生學業(yè)的成功程度[12]；在排課過程中應用關聯規(guī)則，對高校排課進行優(yōu)化[13]；提出了一種基于決策樹的分類算法，為推薦系統(tǒng)模型選擇出最有價值的特征，有效提高了潛在好友推薦準確率[14]. 為了挖掘用戶感興趣的規(guī)則，提高挖掘的效率，本文提出了基于關聯規(guī)則和相似度的數據挖掘算法(U-APR)：首先，為解決Apriori算法頻繁掃描數據庫問題，一次性讀入數據并構建矩陣，并利用關聯規(guī)則支持度度量的特性來增加判斷屬性，以加快結束搜索過程；然后，對于初步挖掘的關聯規(guī)則，使用Jaccard相似度算法融合領域專家關注的信息去除冗余規(guī)則；最后，結合支持度、置信度和文本匹配度計算每一條規(guī)則推薦值，按推薦值由高到低輸出關聯規(guī)則. 并采用U-APR算法和目前常用的2種關聯規(guī)則算法，對某高校2016—2019級學生在2019年的繳費和學生獎助學金等財務數據進行挖掘.

1 預備知識

1.1 關聯規(guī)則挖掘

關聯規(guī)則挖掘是以某種方式分析數據源，并從數據集中發(fā)現有趣的關聯或相關關系，即從數據集中找出高頻出現的項目集，也稱為頻繁項集(簡稱頻繁集)，然后再利用這些頻繁集產生關聯規(guī)則的過程[15].

設I={i1,i2,…,in}是數據中所有項的集合，ik(k=1,2,…,n)稱為1個項，包含0個或多個項的集合稱為項集. 如果一個項集包含K個項，則稱其為K-項集. 滿足定義的最小支持度閾值的所有項集，稱作頻繁項集. 設D是任務相關的數據庫事務的集合，其中每個事務T是項的集合，是I的非空子集. 設X和Y是事務T中包含的2個項集，即X?T，Y?T. 若X≠?，Y≠?且X∩Y=?，則構成事務集D的關聯規(guī)則T：X?Y.

一般使用支持度和置信度2個重要的度量值來評價關聯規(guī)則的價值. 在關聯規(guī)則中，將X和Y同時出現的概率定義為關聯規(guī)則的支持度，即：

(1)

其中，P(X∪Y)表示同時包含項集X和項集Y的事務個數，|D|為事務數據庫記錄總數．

置信度是項集X發(fā)生的前提下，項集Y發(fā)生的概率，表示了這條規(guī)則有多大程度上值得可信，即：

(2)

通常用戶更關注的是支持度和置信度都高的強關聯規(guī)則. 為了對關聯規(guī)則進行量化和評估，需要設置最小支持度(min_sup)和最小置信度(min_conf)2個閾值，其中，0

項集的一個最重要的性質是它的支持度計數[16]，也就是包含特定項集的事務個數. 定義項集X的最小支持度計數為δ(X)=min_sup×|D|.

先驗性質的定義為：如果項集X是頻繁項集，則X的子集Y必為頻繁項集；如果項集Y是非頻繁項集，則Y的超集X一定為非頻繁項集. 一個項集X的支持度絕不會超過它的子集的支持度，稱為支持度度量的反單調性[16]. 關聯規(guī)則算法利用先驗性質和支持度度量的反單調性進行剪枝優(yōu)化，可以減少不必要的運算，提高算法效率.

1.2 基于相似度的關聯規(guī)則挖掘

基于相似性度量的算法種類繁多，不同領域、不同類型的數據適用于不同的相似性算法[17]. 其中，Jaccard相似系數[18]主要應用于計算文本相似度. 對于給定的集合A和集合B，Jaccard相似系數定義為

(3)

其取值范圍為[0,1]. 2個樣本點愈相似，則相似系數值愈接近1，反之則愈接近0. 由于最終挖掘的規(guī)則前件和后件都是文本的集合，為了量化規(guī)則與用戶目標的相關性，本文應用Jaccard相似系數來計算關聯規(guī)則與用戶目標文本的匹配度.

1.3 Apriori算法

Apriori算法[2]是關聯規(guī)則挖掘的經典算法，采用逐層搜索迭代的方法：首先，掃描數據庫產生候選集，利用最小支持度度量對候選集進行剪枝，得到新的頻繁項集，再由頻繁項集連接成新的候選集；不斷重復連接和剪枝過程，直到最終頻繁集為空時，結束迭代過程. 從算法的過程可以看出，在每次迭代過程中計算支持度時，都需要重復掃描數據庫，每次迭代過程中頻繁項集兩兩聯接生成新候選集，都會耗費大量的系統(tǒng)資源.

2 U-APR算法

2.1 對Apriori算法的改進

首先，一次性掃描數據庫，并將其表示為對應的矩陣，為減小矩陣規(guī)模，將重復事務壓縮為1行，增加權值向量；其次，利用支持度度量的反單調性，在剪枝過程中，每個候選集項集的支持度分別與最小支持度對比，刪減小于最小支持度的項集，減少新的候選集的生成數量. 算法增加了對候選集事務項個數與支持度計數大小的比較，加快結束算法迭代過程. 下面舉例說明改進算法的思想.

事務數據庫D={t1,t2,t3,t4,t5}中，每一組事務ti表示不同的顧客在商場一次購買商品的集合.D中所有T包含的項目的集合I={i1,i2,i3,i4,i5}. 事務集t1={i1,i2,i3,i5}、t2={i2,i3,i5}、t3={i1,i3,i4}、t4={i1,i3,i4}、t5={i2,i5}. 假設最小支持度min_sup=0.4，則最小支持度計數為min_sup×|D|=0.4×5=2.

改進算法的步驟如下：

步驟1：掃描數據庫，生成二進制矩陣M：

因為事務t3和事務t4包含相同的項集，按算法規(guī)則對M中相同行進行壓縮，得到矩陣M′和權值向量w：

w中的每一個數值表示相同事務的數量；對M中列、行合計，分別得到向量s=(3,3,4,2,3)、r=(4,3,3,2).

步驟2：刪除小于最小支持度計數2的i4列后，得到頻繁1-項集L1={i1,i2,i3,i5}. 連接1-項集得候選集{i1,i2}、{i1,i3}、{i1,i5}、{i2,i3}、{i2,i5}、{i3,i5}.

步驟3：事務項大于等于2的項集個數為6，大于最小支持度計數2. 經計算得到候選集的支持度計數分別為2、3、1、3、3、2，其中候選集{i1,i5}的支持度計數為1，小于最小支持度計數. 去除{i1,i5}后得到頻繁2-項集L2={{i1,i2},{i1,i3},{i2,i3},{i2,i5},{i3,i5}}.

步驟4：連接頻繁2-項集L2，得候選集{i1,i2,i3}、{i1,i2,i5}、{i1,i3,i5}、{i2,i3,i5},事務項大于等于3的項集個數為4. 根據支持度度量的反單調性，直接去除包含{i1,i5}的候選集{i1,i2,i5}和{i1,i3,i5}，對其余候選集進行邏輯與運算，經計算得到支持度計數均為2，從而得到頻繁3-項集L3={{i1,i2,i3},{i2,i3,i5}}.

步驟5：連接頻繁3-項集L3,得候選集{i1,i2,i3,i5}，事務項大于等于4的項集個數為1，小于最小支持度計數2，算法終止.

因此，事務數據庫D的頻繁項集L1、L2、L3分別為:

L1={i1,i2,i3,i5}；L2={{i1,i2},{i1,i3},{i2,i3},

{i2,i5},{i3,i5}}；L3={{i1,i2,i3},{i2,i3,i5}}.

2.2 結合用戶目標的關聯規(guī)則推薦

考慮到關聯規(guī)則挖掘應用在具體領域時，可能挖掘到的結果雖然是符合頻繁項集條件的強規(guī)則，但可能是用戶毫無興趣或者對解決實際問題幫助不大的規(guī)則. 為了量化關聯規(guī)則與用戶挖掘目標的相關性，本文利用Jaccard算法計算用戶目標字段與所挖掘的關聯規(guī)則的相似度，以衡量規(guī)則與用戶目標之間的相似性. 因此，本文在支持度、置信度這2個指標的基礎上增加目標文本匹配度指標match. 通過計算項集與用戶關注內容的文本的匹配指標，動態(tài)指定3個指標參數權重及閾值，計算每一條規(guī)則的推薦值，最終按推薦值由高到低輸出關聯規(guī)則結果.

首先，計算用戶目標文本與每條強關聯規(guī)則的文本匹配度，將匹配度為0的規(guī)則設為無效規(guī)則，再根據下式計算有效規(guī)則的推薦值：

value=λ1*Support(X,Y)+λ2*Confidence(X=>Y)+

λ3*match，

(4)

其中:Support(X,Y)為規(guī)則的支持度;Confidence(X=>Y)為規(guī)則的置信度;match=J(A,B)為目標文本的匹配度;λi為對應比重，由用戶指定. 根據計算出來的每一條規(guī)則的推薦值，由大到小排序，并按排序將挖掘的規(guī)則推薦給用戶.

3 數據挖掘實踐

實驗首先對廣東某高校學生繳費數據集進行了采集及預處理，然后采用U-APR算法對該數據集進行挖掘，最后與傳統(tǒng)Apriori算法、文獻[6]的算法進行了對比實驗.

3.1 數據采集

考慮到學校學生學費管理系統(tǒng)信息的不斷改革和升級，較早時期的學生相關數據存在不完善和信息缺失，因此，采集目前在校學生的基礎信息、學費收繳情況及學生補助發(fā)放情況的學生財務信息. 本文對廣東某高校在校學生學費管理系統(tǒng)數據進行采集，并選取其中的2016—2019級全體學生的2019年度學費繳費數據和補助發(fā)放數據作為研究數據，以學號為標識符，采集到的繳費信息為35 969條，主要有3類信息：學生的基本情況信息、學生繳費數據、學生獎/助學金發(fā)放數據. 包含的數據屬性為：姓名-學號-年級-學院-專業(yè)、收費年度-收費項目-應交學費-已繳學費、學號-獎學金發(fā)放金額-助學金發(fā)放金額-發(fā)放說明.

3.2 數據預處理

首先對采集到的樣本數據按以下步驟進行預處理：(1)由于學生的“姓名”“學號”屬于敏感信息，因此刪除學生“姓名”與“學號”這2項數據，隨機生成學生編號作為學生唯一識別碼；(2)因為系統(tǒng)收費過程中的數據可能存在學生因金額不足將一年學費拆分多次繳費、多繳費退費等問題，所以，針對不同情況，對數據進行分析后根據不同數據項進行不同形式的處理，最后得到真實繳費數據；(3)由于在實際高校收費情況中，學生根據文、理、藝術和體育等不同類別，按不同標準收費，與學生具體專業(yè)不直接相關，因此剔除“專業(yè)”屬性，保留“專業(yè)類型”屬性；(4)根據學生獎學金發(fā)放情況，將獲得國家獎學金、學業(yè)獎學金和優(yōu)秀學生獎學金等獎勵的學生設置為優(yōu)秀學生，其余學生設置為普通學生；(5)因為是對年度數據做關聯規(guī)則分析，所以將一年內分多次發(fā)放的補助進行合并，并按實際發(fā)放補助金額進行離散化處理，數據進行離散化后結果如表1所示；(6)因為本課題關注學生是否欠費，數據表增加字段“是否欠費”，用應繳學費減已繳學費，以生成學費是否欠費的屬性作為研究屬性. 按上述步驟處理完后，對學生繳費相關信息按照相應規(guī)則進行變量的離散化處理，結果見表2.

表1 學生補助離散化處理Table 1 The discretization of student allowance

表2 全部屬性的離散化整理分析Table 2 The discretization analysis of all attributes

3.3 采用U-APR算法的挖掘結果

程序對已做預處理的35 969條學生信息數據進行挖掘,其中包括本科生25 501人、碩士生9 690人、博士生778人. 設置了4組實驗參數進行最小支持度、最小置信度與關聯規(guī)則數量的相關性測試. 由4組實驗參數的結果(表3)可知：規(guī)則數與最小支持度、最小置信度負相關，隨著最小支持度和最小置信度的不斷增大，規(guī)則數相應減少，過大的閾值可能會將一些有趣的規(guī)則篩選掉，過小的閾值則可能產生太多的無用規(guī)則. 一般根據經驗值設置閾值可以得到適當數量的關聯規(guī)則，有利于提高分析效率.

表3 4組實驗參數下的關聯規(guī)則數

在能體現算法有效性的情況下，為了減少分析的復雜程度，本實驗選擇對最小支持度為0.4、最小置信度為0.9時產生的關聯規(guī)則(表4)做進一步去除冗余規(guī)則實驗：第一步，用戶選擇錄入目標文本“交費”時，系統(tǒng)根據式(3)計算規(guī)則的匹配度；第二步，設置權重系數λ1=0.3，λ2=0.4，λ3=0.3，按式(4)計算每一條關聯規(guī)則的推薦值；第三步，根據推薦值得到規(guī)則的結果. 由結果(表5)可知：在選定的閾值條件下，最終去除了18.75%的冗余規(guī)則.

表4 關聯規(guī)則結果Table 4 The mining results with the association rules

表5 基于用戶目標的推薦挖掘結果

3.4 對比實驗結果與分析

為了評估U-APR算法的性能，利用上述已預處理的學生數據集與Apriori算法、文獻[6]的算法進行了對比實驗，根據實驗結果對U-APR算法進行時間性能評估,同時進行冗余規(guī)則消除前后的規(guī)則數對比實驗.

實驗環(huán)境為: CPU為Intel Core(TM)i5-8265，主頻為1.80 GHz，內存為8 GB. 算法采用Python語言進行編寫，在Anaconda環(huán)境下進行編譯與運行.

由不同最小支持度下的3種算法的運行時間(圖1)可知：3種算法的運行時間均隨著最小支持度的增大快速減少，但當最小支持度為0.05時，U-APR算法的挖掘效率明顯高于其他2種算法. 究其原因為：U-APR算法采用一次性掃描數據庫，并利用支持度度量的反單調性不斷刪減非頻繁項集，加快了搜索過程，減少了存儲空間的占用；從時間復雜度方面來看，通過增加行和列判斷屬性，節(jié)約了剪枝步驟中頻繁項集的比較次數，減少了程序運行時間，提升了效率.

圖1 不同最小支持度下的運行時間

由最終輸出關聯規(guī)則數(圖2)可知：隨著最小支持度增大，3種算法挖掘的關聯規(guī)則數均明顯減少；在相同的最小支持度下，U-APR算法減少的冗余規(guī)則明顯多于另2個算法，究其原因為：U-APR算法按照用戶目標對關聯規(guī)則進行二次挖掘，有效去除冗余規(guī)則，減少最終挖掘的規(guī)則數量，可以有效提高用戶對挖掘結果分析的效率.

圖2 不同最小支持度下的關聯規(guī)則數

4 結語

本文提出基于關聯規(guī)則和相似度的數據挖掘算法(U-APR),該算法一次性讀入數據并構建矩陣，并利用關聯規(guī)則支持度度量的特性增加判斷屬性，以加快結束搜索迭代過程；然后，融合領域專家關注的目標，使用相似度算法去除冗余的關聯規(guī)則；最后，結合置信度、支持度和用戶目標匹配度生成推薦值，按推薦值大小對挖掘的規(guī)則排序輸出. 以高校學生實際繳費信息為樣本，U-APR算法與2種常用的關聯規(guī)則算法的對比實驗結果表明：U-APR算法減少了用戶不感興趣的冗余規(guī)則，提高了挖掘效率和減少存儲空間的占用.

本文通過對學生財務數據的挖掘，找出學生屬性與繳費、補助發(fā)放等行為之間的關聯性，可為高?？茖W決策和管理提供有效支持. 學校管理部門可根據挖掘到的關聯規(guī)則，完善學費管理辦法，如結合學校收費標準，對于在學校獲得高額(超過學費標準)補助和獎學金，但在沒有提出申請免交學費的情況下不按時繳納學費的同學給予誠信預警.

U-APR算法具有一般性，也適用于其他領域具有相似結構的數據研究. 在未來的工作中，將研究如何進一步提高大數據環(huán)境下關聯規(guī)則算法的效率.