基于聚類和梯度選擇的網(wǎng)絡(luò)協(xié)作學(xué)習(xí)分組算法

馬艷云，袁 健

(上海理工大學(xué) 光電信息與計算機(jī)工程學(xué)院，上海 200093)

?

基于聚類和梯度選擇的網(wǎng)絡(luò)協(xié)作學(xué)習(xí)分組算法

馬艷云，袁 健

(上海理工大學(xué) 光電信息與計算機(jī)工程學(xué)院，上海 200093)

基于網(wǎng)絡(luò)協(xié)作學(xué)習(xí)具備便捷、海量資源共享和不受時空約束的優(yōu)勢，但其學(xué)習(xí)效果易受學(xué)習(xí)者分組的影響；分組越科學(xué)合理，整體學(xué)習(xí)效果則越理想，反之亦然。文中根據(jù)網(wǎng)絡(luò)協(xié)作學(xué)習(xí)者的個性化特征和協(xié)作特征，在引入團(tuán)隊(duì)協(xié)作學(xué)習(xí)量表解決學(xué)生協(xié)作能力判斷的前提下，提出基于學(xué)習(xí)者特征聚類和協(xié)作特征梯度選擇的GSDBK-means分組算法對學(xué)習(xí)者進(jìn)行分組，以期達(dá)到提高網(wǎng)絡(luò)協(xié)作學(xué)習(xí)效果的目的。經(jīng)實(shí)驗(yàn)證明，GSDBK-means分組算法較于其他分組策略能產(chǎn)生更科學(xué)合理的分組結(jié)果，從而取得更好的學(xué)習(xí)效果。

分組算法；協(xié)作學(xué)習(xí)；聚類；梯度選擇

伴隨著網(wǎng)絡(luò)學(xué)習(xí)和協(xié)作學(xué)習(xí)的發(fā)展，網(wǎng)絡(luò)協(xié)作學(xué)習(xí)成為一種有效的學(xué)習(xí)模式[1]，其既可針對在校學(xué)生進(jìn)行基于網(wǎng)絡(luò)的協(xié)作學(xué)習(xí)，又可使處于不同年齡、時間和地點(diǎn)的人們開展協(xié)作學(xué)習(xí)成為可能。通過在網(wǎng)絡(luò)上進(jìn)行協(xié)作學(xué)習(xí)，解決了傳統(tǒng)網(wǎng)絡(luò)學(xué)習(xí)產(chǎn)生的“孤獨(dú)”學(xué)習(xí)者的問題，也解決了課堂協(xié)作學(xué)習(xí)找不到合適小組成員和資源的窘境。由于對協(xié)作前的準(zhǔn)備——分組缺乏有效的技術(shù)支持[2]，而協(xié)作學(xué)習(xí)的核心是分組，這意味著協(xié)作分組的優(yōu)劣對于協(xié)作學(xué)習(xí)起著關(guān)鍵性的作用。

1 研究現(xiàn)狀

目前網(wǎng)絡(luò)協(xié)作學(xué)習(xí)分組主要在相關(guān)理論上進(jìn)行研究，對于網(wǎng)絡(luò)協(xié)作學(xué)習(xí)分組算法的研究不多。胡慧[3]等基于蟻群算法根據(jù)學(xué)習(xí)者個性化特征進(jìn)行同質(zhì)分組；但蟻群算法搜索時間過長，大部分的時間都耗費(fèi)在算法中解的構(gòu)造，求解時間有待進(jìn)一步的優(yōu)化；Chen Long[4]等基于遺傳算法根據(jù)學(xué)習(xí)者特征進(jìn)行異質(zhì)分組；遺傳算法易造成局部最優(yōu)，當(dāng)學(xué)習(xí)者特征維數(shù)較多時難以進(jìn)行處理和優(yōu)化，算法的時間性能也得不到保證。劉均[5]采用層次聚類方法 AGNES根據(jù)學(xué)習(xí)者認(rèn)知水平進(jìn)行同質(zhì)分組。層次聚類方法相對于K-means算法，層次聚類簇的數(shù)目難以確定。唐杰[6]根據(jù)學(xué)習(xí)者特征采用K-means算法進(jìn)行目標(biāo)聚類、異質(zhì)聚類、差異性聚類對于學(xué)習(xí)者進(jìn)行異質(zhì)分組；K-means算法初始中心點(diǎn)的選取對于算法時間性能具有較大影響。

本文基于協(xié)作學(xué)習(xí)理論[7]、建構(gòu)主義理論[8]，加入?yún)f(xié)作學(xué)習(xí)的群體特征，利用改進(jìn)的聚類算法結(jié)合梯度選擇提出了基于聚類和梯度選擇的網(wǎng)絡(luò)協(xié)作學(xué)習(xí)分組算法(Density-Based Improved K-Means With Gradient Select Grouping Algorithm， GSDBK-means)。通過基于密度選取聚類中心點(diǎn)的方法改進(jìn)K-means算法，對于學(xué)習(xí)者的特征屬性進(jìn)行聚類，再引入團(tuán)隊(duì)學(xué)習(xí)能力量表[9]判斷學(xué)習(xí)者的協(xié)作能力，解決首次協(xié)作學(xué)習(xí)成員群體特征屬性值為0的情況。最后基于梯度選擇根據(jù)學(xué)習(xí)者的協(xié)作能力對于聚類后的每個簇進(jìn)行分組。

2 網(wǎng)絡(luò)協(xié)作學(xué)習(xí)分組模型

在基于網(wǎng)絡(luò)協(xié)作學(xué)習(xí)的環(huán)境中，分組模型是為用戶提供更好服務(wù)的強(qiáng)有力機(jī)制[10]，如圖1所示，學(xué)習(xí)者要進(jìn)行合適的分組，需要獲得學(xué)習(xí)者重要的特征參數(shù)。根據(jù)分組模型，學(xué)習(xí)者在注冊時將個人基本信息存入學(xué)習(xí)者檔案,通過登錄操作進(jìn)一步完善相關(guān)信息存入學(xué)習(xí)者檔案中。本文采用學(xué)習(xí)偏好、知識水平、認(rèn)知水平作為學(xué)生的個性化特征，協(xié)作能力作為協(xié)作特征在學(xué)生登錄后進(jìn)行特征測量。對于協(xié)作特征采用學(xué)生自測和伙伴互測兩種方式進(jìn)行測量。所有的個性化特征和協(xié)作特征均將存儲在學(xué)習(xí)者特征庫中，作為網(wǎng)絡(luò)協(xié)作學(xué)習(xí)分組的依據(jù)。

圖1 網(wǎng)絡(luò)協(xié)作學(xué)習(xí)分組模型

根據(jù)學(xué)習(xí)者的特征量化值，將N個學(xué)習(xí)者基于學(xué)習(xí)者特征相似性和協(xié)作能力差異性進(jìn)行分組，使其既滿足分組原則又能保證小組內(nèi)人數(shù)均勻[11]。本文所需的相關(guān)變量及計算方式如下：

變量 1對象間距離 dist(i,j)。對象之間的距離dist(i,j)使用歐式距離來表示

(1)

式中，d表示數(shù)據(jù)的緯度；ik、jk表示學(xué)習(xí)者i，j對應(yīng)的第K個特征；

變量 2 鄰域半徑Eps。定義對象的鄰域半徑Eps

(2)

其中，i和j表示對象；d表示學(xué)習(xí)者的特征維度；n表示學(xué)習(xí)者的個數(shù)；

變量 3Eps鄰域NEps(p)。數(shù)據(jù)對象p的Eps鄰域NEps(p)定義為

NEps(p)={q∈S|dist(p,q)≤Eps}

(3)

其中 ,S∈Rd為d維實(shí)空間上的數(shù)據(jù)集 , dist(p,q) 表示S中對象p和q之間的距離；

變量 4鄰域密度ρ(p)。為對象p的鄰域NEps(p)內(nèi)所包含的對象個數(shù)，即ρ(p)=|NEps(p)|；

變量 6核心點(diǎn)Mp。對于任意對象p∈S,在P的鄰域NEps(p)內(nèi)，Mp定義為

(4)

3 GSDBK-means分組算法

3.1 數(shù)據(jù)標(biāo)準(zhǔn)化

3.2 算法描述及流程圖

網(wǎng)絡(luò)協(xié)作學(xué)習(xí)強(qiáng)調(diào)的是通過網(wǎng)絡(luò)讓學(xué)習(xí)者以小組形式參與學(xué)習(xí)，最大化個人學(xué)習(xí)成果。如何生成高效而有意義的協(xié)作小組，是網(wǎng)絡(luò)協(xié)作學(xué)習(xí)的關(guān)鍵。本文考慮將學(xué)習(xí)者個性化特征相似的學(xué)習(xí)者分在一個小組，使其對學(xué)習(xí)有共同的興趣，讓協(xié)作能力相異的學(xué)習(xí)者分在一個小組，確保小組成員可互幫互助，增加小組凝聚力。根據(jù)Feichtner和Davis的調(diào)查中顯示，小組成員在4～7個人時為小組的最佳學(xué)習(xí)人數(shù)[14]。本文采用選擇對象鄰域高密度[15]的學(xué)習(xí)者作為K-means的中心點(diǎn)來改進(jìn)學(xué)習(xí)者基于個性化特征相似聚類，對于聚類后的每個簇基于“組間同質(zhì)，組內(nèi)異質(zhì)”，即組間協(xié)作能力相似，組內(nèi)協(xié)作能力有差異的梯度選擇算法進(jìn)行分組。具體GSDBK-means分組算法和分組流程，由圖2進(jìn)行表示。GSDBK-means分組算法步驟：

步驟1 初始化參數(shù)。對于n個對象，p∈s,s={s1,s2,…,sn}，分別通過標(biāo)準(zhǔn)化公式將數(shù)據(jù)量化，設(shè)置聚類的最大迭代次數(shù)time；

步驟2 計算對象的鄰域密度。根據(jù)對象的個性化特征按照式(2)計算聚類對象的鄰域半徑Eps，以每個對象為中心，Eps為鄰域半徑，得到每個對象的NEps(p)，以及每個鄰域內(nèi)的對象個數(shù)|NEps(p)|，即對象在這個鄰域內(nèi)的密度ρ(p)；

步驟3 計算密度核心點(diǎn)。根據(jù)式(4)計算對象的M點(diǎn)，并將這一鄰域內(nèi)的對象全部從待聚類的對象中全部剔除。對剩余的對象按照式(4)進(jìn)行迭代計算，直至得到k個核心點(diǎn)為止；

步驟4 選取初始中心點(diǎn)。根據(jù)密度法計算出的k個核心點(diǎn)，作為K-means聚類的初始聚類中心；

步驟5 計算個性化特征相似度。根據(jù)(1)式計算每個對象到聚類中心的距離dist(i,p)，將對象分到與其距離最小的簇中；

步驟7 按照協(xié)作特征進(jìn)行分層。分別計算每個簇的大小size，并按照協(xié)作能力進(jìn)行排序，再根據(jù)0～size/n,(size/n+1)～size/n×(n-1),size/n×(n-1)～size分成高、中、低3個梯度；

步驟8 根據(jù)協(xié)作特征按照梯度選擇進(jìn)行分組。根據(jù)協(xié)作能力基本呈現(xiàn)正態(tài)分布的排列情況，從高、中、低3個梯度的對象中按照有序選取的方法對應(yīng)順序選取1，n-2，1共n個對象組成小組；當(dāng)某個聚類結(jié)果總?cè)藬?shù)不是n的倍數(shù)時，則將剩余的對象加入其最適合的小組中。

圖2 分組算法流程圖

4 實(shí)驗(yàn)設(shè)計與分析

4.1 實(shí)驗(yàn)設(shè)置

為了證實(shí)本文分組算法的有效性，對于上海理工大學(xué)英語學(xué)科一位老師所帶的4個平行班級200名大一新生設(shè)計基于不同分組策略進(jìn)行網(wǎng)上輔助學(xué)習(xí)的對比實(shí)驗(yàn),并以他們的期末成績作為學(xué)習(xí)效果評判依據(jù)。首先，對于第1個班級采取不分組的方式進(jìn)行學(xué)習(xí)，第2個班級采取學(xué)生隨機(jī)分組的方式進(jìn)行學(xué)習(xí)，第3個班級基于本文所提到的學(xué)生個性化特征(學(xué)習(xí)偏好、知識水平、認(rèn)知水平)進(jìn)行個性化分組，最后一個班級，在考慮學(xué)生個性化特征的基礎(chǔ)上利用團(tuán)隊(duì)學(xué)習(xí)能力量表，加上學(xué)生的協(xié)作特征——協(xié)作能力，基于GSDBK-means進(jìn)行分組學(xué)習(xí)。

其次，設(shè)置小組人數(shù)為4人。第3個小組采取基于密度改進(jìn)的K-means進(jìn)行分組，設(shè)置聚類簇數(shù)K=4,迭代次數(shù)為1 000，聚類后從每個聚類中隨機(jī)抽取4人組成一組；第4個小組同樣設(shè)置聚類簇數(shù)K=4,迭代次數(shù)為1 000。

4.2 實(shí)驗(yàn)分析

表1 采取不同分組策略的學(xué)習(xí)效果對比

從表1中可看出，基于分組的協(xié)作學(xué)習(xí)效率相較于不分組的學(xué)習(xí)效率高；對比隨機(jī)分組和個性化分組，增加協(xié)作特征的GSDBK-means分組學(xué)習(xí)的學(xué)生成績平均值 增幅較大，表征組內(nèi)學(xué)生成績分散程度的 大幅度降低，這表示基于GSDBK-means分組的協(xié)作學(xué)習(xí)能進(jìn)一步的提高學(xué)生成績的平均水平，縮小學(xué)生之間的差距，使學(xué)生之間協(xié)作互助，知識共享的高效學(xué)習(xí)得到了較好的體現(xiàn)。

5 結(jié)束語

通過分析學(xué)習(xí)者協(xié)作學(xué)習(xí)的各要素，建立了網(wǎng)絡(luò)協(xié)作學(xué)習(xí)的分組模型。在此基礎(chǔ)上，通過GSDBK-means算法將學(xué)習(xí)者個人特征相似、協(xié)作能力有差異的學(xué)生組成一個協(xié)作小組，同時又保證了各小組間差異較小，便于組間競爭，這便是符合當(dāng)下流行的“組間同質(zhì)，組內(nèi)異質(zhì)”分組原則。最后根據(jù)英語學(xué)科學(xué)生分組對比學(xué)習(xí)，證明將學(xué)習(xí)偏好、知識水平、認(rèn)知能力相近，協(xié)作能力相異的學(xué)習(xí)者分在一組能促進(jìn)學(xué)習(xí)者之間更充分、有效地交互進(jìn)而提高學(xué)習(xí)效率。針對不同的教學(xué)目標(biāo)，設(shè)計者也可考慮不同的學(xué)習(xí)者特征。本文僅對網(wǎng)絡(luò)協(xié)作學(xué)習(xí)提供智能化分組奠定了基礎(chǔ)，對于網(wǎng)絡(luò)協(xié)作學(xué)習(xí)的學(xué)習(xí)者流動性等特性還需對分組進(jìn)一步改進(jìn)。

[1] 王永固,李克東.主題式網(wǎng)絡(luò)協(xié)作學(xué)習(xí)模型及其案例研究[J].中國電化教育,2008 (2):46-51.

[2] Li Li,Luo Xiangfeng.Automatic student grouping method for foreign language learning[C].Beijing:10th International Conference on Semantics、Knowledge and Grids (SKG),2014.

[3] 胡慧.基于改進(jìn)蟻群算法的協(xié)作學(xué)習(xí)分組研究[J].計算機(jī)工程與應(yīng)用,2014,50(13):137-141.

[4] Chen Long,Yang Qinghong.A group division method based on collaborative learning elements[C].Changsha:26th Chinese Control and Decision Conference,2014.

[5] 劉均,李人厚,鄭慶華.一種面向個性化協(xié)同學(xué)習(xí)的任務(wù)生成方法[J].軟件學(xué)報,2006, 17(1):79-85.

[6] 唐杰,李浩君,邱飛岳.mCSCL環(huán)境下協(xié)作分組的伙伴模型研究[J].中國遠(yuǎn)程教育:綜合版,2012(3):48-51.

[7] 琳達(dá)·哈拉西姆,肖俊洪.協(xié)作學(xué)習(xí)理論與實(shí)踐——在線教育質(zhì)量的根本保證[J].中國遠(yuǎn)程教育:綜合版,2015(8):5-16.

[8] 李靜,趙偉.基于建構(gòu)主義學(xué)習(xí)理論基礎(chǔ)上的現(xiàn)代遠(yuǎn)程教育[J].電化教育研究, 2003(5):37-40.

[9] 陳國權(quán).復(fù)雜變化環(huán)境下人的學(xué)習(xí)能力:概念、模型、測量及影響[J].中國管理科學(xué),2008,16(1):147-157.

[10] 劉菊香.基于模糊理論的網(wǎng)上協(xié)作學(xué)習(xí)學(xué)生分組系統(tǒng)的研究與實(shí)現(xiàn)[D].上海:華東師范大學(xué),2006.

[11] Pang Yulei,Raymond Mugno,Xue Xiaozhen,et al.Constructing collab-orative learning groups with maximum diversity requirements[C].Hualien: IEEE 15th International Conference on Advanced Learning Technologies,2014.

[12] 陳林林.移動學(xué)習(xí)中學(xué)習(xí)者偏好模型研究[D].武漢:華中師范大學(xué),2013.

[13] 孫家振,朱玉全,周李威,等.基于模糊規(guī)則的學(xué)習(xí)者認(rèn)知水平估算方法[J].計算機(jī)應(yīng)用研究,2014,31(9):2652-2655.

[14] 李潔.CSCL中協(xié)作小組分組系統(tǒng)的設(shè)計與開發(fā)研究[D].廣州:華南師范大學(xué),2005.

[15] Xia L N,Jing J W.SA-DBSCAN:A self-adaptive density-based clustering algorithm[J].Journal of the Graduate School of the Chinese Academy of Sciences,2009,26(4):530-538.

Based on GSDBK-means Grouping Algorithm Reseach for Networked Collaborative Learning

MA Yanyun，YUAN Jian

(School of Optical-Electrical and Computer Engineering, University of Shanghai for Science and Technology, Shanghai 200093, China)

Based on network collaborative learning with convenient, massive resources sharing and not subject to the restriction of time and space advantage, but its learning results susceptible to study the impact of packet; packet more scientific and reasonable, learning effect is more ideal, and vice versa. This paper according to the collaborative network learners personalized features and the characteristics of collaboration, in the introduction of team cooperation learning scale to solve student’s cooperative ability judgment premise proposed to learners in grouping learning based on gradient feature clustering and collaborative feature selection GSDBK-means grouping algorithm, in order to improve the network collaborative learning effect. The experimental results show that the GSDBK-means grouping algorithm can produce more scientific and reasonable grouping results compared with other grouping strategies, which can obtain better learning results.

grouping algorithm; collaborative learning; clustering; gradient selection

10.16180/j.cnki.issn1007-7820.2016.12.025

2016- 02- 05

馬艷云(1992-)，女，碩士研究生。研究方向：網(wǎng)絡(luò)學(xué)習(xí)。袁健(1971-)，女，副教授，碩士生導(dǎo)師。研究方向：云計算安全與大數(shù)據(jù)管理等。

TP301.6

A

1007-7820(2016)12-089-04