粒向量与K近邻粒分类器

陈玉明 李 伟

(厦门理工学院计算机与信息工程学院 福建厦门 361024)(cym0620@163.com)

摘 要 K近邻(K nearest neighbor,KNN)分类器是一种经典的分类器,它简单而又有效,已经在人工智能与机器学习领域得到了广泛的应用.针对传统分类器难以处理不确定性数据的问题,研究样本单特征邻域粒化技术,构造粒的向量形式,提出一种基于粒向量的K近邻分类方法.该方法引入邻域粗糙集模型,对分类系统中的样本进行单特征邻域粒化,形成特征邻域粒子.并由多个特征邻域粒子构成一个粒向量,定义了多种粒向量运算算子,提出了2种粒向量距离:相对粒距离与绝对粒距离,证明了粒向量距离的单调性原理.进一步,基于粒向量距离定义了K近邻粒向量概念,提出了K近邻粒分类器.最后,结合UCI数据集,采用K近邻粒分类器与经典K近邻分类器进行比较测试.理论分析和实验表明:针对合适的粒化参数与k值,K近邻粒分类器具有较好的分类性能.

关键词 KNN分类器;粒计算;粒向量;粒距离;粒分类器

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,yS和单原子特征∀aF,定义样本x,y在单原子特征a上的距离函数为

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

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

定义3.设分类系统为C=(S,F,L)和邻域粒化参数为δ,对于样本∀xS,单原子特征∀aF,则xa上的δ邻域粒子定义为

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

性质1.根据邻域粒子的定义,xa上的δ邻域粒子ga(x)δ满足4个性质:

1)ga(x)δ≠∅;

2)xga(x)δ

3)xga(y)δyga(x)δ

定义4.设分类系统为C=(S,F,L)和邻域粒化参数为δ,对于样本∀xS,单原子特征∀aF,邻域粒子ga(x)δ的大小定义为

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

|·|表示集合的基数.易知邻域粒子的大小满足:1≤|ga(x)δ|≤|S|.

定义5.设分类系统为C=(S,F,L)和邻域粒化参数为δ,对于样本∀xS,特征子集∀PF,设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)和邻域粒化参数为δ,对于样本∀xS,特征子集∀PF,设P={a1,a2,…,am},则x在特征子集P上的δ邻域粒向量VP(x)δ的大小定义为

粒向量VP(x)δ的大小也称为粒向量的模.

定理1.设分类系统为C=(S,F,L),对于样本∀xS,单特征∀aFga(x)γga(x)δxa上的邻域粒子,若0≤γδ≤1,则ga(x)γga(x)δ.

证明.对于∀xS,根据邻域粒子的定义,则有ga(x)γ={y|x,yS,Da(x,y)≤γ}和ga(x)δ={y|x,yS,Da(x,y)≤δ}.因0≤γδ≤1,易知ga(x)γga(x)δ.

证毕.

定理2.设分类系统为C=(S,F,L),对于样本∀xS,特征子集∀PFgP(x)γgP(x)δxP上的邻域粒元素,若0≤γδ≤1,则|gP(x)γ|≤|gP(x)δ|.

证明.对于∀aF和0≤γδ≤1,根据定理1,则ga(x)γga(x)δ.因此,|ga(x)γ|≤|ga(x)δ|成立.对于∀PF,根据定义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 邻域分类系统

Sabclx10.10.20.11x20.20.50.21x30.30.30.30x40.70.10.30

样本集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},则x1P上的粒向量为

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

该粒向量的大小为

x2P上的粒向量为

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

该粒向量的大小为

x3P上的粒向量为

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

该粒向量的大小为

x4P上的粒向量为

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).∀xS,存在F上的δ邻域粒向量VF(x)δ,则在F上所有粒向量的集合称为粒向量组,定义为

ZFδ={VF(x)δ|∀xS}.

定义8.设分类系统为C=(S,F,L),其中特征集为F=(a1,a2,…,am).对于∀x,yS,存在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,yS,存在F上的2个δ邻域粒向量为

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

则2个粒向量的相对距离定义为

d(VF(x)δ,VF(y)δ)=


定理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)δ|,可知:

=

F=(a1,a2,…,am),可知|F|=m.因此,|F|,则由定义9,因P=VF(x)δ,Q=VF(y)δ,则0≤d(P,Q)≤1成立.

证毕.

定义10.设分类系统为C=(S,F,L),其中特征集F={a1,a2,…,am}.对于∀x,yS,存在F上的2个δ邻域粒向量为VF(x)δ=(ga1(x)δ,ga2(x)δ,…,gam(x)δ),VF(y)δ=(ga1(y)δ,ga2(y)δ,…,gam(y)δ),则2个粒向量的绝对距离定义为

h(VF(x)δ,VF(y)δ)=


|gam(x)δgam(y)δ|).

定理4.任意2个邻域粒向量P=VF(x)δ,Q=VF(y)δ的绝对距离满足:0≤h(P,Q)≤1.

证明.设s=gai(x)δt=gai(y)δ,由|gai(x)δgai(y)δ|=|gai(x)δgai(y)δ-gai(x)δgai(y)δ|,可知,0≤|gai(x)δgai(y)δ|≤|S|.由F=(a1,a2,…,am),知|F|=m,则|F|×|S|.由:

h(VF(x)δ,VF(y)δ)=
gai(y)δ|,

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

证毕.

定义11.设分类系统为C=(S,F,L),∀xS,存在F上的δ邻域粒向量VF(x)δ.设lxL为样本x的类别标签,则一条邻域粒向量规则定义为序对:r(x)=〈VF(x)δ,lx〉,邻域粒向量规则库定义为:B={r(x)|∀xS}.

分类系统通过邻域参数粒化为单特征邻域粒子,多个单特征邻域粒子构成邻域粒向量.邻域粒向量与其类别标签形成一条粒向量规则,粒向量规则的集合构成了粒向量规则库.因此,分类过程则可转化为粒向量规则库中的推理、搜索与匹配过程.

邻域粒向量的距离可以作为粒向量的相似性度量,表示邻域粒向量的相似程度,粒向量距离越小,2个粒向量的相似度越大;反之,粒向量距离越大,2个粒向量的相似度越小.

2.3 K近邻粒向量组

定义12.设分类系统为C=(S,F,L),ZF上的邻域粒向量组,k>0的正整数,对于任一δ邻域粒向量PZ,则该粒向量PK近邻粒向量组定义为

VKNN(P,Z)={IZ|∀TiI,
TjZ-I,(|I|=k)∧(d(P,Ti)≤d(P,Tj))}.

邻域粒向量组是所有邻域粒向量的集合,邻域粒向量PK近邻粒向量组是邻域粒向量组的子集,只是部分邻域粒向量的集合,即为邻域粒向量组中离邻域粒向量P最近的k个邻域粒向量.根据邻域粒向量的距离可以定义了2种K近邻粒向量组,第1种是基于绝对距离的K近邻粒向量组,第2种是基于相对距离的K近邻粒向量组.

定义13.设分类系统为C=(TrTe,F,L),其中Tr为训练集,Te为测试集.设Z为训练集Tr上的粒向量组.对于测试样本∀xTe,单特征∀aiF,测试样本x在训练集Tr中特征ai上的δ邻域测试粒子为gai(x)δ={y|xTe,yTr,Dai(x,y)≤δ},则测试样本x在训练集Tr中的测试粒向量为R=VF(x)δ=(ga1(x)δ,…,gai(x)δ,…,gam(x)δ),则测试粒向量RK近邻粒向量组定义为

VKNN(R,Z)={IZ|∀TiI,∀TjZ-I,
(|I|=k)∧(d(R,Ti)≤d(R,Tj))}.

测试粒向量R是测试样本x在训练集粒化而形成的邻域粒向量.测试粒向量RK近邻粒向量组是训练集粒向量组中离测试粒向量R最近的k个邻域粒向量.

2.4 K近邻粒分类器

通过对测试粒向量RK近邻粒向量组定义,我们可知,测试粒向量的分类可转为在粒向量组中寻找与匹配k个最近邻粒向量的过程.根据粒向量组和粒向量规则库的定义可知,带有类别标签的粒向量的集合即为粒向量规则库.因此,测试粒向量的分类可转化为在粒向量规则库中的搜索与匹配k个最近邻粒向量的过程.

定义14.设分类系统为C=(TrTe,F,L),其中Tr为训练集,Te为测试集.设B为训练集Tr在特征集F上粒向量规则库.对于测试样本∀xTe,测试样本x在训练集Trδ邻域测试粒向量为R=VF(x)δ=(ga1(x)δ,ga2(x)δ,…,gai(x)δ,…,gam(x)δ),其中gai(x)δ={y|xTe,yTr,Dai(x,y)≤δ},则测试粒向量RK近邻粒向量规则组定义为

VKNL(R,B)={IB|∀TiI,
TjB-I,(|I|=k)∧(d(R,Ti)≤d(R,Tj))}.

定义15.设分类系统为C=(TrTe,F,L),其中Tr为训练集,Te为测试集.对于测试样本xTe的邻域测试粒向量RLd(R)为测试粒向量RK近邻粒向量规则组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)、测试样本tk值及邻域参数δ;

输出:测试样本t的类别标签lt.

1)训练集和测试样本归一化:Tr,t∈[0,1];

2)对每一个训练样本xTr循环执行步骤3)~6):

3)在每个单原子特征aiF上分别进行δ邻域粒化为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〉和粒向量距离dh插入临时变量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<n;步骤8)~14)都是线性复杂度,为O(m).因而,最坏情况下,VKNG算法的时间复杂度为O(m×n2).根据采用相对粒距离与绝对粒距离的不同,VKNG算法分为VKNGR算法与VKNGA算法.

4 实验分析

本文采用UCI数据集中8个数据集作为实验测试的数据源,如表2所示:

Table 2 Descriptions of Datasets
表2 数据集描述

DatasetsSamplesFeaturesCategoriesEcoli33678Glass21496Iris15043Pima76882Seeds21073Segmentation210197WDBC569302Wine178133

由于表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.2 Classification accuracy of different δ on datasets Iris and Pima
图2 在数据集Iris和Pima上不同邻域参数的分类精度

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近邻粒分类器的构建.还可以研究局部数据的粒化,构建局部邻域粒向量,将本文提出的分类方法应用于大数据系统的分类领域.

参考文献

[1]Hart P E.The condensed nearest neighbor rule[J].IEEE Transactions on Information Theory,1968,14(3):515-516

[2]Kamencay P,Zachariasova M,Hudec R,et al.A novel approach to face recognition using image segmentation based on SPCA-KNN method[J].Radioengineering,2013,22(1):92-99

[3]Tan Songbo.An effective refinement strategy for KNN text classifier[J].Expert Systems with Applications,2006,30(2):290-298

[4]Liu Yaohui,Ma Zhengming,Yu Fang.Adaptive density peak clustering based on K nearest neighbors with aggregating strategy[J].Knowledge-Based Systems,2017,133:208-220

[5]Gallego A J,Calvo-Zaragoza J,Valero-Mas J J,et al.Clustering-based k-nearest neighbor classification for large-scale data with neural codes representation[J].Pattern Recognition,2018,74:531-543

[6]Maillo J,Ramírez S,Triguero I,et al.kNN-IS:An iterative spark-based design of the k-nearest neighbors classifier for big data[J].Knowledge-Based Systems,2017,117:3-15

[7]Zhang Minling,Zhou Zhihua.ML-KNN:A lazy learning approach to multi-label learning[J].Pattern Recognition,2007,40(7):2038-2048

[8]Du Mingjing,Ding Shifei,Jia Hongjie.Study on density peaks clustering based on k-nearest neighbors and principal component analysis[J].Knowledge-Based Systems,2016,99:135-145

[9]Liu Rui,Wang Hong,Yu Xiaomei.Shared-nearest-neighbor-based clustering by fast search and find of density peaks[J].Information Sciences,2018,450:200-226

[10]Yuan Jiankui,Chen Weimin.A γ dose distribution evaluation technique using the k-d tree for nearest neighbor searching[J].Medical Physics,2010,37(9):4868-4873

[11]Li Can,Qian Jiangbo,Dong Yihong,et al.M2LSH:An LSH based technique for approximate nearest neighbor searching on high dimensional data[J].Acta Electronica Sinica,2017,45(6):1431-1442 (in Chinese)(李灿,钱江波,董一鸿,等.M2LSH:基于LSH的高维数据近似最近邻查找算法[J].电子学报,2017,45(6):1431-1442)

[12]Bhattacharya G,Ghosh K,Chowdhury A S.Granger causality driven AHP for feature weighted kNN[J].Pattern Recognition,2017,66:425-436

[13]Hwang Wenjyi,Wen Kuowei.Fast kNN classification algorithm based on partial distance search[J].Electronics Letters,1998,34(21):2062-2063

[14]Li Ronglu,Hu Yunfa.A density-based method for reducing the amount of training data in kNN text classification[J].Journal of Computer Research and Development,2004,41(4):539-545 (in Chinese)(李荣陆,胡运发.基于密度的kNN文本分类器训练样本裁剪方法[J].计算机研究与发展,2004,41(4):539-545)

[15]Tan Songbo.Neighbor-weighted K nearest neighbor for unbalanced text corpus[J].Expert Systems with Applications,2005,28(4):667-671

[16]Ouyang Desheng,Li Dong,Li Qi.Cross-validation and non-parametric k nearest-neighbour estimation[J].Econometrics Journal,2010,9(3):448-471

[17]Yang Liu,Yu Jian,Jing Liping.An adaptive large margin nearest neighbor classification algorithm[J].Journal of Computer Research and Development,2013,50(11):2269-2277 (in Chinese)(杨柳,于剑,景丽萍.一种自适应的大间隔近邻分类算法[J].计算机研究与发展,2013,50(11):2269-2277)

[18]Ghosh A K,Azen S P.On optimum choice of k in nearest neighbor classification[J].Computational Statistics &Data Analysis,2006,50(11):3113-3123

[19]Li Rong,Ye Shiwei,Shi Zhongzhi.SVM-KNN Classifier:A new method of improving the accuracy of SVM classifier[J].Acta Electronica Sinica,2002,30(5):745-748 (in Chinese)(李蓉,叶世伟,史忠植.SVM-KNN分类器:一种提高SVM分类精度的新方法[J].电子学报,2002,30(5):745-748)

[20]Aburomman A A,Reaz M B I.A novel SVM-kNN-PSO ensemble method for intrusion detection system[J].Applied Soft Computing,2016,38:360-372

[21]Kar S,Sharma K D,Maitra M.Gene selection from microarray gene expression data for classification of cancer subgroups employing PSO and adaptive k-nearest neighborhood technique[J].Expert Systems with Applications,2015,42(1):612-627

[22]Sun Xiao,Pan Ting,Ren Fuji.Facial expression recognition using ROI-KNN deep convolutional neural networks[J].Acta Automatica Sinica,2016,42(6):883-891 (in Chinese)(孙晓,潘汀,任福继.基于ROI-KNN卷积神经网络的面部表情识别[J].自动化学报,2016,42(6):883-891)

[23]Keller J M,Gray M R,Givens J A.A fuzzy k-nearest neighbor algorithm[J].IEEE Transactions on Systems Man &Cybernetics,1985,15(4):580-585

[24]Zadeh L A.Toward a theory of fuzzy information granulation and its centrality in human reasoning and fuzzy logic[J].Fuzzy Sets and Systems,1997,90(2):111-127

[25]Lin Tsauyoung.Data mining:Granular computing approach[G] //LNCS 1574:Proc of the Pacific-Asia Conf on Knowledge Discovery and Data Mining.Berlin:Springer,1999:24-33

[26]Lin Tsauyoung,Zadeh L A.Special issue on granular computing and data mining[J].International Journal of Intelligent Systems,2004,19(7):565-566

[27]Miao Duoqian,Xu Feifei,Yao Yiyu,et al.Set-theoretic formulation of granular computing[J].Chinese Journal of Computers,2012,35(2):351-363 (in Chinese)(苗夺谦,徐菲菲,姚一豫,等.粒计算的集合论描述[J].计算机学报,2012,35(2):351-363)

[28]Wang Guoyin,Zhang Qinghua,Ma Xiao,et al.Granular computer models for knowledge uncertainty[J].Journal of Software,2011,22(4):676-694 (in Chinese)(王国胤,张清华,马希骜,等.知识不确定性问题的粒计算模型[J].软件学报,2011,22(4):676-694)

[29]Xu Ji,Wang Guoyin,Yu Hong.Review of big data processing based on granular computing[J].Chinese Journal of Computers,2015,38(8):1497-1517 (in Chinese)(徐计,王国胤,于洪.基于粒计算的大数据处理[J].计算机学报,2015,38(8):1497-1517)

[30]Yao Yiyu.Relational interpretations of neighborhood operators and rough set approximation operators[J].Information Sciences,1998,111(1):239-259

[31]Yao Yiyu,Zhang Nan,Miao Duoqian,et al.Set-theoretic approaches to granular computing[J].Fundamenta Informaticae,2012,115:247-264

[32]Hu Qinghua,Yu Daren,Xie Zongxia.Neighborhood classifiers[J].Expert Systems with Applications,2008,34(2):866-876

[33]Hu Qinghua,Yu Daren,Liu Jinfu,et al.Neighborhood rough set based heterogeneous feature subset selection[J].Information Sciences,2008,178(18):3577-3594

[34]Zhu Pengfei,Hu Qinghua.Adaptive neighborhood granularity selection and combination based on margin distribution optimization[J].Information Sciences,2013,249:1-12

[35]Pedrycz W,Park B J,Oh S K.The design of granular classifiers:A study in the synergy of interval calculus and fuzzy sets in pattern recognition[J].Pattern Recognition,2008,41(12):3720-3735

[36]Roh S B,Pedrycz W,Ahn T C.A design of granular fuzzy classifier[J].Expert Systems with Applications,2014,41(15):6786-6795

[37]Zhong Chunfu,Pedrycz W,Wang Dan,et al.Granular data imputation:A framework of granular computing[J].Applied Soft Computing,2016,46:307-316

[38]Pawlak Z.Rough sets[J].International Journal of Information and Computer Sciences,1982,11(1):341-356

Granular Vectors and K Nearest Neighbor Granular Classifiers

Chen Yuming and Li Wei

(College of Computer and Information Engineering,Xiamen University of Technology,Xiamen,Fujian 361024)

Abstract K nearest neighbor (KNN)classifier is a classical,simple and effective classifier.It has been widely employed in the fields of artificial intelligence and machine learning.Aiming at the problem that traditional classifiers are difficult to deal with uncertain data,we study a technique of neighborhood granulation of samples on each atom feature,construct some granular vectors,and propose a K nearest neighbor classification method based on these granular vectors in this paper.The method introduces a neighborhood rough set model to granulate samples in a classification system,and the raw data can be converted into some feature neighborhood granules.Then,a granular vector is induced by a set of neighborhood granules,and several operators of granular vectors are defined.We present two metrics of granular vectors which are relative granular distance and absolute granular distance,respectively.The monotonicity of distance of granular vectors is proved.Furthermore,the concept of K nearest neighbor granular vector is defined based on the distance of granular vectors,and K nearest neighbor granular classifier is designed.Finally,the K nearest neighbor granular classifier is compared with the classical K nearest neighbor classifier using several UCI datasets.Theoretical analysis and experimental results show that the K nearest neighbor granular classifier has better classification performance under suitable granulation parameters and k values.

Key words K nearest neighbor (KNN)classifier;granular computing;granular vector;granular distance;granular classifier

中图法分类号 TP181

收稿日期2018-08-14;修回日期:2019-05-22

基金项目国家自然科学基金项目(61573297,61976183);福建省出国留学奖学基金项目;福建省自然科学基金项目(2016J01198,2019J01850);福建省教育厅A类项目(JA15363);厦门市科技计划指导项目(3502Z20179038)

This work was supported by the National Natural Science Foundation of China (61573297,61976183),the Scholarship for Studying Abroad Program of Fujian Province,the Natural Science Foundation of Fujian Province of China (2016J01198,2019J01850),the Class A Project Fujian Provincial Education Department (JA15363),and the Science and Technology Planning Guidance Project of Xiamen (3502Z20179038).

Chen Yuming,born in 1977.PhD,professor.His main research interests include machine learning,rough sets,and granular computing.

Li Wei,born in 1979.PhD,associate professor.His main research interests include artificial intelligence,computer graphics,and granular computing.