A análise de agrupamento é um dos algoritmos de processamento de dados mais comummente utilizados. Ao longo de meio século, K significa que continua a ser o algoritmo de clustering mais popular devido à sua simplicidade. O tradicional K significa clustering tenta atribuir n objectos de dados a k clusters, começando com centros iniciais aleatórios. No entanto, a maioria das variantes k significa que as variantes tendem a calcular a distância de cada ponto de dados a cada centro de agrupamento para cada iteração. Propomos uma heurística rápida para superar este estrangulamento com apenas um aumento marginal do erro médio quadrático (MSE). Observamos que em todas as iterações de K significa, um ponto de dados muda a sua filiação apenas entre um pequeno subconjunto de clusters. A nossa heurística prevê tais aglomerados para cada ponto de dados, olhando para aglomerados próximos após a primeira iteração de k-meios. Aumentamos as conhecidas variantes de k-meios como K-meios melhorados e K-meios com Triângulo Desigualdade usando a nossa heurística para demonstrar a sua eficácia. Para vários conjuntos de dados, a nossa heurística atinge uma velocidade de até 3 vezes quando comparada com variantes eficientes de k-meios.