一種改進(jìn)的KNN案例推理檢索算法*

孫寶貴，車文剛，廖江福

(1.昆明理工大學(xué)信息工程與自動(dòng)化學(xué)院，云南 昆明650500；2.昆明理工大學(xué)云南省計(jì)算機(jī)技術(shù)應(yīng)用重點(diǎn)實(shí)驗(yàn)室，云南 昆明650500)

1 引言

案例推理CBR(Case-Based Reasoning)是人工智能領(lǐng)域中一種基于現(xiàn)有知識(shí)的問題求解與學(xué)習(xí)方法，其通過重用或修改與目標(biāo)案例相似性高的歷史案例解決問題[1]。目前，對(duì)CBR的應(yīng)用與研究非常廣泛[2 -5]，應(yīng)用最為廣泛的CBR模型是Aamodt等[6]提出的“4R循環(huán)”，包括以下4個(gè)環(huán)節(jié)：(1)案例檢索(Retrieve)：從案例庫中檢索與目標(biāo)案例相似性最高的一個(gè)或多個(gè)相似源案例；(2)案例重用(Reuse)：將檢索得到的相似源案例作為建議解；(3)案例修正(Revise)：對(duì)建議解進(jìn)行評(píng)估。若評(píng)估合格，則不需要修正；若評(píng)估不合格，則對(duì)建議解進(jìn)行相應(yīng)的修正；(4)案例保存(Retain)：將目標(biāo)案例及其解決方案作為新案例存儲(chǔ)到案例庫中。

案例檢索是案例推理的中心環(huán)節(jié)，因此，檢索算法的性能直接影響案例推理檢索結(jié)果的精度和執(zhí)行時(shí)間[7]。目前常用的案例推理檢索算法有：知識(shí)引導(dǎo)法(Knowledge-Guided)、歸納索引法(Induce Indexing)和K-最近鄰KNN(K-Nearest Neighbor)算法等。其中，由于K-最近鄰算法通過歐氏距離實(shí)現(xiàn)相似性計(jì)算，所以被廣泛應(yīng)用于案例推理。

但是，傳統(tǒng)的KNN算法在檢索案例時(shí)存在2處缺陷：(1)計(jì)算量大，效率低。傳統(tǒng)KNN算法需要對(duì)案例庫中所有的案例進(jìn)行相似度計(jì)算。因此，對(duì)于海量案例庫而言，計(jì)算量巨大，會(huì)降低效率。(2)近鄰K值影響最終的輸出結(jié)果。當(dāng)K值較小時(shí)，容易發(fā)生過擬合；當(dāng)K值較大時(shí)，會(huì)將噪聲點(diǎn)劃分為相似源案例，導(dǎo)致輸出結(jié)果的誤差增大，質(zhì)量下降[8]。

目前對(duì)于改善傳統(tǒng)KNN算法性能、提高案例推理檢索效率的研究頗多。張春曉等[9]提出了一種通過遺傳算法、內(nèi)省學(xué)習(xí)和群決策思想改進(jìn)的CBR分類方法。但是，該方法需要多次迭代實(shí)驗(yàn)，才能確定最佳匹配屬性與不匹配屬性的閾值。嚴(yán)愛軍等[10]提出了一種基于可信度閾值優(yōu)化的CBR評(píng)價(jià)分類方法，以改善CBR分類器性能。然而其存在一個(gè)問題：可信度閾值優(yōu)化方法能否劃分出合理的可信集與不可信集。樊瑞宣等[11]提出了一種個(gè)性化K近鄰的檢索算法，其每個(gè)樣本的近鄰K值通過算法自動(dòng)確定。但是，文獻(xiàn)[11]算法需要對(duì)每個(gè)樣本優(yōu)化近鄰K值，因此時(shí)間復(fù)雜度相對(duì)較高。萬碧君等[12]提出了一種改進(jìn)K最近鄰回歸建模算法。文獻(xiàn)[12]中改進(jìn)的算法雖然提高了檢索效率，彌補(bǔ)了傳統(tǒng)KNN算法的2個(gè)缺陷，但是其采用的K-Means和粒子群優(yōu)化算法都存在易陷入局部最優(yōu)解的問題，且粒子群優(yōu)化算法不易收斂。

針對(duì)傳統(tǒng)KNN檢索算法的2處缺陷及其現(xiàn)有研究的不足，本文提出一種改進(jìn)的KNN案例推理檢索算法(SAGA-FCM-GAPSO-KNN_Opt_Stra)：以遺傳模擬退火-模糊C均值聚類SAGA-FCM(Simulated Annealing Genetic Algorithm-Fuzzy C-Means)算法對(duì)案例庫聚類；利用改進(jìn)的遺傳-粒子群優(yōu)化混合GA-PSO(Genetic Algorithm-Particle Swarm Optimization)算法優(yōu)化各類簇的近鄰K值；然后，提出最優(yōu)原則的檢索策略，確定目標(biāo)案例的檢索子案例庫及近鄰K值;最后，利用Mackey-Glass混沌時(shí)間序列數(shù)據(jù)驗(yàn)證改進(jìn)的KNN案例推理檢索算法的有效性。

2 相關(guān)內(nèi)容

2.1 CBR問題描述

一般地，案例在案例庫中采用二元組形式存儲(chǔ)：

Ck={Xk;yk},k=1,2,3,…,n

其中，n為案例庫Ck中的源案例總數(shù)，yk為第k條源案例的類型，Xk為第k條源案例的問題描述，可以表示為：

Xk={x1k,x2k,x3k,…,xik,…,xmk},

i=1，2，3,…,m

其中，m為案例的特征屬性總數(shù),xik為第k條源案例的第i個(gè)特征屬性。

以線性問題類型的案例推理為例，Ck={x1k,x2k,x3k,…,xmk;yk} 。xmk與yk都是實(shí)數(shù)，且m個(gè)特征屬性間接地決定輸出值。

2.2 K最近鄰回歸算法

K最近鄰算法KNN是1967年由Cover和Hart[13]提出的一種基本分類與回歸算法，是最簡(jiǎn)單的機(jī)器學(xué)習(xí)算法之一。相較于其他常用的檢索算法，KNN是基于距離的相似性度量算法，沒有檢索過程繁雜以及對(duì)數(shù)據(jù)的歸納整理操作。

一般地，在案例推理中應(yīng)用KNN算法，有以下3個(gè)步驟：

步驟1計(jì)算目標(biāo)案例與案例庫中所有案例的距離-特征項(xiàng)距離和；

步驟2從案例庫中選擇K個(gè)距離最小的案例作為相似源案例；

步驟3利用K個(gè)相似源案例預(yù)測(cè)輸出最終結(jié)果。

一般地，KNN算法采取求K個(gè)相似源案例的輸出值的平均值或加權(quán)平均值作為預(yù)測(cè)結(jié)果：

平均值如式(1)所示：

(1)

加權(quán)平均值如式(2)所示：

(2)

其中,ωi為yi的權(quán)重。

3 改進(jìn)的KNN案例推理檢索算法

針對(duì)聚類與近鄰K值問題，本文利用遺傳模擬退火-模糊C均值聚類算法實(shí)現(xiàn)案例庫聚類，通過改進(jìn)的遺傳-粒子群優(yōu)化混合算法優(yōu)化每個(gè)類簇的近鄰K值。

3.1 基于遺傳模擬退火-模糊C均值聚類算法的聚類

將聚類思想應(yīng)用到案例推理的檢索過程，有利于減少檢索時(shí)間，提高檢索質(zhì)量。常用的聚類算法有：K-Means聚類算法、模糊C均值聚類算法、支持向量機(jī)算法、神經(jīng)網(wǎng)絡(luò)和遺傳模糊C均值聚類算法等。

相較于K-Means聚類算法，模糊C均值聚類算法是一種基于目標(biāo)函數(shù)的模糊聚類算法。其在K-Means聚類算法的基礎(chǔ)上增加了隸屬度函數(shù)，用來描述樣本與某一類簇的相似程度，使得樣本的隸屬度可以為[0,1]的實(shí)數(shù)?；诖耍僭O(shè)一個(gè)數(shù)據(jù)集X有n個(gè)樣本，聚類數(shù)為cn。其目標(biāo)函數(shù)為：

(3)

隸屬度函數(shù)uij如式(4)所示：

(4)

類簇中心cj如式(5)所示：

(5)

但是，模糊C均值聚類算法本質(zhì)上依然是局部搜索優(yōu)化算法。與K-Means算法一樣，若初始值選擇不當(dāng)，就會(huì)收斂到局部最優(yōu)解。

因此，本文采用遺傳模擬退火-模糊C均值聚類SAGA-FCM算法實(shí)現(xiàn)案例庫聚類。遺傳模擬退火算法作為一種改進(jìn)的優(yōu)化算法[14]，在優(yōu)化算法前期，初始化生成的種群中個(gè)體的差異較大，即個(gè)體的適應(yīng)度值相差較大，因此會(huì)存在部分較為優(yōu)秀的個(gè)體，而此時(shí)模擬退火算法中的溫度值較高，有較大的概率接受較劣個(gè)體成為新解，以避免整個(gè)種群較早地收斂于局部?jī)?yōu)秀個(gè)體，出現(xiàn)陷入局部最優(yōu)解的問題；在優(yōu)化算法后期，整個(gè)種群中個(gè)體的適應(yīng)度值基本相同。此時(shí)溫度值較低，模擬退火算法可以適當(dāng)拉伸遺傳算法中種群個(gè)體的適應(yīng)度值，擴(kuò)大種群個(gè)體間適應(yīng)度值的差異，提升優(yōu)秀個(gè)體在后期迭代過程中的優(yōu)勢(shì)，克服了遺傳算法在種群后期進(jìn)化時(shí)停滯不前的缺點(diǎn)。因此，遺傳模擬退火算法可以提高全局與局部的搜索能力與效率，能夠解決FCM算法或K-Means算法因初始值選擇不當(dāng)，導(dǎo)致算法陷入局部最優(yōu)問題。所以，遺傳模擬退火-模糊C均值聚類(SAGA-FCM)算法可以更加穩(wěn)定有效地收斂到全局最優(yōu)解,具體步驟如算法1所示。

算法1遺傳模擬退火-模糊C均值聚類算法

輸入：數(shù)據(jù)集X，類簇個(gè)數(shù)cn。

輸出：cn個(gè)不同簇間疏散、同簇內(nèi)密集的類簇。

步驟1初始化種群控制參數(shù)：種群規(guī)模pop_size,最大進(jìn)化次數(shù)max_Iterate，交叉概率Pc，變異概率Pm，退火初始溫度Tstart，冷卻系數(shù)J，終止溫度Tend。

步驟2隨機(jī)初始化cn個(gè)類簇中心，并生成初始種群Chrom。對(duì)每個(gè)類簇中心用式(4)計(jì)算各樣本的隸屬度，以及用式(3)計(jì)算每個(gè)個(gè)體的適應(yīng)度值Fi,其中i=1，2，…，pop_size。

步驟3設(shè)置進(jìn)化迭代參數(shù)Iterate=0。

步驟4對(duì)種群Chrom進(jìn)行選擇、交叉和變異等遺傳操作，對(duì)新產(chǎn)生的個(gè)體用式(4)和式(5)計(jì)算各樣本的隸屬度以及cn個(gè)類簇中心，并用式(3)計(jì)算每一個(gè)體的適應(yīng)度值fi。若fi>Fi，則用新個(gè)體替換舊個(gè)體；否則，以概率P=exp((Fi-fi)Ti)接受新個(gè)體，拋棄舊個(gè)體,其中，Ti為模擬退火時(shí)，每次冷卻的溫度。

步驟5令I(lǐng)terate=Iterate+1,若Iterate

步驟6令Ti=J*Ti-1,若Ti>Tend，則轉(zhuǎn)至步驟3；否則，輸出最優(yōu)結(jié)果。

由此，得到cn個(gè)不同簇間疏散、同簇內(nèi)密集的類簇。

3.2 改進(jìn)的遺傳-粒子群優(yōu)化混合算法優(yōu)化近鄰K值

一般地，使用交叉驗(yàn)證法或者優(yōu)化算法確定近鄰K值，比如遺傳算法、粒子群優(yōu)化算法和灰狼優(yōu)化算法。但是，遺傳算法容易出現(xiàn)早熟收斂的情況；粒子群優(yōu)化算法與灰狼優(yōu)化算法都存在局部最優(yōu)解且不易收斂的缺點(diǎn)。因此，本文采用改進(jìn)的遺傳-粒子群優(yōu)化混合GA-PSO算法，可以有效地避免局部最優(yōu)以及早熟收斂的缺陷。具體算法步驟如算法2所示。

算法2遺傳-粒子群優(yōu)化混合算法

輸入：cn個(gè)類簇。

輸出：cn個(gè)類簇的近鄰K值。

步驟1初始化粒子群并對(duì)其編碼，本文采用真實(shí)值整數(shù)編碼,如：02，12，36。

步驟2計(jì)算各類簇中每個(gè)案例與同類簇中其他案例的距離，并將距離值按升序排序。

步驟3通過適應(yīng)度函數(shù)計(jì)算每個(gè)粒子的適應(yīng)度值。其中，適應(yīng)度值為當(dāng)前粒子值下，預(yù)測(cè)輸出值的均方誤差值，如式(6)所示：

(6)

其中,N為類簇內(nèi)案例的個(gè)數(shù)；yj,real為第j個(gè)案例輸出值的真實(shí)值；yj,pre為第j個(gè)案例輸出值的預(yù)測(cè)值，如式(7)所示：

(7)

其中,yi為升序排序后前K個(gè)案例輸出值的真實(shí)值。d為當(dāng)前粒子數(shù)，表示某案例在類簇中最相似的d個(gè)案例，即步驟2中升序排序后的前d個(gè)案例。

步驟4根據(jù)粒子適應(yīng)度值更新粒子最優(yōu)值Pbest和群體最優(yōu)值Gbest。

步驟5將群體最優(yōu)值Gbest十位上的數(shù)值對(duì)應(yīng)交叉到粒子值的十位上，若新粒子的適應(yīng)度值優(yōu)于未交叉粒子的適應(yīng)度值，則更新粒子及其適應(yīng)度值。例如：群體最優(yōu)值Gbest=16，當(dāng)前粒子individual=32。交叉后的粒子new_individual=12。

步驟6對(duì)粒子上的個(gè)位值、十位值進(jìn)行變異，若新粒子的適應(yīng)度值優(yōu)于未變異粒子的適應(yīng)度值，則更新粒子及其適應(yīng)度值。

步驟7循環(huán)執(zhí)行步驟3～步驟5，直到滿足結(jié)束迭代的條件。

步驟8輸出cn個(gè)類簇的近鄰K值。

3.3 最優(yōu)原則檢索策略

本文采用平均值作為預(yù)測(cè)結(jié)果。因此，當(dāng)聚類以及優(yōu)化近鄰K值的工作完成后，需要確定目標(biāo)案例的檢索子案例庫及其近鄰K值，才能開始檢索案例并計(jì)算平均值。

一般地，確定目標(biāo)案例的檢索子案例庫步驟如下所示:

步驟1通過式(8)計(jì)算目標(biāo)案例與各類簇中心的距離distj：

(8)

其中，m為案例中特征屬性的個(gè)數(shù)；h′i為目標(biāo)案例的第i個(gè)特征屬性的值；vj,i為類簇j中心的第i個(gè)特征屬性的值。

步驟2根據(jù)式(9)確定最小值距離Min:

Min=min(dist1,dist2,…,distcn)

(9)

其中,cn為類簇個(gè)數(shù),distcn為第cn個(gè)類簇的類簇中心與目標(biāo)案例的距離。

步驟3依據(jù)最小值Min找到相應(yīng)的類簇，將該類簇作為目標(biāo)案例的檢索子案例庫，并確定其近鄰K值。

但是，上述方法可能存在一個(gè)現(xiàn)象：除卻最小距離Min外，個(gè)別目標(biāo)案例與剩余類簇中心的距離中還存在幾乎等于最小距離Min的值。這說明存在此現(xiàn)象的目標(biāo)案例恰好處于2個(gè)類簇的邊界，且距離2個(gè)類簇中心的距離幾乎相等。

因此，上述方法在確定此類型目標(biāo)案例的檢索案例庫時(shí)，會(huì)強(qiáng)制剔除掉較相似的類簇，將其劃分到最相似的類簇中。這會(huì)導(dǎo)致此類型目標(biāo)案例損失部分相似歷史案例，使其檢索案例庫減小。

針對(duì)上述現(xiàn)象，本文提出一種最優(yōu)原則的檢索策略。最優(yōu)原則檢索策略的具體步驟如下所示：

步驟1通過式(8)計(jì)算目標(biāo)案例與各類簇中心的距離distj；

步驟2將各個(gè)距離distj按升序排列成(dist1,dist2,…,distcn)，并通過式(10)計(jì)算Dist:

Dist=dist2-dist1

(10)

步驟3通過判斷Dist與閾值的大小，確定dist2對(duì)應(yīng)的子類簇是否歸并到目標(biāo)案例的檢索子案例庫；

步驟4如果Dist大于閾值，目標(biāo)案例的檢索子案例庫為dist1對(duì)應(yīng)的子類簇，其近鄰K值為該類簇的近鄰K值；

步驟5如果Dist小于或等于閾值，目標(biāo)案例的檢索子案例庫為dist1、dist2對(duì)應(yīng)的子類簇，其近鄰K值為2個(gè)類簇近鄰K值的平均值。

根據(jù)上述步驟可得到各目標(biāo)案例的檢索案例庫和近鄰K值。

3.4 算法流程

本文利用遺傳模擬退火-模糊C均值聚類算法對(duì)案例庫進(jìn)行有效分類，然后通過改進(jìn)的遺傳-粒子群優(yōu)化混合算法優(yōu)化近鄰K值，最后根據(jù)提出的最優(yōu)原則檢索策略，確定檢索子案例庫及其近鄰K值，預(yù)測(cè)輸出結(jié)果。具體的檢索流程如圖1所示。

Figure 1 Flow chart of the improved KNN retrieval algorithm of case-based reasoning proposed in this paper圖1 本文改進(jìn)的KNN案例推理檢索算法的流程圖

4 實(shí)驗(yàn)及結(jié)果分析

4.1 實(shí)驗(yàn)方案

當(dāng)φ=17時(shí)，上述微分方程呈現(xiàn)混沌特性。本文仿真取φ=30，通過Runge-Kutta方法生成20 000個(gè)數(shù)據(jù)。去掉前5 000個(gè)暫態(tài)點(diǎn)，從剩下的點(diǎn)中選取1 000個(gè)數(shù)據(jù)點(diǎn)。其中，前800個(gè)數(shù)據(jù)點(diǎn)組成訓(xùn)練集，后200個(gè)數(shù)據(jù)點(diǎn)組成測(cè)試集。對(duì)選取的數(shù)據(jù)點(diǎn)進(jìn)行異構(gòu)重組，得出時(shí)延為1，嵌入維為4[15]，即一個(gè)案例由5個(gè)數(shù)據(jù)點(diǎn)組成，前4個(gè)數(shù)據(jù)點(diǎn)決定后1個(gè)數(shù)據(jù)點(diǎn)，如圖2所示。

Figure 2 Heterogeneous reorganization of data sets to form case base圖2 數(shù)據(jù)集異構(gòu)重組形成案例庫

本文進(jìn)行了2組實(shí)驗(yàn)：

實(shí)驗(yàn)1不考慮目標(biāo)案例的邊界問題，即未采用最優(yōu)原則檢索策略，比較本文提出的檢索算法與其他4種檢索算法的預(yù)測(cè)結(jié)果，以驗(yàn)證本文提出的檢索算法在未采用最優(yōu)原則檢索策略時(shí)具有良好的預(yù)測(cè)能力。

實(shí)驗(yàn)2考慮目標(biāo)案例的邊界問題，比較結(jié)合最優(yōu)原則檢索策略前后，本文提出的檢索算法的預(yù)測(cè)結(jié)果，驗(yàn)證最優(yōu)原則檢索策略的有效性。

評(píng)價(jià)2組實(shí)驗(yàn)預(yù)測(cè)結(jié)果的指標(biāo)采用均方誤差值MSE(Mean Squared Error)和平均絕對(duì)百分誤差MAPE(Mean Absolute Percentage Error)。

以下為本文采用的5種檢索算法：

(1)傳統(tǒng)KNN檢索算法(未采用最優(yōu)原則檢索策略)，記為KNN；

(2)基于模糊C均值聚類算法和粒子群優(yōu)化算法改進(jìn)的KNN檢索算法(未采用最優(yōu)原則檢索策略)，記為FCM-PSO-KNN；

(3)基于遺傳模擬退火-模糊C均值聚類算法和粒子群優(yōu)化算法改進(jìn)的KNN檢索算法(未采用最優(yōu)原則檢索策略)，記為SAGA-FCM-PSO-KNN；

(4)基于灰狼-支持向量機(jī)算法和遺傳-粒子群優(yōu)化混合算法改進(jìn)的KNN檢索算法(未采用最優(yōu)原則檢索策略)，記為GWOSVM-GAPSO-KNN；

(5)基于遺傳模擬退火-模糊C均值聚類算法和遺傳-粒子群優(yōu)化混合算法改進(jìn)的KNN檢索算法(未采用最優(yōu)原則檢索策略)，記為SAGA-FCM-GAPSO-KNN；

(6)本文提出的檢索算法(采用最優(yōu)原則檢索策略)，記為SAGA-FCM-GAPSO-KNN_Opt_Stra。

4.2 參數(shù)設(shè)置

對(duì)于聚類及優(yōu)化近鄰K值的算法，有以下要求：模擬退火算法與粒子群優(yōu)化算法要保證局部搜索能力，且收斂速度不宜太慢；遺傳算法需保證全局尋優(yōu)能力等。本文提到的算法的參數(shù)設(shè)置如表1所示。

Table 1 Parameter setting of each algorithm表1 各算法的參數(shù)設(shè)置

Figure 4 Partial figure of prediction results by 5 retrieval algorithms圖4 5種檢索算法預(yù)測(cè)結(jié)果的局部圖

4.3 聚類有效性評(píng)價(jià)指標(biāo)

本文采用Davies-Bouldin指標(biāo)DBI(Davies Bouldin Index)對(duì)聚類的最佳類簇?cái)?shù)進(jìn)行評(píng)價(jià)，其定義如式(11)所示：

(11)

(12)

(13)

其中，xi表示類簇C中第i個(gè)樣本的值，|C|表示類簇C中樣本的個(gè)數(shù)；ci表示第i個(gè)類簇；avg(C)表示類簇C的類內(nèi)樣本的平均距離；u為類簇C的中心點(diǎn)。

DBI通過計(jì)算任意2類簇的類內(nèi)平均距離之和除以2類簇中心距離，最后求最大值。DBI越小意味著類簇內(nèi)距離越小，類簇間距離越大，聚類效果越好。

4.4 實(shí)驗(yàn)結(jié)果及分析

(1)不考慮目標(biāo)案例邊界問題，比較5種檢索算法的預(yù)測(cè)結(jié)果。

通過Davies-Bouldin評(píng)價(jià)指標(biāo)確定最佳仿真類簇個(gè)數(shù)為4。4種改進(jìn)的KNN檢索算法對(duì)訓(xùn)練集聚類，其結(jié)果為：158*5,170*5,200*5,266*5。相應(yīng)的近鄰K值為：11,14,10,19。傳統(tǒng)KNN的近鄰K值為訓(xùn)練集數(shù)目的平方根，即仿真數(shù)據(jù)取26。5種檢索算法仿真結(jié)果如圖3和圖4所示。

Figure 3 Comparison of prediction results of 5 retrieval algorithms圖3 5種檢索算法的預(yù)測(cè)結(jié)果對(duì)比圖

圖3和圖4能夠具體展現(xiàn)各檢索算法預(yù)測(cè)結(jié)果的擬合情況，其中 SAGA-FCM-GAPSO-KNN檢索算法具有良好的擬合效果。擬合效果最差的是傳統(tǒng)KNN檢測(cè)算法，可以看出大部分案例的預(yù)測(cè)值與真實(shí)值有一定的差距。4種改進(jìn)的檢索算法中，GWOSVM-GAPSO-KNN算法預(yù)測(cè)結(jié)果波動(dòng)性較大，擬合效果相對(duì)較差。

由表2可知，5種檢索算法中，MSE、MAPE最小的是SAGA-FCM-GAPSO-KNN算法，其次是SAGA-FCM-PSO-KNN算法，最差的是傳統(tǒng)的KNN算法。在改進(jìn)的4種算法中，預(yù)測(cè)效果最差的為GWOSVM-GAPSO-KNN算法。通過比較FCM-PSO-KNN與SAGA-FCM-PSO-KNN以及GWOSVM-GAPSO-KNN與SAGA-FCM-GAPSO-KNN的MSE和MAPE發(fā)現(xiàn)：在優(yōu)化近鄰K值算法相同的情況下，SAGA-FCM聚類算法效果最好，說明SAGA算法可以有效地解決FCM算法易陷入局部最優(yōu)的問題；比較SAGA-FCM-PSO-KNN與SAGA-FCM-GAPSO-KNN的MSE發(fā)現(xiàn)：在聚類算法相同的情況下，GAPSO算法優(yōu)化近鄰K值的效果最佳。因此，SAGA-FCM-GAPSO-KNN算法在檢索案例時(shí)預(yù)測(cè)結(jié)果最好。

Table 2 Evaluation index of prediction results of 5 retrieval algorithms表2 5種檢索算法預(yù)測(cè)結(jié)果的評(píng)價(jià)指標(biāo)

從圖4可看出，5種檢索算法對(duì)案例6～案例12、案例50～案例55、案例106～案例110、案例127～案例131、案例184～案例190預(yù)測(cè)的結(jié)果皆存在明顯的誤差。通過分析數(shù)據(jù)發(fā)現(xiàn)：上述目標(biāo)案例與4個(gè)類簇中心的距離中，次小距離值與最小距離值非常接近。因此可以驗(yàn)證這些目標(biāo)案例存在邊界問題。上述部分目標(biāo)案例與4個(gè)類簇中心的距離，如表3所示。

由表3可知：上述目標(biāo)案例與4個(gè)類簇中心的距離按照升序排序后，前2個(gè)最小距離的最小為0.003，最大為0.099，因此，本文提出的最優(yōu)原則檢索策略中的閾值取為0.1。下節(jié)實(shí)驗(yàn)考慮目標(biāo)案例的邊界問題，比較采用最優(yōu)原則檢索策略前后本文檢索算法的預(yù)測(cè)結(jié)果。

Table 3 Distance between some target cases and the centers of 4 clusters(SAGA-FCM-GAPSO-KNN)表3 部分目標(biāo)案例與4個(gè)類簇中心的距離(SAGA-FCM-GAPSO-KNN算法)

(2)比較SAGA-FCM-GAPSO-KNN與SAGA-FCM-GAPSO-KNN_Opt_Stra的預(yù)測(cè)結(jié)果。

通過上文的對(duì)比實(shí)驗(yàn)可知：不考慮目標(biāo)案例邊界問題的情況下，相較于其他檢索算法，SAGA-FCM-GAPSO-KNN算法預(yù)測(cè)結(jié)果精度最高?；诖?，本節(jié)實(shí)驗(yàn)將在SAGA-FCM-GAPSO-KNN算法基礎(chǔ)上，采用最優(yōu)原則檢索策略，比較SAGA-FCM-GAPSO-KNN與SAGA-FCM-GAPSO-KNN_Opt_Stra的預(yù)測(cè)結(jié)果。采用最優(yōu)原則檢索策略后，上述目標(biāo)案例的預(yù)測(cè)結(jié)果如表4所示。

由表4可知，相較于SAGA-FCM-GAPSO-KNN，采用最優(yōu)原則策略后，SAGA-FCM-GAPSO-KNN_Opt_Stra算法有效解決了目標(biāo)案例的邊界問題，使目標(biāo)案例的檢索子案例庫擴(kuò)大，預(yù)測(cè)結(jié)果更接近真實(shí)值。雖然存在極個(gè)別預(yù)測(cè)結(jié)果不是最佳的情況(案例108、案例109、案例188)，但相較其他算法，SAGA-FCM-GAPSO-KNN_Opt_Stra整體預(yù)測(cè)效果最佳。

SAGA-FCM-GAPSO-KNN與SAGA-FCM-GAPSO-KNN_Opt_Stra算法對(duì)上述目標(biāo)案例預(yù)測(cè)的結(jié)果如圖5所示，對(duì)整體目標(biāo)案例預(yù)測(cè)的結(jié)果如圖6所示。

從圖5可直觀看出，采用最優(yōu)原則檢索策略后，SAGA-FCM-GAPSO-KNN_Opt_Stra算法對(duì)200個(gè)目標(biāo)案例進(jìn)行預(yù)測(cè)時(shí)，顯著地減小了因目標(biāo)案例的邊界問題而導(dǎo)致的誤差，驗(yàn)證了本文提出的最優(yōu)原則檢索策略的有效性，改善了預(yù)測(cè)結(jié)果和整體的擬合效果。如圖6所示。

Table 4 Prediction results of some target cases by each algorithm 表4 各算法對(duì)部分目標(biāo)案例的預(yù)測(cè)結(jié)果

Figure 5 Partial figure of prediction results by the retrieval algorithm proposed in this paper圖5 本文檢索算法預(yù)測(cè)結(jié)果的局部圖

Figure 6 Prediction results of the retrieval algorithm proposed in this paper圖6 本文檢索算法的預(yù)測(cè)結(jié)果

由表5可得，相較于KNN算法，SAGA-FCM-GAPSO-KNN_Opt_Stra算法對(duì)200個(gè)目標(biāo)案例仿真預(yù)測(cè)結(jié)果的MSE、MAPE值分別提高了62.7%和44.7%。相較于SAGA-FCM-GAPSO-KNN算法，SAGA-FCM-GAPSO-KNN_Opt_Stra算法預(yù)測(cè)結(jié)果的MSE、MAPE值分別提高了18.9%和8.9%。因此，SAGA-FCM-GAPSO-KNN_Opt_Stra算法可以提高線性問題預(yù)測(cè)結(jié)果的質(zhì)量。

Table 5 Evaluation index of the prediction result of each retrieval algorithm 表5 各檢索算法預(yù)測(cè)結(jié)果的評(píng)價(jià)指標(biāo)

5 結(jié)束語

案例推理的中心環(huán)節(jié)是案例檢索。對(duì)于海量案例庫，在處理線性問題時(shí)，傳統(tǒng)的KNN檢索算法需要對(duì)所有案例進(jìn)行相似度計(jì)算，且固定近鄰K值會(huì)影響預(yù)測(cè)結(jié)果的質(zhì)量。因此，本文利用聚類、優(yōu)化近鄰K值思想和最優(yōu)原則檢索策略，提出一種改進(jìn)的KNN案例推理檢索算法。并通過Mackey-Glass混沌時(shí)間序列數(shù)據(jù)進(jìn)行仿真，實(shí)驗(yàn)結(jié)果表明，針對(duì)線性問題，本文提出的改進(jìn)KNN案例推理檢索算法不僅解決了傳統(tǒng)KNN檢索算法存在的兩大缺陷，而且還具有良好的預(yù)測(cè)能力，可以進(jìn)一步改善預(yù)測(cè)結(jié)果。