基于三支決策的KNN漸進(jìn)式文本分類方法

作者簡(jiǎn)介：馬新宇（1996－），男，黑龍江哈爾濱人，碩士，主要研究方向?yàn)槿Q策、機(jī)器學(xué)習(xí)；黃春梅（1974－），女（通信作者），黑龍江人，副教授，碩導(dǎo)，碩士，主要研究方向?yàn)槿Q策（huangchunmeihl@163.com）；姜春茂（1972－），男，黑龍江人，教授，碩導(dǎo)，博士，主要研究方向?yàn)樵朴?jì)算、智能決策.

摘 要：在傳統(tǒng)的文本分類中，KNN算法以其簡(jiǎn)單、分類準(zhǔn)確率高、非參數(shù)得到了廣泛的應(yīng)用。但是傳統(tǒng)KNN算法在進(jìn)行文本分類的過程中，需要計(jì)算待分類文本與每一個(gè)訓(xùn)練樣本的相似度，當(dāng)面對(duì)海量的文本時(shí)，分類的效果會(huì)明顯降低。針對(duì)此問題，提出了一種基于三支決策的KNN漸進(jìn)式文本分類方法用于提高其分類效率，結(jié)合三支決策在分類問題中的優(yōu)勢(shì)，將三支決策與KNN算法相結(jié)合，對(duì)標(biāo)題、摘要、關(guān)鍵詞等進(jìn)行漸進(jìn)式的分類處理，從而完成待分類文本的分類，提高文本分類的效率和性能。實(shí)驗(yàn)表明，該算法能夠在確保KNN算法分類準(zhǔn)確率的基礎(chǔ)上，同時(shí)提高分類效率。

關(guān)鍵詞：三支決策；KNN算法；漸進(jìn)式；文本分類

中圖分類號(hào)：TP391.1 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1001－3695（2023）04－017－1065－05doi： 10.19734/j.issn.1001－3695.2022.08.0457

Abstract：In the traditional text classification， KNN algorithm is widely used in text classification because of its simplicity， high classification accuracy and non parameter. However， in the process of text classification， traditional KNN needs to calculate the similarity between the text to be classified and each training sample. When faced with massive text， the classification effect will be significantly reduced. To solve this problem， this paper proposed a KNN progressive text classification method based on three-way decision making to improve its classification efficiency. With the advantages of three-way decision in classification， this algorithm combined the three-way decision with KNN algorithm， through the title， abstract， keywords and other progressive classification processing， so as to complete the text classification and improve the efficiency and performance of text classification. Experiments show that the algorithm can ensure the classification accuracy of KNN algorithm and improve the classification efficiency at the same time.

Key words：three-way decision; KNN algorithm; progressive; text classification

0 引言

隨著互聯(lián)網(wǎng)的迅速發(fā)展和網(wǎng)絡(luò)文本海量增加，從海量的文本數(shù)據(jù)中挖掘出有價(jià)值的信息已經(jīng)成為了人們關(guān)注的熱點(diǎn)。分類是數(shù)據(jù)挖掘中的實(shí)用技術(shù)之一［1］，通過從海量文本中確定數(shù)據(jù)類別，幫助人們從中發(fā)現(xiàn)大量有用的知識(shí)。常見的分類算法包括神經(jīng)網(wǎng)絡(luò)［2］、SVM［3］、決策樹［4］和KNN［5］等。其中，KNN算法因其簡(jiǎn)單有效，在分類算法中有著廣泛的應(yīng)用。其基本思想是：首先從訓(xùn)練樣本中尋找與待測(cè)樣本距離最近的k個(gè)樣本，然后根據(jù)這k個(gè)距離最近樣本的類進(jìn)行概率計(jì)算，通過投票來得到分類的結(jié)果，以此來決定測(cè)試樣本的類別。然而，面向海量文本數(shù)據(jù)時(shí)，傳統(tǒng)的KNN算法存在分類計(jì)算量巨大的問題，即隨著文本不斷增加，特征維數(shù)也會(huì)增加，每一個(gè)待分類文本都要計(jì)算它到全體已知樣本的距離，才能得到它的第k個(gè)最近鄰點(diǎn)，使得算法的效率下降，特征越多，分類的效率越低。因此，一系列改進(jìn)KNN算法相繼被提出［6～10］，用于解決KNN算法在面對(duì)海量的文本數(shù)據(jù)時(shí)分類效率較低的這一缺陷。

對(duì)于此，很多學(xué)者開展基于改進(jìn)KNN的算法研究，大致可以分為兩類：a）通過精簡(jiǎn)訓(xùn)練樣本數(shù)量或特征維度；b）采用快速搜索方法，通過對(duì)搜索速度的提升來直接提升KNN的分類效率。文獻(xiàn)［6］通過粗糙集和KNN分類算法將訓(xùn)練集分為了確定集和不確定集，確定集直接分類，不確定集再通過KNN算法進(jìn)行進(jìn)一步的分析確定類別，其大大提高了文本分類的效率和準(zhǔn)確性，且滿足處理大量文本數(shù)據(jù)的要求。文獻(xiàn)［7］提出一種基于加權(quán)局部線性KNN的文本分類算法，通過加權(quán)表示系數(shù)，引入非負(fù)約束來規(guī)避表示系數(shù)出現(xiàn)的噪聲干擾，通過實(shí)驗(yàn)表明所提算法在文本分類上具有準(zhǔn)確率較高、收斂性強(qiáng)等優(yōu)勢(shì)。文獻(xiàn)［8］提出了一種基于密度的訓(xùn)練樣本裁剪方法，使樣本分布密度趨于平均，降低了KNN的計(jì)算量。文獻(xiàn)［9］提出一種基于關(guān)鍵詞相似度作為文本特征，能夠有效挖掘出文本與不同類別的核心語義關(guān)聯(lián)，在轉(zhuǎn)換為特征向量的過程中保留語義，降低了特征維度，提高了分類效率。文獻(xiàn)［10］提出了一種基于聚類改進(jìn)KNN算法進(jìn)行文本分類，采用改進(jìn)χ2統(tǒng)計(jì)量方法進(jìn)行文本特征提取，提高了分類精度。

針對(duì)KNN算法在面對(duì)海量文本數(shù)據(jù)時(shí)，隨著數(shù)據(jù)規(guī)模的增大而分類效率降低這一問題，本文主要通過對(duì)文本特性和漸進(jìn)式方法進(jìn)行結(jié)合，將待分類文本在不用進(jìn)行全文分析的基礎(chǔ)上成功分類。首先，分析文本數(shù)據(jù)基本特性，由于文本大部分都有著明顯特性，例如標(biāo)題作為文本的主要核心，多數(shù)文本憑著標(biāo)題就可以知道其所屬的類別；其次，進(jìn)行漸進(jìn)式文本處理，主要依據(jù)在于文本的摘要和關(guān)鍵詞是文章整體的精華所在，當(dāng)文本沒有標(biāo)題時(shí)，可以根據(jù)文章首段判別文本的類別；最后，根據(jù)文本特性和漸進(jìn)式文本處理方式完成整體文本分類。

當(dāng)存在海量文本數(shù)據(jù)時(shí)，對(duì)于全文進(jìn)行分析和只進(jìn)行標(biāo)題或者摘要和關(guān)鍵詞來說，后者可以大大地降低計(jì)算成本，降低時(shí)間復(fù)雜度。但是，從單個(gè)層次上來說，只針對(duì)標(biāo)題或者是只針對(duì)摘要和關(guān)鍵詞，其在大量降低時(shí)間復(fù)雜度的同時(shí)，也要面對(duì)獲取的信息少的這一問題，特征的降低使得其在面對(duì)某些文本時(shí)，分類的準(zhǔn)確率上不可避免地會(huì)降低。三支決策在二支決策的基礎(chǔ)上引入了中間域的概念，能更好地描述類別邊界模糊的結(jié)構(gòu)特征，避免了二支決策的缺陷，將對(duì)象與類的關(guān)系分為了對(duì)象確定屬于該類別（POS）、對(duì)象確定不屬于該類別（NEG）和不確定對(duì)象是否屬于該類別（BND）三種。結(jié)合三支決策在面對(duì)分類問題處理的優(yōu)勢(shì)，將三支決策與文本分類相結(jié)合，然而根據(jù)現(xiàn)有的決策規(guī)則，單步三支決策往往只考慮單一粒度，易導(dǎo)致決策結(jié)果的高錯(cuò)誤分類率（ECR）。

本文提出一種基于三支決策的KNN漸進(jìn)式文本分類方法。借鑒多粒度思想，將三支決策和漸進(jìn)式文本分類方法結(jié)合，提供了從粗粒度到細(xì)粒度的漸進(jìn)式認(rèn)知過程，解決了KNN算法面對(duì)海量文本數(shù)據(jù)時(shí)，分類效果不佳和單步三支決策高錯(cuò)誤分類率的問題。首先，對(duì)文本數(shù)據(jù)進(jìn)行預(yù)處理和特征提取；然后采用結(jié)合三支決策思想的KNN算法將數(shù)據(jù)進(jìn)行劃分，將其劃分成POS域（接受）、NEG域（拒絕）和BND域（不確定）三個(gè)域，采用漸進(jìn)式思想接著對(duì)BND域和NEG域的數(shù)據(jù)繼續(xù)進(jìn)行劃分；最后實(shí)驗(yàn)表明，該算法在保證分類準(zhǔn)確率的基礎(chǔ)上提高了分類效率。

1 相關(guān)工作

1.1 三支決策

三支決策［11～13］是一種三層次決策理論框架。通過對(duì)傳統(tǒng)的二支決策進(jìn)行擴(kuò)展，三支決策引入不確定信息的不承諾決策選項(xiàng)，對(duì)不確定的情況進(jìn)行進(jìn)一步的研究處理。在實(shí)際問題應(yīng)用時(shí)，可以有效避免二支決策可能存在的高錯(cuò)誤率問題。

圖1表示由分、治、效三步結(jié)合的三支決策模型，展現(xiàn)了分、治、效這三者之間的關(guān)系。目前大多數(shù)三支決策的理論都是這種從上而下的模式，通過一個(gè)合理的三分區(qū)域的劃分來設(shè)計(jì)具有針對(duì)性的策略。

1.2 文本分類

文本分類通常是為了解決未知文本的歸類問題，通過其文本內(nèi)容在某些方面的特征，分類到其應(yīng)所屬的類別。文本分類的處理大致分為文本預(yù)處理、文本特征提取［17］等。

1.2.1 文本預(yù)處理

文本預(yù)處理主要是對(duì)中文文本進(jìn)行分詞并除去停用詞。由于中文往往缺少明確的分隔符，并且存在諸多對(duì)分類沒有信息價(jià)值的詞語，所以在分類之前需要對(duì)文本進(jìn)行預(yù)處理，將文本處理成詞語的表示形式并過濾掉部分信息價(jià)值較少的詞語。

1.2.2 特征項(xiàng)提取

文本預(yù)處理之后，得到的數(shù)據(jù)通常是半結(jié)構(gòu)化或無結(jié)構(gòu)化形式，而此類特征向量對(duì)文本進(jìn)行表示通常會(huì)提高維度，因此需要進(jìn)行特征抽取，降低特征維度。從原特征集合通過線性或非線性映射抽取出新的少量特征，而得到的新特征通常是從多個(gè)原始特征線性或非線性變換而來的。不同的特征提取方法在選擇詞的時(shí)候，都會(huì)有自己的傾向。

2 基于三支決策的漸進(jìn)式KNN文本分類

本章結(jié)合三支決策方法，將文本的隸屬度作為分類的主要依據(jù)，構(gòu)建漸進(jìn)式文本分類模型，并提出一種基于三支決策的漸進(jìn)式KNN文本快速分類算法。

2.1 基于隸屬度的三支決策

在基于隸屬度的三支決策分類模型中，將待分類文本根據(jù)其隸屬度將對(duì)象與類的關(guān)系分為了對(duì)象確定屬于該類別、對(duì)象確定不屬于該類別和不確定對(duì)象是否屬于該類別三種。基于此，給出一種基于隸屬度的三支決策分類（membership degree-based three-way decision，MD-TWD），如圖2所示。

上述過程通過對(duì)BND域進(jìn)行特征添加，在原來的特征上添加新的特征，形成一個(gè)新的特征向量集，計(jì)算其隸屬度μci，根據(jù)隸屬度μci將BND域再次進(jìn)行區(qū)域的劃分。

借助多級(jí)粒度的基本思想以及粗粒度到細(xì)粒度的漸進(jìn)認(rèn)知過程，本文提出一種基于三支決策的KNN漸進(jìn)式文本分類模型框架，如圖4所示。

首先，對(duì)文本數(shù)據(jù)進(jìn)行預(yù)處理，其中主要包括對(duì)中文文本進(jìn)行分詞并除去其停用詞；其次，文本預(yù)處理后對(duì)其進(jìn)行特征提取，降低特征維度；然后，將數(shù)據(jù)導(dǎo)入KNN算法中進(jìn)行劃分，判斷其隸屬度μci與閾值（α，β）的大小關(guān)系，將數(shù)據(jù)劃分成三個(gè)區(qū)域，POS域表示分類成功，對(duì)NEG域數(shù)據(jù)進(jìn)行全文文本分詞后再根據(jù)文本向量進(jìn)行KNN算法分類，對(duì)BND域進(jìn)行特征添加后繼續(xù)采用KNN算法分類，直到全部文本分類完成。

3.2 不同實(shí)驗(yàn)算法的對(duì)比與分析

3.2.1 參數(shù)設(shè)置

為驗(yàn)證本文算法性能，本文比較了所提出的算法和傳統(tǒng)KNN算法以及reference 4 algorithm的準(zhǔn)確率、召回率以及綜合分類率F1和運(yùn)行時(shí)間。

使用KNN算法進(jìn)行分類的時(shí)候，對(duì)于k值的選取非常重要［21］，k值較小易發(fā)生過擬合現(xiàn)象，k值較大易使分類發(fā)生錯(cuò)誤。因此，為了確定k值的取值，進(jìn)行了如下實(shí)驗(yàn)，采用相同的數(shù)據(jù)集，對(duì)比了在不同K值的情況下其準(zhǔn)確率、召回率和綜合分類率值的值，結(jié)果如圖5所示。

從圖5可知，隨著k值的增大，前期來看precision、recall和F1是上升的趨勢(shì)，但是當(dāng)后面k值不斷增大后，總體緩慢下降。在k=4時(shí)，總體取得較好的效果；取值過小，相似的數(shù)據(jù)有的未被包含進(jìn)來；取值過大，并不相似的數(shù)據(jù)又會(huì)被包含進(jìn)來，從而造成噪聲，導(dǎo)致分類效果下降，同時(shí)也使得計(jì)算量增加。因此，本文KNN算法中所選取的k值為4。

3.2.2 算法的時(shí)間比較

本文統(tǒng)計(jì)了算法的運(yùn)行時(shí)間，對(duì)于準(zhǔn)確率相同的算法，比較算法的運(yùn)行時(shí)間，運(yùn)行時(shí)間越少的算法，說明其分類的效率越高。為了排除隨機(jī)因素帶來的影響，進(jìn)行了多次實(shí)驗(yàn)，并取多次運(yùn)行時(shí)間的平均值作為實(shí)驗(yàn)時(shí)間。表2為三種不同算法的耗時(shí)比較，圖6為三種算法分別運(yùn)行10次的時(shí)間對(duì)比，從表2和圖6可以發(fā)現(xiàn)，reference 4 algorithm與MDP-3WD執(zhí)行時(shí)間比較接近，且穩(wěn)定；KNN算法的執(zhí)行時(shí)間約為reference 4 algorithm與MDP-3WD執(zhí)行時(shí)間的2～3倍，并且運(yùn)行時(shí)間不穩(wěn)定。

3.2.3 算法的性能比較

本次實(shí)驗(yàn)在k=4的情況下完成，以準(zhǔn)確率、召回率和F1為評(píng)價(jià)指標(biāo)，對(duì)算法進(jìn)行了對(duì)比實(shí)驗(yàn)，其實(shí)驗(yàn)結(jié)果如圖7～9所示。

如圖7所示，本文MDP-3WD相比于reference 4 algorithm的準(zhǔn)確率更高，在與KNN相比時(shí)，其分類準(zhǔn)確率基本差不多，但是從表2中可得，MDP-3WD算法分類的速度接近于傳統(tǒng)KNN算法的2～3倍，對(duì)測(cè)試集文本進(jìn)行處理后，在文本數(shù)量不變的情況下，通過降低其詞袋的長(zhǎng)度，大大降低了計(jì)算的開銷，從而提高其分類的效率。圖8為相同數(shù)據(jù)集下三種算法的召回率對(duì)比，往往召回率與準(zhǔn)確率相反，本文MDP-3WD相對(duì)穩(wěn)定。圖9為三種算法對(duì)于相同數(shù)據(jù)集綜合分類率F1值的直觀對(duì)比，證明了本文基于三支決策的KNN漸進(jìn)式文本分類算法在保證分類器分類性能的前提下，能夠有效地提高分類效率，帶來更好的時(shí)間性能。

4 結(jié)束語

本文針對(duì)傳統(tǒng)KNN算法在面對(duì)海量的文本數(shù)據(jù)時(shí)，計(jì)算開銷大、特征維度高、分類效率低等問題，提出一種基于三支決策的KNN漸進(jìn)式文本分類算法。該算法通過對(duì)標(biāo)題、摘要和關(guān)鍵詞等進(jìn)行漸進(jìn)性分析，并結(jié)合了三支決策的思想，從多粒度的角度上來達(dá)到降低特征維度的效果，使得改進(jìn)后的算法在面對(duì)海量文本數(shù)據(jù)時(shí)，分類效率并不會(huì)像傳統(tǒng)KNN算法一樣顯著降低。下一步，本文將著重考慮在已有分類器的基礎(chǔ)上，再次改進(jìn)算法的準(zhǔn)確性和魯棒性。

參考文獻(xiàn)：

［1］Wang Tao，Cai Yi，Leung H F，et al. On entropy-based term weighting schemes for text categorization ［J］. Knowledge and Information Systems，2021，63（9）： 2313－2346.

［2］Zhang Xinyi，Xu Jiahao，Soh C，et al. LA－HCN： label-based attention for hierarchical multi-label text classification neural network［J］. Expert Systems with Applications，2022，187： 115922.

［3］Watanabe W M，F(xiàn)elizardo K R，Jr A C，et al. Reducing efforts of software engineering systematic literature reviews updates using text classification［J］. Information and Software Technology，2020，128： 106395.

［4］Chen Wang，Andi W，Xu Jian，et al. Outsourced privacy-preserving decision tree classification service over encrypted data［J］. Journal of Information Security and Applications，2020，53： 102517.

［5］Xiao Qingtao，Zhong Xin，Zhong Chenghua. Application research of KNN algorithm based on clustering in big data talent demand information classification［J］. International Journal of Pattern Recognition and Artificial Intelligence，2020，34（6）： 2050015.

［6］楊帥華，張清華. 粗糙集近似集的KNN文本分類算法研究［J］. 小型微型計(jì)算機(jī)系統(tǒng)，2017，38（10）： 2192－2196. （Yang Shuai-hua，Zhang Qinghua. Research on K-nearest neighbor text classification algorithm of approximation set of rough set［J］. Journal of Chinese Computer Systems，2017，38（10）： 2192－2196.）

［7］齊斌，鄒紅霞，王宇. 基于加權(quán)局部線性KNN的文本分類算法［J］. 計(jì)算機(jī)應(yīng)用研究，2020，37（8）： 2381－2385. （Qi Bin，Zou Hongxia，Wang Yu. Text categorization algorithm based on weighted locally linear KNN［J］. Application Research of Computers，2020，37（8）： 2381－2385.）

［8］李榮陸，胡運(yùn)發(fā). 基于密度的KNN文本分類器訓(xùn)練樣本裁剪方法［J］. 計(jì)算機(jī)研究與發(fā)展，2004，41（4）： 539－545. （Li Ronglu，Hu Yunfa. A density-based method for reducing the amount of training data in KNN text classification［J］. Journal of Computer Research and Development，2004，41（4）： 539－545.）

［9］張振豪，過弋，韓美琪，等. 基于關(guān)鍵詞相似度的短文本分類方法研究［J］. 計(jì)算機(jī)應(yīng)用研究. 2020，37（1）： 26－29. （Zhang Zhenhao，Guo Yi，Han Meiqi，et al. Research on short text classification based on keyword similarity［J］. Application Research of Compu-ters，2020，37（1）： 26－29.）

［10］周慶平，譚長(zhǎng)庚，王宏君，等. 基于聚類改進(jìn)的KNN文本分類算法［J］. 計(jì)算機(jī)應(yīng)用研究，2016，33（11）： 3374－3377. （Zhou Qingping，Tan Changgeng，Wang Hongjun. et al. Improved KNN text classification algorithm based on clustering［J］. Application Research of Computers，2016，33（11）： 3374－3377.）

［11］Yao Yiyu. Three-way decisions and cognitive computing［J］. Cognitive Computation，2016，8： 543－554.

［12］Yao Yiyu. Three-way granular computing，rough sets，and formal concept analysis［J］. International Journal of Approximate Reaso-ning，2020，116： 106－125.

［13］Yao Yiyu. Tri-level thinking： models of three-way decision［J］. International Journal of Machine Learning and Cybernetics，2020，11（5）： 947－959.

［14］郭豆豆，姜春茂. 基于M-3WD的多階段區(qū)域轉(zhuǎn)換策略研究［J］. 計(jì)算機(jī)科學(xué)，2019，46（10）： 279－285. （Guo Doudou，Jiang Chunmao. Multi-stage regional transformation strategy in move-based three-way decisions model［J］. Computer Science，2019，46（10）： 279－285.）

［15］郭豆豆，姜春茂，楊翎. 一種面向移動(dòng)三支決策模型的有效性度量方法研究［J］. 小型微型計(jì)算機(jī)系統(tǒng)，2021，42（12）： 2511－2518. （Guo Doudou，Jiang Chunmao，Yang Ling. An effectiveness measure approach for movement-based three-way decision model［J］. Journal of Chinese Computer Systems，2021，42（12）： 2511－2518.）

［16］Yao Yiyu，Wong S K M，Lingras P. A decision-theoretic rough set model［C］// Proc of the 5th International Symposium on Methodologies for Intelligent System. 1990： 17－24.

［17］肖琳，陳博理，黃鑫，等. 基于標(biāo)簽語義注意力的多標(biāo)簽文本分類［J］. 軟件學(xué)報(bào)，2020，31（4）： 1079－1089. （Xiao Lin，Chen Boli，Huang Xin，et al. Multi-label text classification method based on label semantic information［J］. Journal of Software，2020，31（4）： 1079－1089.）

［18］Zhang Yan，Yao Jingtao. Game theoretic approach to shadowed sets： a three-way tradeoff perspective［J］. Information Sciences，2020，507： 540－552.

［19］Pedrycz W. Shadowed sets： representing and processing fuzzy sets［J］. IEEE Trans on Systems，Man，and Cybernetics，Part B （Cybernetics），1998，28（1）： 103－109.

［20］Deng Xiaofei，Yao Yiyu. Mean-value-based decision-theoretic sha-dowed sets［C］// Proc of the 6th Joint IFSA World Congress and NAFIPS Annual Meeting. 2013： 1382－1387.

［21］孫可，龔永紅，鄧振云. 一種高效的K值自適應(yīng)的SA-KNN算法［J］. 計(jì)算機(jī)工程與科學(xué)，2015，37（10）： 1965－1970. （Sun Ke，Gong Yonghong，Deng Zhenyun. An efficient SA-KNN algorithm with adaptive K value［J］. Computer Engineering amp; Science，2015，37（10）： 1965－1970.）