基于用戶網絡嵌入的民宿房源推薦方法

劉彤 曾誠 何鵬

摘 要：隨著民宿行業的迅速發展，在線民宿訂房系統開始流行起來。讓用戶在海量房源信息中快速找到所需房源是訂房系統中待解決的問題。針對房源推薦中用戶冷啟動與數據稀疏性的問題，提出基于網絡嵌入法的房源個性化推薦（UNER）方法。首先通過用戶在系統中的歷史行為數據及標簽信息構建兩類用戶網絡;然后基于網絡嵌入法將網絡映射至低維向量空間中，得到用戶節點的向量表示并通過用戶向量計算用戶相似度矩陣;最后依據該矩陣為用戶進行房源推薦。實驗數據來源于貴州“水東鄉舍”民宿訂房系統。實驗結果表明，相對于基于用戶的協同過濾算法，所提方法的綜合評價指標（F1）提升了20個百分點，平均正確率（MAP）提升11個百分點，體現出該方法的優越性。

關鍵詞：網絡嵌入;房源推薦;協同過濾;用戶行為

中圖分類號：TP311.51

文獻標志碼：A

Housing recommendation method based on user network embedding

LIU Tong1， ZENG Cheng1，2*， HE Peng1，2

1.School of Computer Science and Information Engineering， Hubei University， Wuhan Hubei 430062， China）

2.Hubei Engineering Research Center for Education Informationization， Wuhan Hubei 430062， China

Abstract：

With the rapid development of the hotel industry， the online hotel reservation system has become popular. How to let users quickly find the housing they need from massive housing information is the problem to be solved in the reservation system. Aiming at the cold start and data sparseness of users in the housing recommendation， the User Network Embedding Recommendation （UNER） method based on the network embedding method was proposed. Firstly， two kinds of user networks were constructed by the users historical behavior data and tag information in the system. Then， the network was mapped into the lowdimensional vector space based on the network embedding method， and the vector representation of the user node was obtained and the user similarity matrix was calculated by the user vector. Finally， according to the matrix， the housing recommendation was performed for the user. The experimental data come from the hotel reservation system of “Shuidongxiangshe” in Guizhou. The experimental results show that compared with the userbased collaborative filtering algorithm， the proposed method has the comprehensive evaluation index （F1） increased by 20 percentage points and the Mean Average Precision （MAP） increased by 11 percentage points， reflecting the superiority of the method.

Key words：

network embedding; housing recommendation; collaborative filtering; user behavior

0?引言

隨著互聯網越發普及和成熟，在線訂房系統受到很多人的青睞，為用戶提供個性化推薦策略也是訂房系統中必不可少的一部分，它可以幫助用戶在海量房源中找到所需房源。推薦系統主要是挖掘用戶潛在需求，幫助用戶進行決策[1]，推薦效果的好壞直接影響著用戶體驗和公司收益。[2]。在民宿房源推薦問題中，協同過濾推薦方法[3-5]無法解決用戶冷啟動問題[6]及數據稀疏性問題。

針對上述問題，本文通過用戶在注冊時選擇的標簽數據與用戶行為數據構建兩類用戶用戶網絡，并使用網絡嵌入（network embedding）法分別得到兩種網絡中用戶節點的向量表示。使用用戶標簽數據構建的網絡來解決系統中用戶冷啟動問題;同時在構建網絡時充分考慮網絡中節點的一階和二階關系用來解決數據稀疏問題。

1?相關工作

網絡結構在現實生活中處處可見， 比如道路將城市之間連接成交通網絡，論文中引用關系將論文之間構成學術論文網絡。對各種數據網絡進行分析時首先要對網絡進行表示，常用的方法是用鄰接矩陣表示網絡，最終將節點用高維稀疏向量表示， 這種方法計算時間長并且消耗大量空間。文獻[7]中將由網絡表示的鄰接矩陣作為奇異值分解（Singular Value Decomposition， SVD）算法的輸入參數，將節點用低維表示，但是這種表示在數據挖掘中性能不理想。文獻[8]中提出的算法將網絡中的信息擴散問題轉換為低維空間上的信息擴散問題，并使用低維向量表示節點信息，但是算法的復雜度可以達到立方量級，所以不適合大規模網絡分析任務。

網絡嵌入法[9]又稱網絡表示學習，是表示學習技術的一個子集。表示學習是一種對數據廣義的特征表示，而網絡嵌入法則更加專注于網絡的表示，旨在將網絡中的節點以更加直觀、更加高效的某種方式盡可能地還原原始空間中節點的關系，把網絡中的每個節點映射成為一個低維稠密實數向量，不僅可以降低時間和空間上的計算開銷，而且可以提高節點向量在各種網絡分析任務中的性能。

Xie等[10-11]將網絡表示學習應用于地點推薦領域;Ding等[12]在基于位置的社交網絡中利用用戶的興趣點來提供更加準確的推薦;He等[13]通過向NCF（Neural Collaborative Filtering）模型中輸入用戶和商品網絡中邊的信息，同時使用多層感知機來得到用戶和商品間的非線性關系，最終計算用戶間相似度來進行推薦;文獻[14]中DeepWalk算法在網絡中進行隨機游走得到節點訪問序列，然后將其作為skipgram[15]的輸入并得到節點向量。網絡嵌入法是近幾年快速發展的數據分析技術，但是它在個性推薦領域還處于剛起步的階段。

2?解決方案

UNER（User Network Embedding Recommendation）方法的整體解決方案如圖1所示。

1）通過用戶標簽數據構建用戶用戶網絡，并通過網絡嵌入法計算用戶節點向量表示形式，通過該類型網絡中用戶的向量表示來解決民宿房源推薦問題中用戶冷啟動問題。

2）使用對比標度權重法計算用戶各行為的權重值，并通過用戶行為數據構建用戶用戶網絡。

3）為解決用戶標簽數據和用戶行為數據稀疏問題，本文在計算網絡中節點向量時不僅考慮節點間的一階鄰近度，同時還考慮節點間的二階鄰近度，即通過增加節點的高階鄰居（如鄰居的鄰居）來拓展網絡中節點的鄰居，用以解決用戶數據稀少造成的稀疏性問題。

4）通過用戶節點的特征向量計算用戶間相似性，使用協同推薦得到TopN推薦房源列表。

為方便閱讀，介紹算法中用到的結構和定義。

定義1?用戶標簽。用戶在注冊時選擇興趣標簽，對于用戶u而言，用戶標簽集Tu可以表示一個用戶u自身的標簽集合〈u，t〉，數據集T={Tu：u∈U}是所有用戶的標簽記錄集合。

定義2?用戶行為。用戶在使用民宿訂房系統時，會產生各種行為，比如瀏覽、收藏、購買等。一個用戶u對房源h產生的行為b可以用三元組〈u，h，b〉來表示，將該三元組稱為Bu。數據集B是所有用戶對房源產生的行為數據集合。

定義3?用戶共現。當兩個用戶具有相同標簽或者對同一房源都具有行為時，那么就稱為這兩個用戶共現。

當給定用戶標簽數據集后，需要通過用戶的標簽來統計用戶對之間的共現次數來確定兩用戶之間的權重。若使用用戶行為數據，則需要計算用戶各行為的權重。最終通過數據集T和B，構建兩類用戶用戶網絡。下面介紹用戶用戶網絡的定義。

定義4?用戶用戶網絡。用戶用戶網絡主要是通過抽取用戶對之間的共現信息構建獲得?？梢詫⒂脩粲脩艟W絡表示成G=（V，E）的加權無向圖形式，每一個節點代表著一個用戶，V表示網絡中的節點信息。E表示網絡中節點和節點即用戶和用戶之間的無向邊，代表用戶之間共現信息。節點Vi和節點Vj之間邊的權重Wi， j是由用戶標簽集合T和用戶行為集合B中用戶i和用戶j之間的共現次數。

根據以上定義，可以通過用戶標簽集合T和用戶行為集合B構建出兩類用戶用戶網絡。圖2是基于用戶標簽的用戶用戶網絡。在通過用戶標簽構建用戶用戶網絡的過程中，分析用戶標簽中每個用戶和其他用戶是否具有相同的標簽，從而獲得用戶用戶網絡中邊的權重。在本例中，用戶1和用戶2都有標簽1和標簽2，因此在用戶用戶網絡中，用戶1和用戶2對應節點的邊的權重為2。

圖3是基于用戶行為的用戶用戶網絡。在通過用戶行為構建用戶用戶網絡的過程中，分析用戶和其他用戶是否對同一房源產生行為。使用對比標度權重法計算各種行為所對應的權重，網絡中兩個用戶節點間邊的權重是這兩個用戶對同一房源產生的行為權重相加之和。圖3中user_1和user_2之間邊的權重為user_1對h_2和h_3產生行為的權重加上user_2對h_2和h_3產生行為的權重。

最終，構建兩類用戶網絡后，當系統判定用戶為新用戶時，則通過用戶標簽信息來構建用戶用戶網絡并計算用戶向量，然后計算用戶相似矩陣，最終完成TopN推薦。基于用戶標簽的網絡主要用于解決用戶冷啟動問題;如果用戶不是新用戶，那么利用用戶在系統中的行為數據來構建網絡，然后計算用戶相似矩陣，最后為用戶提供TopN推薦。

3?研究方法

3.1?網絡嵌入法的一階鄰近度和二階鄰近度

一階鄰近度?該模型只適用于無向圖，對于用戶用戶網絡中的一條無向邊（i， j）定義兩個節點vi和vj的共享概率如下：

p1（vi，vj）=11+exp（-uiT，uj）（1）

其中：ui和uj是網絡中節點i和j的向量化表示形式，相當于從Embedding的角度來描述節點之間的親密程度，兩個節點親密程度的度量將由網絡的數據結構中獲得。

1（vi，vj）=wijW（2）

其中：wij是節點i和j間邊的權值;W是指網絡中所有邊權值的和，即W=∑ （i，j）∈Ewij。為保證一階鄰近度的可靠性，p1和1之間的分布差異越小越好，則將目標函數優化如下：

O1=d（p1，1）（3）

兩個概率之間的分布差異由d（）函數來衡量，本文中選用KL散度，可以將式（3）優化為：

O1=-∑ （i，j）∈EWijlogp1（vi，vj）（4）

通過學習訓練，我們可以得到每個用戶節點的特征向量{ui}i=1，2，…，|U|，并且滿足使式（4）最小化。

二階鄰近度?二階鄰近度是認為網絡中與其他節點具有相同鄰居節點的兩個節點彼此相似。在該情況下，每個節點也被認為是一個特定的“上下文”，并假設在“上下文”上具有相似分布的節點是相似的。因此每個節點都具有兩種角色：節點本身和其他節點的特定“上下文”。引入兩個向量ui和ui′，當vi被處理為節點時，ui是vi的表示;當vi被當作“上下文”處理時，ui′是vi的表示。對于邊（i，j），將節點vi生成“上下文”vj的概率定義為：

p（vj|vi）=exp（ui′T·ui）∑|V|k=1exp（uK′T·ui）（5）

其中|V|是頂點或“上下文”的數量。為了保證節點間二階相似度信息，則應該使降維之后上下文的概率p（·|vi）盡可能地接近實際概率（·|vi）。表示為：

O2=∑ i∈Vaid（（·|vi），p（·|vi））（6）

由于網絡節點的重要性可能不同，所以式（6）中的ai表示網絡中節點i的重要程度。實際概率定義為（vj|vi）=wij∑ k∈N（i）wik，其中wij是邊（i，j）的權重，N（i）是節點vi鄰近的節點集。這里采用KL散度作為距離函數：

O2=-∑ （i，j）∈EWijlogp2（vj|vi）（7）

通過模型的學習訓練，可以得到使式（7）最小化{ui}i=1，2，…，|U|，就能通過一個d維的向量的ui′表示每個頂點ui。最后，每個用戶節點ui的嵌入向量表示ui為一級鄰近度下的向量ui1與二階鄰近度下向量ui2的線性組合，即：

ui=γui1+（1-γ）ui2（8）

3.2?基于用戶網絡嵌入的推薦

基于用戶網絡嵌入法的推薦是通過用戶用戶網絡得到用戶相似矩陣，使用相似用戶進行房源推薦。通過上述方法計算，可得到每個用戶的特征向量ui，本文中采用余弦相似度[16]來計算用戶間相似度，并獲得相似用戶集合S（u）。

sim（ui，uj）=cos（ui，uj）（9）

對于用戶u是否選擇房源h，根據其相似用戶集中的用戶選擇情況進行判斷。對于房源h，用戶u選擇它的概率的計算公式如下：

p（u，h）=∑ v∈S（u）∩N（h）sim（u，v）·rvh（10）

其中：rvh表示用戶u的相似用戶v對房源h的喜歡程度，N（h）是已選擇了房源h的用戶集。最后得到用戶u對未曾關注過的房源感興趣的概率列表，并且將概率大的房源進行優先推薦。

3.3?對比標度權重法

民宿訂房系統中的用戶行為包括瀏覽、收藏和購買。本文利用對比標度權重法[17]來確定不同行為下用戶對該房源的喜愛程度。它是指事物與離散變量各類之間有一定的聯系，所以就可將權重的概念使用到分類變量上，數量化賦值的標準將由對指標各分類的不同權重來確定。首先按層次分析法的原則將某個分類變量依據一定的規則進行賦值，然后根據各個類之間的重要程度，最后按照從1～9的標度方法，如表1所示，一一對比標度，構造如下判斷矩陣：

D1D2?…?Dn

D1D2Dn-1Dnd11d12…d1n

d21d22…d2n

d（n-1）1d（n-1）2…d（n-1）n

dn1dn2…dnn

4?實驗分析

4.1?數據獲取

實驗數據主要來自于貴州“水東鄉舍”項目2018年5月—2019年2月 200位用戶的標簽數據和行為數據以及150間民宿房源數據?！八畺|鄉舍”是我們團隊為貴州某公司實施的精準扶貧項目，擬在開陽縣試點，成功后在貴陽市及貴州省推廣。

1）用戶標簽數據。民宿訂房系統中的用戶注冊頁面設計了用戶選擇興趣標簽的功能。用戶在注冊時選擇的標簽數據就是用戶標簽數據集。

2）用戶行為數據。民宿訂房系統中定義了三種用戶行為，分別為瀏覽、收藏和購買。用戶對商品的收藏和購買行為是在系統中明確產生的行為，很容易獲取。系統中獲取用戶瀏覽房間的記錄主要是通過頁面中的JavaScript代碼來實現。

4.2?計算用戶各行為權重

用戶行為（瀏覽、收藏、購買）是用戶對該房源是否有興趣的體現，不同的行為表示了用戶對該房源的喜好程度。用戶各行為的權重計算分為下面三步。

1）根據表1構建判斷矩陣，兩兩行為進行對比，得出行為之間的相對重要性，如表2所示。

2）計算特征向量。從表3中的數值可以計算瀏覽、收藏和購買行為的特征向量值。計算方法在4.3節詳細講述。計算過程如下所示：

瀏覽=31×1/5×1/9=0.28;收藏=35×1×1/4=1.08;購買=39×4×1=3.30。

3）對特征向量值作歸一化處理，確定權重系數。計算過程如下：

瀏覽=0.28/4.66=0.06;收藏=1.08/4.66=0.23;購買=3.30/4.66=0.70。通過計算，可以得到三種行為的權重系數。

4.3?構建網絡

本節以用戶行為數據集為例，構建基于用戶行為的用戶用戶網絡。圖4為用戶行為的部分數據集，該數據集主要由用戶編號、房源編號和行為編號構成。

圖5為將圖4中數據轉換為帶權無向圖后的數據形式。

將圖5中的數據經過網絡嵌入法計算其一階與二階鄰近度，并將兩種近鄰度下的用戶特征向量進行線性組合就可得到每個用戶節點的向量表示形式，如圖6所示。

4.4?參數影響分析

本文所提算法采用綜合評價指標（F1值）和平均正確率（Mean Average Precision，MAP）來衡量。F1計算公式為：

F1@K=2PRP+R

其中：P為精確率，R為召回率。

MAP的計算公式為：

MAP@K=∑Nn=1Avep（n）N

其中Avep（n）=∑nq=1（p（q）×rel（q））number of relevant documents;N表示為N個用戶推薦;對于已排序好的推薦列表，q代表推薦列表中房源的排名，當q為已推薦成功房源時rel（k）為1，否則為0;p（q）是q前面房源的精確度。

將用戶行為數據集隨機抽出25%的數據作為測試集，剩余數據作為訓練集。用戶向量維度的設置為LINE方法中的默認值128維，在優化過程中取負采用數為5，學習率的初始值設置為ρ0=0.025，且ρτ=ρ0（1-t/T），其中T為網絡中邊的數量。對于式（8）參數γ值的確定，采用變量固定措施。保持UNER方法中相似用戶集S（u）=5，參數γ按照每次增加0.1的方式從0到1變化，分別為用戶推薦4、6和8個房源，結果如圖7所示，當γ值取0.7時，實驗結果最佳。

4.5?實驗結果

為了驗證本文實驗的有效性，將UNER方法的推薦結果與基于用戶的協同過濾算法（Userbased Collaborative Filtering，UserCF）的結果再進行對比。當γ=0.7，目標用戶的相似數據集S（u）長度取5時，分別推薦6～10個房源，然后計算F1值和MAP值，兩種算法得到的結果，如表3所示。

當目標用戶的相似數據集S（u）長度取10時，分別推薦6～10個房源，然后計算F1值，分別得到兩種算法的F1值和MAP值，如表4所示。

將表4與表5轉換為圖表形式，如圖8和圖9所示，可以看出在兩種情況下UNER的綜合評價指標和平均正確率均比UserCF高，即UNER的推薦結果比UserCF更優。

5?結語

從實驗結果中可看出，基于用戶網絡嵌入法的民宿房源推薦方法要比協同過濾算法在綜合評價指標上更優。相對基于用戶的協同過濾算法，UNER方法的推薦綜合評價指標（F1值）和平均正確率（MAP）均比基于用戶的協同過濾算法更優。由于本文的研究主要是針對民宿房源的推薦，所以數據集采用貴州“水東鄉舍”項目中的用戶標簽數據和用戶行為數據。

另外，在后期研究中應加入用戶的社交網絡數據，來提高推薦的精準度。同時，應結合更多用戶的隱性行為數據，比如用戶在頁面的停留時間、用戶對房源的評價信息以及用戶行為產生的時間，并考慮多方面因素確定行為權重，從而更加精準為用戶推薦房源信息。

參考文獻 （References）

[1]DESHPANDE M， KARRYPIS G. Itembased TopNrecommendation algorithms[J]. ACM Transactions on Information Systems， 2004， 22（1）：143-177.

[2]JUNG K Y， HWANG H J， KANG U G. Constructing full matrix through Naive Bayesian for collaborative filtering[C]// Proceedings of the 2006 International Conference on Intelligent Computing， LNCS 4114. Berlin： Springer， 2006：1210-1215.

[3]GOLDBERG D， NICHOLS D， OKI B M， et al. Using collaborative filtering to weave an information tapestry[J]. Communications of the ACM， 1992， 35（12）： 61-70.

[4]BREESE B J S， HECKERMAN D， KADIE C. Empirical analysis of predictive algorithms for collaborative filtering[C]// Proceedings of the 4th Conference on Uncertainty in Artificial Intelligence， 1998：43-52.

[5]鄧愛林，朱揚勇，施伯樂. 基于項目評分預測的協同過濾推薦算法[J]. 軟件學報， 2003， 14（9）：1621-1628. （DENG A L， ZHU Y Y， SHI B L. A collaborative filtering recommendation algorithm based on item rating prediction [J]. Journal of Software， 2003， 14（9）： 1621-1628.）

[6]邵煜，謝穎華. 協同過濾算法中冷啟動問題研究[J]. 計算機系統應用， 2019， 28（2）：246-252. （SHAO Y， XIE Y H. Research on coldstart problem of collaborative filtering algorithm[J]. Computer Systems & Applications， 2019， 28（2）：246-252.）

[7]LE T M V， LAUW H W. Probabilistic latent document network embedding[C]// Proceedings of the 2014 IEEE International Conference on Data Mining. Piscataway： IEEE， 2014： 270-279.

[8]BOURIGAULT S， LAGNIER C， LAMPRIER S， et al. Learning social network embeddings for predicting information diffusion[C]// Proceedings of the 2014 IEEE International Conference on Data Mining. Piscataway： IEEE， 2014： 393-402.

[9]PEROZZI B， ALRFOU R， SKIENA S. DeepWalk： online learning of social representations[C]// Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2014：701-710.

[10]XIE M， YIN H， XU F， et al. Graphbased metric embedding for next POI recommendation[C]// Proceedings of the 2016 International Conference on Web Information Systems Engineering， LNCS 10042. Berlin： Springer， 2016： 207-222.

[11]XIE M， YIN H， WANG H， et al. Learning graphbased POI embedding for locationbased recommendation[C]// Proceedings of the 25th ACM International on Conference on Information and Knowledge Management. New York： ACM， 2016：15-24.

[12]DING R， CHEN Z. RecNet： a deep neural network for personalized POI recommendation in locationbased social networks[J]. International Journal of Geographical Information Science， 2018， 32（8）： 1631-1648.

[13]HE X， LIAO L， ZHANG H， et al. Neural collaborative filtering[J]. Proceedings of the 26th International Conference on World Wide Web. Republic and Canton of Geneva， Switzerland： International World Wide Web Conferences Steering Committee， 2017：173-182.

[14]WANG D， CUI P， ZHU W. Structural deep network embedding[C]// Proceedings of the 22nd ACM SIGKDD International Conference. New York： ACM， 2016：1225-1234.

[15]MIKOLOV T， SUTSKEVER I， CHEN K， et al. Distributed representations of words and phrases and their compositionality[C]// Advances in Neural Information Processing Systems 26. Cambridge， MA： MIT Press， 2013：3111-3119.

[16]LUO C， ZHAN J， WANG L， et al. Cosine normalization： using cosine similarity instead of dot product in neural networks[EB/OL]. [2019-03-20]. https：//arxiv.org/pdf/1702.05870.pdf.

[17]高陽，余建偉. 判斷矩陣標度擴展法在不同標度下的比較[J]. 統計與決策， 2007（20）：152-154. （GAO Y， YU J W. Comparison of judgment matrix scale expansion method under different scales[J]. Statistics and Decision， 2007（20）：152-154.）

This work is partially supported by the National Natural Science Foundation of China （61902114）， the Hubei Province Major Technological Innovation Project （2016CFB309）.

LIU Tong， born in 1993， M. S. candidate. His research interests include big data processing， recommendation algorithm.

ZENG Cheng， born in 1976， Ph. D.， professor. His research interests include big data processing， domain software engineering， service recommendation.

HE Peng， born in 1988， Ph. D.， associate professor. His research interests include big data processing， software metrics， complex network.