粒向量与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改进算法，我们从全新的角度出发，在集合论与单特征邻域信息粒化的基础上定义了粒向量，并提出一种新的分类器模型：K近邻粒分类器.信息粒的概念最初由Zadeh[24]定义;粒计算首次由Lin等人[25-26]提出;苗夺谦等人[27]从集合论角度讨论了粒计算的结构;王国胤等人[28-29]分析了粒计算中的不确定性度量及在大数据中的应用;Yao等人[30-31]提出了邻域系统及邻域粒计算;Hu等人[32-34]分析了邻域约简和分类;Pedrycz等人[35-37]设计了多种超盒模糊粒分类器.我们从分类系统的单特征邻域粒化出发，定义了粒向量距离度量，提出了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个邻域粒向量，邻域粒向量和类别标签组成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近邻粒分类器没有训练过程，只有粒化过程、匹配过程和分类过程.粒化过程包括：数据预处理、划分训练集和测试集、训练集粒化为粒向量规则库、测试集粒化为测试粒向量集合.粒匹配过程包括：测试粒向量与粒向量规则的距离计算，按照粒距离进行排序，选出k个最近邻的粒向量规则.分类过程则包括：判定测试粒向量的类别.具体的粒化、匹配与分类过程为：

1)数据集预处理.删去存在缺失值的数据，对数据集归一化为0～1之间的数值.

2)划分训练集与测试集.按照训练集80%与测试集20%的规则进行划定.

3)邻域粒化训练集.设定粒化参数，根据单特征粒化训练集，形成粒向量规则库.

4)邻域粒化测试集.取出一个测试样本，在每个单特征上计算该测试样本与每个训练样本的距离，形成一个测试粒向量，所有的测试样本粒化为测试粒向量集合.

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)中训练集的邻域粒化采用Hash排序算法，时间复杂度为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 邻域参数的影响

邻域粒化过程需要设置邻域粒化的参数，实验中邻域粒化参数以0.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近邻粒分类器的构建.还可以研究局部数据的粒化，构建局部邻域粒向量，将本文提出的分类方法应用于大数据系统的分类领域.