大數據演算法ppt

Ⅰ 大數據最常用的演算法有哪些

奧地利符號計算研究所(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博士對於最重要的演算法的調查結果。你們熟悉哪些演算法?又有哪些演算法是你們經常使用的?

Ⅱ 大數據常用的各種演算法

我們經常談到的所謂的​​ 數據挖掘 是通過大量的數據集進行排序，自動化識別趨勢和模式並且建立相關性的過程。那現在市面的數據公司都是通過各種各樣的途徑來收集海量的信息，這些信息來自於網站、公司應用、社交媒體、移動設備和不斷增長的物聯網。

比如我們現在每天都在使用的搜索引擎。在自然語言處理領域，有一種非常流行的演算法模型，叫做詞袋模型，即把一段文字看成一袋水果，這個模型就是要算出這袋水果里，有幾個蘋果、幾個香蕉和幾個梨。搜索引擎會把這些數字記下來，如果你想要蘋果，它就會把有蘋果的這些袋子給你。

當我們在網上買東西或是看電影時，網站會推薦一些可能符合我們偏好的商品或是電影，這個推薦有時候還挺准。事實上，這背後的演算法，是在數你喜歡的電影和其他人喜歡的電影有多少個是一樣的，如果你們同時喜歡的電影超過一定個數，就把其他人喜歡、但你還沒看過的電影推薦給你。 搜索引擎和推薦系統 在實際生產環境中還要做很多額外的工作，但是從本質上來說，它們都是在數數。

當數據量比較小的時候，可以通過人工查閱數據。而到了大數據時代，幾百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模型中。

Ⅲ 大數據挖掘的演算法有哪些

大數據挖掘的演算法：
1.樸素貝葉斯，超級簡單，就像做一些數數的工作。如果條件獨立假設成立的話，NB將比鑒別模型收斂的更快，所以你只需要少量的訓練數據。即使條件獨立假設不成立，NB在實際中仍然表現出驚人的好。
2. Logistic回歸，LR有很多方法來對模型正則化。比起NB的條件獨立性假設，LR不需要考慮樣本是否是相關的。與決策樹與支持向量機不同，NB有很好的概率解釋，且很容易利用新的訓練數據來更新模型。如果你想要一些概率信息或者希望將來有更多數據時能方便的更新改進模型，LR是值得使用的。
3.決策樹，DT容易理解與解釋。DT是非參數的，所以你不需要擔心野點（或離群點）和數據是否線性可分的問題，DT的主要缺點是容易過擬合，這也正是隨機森林等集成學習演算法被提出來的原因。
4.支持向量機，很高的分類正確率，對過擬合有很好的理論保證，選取合適的核函數，面對特徵線性不可分的問題也可以表現得很好。SVM在維數通常很高的文本分類中非常的流行。

如果想要或許更多更詳細的訊息，建議您去參加CDA數據分析課程。大數據分析師現在有專業的國際認證證書了，CDA，即「CDA 數據分析師」，是在數字經濟大背景和人工智慧時代趨勢下，面向全行業的專業權威國際資格認證， 旨在提升全民數字技能，助力企業數字化轉型，推動行業數字化發展。 「CDA 數據分析師」具體指在互聯網、金融、零售、咨詢、電信、醫療、旅遊等行業專門從事數據的採集、清洗、處理、分析並能製作業務報告、 提供決策的新型數據分析人才。點擊預約免費試聽課。

Ⅳ 大數據經典演算法解析（1）一C4.5演算法

姓名：崔升    學號：14020120005

【嵌牛導讀】：

C4.5作為一種經典的處理大數據的演算法，是我們在學習互聯網大數據時不得不去了解的一種常用演算法

【嵌牛鼻子】：經典大數據演算法之C4.5簡單介紹

【嵌牛提問】：C4.5是一種怎麼的演算法，其決策機制靠什麼實現？

【嵌牛正文】：

決策樹模型：

決策樹是一種通過對特徵屬性的分類對樣本進行分類的樹形結構，包括有向邊與三類節點：

根節點（root node），表示第一個特徵屬性，只有出邊沒有入邊；

內部節點（internal node），表示特徵屬性，有一條入邊至少兩條出邊

葉子節點（leaf node），表示類別，只有一條入邊沒有出邊。

上圖給出了（二叉）決策樹的示例。決策樹具有以下特點：

對於二叉決策樹而言，可以看作是if-then規則集合，由決策樹的根節點到葉子節點對應於一條分類規則;

分類規則是 互斥並且完備 的，所謂 互斥 即每一條樣本記錄不會同時匹配上兩條分類規則，所謂 完備 即每條樣本記錄都在決策樹中都能匹配上一條規則。

分類的本質是對特徵空間的劃分，如下圖所示，

決策樹學習：

決策樹學習的本質是從訓練數據集中歸納出一組分類規則[2]。但隨著分裂屬性次序的不同，所得到的決策樹也會不同。如何得到一棵決策樹既對訓練數據有較好的擬合，又對未知數據有很好的預測呢？

首先，我們要解決兩個問題：

如何選擇較優的特徵屬性進行分裂？每一次特徵屬性的分裂，相當於對訓練數據集進行再劃分，對應於一次決策樹的生長。ID3演算法定義了目標函數來進行特徵選擇。

什麼時候應該停止分裂？有兩種自然情況應該停止分裂，一是該節點對應的所有樣本記錄均屬於同一類別，二是該節點對應的所有樣本的特徵屬性值均相等。但除此之外，是不是還應該其他情況停止分裂呢？

2. 決策樹演算法

特徵選擇

特徵選擇指選擇最大化所定義目標函數的特徵。下面給出如下三種特徵（Gender, Car Type, Customer ID）分裂的例子：

圖中有兩類類別（C0, C1），C0: 6是對C0類別的計數。直觀上，應選擇Car Type特徵進行分裂，因為其類別的分布概率具有更大的傾斜程度，類別不確定程度更小。

為了衡量類別分布概率的傾斜程度，定義決策樹節點tt的不純度（impurity），其滿足：不純度越小，則類別的分布概率越傾斜；下面給出不純度的的三種度量：

其中，p(ck|t)p(ck|t)表示對於決策樹節點tt類別ckck的概率。這三種不純度的度量是等價的，在等概率分布是達到最大值。

為了判斷分裂前後節點不純度的變化情況，目標函數定義為信息增益（information gain）：

I(⋅)I(⋅)對應於決策樹節點的不純度，parentparent表示分裂前的父節點，NN表示父節點所包含的樣本記錄數，aiai表示父節點分裂後的某子節點，N(ai)N(ai)為其計數，nn為分裂後的子節點數。

特別地，ID3演算法選取 熵值 作為不純度I(⋅)I(⋅)的度量，則

cc指父節點對應所有樣本記錄的類別；AA表示選擇的特徵屬性，即aiai的集合。那麼，決策樹學習中的信息增益ΔΔ等價於訓練數據集中 類與特徵的互信息 ，表示由於得知特徵AA的信息訓練數據集cc不確定性減少的程度。

在特徵分裂後，有些子節點的記錄數可能偏少，以至於影響分類結果。為了解決這個問題，CART演算法提出了只進行特徵的二元分裂，即決策樹是一棵二叉樹；C4.5演算法改進分裂目標函數，用信息增益比（information gain ratio）來選擇特徵：

因而，特徵選擇的過程等同於計算每個特徵的信息增益，選擇最大信息增益的特徵進行分裂。此即回答前面所提出的第一個問題（選擇較優特徵）。ID3演算法設定一閾值，當最大信息增益小於閾值時，認為沒有找到有較優分類能力的特徵，沒有往下繼續分裂的必要。根據最大表決原則，將最多計數的類別作為此葉子節點。即回答前面所提出的第二個問題（停止分裂條件）。

決策樹生成：

ID3演算法的核心是根據信息增益最大的准則，遞歸地構造決策樹；演算法流程如下：

如果節點滿足停止分裂條件（所有記錄屬同一類別 or 最大信息增益小於閾值），將其置為葉子節點；

選擇信息增益最大的特徵進行分裂；

重復步驟1-2，直至分類完成。

C4.5演算法流程與ID3相類似，只不過將信息增益改為 信息增益比 。

3. 決策樹剪枝

過擬合

生成的決策樹對訓練數據會有很好的分類效果，卻可能對未知數據的預測不準確，即決策樹模型發生過擬合（overfitting）——訓練誤差（training error）很小、泛化誤差（generalization error，亦可看作為test error）較大。下圖給出訓練誤差、測試誤差（test error）隨決策樹節點數的變化情況：

可以觀察到，當節點數較小時，訓練誤差與測試誤差均較大，即發生了欠擬合（underfitting）。當節點數較大時，訓練誤差較小，測試誤差卻很大，即發生了過擬合。只有當節點數適中是，訓練誤差居中，測試誤差較小；對訓練數據有較好的擬合，同時對未知數據有很好的分類准確率。

發生過擬合的根本原因是分類模型過於復雜，可能的原因如下：

訓練數據集中有噪音樣本點，對訓練數據擬合的同時也對噪音進行擬合，從而影響了分類的效果；

決策樹的葉子節點中缺乏有分類價值的樣本記錄，也就是說此葉子節點應被剪掉。

剪枝策略

為了解決過擬合，C4.5通過剪枝以減少模型的復雜度。[2]中提出一種簡單剪枝策略，通過極小化決策樹的整體損失函數（loss function）或代價函數（cost function）來實現，決策樹TT的損失函數為：

其中，C(T)C(T)表示決策樹的訓練誤差，αα為調節參數，|T||T|為模型的復雜度。當模型越復雜時，訓練的誤差就越小。上述定義的損失正好做了兩者之間的權衡。

如果剪枝後損失函數減少了，即說明這是有效剪枝。具體剪枝演算法可以由動態規劃等來實現。

4. 參考資料

[1] Pang-Ning Tan, Michael Steinbach, Vipin Kumar, Introction to Data Mining .

[2] 李航，《統計學習方法》.

[3] Naren Ramakrishnan, The Top Ten Algorithms in Data Mining.

Ⅳ 大數據的新演算法:簡化數據分類

大數據的新演算法:簡化數據分類

如今，大數據時代悄然來臨。專家用「大數據」的表達描述大量信息，比如數十億人在計算機、智能手機以及其他電子設備上分享的照片、音頻、文本等數據。當前這種模式為我們的未來展現了前所未有的願景：比如追蹤流感疫情蔓延，實時監控道路交通，處理緊急自然災害等。對人們而言，想要利用這些龐大的數據，首先必須要了解它們，而在此之前我們需要一種快捷有效自動的方式對數據進行分類。

其中一種最為常用的系統，是一系列稱之為簇分析的統計技術，這種技術能依據數據的「相似性」進行數據分組。來自義大利國際高等研究院(SISSA)的兩位研究者基於簡單且強大的原理設計了一種簇分析方法，被證明可以非常有效地解決一些大數據分析中遇到的主要典型問題。

數據集合可以視為多維空間的雲數據點。這些點呈現不同分配方式：或稀疏地分布在一個區域，或密集地分布在另外一個區域。簇分析就是用來有效地鑒別密集型區域，基於基本的准則將數據分為一定數量的重要子集合，每個子集合對應一種分類。

「以一個面部圖像資料庫為例，」SISSA統計與生物物理系教授Alessandro Laio說，「資料庫可能包含同一個人的多張照片，簇分析可以用來歸類同一人的所有照片。這種類型的分析可用自動臉部識別系統來完成。」

「我們試著設計一種較現有方法更為有效的演算法，來解決簇分析中典型的問題。」Laio繼續補充說。

「我們的方法基於一種新的鑒定簇中心，比如子集合，」另一位研究者Alex Rodriguez解釋道，「試想這樣的情形，在無法訪問地圖中，卻不得不鑒定全球所有的城市時，這無疑是一個艱巨的任務。」Rodriguez進一步解釋道，「因此我們在做一種探索式的識別，嘗試尋找一條簡單的規則或是一種捷徑來達成目標。」

「為了確定一個地方是否達到城市級別規模，我們可以讓當地居民計數自己的『鄰居』，換句話說，他房子的100米內住了多少人。一旦得到這個數字，我們繼續去確認每一個居民，他們身邊最近的擁有最多鄰居數的居民。藉助這兩組數據結果交叉的部分，就可以推斷每個人所在居住區域人口的稠密程度，以及擁有鄰居數最多的兩家間距。就全球人口而言，通過自動交叉檢測這些數據，我們能識別代表簇狀中心的個體，這些個體就是不同的城市。」 Laio解釋道。

「我們的演算法能夠精確地完成此類計算，也適用於其他場景，」Rodriguez進一步補充說，此演算法表現相當優異。Rodriguez對此有著深刻理解：「借用面部數據檔案Olivetti Face資料庫，我們測試了自己的數學模型，並獲得了滿意的結果。此系統能夠正確地識別大部分個體，從不產生假陽性結果，這意味著在某些情況下，它可能無法識別事物，但絕不會混淆一個個體與另一個個體。與類似的方法相比，我們的演算法能夠有效地剔除異類，要知道這些異類的數據點與其他數據存在較大差異是會損毀分析結果的。」

以上是小編為大家分享的關於大數據的新演算法:簡化數據分類的相關內容，更多信息可以關注環球青藤分享更多干貨

Ⅵ 大數據分析之聚類演算法

大數據分析之聚類演算法
1. 什麼是聚類演算法
所謂聚類，就是比如給定一些元素或者對象，分散存儲在資料庫中，然後根據我們感興趣的對象屬性，對其進行聚集，同類的對象之間相似度高，不同類之間差異較大。最大特點就是事先不確定類別。
這其中最經典的演算法就是KMeans演算法，這是最常用的聚類演算法，主要思想是:在給定K值和K個初始類簇中心點的情況下，把每個點(亦即數據記錄)分到離其最近的類簇中心點所代表的類簇中，所有點分配完畢之後，根據一個類簇內的所有點重新計算該類簇的中心點(取平均值)，然後再迭代的進行分配點和更新類簇中心點的步驟，直至類簇中心點的變化很小，或者達到指定的迭代次數。
KMeans演算法本身思想比較簡單，但是合理的確定K值和K個初始類簇中心點對於聚類效果的好壞有很大的影響。
聚類演算法實現
假設對象集合為D，准備劃分為k個簇。
基本演算法步驟如下：
1、從D中隨機取k個元素，作為k個簇的各自的中心。
2、分別計算剩下的元素到k個簇中心的相異度，將這些元素分別劃歸到相異度最低的簇。
3、根據聚類結果，重新計算k個簇各自的中心，計算方法是取簇中所有元素各自維度的算術平均數。
4、將D中全部元素按照新的中心重新聚類。
5、重復第4步，直到聚類結果不再變化。
6、將結果輸出。

核心Java代碼如下：
/**
* 迭代計算每個點到各個中心點的距離，選擇最小距離將該點劃入到合適的分組聚類中，反復進行，直到
* 分組不再變化或者各個中心點不再變化為止。
* @return
*/
public List[] comput() {
List[] results = new ArrayList[k];//為k個分組，分別定義一個聚簇集合，未來放入元素。

boolean centerchange = true;//該變數存儲中心點是否發生變化
while (centerchange) {
iterCount++;//存儲迭代次數
centerchange = false;
for (int i = 0; i < k; i++) {
results[i] = new ArrayList<T>();
}
for (int i = 0; i < players.size(); i++) {
T p = players.get(i);
double[] dists = new double[k];
for (int j = 0; j < initPlayers.size(); j++) {
T initP = initPlayers.get(j);
/* 計算距離 這里採用的公式是兩個對象相關屬性的平方和，最後求開方*/
double dist = distance(initP, p);
dists[j] = dist;
}

int dist_index = computOrder(dists);//計算該點到各個質心的距離的最小值，獲得下標
results[dist_index].add(p);//劃分到對應的分組。
}
/*
* 將點聚類之後，重新尋找每個簇的新的中心點，根據每個點的關注屬性的平均值確立新的質心。
*/
for (int i = 0; i < k; i++) {
T player_new = findNewCenter(results[i]);
System.out.println("第"+iterCount+"次迭代，中心點是："+player_new.toString());
T player_old = initPlayers.get(i);
if (!IsPlayerEqual(player_new, player_old)) {
centerchange = true;
initPlayers.set(i, player_new);
}

}

}

return results;
}
上面代碼是其中核心代碼，我們根據對象集合List和提前設定的k個聚集,最終完成聚類。我們測試一下，假設要測試根據NBA球員的場均得分情況，進行得分高中低的聚集，很簡單，高得分在一組，中等一組，低得分一組。
我們定義一個Player類，裡面有屬性goal，並錄入數據。並設定分組數目為k=3。
測試代碼如下:
List listPlayers = new ArrayList();
Player p1 = new Player();
p1.setName(「mrchi1」);
p1.setGoal(1);
p1.setAssists(8);
listPlayers.add(p1);

Player p2 = new Player();
p2.setName("mrchi2");
p2.setGoal(2);
listPlayers.add(p2);

Player p3 = new Player();
p3.setName("mrchi3");
p3.setGoal(3);
listPlayers.add(p3);
//其他對象定義此處略。製造幾個球員的對象即可。
Kmeans<Player> kmeans = new Kmeans<Player>(listPlayers, 3);
List<Player>[] results = kmeans.comput();
for (int i = 0; i < results.length; i++) {
System.out.println("類別" + (i + 1) + "聚集了以下球員：");
List<Player> list = results[i];
for (Player p : list) {
System.out.println(p.getName() + "--->" + p.getGoal()

}
}
演算法運行結果：

可以看出中心點經歷了四次迭代變化，最終分類結果也確實是相近得分的分到了一組。當然這種演算法有缺點，首先就是初始的k個中心點的確定非常重要，結果也有差異。可以選擇彼此距離盡可能遠的K個點，也可以先對數據用層次聚類演算法進行聚類，得到K個簇之後，從每個類簇中選擇一個點，該點可以是該類簇的中心點，或者是距離類簇中心點最近的那個點。

Ⅶ 大數據核心演算法有哪些

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)。

Ⅷ 大數據培訓內容，大數據要學哪些課程

《大數據實訓課程資料》網路網盤資源免費下載

鏈接:https://pan..com/s/1RiGvjn2DlL5pPISCG_O0Sw

大數據實訓課程資料|雲計算與虛擬化課程資源|課程實驗指導書綜合版|機器學習與演算法分析課程資源|Spark課程資源|Python課程資源|Hadoop技術課程資源|雲計算課程資料.zip|微課.zip|演算法建模與程序示例.zip|spark課程資源.zip|hadoop課程資源.zip|實驗指導書|教學視頻|教學PPT

Ⅸ 大數據分析的常用方法

1. Analytic Visualizations（可視化分析）

不管是對數據分析專家還是普通用戶，數據可視化是數據分析工具最基本的要求。可視化可以直觀的展示數據，讓數據自己說話，讓觀眾聽到結果。

2. Data Mining Algorithms（數據挖掘演算法）
可視化是給人看的，數據挖掘就是給機器看的。集群、分割、孤立點分析還有其他的演算法讓我們深入數據內部，挖掘價值。這些演算法不僅要處理大數據的量，也要處理大數據的速度。

3. Predictive Analytic Capabilities（預測性分析能力）
數據挖掘可以讓分析員更好的理解數據，而預測性分析可以讓分析員根據可視化分析和數據挖掘的結果做出一些預測性的判斷。

4. Semantic Engines（語義引擎）
由於非結構化數據的多樣性帶來了數據分析的新的挑戰，需要一系列的工具去解析，提取，分析數據。語義引擎需要被設計成能夠從「文檔」中智能提取信息。

5. Data Quality and Master Data Management（數據質量和數據管理）

數據質量和數據管理是一些管理方面的最佳實踐。通過標准化的流程和工具對數據進行處理可以保證一個預先定義好的高質量的分析結果。