Классификаторы машинного обучения Big-O или сложности

14

Чтобы оценить производительность нового алгоритма классификатора, я пытаюсь сравнить точность и сложность (большое в обучении и классификации). Из машинного обучения: обзор Я получаю полный список контролируемых классификаторов, а также таблицу точности между алгоритмами и 44 задачи тестирования из репозитория данных UCI . Тем не менее, я не могу найти обзор, бумагу или веб-сайт с Big-O для общих классификаторов, таких как:

  • C4.5
  • РИППЕР (я думаю, что это может быть невозможно, но кто знает)
  • ANN с обратным распространением
  • Наивный байесовский
  • K-NN
  • SVM

Если у кого-нибудь есть выражение для этих классификаторов, это будет очень полезно, спасибо.

Dinl
источник
2
Вы можете быть заинтересованы в следующей статье: thekerneltrip.com/machine/learning/… Полный отказ от ответственности, это мой блог :)
RUser4512
Не хочешь отследить места, на которые сейчас указывают мертвые ссылки вопроса?
Мэтт
@ RUser4512 действительно отличный блог! Вы также решили добавить сложность пространства?
Мэтт
1
@matt Спасибо :) да, но, вероятно, в другой статье, есть много вещей, чтобы сказать об этом!
RUser4512

Ответы:

11

Ndc

Тогда обучение имеет сложности:

  1. O(Nd)di
  2. kO(1)O(Nd)
  3. O(N2)O(N3)O(N3)O(N2.3)
  4. O(NR)

Сложности тестирования:

  1. O(cd)dc
  2. kO(Nd)

Источник: «Основные векторные машины: быстрое обучение SVM по очень большим наборам данных» - http://machinelearning.wustl.edu/mlpapers/paper_files/TsangKC05.pdf

Извините, я не знаю о других.

samthebest
источник
6
O(n2)O(n3)
@MarcClaesen Ссылка больше не работает, и она не на обратном пути. Это тот же документ: leon.bottou.org/publications/pdf/lin-2006.pdf ?
словами