分類算法在范例推理中的研究與應(yīng)用

劉連喜，邢 彤，徐 浩，王 偉，高 凱

（1.河北科技大學(xué)財務(wù)處，河北石家莊 050018；2.河北化工醫(yī)藥職業(yè)技術(shù)學(xué)院，河北石家莊 050026；3.河北科技大學(xué)信息科學(xué)與工程學(xué)院，河北石家莊 050018）

分類算法在范例推理中的研究與應(yīng)用

劉連喜1，邢 彤1，徐 浩2，王 偉3，高 凱3

（1.河北科技大學(xué)財務(wù)處，河北石家莊 050018；2.河北化工醫(yī)藥職業(yè)技術(shù)學(xué)院，河北石家莊 050026；3.河北科技大學(xué)信息科學(xué)與工程學(xué)院，河北石家莊 050018）

將范例推理中的范例初步匹配看作文本分類的特殊情形，提出基于類別中心向量的分類算法。通過確定待處理案例的歸屬類別，縮小范例檢索范圍，減少在范例精確匹配階段的計算量，提高案例初步匹配的準(zhǔn)確性。在此基礎(chǔ)上，將上述算法應(yīng)用在對交通事故案例的處理與交通信息預(yù)警系統(tǒng)中。實(shí)驗(yàn)與使用表明，該算法能較為準(zhǔn)確地判斷事故類型并給出相應(yīng)的預(yù)警信息。

人工智能；自然語言處理；分類；信息檢索；范例推理

范例推理（case－based reasoning，CBR）作為基于規(guī)則推理技術(shù)的一個重要補(bǔ)充，是當(dāng)前人工智能及機(jī)器學(xué)習(xí)領(lǐng)域中的熱門課題與前沿研究方向之一。CBR的執(zhí)行過程如圖1所示，主要包括檢索相似案例、重用相似案例并推斷新案例解決方案、修訂解決方案、保存新案例以備后用等。由于CBR具有信息的完全表達(dá)、增量式學(xué)習(xí)、形象思維的準(zhǔn)確模擬、求解效率高等特點(diǎn)，因此能夠應(yīng)用在那些沒有很強(qiáng)的理論模型和領(lǐng)域知識不完全的決策環(huán)境中［1］。目前，關(guān)于范例推理的研究主要集中在以下幾個方面：范例的索引及檢索技術(shù)，范例修正技術(shù)及其修正規(guī)則的獲取方法，范例庫的維護(hù)技術(shù)及其性能的研究，范例工程的自動化，范例推理的理論基礎(chǔ)，范例推理與其他方法（包括學(xué)習(xí)技術(shù)、多Agent技術(shù)、推理方法、數(shù)據(jù)挖掘、數(shù)據(jù)倉庫技術(shù)）的集成技術(shù)，范例推理的應(yīng)用，研制CBR開發(fā)平臺，CBR融合及大規(guī)模并行處理，基于Web的分布式CBR系統(tǒng)，可視化CBR技術(shù)及對話式CBR模型等［2－5］。

圖1 CBR執(zhí)行過程Fig.1 Process of CBR

由于交通事故發(fā)生的原因和案發(fā)現(xiàn)場的勘察結(jié)果之間往往有著一定的因果聯(lián)系，因此通過對事故勘查的特征提取，并通過相應(yīng)的匹配算法，將所抽取出來的新案例特征與范例庫中典型事故案例——指那些已成功處理、具有某些典型的特征屬性進(jìn)行比較，檢索那些較符合的事故案例，找出相應(yīng)事故的解決方案，并由分析得出相應(yīng)的預(yù)警信息是可行、可信的?；贑BR的交通事故處理及其預(yù)警機(jī)制研究，可為處理類似的交通事故案件提供決策參考。但一般的范例推理過程在檢索源范例時，往往存在著檢索結(jié)果不準(zhǔn)確、檢索效率低下等問題。如果能在檢索范例之前，通過適當(dāng)?shù)姆诸愃惴?，確定新案例最可能歸屬的類別，然后再在其所屬類別范圍里通過相似度查找最近似的部分范例，就可以有效縮小范例檢索的范圍，提高范例檢索的效率和準(zhǔn)確率。在此將范例的初步匹配問題看作文本分類問題的特殊情形，提出基于類別中心向量的分類算法，并將其應(yīng)用到范例推理的初步匹配階段。從空間幾何角度看，計算平均向量的過程就是計算多維空間中1個點(diǎn)集群中心的過程，只要1個點(diǎn)處于以這個中心和一定半徑所劃定的空間區(qū)域里，就可以認(rèn)為該點(diǎn)所代表的案例歸屬于這個中心向量所代表的類別。在前期工作基礎(chǔ)上，通過分類算法首先確定待處理案例的歸屬類別，減少了在范例精確匹配階段的計算量，提高了范例推理系統(tǒng)整體性能。通過對公路車輛監(jiān)控與交通事故處理（數(shù)據(jù)分析）的應(yīng)用表明，該算法能較為準(zhǔn)確地判斷事故類型并給出相應(yīng)的預(yù)警信息。

1 范例的組織及其向量化表示

在CBR及其推理過程中，首先要明確范例庫及其組織方式。在本應(yīng)用中，范例庫中所有交通事故范例按事故原因被分成8個類存儲，相同類別的范例保存在以類別名稱命名的文件夾中，各種信息用不同字段標(biāo)志符表示出來。當(dāng)有新的案例到來時，首先依據(jù)類別中心向量分類算法確定新范例的歸屬類別，然后計算新范例與其歸屬類別中每個范例的語義相似度，如果相似度大于閾值，就認(rèn)為新范例與已有范例相似，不再儲存，否則將新案例的信息數(shù)據(jù)以文本文件的形式保存到所屬類別的文件夾里。

當(dāng)完成了范例的向量化表示后，就構(gòu)建起了范例庫的向量空間模型，之后才能在這個向量空間里實(shí)現(xiàn)分類算法。為了便于將范例內(nèi)容映射入向量空間，使用中科分詞模塊ICTCLAS對范例的正文文本進(jìn)行分詞處理。即首先將范例正文中的所有非中文字符替換為空格符，使用分詞模塊對預(yù)處理的范例正文進(jìn)行分詞，根據(jù)停用詞詞典去除分詞結(jié)果中的停用詞。要想實(shí)現(xiàn)范例的向量化表示，須首先建立向量模板，之后可以依據(jù)向量模板實(shí)現(xiàn)范例的向量化。向量模板的構(gòu)建過程大致分如下4個步驟。

1）逐篇掃描范例庫每個范例正文的分詞結(jié)果，分別統(tǒng)計各詞項在所屬范例正文中出現(xiàn)的詞頻（TF）和各詞項在所屬范例類別中出現(xiàn)的文檔數(shù)（DF）。

2）選擇特征詞。采用TFIDF算法作為特征詞權(quán)值的計算方法，計算公式如式（1）所示，其中IDF是詞條t的逆文檔頻率，m是某一類別文檔中包含詞條t的文檔數(shù)，n是包含詞條t的文檔總數(shù)。

3）將所有詞項按照IDF值從大到小排列，再根據(jù)預(yù)先設(shè)定的最大向量維數(shù)k選取IDF最大的前k個詞項作為特征詞項。為了統(tǒng)一所有特征詞項的分布概率，需要對特征詞的IDF值進(jìn)行歸一化處理，具體方法如式（2）所示，式中IDFi表示第i項特征詞的IDF值，max（·）函數(shù)表示所有特征詞項中最大的IDF值。

在構(gòu)建了向量模板以后，就可以依據(jù)向量模板實(shí)現(xiàn)范例的向量化表示了，主要步驟如下。

1）將范例正文中的非中文字符替換為空格，用分詞模塊對其進(jìn)行分詞。

2）統(tǒng)計每個范例中各詞項的文檔頻率TF?？紤]到范例正文長度的差異，須依據(jù)范例正文長度對每個詞項的文檔頻率進(jìn)行歸一化處理，計算公式如式（3）所示，其中TFi是范例中詞項i的文檔頻率，li是范例正文長度。

為了統(tǒng)一范例中詞項的分布概率，還需要對詞項的TF值進(jìn)行歸一化處理，見式（4），式中max（·）是范例正文所有詞項中最大的TF值：

在完成向量歸一化后，掃描范例分詞結(jié)果中的每個詞項。當(dāng)把一個范例正文分詞結(jié)果中所有詞項掃描完畢后，就得到了該范例的空間向量。

2 類別中心向量的分類算法及其應(yīng)用

類別中心向量是用各個類別的中心向量來代表相應(yīng)類別，并且根據(jù)新來的案例向量與各類別中心向量的相似程度來判別新案例所歸屬的范例類別。算法處理流程見圖2。

圖2 類別中心向量分類算法流程圖Fig.2 Flow chart of the class－center vector based category algorithm

在建立了范例的向量空間模型以后，各范例都表示為向量的形式。筆者采用算數(shù)平均的方法來計算各類別的中心向量，計算公式如式（5）所示，式中Vcenter為某文檔類別的中心向量，W1為范例向量中第1維向量的權(quán)重，Wj為范例向量中第j維向量的權(quán)重，ni為文檔類別i中包含的文檔數(shù)：

通過上述步驟計算得到了各范例類別的中心向量、中心向量常數(shù)以及各類別的分類閾值后，就可以著手生成類別中心向量分類算法中的分類器模型。為了便于各種類型數(shù)據(jù)的統(tǒng)一存儲，采用XML文件格式保存分類器模型。當(dāng)某個類別的中心向量需要動態(tài)修正時，XML文件可以方便地讀取和保存相應(yīng)類別的中心向量。圖3是分類流程。范例推理系統(tǒng)的輸入數(shù)據(jù)就是待處理的交通案例，輸出就是交通事故的處理方案和某一時段的交通預(yù)警信息。在得到（或者用戶輸入）新案例后，首先將新案例的數(shù)據(jù)進(jìn)行向量化處理，然后應(yīng)用提出的分類算法來確定新案例所屬的類別，從而實(shí)現(xiàn)案例的初步匹配。之后，就可以在新案例所屬的類別內(nèi)利用向量的相似度算法為新案例找到最為相似的范例，從而實(shí)現(xiàn)案例的匹配，最終實(shí)現(xiàn)交通事故案例的范例推理過程，并借助它輔助交通處理事故。

3 實(shí)驗(yàn)分析與測試

圖3 分類流程Fig.3 Flow of the category

分別在不同的訓(xùn)練和測試樣本集中，在不同的兼取類別情況下，對類別中心向量分類算法在交通范例推理系統(tǒng)中的應(yīng)用性能進(jìn)行了測試。表1是在封閉性測試情況下，測試兼取類別數(shù)對分類器性能的影響。

表1 封閉性不同兼取類別測試Tab.1 Colse test on different compatibility numbers of the category

從表1數(shù)據(jù)可以看出，兼取類別數(shù)增加后，分類器的性能得到了顯著提高?？梢娫趯煌ò咐M(jìn)行初次匹配時，必須考慮兼類的情況，這也是符合客觀事實(shí)的。

在交通案例的選取上，基礎(chǔ)案例的缺乏是一個不可避免的問題。由于行業(yè)數(shù)據(jù)的保密性，這里采用的是從網(wǎng)上收集的一些案例來充當(dāng)范例庫的素材。盡管本文提出的算法有效實(shí)現(xiàn)了案例的初步匹配，但是該分類算法的性能還有提升空間，所以下一步還要在改進(jìn)分類算法性能上再做一些工作。

4 結(jié) 語

將范例的初步匹配問題看作文本的分類問題，提出基于類別中心向量的分類算法，并將其應(yīng)用到范例推理系統(tǒng)的初步匹配階段。通過分類算法首先確定待處理案例的歸屬類別，有效縮小了范例檢索的范圍，減少了在范例精確匹配階段的計算量，提高了范例推理系統(tǒng)整體性能。實(shí)驗(yàn)與使用表明，該算法能較為準(zhǔn)確地判斷事故類型并給出相應(yīng)的預(yù)警信息。

［1］ 劉 芳.基于CBR的智能決策支持系統(tǒng)研究與應(yīng)用［D］.蘭州：蘭州大學(xué)，2008.

［2］ 陸汝鈐.世紀(jì)之交的知識工程與知識科學(xué)［M］.北京：清華大學(xué)出版社，2001.

［3］ 陳文偉.決策支持系統(tǒng)及其開發(fā)［M］.北京：清華大學(xué)出版社，2000.

［4］ 周 勇，賈瑞玉.范例推理在智能決策系統(tǒng)中的應(yīng)用研究［J］.電腦知識與技術(shù)（學(xué)術(shù)交流）（Computer Knowledge and Technology（Academic Exchange）），2007（3）：824－829.

［5］ 王 偉，許云峰，高 凱.基于哈希表的動態(tài)向量降維方法的研究及應(yīng)用［J］.河北科技大學(xué)學(xué)報（Journal of Hebei University of Science and Technology），2011，32（4）：360－365.

Study on catagory algorithm and its application in cased－based reasoning

LIU Lian－xi1，XING Tong1，XU Hao2，WANG Wei3，GAO Kai3
（1.Finance Department，Hebei University of Science and Technology，Shijiazhuang Hebei 050018，China；2.Hebei Chemical and Pharmaceutical College，Shijiazhuang Hebei 050026，China；3.College of Information Science and Engineering，Hebei University of Science and Technology，Shijiazhuang Hebei 050018，China）

This paper presents the class－centre vector based category algorithm，which is regarded as the basis of the text classification in case－based reasoning application.On the basis of the proposed algorithm，this method can be used to determine those cases＇affiliation，and as a result this can reduce the retrieval scope so as to reduce the calculation and improve the precision.We use the proposed algorithm in the traffic accident analysis and the corresponding early warning system.The experimental results and the analysis prove the feasibility of the approach，and the existing problems and further works are also discussed in the end.

artificial intelligence；natural language understanding；category；information retrieval；case－based reasoning

TP274

A

1008－1542（2012）02－0150－04

2011－11－17；責(zé)任編輯：李 穆

河北省科技支撐計劃資助項目（074572172）

劉連喜（1965－），女，河北高邑人，高級會計師，主要從事信息管理、會計理論與電算化技術(shù)等方面的研究。

高 凱副教授。E－mail：gaokao68＠163.com