基于Harmonic函數(shù)的自動(dòng)試題標(biāo)注模型

謝 瑩，許榮斌

（安徽大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，合肥 安徽230601）

在目前的高校教學(xué)評(píng)價(jià)工作中，課程科目繁多，試題量大，組卷工作任務(wù)繁重.自動(dòng)試題標(biāo)注是指在組建試題庫(kù)時(shí)對(duì)小部分試題進(jìn)行關(guān)鍵詞分類(lèi)標(biāo)注，建立一個(gè)模型，新加入的試題可以通過(guò)此模型進(jìn)行自動(dòng)標(biāo)注分類(lèi).這項(xiàng)工作可以減輕教師題庫(kù)建設(shè)的工作量，亦可發(fā)展此模型對(duì)試題得分率進(jìn)行預(yù)測(cè)，從而控制組卷的難易程度.由于人工標(biāo)注樣本代價(jià)很大，自動(dòng)試題標(biāo)注工作對(duì)文本快速索引和檢索系統(tǒng)有著重要的意義［1］.

文本標(biāo)注問(wèn)題在近10年一直較為活躍，也產(chǎn)生了一些有效的方法.研究文本自動(dòng)分類(lèi)的核心問(wèn)題是如何構(gòu)造分類(lèi)函數(shù)(分類(lèi)器)，分類(lèi)函數(shù)需要通過(guò)某種算法進(jìn)行學(xué)習(xí)獲得．分類(lèi)是重要的數(shù)據(jù)挖掘方法，在眾多的文本分類(lèi)算法中，目前主要有改進(jìn)的 Rocchio 算法［2］、改進(jìn)的貝葉斯分類(lèi)算法［3］、K-近鄰算法［4］和支持向量機(jī)的知識(shí)組織算法［5］.近年來(lái)鄔開(kāi)俊等將遺傳算法和并行協(xié)同進(jìn)化算法結(jié)合起來(lái),在粗糙集的基礎(chǔ)上設(shè)計(jì)了一個(gè)并行協(xié)同進(jìn)化遺傳算法，并將該算法用于文本特征選擇.該方法采用遺傳算法搜索特征,利用并行協(xié)同進(jìn)化算法來(lái)提高時(shí)間效率,從而較快地獲得較具代表性的特征子集［6］.何躍等提出了一種改進(jìn)的以訪問(wèn)時(shí)間、點(diǎn)擊次數(shù)以及訪問(wèn)路徑共同刻畫(huà)用戶的訪問(wèn)興趣的Web日志挖掘算法.首先以Web日志為基礎(chǔ)構(gòu)建相關(guān)矩陣,使用平均訪問(wèn)時(shí)間相似度和訪問(wèn)路徑相似度共同度量用戶訪問(wèn)興趣的相似程度,最后采用直接聚類(lèi)去除相交項(xiàng)的聚類(lèi)算法將相似用戶和相關(guān)URL聚類(lèi)［7］.

在文本標(biāo)注存在的方法中，最簡(jiǎn)單的是將標(biāo)注問(wèn)題看做一種特征空間重建［8］.最常見(jiàn)的方法是使用K-近鄰方法及擴(kuò)展來(lái)分配關(guān)鍵字.如基于選擇相關(guān)距離，使用稀疏邏輯回歸的方法，如LASSO方法［9］.實(shí)踐效果上，平均距離方法比加噪LASSO方法在標(biāo)注精度上會(huì)更好.目前所提出的一些方法都較少對(duì)訓(xùn)練樣本文本的關(guān)鍵字和類(lèi)區(qū)域之間的相應(yīng)關(guān)系進(jìn)行深入研究.本文分析標(biāo)注數(shù)據(jù)的特點(diǎn)，構(gòu)建描述數(shù)據(jù)序列相似的對(duì)稱(chēng)權(quán)矩陣，結(jié)合基于圖的拉普拉斯算子方法，采用約束化Harmonic函數(shù)，進(jìn)行自動(dòng)試題標(biāo)注工作.

1 模型的提出與分析

1.1 自動(dòng)試題標(biāo)注工作框架

在自動(dòng)試題標(biāo)注工作中，假設(shè)標(biāo)注總試題樣本數(shù)目為n，其中l(wèi)個(gè)樣本是已標(biāo)注樣本，u個(gè)樣本為未標(biāo)注樣本.一般而言，在實(shí)際工作中，已標(biāo)注樣本個(gè)數(shù)應(yīng)遠(yuǎn)小于未標(biāo)注樣本的數(shù)目，即l

1.2 基于圖的拉普拉斯算子

在全部n個(gè)結(jié)點(diǎn)上定義n×n對(duì)稱(chēng)權(quán)矩陣W=［wij］：

其中xi∈Rp，p是單個(gè)樣本的維度.xi是原始數(shù)據(jù)X的第i個(gè)樣本.基于以上定義，W是一個(gè)具有非負(fù)元素的正定矩陣，存儲(chǔ)了n個(gè)數(shù)據(jù)序列的相似性信息，在歐式空間中相近的點(diǎn)在W矩陣中將會(huì)賦予較大的邊權(quán)［10-12］.

設(shè)定D為W的對(duì)角度矩陣，Dii=∑jWij.基于圖的組合拉普拉斯算子Δ定義為：

本文將W中的節(jié)點(diǎn)以(x1,…，xn)序列映射到1-D空間中.若i,j點(diǎn)是相似節(jié)點(diǎn)，即Wij較大時(shí)，i,j節(jié)點(diǎn)在映射空間中是連接的，則(xi-xj)2值較小，可得到目標(biāo)方程如下：

若向量x在其維度上沒(méi)有約束，則當(dāng)xi=0時(shí)將會(huì)得到最小值.但是這個(gè)結(jié)果顯然不符合要求，需要對(duì)xi進(jìn)行規(guī)則化約束為∑ixi2=1.若將xi替換為xi+a時(shí)，為了使得目標(biāo)方程值仍不發(fā)生改變，對(duì)xi再加上約束為∑xi=0，此時(shí)xi中必然含有混合元素.

基于以上兩種約束，映射問(wèn)題轉(zhuǎn)變?yōu)椋?/p>

映射問(wèn)題（3）的解較易求得，由于：

Δ算子如前定義，稱(chēng)為圖拉普拉斯，最小化映射目標(biāo)的映射解由下式的特征向量決定：

拉普拉斯映射廣泛使用于機(jī)器學(xué)習(xí)工作，作為保留局部拓?fù)浣Y(jié)構(gòu)而映射圖節(jié)點(diǎn)的正則化方法.

1.3 Harmonic函數(shù)的基本理論

本文將在連通圖G=(V,E)上計(jì)算實(shí)值函數(shù)f(i)=yi，i∈1,…，l.基于函數(shù)f對(duì)未分配類(lèi)標(biāo)試題集進(jìn)行自動(dòng)標(biāo)注工作.本文的目的是希望未加標(biāo)簽的數(shù)據(jù)點(diǎn)在同類(lèi)條件下應(yīng)該相似，可以基于式（3）定義代價(jià)函數(shù)：

研究發(fā)現(xiàn)，最小代價(jià)函數(shù)f=arg minf|L=ftE(f)是滿足Harmonic屬性的.

屬性1：在未標(biāo)簽數(shù)據(jù)點(diǎn)集UU上滿足Δf=0，在已標(biāo)簽數(shù)據(jù)集L上亦滿足此屬性.Δ=D-W為如前定義的組合拉普拉斯算子.D=diag(di)為對(duì)角矩陣，每一個(gè)元素di=∑jWij，而W=［Wij］為權(quán)矩陣.

屬性2：在每一個(gè)未加標(biāo)簽的數(shù)據(jù)點(diǎn)f的值是鄰近點(diǎn)的均值：

將 f的表達(dá)做一些修改：f=Pf，其中P=D-1W.基于Harmonic函數(shù)的最大原則［13］，f是唯一的并且滿足0＜f(j)＜0，其中 j∈U.

為了將Harmonic函數(shù)直接應(yīng)用于自動(dòng)試題標(biāo)注，采用矩陣算子，將權(quán)矩陣W分為4塊：

1.4 類(lèi)群正則化

基于Harmonic函數(shù)f來(lái)求解未標(biāo)簽數(shù)據(jù)的標(biāo)簽值，最簡(jiǎn)單直接的閾值判別準(zhǔn)則是：

本文將基于Harmonic函數(shù)（10）及閾值判別原則（12）對(duì)圖像數(shù)據(jù)進(jìn)行自動(dòng)標(biāo)注工作.

1.5 算法流程

第一步：讀入數(shù)據(jù)集數(shù)據(jù)得到統(tǒng)計(jì)數(shù)據(jù)集X∈Rp*n，讀入類(lèi)別數(shù)K，讀入每類(lèi)樣本數(shù)m，設(shè)定訓(xùn)練樣本比率，每類(lèi)中學(xué)習(xí)樣本為ln，標(biāo)準(zhǔn)樣本為un.

第二步：獲得學(xué)習(xí)樣本矩陣dataMatrix∈Rp*n，獲得標(biāo)注樣本矩陣queryMatrix∈Rp*un，重新建構(gòu)數(shù)據(jù)矩陣X，使得X的前l(fā)n×K個(gè)列向量為未標(biāo)注樣本，其余為學(xué)習(xí)樣本.

第三步：依據(jù)式（1）計(jì)算相似度矩陣W；計(jì)算圖拉普拉斯算子Δ=D-W，D=diag(di)依據(jù)（10）計(jì)算Harmonic函數(shù)fu.

第四步：利用閾值原則（12）計(jì)算自動(dòng)標(biāo)注精度.

準(zhǔn)則（11）在類(lèi)與類(lèi)之間分隔較好的情況下，效果會(huì)比較好.而在實(shí)際數(shù)據(jù)應(yīng)用中，類(lèi)與類(lèi)之間經(jīng)常并不是理想分隔，這時(shí)再應(yīng)用準(zhǔn)則(11)易產(chǎn)生較為嚴(yán)重的錯(cuò)誤標(biāo)注結(jié)果.

對(duì)矩陣W進(jìn)行研究發(fā)現(xiàn)，由于W是數(shù)據(jù)流形結(jié)構(gòu)的存儲(chǔ)矩陣，在實(shí)際應(yīng)用中往往比較難計(jì)算，并且不能反映標(biāo)注工作.將考慮類(lèi)標(biāo)優(yōu)先準(zhǔn)則，假設(shè)類(lèi)1所占比例為q，類(lèi)0所占比例為1-q，利用類(lèi)群正則化來(lái)調(diào)整類(lèi)分布，以此更好的取得精確的標(biāo)注結(jié)果.

定義類(lèi)1群為∑ifu(i)，類(lèi)0群為∑i(1-fu(i)).類(lèi)群正則化度量了類(lèi)群，若未標(biāo)簽數(shù)據(jù)點(diǎn)i滿足條件（12），模型（10）將會(huì)把數(shù)據(jù)點(diǎn)i分配給類(lèi)1，否則將數(shù)據(jù)點(diǎn)i分配給類(lèi)0.

2 自動(dòng)試題標(biāo)注實(shí)驗(yàn)分析

2.1 實(shí)驗(yàn)數(shù)據(jù)集描述

本文采用程序設(shè)計(jì)試題數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)工作.將計(jì)算機(jī)程序設(shè)計(jì)基礎(chǔ)課程的數(shù)據(jù)集以知識(shí)點(diǎn)的形式建立.在正式組卷時(shí)可以設(shè)定為選擇題、填空題、簡(jiǎn)答題及程序編程題.試題數(shù)據(jù)集S中每條記錄具有一個(gè)標(biāo)簽，共20個(gè)標(biāo)簽，標(biāo)簽集合為：程序設(shè)計(jì)基本概念、對(duì)象的概念、數(shù)據(jù)類(lèi)型、變量與常量、運(yùn)算符和表達(dá)式、常用內(nèi)部函數(shù)、順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)、程序調(diào)試、數(shù)組的概念、靜態(tài)數(shù)組及聲明、數(shù)組的基本操作、常用算法、函數(shù)過(guò)程的定義和調(diào)用、子過(guò)程的定義與調(diào)用、參數(shù)傳遞、過(guò)程和變量的作用域、控件設(shè)計(jì)、常用的文件操作語(yǔ)句和函數(shù).數(shù)據(jù)集共有1 000個(gè)試題條目，每一個(gè)條目具備若干個(gè)關(guān)鍵字并歸屬于某一標(biāo)簽類(lèi)別.數(shù)據(jù)集特征空間如圖1所示，左圖展示了第一類(lèi)的數(shù)據(jù)集特征空間，右圖展示了第二類(lèi)的數(shù)據(jù)集特征空間.從兩圖對(duì)比可以看出，各類(lèi)內(nèi)的數(shù)據(jù)特征較為統(tǒng)一，類(lèi)內(nèi)相似度較高.

圖1 試題數(shù)據(jù)集特征空間

2.2 TF-IDF方法

本文采用 Term frequency-inverse document frequency（TF-IDF）方法［2］對(duì)試題庫(kù)進(jìn)行統(tǒng)計(jì)工作.TFIDF是一種用于資訊檢索與資訊探勘的常用加權(quán)統(tǒng)計(jì)方法，用以評(píng)估一個(gè)字詞對(duì)于一個(gè)文件集或一個(gè)語(yǔ)料庫(kù)中的其中一份文件的重要程度.字詞的重要性隨著它在文件中出現(xiàn)的次數(shù)成正比增加，但同時(shí)會(huì)隨著它在語(yǔ)料庫(kù)中出現(xiàn)的頻率成反比下降.TF-IDF加權(quán)的各種形式常被搜尋引擎應(yīng)用，作為文件與用戶查詢之間相關(guān)程度的度量或評(píng)級(jí).

在本文給定的試題文件里，由于詞頻 (TF)是某一個(gè)給定的詞語(yǔ)在該文件中出現(xiàn)的次數(shù)，這個(gè)參數(shù)將會(huì)進(jìn)行歸一化工作，以防止它偏向長(zhǎng)的文件（同一個(gè)關(guān)鍵詞在長(zhǎng)試題里可能會(huì)比短試題有更高的詞頻，而不管該關(guān)鍵詞重要與否）.而逆向文件頻率 (IDF)將測(cè)試關(guān)鍵詞普遍重要性.試題集內(nèi)的高詞語(yǔ)頻率，以及該詞語(yǔ)在整個(gè)試題集合中的低文件頻率，可以產(chǎn)生出高權(quán)重的TF-IDF.因此，TF-IDF將在試題庫(kù)中過(guò)濾掉常見(jiàn)的關(guān)鍵詞，保留重要的關(guān)鍵詞.

2.3 相關(guān)方法的自動(dòng)試題標(biāo)注效果的比較與分析

本文采用1-NN方法和thresh方法作為比較方法，對(duì)Harmonic方法的自動(dòng)試題標(biāo)注精度進(jìn)行比較分析.1-NN方法即在半監(jiān)督分類(lèi)時(shí)采用數(shù)據(jù)點(diǎn)1近鄰來(lái)進(jìn)行分類(lèi)工作，而thresh方法即采用公式（11）進(jìn)行閾值選擇來(lái)分類(lèi).

采用k次交叉驗(yàn)證方法對(duì)實(shí)驗(yàn)精度進(jìn)行測(cè)量，初始采樣分割成k個(gè)子樣本，一個(gè)單獨(dú)的子樣本被保留作為驗(yàn)證模型的數(shù)據(jù)，其他k-1個(gè)樣本用來(lái)訓(xùn)練.交叉驗(yàn)證重復(fù)k次，每個(gè)子樣本驗(yàn)證一次，平均k次的結(jié)果，最終得到一個(gè)單一估測(cè).這個(gè)方法的優(yōu)勢(shì)在于，同時(shí)重復(fù)運(yùn)用隨機(jī)產(chǎn)生的子樣本進(jìn)行訓(xùn)練和驗(yàn)證，每次的結(jié)果驗(yàn)證一次.當(dāng)已加標(biāo)簽數(shù)據(jù)量增加，即參與學(xué)習(xí)的數(shù)據(jù)量增加時(shí)，標(biāo)注精度也總體隨之增加.如圖2所示.在較常使用的10-交叉驗(yàn)證法中，數(shù)據(jù)集在Harmonic方法下標(biāo)注精度達(dá)到42.3%，1-NN方法達(dá)到33.2%，而thresh方法達(dá)到23.1%；當(dāng)訓(xùn)練樣本百分比達(dá)到20%時(shí)，即在5-交叉驗(yàn)證法測(cè)量下，數(shù)據(jù)集在Harmonic方法下標(biāo)注精度達(dá)到63.3%，1-NN方法達(dá)到53.2%，而thresh方法達(dá)到37.1%.

圖2 試題數(shù)據(jù)集在不同已加標(biāo)簽數(shù)據(jù)量下的標(biāo)注精度圖

在已加標(biāo)簽數(shù)據(jù)量達(dá)到總數(shù)據(jù)量的50%和80%時(shí)，1-NN方法和thresh方法的標(biāo)注精度均有不同程度的下降，出現(xiàn)“粘滯”現(xiàn)象.而Harmonic方法則較為平穩(wěn)上升.分析發(fā)現(xiàn)，在學(xué)習(xí)樣本所占比例較大的情況下，拉普拉斯映射的學(xué)習(xí)能力較為穩(wěn)定.

2.4 類(lèi)塊特性

由于原始數(shù)據(jù)是經(jīng)過(guò)TF-IDF方法得到的統(tǒng)計(jì)數(shù)據(jù)矩陣較為稀疏，不能采用傳統(tǒng)的RBF相似度度量方法，即在全部n個(gè)結(jié)點(diǎn)上定義n×n對(duì)稱(chēng)權(quán)矩陣W=［wij］：

其中xi∈Rp，p是單個(gè)樣本的維度.xid是xi的第d個(gè)成分.

若采用RBF相似度度量法，得到的相似度矩陣無(wú)明顯類(lèi)塊特性.考慮到以上情況，本文采用Cosine相似度度量，即：

得到的相似度矩陣如圖3所示.

從圖3中可以明顯看出，由于本數(shù)據(jù)集是每類(lèi)50條試題，從而相似度矩陣中具備K個(gè)50*50的類(lèi)塊結(jié)構(gòu)，K為類(lèi)別總數(shù).表明相似類(lèi)特征較為集中，這樣的相似度矩陣有利于分類(lèi)工作的展開(kāi).

研究發(fā)現(xiàn)，從Harmonic方法得到的未標(biāo)簽數(shù)據(jù)集應(yīng)同樣具備類(lèi)塊特性.在5-交叉驗(yàn)證下解得的數(shù)據(jù)圖如圖4所示.從圖4中可以看出，求出的未標(biāo)簽數(shù)據(jù)集相似類(lèi)特征亦較為集中，聚類(lèi)效果良好.

圖3 數(shù)據(jù)集相似度矩陣部分示意圖

圖4 數(shù)據(jù)點(diǎn)矩陣部分示意圖

3 結(jié)論

高等院校教學(xué)工作中，組卷試題庫(kù)中試題量巨大，科目繁多.為加速自動(dòng)組卷工作，減輕人力標(biāo)注成本，本文結(jié)合拉普拉斯映射和Harmonic方法，將其應(yīng)用于半監(jiān)督試題自動(dòng)標(biāo)注，這項(xiàng)工作采用拉普拉斯算子將原數(shù)據(jù)映射到低維空間中，采用Harmonic函數(shù)作為自動(dòng)圖像標(biāo)注模型，新方法具備Harmonic屬性，利用數(shù)據(jù)相似度矩陣和基于圖的拉普拉斯算子分析數(shù)據(jù)結(jié)構(gòu)，強(qiáng)化數(shù)據(jù)類(lèi)塊特性.

實(shí)驗(yàn)證明此方法確實(shí)在自動(dòng)試題標(biāo)注精度上有很好的效果，標(biāo)注精確度均高于1-NN方法和閾值選擇方法，具備有效性.但在實(shí)驗(yàn)中發(fā)現(xiàn)，降維的維度控制對(duì)標(biāo)注的準(zhǔn)確性存在很大的影響.下一步，可以研究如何控制降維維度與標(biāo)注準(zhǔn)確性，使得兩個(gè)指標(biāo)之間取得較好的平衡；并研究如何在試題集中訓(xùn)練得分預(yù)測(cè)模型，用于預(yù)測(cè)與控制組卷后試卷的難易程度.這項(xiàng)工作的開(kāi)展，有利于教師將檢測(cè)評(píng)價(jià)的工作再反到教學(xué)工作中去，對(duì)課程教學(xué)亦具有很好的實(shí)際意義.