機器學習分類器 big-O 或複雜性

為了評估新分類器算法的性能，我試圖比較準確性和復雜性（訓練和分類中的大 O）。從Machine Learning: a review我得到了一個完整的監督分類器列表，還有一個算法之間的準確度表，以及來自UCI 數據存儲庫的 44 個測試問題。但是，對於常見的分類器，我找不到帶有 big-O 的評論、論文或網站，例如：

• C4.5
• RIPPER（我認為這可能是不可能的，但誰知道）
• 具有反向傳播的 ANN
• 樸素貝葉斯
• K-NN
• 支持向量機

如果有人對這些分類器有任何表達，那將非常有用，謝謝。

讓= 訓練樣本的數量，= 特徵的維度和=類數。

然後訓練有復雜性：

1. 樸素貝葉斯是，它需要做的就是計算每個特徵值的頻率對於每個班級。
2. -NN 在（甚至有人說不存在，但是訓練的空間複雜度是因為您需要存儲數據，這也需要時間）。
3. 非線性非近似 SVM 是或者取決於內核。你可以得到一個向下有一些技巧。
4. 近似 SVM 是其中 R 是迭代次數。

測試複雜性：

1. 樸素貝葉斯在因為你必須檢索每個特徵值類。
2. -NN 在因為您必須將測試點與數據庫中的每個數據點進行比較。

資料來源：“核心向量機：超大型數據集上的快速 SVM 訓練”- http://machinelearning.wustl.edu/mlpapers/paper_files/TsangKC05.pdf

對不起，我不知道其他人。

引用自：https://stats.stackexchange.com/questions/96995