一種基于矩陣的關聯規則算法的研究與應用

黃毅杰，張藝雪

(1.漳州職業技術學院 計算機工程系，福建 漳州363000；2.漳州衛生職業學院 信息技術部，福建 漳州363000)

關聯規則是數據挖掘技術的主要研究方向之一.1994年, Agrawal等人提出了關聯規則挖掘的經典算法Apriori[1].Apriori算法利用層次循環順序搜索的方法來挖掘頻繁項集，但該算法需要多次掃描數據庫并產生了大量的候選項集[2].

本文提出了一種基于矩陣的關聯規則算法，通過向量矩陣來表示事務數據庫，減少了掃描數據庫的次數，通過矩陣的運算快速生成k-項集.

1 關聯規則基本概念

假設項的集合為I={i1，i2，…，im}，在I中包含了m個不同的數據項.在給定的數據庫D中，所有的事務都包含在D中，T表示D中的每條事務，T是I中項的集合，使得T?I.每條事務T有唯一的TID標識.關聯規則如同A?B蘊涵式，其中，A?I,B?I，且A∩B=?.設A是I的子集，A的支持度S(A)是指D中出現A的概率，如果S(A)≥最小支持度(min_sup)，則稱A為頻繁項集.蘊涵式A?B具有支持度S(A?B)，其支持度是指A和B在D中同時發生的概率，即S(A?B)=P(A∪B)[3].

關聯規則的支持度和可信度分別體現出了規則發生的頻度和強度.

在事務數據庫D中找出同時滿足最小可信度(min_sup)和最小可信度(min_conf)是關聯分析的最終目的[4].

2 Apriori算法思想

Apriori算法的實現可分為兩步：

第一步是發現事務數據庫D中的所有支持度大于最小支持度的項集，這個工作是關聯規則的關鍵所在，具有較大的計算量，也是衡量算法性能的關鍵.

第二步是根據第一步識別出的頻繁項集提取出關聯規則[5].

Apriori算法的流程圖如圖1所示：

圖1 Apriori算法的流程圖

從Apriori算法的流程圖中可以看出，Apriori算法需要多次反復掃描數據庫，產生較大的I/O消耗，在k=2的時候會產生大量的候選項集，特別是在挖掘較大型的數據庫關聯規則時，使得效率降低.

3 基于矩陣的關聯規則算法

算法的改進思想是通過把事務數據庫轉換為向量矩陣減少掃描數據庫次數，在K=2時，采用轉化后的矩陣乘以其轉置矩陣的方法得到較少的候選項集，提高效率.算法步驟如下：

(1)轉換矩陣：掃描一遍數據庫，把事務數據庫D轉換為向量矩陣Am×n，矩陣的行代表D中的每條事務，矩陣的列代表D中數據項，其中，

(2)生成頻繁1-項目集：按順序求各列向量的數量積，在結果中統計1的數量，這個數量值即項目I的支持度計數support_count(Ij)，如果support_count(Ij)/n>最小支持度(min_sup),則Ij項的組合為頻繁1-項目集，否則Ij為非頻繁1-項目集，刪除該項所在的列，按照支持度計數由小到大排序，生成矩陣D1.

(3)生成頻繁2-項目集：通過D1乘以D1的轉置矩陣得到S，如果S矩陣右上角的數據Sij>min_sup，則Sij項的組合為頻繁2-項目集[6]，對滿足min_sup的Sij的數據修改為“1”，其余改為“0”，生成矩陣D2.

(4)裁剪矩陣，產生k-項集：實際上往往L中的有些頻繁(k-1)-項目集已經對Lk-1的生成沒有作用，計算Lk-1各個項目出現的頻度，如果其中有項目的頻度小于k-1，則刪除該項目所在的項目集，以此減少產生不必要的候選項集.通過對Lk-1的連接和剪枝，產生頻繁k-項集.

4 實驗分析

事務數據庫如表1所示，設定最小支持度計數2，

表1 事務數據庫

表2 矩陣D1

對各個項集進行支持度計數，每個項集都滿足最小支持度，生成矩陣D1，如表2所示.其中L1為{I1:2,I2:3,I3:4,I4:2,}

通過D1乘以D1的轉置矩陣得到S，其中L2為{I2I3:3,I2I4:2,I3I4:2}

通過L2連接得到L3為{I2I3I4}，由L3可知不會產生頻繁4-項集，算法停止.

5 算法性能分析

本文提出的算法把事務數據庫轉換為向量矩陣，不再掃描原始的事務數據庫，向量矩陣只存儲0和1數據，大大減少了占用的空間，特別是在大數據集上更能體現其運算效率.圖2為本文算法與Apriori算法在測試事務數據庫，在最小支持度設為2%，事務從500到8 500的增加過程中的算法的執行時間比較結果.從圖中可以看出，隨著事務的增加，本文提出的算法的運行時間優勢更為明顯.

圖2 算法比較

6 在教學評價模塊上的應用

學生對教師的教學評價可以體現出該教師在教學過程中給學生留下印象的好壞，體現出該教師的教學效果等，通過關聯分析學生對教師的教學評價，挖掘出教學質量與教師的一些性質的關聯規則對高校的師資引進、師資建設、師資配置的決策起到重要作用.

學生評價表主要包含了教學態度、教學水平、教學方法、教學效果等四個一級指標，總的包含16個二級指標.教師任課班級的學生對18個二級指標進行評分，取其平均分并用五級制來體現學生評價的最終結果.

本文的數據來源于某高職教學管理系統數據庫，并通過一定方式去除了一些異常信息，如有些學生的評價分全為0，有些學生的評價時間只有幾秒鐘等.

本文的挖掘對象主要在教師的職稱、學歷、任職時間、性別和評價得分等級，其中職稱包含助教、講師、副教授、教授，項目用{I1，I2，I3，I4}表示；學歷包含本科、碩士、博士，項目用{I5，I6，I7}表示；任教時間包含<5年、6～10年、11～15年、>16年，項目用{I8，I9，I10，I11}表示；性別包含男、女，項目用{I12，I13}表示；評價得分等級包含優、良、中、合格、不合格，項目用{I14，I15，I16，I17，I18}表示.通過項目表示教師信息如表3所示.

表3 項目信息表

根據本文提出的算法，將事務數據庫轉換為向量矩陣，如表4所示.

表4 轉換后的矩陣

運用本文提出的算法對轉換后的矩陣進行挖掘，設最小支持度為15%，最小可信度為50%，得到以下典型關聯規則，如表5所示.

表5 典型關聯規則

由上表可以看出，如第1條關聯規則中表示，在數據庫中，有26.8%的記錄為講師，碩士，任職時間11～15年的，在這26.8%的記錄中，有53.3%的評價等級為優秀；在第二條關聯規則中表示，在數據庫中，有32.6%的記錄為助教，碩士，任職時間<5年的，在這32.6%的記錄中，有91.3%的評價等級為中.

通過這些關聯規則可以看出學歷、職稱層次較高和任職時間較長的教師的評價等級都比較高，為了提高高校教師教學效果，應鼓勵青年教師提高學歷層次，通過“老帶新”的方式，提高高校教師的教學水平.

7 結束語

本文介紹了數據挖掘中關聯規則的概念和Apriori算法的基本思想，提出了一種基于矩陣的關聯規則算法，并運用該算法于高校教學評價系統中，通過對學生評價結果進行關聯規則的挖掘，可以對學校進一步提高教學效果起到客觀的參考作用.

參考文獻：

[1]Jaeger T,Sailer R,Shankar U.PRIMA:Policy-reduced Integrity Measurement Architecture[C]//Proc.of the 11th ACM Symposium on Access Control Models and Technologies.Lake Tahoe,USA:[s.n.],2006:19-28.

[2]劉星沙，譚利球，熊擁軍.關聯規則挖掘算法及其應用研究[J].計算機工程與科學，2007(10):13-16.

[3]廖琴，郝志峰，陳志宏.數據挖掘與數學建模[M].北京：國防工業出版社，2010:74-75.

[4]劉獨玉,楊晉浩,鐘守銘.關聯規則挖掘研究綜述[J].成都大學學報,2006,25(1):54-58.

[5]HAN Jia-wei，KAMBER M.數據挖掘概念與技術[M].范明，孟小峰，等譯.北京:機械工業出版社,2001:149-179.

[6]黃龍軍，段龍鎮，章志明.一種基于上三角項集矩陣的頻繁項集挖掘算法[J].計算機應用研究,2006(11):25-26,40.