基于SVM的論文元數(shù)據(jù)抽取方法研究

歐陽輝，祿樂濱

（空軍工程大學 電訊工程學院，陜西 西安 710077）

隨著DOI的應(yīng)用與發(fā)展，信息的自動抽取研究得到了廣泛關(guān)注，但自動抽取器對電子文檔進行元數(shù)據(jù)自動抽取基本上都是從電子文檔的頭文件中進行抽取，抽取的字段以文檔的形式特征（類型、生成時間、軟件相關(guān)信息等）為主，而關(guān)鍵內(nèi)容的相關(guān)元數(shù)據(jù)則難以獲得[1]。

數(shù)據(jù)庫中的科技論文文獻有近90%是PDF格式的文檔，目前對PDF格式文檔進行元數(shù)據(jù)抽取主要采用間接抽取法，即先把PDF格式的文檔轉(zhuǎn)換為其他格式文檔后再進行元數(shù)據(jù)抽取。在文獻[2]中李朝光等人進行了從TXT文檔中基于正則表達式來提取論文元數(shù)據(jù)的研究，成功率達到74.3%。在文獻[3]中，通過把PDF文件用工具PDF2HTML工具轉(zhuǎn)換成中間文檔，再總結(jié)出標題、作者名、作者地址、E-mail共4類論文元數(shù)據(jù)特征，最后利用XSLT作為抽取規(guī)則制定語言進行抽取，但是元數(shù)據(jù)類型不夠豐富，特征總結(jié)不夠全面，還有待于進一步研究。

一個PDF文檔由文件頭、文件體、交叉引用表、文件尾4部分組成，是8位二進制字節(jié)序列，也可以用7位ASCII來描述。它是以二進制傳輸和存儲的，可由簡單文本組成，也可能是由文本和各種類型的圖像（彩色圖像、灰度圖像和二值圖像）混合組成[4]。

對于論文元數(shù)據(jù)抽取來說，PDF文檔的文件頭、交叉引用表、文件尾等額外文檔描述信息對基于統(tǒng)計的模型甚至是一種干擾。研究發(fā)現(xiàn)，pdfbox開源庫對PDF文檔進行過濾處理后可以得到自由文本格式論文，這樣就可以通過libsvm開源庫建立支持向量機仿真模型對轉(zhuǎn)換后的文檔進行元數(shù)據(jù)抽取。

1 支持向量機（SVM）

支持向量機（Support Vector Machine，SVM）是由統(tǒng)計學習理論發(fā)展而來的一種機器學習方法，它以最大化分類間隔構(gòu)造最優(yōu)分類超平面來提高支持向量機的泛化能力，具有訓練樣本小、學習速度快、易于擴展等特點[5]，已經(jīng)成為目前的研究熱點，在模式識別，包括手寫字符識別、網(wǎng)頁或文本自動分類、說話人識別、人臉識別、遙感圖像分析等方面都有非常出色的表現(xiàn)[6]。

1.1 支持向量機的原理

支持向量機建模的過程就是解決最優(yōu)分類超平面的參數(shù)確定問題，確定各個參數(shù)實質(zhì)是一個二次優(yōu)化問題，其幾何意義是求在約束條件下分類間隔的最大值，對于輸入空間中的非線性問題，可以通過核函數(shù)計算特征空間中向量與支持向量之間的內(nèi)積使其轉(zhuǎn)化為特征空間的線性分類問題，判別函數(shù)如下：

對于非線性問題，僅僅依靠核函數(shù)會導(dǎo)致目標空間維數(shù)過高，為此這里引入松弛變量和懲罰因子來解決該問題，這樣就把一個復(fù)雜的最優(yōu)化問題簡化為對原有樣本數(shù)據(jù)的內(nèi)積運算和選擇適當?shù)暮撕瘮?shù)及其參數(shù)的問題，這樣構(gòu)造出的支持向量機也稱為軟間隔支持向量機。最常用的軟間隔支持向量機是C-SVM，參數(shù)C為懲罰因子。

1.2 多分類支持向量機模型

多分類支持向量機是專門解決有多個類別的分類算法。支持向量機最初是為兩類分類問題而設(shè)計的，但在實際應(yīng)用中更多的是需要從多個類中提取出所需要的數(shù)據(jù)和信息，這使得多類分類問題的應(yīng)用更普遍。對于多分類問題，最常用的方法是將多分類問題轉(zhuǎn)化成兩類分類問題來求解，選定其中的一個類或多個類作為正類，將其余的類作為負類，建立兩分類的支持向量機，再對余下的類多次運用兩分類的支持向量機將其一一分開，該類主要的方法有one-against-one、one-against-all、DDAGSVM及樹型支持向量機等方法。

比較以上4種方法，“one-against-all”方法對K類問題只要建立K個支持向量機，訓練過程很快，但在預(yù)測過程中存在無解的危險，當K個支持向量機對該樣本都輸出為否時，該樣本就找不到屬于它的類，出現(xiàn)無解的情況。“one-againstone”方法和DDAGSVM方法對K類問題都要建立K（K－1）/2個支持向量機，建立支持向量機的速度相對較慢，而且“oneagainst-one”方法在測試過程中每一個樣本都需要經(jīng)過這K（K－1）/2個支持向量機的分類，因此其訓練速度和分類速度都較慢。DDAGSVM方法每個測試樣本也需要從根節(jié)點走完一條到葉子節(jié)點的路徑才能判別出目標所屬的類別，經(jīng)過的支持向量機的分類次數(shù)為K次，其分類速度較快，而且每條路徑都以葉子節(jié)點結(jié)束，所以不會出現(xiàn)無解的情況。但該方法存在差錯積累，一旦在根節(jié)點分類錯誤，則在后續(xù)節(jié)點就不能找到正確分類，只能一錯再錯，最后得到錯誤分類。

樹型支持向量機多類分類方法實質(zhì)上是一種決策二叉樹的方法?；诙鏄涞亩囝怱VM首先將所有類別分成2個子類，再將子類進一步劃分成2個次級子類，如此循環(huán)，直到所有節(jié)點都只包含一個單獨的類別（即葉子節(jié)點）為止。該方法分類準確率高，分類速度快，但難點是樹型結(jié)構(gòu)的設(shè)計和差錯積累問題。

從分類準確率角度分析，在樹形結(jié)構(gòu)中，越上層的節(jié)點（即越早分離出來的類）的分類性能對整個分類模型的推廣性影響越大。在文獻[7]中，通過例證得出越易分辨的類放到上層，最終的總分類誤差數(shù)越小。因此，應(yīng)該讓最易分割的類最早分割出來，即在二叉樹的上層節(jié)點處分割，這樣才能使得上層的SVM子分類器具有更高的推廣性能，減少差錯積累，提高分類準確率。找出最易分割的類別的基本思想是，讓與其他類相隔最遠的類最先分割出來，此時構(gòu)造的最優(yōu)超平面也應(yīng)具有較好的推廣性。

而判斷一個算法好壞除了要判斷其錯分率，空間復(fù)雜度等指標外，還要判斷其運行時間，這里的時間是指訓練時間（建立所有支持向量機的時間）和分類時間（判斷一個新的未知的樣本點屬于哪個類）。

訓練時間主要在于求解單個支持向量機的時間和建立支持向量機的個數(shù)，文獻[7]從理論上分析了“正態(tài)樹”和“偏態(tài)樹”的訓練總時間，得出相同樣本數(shù)量的情況下，“正態(tài)樹”的訓練總時間最短。

分類時間主要在于求出未知樣本點所在的類需要經(jīng)過的支持向量機運算的個數(shù)。在樹形結(jié)構(gòu)中，分類時間主要取決于二叉樹的層數(shù)，即所建立的二叉樹的深度越大，其分類時間越長，反之越短。因此，二叉樹的深度越小越好。

1.3 基于平衡二叉樹的多類分類支持向量機

為了優(yōu)化仿真模型，這里提出基于平衡二叉樹的支持向量機多類分類方法（BBT-SVM），算法步驟如下：

1）定義類與類之間的距離 dij（i，j=1，2，3，…，k；i=j）。 在線性情況下，2樣本x1，x2間距定義取2個樣本的歐氏距離

在非線性情況下，2樣本x1，x2間距定義為

式中，?（x）為向量x經(jīng)過核函數(shù)映射到高維向量空間后所對應(yīng)的向量。 k（x1，x1）=?（x1）g?（x2）為核函數(shù)。

2）分別對各個類別與其他類別距離值按由大到小的順序排列，并重新編號。例如，第i類與其他類距離值為dij（i，j=1，2，3，…，k；i=j），按由大到小排序為

3）比較各類的D1，選出具有最大D1的2個類。 若Ci的大于Cj的即則Ci排在Cj之前。 若Ci的與Cj的相等，即，則再比較Ci的與Cj的，若Ci的大于Cj的，即，則Ci排在Cj之前。 若Ci的與Cj的相等，即，則再比較Ci的與Cj的依此類推，則得到具有最大距離的2個類A和B，用表示。從類集合中去掉類A和類B，重新比較各類的D1，挑出各類中具有最大D1的個類C和D，用表示。最后得到序列：若類別總數(shù)為奇數(shù)，則會留下最后剩下的類別，記為Z）。

5）分別以左右子樹包含的類為集合，重復(fù)步驟2）～步驟4），建立左右子樹。

6）重復(fù)步驟5），直至得到所有葉子節(jié)點，算法結(jié)束。

該改進算法融合了最大類間距離和平衡樹的思想，從理論上分析，最大類間距離保證較高的分類準確率；運用平衡樹的思想，使分類樹的深度最小，而且使正例和反例的樣本數(shù)目近似相等，分類錯誤率較低。

對于K類問題，比較各方法的性能，如表1所示。

表1 多類分類支持向量機的比較

2 建立SVM的仿真模型

2.1 SVM模型的確定

針對論文元數(shù)據(jù)的特點，選取6類典型元數(shù)據(jù)作為測試對象，樹中度為2的節(jié)點則為支持向量機，則支持向量機的個數(shù)為5個，每個支持向量機都選擇C-SVM模型且C值的限定范圍為 （10-5，105）。本模型中采用的核函數(shù)是徑向基函數(shù)： K（x，y）=exp［（x-y）2/δ2］，δ 為模型要確定的參數(shù)，在本模型中限定范圍為（10-5，105）。

本文用于訓練的數(shù)據(jù)集為隨機選取的2萬篇論文，用于實驗的論文元數(shù)據(jù)類別初步定為出版社信息、標題、作者、摘要、關(guān)鍵詞，參考文獻等6類。首先將樣本去噪，對數(shù)據(jù)進行規(guī)范化，處理奇異樣本點，最后樣本用特征向量表示。根據(jù)式（2）和式（3）并按照平衡二叉樹支持向量機的建立步驟進行計算，建立的BBT-SVM模型如圖1所示。

圖1 基于BBT-SVM的論文元數(shù)據(jù)抽取模型

2.2 SVM模型的優(yōu)化仿真

這里用MyEclipse 6.0結(jié)合MATLAB 7.1并選用libsvm開源庫編程建立仿真模型，用交叉驗證法尋找最佳參數(shù)，用k-fold法計算交互檢驗準確度和均方根誤差，實驗中k取10，采用徑向基核函數(shù)，運用交叉驗證法使核參數(shù)σ和懲罰因子C在區(qū)間（10-5，105）進行搜索，如圖2所示，由交叉驗證法搜索出的各支持向量機模型的參數(shù)如表2所示，從而得到最優(yōu)SVM仿真模型。

圖2 網(wǎng)格搜索法得到SVM-1的最佳參數(shù)

表2 BBT-SVM模型中各SVM的參數(shù)

3 結(jié)果分析

為了檢驗支持向量機的性能，隨機選取3萬篇論文文獻進行論文元數(shù)據(jù)抽取，實驗結(jié)果如表3所示。

表3 論文元數(shù)據(jù)的抽取結(jié)果

在實驗結(jié)果中，F(xiàn)度量值F=（B2+1）PR/B2P+R，調(diào)節(jié)B的值可以讓用戶在查全率和查準率上求得平衡，在文獻[8]中，取B=0.5，代表P的重要程度是R的2倍，這是基于元數(shù)據(jù)提取的查準率比查全率重要的考慮，而在論文文獻元數(shù)據(jù)中初步選取的元數(shù)據(jù)是基本元數(shù)據(jù)，都是必須的，所以數(shù)據(jù)的完備性同準確性一樣重要，因此取B=1。

4 結(jié) 論

本文針對PDF文件的特點，選用pdfbox開源庫對PDF文件進行解析得到，通過分析多類分類支持向量機的特點和性能提出了BBT-SVM模型。運用網(wǎng)格搜索法得到最佳參數(shù)得到BBT-SVM最優(yōu)模型，最后對隨機選取的3萬篇論文文獻進行元數(shù)據(jù)抽取。經(jīng)過試驗，各類元數(shù)據(jù)的查全率都提高了86%以上，查準率都在92%以上，F(xiàn)度量值都在89%以上，與基于正則表達式的方法相比提高了20%。由試驗數(shù)據(jù)結(jié)果可知，查全率比較低，這是因為文獻中的部分論文是加密的PDF文檔，pdfbox無法對其進行解析。針對加密的PDF論文文獻的元數(shù)據(jù)抽取是下一步研究的重點。

[1]曾蘇，馬建霞，張秀秀.元數(shù)據(jù)自動抽取研究新進展[J].現(xiàn)代圖書情報技術(shù)，2008，163（4）：7－11.

[2]李朝光，張銘，鄧志鴻，等.論文元數(shù)據(jù)信息的自動抽取[J].計算機工程與應(yīng)用，2002，21（5）：189-235.

[3]陳俊林，張文德.基于XSLT的PDF論文元數(shù)據(jù)的優(yōu)化抽取[J].現(xiàn)代圖書情報技術(shù)，2007，147（2）：18-23.

[4]陳云榕，劉立柱，丁志鴻.PDF文件中關(guān)鍵信息的提取與組織方法研究[J].計算機工程與應(yīng)用，2007，27（4）：39-45.

[5]范婕婷，賴惠成.一種基于SVM算法的垃圾郵件過濾方法[J].計算機工程與應(yīng)用，2008，44（28）：95-98.

[6]Keerthi S，Chih-Jen Lin.Asymptotic behavior of support vector machines with Gaussian kernel[J].Nerual Computation，2003（15）：1667-1689.

[7]劉志剛，李德仁，秦前清，等.支持向量機在多類分類問題中的推廣[J].計算機工程與應(yīng)用，2004，12（7）：10-13.

[8]楊宇，張銘，周寶曜.基于多種規(guī)則的課程元數(shù)據(jù)自動抽取[J].計算機科學，2008，35（3）：94-96.