一種基于矩陣的關(guān)聯(lián)規(guī)則算法的研究與應(yīng)用

黃毅杰，張藝雪

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

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

本文提出了一種基于矩陣的關(guān)聯(lián)規(guī)則算法，通過向量矩陣來表示事務(wù)數(shù)據(jù)庫，減少了掃描數(shù)據(jù)庫的次數(shù)，通過矩陣的運算快速生成k-項集.

1 關(guān)聯(lián)規(guī)則基本概念

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

關(guān)聯(lián)規(guī)則的支持度和可信度分別體現(xiàn)出了規(guī)則發(fā)生的頻度和強度.

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

2 Apriori算法思想

Apriori算法的實現(xiàn)可分為兩步：

第一步是發(fā)現(xiàn)事務(wù)數(shù)據(jù)庫D中的所有支持度大于最小支持度的項集，這個工作是關(guān)聯(lián)規(guī)則的關(guān)鍵所在，具有較大的計算量，也是衡量算法性能的關(guān)鍵.

第二步是根據(jù)第一步識別出的頻繁項集提取出關(guān)聯(lián)規(guī)則[5].

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

圖1 Apriori算法的流程圖

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

3 基于矩陣的關(guān)聯(lián)規(guī)則算法

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

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

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

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

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

4 實驗分析

事務(wù)數(shù)據(jù)庫如表1所示，設(shè)定最小支持度計數(shù)2，

表1 事務(wù)數(shù)據(jù)庫

表2 矩陣D1

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

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

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

5 算法性能分析

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

圖2 算法比較

6 在教學評價模塊上的應(yīng)用

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

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

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

本文的挖掘?qū)ο笾饕诮處煹穆毞Q、學歷、任職時間、性別和評價得分等級，其中職稱包含助教、講師、副教授、教授，項目用{I1，I2，I3，I4}表示；學歷包含本科、碩士、博士，項目用{I5，I6，I7}表示；任教時間包含<5年、6～10年、11～15年、>16年，項目用{I8，I9，I10，I11}表示；性別包含男、女，項目用{I12，I13}表示；評價得分等級包含優(yōu)、良、中、合格、不合格，項目用{I14，I15，I16，I17，I18}表示.通過項目表示教師信息如表3所示.

表3 項目信息表

根據(jù)本文提出的算法，將事務(wù)數(shù)據(jù)庫轉(zhuǎn)換為向量矩陣，如表4所示.

表4 轉(zhuǎn)換后的矩陣

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

表5 典型關(guān)聯(lián)規(guī)則

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

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

7 結(jié)束語

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

參考文獻：

[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]劉星沙，譚利球，熊擁軍.關(guān)聯(lián)規(guī)則挖掘算法及其應(yīng)用研究[J].計算機工程與科學，2007(10):13-16.

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

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

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

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