決策樹 Decision Tree
決策樹是樹狀演算法的代表,
其延伸還有隨機森林與 GBDT (Gradient Boosted Decision Tree) 演算法。
決策樹的核心概念就是在尋找「重要的屬性」,
怎樣才算是重要的屬性 會 因用途 而 有所不同,
但「重要的屬性」基本上 能「降低 某件事情的不確定性 的 數量」;
在分類問題中,就是希望 分割出來 的 群組內
越純、均一、同質性 越高越好,
而 組間的差異 要大。
決策樹的流程,就是在降低不純度同時理解這批資料。
最常見的分割原則稱為資訊增益 (information gain),
它是一種以「熵」ㄕㄤ(entropy,雜亂程度)作為純度衡量基礎的方法。
當 某個屬性 對分類越有用,代表我們透過該屬性建立的區隔,
能大幅降低 entropy,使 資訊增益 大幅提升。
舉例來說,若要在一批貓與狗的資料中區分二者,
「毛色」可能無法帶來 最大的資訊增益,而「耳朵形狀」
可能就能大幅降低分類的雜亂程度,大幅提高資訊增益。
因此「耳朵形狀」會是區隔貓狗中很重要的屬性。
樹狀結構 由根部開始 由上而下,由根節點開始、每個節點 都用一個屬性
作檢驗,以分支出 更多的 內部節點 與 終端節點(即葉節點,為預測結果)
構成。
在上述的例子中,「耳朵形狀」作為重要的屬性,更可能被放在上方的節點。
決策樹有幾個特點:
- 人類容易解釋 if-then 的模型結果
- 資料若有些許變化,結果就會產明顯變化,預測性能稍差
- 只能批次學習
- 可處理 非線性的資料,但 不擅長處理 線性的資料
- 樹狀結構 複雜多層 的情形下容易產生 過度擬合 (overfitting) 的問題
支援向量機 SVM (Support Vector Machine)
SVM 的概念其實不像它的名字一樣難以理解;
SVM 的目標,是在畫出一條決策分界線 (decision boundary),
在決策分界線的兩側找與這個邊界最相近的資料點作為 support vector,
希望最靠近邊界的這些 support vector 可以與這條現有最大的距離,
以便區分二類。
另外,SVM 演算法還會使用「核心」 (kernel) 的技巧。
核心 (kernel) 的概念就是,「在較低維度時無法以線性分割的資料,
將他們 轉至更高維度,就是能夠線性分割的」;
想像手機遊戲《水果忍者》,如果那些水果全都放在桌上(二維),
你很難用一條直線將他們區隔開來,但當他們被拋到空中,
你就能在空中(三維)畫出一個切面來分隔這些水果,
而這個切面在三維空間裡屬於線性,但投射回平面,就可能是條曲線。
常見的核心技巧如
線性核心 (linear kernel)、
多項式核心 (polynomial kernel)、
RBF 核心 (radial basis function)。
SVM有以下幾個特點:
- 邊界最大化後,可得到一個平滑的超平面
- 可利用 kernel 技巧分離非線性的資料
- 可在線學習或批次學習
KNN (K-Nearest Neighbor)
KNN 演算法就如字面上意思一樣直觀,它會在輸入一筆資料 i 時,
根據與 i 最鄰近的 k 個已知資料類別,去決定該筆輸入資料的類別。
這種演算法除了做分類用途,也能用來做近似項目的搜尋。
須注意的是,如果當某個屬性值出現在絕大多數的資料中可能會影響結果。
例如 100 筆資料中有 90 筆具 A 屬性、10 筆具 B 屬性,則有可能
在測試資料的眾多特徵都偏向 B 時卻被分為 A 類,
因此資料須先經過正規化處理。
另外,k 的選擇也可能大幅影響決策分界線的結果,
原因是 k 具有類似「投票票數」的概念。
因此,當 k 為偶數而 k 個最近鄰居有多個類別「票數」一樣多時,
或當 k 為目標類別數的倍數時,都會有難以判定類別的問題。
另外,當 k 的數量過小或過大時,
也會產生 overfitting 或 underfitting 的問題。
選擇 k 值時,通常會將資料間的距離與散布方向作為驗證參考。
KNN 演算法幾個特點如下:
- 因為需計算每一筆資料之間的距離,計算上較耗時
- k 的數量大幅影響預測的結果與性能