基于模式匹配算法的空間屬性數(shù)據(jù)挖掘仿真

曹麗娜，王 霞，周 瑛

(石家莊鐵道大學四方學院，河北石家莊051132)

1 引言

隨著數(shù)字化的發(fā)展，地理信息系統(tǒng)應運而生。地理信息系統(tǒng)是一種空間信息系統(tǒng)，包含各種地理分布屬性數(shù)據(jù)，海量信息對數(shù)據(jù)的存儲和管理增加了不小的壓力。從海量多屬性數(shù)據(jù)中過濾冗余數(shù)據(jù)，挖掘出主要數(shù)據(jù)信息難度較大，空間屬性數(shù)據(jù)的準確挖掘至關(guān)重要。

盧浩等人提出利用Apriori算法完成數(shù)據(jù)挖掘。模式匹配算法是一種用于挖掘數(shù)據(jù)的常用算法，具有簡單直接易懂等優(yōu)點。但該算法運行時間過長。馬蘭等人以模式匹配算法為基礎(chǔ)，提出使用無回溯模式匹配算法進行數(shù)據(jù)挖掘，解決了普通模式匹配算法不必要的回溯匹配問題，能夠提高效率，但數(shù)據(jù)的復雜程度較高，導致匹配準確性不夠理想。

因此本文在上述研究基礎(chǔ)上提出基于弱無回溯模式匹配算法的空間屬性數(shù)據(jù)挖掘方法，在保證高效率挖掘空間屬性數(shù)據(jù)基礎(chǔ)上，提升挖掘準確性，為數(shù)據(jù)挖掘提供技術(shù)支持。

2 空間數(shù)據(jù)庫

數(shù)據(jù)庫有一般關(guān)系數(shù)據(jù)庫、事務數(shù)據(jù)庫等類型，其中地理信息系統(tǒng)使用的數(shù)據(jù)庫為空間數(shù)據(jù)庫，該數(shù)據(jù)庫由相當多的空間數(shù)據(jù)和屬性數(shù)據(jù)組成，具有特殊重要性。空間數(shù)據(jù)庫系統(tǒng)的語義信息比其它數(shù)據(jù)庫系統(tǒng)更復雜和豐富，但這種豐富也造成更多冗余數(shù)據(jù)出現(xiàn)。因此從空間數(shù)據(jù)庫中挖掘重要信息和知識尤為重要，這種約減空間數(shù)據(jù)和屬性數(shù)據(jù)行為稱為空間數(shù)據(jù)挖掘。

地理信息系統(tǒng)的空間數(shù)據(jù)庫中除了有關(guān)于對象集合的空間位置和拓撲關(guān)系外，還擁有與該對象有關(guān)的屬性信息。其中空間數(shù)據(jù)具體包括位置信息和拓撲信息，屬性數(shù)據(jù)具體包括名稱、類型和特性等信息。

在空間參照系中空間實體的具體位置以及和其它相鄰對象間的關(guān)系均可通過空間定位特征確定，由空間數(shù)據(jù)描述的空間對象都具有這種特征?？臻g對象還具有由屬性數(shù)據(jù)的屬性碼和屬性值描述的質(zhì)量特征。

除此之外，空間對象還具有多維特征和時序特征。多維特征中二維指平面，三維指空間位置，在三維基礎(chǔ)上加入時間參數(shù)是四維，二維基礎(chǔ)上加數(shù)字地面模型是2+1維，二維基礎(chǔ)上加高度屬性值是2.5維?？臻g對象隨時間變化的特征稱為時序特征。

屬性數(shù)據(jù)反映了空間對象的特征，分為非空間型和空間型兩種。類型、名稱等為非空間型的特征，邊長、體積等則為空間型的特征。

3 空間屬性數(shù)據(jù)的弱無回溯模式匹配挖掘算法

有效結(jié)合空間數(shù)據(jù)庫特點，采用挖掘效率和精度更具優(yōu)勢的弱無回溯模式匹配(KMP)算法挖掘空間數(shù)據(jù)庫中的屬性數(shù)據(jù)。

3.1 模式匹配算法思想

設(shè)兩個字符串和：=，，…，，=，，…，，其中0<<=，表示目標子串，表示模式子串。在中查找與相同的子串即為目的。如果在中查找到子串與相同，則匹配完成，指出該子串在的位置，實現(xiàn)數(shù)據(jù)挖掘；如果在中有不止一個子串與相同，找出第一個子串即為挖掘成功。若中匹配一次找不到模式為的子串則稱第一次匹配失敗，此時串移動一個字符位，強制串的指針向前返回，串重新對比串對應字符，進行第二次匹配，這種行為稱為算法的回溯。在這種算法下，當中逐漸增大時，回溯次數(shù)也隨之增加。

這就出現(xiàn)一個問題，最好情況是一次匹配成功，但可能出現(xiàn)最壞情況即最后一次匹配成功——匹配-+1次，每次匹配對比次，共需要對比×(-+1)次，導致匹配挖掘時間大幅增加。由此提出無回溯模式匹配算法。

3.2 無回溯模式匹配算法(KMP)

3.2.1 KMP算法思想

模式匹配算法中的回溯行為是無意義的。比如與字符串中，=，=，〈〉，由〈〉得到〈〉，右移一個字符位再與比較肯定是不相等的，因此一次回溯無意義。而=又能得到=，此時右移一個字符位依然不等于，二次回溯無意義。當右移三個字符位時出現(xiàn)了必要移動，此時串的指針不必向前返回，而是從串中定位一個合適點進行比較。

當串在匹配過程中已經(jīng)成功匹配[]前的每個字符，而[]≠[]，即[1…-1]=t[j-+1…j-1]時，串無回溯。此時判斷串右移位數(shù)，確定中與中當前字符比較的字符，記為[]。[]位置比[]更靠前，因此比大，則對于不同的值有不同的值，值只由串中的前個字符決定，與串不相關(guān)。那么考慮將這個匹配進程加快，通過建立數(shù)組先計算出每個[]處的移動值實現(xiàn)。對應i的k值用next[i]表達，當next[i]與0相等時，不需要再將Y串中字符對比t[j]；否則匹配過程中出現(xiàn)y[i]不等，next[i]比0大，需要使用Y中第next[i]個字符對比t[j]。

3.2.2 KMP算法

設(shè)完成匹配next[i]數(shù)組

[初始化]

i←1：j←i

[重復使用next[i]比較]

循環(huán)i<=m且j<=n時重復執(zhí)行

若y[i]=t[j]則i←i+1：j←j+1

否則若next[i]>0則i←next[i]

否則i←1：j←j+1

KMP算法中T串無回溯，受j值持續(xù)增大影響導致，出現(xiàn)匹配失敗時Y串立即通過next數(shù)組移動到合適的位置。

上述算法中j以1為初值，且持續(xù)增大，循環(huán)過程中始終j<=n，因此算法中最多循環(huán)執(zhí)行n次j←j+1，同樣地，i←i+1也最多執(zhí)行n次。此外i也以1為初值，循環(huán)過程中始終i>0，next[i]

目標串T與next無相關(guān)性，由模式串Y決定next數(shù)組的值。因此next數(shù)組的值可在給定模式串Y匹配前預先求得。next[i]由下述k的性質(zhì)決定，取最大值。

1)1<=k

2)y[1…k-1]=y[i-k+1…i-1]

3)y[k]〈〉y[i]

若k不滿足上述條件，取k的值為0。

next[i]的值減去1即為y[1…k-1]中相同的前綴子串和后綴子串的最大長度，因此要找出真子串最值再計算next[i]。實際上確定next[i]值的過程同樣是模式匹配，只是模式串和目標串都是Y串。next數(shù)組算法見下文。

[初始化]

i←1：j←0；next[1]←0[重復對比計算]

循環(huán)當i

1)[找到y(tǒng)[1…i]中相同前綴和后綴的最大長度，將此值送j]

循環(huán)當j>0，y[i]〈〉y[j]時，反復執(zhí)行j←next[j]

2)[計數(shù)器+1]

i←i+1；j←j+1

3)[計算next[i]]

當y[i]=y[j]，則next[i]←next[j]，否則next[i]←j

next數(shù)組算法通過無回溯模式匹配算法進行優(yōu)化可降低其時間復雜度。優(yōu)化后的算法不需逐個移位，更不需每次移位后都重新進行對比，只需考慮y[1…i]中的前綴和后綴。計算next[i+1]時只需先求得next[1]，next[2]，…，next[i]的值然后加以利用即可快速匹配，提升匹配效率。任何模式串Y中始終有next[1]=0，由此提供了計算next[i]的基礎(chǔ)。

3.3 基于弱KMP算法的數(shù)據(jù)挖掘

3.3.1 基本思想

KMP模式匹配算法嚴格查找與模式串相同的字符串，當數(shù)據(jù)出現(xiàn)信息倒置或修飾等情況，就會影響KMP算法的挖掘準確率。因此對KMP算法進行改進，提出一種弱KMP模式匹配挖掘算法進行空間屬性數(shù)據(jù)挖掘。

目標串中存在部分與模式串相似但不完全相同的字符，KMP算法的嚴格性會忽略這種相似信息，認為這種目標串并不是完全不匹配模式串，因此利用一些手段重新查找匹配。加入數(shù)據(jù)準確權(quán)數(shù)標準和數(shù)據(jù)增多滑動窗口，此時再進行比對，這種算法稱為弱KMP模式匹配挖掘算法。

3.3.2 逆序數(shù)

全排列的產(chǎn)生使用從1開始的自然數(shù)編號個不同元素。令其中一個為標準排列，若其它排列中存在逆序，該排列的部分元素就與標準排列中這部分元素排列次序相反。一個排列中一共含有多少個逆序，逆序數(shù)的數(shù)值就為多少。

333 數(shù)據(jù)準確權(quán)數(shù)

反應模式串與目標串匹配程度的參數(shù)為準確權(quán)數(shù)。假設(shè)一個串由個數(shù)據(jù)組成，當發(fā)生完全匹配時，準確權(quán)數(shù)就為；當發(fā)生不完全匹配時，準確權(quán)數(shù)設(shè)為(0<=<=)，則目標串和模式串的匹配程度為。

假設(shè)模式串中有個按順序排列的數(shù)據(jù)，但這些數(shù)據(jù)還可以變換順序，為了求出數(shù)據(jù)序列的逆序數(shù)，編號每個數(shù)據(jù)，則最大逆序數(shù)按照式(1)計算

(1)

將目標數(shù)據(jù)的準確權(quán)數(shù)關(guān)系式定為式(2)

(2)

當=1，=0時，準確率為1。

334 數(shù)據(jù)增多滑動窗口

假設(shè)模式串中有個按順序排列的數(shù)據(jù)，當目標串中含有的對應數(shù)據(jù)比模式串多，長度較長，要分別向前和向后延長滑動窗口，延長長度為所有缺少的數(shù)據(jù)數(shù)。

在本文方法中，當數(shù)據(jù)準確權(quán)數(shù)為時，選擇KMP模式匹配算法進行數(shù)據(jù)挖掘即可；數(shù)據(jù)準確權(quán)數(shù)為a(0<=a<=n)時，使用弱KMP模式匹配挖掘算法，將滑動窗口延長，擴充進缺少數(shù)據(jù)，對新的數(shù)據(jù)計算準確權(quán)數(shù)，最終結(jié)果與原窗口數(shù)據(jù)的準確權(quán)數(shù)相加，保證挖掘準確率。

4 仿真研究

4.1 本文數(shù)據(jù)挖掘方法的應用效果

使用本文方法對某地農(nóng)業(yè)空間屬性數(shù)據(jù)庫進行挖掘仿真，挖掘2016年到2020年夏玉米和冬小麥的相關(guān)數(shù)據(jù)，其中夏玉米選取6月數(shù)據(jù)，冬小麥選取4月數(shù)據(jù)，挖掘結(jié)果見表1。

表1 本文方法挖掘空間屬性數(shù)據(jù)

根據(jù)表1可知，使用本文方法可對空間屬性數(shù)據(jù)進行有效挖掘。且查閱歷史數(shù)據(jù)，發(fā)現(xiàn)本文通過仿真獲取的挖掘數(shù)據(jù)與真實數(shù)據(jù)誤差較小，因此可以確定本文方法在挖掘空間屬性數(shù)據(jù)上的應用性良好。

4.2 多種類數(shù)據(jù)文檔下挖掘性能分析

從數(shù)據(jù)庫中選取三個文檔A、B、C，大小分別為95kB、158kB、384kB，采用本文方法分別對其進行匹配挖掘，匹配次數(shù)對比結(jié)果見圖1。

圖1 各文檔挖掘匹配次數(shù)

根據(jù)圖1可知，匹配次數(shù)隨著模式串長度增加而相對穩(wěn)定增加。數(shù)據(jù)越多，其中可匹配的模式串就越多，因此匹配次數(shù)也隨之增加。由圖2可知當模式串數(shù)值較小時，與匹配次數(shù)間線性關(guān)系較小，出現(xiàn)包含較大數(shù)據(jù)量的文檔C匹配次數(shù)比文檔A與文檔B小的情況；且模式串較小時，越大的文檔匹配次數(shù)上升趨勢也越大。模式串逐漸增大時，文檔C的匹配次數(shù)上升趨勢逐漸放緩，即匹配時間也隨之降低，說明本文方法在大量數(shù)據(jù)中挖掘效率更高。

4.3 挖掘效率和準確率測試

為了對比本文方法應用的弱KMP算法進行空間屬性數(shù)據(jù)挖掘的優(yōu)越性，將其與KMP算法和模式匹配算法進行對比分析。從空間屬性數(shù)據(jù)庫中選取五個空間屬性數(shù)據(jù)包，大小依次為198k、356k、525k、684k、837k，對比應用三種算法挖掘空間屬性數(shù)據(jù)的時間和準確率，對比結(jié)果見圖2。

圖2 不同數(shù)據(jù)量下三種算法挖掘性能

由圖2(a)可得，三種算法的挖掘時間均受數(shù)據(jù)量影響，呈正比例關(guān)系，模式匹配算法時間消耗量始終高于另外兩種算法；弱KMP算法和KMP算法上升趨勢更平穩(wěn)，且前者消耗時間最少。這是因為KMP算法比模式匹配算法少了不必要的回溯匹配過程，大大縮減了挖掘時間，提高運行效率，而弱KMP算法避免了數(shù)據(jù)出現(xiàn)信息倒置等情況，運行效率更高一點。

由圖2(b)可知，模式匹配算法和弱KMP算法在數(shù)據(jù)量增多時均能保持高準確率，模式匹配算法不斷回溯精準匹配對比，而本文應用的弱KMP算法準確挖掘水平也能達到與模式匹配算法不相上下，但時間消耗卻縮短了一半。

弱KMP算法挖掘時間消耗偶爾較KMP算法多，但整體時間效率和準確率都比另外兩種算法高。與模式匹配算法相比，KMP算法在節(jié)省時間上更有優(yōu)勢，而模式匹配算法準確率更高。但弱KMP算法保證時間效率下挖掘準確率也能達到90%以上，主要原因為當模式串中字符順序發(fā)生改變，或者含有其它信息摻雜在一起，KMP算法嚴格匹配性導致較難準確挖掘，但本文提出的弱KMP算法可通過延長滑動窗口、計算準確權(quán)數(shù)應對各種復雜變化形式，能夠有效匹配，提高挖掘準確率。

綜合時間效率與準確率兩個方面，本文應用的弱KMP模式匹配算法在空間屬性數(shù)據(jù)挖掘中展現(xiàn)出了較好的優(yōu)越性。

5 結(jié)論

提出基于弱KMP模式匹配算法挖掘空間屬性數(shù)據(jù)。以數(shù)據(jù)挖掘時間效率和準確率為測試指標，設(shè)計仿真。仿真結(jié)果驗證了本文方法能夠在復雜數(shù)據(jù)環(huán)境中保證高準確率，且大幅提高挖掘效率，具有較好的應用性。