KDD 2017 參會報告

05-02

一背景：

KDD的全稱是ACM SIGKDD Conference on Knowledge Discovery and Data Mining。SIGKDD是ACM在數據挖掘領域的頂級學術會議，每年都吸引著超過2000位來自世界各地的頂級數據挖掘學者，以及知名企業代表前來參加。然而，大會的論文接收每年卻僅約200篇，接收率不超過15%。

今年的KDD大會於加拿大新斯科舍省的首府哈利法克斯（Halifax）落下帷幕。哈利法克斯是位於加拿大東部大西洋畔的一個城市，市區人口414400（2014年）。這已經可以算是近些年來大型會議舉辦城市中規模最小的了。據KDD會議主席介紹，之所以選擇哈利法克斯來舉辦有一個原因是「一直鍥而不捨的申請」。所以這次大會對於這個小城市來說是一件大事情。市長不僅親自來站台，並且還發表了一段熱情洋溢的講話。本次大會比較有特點的地方是主會場在冰球體育館內。儘管該城市已經是傾囊而出了，然而這麼個小城市一下子湧進了這麼多的參會人員，整個城市從旅館到飛機的壓力就嚴重超出負荷了。導致有的同學路上耽誤了兩天。

二概述：

有來自51個國家的1656人註冊了會議，是美國之外人數最多的一次。

註冊人來源佔比圖

考慮到美、加兩國也有大量華人註冊，所以和其他AI會議一樣，華人研究學者一直都是主角。本次會議有創記錄的總共1143篇投稿，其中研究型747篇，64篇oral（8.6%）和66篇poster(8.8%)。應用數據科學類390篇投稿，36篇oral (9.2%)和50篇poster(12.8%)。

三會議交流

會議中阿里的站台是最受關注的展台之一，很多著名學者來交流。大家對機器學習演算法在阿里的實際應用很感興趣，反映了KDD對演算法在工業應用中的偏好。

KDD 2017大會主席Stan Matwin在阿里展台

下屆KDD會議主席林智仁教授、熊輝教授在阿里展台

除了上述學者，伯克利大學的郁彬教授、今日頭條的李磊博士等也和我們進行了深入的交流。

四有監督學習

AnnexML: Approximate nearest neighbor search for extreme multi-label classification

背景：極多標籤分類最近受到了很大的關注。

比如一個例子是通過使用最相關的維基百科類的子集，用極多標籤分類器學習來標記新的維基百科文章（圖一）。另一個例子是考慮到用戶的網頁瀏覽歷史和搜索關鍵字，構建一個分類器給網路用戶顯示在線廣告。這兩個例子都出現了優化極多標籤分類器的需求。在這些案例中，標籤數量從萬到百萬不等。第一個例子如下圖所示:

訓練過程如下：

每一個點代表一個訓練樣本。具有相似標籤向量的樣本被連接起來組成下面的向量圖
訓練中學習出的超平面被分成K個子圖，並且讓這個結構儘可能的多
特徵空間經過學習被分成不同的子空間並且在嵌入式的子空間中更接近地分配連接樣本

預測過程如下：

1.使用訓練得到的超平面，決定測試樣本屬於哪一個區間

2.使用矩陣把測試點置於嵌入空間

3.這樣就能得到嵌入空間中的K最近相鄰點

4.經驗上的K最近相鄰分布的結果可以因此得到為：

對於精確預測：

1）用近似KNN（KNNG）作為弱分類方式來學習區域數據點

2）學習嵌入空間時，把這個問題轉化為排序問題

對於快速預測：

通過高效的在嵌入空間中穿越學到的KNNG來使用一個近似KNN搜索技術

從而得到下面圖示的嵌入空間

下圖顯示了實驗結果：

該論文有效地利用近似最近鄰搜索方法有效地探索嵌入空間中學習的KNN鄰圖。通過對幾個大規模的真實世界數據集進行了評估，並將提供的方法與最近的最新方法進行了比較。論文提供的實驗結果表明， Annexml可以顯著提高預測精度，特別是在有較大的標籤空間數據集。此外，Annexml提高了預測的時間和精度之間的權衡。在同級別的精確度，Annexml預測的時間比著名的SLEEC速度高達58次。

Similarity Forests

隨機森林由於其非凡的精度和有效性成為被經常使用的最成功的方法之一。然而它的使用主要局限於多維數據集。在本文中，作者提出了一個擴展的隨機森林方法突破這個局限。只需要計算數據對象之間的相似性，此外，在計算複雜性上，也從降低到的一部分。

本論文主要的貢獻在於：

設計了一種利用相似值來計算而不是多維特徵計算的隨機森林的方法
相似值的計算複雜度大概是
可以用於缺失值和有噪音的數據集
可以被應用於當全維度的表示是可能的時候：提供一個有競爭力的或者較傳統的隨機森林方法有輕微表現優勢的方法

SimForest 演算法細節為：

訓練：利用已經取樣的點的對構建森林的每一棵樹並且利用相似值進行拆分：當每一個葉子節點有100%準確度的情況下構建樹

測試：對於每一個測試樣例，僅僅使用測試點和訓練點之間的相似值來遍歷樹：預測葉子節點的顯著屬性。

相似值的計算公式為：

經過簡化以後成為：

下面兩張表顯示了SimForest 和SVM 在兩種情況下的對比，顯示出SimForest的性能優勢。

固定噪音係數下的準確率（α=2.5）

15% 的相似值丟失的情況下的準確率

五推薦部分

Unsupervised P2P Rental Recommendations via Integer Programming

這篇來自於密蘇里科技大學的文章針對如Airbnb、FlipKey以及HomeAway等P2P應用系統中的推薦問題做了很有意思的研究，遊客在外旅遊很重要的事情便是住和行，而這類item的推薦很難用有監督學習基於大量數據來訓練，這與我們之前參與飛豬旅行相關推薦問題的研究類似。選擇住處每個人都有不同的喜好，但對於房間的選擇條件確是我們可以抽象出來的，Yanjie Fu這裡提出了一種基於整數規劃的推薦系統，他將風險和收益都集中在一個目標函數中進行評估。民宿與酒店不同，你很難將其標準化進行評估，同時有很多信息是比較難獲取的；遊客在這種狀況下除了要關心住處的各項舒適指標，還要特別關注社區的安全問題，畢竟人身安全也很重要。整數規劃是眾所周知的難解問題，最常用的方法便是分支定界，而窮盡搜索的方法效率地下，這篇文章提出了learning to BB的思路，即引入分支選擇變數去模擬學習分支定界的演算法行為，這顯著改善了演算法性能。作者的實驗是在紐約市做的，結果是性能和效果上都達到了還不錯的效果。

住宿選擇有利/有風險的feature集合

問題的抽象定義：

Meta-Graph Based Recommendation Fusion over Heterogeneous Information Networks

這篇文章來自於香港科技大學，主要介紹了meta-graph在異構信息網路推薦中的應用研究。HIN異構信息網路對於淘寶的電商推薦建模非常有用，用戶和商品是典型的兩部圖，而它們之間會發生多種類型的關聯，如點擊、收藏、加購、購買、評論、退貨以及推薦等等。基於HIN的推薦主要面臨兩類問題，首先是如何表達推薦的高層語義信息，其次是如何融合異構的信息來進行item推薦。作者分別通過引入meta-graph概念以及採用MF（矩陣分解）+FM（因子分解機）方法嘗試解決了這兩個問題，文中在亞馬遜（類淘寶）和Yelp（類點評）兩個數據集上做了實驗，與傳統的異構信息網路演算法及FM演算法做了比較，作者新提出的思路明顯優於當前水平。我覺得這篇文章的工作還是比較接地氣的，沒有非常花哨的變形和複雜的模型，針對當前企業級推薦的複雜性和局限性進行了卓有成效的研究工作。

上圖是文中異構網路的例子及基於meta-graph訓練user-item隱空間向量的定義。

Recurrent Poisson Factorization for Temporal Recommendation

這篇文章來自伊朗德黑蘭的Sharif University of Technology，用到的因子分解機方法變種我之前並不熟悉，即泊松分解。文章中對於研究這個問題的動機描述很打動我，用戶在淘寶上逛推薦場景時，有的人喜歡商品找相似，有的人喜歡尋找新奇特，重口難調，而只是基於統計眾數的行為日誌做協同過濾會導致長尾用戶或者長尾需求很難得到滿足；但如果我們基於規則腳本又很難窮舉出用戶的興趣偏好，特別是這些偏好還是隨著時間變化的。這篇文章提出的再生泊松分解演算法比較系統的將時間類因素引入到泊松分解演算法中去，為我們解決推薦系統目前面臨的長尾優化問題提供了一條很值得嘗試的思路，文中實驗部分不算非常solid，這點我們可以在這個基礎上做進一步的研究。下圖是RPF再生泊松分解演算法的圖示：

Bridging Collaborative Filtering and Semi-Supervised Learning: A Neural Approach for POI Recommendation

這篇文章來自於KDD經典paper大戶—UIUC的Han Jiawei老師實驗室，論文中的方法和實驗都比較solid，主要嘗試用神經網路模型來結合協同過濾與半監督學習，然後進行POI（興趣點）的推薦。文章中的思路不算特別新穎，對數據問題的建模屬於今年Deep Learning for Recommendation的標準配置。下圖是文中設計的NN網路結構

Embedding-based News Recommendation for Millions of Users

這篇文章來自於Yahoo日本，主要介紹了日本首頁上的新聞推薦，比較標準的基於DL的一個工作，新意不多，因此大會也並沒有將這篇文章選入做oral presentation。文中分為三個主要步驟，首先基於一個去噪自動編碼器生成新聞的分散式表達；然後以用戶瀏覽歷史作為輸入基於RNN模型生成用戶表達；最後用user-item內積排序做top-k推薦。作者在Yahoo日本首頁上線實驗了他們的演算法，ctr有10%-23%的提升，我們在手淘首頁猜你喜歡的視頻瀑布流推薦中也嘗試了類似的方法，ctr有20%的提升，這是在item本身屬性挖掘比較困難的前提下一種折中方法，整體效果還是不錯的。

Dynamic Attention Deep Model for Article Recommendation by Learning Human Editors』 Demonstration

這篇文章來自於上海交通大學，值得注意的是來自UCL的Weinan Zhang，今年UCL的Jun Wang老師實驗室在推薦、IR領域非常活躍。文中提到的motivation對電商推薦還是很有啟發的，傳統的新聞門戶網站選擇上頭版的模式都是編輯選稿，而這樣的方式是勞力密集型，演算法衝進去試圖去捕獲編輯的選稿過程，進而可以把這個工作自動化掉，還能做到supervised，挺有意思的工作。手淘的產品一直在提社會化選品、達人選品其實就是這個路子，人的大腦判斷並不是只基於一些熱點辭彙或者圖片展示等淺層特徵，而attention model可以在一定程度上刻畫選品感覺這個東西，這篇適合做推薦的同學泛讀。

Online Ranking with Constraints: A Primal-Dual Algorithm and Applications to Web Traffic-Shaping

這篇文章來自於Yahoo研究院，本著他們出品必出精品的原則拜讀了一下，企業研究院搞的問題就是接地氣，文章中著手解決的問題對於處理推薦流量上非商品item、廣告以及自然流量item之間的關係非常有用，其提出的指標矩陣體系也很實用。下面是幾張現場拍的問題分析ppt部分截圖，感性的同學可以去詳細讀下文章。

六表徵學習

表徵學習旨在自動抽取特徵，用以取代（專家）特徵工程所花費的時間。帶著強大的自動特徵抽取的能力，表徵學習在傳統機器學習一直無法突破的領域，取得了非常驚人的優異表現。今年KDD的表徵學習會場總共包含了5篇文章。除了第一篇「EmbedJoin: Efficient Edit Similarity Joins via Embeddings」是採用資料庫的思路對高維數據進行embedding外，其餘四篇paper都跟神經網路相關。最近representation learning, embedding方面的文章非常多，大有「全民embedding, everything to vector「之勢。

EmbedJoin: Efficient Edit Similarity Joins via Embeddings

Edit similarity join是資料庫系統的一個主要操作，在數據清理集成，生物信息學，協同過濾，自然語言處理等領域有著廣泛的應用。Edit distance中文又叫編輯距離，i.e., ED(x,y)指將字元串x轉為字元串y所需的最少編輯次數，常見的編輯方式有插入、刪除、替換。給定一堆字元串，一個閾值K， edit similarity join將會返回所有edit distance小於K的字元串組合。例如，給定字元串ACCAT，CCAAT，GCCCT，CACGA，AACGG，假設K=2，edit similarity join將會返回(ACCAT，CCAAT)，(ACCAT，GCCCT)，(CACGA，AACGG)。

跟常見的距離度量方式，e.g., Hamming distance、 Cosine、Jaccard，Edit distance可以很好的保留待比字元串中字元的順序。這些在某些特定的應用場景下至關重要。然而，Hamming distance、 Cosine、Jaccard等距離度量方法只需要O(n)進行計算，edit distance需要O(n^2)的時間複雜度，n為待比字元串的長度。

針對這個問題，當前已有大量的優化演算法被提出。但目前所有的技術方案均不能很好地解決較長待比字元串的大閾值問題。在實際使用場景中，較長的字元串往往需要使用較大的閾值才能夠找到合適的匹配。根據最新的文獻報告，當K=0.25*n，目前的技術都會有性能的瓶頸。

針對上述問題，這篇文章提出了名為「EmbedJoin」的解決方案。與目前大部分的優化演算法直接計算原始字元串的edit distance不一樣，EmbedJoin包含兩步: i), 將待比字元串從Edit space映射到Hamming space，映射的方法已被證明能夠提供距離的bound；ii)，利用hamming space上LSH對字元串進行過濾。

EmbedJoin使用到的主要技術包括以下兩個(感興趣的同學可以具體去看paper)

a).CGK embedding

b).LSH for hamming distance (bit sampling)

EmbedJoin的效果:

i). 犧牲一點召回, e.g., 95%-99% recall, 100% precision，大幅降低response time和memory usage

ii).能夠handle大閾值的edit similarity join, e.g., 20% * n

Collaboratively Improving Topic Discovery and Word Embedding by Coordinating Global and Local Contexts

一個文本語料庫一般都包含兩部分的信息：全局上下文(global context)和局部上下文(local context)。

i). 全局上下文: 主要指的是文檔級別的共現信息，一般可用於對文檔進行topic modeling。常見的topic models演算法，例如LDA和PLSA，都是基於「each document is composed of a mixture of latent topics, each of which is a multinomial distribution over words」的假設。

ii).局部上下文: 主要指的是詞級別上下文信息，包含了詞的semantic和syntactic信息，一般可用於對詞進行embedding。常見的word embedding models，例如NPLM和Skip-Gram都採用了以下假設, i.e., 」words occurring in similar local contents tend to have similar semantic and syntactic properties」。

其中全局上下文用document-word矩陣描述，矩陣上下文用word co-occurrence矩陣刻畫。

兩種類型的信息互為補充，可協同使用。

基於上述想法，作者提出了一個統一語言模型。該語言模型採用了以下三個假設:

i). Global: 每篇文檔集中在很一小部分的topics，每個topics包含一小部分概率較高的詞。

ii).Local: 經常出現在一起的詞趨於用於同樣的syntactic和semantic特性，因此在embedding空間裡面應該離得比較近。

iii). Collaboration: 在embedding space裡面離得比較近的詞趨於擁有同樣的topic distribution, 反之亦然。

最後使用協同矩陣分解來discover topic structures和learn word embedding。

聯合embedding的效果: topic coherence，document classification, word similarity, word analogy等任務上都比現有的方法有所提高。

Metapath2vec: Scalable Representation Learning for Heterogeneous Networks

Network embedding已被廣泛研究，與deepwalk，node2vec有所不同,

來自微軟與其他機構合作的這篇文章主要研究異構網路的embedding。

異構網路的embedding主要有以下三點挑戰:

基於這些挑戰，作者給出的solution是:

其中mmetapath2vec與metapath2vec++都是採用了meta-path-based random walks.與一般的random walk不同的地方在於每一walk都會依舊現有的scheme有bias. Metapath2vec與metapath2vec++在於embedding使用的模型。Metapath2vec採用skip-gram, 而metapath2vec++採用的是heterogeneous skip-gram。兩者的主要區別在於計算softmax的過程中是否考慮node type。

Deepwalk/node2vec，PTE，metapath2vec，metapath2vec++得到的node embedding的可視化展示：

Struc2vec: Learning Node Representations from Structural Identity

Deep walk，node2vec以及剛才介紹的metapath2vec都是利用一個node的context information對一個node進行embedding。這些方法在分類與預測任務上取得了不錯的表現。然而這種就node context information進行embedding的方法也有不足之處。例如，下圖中的u和v在結構上非常相似，但是由於兩者之間離得非常遠，沒有任何share的node，之前的embedding方式並不能捕捉到他們之間結構上的相似性。

這篇文章提出了一個較為靈活的框架，i.e., struc2vec，對圖中的節點進行embedding，以期能夠捕捉node在結構上的相似度。

Struc2Vec主要包含以下三步:

i). 衡量node之間的structural similarity

ii). 基於node的structural similarity，構建context graph

iii).產生每個node的context

iv). Node embedding

struc2vec在barbell graph上的效果展示：

七 Workshop-AdKDD&TargetAD

這是兩個computational advertising領域的workshop，KDD2017兩者合在一起召開。其中TargetAD較新，今年是第3期；AdKDD則相對歷史悠久，從2007年至今已經舉辦過10期。很多ad領域的經典工作，如2013年Facebook的GBDT+LR，今年Google的Deep & Cross Network，均是發表在AdKdd上的，總體來說，這個workshop能夠較好地反映這個行業的巨頭們在ad方向上的關注和研發重點，發表的工作實用性很強。在KDD2017的現場，這個workshop幾乎是我見到的最火爆的一個，不僅座無虛席，幾乎能落腳的地方都有人席地而坐；下午的talk我來晚了點，只能站在門口聽完，工業界topic的影響力和人氣可見一斑。

AdKDD&TargetAD 2017的outline

這是一個full day的workshop，分為兩類talk，穿插進行。

1）invited talk

今年邀請了四位大牛，Amazon的Alex Smola，Cornell 的Thorsten Joachims，Netflix的Randall Lewis，Stanford的Susan Athey，陣容還是蠻強大的。前兩位大家應該更為熟悉一些，他們的talk集中在更好地針對工業數據進行建模，後兩位集中討論了廣告的效果歸因，採用的方法是Causal Inference，這是今年KDD上一個討論和關注得較多的一個流派。

slides的地址見：https://adkdd17.wixsite.com/adkddtargetad2017/copy-of-alex-smola。不過還有兩位遲遲沒有提交，感興趣的同學只能自己發信去索要了。

2）accepted paper report

一共12篇工作被接收，且全部進行了oral宣講。今年比較好的是，全部的slides都公布在網站上了，地址：https://adkdd17.wixsite.com/adkddtargetad2017/accepted-papers。

重點方向一覽

1）市場保留價

本次workshop有兩篇相關的工作，分別來自linkedin和yahoo，帶著非常濃厚的工業風。其中yahoo這篇工作的所有作者均加入了阿里，感興趣的同學可以直接找作者們交流細節。

相關論文如下：

Data-Driven Reserve Prices for Social Advertising Auctions at LinkedIn，來自LinkedIn

Optimal Reserve Price for Online Ads Trading Based on Inventory Identification，來自Yahoo

2）預估模型

這是成熟的ad公司關注和研究的焦點。本次workshop中有四篇相關的工作，其中google的DCN(deep & cross network)我做了重點跟蹤，是對google wide&deep learning工作的後續拓展，延續了google ads一貫的對人工交叉特徵的堅持作風，巧妙地通過多層神經網路構造了多項式階交叉特徵，感興趣的同學可以讀一讀。

相關論文如下：

Deep & Cross Network for Ad Click Predictions，來自Google

An Ensemble-based Approach to Click-Through Rate Prediction for Promoted Listings，來自Etsy，作者之一是微博上比較火的技術網紅洪亮劼。

A Practical Framework of Conversion Rate Prediction for Online Display Advertising，來自Yahoo&Alibaba

Ranking and Calibrating Click-Attributed Purchases in Performance Display Advertising，來自http://A9.com

3）市場度量和優化機制。

這方面的工作比較雜，來自多家公司，從中也可以看到ad這個領域不同的角色其關注和優化角度百家爭鳴。

相關論文如下：

Blacklisting the Blacklist in Digital Advertising，來自Dstillery

MM2RTB: Bringing Multimedia Metrics to Real-Time Bidding，來自National University of Singapore，這是唯一一篇純學術界的工作

Profit Maximization for Online Advertising Demand-Side Platforms，來自adobe&yahoo

Anti-Ad Blocking Strategy: Measuring its True Impact，來自adobe

Cost-sensitive Learning for Utility Optimization in Online Advertising Auctions，來自facebook，Criteo和google。

Attribution Modeling Increases Efficiency of Bidding in Display Advertising，來自Criteo

八KDD cup

背景：

關於智慧交通領域的經驗積累，阿里雲早在2015年已經開始有所沉澱。浙江省交通運輸廳於15年4月公布了一項新的試點項目，將高速公路歷史數據、實時數據與路網狀況結合，基於阿里雲大數據平台，預測未來一小時內的路況。結果是，實時路況監測成本下降了 90%，未來路況預測準確率在 91%以上。

2016年9 月，在雲棲大會上發布的「杭州城市大腦」的交通模塊在蕭山區市心路投入使用，其首要目的是解決城市發展中的交通問題。試驗數據顯示：通過智能調節紅綠燈，道路車輛通行速度平均提升了 3% 至 5%，在部分路段有 11% 的提升。正如發布時王堅博士所言：世界上最遠的距離是紅綠燈與交通監控攝像頭之間的距離，他們雖然在同一根杆子上，但是從來沒有通過數據被連接過。因此，打通數據並在海量、實時數據分析處理的基礎上做出智能決策，是城市大腦的基本定位。

賽題：

基於以上阿里雲在城市大腦、智慧交通中的豐富積累，在今年的KDD CUP賽題設置中，阿里雲選擇了交通領域中高速公路收費站相關問題作為任務：

Task 1: To estimate the average travel timefrom designated intersections to tollgates（預測車輛從路口到收費站的平均用時）

Task 2: To predict average tollgate trafficvolume（高速收費站車流量預測）

這兩個任務是基於智慧交通信號燈，其邏輯如下：

根據以上步驟，預測效果如下：

賽況

當中國擁堵問題出現在國際頂賽中，吸引了全世界的數據演算法專家紛紛來參賽。據悉，本次KDD CUP一共有3582支隊伍參賽，覆蓋全球48個國家，731座高校，參賽隊伍有來自微軟、因特爾等知名互聯網企業，也有來自清華大學、波士頓大學等高等學府。對此KDD CUP Chair表示不可思議，這是KDD CUP史上規模最大的比賽，他表示這次的比賽很成功，來自世界各地的選手能夠通過這次的比賽了解中國的交通問題，整個比賽running的很順利，同時也感謝阿里雲天池平台的平台支持。

在KDD CUP公布獲獎名單時，讓人意外的是，本屆大會獲獎名單被中國選手包圓，更有一個名為Convolution的團隊取得雙料冠軍。在現場採訪到為什麼可以取得如此成績的時候，其隊長表示團隊成員都是從事機器學習工作，有技術積累，日常的工作與學習就是與比賽相似的內容，此外團隊合作很默契，從開始就討論列出來這類問題可能有突破的點，分工逐步實驗，後面又能比較快提出應對具體問題的方案，最後團隊有著豐富的參賽經驗。

2017的KDD CUP，有收穫也有喜悅，阿里雲天池不僅在國際舞台上show了一把中國的交通難題，更是向全世界展示了中國技術的力量。

九 城市計算研究

城市計算研究的提出

隨著可移動感知設備和雲計算的普及，人類可以實時感知城市活動和狀態並進行存儲。在這樣的背景下，學術界提出了城市計算的概念並將其定位於致力從計算機和數據科學的角度理解和解決城市問題。2014年的綜述研究介紹城市計算包括數據獲取和存儲、數據聚合、多源數據融合和演算法模型設計四個階段；同時研究指出城市計算旨在解決交通擁堵、能源消耗、環境污染和其他有關城市規劃、社會經濟發展及安全等方面的問題。在2017年KDD會議上，城市計算Tutorial環節詳細介紹了學術界如何探索利用大數據和人工智慧技術反哺城市建設。下面，我們將通過幾個典型研究示例城市計算的研究思路和方法。

綜述研究：

https://www.microsoft.com/en-us/research/publication/urban-computing-concepts-methodologies-and-applications/

Tutorial：http://uctutorial.chinacloudsites.cn/

城市計算研究示例

2.1 基於共享單車軌跡的自行車道規劃

Planning Bike Lanes based on Sharing-Bikes』 Trajectories : https://www.microsoft.com/en-us/research/wp-content/uploads/2017/06/main.pdf

（1）研究問題

隨著共享單車在城市的大量投放，在短距離出行時人們越來越多選擇騎車出行，但中國城市自行車道規劃不足，大多數時間自行車和機動車同時行駛在一條幹道上，有時自行車甚至會佔據人行專用道，不僅帶來了出行安全隱患而且導致了嚴重的交通管理問題。所以作者期望從單車出行軌跡中挖掘出和需求高度契合的自行車道規劃路徑，推動和優化規劃工作。

那作者是如何將這個規劃問題演算法化的呢？

（2）演算法設計

作者將城市抽象成一個圖結構，每條路段構成圖的邊，每兩條邊之間的節點為圖的頂點，所需規劃的自行車道就是圖中滿足出行需求和規劃限制條件的邊的集合。

出行需求被設計為體現在兩個方面

1. 出行次數需求：計算通過邊的軌跡數量。軌跡數量越多，規劃價值越高。

2. 出行體驗需求：單車能夠連續通過被規劃為自行車道邊的長度總和。總和越長，規劃價值越高。

規劃限制條件文中考慮有兩點：

1. 施工點的數量限制：一般政府僅允許在k個不相連的區域同時翻新車道。

2. 成本限制：財政撥款限制。每條路段翻新為自行車道的成本各不相同，決定於地理屬性。

所以自行車道規劃問題就被定義為圖搜索問題，搜索目標是在滿足規劃限制條件下搜索能夠帶來最大規劃價值邊的集合。具體的公式請參見原文。

（3）演算法求解

但這個搜索問題是個NP-hard問題，所以作者設計了一套啟發式貪婪演算法：

Step 1. 對歷時一個月的3971輛共享單車軌跡數據進行聚類，挑選具有最高價值的邊為搜索起點。

Step 2. 從和搜索起點地理相連的路段中挑選在本次搜索中提升區域整體單成本價值最高的路段加入到最優邊集合中。

Step 3. 迭代直至最優邊集合中所有的成本達到財政撥款的額度。

小結：

本研究從數據出發，探索利用單車軌跡數據挖掘城市自行車道規劃方案，具有很強的前瞻性。但其現實可應用性有待打磨，從數據中挖掘的路徑可能並不適合設置自行車道，因為道路的寬度可能不足，也可能因為道路在城市交通運輸中作為主要幹道，需要保證機動車通行和減少安全風險，這些軟性的因素都可以被加入到演算法模型中，求得一個更符合實際的可行解。

2.2 危險品運輸對城市安全影響評估

No Longer Sleeping with a Bomb: A Duet System for Protecting
Urban Safety from Dangerous Goods: http://www.kdd.org/kdd2017/papers/view/no-longer-sleeping-with-a-bomb-a-duet-system-for-protecting-urban-safety-fr

受啟發於天津港危險品倉庫爆炸事件，作者基於城市危險品運輸車軌跡和人群密度量化每個小區的風險值，挖掘常發性風險小區集合，並基於運輸車行駛方向找到高風險小區路徑，支持政府安全防控策略的制定。研究的主要步驟如下圖所示，詳細內容請參看原文。

最後作者提到，北京政府基於本文的研究結果決定改造北京美食街危險品運輸管道，因為美食街是火鍋店和人群都很密集的地方，安全風險值很高。

2.3 城市小區劃分

Segmentation of Urban Areas Using Road Networks: https://www.microsoft.com/en-us/research/publication/segmentation-of-urban-areas-using-road-networks/

2.2研究中的作者將路網劃分成大小相等的網格，這樣的劃分雖然便於學術研究，卻無法體現小區實際的功能意義，所以有研究學者利用圖像處理中形態學處理方法對路網點陣圖進行除噪和平滑處理，從而將道路相交組成的區域劃分為小區，和現實世界的意義更貼近。

城市計算Workshop單元研究集錦

Workshop專場: http://urbcomp.ist.psu.edu/2017/accept.html

KDD2017舉辦了城市計算的Workshop專場，所有的研究均可免費下載，有興趣的同學可以深入挖掘下。其中有篇文章已經嘗試將深度強化學習引入到區域信號燈協同控制領域，研究方向和實際應用需求完全相符，但作者過於簡化動作空間，同時假設用於表示狀態空間的信息輸入是現實可收集的，最後基於簡單的路口結構和模擬的OD矩陣用模擬器訓練模型，和實際應用還有較大的差距，但隨著模型設計更加符合路口實際結構，視頻殘採集數據更完全，相信深度反饋學習在信號控制領域也可以取得突破。

總結

我們生活的城市每天在產出大量的數據：人群移動軌跡、社交媒體輿論、公共出行記錄和環境檢測指標等，雲存儲和雲計算使得我們可以實時記錄、分析城市運行狀態，解決城市在快速發展中遇到的問題。城市計算研究領域給我們提供了一個很好的思路，但由於各行業數據粒度（時間和空間）不同、數據處理方式不同、業務需求也不相同，所以很難有一個統一的解決方案，而且這些解決方案在最後真正落地時需要和業務進行深入的溝通：哪些信息可以來源於數據，哪些信息則需要管理經驗及策略的指導。

十 KDD China （傑銘）

KDD 2017的首日下午，大會特別為SIGKDD China舉行了中國數據挖掘會議（Data Science @China），吸引了眾多聽眾參與。這是SIGKDD繼2016年後第二次舉辦中國專場。也是現場除了印度專場之外，另外一家完全為了一個國家舉辦的專場會議。會議在KDD China秘書長、微軟亞洲研究院研究員鄭宇博士的主持下進行。香港科技大學的楊強，羅格斯大學的熊輝，微軟亞洲研究院的鄭宇，今日頭條AI實驗室的李磊，滴滴出行研究院的副院長葉傑平，西蒙弗雷澤大學的裴健，以及清華大學的唐傑和崔鵬分別分享了各自最新的研究成果。

羅格斯大學教授、百度高級顧問熊輝：AI人才的機遇與挑戰

熊輝教授在本場演講中為我們描述了AI人才當下面臨的機遇與挑戰。他指出，傳統工作環境中任勞任怨、按部就班的「員工」在當前AI發展中會被一步步淘汰，即便是極具領域知識的「人才」也不再是行業的寵兒。他認為，當前AI業界最歡迎的是具備「人才」的專業技能、又具備領導力的「精英」。就此，熊輝給公司人才管理提出了幾點建議：注重打磨公司文化、對人才供求做出正確的預見、實現職位描述精準化等等。當然，這裡我們並不僅僅要討論這個方法論。作為合作者，熊輝教授在本次KDD發表了8篇文章，下面我們選取一篇進行學習。

Prospecting the Career Development of Talents: A Survival Analysis Perspective

本文的貢獻在於：

1）研究的方向是人才職業生涯路徑建模，重點放在人才管理的兩個問題上，即：營業額與職業發展。提出了一種新的生存分析方法來建模：利用排序約束公式基於多任務學習建立員工的職業發展道路。

2）對現實世界的人才數據進行廣泛的評估以證明生存模型的效率，

3）預測營業額和員工的職業發展。

本文提出了兩種模型：