空間Co—location模式挖掘經典算法的實現與比較

周慶芳

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

關鍵詞：空間數據挖掘；Co-location模式；Joinbase算法；Joinless算法

中圖分類號：TP3-0 文獻標識碼：B 收稿日期：2015-12-09

一、引言

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

二、空間Co-location模式挖掘

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

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

三、算法實現

Java HashMap是Java中最常用的容器類之一，它是基于哈希表的Map接口的非同步實現，能夠快速地存取鍵值對。在很多情況下，哈希表的效率都要優于搜索樹和其他查找結構，因此哈希表在很多領域尤其是在關聯數組、數據庫索引、緩存等方面得到了廣泛應用。

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

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

四、小結

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

參考文獻：

[1]王麗珍，周麗華，陳紅梅.數據倉庫與數據挖掘原理及應用（第二版）[M].北京：科學出版社，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].南京大學學報（自然科學版），2012，48（1）：99-107.

[5]熊國華，周 俊，童小華，等.空間數據線要素綜合的經典算法及其實現[J].水利科技與經濟，2006，12（6）.

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