改進的關聯規則挖掘算法及其在課程設置中的應用

楊強

長江大學計算機科學學院 湖北荊州 434023

作者：楊強，長江大學計算機科學學院講師。

隨著基于校園網絡教學管理系統中學生成績信息的急劇增長，直接根據學生的成績數據分布找出前期課程與后繼課程的關系、課程教授效果等，并據此進行教學進程的決策是十分困難的。因此必須借助于相應的數據挖掘工具，發現數據中隱藏的課程相關規律或模式，為決策提供支持。

1 關聯規則挖掘算法

1.1 算法描述

關聯規則的概念首先由R.Agrowal等人提出，是描述數據庫中數據項（屬性、變量）之間所存在的（潛在）關系的規則，目前已成為數據挖掘中非常重要的一個研究方向。

發現關聯規則要經過4個步驟：1）預處理與挖掘任務有關的數據。根據具體問題的要求對數據庫進行相應的操作，從而構成規格化的數據庫D；2）針對D，求出所有滿足最小支持度的項集，即大項集，由于一般情況下所面臨的數據庫都比較大，所以此步是算法的核心；3）生成滿足最小置信度的規則，形成規則集R；4）解釋并輸出R。

經典關聯規則挖掘算法Apriori，它是一種找頻繁項集的基本算法。算法的核心主要在尋找頻繁項目集上，主要是基于Apriori性質：頻繁項集的所有非空子集都必須也是頻繁的。利用這個性質可以有效地壓縮搜索空間。算法主要思路：為找Lk，通過Lk-1與自己連接產生候選k項集的集合，該候選項的集合記作Ck；依次下去直到Ck+1為空。在產生Ck（k＝1,2,…,k）時，利用剪枝策略壓縮Ck。利用任何非頻繁的(k-1)項集都不可能是頻繁k項集這一Apriori性質，刪去那些(k-1)子集不在Lk-1中的k候選項目集。

Apriori過多次掃描數據庫D來發現所有頻繁項集。存在2個問題：1）算法必須多次掃描事務數據庫，對候選項目集進行模式匹配；2）算法必須花大量的時間進行連接操作及處理候選項目集。這2個問題是當前關聯規則挖掘的熱點和難點。也是約束系統性能的瓶頸。

1.2 算法改進

針對以上2個問題，可以對Apriori算法做下面的改進。

1）首先，掃描事務數據庫，同時記錄包含該項的事務標識符TID，產生1（項候選集C1）。C1的結構為：項集Item—set，支持計數Support，事務標識符列表Tid—list。然后從C1中刪除不滿足最小支持度閾值的項集，則C1中的項集集合即是頻繁1（項集L1）。

2）Lk-1與Lk-1連接，生成Ck。其中Ck事務

標識符列表等于生成它的2個Lk-1的事務標識符列表的交集。對Ck的計數不需掃描事務數據庫，只需計算Ck中事務標識符列表中的TID個數即可。

1.3 算法描述

輸入：事務數據庫D；最小支持度閥值min_sup。輸出：D中的頻繁項集L。見框1。

2 算法在課程相關性分析中的應用

2.1 算法應用

設I是由m門課程組成的集合，給定一個數據庫D為學生成績庫記錄的集合，其中的每一個記錄T是I中一組屬性的集合，即Tgl，T有一個唯一的標識符TID。

根據上述對算法改進的思想，候選集的結構中包含一個事物標識符列表，該列的長度是不確定的，因此在關系數據庫中不容易實現。為此，在算法的實現做了如下調整：在候選集表中，每一個＜項集，事務標識符＞作為一個記錄，這樣候選集中的一個項集對應多條記錄。學生課程成績表的部分數據字段如表1所列，該表中的部分數據如表2所列。

表1 學生課程成績表部分字段

表2 學生課程成績部分數據表

表3 候選項集

2.2 挖掘結果

本實例是對某校計算機學院的學生成績進行分析，首先是對各不同專業的學生成績進行分析，得到專業內各課程之間的相關信息。由于各專業各學科存在交叉性，可以利用改進后的關聯規則進行綜合分析，得到學院內課程之間的相關性分析。通過對學生成績數據庫挖掘后，得出課程關聯規則（如表4所示）：規則1表明，離散數學作為石油地質基礎的先行課程的支持度是3.97%，信任度是72.84%。因此加強離散數學的學習有助于數據結構的學習。其他規則同樣可按這種方式分析。

對表2中的數據進行處理，得到的候選項集如表3所列。然后從候選集表中統計每個項集的計數，插入頻繁項集表中。同時，將候選集中的非頻繁項集刪除，以便于生成下一級候選集。

表4 挖掘結果部分實例

3 結論

通過改進后的Apriori算法對教育信息數據庫進行數據挖掘，產生的規則對學校的課程安排、學生的素質教育以及教學模式等方面提供了有價值的參考。所以決策者可以通過合理安排相關課程的開課順序、加強前期課程的教學時間和師資配備來改善后續課程的教學效果，從而為制定合理、最優的教學計劃和人才培養方案提供幫助。

[1]Agrawal R, Imielinski T, Swami A. Mining Association Rules between Sets of Items in Large Databases[A].ACM SIGMOD Conference,1993

[2]Agrawal R, Srikant R. Fast Algorithms for Mining Association Rules in Large Database[A].VLDB:1994

[3]安穎.一種改進的Apriori挖掘關聯規則算法[J].軟件導刊,2008(10)

[4]曲春錦.改進的關聯規則挖掘算法及其在教育信息挖掘中的應用[J].交通與計算機,2005(4)