http://antkillerfarm.github.io/

Kendall秩相關系數（Kendall rank correlation coefficient）

對于秩變量對(xi,yi),(xj,yj)：

(xi?xj)(yi?yj)???>0,=0,<0,concordantneither concordant nor discordantdiscordant

τ=(number of concordant pairs)?(number of discordant pairs)n(n?1)/2

注：Sir Maurice George Kendall，1907~1983，英國統計學家。這個人職業生涯的大部分時間都是一個公務員，二戰期間出任英國船運協會副總經理。1949年以后擔任倫敦大學教授。

參見：

https://en.wikipedia.org/wiki/Kendall_rank_correlation_coefficient

Tanimoto系數

T(x,y)=|X∩Y||X∪Y|=|X∩Y||X|+|Y|?|X∩Y|=∑xiyi∑x2i????√+∑y2i????√?∑xiyi

該系數由Taffee T. Tanimoto于1960年提出。Tanimoto生平不詳，從名字來看，應該是個日本人。在其他領域，它還有另一個名字Jaccard similarity coefficient。（兩者的系數公式一致，但距離公式略有差異。）

注：Paul Jaccard，1868～1944，蘇黎世聯邦理工學院（ETH Zurich）博士，蘇黎世聯邦理工學院植物學教授。ETH Zurich可是出了24個諾貝爾獎得主的。

參見：

https://en.wikipedia.org/wiki/Jaccard_index

ALS算法原理

http://www.cnblogs.com/luchen927/archive/2012/02/01/2325360.html

上面的網頁概括了ALS算法出現之前的協同過濾算法的概況。

ALS算法是2008年以來，用的比較多的協同過濾算法。它已經集成到Spark的Mllib庫中，使用起來比較方便。

從協同過濾的分類來說，ALS算法屬于User-Item CF，也叫做混合CF。它同時考慮了User和Item兩個方面。

用戶和商品的關系，可以抽象為如下的三元組：<User,Item,Rating>。其中，Rating是用戶對商品的評分，表征用戶對該商品的喜好程度。

假設我們有一批用戶數據，其中包含m個User和n個Item，則我們定義Rating矩陣Rm×n，其中的元素rui表示第u個User對第i個Item的評分。

在實際使用中，由于n和m的數量都十分巨大，因此R矩陣的規模很容易就會突破1億項。這時候，傳統的矩陣分解方法對于這么大的數據量已經是很難處理了。

另一方面，一個用戶也不可能給所有商品評分，因此，R矩陣注定是個稀疏矩陣。矩陣中所缺失的評分，又叫做missing item。

針對這樣的特點，我們可以假設用戶和商品之間存在若干關聯維度（比如用戶年齡、性別、受教育程度和商品的外觀、價格等），我們只需要將R矩陣投射到這些維度上即可。這個投射的數學表示是：

Rm×n≈Xm×kYTn×k(1)

這里的≈表明這個投射只是一個近似的空間變換。

不懂這個空間變換的同學，可參見《機器學習（十二）》中的“奇異值分解”的內容，或是本節中的“主成分分析”的內容。

一般情況下，k的值遠小于n和m的值，從而達到了數據降維的目的。

幸運的是，我們并不需要顯式的定義這些關聯維度，而只需要假定它們存在即可，因此這里的關聯維度又被稱為Latent factor。k的典型取值一般是20～200。

這種方法被稱為概率矩陣分解算法(probabilistic matrix factorization，PMF)。ALS算法是PMF在數值計算方面的應用。

為了使低秩矩陣X和Y盡可能地逼近R，需要最小化下面的平方誤差損失函數：

minx?,y?∑u,i?is known(rui?xTuyi)2

考慮到矩陣的穩定性問題，使用Tikhonov regularization，則上式變為：

minx?,y?L(X,Y)=minx?,y?∑u,i?is known(rui?xTuyi)2+λ(|xu|2+|yi|2)(2)

優化上式，得到訓練結果矩陣Xm×k,Yn×k。預測時，將User和Item代入rui=xTuyi，即可得到相應的評分預測值。

同時，矩陣X和Y，還可以用于比較不同的User（或Item）之間的相似度，如下圖所示：

ALS算法的缺點在于：

1.它是一個離線算法。

2.無法準確評估新加入的用戶或商品。這個問題也被稱為Cold Start問題。

ALS算法優化過程的推導

公式2的直接優化是很困難的，因為X和Y的二元導數并不容易計算，這時可以使用類似坐標下降法的算法，固定其他維度，而只優化其中一個維度。

對xu求導，可得：

?L?xu=?2∑i(rui?xTuyi)yi+2λxu=?2∑i(rui?yTixu)yi+2λxu=?2YTru+2YTYxu+2λxu

令導數為0，可得：

YTYxu+λIxu=YTru?xu=(YTY+λI)?1YTru(3)

同理，對yi求導，由于X和Y是對稱的，因此可得類似的結論：

yi=(XTX+λI)?1XTri(4)

因此整個優化迭代的過程為：

1.隨機生成X、Y。（相當于對迭代算法給出一個初始解。）
Repeat until convergence {
2.固定Y，使用公式3更新xu。
3.固定X，使用公式4更新yi。
}

一般使用RMSE（root-mean-square error）評估誤差是否收斂，具體到這里就是：

RMSE=∑(R?XYT)2N?????????????√

其中，N為三元組<User,Item,Rating>的個數。當RMSE值變化很小時，就可以認為結果已經收斂。

算法復雜度：

1.求xu：O(k2N+k3m)

2.求yi：O(k2N+k3n)

可以看出當k一定的時候，這個算法的復雜度是線性的。

因為這個迭代過程，交替優化X和Y，因此又被稱作交替最小二乘算法（Alternating Least Squares，ALS）。

隱式反饋

用戶給商品評分是個非常簡單粗暴的用戶行為。在實際的電商網站中，還有大量的用戶行為，同樣能夠間接反映用戶的喜好，比如用戶的購買記錄、搜索關鍵字，甚至是鼠標的移動。我們將這些間接用戶行為稱之為隱式反饋（implicit feedback），以區別于評分這樣的顯式反饋（explicit feedback）。

隱式反饋有以下幾個特點：

1.沒有負面反饋（negative feedback）。用戶一般會直接忽略不喜歡的商品，而不是給予負面評價。

2.隱式反饋包含大量噪聲。比如，電視機在某一時間播放某一節目，然而用戶已經睡著了，或者忘了換臺。

3.顯式反饋表現的是用戶的喜好（preference），而隱式反饋表現的是用戶的信任（confidence）。比如用戶最喜歡的一般是電影，但觀看時間最長的卻是連續劇。大米購買的比較頻繁，量也大，但未必是用戶最想吃的食物。

4.隱式反饋非常難以量化。

ALS-WR

針對隱式反饋，有ALS-WR算法（ALS with Weighted-λ-Regularization）。

首先將用戶反饋分類：

pui={1,0,preferenceno preference

但是喜好是有程度差異的，因此需要定義程度系數：

cui=1+αrui

這里的rui表示原始量化值，比如觀看電影的時間；

這個公式里的1表示最低信任度，α表示根據用戶行為所增加的信任度。

最終，損失函數變為：

minx?,y?L(X,Y)=minx?,y?∑u,icui(pui?xTuyi)2+λ(∑u|xu|2+∑i|yi|2)

除此之外，我們還可以使用指數函數來定義cui：

cui=1+αlog(1+rui/?)

ALS-WR沒有考慮到時序行為的影響，時序行為相關的內容，可參見：

http://www.jos.org.cn/1000-9825/4478.htm

參考

參考論文：

《Large-scale Parallel Collaborative Filtering forthe Netflix Prize》

《Collaborative Filtering for Implicit Feedback Datasets》

《Matrix Factorization Techniques for Recommender Systems》

其他參考：

http://www.jos.org.cn/html/2014/9/4648.htm

http://www.fuqingchuan.com/2015/03/812.html

http://www.docin.com/p-714582034.html

http://www.tuicool.com/articles/fANvieZ

http://www.68idc.cn/help/buildlang/ask/20150727462819.html

主成分分析

真實的訓練數據總是存在各種各樣的問題。

比如拿到一個汽車的樣本，里面既有以“千米/每小時”度量的最大速度特征，也有“英里/小時”的最大速度特征。顯然這兩個特征有一個是多余的，我們需要找到，并去除這個冗余。

再比如，針對飛行員的調查，包含兩個特征：飛行的技能水平和對飛行的愛好程度。由于飛行員是很難培訓的，因此如果沒有對飛行的熱愛，也就很難學好飛行。所以這兩個特征實際上是強相關的（strongly correlated）。如下圖所示：

我們的目標就是找出上圖中所示的向量u1。

為了實現這兩個目標，我們可以采用PCA（Principal components analysis）算法。

數據的規則化處理

在進行PCA算法之前，我們首先要對數據進行預處理，使之規則化。其方法如下：

1.μ=1m∑mi=1x(i)
2.x(i):=x(i)?μ
3.σ2j=1m∑i(x(i))2
4.x(i)j:=x(i)j/σj

多數情況下，特征空間中，不同特征向量所代表的維度之間，并不能直接比較。

比如，攝氏度和華氏度，雖然都是溫度的單位，但兩種溫標的原點和尺度都不相同，因此需要規范化之后才能比較。

步驟1和2，用于消除原點偏差（常數項偏差）。步驟3和4，用于統一尺度（一次項偏差）。

雖然上面的辦法，對于二次以上的偏差無能為力，然而多數情況下，這種處理，已經比原始狀態好多了。

PCA算法推導

回到之前的話題，為了找到主要的方向u，我們首先觀察一下，樣本點在u上的投影應該是什么樣子的。

上圖所示是5個樣本在不同向量上的投影情況。其中，X表示樣本點，而黑點表示樣本在u上的投影。

很顯然，左圖中的u就是我們需要求解的主成分的方向。和右圖相比，左圖中各樣本點x在u上的投影點比較分散，也就是投影點之間的方差較大。

由《機器學習（十一）》一節的公式4，可知樣本點x在單位向量u上的投影為：xTu。

因此，這個問題的代價函數為：

1m∑i=1m(x(i)Tu)2=1m∑i=1m(x(i)Tu)T(x(i)Tu)=1m∑i=1muTx(i)x(i)Tu=uT(1m∑i=1mx(i)x(i)T)u=uTΣu

即：

maxus.t.uTΣuuTu=1

其拉格朗日函數為：

L(u)=uTΣu?λ(uTu?1)

總結

以上是生活随笔為你收集整理的机器学习（十四）——协同过滤的ALS算法（2）、主成分分析的全部內容，希望文章能夠幫你解決所遇到的問題。

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