含有數值特徵的二元分類專用確切分割器

在本單元中，您將探索最簡單且最常見的分割器演算法，並在下列設定中建立 $\mathrm{feature}_i \geq t$ 格式的條件：

• 二元分類工作
• 範例中缺少值
• 對範例沒有預先計算的索引

假設一組 $n$ 範例含有數值特徵，以及二元期標籤「橘色」和「藍色」。形式來說，請將資料集 $D$ 描述為：

$$D = \{(x_i,y_i)\}_{i\in[1,n]}$$

其中：

• $x_i$ 是 $\mathbb{R}$ (實際數字集) 的數值特徵值。
• $y_i$ 是二進位範圍的「{orange, blue}」二進位分類值。

我們的目標是找出門檻值 $t$ (門檻)，這樣根據 $x_i \geq t$ 條件將範例 $D$ 分成 $$(rue)$ 和$ F(alse)$ 個群組，可以改善標籤的分隔。例如，$T $範例和「$F」和「更多」的範例

Shannon entropy 是一項失調指標。二進位檔標籤：

• 範例中的標籤達到平衡時 (Shannon 熵的最大值) 為 50% (藍色和 50% 的橘色)。
• 範例中的標籤為純粹 (100% 藍色或 100% 橘色) 時，Shannon 頂點至少等於 (值零)。

圖 8. 三個不同的熵層級。

 

正式來說，我們希望找出一個條件來減少 $T$ 和 $F$ 中標籤分佈的加權總和。對應的分數是資訊增益，也就是 $D$' 熵和 {$T$,$F$} 的差距。這個差異稱為「資訊增益」。

下圖顯示錯誤的分割，其中熵保持不變，且資訊偏低：

圖 9. 不佳的分割無法減少標籤順序。

 

相較之下，下圖呈現的分割效果較好，熵的分數偏低 (而且資訊增長) 較高：

圖 10. 良好的分割方式會減少標籤的數量。

 

正式：

\[\begin{eqnarray} T & = & \{ (x_i,y_i) | (x_i,y_i) \in D \ \textrm{with} \ x_i \ge t \} \\[12pt] F & = & \{ (x_i,y_i) | (x_i,y_i) \in D \ \textrm{with} \ x_i \lt t \} \\[12pt] R(X) & = & \frac{\lvert \{ x | x \in X \ \textrm{and} \ x = \mathrm{pos} \} \rvert}{\lvert X \rvert} \\[12pt] H(X) & = & - p \log p - (1 - p) \log (1-p) \ \textrm{with} \ p = R(X)\\[12pt] IG(D,T,F) & = & H(D) - \frac {\lvert T\rvert} {\lvert D \rvert } H(T) - \frac {\lvert F \rvert} {\lvert D \rvert } H(F) \end{eqnarray}\]

其中：

• $IG(D,T,F)$ 是將 $D$ 拆分成 $T$ 和 $F$ 的相關資訊。
• $H(X)$ 是一組範例 $X$ 的熵。
• $|X|$ 是集合 $X$ 中的元素數量。
• $t$ 是門檻值。
• $pos$ 是「positive」標籤值，例如在上述範例中為「quot;blue&quot」。選擇不同的標籤做為「正面標籤」；不會變更概略值或資訊增益。
• $R(X)$ 是範例 $X$ 中的正標籤值比率。
• $D$ 是資料集 (如本單元的先前定義)。

在以下範例中，系統會將具有單一數值特徵 $x$ 的二元分類資料集納入考量。下圖顯示了不同門檻 $t$ 值 (x 軸)：

1. 特徵 $x$ 的直方圖。
2. $blue$、$T$ 和 $F$ 中的範例，以門檻值為依據。
3. $D$、$T$ 和 $F$的熵。
4. 資訊增加；也就是說，$D$ 和 {$T$,$F$} 之間的熵差異是根據樣本數量加權計算。

圖 11. 四個門檻圖。

 

這些圖表會顯示以下內容：

• 「頻率」圖表則顯示觀測結果的相對分散度介於 18 到 60 次之間。廣泛值分佈代表有許多潛在的分割項目，非常適合用於訓練模型。

• 資料集中「藍色」的比率約為 25%。藍色標籤的「比率」圖表表示門檻值介於 20 到 50 之間：

  • $T$ 組合含有超過「藍色」標籤的例子 (標籤數量上限為 35%，上限為 35%)。
  • $F$ 集合含有「藍色」標籤的互補缺陷，閾值 35 僅為 8%。

  「藍色標籤的比率」和「資訊集」的圖表皆代表標籤在這個閾值範圍內，相對位置的相對精確性。

• 這項觀察結果會在「資訊增益」圖表中獲得確認。在 t~=28 中，資訊取得的最大值為：x = 28。因此，分割器傳回的條件會是 $x \geq 28$。

• 資訊增加一律為正或空值。門檻值會轉換為零，因為門檻值會轉換為最大 / 最小值。在這些情況下，$F$ 或 $T$ 都空白，而另一個則包含整個資料集，並以 {0/} 代表 $D$ 的系數。 在 $H(T)$ = $H(F)$ = $H(D)$ 時，資訊增長也是零。在閾值 60 時，$quot$$ 和 $F$ 都是多少。

一組實際數字 ($\mathbb{R}$) 中的候選值是無限。不過，由於範例數量有限，只有 $D$ 和 $F$ 的有限數量有限制。因此，只有少量的 $t$ 值可用於測試。

傳統方法是按照 x_s(i) 遞增排序 x_i 值，如下所示：

$$ x_{s(i)} \leq x_{s(i+1)} $$

接著，在 $x_i$ 的連續排序值中途測試每個值的 $t$。例如，假設您有特定特徵的 1,000 個浮點值。排序後，假設前兩個值是 8.5 和 8.7。在此情況下，要測試的第一個門檻值為 8.6。

我們會考慮使用以下 t 候選值：

$$ X = \left\{ \frac {x_{s(i)} + x_{s(i + 1)}} {2} \lvert x_{s(i)} \ne x_{s(i+1)} \right\} $$

這個演算法的時間複雜度為 $\mathcal{O} ( n \log n) $，$n$ 中的節點範例 (因為特徵值的排序)。在決策樹上套用時，分割演算法會套用至每個節點和每個特徵。請注意，每個節點都會收到約 1/2 的父項範例。因此，根據主要定理，使用這個分割器訓練決策樹狀結構的時間複雜度為：

$$ \mathcal{O} ( m n \log^2 n ) $$

其中：

• $m$ 是特徵的數量。
• $n$ 是訓練範例的數量。

在這個演算法中，特徵的值無關，僅是順序。因此，這個演算法的運作方式與特徵值的縮放或分佈無關。因此在訓練決策樹狀圖時，我們不需要標準化或縮放數值特徵。