Calcular e representar graficamente o limite de decisão da LDA

Eu vi um gráfico de análise discriminante linear (LDA) com limites de decisão de The Elements of Statistical Learning :

Entendo que os dados são projetados em um subespaço de menor dimensão. No entanto, gostaria de saber como obtemos os limites de decisão na dimensão original, para que eu possa projetar os limites de decisão em um subespaço de dimensão inferior (como as linhas pretas na imagem acima).

Existe uma fórmula que eu possa usar para calcular os limites de decisão na dimensão original (superior)? Se sim, então de que entradas essa fórmula precisa?

Esta figura em particular em Hastie et al. foi produzido sem equações computacionais de limites de classe. Em vez disso, o algoritmo descrito por @ttnphns nos comentários foi usado, consulte a nota de rodapé 2 na seção 4.3, página 110:

Para esta figura e muitas figuras semelhantes no livro, calculamos os limites da decisão por um método de contorno exaustivo. Nós calculamos a regra de decisão em uma treliça fina de pontos e, em seguida, usamos algoritmos de contorno para calcular os limites.

No entanto, continuarei descrevendo como obter equações dos limites da classe LDA.

Vamos começar com um exemplo 2D simples. Aqui estão os dados do conjunto de dados Iris ; Eu descarto as medidas das pétalas e considero apenas o comprimento e a largura das sépalas. Três classes são marcadas nas cores vermelho, verde e azul:

Denotemos meios de classe (centróides) como . A LDA assume que todas as classes têm a mesma covariância dentro da classe; dados os dados, essa matriz de covariância compartilhada é estimada (até o dimensionamento) como , onde a soma está sobre todos os pontos de dados e o centróide da respectiva classe é subtraído de cada ponto.W = ∑ i ( x i - μ k ) ( x i - μ k ) $\boldsymbol\mu_1, \boldsymbol\mu_2, \boldsymbol\mu_3$$\mathbf{W} = \sum_i (\mathbf{x}_i-\boldsymbol \mu_k)(\mathbf{x}_i-\boldsymbol \mu_k)^\top$

Para cada par de classes (por exemplo, classes e ), há um limite de classe entre elas. É óbvio que o limite deve passar pelo ponto médio entre os dois centróides da classe . Um dos resultados centrais da LDA é que esse limite é uma linha reta ortogonal a . Existem várias maneiras de obter esse resultado, e mesmo que não fizesse parte da pergunta, vou sugerir brevemente três delas no Apêndice abaixo.2 ( μ 1 + μ 2 ) / 2 W - 1 ( μ 1 - μ 2$1$$2$$(\boldsymbol \mu_{1} + \boldsymbol \mu_{2})/2$$\mathbf{W}^{-1} \boldsymbol (\boldsymbol \mu_{1} - \boldsymbol \mu_{2})$

Observe que o que está escrito acima já é uma especificação precisa do limite. Se se quer ter uma equação de linha na forma padrão , em seguida, coeficientes de e podem ser calculados e será dada por algumas fórmulas desorganizados. Mal posso imaginar uma situação em que isso seria necessário.a $y=ax+b$$a$$b$

Vamos agora aplicar esta fórmula ao exemplo Iris. Para cada par de classes, encontro um ponto do meio e planto uma linha perpendicular a :$\mathbf{W}^{-1} \boldsymbol (\boldsymbol \mu_{i} - \boldsymbol \mu_{j})$

Três linhas se cruzam em um ponto, como deveria ser esperado. Os limites de decisão são dados por raios a partir do ponto de interseção:

Observe que se o número de classes for , haverá pares de classes e muitas linhas, todas se cruzando em uma confusão emaranhada. Para desenhar uma imagem bonita como a de Hastie et al., É necessário manter apenas os segmentos necessários, e é um problema algorítmico separado em si (não relacionado ao LDA de forma alguma, porque não é necessário fazer isso) a classificação; para classificar um ponto, verifique a distância de Mahalanobis para cada classe e escolha a que tem a menor distância ou use LDAs em série ou em pares).$K\gg 2$$K(K-1)/2$

Nas dimensões a fórmula permanece exatamente a mesma : o limite é ortogonal a e passa por . No entanto, em dimensões mais altas, isso não é mais uma linha, mas um hiperplano de dimensões . Para fins de ilustração, pode-se simplesmente projetar o conjunto de dados para os dois primeiros eixos discriminantes e, assim, reduzir o problema ao caso 2D (que eu acredito que foi o que Hastie et al. Fizeram para produzir essa figura).$D>2$$\mathbf{W}^{-1} \boldsymbol (\boldsymbol \mu_{1} - \boldsymbol \mu_{2})$$(\boldsymbol \mu_{1} + \boldsymbol \mu_{2})/2$$D-1$

Apêndice

Como ver que o limite é uma linha reta ortogonal a ? Aqui estão várias maneiras possíveis de obter esse resultado:$\mathbf{W}^{-1} (\boldsymbol \mu_{1} - \boldsymbol \mu_{2})$

1. A maneira elegante: induz a métrica de Mahalanobis no avião; o limite deve ser ortogonal a nesta métrica, QED.$\mathbf{W}^{-1}$$\boldsymbol \mu_{1} - \boldsymbol \mu_{2}$

2. A maneira gaussiana padrão: se as duas classes são descritas por distribuições gaussianas, a probabilidade de log de que um ponto pertence à classe é proporcional a . No limite, as probabilidades de pertencer às classes e são iguais; escreva, simplifique e você imediatamente chegará a , QED.$\mathbf x$$k$$(\mathbf x - \boldsymbol \mu_k)^\top \mathbf W^{-1}(\mathbf x - \boldsymbol \mu_k)$$1$$2$$\mathbf x^\top \mathbf W^{-1} (\boldsymbol \mu_{1} - \boldsymbol \mu_{2}) = \mathrm{const}$

3. A maneira laboriosa, mas intuitiva. Imagine que é uma matriz de identidade, ou seja, todas as classes são esféricas. Então a solução é óbvia: o limite é simplesmente ortogonal a . Se as classes não são esféricas, pode-se fazê-las esféricas. Se a decomposição em si de for , matriz fará o truque (veja, por exemplo, aqui ). Portanto, após aplicar , o limite é ortogonal a . Se pegarmos esse limite, transforme-o novamente comμ 1 - μ 2 W W = L D L ⊤ S = D - 1 / 2 L ⊤ S S ( μ 1 - μ 2 ) S - 1 S ⊤ S ( μ 1 - μ 2 ) $\mathbf{W}$$\boldsymbol \mu_1 - \boldsymbol \mu_2$$\mathbf{W}$$\mathbf{W} = \mathbf U \mathbf D \mathbf U^\top$$\mathbf S = \mathbf D^{-1/2} \mathbf U^\top$$\mathbf S$$\mathbf S (\boldsymbol \mu_{1} - \boldsymbol \mu_{2})$$\mathbf S^{-1}$ e pergunte o que é ortogonal agora, a resposta (deixada como exercício) é: to . Conectando a expressão para , obtemos QED.$\mathbf S^\top \mathbf S \boldsymbol (\boldsymbol \mu_{1} - \boldsymbol \mu_{2})$$\mathbf S$