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得到的最大間隔超平面。在超平面上的樣本點也稱爲支援向量。