符號學派主要演算法

決策樹演算法

1. 決策樹基本概念
   一種由上而下，利用不同屬性的值，來逐漸細分類別的一種監督式分類演算法，每個內部節點(Internal Node)代表一個數性的測試決策點，每個分支(Branch)代表一個測試的結果輸出，每個葉點(Leaf)則代表最後的分類結果。

2. 熵值基本概念
   熵值(Entropy)又稱「亂度」指資料分割的不純度或稱混雜度，利用某特徵來分成兩類時，同一類裡面相同類別的比例愈高則純度愈高，也表示資訊獲利能力高，熵值低。

3. 決策樹訓練步驟
   ①選出所有重要相關的特徵變數。
   ②將所有樣本看成一個節點。
   ③利用熵值計算，找出一個最有區別力，純度最高、熵值最低的屬性當作第一個內部分割節點。
   ④將決策樹分為N1與N2兩個Subtree。
   ⑤對N1與N2執行③直到達到最後的分類結果(葉點)為止。

4. 決策樹優點

• 可解釋性及可視性：透過層級快速瞭解特徵重要性。
• 穩健性。
• 泛用性。
• 容易性

5. 缺點

• 樣本不平衡問題。
• 地區最佳化問題(Local Optimization)：決策樹是一步一步來尋找最優的區別節點，是屬於一種貪心性的演算法(Greedy Algorithm)，因每顆樹特性不同，無法保證得到全局最佳解(Global Optimization)。
• 過度擬合問題：維度太多、深度太長、太複雜會產生過度擬合的偏失問題，容易出錯，概化能不足。

集成學習法(Ensemble Mrthod)

為了降低單一樣本與模式的缺點，而混合多種樣本子集合、多種演算法且最後透過投票的多數決或用加權平均的方式，來產生最後答案的一種混合式學習法。

1. 袋裝法(Bagging)
   又稱引導聚集演算法(Bootstrap Aggregation)，利用隨機抽取多個不同子樣本集(Sub Sample Set)經過模式運算後，將結果答案以投票或平均方式來決定的一種集成學習方法。
   在 分類 任務中使用投票決定，在 迴歸 任務則使用平均。
   此為並行方法，無強依賴關係，具獨立性。
   袋裝法因為不斷抽樣不斷training，所以主要是降低樣本偏差、不平衡以及噪音(品質不好的資料)問題。

2. 隨機森林(Random Forest, RF)
   除了隨機抽取多種不同的樣本子集合減少樣本偏失外，再原來樣本的特徵中隨機選擇不同特徵子集合(Feature Sub Set)來建構演算法，使每一棵樹皆為獨立的、不相同的、不會有相關性。
   此為並行方法，無強依賴關係，具獨立性。
   因隨機森林同時解決單一樣本的偏失以及單一演算法偏失，就像由「多位法官」同時看各種「不同角度案件資訊」，最後再綜合所有法官的意見來作判斷，大大降低過度擬合、不穩定問題，也大大提升準確度。

3. 提升法(Boosting)
   為一種序列式、不斷的「從錯誤中改善模式準確度」的一種集成學習法，具有強依賴關係。
   從以前預測錯誤中學習，以便在未來做出更好的預測。
   主要原理☞給一系列的弱學習器賦予權重，先前被分錯的樣本會被給予更多權重。

• 自適應提升法(Adaptive Boosting, AdaBoost)
• 梯度提升法(Gradient Bootsing)
• 極端梯度提升法(Extreme Gradient Boosting, XGBoost)☞隨機抽取特徵，故不會每次都拿全部特徵參與決策。

補充：堆疊法(Stacking)

截然不同組合，多模型方法，對同問題探索不同模型空間。
可建立多個不同學習方式，使用期建構中間預測，一個模型，一個預測。使用中介預測訓練新模型學同個目標。
利用投票、迴歸、新模型預測。

參考資料
人工智慧-概念應用與管理　林東清著