LBS推薦系統的設計方法

發表于2016-01-04 15:45|1291次閱讀| 來源阿里巴巴資深工程師|0 條評論| 作者賈雙成

推薦系統LBS案例 摘要：推薦系統是興趣點系統的核心，本文將重點介紹推薦系統。推薦系統是一個很龐大的課題，該文主要講述推薦系統的設計方法，包含推薦系統的數學基礎和設計原理。

在 《程序員》12月刊A中，我們介紹了POI（興趣點）的設計及其搜索。由于推薦系統是興趣點系統的核心，所以接下來，我們將介紹推薦系統。推薦系統是一個很龐大的課題，將分成兩期予以介紹：本期講述推薦系統的設計方法，包含推薦系統的數學基礎和設計原理。

關于推薦系統有很多經典的應用，比如：淘寶/天貓/亞馬遜上的商品都是通過推薦系統來排列的；各種音樂應用（比如網易云音樂或者蝦米音樂）都是按照推薦系統的原理來向用戶推薦音樂的；今日頭條等新聞推薦應用已經充分說明了新聞推薦的力量；Netflix的電影推薦技術也為優酷/搜狐等視頻應用指明了道路。LBS應用的推薦系統的原理與這些典型的推薦系統應用的基本原理相同，比如：美團/糯米的興趣點推薦，淘寶/支付寶口碑的興趣點推薦。

希望通過這兩期的介紹，讀者可以明白一個推薦系統的設計原理，以及如何應用。在本期中我們將首先講述推薦系統的前世今生，之后講述推薦系統的數學基礎，最后講述推薦系統的設計原理。

推薦系統的前世今生

隨著互聯網的發展，人們正處于一個信息爆炸的時代。相比于過去的信息匱乏，面對現階段海量的信息數據，對信息的篩選和過濾成為了衡量一個系統好壞的重要指標。一個具有良好用戶體驗的系統，會將海量信息進行篩選、過濾，將用戶最關注最感興趣的信息展現在用戶面前。這大大增加了系統工作的效率，也節省了用戶篩選信息的時間。

搜索引擎的出現在一定程度上解決了信息篩選問題，但還遠遠不夠。搜索引擎需要用戶主動提供關鍵詞來對海量信息進行篩選。當用戶無法準確描述自己的需求時，搜索引擎的篩選效果將大打折扣，而用戶將自己的需求和意圖轉化成關鍵詞的過程本身就是一個并不輕松的過程。

在此背景下，推薦系統出現了，推薦系統是一種利用歷史數據的關聯分析，是一種通過對用戶的行為數據進行挖掘，從而向用戶推薦有用的信息技術。推薦系統是最典型的數據挖掘應用，也是知名度最高的數據挖掘應用。 推薦系統的任務就是解決上述的問題，聯系用戶和信息，一方面幫助用戶發現對自己有價值的信息，另一方面讓信息能夠展現在對他感興趣的人群中，從而實現信息提供商與用戶的雙贏。

推薦系統的數學基礎

推薦系同的數學基礎是距離，和相關系數。距離和相關系數的本質都是相似度。距離用來表示兩個（組）散亂數據間的相似度；而相關系數用來表示兩組近似線性的數據的相似度。相似度計算是各種數據挖掘算法的主要數學基礎。比如：聚類算法中往往是利用數據間的彼此距離或者相關系數進行計算的。基于實例的學習中的K近鄰算法，及關聯分析也是利用距離或相關系數作為數據基礎的。各種推薦算法在本質上只是某一種計算相關系數的方法而已。限于篇幅，以下僅介紹幾種常見距離和相關系數，其他詳細內容，可參見我撰寫的《LBS核心技術揭秘》一書。

距離

距離是聚類的基礎,是最重要的數據挖掘中最重要的概念之一，也是衡量相似度的主要指標之一。距離有很多種，各種距離的應用場景可以簡單概括為：

• 空間：歐氏距離；
• 路徑：曼哈頓距離；
• 國際象棋國王：切比雪夫距離；
  
• 歐氏距離、曼哈頓距離、切比雪夫距離三種距離的統一形式：閔可夫斯基距離；
  
• 加權：標準化歐氏距離；
  
• 排除量綱和依存：馬氏距離；
  
• 編碼差別：漢明距離。
  

在各種距離中，閔可夫斯基距離是最常見的一種距離。

1.閔可夫斯基距離

兩個n維變量a(x11，x12，…，x1n)與b(x21，x22，…，x2n)間的閔可夫斯基距離(Minkowski Distance)定義為：

其中p是一個變參數。

當p=1時，就是曼哈頓距離

當p=2時，就是歐氏距離

當p→∞時，就是切比雪夫距離

根據變參數的不同，閔氏距離可以表示一類的距離。

（1）歐氏距離。最常見的兩點之間或多點之間的距離表示法又稱之為歐幾里得度量，它定義于歐幾里得空間中，如點 x = (x1,...,xn) 和 y = (y1,...,yn) 之間的距離為：

• 二維平面上兩點a(x1,y1)與b(x2,y2)間的歐氏距離：

• 三維空間兩點a(x1,y1,z1)與b(x2,y2,z2)間的歐氏距離：

兩個n維向量a(x11,x12,…,x1n)與 b(x21,x22,…,x2n)間的歐氏距離：

也可以用表示成向量運算的形式：

標準化歐氏距離(Standardized Euclidean distance)是針對簡單歐氏距離的缺點而作的一種改進方案。標準歐氏距離的思路：既然數據各維分量的分布不一樣，那先將各個分量都“標準化”到均值、方差相等。

假設樣本集X的數學期望或均值(mean)為m，標準差(standard deviation，方差開根)為s，那么X的“標準化變量”X*表示為：(X-m）/s，而且標準化變量的數學期望為0，方差為1。

即樣本集的標準化過程(standardization)用公式描述就是：

標準化后的值=(標準化前的值－分量的均值) /分量的標準差

經過簡單的推導就可以得到兩個n維向量a(x11,x12,…,x1n)與 b(x21,x22,…,x2n)間的標準化歐氏距離的公式：　

（2）曼哈頓距離。曼哈頓距離的正式意義為L1-距離或城市區塊距離(City Block distance)，也就是在歐幾里得空間的固定直角坐標系上兩點所形成的線段對坐標軸產生的投影的距離總和。例如在平面上，坐標（x1,y1）的點P1與坐標（x2,y2）的點P2的曼哈頓距離為：，要注意的是，曼哈頓距離依賴坐標系統的轉度，而非系統在坐標軸上的平移或映射。

• 二維平面兩點a(x1,y1)與b(x2,y2)間的曼哈頓距離：

• 兩個n維向量a(x11,x12,…,x1n)與 b(x21,x22,…,x2n)間的曼哈頓距離：

（3）切比雪夫距離。若二個向量或二個點p、q，其座標分別為 及 ，則兩者之間的切比雪夫距離定義如下：

這也等于以下Lp度量的極值： 因此切比雪夫距離也稱為L∞度量。

以數學的觀點來看，切比雪夫距離是由一致范數（uniform norm）（或稱為上確界范數）所衍生的度量，也是超凸度量（injective metric space）的一種。

在平面幾何中，若二點p及q的直角坐標系坐標為 及，則切比雪夫距離為：。

在國際象棋中，國王走一步能夠移動到相鄰的8個方格中的任意一個。那么國王從格子(x1,y1)走到格子(x2,y2)最少需要的步數總是max(|x2-x1|,|y2-y1|)步。有一種類似的一種距離度量方法叫切比雪夫距離。

• 二維平面兩點a(x1,y1)與b(x2,y2)間的切比雪夫距離：

• 兩個n維向量a(x11,x12,…,x1n)與 b(x21,x22,…,x2n)間的切比雪夫距離：

這個公式的另一種等價形式是

在閔可夫斯基距離中，最常用的是歐氏距離，它的主要優點是當坐標軸進行正交旋轉時，歐氏距離是保持不變的。因此，如果對原坐標系進行平移和旋轉變換，則變換后樣本點間的距離和變換前完全相同。

值得注意的是，在采用閔可夫斯基距離時，一定要采用相同量綱的變量。如果變量的量綱不同，測量值變異范圍相差懸殊時，建議首先進行數據的標準化處理，然后再計算距離。在采用閔可夫斯基距離時，還應盡可能地避免變量的多重相關性（multi-collinearity）。多重相關性所造成的信息重疊，會片面強調某些變量的重要性。

由于閔可夫斯基距離的這些缺點，一種改進的距離就是馬氏距離。

?相關系數

由于習慣的原因，我們把兩組樣本近似線性的數據的距離稱之為：相關系數。相關系數是衡量相似度的主要指標之一。

相關系數屬于最重要的數據挖掘的概念之一。有兩種重要的相關系數：夾角余弦（又稱為：皮爾遜積矩相關系數）；杰卡德相似系數。其中夾角余弦是在LBS中應用最普遍的相關系數。

1.夾角余弦

在二維空間中向量A(x1,y1)與向量B(x2,y2)的夾角余弦公式：

如果是對于兩組樣本數據來說，兩組n維樣本點a(x11,x12,…,x1n)和b(x21,x22,…,x2n)的夾角余弦

相類似，對于兩個n維樣本點a(x11,x12,…,x1n)和b(x21,x22,…,x2n)，可以使用類似于夾角余弦的概念來衡量它們間的相似程度，即

夾角余弦取值范圍為[-1,1]。夾角余弦越大表示兩個向量的夾角越小，夾角余弦越小表示兩向量的夾角越大。當兩個向量的方向重合時夾角余弦取最大值1，當兩個向量的方向完全相反夾角余弦取最小值-1。

如果將夾角余弦的概念再引申一下，引申到兩組數據的回歸直線的夾角的余弦，則得到了皮爾遜積矩相關系數（又稱作PPMCC或PCC，一般簡稱為相關系數），用于度量兩個變量X和Y之間的相關（線性相關）。在LBS中，該系數廣泛用于度量兩個變量之間的相關程度。如圖1所示。

圖1回歸直線

回歸直線： y=f(x)和 x=f(y)。其中：ax、bx與ay、by屬于線性回歸方程的系數。

相關系數是兩組數據的中心化后的夾角的余弦值，即：等于兩條回歸線y=f(x) 和 x=f(y) 夾角的余弦值。

具體地說，相關系數等于兩個變量之間的協方差和標準差的商：

相關距離的定義是：

以上方程定義了總體相關系數, 一般表示成希臘字母ρ(rho)。基于樣本對協方差和方差進行估計時, 一般表示成r：

一種等價表達式的是表示成標準分的均值。基于(Xi, Yi)的樣本點，樣本皮爾遜系數是

其中 、及分別是標準分、樣本平均值和樣本標準差。

（1）相關系數的適用范圍。

當兩個變量的標準差都不為零時，相關系數才有定義，皮爾遜相關系數適用于：

1.兩個變量之間是線性關系，都是連續數據。

2.兩個變量的總體是正態分布，或接近正態的單峰分布。

3.兩個變量的觀測值是成對的，每對觀測值之間相互獨立。

（2）相關系數的應用。

比如：有5個國家的儲蓄分別為 1, 2, 3, 5 和 8 億元。 假設這5個國家的貧困百分比分別為 11%, 12%, 13%, 15%, 和18% 。

令 x 和 y 分別為包含上述5個數據的向量: x = (1, 2, 3, 5, 8) 和 y = (0.11, 0.12, 0.13, 0.15, 0.18)。

利用通常的方法計算兩個向量之間的夾角, 未中心化的相關系數是:

將數據中心化 ，即：通過E(x) = 3.8移動 x 和通過 E(y) = 0.138 移動 y ，得到：

x = (?2.8, ?1.8, ?0.8, 1.2, 4.2) ；

y = (?0.028, ?0.018, ?0.008, 0.012, 0.042)。

從而：

推薦系統的設計

推薦引擎分以下兩類。

第一類稱為協同過濾，即基于相似用戶的協同過濾推薦（盡最大可能發現用戶間的相似度），以及基于相似物品的協同過濾推薦（盡最大可能發現物品間的相似度）。

第二類是基于內容分析的推薦（調查問卷、電子郵件，或者其他基于內容特征的分析）。

協同過濾

基于協同過濾的推薦在本質上仍是計算相關系數。在小規模實現時，考慮計算其相關系數；在大規模的實現時，考慮使用邏輯回歸算法（這也是淘寶/亞馬遜/facebook所采用的算法，本質上屬于單層采用Sigmoid型激發函數的神經網絡，訓練數據時，輸出可以是推薦的商品，輸入最好是比商品更多的特征維度，比如十億以上的維度）。

（1）協同過濾的種類

協同過濾可分為以下三個子類。

• 基于用戶（user）的推薦：這種推薦是通過共同口味與偏好找相似鄰居用戶，常使用K-近鄰算法。要達到的效果是：因為你的朋友喜歡，所以推測你可能也喜歡；
• 基于物品（item）的推薦：這種推薦是要發現物品之間的相似度，從而推薦類似的物品。要達到的效果是：因為你喜歡物品A，又因為C與A相似，所以推測你可能也喜歡C；
• 基于模型的推薦：這種推薦是要基于樣本的用戶喜好信息構造一個推薦模型，然后根據實時的用戶喜好信息預測推薦。

（2）做協同過濾推薦應考慮的因素

上述幾種推薦在使用時，要考慮以下因素。精確度（Accuracy）：選擇基于數量較少的因子來建立推薦算法；

• 效率（Efficiency）：效率；
  
• 穩定性（Stability）：選擇基于變動頻度較低的因子來建立推薦算法。例如，如果商品基本固定，用戶不斷變化，則選擇基于item的算法；
  
• 說服力（Justifiability）：如果要考慮說服力，則優先選擇基于item的算法，因為比較容易理解；例如，因為你喜歡三星Galaxy，所以給你推薦HTC One；
  

• 驚喜度（Serendipity）：如果要考慮驚喜度，則優先選擇基于用戶的推薦。

在工業界，通常采用的推薦算法如下：

• 多種算法融合+ 統一模型（Model）→劃分等級（Ranking/Filtering）；
• 通過不同的輸出來決定使用不同的算法。

（3）做協同過濾推薦的步驟

1）若要做協同過濾，那么收集用戶偏好則是關鍵。可以通過用戶的行為諸如評分（如不同的用戶對不同的作品有不同的評分，而評分接近則意味著喜好口味相近，便可判定為相似用戶）、投票、轉發、保存、書簽、標記、評論、點擊流、頁面停留時間、是否購買等獲得。

2）收集用戶行為數據之后，接下來便要對數據進行減噪與歸一化操作（得到一個用戶偏好的二維矩陣，一維是用戶列表，另一維是物品列表，值是用戶對物品的偏好，一般是 [0,1] 或者[?1, 1]的浮點數值）。

3）計算相似用戶或相似物品的相似度。

4）計算出來的這兩個相似度將作為基于用戶、物品的兩項協同過濾的推薦。

基于內容的推薦

所謂內容（Content），是指能夠描述用戶/物品的特征，比如：

對于物品來說，要考慮的內容特征有以下三項。

（1）電影

對電影來說，需要考慮的特征如下。

• 電影：紅番區；
• 類型：動作/冒險；
  
• 演員：成龍；
  
• 年份：1997。

（2）文本

對文本來說，需要考慮的特征如下。

• 詞性；
• 單詞轉化為向量（Word2vec）；
  
• 主題。

（3）多媒體

對多媒體來說，需要考慮的特征如下。

• Audio；
• 圖片像素。
  

總的來說，對用戶特征來說，要考慮的內容特征如圖2所示。

圖2 ?用戶特征

將用戶或物品的特征進行統一表示（例如表示成特征向量），即可利用相似度來進行等級（ranking）劃分，從而推薦。

總的來說，協同過濾往往沒有考慮用戶或物品本身的特征，但能保證有一定的驚喜度。而基于內容的推薦能夠充分應用物品（item）和用戶自身的特征信息，且能夠提供明確的推薦理由，但是容易推薦過于一致的結果。

綜上所述，我們已經把推薦系統的數學基礎和設計原理講完了。為了讀者能深入了解推薦系統的設計，我們可訪問《推薦系統的應用案例剖析》一文，了解更多推薦系統應用案例。

作者簡介

賈雙成，阿里巴巴資深工程師，擅長于數據編譯、數據挖掘的系統分析和架構設計，主持研發過多個高端車載導航及adas數據編譯器。曾發表發明專利、論文四十余篇，著有《LBS核心技術揭秘》、《數據挖掘核心技術揭秘》。

本文為CSDN原創文章，未經允許不得轉載，如需轉載請聯系market#csdn.net(#換成@)

總結

以上是生活随笔為你收集整理的LBS推荐系统的设计方法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。