改進的Apriori算法在教學評價中的應用研究

摘要:該文通過對Apriori算法進行改進，借助0-1矩陣，只掃描一次數據庫，直接從高維項目集入手計算項目集的支持度，從而尋找最大頻繁項目集。將該改進算法應用于課堂教學評價中，可以挖掘出影響課堂質量的因素，從而指導教師改善課堂教學，提高教學質量。

關鍵詞:頻繁項目集;侯選項目集;Apriori算法

中圖分類號:G434文獻標識碼:A文章編號:1009-3044(2010)01-145-03

Application Research of an Improvement on Apriori Algorithm in Evaluating Teaching Quality

HE Fen， WU Ye-fu

(Wuhan University of Technology， Wuhan 430063， China)

Abstract: This paper mainly researches about the improvement on Apriori algorithm and the application research in evaluating teaching quality. This improvement based on 0-1 matrix，it just scans database once，and finds out the highest dimension frequent itemset directly from high dimension itemset. With the help of this improved algorithm ，some obtained knowledge will be applied in guiding the teaches' teaching and improving the quality of teaching.

Key words: frequent itemset; candidate itemset; Apriori algorithm

由于教學信息數量大、量度水平低、教學信息的隱含性、教學信息的模糊性等特征，蘊含在教學中的很多潛在、有用信息難以被人們發現利用。利用數據挖掘中的關聯挖掘技術，可以對潛在數據提取、分析、處理，從中及時發現有用的信息，從大量不確定因素中找到規律，指導教師分析、反思改進教學。

關聯規則挖掘是數據挖掘中最活躍的研究領域之一，最早由Agrawal等人于1993年首先提出。在眾多的關聯規則挖掘中，Apriori算法是最基本也最核心的一種。

1 傳統Apriori算法

Apriori算法是1994年由R.Agrawal和R.Srikant提出的，它使用的深度優先的迭代搜索方法，首先找到頻繁1-項集集合F1，用F1找頻繁2-項集集合F2，再用F2找F3，依次循環的方式，直到不能找到頻繁K-項集為止，且找每個Fk都需要一次數據庫全掃描。

傳統算法最重要的的不足是:對數據庫進行多次掃描，需要很大的I/O負載，并且候選項目數多，計算項過多，內存利用率低，以致影響運行效率。

2 改進的Apriori算法思想

2.1 將事務數據庫轉化為0-1矩陣

規則1:對一個含有n個事務Ti(i=1，2，……n)，m個項目Xj(j=1，2……m)的事務數據庫，首先將其生成一個(n+1)×(m+1)的矩陣，其中第一行用于標識項目，第一列用于標識事務。

對每一列求和即為對應項目Xj在所有事務中出現的總次數k，若k小于最小支持度minsup，則說明該項目不可能出現在任何頻繁項集中，所以應將該項目對應的列直接刪掉，這樣做不會影響頻繁項集的生成，相反簡化了矩陣，更易于后面的操作，經過這步操作形成初始矩陣M。

2.2 直接利用矩陣從高階項集著手尋找最大頻繁項集

改變傳統Apriori由低維頻繁項集到高維項集的多次連接運算，直接利用矩陣從高階項集著手尋找最大頻繁項集。

主要過程為:

1)對關聯矩陣M的每一行進行求和，計算出所有事物包含的項目數;

2)選取項目數最多K(可能包含多個)的為測試頻繁項目集的備選項目集;

3)依次計算備選項目集中各項目集的支持度，若支持度小于最小支持度minsup，則直接從備選項目集中刪除，最后剩余的即為我們要尋找的頻繁項目集;若備選項目集最后為空，則k值減1繼續2)，直到找到頻繁項目集。

其中3)中計算項目集的支持度不采用傳統的連接、剪枝等步驟，直接利用矩陣來計算，主要通過選取項目集中包含的項目構成新的矩陣，直接掃描矩陣，計算出全為1的行數即為支持度，這樣不用重復掃描數據庫，減小I/O負載。

3 改進的Apriori算法在教學評價中的應用研究

3.1 確定挖掘對象和目標

影響教師教學質量的因素很多，包括諸如:教師性別、年齡，學歷，職稱、教學內容、教學方法、教學態度等等。通過對這些因素之間關聯關系的挖掘，期望用所獲得的分析結果指導教師的教學工作。

3.2 數據準備

采用學校課堂教學評估表獲取的評教數據作為數據源，隨機抽取分析數據如圖1。

3.3 數據轉換

這一部分主要是根據實際需要選取不同的數據源作為挖掘對象，由圖1可見，針對教學評分這列，可能出現的值為差、中、良、優四種，可以分別考慮導致不同教學效果的因素。如果只選取課堂教學評分為優的數據，則數據源縮小為圖2。

為便于對教師教學質量的數據挖掘，首先夠找數據挖掘的指標系數如表1。

表1 價的指標體系說明

根據規則1，將選取的數據源轉化成0-1矩陣，因為此部分試驗主要是挖掘導致教學質量優的主要因素，則最后一列關于全為1，可暫時省略不表示出來，最后初始矩陣為圖3。

假定最小支持度minsup為3，觀察矩陣可知X21，X41，X52，X53，X63，X72，X73項小于最小支持度，則可以把它們所在的列直接刪除，簡化操作，簡化后的矩陣為M，圖4。

3.4 確定頻繁項目集

針對本測試試驗，對關聯矩陣M的每一行進行求和，計算除所有事物的項目數，則選取初始k值為7，頻繁項目集的備選項目集為{{X12，X22，X33，X42，X51，X61，X71｝，{X11，X22，X32，X42，X51，X62，X71｝，{X12，X23，X33，X43，X51，X61，X71｝，{X12，X23，X31，X42，X51，X61，X71}，{X11，X23，X33，X43，X51，X61，X71}，{X12，X23，X31，X43，X51，X62，X71}，{X12，X22，X32，X42，X51，X62，X71}，{X12，X22，X33，X43，X51，X61，X71}｝。接著計算各項目集的支持度，可以直接選取項目集中包含的項目所對應的行組成新的矩陣，計算每一行所有元素相與之和，即計算每行都全為1的行數。如計算{X11，X23，X33，X43，X51，X61，X71}的支持度則選取該項目集中的項目即:X11，X23，X33，X43，X51，X61，X71所在列構成新的矩陣，如圖5。

全為1的行有3行，即事務14、19、23，所以{X11，X23，X33，X43，X51，X61，X71}的支持度為3。通過對不同矩陣進行“與運算”的方法可得候選項目集中所有項目的支持度如表2。

經過這一步確定{X11 ，X23 ，X33 ，X43，X51 ，X61 ，X71}即為我們要尋找的項目集，則不用再進一步求解。

4 總結

本測試用例中使用的計算項目集支持度方式是直接從高維項集著手，省掉了傳統由低維向高維連接而產生大量重復項目集的過程，簡化了很多關于支持度的計算等等，大大提高了效率。但讓實際應用中很多情況存在不能這樣通過一次k的取值就能得出候選集的情況，循環減小k的值，每次去項目集中的k個項目，按照同樣的方向即可求各項目集的支持度，最終確定我們需要的頻繁項目集。將這種算法應用于課堂教學評價中，可以挖掘出影響課堂質量的因素，從而指導教師改善課堂教學，提高教學質量。

參考文獻:

[1] 胡可云，田鳳占，黃厚寬.數據挖掘:理論與應用[M].北京:清華大學出版社，北京交通大學出版社，2008.

[2] 鞠平.課堂教學質量評價探討[C].第二屆全國高校電氣工程及其自動化專業教學改革研討會論文，2004.

[3] Han Jiawei，Kamber M.數據挖掘:概念與技術[M].北京:機械工業出版社，2007.

[4] 梁循.數據挖掘算法與應用[M].北京:北京大學出版社，2006.

[5] 杜習慧，羅坤杰，羅文俊.關聯規則Apriori算法的改進[J].電腦知識與技術，2009(6):1295-1296.

[6] 袁萬蓮，鄭誠，翟明清.一種改進的Apriori算法[J].計算機技術與發展，2008，18(5):50-54.

[7] 胡吉明，鮮學豐.挖掘關聯規則中Apriori算法的研究與改進[J].計算機技術與發展，2006，16(4):99-100

[8] 文蓉，李仁發.一種優化的Apriori算法[J].計算機系統應用，2008，12(1):94-120.