一種新的自動(dòng)概念圖生成模型C-IK2

鄔寶嫻,謝 燚,郝天永,沈映姍

(華南師范大學(xué) 計(jì)算機(jī)學(xué)院,廣東 廣州 510631)

0 引言

隨著教育信息化和現(xiàn)代化水平的不斷提升,個(gè)性化教學(xué)和個(gè)性化測(cè)試系統(tǒng)應(yīng)運(yùn)而生。這些系統(tǒng)能夠根據(jù)學(xué)習(xí)者的能力、行為和學(xué)習(xí)結(jié)構(gòu)來定制學(xué)習(xí)內(nèi)容[1-5]。因此,教師可以根據(jù)學(xué)生的具體學(xué)習(xí)情況來制定相應(yīng)的教學(xué)策略。概念圖是一種用節(jié)點(diǎn)代表概念、連線表示概念間關(guān)系的圖示法,即利用圖示的方法表達(dá)人們頭腦中的概念、思想和理論等,其為教師提供了進(jìn)一步分析和完善教學(xué)策略的方法。Markhan等人[6]提出將概念圖作為一種教學(xué)原理和理論運(yùn)用到教學(xué)活動(dòng)中來幫助師生提高教學(xué)質(zhì)量。在教學(xué)過程中,利用概念圖可以幫助教師構(gòu)建知識(shí)網(wǎng)絡(luò),以便于教師對(duì)相關(guān)知識(shí)點(diǎn)之間的內(nèi)容進(jìn)行梳理,促進(jìn)學(xué)生進(jìn)行有意義的學(xué)習(xí)。但是,有效地創(chuàng)建概念圖是一項(xiàng)既復(fù)雜又耗時(shí)耗力的任務(wù)。因此,研究如何有效地自動(dòng)生成概念圖是必要的。

現(xiàn)有研究人員對(duì)概念圖進(jìn)行了諸多研究,并提出了一系列概念圖的自動(dòng)生成方法。Atapattu等人[7]提出了一種自然語言處理(NLP)算法,利用該算法從幻燈片中進(jìn)行“概念-關(guān)系-概念”三重提取,形成概念圖,替代了專家手工生成概念圖的方法。然而,其生成的概念圖是靜態(tài)的,不能反映學(xué)生學(xué)習(xí)過程的連續(xù)表現(xiàn),無法有效地分析出學(xué)生的學(xué)習(xí)理解能力。Huang等人[8]通過考慮問題的錯(cuò)對(duì)錯(cuò)關(guān)系和正確對(duì)正確關(guān)系,更精確地計(jì)算概念之間的關(guān)聯(lián)度,從而提高概念圖的準(zhǔn)確性,該方法生成的概念圖針對(duì)的是所有學(xué)生,忽略了不同學(xué)生對(duì)知識(shí)掌握程度的差異。Shao等人[9]提出TA-ARM自動(dòng)生成概念圖算法,該算法考慮概念之間的關(guān)聯(lián)性,使用文本分類算法,并結(jié)合關(guān)聯(lián)規(guī)則挖掘方法生成概念圖。但該算法生成的概念圖只考慮了概念間的方向性,沒有考慮概念間內(nèi)在的結(jié)構(gòu),很難從概念圖中得到學(xué)生對(duì)概念的有效理解。

隨著自動(dòng)概念圖生成方法研究的發(fā)展,貝葉斯網(wǎng)絡(luò)作為一種概率圖模型,近年來在自動(dòng)概念圖生成研究上得到了重視。貝葉斯網(wǎng)絡(luò)的圖結(jié)構(gòu)表示為節(jié)點(diǎn)及節(jié)點(diǎn)之間的連邊,邊表示兩個(gè)節(jié)點(diǎn)變量為因果關(guān)系。Alfonso[10]使用貝葉斯網(wǎng)絡(luò)概念圖模型,該模型采用關(guān)聯(lián)規(guī)則挖掘技術(shù)來分析多項(xiàng)選擇考試問題的學(xué)生答案,進(jìn)而針對(duì)特定學(xué)習(xí)領(lǐng)域半自動(dòng)地生成精準(zhǔn)的能力圖。Cooper 和 Herskovits[11]提出K2算法,該算法是基于兩階段的貪婪啟發(fā)式算法。其第一階段是對(duì)搜索空間進(jìn)行剪枝;第二階段是搜索滿足有向圖約束的網(wǎng)絡(luò)結(jié)構(gòu),該算法的結(jié)果受輸入變量的排序影響,因此,找到最佳變量排序順序?qū)μ岣咚惴ㄐ阅苤陵P(guān)重要。基于K2算法序列改進(jìn)的圖研究近年來得到越來越多的重視,例如,Tabar等人[12]提出利用L1正則化馬爾可夫鏈獲得K2算法的輸入序列,以改進(jìn)K2算法。但現(xiàn)有研究普遍存在準(zhǔn)確性不高問題,并且存在忽視圖質(zhì)量這一重要指標(biāo)的問題。

綜合以上討論,本文提出了一種新的自動(dòng)概念圖生成模型C-IK2,以解決概念圖不能反映學(xué)生對(duì)概念的理解程度,同時(shí)忽略不同學(xué)生對(duì)概念的接受程度不同的問題。本文生成了概念之間具有內(nèi)在層次關(guān)系的概念圖,彌補(bǔ)現(xiàn)有研究僅考慮概念間關(guān)系的缺陷,為教師提供概念教學(xué)計(jì)劃的指導(dǎo)。本文調(diào)研了LPG(Learning Paths Automatic Generation Algorithm)算法[13]所構(gòu)造概念圖的局限性。該算法雖然能夠生成簡潔的有向無環(huán)圖,揭示概念之間的相互關(guān)系,但忽略了概念之間的層次關(guān)系,使得在教學(xué)等差異化應(yīng)用中作用受限。K2算法是構(gòu)建具有層次結(jié)構(gòu)貝葉斯網(wǎng)絡(luò)圖方法,通過與LPG算法的結(jié)合,能夠?yàn)闃?gòu)建具有層次結(jié)構(gòu)的概念圖提供新的思路。然而K2算法存在一個(gè)缺陷,即所使用的節(jié)點(diǎn)序列是以遞增方式作為輸入,而未充分考慮節(jié)點(diǎn)序列之間的實(shí)際關(guān)系。因此,在構(gòu)建具有層次結(jié)構(gòu)的概念圖時(shí),還需要充分考慮節(jié)點(diǎn)序列的關(guān)系,以更準(zhǔn)確地反映概念之間的層次結(jié)構(gòu)和相互關(guān)系。C-IK2 模型以LPG算法構(gòu)造作為中間件以生成有效序列,該序列作為K2算法的輸入序列,生成概念圖。最終模型通過將改進(jìn)K2算法和LPG算法結(jié)合形成一種新的自動(dòng)化概念圖生成模型。

本文主要貢獻(xiàn)如下:

(1) 提出新的學(xué)習(xí)路徑生成方法作為K2算法的輸入序列。

(2) 構(gòu)建基于LPG算法與K2算法相結(jié)合的C-IK2模型,用于生成具有層次結(jié)構(gòu)特點(diǎn)的概念圖,改進(jìn)傳統(tǒng)路徑教學(xué)中的單一方向性問題,通過層次結(jié)構(gòu)展現(xiàn)了概念之間的深度聯(lián)系。

(3) 實(shí)驗(yàn)結(jié)果表明,C-IK2模型在圖準(zhǔn)確度和圖結(jié)構(gòu)質(zhì)量上優(yōu)于現(xiàn)有基于評(píng)分的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)方法。

1 國內(nèi)外研究現(xiàn)狀

1.1 自動(dòng)概念圖生成研究

近年來,智慧學(xué)習(xí)系統(tǒng)變得越來越流行,該系統(tǒng)可以根據(jù)學(xué)生的能力為學(xué)生提供定制的課程,以達(dá)到個(gè)性化學(xué)習(xí)的目的。為了滿足個(gè)性化學(xué)習(xí)的需求,教師常常利用概念圖為學(xué)生制定個(gè)性化的學(xué)習(xí)方案,從而更好地開展教學(xué)。然而,手動(dòng)創(chuàng)建概念圖既費(fèi)時(shí)又費(fèi)力。因此,如何實(shí)現(xiàn)概念圖的自動(dòng)生成已成為當(dāng)前個(gè)性化學(xué)習(xí)研究的熱點(diǎn)問題。Chen等人[14]為了實(shí)現(xiàn)從學(xué)術(shù)文章中生成電子信息領(lǐng)域概念圖,以該領(lǐng)域的相關(guān)期刊文章和會(huì)議論文作為數(shù)據(jù)源,利用文本挖掘技術(shù)自動(dòng)生成學(xué)習(xí)領(lǐng)域的概念圖。Wang等人[15]提供了一個(gè)框架用于生成特定類型的知識(shí)圖,即來自教科書的概念圖。這些研究直接從教學(xué)文本分析中生成概念圖,在一定程度上為教師合理根據(jù)教材進(jìn)行教學(xué)過程設(shè)計(jì)提供一定參考,幫助學(xué)生更好地理解教材概念。盛泳潘等人[16]提出基于開放域抽取的多文檔概念圖構(gòu)建方法。該方法先對(duì)文檔進(jìn)行排序,然后從多篇文章中抽取出大量具有事實(shí)表達(dá)能力的三元組實(shí)例。通過關(guān)系實(shí)例過濾算法得到顯著關(guān)系實(shí)例,并構(gòu)成多個(gè)概念子圖,接下來進(jìn)一步合并其中的等價(jià)概念,合并或增加新的關(guān)系類型,最終形成一張連通的概念圖。然而這些直接從文本中提取關(guān)鍵字的方法并沒有分析學(xué)生的學(xué)習(xí)行為,因此無法確定學(xué)生對(duì)概念的熟悉程度,也無法從學(xué)生的角度出發(fā)判斷該概念圖的創(chuàng)建是否真的適應(yīng)學(xué)生的學(xué)習(xí)要求。

Tseng等人[17]提出了一個(gè)兩階段概念圖構(gòu)造方法(TP-CMC),通過學(xué)習(xí)者的歷史測(cè)試記錄自動(dòng)生成概念圖,第一階段用于預(yù)處理測(cè)試記錄,即轉(zhuǎn)換數(shù)字等級(jí)數(shù)據(jù)和完善測(cè)試記錄,并從輸入數(shù)據(jù)中挖掘關(guān)聯(lián)規(guī)則;第二階段用于轉(zhuǎn)換挖掘的關(guān)聯(lián)規(guī)則,學(xué)習(xí)概念之間的先決條件關(guān)系以生成所有學(xué)習(xí)者概念圖。Romero等人[18]提出了一種基于概念圖的學(xué)習(xí)策略,學(xué)生自己生成概念圖并將生成的概念圖與其教師生成的概念圖進(jìn)行比較,發(fā)現(xiàn)學(xué)生在概念把握方面的不足。這些研究生成的概念圖反映所有學(xué)生的學(xué)習(xí)情況,所有學(xué)生都以相同的學(xué)習(xí)方式和學(xué)習(xí)路徑進(jìn)行學(xué)習(xí),如果后續(xù)要對(duì)概念圖進(jìn)行進(jìn)一步分析則會(huì)相當(dāng)耗時(shí)。Li等人[13]充分考慮了不同學(xué)生群體的學(xué)習(xí)性能,利用聚類算法和關(guān)聯(lián)規(guī)則挖掘生成了具有不同學(xué)習(xí)特征的概念圖,并利用拓?fù)渑判蛩惴ㄉ闪藥追N簡化的學(xué)習(xí)路徑,該算法生成的概念圖考慮了概念間的聯(lián)系,但是沒有考慮概念間的內(nèi)在結(jié)構(gòu)層次。

總的來說,對(duì)概念圖的研究分為三種類型。第一類利用文本挖掘技術(shù)直接從文本中提取概念以生成概念圖,然而生成的概念圖缺乏進(jìn)一步的分析,不能反映學(xué)生對(duì)概念的實(shí)際理解程度;第二類研究考慮學(xué)生的學(xué)習(xí)表現(xiàn),但是生成的概念圖反映了所有學(xué)生的學(xué)習(xí)表現(xiàn),不能根據(jù)學(xué)生對(duì)概念的掌握程度來區(qū)分學(xué)生;第三類研究能區(qū)分不同學(xué)生的學(xué)習(xí)情況,卻不能反映概念之間的內(nèi)在層次關(guān)系,無法指導(dǎo)教師制訂概念教學(xué)計(jì)劃。

1.2 貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)方法

貝葉斯網(wǎng)路結(jié)構(gòu)學(xué)習(xí)方法主要分為基于約束的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)方法和基于評(píng)分的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)方法[19]。基于約束的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)方法使用一系列的條件假設(shè)檢驗(yàn)來學(xué)習(xí)模型中變量之間的獨(dú)立性從而生成有向圖。PC(PredictiveCausation)和IC(InductiveCausation)是這類方法的著名例子?；谠u(píng)分的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)方法是通過衡量其評(píng)分函數(shù)從而找到最好有向圖的,即當(dāng)給定數(shù)據(jù)集D={D1,D2,…,Dn}時(shí),找到一個(gè)結(jié)構(gòu)G*,使得G*滿足式(1)的條件。

(1)

其中,Gn為變量集V={X1,X2,…,Xn}在有向圖搜索空間中的所有可能結(jié)構(gòu)。

基于評(píng)分的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)方法有GOBNILP算法[20]、貪婪爬山搜索算法[21]、貪婪最大最小爬山算法[22]、K2算法[23]等。本文主要研究K2算法,該算法是以給定優(yōu)先序列節(jié)點(diǎn)作為輸入,從數(shù)據(jù)中學(xué)習(xí)到使得貝葉斯網(wǎng)絡(luò)后驗(yàn)概率最大的貝葉斯結(jié)構(gòu)網(wǎng)絡(luò)。K2算法通過輸入節(jié)點(diǎn)的先后順序來降低計(jì)算復(fù)雜性,因而生成合理的點(diǎn)序列至關(guān)重要。基于K2的改進(jìn)方法可以分為基于約束方法改進(jìn)K2方法、基于互信息改進(jìn)K2方法、基于先驗(yàn)序改進(jìn)K2方法、基于領(lǐng)域知識(shí)改進(jìn)K2算法和基于圖論改進(jìn)K2方法[24]。Aouay等人[25]提出一種基于粒子群算法和K2算法的結(jié)構(gòu)學(xué)習(xí)新方法,此處的粒子群算法用于在有序空間中進(jìn)行搜索,然后通過運(yùn)用K2算法返回與其相符的貝葉斯網(wǎng)絡(luò)。Chen等人[26]使用互信息(MI)和獨(dú)立性檢測(cè)來獲得節(jié)點(diǎn)的正確排列。Ko 和 Kim[27]提出了一種新的評(píng)價(jià)度量方法,用來評(píng)估條件頻率以確定節(jié)點(diǎn)的順序,該算法讓孩子節(jié)點(diǎn)的父節(jié)點(diǎn)使用離散Dirichlet概率密度函數(shù),通過驗(yàn)證條件頻率使子節(jié)點(diǎn)在連接到正確的父節(jié)點(diǎn)時(shí)具有更大的條件概率。Ai[28]證明了信息熵可以作為一個(gè)有效的度量指標(biāo)來評(píng)估每個(gè)節(jié)點(diǎn)的重要性,可以將熵從低到高排序來建立節(jié)點(diǎn)的有效順序。劉艷杰等人[29]提出以學(xué)生7門主干學(xué)科成績作為數(shù)據(jù)樣本,用節(jié)點(diǎn)間的條件互信息對(duì)各節(jié)點(diǎn)進(jìn)行條件獨(dú)立性檢測(cè), 確定貝葉斯網(wǎng)絡(luò)的初步結(jié)構(gòu), 再利用K2算法進(jìn)行全局優(yōu)化, 最終確定網(wǎng)絡(luò)結(jié)構(gòu)。

雖然這些算法在提高圖準(zhǔn)確性上有一定的效果,但它們忽略了圖結(jié)構(gòu)質(zhì)量這一重要指標(biāo),性能還有待進(jìn)一步提升。

2 自動(dòng)概念圖生成模型C-IK2

2.1 K2算法

K2算法在給定一個(gè)數(shù)據(jù)集D的情況下,搜索具有最大后驗(yàn)概率網(wǎng)絡(luò)結(jié)構(gòu)的G,即求解最大的p(G|D)。K2算法運(yùn)用啟發(fā)式搜索方法,首先假設(shè)節(jié)點(diǎn)中缺少父節(jié)點(diǎn),然后在每一步中逐步增加滿足結(jié)構(gòu)網(wǎng)絡(luò)概率最大的父節(jié)點(diǎn)。當(dāng)無法再提高網(wǎng)絡(luò)結(jié)構(gòu)概率時(shí),K2算法停止增加父節(jié)點(diǎn)。因此,K2算法輸入序列對(duì)減少計(jì)算復(fù)雜度有著至關(guān)重要的影響。這意味著,若節(jié)點(diǎn)xi在排序中優(yōu)先于節(jié)點(diǎn)xj,則節(jié)點(diǎn)xj不能是節(jié)點(diǎn)xi的父節(jié)點(diǎn)。

2.2 LPG算法

基于K2算法輸入序列特性,即如果節(jié)點(diǎn)xi在排序中優(yōu)先于節(jié)點(diǎn)xj,則節(jié)點(diǎn)xj不能是節(jié)點(diǎn)xi的父節(jié)點(diǎn),應(yīng)用LPG[13]算法思想來構(gòu)造節(jié)點(diǎn)有效序列。該算法利用QC和R兩個(gè)數(shù)據(jù)集獲得學(xué)生特征,根據(jù)學(xué)生的錯(cuò)誤率進(jìn)行聚類處理得到學(xué)生分簇G={G1,G2,…,Gi,…,Gk},對(duì)每個(gè)簇Gi矩陣計(jì)算其問題之間的一致性,符合一致性要求的簇進(jìn)入下一步,計(jì)算Gi矩陣中問題之間的置信度。構(gòu)造新的qc′,如式(2)所示。

(2)

(3)

其中,Rev (Cu,Cv)Qa→Qb表示由關(guān)聯(lián)規(guī)則導(dǎo)出的問題Qa→Qb對(duì)應(yīng)概念Cu和Cv的相關(guān)度,Confidence(Qa→Qb)是Qa→Qb的置信度。

接著利用此相關(guān)度生成概念圖,最后利用拓?fù)渑判騺砬蟮脤W(xué)習(xí)路徑。相關(guān)實(shí)驗(yàn)證明生成概念圖的合理性,而且生成的學(xué)習(xí)路徑能有效區(qū)分學(xué)生。該算法生成的學(xué)習(xí)路徑是一個(gè)線性序列,此線性序列能表示學(xué)生學(xué)習(xí)概念的順序,即若概念Qa在Qb之前,則一定先學(xué)習(xí)概念Qa,這與K2算法的輸入序列特性一致。

2.3 C-IK2模型

用LPG算法生成概念圖和用K2算法生成概念圖都存在缺陷,LPG算法生成的概念圖,雖然考慮了概念之間的聯(lián)系,但是概念之間的上下級(jí)關(guān)系卻無法確定,而使用K2算法生成的概念圖雖然考慮,變量之間的上下級(jí)關(guān)系,但是其輸入是按照變量之間的遞增序列,而不同學(xué)生行為有著不同的輸入序列,它忽視了輸入序列的合理性。

為了解決K2算法輸入序列的合理性問題,本文改進(jìn)LPG算法和K2算法,并將兩個(gè)算法結(jié)合起來,提出了一種新自動(dòng)概念圖生成模型C-IK2,它同時(shí)具有LPG算法與K2算法的特點(diǎn)。

在C-IK2模型中,首先根據(jù)學(xué)生考試數(shù)據(jù)和概念與問題數(shù)據(jù)提取學(xué)生錯(cuò)誤率信息;然后利用數(shù)據(jù)挖掘中的聚類技術(shù)將學(xué)生聚類成若干簇,將不同簇的學(xué)生進(jìn)行理解水平的預(yù)處理;接著利用改進(jìn)LPG算法求得概念間序列,將此序列作為K2算法的輸入;最后使用改進(jìn)K2算法生成具有層次結(jié)構(gòu)的概念圖,每個(gè)概念圖反映了相應(yīng)學(xué)生簇的學(xué)習(xí)表現(xiàn)。該算法的整體框架如圖1所示。

圖1 概念圖生成模型C-IK2的框架示意

2.3.1 數(shù)據(jù)處理

在提取學(xué)生錯(cuò)誤率之前,分析給定的兩個(gè)矩陣,第一個(gè)矩陣表示試題和概念之間的關(guān)系,其中試題與概念之間的關(guān)系表示試題屬于試卷中的哪個(gè)概念。當(dāng)一個(gè)試題關(guān)聯(lián)多個(gè)概念時(shí),如果一個(gè)學(xué)生在問題上出現(xiàn)錯(cuò)誤,我們無法僅憑這一錯(cuò)誤判斷他具體哪一個(gè)概念未掌握。因此,在該算法中一個(gè)試題只屬于一個(gè)概念,但一個(gè)概念可以包含許多試題,將試題和概念之間的關(guān)系表示為QC,為了保證該數(shù)據(jù)集的正確性,QC由相關(guān)專家給出。對(duì)于上述參與試題(Q1,Q2,Q3,…,QNq)與概念(C1,C2,C3,…,CNc)間的關(guān)系,定義的問題概念矩陣如式(4)所示。

(4)

其中,qcij∈{0,1}表示第i個(gè)問題是否屬于第j個(gè)概念,qcij=0表示第i個(gè)試題不屬于第j個(gè)概念,qcij=1表示第i個(gè)試題屬于第j個(gè)概念。

另一個(gè)矩陣是學(xué)生的測(cè)試記錄,用SQ表示。該數(shù)據(jù)集表明學(xué)生(S1,S2,S3,…,SNs)對(duì)每個(gè)試題(Q1,Q2,Q3,…,QNq)的回答是否正確。該學(xué)生測(cè)試記錄矩陣結(jié)果如式(5)所示。

(5)

其中,sqij表示第i個(gè)學(xué)生是否正確回答試題j,sqij∈{0,1},sqij=0表示第i個(gè)學(xué)生沒有正確回答第j個(gè)試題,sqij=1表示第i個(gè)學(xué)生有正確回答第j個(gè)題。

下一步,使用聚類算法分析新的學(xué)生特征。聚類分析是一種無監(jiān)督的機(jī)器學(xué)習(xí)方法,該方法可在非均勻大樣本中構(gòu)造具有均勻性質(zhì)的簇,使簇內(nèi)盡可能同質(zhì),各簇之間的差異盡可能大。因此根據(jù)學(xué)生特點(diǎn)將學(xué)生分成幾個(gè)不同的簇,使同一簇的學(xué)生盡可能相似,即同一簇的學(xué)生在掌握概念方面盡可能相似。本文利用Birch聚類算法對(duì)學(xué)生進(jìn)行分簇,再對(duì)不同的學(xué)生簇進(jìn)行單獨(dú)分析。學(xué)生簇表示為G={G1,G2,…,Gi,…,Gk},其中Gi表示第i簇,k表示簇?cái)?shù)。其數(shù)據(jù)處理過程的正確性和有效性在Li等人[18]提出的論文中得到證實(shí)。

基于QC和G,將不同簇的學(xué)生正確回答試題程度轉(zhuǎn)化為該簇學(xué)生對(duì)每個(gè)概念的掌握程度,表示為gx={gx1,gx2,…,gxi,…,gxk},其中k是小簇?cái)?shù)目,gxi表示第i簇學(xué)生,第i個(gè)小簇對(duì)概念掌握程度的矩陣如式(6)所示。

11月中旬柑橘產(chǎn)量與降水量呈顯著正相關(guān)，柑橘進(jìn)入果實(shí)成熟采摘期，降水有利果實(shí)增重，干旱會(huì)使果實(shí)內(nèi)的水分向葉片輸出，單果重下降。但是，成熟期適度的干旱有利于提高果實(shí)品質(zhì)和采收貯藏［12］。

(6)

其中,Nc是概念數(shù)目,sgxNiNj表示第i學(xué)生對(duì)概念j的掌握程度,sgxNiNj∈[0,1],表示學(xué)生回答試題的正確率。sgxNiNj值越大,第i簇學(xué)生對(duì)概念j的掌握就越好。第i簇學(xué)生回答試題的正確率可以轉(zhuǎn)化為該簇學(xué)生對(duì)每個(gè)概念的掌握水平,表現(xiàn)為掌握與沒掌握二種形式。如果sgxNiNj∈[0,0.6],則認(rèn)為學(xué)生i在概念j上的掌握程度不符合要求;如果sgxNiNj∈[0.6,1],則認(rèn)為學(xué)生i能較好地掌握概念j。在接下來的步驟中,分別對(duì)每簇進(jìn)行上述處理。將GX轉(zhuǎn)化為GX′={gx′1,gx′2,…,gx′i,…,gx′k},GX′表示學(xué)生是否掌握知識(shí)矩陣,其中n是小簇?cái)?shù)目,gx′i表示第i簇學(xué)生是否掌握該知識(shí),gx′i由式(7)表示。

(7)

2.3.2 實(shí)驗(yàn)方法

對(duì)數(shù)據(jù)處理后生成的GX′與QC進(jìn)行分析,首先基于某個(gè)簇學(xué)生特征矩陣gxi′,計(jì)算問題Qa和Qb的計(jì)數(shù)器值,其Qa=[ga1,ga2,…gai,…,gaNc],Qb=[gb1,gb2,…gbi,…,gbNc]。計(jì)數(shù)器表示問題Qa和Qb之間的答案一致性,如式(8)所示。

只有當(dāng)Count(Qa,Qb)>Nc×40%是真時(shí),才轉(zhuǎn)入下一步。

(8)

使用LPG算法分析學(xué)生掌握概念的關(guān)系圖,挖掘概念之間潛在的聯(lián)系。結(jié)合LPG算法生成關(guān)系圖之前,要考慮兩種情況: 情況一: 學(xué)生掌握了概念a且掌握概念b的情況;情況二: 學(xué)生沒有掌握概念a且沒有掌握概念b的情況。

基于學(xué)生概念掌握矩陣gxi′使用LPG算法進(jìn)行挖掘,在進(jìn)行LPG算法挖掘之前,先對(duì)gxi′進(jìn)行分析,將其分為上述兩種情況。接下來分別對(duì)這兩種情況用LPG算法處理,過程如下: 第一構(gòu)造概念1項(xiàng)集,表示學(xué)習(xí)者對(duì)該概念的掌握程度;第二構(gòu)造概念2項(xiàng)集,即學(xué)習(xí)者同時(shí)掌握兩個(gè)概念的學(xué)習(xí)程度,然后計(jì)算每組概念的支持度,設(shè)置支持度閾值。只有滿足支持度閾值才能進(jìn)行下一步,計(jì)算學(xué)生掌握概念Cx同時(shí)掌握概念Cy的置信度,和學(xué)生未掌握概念Cx也未掌握概念Cy的置信度。同樣設(shè)置閾值來評(píng)估概念間關(guān)系的強(qiáng)弱,并最終得出概念關(guān)系圖。為了避免概念之間的相關(guān)程度太小,使得關(guān)聯(lián)規(guī)則不可信,再計(jì)算概念之間的關(guān)聯(lián)規(guī)則設(shè)置支持度閾值,即支持度大于0.9的關(guān)聯(lián)規(guī)則。再計(jì)算學(xué)生不能掌握概念a和不能掌握概念b的置信度。LPG算法在這之后還是用了問題概念數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。為了使得算法更具有普遍性,能夠獲得更精確的概念圖,對(duì)LPG算法進(jìn)行改進(jìn)。本文對(duì)問題概念數(shù)據(jù)集進(jìn)行處理生成GX′,因此無需后續(xù)操作。將改進(jìn)LPG算法得到的關(guān)系圖作為生成概念圖的中間件。在建立概念關(guān)系圖的過程中,如果概念圖表示掌握了x概念也掌握了y概念,那么概念圖的箭頭為Cx→Cy;如果概念圖表示既沒有掌握x概念也沒有掌握y概念,那么概念圖的箭頭為Cy→Cx,以此生成k個(gè)概念關(guān)系圖,表示RM={RM1,RM2,…,RMi,…RMk},其中RMi表示第i個(gè)概念關(guān)系圖,k表示概念關(guān)系圖的數(shù)量。每個(gè)概念關(guān)系圖反映了相應(yīng)的學(xué)生簇的學(xué)習(xí)表現(xiàn)。下面將對(duì)每個(gè)概念關(guān)系圖進(jìn)行分析。

當(dāng)概念數(shù)量大時(shí),概念之間的關(guān)聯(lián)規(guī)則復(fù)雜,使用人力來分析概念非常耗時(shí),因而使用K2算法來自動(dòng)生成概念圖是必要的。本文在使用K2算法之前需要將復(fù)雜的概念關(guān)系圖自動(dòng)轉(zhuǎn)化為概念序列。拓?fù)渑判蛩惴ㄊ欠治鲇邢驘o環(huán)圖[30]的常用算法,該算法可以將有向無環(huán)圖轉(zhuǎn)換為節(jié)點(diǎn)序列,由于任意兩個(gè)概念之間要么具有確定的先后關(guān)系,要么沒有關(guān)系,絕對(duì)不存在互相矛盾的關(guān)系,符合拓?fù)渑判蛏傻墓?jié)點(diǎn)序列的特性,因此使用拓?fù)渑判騺砩筛拍钚蛄惺呛侠淼摹?/p>

(9)

C-IK2模型的偽碼如算法1所示,其中步驟1～5對(duì)數(shù)據(jù)集G進(jìn)行預(yù)處理,步驟7～26生成概念關(guān)系圖,步驟27～28將概念關(guān)系圖轉(zhuǎn)化為輸入序列,步驟28利用輸入序列和K2算法生成概念圖CM。

算法1 C-IK2模型

3 實(shí)驗(yàn)與結(jié)果

實(shí)驗(yàn)的目標(biāo)是對(duì)所提出的模型進(jìn)行實(shí)證評(píng)估。首先借助ASIA網(wǎng)絡(luò),對(duì)Tabar等人[12]、Ko和Kim[21]、Ai[28]提出的三種基于節(jié)點(diǎn)排序的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法進(jìn)行了性能評(píng)估。GOB-NILP算法[20]、貪婪爬山搜索算法[21]、貪婪最大最小爬山算法[22]、K2算法[23]和Behjati等人[31]提出的基于評(píng)分的算法進(jìn)行比較。最后對(duì)所提出模型生成的概念圖與K2算法生成的概念圖做比較。實(shí)驗(yàn)從五個(gè)方面來對(duì)本文所提出的算法進(jìn)行評(píng)價(jià): 生成圖結(jié)構(gòu)的準(zhǔn)確性、圖結(jié)構(gòu)質(zhì)量、生成概念圖的合理性、算法的時(shí)間復(fù)雜度以及數(shù)據(jù)變量序列的算法影響。其中生成圖結(jié)構(gòu)的準(zhǔn)確性、圖結(jié)構(gòu)質(zhì)量、生成概念圖的合理性三個(gè)評(píng)價(jià)指標(biāo)體現(xiàn)的自動(dòng)生成的概念圖的有效性。而算法的時(shí)間復(fù)雜度以及數(shù)據(jù)集變量序列算法的影響體現(xiàn)了C-IK2算法改進(jìn)K2算法的有效性。

3.1 數(shù)據(jù)集和實(shí)驗(yàn)環(huán)境

為了測(cè)試C-IK2模型,實(shí)驗(yàn)使用了標(biāo)準(zhǔn)的性能度量。實(shí)驗(yàn)數(shù)據(jù)集使用著名ASIA基準(zhǔn)網(wǎng)絡(luò), 該網(wǎng)絡(luò)來自bnlearn R包[32]中包含的貝葉斯網(wǎng)絡(luò)存儲(chǔ)庫的ASIA數(shù)據(jù)集,含有8個(gè)變量、8條邊,并用公開教育數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)分析,此數(shù)據(jù)集包含6 866名學(xué)生在計(jì)算機(jī)文化基礎(chǔ)課程中的大規(guī)模測(cè)驗(yàn),有總計(jì)617 940條測(cè)試記錄數(shù)據(jù),涵蓋90個(gè)問題、29個(gè)概念類型。

試題與概念之間的關(guān)系(QC)由相關(guān)領(lǐng)域的權(quán)威專家給出,保證了正確性和權(quán)威性。實(shí)驗(yàn)運(yùn)行環(huán)境為Windows 10操作系統(tǒng),編程語言為Python 3.6和Matlab。表1列出的是對(duì)實(shí)驗(yàn)中使用的數(shù)據(jù)庫的描述。

表1 數(shù)據(jù)集統(tǒng)計(jì)

為了便于理解,測(cè)試記錄數(shù)據(jù)和學(xué)生測(cè)試記錄樣例數(shù)據(jù)如表2和表3所見,0表示該學(xué)生未正確回答該問題,1表示該學(xué)生已正確回答該問題,橫軸表示學(xué)生,縱軸表示問題。類似的在表3中,1表示問題屬于該概念,0表示問題不屬于該概念,橫坐標(biāo)代表問題,縱坐標(biāo)代表概念.

表2 學(xué)生測(cè)試記錄數(shù)據(jù)樣例

表3 概念問題數(shù)據(jù)樣例

續(xù)表

3.2 基線方法和評(píng)估標(biāo)準(zhǔn)

實(shí)驗(yàn)采用現(xiàn)有基于節(jié)點(diǎn)序列的重要相關(guān)方法作為基線方法。Tabar等人、Ko和Kim、Ai 中引入了新的節(jié)點(diǎn)序列算法,為了證明C-IK2模型解決貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)問題的有效性,實(shí)驗(yàn)使用ASIA數(shù)據(jù)集。為與上述三種算法進(jìn)行充分對(duì)比,以評(píng)估所提出的C-IK2模型的性能,本文使用以下評(píng)估指標(biāo): 真陽性(TP)表示正確識(shí)別的邊的數(shù)量;錯(cuò)誤陽性(FP)表示錯(cuò)誤識(shí)別的邊的數(shù)量;假否定(FN)指定錯(cuò)誤識(shí)別的非鏈接邊的數(shù)量。錯(cuò)誤陽性和假否定描述了原始結(jié)構(gòu)和推斷結(jié)構(gòu)之間的差異(Graph error)。準(zhǔn)確率(P)、召回率(R)和F1值的計(jì)算如式(10)～式(12)所示。

同時(shí),為了研究所提出的結(jié)構(gòu)學(xué)習(xí)算法學(xué)習(xí)網(wǎng)絡(luò)結(jié)構(gòu)的準(zhǔn)確性,實(shí)驗(yàn)研究了隨數(shù)據(jù)集大小召回率、準(zhǔn)確率和F1的變化情況。

對(duì)于教育數(shù)據(jù)集,實(shí)驗(yàn)考慮區(qū)分學(xué)生對(duì)概念理解程度,使用聚類算法,根據(jù)學(xué)生概念掌握程度特征進(jìn)行分簇,分別使用K-means、Birch、高斯混合聚類算法進(jìn)行分簇,使用Calinski Harabasz分?jǐn)?shù)作為聚類算法的評(píng)估指標(biāo),其數(shù)學(xué)計(jì)算如式(13)所示。

(13)

其中,N為訓(xùn)練集樣本,k為類別數(shù),Bk為類別之間的協(xié)方差矩陣,Wk為類別內(nèi)部數(shù)據(jù)的協(xié)方差矩陣。tr為矩陣的跡。類別內(nèi)部數(shù)據(jù)的協(xié)方差越小越好,類別之間的協(xié)方差越大越好,當(dāng)簇密度較小且分離較好時(shí),Calinski Harabasz分?jǐn)?shù)更高。

C-IK2自動(dòng)概念圖生成模型與5種基于評(píng)分的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)方法在標(biāo)準(zhǔn)數(shù)據(jù)集ASIA中進(jìn)行比較。這五種方法分別是GOBNILP算法、貪婪爬山搜索算法、貪婪最大最小爬山算法、K2算法和Behjati等人提出的算法,實(shí)驗(yàn)使用BIC學(xué)習(xí)網(wǎng)絡(luò)結(jié)構(gòu)的質(zhì)量和概念圖的現(xiàn)實(shí)意義對(duì)三個(gè)方面對(duì)所提出的算法進(jìn)行了評(píng)價(jià),使用貝葉斯信息準(zhǔn)則作為績效衡量標(biāo)準(zhǔn)(Bayesian Information Criterion, BIC),BIC可用式(14)表示。

(14)

3.3 實(shí)驗(yàn)結(jié)果

使用準(zhǔn)確率、召回率和F1在 ASIA 數(shù)據(jù)集中對(duì)不同的樣本(1 000、2 000、5 000和10 000)來評(píng)估結(jié)構(gòu)學(xué)習(xí)準(zhǔn)確率?？梢钥闯?C-IK2模型對(duì)于不同大小的樣本產(chǎn)生了最接近原始ASIA網(wǎng)絡(luò)的結(jié)構(gòu)。在表4中,粗體值表示該算法部分最佳結(jié)果,C-IK2模型比其他三種算法在生成ASIA 網(wǎng)絡(luò)上有最高的準(zhǔn)確率、召回率和F1得分。而從穩(wěn)定性來看,C-IK2方法無論是在樣本較小的2 000數(shù)據(jù),還是在樣本較大的10 000數(shù)據(jù)中都能保持穩(wěn)定且更接近原始ASIA網(wǎng)絡(luò)結(jié)構(gòu)。

表4 算法性能對(duì)比

實(shí)驗(yàn)對(duì)ASIA數(shù)據(jù)集取10 000個(gè)數(shù)據(jù),算法的性能指標(biāo)給出GOBNILP算法、貪婪爬山搜索算法,貪婪最大最小爬山算法、K2算法、Behjati等人提出的算法和C-IK2模型在ASIA網(wǎng)絡(luò)的10個(gè)隨機(jī)數(shù)據(jù)集上達(dá)到的得分的平均值。表5中粗體值表示該算法部分最佳結(jié)果。結(jié)果顯示,C-IK2模型在ASIA數(shù)據(jù)集上網(wǎng)絡(luò)結(jié)構(gòu)得分較高。

表5 ASIA數(shù)據(jù)集BIC得分

將C-IK2模型應(yīng)用到實(shí)際的教育測(cè)試記錄數(shù)據(jù)集中,經(jīng)過專家分析,將其聚類為5簇。分別使用K-means、Birch和高斯混合聚類算法進(jìn)行分簇,其結(jié)果如表6所示。實(shí)驗(yàn)表明,使用Birch聚類算法的Calinski_Harabasz的分?jǐn)?shù)較高,說明使用Birch聚類算法進(jìn)行分簇,能有效地區(qū)分學(xué)生對(duì)概念的理解程度。

表6 聚類算法及評(píng)價(jià)結(jié)果

Birch聚類算法分簇結(jié)果如表7所示。對(duì)每簇?cái)?shù)據(jù)進(jìn)行分析,使用C-IK2模型與基于評(píng)分的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)方法進(jìn)行了比較: GOBNILP算法、貪婪爬山搜索算法、貪婪最大最小爬山算法、K2算法。

表7 聚類分簇結(jié)果

實(shí)驗(yàn)為了與這四個(gè)算法進(jìn)行比較,記錄了每個(gè)算法找到的均值結(jié)構(gòu)網(wǎng)絡(luò)得分?？傮w上,C-IK2對(duì)K2 算法在基于教育測(cè)試記錄上有提高,并且隨著樣本的增加,這種提高越明顯,具體如圖2所示。

圖2 K2算法和C-IK2模型BIC精度對(duì)比

表8是C-IK2模型和基于評(píng)分的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)方法在教育測(cè)試記錄數(shù)據(jù)中的BIC精度結(jié)果,其中黑色粗體表示每個(gè)數(shù)據(jù)在數(shù)據(jù)集所得到最佳結(jié)果。C-IK2模型在BIC精度方面總體上優(yōu)于GOBNILP算法、貪婪爬山搜索算法、貪婪最大最小爬山算法和K2算法。其中,Bi concept map2數(shù)據(jù)集上貪婪爬山算法的精度最優(yōu),考慮其原因是在數(shù)據(jù)集較小時(shí),貪婪爬山搜索算法的BIC 網(wǎng)絡(luò)質(zhì)量分?jǐn)?shù)優(yōu)于其他算法。

表8 概念圖BIC得分

實(shí)驗(yàn)通過時(shí)間復(fù)雜度來對(duì)比K2算法和C-IK2算法,進(jìn)行10次選取其時(shí)間的平均值。其中實(shí)驗(yàn)中所對(duì)比的時(shí)間復(fù)雜度是構(gòu)建概念圖過程的時(shí)間復(fù)雜度,不包含構(gòu)建序列過程。如表9所示,C-IK2的時(shí)間復(fù)雜度比K2的時(shí)間復(fù)雜度少,說明C-IK2算法過程中生成的有效序列,能減少K2算法的搜索時(shí)間,提高K2算法的效率,高效生成概念圖。

表9 時(shí)間復(fù)雜度比較

實(shí)驗(yàn)改變數(shù)據(jù)Bi_concept_map1變量和數(shù)據(jù)Bi_concept_map2變量順序得到Bi_concept_map11、Bi_concept_map12、Bi_concept_map13、Bi_concept_map21、Bi_concept_map22和Bi_concept_map23,對(duì)比K2算法和C-IK2算法,結(jié)果如表10所示。從表10中可以看出,K2算法與C-IK2算法的BIC值都受數(shù)據(jù)集中變量位置的影響,但是C-IK2算法的BIC值比K2算法的BIC值高。

表10 改變變量位置的BIC比較

3.4 概念圖分析

實(shí)驗(yàn)使用LPG算法、K2算法和C-IK2算法生成概念圖,選取其中兩個(gè)簇概念圖進(jìn)行分析。LPG算法生成簇1和簇3的概念圖一致,如圖3所示。概念圖能清晰表示概念之間的相關(guān)關(guān)系,卻無法判斷從何處開始學(xué)習(xí)。此外,簇1與簇3生成的概念圖相同,更進(jìn)一步驗(yàn)證了。該算法只考慮了概念間關(guān)系,無法指導(dǎo)教師教學(xué)。圖4、圖5是利用K2算法生成的概念圖,在由K2算法生成的概念圖中,簇1和簇3以概念1作為根節(jié)點(diǎn),這是由于生成概念圖時(shí)只以遞增作為輸入序列,因此無法進(jìn)行個(gè)性化教學(xué)。為改進(jìn)上述缺點(diǎn),實(shí)驗(yàn)采用C-IK2模型自動(dòng)生成概念圖。圖6、圖7是由C-IK2模型生成的概念圖,從圖中可以看出,由C-IK2生成的概念圖,簇1和簇3分別以17和14作為根節(jié)點(diǎn),這是由于該算法考慮了不同節(jié)點(diǎn)之間的關(guān)系,以此作為生成概念圖的依據(jù)。同時(shí),圖6、圖7概念圖具有層次結(jié)構(gòu),能有效判斷出概念學(xué)習(xí)的順序。在實(shí)際學(xué)習(xí)中,不同學(xué)習(xí)群體的學(xué)習(xí)能力和理解具有差異,C-IK2模型能夠針對(duì)不同學(xué)習(xí)群體的學(xué)習(xí)者繪制個(gè)性化概念圖,指導(dǎo)教師開展個(gè)性化教育。

圖3 LPG算法生成簇1和 簇3概念圖

圖4 K2算法生成簇1概念圖

圖5 K2算法生成簇3概念圖

圖6 C-IK2模型生成簇1概念圖

圖7 C-IK2模型生成簇3概念圖

具體分析C-IK2生成概念圖,以圖6為例,教師在教導(dǎo)簇1的學(xué)生時(shí)可以首先學(xué)習(xí)概念17,接著教導(dǎo)概念12、9、20。這三個(gè)概念的教導(dǎo)可在同一節(jié)課中完成,也可分開教導(dǎo),但是要注意必須學(xué)習(xí)完概念9,20才可以學(xué)習(xí)概念14,而概念8、20、21、22 在學(xué)習(xí)完概念20之后才可以學(xué)習(xí)。概念5、18、11則需要學(xué)完概念14和20以后才能學(xué)習(xí)。概念23不僅與概念22有直接關(guān)系,還與概念20有直接關(guān)系,因此在教學(xué)過程中,可以適當(dāng)復(fù)習(xí)概念20的內(nèi)容,教師再教導(dǎo)概念23以幫助學(xué)生構(gòu)建知識(shí)點(diǎn)的聯(lián)系,更好地理解概念。教師在教導(dǎo)完上述概念后,可教導(dǎo)概念1、10、26,接著教導(dǎo)概念13、6、19、25,最后教導(dǎo)概念29、27、24。由于7、15、16、28這四個(gè)概念與其他概念相關(guān)性并不大,可以選擇任意時(shí)候進(jìn)行教學(xué)。此外,教師在教學(xué)過程中可以按照縱向來教學(xué),如某一節(jié)課教導(dǎo)概念17、20、8,可以讓學(xué)生了解概念之間的關(guān)系;也可以按照橫向教學(xué),如教導(dǎo)12、7、15、16、28,讓學(xué)生掌握幾個(gè)知識(shí)點(diǎn)。由此可見,使用C-IK2概念圖進(jìn)行教學(xué)指導(dǎo)更為靈活。

4 總結(jié)和展望

為了生成具有層次結(jié)構(gòu)特點(diǎn)能反映學(xué)生學(xué)習(xí)能力并能指導(dǎo)教師教學(xué)的概念圖,本文提出了C-IK2模型。該模型具有以下特點(diǎn): ①適應(yīng)性好,對(duì)不同學(xué)生簇有不同概念圖; ②通用性高,算法不僅在教育方面的數(shù)據(jù)集上有良好的結(jié)果,在ASIA公開數(shù)據(jù)集上也有較好的結(jié)果。

盡管C-IK2模型表現(xiàn)良好,但也有一些局限性。C-IK2模型只能對(duì)二分類數(shù)據(jù)有效,并且相應(yīng)關(guān)系只能是一個(gè)問題針對(duì)一個(gè)概念的關(guān)系,然而現(xiàn)實(shí)中,一個(gè)問題可能包含多個(gè)對(duì)應(yīng)概念,因此該模型在靈活性上有所欠缺。此外,該算法受數(shù)據(jù)集變量位置的影響,如何有效構(gòu)建輸入數(shù)據(jù)集,以提高C-IK2算法的圖結(jié)構(gòu)準(zhǔn)確度,是亟待解決的問題。