spark推薦演算法

『壹』 Spark筆記(1) ：餘弦相似度計算

spark

在推薦系統中，基於物品的協同過濾演算法是業界應用最多的演算法，它的思想是給用戶推薦那些和他們喜歡的物品相似的物品，主要分為兩個步驟：一，計算物品之間的相似度；二，根據物品相似度和用戶的歷史行為給用戶生成推薦列表。

其中物品的相似度的計算，可以通過餘弦相似度計算。餘弦相似度用向量空間中兩個向量夾角的餘弦值作為衡量兩個個體間差異的大小。餘弦值越接近1，就表明夾角越接近0度，也就是兩個向量越相似，這就叫"餘弦相似性"。
計算公式如下：

以文本相似度為例，用上述理論計算文本的相似性。

怎樣計算上面兩句話的相似程度？

基本思路是：如果這兩句話的用詞越相似，它們的內容就應該越相似。因此，可以從詞頻入手，計算它們的相似程度。
第一步，分詞

第二步，列出所有的詞

第三步，計算詞頻

第四步，寫出詞頻向量

問題就變成了如何計算這兩個向量的相似程度。可以想像成空間中的兩條線段，都是從原點出發，指向不同的方向。兩條線段之間形成一個夾角，如果夾角為0度，意味著方向相同、線段重合,這是表示兩個向量代表的文本完全相等；如果夾角為180度，意味著方向正好相反。因此，我們可以通過夾角的大小，來判斷向量的相似程度。夾角越小，就代表越相似。
使用上面的公式計算可得：

計算結果中夾角的餘弦值為0.81非常接近於1，所以，上面的句子A和句子B是基本相似的。

spark例子：

運行結果：

『貳』 推薦系統UserCF和ItemCF

UserCF（User Collaboration Filter），又稱 基於用戶的協同過濾演算法。

協同過濾：就是指眾多的用戶可以齊心協力，通過不斷地和網站互動，使 自己的推薦列表能夠不斷過濾掉自己不感興趣的物品，從而越來越滿足自己的需求。

而基於用戶是指通過分析用戶對商品的行為（如瀏覽、收藏、加入購物車、購買……）計算出哪些用戶是興趣相似的，然後把興趣相似的用戶所關注的商品相互推薦。

舉個例子：

由上表可以看出用戶A和用戶C比較相似，所以把用戶A感興趣的商品4推薦給用戶C。

步驟一般分為兩步：

再舉個詳細點的例子：

假設我們這么一些數據(用戶(字母) 商品(數字)_行為，)：

我們可以給不同的行為賦予不同的評分（假設瀏覽1分、收藏3分、加入購物車5分、購買10分），得到以下數據：

這樣看著比較累，而且也不方便計算，可以把它轉換為矩陣形式,稱之為 評分矩陣 ：

計算相似度

計算相似度的方式有很多，如餘弦相似度、切比雪夫距離、歐里幾得距離、曼哈頓距離、傑卡德距離、皮爾森系數……計算相似度的方式不同計算出來的相似度也不同。

這里只介紹餘弦相似度，其他的請自行網路。

假設有二維向量a,b如下圖所示

則他們的餘弦相似度為

推廣到多維向量a(a1,a2,a3,a4……)，b(b1,b2,b3,b4……)

有了公式就能計算出用戶相似度了：

推薦列表 = 相似度矩陣 X 評分矩陣

由於用戶已經對推薦列表中的一些商品有過行為，所以還要把這些商品給濾除掉

得到最終的推薦列表，其數值代表的意義是用戶對商品的感興趣程度：

ItemCF（Item Collaboration Filter），又稱 基於商品(物品)的協同過濾演算法。

其原理與UserCF類似，是基於用戶對商品的偏好找到相似的商品，然後推薦相似的商品品給他。
計算過程也非常相似，區別在於計算時把UserCF的 評分矩陣轉置 ，再計算商品與商品之間的相似度得到 商品之間的相似度矩陣 。
最後的 推薦列表 = 商品之間的相似度矩陣 X 評分矩陣轉置

對於電子商務，用戶數量一般大大超過商品數量，此時Item CF的計算復雜度較低。
比如在購書網站上，當你看一本書的時候，推薦引擎會給你推薦相關的書籍，這個推薦的重要性進進超過了網站首頁對該用戶的綜合推薦。可以看到，在這種情況下，Item CF 的推薦成為了引導用戶瀏覽的重要手段。基於物品的協同過濾演算法，是目前電子商務採用最廣泛的推薦演算法。

在非社交網路的網站中，內容內在的聯系是很重要的推薦原則，它比基於相似用戶的推薦原則更加有效。在社交網路站點中，User CF 是一個更好錯的選擇，User CF 加上社會網路信息，可以增加用戶對推薦解釋的信服程度。

推薦多樣性和精度，各有千秋。

參考：
Spark基於用戶的協同過濾演算法 https://www.toutiao.com/a6498952374487368205/?tt_from=mobile_qq&utm_campaign=client_share&app=news_article&utm_source=mobile_qq&iid=15393016323&utm_medium=toutiao_android

推薦系統_itemCF和userCF
http://blog.csdn.net/u011263983/article/details/51498458

『叄』 有什麼關於 Spark 的書推薦

《大數據Spark企業級實戰》本書共包括14章，每章的主要內容如下。

第一章回答了為什麼大型數據處理平台都要選擇SPARK

第二章回答了如何從頭構建Hadoop集群的問題。

附錄從spark的角度解釋了Scala，並詳細解釋了Scala函數編程和面向對象編程。

『肆』 spark和hadoop的區別

hadoop:是分布式存儲系統，同時提供分布式計算環境，存儲稱為hdfs，計算稱為maprece 簡稱MR。
spark：是一個分布式計算框架，類似於hadoop的運算環境，但是比maprece提供了更多支持，與其他系統的對接，一些高級演算法等，可以獨立運行，也可以使用hdfs上的數據，調度任務也可以基於hadoop的yarn來管理。由於整個計算都可以在內存中完成，所以速度自然比傳統的MR計算的快。除此之外spark運行時佔用的系統資源也比MR小得多，相比較屬於輕量級運行。最核心的也是它提供的分析學習演算法，這個大部分分布式架構不具有的。
一般spark下的編程多數基於scala來完成，而非java，所以想學習spark一定要學習scala語言

『伍』 請簡要描述一下hadoop，spark，mpi三種計算框架的特點以及分別適用於什麼樣的場景

Spark已經取代Hadoop成為最活躍的開源大數據項目，但是，在選擇大數據框架時，企業不能因此就厚此薄彼
近日，著名大數據專家Bernard Marr在一篇文章中分析了Spark和 Hadoop 的異同
Hadoop和Spark均是大數據框架，都提供了一些執行常見大數據任務的工具，但確切地說，它們所執行的任務並不相同，彼此也並不排斥
雖然在特定的情況下，Spark據稱要比Hadoop快100倍，但它本身沒有一個分布式存儲系統
而分布式存儲是如今許多大數據項目的基礎，它可以將 PB 級的數據集存儲在幾乎無限數量的普通計算機的硬碟上，並提供了良好的可擴展性，只需要隨著數據集的增大增加硬碟
因此，Spark需要一個第三方的分布式存儲，也正是因為這個原因，許多大數據項目都將Spark安裝在Hadoop之上，這樣，Spark的高級分析應用程序就可以使用存儲在HDFS中的數據了
與Hadoop相比，Spark真正的優勢在於速度，Spark的大部分操作都是在內存中，而Hadoop的MapRece系統會在每次操作之後將所有數據寫回到物理存儲介質上，這是為了確保在出現問題時能夠完全恢復，但Spark的彈性分布式數據存儲也能實現這一點
另外，在高級數據處理（如實時流處理、機器學習）方面，Spark的功能要勝過Hadoop
在Bernard看來，這一點連同其速度優勢是Spark越來越受歡迎的真正原因
實時處理意味著可以在數據捕獲的瞬間將其提交給分析型應用程序，並立即獲得反饋
在各種各樣的大數據應用程序中，這種處理的用途越來越多，比如，零售商使用的推薦引擎、製造業中的工業機械性能監控
Spark平台的速度和流數據處理能力也非常適合機器學習演算法，這類演算法可以自我學習和改進，直到找到問題的理想解決方案
這種技術是最先進製造系統（如預測零件何時損壞）和無人駕駛汽車的核心
Spark有自己的機器學習庫MLib，而Hadoop系統則需要藉助第三方機器學習庫，如Apache Mahout
實際上，雖然Spark和Hadoop存在一些功能上的重疊，但它們都不是商業產品，並不存在真正的競爭關系，而通過為這類免費系統提供技術支持贏利的公司往往同時提供兩種服務
例如，Cloudera 就既提供 Spark服務也提供 Hadoop服務，並會根據客戶的需要提供最合適的建議
Bernard認為，雖然Spark發展迅速，但它尚處於起步階段，安全和技術支持基礎設施方還不發達，在他看來，Spark在開源社區活躍度的上升，表明企業用戶正在尋找已存儲數據的創新用法

『陸』 Spark核心-RDD

RDD是Spark中的數據抽象，全稱 彈性分布式數據集（Resilient Distributed Datasets） 。RDD可以理解為將一個大的數據集合以分布式的形式保存在集群伺服器的內存中。RDD是一個容錯的、並行的數據結構，可以讓用戶顯式地將數據存儲到磁碟和內存中，並能控制數據的分區。

RDD是Spark的核心，也是整個Spark的架構基礎。

RDD的特點：

RDD的5個主要屬性：

可以通過兩種方式創建RDD：

轉換操作指的是在原RDD實例上進行計算，然後創建一個新的RDD實例。

RDD中的所有的轉換操作都是 惰性 的，在執行RDD的轉換操作的時候，並不會直接計算結果，而是記住這些應用到基礎數據集上的轉換動作，只有行動操作時，這些轉換才會真正的去執行。這樣設計的好處是更加有效率的運行。

行動操作指的是向驅動器程序返回結果或把結果寫入外部系統的操作。

Spark在調用RDD的行動操作的時候，會觸發Spark中的連鎖反應。當調用的行動操作的時候，Spark會嘗試創建作為調用者的RDD。如果這個RDD是從文件中創建的，那麼Spark會在worker節點上讀取文件至內存中。如果這個RDD是通過其他RDD的轉換得到的，Spark會嘗試創建其父RDD。這個過程會一直持續下去，直到Spark找到根RDD。然後Spark就會真正執行這些生成RDD所必須的轉換計算。最後完成行動操作，將結果返回給驅動程序或者寫入外部存儲。

Spark速度非常快的原因之一，就是在不同操作中在內存中持久化一個數據集。當持久化一個RDD後，每一個節點都將把計算的分片結果保存在內存中，並在對此數據集進行的其他動作中重用。這使得後續的動作變得更加迅速。緩存是Spark構建迭代演算法和快速互動式查詢的關鍵。所以我們在開發過程中，對經常使用的RDD要進行緩存操作，以提升程序運行效率。

RDD緩存的方法

RDD類提供了兩種緩存方法：

cache方法其實是將RDD存儲在集群中Worker的內存中。

persist是一個通用的cache方法。它可以將RDD存儲在內存中或硬碟上或者二者皆有。

緩存的容錯

緩存是有可能丟失（如機器宕機），或者存儲於內存的數據由於內存不足而被刪除。RDD的緩存的容錯機制保證了即使緩存丟失也能保證計算的正確執行。通過基於RDD的一系列的轉換，丟失的數據會被重新計算。因為RDD的各個Partition是相對獨立的，所以在重新計算的時候只需要計算丟失部分Partition即可，不需要重新計算全部的Partition。因此，在一個緩存RDD的節點出現故障的時候，Spark會在另外的節點上自動重新創建出現故障的節點中存儲的分區。

RDD的緩存能夠在第一次計算完成後，將計算結果保存到內存、本地文件系統或者Tachyon中。通過緩存，Spark避免了RDD上的重復計算，能夠極大地提升計算速度。但是，如果緩存丟失了，則需要重新計算。如果計算特別復雜或者計算特別耗時，那麼緩存丟失對於整個Job的影響是不容忽視的。為了避免緩存丟失重新計算帶來的開銷，所以Spark引入了檢查點（checkpoint）機制。

緩存是在計算結束後，直接將計算結果通過用戶定義的存儲級別寫入不同的介質。而檢查點不同，它是在計算完成後，重新建立一個Job來計算。所以為了避免重復計算，推薦先將RDD緩存，這樣在進行檢查點操作時就可以快速完成。

Spark會根據用戶提交的計算邏輯中的RDD的轉換和動作來生動RDD之間的依賴關系，同時這個計算鏈也就生成了邏輯上的DAG。

RDD之間的依賴關系包括：

Spark中的依賴關系主要體現為兩種形式：

『柒』 推薦系統中矩陣分解演算法-funkSVD和ALS

矩陣分解funkSVD:該矩陣分解不像是線代中的，他屬於偽分解。其主要思想是，用兩個m＊k和k＊n的矩陣代替m＊n的矩陣。

因為在推薦系統中，矩陣十分稀疏，分解後的矩陣一般是密集的，且可以通過行列相乘來得到空缺的值。

(其預測的是第u個用戶對第i個商品的評分)

其通過機器學習最小化損失函數來得到矩陣，

其學習方式有兩種，一種是隨機梯度下降，一種是交替最小二乘。

第一種不說，隨處可見。第二種是通過

該式子實現的。

我們先隨機化一個Q，因為R是那個稀疏矩陣已知，所以能得到P，我們再反過來用PR求Q。直到模型的誤差低於一個閾值。

上面的svd是對於評分的演算法，還有svd++等對用戶，物品做了偏移項。

隱式矩陣分解(最常見)ALS

我們一般的推薦問題不是通過評分推薦，因為評分的產生十分的困難，一般用戶沒有這個習慣。我們與其預測評分，不如去預測用戶行為。如果我們給用戶一個頁面有十個商品，我們預測到用戶會點擊哪一個，這不就說明用戶喜歡這個。而且基於用戶的信息很多。

我們的矩陣由1，0和空缺組成，1表示該用戶點擊過該商品(即表示用戶對它有想法)，0表示用戶對它沒有想法(怎麼是沒想法呢，我們定義用戶知道他卻不想了解他。即我們在所有沒有點擊該商品的用戶中抽樣，該商品越火熱抽取的人越多。因為熱門的東西大家應該都知道，而你卻沒點擊他，說明他不感興趣)

我們要將該矩陣分解。

我們的損失函數是

Cui是置信度，比如我點擊10次當時比只點擊一次的喜歡置信度高。

對於學習方法，我們使用加權交替最小二乘法

初始化Y，我們計算出x，再通過

計算出y。再反復交替，直到小於閾值。

該演算法目前在spark上有實現。且sparkml將其作為唯一的推薦系統演算法。

『捌』 spark als 每次運行推薦結果不一樣 帶隨機嗎

在ml中常見的優化演算法基本都是：sgd這種對每個單變數進行同步更新als(交替最小二乘）/smo(序列最小優化）這種交替（固定一個單變數，優化另一個單變數）思路。如果你熟悉smo，那麼als就也可以理解了。其它（希望的人補充）