A funcionalidade de pesquisa está em construção.
A funcionalidade de pesquisa está em construção.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

Variance-Based k-Clustering Algorithms by Voronoi Diagrams and Randomization Baseado em Variância k-Algoritmos de agrupamento por diagramas de Voronoi e randomização

Mary INABA, Naoki KATOH, Hiroshi IMAI

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

Neste artigo consideramos o k-problema de clustering para um conjunto S of n pontos pi=(xi) Na despaço tridimensional com erros baseados em variância como critérios de agrupamento, motivado a partir do problema de quantização de cores de calcular uma tabela de consulta de cores para exibição de buffer de quadros. Como critério intercluster a ser minimizado, é usada a soma dos erros intra-cluster em cada cluster, e como critério intra-cluster de um cluster Sj|Sj|α-1 Σpi Sj ||xi - - x (Sj)||2 é considerado, onde |||| é o L2 norma e - x (Sj) é o centróide dos pontos em Sj, ou seja, (1/|Sj|)Σpi Sj xi. Os casos de α=1,2 correspondem à soma dos erros quadráticos e à soma dos erros quadráticos de todos os pares, respectivamente. O k-problemas de agrupamento sob o critério com α = 1,2 são tratados de forma unificada, caracterizando a solução ótima para o k-problema de agrupamento pelo diagrama euclidiano de Voronoi ordinário e pelo diagrama de Voronoi ponderado com pesos multiplicativos e aditivos. Com esta estrutura, o problema está relacionado à função de quebra primária generalizada para os diagramas de Voronoi. A função primária de quebra é mostrada como O(nÓ (kd)), o que implica que, para fixo k, este problema de agrupamento pode ser resolvido em tempo polinomial. Para o problema com o critério intra-cluster mais típico da soma dos erros quadráticos, apresentamos também um algoritmo randomizado eficiente que, grosso modo, encontra um ε-agrupamento 2 aproximado em O(n(1/ε)d) tempo, que é bastante prático e pode ser usado para problemas reais de grande escala, como o problema de quantização de cores.

Publicação
IEICE TRANSACTIONS on Information Vol.E83-D No.6 pp.1199-1206
Data de publicação
2000/06/25
Publicitada
ISSN online
DOI
Tipo de Manuscrito
PAPER
Categoria
Algoritmos

autores

Palavra-chave