基于Online Judge 進行程序設計類課程實踐的混合推薦

肖春蕓，賀樑，竇亮，楊靜

（華東師范大學計算機科學與技術學院，上海200062）

0 引言

近年來，教育的個性化需求越來越受到教育工作者的重視。2018 年4 月，教育部印發的《教育信息化2.0 行動計劃》中提出要“探索在信息化條件下實現差異化教學、個性化學習、精細化管理、智能化服務的典型途徑”[1]。在計算機專業教學中，對使用信息化工具有著得天獨厚的優勢，Online Judge（簡稱OJ，在線判題）平臺是其中的典型。OJ 平臺最初用于ACM 國際大學生程序設計競賽中的自動判題和排名，現已廣泛應用于世界各地高校學生的程序設計實踐、參賽隊員的訓練和選拔、程序設計競賽以及各種編程語言、數據結構和算法等課程的作業自動提交判斷中。依托OJ平臺進行計算機編程實踐的優勢十分明顯，一方面，平臺判題客觀，反饋及時；另一方面，對學生提交程序的過程記錄全面，每個學生的提交記錄、提交次數、測試數據通過的詳細情況都在平臺中有客觀記錄。

在傳統編程教學中，OJ 平臺的使用方式一般包括：

（1）教師在OJ 平臺上出題，布置編程作業，設定提交期限；利用學生提交程序的通過情況了解教學生對知識點的掌握情況；

（2）組織在線測試，及時客觀考查學生的學習效果等。

在此基礎上，教師可以給出題目難度分層，建議學生根據自身情況選擇不同難度的題目來練習。題目難度一般由教師從對教學內容的理解出發、基于經驗進行估算。理想情況下，學生根據由簡單到復雜的學習路徑完成實踐作業題，這樣的學習路徑有助于循序漸進掌握課程內容并提高編程能力。但在實際教學中，經常發生由于學生間的差異較大導致整體學習效果不佳的情形。例如：部分學生完成實踐作業題花費時間多，問題積累后無法跟上教學進度；而少量學生（特別是參加過程序競賽訓練的學生）完成速度快，認為實踐作業題缺乏挑戰和含金量；部分學生在已學習過的前導課程中有知識點缺漏，很難完成教師給定的任務；另外，還出現一些題目的某些測試點難度大，學生提交反復受挫，降低了學習的積極性。

在某學期的《數據結構》課程中，筆者對開課4 周后OJ 平臺上的數據結構課程實踐作業題的完成情況進行了分析，發現進度很不均衡，一些典型實例見表1。

從表1 的實例分析看出，雖然教師通過定期布置實踐作業題的方式給出了在OJ 平臺中的編程練習的學習路徑，但學生間的個體差異不容忽視，題目難度的差異也不容忽視。在上例的分析中發現，題集中的第28 題，有一位學生提交了89 次后才通過，主要原因是該題的測試數據量非常大，對算法要求較高。如果學生們在這道題目上反復提交而不能通過，會在時間花費及學習興趣方面都受到影響。因此，需要給出更個性化和智能化的學習路徑，才能有效激發學生的學習興趣，減少因反復提交失敗受挫而放棄的情況發生。

表1 某學期數據結構課程中學生OJ 實踐作業題情況分析

因此，我們在程序設計類教學中提出了利用混合推薦的思想，結合以下幾個維度為學生進行個性化學習路徑推薦的方法：①教師給出的學習路徑；②同類學生的學習路徑協同推薦；③結合學生上下文信息（做題習慣、時間段、個性等）給出的推薦。在進行個性化推薦時，給出推薦理由，根據學生對推薦理由的認可度反饋來動態更新推薦算法的權重參數。同時，基于協同推薦的思想建立學習“群組”，有利于碰到同類問題的學生之間的交流。綜合上述方式，以期對學生的學習興趣、信心和效率等產生正向的促進作用。

1 工作基礎和現狀分析

1.1 EOJ及編程類課程實踐題集

本校計算機專業建設的OJ 平臺稱為EOJ[2]，已支持C、C++、Java、Python、Pascal、PHP 等10 多種語言的編程解題，屬于國內領先的、支持語言較多的OJ 平臺。平臺最初是為了訓練本科生參加程序設計競賽而設計開發的，目前本專業將大部分專業課程的上機練習和考試建設在EOJ 中，既真實地考查學生的編程能力，又方便教師的教學管理。目前基于平臺的程序設計類課程有：《程序設計基礎》、《程序設計能力實訓》、《數據結構》、《算法分析與設計》。這些課程2018-2019學年在EOJ 平臺上的上機情況如表2 所示。

表2 EOJ 平臺上的課程開設情況

從表2 的數據分析得到，在每門課程中，每道題目的平均提交次數均大于學生人數，說明學生在一道題目上都多次提交。

在程序設計類課程的教學中，我們發現有很多課程知識點有疊加的部分，我們把不同課程的知識點標簽進行了集中梳理，盡量做到同一個知識點用同樣的標簽進行標記。本課題將分析課程的提交日志，進行個性化學習路徑的推薦。

1.2 學習路徑

學習路徑是個性化學習中的核心部分，大量研究者從不同的視角對學習路徑的產生進行了研究。目前已有研究工作中需要進一步改進的問題包括：①學習路徑中的學習內容粒度較粗，常見的僅為課程序列和知識點序列；②路徑缺乏動態性；③路徑產生中的推薦原因不夠清晰。本文將探索如何進行細粒度的推薦，并給出推薦理由，根據學生的認可度動態調整推薦策略，生成個性化的學習路徑。

1.3 推薦算法

自推薦算法被提出以來，先后有很多改進方法，其中經典的方法有協同過濾方法、矩陣分解方法、混合推薦方法及近年來流行的基于深度學習的方法等。這些算法中已有一部分被嘗試用于OJ 平臺的題目推薦中。文獻[3]中的工作依據用戶是否已經成功解決相應的問題及用戶做題提交次數與閾值的大小關系對用戶進行詳細的劃分，使用Jaccard 測量兩個集合的交疊率，并將其作為相似性函數測量兩位用戶之間的相似度。文獻[4]中的工作在之前研究的基礎上添加了噪音處理技術，使用Simple Matching Coefficient（SMC）函數作為相似性函數得到目標用戶的最近鄰，并使用最近鄰數據進行相關題目的推薦。此外，在OJ 推薦上還存在一些其他的方法，如文獻[5]中提出的基于關聯規則挖掘的方法，當目標用戶解決一道題目之后，算法可根據題目之間的關聯規則為用戶生成下一題的推薦。

混合推薦算法是將幾種推薦算法進行融合，算法既可以同時采用多種推薦技術給出多個推薦結果供用戶參考選擇，也可以將多種推薦技術進行加權得到一種推薦結果。算法還可以將不同推薦方法產生的特征進行相應的融合得到最佳的推薦。本文的探討背景是特定課程中的細粒度學習路徑推薦，將采用混合推薦的思想來實現個性化學習路徑推薦。

2 基于OJ平臺的編程實踐類課程學習路徑混合推薦

2.1 總體結構

基于OJ 平臺的混合推薦的總體思想是：在教師給出的學習路徑基礎上，將用戶（即學生）自身的因素考慮在內，結合基于用戶的協同過濾方法和上下文信息（時間、登錄的設備、情緒等因素）動態產生學習路徑，并同時生成推薦理由，以便用戶根據自身的需求選擇合適的題目作為“下一題”。另外，教師和學生都可以對推薦結果進行評價，相關的評價信息用于動態調整混合推薦中各部分權重，以獲得越來越準確的推薦效果。圖1 所示是混合推薦總體思想的示意圖，后續分節具體闡述各部分。

2.2 教師給出的學習路徑

作為應用于特定課程的學習路徑推薦，由教師首先根據課程知識點結構給出基礎學習路徑。學習路徑包含3 個關鍵要素：知識點的前后關聯、題目難度和跳轉條件。在本文的研究中，借助基礎Petri 網結構來給出學習路徑的可視化表示：

（1）結點：每個結點表示OJ 平臺中上機實踐題集的一道題目，可以在結點上標記難度值和相關知識點等屬性；

（2）變遷：若題目涉及的知識點之間具有前導和后續的關系，則在它們之間增加一個變遷；

（3）變遷規則：變遷規則指的是激活變遷的若干條件。例如，變遷t1 有n 個輸入結點，可以定義這n 個結點中的80%完成即激活變遷。變遷被激活后，學生可以做變遷的輸出結點對應的題目；變遷規則也可以根據題目難度進行定義，例如完成了難度值大于閾值的題目后即可以激活變遷。

教師在課程教學中，首先需要對OJ 中編程練習題的所屬知識點進行分類和相互關聯的梳理，基于這些分類，教師給題目打上標簽并根據經驗預估難度。對于表示一道題目的結點來說，其屬性包括：題目編號、知識點標簽和難度。最后，根據學習順序、難度層次，把結點通過“變遷”關聯起來，即形成了教師給出的學習路徑。

以《數據結構》課程的實踐題集為例，圖2 所示是《數據結構》課程中教師在“線性結構”部分給出的鏈表學習路徑的示意圖。圖中T1、T2、T3即為變遷，表示學習的先后順序。每個變遷根據需要進行規則疊加。在T3 上，目前設置的規則是“完成題目1007 或題目1014”可激活變遷，這表示完成兩道題目中的一道就可以進入下一個題目。但是對于不同的學生，做題習慣可能不同，有的學生希望在一個知識點上進行多道題目的練習以夯實基礎，而有的學生樂于挑戰更有難度的題目。因此，在這個教師給出的路徑上如何增加個性化推薦是本文要研究的主要內容。由于要單獨采集學生個體的偏好比較困難，而平臺已經積累了大量的提交記錄，所以我們選擇使用協同推薦的思想來完成推薦。

圖1 混合推薦總體思想示意圖

圖2 教師給出的鏈表部分學習路徑示意圖

2.3 基于用戶的協同過濾推薦算法

以基于用戶的協同過濾方法為基礎，可以根據目標用戶解題時的嘗試提交次數和最后解題結果找出和目標用戶相似的n 位用戶，根據這最相似的n 位用戶已經做過并最終通過的題目且目標用戶未做過的題目為目標用戶生成Top-k 道題推薦。這部分使用的推薦算法的關鍵步驟如下。

（1）創建用戶-題目的0/1 二進制矩陣M[u,p]，如果用戶解題成功，則結果為1，否則為0，見表3，以用戶U1 為例，該用戶成功解題P1～P4,P6～P9，但P5,P10沒有通過。放縮到-1～1 的范圍中，結果（保留2 位小數）見表5。

表3 用戶-問題二進制矩陣M[u,p]

X_norm=(X-X_min)/(X_max-X_min) （1）

表4 用戶-問題擴充矩陣

表4 用戶-問題擴充矩陣

?

表5 用戶-問題擴充矩陣歸一化結果

表5 用戶-問題擴充矩陣歸一化結果

?

（2）使用用戶解題時的嘗試提交次數細粒度地表示用戶-題目矩陣并生成矩陣，以獲取精確的相似用戶。其中，若用戶解題成功，則使用解題成功前的嘗試提交次數正數表示，反之使用嘗試提交次數的負數形式表示，0 表示未進行過提交，見表4。

為便于計算和統計，將M1[ ]u,p 取絕對值后，對每個問題按照公式（1）進行歸一化計算，計算結果加上原來對應的正負號后生成矩陣M2[ ]u,p ，M2 矩陣將數據

（3）使用歸一化后的用戶嘗試提交次數作為用戶的向量表示，基于余弦相似度函數，利用公式（2），求解用戶u,v 之間的相似度，并生成相應的相似度矩陣。

利用上式得到的用戶之間的相似度矩陣見表6。

表6 用戶-用戶相似度矩陣

以上述用戶之間的相似度矩陣為例，對于用戶U6，最相似的三位用戶為：U4、U3 和U1。

（4）遍歷目標用戶在二進制矩陣M[u,p]中分數為0的題目，將目標用戶U6 前n 位相似用戶做題情況利用公式（3）進行求和得到題目的推薦分數，將推薦分數降序排列取前k 道為用戶生成推薦。

以用戶U6 為例，最相似的前3 位用戶為U4、U3、U1，將其代入公式（3）中，得到對于用戶U6 未做或未提交通過的題目P6、P7、P8、P9、P10、P5 的系統推薦分數，分別為2.417、0.722、2.417、2.417、1.695、0.0。若取k=3，本例中即得到協同過濾推薦算法結果為UserCFtopk={P6，P8，P9}。

2.4 上下文相關策略

除了教師給出的學習路徑及基于用戶協同的過濾推薦算法產生的若干候選題之外，在生成個性化的學習路徑時還應該考慮用戶的上下文信息。例如，當前時間、用戶的本次登錄持續在線時間、用戶的性格特征等。在本次教改嘗試中，我們考慮了三個方面的內容。

（1）時間因素：在較晚的時間段（0 點～8 點）或者用戶本次登錄持續在線超過平均值后，將協同過濾得到的推薦列表按照題目原有難度升序排序，生成一個新的推薦列表Context-topk 用于題目推薦，即在“凌晨或用戶在線時間過長”這個上下文環境中，傾向于將簡單的題目優先推薦，以調節學生的學習強度。

（2）反饋信息：個性化的學習路徑是否能符合學生的需求，需要在實際使用中不斷探索。因此，我們在推薦算法中設置了反饋環節。學生每次在推薦的題目中選擇某道題目開始練習，如果在此次登錄中成功提交，則認為推薦成功。每道推薦成功的題目在上下文相關策略中都會增加一次權重，可以按照這個策略對協同推薦的結果進行再次排序。

（3）知識點補缺：在我們的EOJ 系統中，每門程序設計類課程的練習題都給出了“知識點”標簽，在此基礎上，算法會選擇一些非本課程題庫中的同類知識點題目放入候選推薦列表推給學生，便于需要復習和夯實基礎的學生快速找到同類練習。

2.5 推薦結果生成

本文工作最終生成的推薦結果是一個細粒度的個性化學習路徑。根據學生解題情況，在教師給出的學習路徑上求出后續的結點。同時，使用協同過濾推薦算法得到排序后的k 道題目，將包含這些題目結點的學習路徑子圖取出，生成的個性化學習路徑推薦。在此基礎上，附加推薦理由及根據上下文相關策略生成的排序結果，幫助學生選擇合適的題目繼續學習。

3 應用案例

在華師大計算機專業的專業課程《數據結構》的教學中，我們使用了混合推薦算法為每個學生的每次登錄生成個性化學習路徑推薦。課程題庫共100 道編程練習，有知識點標簽和難度標記，教師在布置作業時給出了根據知識點生成的學習路徑。如圖3 所示，在某位學生的一次登錄中，根據系統中的做題記錄，他已成功提交了1009,1006,1007 三道題，依據教師給出的學習路徑，他后續可以選擇的題目是1014,1106,1064,1065。依序后臺的協同推薦及上下文相關推薦，排序后的前3 道題目是UserCF-top3={1014,1065,1064}。

據初步統計，在EOJ 平臺上實施了個性化學習路徑混合推薦后，《數據結構》課程中，學生通過推薦鏈接點擊進入下一題的比例占70%，在學期結束時練習題集的完成比例比上一學年上升約10%。

4 結語

要在OJ 平臺上實施個性化學習路徑混合推薦，對于教師來說，題庫建設階段需要根據知識點順序規劃靜態學習路徑，從某種程度上來說促進教師對OJ 練習題的深入了解。對學生來說，個性化推薦增加了學生與平臺的互動，學生的行為反饋到個性化學習路徑推薦算法中，推薦結果受到學生的廣泛歡迎。

在后續的工作中，我們將考慮在上下文中加入用戶的性格特征，并在“推薦結果生成”環節融合其他學習模型進行嘗試，并嘗試進行更多的基于知識點的推薦，以期在整體的編程類課程教學中達到更好的效果。

圖3 應用案例——《數據結構》課程中對某用戶生成的推薦結果