周慶芳

摘 要：空間Co-location模式挖掘是空間數(shù)據(jù)挖掘的一個重要領(lǐng)域，其目標(biāo)是發(fā)現(xiàn)空間中在一起頻繁出現(xiàn)的空間特征。Joinless算法沿用了Joinbase的度量標(biāo)準(zhǔn)，定義了星型鄰近關(guān)系，并利用它的性質(zhì)，將Joinbase算法中的連接操作替換成了更快速的查找操作。本文基于Java HashMap實(shí)現(xiàn)了上述兩種算法，并通過實(shí)驗(yàn)考察了參數(shù)設(shè)置對挖掘算法效率的影響、Joinbase算法和Joinless算法的剪枝策略的效率，同時，從時間、空間兩方面比較了這兩種算法的異同，以期為學(xué)生學(xué)習(xí)、老師教學(xué)以及實(shí)際應(yīng)用研究提供參考。

關(guān)鍵詞：空間數(shù)據(jù)挖掘；Co-location模式；Joinbase算法；Joinless算法

中圖分類號：TP3-0 文獻(xiàn)標(biāo)識碼：B 收稿日期：2015-12-09

一、引言

現(xiàn)實(shí)世界中的物體都占據(jù)一定的物理空間，并且與周圍的其他物體存在諸多聯(lián)系。本文首先介紹了Joinbase算法和Joinless算法，并詳細(xì)闡述了其中的剪枝策略以及一些可能的優(yōu)化方法；其次，分析了使用Java編程語言實(shí)現(xiàn)的兩種算法，并進(jìn)行了相關(guān)實(shí)驗(yàn)，考察了參數(shù)設(shè)置對算法的影響，探究了剪枝策略的效率以及比較兩種算法。

二、空間Co-location模式挖掘

空間特征（spatial feature）是一系列特征的集合，它們用來表示空間中事物的不同屬性，記為F= {f1，f2，…，fn}。它們的實(shí)例（instance）就是指空間中體現(xiàn)這些特征（可以是一種或多種）的具體事物，記為I={i1，i2，…，in}，其中每個實(shí)例in∈I都可以表示為“實(shí)例ID、所屬特征、空間位置”。以植被數(shù)據(jù)為例，某種植被可以看作是空間特征，而這種植被的某一個個體則稱之為實(shí)例。

Co-location規(guī)則的條件概率表示由模式c1推出模式c2的可信度，計算方法為：

三、算法實(shí)現(xiàn)

Java HashMap是Java中最常用的容器類之一，它是基于哈希表的Map接口的非同步實(shí)現(xiàn)，能夠快速地存取鍵值對。在很多情況下，哈希表的效率都要優(yōu)于搜索樹和其他查找結(jié)構(gòu)，因此哈希表在很多領(lǐng)域尤其是在關(guān)聯(lián)數(shù)組、數(shù)據(jù)庫索引、緩存等方面得到了廣泛應(yīng)用。

HashMap中的Map.Entry包含了鍵、值、哈希碼以及一個指向下個Map.Entry的引用，值得注意的是Java容器中都是存放對象的引用，所以，HashMap中鍵值也都是引用。因?yàn)榭臻g效率與具體的實(shí)現(xiàn)有關(guān)，而目前JVM有很多不同的實(shí)現(xiàn)方法，數(shù)組的長度等于容量除以負(fù)載因子，為了保持一致，本文討論空間效率時，是假設(shè)在64位機(jī)器上，并且每個引用占用8個字節(jié)的條件下進(jìn)行。

筆者通過實(shí)驗(yàn)比較Joinbase和Joinless算法，并探究兩種算法中的一些剪枝策略的效率以及參數(shù)設(shè)置對挖掘算法的影響。首先計算hashCode時需要對所有的關(guān)鍵域使用乘法進(jìn)行操作——即使編譯器優(yōu)化為位移操作，這樣，使用現(xiàn)有的HashMap還不如“直接比較”高效。

四、小結(jié)

本文使用Java HashMap實(shí)現(xiàn)了Joinless算法和Joinbase算法，并使用數(shù)據(jù)測試了算法的效率以及參數(shù)對算法的影響。通過比較Joinbase算法和Joinless算法，我們發(fā)現(xiàn)Joinless算法的效率與實(shí)現(xiàn)方式有很大的關(guān)系，雖然理論上說Joinless的查找操作要比Joinbase的連接操作高效，但是由于Java HashMap本身的機(jī)制影響，導(dǎo)致Joinless實(shí)際的運(yùn)行效率反而不如Joinbase。

參考文獻(xiàn)：

[1]王麗珍，周麗華，陳紅梅.數(shù)據(jù)倉庫與數(shù)據(jù)挖掘原理及應(yīng)用（第二版）[M].北京：科學(xué)出版社，2009.

[2]Huang Yan，Shashi Shekhar and Hui Xiong.Discovering Colocation patterns from Spatial Data Sets： A Heneral Approach[J].IEEE Transactions on Knowledge and Data Engineering，2004，16（12）.

[3]Yoo，Jin Soung，and Shashi Shekhar.A joinless approach for mining spatial colocation patterns[J].IEEE Transactions on Knowledge and Data Engineering，2006，18（10）.

[4]馮 嶺，王麗珍，高世健.一種帶稀有特征的空間co-location模式挖掘新方法[J].南京大學(xué)學(xué)報（自然科學(xué)版），2012，48（1）：99-107.

[5]熊國華，周 俊，童小華，等.空間數(shù)據(jù)線要素綜合的經(jīng)典算法及其實(shí)現(xiàn)[J].水利科技與經(jīng)濟(jì)，2006，12（6）.

[6]王 新，肖 濤，蘆俊麗，等.空間Co-Location模式增量挖掘及演化分析[J].軟件學(xué)報，2014，（S2）.