核K近邻分类算法在基因表达式编程中的应用

吴晓明

摘 要：本文提出了一种新的核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，令个体的适应度为：

fitness=1000*（1-e）

求适应度函数时，需要频繁计算核距离，因此，缩短计算核距离的时间是提高算法效率的一个有效手段。基于此，我们提出了下面的定理1，该定理很容易用数学归纳法证明。

定理1（求核距离的快速方法）令K={k1，k2，k3}，其中k1、k2、k3是上面提到的3个常用核函数，S是K上的加法、乘法、指数运算等运算符的集合。k是由K和S中元素构成的任一符合语法规范的算术表达式，由定理2可知k是核函数。如果原空间X中的内积进行规范化，则存在实数SPID，对于X中任意点x都有k（x，x）=SPID。

此时，核距离的公式可以修改为：

d>（φ（x1），φ（x2））·■

上式计算核距离可以使求适应度的时间缩短约2/3。

4.GEPKNN算法

综合上面的分析，GEPKNN的伪码如下：

算法（GEPKNN）

输入T//训练集

输出核KNN分类器

Init（p（0））//初始化种群

t=0

while（t

p（t+1）=GEP（p（t））//产生下代种群

for（individual I in p（t+1））{

k=decode（I）//k是核函数

e=crossvalidation（T，核KNN（k））

//用核函数k构造核KNN，在训练集上

//作交叉验证

I.fitness=1000*（1-e）}t++

if（bestFitness>threshold）

Break}

k=decode（p（t）中的最好个体I）

Return核KNN（k）

二、实验结果

为验证GEPKNN算法的有效性，我们在UCI的wisconsin-breast-canser、iris、diabetes和glass四个标准数据集上比较了GEPKNN，KNN和C4.5等算法的分类性能。对每个数据集，我们随机抽取其中65%作为训练集，剩下的35%作为测试集。GEPKNN的參数设置汇总详见表1。

实验程序用java和Weka实现，实验平台为jdk1.6，pentium4 1.8GHZ处理器，512M内存，Windows xp操作系统。

表1 试验结果

■

三、总结

本文提出的GEPKNN算法较好地解决了为核KNN选择核函数及其参数的问题，实验结果表明GEPKNN算法是有效的。

参考文献：

[1]饶鲜，杨绍全，魏青，董春曦.核的最近邻算法及其仿真[J].系统工程与电子技术，2007，29（3）：470-471.

[2]李曲，蔡之华，蒋思伟，朱莉.基因表达式程序设计在预测中的应用研究[A].第五届全球智能控制与自动化大会[C].杭州：2004.