引論：我們?yōu)槟砹?3篇匹配算法論文范文，供您借鑒以豐富您的創(chuàng)作。它們是您寫作時(shí)的寶貴資源，期望它們能夠激發(fā)您的創(chuàng)作靈感，讓您的文章更具深度。

篇1

1KMP算法

最簡(jiǎn)單的樸素串匹配算法(BF算法)是從主串的第一個(gè)字符和模式串的第一個(gè)字符進(jìn)行比較，若相等則繼續(xù)逐個(gè)比較后續(xù)字符，否則從主串的第二個(gè)字符起再重新和模式串的第一個(gè)字符進(jìn)行比較。依次類推，直至模式串和主串中的一個(gè)子串相等，此時(shí)稱為匹配成功，否則稱為匹配失敗。樸素模式匹配算法匹配失敗重新比較時(shí)只能向前移一個(gè)字符，若主串中存在和模式串只有部分匹配的多個(gè)子串，匹配指針將多次回溯，而回溯次數(shù)越多算法的效率越低，它的時(shí)間復(fù)雜度一般情況下為O((n-m+1)m)（注：n和m分別為主串和模式串的長(zhǎng)度），最壞的情況下為O(m*n)，最好的情況下為O(m+n)。KMP模式匹配算法正是針對(duì)上述算法的不足做了實(shí)質(zhì)性的改進(jìn)。其基本思想是：當(dāng)一趟匹配過程中出現(xiàn)失配時(shí)，不需回溯主串，而是充分利用已經(jīng)得到的部分匹配所隱含的若干個(gè)字符，過濾掉那些多余的比較，將模式串向右“滑動(dòng)”盡可能遠(yuǎn)的一段距離后，繼續(xù)進(jìn)行比較，從而提高模式匹配的效率，該算法的時(shí)間復(fù)雜度為O(m+n)。

那么如何確定哪些是多余的比較？在KMP算法中通過引入前綴函數(shù)f(x)來確定每次匹配不需要比較的字符，保證了匹配始終向前進(jìn)行，無須回溯。假設(shè)主串為s1s2，sn.，模式串為t1t2，tm.，其中m≦n，從si+1開始的子串遇到一個(gè)不完全的匹配，使得：

(1.1)

如果我們能確定一個(gè)最小的整數(shù)，使得：

(1.2)

其中，所以確定i''''等價(jià)于確定k，這里的k值就是我們要求的前綴函數(shù)f(x)。由式1.1和1.2中K值與主串s無關(guān)，只與給定的模式串t中與主串匹配的q有關(guān)，即k=f(q)，

f(q)=max{i|0iq且t[1..i]是t[1..q]的后綴}(1.3)

確定KMP前綴函數(shù)的算法如下：

#defineMAXSIZE100

Typedefunsignedcharstring[MAXSIZE+1];//0號(hào)單元用來存放串的長(zhǎng)度

voidf(sstringt,int*array)

{

m=t[0];//m為當(dāng)前模式串的長(zhǎng)度

array=(int*)malloc((m+1)*sizeof(int));//0號(hào)元不用

array[1]=0;k=0;

for(q=2;q<=m;q++)

{while(k>0&&t[k+1]!=t[q])k=array[k];

if(t[k+1]==t[q])k=k+1;

array[q]=k;

}

}

關(guān)于KMP算法的前綴函數(shù)f(x)的示例見表1。

當(dāng)模式串中有i個(gè)字符串匹配成功，第i+1個(gè)字符不匹配時(shí)，則從i-f(i)個(gè)字符重新開始比較，這樣不僅無須回溯，而且一次可以向前滑動(dòng)i-f(i)個(gè)字符，大大提高了模式匹配的效率。下面給出樸素匹配算法和KMP匹配算法的比較，見表2。

表2樸素匹配算法和KMP匹配算法比較表

樸素算法KMP算法

時(shí)間復(fù)雜度O((n-m+1)m)O(m+n)

向前移動(dòng)字符個(gè)數(shù)1q-f(q)

回溯次數(shù)q-1無

其中：n為主串長(zhǎng)度，m為模式串長(zhǎng)度，q為匹配成功的字符個(gè)數(shù)

2KMP算法的改進(jìn)

在KMP算法的實(shí)際應(yīng)用中，發(fā)現(xiàn)該算法也存在著不足，結(jié)合下面的表一來論述KMP模式匹配算法的改進(jìn)。假設(shè)模式串前4個(gè)字符與主串的第i+1..i+4匹配成功，第5個(gè)字符匹配失敗，此時(shí)前綴函數(shù)f(4)=1，下一次匹配將從第i+4開始，并直接將模式串中的第2個(gè)字符與主串中的第i+5個(gè)字符進(jìn)行比較，從表1中可知，匹配必將失敗，此次比較是多余的。這說明此時(shí)的前綴函數(shù)f(x)并不是最優(yōu)，需要對(duì)前綴函數(shù)進(jìn)行改進(jìn)。實(shí)質(zhì)上，所謂對(duì)KMP算法的改進(jìn)就是對(duì)其前綴函數(shù)的改進(jìn)。

4結(jié)語

本文給出的算法較樸素匹配算法在效率上有了較大的提高，尤其是對(duì)重復(fù)字符出現(xiàn)較少的數(shù)據(jù)段進(jìn)行模式匹配可取得較高的查找效率。應(yīng)用于大型數(shù)據(jù)庫的數(shù)據(jù)查詢，會(huì)更加有效地縮短查找時(shí)間。

參考文獻(xiàn)

[1]嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].清華大學(xué)出版社，2001

篇2

引言

雙目視覺是一種通過兩幅圖像獲取物體三維信息的方法，具有通過二維圖像認(rèn)知物體三維立體信息的能力，其關(guān)鍵技術(shù)就是要解決兩幅圖像中對(duì)應(yīng)點(diǎn)的匹配問題［1］。立體匹配一直都是機(jī)器視覺領(lǐng)域中的難點(diǎn)和熱點(diǎn)，論文根據(jù)結(jié)合變電站及巡檢機(jī)器人雙目視覺系統(tǒng)的特點(diǎn)，運(yùn)用匹配輔助區(qū)域匹配算法實(shí)現(xiàn)立體匹配，獲得密集準(zhǔn)確的深度圖。

1、立體匹配原理

立體匹配基于視差原理，如圖1所示。其中基線距B=兩攝像機(jī)的投影中心連線的距離；攝像機(jī)焦距為f。設(shè)兩攝像機(jī)在同一時(shí)刻觀看空間物體的同一特征點(diǎn)，分別在“左眼”和“右眼”上獲取了點(diǎn)的圖像，它們的圖像像素坐標(biāo)分別為

采用平行攝像機(jī)模型，兩攝像機(jī)的圖像在同一個(gè)平面上，并且特征點(diǎn)p的圖像坐標(biāo)y坐標(biāo)在左右圖像平面上相同，

可以得到：

要想根據(jù)左右圖像對(duì)完成立體匹配任務(wù)，就把只需計(jì)算左右圖像對(duì)的立體視差，立體視差是景物點(diǎn)在左右圖像中圖像像素的橫坐標(biāo)之差，即：

從而就可以建立立體視差圖(又稱深度圖)。所建立的立體視差圖可以細(xì)分為兩個(gè)子區(qū)域，零視差子區(qū)域和非零視差子區(qū)域，零視差子區(qū)域?yàn)闄C(jī)器人可以自由行走的無障礙平坦區(qū)域；非零視差子區(qū)域?yàn)槠教箙^(qū)域上的凸出區(qū)域，可能是障礙物存在的區(qū)域。

根據(jù)式(3)及立體視差原理，可以方便地計(jì)算世界坐標(biāo)下的特征點(diǎn)在攝像機(jī)坐標(biāo)系下的三維坐標(biāo)：

左攝像機(jī)像面上的任意一點(diǎn)只要能在右攝像機(jī)像面上找到對(duì)應(yīng)的匹配點(diǎn)，就可以確定出該點(diǎn)的三維坐標(biāo)。這種方法是完全的點(diǎn)對(duì)點(diǎn)運(yùn)算，像面上所有點(diǎn)只要存在相應(yīng)的匹配點(diǎn)，就可以根據(jù)式(5)計(jì)算出對(duì)應(yīng)的三維坐標(biāo)。

2、立體匹配設(shè)計(jì)

經(jīng)過圖像預(yù)處理，可以為立體匹配提供較理想立體圖像對(duì)，降低了匹配算法的難度。論文結(jié)合變電站、檢機(jī)器人雙目視覺系統(tǒng)的特點(diǎn)，運(yùn)用特征輔助區(qū)域匹配算法實(shí)現(xiàn)立體匹配，該算法結(jié)合特征匹配算法及區(qū)域匹配算法的優(yōu)點(diǎn)，可以在計(jì)算量不大的情況下，生成密集準(zhǔn)確的立體視差圖。

算法的總體上分三步：

2.1 匹配初始化階段

匹配初始化階段需要完成以下工作：對(duì)雙目攝像機(jī)參數(shù)的標(biāo)定；對(duì)攝像機(jī)所采用的圖像運(yùn)用高斯―拉普拉斯模板進(jìn)行圖像預(yù)處理；對(duì)預(yù)處理的圖像運(yùn)用加速主成分分析法實(shí)現(xiàn)圖像的特征提取；這些過程都是為后面的立體匹配做準(zhǔn)備，為之提供較理想的立體圖像對(duì)。

2.2 特征匹配階段

根據(jù)各種匹配準(zhǔn)則縮小匹配點(diǎn)的搜索范圍，利用特征匹配算法確定正確的匹配點(diǎn)。

2.3 區(qū)域匹配階段

由于前面特征提取算法限制，不可能把景物所有特征點(diǎn)全部提取到，所以特征點(diǎn)匹配完成后，還存在一些有價(jià)值的非特征點(diǎn)未被匹配。但是這些未被匹配點(diǎn)被已匹配點(diǎn)限制在較小的范圍內(nèi)，對(duì)這些小范圍點(diǎn)的匹配就是區(qū)域匹配算法的工作。

對(duì)多個(gè)可能的候選匹配點(diǎn)比較時(shí)，可能使用的依據(jù)有灰度、曲率、拉普拉斯變換、梯度等。結(jié)合變電站實(shí)際環(huán)境，運(yùn)用連續(xù)性約束準(zhǔn)則和灰度、x方向的灰度梯度、梯度方向唯一確定匹配點(diǎn)［2］。思路如下：

①┍算視覺連續(xù)性約束相關(guān)系數(shù)

其中d為已匹配點(diǎn)的視差均值，d為當(dāng)前候選匹配點(diǎn)的視差。若，1為預(yù)先設(shè)定視覺連續(xù)性約束相關(guān)系數(shù)閾值，排除此候選匹配點(diǎn)，重復(fù)執(zhí)行此步直到時(shí)，執(zhí)行第2步；否則直接執(zhí)行第2步執(zhí)行。

②計(jì)算候選匹配點(diǎn)與待匹配點(diǎn)的灰度相關(guān)值Vcorr、x方向的灰度梯度接近程度系數(shù)Kgard_r、梯度方向相關(guān)系數(shù)式(7)-(8)中，K_gard_x、K_gard_y為基準(zhǔn)圖像上特征點(diǎn)x和y方向的梯度，Rgrad_x、Rgrad_y為候選匹配點(diǎn)x和y方向的梯度，fl、fr為左右圖像的灰度函數(shù)，、為特征點(diǎn)和候選匹配點(diǎn)在窗口(2N+2M+1)中灰度均、為兩點(diǎn)在窗口中灰度標(biāo)準(zhǔn)差。若有Vcorr

③計(jì)算總判斷依據(jù)

計(jì)算出所有候選匹配點(diǎn)的Iall值，其Iall值最大者即認(rèn)為是最佳候選匹配點(diǎn)，即特征點(diǎn)Pleft在右圖像中的匹配點(diǎn)。

要匹配固定大小的圖像窗口中的像素，相似約束準(zhǔn)則是兩幅圖像在窗口中的相關(guān)性度量，當(dāng)被搜索區(qū)域的點(diǎn)與待匹配點(diǎn)間相似約束準(zhǔn)則最大化時(shí)，認(rèn)為搜索區(qū)域的點(diǎn)是待匹配點(diǎn)的匹配點(diǎn)［3］。

設(shè)有立體圖像對(duì)IMG1、IMGr，Pl、Pr為兩幅圖像中的像素點(diǎn)，相關(guān)窗口大小為，為圖像IMGl中像素點(diǎn)Pl在圖像3、實(shí)驗(yàn)與結(jié)果

圖2中左右兩圖像，是左右攝像機(jī)對(duì)同一景物拍攝所得。

根據(jù)上圖的左右兩圖，運(yùn)用立體匹配算法求得立體視差圖。實(shí)驗(yàn)結(jié)果如圖3所示，其中左圖像素深度圖，右圖是對(duì)左圖經(jīng)median處理后的效果圖，看起來對(duì)左圖清晰了不少，但不能顯示真實(shí)圖像視差關(guān)系。此算法消耗較長(zhǎng)時(shí)間，將在以后工作中改進(jìn)。

參考文獻(xiàn)

［1］楊俊,賈秀芳.變電站防火防盜圖像識(shí)別的研究.中國(guó)高等學(xué)校電力系統(tǒng)及其自動(dòng)化專業(yè)第20屆學(xué)術(shù)年會(huì)，2004.7.

［2］林琳.機(jī)器人雙目視覺定位技術(shù)研究［D］．西安電子科技大學(xué)碩士學(xué)位論文,2009.

篇3

1 引言

在現(xiàn)有的畢業(yè)論文選題系統(tǒng)中，一個(gè)學(xué)生只能選擇一個(gè)題目作為自己最終的題目，同樣，一個(gè)題目只能分配給一個(gè)學(xué)生。如果最后題目由學(xué)生自己確定，那就會(huì)出現(xiàn)先選的學(xué)生具有更大的選擇余地，后選的學(xué)生由于不能再選已經(jīng)選定的題目，所以其可選擇的題目會(huì)越來越少，這對(duì)很多學(xué)生來說很不公平。如果學(xué)生選擇自己的志愿，最終題目由老師來定，這不但加大了老師的工作量，而且還是不能保證每位同學(xué)的公平性。如何采用計(jì)算機(jī)智能輔助選題，設(shè)計(jì)最優(yōu)匹配算法實(shí)現(xiàn)學(xué)生與題目的整體最優(yōu)匹配，會(huì)大大提高選題的效率。

湯穎曾在《畢業(yè)設(shè)計(jì)立項(xiàng)與選題管理及其支持系統(tǒng)》中提出，采用模糊匹配技術(shù)進(jìn)行學(xué)生-題目的自動(dòng)匹配；潘志方在《一種改進(jìn)的Ford-Fulkenson算法在選題系統(tǒng)中的應(yīng)用研究》中將題目與學(xué)生的匹配抽象為二分圖的匹配，并采用改進(jìn)的Ford-Fulkenson算法實(shí)現(xiàn)題目與學(xué)生的自動(dòng)匹配。以上兩種方法只考慮了學(xué)生與題目之間的最大匹配值，并沒有考慮學(xué)生的整體滿意度最優(yōu)的情況。

本文將通過采用最優(yōu)匹配算法（KM）確定一種匹配方案，使得學(xué)生的整體滿意度最高。具體方法概括如下：學(xué)生預(yù)選多個(gè)題目，并根據(jù)自己對(duì)題目的滿意度由高到底排序，這樣，滿意度成為二分圖的一分值，如圖1所示：

2 系統(tǒng)功能模塊設(shè)計(jì)

根據(jù)前期的可行性分析，本系統(tǒng)主要進(jìn)行以下模塊的設(shè)計(jì)：系統(tǒng)管理員模塊、專業(yè)負(fù)責(zé)人管理模塊、指導(dǎo)教師管理模塊和學(xué)生選題模塊。

系統(tǒng)管理員模塊主要負(fù)責(zé)對(duì)系統(tǒng)參數(shù)的設(shè)置及用戶的管理。主要實(shí)現(xiàn)以下功能：

（1）系統(tǒng)設(shè)置：對(duì)系統(tǒng)標(biāo)題、畢業(yè)生、選題參數(shù)設(shè)置；

（2）學(xué)院及專業(yè)設(shè)置：完成學(xué)院、專業(yè)的添加、刪除、修改操作；

（3）數(shù)據(jù)字典的維護(hù)：教師信息、選題難度、選題方向燈信息的維護(hù)；

（4）教師和學(xué)生的管理：完成教師、學(xué)生信息的添加、刪除和修改操作；

（5）文件文化建設(shè)管理：日志文件查看、上傳文件的管理。

專業(yè)負(fù)責(zé)人管理模塊與系統(tǒng)管理員權(quán)限相似，但操作的數(shù)據(jù)只能針對(duì)于指定專業(yè)，無法瀏覽及操作整個(gè)學(xué)院的課題及學(xué)生信息。最重要的功能是實(shí)現(xiàn)題目的審核。

導(dǎo)師管理模塊主要用于選題以及選擇自己選題學(xué)生的審核確認(rèn)。

（1）個(gè)人中心管理：如信息修改及密碼重置；

（2）選題管理：選題的增加、修改、刪除以及選題類型的設(shè)置；

（3）學(xué)生選題查詢及審核。

學(xué)生模塊主要實(shí)現(xiàn)學(xué)生選題的選擇及確認(rèn)。

（1）學(xué)生個(gè)人信息的修改；

（2）學(xué)生選題及確認(rèn)信息查詢；

（3）學(xué)生留言及咨詢。

3 KM算法在系統(tǒng)中的實(shí)現(xiàn)

KM算法由Kuhn和Munkras分別提出來，這是一種問題。經(jīng)典的算法。該算法由通過每個(gè)頂點(diǎn)一個(gè)頂標(biāo)（A[i][j]）來求最大權(quán)匹配的問題轉(zhuǎn)化為不斷尋找增廣道路以使二分圖的匹配數(shù)達(dá)到最大的完備匹配。KM算法的關(guān)鍵在于不斷尋找二分圖中的可增廣道路。如果找到一條可增廣道路，就可以額將屬于和不屬于相等子圖的邊取相反，從而相等子圖里就是增加一條邊，一直到所有的頂點(diǎn)都進(jìn)入相等子圖為止。

KM算法可以很好地解決選題系統(tǒng)中，題目與學(xué)生最優(yōu)匹配的問題。下面以國(guó)際商學(xué)院09級(jí)本科學(xué)生選題為例。

在匹配過程中，設(shè)學(xué)生的集合為X={X1，X2，X3……Xn}，選題的集合設(shè)置為Y={Y1，Y2，Y3……Yn}，學(xué)生對(duì)自己選題的滿意度為二維矩陣Z[m][n]，其他題目規(guī)定權(quán)值為0。系統(tǒng)規(guī)定學(xué)生最多可預(yù)選3個(gè)題目，并按照滿意度分別設(shè)置0.9，0.7，0.5。以下表1是對(duì)國(guó)際經(jīng)濟(jì)與貿(mào)易專業(yè)使用不同算法得出的學(xué)生滿意程度。

下面對(duì)以上數(shù)據(jù)進(jìn)行說明。如采用手工分配的方式，使得681名學(xué)生中414名同學(xué)分的了題目，滿意度為60.82%；如果采用最大匹配算法進(jìn)行分配，可以使分配數(shù)達(dá)到最大，有517名學(xué)生分得題目，滿意度上升為79.99%；最有用最有匹配算法進(jìn)行分配，使總體滿意度達(dá)到78.24%，533人。需要說明的一點(diǎn)是，KM算法只是找到了整體最優(yōu)匹配而不是最大數(shù)匹配，如果整體最優(yōu)情況下匹配數(shù)和最大匹配數(shù)相差得太大的話，那么整體最優(yōu)方案顯得不太可取。所以，最好的情況就是同時(shí)考慮最優(yōu)匹配和最大匹配來同時(shí)控制兩者的大小。

4 結(jié)語

本系統(tǒng)實(shí)現(xiàn)了畢業(yè)論文選系統(tǒng)工作的各個(gè)管理功能，通過實(shí)現(xiàn)教師與學(xué)生的雙向選擇，使用KM算法，提高選題的質(zhì)量和效率，為學(xué)院充分利用網(wǎng)絡(luò)完成畢業(yè)論文選題工作提供了便利的平臺(tái)。

參考文獻(xiàn)：

[1]湯穎.畢業(yè)設(shè)計(jì)立項(xiàng)與選題管理及支持系統(tǒng)[J].合肥工業(yè)大學(xué)學(xué)報(bào)，2006，29（5）.

篇4

1 引言

突發(fā)公共衛(wèi)生事件應(yīng)急系統(tǒng)的建立對(duì)于保障公共安全，建設(shè)社會(huì)主義和諧社會(huì)具有特殊重要的現(xiàn)實(shí)意義。目前國(guó)內(nèi)外在應(yīng)急響應(yīng)領(lǐng)域已經(jīng)取得了很大的進(jìn)步，但對(duì)應(yīng)急預(yù)案系統(tǒng)的研究才剛剛處于起步階段。作為整個(gè)系統(tǒng)中最為基礎(chǔ)和根本的一環(huán)，應(yīng)急預(yù)案對(duì)于應(yīng)急響應(yīng)的實(shí)施具有重要作用。

本文通過對(duì)現(xiàn)有應(yīng)急預(yù)案和應(yīng)急響應(yīng)過程的分析，通過框架技術(shù)對(duì)應(yīng)急預(yù)案的知識(shí)進(jìn)行表示，研究了預(yù)案的匹配算法，給出了預(yù)案相似度以及價(jià)值評(píng)估的計(jì)算方法。

2 智能預(yù)案匹配

應(yīng)急預(yù)案是應(yīng)急事件處置的領(lǐng)域知識(shí)來源。應(yīng)急預(yù)案管理系統(tǒng)可以在對(duì)處置預(yù)案、資源分布轉(zhuǎn)臺(tái)、事件處置狀態(tài)自動(dòng)初步生成事件處置方案。再經(jīng)過處置人員對(duì)初步方案進(jìn)行調(diào)整，經(jīng)過認(rèn)可后即可作為高效地應(yīng)急響應(yīng)處理的指導(dǎo)方案。

2.1 基于框架的匹配

預(yù)案采用框架的智能化存儲(chǔ)結(jié)構(gòu)表示，預(yù)案的智能匹配自然和框架體系的匹配息息相關(guān)。基于框架體系的匹配系統(tǒng)一般由兩大部分組成：

（1）由框架及其相互關(guān)聯(lián)構(gòu)成的知識(shí)庫。提供求解問題所需要的知識(shí)；

（2）由一組解釋程序構(gòu)成的框架推理機(jī)。針對(duì)用戶提出的問題，通過運(yùn)用知識(shí)庫中的相關(guān)知識(shí)完成求解問題的任務(wù)，給出問題的解；

2.2 匹配過程及算法

3.2 數(shù)據(jù)相似度研究

預(yù)案是介于數(shù)據(jù)與知識(shí)之間的一種知識(shí)存在形式，存儲(chǔ)預(yù)案的框架結(jié)構(gòu)具有不同數(shù)據(jù)類型的槽和側(cè)面屬性。計(jì)算不同數(shù)據(jù)類型屬性的相似度，首先要討論屬性即槽值和側(cè)面值的數(shù)據(jù)類型。一般來說，屬性的數(shù)據(jù)類型分為以下三個(gè)大類。針對(duì)以上三大類型，分別來討論其相似度算法。

4 結(jié)論

本文主要論述了智能預(yù)案框架表示與預(yù)案知識(shí)匹配機(jī)制。通過對(duì)現(xiàn)有應(yīng)急預(yù)案和應(yīng)急響應(yīng)過程的分析，提出一個(gè)對(duì)應(yīng)急預(yù)案的描述方法。利用框架結(jié)構(gòu)完整的描述預(yù)案實(shí)體單元，依據(jù)各框架間的縱向聯(lián)系和橫向聯(lián)系，從而形成框架網(wǎng)絡(luò)。利用框架知識(shí)表示，研究了預(yù)案的智能匹配與相似度比對(duì)。最后討論了預(yù)案相似度算法，給出了預(yù)案相似度以及價(jià)值評(píng)估的計(jì)算方法，討論了預(yù)案框架中不同數(shù)據(jù)類型屬性的相似度算法，重點(diǎn)研究了數(shù)值類型和文本類型的屬性相似度算法。

參考文獻(xiàn)

[1]Nilsson NJ. Artificial Intelligence： A New Synthesis[M].Copyrighted Matenal，2000.

[2]Sui YF，Gro Y， Cao CG.Ontologies， Frames and Logical Theories in NKI[J].Journal of Software，2005，16（12）.

[3]李晨陽，曹忠升，馮玉才.一種基于框架和中間件模型的知識(shí)庫系統(tǒng)[J].計(jì)算機(jī)應(yīng)用，2000（12）：1298-1300.

[4]張榮梅.基于CBR與MAS的智能決策支持系統(tǒng)研究及應(yīng)用[D]：[碩士學(xué)位論文].北京：北京科技大學(xué)，2001.

[5]劉義剛.基于預(yù)案庫的快速智能決策支持系統(tǒng)的研究[D]：[碩士學(xué)位論文].北京：北京理工大學(xué)，2001.

[6]楊健，趙秦怡.基于案例的推理技術(shù)研究進(jìn)展及應(yīng)用[J].計(jì)算機(jī)工程與設(shè)計(jì)，2008，29（3）：710.

篇5

摘要：分析了畢業(yè)論文選題系統(tǒng)的特點(diǎn)，引入了學(xué)生及指導(dǎo)教師對(duì)選題結(jié)果的滿意度，建立了一個(gè)以總體滿意度最大為目標(biāo)的畢業(yè)論文選題系統(tǒng)模型，并在此基礎(chǔ)上設(shè)計(jì)實(shí)現(xiàn)了基于web的本科畢業(yè)論文選題系統(tǒng)。實(shí)際應(yīng)用表明，該系統(tǒng)可以有效的提高畢業(yè)論文選題的總體滿意度及選題質(zhì)量。

Abstract: The thesis analyzed the characteristics of graduation projects' selection system, introduced the satisfaction of student and instructor with the results on the topics, established a model of graduation projects' selection system which took the overall satisfaction as the goal, and on this basis, designed and implemented graduation projects' selection system for undergraduates based on web. The application showed that this system could effectively improve the overall satisfaction of thesis topics and the quality.

關(guān)鍵詞：滿意度 畢業(yè)設(shè)計(jì) 選題系統(tǒng) web

Key words: satisfaction；graduation project；selection systems；web

中圖分類號(hào)：TP39 文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1006-4311（2011）29-0147-02

0引言

畢業(yè)設(shè)計(jì)（論文）是高校培養(yǎng)學(xué)生的重要環(huán)節(jié)，隨著高校的擴(kuò)招，畢業(yè)論文選題的工作量也越來越大，以往的手工選題的方式已經(jīng)遠(yuǎn)遠(yuǎn)不能滿足高校畢業(yè)論文選題的需求。一個(gè)有效的方法是采用計(jì)算機(jī)智能選題系統(tǒng)，在畢業(yè)論文選題系統(tǒng)中，一個(gè)學(xué)生只能選擇一個(gè)題目作為自己的最終論文題目；同樣，一個(gè)題目也只能分配給一個(gè)學(xué)生。如果最終題目由學(xué)生自己確定，那么就會(huì)出現(xiàn)這樣的情況：先選的學(xué)生具有更大的選擇余地，后選的學(xué)生由于不能再選已經(jīng)選定的題目，所以其可選擇的題目會(huì)越來越少，這對(duì)很多學(xué)生來說是很不公平的。如果學(xué)生選擇自己的志愿，而最終題目由老師來定，這不但加大了老師的工作量，而且還是不能保證每位同學(xué)的公平性。如果采用計(jì)算機(jī)智能輔助選題，設(shè)計(jì)最優(yōu)匹配算法實(shí)現(xiàn)學(xué)生與題目的整體最優(yōu)匹配，無疑將大大提高選題的效率。

一些學(xué)者曾對(duì)題目的智能化匹配作過比較深入的研究，如湯穎采用模糊匹配技術(shù)進(jìn)行學(xué)生一題目的自動(dòng)匹配[1]；潘志方將題目與學(xué)生的匹配抽象為二分圖的匹配，并采用改進(jìn)的Ford-Fulkenson算法實(shí)現(xiàn)了題目與學(xué)生的自動(dòng)匹配[2]；楊勝超等將學(xué)生的滿意度引入到了畢業(yè)論文選題中[3]。但是，他們只是考慮了題目與學(xué)生的最大匹配數(shù)，并沒有同時(shí)考慮學(xué)生和教師整體滿意度最優(yōu)的情況，而教師的滿意度往往對(duì)選題質(zhì)量的控制起著關(guān)鍵作用。

本文在畢業(yè)論文選題系統(tǒng)中引入了學(xué)生和教師的滿意度，建立了在最有匹配基礎(chǔ)上的以滿意度最大為目標(biāo)的選題系統(tǒng)模型，給出了算法實(shí)現(xiàn)并將其應(yīng)用到了本科畢業(yè)論文選題系統(tǒng)的設(shè)計(jì)中，最后給出了畢業(yè)論文選題系統(tǒng)的具體實(shí)現(xiàn)，并進(jìn)行了實(shí)際測(cè)試。測(cè)試結(jié)果表明，該選題的應(yīng)用可以提高選題的總體滿意度和選題質(zhì)量。

1選題系統(tǒng)最大滿意度模型

設(shè)S為學(xué)生的集合，有sm屬于S，m屬于[1，M]，其中M為學(xué)生數(shù)。設(shè)T為題目的集合，有tn屬于T，n屬于[1，N]，其中N為論文題目總數(shù)。那么對(duì)于所有的選題情況有集合Anm，對(duì)于某一具體選題，學(xué)生滿意度Xnm，教師滿意度Ynm，那么Xnm+Ynm有最大值，max(Xnm+Ynm)。因此，該問題變成了求解滿意度最大值問題，并能確定在取得最大值情況下Anm的集合，也就是具體的每一個(gè)學(xué)生的對(duì)應(yīng)的唯一的選題。

2畢業(yè)論文選題系統(tǒng)的設(shè)計(jì)實(shí)現(xiàn)

2.1 系統(tǒng)用例該系統(tǒng)的用戶主要有三類，分別是系統(tǒng)管理員、普通教師和學(xué)生，系統(tǒng)用例說明如表1所示。

2.2系統(tǒng)流程設(shè)計(jì)基于最大滿意度的畢業(yè)設(shè)計(jì)選題系統(tǒng)，充分考慮了學(xué)生確定自己論文題目的自由性：學(xué)生可以自主命題由老師來審核，如果審核通過則可作為自己的最終論文題目，如果未通過審核還可以反過來參加預(yù)選或者再次自主命題（有最大自主命題數(shù)限制）。同時(shí)將教師對(duì)選題情況的評(píng)價(jià)引入，更加合理。同時(shí)還優(yōu)化了題目預(yù)選的匹配：通過管理員啟動(dòng)最大滿意度匹配算法，確定出學(xué)生與題目的最優(yōu)匹配方案，這樣便大大減輕了老師的工作量，提高了選題的效率。最后，如果通過以上兩個(gè)步驟還有學(xué)生沒有定題，就只有通過老師手動(dòng)確定學(xué)生的最終題目。

2.3 系統(tǒng)數(shù)據(jù)庫設(shè)計(jì)基于前邊的分析設(shè)計(jì)，我們需要設(shè)計(jì)到下列各表，這些表之間相互關(guān)聯(lián)，共同存儲(chǔ)著系統(tǒng)所需要的數(shù)據(jù)。在設(shè)計(jì)數(shù)據(jù)庫表的過程中，應(yīng)遵循以下幾條原則，數(shù)據(jù)庫設(shè)計(jì)一個(gè)表最好值存儲(chǔ)一個(gè)實(shí)體或?qū)ο蟮南嚓P(guān)信息，不同的實(shí)體最好存儲(chǔ)在不同的數(shù)據(jù)表中，如果實(shí)體還可以再分，實(shí)體的劃分原則是最好能夠比當(dāng)前系統(tǒng)要開發(fā)的實(shí)體的顆粒度要小，數(shù)據(jù)表的信息結(jié)構(gòu)一定要合適的，表的字段的數(shù)量一定不要過多，擴(kuò)充信息和動(dòng)態(tài)變化的信息一定要分開在不同的表里，對(duì)于多對(duì)多這樣的表關(guān)系系統(tǒng)盡量不出現(xiàn)。該系統(tǒng)中主要的數(shù)據(jù)表如表2-表5。

普通教師參數(shù)表保存的是用戶參數(shù)，UserID是用戶注冊(cè)時(shí)輸入的，作為該表的主鍵，表中記錄的用戶編號(hào)是不會(huì)相同的，這要求在用戶注冊(cè)時(shí)檢查欲注冊(cè)的用戶名是否已經(jīng)被注冊(cè)過，這是必要的一步。（故部分系統(tǒng)在注冊(cè)時(shí)要求用個(gè)人Email地址作為用戶ID，這樣重復(fù)的幾率非常低，但也是需要檢查的。）且UserID在其他表中也會(huì)用到。（表2）

學(xué)生參數(shù)表保存的是用戶參數(shù)，StID是用戶注冊(cè)時(shí)輸入的，作為該表的主鍵，表中記錄的用戶編號(hào)是不會(huì)相同的，這要求在用戶注冊(cè)時(shí)檢查欲注冊(cè)的用戶名是否已經(jīng)被注冊(cè)過，這是必要的一步。（表3）管理員參數(shù)表是管理員的一些注冊(cè)信息，其中Adminid是管理員編號(hào)，是該表的主鍵。其余各字段與普通教師參數(shù)表中的字段意義相同。（表4）

題目信息參數(shù)表是信息的各種參數(shù)，包括題目的編號(hào)（系統(tǒng)自動(dòng)生成），是該表的主鍵。題目的詳細(xì)內(nèi)容是對(duì)該題目的簡(jiǎn)單介紹，題目類別根據(jù)需要進(jìn)行設(shè)置。（表5）

2.4 系統(tǒng)實(shí)現(xiàn)最后，系統(tǒng)采用asp+access進(jìn)行了實(shí)現(xiàn)，具體實(shí)現(xiàn)過程由于篇幅所限，不再贅述。

3系統(tǒng)測(cè)試

該系統(tǒng)設(shè)計(jì)完成后，在榆林學(xué)院信息工程學(xué)院2010屆本科畢業(yè)生的畢業(yè)論文選題過程中進(jìn)行了實(shí)際的測(cè)試，測(cè)試數(shù)據(jù)如表6。

在此次測(cè)試中，共有學(xué)生96人，題目107個(gè)，從表中可以看出，采用手工分配方案，只有74個(gè)學(xué)生可以分得選題，而采用智能最大滿意度方案，有91人分得了選題（其余學(xué)生采用手工分配）；在滿意度方面，采用最大滿意度方案后，學(xué)生的整體滿意度和教師的整體滿意度均有較大提高。

4結(jié)束語

按照以上描述的設(shè)計(jì)思路和算法，采用Asp技術(shù)+Access后臺(tái)數(shù)據(jù)庫實(shí)現(xiàn)了畢業(yè)論文選題系統(tǒng)。該系統(tǒng)將選題結(jié)果學(xué)生和教師整體滿意度最大作為目標(biāo)，不但大大降低了整個(gè)選題過程的工作量，而且大大提高了學(xué)生及教師對(duì)選題結(jié)果的整體滿意度，從而提高了選題質(zhì)量。該系統(tǒng)在榆林學(xué)院信息工程學(xué)院2010屆計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)本科畢業(yè)生的畢業(yè)論文選題中進(jìn)行了應(yīng)用，取得了良好的效果。

參考文獻(xiàn)：

篇6

Research of the Text Subjective Question's Auto Remarking Algorithm Based on Word Segmentation Algorithm &VSM

LI Xue-jun

(Southwest University of Science and Technology, Mianyang 621010, China)

Abstract: The paper makes use of the studied results(such as Vector Space Model (VSM), Word Segmentation algorithm and so on) of the native language understanding, and applys them in processing the text subjective question's answer (including the standard answer and the student's answer), and then it used the text_charactered vector matching algorithm to auto remark those student's examining paper by the computer system. According to the experiment, the algorithm has accuracy of remarking and some valuable domains of application.

Key words: Auto-remarking; Word Segmentation algorithm; Vector Space Model (VSM); Text character matched

隨著計(jì)算機(jī)技術(shù)和互聯(lián)網(wǎng)技術(shù)迅猛發(fā)展，傳統(tǒng)教育模式發(fā)生了變化，越來越多的課程提出了在線考試的需求。計(jì)算機(jī)可以很好地完成客觀題（如選擇題、判斷題）的判分工作，其判分策略、關(guān)鍵技術(shù)及其應(yīng)用實(shí)例詳見文獻(xiàn)[1]至文獻(xiàn)[3]。亦即把考生作答的結(jié)果和題目標(biāo)準(zhǔn)答案進(jìn)行精確匹配從而得到考生的得分。文獻(xiàn)[4]提出了一種近似串匹配算法來對(duì)文本錄入題的自動(dòng)評(píng)分算法，其本質(zhì)還是進(jìn)行文本的比較，與客觀題的判分原理基本是相同的。

計(jì)算機(jī)自動(dòng)評(píng)分是指利用計(jì)算機(jī)程序來模擬人工評(píng)分的標(biāo)準(zhǔn)和內(nèi)部過程。對(duì)客觀題的評(píng)分是通過把試題的標(biāo)準(zhǔn)答案與考生的答案做一個(gè)精確比較，并據(jù)此作為是否給學(xué)生相應(yīng)的題目分值；對(duì)于主觀題，目前一般是讓考生把其作答的結(jié)果形成一個(gè)文件（答案文件），再通過網(wǎng)絡(luò)把考生的答案文件上傳到考試服務(wù)器中的專用目錄中，科任教師在考試結(jié)束后對(duì)考生的答案文件進(jìn)行人工評(píng)判來進(jìn)行給分；最后把考生客觀題的計(jì)算機(jī)自動(dòng)評(píng)分結(jié)果和主觀題的人工評(píng)分結(jié)果累加起來作為考生的最終成績(jī)。對(duì)于客觀題可以完全不要人工干預(yù)，而主觀題就必須在人工干預(yù)下才能完成。

因此本文就此提出將人工智能的自然語言理解技術(shù)（主要是分詞算法）、文本的空間向量模型表示和知識(shí)的框架表示內(nèi)容應(yīng)用到網(wǎng)絡(luò)考試系統(tǒng)中的主觀題的自動(dòng)評(píng)分過程中。

1 文本主觀題自動(dòng)評(píng)分原理

對(duì)于在線考試系統(tǒng)來說，其自動(dòng)評(píng)分是在特定范圍內(nèi)的，不需要讓其理解所有的自然語言，只需要理解標(biāo)準(zhǔn)答案即可。因此，應(yīng)該使用某種算法使標(biāo)準(zhǔn)答案轉(zhuǎn)化成機(jī)器能夠理解的形式，將考生答案也按照一定的規(guī)則轉(zhuǎn)化成計(jì)算機(jī)可以理解的形式，然后再將其和標(biāo)準(zhǔn)答案進(jìn)行匹配并評(píng)分。其關(guān)鍵是如何將評(píng)分規(guī)則轉(zhuǎn)化為可以被機(jī)器理解的知識(shí)庫。主觀題的自動(dòng)評(píng)分原理如圖1所示。

2 自動(dòng)分詞算法簡(jiǎn)介

2.1 最大匹配分詞算法

匹配分詞法是按照一定的策略將待切分的漢字串與一個(gè)“充分大的”機(jī)器詞典（如金山詞霸等）中的詞條進(jìn)行匹配，若在詞典中找到某個(gè)字符串，則匹配成功（識(shí)別出一個(gè)詞）。按照掃描方向的不同，串匹配分詞方法可以分為正向匹配和逆向匹配。按照不同長(zhǎng)度優(yōu)先匹配的情況，可以分為最大（最長(zhǎng)）匹配和最小（最短）匹配。最大匹配分詞法即先確定一個(gè)最大的詞的長(zhǎng)度，然后從左（正向）或從右（逆向）取該長(zhǎng)度的詞串，將詞串與詞典中的詞條匹配，如果沒有該詞則去掉一個(gè)字符繼續(xù)匹配，以此類推，直到達(dá)到匹配或剩下一個(gè)單字為止。

2.2 最大概率分詞算法

最大概率分詞算法的基本思想是：假設(shè)一個(gè)待切分的漢字串可能包含多種分詞結(jié)果，將其中概率最大的那個(gè)作為該字串的分詞結(jié)果。例如，有一個(gè)句子S＝“有意見分歧”，第一種分詞路徑W1＝“有/意見/分歧/”，第二種分詞路徑W2＝“有意/見/分歧/”，如圖2所示。到底應(yīng)該選擇哪一種為最后的分詞結(jié)果呢？

根據(jù)概率分詞算法的基本思想，需要計(jì)算每一種方法出現(xiàn)的選取概率的作為最后結(jié)果，即計(jì)算Max(P(W1|S), P(W2|S))。概率計(jì)算方法如圖3所示。

每一個(gè)詞匯出現(xiàn)的概率P(wi) 可以在帶詞頻的詞典中查出。通過查詞典可以得到每個(gè)詞的概率為：P(有)=0.0180，P(有意)=0.0005，P(意見)=,0.0010，P(見) =0.0002，P(分歧)=0.0001。

對(duì)于第一種分詞方法：P(w1) = P(有) * P(意見) * P(分歧) = 1.8×10-9；

對(duì)于第二種分詞方法：P(w2) = P(有意) * P(見) * P(分歧) = 1×10-11；

由上所示，P(w1) > P(w2)，所以取第一種方法作為分詞結(jié)果。

3 文本矢量特征匹配算法

主觀試題的答案以文本方式存儲(chǔ)，經(jīng)過分詞后的文本如何表示才能更加容易地被計(jì)算機(jī)處理關(guān)系到文本處理的準(zhǔn)確性，因此文本表示方法是自動(dòng)評(píng)分算法的一個(gè)關(guān)鍵問題。近年來，在Web文本信息特征獲取算法的研究中，矢量空間模型(Vector Space Model，VSM )[5-6]是應(yīng)用較多且效果較好的方法之一，本算法借鑒了該模型的思想。在矢量空間模型中，文本被看作由一組正交詞條所生成的矢量空間。根據(jù)這個(gè)思想，同時(shí)考慮到考試評(píng)分中經(jīng)常將試題答案分為幾個(gè)要點(diǎn)，因此提出主觀題成績(jī)?cè)u(píng)判模型為：

首先，答案文本是由一些要點(diǎn)組成，如果把答案文本（Answer text 用A來表示）看成一個(gè)由n個(gè)要點(diǎn)（Pi）組成的集合，則可以這樣表示答案：A={P1,P2,…,Pi,…,Pn}；設(shè)每個(gè)要點(diǎn)Pi的分值為Mi，則該答案的總分M為：；按照VSM思想，將標(biāo)準(zhǔn)答案每一個(gè)要點(diǎn)Pi被看成是由Ki個(gè)特征詞（wj）組成的向量P：；設(shè)每個(gè)特征詞的權(quán)重是wj（由經(jīng)驗(yàn)豐富的任課教師人工設(shè)置），則其歸一化權(quán)重為：；設(shè)考生答案的每一個(gè)要點(diǎn)Pi'也被看成是由Ki'個(gè)特征詞（wj'）組成的向量P'：；通過計(jì)算考生答案和標(biāo)準(zhǔn)答案的向量間的距離并據(jù)此計(jì)算考生可得到到該要點(diǎn)的分值，即：(如果向量間的距離為0，則說明考生答案和標(biāo)準(zhǔn)答案完全匹配，考生可以拿到該要點(diǎn)的所有分值)；考生所得總分M'為：。

4 算法測(cè)試及結(jié)論

本論文采用oracle作為后臺(tái)數(shù)據(jù)庫管理系統(tǒng)（因?yàn)橄到y(tǒng)所用的詞典數(shù)據(jù)庫都比較大），基于B/S模式設(shè)計(jì)了基于文本的主觀題自動(dòng)評(píng)分測(cè)試軟件。通過對(duì)不同名詞解釋題目（答案長(zhǎng)度及復(fù)雜度不同）的評(píng)測(cè)，再將本算法評(píng)得的分?jǐn)?shù)與人工評(píng)分相比，分?jǐn)?shù)的容差在（－0.5～＋0.5），可以測(cè)得其評(píng)分的準(zhǔn)確度在86.93％。通過實(shí)際的數(shù)據(jù)測(cè)試可以看出，答案越復(fù)雜，要點(diǎn)越多，評(píng)分的準(zhǔn)確性越差；相反，要點(diǎn)越少，答案越簡(jiǎn)單，評(píng)分的準(zhǔn)確性越好。而且人工設(shè)置關(guān)鍵詞和權(quán)重也有利有弊，人工設(shè)置固然增強(qiáng)了系統(tǒng)的準(zhǔn)確程度，但是其前提是設(shè)置人必須是有經(jīng)驗(yàn)的老師，如果是沒有經(jīng)驗(yàn)的老師設(shè)置，則給算法增加了人為的誤差。該算法具有一定的實(shí)用性，但還有待進(jìn)一步的完善。

參考文獻(xiàn)：

[1] 華蕊. 自動(dòng)組卷及評(píng)分系統(tǒng)的設(shè)計(jì)[J]. 中國(guó)電化教育.2002,(2):84-85.

[2] 朱映輝, 江玉珍.計(jì)算機(jī)自動(dòng)評(píng)卷策略分析與研究[J]. 電腦知識(shí)與技術(shù),2005,(35):30-32.

[3] 李丁. 計(jì)算機(jī)考試系統(tǒng)中自動(dòng)評(píng)分策略的研究與實(shí)現(xiàn)[J]. 廣東廣播電視大學(xué)學(xué)報(bào),2002,11(4):30-32.

篇7

Key words: immune theory clonal selection antibodies circulating complement

一、引言

人工免疫系統(tǒng)是一個(gè)新興的計(jì)算智能研究領(lǐng)域。近年來,人工免疫系統(tǒng)及其應(yīng)用已逐漸成為了智能信息系統(tǒng)中的研究熱點(diǎn)。生物免疫系統(tǒng)的免疫識(shí)別過程能在較短的時(shí)間內(nèi)利用數(shù)量相對(duì)有限的抗體去識(shí)別近乎無限多的抗原,從信息處理的角度看,這是在資源受限條件下的一整套高效問題求解機(jī)制。克隆選擇學(xué)說的基因重組、親和度成熟、受體編輯等機(jī)制較好地從個(gè)體層次上闡述了這種高效問題求解能力的形成,因而成為多種人工免疫系統(tǒng)模型和算法的重要思想來源,免疫算法就是一種借鑒該系統(tǒng)特性而形成的啟發(fā)式搜索算法.它具有保持種群分布多樣性的特性,避免陷入局部最優(yōu)解的優(yōu)點(diǎn)。

二、克隆選擇原理

克隆選擇是生物免疫系統(tǒng)理論的重要學(xué)說,其原理(如下圖1所示)的基本思想是只有那些能夠識(shí)別抗原的細(xì)胞才進(jìn)行擴(kuò)增,只有這些細(xì)胞才能被選擇并保留下來,而那些不能識(shí)別抗原的細(xì)胞則不選擇,也不進(jìn)行擴(kuò)增。骨髓中微小的“休眠”的B細(xì)胞每一個(gè)都載有一個(gè)不同的抗體類型。這些細(xì)胞載有對(duì)于抗原特異的受體,擴(kuò)增分化成漿細(xì)胞和記憶細(xì)胞。

免疫系統(tǒng)在成長(zhǎng)的克隆中也是自適應(yīng)的,同時(shí)也呈現(xiàn)了一種變異機(jī)制,在對(duì)抗體特異編碼的基因中產(chǎn)生極高頻率點(diǎn)變異。該機(jī)制(體細(xì)胞高頻變異)與為改進(jìn)抗原結(jié)合而進(jìn)行的選擇,共同導(dǎo)致細(xì)胞與抗原具有極高的親和力匹配。

根據(jù)免疫系統(tǒng)中的克隆選擇學(xué)說的思想,該算法在抗體種群和抗體優(yōu)秀決定基中進(jìn)行克隆選擇操作,全面的模擬了生物免疫系統(tǒng)克隆選擇的過程,很好的保持了抗體種群的多樣性。

三、克隆選擇算法

3.1 抗體/抗原匹配算法

要確定一個(gè)B細(xì)胞對(duì)象與提呈的抗原結(jié)合得有多好,在抗原上任何點(diǎn)開始匹配;匹配算法計(jì)算每一位,在抗原與抗體之間以互補(bǔ)的方式進(jìn)行匹配,得出匹配值,再?gòu)钠ヅ浞种档玫浇Y(jié)合值,根據(jù)抗體的結(jié)合值的大小可以看出抗體和抗原是否結(jié)合的完美,并且可以判定出結(jié)合完美的抗體中哪些決定基起到了關(guān)鍵的作用。

對(duì)于一個(gè)抗體結(jié)合一個(gè)抗原,結(jié)合必須是穩(wěn)定的,也就是匹配分值在匹配發(fā)生之前必須超過一定的閾值。該設(shè)定閾值為抗體大小的一半。該方法是Hightower的匹配算法的修改,只是多種偽生物匹配的一種。

抗體/抗原匹配算法的描述:

(1)初始化抗體群,針對(duì)抗體與抗原的決定基逐位進(jìn)行異或操作,若抗體和抗原相對(duì)應(yīng)的決定基相同為0,不同為1,結(jié)果統(tǒng)記為c;

(2)將抗體與抗原的決定基逐位進(jìn)行異或操作結(jié)果的累積和記為(公式一);

(3)對(duì)由兩個(gè)或者更多個(gè)1組成的每一區(qū)域記錄長(zhǎng)度為l;

(4)記抗體的結(jié)合度為(公式二);

(5)定義閾值為

(6)抗體Ab 移位一位。

3.2 克隆選擇算法的實(shí)現(xiàn)

克隆選擇算法的實(shí)質(zhì)是在進(jìn)化過程中,在每一代最優(yōu)解的附近,根據(jù)親和度的大小進(jìn)行克隆,產(chǎn)生一個(gè)變異解的群體,從而擴(kuò)大了搜索范圍(即增加了抗體的多樣性),有助于防止進(jìn)化的早熟和搜索限于局部極小值,同時(shí)通過克隆選擇來加快收斂速度。其基本思想為:隨機(jī)生成N個(gè)抗體組成的抗體群,對(duì)這些抗體進(jìn)行一些操作后,選出抗體中優(yōu)秀的決定基片段,針對(duì)這些優(yōu)秀的決定基片段進(jìn)行克隆操作,從而形成子抗體。克隆選擇操作只是在優(yōu)秀的抗體決定基中進(jìn)行,而不是在抗體的所有決定基中。

克隆選擇算法是根據(jù)克隆選擇原理和親和度的成熟發(fā)展而來的,其主要考慮了免疫方面的如下幾個(gè)方面:

(1)保持功能性的細(xì)胞從指令系統(tǒng)中分離;

(2)受刺激最強(qiáng)的個(gè)體進(jìn)行選擇和克隆;

(3)為受刺激的細(xì)胞死亡;

(4)親和力度較好的克隆個(gè)體重新選擇;

(5)多樣化的產(chǎn)生和保持。

克隆選擇算法的實(shí)現(xiàn)步驟(流程圖如圖2所示):

(1)初始化。隨機(jī)產(chǎn)生初始的抗體群(P);

(2)計(jì)算抗體與抗原的結(jié)合度。本文采用的抗體和抗原是否完美結(jié)合的匹配算法,是由Hightower提出的,對(duì)抗體和抗原逐位進(jìn)行異或操作,即抗體和抗原的決定基位相同記為0,不同記為1,若抗體和抗原結(jié)合,則其為1,根據(jù)公式一得出該抗體的匹配值,然后根據(jù)公式二可得到該組抗體和抗原的結(jié)合強(qiáng)度值(M);

(3)挖掘一個(gè)抗體中優(yōu)秀的決定基片段。根據(jù)抗體和抗原的結(jié)合的匹配程度,我們可以看出抗體與抗原能夠結(jié)合上的決定基位,算法中提到必須是兩個(gè)或者更多個(gè)連續(xù)結(jié)合的決定基片段才進(jìn)行挖掘提取(Pm)。

(4)對(duì)選擇出抗體的優(yōu)秀決定基的片段進(jìn)行克隆操作,產(chǎn)生一個(gè)暫時(shí)的克隆群體(C);

(5)隨機(jī)生成新的編碼融合進(jìn)暫時(shí)的克隆群體中,形成新的抗體群(Pn)。

3.3 抗體的循環(huán)補(bǔ)充

生物免疫系統(tǒng)中為了保持抗體的多樣性,每天都會(huì)產(chǎn)生大量的新的抗體注入到免疫系

統(tǒng)中,其中大多數(shù)抗體決定基的片段會(huì)因?yàn)榻Y(jié)合度太低而遭受到抑制,但仍有少數(shù)的抗體片段跟抗原具有很好的結(jié)合,獲得了克隆擴(kuò)增機(jī)會(huì)。為了模擬這一抗體循環(huán)補(bǔ)充機(jī)制,我們?cè)诿看螌?duì)優(yōu)秀抗體決定基片段的提取之后,再隨機(jī)產(chǎn)生的抗體決定基注入到提取出來的優(yōu)秀抗體決定基片段中,形成新的抗體進(jìn)入到克隆擴(kuò)增以及結(jié)合度成熟的過程中,以提高抗體的多樣性,實(shí)現(xiàn)全局范圍內(nèi)的搜索優(yōu)化,避免陷入局部最優(yōu)解。

四、克隆選擇算法運(yùn)行結(jié)果

圖3(a)中我們可以清楚的看到抗原與抗體是怎樣結(jié)合的,并找到了能夠完美結(jié)合的抗體中優(yōu)秀的決定基片段,根據(jù)算法的運(yùn)行可得出抗體與抗原的結(jié)合度為156。圖3(b)中可以看出算法能夠?qū)@些優(yōu)秀決定基片段進(jìn)行了挖掘。圖3(c)中算法實(shí)現(xiàn)克隆。圖3

(d)中隨機(jī)生成新的編碼融合進(jìn)暫時(shí)的克隆群體中,形成新的抗體群。

五、結(jié)束語

借鑒了生物免疫系統(tǒng)中的克隆選擇原理,從而設(shè)計(jì)了本算法。在文中詳細(xì)闡述了算法的實(shí)現(xiàn)步驟,并且該算法通過調(diào)試能正確的完成其功能輸出。但是該算法還沒有通過實(shí)例驗(yàn)證,在接下來的工作中,將本算法應(yīng)用到實(shí)例中,來判定算法的性能。

參考文獻(xiàn):

[1]韋巍,張國(guó)宏.人工免疫系統(tǒng)及其在控制系統(tǒng)中的應(yīng)用.控制理論與應(yīng)用,2002,19 (2):157-160

[2]莫宏偉.人工免疫系統(tǒng)原理與應(yīng)用.哈爾濱工業(yè)大學(xué)出版社.2003.1390

篇8

1、積相關(guān)算法概述

以圖像匹配為基礎(chǔ)的電視跟蹤方法,習(xí)慣上稱為電視圖像相關(guān)跟蹤,簡(jiǎn)稱為相關(guān)跟蹤。積相關(guān)算法是常見的相關(guān)算法中的一種,也叫歸一化相關(guān)算法:

相似性度量(x0,y0)的表達(dá)式為:

n~(x0,y0)=m-1X=0m-1y=0f(x,y)t(x+x0,y+y0)m-1X=0m-1y=0f2(x,y)m-1X=0m-1y=0t2(x+x0,y+y0)

其中,0≤x0≤n-m, 0≤y0≤n-m。如果把f(x,y)和t(x,y)分別看作兩個(gè)歐式空間里的矢量,那么積相關(guān)算法的度量值表達(dá)式正是這兩個(gè)矢量在歐式空間里夾角的余弦。這是一個(gè)非常有用的性質(zhì),它的實(shí)際意義是,當(dāng)環(huán)境光強(qiáng)發(fā)生變換時(shí)。應(yīng)用積相關(guān)算法可以不受干擾。

2、跟蹤穩(wěn)定性的研究

所謂跟蹤的穩(wěn)定性是指匹配點(diǎn)的位置是否能夠唯一確定或者在一個(gè)極小的范圍內(nèi)滑動(dòng)。研究系統(tǒng)跟蹤的穩(wěn)定性具有十分重要的意義。

2.1圖像預(yù)處理對(duì)跟蹤穩(wěn)定性的影響

在智能電視跟蹤系統(tǒng)中實(shí)現(xiàn)積相關(guān)算法時(shí),采取必要的圖像預(yù)處理是非常必要和有益的。對(duì)模板和實(shí)時(shí)圖像進(jìn)行灰度均衡,使相關(guān)峰變得尖銳,從而提高跟蹤性能;增大圖像的對(duì)比度,也可以使相關(guān)峰變得尖銳,從而提高跟蹤性能;對(duì)圖像進(jìn)行灰度最小化處理,使相關(guān)峰變得尖銳,提高跟蹤性能。

2.2模板選取對(duì)跟蹤穩(wěn)定性的影響

積相關(guān)跟蹤算法的模板需要人工在視場(chǎng)范圍內(nèi)進(jìn)行鎖定,這個(gè)初始的第一個(gè)模板對(duì)跟蹤效果也是有影響的。為了得到良好的跟蹤效果,相關(guān)峰應(yīng)當(dāng)盡量選擇在圖像比較復(fù)雜并且沒有規(guī)律的區(qū)域內(nèi)。

2.3奇偶場(chǎng)對(duì)跟蹤穩(wěn)定性的影響

系統(tǒng)采用的攝像頭是按照PAL-D制式進(jìn)行隔行掃描按照奇偶場(chǎng)產(chǎn)生圖像的。對(duì)一幅靜止的圖像如果采用隔場(chǎng)匹配,那么一個(gè)模板始終與奇數(shù)場(chǎng)或者偶數(shù)場(chǎng)的實(shí)時(shí)圖像進(jìn)行匹配,此時(shí)跟蹤點(diǎn)就始終是穩(wěn)定的。對(duì)于動(dòng)態(tài)的、連續(xù)的圖像,應(yīng)該在算法中加入一些處理措施,比如對(duì)模板進(jìn)行刷新,否則可能造成跟蹤不穩(wěn)定。

3、簡(jiǎn)化的快速積相關(guān)圖像匹配算法

基于前面給出的簡(jiǎn)化歸一化積相關(guān)度量方法,為了進(jìn)一步減少匹配算法匹配時(shí)間,提高匹配效率,且同時(shí)保證一定的匹配精度與匹配概率,設(shè)計(jì)了先粗后精的分層匹配控制策略。

3.1先粗后精的分層匹配控制策略

下圖中給出了匹配控制策略的設(shè)計(jì)框圖。

這種匹配控制策略首先是進(jìn)行粗匹配,確定匹配點(diǎn)的大概位置或候選位置,接著進(jìn)行精匹配,確定匹配點(diǎn)的精確位置或最佳位置。精匹配是在粗匹配的結(jié)果---候選匹配子圖中完成的,因而搜索范圍大大減少,提高了匹配速度。

對(duì)于本文算法,使用該方案需要注意以下三點(diǎn)。

(1) 粗匹配階段,為了保證精匹配階段的有效性,必須確保粗篩選后所保留的預(yù)選點(diǎn)包含有匹配點(diǎn)。

(2) 門限法實(shí)現(xiàn)起來難度較大,多數(shù)是靠大量實(shí)驗(yàn)及經(jīng)驗(yàn)獲取,且僅在特定的情況下可以采用。實(shí)際中,可以考慮采用3~5點(diǎn)篩選法,即直接取粗匹配階段度量值最優(yōu)的3~5個(gè)匹配點(diǎn)作為精匹配基準(zhǔn)點(diǎn)。

(3) 圖像的預(yù)處理是指對(duì)匹配圖像的灰度數(shù)據(jù)進(jìn)行一定的壓縮或特征提取。在粗匹配階段,可以考慮隔像素取值且隔像素搜索。而在精匹配階段,像素值及搜索范圍均要適當(dāng)擴(kuò)展。

3.2算法設(shè)計(jì)

結(jié)合簡(jiǎn)化的度量方法及前面給出的先粗后精的分層匹配控制方案,設(shè)計(jì)了簡(jiǎn)化的快速歸一化積相關(guān)圖像匹配算法。

(1) 粗匹配階段

計(jì)算總的匹配搜索次數(shù)(如對(duì)于大小分別為m×m和n×n的基準(zhǔn)圖與實(shí)時(shí)圖,則總的搜索次數(shù)為(m-n+1)×(m-n+1),進(jìn)行循環(huán)遞推匹配。匹配準(zhǔn)則如下。

①每隔n1像素從基準(zhǔn)圖左上角開始掃描獲取各個(gè)基準(zhǔn)子圖,并在實(shí)時(shí)圖及所選的基準(zhǔn)子圖中隔n2個(gè)像素取其滅度值,組成用于相關(guān)匹配的維數(shù)較小的灰度矢量。

②利用簡(jiǎn)化的歸一化積相關(guān)度量方法比較基準(zhǔn)子圖與實(shí)時(shí)圖灰度矢量的相似性。

③采用遞歸比較的方法得到3~5個(gè)最優(yōu)的匹配點(diǎn),對(duì)應(yīng)的基準(zhǔn)子圖作為候選配子圖。

(2) 精匹配階段

在粗匹配階段得到的各個(gè)匹配點(diǎn)周圍適當(dāng)展開進(jìn)行搜索匹配(若粗匹配階段是隔n1像素進(jìn)行搜索的,則在各匹配點(diǎn)周圍展開的幅值為應(yīng)在n1/2到n1的范圍內(nèi))。

①利用簡(jiǎn)化的積相關(guān)度量方法逐一取候選子圖,并在其擴(kuò)展的范圍內(nèi)進(jìn)行灰度匹配。

②所有度量值中,Rs(u,v)值最大的匹配位置便是最終的匹配結(jié)果。

4、提高跟蹤實(shí)時(shí)性

經(jīng)過大量的實(shí)驗(yàn),采用快速的簡(jiǎn)化積相關(guān)算法進(jìn)行匹配仿真實(shí)驗(yàn)可得出如下結(jié)論:

第一是積相關(guān)及本文簡(jiǎn)化快速積相關(guān)算法在智能電視跟蹤系統(tǒng)中出項(xiàng)的穩(wěn)定性干擾以及較小的幾何畸變具有良好的抑制作用,且實(shí)時(shí)圖像越大,其抑制能力越好。

第二是對(duì)未經(jīng)選定的圖像,可以考慮對(duì)匹配數(shù)據(jù)及搜索方案進(jìn)行適當(dāng)調(diào)整以獲得滿意的匹配效率。對(duì)于經(jīng)過選定的圖像,采用本文提出簡(jiǎn)化的積相關(guān)度量方法及先粗后精的分層匹配控制策略,有效地提高了匹配效率。

第三是減少匹配次數(shù)。在匹配時(shí),進(jìn)行一次粗匹配和二次精匹配。一次粗匹配時(shí)將步長(zhǎng)設(shè)為2個(gè)像素,這樣可以使計(jì)算量減少為原來的1/4。需要指出的是,采取上述的參數(shù)進(jìn)行積相關(guān)處理時(shí),一次粗匹配的過程中,可能會(huì)遺漏實(shí)際的最佳匹配點(diǎn),但是最佳匹配區(qū)域不會(huì)被遺漏,也就是說,最佳匹配點(diǎn)可以在二次精匹配中找回。

總之,通過上述方法可以在有限的硬件條件下,有效地提高了系統(tǒng)跟蹤的穩(wěn)定和實(shí)時(shí)性。

參考文獻(xiàn):

[1] Franz Matthias O, Bernhard. Scene-based homing by image matching[J].Biol. Cybern,1998:191-202.

[2]劉揚(yáng),趙峰偉,等.景像匹配區(qū)選擇方法研究[J].紅外與激光工程, 2001, 30(3): 168-170.

[3]任仙怡,廖云濤,張桂林等.一種新的相關(guān)跟蹤方法研究[J].中國(guó)圖象圖形學(xué)報(bào)(A版),2002,7(6):553~557.

[4]劉嘉.應(yīng)用隨機(jī)過程[M].北京:科學(xué)出版社,2002:12~13.

[5]彭架雄,雷達(dá)圖像匹配制導(dǎo)技術(shù),華中理工大學(xué).

[6]孔丹,李介谷.亞像元精度的圖像匹配技術(shù)[J].紅外與激光工程,1999,27(1): 29-32.

[7]李尊民.電視圖像自動(dòng)跟蹤的基本原理.國(guó)防工業(yè)出版社.1998.

[8]齊文寧.導(dǎo)彈上圖象處理機(jī)的研制及邊緣提取算法的研究.東南大學(xué)碩士學(xué)位論文.1997.

篇9

影像匹配實(shí)際上就是兩幅（或者多幅）影像之間識(shí)別同名點(diǎn)，它是計(jì)算機(jī)視覺及數(shù)字?jǐn)z影測(cè)量的核心問題。我們知道要匹配的點(diǎn)的同名像點(diǎn)肯定在其同名核線上。在進(jìn)行最小二乘影像匹配之前，需要先進(jìn)行粗匹配。然后在粗匹配的基礎(chǔ)上用最小二乘法進(jìn)行精匹配。我們這次討論的是利用一維搜索的方法來進(jìn)行粗匹配。這就是利用同名核線來進(jìn)行同名像點(diǎn)的粗匹配。這相對(duì)于二維匹配來說速度更快。

1.1基于數(shù)字影像幾何糾正法提取核線，利用共面條件來確定同名核線

我們知道，核線在航空攝影測(cè)量上是相互不平行的，它們相交于一點(diǎn)---核點(diǎn)。但是如果將影像上的核線投影（或者稱為糾正）到一對(duì)“相對(duì)水平”-------平行于攝影基線的影像對(duì)上后，則核線相互平行。正是由于“水平”的像片具有這么一特性，我們就有可能在“水平”像片上建立規(guī)則的格網(wǎng)，它的行就是核線，核線上像元素（坐標(biāo)為xt、yt）的灰度可由它對(duì)應(yīng)的實(shí)際像片的像元素的坐標(biāo)為x，y的灰度求的 ，即g（xt，yt）=g（x，y）。

根據(jù)前邊的共線方程，同一攝站點(diǎn)攝取的水平像片與傾斜像片，其水平和傾斜像片的坐標(biāo)之間的關(guān)系為：

(1-1-1)

(1-1-2)

上邊的式子中a1,a2…,c3為左片的九個(gè)方向余弦，是該像片的外方位角素的函數(shù)，f為像片主距。顯然在水平像片上，當(dāng)yt為常數(shù)的時(shí)候，則為核線,將yt=c代入（1-1-1）和（1-1-2）式經(jīng)整理，得：

（1-1-3）

其中：

e3=d3

若在“水平”像片上以等間隔獲取一系列xt值 ，(k+1)*,(k+2)*…,可以得到一系列的像片坐標(biāo)（x1，y1），（x2，y2），（x3，y3），…，這些點(diǎn)就位于傾斜像片p的核線上。

同樣以yt=c 代入右邊的共線方程：

(1-1-4)

(1-1-5)

其中， ， ，… 右方像片的對(duì)于單獨(dú)像對(duì)像空間輔助坐標(biāo)的角方位元素的函數(shù)，由此可得右片上的同名核線。

1.2核線的重排列（重新采樣）

已知原始的影像的灰度序列，為求待定的平行于基線的“水平”影像。這就需要進(jìn)行核線的灰度重采樣。按照式（1-1-1）和（1-1-2）將“水平”像片上的坐標(biāo)u，v反算到原始影像上的x，y。但是由于所求得的像點(diǎn)不一定恰好都落在原始影像采樣的像元中心，這就必須進(jìn)行灰度的內(nèi)插-----重采樣。通常所用到的是雙線形插值法，取臨近的四個(gè)像元點(diǎn)的灰度的數(shù)值進(jìn)行待求點(diǎn)的灰度的計(jì)算。

圖1-2-1雙線形重采樣

本公式中y1代P點(diǎn)到g1，g4連線的距離，x1代表P點(diǎn)到g3,g2連線的距離的大小

1.3數(shù)字影像匹配的基本算法

本論文講述的相關(guān)系數(shù)法主要是對(duì)于一維影像相關(guān)的。

如圖1-3-1所示是一維影像相關(guān)的目標(biāo)區(qū)和搜索區(qū)（這里取m=n）。設(shè)g代表目標(biāo)區(qū)內(nèi)的點(diǎn)組的灰度值，g’代表搜索區(qū)內(nèi)相應(yīng)點(diǎn)組的灰度值，則每個(gè)點(diǎn)組共取得了n個(gè)點(diǎn)的灰度值的均值為

圖1-3-1一維相關(guān)目標(biāo)和搜索區(qū)域

，（i=0，1，2…n） （1-3-1）

兩個(gè)點(diǎn)組的方差 ， 分別為：

， （1-3-2）

兩個(gè)點(diǎn)組的協(xié)方差 為：

（1-3-3）

則兩個(gè)點(diǎn)組的相關(guān)系數(shù) 為：

（0,1,… -n） （1-3-4）

在搜索區(qū)內(nèi)沿核線尋找同名像點(diǎn)，每次移動(dòng)一個(gè)像素，按照（1-3-4）來依次相關(guān)系數(shù) ，取其中的最大的數(shù)值，其對(duì)應(yīng)的相關(guān)窗口的中心像素就被認(rèn)為是目標(biāo)點(diǎn)的同名像點(diǎn)。

1.4用相關(guān)系數(shù)的拋物線擬合來提高相關(guān)精度

為了把同名點(diǎn)求的更為準(zhǔn)確一些，可以把相關(guān)系數(shù)的最大點(diǎn)i點(diǎn)左右若干點(diǎn)（一般取左右個(gè)兩個(gè)點(diǎn)）聯(lián)系起來，從而將其函數(shù)的最大值k處的作為尋求的同名點(diǎn)的位置，結(jié)果會(huì)更好一些。

圖1-4-1拋物線擬合

如圖1-4-1所示設(shè)有相鄰像元素系處的5個(gè)相關(guān)系數(shù)，用一個(gè)二次拋物線方程式來擬合，取用的拋物線方程，代表相應(yīng)S位置處灰度的數(shù)值。

（1-4-1）

式中的參數(shù)A，B，C用間接平差方法求的。此時(shí)拋物線頂點(diǎn)k處的位置為：

（1-4-2）

由相關(guān)系數(shù)拋物線擬合可以使相關(guān)精度提高到0.15-0.2個(gè)子像素（當(dāng)信噪比較高的時(shí)候），但是相關(guān)精度和信噪比近似成反比例關(guān)系。當(dāng)信噪比比較小的時(shí)候，采用相關(guān)系數(shù)拋物線擬合也不能提高相關(guān)精度。

2僅考慮相對(duì)位移的一維最小二乘影像匹配

2.1一維最小二乘影像匹配原理

在本次僅僅考慮相對(duì)位移的一維最小二乘影像相關(guān)。在一維影像相關(guān)中是在傾斜影像相對(duì)應(yīng)的水平影像坐標(biāo)系中沿x軸方向?qū)で笸c(diǎn)，若在最小二乘算法中把搜索區(qū)像點(diǎn)移動(dòng)的位移量作為一個(gè)幾何參數(shù)引入，就可以直接解算像點(diǎn)的位移。

設(shè)有兩個(gè)一維灰度函數(shù) ， ，除了隨機(jī)噪聲 ， 外， 相對(duì)于 存在位移量 。如圖4-3-1所示，則

（2-1-1）

則（2-1-2）

圖 2-1-1 僅考慮相對(duì)位移的一維最小二乘影像相關(guān)

為了解求相對(duì)位移量，需要對(duì)（2-1-2）式子進(jìn)行線性化：

（2-1-3）

對(duì)離散的數(shù)字影像，灰度函數(shù)的導(dǎo)數(shù) 可以由差分 代替，即

（2-1-4）

其中 采樣間隔。令 ，則誤差方程式可以寫為；

（2-1-5）

為了解求 ，取一個(gè)窗口，對(duì)窗口內(nèi)的每個(gè)像元素都可以列出一個(gè)誤差方程式，按照的原則，則可以求得影像的相對(duì)位移的量 ：

（2-1-6）

因?yàn)榻馑愣际蔷€性化的結(jié)果得到的，因此，解算需要迭代進(jìn)行。解得 后，對(duì) 進(jìn)行重新采樣，各迭代計(jì)算時(shí)，系數(shù) 以及常數(shù)項(xiàng) 均采用重新采樣后的灰度值進(jìn)行計(jì)算。

2.2計(jì)算最佳的匹配點(diǎn)位

我們知道，影像匹配的目的是為了尋求獲得同名點(diǎn)。通常以待定的目標(biāo)點(diǎn)建立一個(gè)目標(biāo)窗口，窗口的中心點(diǎn)就是目標(biāo)點(diǎn)。但是，在高精度影像相關(guān)中，必須考慮目標(biāo)窗口的中心點(diǎn)是否是最佳的匹配點(diǎn)。根據(jù)最小二乘法影像匹配的精度理論可以知道：影像匹配中的精度取決于影像灰度的梯度 ， 。因此，可以用梯度的平方為權(quán)，在左方影像窗口中內(nèi)對(duì)坐標(biāo)做加權(quán)平均：

（2-2-1）

以它作為目標(biāo)點(diǎn)坐標(biāo)，它的同名點(diǎn)坐標(biāo)可以由最小二乘法影像匹配所求得的幾何變換參數(shù)求得；

（2-2-2）

隨著以最小二乘法為基礎(chǔ)的高精度數(shù)字影像匹配算法的發(fā)展，為了近一步提高起可靠性與精度，攝影測(cè)量工作者進(jìn)而有提出了各種帶有約束條件的最小二乘影像匹配的算法。例如，附帶有共線條件的最小二乘相關(guān)以及與VLL法相結(jié)合的最小二乘影像匹配方法都得到了廣泛的應(yīng)用和研究。

3 最小二乘影像匹配的精度分析

篇10

鍵，在分布式環(huán)境下加速后綴數(shù)組的構(gòu)造需要充分考慮到通信對(duì)算法性能的影響。串匹配問題是計(jì)算機(jī)科學(xué)中研究得最廣泛的問題之一，在文字編輯與處理、圖像處理、信息檢索、分子生物學(xué)等領(lǐng)域都有很廣泛的應(yīng)用。本文解決的是分布式存儲(chǔ)環(huán)境下的精確串匹配問題。在串匹配的許多實(shí)際應(yīng)用中一個(gè)確定的文本常常被查詢很多次(比如對(duì)非常長(zhǎng)的基因序列的查詢)。針對(duì)這種情況，Manber.U和E.W.Myers提出建立后綴數(shù)組(suffixarrays)〔1〕來提高查詢的性能論文，而后綴數(shù)組最大的不足是它的構(gòu)造時(shí)間過長(zhǎng)。因此一直以來，如何快速有效地構(gòu)造后綴數(shù)組成了提高基于后綴數(shù)組的串匹配算法性能的關(guān)

2USAA算法

假設(shè)N，M為文本串和模式串的長(zhǎng)度，P為處理器數(shù)，算法設(shè)計(jì)思路如下:

(1)將長(zhǎng)為N的文本串A均勻劃分成互不重盛的P段，分布于處理器。~(P一l)中，且使相鄰的文本段分布在相鄰的處理器中，顯然每個(gè)處理器中局部文本段的長(zhǎng)度為〔N/P〕。

(2)除了處理器O外，其它每個(gè)處理器利用KMP算法計(jì)算分配到自己的文本串的頭個(gè)字符與模式串，基金項(xiàng)目:國(guó)家自然科學(xué)基金重點(diǎn)項(xiàng)目(60533020)的匹配信息。如果存在匹配情況，就向相鄰的前一個(gè)處理器發(fā)送最大匹配后綴長(zhǎng)度Maxsuffixlen，否則就發(fā)送一個(gè)負(fù)數(shù)。每個(gè)處理器可獨(dú)立地計(jì)算和發(fā)送該值，所以這一步的計(jì)算復(fù)雜度為O(M)，通信復(fù)雜度為O(1)。

(3)處理器1~(P-l)接收前一個(gè)處理器的信息。

(4)利用Manber.U和E.W.Myers在文獻(xiàn)〔〔1〕中的算法各處理器并行地構(gòu)造局部文本段的后綴數(shù)組。

(5)利用Manber.U和E.W.Myers在文獻(xiàn)〔1〕中的算法各處理器并行地進(jìn)行模式申的匹配。算法的計(jì)算復(fù)雜度為O((N/P(109109(N/P)))，通信復(fù)雜度為0(1)，大大降低了通信復(fù)雜度。

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

我們?cè)诨诜植即鎯?chǔ)的32節(jié)點(diǎn)HPRX2600高性能機(jī)群系統(tǒng)上測(cè)試了上述算法，比較了USAA和目前理論值最好的MMsortlz〕算法之間的性能，其計(jì)算復(fù)雜度為，通信復(fù)雜度為。

圖1給出了當(dāng)M一16、P~2時(shí)，N的取值對(duì)算法執(zhí)行時(shí)間的影響。從圖中看出當(dāng)時(shí)，由于N、P的取值成了影響算法復(fù)雜度的主項(xiàng)，因此在實(shí)際應(yīng)用中USAA算法比MMsort算法表現(xiàn)要好。

圖2給出了當(dāng)N變大時(shí)，USAA算法和MMsort算法的通信時(shí)間比較。可以看出，隨著文本串的規(guī)模變大，由于處理器間需要進(jìn)行的通信量增加，MMsort算法的通信時(shí)間有明顯的上升，而USAA算法的上升幅度要顯著小于MMsort。

4結(jié)論

本文提出的USAA算法通過采取均勻的后綴分配方式來降低處理段間匹配時(shí)的通信消耗，在(N/P)M的情況下使算法在保持計(jì)算復(fù)雜度的同時(shí)大大降低了通信復(fù)雜度。通過實(shí)驗(yàn)結(jié)果可以看到，USAA算法很好地解決了在分布式存儲(chǔ)環(huán)境下降低后級(jí)數(shù)組構(gòu)造中的通信復(fù)雜度的問題。

參考文獻(xiàn)

篇11

Components Based Graduation Design Managing Information System

YANG Zu-qiao1, LIU Gui-mei2

(1.College of Mathematics & Computer Science, HuangGang Normal University, Huanggang 438000, China; 2.Educational Technology Center, HuangGang Normal University，Huanggang 438000 , China)

Abstract: According to construction status of digital campus and the actual demands of graduation design management in our school, the basic modules of the projection management system is designed based on the Java Web Component technology. To achieve the functions of user registration, teacher questions, student topics, upload documents, download information, tutoring etc., and selected theme matching algorithm and system security are discussed mainly. Application the system can regulate the graduation designs selection and management process, improve work efficiency, economize the human resources and management costs, improve the management level of graduate de? sign.

Key words: Java Web component；management information system; graduate design；matching algorithm; Workflow

長(zhǎng)期以來，畢業(yè)設(shè)計(jì)管理全過程基本上是手工或計(jì)算機(jī)輔助打印等方式完成，這種管理方式效率較低，容易出錯(cuò)，不能適應(yīng)高校信息化的要求。因此需要一個(gè)針對(duì)此流程進(jìn)行管理的系統(tǒng)，使得此過程更加方便，更加透明，更加高效，以節(jié)省更多的人力和不必要的工作。現(xiàn)在有許多高校已經(jīng)設(shè)計(jì)并開發(fā)了畢業(yè)設(shè)計(jì)管理系統(tǒng)，方便了學(xué)生和教師，提高了管理效率，但是，部分系統(tǒng)還是沒有從根本上改變畢業(yè)設(shè)計(jì)管理工作的總體流程和管理理念，存在信息孤立、交互方式單調(diào)等問題，也還有以下幾個(gè)待改進(jìn)的方面：1）過多關(guān)注于畢業(yè)設(shè)計(jì)的選題管理，對(duì)畢業(yè)設(shè)計(jì)的過程管理的重視不夠；2）部分系統(tǒng)在可維護(hù)性、執(zhí)行效率和可擴(kuò)展性等方面還存在一些問題[1]；3）系統(tǒng)信息的安全性有待進(jìn)一步提高[2]。

作為J2EE體系中的重要一環(huán)，JSP為創(chuàng)建高度動(dòng)態(tài)的Web應(yīng)用提供了一個(gè)獨(dú)特的開發(fā)環(huán)境[3]。JSP設(shè)計(jì)目標(biāo)是為了使動(dòng)態(tài)頁面編寫更容易，更簡(jiǎn)單。到處可執(zhí)行，JSP技術(shù)完全與平臺(tái)無關(guān)的設(shè)計(jì)，包含它的動(dòng)態(tài)網(wǎng)頁和底層Server元件設(shè)計(jì)，加強(qiáng)元件功能，更容易建立動(dòng)態(tài)網(wǎng)頁。由于Java Web組件技術(shù)具有以下優(yōu)點(diǎn)：

1）可重復(fù)使用跨平臺(tái)的組件(如：JavaBean或Enterprise JavaBean組件)來執(zhí)行更復(fù)雜的運(yùn)算、數(shù)據(jù)處理；

2）組件可以跨平臺(tái)使用；

3）組件是基于二進(jìn)制代碼編碼，運(yùn)行效率高，安全性好。

該文利用Java Web組件技術(shù)開發(fā)一個(gè)適合地方計(jì)算機(jī)類專業(yè)的畢業(yè)設(shè)計(jì)管理系統(tǒng)，實(shí)現(xiàn)畢業(yè)設(shè)計(jì)全過程的信息化管理。

1系統(tǒng)設(shè)計(jì)

軟件體系結(jié)構(gòu)的設(shè)計(jì)是整個(gè)軟件開發(fā)過程中的關(guān)鍵點(diǎn)。B/S架構(gòu)在客戶端使用瀏覽器就可以訪問到系統(tǒng)，大大簡(jiǎn)化了客戶端載荷，減輕了系統(tǒng)維護(hù)與升級(jí)的成本和工作量，降低了用戶的總體成本。系統(tǒng)總體任務(wù)是對(duì)學(xué)生和指導(dǎo)教師進(jìn)行管理，在仔細(xì)分析管理流程和已有系統(tǒng)的特色基礎(chǔ)上，本系統(tǒng)采用三層B/S架構(gòu)，包括瀏覽器、Web服器和數(shù)據(jù)庫服務(wù)器，如圖1所示。

第二個(gè)問題是系統(tǒng)的安全性問題。本系統(tǒng)中采用隨機(jī)登錄驗(yàn)證碼機(jī)制防止惡意注冊(cè)和MD5加密機(jī)制保護(hù)用戶的密碼，可以實(shí)現(xiàn)對(duì)消息完整性的保護(hù)。這兩種安全措施可以有效保證用戶的密碼安全，從而提高系統(tǒng)的安全性能。

實(shí)現(xiàn)高校畢業(yè)設(shè)計(jì)及論文管理網(wǎng)絡(luò)化，為教師、學(xué)生以及學(xué)校管理都提供了極大便利，本系統(tǒng)有較強(qiáng)的針對(duì)性及實(shí)用性，能夠解決本校論文管理存在一系列問題，在投入使用后，為教師、學(xué)生和管理人員提供了交流溝通的平臺(tái)，實(shí)現(xiàn)管理人員、教師和學(xué)生的交流與互動(dòng)，有效解決高校畢業(yè)設(shè)計(jì)中存在的一些問題，規(guī)范畢業(yè)設(shè)計(jì)流程，提高畢業(yè)設(shè)計(jì)的質(zhì)量。系統(tǒng)在具體使用過程中，肯定還會(huì)出現(xiàn)這樣那樣一些問題，但隨著新技術(shù)不斷發(fā)展以及設(shè)計(jì)者對(duì)軟件體系不斷更新與完善，相信隨著本系統(tǒng)日漸成熟，給學(xué)校的教學(xué)管理及發(fā)展帶來方便。

[1]張敬普,婁鵬宇.工作流技術(shù)在畢業(yè)設(shè)計(jì)系統(tǒng)中的應(yīng)用[J].數(shù)字技術(shù)與應(yīng)用,2010 (8):35-35.

[2]曾小平,吳暾華.本科畢業(yè)設(shè)計(jì)管理系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].微型機(jī)與應(yīng)用, 2011 ,30(18):83-85.

篇12

1 緒論

圖像拼接技術(shù)有悠久的研究歷史。早期用于航空遙感照片合成，在20世紀(jì)90年代Heung——Yeung Shum研究了同心圓拼圖(柱面全景圖)， 20世紀(jì)90年代中期，微軟研究院的Szeliski教授提出基于運(yùn)動(dòng)的全景圖像拼接模型，將8參數(shù)減低為4參數(shù)，2003年M.Brown發(fā)表了全自動(dòng)的圖像拼接算法的文章，使用捆綁調(diào)整技術(shù)，同時(shí)，魚眼鏡頭拍攝圖像生成球面全景圖的繪制技術(shù)也得到廣泛研究。

2 全景圖像拼接技術(shù)的概述

2.1 全景圖的模式分類

全景圖根據(jù)圖像投影方式的不同，存在幾種全景圖像：一種是球面全景圖像，一種是多面體全景圖像，還有一種是最常用的柱面全景圖像。柱面全景處理起來比球面全景與多面體全景簡(jiǎn)單得多，因而應(yīng)用面比較廣。

2.2 全景圖的生成流程

全景圖的聲稱流程如下：圖像的采集，圖像的預(yù)處理，圖像的變換，圖像匹配，圖像的平滑處理。

3 基于特征匹配的柱面全景圖拼接技術(shù)的研究

3.1 原始圖像的采集和幾何校正

3.1.1 拍攝方法和原則

照相機(jī)拍攝時(shí)一般有三種情況：

1.旋轉(zhuǎn)照相機(jī)拍攝

在這種情況下，放置照相機(jī)的三腳架在拍攝過程中一直在同一位置。照相機(jī)繞垂直軸旋轉(zhuǎn)，每旋轉(zhuǎn)一定的角度，拍攝一張照片。拍攝得到一系列照片中相鄰兩張必須有部分重疊。建議相鄰圖像之間重疊比例達(dá)到50%。重疊比例越大，拼接就越容易。

2.平移照相機(jī)拍攝

平移照相機(jī)指的是照相機(jī)在一個(gè)平行于成像平面的方向上平移。這種情況的缺點(diǎn)：拍攝的相片在一個(gè)平面上，拍攝的三維感覺不如旋轉(zhuǎn)拍攝的。科技論文。

3.手持照相機(jī)拍攝

這種方法比較容易做到，手持照相機(jī)原地旋轉(zhuǎn)拍攝。但是，拼接手持照相機(jī)拍攝的照片是很困難的，因?yàn)樵谂臄z過程中，照相機(jī)的運(yùn)動(dòng)非常復(fù)雜。可以增加重疊比例，使照相機(jī)旋轉(zhuǎn)角度、平移減小，因而減小相鄰圖像之間的不連續(xù)程度。

用照相機(jī)拍攝全景圖像，要取得較好的效果，必須注意以下幾個(gè)方面的原則：

3.2 圖像的變換

將一幅圖像與另一幅圖像匹配，常需要對(duì)一幅圖像進(jìn)行一系列的變換，這些變換可分為剛體變換、仿射變換、投影變換和非線性變換。

3.3 圖像的匹配

3.3.1圖像拼接算法的原理

一般情況下，經(jīng)過柱面投影變換得到的具有重疊區(qū)域的柱面全景圖中相鄰的兩幅待拼接圖像間的重疊[2]范圍大約在30%-50%之間。為了減少在特征區(qū)域提取時(shí)候的盲目性，我們可以先對(duì)灰度圖像進(jìn)行圖像輪廓的提取，盡量的讓選擇的特征區(qū)域包含獨(dú)特的信息，容易識(shí)別。

在圖像匹配過程中，希望匹配點(diǎn)要準(zhǔn)確，即關(guān)峰尖銳，定位精度高，因此在實(shí)驗(yàn)過程中用邊緣檢測(cè)的方法提取圖像的邊緣從而使圖像的輪廓更為清晰，這樣有利于提高匹配的精度和降低偽匹配的可能性。

3.3.2 基于特征區(qū)域的提取和匹配算法的實(shí)現(xiàn)

本文采用Moravec[3]算子進(jìn)行特征區(qū)域的提取，窗口的大小可以采用55到2121。窗口越大，抗噪聲能力越強(qiáng)，同時(shí)運(yùn)算量也越大。

特征區(qū)域的匹配過程步驟如下：

1.將匹配圖像重疊部分的像素灰度值和位置信息讀入數(shù)據(jù)矩陣B，矩陣B讀入的是匹配圖像重疊部分的數(shù)據(jù)。

2.設(shè)置一個(gè)或者多個(gè)二維循環(huán)，通過對(duì)循環(huán)條件的設(shè)置或者分段設(shè)置循環(huán)，使搜索路徑可以沿著預(yù)處理之后提取的輪廓邊沿進(jìn)行，將整個(gè)圖像的重疊區(qū)域全部搜索一遍。科技論文。

3.沿著搜索的路徑提取矩陣B的55，并且對(duì)矩陣內(nèi)部的元素進(jìn)行運(yùn)算，分別計(jì)算該矩陣和單位矩陣的元素的均方差和灰度差的絕對(duì)值之和，分別把它們賦給兩個(gè)變量。

4.將記錄的當(dāng)時(shí)搜索區(qū)域和單位矩陣的均方差和灰度差的絕對(duì)值之和跟之前的記錄值作比較（記錄值的初值的均方差為0，灰度值的絕對(duì)值之和為10），記錄均方差的最大值和灰度值的絕對(duì)值之和的最小值，并且分別記錄它們的坐標(biāo)位置。科技論文。

5.搜索矩陣下移，再次重復(fù)步驟2和步驟3。

6.搜索結(jié)束，就得到了在矩陣B中令均方差最小且灰度值的絕對(duì)值之和最大的區(qū)域，記錄該區(qū)域的位置和中心點(diǎn)的坐標(biāo)位置。

在本課題的實(shí)現(xiàn)過程中，待拼接的圖像已經(jīng)經(jīng)過了預(yù)處理和輪廓提取，所以在拼接的過程中，只需要將算子的中心沿著重疊部分圖像的輪廓進(jìn)行就可以了。

3.4圖像的平滑處理

在拍攝柱面全景圖時(shí)，周圍環(huán)境和相機(jī)本身引起的最大問題就是相鄰圖像之間的光照變化較大，會(huì)出現(xiàn)帶狀痕，為了消除這種拼接區(qū)域帶狀痕影響，提出了一種直方圖處理方法：

1.對(duì)于24位色圖，首先將RGB圖像轉(zhuǎn)換成HIS類型圖像，針對(duì)其I分量進(jìn)行處理，等同于對(duì)灰度圖像的灰度值進(jìn)行處理。

2.將兩幅圖像的1/3公共部分作為重疊區(qū)域，注意要保證兩個(gè)重疊區(qū)域像素?cái)?shù)目一致。

3.分別計(jì)算左、右兩邊重疊區(qū)域的I分量或灰度圖像灰度值的和sum1與sum2。

4.Differ=sum1/sum2，將圖像2的每一個(gè)像素的I分量或者灰度圖像2的每一個(gè)像素的值與參數(shù)Differ相乘加權(quán)。這樣做的目的是將兩幅圖像的亮度均值統(tǒng)一，使得重疊區(qū)域在拼接時(shí)能夠平滑過渡。

4 總結(jié)與展望

隨著虛擬現(xiàn)實(shí)技術(shù)的不斷發(fā)展，虛擬現(xiàn)實(shí)技術(shù)開始走向大眾化，并應(yīng)用于網(wǎng)上購(gòu)物、網(wǎng)上旅游、網(wǎng)上教育和在線游戲等領(lǐng)域，虛擬現(xiàn)實(shí)系統(tǒng)將會(huì)成為未來世界一個(gè)不可缺少的重要組成部分。

【參考文獻(xiàn)】

[1]王玉珍.基于特征區(qū)域的圖像拼接技術(shù).蘭州大學(xué)碩士學(xué)位論文，2001：

3-10

[2]蘭培真,馬越,邱志雄,金一垂.不同視點(diǎn)重疊圖像自動(dòng)拼接算法.中國(guó)航海，2001，(2)：41-45

篇13

〔中圖分類號(hào)〕TP391 〔文獻(xiàn)標(biāo)識(shí)碼〕A 〔文章編號(hào)〕1008-0821（2016）02-0140-05

〔Abstract〕Text mining is an important aspect of data mining technology.According to the features of syntactic rules，the paper uses the text mining technology，and puts forward the design model based on the syntactic rules text knowledge mining.It analyzes the working principles of the data preparation，the syntactic rules knowledge structure，the text preprocessing，the text mining and the evaluation of mining results.Meanwhile it expounds the process of the construction of the syntax rules.At last，the paper identifies the model after some physical experiments.All in all，the design has certain research significance and application value to implement the intelligent of the text knowledge mining.

〔Key words〕text mining；syntactic rules；pattern matching；text pretreatment

隨著信息技術(shù)、網(wǎng)絡(luò)技術(shù)和各種數(shù)字化資源的建設(shè)，人們正面臨著海量、快速增長(zhǎng)的文本數(shù)據(jù)資源，傳統(tǒng)的搜索引擎和查找技術(shù)已遠(yuǎn)遠(yuǎn)不能滿足人們的需求。如何從大量原始的、未經(jīng)處理的文本數(shù)據(jù)集合中挖掘出潛在未知的知識(shí)，滿足人們獲取各種信息和知識(shí)的需要，已成為一個(gè)重要的研究課題。

1 文本挖掘及句法規(guī)則概述

文本挖掘（Text Mining，TM）是在數(shù)據(jù)挖掘的基礎(chǔ)上發(fā)展起來的一個(gè)分支，它以文本數(shù)據(jù)作為挖掘?qū)ο螅饕蝿?wù)是對(duì)隱藏于海量文本中沒有檢測(cè)到的非結(jié)構(gòu)化知識(shí)進(jìn)行提取的過程[1]。文本挖掘處理的對(duì)象是由多數(shù)據(jù)源組成的大量文本文檔，包括新聞文章、研究論文、書籍期刊、報(bào)告會(huì)議、檔案文獻(xiàn)、Internet網(wǎng)絡(luò)信息等半結(jié)構(gòu)化或者高度非結(jié)構(gòu)化的數(shù)據(jù)[2]。

漢語句子的結(jié)構(gòu)非常自由，但其蘊(yùn)含的基本規(guī)則相對(duì)穩(wěn)定，句法規(guī)則是從漢語本身的屬性特點(diǎn)出發(fā)，將構(gòu)成句子的詞或詞組按一定的語法關(guān)系和句子結(jié)構(gòu)，組合成能夠表達(dá)完整意思的規(guī)則[3]，如詞語的分類、句式結(jié)構(gòu)的確定、句法描述體系和句法構(gòu)成元素的建立等，它是對(duì)句子結(jié)構(gòu)的抽象概括，通過組合和聚合關(guān)系造出無數(shù)合格的句子，是對(duì)句子分析的一種總結(jié)結(jié)果。

2 基于句法規(guī)則的文本知識(shí)挖掘技術(shù)的分析與設(shè)計(jì)

本文采用句法規(guī)則構(gòu)造實(shí)現(xiàn)文本知識(shí)挖掘，主要設(shè)計(jì)如下：首先，根據(jù)知識(shí)的表示和用戶的不同需求，構(gòu)造出能全面準(zhǔn)確表達(dá)文本內(nèi)容的句法規(guī)則；其次，針對(duì)多源文本數(shù)據(jù)的特點(diǎn)和存在的問題進(jìn)行預(yù)處理操作，為核心挖掘提供干凈、準(zhǔn)確、簡(jiǎn)潔的目標(biāo)數(shù)據(jù)；再次，基于模式匹配算法，執(zhí)行句法規(guī)則與目標(biāo)文本數(shù)據(jù)的匹配，得出滿足句法規(guī)則條件的挖掘結(jié)果；最后，通過一定的指標(biāo)對(duì)挖掘結(jié)果進(jìn)行評(píng)價(jià)，將滿足用戶需求的知識(shí)可視化表達(dá)到用戶界面，供其選擇和使用，具體過程如圖1所示：

2.1 數(shù)據(jù)準(zhǔn)備

數(shù)據(jù)準(zhǔn)備主要是多源文本數(shù)據(jù)的獲取，它通過多種數(shù)據(jù)源獲取用于文本知識(shí)挖掘的數(shù)據(jù)，并存儲(chǔ)在本地硬盤中[4]。文本數(shù)據(jù)的獲取有多種途徑，主要來源是Internet網(wǎng)絡(luò)信息、研究成果、各種專題數(shù)據(jù)，以及其他文獻(xiàn)資料。選擇文本數(shù)據(jù)的數(shù)據(jù)源需要遵循以下原則：一是能為對(duì)象提供詳細(xì)、準(zhǔn)確數(shù)據(jù)；二是要考慮數(shù)據(jù)的可整合性、可挖掘性和現(xiàn)勢(shì)性。文本知識(shí)的挖掘是一種基于句法規(guī)則的集中式挖掘，務(wù)必要求多源文本數(shù)據(jù)在結(jié)構(gòu)上能夠整合到同一平臺(tái)框架下，并且保持一定的現(xiàn)勢(shì)性，從而簡(jiǎn)化挖掘操作，提高知識(shí)獲取的準(zhǔn)確度。

2.2 句法規(guī)則構(gòu)造

句法規(guī)則構(gòu)造是根據(jù)知識(shí)的表示方法和漢語的句法組成結(jié)構(gòu)，通過對(duì)表達(dá)語料庫的的詳細(xì)分析，將知識(shí)規(guī)則化，為核心挖掘提供模式匹配的基礎(chǔ)條件。它主要分為3個(gè)層次：模板元素、句法規(guī)則、規(guī)則庫。建立用于構(gòu)造句法規(guī)則和約束文本分詞、詞性標(biāo)注的模板元素，構(gòu)造出用于模式匹配的句法規(guī)則，構(gòu)建相應(yīng)的規(guī)則樹。從模板元素建立到句法規(guī)則構(gòu)造，再到規(guī)則庫的構(gòu)建帶有明顯的層次性和結(jié)構(gòu)性。

句法規(guī)則構(gòu)造過程分為以下幾步：一是收集并提煉出資料中的模板元素并建立相應(yīng)的模板元素庫；二是根據(jù)語法要求和句法結(jié)構(gòu)將模板元素組合成句法規(guī)則；三是把句法規(guī)則存放入規(guī)則庫。

2.2.1 句法規(guī)則的模板元素

模板元素是用戶作為約束文本預(yù)處理結(jié)果的一種擴(kuò)充詞典，各個(gè)模板元素之間相互作用、相互影響構(gòu)成了表達(dá)文本內(nèi)容的句法規(guī)則。在這里借鑒漢語句法結(jié)構(gòu)組成和本體概念的構(gòu)建方法，將構(gòu)成規(guī)則的每個(gè)〈詞語〉抽象為詞性，每種詞性下面包含了能夠反映該詞性性質(zhì)的元素，稱為模板元素，規(guī)則中的每個(gè)模板元素都是該事件的參與者，一個(gè)句法規(guī)則看作是一個(gè)句子的語義的某種抽象化表示[5]，用模板元素表示該句子的語義，具體表示為：

從式（1）可以看出，多個(gè)模板元素根據(jù)漢語句子的語法要求和句法結(jié)構(gòu)組合，即可構(gòu)成能夠表示特定文本知識(shí)的規(guī)則，我們稱這種表示知識(shí)的規(guī)則為句法規(guī)則。因此，本文的句法規(guī)則是以模板元素為基本單位，根據(jù)人們表達(dá)習(xí)慣將多個(gè)模板元素按照語法關(guān)系組合成能夠表達(dá)知識(shí)的句子。模板元素作為句法規(guī)則的組成，是一種類似本體的表達(dá)類型，可表示為屬性（內(nèi)容1，內(nèi)容2，…，內(nèi)容n），其中屬性抽象為能夠表達(dá)該領(lǐng)域知識(shí)的任意一種詞性，如“詞性：名詞”，內(nèi)容則表示該模板元素范圍內(nèi)包含的所有詞的集合。

本文在采用中科院ICTCLAS分詞系統(tǒng)漢語詞性標(biāo)記統(tǒng)計(jì)的基礎(chǔ)上，提出了多個(gè)屬性類別選項(xiàng)以描述模板元素，具體如表1所示：

然后，對(duì)各詞類內(nèi)容進(jìn)行具體劃分，如以謂詞表為例：

2.2.2 句法規(guī)則構(gòu)造

句法規(guī)則是模式匹配的邏輯核心，是知識(shí)表示內(nèi)容的形式化概要，起到把要挖掘的知識(shí)內(nèi)容類型化和結(jié)構(gòu)化的作用。一條句法規(guī)則通常指出模板元素之間的關(guān)系，當(dāng)句法規(guī)則與目標(biāo)文本進(jìn)行匹配時(shí)，必須合理約束各模板元素之間的語法關(guān)系和句法結(jié)構(gòu)，嚴(yán)格按照每個(gè)模板元素在句法規(guī)則中的出現(xiàn)順序?qū)ζ溥M(jìn)行匹配[4]。例如：北京是中國(guó)的首都，與天津市相鄰，它的句法化表達(dá)為：〈主語〉+〈謂詞〉+〈地名〉，〈連詞〉+〈地名〉+〈謂詞〉，它的句法規(guī)則為：n/v/ns/f/w2/cc/ns/v。

2.2.3 規(guī)則庫

規(guī)則庫是用戶需求與目標(biāo)文本之間進(jìn)行問題求解的基礎(chǔ)，用于描述相應(yīng)領(lǐng)域內(nèi)知識(shí)概要的產(chǎn)生式集合[6]，它包含了所有能反應(yīng)和表達(dá)實(shí)體文本知識(shí)的方法和表現(xiàn)形式，能夠?yàn)橛脩籼峁┎煌某橄竺枋觯纬刹煌耐评礞湥贸霾煌耐诰蚪Y(jié)果。本文規(guī)則庫采用規(guī)則樹結(jié)構(gòu)存儲(chǔ)，如圖2所示：

圖2中，規(guī)則庫作為樹的根結(jié)點(diǎn)，共包含24個(gè)子結(jié)點(diǎn)，分別代表本文構(gòu)造的24條句法規(guī)則。按照結(jié)點(diǎn)所在層次由高到低分別定義為一級(jí)、二級(jí)、三級(jí)和四級(jí)規(guī)則。該規(guī)則樹構(gòu)建的基本策略是：

（1）將所有的句法規(guī)則置于一個(gè)集合中，即規(guī)則庫作為規(guī)則樹的根結(jié)點(diǎn)；

（2）根據(jù)句法規(guī)則的組成結(jié)構(gòu)對(duì)其進(jìn)行劃分，將相互獨(dú)立并且不被包含的句法規(guī)則按編號(hào)順序（從A到X）依次作為第二層的子結(jié)點(diǎn)，定義為一級(jí)規(guī)則；

（3）將其余句法規(guī)則根據(jù)包含與被包含的關(guān)系，依次劃分到相應(yīng)子結(jié)點(diǎn)下面，并分別定義為二級(jí)、三級(jí)和四級(jí)規(guī)則。

采用以上樹結(jié)構(gòu)存儲(chǔ)句法規(guī)則，結(jié)構(gòu)清晰，便于執(zhí)行與目標(biāo)文本的匹配，減少部分句法規(guī)則與目標(biāo)文本之間不必要的匹配。

2.3 文本預(yù)處理

文本預(yù)處理是文本挖掘的基礎(chǔ)，主要對(duì)目標(biāo)對(duì)象的多源文本數(shù)據(jù)進(jìn)行操作，將多數(shù)據(jù)源中獲取的文本數(shù)據(jù)進(jìn)行處理，為下一步的文本知識(shí)挖掘提供比較“滿意”的目標(biāo)數(shù)據(jù)。預(yù)處理主要包括文本快速整合、文本分詞和詞性標(biāo)注、目標(biāo)文本存儲(chǔ)等，本文采用中科院的開源ICTCLAS分詞系統(tǒng)對(duì)文本進(jìn)行分詞和詞性標(biāo)注。

文本預(yù)處理主要分為3個(gè)步驟：

（1）多源文本數(shù)據(jù)快速整合。將目標(biāo)對(duì)象的多源文本數(shù)據(jù)集成到同一文本文檔中。

（2）中文分詞和詞性標(biāo)注。將經(jīng)過整合的目標(biāo)對(duì)象文本數(shù)據(jù)分詞、標(biāo)注詞性。

（3）目標(biāo)文本存儲(chǔ)。將目標(biāo)文本以段為單位編碼并索引標(biāo)記，建立兩個(gè)二維表分開存儲(chǔ)目標(biāo)文本分詞結(jié)果和目標(biāo)文本詞性標(biāo)注結(jié)果。例如，對(duì)于預(yù)處理之后的目標(biāo)文本：南京/n位于/v江蘇省/ns中部/f，我們采用表3和表4所示存儲(chǔ)：

2.4 文本知識(shí)挖掘

文本預(yù)處理完成以后，即可進(jìn)行文本挖掘操作。文本知識(shí)挖掘是采用模式匹配算法，將規(guī)則庫中的句法規(guī)則和目標(biāo)文本執(zhí)行精確匹配，得出符合規(guī)則條件的文本結(jié)果，并將其保存。它的主要任務(wù)是通過各種算法挖掘出用戶需要的信息，主要包括特征提取、文本分類、文本聚類、文本提取、關(guān)聯(lián)分析等[7]。本文采用KMP（Knuth-Morris-Pratt）算法進(jìn)行模式匹配，基本思想是：當(dāng)匹配過程中出現(xiàn)字符比較不相等時(shí)，模式串利用已經(jīng)得到的“部分匹配”結(jié)果將模式串向右“滑動(dòng)”，重新開始下一趟的匹配。例如對(duì)于主串“acabaabaabcac”，模式串“abaabcac”，利用KMP算法進(jìn)行匹配的過程如下：

具體挖掘流程如圖3：

基于句法規(guī)則的模式匹配的執(zhí)行步驟為：

（1）讀取句法規(guī)則庫，輸入目標(biāo)文本詞性和目標(biāo)文本分詞，啟動(dòng)基于句法規(guī)則的模式匹配。

（2）對(duì)規(guī)則庫中的句法規(guī)則按照由高到低級(jí)別依次和所有編碼的目標(biāo)文本詞性執(zhí)行匹配。采用匹配算法遍歷目標(biāo)文本詞性執(zhí)行精確匹配，直到所有句法規(guī)則與目標(biāo)文本詞性執(zhí)行完匹配，輸出所有句法規(guī)則匹配結(jié)果。若無句法規(guī)則匹配結(jié)果，則匹配失敗，結(jié)束整個(gè)模式匹配。

（3）將所有句法規(guī)則匹配結(jié)果轉(zhuǎn)換為對(duì)應(yīng)文本字符。根據(jù)二維表編碼關(guān)聯(lián)返回到對(duì)應(yīng)目標(biāo)文本分詞中，根據(jù)索引標(biāo)記將句法規(guī)則匹配結(jié)果轉(zhuǎn)換成相對(duì)應(yīng)的文本字符，該文本字符即為文本知識(shí)挖掘結(jié)果。

（4）輸出所有基于句法規(guī)則的挖掘結(jié)果，匹配結(jié)束。

2.5 挖掘結(jié)果評(píng)價(jià)和知識(shí)表達(dá)

評(píng)價(jià)是指通過一定的評(píng)價(jià)標(biāo)準(zhǔn)對(duì)挖掘結(jié)果進(jìn)行評(píng)估，把符合條件的結(jié)果返回到可視化模塊。知識(shí)表達(dá)是將評(píng)價(jià)后的結(jié)果表達(dá)到用戶界面，供用戶選擇使用，最終經(jīng)過可視化表達(dá)的結(jié)果即為用戶期待已久的知識(shí)。文本挖掘質(zhì)量評(píng)估是對(duì)挖掘結(jié)果的整體衡量，若挖掘結(jié)果滿足評(píng)價(jià)指標(biāo)，則挖掘完成，否則重新挖掘。

3 實(shí)驗(yàn)結(jié)果驗(yàn)證

下面我們以鄭州市地理信息文本知識(shí)的挖掘?yàn)槔肰isualStudio 2010作為開發(fā)平臺(tái)，介紹整個(gè)挖掘?qū)崿F(xiàn)過程。

3.1 數(shù)據(jù)選取

打開數(shù)據(jù)源接口，通過Internet搜索引擎選取30篇鄭州市地理信息數(shù)據(jù)，并保存到“F：＼鄭州市地理信息文本數(shù)據(jù)”中。

3.2 文本預(yù)處理

對(duì)以上選取的文本數(shù)據(jù)進(jìn)行預(yù)處理。在ICTCLAS分詞系統(tǒng)上進(jìn)行設(shè)置，通過選擇文本、添加用戶詞典、分詞并標(biāo)注詞性、結(jié)果保存，實(shí)現(xiàn)文本快速整合、分詞和詞性標(biāo)注。對(duì)預(yù)處理后的目標(biāo)文本設(shè)置過濾功能，將對(duì)應(yīng)的目標(biāo)文本分詞和目標(biāo)文本詞性以段為單位編碼同時(shí)用索引標(biāo)記，分開存儲(chǔ)。存儲(chǔ)結(jié)果如下圖所示：

3.3 文本知識(shí)挖掘

文本知識(shí)挖掘是在本文2.2句法規(guī)則構(gòu)造的基礎(chǔ)上進(jìn)行，主要分為3個(gè)過程：匹配條件提交、匹配實(shí)現(xiàn)和結(jié)果轉(zhuǎn)換。匹配條件提交指讀取規(guī)則庫、輸入目標(biāo)文本詞性和目標(biāo)文本分詞，匹配實(shí)現(xiàn)通過執(zhí)行模式匹配算法代碼來實(shí)現(xiàn)，結(jié)果轉(zhuǎn)換利用句法規(guī)則匹配結(jié)果的編碼和索引標(biāo)記將其轉(zhuǎn)換為對(duì)應(yīng)的目標(biāo)文本分詞字符，實(shí)現(xiàn)挖掘結(jié)果。挖掘結(jié)果分別如圖6所示：

3.4 評(píng)價(jià)和表達(dá)

在完成文本知識(shí)挖掘以后，便對(duì)挖掘結(jié)果進(jìn)行評(píng)價(jià)，并按相對(duì)優(yōu)劣次序?qū)⒌乩砦恢梦谋局R(shí)可視化表達(dá)，并可導(dǎo)出為常用的EXCEL、WORD等文檔格式，如圖7所示：

通過以上實(shí)例可以看出，采用基于句法規(guī)則的文本挖掘方法，能夠?yàn)橛脩粼谕诰蚪Y(jié)果中得到比較滿意的信息，從而較好的達(dá)到設(shè)計(jì)的目的。

4 結(jié)束語

隨著文本數(shù)據(jù)資源的不斷增長(zhǎng)，僅僅通過簡(jiǎn)單的搜索引擎和數(shù)據(jù)篩選功能已經(jīng)無法滿足人們對(duì)信息和知識(shí)的需求，迫切需要高效率的信息分析方法。采用基于句法規(guī)則的文本知識(shí)挖掘設(shè)計(jì)方案，能夠從句法規(guī)則設(shè)計(jì)入手，利用現(xiàn)有文本挖掘技術(shù)，從眾多文本數(shù)據(jù)中快速地獲取用戶需求的知識(shí)，對(duì)實(shí)現(xiàn)文本知識(shí)智能化挖掘具有一定的借鑒意義。

參考文獻(xiàn)

[1]Antonis Spinakis.Text Mining A Powerful Tool for Knowledge Management[EB/OL].http：∥/articles/TextMining.pdf，2010，（7）.

[2]張?chǎng)S鑫.文本挖掘工具述評(píng)[J].圖書情報(bào)工作，2012，（4）：26.

[3]楊暉.言語實(shí)踐中的句法認(rèn)知[J].吉林師范大學(xué)學(xué)報(bào)：人文社會(huì)科學(xué)版，2007，（4）：64-66.

[4]馬紹龍.基于句法規(guī)則的地理位置文本知識(shí)挖掘[C].鄭州：信息工程大學(xué)論文集，2014（4）：170-173.