Olá Flavio,
É normal, pois a inicialização do algoritmo é sempre diferente a cada vez que executamos (a inicialização dos centróides). Para sempre ter os mesmos resultados, você pode configurar o parâmetro random_state do k-means (pode colocar qualquer valor inteiro, e usando o mesmo valor os resultados sempre serão os mesmos)
Jones