Iforest演算法

① RandomForest隨機森林演算法

https://blog.csdn.net/qq_16633405/article/details/61200502
http://blog.itpub.net/12199764/viewspace-1572056/
https://blog.csdn.net/colourful_sky/article/details/82082854

隨機森林中隨機是核心，通過隨機的選擇樣本、特徵，降低了決策樹之間的相關性。隨機森林中的隨機主要有兩層意思，一是隨機在原始訓練數據中有放回的選取等量的數據作為訓練樣本，二是在建立決策樹時，隨機的選特徵中選取一部分特徵建立決策樹。這兩種隨機使得各個決策樹之間的相關性小，進一步提高模型的准確性。
隨機森林未用到決策樹的剪枝，那怎樣控制模型的過擬合呢？主要通過控制 樹的深度(max_depth)，結點停止分裂的最小樣本數（min_size）等參數。隨機森林還可以處理缺失值。

假設訓練集中n個樣本，每個樣本有d個特徵，需要訓練一個包含T棵數的隨機森林，具體的演算法流程如下所示：
1、對於T棵決策樹，分別重復如下操作：a、使用Bootstrap抽樣，從訓練集D獲得大小為n的訓練集D； b、從d個特徵中隨機選取m（m
2、如果是回歸問題，則最後的輸出是 每個樹輸出的均值；
3、如果是分類問題，則根據投票原則，確定最終的類別。
每棵樹的生成都是隨機的，至於隨機選取的特徵數，如何決定隨機選取的特徵數的大小呢，主要有兩種方法，一種是交叉驗證，另外一種的經驗性設置 m= log_2 d +1。

1、分類間隔：分類間隔是指森林中正確分類樣本的決策樹的比例減去錯誤分類的決策樹的比例，通過平均每個樣本的分類間隔得到隨機森林的分類間隔。對於分類間隔，當然是越大越好，大的分類間隔說明模型的分類效果比較穩定，泛化效果好。
2、袋外誤差：對於每棵樹都有一部分樣本而沒有被抽取到，這樣的樣本就被稱為袋外樣本，隨機森林對袋外樣本的預測錯誤率被稱為袋外誤差（Out-Of-Bag Error,OOB）。計算方式如下所示：
（1）對於每個樣本，計算把該樣本作為袋外樣本的分類情況；
（2）以投票的方式確定該樣本的分類結果；
（3）將誤分類樣本個數占總數的比率作為隨機森林的袋外誤差。
3、變數重要程度刻畫：其實變數重要程度刻畫不能算是模型性能評估裡面，因為有的實際應用中需要查看這么多的特徵中到底那一部分特徵是相對重要的特徵，這個時候變數的重要程度的刻畫就顯得尤為重要了。其計算方式主要有一下兩種方式：
（1）通過計算特徵的平均信息增益大小得出；
（2）通過計算每個特徵對模型准確率的影響，通過打亂樣本中某一特徵的特徵值順序，產生新樣本，將新樣本放入建立好的隨機森林模型計算準確率。相對於不重要的特徵，即使打亂了順序也不會對結果產生很大的影響，對於重要的特徵，會對結果產生很大的影響的。

優點 ：
1、對於大部分的數據，它的分類效果比較好。
2、能處理高維特徵，不容易產生過擬合，模型訓練速度比較快，特別是對於大數據而言。
3、在決定類別時，它可以評估變數的重要性。
4、對數據集的適應能力強：既能處理離散型數據，也能處理連續型數據，數據集無需規范化。
缺點 ：
1、隨機森林容易產生過擬合，特別是在數據集相對小或者是低維數據集的時候。
2、 計算速度比單個的決策樹慢。
3、 當我們需要推斷超出范圍的獨立變數或非獨立變數，隨機森林做得並不好。

分類問題

回歸問題

常用方法 ：參考 https://blog.csdn.net/w952470866/article/details/78987265
predict_proba(x)：給出帶有概率值的結果。每個點在所有label（類別）的概率和為1。
predict(x)：預測X的結果。內部還是調用的predict_proba()，根據概率的結果看哪個類型的預測值最高就是哪個類型。
predict_log_proba(x)：和predict_proba基本上一樣，只是把結果給做了log()處理。
fit(X, y, sample_weight=None)： 從訓練數據集(X,y)上建立一個決策樹森林。x為訓練樣本，y為目標值（分類中的類標簽，回歸中的實數）。
參數
和GBDT對比，GBDT的框架參數比較多，重要的有最大迭代器個數，步長和子采樣比例，調參起來比較費力。但是RandomForest則比較簡單，這是因為bagging框架里的各個弱學習器之間是沒有依賴關系的，這減小的調參的難度。換句話說，達到同樣的調參效果，RandomForest調參時間要比GBDT少一些。
Bagging框架參數 ：
n_estimators：最大的弱學習器個數（建立隨機森林分類器（樹）的個數）。太小容易欠擬合，太大又容易過擬合，一般選擇一個適中的數值。增大可以降低整體模型的方差，提升模型的准確度，且不會對子模型的偏差和方差有任何影響。由於降低的是整體模型方差公式的第二項，故准確度的提高有一個上限。在實際應用中，可以在1至200之間取值；
n_jobs：引擎允許使用處理器的數量。 若值為1則只能使用一個處理器， 值為-1則表示沒有限制。設置n_jobs可以加快模型計算速度；
oob_score：是否採用袋外誤差來評估模型的好壞，默認為 False，推薦設置為True，因為袋外分數反應了一個模型擬合後的泛化能力；
CART決策樹參數 ：
max_features: RF劃分時考慮的最大特徵數。可以使用很多種類型的值，默認是"None",意味著劃分時考慮所有的特徵數；如果是"log2"意味著劃分時最多考慮log2N個特徵；如果是"sqrt"或者"auto"意味著劃分時最多考慮N−−√N個特徵。如果是整數，代表考慮的特徵絕對數。如果是浮點數，代表考慮特徵百分比，即考慮（百分比xN）取整後的特徵數，其中N為樣本總特徵數。一般來說，如果樣本特徵數不多，比如小於50，我們用默認的"None"就可以了，如果特徵數非常多，我們可以靈活使用剛才描述的其他取值來控制劃分時考慮的最大特徵數，以控制決策樹的生成時間。
max_depth: 決策樹最大深度。默認為"None"，決策樹在建立子樹的時候不會限制子樹的深度這樣建樹時，會使每一個葉節點只有一個類別，或是達到min_samples_split。一般來說，數據少或者特徵少的時候可以不管這個值。如果模型樣本量多，特徵也多的情況下，推薦限制這個最大深度，具體的取值取決於數據的分布。常用的可以取值10-100之間。
min_samples_split: 內部節點再劃分所需最小樣本數，默認2。這個值限制了子樹繼續劃分的條件，如果某節點的樣本數少於min_samples_split，則不會繼續再嘗試選擇最優特徵來進行劃分。 默認是2.如果樣本量不大，不需要管這個值。如果樣本量數量級非常大，則推薦增大這個值。
min_samples_leaf:葉子節點最少樣本數。 這個值限制了葉子節點最少的樣本數，如果某葉子節點數目小於樣本數，則會和兄弟節點一起被剪枝。 默認是1,可以輸入最少的樣本數的整數，或者最少樣本數占樣本總數的百分比。如果樣本量不大，不需要管這個值。如果樣本量數量級非常大，則推薦增大這個值。
min_weight_fraction_leaf：葉子節點最小的樣本權重和。這個值限制了葉子節點所有樣本權重和的最小值，如果小於這個值，則會和兄弟節點一起被剪枝。 默認是0，就是不考慮權重問題。一般來說，如果我們有較多樣本有缺失值，或者分類樹樣本的分布類別偏差很大，就會引入樣本權重，這時我們就要注意這個值了。
max_leaf_nodes: 最大葉子節點數。通過限制最大葉子節點數，可以防止過擬合，默認是"None」，即不限制最大的葉子節點數。如果加了限制，演算法會建立在最大葉子節點數內最優的決策樹。如果特徵不多，可以不考慮這個值，但是如果特徵分成多的話，可以加以限制，具體的值可以通過交叉驗證得到。
min_impurity_split: 節點劃分最小不純度。這個值限制了決策樹的增長，如果某節點的不純度(基於基尼系數，均方差)小於這個閾值，則該節點不再生成子節點，即為葉子節點 。一般不推薦改動默認值1e-7。
上面的決策樹參數中最重要的包括最大特徵數 max_features ， 最大深度 max_depth ， 內部節點再劃分所需最小樣本數 min_samples_split 和葉子節點最少樣本數 min_samples_leaf 。
參數調優 ：隨機森林參數的調優在數據分析和挖掘中也佔有一定的地位，學會好的調優方法能夠達到事半功倍的效果。調優參考 https://blog.csdn.net/cherdw/article/details/54971771

② 數據挖掘RAINFOREST演算法

上面演算法講的很清楚了，我來舉個例子：

Training data：
Id age income class
1 young 65 G
2 young 15 B
3 young 75 G
4 senior 40 B
5 senior 100 G
6 senior 60 G

AVC set „age「 for N1：
value class count
young B 1
young G 2
senior B 1
senior G 2

AVC set „income「 for N1：
value class count
15 B 1
40 B 1
60 G 1
65 G 1
75 G 1
100 G 1

AVC set „income「 for N2：
value class count
15 B 1
65 G 1
75 G 1

AVC set „age「 for N2:
value class count
young B 1
young G 2

最後推出雨林： N1
age=young / \ age=senior
/ \
N2 N3

最後提醒一點，對於雨林演算法，訓練樣本集不要大於3百萬。否則改用SPRINT。

③ 大數據科學家需要掌握的幾種異常值檢測方法

引言

異常值檢測與告警一直是工業界非常關注的問題，自動准確地檢測出系統的異常值，不僅可以節約大量的人力物力，還能盡早發現系統的異常情況，挽回不必要的損失。個推也非常重視大數據中的異常值檢測，例如在運維部門的流量管理業務中，個推很早便展開了對異常值檢測的實踐，也因此積累了較為豐富的經驗。本文將從以下幾個方面介紹異常值檢測。

1、異常值檢測研究背景

2、異常值檢測方法原理

3、異常值檢測應用實踐

異常值檢測研究背景

異常值，故名思議就是不同於正常值的值。 在數學上，可以用離群點來表述，這樣便可以將異常值檢測問題轉化為數學問題來求解。

異常值檢測在很多場景都有廣泛的應用，比如：

1、流量監測

互聯網上某些伺服器的訪問量，可能具有周期性或趨勢性：一般情況下都是相對平穩的，但是當受到某些黑客攻擊後，其訪問量可能發生顯著的變化，及早發現這些異常變化對企業而言有著很好的預防告警作用。

2、金融風控

正常賬戶中，用戶的轉賬行為一般屬於低頻事件，但在某些金融詐騙案中，一些嫌犯的賬戶就可能會出現高頻的轉賬行為，異常檢測系統如果能發現這些異常行為，及時採取相關措施，則會規避不少損失。

3、機器故障檢測

一個運行中的流水線，可能會裝有不同的感測器用來監測運行中的機器，這些感測器數據就反應了機器運行的狀態，這些實時的監測數據具有數據量大、維度廣的特點，用人工盯著看的話成本會非常高，高效的自動異常檢測演算法將能很好地解決這一問題。

異常值檢測方法原理

本文主要將異常值檢測方法分為兩大類：一類是基於統計的異常值檢測，另一類是基於模型的異常值檢測。

基於統計的方法  

基於模型的方法

1、基於統計的異常值檢測方法

常見的基於統計的異常值檢測方法有以下2種，一種是基於3σ法則，一種是基於箱體圖。

3σ法則  

箱體圖

3σ法則是指在樣本服從正態分布時，一般可認為小於μ-3σ或者大於μ+3σ的樣本值為異常樣本，其中μ為樣本均值，σ為樣本標准差。在實際使用中，我們雖然不知道樣本的真實分布，但只要真實分布與正太分布相差不是太大，該經驗法則在大部分情況下便是適用的。

箱體圖也是一種比較常見的異常值檢測方法，一般取所有樣本的25%分位點Q1和75%分位點Q3，兩者之間的距離為箱體的長度IQR，可認為小於Q1-1.5IQR或者大於Q3+1.5IQR的樣本值為異常樣本。

基於統計的異常檢測往往具有計算簡單、有堅實的統計學基礎等特點，但缺點也非常明顯，例如需要大量的樣本數據進行統計，難以對高維樣本數據進行異常值檢測等。

2、基於模型的異常值檢測

通常可將異常值檢測看作是一個二分類問題，即將所有樣本分為正常樣本和異常樣本，但這和常規的二分類問題又有所區別，常規的二分類一般要求正負樣本是均衡的，如果正負樣本不均勻的話，訓練結果往往會不太好。但在異常值檢測問題中，往往面臨著正（正常值）負（異常值）樣本不均勻的問題，異常值通常比正常值要少得多，因此需要對常規的二分類模型做一些改進。

基於模型的異常值檢測一般可分為有監督模型異常值檢測和無監督模型異常值檢測，比較典型的有監督模型如oneclassSVM、基於神經網路的自編碼器等。 oneclassSVM就是在經典的SVM基礎上改進而來，它用一個超球面替代了超平面，超球面以內的值為正常值，超球面以外的值為異常值。

經典的SVM  

1

 基於模型的方法

2

基於神經網路的自編碼器結構如下圖所示。

自編碼器（AE）

將正常樣本用於模型訓練，輸入與輸出之間的損失函數可採用常見的均方誤差，因此檢測過程中，當正常樣本輸入時，均方誤差會較小，當異常樣本輸入時，均方誤差會較大，設置合適的閾值便可將異常樣本檢測出來。但該方法也有缺點，就是對於訓練樣本比較相近的正常樣本判別較好，但若正常樣本與訓練樣本相差較大，則可能會導致模型誤判。

無監督模型的異常值檢測是異常值檢測中的主流方法，因為異常值的標注成本往往較高，另外異常值的產生往往無法預料，因此有些異常值可能在過去的樣本中根本沒有出現過， 這將導致某些異常樣本無法標注，這也是有監督模型的局限性所在。 較為常見的無監督異常值檢測模型有密度聚類（DBSCAN）、IsolationForest（IF）、RadomCutForest（RCF）等，其中DBSCAN是一種典型的無監督聚類方法，對某些類型的異常值檢測也能起到不錯的效果。該演算法原理網上資料較多，本文不作詳細介紹。

IF演算法最早由南京大學人工智慧學院院長周志華的團隊提出，是一種非常高效的異常值檢測方法，該方法不需要對樣本數據做任何先驗的假設，只需基於這樣一個事實——異常值只是少數，並且它們具有與正常值非常不同的屬性值。與隨機森林由大量決策樹組成一樣，IsolationForest也由大量的樹組成。IsolationForest中的樹叫isolation tree，簡稱iTree。iTree樹和決策樹不太一樣，其構建過程也比決策樹簡單，因為其中就是一個完全隨機的過程。

假設數據集有N條數據，構建一顆iTree時，從N條數據中均勻抽樣(一般是無放回抽樣)出n個樣本出來，作為這顆樹的訓練樣本。

在樣本中，隨機選一個特徵，並在這個特徵的所有值范圍內（最小值與最大值之間）隨機選一個值，對樣本進行二叉劃分，將樣本中小於該值的劃分到節點的左邊，大於等於該值的劃分到節點的右邊。

這樣得到了一個分裂條件和左、右兩邊的數據集，然後分別在左右兩邊的數據集上重復上面的過程，直至達到終止條件。 終止條件有兩個，一個是數據本身不可再分(只包括一個樣本，或者全部樣本相同)，另外一個是樹的高度達到log2(n)。 不同於決策樹，iTree在演算法裡面已經限制了樹的高度。不限制雖然也可行，但出於效率考慮，演算法一般要求高度達到log2(n)深度即可。

把所有的iTree樹構建好了，就可以對測試數據進行預測了。預測的過程就是把測試數據在iTree樹上沿對應的條件分支往下走，直到達到葉子節點，並記錄這過程中經過的路徑長度h(x)，即從根節點，穿過中間的節點，最後到達葉子節點，所走過的邊的數量(path length)。最後，將h(x)帶入公式，其中E(.)表示計算期望，c(n)表示當樣本數量為n時，路徑長度的平均值，從而便可計算出每條待測數據的異常分數s(Anomaly Score)。異常分數s具有如下性質：

1）如果分數s越接近1，則該樣本是異常值的可能性越高；

2）如果分數s越接近0，則該樣本是正常值的可能性越高；

RCF演算法與IF演算法思想上是比較類似的，前者可以看成是在IF演算法上做了一些改進。針對IF演算法中沒有考慮到的時間序列因素，RCF演算法考慮了該因素，並且在數據樣本采樣策略上作出了一些改進，使得異常值檢測相對IF演算法變得更加准確和高效，並能更好地應用於流式數據檢測。

IF演算法

RCF演算法

上圖展示了IF演算法和RCF演算法對於異常值檢測的異同。我們可以看出原始數據中有兩個突變異常數據值，對於後一個較大的突變異常值，IF演算法和RCF演算法都檢測了出來，但對於前一個較小的突變異常值，IF演算法沒有檢測出來，而RCF演算法依然檢測了出來，這意味著RCF有更好的異常值檢測性能。

異常值檢測應用實踐

理論還需結合實踐，下面我們將以某應用從2016.08.16至2019.09.21的日活變化情況為例，對異常值檢測的實際應用場景予以介紹：

從上圖中可以看出該應用的日活存在著一些顯著的異常值（比如紅色圓圈部分），這些異常值可能由於活動促銷或者更新迭代出現bug導致日活出現了比較明顯的波動。下面分別用基於統計的方法和基於模型的方法對該日活序列數據進行異常值檢測。

基於3σ法則（基於統計）

RCF演算法（基於模型）

從圖中可以看出，對於較大的突變異常值，3σ法則和RCF演算法都能較好地檢測出來， 但對於較小的突變異常值，RCF演算法則要表現得更好。

總結

上文為大家講解了異常值檢測的方法原理以及應用實踐。綜合來看，異常值檢測演算法多種多樣 ，每一種都有自己的優缺點和適用范圍，很難直接判斷哪一種異常檢測演算法是最佳的， 具體在實戰中，我們需要根據自身業務的特點，比如對計算量的要求、對異常值的容忍度等，選擇合適的異常值檢測演算法。

接下來，個推也會結合自身實踐，在大數據異常檢測方面不斷深耕，繼續優化演算法模型在不同業務場景中的性能，持續為開發者們分享前沿的理念與最新的實踐方案。

④ 決策樹基本概念及演算法優缺點

分類決策樹模型是一種描述對實例進行分類的樹形結構. 決策樹由結點和有向邊組成. 結點有兩種類型: 內部結點和葉節點. 內部節點表示一個特徵或屬性, 葉節點表示一個類.
決策樹(Decision Tree),又稱為判定樹, 是一種以樹結構(包括二叉樹和多叉樹)形式表達的預測分析模型.

分類樹--對離散變數做決策樹

回歸樹--對連續變數做決策樹

優點:
(1)速度快: 計算量相對較小, 且容易轉化成分類規則. 只要沿著樹根向下一直走到葉, 沿途的分裂條件就能夠唯一確定一條分類的謂詞.
(2)准確性高: 挖掘出來的分類規則准確性高, 便於理解, 決策樹可以清晰的顯示哪些欄位比較重要, 即可以生成可以理解的規則.
(3)可以處理連續和種類欄位
(4)不需要任何領域知識和參數假設
(5)適合高維數據
缺點:
(1)對於各類別樣本數量不一致的數據, 信息增益偏向於那些更多數值的特徵
(2)容易過擬合
(3)忽略屬性之間的相關性

若一事假有k種結果, 對應概率為 , 則此事件發生後所得到的信息量I為:

給定包含關於某個目標概念的正反樣例的樣例集S, 那麼S相對這個布爾型分類的熵為:

其中 代表正樣例, 代表反樣例

假設隨機變數(X,Y), 其聯合分布概率為P(X=xi,Y=yi)=Pij, i=1,2,...,n;j=1,2,..,m
則條件熵H(Y|X)表示在已知隨機變數X的條件下隨機變數Y的不確定性, 其定義為X在給定條件下Y的條件概率分布的熵對X的數學期望

在Hunt演算法中, 通過遞歸的方式建立決策樹.

使用信息增益, 選擇 最高信息增益 的屬性作為當前節點的測試屬性

ID3( Examples,Target_attribute,Attributes )

Examples 即訓練樣例集. Target_attribute 是這棵樹要預測的目標屬性. Attributes 是除目標屬性外供學習到的決策樹測試的屬性列表. 返回能正確分類給定 Examples 的決策樹.

class sklearn.tree.DecisionTreeClassifier(criterion='gini', splitter='best', max_depth=None, min_samples_split=2, min_samples_leaf=1, min_weight_fraction_leaf=0.0, max_features=None, random_state=None, max_leaf_nodes=None, min_impurity_decrease=0.0, min_impurity_split=None, class_weight=None, presort=False)

限制決策樹層數為4的DecisionTreeClassifier實例

This plot compares the decision surfaces learned by a dcision tree classifier(first column), by a random forest classifier(second column), by an extra-trees classifier(third column) and by an AdaBoost classifier(fouth column).

Output:

A comparison of a several classifiers in scikit-learn on synthetic datasets.
The point of this examples is to illustrate the nature of decision boundaries of different classifiers.

Particularly in high-dimensional spaces, data can more easily be separated linearly and the simplicity of classifiers such as naive Bayes and linear SVMs might lead to better generalization than is achieved by other classifiers.

This example fits an AdaBoost decisin stump on a non-linearly separable classification dataset composed of two "Gaussian quantiles" clusters and plots the decision boundary and decision scores.

Output:

⑤ 誰有金融數據挖掘，關聯規則分析與挖掘的一些介紹啊

雨林演算法的數據結構：
AVC-set:節點n包含的所有紀錄在某個屬性上的投影，其中該AVC-set包括了屬性的不同值在每個類別上的計數。
AVC-group:一個節點n上所有的AVC -set的集合
AVC-set的所佔內存的大小正比於對應屬性的不同值個數，AVC-group並不是資料庫信息的簡單的壓縮，它只是提供了建立決策樹需要的信息， AVC-group所佔用的內存空間遠遠小於資料庫所實際佔用的空間。
一般設計方案：
AVC_set
{
//存儲屬性的各個值
DistinctValue[]
//存儲屬性各個值在某個類上對應的計數
DistinctValueCountForClassA[]
DistinctValueCountForClassB[]
… …
}
AVC_group
{
//節點n中的每個屬性的avc_set
AVC_set[]
}
自頂向下決策樹演算法
BuildTree(Node m,datapatition D,algorithm decisionTree)
對D使用決策樹演算法decisionTree得到分裂指標crit(n)
令k為節點n的子節點個數
if(k>0)
建立n的k個子節點c1,…,ck
使用最佳分割將D分裂為D1,…,Dk
for(i=1;i<=k;i++)
BuildTree(ci,Di)
endfor
endif
RainForest 演算法框架重新定義的部分：
1a) for 每一個屬性的謂詞p,尋找最佳的分割
1b) decisionTree.find_best_partitioning(AVC-set of p)
1c) endfor
2a) k= decisionTree.decide_splitting_criterion();//決定最終的分割

雨林演算法的常規過程：
建立節點的AVC-group
(通過讀取整個原始資料庫或者某個分支的資料庫表或文件)
選擇分裂屬性和分裂標准：取決於使用雨林演算法框架的具體演算法，通過逐一檢查AVC-set來選擇。
將數據分解到各個子節點：必須讀取整個數據集(資料庫或文件)，將各條數據分解到各個子節點中，此時如果有足夠的內存，我們將建立一個或多個子節點的AVC-group

參考資料：李岱 rainforest.ppt 什麼是數據挖掘
數據挖掘(Data Mining)，又稱為資料庫中的知識發現(Knowledge Discovery in Database, KDD)，就是從大量數據中獲取有效的、新穎的、潛在有用的、最終可理解的模式的非平凡過程，簡單的說，數據挖掘就是從大量數據中提取或「挖掘」知識。
並非所有的信息發現任務都被視為數據挖掘。例如，使用資料庫管理系統查找個別的記錄，或通過網際網路的搜索引擎查找特定的Web頁面，則是信息檢索（information retrieval）領域的任務。雖然這些任務是重要的，可能涉及使用復雜的演算法和數據結構，但是它們主要依賴傳統的計算機科學技術和數據的明顯特徵來創建索引結構，從而有效地組織和檢索信息。盡管如此，數據挖掘技術也已用來增強信息檢索系統的能力。
編輯本段數據挖掘的起源
為迎接前一節中的這些挑戰，來自不同學科的研究者匯集到一起，開始著手開發可以處理不同數據類型的更有效的、可伸縮的工具。這些工作建立在研究者先前使用的方法學和演算法之上，在數據挖掘領域達到高潮。特別地是，數據挖掘利用了來自如下一些領域的思想：(1) 來自統計學的抽樣、估計和假設檢驗，(2) 人工智慧、模式識別和機器學習的搜索演算法、建模技術和學習理論。數據挖掘也迅速地接納了來自其他領域的思想，這些領域包括最優化、進化計算、資訊理論、信號處理、可視化和信息檢索。
一些其他領域也起到重要的支撐作用。特別地，需要資料庫系統提供有效的存儲、索引和查詢處理支持。源於高性能（並行）計算的技術在處理海量數據集方面常常是重要的。分布式技術也能幫助處理海量數據，並且當數據不能集中到一起處理時更是至關重要。
編輯本段數據挖掘能做什麼

1)數據挖掘能做以下六種不同事情（分析方法）：
· 分類 （Classification）
· 估值（Estimation）
· 預言（Prediction）
· 相關性分組或關聯規則（Affinity grouping or association rules）
· 聚集（Clustering）
· 描述和可視化（Des cription and Visualization）
· 復雜數據類型挖掘(Text, Web ,圖形圖像，視頻，音頻等)
2)數據挖掘分類
以上六種數據挖掘的分析方法可以分為兩類：直接數據挖掘；間接數據挖掘
· 直接數據挖掘
目標是利用可用的數據建立一個模型，這個模型對剩餘的數據，對一個特定的變數（可以理解成資料庫中表的屬性，即列）進行描述。
· 間接數據挖掘
目標中沒有選出某一具體的變數，用模型進行描述；而是在所有的變數中建立起某種關系 。
· 分類、估值、預言屬於直接數據挖掘；後三種屬於間接數據挖掘
3)各種分析方法的簡介
· 分類 （Classification）
首先從數據中選出已經分好類的訓練集，在該訓練集上運用數據挖掘分類的技術，建立分類模型，對於沒有分類的數據進行分類。
例子：
a. 信用卡申請者，分類為低、中、高風險
b. 分配客戶到預先定義的客戶分片
注意： 類的個數是確定的，預先定義好的
· 估值（Estimation）
估值與分類類似，不同之處在於，分類描述的是離散型變數的輸出，而估值處理連續值的輸出；分類的類別是確定數目的，估值的量是不確定的。
例子：
a. 根據購買模式，估計一個家庭的孩子個數
b. 根據購買模式，估計一個家庭的收入
c. 估計real estate的價值
一般來說，估值可以作為分類的前一步工作。給定一些輸入數據，通過估值，得到未知的連續變數的值，然後，根據預先設定的閾值，進行分類。例如：銀行對家庭貸款業務，運用估值，給各個客戶記分（Score 0~1）。然後，根據閾值，將貸款級別分類。
· 預言（Prediction）
通常，預言是通過分類或估值起作用的，也就是說，通過分類或估值得出模型，該模型用於對未知變數的預言。從這種意義上說，預言其實沒有必要分為一個單獨的類。預言其目的是對未來未知變數的預測，這種預測是需要時間來驗證的，即必須經過一定時間後，才知道預言准確性是多少。
· 相關性分組或關聯規則（Affinity grouping or association rules）
決定哪些事情將一起發生。
例子：
a. 超市中客戶在購買A的同時，經常會購買B，即A => B(關聯規則)
b. 客戶在購買A後，隔一段時間，會購買B （序列分析）
· 聚集（Clustering）
聚集是對記錄分組，把相似的記錄在一個聚集里。聚集和分類的區別是聚集不依賴於預先定義好的類，不需要訓練集。
例子：
a. 一些特定症狀的聚集可能預示了一個特定的疾病
b. 租VCD類型不相似的客戶聚集，可能暗示成員屬於不同的亞文化群
聚集通常作為數據挖掘的第一步。例如，"哪一種類的促銷對客戶響應最好？"，對於這一 類問題，首先對整個客戶做聚集，將客戶分組在各自的聚集里，然後對每個不同的聚集，回答問題，可能效果更好。
· 描述和可視化（Des cription and Visualization）
是對數據挖掘結果的表示方式。
編輯本段數據挖掘中的關聯規則上面演算法講的很清楚了，我來舉個例子：

Training data：
Id age income class
1 young 65 G
2 young 15 B
3 young 75 G
4 senior 40 B
5 senior 100 G
6 senior 60 G

AVC set „age「 for N1：
value class count
young B 1
young G 2
senior B 1
senior G 2

AVC set „income「 for N1：
value class count
15 B 1
40 B 1
60 G 1
65 G 1
75 G 1
100 G 1

AVC set „income「 for N2：
value class count
15 B 1
65 G 1
75 G 1

AVC set „age「 for N2:
value class count
young B 1
young G 2

最後推出雨林： N1
age=young / \ age=senior
/ \
N2 N3

最後提醒一點，對於雨林演算法，訓練樣本集不要大於3百萬。否則改用SPRINT。
1.什麼是關聯規則
在描述有關關聯規則的一些細節之前，我們先來看一個有趣的故事： "尿布與啤酒"的故事。
在一家超市裡，有一個有趣的現象：尿布和啤酒赫然擺在一起出售。但是這個奇怪的舉措卻使尿布和啤酒的銷量雙雙增加了。這不是一個笑話，而是發生在美國沃爾瑪連鎖店超市的真實案例，並一直為商家所津津樂道。沃爾瑪擁有世界上最大的數據倉庫系統，為了能夠准確了解顧客在其門店的購買習慣，沃爾瑪對其顧客的購物行為進行購物籃分析，想知道顧客經常一起購買的商品有哪些。沃爾瑪數據倉庫里集中了其各門店的詳細原始交易數據。在這些原始交易數據的基礎上，沃爾瑪利用數據挖掘方法對這些數據進行分析和挖掘。一個意外的發現是："跟尿布一起購買最多的商品竟是啤酒！經過大量實際調查和分析，揭示了一個隱藏在"尿布與啤酒"背後的美國人的一種行為模式：在美國，一些年輕的父親下班後經常要到超市去買嬰兒尿布，而他們中有30%～40%的人同時也為自己買一些啤酒。產生這一現象的原因是：美國的太太們常叮囑她們的丈夫下班後為小孩買尿布，而丈夫們在買尿布後又隨手帶回了他們喜歡的啤酒。
按常規思維，尿布與啤酒風馬牛不相及，若不是藉助數據挖掘技術對大量交易數據進行挖掘分析，沃爾瑪是不可能發現數據內在這一有價值的規律的。
數據關聯是資料庫中存在的一類重要的可被發現的知識。若兩個或多個變數的取值之間存在某種規律性，就稱為關聯。關聯可分為簡單關聯、時序關聯、因果關聯。關聯分析的目的是找出資料庫中隱藏的關聯網。有時並不知道資料庫中數據的關聯函數，即使知道也是不確定的，因此關聯分析生成的規則帶有可信度。關聯規則挖掘發現大量數據中項集之間有趣的關聯或相關聯系。Agrawal等於1993年首先提出了挖掘顧客交易資料庫中項集間的關聯規則問題，以後諸多的研究人員對關聯規則的挖掘問題進行了大量的研究。他們的工作包括對原有的演算法進行優化，如引入隨機采樣、並行的思想等，以提高演算法挖掘規則的效率；對關聯規則的應用進行推廣。關聯規則挖掘在數據挖掘中是一個重要的課題，最近幾年已被業界所廣泛研究。
2.關聯規則挖掘過程、分類及其相關演算法
2.1關聯規則挖掘的過程
關聯規則挖掘過程主要包含兩個階段：第一階段必須先從資料集合中找出所有的高頻項目組(Frequent Itemsets)，第二階段再由這些高頻項目組中產生關聯規則(Association Rules)。
關聯規則挖掘的第一階段必須從原始資料集合中，找出所有高頻項目組(Large Itemsets)。高頻的意思是指某一項目組出現的頻率相對於所有記錄而言，必須達到某一水平。一項目組出現的頻率稱為支持度(Support)，以一個包含A與B兩個項目的2-itemset為例，我們可以經由公式(1)求得包含{A,B}項目組的支持度，若支持度大於等於所設定的最小支持度(Minimum Support)門檻值時，則{A,B}稱為高頻項目組。一個滿足最小支持度的k-itemset，則稱為高頻k-項目組(Frequent k-itemset)，一般表示為Large k或Frequent k。演算法並從Large k的項目組中再產生Large k+1，直到無法再找到更長的高頻項目組為止。
關聯規則挖掘的第二階段是要產生關聯規則(Association Rules)。從高頻項目組產生關聯規則，是利用前一步驟的高頻k-項目組來產生規則，在最小信賴度(Minimum Confidence)的條件門檻下，若一規則所求得的信賴度滿足最小信賴度，稱此規則為關聯規則。例如：經由高頻k-項目組{A,B}所產生的規則AB，其信賴度可經由公式(2)求得，若信賴度大於等於最小信賴度，則稱AB為關聯規則。
就沃爾馬案例而言，使用關聯規則挖掘技術，對交易資料庫中的紀錄進行資料挖掘，首先必須要設定最小支持度與最小信賴度兩個門檻值，在此假設最小支持度min_support=5% 且最小信賴度min_confidence=70%。因此符合此該超市需求的關聯規則將必須同時滿足以上兩個條件。若經過挖掘過程所找到的關聯規則「尿布，啤酒」，滿足下列條件，將可接受「尿布，啤酒」的關聯規則。用公式可以描述Support(尿布，啤酒)>=5%且Confidence(尿布，啤酒)>=70%。其中，Support(尿布，啤酒)>=5%於此應用範例中的意義為:在所有的交易紀錄資料中，至少有5%的交易呈現尿布與啤酒這兩項商品被同時購買的交易行為。Confidence(尿布，啤酒)>=70%於此應用範例中的意義為:在所有包含尿布的交易紀錄資料中，至少有70%的交易會同時購買啤酒。因此，今後若有某消費者出現購買尿布的行為，超市將可推薦該消費者同時購買啤酒。這個商品推薦的行為則是根據「尿布，啤酒」關聯規則，因為就該超市過去的交易紀錄而言，支持了「大部份購買尿布的交易，會同時購買啤酒」的消費行為。
從上面的介紹還可以看出，關聯規則挖掘通常比較適用與記錄中的指標取離散值的情況。如果原始資料庫中的指標值是取連續的數據，則在關聯規則挖掘之前應該進行適當的數據離散化（實際上就是將某個區間的值對應於某個值），數據的離散化是數據挖掘前的重要環節，離散化的過程是否合理將直接影響關聯規則的挖掘結果。
2.2關聯規則的分類
按照不同情況，關聯規則可以進行分類如下：
1.基於規則中處理的變數的類別，關聯規則可以分為布爾型和數值型。
布爾型關聯規則處理的值都是離散的、種類化的，它顯示了這些變數之間的關系；而數值型關聯規則可以和多維關聯或多層關聯規則結合起來，對數值型欄位進行處理，將其進行動態的分割，或者直接對原始的數據進行處理，當然數值型關聯規則中也可以包含種類變數。例如：性別=「女」=>職業=「秘書」 ，是布爾型關聯規則；性別=「女」=>avg（收入）=2300，涉及的收入是數值類型，所以是一個數值型關聯規則。
2.基於規則中數據的抽象層次，可以分為單層關聯規則和多層關聯規則。
在單層的關聯規則中，所有的變數都沒有考慮到現實的數據是具有多個不同的層次的；而在多層的關聯規則中，對數據的多層性已經進行了充分的考慮。例如：IBM台式機=>Sony列印機，是一個細節數據上的單層關聯規則；台式機=>Sony列印機，是一個較高層次和細節層次之間的多層關聯規則。
3.基於規則中涉及到的數據的維數，關聯規則可以分為單維的和多維的。
在單維的關聯規則中，我們只涉及到數據的一個維，如用戶購買的物品；而在多維的關聯規則中，要處理的數據將會涉及多個維。換成另一句話，單維關聯規則是處理單個屬性中的一些關系；多維關聯規則是處理各個屬性之間的某些關系。例如：啤酒=>尿布，這條規則只涉及到用戶的購買的物品；性別=「女」=>職業=「秘書」，這條規則就涉及到兩個欄位的信息，是兩個維上的一條關聯規則。
2.3關聯規則挖掘的相關演算法
1.Apriori演算法：使用候選項集找頻繁項集
Apriori演算法是一種最有影響的挖掘布爾關聯規則頻繁項集的演算法。其核心是基於兩階段頻集思想的遞推演算法。該關聯規則在分類上屬於單維、單層、布爾關聯規則。在這里，所有支持度大於最小支持度的項集稱為頻繁項集，簡稱頻集。
該演算法的基本思想是：首先找出所有的頻集，這些項集出現的頻繁性至少和預定義的最小支持度一樣。然後由頻集產生強關聯規則，這些規則必須滿足最小支持度和最小可信度。然後使用第1步找到的頻集產生期望的規則，產生只包含集合的項的所有規則，其中每一條規則的右部只有一項，這里採用的是中規則的定義。一旦這些規則被生成，那麼只有那些大於用戶給定的最小可信度的規則才被留下來。為了生成所有頻集，使用了遞推的方法。
可能產生大量的候選集,以及可能需要重復掃描資料庫，是Apriori演算法的兩大缺點。
2.基於劃分的演算法
Savasere等設計了一個基於劃分的演算法。這個演算法先把資料庫從邏輯上分成幾個互不相交的塊，每次單獨考慮一個分塊並對它生成所有的頻集，然後把產生的頻集合並，用來生成所有可能的頻集，最後計算這些項集的支持度。這里分塊的大小選擇要使得每個分塊可以被放入主存，每個階段只需被掃描一次。而演算法的正確性是由每一個可能的頻集至少在某一個分塊中是頻集保證的。該演算法是可以高度並行的，可以把每一分塊分別分配給某一個處理器生成頻集。產生頻集的每一個循環結束後，處理器之間進行通信來產生全局的候選k-項集。通常這里的通信過程是演算法執行時間的主要瓶頸；而另一方面，每個獨立的處理器生成頻集的時間也是一個瓶頸。
3.FP-樹頻集演算法
針對Apriori演算法的固有缺陷，J. Han等提出了不產生候選挖掘頻繁項集的方法：FP-樹頻集演算法。採用分而治之的策略，在經過第一遍掃描之後，把資料庫中的頻集壓縮進一棵頻繁模式樹（FP-tree），同時依然保留其中的關聯信息，隨後再將FP-tree分化成一些條件庫，每個庫和一個長度為1的頻集相關，然後再對這些條件庫分別進行挖掘。當原始數據量很大的時候，也可以結合劃分的方法,使得一個FP-tree可以放入主存中。實驗表明，FP-growth對不同長度的規則都有很好的適應性，同時在效率上較之Apriori演算法有巨大的提高。
3.該領域在國內外的應用
3．1關聯規則發掘技術在國內外的應用
就目前而言，關聯規則挖掘技術已經被廣泛應用在西方金融行業企業中，它可以成功預測銀行客戶需求。一旦獲得了這些信息，銀行就可以改善自身營銷。現在銀行天天都在開發新的溝通客戶的方法。各銀行在自己的ATM機上就捆綁了顧客可能感興趣的本行產品信息，供使用本行ATM機的用戶了解。如果資料庫中顯示，某個高信用限額的客戶更換了地址，這個客戶很有可能新近購買了一棟更大的住宅，因此會有可能需要更高信用限額，更高端的新信用卡，或者需要一個住房改善貸款，這些產品都可以通過信用卡賬單郵寄給客戶。當客戶打電話咨詢的時候，資料庫可以有力地幫助電話銷售代表。銷售代表的電腦屏幕上可以顯示出客戶的特點，同時也可以顯示出顧客會對什麼產品感興趣。
同時，一些知名的電子商務站點也從強大的關聯規則挖掘中的受益。這些電子購物網站使用關聯規則中規則進行挖掘，然後設置用戶有意要一起購買的捆綁包。也有一些購物網站使用它們設置相應的交叉銷售，也就是購買某種商品的顧客會看到相關的另外一種商品的廣告。
但是目前在我國，「數據海量，信息缺乏」是商業銀行在數據大集中之後普遍所面對的尷尬。目前金融業實施的大多數資料庫只能實現數據的錄入、查詢、統計等較低層次的功能，卻無法發現數據中存在的各種有用的信息，譬如對這些數據進行分析，發現其數據模式及特徵，然後可能發現某個客戶、消費群體或組織的金融和商業興趣，並可觀察金融市場的變化趨勢。可以說，關聯規則挖掘的技術在我國的研究與應用並不是很廣泛深入。
3．2近年來關聯規則發掘技術的一些研究
由於許多應用問題往往比超市購買問題更復雜，大量研究從不同的角度對關聯規則做了擴展，將更多的因素集成到關聯規則挖掘方法之中，以此豐富關聯規則的應用領域，拓寬支持管理決策的范圍。如考慮屬性之間的類別層次關系，時態關系，多表挖掘等。近年來圍繞關聯規則的研究主要集中於兩個方面，即擴展經典關聯規則能夠解決問題的范圍，改善經典關聯規則挖掘演算法效率和規則興趣性。
編輯本段數據挖掘技術實現
在技術上可以根據它的工作過程分為：數據的抽取、數據的存儲和管理、數據的展現等關鍵技術。
·數據的抽取
數據的抽取是數據進入倉庫的入口。由於數據倉庫是一個獨立的數據環境，它需要通過抽取過程將數據從聯機事務處理系統、外部數據源、離線的數據存儲介質中導入數據倉庫。數據抽取在技術上主要涉及互連、復制、增量、轉換、調度和監控等幾個方面的處理。在數據抽取方面，未來的技術發展將集中在系統功能集成化方面，以適應數據倉庫本身或數據源的變化，使系統更便於管理和維護。
·數據的存儲和管理
數據倉庫的組織管理方式決定了它有別於傳統資料庫的特性，也決定了其對外部數據的表現形式。數據倉庫管理所涉及的數據量比傳統事務處理大得多，且隨時間的推移而快速累積。在數據倉庫的數據存儲和管理中需要解決的是如何管理大量的數據、如何並行處理大量的數據、如何優化查詢等。目前，許多資料庫廠家提供的技術解決方案是擴展關系型資料庫的功能，將普通關系資料庫改造成適合擔當數據倉庫的伺服器。
·數據的展現
在數據展現方面主要的方式有：
查詢：實現預定義查詢、動態查詢、OLAP查詢與決策支持智能查詢；報表：產生關系數據表格、復雜表格、OLAP表格、報告以及各種綜合報表；可視化：用易於理解的點線圖、直方圖、餅圖、網狀圖、互動式可視化、動態模擬、計算機動畫技術表現復雜數據及其相互關系；統計：進行平均值、最大值、最小值、期望、方差、匯總、排序等各種統計分析；挖掘：利用數據挖掘等方法，從數據中得到關於數據關系和模式的知識。
編輯本段數據挖掘與數據倉庫融合發展
數據挖掘和數據倉庫的協同工作，一方面，可以迎合和簡化數據挖掘過程中的重要步驟，提高數據挖掘的效率和能力，確保數據挖掘中數據來源的廣泛性和完整性。另一方面，數據挖掘技術已經成為數據倉庫應用中極為重要和相對獨立的方面和工具。
數據挖掘和數據倉庫是融合與互動發展的，其學術研究價值和應用研究前景將是令人振奮的。它是數據挖掘專家、數據倉庫技術人員和行業專家共同努力的成果，更是廣大渴望從資料庫「奴隸」到資料庫「主人」轉變的企業最終用戶的通途。
統計學與數據挖掘
統計學和數據挖掘有著共同的目標：發現數據中的結構。事實上，由於它們的目標相似，一些人（尤其是統計學家）認為數據挖掘是統計學的分支。這是一個不切合實際的看法。因為數據挖掘還應用了其它領域的思想、工具和方法，尤其是計算機學科，例如資料庫技術和機器學習，而且它所關注的某些領域和統計學家所關注的有很大不同。
1．統計學的性質
試圖為統計學下一個太寬泛的定義是沒有意義的。盡管可能做到，但會引來很多異議。相反，我要關注統計學不同於數據挖掘的特性。
差異之一同上節中最後一段提到的相關，即統計學是一門比較保守的學科，目前有一種趨勢是越來越精確。當然，這本身並不是壞事，只有越精確才能避免錯誤，發現真理。但是如果過度的話則是有害的。這個保守的觀點源於統計學是數學的分支這樣一個看法，我是不同意這個觀點的,盡管統計學確實以數學為基礎（正如物理和工程也以數學為基礎，但沒有被認為是數學的分支），但它同其它學科還有緊密的聯系。
數學背景和追求精確加強了這樣一個趨勢：在採用一個方法之前先要證明，而不是象計算機 這

⑥ 求問隨機森林演算法的簡單實現過程

隨機森林（Random forest）指的是利用多棵樹對樣本進行訓練並預測的一種分類器。 並且其輸出的類別是由個別樹輸出的類別的眾數而定。在機器學習中有一個地位很重要的包scikit-learn可實現隨機森林演算法。

原理：（隨機森林的分類預測和回歸預測sklearn.ensemble.RandomForestRegressor方法）
(1)給定訓練集S，測試集T，特徵維數F。確定參數：使用到的CART的數量t，每棵樹的深度d，每個節點使用到的特徵數量f，終止條件：節點上最少樣本數s，節點上最少的信息增益m，對於第1-t棵樹，i=1-t：
(2)從S中有放回的抽取大小和S一樣的訓練集S(i)，作為根節點的樣本，從根節點開始訓練
(3)如果當前節點上達到終止條件，則設置當前節點為葉子節點，如果是分類問題，該葉子節點的預測輸出為當前節點樣本集合中數量最多的那一類c(j)，概率p為c(j)占當前樣本集的比例；如果是回歸問題，預測輸出為當前節點樣本集各個樣本值的平均值。然後繼續訓練其他節點。如果當前節點沒有達到終止條件，則從F維特徵中無放回的隨機選取f維特徵。利用這f維特徵，尋找分類效果最好的一維特徵k及其閾值th，當前節點上樣本第k維特徵小於th的樣本被劃分到左節點，其餘的被劃分到右節點。繼續訓練其他節點。
(4)重復(2)(3)直到所有節點都訓練過了或者被標記為葉子節點。
(5)重復(2),(3),(4)直到所有CART都被訓練過。
隨機森林的簡單實現過程如下：
一、 開發環境、編譯環境：
PyCharm Community Edition 2016.2.3
python2.7.10
二、 所用庫及安裝方法：
pandas[python自帶]
sklearn：命令行pip install sklearn;如果沒有安裝pip,先使用easy_install pip安裝pip；如果在MAC上沒有許可權，使用sudo pip install sklearn;
三、 代碼介紹
1. 使用pandas讀取本地excel的訓練集和測試集，將屬性集賦給X_train和Y_train;將要預測的集合賦給X_test和Y_test;
2. 使用DictVectorizer對數據進行規范化、標准化
3. 生成RandomForestRegressor對象，並將訓練集傳入fit方法中進行訓練
4. 調用predict函數進行預測，並將結果存入y_predict變數中；
5. 使用mean_squared_error、score方法輸出MSE、NMSE值對擬合度、穩定度進行分析；輸出feature_importance，對影響最終結果的屬性進行分析；
6. 詳細代碼見附錄
四、 附錄
# coding:utf-8
import pandas as pd
data_train = pd.read_excel('/Users/xiaoliu/Desktop/data_train.xlsx')
X_train = data_train[['CPI', 'GDP', 'PPI', 'AJR', 'BJFJ', 'FBDR', 'PCFD', 'PCFDED', 'BDR']]
y_train = data_train['FJ']

data_test = pd.read_excel('/Users/xiaoliu/Desktop/data_test.xlsx')
X_test = data_test[['CPI', 'GDP', 'PPI', 'AJR', 'BJFJ', 'FBDR', 'PCFD', 'PCFDED', 'BDR']]
y_test = data_test['FJ']

from sklearn.feature_extraction import DictVectorizer

vec = DictVectorizer(sparse=False)
X_train = vec.fit_transform(X_train.to_dict(orient='records'))
X_test = vec.transform(X_test.to_dict(orient='records'))

from sklearn.ensemble import RandomForestRegressor
rf = RandomForestRegressor()
rf.fit(X_train,y_train)
y_predict = rf.predict(X_test)
print 'predict value:',y_predict

from sklearn.metrics import mean_squared_error
print 'MSE:', mean_squared_error(y_test, y_predict)
print 'NMES:',rf.score(X_test, y_test)
print rf.feature_importances_