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.
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.
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 2 ≥ w 3 und für alle Punkte ( b 1 , b 2 ) in B , w 1 b 1 +w1 w2 w3 (a1,a2) A w1a1+w2a2≥w3 (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<w3 w1x+w2y≥w3 A
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,w3 A B
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 ) } .w1ai1+w2ai2≥w3 i=1,..,|A| A={(a11,a12),…,(a|A|1,a|A|2)}
für jedes j = 1 , . . , | B | , wobei B = { ( b 1 1 , b 1 2 ) , … , ( b | B | 1 , b | B | 2 ) } .w1bj1+w2bj2<w3 j=1,..,|B| B={(b11,b12),…,(b|B|1,b|B|2)}
Wenn diese Einschränkungen konsistent sind, ist eine Linie vorhanden.
quelle
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
quelle