粒向量與K近鄰粒分類器

陳玉明 李 偉

(廈門理工學院計算機與信息工程學院 福建廈門 361024)(cym0620@163.com)

KNN是最簡單的分類算法，由Hart[1]于1968年提出，主要思想是計算待分類樣本與訓練樣本之間的差異性，并按照差異由小到大排序，選出前面k個差異最小的類別，并統計在k個類別中出現次數最多的類別為最相似的類，最終將待分類樣本分到與訓練樣本最相似的類中.KNN算法在眾多領域得到了廣泛的應用，例如人臉識別[2]、文字識別[3]、聚類[4]、大數據[5-6]、多標簽學習[7]等.經典KNN算法存在時間和空間復雜度高、k個近鄰樣本的同權重影響分類精度、噪聲敏感、不均衡樣本分類精度低、k值難以確定等不足.眾多學者從多個方面提出了許多改進算法[8-23]，提高了KNN算法的效率.

KNN算法存儲訓練集的所有樣本數據，造成了極大的存儲開銷和計算代價.已有很多文獻提出了減少計算的方法，這些方法大致可分為2類：1)減少訓練集的大小，刪去部分冗余的樣本，或通過聚類的方式選擇部分樣本[8]；2)采用快速算法[9]搜索到k個近鄰樣本，以及引入高效的索引方法.比較常用的方法有K-D樹[10]、局部敏感Hash[11]等.

經典KNN算法采用歐氏距離計算相似度，而且賦予每個特征同等的權重，這種方法造成KNN算法對噪聲特征非常敏感.為此，許多改進算法在度量相似度的距離公式中給特征賦予不同權重，可根據特征在整個訓練樣本庫中的分類作用得到特征權重[12]，也可根據訓練樣本庫中的局部樣本靠近待測樣本的距離得到樣本權重[13].當各類樣本分布不均衡時，存在KNN算法分類性能下降的問題.目前改進的方法有均勻化樣本分布密度[14]、優化判決策略.文獻[15]賦予稀少樣本更高的權重，使得樣本相對更均勻，從而改善了近鄰判決規則.

KNN的分類效果很大程度上依賴于k值的選擇.k值選擇過小，得到的近鄰數過少，會降低分類的精度，同時放大了噪聲數據的干擾；而k值選擇過大，把實際上并不相似的數據也包含進來，造成噪聲增加而導致分類效果降低.如何選擇恰當的k值也成為KNN研究的熱點[16-18].

除上述改進算法之外，也有研究者將KNN和其他分類算法進行集成.例如KNN與SVM進行集成[19-20]、KNN與PSO集成[21]、深度學習與KNN集成[22]以及模糊KNN[23]等方法，有效提高了KNN分類算法的分類性能.

KNN算法是一個性能優秀的分類算法，許多學者從不同角度提出了多種KNN改進算法，我們從全新的角度出發，在集合論與單特征鄰域信息?；幕A上定義了粒向量，并提出一種新的分類器模型：K近鄰粒分類器.信息粒的概念最初由Zadeh[24]定義;粒計算首次由Lin等人[25-26]提出;苗奪謙等人[27]從集合論角度討論了粒計算的結構;王國胤等人[28-29]分析了粒計算中的不確定性度量及在大數據中的應用;Yao等人[30-31]提出了鄰域系統及鄰域粒計算;Hu等人[32-34]分析了鄰域約簡和分類;Pedrycz等人[35-37]設計了多種超盒模糊粒分類器.我們從分類系統的單特征鄰域?；霭l，定義了粒向量距離度量，提出了K近鄰粒向量的概念，從而將分類問題轉化為K近鄰粒向量的搜索問題，構建了K近鄰粒分類器模型.進一步設計了K近鄰粒分類器，并進行了實驗驗證.理論分析與實驗結果表明，K近鄰粒分類器可以在合適的粒化參數及k值情況下，取得較好的分類性能.

1 鄰域粒化與粒向量

波蘭數學家Pawlak[38]提出的粗糙集理論是分類系統采用最為廣泛的模型之一.在粗糙集理論中，等價類視為一個基本粒子.對于現實世界廣泛存在的實數型數據，需要進行離散化過程，而離散化過程容易造成分類信息的丟失.為此，Yao[30]提出了鄰域粗糙集模型，Hu等人[32-34]應用于數據分類領域，其鄰域粒化是從整個特征空間進行，下面以單個特征為標準進行鄰域粒化并構造粒向量.

定義1.設C=(S,F,L)為一分類系統，其中S={x1,x2,…,xn}為樣本集合，F={f1,f2,…,fm}是特征集合，L表示樣本的標簽或類別.樣本在特征集F上的值是實數型的數據，在標簽L上的值為符號型或離散型的數據.

定義2.設分類系統為C=(S,F,L)，對于樣本?x,y∈S和單原子特征?a∈F,定義樣本x,y在單原子特征a上的距離函數為

Da(x,y)=|v(x,a)-v(y,a)|,

其中，v(x,a)表示樣本x在特征a上的值.

定義3.設分類系統為C=(S,F,L)和鄰域?；瘏禐棣?，對于樣本?x∈S,單原子特征?a∈F,則x在a上的δ鄰域粒子定義為

ga(x)δ={y|x,y∈S,Da(x,y)≤δ}.

性質1.根據鄰域粒子的定義，x在a上的δ鄰域粒子ga(x)δ滿足4個性質：

1)ga(x)δ≠?；

2)x∈ga(x)δ；

3)x∈ga(y)δ?y∈ga(x)δ；

定義4.設分類系統為C=(S,F,L)和鄰域?；瘏禐棣?，對于樣本?x∈S,單原子特征?a∈F,鄰域粒子ga(x)δ的大小定義為

M(ga(x)δ)=|ga(x)δ|,

|·|表示集合的基數.易知鄰域粒子的大小滿足：1≤|ga(x)δ|≤|S|.

定義5.設分類系統為C=(S,F,L)和鄰域粒化參數為δ，對于樣本?x∈S,特征子集?P?F,設P={a1,a2,…,am}，則x在特征子集P上的δ鄰域粒向量定義為

VP(x)δ=(ga1(x)δ,ga2(x)δ,…,gam(x)δ).

ga(x)δ是樣本x在特征a上的δ鄰域粒子，是一個集合的形式，它稱為粒向量的一個元素，簡稱為粒元素.VP(x)δ則為粒向量，由粒元素組成.因此，粒向量的元素是集合，與傳統向量不一樣，傳統向量的元素是一個實數.當粒向量的元素都為空集時，稱為空粒向量，記為Vnull；當粒向量的元素都是樣本集，稱為滿粒向量，記為Vfull.

定義6.設分類系統為C=(S,F,L)和鄰域?；瘏禐棣?，對于樣本?x∈S,特征子集?P?F,設P={a1,a2,…,am}，則x在特征子集P上的δ鄰域粒向量VP(x)δ的大小定義為

粒向量VP(x)δ的大小也稱為粒向量的模.

定理1.設分類系統為C=(S,F,L)，對于樣本?x∈S,單特征?a∈F，ga(x)γ，ga(x)δ為x在a上的鄰域粒子，若0≤γ≤δ≤1，則ga(x)γ?ga(x)δ.

證明.對于?x∈S，根據鄰域粒子的定義，則有ga(x)γ={y|x,y∈S,Da(x,y)≤γ}和ga(x)δ={y|x,y∈S,Da(x,y)≤δ}.因0≤γ≤δ≤1，易知ga(x)γ?ga(x)δ.

證畢.

定理2.設分類系統為C=(S,F,L)，對于樣本?x∈S,特征子集?P?F，gP(x)γ，gP(x)δ為x在P上的鄰域粒元素，若0≤γ≤δ≤1，則|gP(x)γ|≤|gP(x)δ|.

證明.對于?a∈F和0≤γ≤δ≤1，根據定理1，則ga(x)γ?ga(x)δ.因此，|ga(x)γ|≤|ga(x)δ|成立.對于?P?F，根據定義6，可知:

由|ga(x)γ|≤|ga(x)δ|，則|gP(x)γ|≤|gP(x)δ|成立.

證畢.

例1.分類系統C=(S,F,L)如表1所示，S={x1,x2,x3,x4}為樣本集合，F={a,b,c}為特征集合，L={l}為類別標簽.設鄰域?；瘏郸?0.1.

Table 1 A Neighborhood Classification System表1 鄰域分類系統

樣本集S={x1,x2,x3,x4}，若按照特征a進行鄰域粒化，則鄰域粒子分別為g1=ga(x1)0.1={x1,x2}，g2=ga(x2)0.1={x1,x2,x3}，g3=ga(x3)0.1={x2,x3}，g4=ga(x4)0.1={x4}.

若按照特征b進行鄰域?；?，則鄰域粒子分別為g5=gb(x1)0.1={x1,x3,x4}，g6=gb(x2)0.1={x2}，g7=gb(x3)0.1={x1,x3}，g8=gb(x4)0.1={x1,x4}.

若按照特征c進行鄰域粒化，則鄰域粒子分別為g9=gc(x1)0.1={x1,x2}，g10=gc(x2)0.1={x1,x2,x3,x4}，g11=gc(x3)0.1={x2,x3,x4} ，g12=gc(x4)0.1={x2,x3,x4}.

若P={a,b,c}，則x1在P上的粒向量為

VP(x1)δ=(g1,g5,g9)=
(ga(x1)0.1,gb(x1)0.1,gc(x1)0.1)=
({x1,x2},{x1,x3,x4},{x1,x2}).

該粒向量的大小為

x2在P上的粒向量為

VP(x2)δ=(ga(x2)0.1,gb(x2)0.1,gc(x2)0.1)=
({x1,x2,x3},{x2},{x1,x2,x3,x4}),

該粒向量的大小為

x3在P上的粒向量為

VP(x3)δ=(ga(x3)0.1,gb(x3)0.1,gc(x3)0.1)=
({x2,x3},{x1,x3},{x2,x3,x4}).

該粒向量的大小為

x4在P上的粒向量為

VP(x4)δ=(ga(x4)0.1,gb(x4)0.1,gc(x4)0.1)=
({x4},{x1,x4},{x2,x3,x4}).

該粒向量的大小為

2 基于粒向量的K近鄰粒分類器

采用鄰域?；?，將1個樣本?；癁?個鄰域粒向量，鄰域粒向量和類別標簽組成1條粒規則，所有樣本的粒規則構成粒規則庫.通過定義粒距離度量，提出K近鄰粒子的概念，從而將分類問題轉化為K近鄰粒向量的搜索問題.1個測試樣本粒化為1個鄰域粒向量，在粒規則庫中搜索該粒向量的K近鄰粒向量，K近鄰粒向量中數量最多的類別標簽即為測試樣本的預測標簽.

2.1 粒向量的運算

定義7.設分類系統為C=(S,F,L).?x∈S，存在F上的δ鄰域粒向量VF(x)δ，則在F上所有粒向量的集合稱為粒向量組，定義為

ZFδ={VF(x)δ|?x∈S}.

定義8.設分類系統為C=(S,F,L)，其中特征集為F=(a1,a2,…,am).對于?x,y∈S，存在F上的2個δ鄰域粒向量為

VF(x)δ=(ga1(x)δ,ga2(x)δ,…,gam(x)δ)，
VF(y)δ=(ga1(y)δ,ga2(y)δ,…,gam(y)δ)，

則2個粒向量的交、并、減與異或運算定義為

VF(x)δ∧VF(y)δ=(ga1(x)δ∧ga1(y)δ,
ga2(x)δ∧ga2(y)δ,…,gam(x)δ∧gam(y)δ)；
VF(x)δ∨VF(y)δ=(ga1(x)δ∨ga1(y)δ,
ga2(x)δ∨ga2(y)δ,…,gam(x)δ∨gam(y)δ)；
VF(x)δ-VF(y)δ=(ga1(x)δ-ga1(y)δ,
ga2(x)δ-ga2(y)δ,…,gam(x)δ-gam(y)δ)；
VF(x)δ⊕VF(y)δ=(ga1(x)δ⊕ga1(y)δ,
ga2(x)δ⊕ga2(y)δ,…,gam(x)δ⊕gam(y)δ).

2.2 粒向量的距離度量及粒規則

定義9.設分類系統為C=(S,F,L)，其中特征集為F=(a1,a2,…,am).對于?x,y∈S，存在F上的2個δ鄰域粒向量為

VF(x)δ=(ga1(x)δ,ga2(x)δ,…,gam(x)δ)，
VF(y)δ=(ga1(y)δ,ga2(y)δ,…,gam(y)δ)，

則2個粒向量的相對距離定義為

定理3.任意2個鄰域粒向量P=VF(x)δ,Q=VF(y)δ的相對距離滿足：0≤d(P,Q)≤1.

證明.設s=gai(x)δ，t=gai(y)δ由|gai(x)δ⊕gai(y)δ|=|gai(x)δ∨gai(y)δ-gai(x)δ∧gai(y)δ|，可知:

證畢.

定義10.設分類系統為C=(S,F,L)，其中特征集F={a1,a2,…,am}.對于?x,y∈S，存在F上的2個δ鄰域粒向量為VF(x)δ=(ga1(x)δ,ga2(x)δ,…,gam(x)δ)，VF(y)δ=(ga1(y)δ,ga2(y)δ,…,gam(y)δ)，則2個粒向量的絕對距離定義為

定理4.任意2個鄰域粒向量P=VF(x)δ,Q=VF(y)δ的絕對距離滿足：0≤h(P,Q)≤1.

則0≤h(VF(x)δ,VF(y)δ)≤1成立.因P=VF(x)δ,Q=VF(y)δ，則0≤h(P,Q)≤1成立.

證畢.

定義11.設分類系統為C=(S,F,L)，?x∈S，存在F上的δ鄰域粒向量VF(x)δ.設lx∈L為樣本x的類別標簽，則一條鄰域粒向量規則定義為序對：r(x)=〈VF(x)δ,lx〉，鄰域粒向量規則庫定義為：B={r(x)|?x∈S}.

分類系統通過鄰域參數粒化為單特征鄰域粒子，多個單特征鄰域粒子構成鄰域粒向量.鄰域粒向量與其類別標簽形成一條粒向量規則，粒向量規則的集合構成了粒向量規則庫.因此，分類過程則可轉化為粒向量規則庫中的推理、搜索與匹配過程.

鄰域粒向量的距離可以作為粒向量的相似性度量，表示鄰域粒向量的相似程度，粒向量距離越小，2個粒向量的相似度越大；反之，粒向量距離越大，2個粒向量的相似度越小.

2.3 K近鄰粒向量組

定義12.設分類系統為C=(S,F,L)，Z為F上的鄰域粒向量組，k>0的正整數，對于任一δ鄰域粒向量P∈Z，則該粒向量P的K近鄰粒向量組定義為

VKNN(P,Z)={I?Z|?Ti∈I,
?Tj∈Z-I,(|I|=k)∧(d(P,Ti)≤d(P,Tj))}.

鄰域粒向量組是所有鄰域粒向量的集合，鄰域粒向量P的K近鄰粒向量組是鄰域粒向量組的子集，只是部分鄰域粒向量的集合，即為鄰域粒向量組中離鄰域粒向量P最近的k個鄰域粒向量.根據鄰域粒向量的距離可以定義了2種K近鄰粒向量組，第1種是基于絕對距離的K近鄰粒向量組，第2種是基于相對距離的K近鄰粒向量組.

定義13.設分類系統為C=(Tr∪Te,F,L)，其中Tr為訓練集，Te為測試集.設Z為訓練集Tr上的粒向量組.對于測試樣本?x∈Te，單特征?ai∈F，測試樣本x在訓練集Tr中特征ai上的δ鄰域測試粒子為gai(x)δ={y|x∈Te,y∈Tr,Dai(x,y)≤δ}，則測試樣本x在訓練集Tr中的測試粒向量為R=VF(x)δ=(ga1(x)δ,…,gai(x)δ,…,gam(x)δ)，則測試粒向量R的K近鄰粒向量組定義為

VKNN(R,Z)={I?Z|?Ti∈I,?Tj∈Z-I,
(|I|=k)∧(d(R,Ti)≤d(R,Tj))}.

測試粒向量R是測試樣本x在訓練集?；纬傻泥徲蛄Ｏ蛄?測試粒向量R的K近鄰粒向量組是訓練集粒向量組中離測試粒向量R最近的k個鄰域粒向量.

2.4 K近鄰粒分類器

通過對測試粒向量R的K近鄰粒向量組定義，我們可知，測試粒向量的分類可轉為在粒向量組中尋找與匹配k個最近鄰粒向量的過程.根據粒向量組和粒向量規則庫的定義可知，帶有類別標簽的粒向量的集合即為粒向量規則庫.因此，測試粒向量的分類可轉化為在粒向量規則庫中的搜索與匹配k個最近鄰粒向量的過程.

定義14.設分類系統為C=(Tr∪Te,F,L)，其中Tr為訓練集，Te為測試集.設B為訓練集Tr在特征集F上粒向量規則庫.對于測試樣本?x∈Te，測試樣本x在訓練集Tr中δ鄰域測試粒向量為R=VF(x)δ=(ga1(x)δ,ga2(x)δ,…,gai(x)δ,…,gam(x)δ)，其中gai(x)δ={y|x∈Te,y∈Tr,Dai(x,y)≤δ}，則測試粒向量R的K近鄰粒向量規則組定義為

VKNL(R,B)={I?B|?Ti∈I,
?Tj∈B-I,(|I|=k)∧(d(R,Ti)≤d(R,Tj))}.

定義15.設分類系統為C=(Tr∪Te,F,L)，其中Tr為訓練集，Te為測試集.對于測試樣本x∈Te的鄰域測試粒向量R，Ld(R)為測試粒向量R的K近鄰粒向量規則組VKNL(R,B)中的類別標簽集合，則Ld(R)中最多的類別標簽為測試樣本x的類別標簽.

3 基于粒向量的K近鄰粒分類器設計

K近鄰粒分類器是一種基于集合運算的分類器，分為?；?、匹配與分類過程.下面論述K近鄰粒分類器的原理，并給出具體的K近鄰粒分類算法.

3.1 K近鄰粒分類器的原理

K近鄰粒分類器沒有訓練過程，只有?；^程、匹配過程和分類過程.粒化過程包括：數據預處理、劃分訓練集和測試集、訓練集?；癁榱Ｏ蛄恳巹t庫、測試集粒化為測試粒向量集合.粒匹配過程包括：測試粒向量與粒向量規則的距離計算，按照粒距離進行排序，選出k個最近鄰的粒向量規則.分類過程則包括：判定測試粒向量的類別.具體的?；?、匹配與分類過程為：

1)數據集預處理.刪去存在缺失值的數據，對數據集歸一化為0～1之間的數值.

2)劃分訓練集與測試集.按照訓練集80%與測試集20%的規則進行劃定.

3)鄰域粒化訓練集.設定?；瘏?，根據單特征粒化訓練集，形成粒向量規則庫.

4)鄰域粒化測試集.取出一個測試樣本，在每個單特征上計算該測試樣本與每個訓練樣本的距離，形成一個測試粒向量，所有的測試樣本?；癁闇y試粒向量集合.

5)粒向量的搜索與匹配.取出一個測試粒向量，計算該測試粒向量與規則庫中每條粒向量規則的距離，按照距離升序排序，選出k個最近鄰的粒向量規則.

6)測試粒向量的類別判斷.k個最近鄰的粒向量規則中最多的類別標簽則為測試粒向量的類別標簽.

7)所有測試粒向量的分類.轉步驟5，進行下一個測試粒向量的分類，直到所有測試粒向量分類完畢.

從分析可知，K近鄰粒分類器類似于傳統KNN分類器，不需要使用訓練集進行訓練，訓練時間復雜度為0.

3.2 K近鄰粒分類算法

根據前述K近鄰粒分類器的原理與步驟，從而可設計出K近鄰粒分類器，具體的K近鄰粒分類算法描述如算法1所示：

算法1.K近鄰粒分類算法(VKNG).

輸入：訓練集C=(Tr,F,L)、測試樣本t，k值及鄰域參數δ;

輸出：測試樣本t的類別標簽lt.

1)訓練集和測試樣本歸一化：Tr,t∈[0,1]；

2)對每一個訓練樣本x∈Tr循環執行步驟3)～6)：

3)在每個單原子特征ai∈F上分別進行δ鄰域粒化為gai(x)δ；

4)形成x的δ鄰域粒向量

VF(x)δ=(ga1(x)δ,ga2(x)δ,…,gam(x)δ)；

5)獲取x的類別標簽lx；

6)構造粒向量規則R(x)=〈VF(x)δ,lx〉,插入到粒向量規則庫B中；

7)在訓練集中對測試樣本t進行粒化,形成測試粒向量VF(t)δ；

8)對每個粒向量規則R(x)循環執行步驟9),10);

9)根據定義9或定義10計算粒向量距離

d(VF(x)δ,VF(t)δ)或h(VF(x)δ,VF(t)δ)；

10)將粒向量規則〈VF(x)δ,lx〉和粒向量距離d或h插入臨時變量T中；

11)對T中的粒向量按粒向量距離進行升序排序；

12)從T中選出排在前面的k個粒向量及其類別標簽插入到目標變量W中；

13)目標變量W中類別標簽最多的那一類別判定為測試樣本t的類別，設為lt；

14)返回測試樣本的類別標簽lt.

在算法VKNG中，主要涉及鄰域?；^程.步驟3)中訓練集的鄰域?；捎肏ash排序算法，時間復雜度為O(m×n)，其中m為特征的個數，n為訓練樣本的個數；步驟2)～6)時間復雜度則為O(m×n2);步驟7)為測試集的鄰域粒化，時間復雜度為O(m×t2)，其中t為測試樣本的個數，t

4 實驗分析

本文采用UCI數據集中8個數據集作為實驗測試的數據源，如表2所示：

Table 2 Descriptions of Datasets表2 數據集描述

由于表2中數據集的值域不同，需要對數據集進行歸一化預處理.我們采用最大最小值法，以確保所有數據都能轉化為[0,1]之間的數據.最大最小值歸一化公式為

數據在每個單原子特征上進行鄰域?；?，形成粒向量.分類算法分別采用傳統的KNN分類器，基于相對粒向量距離的K近鄰粒分類器VKNGR和基于絕對向量距離的K近鄰粒分類器VKNGA.為測試K近鄰粒分類器的分類精度，每個數據集隨機分成5份，其中一份為測試集，剩下的為訓練集.然后再選另一份為測試集，剩下的為訓練集，共測試5次，分類精度為5次的平均值.

4.1 鄰域參數的影響

鄰域?；^程需要設置鄰域?；膮?，實驗中鄰域?；瘏狄?.05為起點，0.05為間隔，直到1為止.本節實驗主要測試鄰域參數的影響，k值則固定，具體數值由實驗確定.8個UCI數據集的分類結果實驗如圖1～4所示:

Fig.1 Classification accuracy of different δ on datasets Ecoli and Glass圖1 在數據集Ecoli和Glass上不同鄰域參數的分類精度

Fig.3 Classification accuracy of different δ on datasets Seeds and Segmentation圖3 在數據集Seeds和Segmentation上不同鄰域參數的分類精度

Fig.4 Classification accuracy of different δ on datasets WDBC and Wine圖4 在數據集WDBC和Wine上不同鄰域參數的分類精度

從圖1(a)可知，對于Ecoli數據集，傳統KNN分類器在k=7時，分類精度為0.865 7；而對于K近鄰粒分類器，鄰域參數為0.3和0.35，且k=7時，VKNGR分類精度達到最大值為0.895 5，VKNGA分類精度達到最大值為0.895 5.VKNGR算法的分類精度略好于VKNGA算法.在鄰域參數為0.3～0.35時，K近鄰粒分類器的分類效果較好，在鄰域參數較小或較大的情況下分類效果不佳.從圖1(b)可知，對于Glass數據集，k=1時，KNN算法的分類精度為0.698 1，VKNGR算法的最大分類精度為0.792 5，VKNGA算法的最大分類精度為0.811 3，VKNGA算法的分類精度略好于VKNGR算法.當k=1時，在合適鄰域參數下，K近鄰粒分類器好于KNN.對于K近鄰粒分類器，在鄰域參數較小的情況下分類精度較好.

從圖2(a)可知，對于Iris數據集，當k=1時，KNN算法分類精度為0.933 3，VKNGR算法和VKNGA算法在鄰域參數為0.55時分類精度為1.VKNGA算法略好于VKNGR算法.從圖2(b)可知，對于Pima數據集，當k=9時，KNN算法分類精度為0.729 2；VKNGR算法在鄰域參數為0.25時，分類精度達到最大值，為0.760 4；VKNGA算法在鄰域參數為0.4時分類精度達到最大值，為0.760 4.可知在合適鄰域參數下，VKNGA和VKNGR粒分類器好于傳統的KNN算法.

從圖3(a)可知，對于Seeds數據集，當k=3時，KNN算法分類精度為0.904 8；VKNGR算法在鄰域參數為0.6時分類精度達到最大值，為0.928 6；VKNGA算法在鄰域參數為0.5和0.6時分類精度達到最大值，為0.928 6.從圖3(b)可知，對于Segmentation數據集，當k=4時，KNN算法分類精度為0.833 3；VKNGR和VKNGA算法在鄰域參數為0.3～0.4時分類精度都達到最大值，為0.881，且VKNGR算法略好于VKNGA算法.在合適鄰域參數下，VKNGR和VKNGA算法好于傳統的KNN算法.

從圖4(a)可知，對于WDBC數據集，當k=4時，KNN算法分類精度為0.964 8；VKNGA算法在鄰域參數為0.1時分類精度達到最大值，為0.9718；VKNGA算法略好于VKNGR算法.從圖4(b)可知，對于Wine數據集，當k=13時，KNN算法分類精度為0.954 5；VKNGR算法在鄰域參數為0.45和0.55時分類精度達到最大值，為1；VKNGA算法在鄰域參數為0.5～0.55時分類精度達到最大值，也為1.可知在合適鄰域參數下，VKNGR算法和VKNGA算法好于傳統的KNN算法.

從圖1～4的實驗分析可知，當數據集的類別數或特征數較多時，比如Ecoli和WDBC數據集，大部分情況下，粒分類器的分類效果不佳，只有某個鄰域參數下，分類效果才好于KNN算法；當數據集的類別數較小時，比如Iris，Pima，Seeds，Wine，粒分類器的分類效果較好，多數鄰域參數情況下好于KNN算法.當鄰域參數較大時，數據集的分類精度都較低，分類效果不理想.因此，鄰域參數是粒分類器分類精度高低的關鍵因素之一.大部分情況下，VKNGA算法的分類精度略好于VKNGR算法，說明粒向量的絕對距離度量效果略好于粒向量的相對距離度量.

4.2 k值的影響

KNN分類器中，k值的選擇影響著分類的精度.本節實驗主要測試k值的影響，鄰域參數則固定，具體數值由4.1節實驗中分類精度最好情況下的鄰域參數值.實驗中k值從1變化到20為止，8個UCI數據集的分類結果實驗如圖5～8所示.

Fig.5 Classification accuracy of different k on datasets Ecoli and Glass圖5 在數據集Ecoli和Glass上不同k值的分類精度

Fig.6 Classification accuracy of different k on datasets Iris and Pima圖6 在數據集Iris和Pima上不同k值的分類精度

Fig.7 Classification accuracy of different k on datasets Seeds and Segmentation圖7 在數據集Seeds和Segmentation上不同k值的分類精度

Fig.8 Classification accuracy of different k on datasets WDBC and Wine圖8 在數據集WDBC和Wine上不同k值的分類精度

從圖5(a)可知，對于Ecoli數據集，k值偏小時，VKNGR算法和VKNGA算法的分類精度好于KNN算法；k值處于5～12時，KNN算法的分類精度好于VKNGR算法和VKNGA算法；k值處于13～20時，VKNGA算法好于KNN算法，而KNN算法好于VKNGR算法.大部分情況下，VKNGA算法的分類精度好于VKNGR和KNN算法.從圖5(b)可知，對于Glass數據集，VKNGA和VKNGR算法的分類精度都有16次高于KNN算法，而VKNGA算法的分類精度有14次高于VKNGR算法.因此，在不同的k值情況下，VKNGA算法好于KNGR算法，KNGR算法好于KNN算法.

從圖6(a)可知，對于Iris數據集，在k=1時，VKNGA算法和VKNGR算法的分類精度高于KNN算法.在k為15,16或17時，KNN算法的分類精度高于VKNGA算法和VKNGR算法.從圖6(b)可知，對于Pima數據集，在k值為6～13時，VKNGA算法和VKNGR算法的分類精度高于KNN算法；其他k值時，KNN算法的分類精度高于VKNGA算法和VKNGR算法.因此，在合適的k值情況下，VKNGA算法和VKNGR算法優于KNN算法.

從圖7(a)可知，對于Seeds數據集，VKNGR算法的分類精度有8次高于KNN算法，VKNGA算法的分類精度有7次高于KNN算法，而KNN算法的分類精度只有2次高于VKGR和VKGA算法.因此，大部分k值情況下，VKNGR和VKNGA算法好于KNN算法.從圖7(b)可知，對于Seg-mentation數據集，大部分k值情況下，KNN算法的分類精度好于VKNGR算法和VKNGA算法,VKNGA算法的分類精度略好于VKNGR算法.

從圖8(a)可知，對于WDBC數據集，在k值為3～8時，VKNGA算法的分類精度好于VKNGR算法和KNN算法；在k值偏大的情況下，KNN算法的分類精度好于VKNGR和VKNGA算法；大部分情況下，VKNGA算法的分類精度好于VKNGR算法.從圖8(b)可知，對于Wine數據集，VKNGA算法的分類精度有16次高于KNN算法；VKNGR算法的分類精度有12次高于KNN算法.因此，VKNGA算法和VKNGR算法都好于KNN算法.

從圖5～8實驗分析可知，不同k值的情況下，當數據集的類別數較少時，例如Iris，Pima，Seeds，Wine數據集，粒分類器的分類效果較好，大部分情況好于KNN算法；當數據集的類別數或特征數較多時，例如Segmentation和WDBC，粒分類器的分類效果差于KNN算法.大部分情況下，VKNGA算法的分類精度略好于VKNGR算法，說明粒向量的絕對距離度量效果好于粒向量的相對距離度量.k值的選擇也是分類的關鍵，設置過小會降低分類精度，設置過大則會增加噪聲，降低分類效果.一般k值取1～n0.5(n為訓練集樣本個數)的范圍，然后采用交叉驗證法來選取最優的k值.

5 總結與展望

傳統的分類器是數值的計算，未涉及集合的運算，本文從研究樣本的鄰域粒化出發，提出了一種新型的集合形式的分類器：K近鄰粒向量分類器.首先，引入鄰域粗糙集?；椒?，在分類系統中構建粒向量和粒規則，并定義了粒向量的大小度量與運算規則.

進一步提出了粒向量的2種距離度量：粒向量絕對距離與粒向量相對距離，并定義了K近鄰粒向量的概念，設計了K近鄰粒分類器.實驗結果表明:新提出的K近鄰粒分類器能夠成功對樣本進行分類，并在合適?；瘏迪履軌蛉〉幂^好的分類性能.在未來的工作中，引入神經網絡的方法進行參數調參，獲取優化的鄰域?；瘏?，用于K近鄰粒分類器的構建.還可以研究局部數據的粒化，構建局部鄰域粒向量，將本文提出的分類方法應用于大數據系統的分類領域.