Die Linie trennt zwei Punktmengen

19

Gibt es eine Möglichkeit, festzustellen, ob zwei Punktmengen durch eine Linie getrennt werden können?

Wir haben zwei Sätze von Punkten und wenn es eine Linie gibt, die und so trennt, dass alle Punkte von und nur auf der einen Seite der Linie und alle Punkte von und nur auf der anderen Seite.ABABAABB

Der naivste Algorithmus, den ich mir ausgedacht habe, besteht darin, ein konvexes Polygon für und erstellen und es auf Schnittmenge zu testen. Es sieht so aus, als ob die Zeitkomplexität dafür wie für die Konstruktion eines konvexen Polygons. Eigentlich erwarte ich keine Verbesserung der Zeitkomplexität, ich bin nicht sicher, ob es überhaupt verbessert werden kann. Aber zumindest sollte es eine schönere Möglichkeit geben, festzustellen, ob es eine solche Linie gibt.ABO(nlogh)

com
quelle

Antworten:

19

Sowohl uli als auch Dave Clarke stellen zu Recht fest, dass dies ein lineares Programmierproblem ist, auch in höheren Dimensionen (Können diese beiden Punktmengen durch eine Hyperebene getrennt werden?) Und daher in polynomieller Zeit gelöst werden können. Aber weil Ihre Punkte in der Ebene liegen, kann Ihr Problem tatsächlich in Zeit gelöst werden, wobei n die Gesamtzahl der Punkte ist.O(n)n

Die einfachste Lösung ist wahrscheinlich Seidels randomisierter Algorithmus. Wählen Sie einen Eingabepunkt gleichmäßig zufällig und berechnen Sie rekursiv eine Trennlinie für alle Punkte mit Ausnahme von p .p p

  • Wenn keine solche Linie existiert, sind die ursprünglichen Punkte nicht trennbar.

  • Befindet sich auf der richtigen Seite von , trennt die ursprünglichen Punkte.p

  • Befindet sich auf der falschen Seite von , können entweder die ursprünglichen Punkte durch eine Linie durch p getrennt werden , oder die ursprünglichen Punkte sind überhaupt nicht trennbar. Diese Bedingung ist leicht in O ( n ) Zeit [Übung] zu überprüfen .ppO(n)

Dieser Algorithmus läuft mit hoher Wahrscheinlichkeit (in Bezug auf die Zufallsauswahl des Algorithmus ) in -Zeit. Weitere Informationen finden Sie in der Originalarbeit oder in den Online-Vorlesungsunterlagen.O(n)

JeffE
quelle
Vielen Dank, ich werde mich mit diesem Papier befassen.
com
In Ihrem dritten Fall geben Sie an, dass es so sein könnte, dass die Linie durch verläuft. Wie hilft es, das zu wissen? p
Tarrasch
10

Die Eigenschaft Ihrer zwei Datensätze ist die der linearen Trennbarkeit , einfach, dass es eine Linie gibt, die sie trennt. Beim maschinellen Lernen wird viel Wert darauf gelegt, lineare Klassifikatoren zu finden. Hierbei handelt es sich um Linien, die die gewünschte Trennung durchführen.

Wenn Sie über Linien sprechen, gehe ich davon aus, dass Ihre Punkte in der Ebene liegen. Was Sie tun möchten, ist, Werte , w 2 und w 3 zu finden , so dass für alle Punkte ( a 1 , a 2 ) in Menge A , w 1, a 1 + w 2, a 2w 3 und für alle Punkte ( b 1 , b 2 ) in B , w 1 b 1 +w1w2w3(a1,a2)Aw1a1+w2a2w3(b1,b2)B . Somit kann die Ungleichung w 1 x + w 2 y w 3 als ein Klassifikator für die Menge A angesehen werden .w1b1+w2b2<w3w1x+w2yw3A

Es gibt eine Vielzahl von Algorithmen für maschinelles Lernen zur Bestimmung einer optimalen Linie (lineare Regression, logistische Regression usw.). Diese finden Werte für basierend auf einer Fehlermetrik. Dann können Sie testen, ob alle Punkte korrekt klassifiziert sind. Das heißt, ob alle Werte in A die Gleichung oben und in ähnlicher Weise für B .w1,w2,w3AB

Da Sie nur daran interessiert sind, ob eine solche Linie existiert, müssen Sie vorhandene Techniken verwenden (obwohl dies wahrscheinlich einfacher wäre). Stellen Sie einfach die folgende Gleichheitssammlung in Bezug auf die freien Variablen .w1,w2,w3

für jedes i = 1 , . . , | A | , wobei A = { ( a 1 1 , a 1 2 ) , , ( a | A | 1 , a | A | 2 ) } .w1a1i+w2a2iw3i=1,..,|A|A={(a11,a21),,(a1|A|,a2|A|)}

für jedes j = 1 , . . , | B | , wobei B = { ( b 1 1 , b 1 2 ) , , ( b | B | 1 , b | B | 2 ) } .w1b1j+w2b2j<w3j=1,..,|B|B={(b11,b21),,(b1|B|,b2|B|)}

Wenn diese Einschränkungen konsistent sind, ist eine Linie vorhanden.

Dave Clarke
quelle
5

Wenn ich mich erinnere, unterstütze ich Vektormaschinen, die separate Hyperebenen konstruieren. Wenn Sie Dimension wählen, wird die Hyperebene natürlich zu einer Linie. Möglicherweise müssen Sie prüfen, ob weitere Annahmen zu erfüllen sind. In zwei Dimensionen kann sich der gesamte Ansatz erheblich vereinfachen, sodass die Laufzeit möglicherweise besser ist als beim allgemeinen Ansatz.2

uli
quelle