k最近邻算法已广泛用于数据挖掘、模式识别、机器学习、生物信息学等多个领域,也一直是国内外研究的热点。然而,k NN算法有高的计算复杂性、对训练样本的依赖性、样本之间没有权重区别等问题。膜计算是生物计算的一个分支,简称为P系统。P系统具有分布式、并行性、非确定性、可拓展性、易于程序实现等特性,适于求解应用问题。P系统通过多个膜并行计算,利用进化与转运机制求解问题的全局最优解,能够克服传统算法陷入局部最优的缺点。本文针对k最近邻算法所遭遇的几个问题,考虑利用P系统的分布式和并行计算优势和对象的进化-转运机制来改进传统的k最近邻算法,提出了两种改进的k最近邻算法,分别是由P系统优化的k最近邻算法(k NN-P)和由P系统进化的可编辑的k最近邻算法(Edited-k NN-P)。论文的主要创新性工作如下:(1)基于P系统改进的k最近邻算法。首先设计了一个组织型P系统,此处的P系统结构只涉及细胞与环境之间交流,不包含细胞与细胞之间的交流;采用PSO速度-位移模型让每个细胞进化出最好的对象;再根据膜计算的转运规则,把每个细胞中进化的最好对象转运到环境中,最后环境中得到的对象就是k邻近算法的最好k个邻居。(2)由P系统进化的可编辑的k最近邻算法。此算法分为两步:首先采用一个P系统进化出一个可编辑的样本集,它是原始样本集的一个子集;然后k NN分类器将依据这个可编辑样本集对未知样本进行分类。此处的主要工作是在算法的第一步,进化出一个可编辑的样本集。设计了一个组织型P系统,包含细胞与细胞之间的交流、细胞与环境之间的交流。采用基于MSE规则的对象评价函数,采用离散二进制PSO的速度-位移模型作为进化规则,通过转运规则将每个细胞中的最好的对象转运到环境中,最后环境中将得到一个最优的对象,即为P系统进化的一个可编辑的样本集。本文提出的两个新算法k NN-P和Edited-k NN-P在18个UCI基准数据集上,分别与经典的k NN算法和8个近几年改进的k NN算法进行了实验对比结果分析,在k∈{3,5,7,9}不同取值的情况下,本文提出的两个算法表现出高的准确率和泛化力。