王蕾 王亮 關(guān)如君

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

關(guān)鍵詞：戶外廣告投放;Skyline查詢;移動軌跡數(shù)據(jù)

中圖分類號：TP391 文獻(xiàn)標(biāo)識碼：A 文章編號：1007-9416（2020）02-093-02

1 戶外廣告影響力傳播及定價(jià)模型

1.1 用戶出行意圖刻畫

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

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

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

1.2 戶外廣告?zhèn)鞑ビ绊懥δＰ?/p>

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

其中c1和c2分別是fw和v的調(diào)節(jié)參數(shù)。

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

1.3 戶外廣告定價(jià)機(jī)制

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

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

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

其中出租車的車流量和商業(yè)得分帶來的價(jià)格增量分別為和，a1和a2為調(diào)節(jié)參數(shù)。

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

2.1 戶外廣告查詢問題

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

其中表示G的整體成本，表示G的整體影響力。戶外廣告位置推薦問題希望能夠同時兼顧廣告?zhèn)鞑サ挠绊懥屯斗懦杀尽?/p>

2.2 改進(jìn)的G-Skyline查詢

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

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

3 實(shí)驗(yàn)評價(jià)

本節(jié)對所提出的方法在真實(shí)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)仿真以驗(yàn)證算法的相關(guān)性能。所采用的基準(zhǔn)方法包括：（1）加權(quán)法WS;（2）傳統(tǒng)的G-Skyline查詢方法。

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

其中，h1和h2分別是和的調(diào)節(jié)參數(shù)，用來調(diào)節(jié)兩者的權(quán)重。

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

4 結(jié)論

本文提出了改進(jìn)的G-Skyline查詢算法，該算法優(yōu)先計(jì)算支配數(shù)最大的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