E-learning平臺中的課程相似性搜索研究

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

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

E-learning平臺中的課程相似性搜索研究

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

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

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

E-learning； 選修關系； 相似性搜索； SimRank； CourseSim

0 引言

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

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

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

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

1 預備知識

1.1 選修關系網(wǎng)絡

E-Learning平臺中的學生、課程以及兩者之間的選修關系就構成了選修關系網(wǎng)絡，記為G=(V,E).其中：V=VS∪VC，這里的VS和VC分別表示學生和課程類型的實體集合；E表示選修關系集合，有序對(s,c)∈E表示學生s∈VS和課程c∈VC之間的選修關系.

1.2SimRank模型

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

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

(b)).

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

2 優(yōu)化算法

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

2.2SimRank計算公式的矩陣形式

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

2.3CourseSim計算模型

2.4CourseSim計算算法

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

算法1CourseSim的離線計算算法．

輸入：選修關系網(wǎng)絡G；

輸出：學生相似性矩陣RS．

foreachs∈VS

RS(s,s)←1;

endfor

endfor

endfor

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

算法2CourseSim-baseline．

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

輸出：top-k個最相似的課程．

RC(Q,Q)←1;

foreachc∈VCQ

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

endfor

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

算法3CourseSim-pruning．

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

輸出：top-k個最相似的課程．

RC(Q,Q)←1;

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

endfor

endfor

endfor

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

3 實驗與結果

3.1 實驗設置

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

3.2 性能測試

表1表示離線計算相似性的時間開銷.結果顯示，CoureSim的時間開銷低于SimRank和P-Rank的 0.02%，這是因為CoureSim不需多次迭代，而且計算過程中沒有涉及到零元素相乘的操作.表2表示離線計算相似性的存儲開銷，這里的符號“M”是指“1 024*1 024”.結果顯示，CourseSim相似性矩陣為SimRank和P-Rank在迭代次數(shù)為2時的40.42%，為在迭代次數(shù)為10時的22.63%.SimRank和P-Rank存儲開銷相同，這是因為選修關系是雙向的，從而使兩者的計算結果相同.

圖1表示CourseSim-baseline和CourseSim-pruning的查詢處理時間.結果顯示，當k增加時，查詢時間的增加趨勢并不明顯，這是因為排序操作所需的時間開銷遠低于相似性計算過程.CourseSim-baseline的查詢時間約為890ms，約為CourseSim-baseline查詢時間的6.01%.結果表明，本文提出的優(yōu)化方法是可行的，能夠減少在線查詢的時間開銷.

表1 離線計算相似性的時間開銷

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

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

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

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

圖2 k取不同值時對應的NDCGFig.2 NDCG value at different k

表3 參數(shù)h不同取值對應的CourseSim性能

4 總結

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

[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:一種基于維基百科結構信息的語義關聯(lián)度計算算法[J]. 計算機學報, 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]. 軟件學報, 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]李欣雨, 袁方, 劉宇, 等. 面向中文新聞話題檢測的多向量文本聚類方法[J]. 鄭州大學學報(理學版), 2016, 48(2): 47-52.

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

(責任編輯：方惠敏)

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

上海市自然科學基金項目(16ZR14228)；上海理工大學國家級項目培育基金(16HJPY-QN04)；國家新聞出版廣電總局新聞出版業(yè)科技與標準重點實驗室“柔軟印刷綠色制版與標準化實驗室”建設項目．

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

TP391

A

1671-6841(2017)03-0039-06

10.13705/j.issn.1671-6841.2017031