基于方向權(quán)值標(biāo)簽傳播的微學(xué)習(xí)單元聚類算法

胡志遠, 張月琴*, 陳健,2

(1.太原理工大學(xué)信息與計算機學(xué)院, 晉中 030600; 2.賽博大學(xué)信息技術(shù)綜合學(xué)院, 日本 福岡 8130017)

互聯(lián)網(wǎng)開啟的信息時代,令工作、生活、學(xué)習(xí)的節(jié)奏加快,同時也導(dǎo)致作息時間的碎片化。為適應(yīng)利用碎片化時間進行學(xué)習(xí)的需求,一種新型的學(xué)習(xí)模式——微學(xué)習(xí),在2005年被首次提出[1]。這一在線學(xué)習(xí)方式具備的微內(nèi)容、微過程、微媒介、微資源等特點[2],使學(xué)習(xí)者可以合理地利用碎片化時間學(xué)習(xí),為解決學(xué)習(xí)時間碎片化、學(xué)習(xí)場所自主化等問題提供一個好的方案。近年來,微學(xué)習(xí)獲得了越來越多的學(xué)者的關(guān)注和研究,并取得了一定的研究成果[3]。但由于互聯(lián)網(wǎng)的飛速發(fā)展,知識更新的學(xué)習(xí)頻度和數(shù)量越來越大,導(dǎo)致學(xué)習(xí)者在尋找適合自己的學(xué)習(xí)資源時會花費大量的時間。為此,實現(xiàn)學(xué)習(xí)資源的合理組織,可以幫助學(xué)習(xí)者節(jié)省查找學(xué)習(xí)資源的時間,對促進其個性化學(xué)習(xí)具有重要意義。

在學(xué)習(xí)過程中,不同學(xué)習(xí)者由于其知識背景、學(xué)習(xí)習(xí)慣等因素的不同,會存在不同的學(xué)習(xí)偏好,導(dǎo)致其所適合的學(xué)習(xí)單元與學(xué)習(xí)順序有所不同。為了找出適合于不同學(xué)習(xí)偏好的學(xué)習(xí)者的學(xué)習(xí)單元,本文研究將圖聚類技術(shù)應(yīng)用到由不同學(xué)習(xí)者學(xué)習(xí)路徑挖掘得到的學(xué)習(xí)單元之間的特征序列的處理中,以學(xué)習(xí)單元為節(jié)點,以學(xué)習(xí)單元的學(xué)習(xí)順序為有向邊構(gòu)成一個有向圖。

圖聚類是將圖結(jié)構(gòu)中所有節(jié)點劃分至不同簇群中的過程[4]。每個簇群內(nèi)部的節(jié)點具有一定的相關(guān)性,節(jié)點之間的聯(lián)系也更加緊密,不同簇群之間的節(jié)點具有較大的差異性,其聯(lián)系也較弱。近年來,圖聚類作為一個研究熱點,已經(jīng)被應(yīng)用到不同學(xué)科領(lǐng)域,并利用相關(guān)學(xué)科知識開發(fā)了很多算法,如基于標(biāo)簽傳播的算法LPA (label propagation algorithm)[5]、基于信息編碼的算法Infomap[6]、基于隨機游走的算法Walktrap[7]等。

上述算法大多針對的是無向圖,而對于學(xué)習(xí)路徑來說,學(xué)習(xí)單元間存在學(xué)習(xí)先后順序,因此,有向圖比無向圖更適用于表述微學(xué)習(xí)單元的聚類問題。現(xiàn)提出一種以相似學(xué)習(xí)者的學(xué)習(xí)履歷構(gòu)建的有向圖為基礎(chǔ)的基于有向邊權(quán)值的標(biāo)簽傳播算法,實現(xiàn)對微學(xué)習(xí)單元的聚類。該算法以LPA算法為基礎(chǔ),具有以下改進:①提出使用圖節(jié)點的利用度,即利用次數(shù)來確定標(biāo)簽更新順序,以避免標(biāo)簽更新順序上的隨機性;②提出以有向邊權(quán)值以量化有向邊的方向信息,并以其累加值控制標(biāo)簽更新過程;③引入標(biāo)簽權(quán)重以解決簇群的過傳播問題。

1 相關(guān)工作

本節(jié)首先介紹微學(xué)習(xí)單元聚類相關(guān)研究,其次介紹標(biāo)簽傳播算法及其相關(guān)研究。

1.1 微學(xué)習(xí)單元聚類研究

為了解決微學(xué)習(xí)單元因其分散化、海量和多源異構(gòu)性等特性而導(dǎo)致的學(xué)習(xí)內(nèi)容篩選困難,近年來已有研究者通過優(yōu)化聚類技術(shù)來發(fā)現(xiàn)學(xué)習(xí)單元之間的隱藏關(guān)系,實現(xiàn)對微學(xué)習(xí)單元的合理組織。Ding等[8]采用LDA模型對微學(xué)習(xí)單元進行主題建模,提出基于主題特征中心的融合層次聚類算法對學(xué)習(xí)單元進行聚類,表現(xiàn)出良好聚類效果。馮耀武等[9]提出一種改進的骨干粒子群無監(jiān)督特征選擇算法用于選擇微學(xué)習(xí)單元的代表性特征,以提高聚類精度。武國勝等[10]采用LSA模型對微學(xué)習(xí)單元建模,并針對學(xué)習(xí)單元的特性改進了密度峰值聚類算法以提高聚類精度。

以上研究都是以單個微學(xué)習(xí)單元作為研究對象,從而將學(xué)習(xí)單元按照不同的內(nèi)容進行重組。但只是簡單地以學(xué)習(xí)內(nèi)容進行聚類,不能反映不同的學(xué)習(xí)個性與其所適合的學(xué)習(xí)單元之間的聯(lián)系。

1.2 標(biāo)簽傳播算法相關(guān)理論及研究

標(biāo)簽傳播算法(LPA)是Raghavan等[5]于2007年提出的一種基于無向圖的啟發(fā)式社區(qū)發(fā)現(xiàn)算法,因其不需要任何目標(biāo)函數(shù)和先驗信息且具有線性時間復(fù)雜度而廣受關(guān)注。該算法受到流行病傳播的啟發(fā),通過節(jié)點標(biāo)簽的迭代傳播直至收斂來檢測社區(qū)結(jié)構(gòu)。

該算法首先將圖中的每一個節(jié)點看成一個獨立的社區(qū),賦予不同的標(biāo)簽,然后將節(jié)點隨機排列對其遍歷進行標(biāo)簽更新;對于當(dāng)前遍歷到的節(jié)點,統(tǒng)計其鄰居節(jié)點中各個標(biāo)簽出現(xiàn)的頻率,將頻率最高的標(biāo)簽作為當(dāng)前節(jié)點的新標(biāo)簽,若存在多個最高頻率標(biāo)簽,則隨機選擇一個;重復(fù)上述過程,直至所有節(jié)點的標(biāo)簽達到穩(wěn)定,最終擁有相同標(biāo)簽的節(jié)點被劃分到同一個社區(qū)中。目前,LPA算法已被應(yīng)用于改進傳統(tǒng)聚類算法,并且取得較好的效果[11]。

LPA算法因其線性時間復(fù)雜度,經(jīng)過較少的迭代次數(shù)后即可收斂,但也存在一些問題。其一是因其節(jié)點標(biāo)簽更新順序和標(biāo)簽更新策略中存在較大的隨機性,導(dǎo)致社區(qū)劃分結(jié)果的穩(wěn)定性和準(zhǔn)確率下降;其二是因其傳播特性導(dǎo)致在關(guān)系較為緊密的圖結(jié)構(gòu)中容易出現(xiàn)過傳播現(xiàn)象,即較大的社區(qū)很容易將自身的標(biāo)簽傳播給相鄰的小社區(qū),從而形成巨型社區(qū)。為此,研究者們提出許多改進的LPA算法以提高性能。Barer等[12]提出的LPAm (modularity-specialized LPA)算法將模塊度與LPA算法相結(jié)合,通過最大化模塊度函數(shù)來約束標(biāo)簽傳播過程,找出最優(yōu)社區(qū)化分。但算法容易陷入目標(biāo)函數(shù)局部最大值而影響結(jié)果準(zhǔn)確性。為此Liu等[13]提出LPAm+(advanced modularity-specialized LPA)算法,引入多步貪心算法合并相似社區(qū),解決了局部最大值問題,提高了性能。Wang等[14]提出NI_LPA (LPA based on node importance)算法引入節(jié)點重要性,選擇重要性高的節(jié)點標(biāo)簽更新當(dāng)前節(jié)點標(biāo)簽,降低了標(biāo)簽更新過程的隨機性。林天森等[15]提出LPA-IS (LPA based on node importance and similarity)算法,根據(jù)節(jié)點重要性確定節(jié)點更新順序,并將節(jié)點重要性與節(jié)點相似性相結(jié)合提出標(biāo)簽綜合影響力來更新標(biāo)簽。劉揚等[16]提出LRW_LPA (local random walk based LPA)算法通過限制隨機游走的范圍,減小了節(jié)點鄰域范圍過大對節(jié)點歸屬不準(zhǔn)確的影響,提升了社區(qū)劃分的質(zhì)量。鄭文萍等[17]提出LPARW (improved label propagation algorithm based on random walk)算法通過相似性度量確定種子節(jié)點,并只對種子節(jié)點賦予初始標(biāo)簽而更新其他節(jié)點的標(biāo)簽,減小了劃分結(jié)果的不確定性。孫學(xué)良等[18]提出了TS-LPA (two-stage community detection algorithm based on label propagation)算法,結(jié)合廣度優(yōu)先傳播的思想提出兩階段標(biāo)簽更新策略,除相鄰節(jié)點的影響外,加入附近種子節(jié)點的影響,共同完成節(jié)點標(biāo)簽的更新。

上述算法雖然解決了LPA算法的主要問題,但主要是針對無向圖而研究的。相比無向圖,有向圖中的社區(qū)發(fā)現(xiàn)問題,即本文提出的簇群發(fā)現(xiàn)問題被認(rèn)為是一項更具挑戰(zhàn)性的任務(wù)[19]。目前,針對有向圖改進LPA算法的研究較少,常見的方法是忽略有向圖中邊的方向,將其轉(zhuǎn)換成無向圖進行處理。然而,有向邊作為有向圖的關(guān)鍵組成部分,包含著大量的有用信息,直接忽略會導(dǎo)致一些有意義的社區(qū)或簇群被忽略。為了解決這個問題,Leicht等[20]提出了有向模塊度(directed modularity, DQ),將模塊度擴展到有向圖,在最大化模塊度的同時保留了邊的方向信息。Antunovic等[21]提出了OLPAm+ (orientation respecting LPAm+)算法將有向模塊度引入LPAm+算法從而將其擴展到有向無環(huán)圖上,并將其應(yīng)用在課程學(xué)習(xí)網(wǎng)絡(luò)中,表現(xiàn)出良好效果。Li[22]提出了DLAP (directed LPA)算法將邊的局部方向轉(zhuǎn)化為邊的權(quán)重,解決了有向模塊度不能識別局部方向的缺陷。Hosseini-Pozveh等[23]提出了DBLPA (directed balanced LPA)算法,結(jié)合平衡理論改進了DLPA算法,將LPA算法擴展至有向符號網(wǎng)絡(luò)。但二者均忽略了節(jié)點相似性對于劃分結(jié)果的影響。Laassem等[24]將庫侖定律引入LPA算法提出了LPA_CL (LPA for community detection based on Coulomb’s law)算法,提高了準(zhǔn)確性和穩(wěn)定性,但計算庫侖矩陣過程較為復(fù)雜,降低了算法運行效率。

現(xiàn)有的LPA算法改進方法主要針對節(jié)點標(biāo)簽更新順序以及標(biāo)簽更新策略進行,但對圖中已有信息的有效利用并沒有較好的策略,且一些算法效率較低。針對這些問題,現(xiàn)提出一種改進的標(biāo)簽傳播算法應(yīng)用于微學(xué)習(xí)單元的聚類處理中。首先針對學(xué)習(xí)行為特征,提出一種高效的初始化標(biāo)簽更新順序的計算方法。其次將學(xué)習(xí)順序的方向信息和學(xué)習(xí)單元間的相似性相結(jié)合改進標(biāo)簽更新策略,在有效利用已知信息的同時保持較高的運算效率。

2 基于有向邊權(quán)值的標(biāo)簽傳播算法

研究對象為學(xué)習(xí)者利用微學(xué)習(xí)單元進行學(xué)習(xí)的學(xué)習(xí)履歷。為達成一個局部學(xué)習(xí)目標(biāo)的學(xué)習(xí)過程被視為一個學(xué)習(xí)周期。從學(xué)習(xí)履歷中發(fā)現(xiàn)歸屬于同一學(xué)習(xí)周期的微學(xué)習(xí)單元將有助于學(xué)習(xí)者選擇適合的微學(xué)習(xí)單元。利用該履歷,本文研究中嘗試建立一個由微學(xué)習(xí)單元及學(xué)習(xí)順序的特征序列的方向信息組成的有向無權(quán)圖。G=(V,E)被用于表示這一有向圖,其中V={vi},1≤i≤n表示所有學(xué)習(xí)單元節(jié)點的集合,vi表示單個學(xué)習(xí)單元節(jié)點,n表示圖中學(xué)習(xí)單元節(jié)點的數(shù)量;E={ei→j},1≤i≠j≤m表示基于學(xué)習(xí)單元的學(xué)習(xí)順序所形成的有向邊的集合,ei→j表示由學(xué)習(xí)單元vi和vj構(gòu)成的學(xué)習(xí)順序所表示的邊,m表示所有學(xué)習(xí)順序的數(shù)量。

本文提出的LPADEW算法主要包括以下3個過程:節(jié)點利用度計算、節(jié)點間有向邊權(quán)值的計算、利用有向邊權(quán)累加值實現(xiàn)標(biāo)簽更新。首先計算有向圖中各節(jié)點的利用度,將節(jié)點按照利用度升序排列作為標(biāo)簽更新順序;其次計算目標(biāo)學(xué)習(xí)單元節(jié)點與其前置鄰居節(jié)點和后置鄰居節(jié)點的有向邊權(quán)值;最后將屬于不同學(xué)習(xí)周期的簇群標(biāo)簽的有向邊權(quán)值的累加值作為標(biāo)簽的初始選擇依據(jù),再計算歸屬于各學(xué)習(xí)周期的簇群標(biāo)簽權(quán)值,將兩者的乘積的大小作為標(biāo)簽更新最終依據(jù),選擇最高值的簇群標(biāo)簽作為目標(biāo)節(jié)點的新標(biāo)簽。

2.1 節(jié)點利用度計算

LPA算法存在不穩(wěn)定性的一個重要原因是由于其節(jié)點標(biāo)簽更新過程的隨機性,算法會根據(jù)不同的節(jié)點更新順序得到不同的結(jié)果。在一個學(xué)習(xí)單元有向圖中,單元節(jié)點的入度或出度越大,表明與這個學(xué)習(xí)單元相鄰的其他學(xué)習(xí)單元的數(shù)量越多,則這個學(xué)習(xí)單元在單元序列中被利用的次數(shù)越多,此單元對與其直接相連的單元的標(biāo)簽影響力越大。將這一概念定義為學(xué)習(xí)單元節(jié)點利用度,節(jié)點i的利用度Ui的計算方式為

(1)

利用度高的單元節(jié)點的標(biāo)簽信息被用于更新利用度低的單元節(jié)點標(biāo)簽。在標(biāo)簽更新過程中,節(jié)點初始化順序按照節(jié)點利用度升序進行。

2.2 節(jié)點間有向邊權(quán)值的計算

有向模塊度的先行研究表明由低出度高入度的節(jié)點指向低入度高出度的節(jié)點的邊對有向圖模塊化的貢獻更大。如存在具有低出度高入度的單元節(jié)點vi和高出度低入度的單元節(jié)點vj,同時存在學(xué)習(xí)順序為節(jié)點vi指向節(jié)點vj的邊ei→j,則節(jié)點vi和節(jié)點vj可能屬于同一個學(xué)習(xí)周期。為計算微學(xué)習(xí)單元的學(xué)習(xí)順序的權(quán)重,將邊ei→j的方向信息定義為邊ei→j的權(quán)重。當(dāng)邊的方向權(quán)重越大時,表明該學(xué)習(xí)順序的內(nèi)在相關(guān)程度越大,組成該順序的學(xué)習(xí)單元也更可能屬于同一個學(xué)習(xí)周期。節(jié)點i到節(jié)點j的有向邊權(quán)Wi→j計算方式為

(2)

但對于具有固定入度和出度的兩個節(jié)點在不同情況下由式(2)的計算結(jié)果相同。如圖1所示,單元節(jié)點v1和單元節(jié)點v2在兩種情況(情況1和情況2)下雖然具有相同的入度和出度,但在情況2下由于單元節(jié)點v3與v1和v2形成環(huán)狀結(jié)構(gòu),導(dǎo)致v1和v2屬于同一個學(xué)習(xí)周期的概率要比在情況1下要更高,式(2)無法反映這種現(xiàn)象。為了解決這個問題,本文定義在有向邊方向權(quán)重的基礎(chǔ)上提出一個節(jié)點相關(guān)性計算公式。

圖1 關(guān)于節(jié)點v1和v2的兩種局部圖結(jié)構(gòu)示例Fig.1 Examples of two local graph structuresfor nodes v1 and v2

用Γ(i)表示單元節(jié)點vi及其鄰居節(jié)點組成的集合,若存在Γ(i)={vj∈V|ei→j∈E,ej→i∈E}∪{vi},則任意兩個單元節(jié)點vi和vj的相關(guān)性σ(i,j)定義為

(3)

式(3)表明如果兩個單元節(jié)點的公共鄰域單元節(jié)點數(shù)量越多,則兩個學(xué)習(xí)單元的相關(guān)性越大,此時兩個學(xué)習(xí)單元屬于同一個學(xué)習(xí)周期的可能性越大。利用節(jié)點的相關(guān)性公式,提出一個基于節(jié)點相關(guān)性的有向邊權(quán)計算方式,即

(4)

式(4)考慮了單元節(jié)點的相關(guān)性對學(xué)習(xí)順序的影響,避免了將方向權(quán)重較大但相關(guān)性較低的單元節(jié)點劃分至同一學(xué)習(xí)周期的問題。

2.3 基于有向邊權(quán)值的標(biāo)簽更新

(5)

同時,為避免過傳播現(xiàn)象,本文提出一種基于標(biāo)簽權(quán)值的方法來限制微學(xué)習(xí)單元簇群的增長,即隨著一個微學(xué)習(xí)單元簇群規(guī)模的增大,該標(biāo)簽權(quán)值會逐漸變小,在選擇目標(biāo)節(jié)點的標(biāo)簽時會盡量不去選擇簇群規(guī)模太大的簇群標(biāo)簽,從而平衡簇群增長。標(biāo)簽為l的簇群的標(biāo)簽權(quán)值Lwl的計算公式為

(6)

式(6)中:Cl為標(biāo)簽為l的簇群。

將標(biāo)簽權(quán)值引入標(biāo)簽更新規(guī)則后,改進的標(biāo)簽更新規(guī)則的最終計算方式為

(7)

式(7)表明,隨著同一簇群內(nèi)節(jié)點數(shù)量的增長,此簇群的標(biāo)簽權(quán)值將減小,此時其標(biāo)簽傳播能力也隨之降低,防止形成巨型簇群。

2.4 算法描述

本文算法的偽代碼如算法1所示。

算法1 基于有向邊權(quán)值的標(biāo)簽傳播算法輸入 有向無權(quán)圖G=(V,E),最大迭代次數(shù)tmax輸出 簇群處理結(jié)果Com={C1,C2,…,Cn}1.在第一次迭代將每個節(jié)點劃分為一個簇群2.根據(jù)式(1),計算各節(jié)點的利用度,并將其升序排列得到節(jié)點更新順序Vk={vi|1≤i≤n}3.for t=0 to tmax do4.for each vj∈Vk do5.根據(jù)式(7),得到vj的新標(biāo)簽; end for6.P=True; //P用來判斷算法是否收斂7.for each vj∈Vk do8.if lj≠lnewj: //根據(jù)式(7),校驗標(biāo)簽9.P=False; //存在一個節(jié)點校驗失敗10.end for11.if t=tmaxP=True: //若達到最大迭代次數(shù)或已收斂,結(jié)束算法12.根據(jù)節(jié)點標(biāo)簽值將其劃分至對應(yīng)簇群C中13.end for

代碼1～2行對所有節(jié)點進行初始化并計算其利用度,進行升序排列。

代碼3～14行算法為迭代運算。其中:代碼4～6行根據(jù)式(7)對每個節(jié)點進行處理并賦予新標(biāo)簽。代碼7～11行對族群劃分后的有向圖進行收斂判斷。重復(fù)遍歷節(jié)點并根據(jù)式(7)計算新標(biāo)簽,若所有節(jié)點的舊標(biāo)簽與新標(biāo)簽相同,則判定為算法已收斂,否則算法未收斂。代碼12～13行判斷算法是否結(jié)束,若達到最大迭代次數(shù)或算法收斂,則將所有標(biāo)簽相同的節(jié)點劃分至同一簇群中,算法運行結(jié)束,否則算法進入下一次迭代。

3 實驗設(shè)計與分析

為了評價所提算法在有向圖聚類中的有效性,本節(jié)分別在微學(xué)習(xí)真實數(shù)據(jù)集和人工數(shù)據(jù)集上,將本文所提算法與6種有向圖聚類算法進行對比實驗,并對實驗結(jié)果進行分析。所選用的基準(zhǔn)有向圖聚類算法如下。

(1)Infomap:一種基于信息編碼的算法。該算法以圖中隨機游走的概率流代表真實系統(tǒng)中信息流,通過對概率流的描述進行壓縮來進行聚類。

(2)GEMSEC (graph embedding with self clustering)[25]:一種基于隨機游走的算法。該算法使用隨機游走來近似點互信息矩陣。該矩陣采用近似因式分解結(jié)合類似k-means的聚類代價進行分解。

(3)Leiden[26]:一種基于優(yōu)化的算法。通過最大化圖模塊度值來進行聚類。

(4)OSLOM (order statistics local optimization method)[27]:一種基于優(yōu)化的算法。通過對由劃分的簇與隨機生成的簇之間的差異得到的質(zhì)量函數(shù)進行局部優(yōu)化,找出得分較高的簇來以完成聚類。

(5)DLPA:一種LPA算法在有向圖上的擴展,僅僅針對有向圖修改了標(biāo)簽傳播規(guī)則,使算法能夠識別局部方向信息。

(6)LPA:經(jīng)典LPA算法,在實驗對比環(huán)節(jié)將有向圖簡單地去除方向信息轉(zhuǎn)化成無向圖來運行。

其中GEMSEC、DLPA和LPA三種算法因運行時存在隨機性,實驗結(jié)果將取10次運行后的平均值。

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

由于國內(nèi)鮮有教育數(shù)據(jù)挖掘領(lǐng)域的公開數(shù)據(jù)集,因此本次實驗使用的微學(xué)習(xí)真實數(shù)據(jù)集為英國開放大學(xué)(Open University, OU)的公開數(shù)據(jù)集OULAD[28](Open University learning analytics dataset)。

OU是全球最大的遠程教育大學(xué)之一,截至2017年,已有約170 000名學(xué)生注冊學(xué)習(xí)。OU提供數(shù)百個在線課程,課程所需的相關(guān)資料通過虛擬學(xué)習(xí)環(huán)境交付給學(xué)生,學(xué)生與學(xué)習(xí)資料的交互記錄均被記錄在數(shù)據(jù)庫中。OULAD是教育數(shù)據(jù)挖掘領(lǐng)域中最全面且最具有基準(zhǔn)價值的數(shù)據(jù)集之一,其中包含了7門在線課程的基本信息、注冊學(xué)習(xí)者的基本信息及其與大量學(xué)習(xí)資料的交互數(shù)據(jù),出于隱私保護OU已將相關(guān)數(shù)據(jù)均進行匿名化處理。目前,中外學(xué)者已在其研究領(lǐng)域中廣泛運用該數(shù)據(jù)集產(chǎn)生了大量學(xué)術(shù)論文。本節(jié)將取出其中部分課程及交互數(shù)據(jù)進行實驗。

人工數(shù)據(jù)集使用基于高斯隨機分區(qū)生成模型[29](Gaussian random partition generator)生成的隨機有向圖。

3.2 評價指標(biāo)

采用有向模塊度(directed modularity, DQ)、標(biāo)準(zhǔn)互信息(normalized mutual information, NMI)、調(diào)整蘭德系數(shù)(adjusted Rand index, ARI)來綜合評價有向圖聚類質(zhì)量。

DQ是目前最常用的一種有向圖聚類質(zhì)量評價指標(biāo),定義為有向圖中簇群內(nèi)部的總邊數(shù)所占比例與該圖在隨機連接的情況下相同簇群分配所形成的簇群內(nèi)部的總邊數(shù)所占比例的期望值的差。計算公式為

(8)

式(8)中:i和j為正整數(shù);A=[Aij]為有向圖的鄰接矩陣,若存在邊(i,j),則Aij=1,否則Aij=0;m為有向圖中邊的總數(shù);Ci和Cj分別是節(jié)點i和節(jié)點j所屬的簇群,如果i和j屬于同一個簇群,δ(Ci,Cj)=1,否則δ(Ci,Cj)=0。在通常情況下,DQ越高,其聚類質(zhì)量越高,在真實數(shù)據(jù)集中DQ取值一般為0.3～0.8。在極端情況下,若整個圖被劃分為一個簇群,DQ=0,若每個節(jié)點都被獨立劃分為一個簇群,DQ<0。

NMI和ARI通過衡量真實劃分和算法劃分結(jié)果的相似性來對聚類精度進行評價。設(shè)二維矩陣A={A1,A2,…,An}為真實劃分,B={B1,B2,…,Bm}為算到的聚類結(jié)果,則NMI和ARI的計算方式分別為

(9)

(10)

式中:N為圖中節(jié)點個數(shù);T=[Tij]為一個混淆矩陣,其元素Tij為A中屬于簇群i的節(jié)點同時也屬于B中簇群j的節(jié)點個數(shù),Ti·和T·j分別為Τ中第i行和第j列元素之和。

由式(9)和式(10)可以看出,NMI和ARI的值越大,表明有算法聚類據(jù)的真實劃分情況越接近,當(dāng)值為1時,A、B兩種劃分完全一致,值為0時,A、B兩種劃分完全獨立。

3.3 微學(xué)習(xí)真實數(shù)據(jù)集實驗及結(jié)果

本部分實驗使用OULAD中EEE、FFF和GGG共3門課程完成,其中EEE和FFF課程屬于STEM類課程,GGG為社會科學(xué)類課程。每個課程會在每個學(xué)習(xí)周期結(jié)束時安排有測驗,用于考核相應(yīng)學(xué)習(xí)階段的知識掌握情況,課程結(jié)束后會有一次期末考試評價學(xué)生的最終學(xué)習(xí)效果。本次實驗首先根據(jù)學(xué)習(xí)者的教育層次、年齡、是否重修、期末成績等級等指標(biāo)對學(xué)習(xí)者進行分組,認(rèn)為同一組學(xué)生具備相似的前置知識和學(xué)習(xí)方法,是相似學(xué)習(xí)者,不同分組的學(xué)生具有不同的個性化表現(xiàn),由于前置知識的不同導(dǎo)致所選擇的學(xué)習(xí)單元會有所不同。在學(xué)習(xí)過程中選擇的學(xué)習(xí)單元會大致相同。在對學(xué)習(xí)者分組時將動態(tài)控制指標(biāo)數(shù)量以保證每組學(xué)習(xí)者在具有較大的學(xué)習(xí)個性差異的同時其數(shù)量差距不會太大,以避免后續(xù)序列模式挖掘的結(jié)果缺乏代表性。

從學(xué)習(xí)課程開始到單元測驗為止為一個學(xué)習(xí)周期,到期末考試為止存在若干個學(xué)習(xí)周期。表1為3門課程的學(xué)習(xí)周期數(shù)量。

表1 3門課程的學(xué)習(xí)周期數(shù)量Table 1 Period count of 3 courses

表2為EEE課程中以良好成績通過期末考試、學(xué)歷層次在本科及以上、年齡屬于0～35歲且沒有重修過這門課程的一組學(xué)習(xí)者的部分學(xué)習(xí)序列。

表2 EEE課程一組學(xué)習(xí)者的學(xué)習(xí)序列Table 2 Unit sequences of a group of students in course EEE

在得到每組學(xué)生的學(xué)習(xí)序列后,首先對每一階段的學(xué)習(xí)單元進行統(tǒng)計,如果一個學(xué)習(xí)單元在某個學(xué)習(xí)周期中出現(xiàn)的次數(shù)最多,就將此單元賦予對應(yīng)學(xué)習(xí)周期的標(biāo)簽,即此單元應(yīng)歸屬于這個學(xué)習(xí)周期的學(xué)習(xí)單元。

其次對每組學(xué)習(xí)者的不同學(xué)習(xí)階段的單元交互數(shù)據(jù)使用VMSP算法進行最大序列模式挖掘,設(shè)置參數(shù)最小支持度為0.8,最大模式長度為8,代表將至少在80%的序列中挖掘序列模式,同時所挖掘的序列模式長度最大為8,將得到的結(jié)果進行去重處理。表3為EEE課程中同組學(xué)習(xí)者每個學(xué)習(xí)周期得到的序列模式的部分?jǐn)?shù)據(jù)。

表3 EEE課程一組學(xué)習(xí)者的序列模式Table 3 Sequence pattern of a group of students in course EEE

將得到的每個序列模式按照學(xué)習(xí)單元的先后順序構(gòu)建為有向圖,作為本文算法的輸入數(shù)據(jù)。圖2為EEE課程同組學(xué)生的學(xué)習(xí)行為圖,展示了這組學(xué)生的學(xué)習(xí)序列中頻繁出現(xiàn)的學(xué)習(xí)模式。其中,每個節(jié)點代表一個學(xué)習(xí)單元,每條有向邊代表一組單元學(xué)習(xí)順序,分布相對緊湊的學(xué)習(xí)單元理應(yīng)歸屬于同一個學(xué)習(xí)周期。

圖2 EEE課程一組學(xué)習(xí)者的學(xué)習(xí)行為圖Fig.2 Behavior graph of a group of students in course EEE

本節(jié)取EEE、FFF和GGG共3門課程里的任意1～2組學(xué)習(xí)者,驗證算法的有效性。數(shù)據(jù)集分別為EEE:課程EEE中以良好成績通過期末考試、學(xué)歷層次在本科及以上、年齡屬于0～35歲且沒有重修過這門課程的學(xué)習(xí)者;FFF:課程FFF中以優(yōu)秀成績通過期末考試、年齡屬于0～35歲且沒有重修過這門課程的學(xué)習(xí)者;GGG:課程GGG中以優(yōu)秀成績通過期末考試、年齡屬于0～35歲且沒有重修過這門課程的學(xué)習(xí)者。表4為所選取的5組數(shù)據(jù)集的基本信息。

表4 微學(xué)習(xí)數(shù)據(jù)集基本信息Table 4 Basic information of micro-learning datasets

實驗結(jié)果如表5所示?？梢钥吹?本文所提出的LPADEW算法在3組微學(xué)習(xí)真實數(shù)據(jù)集上的聚類結(jié)果優(yōu)于大多數(shù)對比算法,整體性能略強于Leiden算法,表現(xiàn)較好。

表5 微學(xué)習(xí)數(shù)據(jù)集實驗結(jié)果對比Table 5 Comparison of experiment results on micro-learning datasets

3.4 人工數(shù)據(jù)集實驗及結(jié)果

人工數(shù)據(jù)集由高斯隨機分區(qū)生成模型生成。使用該模型生成的隨機有向圖具有n個節(jié)點,每個簇群的規(guī)模由平均規(guī)模s和形狀參數(shù)v決定,簇群規(guī)模符合以s為期望、s/v為方差的高斯分布。簇內(nèi)的節(jié)點以概率p_in相連,簇間的節(jié)點以概率p_out相連。

本文研究將隨機有向圖的規(guī)模控制到和微學(xué)習(xí)真實數(shù)據(jù)集相似的規(guī)模。參數(shù)設(shè)置為節(jié)點數(shù)n=60,平均簇群規(guī)模s=12,形狀參數(shù)v=6,簇內(nèi)連接概率p_in=0.5,簇間連接概率p_out為0.01～0.1。每個節(jié)點代表一個學(xué)習(xí)單元,每條有向邊代表一種學(xué)習(xí)單元順序。用ARI和DQ評價聚類質(zhì)量,實驗結(jié)果如圖3和圖4所示。

圖3 隨機有向圖上的ARI值比較Fig.3 Comparisons of ARI on randomgraph

圖4 隨機有向圖上的DQ值比較Fig.4 Comparisons of DQ on randomgraph

由圖3和圖4可以看出,當(dāng)p_out<0.08時,LPADEW算法相比其他6種算法在聚類精度上取得了更好的結(jié)果,但作為代價則降低了DQ值,Leiden算法由于最大化目標(biāo)函數(shù)導(dǎo)致其在DQ值上表現(xiàn)較好,但丟失了精度;當(dāng)p_out>0.08時,由于各簇群之間的連接概率變大,簇結(jié)構(gòu)開始變得模糊,此時各個算法的性能均開始下降,其中LPA算法因無法利用有向圖的方向信息,導(dǎo)致表現(xiàn)較差,LPADEW算法的整體性能仍優(yōu)于大多數(shù)對比算法。

4 結(jié)論

針對按學(xué)習(xí)周期對相似學(xué)習(xí)者的成功學(xué)習(xí)履歷中的微學(xué)習(xí)單元及學(xué)習(xí)順序的聚類問題,現(xiàn)提出一種基于有向邊權(quán)值的標(biāo)簽傳播算法LPADEW。該算法首先根據(jù)單元節(jié)點利用度并升序排列以確定標(biāo)簽的更新順序。其次計算有向邊權(quán)累加值,并選取結(jié)果最大的標(biāo)簽更新目標(biāo)節(jié)點的標(biāo)簽,同時引入標(biāo)簽權(quán)重控制過傳播問題最后將具有相同標(biāo)簽的單元節(jié)點聚類至同一學(xué)習(xí)周期。LPADEW算法可避免標(biāo)簽選擇過程的隨機性,并可提高學(xué)習(xí)周期劃分的質(zhì)量。與Infomap、GEMSEC、Leiden、OSLOM、DLPA和LPA等算法的對比實驗表明,LPADEW算法在NMI、ARI和DQ等指標(biāo)上均有較好的表現(xiàn)。今后,將嘗試調(diào)整邊權(quán)重和實現(xiàn)迭代次數(shù)的非監(jiān)督處理,以提高算法的性能和精度。