吳曉明

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

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

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

一、GEPKNN算法

1.核KNN算法

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

2.遺傳算子

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

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

為了縮短訓(xùn)練時間，我們在算法中統(tǒng)一取k=3。

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

fitness=1000*（1-e）

求適應(yīng)度函數(shù)時，需要頻繁計算核距離，因此，縮短計算核距離的時間是提高算法效率的一個有效手段?；诖耍覀兲岢隽讼旅娴亩ɡ?，該定理很容易用數(shù)學(xué)歸納法證明。

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

此時，核距離的公式可以修改為：

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

上式計算核距離可以使求適應(yīng)度的時間縮短約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)練集上

//作交叉驗證

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

if（bestFitness>threshold）

Break}

k=decode（p（t）中的最好個體I）

Return核KNN（k）

二、實驗結(jié)果

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

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

表1 試驗結(jié)果

■

三、總結(jié)

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

參考文獻(xiàn)：

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

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