¿Si hay una manera de identificar si dos conjuntos de puntos se pueden separar por una línea?
Tenemos dos conjuntos de puntos y B si hay una línea que separa A y B de manera que todos los puntos de A y solo A en un lado de la línea, y todos los puntos de B y solo B en el otro lado.
El algoritmo más ingenuo que se me ocurrió es construir un polígono convexo para y B y probar su intersección. Parece que la complejidad del tiempo para esto debería ser O ( n log h ) como para construir un polígono convexo. En realidad, no espero ninguna mejora en la complejidad del tiempo, no estoy seguro de que pueda mejorarse en absoluto. Pero al menos debería haber una forma más hermosa de determinar si existe tal línea.
La propiedad de sus dos conjuntos de datos es la de la separabilidad lineal , simplemente, que hay una línea que los separa. Se dedica mucho aprendizaje automático a encontrar clasificadores lineales , que son líneas que realizan la separación que le interesa.
Mientras habla de líneas, supondré que sus puntos se encuentran en el plano. Lo que se quiere hacer es encontrar los valores de , w 2 y W 3 , de tal manera que para todos los puntos ( un 1 , un 2 ) en el conjunto A , W 1 a 1 + w 2 a 2 ≥ w 3 y para todos los puntos ( b 1 , b 2 ) en B , w 1 b 1 +w1 w2 w3 (a1,a2) A w1a1+w2a2≥w3 (b1,b2) B . Así, la desigualdad w 1 x + w 2 y ≥ w 3 puede ser visto como un clasificador para el grupo A .w1b1+w2b2<w3 w1x+w2y≥w3 A
Existen muchos algoritmos de aprendizaje automático para determinar una línea óptima (regresión lineal, regresión logística, etc.). Estos encontrarán valores para basados en alguna métrica de error. Luego puede probar si todos los puntos están clasificados correctamente. Es decir, si todos los valores en A satisfacer la ecuación de arriba y de manera similar para B .w1,w2,w3 A B
Si estas restricciones son consistentes, entonces existe una línea.
fuente
fuente