李偉　陳忠紅

摘要：移動(dòng)通信、互聯(lián)網(wǎng)及空間定位技術(shù)的成熟極大地促進(jìn)了LBS（Location Based Services）的發(fā)展，也產(chǎn)生了越來(lái)越多的位置大數(shù)據(jù)。合理地使用時(shí)空數(shù)據(jù)挖掘技術(shù)可有效進(jìn)行知識(shí)發(fā)現(xiàn)及價(jià)值提取，在追蹤目標(biāo)用戶，維護(hù)公共安全等方面具有重要意義。本文以移動(dòng)終端位置信息為研究對(duì)象，從推斷目標(biāo)用戶敏感信息的角度出發(fā)，研究了基于時(shí)空數(shù)據(jù)挖掘的空間位置聚類方法，并總結(jié)了當(dāng)前各類技術(shù)的不足，并指出了今后發(fā)展方向。

關(guān)鍵詞：移動(dòng)終端；位置信息；聚類技術(shù)；公共安全

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2015）29-0034-02

1 概述

隨著移動(dòng)互聯(lián)網(wǎng)的普及，網(wǎng)絡(luò)虛擬世界中人們通過(guò)網(wǎng)絡(luò)ID以匿名方式進(jìn)行社交活動(dòng)，使得對(duì)違法活動(dòng)的溯源追蹤更加困難。而位置信息是連接現(xiàn)實(shí)世界和虛擬世界的橋梁，通過(guò)收集手機(jī)入網(wǎng)所在基站號(hào)，采集手機(jī)APP提交地理坐標(biāo)，網(wǎng)絡(luò)爬蟲采集LBSN上用戶簽到的語(yǔ)義化地點(diǎn)，甚至直接通過(guò)服務(wù)提供商獲取等途徑都可以獲取手機(jī)位置信息的大數(shù)據(jù)。近年來(lái)，隨著大數(shù)據(jù)時(shí)代的興起，通過(guò)機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘的手段可以從海量位置數(shù)據(jù)中獲取有價(jià)值的信息。在維護(hù)公共安全方面，這種方法可以實(shí)現(xiàn)對(duì)目標(biāo)人的追蹤。

這種跟蹤手段可以有很多應(yīng)用，如網(wǎng)警可以通過(guò)分析移動(dòng)終端社交APP（微信、微博、QQ、人人、陌陌）上傳的歷史位置信息，可有效追捕在此類社交網(wǎng)站散步不良信息者或網(wǎng)絡(luò)詐騙者。同樣，警察可以通過(guò)分析手機(jī)基站定位信息，推斷犯罪嫌疑人住址，為實(shí)施抓捕提供有效情報(bào)。

2014年11月20日，在首屆世界互聯(lián)網(wǎng)大會(huì)分論壇“網(wǎng)絡(luò)空間安全和國(guó)際合作”上，以色列網(wǎng)絡(luò)安全專家Shai Schiller發(fā)表題為《從大數(shù)據(jù)當(dāng)中發(fā)現(xiàn)情報(bào)》的演講。他使用Deep Analytics系統(tǒng)檢索在Facebook、Twitter等社交平臺(tái)上與“占中”相關(guān)的活躍用戶及其消息記錄。Deep Analytics系統(tǒng)可以獲取這些用戶的資料、相互關(guān)系、地理位置等，并通過(guò)數(shù)據(jù)挖掘技術(shù)進(jìn)行分析和過(guò)濾，查出活動(dòng)的“重要成員的主要信息、參加活動(dòng)的地方和參加活動(dòng)的具體情況”等，并根據(jù)歷史位置信息，對(duì)某個(gè)區(qū)域“建立一個(gè)圍墻”，監(jiān)管區(qū)域內(nèi)所有人的Twitter數(shù)據(jù)。這一應(yīng)用充分說(shuō)明了利用手機(jī)位置大數(shù)據(jù)信息在追蹤目標(biāo)人，維護(hù)公共安全中的重要意義。

2 時(shí)空數(shù)據(jù)挖掘?qū)崿F(xiàn)位置信息聚類

20世紀(jì)90年代中后期，數(shù)據(jù)挖掘領(lǐng)域的一些較成熟的技術(shù)，如關(guān)聯(lián)規(guī)則挖掘、分類、預(yù)測(cè)與聚類等被逐漸用于時(shí)間序列數(shù)據(jù)挖掘和空間數(shù)據(jù)挖掘，以發(fā)現(xiàn)與時(shí)間或空間相關(guān)的有價(jià)值的模式。時(shí)空數(shù)據(jù)挖掘是綜合利用各種數(shù)據(jù)挖掘技術(shù)從具有海量、高維、高噪聲和非線性等特性的時(shí)空數(shù)據(jù)中提取出隱含的、人們事先不知道的、但又潛在有用的信息及知識(shí)的過(guò)程。對(duì)于移動(dòng)終端位置大數(shù)據(jù)的分析，在獲得時(shí)間、空間、用戶ID三種屬性的條件下，借助時(shí)空挖掘技術(shù)對(duì)位置信息進(jìn)行聚類分析，可實(shí)現(xiàn)對(duì)用戶敏感信息，如用戶居住地位置、用戶之間是否存在社會(huì)關(guān)系、用戶即將到達(dá)的位置等的推斷。

但在現(xiàn)實(shí)中，由于人們使用移動(dòng)設(shè)備的習(xí)慣不同，很難獲得等間隔、規(guī)律性的定位信息。更重要的是，由于隱私法規(guī)等約束，這種位置信息也并非實(shí)時(shí)的，而是歷史位置信息。這一類數(shù)據(jù)在位置信息中占較大比重，使得追蹤目標(biāo)人變得更加困難。

然而，研究人員證明，大多數(shù)人平時(shí)往返于固定的地點(diǎn)，而且活動(dòng)帶有很強(qiáng)的規(guī)律性。這就意味著通過(guò)對(duì)歷史位置數(shù)據(jù)進(jìn)行有效挖掘，可以推斷得知目標(biāo)住所、工作地點(diǎn)等重要信息。正所謂“跑得了和尚跑不了廟”，通過(guò)這種手段，結(jié)合目標(biāo)作息規(guī)律，可以預(yù)知目標(biāo)所在位置。

在處理位置信息時(shí)，由于用戶所在建筑物形狀不同、定位誤差、采集數(shù)據(jù)的誤差、人為干擾等因素，首先需要拋開時(shí)間尺度，對(duì)位置進(jìn)行聚類。所謂聚類（分析）即根據(jù)數(shù)據(jù)中發(fā)現(xiàn)的描述對(duì)象及其關(guān)系的信息，將數(shù)據(jù)對(duì)象分組[24]。算法的種類主要分為基于劃分的聚類、基于層次的聚類、基于密度的聚類、基于網(wǎng)格的聚類、基于模型的聚類等5大方法。

1）基于劃分的聚類方法

其基本思想是簡(jiǎn)單地將數(shù)據(jù)對(duì)象集劃分為不重疊的子集，從而使每個(gè)數(shù)據(jù)對(duì)象恰在一個(gè)子集中。假設(shè)給定一個(gè)包含n個(gè)對(duì)象或數(shù)據(jù)的集合，將數(shù)據(jù)集劃分為k個(gè)子集，其中每個(gè)子集均代表一個(gè)聚類（k

2）基于層次的聚類方法

其基本思想是通過(guò)將數(shù)據(jù)組織為若干組并形成一個(gè)相應(yīng)的樹來(lái)進(jìn)行聚類的，可分為自頂向下的分裂算法和自底向上的凝聚算法兩種。分裂聚類算法，首先將所有對(duì)象置于一個(gè)簇中，然后逐漸細(xì)分為越來(lái)越小的簇，直到每個(gè)對(duì)象自成一簇，或達(dá)到了某個(gè)終止條件。而凝聚聚類算法則相反，首先將每個(gè)對(duì)象作為一個(gè)簇，然后將相互鄰近的簇合并為一個(gè)大簇，直到所有的對(duì)象都在一個(gè)簇中，或達(dá)到了某個(gè)終止條件。其代表算法有CURE、ROCK、BIRCH等。

3）基于密度的聚類方法

其基本思想是利用數(shù)據(jù)集本身的結(jié)構(gòu)特征，判斷某一區(qū)域內(nèi)數(shù)據(jù)集的密度來(lái)判斷是否歸類的方法。密度聚類算法的優(yōu)點(diǎn)是，它能夠應(yīng)用于任何形狀的數(shù)據(jù)集處理中，而且它不用預(yù)先設(shè)定類的數(shù)量?；诿芏鹊姆椒捎脕?lái)過(guò)濾“噪音”孤立點(diǎn)數(shù)據(jù)，以發(fā)現(xiàn)任意形狀的簇"其主要思想是只要臨近區(qū)域的密度（樣本數(shù)目）超過(guò)某個(gè)閥值則繼續(xù)聚類。即對(duì)于給定簇中的每個(gè)樣本，在一個(gè)給定范圍的區(qū)域中必須至少包含某個(gè)數(shù)目的樣本。

4）基于網(wǎng)格的聚類方法

基于網(wǎng)格的空間聚類方法采用了一個(gè)多分辨率的網(wǎng)格數(shù)據(jù)結(jié)構(gòu).該類算法首先將數(shù)據(jù)空間劃分為有限個(gè)單元的網(wǎng)格結(jié)構(gòu)，所有的處理都以單個(gè)的單元為對(duì)象.這樣處理的一個(gè)突出的優(yōu)點(diǎn)就是處理速度快，通常與目標(biāo)數(shù)據(jù)庫(kù)中記錄的個(gè)數(shù)無(wú)關(guān)，只與把數(shù)據(jù)空間分成多少個(gè)單元有關(guān)。代表算法有STING、Wavecluster和CLIQUE算法。

5）基于模型的聚類方法

基于模型的取類方法為每個(gè)簇假定一個(gè)模型，并在數(shù)據(jù)中尋找對(duì)給定模型的最佳擬合。目前主要研究的是利用概率統(tǒng)計(jì)模型進(jìn)行概念取類和利用神經(jīng)網(wǎng)絡(luò)技術(shù)進(jìn)行自組織聚類等方面。它們面對(duì)的主要問(wèn)題仍然是如何適用于大數(shù)據(jù)源的聚類應(yīng)用?；谀Ｐ偷目臻g聚類方法包括基于統(tǒng)計(jì)的空間聚類方法和基于神經(jīng)網(wǎng)絡(luò)的空間聚類方法等。如EM、COBWEB、SOM算法等。是給每一個(gè)聚類假定一個(gè)模型，然后去尋找能夠很好地滿足這個(gè)模型的數(shù)據(jù)集。

1996年，Martin Ester等人提出了一種DBSCAN算法[1]，該算法采用空間索引技術(shù)來(lái)搜索對(duì)象的鄰域，引入了“核心點(diǎn)”、“邊界點(diǎn)”、“噪聲點(diǎn)”和“密度可達(dá)”等概念，如圖 2所示，從核心點(diǎn)出發(fā)，以超球狀區(qū)域內(nèi)數(shù)據(jù)對(duì)象的數(shù)量來(lái)衡量此區(qū)域密度的高低，把所有密度可達(dá)的對(duì)象組成一個(gè)簇。該算法可以發(fā)現(xiàn)任意形狀的簇，能夠有效排除噪聲點(diǎn)和離群點(diǎn)。

然而，DBSCAN算法存在許多不足，如對(duì)輸入?yún)?shù)敏感，致使參數(shù)選擇困難等。針對(duì)這一問(wèn)題，F(xiàn)eng Pingjiang提出了一種自適應(yīng)DBSCAN算法[3]，該算法在選取固定minPts的條件下，采用不同的Eps參數(shù)進(jìn)行聚類，最后對(duì)每次聚類的有效性進(jìn)行對(duì)比，并從中取最優(yōu)。這種方法通過(guò)“試”的方法，在一定程度上解決了參數(shù)選取問(wèn)題，但也帶來(lái)了可觀的時(shí)間代價(jià)。夏魯寧等人[4]提出了一種SA-DBSCAN算法，該算法通過(guò)分析數(shù)據(jù)集統(tǒng)計(jì)特性以確定Eps和MinPts參數(shù)，避免了聚類分析過(guò)程中的人工干預(yù)，防止了人為選擇參數(shù)不當(dāng)帶來(lái)的誤差，實(shí)現(xiàn)了聚類分析的自動(dòng)化。

2014年，Alex Rodriguez等人在《Science》上提出了一種新型、簡(jiǎn)潔、高效的聚類算法[2]。該算法的假設(shè)是類簇的中心由一些局部密度比較低的點(diǎn)圍繞，并且這些點(diǎn)距離其他有高局部密度的點(diǎn)的距離都比較大。通過(guò)計(jì)算最近鄰距離，得到聚類中心，并依據(jù)密度大小排序，將剩余點(diǎn)劃分至所屬類別。該算法只需計(jì)算一次距離，且不需要參數(shù)，不需迭代，可針對(duì)各種類型的點(diǎn)集進(jìn)行聚類。

空間位置數(shù)據(jù)具有高維度、非線性、稀疏性等特征，因此在選用聚類算法上應(yīng)綜合考慮數(shù)據(jù)特性?；趧澐值木垲惙椒ㄐ枰o出簇的個(gè)數(shù)，而采集的位置數(shù)據(jù)沒(méi)有這一先驗(yàn)信息。而人類活動(dòng)一般具有較強(qiáng)的規(guī)律性，因此，所到重點(diǎn)區(qū)域通常較為頻繁，拋開時(shí)間維度，從空間看，這就造成了重點(diǎn)區(qū)域密度不同?；诿芏鹊木垲惙椒ㄒ詳?shù)據(jù)集在空間分布上的稠密程度為依據(jù)進(jìn)行聚類，無(wú)需預(yù)先設(shè)定簇的數(shù)量，因此特別適合于對(duì)未知內(nèi)容的數(shù)據(jù)集進(jìn)行聚類[5]。

3 總結(jié)

本文研究了空間位置聚類、對(duì)時(shí)空挖掘技術(shù)在移動(dòng)終端位置信息推斷在公共安全領(lǐng)域的應(yīng)用。以下將對(duì)目前聚類方法中存在的問(wèn)題以及在這些問(wèn)題上所做的改進(jìn)做一個(gè)總結(jié)：

1）從以上對(duì)傳統(tǒng)的聚類分析方法所做的總結(jié)來(lái)看，不管是k-means方法，還是CURE方法，在進(jìn)行聚類之前都需要用戶事先確定要得到的聚類的數(shù)目。然而在現(xiàn)實(shí)數(shù)據(jù)中，聚類的數(shù)目是未知的，通常要經(jīng)過(guò)不斷的實(shí)驗(yàn)來(lái)獲得合適的聚類數(shù)目，得到較好的聚類結(jié)果。

2）隨著信息時(shí)代的到來(lái)，對(duì)大量的數(shù)據(jù)進(jìn)行分析處理是很龐大的工作，這就關(guān)系到計(jì)算效率的問(wèn)題。有文獻(xiàn)提出了一種基于最小生成樹的聚類算法，該算法通過(guò)逐漸丟棄最長(zhǎng)的邊來(lái)實(shí)現(xiàn)聚類結(jié)果，當(dāng)某條邊的長(zhǎng)度超過(guò)了某個(gè)閾值，那么更長(zhǎng)邊就不需要計(jì)算而直接丟棄，這樣就極大地提高了計(jì)算效率，降低了計(jì)算成本。

3）目前的許多算法都只是理論上的，經(jīng)常處于某種假設(shè)之下，比如聚類能很好地被分離，沒(méi)有突出的孤立點(diǎn)等，但是現(xiàn)實(shí)數(shù)據(jù)通常是很復(fù)雜的，噪聲很大，因此如何有效的消除噪聲的影響，提高處理現(xiàn)實(shí)數(shù)據(jù)的能力還有待進(jìn)一步的提高。

參考文獻(xiàn)：

[1] Ester M， Kriegel H， Sander J， et al. A density-based algorithm for discovering clusters in large spatial databases with noise.[C]. In： Kdd.1996. 226-231.

[2] Rodriguez A， Laio A. Clustering by fast search and find of density peaks[J]. SCIENCE. 2014， 344（6191）： 1492-1496.

[3] Pingjiang F， Lindong G. Adaptive DBSCAN-based algorithm for constellation reconstruction and modulation identification[C]. In： Radio Science Conference， 2004. Proceedings. 2004 Asia-Pacific.IEEE， 2004. 177-180.

[4] 豐江帆，熊雨虹. 一種基于個(gè)人位置信息的重要地點(diǎn)識(shí)別方法[J]. 小型微型計(jì)算機(jī)系統(tǒng)，2013（3）： 503-507.

[5] Kumar N， Sivasathya S. Density-Based Spatial Clustering with Noise–A Survey[J]. 2014.

[6] Vesanto J， Alhoniemi E. Clustering of the self-organizing map[J]. Neural Networks， IEEE Transactions on. 2000， 11（3）： 586-600.