黃毅杰，張藝雪

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

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

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

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

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

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

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

2 Apriori算法思想

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

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

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

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

圖1 Apriori算法的流程圖

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

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

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

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

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

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

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

4 實(shí)驗(yàn)分析

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

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

表2 矩陣D1

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

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

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

5 算法性能分析

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

圖2 算法比較

6 在教學(xué)評(píng)價(jià)模塊上的應(yīng)用

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

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

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

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

表3 項(xiàng)目信息表

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

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

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

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

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

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

7 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

[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].計(jì)算機(jī)工程與科學(xué)，2007(10):13-16.

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

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

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

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