基于函數(shù)S-粗集的Bellman 原理優(yōu)化算法在知識測度的應(yīng)用

1、第2期田民格：基于函數(shù)S-粗集的Bellman原理優(yōu)化算法在知識測度的應(yīng)用.449.基于函數(shù)S-粗集的Bellman原理優(yōu)化算法在知識測度的應(yīng)用田民格(三明學(xué)院 數(shù)學(xué)與計算機科學(xué)系,福建 三明 365004)摘要：應(yīng)用函數(shù)雙向S-粗集理論實現(xiàn)參考模式和測試模式的動態(tài)模式匹配，用Bellman原理的動態(tài)規(guī)劃算法實現(xiàn)全局約束定義下的Levenstein距離的計算，以此確定出參考模式和測試模式的距離測度，有明顯降低計算復(fù)雜度的效果，并以無紙考試系統(tǒng)非標(biāo)準(zhǔn)化試題的智能評分為例進行說明。關(guān)鍵詞：S-粗集; Bellman原理; Levenstein距離; 計算復(fù)雜度中圖分類號：0159文獻(xiàn)標(biāo)識碼：A文章

2、編號：1673-4343(2008)04-0447-04The Application of Optimization Algorithm Based on Function S-Rough Sets Bellman PrincipleTian Min-ge(Department of Mathematics and Computer Science,Sanming University,Sanming 365004,China)Abstract: Function S-Rough Sets realizes dynamic template matching between referenc

3、e template and test template,then calculates the Levenstein distance with dynamic programming algorithm of Bellman principle and finds the Knowledge distance measure which can reduce the compute complexity greatly. It ends in the intelligence estimate of nonstandardization test questions of no paper

4、 examination system.Key words: S-Rough Sets; Bellman principle; Levenstein distance; computation complexity收稿日期：作者簡介:田民格(1969-),男,福建大田人,講師Pawlak1粗集作為處理不確定性和不精確性問題的重要理論，在知識發(fā)現(xiàn)的理論與應(yīng)用研究等領(lǐng)域中已經(jīng)取得了許多成果，而史開泉教授的S-粗集2-4理論則大大地拓寬了動態(tài)系統(tǒng)的數(shù)據(jù)挖掘、知識發(fā)現(xiàn)、模式識別等領(lǐng)域的研究，特別是函數(shù)雙向S-粗集5，很好地解決了邊界知識問題和知識的遷移問題，而對知識測度的優(yōu)化算法上，在相關(guān)的文獻(xiàn)中都沒

5、有給出討論，這就需要對函數(shù)雙向S-粗集進行拓展。本文給出了用函數(shù)雙向S-粗集理論實現(xiàn)知識測度的方法，并給出了用Bellman原理的動態(tài)規(guī)劃算法實現(xiàn)知識測度的優(yōu)化算法。1 函數(shù)S-粗集1.1 函數(shù)S-粗集與它的結(jié)構(gòu)設(shè)D是有限函數(shù)論域，是函數(shù)集，R是D上的屬性集，u是R一函數(shù)等價類，稱分別是的下近似、上近似，而且稱集合對()為的R-函數(shù)粗集，稱是的R-邊界。1.2 函數(shù)單向S-粗集給定函數(shù)集，R是定義在D上的函數(shù)等價關(guān)系，u是R一函數(shù)等價類，是定義在D上的函數(shù)遷移，稱，分別是的下近似、上近似，而且稱集合對是的函數(shù)單向S-粗集，稱=-是的R-邊界。1.3函數(shù)雙向S-粗集給定函數(shù)集，R是定義在D上的函

6、數(shù)等價關(guān)系，u是R一函數(shù)等價類，是定義在D上的函數(shù)遷移，稱，分別是的下近似、上近似，而且稱集合對是的函數(shù)雙向S-粗集，稱-是的R-邊界。2 Bellman原理的動態(tài)規(guī)劃算法求距離測度62.1 模式的距離測度模式是由一系列的識別符號串或特征向量(串模式)組成的。設(shè)參考模式的特征向量序列為r(i)，i=1,2,I，設(shè)測試模式的特征向量序列為t(j)，j=1,2,J，則可用d(i,j)表示參考模式元素i與測試模式元素j之間的距離，通常用距離越小表示兩模式相應(yīng)特征向量越匹配，也有一些實例選擇距離越大表示兩模式相應(yīng)特征向量越匹配。一般IJ。設(shè)(ik,jk)|k=0,1,f表示從節(jié)點(i0,j0)到點節(jié)(

7、if,jf)的一條測試路徑，并以此得出該路徑對應(yīng)的全程代價函數(shù)D為求兩模式的最優(yōu)距離測度，必須選擇最優(yōu)路徑，為此必須遍歷所有可能的測試路徑。在不考慮函數(shù)遷移的情況下，即使用函數(shù)S-粗集情況下，這個過程的計算量就已經(jīng)很高，若再考慮函數(shù)遷移，即使用函數(shù)雙向S-粗集，則其計算量更高，而在知識測度中必須考慮函數(shù)遷移，否則將無法準(zhǔn)確測試出特征向量為同義詞和反義詞時的模式距離。減少計算復(fù)雜度的有效工具之一就是基于Bellman原理的動態(tài)規(guī)劃算法。2.2 Bellman動態(tài)規(guī)劃算法設(shè)從節(jié)點(i0,j0)到節(jié)點(if,jf)的一條最優(yōu)化路徑可表示為則通過節(jié)點(i,j)的最優(yōu)化約束路徑可表示為Bellman原理

8、描述為其中表示路徑的串聯(lián)。Bellman原理敘述為：經(jīng)過節(jié)點(i,j)的從節(jié)點(i0,j0)到點節(jié)(if,jf)的最優(yōu)路徑是，一條從節(jié)點(i0,j0)到點節(jié)(i,j)的最優(yōu)路徑與由節(jié)點(i,j)到點節(jié)(if,jf)的最優(yōu)路徑的串聯(lián)。其推論就是如果找到了從節(jié)點(i0,j0)到點節(jié)(i,j)的最優(yōu)路徑，則僅僅需要找到從節(jié)點(i,j)到點節(jié)(if,jf)的最優(yōu)路徑。設(shè)從節(jié)點(i0,j0)到點節(jié)(if,jf)的最優(yōu)路徑的測度為，則其中表示從節(jié)點(ik,jk)到點節(jié)(ik-1,jk-1)的測度(也叫轉(zhuǎn)移代價)。由上式可知最優(yōu)路徑的搜索僅僅在節(jié)點的子集中進行，用全局約束定義，而相鄰節(jié)點間的轉(zhuǎn)移則用局部約束

9、定義，這就Bellman原理的動態(tài)規(guī)劃(dynamic programming)算法。根據(jù)Bellman原理的動態(tài)規(guī)劃算法表達(dá)式可知是一個遞歸的算法。2.3 Levenstein距離Levenstein距離也稱為編輯距離。設(shè)兩個模式A和B之間的Levenstein距離為D(A,B)，則D(A,B)定義為由模式A向模式B轉(zhuǎn)換的過程中需要改變的符號個數(shù)C、插入的符號個數(shù)I和刪除的符號個數(shù)R的總和的最小值，其中j包含由A到B所有符號改變的可能組合。上式可用Bellman的動態(tài)規(guī)劃算法以求所需要的最小值，其第一步是根據(jù)具體問題規(guī)定節(jié)點轉(zhuǎn)移約束。根據(jù)具體的情況可采用下面的約束：(1) 節(jié)點(0,0)的代

10、價D(0,0)是0；(2) 搜索完整路徑；(3) 每個節(jié)點(i,j)僅可以通過三個節(jié)點到達(dá)，即(i-1,j-1),(i-1,j), (i,j-1)相應(yīng)的三個轉(zhuǎn)移代價是在距離最小值匹配中，若對應(yīng)于節(jié)點(i,j)的符號相同或特征向量匹配，則轉(zhuǎn)移代價是0；若不匹配，則為1。在動態(tài)規(guī)劃過程中，結(jié)合約束條件和編輯距離，得到計算Levenstein距離的算法如下。D(0,0)=0For i=1 to ID(i,0)=D(i-1,0)+1End ForFor j=1 to JD(0,j)=D(0,j-1)+1End ForFor j=1 to I For j=1 to J c1=D(i-1,j-1)+d(i

11、,j|i-1,j-1) c2=D(i-1,j)+1 c3=D(i,j-1)+1 D(i,j)=min(c1,c2,c3) End ForEnd ForD(A,B)=D(I,J)3 實例說明使用函數(shù)雙向S-粗集和Bellman原理的動態(tài)規(guī)劃算法實現(xiàn)知識測試的應(yīng)用很多，如無紙考試系統(tǒng)非標(biāo)準(zhǔn)化試題的智能評分、粗?jǐn)?shù)據(jù)內(nèi)外挖掘、粗搜索引擎的設(shè)計等。下面以無紙考試系統(tǒng)非標(biāo)準(zhǔn)化試題的智能評分為例進行說明。設(shè)D是所有可能答案構(gòu)成的論域，Q是參考模式即標(biāo)準(zhǔn)答案通過等價類劃分構(gòu)成的集合，也就是將參考模式的特征向量序列r(i)劃分成若干個等價類，每個等價類構(gòu)成標(biāo)準(zhǔn)答案的一部分，如設(shè)某個英譯漢考題，題面是“He is

12、 fat,she is beautiful.”，則它的標(biāo)準(zhǔn)答案是“他是胖的，她是漂亮的”，則可以產(chǎn)生一個等價類劃分是(他,是,胖的),(她,是,漂亮的)，即集合Q=(他,是,胖的)，(她,是,漂亮的)，則Q的下近似R-(Q)=(他,胖)，(她,漂亮)，Q的上近似R-(Q)=(他,確實,是,胖的)，(她,確實,是,漂亮的)。設(shè)有一函數(shù)f:美麗漂亮F，則原本“美麗”Q，但通過F函數(shù)遷移，使f(美麗)=漂亮Q，因此通過使用函數(shù)單向S-粗集的理論而增加的部分答案=(她,是,美麗的)，因此完整的答案等價類=(他,是,胖的)，(她,是,漂亮的)，(她,是,美麗的)。類似地，設(shè):胖肥，也就是原本“胖”Q，但

13、通過函數(shù)遷移，使(胖)=肥Q，因此通過使用函數(shù)雙向S-粗集的理論而減少的部分答案(即錯誤的答案)=(他,是,肥的)，則最終答案等價類=(他,是,胖的)，(她,是,漂亮的)，(她,是,美麗的)-(他,是,肥的)。需要特別說明的是，這里的表示的意義是考生所給的答題是中的一個子集，但不應(yīng)該出現(xiàn)答題，也就是若考生出現(xiàn)答題，則意味著不是不得分問題，而是可能要倒扣分的問題(如，可能的評判標(biāo)準(zhǔn)是，不回答不得分，非嚴(yán)重性答錯或與題目無關(guān)的答題不得分也不扣分，嚴(yán)重性答錯倒扣分)。按照如上例子，若考生答題特征向量序列是(他,是,肥的)，(她,是,美麗的)，則若按S-粗集評判，考生兩部分答題都不符合標(biāo)準(zhǔn)答案，不得分

14、；若按函數(shù)單向S-粗集考生答對了問題的后面一半，可得一半的分?jǐn)?shù)；若按函數(shù)雙向S-粗集考生答對了問題的后面一半，理應(yīng)可得一半的分?jǐn)?shù)，同時考生又答了不應(yīng)該答的前一半“(他,是,肥的)”，則前一半答題可能是要倒扣分的。因此，Q*的下近似=(他,胖)，(她,漂亮)，(她,美麗)-(他,肥)，Q*的上近似=(他,確實,是,胖的)，(她,確實,是,漂亮的)，(她,確實,是,美麗的)-(他,確實,是,肥的)。在測試模式中最優(yōu)的匹配模式即考生答題與標(biāo)準(zhǔn)答案的Levenstein距離的模式是：(他,是,胖的)，(她,是,漂亮的)，(她,是,美麗的)-(他,是,肥的)因此，可以的正確答題是“他是胖的，她是漂亮的”

15、或“他是胖的，她是美麗的”及其上下近似，但不包含遷移出的等價類(他,是,肥的)。參考模式的特征向量序列可劃分為r(i)|i=1,2,I=(他,是,胖的),(她,是,漂亮的)測試模式的特征向量序列則應(yīng)根據(jù)考生具體答題來確定和劃分，可能的劃分是t(i)|j=1,2,J=(他,是,肥的),(她,確實,是,美麗的)由此可知參考模式和測試模式的元素一般是不等的，Levenstein距離一般也不是最小的(最匹配的)。4 結(jié)束語函數(shù)雙向S-粗集理論在參考模式和測試模式的動態(tài)模式匹配上有著越來越廣泛的應(yīng)用，用Bellman原理的動態(tài)規(guī)劃算法實現(xiàn)全局約束定義下的Levenstein距離的計算，以此確定出參考模式

16、和測試模式的Levenstein距離，實踐證明，在減少計算復(fù)雜度上有比較明顯的效果。參考文獻(xiàn)：1 PAWLAK Z.Rough Sets J.International Journal of International Sciences,1982,(11):341-3562 SHI Kai-quan.Srough Sets and its Application in Diagnosis-Recognition for DiseaseJ.IEEE Proce-edings of the First International Conferences onMachine Learning and Cybernetics,2002,4(1):50-54.3 SHI Kai-quan.CUI Yu-quan.One Direction S-Rough Decision and Its Decision ModelJ.IEEE Proce-edings of the Third International Conferences onMachine Learning and Cybernetics,2002,4(1):50-5