改進(jìn)的關(guān)聯(lián)規(guī)則挖掘算法及其在課程設(shè)置中的應(yīng)用

楊強(qiáng)

長江大學(xué)計(jì)算機(jī)科學(xué)學(xué)院 湖北荊州 434023

作者：楊強(qiáng)，長江大學(xué)計(jì)算機(jī)科學(xué)學(xué)院講師。

隨著基于校園網(wǎng)絡(luò)教學(xué)管理系統(tǒng)中學(xué)生成績信息的急劇增長，直接根據(jù)學(xué)生的成績數(shù)據(jù)分布找出前期課程與后繼課程的關(guān)系、課程教授效果等，并據(jù)此進(jìn)行教學(xué)進(jìn)程的決策是十分困難的。因此必須借助于相應(yīng)的數(shù)據(jù)挖掘工具，發(fā)現(xiàn)數(shù)據(jù)中隱藏的課程相關(guān)規(guī)律或模式，為決策提供支持。

1 關(guān)聯(lián)規(guī)則挖掘算法

1.1 算法描述

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

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

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

Apriori過多次掃描數(shù)據(jù)庫D來發(fā)現(xiàn)所有頻繁項(xiàng)集。存在2個問題：1）算法必須多次掃描事務(wù)數(shù)據(jù)庫，對候選項(xiàng)目集進(jìn)行模式匹配；2）算法必須花大量的時間進(jìn)行連接操作及處理候選項(xiàng)目集。這2個問題是當(dāng)前關(guān)聯(lián)規(guī)則挖掘的熱點(diǎn)和難點(diǎn)。也是約束系統(tǒng)性能的瓶頸。

1.2 算法改進(jìn)

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

1）首先，掃描事務(wù)數(shù)據(jù)庫，同時記錄包含該項(xiàng)的事務(wù)標(biāo)識符TID，產(chǎn)生1（項(xiàng)候選集C1）。C1的結(jié)構(gòu)為：項(xiàng)集Item—set，支持計(jì)數(shù)Support，事務(wù)標(biāo)識符列表Tid—list。然后從C1中刪除不滿足最小支持度閾值的項(xiàng)集，則C1中的項(xiàng)集集合即是頻繁1（項(xiàng)集L1）。

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

標(biāo)識符列表等于生成它的2個Lk-1的事務(wù)標(biāo)識符列表的交集。對Ck的計(jì)數(shù)不需掃描事務(wù)數(shù)據(jù)庫，只需計(jì)算Ck中事務(wù)標(biāo)識符列表中的TID個數(shù)即可。

1.3 算法描述

輸入：事務(wù)數(shù)據(jù)庫D；最小支持度閥值min_sup。輸出：D中的頻繁項(xiàng)集L。見框1。

2 算法在課程相關(guān)性分析中的應(yīng)用

2.1 算法應(yīng)用

設(shè)I是由m門課程組成的集合，給定一個數(shù)據(jù)庫D為學(xué)生成績庫記錄的集合，其中的每一個記錄T是I中一組屬性的集合，即Tgl，T有一個唯一的標(biāo)識符TID。

根據(jù)上述對算法改進(jìn)的思想，候選集的結(jié)構(gòu)中包含一個事物標(biāo)識符列表，該列的長度是不確定的，因此在關(guān)系數(shù)據(jù)庫中不容易實(shí)現(xiàn)。為此，在算法的實(shí)現(xiàn)做了如下調(diào)整：在候選集表中，每一個＜項(xiàng)集，事務(wù)標(biāo)識符＞作為一個記錄，這樣候選集中的一個項(xiàng)集對應(yīng)多條記錄。學(xué)生課程成績表的部分?jǐn)?shù)據(jù)字段如表1所列，該表中的部分?jǐn)?shù)據(jù)如表2所列。

表1 學(xué)生課程成績表部分字段

表2 學(xué)生課程成績部分?jǐn)?shù)據(jù)表

表3 候選項(xiàng)集

2.2 挖掘結(jié)果

本實(shí)例是對某校計(jì)算機(jī)學(xué)院的學(xué)生成績進(jìn)行分析，首先是對各不同專業(yè)的學(xué)生成績進(jìn)行分析，得到專業(yè)內(nèi)各課程之間的相關(guān)信息。由于各專業(yè)各學(xué)科存在交叉性，可以利用改進(jìn)后的關(guān)聯(lián)規(guī)則進(jìn)行綜合分析，得到學(xué)院內(nèi)課程之間的相關(guān)性分析。通過對學(xué)生成績數(shù)據(jù)庫挖掘后，得出課程關(guān)聯(lián)規(guī)則（如表4所示）：規(guī)則1表明，離散數(shù)學(xué)作為石油地質(zhì)基礎(chǔ)的先行課程的支持度是3.97%，信任度是72.84%。因此加強(qiáng)離散數(shù)學(xué)的學(xué)習(xí)有助于數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)。其他規(guī)則同樣可按這種方式分析。

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

表4 挖掘結(jié)果部分實(shí)例

3 結(jié)論

通過改進(jìn)后的Apriori算法對教育信息數(shù)據(jù)庫進(jìn)行數(shù)據(jù)挖掘，產(chǎn)生的規(guī)則對學(xué)校的課程安排、學(xué)生的素質(zhì)教育以及教學(xué)模式等方面提供了有價(jià)值的參考。所以決策者可以通過合理安排相關(guān)課程的開課順序、加強(qiáng)前期課程的教學(xué)時間和師資配備來改善后續(xù)課程的教學(xué)效果，從而為制定合理、最優(yōu)的教學(xué)計(jì)劃和人才培養(yǎng)方案提供幫助。

[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]安穎.一種改進(jìn)的Apriori挖掘關(guān)聯(lián)規(guī)則算法[J].軟件導(dǎo)刊,2008(10)

[4]曲春錦.改進(jìn)的關(guān)聯(lián)規(guī)則挖掘算法及其在教育信息挖掘中的應(yīng)用[J].交通與計(jì)算機(jī),2005(4)