肖 錚

（四川工商職業(yè)技術學院 信息工程系，成都 611830）

0 引言

K 近鄰算法在選擇用于分類判斷的近鄰時，只考慮距離輸入樣本足夠近的那些訓練樣本，即只使用了輸入樣本的近鄰信息，可以看作是一種單向選擇過程。在實際應用中，訓練樣本的近鄰信息對于分類判決同樣具有重要作用，它們的近鄰也可以被用來判斷它們與輸入樣本之間的鄰近性[1]。因此，為了同等地考慮輸入樣本和訓練樣本的作用，提出一種雙向近鄰選擇方法，即K 廣義近鄰（KGNN，k-general nearest neighbor）算法[2]。算法的基本思想是：尋找輸入樣本的K 近鄰訓練樣本，采用K 近鄰包含輸入樣本的訓練樣本作為廣義近鄰，再通過多數(shù)表決規(guī)則對輸入樣本進行分類。[3]

1 算法實現(xiàn)

1.1 算法描述

KGNN 算法推廣了傳統(tǒng)KNN 算法中的近鄰選擇方法，從雙向角度，以更廣義的方式來看待輸入樣本和訓練樣本之間的關系[4]。只要輸入樣本和訓練樣本滿足單向近鄰條件，就可以將該樣本選作廣義近鄰用來分類。也就是說，KGNN 算法綜合考慮了輸入樣本和訓練樣本的近鄰信息，以便選出更為可靠的近鄰，提高分類效果[5]。圖1 簡單描述了KGNN 算法的流程。

圖1 KGNN 算法流程圖

同時，KGNN 算法擴大了近鄰的范圍，使得所選出的廣義近鄰可能與輸入樣本具有較遠的距離，而這些近鄰分類能力本來就比較弱。此外，由于廣義近鄰中的一部分是從訓練樣本的角度考慮所選，因此可能分布稀疏，具有任意的形狀，包含很多離群點。[6]

1.2 改進算法

改進優(yōu)化進行篩選的基本思路是將廣義近鄰劃分為核心近鄰與其他近鄰兩部分，其中核心近鄰是與輸入樣本互為K 近鄰的那部分，因此全部保留作為最終近鄰以用于分類判決。同時由于這種親密性，認為與核心近鄰相似性較小的其他近鄰與輸入樣本之間的相似性也較小，因此刪去。

此算法具體的篩選規(guī)則為：保留全部m 個核心近鄰，如果某個其他近鄰的2m 個近鄰中包含2m 個核心近鄰，則將它保留，否則刪除。算法的簡單流程如圖2 所示。

1.3 算法步驟

圖2 改進算法流程圖

第一步，根據(jù)GNN 規(guī)則尋找x′在當前k 值下的廣義近鄰，表示為GNNk（x′）。GNN 規(guī)則具體描述如下：

任意訓練樣本xi，若x′∈KNk（xi）或xi∈KNk（x′），則xi∈GNNk（x′）。其中KNk（xi）和KNk（x′）分別表示 xi和 x′在 T′中的 k 近鄰。

第二步，將x′的廣義近鄰GNNk（x′）劃分為核心近鄰CNNk（x′）和其他近鄰ONNk（x′）兩部分。劃分規(guī)則為：

若某廣義近鄰xi滿足x′∈KNk（xi），且xi∈KNk（x′），即xi和x′互為近鄰關系，則被選為核心近鄰，即xi∈CNNk（x′）；否則被劃分為其他近鄰，即xi∈ONNk（x′）。

第三步，選擇最終近鄰 FNNk（x′）。篩選規(guī)則為：

將全部核心近鄰保留作為最終近鄰，即CNNk（x′）?FNNk（x′），并統(tǒng)計其數(shù)目c；對于某其他近鄰xi∈ONNk（x′），如果它的2m 個近鄰中包含m/2個核心近鄰，則將它保留，即xi∈FNNk（x′），否則刪除。

第四步，分類判決。公式為：

1.4 算法實驗

為了衡量所提方法的分類性能，將其在不同k 值下的分類錯誤率與傳統(tǒng)KNN 算法及KGNN算法進行對比。表1 給出了所用的6 個UCI 真實數(shù)據(jù)集的具體信息。

每次實驗將數(shù)據(jù)集隨機劃分為訓練集和測試集，訓練集包含整個數(shù)據(jù)集中約30%的樣本，測試集為數(shù)據(jù)集中剩余的樣本，訓練集的尺寸如表1所示。重復進行20 次實驗，最終的實驗結果為這20 次實驗的平均值。

表1 實驗中所用真實數(shù)據(jù)集的特征

2 實驗結果

不同數(shù)據(jù)集中不同k 值下分類錯誤率如表2所示。括號中的值表示與KGNN 算法相比，所提方法錯誤率減小的百分比，即正值表示錯誤率下降。粗體字表示該k 值下四種方法錯誤率的最小值。從核心近鄰的角度，考慮其他近鄰與它們的近鄰關系，希望能夠保留聚集在核心近鄰周圍的部分其他近鄰。

3 結果分析

篩選方案從其他近鄰的角度，考慮核心近鄰與其他核心近鄰的近鄰關系，希望能夠保留與多數(shù)核心近鄰距離都比較近的其他近鄰。也就是說，基于KGNN 的改進算法保留了與部分核心近鄰距離較近的其他近鄰，而忽略了其他近鄰的空間分布。實驗結果表明，提出的改進方法在多個數(shù)據(jù)集上均能獲得比KGNN 算法更好的效果。

KGNN 算法推廣了傳統(tǒng)KNN 算法中的近鄰選擇方法，提出廣義近鄰的概念，擴大了近鄰的范圍，也因此使得所選近鄰中可能包含過多的離群點，影響分類性能。針對KGNN 算法中選出的廣義近鄰，提出了篩選方案，能夠選出并刪除潛在的離群點，以便進一步提高分類效果。在接下來的工作中，希望能夠找到更為合理的篩選方法，以進一步提高算法的分類效果。

表2 不同數(shù)據(jù)集中不同k 值下的分類錯誤率（%）

續(xù)表