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

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

2017-05-09 16:49

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

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

介紹

背景

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

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

推薦形式

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

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

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

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

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

主要算法以及介紹

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

協(xié)同過(guò)濾模型

模型介紹

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

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

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

算法邏輯

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

K-means

算法介紹

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

算法邏輯

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

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

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

K-Means算法在實(shí)際運(yùn)行的過(guò)程中存在以下幾個(gè)問(wèn)題

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

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

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

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

SVD

算法介紹

特征值分解是一個(gè)提取矩陣特征很不錯(cuò)的方法，但是它只是對(duì)方陣而言的，在現(xiàn)實(shí)的世界中，我們看到的大部分矩陣都不是方陣，比如說(shuō)有N個(gè)學(xué)生，每個(gè)學(xué)生有M科成績(jī)，這樣形成的一個(gè)N*M的矩陣就不可能是方陣，我們?cè)鯓硬拍苊枋鲞@樣普通的矩陣呢的重要特征呢？奇異值分解可以用來(lái)干這個(gè)事情，奇異值分解是一個(gè)能適用于任意的矩陣的一種分解的方法。

算法邏輯

算法公式：

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

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

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

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

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

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

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

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

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

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

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

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

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

代碼樣例

公共函數(shù)

該部分主要是用來(lái)加載樣本數(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 分類器
# 測(cè)試集： testdata；訓(xùn)練集： trainSet；類別標(biāo)簽： listClasses； k:k 個(gè)鄰居數(shù)
def classify(testdata, trainSet, listClasses, k):
dataSetSize = trainSet.shape[0] # 返回樣本集的行數(shù)
distances = array(zeros(dataSetSize))
for indx in xrange(dataSetSize): # 計(jì)算測(cè)試集與訓(xùn)練集之間的距離：夾角余弦
distances[indx] = cosdist(testdata,trainSet[indx])
# 根據(jù)生成的夾角余弦按從大到小排序,結(jié)果為索引號(hào)
sortedDistIndicies = argsort(-distances)
classCount={}
for i in range(k): # 獲取角度最小的前 k 項(xiàng)作為參考項(xiàng)
# 按排序順序返回樣本集對(duì)應(yīng)的類別標(biāo)簽
voteIlabel = listClasses[sortedDistIndicies[i]]
# 為字典 classCount 賦值,相同 key，其 value 加 1
classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
# 對(duì)分類字典 classCount 按 value 重新排序
# sorted(data.iteritems(), key=operator.itemgetter(1), reverse=True)
# 該句是按字典值排序的固定用法
# classCount.iteritems()：字典迭代器函數(shù)
# key：排序參數(shù)； operator.itemgetter(1)：多級(jí)排序
sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
return sortedClassCount[0][0] # 返回序最高的一項(xiàng)

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個(gè)U,S,V的值
Vr=V[:,:r]
testresult=data_point*Ur*np.linalg.inv(Sr) # 計(jì)算data_point的坐標(biāo)
resultarray=array([comsSim(testresult,vi) for vi in Vr]) # 計(jì)算距離
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ò)算法高級(jí)應(yīng)用班” 要開(kāi)課啦！

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

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

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