Maschinelles Lernen Klassifikatoren Big-O oder Komplexität

14

Um die Leistung eines neuen Klassifikator-Algorithmus zu bewerten, versuche ich, die Genauigkeit und die Komplexität (Big-O in Training und Klassifizierung) zu vergleichen. Aus dem maschinellen Lernen: Nach einer Überprüfung erhalte ich eine vollständige Liste der überwachten Klassifizierer, außerdem eine Genauigkeitstabelle zwischen den Algorithmen und 44 Testprobleme aus dem UCI-Daten-Repository . Ich kann jedoch keine Rezension, kein Papier oder keine Website mit dem Big-O für gängige Klassifikatoren finden, z.

  • C4.5
  • RIPPER (Ich denke, das ist vielleicht nicht möglich, aber wer weiß)
  • ANN mit Rückenausbreitung
  • Naive Bayesian
  • K-NN
  • SVM

Wenn jemand einen Ausdruck für diese Klassifikatoren hat, wird er sehr nützlich sein, danke.

Dinl
quelle
2
Sie könnten an folgendem Artikel interessiert sein: thekerneltrip.com/machine/learning/… Vollständiger Haftungsausschluss, es ist mein Blog :)
RUser4512
Möchten Sie die Stellen zurückverfolgen, auf die die jetzt toten Links der Frage hingewiesen haben?
Matt
@ RUser4512 wirklich tolle Blog-Überlegung! Haben Sie darüber nachgedacht, die Komplexität des Speicherplatzes zu erhöhen?
Matt
1
@matt Danke :) ja, aber wahrscheinlich gibt es auch in einem anderen Artikel viel zu sagen!
RUser4512

Antworten:

11

Es sei = Anzahl der Trainingsbeispiele, = Dimensionalität der Merkmale und = Anzahl der Klassen.Ndc

Dann hat das Training Komplexitäten:

  1. Naive Bayes ist . Sie müssen lediglich die Häufigkeit jedes Merkmalswerts für jede Klasse berechnen .O(Nd)di
  2. k -NN ist in (einige Leute sagen sogar, dass es nicht existiert, aber die räumliche Komplexität des Trainings ist da Sie die Daten speichern müssen, was auch Zeit kostet) .O(1)O(Nd)
  3. Die nichtlineare, nicht angenäherte SVM ist je nach Kernel oder . Sie können mit einigen Tricks ein auf .O(N2)O(N3)O(N3)O(N2.3)
  4. Die ungefähre SVM ist wobei R die Anzahl der Iterationen ist.O(NR)

Komplexität testen:

  1. Naive Bayes befindet sich in da Sie Feature-Werte für jede der Klassen abrufen müssen .O(cd)dc
  2. k -NN befindet sich in da Sie den Testpunkt mit jedem Datenpunkt in Ihrer Datenbank vergleichen müssen.O(Nd)

Quelle: "Core Vector Machines: Schnelles SVM-Training für sehr große Datenmengen" - http://machinelearning.wustl.edu/mlpapers/paper_files/TsangKC05.pdf

Entschuldigung, ich weiß nichts über die anderen.

samthebest
quelle
6
O(n2)O(n3)
@MarcClaesen Der Link funktioniert nicht mehr und befindet sich nicht auf dem Wayback-Rechner. Ist dies dasselbe Papier: leon.bottou.org/publications/pdf/lin-2006.pdf ?
wordsforthewise