基于數字標牌廣告數據的興趣點推薦算法研究

解貴龍　張　珣　于重重　趙　霞

(北京工商大學計算機與信息工程學院　北京 100048)

?

基于數字標牌廣告數據的興趣點推薦算法研究

解貴龍張珣*于重重趙霞

(北京工商大學計算機與信息工程學院北京 100048)

摘要為了解決數字標牌廣告投放的推薦問題，研究基于位置數據的推薦算法。在已有的基于矩陣分解思想的興趣點推薦算法基礎上，提出結合矩陣分解思想和商業地理信息數據的興趣點推薦模型，并在基于位置的數字標牌廣告數據上進行實驗。實驗結果表明，通過為矩陣分解附加商業地理信息的方法，解決了位置訪問數據稀疏性的問題，并為數據類型單一，推薦依據不足的問題提供了有效的數據參考及實現方法。為數字標牌廣告投放提供了重要的參考依據。

關鍵詞興趣點推薦數字標牌位置推薦矩陣分解

0引言

數字標牌是一種全新的媒體概念， 指的是在大型商場、超市、酒店大堂、飯店、影院及其他人流匯聚的公共場所，通過大數字標牌終端顯示設備，發布商業、財經和娛樂信息的多媒體專業視聽系統[1]。然而，傳統的數字標牌的選址，廣告的投放均由人工完成，時效性低、缺乏參考依據、已經不能滿足廣大廣告主和媒體商的利益需求[2]。因此，構建廣告精準投放推薦模型，為廣告主用戶提供廣告牌的推薦，實現廣告商和媒體商的利益最大化，成為值得研究的課題。本文所研究的興趣點推薦即可為廣告投放方提供有關數字標牌的地理屬性和商業屬性的分析結果，從而達到廣告在時間、空間、個性化上精準投放的目的。

本文所要研究的興趣點推薦是推薦領域比較新的研究點，其中一個重要特性就是位置數據，訪問或簽到，它可以看成推薦系統中常見的隱式評分數據。隱式評分是相對于顯示評分而言的，它不需要用戶額外行動，而是根據用戶行為判斷對待推薦物品的喜好或厭惡程度。而對這種隱式數據的處理主要是量化這種喜好或厭惡程度的操作。2010年Ye Mao等人利用用戶社交好友的協同評分和通過距離衡量好友之間的相似性進行興趣點推薦[3]，但此方法忽略了隱式數據的處理。2012年Cheng Chen等人基于用戶簽到頻率，利用矩陣分解思想進行興趣點推薦[4]，很好地處理了隱式數據，但是并沒有考慮到地理特征等其他因素的影響。同時還有些工作利用這些位置信息通過對空間聚集效應建模來幫助位置推薦[5,6]，但是這些方法是獨立于協同過濾的。2014年Lian De-Fu等人在此基礎上提出了基于地理建模內嵌的加權矩陣分解方法進行興趣點推薦[7]，擴展了地理特征因素，并為可能添加的其他因素提供了一種方法。

本文研究的興趣點推薦，主要針對廣告-興趣點矩陣稀疏性處理及數字標牌位置數據的特性分析處理這兩個問題展開。針對于以上兩個問題，本文基于Lian De-fu等人提出的GeoMF算法[7]，結合數字標牌數據特點，提出一種考慮位置的社會經濟數據作為推薦指標的推薦算法，該算法較有效地解決了上述問題。

1基于位置廣告數據的興趣點推薦算法

1.1基本矩陣分解推薦算法

運用矩陣分解做推薦面臨最大的挑戰是數據的稀疏性。對于缺失的評分，可以轉化為基于機器學習的回歸問題，也就是連續值的預測，矩陣分解如下：

(1)

(2)

(3)

其中β是正則參數。最后的目標，就是每一個非缺失值元素的損失函數的總和最小。

為了快速有效地得到損失函數的最小值，需要對損失函數的更新采用優化算法。下面式(4)為基于梯度下降的優化算法，式(5)是P、Q矩陣里面每個元素的更新方式：

(4)

(5)

其中，θ、β均為優化參數。

對于類似播放頻次這種隱式數據，加權矩陣分解會在大部分的隱式數據上工作得很好，因為它把所有的未投放位置都作為負樣本，并給它們賦了一個更小的權重[8,9]。在加權矩陣分解中，對損失函數的每一項進行了加權修改：

(6)

其中wij為權重矩陣W第i行j列的元素，wij元素的值如下：

(7)

其中α(cij)為R矩陣每個元素的值，這表明權重是依賴于訪問頻率的。這樣的設置可以體現訪問頻率是用戶偏好的置信值的特性。

1.2基于數字標牌廣告投放的興趣點推薦模型

本文所采用的興趣點推薦算法原理主要如圖1興趣點推薦算法原理所示，每個數字標牌實體即為一個興趣點。首先構造出廣告在興趣點上的播放頻次矩陣，然后通過矩陣分解算法將該矩陣分成兩個隱式特征和對應興趣點和廣告組成的隱式空間，再通過附加上廣告播放范圍矩陣和興趣點影響力矩陣，最后合并兩個矩陣，形成最后的推薦結果矩陣。這樣則可為播放頻次數據引入可能影響推薦效果的其他數據，從而提高推薦結果的可信度。

圖1　興趣點推薦算法原理

圖1中，播放頻次矩陣R的每一個元素rij(其中1≤i≤M，1≤j≤N)為廣告類型xi對應在數興趣點yj上的對于播放時間加權的播放頻次，i的最大值數為廣告類型數M，j的最大值為興趣點的個數N。由此矩陣直接進行矩陣分解得到的兩個隱式特征矩陣(分別為M行K列和K行N列)組成的隱式空間。根據矩陣分解及內積的性質，可以為這兩個隱式特征矩陣附加上包含其他信息的矩陣。當附加廣告播放范圍矩陣X(M行L列)和興趣點影響力矩陣Y(L行N列)時，可以有效表達廣告類型對不同興趣點的偏好，所以本文選取此兩矩陣作為附加信息，根據這兩個矩陣的信息，為興趣點推薦提供更多的可信度。

廣告類型分布范圍矩陣是由一系列區域以及廣告類型在這些區域上出現的可能性共同組成的。而興趣點的影響范圍矩陣是由興趣點能影響到的區域以及興趣點對它們的影響力值所組成的。對于興趣點的影響范圍，當假設區域是通過把目標地域劃分成L個的均勻網格得到的，表示為L={g1,g2,…,gi}(其中1≤i≤l)。因此定義如下：

定義1廣告分布區域，一類廣告的分布區域是指有一系列的廣告可能會出現的網格區域gi(1≤i≤l)，在上面可能出現的非負的可能性x()i對所組成的。

本文可以把廣告的分布區域表示成一個非負向量x={x1，x2，…，xi}(1≤i≤l)。其中每一個元素xl表示了此廣告在網格區域gl出現的可能性。

定義2興趣點的影響范圍，即一個興趣點的影響范圍是由一系列的興趣點能影響到的網格區域gl和在網格區域上的非負影響力yl對所組成的。

影響力的分布對于每個具體位置是連續并與周圍位置有相互影響的，如圖2影響力分布示例。

圖2　影響力分布示例

X軸和Y軸分別表示地塊的經度和維度的相對坐標，其中X軸坐標坐標由-3到2，Y軸坐標由-2到2，Z軸表示影響力的值。從圖中可以看出某一具體位置的影響力。實際數字標牌影響力是沒有負值的。此處為方便顯示影響力的變化趨勢引入負值。

同樣，興趣點影響范圍區域也可以被轉化成一個非負向量y={y1，y2，…，yi}(1≤i≤l)。當假設興趣點的影響力是固定的且是以這個興趣點為中心正態分布的。那么興趣點i在網格區域gl的影響力如下：

(8)

其中K(·)為標準正態分布而σ則是標準差。d(l,i)表示興趣點i與gl網格區域的距離。然而實際情況興趣點的影響力往往是不同的，興趣點的影響力受諸多因素影響，而其中一個可能影響最大的因素是社會經濟因素，如人口、收入等因素。為此，本文希望通過對一些社會經濟因素的分析，將興趣點的影響力函數進行修正為：

(9)

其中ti為修正系數，直接決定于興趣點所屬網格區域gi的社會經濟因素。為此，本文構建該修正系數矩陣：

(10)

其中ki,j表示第j個社會經濟因素在i興趣點所在地塊區域上的取值，wj表示第j個社會經濟因素的權重。各個權重的調整可根據不同網格區域所播放的廣告時長總和比例及各個社會經濟因素的比值進行調整。假設每個社會經濟因素之間互不影響，將有廣告播放記錄的網格區域挑選出來，選取其中一個區域作為基準區域，以此區域各社會經濟因素比例為基準設置初始權重。然后任意選取一個剩余區域，按廣告播放時長比例與對應社會經濟因素比例的比值逐步調整權重，進一步以更新后的權重為基準繼續進行權重修正，直到所有有播放記錄的區域迭代完即止。這樣選取區域的好處在于每個區域所做的比較基本相同，因為目前還沒法證明某個區域具有權重調整的代表性。第j個權重更新表達式為：

(11)

其中sn+1和sn分別表示后一次選擇的區域的廣告播放時長總和和前一次所選區域廣告播放時長總和。

這樣設置影響力向量的優點是x和y之間的點積對應了對廣告類型投放位置的核密度估計。具體來說，廣告類型u在興趣點i上的估計密度等于：

(12)

其中Pu是廣告類型u的投放興趣點集合。如果這些興趣點Pu被映射到相應的網格區域Lu?L，那么這個估計就變成：

(13)

其中nl為廣告類型u對gl的投放頻率。

本文利用x和y來擴展在矩陣分解中得到的廣告類型隱向量和興趣點隱向量。因此估計偏好矩陣，如下表示：

R=PQT+XYT

(14)

其中，所有廣告類型的分布范圍向量按行堆積得到廣告類型分布范圍矩陣X并且把所有興趣點的影響范圍向量按行堆積得到興趣點影響區域矩陣Y。進行這種顯式擴展來增加位置和商業信息的原因在于還沒有證據說明隱式空間己經包含了位置和商業相關信息，這里可以看到很容易通過類似的方法添加其他類型的屬性信息，比如興趣點類別等。在這種情況下，廣告類型對興趣點的偏好就建模成擴展空間內的點積，因此包含了來自于隱空間的興趣信息也包含了對興趣點的位置偏好。如果廣告類型對興趣點的位置偏好是非零的，那么廣告類型的分布區域是與興趣點的影響范圍相交的，從而，這些興趣點是可以從廣告類型的分布區域范圍可達的。

最后需要對廣告可達范圍矩陣和興趣點影響力矩陣進行調整：

(15)

其中，addsij為調整后的矩陣元素。k為調整系數，初始設為1，即視頻次矩陣和附加信息矩陣對推薦結果影響作用相同。addij為調整前的矩陣i行j列元素。H1為頻次矩陣中的最大值，L1為頻次矩陣中的最小值。H2為附加矩陣中的最大值，L2為附加矩陣中的最小值。

2數據處理

本文廣告播放數據及數字標牌關數據為合作企業提供，經濟相關數據來源為第三次經濟普查數據。其中播放記錄為北京地區的1311塊數字標牌在2013年1月至2014年12月間所產生的全部播放記錄，約6GB大小數據量。并包括期間全部播放廣告的基礎數據，和數字標牌的基礎數據。

2.1基礎數據處理

2.1.1剔除冗余數據

播放記錄中有無效播放記錄或空播放記錄，對之后的數據處理屬于冗余信息，需要進行剔除。

2.1.2數據存儲

需要將基礎的數據存入數據庫以備查詢調用。包括基礎的行業標簽庫，數字標牌(興趣點)庫，廣告素材庫，地塊信息庫。本文采用redis內存數據庫進行存儲。

2.1.3數據結果統計

對播放記錄進行初步的統計并將統計結果存入對應數據庫中。對統計數據入庫。并形成廣告類型和興趣點的播放頻次矩陣并存儲成文件保存到本地。同時形成興趣點和地塊的影響力矩陣，此矩陣為根據經濟因素調整后的矩陣，并存儲成文件保存到本地。

2.2經濟特征數據處理

本文所指的特征數據為那些可以反映某一地區完整經濟情況并與地理位置有緊密聯系的經濟類型數據。對于這種經濟特征數據的處理，首先需要去掉或合并關聯度過大的經濟數據。然后通過各地塊的經濟數據變化與播放時長記錄變化的關聯性分析，找出對播放時長影響進行特征提取。本文經過分析選取常住人口、商業從業人口和平均地價作為后續推薦結果的參考依據。

2.3地塊數據處理

2.3.1地理數據分塊

為方便統計地理位置上的經濟數據，并與興趣點產生關聯。需要對地理位置進行分塊，本文將興趣點分布的范圍分成500米×500米的小地塊。地塊有其中心點經緯度坐標。

2.3.2相關數據關聯

在將地理數據分塊好后，需要將各類經濟數據關聯到地塊上，并根據地塊坐標及所占范圍將各數字標牌(興趣點)與地塊進行關聯。將各數字標牌播放廣告的有效時長總和統計結果關聯到地塊上。

3實驗

3.1開發環境

本文采用python2.7作為開發語言。為快速響應查詢信息，數據庫選為Redis2.6。采用NumPy1.8.1進行數據處理。同時調用用于協同過濾的矩陣分解基礎推薦算法LIBMF1.2庫[10]進行基本矩陣分解。本文采用Matplotlib1.4.3進行數據的統計分析展示，采用ArcMap10.1對推薦結果關聯到地理位置上的分析展示。

3.2推薦結果分析

最終推薦結果為廣告播放頻次矩陣分解的結果與數字標牌影響力矩陣和廣告播放范圍矩陣合并的結果。最終會為每個廣告類型生成推薦數字標牌的列表。根據列表中值的大小決定為該廣告類型推薦的數字標牌，也就是選取TopN結果推薦。

為了測試推薦結果的準確性，本文選用準確率(Precision)參數進行評定，其定義為pu=nu/Nu，其中pu為廣告類型u的準確率，Nu為廣告類型u選取N個推薦結果，nu表示這些推薦結果中為u實際播放過的個數。

為每種廣告類型的前10個推薦結果進行Precision評定。圖3為在廣告類型中隨機抽取的10種廣告類型的Precision結果。

圖3　隨機抽取推薦結果Precision值

可以從圖中看出推薦結果的Precision評定基本在10%左右，初步確定推薦結果具有一定的可信度。

圖4展示了所有廣告類型在北京范圍內產生的前10個推薦結果中的Precision值的統計結果。

圖4　廣告類型Precision值統計

圖4中的百分數，如10%～14%表示的是廣告類型的Precision值在10%～14%之間，其所占的餅狀圖面積與整個餅狀圖的比值代表了Precision值在10%～14%之間的所有廣告類型數占總的廣告類型數的比值。從圖中可以看出有超過75%的廣告類型的Precision值集中在8%～14%概率上，這表明推薦結果在整體數據的推薦效果上是比較集中的。并且推薦結果在保持一定的可信度的同時，還擁有著不錯的興趣偏移預測，即因為時間、地點等因素改變所引起的播放興趣轉變。

對于某一類廣告投放推薦結果，我們希望它能根據相似或相同類型廣告的歷史播放記錄和商業地理信息數據，選出那些包含著投放用戶已有投放經驗，如在學校附近投放培訓、教育類的廣告，的數字標牌(推薦結果)。并且能根據商業地理信息數據為其篩選排序。以下為某一類廣告推薦結果的具體分析。

商業地理信息數據就是將商業特征和現象的數值表征聯系到它所在的地理信息上[11]。本文利用商業地理信息數據完成推薦結果在位置上的展示，展示選取技能培訓、教育輔助及其他教育行業，行業代碼為P829的廣告的所有推薦結果展示在北京市范圍內的分布情況。如圖5為北京地區推薦結果分布。

圖5　P829北京地區推薦結果分布

途中顏色越深的點表示此位置的數字標牌的推薦值越高，顏色越淺的點表示推薦的值越低?？梢钥闯龃蟛糠值母咄扑]度的數字標牌都集中在三環內。

為了更準確地看出推薦數字標牌分布的趨勢，本文用相同的數據繪制了如圖6北京地區推薦結果熱度的推薦值的熱點圖。

圖6　P829北京地區推薦結果熱度

圖6中顏色越深的區域表示推薦的值越高，顏色越淺的區域表示推薦值越低。由圖6中可以看出，對于技能培訓類的廣告，這里會推薦三環內偏北值的數字標牌進行投放，這些推薦結

果里包含著如“在學校附近投放培訓教育類廣告”等的投放經驗，同時推薦值的排序也借助了商業地理信息的指導，那些人流密集，商業發達的地區的推薦值會更高，與推薦決策吻合。

4結語

本文通過基本的矩陣分解算法，利用它對其他數據的很好的擴展性能選取了部分商業地理信息融合在推薦算法中，從而在解決了數據稀疏性問題的同時為推薦結果提供了更多的推薦依據，提高了推薦結果的可信度。同時為數字標牌這種有著明顯地理特征的興趣點提供了一種可能的推薦模型。從推薦結果上看，本文在保證一定可信度的同時，為可能的興趣偏移提供了一定的預測性能。

參考文獻

[1] 叢秋波.數字標牌:新媒體,新趨勢,新市場[J].電子設計技術,2009(6):76.

[2] 王敏,寇亞龍,趙霞.數字標牌廣告即時排期優化算法研究[J].電腦知識與技術,2014(26):210-213.

[3] Ye M,Yin P,Lee W C,et al.Exploiting geographical influence for collaborative point-of-interest recommendation[C]//Proceedings of the 34th international ACM SIGIR conference on Research and development in Information Retrieval.ACM,2011:325-334.

[4] Cheng C,Yang H,King I,et al.Fused matrix factorization with geographical and social influence in location-based social networks[C]//Twenty-Sixth AAAI Conference on Artificial Intelligence,2012.

[5] Liu B,Fu Y,Yao Z,et al.Learning geographical preferences for point-of-interest recommendation[C]//Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining.ACM,2013:1043-1051.

[6] Zhang J D,Chow C Y.iGSLR:personalized geo-social location recommendation:a kernel density estimation approach[C]//Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems.ACM,2013:334-343.

[7] Lian D,Zhao C,Xie X,et al.GeoMF:joint geographical modeling and matrix factorization for point-of-interest recommendation[C]//Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining.ACM,2014:831-840.

[8] Hu Y,Koren Y,Volinsky C.Collaborative filtering for implicit feedback datasets[C]//Data Mining,2008.ICDM’08.Eighth IEEE International Conference on.IEEE,2008:263-272.

[9] Pan R,Zhou Y,Cao B,et al.One-class collaborative filtering[C]//Data Mining,2008.ICDM’08.Eighth IEEE International Conference on.IEEE,2008:502-511.

[10] Zhuang Y,Chin W S,Juan Y C,et al.A fast parallel SGD for matrix factorization in shared memory systems[C]//Proceedings of the 7th ACM conference on Recommender systems.ACM,2013:249-256.

[11] Zhang X,Zhang X,Zhong E,et al.Multi-Scale Centrality Measures of Street Network in Beijing,China[J].Sensor Letters,2014,12(3-5):651-658.

收稿日期：2015-07-02。國家自然科學青年基金項目(612020 60)；教育部人文社會科學研究青年基金項目(15YJCZp24)；北京市自然科學基金重點項目B類(KZ201410011014)；北京市教育委員會2015年度科技計劃面上項目(KM201510011009)；北京市自然科學基金青年項目(9164025)。解貴龍，碩士生，主研領域：機器學習，數據挖掘。張珣，講師。于重重，教授。趙霞，副教授。

中圖分類號TP301.6

文獻標識碼A

DOI:10.3969/j.issn.1000-386x.2016.07.056

RESEARCH ON POI RECOMMENDATION ALGORITHM BASED ON DIGITAL SIGNAGE ADVERTISEMENT DATA

Xie GuilongZhang Xun*Yu ChongchongZhao Xia

(CollegeofComputerandInformationEngineering,BeijingTechnologyandBusinessUniversity,Beijing100048,China)

AbstractTo solve the problem of digital signage advertising recommendation, we studied the location data-based recommendation algorithm. On the basis of existing point of interest (POI) recommendation algorithm, which is based on matrix factorisation idea, we proposed a POI recommendation model which combines the matrix factorisation idea and commercial GIS data, and conducted experiments on location-based digital signage advertising data. Experimental results showed that, by the method appending commercial GIS data to matrix factorisation, the problem of location access data sparseness has been solved, and this provides an effective reference and implementation approach for the problems of single data type and insufficient recommendation basis. Our study provides an important reference basis for the digital signage advertising.

KeywordsPoints of interest recommendationDigital signageLocation recommendationMatrix factorisation