歐陽輝，祿樂濱

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

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

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

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

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

1 支持向量機(jī)（SVM）

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

1.1 支持向量機(jī)的原理

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

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

1.2 多分類支持向量機(jī)模型

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

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

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

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

而判斷一個(gè)算法好壞除了要判斷其錯(cuò)分率，空間復(fù)雜度等指標(biāo)外，還要判斷其運(yùn)行時(shí)間，這里的時(shí)間是指訓(xùn)練時(shí)間（建立所有支持向量機(jī)的時(shí)間）和分類時(shí)間（判斷一個(gè)新的未知的樣本點(diǎn)屬于哪個(gè)類）。

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

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

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

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

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

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

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

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

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

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

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

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

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

表1 多類分類支持向量機(jī)的比較

2 建立SVM的仿真模型

2.1 SVM模型的確定

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

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

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

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

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

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

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

3 結(jié)果分析

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

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

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

4 結(jié) 論

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

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

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

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

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

[5]范婕婷，賴惠成.一種基于SVM算法的垃圾郵件過濾方法[J].計(jì)算機(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ī)在多類分類問題中的推廣[J].計(jì)算機(jī)工程與應(yīng)用，2004，12（7）：10-13.

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