從理論到實踐，一文詳解 AI 推薦系統(tǒng)的三大算法

本文作者： AI研習(xí)社

2017-05-09 16:49

導(dǎo)語：由于信息的爆炸式增長，對信息獲取的有效性、針對性的需求也就自然出現(xiàn)了。

雷鋒網(wǎng)按：本文作者孫愛華，原文載于作者個人博客，雷鋒網(wǎng)已獲授權(quán)。

介紹

背景

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

由于信息的爆炸式增長，對信息獲取的有效性，針對性的需求也就自然出現(xiàn)了。推薦系統(tǒng)應(yīng)運而生。

推薦形式

電商網(wǎng)站常見的推薦形式包括三種：

- 針對用戶的瀏覽、搜索等行為所做的相關(guān)推薦；
- 根據(jù)購物車或物品收藏所做的相似物品推薦；
- 根據(jù)歷史會員購買行為記錄，利用推薦機制做EDM或會員營銷。

前面2種表現(xiàn)形式是大家可以在網(wǎng)站上看到，而第3種表現(xiàn)形式只有體驗后才能知曉，一封郵件，一條短信，一條站內(nèi)消息都是它的表現(xiàn)方式。

下面將對亞馬遜中國的前兩種表現(xiàn)形式進(jìn)行簡單說明：

● 對于非登錄用戶，亞馬遜中國在網(wǎng)站首頁和類目欄，會根據(jù)各個類目暢銷品的情況做響應(yīng)的推薦，其主要表現(xiàn)形式為排行榜。搜索瀏覽頁面以及具體的產(chǎn)品頁面的推薦形式則有關(guān)聯(lián)推薦（“經(jīng)常一起購買的商品”）和基于人群偏好的相似性推薦（“購買此物品的顧客也購買了”、“看過此商品的顧客購買的其他商品”）。
● 對于登錄用戶，亞馬遜中國則給出了完全不同的推薦方式，網(wǎng)站會根據(jù)用戶的歷史瀏覽記錄在登入界面首屏展現(xiàn)出一個今日推薦的欄目，緊接著是最近一次瀏覽商品的記錄和根據(jù)該物品所給的產(chǎn)品推薦（“根據(jù)瀏覽推薦給我的商品”、“瀏覽XX產(chǎn)品的用戶會買XX的概率”），值得注意的是，每個頁面最下方網(wǎng)站都會根據(jù)用戶的瀏覽行為做響應(yīng)推薦，如果沒有瀏覽記錄則會推薦“系統(tǒng)暢銷品”（13頁，50款商品）。

主要算法以及介紹

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

協(xié)同過濾模型

模型介紹

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

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

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

算法邏輯

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

K-means

算法介紹

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

算法邏輯

網(wǎng)上有很多關(guān)于K-Means算法的描述，個人覺得大多數(shù)都很拗口，不容易理解，下面這個圖中舉例的方式，感覺比較容易理解

從理論到實踐，一文詳解 AI 推薦系統(tǒng)的三大算法

在Python的sklearn庫中已經(jīng)實現(xiàn)了該算法，如果有興趣也可以實現(xiàn)一個自己的K-Means算法。

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

1. 最大問題是：K值對最后的結(jié)果影響較大，但是該值是由用戶確定的，且不同的數(shù)據(jù)集，該值沒有可借鑒性

2. 對離群數(shù)據(jù)點敏感，就算少量的離群數(shù)據(jù)也能對結(jié)果造成較大的影響

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

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

SVD

算法介紹

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

算法邏輯

算法公式：

從理論到實踐，一文詳解 AI 推薦系統(tǒng)的三大算法

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

從理論到實踐，一文詳解 AI 推薦系統(tǒng)的三大算法

那么奇異值和特征值是怎么對應(yīng)起來的呢？首先，我們將一個矩陣A的轉(zhuǎn)置 *A，將會得到一個方陣，我們用這個方陣求特征值可以得到：

從理論到實踐，一文詳解 AI 推薦系統(tǒng)的三大算法

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

從理論到實踐，一文詳解 AI 推薦系統(tǒng)的三大算法

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

從理論到實踐，一文詳解 AI 推薦系統(tǒng)的三大算法

r是一個遠(yuǎn)小于m、n的數(shù)，這樣矩陣的乘法看起來像是下面的樣子

從理論到實踐，一文詳解 AI 推薦系統(tǒng)的三大算法

邊的三個矩陣相乘的結(jié)果將會是一個接近于A的矩陣，在這兒，r越接近于n，則相乘的結(jié)果越接近于A。而這三個矩陣的面積之和（在存儲觀點來說，矩陣面積越小，存儲量就越?。┮h(yuǎn)遠(yuǎn)小于原始的矩陣A，我們?nèi)绻胍獕嚎s空間來表示原矩陣A，我們存下這里的三個矩陣：U、Σ、V就好了。

在Numpy的linalg中，已經(jīng)對SVD進(jìn)行了實現(xiàn)，可直接進(jìn)行使用

代碼樣例

公共函數(shù)

該部分主要是用來加載樣本數(shù)據(jù)的代碼

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

使用鄰域法進(jìn)行推薦

# 夾角余弦距離公式
def cosdist(vector1,vector2):
return dot(vector1,vector2)/(linalg.norm(vector1)*linalg.norm(vector2))

# kNN 分類器
# 測試集： testdata；訓(xùn)練集： trainSet；類別標(biāo)簽： listClasses； k:k 個鄰居數(shù)
def classify(testdata, trainSet, listClasses, k):
dataSetSize = trainSet.shape[0] # 返回樣本集的行數(shù)
distances = array(zeros(dataSetSize))
for indx in xrange(dataSetSize): # 計算測試集與訓(xùn)練集之間的距離：夾角余弦
distances[indx] = cosdist(testdata,trainSet[indx])
# 根據(jù)生成的夾角余弦按從大到小排序,結(jié)果為索引號
sortedDistIndicies = argsort(-distances)
classCount={}
for i in range(k): # 獲取角度最小的前 k 項作為參考項
# 按排序順序返回樣本集對應(yīng)的類別標(biāo)簽
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()：字典迭代器函數(shù)
# key：排序參數(shù)； operator.itemgetter(1)：多級排序
sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
return sortedClassCount[0][0] # 返回序最高的一項

if __name__ == '__main__':
# 使用領(lǐng)域算法進(jìn)行推薦
recommand_by_distance()

使用SVD進(jìn)行推薦

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的坐標(biāo)
resultarray=array([comsSim(testresult,vi) for vi in Vr]) # 計算距離
descindx=argsort(-resultarray)[:1]
print descindx
# print resultarray
print resultarray[descindx]

if __name__ == '__main__':
# 使用SVD算法進(jìn)行推薦
recommand_by_svd()

TensorFlow & 神經(jīng)網(wǎng)絡(luò)算法高級應(yīng)用班” 要開課啦！

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

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

兩名授課老師佟達(dá)、白發(fā)川身為 ThoughtWorks 的資深技術(shù)專家，具有豐富的大數(shù)據(jù)平臺搭建、深度學(xué)習(xí)系統(tǒng)開發(fā)項目經(jīng)驗。