計算機課程相似度計算方法及其改進

仲啟玉，張少宏* ，丁 漢，張芷芊

（1.廣州大學計算機科學與網絡工程學院，廣東 廣州 510006；2.廣州華南商貿職業學院信息工程學院，廣東 廣州 510650）

隨著互聯網技術的不斷發展，計算機科學成為時下熱門專業。對教育數據進行挖掘可用于設計更好、更智能的學習技術，并更好地為學習者和教育者提供有用信息［1］。如根據學生在教室中的座位選擇來評估數學能力，對學生課堂筆記的記錄情況研究學生學習信念和學習能力關系等［2］。通過對學生建?？梢垣@得一個相對清晰的學生學習風格模式。文獻［3］從學習系統中獲得學生、課程、評價等級的數據，構建課程推薦系統，以及可用于預測學生成績的方法，所提出的課程推薦系統可以在實踐中應用。簡單的課程標簽化難以有效利用相關輔助信息，計算機領域知識點往往蘊含在高校教學大綱、課程大綱、網頁以及計算機領域的文獻等資源中，若將這些知識融合在一起，把相關知識點之間的層次關系和聯系用知識網絡的形式表現出來，形成簡潔清晰的知識網絡圖［4］，通過這樣的圖結構可以快速了解各知識點之間的聯系和區別，對于掌握計算機知識整體結構幫助非常大?，F有的課程僅提供本身的孤立信息，而對于某一領域知識的掌握不能僅靠孤立的課程學習，而是要掌握課程間的關系以及某課程和這一領域間的關系，比如計算機學科間的相似或遞進關系對于計算機領域知識的學習就很重要，學習計算機不僅需要很好的數學基礎，同時還需要其他學科背景知識的積累?，F有的關于計算機課程關系的研究多為先修關系（prerequisite）的研究。文獻［5］研究了大學課程中概念與課程之間的聯系，將大學課程表示為一個以課程和概念為節點，以它們之間的連接為邊緣的圖，利用圖論的方法來表示二者之間的關系。文獻［6］提出了先決條件網絡來可視化學術課程中的隱藏結構，將學術課程視為一個復雜的系統，其中的節點代表課程，節點之間的連接則可以從課程列表中輕松獲得課程的先修關系。文獻［6］提供了一種評估課程的方法，并且為課程修訂提供了框架，使整個課程的重要程度可見，并提供了定量的分析。文獻［7］研究如何從課程依賴中提取概念先決條件關系，提出一個優化的框架來解決該問題，并創建了一個用于研究此問題的真實數據集，包含來自11所美國大學的計算機科學課程清單以及課程的概念對和先修課程標簽。文獻［8］研究了一種基于課程和概念對大學課程中的連通性和知識流進行了定量檢查的方法，為課程編制和表示課程依賴概念提供了有效方法。文獻［9］提出一個可視化大學課程結構的工具，包括課程和知識之間的聯系，以及使用圖論概念檢測、分析和可視化課程結構，便于課程學習和課程修訂。本文以國外計算機名校的計算機科學課程為分析對象，以課程和知識點為雙關系圖，量化知識點之間、課程之間、高校之間的聯系，進行計算機課程知識圖譜的構建分析，直觀反映計算機專業課程體系，為高校開展計算機課程和學生選擇課程學習提供一定的數據參考。本文討論了如何獲取相關數據，如何提取課程關鍵詞、構建語料庫、如何計算相似度等。利用多種算法進行計算，并根據計算的結果進行對比分析，選擇出最適合本文的算法。

1 構建語料庫

1.1 課程數據的爬取

網絡爬蟲是一種能自動下載網頁的程序，本文使用Python語言來設計適合本文的網絡爬蟲以獲取數據。為獲取具有代表性的計算機科學課程文本內容，本文選取的文本來自排名靠前的國外計算機名校。通過各個學校官網上的計算機科學課程信息，選取需要的字段。為了研究計算科學課程的知識圖譜，選取字段：課程id＼課程名＼課程描述＼課程關系，用課程描述來代表每門課程。爬取下來的課程信息保存為Excel文件，保存格式如下：課程ID（ID）、課程名（Name）、課程描述（Course Description）、排選課＼預選課（Prerequisites），將每一項存在一列中，一共有4列數據，以便后續讀取。數據保存格式如圖1所示。最終爬取了約100所學校，近6 000門課程，每所學校存為一個Excel文件單獨存放，每一行是一個課程信息，文件名為學校名簡寫。

圖1 數據保存格式Fig.1 Data saving format

1.2 數據預處理

使用Python的NLTK工具來進行英文文本的數據預處理，構建文本詞庫。為了對課程內容信息進行分析，需要對課程內容數據進行單詞小寫化、去標點符號、分詞處理及去停用詞等處理，以消除臟數據對結果的影響。

將所有單詞統一小寫化，標點符號在文本中無實際意義，因此，將文本去除標點符號。英文語料的分詞方法有空格分詞、re匹配符號進行分詞和NLTK分詞器等，本文選用NLTK分詞器進行分詞。原理很簡單，依據空格和標點符號來進行分詞處理。停用詞指的是在文本中沒有什么實際意義的詞，如“the”“all”“so”等詞，在語料庫中還會影響最終分析結果，因此，在對課程文本進行分析前，將這些詞剔除。

由于英語單詞詞形多變，一個單詞可能有名詞、動詞、形容詞、副詞等各種形式，其表達的詞根意思是一樣的，為了有效地提高關鍵詞密度，需要對課程文本單詞進行詞形還原處理。詞形還原就是返回詞的原形，根據單詞的詞性來提取單詞的詞干，對單詞進行詞性的識別，根據詞性標注來處理單詞詞綴，從而還原單詞?？梢钥闯?，單詞經過詞形還原處理后是具有一定意義且完整的詞，能準確地表達文本，符合對數據預處理結果的預期。根據單詞詞性進行詞形還原，結果存儲在課程表格第四列，數據預處理結果如圖2所示。

1.3 課程文本量化

計算機是無法直接識別文本的，為了對文本進行有效地數學分析，需要將其進行量化，轉化為向量表示。詞袋模型和詞向量模型是兩種最常用的模型。向量空間模型就是詞袋模型，其中，最簡單的是基于詞的獨熱表示（one-hot representation）。工程上比較常用的是用詞的TF-IDF［10］值作為權重，它是文本處理中最常見的一種權重計算方式；另一種就是文本的分布式表示方法（distributed representation），其中，LSA、LSI、pLSI，以及Word2Vec［11］、Doc2Vec方法都屬于分布式表示。

詞袋模型的方法將文本變成一串數字（索引）的集合，在詞袋模型中，將文檔單詞映射，并統計這種單詞的出現次數。這種向量表示法不保存原始句子中詞的順序。

詞向量也叫詞嵌入，就是將單詞映射到向量空間里，將詞用向量來表示。One-hot表示方法是把每個詞表示為一個很長的向量，向量的維度就是詞匯表的長度，其中，絕大多數元素為0，只有一個維度的值為1，這個維度就代表了單詞，但是這種表示方法中，任何兩個單詞都是孤立的，無法在語義層面上表達單詞之間的關系。Distributed representation表示方法通過訓練，使所有單詞向量構成向量空間，每個單詞被映射到較短的單詞向量。本文采用distributed representation來表示詞向量。

1.4 特征詞權重量化

對于文本數據的處理，首先就是要獲取文本的特征信息，提取文本關鍵詞，包括候選關鍵詞提取、用詞頻或TF-IDF等過濾，以及使用閾值從候選詞中選擇關鍵詞。

本文使用課程描述的特征詞來代表這一門課程，特征詞提取的算法有很多種，不同算法提取的效果也會不同。常見的有TF算法和TF-IDF算法等。TF算法中一些常用詞的權重很大，因此，不適合使用TF算法來衡量權重。本文選取了TFIDF算法來計算語料庫的詞的權重，進行特征詞的權重量化。TF-IDF算法目前在文本分類中被廣泛使用，它借鑒了信息檢索。某詞在某文檔中是高詞頻，而在整個文檔集中該詞又是低文檔頻數，可以通過TF-IDF公式獲取較高的權值。TF-IDF傾向于過濾掉常用詞并保留重要詞，對比TF算法，TF-IDF算法更符合本文對于特征詞權重的衡量，因此，本文使用TF-IDF算法來量化表示特征詞權重。

2 相似度計算

2.1 課程相似度計算

根據現有相似度度量方法進行特征詞（知識點）與特征詞（知識點）之間的相似度計算、課程與課程的相似度計算以及學校與學校的相似度計算。本文計算課程之間的相似度主要是單詞語義相似度的度量，選用TF-IDF模型、LDA主題模型及詞向量模型等來建模并計算相似度，并通過這3種方法的相似度計算效果進行分析比較，從而選擇適合本文的計算方法。

使用TF-IDF方法計算的課程相似度過于分散，從0.1～0.9，而且如果兩門課程之間想要相同的詞，則相似度為0，效果不好，不符合本文對于相似度計算的要求，因此，后續對于相似度的計算不使用這種方法。

利用LDA主題模型計算出來的相似度非常密集，都在0.5之間，效果不是很好，而且最致命的缺點是LDA模型相當不穩定，對于不同的語料庫計算相似度需要訓練不同數量的主題，由于本文語料庫比較大，用這種方法計算相似度不切實際，因此，LDA主題模型計算相似度的方法也不適用。

本文采用詞向量來表示課程文本單詞的表示方法，通過訓練可以將每個詞映射為一個固定長度的向量，這些向量構成了一個詞向量空間，其中，每一個向量可以當作空間上的一個點，通過計算向量之間的距離來表示詞之間的相似性［12］。圖3為詞向量文件，其中，每一個單詞都是由一個300維的向量來表示的，一共有13 119個單詞。從第二行開始每一行代表一個單詞，用空格隔開，圖中第二行代表單詞“the”，后邊是它的向量表示。這就是整個語料的整體結構，是一個標準的詞向量表示文本，可以使用gensim等第三方庫直接讀取。

圖3 詞向量文件Fig.3 Word vector file

基于詞向量計算課程相似度算法設計如下：

（1）計算詞之間的相似度，即通過計算兩個詞向量的夾角余弦值來計算兩個詞的相似度；

（2）計算課程之間的相似度，即基于詞之間的相似度矩陣，通過計算得出兩門課程的詞的相似度矩陣，然后計算詞相似度矩陣行方向與列方向詞的最大值／中位數相似度總和，再求平均值，即為兩門課程之間的相似度。

詞向量方法計算的相似度效果比前兩種方法效果要好，但是相似度也相對比較集中。中位數方法與最大值方法整體趨勢是一樣的，本文選用最大值法，通過對比課程得出相似度的計算還是存在一定的偏差，因此，需要改進算法。

2.2 設計詞組相似度計算的新算法

基于詞向量計算課程相似度的算法效果雖然很好，但是對于本文存在著很大的弊端：計算相似度時間過長，計算60門課程之間的相似度要0.5 h，而語料庫的課程信息較多，因此，需要對算法進行改進。運行時間緩慢的原因主要有：①多次讀取遍歷向量模型：每一次計算詞的相似度，就得遍歷兩遍詞向量模型找到其對應的詞向量，然后再計算它們之間的相似度，多次讀取消耗時間；②多次重復計算詞對相似度：課程的詞有大量重復，也就意味著多次重復計算同一詞對的相似度。

針對上述兩個原因，對向量模型的算法進行優化設計：①減少多次讀取遍歷向量模型的時間，即使用字典將向量模型一次讀取存儲起來，字典｛key：value｝采用｛詞：向量｝的存儲方式，每當需要查找一個詞的向量時，直接使用關鍵字索引的方式即可；②利用標注矩陣減少詞對計算次數。

具體實現方法及步驟如下：

（1）遍歷語料庫，得到詞匯表（即語料庫所有單詞詞匯）；

（2）生成標注矩陣。根據詞匯表，生成詞匯*詞匯的二維矩陣，初始化全部為0，遍歷課程對，如果要計算相似度的詞，則加1；

（3）生成詞相似度矩陣。根據詞匯表，生成詞匯*詞匯的二維矩陣，初始化全部為0，根據標記矩陣，如果兩個詞的標注矩陣值＞0，則計算這兩個詞的相似度，從而完成知識點與知識點關系的量化；

?

（4）計算課程之間的相似度。先構建兩門課程的詞矩陣，根據詞相似度矩陣，得到兩門課程的詞矩陣的相似度矩陣，然后計算詞相似度矩陣行方向與列方向詞的最大值／中位數相似度總和，再求平均值，即為兩門課程之間的相似度，從而完成所有課程關系的量化，描述所有課程之間的關系。算法描述：

標注矩陣生成結果如圖4所示。標注矩陣中，很多詞對之間的標注矩陣遠遠大于1，說明這些詞對不止計算一次。用標注矩陣的方法避免了這些詞對多次計算相似度，從而加快了計算速度。圖4中標注矩陣為0的單詞對說明兩個單詞之間不用計算相似度的。

圖4 標注矩陣生成結果Fig.4 Results of labeling matrix

相似度矩陣構建結果見圖5。由圖5可以看出詞之間的相似度，如詞對（sensor，surveillance）＝0.53，說明這兩個單詞之間的相似度為0.53，根據這些詞（知識點）的相似矩陣繼而可以進行下一步的計算，即課程相似度的計算。

圖5 相似度矩陣構建結果Fig.5 Results of similarity matrix construction

課程熱力圖見圖6，可以看出相似度主要集中在0.3～0.7之間，沒有什么異常的數據，可通過課程實際情況大概衡量相似度的準確性。選擇一門課程Cloud Computing，它和Developing Enterprise Web Applications相似度最大，相似度為0.79，和Research Topics in Computer Science相似度最小，相似度為0.41。根據課程描述，可以看出這種方法計算出來的相似度相對比較準確，運算速度較快，符合本文的預期要求。

2.3 學校相似度計算

計算學校之間相似度的方法與計算課程相似度矩陣方法類似，即讀入所有課程相似度矩陣，然后計算行方向與列方向詞的最大值／中位數相似度總和，再求平均值，即為兩所學校之間的相似度。

學校相似度計算為計算機專業課程改革提供一定的數據支持，也為學生選擇合適的學校提供了一定的參考數據。

2.4 相似度算法運行時間比較

兩種算法相似度計算時間對比如圖7所示。由圖7可知，新算法比舊算法要快大約2～3倍，且計算相似度課程數目越多時，節約的時間越多。比如當計算10所學校的課程相似度時，舊方法需要22 h，而新方法只需6 h，節約了16 h；當計算30所學校時，可節約32 h。這只是部分結果，新算法還需進一步優化。

圖7 不同方法相似度計算時間對比Fig.7 Comparison of similarity calculation time of different methods

3 聚類分析

3.1 層次聚類

（1）課程層次聚類

采用層次聚類法［13］計算語料庫課程之間的相似度，使用前面計算的相似度文件直接聚類，而不需要重新計算距離，并按課程相似度由高到低的順序來進行排序，排序后重新劃分節點。根據選用方法的原理及相似度計算的目標，選用ward的方法來進行層次聚類。

由課程層次聚類結果（圖8）可以看出，課程經過層次聚類后被分為幾個類，同一個類別的課程分布的距離比較靠近，由此可以看出哪些課程更為相似。

圖8 課程－層次聚類樹形圖Fig.8 Courses hierarchical clustering dendrogram

（2）學校層次聚類

學校層次聚類結果（圖9）顯示看出各個高校聚類后的分類結果及空間分布，可以判斷哪些學校更為相似，從而為學生選擇高校提供一定的參考。

圖9 學校－層次聚類樹形圖Fig.9 Schools hierarchical clustering dendrogram

但從高校分布的散點圖（圖10）來看，部分同一分類的高校距離較遠，比如wvu（西弗吉尼亞大學）與brown（布朗大學）在空間上的距離比較遠，但是經過聚類卻屬于同一類別，所以，高校關系的層次聚類效果，并不符合預期結果。

圖10 學校－層次聚類散點圖Fig.10 Schools hierarchical clustering scatter diagram

3.2 K-means聚類

K-means算法［14］是依據數據在空間中的分布位置關系將數據聚類為K個簇。從原始集群中選擇K個點作為簇的質心，重新計算質心，樣本點選擇歸入離自己在空間分布最近的簇，計算每個簇的質心，并更新簇的質心。

（1）課程－K-means聚類

從課程－K-means聚類結果（圖11）可以看出，經過K-means聚類的課程關系分布與課程層次聚類效果一樣，同一類別的課程在空間上的分布接近，符合預期結果。對于課程的K-means聚類來說，K值的選擇是比較重要的，如何選擇一個合適的K值，需要經過多次合理試驗，并根據聚類效果進行選擇。

圖11 課程－K-means聚類散點圖Fig.11 Courses K-means clustering scatter diagram

（2）學校－K-means聚類

從學校－K-means聚類結果（圖12）可以看出，經過K-means聚類后各個高校之間的關系與層次聚類效果不同，接下來對這兩種方法的結果進行對比分析。

圖12 學校－K-means聚類散點圖Fig.12 Schools K-means clustering scatter diagram

3.3 高校聚類結果分析

由圖10和圖12可以看出，兩種聚類結果空間的分布大體相同，但由于參數不同以及算法原理不同，最后的聚類分類結果不同，比如在層次聚類中，學校wvu（西弗吉尼亞大學）與bulletins（賓夕法尼亞州立大學）是不屬于一個類別的，但是在K-means聚類中，它們屬于同一個類別，而且在Kmeans聚類中，同一類別的高校比層次聚類的高校在距離上更加接近，因此，與層次聚類相比，Kmeans聚類的結果更符合預期的結果。

4 結 論

在傳統的計算機科學課程描述方法中，存在著很多不足：①缺乏對專業課程間關系的整體結構的量化，只是提及了部分課程的關系，而沒有具體量化各課程間的關系；②沒有對課程知識點之間關系的量化，無法獲得各知識點之間的具體聯系；③基于文檔描述各個課程，不適合在整體上把握計算機科學專業課程的結構。

針對計算機科學傳統描述方法的不足，本文以國外排名靠前的計算機名校的計算機科學課程數據為語料庫，通過對課程知識點的特征提取、權重計算和量化表示，介紹了相似度計算的多種方法，通過不同的算法計算課程間的相似度，并對計算結果進行分析比較，最終選擇最符合預期目標的算法。同時，在課程相似度的基礎上完成了對學校相似度的計算，并分別利用層次聚類和Kmeans聚類對課程和學校進行聚類分析比較。本文提供了從課程信息數據中發現其中所蘊含的知識、課程體系結構、課程關系計算的方法，為課程學習者提供課程的整體框架和關鍵知識內容，為改善計算機教育質量提供了科學依據和數據支持。

本文設計了詞組相似度計算的新算法，原來的相似度算法直接遍歷詞向量文件，找出所有課程對中單詞對的向量進行相似度計算，這樣會導致詞對相似度多次重新計算。本文對相似度計算算法進行改進，利用標注矩陣，使每個詞對僅需計算一次相似度，從而避免了詞對相似度的重復計算，有效提高了相似度計算的速度。新的相似度計算方法具有顯著的借鑒價值，有大量的應用場合，比如無向圖挖掘時的點對相似度計算，社交網絡社區發現，聚類融合時點對相似度比較等。研究過程中遇到了很多問題，比如包括如何快速計算相似度、如何處理高維度向量等，通過對各種算法進行對比，最終確定算法的選擇，解決了這些問題，為計算課程知識圖譜的構建提供了牢固的數據基礎和算法基礎。