，

(福建工程學(xué)院 信息科學(xué)與工程學(xué)院，福建 福州 350118)

基于改進(jìn)KNN的案例匹配模塊的設(shè)計(jì)與實(shí)現(xiàn)

謝開(kāi)池，薛醒思

(福建工程學(xué)院 信息科學(xué)與工程學(xué)院，福建 福州 350118)

為了提高KNN檢索策略的檢索效率和檢索結(jié)果的質(zhì)量，提出一種改進(jìn)的KNN檢索策略。在引入圖書(shū)館領(lǐng)域本體和概念語(yǔ)義相似度度量技術(shù)的前提下，利用句法結(jié)構(gòu)篩選不合理的案例以降低計(jì)算規(guī)模,從而提高案例的檢索質(zhì)量和效率，利用改進(jìn)的微粒群算法優(yōu)化概念語(yǔ)義相似度度量技術(shù)中的組合參數(shù)以提高KNN檢索的結(jié)果質(zhì)量。實(shí)驗(yàn)數(shù)據(jù)采用福州曉鋒科技信息咨詢有限公司提供的圖書(shū)館參考咨詢測(cè)試數(shù)據(jù)。實(shí)驗(yàn)結(jié)果表明，相比于傳統(tǒng)KNN和基于傳統(tǒng)PSO的改進(jìn)KNN方案有效地提高了案例匹配結(jié)果的查全率和查準(zhǔn)率。

案例推理； KNN； 微粒群算法

圖書(shū)館虛擬咨詢參考系統(tǒng)是一類(lèi)智能決策支持系統(tǒng)(intelligent decision support systems，簡(jiǎn)稱(chēng)IDSS)[1]，該系統(tǒng)利用基于知識(shí)庫(kù)和案例庫(kù)的推理技術(shù)確定用戶決策所需的信息。案例推理技術(shù)[2](case based reasoning，簡(jiǎn)稱(chēng)CBR)是IDSS的核心技術(shù)之一，其目的是依據(jù)給定的決策問(wèn)題和決策環(huán)境的特征描述，快速而有效地確定案例庫(kù)中對(duì)求解的問(wèn)題最有幫助的案例[3]。在案例推理技術(shù)中，如何制定一種高效的案例檢索策略是目前亟需解決的關(guān)鍵問(wèn)題[4]。針對(duì)該問(wèn)題，李小展[5]提出了分階段的最近鄰策略，利用特征加權(quán)的產(chǎn)K nearest neighbourhood(KNN)逐步縮小案例檢索范圍，以此提高醫(yī)療輔助診斷系統(tǒng)的檢索效率；費(fèi)玉蓮[6]采用計(jì)算概念之間的相關(guān)系數(shù)的語(yǔ)義距離求得概念間的相似度，再利用KNN求得源案例和目標(biāo)案例相似度。但這些檢索策略既沒(méi)有全面考慮影響概念語(yǔ)義相似度的相關(guān)因素(語(yǔ)義關(guān)系、語(yǔ)義距離、節(jié)點(diǎn)深度和節(jié)點(diǎn)密度)，且相似度匹配中參數(shù)仍存在人為因素，從而影響檢索結(jié)果的質(zhì)量。針對(duì)上述過(guò)程，提出一種基于圖書(shū)館領(lǐng)域本體知識(shí)庫(kù)的KNN案例檢索策略。首先，在引入圖書(shū)館領(lǐng)域本體[7]的基礎(chǔ)上，利用本體的概念層次樹(shù)結(jié)構(gòu)對(duì)案例問(wèn)句進(jìn)行“主-謂-賓”三元組語(yǔ)義標(biāo)注的案例標(biāo)注，利用案例問(wèn)句的“主-謂-賓”句式結(jié)構(gòu)過(guò)濾案例庫(kù)中不符合的案例集，減少候選案例集的規(guī)模，提高基于KNN的CBR技術(shù)的效率和結(jié)果質(zhì)量。其次，通過(guò)改進(jìn)的微粒群優(yōu)化算法確定三類(lèi)相似度度量技術(shù)最優(yōu)的集成權(quán)重、K值及相似度閾值，并在匹配過(guò)程中綜合考慮3類(lèi)基于本體概念層次樹(shù)的相似度度量技術(shù)，提高了案例檢索的查準(zhǔn)率和查全率。

1 相關(guān)概念與技術(shù)

定義1本體(Ontology)：本體是一個(gè)共享概念化模型的形式化和顯式的說(shuō)明規(guī)范[8]，其核心是本體能夠解釋計(jì)算機(jī)語(yǔ)義信息。文中本體可表示為一個(gè)三元組O=(C,R,A)。其中：C表示概念的集合，即某一領(lǐng)域的概念范疇；R表示概念間的關(guān)系，即該領(lǐng)域概念之間的關(guān)聯(lián)；A表示公理集，即關(guān)于被建模領(lǐng)域中真假的論述。

定義2本體概念層次樹(shù)：給定本體O，本體概念層次樹(shù)是一個(gè)三元組T=(N,R,F)。其中：N={n1,n2,…,ne}是本體概念層次樹(shù)中個(gè)概念節(jié)點(diǎn)的集合,ni(i=1,2,…,e)對(duì)應(yīng)O中的概念ci(i=1,2,…,|C|)；R=(ni,nj)i,j∈{1,2,…,e}是本體概念層次樹(shù)中概念節(jié)點(diǎn)ni和nj之間的邊集合，表示對(duì)應(yīng)概念ci和cj之間的is-a關(guān)系；F={F1,F2,…}是本體概念層次樹(shù)的層的集合。其中：令path(ni) 表示概念節(jié)點(diǎn)ni到根節(jié)點(diǎn)的最短路徑長(zhǎng)度，F(xiàn)j={ni|ni?N,path(ni)=j,i∈[1,e],j=1,2,…}。

定義3圖書(shū)館參考咨詢案例：圖書(shū)館參考咨詢案例是一個(gè)五元組case=(caseId,question,predicate,keyword,answer) ,其中caseId表示圖書(shū)館參考咨詢案例的編號(hào)；question表示該案例的問(wèn)題；predicate表示該案例的謂語(yǔ)；keyword=(subject,object)表示該案例的關(guān)鍵詞(分別是主語(yǔ)和謂語(yǔ))；answer表示該案例的問(wèn)題答案。

定義4圖書(shū)館參考咨詢案例庫(kù)：圖書(shū)館參考咨詢案例庫(kù)是指一種將已存在的圖書(shū)館參考咨詢案例以一定的索引方式存儲(chǔ)的知識(shí)庫(kù)，表示為Case={case1,case2,…,casez}，casez表示案例庫(kù)中的第Z個(gè)歷史案例(history case，簡(jiǎn)稱(chēng)HC),Z表示圖書(shū)館參考咨詢案例的個(gè)數(shù)。在本文的工作中，尚未保存在案例庫(kù)中的新案例稱(chēng)為目標(biāo)案例(new case,簡(jiǎn)稱(chēng)NC)，同時(shí)將圖書(shū)館參考咨詢案例庫(kù)分成訓(xùn)練集和測(cè)試集兩部分，訓(xùn)練集表示為T(mén)rainCase={casei|casei?Case,i∈[1,numtrain],numtrain

定義5圖書(shū)館參考咨詢案例檢索詞集合：給定num_q個(gè)檢索詞，圖書(shū)館參考咨詢案例檢索詞集合定義如下：Q={q1,q2,..,qnum_q}，其中qi=(subjecti,predicatei,objecti),i=1,2,…,num_q表示第i個(gè)檢索詞，subjecti、predicatei和objecti分別表示檢索詞的主語(yǔ)、謂語(yǔ)和賓語(yǔ)。

定義6圖書(shū)館參考咨詢案例匹配結(jié)果質(zhì)量度量技術(shù)：給定案例參考匹配結(jié)果Refer和案例匹配結(jié)果ReturnCase(指案例匹配的結(jié)果)，圖書(shū)館參考咨詢案例匹配結(jié)果的查全率r(ReturnCase,Refer)、查準(zhǔn)率p(ReturnCase,Refer)、度量f(ReturnCase,Refer) 分別定義如下[9]：

f(ReturnCase,Refer)=

公式(1)-(3)中：|Refer∩ReturnCase|表示匹配結(jié)果參考匹配結(jié)果的交集個(gè)數(shù)；|Refer|表示參考匹配結(jié)果的個(gè)數(shù)；|ReturnCase|表示匹配結(jié)果的個(gè)數(shù)。

定義7概念語(yǔ)義相似度和案例相似度：概念語(yǔ)義相似度是概念間可以互相替換的程度[10]。通過(guò)綜合考慮兩個(gè)概念的語(yǔ)義距離、節(jié)點(diǎn)深度和節(jié)點(diǎn)密度[11]來(lái)度量它們之間的概念語(yǔ)義相似度。

(1)語(yǔ)義距離是指在本體概念層次樹(shù)中，概念ni和nj到兩者最近共同父節(jié)點(diǎn)的路徑長(zhǎng)度distance(ni,nj)。如果distance(ni,nj)越小，即概念的語(yǔ)義距離越小，其相似度越大；反之則相似度越小。

(2)節(jié)點(diǎn)深度是指在本體概念層次樹(shù)中某一概念節(jié)點(diǎn)ni所處層次集Fdepth(depth=1,2,…) 到根節(jié)點(diǎn)的路徑長(zhǎng)度depth。若兩個(gè)節(jié)點(diǎn)ni和nj的層次數(shù)之和depth(ni)+depth(nj) 越大，對(duì)應(yīng)的概念之間的相似度則越大；若兩個(gè)節(jié)點(diǎn)的層次數(shù)之差|depth(ni)-depth(nj)| 越小，對(duì)應(yīng)概念之間的相似度則越大。

(3)節(jié)點(diǎn)密度是指在本體概念層次樹(shù)中，概念節(jié)點(diǎn)ni和nj的共同父節(jié)點(diǎn)擁有的子節(jié)點(diǎn)密度。則二者的節(jié)點(diǎn)密度定義如下：

其中：p是指以概念節(jié)點(diǎn)ni和nj的共同父節(jié)點(diǎn)為根節(jié)點(diǎn)的子樹(shù)所包含的除根節(jié)點(diǎn)以外的節(jié)點(diǎn)個(gè)數(shù)；q是指節(jié)點(diǎn)ni、nj和它們共同父節(jié)點(diǎn)之間所構(gòu)成樹(shù)的最大層次差。

在研究中，給出兩個(gè)概念節(jié)點(diǎn)ni和nj，它們之間的概念語(yǔ)義相似度度量公式定義如下[12]：

給定歷史案例HC和目標(biāo)案例NC，二者的案例相似度定義如下：

式中，

simallconcept=max(simconcept(hcsubject,

ncsubject),simconcept(hcsubject,ncobject))+

max(simconcept(hcobject,ncsubject),

simconcept(hcobject,ncobject))+

max(simconcept(ncsubject,hcsubject),

simconcept(ncsubject,hcobject))+

max(simconcept(ncobject,hcsubject),

simconcept(ncobject,hcobject))

其中：hcsubject表示歷史案例中的主語(yǔ)；hcobject表示歷史案例中的賓語(yǔ)；ncsubject表示目標(biāo)案例的主語(yǔ)；ncobject表示目標(biāo)案例的賓語(yǔ)；simconcept表示主賓間相似度，用公式(5)計(jì)算。

2 基于本體和微粒群算法的改進(jìn)KNN技術(shù)

基于改進(jìn)KNN的案例檢索策略分兩個(gè)步驟：基于改進(jìn)PSO的參數(shù)訓(xùn)練步驟和案例測(cè)試步驟。已知檢索詞集合的前提下，首先利用改進(jìn)PSO算法和案例訓(xùn)練集TrainCase尋優(yōu)得到參數(shù)集合A；然后基于給定的案例測(cè)試集TestCase，利用訓(xùn)練的參數(shù)集合A和TestCase中某一案例檢索，得到該案例的匹配案例集合。該技術(shù)的框架圖如圖1所示。

2.1 案例檢索策略中確定參數(shù)集合的單目標(biāo)優(yōu)化模型

在案例檢索過(guò)程中，如何確定KNN檢索策略中由相似度權(quán)重、K值和閾值組成的最優(yōu)參數(shù)集合，使得測(cè)試集中所有案例的檢索結(jié)果質(zhì)量最優(yōu)是案例檢索策略中的關(guān)鍵問(wèn)題。基于明顯的觀察結(jié)果，結(jié)果案例的數(shù)量和結(jié)果案例間的相似度同案例匹配結(jié)果質(zhì)量相關(guān)，因此針對(duì)該問(wèn)題提出的單目標(biāo)優(yōu)化模型數(shù)學(xué)形式如下：

圖1 基于改進(jìn)KNN的案例檢索策略框架圖Fig.1 The framework of improved KNN-based case retrieval strategy

其中：X是參數(shù)集合向量(x1,x2,…,xn)T，xi(i=1,2,…,n-2) 是概念相似度影響因素i的權(quán)重，xn-1是KNN策略中K值，xn是用于過(guò)濾同目標(biāo)案例相似度值太低的源案例的閾值；f(X) 是訓(xùn)練集中所有案例匹配結(jié)果的平均質(zhì)量，其度量函數(shù)定義如下：

式中：valuel(l=1,2,…,numtrain) 表示訓(xùn)練集中案例casel的評(píng)價(jià)值，其計(jì)算公式如下：

2.2 改進(jìn)的自適應(yīng)慣性權(quán)重的微粒群優(yōu)化算法

在設(shè)置了以上變量后，粒子的慣性權(quán)重依據(jù)以下原則賦值：

(1)若f(k)(xi)>f(k)frontxavg，說(shuō)明該粒子屬于種群中優(yōu)秀的粒子，該粒子的下一取值要趨近于收斂，w取值范圍內(nèi)的最小值0.4。

(2)若f(k)(xi)

(3)若f(k)behindxavg≤f(k)(xi)≤f(k)frontxavg，說(shuō)明該粒子處于中等水平，正在逐步尋優(yōu)，因此其取值按如下改進(jìn)的公式計(jì)算：

其中：wmax，wmin分別為初始慣性權(quán)重和終止慣性權(quán)重，本文wmax取值為0.9，wmin取值為0.4，k為當(dāng)前迭代次數(shù)，itermax為最大迭代次數(shù)。

通過(guò)以上的改進(jìn)，防止當(dāng)前迭代中粒子適應(yīng)度變差的粒子引導(dǎo)繼續(xù)向更差的方向移動(dòng)，有效的降低了無(wú)效迭代的次數(shù)。同時(shí)，收斂速度加快，結(jié)果更穩(wěn)定。改進(jìn)的自適應(yīng)慣性權(quán)重的PSO算法流程如圖2。

圖2 改進(jìn)的PSO算法流程圖Fig.2 Comparison of the matching result’s quality by f-measure among three schemes

3 實(shí)驗(yàn)結(jié)果與分析

選用的測(cè)試數(shù)據(jù)集(圖書(shū)館參考咨詢數(shù)據(jù))是由福州曉峰科技信息咨詢有限公司提供的圖書(shū)館領(lǐng)域的相關(guān)知識(shí)。在案例的句法結(jié)構(gòu)信息中，動(dòng)詞是其他成分(主語(yǔ)，賓語(yǔ)等名詞)的基礎(chǔ)，能直接影響案例匹配的正確率[19]。依據(jù)上述內(nèi)容將測(cè)試數(shù)據(jù)分為兩類(lèi)來(lái)評(píng)價(jià)案例匹配模塊的結(jié)果質(zhì)量：(1)測(cè)試案例僅含有一個(gè)動(dòng)詞；(2)測(cè)試案例有兩個(gè)及以上的動(dòng)詞。

每個(gè)測(cè)試用例由目標(biāo)案例、檢索詞集合及參考匹配結(jié)果組成，分別表示用戶咨詢問(wèn)題、經(jīng)過(guò)分詞擴(kuò)展模塊后的檢索詞集合和由專(zhuān)家確定的標(biāo)準(zhǔn)匹配結(jié)果。表1給出了本文測(cè)試用例的詳細(xì)描述。

表1 測(cè)試用例描述Tab.1 The description of test cases

續(xù)表

編號(hào)目標(biāo)案例檢索詞集合參考匹配結(jié)果204如何查詢外文引文索引文獻(xiàn)的“收錄號(hào)”?(#,查詢,文獻(xiàn))(#,查詢,收錄號(hào))(如何查詢外文引文索引文獻(xiàn)的“收錄號(hào)”?)(如何查找國(guó)內(nèi)外標(biāo)準(zhǔn)文獻(xiàn)?)(如何找到與課題相關(guān)的文獻(xiàn)?)205圖書(shū)條碼號(hào)、索書(shū)號(hào)有什么含義?(#,有,圖書(shū)條碼號(hào))(#,有,含義)(圖書(shū)條碼號(hào),有,含義)(#,有,索書(shū)號(hào))(索書(shū)號(hào),有,含義)圖書(shū)條碼號(hào)、索書(shū)號(hào)有什么含義?

改進(jìn)PSO的算法參數(shù)如下：

(1)基于本體的概念語(yǔ)義相似度度量的調(diào)節(jié)參數(shù)a用于調(diào)節(jié)概念相似度值，a取值越大概念相似度值語(yǔ)義距離趨近于1的速度越快[20]，取值為1時(shí)相似度效果最好。

(2)粒子群種群規(guī)模及最大進(jìn)化代數(shù)的設(shè)定與問(wèn)題的規(guī)模成正比，設(shè)定值偏小會(huì)影響結(jié)果的質(zhì)量，設(shè)定值偏大影響結(jié)果運(yùn)行的效率。種群規(guī)模建議范圍為[5,20],最大進(jìn)化代數(shù)建議范圍為[500,2 000]。由于本文的問(wèn)題規(guī)模不大(僅有5個(gè)參數(shù)需要確定)，因此種群規(guī)模及最大進(jìn)化代數(shù)分別設(shè)置為10個(gè)個(gè)體和1 000次迭代。

(3)wmax是慣性權(quán)重w的初始值，wmin為粒子進(jìn)化到最大迭代數(shù)的慣性權(quán)重值，當(dāng)wmax=0.9，wmin=0.4時(shí)優(yōu)化問(wèn)題取得最好的效果[21]，因此本文取值為wmax=0.9，wmin=0.4。

(4)學(xué)習(xí)因子c1,c2分別表示粒子個(gè)體向局部最優(yōu)和全局最優(yōu)位置移動(dòng)的能力，一般設(shè)為相同的值，常見(jiàn)的設(shè)定為2[22]。

(5)隨機(jī)因子r1,r2是也是影響粒子“自我學(xué)習(xí)”和“社會(huì)學(xué)習(xí)”的能力，一般取值為[0,1]之間的隨機(jī)數(shù)[23]。

表2中的數(shù)據(jù)是基于句法結(jié)構(gòu)過(guò)濾的KNN(方案1)、基于改進(jìn)PSO的KNN(方案2)及基于句法結(jié)構(gòu)和改進(jìn)PSO的KNN(方案3)3種方法的匹配結(jié)果的f度量(查全率，查準(zhǔn)率)，其中本文的方法是在每個(gè)測(cè)試用例上獨(dú)立運(yùn)行10次后的平均f度量值。從表2可以看出，方法3的匹配結(jié)果的f度量值都明顯優(yōu)于方案1和方案2，說(shuō)明基于改進(jìn)PSO的KNN檢索策略明顯優(yōu)于標(biāo)準(zhǔn)的KNN策略。此外，從方案3的f值比對(duì)中可以看出所有測(cè)試案例都遠(yuǎn)遠(yuǎn)高于方案2(至少高出25%)，該數(shù)據(jù)證明利用句法結(jié)構(gòu)(動(dòng)詞)過(guò)濾候選案例集可以很大程度的提高匹配的質(zhì)量。

表2 通過(guò)f度量值比較3種方案的匹配結(jié)果質(zhì)量Tab.2 Comparison of matching result’s quality by f-measure among three schemes

圖3通過(guò)比較方案2和方案3得出有無(wú)句法結(jié)構(gòu)過(guò)濾策略對(duì)所有案例測(cè)試獨(dú)立運(yùn)行10次后的平均運(yùn)行時(shí)間(時(shí)間單位為ms)影響，從該圖3可以看出經(jīng)過(guò)句法結(jié)構(gòu)過(guò)濾案例候選集的方案3的大部分遠(yuǎn)遠(yuǎn)低于未過(guò)濾案例候選集的方案2。本文測(cè)試案例庫(kù)的規(guī)模為233個(gè)案例，若是案例庫(kù)的規(guī)模更大，未預(yù)先經(jīng)過(guò)句法結(jié)構(gòu)過(guò)濾的方案其運(yùn)行速度將非常慢，從而影響算法的效率。圖4通過(guò)比較標(biāo)準(zhǔn)PSO和本文改進(jìn)的PSO進(jìn)化代數(shù)與獨(dú)立運(yùn)行10次后的平均適應(yīng)度值的變化關(guān)系。從該圖4可以得出標(biāo)準(zhǔn)的PSO算法無(wú)效進(jìn)化代數(shù)多，且易陷入局部最優(yōu)，無(wú)法收斂到全局最優(yōu)解，而改進(jìn)的PSO算法收斂的最優(yōu)解略高于標(biāo)準(zhǔn)的PSO，在不到600代就達(dá)到了最優(yōu)解。

圖3 通過(guò)運(yùn)行時(shí)間比較3種方案的匹配效率Fig.3 Comparison of matching efficiency under the running time among three schemes

圖4 基于標(biāo)準(zhǔn)PSO和改進(jìn)PSO的適應(yīng)度值對(duì)比圖Fig.4 The comparison of the fitness value between standard PSO and improved PSO

綜上所述，本文提出的兩個(gè)創(chuàng)新技術(shù)(利用句法結(jié)構(gòu)過(guò)濾案例候選集和利用改進(jìn)的PSO優(yōu)化KNN參數(shù))不僅能夠確定的質(zhì)量?jī)?yōu)于傳統(tǒng)KNN和基于傳統(tǒng)PSO的KNN方案的案例匹配結(jié)果，還能顯著提高案例匹配過(guò)程的效率。因此，改進(jìn)PSO的KNN檢索策略在案例推理中能更高效率的獲取到高質(zhì)量的案例匹配結(jié)果。

4 結(jié)論

針對(duì)KNN檢索策略中檢索效率低、缺乏隱含語(yǔ)義以及有人為因素的權(quán)重取值3個(gè)缺陷，提出了一種基于本體和微粒群算法的改進(jìn)KNN檢索策略。首先，基于圖書(shū)館領(lǐng)域本體的背景條件下，利用經(jīng)過(guò)中文分詞及查詢擴(kuò)展步驟得到的檢索詞集合中的謂語(yǔ)過(guò)濾案例庫(kù)，得到初步案例候選集；然后為了避免相似度度量技術(shù)中參數(shù)設(shè)定包含人為因素影響，提出并設(shè)計(jì)了一種改進(jìn)的微粒群優(yōu)化算法，并利用改進(jìn)PSO優(yōu)化度量技術(shù)中的參數(shù)以提高案例匹配的準(zhǔn)確率。實(shí)驗(yàn)數(shù)據(jù)采用的是福州曉鋒科技信息咨詢有限公司提供的圖書(shū)館參考咨詢測(cè)試數(shù)據(jù)。實(shí)驗(yàn)結(jié)果表明，相比于傳統(tǒng)KNN和基于傳統(tǒng)PSO的KNN方案，本方案有效地提高了案例匹配結(jié)果的查全率和查準(zhǔn)率。

[1] 楊斌宇.基于案例的推理在智能決策支持系統(tǒng)中的應(yīng)用[D].長(zhǎng)春:吉林大學(xué),2004.

[2] 王津津.案例推理在決策支持系統(tǒng)中的應(yīng)用研究[D].合肥:合肥工業(yè)大學(xué),2010.

[3] 李鋒剛,倪志偉,郜巒.基于案例推理和多策略相似性檢索的中醫(yī)處方自動(dòng)生成[J].計(jì)算機(jī)應(yīng)用研究,2010,27(2):544-547.

[4] 張春曉.案例推理的認(rèn)知改進(jìn)策略及學(xué)習(xí)性能研究[D].北京:北京工業(yè)大學(xué),2014.

[5] 李小展.基于文本挖掘的醫(yī)學(xué)診療案例推理系統(tǒng)的研究與應(yīng)用[D].廣州:廣東工業(yè)大學(xué),2011.

[6] 費(fèi)玉蓮.面向電子商務(wù)的談判支持系統(tǒng)研究[D].杭州:浙江工商大學(xué),2011.

[7] 李景.領(lǐng)域本體的構(gòu)建方法與應(yīng)用研究[D].北京:中國(guó)農(nóng)業(yè)科學(xué)院,2009.

[8] 崔巍.基于Peer-to-Peer網(wǎng)和地理ontology的系統(tǒng)集成和互操作研究[J].計(jì)算機(jī)工程與應(yīng)用,2003,39(32):45-47.

[9] 薛醒思.基于進(jìn)化算法的本體匹配問(wèn)題研究[D].西安:西安電子科技大學(xué),2014.

[10] 楊美榮,邵洪雨,史建鋒,等.改進(jìn)的領(lǐng)域本體概念相似度計(jì)算模型研究[J].情報(bào)科學(xué),2014,32(5):72-77.

[11] 唐中林.基于本體的概念相似度計(jì)算方法的研究[D].武漢:武漢理工大學(xué),2013.

[12] 陳沈焰,吳軍華.基于本體的概念語(yǔ)義相似度計(jì)算及其應(yīng)用[J].微電子學(xué)與計(jì)算機(jī),2008(12):96-99.

[13] 董穎,唐加福,許寶棟,等.一種求解非線性規(guī)劃問(wèn)題的混合粒子群優(yōu)化算法[J].東北大學(xué)學(xué)報(bào)(自然科學(xué)版),2003,24(12):1141-1144.

[14] 關(guān)圣濤,楚紀(jì)正,邵帥.粒子群優(yōu)化算法在非線性模型預(yù)測(cè)控制中的研究應(yīng)用[J].北京化工大學(xué)學(xué)報(bào)(自然科學(xué)版),2007,34(6):653-656.

[15] 王書(shū)斌,單勝男,羅雄麟.基于T-S模糊模型與粒子群優(yōu)化的非線性預(yù)測(cè)控制[J].化工學(xué)報(bào),2012,63(S0):176-187.

[16] Shi Yuhui,Eberhart R C.Fuzzy adaptive particle swarm optimization[C]∥Proceedings of the 2001 Congress on Evolutionary Computation.Washington D C：IEEE,2001:101-106.

[17] 劉偉,周育人.一種改進(jìn)慣性權(quán)重的PSO算法[J].計(jì)算機(jī)工程與應(yīng)用,2009,45(7):46-48.

[18] 申丹丹,石躍祥,周文杰,等.基于適應(yīng)值引導(dǎo)的粒子群改進(jìn)算法[J].計(jì)算機(jī)工程與應(yīng)用,2015,51(14):63-66.

[19] 龔小謹(jǐn),羅振聲,駱衛(wèi)華.漢語(yǔ)句子謂語(yǔ)中心詞的自動(dòng)識(shí)別[J].中文信息學(xué)報(bào),2003,17(2):7-13.

[20] 張帆,鐘金宏,黃玲.改進(jìn)的領(lǐng)域本體概念相似度計(jì)算方法[J].計(jì)算機(jī)工程,2010,36(23):66-68.

[21] 胡建秀,曾建潮.微粒群算法中慣性權(quán)重的調(diào)整策略[J].計(jì)算機(jī)工程,2007,33(11):193-195.

[22] 黃少榮.粒子群優(yōu)化算法綜述[J].計(jì)算機(jī)工程與設(shè)計(jì),2009,30(8):1977-1980.

[23] 王杰文,李赫男.粒子群優(yōu)化算法綜述[J].現(xiàn)代計(jì)算機(jī)(專(zhuān)業(yè)版),2009,30(2):22-27.

[24] 王家超.基于事例推理在甲型H1N1流感診斷中的應(yīng)用研究[D].沈陽(yáng):東北大學(xué),2010.

(特約編輯：黃家瑜)

DesignandimplementationofacasematchingmodulebasedonimprovedKNN

Xie Kaichi,Xue Xingsi

(College of Information Science and Engineering,Fujian University of Technology,Fuzhou 350118,China)

To improve the efficiency and quality of case retrieval,an improved KNN retrieval strategy was proposed.By introducing library domain ontology and concept semantic similarity measurement technology,cases’ syntactic structure was employed to filter out the unreasonable cases to reduce the computation amount (search space) and improve the case retrieval (alignment’s) quality.Then,an improved particle swarm algorithm was presented to determine the optimal aggregating parameters in the similarity measure technologies to improve the case alignment’s quality.In the experiment,the testing cases were from Fuzhou Xiaofeng Science and Technology Information Consulting Ltd.,Co,.The experimental results show that compared with the traditional KNN and the traditional PSO-based KNN,the proposal can significantly improve the case alignment’s quality in terms of both recall and precision.

case based reasoning;K nearest neighbourhood;particle swarm algorithm

TP182

A

1672-4348(2017)04-0349-09

10.3969/j.issn.1672-4348.2017.04.009

2017-05-26

國(guó)家級(jí)大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計(jì)劃項(xiàng)目(201610388024)

薛醒思(1981-)，男，福建福清人，副教授，博士,研究方向：智能計(jì)算和本體技術(shù)的研究與應(yīng)用。