謝 瑩，許榮斌

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

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

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

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

1 模型的提出與分析

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

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

1.2 基于圖的拉普拉斯算子

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

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

設(shè)定D為W的對角度矩陣，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在其維度上沒有約束，則當(dāng)xi=0時(shí)將會得到最小值.但是這個結(jié)果顯然不符合要求，需要對xi進(jìn)行規(guī)則化約束為∑ixi2=1.若將xi替換為xi+a時(shí)，為了使得目標(biāo)方程值仍不發(fā)生改變，對xi再加上約束為∑xi=0，此時(shí)xi中必然含有混合元素.

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

映射問題（3）的解較易求得，由于：

Δ算子如前定義，稱為圖拉普拉斯，最小化映射目標(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對未分配類標(biāo)試題集進(jìn)行自動標(biāo)注工作.本文的目的是希望未加標(biāo)簽的數(shù)據(jù)點(diǎn)在同類條件下應(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)為對角矩陣，每一個元素di=∑jWij，而W=［Wij］為權(quán)矩陣.

屬性2：在每一個未加標(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)用于自動試題標(biāo)注，采用矩陣算子，將權(quán)矩陣W分為4塊：

1.4 類群正則化

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

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

1.5 算法流程

第一步：讀入數(shù)據(jù)集數(shù)據(jù)得到統(tǒng)計(jì)數(shù)據(jù)集X∈Rp*n，讀入類別數(shù)K，讀入每類樣本數(shù)m，設(shè)定訓(xùn)練樣本比率，每類中學(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個列向量為未標(biāo)注樣本，其余為學(xué)習(xí)樣本.

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

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

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

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

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

2 自動試題標(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ù)集以知識點(diǎn)的形式建立.在正式組卷時(shí)可以設(shè)定為選擇題、填空題、簡答題及程序編程題.試題數(shù)據(jù)集S中每條記錄具有一個標(biāo)簽，共20個標(biāo)簽，標(biāo)簽集合為：程序設(shè)計(jì)基本概念、對象的概念、數(shù)據(jù)類型、變量與常量、運(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ù)過程的定義和調(diào)用、子過程的定義與調(diào)用、參數(shù)傳遞、過程和變量的作用域、控件設(shè)計(jì)、常用的文件操作語句和函數(shù).數(shù)據(jù)集共有1 000個試題條目，每一個條目具備若干個關(guān)鍵字并歸屬于某一標(biāo)簽類別.數(shù)據(jù)集特征空間如圖1所示，左圖展示了第一類的數(shù)據(jù)集特征空間，右圖展示了第二類的數(shù)據(jù)集特征空間.從兩圖對比可以看出，各類內(nèi)的數(shù)據(jù)特征較為統(tǒng)一，類內(nèi)相似度較高.

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

2.2 TF-IDF方法

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

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

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

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

采用k次交叉驗(yàn)證方法對實(shí)驗(yàn)精度進(jìn)行測量，初始采樣分割成k個子樣本，一個單獨(dú)的子樣本被保留作為驗(yàn)證模型的數(shù)據(jù)，其他k-1個樣本用來訓(xùn)練.交叉驗(yàn)證重復(fù)k次，每個子樣本驗(yàn)證一次，平均k次的結(jié)果，最終得到一個單一估測.這個方法的優(yōu)勢在于，同時(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)證法測量下，數(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 類塊特性

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

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

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

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

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

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

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

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

3 結(jié)論

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

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