Pusat Kesehatan Masyarakat (Puskesmas) merupakan fasilitas tingkat pertama untuk kesehatan masyarakat di wilayah kerjanya. Bagian terpenting puskesmas adalah ketersediaan tenaga kesehatan medis. Kalimantan Timur merupakan provinsi yang memiliki presentase 51,3 % untuk kesedian tenaga kesehatan medis presentase tersebut masih jauh dibawah Daerah Istimewa Yogyakarta dan Bangka Belitung yang memiliki presentase diatas 80%. Peran pemerintah sangat diperlukan untuk meningkatkan jumlah tenaga kesehatan medis. Pengelompokan tenaga kesehatan medis menggunakan Hierarchical Agglomerative Clustering dengan metode Average linkage merupakan salah satu cara untuk pemerintah memperoleh informasi terkait puskesmas yang memerlukan penambahan tenaga kesehatan medis. Hasil pengelompokan 26 puskesmas di Kota Samarinda dengan metode jarak Manhattan, Euclidean, Minkowski dan Chebyshev memiliki hasil iterasi yang berbeda-beda. Pengelompokan dengan metode jarak Manhatan iterasi dilakukan sebanyak 16 kali, jarak Euclidean iterasi dilakukan sebanyak 22 kali, jarak Minkowski iterasi dilakukan sebanyak 24 kali dan jarak Chebyshev iterasi dilakukan sebanyak 6 kali. Cluster yang terbentuk diuji menggunakan metode Silhouette Coefficient untuk menentukan cluster dan metode jarak yang lebih optimal. Berdasarkan hasil pengujian pada 2 cluster, 3 cluster dan 4 cluster dengan 4 metode jarak didapatkan cluster optimal yaitu 4 cluster dengan menggunakan metode jarak Manhattan dengan nilai Silhoutte 0.640761128. Pengelompokan dengan 4 cluster pada 26 puskesmas terdiri atas Cluster 1 yang merupakan kelompok yang kurang jumlah tenaga kesehatan medis yang terdapat pada 22 puskesmas, Cluster 2 merupakan kelompok yang memiliki Kesehatan Masyarakat tertinggi dan masih kurang untuk jenis tenaga kesehatan lainnya yang terdapat pada 2 puskesmas, Cluster 3 merupakan kelompok yang memiliki jumlah tenaga kesehatan yang sangat tinggi di semua jenis kesehatan kecuali perawat yang terdapat pada 1 puskesmas dan Cluster 4 memiliki jumlah tenaga kesehatan yang sangat tinggi pada dokter gigi, perawat, kesehatan masyarakat, kesehatan lingkungan dan ahli gizi yang terdapat pada 1 puskesmas. Berdasarkan jumlah penduduk di Kota Samarinda dengan jumlah tenaga kesehatan masih memerlukan penambahan tenaga kesehatan medis khususnya untuk menambah 350 dokter, 82 dokter gigi, 1543 perawat, 921 bidan, 97 kesehatan masyarakat, 146 kesehatan lingkungan dan 130 ahli gizi.