基于數(shù)據(jù)支持的Apriori分類(lèi)算法的課程推薦研究

引言

在互聯(lián)網(wǎng)大數(shù)據(jù)時(shí)代，人人均需學(xué)習(xí)，時(shí)時(shí)均可學(xué)習(xí)，學(xué)習(xí)是信息化時(shí)代的顯著特征，在網(wǎng)絡(luò)教學(xué)中，根據(jù)學(xué)生的需求，智能性推薦學(xué)生可能感興趣的課程，對(duì)于改善用戶(hù)體驗(yàn)十分重要。傳統(tǒng)的推薦算法采用“最近最常使用”的思想，即某個(gè)課程最近被觀看得越多，喜歡該課程的學(xué)生可能更多。該算法雖然比較樸素，也能取得不錯(cuò)的效果，但是有一個(gè)致命的缺點(diǎn)，就是無(wú)法根據(jù)學(xué)生需求智能推薦。例如，某個(gè)學(xué)生是藝術(shù)生，推薦卻是數(shù)據(jù)結(jié)構(gòu)之類(lèi)的課程，這種推薦極大可能將是一個(gè)無(wú)效推薦。如何實(shí)現(xiàn)智能的有效推薦課程？“最近最常使用”這種樸素的算法無(wú)能為力，而Apriori算法卻能滿(mǎn)足需求，實(shí)現(xiàn)智能推薦。

Apriori算法

1.Apriori算法介紹

Apriori算法是一種親和性分析分類(lèi)算法，用來(lái)分析兩個(gè)數(shù)據(jù)之間的相似度。親和性分析算法使用廣泛，我們?nèi)粘Ｉ钪械漠a(chǎn)品推薦、顧客群劃分、攻擊檢測(cè)等都有親和性分析算法的身影。日常生活中，我們不可能擁有全部數(shù)據(jù)集，只是擁有數(shù)據(jù)集的一部分。OneR之類(lèi)的分析算法要求遍歷全部數(shù)據(jù)集，得出每一個(gè)特征值的置信度和誤差，然后選取最佳數(shù)據(jù)規(guī)則。這種方法一是訓(xùn)練數(shù)據(jù)不能達(dá)到理想情況，二是算法復(fù)雜度太大，當(dāng)數(shù)量增多時(shí)，OneR算法復(fù)雜度將呈指數(shù)級(jí)爆炸式增長(zhǎng)，不利于計(jì)算機(jī)分析大數(shù)據(jù)。

親和性分析算法不必遍歷全部數(shù)據(jù)集，它維護(hù)一個(gè)頻繁集合，然后不斷地加入新的頻繁項(xiàng)，從而巧妙地規(guī)避了復(fù)雜度爆炸式增長(zhǎng)的問(wèn)題。Apriori算法就是一個(gè)簡(jiǎn)單巧妙的親和性分析分類(lèi)算法。

Apriori算法首先要設(shè)立一個(gè)最小支持度，這是Apriori算法的重點(diǎn)和精髓所在。因?yàn)锳priori算法只考慮頻繁的集合，而忽略不頻繁的集合，故必須設(shè)定一個(gè)最小支持度來(lái)制訂頻繁集合的下限。正因?yàn)锳priori算法不必考慮全部集合，所以Apriori算法的計(jì)算時(shí)間較短，效率相對(duì)比較高。

2.數(shù)據(jù)獲取與清洗

有關(guān)課程推薦的數(shù)據(jù)挖掘?qū)嵺`數(shù)據(jù)獲取并不像獲得網(wǎng)絡(luò)訪(fǎng)問(wèn)日志那么煩瑣。學(xué)生選課項(xiàng)目在數(shù)據(jù)庫(kù)內(nèi)有清晰、明確的記載，數(shù)據(jù)庫(kù)導(dǎo)出數(shù)據(jù)機(jī)制也很完善，同時(shí)Python數(shù)據(jù)挖掘軟件包Pandas也支持直接從數(shù)據(jù)庫(kù)拿取數(shù)據(jù)。本節(jié)還是先導(dǎo)出學(xué)生選課數(shù)據(jù)CSV文件，然后再在Jupyter平臺(tái)上進(jìn)行數(shù)據(jù)清洗，最終得到數(shù)據(jù)挖掘必要的數(shù)據(jù)信息。

網(wǎng)絡(luò)教學(xué)平臺(tái)課程分為必修課程和選修課程。必修課程是按照教師要求，班級(jí)統(tǒng)一注冊(cè)的課程，該類(lèi)型課程具有強(qiáng)制性，學(xué)生不可取消。選修課程是學(xué)生根據(jù)自己的興趣選學(xué)的課程，可以隨時(shí)取消學(xué)習(xí)。在課程推薦系統(tǒng)中，應(yīng)該推薦選修課程而不是必修課程，這一是因?yàn)椴煌嗉?jí)的學(xué)習(xí)要求可能不同，二是因?yàn)楸匦拚n程選課基數(shù)大，構(gòu)建選課系統(tǒng)時(shí)，會(huì)產(chǎn)生一定噪聲問(wèn)題。因此，本文的課程推薦算法只設(shè)計(jì)選修課程的推薦。

筆者使用compulsory字段來(lái)判斷一門(mén)課是不是選修課。所使用的代碼為：

SELECT a.sid， a.cid， a.canceled FROM student_course as a LEFT JOIN course as b on a.cid = b.cid WHERE b.compulsory = '0' limit 10000;

篩選出100000條學(xué)生的選修課信息，并用DataStrip的數(shù)據(jù)導(dǎo)出功能導(dǎo)出CSV數(shù)據(jù)。因?yàn)閿?shù)據(jù)庫(kù)里的數(shù)據(jù)十分規(guī)則，所以這里的數(shù)據(jù)不需要做數(shù)據(jù)清洗。

3.數(shù)據(jù)處理過(guò)程

首先使用pandas加載用戶(hù)數(shù)據(jù)，因?yàn)閷?dǎo)出數(shù)據(jù)時(shí)沒(méi)有設(shè)置數(shù)據(jù)表頭，所以需要把header設(shè)置為none，同時(shí)設(shè)置表頭sid、cid和canceled。加載用戶(hù)數(shù)據(jù)后，顯示前5條數(shù)據(jù)來(lái)查看數(shù)據(jù)是否加載成功（如圖1）。

Apriori算法的基本思想是找出數(shù)據(jù)的頻繁項(xiàng)集合，對(duì)于課程推薦來(lái)說(shuō)，算法依據(jù)是：如果學(xué)生喜歡某些選修課，那么他們可能喜歡另一些選修課。那么怎么確定學(xué)生是否喜歡某門(mén)選修課呢？判斷依據(jù)是：如果學(xué)生注冊(cè)了選修課，同時(shí)也沒(méi)有取消該選修課，那么他們就是喜歡這門(mén)選修課;注冊(cè)過(guò)該選修課，但是隨后又取消了該門(mén)選修課，那么學(xué)生就是不喜歡該門(mén)選修課;沒(méi)有注冊(cè)的課程不知道學(xué)生是否喜歡它們。使用代碼all_courses['favorable'] = all_courses['canceled'] == 0來(lái)判斷學(xué)生是否喜歡某門(mén)選修課，顯示判斷結(jié)果。

Apriori算法比較復(fù)雜，運(yùn)算所需的內(nèi)存量很大。在筆者16G內(nèi)存的機(jī)器下，訓(xùn)練用戶(hù)達(dá)到200的情況下，內(nèi)存使用已達(dá)12G左右。因此本文為了減少運(yùn)算量，使用數(shù)據(jù)集中的一部分來(lái)訓(xùn)練模型。選擇前200個(gè)用戶(hù)的選課數(shù)據(jù)，并篩選出它們喜歡的課程，存儲(chǔ)在favorable_courses里面，然后按學(xué)生id進(jìn)行分類(lèi)。代碼如圖2所示。

從圖2中可以看到，前200名學(xué)生喜歡的課程記錄一共有17152條，按照學(xué)號(hào)分類(lèi)后，一共有199條數(shù)據(jù)。因?yàn)閷W(xué)生是否喜歡某門(mén)選修課程是一個(gè)固定已知常量，所以將它的類(lèi)型設(shè)置為frozenset，這樣做的原因是能夠加快后面Apriori算法的運(yùn)行速度。

然后，創(chuàng)建一個(gè)新的集合，用來(lái)觀察前200名學(xué)生中喜歡的選修課喜歡的人的數(shù)量，并且按照喜歡的人數(shù)進(jìn)行降序排列，顯示其前5位。

Apriori算法的流程是使用最小支持度生成最初頻繁項(xiàng)集。然后不斷迭代循環(huán)，查找現(xiàn)有頻繁項(xiàng)集的超集，并判斷新生的集合是否頻繁，如果不是，算法迭代完成，如果不是把生成的集合當(dāng)作新的查找集合，繼續(xù)查找頻繁集合，直到完成為止。

生成頻繁項(xiàng)集合時(shí)，每次加入學(xué)生已經(jīng)訂閱過(guò)但是卻沒(méi)有出現(xiàn)在里面的課程，用它生成新的數(shù)據(jù)項(xiàng)。每次新生成的數(shù)據(jù)項(xiàng)集合都會(huì)與最小支持度比較，判斷它是否足夠頻繁，如果是，則返回作為新的查找集合。如果將最小支持度設(shè)置為50，運(yùn)行代碼，初始項(xiàng)目集合中有50個(gè)頻繁項(xiàng)集。然后對(duì)測(cè)試數(shù)據(jù)進(jìn)行Apriori算法訓(xùn)練，訓(xùn)練數(shù)據(jù)代碼會(huì)顯示，對(duì)于測(cè)試數(shù)據(jù)，最多生成1596個(gè)頻繁項(xiàng)集，同時(shí)也可以看到，隨著迭代次數(shù)的增多，頻繁項(xiàng)集的數(shù)量不斷衰減，Apriori算法只需判斷頻繁數(shù)據(jù)項(xiàng)集合的超集而不需要遍歷所有數(shù)據(jù)，快速收斂正是Apriori算法的優(yōu)點(diǎn)。

生成頻繁數(shù)據(jù)項(xiàng)集合后，我們還需要在該集合中抽取關(guān)聯(lián)規(guī)則。該關(guān)聯(lián)規(guī)則就是課程推薦算法：如果學(xué)生喜歡規(guī)則前提中的所有課程，那么他可能喜歡結(jié)論中的課程。對(duì)待任何一個(gè)頻繁數(shù)據(jù)項(xiàng)集合，都要生成一條這樣的關(guān)聯(lián)規(guī)則。

如上頁(yè)圖3所示，遍歷每一次頻繁數(shù)據(jù)項(xiàng)集合，對(duì)其中的每一個(gè)頻繁數(shù)據(jù)項(xiàng)，收取一條記錄作為結(jié)論，其余記錄作為條件，并把它加入備選關(guān)聯(lián)規(guī)則集。一共生成了29188條關(guān)聯(lián)規(guī)則集合。

打印第10000條到10005條備選關(guān)聯(lián)規(guī)則，如圖4所示，其中frozenset（）表示前提條件，學(xué)生喜歡的選修課程，后面是結(jié)論，學(xué)生可能喜歡的選修課程。例如，學(xué)生喜歡id為296、2858、2571、356的選修課程，那么他可能喜歡第260條選修課程。

篩選備選關(guān)聯(lián)規(guī)則。遍歷所有學(xué)生喜歡的課程集合，首先判斷學(xué)生是否喜歡關(guān)聯(lián)規(guī)則前提下的所有選修課程。如果喜歡，則判斷用戶(hù)是否喜歡結(jié)論中的課程。如果是，則關(guān)聯(lián)規(guī)則有效，如果不是，關(guān)聯(lián)規(guī)則無(wú)效。用規(guī)則成功的次數(shù)除以所有應(yīng)用規(guī)則的次數(shù)，得到規(guī)則的置信度，即生成9245條有效關(guān)聯(lián)規(guī)則。對(duì)前5條有效關(guān)聯(lián)規(guī)則進(jìn)行排序，得到的關(guān)聯(lián)規(guī)則的置信度均為1。

4.數(shù)據(jù)處理的結(jié)果

最后對(duì)生成的關(guān)聯(lián)規(guī)則進(jìn)行測(cè)試，測(cè)試數(shù)據(jù)選取除去訓(xùn)練數(shù)據(jù)的用戶(hù)數(shù)據(jù)。對(duì)于每一條關(guān)聯(lián)規(guī)則，首先判斷關(guān)聯(lián)規(guī)則的前提是否在測(cè)試數(shù)據(jù)中，如果是，則判斷關(guān)聯(lián)規(guī)則的結(jié)論是否在測(cè)試數(shù)據(jù)中，如果在，則關(guān)聯(lián)規(guī)則有效。用規(guī)則成功的次數(shù)除以所有應(yīng)用規(guī)則的次數(shù)，得到規(guī)則的置信度——共生成9245條有效關(guān)聯(lián)規(guī)則。對(duì)執(zhí)行規(guī)則進(jìn)行排序后，打印出前五條關(guān)聯(lián)規(guī)則以及他們的訓(xùn)練置信度和測(cè)試置信度。不難發(fā)現(xiàn)，最高置信度規(guī)則為0.903。在測(cè)試中對(duì)于選修了id為1210、589選修課程的學(xué)生來(lái)說(shuō)，有90.3%的可能性選擇id為1196的選修課程。

Apriori算法的改進(jìn)

分析上述Apriori算法，每次通過(guò)遍歷候選數(shù)據(jù)集，比較它是不是第k-1次頻繁項(xiàng)集的子集，若是，則把它加入第k次頻繁項(xiàng)集，若不是則將該數(shù)據(jù)集舍去。當(dāng)數(shù)據(jù)挖掘的數(shù)據(jù)量不大時(shí)，這不會(huì)造成什么影響。當(dāng)挖掘的數(shù)據(jù)量變大時(shí)，每次比較和刪除數(shù)據(jù)集將會(huì)造成很大的性能損失。性能損失主要有兩方面，一是每次比較是不是k-1次頻繁項(xiàng)目集的子集時(shí)查找所帶來(lái)的性能損失，二是每次刪去數(shù)據(jù)集合時(shí)IO操作帶來(lái)的性能損失。數(shù)據(jù)集越大，這兩個(gè)操作帶來(lái)的損失越大。

解決上述問(wèn)題的方案有兩種，一是減小頻繁備選數(shù)據(jù)集的生成數(shù)量。當(dāng)合適的備選數(shù)據(jù)集生成得越少時(shí)，在數(shù)據(jù)查找和刪去無(wú)效數(shù)據(jù)集合上所花費(fèi)的時(shí)間和IO操作就會(huì)變少。二是減少查找所花費(fèi)的時(shí)間。每次查找都是按照順序查找完成的，時(shí)間復(fù)雜度為O（n），如果每次將上一次生成的頻繁數(shù)據(jù)集映射到Hash表上，那么子集比較的時(shí)間復(fù)雜度為O（1），生成頻繁項(xiàng)集的時(shí)間也從O（n2）下降到O（n）。

我們知道，第k次頻繁數(shù)據(jù)集一定是第k-1次的子集，因此我們可以將k-1次的數(shù)據(jù)集合兩兩合并，生成備選數(shù)據(jù)集合，再與第k-1次數(shù)據(jù)集合進(jìn)行比較，而不是從原始數(shù)據(jù)集合中生成Cnk個(gè)備選數(shù)據(jù)集合，然后與k-1次頻繁數(shù)據(jù)集合比較，刪去不合適的頻繁數(shù)據(jù)集合。同時(shí)，將每次生成的頻繁項(xiàng)集映射到Hash桶中，以降低比較所花費(fèi)的時(shí)間。修改數(shù)據(jù)集查找算法，修改后的算法如上頁(yè)圖5所示。

上述查找算法遍歷第k-1次頻繁項(xiàng)集，不斷比較兩個(gè)頻繁項(xiàng)集之間的前k-2項(xiàng)是否相同，然后生成新的頻繁項(xiàng)集的備選集合。由上文分析可知，頻繁項(xiàng)集的子集一定是頻繁的它的逆否命題，不平凡的集合一定不是頻繁項(xiàng)的子集。于是遍歷以前產(chǎn)生的k-1次頻繁項(xiàng)集，查找新生成的頻繁項(xiàng)集是否包含這些子集。如果包含，則保留，如果不包含，則刪去該備選集合。

以上文學(xué)生數(shù)據(jù)作為訓(xùn)練數(shù)據(jù)，比較改進(jìn)前和改進(jìn)后的算法，算法執(zhí)行時(shí)間明顯縮短。

Apriori算法的應(yīng)用

如上所述，在數(shù)據(jù)挖掘平臺(tái)生成關(guān)聯(lián)規(guī)則以后，將關(guān)聯(lián)規(guī)則存儲(chǔ)內(nèi)存中。每次用戶(hù)登錄時(shí)，電化教學(xué)系統(tǒng)向數(shù)據(jù)挖掘平臺(tái)發(fā)送該用戶(hù)目前的選課列表，高性能數(shù)據(jù)挖掘服務(wù)器根據(jù)用戶(hù)數(shù)據(jù)，選擇合適的關(guān)聯(lián)規(guī)則，向用戶(hù)推薦課程。將數(shù)據(jù)挖掘平臺(tái)和前端系統(tǒng)分離的原因是數(shù)據(jù)挖掘系統(tǒng)計(jì)算量很大，如果和電化教學(xué)系統(tǒng)共享一臺(tái)主機(jī)，將會(huì)影響電化教學(xué)系統(tǒng)的性能。

Apriori系統(tǒng)測(cè)試

1.系統(tǒng)功能測(cè)試

后臺(tái)系統(tǒng)具有備課中心、課程管理、教學(xué)互動(dòng)、組織結(jié)構(gòu)、用戶(hù)管理、統(tǒng)計(jì)報(bào)表、校本資源、網(wǎng)絡(luò)硬盤(pán)、系統(tǒng)設(shè)置等9大功能。備課中心負(fù)責(zé)添加課程、試題和資源。課程管理負(fù)責(zé)課程的審批和發(fā)布。教學(xué)互動(dòng)是討論交流環(huán)節(jié)板塊，教師可以在此添加課程內(nèi)容，發(fā)布作業(yè)，回答學(xué)生的提問(wèn)。組織結(jié)構(gòu)負(fù)責(zé)管理學(xué)生班級(jí)和專(zhuān)業(yè)，系統(tǒng)管理員可以在用戶(hù)管理模塊添加學(xué)生、教師等角色。統(tǒng)計(jì)報(bào)表功能能夠統(tǒng)計(jì)課程的播放次數(shù)、資源的下載次數(shù)。通過(guò)本系統(tǒng)，管理員和教師能夠有效地管理電化教學(xué)系統(tǒng)。

以添加題庫(kù)為例，選擇備課中心→題庫(kù)管理→添加試題，會(huì)新增一個(gè)題目輸入框，在此輸入框中可以輸入試題的題面，也可以從Word導(dǎo)入題面，在標(biāo)準(zhǔn)答案輸入框中可以輸入該試題的答案。同時(shí)，可以控制題目的難易程度和所要考查的知識(shí)點(diǎn)，點(diǎn)擊提交按鈕即可完成試題的添加。

2.推薦系統(tǒng)的測(cè)試

基于Apriori算法的熱門(mén)課程推薦，每次推薦的課程將和學(xué)生完成的觀看的課程相關(guān)。系統(tǒng)測(cè)試用戶(hù)完成了一個(gè)模擬電路的課程，因此推薦的都是和電工相關(guān)的課程。現(xiàn)在，已經(jīng)得出了每條規(guī)則的置信度，如何評(píng)估算法的性能呢？這里采用平均置信度這一評(píng)估標(biāo)準(zhǔn)，即把Apriori算法產(chǎn)生的9245條推薦規(guī)則的置信度做一次均值運(yùn)算，和普通的最近最常訪(fǎng)問(wèn)算法做對(duì)比，比較算法的性能。代碼如上頁(yè)圖6所示。從圖6中可以看出，Apriori算法的性能遠(yuǎn)高于最近最常所使用算法。數(shù)據(jù)挖掘技術(shù)能夠有效地提升課程推薦的準(zhǔn)確度。

結(jié)束語(yǔ)

本文重點(diǎn)介紹了兩個(gè)問(wèn)題的數(shù)據(jù)挖掘過(guò)程：登錄日志的數(shù)據(jù)挖掘和課程推薦的數(shù)據(jù)挖掘。兩個(gè)數(shù)據(jù)挖掘過(guò)程均很好地完成了數(shù)據(jù)挖掘任務(wù)并獲取了相關(guān)結(jié)論，對(duì)改進(jìn)電化教學(xué)系統(tǒng)、提高教學(xué)質(zhì)量有著很重要的意義。

參考文獻(xiàn)：

李廣璞，黃妙華.頻繁項(xiàng)集挖掘的研究進(jìn)展及主流方法[J].計(jì)算機(jī)科學(xué)，2018，45（S2）：1-11+26.

作者簡(jiǎn)介：吳浩，江蘇省海安中等專(zhuān)業(yè)學(xué)校講師，碩士研究生畢業(yè)，研究方向?yàn)樾畔⒒虒W(xué)與教學(xué)改革。

基金項(xiàng)目：本文是第四期江蘇省教育科學(xué)研究院立項(xiàng)的職業(yè)教育教學(xué)改革重點(diǎn)課題（編號(hào)ZCZ39）的研究成果之一;也是江蘇聯(lián)合職業(yè)技術(shù)學(xué)院立項(xiàng)課題（編號(hào)B/2018/07/119）的研究成果之一。