林高思源

(福建師范大學(xué) 計(jì)算機(jī)與網(wǎng)絡(luò)空間安全學(xué)院, 福州 350117)

KNN算法是一種基本的分類(lèi)方法, 在文本分類(lèi)、人臉識(shí)別[1]、遙感圖象識(shí)別等各個(gè)領(lǐng)域都有著廣泛的應(yīng)用, 特別是當(dāng)大規(guī)模數(shù)據(jù)集各類(lèi)別分布區(qū)域重疊較多時(shí), 較其他算法有更優(yōu)良的表現(xiàn).如戚玉嬌等[2]使用KNN算法對(duì)大興安嶺地區(qū)森林地上碳儲(chǔ)量進(jìn)行遙感估算； 宋飛揚(yáng)等[3]提出一種空氣質(zhì)量預(yù)測(cè)模型, 通過(guò)結(jié)合KNN算法和LSTM模型, 有效提高模型的預(yù)測(cè)精度； 薛衛(wèi)等[4]使用AdaBoost算法對(duì)KNN算法分類(lèi)器進(jìn)行集成, 用于蛋白質(zhì)的亞細(xì)胞定位預(yù)測(cè)問(wèn)題.

雖然KNN算法簡(jiǎn)便易懂, 但亦存在一些缺點(diǎn).為克服這些缺點(diǎn), 目前已經(jīng)有很多學(xué)者提出改進(jìn)的方法,如Guo等提出的KNN Model算法[5,6], 使用代表點(diǎn)集合來(lái)建立分類(lèi)模型, 且能自動(dòng)確定近鄰數(shù)k的取值； 陳黎飛等[7]提出一種多代表點(diǎn)的學(xué)習(xí)算法MEC, 該算法基于結(jié)構(gòu)化風(fēng)險(xiǎn)最小化理論[8]來(lái)進(jìn)行理論分析, 且使用聚類(lèi)算法生成代表點(diǎn)集合, 以此構(gòu)建分類(lèi)模型. 劉繼宇[9]等提出一種基于普通粗糙集的加權(quán)KNN算法, 對(duì)現(xiàn)有的粗糙集值約簡(jiǎn)算法可能存在的問(wèn)題進(jìn)行改進(jìn).王邦軍等[10]提出基于多協(xié)方差和李群結(jié)構(gòu)的李-KNN分類(lèi)算法, 該算法利用集成的思想, 充分利用各種統(tǒng)計(jì)特征的影響, 結(jié)合KNN算法和李群結(jié)構(gòu)的優(yōu)勢(shì). 劉發(fā)升等[11]提出一種基于變精度粗糙集的加權(quán)KNN文本分類(lèi)算法(VRSW-KNN算法), 通過(guò)引入變精度粗糙集結(jié)合樣本加權(quán)的方法來(lái)更有效的控制類(lèi)別的分布區(qū)域, 從而有效提高分類(lèi)的準(zhǔn)確率, 然而比較依賴(lài)參數(shù)的取值.

根據(jù)以上研究現(xiàn)狀, 本文提出一種基于多代表點(diǎn)的變精度粗糙集加權(quán)KNN算法, 并且使用該算法在文本分類(lèi)領(lǐng)域進(jìn)行應(yīng)用. 本算法在VRSW-KNN算法的基礎(chǔ)之上, 借鑒該算法的分類(lèi)過(guò)程, 引入多代表點(diǎn)思想生成一系列代表點(diǎn)集合并使用聚類(lèi)算法構(gòu)建更加精確的分類(lèi)模型, 使用結(jié)構(gòu)化風(fēng)險(xiǎn)最小化理論進(jìn)行理論層面的分析和進(jìn)一步優(yōu)化算法, 最終得出一個(gè)數(shù)目適宜的模型簇集合用于分類(lèi). 與VRSW-KNN算法相比, 本文算法不僅能更精確的劃分各類(lèi)別的分布區(qū)域, 更好的適應(yīng)各種情況的數(shù)據(jù)集, 且能大幅降低分類(lèi)的時(shí)間開(kāi)銷(xiāo).

本文的組織結(jié)構(gòu)如下: 第1節(jié)介紹本文的背景知識(shí)與相關(guān)工作； 第2節(jié)描述本文提出的算法, 并對(duì)部分影響因素進(jìn)行理論層面分析； 第3節(jié)給出實(shí)驗(yàn)環(huán)境, 并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析； 第4節(jié)總結(jié)全文, 同時(shí)給出未來(lái)可能的研究方向.

1 背景知識(shí)與相關(guān)工作

1.1 基于變精度粗糙集的加權(quán)KNN文本分類(lèi)算法(VRSW-KNN)

Ziarko[12]于1993年利用相對(duì)錯(cuò)誤分類(lèi)率提出一種變精度粗糙集模型, 該模型利用精度β把原來(lái)經(jīng)典粗糙集的上、下近似區(qū)域推廣到任意精度水平, β∈[0,0.5), 使粗糙集的區(qū)域變得更加靈活.

由于數(shù)據(jù)集的類(lèi)別分布并不一定均衡, 這導(dǎo)致普通KNN算法在判斷類(lèi)別時(shí)會(huì)更容易把訓(xùn)練集中占比較多的類(lèi)別給予測(cè)試樣本, 使分類(lèi)精確度降低. 為更好的解決該問(wèn)題, 該算法根據(jù)測(cè)試樣本的K近鄰樣本分布特征使用式(1)對(duì)K個(gè)樣本分別計(jì)算權(quán)重, 再使用式(2)計(jì)算測(cè)試樣本向量與K個(gè)訓(xùn)練樣本向量的相似度, 最后使用式(3)計(jì)算各類(lèi)別最終權(quán)重, 并將該向量分配給最終權(quán)重最大的類(lèi)別[11].

樣本權(quán)重計(jì)算公式[11]:

式中,Num(Ci)為 K近鄰中屬于Ci的 文本數(shù)量；Avgnum(Cl)是指K近鄰中類(lèi)別的平均文本數(shù).

相似度計(jì)算公式[11]:

其中, 特征向量dj={Wi1,Wi2,···,Win}T, 而Win代表文件dj的第n維.

VRSW-KNN決策規(guī)則為[11]:

VRSW-KNN算法利用變精度粗糙集的上下近似區(qū)域來(lái)使每個(gè)類(lèi)別都有一個(gè)以類(lèi)別質(zhì)心作為中心點(diǎn)的近似區(qū)域, 以此檢測(cè)測(cè)試樣本和各類(lèi)別分布區(qū)域的相對(duì)位置. 同時(shí)結(jié)合文本數(shù)量加權(quán)的思想, 從而能夠在文本分類(lèi)問(wèn)題上比普通的KNN算法表現(xiàn)更好. 其計(jì)算類(lèi)Xi的上下近似半徑的算法步驟如下[11,13]:

Begin

Step 1. 計(jì)算第i類(lèi)的質(zhì)心O(Xi).

Step 2. 計(jì)算類(lèi)別中心O(Xi)與同類(lèi)別樣本的相似度, 則第i類(lèi)別的上近似半徑為相似度的最低值.

Step 3. 計(jì)算類(lèi)別中心O(Xi)與訓(xùn)練集中全部樣本的相似度, 如果樣本相似度超過(guò)上近似半徑, 則將其按照降序進(jìn)入隊(duì)列中.

End

算法中Num(n)表 示前n個(gè)樣本中不屬于類(lèi)別Xi的樣本數(shù)目.

VRSW-KNN算法總體步驟如下[11,13]:

Begin

Step 1. 數(shù)據(jù)預(yù)處理, 將文本數(shù)據(jù)轉(zhuǎn)變?yōu)橄蛄靠臻g內(nèi)的向量di={Wi1,Wi2,···,Win}T.

Step 2. 得出各類(lèi)別近似半徑.

Step 3. 根據(jù)式(2)得出測(cè)試樣本與各類(lèi)別的相似度, 確定測(cè)試樣本在數(shù)據(jù)集整體中的相對(duì)位置.

Step 4. 分類(lèi)階段應(yīng)首先得出該樣本是否屬于某類(lèi)別的下近似半徑范圍內(nèi), 如成立則為該樣本添加這一類(lèi)別的類(lèi)別標(biāo)記, 且算法終止.

Step 5. 如測(cè)試樣本與一些類(lèi)別中心的相似度大于類(lèi)別的上近似半徑, 則在這些類(lèi)別中先使用式(1)計(jì)算各類(lèi)別的權(quán)重, 再使用式(3)進(jìn)行最終決策.

Step 6. 如測(cè)試樣本與所有類(lèi)別中心的相似度都小于類(lèi)別的上近似半徑, 則在完整訓(xùn)練集中先使用式(1)計(jì)算各類(lèi)別的權(quán)重, 再使用式(3)來(lái)進(jìn)行最終決策.

End

2 多代表點(diǎn)的VRSW-KNN算法

多代表點(diǎn)的VRSW-KNN算法, 全稱(chēng)MVRSWKNN, 簡(jiǎn)稱(chēng)M-KNN, 該算法利用多代表點(diǎn)思想來(lái)讓每個(gè)類(lèi)別的代表區(qū)域變得更加細(xì)致, 從而通過(guò)增強(qiáng)分類(lèi)模型的判斷能力, 來(lái)解決VRSW-KNN算法在部分情況下表現(xiàn)失常的問(wèn)題. 本節(jié)將先介紹模型簇的形式定義和總體分類(lèi)模型, 根據(jù)結(jié)構(gòu)風(fēng)險(xiǎn)理論[8]來(lái)確定算法的優(yōu)化目標(biāo), 再給出算法的總體過(guò)程并對(duì)此進(jìn)行分析.

2.1 分類(lèi)模型

M-KNN算法構(gòu)建分類(lèi)模型是為能從給定數(shù)據(jù)集Tr={(x1,y1),(x2,y2),···,(xn,yn)} 中 得到被優(yōu)化過(guò)的k個(gè)類(lèi)別的模型簇集合 {C1,C2,···,Ck}, 其中的Ci指的是第i類(lèi)的模型簇集合, 可看作Ci={pi1,pi2,···,pim}, 其中的pij是經(jīng)過(guò)優(yōu)化過(guò)的第i類(lèi)模型簇集合的第j個(gè)模型簇,m為第i類(lèi)的模型簇總數(shù), 同時(shí)可把模型簇pij覆蓋區(qū)域內(nèi)的樣本點(diǎn)集合稱(chēng)為Xij.

模型簇pij的 代表點(diǎn)是該模型簇范圍內(nèi)所有點(diǎn)的中心, 因此亦可稱(chēng)為中心點(diǎn), 采用式(4)計(jì)算:

分類(lèi)算法步驟如下:

輸入: 模型簇集合 {C1,C2,···,Ck}, 待分類(lèi)樣本xα,參數(shù)t, 近鄰數(shù)k.

輸出: 樣本數(shù)據(jù)xα的類(lèi)別yα.

Begin

Step 1. 根據(jù)式(2)計(jì)算xα與各模型簇的中心點(diǎn)之間的相似度, 從而確定xα的位置.

Step 2. 首先判斷xα是否屬于某個(gè)模型簇的下近似區(qū)域, 如果屬于, 則直接將xα歸于該模型簇所屬的類(lèi)別,算法終止.

Step 3. 如樣本屬于某些模型簇的上近似區(qū)域, 則在這些模型簇的覆蓋區(qū)域中選出與xα相似度最大的k個(gè)樣本后使用式(3)得出xα的類(lèi)別.

Step 4. 如果樣本不屬于所有類(lèi)別的上近似區(qū)域,則在所有模型簇的覆蓋區(qū)域中選出與xα相似度最大的k個(gè)樣本后使用式(3)得出xα的類(lèi)別.

End

2.2 結(jié)構(gòu)風(fēng)險(xiǎn)

應(yīng)用分類(lèi)算法來(lái)對(duì)未分類(lèi)樣本進(jìn)行分類(lèi)可看作一個(gè)k-分類(lèi)模型[7]的變型, 即:

和基于該分類(lèi)模型的二類(lèi)分類(lèi)判斷, 即:

其中,xα為待分類(lèi)樣本.

為提高模型的性能, 基于該文獻(xiàn)所提到的k-分類(lèi)模型來(lái)對(duì)本節(jié)的分類(lèi)模型基于VC維理論[8]進(jìn)行結(jié)構(gòu)風(fēng)險(xiǎn)的分析, 可得應(yīng)用本節(jié)算法的分類(lèi)模型來(lái)進(jìn)行分類(lèi)亦是一個(gè)二類(lèi)分類(lèi)過(guò)程, 而二類(lèi)分類(lèi)模型期望風(fēng)險(xiǎn)的上界[8], 期望風(fēng)險(xiǎn)R(Mk)可表示為:

其中,hk表示Mk的VC維；VC_confidence(hk)表示VC置信度；Remp(Mk)表示經(jīng)驗(yàn)風(fēng)險(xiǎn), 為分類(lèi)模型使用訓(xùn)練集時(shí)的平均誤差. 而在本節(jié)算法中,Mk的經(jīng)驗(yàn)風(fēng)險(xiǎn)為:

由此可得, 分類(lèi)的性能與VC置信度和經(jīng)驗(yàn)風(fēng)險(xiǎn)都密切相關(guān). 其中VC置信度隨|Mk|即模型簇?cái)?shù)目的增加而出現(xiàn)單調(diào)遞增的狀態(tài). 這點(diǎn)可由研究學(xué)習(xí)矢量量化(Learning Vector Quantization, LVQ)算法的VC維的文獻(xiàn)[14]證明. 根據(jù)其定理1的結(jié)論可得LVQ的VC維是其“原型”數(shù)目的一個(gè)單調(diào)遞增函數(shù), 而本文算法所定義的模型簇可在文獻(xiàn)[7]的基礎(chǔ)上亦可看作一種LVQ“原型”的擴(kuò)展. 因此根據(jù)VC置信度的定義[8],VC置信度是VC維的遞增函數(shù), 可得本文分類(lèi)模型的VC置信度亦隨|Mk|的增加而單調(diào)遞增.

經(jīng)驗(yàn)風(fēng)險(xiǎn)亦與|Mk|有關(guān), 這點(diǎn)可從極端情況上觀(guān)察得出, 當(dāng) |Mk|與類(lèi)別數(shù)目相等時(shí), 一個(gè)類(lèi)別僅有一個(gè)簇,這種情況下, 多代表點(diǎn)思想就失去作用, 變?yōu)閂RSWKNN算法, 經(jīng)驗(yàn)風(fēng)險(xiǎn)在該情況下具有最大值； 而當(dāng)|Mk|與樣本點(diǎn)的數(shù)目相等的時(shí)候, 每個(gè)樣本點(diǎn)都構(gòu)成一個(gè)模型簇, 這種情況下, 經(jīng)驗(yàn)風(fēng)險(xiǎn)降低到0. 結(jié)合這兩種極端情況, 可以得出結(jié)論, 經(jīng)驗(yàn)風(fēng)險(xiǎn)總體上隨著模型簇?cái)?shù)目的增加而呈減少趨勢(shì). 但并不表明減少的過(guò)程是單調(diào)遞減, 這點(diǎn)從文獻(xiàn)[7]中可以得到證明.

綜上可得,R(Mk)的上限由VC置信度和經(jīng)驗(yàn)風(fēng)險(xiǎn)共同決定, 而這兩個(gè)因素又都與|Mk|值有關(guān), 因此模型訓(xùn)練算法的目的便是得出一個(gè)適合的 |Mk|值來(lái)盡量使得分類(lèi)模型的期望風(fēng)險(xiǎn)達(dá)到較低值.

模型訓(xùn)練算法:

輸入: 訓(xùn)練集Tr, 參數(shù)β, 分類(lèi)模型類(lèi)別標(biāo)號(hào)k(k=1,2,···,K).

輸出: 分類(lèi)模型Mk.

Begin

Step 1. 構(gòu)造初始分類(lèi)模型Mk={pk1}, 設(shè)X0={Tr中類(lèi)別標(biāo)號(hào)為k的樣本}, 根據(jù)類(lèi)別標(biāo)號(hào)為k的樣本計(jì)算出初始模型簇的上下近似區(qū)域和中心點(diǎn), 從而得出pk1的各個(gè)值.

Step 2. 計(jì)算初始模型的Remp(Mk).

Step 3. 如果Remp(Mk)=0 或者|Mk|等于數(shù)據(jù)點(diǎn)的個(gè)數(shù), 返回Mk, 算法終止.

Step 4. 使用K-means聚類(lèi)算法[15]對(duì)Xl中的樣本進(jìn)行聚類(lèi), 劃分成|Mk|+1個(gè) 集合X1,X2,···,X|Mk|+1.

Step 5. 構(gòu)造新分類(lèi)模型Mk′={pki|i=1,2,···,|Mk|+1}并 構(gòu)造其中的新模型簇

Step 6. 使用式(6)計(jì)算Mk′的 經(jīng)驗(yàn)風(fēng)險(xiǎn)Remp(Mk′).如果Remp(Mk′)≥Remp(Mk), 返回Mk, 算法結(jié)束. 否則,Mk=Mk′, 重復(fù)Step 3至Step 5.

End

對(duì)于每個(gè)類(lèi)別, 訓(xùn)練算法的過(guò)程是從1開(kāi)始, 逐個(gè)遞增模型簇?cái)?shù)目, 直到經(jīng)驗(yàn)風(fēng)險(xiǎn)Remp(Mk)達(dá)到一個(gè)局部極小值或?yàn)?后, 停止遞增并記錄目前的該類(lèi)別模型簇狀況. 根據(jù)文獻(xiàn)[7]提供的策略, 這里的局部極小值指的是第一個(gè)經(jīng)驗(yàn)風(fēng)險(xiǎn)極小值, 這樣可以在降低訓(xùn)練階段耗時(shí)的同時(shí), 使VC置信度和經(jīng)驗(yàn)風(fēng)險(xiǎn)達(dá)到一種平衡. 本節(jié)算法亦沿用該策略. 最終, 對(duì)于每個(gè)類(lèi)別,都有一至多個(gè)模型簇表示該類(lèi)別的分布情況, 從而比VRSW-KNN算法更擅于對(duì)樣本進(jìn)行精準(zhǔn)分類(lèi).

3 實(shí)驗(yàn)與分析

實(shí)驗(yàn)選擇KNN、VRSW-KNN, 這兩種基于最近鄰思想的分類(lèi)器作為比對(duì)的對(duì)象. 實(shí)驗(yàn)設(shè)備為: CPU為CORE i7-8750H2.20 GHz, 16 GB RAM, Windows 10操作系統(tǒng)的計(jì)算機(jī).

3.1 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)數(shù)據(jù)使用復(fù)旦大學(xué)原計(jì)算機(jī)信息與技術(shù)系國(guó)際數(shù)據(jù)庫(kù)中心自然語(yǔ)言處理小組的中文語(yǔ)料庫(kù)[11]中的2400篇作為數(shù)據(jù)集, 包括藝術(shù), 歷史, 計(jì)算機(jī), 環(huán)境,體育, 農(nóng)業(yè)等共8個(gè)類(lèi)別.

其中的1600篇作為訓(xùn)練樣本, 800篇作為測(cè)試樣本. 在正式實(shí)驗(yàn)前, 對(duì)數(shù)據(jù)集進(jìn)行分詞, 去停用詞, 特征提取后再使用TF-IDF特征詞加權(quán)方式將所有文本變?yōu)樘卣飨蛄?

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

實(shí)驗(yàn)的分類(lèi)性能評(píng)價(jià)指標(biāo)采用Micro-F1指標(biāo)來(lái)衡量分類(lèi)器的分類(lèi)精度, 同時(shí)對(duì)3種算法所使用的訓(xùn)練集和測(cè)試集均一致, 且實(shí)驗(yàn)結(jié)果為多次運(yùn)行后的平均值, 以避免隨機(jī)因素導(dǎo)致的影響.

本實(shí)驗(yàn)中表1為固定t=1.0,k=10, 粗糙集精度β的取值分別為0.05、0.10、0.15時(shí)3種算法的F1值, 由于參數(shù)t與耗時(shí)無(wú)關(guān), 因此表2為僅β取不同值時(shí)3種算法的耗時(shí)對(duì)比.

表1 β取不同值時(shí)3種算法的Micro-F1值對(duì)比

表2 β取不同值時(shí)3種算法的耗時(shí)對(duì)比

由表1可知, 當(dāng)粗糙集精度β從0.05逐漸增加到0.15時(shí), 對(duì)于VRSW-KNN算法, 模型簇的下近似區(qū)域覆蓋范圍逐漸變大, 導(dǎo)致在分類(lèi)時(shí)模型簇的F1值逐漸降低. 但對(duì)于M-KNN算法, 雖下近似區(qū)域覆蓋范圍發(fā)生相同變化, 但由于在訓(xùn)練模型時(shí), 每個(gè)類(lèi)別分布區(qū)域由多個(gè)模型簇組成, 導(dǎo)致雖粗糙集精度β發(fā)生較大變化, 但對(duì)各類(lèi)別的覆蓋區(qū)域影響較小, 不會(huì)導(dǎo)致F1值的大幅降低. 因此可知使用多代表點(diǎn)思想后, 生成的模型簇的表現(xiàn)與VRSW-KNN算法相比不僅準(zhǔn)確率略有上升, 且在參數(shù)的選取上更加容易接近較優(yōu)良的結(jié)果.

由表2可知, 普通的KNN算法耗時(shí)最長(zhǎng), M-KNN算法在耗時(shí)上較VRSW-KNN算法大幅縮短. 原因是雖然VRSW-KNN算法使用變精度粗糙集的思想, 然而只簡(jiǎn)單的設(shè)定一個(gè)類(lèi)別只有一個(gè)簇, 導(dǎo)致并沒(méi)有充分的利用該分類(lèi)模型, 其分類(lèi)時(shí)間隨著樣本數(shù)的增加而急劇增長(zhǎng). 很多數(shù)據(jù)點(diǎn)仍需要多個(gè)類(lèi)別甚至全部類(lèi)別的模型簇內(nèi)樣本尋找K近鄰, 但M-KNN算法結(jié)合多代表點(diǎn)的思想, 將每個(gè)類(lèi)別分布區(qū)域劃分成多個(gè)模型簇, 雖然導(dǎo)致訓(xùn)練分類(lèi)模型的時(shí)長(zhǎng)大幅增加, 但在分類(lèi)階段則獲得各類(lèi)別更精確的分布區(qū)域, 讓很多數(shù)據(jù)點(diǎn)能夠在分類(lèi)算法的前兩步就獲得較準(zhǔn)確的標(biāo)記, 從而大幅降低數(shù)據(jù)分類(lèi)的耗時(shí), 導(dǎo)致在本節(jié)算法中, 大部分耗時(shí)是訓(xùn)練分類(lèi)模型的耗時(shí). 因此, 在更大規(guī)模的文本數(shù)據(jù)集中, 本節(jié)算法的分類(lèi)性能會(huì)遠(yuǎn)好于VRSWKNN算法和普通的KNN算法.

綜上所述, 本文算法能更加有效的提升分類(lèi)的效率和準(zhǔn)確率.

4 結(jié)束語(yǔ)

本文提出一種較高效的基于多代表點(diǎn)思想的變精度粗糙集加權(quán)KNN算法, 并使用該算法在文本分類(lèi)領(lǐng)域中進(jìn)行實(shí)驗(yàn). 實(shí)驗(yàn)結(jié)果不僅成功驗(yàn)證期望風(fēng)險(xiǎn)的理論分析的正確性, 更表明該算法的實(shí)際可行性, 進(jìn)一步解決VRSW-KNN算法在刻畫(huà)各個(gè)類(lèi)別分布情況的不足, 從而在大幅降低時(shí)間開(kāi)銷(xiāo)的同時(shí)提高分類(lèi)的準(zhǔn)確率. 下一步的工作重點(diǎn)是圍繞訓(xùn)練模型的各個(gè)影響因素, 探索在保證分類(lèi)準(zhǔn)確率且能降低訓(xùn)練期間時(shí)間開(kāi)銷(xiāo)的相關(guān)方法.