E-learning平臺(tái)中的課程相似性搜索研究

張明西， 王金華， 王曉紅， 李肖赫

(1.上海理工大學(xué) 出版印刷與藝術(shù)設(shè)計(jì)學(xué)院 上海 200093； 2. 復(fù)旦大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院 上海 201203；3.哈爾濱工業(yè)大學(xué)(威海) 計(jì)算機(jī)學(xué)院 山東 威海 264209)

E-learning平臺(tái)中的課程相似性搜索研究

張明西1， 王金華2， 王曉紅1， 李肖赫3

(1.上海理工大學(xué) 出版印刷與藝術(shù)設(shè)計(jì)學(xué)院 上海 200093； 2. 復(fù)旦大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院 上海 201203；3.哈爾濱工業(yè)大學(xué)(威海) 計(jì)算機(jī)學(xué)院 山東 威海 264209)

針對(duì)E-learning平臺(tái)中的課程相似性搜索問(wèn)題，在SimRank模型基礎(chǔ)上提出一種高效的課程相似性搜索方法(CourseSim)，依據(jù)學(xué)生和課程之間的選修關(guān)系查找相似的課程.結(jié)合SimRank矩陣形式及其快速收斂特點(diǎn)，構(gòu)建二次迭代模型，并將相似性搜索分為兩個(gè)階段：第一階段離線計(jì)算學(xué)生相似性，結(jié)合學(xué)習(xí)興趣除去關(guān)系強(qiáng)度較弱的鏈接，以減少非必要的計(jì)算操作，并通過(guò)避免多余的零值累加減少計(jì)算開銷；第二階段進(jìn)行在線查詢處理，在學(xué)生相似性基礎(chǔ)上計(jì)算課程相似性，通過(guò)累加操作優(yōu)化查詢處理.實(shí)驗(yàn)結(jié)果表明，CourseSim方法能夠降低超過(guò)99.98%的時(shí)間開銷和59.58%存儲(chǔ)開銷，達(dá)到99.80%以上的NDCG.

E-learning； 選修關(guān)系； 相似性搜索； SimRank； CourseSim

0 引言

E-Leaning(On-line Learning)是一種基于互聯(lián)網(wǎng)的在線學(xué)習(xí)平臺(tái),當(dāng)前E-Learning站點(diǎn)有很多，比如edX、MOOC、coursegraph等，這類平臺(tái)為學(xué)習(xí)者提供了大量有價(jià)值的教學(xué)資源.但是教學(xué)資源的多樣化和復(fù)雜化使學(xué)生面臨著信息選擇的困難.因此，有必要設(shè)計(jì)和開發(fā)一種有效的數(shù)據(jù)管理算法和應(yīng)用，用于分析數(shù)據(jù)之間存在的潛在聯(lián)系，并從大規(guī)模數(shù)據(jù)中發(fā)現(xiàn)有價(jià)值的信息.

當(dāng)前圍繞數(shù)據(jù)管理方面的研究有很多，比如聚類分析、鏈路預(yù)測(cè)及相似性搜索等. 文獻(xiàn)[1]在2002年提出SimRank模型，將實(shí)體之間相似性定義為隨機(jī)游走的期望相遇概率，以迭代形式計(jì)算實(shí)體之間的相似性.文獻(xiàn)[2]考慮指入鏈接和指出鏈接計(jì)算實(shí)體之間的相似性，解決了相似性計(jì)算的“l(fā)imited information”問(wèn)題.文獻(xiàn)[3]整合實(shí)體之間的任意相遇情況，解決了相似性計(jì)算的“zero similarity”問(wèn)題.文獻(xiàn)[4]通過(guò)忽略鏈接方向來(lái)發(fā)現(xiàn)實(shí)體之間任意方向的相遇情況，使相似性計(jì)算更加全面.文獻(xiàn)[5]采用統(tǒng)一關(guān)系矩陣表示異構(gòu)網(wǎng)絡(luò)中的鏈接關(guān)系，采用迭代計(jì)算方式克服矩陣稀疏情況.文獻(xiàn)[6]通過(guò)指定不同的元路徑實(shí)現(xiàn)異構(gòu)網(wǎng)絡(luò)中的相似性計(jì)算，基于路徑數(shù)度量實(shí)體之間的相似性.文獻(xiàn)[7]將實(shí)體相似性轉(zhuǎn)換為所關(guān)聯(lián)的屬性相似性，適用于X-Star網(wǎng)絡(luò)的相似性計(jì)算.文獻(xiàn)[8]能夠計(jì)算不同類型實(shí)體之間的相關(guān)性，允許用戶提供任意類型的實(shí)體進(jìn)行查詢.文獻(xiàn)[9]結(jié)合維基百科中的文獻(xiàn)網(wǎng)絡(luò)和分類樹來(lái)計(jì)算詞語(yǔ)間的語(yǔ)義關(guān)聯(lián)度.上述方法以迭代方式計(jì)算相似性，在相似性矩陣維護(hù)過(guò)程中需要很高的時(shí)間和存儲(chǔ)開銷.文獻(xiàn)[10]表明，與基于文本的相似性搜索方法相比，這種基于鏈接關(guān)系的相似性搜索的返回結(jié)果更加符合人們的直觀判斷.

近年來(lái)研究者們圍繞相似性搜索效率優(yōu)化方面進(jìn)行了大量研究[11-16].文獻(xiàn)[11]采用關(guān)鍵節(jié)點(diǎn)對(duì)、局部和過(guò)濾閾值相似性三種方法來(lái)優(yōu)化SimRank計(jì)算, 文獻(xiàn)[12]通過(guò)避免局部偏和重復(fù)計(jì)算進(jìn)一步優(yōu)化了計(jì)算過(guò)程.文獻(xiàn)[13]提出P-Rank異步積累更新算法，降低了處理器的等待時(shí)間.但這幾種方法都需要維護(hù)大規(guī)模的相似性矩陣.文獻(xiàn)[14]通過(guò)設(shè)計(jì)“seed germination”模型來(lái)優(yōu)化“partial sums”的離線計(jì)算，依據(jù)“partial sums”的離線計(jì)算結(jié)果來(lái)提高在線相似性計(jì)算效率.文獻(xiàn)[15]將圖上的相似性搜索問(wèn)題轉(zhuǎn)化為在乘積圖上尋找權(quán)威節(jié)點(diǎn)的問(wèn)題.這兩種方法降低了離線計(jì)算開銷，但是會(huì)增加在線計(jì)算開銷，降低查詢處理效率.

本文在SimRank模型基礎(chǔ)上提出一種高效的課程相似性搜索方法(CourseSim).主要貢獻(xiàn)包括：1) 基于SimRank快速收斂特點(diǎn)，提出二次迭代模型，以降低相似性計(jì)算開銷；2) 結(jié)合選修關(guān)系網(wǎng)絡(luò)特征提出一種學(xué)習(xí)興趣度量方法，用于去除弱鏈接關(guān)系，減少非必要的計(jì)算開銷；3) 采用相似性累加計(jì)算的方法優(yōu)化在線查詢處理，以降低在線查詢處理的時(shí)間開銷；4) 在真實(shí)數(shù)據(jù)集上開展大量實(shí)驗(yàn)，在效率和效果兩個(gè)方面進(jìn)行了對(duì)比分析.

1 預(yù)備知識(shí)

1.1 選修關(guān)系網(wǎng)絡(luò)

E-Learning平臺(tái)中的學(xué)生、課程以及兩者之間的選修關(guān)系就構(gòu)成了選修關(guān)系網(wǎng)絡(luò)，記為G=(V,E).其中：V=VS∪VC，這里的VS和VC分別表示學(xué)生和課程類型的實(shí)體集合；E表示選修關(guān)系集合，有序?qū)?s,c)∈E表示學(xué)生s∈VS和課程c∈VC之間的選修關(guān)系.

1.2SimRank模型

SimRank以遞歸的方式定義相似性，實(shí)體a,b∈V之間的相似性可定義為

SimRank以迭代方式計(jì)算相似性，實(shí)體a,b在第t次迭代的相似性記為Rt(a,b).當(dāng)t=0時(shí)，如果a=b，那么R0(a,b)=1，否則R0(a,b)=0. 當(dāng)t=1,2,…時(shí)，如果a=b，那么Rt(a,b)=1，否則

(b)).

SimRank計(jì)算所有網(wǎng)絡(luò)實(shí)體之間第t次迭代相似性的時(shí)間復(fù)雜度為O(td2n2)，空間復(fù)雜度為O(n2)，這里的n為網(wǎng)絡(luò)中的實(shí)體數(shù)量，d為網(wǎng)絡(luò)節(jié)點(diǎn)的平均度.

2 優(yōu)化算法

2.1 選修關(guān)系網(wǎng)絡(luò)的弱鏈接刪除策略

2.2SimRank計(jì)算公式的矩陣形式

SimRank在第t次迭代的相似性矩陣記為Rt.當(dāng)t=0時(shí)，R0=In；當(dāng)t=1,2,…時(shí)，Rt=(CPRt-1P′)offdiag+In，其中：P表示實(shí)體之間的反向轉(zhuǎn)移概率矩陣，矩陣元素為游走者沿著指入鏈接方向進(jìn)行隨機(jī)游走時(shí)的轉(zhuǎn)移概率；P′表示P的轉(zhuǎn)置；Moffdiag表示將矩陣M中的對(duì)角元素全部設(shè)置為零之后得到的矩陣；In為n×n的單位對(duì)角矩陣.基于矩陣運(yùn)算，SimRank時(shí)間復(fù)雜度降低為O(tdn2)，空間復(fù)雜度不變.

2.3CourseSim計(jì)算模型

2.4CourseSim計(jì)算算法

為了進(jìn)一步降低計(jì)算開銷，相似性搜索過(guò)程分為離線和在線兩個(gè)階段.離線階段依據(jù)選修關(guān)系網(wǎng)絡(luò)計(jì)算學(xué)生相似性.在線階段處理查詢請(qǐng)求，基于學(xué)生相似性計(jì)算課程相似性.

算法1CourseSim的離線計(jì)算算法．

輸入：選修關(guān)系網(wǎng)絡(luò)G；

輸出：學(xué)生相似性矩陣RS．

foreachs∈VS

RS(s,s)←1;

endfor

endfor

endfor

2.4.2 在線查詢處理算法 算法2表示CourseSim在線查詢處理的基本算法.給定查詢Q，首先計(jì)算Q與所有候選課程之間的相似性，最后返回top-k個(gè)最相似的課程.算法中的DCR(Q,*)用于存儲(chǔ)CPCS(Q,*)RS的計(jì)算結(jié)果.算法平均時(shí)間開銷為O(nC(dC+nD))，其中nD表示向量DCR(Q,*)的平均非零元素?cái)?shù).

算法2CourseSim-baseline．

輸入：選修關(guān)系網(wǎng)絡(luò)G，矩陣RS，查詢Q，參數(shù)k;

輸出：top-k個(gè)最相似的課程．

RC(Q,Q)←1;

foreachc∈VCQ

DCR(Q,*)←CPCS(Q,*)RS

endfor

選擇top-k個(gè)最相似的課程，排序并輸出.

算法3CourseSim-pruning．

輸入：選修關(guān)系網(wǎng)絡(luò)G，矩陣RS，查詢Q，參數(shù)k;

輸出：top-k個(gè)最相似的課程．

RC(Q,Q)←1;

RC(Q,c)←RC(Q,c)+CPCS(Q,s)RS(s,s′)PCS′(s′,c);

endfor

endfor

endfor

選擇top-k個(gè)最相似的課程，排序并輸出.

3 實(shí)驗(yàn)與結(jié)果

3.1 實(shí)驗(yàn)設(shè)置

在機(jī)器配置方面，CPU為Intel(R) Core(TM) i5-4200，頻率為2.30 GHz，內(nèi)存為12.0 GB.開發(fā)環(huán)境為VS C++2010.實(shí)驗(yàn)在MOOC學(xué)院(http://mooc.guokr.com/)數(shù)據(jù)集上進(jìn)行.采用網(wǎng)絡(luò)爬蟲抓取課程及學(xué)生信息，選擇12 018位學(xué)生、2 195門課程、23 252條選修關(guān)系構(gòu)建選修關(guān)系網(wǎng)絡(luò).實(shí)驗(yàn)對(duì)比方法包括SimRank[1]和P-Rank[2]，采用文獻(xiàn)[12]對(duì)兩者計(jì)算過(guò)程進(jìn)行優(yōu)化.阻尼系數(shù)C設(shè)置為0.8，參數(shù)h設(shè)置為0.6.在效率評(píng)估方面，主要對(duì)比和分析離線計(jì)算和在線查詢處理兩個(gè)方面的計(jì)算開銷.在效果評(píng)估方面，采用NDCG[16]評(píng)估相似性計(jì)算效果，依據(jù)返回結(jié)果中課程的排序及其對(duì)應(yīng)相似性來(lái)計(jì)算第k個(gè)位置的NDCG值，效果評(píng)估的基準(zhǔn)為SimRank相似性的精確值.

3.2 性能測(cè)試

表1表示離線計(jì)算相似性的時(shí)間開銷.結(jié)果顯示，CoureSim的時(shí)間開銷低于SimRank和P-Rank的 0.02%，這是因?yàn)镃oureSim不需多次迭代，而且計(jì)算過(guò)程中沒(méi)有涉及到零元素相乘的操作.表2表示離線計(jì)算相似性的存儲(chǔ)開銷，這里的符號(hào)“M”是指“1 024*1 024”.結(jié)果顯示，CourseSim相似性矩陣為SimRank和P-Rank在迭代次數(shù)為2時(shí)的40.42%，為在迭代次數(shù)為10時(shí)的22.63%.SimRank和P-Rank存儲(chǔ)開銷相同，這是因?yàn)檫x修關(guān)系是雙向的，從而使兩者的計(jì)算結(jié)果相同.

圖1表示CourseSim-baseline和CourseSim-pruning的查詢處理時(shí)間.結(jié)果顯示，當(dāng)k增加時(shí)，查詢時(shí)間的增加趨勢(shì)并不明顯，這是因?yàn)榕判虿僮魉璧臅r(shí)間開銷遠(yuǎn)低于相似性計(jì)算過(guò)程.CourseSim-baseline的查詢時(shí)間約為890ms，約為CourseSim-baseline查詢時(shí)間的6.01%.結(jié)果表明，本文提出的優(yōu)化方法是可行的，能夠減少在線查詢的時(shí)間開銷.

表1 離線計(jì)算相似性的時(shí)間開銷

表2 相似性矩陣規(guī)模

圖2表示k取不同值時(shí)對(duì)應(yīng)的NDCG，其中SimRank和P-Rank的迭代次數(shù)t=10.結(jié)果顯示，SimRank和P-Rank的NDCG相同，表明兩者在選修關(guān)系網(wǎng)絡(luò)中具有相同的查詢效果.當(dāng)k發(fā)生變化時(shí)，SimRank值和P-Rank的NDCG值始終為1，這是因?yàn)榻?jīng)過(guò)10次迭代計(jì)算結(jié)果已經(jīng)趨于收斂狀態(tài).CourseSim的NDCG值小于1，但是已經(jīng)達(dá)到超過(guò)99.80%的NDCG值.當(dāng)k從10到30增加時(shí)，CourseSim的NDCG值逐漸減小，當(dāng)k取值從30增加到50時(shí)，又出現(xiàn)增加趨勢(shì)，這是因?yàn)榉祷亟Y(jié)果中排序第1的課程是查詢本身，對(duì)應(yīng)NDCG值為1，從而影響NDGG值的總體增加的變化趨勢(shì).

表3表示不同參數(shù)h對(duì)應(yīng)的CourseSim的性能.在線查詢階段，僅記錄返回top-50個(gè)課程時(shí)對(duì)應(yīng)的查詢時(shí)間和NDC值G，而且僅記錄CourseSim-pruning的時(shí)間開銷.分析可知，h值設(shè)置越低，離線計(jì)算時(shí)間及存儲(chǔ)開銷、在線查詢時(shí)間也會(huì)越低.在效果測(cè)試方面，NDCG值隨著參數(shù)h的降低而減小，這表明相似性計(jì)算結(jié)果和SimRank理論值之間的誤差隨著h增加而呈現(xiàn)增加的趨勢(shì).

圖1 在線查詢處理的時(shí)間開銷Fig.1 Time cost of on-line query processing

圖2 k取不同值時(shí)對(duì)應(yīng)的NDCGFig.2 NDCG value at different k

表3 參數(shù)h不同取值對(duì)應(yīng)的CourseSim性能

4 總結(jié)

本文提出一種E-Learning平臺(tái)中的課程相似性搜索算法，用于從大規(guī)模的教學(xué)資源中查找相似的課程.結(jié)合選修關(guān)系網(wǎng)絡(luò)特征和SimRank快速收斂特點(diǎn)，對(duì)離線計(jì)算和在線查詢處理兩個(gè)階段進(jìn)行了優(yōu)化.與現(xiàn)有方法相比，相似性計(jì)算過(guò)程不需多次迭代，顯著降低了計(jì)算開銷，返回結(jié)果的精確度損失低.未來(lái)研究工作將圍繞個(gè)性化課程推薦展開，通過(guò)整合選修關(guān)系、用戶評(píng)論等多方面的信息，結(jié)合聚類分析、社群挖掘等方法[17-18]研究課程推薦問(wèn)題.

[1] JEH G, WIDOM J. Simrank: a measure of structural-context similarity[C]//Proceedings of the Eighth ACM SIGKDD International Conferenceon Knowledge Discovery and Data Mining (SIGKDD2002). Edmonton,Alberta, 2002: 538-543.

[2] ZHAO P, HAN J, SUN Y. P-Rank: a comprehensive structural similarity measure over information networks[C]//Proceedings of the 18th ACM Conference on Information and Knowledge Management(CIKM 2009). Hong Kong, 2009: 553-62.

[3] YU W, LIN X,ZHANG W, et al. More is simpler: effectively and efficiently assessing node-pair similarities based on hyperlinks[J]. Proceedings of the vldb endowment, 2014, 7(1): 13-24.

[4] YOON S, KIM S, PARK S. C-Rank: a link-based similarity measure for scientific literature databases[J]. Information sciences, 2016, 326(1): 25-40.

[5] XI W, FOX E A, FAN W, et al. Simfusion: measuring similarity using unified relationship matrix[C]//Proceedings of the 28th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR 2005). Salvador,Brazil, 2005: 130-137.

[6] SUN Y, HAN J, YAN X, et al. PathSim: meta path-based top-ksimilarity search in heterogeneous information networks[J]. Proceedings of the vldb endowment, 2011, 4(11): 992-1003.

[7] ZHANG M, HU H, HE Z, et al. top-ksimilarity search in heterogeneous information networks with X-Star network schema[J]. Expert systems with applications, 2015, 42(2): 699-712.

[8] SHI C, KONG X, HUANG Y, et al. HeteSim: a general framework for relevance measure in heterogeneous networks[J]. IEEE transactions on knowledge & data engineering, 2014, 26(10): 2479-2492.

[9] 孫琛琛, 申德榮, 單菁, 等. WSR:一種基于維基百科結(jié)構(gòu)信息的語(yǔ)義關(guān)聯(lián)度計(jì)算算法[J]. 計(jì)算機(jī)學(xué)報(bào), 2012, 35(11): 2362-2370.

[10]MAGUITMAN A G, MENCZER F, ERDINC F, et al. Algorithmic computation and approximation of semantic similarity[J]. World wide web, 2006, 9(4):431-456.

[11]LIZORKIN D, VELIKHOV P, GRINEV M, et al. Accuracy estimate and optimization techniques for SimRank computation[J]. The VLDB journal, 2010, 19(1): 45-66.

[12]YU W, LIN X, ZHANG W. Towards efficient SimRank computation on large networks[C]//IEEE 29th International Conference on Data Engineering (ICDE 2013). Brisbane, 2013: 601-612.

[13] 王旭叢, 李翠平, 陳紅. 大數(shù)據(jù)下基于異步累積更新的高效P-Rank計(jì)算方法[J]. 軟件學(xué)報(bào), 2014, 25(9): 2136-2148.

[14]KUSUMOTO M, MAEHARA T, KAWARABAYASHI K. Scalable similarity search for Simank[C]// International Conference on Management of Data (SIGMOD 2014),Snowbird,UT, 2014: 325-336.

[15]LEE P, LAKSHMANAN V S L, YU J X. On top-kstructural similarity search[C]//IEEE 28th International Conference on Data Engineering (ICDE 2012). Washington, 2012: 774-785.

[16]RVELIN K, KEK,INEN J. Cumulated gain-based evaluation of IR techniques[J]. Acm transactions on information systems, 2002, 20(4): 422-446.

[17]李欣雨, 袁方, 劉宇, 等. 面向中文新聞話題檢測(cè)的多向量文本聚類方法[J]. 鄭州大學(xué)學(xué)報(bào)(理學(xué)版), 2016, 48(2): 47-52.

[18]許長(zhǎng)清, 趙華東, 宋曉輝.基于大數(shù)據(jù)的電力用戶群體識(shí)別與分析方法研究[J]. 鄭州大學(xué)學(xué)報(bào)(理學(xué)版), 2016, 48(3): 113-117.

(責(zé)任編輯：方惠敏)

On Course Similarity Search in E-learning Platform

ZHANG Mingxi1, WANG Jinhua2, WANG Xiaohong1, LI Xiaohe3

(1.CollegeofCommunicationandArtDesign,UniversityofShanghaiforScienceandTechnology,Shanghai200093,China; 2.SchoolofComputerScience,FudanUniversity,Shanghai201203,China; 3.CollegeofComputerScienceandTechnology,HarbinInstituteofTechnology,Weihai264209,China)

An efficient course similarity search approach based on SimRank was proposed for finding similar courses from E-Learning platform. The similarities between courses were computed by the course-taking relationship network. Based on the matrix form of SimRank and its rapid convergence characteristics, the iteration number was limited into two, and the similarity search process was divided into two stages: off-line stage and on-line stage. In the off-line stage, the similarities between students were computed. The computation cost was reduced by pruning the lower informative links and skipping the operations on zero values. In the on-line stage, the query request was processed. The similarities between query and candidate courses were computed based on the similarities between students, and on-line query processing was speeded up by accumulation operations. Extensive experiments demonstrated that CourseSim had more than 99.98% reduction in the time cost and 59.58% reduction in the space cost, and achieved more than 99.80% NDCG.

E-learning； course-taking relationship； similarity search； SimRank； CourseSim

2017-03-04

上海市自然科學(xué)基金項(xiàng)目(16ZR14228)；上海理工大學(xué)國(guó)家級(jí)項(xiàng)目培育基金(16HJPY-QN04)；國(guó)家新聞出版廣電總局新聞出版業(yè)科技與標(biāo)準(zhǔn)重點(diǎn)實(shí)驗(yàn)室“柔軟印刷綠色制版與標(biāo)準(zhǔn)化實(shí)驗(yàn)室”建設(shè)項(xiàng)目．

張明西(1985—)，男，安徽亳州人，講師，主要從事社會(huì)網(wǎng)絡(luò)分析、信息檢索、新媒體數(shù)據(jù)管理方面的研究，E-mail: mingxizhang10@fudan.edu.cn．

TP391

A

1671-6841(2017)03-0039-06

10.13705/j.issn.1671-6841.2017031