程序在線測評系統的知識圖譜構建與應用

宋瑋情，崔煥慶，楊峻鑄

（山東科技大學計算機科學與工程學院，山東 青島 266590）

0 引言

隨著大數據時代來臨，數據價值日益增加。面對多樣化的數據形式，傳統關系型數據庫只能處理簡單的數據關系，而知識圖譜能高效地存儲和應用復雜的關系知識，受到了學者們的廣泛關注和研究，目前已成為知識應用和資源管理的重要技術之一［1］。知識圖譜由節點和邊組成，其中節點表示概念和實體，概念指抽象出的事物。實體指具體事物，基本特征通過屬性表示；邊表示實體與概念之間的關系。知識圖譜本質是一個具有屬性的實體，通過關系相互連接所構建的網狀知識庫，并以結構化的形式描述客觀世界的概念、實體和兩者之間的相互關系［2］。因此，知識圖譜不僅表示語義關系，還能聯系各類信息構建關系網絡，從“關系”的角度分析問題。

近年來，傳統課堂教學模式存在教師教學強度大、學生學習效率低、教學資源利用率低等問題。為了解決上述問題，提出了程序在線評測（Online Judge，OJ）系統，該系統在程序設計等課程的教學、競賽中受到廣泛應用，獲取了海量的數據資源，這些資源是計算機教育的重要組成部分［3］。如何從數據資源中分析出有價值的信息輔助教學是目前的研究熱點。基于此，本文結合知識圖譜對OJ 系統的數據進行處理，構建OJ 知識圖譜，并通過挖掘、分析數據，為個性化教學和學習提供數據支撐，最后以個例分析的形式討論OJ知識圖譜對學情分析與路徑規劃的實際應用價值。

1 相關工作

知識圖譜由三元組表示，表達式為head,relation,tail，簡記為h,r,t。其中，h和t分別表示三元組的頭實體和尾實體，r表示頭實體和尾實體之間的關系，每個節點和關系都通過鍵值對（Key-value）進行表示［4］。知識圖譜可通過關系型數據庫、RDF 三元組庫和圖數據庫進行存儲。其中，圖數據庫是基于圖形式存儲的新型非關系型數據庫，具有存儲靈活、查詢高效等優勢，適合表示如（實體，屬性名，屬性值）、（實體1，關系，實體2）等形式數據，并且關聯查詢無需復雜操作［5］。

馬騰等［6］建立了個性化教學知識圖譜，將知識圖譜融入教師備課、課堂教學、課下作業布置、課外輔導等一系列教學環節當中，自動為學生提供感興趣的學習內容，實現了精準化和個性化教學。黃梅根等［7］創建了初、高中知識圖譜，基于知識圖譜使用改進的認知診斷模型診斷學生對特定知識點的認知程度。Yan［8］以“國際貿易實務”課程為研究實例，通過融合教學理論與教學資源構建知識圖譜，幫助學生提高學習效率；通過培養邏輯思維能力和改進教學方法，提高教師教學水平。Zheng［9］從MOOC 網站上獲取課程的相關信息，對實體和關系進行提取，構建高等教育知識圖譜。

本文基于Neo4j 構建OJ 數據的知識圖譜，給出了OJ 數據的預處理過程。然后，Web 端通過可視化方式展現OJ 數據的網絡關系，進一步分析OJ 知識圖譜在學情分析、個性化教學和學習方面的應用。

2 OJ 知識圖譜的本體設計

為了構建實用性強、結構合理的OJ 知識圖譜，本文設計主要從2個方面考慮：①OJ系統中實體和關系的組織；②現實應用對OJ 知識圖譜的功能需求。OJ 系統中包含的節點種類較少，但節點之間的關系數量很多，需要設計明確的知識架構作為創建知識圖譜的基礎［10］，即定義OJ 知識圖譜中包含各實體的概念以及它們之間的關系。如表1 所示，OJ 知識圖譜中主要包含測試、題、學生、老師4 類實體，為了準確描述各實體信息，定義了每類實體的相關屬性。實體屬性分為對象屬性和數據屬性，其中對象屬性描述實體之間的關系，值為相關的另一實體；數據屬性表示實體的屬性，值為XSD（XML Schema Definition）的數據類型。基于上述設計，將各類實體和關系相互組合構成了一個縱橫交錯復雜的知識圖譜，如圖1 所示（彩圖掃OSID 碼可見，下同）。

3 構建OJ 知識圖譜

3.1 數據采集

首先需要采集、分析數據。OJ 系統使用關系型數據庫存儲數據，先將數據以逗號分隔的CSV 文件導出，為了防止亂碼，所有CSV 文件格式都使用UTF-8 進行編碼。如表2 所示，文件存儲了OJ 系統的實體、關系及它們之間的屬性，每條記錄都擁有唯一的ID 屬性，然后利用Neo4j 中Cypher 的LOAD CSV 命令將數據導入至Neo4j。

Table 1 Entity attribute table表1 實體屬性表

Fig.1 Ontology structure of OJ knowledge graph圖1 OJ 知識圖譜的本體結構

Table 2 CSV file table表2 CSV 文件表

3.2 知識圖譜的構建方式

知識圖譜構建的主要方式有：自底向上、自頂向下和自動構建3 種。自底向上的構建方式根據人們已知知識為主導，對相關領域概念進行層次劃分，該方式適合構建通用型知識圖譜；自頂向下的構建方式先從比較權威的公開數據集或專業的網站中獲取數據信息，再通過技術手段獲取所需的信息實體、關系及屬性，適合在知識明確、關系清晰的領域構建知識圖譜；自動構建則通過機器學習、數據自動獲取、統計等技術構建知識圖譜。由于OJ 系統應用于特定領域，本文采用自頂向下的構建方式，將實體、關系及屬性信息輸入圖形數據庫Neo4j 中實現知識圖譜的可視化展示及存儲。

基于山東科技大學OJ 系統中2019 年程序設計基礎（C語言）實驗課程數據構建知識圖譜，其中數據包括924 個實體（6 名老師、298 道題目、164 次測試和456 名學生）和153 612 條關系。圖2 展示了OJ 知識圖譜的部分內容，其中學生、題目之間的提交關系占據了非常重要的地位，它們不僅展示了學生對某個題目所涵蓋知識點的學習情況，還體現了學生的努力程度、學習能力和學習效果。此外，對這些關系進行分析有助于教師提供個性化輔導和教學，有助于實現學生學習效果的形成性評價。

Fig.2 Partial knowledge graph圖2 部分知識圖譜

4 OJ 知識圖譜的應用

目前，在線教育領域存在老師獲取反饋不及時、學生定位［11］和學習路徑［12］不清晰、教師學生數據管理繁瑣等問題，借助OJ 知識圖譜可有效解決上述問題。本文基于Neo4j 的查詢語言Cypher 對知識圖譜信息進行檢索，分別從學生、教師和教學管理人員角度，以個例分析方式對OJ知識圖譜的潛在應用進行說明。

從學生角度而言，由于學生存在學習努力程度、學習能力、興趣愛好等個體差異，基于知識圖譜分析學生題目提交和通過情況及各種信息，對學生進行畫像［13-14］，能夠更好掌握每個學生的特點。進一步，根據K-means 聚類算法分析學生的學習情況，提取學生之間的相似度，如圖3 所示。通過聚類分析后，選擇相似用戶有助于后續工作的研究。例如：如圖4 所示，通過分析學習者的相似度，結合知識圖譜可個性化定制學生的學習路徑［15］。

Fig.3 Student clustering圖3 學生聚類

Fig.4 Student learning path planning圖4 學生學習路徑規劃

從教師角度而言，OJ 知識圖譜幫助教師分析學生對不同問題的掌握程度，判斷學生的學習水平和能力，實現學情分析，從而有針對性地調整教學計劃和提供個性化輔導。如圖5所示，76.8%的學習者在答題過程中出現答案錯誤，表明學習者對相關知識點的學習程度不夠，還需加強練習。

Fig.5 Students'errors in one test圖5 一次測試中學生的錯誤情況

從教學管理者角度而言，借助知識圖譜能有效掌握教學質量。如圖6 所示，以兩位老師（實體為紅色節點）為例，分析代表測試集的橙色節點順序，可生成每位教師的教學路徑。如果當測試集由題目組成時，則分析題目的先后順序可生成教學路徑，進一步分析可為教師進行教學畫像。

Fig.6 Analysis of teaching paths of different teachers圖6 不同教師的教學路徑分析

5 結語

本文對OJ 知識圖譜進行本體設計，通過圖數據庫Neo4j 和程序在線測評系統數據構建OJ 知識圖譜，并利用可視化方法分析OJ 知識圖譜的潛在應用。首先，OJ 知識圖譜能顯著提高學生學習興趣和學習效果，其次能協助教師進行學情分析，協助教學管理人員進行評教和評學，OJ知識圖譜能在一定程度上滿足現實課程教學需求。未來將進一步完善OJ 知識圖譜，為智能問答、成績預測分析、個性化課程推薦、關系挖掘等應用提供更強大的推動力。