2003年，Amazon公司的Linden、Smith、York大佬刊發了一篇名為《Item-to-Item Collaborative Filtering》的文章；這篇文章首次解釋了Amazon公司商品推薦系統的原理。從那時起，這類算法就一直主導著推薦領域。無論是Netflix、Amazon還是Facebook，每一個擁有大量用戶群的網站或應用程序都會使用某種形式的協同過濾算法來推薦產品（可能是電影、產品或社交）。協同過濾試圖利用社交網絡的力量提供可靠、相關、有時甚至令人驚喜的推薦。如果Alice和Bob在很大程度上喜歡同一部電影（比如The Lion King、Aladdin和Toy Story），而愛麗絲也喜歡Finding Nemo，那么沒有看過Finding Nemo鮑勃很可能也會喜歡。這樣的推薦結果往往符合一類群體的訴求。為了構建穩定的、良好的協同濾波推薦算法，掌握最基本的Data Mining算法是必須的。今天學習主要關注以下部分：

• 相似性測度Similarity measures：對于兩個產品，如何從數學上量化它們之間有多不同或相似？相似性度量有助于我們回答這個問題。在ACM暑校培訓構建內容推薦引擎時，已經使用了相似性度量（余弦分數）。今天又學到了更多的相似性分數測度方法~~
• 數據降維Dimensionality reduction：在構建協同濾波推薦算法時，通常要處理數百萬用戶對數百萬個產品的評級。在這種情況下，用戶和產品向量的維度將達到數百萬。為了提高推薦模型的性能、加快計算速度并避免維度爆炸的詛咒，通常最好在保留大部分信息的同時大幅減少維度的數量。
• 監督學習Supervised learning：監督學習是一類機器學習算法，它利用標簽數據推斷出一個映射函數，然后用它來預測未標記數據的標簽（或類）。這里將研究一些最流行的監督學習算法，例如支持向量機、邏輯回歸、決策樹和嵌套。
• 聚類Clustering：聚類是一種無監督學習，算法試圖將所有數據點劃分成一定數量的聚類。因此，在不使用標簽數據集的情況下，聚類算法能夠將類分配給所有未標記的點。在本文中，我們將研究k-means聚類，這是一種簡單但功能強大的算法，廣泛應用于協同過濾推薦算法中。
• 評估方法Evaluation methods：用于衡量這些算法性能的評估指標。這些指標包括準確性accuracy、精確性precision、召回率recall、F1 score等。

1. 問題背景

第i個用戶與第j個產品組成的評級矩陣，利用rij表示

協同過濾算法試圖解決預測問題。換句話說，我們得到一個i用戶和j產品的矩陣。第i行和第j列中的值（用rij表示）表示用戶i對第j項給出的評級。我們的工作是完成這個矩陣。換句話說，我們需要預測矩陣中沒有數據的所有單元格。例如，在前面的圖中，我們被要求預測用戶e是否喜歡音樂播放器項。為了完成這項任務，有些評級是可用的（例如用戶A喜歡音樂播放器和視頻游戲），而其他評級則不可用（例如，我們不知道用戶C和D是否喜歡游戲）。

2. 相似性測度

從前面的評分矩陣中，我們看到每個用戶都可以表示為一個j維向量，其中第k維表示該用戶對第k個產品的評分。假設1表示相似，-1表示不喜歡，0表示沒有評級。因此，用戶B的偏好向量可以表示為（0，1，-1，-1）。同理，每一個產品也可以表示為一個i維的向量，其中第k個維度表示第k個用對該產品的評級。因此，上圖中游戲這個產品可以表示為（1，-1，0，0，-1）。

• 歐氏距離?Euclidean distance

歐幾里得距離可以定義為連接在n維笛卡爾平面上繪制的兩個數據點的線段長度。歐幾里得分數可以取0到無窮大之間的任何值。歐幾里得分數（或距離）越低，兩個向量之間越相似。

import numpy as npdef euclidean(v1, v2):diff = np.power(np.array(v1)- np.array(v2), 2)sigma_val = np.sum(diff)euclid_score = np.sqrt(sigma_val)return euclid_scoreu1 = [5,1,2,4,5] u2 = [1,5,4,2,1] euclidean(u1,u2)>>> output : 7.483314773547883

• 皮爾遜相關系數?Pearson correlation

考慮兩個用戶，Alice和Bob，他們同時給相同的五部電影打分。Alice對她的收視率非常吝嗇，對任何電影都不超過4分。另一方面，Bob比較開明，在給電影打分時從不給低于2分的分數。計算他們之間的的歐幾里得距離如下：

alice = [1,1,3,2,4] bob = [2,2,4,3,5] euclidean(alice, bob)>>> output : 2.2360679774997898

歐幾里得距離約為2.23。然而，仔細觀察后，我們發現Bob的評分總是比Alice高。因此，我們可以說Alice和Bob的評分是極為相關的。換句話說，如果我們知道Alice對一部電影的評價，我們可以高精度地計算Bob對同一部電影的評價（在本例中，只需添加1）。考慮相反的情況，假設Eve的電影偏好與Alice極端地相反：

eve = [5,5,3,4,2] euclidean(eve, alice)>>> output : 6.324555320336759

歐拉分數高達6.32分，表明這兩個人非常不同。雖然一個人的評級非常不同，但可以用來準確預測另一個人的相應評級。從數學上講，認為Alice和Eve的評分有很強的負相關。

歐幾里得距離強調幅度，在這個例子中，不能很好地度量兩個用戶相似或不同的程度。Pearson相關性正可以彌補這個缺陷。Pearson相關性是-1和1之間的一個分數，其中-1表示總負相關（與Alice和Eve的情況一樣），1表示總正相關（與Alice和Bob的情況一樣），而0表示兩個實體之間沒有任何關聯（或相互獨立）。

from scipy.stats import pearsonr pearsonr(alice, bob) pearsonr(alice, eve)>>> output : (1.0, 0.0) (-1.0, 0.0)

• 余弦相似性?Cosine similarity

余弦相似度分數計算N維空間中兩個向量之間角度的余弦。當余弦分數為1（或角度為0）時，向量完全相似。另一方面，余弦分數為-1（或角度180度）表示這兩個向量完全不同。不同的相似性評分適用于不同的場景。對于幅度很重要的情況，歐幾里得距離是一個合適的度量標準。然而，正如在皮爾遜相關小節中所描述的案例中所看到的，幅度對我們來說不如相關性重要。因此，在構建協同過濾推薦算法時，使用Pearson和余弦相似性分數是最常用的手段。

3. 聚類?Clusterin

協作過濾背后的一個主要想法是，如果用戶A對產品的看法與用戶B相同，那么A對另一個產品的看法也比隨機選擇的用戶更可能與B相同。聚類是協同過濾算法中最常用的技術之一。它是一種無監督的學習，將數據點分組到不同的類中，使屬于特定類的數據點比屬于不同類的數據點更相似。這里重點介紹K-means聚類方法。

• k均值聚類?k-means clustering

k均值算法是目前最簡單、最流行的機器學習算法之一。它以數據點和簇數k作為輸入。接下來，它在平面上隨機繪制k個質心。在隨機繪制K個質心之后，重復執行以下兩個步驟，直到K個質心集不再發生變化。①?將數據點指定給質心：將每個數據點指定給與其最近的質心。分配給特定質心的數據點集合稱為簇。因此，對K個質點的分配導致了K簇的形成；②?質心的重新分配：在下一步中，將每個簇的質心重新計算為簇的中心（或簇中所有點的平均值）。然后將所有數據點重新分配給新的質心。

k=2情況下，k-means聚類算法的可視化效果 # generating three clusters from sklearn.datasets.samples_generator import make_blobs import matplotlib.pyplot as plt X, y = make_blobs(n_samples=300, centers=3, cluster_std=0.50, random_state=0) plt.scatter(X[:,0],X[:,1], s=50) plt.show()# using k-means cluster from sklearn.cluster import KMeanskmeans = KMeans(n_clusters=3, init='random', max_iter=10) kmeans.fit(X) y_pred = kmeans.predict(X) plt.scatter(X[:,0], X[:,1], c=y_pred, s=50) centroids = kmeans.cluster_centers_ plt.scatter(centroids[:, 0], centroids[:, 1], c='black', s=100, marker='X') plt.show() 3-cluster數據生成 -> k-means聚類結果

• 其他的聚類算法?Other clustering algorithms

k均值算法雖然功能強大，但并不適用于所有場合（針對cluster呈現高斯分布或近似高斯分布效果最好）。特例如下：

2-moon-shaped -> k-means cluster結果 -> spectral cluster結果 # generating moon-shape samples from sklearn.datasets import make_moons x_m, y_m = make_moons(300, noise=0.05, random_state=0) plt.scatter(x_m[:,0], x_m[:,1], s=50) plt.show()# using k-means cluster kmm = KMeans(n_clusters=2, init='random', max_iter=10) kmm.fit(x_m) y_m_pred = kmm.predict(x_m) plt.scatter(x_m[:,0], x_m[:,1], c=y_m_pred, s=50) centroids = kmm.cluster_centers_ plt.scatter(centroids[:, 0], centroids[:, 1], c='red', s=100, marker='X') plt.show()# using spectral cluster from sklearn.cluster import SpectralClustering model = SpectralClustering(n_clusters=2, affinity='nearest_neighbors') y_m_sc = model.fit_predict(x_m) plt.scatter(x_m[:,0], x_m[:,1], c=y_m_sc, s=50) plt.show()

4. 降維?Dimensionality reduction

隨著數據的維度數量增加，大多數機器學習算法往往表現不佳。這種現象通常被稱為維數災難。因此，最好減少數據中特征的數量，同時保留盡可能多的信息。實現這一點有兩種方法

① 特征選擇?Feature selection：該方法包括識別預測能力最低的特征，并將它們全部刪除。因此，特征選擇涉及到識別對于特定場景最重要的特征子集。特征選擇的一個重要區別是它保持了每個被保留特征的原始含義。例如，假設有一個包含價格、面積和房間數量的住房數據集作為特征。現在，如果我們要取消區域功能，剩余的價格和房間數量功能仍然意味著它們最初的功能。

② 特征提取?Feature extraction：特征提取接收M維數據并將其轉換為N維輸出空間（通常M>>N），同時保留大部分信息。然而，在這樣做的過程中，它創建了沒有內在含義的新特性。例如，如果使用相同的住房數據集并使用特征提取將其輸出到二維空間中，那么新的特征并不意味著價格、面積或房間數量。

在不討論深度模型（DeepLearning）之前，常用的數據降維方法就是主成分分析Principle Component Analysis。

• 主成分分析 Principle Component Analysis

主成分分析是一種無監督特征提取算法，它采用m維輸入來創建一組n（m>>n）線性不相關變量（稱為主成分），使得n維由于（m-n）維的丟失而損失盡可能小的方差（或信息）。PCA中的線性變換是這樣進行的：第一個主分量保持最大方差（或信息）。它是通過考慮那些相互高度相關的變量來實現的。每個主成分比每個后續成分都有更多的方差，并且與前面的成分是正交的。一個基因分析的例子如下：

其他的降維方法如Linear-discriminant analysis、Singular value decomposition因為用的比較少，這里先不做展開討論。

5. 監督學習

監督學習是一類機器學習算法，它以一系列向量及其相應的輸出（連續值或類）作為輸入，生成一個可用于映射新實例的推斷函數。使用監督學習的一個重要前提是標記數據的可用性。換句話說，我們有必要訪問已經知道正確輸出的輸入。監督學習可以分為兩類：分類和回歸。分類問題有一組離散的值作為目標變量（例如，喜歡和不喜歡），而回歸問題有一個連續的值作為目標（例如，平均評級在1到5之間）。考慮前面定義的評級矩陣。可以將（m-1）列作為輸入，將m-th列作為目標變量。這樣，應該可以通過傳遞相應的（m-1）維向量來預測m-th列中的不存在的值。監督學習是機器學習中最成熟的子領域之一，因此，有許多有效的算法可用于執行精確的預測。這里只介紹在各種應用程序（包括協作過濾）中成功使用的一些最流行的算法，當然仍不包含深度學習模型。

• k最近鄰?k-nearest neighbors

k-最近鄰（kNN）可能是最簡單的機器學習算法。在分類情況下，它通過K最近鄰的多數投票結果，將一個類分配給特定的數據點。換言之，數據點被分配給K最近鄰中最常見的類。在回歸情況下，根據目標變量的k-最近鄰計算目標變量的平均值。與大多數機器學習算法不同，KNN本質上是非參數的和懶惰的。前者意味著KNN不會對數據的分布做出任何基礎假設。換句話說，模型結構完全由數據決定。后者意味著K-NN幾乎不需要任何的訓練。它只在預測階段計算特定點的k-最近鄰。

• 支持向量機?Support vector machines

支持向量機是目前工業上應用最廣泛的分類算法之一。它以一個n維數據集作為輸入，并以類的最大間隔的方式構造（n-1）維超平面。以上圖數據的二分類為例；他存在三個可能的超平面（直線），把數據分成兩個類。很明顯，實線是具有最大的類間隔。換句話說，這個超平面最大限度地分隔了這兩個類。超平面下的任何點都將被劃分為一個紅色的正方形，而上面的任何點都將被劃分為一個藍色的圓。SVM模型只依賴于支持向量；這些點決定了兩個類之間可能的最大邊界。上圖中，實心的正方形和圓形是支持向量，其余數據點對SVM模型并沒有任何貢獻。其實，通過核函數技巧（如高斯徑向核），SVM模型非常適合非線性數據分類，這也是在深度模型出現之前，SVM備受算法研究人員青睞的原因。

• Ensembling -?Bagging and random forests

集成背后的主要思想是多個算法的預測能力遠遠大于單個算法。決策樹是構建集成模型時最常用的基礎算法。Bagging是bootstrap aggregating的簡稱。與大多數其他集成方法一樣，對大量基本分類模型進行平均，并對結果平均，以實現最終預測。建立一個bagging模型可以遵循以下步驟：①自助采樣；②挑選基類分類器，如決策樹，并利用采樣后的數據進行訓練；③重復訓練N個模型，最終的模型輸出就是N個分類器的平均輸出。Bagging模型的代表是隨機森林。除了采樣數據點之外，隨機森林集成方法還強制每個基礎分類器隨機選擇特征子集（通常是等于特征總數平方根的數字）。選擇樣本的子集以及特征來構建基礎決策樹，極大地增強了每一棵樹的隨機性。這反過來又增加了隨機林的魯棒性，并允許它在有噪聲數據的情況下運行得非常好。此外，從特征子集構建基礎分類器并分析它們對最終預測的貢獻，允許隨機森林確定每個特征的重要性。因此，可以使用隨機森林進行特征選擇。

• Ensembling -?Boosting?

由于自助采樣的原因，Bagging和隨機森林模型所訓練的基礎分類器是完全彼此依賴的。這個時候Boosting就派上用場了。與隨機森林一樣，Boosting模型使用樣本和特征的子集構建基礎分類模型。不同的是，在構建下一個基礎分類器的同時，Boosting模型試圖糾正前一個分類器所犯的錯誤。不同的提升算法以不同的方式實現這一點。Boosting一類算法性能非常強大。常常應用在數據科學研究領域。

總結

以上是生活随笔為你收集整理的Collaborative Filter - Data Mining基础（ACM暑校）的全部內容，希望文章能夠幫你解決所遇到的問題。

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