IMPLEMENTASI FUZZY C-MEAN DAN ALGORITMA PARTICLE SWARM OPTIMIZATION UNTUK CLUSTERING KABUPATEN/KOTA DI INDONESIA BERDASARKAN INDIKATOR INDEKS PEMBANGUNAN MANUSIA
on
E-Jurnal Matematika Vol. 11(3), Agustus 2022, pp. 191-198
DOI: https://doi.org/10.24843/MTK.2022.v11.i03.p380
ISSN: 2303-1751
IMPLEMENTASI FUZZY C-MEAN DAN ALGORITMA
PARTICLE SWARM OPTIMIZATION UNTUK CLUSTERING KABUPATEN/KOTA DI INDONESIA BERDASARKAN INDIKATOR INDEKS PEMBANGUNAN MANUSIA
I Kadek Sona Dwiguna1§, G. K. Gandhiadi2, Luh Putu Ida Harini3
1Program Studi Matematika, Fakultas MIPA – Universitas Udayana [Email: [email protected]]
2Program Studi Matematika, Fakultas MIPA – Universitas Udayana [Email: [email protected]]
3Program Studi Matematika, Fakultas MIPA – Universitas Udayana [Email: [email protected]]
§Corresponding Author
ABSTRACT
This research is aimed to determine conduct clustering in accordance with the conditions of districts / cities throughout Indonesia based on the IPM indicator and to determine the performance comparison of Fuzzy C-Means using particle swarm optimization compared to ordinary fuzzy c mean. The study uses 514 district / city data in Indonesia based on four IPM indicators. The research show 4 clusters that describe the condition of the Indonesian region and based on the results of cluster validation shows that there are differences in the ordinary Fuzzy C-Means mean algorithm and Fuzzy C-Means using particle swarm optimization.
Keywords: Fuzzy C Means, IPM Indicator, Particle Swarm Optimization.
keanggotaan. FCM termasuk algoritma clustering yang paling populer, dikarenakan dalam implementasinya sangat mudah dan memiliki kinerja yang terbilang baik, walaupun demikian Fuzzy C-Means memiliki kekurangan yaitu dengan dibangkitkannya pusat klaster secara acak menyebabkan sering kali solusi terjebak dalam optimum lokal, hal ini membuat penulis ingin menggunakan salah satu algoritma optimasi yaitu algoritma Particle Swarm Optimization untuk membantu Fuzzy C-Means yang diharapkan mendapatkan solusi yang lebih baik (Kusumadewi, 2002).
Particle Swarm Optimization merupakan algoritma optimasi yang didasari oleh suatu perilaku sosial dari pergerakan burung,ikan atau makhluk hidup yang berkelompok lainnya. Particle Swarm Optimization menyediakan prosedur pencarian dengan berbasis populasi di mana setiap individu disebut dengan partikel. Partikel merupakan kandidat solusi dari permasalahan yang diberikan, setiap iterasi partikel berpindah posisi menuju ke posisi terbaik di mana solusi terbaik ditemukan (Eberhart & Kennedy, 1995).
Adapun tujuan dari penelitian ini, yaitu melakukan clustering yang sesuai dengan kondisi kabupaten/kota di seluruh Indonesia berdasarkan indikator IPM kemudian membandingkan kinerja Fuzzy C-Means dan algoritma Particle Swarm Optimization dibandingkan Fuzzy C-Means biasa
Algoritma FCM Menurut Kusumadewi, (2002), adalah suatu teknik klasterisasi data yang mana keberadaan setiap data dalam suatu klaster ditentukan oleh nilai derajat keanggotaan suatu data yang disimbolkan dengan μik, elemen di baris ke-i dan kolom ke-k di μ menunjukkan seberapa besar nilai derajat keanggotaan obyek ke-i di klaster ke-k. Derajat keanggotaan μtk bernilai pada rentang 0 sampai 1. Semakin tinggi derajat keanggotaan maka semakin tinggi kemiripan data dalam satu kelompok. Setiap derajat keanggotaan μik haruslah mengikuti kaidah-kaidah sebagai berikut.
μik ∈ [0,1],∀i = 1,2,..,N; ∀k = 1,2,..,c
c
∑ μik = 1; ∀i = 1,2,3,..,N
k=1
n
0<∑ μik<N;∀J = 1,2,3,..,c
(2)
(3)
k=1
Dengan N adalah jumlah obyek penelitian dan c adalah jumlah klaster.
Konsep dasar FCM adalah untuk meminimalkan fungsi obyektif J(U,V') yang
didefinisikan sebagai berikut.
C N
](U,V) = ∑∑( μkw⅛k 1=1 k=1
d-tk = lZk-Vi12
(4)
(5)
Dengan U adalah matriks fuzzy partisi dari data Z, V = [v1,v2, . ,vc] adalah pusat klaster, c adalah jumlah klaster dfk adalah jarak Euclidean yang digunakan untuk menghitung jarak antara Zk dan Vt, w adalah bobot pada nilai keanggotaan yang bernilai lebih dari 1.
Algoritma FCM bermulai dengan menentukan pusat cluster yang akan menandai lokasi rata-rata setiap cluster. Pada iterasi 0 atau kondisi awal, pusat klaster ini masih belum tepat, dengan demikian diperlukan perbaikan pusat klaster dan derajat keanggotaan secara berulang dengan menggunakan persamaan
sebagai berikut. ∑N=ι(μt1)wz1 (6)
y'k ∑N,ι(μtkt)w
n> = L⅛⅛l (7
1∑u ⅛,⅛]-,J
Berikut ini adalah langkah-langkah dalam algoritma FCM. (Kusumadewi, 2002)
-
1. Menentukan jumlah klaster (c), pangkat pembobot (w), maksimum iterasi, error terkecil yang diharapkan (ε).
-
2. Membangkitkan random matriks derajat keanggotaan.
-
3. Menghitung pusat klaster dengan persamaan (3).
-
4. Memperbaiki matriks U dengan persamaan
(7)
-
5. Menghitung fungsi obyektif dengan persamaan (4).
-
6. Memeriksa kondisi berhenti (konvergen), yaitu:
(l](U,V)t-](U,V)t-1∣)<ε atau (t > maksimum iterasi).
-
7. Jika terpenuhi algoritma berhenti, jika tidak maka langkah ke-4 algoritma dilakukan kembali.
Algoritma Particle Swarm Optimization adalah algoritma optimasi berbasis pada populasi, dengan kata lain algoritma ini mengeksploitasi populasi suatu solusi untuk menyelidiki ruang pencarian secara bersamaan pada setiap iterasinya. Populasi dalam algoritma PSO disebut dengan istilah swarm dan individu-individunya disebut dengan partikel.
Setiap partikel diberi suatu fungsi fitness yang unik yang berbeda dengan partikel di swarm lainnya sesuai dengan masalah yang bersesuaian, nilai fitness suatu partikel ke —i dievaluasi menggunakan fungsi fitness tertentu yang dinotasikan dengan ft (t) dengan t adalah jumlah iterasi.
PSO menyimpan ingatan (memory) di mana setiap partikel menyimpan posisi terbaik yang pernah dikunjungi partikel selama pencarian solusi (Ptbest) yang didefinisikan
berikut (Parsopoulos & Vrahatis, 2010)
Ptbest (t) = argminf(Xi(t)),i = 1,2, ...,m
Dengan arg min f (xt (t))adalah
sebagai
(8)
posisi
partikel Xt dengan f(xt(t)) yang paling minimal hingga iterasi ke- t dan m adalah banyaknya partikel. Setiap iterasi algoritma PSO, maka
setiap partikel akan semakin mendekati nilai minimum global. Dimisalkan g adalah posisi terbaik dengan nilai fungsi terendah diantara Pibest setiap partikel pada t iterasi yang diberikan, maka:
gbest(t = argminf (pibest (t)) (9)
Setiap partikel akan memperbarui (update) kecepatan dan posisinya masing-masing dengan menggunakan persamaan berikut :
viti(t + 1) = w* viti(t) + φ1*
rι(pibest - ^i) + ^2 * r2(gbest - %i) (10)
Xi(t+1) = xi + viti (11)
dengan w adalah koefisien inersia yang ditetapkan sebelumnya dan selanjutnya diturunkan dengan secara bertahap setiap iterasi, jika dituliskan secara matematis adalah sebagai berikut.
w(t) = Wmax - (-----------) * t (
dengan wmax dan wmin adalah nilai koefisien inersia yang maksimum dan minimum, Tmax adalah maksimum iterasi dan t adalah iterasi yang sedang berlangsung. Ketika w bernilai maksimum, proses pencarian terjadi secara global ke segala arah. Sementara itu, ketika w diturunkan, pencarian menjadi lebih ke fokus ke suatu area tertentu yang potensial (Suyanto, 2017) ,φ1, φ2 adalah koefisien akselerasi berupa konstanta positif pada umumnya bernilai 2 (Eberhart & Kennedy, 1995) dan r1,r2 adalah bilangan acak pada interval [0,1].
Setelah kecepatan dan posisi partikel diperbarui mengikuti partikel optimum, algoritma PSO terus dilakukan berulang hingga diperoleh semua partike (Izakian & Abraham, 2011)l menuju solusi yang optimum. (Izakian & Abraham, 2011).
Berikut ini adalah langkah-langkah algoritma Particle Swarm Optimization
-
1. Menginisialisasi posisi awal setiap partikel (Xi) dan kecepatan awal setiap partikel (viti) secara acak dengan i = 1,2,..., l dan l adalah banyaknya partikel.
-
2. Menghitung nilai fungsi fitness (fungsi tujuan) untuk setiap partikel f(Xt).
-
3. Menentukan Pibest dan gbest awal setiap partikel.
-
4. Memperbarui kecepatan setiap partikel (viti) dengan persamaan (10)
-
5. Memperbarui posisi setiap partikel (Xi) dengan persamaan (11)
-
6. Menghitung kembali fungsi fitness (fungsi tujuan) f(χi), jika Kxl) ≤ f(plbest) maka Pibest = Xi, setelah mendapatkan Pibest baru, maka didapatkan gbest baru.
_ (pibest, f(pibest) < f(gbest^ best ^ Ubest J(Pibest) ≥ f(gbest )
-
7. Jika iterasi mencapai maksimum atau konvergen, maka algoritma berhenti, jika tidak maka langkah ke-4 algoritma dilakukan kembali.
Permasalahan dari FCM adalah solusi yang diperoleh sering kali terjebak dalam optimum lokal. (Wei Pang, 2004) dalam jurnalnya mengusulkan modifikasi algoritma Particle Swarm Optimization untuk permasalahan TSP (Travel Salesman Problem) yang kemudian dikenal dengan Fuzzy Particle Swarm Optimization (FPSO). Pada FPSO, solusi optimum adalah fungsi obyektif pada FCM, dalam FPSO, pencarian solusi dilakukan dengan memanggil l sejumlah partikel, dengan partikel adalah kandidat solusi dalam permasalahan FCM. Posisi partikel dalam FPSO dinotasikan dengan Xi. Posisi partikel dalam FPSO merepresentasikan matriks derajat keanggotaan U dalam FCM, dengan kata lain Xi merupakan matriks yang berisikan q jumlah data yang diproses dan c jumlah kluster.
Konsep dasar FCM adalah meminimalkan fungsi obyektif dengan kata lain semakin kecil J(U, V) semakin baik solusi yang diperoleh, hal ini berarti posisi partikel ke-i dengan nilai f(Xi) yang terendah adalah posisi partikel ke-i yang terbaik dan gbest adalah f(Pibest) yang terkecil. Setelah diperoleh Pibest dan gbest keseluruhan partikel dalam ruang solusi bergerak mengikuti posisi partikel dengan f(Xt) yang terbaik, pergerakan partikel ini dihitung dengan cara sebagai berikut.(Izakian & Abraham, 2011).
viti(t + 1) = w * viti(t) + φιrr(Pibest — Xi) + φ2r2(gbest — Xi)
Xi(t + 1) = Xi^ viti
(13)
(14)
Setelah semua posisi partikel telah diperbarui, tinggi kemungkinan aturan ∑k=1μpk = 1,∀p untuk setiap posisi partikel tidak dipenuhi. Pada kondisi seperti ini, maka dilakukan normalisasi matriks untuk setiap partikel. Pertama semua nilai μpk yang bernilai negatif menjadi nol. Jika semua nilai dalam baris matriks bernilai nol maka bangkitkan bilangan acak dengan interval [0,1]. Matriks baru yang telah dinormalkan ditunjukkan sebagai
berikut.(Izakian & Abraham, 2011).
v normal _ Xi = |
r μιι μci t |
(15) |
∑c=1μi1 . ∑c=1μi1 • X ⋮ Pin μcn | ||
-∑c=1,μin ∑c=ιμin- |
Izakian & Abraham (2011) dalam jurnalnya mengintegrasi algoritma FCM ke dalam algoritma Fuzzy Particle Swarm Optimization (FPSO) untuk membentuk algoritma klasterisasi yang disebut dengan algoritma FCM-PSO. Dalam algoritma FCM-PSO, kinerja algoritma FCM dan algoritma FPSO dapat dipertahankan dan bisa ditingkatkan guna mendapatkan hasil klaster yang lebih baik.
Algoritma FCM-PSO
-
1. Menentukan data yang akan dilakukan klasterisasi zij yaitu data sampel ke-i dengan
-
i. = (1,2,3 ...N) dan variabel ke√ dengan y = (1,2,3n).
-
2. Menentukan jumlah klaster (c), pangkat pembobot (w), maksimum iterasi, error terkecil yang diharapkan (ε).
-
3. Algoritma FPSO
-
i. Menghitung pusat klaster masing-masing partikel menggunakan persamaan (6).
-
ii. Menghitung nilai J(U,V) dan f (xc) masing-masing partikel menggunakan persamaan (4).
-
iii. Menentukan Pcbest setiap partikel
menggunakan persamaan (8).
-
iv. Menentukan gbest menggunakan
persamaan (9).
-
v. Memperbarui kecepatan (vitc) seluruh partikel menggunakan persamaan (13).
-
vi. Memperbarui posisi (xc) seluruh partikel dengan persamaan (14).
-
a. Cek kondisi posisi setiap partikel ⅛).
-
b. Jika ∑k=1μpk ≠ 1,∀p lakukan normalisasi matriks dengan menggunakan persamaaan (15)
-
c. Jika ∑k=ι^pk = 1 ,∀P, algoritma dilanjutkan.
-
vii. Melakukan kembali langkah ke-3 hingga t ≤ maksimum iterasi atau
gbest(t) — gbest(t — 1) < ε.
-
4. Algoritma FCM
-
i. Menghitung pusat klaster masing-masing partikel menggunakan
persamaan (6).
-
ii. Menghitung fungsi jarak euclidean masing-masing partikel menggunakan persamaan (5).
-
iii. Memperbarui fungsi keanggotaan masing-masing partikel menggunakan persamaan (7).
-
iv. Menentukan Pcbest setiap partikel
menggunakan persamaan (8).
-
v. Menentukan nilai gbest menggunakan persamaan (9).
-
vi. Melakukan kembali Langkah 4 hingga t ≤ maksimum iterasi atau gbest(t) — gbest(t — 1) < ε.
-
5. Melakukan ulang langkah ke-3 hingga t ≤ maksimum iterasi atau tidak terdapat
perubahan nilai gbest selama 2 iterasi berturut-turut.
Validitas Cluster digunakan untuk membandingkan kinerja pengelompokan Fuzzy C-Means dan algoritma optimasi Particle Swarm Optimization dengan Fuzzy C-Means biasa.
-
1. Partition Coefficient (PC)
Indeks ini digunakan untuk menghitung jumlah overlapping antar kelompok. Indeks ini dirumuskan sebagai berikut. (Balasko, Abonyi, & Feil, 2005)
C N
PC(C) = 1∕N∑∑μ⅛ i=i k=i
dengan N merupakan jumlah objek penelitian, c adalah jumlah klaster, dan μik adalah nilai keanggotaan objek ke-k dengan pusat kelompok ke-i. Nilai PC yang paling besar menunjukkan jumlah kelompok yang optimal.
-
2. Xie and Beni’s Index (XB)
Indeks ini digunakan untuk mengukur rasio total variasi dalam klaster dan pemisahan antar klaster. Indeks ini dirumuskan sebagai berikut. (Balasko, Abonyi, & Feil, 2005)
XB =
∑ci=ι∑N=ιμ⅛∖∖Xk-VkW2
Nmini,k^Vk — vi∖∖2
dengan N adalah jumlah obyek penelitian, c adalah jumlah kelompok μik adalah nilai keanggotaan obyek ke-k dengan pusat kelompok ke-i, m adalah pembobot dalam FCM, Wxk — VkW2 adalah jarak euclidean data (xk) dengan pusat klaster vi, dan Wvk — ViW2 adalah jarak euclidean antar pusat klaster, klaster yang lebih baik ditunjukkan dengan nilai XB yang lebih rendah.
-
3. Partition Index (PI)/Separation dan Compactness (SC)
PI atau SC adalah rasio antara jumlah kepadatan dan pemisahan antar klaster. PI atau SC digunakan untuk membandingkan hasil pengelompokan yang berbeda yang memiliki jumlah klaster yang sama. Indeks ini
dirumuskan dalam persamaan berikut (Balasko, Abonyi, & Feil, 2005)
C sc=∑ i=ι
∑‰ιG¾)mlkfc -vi∖∖2
^Vi ∑C=1Hvy - Vt∏2
Dengan V adalah jumlah obyek penelitian, Ni adalah obyek penelitian kelompok ke-i, c merupakan banyaknya klaster, μik merupakan nilai keanggotaan obyek ke-k dengan pusat kelompok ke-i, m merupakan pembobot dalam FCM, ∣∖xk -ViW2 adalah jarak euclidean data (xk) dengan pusat klaster Vi, dan ∣∖vk — ViW2 adalah jarak euclidean antar pusat klaster. Partisi klaster yang lebih baik ditunjukkan dengan nilai SC yang lebih rendah
-
4. Separation Index (S)
Pemisahan antar klaster pada Separation Index (S), didefinisikan sebagai minimum jarak antar pusat klaster. Indeks ini dirumuskan dalam persamaan berikut (Bezdek, 1996).
C
≡ = ∑ i=i
∑‰ιG⅛)mlkk-ViW2 vImiKijWvj - vi∖∖2
Nilai S yang lebih rendah mengindikasikan partisi kelompok yang lebih baik.
Indikator IPM menurut (Badan Pusat Statistik, 2019) ada empat, yaitu
-
1. Umur Harapan Hidup saat Lahir (UHH) Merupakan rataan taksiran jumlah tahun yang dapat dicapai oleh seseorang selama hidup.
-
2. Rata-rata Lama Sekolah (RLS) Menggambarkan jumlah tahun pada penduduk usia 25 tahun ke atas dalam menjalani pendidikan formal.
-
3. Angka Harapan Lama Sekolah ( HLS ) Menggambarkan lamanya sekolah dalam satuan tahun yang diharapkan akan diperoleh oleh anak rentang umur tertentu di masa mendatang.
-
4. Pengeluaran per Kapita Disesuaikan Merupakan pengeluaran yang ditentukan dari nilai pengeluaran per kapita dan paritas daya beli (Purcashing Power Parity-PPP).
-
2. METODE PENELITIAN
Sumber Data. Data yang akan digunakan dalam penelitian ini merupakan data sekunder yang diperoleh dari BPS tahun 2019, yaitu data indikator IPM di 514 Kabupaten/Kota di Indonesia.
Variabel Penelitian. Variabel penelitian yang digunakan diperoleh dari BPS tahun 2019, variabel merupakan indikator IPM yang digunakan oleh BPS ,meliputi Umur Harapan Hidup-UHH (Z1), Rata-rata Lama Sekolah-RLS (Z2), Angka Harapan Lama Sekolah-HLS (Z3), dan Pengeluaran per kapita yang disesuaikan-PPK (Z4).
Teknik analisis data. Berikut ini adalah langkah-langkah yang dilakukan dalam penelitian.
-
1. Menentukan data yang akan dilakukan klasterisasi Zij yaitu data sampel ke-i dengan
i = (1,2,3 ...N) dan variabel ke-j dengan j = (1,2,3, .,n). Dalam penelitian ini N merupakan jumlah data Kabupaten/Kota di Indonesia yaitu 514 dan n merupakan variabel yang digunakan yaitu 4 indikator IPM yaitu UHH (Z1), RLS(Z2), AHS(Z3) , dan PPK(Z4).
-
2. Menormalisasi data Xij dengan z-score.
TP-Zii
Zij = (zij--)—lV^nI
untuk setiap i , dengan Zij adalah data sampel yang telah di normalisasi dan Zij adalah data sampel yang belum di normalisasi.
-
3. Menentukan jumlah klaster (c), pangkat pembobot (w), maksimum iterasi, error terkecil yang diharapkan (ε). Jumlah klaster yang digunakan adalah 4 mengikuti jumlah pengelompokan yang dilakukan oleh BPS, pangkat pembobot adalah 2, maksimum iterasi kondisi berhenti pada sub iterasi FPSO adalah tercapai 1000 iterasi atau nilai gbest tidak berubah selama 200 iterasi beruntun., maksimum iterasi pada sub iterasi FCM adalah 5 dan kondisi berhenti keseluruhan algoritma FCM-PSO adalah nilai gbest tidak berubah selama 2 iterasi beruntun.
-
4. Algoritma FPSO
-
i. Menghitung pusat klaster masing-masing partikel menggunakan persamaan (6).
-
ii. Menghitung nilai /(U, V) dan f(Xi) masing-masing partikel menggunakan persamaan (4).
-
iii. Menentukan Pibest setiap partikel menggunakan persamaan (8).
-
iv. Menentukan gbest menggunakan
persamaan (9).
-
v. Memperbarui kecepatan (viti) seluruh
partikel menggunakan persamaan (13).
-
vi. Memperbarui posisi (xi) seluruh partikel dengan persamaan (14).
-
a. Memeriksa kondisi posisi setiap partikel (xt)
-
b. Jika ∑k=ιFpk ≠ 1,∀P dilakukan
normalisasi matriks dengan
menggunakan persamaan (15)
-
c. Jika ∑k=ιPpk = 1,∀P, algoritma
dilanjutkan
-
vii. Melakukan ulang langkah ke-4 hingga t ≤ maksimum iterasi atau gbest(t) —
gbest(t — 1) < ε
-
5. Algoritma FCM
-
i. Menghitung pusat klaster masing-masing
partikel menggunakan persamaan (6).
-
ii. Menghitung jarak euclidean masing-
masing partikel menggunakan persamaan (5).
3. HASIL DAN DISKUSI
Penelitian ini dikerjakan untuk mengetahui hasil clustering algoritma hybrid Fuzzy C-Means dengan algoritma optimasi Particle Swarm Optimization pada data 514 kabupaten/kota di Indonesia. Hasil clustering data tersebut diharapkan nantinya dapat dijadikan sebagai acuan sejauh mana pembangunan nasional di Indonesia, sehingga diharapkan kabupaten/kota yang berada di klaster terbawah bisa mendapat perhatian lebih oleh pemerintah.
Berikut ini adalah data kabupaten/kota di Indonesia.
Tabel 1. Data Kabupaten/Kota di Indonesia
No. |
Kabupaten / Kota |
AHH (Z1) (Tahun ) |
RLS (Z2) (Tahun ) |
HLS (Z3) (Ribu Rupiah/Tahun ) |
PPK(Z4 ) (Tahun) |
1 |
SIMEULUE |
65.22 |
13.51 |
7210.00 |
9.08 |
2 |
ACEH SINGKIL |
67.36 |
14.30 |
8715.00 |
8.52 |
3 |
ACEH SELATAN |
64.27 |
14.41 |
8187.00 |
8.59 |
4 |
ACEH TENGGAR A |
68.04 |
13.99 |
8067.00 |
9.65 |
5 |
ACEH TIMUR |
68.67 |
13.02 |
8600.00 |
7.86 |
6 |
ACEH TENGAH |
68.82 |
14.26 |
10782.00 |
9.69 |
512 |
INTAN JAYA |
65,09 |
7.36 |
5593.00 |
2.64 |
513 |
DEIYAI |
64,63 |
9.80 |
4958.00 |
3.00 |
514 |
KOTA JAYAPURA |
70,00 |
15.00 |
15176.00 |
11.55 |
-
iii. Memperbarui fungsi keanggotaan setiap partikel menggunakan persamaan (7).
-
iv. Menentukan Pibest setiap partikel menggunakan persamaan (8).
-
v. Menentukan nilai gbest menggunakan persamaan (9).
-
vi. Melakukan kembali langkah 5 hingga t ≤ maximum iterasi atau gbest(t) — gbest(t — 1) < ε.
-
6. Melakukan kembali langkah ke-4 hingga t ≤ maximum iterasi atau tidak terdapat perubahan nilai gbest selama 2 iterasi beruntun.
-
7. Melakukan uji validitas untuk kelompok yang diperoleh dari Fuzzy C-Means dan Particle Swarm Optimization dengan Fuzzy C-Means tanpa optimasi.
-
8. Menginterprasi hasil pengelompokan yang diperoleh.
Berdasarkan data yang ditunjukkan pada tabel 1 selanjutnya akan dilakukan normalisasi data, kemudian dengan mengikuti tahapan-tahapan algoritma FCM-PSO akan diperoleh gbest untuk seluruh partikel di setiap iterasinya. gbest mempresentasikan solusi dari FCM yaitu fungsi obyektif paling minimum. Selanjutnya algoritma FCM-PSO akan terus berjalan hingga kondisi berhentinya terpenuhi. Dengan bantuan software Matlab berikut adalah nilai gbest untuk setiap iterasinya dan perbandingan dengan algoritma FCM tanpa optimasi.
Tabel 2. Fungsi Obyektif FCM-PSO
iterasi |
FCM — PSO |
1 |
491.405469745084 |
2 |
434.504609958592 |
3 |
433.820162036769 |
4 |
433.789060324425 |
5 |
433.785768537181 |
6 |
433.785202111597 |
7 |
433.785080865956 |
8 |
433.785055463270 |
9 |
433.785054126373 |
10 |
433.785054068165 |
Tabel 3. Fungsi Obyektif FCM
iterasi |
FCM |
1 |
682.8043733617 |
2 |
512.4185957680 |
3 |
511.0442316092 |
52 |
433.7850972358 |
53 |
433.7850875734 |
Perbandingan Fuzzy C-Means dengan Fuzzy C-Means dan Particle Swarm Optimization
Berdasarkan tabel 2 diperoleh fungsi obyektif pada algoritma Fuzzy C-Means dengan algoritma optimasi Particle Swarm Optimization setelah 10 iterasi mendapatkan fungsi obyektif terakhir sebesar 433.78505. Sedangkan pada tabel 3 diperoleh FCM tanpa optimasi setelah 53 iterasi dilakukan diperoleh fungsi obyektif terakhir sebesar 433.78508 hal ini menunjukkan FCM-PSO tidak memiliki hasil yang berbeda secara signifikan walaupun hasil yang diperoleh dari algoritma FCM-PSO sedikit lebih baik, langkah selanjutnya adalah menguji validitas klaster dengan menggunakan indeks Partition Coefficient (PC), Xie and Beni’s Index (XB), Partition Index (PI)/Separation dan Compactness (SC) dan Separation Index (S). Hasil pengujian dilakukan dengan Matlab yang bisa dilihat pada tabel di bawah ini.
Tabel 4. Perbandingan Algoritma FCM-PSO dan Algoritma FCM
Validitas |
FCM-PSO |
FCM |
PC |
0.43642120 |
0.43641980 |
SC |
0.41558799 |
0.41558872 |
S |
0.00134610 |
0.00134612 |
XB |
1.94088680 |
1.94054017 |
Berdasarkan tabel 4 dapat dilihat bahwa berdasarkan kedua uji validitas yang dilakukan, hasil partisi menggunakan metode FCM-PSO lebih unggul di 3 dari 4 uji validitas yang dilakukan walaupun tidak signifikan.
Interpretasi hasil clustering kabupaten/kota di Indonesia
Software matlab memerlukan 10 iterasi untuk mendapatkan posisi partikel terbaik sebelum memperoleh solusi optimal pada fungsi tujuan senilai 433.785054068165. Hasil kedua yang diperoleh adalah pusat 197lister atau center .
'70.030 12.888 10940.97 8.371'
65.364 12.592 8459.01 7.575
72.230 14.461 14196.16 10.559
69.202 12.289 9509.899 7.321
Berdasarkan dari pusat klaster (V) yang diperoleh, maka Kabupaten/Kota di Indonesia dikelompokkan menjadi 4 kelompok sebagai berikut:
-
1. Kelompok pertama (Cluster ke-1), berisi kabupaten/kota yang memiliki angka harapan hidup saat lahir sekitar 70.030 tahun; memiliki harapan lama sekolah sekitar 12.888 tahun ; memiliki rata-rata pengeluaran per kapita 10940.97 ribu rupiah per tahun; dan memiliki rata-rata lama sekolah 8.371 tahun.
-
2. Kelompok kedua (Cluster ke-2), berisi kabupaten/kota yang memiliki angka harapan hidup saat lahir
sekitar 65.364 tahun; memiliki harapan lama sekolah sekitar 12.592 tahun ; memiliki rata-rata pengeluaran
perkapita 8459.01 ribu rupiah per tahun; dan memiliki rata-rata lama sekolah 7.575 tahun.
-
3. Kelompok ketiga (Cluster ke-3), berisi kabupaten/kota yang memiliki angka harapan hidup saat lahir sekitar 72.23 tahun; memiliki harapan lama sekolah sekitar 14.461 tahun ; memiliki rata-rata pengeluaran perkapita
-
14196.16 ribu rupiah per tahun; dan
memiliki rata-rata lama sekolah 10.559 tahun.
-
4. Kelompok keempat (Cluster ke-4), berisi kabupaten/kota yang memiliki angka harapan hidup saat lahir sekitar 69.202 tahun; memiliki harapan lama sekolah sekitar 12.289 tahun ; memiliki rata-rata pengeluaran perkapita
9509.899 ribu rupiah per tahun; dan memiliki rata-rata lama sekolah 7.321 tahun.
Berikut adalah hasil pengelompokan kabupaten/kota di Indonesia berdasarkan derajat keanggotaannya.
Tabel 5. Hasil klaster kabupaten/kota di Indonesia
Klaster 1 |
Klaster 2 |
Klaster 3 |
Klaster 4 |
Aceh Tenggara |
Simeulue |
Aceh Besar |
Aceh Timur |
Aceh Tengah |
Aceh Singkil |
Kota Banda Aceh |
Nias |
Aceh Barat |
Aceh Selatan |
Kota Sabang |
Nias Selatan |
Pidie |
Aceh Barat Daya |
Kota Langsa |
Nias Utara |
Bireuen |
Gayo Lues |
Kota Lhokseumawe |
Nias Barat |
Aceh Utara |
Kota Subulussalam |
Toba Samosir |
Indragiri Hilir |
Mimika |
Deiyai |
Kota Jayapura |
Intan Jaya |
Berdasarkan pengelompokan 4 klaster tersebut bisa diambil kesimpulan kelompok ke 2 yang berisikan 138 kabupaten/kota memiliki nilai indikator terkecil. 138 kabupaten/kota tersebut 69.5% merupakan kabupaten/kota yang berada di kawasan Indonesia timur.
-
4. SIMPULAN DAN SARAN
Simpulan
-
a. Metode Fuzzy C-Means dapat dipadukan dengan optimasi Particle Swarm Optimization dalam proses clustering. FCM-PSO membagi data kabupaten/kota di Indonesia menjadi 4 klaster, proses algoritma berhenti pada iterasi ke-10 dengan fungsi obyektif diperoleh sebesar 433.7850541 hasil pengelompokan menunjukkan
kabupaten/kota di Indonesia bagian timur cenderung masuk ke dalam klaster kedua yaitu klaster dengan nilai indikator yang paling kecil, dengan demikian diharapkan pembangunan nasional lebih ditingkatkan lagi pada wilayah di Indonesia bagian timur.
-
b. Penggunaan algoritma optimasi Particle Swarm Optimization dalam Fuzzy C-Means tidak terlalu berpengaruh secara signifikan walaupun 3 dari 4 uji validitas, algoritma FCM-PSO lebih unggul dari FCM.
Saran
Saran yang bisa diberikan pada penelitian tentang clustering Kabupaten/Kota di Indonesia
adalah menggunakan optimasi yang lain seperti Ant-Colony, Genetic Algorithm yang kemudian dipadukan dengan algoritma FCM.
DAFTAR PUSTAKA
Badan Pusat Statistik. (2019). Indeks Pembangunan Manusia 2019. Jakarta: Badan Pusat Statistik.
Balasko, B., Abonyi, J., & Feil, B. (2005). Fuzzy Clustering and Data Analysis Toolbox For Use with Matlab. Department of Process Engineering University of Veszprem.
Bezdek, J. C. (1996). Validity-guided (Re) Clustering with applications to image segmentation. IEEE Transactions on Fuzzy Systems, 112-123.
Eberhart, R. C., & Kennedy, J. (1995). A new optimizer using particle swarm theory. In Proceedings of the sixth international symposium on micro machine and human. MHS'95. Proceedings of the Sixth International Symposium on Micro Machine and Human Science, 39-43.
Izakian, H., & Abraham, A. (2011). Fuzzy C-means and fuzzy swarm for fuzzy clustering problem. Expert Systems with Applications, 1835-1838.
Kusumadewi, S., & Purnomo, H. (2010).
Aplikasi Logika Fuzzy untuk Pendukung Keputusan. Yogyakarta: Graha Ilmu.
Parsopoulos, K. E., & Vrahatis, M. N. (2010). Particle Swarm Optimization and Intelligence: Advances and Applications. New York: Information Science
Reference.
Parsopoulos, K., & Vrahatis, M. (2010). Particle swarm optimization and intelligence : advances and applications. Information Science Reference.
Wei Pang, K.-P. W. (2004). Fuzzy Discrete Particle Swarm Optimization for Solving Traveling Salesman Problem. The Fourth International Conference on Computer and Information Technology, 796-800.
198
Discussion and feedback