什麼是霍夫丁樹演算法？

霍夫丁樹演算法是一種用於流資料分類的決策樹學習方法。它最初用於跟蹤網路點選流並構建模型以預測使用者可能訪問哪些網路主機和網站。它通常以次線性時間執行，並生成與傳統批次學習者生成的決策樹幾乎相同的決策樹。

它使用霍夫丁樹，該樹利用這樣的思想：一個小樣本通常足以選擇最佳分割屬性。霍夫丁界（或加性切爾諾夫界）在數學上支援了這一思想。

假設我們對範圍為R的隨機變數r進行N次獨立觀察，其中r是一個屬性選擇度量。（對於機率，R為1，對於資訊增益，它為log c，其中c是類的數量。）在霍夫丁樹的情況下，r是資訊增益。如果我們計算該樣本的均值r’，則霍夫丁界指出，r的真實均值至少為r’−ε，機率為1−δ，其中δ是使用者指定的，並且

$$\varepsilon=\sqrt{\frac{R^{2}ln\frac{1}{\delta}}{2N}} $$

霍夫丁樹演算法使用霍夫丁界來確定在選擇分割屬性時，在節點處需要滿足高機率的最小示例數N。與大多數其他界限方程不同，霍夫丁界與機率分佈無關。這是可取的，因為可能無法知道資訊增益或使用的任何屬性選擇度量的機率分佈。

該演算法以屬性A描述的一系列訓練示例S和精度引數δ作為輸入。提供評估函式G(A_i)，它可以是資訊增益、增益率、基尼指數或其他一些屬性選擇度量。在決策樹中的每個節點處，我們需要針對剩餘屬性A_i中的一個最大化G(A_i)。目標是找到滿足霍夫丁界的最小元組數N。

該演算法以屬性A描述的一系列訓練示例S和精度引數δ作為輸入。提供評估函式G(A_i)，它可以是資訊增益、增益率、基尼指數或其他一些屬性選擇度量。在決策樹中的每個節點處，我們需要針對剩餘屬性A_i中的一個最大化G(A_i)。目標是找到滿足霍夫丁界的最小元組數N。

對於給定節點，令A_a為達到最高G的屬性，A_b為達到第二高G的屬性。如果G(A_a) − G(A_b) > ε，其中ε是計算出來的。

霍夫丁樹演算法中必須維護的唯一統計資料是屬性A_i的值v_j與類標籤y_k的計數n_ijk。因此，如果d是屬性的數量，v是任何屬性的最大值的數量，c是類的數量，l是樹的最大深度（或層數），則所需的總記憶體為O(ldvc)。

基尼係數

更新於：2021年11月25日

4K+ 瀏覽量

啟動你的職業生涯

透過完成課程獲得認證

開始學習