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

在本單元中,您將探索最簡單且最常見的分割器演算法,並在下列設定中建立 featureit 格式的條件:

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

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

D={(xi,yi)}i[1,n]

其中:

  • xiR (實際數字集) 的數值特徵值。
  • yi 是二進位範圍的「{orange, blue}」二進位分類值。

我們的目標是找出門檻值 t (門檻),這樣根據 xit 條件將範例 D 分成 $$(rue) F(alse)T F」和「更多」的範例

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

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

三張圖表。高熵圖表代表兩個不同類別的大量理解。低項目圖表說明兩個不同類別的一點點認同。無爭議圖表顯示兩個不同類別的表示;也就是說,無熵圖表只會顯示單一類別。

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

 

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

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

兩張圖表顯示兩個不同類別的程式碼差異很大。

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

 

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

兩張圖表。一張圖表顯示了大約 95% 的橘色類別和 5% 的藍色類別。另一個圖表是由約 95% 的藍色類別和 5% 的橘色類別組成。

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

 

正式:

T={(xi,yi)|(xi,yi)D with xit}F={(xi,yi)|(xi,yi)D with xi<t}R(X)=|{x|xX and x=pos}||X|H(X)=plogp(1p)log(1p) with p=R(X)IG(D,T,F)=H(D)|T||D|H(T)|F||D|H(F)

其中:

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

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

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

四個門檻值和其他參數的比較。此圖下方的清單匯總了每個圖表。

圖 11. 四個門檻圖。

 

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

  • 「頻率」圖表則顯示觀測結果的相對分散度介於 18 到 60 次之間。廣泛值分佈代表有許多潛在的分割項目,非常適合用於訓練模型。
  • 資料集中「藍色」的比率約為 25%。藍色標籤的「比率」圖表表示門檻值介於 20 到 50 之間:

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

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

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

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

一組實際數字 (R) 中的候選值是無限。不過,由於範例數量有限,只有 DF 的有限數量有限制。因此,只有少量的 t 值可用於測試。

傳統方法是按照 xs(i) 遞增排序 xi 值,如下所示:

xs(i)xs(i+1)

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

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

X={xs(i)+xs(i+1)2|xs(i)xs(i+1)}

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

O(mnlog2n)

其中:

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

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