時間：2022-05-25 01:28:08
導語：在匹配算法論文的撰寫旅程中，學習并吸收他人佳作的精髓是一條寶貴的路徑，好期刊匯集了九篇優(yōu)秀范文，愿這些內(nèi)容能夠啟發(fā)您的創(chuàng)作靈感，引領(lǐng)您探索更多的創(chuàng)作可能。
關(guān)鍵詞： 模式匹配; 跳轉(zhuǎn)距離; BM算法; BMH算法; BMHS算法; DBMHS算法
中圖分類號：TP393 文獻標志碼：A 文章編號：1006-8228（2015）01-08-04
An improved pattern matching algorithm of BMHS
Zhang Huan， Hu Yong
（School of Electronic and Information Engineering， Sichuan University， Chengdu， Sichuan 610065， China）
Abstract： Pattern matching plays an important role in computer application. By analyzing BM， BMH， BMHS algorithm and their corresponding improved algorithms， a new improved algorithm（called DBMHS） based on BMHS is proposed. DBMHS takes full advantages of two ends string characters of pattern string， through comparing two ends character jump distance of pattern matching， jump distance is increased. The experiment results show that the improved algorithm significantly increases the jump distance of matching window， effectively improving the matching efficiency.
Key words： pattern matching; jump distance; BM algorithm; BMH algorithms; BMHS algorithm; DBMHS algorithm
0 引言
隨著網(wǎng)絡(luò)技術(shù)的高速發(fā)展，網(wǎng)絡(luò)資源呈爆炸式增長。如何在網(wǎng)絡(luò)數(shù)據(jù)中找到需要的信息，已經(jīng)成為人們研究的熱點問題。模式匹配算法在很多領(lǐng)域得到了較為廣泛的應(yīng)用，如入侵檢測、計算機病毒特征匹配[1]、搜索引擎、文本挖掘等。目前關(guān)于模式匹配的算法有很多，其中最著名的是BM算法[2]。BM算法發(fā)展的過程中，1980年Horspol發(fā)表了改進與簡化BM算法的論文，即Boyer Moore Horspoo（BMH）算法[3]，隨后Sunday在1990年在BMH算法的基礎(chǔ)上又進行了改進，提出了BMHS算法[4]。本文對現(xiàn)有幾種典型模式算法進行分析，在BMHS算法的基礎(chǔ)上進行改進，并進行試驗和結(jié)果分析。
1 典型算法
1.1 BM算法
BM算法是由Boyer和Moore在1977提出的單模式匹配算法。它是目前實際應(yīng)用中效率較高的單模式匹配算法之一。BM算法采用從右向左比較的方法，同時應(yīng)用到了兩種啟發(fā)式規(guī)則，即壞字符規(guī)則和好后綴規(guī)則，來決定向右跳躍的距離。BM 算法中壞字符跳躍表和好后綴跳躍表的設(shè)計對提高BM算法效率有至關(guān)重要的作用。設(shè)文本T（長度為n），模式串P（長度為m）。
⑴ 壞字符跳躍表：當Pk≠Ti，即不匹配情況發(fā)生時，若此時Pk是P的末字符且Ti在模式串P中不出現(xiàn)，則下一次比較可以將匹配窗口直接移動m個位置后繼續(xù)匹配;若Ti在模式串P中出現(xiàn)，則找到Ti在模式串P中出現(xiàn)的最右邊的位置j（1≤j≤m-1），匹配窗口移動的距離為m-j（如圖1所示）。
<E：＼方正創(chuàng)藝5.1＼Fit201412＼圖＼zh圖1.tif>
圖1 壞字符規(guī)則
⑵ 好后綴跳躍表： 當Pk≠Ti（k<m）時，子串Pk+1Pk+2…Pm與Ti+1Ti+2…Ti+m-k是匹配的。若在模式串P的k位置左邊有與Pk+1Pk+2…Pm相同的子串P1P2…Pm-s或Pk+1Pk+2…Pm的某個后綴Ps+1Ps+2…Pm與P的某前綴P1P2…Pm-s相同，即移動匹配窗口s位使Ti位置與該子串對應(yīng)位置對齊，算法繼續(xù)匹配（如圖2所示）。
<E：＼方正創(chuàng)藝5.1＼Fit201412＼圖＼zh圖2.tif>
圖2 好后綴規(guī)則
在匹配過程中，模式串P與文本T從右向左開始匹配，一旦發(fā)現(xiàn)不匹配，取好字符跳轉(zhuǎn)和壞字符跳轉(zhuǎn)之間較大的值作為模式串P的向右跳轉(zhuǎn)距離。最理想的情況是每次匹配時文本T中第一個匹配的字符不存在于模式串P中，此時BM的算法的時間復雜度為O（n/m）;最壞的情況是文本T中有多個重復的字符，并且模式串P由m-1個相同的字符前加一個不同的字符組成，在這種情況下，BM算法的時間復雜度為O（mn）。
1.2 BMH算法
Horspool提出的BMH算法相對于BM算法更容易實現(xiàn)。BMH算法在預(yù)處理階段只使用了壞字符跳躍表，無論文本中哪個字符造成了匹配失敗，都將依據(jù)壞字符跳轉(zhuǎn)表向右移動。BMH算法的基本思想是：①搜索文本時，從頭到尾搜索，匹配時從右向左匹配。首先比較文本指針所指字符和模式串的最后一個字符，如果相等，再比較其余m-1個字符，無論文本中哪個字符造成了匹配失敗，都將由文本中和模式串最后一個位置對應(yīng)的字符來啟發(fā)模式串向右移動，即當匹配開始比較TiTi+1…Ti+m-1和P0P1…Pm-1時，一旦發(fā)生不匹配，計算跳轉(zhuǎn)距離skip（Ti+m-1），跳轉(zhuǎn)后將模式串和文本對齊后重新匹配。②如果與P完全匹配，返回在T中對應(yīng)的位置;③如果搜索完T仍然找不到完全匹配的位置，則查找失敗[3]（如圖3所示）。壞字符跳轉(zhuǎn)計算公式：
<E：＼方正創(chuàng)藝5.1＼Fit201412＼圖＼zh圖3.tif>
圖3 BMH算法
如圖3所示，當文本中的與T2（‘d’）與模式串P中的P2（‘c’）發(fā)生不匹配時，計算跳轉(zhuǎn)距離skip（T4），可以看出P1與T4相等，模式串P向右移動3個字符，即skip（T4）等于3，然后將P1與T4對齊后重新匹配。
BMH算法簡化了初始化過程，匹配過程中的判斷過程也作了簡化，因為BMH算法只采用了BM算法的壞字符移動規(guī)則，并且將失配情況與偏移量的計算獨立，不關(guān)心文本串中哪個字符造成了失配，只考慮用于模式串最右端對齊的文本字符來決定偏移量。該算法的理論時間復雜度與BM算法一致，但實際使用情況下較BM算法效率高。
1.3 BMHS算法
BMHS算法在BMH算法的基礎(chǔ)上作了進一步改進，該算法的主要思想是：當開始匹配TiTi+1…Ti+m-1和P0P1…Pm-1時，若發(fā)生不匹配，考慮下一個字節(jié)的情況，即利用下一個字符Ti+m決定右移量。當下一個字符Ti+m不在模式串P中出現(xiàn)時，它的右移量比BMH算法的右移量大，跳過m+1個字符。通常情況下，BMHS算法比BMH算法快，但當Ti+m-1不在模式中出現(xiàn)，而Ti+m出現(xiàn)在模式串中時， BMHS算法[4]的效果就不如BMH算法[3]。匹配過程如圖4。BMHS算法的跳轉(zhuǎn)距離計算公式為：
<E：＼方正創(chuàng)藝5.1＼Fit201412＼圖＼zh圖4.tif>
圖4 BMHS算法
如圖4所示，當Ti+m出現(xiàn)在模式串P中時，如圖4（a），將模式串P中的字符‘e’與Ti+m對齊;當Ti+m不存在于模式串P中時，如圖4（b）所示，模式串P向右移動m+1個字符;而圖4（c）中當Ti+m存在于模式串P中，而Ti+m-1不存在于模式串P中時，skip（Ti+m-1）等于5，而skip（Ti+m）等于1，Ti+m-1的跳轉(zhuǎn)距離大于Ti+m的跳轉(zhuǎn)距離，若還使用Ti+m為標準，則會降低匹配效率。在BMHS算法中最理想的時間復雜度為O（n/m+1）。
1.4 對各算法的已有改進
在模式匹配中存在兩個基本定理：任何字符串匹配算法的最壞情況下必須檢查至少n-m+1個文本中的字符;任何字符串匹配算法至少檢查n/m個字符[5]。因此，沒有一個算法比BM算法有更好的計算復雜度，但是我們可以通過改進來減少比較次數(shù)，提高匹配的平均性能。
基于以上三種模式匹配算法，近些年已經(jīng)有多種改進算法。例如，利用統(tǒng)計字符在模式串中出現(xiàn)的頻率來實現(xiàn)跳轉(zhuǎn)[6];利用雙字節(jié)計算偏移量[7-9];通過模式串P和文本T之間的關(guān)系來實現(xiàn)跳轉(zhuǎn)[10];利用已匹配成功的字符串來進行跳轉(zhuǎn)[11]，以及從模式串兩端向中間匹配的方式[12]來改進模式匹配算法等。以上算法雖然減小了匹配次數(shù)，但相應(yīng)增加了匹配的時間。接下來詳細介紹一種通過雙字節(jié)來計算偏移量的模式匹配改進算法。
2012年袁靜波提出了一種改進的BMHS模式匹配算法[8]。該算法在BMHS算法的基礎(chǔ)上利用文本T中與模式串P最后一個字符對應(yīng)的字符Ti+m-1，以及Ti+m和Ti+m+1來實現(xiàn)跳轉(zhuǎn)，模式串P和文本T從右向左匹配。以下是具體匹配過程。
第一步：當文本T和模式串P發(fā)生失配時，首先判斷Ti+m是否在模式串中，若不存在直接跳過m+1的距離，如圖5所示，文本T中的T4（‘d’）不在模式串P中，則模式串P向右移動m+1個字符。
<E：＼方正創(chuàng)藝5.1＼Fit201412＼圖＼zh圖5.tif>
圖5 Ti+m不在模式串P中
第二步：當Ti+m在模式串中時，判斷子串Ti+m Ti+m+1是否在模式串P中，若不存在，則跳過m+2的距離，如圖6，子串“be”不在模式串P中，則模式串向右跳轉(zhuǎn)m+2個字符。
<E：＼方正創(chuàng)藝5.1＼Fit201412＼圖＼zh圖6.tif>
圖6 Ti+m Ti+m+1不在模式串P中
第三步：若模式串包含Ti+m Ti+m+1，則比較子串Ti+m-1Ti+m是否存在于模式串P中，不存在的話跳轉(zhuǎn)m+1個字符，如圖7，子串Ti+m Ti+m+1（“be”）存在與模式串P中，而子串Ti+m-1 Ti+m（“gb”）不存在與模式串P中，則模式串P向右跳轉(zhuǎn)m+1個字符。
<E：＼方正創(chuàng)藝5.1＼Fit201412＼圖＼zh圖7.tif>
圖7 Ti+m-1 Ti+m不在模式串P中
第四步：若Ti+m Ti+m+1和Ti+m-1 Ti+m都存在于模式串中，則取兩者之間匹配的最大值進行跳轉(zhuǎn)，如圖8，可以看出，子串Ti+m Ti+m+1（“ea”）的跳轉(zhuǎn)距離為2，子串Ti+m-1 Ti+m（“ae”）的跳轉(zhuǎn)距離為3，取跳轉(zhuǎn)距離較大的值，則模式串P應(yīng)向右跳轉(zhuǎn)3個字符。
<E：＼方正創(chuàng)藝5.1＼Fit201412＼圖＼zh圖8.tif>
圖8 比較得到較大值進行跳轉(zhuǎn)
在該改進算法中，模式串P最大的跳轉(zhuǎn)距離為m+2，在理想的情況下該算法的時間復雜度為O（n/m+2）。
2 DBMHS算法
2.1 基本思想
通過觀察BM，BMH和BMHS算法的匹配過程可以發(fā)現(xiàn)，這些算法在匹配窗口的首字符匹配均失敗時效率最優(yōu)。本文提出的DBMHS算法通過比較模式串P的第一個字符P0的跳轉(zhuǎn)距離jump（P1）和在T中與模式串P最后一個字符對應(yīng)的后一個字符Ti+m的跳轉(zhuǎn)距離jump（Ti+m）來移動模式串P。跳轉(zhuǎn)距離公式如下：
jump（P1）={k|Ti+k=P1，1≤k≤m}
jump（Ti+m+1）=m-k+1 k=Max{k|Pk=Ti+m+1，1≤k≤m}
2.2 匹配算法
顯然，提高首字符匹配失敗的概率是提高算法效率的關(guān)鍵之一。改進的DBMHS算法結(jié)合了BMHS算法特點，首先模式串P與文本T左端對齊，從右向左開始匹配，先檢測T中與模式串最后一個字符相對應(yīng)的字符Ti+m-1是否在模式串P中，若Ti+m-1不在模式串P中出現(xiàn)，則檢測后一個字節(jié)Ti+m是否存在于模式串P中，若Ti+m不在模式串P中出現(xiàn)，則模式串P可以向右移動最大的距離m+1，否則移動距離為m。如圖9、圖10所示。
<E：＼方正創(chuàng)藝5.1＼Fit201412＼圖＼zh圖9.tif>
圖9 Ti+m不存在于模式串P中
<E：＼方正創(chuàng)藝5.1＼Fit201412＼圖＼zh圖10.tif>
圖10 Ti+m存在于模式串P中
若Ti+m-1與模式串P中對應(yīng)的字符相匹配，則接著匹配余下的字符，一旦發(fā)生不匹配的情況，則檢測Ti+m是否存在于模式串P中，若不存在，則模式串P直接向右移動m+1的距離，若存在則計算Ti+m的跳轉(zhuǎn)距離，然后計算模式串P中第一個字符P0的跳轉(zhuǎn)距離，比較這兩個跳轉(zhuǎn)距離，選擇較大的跳轉(zhuǎn)距離作為模式串P的實際跳轉(zhuǎn)距離。從圖11可以看出，若使用Ti+m進行跳轉(zhuǎn)，則模式串P的跳轉(zhuǎn)距離為1，若使用模式串P的第一個字符P0進行跳轉(zhuǎn)，則模式串的跳轉(zhuǎn)距離為2，通過比較，使用P0的跳轉(zhuǎn)距離可以使模式串P盡量的向右移動。需要注意的是，若模式串P或文本T中同一個字符出現(xiàn)多次，在計算跳轉(zhuǎn)距離時，需分情況處理，例如，若匹配Ti+m時，P中出現(xiàn)多個與Ti+m相同的字符，則選擇最右端的字符與Ti+m對齊;若是在匹配P0時出現(xiàn)這種情況，則選擇T中靠左的字符進行對齊。
<E：＼方正創(chuàng)藝5.1＼Fit201412＼圖＼zh圖11.tif>
圖11 P1跳轉(zhuǎn)距離大于Ti+m
若算法在匹配時自右向左均匹配成功，則此時找到一次完全匹配，算法結(jié)束。DBMHS匹配算法偽代碼描述如表1。
表1 DBMHS匹配算法偽代碼
[輸入：文本串T，模式串P
輸出：文本串T中是否存在子串P＼&While i≤T
Do If Ti+m-1 Pm
If Ti+m-1P
If Ti+mP Then MOVE m;
Else MOVE m+1;
Else
If Ti+mP Then MOVE m+1;
Else MOVE max（jump（P0），jump（Ti+m））;
Else If Ti+kPk
If Ti+mP Then MOVE m+1;
Else MOVE max（jump（P0），jump（Ti+m））;
Else If Ti。。。i+m-1= P0。。。m-1 Then Return true;
Return false;＼&]
2.3 算法分析
從BMHS算法的匹配算法可以看出，BMHS算法在比較時利用下一個字符Ti+m決定右移量，當Ti+m不在模式串P中出現(xiàn)時會跳轉(zhuǎn)最大的距離m+1，但當Ti+m出現(xiàn)在模式串P中時，由于多進行了一次匹配，BMHS匹配算法的效果就不如BMH算法。因此，DBMHS匹配算法通過模式串兩端的字符來充分利用Ti+m。當Ti+m出現(xiàn)在模式串P中時，計算Ti+m的跳轉(zhuǎn)距離，并計算第一個字符P0的跳轉(zhuǎn)距離，通過比較這兩個字符的跳轉(zhuǎn)距離來實現(xiàn)更大的跳轉(zhuǎn)，這樣不僅提高了Ti+m的利用率，而且獲得了更高的匹配效率。
3 算法性能測試
本實驗使用的計算機硬件平臺為IntelPentium G2020處理器，4G內(nèi)存，軟件平臺為Windows 7操作系統(tǒng)，Microsoft Visual Studio 2010集成開發(fā)環(huán)境。在此環(huán)境下分別對BMHS算法、IBMHS算法和DBMHS算法進行測試，IBMHS匹配算法為文獻[8]中提出的對BMHS匹配算法的改進算法。
實驗隨機選取4個不同長度的文本串，實驗文本字符集由大小寫字母，數(shù)字和空格組成。模式串從文本串中隨機提取。分別執(zhí)行BMHS算法、IBMHS算法和DBMHS算法程序，統(tǒng)計不同長度文本串，不同模式串的情況下，算法的執(zhí)行時間和匹配窗口的移動次數(shù)。每個算法分別執(zhí)行10000次，運行時間取平均值。得到的數(shù)據(jù)如表2和表3。
表2 匹配窗口移動次數(shù)
[文本長度＼&模式串長度＼&BMHS＼&IBMHS＼&DBMHS＼&匹配次數(shù)＼&匹配次數(shù)＼&匹配次數(shù)＼&2481＼&12＼&259＼&183＼&202＼&1138＼&10＼&114＼&90＼&95＼&555＼&14＼&44＼&32＼&35＼&225＼&12＼&16＼&13＼&14＼&]
表3 匹配時間
[文本長度＼&模式串長度＼&BMHS＼&IBMHS＼&DBMHS＼&匹配時間＼&匹配時間＼&匹配時間＼&2481＼&12＼&0.218＼&1.482＼&0.218＼&1138＼&10＼&0.094＼&0.671＼&0.094＼&555＼&14＼&0.031＼&0.218＼&0.031＼&225＼&12＼&0.016＼&0.094＼&0.016＼&]
由表2和表3可以看出，本文提出的算法相比傳統(tǒng)的BMHS算法有較大的改進。例如第一次匹配，DBMHS匹配次數(shù)較BMHS減少了約28%，并且文本長度越長，減少的匹配次數(shù)就會越多。此外，DBMHS在匹配用時上與傳統(tǒng)的BMHS算法比較接近。雖然IBMHS算法的匹配次數(shù)少于DBMHS算法，但是匹配時間幾乎是DBMHS算法的7倍。從效率上來說，DBMHS算法要優(yōu)于其他算法。
4 結(jié)束語
本文通過分析BM，BMH和BMHS模式匹配算法，提出了一種改進的算法DBMHS。由于DBMHS算法充分利用了模式串兩端字符，通過實驗可以證明，該算法的匹配效率得到了顯著提升。下一步的研究將考慮該算法應(yīng)用在多模式匹配中，并利用語言學中的知識，如模式串與文本結(jié)構(gòu)，使其性能更加優(yōu)越。
參考文獻：
[1] Yang Wang and Hidetsune Kobayashi. High Performance Pattern
Matching Algorithm for Network Security. IJCSNS International Journal of Computer Science and Network Security，2006.6（10）：83-87
[2] Boyer R S，Moore J S.A Fast String Searching Algorithm[J].
Communications of the ACM，1977.20：762-772
[3] Horspool N R. Practical Fast Searching in Strings[J]. Software
Practice and Experience，1980.10（6）：5012506
[4] Sunday D M. A very fast substring search algorithm[J].
Communication of the ACM，1990.33（8）：132-142
[5] 李雪瑩，劉寶旭等.字符串匹配技術(shù)研究[J].計算機工程，2004.30
（22）：24226
[6] 劉勝飛，張云泉.一種改進的BMH模式匹配算法[J].計算機科學，
2008.35（11）：164-165
[7] 姚保峰，王磊.一種改進的BMH模式匹配算法[J].湖南工程學院學報：
自然科學版，2011.3：40-42
[8] Yuan J， Yang J， Ding S. An Improved Pattern Matching Algorithm
Based on BMHS[C]//Distributed Computing and Applications to Business， Engineering & Science （DCABES）， 2012 11th International Symposium on. IEEE，2012：441-445
[9] 王浩，張霖.基于壞字符序檢測的快速模式匹配算法[J].計算機應(yīng)用
與軟件，2012.29（5）：114-116
[10] Shrivastava G， Jain A. A Review of Intrusion Detection Method
Based On Automatic Pattern Matching[J]. Computer Engineering，2012.1（1）：88-90
[11] Chen Q， Niu Y， Wang Z， et al. Improved BM Pattern Matching
Algorithm for Intrusion Detection[C]//Computational Science and Optimization （CSO）， 2010 Third International Joint Conference on. IEEE，2010.1：440-444
摘要：
目標檢測和跟蹤技術(shù)是無人機航拍領(lǐng)域的重要研究方向?？偨Y(jié)了無人機航拍視頻中目標檢測和跟蹤的常用方法并對其進行了分類。分析了各類別的優(yōu)缺點，并討論了無人機航拍視頻中目標檢測與跟蹤的難點及未來發(fā)展趨勢。
關(guān)鍵詞：
無人機；目標檢測；目標跟蹤；航拍
引言
無人機又稱為無人駕駛飛行器，是一種具有遙控、自動、半自主、全自動飛行能力的飛行器。常見的無人機主要分為固定翼無人機、直升機和多旋翼無人機。2010年前，固定翼無人機和無人直升機在航拍領(lǐng)域占據(jù)了主流地位，然而，在近幾年中，隨著控制技術(shù)、傳感器技術(shù)和計算機視覺領(lǐng)域的快速發(fā)展，多旋翼無人機成為了航拍領(lǐng)域的新星，尤其是四旋翼無人機和八旋翼無人機受到了航拍領(lǐng)域的青睞，其模型如圖1所示。多旋翼尤其是四旋翼無人機之所以受到廣泛關(guān)注和應(yīng)用主要是因為有以下特點［1］:操控簡單，四旋翼無人機可以實現(xiàn)垂直起降，不受場地的限制，飛行過程中動作靈活并可實現(xiàn)空中懸停;便于攜帶，旋翼無人機具有體積小、便于攜帶且操作靈活等特點;經(jīng)濟實惠，多旋翼無人機最大的優(yōu)點就是成本低，所以，受到廣泛應(yīng)用。目標檢測與跟蹤技術(shù)作為計算機視覺領(lǐng)域的關(guān)鍵技術(shù)，受到了各界學者的廣泛關(guān)注。在無人機航拍領(lǐng)域中，為了實現(xiàn)追蹤拍攝，目標檢測和跟蹤必不可少。因此，目標檢測和跟蹤技術(shù)是無人機航拍領(lǐng)域的重要研究方向［2］。另外，航拍視頻中由于畫面較大，目標在場景中所占面積較小，背景復雜，目標易發(fā)生尺度、旋轉(zhuǎn)、光照和遮擋干擾以及相機抖動等影響，航拍視頻中目標的檢測和跟蹤變得尤為復雜，檢測和跟蹤工作變得更加困難。本文主要就無人機航拍視頻中的目標檢測和跟蹤技術(shù)展開討論，對目標檢測和跟蹤算法的分類、優(yōu)缺點和應(yīng)用范圍進行總結(jié)，并對航拍視頻中目標檢測和跟蹤算法的難點和發(fā)展趨勢加以討論。
1無人機航拍視頻目標檢測技術(shù)
對無人機航拍視頻中的目標進行跟蹤時，首先需要對目標進行檢測，目標檢測的準確與否會直接影響后續(xù)對目標的處理，所以，目標檢測技術(shù)在無人機航拍視頻目標的檢測和跟蹤系統(tǒng)中起到了至關(guān)重要的作用。目前，運動目標檢測算法相對來說比較成熟，可應(yīng)用于無人機航拍視頻的目標檢測算法主要有以下幾種:
1)幀間差分法。主要通過連續(xù)兩幀相同位置像素點間的灰度差來確定目標的移動，算法操作簡單，易于實現(xiàn)，但是，該算法只適用于靜態(tài)背景和目標單一條件下的目標檢測，所以，應(yīng)用于無人機航拍視頻的目標檢測時，只適用于無人機懸停狀態(tài)下的運動目標的檢測，應(yīng)用范圍有限。
2)背景差分法。其原理是通過預(yù)先設(shè)置背景，然后通過對檢測圖像和預(yù)設(shè)背景作差的方式提取目標。該方法能夠得到較為完整的目標圖像并且能夠滿足實時性要求。但是，在實際背景與預(yù)設(shè)背景相差較大或者實際檢測過程中發(fā)生明顯光照變化的情況下，該方法檢測精度會下降較大。所以，該算法同樣只適用于無人機懸停狀態(tài)下的目標檢測。
3)光流法。該方法將光流作為灰度像素點在圖像上的瞬時運動場，從而實現(xiàn)對目標的跟蹤。該方法根據(jù)原理主要分為四類:基于梯度的方法、基于匹配的方法、基于能量的方法和基于相位的方法。光流法的工作流程為:首先，在圖像中等間隔選取光流點;其次，計算光流點的運動矢量(常用HS法和LK法等);最后，根據(jù)運動矢量檢測運動目標。與前兩種方法相比，由于光流場能夠反應(yīng)像素點的灰度運動情況，所以，光流目標檢測法能夠進行動態(tài)背景下的目標檢測。
4)特征匹配法。主要通過提取待檢測目標的特征(角點特征、顏色特征等)建立目標模板，然后在實時視頻中通過檢測圖像中的特征圖目標模板進行相似性判別，從而實現(xiàn)目標的檢測。目前常用的特征匹配算法有SIFT［6］、SURF［7］、BRISK［8］和FREAK［9］等。特征匹配法是目前應(yīng)用最為廣泛的目標檢測和識別算法。其不但可以檢測出目標，同時可以實現(xiàn)對目標進行識別，并對目標的尺度、旋轉(zhuǎn)、光照和遮擋等具有較好的魯棒性。特征匹配算法既適用于動態(tài)背景的目標檢測，也適用于靜態(tài)目標的檢測。
2無人機航拍視頻目標跟蹤技術(shù)
目標跟蹤技術(shù)是通過確定視頻連續(xù)幀中目標的位置和大小來實現(xiàn)的，主要的跟蹤方法主要有以下幾種。
2．1CamShift算法［10］
CamShift算法是對MeanShift算法的改進，是由Bradski提出的連續(xù)自適應(yīng)漂移算法。MeanShift算法是一種基于核密度估計的非參數(shù)模式匹配算法。首先，手動選取待跟蹤目標區(qū)域，使用MeanShift顏色直方圖信息作為模板，再對下一幀圖像的顏色直方圖提取，進行匹配，通過計算相似度獲得相似度密度分布圖，圖中的極值位置即為目標的位置。由于MeanShift算法模板不能實現(xiàn)實時更新且在跟蹤過程中核函數(shù)帶寬固定不變(跟蹤窗口固定不變)，所以，當目標發(fā)生尺度變化或外界干擾時，會造成跟蹤目標不準確或者跟蹤目標丟失的現(xiàn)象。Cam-Shift算法是將視頻中的每一幀都進行MeanShift運算，不僅可以實現(xiàn)對目標模板進行更新，也可以實現(xiàn)自動調(diào)節(jié)跟蹤窗口大小的功能。CamShift算法流程大致分為以下幾步:
1)將圖像從RGB空間轉(zhuǎn)化為HSV空間，此步驟的主要目的是為了減小跟蹤過程中光照的影響;
2)目標初始化，手動選取目標的位置和大小并提取目標區(qū)域的H分量的直方圖;
3)計算圖像反向投影，認為反向投影圖中像素點亮度越大，其為目標區(qū)域的概率就越大;
4)利用MeanShift算法進行迭代運算，移動搜索窗口的中心到迭代的最大位置;
5)調(diào)整搜索窗口的大小;
6)重復步驟3～5，直至視頻最后一幀。算法的具體流程圖如圖2所示。
2．2卡爾曼濾波算法［11］
卡爾曼濾波算法是一種小方差最佳線性遞推方法，通過當前目標信息可實現(xiàn)對下一幀目標位置進行預(yù)測，從而實現(xiàn)目標的跟蹤?？柭鼮V波算法是通過狀態(tài)方程和預(yù)測方程兩個方程實現(xiàn)的，狀態(tài)方程可實現(xiàn)對系統(tǒng)的狀態(tài)進行客觀描述;預(yù)測方程可實現(xiàn)系統(tǒng)對下一時刻狀態(tài)的預(yù)測。其工作原理如圖3所示。
2．3粒子濾波算法［12］
粒子濾波的實質(zhì)是用帶有權(quán)值的粒子表示后驗概率，這些粒子隨著目標模型的移動而移動，最后與目標模板進行匹配并更新權(quán)值，這些粒子的狀態(tài)加權(quán)即為后驗概率。粒子濾波一般可分為4個步驟:1)采樣:在系統(tǒng)的狀態(tài)空間中隨機采集粒子并對其進行加權(quán)，以反映目標的狀態(tài);2)重采樣:為了防止粒子退化的現(xiàn)象，保留權(quán)值較大的粒子，減少權(quán)值小的粒子;3)狀態(tài)轉(zhuǎn)移:粒子濾波利用狀態(tài)轉(zhuǎn)移目標在下一時刻的狀態(tài)，即可得到新的粒子;4)系統(tǒng)觀測:利用觀測數(shù)據(jù)來推算粒子的權(quán)值，從而得到概率密度函數(shù)。算法具體流程如圖4所示。
2．4特征匹配算法［13］
基于特征匹配的目標跟蹤是采用目標的局部特征信息，通過特征匹配來進行跟蹤的算法。目前常用的特征匹配算法有SIFT、SURF、ORB、BRISK和FREAK等?；谔卣髌ヅ涞哪繕烁櫵惴煞譃?步:特征點檢測;特征描述;特征點篩選;特征點匹配。跟蹤算法的具體流程如圖5所示。四種常用算法的原理和優(yōu)缺點如表1所示。
3無人機航拍視頻目標檢測和跟蹤技術(shù)難點
航拍視頻中目標的檢測與跟蹤要想達到良好的效果，首先必須能夠準確檢測出目標的位置;其次要對檢測出的目標進行持續(xù)、準確跟蹤。當目標受到外界背景和遮擋等干擾時，具有較好的抗干擾性，并在通過干擾時能夠具有迅速恢復跟蹤的能力。目前，無人機航拍視頻的目標識別和跟蹤主要面臨如下問題:
1)光線的變化。室外無人機航拍過程中避免不了光線的變化，光線的亮度變化使總體環(huán)境和跟蹤目標的顏色、亮度等特征都會隨之改變，對目標檢測和跟蹤產(chǎn)生影響。
2)復雜背景。航拍視頻具有大視場、大廣角的特點，所以，航拍視頻具有信息量大、背景復雜、視場不確定性和目標在視場中占據(jù)面積較小等特點。目標容易受到復雜背景和相似目標的干擾，這種不確定性因素對航拍過程中的目標檢測和跟蹤會造成較大干擾。
3)目標尺度、旋轉(zhuǎn)問題。無人機航拍視頻中，由于無人機飛行高度、飛行角度和飛行方向等問題，非常容易造成目標的尺度變化和旋轉(zhuǎn)變化。當尺度和旋轉(zhuǎn)變化范圍較大時，會造成識別和跟蹤算法精度顯著下降。
4)目標遮擋。在無人機航拍視頻中，目標會經(jīng)常出現(xiàn)被外界事物遮擋的情況，這對目標檢測和跟蹤算法會產(chǎn)生較大影響，當目標受到嚴重遮擋時，甚至造成目標檢測無法實現(xiàn)、目標跟蹤失敗等問題。
4無人機航拍視頻目標檢測與跟蹤展望
隨著無人機航拍領(lǐng)域的快速發(fā)展，航拍視頻的目標檢測與跟蹤技術(shù)必然會得到快速發(fā)展，在未來將有以下2個方面的發(fā)展特點:1)向著實時性更強的方向發(fā)展。隨著計算機運算能力的發(fā)展和算法的不斷創(chuàng)新和改進，目標檢測和跟蹤的快速性會不斷提高，滿足實時性的需求。2)向著魯棒性更強的方向發(fā)展。衡量目標檢測和跟蹤性能好壞的一個重要因素就是算法的魯棒性。未來目標檢測算法發(fā)展的一個重要目標就是運用較少的信息，就能夠?qū)崿F(xiàn)準確的目標檢測和跟蹤，并對外界干擾具有較高的魯棒性。
5結(jié)束語
本文詳細介紹了無人機航拍視頻目標檢測和跟蹤的常用方法，分析了各方法的基本原理、優(yōu)缺點和適用范圍，最后指出了研究難點和發(fā)展趨勢，相信通過各界學者的共同努力，無人機航拍視頻目標檢測和跟蹤將會發(fā)生巨大的飛躍。
參考文獻：
［1］朱瑋．基于視覺的四旋翼飛行器目標識別及跟蹤．南京:南京航空航天大學學位論文，2014
［2］李文輝．航拍視頻中運動目標的檢測與跟蹤算法研究．西安:西安電子科技大學學位論文，2014
［3］林雯．新型基于幀間差分法的運動人臉檢測算法研究．計算機仿真，2010，27(10)
［4］汪國強，蓋琪琳，于懷勇，等．基于背景差分法的視頻目標檢測算法研究．黑龍江大學工程學報，2014，5(4)
［5］吳振杰．基于改進光流法的運動目標檢測與跟蹤系統(tǒng)．鄭州:鄭州大學學位論文，2012
［10］王巍，孟朝暉．一種改進的CamShift目標跟蹤方法．信息技術(shù)，2015(1)
［11］瞿衛(wèi)欣，程承旗．基于Kalman濾波的CamShift運動跟蹤算法．北京大學學報(自然科學版)，2015，51(5)
［12］李忠海，王莉，崔建國．基于CamShift和ParticleFilter的小目標跟蹤算法．計算機工程與應(yīng)用，2011，47(9)
一、 課題任務(wù)與目的
1、課題的主要任務(wù)：以DSP平臺為系統(tǒng)硬件平臺，并基于DM6437為處理器核心，設(shè)計硬件原理圖，編寫特征點提取算法，使系統(tǒng)通過特征點匹配對靜態(tài)目標進行識別。
2、課題的主要目的：設(shè)計并實現(xiàn)一個功能完整，操作簡單的目標識別系統(tǒng)，使其能夠?qū)o態(tài)圖像目標進行特征提取與匹配，從而進行目標識別。
二、調(diào)研資料情況
1、課題的學術(shù)狀態(tài)：
(1)DM6437關(guān)鍵特性
時鐘頻率達 600MHz， 1個TVP5146M2視頻解碼器4個視頻DACV輸出，128MDDR2DRAM，提供16M non-volatile flash memory, 64M NAND flash, 2M SRAM 提供UART, CAN，I/O接口，AIC33 立體音頻編碼器，10/100 MBS以太網(wǎng)接口，可配置的 boot load 選項，嵌入式的 JTAG 仿真器接口，4個用戶LEDs及4個用戶切換點，提供子板擴展插槽，VLYNQ接口，提供S/PDIF接口。
(2)SIFT算法
從理論上說，SIFT是一種相似不變量，即對圖像尺度變化和旋轉(zhuǎn)是不變量。然而，由于構(gòu)造SIFT特征時，在很多細節(jié)上進行了特殊處理，使得SIFT對圖像的復雜變形和光照變化具有了較強的適應(yīng)性，同時運算速度比較快，定位精度比較高。如：在多尺度空間采用DOG算子檢測關(guān)鍵點，運算速度大大加快;關(guān)鍵點的精確定位不僅提高了精度，而且大大提高了關(guān)鍵點的穩(wěn)定性;在構(gòu)造描述子時，以子區(qū)域的統(tǒng)計特性，而不是以單個像素作為研究對象，提高了對圖像局部變形的適應(yīng)能力;對于16*16的關(guān)鍵點鄰域和4*4的子區(qū)域，在處理梯度幅度時都進行了類似于高斯函數(shù)的加權(quán)處理，強化了中心區(qū)域，淡化了邊緣區(qū)域的影響，從而提高了算法對幾何變形的適應(yīng)性;該方法不僅對通用的線性光照模型具有不變性，而且對復雜的光照變化亦具有一定的適應(yīng)性。
SIFT算法的特點：1. SIFT特征是圖像的局部特征，其對旋轉(zhuǎn)、尺度縮放、亮度變化保持不變性，對視角變化、仿射變換、噪聲也保持一定程度的穩(wěn)定性;2. 獨特性(Distinctiveness)好，信息量豐富，適用于在海量特征數(shù)據(jù)庫中進行快速、準確的匹配;3. 多量性，即使少數(shù)的幾個物體也可以產(chǎn)生大量的SIFT特征向量;4. 高速性，經(jīng)優(yōu)化的SIFT匹配算法甚至可以達到實時的要求;5. 可擴展性，可以很方便的與其他形式的特征向量進行聯(lián)合。
2、參考文獻
【1】《TMS320DM6437 Datasheet》，
【2】
【3】
【4】baike.soso.com/v8850239.htm
【5】《Allegro PCB Design CIS Getting Started Guide》,
【6】周建雄，張笑微《基于DM6437 的運動目標檢測系統(tǒng)》，《信息化縱橫》2019年第12期
【7】《C/C++圖像處理編程》，清華大學出版社
【8】孫艷麗,李建海,王玲玲,孫晶《基于SIFT的多焦距圖像特征點提取算法》，《現(xiàn)代電子技術(shù)》2019 年第23 期總第334 期
【9】蔣建國,李明,齊美彬《基于TMS320DM6437的運動目標實時檢測與跟蹤》，合肥工業(yè)大學學報(自然科學版)2019年7月第34卷第7期
【10】《OrCAD Capture User's Guide》，
三、初步設(shè)計方法與實施方案
1、設(shè)計方法：
(1)、將外部圖像傳輸?shù)紻M6437處理器。
(2)、在DM6436處理器中利用Sift算法對特征點進行提取。
(3)、將提取的特征點與以存特征點進行比對。
(4)、將對比結(jié)果進行反饋。
2、實施方案：
(1)、基于Sift算法設(shè)計特征點提取算法
(2)、設(shè)計硬件原理圖
(3)、基于Matlab軟件進行仿真
(4)、對仿真結(jié)果進行分析，并對不足處進行改進與優(yōu)化
(5)、編寫基于該DSP硬件平臺的演示工程文件
四、預(yù)期結(jié)果
1、主要內(nèi)容：本課題旨在設(shè)計出一套目標識別系統(tǒng)，通過圖像特征提取與匹配算法實現(xiàn)目標的識別，圖像數(shù)據(jù)由前端傳輸給出，系統(tǒng)硬件平臺使用DSP平臺。
2、預(yù)期結(jié)果：本課題結(jié)束后，基本應(yīng)可以對靜態(tài)圖像目標進行特征點的提取與匹配，并對匹配后的結(jié)果進行反饋。
五、進度計劃
第1周：查找相關(guān)資料對課題進行初步了解，撰寫開題報告。
第2周：深入研究課題內(nèi)容，對系統(tǒng)各部分模塊進行了解。
第3-4周：對DM6437處理器核心進行研究
第5周：設(shè)計硬件原理圖
第6-7周：研究SIFT算法
第8周：編寫特征點提取算法
第9周：編寫圖像處理程序。
第10周：基于Matlab軟件制作仿真文件
第11周：分析仿真文件
第12周：制作PCB原理圖
第13周：系統(tǒng)測試及調(diào)試
第14周：撰寫畢業(yè)論文
[關(guān)鍵詞]電子圖書館 LINGO聚簇算法 用戶興趣 分組模型
20世紀末開始隨著計算機技術(shù)的發(fā)展,各種信息資源大量涌現(xiàn),進入了信息大爆炸的時代。如何在廣闊的信息海洋中檢索到自己感興趣的數(shù)據(jù)越來越成為網(wǎng)絡(luò)用戶關(guān)注的焦點。針對用戶檢索信息的需求,相繼出現(xiàn)了許多優(yōu)秀的搜索引擎,比如雅虎,Google,百度等。同時一些電子商務(wù)網(wǎng)站,比如Amazon,eBay,淘寶,當當?shù)纫餐ㄟ^不同的檢索策略為用戶提供信息檢索服務(wù)。而且隨著商業(yè)搜索引擎的不斷完善,信息檢索在教育領(lǐng)域發(fā)揮的作用也越來越重要,其中最重要的應(yīng)用就是在電子圖書館中的資源檢索。
一、電子圖書館概述
電子圖書館(Digital Library)在信息大爆炸的時代背景下誕生,改變了傳統(tǒng)圖書館資源管理方式、信息檢索方式上的不足,越來越成為圖書資源管理和資源檢索的重中之重。
廣義而言,電子圖書館包括所有電子形式的圖書館資源:經(jīng)過電子化轉(zhuǎn)換的或以電子形式出版的資料,新出版的或經(jīng)過回溯性加工的資料(包括期刊、參考工具書、專著、視頻音頻資料等)[2]。電子圖書館還可以通過網(wǎng)絡(luò)將分散的電子資源集中在一起,為用戶提供無限量的電子資源信息。
一個完整的電子圖書館系統(tǒng)應(yīng)該包括以下幾個部分:用戶發(fā)出信息查詢請求、系統(tǒng)接收請求并進行檢索處理、檢索結(jié)果返回給用戶三個部分。
但是現(xiàn)存的很多電子圖書館系統(tǒng)把注意力放在如何提高檢索請求的處理速度上,而忽略了最重要的一個因素:用戶(Users)。電子圖書館服務(wù)的主要服務(wù)對象是不同的用戶,關(guān)鍵在于針對不同的用戶,通過系統(tǒng)的分析和判斷,對不同用戶的檢索行為進行記錄、分析、綜合,進而為不同的用戶返回用戶感興趣的檢索結(jié)果。
例如電子圖書館應(yīng)該針對不同學院不同學科的用戶的不同興趣進行信息的檢索,通過為不同組的用戶設(shè)置不同的檢索庫,在進行相關(guān)檢索時首先從這幾個數(shù)據(jù)庫中進行檢索,從而達到最快最高效的返回檢索結(jié)果的目的。
所以本文提出了一個基于用戶興趣的分組模型。根據(jù)用戶的興趣將用戶進行分組,根據(jù)不同的分組采取更有針對性的信息檢索。
二、用戶分組算法設(shè)計
用戶分組模塊主要包含兩個部分,第一部分是電子資源主題關(guān)鍵字的獲取,獲取主題關(guān)鍵字后返回給用戶,根據(jù)用戶對這些關(guān)鍵字的興趣獲得用戶興趣集合,該集合是進行用戶分組的主要依據(jù);第二部分是根據(jù)第一部分獲得的用戶興趣集合進行用戶間的形似度匹配,將具有相同興趣的用戶劃歸為同一組。
1.資源主題提取原理
本文提出的檢索系統(tǒng)模型根據(jù)用戶的檢索興趣對用戶進行分類,通過處理同類用戶的請求以實現(xiàn)快速準確的檢索電子資源。用戶興趣(User interest)主要通過歸納分析用戶對電子資源的瀏覽、查詢以及下載等操作而獲得。
要實現(xiàn)資源檢索,首先就要獲得相應(yīng)資源的主題(Topic)信息。本文利用LINGO聚簇算法實現(xiàn)電子資源主題的提取。同時該算法也可以用來解決稀有主題的檢索和冷門主題過度重復檢索的問題。
當用戶檢索主題為T1的資源時,通過LINGO聚簇算法返回的結(jié)果既包括T1有關(guān)的資源,也包括與主題T1相近的其他資源,用戶需要在這些返回結(jié)果中進行選擇。同時系統(tǒng)為用戶返回一組這些相近主題的集合。通過記錄、分析、歸納用戶對這些主題對應(yīng)資源的操作,為每個主題T計算一個權(quán)值 ,同時對這些主題T根據(jù)其權(quán)值進行排列,獲得用戶興趣關(guān)鍵字集合。
利用LINGO算法檢索到的電子資源主題(topic)和用戶興趣集合是本文提出的檢索模型中對用戶進行分類的主要依據(jù)。
2. 相似度匹配算法原理
在進行信息檢索時,最重要的相似度匹配方法有兩種:變量相似性匹配和相關(guān)性匹配。所以,我們需要進行如下計算:
(公式1)
(公式2)
(公式3)
公式(1)代表了用戶a和i的相關(guān)性。其中,表示用戶a中主題j的權(quán)值,代表用戶a對主題j的重視程度。j表示用戶a和i所對應(yīng)的用戶興趣集合中的元素。V代表由公式(3)計算出的用戶興趣集合元素的概率。公式(2)代表了用戶a和i的變量相似性。
當某個主題的權(quán)值改變或者新加主題的時候,分組系統(tǒng)將重新計算用戶興趣權(quán)值,從而對用戶分組進行調(diào)整。
當用戶a的操作影響主題j時,根據(jù)主題j的權(quán)值變化,通過計算每個用戶分組受影響的概率來判斷將對哪個用戶組進行調(diào)整,見公式(4)。
(公式4)
其中表示用戶組k受影響的概率。T為系統(tǒng)中所有用戶的數(shù)量,是用戶i所屬的分組,是用戶i受主題j影響的概率,N代表用戶組K中的用戶總數(shù),表示用戶組k的用戶數(shù)在系統(tǒng)總用戶數(shù)中的比率。
三、系統(tǒng)框架及原理
1.模型框架設(shè)計
圖3-1是本模型的一個系統(tǒng)框架結(jié)構(gòu)圖。
圖3-1系統(tǒng)框架結(jié)構(gòu)簡圖
由圖3-1可知,該模型與傳統(tǒng)的圖書館檢索模型并沒有差別,都是由三大部分組成:用戶,檢索服務(wù)器,資源。首先,用戶的查詢請求發(fā)送給檢索服務(wù)器,檢索服務(wù)器根據(jù)用戶的檢索主題和用戶興趣集合對用戶分類,然后針對用戶類別的不同,將用戶的檢索請求進行分化處理,然后針對不同的用戶組別查詢相應(yīng)的電子資源庫。
在本模型中,最重要的是用戶分組模塊,只有對用戶進行有效的分組才能對用戶的信息檢索請求進行有針對性的查詢。本文提出的分組模型主要根據(jù)用戶興趣的相似度來對用戶進行分組。
2. 系統(tǒng)工作流程
系統(tǒng)工作流程分為以下幾個步驟:
(1)用戶發(fā)出資源查詢請求。
用戶在客戶端操作電子信息資源,在這個過程中,用戶會瀏覽、下載、查詢特定資源,客戶端根據(jù)用戶的行為搜集用戶查詢主題集合T與用戶興趣集合I。
(2)檢索服務(wù)器接收用戶請求以及集合T和集合I。
服務(wù)器端接收用戶請求后,首先根據(jù)客戶端傳送過來的用戶查詢主題集合T和用戶興趣集合I為用戶分組。同時,當用戶有新的查詢請求到達時,分組模塊利用相似度匹配算法對現(xiàn)在的分組情況進行調(diào)整。
(3)根據(jù)步驟(2)獲得的分組結(jié)果,針對電子圖書館的不同資源庫進行資源查詢處理。
(4)將查詢結(jié)果返回給用戶。
四、 結(jié)束語
本文介紹了基于用戶興趣的分組模型在電子圖書館信息檢索中的應(yīng)用。本論文提出的檢索模型與傳統(tǒng)的圖書館檢索模型并無大的差別,唯一不同的地方是在檢索服務(wù)器端對用戶進行分組處理,根據(jù)用戶興趣將用戶分成不同的組別,針對不同的組別,檢索服務(wù)器將檢索不同的電子信息資源庫。這樣縮小了檢索服務(wù)器檢索資源的范圍,提高了檢索效率和準確度。
本文采用LINGO聚簇算法實現(xiàn)電子資源主題的提取,該算法能夠有效解決稀有關(guān)鍵字的檢索問題,同時對于某些冷門領(lǐng)域的過度重復檢索問題也有良好的解決方案,所以利用該算法進行電子資源的檢索和管理,能夠提供用戶感興趣且全面的電子資源信息。
本文的重點在于用戶的分組,根據(jù)用戶興趣集合利用相關(guān)性匹配和變量相似度匹配算法進行用戶的分組處理,該算法能夠根據(jù)用戶檢索、瀏覽、下載電子資源的行為對用戶進行自動分組,為檢索服務(wù)器確定目標檢索資源庫提供了依據(jù)。進一步保證了檢索結(jié)果的準確性和高效性。
參考文獻:
[1] Digital Libraries
[2] 王預(yù):基于數(shù)字圖書館檢索技術(shù)的數(shù)據(jù)挖掘研究[J].計算機技術(shù)與發(fā)展,2006(11)
[3] Stanislaw Oilskin and David Weiss: Conceptual Clustering Using Lingo Algorithm: Evaluation on Open Directory Project Data, Advanced in Soft Computing, Intelligent Information Processing and Web Mining, Proceedings of the International IIS: IIPWM’04 Conference, Zapopan, Poland (2004) 369-37
[4] 林鴻飛,楊元生:用戶興趣模型的表示和更新機制[J].計算機研究與發(fā)展,2002(7)
關(guān)鍵詞：汽車后市場；用戶聚類；智能推薦算法
項目資助：國家科技支撐（2013BAH13F01）資助
1. 引言
進入新世紀以來，我國就進入了汽車產(chǎn)業(yè)高速發(fā)展的時代，已成為全球最大的汽車生產(chǎn)國與最大的汽車消費市場。從我國宏觀經(jīng)濟發(fā)展水平和當前的人均汽車保有量來看，我國汽車市場仍然孕育著巨大的發(fā)展?jié)摿Α?/p>
目前在我國的汽車產(chǎn)業(yè)高速發(fā)展的同時顯現(xiàn)出汽車后市場服務(wù)的缺位，即汽車后市場服務(wù)缺乏品牌意識，服務(wù)的理念和服務(wù)質(zhì)量、服務(wù)的可信度、服務(wù)的標準化、服務(wù)的人性化均十分淡漠。在汽車服務(wù)業(yè)企業(yè)，提供的服務(wù)和產(chǎn)品大同小異，較難提出差異化的項目來構(gòu)建企業(yè)獨特性，客戶粘度低，具有較高的話語權(quán)。傳統(tǒng)的汽車服務(wù)推薦只是針對車型、車主職業(yè)等信息來對客戶進行一個粗略的歸類，由具體的接待人員來進行推薦，通常無法取得很好的效果。對客戶偏好的深度挖掘，以及更加個性化、人性化的推薦服務(wù)，提供更好的客戶體驗是提高服務(wù)業(yè)企業(yè)的市場競爭力的有力工具。
2. 汽車后市場服務(wù)業(yè)發(fā)展現(xiàn)狀
隨著我國汽車工業(yè)的迅猛發(fā)展，汽車售后服務(wù)業(yè)在整個產(chǎn)業(yè)鏈中的重要作用逐漸顯現(xiàn)出來，其成為各大汽車廠商追逐的新的利潤增長點。不管是汽車企業(yè)、汽車消費者還是政府的相關(guān)部門，都對售后服務(wù)給予了前所未有的關(guān)注?？蛻舻南M行為反映出了他們對需求并不清晰，客戶很多時候并不清楚自己到底需要什么樣的服務(wù)，不能很好的識別自己需要的服務(wù)。同時，服務(wù)提供方也并不能主動的對客戶進行服務(wù)，更多的是被動地響應(yīng)客戶的要求，服務(wù)質(zhì)量難以有質(zhì)地提升。
目前汽車售后服務(wù)大多采用“被動響應(yīng)”服務(wù)模式，即當汽車零部件出現(xiàn)故障時才對其進行維修和保養(yǎng)。由于客戶駕駛行為習慣對汽車各零部件造成的磨損程度不同，導致汽車出現(xiàn)故障的概率和所需要的維修服務(wù)也因人而異。因此，可以考慮通過分析客戶駕駛行為對汽車零件性能產(chǎn)生的影響，選取合適的影響指標對零件的磨損進行測度，并結(jié)合零部件的正常使用壽命來預(yù)測其可能出現(xiàn)的故障和時間，主動的提供相應(yīng)的服務(wù)來提高售后服務(wù)的質(zhì)量和效率。
汽車產(chǎn)品在性能、價格和外形等方面逐步趨于同質(zhì)化，消費者更加關(guān)注產(chǎn)品附加值，從而使服務(wù)成為了競爭的主角。依據(jù)客戶消費記錄對客戶群進行細分，可以使企業(yè)根據(jù)客戶價值級別的不同決定如何在客戶中分配企業(yè)有限資源，然后根據(jù)客戶的不同需求，設(shè)計和實施不同的客戶保持策略。
3. 數(shù)據(jù)挖掘在汽車售后服務(wù)中的應(yīng)用
數(shù)據(jù)挖掘作為數(shù)據(jù)庫知識發(fā)現(xiàn)的核心部分，目前存在很多數(shù)據(jù)挖掘方法和算法。根據(jù)挖掘任務(wù)分，有如下幾種知識發(fā)現(xiàn)任務(wù)：分類知識發(fā)現(xiàn)、數(shù)據(jù)總結(jié)、數(shù)據(jù)聚類、關(guān)聯(lián)規(guī)則發(fā)現(xiàn)、序列模式發(fā)現(xiàn)、依賴關(guān)系或依賴模型發(fā)現(xiàn)、異常發(fā)現(xiàn)和趨勢預(yù)測等。運用最多的是分類知識發(fā)現(xiàn)和數(shù)據(jù)聚類算法。
客戶偏好挖掘和推薦的基本流程是：根據(jù)客戶歷史消費記錄對客戶進行偏好挖掘，并對客戶進行聚類分析；根據(jù)兩種以上的服務(wù)或者產(chǎn)品同時被消費的頻度，利用關(guān)聯(lián)規(guī)則將服務(wù)或產(chǎn)品進行聚類；利用關(guān)聯(lián)規(guī)則算法將用戶和服務(wù)產(chǎn)品進行匹配，推出針對性的智能化的推薦。
3.1對客戶進行偏好挖掘
從用戶行為信息中挖掘出用戶偏好并構(gòu)建偏好文檔是進行商品特征與用偏好匹配推薦的基礎(chǔ)。消費者細分的方法很多。有依據(jù)人口統(tǒng)計指標的細分、消費者心理細分、生活習慣細分、購買動機細分等等。在現(xiàn)實中對單個消費者個體的研究是不可能的。通過使用數(shù)據(jù)挖掘，可以根據(jù)所擁有的數(shù)據(jù)特征挖掘劃分不同的消費者群，“分群”意味著把有相似特征的消費者歸為同一組，即建立用戶群，同時把不同用戶群之間的差異最大化。
消費者行為特征挖掘的技術(shù)是聚類。聚類是探索型數(shù)據(jù)挖掘技術(shù)。可以使用許多種不同類型的聚類技術(shù)。聚類數(shù)據(jù)挖掘能夠根據(jù)已測度的變量將相似消費者歸到一起，同時使不同類型的消費者群組之間的差異最大化。本質(zhì)相同的群組具有特定的消費者行為描述，所有聚類技術(shù)只要正確使用，都能產(chǎn)生恰當?shù)姆纸M。
3.2服務(wù)產(chǎn)品的聚類分析
類似于在購買鐵錘的顧客當中，有70%的人同時購買了鐵釘；在超市買面包的人有70%會購買牛奶。關(guān)聯(lián)算法簡單來講就是對同時被消費的商品進行聚類，并分析這些相關(guān)產(chǎn)品的頻度是否滿足將其關(guān)聯(lián)起來的最低置信度。
關(guān)聯(lián)規(guī)則挖掘過程主要包含兩個階段：
【一】：必須先從資料集合中找出所有的高頻項目組（Frequent Item sets） 【若支持度大于等于所設(shè)定的最小支持度（Minimum Support）門檻值時，則{A，B}稱為高頻項目組】
【二】：再由這些高頻項目組中產(chǎn)生關(guān)聯(lián)規(guī)則（Association Rules）【在最小信賴度（Minimum Confidence）的條件門檻下，若一規(guī)則所求得的信賴度滿足最小信賴度，稱此規(guī)則為關(guān)聯(lián)規(guī)則】。
在汽車售后服務(wù)中，就是要通過關(guān)聯(lián)規(guī)則運算，形成服務(wù)和商品的一個組合產(chǎn)品，這些強關(guān)聯(lián)的組合產(chǎn)品，在客戶選擇了組合中的任意一種產(chǎn)品或服務(wù)之后，都會依據(jù)算法向他推薦另一個與前者有著強關(guān)聯(lián)關(guān)系的產(chǎn)品或服務(wù)。
3.3客戶類型和產(chǎn)品服務(wù)類型進行匹配
利用匹配算法，將消費者的類型與產(chǎn)品服務(wù)的類型進行匹配，分析出不同的客戶群體最有可能進行那種類型的消費。以及不同消費群體的偏好認知程度不同，對推薦的接受程度差異也很大。
從汽車質(zhì)量等級、汽車燃油和機油等級、汽車行駛道路環(huán)境、汽車外部環(huán)境、客戶駕駛技術(shù)、汽車修理頻率和汽車行駛里程，提取客戶的這七個因素數(shù)據(jù)對客戶行為進行數(shù)據(jù)挖掘分析，對汽車用戶進行劃分，分析出不同的駕駛習慣、經(jīng)歷、環(huán)境的不同，進行汽車維修的項目和頻率也是不同的。
4. 結(jié)論
與汽車前市場相比，汽車后市場領(lǐng)域具有更大的發(fā)展空間和發(fā)展?jié)摿?。但是汽車后市場的現(xiàn)狀是，服務(wù)與產(chǎn)品的差異化程度低，服務(wù)人員的整體水平參差不齊，客戶體驗成為留住客戶的關(guān)鍵。深入分析汽車消費者的偏好特征，對不同類型的客戶，盡可能的做出貼近其需求和偏好的產(chǎn)品或服務(wù)推薦，只有這樣才可以增強客戶的忠誠度，提高客戶粘度，進而為培養(yǎng)客戶、發(fā)展客戶、留住客戶打好基礎(chǔ)。智能化推薦，改善客戶體驗，也是汽車服務(wù)業(yè)取得進一步突破的一種有效的途徑。
參考文獻
[1]黃武漢，孟祥武，王立才.移動通信網(wǎng)中基于用戶社會化關(guān)系挖掘的協(xié)同過濾算法[J].電子與信息學報，2011，33（12）：3002—3007.
[2]張璇.汽車售后服務(wù)業(yè)客戶駕駛偏好分析研究（D）.武漢理工大學碩士論文，2012，5.
[關(guān)鍵詞]知識服務(wù)D-Rank基于滑動窗口的低頻特征部分匹配算法共詞網(wǎng)絡(luò)引文網(wǎng)絡(luò)
[分類號]G250 TP29
數(shù)十年來，信息技術(shù)遵循摩爾定律高速發(fā)展著，目前，海量存儲設(shè)備和高性能計算得到普遍應(yīng)用。海量信息得以被深度挖掘和處理，大數(shù)據(jù)、高性能計算已經(jīng)成為當前技術(shù)研究的重點。
1 信息技術(shù)夯實知識服務(wù)自動化的基礎(chǔ)
信息服務(wù)機構(gòu)的核心能力不在于所擁有的資源，而在于具備利用廣泛的信息資源為用戶創(chuàng)造價值的知識和能力，即知識服務(wù)的能力。信息服務(wù)機構(gòu)開展基于分析和基于內(nèi)容的參考咨詢服務(wù)被認為是典型的知識服務(wù)。但傳統(tǒng)的咨詢服務(wù)過程人工參與過多，服務(wù)深度和廣度都受到限制。廣泛開展高水平的知識服務(wù)還需遵循海量信息資源加高性能計算的思路，即基于海量信息利用算法研發(fā)自動化的知識服務(wù)路線(為便于討論，下文所稱的知識服務(wù)皆為自動化知識服務(wù))。實現(xiàn)這樣的服務(wù)需要硬件、海量信息和智能算法三個條件的成熟。其中硬件是構(gòu)建知識服務(wù)的物質(zhì)基礎(chǔ)，海量信息是構(gòu)建知識服務(wù)的原材料，智能算法是構(gòu)建知識服務(wù)的引擎。
1.1 硬件
影響知識服務(wù)的主要硬件因素包括存儲設(shè)備、CPU和網(wǎng)絡(luò)。知識服務(wù)依賴于海量數(shù)據(jù)，海量數(shù)據(jù)存儲需要高性能的存儲設(shè)備的存儲能力。知識服務(wù)的成果依賴于智能算法基于海量數(shù)據(jù)的計算，因此需要廉價且高性能的計算能力。同時，知識服務(wù)的成果需要從服務(wù)器傳遞給用戶，因此需要高性能的通訊網(wǎng)絡(luò)架起用戶和知識服務(wù)之間的橋梁。
當今的存儲技術(shù)已經(jīng)非常成熟，IBM等領(lǐng)先的存儲系統(tǒng)研發(fā)機構(gòu)推出的新型存儲系統(tǒng)單體容量可達數(shù)百TB，并且具有很高的性價比。與此同時，高性能計算能力和網(wǎng)絡(luò)也得到快速發(fā)展，國際TOP 500組織最近公布的最新全球超級計算機500強排行榜，位居榜首的日本超級計算機“京”的運算速度達到了每秒8162萬億次。中國互聯(lián)網(wǎng)基礎(chǔ)資源的發(fā)展使資源商更好地將知識服務(wù)帶給網(wǎng)絡(luò)用戶成為可能。截至2011年6月底，我國Ipv4地址數(shù)量為3.32億，較2010年底增長19.4％。我們擁有的Ipv6地址全球排名第15位。國際出口帶寬達到1182261.45Mbps。這些均為知識服務(wù)的發(fā)展創(chuàng)造了硬件條件。
1.2 海量信息
當前，紙本文獻的數(shù)字化和基于數(shù)字化平臺直接創(chuàng)造的數(shù)字化信息的積累也達到了非?？捎^的規(guī)模。以國家數(shù)字圖書館推廣工程的建設(shè)為例，在數(shù)字資源建設(shè)方面，該工程計劃到“十二五”末，數(shù)字資源總量達到10000TB，相當于26億冊圖書，或926萬小時視頻。其中電子圖書可達到200萬種，電子期刊達到12000種，電子報紙2 000種，音頻資源20萬小時／100萬首曲目，視頻資源30萬小時／150萬部集。海量的品質(zhì)信息得以數(shù)字化，網(wǎng)絡(luò)化、數(shù)字化知識服務(wù)成為“有源清渠”。
1.3 智能算法
搜集資料和整理、分析資料曾被視為科學研究最費時費力的工作，現(xiàn)在借助人工智能算法的力量，信息服務(wù)人員可以為用戶的這一過程提供直接的服務(wù)和支持。通過智能搜索技術(shù)可以快速幫助用戶找到所需要的信息，甚至借助文本挖掘等算法直接得出各種有價值的研究線索和提示信息。相信隨著信息處理技術(shù)的發(fā)展，越來越多的人工智能算法會應(yīng)用到信息服務(wù)中，向用戶直接提供各種知識服務(wù)，直接輔助用戶的科研創(chuàng)造過程。
2 知識服務(wù)發(fā)展與應(yīng)用
縱觀數(shù)字化、網(wǎng)絡(luò)化的圖書館情報信息服務(wù)的發(fā)展，大致可以分為資源服務(wù)、知識服務(wù)、社區(qū)服務(wù)三個階段：
在資源服務(wù)階段，服務(wù)方主要關(guān)注客戶所需要的文獻資源，以便能快速全面地滿足用戶的文獻需求。
在知識服務(wù)階段，服務(wù)方會利用計算機技術(shù)對資源進行特定的處理，開發(fā)形成這種特定知識服務(wù)，滿足用戶的特定知識需求。下文所講的知識脈絡(luò)分析的服務(wù)、論文相似性檢測服務(wù)和wolfram等都是基于資源加技術(shù)的思想研發(fā)的向用戶提供知識服務(wù)的代表。
在社區(qū)服務(wù)階段，服務(wù)方會全面調(diào)動資源、技術(shù)和人等要素，建設(shè)三要素實現(xiàn)互動的互聯(lián)網(wǎng)社區(qū)，并基于社區(qū)的互動面向用戶提供服務(wù)，滿足用戶全方位的需求。
3 知識服務(wù)促進學術(shù)創(chuàng)新
信息服務(wù)時代，信息服務(wù)人員以購買和組織文獻資源為主要工作，以滿足用戶的文獻資源需求為最終服務(wù)目標。知識服務(wù)時代，信息服務(wù)人員則將視角擴展到各種知識服務(wù)技術(shù)，關(guān)注資源和技術(shù)兩個方面，以滿足用戶的直接信息需求為服務(wù)目標，借助各種知識服務(wù)手段，參與用戶搜集資料、整理資料和分析資料的全過程。
采用知識服務(wù)手段，借助技術(shù)和算法的力量，大大提高了科研資料收集和整理的效率，根據(jù)人們的需要有針對性地組織和分析知識，解決用戶最終信息需求。自動化的知識服務(wù)可以實現(xiàn)7×24全天候服務(wù)，通過網(wǎng)絡(luò)，可以為任何聯(lián)網(wǎng)用戶提供服務(wù)，沒有了時間、空間的限制，服務(wù)能力得到大幅提升。作為一種服務(wù)，它的特點在于它是一種面向知識內(nèi)容和解決方案的服務(wù)，它的目的是提高科研學習效率和質(zhì)量，促進學術(shù)創(chuàng)新。
4 幾項知識服務(wù)研發(fā)成果
北京萬方數(shù)據(jù)股份有限公司(以下簡稱萬方數(shù)據(jù))在近20年的信息服務(wù)中積累了千萬量級的高品質(zhì)學術(shù)信息資源，并擁有依托集群技術(shù)和分布式管理技術(shù)的網(wǎng)絡(luò)化存儲和高性能計算能力，筆者所在研發(fā)團隊以此為基礎(chǔ)，研發(fā)了萬方數(shù)據(jù)知識服務(wù)平臺，并在其中推出了多項得到學術(shù)界好評的知識服務(wù)成果。
查看更多《信息技術(shù)》雜志社信息請點擊： 《信息技術(shù)》編輯部
基金項目
(1)基于c＋＋ builder的共焦顯微鏡三維重建方法 楊召雷 張運波 董洪波
(4)m—link在通信系統(tǒng)仿真中的設(shè)計與實現(xiàn) 姚云龍 周俊 劉強
(8)基于嵌入式的無線煤炭自燃預(yù)警系統(tǒng) 劉德文 杜宇人
(11)tts語音單元的無損壓縮與按需解壓縮技術(shù) 卡斯木江·卡迪爾 古麗娜爾·艾力 艾斯卡爾·艾木都拉
無
(14)2012年中國國際信息通信展覽會開幕 無
基金項目
(15)低載荷工業(yè)機器人運動學分析與仿真 陳蓓玉 胡凱 楊樂
(19)基于zigbee無線傳感網(wǎng)絡(luò)監(jiān)測系統(tǒng)的實現(xiàn) 楊俊 阮超 陳?，?付紅橋
(23)endnote x5軟件在論文撰寫過程中的應(yīng)用 程宏輝 程筱農(nóng) 奚和平 黃新
(26)一種近距離無線傳感器系統(tǒng)的設(shè)計 葉天鳳 胡長暉 葉夢君 萬里光
(29)sakai網(wǎng)絡(luò)教學平臺統(tǒng)一身份認證中心的實現(xiàn) 柯水洲 馬雪梅 王新舸 鄒剛
(33)增益連續(xù)可調(diào)寬帶前置放大電路設(shè)計與實現(xiàn) 汪俊杰 蓋建新 劉旭 程爽
(37)actionscript3.0垃圾回收機制及優(yōu)化策略 李智勇
(40)基于彩信的遠程控制寵物籠系統(tǒng)的研制 楊樂 高超
(42)spring mvc技術(shù)分析及在實踐教學系統(tǒng)中的應(yīng)用 符紅霞
(47)支持向量機在廣義預(yù)測控制中的應(yīng)用 張偉 賈蓉
(50)測控信息技術(shù)領(lǐng)域提高學生實踐創(chuàng)新能力的方法 王可寧 劉纏牢 王偉 張雄星
(53)一種復雜背景下車牌定位算法 趙大偉 陳剛
研究與探討
(58)基于spce061a的語音手動雙控制開關(guān)的設(shè)計 李建新 張肖飛 徐麗妍
(62)基于bp神經(jīng)網(wǎng)絡(luò)的鉆井復雜情況和事故診斷 崔猛 汪海閣 李洪 紀國棟 于洋
無
(65)第九屆通信企業(yè)管理現(xiàn)代化創(chuàng)新成果審定會開幕 無
研究與探討
(66)一種基于單攝像頭的虛擬鍵盤 楊騁
(68)基于橢圓曲線的充值卡加密 孫傳亮 周海港
(72)基于ccd和光電編碼器的差速整定方法研究 李增彥 張迪洲 張男
(77)嵌入式軟件仿真測試平臺開發(fā) 林丹丹
(80)基于anybus-s pn io模塊的profinet遠程i/o設(shè)計 楊明 王永剛 張陸毅
(85)采用mel倒譜參數(shù)的咳嗽聲識別方法 尹永 莫鴻強
(92)模板匹配算法的兩種實現(xiàn)方法比較 謝方方 楊文飛 陳靜 李芳 于越
(96)基于msp430的低頻信號分析儀設(shè)計 張君 李金龍 郭建強 楊林曉
(101)基于labview的雙向智能鑰匙充放電測試系統(tǒng) 尹武 張文娟 周繼宇
br> (104)多用途市電負載功率調(diào)功電路的設(shè)計 姚正武 部紹海 林濤 李樹偉
(107)gps周跳探測與修復方法的比較分析 徐歡 唐亮 都業(yè)濤
(112)并行計算技術(shù)綜述 王磊
(116)衛(wèi)星遠程監(jiān)視及實時故障診斷研究與應(yīng)用 陳懷木 賈銀山 穆友勝
(121)基于soa的一體化繳費接入管理平臺設(shè)計 王樹全 鄒寧峰 金鑫
(125)基于增量式pid控制算法的智能車設(shè)計 肖文健 李永科
應(yīng)用技術(shù)
(128)油層保護模糊專家系統(tǒng)的分析與設(shè)計 張丹 曹謝東 魏存擋 龐揚
(131)基于multisim10低頻信號源的設(shè)計與仿真 蘭羽 周茜
(134)光電池基本特性的測定 趙楠 孫雪萍 李平舟
(137)基于單片機的無視頻報警監(jiān)測儀設(shè)計 李釗
(140)基于hfss的有孔屏蔽體的屏蔽效能分析 陳新平 楊顯清
(144)戰(zhàn)術(shù)無線電臺半實物仿真系統(tǒng)設(shè)計與實現(xiàn) 張愛民 辛廣輝 鄭振華
(147)基于混合高斯模型與核密度估計的目標檢測 呂游 任政 李向陽 方向忠
(151)基于業(yè)務(wù)流程的信息化建設(shè)與應(yīng)用 劉光偉
(153)基于國產(chǎn)cpu的嵌入式醫(yī)療電子無線網(wǎng)絡(luò)設(shè)計 裴家俊 張輝 劉蕓 戎蒙恬
(157)利用vba及office自動化技術(shù)輔助人事辦公 王晶
(159)數(shù)字鐘電路的設(shè)計 曹嘯敏
(163)基于電磁傳感器的智能車自主尋跡系統(tǒng)設(shè)計 師克 王洪軍 李永科
無
(166)上海市中國軟件名城創(chuàng)建暨軟件產(chǎn)業(yè)工作會召開 無
應(yīng)用技術(shù)
(167)異步時鐘亞穩(wěn)態(tài)仿真方法 高文輝 胥志毅 鄔天愷 劉文江 仲景尼
(170)lwip的移植及其在并行系統(tǒng)中的應(yīng)用 趙虎 黎英 游謙
(173)盲人行走輔助裝置中道路檢測算法的研究 徐姍姍 應(yīng)捷 宋彥斌
無
(176)尚冰出席第八屆中國信息無障礙論壇開幕式并致辭 無
應(yīng)用技術(shù)
(177)多載波傳輸系統(tǒng)的頻偏及采樣鐘聯(lián)合補償算法 李炎 周志平 李鑫
(181)智能小車模糊-pid控制調(diào)速系統(tǒng)設(shè)計 張家驊 徐連強 吳迎春
無
(183)第九屆海峽兩岸信息產(chǎn)業(yè)和技術(shù)標準論壇舉行 無
綜述與評論
(184)epc信息管理系統(tǒng)在裝備器材保障中的研究 康帥 高慶 程遠增
(187)基于供應(yīng)鏈信息共享的備件資源整合研究 黃健 程中華 王亞彬
(190)航空航天偵察情報保障能力綜合評價模型研究 童濤 楊桄 譚海峰 王壽彪 葉怡
(194)裝備保障信息評價研究 趙國存 劉占嶺
無
(f0003)
論文摘要：本體作為一種能在語義和知識層次上描述信息系統(tǒng)的概念模型建模工具，在應(yīng)用領(lǐng)域中得到了廣泛的使用，然而企業(yè)內(nèi)外部環(huán)境的改變，對本體提出了新的要求：本體必須不斷變化以適應(yīng)新的知識結(jié)構(gòu)，即實現(xiàn)知識管理系統(tǒng)的可重構(gòu)性。因此，基于本體的知識建模方法，從本體變化的角度分析了實現(xiàn)可重構(gòu)性的方法、技術(shù)和工具，最后，總結(jié)了目前研究尚存在的缺陷以及未來可能的研究方向。
1引言
1．I研究背景介紹．
隨著知識經(jīng)濟時代的到來，知識管理受到越來越多的關(guān)注，它跨越了眾多的學科，在眾多領(lǐng)域得到研究和應(yīng)用，如：產(chǎn)品設(shè)計領(lǐng)域、工藝制造領(lǐng)域、醫(yī)藥生物等。在不斷的研究和實踐中，人們設(shè)計和開發(fā)了各種知識管理系統(tǒng)、知識管理工具。但是，企業(yè)處在一個開放式的、不斷變化的環(huán)境中，一旦環(huán)境發(fā)生改變，知識結(jié)構(gòu)就要修改或補充，而已有的系統(tǒng)和工具不能滿足這些要求，因此，如何實現(xiàn)可重構(gòu)的知識管理系統(tǒng)成為迫切需要解決的問題。
1．2相關(guān)定義
定義i：本體(ontology)。本體是共享概念模型的明確的、形式化的規(guī)范描述。它包括概念模型、明確化、形式化和共享四層含義。本體由類、屬性(又叫槽)和個體及其之間的關(guān)系構(gòu)成。
定義2：本體進化(ontologyevolution)。它指在本體發(fā)生改變后，本體管理系統(tǒng)不會丟失數(shù)據(jù)或能保持一致性的能力。本體進化關(guān)心最新版本的有效性。
定義3：本體版本(ontologyversioning)。它指在本體發(fā)生改變后，本體管理系統(tǒng)允許訪問不同的版本。本體版本處理有效性、互用性和所有以前版本的管理。
定義4：可重構(gòu)知識管理系統(tǒng)。它指企業(yè)可以根據(jù)自身的特點來定制(包括改變和擴充)知識結(jié)構(gòu)框架，而相應(yīng)的知識錄入、維護、檢索和顯示界面等可以自動調(diào)整(或允許用戶定制)，以適應(yīng)新的知識結(jié)構(gòu)。
2本體變化與可重構(gòu)知識管理系統(tǒng)
2．1基于本體進化的方法和理論
由于領(lǐng)域知識是經(jīng)常變化的，所以描述這些知識的本體也需要作出相應(yīng)的變化，以實現(xiàn)知識管理可重構(gòu)性的需求。如前所述，本體進化與本體版本的側(cè)重點不同，本體進化關(guān)心的是新版本本體的有效性。怎樣滿足新的知識結(jié)構(gòu)、本體一致性的特征都將是本體進化所要研究的內(nèi)容。
德國Karlsruhe大學不少學者對本體進化等做了深人的研究。L·Stojanovic等人結(jié)合他們已經(jīng)開發(fā)的KAON(Karlsruhe本體和語義框架)，將本體進化流程分為6個階段：俘獲改變、表示改變、語義變化、執(zhí)行改變、延伸改變和改變生效，該流程系統(tǒng)地分析了知識改變的原因和結(jié)果，確保執(zhí)行改變后的本體及其依賴產(chǎn)物依舊保持它們的一致性。
為了滿足不同用戶的需求，該研究還讓用戶參與解決本體的變化問題，允許用戶設(shè)置高級的進化決策，建議用戶發(fā)掘潛本體應(yīng)用中的本體、實例或用戶行為的可能變化。但L Sto—jano~c等人的研究對本體的具體操作處理得不夠詳細，對變更的描述也存在缺陷，因此謝強、張磊提出了基于用戶自定義變更的本體進化方法(0E—UDC)，將用戶自定義變更轉(zhuǎn)換成原子變更，實現(xiàn)了本體變更的形式化描述問題。
浙江大學人工智能研究所的周明建等，在以O(shè)ML為本體建模語言的基礎(chǔ)上提出了EDOCOM框架，見圖1。該框架的特點是：(1)在處理進化前，已對可能存在的沖突進行分析和解決；(2)對于系統(tǒng)進化過程中，少量不能自動更新的內(nèi)容，采取公告管理的方法進行手動修改；(3)為版本管理和進化提供了充分的信息使其得以恢復到進化前的狀態(tài)。由于本體進化中會涉及到概念的修改和補充，但是該概念本身會和其他概念或類之間存在復雜的關(guān)系，如何實現(xiàn)對此概念的修改，與之關(guān)聯(lián)的彼概念能自動完成修改，是本體進化的一個關(guān)鍵點，本文獻對此介紹得不夠具體。此外，該框架面向的是OML語言，無法兼容W3C推薦的OWL語言。
華中科技大學孫小林在其博士論文中提出了基于2一型模糊邏輯推理的本體進化方法，彌補了本體系統(tǒng)對模糊信息研究很少的現(xiàn)狀。該方法采用2一FSWRL本體存放知識庫，以數(shù)據(jù)挖掘中增量式層次聚類算法為基礎(chǔ)，構(gòu)造一種基于2一型模糊描述邏輯的本體進化模型來實現(xiàn)2一型模糊本體半自動的構(gòu)建與進化，不僅可以大大減輕本體構(gòu)建初期的人工參與力度與工作量，而且能夠使本體在環(huán)境發(fā)生改變的時候迅速做出反應(yīng)。
2．2基于本體版本的方法和理論
為了完成本體版本交互和共享的功能，近年來研究者們開發(fā)了許多致力于管理、修改、進化本體的工具和系統(tǒng)。很多本體編輯工具，像prot6g6、OntoEdit都會有一個本體變更日志來記錄本體的版本變化，但是本體變更日志在不少情況下是難以獲取的，比如在語義網(wǎng)中，我們僅能得到新老版本的本體，而不是它們在變更時的紀錄。鑒于此，MichelKlein等建立了一個改變設(shè)置，與日志不同的是，它只記錄必要的操作記錄、操作不需要按順序記錄以及記錄方式不唯一。既然變更的方式不唯一，那么必須有一個統(tǒng)一的方法來整合這眾多的變更，因此，MichelKlein等又提出了一個集成所有變更的框架，實現(xiàn)了本體一致性的要求。
針對當前本體變化研究中本體變化的約束模型和算法缺失問題，柯賢達引入了本體變化表達的元數(shù)據(jù)模型，以一個類／概念來表達本體的某種變化，擴展建立一個Modify—Inst類，描述和記錄知識實例的變化，這一點與MichelKlein等的想法一致，不過后者的本體用于記錄基本變更操作和復雜變更操作。為了保證變化操作發(fā)生后本體的一致性，柯賢達提出用特定的算法來表示每一種類型的本體變化的約束。如果某一本體變化類型t對應(yīng)的約束算法為C，則這種對應(yīng)關(guān)系可以表達成為二元關(guān)系Corresp。ndence(t，c)。其中t∈Cchg，C∈{RulesCheckAlgorithm}。RulesCheckAl—gorithm算法用于檢測該本體變化操作是否可以執(zhí)行。每一種類型的本體變化對應(yīng)一個檢測算法。而所有這些約束算法構(gòu)成的集合稱之為ChangeCheckAlgorithmBase。
本體版本的研究的另一個方面是版本的匹配問題，不同版本間的單向匹配不能夠滿足用戶的不同需求，如何實現(xiàn)版本問的雙向匹配，實現(xiàn)數(shù)據(jù)共享和重用的能力，是本體版本研究的一個重要問題。中科大趙思陽等提出了一種新的本體版本匹配方法，方法可以對同一本體的兩個版本同時進行正向和逆向匹配，將不同版本中的相似元素聯(lián)系起來并相互轉(zhuǎn)換。其中，本體的雙向匹配用一個五元組{E1，E2，R，TE，M}來表示，E1，E2一兩種不同本體版本的匹配元素，R一匹配關(guān)系，TE一轉(zhuǎn)換表達式，M一元數(shù)據(jù)。在匹配方法的實現(xiàn)上，采用雙向轉(zhuǎn)換表達式來描述雙向轉(zhuǎn)換，提出使用單向表達式求逆的方法來將單向匹配表達式擴展到雙向轉(zhuǎn)換表達式，從而簡化了匹配算法。
PieterDeLeenheer提出了一個管理和修改多本體版本的獨立于模型的框架。為了保持表示模型的獨立性，它選擇可能世界本體來抽象地表示本體及其進化過程；此外，它受信度網(wǎng)的啟發(fā)，對版本的轉(zhuǎn)化進行了分類，它們是修改，擴展，壓縮和維持原狀。在研究的最后，作者介紹了框架實現(xiàn)必須具備的元件：本體格瀏覽器，用于定義轉(zhuǎn)化的編輯器及告示agent。
3基于本體的實現(xiàn)工具
Pr0t∈是斯坦福大學開發(fā)的本體編輯和知識獲取軟件，它提供版本間的日志變更，但是在語義網(wǎng)中，Prot6g6就顯得不足，因為本體的變更變得難以獲得，此外，Prot6g6是手動的輸入本體的內(nèi)容，必須記住其他的方法才能實現(xiàn)數(shù)據(jù)庫與本體庫的自動轉(zhuǎn)化。
OntoView是馬德里理工大學開發(fā)的本體版本匹配工具，其開發(fā)原理受CVS的影響，它能保持不同網(wǎng)絡(luò)本體間的互用，維護不同本體的改變以及不同版本概念問的聯(lián)系。德國的Karlsruhe大學對本體進化進行了不少研究，開發(fā)了KAON軟件，該軟件是目前功能和結(jié)構(gòu)較完善的語義網(wǎng)的支撐軟件，能協(xié)助大型本體的開發(fā)、修改和維護。一般地，它被分成：應(yīng)用和服務(wù)層、KAON API層以及數(shù)據(jù)和遠程服務(wù)層三個層次。其中，API中加入了本體管理和進化的重要元素，如：進化記錄、可逆性變更、進化決策、進化圖像、帶有同步進化的本體蘊含工具、本體發(fā)現(xiàn)和用戶使用軌跡記錄；()I～modeller是KAON框架的一部分，是一個本體和元數(shù)據(jù)工程化工具。目前本體進化的需求都可以在()I—modeller中實現(xiàn)它完善了KAON API在本體進化中的以一些缺陷，表現(xiàn)在：本體工程師可以設(shè)置進化決策；本體變更執(zhí)行前，系統(tǒng)會計算其他與之關(guān)聯(lián)的變更；提供了部分撤銷重做功能。
【關(guān)鍵詞】身份認證;MD5算法;分組變序;碰撞;安全
【中圖分類號】G420 【文獻標識碼】A 【論文編號】1009―8097(2010)09―0119―04
一 引言
現(xiàn)代遠程教育系統(tǒng)是以計算機軟硬件技術(shù)為基礎(chǔ),通過互聯(lián)網(wǎng)向處于不同地域的用戶提供教育服務(wù)的信息系統(tǒng)。遠程用戶在獲得教育服務(wù)之前,通常需要通過系統(tǒng)的身份認證。目前來講,最常用的身份認證技術(shù)是基于用戶名/密碼的靜態(tài)認證技術(shù)。該身份認證技術(shù)起源于上個世紀70年代初[1],認證系統(tǒng)通過登記、注冊等方式事先保存合法用戶的用戶名和密碼;認證時,系統(tǒng)將用戶輸入的用戶名和密碼與對應(yīng)合法用戶的用戶名和密碼進行匹配,以此來驗證用戶身份的合法性。在這種認證技術(shù)中,用戶名和密碼均以明文的方式進行傳輸和存儲,無法抵擋重放攻擊[2]。一種解決辦法是對密碼加密后再傳輸和存儲,只要加密算法夠可靠,就可以有效地防止重放攻擊。1992年,RIVEST R[3]提出了MD5(Message Digest 5)算法,該算法從理論上講具有不可逆性、離散型和唯一性[4],因此基于用戶名/密碼的靜態(tài)身份認證技術(shù)在應(yīng)用了MD5算法后,其安全性可以得到較大的增強。然而王小云[5]等人在2004年8月召開的國際密碼學會議(Crypto 2004)上做了破譯MD5、HAVAL-128、 MD4和RIPEMD算法的報告,給出了一種高效的MD5碰撞[6]方法,可以在短時間內(nèi)找到多個碰撞,這意味著如果攻擊者竊取到密文并且展開碰撞攻擊,則將有可能繞過認證,這又使得重放攻擊變?yōu)榭赡堋?/p>
針對這個問題,本文提出了一種基于MD5分組變序的動態(tài)身份認證技術(shù),該技術(shù)通過隨機數(shù),對原MD5密文采用分組變序的方法生成偽MD5密文存儲到數(shù)據(jù)庫中,并且每次驗證成功后,再次生成隨機數(shù)重新分組變序,產(chǎn)生另一個偽MD5密文替換原偽MD5密文,以此實現(xiàn)了用戶密碼明文不變,但數(shù)據(jù)庫中密文隨認證次數(shù)不斷變化的功能,進一步增強基于MD5的靜態(tài)身份認證技術(shù)的安全性,從而更安全地保護遠程教育系統(tǒng)中的教育資源以及用戶的信息。
二 基于MD5分組變序的動態(tài)身份認證技術(shù)
傳統(tǒng)的基于MD5用戶名/密碼的靜態(tài)身份認證技術(shù)是將用戶的密碼進行MD5加密,再發(fā)送到服務(wù)器端進行存儲,這種方式的安全性主要取決于MD5算法本身。除了向用戶騙取密碼以外,要獲取真正的密碼,只有通過對密文碰撞來獲得,然而從理論上來講,如果要對一個MD5密文使用窮舉法進行碰撞破解,用一臺運算速度為10億次/秒的超級計算機,需要 年[6],即使使用效率較高的生日攻擊法[5],同樣的運算速度,仍需要58年的時間[6],而王小云等人提出的方法則可以在數(shù)小時之內(nèi)找到一對碰撞[7],因此傳統(tǒng)的基于MD5用戶名/密碼的靜態(tài)身份認證技術(shù)已經(jīng)不再安全。進一步分析,如果碰撞的對象并不是MD5值,那一切針對MD5的碰撞方法將不起作用。本文提出的基于MD5分組變序的動態(tài)身份認證技術(shù)的核心即在于動態(tài)地生成偽MD5密文,使針對MD5值的碰撞攻擊無效,從而在原基于MD5的身份認證技術(shù)的基礎(chǔ)上,進一步增強其安全性。
該身份認證技術(shù)的體系結(jié)構(gòu)如圖1所示。
從圖中可以看出,所有關(guān)于用戶密碼的加密處理全部在客戶端完成,在網(wǎng)絡(luò)中僅傳輸用戶名、密鑰和加密后的偽MD5密文,而服務(wù)器端則為一個數(shù)據(jù)庫,僅起到存儲這些信息的功能,這么做既保證了網(wǎng)絡(luò)傳輸?shù)陌踩?對用戶的密碼又做到了消息級的加密[8]。
客戶端由密鑰生成、MD5加密、密文數(shù)組生成、偽MD5密文生成、偽MD5密文分割、密文數(shù)組比較六個模塊組成,這幾個模塊的不同組合構(gòu)成了用戶注冊和認證過程。
1 用戶注冊階段
用戶注冊主要流程如圖2所示。
步驟1:用戶輸入用戶名和密碼,客戶端首先對密碼進行MD5加密操作,得到32位長度的MD5字符串,記為 ;同時執(zhí)行密鑰生成程序,生成隨機數(shù),記為 , ,且 為32的因數(shù)。
步驟2:執(zhí)行MD5密文數(shù)組生成程序,將 按密鑰 的值為長度進行分組,將分組后的字符串存入字符串數(shù)組中,該字串符數(shù)組記為 。
步驟3:執(zhí)行偽MD5密文生成程序,隨機變換 中元素的順序,依次把值從變序后的 中取出,生成新字符串,該字符串即偽MD5密文,記為 。
步驟4:客戶端將用戶名、密鑰和偽MD5密文 發(fā)送至服務(wù)端,并存儲到數(shù)據(jù)庫中。
從注冊的過程可以看出,該認證技術(shù)的動態(tài)性體現(xiàn)在密鑰 的隨機性上, 的不同使密文 分組的位置不同,從而使得最終得到的密文 也是不同的。然而生成的偽MD5字符串 ,來源于標準的MD5字符串,這就為認證提供了依據(jù),但同時又不是MD5字符串,因此任何針對MD5算法進行的破解將不起作用。
2 用戶認證階段
用戶認證主要流程如圖3所示。
步驟1:待驗證用戶輸入用戶名和密碼,客戶端依然執(zhí)行MD5程序,將用戶輸入的密碼進行MD5加密,生成待驗證密文,記為 ,同時將用戶名發(fā)送至服務(wù)器端。
步驟2:服務(wù)器端從數(shù)據(jù)庫中查詢是否存在該用戶名,不存在則認證失敗,存在則取出數(shù)據(jù)庫中的偽MD5密文 和密鑰 ,一起傳輸至客戶端。
步驟3:用密鑰 對待驗證的MD5字符串 執(zhí)行客戶端MD5密文數(shù)組生成程序,得到待驗證的字符串數(shù)組中,該數(shù)組記為 ,同時執(zhí)行偽MD5密文分割程序,以 為每組長度對 進行分組,每 位后加入“,”生成分割后的偽MD5字符串,記為 。
步驟4:執(zhí)行密文數(shù)組比較程序,依次取出數(shù)組 中的值與 進行比較,如果 的每個元素都包含在 中,則通過認證,如果有一個不包含,則認證失敗。判斷的根據(jù)在于 本身只是對MD5字符串做了位置上的改變,如果待認證的口令正確,那么 中的每個元素都應(yīng)該包含在 中的,但只要數(shù)組中有一個元素不包含在密文字符串中,就可以判斷認證失敗。
步驟5:如果驗證通過,則對 再重新執(zhí)行一次分組變序操作,用得到的新的偽MD5密文和新密鑰替換原有的密文與密鑰,一起存入數(shù)據(jù)庫。
需要說明的是,本文給出的匹配方法并沒有直接把數(shù)據(jù)庫中的 和 的元素進行包含比較,而是以“,”分割后再比較,原因在于密文的長度為32,而數(shù)組中值的長度小于或等于32,那么不排除數(shù)組的值交叉包含于密文中的情況,假設(shè)密文是c4ca4238a0b923820dcc509a6f75849b,密鑰為16,則數(shù)組 的長度為2,再假設(shè)數(shù)組中的兩個值分別為a0b923820dcc509a,20dcc509a6f75849b,雖然這兩個值也都包含在密文中,但a0b923820dcc509a處于密文(c4ca4238-a0b923820dcc509a-6f75849b)的中間位置,而20dcc509a6f75849b處于密文(c4ca4238a0b9238-20dcc509a6f 75849b)的后半段,這種情況的出現(xiàn)有可能使匹配算法失效,反而造成認證的不精確。事實上標準的MD5字符串是多個16進制字符串的組合,而“,”是不可能出現(xiàn)在16進制字符串中的,采用“,”分組后再比較則可以有效地避免這種情況。
三 安全性驗證
本文為全文原貌 未安裝PDF瀏覽器用戶請先下載安裝 原版全文
以上認證技術(shù)是對單個MD5值進行分組變序,根據(jù)不同的 ,除去MD5值本身,每個MD5值能演變出 -1個偽MD5值,記為下式:
(1)
由于隨機數(shù)的存在,要還原得到真正的MD5值,只能通過暴力破解法來實現(xiàn),對于單個MD5值,暴力破解的運算量為 ,同樣使用一臺運算量為10億次/秒的超級計算機,需要約 年。
由于偽MD5密文和密鑰K均在網(wǎng)絡(luò)中傳輸,如果攻擊者知道該算法,利用密鑰K進行攻擊,那么最終密文的安全性取決于變換的順序種類。變換的順序種類由密鑰K確定,K越小,順序種類越多,破解的運算量越大。
對于單個MD5值,當 時, ,即不存在偽MD5值, 不可取。
當 時, ,暴力破解的運算量僅為1,很容易還原得到原始MD5值,因此密鑰為16時,已經(jīng)存在很大的安全隱患了。
當 時, ,暴力破解的運算量為23。
當 時, ,暴力破解的運算量為40319。
當 時, ,同樣使用一臺運算量為10億次/秒的超級計算機,需要約663457年。
當 時,暴力破解的運算量更是巨大的。
更進一步研究,該認證技術(shù)同樣適合對多個MD5值的組合進行分組變序,假設(shè) 為由 個 組成的長度為 的字符串,其中 。這種情況下,暴力破解的運算量為 ,這樣的運算量更是天文數(shù)字。而在知道該認證算法的情況下,暴力破解的運算量為 , , 可取的值更多,運算量更大。
對于應(yīng)用該認證技術(shù)的系統(tǒng)來講,運算量僅僅取決于變序算法的復雜度,本文采取經(jīng)典的洗牌算法[9]作為變序算法,以隨機數(shù) 作為變序的基礎(chǔ),以保證每次交換順序后的結(jié)果與交換之前的不同,算法復雜度僅為數(shù)組的長度,即 。
實際應(yīng)用時,當 , 時,最終生成的密文的安全性將是相當高的。而當 時,可選擇的 更多,安全性則更高,而同時對認證系統(tǒng)的運算量并不會有太大增加。
四 實驗分析
本實驗選擇瀏覽器/服務(wù)器作為運行模式,選擇JavaScript作為客戶端注冊、認證程序編寫語言,保證運算均在瀏覽器端完成,選擇Java作為服務(wù)器端數(shù)據(jù)庫訪問語言,選擇MySQL作為測試數(shù)據(jù)庫。假設(shè)密碼明文為888888,則MD5值為21218CCA77804D2BA1922C33E0151105,對比最終密文、密鑰做8次運算,其中第一次為注冊,后7次為認證,運算結(jié)果對比如表1所示。
從表1可以看出,最終生成的密文已經(jīng)和原MD5值已經(jīng)有較大的不同,即使是相同的密鑰,由于交換了順序,密文也是不同的,攻擊者即使得到這些密文,也是徒勞的。
五 結(jié)束語
本文通過分析目前遠程教育系統(tǒng)常用的身份認證技術(shù)的優(yōu)缺點,以基于MD5的用戶名/密碼的靜態(tài)身份認證為基礎(chǔ),提出了基于MD5分組變序的動態(tài)身份認證技術(shù),該技術(shù)通過分組變序隨機地產(chǎn)生偽MD5密文,將偽MD5密文在客戶端和服務(wù)器端之間傳輸,并存儲到數(shù)據(jù)庫中,從而可以有效抵擋碰撞攻擊和重放攻擊,并且實現(xiàn)了數(shù)據(jù)庫中的密碼隨認證次數(shù)不斷變化,而對用戶透明的功能,進一步增強了原基于MD5的用戶名/密碼的靜態(tài)身份認證的安全性。同時,該技術(shù)僅僅是對經(jīng)MD5加密后的密文進行再處理,與MD5算法本身并有沒有很大的關(guān)聯(lián),因此具有一定的通用性,只要稍做修改,就可以用于任何基于不可逆算法的身份認證技術(shù)中,以起到在原有認證技術(shù)的基礎(chǔ)上,增加其安全性的作用。
參考文獻
[1] 曹雪菲.基于身份的認證協(xié)議的理論及應(yīng)用研究[D].西安:電子科技大學,2008.
[2] Carles Garrigues, Nikos Migas, William Buchanan, et al. Protecting mobile agents from external replay attacks[J]. Journal of Systems and Software,2009,82(2):197-206.
[3] RIVEST R.RFC 1321 The MD5 Message-Digest Algorithm[S].Boston: MIT Laboratory for Computer Science and RSA DATA Security, Inc, 1992.
[4] 王津濤,覃尚毅,王冬梅.基于MD5的迭代冗余加密算法[J].計算機工程與設(shè)計,2007,28(1):41-42.
[5] Wang Xiaoyun, Feng Dengguo, Lai Xuejia, et al. Collisions for hash functions MD4, MD5 Haval-128 and RIPEMD[R].CRYPTO 2004, Cryptology ePrint Archive, 2004.
[6] Eric Thompson.MD5 collisions and the impact on computer forensics[J].Digital Investigation,2005,2(1): 36-40.
[7] 張裔智,趙毅,湯小斌.MD5算法研究[J].計算機科學, 2008,35(7):295-297.
[8] Paul Kearney.Message level security for web services[J].
Information Security Technical Report, 2005,10(1):41-50.