嚴愛軍，魏志遠

（1.北京工業(yè)大學信息學部，北京 100124；2.數(shù)字社區(qū)教育部工程研究中心（北京工業(yè)大學），北京 100124；3.城市軌道交通北京實驗室（北京工業(yè)大學），北京 100124）

0 引言

案例推理（Case-Based Reasoning，CBR）方法的思想最早由美國耶魯大學的Schank 描述［1］，其原理是利用原有的案例來解釋或解決一個新的問題［2］，后逐漸成為人工智能領(lǐng)域一種重要的問題求解方法且成功應(yīng)用在分類［3］、診斷［4］、設(shè)計［5］等領(lǐng)域。CBR求解過程模型包括四個環(huán)節(jié)，即案例檢索、案例重用、案例修正和案例存儲［6］。其中，案例檢索處于四個環(huán)節(jié)的第一步，檢索質(zhì)量的好壞直接影響CBR 模型的性能，而不合理的權(quán)重分配會影響檢索質(zhì)量。所以，對特征權(quán)重進行合理分配［7］十分必要。另外，案例存儲是案例推理的最后一個環(huán)節(jié)，也是實現(xiàn)增量式學習的一個步驟，隨著案例庫中案例數(shù)量的不斷增加，CBR模型的性能可能會得到顯著改善，但隨著冗余案例［8］或噪聲案例［9］的增加，將會導致其求解性能的下降。因此，針對特定的系統(tǒng)，往往需要制定一個完備的案例庫維護措施。

特征賦權(quán)方法主要有主觀賦權(quán)法和客觀賦權(quán)法［10］。常用的主觀賦權(quán)法有專家調(diào)查法、數(shù)值邏輯法、可調(diào)均值法等［11］?？陀^賦權(quán)法主要有遺傳算法（Genetic Algorithm，GA）［12］、熵權(quán)（Entropy Weight，EW）法［13］等。文獻［14］采用了遺傳算法考慮主觀因素和客觀因素影響的自適應(yīng)屬性權(quán)重的分配方法，提高了案例推理的整體效率；文獻［15］通過采用基于有序加權(quán)平均（Ordered Weighted Averaging，OWA）算子的賦權(quán)方法確定各特征屬性權(quán)值；文獻［16］利用熵權(quán)法和層次分析（Analytic Hierarchy Process，AHP）法分別計算案例特征屬性的主觀、客觀權(quán)重以求得綜合權(quán)重，以最大限度地減少信息損失。以上研究從主客觀的角度出發(fā)，全面考慮影響特征權(quán)重的因素。然而，基于遺傳算法的特征權(quán)重分配極易陷入局部最優(yōu)，而且熵權(quán)法對隨機數(shù)據(jù)的變化幅度非常敏感。

針對案例庫維護：文獻［17］提出了一種基于軟能力模型和模糊聚類技術(shù)的軟案例庫維護方法，有效提高了系統(tǒng)的性能并且減少了存儲空間；文獻［18］提出了一種基于加權(quán)特征密度聚類的方法，把具有足夠高密度的區(qū)域劃分為小的簇，并識別出噪聲案例，減少了存儲空間和搜索時間；Ayed 等［19］提出了基于證據(jù)策略的案例集成維護方法，通過提供新的交替技術(shù)來正確監(jiān)測噪聲或冗余；Torrent-Fontbona 等［20］提出了基于案例的冗余減少和屬性權(quán)重學習的案例庫維護方法。以上方法在案例庫維護方面具有一定成效，但面對數(shù)據(jù)量大的任務(wù)很難滿足實時性要求，而且沒有充分考慮離群、冗余或噪聲案例對系統(tǒng)性能的影響。

針對以上問題，本文對案例推理分類模型中的特征權(quán)重采用蟻獅（Ant Lion Optimizer，ALO）算法［21］進行分配、案例庫采用高斯混合模型的期望最大化（Expectation Maximization of Gaussian Mixture Model，GMMEM）算法［22］進行維護，提出了AGECBR（Ant lion and Expectation maximization of Gaussian mixture model Case-Based Reasoning）方法；并且，通過實驗驗證AGECBR方法能夠有效提高案例推理分類算法的性能。

1 CBR分類原理與問題分析

1.1 CBR分類原理

案例推理分類器的結(jié)構(gòu)原理如圖1 所示，包括案例檢索、案例重用、案例修正和案例存儲等四個步驟。

圖1 CBR分類器結(jié)構(gòu)Fig.1 Structure of CBR classifier

各部分的功能分別是：

1）案例檢索。計算目標案例和案例庫中各源案例的相似度，并按相似度大小對其進行排序，得到與目標案例最為相似的k個源案例。

2）案例重用。對檢索出來的k個源案例進行類別統(tǒng)計，將數(shù)量最多的那一種類別作為建議類別。

3）案例修正。對獲得的建議類別進行評價，若評價失敗，則需要對結(jié)果進行修正，以獲得最終的正確類別。

4）案例存儲。將目標案例和正確類別合并為一條新案例存儲在案例庫中，供下次的問題求解，從而實現(xiàn)CBR 的經(jīng)驗存儲和增量式學習過程。

1.2 問題分析

以下對影響案例推理分類性能的因素進行分析，主要考察特征權(quán)重大小和案例存儲等兩方面的影響：

1）特征權(quán)重。以數(shù)值類型案例為例，圖1 中的案例檢索是通過計算目標案例與案例庫中源案例的相似度來實現(xiàn)的，較為常見的相似度計算方法是采用如下所示的歐氏距離公式：

其中：p是源案例總數(shù)；xi為目標案例的第i個特征值，xi，k為第k條源案例的第i個特征值；ωi(i=1，2，…，m)是第i個特征的權(quán)重。從式（1）可以看出，影響相似性度量是否準確的一個關(guān)鍵因素是特征權(quán)重ωi的大小，標志著特征的重要程度。權(quán)重的優(yōu)化分配問題可以表示為：

其中：F表示CBR 分類器的性能指標［7］。當分配的特征權(quán)重滿足上述等式約束和有界約束條件，并使得性能指標F的值取最大，就說明分配的權(quán)重是合理的。目前存在的一些客觀賦權(quán)法，比如遺傳算法存在容易陷入局部最優(yōu)等問題。2015年由Mirjalili提出的蟻獅算法［21］是一種無梯度算法，它使用了大量的搜索來逼近全局最優(yōu)解，可以有效避免陷入局部最優(yōu)問題。它在定義離散型特征變量的變化范圍時，采用自適應(yīng)收縮機制，可以隨著迭代次數(shù)的增加而促進利用；同時，該算法需調(diào)整的參數(shù)較少，而且部分參數(shù)能夠自適應(yīng)更改，有利于解決參數(shù)優(yōu)化、求取全局最優(yōu)解等問題。因此，本文將采用蟻獅算法進行特征權(quán)重的優(yōu)化分配，以期提高CBR 分類器的性能指標。

2）案例存儲。使用CBR 求解問題的最后一個步驟是案例存儲，這也是實現(xiàn)CBR 增量式學習的重要一步。隨著時間的推移，新案例不斷被保存，雖然案例數(shù)的不斷增加可以使得檢索到相似案例的概率增大，但也使得算法檢索時間增長。目前采用的一些案例庫維護方法，比如密度聚類算法存在實時性較差、只能處理單一類型數(shù)據(jù)等問題。1998 年由Bilmes提出的高斯混合模型的期望最大化算法［22］可以擬合出多種數(shù)據(jù)類型分布，并處理同一集合下包含不同分布情況的數(shù)據(jù)；同時，該算法還可以用于處理數(shù)據(jù)缺失等問題。因此，本文將采用高斯混合模型的期望最大化算法對案例庫進行聚類，并刪除案例庫中的冗余案例和噪聲案例，以期實現(xiàn)案例庫的有效維護，提高CBR的分類性能。

2 基于ALO的權(quán)重優(yōu)化

蟻獅算法［21］模擬了自然界蟻獅使用陷阱獵捕螞蟻的機制。代表嘗試解的螞蟻隨機游走時會受到陷阱的影響，被代表局部最優(yōu)解的蟻獅所捕食，所有的蟻獅捕食螞蟻后從中選取最優(yōu)位置的蟻獅作為一次迭代計算后的全局最優(yōu)解，通過不斷地迭代，得到最終的全局最優(yōu)解，即蟻獅的最終位置坐標。

根據(jù)上述機制，令特征權(quán)重對應(yīng)于蟻獅的位置坐標，采用蟻獅算法對特征權(quán)重優(yōu)化分配共包含四個步驟：權(quán)重初始化以及迭代更新、計算適應(yīng)度、采用輪盤賭方法選取特征變量、更新特征權(quán)重并得到最優(yōu)特征權(quán)重。下面介紹具體的算法。

1）權(quán)重初始化以及權(quán)重的迭代更新。

令迭代過程中的特征權(quán)重為ω(t)，更新公式為：

其中：cumsum表示計算累計和；m表示最大迭代次數(shù)（也是m個特征）；t1～tm表示特征權(quán)重對應(yīng)的每列最大迭代次數(shù)分別為1次到m次；r(ti)是一個隨機函數(shù)。

其中：rand用來產(chǎn)生位于區(qū)間［0，1］內(nèi)具有均勻分布的隨機數(shù)。

根據(jù)式（2），權(quán)重受邊界范圍約束，所以式（3）不能直接用于更新特征權(quán)重，需使用式（5）對其進行約束：

其中：ai是初始化權(quán)重中權(quán)重最小值；bi是初始化權(quán)重中權(quán)重最大值為第t次迭代第i個特征變量的最小值為第t次迭代第i個特征變量的最大值。

第t次迭代的第j個權(quán)重與第t次迭代中所有變量的最值相加即為第t次迭代第i個特征變量的最值，第t次迭代第i個特征變量的最值定義如下：

其中：ct為第t次迭代所有特征變量的最小值；dt為第t次迭代所有特征變量的最大值表示在第t次迭代時所選擇的第j個特征權(quán)重，即在一組權(quán)重中，除去第i個特征權(quán)重后剩余的最優(yōu)特征權(quán)重。

為了更快速得到特征變量的最值，在迭代過程中，不斷縮小特征變量的檢索范圍，下面對式（6）和（7）進行如下約束：

其中：I=10wt/m；w是基于當前迭代定義的常數(shù)（當t＞0.1m，w=2；當t＞0.5m，w=3；當t＞0.75m，w=4；當t＞0.9m，w=5；當t＞0.95m，w=6），其他符號意義參見式（3）、（6）和（7）。

2）計算適應(yīng)度函數(shù)。

評價權(quán)重尋優(yōu)的適應(yīng)度函數(shù)為案例推理分類器的準確率，如下所示：

其中：g為測試集中分類正確的數(shù)量；p′為測試集中案例總數(shù)量。

3）采用輪盤賭方法選取特征變量。

在蟻獅算法權(quán)重尋優(yōu)過程中，根據(jù)權(quán)重對應(yīng)的適應(yīng)度值，采用輪盤賭的方法選取適應(yīng)度值高的特征變量，進行下一次迭代。

4）更新特征權(quán)重并得到最優(yōu)特征權(quán)重。

在每次迭代過程中，都會得到一個最優(yōu)權(quán)重。當最優(yōu)權(quán)重出現(xiàn)后，根據(jù)式（11）將此時最優(yōu)權(quán)重定義為當前值：

當最后一次迭代完成后，確定m個最優(yōu)特征權(quán)重，至此，特征權(quán)重分配過程結(jié)束。

算法偽代碼如下所示：

3 基于GMMEM的案例庫維護

案例庫維護包含案例庫聚類和案例庫約簡兩部分：首先，利用高斯混合模型的期望最大化算法（GMMEM）［22］對歸一化后的案例樣本進行聚類，得到J個聚類簇，此時獲得的案例庫定義為Bg。其次，對每個聚類簇分兩個步驟進行約簡：第一步，若Bg中只包含一個案例則作為離群案例保存，否則統(tǒng)計Bg中占少數(shù)類別的案例，將其作為噪聲案例刪除得到聚類簇C；第二步，若聚類簇C中存在相似度大于設(shè)定閾值的案例，則作為冗余案例刪除并得到聚類簇P；最后將p′個約簡后的聚類簇合并構(gòu)成約簡案例庫Q［23-24］。

1）案例庫聚類。

高斯混合聚類采用概率模型來表達聚類原型。對于數(shù)據(jù)集中的向量Dk，設(shè)其概率密度函數(shù)為：

其中：μ是m維均值向量；Σ是m*m的協(xié)方差矩陣。將概率密度函數(shù)記為N(Dk|μ，Σ)，則高斯混合分布定義為：

在每步迭代中，根據(jù)式（16）計算每個案例樣本屬于每個高斯成分的后驗概率γkc（E 步），再根據(jù)式（17）、（18）、（20）更新參數(shù)模型{(πc，μc，Σc)|1 ≤c≤J}（M 步）。當高斯混合分布（14）已知時，高斯混合聚類將樣本劃分為J個聚類簇，聚類簇表示為：

其中：xi，l表示Bg中第i個特征變量的值；g是案例庫劃分的聚類簇數(shù)；l為Bg中案例數(shù)。

2）案例庫的約簡。

對Bg約簡，若Bg中只包含一個案例，則作為離群案例保存；否則統(tǒng)計Bg中占多數(shù)類別的案例，通過占多數(shù)類別的案例確定占少數(shù)類別的案例，并將這些少數(shù)案例作為噪聲案例去除，去除噪聲案例后得到聚類簇C，表示為

接著，將聚類簇C中每個案例作為目標案例，計算出該案例與其他案例之間的歐氏距離和相似度，若目標案例與其近鄰案例間的相似度均大于設(shè)定閾值，則將此類近鄰案例作為冗余案例刪除，去除冗余后得到聚類簇P，表示為：

當所有聚類簇完成約簡后，與p3個離群點案例合并成約簡案例庫：

其中：約簡后的案例個數(shù)p′=p1+p2+p3。

算法偽代碼如下所示：

4 實驗

為驗證CBR 分類模型的性能，本章首先介紹了實驗設(shè)計方案以及實驗步驟，然后進行了算法性能的實驗測試，最后是對比實驗和結(jié)果分析。

實驗在Matlab R2016a 9.0.0 環(huán)境下編程實現(xiàn)，所用的計算機CPU 為Intel Core i5-4590H CPU @3.30 GHz，內(nèi)存為4 GB。實驗中所用數(shù)據(jù)集選取UCI［25］數(shù)據(jù)庫中的5 組分類數(shù)據(jù)集進行實驗，具體信息如表1所示。

表1 實驗數(shù)據(jù)集基本信息Tab.1 Basic information of experimental datasets

4.1 實驗設(shè)計

為了對本文模型進行有效性測試，采用五折交叉驗證法，實驗分為性能測試和對比實驗。

測試CBR 分類模型算法受k近鄰個數(shù)的影響。實驗步驟如下：

步驟1 選定數(shù)據(jù)集，確定歷史案例庫和目標案例庫，將案例的特征變量進行歸一化處理；

步驟2 對歷史案例庫依據(jù)文獻［26］最大相關(guān)最小冗余法選取m個特征變量，并運用算法1 對特征變量進行權(quán)重分配；

步驟3 通過式（1）對目標案例進行檢索；

步驟4 檢索出k個相似源案例并統(tǒng)計故障類別，將個數(shù)最多的一種故障類別作為目標案例的建議類別；

步驟5 根據(jù)算法2對案例庫進行聚類，刪除冗余案例和噪聲案例，進行案例庫維護，以決定是否將案例進行存儲；

步驟6 如果有新的目標案例出現(xiàn)，轉(zhuǎn)至步驟3，直至所有目標案例完成分類測試；

步驟7 分別取k=1，3，5，7，9，重復(fù)步驟3～6，并記錄不同k值下的分類準確率。

對比實驗包含三個：

實驗1 將不同權(quán)重分配方法（均權(quán)重（Average Weight，AW）、遺傳算法（GA）、注水法（Water Filling Algorithm，WFA）、互信息（Mutual Information，MI）法、蟻獅（ALO）算法）與CBR結(jié)合后的分類性能進行對比；

實驗2 將不同的案例庫維護方法（模糊C均值（Fuzzy CMeans，F(xiàn)CM）聚類法、代數(shù)重建（Algebra Reconstruction Technique，ART）法、自組織映射（Self-Organizing Feature Map，SOFM）神經(jīng)網(wǎng)絡(luò)法、高斯混合模型的期望最大化法（GMMEM））與CBR結(jié)合后的分類性能進行對比；

實驗3 將采用蟻獅算法對權(quán)重分配與高斯混合模型的期望最大化算法對案例庫維護后的CBR 分類記為AGECBR，然后與反向傳播算法（Error Back Propagation，BP）、k近鄰（k-Nearest Neighbor，kNN）算法、支持向量機（Support Vector Machine，SVM）等經(jīng)典方法進行實驗對比。

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

ALO 算法參數(shù)主要由特征變量m、最大迭代次數(shù)n、特征變量的最大值d和最小值c構(gòu)成。根據(jù)分類數(shù)據(jù)集數(shù)據(jù)特點，特征變量的最小值c為0，最大值d為1。本文特征變量數(shù)m通過最大相關(guān)最小冗余法［26］獲得。其余參數(shù)利用網(wǎng)格搜索算法（GridSearchCV），通過窮舉搜索、循環(huán)遍歷所有候選參數(shù)得到最優(yōu)參數(shù)，根據(jù)測試集案例的準確率高低評價參數(shù)的優(yōu)劣。其余參數(shù)設(shè)置為ID1：m=7，n=50；ID2：m=9，n=55；ID3：m=23，n=40；ID4：m=8，n=55；ID5：m=4，n=55。

4.3 性能測試

為測試近鄰個數(shù)k變化時對CBR 分類模型算法的影響，根據(jù)性能測試的實驗步驟1～7進行實驗測試，當k=1，3，5，7，9時，觀察分類準確率的變化情況。實驗結(jié)果如表2 所示。由表2 可知，隨著k值的增加，平均準確率會有不同程度的下降或上升，但幅度不大。其中，當k=1 時，平均分類準確率最高。

表2 不同近鄰個數(shù)k的分類準確性 單位：%Tab.2 Classification accuracy of different nearest neighbor number k unit：%

4.4 對比實驗

此節(jié)共包含三個實驗，分別為不同權(quán)重分配方法、不同案例庫維護方法以及不同分類方法的對比實驗。

4.4.1 權(quán)重分配

為了考察ALO 權(quán)重分配方法的性能，根據(jù)實驗1 對表1所示的5 個數(shù)據(jù)集進行分類對比實驗，實驗結(jié)果如表3 所示。五折交叉實驗的分類準確率平均值分別為：89.28%、89.95%、87.98%、88.71%、92.43%。由此可知，五種權(quán)重分配方法的平均分類準確率由低到高依次是：WFA、MI、AW、GA、ALO。在蟻獅算法中采用輪盤賭的方法隨機選擇特征變量，保證特征變量在搜索空間內(nèi)的變化；在迭代過程中，特征變量的變化范圍自適應(yīng)地減小，保證了算法的收斂性；蟻獅算法運用大量搜索來逼近全局最優(yōu)解，避免了局部最優(yōu)解，所以ALO權(quán)重分配方法能夠使CBR分類器分類準確率提升。

表3 不同權(quán)重分配方法的平均分類準確率（k=1） 單位：%Tab.3 Average classification accuracy of different weight allocation methods（k=1） unit：%

4.4.2 案例庫維護

根據(jù)實驗2，將FCM、ART、SOFM、GMMEM 方法與CBR 相結(jié)合，進行案例庫維護對比實驗。其中，GMMEM 案例庫維護方法的分類準確率最高為89.78%，其余三種案例庫維護方法的分類準確率由低到高分別為SOFM（85.89%）、FCM（88.35%）、ART（88.63%）。說明采用GMMEM 概率式的聚類方法不僅保持了案例庫的一定規(guī)模，而且保證了案例檢索的準確率，對提升CBR的分類性能具有促進作用。

4.4.3 分類方法

根據(jù)實驗3，將本文AGECBR 分類模型算法與BP、kNN、SVM、FCMCBR（Fuzzy C-Means Case-Based Reasoning）等分類算法進行對比實驗，實驗結(jié)果如表4 所示?？梢钥闯觯疚乃惴ㄖ挥性贗D 為5 的數(shù)據(jù)集中的準確率低于其中兩種方法，其余數(shù)據(jù)集中的準確率都有不同程度的提升。五種方法的平均分類準確率由低到高排序為：BP、SVM、FCMCBR、kNN、AGECBR。

表4 不同算法的分類準確率 單位：%Tab.4 Classification accuracy of different algorithms unit：%

為了全面客觀評定本文方法的效果，從精確率、召回率和F1值角度進行分析［3］：

1）案例實際結(jié)果為故障且算法模型檢測結(jié)果為故障，記為真陽（True Position，TP）；

2）案例實際結(jié)果為故障而算法模型檢測結(jié)果為正常，記為假陰（False Negative，F(xiàn)N）；

3）案例實際結(jié)果是正常且算法模型檢測結(jié)果為正常，記為真陰（True Negative，TN）；

4）案例實際結(jié)果是正常而算法模型檢測結(jié)果為故障，記為假陽（False Positive，F(xiàn)P）。

精確率為正確預(yù)測為正的占全部預(yù)測為正的比例，公式如下：

召回率為正確預(yù)測為正的占全部實際為正的比例，公式如下：

實驗結(jié)果如表5 所示。由表5 可知：在精確率方面，除ID為4時偏低外，其余數(shù)據(jù)集的都在90%以上，說明本文算法能夠有效預(yù)測出全部預(yù)測為正常類案例中正常類的案例個數(shù)；在召回率方面，所有數(shù)據(jù)集的召回率都高于90%，即本文算法對正常類樣本錯誤分類的比例很??；在F1 方面，除ID 為4 時稍低于90%，其余數(shù)據(jù)集的值都在95%以上，表明本文算法的效果比較理想。

表5 精確率、召回率和F1值Tab.5 Precision，recall and F1 value

由表6 可知，對于不同分類方法的運行時間，AGECBR 分類時間要稍低于BP和FCMCBR，但是高于kNN和SVM。綜合分類準確率和分類運行時間，AGECBR 的綜合性能更占優(yōu)勢。

表6 不同分類方法的運行時間 單位：sTab.6 Running time of different classification methods unit：s

5 結(jié)語

為了提高CBR 分類器的分類性能，本文一是采用蟻獅算法對特征變量的權(quán)重進行了分配；二是針對案例庫維護存在的效用問題，采用GMMEM 方法進行了案例庫的維護，通過分離噪聲案例、冗余案例和離群案例來得到約簡案例庫。為了驗證本文方法的有效性，分別進行了性能測試和對比實驗，主要結(jié)果如下：

1）在案例檢索階段采用基于ALO 的特征權(quán)重分配方法，并將CBR 案例分類準確率作為ALO 的適應(yīng)度函數(shù)，通過該方法分配的特征權(quán)重能夠有效提升CBR的分類性能；

2）在案例庫的維護過程中，采用GMMEM 的聚類方法，能有效約減案例庫的規(guī)模，同時也能提高CBR的分類準確率。

盡管本文方法在提升CBR 分類性能方面具有一定優(yōu)勢，但也存在著一些不足之處，比如，在權(quán)重分配的過程中，需要不斷調(diào)節(jié)ALO 算法的參數(shù)，以便能夠使CBR 分類準確率達到最高；同時為了提升CBR 的分類準確率采用了案例庫維護策略，與傳統(tǒng)的案例推理分類器對比增加了時間復(fù)雜度。以上存在的這些問題需要進一步研究改進。