algorithm - teoria - Determine si las dos clases son linealmente separables(algorítmicamente en 2D)
svm multiclase (8)
Hay dos clases, llamémoslas X y O. Un número de elementos que pertenecen a estas clases se extienden en el plano xy. Aquí hay un ejemplo donde las dos clases no son linealmente separables. No es posible dibujar una línea recta que divide perfectamente las X y las Os en cada lado de la línea.
¿Cómo determinar, en general, si las dos clases son linealmente separables? . Estoy interesado en un algoritmo donde no se hacen suposiciones con respecto al número de elementos o su distribución. Un algoritmo de la complejidad computacional más baja es, por supuesto, preferido.
Aquí hay un algoritmo ingenuo que estoy bastante seguro de que funcionará (y, de ser así, muestra que el problema no es NP-completo, como afirma otro post), pero no me sorprendería si pudiera hacerse de manera más eficiente: Si existe una línea de separación, será posible moverla y rotarla hasta que toque dos de las X''es o una X y una O. Por lo tanto, podemos simplemente mirar todas las líneas posibles que se intersecan con dos X''es o una X y una O, y ver si alguna de ellas son líneas divisorias. Entonces, para cada uno de los pares O (n ^ 2) , itere sobre todos los otros n-2 elementos para ver si todas las X''es están en un lado y todas las O en el otro. Complejidad del tiempo total: O (n ^ 3) .
Calcular una SVM lineal y luego determinar qué lado del plano calculado con los marginales óptimos en que se encuentra cada punto le dirá si los puntos son linealmente separables.
Esto es una exageración, pero si necesita una solución rápida, hay muchas bibliotecas SVM existentes que lo harán por usted.
Como lo menciona ElKamina, Perceptrón lineal está garantizado para encontrar una solución si existe. Este enfoque no es eficiente para grandes dimensiones. Desde el punto de vista computacional, la forma más efectiva de decidir si dos conjuntos de puntos se pueden separar linealmente es mediante la aplicación de la programación lineal.
Un código con un ejemplo para resolver usando Perceptron en Matlab está here
Desde el punto de vista computacional, la forma más efectiva de decidir si dos conjuntos de puntos se pueden separar linealmente es mediante la aplicación de la programación lineal . GLTK es perfecto para ese propósito y prácticamente todos los lenguajes de alto nivel ofrecen una interfaz para ello: R , Python, Octave, Julia, etc.
Digamos que tienes un conjunto de puntos A y B:
Luego tienes que minimizar el 0 para las siguientes condiciones:
(La A a continuación es una matriz, no el conjunto de puntos desde arriba)
"Minimizar 0" efectivamente significa que no es necesario optimizar realmente una función objetivo porque esto no es necesario para averiguar si los conjuntos son linealmente separables.
En el final ( ) está definiendo el plano de separación.
En caso de que esté interesado en un ejemplo práctico en R o en los detalles matemáticos, compruebe R .
Perceptrón lineal está garantizado para encontrar dicha separación si existe.
Probablemente pueda aplicar programación lineal a este problema. No estoy seguro de su complejidad computacional en términos formales, pero la técnica se aplica con éxito a problemas muy grandes que cubren una amplia gama de dominios.
En general, ese problema es NP-duro, pero existen buenas soluciones aproximadas como el clustering K-means .
Si encuentra el casco convexo para los puntos X y los puntos O separado (es decir, tiene dos cascos convexos separados en esta etapa), entonces solo tendrá que verificar si algún segmento de los cascos se intersectó o si el casco fue encerrado por el casco. otro.
Si se descubriera que los dos cascos están totalmente separados, los dos conjuntos de datos se podrían separar geométricamente.
Dado que los cascos son convexos por definición, cualquier separador sería una línea recta.
Hay algoritmos eficientes que se pueden usar tanto para encontrar el casco convexo (el algoritmo qhull se basa en un enfoque de casco qhull O(nlog(n)) creo), y para realizar pruebas de intersección de línea de línea para un conjunto de segmentos ( sweepline en O(nlog(n)) ), en general, parece que debería ser posible un algoritmo eficiente de O(nlog(n)) .
Este tipo de enfoque también debe generalizarse a las pruebas generales k-way separación de k-way (donde tiene k grupos de objetos) formando el casco convexo y realizando las pruebas de intersección para cada grupo.
También debería funcionar en dimensiones más altas, aunque las pruebas de intersección comenzarían a ser más desafiantes ...
Espero que esto ayude.