盧小華，劉靜

（山西工商學(xué)院，山西 太原 030006）

Apriori算法在網(wǎng)絡(luò)教學(xué)平臺自動推薦學(xué)習(xí)資源功能中的應(yīng)用

盧小華，劉靜

（山西工商學(xué)院，山西 太原 030006）

主要研究了數(shù)據(jù)挖據(jù)關(guān)聯(lián)規(guī)則中挖掘頻繁項集的Apriori算法在教學(xué)平臺中的應(yīng)用，以學(xué)生進(jìn)入課程中心進(jìn)行學(xué)習(xí)的日志記錄作為原始數(shù)據(jù)，采用Apriori算法分析知識網(wǎng)頁間的關(guān)聯(lián)，根據(jù)關(guān)聯(lián)規(guī)則進(jìn)行學(xué)習(xí)資源的個性化推薦，從而滿足不同學(xué)生的學(xué)習(xí)需求。

關(guān)聯(lián)規(guī)則；Apriori算法；教學(xué)平臺；學(xué)習(xí)資源推薦

引言

隨著信息技術(shù)和網(wǎng)絡(luò)技術(shù)的快速發(fā)展，各大高校均構(gòu)建了網(wǎng)絡(luò)教學(xué)平臺，但是現(xiàn)有的教學(xué)平臺缺乏個性化功能設(shè)計，不能根據(jù)不同需求進(jìn)行學(xué)習(xí)資源的自動化推薦，因此在教學(xué)平臺的設(shè)計中，加入數(shù)據(jù)挖據(jù)中基于關(guān)聯(lián)規(guī)則的Apriori算法對于提高學(xué)生的學(xué)習(xí)效果是很有意義的。

1　關(guān)聯(lián)規(guī)則的相關(guān)概念

假設(shè)用字母D代表數(shù)據(jù)庫中所有事務(wù)的集合，而每個事務(wù)用字母T來表示，事務(wù)的標(biāo)識符用TID來表示，且T≠。并假設(shè)用字母I來表示數(shù)據(jù)庫中所有數(shù)據(jù)項的集合，其中每一項用Im來表示，T為I的子集。假定A、B均為項集，均是T的非空子集，且A和B的交集不為空，則說明A和B是相關(guān)聯(lián)的項集，既A=＞B。這個推算公式就稱為D中A和B的關(guān)聯(lián)規(guī)則［1］。

1）D中項集X出現(xiàn)的次數(shù)稱為支持度計數(shù)。

2）在數(shù)據(jù)事務(wù)集合D中，項目集A所在的事務(wù)數(shù)與D中總的事務(wù)數(shù)的百分比稱之為A在D中的支持度，記作sup（A）［2］。

3）關(guān)聯(lián)規(guī)則的一般形式為：A=＞B，其含義為A出現(xiàn)的同時也導(dǎo)致B出現(xiàn)。則A=＞B的支持度為：support（A=＞B）=suppport（A∪B）=P（A∪B）=T（A∪B）/|D|

其中|T（A∪B）|代表A∪B的事務(wù)數(shù)，|D|表示事務(wù)總數(shù)，支持度代表了關(guān)聯(lián)規(guī)則的頻度［3］。

由用戶自設(shè)的支持度的一個閾值，記作minsup。

是指數(shù)據(jù)庫事務(wù)D中A和B同時出現(xiàn)的次數(shù)與A出現(xiàn)的次數(shù)之比。

confidence（A=＞B）=（support（A∪B）/（support（A））

是用戶設(shè)定的衡量置信度的一個閾值，表示關(guān)聯(lián)規(guī)則的最低準(zhǔn)確率，記作minconf。

對一個項目集X，如果support（X）≥min_sup，稱X為頻繁項目集，頻繁k項集的集合通常記為Lk［4］。

如果support（A=＞B） ≥minsup 且confidence（A=＞B）≥minconf，稱關(guān)聯(lián)規(guī)則A=＞B為較強規(guī)則。

如果一個項集是頻繁的，那么它的所有子集（不包括空集）也一定是頻繁的［5］。

2　關(guān)聯(lián)規(guī)則挖掘的經(jīng)典算法—Apriori算法

Apriori算法又叫逐層搜索迭代方法，它是用第k項集搜索第k+1項集［6］。算法的基本思想為：第一，首先對整個事務(wù)數(shù)據(jù)庫進(jìn)行掃描，統(tǒng)計其中每一項出現(xiàn)的次數(shù)。第二，找出所有支持度≥用戶設(shè)定的最小支持度的項集。第三，將滿足條件的所有項集作為一個集合賦給頻繁1項集L1。第四，通過L1自身連接生成候選項集，將候選項進(jìn)行計數(shù)，與最小支持度進(jìn)行比較，將滿足條件的所有項集作為一個集合賦給頻繁2項集的集合L2。第五，采用同樣的方法通過L2自身連接查找頻繁3項集L3。第六，循環(huán)執(zhí)行以上操作，直到不能產(chǎn)生頻繁項集為止。在查找頻繁項集的過程中可使用先驗性質(zhì)判斷進(jìn)行剪枝操作。第七，利用以上操作步驟生成的頻繁項集計算關(guān)聯(lián)規(guī)則［7］。

Apriori算法的核心是使用Lk-1找出LK項，k≥2，主要步驟為連接和剪枝：

1） 連接。將LK-1與其自身通過連接運算生成候選k項集的集合，用Ck來表示。假設(shè)l1和l2是LK-1中的項集，li［j］ 表示li的第j，如果l1［1］=l2［1］）（l1［2］=l2［2］）（l1［k-2］=l2［k-2］）（l1［k-1］＜l2［k-1］） ，則LK-1中的元素l1和l2是可連接的，連接l1和l2產(chǎn)生的結(jié)果項集是｛l1［1］，l1［2］，…l1［k-1］，l2［k-1］｝［8］，項集中不能存在重復(fù)的項。

2）剪枝步。通過掃描數(shù)據(jù)庫，對Ck項集中每個項進(jìn)行計數(shù)，其中值不小于最小支持度的項都屬于Lk。為了節(jié)省計算量，使用算法的先驗性質(zhì)，假如Ck中的一個候選k項集的（k-1）項子集不屬于LK-1，則將其從Ck中刪除。

1）輸入事務(wù)數(shù)據(jù)庫，用D表示。設(shè)定最小支持度閾值，用Minsup表示

2）輸出D中的頻繁項集。

3）算法偽代碼表示如下［9］：

L1=find（D）； //L1表示頻繁1項集，find （D）表示從數(shù)據(jù)事務(wù)中查找頻繁項集

for（i=2； Li-1；i++） //通過頻繁i-1項集生成頻繁i項集

｛Ci=funapr （Li-1）； //調(diào)用函數(shù)funapr （），生成候選項集Ci

for each 事務(wù)T∈D//T代表一個事務(wù)，通過for循環(huán)對每一個事務(wù)進(jìn)行判斷

｛C1=subset（Ci，T）； //取得候選項

for each 候選c∈CT；

c.count++；｝

Li=｛c∈Ci| c.count≥minsup｝

｝

return L=UiLi

Procedure funapr （Li-1：frequent（i-1）itemset）

｛for each項集l1∈Li-1

for each 項集l2∈Li-1

If（l1［1］=l2［1］）^（l1［2］=l2［2］）…^（l1［k-2］=l2［k-2］）^（l1［k-1］＜l2［k-1］） then

｛ c=l1l2； // 連接操作

If infreqset（c，Li-1） then // 如果不是頻繁項集

delete c； //剪枝操作

else add c to Ci；｝

Return Ci；

Procedure infreset（c：candidate i itemset； Li-1：frequent（k-1）itemsets）

｛ for each（k-1） subset s of c//通過本程序判斷s是否為非頻繁項集

If s Li-1then //如果子集s不屬于Li-1

return true；

else

return false｝

1）生成每個頻繁項集l的非空子集［10］。

2）如果（support_count（1）/（support_count（s）≥min_conf，則輸出規(guī)則“s=＞ （l-s）”，其中min_conf代表最小置信度閾值。

3　Apriori算法在平臺教學(xué)資源推薦中的應(yīng)用

Apriori算法挖掘過程分為四步：第一，對于進(jìn)行挖掘的數(shù)據(jù)信息進(jìn)行整理，形成一個計算機能處理的數(shù)據(jù)庫；第二，從數(shù)據(jù)庫中把具有一定價值的數(shù)據(jù)項整理出來；第三，把整理過的數(shù)據(jù)項轉(zhuǎn)換成算法能夠處理的事務(wù)；第四，根據(jù)預(yù)先所設(shè)定的最小支持度得到頻繁項集；第五，根據(jù)頻繁項級級預(yù)先設(shè)定的最小置信度得到事務(wù)間的關(guān)聯(lián)規(guī)則［11］。

實例分析：采用Apriori算法挖掘?qū)W生進(jìn)入課程中心進(jìn)行課程學(xué)習(xí)的訪問日志，找出訪問較頻繁的知識點頁面，判斷學(xué)生的興趣。基于學(xué)生頻繁進(jìn)行學(xué)習(xí)的頁面，獲取學(xué)生的學(xué)習(xí)需求趨勢，找出頻繁項集，進(jìn)行個性化學(xué)習(xí)資源的推薦。

數(shù)據(jù)收集在數(shù)據(jù)挖掘前期工作中是非常重要的，收集學(xué)生訪問平臺知識點網(wǎng)頁的記錄，隨機抽取了4條記錄，如表1所示。

表1　學(xué)生訪問知識點網(wǎng)頁記錄數(shù)據(jù)表

把數(shù)據(jù)表轉(zhuǎn)換成事務(wù)數(shù)據(jù)庫D，例題中共有4個事務(wù)，即|D|=4，其中C代表C語言，CJ代表C++，CS代表C#，J代表計算機基礎(chǔ)，P代表Photoshop，轉(zhuǎn)換后記錄如表2所示。

表2　學(xué)生訪問知識點網(wǎng)頁的事務(wù)數(shù)據(jù)

將事務(wù)數(shù)據(jù)表轉(zhuǎn)化成布爾矩陣，如表3所示。

表3　學(xué)生訪問知識點網(wǎng)頁的布爾矩陣圖

按照算法的兩個步驟進(jìn)行關(guān)聯(lián)規(guī)則挖掘， 在本例中假設(shè)最小支持度計數(shù)為2，即min_sup=2，最小置信度為6 5%。

1）使用候選項集找出所有頻繁項集。

在查找L1時，將事務(wù)數(shù)據(jù)庫中所有的事務(wù)進(jìn)行掃描，將所有項的出現(xiàn)次數(shù)進(jìn)行統(tǒng)計，從而確定C1，從C1中把大與等于最小支持度閾值的項取出來，組成集合賦給L1，如圖1所示：

圖1　候選項集C1和頻繁項集L1的產(chǎn)生

2） 通過Ll其自身連接產(chǎn)生C2—候選兩項集的項集，計算C2中兩項集出現(xiàn)的次數(shù)，然后將其值與最小支持度比較，不小于最小支持度的項集賦給L2。

圖2　候選項集C2和頻繁項集L2的產(chǎn)生

3） L2與自身連接生成C3—候選三項集的項集，計算C3中兩項集出現(xiàn)的次數(shù)，然后將其值與最小支持度比較，不小于最小支持度的項集賦給L3。

圖3　候選項集C3和頻繁項集L3的產(chǎn)生

4） L3與自身連接不再生成頻繁項集，因此算法結(jié)束。

通過分析結(jié)果發(fā)現(xiàn)C語言和C++、C#兩門課程之間存在著密切的關(guān)聯(lián)，將得到的關(guān)聯(lián)規(guī)則結(jié)果存放到關(guān)聯(lián)規(guī)則表中，在學(xué)生選擇學(xué)習(xí)C語言課程時平臺自動推薦學(xué)習(xí)C++、C#，如圖4所示。

圖4　平臺自動推薦學(xué)習(xí)資源界面圖

4　結(jié)語

隨著Internet的迅速發(fā)展，網(wǎng)絡(luò)教學(xué)平臺的應(yīng)用已成為網(wǎng)絡(luò)教育的一種主流模式。數(shù)據(jù)挖掘技術(shù)中Apriori算法在教學(xué)平臺中的應(yīng)用可以為學(xué)生自動推薦個性化的學(xué)習(xí)資源，從而可以滿足不同學(xué)習(xí)者的學(xué)習(xí)需求，提高學(xué)習(xí)效果和質(zhì)量。

［1］林炳源.基于FP樹的關(guān)聯(lián)規(guī)則算法改進(jìn)研究. 林炳源［D］.贛州：江西理工大學(xué)，2012.

［2］Jiawei Han ，Micheline Kamber ，Jian Pei.Date Mining Concepts and Techiques Third Edition［M］.BeiJing：China Machine Press.2012.

［3］李文靜.淺談數(shù)據(jù)挖掘中的分類算法［J］.甘肅科技縱橫，2007（3）：2.

［4］劉芳.基于雙向搜索的關(guān)聯(lián)規(guī)則挖掘算法研究［D］.重慶：重慶郵電大學(xué)，2011.

［5］謝亮.基于主從關(guān)系數(shù)據(jù)模型的關(guān)聯(lián)規(guī)則挖掘研究［D］.合肥：合肥工業(yè)大學(xué)，2009.

［6］樊妍妍.基于數(shù)據(jù)挖掘的個性化在線教學(xué)輔助系統(tǒng)的研究與設(shè)計［D］.合肥：安徽大學(xué)，2011.

［7］R obert C ool ey，Bam shad M obasher，Jai deep Sri vast ava［M］.D at a Preparat i on f or M i ni ng W orl d W i de W eb Brow si ng Pat t erns. Know l edge and Inf orm at i on Syst em s，1999.

［8］范明.數(shù)據(jù)挖掘概念與技術(shù)［M］.孟小峰，譯.北京：機械工業(yè)出版社，2012.

［9］Fayyad U.Data mining and knowledge discovery in databases implications for scientific databases［C］//International Conference on Scientific Database Management，1997：51-55.

［10］（美）譚.斯坦巴赫.數(shù)據(jù)挖掘技術(shù)導(dǎo)論［M］.范明等，譯.北京：人民郵電出版社，2006.

（編輯：賈娟）

Application of Apriori Calculation in Network Teaching Platform to Automatically Recommend Learning Resources Function

Lu Xiaohua，Liu Jing
（Computer Information Engineering College of Shanxi Technology and Business University，Taiyuan Shanxi 030006）

This paper mainly studies the data digging， according to the association rules Apriori algorithm for mining frequent itemsets in the application of the teaching platform， into the heart of the course on the students to learn the logging as raw data， USES the Apriori algorithm analysis knowledge web page， the correlation between learning resources according to association rules of personalized recommendation， to meet different learning needs of students.

association rule； Apriori calculation； teaching platform； study material recommend

TP311

A

2095-0748（2016）15-0101-04

10.16525/j.cnki.14-1362/n.2016.15.43

2016-07-06

課題項目:山西工商學(xué)院《C語言程序設(shè)計精品課程建設(shè)項目管理研究》，編號：201549

盧小華（1981—），女，山西五臺人，工程碩士，現(xiàn)就職于山西工商學(xué)院計算機信息工程學(xué)院，研究方向：數(shù)據(jù)挖掘；劉靜（1981—），男，山西朔州人，現(xiàn)就職于山西工商學(xué)院網(wǎng)絡(luò)中心，教育技術(shù)學(xué)專業(yè)。