python kmeans

python-kmeans

implementação python de cluster k-means. k-means é uma técnica de aprendizagem não supervisionada que tenta agrupar pontos de dados semelhantes em um número de grupos especificado pelo usuário. O exemplo abaixo mostra a progressão de clusters para o conjunto de dados Iris usando o algoritmo de inicialização centróide k-means++.

Descrição

k-means tenta identificar um número k(<N) de clusters especificado pelo usuário a partir de um conjunto de N vetores de valor real d-dimensionais. O algoritmo prossegue tentando minimizar a soma dos quadrados das distâncias do centro do cluster até os membros do cluster. O algoritmo canônico prossegue em três fases:

1. Inicialize k centróides aleatórios (centros de cluster);
2. atribuir pontos de dados ao cluster mais próximo de acordo com a métrica de distância (normalmente distância euclidiana);
3. atualizar os centróides para a média dos membros do cluster;
4. repita as etapas 2 e 3 até que as atribuições da etapa 2 não mudem.

A saída do algoritmo é uma atribuição de cluster para cada ponto de dados e um nível final de “distorção”. O algoritmo não produz uma solução comprovadamente ótima, e os centros iniciais do cluster podem fazer com que o algoritmo fique preso em uma solução localmente ótima que é claramente abaixo do ideal (veja o exemplo 2d básico na seção Resultados).

Muitas pesquisas se concentraram em:

• selecionando centros de cluster iniciais. K-Means++ é um método bem conhecido e está incluído nesta implementação. O algoritmo é descrito na subseção a seguir.
• computando distâncias, ou seja, usando outras medidas além da euclidiana, veja aqui.

K-Means++

Em vez de inicializar centróides aleatórios como na etapa 1 acima, k-means++ espalha probabilisticamente os centróides iniciais para evitar uma configuração inicial ruim, o algoritmo é:

1. Escolha o primeiro centróide aleatoriamente.
2. Para cada ponto de dados x, calcule a distância d(x), de x ao centróide mais próximo que já foi escolhido.
3. Selecione um ponto de dados para ser o próximo centróide usando uma probabilidade ponderada proporcional a d(x)2.

Esta técnica favorece pontos de dados que não estão próximos de outros centróides iniciais e usa uma política de seleção que lembra a seleção por roda de roleta (ou proporcional à aptidão), frequentemente usada em algoritmos genéticos.

Recursos

Algoritmo Básico

• K-Means é descrito em 10 principais algoritmos para mineração de dados;

• K-Means é descrito em Teoria da Informação, Inferência e Algoritmos de Aprendizagem, trecho aqui;

• O professor Andrew Moore, da CMU, tem algumas boas notas aqui;

• Exemplo Edureka, usando dados criminais

Inicialização de Clusters

• K-Means++ e artigo completo aqui

• Um estudo comparativo de métodos de inicialização eficientes para o algoritmo de agrupamento K-Means

Por que não usar o SciPy?

SciPy tem uma implementação k-means. O objetivo deste trabalho é construir uma implementação python pura para fins de aprendizagem e ajudar outros a aprender o algoritmo k-means. Leitores interessados ​​com experiência mínima em python serão capazes de ler e passar por esse código sem a complexidade adicional de uma biblioteca como a SciPy. Não se destina de forma alguma ao uso em produção :)

Executando o código

Dependências

• píton 3.6.3
• matplotlib 2.1.1 - veja aqui para obter instruções de instalação.

Execução

Execute o código com o interpretador python:

python kmeans.py ./resources/<config.cfg>

Onde config.cfg é um arquivo de configuração de texto simples. O formato do arquivo de configuração é um ditado python com os seguintes campos:

 {
   'data_file' : '\resources\iris.csv',
   'data_project_columns' : ['sepal_length','sepal_width','petal_length','petal_width','class'],
   'k' : 3,
   'cluster_atts' : ['sepal_length','sepal_width','petal_length','petal_width'],
   'init_cluster_func' : 'kmeans_plus_plus',
   'plot_config' :
    {'output_file_prefix' : 'iris',
     'plots_configs': [
        {'plot_atts' : ['sepal_length','sepal_width']},
        {'plot_atts' : ['sepal_length','petal_length']},
        {'plot_atts' : ['sepal_length','petal_width']},
        {'plot_atts' : ['sepal_width','petal_length']},
        {'plot_atts' : ['sepal_width','petal_width']},
        {'plot_atts' : ['sepal_width','petal_width']}
     ]
   }
}

Você deve especificar:

• um arquivo de dados csv;
• um subconjunto de campos para projetar do arquivo;
• o número de clusters a formar, k;
• o subconjunto de atributos utilizados no processo de clusterização;
• opcionalmente, especifique uma função de cluster inicial (default='rand_init_centroids'), os autores interessados ​​podem adicionar sua própria função ao código e especificá-la aqui;
• uma configuração de plotagem que inclui
  • prefixo para arquivos png criados durante o processo no diretório de trabalho, se não for especificado, as imagens não serão produzidas;
  • as configurações individuais de parcela, limitadas a 2 dimensões por parcela.

Resultados

Conjunto de dados da íris

O conjunto de dados Iris (iris.config), de Lichman, M. (2013). Repositório de aprendizado de máquina UCI. Irvine, CA: University of California, School of Information and Computer Science., é um conjunto de dados muito conhecido na comunidade de aprendizado de máquina. Aqui estão os resultados dos meus clusters iniciais aleatórios:

Dados 2D sintéticos básicos

Esses dados foram gerados para fins de depuração (consulte basic2d.config) e ilustram o efeito de uma escolha inadequada de clusters aleatórios iniciais. Os resultados abaixo demonstram uma configuração centróide inicial que impede o algoritmo de atingir a atribuição óbvia do cluster. Neste caso, a colocação do centróide vermelho significa que o centróide azul captura todos os pontos de dados nos quadrantes inferior esquerdo e inferior direito.

Crime

O conjunto de dados criminais (crime.config) é de Edureka, aqui.