多代表點的加權近鄰分類算法①

林高思源

(福建師范大學 計算機與網絡空間安全學院, 福州 350117)

KNN算法是一種基本的分類方法, 在文本分類、人臉識別[1]、遙感圖象識別等各個領域都有著廣泛的應用, 特別是當大規模數據集各類別分布區域重疊較多時, 較其他算法有更優良的表現.如戚玉嬌等[2]使用KNN算法對大興安嶺地區森林地上碳儲量進行遙感估算； 宋飛揚等[3]提出一種空氣質量預測模型, 通過結合KNN算法和LSTM模型, 有效提高模型的預測精度； 薛衛等[4]使用AdaBoost算法對KNN算法分類器進行集成, 用于蛋白質的亞細胞定位預測問題.

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

根據以上研究現狀, 本文提出一種基于多代表點的變精度粗糙集加權KNN算法, 并且使用該算法在文本分類領域進行應用. 本算法在VRSW-KNN算法的基礎之上, 借鑒該算法的分類過程, 引入多代表點思想生成一系列代表點集合并使用聚類算法構建更加精確的分類模型, 使用結構化風險最小化理論進行理論層面的分析和進一步優化算法, 最終得出一個數目適宜的模型簇集合用于分類. 與VRSW-KNN算法相比, 本文算法不僅能更精確的劃分各類別的分布區域, 更好的適應各種情況的數據集, 且能大幅降低分類的時間開銷.

本文的組織結構如下: 第1節介紹本文的背景知識與相關工作； 第2節描述本文提出的算法, 并對部分影響因素進行理論層面分析； 第3節給出實驗環境, 并對實驗結果進行分析； 第4節總結全文, 同時給出未來可能的研究方向.

1 背景知識與相關工作

1.1 基于變精度粗糙集的加權KNN文本分類算法(VRSW-KNN)

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

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

樣本權重計算公式[11]:

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

相似度計算公式[11]:

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

VRSW-KNN決策規則為[11]:

VRSW-KNN算法利用變精度粗糙集的上下近似區域來使每個類別都有一個以類別質心作為中心點的近似區域, 以此檢測測試樣本和各類別分布區域的相對位置. 同時結合文本數量加權的思想, 從而能夠在文本分類問題上比普通的KNN算法表現更好. 其計算類Xi的上下近似半徑的算法步驟如下[11,13]:

Begin

Step 1. 計算第i類的質心O(Xi).

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

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

End

算法中Num(n)表 示前n個樣本中不屬于類別Xi的樣本數目.

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

Begin

Step 1. 數據預處理, 將文本數據轉變為向量空間內的向量di={Wi1,Wi2,···,Win}T.

Step 2. 得出各類別近似半徑.

Step 3. 根據式(2)得出測試樣本與各類別的相似度, 確定測試樣本在數據集整體中的相對位置.

Step 4. 分類階段應首先得出該樣本是否屬于某類別的下近似半徑范圍內, 如成立則為該樣本添加這一類別的類別標記, 且算法終止.

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

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

End

2 多代表點的VRSW-KNN算法

多代表點的VRSW-KNN算法, 全稱MVRSWKNN, 簡稱M-KNN, 該算法利用多代表點思想來讓每個類別的代表區域變得更加細致, 從而通過增強分類模型的判斷能力, 來解決VRSW-KNN算法在部分情況下表現失常的問題. 本節將先介紹模型簇的形式定義和總體分類模型, 根據結構風險理論[8]來確定算法的優化目標, 再給出算法的總體過程并對此進行分析.

2.1 分類模型

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

模型簇pij的 代表點是該模型簇范圍內所有點的中心, 因此亦可稱為中心點, 采用式(4)計算:

分類算法步驟如下:

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

輸出: 樣本數據xα的類別yα.

Begin

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

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

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

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

End

2.2 結構風險

應用分類算法來對未分類樣本進行分類可看作一個k-分類模型[7]的變型, 即:

和基于該分類模型的二類分類判斷, 即:

其中,xα為待分類樣本.

為提高模型的性能, 基于該文獻所提到的k-分類模型來對本節的分類模型基于VC維理論[8]進行結構風險的分析, 可得應用本節算法的分類模型來進行分類亦是一個二類分類過程, 而二類分類模型期望風險的上界[8], 期望風險R(Mk)可表示為:

其中,hk表示Mk的VC維；VC_confidence(hk)表示VC置信度；Remp(Mk)表示經驗風險, 為分類模型使用訓練集時的平均誤差. 而在本節算法中,Mk的經驗風險為:

由此可得, 分類的性能與VC置信度和經驗風險都密切相關. 其中VC置信度隨|Mk|即模型簇數目的增加而出現單調遞增的狀態. 這點可由研究學習矢量量化(Learning Vector Quantization, LVQ)算法的VC維的文獻[14]證明. 根據其定理1的結論可得LVQ的VC維是其“原型”數目的一個單調遞增函數, 而本文算法所定義的模型簇可在文獻[7]的基礎上亦可看作一種LVQ“原型”的擴展. 因此根據VC置信度的定義[8],VC置信度是VC維的遞增函數, 可得本文分類模型的VC置信度亦隨|Mk|的增加而單調遞增.

經驗風險亦與|Mk|有關, 這點可從極端情況上觀察得出, 當 |Mk|與類別數目相等時, 一個類別僅有一個簇,這種情況下, 多代表點思想就失去作用, 變為VRSWKNN算法, 經驗風險在該情況下具有最大值； 而當|Mk|與樣本點的數目相等的時候, 每個樣本點都構成一個模型簇, 這種情況下, 經驗風險降低到0. 結合這兩種極端情況, 可以得出結論, 經驗風險總體上隨著模型簇數目的增加而呈減少趨勢. 但并不表明減少的過程是單調遞減, 這點從文獻[7]中可以得到證明.

綜上可得,R(Mk)的上限由VC置信度和經驗風險共同決定, 而這兩個因素又都與|Mk|值有關, 因此模型訓練算法的目的便是得出一個適合的 |Mk|值來盡量使得分類模型的期望風險達到較低值.

模型訓練算法:

輸入: 訓練集Tr, 參數β, 分類模型類別標號k(k=1,2,···,K).

輸出: 分類模型Mk.

Begin

Step 1. 構造初始分類模型Mk={pk1}, 設X0={Tr中類別標號為k的樣本}, 根據類別標號為k的樣本計算出初始模型簇的上下近似區域和中心點, 從而得出pk1的各個值.

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

Step 3. 如果Remp(Mk)=0 或者|Mk|等于數據點的個數, 返回Mk, 算法終止.

Step 4. 使用K-means聚類算法[15]對Xl中的樣本進行聚類, 劃分成|Mk|+1個 集合X1,X2,···,X|Mk|+1.

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

Step 6. 使用式(6)計算Mk′的 經驗風險Remp(Mk′).如果Remp(Mk′)≥Remp(Mk), 返回Mk, 算法結束. 否則,Mk=Mk′, 重復Step 3至Step 5.

End

對于每個類別, 訓練算法的過程是從1開始, 逐個遞增模型簇數目, 直到經驗風險Remp(Mk)達到一個局部極小值或為0后, 停止遞增并記錄目前的該類別模型簇狀況. 根據文獻[7]提供的策略, 這里的局部極小值指的是第一個經驗風險極小值, 這樣可以在降低訓練階段耗時的同時, 使VC置信度和經驗風險達到一種平衡. 本節算法亦沿用該策略. 最終, 對于每個類別,都有一至多個模型簇表示該類別的分布情況, 從而比VRSW-KNN算法更擅于對樣本進行精準分類.

3 實驗與分析

實驗選擇KNN、VRSW-KNN, 這兩種基于最近鄰思想的分類器作為比對的對象. 實驗設備為: CPU為CORE i7-8750H2.20 GHz, 16 GB RAM, Windows 10操作系統的計算機.

3.1 實驗數據

實驗數據使用復旦大學原計算機信息與技術系國際數據庫中心自然語言處理小組的中文語料庫[11]中的2400篇作為數據集, 包括藝術, 歷史, 計算機, 環境,體育, 農業等共8個類別.

其中的1600篇作為訓練樣本, 800篇作為測試樣本. 在正式實驗前, 對數據集進行分詞, 去停用詞, 特征提取后再使用TF-IDF特征詞加權方式將所有文本變為特征向量.

3.2 實驗結果與分析

實驗的分類性能評價指標采用Micro-F1指標來衡量分類器的分類精度, 同時對3種算法所使用的訓練集和測試集均一致, 且實驗結果為多次運行后的平均值, 以避免隨機因素導致的影響.

本實驗中表1為固定t=1.0,k=10, 粗糙集精度β的取值分別為0.05、0.10、0.15時3種算法的F1值, 由于參數t與耗時無關, 因此表2為僅β取不同值時3種算法的耗時對比.

表1 β取不同值時3種算法的Micro-F1值對比

表2 β取不同值時3種算法的耗時對比

由表1可知, 當粗糙集精度β從0.05逐漸增加到0.15時, 對于VRSW-KNN算法, 模型簇的下近似區域覆蓋范圍逐漸變大, 導致在分類時模型簇的F1值逐漸降低. 但對于M-KNN算法, 雖下近似區域覆蓋范圍發生相同變化, 但由于在訓練模型時, 每個類別分布區域由多個模型簇組成, 導致雖粗糙集精度β發生較大變化, 但對各類別的覆蓋區域影響較小, 不會導致F1值的大幅降低. 因此可知使用多代表點思想后, 生成的模型簇的表現與VRSW-KNN算法相比不僅準確率略有上升, 且在參數的選取上更加容易接近較優良的結果.

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

綜上所述, 本文算法能更加有效的提升分類的效率和準確率.

4 結束語

本文提出一種較高效的基于多代表點思想的變精度粗糙集加權KNN算法, 并使用該算法在文本分類領域中進行實驗. 實驗結果不僅成功驗證期望風險的理論分析的正確性, 更表明該算法的實際可行性, 進一步解決VRSW-KNN算法在刻畫各個類別分布情況的不足, 從而在大幅降低時間開銷的同時提高分類的準確率. 下一步的工作重點是圍繞訓練模型的各個影響因素, 探索在保證分類準確率且能降低訓練期間時間開銷的相關方法.