王麗鵬，張鵬云，和志強(qiáng)

(河北經(jīng)貿(mào)大學(xué) 信息技術(shù)學(xué)院，河北 石家莊 050061)

基于特征詞匹配的政策文本分類算法研究與實(shí)現(xiàn)

王麗鵬，張鵬云，和志強(qiáng)

(河北經(jīng)貿(mào)大學(xué) 信息技術(shù)學(xué)院，河北 石家莊 050061)

在基于特征詞遍歷匹配的文本分類算法中，字符串匹配算法的選取及相似度閾值控制對文本分類結(jié)果起著決定性的作用。針對三種常用的字符串匹配算法做了分析及對比實(shí)驗(yàn)，選取了最適合政策文本分類的一種字符串匹配算法。并通過研究政策文本具有的特征提出了一種基于特征詞加權(quán)的相似度閾值計(jì)算方法，經(jīng)實(shí)驗(yàn)證明相似度閾值符合分類要求。

字符串匹配算法；閾值計(jì)算；文本分類

0 引言

豐富的網(wǎng)絡(luò)信息資源為研究Web文本分類技術(shù)提供了有利條件。然而，不規(guī)則的Web頁面結(jié)構(gòu)，半結(jié)構(gòu)化的文本信息，繁多的信息種類對于Web文本分類提出了巨大挑戰(zhàn)[1]。Web文本數(shù)據(jù)挖掘主要是對Web文本中包含的關(guān)鍵詞匯進(jìn)行矢量化并對特征詞進(jìn)行總和、分類、聚類及相關(guān)性研究，同時(shí)可以對Web頁面內(nèi)容等數(shù)據(jù)進(jìn)行相關(guān)趨勢預(yù)測等[2]。文本分類與文本聚類是文本數(shù)據(jù)挖掘的核心技術(shù)。然而在眾多文本分類算法中，尚沒有一種適合于政策文本分類的算法。本文通過對比三種字符串匹配算法的分類效果及計(jì)算消耗時(shí)間選取了一種適合政策文本分類的字符串匹配算法，并通過分析政策文本具有的特征提出一種相似度閾值計(jì)算的方法。

1 網(wǎng)頁文本分類關(guān)鍵技術(shù)

1.1 網(wǎng)頁文本內(nèi)容提取技術(shù)

與普通純文字文檔相比，Web頁面文本的結(jié)構(gòu)具有多樣性，Web頁面是半結(jié)構(gòu)化數(shù)據(jù)。Web頁面的基本結(jié)構(gòu)是DOM(Document Object Model，文檔對象模型)結(jié)構(gòu)[3]。由于HTML語法靈活多變，大部分Web頁面的設(shè)計(jì)很可能不符合W3C規(guī)范，可能在進(jìn)行頁面解析時(shí)影響解析結(jié)果。要想研究Web頁面的主要內(nèi)容，就必須在解析HTML頁面的時(shí)候排除不相關(guān)信息的干擾。

本文使用一款完全開源的HTML頁面解析器J-soup框架來完成從HTML到文本轉(zhuǎn)化的過程。J-soup能夠準(zhǔn)確的解析Web頁面并將HTML轉(zhuǎn)換為Dom樹結(jié)構(gòu)。程序初始規(guī)定所有抓取的頁面符合Web瀏覽器創(chuàng)建文檔所使用的模型規(guī)則。開發(fā)者可以根據(jù)自己的需求來自定義匹配規(guī)則，避免浪費(fèi)資源提高程序效率。

1.2 特征詞提取技術(shù)及加權(quán)方法

Web頁面文本分類的前期處理工作即文本內(nèi)容抓取、干擾去除，之后關(guān)鍵的部分就是文本特征詞的提取。一個(gè)好的特征詞抽取算法可以有效的避免數(shù)據(jù)不平衡的現(xiàn)象，提高數(shù)據(jù)利用率和分類的準(zhǔn)確性[4]。

本文采用中科院研究的NLPIR漢語分詞系統(tǒng)中關(guān)鍵詞抽取功能進(jìn)行文本關(guān)鍵詞的抽取，該系統(tǒng)的關(guān)鍵詞提取技術(shù)得到了普遍認(rèn)可。加權(quán)算法采用文本分類中普遍采用的TF-IDF權(quán)重計(jì)算方法[5]。

1.3 字符串匹配算法的優(yōu)缺點(diǎn)

常用于文本分類的字符串匹配算法有編輯距離相似度算法、Jaro-Winkler Distance算法及余弦相似度算法。

(1)編輯距離相似度算法思想簡單易于實(shí)現(xiàn)，所以在文本分類中得到了普遍使用。但編輯距離相似度算法是根據(jù)兩個(gè)字符串之間相互轉(zhuǎn)換需要的步驟多少來確定相似度的，在計(jì)算相似度較高的字符串之間的相似度時(shí)，計(jì)算結(jié)果區(qū)分度不高。而且在涉及專業(yè)詞匯的相似度計(jì)算時(shí)其準(zhǔn)確率往往很低[6]。

(2)余弦相似度算法準(zhǔn)確率雖然較高，但是由于該算法計(jì)算中涉及較多分詞對比計(jì)算，所以會消耗大量時(shí)間[7]。在數(shù)據(jù)量較大時(shí)，使用余弦相似度計(jì)算字符串之間的相似度的時(shí)間將會量級增長，這遠(yuǎn)超于用戶接受范圍[8]。

(3)Jaro-Winkler Distance算法在編輯距離相似度算法的基礎(chǔ)上進(jìn)行了改進(jìn)，在計(jì)算相似度時(shí)，規(guī)定兩個(gè)分別來自字符串S1和字符串S2的字符之間的距離即Distance不能超過公式(1)計(jì)算結(jié)果，很大程度上提高了相似度計(jì)算的準(zhǔn)確率[9]。然而由于該算法是基于編輯距離相似度算法進(jìn)行改進(jìn)的，其計(jì)算結(jié)果區(qū)分度不高的局限性仍然存在[10]。

(1)

通過對比三種字符串匹配算法的準(zhǔn)確率及計(jì)算消耗時(shí)間本文選取Jaro-Winkler Distance算法作為政策文本分類中的字符串匹配算法。

2 基于特征詞加權(quán)的相似度閾值計(jì)算方法

基于特征詞匹配的文本分類算法的關(guān)鍵在于字符串匹配算法的選取，而字符串匹配算法的主要難題就是相似度閾值計(jì)算[8]。本文基于特征詞加權(quán)提出一種計(jì)算相似度閾值的方法：首先對訓(xùn)練集C1中抽取的特征詞進(jìn)行加權(quán)，權(quán)值計(jì)算方法為TF-IDF，并將所有特征詞入庫得到文本特征詞庫K1；為了體現(xiàn)特征詞的普遍性(聚合性)，對樣本集C2進(jìn)行聚類，將C2分為若干個(gè)樣本集C21，C22，C23…C2n(n為C2聚類后的子樣本集個(gè)數(shù))，對若干個(gè)樣本集中抽取的特征詞加權(quán)并入庫得到樣本詞庫K21，K22，K23…K2n。

(2)

本文規(guī)定在計(jì)算相似度之合S1，S2，S3…Sn時(shí)，結(jié)合特征詞的權(quán)值不同給每個(gè)特征詞的相似度乘上不同的系數(shù)。圖1為特征詞的權(quán)值分布圖：

圖1 特征詞的權(quán)值分布圖

根據(jù)權(quán)值分布，分別給權(quán)值在0-5和13以上的特征詞的相似度賦予系數(shù)(1+ρ)(0<ρ<1)，權(quán)值在6-12之間的特征詞的相似度賦予系數(shù)(1-ρ)。則公式(2)可變?yōu)椋?/p>

(3)

考慮到特征詞權(quán)值越大越具有代表性，ρ越大權(quán)值大的特征詞在閾值計(jì)算中所占比重越大，所以ρ取允許范圍內(nèi)的最大值0.9，根據(jù)公式(3)計(jì)算得出W為0.8(計(jì)算精確到0.1)。

從樣本集抽取200條政策與訓(xùn)練集進(jìn)行匹配。當(dāng)特征詞的相似度發(fā)生變化時(shí)，匹配數(shù)量與相似度關(guān)系如圖3所示。

圖2 系數(shù)ρ與閾值W關(guān)系圖

圖3 匹配數(shù)量圖

通過觀察實(shí)驗(yàn)數(shù)據(jù)發(fā)現(xiàn)，當(dāng)W取0.8時(shí)，能夠?qū)y試集文本分類且大部分文本被認(rèn)為相似，符合一般規(guī)律，滿足分類要求。

3 文本分類算法研究與實(shí)現(xiàn)

圖4 政策文本分類算法流程圖

將網(wǎng)頁文本抓取入庫后，抽取所有河北省數(shù)據(jù)作為訓(xùn)練集。首先通過NLPIR漢語分詞系統(tǒng)將文本碎片化為河北政策語料庫。然后通過模糊查詢模擬聚類結(jié)果得到200條其他省的政策文本并抽取文本特征詞作為測試集，將測試集詞庫與訓(xùn)練集詞庫(即河北政策詞庫)進(jìn)行匹配分類。圖4為分類算法流程圖。

算法具體步驟如下：

從已經(jīng)抓取的政策庫中抽取所有河北政策文本作為訓(xùn)練集C1；

使用分詞系統(tǒng)對河北政策文本進(jìn)行分詞得到河北政策詞庫K1；

使用加權(quán)算法給訓(xùn)練集詞庫中的特征詞加權(quán)；

對數(shù)據(jù)庫進(jìn)行模糊查詢隨機(jī)抽取200條外省政策模擬聚類結(jié)果，得到測試集C2；

對測試集文本進(jìn)行分詞得到測試詞庫K2并計(jì)算特征詞權(quán)值；

使用基于特征詞加權(quán)的相似度閾值算法計(jì)算閾值W12；

使用Jaro-Winkler Distance算法計(jì)算訓(xùn)練集詞庫中所有特征詞與測試集詞庫中所有特征詞的相似度，根據(jù)閾值W12判定是否為相似(相似度小于W12為不相似，反之則認(rèn)為相似)得到相似詞庫S12。

根據(jù)一個(gè)特征詞唯一對應(yīng)一條文本數(shù)據(jù)的性質(zhì)遍歷S12中所有特征詞，取出C2中的相似文本得到相似文本集合C12。

4 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

4.1 實(shí)驗(yàn)環(huán)境介紹

Windows 7系統(tǒng)，Eclipse，Tomcat7.40，JDK1.8

4.2 實(shí)驗(yàn)結(jié)果的評估標(biāo)準(zhǔn)

文本分類結(jié)果評估指標(biāo)使用信息檢索中常用的標(biāo)準(zhǔn)，即查全率(Recall)、查準(zhǔn)率(Precision)：

查全率P=相似文本個(gè)數(shù)/ 測試集文本個(gè)數(shù)，即系統(tǒng)檢索出相關(guān)信息的能力；

查準(zhǔn)率R=相似文本個(gè)數(shù)/ 參與測試的文本個(gè)數(shù)，即系統(tǒng)拒絕非相關(guān)信息的能力。

綜合指標(biāo)F=2×R×P/(R+P)，表示分類算法的綜合分類效率。

4.3 實(shí)驗(yàn)數(shù)據(jù)準(zhǔn)備

本文針對于政策文本進(jìn)行分類，實(shí)驗(yàn)政策文本選自于河北人社廳、工信廳、科技廳、政府等11個(gè)部門下的政策法規(guī)欄目的政策文本。通過主題爬蟲Web Magic將相關(guān)政策文本抓取入庫并進(jìn)行結(jié)構(gòu)化整理。數(shù)據(jù)庫中政策表的部分字段如表1所示。

表1 文本數(shù)據(jù)結(jié)構(gòu)化表

圖5 實(shí)驗(yàn)數(shù)據(jù)分布

本次實(shí)驗(yàn)數(shù)據(jù)是從已抓取的政策數(shù)據(jù)庫中抽取，為了使實(shí)驗(yàn)更加具有普遍性因此選取了各個(gè)行業(yè)相關(guān)的政策文本作為實(shí)驗(yàn)數(shù)據(jù)集。

4.4 實(shí)驗(yàn)結(jié)果分析

三種字符串相似度算法對應(yīng)的分類結(jié)果的準(zhǔn)確率與時(shí)間消耗(查準(zhǔn)率、查全率及分類時(shí)間分別用B、P和T表示)。實(shí)驗(yàn)一，比較三種字符串算法用于分類的性能。

由實(shí)驗(yàn)結(jié)果可知，在三種字符串相似度算法中Jaro-Winkler Distance算法時(shí)間消耗較少，準(zhǔn)確率高，最適合用于政策文本分類。

表2 算法對比結(jié)果表

實(shí)驗(yàn)二，比較本文分類算法與傳統(tǒng)分類算法對于政策文本分類的性能。

表3 算法分類效果對比表

由表3可知，本文改進(jìn)算法在政策文本分類中性能優(yōu)于傳統(tǒng)分類算法，滿足實(shí)際需求。

5 總結(jié)

本文首先介紹了文本分類的研究背景和相關(guān)研究現(xiàn)狀，然后對普遍用于文本分類的三種字符串匹配算法進(jìn)行了分析及比較實(shí)驗(yàn)，選取了最適合政策文本分類的字符串匹配算法，并提出了一種基于特征詞加權(quán)的相似度閾值計(jì)算方法。然而對于不同類型的文本特征詞出現(xiàn)的位置及數(shù)量也不同，如何高效的抽取一篇文本的特征詞，抽取幾個(gè)特征詞能夠恰當(dāng)?shù)拇硪黄谋臼且粋€(gè)值得研究的方向。由于該文只是抽取河北政策文本作為實(shí)驗(yàn)訓(xùn)練集數(shù)據(jù)，對于其他省市政策分類的系數(shù)還有待具體調(diào)整，如何恰當(dāng)?shù)倪x取值來適應(yīng)不同地區(qū)政策分類也是一個(gè)有待研究的方向。

[1] 張強(qiáng).網(wǎng)頁內(nèi)容獲取及基于意圖的聚類[D].北京郵電大學(xué), 2010.

[2] 陸洋.基于語義分析的文本挖掘研究[D].浙江工業(yè)大學(xué), 2011.

[3] 白凡.改進(jìn)的K近鄰算法在網(wǎng)頁文本分類中的應(yīng)用[D].安徽大學(xué), 2010.

[4] 曾俊.結(jié)合SVM和KNN的Web日志挖掘技術(shù)研究方法[J].計(jì)算機(jī)應(yīng)用研究, 2012, 29(5):1926-1928.

[5] 王艷, 張帆, 楊炳儒.基于Web挖掘的數(shù)字圖書館個(gè)性化技術(shù)研究[J].情報(bào)雜志, 2007, 26(1):37-38.

[6] 何鋒, 谷鎖林, 陳彥輝.基于編輯距離相似度的文本校驗(yàn)技術(shù)研究與應(yīng)用[J].飛行器測控學(xué)報(bào), 2015, 34(4):389-394.

[7] 吳凌芬,楊小淵,葉添杰,劉冰,王太宏.改進(jìn)Jaro-Winkler算法在迎賓機(jī)器人語音交互中的應(yīng)用[J].現(xiàn)代計(jì)算機(jī)(專業(yè)版),2015,(08):8-13.

[8] 彭凱, 汪偉, 楊煜普,等.基于余弦距離度量學(xué)習(xí)的偽K近鄰文本分類算法[J].計(jì)算機(jī)工程與設(shè)計(jì), 2013, 34(6):2200-2203.

[9] 盧葦, 彭雅.幾種常用文本分類算法性能比較與分析[J].湖南大學(xué)學(xué)報(bào)(自科版), 2007, 34(6):67-69.

[10] 刁力力, 王麗坤, 陸玉昌,等.計(jì)算文本相似度閾值的方法[J].清華大學(xué)學(xué)報(bào)(自然科學(xué)版), 2003, 43(1):108-111.

Researchandimplementationoftextcategorizationalgorithmbasedonfeaturewordmatching

WANGLi-peng，ZHANGPeng-yun,HEZhi-qiang

(HebeiUniversityofEconomicsandBusiness,ShijiazhuangHebei050061,China)

In the text categorization algorithm based on the feature word traversal matching, the selection of the string matching algorithm and the similarity threshold control play a decisive role in the text classification result.In this paper, three commonly used string matching algorithms are analyzed and compared experimentally, then, a string matching algorithm which is most suitable for policy text classification is selected.Finally, a similarity threshold calculation method based on feature word weighting is proposed by studying the characteristics of policy text.It is proved that the similarity threshold can meet the classification requirement.

String matching algorithm；Threshold calculation；Text categorization

2017-09-20

河北省科技創(chuàng)新政策法規(guī)需求庫建設(shè)研究(17960119D)

王麗鵬(1991-)，男，河北邯鄲人，碩士研究生，主要從事數(shù)據(jù)挖掘，高速數(shù)據(jù)采集研究.

1001-9383(2017)03-0001-06

TP391

A