¿Cómo aprender los puntos dentro de un cuadrado con su límite?

Question

¿Es posible clasificar los puntos dentro de un cuadrado? es decir, si $a \le x \le b$ y $c \le y \le d$ etiqueta es $+1$ % si no $0$.

¿Es que es posible usando SVM por ejemplo?

Gracias, Zach

Answer 1

Su especificación de la plaza como tener los lados paralelos a la frontera hace que el problema relativamente sencillo, siempre y cuando no se requieran para ser escrito como una sola SVM, pero puede establecerse por algo como esto.

Uno muy simple estimación de la frontera de la plaza es para aquellos puntos que han $+1$ etiquetas simplemente tomar el máximo y el mínimo de $x$ y el mínimo y máximo de $y$. (Será demasiado pequeño, por supuesto, pero si hay un montón de puntos, no es mi mucho.)

Si luego de excluir los puntos con "$0$" de las etiquetas de la parte superior y la parte inferior de la plaza, se puede utilizar SVM o algo similar para SVM en la izquierda y la mitad derecha de la $x$'s (solo es un 1-D problema para cada lado. Fácil.)

-- así que en el lado derecho, por ejemplo, sólo se necesita el más pequeño $x$ "$0$"- etiqueta por encima de la más grande "$1$"-la etiqueta $x$), ...

(Para la siguiente aproximación de la plaza, se podría dividir la diferencia entre el mayor $1$-x y el siguiente mayor $0$-x:

Usted puede, a continuación, repita el procedimiento para la izquierda, los límites superior e inferior. Esto le da una mejor estimación de los límites que la inicial.)

Por supuesto que esto no sea exactamente en la plaza (de hecho, en este punto el algoritmo es realmente para un rectángulo con lados paralelos a los ejes), pero los 4 conjuntos de verde y rosa líneas (no mostrado) dará los límites dentro de los que se desea ajustar la plaza.

Así que a partir de ahí es una cuestión de la expansión de los lados de la azul en el "estrecho", la dirección de la casi-cuadrado rectángulo y la reducción de la "amplia" de la dirección, hasta la plaza. Tenga en cuenta que usted no reducir/ampliar los lados de manera uniforme; si quieres ser SVM-ish, tendría que hacerlo, así como para aumentar la cantidad restante "espacio de maniobra" (distancia entre el azul y el verde o el rosa, la que esté más cerca) que tiene (que es, tendría que mover el lado con la mayor brecha entre el verde y el rosa, en primer lugar, hasta llegar al tamaño de la siguiente más pequeña brecha entre el azul y el verde o rosa, a continuación, cambie ambas simultáneamente hasta llegar a la siguiente hueco más pequeño, y así sucesivamente).

(Pensando un poco más de este paso se puede hacer de forma muy sencilla.)

Por lo que algunos de procesamiento inicial ($\cal{O}(n)$) para encontrar el interior y exterior de las cajas y el rectángulo azul - esencialmente cuatro trivial "SVM"s, seguido por un simple conjunto de expansión/contracción de los cálculos para encontrar un real plaza.

Si realmente hay una plaza que separa perfectamente el "$1$" y "$0$" de los casos, que debe funcionar bastante bien y dar una buena SVM-como solución. (Si no hay separación perfecta, usted puede necesitar para adaptarse más a fondo en el fin de minimizar el error en la clasificación.)

Answer 2

SVM es un clasificador lineal que significa que sólo se puede aprender a decidir de qué lado de una línea recta los puntos deben de ir. Para hacer un cuadrado obviamente, se necesita de cuatro líneas rectas. Así que la respuesta corta es no lineal SVM no se puede aprender de un cuadrado.

Sin embargo, se puede aplicar un kernel función a los datos del mapa en una dimensión superior. Si usted elige el kernel, no podría ser de grandes dimensiones de la línea que corresponde aproximadamente a un cuadrado en la parte inferior de espacio tridimensional.

Piense en ello de esta manera. Sus puntos se encuentran en un pedazo de papel y las SVM es un par de tijeras que llega a hacer un corte recto. Desea capturar sólo los puntos en la plaza con la que un corte. Si la página es plana no se puede hacer. Si usted pellizca el papel en el medio de la plaza para que parte es elevada. se podría cortar por debajo de la pizca y con un solo corte de seleccionar los puntos.