城市多源數據投放位置推薦算法的研究

王蕾 王亮 關如君

摘要：本文融合城市出租車交通數據、城市路網數據以及城市興趣點（Point of Interest，POI）數據，通過刻畫用戶出行的潛在意圖，提出了面向潛在目標用戶的戶外廣告影響力量化模型;同時基于城市商業基礎設施與公共交通設施分布情況，設計了戶外廣告在不同空間區域投放的定價策略。在此基礎之上，形式化定義了廣告影響力-投放成本兩優化目標的戶外廣告精準投放位置推薦問題，通過對傳統G-Skyline查詢算法的改進，基于最大支配數計算以及高效剪枝策略設計了位置推薦查詢算法。在真實數據集上的實驗結果驗證了本文所提相關方法的有效性。

關鍵詞：戶外廣告投放;Skyline查詢;移動軌跡數據

中圖分類號：TP391 文獻標識碼：A 文章編號：1007-9416（2020）02-093-02

1 戶外廣告影響力傳播及定價模型

1.1 用戶出行意圖刻畫

在出租車軌跡數據中，行程的軌跡T由位置序列 表示，軌跡位置由{lon， lat}表示。通過行程T的目的地附近的POI類型建立向量空間模型，以刻畫乘客的出行意圖，其中的表示POI類別為i的概率。

目的地為路段r的所有行程，它們的出行意圖向量分別為，那么在路段r上的出行意圖向量可表示為：

本文采用廣告投放位置的乘客出行意圖分布向量和廣告本身的內容主題向量之間的匹配程度來量化表征廣告投放的精準程度：

1.2 戶外廣告傳播影響力模型

基于出租車的行程軌跡，本文綜合車流量和車速兩方面因素定義了路段r上的廣告曝光強度為：

其中c1和c2分別是fw和v的調節參數。

當給定一個廣告查詢q，那么q在路段r上的傳播影響力可以用r上的廣告曝光強度和對應的廣告匹配度來量化，具體公式可表示為：

1.3 戶外廣告定價機制

本文從多個不同的影響因素出發綜合構建了戶外廣告定價機制。房地產價格與人口密度具有正相關性，用PriceEst（r）來表示道路r附近小區的房產價格;城市道路上的交通設施情況，主要體現在公交站數量、途徑的公交車線路數量以及與最近地鐵站的距離上。定義路段r上的廣告投放價格。房產價格是實際的價格指標，所以以房價為基礎構建線性模型：

其中ω和b受到路段r的其他條件限制。ω值受到交通環境的影響：

其中和分別表示最大公交站數和最大公交線路數量。取，表示與地鐵站的距離上限取5000米。公交線路數量和公交站數量越大則ω值越大，而與地鐵站的距離越小則ω值越大，ω值一般大于等于1。j是用來調節ω值范圍的參數，范圍在（0，1）之間。將和線性組合得到：

其中出租車的車流量和商業得分帶來的價格增量分別為和，a1和a2為調節參數。

2 基于G-Skyline的戶外廣告位置推薦

2.1 戶外廣告查詢問題

定義1（戶外廣告推薦）：給定一個廣告查詢q和城市范圍內的位置集合。戶外廣告位置推薦問題是在S中查找一組位置進行廣告投放。具體的需要在所有的位置組合中搜索滿足目標函數的最優組。目標函數如下：

其中表示G的整體成本，表示G的整體影響力。戶外廣告位置推薦問題希望能夠同時兼顧廣告傳播的影響力和投放成本。

2.2 改進的G-Skyline查詢

定義2（支配數）：設，ri的支配數表示ri所支配位置的數量，用表示。G的支配數表示G中所有位置支配數之和，表示為。

在位置集合S的Skyline層中，低層位置至少在一個維度上優于高層，同一層位置的支配數越大，則其成本和影響力越均衡，更適合被選擇作為廣告投放的目標位置。改進的G-Skyline查詢算法只需要計算得到支配數最大的G-Skyline組，所以在Skyline層的前k層中，如果有，則可以將ri從有DSG中刪除，達到對DSG進行簡化的目的。

3 實驗評價

本節對所提出的方法在真實數據集上進行實驗仿真以驗證算法的相關性能。所采用的基準方法包括：（1）加權法WS;（2）傳統的G-Skyline查詢方法。

加權法WS主要是采用加權思想將兩個目標轉換為單目標問題求解，把問題簡單處理為求最大值的問題，在候選的位置集合中直接選擇目標函數值最大的位置作為廣告查詢q的投放位置。所以目標函數可以定義為：

其中，h1和h2分別是和的調節參數，用來調節兩者的權重。

當選擇不同的k時，3種算法的耗時對比如圖1所示，其中改進的G-Skyline查詢算法在時，隨著k值的不斷增大，其運行效率上的優勢越來越明顯。由于G-Skyline組不能被其他的組所支配，所以如圖2，圖3所示G-Skyline查詢算法的平均影響力優于WS算法。

4 結論

本文提出了改進的G-Skyline查詢算法，該算法優先計算支配數最大的G-Skyline組，最大程度減少了廣告投放位置的候選組合。

Research on Urban Multi-source Data Placement Recommendation Algorithm

WANG Lei ，WANG Liang，GUAN Ru-jun

（Department of? Electrical and Control Engineering， Xian University of? Science and Technology， Xi'an? Shaanxi? 710054）

Abstract：This paper combines urban taxi traffic data， urban road network data and city point of interest （POI） data. By portraying the potential intention of user travel， this paper proposes an outdoor advertising influence power model for potential target users. At the same time， based on the distribution of urban commercial infrastructure and public transportation facilities， the pricing strategy of outdoor advertising in different spatial regions was designed. On this basis， this paper formalizes the recommendation of outdoor advertising precision placement for advertising influence-delivery cost optimization goal. By improving the traditional G-Skyline query algorithm， the location recommendation query algorithm is designed based on the maximum dominance calculation and efficient pruning strategy.

Key words：outdoor advertising; G-Skyline query; trajectory data