大數(shù)據(jù)(數(shù)據(jù)挖掘)以及位置地理信息

1、東北大學秦皇島分校Northeastern University at Qinhuangdao位置大數(shù)據(jù)的價值提取與協(xié)同挖掘方法軟件工程課程設(shè)計軟件工程課程設(shè)計目 錄選題背景設(shè)計理論總體模型參考文獻選題背景一 選題背景一LBS 位置服務(wù)(location based service,簡稱 LBS)是近年來新興的移動計算服務(wù).位置服務(wù)主要需重視其兩個方面的能力:提供位置的能力提供位置的能力和理解位置的能力和理解位置的能力. 理解位置的能力：目前尚有很多挑戰(zhàn),理解位置其實就是理解位置背后所反映出來的人的活動、人的情感和人的環(huán)境,因此也被稱為泛在測繪(ubiquitous mapping)或位置社會

2、感知(location-based social awareness)2.研究目的-位置服務(wù) 選題背景一LBD 位置大數(shù)據(jù)(location big data)是構(gòu)成泛在測繪和位置社會感知的重要資源,具有相當大的體量.近幾年,位置服務(wù)、數(shù)據(jù)挖掘和機器學習領(lǐng)域,已經(jīng)涌現(xiàn)出一批針對位置大數(shù)據(jù)的優(yōu)秀研究.其所使用的數(shù)據(jù)集在體量和復(fù)雜性上均已達到了“大”數(shù)據(jù)的層次。研究目的-位置大數(shù)據(jù) 選題背景一LBD特點 研究目的-復(fù)雜但稀疏 位置大數(shù)據(jù)主要來源于車聯(lián)網(wǎng)車聯(lián)網(wǎng)(Internet of vehicles,簡稱簡稱 IOV)、移動社交網(wǎng)絡(luò)等新興互聯(lián)網(wǎng)應(yīng)用,更新速度快且具有很大的混雜性(inaccurat

3、e).同時,往往受到數(shù)據(jù)采集技術(shù)數(shù)據(jù)采集技術(shù)等方面的客觀制約,使得這些數(shù)據(jù)不能全面和正確地反映觀察對象的整體全貌,因而具有“復(fù)雜但稀疏復(fù)雜但稀疏(complex yet sparse)”的特點.如何從如何從位置大數(shù)據(jù)中獲得價值位置大數(shù)據(jù)中獲得價值,進而發(fā)現(xiàn)人類社群活動規(guī)律進而發(fā)現(xiàn)人類社群活動規(guī)律,是非常值得探討的問題. 選題背景一數(shù)據(jù)挖掘 研究目的-關(guān)聯(lián)應(yīng)用 從關(guān)聯(lián)應(yīng)用關(guān)聯(lián)應(yīng)用角度闡述位置大數(shù)據(jù)的意義和價值.傳統(tǒng)的諸如軌跡數(shù)據(jù)等往往僅被用以分析城市交通等直接且特定的問題.但大量經(jīng)典的大數(shù)據(jù)科學研究表明,通過價值提取和協(xié)同挖掘價值提取和協(xié)同挖掘后的數(shù)據(jù)結(jié)果能夠?qū)⒁恍┛此茻o關(guān)的事件很好地聯(lián)系在一起

4、,從而從數(shù)據(jù)層面“直接”反映一些原本需要復(fù)雜因果建模才能得到的結(jié)果,且更加直觀和準確1013.將簡單直接的數(shù)據(jù)應(yīng)用到社會經(jīng)濟活動、政治活動、自然環(huán)境、人類情感以及人口衛(wèi)生等一系列社會學、人類學、經(jīng)濟學的研究中。二設(shè)計理論（ ）二設(shè)計理論1.基本定義和預(yù)處理方法（ ）二設(shè)計理論1.基本定義和預(yù)處理方法1.1 地圖的預(yù)處理(a) 網(wǎng)格化分區(qū)14,15.(b) 依道路網(wǎng)分區(qū)16(c) 依位置密度分區(qū)5,17,18(d) 依參考點分區(qū)7（ ）二設(shè)計理論2.局部位置數(shù)據(jù)的特征提取2.1 區(qū)域靜態(tài)特征 區(qū)域靜態(tài)特征主要統(tǒng)計的是區(qū)域內(nèi)與地圖地貌相關(guān)的一些指標,可用于對不同區(qū)域進行聚/分類處理,例如區(qū)域內(nèi)快速

5、路的長度、普通路段的長度、道路交叉口數(shù)量、區(qū)域道路彎曲度、道路基質(zhì)質(zhì)量等特性所構(gòu)成的特征向量s2.2 個體移動模式特征 個體移動模式(mobility pattern,簡稱 MP)以單個移動對象o為觀察目標,包括其在一段時間內(nèi)的移動獨一性、隨機性、周期性、轉(zhuǎn)移性、動靜間歇性和移動期望性等方面.mp（ ）二設(shè)計理論2.局部位置數(shù)據(jù)的特征提取2.2.1 移動獨立性結(jié)論：通過觀察很少的區(qū)域,便能唯一確定一條用戶軌跡.這既說明個體移動具有高度的規(guī)律性。獨一性大小反映出數(shù)據(jù)集所在人群的整齊劃一程度,因此在不同數(shù)據(jù)集上分析個體移動獨一性,將有助于通過位置大數(shù)據(jù)分析其背后人群的自由程度、政治體制和生活情態(tài)。

6、（ ）二設(shè)計理論2.局部位置數(shù)據(jù)的特征提取2.2.2 移動隨機性 個體移動的隨機性可用位置熵(location entropy)來度量.設(shè) 為訪問一個位置的隨機變量,參照信息熵的定義,可以給出多類位置熵:xp補充：補充： 信息熵 信息論之父 C. E. Shannon 在 1948 年發(fā)表的論文中指出，任何信息都存在冗余，冗余大小與信息中每個符號的出現(xiàn)概率或者說不確定性有關(guān)。衡量它可以根據(jù)其出現(xiàn)的概率來度量。概率大，出現(xiàn)機會多，不確定性?。环粗痛?。 不確定性函數(shù)f是概率P的單調(diào)遞降函數(shù)；兩個獨立符號所產(chǎn)生的不確定性應(yīng)等于各自不確定性之和，即f（P1，P2）=f（P1）+f（P2），這稱為可加

7、性。同時滿足這兩個條件的函數(shù)f是對數(shù)函數(shù)，即：xp（ ）二設(shè)計理論2.局部位置數(shù)據(jù)的特征提取2.2.3 移動轉(zhuǎn)移性Jaccard 系數(shù)，又叫Jaccard相似性系數(shù)，用來比較樣本集中的相似性和分散性的一個概率。Jaccard系數(shù)等于樣本集交集與樣本集合集的比值，即J=|AB|/|AB|。（ ）二設(shè)計理論2.局部位置數(shù)據(jù)的特征提取2.2.4 移動期望性（ ）二設(shè)計理論2.局部位置數(shù)據(jù)的特征提取2.2.4 移動期望性（ ）二設(shè)計理論2.局部位置數(shù)據(jù)的特征提取2.2.4 移動期望性（ ）二設(shè)計理論3.位置大數(shù)據(jù)降維分析及全局建模3.1 位置大數(shù)據(jù)建模（ ）二設(shè)計理論3.位置大數(shù)據(jù)降維分析及全局建模3

8、.2 空間尺度上的降維處理 介數(shù)是所有經(jīng)過 ri 的最短路徑數(shù)量(,忽視了多條路徑在交通中存在的關(guān)聯(lián)性.所以我們對介數(shù)指標進行了改進,其核心思想是:i) 如果網(wǎng)絡(luò)中大量交通行為會同時選擇兩個結(jié)點 ri和 rj作為其最短路徑的傳播點,那么這兩個結(jié)點的重要性是共生關(guān)系,記為ij0.原始介數(shù)指標將這二者共同承擔的那一部分重要性重復(fù)計算到各自結(jié)點中去,造成了重要性的高估;ii) 如果對網(wǎng)絡(luò)中結(jié)點 ri 進行摘除后可以發(fā)現(xiàn),原本那些以 ri 為最短路徑的鏈路大部分“取道”結(jié)點 rj,說明結(jié)點 rj 對結(jié)點 ri 具有潛在的替代作用,記為ij0.這種替代性在原始介數(shù)指標中未能體現(xiàn),從而造成了結(jié)點交通重要性

9、的低估.（ ）二設(shè)計理論3.位置大數(shù)據(jù)降維分析及全局建模3.2 空間尺度上的降維處理（ ）二設(shè)計理論3.位置大數(shù)據(jù)降維分析及全局建模3.3 時間尺度上的降維處理（ ）二設(shè)計理論4.特征關(guān)聯(lián)及協(xié)同挖掘研究目的：大數(shù)據(jù)研究中還有一個突出問題,即,數(shù)據(jù)稀疏性導(dǎo)致的結(jié)果失真。群體往往比較喜歡在一些特定場所聚集,從而造成這些地方的觀察數(shù)據(jù)密度過高.而真正需要密度數(shù)據(jù)的區(qū)域,由于缺少采集手段,卻又無法獲得真實的位置記錄.（ ）二設(shè)計理論4.特征關(guān)聯(lián)及協(xié)同挖掘4.1 空間尺度上的協(xié)同挖掘（ ）二設(shè)計理論4.特征關(guān)聯(lián)及協(xié)同挖掘4.1 空間尺度上的協(xié)同挖掘（ ）三總體模型（ ）四參考文獻5 Pan G, Qi

10、GD, Wu ZH, Zhang DQ, Li SJ. Land-Use classification using taxi GPS traces. IEEE Trans. on Intelligent Transportation Systems, 2012, 14(1):113123. doi: 10.1109/TITS.2012.22092017 de Montjoye YA, Hidalgo CA, Verleysen M, Blondel UD. Unique in the CROWD: The privacy bounds of human mobility.Scientific

11、Reports, 2013,3. doi: 10.1038/srep013768 Song X, Zhang QS, Sekimoto Y, Horanont T, Ueyama S, Shibasaki R. Modeling and probabilistic reasoning of populationevacuation during large-scale disaster. In: Proc. of the 19th ACM SIGKDD Intl Conf. on Knowledge Discovery and Data Mining.New York: ACM Press,

12、2013. 12311239. doi: 10.1145/2487575.248818914 Zheng Y, Liu F, Hsie HP. U-Air: When urban air quality inference meets big data. In: Proc. of the KDD. 2013. http:/ Liu SY, Liu YH, Ni LM, Fan JP, Li ML. Towards mobility-based clustering. In: Proc. of the 16th ACM SIGKDD Intl Conf. onKnowledge Discover

13、y and Data Mining. New York: ACM Press, 2010. 919928. doi: 10.1145/1835804.183592016 Yuan J, Zheng Y, Xie X. Discovering regions of different functions in a city using human mobility and POIs. In: Proc. of the 18th ACM SIGKDD Intl Conf. on Knowledge Discovery and Data Mining. New York: ACM Press, 20

14、12. 186194. doi:10.1145/2339530.233956117 Zhu B, Huang QX, Guibas L, Zhang L. Urban population migration pattern mining based on taxi trajectories. 2013. http:/ Li ZH, Ding BL, Han JW, Kays R, Nye P. Mining periodic behaviors for moving objects. In: Proc. of the 16th ACM SIGKDD Intl Conf. on Knowled

15、ge Discovery and Data Mining. New York: ACM Press, 2010. 10991108. doi: 10.1145/1835804.1835942（ ）四參考文獻24 Cranshaw J, Toch E, Hong J, Kittur A, Sadeh N. Bridging the gap between physical location and online social networks. In: Proc. of the 12th ACM Intl Conf. on Ubiquitous Computing. New York: ACM

16、Press, 2010. 119128. doi: 10.1145/1864349.186438026 Yuan J, Zheng Y, Xie X, Sun GZ. T-Drive: Enhancing driving directions with taxi drivers intelligence. IEEE Trans. on Knowledge and Data Engineering, 2013,25(1):220232. doi:10.1109/TKDE.2011.20033 Guo C, Wang LN, Zhang XY. Study on network vulnerability identification and equilibrated network immunization strategy. IEICE on Information and System, 2012,E95-D(1):4655. doi: 10.1587/tran