利用維基百科點(diǎn)擊流的概念依賴關(guān)系識(shí)別方法

胡 成，陳 昊，肖 奎

(湖北大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，武漢 430062)

E-mail:xiaokui@hubu.edu.cn

1 引 言

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

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

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

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

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

2 相關(guān)研究

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

基于"A-B"點(diǎn)擊流數(shù)據(jù)的概念對(duì)的特征主要反應(yīng)了概念A(yù)與B的直接依賴關(guān)系.本文根據(jù)"A-B"點(diǎn)擊流數(shù)據(jù)建立了6個(gè)概念對(duì)的特征，這些特征來自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)之差的絕對(duì)值.

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

(2)

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

(3)

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

(4)

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

(5)

4.2 "RA-B"點(diǎn)擊流數(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)之差的絕對(duì)值.

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

(9)

(10)

(11)

4.3 "A-RB"點(diǎn)擊流數(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)之差的絕對(duì)值.

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

(15)

(16)

(17)

4.4 "RA-RB"點(diǎn)擊流數(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)之差的絕對(duì)值.

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

(21)

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

(22)

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

(23)

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

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

5 實(shí) 驗(yàn)

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

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

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

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

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

5.2 方法評(píng)估

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

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

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

表3 方法評(píng)估結(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值均比其他分類器高.同樣隨機(jī)森林在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分類器進(jìn)行后續(xù)的實(shí)驗(yàn).

5.3 與baseline方法的比較

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

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

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

5.4 跨領(lǐng)域分析

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

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

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

6 總 結(jié)

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

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