吳曉明

摘 要：本文提出了一種新的核k近鄰分類算法（GEPKNN）。主要內(nèi)容是在基因表達(dá)式編程中，依靠GEP搜索復(fù)雜表達(dá)式空間方面的優(yōu)勢(shì)，為核KNN自動(dòng)構(gòu)造與數(shù)據(jù)相關(guān)的核函數(shù)，以減小人工選擇核函數(shù)的主觀性，達(dá)到提升核KNN分類性能的目的。該算法優(yōu)于傳統(tǒng)核KNN算法，結(jié)構(gòu)簡(jiǎn)單，分類速度快并且在高維空間上仍然保持較好的分類性能。

關(guān)鍵詞：核KNN算法；遺傳算子；基因表達(dá)式編程；核k近鄰分類器

核KNN的主要不足在于其分類性能對(duì)核函數(shù)比較敏感。為了降低選擇核函數(shù)時(shí)的不確定性，筆者提出了一種基于基因表達(dá)式編程的核KNN算法，簡(jiǎn)記為GEPKNN。算法的基本思路是利用GEP的函數(shù)空間搜索能力，為核KNN自動(dòng)構(gòu)造與訓(xùn)練數(shù)據(jù)相關(guān)的核函數(shù)。

一、GEPKNN算法

1.核KNN算法

核KNN與KNN的主要區(qū)別在于使用了不同的距離度量，如果將KNN所用的X上的歐氏距離替換為核距離，就得到了一個(gè)核KNN分類器。

2.遺傳算子

GEP的大部分遺傳算子可以不加改變地應(yīng)用到GEPKNN中。需要注意的是，應(yīng)用遺傳算子于染色體時(shí)，必須保持EDOM和PDOM的邊界，防止產(chǎn)生無(wú)效的后代，還要引入兩個(gè)特殊的算子用于進(jìn)化PDOM域：其中PDInversion算子轉(zhuǎn)置PDOM中的隨機(jī)子串，而CPMutation改變常數(shù)池中隨機(jī)位置上的常數(shù)。

3.適應(yīng)度函數(shù)

為了縮短訓(xùn)練時(shí)間，我們?cè)谒惴ㄖ薪y(tǒng)一取k=3。

求個(gè)體適應(yīng)度的具體過(guò)程是：個(gè)體I的兩個(gè)域（表達(dá)式域和參數(shù)域）解碼后組裝成核函數(shù)k，把k載入核KNN后就可以在其上作k折交叉驗(yàn)證了。假設(shè)經(jīng)過(guò)k折交叉驗(yàn)證得到的平均錯(cuò)誤率是e，令個(gè)體的適應(yīng)度為：

fitness=1000*（1-e）

求適應(yīng)度函數(shù)時(shí)，需要頻繁計(jì)算核距離，因此，縮短計(jì)算核距離的時(shí)間是提高算法效率的一個(gè)有效手段?；诖?，我們提出了下面的定理1，該定理很容易用數(shù)學(xué)歸納法證明。

定理1（求核距離的快速方法）令K={k1，k2，k3}，其中k1、k2、k3是上面提到的3個(gè)常用核函數(shù)，S是K上的加法、乘法、指數(shù)運(yùn)算等運(yùn)算符的集合。k是由K和S中元素構(gòu)成的任一符合語(yǔ)法規(guī)范的算術(shù)表達(dá)式，由定理2可知k是核函數(shù)。如果原空間X中的內(nèi)積進(jìn)行規(guī)范化，則存在實(shí)數(shù)SPID，對(duì)于X中任意點(diǎn)x都有k（x，x）=SPID。

此時(shí)，核距離的公式可以修改為：

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

上式計(jì)算核距離可以使求適應(yīng)度的時(shí)間縮短約2/3。

4.GEPKNN算法

綜合上面的分析，GEPKNN的偽碼如下：

算法（GEPKNN）

輸入T//訓(xùn)練集

輸出核KNN分類器

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

t=0

while（t

p（t+1）=GEP（p（t））//產(chǎn)生下代種群

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

k=decode（I）//k是核函數(shù)

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

//用核函數(shù)k構(gòu)造核KNN，在訓(xùn)練集上

//作交叉驗(yàn)證

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

if（bestFitness>threshold）

Break}

k=decode（p（t）中的最好個(gè)體I）

Return核KNN（k）

二、實(shí)驗(yàn)結(jié)果

為驗(yàn)證GEPKNN算法的有效性，我們?cè)赨CI的wisconsin-breast-canser、iris、diabetes和glass四個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集上比較了GEPKNN，KNN和C4.5等算法的分類性能。對(duì)每個(gè)數(shù)據(jù)集，我們隨機(jī)抽取其中65%作為訓(xùn)練集，剩下的35%作為測(cè)試集。GEPKNN的參數(shù)設(shè)置匯總詳見(jiàn)表1。

實(shí)驗(yàn)程序用java和Weka實(shí)現(xiàn)，實(shí)驗(yàn)平臺(tái)為jdk1.6，pentium4 1.8GHZ處理器，512M內(nèi)存，Windows xp操作系統(tǒng)。

表1 試驗(yàn)結(jié)果

■

三、總結(jié)

本文提出的GEPKNN算法較好地解決了為核KNN選擇核函數(shù)及其參數(shù)的問(wèn)題，實(shí)驗(yàn)結(jié)果表明GEPKNN算法是有效的。

參考文獻(xiàn)：

[1]饒鮮，楊紹全，魏青，董春曦.核的最近鄰算法及其仿真[J].系統(tǒng)工程與電子技術(shù)，2007，29（3）：470-471.

[2]李曲，蔡之華，蔣思偉，朱莉.基因表達(dá)式程序設(shè)計(jì)在預(yù)測(cè)中的應(yīng)用研究[A].第五屆全球智能控制與自動(dòng)化大會(huì)[C].杭州：2004.