大數據預測演算法
⑴ 大數據分析的高級分析演算法
眾所周知,大數據分析的高級分析演算法過程為下游流程提供了更精確,價值更高的數據,這對於公司真正利用其數據的價值並實現其所需的結果至關重要。下面是小編整理的一些高級分析計劃中使用的一些最受歡迎的演算法。每種方法都有優缺點,可以有效地利用它來產生業務價值的方式也不同。實施這些演算法的最終目標是進一步優化數據,使結果信息可以應用於業務決策。
⑵ 大數據挖掘常用的演算法有哪些
1、預測建模:將已有數據和模型用於對未知變數的語言。
分類,用於預測離散的目標變數。
回歸,用於預測連續的目標變數。
2、聚類分析:發現緊密相關的觀測值組群,使得與屬於不同簇的觀測值相比,屬於同一簇的觀測值相互之間盡可能類似。
3、關聯分析(又稱關系模式):反映一個事物與其他事物之間的相互依存性和關聯性。用來發現描述數據中強關聯特徵的模式。
4、異常檢測:識別其特徵顯著不同於其他數據的觀測值。
有時也把數據挖掘分為:分類,回歸,聚類,關聯分析。
⑶ 大數據經典演算法解析(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.