大數據十大經典演算法
A. 大數據挖掘需要學習哪些技術大數據的工作
處理大數據需要一個綜合、復雜、多方位的系統，系統中的處理模塊有很多，而數據挖掘技術以一個獨立的身份存在於處理大數據的整個系統之中，與其他模塊之間相輔相成、協調發展。在大數據時代中，數據挖掘技術的地位是無可比擬的。
數據挖掘的基本流程
在正式講數據挖掘知識清單之前，我先和你聊聊數據挖掘的基本流程。
數據挖掘的過程可以分成以下 6 個步驟。
商業理解：數據挖掘不是我們的目的，我們的目的是更好地幫助業務，所以第一步我們要從商業的角度理解項目需求，在這個基礎上，再對數據挖掘的目標進行定義。
數據理解：嘗試收集部分數據，然後對數據進行探索，包括數據描述、數據質量驗證等。這有助於你對收集的數據有個初步的認知。
數據准備：開始收集數據，並對數據進行清洗、數據集成等操作，完成數據挖掘前的准備工作。
模型建立：選擇和應用各種數據挖掘模型，並進行優化，以便得到更好的分類結果。
模型評估：對模型進行評價，並檢查構建模型的每個步驟，確認模型是否實現了預定的商業目標。
上線發布：模型的作用是從數據中找到金礦，也就是我們所說的「知識」，獲得的知識需要轉化成用戶可以使用的方式，呈現的形式可以是一份報告，也可以是實現一個比較復雜的、可重復的數據挖掘過程。數據挖掘結果如果是日常運營的一部分，那麼後續的監控和維護就會變得重要。
數據挖掘的十大演算法
為了進行數據挖掘任務，數據科學家們提出了各種模型，在眾多的數據挖掘模型中，國際權威的學術組織 ICDM （the IEEE International Conference on Data Mining）評選出了十大經典的演算法。
按照不同的目的，我可以將這些演算法分成四類，以便你更好的理解。
分類演算法：C4.5，樸素貝葉斯（Naive Bayes），SVM，KNN，Adaboost，CART
聚類演算法：K-Means，EM
關聯分析：Apriori
連接分析：PageRank
1. C4.5
C4.5 演算法是得票最高的演算法，可以說是十大演算法之首。C4.5 是決策樹的演算法，它創造性地在決策樹構造過程中就進行了剪枝，並且可以處理連續的屬性，也能對不完整的數據進行處理。它可以說是決策樹分類中，具有里程碑式意義的演算法。
2. 樸素貝葉斯（Naive Bayes）
樸素貝葉斯模型是基於概率論的原理，它的思想是這樣的：對於給出的未知物體想要進行分類，就需要求解在這個未知物體出現的條件下各個類別出現的概率，哪個最大，就認為這個未知物體屬於哪個分類。
3. SVM
SVM 的中文叫支持向量機，英文是 Support Vector Machine，簡稱 SVM。SVM 在訓練中建立了一個超平面的分類模型。如果你對超平面不理解，沒有關系，我在後面的演算法篇會給你進行介紹。
4. KNN
KNN 也叫 K 最近鄰演算法，英文是 K-Nearest Neighbor。所謂 K 近鄰，就是每個樣本都可以用它最接近的 K 個鄰居來代表。如果一個樣本，它的 K 個最接近的鄰居都屬於分類 A，那麼這個樣本也屬於分類 A。
5. AdaBoost
Adaboost 在訓練中建立了一個聯合的分類模型。boost 在英文中代表提升的意思，所以 Adaboost 是個構建分類器的提升演算法。它可以讓我們多個弱的分類器組成一個強的分類器，所以 Adaboost 也是一個常用的分類演算法。
6. CART
CART 代表分類和回歸樹，英文是 Classification and Regression Trees。像英文一樣，它構建了兩棵樹：一棵是分類樹，另一個是回歸樹。和 C4.5 一樣，它是一個決策樹學習方法。
7. Apriori
Apriori 是一種挖掘關聯規則（association rules）的演算法，它通過挖掘頻繁項集（frequent item sets）來揭示物品之間的關聯關系，被廣泛應用到商業挖掘和網路安全等領域中。頻繁項集是指經常出現在一起的物品的集合，關聯規則暗示著兩種物品之間可能存在很強的關系。
8. K-Means
K-Means 演算法是一個聚類演算法。你可以這么理解，最終我想把物體劃分成 K 類。假設每個類別裡面，都有個「中心點」，即意見領袖，它是這個類別的核心。現在我有一個新點要歸類，這時候就只要計算這個新點與 K 個中心點的距離，距離哪個中心點近，就變成了哪個類別。
9. EM
EM 演算法也叫最大期望演算法，是求參數的最大似然估計的一種方法。原理是這樣的：假設我們想要評估參數 A 和參數 B，在開始狀態下二者都是未知的，並且知道了 A 的信息就可以得到 B 的信息，反過來知道了 B 也就得到了 A。可以考慮首先賦予 A 某個初值，以此得到 B 的估值，然後從 B 的估值出發，重新估計 A 的取值，這個過程一直持續到收斂為止。
EM 演算法經常用於聚類和機器學習領域中。
10. PageRank
PageRank 起源於論文影響力的計算方式，如果一篇文論被引入的次數越多，就代表這篇論文的影響力越強。同樣 PageRank 被 Google 創造性地應用到了網頁權重的計算中：當一個頁面鏈出的頁面越多，說明這個頁面的「參考文獻」越多，當這個頁面被鏈入的頻率越高，說明這個頁面被引用的次數越高。基於這個原理，我們可以得到網站的權重劃分。
最後
演算法可以說是數據挖掘的靈魂，也是最精華的部分。這 10 個經典演算法在整個數據挖掘領域中的得票最高的，後面的一些其他演算法也基本上都是在這個基礎上進行改進和創新。今天你先對十大演算法有一個初步的了解，你只需要做到心中有數就可以了。
B. 數據挖掘十大經典演算法（1）——樸素貝葉斯(Naive Bayes)
在此推出一個演算法系列的科普文章。我們大家在平時埋頭工程類工作之餘，也可以抽身對一些常見演算法進行了解，這不僅可以幫助我們拓寬思路，從另一個維度加深對計算機技術領域的理解，做到觸類旁通，同時也可以讓我們搞清楚一些既熟悉又陌生的領域——比如數據挖掘、大數據、機器學習——的基本原理，揭開它們的神秘面紗，了解到其實很多看似高深的領域，其實背後依據的基礎和原理也並不復雜。而且，掌握各類演算法的特點、優劣和適用場景，是真正從事數據挖掘工作的重中之重。只有熟悉演算法，才可能對紛繁復雜的現實問題合理建模，達到最佳預期效果。
本系列文章的目的是力求用最干練而生動的講述方式，為大家講解由國際權威的學術組織the IEEE International Conference on Data Mining (ICDM) 於2006年12月評選出的數據挖掘領域的十大經典演算法。它們包括：
本文作為本系列的第一篇，在介紹具體演算法之前，先簡單為大家鋪墊幾個數據挖掘領域的常見概念：
在數據挖掘領域，按照演算法本身的行為模式和使用目的，主要可以分為分類(classification)，聚類(clustering)和回歸(regression)幾種，其中：
打幾個不恰當的比方 ：
另外，還有一個經常有人問起的問題，就是 數據挖掘 和 機器學習 這兩個概念的區別，這里一句話闡明我自己的認識：機器學習是基礎，數據挖掘是應用。機器學習研製出各種各樣的演算法，數據挖掘根據應用場景把這些演算法合理運用起來，目的是達到最好的挖掘效果。
當然，以上的簡單總結一定不夠准確和嚴謹，更多的是為了方便大家理解打的比方。如果大家有更精當的理解，歡迎補充和交流。
好了，鋪墊了這么多，現在終於進入正題！
作為本系列入門的第一篇，先為大家介紹一個容易理解又很有趣的演算法—— 樸素貝葉斯 。
先站好隊，樸素貝葉斯是一個典型的 有監督的分類演算法 。
光從名字也可以想到，要想了解樸素貝葉斯，先要從 貝葉斯定理 說起。
貝葉斯定理是我們高中時代學過的一條概率學基礎定理，它描述了條件概率的計算方式。不要怕已經把這些知識還給了體育老師，相信你一看公式就能想起來。
P(A|B)表示事件B已經發生的前提下，事件A發生的概率，叫做事件B發生下事件A的條件概率。其基本求解公式為：
其中，P(AB)表示A和B同時發生的概率，P(B)標識B事件本身的概率。
貝葉斯定理之所以有用，是因為我們在生活中經常遇到這種情況：我們可以很容易直接得出P(A|B)，P(B|A)則很難直接得出，但我們更關心P(B|A)。
而貝葉斯定理就為我們打通從P(A|B)獲得P(B|A)的道路。
下面不加證明地直接給出貝葉斯定理：
有了貝葉斯定理這個基礎，下面來看看樸素貝葉斯演算法的基本思路。
你看，其思想就是這么的樸素。那麼，屬於每個分類的概率該怎麼計算呢？下面我們先祭出形式化語言！
那麼現在的關鍵就是如何計算第3步中的各個條件概率。我們可以這么做：
因為分母對於所有類別為常數，因為我們只要將分子最大化皆可。又因為各特徵屬性是條件獨立的，所以有：
如果你也跟我一樣，對形式化語言有嚴重生理反應，不要怕，直接跳過前面這一坨，我們通過一個鮮活的例子，用人類的語言再解釋一遍這個過程。
某個醫院早上收了六個門診病人，如下表。
現在又來了第七個病人，是一個打噴嚏的建築工人。請問他最有可能患有何種疾病？
本質上，這就是一個典型的分類問題， 症狀 和 職業 是特徵屬性， 疾病種類 是目標類別
根據 貝葉斯定理
可得
假定"打噴嚏"和"建築工人"這兩個特徵是獨立的，因此，上面的等式就變成了
這是可以計算的。
因此，這個打噴嚏的建築工人，有66%的概率是得了感冒。同理，可以計算這個病人患上過敏或腦震盪的概率。比較這幾個概率，就可以知道他最可能得什麼病。
接下來，我們再舉一個樸素貝葉斯演算法在實際中經常被使用的場景的例子—— 文本分類器 ，通常會用來識別垃圾郵件。
首先，我們可以把一封郵件的內容抽象為由若干關鍵片語成的集合，這樣是否包含每種關鍵詞就成了一封郵件的特徵值，而目標類別就是 屬於垃圾郵件 或 不屬於垃圾郵件
假設每個關鍵詞在一封郵件里出現與否的概率相互之間是獨立的，那麼只要我們有若干已經標記為垃圾郵件和非垃圾郵件的樣本作為訓練集，那麼就可以得出，在全部垃圾郵件（記為Trash）出現某個關鍵詞Wi的概率，即 P(Wi|Trash)
而我們最重要回答的問題是，給定一封郵件內容M，它屬於垃圾郵件的概率是多大，即 P(Trash|M)
根據貝葉斯定理，有
我們先來看分子：
P(M|Trash) 可以理解為在垃圾郵件這個范疇中遇見郵件M的概率，而一封郵件M是由若干單詞Wi獨立匯聚組成的，只要我們所掌握的單詞樣本足夠多，因此就可以得到
這些值我們之前已經可以得到了。
再來看分子里的另一部分 P(Trash) ，這個值也就是垃圾郵件的總體概率，這個值顯然很容易得到，用訓練集中垃圾郵件數除以總數即可。
而對於分母來說，我們雖然也可以去計算它，但實際上已經沒有必要了，因為我們要比較的 P(Trash|M) 和 P(non-Trash|M) 的分母都是一樣的，因此只需要比較分子大小即可。
這樣一來，我們就可以通過簡單的計算，比較郵件M屬於垃圾還是非垃圾二者誰的概率更大了。
樸素貝葉斯的英文叫做 Naive Bayes ，直譯過來其實是 天真的貝葉斯 ，那麼他到底天真在哪了呢？
這主要是因為樸素貝葉斯的基本假設是所有特徵值之間都是相互獨立的，這才使得概率直接相乘這種簡單計算方式得以實現。然而在現實生活中，各個特徵值之間往往存在一些關聯，比如上面的例子，一篇文章中不同單詞之間一定是有關聯的，比如有些詞總是容易同時出現。
因此，在經典樸素貝葉斯的基礎上，還有更為靈活的建模方式—— 貝葉斯網路（Bayesian Belief Networks, BBN） ，可以單獨指定特徵值之間的是否獨立。這里就不展開了，有興趣的同學們可以做進一步了解。
最後我們來對這個經典演算法做個點評：
優點：
缺點：
好了，對於 樸素貝葉斯 的介紹就到這里，不知道各位看完之後是否會對數據挖掘這個領域產生了一點興趣了呢？
C. 大數據最常用的演算法有哪些
奧地利符號計算研究所(Research Institute for Symbolic Computation，簡稱RISC)的Christoph Koutschan博士在自己的頁面上發布了一篇文章，提到他做了一個調查，參與者大多數是計算機科學家，他請這些科學家投票選出最重要的演算法，以下是這次調查的結果，按照英文名稱字母順序排序。
大數據等最核心的關鍵技術：32個演算法
1、A* 搜索演算法——圖形搜索演算法，從給定起點到給定終點計算出路徑。其中使用了一種啟發式的估算，為每個節點估算通過該節點的最佳路徑，並以之為各個地點排定次序。演算法以得到的次序訪問這些節點。因此，A*搜索演算法是最佳優先搜索的範例。
2、集束搜索(又名定向搜索，Beam Search)——最佳優先搜索演算法的優化。使用啟發式函數評估它檢查的每個節點的能力。不過，集束搜索只能在每個深度中發現最前面的m個最符合條件的節點，m是固定數字——集束的寬度。
3、二分查找(Binary Search)——在線性數組中找特定值的演算法，每個步驟去掉一半不符合要求的數據。
4、分支界定演算法(Branch and Bound)——在多種最優化問題中尋找特定最優化解決方案的演算法，特別是針對離散、組合的最優化。
5、Buchberger演算法——一種數學演算法，可將其視為針對單變數最大公約數求解的歐幾里得演算法和線性系統中高斯消元法的泛化。
6、數據壓縮——採取特定編碼方案，使用更少的位元組數(或是其他信息承載單元)對信息編碼的過程，又叫來源編碼。
7、Diffie-Hellman密鑰交換演算法——一種加密協議，允許雙方在事先不了解對方的情況下，在不安全的通信信道中，共同建立共享密鑰。該密鑰以後可與一個對稱密碼一起，加密後續通訊。
8、Dijkstra演算法——針對沒有負值權重邊的有向圖，計算其中的單一起點最短演算法。
9、離散微分演算法(Discrete differentiation)。
10、動態規劃演算法(Dynamic Programming)——展示互相覆蓋的子問題和最優子架構演算法
11、歐幾里得演算法(Euclidean algorithm)——計算兩個整數的最大公約數。最古老的演算法之一，出現在公元前300前歐幾里得的《幾何原本》。
12、期望-最大演算法(Expectation-maximization algorithm，又名EM-Training)——在統計計算中，期望-最大演算法在概率模型中尋找可能性最大的參數估算值，其中模型依賴於未發現的潛在變數。EM在兩個步驟中交替計算，第一步是計算期望，利用對隱藏變數的現有估計值，計算其最大可能估計值;第二步是最大化，最大化在第一步上求得的最大可能值來計算參數的值。
13、快速傅里葉變換(Fast Fourier transform，FFT)——計算離散的傅里葉變換(DFT)及其反轉。該演算法應用范圍很廣，從數字信號處理到解決偏微分方程，到快速計算大整數乘積。
14、梯度下降(Gradient descent)——一種數學上的最優化演算法。
15、哈希演算法(Hashing)。
16、堆排序(Heaps)。
17、Karatsuba乘法——需要完成上千位整數的乘法的系統中使用，比如計算機代數系統和大數程序庫，如果使用長乘法，速度太慢。該演算法發現於1962年。
18、LLL演算法(Lenstra-Lenstra-Lovasz lattice rection)——以格規約(lattice)基數為輸入，輸出短正交向量基數。LLL演算法在以下公共密鑰加密方法中有大量使用：背包加密系統(knapsack)、有特定設置的RSA加密等等。
19、最大流量演算法(Maximum flow)——該演算法試圖從一個流量網路中找到最大的流。它優勢被定義為找到這樣一個流的值。最大流問題可以看作更復雜的網路流問題的特定情況。最大流與網路中的界面有關，這就是最大流-最小截定理(Max-flow min-cut theorem)。Ford-Fulkerson 能找到一個流網路中的最大流。
20、合並排序(Merge Sort)。
21、牛頓法(Newton』s method)——求非線性方程(組)零點的一種重要的迭代法。
22、Q-learning學習演算法——這是一種通過學習動作值函數(action-value function)完成的強化學習演算法，函數採取在給定狀態的給定動作，並計算出期望的效用價值，在此後遵循固定的策略。Q-leanring的優勢是，在不需要環境模型的情況下，可以對比可採納行動的期望效用。
23、兩次篩法(Quadratic Sieve)——現代整數因子分解演算法，在實踐中，是目前已知第二快的此類演算法(僅次於數域篩法Number Field Sieve)。對於110位以下的十位整數，它仍是最快的，而且都認為它比數域篩法更簡單。
24、RANSAC——是「RANdom SAmple Consensus」的縮寫。該演算法根據一系列觀察得到的數據，數據中包含異常值，估算一個數學模型的參數值。其基本假設是：數據包含非異化值，也就是能夠通過某些模型參數解釋的值，異化值就是那些不符合模型的數據點。
25、RSA——公鑰加密演算法。首個適用於以簽名作為加密的演算法。RSA在電商行業中仍大規模使用，大家也相信它有足夠安全長度的公鑰。
26、Sch?nhage-Strassen演算法——在數學中，Sch?nhage-Strassen演算法是用來完成大整數的乘法的快速漸近演算法。其演算法復雜度為：O(N log(N) log(log(N)))，該演算法使用了傅里葉變換。
27、單純型演算法(Simplex Algorithm)——在數學的優化理論中，單純型演算法是常用的技術，用來找到線性規劃問題的數值解。線性規劃問題包括在一組實變數上的一系列線性不等式組，以及一個等待最大化(或最小化)的固定線性函數。
28、奇異值分解(Singular value decomposition，簡稱SVD)——在線性代數中，SVD是重要的實數或復數矩陣的分解方法，在信號處理和統計中有多種應用，比如計算矩陣的偽逆矩陣(以求解最小二乘法問題)、解決超定線性系統(overdetermined linear systems)、矩陣逼近、數值天氣預報等等。
29、求解線性方程組(Solving a system of linear equations)——線性方程組是數學中最古老的問題，它們有很多應用，比如在數字信號處理、線性規劃中的估算和預測、數值分析中的非線性問題逼近等等。求解線性方程組，可以使用高斯—約當消去法(Gauss-Jordan elimination)，或是柯列斯基分解( Cholesky decomposition)。
30、Strukturtensor演算法——應用於模式識別領域，為所有像素找出一種計算方法，看看該像素是否處於同質區域( homogenous region)，看看它是否屬於邊緣，還是是一個頂點。
31、合並查找演算法(Union-find)——給定一組元素，該演算法常常用來把這些元素分為多個分離的、彼此不重合的組。不相交集(disjoint-set)的數據結構可以跟蹤這樣的切分方法。合並查找演算法可以在此種數據結構上完成兩個有用的操作：
查找：判斷某特定元素屬於哪個組。
合並：聯合或合並兩個組為一個組。
32、維特比演算法(Viterbi algorithm)——尋找隱藏狀態最有可能序列的動態規劃演算法，這種序列被稱為維特比路徑，其結果是一系列可以觀察到的事件，特別是在隱藏的Markov模型中。
以上就是Christoph博士對於最重要的演算法的調查結果。你們熟悉哪些演算法?又有哪些演算法是你們經常使用的?
D. 大數據挖掘的演算法有哪些
大數據挖掘的演算法：
1.樸素貝葉斯，超級簡單，就像做一些數數的工作。如果條件獨立假設成立的話，NB將比鑒別模型收斂的更快，所以你只需要少量的訓練數據。即使條件獨立假設不成立，NB在實際中仍然表現出驚人的好。
2. Logistic回歸，LR有很多方法來對模型正則化。比起NB的條件獨立性假設，LR不需要考慮樣本是否是相關的。與決策樹與支持向量機不同，NB有很好的概率解釋，且很容易利用新的訓練數據來更新模型。如果你想要一些概率信息或者希望將來有更多數據時能方便的更新改進模型，LR是值得使用的。
3.決策樹，DT容易理解與解釋。DT是非參數的，所以你不需要擔心野點（或離群點）和數據是否線性可分的問題，DT的主要缺點是容易過擬合，這也正是隨機森林等集成學習演算法被提出來的原因。
4.支持向量機，很高的分類正確率，對過擬合有很好的理論保證，選取合適的核函數，面對特徵線性不可分的問題也可以表現得很好。SVM在維數通常很高的文本分類中非常的流行。
如果想要或許更多更詳細的訊息，建議您去參加CDA數據分析課程。大數據分析師現在有專業的國際認證證書了，CDA，即「CDA 數據分析師」，是在數字經濟大背景和人工智慧時代趨勢下，面向全行業的專業權威國際資格認證， 旨在提升全民數字技能，助力企業數字化轉型，推動行業數字化發展。 「CDA 數據分析師」具體指在互聯網、金融、零售、咨詢、電信、醫療、旅遊等行業專門從事數據的採集、清洗、處理、分析並能製作業務報告、 提供決策的新型數據分析人才。點擊預約免費試聽課。
E. 大數據經典演算法解析（5）一EM演算法
姓名：崔升 學號：14020120005
【嵌牛導讀】：
EM作為一種經典的處理大數據的演算法，是我們在學習互聯網大數據時不得不去了解的一種常用演算法
【嵌牛鼻子】：經典大數據演算法之EM簡單介紹
【嵌牛提問】：EM是一種怎麼的演算法，其如何去觀測其中隱變數的？
【嵌牛正文】：
1. 極大似然
極大似然（Maximum Likelihood）估計為用於已知模型的參數估計的統計學方法。比如，我們想了解拋硬幣是正面（head）的概率分布θθ；那麼可以通過最大似然估計方法求得。假如我們拋硬幣1010次，其中88次正面、22次反面；極大似然估計參數θθ值：
θ^=argmaxθl(θ)=argmaxθθ8(1−θ)2θ^=argmaxθl(θ)=argmaxθθ8(1−θ)2
其中，l(θ)l(θ)為觀測變數序列的似然函數（likelihood function of the observation sequence）。對l(θ)l(θ)求偏導
∂l(θ)∂θ=θ7(1−θ)(8−10θ)⇒θ^=0.8∂l(θ)∂θ=θ7(1−θ)(8−10θ)⇒θ^=0.8
因為似然函數l(θ)l(θ)不是凹函數（concave），求解極大值困難。一般地，使用與之具有相同單調性的log-likelihood，如圖所示
凹函數（concave）與凸函數（convex）的定義如圖所示：
從圖中可以看出，凹函數「容易」求解極大值，凸函數「容易」求解極小值。
2. EM演算法
EM演算法（Expectation Maximization）是在含有隱變數（latent variable）的模型下計算最大似然的一種演算法。所謂隱變數，是指我們沒有辦法觀測到的變數。比如，有兩枚硬幣A、B，每一次隨機取一枚進行拋擲，我們只能觀測到硬幣的正面與反面，而不能觀測到每一次取的硬幣是否為A；則稱每一次的選擇拋擲硬幣為隱變數。
用Y表示觀測數據，Z表示隱變數；Y和Z連在一起稱為完全數據( complete-data )，觀測數據Y又稱為不完全數據(incomplete-data)。觀測數據的似然函數：
P(Y|θ)=∑ZP(Z|θ)P(Y|Z,θ)P(Y|θ)=∑ZP(Z|θ)P(Y|Z,θ)
求模型參數的極大似然估計：
θ^=argmaxθlogP(Y|θ)θ^=argmaxθlogP(Y|θ)
因為含有隱變數，此問題無法求解。因此，Dempster等人提出EM演算法用於迭代求解近似解。EM演算法比較簡單，分為兩個步驟：
E步（E-step），以當前參數θ(i)θ(i)計算ZZ的期望值
Q(θ,θ(i))=EZ[logP(Y,X|θ)|Y,θ(i)]Q(θ,θ(i))=EZ[logP(Y,X|θ)|Y,θ(i)]
M步（M-step），求使Q(θ,θ(i))Q(θ,θ(i))極大化的θθ，確定第i+1i+1次迭代的參數的估計值θ(i+1)θ(i+1)
θ(i+1)=argmaxθQ(θ,θ(i))θ(i+1)=argmaxθQ(θ,θ(i))
如此迭代直至演算法收斂。關於演算法的推導及收斂性證明，可參看李航的《統計學習方法》及Andrew Ng的《CS229 Lecture notes》。 這里 有一些極大似然以及EM演算法的生動例子。
3. 實例
[2]中給出極大似然與EM演算法的實例。如圖所示，有兩枚硬幣A、B，每一個實驗隨機取一枚拋擲10次，共5個實驗，我們 可以 觀測到每一次所取的硬幣，估計參數A、B為正面的概率θ=(θA,θB)θ=(θA,θB)，根據極大似然估計求解
如果我們 不能 觀測到每一次所取的硬幣，只能用EM演算法估計模型參數，演算法流程如圖所示：
隱變數ZZ為每次實驗中選擇A或B的概率，則第一個實驗選擇A的概率為
P(z1=A|y1,θ(0))=P(z1=A|y1,θ(0))P(z1=A|y1,θ(0))+P(z1=B|y1,θ(0))=0.65∗0.450.65∗0.45+0.510=0.45P(z1=A|y1,θ(0))=P(z1=A|y1,θ(0))P(z1=A|y1,θ(0))+P(z1=B|y1,θ(0))=0.65∗0.450.65∗0.45+0.510=0.45
按照上面的計算方法可依次求出隱變數ZZ，然後計算極大化的θ(i)θ(i)。經過10次迭代，最終收斂。
4. 參考資料
[1] 李航，《統計學習方法》.
[2] Chuong B Do & Serafim Batzoglou, What is the expectation maximization algorithm?
[3] Pieter Abbeel, Maximum Likelihood (ML), Expectation Maximization (EM) .
[4] Rudan Chen, 【機器學習演算法系列之一】EM演算法實例分析 .
F. 大數據常用的各種演算法
我們經常談到的所謂的 數據挖掘 是通過大量的數據集進行排序，自動化識別趨勢和模式並且建立相關性的過程。那現在市面的數據公司都是通過各種各樣的途徑來收集海量的信息，這些信息來自於網站、公司應用、社交媒體、移動設備和不斷增長的物聯網。
比如我們現在每天都在使用的搜索引擎。在自然語言處理領域，有一種非常流行的演算法模型，叫做詞袋模型，即把一段文字看成一袋水果，這個模型就是要算出這袋水果里，有幾個蘋果、幾個香蕉和幾個梨。搜索引擎會把這些數字記下來，如果你想要蘋果，它就會把有蘋果的這些袋子給你。
當我們在網上買東西或是看電影時，網站會推薦一些可能符合我們偏好的商品或是電影，這個推薦有時候還挺准。事實上，這背後的演算法，是在數你喜歡的電影和其他人喜歡的電影有多少個是一樣的，如果你們同時喜歡的電影超過一定個數，就把其他人喜歡、但你還沒看過的電影推薦給你。 搜索引擎和推薦系統 在實際生產環境中還要做很多額外的工作，但是從本質上來說，它們都是在數數。
當數據量比較小的時候，可以通過人工查閱數據。而到了大數據時代，幾百TB甚至上PB的數據在分析師或者老闆的報告中，就只是幾個數字結論而已。 在數數的過程中，數據中存在的信息也隨之被丟棄，留下的那幾個數字所能代表的信息價值，不抵其真實價值之萬一。 過去十年，許多公司花了大價錢，用上了物聯網和雲計算，收集了大量的數據，但是到頭來卻發現得到的收益並沒有想像中那麼多。
所以說我們現在正處於「 數字化一切 」的時代。人們的所有行為，都將以某種數字化手段轉換成數據並保存下來。每到新年，各大網站、App就會給用戶推送上一年的回顧報告，比如支付寶會告訴用戶在過去一年裡花了多少錢、在淘寶上買了多少東西、去什麼地方吃過飯、花費金額超過了百分之多少的小夥伴；航旅縱橫會告訴用戶去年做了多少次飛機、總飛行里程是多少、去的最多的城市是哪裡；同樣的，最後讓用戶知道他的行程超過了多少小夥伴。 這些報告看起來非常酷炫，又冠以「大數據」之名，讓用戶以為是多麼了不起的技術。
實際上，企業對於數據的使用和分析，並不比我們每年收到的年度報告更復雜。已經有30多年歷史的商業智能，看起來非常酷炫，其本質依然是數數，並把數出來的結果畫成圖給管理者看。只是在不同的行業、場景下，同樣的數字和圖表會有不同的名字。即使是最近幾年炙手可熱的大數據處理技術，也不過是可以數更多的數，並且數的更快一些而已。
在大數據處理過程中會用到那些演算法呢？
1、A* 搜索演算法——圖形搜索演算法，從給定起點到給定終點計算出路徑。其中使用了一種啟發式的估算，為每個節點估算通過該節點的較佳路徑，並以之為各個地點排定次序。演算法以得到的次序訪問這些節點。因此，A*搜索演算法是較佳優先搜索的範例。
2、集束搜索(又名定向搜索，Beam Search)——較佳優先搜索演算法的優化。使用啟發式函數評估它檢查的每個節點的能力。不過，集束搜索只能在每個深度中發現最前面的m個最符合條件的節點，m是固定數字——集束的寬度。
3、二分查找(Binary Search)——在線性數組中找特定值的演算法，每個步驟去掉一半不符合要求的數據。
4、分支界定演算法(Branch and Bound)——在多種最優化問題中尋找特定最優化解決方案的演算法，特別是針對離散、組合的最優化。
5、Buchberger演算法——一種數學演算法，可將其視為針對單變數較大公約數求解的歐幾里得演算法和線性系統中高斯消元法的泛化。
6、數據壓縮——採取特定編碼方案，使用更少的位元組數(或是其他信息承載單元)對信息編碼的過程，又叫來源編碼。
7、Diffie-Hellman密鑰交換演算法——一種加密協議，允許雙方在事先不了解對方的情況下，在不安全的通信信道中，共同建立共享密鑰。該密鑰以後可與一個對稱密碼一起，加密後續通訊。
8、Dijkstra演算法——針對沒有負值權重邊的有向圖，計算其中的單一起點最短演算法。
9、離散微分演算法(Discrete differentiation)。
10、動態規劃演算法(Dynamic Programming)——展示互相覆蓋的子問題和最優子架構演算法
11、歐幾里得演算法(Euclidean algorithm)——計算兩個整數的較大公約數。最古老的演算法之一，出現在公元前300前歐幾里得的《幾何原本》。
12、期望-較大演算法(Expectation-maximization algorithm，又名EM-Training)——在統計計算中，期望-較大演算法在概率模型中尋找可能性較大的參數估算值，其中模型依賴於未發現的潛在變數。EM在兩個步驟中交替計算，第一步是計算期望，利用對隱藏變數的現有估計值，計算其較大可能估計值;第二步是較大化，較大化在第一步上求得的較大可能值來計算參數的值。
13、快速傅里葉變換(Fast Fourier transform，FFT)——計算離散的傅里葉變換(DFT)及其反轉。該演算法應用范圍很廣，從數字信號處理到解決偏微分方程，到快速計算大整數乘積。
14、梯度下降(Gradient descent)——一種數學上的最優化演算法。
15、哈希演算法(Hashing)。
16、堆排序(Heaps)。
17、Karatsuba乘法——需要完成上千位整數的乘法的系統中使用，比如計算機代數系統和大數程序庫，如果使用長乘法，速度太慢。該演算法發現於1962年。
18、LLL演算法(Lenstra-Lenstra-Lovasz lattice rection)——以格規約(lattice)基數為輸入，輸出短正交向量基數。LLL演算法在以下公共密鑰加密方法中有大量使用：背包加密系統(knapsack)、有特定設置的RSA加密等等。
19、較大流量演算法(Maximum flow)——該演算法試圖從一個流量網路中找到較大的流。它優勢被定義為找到這樣一個流的值。較大流問題可以看作更復雜的網路流問題的特定情況。較大流與網路中的界面有關，這就是較大流-最小截定理(Max-flow min-cut theorem)。Ford-Fulkerson 能找到一個流網路中的較大流。
20、合並排序(Merge Sort)。
21、牛頓法(Newton's method)——求非線性方程(組)零點的一種重要的迭代法。
22、Q-learning學習演算法——這是一種通過學習動作值函數(action-value function)完成的強化學習演算法，函數採取在給定狀態的給定動作，並計算出期望的效用價值，在此後遵循固定的策略。Q-leanring的優勢是，在不需要環境模型的情況下，可以對比可採納行動的期望效用。
23、兩次篩法(Quadratic Sieve)——現代整數因子分解演算法，在實踐中，是目前已知第二快的此類演算法(僅次於數域篩法Number Field Sieve)。對於110位以下的十位整數，它仍是最快的，而且都認為它比數域篩法更簡單。
24、RANSAC——是「RANdom SAmple Consensus」的縮寫。該演算法根據一系列觀察得到的數據，數據中包含異常值，估算一個數學模型的參數值。其基本假設是：數據包含非異化值，也就是能夠通過某些模型參數解釋的值，異化值就是那些不符合模型的數據點。
25、RSA——公鑰加密演算法。較早的適用於以簽名作為加密的演算法。RSA在電商行業中仍大規模使用，大家也相信它有足夠安全長度的公鑰。
26、Schönhage-Strassen演算法——在數學中，Schönhage-Strassen演算法是用來完成大整數的乘法的快速漸近演算法。其演算法復雜度為：O(N log(N) log(log(N)))，該演算法使用了傅里葉變換。
27、單純型演算法(Simplex Algorithm)——在數學的優化理論中，單純型演算法是常用的技術，用來找到線性規劃問題的數值解。線性規劃問題包括在一組實變數上的一系列線性不等式組，以及一個等待較大化(或最小化)的固定線性函數。
28、奇異值分解(Singular value decomposition，簡稱SVD)——在線性代數中，SVD是重要的實數或復數矩陣的分解方法，在信號處理和統計中有多種應用，比如計算矩陣的偽逆矩陣(以求解最小二乘法問題)、解決超定線性系統(overdetermined linear systems)、矩陣逼近、數值天氣預報等等。
29、求解線性方程組(Solving a system of linear equations)——線性方程組是數學中最古老的問題，它們有很多應用，比如在數字信號處理、線性規劃中的估算和預測、數值分析中的非線性問題逼近等等。求解線性方程組，可以使用高斯—約當消去法(Gauss-Jordan elimination)，或是柯列斯基分解( Cholesky decomposition)。
30、Strukturtensor演算法——應用於模式識別領域，為所有像素找出一種計算方法，看看該像素是否處於同質區域( homogenous region)，看看它是否屬於邊緣，還是是一個頂點。
31、合並查找演算法(Union-find)——給定一組元素，該演算法常常用來把這些元素分為多個分離的、彼此不重合的組。不相交集(disjoint-set)的數據結構可以跟蹤這樣的切分方法。合並查找演算法可以在此種數據結構上完成兩個有用的操作：
查找：判斷某特定元素屬於哪個組。
合並：聯合或合並兩個組為一個組。
32、維特比演算法(Viterbi algorithm)——尋找隱藏狀態最有可能序列的動態規劃演算法，這種序列被稱為維特比路徑，其結果是一系列可以觀察到的事件，特別是在隱藏的Markov模型中。
G. 大數據經典演算法解析（8）一KNN演算法
姓名：崔升 學號：14020120005
【嵌牛導讀】：
本文討論的kNN演算法是監督學習中分類方法的一種。所謂監督學習與非監督學習，是指訓練數據是 否有標注類別，若有則為監督學習，若否則為非監督學習。監督學習是根據輸入數據（訓練數據） 學習一個模型，能對後來的輸入做預測。在監督學習中，輸入變數與輸出變數可以是連續的，也可 以是離散的。若輸入變數與輸出變數均為連續變數，則稱為 回歸 ；輸出變數為有限個離散變數，則 稱為 分類 ；輸入變數與輸出變數均為變數序列，則稱為 標注 [2]。
【嵌牛鼻子】：經典大數據演算法之kNN演算法的簡單介紹
【嵌牛提問】：kNN是一種怎麼的演算法，其數學原理又是如何？
【嵌牛正文】：
1. 引言
頂級數據挖掘會議ICDM於2006年12月評選出了數據挖掘領域的 十大經典演算法 ：C4.5, k-Means, SVM, Apriori, EM, PageRank, AdaBoost, kNN, Naïve Bayes與 CART。 以前看過關於這些數據挖掘演算法，但對背後數學原理未做過多探究，因而藉此整理以更深入地理解這些演算法。
2. kNN演算法
kNN演算法的核心思想非常簡單：在訓練集中選取離輸入的數據點最近的k個鄰居，根據這個k個鄰居中出現次數最多的類別（最大表決規則），作為該數據點的類別。
演算法描述
訓練集T={(x1,y1),(x2,y2),⋯,(xN,yN)}T={(x1,y1),(x2,y2),⋯,(xN,yN)}，其類別yi∈{c1,c2,⋯,cK}yi∈{c1,c2,⋯,cK}，訓練集中樣本點數為NN，類別數為KK。輸入待預測數據xx，則預測類別
y=argmaxcj∑xi∈Nk(x)I(yi=cj),i=1,2,⋯,N;j=1,2,⋯,K(1)(1)y=argmaxcj∑xi∈Nk(x)I(yi=cj),i=1,2,⋯,N;j=1,2,⋯,K
其中，涵蓋xx的k鄰域記作Nk(x)Nk(x)，當yi=cjyi=cj時指示函數I=1I=1，否則I=0I=0。
分類決策規則
kNN學習模型：輸入XX，通過學習得到決策函數：輸出類別Y=f(X)Y=f(X)。假設分類損失函數為0-1損失函數，即分類正確時損失函數值為0，分類錯誤時則為1。假如給xx預測類別為cjcj，即f(X)=cjf(X)=cj；同時由式子 (1) (1)可知k鄰域的樣本點對學習模型的貢獻度是均等的，則kNN學習模型誤分類率為
1k∑xi∈Nk(x)I(yi≠f(xi))=1k∑xi∈Nk(x)I(yi≠cj)=1−1k∑xi∈Nk(x)I(yi=cj)(2)(2)1k∑xi∈Nk(x)I(yi≠f(xi))=1k∑xi∈Nk(x)I(yi≠cj)=1−1k∑xi∈Nk(x)I(yi=cj)
若要最小化誤分類率，則應
maxcj∑xi∈Nk(x)I(yi=cj)maxcj∑xi∈Nk(x)I(yi=cj)
所以，最大表決規則等價於經驗風險最小化。
存在問題
k值得選取對kNN學習模型有著很大的影響。若k值過小，預測結果會對噪音樣本點顯得異常敏感。特別地，當k等於1時，kNN退化成最近鄰演算法，沒有了顯式的學習過程。若k值過大，會有較大的鄰域訓練樣本進行預測，可以減小噪音樣本點的減少；但是距離較遠的訓練樣本點對預測結果會有貢獻，以至於造成預測結果錯誤。下圖給出k值的選取對於預測結果的影響：
前面提到過，k鄰域的樣本點對預測結果的貢獻度是相等的；但距離更近的樣本點應有更大的相似度，其貢獻度應比距離更遠的樣本點大。可以加上權值wi=1/∥xi−x∥wi=1/‖xi−x‖進行修正，則最大表決原則變成：
maxcj∑xi∈Nk(x)wi∗I(yi=cj)maxcj∑xi∈Nk(x)wi∗I(yi=cj)
3. 參考資料
[1] Michael Steinbach and Pang-Ning Tan, The Top Ten Algorithms in Data Mining.
[2] 李航，《統計學習方法》.