Convertendo matriz de similaridade para matriz de distância (euclidiana)

27

No algoritmo de floresta aleatória, Breiman (autor) constrói a matriz de similaridade da seguinte maneira:

  1. Envie todos os exemplos de aprendizado em cada árvore da floresta

  2. Se dois exemplos aterrissarem na mesma folha, incrementar o elemento correspondente na matriz de similaridade em 1

  3. Normalize a matriz com número de árvores

Ele diz:

As proximidades entre os casos n e k formam uma matriz {prox (n, k)}. A partir de sua definição, é fácil mostrar que essa matriz é simétrica, definida positiva e delimitada acima por 1, com os elementos diagonais iguais a 1. Segue-se que os valores 1-prox (n, k) são distâncias ao quadrado em uma distância euclidiana. espaço de dimensão não superior ao número de casos. Fonte

Em sua implementação, ele usa sqrt (1-prox) , onde prox é uma matriz de similaridade, para convertê-lo em matriz de distância. Acho que tem algo a ver com as "distâncias quadradas em um espaço euclidiano", citadas acima.

Alguém pode esclarecer um pouco por que segue que 1-prox são distâncias quadradas em um espaço euclidiano e por que ele usa a raiz quadrada para obter a matriz da distância?

Uros K
fonte

Respostas:

30

insira a descrição da imagem aqui

De acordo com o teorema do cosseno , no espaço euclidiano, a distância quadrada (euclidiana) entre dois pontos (vetores) 1 e 2 é . Comprimentos ao quadrado e são as somas das coordenadas ao quadrado dos pontos 1 e 2, respectivamente (são os hipotenus pitagóricos). A quantidade é chamada de produto escalar (= produto escalar , = produto interno) dos vetores 1 e 2.d122=h12+h222h1h2cosϕh12h22h1h2cosϕ

O produto escalar também é chamado de similaridade do tipo ângulo entre 1 e 2 e, no espaço euclidiano, é geometricamente a medida de similaridade mais válida , porque é facilmente convertida na distância euclidiana e vice-versa (veja também aqui ).

O coeficiente de covariância e a correlação de Pearson são produtos escalares. Se você centralizar seus dados multivariados (para que a origem esteja no centro da nuvem de pontos), então normalizados são as variações dos vetores (não das variáveis ​​X e Y na foto acima), enquanto para dados centralizados é Pearson ; portanto, um produto escalar é a covariância. [Uma nota lateral. Se você está pensando agora em covariância / correlação entre variáveis , não pontos de dados, pode perguntar se é possível desenhar variáveis ​​para serem vetores como na foto acima. Sim, é possível, é chamado " espaço de assuntoh2cosϕrσ1σ2r12"forma de representação. O teorema do cosseno permanece verdadeiro, independentemente do que é considerado como" vetor "nesta instância - pontos de dados ou características de dados.]

Sempre que tivermos uma matriz de similaridade com 1 na diagonal - ou seja, com todos os definidos como 1, e acreditarmos / esperamos que a similaridade seja um produto escalar euclidiano , podemos convertê-la para a distância euclidiana quadrada se precisa (por exemplo, para fazer esse agrupamento ou MDS que requer distâncias e desejavelmente euclidianas). Pois, pelo que se segue da fórmula do teorema do cosseno acima, é ao quadrado euclidiano . Obviamente, você pode eliminar o fator se sua análise não precisar e converter pela fórmulahsd2=2(1s)d2d2=1s. Como exemplo frequentemente encontrado, essas fórmulas são usadas para converter Pearson em distância euclidiana. (Veja também este e todo o tópico questionando algumas fórmulas para converter em uma distância.)rr

Logo acima, eu disse se "acreditamos / esperamos isso ...". Você pode verificar e ter certeza de que a semelhança matriz - a um particular na mão - é geometricamente "OK" matriz produto escalar se a matriz não tem valores próprios negativos. Mas se os tiver, significa que não são produtos escalares verdadeiros, pois há algum grau de não convergência geométrica nos ou nos que "se escondem" atrás da matriz. Existem maneiras de tentar "curar" essa matriz antes de transformá-la em distâncias euclidianas.sshd

ttnphns
fonte