吳敬學(xué)

（順德職業(yè)技術(shù)學(xué)院 設(shè)計(jì)學(xué)院，廣東 佛山 528333）

基于粒子群優(yōu)化的KNN分類算法改進(jìn)研究

吳敬學(xué)

（順德職業(yè)技術(shù)學(xué)院 設(shè)計(jì)學(xué)院，廣東 佛山 528333）

針對(duì)傳統(tǒng)KNN算法尋找近鄰耗時(shí)過多的不足，提出利用粒子群優(yōu)化算法搜索近鄰。粒子初始化為k個(gè)訓(xùn)練樣本的編號(hào)，對(duì)于每一代：個(gè)體最優(yōu)pbest定義為當(dāng)前粒子與上一代pbest搜索到的最近鄰集合，群體最優(yōu)gbest定義為當(dāng)前pbest搜索到的最近鄰集合。并在迭代過程中建立距離表，通過距離表的更新與查詢避免重復(fù)計(jì)算。對(duì)比實(shí)驗(yàn)表明，改進(jìn)算法在分類精度不減甚至略微提高基礎(chǔ)上，耗時(shí)縮短80%以上。

KNN；粒子群優(yōu)化；文本分類

文本分類是可用于數(shù)字圖書館的一項(xiàng)重要技術(shù)。常用的分類方法有：決策樹﹑最大熵﹑k近鄰﹑遺傳算法﹑神經(jīng)網(wǎng)絡(luò)﹑樸素貝葉斯﹑支持向量機(jī)﹑基于投票的方法﹑Rocchio分類等［1］。其中，k近鄰（k nearest neighbor，KNN）算法作為向量空間模型（VSM）下最好的分類算法之一［2］，由Cover和Hart于1967年提出［3］，基本思想是：在VSM表示下，分別計(jì)算待分類樣本與訓(xùn)練樣本的距離或相似度，找出與待分類樣本最相近的k個(gè)近鄰，根據(jù)這k個(gè)近鄰的類別確定待分類樣本歸屬。KNN方法基于類比學(xué)習(xí)，是一種非參數(shù)的分類技術(shù)，在基于統(tǒng)計(jì)的模式識(shí)別中非常有效，對(duì)于未知和非正態(tài)分布可以取得較高的分類準(zhǔn)確率，具有魯棒性﹑概念清晰等諸多優(yōu)點(diǎn)［4］。

但是，作為一種懶惰學(xué)習(xí)方法，KNN算法不具備離線訓(xùn)練階段，所有計(jì)算都在分類過程中完成，同時(shí)，由于需要與訓(xùn)練樣本逐個(gè)比較以確定待分類樣本的近鄰，計(jì)算開銷大，分類效率低，這也限制了其在大數(shù)據(jù)﹑Web分類等方面的應(yīng)用。為了提高KNN算法效率，目前常見方法有減小樣本集規(guī)模和采用快速搜索算法。前者可通過特征降維和訓(xùn)練集剪裁實(shí)現(xiàn)。特征降維，如基于遺傳算法的特征選擇［5］﹑基于向量聚合技術(shù)的特征抽?。?］等，是文本分類的重要預(yù)處理過程，但降維后的向量通常仍具有高維性和稀疏性。訓(xùn)練集剪裁，如Editing方法［7］﹑Condensing方法［8］以及基于密度的剪裁［9］等，能有效降低計(jì)算開銷，但已有研究成果表明，分類準(zhǔn)確率和樣本規(guī)模呈正相關(guān)性［10］，因此這種方法會(huì)損失一定精度。采用快速搜索算法，是另一種常用方法，又分為局部最優(yōu)搜索與全局最優(yōu)搜索。局部最優(yōu)搜索是在訓(xùn)練集中選取或生成一些代表樣本，通過與代表樣本的比較，劃定一個(gè)最有可能包含k個(gè)近鄰的樣本集合，并在此集合內(nèi)進(jìn)行精確搜索，如文獻(xiàn)［11］利用Rocchio方法計(jì)算各類的原型向量，并通過比較得到k0個(gè)候選類別，然后在k0個(gè)類中心區(qū)域進(jìn)行精確搜索，文獻(xiàn)［12］則對(duì)每個(gè)類別內(nèi)的相似樣本聚類生成m個(gè)簇，通過文本串接得到各簇代表向量，并以此代替原始樣本建立分類模型。局部最優(yōu)搜索能夠較大程度降低計(jì)算開銷，但只是在局部范圍內(nèi)進(jìn)行精確匹配，真正的近鄰可能由于代表樣本選取不當(dāng)而錯(cuò)過，因此無(wú)法保證找到精確的k個(gè)近鄰。全局最優(yōu)搜索主要利用三角不等式原理，通過構(gòu)建判別式，排除不可能成為近鄰的訓(xùn)練樣本，如文獻(xiàn)［13］首先在訓(xùn)練樣本中確定一個(gè)基準(zhǔn)點(diǎn)R，然后根據(jù)基準(zhǔn)點(diǎn)R﹑測(cè)試樣本x和訓(xùn)練樣本i三點(diǎn)之間幾何關(guān)系構(gòu)造不等式，判斷是否將樣本i排除，文獻(xiàn)［14］則基于小波變換，利用向量的方差和在小波域中的逼近系數(shù)構(gòu)造不等式，排除不可能成為近鄰的樣本。全局最優(yōu)搜索需要對(duì)全部樣本進(jìn)行考察，將不可能成為近鄰的樣本排除，因此在降低計(jì)算開銷方面較局部方法稍差，但其能夠在全局范圍找出精確的k個(gè)近鄰，保證分類精度不變。本文利用粒子群優(yōu)化算法搜索近鄰，在全局范圍內(nèi)，根據(jù)個(gè)體最優(yōu)和群體最優(yōu)進(jìn)行有指導(dǎo)地搜索，在保持或近似保持分類精度不變的情況下，提高分類速度。

1 粒子群優(yōu)化算法

美國(guó)心理學(xué)家Kennedy和電氣工程師Eberhart根據(jù)鳥類在覓食過程中通過自身經(jīng)驗(yàn)與相互之間的信息共享能夠迅速發(fā)現(xiàn)散落分布的食物這一現(xiàn)象，于1995年提出了粒子群優(yōu)化（particle swarm optimization，PSO）算法［15］。算法的基本思想是：隨機(jī)初始化一群沒有體積沒有質(zhì)量的粒子，將每個(gè)粒子視為目標(biāo)問題的一個(gè)可行解，粒子的好壞根據(jù)具體問題的適應(yīng)度函數(shù)計(jì)算。粒子根據(jù)速度更新位置，而速度則通過個(gè)體最優(yōu)和種群最優(yōu)計(jì)算得到。

粒子群優(yōu)化算法的數(shù)學(xué)表述為：假設(shè)在D維搜索空間中，粒子種群規(guī)模為N，則第i（i=1，2，...，N）個(gè)粒子的位置和速度分別表示為Xi=（xi1，xi2，...，xiD） 和 Vi=（vi1，vi2，...，viD）， 該 粒 子 所經(jīng)歷的最佳位置（pbest）表示為Pi=（pi1，pi2，...，piD），種群中所有粒子所發(fā)現(xiàn)的最佳位置（gbest）記為Pg。對(duì)于第t+1（t≥1）次迭代，粒子i在第d（d=1，2，...，D）維上的速度和位置分別依據(jù)式（1）和式（2）進(jìn)行更新：

其中，w為慣性權(quán)重，其大小決定了粒子對(duì)當(dāng)前速度繼承的多少，選擇一個(gè)合適的w有助于PSO均衡它的探索能力與開發(fā)能力。Shi等指出較大的慣性權(quán)重有利于展開全局尋優(yōu)，而較小的慣性權(quán)重則有利于局部尋優(yōu)，并提出從0.9線性遞減到0.4的慣性權(quán)重策略［16］，采用這種慣性權(quán)重的PSO算法也稱為標(biāo)準(zhǔn)PSO算法。c1和c2稱為學(xué)習(xí)因子，也稱加速常數(shù)，分別用于控制粒子指向自身或鄰域最佳位置的運(yùn)動(dòng)，體現(xiàn)了粒子的自我認(rèn)知和向群體最優(yōu)學(xué)習(xí)的能力，通常取 c1=c2=2［17］。r1和r2為［0，1］范圍內(nèi)的均勻隨機(jī)數(shù)。同時(shí)，粒子速度往往被限制在［-vmax，vmax］內(nèi)，vmax增大，有利于全局搜索；vmax減小，則有利于局部開發(fā)［18］。但是，vmax過大可能使粒子步長(zhǎng)過大從而飛過最優(yōu)解導(dǎo)致難以收斂；vmax過小則可能使粒子步長(zhǎng)太小導(dǎo)致陷入局部搜索空間而無(wú)法進(jìn)行全局搜索［19］。vmax的值通常根據(jù)經(jīng)驗(yàn)確定，并一般設(shè)定為問題空間的10%～20%［18］。

文獻(xiàn)［20］認(rèn)為，標(biāo)準(zhǔn)PSO中的“速度”概念并不是必需的，反而可能造成粒子“發(fā)散”，影響收斂速度與精度，并給出粒子進(jìn)化過程與速度無(wú)關(guān)的證明，提出一種簡(jiǎn)化的粒子群優(yōu)化算法sPSO，粒子位置更新由（3）式?jīng)Q定。

sPSO算法取消標(biāo)準(zhǔn)PSO中粒子速度的概念，避免了人為確定參數(shù)［-vmax，vmax］對(duì)粒子收斂速度和收斂精度的影響。

2 基于sPSO的改進(jìn)KNN算法

KNN算法的一個(gè)重要步驟是搜索待分類樣本的k個(gè)近鄰，龐大計(jì)算開銷也由此而來(lái)。設(shè)訓(xùn)練集為T，任意k個(gè)訓(xùn)練樣本組成的集合為T*，不難證明，若T*是待分類樣本x的最近鄰組合，那么其中各樣本到x的距離之和必然最小，則KNN算法搜索近鄰的過程可視為在T中尋找T*的組合優(yōu)化問題，約束條件為T*中各樣本到x的距離之和最小。因此，可利用PSO算法搜索k個(gè)近鄰。文獻(xiàn)［21］基于標(biāo)準(zhǔn)PSO算法實(shí)現(xiàn)近鄰搜索，但并未給出［-vmax，vmax］參數(shù)設(shè)置。本文采用文獻(xiàn)［20］提出的簡(jiǎn)化粒子群算法sPSO，給出一種改進(jìn)的KNN算法sPSO-KNN，該算法取消速度概念，避免人為確定參數(shù)［-vmax，vmax］對(duì)收斂速度和收斂精度的影響，在保持分類精度不降的條件下提高分類速度。

2.1 粒子編碼

由于本問題的目標(biāo)解為k個(gè)最近鄰組成的集合，則粒子編碼應(yīng)為k個(gè)訓(xùn)練樣本的編號(hào)。處理這類離散型問題，應(yīng)對(duì)標(biāo)準(zhǔn)PSO算法加以修改。Kenney等曾在經(jīng)典PSO基礎(chǔ)上提出用于解決0-1整數(shù)規(guī)劃的二進(jìn)制版本的離散PSO（BPSO）算法［22］，另外也有學(xué)者通過取整函數(shù)直接將連續(xù)PSO用于任務(wù)分配問題［23］。通過實(shí)驗(yàn)得出，BPSO方法計(jì)算量較大，不適合本文應(yīng)用，因此采用十進(jìn)制數(shù)表示訓(xùn)練樣本編號(hào)，并通過“向上取整”函數(shù)取整。另外，在進(jìn)化過程中，若樣本編號(hào)小于1則置為1，若大于訓(xùn)練樣本數(shù)則置為訓(xùn)練樣本數(shù)。

2.2 粒子評(píng)價(jià)與 pbest、gbest更新

通過實(shí)驗(yàn)得出，以距離之和最小作為評(píng)價(jià)粒子的標(biāo)準(zhǔn)，以粒子位置直接更新個(gè)體最優(yōu)pbest和群體最優(yōu)gbest的方法，其效果并不理想。因此，對(duì)粒子評(píng)價(jià)與pbest﹑gbest更新策略進(jìn)行修改。對(duì)于每一次迭代：

1）不再對(duì)粒子進(jìn)行評(píng)價(jià)，只是計(jì)算粒子中各訓(xùn)練樣本到待分類樣本距離。

2）pbest更新操作為：計(jì)算pbest及本代粒子中的各訓(xùn)練樣本到待分類樣本距離，對(duì)結(jié)果按升序排序，將距離最小的前k個(gè)樣本的編號(hào)作為pbest。

3）gbest更新操作為：計(jì)算所有粒子pbest中的訓(xùn)練樣本到待分類樣本距離，對(duì)結(jié)果按升序排序，將距離最小的前k個(gè)樣本的編號(hào)作為gbest。

同時(shí)，對(duì)于每一個(gè)待分類樣本，在內(nèi)存中建立所有訓(xùn)練樣本到其的距離表，每次計(jì)算距離前先進(jìn)行查詢，若該訓(xùn)練樣本已經(jīng)過比較，則直接調(diào)取距離，若未經(jīng)過比較，則計(jì)算距離并更新距離表，以此避免重復(fù)計(jì)算帶來(lái)的多余開銷。

2.3 算法步驟

基于sPSO算法搜索近鄰的步驟如下：

步驟1 初始化。隨機(jī)生成粒子，每個(gè)粒子為k個(gè)訓(xùn)練樣本的編號(hào)，每個(gè)粒子的pbest即為其本身，gbest為所有粒子的訓(xùn)練樣本中，與待分類樣本距離最小的前k個(gè)樣本的編號(hào)。

步驟2 更新粒子。按照式（3）對(duì)粒子狀態(tài)進(jìn)行更新。

步驟3 計(jì)算距離。對(duì)于各個(gè)粒子所代表的訓(xùn)練樣本，查詢距離表，若該樣本尚未經(jīng)過比較，則計(jì)算其到待分類樣本之間距離，并更新距離表。

步驟4 更新pbest﹑gbest。依據(jù)2.2介紹的方法，從距離表中調(diào)取距離并對(duì)pbest﹑gbest進(jìn)行更新。

步驟5 判斷終止。若本代gbest中各訓(xùn)練樣本到待分類樣本距離之和與上一代相等，則終止迭代并輸出最近鄰組合gbest，否則轉(zhuǎn)至步驟2。

3 對(duì)比實(shí)驗(yàn)

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

實(shí)驗(yàn)數(shù)據(jù)采用中科院自動(dòng)化所整理的中文新聞?wù)Z料［24］，該語(yǔ)料集包含8個(gè)類別，其中訓(xùn)練樣本數(shù)為13 025，測(cè)試樣本數(shù)為3 254。本研究所選類別及各類包含的訓(xùn)練樣本﹑測(cè)試樣本數(shù)量如表1。

表1 實(shí)驗(yàn)語(yǔ)料類別及樣本數(shù)量

3.2 實(shí)驗(yàn)設(shè)置

采用IG方法進(jìn)行特征選擇，設(shè)置兩組實(shí)驗(yàn)，特征詞數(shù)分別為500和1 000，對(duì)比算法為sPSO-KNN與傳統(tǒng)KNN，每組實(shí)驗(yàn)分別設(shè)置測(cè)試樣本數(shù)為200﹑500﹑2 166三輪。近鄰數(shù)為15，粒子數(shù)為10，學(xué)習(xí)因子c1=c2=2，慣性權(quán)重w為0.9至0.4遞減，相似性度量采用歐式距離，類別判斷采取多數(shù)法。每種算法執(zhí)行10次，取平均值作為最終實(shí)驗(yàn)結(jié)果。

3.3 結(jié)果與分析

改進(jìn)算法sPSO-KNN與傳統(tǒng)KNN算法對(duì)比實(shí)驗(yàn)結(jié)果的統(tǒng)計(jì)數(shù)據(jù)如表2。

從表2可以看出，改進(jìn)算法sPSO-KNN在保持精度不降甚至稍微提高基礎(chǔ)上，執(zhí)行時(shí)間大大縮短。在不同實(shí)驗(yàn)條件下，改進(jìn)算法耗時(shí)減少均在80%以上，說明改進(jìn)算法在提高分類速度方面具有穩(wěn)定性。另外，特征詞數(shù)為500時(shí)，耗時(shí)減少平均為82.9%；特征詞數(shù)為1 000時(shí)，耗時(shí)減少平均為85.49%，說明隨著樣本規(guī)模增大，改進(jìn)算法速度的提高也越來(lái)越顯著。

通過對(duì)實(shí)驗(yàn)數(shù)據(jù)的進(jìn)一步分析發(fā)現(xiàn)，對(duì)于每個(gè)測(cè)試樣本，利用sPSO方法搜索近鄰的進(jìn)化代數(shù)平均為10代左右，由于粒子數(shù)設(shè)置為10，近鄰數(shù)為15，則理論上確定該測(cè)試樣本的k個(gè)近鄰需要經(jīng)過約1 500次相似性比較，遠(yuǎn)低于傳統(tǒng)KNN算法的8 669次。同時(shí)，通過對(duì)距離表的監(jiān)測(cè)發(fā)現(xiàn)，實(shí)際上經(jīng)過相似性比較的訓(xùn)練樣本數(shù)平均為1 100個(gè)左右，說明設(shè)置距離表所避免的重復(fù)計(jì)算開銷接近30%。

表2 實(shí)驗(yàn)結(jié)果統(tǒng)計(jì)數(shù)據(jù)

4 結(jié)語(yǔ)

利用粒子群優(yōu)化算法進(jìn)行組合優(yōu)化，粒子的進(jìn)化只針對(duì)樣本的編號(hào)，而不涉及具體形式與取值，這種特性使粒子群算法非常適用于KNN算法的近鄰搜索。雖然屬于一種隨機(jī)搜索策略，不能像利用不等式排除等全局最優(yōu)搜索方法一樣，得到的解一定為精確的k個(gè)近鄰，但其搜索過程也是基于全局范圍，有很大概率能夠搜索到精確的k個(gè)近鄰，對(duì)比實(shí)驗(yàn)也證明這種方法并未導(dǎo)致分類精度下降。粒子在個(gè)體最優(yōu)pbest和群體最優(yōu)gbest的指導(dǎo)下，能夠盡快找到近鄰樣本，而不用與訓(xùn)練樣本逐個(gè)比較，極大降低了計(jì)算開銷，算法執(zhí)行時(shí)間縮短80%以上，并且隨著樣本規(guī)模增大，效率的提升愈發(fā)顯著。如何利用粒子群優(yōu)化算法，在提高算法速度基礎(chǔ)上，進(jìn)一步實(shí)現(xiàn)分類精度的提高，是后續(xù)研究方向。

［1］ 奉國(guó)和.自動(dòng)文本分類技術(shù)研究［J］.情報(bào)雜志，2007，26（12）：108-111.

［2］ YANG Y Y，LIU X.A re-examination of text categorization methods［C］//Hearst M，Gey F，Tong R.Proceedings of 22ndAnnual International ACM SIGIR Conference on Research and Development in Information Retrieval.New York：ACM Press，1999：42-49.

［3］ COVER T M，HART P E.Nearest neighbor pattern classification［J］.IEEE Transactions on Information Theory，1967，IT13（1）：21-27.

［4］ 錢曉東，王正歐.基于改進(jìn)KNN的文本分類方法［J］.情報(bào)科學(xué)，2005，23（4）：550-554.

［5］ RAYMER M L，PUNCH W E，GOODMAN E D，et al.Dimensionality reduction using genetic algorithms［J］.IEEE Transactions on Evolutionary Computation，2000，4（2）：164-171.

［6］ 李瑩，張曉輝，王華勇，等.一種應(yīng)用向量聚合技術(shù)的KNN中文文本分類方法［J］.小型微型計(jì)算機(jī)系統(tǒng)，2004，25（6）：993-996.

［7］ WILSON D L.Asymptotic properties of nearest neighbor rules using edited data［J］.IEEE Transactions on Systems，Man and Cybernetics，1972，SMC-2（3）：408-421.

［8］ HART P E.The condensed nearest neighbor rule［J］.IEEE Transactions on Information Theory.1968，14（3）：515-516.

［9］ 李榮陸，胡運(yùn)發(fā).基于密度的KNN文本分類器訓(xùn)練樣本剪裁方法［J］.計(jì)算機(jī)研究與發(fā)展，2004，41（4）：539-545.

［10］ 魯婷，王浩，姚宏亮.一種基于中心文檔的KNN中文文本分類算法［J］.計(jì)算機(jī)工程與應(yīng)用，2011，47（2）：127-130.

［11］ 吳春穎，王士同.一種改進(jìn)的KNN Web文本分類方法［J］.計(jì)算機(jī)應(yīng)用研究，2008，25（11）：3275-3277.

［12］ 張孝飛，黃河燕.一種采用聚類技術(shù)改進(jìn)的KNN文本分類方法［J］.模式識(shí)別與人工智能，2009，22（6）：936-940.

［13］ 王煜，白石，王正歐.用于Web文本分類的快速KNN算法［J］.情報(bào)學(xué)報(bào)，2007，26（1）：60-64.

［14］ 喬玉龍，潘正祥，孫圣和.一種改進(jìn)的快速k-近鄰分類算法［J］.電子學(xué)報(bào)，2005，33（6）：1146-1149.

［15］ KENNEDY J，EBERHART R C.Particle swarm optimization［C］//IEEE.Proceedings of 1995 IEEE International Conference on Neural Networks.New York：IEEE，1995：1942-1948.

［16］ SHI Y H，EBERHART R C.Empirical study of particle swarm optimization［C］//IEEE.Proceedings of the 1999 Congress on Evolutionary Computation.New York：IEEE，1999：1945-1950.

［17］ OZCAN E，MOHAN C.Particle swarm optimization：surfing the waves［C］//IEEE.Proceedings of the 1999 Congress on Evolutionary Computation.New York：IEEE，1999：1939-1944.

［18］ EBERHART R C，SHI Y H.Particle swarm optimization：development，applications and resources［C］//IEEE.Proceedings of the 2001 Congress on Evolutionary Computation.New York：IEEE，2001：81-86.

［19］ YAMILLE D V，VENAYAGAMOORTHY G K，MOHAGHEGHI S，et al.Particle swarm optimization：basic concepts，variants and applications in powersystems［J］.IEEE Transactions on Evolutionary Computation，2008，12（2）：171-195.

［20］ 胡旺，李志蜀.一種更簡(jiǎn)化而高效的粒子群優(yōu)化算法［J］.軟件學(xué)報(bào)，2007，18（4）：861-868.

［21］ 張國(guó)英，沙蕓，江慧娜.基于粒子群優(yōu)化的快速KNN分類算法［J］.山東大學(xué)學(xué)報(bào)（理學(xué)版），2006，41（3）：34-36，42.

［22］ KENNEY J，EBERHART R C.A discrete binary version of the particle swarm algorithm［C］//IEEE.1997 IEEE international conference on systems，man，and cybernetics，computational cybernetics and simulation.New York：IEEE，1997：4104-4108.

［23］ LIANG Z G，GU X S，et al.A novel particle swarm optimization algorithm for permutation flow-shop scheduling to minimize makespan［J］.Chaos，solitons and fractals，2008，35（5）：851-861.

［24］ 中科院自動(dòng)化所.以IG卡方等特征詞選擇方法生成的多維度ARFF格式中文VSM模型［EB/OL］.（2013-04-20）［2017-07-06］.http：//www.datatang.com/data/13485.

Research on the Improvement of KNN Algorithm Based on Particle Swarm Optimization

WU Jingxue
（School of Design，Shunde Polytechnic，F(xiàn)oshan Guangdong 528333，China）

In order to overcome the shortcomings of taking too much time in seraching for neighbors of the traditional KNN algorithm，this paper puts forward the particle swarm optimization algorithm to search for neighbors. Particles are initialized as the serial number of the k training samples，and in each iteration，an optimal individual pbest is defined as the set containing the current particle and the nearest neighbors searched by its previous pbest，and a group optimal gbest is defined as the set of nearest neighbors searched by current pbest. A distance index is used to avoid double counting. Contrastive experiments showed that the improved algorithm could shorten the time by more than 80%，without decreasing or even increasing the accuracy slightly.

KNN；particle swarm optimization；text categorization

TP301.6；G354

A

1672-6138（2017）04-0005-05

10.3969/j.issn.1672-6138.2017.04.002

2017-07-06

吳敬學(xué)（1986—），男，回族，河北承德人，碩士，研究方向：數(shù)據(jù)挖掘，經(jīng)濟(jì)信息分析。

曹娜］