在本單元中,您將探索最簡單且最常見的分割器演算法,並在下列設定中建立 格式的條件:
- 二元分類工作
- 範例中缺少值
- 對範例沒有預先計算的索引
假設一組 範例含有數值特徵,以及二元期標籤「橘色」和「藍色」。形式來說,請將資料集 描述為:
其中:
- 是 (實際數字集) 的數值特徵值。
- 是二進位範圍的「{orange, blue}」二進位分類值。
我們的目標是找出門檻值 (門檻),這樣根據 條件將範例 分成 $$(rue) F(alse)T F」和「更多」的範例
Shannon entropy 是一項失調指標。二進位檔標籤:
- 範例中的標籤達到平衡時 (Shannon 熵的最大值) 為 50% (藍色和 50% 的橘色)。
- 範例中的標籤為純粹 (100% 藍色或 100% 橘色) 時,Shannon 頂點至少等於 (值零)。
圖 8. 三個不同的熵層級。
正式來說,我們希望找出一個條件來減少 和 中標籤分佈的加權總和。對應的分數是資訊增益,也就是 ' 熵和 {,} 的差距。這個差異稱為「資訊增益」。
下圖顯示錯誤的分割,其中熵保持不變,且資訊偏低:
圖 9. 不佳的分割無法減少標籤順序。
相較之下,下圖呈現的分割效果較好,熵的分數偏低 (而且資訊增長) 較高:
圖 10. 良好的分割方式會減少標籤的數量。
正式:
其中:
- 是將 拆分成 和 的相關資訊。
- 是一組範例 的熵。
- 是集合 中的元素數量。
- 是門檻值。
- 是「positive」標籤值,例如在上述範例中為「quot;blue"」。選擇不同的標籤做為「正面標籤」;不會變更概略值或資訊增益。
- 是範例 中的正標籤值比率。
- 是資料集 (如本單元的先前定義)。
在以下範例中,系統會將具有單一數值特徵 的二元分類資料集納入考量。下圖顯示了不同門檻 值 (x 軸):
- 特徵 的直方圖。
- 、 和 中的範例,以門檻值為依據。
- 、 和 的熵。
- 資訊增加;也就是說, 和 {,} 之間的熵差異是根據樣本數量加權計算。
圖 11. 四個門檻圖。
這些圖表會顯示以下內容:
- 「頻率」圖表則顯示觀測結果的相對分散度介於 18 到 60 次之間。廣泛值分佈代表有許多潛在的分割項目,非常適合用於訓練模型。
資料集中「藍色」的比率約為 25%。藍色標籤的「比率」圖表表示門檻值介於 20 到 50 之間:
- 組合含有超過「藍色」標籤的例子 (標籤數量上限為 35%,上限為 35%)。
- 集合含有「藍色」標籤的互補缺陷,閾值 35 僅為 8%。
「藍色標籤的比率」和「資訊集」的圖表皆代表標籤在這個閾值範圍內,相對位置的相對精確性。
這項觀察結果會在「資訊增益」圖表中獲得確認。在 t~=28 中,資訊取得的最大值為:x = 28。因此,分割器傳回的條件會是 。
資訊增加一律為正或空值。門檻值會轉換為零,因為門檻值會轉換為最大 / 最小值。在這些情況下, 或 都空白,而另一個則包含整個資料集,並以 {0/} 代表 的系數。 在 = = 時,資訊增長也是零。在閾值 60 時,F$ 都是多少。
一組實際數字 () 中的候選值是無限。不過,由於範例數量有限,只有 和 的有限數量有限制。因此,只有少量的 值可用於測試。
傳統方法是按照 xs(i) 遞增排序 xi 值,如下所示:
接著,在 的連續排序值中途測試每個值的 。例如,假設您有特定特徵的 1,000 個浮點值。排序後,假設前兩個值是 8.5 和 8.7。在此情況下,要測試的第一個門檻值為 8.6。
我們會考慮使用以下 t 候選值:
這個演算法的時間複雜度為 , 中的節點範例 (因為特徵值的排序)。在決策樹上套用時,分割演算法會套用至每個節點和每個特徵。請注意,每個節點都會收到約 1/2 的父項範例。因此,根據主要定理,使用這個分割器訓練決策樹狀結構的時間複雜度為:
其中:
- 是特徵的數量。
- 是訓練範例的數量。
在這個演算法中,特徵的值無關,僅是順序。因此,這個演算法的運作方式與特徵值的縮放或分佈無關。因此在訓練決策樹狀圖時,我們不需要標準化或縮放數值特徵。