Natureza | Algoritmo de particionamento de dados ( d ) |
---|
O particionamento em k -means (ou k -means em inglês) é um método de particionamento de dados e um problema de otimização combinatória . Dados pontos e um inteiro k , o problema é dividir os pontos em k grupos, muitas vezes chamados de clusters , de modo a minimizar uma determinada função. Consideramos a distância de um ponto da média dos pontos de seu cluster; a função a ser minimizada é a soma dos quadrados dessas distâncias.
Existe uma heurística clássica para esse problema, freqüentemente chamada de métodos k- médias , usada para a maioria das aplicações. O problema também é estudado como um problema de otimização clássico, com, por exemplo, algoritmos de aproximação .
As k- médias são usadas em particular na aprendizagem não supervisionada, onde as observações são divididas em k partições. Os clusters dinâmicos são uma generalização do princípio para o qual cada partição é representada por um anel pode ser mais complexo do que a média. Um algoritmo clássico de k- médias é o mesmo que o algoritmo de quantização Lloyd-Max .
Dado um conjunto de pontos ( x 1 , x 2 ,…, x n ), tentamos particionar os n pontos em k conjuntos S = { S 1 , S 2 ,…, S k } ( k ≤ n ) minimizando o distância entre os pontos dentro de cada partição:
onde μ i é o baricentro dos pontos em S i .
O termo " k -means" foi usado pela primeira vez por James MacQueen em 1967, embora a ideia original tenha sido proposta por Hugo Steinhaus em 1957. O algoritmo clássico foi proposto por Stuart Lloyd em 1957 para fins de modulação por código de pulso , mas não foi lançado fora da Bell Labs antes de 1982. em 1965, EW Forgy publicou um método essencialmente semelhante, razão pela qual às vezes é chamado de "método de Lloyd Forgy". Uma versão mais eficiente, codificada em Fortran , foi publicada por Hartigan e Wong em 1975/1979.
Existe um algoritmo clássico para o problema, às vezes chamado de método k-means , amplamente utilizado na prática e considerado eficiente, embora não garanta a otimização nem o tempo de computação polinomial .
A inicialização é um fator determinante na qualidade dos resultados (mínimo local). Muitos trabalhos tratam desse ponto. Existem dois métodos de inicialização usuais: o método de Forgy de um lado e o particionamento aleatório do outro. O método de Forgy atribui os k pontos das médias iniciais a k dados de entrada escolhidos aleatoriamente. O particionamento aleatório atribui aleatoriamente um cluster para cada parte dos dados e então prossegue para o (primeiro) cálculo dos pontos médios iniciais.
K-means ++ é um algoritmo de inicialização de k pontos que propõe uma inicialização melhorando a probabilidade de obtenção da solução ótima (mínimo global). A intuição por trás dessa abordagem é distribuir os k pontos das médias iniciais. O ponto médio inicial do primeiro cluster é escolhido aleatoriamente a partir dos dados. Em seguida, cada ponto médio inicial é escolhido a partir dos pontos restantes, com uma probabilidade proporcional ao quadrado da distância entre o ponto e o cluster mais próximo.
Existe um número finito de partições possíveis com k classes. Além disso, cada etapa do algoritmo diminui estritamente a função de custo, positiva, e revela uma partição melhor. Isso permite afirmar que o algoritmo sempre converge em tempo finito, ou seja, termina.
O particionamento final nem sempre é ideal. Além disso, o tempo de cálculo pode ser exponencial no número de pontos, mesmo no plano. Na prática, é possível impor um limite ao número de iterações ou um critério de melhoria entre as iterações.
Em k fixo, a complexidade suave é polinomial para algumas configurações, incluindo pontos no espaço euclidiano e o caso da divergência de Kullback-Leibler . Se k fizer parte da entrada, a complexidade suave ainda é polinomial para o caso euclidiano. Esses resultados explicam em parte a eficiência do algoritmo na prática.
O problema das k- médias é NP-difícil no caso geral. No caso euclidiano, existe um algoritmo de aproximação polinomial, de razão 9, por busca local .
Uma possível desvantagem do k-means para particionamento é que os clusters dependem da inicialização e da distância escolhida .
O fato de ter que escolher o parâmetro k a priori pode ser percebido como uma desvantagem ou uma vantagem. No caso do cálculo da bolsa de palavras, por exemplo, é possível fixar exatamente o tamanho do dicionário desejado. Pelo contrário, em certas partições de dados , será preferível dispensar tal restrição.