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

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

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

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

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

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

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

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

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

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