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

引言

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

Apriori算法

1.Apriori算法介紹

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

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

Apriori算法首先要設立一個最小支持度，這是Apriori算法的重點和精髓所在。因為Apriori算法只考慮頻繁的集合，而忽略不頻繁的集合，故必須設定一個最小支持度來制訂頻繁集合的下限。正因為Apriori算法不必考慮全部集合，所以Apriori算法的計算時間較短，效率相對比較高。

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

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

網(wǎng)絡教學平臺課程分為必修課程和選修課程。必修課程是按照教師要求，班級統(tǒng)一注冊的課程，該類型課程具有強制性，學生不可取消。選修課程是學生根據(jù)自己的興趣選學的課程，可以隨時取消學習。在課程推薦系統(tǒng)中，應該推薦選修課程而不是必修課程，這一是因為不同班級的學習要求可能不同，二是因為必修課程選課基數(shù)大，構建選課系統(tǒng)時，會產(chǎn)生一定噪聲問題。因此，本文的課程推薦算法只設計選修課程的推薦。

筆者使用compulsory字段來判斷一門課是不是選修課。所使用的代碼為：

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條學生的選修課信息，并用DataStrip的數(shù)據(jù)導出功能導出CSV數(shù)據(jù)。因為數(shù)據(jù)庫里的數(shù)據(jù)十分規(guī)則，所以這里的數(shù)據(jù)不需要做數(shù)據(jù)清洗。

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

首先使用pandas加載用戶數(shù)據(jù)，因為導出數(shù)據(jù)時沒有設置數(shù)據(jù)表頭，所以需要把header設置為none，同時設置表頭sid、cid和canceled。加載用戶數(shù)據(jù)后，顯示前5條數(shù)據(jù)來查看數(shù)據(jù)是否加載成功（如圖1）。

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

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

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

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

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

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

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

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

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

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

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

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

Apriori算法的改進

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

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

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

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

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

Apriori算法的應用

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

Apriori系統(tǒng)測試

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

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

以添加題庫為例，選擇備課中心→題庫管理→添加試題，會新增一個題目輸入框，在此輸入框中可以輸入試題的題面，也可以從Word導入題面，在標準答案輸入框中可以輸入該試題的答案。同時，可以控制題目的難易程度和所要考查的知識點，點擊提交按鈕即可完成試題的添加。

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

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

結束語

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

參考文獻：

李廣璞，黃妙華.頻繁項集挖掘的研究進展及主流方法[J].計算機科學，2018，45（S2）：1-11+26.

作者簡介：吳浩，江蘇省海安中等專業(yè)學校講師，碩士研究生畢業(yè)，研究方向為信息化教學與教學改革。

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