CART：選擇Gini係數最小的作為劃分特徵，Gini係數越小，純度越高。（只能二叉樹，既能分類又能回歸）

代價函數

N：決策樹在該節點 (在特定數據集中訓練的時候) 的樣本數

H(T)：該葉子節點的熵值

T：決策樹的葉節點個數，即模型複雜度

alpha：正則化參數

剪枝策略

目的是防止過擬合，增強其泛化能力

預剪枝

1. 簡介：對每個結點在劃分前先進行限定，比如在python 中設定max_depth，樹的高度，每個節點/葉子節點的最小樣本值、最大節點/葉子節點數等等，達到該指標時就停止生長
2. 優缺點：代價小，但容易產生「視界局限」，斷絕了其後繼節點進行「好」的分支操作的任何可能性往往可以達到局部最優解卻不能達到全局最優解，不一定是最佳的決策樹。

後剪枝：

1. 簡介：先讓樹充分生長，然後對所有相鄰的成對葉節點考慮是否消去它們，比預剪枝保留了更多的分支，它是自底向上的剪枝，克服了「視界局限」
2. 優缺點：欠擬合風險較小，泛化能力往往優於預剪枝，然而因為要完全生長一棵樹，花費很多時間訓練，數據集規模大、維度高時並不適用實際應用。

其他

1. 連續值怎麼處理？連續值離散化處理，劃分成不同的區間
2. 遞歸的終止條件是什麼呢？
3. 所有訓練數據子集被基本正確分類
4. 沒有合適的特徵可選，可用特徵為0，或者可用特徵的信息增益或信息增益比都很小了。

隨機森林

模型思想

1. 雙重隨機性
2. 從N個樣本中以有放回抽樣的方式，即從原始訓練集中隨機選擇n個樣本，作為訓練集
3. 對於每一個決策點，從原始訓練集的M個特徵數中隨機選擇m個特徵來構建最佳分裂方式，以此構建多棵決策樹形成隨機森林，每棵樹完整生長不剪枝
4. 結果判別：對於分類問題，按多棵樹分類器投票決定最終分類結果；對於回歸問題，由多棵樹預測值的均值決定最終預測結果
5. 通常選取logn2+1個屬性，其中n是數據集的實例數。
6. 誤差分析：將各個樹的未採樣樣本作為預測樣本統計誤差作為誤分率

模型優缺點

準確率可以和Adaboost相媲美，對錯誤和離群點更魯棒。準確率依賴於個體分類器的實力和它們之間的依賴性。理想情況是保持個體分類器的能力而不提高它們的相關性。

優點

1. 減少過擬合：兩個隨機性的引入，使得隨機森林不容易陷入過擬合，具有很好的抗雜訊能力
2. 效率高：。由於在每次劃分時只考慮很少的屬性，可能比Bagging和Boosting更快，因此它們在大型資料庫上非常有效。所以相比於 Bagging 計算開銷更小，訓練效率更高
3. 數據預處理：對數據的適應能力強，可以處理離散和連續的，無需要規範化；
4. 缺失值處理：有很好的方法來填充缺失值，即便有很大一部分數據缺失，仍能維持很高準確度。給出了變數重要性的內在估計，對於不平衡樣本分類，它可以平衡誤差。可以計算各實例的親近度，對於數據挖掘、檢測離群點和數據可視化非常有用

缺點

1. 由於增加了屬性的擾動，隨機森林中基學習器的性能降低，使得在隨機森林在起始時候性能較差，但是隨著基學習器的增多，隨機森林通常會收斂於更低的泛化誤差，相比於 Bagging；
2. 對每次劃分所考慮的屬性數很敏感。
3. 隨機森林方法被證明對大規模數據集和存在大量且有時不相關特徵的項（item）來說很有
4. 在雜訊較大的時候容易過擬合。

python 參數

1. n_estimators:數值型取值: 森林中決策樹的個數，默認是10
2. criterion:字元型取值:採用何種方法度量分裂質量，信息熵或者基尼指數，默認是基尼指數
3. max_features:取值為int型, float型, string類型, or None()，默認"auto"，尋求最佳分割時的考慮的特徵數量，即特徵數達到多大時進行分割。

int:max_features等於這個int值

float:max_features是一個百分比，每(max_features * n_features)特徵在每個分割出被考慮。

"auto":max_features等於sqrt(n_features)

"sqrt":同等於"auto"時

"log2":max_features=log2(n_features)

None:max_features = n_features

1. max_depth:int型取值或者None，默認為None 樹的最大深度
2. min_samples_split:int型取值，float型取值，默認為2，分割內部節點所需的最少樣本數量

int:如果是int值，則就是這個int值

float:如果是float值，則為min_samples_split * n_samples

1. min_samples_leaf:int取值，float取值，默認為1，葉子節點上包含的樣本最小值

int:就是這個int值

float:min_samples_leaf * n_samples

1. min_weight_fraction_leaf : float，default=0.能成為葉子節點的條件是：該節點對應的實例數和總樣本數的比值，至少大於這個min_weight_fraction_leaf值
2. max_leaf_nodes:int類型，或者None(默認None)，最大葉子節點數，以最好的優先方式生成樹，最好的節點被定義為雜質相對較少，即純度較高的葉子節點
3. min_impurity_split:float取值，樹增長停止的閥值。一個節點將會分裂，如果他的雜質度比這個閥值；如果比這個值低，就會成為一個葉子節點。
4. min_impurity_decrease:float取值，默認0. 一個節點將會被分裂，如果分裂之後，雜質度的減少效果高於這個值。
5. bootstrap:boolean類型取值，默認True，是否採用有放回式的抽樣方式
6. class_weight:dict, list or dicts, "balanced"，如果沒有給定這個值，那麼所有類別都應該是權重1，對於多分類問題，可以按照分類結果y的可能取值的順序給出一個list或者dict值，用來指明各類的權重；"balanced"模式，使用y值自動調整權重，該模式類別權重與輸入數據中的類別頻率成反比，即n_samples / (n_classes * np.bincount(y))，分布為第n個類別對應的實例數。 "balanced_subsample"模式和"balanced"模式類似，只是它計算使用的是有放回式的取樣中取得樣本數，而不是總樣本數

相似性演算法比較

都是基於樹演算法，隨機森林（Random Forest）和GBM演算法有什麼不一樣？

回答：基本差異在於，隨機森林演算法使用Bagging技術做預測，GBM使用Boosting技術來做預測。

在Bagging演算法中，數據集使用返回隨機抽樣被分為n個樣本集，然後使用學習演算法在所有樣本上建立模型，得出的預測結果由投票或者平均機制組合。Bagging是平行進行的。

在Boosting演算法中，在第一輪的預測之後，演算法將未分類的預測權重加大，因此該預測可以在接下來的回合中被糾正。這種有序流程，不斷將未分類的預測權重加大直到觸發停止準則。

隨機森林（主要）通過降低方差改進模型的精確度，已生成樹不能幫助減少方差。GBM演算法通過降低模型中的偏差和方差提高精確度。

K-Means

是一種無監督學習演算法

模型優缺點

優點

1. 收斂速度快，模型簡單，如果你的預處理數據和特徵工程都做得十分有效，那它將具備令人驚嘆的靈活性。
2. 聚類效果較優。
3. 演算法的可解釋度比較強。
4. 主要需要調參的參數僅僅是簇數k。

缺點

1. 該演算法需要指定集群的數量，而 K 值的選擇通常都不是那麼容易確定的（肘部法則）
2. 採用迭代方法，得到的結果只是局部最優。（多次隨機初始化K個點）
3. 樣本較大是計算速度慢（用Mini Batch K-Means中，選擇一個合適的批樣本大小batch size，通過無放回的隨機採樣隨機選擇batch size個樣本來做K-Means聚類。用得到不同的隨機採樣集來得到聚類簇，選擇其中最優的聚類簇
4. 如果訓練數據中的真實集群並不是類球狀的，K 均值聚類會得出一些比較差的集群。
5. 對於不是凸的數據集比較難收斂(改進：基於密度的聚類演算法更加適合，如DESCAN演算法)
6. 如果各隱含類別的數據不平衡，比如各隱含類別的數據量嚴重失衡，或者各隱含類別的方差不同，則聚類效果不佳。
7. 對噪音和異常點比較的敏感(改進1：離群點檢測的LOF演算法，通過去除離群點後再聚類，可以減少離群點和孤立點對於聚類效果的影響；改進2：改成求點的中位數，這種聚類方式即K-Mediods聚類（K中值）

K-Means與KNN的區別

1. 無監督/監督
2. K-Means是無監督學習的聚類演算法，沒有樣本輸出；
3. KNN是監督學習的分類演算法，有對應的類別輸出。
4. 是否需要訓練

• K-Means則有明顯的訓練過程，找到k個類別的最佳質心，從而決定樣本的簇類別。
• KNN基本不需要訓練，對測試集裡面的點，只需要找到在訓練集中最近的k個點，用這最近的k個點的類別來決定測試點的類別。

1. 相似點：兩個演算法都包含一個過程，即找出和某一個點最近的點。兩者都利用了最近鄰(nearest neighbors)的思想。

模型演算法

1. 隨機選擇K個點作為聚類中心
2. 計算其他所有的點到這K個中心點的距離，並將它歸到距離最近的聚類中心
3. 重新計算每個聚類的中心點，即每個組的平均值，並更新聚類中心的位置
4. 重複2，3過程，即重新計算所有點距離這些中心點的距離，並進行重新劃分它所歸於的類，並在此更新這個類的中心點……直到這些中心點不再變化

如何選擇K

1. K< m m 聚類中心點個數要小於所有訓練實例的數量
2. 繪製聚類數量與代價函數的關係，選擇曲線的肘部點作為K的個數
3. 根據業務的sense，例如衣服的size人為規定選擇多少型號

公式

分配(Assignment)：將每個觀測分配到聚類中，使得組內平方和（WCSS）達到最小。其中每個{displaystyle x_{p}} 都只被分配到一個確定的聚類{displaystyle S^{t}} 中，儘管在理論上它可能被分配到2個或者更多的聚類。

更新(Update)：對於上一步得到的每一個聚類，以聚類中觀測值的圖心，作為新的均值點。

代價函數：最小化所有的數據點與其所關聯的聚類中心點之間的距離之和

KNN

模型優缺點

1. 優點
2. 演算法本身簡單有效，分類器不需要使用訓練集進行訓練
3. 缺點
4. 分類的計算複雜度和訓練集中的樣本總數成正比

模型演算法

1. 對於未知類別的點，計算它與已知類別數據集中的點的距離
2. 按照距離排序
3. 選取與當前點距離最小的K個點
4. 確定前k個點所在類別的出現概率
5. 返回前k個點出現頻率最高的類別作為當前點預測分類

參考：《python 數據分析與機器學習實戰》

推薦閱讀：