基于多維不完全分類樹的教學資源推薦方法

李 松，袁登科，張麗平，田新雨

（哈爾濱理工大學，黑龍江 哈爾濱 150080）

0 引言

在新工科建設和教育大數據的背景下，個性化自適應學習成為了數字化學習的新常態。教育大數據、人工智能、數據挖掘、機器學習等技術的發展為實現個性化和精準化的學習提供了有力支持。當前，教學資源信息在爆炸性增長，教學資源呈現數量多、更新快、知識點之間的關聯復雜等特點，從而帶來了“信息過載”和“學習迷航”等問題。學習者在教學資源的搜索、查詢和選擇等方面往往會耗費較多的時間，效率較低。傳統的教學資源管理系統和相關搜索技術已經不能滿足學習者個性化的學習需求。因此，資源推薦服務必不可少，教學資源的推薦方法和相關系統［1-2］具有重要的意義，高質量的推薦系統能充分考慮學習者的差異性，并精準、高效地為學習者提供個性化學習資源。

推薦系統通過分析用戶和物品等大量信息，挖掘出物品的特點和用戶的潛在需求，及時地為用戶推薦所需的物品。推薦系統具有高效性和智能性等優點，已經應用到了諸多領域，如位置服務、廣告推送、社交網絡、營銷推薦［3］等。主要的推薦方法包括基于內容的推薦方法、基于協同過濾的方法［4］和混合推薦方法。近些年，對推薦系統的研究進一步拓展到圖神經網絡社會化推薦方法［5］、混合推薦方法［6-8］、長序列推薦方法［9］、融合知識圖譜的推薦方法［10］等。

實現學習資源有效、精準的推薦是教學資源推薦服務成功的關鍵所在。本文針對教學資源數據信息的動態變化性和不完全性等特點，對基于不完全分類樹的教學資源推薦的關鍵技術與相關系統進行了研究與設計。

1 多維不完全分類樹的分類方法

教學資源信息具有海量性、復雜性、不確定性、動態變化性和多維性等特點。現實中，一些數據信息經常動態變化，屬性特征信息經常有增加變化，關鍵維度的數據信息有缺失現象，從而對系統查詢和推薦有較大的影響。因此，資源信息的預處理具有重要意義。為了對復雜的數據信息進行有效的預處理，提出了一種多維不完全數據帶權分類樹和相應的分類方法（圖1）。不完全數據帶權分類樹可對多維不完全數據進行維度缺失判斷和分類，其結構和B+樹類似。不完全數據帶權分類樹T 由葉節點N、分支上的權重w、內部節點和根節點組成。

圖1 不完全數據帶權分類樹

通過構建好的帶權分類樹模型對不完全數據集進行分類的主要思想為：將待分類的數據元組依次存進帶權分類樹根節點N中，從上到下依次對不完全數據進行分類，根節點存放著即將進行分類的數據集中的元組，根據數據的維度不同依次將維度屬性值從左到右依次存入內部節點中；葉節點中存放著判斷完成的維度屬性數值，判斷過程如下，當存放在中間節點中的維度屬性值缺失，則進入左孩子節點中，權重為0，當維度屬性值不缺失即進入右孩子節點中，權重為1，從左向右依次對內部節點的維度屬性值進行判斷并存入葉節點中。存入葉節點的維度數據值按照水平索引并根據每個維度權重值的不同完成一次分類。一次分類結束后將葉節點的維度屬性值清空，依次進行后續的分類操作，即完成對整個多維不完全數據集的分類。

進一步給出了基于不完全數據帶權分類樹的分類規則。分類規則：給定一個不完全數據集O，若數據集中的任意元組o缺失相同的維度，使用不完全數據帶權分類樹分類模型，維度權重相同的元組被分到相同的桶中即完成了數據的分類。

規則說明：對于一個不完全數據集O，假設元組缺失的維度用“-”表示，其里面的任意缺失維度的元組o={o1,-,o2,...,oi,-,...,od}，首先將每個維度數據分配到第二層中，從第一維度i開始判斷，若維度i缺失，則i∈nodeleftChild，權重為0，否則i∈noderightChild權重為1，其中nodeleftChild為左孩子節點，noderightChild為右孩子節點。然后判斷第二個維度j，若該維度j缺失，則j∈nodeleftChild，權重為0，否則j∈noderightChild，權重為1。以此類推，直到所有維度判斷完，根據各個維度權重值、通過水平索引將這個數據輸出到對應的桶內，依次判斷數據集中的其他元組，做如上分類操作，最后完成全部數據的分類。

由以上論述可知，不完全數據帶權分類樹分類方法主要分為兩個階段，第一階段是不完全數據帶權分類樹建模，第二階段是多維不完全數據集在不完全數據帶權分類樹模型中進行分類。不完全數據帶權分類樹的根節點根據維度不同分支形成內部節點，內部節點根據該維度的屬性值是否缺失進行分支，并對左右分支賦予不同的權重，最后通過水平索引依據每個維度權重不同成功分類，對一個數據元組分類后，水平索引輸出加權的數據入桶即分類后數據集合空間，葉節點全部變為空。重復操作直到所有數據全部分類結束。

2 優化的資源信息聚類方法

教學資源信息和用戶信息的數據量往往是巨大而繁雜的，傳統推薦系統中所用的協同過濾算法在相似度計算和近鄰查詢方面的效率往往較低，時間代價較高。為了提升推薦效率，將密度峰聚類技術［11］引入推薦系統中。針對海量教學資源信息的不確定性和易缺性，對傳統密度峰聚類技術進行了改進，提出了密度峰聚類的改進方法，再將改進的密度峰聚類方法用到推薦系統的關鍵環節中。

密度峰聚類算法是一種基于密度的聚類算法，該算法的基本思想基于一種假設：聚類中心的局部密度最高并且被低密度數據對象包圍，與其他聚類中心的距離更大。針對密度峰值聚類方法不能自適應選取簇的數目以及人工選取聚類中心等問題，新提出了一種將小類合并思想和模糊C-均值算法相融合的改進的聚類方法。

如果兩個簇中心點之間的歐氏距離的差小于一個事先給定的值ɑ，且這兩個簇各自包含的樣本數據到另一個簇的中心點距離很接近，此時可以將它們看作一個簇而加以合并。首先，計算密度峰聚類算法中各個簇中心點之間的距離差dij，如式（1）所示，接下來，在密度峰聚類算法得到的聚類結果中找出各個類包含的樣本集合S，從所有簇中任取兩個簇，計算各自的數據點與另一個簇中心之間距離差的和的比值wij，如式（2）所示。

其中，公式（1）中vi和vj表示由基本的密度峰算法所獲取的聚類中心點。式（2）中Sik表示屬于i類的k個樣本點。循環計算式（1）的dij值和式（2）的wij值，wij的值越接近1，那么這兩個簇之間的距離越接近，說明它們滿足合并條件，將第i類和第j類合并為一類，選擇距離vi和vj連線中點最近的數據點作為初始聚類中心點，多次迭代計算dij和wij的值，直到遍歷所有的聚類中心點，最終獲得初始簇的數目。優化聚類方法的主要步驟如下。

（1）通過密度峰算法計算數據點的局部密度和與其他密度更高點之間的最小距離；

（2）從決策圖中獲得初始聚類的中心點集和選取的聚類數；

（3）將密度峰算法所得的聚類數目作為小類合并的初始條件，進行小類合并處理，自適應獲取初始簇的數目；

（4）合并后確定新的初始聚類中心集；

（5）將中心點集和初始簇數目作為模糊C-均值聚類方法的輸入信息；

（6）通過模糊C-均值聚類的反復迭代計算新的目標函數、隸屬度矩陣和聚類中心；

（7）獲取最終的隸屬度矩陣和聚類中心集。

進而，將基于不完全分類樹的分類方法和優化的密度峰聚類方法用到推薦系統中。所提出的優化推薦方法的主要思想為：利用不完全分類樹的分類方法對初始教學資源信息和用戶信息進行分類；針對一些復雜的分類數據信息，進一步采用改進的密度峰聚類方法分別對類中的用戶信息和教學資源信息進行聚類，得到用戶信息聚類簇和教學資源信息聚類簇；對每個類簇進行計算，基于計算結果進行推薦。本文所提出的優化推薦方法的具體流程如下。

（1）提取教學資源信息和用戶信息的特征值；

（2）利用不完全分類樹對數據信息進行分類；

（3）利用密度峰聚類優化方法對各類教學資源信息和用戶信息進行聚類；

（4）基于聚類結果集，根據用戶和教學資源評分信息進行相似度計算，得到特征相似度矩陣；

（5）基于特征相似度矩陣，選擇評分相似度較高的用戶作為目標用戶的最近鄰居集；

（6）根據最近鄰居集的興趣評分，在聚類結果中查詢最近鄰居評分較高的教學資源聚類；

（7）生成和推送教學資源推薦列表。

以上推薦流程通過密度峰聚類方法可較大程度地減少教學資源信息和用戶信息近鄰查找的數據量，可較大程度地提升推薦系統的推薦效率。

3 推薦方法性能比較和分析

針對資源信息的復雜性、多維性和不完全性，為了提升推薦系統的推薦性能，本文提出了不完全帶權分類樹的分類方法和改進的密度峰聚類方法，本節進一步給出本文優化的推薦方法和已有方法的實驗比較分析。所采用的對比方法為傳統協同過濾推薦方法和先進的混合推薦方法［6］。實驗主要驗證的是3 個算法的查詢性能，測試的指標是CPU運行時間和準確率（圖2、圖3）。所用的實驗數據集來自自建的教學信息資源庫，初始數據集的維度信息缺失率為3%。

圖2 推薦方法的CPU運行時間

圖3 推薦方法的準確率

由圖2 可知，隨著數據量的增加，3 種方法的運行時間均逐漸增長。本文方法的時間代價最小，主要是因為本文方法利用不完全帶權分類樹對數據信息進行了分類，對復雜的數據信息進行有效的預處理，在分類的基礎上進一步對復雜的類的信息進行了有效的聚類，相似度矩陣和最近鄰居集的計算是基于聚類結果進行的，從而較大程度地減少了計算量，提升了推薦效率。

圖3展示了推薦方法的準確率情況。由圖3可知，在數據量較小時準確率較高，隨著數據量的增加，3 種方法的準確率逐漸降低。本文方法的準確率變化比較平穩，受數據量增大的影響較小，在3種方法中準確率最高，主要是因為本文利用不完全帶權分類樹對維度缺失問題進行了處理，對初始數據集進行了組織和優化，改進的密度峰聚類消除了一些特異信息的干擾。

4 教學資源推薦系統設計

本文前面研究了不完全分類樹和分類方法，提出了基于密度峰聚類的推薦方法。進一步基于所提方法對教學資源推薦系統進行了分析與設計（圖4）。

圖4 教學資源推薦系統主要模塊

圖5 展示了所設計的推薦系統關鍵模型框架，由圖5 可知，系統對初始的教學資源信息和用戶信息首先進行分類樹分類和密度峰聚類的預處理，經過預處理的信息構成了教學資源數據集和用戶信息數據集；再對兩個數據集進行基本的離線計算，生成了資源模型和用戶模型；進一步基于資源模型和用戶模型進行推薦策略選擇、推薦計算、推薦結果排名和推薦結果優化；最后輸出推薦結果信息。

圖5 系統關鍵邏輯模型框架

5 結語

為了提升推薦系統的推薦效率和準確率，本文對教學資源的推薦方法和相關系統進行了研究與設計。為了對復雜的數據信息進行有效的預處理，首先提出了一種多維不完全數據帶權分類樹和相應的分類方法；在分類基礎上，為了提升計算相似矩陣和近鄰的效率，針對每一類的教學資源信息和用戶信息，對密度峰聚類方法進行了優化，并將優化的密度峰聚類方法用到推薦系統中的用戶聚類和教學資源聚類等重要環節；進一步設計了基于不完全分類樹的教學資源推薦系統。未來的研究重點主要在于大數據平臺下的基于知識圖譜的教學資源推薦系統的設計與實現。