資料探勘機器學習總結
資料探勘機器學習總結
1 決策樹演算法
機器學習中，決策樹是一個預測模型；它代表的是物件屬性值與物件值之間的一種對映關係。樹中每個節點表示某個物件，每個分叉路徑則代表的某個可能的屬性值，而每個葉結點則對應具有上述屬性值的子物件。決策樹僅有單一輸出；若需要多個輸出，可以建立獨立的決策樹以處理不同輸出。
從資料產生決策樹的機器學習技術叫做決策樹學習, 通俗說就是決策樹。
決策樹學習也是資料探勘中一個普通的方法。在這裡，每個決策樹都表述了一種樹型結構，它由它的分支來對該型別的物件依靠屬性進行分類。每個決策樹可以依靠對源資料庫的分割進行資料測試。這個過程可以遞迴式的對樹進行修剪。當不能再進行分割或一個單獨的類可以被應用於某一分支時，遞迴過程就完成了。另外，隨機森林分類器將許多決策樹結合起來以提升分類的正確率。 決策樹同時也可以依靠計算條件機率來構造。決策樹如果依靠數學的計算方法可以取得更加理想的效果。
1.1 決策樹的工作原理
決策樹一般都是自上而下的來生成的。
選擇分割的方法有多種，但是目的都是一致的，即對目標類嘗試進行最佳的分割。
從根節點到葉子節點都有一條路徑，這條路徑就是一條“規則”。
決策樹可以是二叉的，也可以是多叉的。
對每個節點的衡量：
1) 透過該節點的記錄數；
2) 如果是葉子節點的話，分類的路徑；
3) 對葉子節點正確分類的比例。
有些規則的效果可以比其他的一些規則要好。
1.2 ID3演算法
1.2.1 概念提取演算法CLS
1) 初始化引數C={E}，E包括所有的例子，為根；
2) 如果C中的任一元素e同屬於同一個決策類則建立一個葉子節點YES終止；否則依啟發式標準，選擇特徵Fi={V1, V2, V3,……, Vn}並建立判定節點，劃分C為互不相交的N個集合C1，C2，C3，……，Cn；
3) 對任一個Ci遞迴。
1.2.2 ID3演算法
1) 隨機選擇C的一個子集W (視窗)；
2) 呼叫CLS生成W的分類樹DT(強調的啟發式標準在後)；
3) 順序掃描C蒐集DT的意外(即由DT無法確定的例子)；
4) 組合W與已發現的意外，形成新的W；
5) 重複2)到4)，直到無例外為止。
啟發式標準：
只跟本身與其子樹有關，採取資訊理論用熵來量度。
熵是選擇事件時選擇自由度的量度，其計算方法為：P=freq(Cj,S)/|S|；INFO(S)=-SUM(P*LOG(P))；SUM()函式是求j從1到n的和。Gain(X)=Info(X)-Infox(X)；Infox(X)=SUM( (|Ti|/|T|)*Info(X)；
為保證生成的決策樹最小，ID3演算法在生成子樹時，選取使生成的子樹的熵(即Gain(S))最小的特徵來生成子樹。
ID3演算法對資料的要求：
1) 所有屬性必須為離散量；
2) 所有的訓練例的所有屬性必須有一個明確的值；
3) 相同的因素必須得到相同的結論且訓練例必須唯一。
1.3 C4.5演算法
由於ID3演算法在實際應用中存在一些問題，於是Quilan提出了C4.5演算法，嚴格上說C4.5只能是ID3的一個改進演算法。
C4.5演算法繼承了ID3演算法的優點，並在以下幾方面對ID3演算法進行了改進：
1) 用資訊增益率來選擇屬性，克服了用資訊增益選擇屬性時偏向選擇取值多的屬性的`不足；
2) 在樹構造過程中進行剪枝；
3) 能夠完成對連續屬性的離散化處理；
4) 能夠對不完整資料進行處理。
C4.5演算法有如下優點：
產生的分類規則易於理解，準確率較高。
C4.5演算法有如下缺點：
在構造樹的過程中，需要對資料集進行多次的順序掃描和排序，因而導致演算法的低效。此外，C4.5只適合於能夠駐留於記憶體的資料集，當訓練集大得無法在記憶體容納時程式無法執行。
分類決策樹演算法：
C4.5演算法是機器學習演算法中的一種分類決策樹演算法，其核心演算法是ID3演算法。
分類決策樹演算法是從大量事例中進行提取分類規則的自上而下的決策樹。
決策樹的各部分是：
根：學習的事例集；
枝：分類的判定條件；
葉：分好的各個類。
1.3.1 C4.5對ID3演算法的改進
1) 熵的改進，加上了子樹的資訊。
Split_Infox(X)= -SUM( (|T|/|Ti|)*LOG(|Ti|/|T|))；
Gain ratio(X)= Gain(X)/Split_Infox(X);
2) 在輸入資料上的改進
① 因素屬性的值可以是連續量，C4.5對其排序並分成不同的集合後按照ID3演算法當作離散量進行處理，但結論屬性的值必須是離散值。
② 訓練例的因素屬性值可以是不確定的，以?表示，但結論必須是確定的。
3) 對已生成的決策樹進行裁剪，減小生成樹的規模。
2 The k-means algorithm（k平均演算法）
k-means algorithm是一個聚類演算法，把n個物件根據它們的屬性分為k個分割，k < n。它與處理混合正態分佈的最大期望演算法很相似，因為他們都試圖找到資料中自然聚類的中心。它假設物件屬性來自於空間向量，並且目標是使各個群組內部的均方誤差總和最小。
假設有k個群組Si, i=1,2,...,k。μi是群組Si內所有元素xj的重心，或叫中心點。
k平均聚類發明於1956年，該演算法最常見的形式是採用被稱為勞埃德演算法(Lloyd algorithm)的迭代式改進探索法。勞埃德演算法首先把輸入點分成k個初始化分組，可以是隨機的或者使用一些啟發式資料。然後計算每組的中心點，根據中心點的位臵把物件分到離它最近的中心，重新確定分組。繼續重複不斷地計算中心並重新分組，直到收斂，即物件不再改變分組（中心點位臵不再改變）。
勞埃德演算法和k平均通常是緊密聯絡的，但是在實際應用中，勞埃德演算法是解決k平均問題的啟發式法則，對於某些起始點和重心的組合，勞埃德演算法可能實際上收斂於錯誤的結果。（上面函式中存在的不同的最優解）
雖然存在變異，但是勞埃德演算法仍舊保持流行，因為它在實際中收斂非常快。實際上，觀察發現迭代次數遠遠少於點的數量。然而最近，David Arthur和Sergei Vassilvitskii提出存在特定的點集使得k平均演算法花費超多項式時間達到收斂。
近似的k平均演算法已經被設計用於原始資料子集的計算。
從演算法的表現上來說，它並不保證一定得到全域性最優解，最終解的質量很大程度上取決於初始化的分組。由於該演算法的速度很快，因此常用的一種方法是多次執行k平均演算法，選擇最優解。
k平均演算法的一個缺點是，分組的數目k是一個輸入引數，不合適的k可能返回較差的結果。另外，演算法還假設均方誤差是計算群組分散度的最佳引數。
3 SVM（支援向量機）
支援向量機，英文為Support Vector Machine，簡稱SV機（論文中一般簡稱SVM）。它是一種監督式學習的方法，它廣泛的應用於統計分類以及迴歸分析中。
支援向量機屬於一般化線性分類器。它們也可以被認為是提克洛夫規範化（Tikhonov Regularization）方法的一個特例。這種分類器的特點是他們能夠同時最小化經驗誤差與最大化幾何邊緣區。因此支援向量機也被稱為最大邊緣區分類器。
在統計計算中，最大期望（EM）演算法是在機率（probabilistic）模型中尋找引數最大似然估計的演算法，其中機率模型依賴於無法觀測的隱藏變數（Latent Variable）。最大期望經常用在機器學習和計算機視覺的資料集聚（Data Clustering）領域。最大期望演算法經過兩個步驟交替進行計算，第一步是計算期望（E），也就是將隱藏變數像能夠觀測到的一樣包含在內從而計算最大似然的期望值；另外一步是最大化（M），也就是最大化在 E 步上找到的最大似然的期望值從而計算引數的最大似然估計。M 步上找到的引數然後用於另外一個 E 步計算，這個過程不斷交替進行。
Vapnik等人在多年研究統計學習理論基礎上對線性分類器提出了另一種設計最佳準則。其原理也從線性可分說起，然後擴充套件到線性不可分的情況。甚至擴充套件到使用非線性函式中去，這種分類器被稱為支援向量機(Support Vector Machine，簡稱SVM)。支援向量機的提出有很深的理論背景。支援向量機方法是在近年來提出的一種新方法，但是進展很快，已經被廣泛應用在各個領域之中。
SVM的主要思想可以概括為兩點：(1) 它是針對線性可分情況進行分析，對於線性不可分的情況，透過使用非線性對映演算法將低維輸入空間線性不可分的樣本轉化為高維特徵空間使其線性可分，從而使得高維特徵空間採用線性演算法對樣本的非線性特徵進行線性分析成為可能；(2) 它基於結構風險最小化理論之上在特徵空間中建構最優分割超平面，使得學習器得到全域性最最佳化，並且在整個樣本空間的期望風險以某個機率滿足一定上界。
在學習這種方法時，首先要弄清楚這種方法考慮問題的特點，這就要從線性可分的最簡單情況討論起，在沒有弄懂其原理之前，不要急於學習線性不可分等較複雜的情況，支援向量機在設計時，需要用到條件極值問題的求解，因此需用拉格朗日乘子理論，但對多數人來說，以前學到的或常用的是約束條件為等式表示的方式，但在此要用到以不等式作為必須滿足的條件，此時只要瞭解拉格朗日理論的有關結論就行。
支援向量機將向量對映到一個更高維的空間裡，在這個空間裡建立有一個最大間隔超平面。在分開資料的超平面的兩邊建有兩個互相平行的超平面。分隔超平面使兩個平行超平面的距離最大化。假定平行超平面間的距離或差距越大，分類器的總誤差越小。一個極好的指南是C.J.C Burges的《模式識別支援向量機指南》。van der Walt 和 Barnard 將支援向量機和其他分類器進行了比較。
有很多個分類器(超平面）可以把資料分開，但是隻有一個能夠達到最大分割。
我們通常希望分類的過程是一個機器學習的過程。這些資料點並不需要是中的點，而可以是任意(統計學符號)中或者 (計算機科學符號) 的點。我們希望能夠把這些點透過一個n-1維的超平面分開，通常這個被稱為線性分類器。有很多分類器都符合這個要求，但是我們還希望找到分類最佳的平面，即使得屬於兩個不同類的資料點間隔最大的那個面，該面亦稱為最大間隔超平面。如果我們能夠找到這個面，那麼這個分類器就稱為最大間隔分類器。
設樣本屬於兩個類，用該樣本訓練SVM得到的最大間隔超平面。在超平面上的樣本點也稱為支援向量。