一種基于遺傳算法的試題推薦方法

徐明遠

（上海工程技術大學電子電氣工程學院，上海 201600）

0 引言

如今已進入大數據時代，智能教育、在線教育發展十分迅速，其可較為便利地為學生提供所需的試題進行練習，從而協助學生對學過的知識進行鞏固。但是，考慮到試題資源數量龐大，學生很難在有限時間內對全部試題都進行練習。因此，如何協助學生在海量的試題資源里找出最合適的試題，是一個非常關鍵的問題［1］。近年來，學者們嘗試將推薦系統相關技術應用于試題推薦等領域。如果使用傳統推薦系統在電子商務方面的應用案例進行類比，則可將學生當作電子商務中的客戶，將試題當作商品，學生考分當作客戶對商品的評分。因此，如果需要預估學生的試題得分，使用試題推薦的方式比較簡潔、容易理解，且能夠獲得較好效果［2］。

通過分析傳統推薦系統可發現，基于協同過濾的算法是運用最廣泛的一種算法，其分成兩個類別［3］：一是以近鄰為基礎的協同過濾法，該方法主要通過參照學生的歷史答題情況，求出不同學生之間的近似度，由此找出最為近似的學生，然后根據近似學生的得分情況預估目標學生的得分，最終參照預測的得分數據進行相應的試題推薦工作；二是以遺傳算法模型為基礎的協同過濾。該方法通過矩陣分解方式對學生與試題進行相應分解，形成一組有關隱藏因子的影響因素，由此構建關于學生與試題二者關系的低維矩陣，并展示出二者在低維空間內的表現情況，從而預估學生的試題分值，最后參照預估分值實施對應的試題推薦工作。

認知診斷理論作為教育與心理測量學科中新一代測量理論的核心，主要通過認知診斷模型對被試的作答數據進行分析研究，發掘學生潛在、不可直接觀察的知識狀態與作答反應模式之間的聯系，為表達學生的知識狀態帶來便利［4］。

將認知診斷方法與遺傳算法相結合應用于試題推薦領域，既能很好地解釋算法的合理性，又能提高試題推薦的準確性，在在線學習越來越普遍的今天，提供了試題推薦的一種優化方案。

1 相關研究

為準確診斷學生的知識狀態，研究者們對認知診斷模型進行了深入研究。如文獻［5］提出規則空間模型，通過轉換被試對試題的反應模式，得到其試題掌握情況與知識狀態，該方法具有較高準確性，但由于專家標定具有主觀性，應用范圍較為局限；文獻［6］提出先確定屬性層級關系，再對學生知識狀態進行診斷的屬性層級模型，進一步提高了認知診斷模型的準確性，但該診斷方式仍具有一些誤差。本文采用的DINA 認知診斷模型在考慮屬性層級關系的前提下，加入被試作答試題時猜測與失誤的概率，相比其他模型能更準確地診斷被試的知識結構。

結合認知診斷模型，根據學生的知識結構進行試題推薦，使推薦更具有合理性，是當下的研究熱點。文獻［7］通過獲取學生的學習方式、知識狀態和學習方法等信息，提出一種個性化試題推薦方法；文獻［8］結合使用多級屬性評分認知診斷模型和遺傳算法模型，根據學生信息進行動態試題推薦。本文將DINA 模型診斷出的知識狀態作為試題推薦的先驗知識，從知識結構的角度進行分析，結合隱含語義分析（LSA）對試題數據進行處理，結果表明，使用遺傳算法得到的試題推薦結果相比傳統方法更加準確。

2 認知診斷

2.1 認知診斷理論研究

從認知心理學方面進行分析，認知診斷模型能夠更好地從知識點這個層級針對學生的認知形態創建相關模型，并輔助學生進行高效的學習規劃。目前的認知診斷模型非常多，主要從兩個層面對其進行分類：①對于認知診斷模型而言，可分成離散型、連續型；②對于認知診斷方法而言，可分成一維技能、多維技能［9］。在很多認知診斷模型中，使用最普遍的是有關一維連續認知建模的項目反應理論（IRT）模型，以及關于多維離散認知建模的DINA模型［10］。

其中，IRT 只是根據學生的答題狀況對學生實施建模，從而得到一維連續能力值，并通過相關能力值展示出學生的綜合實力。IRT 模型將學生設計為一個具備單一能力值的對象，然而在現實應用過程中，考慮到不同試題考察的知識范疇不同，容易導致模型無法體現學生在不同知識方面的實力差距。對于這些情況，有些學者提出了補償性多維IRT模型MIRT-C［11］，以及非補償性多維IRT模型MIRT-NC，通過這些模型能夠從多個方面針對學生實力進行建模操作［12］。

關于受推薦試題對于學生真實難度的問題，本文通過準確作答率指標SR 進行相應評測，設置難度區間后，學生認真作答了全部推薦試題，之后求出準確作答的比例。分母為推薦試題總數，分子為學生正確作答的推薦試題數量，即：

2.2 評價方法

聚類分析是一種無監督的學習方式，如何對聚類結果進行客觀、公正的評價，是聚類問題中最關鍵的研究內容之一［13］。常用的聚類結果評價方法較多，包括外部評價法與內部評價法，這兩種評價法都是以統計測試為基礎，在運算復雜性較高時，以聚類質量指數衡量數據集與已知架構的匹配度。另外還包括相對評價法，在數據集分類結構未知時可采用這種評價法。該評價法其實是找出一個聚類算法，并且確保在相應的假定與參數條件下可定義的最佳聚類結果。

本文采用外部評價法對試題數據進行處理，以一類提前指定的架構為基礎，這類架構能夠體現出人們對數據集聚類架構最直觀的認知，并且所有數據項的分類均處于已知狀態［14］。常見的外部評價方法有熵（Entropy）方法、特征測量（F-measure）等。

（1）熵。將聚類結果設定成CS（Clustering Solution），聚簇j 屬于分類i 的概率為Pij。聚簇指聚類算法得到的類簇，分類指原始數據集中數據的分類。聚簇j的熵定義為：

聚類結果的總熵可定義為各個聚簇熵的加權和，即：

其中，nj代表聚簇j的大小，k 代表聚簇數量，n代表全部對象數量。

對于最佳的聚類結果而言，聚簇內所有試題均源自于單獨一個分類，此刻熵是0。如果熵值較小，則聚類結果通常較好。

（2）特征測量。特征測量的優劣主要與查準率（Precision）、查全率（Recall）兩個參數相關。對于聚類i和分類j，分類j的F（F-measure）值定義如下：

假定｛relevant｝代表與分類j有關的試題集合，｛retrieved｝代表聚類i內全部試題集合，｛relevant｝∩｛retrieved｝代表聚類i中屬于分類j的試題集合，查準率、查全率依次根據以下方法獲?。?/p>

查準率（Precision）：聚類i中屬于分類j的試題數量與聚類i中所有試題數量的比值。

查全率（recall）：聚類i中屬于分類j的試題數量與分類j中全部試題數量的比值。

所有對象的特征測量為所有分類F值的平均值：

其中，n為試題數目。由特征測量的定義可知，F-measure值越大，聚類效果越好。

3 基于遺傳算法的聚類集成

3.1 遺傳算法

遺傳算法（Genetic Algorithms，GA）能夠對生物進化規律進行模擬，屬于一類隨機化的搜尋方式，其對于架構化的對象直接實施操控，具備內在并行性，并且具備全局尋優的能力；能夠選用概率化的尋優方式，可通過自動方式獲得相應的搜尋空間并實施相應的引導優化，通過自適應方式調節搜尋方向［15-16］。其首先通過編碼，采用字符串表達實際問題，這種字符串相當于遺傳學中的染色體（Chromosome），從而將解空間的解數據轉換成遺傳算法可處理的遺傳空間的基因型串結構數據，其中字符串的每一位稱為基因位，每個字符串都是問題的一個解（不一定是最優解），每一代所產生的字符串個體集合稱為種群（Population）；然后利用選擇（Selection）、交叉（Crossover）、變異（Mutation）等操作，使優者繁殖、劣者淘汰，一代一代重復操作，最終找到最優解［17］。

遺傳算法基礎流程如下：

Step1：選取相應的編碼樣式，設置好交叉率、突變率等參數，并設置進化代數Gen=0。

Step2：對種群實施初始化操作，從而獲取P（Gen）。

Step3：參照目標函數求出種群內所有染色體的適應度。

Step4：Gen=Gen+1。

Step5：假如Gen 值能夠符合設置的相關要求，則轉至Step11，否則轉至Step6。

Step6：從P（Gen-1）中找出兩個成員，其中選定的概率及染色體適應度呈正比例關系。

Step7：根據提前設置好的雜交率，從所有選定染色體的一個隨機點上實施對應的雜交處理。

Step8：根據提前設置好的變異率，從所有選定染色體上隨機確認一個點，并轉變對應的位值。

Step9：選定變異后的個體與P（Gen-1）群體內具有較大適應度的染色體，構成種群P（Gen）。

Step10：轉至Step3。

Step11：導出種群P（Gen）內具有最大適應度的個體，并終止算法。

3.2 基于遺傳算法的聚類集成方法

對于基于遺傳算法的聚類集成方法（CEGA）而言，其基礎思想為：對于數據集實施H 次聚類算法［18］（如Kmeans），從而形成H個聚類成員Π={π1，π2，...，πH}，之后，由于基聚類獲取的聚類成員仍存在一定錯誤，因此能夠對聚類成員進行相應的量化處理，得到：

在聚類成員集成階段，將Π={π1，π2，...，πH}作為遺傳算法的初始種群，參照遺傳算法的相關流程實施相應的進化處置，將獲得的最優染色體作為最終聚類結果［19］。

CEGA 算法流程可參見圖1。

Fig.1 CEGA algorithm flow圖1 CEGA算法流程

3.3 聚類成員生成

在該環節可選用經常使用的K-means 算法生成相應的聚類成員，對于初始數據集D={d1，d2，...，dn}實施H 次聚類（將參數設定成k），從而獲取相應的聚類成員集合Π′=Π′為H×n二維數組，其中：

3.4 聚類成員集成

3.4.1 染色體編碼

聚類成員集合選用實數編碼樣式進行編碼操作，對于實數編碼而言，其能夠提高編碼精度，降低運算復雜度。一條染色體對應一個聚類成員，染色體基因對應聚類成員的簇標號。很明顯，在初始數據集內，數據對象數目就是染色體長度。公式（11）即代表一條染色體：

其中，為統一后的簇標號，表示在第i個聚類成員中的第j個數據對象被劃分到簇中。

3.4.2 目標函數

遺傳算法中最關鍵的是目標函數，其能夠指引群體進化方向，確保染色體朝著便于問題妥善處理的方向發展。求聚類問題的解就是要找出一個聚類結果，確保接近的數據被分在同一簇中，不同數據則分在差別的簇中。采用有關聚類結果的綜合評價指數（OCQ）求出任意一條染色體的聚類效果，并且傳回一個適應度。

3.4.3 雜交函數及突變函數設定

在相關進化流程內，算法時常能夠收斂至局部最佳點，卻無法實現全局最佳，因此需要增添與進化代數關聯的交叉率、突變率等參數，以提升算法在全局方面的搜索實力。

雜交函數相關定義如式（12）所示。

其中，Pctemp=為設置的最大交叉率，Pcmin為設置的最小交叉率，應當保證交叉率在最大與最小值區間內進行改變。

突變函數相關定義如式（13）所示。

4 試題推薦分析

4.1 隱含語義分析

隱含語義分析（Latent Semantic Analysis，LSA）是一類科學、合理的降維方式，可實現迅速降維，同時凸顯出文本之間的語義關系［22］。

盡管LSA 是用試題中包含的詞表示試題語義，能夠最大限度掩蓋試題的語義架構，但考慮到試題內關于用詞的多元化特性，LSA 經過奇異值分解及取k 秩近似矩陣后，不但能減少原詞條試題矩陣內涵蓋的噪聲，從而更好地凸現詞條與試題間的語義關聯，而且能減小試題詞條的向量空間，從而降低運算復雜度，提升檢索工作效率［23］。對于文本詞條矩陣Wn×m，則是參照矩陣奇異值分解相關理論，將W 分解成3個矩陣的乘積：

其中，U、V、A 分別代表矩陣n×k、m×k、k×k，k 代表矩陣W 的秩，其屬于1 個對角矩陣。至于對角線元素，則是矩陣W 的k個奇異值依據遞減次序進行相應排布。

假如在矩陣A 內僅選取前面r 個最大的矩陣，則能獲取相應的對角矩陣Ar。相應地，如果選定U、V 最前面的r列，則能獲取Ur、Vr。參照這3 個矩陣組建得到r-秩矩陣Wr，如圖2所示。

Fig.2 Constructing r-Rank matrix of W圖2 構建W的r-秩矩陣

Wr是W 的r 秩近似矩陣，Ur與Vr列向量屬于正交向量，依次代表文本向量、詞向量，通過Wr近似代表文本詞條矩陣W 以完成降維操作。在完成降維處理的空間里，對象之間則是通過詞條的全局應用樣式進行關聯。

4.2 基于遺傳算法的文本聚類集成算法模型

CEGA 作為一種高效的聚類集成算法，可結合LSA 應用于文本聚類中，形成一種新的基于遺傳算法的文本聚類集成方法TCEGA（Test Clustering Ensemble Model Based on Genetic Algorithm）。該方法首先通過LSA 對文本特征矩陣進行降維處理，然后用CEGA 對降維后的矩陣進行聚類操作。整個算法過程簡單、高效。TCEGA 具體步驟如下：

Step1：對于文本進行相關的預處置，并提取詞頻特征矩陣，通過向量空間模型展示出相關文本特征。

Step2：對詞頻特征矩陣進行相應轉換，從而形成TF.IDF，并且進行對應的規范化處置。

Step3：運用LSA 理論對文本特征矩陣作降維處理，得到降維后的矩陣D。

Step4：對矩陣D 執行CEGA 算法。

Step5：輸出最優染色體作為聚類結果。

4.3 實驗結果與分析

4.3.1 實驗數據與評價標準

實驗數據由5 類試題庫數據組成，每個試題庫數據為2722維，采用平均準確率作為實驗評價標準。

4.3.2 實驗結果與分析

在第一組實驗中，在原始文本特征矩陣數據上運行21次LSA 降維算法，每次降維程度不同，得到21 個不同維數的降維后的數據矩陣。在相同的軟件與硬件條件下，在這些數據矩陣及原始數據矩陣上分別運行TCEGA 聚類算法，記錄算法運行時間與聚類結果的平均準確率，根據記錄的數據驗證LSA 對聚類結果平均準確率及聚類速率的影響。表1 給出了不同數據維數情況下TCEGA 的運行時間與聚類結果平均準確率。

Table 1 Relationship among data dimension，algorithm running time and clustering results表1 數據維數與算法運行時間及聚類結果的關系

圖3 顯示了平均準確率與數據維數的關系，x 軸代表文本特征矩陣維數，y 軸代表TCEGA 聚類結果的平均準確率。圖4 顯示了TCEGA 平均運行時間與文本特征矩陣維數的關系，x 軸代表文本特征矩陣維數，y 軸代表算法每代平均進化時間（單位：s）。

在第二組實驗中，為驗證TCEGA 文本聚類方法的高效性，將常用的聚類算法如K-means、SOM 與TCEGA 作對比實驗。首先用LSA 將文本特征矩陣由2 722 維降到191維，然后采用K-means 算法、SOM 與TCEGA 分別對降維后的數據矩陣進行聚類操作，并選用平均準確率作為聚類結果評價標準。

表2 給出了標準K-means 算法、SOM 與TCEGA 聚類結果的平均準確率。

實驗結果表明，TCEGA 比K-means 與SOM 可獲得更好的聚類結果，通過集成方法達到了提高聚類性能的目的。

Fig.3 Relationship between average accuracy and data dimension圖3 平均準確率與數據維數的關系

Fig.4 Relationship between average evolution time per generation and data dimension of TCEGA圖4 TCEGA每代平均進化時間與數據維數的關系

Table 2 Average accuracy of clustering results of each algorithm表2 各算法聚類結果平均準確率

學生知識點掌握程度示例如圖5 所示。由圖可知，在DINA 模型中對學生的知識狀態進行診斷，被試A 對S1、S4、S6等知識點的掌握情況較好，對S3、S8等知識點的掌握情況較差；被試B 則是對S2、S7等知識點的掌握情況較好，對S1、S5等知識點的掌握情況較差。

將被試知識點掌握程度作為算法模型的先驗知識參與試題推薦，從隱含語義分析的角度對試題中的信息進行篩選，并采用TCEGA 算法實現試題選取與推薦。

Fig.5 Examples of students'mastery of knowledge points圖5 學生知識點掌握程度示例

本文提出個性化試題推薦的方式，如果推薦的試題難度較大，則根據所有學生的個性化學習情況為其推薦對應的試題，對于試題的推薦結果會具備更好的可解釋性。

5 結語

本文通過對認知診斷模型與遺傳算法的深入研究，提出一種基于遺傳算法的個性化試題推薦方法。該方法結合學生的知識結構與試題的文本集成信息進行預測，在使用遺傳算法進行試題推薦時，既考慮了群組學生在學習方面相近的情形，又改善了遺傳算法個性化程度不高的問題。最終實驗結果表明，在使用DINA 模型診斷出學生的知識掌握程度后，TCEGA 算法的試題推薦準確性優于傳統推薦算法。

雖然本文通過結合認知診斷模型與遺傳算法的方式增強了試題推薦的可解釋性，提高了試題推薦的準確性，有助于在線學習模式的推廣與應用，但將TCEGA 方法廣泛應用于在線學習領域仍需進一步深入研究與探索。是否可引入更多學生與試題信息作為先驗知識以提高算法準確性，是否可在不同學習場景應用該推薦方法，更有針對性地實現個性化在線學習與測評，將是后續研究重點。