楊強(qiáng)

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

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

隨著基于校園網(wǎng)絡(luò)教學(xué)管理系統(tǒng)中學(xué)生成績(jī)信息的急劇增長(zhǎng)，直接根據(jù)學(xué)生的成績(jī)數(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ù)挖掘中非常重要的一個(gè)研究方向。

發(fā)現(xiàn)關(guān)聯(lián)規(guī)則要經(jīng)過4個(gè)步驟：1）預(yù)處理與挖掘任務(wù)有關(guān)的數(shù)據(jù)。根據(jù)具體問題的要求對(duì)數(shù)據(jù)庫進(jìn)行相應(yīng)的操作，從而構(gòu)成規(guī)格化的數(shù)據(jù)庫D；2）針對(duì)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)集的所有非空子集都必須也是頻繁的。利用這個(gè)性質(zhì)可以有效地壓縮搜索空間。算法主要思路：為找Lk，通過Lk-1與自己連接產(chǎn)生候選k項(xiàng)集的集合，該候選項(xiàng)的集合記作Ck；依次下去直到Ck+1為空。在產(chǎn)生Ck（k＝1,2,…,k）時(shí)，利用剪枝策略壓縮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個(gè)問題：1）算法必須多次掃描事務(wù)數(shù)據(jù)庫，對(duì)候選項(xiàng)目集進(jìn)行模式匹配；2）算法必須花大量的時(shí)間進(jìn)行連接操作及處理候選項(xiàng)目集。這2個(gè)問題是當(dāng)前關(guān)聯(lián)規(guī)則挖掘的熱點(diǎn)和難點(diǎn)。也是約束系統(tǒng)性能的瓶頸。

1.2 算法改進(jìn)

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

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

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

標(biāo)識(shí)符列表等于生成它的2個(gè)Lk-1的事務(wù)標(biāo)識(shí)符列表的交集。對(duì)Ck的計(jì)數(shù)不需掃描事務(wù)數(shù)據(jù)庫，只需計(jì)算Ck中事務(wù)標(biāo)識(shí)符列表中的TID個(gè)數(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門課程組成的集合，給定一個(gè)數(shù)據(jù)庫D為學(xué)生成績(jī)庫記錄的集合，其中的每一個(gè)記錄T是I中一組屬性的集合，即Tgl，T有一個(gè)唯一的標(biāo)識(shí)符TID。

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

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

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

表3 候選項(xiàng)集

2.2 挖掘結(jié)果

本實(shí)例是對(duì)某校計(jì)算機(jī)學(xué)院的學(xué)生成績(jī)進(jìn)行分析，首先是對(duì)各不同專業(yè)的學(xué)生成績(jī)進(jìn)行分析，得到專業(yè)內(nèi)各課程之間的相關(guān)信息。由于各專業(yè)各學(xué)科存在交叉性，可以利用改進(jìn)后的關(guān)聯(lián)規(guī)則進(jìn)行綜合分析，得到學(xué)院內(nèi)課程之間的相關(guān)性分析。通過對(duì)學(xué)生成績(jī)數(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ī)則同樣可按這種方式分析。

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

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

3 結(jié)論

通過改進(jìn)后的Apriori算法對(duì)教育信息數(shù)據(jù)庫進(jìn)行數(shù)據(jù)挖掘，產(chǎn)生的規(guī)則對(duì)學(xué)校的課程安排、學(xué)生的素質(zhì)教育以及教學(xué)模式等方面提供了有價(jià)值的參考。所以決策者可以通過合理安排相關(guān)課程的開課順序、加強(qiáng)前期課程的教學(xué)時(shí)間和師資配備來改善后續(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)