一種改進的KNN案例推理檢索算法*

孫寶貴，車文剛，廖江福

(1.昆明理工大學信息工程與自動化學院，云南 昆明650500；2.昆明理工大學云南省計算機技術(shù)應(yīng)用重點實驗室，云南 昆明650500)

1 引言

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

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

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

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

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

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

2.1 CBR問題描述

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

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個特征屬性。

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

2.2 K最近鄰回歸算法

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

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

步驟1計算目標案例與案例庫中所有案例的距離-特征項距離和；

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

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

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

平均值如式(1)所示：

(1)

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

(2)

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

3 改進的KNN案例推理檢索算法

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

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

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

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

(3)

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

(4)

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

(5)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

輸入：cn個類簇。

輸出：cn個類簇的近鄰K值。

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

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

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

(6)

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

(7)

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

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

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

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

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

步驟8輸出cn個類簇的近鄰K值。

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

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

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

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

(8)

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

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

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

(9)

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

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

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

因此，上述方法在確定此類型目標案例的檢索案例庫時，會強制剔除掉較相似的類簇，將其劃分到最相似的類簇中。這會導致此類型目標案例損失部分相似歷史案例，使其檢索案例庫減小。

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

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

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

Dist=dist2-dist1

(10)

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

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

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

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

3.4 算法流程

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

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

4 實驗及結(jié)果分析

4.1 實驗方案

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

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

本文進行了2組實驗：

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

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

評價2組實驗預(yù)測結(jié)果的指標采用均方誤差值MSE(Mean Squared Error)和平均絕對百分誤差MAPE(Mean Absolute Percentage Error)。

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

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

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

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

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

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

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

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

對于聚類及優(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ù)測結(jié)果的局部圖

4.3 聚類有效性評價指標

本文采用Davies-Bouldin指標DBI(Davies Bouldin Index)對聚類的最佳類簇數(shù)進行評價，其定義如式(11)所示：

(11)

(12)

(13)

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

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

4.4 實驗結(jié)果及分析

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

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

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

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

由表2可知，5種檢索算法中，MSE、MAPE最小的是SAGA-FCM-GAPSO-KNN算法，其次是SAGA-FCM-PSO-KNN算法，最差的是傳統(tǒng)的KNN算法。在改進的4種算法中，預(yù)測效果最差的為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算法在檢索案例時預(yù)測結(jié)果最好。

Table 2 Evaluation index of prediction results of 5 retrieval algorithms表2 5種檢索算法預(yù)測結(jié)果的評價指標

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

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

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

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

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

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

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

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

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

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

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

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

Table 5 Evaluation index of the prediction result of each retrieval algorithm 表5 各檢索算法預(yù)測結(jié)果的評價指標

5 結(jié)束語

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