核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.