基于遺傳算法的全局優化檢索策略研究

（太原理工大學 計算機與軟件學院 太原 030024）

摘 要：案例檢索是基于案例推理(CBR)系統中的關鍵技術，也是實現智能挖掘系統的關鍵環節。為了能夠進一步提高案例檢索效率與準確性，傳統研究多是從案例屬性和案例庫的約減兩方面入手，但是沒有考慮案例屬性權重。提出了一種基于遺傳算法的全局優化案例檢索模型，該模型利用遺傳算法在搜索優化上的優勢，對案例庫、 屬性權重、KNN中的K值進行全局同步優化。最后，通過實驗驗證了該模型在檢索效率與準確性上優于傳統模型。

關鍵詞：K近鄰搜索算法; 遺傳算法; 案例檢索; 基于案例推理; 全局優化

中圖分類號：TP182文獻標志碼：A

文章編號：1001-3695(2009)05-1667-03

Strategy research of global optimization based on genetic algorithm

LI Haifang FAN Hailiang JIN Hui

(College of Computer Software Taiyuan University of Technology Taiyuan 030024 China)

Abstract:Case retrieval is the key technique in CBR，and it is also the most important step in realizing artificial mining system. To improve the efficiency and accuracy of case retrieval most traditional researches focus on attribute reduction and filter casebase but they do not take attribute weights and K of KNN into account. This paper proposed a newglobal optimization research technique based on genetic algorithm. This technique taking advantage of genetic algorithm can optimize casebase attribute weights and K of KNN algorithm synchronously. At last，experiments show that searching efficiency and accuracy under this technique are priorer than traditional technique in efficiency and accuracy.

Key words：KNN; genetic algorithm; case retrieval; CBR; global optimization

從大量數據中抽取出有價值的信息和運行規律的數據挖掘技術，無論是對商業經營還是工企決策，都有極其重要的經濟價值和理論意義。目前市場上已有多種適用商業模式的通用數據挖掘系統，但是這些數據挖掘系統由熟悉數據挖掘術語和數據分析技術的用戶自主去選擇需要的數據挖掘算法，通過模型對數據進行數據挖掘操作，這就使這些數據挖掘系統很難被那些不熟悉數據挖掘術語和數據分析技術的普通用戶所使用^[1]。為了改變這種局限性，很多研究從面向用戶的角度出發，將CBR技術引用到數據挖掘系統中，設計出多策略智能化數據挖掘系統，并且將這些系統運用于實際，在一定范圍內取得了比較大的成功。但是在這些智能化的多策略挖掘系統中，存在案例的屬性比較復雜、案例庫空間不斷動態增長的問題，這樣就會降低案例的檢索效率。如何提高檢索效率，快速準確地從案例庫中獲得人們所需的知識就成為了一個亟待解決的問題。

1 傳統案例檢索模型

面對以上問題的挑戰，傳統研究大部分是從對案例的屬性約簡和案例庫過濾兩方面進行。早在1976年Stearns提出了使用前向搜索法（sequential forward selection）來進行案例屬性的約簡，但是這種方法存在一定的局限性。于是在1989年Siedlecki與Sklanski提出了使用遺傳算法來進行案例屬性的約簡^[2]。注意到以上的方法都沒有考慮到案例屬性的權重，而案例的屬性只是在一定程度上反映某一特定對象是否應該具有某一屬性，真正反映屬性重要性的是屬性的權重。于是在1991年Kelly與Davis提出了使用遺傳算法來進行案例權重的優化，Shin與Han在1999年將此方法運用到公司債券評定系統，Chiu^[3]在2002年將同樣的方法運用在顧客分類系統中。在案例庫的過濾方面運用較多的方法有：Yan和Huang等人提出的神經網絡方法Babu，以及Murty的遺傳方法等^[1]，但是這些研究都是孤立地優化某一方面。如果能夠把以上參數結合起來進行多維同步優化，其搜索效率必然會得到很大的改善。多維優化主要有兩種思路，以結合基于遺傳算法的案例和屬性選擇優化模式為主，主要思想是在編碼時將信息分成了案例選擇、屬性選擇兩個模塊。采用二進制的編碼機制，隨機產生初始種群；采用案例檢索主算法充當適應度函數的優化過程。該算法于1999年由Kuncheva等人提出，2003年由Rozsypal Kubat對編碼方式和適應度函數等進行了優化并通過實驗證實了它的優越性，明顯地減少了案例的搜索空間。2006年Hyunchul Ahn等人把這種算法用在客戶分類系統中，進而在實際應用中檢驗了算法的優越性，并取得了一定的效果^[2]。還有一種基于遺傳算法的屬性權重和屬性選擇技術，但是在這種算法中權重的編碼采用浮點編碼，把屬性設計在某一區間隨機變化，造成了屬性的自學能力不強，不能體現案例權重的現實意義^[4，5]。

2 全局優化案例檢索模型

雖然上文提出了很多關于提高檢索效率的優化方法，但遺憾的是沒有一個能對案例屬性的權重、案例庫、KNN中的K值三方面進行全局優化。為了能夠在以上基礎上進一步提高案例檢索效率，同時又考慮到本模型所運用的方向自身屬性比較多，在屬性權重上的差異也比較大的特點，本文提出了一種基于遺傳算法的全局優化案例檢索模型(GOCBR)。該模型主要是將遺傳算法運用到案例檢索過程對案例庫、案例屬性的權重、KNN中的K值這三方面進行同步優化。最后將該模型運用到基于汽車業的多策略挖掘系統，選取了1 024個案例進行實驗，結果表明在案例檢索效率與準確性上都有明顯提高。

圖1是整個模型的檢索過程。基于遺傳算法優化的過程如圖2所示。

下面對這個流程的關鍵部分進行說明。

1)初始化

根據遺傳算法的步驟，首先應該產生一個用于發現最優化參數的初始化群體，群體中染色體的值是隨機的二進制編碼。但是為了能夠發現最優化的參數集合，應該設計染色體的結構，如圖3所示。

每一個染色體都有屬性的權重、案例選擇、K值全部的信息。每一個染色體的長度為3m+n+10 bit。這里m是屬性的數量；n是案例的數量。為了能夠更加準確地表示權重，將屬性的權重分為八個等級（0:無用，7:非常重要）。用三位來表示屬性的權重，權重的計算公式如下^[2]:

wi=xi/∑Ni=1xi

其中：wi是屬性i的屬性權重；M是全部屬性的數量；xi是屬性i相對重要性的二進制編碼。

由于案例的選擇只有選或不選兩種狀態，采取一位二進制編碼0表示沒有被選擇，1表示被選擇。N是全部案例的數量，參數K的值依據搜索空間的大小編碼。在本文研究中，搜索的空間為1 024(210)^[6]，編碼取十位。

2)確定適應度函數

經過上面的初始化后，系統就會根據初始化的參數由GA計算每個染色體的性能。染色體的性能計算是通過適應度函數來完成的。在研究中，主要的目標是產生提高搜索效率的最優參數集合，因此設定適應度函數如下^[4]:

fitness(ft)=1/n ∑ni=1 CRi(i=1，2，…，n)

ifPOi=AOiCRi=1 elseCRi=0

其中：n是測試數據集的大小；POi是第i個測試數據的預測輸出結果；AOi是第i個測試數據集的實際輸出結果;CRi是預測數據與實際輸出結果的匹配程度。如果POi=AOi，CRi=1；否則為0。

3)確定檢索算法中的相似度量算法

在測試數據庫中尋找相似案例，進行推理時檢索算法采用最常用的KNN算法，通常用公式:

similarity(T，X)=∑ni=1f(Ti，Xi)×wi

其中：T表示目標案例;X表示案例庫中的源案例;n表示每一個案例所包含的特征個數;i∈[1，n]；f是案例T和X中特征i的相似度函數;wi表示特征i的屬性權值。得到的相似度similarity越高，則表示匹配程度越好，對于不同類型的屬性值f采取不同的度量方法。

對于這些描述性的符號型屬性，本文將采用一票否決制的相似度度量方法。假設Xi和Ti分別是原案例X的i屬性和目標案例T中對應的屬性，且都為符號型。該屬性的相似度可以表示為

f(Ti，Xi)=1 如果Ti=Xi0 其他

數值型相似度的度量目前用得最多的相似度計算方法是歐氏距離。歐氏距離公式為

f(Ti，Xi)=∑ni=1(Xi-Ti)21/2

4)遺傳操作

在這個階段中，根據適應度函數進行遺傳操作，包括選擇、 變異、 交叉。為了避免在此操作中進入局部優化，引入一個長度為L的禁忌表，表中記錄了最近進行的L個移動，根據它必須重新定義遺傳操作算子^[7]。

a)選擇算子。選擇的目的是把優化的個體直接遺傳到下一代或通過配對交叉產生新的個體再遺傳到下一代。排序選擇機制是一種基于群體內各個個體之間的相對適應度設計的等級選擇機制。首先根據各個個體的適應度大小進行排序，然后基于所排序號按某種規則進行選擇。本文采用排序選擇機制進行操作。

b)交叉算子。設x是父代經過交叉產生的一個子代染色體。如果x的適應值大于父代群體適應值的平均值，則接受它進入下一代;否則，如果x不在禁忌表中，同樣接受x，如果屬于禁忌，那么選擇父代中最好的染色體進入到下一代。

c)變異算子。設x是一個最優解(染色體)，禁忌表的長度為L，用于存放最近發生變異的信息位的號碼。對x進行變異操作產生新的染色體x′，將變異信息位的號碼與禁忌表中的號碼進行比較。若在表中，屬于禁忌;若不在表中，且小于渴望水平，更新禁忌表，否則，如果x′的適應值大于渴望水平，接受它。

5）重復3)和4)直到滿足遺傳結束條件

當達到滿足條件時也就找到了滿意的參數。

6）驗證

有時候給的測試數據集合太理想，得到的參數集對測試數據集非常有效，但是卻不能確定其是否具有一定的通用性，因此將產生的參數集合運用到驗證數據集合來驗證其是否具有通用

性。

3 實驗

為了驗證本模式的優越性，本文采用三種不同的CBR檢索方法應用于同一個數據庫上:

a)基于KNN檢索的案例選擇的ICBR案例庫優化CBR系統;

b)帶有特征選擇的檢索算法，此特征選擇也采用了遺傳算法，簡稱為FCBR;

c)帶有案例和屬性的TRCBR。

這三種方法都是已經實驗證明在檢索優化算法中比較優秀的，而且都是基于GA優化的。這三種算法代表了三種情況，所以本文就選這三種具有代表性的CBR系統與本文的模型采用10Fold交叉驗證進行比較，從案例搜索空間和推理結果進行比較。

3.1 基于案例推理的數據挖掘算法搜索策略系統結構

基于案例推理的數據挖掘算法搜索策略的系統結構如圖4所示。

在實驗中，本文涉及的屬性包括了汽車方面和調查人的詳細信息，共選擇了11個主要屬性，如表1所示。

為了更好地確定系統參數，先把案例分成測試數據、實驗數據和驗證數據三部分。測試數據占60%，實驗數據占20%，驗證數據占20%。實驗中K值取1、3、5、9、10進行實驗。從結果中得到對推理結果的影響取3最為合適。在進行遺傳優化時初始種群200個，遺傳終止條件為20代，交叉概率為0.7，變異概率為0.1。

實驗運行參數優化對應表如表2所示。

3.2 實驗結果分析

結合表2和3可以看出，ICBR在選擇案例時沒有考慮到屬性的重要性，所以單純地約簡案例使得最優合適的算法也約掉了，在結果中正確率是87.384 3%；對于FCBR也是考慮比較片面；TRCBR相比來說是比較好的。這里也可以說明綜合考慮的好處。GOCBR在搜索空間和案例準確率上相對于其他都有明顯提高。

表3 檢索效率比較

比較項ICBRFCBRTRCBRGOCBR

正確數據1 5101 5441 5961 677

出錯數據2186113251

正確率/%87.384 389.351 992.361 197.048 6

4 結束語

本文針對CBR的相似性案例檢索進行了研究，充分考慮了檢索所涉及到的三個參數，即屬性權重、案例選擇和KNN中的K值，并將這三個方面結合起來，建立了一種新的同步優化檢索模型。該模型的優越性在實驗數據方面得到了驗證。但其在檢索過程中需要較多的時間與計算過程，應用于實際系統還需要進一步的改進。

參考文獻：

[1]李峰剛. 基于優化型案例推理的智能決策技術研究[D]. 合肥:合肥工業大學 2007.

[2]AHN H KIM K J HAN I. A casebased reasoning system with the twodimensional reduction technique for customer classification[J]. Expert Systems with Applications，2007 32(4):1011-1019.

[3]BEDDOE G R PETROVIC S. Selecting and weighting features using a genetic algorithm in a casebased reasoning approach to personnel rostering[J]. European Journal of Operational Research，2006，175(22):649-671.

[4]SHIN K S HAN I. Casebased reasoning supported by genetic algorithms for corporate bond rating[J]. Expert Systems with Applications，1999 16(2): 85-95.

[5]ROZSYPAL A，KUBAT M. Selecting representative examples and attributes by a genetic algorithm[J].

Intelligent Data Analysis，2003，7(4):291-304.

[6]AHN H KIM K. Using genetic algorithms to optimize nearest neighbors for data mining[J]. Annals of Operations Research 2008，163(1):5-18.

［7］黃繼鴻，雷戰波，李欣苗.基于遺傳禁忌算法的案例檢索策略[J]. 系統工程理論方法應用 2004，13(1):10-13.