空間位置的關聯分析及其向量化表示方法①

張 舒,郭旦懷,周純葆,李薰春,靳 薇

1(中國科學院 計算機網絡信息中心,北京 100190)

2(中國科學院大學,北京 100049)

3(國家廣播電視總局廣播電視科學研究院,北京 100866)

4(北京市科學技術研究院,北京 100089)

5(北京市新技術應用研究所,北京 100094)

空間位置作為重要的空間特征,常用于目的地預測與推薦,城市功能規劃,交通管控系統,交通流量預測、位置分類等應用.傳統的空間位置表示方法與空間向量化表示方法,常將其經緯度坐標與興趣點(Points Of Interest,POI)信息將空間位置映射為 ID 類型,其中經緯度用來精確地描述空間位置,興趣點為空間位置增添了大量屬性特征.但是,傳統的空間位置表示方法只保留了自身經緯度與POI 的信息,缺少了空間位置間隱含的時空關聯信息,難以理解空間位置和推斷空間位置間的關聯關系.

融合空間位置的時空關聯信息與其周邊POI 信息,將有助于提高空間向量的表達效果.居民出行軌跡數據能夠為結合兩種信息的空間分析提供可靠的數據支持.居民的出行軌跡可體現居民的出行模式與活動規律,同時也反映出空間位置之間的關聯,是制定城市交通管理方案的關鍵.隨著GPS 定位技術的快速發展,可收集到大規模軌跡數據,使得軌跡數據能夠被用于更加細粒度地分析空間位置的時空關聯關系.當今的大規模軌跡數據,包括機動車軌跡與非機動車軌跡,已能夠支持機器學習、深度學習等對于數據量的需求,并且能夠為空間位置及其關聯關系的理解、表示與推理學習提供可能性.

另一方面,隨著深度學習在自然語言處理、計算機視覺等領域的迅猛發展,研究者已在空間分析中引入了深度學習方法[1].近些年提出的空間上下文理解模型中,考慮空間位置與其臨近位置之間的關系,結合自然語言處理中的詞向量模型,使用神經網絡將詞生成固定長度的向量表示,該詞向量表示能包含該詞的語義與上下文信息,最終生成結合空間鄰接關系的空間位置向量化表示[2,3].但這些方法僅關注了空間的靜態特征,尚未考慮到居民在空間之間的軌跡移動,從而缺失了居民出行的時空模式關聯信息.

在使用深度學習技術處理復雜的關聯關系時,一個有效的模型是圖神經網絡[4].圖神經網絡因其能夠處理圖結構形式的數據引起廣大關注[5].借助圖神經網絡算法能夠為更加復雜的圖結構中的節點生成低維向量表示,該向量表示既包含了節點的類別特征,又聚合了節點在復雜圖網絡中的鄰域特征[6].交通網絡以圖結構形式存在,因此,交通網絡常使用圖神經網絡解決流量預測問題[7,8]與出發地、目的地預測[9]等問題.圍繞空間向量化表示任務,DeepMove 基于出租車軌跡數據,使用圖神經網絡中的隨機游走方法與Word2Vec 方法,為交通網絡中的POI 節點生成含有鄰域關聯信息的向量化表示[10].但是DeepMove 僅使用了簡單的圖神經網絡,未使用節點自身特征,難以聚合鄰域節點特征.另一方面,這些研究只基于單一的軌跡數據,而沒有考慮不同出行方式之間的聯系.例如,居民從住所前往公司,通常會產生從住處到地鐵站的騎行軌跡、從地鐵站到公司所在地的地鐵軌跡、公交站點之間的公交軌跡,通過綜合這些軌跡才能發現住處和公司所在地之間存在的軌跡關聯,而對不同類型的軌跡分別處理則會遺漏大量信息.

本文提出基于圖神經網絡的空間位置向量化表示方法,綜合公交線路軌跡、地鐵線路軌跡與大規模共享單車軌跡數據構建多源交通網絡.同時,針對不同源交通軌跡數據的集成,本文提出一種針對不同類型軌跡數據的集成方法:將長距離出行與短距離出行進行匹配連接,以更全面地覆蓋不同位置之間的空間關聯.使用本文方法生成的空間位置的向量化表示,能夠綜合空間特征、鄰域特征與時空關聯特征.相較于其他已有方法,本文提出的空間向量化表示方法能夠學習到空間位置的關聯關系.

本文首先圍繞著不同類型軌跡數據的網絡構建展開討論;其次介紹融合POI 與軌跡信息的空間向量化表示方法;然后設計實驗以驗證本文提出的空間向量化表示方法的有效性;最后討論針對空間位置向量化表示任務,有待探索的研究方向.

1 多源交通軌跡數據網絡構建

1.1 多源交通軌跡數據

相較于公交車與地鐵等交通方式,近年來共享單車的流行為人們的出行方法提供了新的選擇.共享單車因其更加靈活與便捷的特點,使得共享單車軌跡數據相較于其它交通軌跡數據,具有覆蓋范圍更廣,數據規模更大,采樣密度更高,位置精度更高等特點.由于共享單車在城市交通中的占比逐步增大,能夠從一定程度上更加細粒度地描述城市居民的短距離出行模式,因此本文采用公共交通路網數據(包括公交線路與地鐵線路),與共享單車軌跡數據相結合的方式,共同構建大規模交通網絡.融合了共享單車軌跡數據與公共交通線路的交通網絡能夠更完整地體現居民的出行模式.

為了解居民的短距離出行模式,本文統計了共享單車軌跡數據分布.居民在工作日與非工作日一天內不同時間段的出行分布圖如圖1所示,可發現在工作日期間的早晚上班高峰時刻,居民對于共享單車出行的需求非常大;周末的出行需求量較為平均.此外,在剔除了異常軌跡距離后,騎行軌跡距離分布圖如圖2所示.可發現,當出行距離小于2 公里時,居民更傾向選擇共享單車出行.

圖1 不同時段內共享單車出行量分布圖

圖2 騎行軌跡距離分布圖

對共享單車軌跡數據進行分析后可發現,利用共享單車軌跡數據與公共交通路網數據相結合的方式構建大規模交通網絡,融合多種交通方式的出行軌跡,能夠覆蓋居民針對不同出行需求與出行距離的交通軌跡.

目前通過互聯網開源數據,可獲取到大量免費的共享單車軌跡數據以供研究者使用.本文使用摩拜共享單車開源數據集,涵蓋了北京市居民于 2017年5月14日至2017年5月21日的騎行軌跡,樣本量共計3 214 096 條.為避免異常數據的影響,剔除了騎行距離大于5 公里的軌跡.此外,通過數據爬取技術,獲取北京市公共交通路網數據,具體包括公交車線路數據與地鐵線路數據

1.2 集成不同類型軌跡數據的網絡建模

為綜合不同類型的軌跡數據,識別居民完整的出行模式,本文將長、短距離出行軌跡進行匹配連接.對不同類型軌跡數據的匹配方法如下:

第1 步.使用GeoHash[11]技術將共享單車軌跡數據與公交交通路網數據中的地點經緯度向量成固定長度的字符串.該字符串由空間位置的經緯度向量得到,并且其長短可用于劃分空間位置的大小.本文具體使用長度為7 位的GeoHash 字符串.

第2 步.使用共享單車軌跡中的出發地與目的地作為節點,軌跡作為邊,標記邊的類型為共享單車出行,居民在此出發地與目的地的出行次數作為邊的權重,以構建大規模交通網絡.

第3 步.針對公共交通路網數據,以公共交通站點作為節點,線路作為邊,依據公共交通的類型作為邊的類型,構建大規模交通網絡.

第4 步.通過以上步驟,合計產生 10.5 萬個節點.通過百度地圖開放平臺,獲取交通網絡中的每個節點的POI 信息,經過one-hot 處理后,作為節點的屬性特征;獲取每個節點的交通擁堵信息,經過離散化處理后,作為節點的擁堵特征.

圖3為使用該方法對長、短距離出行軌跡進行匹配的一個示例,例如從圖中A-B,B-C,C-D 分別為某居民從住處到公交站的騎行軌跡,公交運行軌跡,從公交站到公司的騎行軌跡,通過匹配以上3 段軌跡可識別出A 到D 點的實際關聯.

圖3 長、短距離出行軌跡匹配示例

2 融合POI 與軌跡信息的空間向量化方法

本章節首先給出交通網絡的形式化定義;然后介紹本文提出的POI 與軌跡信息融合模型;最后說明基于該模型的空間向量化表示方法.

2.1 形式化定義

文中常見符號的定義如表1所示.使用G=(V,E)表示交通網絡,n=|V|表示節點的個數.使用X∈Rn×D表示節點特征矩陣,xv表示節點v的特征,其中xv∈RD,?v∈V,表示矩陣X的第v行第j列,即節點v的第j個 特征.G與X作為圖神經網絡模型的輸入.

表1 符號定義

2.2 POI 與軌跡信息融合建模

為了在神經網絡模型中結合空間位置節點的POI 信息與軌跡關聯信息,本文基于GraphSAGE 模型[12]提出融合建模的方法.GraphSAGE 模型能夠通過對目標節點的鄰居進行隨機采樣得到子圖,再對子圖進行卷積,替代了直接對全圖進行卷積的方式,大大降低了計算和內存的壓力.此外,GraphSAGE 模型通過學習聚合函數(aggregator)的方式,把鄰居節點的特征聚合到中心節點自身.當學習得到聚合函數后,聚合函數能夠泛化到新的節點或者新的網絡上,即使是在訓練過程中出現未知的節點,模型也能推斷出其向量化表示.這一做法替代了直接學習網絡節點的向量化表示,泛化能力更強,是一種歸納式(inductive)學習算法.

基于GraphSAGE 的向量化表示學習方法在每次迭代中進行以下3 個步驟:

第1 步.對圖中的每個節點采樣固定數量的鄰居節點作為該節點的鄰居節點集合;

第2 步.通過模型學習的聚合函數(aggregator)對采樣得到的鄰居節點集合進行聚合,以把鄰居集合節點的特征信息聚合到中心節點上,得到新的節點向量;

第3 步.通過聚合鄰域特征得到的節點的向量向量化表示用于損失計算,更新權重矩陣W.

算法1 為具體的向量化學習方法.在算法1 中,K為圖卷積的層數,表示每個節點聚合K階鄰居.在外層循環的第k次迭代中,對于每個節點v首先通過聚合函數Agg來對節點v的鄰居節點的k-1 層embedding向量進行聚合,得到節點v第k層的鄰居聚合embedding,再將節點v的k-1 層得到的向量拼接起來接入全連接網絡層,最終得到節點v在第k層的向量化表示.

算法1.基于POI 與軌跡信息融合建模的空間向量化表示算法G=(V,E) Wk,?k∈K輸入:圖 ;節點特征矩陣 X;圖采樣深度 K;權重矩陣 ;非線性激活函數f;聚合函數Agg;鄰居節點采樣函數S.φv,?v∈V輸出:節點的向量化表示步驟:h0v←xv_,?v∈V for k=1···K do:for v∈V do:hk(S(v))←Agg(h(k-1)i,?i∈S(v))okv=CONCAT(h(k-1)v,hkS(v))hkv←f(Wk·okv)end hkv ← hkv||hkv||2,?v∈V end φv=hKv,?v∈V

2.3 空間向量化表示學習方法

已有的Place2Vec 研究通常使用POI 的語義特征與空間特征以生成POI 的向量化表示.但具體的某個空間位置通常存在多個POI,例如在商場與餐廳,住宅區與超市大多會同時出現,難以使用單獨的POI 來表示空間位置.本文提出的方法通過構建大規模多源數據交通網絡與POI 與軌跡信息融合方法直接得到細粒度空間位置的向量化表示.基于章節1.2 中使用公共交通路網數據與共享單車軌跡數據構建的大規模交通網絡中,邊具有各自的類型與權重,各節點的鄰居數分布不均勻.因此,針對空間位置向量化表示任務,須對圖神經網絡中的采樣方法與聚合方法加以修改,以適應交通網絡的特性.具體的,考慮到使用多源數據構建的交通網絡的邊都具有類別、權重等特征,并且根據圖2中對共享單車軌跡數據的統計分析,可發現居民在短距離出行時更傾向于選擇共享單車出行.因此本文提出一種基于出行距離長短的采樣方法,示意圖見圖4(a).對目標節點v的第k層鄰居采樣過程中,當k=1 時,即一階采樣函數,優先采樣邊類型為共享單車軌跡的鄰居節點,當k=2 時,即二階采樣函數,優先采樣邊類型為公共交通線路的鄰居節點.

經過采樣函數后,節點的鄰居節點集合是無序的,因此聚合函數不僅需要有很強的表征學習能力,還具有對稱性(symmetric)要求,即函數的輸出與輸入聚合函數的節點順序無關.本文使用文獻[12]中提出的GCN aggregator 作為聚合方法,將不同層級的鄰域中的鄰居節點的特征聚合起來,并且將聚合后的鄰域節點特征與目標節點特征拼接結合后,傳遞到全連接網絡中.其中節點的聚合過程如圖4(b)所示.利用圖神經網絡的反向傳播機制,最終得到節點的向量化表示.

圖4 交通網絡中采樣與聚合操作示意圖

為了在無監督學習過程中得到更有效的空間位置向量化表示,使用圖神經網絡中的無監督損失函數,該損失函數的優化目標是最大化正樣本的概率,使得鄰居節點的向量化表示更加相近;同時最小化負樣本的概率,使得沒有共同交點的節點的向量化表示相異:

式(1)中,zv(v∈V)為圖神經網絡的輸出,即空間位置的向量化表示;i為與v共同出現在一組隨機游走上的節點;in～pn(i)表示in服從對i的負樣本采樣分布;Q定義為負樣本的個數.對此,使用隨機梯度下降學習方法與Mikolov 等[13]提出的負采樣學習優化算法,用于更新圖神經網絡的權重矩陣Wk(?k∈K)與聚合函數中的參數.當k=2,使用GCN 聚合方法,網絡中節點規模為104左右時,本文提出方法的整體參數規模為105左右.此外,由于空間位置包含多個POI,可通過空間位置的向量化表示經過加權聚合操作后得到POI 的向 量化表示.具體的,POI 的向量化表示pi可定義為:

wij為位置向量 φj在pi中的權重.當使用平均權重時,wij=1.其中,本文使用tf-idf 統計方法計算權重wij[14],用以度量位置與POI 的相關程度.

3 實驗分析

為了驗證本文提出的空間位置的向量化表示方法的有效性,我們分別對空間位置向量化表示、由空間位置向量化表示加權聚合得到的POI 向量化表示進行評估.為了直觀地理解空間位置的向量化表示,部分向量聚類結果采用可視化方式展現.

3.1 評價指標

使用空間位置向量化表示間(vi,vj)的Cosine 距離[15]以定義空間位置的相似度Sspace:

空間位置向量化表示的距離dplace則為:

相似的,由空間位置向量化表示經過加權聚合操作得到的POI 向量化表示,其相似度Spoi定義為POI向量化表示的Cosine 距離.此外,使用輪廓系數評估向量化表示的聚類結果[16].輪廓系數s(i)為:

其中,a(i) 表示樣本i到同簇其他樣本的平均距離;b(i)則為樣本i到其他簇的最小平均距離;s(i) 的值域在[-1,+1]之間.a(i) 度量類內距離,b(i) 度量類間距離.當a(i) ＜＜b(i) 時,即類內距離遠小于類間距離,則s(i)接近于1,表明聚類效果愈好.反之,當a(i) ＞＞b(i)時,即類內距離遠大于類間距離,則s(i) 接近于-1,表明聚類效果愈差,樣本i更應該被分類到其他簇.本文使用平均輪廓系數以評估整體樣本的聚類結果.

3.2 實驗結果與分析

3.2.1 空間位置關聯分析

基于使用本文提出的向量化表示方法所生成的128 維POI 向量化表示,計算POI 之間的相似度Spoi.POI-POI 相似度矩陣如表2所示.具體的,可發現寫字樓與企業園區,科研機構與高等院校,住宅區與購物中心的關聯度更高,其向量間的Cosine 距離也較小.此外,由于使用多源交通數據構建網絡,也能使得向量含有居民行為模式特征,例如機場的POI 向量與寫字樓、高等院校的POI 向量的距離較小,而與超市、公園的POI 向量的距離較大,表明其關聯程度較低.POI 關聯性結果可驗證本文提出的向量生成方法符合POI 之間的關聯程度愈高,其間的Cosine 距離愈小這一規律,表明使用本文方法能夠得到有效且可信度高的向量化表示.

為對比驗證本文提出的向量方法的有效性,將本文方法生成的POI 向量與其他的已有方法進行對比.對比方法分別包括DeepMove[10],Node2Vec[17],其POI 的相關性關聯熱力圖如圖5所示.對比發現,使用本文方法得到的向量能夠關聯POI 的空間位置特征與居民的行為模式特征;POI 向量間的相似度基本符合先驗知識,并且區分度高,優于已有方法.

表2 POI-POI 相關性(Cosine 距離)矩陣

為驗證本文提出的多源數據構建大規模交通網絡方法與交通網絡采樣方法的有效性,設置多組對比實驗分別對模型、交通網絡數據源、采樣方法加以評估.基于K-means 聚類方法對POI 向量進行聚類操作,其超參數K為聚類類目,可表征為POI 的類目.在已有基于興趣點(POI)大數據的研究綜述中表明沈陽市有21 個POI 類目[18],由于POI 類目受多種人為主觀分類因素影響,因此可認為K值應在 5～20范圍內浮動.為避免聚類類目K值選取不當對實驗結果造成的干擾,本文將K分別設定為5、10、15、20 以評估不同POI 聚類類目下的聚類效果,其中K值越大,類別越細致.并且每個K值分別進行5 次實驗取平均值.使用平均輪廓系數對POI 向量聚類效果進行評估.表3給出了使用多種對比模型的實驗結果,其中涉及的對比方法均使用融合了長、短距離軌跡的交通網絡.實驗結果表明,當POI 聚類類目K=15、K=20 時,由于本文提出方法相較于對比方法,既能夠聚合了鄰居節點的信息,又能夠利用空間位置自身的特征,改善DeepMove[10]與Node2Vec[17]方法僅使用網絡中的節點序列特征這一問題,因此當POI 分類類目較細致時,使用本文提出方法生成的向量能夠保留更加細粒度的特征,其聚類效果優于對比方法.表4對比了不同采樣方法的實驗結果,實驗結果表明在多數K值下,使用本文提出的路網采樣方式生成的向量,其聚類效果都優于使用圖神經網絡中隨機采樣方式.表5對比了不同數據源的實驗結果,實驗結果表明,當K值較小時,使用代表長距離出行的公共交通線路所構建的交通網絡,生成的向量聚類效果更好,但當K值逐步增大時,使用長、短距離融合的交通網絡所生成的向量,其聚類效果比較穩定,當K=10、K=15 時,優于僅使用長距離出行軌跡或短距離出行軌跡構建的交通網絡.因此可推斷得出,當POI 分類較為粗泛時,長距離軌跡能區分不同功能區域,因此長距離軌跡構建的網絡效果較好,當POI 分類較為細致時,融合長、短距離的出行軌跡能夠捕捉到更加細粒度并且相對完整的出行模式,因此構建的交通網絡所涵蓋的信息更加豐富,效果更優.

表3 不同向量化方法的實驗結果對比(輪廓系數)

表4 不同采樣方法的實驗結果對比(輪廓系數)

表5 不同數據源的實驗結果對比(輪廓系數)

3.2.2 空間位置聚類分析

首先,利用K-means (K=8)對空間位置向量進行聚類分析,其中每個類別的輪廓系數如圖6(a)所示.為了更加直觀的反映聚類結果,使用t-SNE[19]方法將空間位置向量從128 維空間降維至低維空間,降維后的空間向量化表示的聚類結果如圖6(b)所示,不同的顏色表明不同的類.本文結合低維空間向量化表示的可視化映射圖作為一種直觀的評價方式.通過觀察圖6可發現,使用本文提出的空間向量化表示方法得到的空間位置向量,映射在低維空間后,有較為明顯的類間邊界,能夠驗證本文提出的空間向量化表示方法的有效性.

圖6 聚類分析結果

4 結論與展望

本文提出了一種基于圖神經網絡的空間向量化表示方法.基于共享單車軌跡數據與公共交通線路數據,將長、短距離出行軌跡進行匹配連接,構建大規模交通網絡,該交通網絡能夠覆蓋多種出行模式.提出了融合POI 與軌跡信息的空間向量化表示方法,綜合位置自身的空間特征與其鄰域的特征,并優化節點采樣方法,提高了空間向量化表示的表達能力.以北京市的共享單車軌跡數據與公共交通路網數據為實例,經驗證本文提出的空間向量化表示方法能夠綜合空間特征、鄰域特征與居民出行模式,該向量可作為空間特征用于交流流量預測,交通調度與管理,地理畫像,位置推薦等實際應用中.

在未來的工作中,將進一步研究融合多源數據,例如出租車,網約車數據,以構建大規模的交通網絡.以及當網絡規模增大時,如何提升模型性能,使其能夠處理更大規模的交通網絡.