Gibt es eine Möglichkeit, die lineare Separierbarkeit eines Datasets mit zwei Klassen in hohen Dimensionen zu testen? Meine Merkmalsvektoren sind 40 lang.
Ich weiß, dass ich jederzeit logistische Regressionsexperimente durchführen und die Hitrate im Vergleich zur Falschalarmrate bestimmen kann, um festzustellen, ob die beiden Klassen linear trennbar sind oder nicht, aber es wäre gut zu wissen, ob es dafür bereits ein Standardverfahren gibt.
Antworten:
Nun, Support Vector Machines (SVM) sind wahrscheinlich das, wonach Sie suchen. Beispiel: SVM mit einem linearen RBF-Kernel ordnet Karten einem Raum mit höheren Dimensionen zu und versucht, die Klassen durch eine lineare Hyperebene zu trennen. Dies ist ein schönes kurzes SVM-Video, das die Idee veranschaulicht.
Sie können SVM mit einer Suchmethode für die Feature-Auswahl (Wrapper-Modell) umbrechen und versuchen, festzustellen, ob eines Ihrer Features Ihre Klassen linear sparieren kann.
Es gibt viele interessante Tools für die Verwendung von SVM, einschließlich LIBSVM , MSVMPack und Scikit-learn SVM .
quelle
e1071Paketesvmmitkernel="linear"und mit der Vorhersage im Vergleich zur tatsächlichen verwenden.Die rechnerisch effektivste Methode, um zu entscheiden, ob zwei Punktmengen linear trennbar sind, ist die Anwendung der linearen Programmierung . GLTK ist perfekt für diesen Zweck und so gut wie jede Hochsprache bietet eine Benutzeroberfläche dafür - R , Python, Octave, Julia usw.
In Bezug auf die Antwort, die die Verwendung von SVMs vorschlägt :
Die Verwendung von SVMs ist aus zwei Gründen eine suboptimale Lösung zur Überprüfung der linearen Trennbarkeit:
SVMs sind Soft-Margin-Klassifikatoren. Dies bedeutet, dass sich ein linearer Kernel-SVM möglicherweise mit einer Trennebene begnügt, die nicht perfekt trennt, obwohl dies tatsächlich möglich ist. Wenn Sie dann die Fehlerrate überprüfen, wird sie nicht 0 sein und Sie werden fälschlicherweise den Schluss ziehen, dass die beiden Sätze nicht linear trennbar sind. Dieses Problem kann durch Auswahl eines sehr hohen Kostenkoeffizienten C abgeschwächt werden - dies ist jedoch mit einem sehr hohen Rechenaufwand verbunden.
SVMs sind Maximum-Margin-Klassifikatoren. Dies bedeutet, dass der Algorithmus versucht, eine Trennebene zu finden, die die beiden Klassen trennt, während er versucht, sich so weit wie möglich von beiden zu entfernen. Auch dies ist ein Merkmal, das den Rechenaufwand unnötig erhöht, da es etwas berechnet, das für die Beantwortung der Frage der linearen Trennbarkeit nicht relevant ist.
Angenommen, Sie haben eine Reihe von Punkten A und B:
Dann müssen Sie die 0 für die folgenden Bedingungen minimieren:
(Das A unten ist eine Matrix, nicht die Menge der Punkte von oben)
"Minimieren von 0" bedeutet effektiv, dass Sie eine Zielfunktion nicht wirklich optimieren müssen, da dies nicht erforderlich ist, um herauszufinden, ob die Sätze linear trennbar sind.
Am Ende definiert (
) die Trennebene.
Wenn Sie an einem Arbeitsbeispiel in R oder den mathematischen Details interessiert sind, dann überprüfen Sie dies .
quelle
Linear Perceptron wird garantiert eine Lösung finden, wenn es eine gibt. Dieser Ansatz ist für große Dimensionen nicht effizient. Die rechnerisch effektivste Methode, um zu entscheiden, ob zwei Punktmengen linear trennbar sind, ist die von @ Raffael erwähnte lineare Programmierung.
Eine schnelle Lösung wäre, ein Perzeptron zu lösen. Ein Code mit einem Beispiel zur Lösung mit Perceptron in Matlab finden Sie hier
quelle