基于譜聚類協作學習分組的研究

鄧廣華　李文彪

摘 要：協作學習系統構建了一個協作學習的環境，為教師與學生、學生與學生進行在線討論、協作與交流提供了一個良好的平臺。在線學習過程進行科學的分組，把具有相似興趣的用戶分到一組進行專題或自由討論提高學習效率。用譜聚類算法進行分組，用戶的興趣模型通過向量空間創建，用余弦夾角公式計算相似程度。

關鍵詞：協作學習 譜聚類 向量空間 余弦夾角

中圖分類號：G420 文獻標識碼：A 文章編號：1672-3791（2016）06（b）-0167-02

協作學習系統可以在用戶自主學習過程中根據用戶的興趣主動推薦學習資源給用戶進行在線學習，滿足個性化學習[1]需要，實現“因材施教”的教育理念；同時可以根據各自的興趣，通過聚類算法實現自動分組，使興趣相同的用戶組成一個學習小組，實現協作學習，從而有效提高學習過程中的主動參與性以及團隊合作精神和溝通交流能力。為了更準確的把興趣相似的學生分在同一組，該文通過改進譜聚類算法對在線學習用戶進行自動分組，興趣模型通過向量空間建模，創建為20維。用余弦夾角公式構建相似矩陣，再通過譜聚類NJW[2]算法進行聚類分組，自動確定用戶集劃分為幾個組，以實現協作學習。

1 興趣模型與余弦夾角

學生興趣模型同樣采用向量空間表示法表示，如：

Student（ui）={（ki1，wi1），（ki2，wi2），...，（kih，wih）}，其中ui為學生i，kih為表示學生興趣的關鍵詞，wih為學生對關鍵詞kih的感興趣的程度。假設學生興趣模型總數為n，我們構造一個n×n的距離矩陣S，S[i][j]的值表示學生i和學生j的距離權值，學生興趣模型之間的距離采用余弦夾角值的倒數計算：

2 基于譜聚類算法分組

譜聚類算法要先構建相似矩陣， 相似矩陣體現了一組量化評估數據集之間的相對相似性。相似矩陣通常可以使用歐式距離、余弦相似度、高斯核函數來構建，該文采用高斯核函數進行構建。因為高斯核函數構建的相似矩陣做譜聚類分析的效果較好[3]。

按照公式（3）計算出興趣相似程度值，進而構建譜聚類算法的相似矩陣W。該文使用Ng，Jordan在2001年提出的NJW算法[2]。相似矩陣W構建好后選取規范拉氏矩陣L=DWD做特征值分解，D為度矩陣，是對角矩陣，D等于相似矩陣W的第i行各元素的累加值，其中i（1，n）。分解出拉普拉斯矩陣L的特征值和對應的特征向量，特征值從高到低排序，然后選取前K個特征值對應的特征向量，每個特征向量作為一列，構成矩陣H，再對矩陣H的每一行進行歸一化處理后得到矩陣Y，，構成n×k的矩陣，其中n為原數據點數（待分組的用戶數），這樣把矩陣Y的每一行看成是空間Rk上的一個新點，它與原數據點一 一對應著，然后對空間Rk進行普通聚類處理，該文使用K-means聚類算法對空間Rk新數據點集進行聚類，得到k個聚類，即分成k組。

譜聚類的類目選取直接影響聚類效果，得到特征值后對他從大到小排序，選取拉氏矩陣L的前k個最大特征值就是聚類數目。第k個的特征值與第k+1個的特征值有個跳躍即譜隙（eigen gap），當樣本空間中所有數據點劃分成K類時的聚類效果越好那么第k個特征值與第K+1個特征值的跳躍譜隙就越大這種關系。該文采用Azran和Ghahramani于2006年提出的根據M步隨機游走后的概率矩陣PM的eigen gap[3]來確定K值，它更接近真實的聚類數目。基于譜聚類NJW算法對學生進行分組算法如下：

算法的輸入為：n個學生興趣模型；輸出為：j個組；

（1）對于待分組的學生數據集X={xi}，其中n為總學生數，通過公式（3）高斯核函數計算出學生之間的興趣相似度，得到一個n×n的相似矩陣W，并由相似矩陣W構造Laplician矩陣L。（2）通過eigen gap方法確定K值。（3）計算矩陣L的前K個特征值及其所對應的特征向量，以每個特征向量作為一列構建n×k的矩陣H=[h1，h2，…，hk]Rn×k。（4）將H向量中的行向量做歸一化處理得到Y矩陣，即。（5）把矩陣Y中的每一行看成是Rk空間上的數據點，這些數據點與原數據點一 一對應做K-means聚類，得到k個聚類。（6）假如矩陣Y的第i行屬于K-means聚類的第j類，那么原數據點也歸為第j類，如果沒有完成轉到Step5，直到全部數據歸類完成為止。

3 結語

興趣模型通過余弦夾角公式計算出的是0～1之間的值，模型之間越相似就越接近1，使用這個值的倒數值作為譜圖的權重值，興趣模型之間越相似就靠得越近，從而很好的創建相似矩陣。興趣模型的元素是鍵值對，選用余弦夾角比較合適，該文實現了通過高斯核函數構建相似矩陣后譜聚類算法對鍵值對向量空間模型的聚類分組，實現協作學習。

參考文獻

[1] ZPOLATE，AKARGB.學習風格對學習系統的自動檢測[J].計算機與教育，2009（2）：355-367.

[2] Ng A.Y.，Jordan M.I.，Weiss Y.譜聚類算法分析[Z].2001：849-856.

[3] Azran A.，Ghahramani Z.自動多尺度數據聚類的譜方法[Z].IEEE計算機學會計算機視覺與模式識別程序，2006：190-197.