案例推理分類器的權重分配及案例庫維護方法

嚴愛軍，魏志遠

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

0 引言

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

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

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

針對以上問題，本文對案例推理分類模型中的特征權重采用蟻獅（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分類原理

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

圖1 CBR分類器結構Fig.1 Structure of CBR classifier

各部分的功能分別是：

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

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

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

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

1.2 問題分析

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

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

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

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

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

2 基于ALO的權重優化

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

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

1）權重初始化以及權重的迭代更新。

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

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

其中：rand用來產生位于區間［0，1］內具有均勻分布的隨機數。

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

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

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

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

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

其中：I=10wt/m；w是基于當前迭代定義的常數（當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）計算適應度函數。

評價權重尋優的適應度函數為案例推理分類器的準確率，如下所示：

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

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

在蟻獅算法權重尋優過程中，根據權重對應的適應度值，采用輪盤賭的方法選取適應度值高的特征變量，進行下一次迭代。

4）更新特征權重并得到最優特征權重。

在每次迭代過程中，都會得到一個最優權重。當最優權重出現后，根據式（11）將此時最優權重定義為當前值：

當最后一次迭代完成后，確定m個最優特征權重，至此，特征權重分配過程結束。

算法偽代碼如下所示：

3 基于GMMEM的案例庫維護

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

1）案例庫聚類。

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

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

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

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

2）案例庫的約簡。

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

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

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

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

算法偽代碼如下所示：

4 實驗

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

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

表1 實驗數據集基本信息Tab.1 Basic information of experimental datasets

4.1 實驗設計

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

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

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

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

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

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

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

步驟6 如果有新的目標案例出現，轉至步驟3，直至所有目標案例完成分類測試；

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

對比實驗包含三個：

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

實驗2 將不同的案例庫維護方法（模糊C均值（Fuzzy CMeans，FCM）聚類法、代數重建（Algebra Reconstruction Technique，ART）法、自組織映射（Self-Organizing Feature Map，SOFM）神經網絡法、高斯混合模型的期望最大化法（GMMEM））與CBR結合后的分類性能進行對比；

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

4.2 參數設置

ALO 算法參數主要由特征變量m、最大迭代次數n、特征變量的最大值d和最小值c構成。根據分類數據集數據特點，特征變量的最小值c為0，最大值d為1。本文特征變量數m通過最大相關最小冗余法［26］獲得。其余參數利用網格搜索算法（GridSearchCV），通過窮舉搜索、循環遍歷所有候選參數得到最優參數，根據測試集案例的準確率高低評價參數的優劣。其余參數設置為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 性能測試

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

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

4.4 對比實驗

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

4.4.1 權重分配

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

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

4.4.2 案例庫維護

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

4.4.3 分類方法

根據實驗3，將本文AGECBR 分類模型算法與BP、kNN、SVM、FCMCBR（Fuzzy C-Means Case-Based Reasoning）等分類算法進行對比實驗，實驗結果如表4 所示。可以看出，本文算法只有在ID 為5 的數據集中的準確率低于其中兩種方法，其余數據集中的準確率都有不同程度的提升。五種方法的平均分類準確率由低到高排序為：BP、SVM、FCMCBR、kNN、AGECBR。

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

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

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

2）案例實際結果為故障而算法模型檢測結果為正常，記為假陰（False Negative，FN）；

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

4）案例實際結果是正常而算法模型檢測結果為故障，記為假陽（False Positive，FP）。

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

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

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

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

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

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

5 結語

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

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

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

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