互動式地理資訊系統：設計與實作地理資訊分群及視覺化演算法

Abstract

隨著可偵測地理位置的行動裝置及地圖系統的日漸增加，網路上可取得的地理資料量也逐漸成長。於此同時，使用者對於搜尋並瀏覽這些地理資料的需求也日益提升。因此，網路上也出現了越來越多的地理相關服務。舉例來說，Flickr就允許使用者透過它們自家所推出的網路地圖（Yahoo地圖）來瀏覽照片；Google也提供了一項地圖搜尋服務，讓使用者可以透過文字來搜尋地理資訊，並且透過Google地圖以打點的方式來做呈現。然而，在地圖上打點有時候會造成地圖太過於零亂的現象。因此在本篇論文中，我們設計了一個系統，此系統可以藉由分群的方式，自動把大量的地理資訊作統整的動作。並且透過類似熱力圖的方式來呈現，讓使用者可以瀏覽並明瞭整個地理資訊的分佈狀況。我們提出了一個名為Geo-tree的資料結構，其概念是從四分數的資料結構延伸而來。我們同時也設計了兩個演算法，其一為使用Geo-tree來做地理資訊分群的演算法，其二為使用Geo-tree來產生地理資訊分佈熱力圖的演算法。最後我們從三個大方向來評估整個系統的效能，包括效率、準確性及有效性。實驗的結果顯示了我們的分群演算法在處理大量的地理資訊時，速度比兩個著名的演算法：K中心點演算法以及階層式分群演算法快很多，這對互動式地理資訊系統非常重要，而且分群的準確性也與這兩個方法相當。除此之外，使用者藉由我們的系統也能夠獲得足夠的地理資訊，並且相當滿意我們系統的地理資訊視覺化效果。

With the appearance of location-aware devices and web mapping systems today, the amount of geographic data available on the Web becomes larger. The requirements of searching and browsing geographic data also arise. Accordingly, more and more related services are available on the Web. For example, Flickr allows users to browse photos through its web mapping system; Google provides Map Search service, which displays markers on the map based on users’ text queries. However, plotting lots of geographic data points usually clutters up a map. In this paper, we propose an approach to provide a summary view of geographic data by efficiently clustering. We present a novel data structure, called Geo-tree, which is extended from quadtree, and then develop two algorithms, which use Geo-tree to cluster geographic data and visualize the clusters with a heatmap-like representation. We evaluate the performance of our approach in three different aspects: efficiency, accuracy and effectiveness. The experimental results show that our clustering approach is very efficient in a large scale, compared to K-means and HAC, and our accuracy is comparable to theirs. Furthermore, users can acquire sufficient geographic information and are highly satisfied with our visual results.