Original Article: K-means and KD-trees resources
Author: Dan Pelleg
Recursos K-means e KD-trees
- Read the Papel K-means (PS), or Papel K-means (PDF) .
- Nota: recentemente, um resultado similar, embora independente, foi trazido para o nosso atenção. É anterior ao nosso trabalho. Para completar, você pode ler la tambem.
- Leia o Papel X-means (PS) ou Papel X-means (PDF).
- A implementação de X-means e K-means em forma binária
agora está disponível para download! Atualmente, existem versões para
Linux, OS X e MS-Windows. Eles são distribuídos sob o seguinte
termos:
- O software pode ser usado apenas para fins experimentais e de pesquisa.
- O software não pode ser distribuído a ninguém e não pode ser vendido na totalidade ou parte de um produto de software maior, seja na fonte ou em formas binárias.
- X-means está disponível para pesquisadores na fonte. O código está no padrão C, e pode ser executado autônomo ou através de um wrapper MATLAB. É conhecido por compilar em GCC (em Linux, Cygwin, OS X, Solaris e FreeBSD) e MSVC ++.
- Além de X-means, este código também inclui suporte rápido de K-means. Ele acelerará seu aplicativo K-means, desde que:
- Os seus dados não possuem mais de 15 dimensões. Você ainda pode obter e usar o código se isso não for realizado, mas não espere que seja particularmente rápido. O código inclui uma implementação direta de K-means que não usa árvores KD.
- Você pode calcular distâncias euclidianas entre os dois pontos de dados e essa distância é significativa de alguma forma para você. Este é realmente um pré-requisito para qualquer algoritimo K-means.
- Para obter acesso, preencha os espaços em branco neste Termos de licença, e enviá-lo de volta para Dan Pelleg (sim, há um sinal de mais lá; deixe-o e as palavras antes e depois, como se fossem - funciona). Basicamente, tudo o que diz é que você não pode usar este programa comercialmente. Você pode solicitar isso - concedei cerca de 800 licenças já a pessoas em tantas instituições e estou sempre feliz por ter mais usuários. Não vou vender, alugar, dar ou usar seu endereço de e-mail para qualquer propósito além de lhe dar as instruções de download.
- Há também um K-means e X-means mailing-list.
- Além de X-means, este código também inclui suporte rápido de K-means. Ele acelerará seu aplicativo K-means, desde que:
- Abaixo, preparei um "guia de desenho animado" para K-means:
Introdução aos K-means
Aqui está um conjunto de dados em 2 dimensões com 8000 pontos. Vamos rodar 5-meios nele (K-means com K = 5). Além dos pontos, vemos K-means selecionou 5 pontos aleatórios para centros de aula. Estes são os pontos gorduroso azul, verde, vermelho, preto e roxo. Note-se que, como o acaso tem, eles não correspondem aos gaussianos subjacentes (na verdade, eu tive que coagir o programa para produzir esses pontos iniciais "ruins" - é bastante bom para obter os pontos iniciais "certo").Agora, o programa passa por pontos de dados, associando cada um ao centro de classe mais próximo. Os pontos que você vê são coloridos de acordo com o centro com o qual eles estão associados. Observe o limite azul-verde no canto superior direito. Esta linha (teórica) de pontos que são equidistantes dos centros verde e azul determina qual ponto pertence onde
O próximo passo do algoritmo é re-posicionar os centros de classe. O centro verde será colocado no centro da massa de todos os pontos verdes, e assim por diante. Como se verifica, o centro verde irá mudar para a direita e para cima. A linha preta que sai do centro verde mostra isso. Observe que os centros preto e vermelho compartilham aproximadamente metade do gaussiano à esquerda (e cerca de metade dos Gaussianos estão dentro), então ambos "correm" para a esquerda. O movimento do centro roxo é muito pequeno.
Clique na imagem para ver uma versão maior. Você pode abri-lo em uma nova janela do navegador, para que você ainda possa ler o texto.
O programa moveu os centros e re-coloriu todos os pontos de acordo com qual centro está mais próximo de cada um. Como o centro verde se moveu, o limite azul-verde passa "para fora" do gaussiano no canto superior direito. E provavelmente está em algum lugar na área despojada entre azul e verde. Queremos que esse tipo de coisa aconteça.
Ao olhar para os vetores de movimento, você pode ver o preto e o vermelho continuarão correndo para a esquerda, e o roxo agora domina uma boa parte do seu entorno. Observe o gaussiano "órfão" entre o roxo eo verde. Isso aconteceu porque o preto e o vermelho residem no mesmo gaussiano, então somos "um curto centroide".
O limite verde-púrpura muda para cima e para a direita; Parece que o verde vai possuir apenas "seus" pontos e o roxo terá dois Gaussianos. No canto inferior esquerdo, parece vermelho ter perdido a corrida para preto (o preto é mais à esquerda).
Outra iteração...
Agora, os limites azul-verde e verde-púrpura são praticamente definidos (para o que eles deveriam ser). Observe que o vermelho mudará, tão ligeiramente, para a direita.
O vermelho foi para a direita. Então ganhou mais pontos roxos. Como todos os pontos roxos estão à direita, esse efeito se intensifica. Conseqüentemente, o roxo está perdendo pontos para o vermelho, e também se move para a direita (e para cima).
Outra iteração...
E outra...
E outra...
O vermelho completou sua jornada, ganhando controle sobre um gaussiano anteriormente possuído por roxo. Black fica à posse do gaussiano inteiro à esquerda. K-means encontrou a partição "correta". Uma vez que esta é uma configuração estável, as próximas iterações não moverão demais os centros.
Introdução a KD-trees
Novamente, nosso conjunto de dados de 8000 pontos gerados aleatoriamente, a partir de uma distribuição de 5 gaussianos. Você deveria ver os Gaussianos subjacentes. O limite azul denota o nó kd "raiz". Abrange todos os pontos.
Agora veja as crianças do nó raiz. Cada um é um retângulo, com a linha de divisão paralela ao eixo Y aproximadamente a meio caminho.
Agora você vê os netos da raiz. Cada um é uma divisão de seu pai, ao longo do eixo X desta vez.
E assim por diante, dividindo em dimensões alternadas...
Aqui estão as primeiras sete camadas de KD-tree, tudo em uma imagem.
Fazer K-means rápidos com KD-trees
Todas as explicações na demo K-means acima eram verdadeiras para K-means tradicionais. "Tradicional" significa que, quando você sair e decidir qual centro é mais próximo de cada ponto (ou seja, determinar cores), você faz da maneira ingênua: para cada ponto, calcular distâncias para todos os centros e encontrar o mínimo. Nosso programa é muito mais inteligente do que isso. Primeiro constrói uma kd-tree para os pontos (o que você viu anteriormente). Agora, suponha que alguns kd-node sejam inteiramente propriedade de algum centro. Isso significa que o próximo movimento do centro será afetado pelo centro de massa dos pontos nesse nó kd (e seu número). Assim, ao pré-calcular o centro de massa de cada nodo kd, e armazená-lo no nó, podemos economizar muito trabalho. [mostrar que algum nó é inteiramente de propriedade de um centro também pode ser feito de forma eficiente - veja o papel K-means rápido].Este tipo de computação rápida tem acontecido nos bastidores ao longo da demo. Sempre que um nó provou ser totalmente de propriedade de um centro, o programa desenhou o retângulo desse nodo. Para fins de visualização, também desenhou os pontos dentro dele, mas um programa "real" não precisa fazer isso. Ele apenas usa um número muito pequeno de operações aritméticas para calcular o efeito que um certo nodo kd terá. Isso se opõe a somar as coordenadas de cada ponto dentro desse retângulo, ou seja, um custo linear no número de pontos no retângulo.
Observe o quão fácil foi calcular os centros de massa pretos e azuis. O preto pegou apenas dois nós, e cerca de 50 pontos individuais adicionais. O azul levou 5 nós, mais cerca de 10 pontos. Compare isso com aproximadamente 8000/5 = 1600 pontos cada um (e fazendo 5 distâncias para cada um)!
Outra coisa interessante a notar é como esses retângulos ficam menores à medida que nos aproximamos da linha de fronteira teórica de que falamos anteriormente. Observe o limite vermelho-púrpura. À medida que nos aproximamos, é mais difícil e difícil para os nós grandes e gordurosos ser inteiramente de propriedade do vermelho ou do roxo. Se você pensa sobre isso, eles não podem ser de propriedade inteira de nenhum dos centros, se esse limite os atravessar. Assim, quanto mais chegarmos ao limite, menores os retângulos. E são praticamente pontos individuais muito próximos do limite.
Mantido por Dan Pelleg.
Este material é baseado no trabalho apoiado pela National Science Foundation sob Grant No. 0121671.