基于演化聚類的學習者知識跟蹤模型研究

郭章

（桂林電子科技大學計算機與信息安全學院，桂林541004）

0 引言

智能教學系統作為現代化教育的基礎設施，有著舉足輕重的地位，其利用人工智能技術在沒有人員指導的情況下幫助學習者獲取知識。而學習者模型是智能教學系統的核心組件之一[1]，它利用計算機模型，根據學生和智能教學系統之間的交互數據，來自動衡量學生的知識水平，以便能及時地對學習者的表現進行預測和對教學方案做出指導性決策。在大數據時代，一個精確的、個性化的學習者模型成為教育信息化發展的必然需求。

1 相關工作

使用最為廣泛使用的學習者模型是Corbett 和An?derson[2]在1995 年提出的貝葉斯知識跟蹤模型（Bayes?ian Knowledge Tracing, BKT），它利用隱馬爾可夫模型對學生回答問題的正誤情況進行建模。隨后出現了許多基于此模型改進的更高效的模型[3-5]。其主要改進的方向有兩點：第一為更高的預測精度，第二為更好地對教學做出決策支持。傳統的貝葉斯知識跟蹤模型只針對特定的技能進行建模，也就是說它認為所有學生都具有相同的學習能力和相同的初始技能。而通常不同的學生的學習能力和知識水平都是不一樣的，于是一些學者提出了個性化的貝葉斯知識跟蹤模型，他們從學習者的層面對模型提出了一些個性化的參數。文獻[6]使用一些啟發式的方式來計算單個學生的個性化參數，比如根據該學生回答問題的正確率，第一次回答問題的正誤情況以及隨機設置。文獻[7]使用梯度搜索的方式在訓練模型的時候得到個性化的參數。文獻[8]直接針對每個學生的每個技能訓練出單獨的模型,由于每個學生在每個技能下回答問題數量都有限，因此這種方式難以訓練出較好的模型，并且會導致參數過多的問題。

實際上，個性化的貝葉斯知識跟蹤模型只能預測當前學生的學習表現，而難以預測新學生的情況。通常，他們將一個學生的回答問題的序列數據的最后幾題作為測試集，剩余數據作為訓練集。這個問題稱為冷啟動問題，這類模型在實際使用中就會受到較大的限制。于是一些學者提出了使用聚類來改進傳統的學習者模型[9,10]，其思想在于將學習者按照知識水平的不同分成不同的群體。但他們并未考慮教育領域的數據的特點，而只使用了常見的靜態聚類算法，例如K-means 和譜聚類等，對模型的性能提升并不明顯。通常我們選擇聚類算法會考慮兩點：聚類目的和數據特點。在智能教學系統中，聚類對象為所有的學習者。文獻[11]分析了教育領域數據的特點，并對主流的聚類算法進行了評估。

通過總結前人的工作發現，目前的學習者知識跟蹤模型存在如下不足：（1）模型的個性化能力不足，未考慮學習者個體之間的差異。（2）未考慮到學習者的交互數據具有時間動態特性，即學習者的知識掌握水平是隨著時間平穩變化的。（3）存在冷啟動的問題，即只能預測當前學生的表現，而不能預測新學生的表現。（4）訓練貝葉斯知識跟蹤模型的EM 算法易陷入局部最優解，從而導致出現模型退化的現象。這些問題不僅會影響模型的性能，還會限制它的使用范圍。

為了解決上述提到的問題，本文提出了一種基于演化聚類和貝葉斯網絡的知識跟蹤模型（ECBKT）。該模型將演化聚類算法作為傳統知識跟蹤模型的預處理步驟，根據學習者的學習數據，在每一個時間點上對學習者進行動態的聚類，得到不同知識水平的學生群體。接著將其傳入貝葉斯知識跟蹤模型進行訓練，得到多個不同的預測模型。最后選擇和新學生最相似的簇訓練出來的模型來進行預測。在演化聚類部分，具體實現了K-means 和層次聚類的演化擴展。在模型訓練部分，使用學習曲線技術來調整模型的參數，從而避免模型退化。

2 ECBKT模型

演化聚類是一種常用于社區檢測的動態聚類技術[12,13]。該框架需要結合傳統的靜態聚類算法，并對其在時間序列上進行擴展。它通過向靜態聚類的目標函數增加時間平滑的懲罰項，從而避免相鄰時刻的聚類結果相差較大。該聚類框架具有平滑性、一致性和受噪音干擾小等優點。本文具體實現了K-means 和凝聚層次聚類這兩種靜態聚類的演化擴展。在不同的算法里面，實現了各自的快照質量、歷史代價以及相似度的計算。在聚類結束后，將不同的學習者群體傳入貝葉斯知識跟蹤模型，得到多個知識跟蹤模型。通常訓練貝葉斯網絡使用的EM 算法對初始值非常敏感，沒有合理的初始值設置，易導致陷入局部最大值的問題，從而導致模型性能退化。一些學者往往使用隨機初始化和經驗設置的方式，效果不夠理想，因此本文提出使用學習曲線結合經驗的方式來調整參數。

2.1 問題定義

給定所有學生表現的數據集Uk={ui|,i=1,2,3,…,n}，其中k 為知識點的編號，n 為學生的數量。在特定技能下每個學生的表現數據定義為其觀測序列：ui,T={o1,o2,o3,…,oT},其中T 為該學生回答問題的個數，并且每個學生的T 值可以不相同。定義t 時刻前所有學生的表現數據為Ut?UK。令在t 時刻的聚類結果為Ct，則可以得到一串聚類結果：C1,C2,…,CT,我們的目的在于使每一時刻的聚類質量最高。因此將當前t時刻的聚類質量定義為公式（1）所示。

其中sq 函數為快照質量（snapshot quality），hc 函數為歷史代價（history cost），cp 為歷史代價所占比重，Mt為t 時刻的相似度矩陣。快照質量衡量當前時刻學生表現數據所產生的聚類質量，而歷史代價衡量前一時刻的聚類結果對當前時刻產生的影響。為了提高整體聚類質量，需要有較高的快照質量和較低的歷史代價。

將學習者的知識水平定義為：p( Lt)u，表示在t 時刻學習者u 對知識點已經掌握的概率。概率p( T )為學習者的知識水平從未掌握到已經掌握的概率。此外，定義學習者回答問題猜對的概率為p( G ),誤答概率p( S )。為正確回答問題的概率。則根據貝葉斯條件概率公式，學習者知識掌握水平的概率和回答對問題的概率計算公式分別為公式（2）和（3）。

其中obs 為學習者表現的實際觀測值。以0.5 為閾值，將進行四舍五入，則能預測下一道題回答結果的正確與否。

2.2 ECBKT算法實現

輸入：學習者的表現序列數據U

輸出：新學習者表現的預測序列

（1）計算出最長序列長度T,和每個學生u 的實際序列長度u.realLength,以及總學生數n

（2）for t →1 to T DO

（3） for u →1 to n DO

（4） if u.realLenth ＜t

（5） 將t 時刻前的學習者表現的平均值加入tempdata

（6） else

（7） 將u.realLength 前數據加入tempdata

（8） END for

（9） 使用tempdata 計算t 時刻的聚類結果Ct

（10）END FOR

（11）使用知識跟蹤模型訓練出多個模型

（12）模型參數優化

（13）找到和新學生最相似的簇進行預測

2.3 基于K-means的模型實現

由公式（1）可知，要使當前時刻的聚類質量最高，需要有較高的快照質量和較低的歷史代價。標準K-means 使用貪心策略來分配簇標簽，以及使用求均值的方式來計算簇心值。樣本點之間的距離使用歐氏距離，則構造其相似度矩陣為Mt( i,j )=‖ xi,t-xj,t‖,定義t時刻的簇心集合為：Ct={c1,t,c2,t,…},將快照質量和歷史代價定義為如下公式：

其中U 是所有學生數據的集合，C 是當前時刻的簇心集合。C'為前一時刻的簇心集合，即C'=Ct-1。

在演化K-means 中，仍然使用貪心策略來劃分簇，即選擇離樣本最近的簇作為樣本的標簽。對于簇心的計算，則要用到歷史代價。定義t 時刻簇j 的樣本數為：= |closest(j) |,定義相鄰時刻樣本數量的相對大小為：γ=+。簇心的更新公式如下：

該公式在計算當前的簇心位置時，利用簇的樣本數相對變化大小，考慮到了前一時刻該簇心簇情況。通過實驗發現，由于受到異常值和統計分布的影響，會出現樣本不均衡的現象。也就是說會出現一些簇的樣本數過多，另一些過少，甚至沒有樣本的情況。當出現樣本為空的情況時，就有可能出現γ 的分母為0 的情況。這些情況會嚴重降低聚類質量，以致影響模型整體表現。

對于聚類結果不平衡的問題，需要使用一些平衡約束的手段。本文采用的方式為對每個簇可包含的樣本數量設置上限的方式。如果一個簇包含的樣本數已經達到了上限，則將新來樣本劃分到其余最近的簇。該方式具有快速、簡單的特點。對于出現空簇導致的γ分母為0 的情況，本文直接將本時刻的簇心參數設置來與前一時刻相同,以此來保證聚類結果的一致性。

2.4 基于層次聚類的算法實現

層次聚類也是一種廣泛使用的聚類技術，使用二叉樹來存儲聚類結果。有兩種產生層次聚類的方法：凝聚和分裂，本文使用凝聚的方式。首先，將每一個樣本都作為一個單獨的簇，然后重復合并兩個最近的簇，每次合并都將簇個數減1，直到達到預定的簇個數或者簇個數到1 為止。

（1）相似度和快照質量的計算

令t 時刻聚類構成的二叉樹為Tt，即Ct=Tt=T,令m1,m2,,…,m|u|-1為樹中的內部結點?？煺召|量的計算公式如下：

其中simM為構成結點m 的樣本之間的相似度。本文使用層次聚類常用的簇間距離計算方式作為相似度的計算方式。常用的度量方式有：單鏈、全鏈、組平均和Ward 方式。其中Ward 方式試圖最小化點到簇心的距離平方和，即選擇使合并后簇的誤差平方和（ESS）最小的合并方式。其計算公式如下：

本文使用Ward 方式來進行簇的合并，因為通過實驗發現其余方式會出現聚類結果嚴重不平衡的現象，其原因在于Ward 方式會優先合并樣本數較少的簇。

（2）歷史代價的計算

歷史代價的計算考慮了前一時刻的聚類結果對當前時刻的影響。首先是兩個樣本點的距離的計算。在未考慮歷史信息時，兩個樣本點之間的距離仍然使用歐式距離，表示為：d( i,j )=‖ xi-xj‖。而在考慮歷史信息后兩個樣本點之間的距離計算公式如下：

其中T'和T 為相鄰時刻的聚類結果，即T'=Tt-1，T=Tt,i 和j 為T'的葉子結點。那么總的歷史代價定義為葉子結點的平均距離，公式如下：

在得到快照質量和歷史代價后，根據公式（1）選擇使總質量最小的簇合并方式來合并簇，以完成層次聚類。

2.5 模型參數優化

貝葉斯知識跟蹤模型的本質是隱馬爾可夫模型，模型的訓練方式有多種，最常用的是EM 算法和網格搜索。由于EM 算法對初始值的設置非常敏感，因此EM 算法容易陷入局部最優值，從而導致模型退化[16]。而網格搜索的計算量大。由于沒有合理的初始值設置方法，只能隨機選擇或者憑借一些經驗來設置。

通過實驗發現轉移概率p（T）的值的大小對模型的預測精度影響非常大，如果設置不合理，則可能會出現預測精度低于50%的情況。因此在使用EM 算法訓練完模型后，還需要對p（T）參數進行調整。本文提出了使用學習曲線的方式來搜索最佳值，即網格搜索。其過程為將p（T）逐漸從0 變化到1，預測出多組序列，選擇一個使預測精度最大的p（T）值。由于只需要對一個參數進行檢索，該方法并不會增加太多的運算時間，卻能有效提高預測精度。

3 實驗與結果分析

3.1 數據集與實驗環境

本 文 數 據 集 來 自ASSISTment（https：//sites.google.com/site/assistmentsdata/），它是一個面向中學生的智能教學系統，本文使用其中的2009 和2015 兩種數據集。該數據集中默認學生一旦掌握某知識點后，則不再回答相關問題了，其特點如表1 所示。

表1 ASSISTment 數據集的特點

可以看出2015 的數據相比2009 的數據具有更多的交互記錄，因為后者包含的學生數量更多。原始數據包含大量無關信息，通過特征選擇篩選出最相關的特征：回答問題數量、正確率、嘗試次數、回答問題的時間和使用提示的次數，然后使用標準化來對數據做無量綱化處理。

本文實驗環境為：Windows 10 操作系統，Intel 酷睿i7 CPU,16G 內存，編程語言為Python 3.7。

3.2 預測與評價指標

為了預測學生的表現，使用學生分層的交叉驗證方式來訓練模型。本文選擇5 折交叉驗證。在訓練出多個知識跟蹤模型后，對于測試集的預測，本文使用和測試集最相似的簇訓練出的模型來進行預測，其過程如圖1 所示。

圖1 交叉驗證及預測過程

本文將演化聚類應用到知識跟蹤模型上，具體實現了K-means 和層次聚類的兩種方式。對比模型包括未使用聚類的標準知識跟蹤模型、使用靜態聚類的知識跟蹤模型以及使用演化聚類的模型?？偣? 種模型，分別是：（1）BKT、（2）BKT+KMS、（3）BKT+HC、（4）ECBKT+KMS、（5）ECBKT+HC。其中BKT 代表標準貝葉斯知識跟蹤模型，ECBKT 代表使用了演化聚類的知識跟蹤模型，KMS 代表K-means 聚類算法，HC 代表層次聚類算法。

本文用到的評價指標有：預測精度（ACC）、均方根誤差（RMSE）和AUC 指標。其中ACC 表示預測正確的題目數占總題目數的比率，RMSE 衡量預測值和真實值之間的偏差。而AUC 為ROC 曲線與坐標軸圍成的面積，它是一種衡量二分類模型性能優劣的指標,越接近1 則表示模型的性能越好。

3.3 結論分析

（1）參數優化分析

通過前面的分析，知道EM 算法易陷入局部最優解，導致模型性能退化，表現為預精度低于50%。對于模型參數的優化，使用學習曲線的方式來找到最佳的p（T）。本實驗隨機從訓練集中選擇3 條數據繪制其變化曲線，如圖2 所示。從數據1 和2 來看，如果p（T）參數設置不合理，將會極大影響模型預測精度。

對于所有數據集，繪制其預測精度的分布圖如圖3所示。從中可以看出，未優化的模型預測精度主要分布在低精度區域，而優化后模型的預測精度更高?？梢钥闯觯瑑灮竽苊黠@提高整體預測精度，因此在后面的分析中均使用已優化的模型。

圖2 p（T）參數對模型性能的影響

圖3 預測精度分布對比圖

（2）預測結果分析

在本實驗中，對每一道題的預測直接得到的是回答正確的概率，然后使用四舍五入的方式將其轉換成二分類結果。預測結果如表2 所示。

從中可以看出，在2009 數據集上演化K-means 的預測精度比K-means 高出2%，演化層次聚類的預測精度比層次聚類高出約2%。層次聚類的預測精度比K-means 高出5%。在RMSE 和AUC 指標上也能得到相似的結果。另外，2015 數據集的整體預測精度高于2009 數據集。

表2 模型預測結果

從實驗結果來看，可以得出如下結論：①使用聚類能有效提高模型的預測精度，其原因在于其充分考慮了學生知識水平的個體差異。②演化聚類的性能要高于對應的靜態聚類方法，因為演化聚類考慮到了學習者的交互數據的時間動態特性，使得模型具有平滑性、一致性和受噪音干擾小等優點。③層次聚類的性能要高于K-means。因為K-means 難以劃分非球形或具有不同尺寸或密度的簇。因此層次聚類更適合教育領域數據分析。

4 結語

本文為了提升知識跟蹤模型的預測能力，以及解決其個性化和冷啟動等問題,提出了一種結合演化聚類和貝葉斯網絡的知識跟蹤模型。該模型考慮了學習者的交互數據具有時間動態特性，在每一個時刻的聚類都使用了歷史信息，使得聚類結果具有一致性、平滑性等優點。并實現了層次聚類和K-means 的演化擴展，包括快照質量和歷史代價算法的實現，以及對聚類不平衡問題的處理。此外，為了避免出現模型退化的現象，對原始數據及參數分布進行了分析，提出了使用學習曲線進行優化的方法，最終使得模型的性能得到較大提升。實驗結果表明，本文提出的模型在各項指標上均優于傳統的模型。因此，本文提出的模型能有效促進學習者在智能教學系統中的收益。