⑴ 利用 SVD 實現協同過濾推薦演算法
奇異值分解(Singular Value Decomposition，以下簡稱SVD)
是在機器學習領域廣泛應用的演算法，它不光可以用於 降維演算法中的特徵分解 ，還可以用於 推薦系統 ，以及自然語言處理等領域。
優點： 簡化數據，去除雜訊，提高演算法的結果。
缺點： 數據的轉換可能難以理解。
應用領域： 推薦引擎（協同過濾、相似度計算）、圖像壓縮等。
SVD定義： 如果我們求出了矩陣A的n個特徵值λ1≤λ2≤...≤λn，以及這n個特徵值所對應的特徵向量{w1,w2,...wn}，如果這n個特徵向量線性無關，那麼矩陣A就可以用下式的特徵分解表示：A=WΣW−1，其中W是這n個特徵向量所張成的n×n維矩陣，而Σ為這n個特徵值為主對角線的n×n維矩陣。一般我們會把W的這n個特徵向量標准化，即滿足||wi||2=1, 或者wiTwi=1，此時W的n個特徵向量為標准正交基，滿WTW=I，即WT=W−1, 也就是說W為酉矩陣。要進行特徵分解，矩陣A必須為方陣。那麼如果A不是方陣，則用到SVD。
矩陣A的SVD為：A=UΣVT，其中U是一個m×m的矩陣，Σ是一個m×n的矩陣，除了主對角線上的元素以外全為0，主對角線上的每個元素都稱為奇異值，V是一個n×n的矩陣。U和V都是酉矩陣，即滿足UTU=I,VTV=I。
對於奇異值,它跟我們特徵分解中的特徵值類似，在奇異值矩陣中也是按照從大到小排列，而且奇異值的減少特別的快，在很多情況下，前10%甚至1%的奇異值的和就佔了全部的奇異值之和的99%以上的比例。也就是說，我們也可以用最大的k個的奇異值和對應的左右奇異向量來近似描述矩陣。
因此SVD 也是一種強大的降維工具 ，可以利用 SVD 來逼近矩陣並從中獲得主要的特徵。通過保留矩陣的 80%~90% 的能量，就可以得到重用的特徵並去除雜訊。
推薦系統 是利用電子商務網站向客戶提供商品信息和建議，幫助用戶決定應該購買什麼產品，模擬銷售人員幫助客戶完成購買過程。
主要有以下幾種推薦演算法：
基於內容的推薦（用到自然語言處理）， 協同過濾（主流） ，基於規則推薦（基於最多用戶點擊，最多用戶瀏覽等），混合推薦（類似集成演算法，投票決定），基於人口統計信息的推薦（根據用戶基本信息）
協同過濾推薦分為三種類型。 第一種是基於用戶(user-based)的協同過濾（需要在線找用戶和用戶之間的相似度關系），第二種是基於項目(item-based)的協同過濾（基於項目的協同過濾可以離線找物品和物品之間的相似度關系）， 第三種是基於模型(model based)的協同過濾（用戶和物品，主流）。
一般在推薦系統中，數據往往是使用 用戶-物品 矩陣來表示的。 用戶對其接觸過的物品進行評分，評分表示了用戶對於物品的喜愛程度，分數越高，表示用戶越喜歡這個物品。而這個矩陣往往是稀疏的，空白項是用戶還未接觸到的物品，推薦系統的任務則是選擇其中的部分物品推薦給用戶。
對於這個 用戶-物品 矩陣，用已有的部分稀疏數據來預測那些空白的物品和數據之間的評分關系，找到最高評分的物品推薦給用戶。
具體基於模型的方法有：
用關聯演算法做協同過濾（Apriori演算法、FP Tree演算法）
用聚類演算法做協同過濾（針對基於用戶或者基於模型，Kmeans，DBSCAN）
用分類演算法做協同過濾（設定評分閾值，高於推薦，低於不推薦，邏輯回歸和樸素貝葉斯，解釋性很強）
用回歸演算法做協同過濾（Ridge回歸，回歸樹）
用矩陣分解做協同過濾（由於傳統的奇異值分解SVD要求矩陣不能有缺失數據，必須是稠密的，而用戶物品評分矩陣是一個典型的稀疏矩陣，主要是SVD的一些變種，比如FunkSVD，BiasSVD和SVD++。這些演算法和傳統SVD的最大區別是不再要求將矩陣分解為UΣVT的形式，而變是兩個低秩矩陣PTQ的乘積形式。）
用神經網路做協同過濾（限制玻爾茲曼機RBM）
在 Python 的 numpy 中，linalg已經實現了SVD
⑵ k近鄰協同過濾和協同過濾演算法的區別
協同過濾演算法
協同過濾(Collaborative filtering, CF)演算法是目前個性化推薦系統比較流行的演算法之一。
協同演算法分為兩個基本演算法：基於用戶的協同過濾（UserCF）和基於項目的協同過濾（ItemCF）。
最近這段時間，多數人都選擇使用被稱為個性化協同推薦（Personalized Collaborative Recommender）的演算法。這也是亞馬遜、Netflix、Facebook 的好友推薦，以及一家英國流行音樂網站 Last.fm 的核心演算法。說它 「個性化」，是因為這種演算法會追蹤用戶的每一個行為（如瀏覽過的頁面、訂單記錄和商品評分），以此進行推薦；它們可不是瞎貓碰上死耗子——全憑運氣。說它 「協同」，則是因為這種演算法會根據許多其他的顧客也購買了這些商品或者對其顯示出好感，而將兩樣物品視為彼此關聯，它不是通過分析商品特徵或者關鍵詞來進行判斷的。
⑶ K-Means原理總結
K-means是聚類中的一個經典方法。其中的原理和思想實在是巧妙到爆炸💥。接下來讓我來給大家展示來自1967年的演算法的智慧。
問題引出：如下圖所示，我們想要自動的聚類，肉眼一看是5類。那麼我們隨機生成5個點，它們最終將會成為聚類後每個類的中心點。由於是隨機初始化的5個點，所以它們的位置剛開始大概率不在每個類的中心點上，不過沒關系，我們可以慢慢調整。
過程描述：如上圖所示生成的5個點，它們最終會成為每個類的中心點，此時此刻，每個點有著自己的領域范圍。比如最上面的那個點1，它想要成為一個類的中心點，這個類此時此刻都包含哪些點呢，答案當然是到它的距離比到其他中心點距離更近的所有樣本點。那麼接下來，哪些點符合條件呢?由於每個中心點它都想要控制盡可能多的點，並且得合理。那最上面那個中心點1想要控制位於它自己下面的一些樣本點，會有哪些中心點在跟它競爭呢? 答案是中間左右兩個點2和3，注意最下面兩個中心點4和5參與不到競爭了。所以我們做出兩條垂直平分線a,b。a是連線點1，2的垂直平分線，b是連線點1，3的垂直平分線。垂直平分線有什麼性質啊? 位於線上的點到兩端的距離相等，位於線一側的點到該側端點距離更小。所以！位於垂直平分線a,b上面的所有樣本點暫時歸中心點的領域，注意此時點1並未是該領域樣本點的中心，我們應該更新點1的位置，把它挪到領域的中心。因為三角形三條邊的垂直平分線會交於一點（先畫出兩條交於一點，再從該點向另一個邊做垂線，證明該垂線與邊的交點為中點即可）所以5個中心點互相競爭劃分領域會呈現出如上並不雜亂的界限。我們更新5個中心點的位置，再次重新競爭領域，再更新位置。。。直到中心點的位置不動了，聚類完畢。
原理中一直貫穿著中心的概念，這就是means的含義。接下來我們來分析一下K-means的優缺點。
1.對分布類似球型的數據效果很好。為什麼？試想長條帶狀的末端有一小簇。
............................................. 。
............................................. 。
如果剛開始隨機的中心點一左一右剛剛好，開始競爭，顯然...這些右側的..離。。。的中心點更近，按規則應該歸它領域，然後再更新。這樣就不符合人的直覺了。
2.收斂的很快，中心點更新個幾次後就不咋動了。
3.相對高效並且易估計復雜度O(k·t·n)，t是迭代次數一般幾次就可以完成，k是中心點個數，簇的個數，不會很大。n是數據點的個數，可能會很大。
1.K值不好估計，不能預先去判斷。
2.可能會因為初始點隨機的不好，會收斂到一個奇怪的結果。如下圖。
⑷ 協同過濾與分類
[TOC]
本文是《寫給程序員的數據挖掘實踐指南》的一周性筆記總結。主要涵蓋了以下內容：
所謂推薦系統就是系統根據你的行為操作為你推薦你可能想要的其他物品。這在電商平台、音樂平台、資訊推送平台等多有見到。而協同過濾簡單來說是利用某興趣相投、擁有共同經驗之群體的喜好來推薦用戶感興趣的信息，個人通過合作的機制給予信息相當程度的回應（如評分）並記錄下來以達到過濾的目的進而幫助別人篩選信息。其推薦基礎是用戶評分。這里可以分為兩種用戶評分，即顯式評分與隱式評分。顯式評分即日常見到的為物品打分，如對喜好音樂評級等；隱式評分是通過對用戶行為的持續性觀察，進而發現用戶偏好的一種方法，如新聞網頁中的推送你經常閱讀過的相關內容等。兩種評分方法都有自己的問題。
總體來說，協同過濾其運作機制也可以分為兩種：
基於用戶的推薦是指通過用戶的行為偏好，劃分相似用戶。在相似用戶群體之間互相推送一方喜歡而另一方未有過的物品。核心在於相似用戶群體的劃分。這種推薦方法有自己的局限：
基於用戶的過濾其核心是用戶群體的劃分，其實也就是分類。
這里的距離函數包括三種：曼哈頓距離和歐氏距離。這里以二維舉例，更多維情況下類推即可。
兩距離函數可以一般化為：
其中，當r=1時，函數為曼哈頓距離；當r=2時，函數為歐氏距離。
演算法實現：
在算出距離函數後，通過比對目標用戶與所有用戶群體的偏好，找到最近鄰的用戶並給予推薦。
基於用戶距離的推薦有一個明顯的問題，就是用戶評分體系的差異。比如評分極端的用戶給喜歡的評最高分，給不喜歡的評最低分；而有些用戶傾向於不出現極端評分。即所謂「分數貶值」( Grade Inflation )問題。這種問題的存在可能讓基於距離的評分產生偏差。皮爾遜相關系數可以緩解這種問題。
原皮爾遜相關系數公式在實際運用的時候會出現多次迭代的問題，影響計算效率，這里給出了近似公式：
皮爾遜相關系數的用戶判斷依據不是單純的用戶距離，而是用戶的評分一致性：取值在[-1, 1]之間，越接近1則表示兩用戶的評分一致性越好；反之則反。
python實現：
基於用戶推薦的過程中，另一個存在的問題就是由於大部分人的喜愛物品集合的交集過少，存在大量計算值為0的feature的情況。即所謂 稀疏性 問題。一個較容易理解的例子是對書本內容的挖掘。餘弦相似度會忽略這種0-0匹配。
餘弦相似度：
python實現：
如此多的評估系數，如何進行抉擇呢？根據數據特徵：
另外值得考慮的一點是，目前為止的推薦都是基於單用戶的。即對一個用戶的推薦系統只是基於另一個用戶。這會存在一些問題。比如雖然雖然兩者相似度很高，但是另外一個人有一些怪癖，怪癖的推薦就是不合理的；又比如，在相似度極高的情況下，你不能確定統一賬戶下的操作是同一個人做出的或者說操作行為是為了用戶自身。比如用戶考慮購買某件商品作為禮物送給別人，這就是基於別人喜好的購買行為，這種推薦也是不合適的。
對這種問題的解決可以使用群體劃分的方法。原理與單用戶類似，但是用戶的匹配是k個。在這k位最優匹配的用戶之間，以相似度的大小為依據設定權重作為物品推薦的條件。此即協同過濾的k近鄰。
正如前面提到的基於用戶的推薦有復雜度、稀疏性的問題，而基於物品的過濾則可以緩解這些問題。所謂基於物品的過濾是指，我們事先找到最相似的物品，並結合用戶對物品的評級結果來生成推薦。前提是要對物品進行相似度匹配，找到一種演算法。
這里的調整是指為了減輕用戶評分體系的不一致情況（抵消分數貶值），從每個評級結果中減去該用戶所有物品的平均分的評級結果。
其中，U表示所有同時對i， j進行評級過的用戶的集合。 表示用戶u給物品i的評分減去用戶u對所有物品的評分的平均值。
在得到所有物品的餘弦相似度後，我們就可以通過該指數預測用戶對某件物品的偏好程度。方法就是所有相似物品的相似度乘以得分的總和。
其中p（u, i）指的是用戶u對物品i評分的預測值。N是用戶u的所有評級物品中每個和i得分相似的物品。這里的相似指的是矩陣中存在N和i的一個相似度得分。 是i和N之間的相似度得分。 是u給N的評級結果。公式較好運行的條件是 取值在（-1， 1）之間，這里就要使用歸一化概念。
另一種常用的基於物品過濾的演算法就是 slope one 演算法。它的大概原理是預測用戶u對產品j的評分時，預先計算包含所有物品的兩物品偏差表；根據u的已評價的所有物品評分與該物品和產品j的偏差（ ）之和並乘以所有對此兩類物品有過評分的用戶個數，一一加總，除以所有同時對產品i與u評價過的所有物品有過評分的用戶的人數，得到得分。公式如下：
其中， ； 是利用加權s1演算法給出的用戶u對物品j的預測值。 指的是對所有除j之外u打過分的物品。
python實現：
在前面兩節中，基於物品和基於用戶的過濾其前提都是用戶需要對已有的item進行評分。而實際上，如果一個新的item出現，由於缺乏別人的偏好，他永遠不會被推薦。這就是推薦系統中所謂的—— 冷啟動 問題。基於用戶評價的系統就會出現這種問題。
冷啟動 問題的解決方案之一就是 基於物品屬性的過濾 來進行推薦：對物品自身的屬性進行歸納總結，並以此進行物品推薦。基於物品屬性的過濾存在一個問題同樣是量綱的不統一。如果量綱不統一極端值將會對推薦系統造成大麻煩。解決方法也很簡單：歸一化。此章使用的是z-評分。
使用z得分也存在問題，就是極易受到離群值的影響。這里可以使用 改進的標准分數 來緩解這個問題：
什麼時候可以進行歸一化呢？
這里用曼哈頓距離舉例基於物品屬性的過濾：
在上一章最後一節對於用戶是否喜歡某件item的判別中，實際上包含了分類器的思想：分類器就是利用對象屬性判定對象屬於哪個組或類別的程序。這里簡單用另一個小項目來說明。
簡單來說就是根據運動員的某些指標來判斷這位運動員屬於什麼類別的運動員。
准確率有0.8。
⑸ k-means對數據去噪的原理
k-means對數據去噪的原理如下：
1、首先在數據當中隨機生成k個聚類中心，後計算數據當中每個樣本到這k個聚類中心的距離，並將對應的樣本分到距離最小的聚類中心所對應的簇當中。
2、將所有樣本歸類之後，對於每一個k個簇重新計算每個簇的聚類中心，也就是每個簇中的所有樣本的質心，重復上述操作，直到k-means對數據去噪為止。
⑹ 如何在Hadoop平台上實現K-means演算法
一、介紹Mahout
Mahout是Apache下的開源機器學習軟體包，目前實現的機器學習演算法主要包含有協同過濾/推薦引擎，聚類和分類三 個部分。Mahout從設計開始就旨在建立可擴展的機器學習軟體包，用於處理大數據機器學習的問題，當你正在研究的數據量大到不能在一台機器上運行時，就 可以選擇使用Mahout，讓你的數據在Hadoop集群的進行分析。Mahout某些部分的實現直接創建在Hadoop之上，這就使得其具有進行大數據 處理的能力，也是Mahout最大的優勢所在。相比較於Weka，RapidMiner等 圖形化的機器學習軟體，Mahout只提供機器學習的程序包（library），不提供用戶圖形界面，並且Mahout並不包含所有的機器學習演算法實現， 這一點可以算得上是她的一個劣勢，但前面提到過Mahout並不是「又一個機器學習軟體」，而是要成為一個「可擴展的用於處理大數據的機器學習軟體」，但 是我相信會有越來越多的機器學習演算法會在Mahout上面實現。[1]
二、介紹K-Means
這是Apache官網上的演算法描述，簡單來說就是基於劃分的聚類演算法，把n個對象分為k個簇，以使簇內具有較高的相似度。相似度的計算根據一個簇中對象的平均值來進行。[2]
三、在Hadoop上實現運行
1，實驗環境
①hadoop集群環境：1.2.1 一個Master，兩個Slaves，在開始運行kmeans時啟動hadoop
②操作系統：所有機器的系統均為ubuntu12.04
③Mahout版本：採用的是0.5版
2，數據准備
數據採用的是 這是網上提供的一個比較不錯是數據源。然後用指令 hadoop fs -put /home/hadoop/Desktop/data testdata，將在我桌面的文件data上傳到HDFS的testdata目錄下，這里為什麼是testdata，我也正在思考，因為我本來是上傳到 input里，但是運行時提示could not find ….user/testdata之類的，所以現改為了testdata。
3，運行
①配置Mahout環境：在Apache官網下載Mahout的版本，我選擇的是0.5。然後解壓到你指定的目錄，將此目錄路徑寫入/etc/profile，添加如下語句：
export MAHOUT_HOME=/home/hadoop/hadoop-1.2.1/mahout-distribution-0.5
export HADOOP_CONF_DIR=/home/hadoop/hadoop-1.2.1/conf
export PATH=$PATH:/home/hadoop/hadoop-1.2.1/bin:$MAHOUT_HOME/bin
然後執行 source /etc/profile。在mahout目錄下執行bin/mahout命令，檢測系統是否安裝成功。如圖：
註：此處修改環境變數有些網上提示是/etc/bash.bashrc，我也試著修改過，但是發現在我這里使環境變數生效的是profile。
②運行Mahout里自帶的K-Means演算法，bin/mahout org.apache.mahout.clustering.syntheticcontrol.kmeans.Job，這里啟動後遇到了一點問題，提示 Could not find math.vector。
4，結果
在我的環境下運行5分鍾左右，最後生成一個文件，如圖
四、總結
Mahout是一個很強大的數據挖掘工具，需要進行更深層的了解。
⑺ 協同過濾(2)： KDD2020- HyperGraph CF 基於超圖
協同過濾推薦系統是當今眾多推薦系統中最流行和最重要的推薦方法之一。
盡管已經被廣泛採用，但是現有的基於 cf 的方法，從矩陣分解到新興的基於圖的方法， 在訓練數據非常有限的情況下表現不佳 （數據稀疏問題）。
本文首先指出了造成這種不足的根本原因，並指出現有基於 CF 的方法固有的兩個缺點，即: 1)用戶和物品建模不靈活; 2)高階相關性建模不足。
在這種情況下，文中提出了一個雙通道超圖協同過濾(DHCF)框架來解決上述問題。
首先，引入 雙通道學習策略 (Dual-Channel)，全面利用分治策略，學慣用戶和物品的表示，使這兩種類型的數據可以優雅地相互連接，同時保持其特定屬性。
其次， 利用超圖結構對用戶和具有顯式混合高階相關性的物品進行建模 。提出了跳躍超圖卷積(JHConv)方法，實現高階關系嵌入的顯式和有效傳播。
推薦系統的核心是一系列的推薦演算法，這些演算法能夠**根據用戶的個人特徵有效地從爆炸式信息篩選出信息。協同過濾是目前最受歡迎和廣泛採用的方法之一。
CF 持有一個基本的假設，當向用戶提供推薦時: 那些行為相似的人(例如，經常訪問同一個網站)很可能在物品(例如，音樂、視頻、網站)上分享相似的偏好。
為了實現這一點，一個典型的基於 CFbased 方法執行一個兩步策略: 它首先利用歷史交互區分相似的用戶和項目; 然後基於上面收集的信息，向特定用戶生成推薦。
現有的 CF 方法可以分為三類。
雖然 CF 方法已經研究了多年，但仍然存在局限性，特別是在訓練的先驗知識非常有限的情況下。為了理解這些缺陷，深入挖掘現有 CF 方法的內在機製得到以下局限性:
基於這些生成的連接組，即超邊，可以分別為用戶和物品構造兩個超圖，即兩個通道的表示。本文提出了一種新的跳躍超圖卷積演算法(JHConv) ，該演算法通過聚合鄰域的嵌入並引入先驗信息，有效地在超圖上進行信息傳播。(與傳統的基於圖的方法對比，用戶超圖和項目超圖，可以更靈活地進行復雜的數據關聯建模，並與不同類型的數據結合。)
超圖定義為 ，V表示圖節點， 表示超邊集合，超圖鄰接矩陣 描述節點與超邊的關系
在高層次上，DHCF 首先通過一個雙通道超圖框架學慣用戶和物品的兩組嵌入，在此框架上，DHCF 通過計算用戶和物品嵌入查找表的內積，進一步計算出用戶-項目偏好矩陣。基於這樣的偏好矩陣，DHCF 估計用戶對某個商品感興趣的可能性。
總體分為三步：
構建用戶和物品嵌入矩陣：
為了在預定義的混合高階關繫上聚合相鄰消息,執行以下高階消息傳遞:
為了提取有區別的信息，我們對用戶和物品定義為
綜上所述，上述兩個過程構成了一個集成的DHCF 層，允許對用戶和物品進行明確的建模和編碼，並通過強大的嵌入功能進一步更新和生成更精確的嵌入超圖結構。這種精細嵌入可以進一步應用於推薦系統中的各種下游任務。
與 傳統 HGNNConv 相比，JHConv 允許模型同時考慮其原始特徵和聚合相關表示，在另一方面，這樣的 resnet結構的跳躍連接使模型能夠避免由於集成了許多其他連接而導致的信息稀釋。
引入高階關聯來實現構建超邊，根據自定義的規則分別對用戶和物品進行高階關聯提取
定義1: 物品的 k 階可達鄰居。在用戶-物品交互圖，更具體地說是二部圖中，如果在 itemi 和 itemj 之間存在一個相鄰頂點序列(即一條路) ，且該路徑中的用戶數小於 k，itemi (itemj)是 itemi (itemi)的 k 階可達鄰居。
定義2： 物品的 k階可達用戶。在物品-用戶二部圖中，如果用戶 j 和物品 k 之間存在直接交互作用，則用戶 j 是 itemi 的 k 階可達鄰居，而物品 k 是 itemi 的 k 階可達鄰居。
對於 itemi，其 k 階可達用戶集稱為 。從數學上講，超圖可以定義在一個集簇上，其中每個集代表一個超邊。因此，這里可以通過物品的 k 階可達用戶集構建超邊。
然後在用戶 k 階可達規則的基礎上構造高階超邊組，該超邊組可表示為:
假設通過K階可達規則，構造a個超邊組，最後的超圖需要將這a個超邊組做融合，見上面的總體框架中的描述。
同理，按照相似的K階可達的規則，對物品進行分析，構成物品的超邊(N個用戶，M個物品)
在實驗中，每個用戶觀察到的交互中的10% 被隨機選擇用於訓練，其餘的數據用於測試。這樣的設置增加了 CF 任務的難度，因為模型只能獲取非常有限的觀察到的交互。此外，由於數據的高度稀疏性，它可以很好地評價模型從有限的隱式數據集中挖掘有用信息的能力。對於所有四個數據集，每個用戶至少有兩個用於訓練的交互。
這篇工作基於超圖結構，提出了一種新的CF框架，與基於圖神經網路的CF相比，超圖結構更符合實際情況；此外，雙通道的思路也值得借鑒，之前也分析的一篇雙通道BPR的論文。近年來，基於圖神經網路的推薦已經成為研究主流，而其中超圖相關的工作少之又少，最近看到的另一篇是SIGIR2020上的一篇Next Item Recommendation with Sequential Hypergraphs，在超圖神經網路上並沒多大的改進，重點仍然在於如何用這種結構去解決存在的問題。
如果覺得有用，歡迎點贊關注贊賞，若對推薦感興趣歡迎評論區/私信交流~~~