盧小華，劉靜

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

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

盧小華，劉靜

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

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

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

引言

隨著信息技術(shù)和網(wǎng)絡(luò)技術(shù)的快速發(fā)展，各大高校均構(gòu)建了網(wǎng)絡(luò)教學(xué)平臺(tái)，但是現(xiàn)有的教學(xué)平臺(tái)缺乏個(gè)性化功能設(shè)計(jì)，不能根據(jù)不同需求進(jìn)行學(xué)習(xí)資源的自動(dòng)化推薦，因此在教學(xué)平臺(tái)的設(shè)計(jì)中，加入數(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ù)的集合，而每個(gè)事務(wù)用字母T來表示，事務(wù)的標(biāo)識(shí)符用TID來表示，且T≠。并假設(shè)用字母I來表示數(shù)據(jù)庫中所有數(shù)據(jù)項(xiàng)的集合，其中每一項(xiàng)用Im來表示，T為I的子集。假定A、B均為項(xiàng)集，均是T的非空子集，且A和B的交集不為空，則說明A和B是相關(guān)聯(lián)的項(xiàng)集，既A=＞B。這個(gè)推算公式就稱為D中A和B的關(guān)聯(lián)規(guī)則［1］。

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

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

3）關(guān)聯(lián)規(guī)則的一般形式為：A=＞B，其含義為A出現(xiàn)的同時(shí)也導(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è)的支持度的一個(gè)閾值，記作minsup。

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

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

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

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

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

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

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

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

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

1） 連接。將LK-1與其自身通過連接運(yùn)算生成候選k項(xiàng)集的集合，用Ck來表示。假設(shè)l1和l2是LK-1中的項(xiàng)集，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é)果項(xiàng)集是｛l1［1］，l1［2］，…l1［k-1］，l2［k-1］｝［8］，項(xiàng)集中不能存在重復(fù)的項(xiàng)。

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

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

2）輸出D中的頻繁項(xiàng)集。

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

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

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

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

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

｛C1=subset（Ci，T）； //取得候選項(xiàng)

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項(xiàng)集l1∈Li-1

for each 項(xiàng)集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 // 如果不是頻繁項(xiàng)集

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是否為非頻繁項(xiàng)集

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

return true；

else

return false｝

1）生成每個(gè)頻繁項(xiàng)集l的非空子集［10］。

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

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

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

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

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

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

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

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

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

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

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

1）使用候選項(xiàng)集找出所有頻繁項(xiàng)集。

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

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

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

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

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

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

4） L3與自身連接不再生成頻繁項(xiàng)集，因此算法結(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語言課程時(shí)平臺(tái)自動(dòng)推薦學(xué)習(xí)C++、C#，如圖4所示。

圖4　平臺(tái)自動(dòng)推薦學(xué)習(xí)資源界面圖

4　結(jié)語

隨著Internet的迅速發(fā)展，網(wǎng)絡(luò)教學(xué)平臺(tái)的應(yīng)用已成為網(wǎng)絡(luò)教育的一種主流模式。數(shù)據(jù)挖掘技術(shù)中Apriori算法在教學(xué)平臺(tái)中的應(yīng)用可以為學(xué)生自動(dòng)推薦個(gè)性化的學(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ù)挖掘的個(gè)性化在線教學(xué)輔助系統(tǒng)的研究與設(shè)計(jì)［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］.孟小峰，譯.北京：機(jī)械工業(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

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

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