馬艷云，袁 健

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

?

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

馬艷云，袁 健

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

基于網(wǎng)絡(luò)協(xié)作學(xué)習(xí)具備便捷、海量資源共享和不受時(shí)空約束的優(yōu)勢(shì)，但其學(xué)習(xí)效果易受學(xué)習(xí)者分組的影響；分組越科學(xué)合理，整體學(xué)習(xí)效果則越理想，反之亦然。文中根據(jù)網(wǎng)絡(luò)協(xié)作學(xué)習(xí)者的個(gè)性化特征和協(xié)作特征，在引入團(tuán)隊(duì)協(xié)作學(xué)習(xí)量表解決學(xué)生協(xié)作能力判斷的前提下，提出基于學(xué)習(xí)者特征聚類和協(xié)作特征梯度選擇的GSDBK-means分組算法對(duì)學(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]，其既可針對(duì)在校學(xué)生進(jìn)行基于網(wǎng)絡(luò)的協(xié)作學(xué)習(xí)，又可使處于不同年齡、時(shí)間和地點(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í)找不到合適小組成員和資源的窘境。由于對(duì)協(xié)作前的準(zhǔn)備——分組缺乏有效的技術(shù)支持[2]，而協(xié)作學(xué)習(xí)的核心是分組，這意味著協(xié)作分組的優(yōu)劣對(duì)于協(xié)作學(xué)習(xí)起著關(guān)鍵性的作用。

1 研究現(xiàn)狀

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

本文基于協(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算法，對(duì)于學(xué)習(xí)者的特征屬性進(jìn)行聚類，再引入團(tuán)隊(duì)學(xué)習(xí)能力量表[9]判斷學(xué)習(xí)者的協(xié)作能力，解決首次協(xié)作學(xué)習(xí)成員群體特征屬性值為0的情況。最后基于梯度選擇根據(jù)學(xué)習(xí)者的協(xié)作能力對(duì)于聚類后的每個(gè)簇進(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í)者在注冊(cè)時(shí)將個(gè)人基本信息存入學(xué)習(xí)者檔案,通過登錄操作進(jìn)一步完善相關(guān)信息存入學(xué)習(xí)者檔案中。本文采用學(xué)習(xí)偏好、知識(shí)水平、認(rèn)知水平作為學(xué)生的個(gè)性化特征，協(xié)作能力作為協(xié)作特征在學(xué)生登錄后進(jìn)行特征測(cè)量。對(duì)于協(xié)作特征采用學(xué)生自測(cè)和伙伴互測(cè)兩種方式進(jìn)行測(cè)量。所有的個(gè)性化特征和協(xié)作特征均將存儲(chǔ)在學(xué)習(xí)者特征庫(kù)中，作為網(wǎng)絡(luò)協(xié)作學(xué)習(xí)分組的依據(jù)。

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

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

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

(1)

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

變量 2 鄰域半徑Eps。定義對(duì)象的鄰域半徑Eps

(2)

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

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

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

(3)

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

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

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

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

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

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

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

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

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

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

圖2 分組算法流程圖

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

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

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

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

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

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

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

5 結(jié)束語(yǔ)

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

[1] 王永固,李克東.主題式網(wǎng)絡(luò)協(xié)作學(xué)習(xí)模型及其案例研究[J].中國(guó)電化教育,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ì)算機(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] 劉均,李人厚,鄭慶華.一種面向個(gè)性化協(xié)同學(xué)習(xí)的任務(wù)生成方法[J].軟件學(xué)報(bào),2006, 17(1):79-85.

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

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

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

[9] 陳國(guó)權(quán).復(fù)雜變化環(huán)境下人的學(xué)習(xí)能力:概念、模型、測(cè)量及影響[J].中國(guó)管理科學(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] 陳林林.移動(dòng)學(xué)習(xí)中學(xué)習(xí)者偏好模型研究[D].武漢:華中師范大學(xué),2013.

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

[14] 李潔.CSCL中協(xié)作小組分組系統(tǒng)的設(shè)計(jì)與開發(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)師。研究方向：云計(jì)算安全與大數(shù)據(jù)管理等。

TP301.6

A

1007-7820(2016)12-089-04