基于Harmonic函數的自動試題標注模型

謝 瑩，許榮斌

（安徽大學 計算機科學與技術學院，合肥 安徽230601）

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

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

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

1 模型的提出與分析

1.1 自動試題標注工作框架

在自動試題標注工作中，假設標注總試題樣本數目為n，其中l個樣本是已標注樣本，u個樣本為未標注樣本.一般而言，在實際工作中，已標注樣本個數應遠小于未標注樣本的數目，即l

1.2 基于圖的拉普拉斯算子

在全部n個結點上定義n×n對稱權矩陣W=［wij］：

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

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

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

若向量x在其維度上沒有約束，則當xi=0時將會得到最小值.但是這個結果顯然不符合要求，需要對xi進行規則化約束為∑ixi2=1.若將xi替換為xi+a時，為了使得目標方程值仍不發生改變，對xi再加上約束為∑xi=0，此時xi中必然含有混合元素.

基于以上兩種約束，映射問題轉變為：

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

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

拉普拉斯映射廣泛使用于機器學習工作，作為保留局部拓撲結構而映射圖節點的正則化方法.

1.3 Harmonic函數的基本理論

本文將在連通圖G=(V,E)上計算實值函數f(i)=yi，i∈1,…，l.基于函數f對未分配類標試題集進行自動標注工作.本文的目的是希望未加標簽的數據點在同類條件下應該相似，可以基于式（3）定義代價函數：

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

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

屬性2：在每一個未加標簽的數據點f的值是鄰近點的均值：

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

為了將Harmonic函數直接應用于自動試題標注，采用矩陣算子，將權矩陣W分為4塊：

1.4 類群正則化

基于Harmonic函數f來求解未標簽數據的標簽值，最簡單直接的閾值判別準則是：

本文將基于Harmonic函數（10）及閾值判別原則（12）對圖像數據進行自動標注工作.

1.5 算法流程

第一步：讀入數據集數據得到統計數據集X∈Rp*n，讀入類別數K，讀入每類樣本數m，設定訓練樣本比率，每類中學習樣本為ln，標準樣本為un.

第二步：獲得學習樣本矩陣dataMatrix∈Rp*n，獲得標注樣本矩陣queryMatrix∈Rp*un，重新建構數據矩陣X，使得X的前ln×K個列向量為未標注樣本，其余為學習樣本.

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

第四步：利用閾值原則（12）計算自動標注精度.

準則（11）在類與類之間分隔較好的情況下，效果會比較好.而在實際數據應用中，類與類之間經常并不是理想分隔，這時再應用準則(11)易產生較為嚴重的錯誤標注結果.

對矩陣W進行研究發現，由于W是數據流形結構的存儲矩陣，在實際應用中往往比較難計算，并且不能反映標注工作.將考慮類標優先準則，假設類1所占比例為q，類0所占比例為1-q，利用類群正則化來調整類分布，以此更好的取得精確的標注結果.

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

2 自動試題標注實驗分析

2.1 實驗數據集描述

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

圖1 試題數據集特征空間

2.2 TF-IDF方法

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

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

2.3 相關方法的自動試題標注效果的比較與分析

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

采用k次交叉驗證方法對實驗精度進行測量，初始采樣分割成k個子樣本，一個單獨的子樣本被保留作為驗證模型的數據，其他k-1個樣本用來訓練.交叉驗證重復k次，每個子樣本驗證一次，平均k次的結果，最終得到一個單一估測.這個方法的優勢在于，同時重復運用隨機產生的子樣本進行訓練和驗證，每次的結果驗證一次.當已加標簽數據量增加，即參與學習的數據量增加時，標注精度也總體隨之增加.如圖2所示.在較常使用的10-交叉驗證法中，數據集在Harmonic方法下標注精度達到42.3%，1-NN方法達到33.2%，而thresh方法達到23.1%；當訓練樣本百分比達到20%時，即在5-交叉驗證法測量下，數據集在Harmonic方法下標注精度達到63.3%，1-NN方法達到53.2%，而thresh方法達到37.1%.

圖2 試題數據集在不同已加標簽數據量下的標注精度圖

在已加標簽數據量達到總數據量的50%和80%時，1-NN方法和thresh方法的標注精度均有不同程度的下降，出現“粘滯”現象.而Harmonic方法則較為平穩上升.分析發現，在學習樣本所占比例較大的情況下，拉普拉斯映射的學習能力較為穩定.

2.4 類塊特性

由于原始數據是經過TF-IDF方法得到的統計數據矩陣較為稀疏，不能采用傳統的RBF相似度度量方法，即在全部n個結點上定義n×n對稱權矩陣W=［wij］：

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

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

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

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

研究發現，從Harmonic方法得到的未標簽數據集應同樣具備類塊特性.在5-交叉驗證下解得的數據圖如圖4所示.從圖4中可以看出，求出的未標簽數據集相似類特征亦較為集中，聚類效果良好.

圖3 數據集相似度矩陣部分示意圖

圖4 數據點矩陣部分示意圖

3 結論

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

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