面向城市服務(wù)設(shè)施數(shù)據(jù)的同位模式挖掘研究

姚曉婧

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

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

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

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

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

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

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

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

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