基于新聚類算法的推薦系統的研究與實現

摘要:針對目前遠程教育中，學員數目日漸增多、水平參差不齊而教師資源短缺而無法因材施教等問題，文章構建了一個基于逐層降維聚類分析方法的資源推薦系統。該系統通過基于知識樹的聚類分析將學員分為不同的社區，由教師為社區推薦學習資源以對學員進行相對個性化的學習指導。實驗結果表明，該系統大大縮減了授課教師的工作量，并且有效地提高了學員的學習質量和學習效率;同時這種迅速動態聚類方法可以很好地將散布的學員組織在一起，滿足了學員相互之間的交流、推薦需求。

關鍵詞:遠程教育;聚類分析;個性化學習;主成份分析;線性鑒別分析

Research and Implementation of a Resource Recommendation System Based on a New Clustering Analysis Algorithm

CHEN Qing-hua1， LI Lin-jin2， WENG Zheng-qiu1

(1.City College Wenzhou University， Wenzhou 325000， China; 2.Wenzhou Third People's Hospital， WenZhou 325000， China)

Abstract: Aiming at the disadvantages such as increasing number of e-learners， diversity in learner profiles and great shortage of teachers in E-learning environment， a recommendation system based on technology of clustering analysis using dimensionality reduction method was proposed. It divides learners into different communities dynamically for relatively personalized recommendation on learning resources and guidance by clustering analysis. Experimental results show that the system takes off the heavy burden of the teachers greatly， and enhances learners learning quality and efficiency. Besides， the rapid and dynamic clustering algorithm well groups the dispersive learners to satisfy the efficient recommendation request and communication needs.

Key words: e-learning; clustering analysis; personalized learning; PCA; LDA

1 概述

隨著計算機技術的飛速發展和英特網的廣泛應用，遠程教育(E-Learning)成為現代教育不可或缺的一部分，廣泛應用于培訓、高等教育、終身教育等領域。它突破了傳統意義上的教學方式，不再受時間和空間的物理限制，從而為更多的人提供了受教育及獲取知識的機會。然而，在遠程教育環境中，教師資源往往很少而學員數目龐大且個體差異懸殊，授課教師對學員進行一對一的指導顯得力不從心，而全盤指導又缺乏針對性。

聚類分析作為一種基于相似性的子群劃分方法，可先將學員進行分類，再由授課教師針對不同的簇類分別進行指導，可有效地解決教師的工作量和缺乏針對性之間的矛盾。如F.Yang[1]提出了一種基于海布學習法則的動態群體劃分方法，以將有類似特征的學員組織在一起來提高推薦精確度。

在一般的聚類分析方法中，其核心步驟主要是: 先定義一個合適的度量，然后計算任意兩個樣本之間的距離[6]。當兩個樣本之間的距離小于某個閾值d0時，則稱它們相似，將其劃分到同一簇類。聚類分析具體過程如圖1所示。

在聚類過程中，一方面，為度量樣本間的相似性會采用如Euclid距離、Man-hattan距離、Minkowski距離等。如果將距離的計算過程看成黑盒的話，那么這一過程就是從多維空間到一維空間的過程。另外一方面，距離閾值d0的值該如何確定也是一件困難的事，且在很大程度上決定了簇類的數量和大小。例如，KMEANS方法[5]就是通過計算剩余樣本與質心的歐式距離來不斷地調整質心，直至質心點穩定來得到樣本集的劃分。在這過程中，判斷樣本屬于哪一簇類完全取決于與各個質心的最短距離，換種角度來說，這里的最短距離便是一種變相的閾值d0，而質心的調整過程就是對d0值的最終確定。雖然KMEANS也能夠達到很好的計算效率，但是它對初始質心和數據的順序比較敏感，而且并不適用于劃分任意形狀的數據[6]。

從以上兩方面來考慮，我們試圖先降維做特征提取，而后再進行比較，得到各個簇類。然而，降維必定會導致信息丟失[4]。因此，如何在這過程中保存住最大的信息量以得到合理的簇類成了目前比較關注的問題。比較常用的特征提取方法主要有兩種，分別是PCA[2]和LDA[4]。PCA(主成份分析)基于這樣一種思想:方差最大的方向包含最多的類間信息，而LDA(線性鑒別分析)則是在最大化類間信息的同時最小化類內信息，并最大化兩者之比。另外也存在一些映射方法，如填充曲線，其中比較常見且實用的是一種稱為Hilbert空間曲線的填充方法，它將高維空間中相似的數據映射到一維數值中的鄰近區域中，以保持空間對象的鄰接關系，它具有良好的聚集性[3]。然而，這些具有較高復雜度的方法在動態、多變的環境中并無優勢。

本文根據課程架構，建立個性化推薦模型，并提出了一種適用于該模型的基于逐層降維的聚類分析方法。該方法通過構建基于由知識點形成的知識樹的課程架構，并在此結構上進行逐層計算得到根結點的數值，最后根據該一維數值獲得最后的簇類劃分進行適應性的資源推薦，以達到提高學習效率的目的。

2 個性化推薦模型

2.1 基于知識點的課程架構

本文依據領域專家對課程內容的劃分方案將課程中的知識以知識點(knowledge points)為單位劃分成不同的單元。根據劃分粒度不同，把課程分成不同的層次，以“知識樹”的形式來組織課程，并將其作為課程的導航，使授課老師能夠清晰地掌握學習者對不同模塊的掌握情況。如圖所示的是《數據結構》課程的部分知識樹的樣例。其各對父子結點間的連線形成了滿足傳遞性的偏序關系，稱之為包含關系。如連線就表示，Insertion Sort是Sorting的一部分。

學習資源作為對學習者發揮實效的本體，文中將其與特定的知識點相關聯，該知識點可以是復合知識點也可以是葉子知識點，以形成以知識樹為導引的知識組織結構。

2.2 個性化推薦模型

我們構建的推薦模型如圖3所示，依據整個分析流程將模型分為三個功能模塊，分別是個性化學習模塊、動態分析模塊和推薦模塊。其中，學習模塊的主要作用是為學員提供一個個性化學習和交流的視窗，并獲取學員最新信息以更新至數據庫中;動態分析模塊主要對學員學習后的數據進行即時的動態分析，得到所需的分類結果并實時地表示出來;推薦模塊用于教師根據分析得到的簇類進行基于各個細節的學習資源的推薦。此外，考慮到某些知識點的特殊性，系統中授課教師亦可定制聚類屬性的范圍。

在這個模型中，教師可以對不同簇類進行基于知識點或者相關復合知識點上的適應性資源推薦和個性化試題的定制，亦可以根據自定義的權值生成新的簇類劃分后再進行相關指導。

3 基于層次降維的聚類分析方法

本文提出的基于層次降維的聚類分析方法的核心思想是通過逐層降維將多維數據的距離計算分成不同的部分分別計算，最后將該距離映射到一維數值上進行排序、劃分。

為了更好的說明層次的概念，我們做如下說明。假設對于樣本集Χ中任意樣本x都可以由n個屬性來表述，則定義集合A={a1，a2，…，an}，A中包含了樣本相應的所有屬性特征，而任意元素ai∈A表示樣本的一個屬性。屬性間滿足下列條件:1)屬性間相互獨立，2)屬性間沒有公共的特征部分，分別稱之為屬性的獨立性和互不相交性，否則可以將此屬性進行再度劃分，分成更為細節的兩個或兩個以上的屬性。該樣本集Χ中的所有樣本均可由n維向量α=(α1，α2，…，αn)來描述，其中數值αi∈R表示樣本屬性ai的顯著程度。易見，n維空間中必包含了所有樣本集Χ中的所有樣本。

再次，我們定義集合使每個集合中只包含A中的一個屬性，令A1={a1}， A2={a2}，…， An={an}。顯然，任意子集合Ai A(i =1:n)都處于同一層次即A層，稱之為最底層。由屬性的性質可知，對于任意屬性集合Ai必隸屬于某個新定義的相當或者更大的子集合(存在性)。為使這些新生成的子集合Bj之間保持屬性間的原始特性(獨立性和互不相交性)，則任意集合Ai須根據某一關系只歸屬于某個子集合Bj，即Ai Bj(唯一性)。只有滿足了這兩個性質的屬性的前提下，才能使用本文的方法。那么所有新生成的子集合可構成一個新的屬性定義(在本應用中稱之為復合知識點)組來描述樣本。且易知，Bj滿足:

其中k≤n。那么，樣本集Χ中的數據可由k維向量來描述。從層次角度來說，所有的屬性集合Bi處于同一層次B層。這里，我們稱B層為A層的上一層，而將其從A層到B層的變化過程定義為一次“向上歸約合成”。若k

3.1 拓撲結構的構建

算法的第一步是如上作自底向上歸約合成即從最底層逐步到達最頂層的形成過程。此過程同生成樹的過程一般。得到的結果可以形象地由圖2所示的知識樹結構來描述。

如圖2所示，結點每上一層都使得用于描述樣本屬性特征的維數得到縮減。從子結點到父結點的求值過程便是一次從多維到一維的映射過程:

，其中w為權重。

在各個不同層次的不同結點做適用于本屬性集合特性的某些行為，如本文中所應用的基于知識點的推薦，又如當前盛行的基于職工等級的管理都是非常可行的。此外，任一結點數據的變動，只需計算該子樹相關部分的數值，而不需要重新計算來獲得整棵“知識樹”上的所有數值，減少了計算量。

3.2 權值確定

算法的第二步是確定結點連線權值，即子集合對應于其上層子集合的隸屬度。權值分為兩部分，分別為定值和變化量，其中定值部分采用領域專家制定經驗值的方法，變化量則是依據教學大綱做適度的調整。這種確定方式比起由神經網絡訓練相比，主要是免去了訓練樣本的采集、噪聲和不收斂等問題。

3.3 簇類形成

算法第三步是得到最后的劃分結果。定好權值后依次向上對子結點做加權平均求其父結點數值的運算，直至得到根結點的值。然后，將其作為劃分的依據，進行排序再根據需求劃分成最終所需要的結果。對于學員在簇類中的分布，一般使得學員的人數在各不同水平簇類中從低到高形成正態分布或者平均地劃分使得各個簇類中的樣本數相當。我們采用了符合現實情況的前者。

4 實驗及分析

4.1 系統實現

我們將本系統應用于上海交通大學網絡教育學院的《數據結構》課程。各個模塊如圖4所示:個性化學習模塊中，學員通過瀏覽器便可隨時隨地進行學習與交流;分析模塊中，學員經過一段時間的學習，其分布會逐漸向學習水平較高的簇類轉化;推薦模塊中，授課教師可以方便地進行基于知識樹的推薦。

4.2 結果比較

為了說明本文提到的算法的可行性，定義如下度量簇類內聚集性(1)和度量社區整體聚類效果(2)的式子，其中||Ci||表示簇類Ci內的樣本數，||C||表示簇類個數，Savg指社區的整體平均水平。Davg越小說明簇類空間聚集性越好;E值越小，說明該算法形成的聚類所達到的效果較好。

實驗中，我們將學員總數227人隨機地分成4個人數相當的部分，分別應用了修改后的PCA、LDA、Hilbert填充曲線和本文中提出的算法，并進行比較。我們發現，雖然從Davg的比較來看，LDA與Hilbert較優，但是應用逐層降維聚類分析方法一段時間后社區可以得到較好的Savg值。

半個學年的不同時段內4種方法的結果E如圖5所示。圖中表明，該推薦方法有效地提高整個社區對知識的掌握水平;教師做出的符合各個簇類特性的推薦，促使達到了更高的學習效率。并從另一種角度說明了簇類中的成員對象之間達到了某種較好的相似性。利用社區中的此劃分使得處于同簇類的學員之間能夠進行更為有效的相互交流、相互推薦、相互促進。

5 結束語

本文的方法簡單、復雜度低且易實現，能很好地應用于現實的遠程教育環境。該方法將具有學習水平相當的學員聚集在一起，進行更為有效的學習指導，并給學員提供了互相得益的小群體以相互交流、相互促進，從而達到提高學員學習效率、減輕授課教師工作量的目的。實驗結果表明，這種方法可以將學員迅速地組織在一起，滿足了各自的需求，并且能夠使得授課教師能迅速掌握學員學習的整體概況以調整教學計劃。

在接下來的研究中，我們不僅僅要關注算法的改進，比如在應用算法之前，是否需要對屬性間進行相關性分析，去掉部分相關度比較高的冗余數據以提高分析速度和聚類質量。我們還應使整個系統更具智能性、交互性。

參考文獻:

[1] Yang F.Analysis， Design and Implementation of Personalized Recommendation Algorithms Supporting Self-organized Communities[D].Hagen:Faculty of Math-ematics and Information Technology FernUniversitaet at Hagen，2005.

[2] Jolliffe I T.Principal Component Analysis[M].Springer-Verlag，1986.

[3] Moon B，Jagadish H V，Faloutsos C，et al.Analysis of the Clustering Properties of the Hilbert Space-Filling Curve[J].IEEE Transactions on Knowledge and Data Engineering，2001，13(1):124.

[4] Wang Xuechuan，Paliwal K K.Feature Extraction and Dimensionality Reduction Algorithms and Their Applications in Vowel Recognition[J].Pattern Recognition，2003，36:2429.

[5] Scholkopf B，Smola A，Muller K R.Nonlinear Component Analysis as a Kernel Eigenvalue Problem[J].Neural Computation，1998，10(5):1299.

[6] 行小帥，焦李成.數據挖掘的聚類方法[J].電路與系統學報，2003，8(1):59.