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

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

希望通過這兩期的介紹，讀者可以明白一個(gè)推薦系統(tǒng)的設(shè)計(jì)原理，以及如何應(yīng)用。在本期中我們將首先講述推薦系統(tǒng)的前世今生，之后講述推薦系統(tǒng)的數(shù)學(xué)基礎(chǔ)，最后講述推薦系統(tǒng)的設(shè)計(jì)原理。

推薦系統(tǒng)的前世今生

隨著互聯(lián)網(wǎng)的發(fā)展，人們正處于一個(gè)信息爆炸的時(shí)代。相比于過去的信息匱乏，面對(duì)現(xiàn)階段海量的信息數(shù)據(jù)，對(duì)信息的篩選和過濾成為了衡量一個(gè)系統(tǒng)好壞的重要指標(biāo)。一個(gè)具有良好用戶體驗(yàn)的系統(tǒng)，會(huì)將海量信息進(jìn)行篩選、過濾，將用戶最關(guān)注最感興趣的信息展現(xiàn)在用戶面前。這大大增加了系統(tǒng)工作的效率，也節(jié)省了用戶篩選信息的時(shí)間。

搜索引擎的出現(xiàn)在一定程度上解決了信息篩選問題，但還遠(yuǎn)遠(yuǎn)不夠。搜索引擎需要用戶主動(dòng)提供關(guān)鍵詞來對(duì)海量信息進(jìn)行篩選。當(dāng)用戶無法準(zhǔn)確描述自己的需求時(shí)，搜索引擎的篩選效果將大打折扣，而用戶將自己的需求和意圖轉(zhuǎn)化成關(guān)鍵詞的過程本身就是一個(gè)并不輕松的過程。

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

推薦系統(tǒng)的數(shù)學(xué)基礎(chǔ)

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

距離

距離是聚類的基礎(chǔ),是最重要的數(shù)據(jù)挖掘中最重要的概念之一，也是衡量相似度的主要指標(biāo)之一。距離有很多種，各種距離的應(yīng)用場(chǎng)景可以簡(jiǎn)單概括為：

空間：歐氏距離；

路徑：曼哈頓距離；

國(guó)際象棋國(guó)王：切比雪夫距離；

歐氏距離、曼哈頓距離、切比雪夫距離三種距離的統(tǒng)一形式：閔可夫斯基距離；

加權(quán)：標(biāo)準(zhǔn)化歐氏距離；

排除量綱和依存：馬氏距離；

編碼差別：漢明距離。

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

1.閔可夫斯基距離

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

其中p是一個(gè)變參數(shù)。

當(dāng)p=1時(shí)，就是曼哈頓距離

當(dāng)p=2時(shí)，就是歐氏距離

當(dāng)p→∞時(shí)，就是切比雪夫距離

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

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

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

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

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

也可以用表示成向量運(yùn)算的形式：

標(biāo)準(zhǔn)化歐氏距離(Standardized Euclidean distance)是針對(duì)簡(jiǎn)單歐氏距離的缺點(diǎn)而作的一種改進(jìn)方案。標(biāo)準(zhǔn)歐氏距離的思路：既然數(shù)據(jù)各維分量的分布不一樣，那先將各個(gè)分量都“標(biāo)準(zhǔn)化”到均值、方差相等。

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

即樣本集的標(biāo)準(zhǔn)化過程(standardization)用公式描述就是：

標(biāo)準(zhǔn)化后的值=(標(biāo)準(zhǔn)化前的值－分量的均值) /分量的標(biāo)準(zhǔn)差

經(jīng)過簡(jiǎn)單的推導(dǎo)就可以得到兩個(gè)n維向量a(x11,x12,…,x1n)與 b(x21,x22,…,x2n)間的標(biāo)準(zhǔn)化歐氏距離的公式：

（2）曼哈頓距離。曼哈頓距離的正式意義為L(zhǎng)1-距離或城市區(qū)塊距離(City Block distance)，也就是在歐幾里得空間的固定直角坐標(biāo)系上兩點(diǎn)所形成的線段對(duì)坐標(biāo)軸產(chǎn)生的投影的距離總和。例如在平面上，坐標(biāo)（x1,y1）的點(diǎn)P1與坐標(biāo)（x2,y2）的點(diǎn)P2的曼哈頓距離為：

，要注意的是，曼哈頓距離依賴坐標(biāo)系統(tǒng)的轉(zhuǎn)度，而非系統(tǒng)在坐標(biāo)軸上的平移或映射。

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

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

（3）切比雪夫距離。若二個(gè)向量或二個(gè)點(diǎn)p、q，其座標(biāo)分別為 及 ，則兩者之間的切比雪夫距離定義如下：

這也等于以下Lp度量的極值：

因此切比雪夫距離也稱為L(zhǎng)∞度量。

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

在平面幾何中，若二點(diǎn)p及q的直角坐標(biāo)系坐標(biāo)為

及

，則切比雪夫距離為：

。

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

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

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

這個(gè)公式的另一種等價(jià)形式是

在閔可夫斯基距離中，最常用的是歐氏距離，它的主要優(yōu)點(diǎn)是當(dāng)坐標(biāo)軸進(jìn)行正交旋轉(zhuǎn)時(shí)，歐氏距離是保持不變的。因此，如果對(duì)原坐標(biāo)系進(jìn)行平移和旋轉(zhuǎn)變換，則變換后樣本點(diǎn)間的距離和變換前完全相同。

值得注意的是，在采用閔可夫斯基距離時(shí)，一定要采用相同量綱的變量。如果變量的量綱不同，測(cè)量值變異范圍相差懸殊時(shí)，建議首先進(jìn)行數(shù)據(jù)的標(biāo)準(zhǔn)化處理，然后再計(jì)算距離。在采用閔可夫斯基距離時(shí)，還應(yīng)盡可能地避免變量的多重相關(guān)性（multi-collinearity）。多重相關(guān)性所造成的信息重疊，會(huì)片面強(qiáng)調(diào)某些變量的重要性。

由于閔可夫斯基距離的這些缺點(diǎn)，一種改進(jìn)的距離就是馬氏距離。

相關(guān)系數(shù)

由于習(xí)慣的原因，我們把兩組樣本近似線性的數(shù)據(jù)的距離稱之為：相關(guān)系數(shù)。相關(guān)系數(shù)是衡量相似度的主要指標(biāo)之一。

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

1.夾角余弦

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

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

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

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

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

圖1回歸直線

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

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

具體地說，相關(guān)系數(shù)等于兩個(gè)變量之間的協(xié)方差和標(biāo)準(zhǔn)差的商：

相關(guān)距離的定義是：

以上方程定義了總體相關(guān)系數(shù), 一般表示成希臘字母ρ(rho)?；跇颖緦?duì)協(xié)方差和方差進(jìn)行估計(jì)時(shí), 一般表示成r：

一種等價(jià)表達(dá)式的是表示成標(biāo)準(zhǔn)分的均值。基于(Xi, Yi)的樣本點(diǎn)，樣本皮爾遜系數(shù)是

其中

、

及

分別是標(biāo)準(zhǔn)分、樣本平均值和樣本標(biāo)準(zhǔn)差。

（1）相關(guān)系數(shù)的適用范圍。

當(dāng)兩個(gè)變量的標(biāo)準(zhǔn)差都不為零時(shí)，相關(guān)系數(shù)才有定義，皮爾遜相關(guān)系數(shù)適用于：

1.兩個(gè)變量之間是線性關(guān)系，都是連續(xù)數(shù)據(jù)。

2.兩個(gè)變量的總體是正態(tài)分布，或接近正態(tài)的單峰分布。

3.兩個(gè)變量的觀測(cè)值是成對(duì)的，每對(duì)觀測(cè)值之間相互獨(dú)立。

（2）相關(guān)系數(shù)的應(yīng)用。

比如：有5個(gè)國(guó)家的儲(chǔ)蓄分別為 1, 2, 3, 5 和 8 億元。 假設(shè)這5個(gè)國(guó)家的貧困百分比分別為 11%, 12%, 13%, 15%, 和18% 。

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

利用通常的方法計(jì)算兩個(gè)向量之間的夾角, 未中心化的相關(guān)系數(shù)是:

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

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

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

從而：

推薦系統(tǒng)的設(shè)計(jì)

推薦引擎分以下兩類。

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

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

協(xié)同過濾

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

（1）協(xié)同過濾的種類

協(xié)同過濾可分為以下三個(gè)子類。

基于用戶（user）的推薦：這種推薦是通過共同口味與偏好找相似鄰居用戶，常使用K-近鄰算法。要達(dá)到的效果是：因?yàn)槟愕呐笥严矚g，所以推測(cè)你可能也喜歡；

基于物品（item）的推薦：這種推薦是要發(fā)現(xiàn)物品之間的相似度，從而推薦類似的物品。要達(dá)到的效果是：因?yàn)槟阆矚g物品A，又因?yàn)镃與A相似，所以推測(cè)你可能也喜歡C；

基于模型的推薦：這種推薦是要基于樣本的用戶喜好信息構(gòu)造一個(gè)推薦模型，然后根據(jù)實(shí)時(shí)的用戶喜好信息預(yù)測(cè)推薦。

（2）做協(xié)同過濾推薦應(yīng)考慮的因素

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

效率（Efficiency）：效率；

穩(wěn)定性（Stability）：選擇基于變動(dòng)頻度較低的因子來建立推薦算法。例如，如果商品基本固定，用戶不斷變化，則選擇基于item的算法；

說服力（Justifiability）：如果要考慮說服力，則優(yōu)先選擇基于item的算法，因?yàn)楸容^容易理解；例如，因?yàn)槟阆矚g三星Galaxy，所以給你推薦HTC One；

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

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

多種算法融合+ 統(tǒng)一模型（Model）→劃分等級(jí)（Ranking/Filtering）；

通過不同的輸出來決定使用不同的算法。

（3）做協(xié)同過濾推薦的步驟

1）若要做協(xié)同過濾，那么收集用戶偏好則是關(guān)鍵?？梢酝ㄟ^用戶的行為諸如評(píng)分（如不同的用戶對(duì)不同的作品有不同的評(píng)分，而評(píng)分接近則意味著喜好口味相近，便可判定為相似用戶）、投票、轉(zhuǎn)發(fā)、保存、書簽、標(biāo)記、評(píng)論、點(diǎn)擊流、頁面停留時(shí)間、是否購(gòu)買等獲得。

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

3）計(jì)算相似用戶或相似物品的相似度。

4）計(jì)算出來的這兩個(gè)相似度將作為基于用戶、物品的兩項(xiàng)協(xié)同過濾的推薦。

基于內(nèi)容的推薦

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

對(duì)于物品來說，要考慮的內(nèi)容特征有以下三項(xiàng)。

（1）電影

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

電影：紅番區(qū)；

類型：動(dòng)作/冒險(xiǎn)；

演員：成龍；

年份：1997。

（2）文本

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

詞性；

單詞轉(zhuǎn)化為向量（Word2vec）；

主題。

（3）多媒體

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

Audio；

圖片像素。

總的來說，對(duì)用戶特征來說，要考慮的內(nèi)容特征如圖2所示。

圖2 ?用戶特征

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

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

綜上所述，我們已經(jīng)把推薦系統(tǒng)的數(shù)學(xué)基礎(chǔ)和設(shè)計(jì)原理講完了。為了讀者能深入了解推薦系統(tǒng)的設(shè)計(jì)，我們可訪問《推薦系統(tǒng)的應(yīng)用案例剖析》一文，了解更多推薦系統(tǒng)應(yīng)用案例。

作者簡(jiǎn)介

賈雙成，阿里巴巴資深工程師，擅長(zhǎng)于數(shù)據(jù)編譯、數(shù)據(jù)挖掘的系統(tǒng)分析和架構(gòu)設(shè)計(jì)，主持研發(fā)過多個(gè)高端車載導(dǎo)航及adas數(shù)據(jù)編譯器。曾發(fā)表發(fā)明專利、論文四十余篇，著有《LBS核心技術(shù)揭秘》、《數(shù)據(jù)挖掘核心技術(shù)揭秘》。

本文為CSDN原創(chuàng)文章