Calcular y representar gráficamente el límite de decisión LDA

Question

He visto un gráfico LDA (análisis discriminante lineal) con límites de decisión de Los elementos del aprendizaje estadístico :

Entiendo que los datos se proyectan en un subespacio de dimensiones inferiores. Sin embargo, me gustaría saber cómo se obtienen los límites de decisión en la dimensión original de forma que pueda proyectar los límites de decisión en un subespacio de dimensión inferior (como las líneas negras de la imagen anterior).

¿Existe alguna fórmula que me permita calcular los límites de decisión en la dimensión original (superior)? En caso afirmativo, ¿qué datos de entrada necesita esta fórmula?

Answer 1

Esta figura concreta de Hastie et al. se elaboró sin calcular ecuaciones de límites de clase. En su lugar, se utilizó el algoritmo descrito por @ttnphns en los comentarios, véase la nota a pie de página 2 de la sección 4.3, página 110:

Para esta figura y muchas otras similares del libro, calculamos los límites de decisión mediante un método de contorno exhaustivo. Calculamos la regla de decisión en un entramado fino de puntos y, a continuación, utilizamos algoritmos de contorneado para calcular los límites.

Sin embargo, procederé a describir cómo obtener ecuaciones de límites de clase LDA.

Empecemos con un ejemplo sencillo en 2D. Aquí están los datos del Conjunto de datos Iris descarto las medidas de los pétalos y sólo considero la longitud y la anchura de los sépalos. Las tres clases están marcadas con colores rojo, verde y azul:

Denotemos las medias de las clases (centroides) como $\boldsymbol\mu_1, \boldsymbol\mu_2, \boldsymbol\mu_3$ . LDA asume que todas las clases tienen la misma covarianza dentro de la clase; dados los datos, esta matriz de covarianza compartida se estima (hasta el escalado) como $\mathbf{W} = \sum_i (\mathbf{x}_i-\boldsymbol \mu_k)(\mathbf{x}_i-\boldsymbol \mu_k)^\top$ donde la suma es sobre todos los puntos de datos y el centroide de la clase respectiva se resta de cada punto.

Para cada par de clases (por ejemplo, clase $1$ y $2$ ) hay un límite de clase entre ellos. Es obvio que la frontera tiene que pasar por el punto medio entre los dos centroides de clase $(\boldsymbol \mu_{1} + \boldsymbol \mu_{2})/2$ . Uno de los resultados centrales de LDA es que este límite es una línea recta ortogonal a $\mathbf{W}^{-1} \boldsymbol (\boldsymbol \mu_{1} - \boldsymbol \mu_{2})$ . Hay varias formas de obtener este resultado y, aunque no formaba parte de la pregunta, en el Apéndice que figura a continuación haré una breve alusión a tres de ellas.

Tenga en cuenta que lo escrito anteriormente es ya una especificación precisa del límite. Si se quiere tener una ecuación de línea en la forma estándar $y=ax+b$ entonces los coeficientes $a$ y $b$ puede calcularse y vendrá dada por algunas fórmulas confusas. Me cuesta imaginar una situación en la que esto sea necesario.

Apliquemos ahora esta fórmula al ejemplo del Iris. Para cada par de clases, busco un punto medio y trazo una línea perpendicular a $\mathbf{W}^{-1} \boldsymbol (\boldsymbol \mu_{i} - \boldsymbol \mu_{j})$ :

Tres líneas se cruzan en un punto, como era de esperar. Los límites de decisión vienen dados por rayos que parten del punto de intersección:

Tenga en cuenta que si el número de clases es $K\gg 2$ entonces habrá $K(K-1)/2$ pares de clases y así un montón de líneas, todas cruzándose en un lío enmarañado. Para dibujar un cuadro bonito como el de Hastie et al., hay que conservar sólo los segmentos necesarios, y es un problema algorítmico aparte en sí mismo (no relacionado con el LDA en modo alguno, porque no se necesita para hacer la clasificación; para clasificar un punto, o bien se comprueba la distancia de Mahalanobis a cada clase y se elige la que tenga la distancia más baja, o bien se utiliza una serie o LDA por pares).

En $D>2$ dimensiones la fórmula se mantiene exactamente lo mismo El límite es ortogonal a $\mathbf{W}^{-1} \boldsymbol (\boldsymbol \mu_{1} - \boldsymbol \mu_{2})$ y pasa por $(\boldsymbol \mu_{1} + \boldsymbol \mu_{2})/2$ . Sin embargo, en dimensiones superiores ya no se trata de una línea, sino de un hiperplano de $D-1$ dimensiones. A efectos ilustrativos, se puede simplemente proyectar el conjunto de datos a los dos primeros ejes discriminantes, y reducir así el problema al caso 2D (creo que eso es lo que hicieron Hastie et al. para producir esa figura).

Anexo

Cómo ver que el límite es una recta ortogonal a $\mathbf{W}^{-1} (\boldsymbol \mu_{1} - \boldsymbol \mu_{2})$ ? He aquí varias formas posibles de obtener este resultado:

1. La manera elegante: $\mathbf{W}^{-1}$ induce la métrica de Mahalanobis en el plano; el límite tiene que ser ortogonal a $\boldsymbol \mu_{1} - \boldsymbol \mu_{2}$ en esta métrica, QED.

2. La forma gaussiana estándar: si ambas clases están descritas por distribuciones gaussianas, entonces la probabilidad logarítmica de que un punto $\mathbf x$ pertenece a la clase $k$ es proporcional a $(\mathbf x - \boldsymbol \mu_k)^\top \mathbf W^{-1}(\mathbf x - \boldsymbol \mu_k)$ . En la frontera, las probabilidades de pertenecer a las clases $1$ y $2$ son iguales; escríbalo, simplifique y llegará inmediatamente a $\mathbf x^\top \mathbf W^{-1} (\boldsymbol \mu_{1} - \boldsymbol \mu_{2}) = \mathrm{const}$ QED.

3. La manera laboriosa pero intuitiva. Imagina que $\mathbf{W}$ es una matriz de identidad, es decir, todas las clases son esféricas. Entonces la solución es obvia: la frontera es simplemente ortogonal a $\boldsymbol \mu_1 - \boldsymbol \mu_2$ . Si las clases no son esféricas, se pueden convertir en tales esferificándolas. Si la descomposición propia de $\mathbf{W}$ es $\mathbf{W} = \mathbf U \mathbf D \mathbf U^\top$ entonces matriz $\mathbf S = \mathbf D^{-1/2} \mathbf U^\top$ (véase por ejemplo aquí ). Así que después de aplicar $\mathbf S$ el límite es ortogonal a $\mathbf S (\boldsymbol \mu_{1} - \boldsymbol \mu_{2})$ . Si tomamos este límite, lo transformamos de nuevo con $\mathbf S^{-1}$ y preguntar a qué es ortogonal ahora, la respuesta (dejada como ejercicio) es: a $\mathbf S^\top \mathbf S \boldsymbol (\boldsymbol \mu_{1} - \boldsymbol \mu_{2})$ . Introduciendo la expresión para $\mathbf S$ obtenemos QED.

Answer 2

¡Quiero empezar dando las gracias a @amoeba dice Reinstate Monica & ttnphns por sus contribuciones que me han ayudado mucho! Estoy tan agradecido de hecho, que me gustaría invitarles a una copa o poder devolverles el favor de alguna manera.

Lo único que voy a añadir a su respuesta es mi implementación python de dibujar estos límites Decisión, creo que va a ayudar a los demás, la teoría y la visión es grande, pero algunos entienden mejor a través de código.

El código de abajo es útil para la visualización, he utilizado LDA para la reducción de la dimensionalidad (10 000 dim a 2D) para 3 clases. El framework es sklearn. Solo el código para graficar la DB está escrito abajo, si estás interesado en la parte de entrenamiento del clasificador, la documentación de sci-kit learn es MUY buena. El código de abajo asume que has proyectado tus datos de entrenamiento a 2D y que has calculado sus medias.

x_min, x_max = plt.xlim()
# xplot = np.linspace(x_min, x_max, 100) #to plot the whole lines and find the intersection
#x_l1 and x_l2 to only plot the relevant part of the lines [found the intersection by first plotting the data]
x_l1 = np.linspace(x_min, 0.272, 100)
x_l2 = np.linspace(0.272, x_max, 100)

cov = lda1_2features.covariance_
prec_m = np.linalg.inv(cov)    

line1 = np.dot(prec_m, (mu1[0]-mu1[1]).T)#mu1 contains the coordinates of all the
# classes [in this example 3 classes)
midpoint1 = (mu1[1]+mu1[0])/2
plt.plot(midpoint1[0], midpoint1[1],
        'p', color='magenta', markersize=10, markeredgecolor='grey')
rico1 = -line1[0]/line1[1]
cte1 = midpoint1[1]-(rico1)*midpoint1[0]
# plt.plot(xplot, (rico1*xplot)+cte1, '--b')
plt.plot(x_l1, (rico1*x_l1)+cte1, '--b')

line2 = np.dot(prec_m, (mu1[0]-mu1[2]).T)
midpoint2 = (mu1[2]+mu1[0])/2
plt.plot(midpoint2[0], midpoint2[1],
        'p', color='magenta', markersize=10, markeredgecolor='grey')
rico2 = -line2[0]/line2[1]
cte2 = midpoint2[1]-(rico2)*midpoint2[0]
# plt.plot(xplot, (rico2*xplot)+cte2, '--r')
plt.plot(x_l2, (rico2*x_l2)+cte2, '--r')

line3 = np.dot(prec_m, (mu1[1]-mu1[2]).T)
midpoint3 = (mu1[2]+mu1[1])/2
plt.plot(midpoint3[0], midpoint3[1],
        'p', color='magenta', markersize=10, markeredgecolor='grey')
rico3 = -line3[0]/line3[1]
cte3 = midpoint3[1]-(rico3)*midpoint3[0]
# plt.plot(xplot, (rico3*xplot)+cte3, '--g')
plt.plot(x_l1, (rico3*x_l1)+cte3, '--g')
plt.show()

Subespacio 2D del clasificador I con límites de Decisión, centros de clase (estrella amarilla), cov_ellispses y puntos medios (pentágonos) trazados en una figura usando matplotlib].

Fuentes;

scikit_lda_qda

scikit_lda