基于聚類和案例推理的個性化教學(xué)序列生成

朱忠旭，劉競杰

(安徽工貿(mào)職業(yè)技術(shù)學(xué)院 計算機技術(shù)系，安徽 淮南232007)

智能教學(xué)系統(tǒng)(Intelligent Tutoring System，ITS)是人工智能技術(shù)在教學(xué)領(lǐng)域的應(yīng)用，目標是代替教師對不同知識需求和個性特征的學(xué)生實施個別化教學(xué)，為學(xué)習(xí)者生成個性化的教學(xué)序列是實現(xiàn)智能教學(xué)的關(guān)鍵問題之一.當(dāng)前，大多數(shù)ITS生成教學(xué)序列的方式是通過分析教學(xué)內(nèi)容包含的知識點和知識點之間的關(guān)系建立知識模型，再結(jié)合學(xué)習(xí)者的特征模型抽取知識序列的產(chǎn)生規(guī)則來生成教學(xué)序列的［1］.也有學(xué)者提出采用神經(jīng)網(wǎng)絡(luò)［2］、強化學(xué)習(xí)［3］等方法來生成學(xué)習(xí)序列.

利用由模型提取的知識序列生成規(guī)則來完成教學(xué)序列生成的方法，面臨著學(xué)生的個性數(shù)據(jù)難于測定、規(guī)則難以獲取與描述、系統(tǒng)難以自我完善等瓶頸.然而，案例推理(Case Based Reasoning，CBR)技術(shù)規(guī)避了規(guī)則獲取這一困難環(huán)節(jié)，而且基于CBR的系統(tǒng)隨著存儲案例數(shù)量的逐步增加，系統(tǒng)解決問題的能力也不斷增長.因此，CBR技術(shù)在智能教學(xué)系統(tǒng)開發(fā)中的應(yīng)用逐漸受到了人們的重視.Hidayah等［4］用CBR方法來創(chuàng)建學(xué)生模型，以獲取學(xué)生對當(dāng)前課題內(nèi)容的掌握狀態(tài)，從而對學(xué)生進行個性化的教學(xué)指導(dǎo).Kharrat等［5］將CBR技術(shù)用于智能教學(xué)系統(tǒng)的課程安排.González等［6］提出采用CBR進行智能教學(xué)系統(tǒng)開發(fā)的方法學(xué)，開發(fā)了基于MAS和CBR進行ITS設(shè)計的總體框架.CBR作為一種依據(jù)以往經(jīng)驗解決問題的方法，為ITS系統(tǒng)的開發(fā)提供了新的途徑.

1 基于CBR生成知識序列的實現(xiàn)

1.1 知識模型與學(xué)生案例的定義

定義1知識點是與特定主題相關(guān)的基本知識容量單位，知識點標志和教學(xué)內(nèi)容之間具有一對一的對應(yīng)關(guān)系.知識點表示為KP=(id，name，content，dif，pre，post，mast).id為知識點的編號，name為知識點的名稱，content為知識點對應(yīng)的內(nèi)容，dif為知識點的難度水平，pre為知識點的前提知識點，post為知識點的后繼知識點.系統(tǒng)中，覆蓋相同領(lǐng)域內(nèi)容的知識點的編號和名稱是唯一的，不同課程包含相同的知識點時，對知識點要求的掌握水平可能不同，用mast表示.

學(xué)生案例的內(nèi)容包括問題特征描述、問題解決方法和對案例解答質(zhì)量的評價3個部分，定義2規(guī)范了用于生成教學(xué)序列的案例的結(jié)構(gòu).

定義2(學(xué)生案例)知識序列求解案例庫中的每條案例定義為Ck=(S_Bk，S_Tupsk(C，G)，WPk，L_Sk，C_Evak)，其中S_Bk=(Name，Department，Major，Class)，表示學(xué)生的姓名、所在系、專業(yè)、班級等基本信息;S_Tupsk(C，G)=Set((C，G))是一個課程和成績的二元組集合，描述學(xué)生在校期間學(xué)習(xí)的主要專業(yè)課程及成績;WPk是指學(xué)生所選擇的實習(xí)崗位;L_Sk=Queue(KP)，是一個由多個知識點構(gòu)成的隊列結(jié)構(gòu)，保存了學(xué)生在實習(xí)期間要學(xué)習(xí)的知識，知識點在隊列中的先后順序表示學(xué)習(xí)知識點的時間先后;C_Evak是學(xué)生學(xué)習(xí)任務(wù)完成后對知識序列質(zhì)量的評價.

1.2 學(xué)生案例相似度的計算

采用CBR方法進行問題求解時，首先要能夠快速地從案例庫中找到與當(dāng)前求解問題最相似的案例，案例之間相似度的定義直接關(guān)系到檢索結(jié)果的可用性.

案例的相似度包括總體相似度與局部相似度.影響學(xué)習(xí)序列生成的主要因素有學(xué)生的知識領(lǐng)域、知識水平和選擇的工作崗位.因此，計算案例之間的相似度時需要從3個方面考慮:學(xué)生的專業(yè)知識類別KC、知識水平KL、選擇的崗位P.學(xué)生案例相似度的計算公式定義為

式中，wkc，wkl，wp分別是專業(yè)知識類別、知識水平和崗位相似度在案例相似度計算中所占的比例，wkc+wkl+wp=1，sim(KC)，sim(KL)和sim(P)分別為知識類別、知識水平和崗位的相似度.

1.2.1 學(xué)生專業(yè)知識類別相似度的計算

定義3專業(yè)知識類別樹為對學(xué)生的專業(yè)知識類別逐步細分所得到的樹形結(jié)構(gòu)，記為T(KC).T(KC)的根結(jié)點代表總類別，其下層結(jié)點表示各個專業(yè)大類，每個專業(yè)大類又細分為若干個類別，每個類別所屬的各個專業(yè)構(gòu)成其子類別，各專業(yè)所設(shè)置的專業(yè)方向為葉結(jié)點，由此形成一個層次式的專業(yè)知識類別劃分結(jié)構(gòu).

學(xué)生知識類別相似程度取決于學(xué)生所學(xué)專業(yè)(或?qū)I(yè)方向)在知識類別樹T(KC)中的共同父類別的數(shù)量［7］，相似度計算方法如下式:

式中，kci和kcj分別為學(xué)生i與學(xué)生j所學(xué)習(xí)的專業(yè)(方向)，用函數(shù)common-super(kci，kcj)計算kci和kcj的公共的父結(jié)點，deep(T(KC))為類別樹的深度.

1.2.2 學(xué)生知識水平相似度的計算

學(xué)生知識水平相似度的計算公式如下:

1.2.3 工作崗位相似度的計算

學(xué)生工作崗位所需要的知識集合K-Set(post)定義為一個二元組(KPi，Mai)的集合，KPi為需要的知識點，Mai為工作崗位所需要的對此知識點的掌握水平.根據(jù)每個知識點對工作崗位的重要性的不同，規(guī)定了相應(yīng)的掌握級別如了解、理解、掌握和精通等，即K-Set(post)=Set((KPi，Mai)).

不同工作崗位知識需要的差別從所需知識點的不同及對每個知識點要求掌握程度的不同兩個方面比較.設(shè)工作崗位Posti與Postj需要掌握的知識點數(shù)量分別是ni和nj，它們都需要的知識點集合為CKS(Posti，Postj)，則崗位相似度的計算公式為

計算崗位相似度時，先求出崗位Posti和Postj需要的知識點集合的交集CKS，對CKS中的每個知識點，如果崗位Posti與Postj對其要求的掌握水平相同，則將其權(quán)重設(shè)為1，否則將其權(quán)重設(shè)為崗位Posti與Postj要求的掌握水平的最小值.兩崗位之間的距離定義為

1.3 基于崗位聚類對案例分類

定義5(崗位聚類)對就業(yè)崗位根據(jù)其所需要的專業(yè)知識進行分類，同一個聚類中的工作崗位要求學(xué)生具有的知識類別、知識水平的相似程度較高(即距離小于規(guī)定的閾值).

在CBR中，案例庫的案例數(shù)量隨著問題求解過程的進行不斷增加，所以必須根據(jù)案例庫中案例的變化及時調(diào)整案例組織.文獻［8］通過不斷使用聚類算法對案例庫中的案例進行聚類，控制案例聚類中案例的數(shù)量來加快案例檢索的速度.由于聚類算法的時間復(fù)雜度高、系統(tǒng)生命周期中算法需重復(fù)運行等因素，使得用于案例聚類的時間過多，不利于案例檢索速度的提高.為了減少用于聚類運算的時間，對經(jīng)典2-中心點算法進行了改進，形成惰性2-中心點算法.所謂惰性，是指通過設(shè)定特殊的算法啟動和結(jié)束條件來盡可能地減少聚類算法在軟件運行期間的執(zhí)行次數(shù)以降低聚類所需時間，具體做法如下:①不直接對案例進行聚類，而是對案例中的某個關(guān)鍵屬性進行聚類;②算法的激活由與關(guān)鍵屬性聚類中的屬性相關(guān)的案例的數(shù)量決定，僅當(dāng)案例數(shù)量超出規(guī)定的閾值時才運行聚類算法;③算法執(zhí)行時，隨機選擇兩個對象作為聚類中心，與中心距離不超過規(guī)定閾值的對象為一族，超過閾值的對象放入離外集，將要分類的對象分為兩個主要聚類.

惰性2-中心點算法描述如下:

(1)判斷要進行聚類的對象集S中的對象數(shù)量是否超出設(shè)定的最大值，若超出則轉(zhuǎn)至第(2)步，否則轉(zhuǎn)至第(6)步;

(2)隨機選擇兩個對象o1，o2作為聚類中心;

(3)計算各對象到o1，o2的距離，若某個對象到o1，o2的距離均大于設(shè)定的閾值，則將其放入集合S1;

(4)將S1以外的對象根據(jù)其與o1，o2的距離分為兩個聚類C1，C2;

(5)返回所得的分類C1，C2，S1及C1，C2的中心點o1，o2，轉(zhuǎn)至第(1)步;

(6)結(jié)束.

使用惰性2-中心點算法對學(xué)生選擇的實習(xí)崗位進行聚類運算.由于現(xiàn)實中崗位選擇的不均勻性，隨著新案例的不斷加入，會導(dǎo)致各個崗位聚類的不均勻生長，即選擇某些崗位聚類所包含的學(xué)生數(shù)量過多，而有的聚類包含的案例數(shù)量過少.為了解決這一問題，規(guī)定了一個聚類包含個體數(shù)量的最大值，當(dāng)超過該值時，對該聚類應(yīng)用上述算法時進行拆分，從而保證每個聚類涉及的案例數(shù)目都不會過大.每當(dāng)對崗位聚類進行一次拆分之后，需要重新生成案例的索引，動態(tài)索引創(chuàng)建算法如下:

(1)統(tǒng)計每個崗位聚類中的崗位所關(guān)聯(lián)的案例數(shù)量m;

(2)對m＞閾值M的崗位聚類，判斷其含有的崗位數(shù)n，若n≥2，則應(yīng)用惰性2-中心點算法對其進行聚類，將聚類中心點作為屬性聚類的代表對象，聚類產(chǎn)生的孤點加入到孤點集S中;若n＜2，表示選擇此崗位的學(xué)生案例過多，需要對其進行優(yōu)化，保留學(xué)生評價高的案例，去除學(xué)生評價較低的案例;

(3)判斷孤點集S中的崗位所關(guān)聯(lián)的案例數(shù)量是否超出閾值，若超出，則轉(zhuǎn)至第(2)步;

(4)根據(jù)聚類結(jié)果修改索引表.

1.4 基于CBR生成學(xué)習(xí)序列的過程

由于幾乎不存在與目標案例完全相同的源案例，所以為了使源案例的解決方案能夠成功地應(yīng)用于目標案例，需要對源案例的答案進行適當(dāng)調(diào)整.為了提高系統(tǒng)的自治性、實現(xiàn)改編過程的自動化，設(shè)計了兩種生成目標方案的策略:

(1)當(dāng)案例庫中不存在與目標案例相似的源案例時，由領(lǐng)域模型獲得實習(xí)崗位所需要的知識點，將其作為學(xué)生要學(xué)習(xí)的知識序列.將學(xué)生學(xué)習(xí)知識序列前已掌握的知識點從知識序列中刪除，得到的知識序列與學(xué)生數(shù)據(jù)一起作為案例存入案例庫.

(2)當(dāng)案例庫中存在與目標案例相似的源案例時，如果目標案例的崗位屬性與源案例不同，則根據(jù)目標案例的崗位屬性對相似的源案例的教學(xué)序列進行調(diào)整，將目標案例崗位需要而源案例崗位不需要的知識點加入教學(xué)序列.生成教學(xué)序列的詳細過程如圖1所示.

圖1 教學(xué)序列的生成過程Fig.1 Teaching sequence generating process

2 原型系統(tǒng)應(yīng)用分析

為了驗證上述CBR技術(shù)生成個性化學(xué)習(xí)序列的有效性，基于JADE平臺開發(fā)了學(xué)生頂崗實習(xí)階段智能化教學(xué)的原型系統(tǒng)，采用Oracle 11g數(shù)據(jù)庫進行案例存儲，用戶界面使用Java Swing設(shè)計.規(guī)定聚類時崗位距離閾值為0.9，每個崗位聚類涉及的案例最大數(shù)量為100個，通過學(xué)院2013級的1 000名頂崗實習(xí)學(xué)生的數(shù)據(jù)對原型系統(tǒng)進行檢驗，結(jié)果見圖2至圖4.

圖2 教學(xué)序列生成時間與學(xué)生數(shù)量的關(guān)系Fig.2 Relation between teaching sequence generatingtime and the number of students

圖3 崗位和崗位聚類數(shù)量與學(xué)生數(shù)量的關(guān)系Fig.3 Relation between post，post categoryand the number of students

由圖2可看出，知識序列生成所需的時間隨著學(xué)生數(shù)量的增加而增長.起初，案例庫中源案例的數(shù)量較少，案例檢索所需要的時間t1較短.另外，由案例檢索算法可知，在檢索不到與目標案例相匹配的源案例時，學(xué)習(xí)序列的生成完全由崗位知識需要進行規(guī)則推理決定.當(dāng)案例庫中案例數(shù)量增加時，案例檢中率越來越高，匹配成功的知識序列生成所需時間即為案例檢索所需時間.

隨著使用系統(tǒng)學(xué)生數(shù)量的增加，學(xué)生選擇實習(xí)崗位的數(shù)量和聚類算法對實習(xí)崗位進行聚類的結(jié)果的變化情況見圖3，可以看出崗位聚類的數(shù)量比同期的崗位數(shù)量少得多.

系統(tǒng)初始運行時，學(xué)習(xí)序列較長，經(jīng)過一段時間的運行，當(dāng)案例庫中的案例數(shù)增加到一定程度時，絕大多數(shù)目標案例求解都可以從案例庫中檢索到相似案例，此時平均序列長度較初始時有較大減少并逐步趨于穩(wěn)定，如圖4所示.

圖4 教學(xué)序列長度與學(xué)生數(shù)量的關(guān)系Fig.4 Relation between the length of teaching sequence and the number of students

3 結(jié)論

通過CBR技術(shù)將以往為學(xué)生生成學(xué)習(xí)序列的經(jīng)驗應(yīng)用到當(dāng)前的教學(xué)實例中，有效規(guī)避了教學(xué)序列生成規(guī)則的提取這一難點，降低了系統(tǒng)開發(fā)的難度.利用惰性2-中心點算法對學(xué)生實習(xí)崗位進行聚類，縮小了案例檢索的范圍并提高了系統(tǒng)效率.結(jié)合領(lǐng)域模型，實現(xiàn)了對源案例解答的自動改編及案例檢索失敗時教學(xué)序列的自動生成和案例庫的自動更新等操作.

［1］蔣艷榮，韓堅華，吳偉民.一種自適應(yīng)的個性化學(xué)習(xí)序列生成研究［J］.計算機科學(xué)，2013，40(8):204-209.

［2］Hassina，Sari T，SellamiM.A neural network for generating adaptive lessons［J］.Journal of Computer Science，2005(2):232-243.

［3］Iglesias A，Martinez P，F(xiàn)ernandez F.An experience applying reinforcement learning in a web-based adaptive and intelligent educational system［J］.Informatics in Education，2003(2):223-240.

［4］Hidayah I，Syahrina A，Permanasari A E.Studentmodeling using case-based reasoning in conventional learning system［J］.International Journal of Computer Science and Information Security，2012(10):1-5.

［5］KharratM，ReyhaniN，Badie K.A case-based reasoning approach to intelligent tutoring system by considering learner stylemodel［C］∥Systems and Information Engineering Design Symposium，VA:Charlottesville，2003:41-46.

［6］González C，Burguillo JC，Llamas M.Designing intelligent tutoring systems:a personalization strategy using case-based reasoning and multi-agent systems［J］.Advances in Distributed Computing and Artificial Intelligence Journal，2013(4):41-53.

［7］謝紅薇，李建偉.基于本體的案例推理模型研究［J］.計算機應(yīng)用研究，2009，26(4):1422-1424.

［8］喬麗，姜慧霖.一種k-means聚類的案例檢索算法［J］.計算機工程與應(yīng)用，2011，47(4):185-187.