基于譜聚類協(xié)作學(xué)習(xí)分組的研究

鄧廣華　李文彪

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

關(guān)鍵詞：協(xié)作學(xué)習(xí) 譜聚類 向量空間 余弦夾角

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

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

1 興趣模型與余弦夾角

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

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

2 基于譜聚類算法分組

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

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

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

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

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

3 結(jié)語

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

參考文獻

[1] ZPOLATE，AKARGB.學(xué)習(xí)風(fēng)格對學(xué)習(xí)系統(tǒng)的自動檢測[J].計算機與教育，2009（2）：355-367.

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

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