一種基于aPlorl算法改進的knn文本分類方法

駱凡，彭艷兵

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

?

一種基于aPlorl算法改進的knn文本分類方法

駱凡1，彭艷兵2

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

摘要：針對現在機器學習的文本分類算法普遍使用的knn，支持向量機，神經網絡等算法進行分類中存在的兩個問題，沒有考慮到語義關聯對其文本的影響和受文章長短對其詞頻向量大小的影響，通過結合apjorj算法進行改進knn算法的方法對文本分類樣本進行了分類實驗，結果表明，該改進算法相對于為改進前平均查準率有10%左右的提升，平均召回率有5%左右的提升，得出該方法能有效提高文本分類準確率的結論。

關鍵詞：文本分類；knn；關聯規則；apjorj

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

1　關聯規則

關聯規則是形如X→Y的蘊含表達式，其中X和Y是不相交的項集，即X∩Y≠空集。關聯規則的強度可以用它的支持度（support）和置信度（confjdence）度量。支持度（s）和置信度（c）這兩種度量的形式定義如下：

因此關聯規則挖掘任務分解為如下兩個主要子任務：

1）頻繁項集產生：其目標是發現滿足最小支持度閥值的所有項集，這些項集稱作頻繁項集

2）規則的產生：其目標是從上一步發現的頻繁項集中提取所有高度置信的規則，這些規則稱作強規則。

2　APrlorl算法運用于文本分類

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

3　KNN

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

4　基于APlorl的knn改進算法

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

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

其中wa12…nk為特征詞a1，a2，…，an同時存在時對文檔類型k的權重，wik為特征詞i單獨存在時對文檔類型k的權重。

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

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

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

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

因此距離公式修改為：

由此我們設計出的算法步驟如下：

1）進行文檔預處理，進行分詞

2）統計的到文檔的布爾模型和vsm模型

4）使用經特征提取的布爾模型，進行關聯規則挖掘，使用Aprjorj算法產生頻繁項集與規則，計算出各個頻繁項集的支持度support和各個頻繁項集對各個文檔分類的置信度confjdence

5）根據tf-jdf［2］公式計算vsm模型關鍵字權值：然后排序取前k個特征

6）然后根據更改的knn距離公式計算距離

7）最后使用knn分類規則進行分類，這里使用距離加權表決公式提高其分類準確度：

其中wi=1/i。

這里knn算法中每篇文章取k個特征詞構成特征詞庫，而進行apjorj算法時每篇文章取j個詞構成特征項集，由于詞語關聯需要更多的詞進行關聯以免漏掉關聯性，這里暫取k=30，j=40。

5　實驗應用

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

圖1　文本分類流程圖

首先我們進行knn算法實驗，我們先設定每篇文章取特征詞30個，進行knn實驗，取k不同時所有文檔的平均準確率如圖2所示。

圖2　k取不同值時knn分類算法準確率

由圖1所示k取5時算法復雜性和準確率方面的都能達到較好的效果，因此取k=5進行對比實驗。實驗結果如表1，2所示。

表1　普通knn算法分類結果

每類50個測試樣本，平均查準率為68.4%，平均召回率為63.7%。

每類50個測試樣本，平均查準率為75%，平均召回率為69%。

表1　aPlorl算法改進knn算法分類結果

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

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

表1　是否改進算法和特征詞數對分類效果的影響

由表3可以看出優化算法在特征詞數少時較為明顯，且在特征詞數j=20時算法效果就已經接近于j=30時的數值，說明使用優化算法，在特征詞數從20到30對于分類效果的影響已經接近飽和。其原因可能是因為aprjorj改進算法恰好彌補了那些tf-jdf值不夠高的詞對于文章分類的影響。

6　結論

文中從文本分類的各個方法開始，總結了各個方法的優缺點，提出了通過apjorj算法優化原始knn算法進行文本分類的方法試圖解決語義關聯，詞頻受文章長短影響等問題，通過實驗證明該方法確實有效提高了準確率。

參考文獻：

［1］李仁.關聯規則在文本分類中的研究［D］.南昌：南昌大學，2008.

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

［3］許珂，蒙祖強，林啓峰.基于語義關聯和信息增益的TFIDF改進算法研究［J］.計算機應用與研究，2012，29（2）：557-560.

［4］黨齊民，呂冬煜.基于詞關聯語義的文本分類研究［J］.計算機應用，2004，24（4）：62-66.

［5］趙耀.基于關聯規則的文本分類研究［D］.保定：河北大學，2010.

［6］范恒亮，成衛青.一種基于關聯分析的KNN文本分類方法［J］.計算機技術與發展，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，FiberHome Communications Science&Technology Development Co.，Nanjing 210019，China）

Key words:text c1assjfjcatjon；knn；assocjatjon ru1es；apjorj隨著互聯網信息的飛速增長，文本分類變成了一項處理和資質文本信息的關鍵技術。文本分類技術可用于分類新聞，在互聯網上尋找有趣的信息，或者通過超文本去直到用戶的搜索，因為手動建立文本分類器是很困難和耗時的，通過實例去學習分類在這方面就很有優勢。

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

文獻標識碼：A

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

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

基金項目：國家863計劃資助項目（2012AA013002）；江蘇省科技支撐計劃（2015BAK20B01）

作者簡介：駱凡（1991—），男，湖北武漢人，碩士。研究方向：大數據、機器學習。