姚曉婧

中國科學院遙感與數(shù)字地球研究所，北京 100101

城市空間是人類活動的主要區(qū)域，隨著數(shù)據(jù)采集和共享技術的快速發(fā)展，大量與城市相關的數(shù)據(jù)可被獲取。公共服務設施數(shù)據(jù)作為城市各類數(shù)據(jù)的地理基礎，其中蘊含著豐富的人類群體智慧。在智慧城市建設的發(fā)展契機下，利用數(shù)據(jù)挖掘手段，從較為成熟的城市設施數(shù)據(jù)中提取有趣的規(guī)律和知識，以指導新城市的合理規(guī)劃和后續(xù)設施的合理布局，成為目前一個重要的應用和研究熱點。

同位模式挖掘是解決上述命題的有效方法，它隸屬于空間數(shù)據(jù)挖掘的一個分支，用來尋找具有空間依賴性的特征類型組合，即所謂的流行同位模式。流行模式表現(xiàn)于它們所代表的實例頻繁地出現(xiàn)在同一地點。目前，關于該領域的研究多數(shù)弱化了地理空間的特異性，體現(xiàn)在對距離衰減作用和地理異質特性考慮的不足，導致這些方法應用于城市服務設施數(shù)據(jù)上存在自適應性差和精確度不夠的現(xiàn)象，此外，效率較低和內存需求較高也一直是制約該研究領域的重要瓶頸之一。

本文在現(xiàn)有同位模式挖掘研究的基礎上，提出了3個新的算法，分別為：①考慮距離衰減效應的同位模式挖掘方法；②基于泰森多邊形和距離回饋函數(shù)的自適應同位模式挖掘方法；③高效且節(jié)省空間的極大同位模式挖掘方法。這3個算法從實例關系的處理、模式流行度的計算、候選模式的獲取和空間團實例的計算上，層次遞進地解決了上述提到的問題。此外，基于每個算法的改進重點，筆者利用北京城市公共服務設施數(shù)據(jù)進行了大量的試驗，驗證了算法的有效性。本文的研究工作和創(chuàng)新點包括以下幾個方面：

(1) 首次在實例關系的處理和模式流行程度的鑒定中，將實例之間的距離值作為變量考慮進去，由于挖掘過程中顧及了距離衰減效應的影響，因此有效提升了挖掘結果的精確度。

(2) 提出一種基于泰森多邊形的實例連接方法，打破了常規(guī)只考慮鄰近實例連接的局限性，不僅有效避免了由于距離閾值設置不合理產(chǎn)生的冗余連接計算量和存儲需求，而且由于同時保留了較遠和較近距離的實例連接關系和距離值，使得模式流行程度的判定過程中充分融入距離衰減效應的考慮成為可能。

(3) 發(fā)現(xiàn)基于泰森多邊形的連接實例的距離集合符合廣義極大值的分布規(guī)律，基于這一特征，本文提出利用統(tǒng)計學的方法估計表征區(qū)域密度的距離截斷參數(shù)，省去了用戶預先設定距離閾值的過程，有效提高了同位模式挖掘在未知區(qū)域上執(zhí)行的自適應性。

(4) 將流行的二階同位模式抽象為一個稀疏的無向完全圖，引入一種快速的候選極大同位模式挖掘方法。該方法具體將“退化度次序”和“關鍵點的選擇”融入到經(jīng)典的極大團發(fā)現(xiàn)算法中，有效提升了候選極大同位模式的計算效率。

(5) 采用了一種層次性的驗證方法，構建了一個壓縮樹結構，用來存儲較長候選同位模式的團實例關系。該方法摒棄了現(xiàn)有算法在剪枝程序之前需要為鄰近實例對構建冗余初始結構的過程，并且只需要通過較少而且容易的樹節(jié)點操作即可獲取所有的團實例，有效削減了挖掘過程的內存和時間需求。