基于0-1矩陣的時空關(guān)聯(lián)規(guī)則提取方法研究

基于0-1矩陣的時空關(guān)聯(lián)規(guī)則提取方法研究

主要研究計算機應(yīng)用。

鄭瑾

(福建船政交通職業(yè)學(xué)院信息工程系，福州 350007)

摘要：基于Apriori算法提出了基于0-1矩陣的時空關(guān)聯(lián)規(guī)則挖掘算法，并以挖掘不同年代的土地覆蓋現(xiàn)狀之間的時空關(guān)聯(lián)關(guān)系作為試驗案例，對比Apriori算法的提取結(jié)果和提取效率，研究結(jié)果表明：該算法不僅減少了掃描數(shù)據(jù)庫的次數(shù)，而且減少了冗余候選項集的產(chǎn)生，提高了時空關(guān)聯(lián)規(guī)則的提取效率。

關(guān)鍵詞：0-1矩陣；時空關(guān)聯(lián)規(guī)則；Apriori算法

0引言

數(shù)據(jù)挖掘(Data Mining)是指從數(shù)據(jù)庫或數(shù)據(jù)倉庫中提取隱含的、潛在的、有用的、最終可理解的知識和規(guī)則等，其中關(guān)聯(lián)規(guī)則是DMKD中的重要內(nèi)容之一[1]，它反映出在給定的數(shù)據(jù)庫或數(shù)據(jù)倉庫中，大量數(shù)據(jù)之間存在的內(nèi)在關(guān)聯(lián)關(guān)系，形如X->Y的蘊含式。隨著地理信息系統(tǒng)(Geographical Information System，GIS)與遙感技術(shù)(Remote Sensing，RS)的迅速發(fā)展，空間數(shù)據(jù)呈現(xiàn)出“爆炸式”增長，由于空間數(shù)據(jù)具有空間性、時間性、多維性、海量性、復(fù)雜性、不確定性等特點[2]，因此，如何從海量的空間數(shù)據(jù)中獲取有用的知識成為許多學(xué)者重點關(guān)注的問題。李德仁教授在1994年于加拿大渥太華舉行的地理信息系統(tǒng)國際學(xué)術(shù)會議上，首次提出了從GIS數(shù)據(jù)庫中發(fā)現(xiàn)知識(Knowledge Discovery from GIS，KDG)的概念[3]，系統(tǒng)性地分析了各種空間或非空間的知識類型與挖掘算法。目前，空間關(guān)聯(lián)規(guī)則挖掘的主要方法是通過將空間數(shù)據(jù)庫進行泛化，建立一般事務(wù)數(shù)據(jù)庫，并利用關(guān)聯(lián)規(guī)則挖掘算法，如Apriori算法，從中提取空間關(guān)聯(lián)模式。K.Koperski[4]與陳剛[5]等都曾將Apriori算法應(yīng)用于空間關(guān)聯(lián)規(guī)則領(lǐng)域，提取有趣的空間關(guān)聯(lián)模式。若同時考慮時間維與空間維兩因素，則關(guān)聯(lián)規(guī)則將從平面擴展到立體，形成了時空關(guān)聯(lián)規(guī)則。

時空關(guān)聯(lián)規(guī)則旨在發(fā)現(xiàn)時空數(shù)據(jù)庫或時空數(shù)據(jù)倉庫中各數(shù)據(jù)項集之間潛在的、有用的時空關(guān)聯(lián)關(guān)系，是時空數(shù)據(jù)挖掘領(lǐng)域中最為關(guān)鍵的技術(shù)難點之一。李波等通過建立具有時間與空間特征的洪澤湖水質(zhì)數(shù)據(jù)庫，基于相關(guān)數(shù)據(jù)矩陣獲取洪澤湖水質(zhì)的時空相關(guān)性及其時間和空間分布規(guī)律[6]；沙宗堯提出了時序空間關(guān)聯(lián)規(guī)則挖掘方法，并應(yīng)用于土地類型變化的時空關(guān)聯(lián)分析中[7]；岳慧穎提出了SKDM(Shi Kong Data Mining)算法，先后考慮空間與時間的雙重約束[8]；Florian Verhein等提出了一種應(yīng)用于交通高區(qū)域進行屬性約減的STAR(Spatio-Temporal Association Rules)算法，將關(guān)聯(lián)規(guī)則擴展到時空領(lǐng)域[9]；Marcin Gorawski等基于Apriori算法的基礎(chǔ)上，擴展了自連接的約束條件，從而生成了使用關(guān)聯(lián)模式[10]；夏英等則是綜合分析了SKDM與Apriori算法的基礎(chǔ)上提出了STApriori算法，并應(yīng)用于交通系統(tǒng)中分析交通擁堵趨勢[11]。時空關(guān)聯(lián)規(guī)則挖掘需要同時考慮時間與空間的約束，本研究基于Apriori算法原理，并在綜合考慮空間數(shù)據(jù)特點的基礎(chǔ)上，提出了基于0-1矩陣的時空關(guān)聯(lián)規(guī)則挖掘算法，重新定義了時空數(shù)據(jù)頻繁項集，最后將該算法應(yīng)用于不同年代的土地覆蓋類型之間的時空關(guān)聯(lián)性分析，以證明該算法的有效性。

1算法原理

Apriori算法是數(shù)據(jù)挖掘領(lǐng)域中關(guān)聯(lián)規(guī)則挖掘的經(jīng)典算法之一，該算法于1994年由R.Aglawal等[12]人提出的，該算法的詳細原理和過程見文獻[12]。其本質(zhì)思想是使用一種逐層搜索的迭代方法，根據(jù)挖掘出的頻繁-(k-1)項集通過Apriori-gen()函數(shù)，產(chǎn)生用于挖掘頻繁k-項集的候選項集合(k>=2)，依此循環(huán)直至不能再產(chǎn)生新的頻繁項集為止。該算法每產(chǎn)生一個頻繁k-項集，都需要掃描一次數(shù)據(jù)庫，并且會產(chǎn)生大量的候選項集，造成冗余項集比較多，時間開銷比較大，尤其是面對海量數(shù)據(jù)時，其局限性表現(xiàn)得更為明顯?；贏priori算法的缺陷，許多學(xué)者開始探討如何提高Apriori算法的效率，許多基于Apriori的改進型算法也相繼被提出，如FP-Growth算法[13]等。

本研究在基于布爾矩陣的Apriori改進型算法[14]原理的基礎(chǔ)上，結(jié)合空間數(shù)據(jù)的特點，重新定義時間數(shù)據(jù)頻繁項集，提出了基于0-1矩陣挖掘最大頻繁項集的時空關(guān)聯(lián)規(guī)則挖掘算法，該算法的基本思想是定于最小支持度與置信度，基于Apriori算法提取頻繁1-項集與包含每個頻繁1-項集的事務(wù)ID，每個頻繁1-項集都帶有時間約束條件，并構(gòu)建行標題為頻繁1-項集，列標題為事務(wù)ID的0-1矩陣，該矩陣中，值取‘1’表示該事務(wù)ID包含對應(yīng)的頻繁1-項集，反之不包含。針對該布爾矩陣，計算矩陣中每一列包含‘1’的數(shù)量，若相同數(shù)量‘1’的總列數(shù)大于最小事務(wù)支持度，則將該值假定為最大頻繁項集的可能長度，依此循環(huán)，可得到最大頻繁項集的所有可能性長度?；谠撻L度值，從頻繁1-項集中產(chǎn)生最大頻繁項集的候選項，并計算每個候選項的支持度，如果支持度超過最小事務(wù)支持度，則頻繁，反之不是。最后依據(jù)頻繁項集的非空子集仍頻繁的原理得到所有頻繁項集。由此可見，該算法的基本原理主要包括以下3個方面。

1.1構(gòu)建0-1矩陣

定義最小事務(wù)支持數(shù)，首次掃描事務(wù)數(shù)據(jù)庫時，利用Apriori算法提取頻繁1-項集，每個頻繁1-項集都需要帶有時間約束條件與包含該頻繁1-項集的事務(wù)標識號，定義頻繁1-項集的0-1數(shù)組，長度為事務(wù)數(shù)據(jù)庫的數(shù)量，在該0-1數(shù)組中，頻繁1-項集帶有的事務(wù)標識號TID在數(shù)組中對應(yīng)位置的值為‘1’，不帶有的標識號在數(shù)組中值為0。最后將所有的頻繁1-項集的0-1數(shù)組構(gòu)建成頻繁1-項集0-1矩陣。

定義1頻繁1-項集的0-1數(shù)組為Im[N]TI={BLT1，BLT2，…，BLTn}(1≤n≤N)，其中Im為第m個頻繁1-項集，N為事務(wù)單元的數(shù)量，TI為時間約束條件，T1至Tn分別表示第1個至第n個事務(wù)單元的TID，BLT1至BLTn只取0或1。

輸入：事務(wù)數(shù)據(jù)庫—DTI，最小支持度-m_sup

Begin

foreachtinD

end for

end for

End

1.2提取最大頻繁項集

在0-1矩陣中，每列代表了一條事務(wù)單元記錄，列中‘0’值表示該事務(wù)單元中不包含對應(yīng)的頻繁1-項集，反之，值‘1’則表示含有的頻繁1-項集。因此，‘1’的數(shù)量代表了該事務(wù)單元同時含有的頻繁1-項集的數(shù)量，如果含有相同數(shù)量‘1’的事務(wù)記錄數(shù)的數(shù)量大于最小事務(wù)支持數(shù)，則可以將‘1’的數(shù)量值擬定為最大頻繁項集可能性長度，將所有可能性取值從大到小排序，并依次根據(jù)頻繁1-項集獲取可能性長度的最大頻繁項集的候選項集，通過0-1矩陣來獲取每個候選項集的支持，若支持度大于預(yù)先設(shè)定的最小事務(wù)支持數(shù)，則為最大頻繁項集，反之不是，若都不是最大頻繁項集，則最大頻繁項集的長度為1。

定義3MaxLen[n]為存儲最大頻繁項集可能性長度的數(shù)組，其中n為該數(shù)組的數(shù)量。

定義5候選項的支持度Support(C)=In1[N]TI1&In2[N]TI2&…Inm[N]TIn，其中‘&為布爾運算中的‘與’計算，以下為該部分的偽代碼描述：

輸出：最大頻繁項集-Lk

Begin

常用算法包括以下幾種：平滑、中職與均值濾波。基于以往濾波經(jīng)驗，改進平滑濾波，分析中值和均值兩種方法的結(jié)合。

count the number of value 1 in the current column

end for

pos_len=count the number of the columns with the same number of value 1

if pos_len>m_sup

return MaxLen[n]

end if

Sort(MaxLen[n])

foreach value in MaxLen[n]

foreach itemset in candidate itemsets

if Support(itemset)>m_sup

itemset is frequent

end if

if Maximum frequent itemsets is not null

break;

end if

end for

end for

End

1.3提取所有子頻繁項集

根據(jù)最大頻繁項集的非空子集也頻繁的原理，利用得到的最大頻繁項集，產(chǎn)生余下所有的頻繁項集，所有產(chǎn)生的頻繁項集的支持度仍然按照定義5中的原理進行計算獲取，最后利用所有的頻繁項集來產(chǎn)生關(guān)聯(lián)規(guī)則。

2算法實現(xiàn)及性能比較

為了證明該算法的有效性，本研究以挖掘不同年代的土地覆蓋現(xiàn)狀之間的時空關(guān)聯(lián)關(guān)系作為試驗案例，以2005年—2010年從遙感影像提取的廈門市土地利用現(xiàn)狀圖作為試驗數(shù)據(jù)，分別利用該算法和Apriori算法提取不同年代土地覆蓋類型之間的時空關(guān)聯(lián)規(guī)則，最后對比并分析兩者提取效率的差異性。

2.1數(shù)據(jù)預(yù)處理

根據(jù)目前時空關(guān)聯(lián)規(guī)則挖掘的主要思想，需要對不同年代的土地覆蓋現(xiàn)狀數(shù)據(jù)進行預(yù)處理，將空間數(shù)據(jù)泛化，建立時空事務(wù)數(shù)據(jù)庫?；贗mam Mukhlash和Benhard Sitohang[15]提出空間數(shù)據(jù)預(yù)處理框架，需要進行以下2個方面的空間數(shù)據(jù)預(yù)處理。

2.1.1數(shù)據(jù)準備與處理

獲取從遙感影像解譯的從2005年至2010年的廈門市土地利用覆蓋現(xiàn)狀矢量數(shù)據(jù)，并對該數(shù)據(jù)進行矢量轉(zhuǎn)柵格處理，將處理結(jié)果重采樣成分辨率為100 m的柵格數(shù)據(jù)。最后，利用試驗區(qū)的行政區(qū)范圍，對以上數(shù)據(jù)進行范圍界定，以保證各空間數(shù)據(jù)范圍的一致性。

2.1.2讀取柵格數(shù)據(jù)屬性值，構(gòu)造事務(wù)表

以單個格網(wǎng)單元作為單條事務(wù)記錄，每條事務(wù)記錄由6部分組成，分別是各年代土地覆蓋現(xiàn)狀對應(yīng)柵格的值，每個值都帶有時間約束條件，形如{TID、土地利用類型1(時間1)、土地利用類型2(時間2)、土地利用類型3(時間3)、…、土地利用類型6(時間6)}，最后采用C#面向?qū)ο笳Z言與ArcEngine組件快速讀取柵格數(shù)據(jù)屬性值、構(gòu)造屬性事務(wù)表以及實現(xiàn)Apriori算法和本文所提出算法。

2.2算法比較

針對已構(gòu)建的總事務(wù)記錄數(shù)為167 155的屬性值事務(wù)表，設(shè)置最小事務(wù)支持數(shù)分別為100、200、400、800、1 600、3 200、6 400、12 800、25 600，同時假設(shè)最小支持度為0.03，最小置信度為0.2?；谝陨显O(shè)置的參數(shù)，將已程序化的該算法和Apriori算法在CPU為Pentium(R)Dual-Core2.60 GHz、內(nèi)存為2 GB、操作系統(tǒng)為Microsoft Windows7的PC機上運行并提取空間關(guān)聯(lián)規(guī)則，最后比較2種算法的提取效率，結(jié)果如圖1所示。從圖1中的比較結(jié)果，可以很明顯地發(fā)現(xiàn)：本文所提出的算法在關(guān)聯(lián)規(guī)則提取效率上要優(yōu)于原始的Apriori算法，而且更為穩(wěn)定。

圖1　2種算法的效率比較

3結(jié)語

本研究基于Apriori的算法原理，借鑒基于布爾矩陣的空間關(guān)聯(lián)規(guī)則提取方法，并綜合考慮空間數(shù)據(jù)的特征，提出了一種新的時空關(guān)聯(lián)規(guī)則挖掘算法——基于0-1矩陣的時空關(guān)聯(lián)規(guī)則提取算法，該算法同時考慮時間與空間2個因素，解決了Apriori算法的缺陷，減少了掃描數(shù)據(jù)庫的次數(shù)，在提取過程中，只需要掃描一次數(shù)據(jù)庫，并優(yōu)先通過產(chǎn)生最大頻繁項集的候選項來得到最大頻繁項集，大大減少了候選項集產(chǎn)生的數(shù)量，極大地提高了時空關(guān)聯(lián)規(guī)則的提取效率。但是該算法仍然有許多方面需要斟酌：1)在0-1矩陣，可能存在連續(xù)的多個‘0’值，會造成內(nèi)存資源浪費。2)缺乏對頻繁模式集的質(zhì)量評價，Jiawei Han指出如何得到壓縮的、高質(zhì)量的頻繁模式以及對頻繁模式的解釋是未來急需解決的問題[16]。3)沒有考慮空間數(shù)據(jù)的自相關(guān)性，陳江平等發(fā)現(xiàn)數(shù)據(jù)的空間自相關(guān)性對關(guān)聯(lián)規(guī)則的挖掘存在作用和影響[17]。以上3點，也將是下一步研究工作的重點。

參考文獻

[1] Han Jiawei，Kamber M.數(shù)據(jù)挖掘概念與技術(shù)[M].范明，孟小峰，譯.北京：機械工業(yè)出版社，2007：5-6.

[2] 張俊.時空關(guān)聯(lián)性分析方法研究與應(yīng)用[D].重慶：重慶大學(xué)，2011：7.

[3] 李德仁，王樹良，李德毅.空間數(shù)據(jù)挖掘理論與應(yīng)用[M].北京：科學(xué)出版社，2006：3-4.

[4] Koperski K.Han J.Discovery of spatial association rules in geographic information databases [J].Lecture Notes In Computer Science，1995，951：47-66.

[5] 陳剛，何政偉，楊斌.地形特征與山地氣候變化空間關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘研究[J].地理與地理信息科學(xué)，2010，26(1)：37-40.

[6] 李波，濮培民，韓愛民.洪澤湖水質(zhì)的時空相關(guān)性分析[J].湖泊科學(xué)，2001，14(3)：259-266.

[7] 沙宗堯.時序空間關(guān)聯(lián)規(guī)則挖掘及其應(yīng)用研究[J].地理空間信息，2008，6(5)：18-21.

[8] 岳慧穎.含有時空約束的關(guān)聯(lián)規(guī)則挖掘方法研究[D].哈爾濱：哈爾濱工程大學(xué)，2004：52-54.

[9] Florian Verhein，Sanjay Chawla.Mining Spatio-Temporal patterns in object mobility database[J].Data Mining and Knowledge Discovery，2008，16(1)：5-38.

[10] Marcin Gorawski，Pawel Jureczek.Using Apriori-like Algorithms for Spatio-Temporal Pattern Queries[C]//Proceedings of the International Multiconference on Computer Science and Information Technology，IEEE，2009：43-48.

[11] 夏英，張俊，王國胤.時空關(guān)聯(lián)規(guī)則挖掘算法及其在ITS中的應(yīng)用[J].計算機科學(xué)，2011，38(9)：173-176.

[12] Agrawal R，Imelinski，Swani A.Mining association rules between sets of items in large database[J].International Journal of Science and Modern Engineering，2013，1(5)：2319-6386.

[13] HAN Jia-wei，PEI Jian，YIN Yi-wen，et al.Mining Frequent Patterns without Candidate Generation：A Frequent-Pattern Tree Approach[J].Data Mining and Knowledge Discovery，2004，8(1)：53-87.

[14] 陳俊明.基于布爾矩陣的空間關(guān)聯(lián)規(guī)則提取方法研究[J].測繪與地理空間信息，2014，37(5)：123-126.

[15] Imam Mukhlash，Benhard Sitohang.Spatial Data Preprocessing for Mining Spatial Association Rule with Conventional Association Mining Algorithms[C]//Proceedings of the International Conference on Electrical Engineering and Informatics.Institute Teknologi Bandung，Indonesia June，2007：17-19.

[16] Han Jia-wei，Cheng Hong，Xin Dong，et al.Frequent pattern mining：current status and future directions[J].Data Mining and Knowledge Discovery，2007，15：55-86.

[17] 陳江平，黃炳堅.數(shù)據(jù)空間自相關(guān)性對關(guān)聯(lián)規(guī)則的挖掘與實驗分析[J].地球信息科學(xué)學(xué)報，2011，13(1)：109-117.

doi:10.3969/j.issn.1009-8984.2015.02.030

收稿日期：2015-04-09

作者簡介：鄭瑾(1983-)，女(漢)，福州，講師，碩士

中圖分類號：TP391

文獻標志碼：A

文章編號：1009-8984(2015)02-0114-04

The study on method of extracting spatial-temporal association rules based on 0-1 matrix

ZHENG Jin

(DepartmentofInformationEngineering，

FujianChuanzhengCommunicationsCollege，F(xiàn)uzhou350007，China)

Abstract：In this article，an algorithm of extracting spatial-temporal association rules based on Apriori algorithm has been put forward.A case has been studied on extracting the association rules between land covers in different periods and the extracting results and extracting efficiencies has been compared with Apriori algorithm.The study results show that：the new algorithm improves the efficiency of extracting spatial-temporal association rules by reducing the times of scanning the data，and reducing the generation of redundant candidate sets.

Key words：0-1 matrix；spatial-temporal association rule；Apriori algorithm