Prueba para una separabilidad lineal

Question

Es allí una manera a prueba de separabilidad lineal de las dos de la clase de conjunto de datos en altas dimensiones? Mi función de los vectores de 40 de largo.

Sé que siempre puedo ejecutar la regresión logística experimentos y determinar hitrate vs tasa de falsas alarmas para concluir si las dos clases son linealmente separables o no, pero sería bueno saber si ya existe un procedimiento estándar para hacer eso.

Answer 1

De cómputo de la manera más eficaz para decidir si dos conjuntos de puntos son linealmente separables, es mediante la aplicación de la programación lineal. GLTK es perfecto para ese propósito y prácticamente todos los de alto nivel de idiomas ofrece una interfaz para se - R, Python, Octave, Julia, etc.

Con respecto a la respuesta que sugiere el uso de la SVMs:

El uso de SVMs es un sub-óptima solución para la verificación de una separabilidad lineal por dos razones:

1. SVMs son blandos margen de los clasificadores. Eso significa que un kernel lineal SVM podría conformarse con una separación de plano que es no separar a la perfección a pesar de que podría ser realmente posible. Si a continuación, comprobar la tasa de error va a ser que no de 0 y falsamente a la conclusión de que los dos conjuntos no son linealmente separables. Este problema puede ser atenuada por la elección de un costo muy elevado coeficiente C - pero esto viene de sí mismo en un muy alto coste computacional.

2. SVMs son de máxima margen de los clasificadores. Esto significa que el algoritmo intentará buscar una separación de plano que es la separación de las dos clases, mientras que tratando de mantenerse alejado como sea posible. Nuevamente, esta es una característica de aumentar el esfuerzo computacional innecesariamente como se calcula algo que no es relevante para responder a la pregunta de una separabilidad lineal.

---

Digamos que usted tiene un conjunto de puntos de a y B:

Entonces usted tiene que minimizar el 0 para las siguientes condiciones:

(La siguiente es una matriz, no el conjunto de puntos de la anterior)

"Minimizar 0" significa que usted no necesita para optimizar una función objetivo, porque esto no es necesario averiguar si los conjuntos son linealmente separables.

En la final () es la definición de la separación de avión.

---

En caso de que usted está interesado en un ejemplo de trabajo en R o de las matemáticas detalles, a continuación, compruebe esto hacia fuera.

Answer 2

Bien, máquinas de soporte vectorial (SVM) son, probablemente, lo que usted está buscando. Por ejemplo, SVM lineal de kernel RBF, la función de mapas para una mayor dimenional espacio e intenta separet las clases por una lineal hyperplane. Este es un bonito corto SVM vídeo que ilustra la idea.

Usted puede envolver SVM con un método de búsqueda para la selección de características (modelo de contenedor) y probar a ver si alguna de sus características puede linealmente sparate las clases que tienen.

Hay muchas herramientas interesantes para el uso de la SVM, incluyendo LIBSVM, MSVMPack y Scikit-learn SVM.

Answer 3

Lineal de tipo perceptrón está garantizado para encontrar una solución, si existe. Este enfoque no es eficiente para grandes dimensiones. De cómputo de la manera más eficaz para decidir si dos conjuntos de puntos son linealmente separables, es mediante la aplicación de la programación lineal como se ha mencionado por @Raffael.

Una solución rápida sería la de resolver un tipo perceptrón. Un código con un ejemplo para resolver el uso de tipo perceptrón en Matlab es aquí