785
分享課丨微軟研究院資深主任研究員鄭宇教授：多源數據融合與時空數據挖掘（一）
3月3日，中國人工智能學會AIDL第二期【人工智能前沿講習班】在北京中科院自動化所舉行，本期講習班的主題為【機器學習前沿】。周誌華教授擔任學術主任，前來授課的嘉賓均為中國機器學習界一流專家、資深科研人員和企業精英，包括：耿新、郭天佑、劉鐵岩、王立威、葉傑平、於劍、餘揚、張長水、鄭宇、朱軍。
鄭宇
微軟研究院城市計算領域負責人、資深主任研究員、上海交通大學講座教授、香港科技大學客座教授、人工智能國際權威期刊 ACM TIST 主編、美國計算機學會傑出科學家，ACM數據挖掘中國分會（KDD China）秘書長。2013年被MIT Technology Reivew評為全球傑出青年創新者（TR35）。在國際頂尖會議和期刊上發表論文百餘篇，論文被引用12000多次， H-Index 53（Google Scholar，截至2017-3-15），2016年論文單年被引用3200餘次。
本文根據鄭宇教授在中國人工智能學會AIDL第二期人工智能前沿講習班＊機器學習前沿所作報告《多源數據融合與時空數據》編輯整理而來，本文在未改變原意的基礎上略作了刪減。
謝謝介紹，謝謝邀請！大家經常聽到的機器學習、人工智能這些概念，大部分應用案例都是在圖形圖像以及自然語言處理方麵，在城市裏跟我們生活比較接近的，特別是應用在時空數據的例子比較少。現在我就用城市大數據為例子，來說明一下機器學習如何應用於時空數據領域。
大家都知道我們現在生活越來越現代化，但是問題越來越多：交通擁堵、環境惡化、能耗增加。要解決這些問題在很多年前看似幾乎不可能，因為城市設置非常複雜，環環相扣，牽一發而動全身，現在由於有了各種傳感器技術的成熟和雲計算單元的成熟，使得我們有各種各樣的大數據，從社交媒體到交通流量，從氣象條件到地理信息，如果使用得當的話，我們就能夠用這些數據來發現城市麵臨的問題，並進一步通過組合這些數據來解決我們麵臨的挑戰。基於這樣的機遇和挑戰，我們在2008年就提出了城市計算這樣一個願景，包括以下四個層麵：從下往上（下圖）有城市感知數據獲取，城市數據的管理，城市數據的分析和挖掘到最後服務的提供。
雖然我們今天主題是叫機器學習，但是我想你們肯定想，機器學習到底能解決什麼城市問題。在機器學習真正落地的過程中，可能還要依托於其他的平台甚至於其他的學科，包括數據管理。我就成體係地講講到底機器學習算法怎麼改變我們生活中的方方麵麵。
從最下麵的層麵來看，城市數據感知這部分，其實每個層麵都發現我們都需要用機器學習的方法來做一些事情，這個層麵是概念上劃分的，實際說是互相有交集的。
城市數據獲取
我們看城市數據的獲取，獲取方式主要有兩種：
-
第一種，以傳統傳感器為感知的方法
-
第二種，以人為中心的感知方法
第一個，以傳統傳感器的感知方法進一步可以分成兩個子類，要麼把傳感器放在一些固定的地方，要麼把傳感器裝在一些移動的物體上麵，比如說在公交車、出租車上裝傳感器，但是不管哪一種，一旦裝完之後人就不參與了，這個數據自動傳到我們後台。
另外一個，以人為中心的感知，這是比較新的概念，也叫群體感知，這裏麵也分成兩個方麵，一個叫做被動式群體感知，一個叫主動式群體感知。被動式群體感知，每天每個人都在參與，我們並不知道我們打電話的時候，我們的數據可以拿去改進通話網絡的質量；我們並不知道我們公交車上下車刷卡的時候，這個數據可以幫助優化我們的公交線路，改進城市規劃。把每個人的數據收集在一起，感知城市的變化，最後解決問題，這叫做被動式群體感知。主動式群體感知就是，任務是什麼很明確，什麼時間、什麼地點、幹什麼事情、共享用什麼數據，這個數據拿來幹什麼用都很清楚，甚至還有激勵機製，你可以選擇什麼時候加入或不加入。這是目前城市數據來源的四種方式。
城市感知之後我們會遇到什麼樣的難點呢，特別是跟機器學習有什麼相關性，我總結了四個方麵的難點，跟機器學習相關的難點。
-
第一，我們在城市數據感知的時候，往往拿到的是采樣數據，不是全集。
假設整個城市數據是灰色的點，我們可能隻拿到紅色的這一部分，某些屬性在這些采樣數據上分布跟在全集數據上的分布很不一樣。舉個實例，比如可以拿到出租車的GPS軌跡（數據），我們知道出租車隻是整個城市裏麵車流的一小部分，出租車的分布跟我們私家車的分布可能很不一樣，有的地方可能很多出租車，但是沒有那麼多私家車，反過來，可能有的地方很多私家車，卻沒有什麼出租車。所以你不能說簡單看到幾個出租車，乘一個係數就推斷有多少私家車，這個就是偏斜的分布問題，不管哪個場景裏，發現我們拿到的都是采樣，如何從這些采樣數據裏麵把全集的知識推斷出來，比如說怎麼把整個城市裏麵所有車的車流量實時推斷出來，這就是對應的難點。這個地方有相應的論文，如果你對這個問題感興趣的話，類似的問題可以從這些論文裏找到相關的技術，我先把它概述一下，這是第一個難點。
-
第二，Data Sparsity，我們的傳感器往往是很少的
舉個例子，我們北京市空氣質量分析。北京市我們建了35個空氣質量站點，你知道北京那麼大，光靠這35個空氣質量站點，怎麼把整個北京市每個角落的空氣質量都能夠感知到呢，這是一個數據稀疏的問題，這裏麵要用到一些機器學習的方法來做。
-
第三，Data Missing的問題
這個問題可能很多人認為跟Data Sparsity是同一個問題，其實不是同一個問題.。Data Sparsity是采樣點很少，Data Missing是說本來就應該有個點，可是因為傳感器出現故障，導致這個小時的數據會丟失。Data Missing是一個雪上加霜的問題，不是同一個問題，一個是說傳感器少，一個說我本來有傳感器可能還會丟，怎麼去把這個丟失的數據填滿，這可能是很多問題需要做的預處理的第一步，後麵學習的時候就要填，怎麼填一下等下我來講。Data Sparsity、Data Missing，這是第二和第三大挑戰。
-
第四，資源有限
如何用有限的資源做更多的事情，采更多的數據，如何利用限的資源獲得更大的感知效果，這是非常困難的。為什麼困難？兩個原因，第一，我們有很多候選集可以選，從很大的數據集裏麵選一部分數據的時候，往往是一個NP的問題。比如，我們城市那麼大，每個路口都可以布充電樁或者加油站，而我隻有錢布2到3個充電樁，我應該放在什麼位置，使得效果最大化。這就是一個maximum coverage的問題。還有一個原因會導致問題更難，即我們根本不知道Ground Truth。假設北京已經有兩個空氣質量監測站點，我們還要建4個，我們要放在什麼地方使得空氣質量感知最大化，你沒有建站點之前不知道這個空氣質量多少，根本不知道什麼叫好、什麼叫壞，這是難點，裏麵都有相關的論文去解決這樣的問題。
現在講完城市感知的一些挑戰和采集的方法之後，我們來看一個比較真實的例子。先看一個偏應用的，再看一個偏理論的。先看比較偏應用的。
我們都知道120係統，病人打電話到急救中心，急救中心會從救護車站派車把人送到醫院，再返回到救護車站。救護車站並不都在醫院，有很多原因。
第一，救護車運營係統和醫院其實是兩個不同的係統；
第二，很多時候我們必須要把救護車放在某個地方（不是在醫院），要保證對任何一個唿救，救護車能在規定的時間內能夠到達搶救地點。如果車都放到醫院裏麵，必然有的地方就會太遠，使得救護車不能在規定時間內到達，搶救病人。
下圖是天津市的一個救護車站站點的分布圖。以前站點的選址，可以說基本上是拍腦袋決定，比如根據一個地方大概的總人口數、路網密度來布置站點。大家知道120的需求量跟人口數並不一定成比例，還跟人的身體健康狀況、年齡結構有關。現在我們有了真實的120求救數據，我們知道什麼時間、什麼地方，有多少人求救。以及救護車在急救過程中他們的GPS軌跡、花了多少時間，通過我們的方法、算法重新對站點的位置選址和布局，使得救護車救這麼多病人平均搶救時間最小化。通過我們的算法重新選址後，我們能夠把搶救時間縮短30%。比如，以前救100個病人假設花100個小時，現在隻需要花70個小時，還是那麼多車、還是那麼多站點，我們卻能更快地把病人送到醫院。把時間節約下來留在在手術室搶救病人的生命，這是人命關天的事情，是資源調度優化的問題。這個站點如何部署就很有講究了，你放的好和不好就會有很大的區別。
第一步放完站點之後，第二步，這個站點裏麵的車的數量不是固定的，有的地方早上需求量較大，有的地方晚上需求量較大，不能說車從早到晚一直放在某個站點，浪費了。這個車在站點之間如何動態調配，使得我們的資源最大化，這是問題。這是我們解決這個問題裏邊兩個研究的點，這兩個技術分別幹什麼事情，第一個是選站點，第二個是資源在站點之間的調配。你可以想象這是一類通用的問題。找出一個點，使得很多人到這個點的平均時間最短化。通俗的例子，比如我們10個同學聚會，選擇哪個地方聚會，使得大家去的平均時間最短，這就是一個例子。我們救護車站、火警，凡是時間因素非常關鍵的選址都可選用這類模式。
第二個，偏理論的例子。我剛才說數據會缺失，要填補，怎麼填補？這是一個非常基礎的問題，幾乎我們做所有的機器學習的人在第一步拿出數據的時候會發現，這個數據質量不好，有一些缺失。可能傳感器壞了，或者數據沒傳過來。我們拿的很多數據都是有缺的，氣象數據有缺的，空氣質量有缺的，甚至包括車聯網裏麵數據很多都是會出現殘缺的，怎麼填？這是一個很重要的問題。
我們怎麼做呢？我們基本上就是利用缺失點時序以及空間鄰居的數據，一起來把這個數據填滿，而不是僅僅隻看自己的時間臨近值。至於怎麼用、怎麼填是有講究的，是用前一小時的數據還是用周邊的數據，這個其實是比較難決策的過程。
這個問題有幾個難點，為什麼很難？
-
第一，我們並不知道什麼時候、什麼地方數據缺，缺的是隨機的，不是固定的，導致我們很多機器學習模型不能用。因為我們知道機器學習的輸入，一定是有輸入的特征、維度，各種維度是固定的，如果你不知道哪個地方會缺、哪個地方會有，你的目標在哪裏都不知道，所以很難用一個很好的固定模型來做。甚至有時候會出現整體缺失，比如說6個小時斷電了，所有傳感器沒有了，或者某一個傳感器連續5、6個小時都沒有數據，怎麼辦，這是一個難點，把缺失的數據填完是很難的。
-
第二，我們往往覺得用臨近的差值就好了，但是臨近差值並不一定就對，在很多應用場景裏，特別是我們城市環境裏麵很多應用是不對的。用空氣質量站點為例子，你們看這幾個站點裏麵，這兩個站點更近一點，這個站點更遠一點，按理來講空氣質量缺失的是用近的代替更好一點，但實際發現，雖然這個站點距離近，但是這個站點是在森林裏麵，而兩外兩個站點都在商業區，商業區的空氣質量更像，隨著這兩個商業區的位置比較遠。因此，並不是越近的越像，還要看這些位置所處的環境，這會打破常規規律。時間上也是一樣的，當然在平穩的時候，是越接近的時刻空氣質量越像，比如，這一個小時可能跟未來一個小時的空氣質量接近。當遇到大風、極端天氣，出現陡降的時候，下一個小時的值可能驟降，還不如找更遠的時間的空氣質量還替代此刻的缺失值。時空臨近不一定都是對的，可能大部分都是對的，但不一定都對。
我們用幾個方法來解決這個問題：
-
第一，從時、空兩個角度來解決
空間角度，就是可以用周邊的站點數據。簡單來說，把這個數據放在矩陣裏麵，每一行是傳感器，每一列就是時間點，每個值就是這個傳感器在這個時間點的讀數，這個叉的就是缺的地方。這個缺的時候用周邊的填，相當於用行間的關係把它填了。
時間角度，根據一個傳感器自己的值，就是說前後的值、左右的值來填它，這個傳感器前後時間值就對應這個矩陣裏麵左右行的值。
-
第二，從局部、全局兩個角度來解決
局部，是用最近的數據來填，假設我把最近的數據形成一個小的矩陣，我們通過矩陣的關係來推斷這個數值。
全局，是根據一個很長曆史數據，找到經驗性規律來填。 什麼是全局，根據地理學第一定律，地球上越近的地方越像，大部分時候是滿足這個規律的。隨著距離的增加，兩個點之間的空氣質量相似點就應該下降，這個是正常的。往往都會用這種方法來做，跟距離成反比的線性加權關係。根據時間的話，一般都認為時間越遠越不像，不像一般是指數衰減，一般是用SDS，β是一個小於1的係數，越遠的越不像。這個是經驗公式，不一定都滿足，剛剛講的例子就不滿足，比如剛剛這兩個地方雖然近，反而更遠的更像，是因為這兩個都是酒吧商業街，不見得這個地方就像，而且這個地方臨近的時候也不見得像。這部分數據怎麼辦呢？就靠你最近一段時間的數據，我們不看長遠的，就看最近一段時間裏麵的數據，把它形成一個local view。大家如果學過協同過濾，就是一個推薦的方法，我們把人看成一個傳感器，你就可以用基於用戶的方法和基於這個方法來做一個協同過濾。
總的來說，從時空來看，從局部全局看，2×2就有四種方法，對應四個模型，四個視角。用局部的時間、局部的空間和全局的時間、全局的空間，你分別都會有一個結果，這四個結果做一個多視角的學習（Multiview learning），得到最優解。每個模型的權重都是通過學習獲得的。
總的來說，我們是要考慮局部、全局、時間、空間的關係，綜合來填補缺失值。這個方法可以認為是目前在時空數據差值裏麵最好的方法，幾乎在所有的方法裏比較過是最好的。隻要大家以後做傳感器，做時空數據的時候，拿到數據第一步發現缺，你要填，就用這個方法。
城市數據管理
回到我們的城市計算第二個層麵，剛剛講了城市感知層麵，我們要看城市數據管理。要管好城市大數據就是三方麵的東西，第一，時空數據，這是時空的屬性，不是一般的文本，也不是視頻。第二，就是這種增強性的雲平台，不是普通的雲平台。第三，時空的索引，就是查詢和檢索算法。
我為什麼要講數據管理呢？今天是機器學習的論壇，講數據管理幹什麼呢？其實在真正的場景裏麵，如果沒有這一層，很多機器學習的算法可能隻能停留在論文上，很難在真實係統落地，數據管理的人本身跟機器學習的人應該有很好的合作關係，不是敵人，應該有機的合作。通過後麵的這些例子，大家就會明白了，真正想把機器學習從理論變成實際，解決問題的話，還需要有數據管理的知識，要對平台有了解。
我們城市裏麵數據可能成千上萬個，但是根據數據的結構來分的話其實就兩種，一個是點數據，另一個是網數據。
根據數據關聯的時空屬性的變與不變與否，可以分成三類：1）是時間和空間都不變的，屬性都不變，靜態數據；2）是空間不變、時間變；3）時、空都變。
現在聽起來比較抽象，所以說2×3是6組數據，你們可以想，你心目中所有的數據，我都會告訴你在哪兒。比如說我們的興趣點數據，什麼叫興趣點？一個車站、一個酒吧、一個學校就是興趣點，有坐標、有地址、有名稱，一旦某個商場建好之後空間就不變了，有多少層樓、多少個窗戶也是固定的，所以時間和空間都是靜態的，這是點數據。
我們把傳感器放在好，位置不變，是個點，可是每個讀數隨著時間變化，屬於空間不變、時間變。
時間和空間都變是什麼呢？就像我們去騎摩拜單車，去打Uber，坐滴滴，用戶的數據就屬於時空散點數據，比如2點有用戶請求了，2點半有用戶在另一個地方請求了，位置和位置是變化的，並且時間也在變。
什麼是網絡數據呢？路網是靜態的，這個不變，時空都是靜態的網絡結構數據，一旦把交通流量疊加上來之後，就變成了空間靜態，但是時間動態的數據。什麼是時間和空間都動態並且網絡結構信息呢？就是軌跡。我們可以想象一下，滴滴的軌跡，摩拜的軌跡，都屬於這個數據，人類手機信號也屬於這類數據，我們騎行也屬於這個數據。
所以在摩拜和滴滴裏麵有兩個數據，一個是用戶請求數據，一個是騎行數據和開車數據。你隨便想，任何一種數據都能放到這六種之一，為什麼定義六種？因為不希望拿1千種數據，做1千個模型，1千種算法，這樣我的係統沒辦法承擔。一旦定義好這六種之後，可以對每種數據設定特定的管理算法、挖掘算法和機器學習算法，一旦有了數據之後，就能用這種方法套進去去做。這裏麵軌跡數據是最難的，是信息量最豐富的，人類的出行，打電話的記錄，車的記錄，飛機的記錄，候鳥飛翔，颶風移動，都屬於軌跡數據，因為時間、空間都在變。
講完數據之後，講講平台。異構、多源、多模，是三個不同的東西。異構就是結構和非結構的；多源就是來自於不同的領域和數據源（比如氣象和交通）；多模，就是有文本的、影像的、語音的。在城市大數據裏麵，這三個是全部具備的，那我們也會同時處理這些東西。我們的應用不是城市級別的，不是說某個攝像頭放在一個地方，或者在一條路上，那不叫城市計算。要做就是整個城市規模全做，需求量就是上百萬級、上千萬級用戶規模，這種大的應用場景，這麼多的數據，沒有好的平台是做不到的，所以我們首先就會想到用雲計算平台。但是非常抱歉的告訴大家，現在不管哪一家公司的雲計算平台，都不能很好的支持時空大數據，也就是我們城市大數據，為什麼呢？
有三個原因：
-
第一，時空數據的結構跟文本、圖像是非常不一樣的。大家可以想象我們拍了一個照片之後，這個照片始終是20K，拍的時候20K，永遠是20K，不會說隨著時間的變化不停的在變。但一輛車的軌跡在開車的過程中是不斷增加的，而且軌跡中兩個點不能隨便交換，不像我們一般記錄學生成績，把兩個學生成績兩行交換一下，並不能影響這個表格的準確性，時空數據就不能交換。
-
第二，我們以前查詢文本的時候，可以把包含關鍵詞的文本拿出來，但是我們做時空數據查詢的時候，往往是靠一個時空範圍，比如說查找我周邊最近2分鍾內空駛的出租車，查找過去兩分鍾所有這個樓周邊的摩拜單車哪個是空的，這都是空間加時間範圍查詢，它不是一個Keyword Match的問題。甚至比如說在開車的過程中查找最近的加油站在哪裏，車的位置還在變的，這都是在雲計算平台裏都不直接支持。
-
第三，真正要做城市大數據項目的時候，你發現絕對不是隻用一種數據，會用到多種數據，而且還要把多種數據的知識融合在一起。要融合多源數據的話，先不把各類數據管理好，不把它有機的索引在一起，到時候根本來不及做快速融合的問題，這就叫混合式索引，數據和數據關聯起來，把不同領域數據融合在一起。
這三個技術在現在的雲平台裏麵都是缺失的。
基於這樣的挑戰，2015年在貴陽市，貴陽是城市大數據示範基地，我們落地了中國第一個真正意義上的城市大數據平台。
首先，我們定義了六種數據模型，剛剛介紹過，根據數據結構、時空屬性變與不變，2*3=6種模型，不管什麼數據，都能用這六種模型中的一種把數據裝進去。我們利用了Azure本身的存儲機製，我們並不是什麼都自己做，全部自己做沒有必要，我們是用這個來增強。這個很重要，我們在這個層麵上加入了一個中間層，我們針對不同的數據結構設計了空間索引和時間索引算法，以及針對於多源數據之間的跨域管理做了混合式索引，把時空索引算法集成到 Storm、Hadoop、Spark裏麵去，向上提供API給我們的機器學習算法來用，使得我們的機器學習算法能夠快速的訪問大規模數據。如果你沒有這個，你發現你真的上大係統的時候，我們連特征提取都還沒做，這個任務的時間期限就到了，等不及你了。因為很多時候就是1秒鍾、2秒鍾就給我一個結果出來，如果我們光做特征提取就需要花了一兩個小時，模型怎麼上線，所以必須要有平台來支持。這裏邊既有分布式，也有索引，以前大家都說，我們有分布式係統了，不要索引了，那是不對的，我們可以結合在一起。有的時候你用100台機器學習做的事情，我可能2台機器就能做，因為有了索引和分布式的結合。
為了看平台的規律，給大家看幾個例子。
這個是在貴陽市布充電樁的例子。假設根據過去一年車的軌跡信息，我們在這個區域內放五個充電樁，我應該放在哪五個路口，使這五個路口加在一起，覆蓋的車的數量最大化，我強調一下，我們不是找最熱門的前五個路口，沒有意義，因為可能最熱門的前五個路口都挨著，經過第一個路口就經過第二個路口，我是說五個路口加在一起覆蓋的車總數最大化，就是不重複的車最大化。
以前做這個工作的時候，一輪結果計算需要8個小時到一天，因為計算量非常大。現在有個平台，3秒鍾以內做出來，為什麼需要做這麼快呢？這又回到行業了，我們知道真正布充電樁的時候有很多因素要考慮，還有很多專業的要求，比如說這邊是不是有空地，這周邊有沒有商場，有沒有飯店來容納我們的人，我們充電2—3個小時人去哪裏，不能讓他蹲在馬路邊，這些條件不符合的時候，可以允許用戶把這某個推薦的點刪掉，保留其他幾個點，然後讓算法回去再算，直到我得到一個滿意的結果為止。
這個其實是變成一個新的概念——人機學習。新的時代已經是人的智能加機器智能合在一起。要實現人機智能，一定要提供一個交互的方法，把人的智能帶進去。這個例子裏麵就是，我們先給算法一些簡單規則，讓算法找到一些初始的結果，讓行業專家去看這些結果，用他的經驗去判斷這個點是否合適，需要刪除掉還是加一個點，這樣把人的知識和機器的知識融合在一起，同時把數據科學知識跟專業行業知識融合在一起。
這非常重要，往往我們做大數據、做機器學習的時候到會遇到最後一步落地困難的問題，我們隻有數據科學知識，缺少行業知識，但真正解決問題兩者是缺一不可。行業的人往往不懂機器學習。此外，行業專家心中有很多複雜條件，他不一定能很好的量化和表達出來。此時，利用機器學習驅動的交互可視分析的方法可以彌補兩者之間的鴻溝。
正是因為要通過迭代、交互才能實現人機融合，保證算法執行的效率和性能就變得很重要。你想想，如果我們給算法一個反饋，要等一天才能看結果，人怎麼能跟機器交互呢。隻有像視頻裏那樣，專家給出反饋，算法馬上出結果，才能做到真正的吧人機智能交互和融合。要想獲得這樣的性能，剛才展現的那個城市大數據平台就變得必不可少。
這個問題剛剛說應用是在充電樁的選址，實際上廣告牌的選址是一樣的。很多時候說我們隻有有限的錢放廣告牌，我們放在哪幾個路口使得覆蓋最大化呢。跟我前麵講的救護車那個不一樣，那個是時間最優化，這是一個覆蓋範圍最優化的問題。
沒有平台，別想交互，別想跟人機智能結合，那我們也解決不了實際的行業問題，因為你拿這個結果給專家看的時候，我們還有很多因素沒考慮呢，這個初步的結果可能根本沒用。所以這也是一個行業知識跟機器學習結合的例子。
本文來源於"中國人工智能學會",原文發表時間" 2017-03-21 "
最後更新：2017-05-23 14:33:08