機器學習大數據分析主流算法匯總
作者：探碼科技， 原文鏈接： http://m.nbbskj.com/blog/407
智能推薦系統算法
基于流行度的算法非常簡單粗暴，類似于各大新聞、微博熱榜等，根據PV、UV、日均PV或分享率等數據來按某種熱度排序來推薦給用戶。
這種算法的優點是簡單，適用于剛注冊的新用戶。缺點也很明顯，它無法針對用戶提供個性化的推薦。基于這種算法也可做一些優化，比如加入用戶分群的流行度排序，例如把熱榜上的體育內容優先推薦給體育迷，把政要熱文推給熱愛談論政治的用戶。
協同過濾算法(Collaborative Filtering, CF)是很常用的一種算法，在很多電商網站上都有用到。CF算法包括基于用戶的CF(User-based CF)和基于物品的CF(Item-based CF)。
基于用戶的CF原理如下：
1）分析各個用戶對item的評價（通過瀏覽記錄、購買記錄等）；
2）依據用戶對item的評價計算得出所有用戶之間的相似度；
3）選出與當前用戶最相似的N個用戶；
4）將這N個用戶評價最高并且當前用戶又沒有瀏覽過的item推薦給當前用戶。
基于物品的CF原理大同小異，只是主體在于物品：
1）分析各個用戶對item的瀏覽記錄。
2）依據瀏覽記錄分析得出所有item之間的相似度；
3）對于當前用戶評價高的item，找出與之相似度最高的N個item；
4）將這N個item推薦給用戶。
利用word2vec一類工具，可以將文本的關鍵詞聚類，然后根據topic將文本向量化。如可以將德甲、英超、西甲聚類到“足球”的topic下，將lv、Gucci聚類到“奢侈品”topic下，再根據topic為文本內容與用戶作相似度計算。
綜上，基于內容的推薦算法能夠很好地解決冷啟動問題，并且也不會囿于熱度的限制，因為它是直接基于內容匹配的，而與瀏覽記錄無關。然而它也會存在一些弊端，比如過度專業化(over-specialisation)的問題。這種方法會一直推薦給用戶內容密切關聯的item，而失去了推薦內容的多樣性。
基于模型的方法有很多，用到的諸如機器學習的方法也可以很深，這里只簡單介紹下比較簡單的方法——Logistics回歸預測。我們可以通過分析用戶的行為與使用記錄得到用戶的記錄表，從而得到用戶屬性與行為的非強關聯關系，通過大量測試與經驗，我們可以調整屬性的組合，擬合出最準確的回歸函數。
基于模型的算法由于快速、準確，適用于實時性比較高的業務如新聞、廣告等，而若是需要這種算法達到更好的效果，則需要人工干預反復的進行屬性的組合和篩選，也就是常說的Feature Engineering。而由于新聞的時效性，系統也需要反復更新線上的數學模型，以適應變化。
現實應用中，其實很少有直接用某種算法來做推薦的系統。在一些大的網站如Netflix，就是融合了數十種算法的推薦系統。我們可以通過給不同算法的結果加權重來綜合結果，或者是在不同的計算環節中運用不同的算法來混合，達到更貼合自己業務的目的。
智能分類系統算法
樸素貝葉斯分類是基于貝葉斯定理與特征條件獨立假設的分類方法，發源于古典數學理論，擁有穩定的數學基礎和分類效率。它是一種十分簡單的分類算法，當然簡單并不一定不好用。通過對給出的待分類項求解各項類別的出現概率大小，來判斷此待分類項屬于哪個類別，而在沒有多余條件的情況下，樸素貝葉斯分類會選擇在已知條件下，概率最大的類別。
樸素貝葉斯算法在執行文本分類等工作是會有很好的效果，比如樸素貝葉斯算法常被使用于垃圾郵件的過濾分類中。
- SVM算法
支持向量機（Support Vector Machine，常簡稱為 SVM）是一種監督式學習的方法，可廣泛地應用于統計分類以及回歸分析。支持向量機屬于一般化線性分類器，它能夠同時最小化經驗誤差與最大化幾何邊緣區，因此支持向量機也被稱為最大邊緣區分類器。
同時支持向量機將向量映射到一個更高維的空間里，在這個空間里建立有一個最大間隔超平面。在分開數據的超平面的兩邊建有兩個互相平行的超平面，分隔超平面使兩個平行超平面的距離最大化。假定平行超平面間的距離或差距越大，分類器的總誤差越小。
SVM 算法雖然存在難以訓練和難以解釋的問題，但是在非線性可分問題上的表現十分優秀，在非線性可分問題中常選擇 SVM 算法。
- 基于KNN的算法
K - 近鄰算法，簡稱 KNN（k-Nearest Neighbor），它同樣是一個比較簡單的分類、預測算法。對選取與待分類、待預測數據的最相似的 K 個訓練數據，通過對這 K 個數據的結果或者分類標號取平均、取眾數等方法得到待分類、待預測數據的結果或者分類標號。
KNN 算法相比其他算法也更加簡單，并且易于理解、實現，無需估計參數與訓練。適合對稀有事件進行分類和多分類方面的問題，在這類問題方面 KNN 算法的表現比 SVM 更好。
人工神經網絡，簡稱神經網絡或類神經網絡，是一種模仿生物神經網絡結構和功能的數學模型或計算模型，用于對函數進行估計或近似。神經網絡由大量的人工神經元聯結進行計算。大多數情況下人工神經網絡能在外界信息的基礎上改變內部結構，是一種自適應系統。
人工神經網絡在語音、圖片、視頻、游戲等各類應用場景展現出了優異的性能，但是存在需要大量的數據進行訓練來提高準確性的問題。
回歸算法
它是廣泛為人所知的模型技術之一。線性回歸常被選用在線性預測模型中，在這個模型中，因變量是連續的，自變量可以是連續或離散的，回歸線的性質是線性的。
線性回歸使用最佳擬合直線建立因變量(Y)和一個或多個獨立變量(X)之間的關系(也成為回歸線)
它是被方程式：Y = a + b*X + e 所表示，這里 a 為截距，b 為斜率和 e 為誤差項。這個方程式能基于給定的預測變量來預測目標變量的值。
邏輯回歸用于發現事件的概率=成功和事件的事件=失敗。當因變量是二進制（0/1，True / False，是/否）時，我們應該使用邏輯回歸。這里，Y的值的范圍從0到1，并且它可以由以下等式表示。
odds= p/(1-p) = probability of event occurrence / probability of not event occurrence
ln(odds) = ln(p/(1-p))
logit(p) = ln(p/(1-p)) = b0+b1X1+b2X2+b3X3….+bkXk
上面，p是有特征存在的概率。你應該問的是“為什么我們在方程中使用log？”。
因為我們這里用二項分布（因變量），我們需要選擇最適合這種分布的鏈接函數。并且，它是logit函數。在上面的等式中，選擇參數用來最大化這些觀察樣本的似然值，而不是最小化平方誤差的和（類似于普通回歸）。
如果自變量的冪大于1，則回歸方程是多項式回歸方程。
在這種回歸技術中，最佳擬合線并不是直線。它是一條擬合數據點的曲線。
當我們處理多個自變量時常使用這種形式的回歸。在這種技術中，獨立變量的選擇是借助于自動過程完成的，其不用涉及到人類干預。
它的專長是通過觀察統計值，如R平方，t統計和AIC度量來辨別重要變量。逐步回歸基本上適合回歸模型，通過基于指定標準一次一個地添加/刪除共變量。
該建模技術的目的是利用最小數量的預測變量來最大化預測能力。它是處理更高維度數據集的方法之一。
- Ridge回歸
Ridge回歸是當數據受多重共線性（自相關變量高度相關）時常使用的技術。在多重共線性中，即使最小二乘估計（OLS）是無偏的，它們的方差很大，這偏離了觀察值遠離真實值。通過對回歸估計增加一定程度的偏差，Ridge回歸減小了標準誤差。
- Lasso回歸
與Ridge回歸類似，Lasso（最小絕對收縮和選擇算子）也懲罰回歸系數的絕對大小。此外，它能夠減少變化性和提高線性回歸模型的準確性。Lasso回歸與Ridge回歸的區別在于，它使用的是絕對值懲罰函數而不是平方懲罰函數。這使懲罰（或等價地約束估計的絕對值的和）值導致一些參數估計精確地為零。使用更大的懲罰會讓估計進一步的收縮到絕對零。這導致在給定的n個變量中作變量選擇。
ElasticNet是Lasso和Ridge回歸技術的混合模型。它是用L1和L2作為正則化訓練的。當有多個相關的特征時，Elastic-net是有用的，Lasso可能隨機選擇其中一個，Elastic-net很可能選擇兩個。
在Lasso和Ridge之間折衷的實際優點是它允許Elastic-Net繼承一些Ridge的穩定性。
自然語言處理算法
隱馬爾可夫模型原本是通信領域一個著名的模型。用于通信的編解碼上。
我們發現，隱馬爾可夫模型中，觀察層只與對應的一個隱含層有關系，實際情況往往并非如此，比如詞性標注，翻譯，句法分析等，某一個觀察層的狀態往往與多個隱含層以及相鄰觀察層的狀態有關。條件隨機場便是能處理這種復雜seqToseq的模型。
每個隱馬爾可夫模型都可以轉化為條件隨機場模型。隱馬爾可夫模型主要用于語音識別等方面，其他方面用條件隨機場效果較好。
聚類算法
- k-means聚類算法
算法步驟：
1）首先我們選擇一些類/組，并隨機初始化它們各自的中心點。中心點是與每個數據點向量長度相同的位置。這需要我們提前預知類的數量(即中心點的數量)。
2）計算每個數據點到中心點的距離，數據點距離哪個中心點最近就劃分到哪一類中。
3）計算每一類中中心點作為新的中心點。
4）重復以上步驟，直到每一類中心在每次迭代后變化不大為止。也可以多次隨機初始化中心點，然后選擇運行結果最好的一個。
均值漂移聚類是基于滑動窗口的算法，來找到數據點的密集區域。這是一個基于質心的算法，通過將中心點的候選點更新為滑動窗口內點的均值來完成，來定位每個組/類的中心點。然后對這些候選窗口進行相似窗口進行去除，最終形成中心點集及相應的分組。
具體步驟：
1）確定滑動窗口半徑r，以隨機選取的中心點C半徑為r的圓形滑動窗口開始滑動。均值漂移類似一種爬山算法，在每一次迭代中向密度更高的區域移動，直到收斂。
2）每一次滑動到新的區域，計算滑動窗口內的均值來作為中心點，滑動窗口內的點的數量為窗口內的密度。在每一次移動中，窗口會想密度更高的區域移動。
3）移動窗口，計算窗口內的中心點以及窗口內的密度，知道沒有方向在窗口內可以容納更多的點，即一直移動到圓內密度不再增加為止。
4）步驟一到三會產生很多個滑動窗口，當多個滑動窗口重疊時，保留包含最多點的窗口，然后根據數據點所在的滑動窗口進行聚類。?
與均值漂移聚類類似，DBSCAN也是基于密度的聚類算法。
具體步驟：
1）首先確定半徑r和minPoints. 從一個沒有被訪問過的任意數據點開始，以這個點為中心，r為半徑的圓內包含的點的數量是否大于或等于minPoints，如果大于或等于minPoints則改點被標記為central point,反之則會被標記為noise point。
2）重復1的步驟，如果一個noise point存在于某個central point為半徑的圓內，則這個點被標記為邊緣點，反之仍為noise point。重復步驟1，知道所有的點都被訪問過。
使用高斯混合模型（GMM）做聚類首先假設數據點是呈高斯分布的，相對應K-Means假設數據點是圓形的，高斯分布（橢圓形）給出了更多的可能性。我們有兩個參數來描述簇的形狀：均值和標準差。所以這些簇可以采取任何形狀的橢圓形，因為在x，y方向上都有標準差。因此，每個高斯分布被分配給單個簇。
所以要做聚類首先應該找到數據集的均值和標準差，我們將采用一個叫做最大期望(EM)的優化算法。下圖演示了使用GMMs進行最大期望的聚類過程。
具體步驟：
1）選擇簇的數量（與K-Means類似）并隨機初始化每個簇的高斯分布參數（均值和方差）。也可以先觀察數據給出一個相對精確的均值和方差。
2）給定每個簇的高斯分布，計算每個數據點屬于每個簇的概率。一個點越靠近高斯分布的中心就越可能屬于該簇。
3）基于這些概率我們計算高斯分布參數使得數據點的概率最大化，可以使用數據點概率的加權來計算這些新的參數，權重就是數據點屬于該簇的概率。
4）重復迭代2和3直到在迭代中的變化不大。
層次聚類算法分為兩類：自上而下和自下而上。凝聚層級聚類(HAC)是自下而上的一種聚類算法。HAC首先將每個數據點視為一個單一的簇，然后計算所有簇之間的距離來合并簇，知道所有的簇聚合成為一個簇為止。
具體步驟：
1）首先我們將每個數據點視為一個單一的簇，然后選擇一個測量兩個簇之間距離的度量標準。例如我們使用average linkage作為標準，它將兩個簇之間的距離定義為第一個簇中的數據點與第二個簇中的數據點之間的平均距離。
2）在每次迭代中，我們將兩個具有最小average linkage的簇合并成為一個簇。
3）重復步驟2知道所有的數據點合并成一個簇，然后選擇我們需要多少個簇。
當我們的數據可以被表示為網絡或圖是，可以使用圖團體檢測方法完成聚類。在這個算法中圖團體（graph community）通常被定義為一種頂點(vertice)的子集，其中的頂點相對于網絡的其他部分要連接的更加緊密。
具體步驟：
1）首先初始分配每個頂點到其自己的團體，然后計算整個網絡的模塊性 M。
2）第1步要求每個團體對（community pair）至少被一條單邊鏈接，如果有兩個團體融合到了一起，該算法就計算由此造成的模塊性改變 ΔM。
3）第2步是取ΔM出現了最大增長的團體對，然后融合。然后為這個聚類計算新的模塊性 M，并記錄下來。
4）重復第1步和第2步——每一次都融合團體對，這樣最后得到ΔM的最大增益，然后記錄新的聚類模式及其相應的模塊性分數 M。
5）重復第1步和第2步——每一次都融合團體對，這樣最后得到 ΔM 的最大增益，然后記錄新的聚類模式及其相應的模塊性分數 M。
相識度度量算法
這個基本上是最常用的，最初用在計算文本相似度效果很好，一般像tf-idf一下然后計算，推薦中在協同過濾以及很多算法中都比其他相似度效果理想。
由于余弦相似度表示方向上的差異，對距離不敏感，所以有時候也關心距離上的差異會先對每個值都減去一個均值，這樣稱為調整余弦相似度
基本上就是兩個點的空間距離，下面這個圖就能很明顯的說明他和余弦相似度區別，歐式距離更多考慮的是空間中兩條直線的距離，而余弦相似度關心的是空間夾角。所以歐氏距離能夠體現個體數值特征的絕對差異，所以更多的用于需要從維度的數值大小中體現差異的分析，如使用用戶行為指標分析用戶價值的相似度或差異。
余弦距離更多的是從方向上區分差異，而對絕對的數值不敏感，更多的用于使用用戶對內容評分來區分興趣的相似度和差異，同時修正了用戶間可能存在的度量標準不統一的問題（因為余弦距離對絕對數值不敏感）。
其實這個就是前面講的調整的余弦相似度，因為在推薦系統中均值分為用戶的均值和物品的均值，這里相當于是物品的均值。這個也是比較常用的。
斯皮爾曼等級相關（Spearman’s correlation coefficient for ranked data）主要用于解決稱名數據和順序數據相關的問題。適用于兩列變量，而且具有等級變量性質具有線性關系的資料。由英國心理學家、統計學家斯皮爾曼根據積差相關的概念推導而來，一些人把斯皮爾曼等級相關看做積差相關的特殊形式。
