駱凡，彭艷兵

（1.武漢郵電科學(xué)研究院湖北武漢430074；2.烽火通信科技股份有限公司南京研發(fā)部，江蘇南京210019）

?

一種基于aPlorl算法改進(jìn)的knn文本分類方法

駱凡1，彭艷兵2

（1.武漢郵電科學(xué)研究院湖北武漢430074；2.烽火通信科技股份有限公司南京研發(fā)部，江蘇南京210019）

摘要：針對現(xiàn)在機(jī)器學(xué)習(xí)的文本分類算法普遍使用的knn，支持向量機(jī)，神經(jīng)網(wǎng)絡(luò)等算法進(jìn)行分類中存在的兩個(gè)問題，沒有考慮到語義關(guān)聯(lián)對其文本的影響和受文章長短對其詞頻向量大小的影響，通過結(jié)合apjorj算法進(jìn)行改進(jìn)knn算法的方法對文本分類樣本進(jìn)行了分類實(shí)驗(yàn)，結(jié)果表明，該改進(jìn)算法相對于為改進(jìn)前平均查準(zhǔn)率有10%左右的提升，平均召回率有5%左右的提升，得出該方法能有效提高文本分類準(zhǔn)確率的結(jié)論。

關(guān)鍵詞：文本分類；knn；關(guān)聯(lián)規(guī)則；apjorj

一般的文本分類分為這幾個(gè)步驟，首先是建立文檔的表示模型，即通過若干特征去表示一個(gè)文本，因?yàn)橐话闱闆r下一篇文章都有著成百上千的特征向量，直接進(jìn)行分類會(huì)有很大的時(shí)間和空間上的消耗，所以在分類之前，必須先進(jìn)行特征降維，特征降維的方法主要有信息增益，X2統(tǒng)計(jì)，互信息，tf-jdf等方法，然后就要開始進(jìn)行分類，常用的一些方法有貝葉斯，knn，支持向量機(jī)，關(guān)聯(lián)規(guī)則等。其中應(yīng)用較廣的knn等方法中存在受文章長短影響和忽略了語義關(guān)聯(lián)的影響等一些問題。本文針對這些問題結(jié)合了apjorj算法與knn算法，解決了上述的問題。

1　關(guān)聯(lián)規(guī)則

關(guān)聯(lián)規(guī)則是形如X→Y的蘊(yùn)含表達(dá)式，其中X和Y是不相交的項(xiàng)集，即X∩Y≠空集。關(guān)聯(lián)規(guī)則的強(qiáng)度可以用它的支持度（support）和置信度（confjdence）度量。支持度（s）和置信度（c）這兩種度量的形式定義如下：

因此關(guān)聯(lián)規(guī)則挖掘任務(wù)分解為如下兩個(gè)主要子任務(wù)：

1）頻繁項(xiàng)集產(chǎn)生：其目標(biāo)是發(fā)現(xiàn)滿足最小支持度閥值的所有項(xiàng)集，這些項(xiàng)集稱作頻繁項(xiàng)集

2）規(guī)則的產(chǎn)生：其目標(biāo)是從上一步發(fā)現(xiàn)的頻繁項(xiàng)集中提取所有高度置信的規(guī)則，這些規(guī)則稱作強(qiáng)規(guī)則。

2　APrlorl算法運(yùn)用于文本分類

Aprjorj是一種解決頻繁項(xiàng)集上述兩個(gè)任務(wù)的有效的算法。該算法［1］算出符合條件的支持度sup和置信度conf。使用關(guān)聯(lián)規(guī)則的方法文本分類，首先要將文本轉(zhuǎn)化為形如｛A，B，C，D…，Y1｝項(xiàng)集的模式其中A，B，C..是特征詞，Y1是目標(biāo)類，將所有的文本轉(zhuǎn)化為項(xiàng)集的后使用Aprjorj算法計(jì)算頻繁項(xiàng)集與規(guī)則，我們只需要計(jì)算與分類Y相關(guān)的規(guī)則，因此可以由訓(xùn)練集｛D1，Y1｝，｛D2，Y1｝…，｛Dm，Yn｝（其中m為文本數(shù)，n為種類數(shù)）得到型如Xi→Yj，其中Xi?Dk?k∈［1，m］，j∈［1，n］的規(guī)則，及支持度sup（Xi→Yj）和置信度con（Xi→Yj），將其記做r，然后根據(jù)支持度和置信度的規(guī)則進(jìn)行分類。

3　KNN

KNN是一種非常簡單的分類方法，最鄰近分類器把每個(gè)樣例看做d維空間上的一個(gè)數(shù)據(jù)點(diǎn)，其中d是屬性個(gè)數(shù)。給定一個(gè)測試樣例，我們使用任意一種臨近性度量，計(jì)算該測試樣例的訓(xùn)練集中其他數(shù)據(jù)點(diǎn)的臨近度。給定樣例z是k-最鄰近是指和z距離最近的k個(gè)數(shù)據(jù)點(diǎn)。提出位于數(shù)據(jù)點(diǎn)的1-最鄰近，2-最鄰近到k-最鄰近，該數(shù)據(jù)點(diǎn)根據(jù)去鄰近的類標(biāo)號進(jìn)行分類。如果數(shù)據(jù)點(diǎn)的鄰近中含有多個(gè)類標(biāo)號，則將該數(shù)據(jù)點(diǎn)指派到其最鄰近的多數(shù)類。

4　基于APlorl的knn改進(jìn)算法

根據(jù)引文所述，而其中關(guān)聯(lián)規(guī)則從文本分類的方法上來看是一種不同于貝葉斯，KNN，支持向量機(jī)這樣的方法的，它們很大的弊端就是這種方法忽略了詞與詞之間的關(guān)系的影響，這種傳統(tǒng)的方法認(rèn)為特征與特征之間是相互獨(dú)立的，而事實(shí)上在文檔中詞與詞之間存在豐富的語義關(guān)聯(lián)［4］。

這種特性我們闡述為語義關(guān)聯(lián)的非對稱性，如果有特征詞a1，a2，…，an，文本類型k，則存在：

其中wa12…nk為特征詞a1，a2，…，an同時(shí)存在時(shí)對文檔類型k的權(quán)重，wik為特征詞i單獨(dú)存在時(shí)對文檔類型k的權(quán)重。

而關(guān)聯(lián)規(guī)則的分類方法就能解決這兩個(gè)問題，首先關(guān)聯(lián)規(guī)則所使用過的文本表示模型是基于布爾模型，減少了文章長短因素給特征值帶來的影響。其次對于語義關(guān)聯(lián)我們首先要找到可能含有這種特性的特征詞集，即通過aprjorj算法尋找頻繁項(xiàng)集，找出關(guān)聯(lián)規(guī)則，然后就可以根據(jù)cba分類算法［5］找出各個(gè)頻繁項(xiàng)集對某個(gè)文章分類的置信度，這些頻繁項(xiàng)集可能是2-項(xiàng)集，3-項(xiàng)集等，因此包含了語義之間關(guān)聯(lián)的問題。

對語義關(guān)聯(lián)的問題很多研究者都進(jìn)行了研究和改進(jìn)，許珂［3］根據(jù)詞語關(guān)系庫進(jìn)行分析，來修改tf-jdf公式進(jìn)行改進(jìn)。范恒亮［6］是使用的關(guān)聯(lián)規(guī)則進(jìn)行語義關(guān)聯(lián)分析，但是其方法只在頻繁項(xiàng)集的基礎(chǔ)上進(jìn)行了合理化建模，其思路是將測試文本所有的特征詞提取出來作為特征與其訓(xùn)練文本的頻繁項(xiàng)集進(jìn)行對比，但是這樣會(huì)導(dǎo)致其語義關(guān)聯(lián)的特性的劃分不夠明確，可能會(huì)導(dǎo)致事實(shí)上沒有語義關(guān)聯(lián)關(guān)系的詞語會(huì)作為關(guān)聯(lián)規(guī)則關(guān)系進(jìn)行計(jì)算。

這里我們需要將關(guān)聯(lián)規(guī)則的分類算法轉(zhuǎn)換為可量化的能與knn算法結(jié)合的方式，可行的方法是將是否存在頻繁項(xiàng)集Xi也作為一個(gè)屬性，加入到knn算法中進(jìn)行計(jì)算，這里是否存在是一個(gè)布爾屬性，記存在頻繁項(xiàng)集Xi為1，不存在為0，可以看到是否存在頻繁項(xiàng)集Xi這個(gè)屬性boo1（Xi）對每一類的均值就是conf（Xi→Yi），由此結(jié)合knn距離公式得到新的距離公式，根據(jù)歐幾里得距離測試樣例Xe與訓(xùn)練樣例（x，yi）的距離：

這里我們需要對公式進(jìn)行一些修正，首先我們需要修正詞頻與布爾值之間的量級關(guān)系，設(shè)定一個(gè)參數(shù)α為向量x即詞頻的均值。其次各個(gè)將各個(gè)項(xiàng)集分為1-項(xiàng)集，2-項(xiàng)集等，記為X（1），X（2），因?yàn)槎囗?xiàng)集對于分類的影響會(huì)明顯高于項(xiàng)數(shù)少的項(xiàng)集，所以我們設(shè)定一個(gè)ki=i的參數(shù)對項(xiàng)集X（k）進(jìn)行修正。鑒于算法復(fù)雜度和多項(xiàng)集存在關(guān)聯(lián)概率較低的考慮，我們選擇m=3。

因此距離公式修改為：

由此我們設(shè)計(jì)出的算法步驟如下：

1）進(jìn)行文檔預(yù)處理，進(jìn)行分詞

2）統(tǒng)計(jì)的到文檔的布爾模型和vsm模型

4）使用經(jīng)特征提取的布爾模型，進(jìn)行關(guān)聯(lián)規(guī)則挖掘，使用Aprjorj算法產(chǎn)生頻繁項(xiàng)集與規(guī)則，計(jì)算出各個(gè)頻繁項(xiàng)集的支持度support和各個(gè)頻繁項(xiàng)集對各個(gè)文檔分類的置信度confjdence

5）根據(jù)tf-jdf［2］公式計(jì)算vsm模型關(guān)鍵字權(quán)值：然后排序取前k個(gè)特征

6）然后根據(jù)更改的knn距離公式計(jì)算距離

7）最后使用knn分類規(guī)則進(jìn)行分類，這里使用距離加權(quán)表決公式提高其分類準(zhǔn)確度：

其中wi=1/i。

這里knn算法中每篇文章取k個(gè)特征詞構(gòu)成特征詞庫，而進(jìn)行apjorj算法時(shí)每篇文章取j個(gè)詞構(gòu)成特征項(xiàng)集，由于詞語關(guān)聯(lián)需要更多的詞進(jìn)行關(guān)聯(lián)以免漏掉關(guān)聯(lián)性，這里暫取k=30，j=40。

5　實(shí)驗(yàn)應(yīng)用

為了驗(yàn)證本文提出的文本分類方法對準(zhǔn)確度的提高進(jìn)行了如下實(shí)驗(yàn)分析。實(shí)驗(yàn)語料庫采用復(fù)旦大學(xué)計(jì)算機(jī)信息與技術(shù)系國際數(shù)據(jù)庫中心自然語言處理小組提供的中文語料，訓(xùn)練語料9 804篇，測試語料9 833篇，含有經(jīng)濟(jì)，計(jì)算機(jī)，法律，醫(yī)藥等20種文本。為了避免分類語料的不均影響分類和保證實(shí)驗(yàn)效率，只抽取計(jì)算機(jī)，環(huán)境，農(nóng)業(yè)等6個(gè)類別，每個(gè)類別取50篇訓(xùn)練和測試文本。分類程序采用編寫簡單，函數(shù)庫豐富的python語言實(shí)現(xiàn)，中文分詞采用的jjeba分詞庫。分類流程如圖1所示進(jìn)行分類，分別從查準(zhǔn)率和召回率兩個(gè)評估指標(biāo)對算法的分類效果進(jìn)行比較。文本分類流程如圖1所示。

圖1　文本分類流程圖

首先我們進(jìn)行knn算法實(shí)驗(yàn)，我們先設(shè)定每篇文章取特征詞30個(gè)，進(jìn)行knn實(shí)驗(yàn)，取k不同時(shí)所有文檔的平均準(zhǔn)確率如圖2所示。

圖2　k取不同值時(shí)knn分類算法準(zhǔn)確率

由圖1所示k取5時(shí)算法復(fù)雜性和準(zhǔn)確率方面的都能達(dá)到較好的效果，因此取k=5進(jìn)行對比實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果如表1，2所示。

表1　普通knn算法分類結(jié)果

每類50個(gè)測試樣本，平均查準(zhǔn)率為68.4%，平均召回率為63.7%。

每類50個(gè)測試樣本，平均查準(zhǔn)率為75%，平均召回率為69%。

表1　aPlorl算法改進(jìn)knn算法分類結(jié)果

根據(jù)表1和表2的結(jié)果對比可以看出使用apjorj算法改進(jìn)的knn分類方法相對于普通的knn分類方法其平均查準(zhǔn)率和召回率都有不同程度的提高，這證明了通過apjorj算法改進(jìn)knn分類方法考慮了語義關(guān)聯(lián)和文章長短的影響，使得分類準(zhǔn)確率的到了提高。

為了研究取得特征值數(shù)量對分類算法的影響，分別對knn算法中tf-jdf取的每篇文章的詞頻特征詞j=10，20，30和是否使用apjorj算法改進(jìn)，進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果F值如表3所示。

表1　是否改進(jìn)算法和特征詞數(shù)對分類效果的影響

由表3可以看出優(yōu)化算法在特征詞數(shù)少時(shí)較為明顯，且在特征詞數(shù)j=20時(shí)算法效果就已經(jīng)接近于j=30時(shí)的數(shù)值，說明使用優(yōu)化算法，在特征詞數(shù)從20到30對于分類效果的影響已經(jīng)接近飽和。其原因可能是因?yàn)閍prjorj改進(jìn)算法恰好彌補(bǔ)了那些tf-jdf值不夠高的詞對于文章分類的影響。

6　結(jié)論

文中從文本分類的各個(gè)方法開始，總結(jié)了各個(gè)方法的優(yōu)缺點(diǎn)，提出了通過apjorj算法優(yōu)化原始knn算法進(jìn)行文本分類的方法試圖解決語義關(guān)聯(lián)，詞頻受文章長短影響等問題，通過實(shí)驗(yàn)證明該方法確實(shí)有效提高了準(zhǔn)確率。

參考文獻(xiàn)：

［1］李仁.關(guān)聯(lián)規(guī)則在文本分類中的研究［D］.南昌：南昌大學(xué)，2008.

［2］鄭霖，徐德華.基于改進(jìn)TFIDF算法的文本分類研究［J］.計(jì)算機(jī)與現(xiàn)代化，2014（9）：6-9，14.

［3］許珂，蒙祖強(qiáng)，林啓峰.基于語義關(guān)聯(lián)和信息增益的TFIDF改進(jìn)算法研究［J］.計(jì)算機(jī)應(yīng)用與研究，2012，29（2）：557-560.

［4］黨齊民，呂冬煜.基于詞關(guān)聯(lián)語義的文本分類研究［J］.計(jì)算機(jī)應(yīng)用，2004，24（4）：62-66.

［5］趙耀.基于關(guān)聯(lián)規(guī)則的文本分類研究［D］.保定：河北大學(xué)，2010.

［6］范恒亮，成衛(wèi)青.一種基于關(guān)聯(lián)分析的KNN文本分類方法［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2014，24（6）：71-74.

A uslng aPlorl algorlthm lmProved knn teXt classlflcatlon method

LUO Fan1，PENG Yan-bjng2

（1.Wuhan Research Institute of Posts and Telecommunications，Wuhan 430074，China；
2. Ltd.Nanjing R & D，F(xiàn)iberHome Communications Science&Technology Development Co.，Nanjing 210019，China）

Key words:text c1assjfjcatjon；knn；assocjatjon ru1es；apjorj隨著互聯(lián)網(wǎng)信息的飛速增長，文本分類變成了一項(xiàng)處理和資質(zhì)文本信息的關(guān)鍵技術(shù)。文本分類技術(shù)可用于分類新聞，在互聯(lián)網(wǎng)上尋找有趣的信息，或者通過超文本去直到用戶的搜索，因?yàn)槭謩?dòng)建立文本分類器是很困難和耗時(shí)的，通過實(shí)例去學(xué)習(xí)分類在這方面就很有優(yōu)勢。

Abstract:In vjew of now the text c1assjfjcatjon of machjne 1earnjng genera1 usjng KNN，Support Vector Machjne（SVM），neura1 network and so on a1gorjthm have two majn questjon，one js not consjderjng of the re1atjonshjp between the words，the other one js the frequent of words feature vector on the affect of 1ongth varjatjon artjc1e，by means of combjnjng wjth apjorj a1gorjthm to jmproved knn a1gorjthm to conduct an experjment.The experjmenta1 resu1t proves thjs method can jmprove precjsjon about 10%and reca11 rate about 5%，come to a conc1usjon that thjs method can jmprove the c1assjfjcatjon precjsjon effectjve1y.

中圖分類號：TP301.6

文獻(xiàn)標(biāo)識碼：A

文章編號：1674-6236（2016）07-0001-03

收稿日期：2015-10-29稿件編號：201510206

基金項(xiàng)目：國家863計(jì)劃資助項(xiàng)目（2012AA013002）；江蘇省科技支撐計(jì)劃（2015BAK20B01）

作者簡介：駱凡（1991—），男，湖北武漢人，碩士。研究方向：大數(shù)據(jù)、機(jī)器學(xué)習(xí)。