胡 成，陳 昊，肖 奎

(湖北大學 計算機與信息工程學院，武漢 430062)

E-mail:xiaokui@hubu.edu.cn

1 引 言

伴隨著互聯(lián)網(wǎng)上學習平臺的增加，網(wǎng)絡(luò)學習逐漸成為一種學習常態(tài).在MOOC課程體系中，不同章節(jié)或不同視頻的概念間往往存在著依賴關(guān)系，這種概念依賴關(guān)系可指導(dǎo)學習者的學習順序.對于兩個概念(A，B)，如果學習者在學習概念B之前必須先理解概念A(yù)的含義，那么我們就說概念B依賴于概念A(yù).本文將以維基百科為例研究概念間的依賴關(guān)系挖掘問題.

維基百科作為世界上最知名互聯(lián)網(wǎng)百科全書之一，幾乎囊括了學習者需要的所有概念知識.維基百科概念是指詞條的標題，一個維基百科概念就代表著一個詞條.如果一個概念B依賴于概念A(yù)，那么就意味著理解B的詞條內(nèi)容，需要同時閱讀一下A的詞條內(nèi)容，因為A中包含了一些理解B的詞條內(nèi)容所需的背景知識.當學習者瀏覽概念B的詞條后，緊接著瀏覽概念A(yù)的詞條，像這樣的行為我們稱之為“點擊流”，維基百科官方公布最近30個月用戶的點擊流數(shù)據(jù)(1)https://dumps.wikimedia.org/other/clickstream/，而維基百科概念之間的依賴關(guān)系往往蘊含在這些點擊流數(shù)據(jù)中.通過識別維基百科概念間的依賴關(guān)系，可以生成詞條的學習順序列表，解決學習者因為缺乏背景知識而無法理解詞條內(nèi)容的問題.

當前主流的一些維基百科概念依賴關(guān)系挖掘方法，都是利用維基百科詞條間的鏈接關(guān)系、分類層次、文本內(nèi)容等詞條自身的特征進行概念依賴關(guān)系預(yù)測[11-13].相比于前文的研究，本文的貢獻主要有以下兩方面：

1)提出一種基于維基百科點擊流數(shù)據(jù)的概念依賴關(guān)系挖掘方法，利用維基百科中的用戶點擊流數(shù)據(jù)建立特征，預(yù)測兩個概念間是否存在依賴關(guān)系.

2)通過引入相關(guān)概念集合不僅提升了概念對的覆蓋率，而且保持了較好的概念依賴關(guān)系預(yù)測準確率.

2 相關(guān)研究

最早進行維基百科概念依賴關(guān)系挖掘研究的是Talukdar和Cohen[11]，作者認為如果概念B的詞條中如果包含了一個鏈接指向概念A(yù)，那么概念B很有可能依賴于概念A(yù).文章利用它們兩個概念間的鏈接信息、編輯信息、內(nèi)容信息設(shè)計特征，然后使用MaxEnt分類器預(yù)測概念間的依賴關(guān)系，但其平均準確率只有60%左右.

Liang等人[12，15，16]提出一種基于概念引用距離(RefD)的方法預(yù)測兩個維基百科概念間的依賴關(guān)系.Zhou等人[13，17，20]建立了四組維基百科概念對的特征，包括基于鏈接、基于分類、基于文本內(nèi)容以及基于時間關(guān)系的特征，作者隨后采用六種不同的機器學習分類器進行實驗，實驗結(jié)果表明隨機森林分類器可以在中文和英文數(shù)據(jù)集上表現(xiàn)出較好的效果.

上述方法都是基于維基百科概念本身的特征進行概念依賴關(guān)系預(yù)測.Sayyadiharikandeh等人[14]提出了基于維基百科點擊流(Wikipedia clickstream)數(shù)據(jù)來推斷概念間依賴關(guān)系的方法.這是研究人員首次利用用戶交互行為預(yù)測概念對間的依賴關(guān)系.但是，此方法的主要問題在于，用戶日志所覆蓋的維基百科概念對的比例過于偏低，我們無法利用它來預(yù)測大多數(shù)維基百科概念對間的依賴關(guān)系.他們的研究工作與本文比較相近，所以本文將選擇他們的研究作為我們的一個baseline方法.

此外，還有一些研究工作也與本文研究相關(guān).Liang等人[15，16]在維基百科概念依賴關(guān)系預(yù)測任務(wù)中引入了Active learning方法，從而可以用更少量的訓練集樣本來獲得同等的預(yù)測準確率.Zhou等人[17]也嘗試了利用bagging+boosting的改進式集成學習方法進行維基百科概念依賴關(guān)系的預(yù)測.Alzetta等人[18]研究了如何幫助標注人員建立更準確的概念依賴關(guān)系數(shù)據(jù)集的問題.Chen等人[19]研究了如何利用概念依賴關(guān)系對教學平臺上學生的知識狀態(tài)信息進行補齊，從而實現(xiàn)對學生的知識狀態(tài)的追蹤(knowledge tracing).Wang等人[22]基于改進型協(xié)同過濾設(shè)計出網(wǎng)絡(luò)學習資源的個性化推薦算法.Wang等人[21]利用課程屬性與維基百科屬性設(shè)計特征，識別課程概念間的依賴關(guān)系，這需要一對概念對中的兩個概念必須同時出現(xiàn)在一門課程的課程簡介中，本文方法則并無此要求，凡是維基百科中的概念，均可利用點擊流數(shù)據(jù)實現(xiàn)概念依賴關(guān)系的識別.本文從概念層面出發(fā)，針對Sayyadiharikandeh等人[14]設(shè)計特征值存在的問題，提出利用相關(guān)概念集合方法預(yù)測概念間的依賴關(guān)系.

3 概念依賴關(guān)系識別任務(wù)的定義

為了方便起見，本文規(guī)定對于任意一組概念對(A，B)，其中的兩個概念都必須來自同一個領(lǐng)域.本文中的領(lǐng)域是指一個維基百科分類.一個維基百科分類通常包含了一些詞條和一些子分類，而每個子分類也是由詞條和下級子分類構(gòu)成.換言之，在維基百科知識體系中，領(lǐng)域名稱對應(yīng)的結(jié)點是概念A(yù)與概念B的共同祖先結(jié)點.維基百科知識體系的示例如圖1所示.

圖1 維基百科知識體系示例Fig.1 Wikipedia knowledge system example

對于兩個概念(A，B)，它們之間的關(guān)系可能存在多種情況，比如B依賴于A、A依賴于B、A與B相關(guān)但兩者沒有依賴關(guān)系、A與B不相關(guān)、A與B關(guān)系不清楚[11].本文采用與以研究人員相同的方法，二分類方式來處理這個問題，即只區(qū)分B依賴于A、B不依賴于A兩種情況[11-14].

4 概念依賴關(guān)系識別方法

在維基百科點擊流日志數(shù)據(jù)中，不可能每一對概念都有點擊流數(shù)據(jù)，即從A跳轉(zhuǎn)到B(用戶瀏覽A的詞條后立即瀏覽B的詞條，為了方便以下統(tǒng)稱為從A跳轉(zhuǎn)到B)，或從B跳轉(zhuǎn)到A的情況.因為大多數(shù)維基百科詞條不是熱點話題，不容易被注意，在過去30個月中并沒有任何用戶瀏覽過它們.如果只考慮A與B之間的跳轉(zhuǎn)次數(shù)，那么點擊流日志數(shù)據(jù)能夠覆蓋的概念對的比例會比較低.

本文將利用每個維基百科概念的“相關(guān)概念集合”，來擴大點擊流數(shù)據(jù)的概念對的覆蓋率.首先，我們將本節(jié)使用到的一些基本術(shù)語定義如表1.

表1 基本術(shù)語定義Table 1 Definition of basic terms

在框架語義理論中[12]，一個概念可以由它的“相關(guān)概念集合”來表示，A的“相關(guān)概念集合”與B的“相關(guān)概念集合”的關(guān)系，即A與B的關(guān)系.對于一對概念(A，B)，如果只考慮A與B之間直接的點擊流數(shù)據(jù)("A-B")，那么這樣的點擊流數(shù)據(jù)能夠覆蓋的概念對數(shù)量往往偏少.因此，為了擴大點擊流數(shù)據(jù)的概念對覆蓋率，本文除了考慮兩個概念間直接的跳轉(zhuǎn)次數(shù)("A-B")以外，也考慮了A的相關(guān)概念與B的跳轉(zhuǎn)次數(shù)("RA-B")、A與B的相關(guān)概念的跳轉(zhuǎn)次數(shù)("A-RB")、A的相關(guān)概念與B的相關(guān)概念的跳轉(zhuǎn)次數(shù)("RA-RB")，這樣將會擴大考察的概念的范圍，顯著提升概念對的覆蓋率.

根據(jù)上述4種不同類別的點擊流數(shù)據(jù)，本文為維基百科概念對設(shè)計了4類特征，用于概念依賴關(guān)系的識別.本文使用了維基百科網(wǎng)站發(fā)布的最近30個月的用戶點擊流數(shù)據(jù)來建立概念對的特征.

4.1 "A-B"點擊流數(shù)據(jù)的特征

基于"A-B"點擊流數(shù)據(jù)的概念對的特征主要反應(yīng)了概念A(yù)與B的直接依賴關(guān)系.本文根據(jù)"A-B"點擊流數(shù)據(jù)建立了6個概念對的特征，這些特征來自Sayyadiharikandeh等人的研究工作[14].具體的內(nèi)容如下：

?Weight1(A，B)：用戶從概念A(yù)跳轉(zhuǎn)到B的詞條次數(shù)，即用戶瀏覽了概念A(yù)的詞條以后立即瀏覽概念B的詞條的次數(shù).

?Weight1(B，A)：用戶從概念B的詞條跳轉(zhuǎn)到A的詞條的次數(shù).

?Sum1(A，B)：Weight1(A，B)與Weight1(B，A)之和.

Sum1(A，B)=Weight1(A，B)+Weight1(B，A)

(1)

?Diff1(A，B)：Weight1(A，B)與Weight1(B，A)之差的絕對值.

Diff1(A，B)=|Weight1(A，B)-Weight1(B，A)|

(2)

?Norm1(A)：對Weight1(A，B)進行規(guī)范化處理.

(3)

其中，Sat1(i)為用戶從概念i跳轉(zhuǎn)到其它所有概念的次數(shù)之和.

(4)

?Norm1(B)：對Weight1(B，A)進行規(guī)范化處理.

(5)

4.2 "RA-B"點擊流數(shù)據(jù)的特征

(6)

(7)

?Sum2(A，B)：Weight2(A，B)與Weight2(B，A)之和.

Sum2(A，B)=Weight2(A，B)+Weight2(B，A)

(8)

?Diff2(A，B)：Weight2(A，B)與Weight2(B，A)之差的絕對值.

Diff2(A，B)=|Weight2(A，B)-Weight2(B，A)|

(9)

(10)

(11)

4.3 "A-RB"點擊流數(shù)據(jù)的特征

(12)

(13)

?Sum3(A，B)：Weight3(A，B)與Weight3(B，A)之和.

Sum3(A，B)=Weight3(A，B)+Weight3(B，A)

(14)

?Diff3(A，B)：Weight3(A，B)與Weight3(B，A)之差的絕對值.

Diff3(A，B)=|Weight3(A，B)-Weight3(B，A)|

(15)

(16)

(17)

4.4 "RA-RB"點擊流數(shù)據(jù)的特征

(18)

Weight1(r1，r2)>0

(19)

?Sum4(A，B)：Weight4(A，B)與Weight4(B，A)之和.

Sum4(A，B)=Weight4(A，B)+Weight4(B，A)

(20)

?Diff4(A，B)：Weight4(A，B)與Weight4(B，A)之差的絕對值.

Diff4(A，B)=|Weight4(A，B)-Weight4(B，A)|

(21)

?Norm4(A)：對從A的相關(guān)概念跳轉(zhuǎn)到B的相關(guān)概念的次數(shù)之和進行規(guī)范化處理.

(22)

?Norm4(B)：對從B的相關(guān)概念跳轉(zhuǎn)到A的相關(guān)概念的次數(shù)之和進行規(guī)范化處理.

(23)

如前所述，“相關(guān)概念集合”代表了概念本身，所以總體而言，上述4個特征分別直接和間接的表示了從A跳轉(zhuǎn)到B的次數(shù)，其中第一個特征Weight1(A，B)描述了A與B的直接跳轉(zhuǎn)關(guān)系，其它3個特征——Weight2(A，B)、Weight3(A，B)與Weight4(A，B)描述了A與B的間接跳轉(zhuǎn)關(guān)系.

另一方面，由于f1(·，·)這樣描述直接關(guān)系的特征只能覆蓋少數(shù)概念對.也就是說，維基百科中有相當一部分概念對，因為用戶沒有瀏覽這些詞條，使得描述它們直接關(guān)系的f1(·，·)特征值并不存在，而類似f2(·，·)、f3(·，·)與f4(·，·)這樣描述它們間接關(guān)系的特征值卻存在.本文將利用24對特征進行維基百科概念依賴關(guān)系的預(yù)測.

5 實 驗

5.1 數(shù)據(jù)集

本文使用了Liang等人建立的AL-CPL數(shù)據(jù)集[15]對提出方法的有效性進行驗證.其中包含了Data-mining、Geometry、Physic與Pre-calculus共4個領(lǐng)域的6529對維基百科概念.

針對上述數(shù)據(jù)集，本文首先從維基百科網(wǎng)站獲取了從2017年11月到2020年4月的點擊流數(shù)據(jù)，分別計算在每個領(lǐng)域中，維基百科概念對覆蓋的比例，也就是概念對覆蓋率，具體結(jié)果如圖2所示，橫坐標表示領(lǐng)域名稱，縱坐標表示覆蓋率.

圖2 AL-CPL數(shù)據(jù)的概念對覆蓋度Fig.2 Concept of AL-CPL data coverage

從圖2中可以看出，在引入相關(guān)概念集合以后，點擊流數(shù)據(jù)的概念對覆蓋率都達到90%以上，相比直接的概念對覆蓋率有了大幅的提升.

5.2 方法評估

本文使用Precision(P)、Recall(R)、F1-Score(F1)和Area Under Curve(AUC)4個度量指標對提出方法的性能進行度量，實驗過程采用五折交叉驗證方式進行評估.本文使用7種常見的機器學習分類器進行概念依賴關(guān)系預(yù)測，這些分類器包括隨機森林(RF)、樸素貝葉斯(NB)、C4.5決策樹(C4.5)、多層感知器(MLP)、支持向量機(SVM)、邏輯回歸(LR)和AdaBoost(Ada).所有分類器均采用sklearn庫實現(xiàn)，各分類器使用的參數(shù)均為默認參數(shù).本文使用過采樣方法讓訓練樣本中的類別平衡，表2顯示了使用過采樣方法后，訓練集樣本中的正例與反例數(shù)量.

表2 訓練集樣本中的正例與反例的數(shù)量Table 2 Number of positive and negative examples in the training data

表3顯示了提出方法在AL-CPL數(shù)據(jù)集上的評估結(jié)果.

表3 方法評估結(jié)果Table 3 Method evaluation results

從表3中可以看出，AdaBoost在Geometry、Physics、Pre-calculus數(shù)據(jù)集上的F1值和AUC值均比其他分類器高，在Data-mining數(shù)據(jù)集上的F1和在Geometry數(shù)據(jù)集上的R值均比其他分類器高.同樣隨機森林在Data-mining、Geometry、Physics、Pre-calculus數(shù)據(jù)集上的P值和在Data-mining數(shù)據(jù)集上的AUC值表現(xiàn)比其他分類器好；樸素貝葉斯在Data-mining、Physics、Pre-calculus數(shù)據(jù)集上的R值表現(xiàn)比其他分類器好.總體而言，AdaBoost在概念依賴關(guān)系預(yù)測任務(wù)中表現(xiàn)最好.我們將采用AdaBoost分類器進行后續(xù)的實驗.

5.3 與baseline方法的比較

本文選擇了兩個baseline方法進行比較.第1個是Liang等人[12]提出的計算概念引用距離(RefD)識別概念依賴關(guān)系的方法，作者在其中運用了兩種方式定義維基百科概念的每個相關(guān)概念的權(quán)值，分別是Equal(所有相關(guān)概念權(quán)值均設(shè)置為1)和Tf-idf(所有相關(guān)概念權(quán)值設(shè)置為它們的Tf-idf值)，實驗將分別與這兩種模式(RefD-Equal與RefD-Tfidf)進行比較.第2個是Sayyadiharikandeh等人[14]提出基于維基百科點擊流數(shù)據(jù)來識別概念依賴關(guān)系的方法.我們將按照原文的思想計算概念依賴關(guān)系預(yù)測的結(jié)果.

圖3顯示了本文方法與baseline方法在概念依賴關(guān)系預(yù)測準確率(Accuracy)方面的比較結(jié)果.從表中可以看出，本文方法在3個數(shù)據(jù)集上的準確率都高于3個baseline方法.在Pre-calculus數(shù)據(jù)集上，本文方法的概念依賴關(guān)系預(yù)測準確率略低于RefD-Tfidf方法，但是仍然高于其它baseline方法.我們猜想可能是在Pre-calculus數(shù)據(jù)集中的概念對來自微積分教科書，因此不同概念對的概念之間相較其他數(shù)據(jù)集存在更多的聯(lián)系，導(dǎo)致本文方法在判斷概念依賴關(guān)系時預(yù)測，將那些有依賴關(guān)系的概念對，但是由于點擊次數(shù)偏少，特征值偏低，誤判為沒有依賴關(guān)系.實驗結(jié)果表明本文提出的方法在維基百科概念依賴關(guān)系預(yù)測任務(wù)中具有較好的性能.

圖3 與baseline方法的比較Fig.3 Comparison with baseline method

5.4 跨領(lǐng)域分析

一般情況下，機器學習實驗的訓練集和測試集數(shù)據(jù)會來自同一個領(lǐng)域(in-domain training).但是這也意味著我們需要為每個感興趣的領(lǐng)域都準備好相應(yīng)的訓練集數(shù)據(jù)，很多時候這個前提條件是無法實現(xiàn)的.如果我們可以用來自不同領(lǐng)域的訓練集與測試集數(shù)據(jù)進行實驗(out-of-domain training)，也能達到近似的分類效果，那么這將有助于改進我們的分類器，或者可以采用一些可替代的方法訓練數(shù)據(jù).

按照這個思路，我們對 AL-CPL數(shù)據(jù)集進行in-domain和out-of-domain實驗.每次選擇一個領(lǐng)域的數(shù)據(jù)集作為測試集，其它領(lǐng)域的數(shù)據(jù)集作為訓練集.圖4顯示了AL-CPL數(shù)據(jù)集的實驗結(jié)果.從圖中可以看出，AL-CPL數(shù)據(jù)集的4個領(lǐng)域的in-domain分類準確率都要高于out-of-domain，而out-of-domain訓練的分類準確率也均在60%以上，與in-domain分類準確率比較接近.

圖4 AL-CPL數(shù)據(jù)集跨領(lǐng)域分析Fig.4 Cross-domain analysis of AL-CPL data

6 總 結(jié)

本文利用維基百科點擊流數(shù)據(jù)以及每個概念的相關(guān)概念集合建立概念對特征，預(yù)測兩個概念間的依賴關(guān)系.實驗表明，通過引入相關(guān)概念集合，可以顯著擴大點擊流數(shù)據(jù)的概念對覆蓋率，同時保持較高的概念依賴關(guān)系預(yù)測的準確率.

概念依賴關(guān)系挖掘是概念圖抽取、學習對象排序、學習路徑規(guī)劃以及閱讀順序列表生成等任務(wù)的重要基礎(chǔ).當前的研究僅限于維基百科中概念依賴關(guān)系的挖掘，后續(xù)我們將考慮如何從文本、視頻等學習對象中直接抽取概念，預(yù)測不同學習對象間的概念依賴關(guān)系，并將這種概念依賴關(guān)系用于智能輔導(dǎo)等智慧教育的服務(wù)中.