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

徐明遠(yuǎn)

（上海工程技術(shù)大學(xué)電子電氣工程學(xué)院，上海 201600）

0 引言

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

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

認(rèn)知診斷理論作為教育與心理測量學(xué)科中新一代測量理論的核心，主要通過認(rèn)知診斷模型對被試的作答數(shù)據(jù)進行分析研究，發(fā)掘?qū)W生潛在、不可直接觀察的知識狀態(tài)與作答反應(yīng)模式之間的聯(lián)系，為表達學(xué)生的知識狀態(tài)帶來便利［4］。

將認(rèn)知診斷方法與遺傳算法相結(jié)合應(yīng)用于試題推薦領(lǐng)域，既能很好地解釋算法的合理性，又能提高試題推薦的準(zhǔn)確性，在在線學(xué)習(xí)越來越普遍的今天，提供了試題推薦的一種優(yōu)化方案。

1 相關(guān)研究

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

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

2 認(rèn)知診斷

2.1 認(rèn)知診斷理論研究

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

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

關(guān)于受推薦試題對于學(xué)生真實難度的問題，本文通過準(zhǔn)確作答率指標(biāo)SR 進行相應(yīng)評測，設(shè)置難度區(qū)間后，學(xué)生認(rèn)真作答了全部推薦試題，之后求出準(zhǔn)確作答的比例。分母為推薦試題總數(shù)，分子為學(xué)生正確作答的推薦試題數(shù)量，即：

2.2 評價方法

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

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

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

聚類結(jié)果的總熵可定義為各個聚簇熵的加權(quán)和，即：

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

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

（2）特征測量。特征測量的優(yōu)劣主要與查準(zhǔn)率（Precision）、查全率（Recall）兩個參數(shù)相關(guān)。對于聚類i和分類j，分類j的F（F-measure）值定義如下：

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

查準(zhǔn)率（Precision）：聚類i中屬于分類j的試題數(shù)量與聚類i中所有試題數(shù)量的比值。

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

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

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

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

3.1 遺傳算法

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

遺傳算法基礎(chǔ)流程如下：

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

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

Step3：參照目標(biāo)函數(shù)求出種群內(nèi)所有染色體的適應(yīng)度。

Step4：Gen=Gen+1。

Step5：假如Gen 值能夠符合設(shè)置的相關(guān)要求，則轉(zhuǎn)至Step11，否則轉(zhuǎn)至Step6。

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

Step7：根據(jù)提前設(shè)置好的雜交率，從所有選定染色體的一個隨機點上實施對應(yīng)的雜交處理。

Step8：根據(jù)提前設(shè)置好的變異率，從所有選定染色體上隨機確認(rèn)一個點，并轉(zhuǎn)變對應(yīng)的位值。

Step9：選定變異后的個體與P（Gen-1）群體內(nèi)具有較大適應(yīng)度的染色體，構(gòu)成種群P（Gen）。

Step10：轉(zhuǎn)至Step3。

Step11：導(dǎo)出種群P（Gen）內(nèi)具有最大適應(yīng)度的個體，并終止算法。

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

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

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

CEGA 算法流程可參見圖1。

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

3.3 聚類成員生成

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

3.4 聚類成員集成

3.4.1 染色體編碼

聚類成員集合選用實數(shù)編碼樣式進行編碼操作，對于實數(shù)編碼而言，其能夠提高編碼精度，降低運算復(fù)雜度。一條染色體對應(yīng)一個聚類成員，染色體基因?qū)?yīng)聚類成員的簇標(biāo)號。很明顯，在初始數(shù)據(jù)集內(nèi)，數(shù)據(jù)對象數(shù)目就是染色體長度。公式（11）即代表一條染色體：

其中，為統(tǒng)一后的簇標(biāo)號，表示在第i個聚類成員中的第j個數(shù)據(jù)對象被劃分到簇中。

3.4.2 目標(biāo)函數(shù)

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

3.4.3 雜交函數(shù)及突變函數(shù)設(shè)定

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

雜交函數(shù)相關(guān)定義如式（12）所示。

其中，Pctemp=為設(shè)置的最大交叉率，Pcmin為設(shè)置的最小交叉率，應(yīng)當(dāng)保證交叉率在最大與最小值區(qū)間內(nèi)進行改變。

突變函數(shù)相關(guān)定義如式（13）所示。

4 試題推薦分析

4.1 隱含語義分析

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

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

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

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

Fig.2 Constructing r-Rank matrix of W圖2 構(gòu)建W的r-秩矩陣

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

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

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

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

Step2：對詞頻特征矩陣進行相應(yīng)轉(zhuǎn)換，從而形成TF.IDF，并且進行對應(yīng)的規(guī)范化處置。

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

Step4：對矩陣D 執(zhí)行CEGA 算法。

Step5：輸出最優(yōu)染色體作為聚類結(jié)果。

4.3 實驗結(jié)果與分析

4.3.1 實驗數(shù)據(jù)與評價標(biāo)準(zhǔn)

實驗數(shù)據(jù)由5 類試題庫數(shù)據(jù)組成，每個試題庫數(shù)據(jù)為2722維，采用平均準(zhǔn)確率作為實驗評價標(biāo)準(zhǔn)。

4.3.2 實驗結(jié)果與分析

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

Table 1 Relationship among data dimension，algorithm running time and clustering results表1 數(shù)據(jù)維數(shù)與算法運行時間及聚類結(jié)果的關(guān)系

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

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

表2 給出了標(biāo)準(zhǔn)K-means 算法、SOM 與TCEGA 聚類結(jié)果的平均準(zhǔn)確率。

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

Fig.3 Relationship between average accuracy and data dimension圖3 平均準(zhǔn)確率與數(shù)據(jù)維數(shù)的關(guān)系

Fig.4 Relationship between average evolution time per generation and data dimension of TCEGA圖4 TCEGA每代平均進化時間與數(shù)據(jù)維數(shù)的關(guān)系

Table 2 Average accuracy of clustering results of each algorithm表2 各算法聚類結(jié)果平均準(zhǔn)確率

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

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

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

本文提出個性化試題推薦的方式，如果推薦的試題難度較大，則根據(jù)所有學(xué)生的個性化學(xué)習(xí)情況為其推薦對應(yīng)的試題，對于試題的推薦結(jié)果會具備更好的可解釋性。

5 結(jié)語

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

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