從理論到實踐,一文詳解 AI 推薦系統的三大算法

雷鋒網按：本文作者孫愛華，原文載於作者個人博客，雷鋒網(公眾號：雷鋒網)已獲授權。

  介紹

背景

隨著網際網路行業的井噴式發展，獲取信息的方式越來越多，人們從主動獲取信息逐漸變成了被動接受信息，信息量也在以幾何倍數式爆發增長。舉一個例子，PC時代用google reader，常常有上千條未讀博客更新；如今的微信公眾號，也有大量的紅點未閱讀。垃圾信息越來越多，導致用戶獲取有價值信息的成本大大增加。為了解決這個問題，我個人就採取了比較極端的做法：直接忽略所有推送消息的入口。但在很多時候，有效信息的獲取速度極其重要。

由於信息的爆炸式增長，對信息獲取的有效性，針對性的需求也就自然出現了。推薦系統應運而生。

推薦形式

電商網站常見的推薦形式包括三種： 

- 針對用戶的瀏覽、搜索等行為所做的相關推薦； 

- 根據購物車或物品收藏所做的相似物品推薦； 

- 根據歷史會員購買行為記錄，利用推薦機製做EDM或會員營銷。

前面2種表現形式是大家可以在網站上看到，而第3種表現形式只有體驗後才能知曉，一封郵件，一條簡訊，一條站內消息都是它的表現方式。

下面將對亞馬遜中國的前兩種表現形式進行簡單說明：

● 對於非登錄用戶，亞馬遜中國在網站首頁和類目欄，會根據各個類目暢銷品的情況做響應的推薦，其主要表現形式為排行榜。搜索瀏覽頁面以及具體的產品頁面的推薦形式則有關聯推薦（「經常一起購買的商品」）和基於人群偏好的相似性推薦（「購買此物品的顧客也購買了」、「看過此商品的顧客購買的其他商品」）。

● 對於登錄用戶，亞馬遜中國則給出了完全不同的推薦方式，網站會根據用戶的歷史瀏覽記錄在登入界面首屏展現出一個今日推薦的欄目，緊接著是最近一次瀏覽商品的記錄和根據該物品所給的產品推薦（「根據瀏覽推薦給我的商品」、「瀏覽XX產品的用戶會買XX的概率」），值得注意的是，每個頁面最下方網站都會根據用戶的瀏覽行為做響應推薦，如果沒有瀏覽記錄則會推薦「系統暢銷品」（13頁，50款商品）。

  推薦系統的架構

推薦系統常見的架構體系如下： 

從架構圖可以看出，一個簡單的推薦系統通常包括三個部分

1. 數據來源 

該部分至少包括三部分內容:

● 物品信息 

● 用戶信息，例如用戶愛好，瀏覽記錄，購買記錄等 

● 用戶的物品的偏好，例如 商品評分，商品評論等

2. 算法處理：常見的算法類型主要包括

● 人口統計學推薦：主要是根據用戶資料信息，發現和物品的相關程度

● 物品內容推薦：根據用戶的偏好，推薦相似的物品給用戶

● 協同過濾推薦：根據用戶對物品的偏好，發現物品或是用戶的相關性，然後基於相關性進行推薦，主要包括:1:基於用戶的推薦 2:基於物品的推薦

● SVD(奇異值分解):相當於協同過濾的相似度計算模型，主要基於用戶和物品信息構成的矩陣，矩陣中的值是用戶對商品的評分，這個矩陣通常是一個比較稀疏的矩陣，通過SVD算法可以得到用戶與物品的特徵向量PU(用戶的偏好)，PI（物品的偏好）通過PU*PI得到用戶對物品的評分預測

3. 結果展示：對推薦結果進行展示

  主要算法以及介紹

本章節主要介紹 協同過濾，SVD, K-Means 三種算法

協同過濾模型

模型介紹

協同過濾Collaborative Filtering (CF)算法是推薦算法的一個大分支，基本思想是推薦相似的物品，或者推薦相似用戶（隱式或者顯式）評分過的物品。CF方法主要可以分為兩類：基於鄰域和基於隱語義。

1. 基於鄰域的方法利用「兩個用戶共同評分過的物品」(user-based)或者「共同評價兩個物品的用戶」（item-based）分別計算用戶間的相似度和物品間的相似度。而相似度的計算有餘弦相似度，皮爾遜相似度和一種被稱為「Conditional Probability-Based「的Similarity。皮爾遜係數與餘弦相似度的不同在於，皮爾遜係數還能捕捉負關係,第三個方法的弊端在於由於每個物品（人）鄰域的大小不同，流行物品或評分多的用戶會引起問題。因此，實際中一般採用帶權的皮爾遜相似度(P. 2) 。但基於鄰域方法的缺點是：由於實際用戶評分的數據是十分稀疏，用戶之間可能根本沒有相同的評論；而且用啟發式的方法很難考慮全面用戶和物品之間的所有關係。

2. 基於隱語義的方法則不依賴於共同評分。其基本思想是將用戶和物品分別映射到某種真實含義未知的feature向量。用戶feature代表用戶對不同類別電影的喜好程度（如：動作片5，驚悚片5），物品feature代表電影中大致屬於哪類電影（如：愛情片3，喜劇片5）。然後通過兩個feature向量的內積來判斷用戶對一個物品的喜好程度。雖然這個方法不要求共同評分，但推薦系統還是面臨很大的數據稀疏問題。

算法邏輯

作為CF的兩大基本分類，鄰域的相關算法比較簡單不再介紹，本文主要介紹SVD，不過在介紹SVD之前，先對K-Means做個簡單的說明

K-means

算法介紹

推薦系統大多數都是基於海量的數據進行處理和計算，要在海量數據的基礎上進行協同過濾的相關處理，運行效率會很低，為了解決這個問題通常是先使用K-means對數據進行聚類操作，說白了，就是按照數據的屬性通過K-Means算法把數據先分成幾大類，然後再在每個大類中通過鄰域或是隱語義算法進行推薦

算法邏輯

網上有很多關於K-Means算法的描述，個人覺得大多數都很拗口，不容易理解，下面這個圖中舉例的方式，感覺比較容易理解 

在Python的sklearn庫中已經實現了該算法，如果有興趣也可以實現一個自己的K-Means算法。

K-Means算法在實際運行的過程中存在以下幾個問題 

1. 最大問題是：K值對最後的結果影響較大，但是該值是由用戶確定的，且不同的數據集，該值沒有可借鑑性 

2. 對離群數據點敏感，就算少量的離群數據也能對結果造成較大的影響 

3. 算法初始化中心點的選擇好壞，會直接影響到最終程序的效率

為了解決上面的問題，出現了二分KMeans算法，有興趣的讀者，可以自行尋找相關的資料 ，本文不做詳細介紹

SVD

算法介紹

特徵值分解是一個提取矩陣特徵很不錯的方法，但是它只是對方陣而言的，在現實的世界中，我們看到的大部分矩陣都不是方陣，比如說有N個學生，每個學生有M科成績，這樣形成的一個N*M的矩陣就不可能是方陣，我們怎樣才能描述這樣普通的矩陣呢的重要特徵呢？奇異值分解可以用來幹這個事情，奇異值分解是一個能適用於任意的矩陣的一種分解的方法。

算法邏輯

算法公式： 

公式說明：假設A是一個N * M的矩陣，那麼得到的U是一個N * N的方陣（裡面的向量是正交的，U裡面的向量稱為左奇異向量），Σ是一個N * M的矩陣（除了對角線的元素都是0，對角線上的元素稱為奇異值），V』(V的轉置)是一個N * N的矩陣，裡面的向量也是正交的，V裡面的向量稱為右奇異向量），從圖片來反映幾個相乘的矩陣的大小可得下面的圖片 

那麼奇異值和特徵值是怎麼對應起來的呢？首先，我們將一個矩陣A的轉置 *A，將會得到一個方陣，我們用這個方陣求特徵值可以得到： 

這裡得到的v，就是我們上面的右奇異向量。此外我們還可以得到：

這裡的σ就是上面說的奇異值，u就是上面說的左奇異向量。奇異值σ跟特徵值類似，在矩陣Σ中也是從大到小排列，而且σ的減少特別的快，在很多情況下，前10%甚至1%的奇異值的和就佔了全部的奇異值之和的99%以上了。也就是說，我們也可以用前r大的奇異值來近似描述矩陣，這裡定義一下部分奇異值分解 

r是一個遠小於m、n的數，這樣矩陣的乘法看起來像是下面的樣子

邊的三個矩陣相乘的結果將會是一個接近於A的矩陣，在這兒，r越接近於n，則相乘的結果越接近於A。而這三個矩陣的面積之和（在存儲觀點來說，矩陣面積 越小，存儲量就越小）要遠遠小於原始的矩陣A，我們如果想要壓縮空間來表示原矩陣A，我們存下這裡的三個矩陣：U、Σ、V就好了。

在Numpy的linalg中，已經對SVD進行了實現，可直接進行使用

  代碼樣例

公共函數

該部分主要是用來加載樣本數據的代碼

def load_test_data():

matrix=[[0.238,0,0.1905,0.1905,0.1905,0.1905],[0,0.177,0,0.294,0.235,0.294],[0.2,0.16,0.12,0.12,0.2,0.2],[0.2,0.16,0.12,0.12,0.2,0.1]]

return matrix

使用鄰域法進行推薦

# 夾角餘弦距離公式

def cosdist(vector1,vector2):

    return dot(vector1,vector2)/(linalg.norm(vector1)*linalg.norm(vector2))

# kNN 分類器

# 測試集： testdata；訓練集： trainSet；類別標籤： listClasses； k:k 個鄰居數

def classify(testdata, trainSet, listClasses, k):

    dataSetSize = trainSet.shape[0] # 返回樣本集的行數

    distances = array(zeros(dataSetSize))

    for indx in xrange(dataSetSize): # 計算測試集與訓練集之間的距離：夾角餘弦

        distances[indx] = cosdist(testdata,trainSet[indx])

        # 根據生成的夾角餘弦按從大到小排序,結果為索引號

        sortedDistIndicies = argsort(-distances)

    classCount={}

    for i in range(k): # 獲取角度最小的前 k 項作為參考項

        # 按排序順序返回樣本集對應的類別標籤

        voteIlabel = listClasses[sortedDistIndicies[i]]

        # 為字典 classCount 賦值,相同 key，其 value 加 1

        classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1

    # 對分類字典 classCount 按 value 重新排序

    # sorted(data.iteritems(), key=operator.itemgetter(1), reverse=True)

    # 該句是按字典值排序的固定用法

    # classCount.iteritems()：字典迭代器函數

    # key：排序參數； operator.itemgetter(1)：多級排序

    sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)

    return sortedClassCount[0][0] # 返回序最高的一項

if __name__ == '__main__':

    # 使用領域算法進行推薦

    recommand_by_distance()

使用SVD進行推薦

def comsSim(vecA,vecB):

    eps=1.0e-6

    a=vecA[0]

    b=vecB[0]

    return dot(a,b)/((np.linalg.norm(a)*np.linalg.norm(b))+eps)

def recommand_by_svd():

    r=1

    dataset=np.mat(load_test_data())

    data_point=np.mat([[0.2174,0.2174,0.1304,0,0.2174,0.2174]])

    m,n=np.shape(dataset)

    limit=min(m,n)

    if r>limit:r=limit

    U,S,VT=np.linalg.svd(dataset.T) #SVD 分解

    V=VT.T

    Ur=U[:,:r]

    Sr=np.diag(S)[:r,:r]  #取前r個U,S,V的值

    Vr=V[:,:r]

    testresult=data_point*Ur*np.linalg.inv(Sr)  # 計算data_point的坐標

    resultarray=array([comsSim(testresult,vi) for vi in Vr]) # 計算距離

    descindx=argsort(-resultarray)[:1]

    print descindx

    # print resultarray

    print resultarray[descindx]

if __name__ == '__main__':

    # 使用SVD算法進行推薦

    recommand_by_svd()

TensorFlow & 神經網絡算法高級應用班」 要開課啦！

從初級到高級，理論 + 實戰，一站式深度了解 TensorFlow！

本課程面向深度學習開發者，講授如何利用 TensorFlow 解決圖像識別、文本分析等具體問題。課程跨度為 10 周，將從 TensorFlow 的原理與基礎實戰技巧開始，一步步教授學員如何在 TensorFlow 上搭建 CNN、自編碼、RNN、GAN 等模型，並最終掌握一整套基於 TensorFlow 做深度學習開發的專業技能。

兩名授課老師佟達、白髮川身為 ThoughtWorks 的資深技術專家，具有豐富的大數據平臺搭建、深度學習系統開發項目經驗。

時間：每周二、四晚 20：00-21：00

開課時長：總學時 20 小時，分 10 周完成，每周 2 次，每次 1 小時

線上授課地址：http://www.mooc.ai/

雷鋒網(公眾號：雷鋒網)相關閱讀：

機器學習算法實踐 K均值聚類的實用技巧

PRICAI 2016 論文精選 | 基於稀鬆K-SVD算法的自發性微表情識別

雷鋒網版權文章，未經授權禁止轉載。詳情見轉載須知。