K-Means adalah salah satu algoritma clustering yang sangat popular karena kesederhanaan dan kemampuannya dalam menangani data dengan skala besar. Namun demikian algoritma ini sangat sensitif terhadap centroid awal. Perbedaancentroid awal akan memberikan perbedaan hasil clustering dan apabila centroid awal yang diberikan adalah centroid yang tidak baik maka dapat dipastikan hasil clusteringnya juga tidak baik. Artikel ini memuat sebuah metode baru yang dikembangkan penulis untuk meningkatkan kualitas centroid awal melalui teknik perbaikan k yang didasarkan pada graf hutan yang minimum (minimum forest graf). Hasil percobaan yang telah dilakukan menunjukkan bahwa metode inisialisasi menggunakan graf hutan yang minimum menghasilkan centroid awal yang lebih baik dan konsisten dibandingkan metode Forgy. Disamping itu jumlah Perulangan yang harus dilakukan dalam proses clustering dengan menggunakan metode ini adalah lebih sedikit (rerata 3,2) dibandingkan metode Forgy (rerata 6,4).