基于位向量的關聯規則算法在教學評價中的應用研究

張永雄，余丙軍，鄧志虹

(1.廣州工商學院，廣東 廣州 510850；2.華南理工大學，廣東 廣州 510641)

基于位向量的關聯規則算法在教學評價中的應用研究

張永雄1，余丙軍2，鄧志虹1

(1.廣州工商學院，廣東 廣州 510850；2.華南理工大學，廣東 廣州 510641)

在研究和分析Apriori關聯規則算法缺陷的基礎上，設計了一種效率更高的基于位向量的矩陣關聯規則算法，通過實驗驗證了其可行性和有效性，并把該算法應用到教學評價中，挖掘出影響教學質量的相關因素，從而為學校改進教學管理工作提供客觀有效的決策分析方法。

位向量；Apriori算法；關聯規則；頻繁集

0 引言

數據挖掘是從大量的、不完全的、有噪聲的、模糊的、隨機的數據中，提取隱含在其中的、人們事先不知道的、但有時潛在信息和知識的過程[1]。關聯規則是數據挖掘重要方法的一種，它可以從給定的數據集中發現頻繁出現的項集，以及數據之間的聯系，可以找出滿足一定支持度和置信度的多個數據項的聯系。

本文提出一種基于位向量的關聯規則數據挖掘算法，對某學校部分教師的教學評價結果進行關聯分析，為教學管理部門對教學工作改進提出決策參考。

1 關聯規則與Apriori算法

1.1 關聯規則的描述

關聯規則反映了一種特定數據對象之間的聯系，它有支持度、置信度、提升度、影響度和改進度等等多個測量指標。本文選用支持度和置信度等兩個常用的測量指標作為研究內容。

假設有m個不同數據項組成的一個集合I={I1,I2,I3,…,Im}，在一個事務數據集T，其中每一個事務記錄T是I的一個非空子集，即T?I。對于任意一個非空的項目X(X?I)，如果記錄T包含X的所有數據項(即T?X)，則X的支持度可表示為:

關聯規則如果是X=>Y的表達式，其中X，Y是非空項集(X，Y≠Ф，X，Y=>I)，且X與Y不相交(X∩Y=Ф)，則X=>Y的支持度為：

Dsupp(X=>Y)=Dsupp(X∪Y)。

X=>Y的置信度為：

關聯分析的目的是找出所有不少于指定的最小支持度和最小置信度為約束條件的強關聯規則。

1.2 Apriori算法

由于所有項集的個數是2m-1(除去空集)，而計算一個項集的支持度至少需要遍歷掃描一次數據庫，則計算的復雜性是O(2m)，從中可知，這個過程是一個非常耗時并且效率低的方法。

但是，支持度有一個性質，即如果一個集合是頻繁集，則其子集也是頻繁集，因此，可以得出數學關系為：

Apriori算法是基于以上思路建立的，由Agrawal等人建立的[2-4]。Apriori算法采用一種逐層搜索的迭代方法，從k-項集來生產(k+1)-項集。首先找出頻繁1-項集，記為L1；然后利用頻繁1-項集L1來生產頻繁2-項集L2，不斷地循環，直到無法找到更多的頻繁k-項集為止。每生成一層Lk都需要掃描一次數據庫，而且會產生大量的候選集，這就是Apriori算法的缺陷。

2 基于位向量的關聯規則算法

2.1 算法思路及相關定義

在研究了傳統Apriori算法的缺陷之后，本文提出了一種基于位向量的關聯規則算法，其主要思路就是把事務數據庫的多次掃描和支持度計算轉化為0-1的位向量的計算，減少對數據庫的I/O操作，提高了數據挖掘的效率[5，6]。

定義1 假設一個含有n個事務Ti(i=1,2,3,…,n)，在項集I={I1,I2,I3,…,Im}，Ik在事務數據集T所對應的布爾向量Ik=[t1k,t2k,t3k,…,tnk]，其中，

定義2 項集Ij的支持度Dsupp(Ij)=

2.2 算法步驟

(1)構建矩陣，對含有m個不同數據項，n條事務的數據庫D，進行掃描，生成位向量矩陣An×m，其中，

(2)產生頻繁1-項集，統計結果中1的個數，記為count(Ij)，若count(Ij)少于最小支持度閥值，則從矩陣中刪除該列，否則保留，最后剩下的列就是頻繁1-項集。

(3)產生頻繁2-項集，對上一步產生的新矩陣中的列向量分別兩兩求內積，統計結果中1的個數，記為count(Iij)，若count(Iij)少于最小支持度閥值，則從矩陣中刪除該列，否則保留，最后剩下的列就是頻繁2-項集。

(4)產生頻繁k-項集，對求k-1-項集產生的新矩陣中列向量與頻繁1-項集產生的新矩陣中列向量進行兩兩求內積，統計結果中1的個數，記為count(I1…k)，若count(I1…k)少于最小支持度閥值，則從矩陣中刪除該列，否則保留，最后剩下的列就是頻繁k-項集。

(5)k=k+1，重復第(4)步，直到空矩陣為止。

2.3 算法的描述

算法：基于位向量逐層迭代的候選項集生成頻繁集

輸入：事務數據庫T，最小支持度閥值min-support

輸出：T中的頻繁集L

處理流程：

(1)掃描數據庫并轉換向量矩陣A1

(3)for(k=2;Lk-1≠Ф;k++){

(4)Ck=matrix-gen(A1,Ak-1,min-support);

(5)foreachcandidate{

(7)}

(8)Ak={c∈Ck|count(Ck)≥min-support}

(9)}

(10)returnLk=A1A2…Ak//把1,2,…,k組合在一起，成為新的矩陣

該算法的優點在于k-頻繁項集可以有1-頻繁項集和k-1-頻繁項集得到，無需再次掃描數據庫，數據庫只需訪問一次，即在開始時對整個事務數據庫進行訪問，轉化為布爾向量集。其次，計算機的邏輯與預算效率較高，節省了時間。

2.4 性能分析

本文提出的基于位向量的關聯規則算法是采用一次掃描，把數據庫轉化為位向量矩陣表示，不僅可以使得后續的操作處理不需要掃描數據庫，減少了I/O操作的時間，而且使用二進制位向量矩陣來計算列向量的內積求頻繁集，提高了運算速度。

本文從教學評價數據庫導出1000條事務數據記錄作為測試，其中事務數據記錄選取了性別、年齡、學歷、職稱、教學方法、教學能力、教學態度和教學效果作為數據項。選取支持度為0.05、0.1、0.15、0.2作為測試最小支持度閥值。測試結果如圖1所示。

另外，本文在確定最小支持度為0.15時，分別選取100、200、500、1000條事務數據記錄作為測試，測試結果如圖2所示。

從實驗結果分析，可以得到基于位向量的關聯規則算法比Apriori算法在性能上優越，而且，在數據量越大或者最小支持度越小的時候，更能體現基于位向量的關聯規則算法的性能。

3 位向量的關聯規則在教學評價中的應用

教學管理部門為了做好教學管理工作，提出有效的決策，往往需要清楚影響教學質量的因素，本文通過從教務處導出的教學評價數據，選取認為影響因素比較重要的8個數據項作為研究內容，分別是性別、年齡、學歷、職稱、教學方法、教學能力、教學態度和教學效果。為了簡化測試內容，僅隨機選取了10條評教數據作為數據源，隨機抽取分析數據如圖3所示。

為了便于對原始數據進行數據挖掘分析，對以上數據進行指標系數轉換，如表1所示。

對原始數據進行預處理，概化后的數據如表2所示。

運用位向量的關聯規則算法對概化后的數據表進行關聯規則挖掘，設最小支持度為50%，最小置信度為80%，最后得到的結果如表3所示。

分析表3的結果，可以知道具有碩士及以上學歷的老師，通常都是男老師，年齡在30～40歲之間，并且教學能力和教學效果都很好；同時，也可以知道教學能力好的老師教學態度也很好，反之，教學態度好的老師，通常教學能力也不錯。

本次案例應用僅僅選取了10條記錄作為分析，如果需要實際的應用，還是需要對大量數據進行分析，并設置合理的最小支持度和最小置信度，這樣才能較為準確地挖掘出有參考價值的信息。

表2 概化后的數據

表3 關聯規則挖掘結果

4 結語

本文介紹了關聯規則的相關概念及Apriori算法，針對Apriori算法的缺陷，提出了基于位向量的關聯規則改進算法，通過實驗證明其有效性，并利用該算法對教學評價中的數據項進行關聯挖掘，為學校部門對改進教學管理工作提供了一種可行有效的決策分析方法。

[1] Kamber M.數據挖掘:概念與技術[M].范明,孟小峰,譯.北京:機械工業出版社,2007.

[2] Agrawal R,Imielinski T, Swarmi A.Mining Association Rules Between Sets of Items in Large Databases[J].Acm Sigmod Record,1993,22(2):207-216.

[3] Park JS,Chen MS,Yu PS.An Effective Hash-based algorithm for mining association rules[J].Acm Sigmod Record,1995,24(2):175-186.

[4] Agrawal R,Srikant R.Fast Algorithms for Mining Association Rules in large databases[J].Journal of Computer Science and Technology,2000,15(6):619-624.

[5] 劉以安,劉強,鄒曉華,等.基于向量內積的關聯規則挖掘算法研究[J].計算機工程與應用,2006,42(21):172-174,182.

[6] 嚴海兵,卞福荃.一種基于布爾向量的Apriori改進算法[J].蘇州科技學院學報(自然科學版),2008,25(1):67-70.

Application Research of Association Rule Algorithm Based on Bit Vector in Teaching Quality Evaluation

ZHANGYong-xiong1,YUBing-jun2,DengZhi-hong1

(1.GuangzhouCollegeofTechnologyandBusiness，Guangzhou510850，China;2.SouthChinaUniversityofTechnology，Guangzhou510641,China)

This Paper studies and analyzes the defects of Apriori Association Rule Algorithm, proposing a higher efficiency matrix association rule algorithm based on bit vector. By verifying its feasibility and effectiveness, the algorithm is applied to the teaching quality evaluation, which help uncover the related factors that affect the quality of teaching, so as to provide an objective and effective method of decision analysis for improving the teaching management of the school.

Bit vector; Apriori algorithm; association rule; frequent sets

2016-12-22

2015廣東省青年創新人才類項目(2015WQNCX160)

張永雄(1982-)，男，碩士，廣州工商學院經濟貿易系講師，研究方向：數據分析與云計算。

TP311

A

1674-3229(2017)01-0021-04