爲什麼運行時構造決策樹mnlog（n）？

Question

當m是特徵的數量，n是樣本的數量時，python scikit-learn站點（http://scikit-learn.org/stable/modules/tree.html）指出構建二叉決策樹的運行時間爲mnlog（n）。

我知道log（n）來自分裂後樹的平均高度。我明白，在每次拆分時，都必須查看每個特徵（m）並選擇最佳的拆分。我知道這是通過計算每個樣本在該節點（n）的「最佳度量」（在我的情況下，基尼雜質）完成的。但是，要找到最佳分割，這是否意味着您不得不看每種可能的方式來分割每個特徵的樣本？那不是像2^n-1 * m那樣的東西，而不僅僅是mn？我在想這個錯嗎？任何建議都會有幫助。謝謝。

Answer 1

建立一個決策樹是，在每一個點，做這樣的事情的一種方式：

• 對於每個可能的功能分割上：
  • 查找，最好的可能分裂特徵。
  • 確定這種適合的「優點」。
• 在以上嘗試的所有選項中，採取最佳措施並將其用於拆分。

問題是如何執行每一步。如果您有連續的數據，尋找最佳可能分割的常用技術是將數據按照該數據點升序排序，然後考慮這些數據點之間的所有可能的分割點並採用最小化熵的分割點。這個排序步驟需要花費時間O（n log n），這主導了運行時。由於我們正在爲每個O（m）特徵執行此操作，因此運行時最終將解決每個節點完成的總工作量O（mn log n）。