吴晓明

摘 要：本文提出了一种新的核k近邻分类算法（GEPKNN）。主要内容是在基因表达式编程中，依靠GEP搜索复杂表达式空间方面的优势，为核KNN自动构造与数据相关的核函数，以减小人工选择核函数的主观性，达到提升核KNN分类性能的目的。该算法优于传统核KNN算法，结构简单，分类速度快并且在高维空间上仍然保持较好的分类性能。

关键词：核KNN算法；遗传算子；基因表达式编程；核k近邻分类器

核KNN的主要不足在于其分类性能对核函数比较敏感。为了降低选择核函数时的不确定性，笔者提出了一种基于基因表达式编程的核KNN算法，简记为GEPKNN。算法的基本思路是利用GEP的函数空间搜索能力，为核KNN自动构造与训练数据相关的核函数。

一、GEPKNN算法

1.核KNN算法

核KNN与KNN的主要区别在于使用了不同的距离度量，如果将KNN所用的X上的欧氏距离替换为核距离，就得到了一个核KNN分类器。

2.遗传算子

GEP的大部分遗传算子可以不加改变地应用到GEPKNN中。需要注意的是，应用遗传算子于染色体时，必须保持EDOM和PDOM的边界，防止产生无效的后代，还要引入两个特殊的算子用于进化PDOM域：其中PDInversion算子转置PDOM中的随机子串，而CPMutation改变常数池中随机位置上的常数。

3.适应度函数

为了缩短训练时间，我们在算法中统一取k=3。

求个体适应度的具体过程是：个体I的两个域（表达式域和参数域）解码后组装成核函数k，把k载入核KNN后就可以在其上作k折交叉验证了。假设经过k折交叉验证得到的平均错误率是e，令个体的适应度为：