207

Bab 12
Algoritma Pengelompokan k-Means Paralel
untuk Memproses Big Data

Oleh:

Veronica S. Moertini

12.1. Pengelompokan Data

Dalam konteks penambangan data (data mining), klaster didefinisikan sebagai sekelompok
objek-objek yang memiliki kemiripan yang tinggi (Han et al., 2012). Objek-objek pada sebuah
klaster tertentu memiliki kemiripan yang rendah dengan objek-objek pada klaster-klaster yang
lain. Di sini, objek dapat berupa orang, binatang, barang/benda, foto/citra, dokumen, lagu, video,
transaksi pengguna di bank, toko, e-commerce, hasil perekaman sensor cuaca pada suatu saat,
transaksi pengambilan matakuliah pada satu semester, “klik” pengguna website, dll. Dalam
konteks data mining, sebuah objek akan direpresentasikan menjadi “sebuah elemen” pada
himpunan data (dataset). Jadi, himpunan data berisi representasi dari objek-objek.

Analisis klaster merupakan salah satu teknik pada data mining yang utama. Tujuannya adalah
untuk menemukan klaster-klaster dari himpunan data secara otomatis atau semi-otomatis
menggunakan algoritma clustering. Berdasarkan pendekatan dan/atau konsep yang diadopsi,
teknik clustering dapat dikategorikan ke dalam metoda yang berbasis partisi, hirarki, dan
densitas/kerapatan, grid, model dan konstrain. Setiap kategori teknik memiliki kelebihan dan
kekurangan tersendiri. Kelebihan ini terkait dengan himpunan data yang bagaimana yang
ditangani, klaster bagaimana yang dibutuhkan juga kecepatan dalam meproses himpunan data.
Misalnya, untuk himpunan data yang ditengarai bahwa klaster-klasternya akan “terpisah” satu
sama lain, maka yang cocok digunakan adalah teknik partisi. Sedangkan untuk himpunan data
yang ditengarai akan menghasilkan klaster yang di “dalamnya” terdapat klaster yang lain, maka
yang cocok adalah teknik yang berbasis kerapatan.
 208

Beberapa contoh algoritma pada tiap kategori, diberikan di bawah ini:

• Partisi: k-Means dan k-Medoid
• Hirarki: Diana dan Agnes
• Kerapatan: DBSCAN dan OPTICS
• Grid: WaveCluster dan STING,
• Model: EM, SOM dan COBWEB.

Dari seluruh algoritma-algoritma di atas, k-Means termasuk yang populer dan banyak
dimanfaatkan.

12.2. Manfaat Analisis Klaster

Beberapa manfaat dari analisis klaster dari himpunan data antara lain (Han et al., 2012, URL-
cluster-1):
1. Di bidang bisnis: Pengelompokan pelanggan berdasarkan pembelian mereka untuk
keperluan pemasaran (targeted marketing). Hasil pengelompokan yang disasar: Tiap klaster
pelanggan memiliki pola atau ciri-ciri tertentu yang lalu cocok untuk ditawari produk-
produk tertentu yang cocok atau dibutuhkan pelanggan. Dengan begitu, pemasaran menjadi
lebih efektif.
2. Di bidang pemanfaatan lahan: Pengelompokan citra hasil penginderaan jauh satelit dapat
menghasilkan area dengan pemanfaatan lahan yang serupa (misalnya: perumahan, sawah,
hutan, pertambangan, dll). Hasilnya dapat dimanfaatkan untuk pemantauan pemanfaatan
lahan dari waktu ke waktu atau penyusunan kebijakan terkait dengan pemanfaatan lahan.
3. Di bidang pengarsipan: Pengelompokan dokumen-dokumen berdasar isi (semantik) dari
dokumen. Hasil dari pengelompokan dapat dimanfaatkan pada pencarian dokumen,
misalnya untuk pencarian dengan kata-kunci tertentu, yang dimunculkan adalah dokumen-
dokumen pada klaster tertentu.
4. Secara umum, analisis klaster juga dimanfaatkan pada pengenalan pola pada berbagai jenis
himpunan data (dokumen, citra, audio, video, dll) dan analisis citra (segmentasi objek-objek
yang terdapat di citra), dll.

Pada contoh nomor 1 di atas, disebut bahwa tiap klaster pelanggan memiliki pola atau ciri-ciri
tertentu. Pola tersebut contohnya bagaimana? Interpretasi pola dari sebuah klaster dapat
berupa deskripsi: “Pengguna band-width internet yang tinggi, umurnya belasan tahun, frekuensi
pembelian ayam geprek tinggi dan frekuensi pemakaian ojol tinggi”. Adapun deskripsi klaster
yang lain: “Pengguna band-width internet yang tinggi, umurnya dua puluhan tahun, frekuensi
pembelian bakso tinggi dan pemakaian ojol sedang“. Informasi ini lalu dapat digunakan untuk
 209

“targeted marketing”, misalnya memberikan iklan kepada pengguna umur dua puluhan yang
tidak sering naik ojol untuk menikmati bakso di restoran/warung tertentu.

Sebagai fungsi pada penambangan data, analisis klaster berperan sebagai alat (tool) untuk
menggali “informasi yang terpendam” (insight) dari distribusi data, misalnya deskripsi klaster
di atas.

12.3. Algoritma Pengelompokan k-Means Non-Paralel

Algoritma k-Means banyak digunakan dan populer, karena itu di bab ini dibahas sebagai salah
satu contoh algoritma pengelompokan. Algoritma ini menerima masukan himpunan data
berformat vektor, tiap objek memiliki fitur-fitur dan tiap fitur memiliki nilai yang
merepresentasikan objek tersebut. Misalnya, objek orang memiliki fitur pemanfaatan-band-
witdth (pbw), umur, frekuensi-pembelian-bakso (fpb), frekuensi-naik-ojol (fno). Contoh nilai
fitur sebuah objek adalah: pbw = 15 (gigabyte/bulan), umur = 23, fpb = 12 (per bulan), fno = 20
(per bulan).

Himpunan data yang berisi objek-objek tersebut dapat dipandang sebagai sebuah “tabel”,
dimana kolom-kolom merupakan fitur-fitur dan baris merepresentasikan sebuah objek. Contoh
himpunan data diberikan pada Tabel 12.1.

Tabel 12.1. Contoh himpunan data untuk masukan k-Means.

Objek pbw umur fpb fno

ke
1 15 23 12 20
2 11 18 9 14
3 2 45 4 0
4 4 50 1 1
5 15 23 12 12
6 1 15 9 13
7 21 45 4 1
8 14 30 1 2
9 11 19 9 3

Apabila jumlah fitur hanya dua, misalnya pwb dan umur saja dan objek-objek dikelompokkan
menjadi dua saja (k = 2), maka masukan dan keluaran dari algoritma k-Means dapat
diilustrasikan sebagaimana ditunjukkan pada Gambar 12.1. Objek-objek yang dikelompokkan
berada di sebelah kiri panah terlihat memiliki distribusi yang “terpisah” menjadi 2. Setelah
diumpankan ke k-Means, dihasilkan 2 klaster (ungu dan hijau).
 210

k-Means

Gambar 12.1. Ilustrasi masukan dan hasil k-Means dengan k = 2.

Bagaimana cara kerja algoritma k-Means?

Sejatinya, selain himpunan data, k-Means juga membutuhkan masukan jumlah klaster yang
ingin dibentuk, k pada k-Means (selain itu, juga inisial centroids atau titik-titik pusat
awal/inisialisasi, jumlah pengulangan eksekusi perintah, yang dikenal dengan istilah iterasi,
masksimum dan sebuah nilai konstanta yang digunakan untuk penentuan kapan iterasi
dihentikan, eps). Untuk ilustrasi algoritma k-Means, pada Gambar 12.2 diberikan contoh
beberapa objek yang akan dikelompokkan menjadi dua klaster (k = 2).

Gambar 12.2. Langkah-langkah komputasi k-Means.

Langkah-langkah k-Means sebagaimana ditunjukkan pada Gambar 12.3 adalah:

1. Untuk setiap objek yang terdapat pada himpunan data: jarak objek ke tiap centroid (titik
pusat) dihitung. Objek akan dimasukkan ke klaster dengan jarak terdekat.
2. Jarak tiap objek ke centroid-nya akan dijumlahkan (disimpan pada variabel CostTotal).
 211

3. Jika CostTotal pada iterasi sekarang dikurangi CostTotal dari iterasi sebelumnya
(Delta_CostTotal) lebih kecil atau sama dengan eps, maka iterasi dihentikan. Jika tidak, maka
centroids baru dihitung dan langkah kembali ke nomor 1 dengan menggunakan centroids
yang baru.
Perhitungan centroids baru dilakukan dengan menghitung rata-rata nilai setiap fitur dari semua
objek yang berada di dalam klaster yang sama.

Inisialisasi centroids dan

total jarak (CostTotal = 0)

Baca objek, hitung jarak

objek ke setiap centroid,
tentukan klaster objek
berdasar jarak minimum
dataset di
memori
Hitung total jarak tiap
objek ke centroid-nya
(CostTotal)

Y Object
masih
ada?

Hitung centroid baru dan

Delta_CostTotal
Ganti
centroids

T
Stop?

Simpan keanggotaan objek-objek dan centroids

Gambar 12.3. Algoritma k-Means asli (non-paralel).

 212

Cara untuk menghitung jarak antar objek (atau jarak objek ke centroids) bergantung kepada tipe
nilai dari atribut-atribut objek. Atribut objek dapat bernilai biner (tue/false) atau kategorial
(hijau, merah, hitam, dll) atau numerik/angka. Rumus untuk menhitung jarak antar objek harus
dipilih yang sesuai. Bahasan yang lengkap tentang cara perhitungan antar objek dapat dipelajari
di (Han et al., 2012).

Jika semua atribut objek bertipe numerik, rumus yang sering digunakan adalah jarak Euclidean.
Dalam hal ini, objek dapat direpresentasikan menjadi vektor (contoh x dan y) yang memiliki
atribut ke-1 s/d ke-n. Jika x = (x1, x2, …., xn) dan y = (y1, y2, ….yn), maka jarak x ke y:
i =n
d ( x, y ) =  (x
i =1
i − yi ) 2 (1)

Adapun CostTotal (J) direpresentasikan sebagai:

𝑱 = ∑𝑐𝑖=1 𝐽𝑖 = ∑𝑐𝑖=1(∑𝑘,𝑥𝑘 𝜖𝐺𝑖 𝑑(𝒙𝒌 − 𝒄𝒊 ) (2)

Pada rumus 2 di atas, c = jumlah klaster, xk = objek ke k, ci = centroid ke i, Gi = klaster ke i.

Sedangkan d(xk- ci) = jarak dari objek k ke centroid-nya. Perhitungan ci dilakukan dengan rumus
berikut ini:
1
𝒄𝑖 = ∑𝑘,𝑥𝑘 𝜖𝐺𝑖 𝑥𝑘 (3)
|𝐺𝑖 |

dimana |Gi| menyatakan jumlah objek (anggota) pada klaster ke-i, xk = objek ke k yang menjadi
anggota klaster ke-i. Rumus itu menyatakan bahwa nilai fitur dari objek-objek yang berada
dalam klaster yang sama dirata-rata dan disimpan sebagai centroid klaster tersebut.

Evaluasi Hasil Pengelompokan

Lantas bagaimana kita tahu bahwa hasil pengelompokan “sudah bagus” atau objek-objek
terkelompok dengan benar (objek-objek yang berdekatan berada dalam satu klaster, dan tiap-
tiap klaster saling “berjauhan”)?

Terdapat dua pendekatan dalam mengukur kualitas hasil pengelompokkan, yaitu secara internal
dan eksternal. Bahasan detil tentang metoda untuk mengevaluasi hasil pengelompokan dapat
dipelajari di buku (Han et al., 2012). Prinsip dari 2 metoda yang dapat digunakan diberikan di
bawah ini:
1. Pengukuran internal: Salah satu pendekatannya dilakukan dengan menghitung koefisien
Silhoutte untuk tiap objek, s(i). Nilai s(i) ini berada pada rentang -1 s/d 1. Makin dekat ke 1,
objek makin terkelompok dengan baik. Jika s(i) bernilai negatif, objek terkelompok “dengan
salah”. Untuk mengukur kualitas kelompok secara keseluruhan, nilai s(i) dari semua objek
 213

dirata-rata, lalu disimpan sebagai s. Jika s makin mendekati 1, maka kualitas hasil clustering
makin baik. Namun demikian, jika jumlah objek tidak terlalu banyak dan semua nilai s(i)
masih mungkin untuk divisualisasi (diplot), maka seluruh koefisien dapat diplot untuk
dianalisis (misalnya untuk diamati prosentase objek-objek dengan nilai s(i) negatif).
2. Pengukuran eksternal: Untuk mengukur kualitas hasil pengelompokkan secara eksternal,
dibutuhkan himpunan data “ground-truth” yang berisi objek-objek yang sudah “terlabeli”
dengan kelompok-kelompok yang sebenarnya. Klaster dari tiap objek hasil dari clustering,
dibandingkan dengan label tersebut, lalu dihitung berapa jumlah objek yang terkelompok
dengan benar dan salah. Dari sini, lalu dapat hitung purity (kemurnian) dari tiap klaster
dan/atau akurasinya. Makin besar nilai purity dan akurasinya, makin baik hasil
pengelompokan. Metoda ini lebih cocok digunakan jika hasil pengelompokkan (misalnya,
centroids) dijadikan model, dimana model lalu digunakan untuk menentukan kelompok dari
objek lain (yang tidak disertakan dalam pembuatan model). Namun demikian, teknik
clustering lebih banyak digunakan pada unsupervised learning, dimana himpunan data
“ground-truth” tidak tersedia. (Jika data “ground-truth” tersedia, umumnya digunakan
teknik klasifikasi.)

Sebagaimana telah dibahas sebelumnya, algoritma k-Means mensyaratkan pengguna untuk

menentukan jumlah kelompok (k). Dengan kata lain, pengguna harus memasukkan nilai k
beserta himpunan data sebagai masukan dari k-Means. Lalu bagaimana cara memilih k yang
tepat? Pemilihan tersebut dapat dilakukan dengan metoda sebagai berikut:
1. Jika ukuran himpunan data tidak terlalu besar (misalnya sampai puluhan megabyte),
pengelompokkan dapat dilakukan berulang-ulang dengan nilai k yang berbeda-beda.
Koefisien Silhoutte (tiap objek dan rata-ratanya) dari hasil pengelompokkan, lalu
dibandingkan. Jumlah kelompok terbaik dipilih dari k yang memberikan nilai koefisien
Silhoutte (rata-rata) yang terbesar.
2. Jika ukuran himpuan data besar dan pengelompokan yang berulang-ulang di atas dinilai
tidak efisien (atau tidak feasible), dapat dilakukan sampling secara acak terhadap himpunan
data untuk menghasilkan sub-himpunan data dengan ukuran lebih kecil namun dipandang
merepresentasikan himpunan data aslinya. Kemudian, sub-himpunan data ini
dikelompokkan berulang-ulang dengan nilai k yang berbeda seperti cara nomor 1. Nilai k
yang diperoleh ini lalu digunakan untuk mengelompokkan himpuan data yang sebenarnya.

12.4. Algoritma k-Means Paralel untuk Big Data

Sebagaimana telah disebutkan, himpunan data yang dikelompokkan dapat berukuran besar atau
sangat besar dan mencapai ukuran ratusan (atau lebih) gigabyte. Algoritma k-Means non-paralel
 214

(yang orisinil) dirancang untuk dijalankan pada sebuah komputer (sebuah core), dengan
memanfaatkan memori di komputer itu saja. Kapasitas memori yang dapat digunakan untuk
menyimpan himpunan data biasanya ditentukan oleh sistem operasi atau konfigurasi tertentu
(misalnya, kalau menggunakan Java Virtual Memory, yang disingkat JVM, maka memori
maksimal ditentukan oleh konfigurasi pada JVM). Dengan demikian, k-Means non-paralel tidak
dapat menangani himpunan data yang berukuran lebih besar dari ruang memori yang
dialokasikan untuk k-Meas.

Untuk menangani data dengan ukuran sangat besar, k-Means non-paralel telah dikembangkan
untuk lingkungan sistem tersebar Hadoop dan Spark yang dibahas di bawah ini. Jika pada
algoritma k-Means non-paralel yang digunakan untuk mengelompokkan himpunan data
berukuran kecil sampai besar (sejauh yang dapat ditangani komputasi pada sebuah komputer)
nomor klaster keanggotaan tiap objek direkam dan dijadikan sebagai keluaran algoritma, maka
pada pengelompokan big data tidak demikian. Karena jumlah objek dapat mencapai jutaan
bahkan milyardan, informasi tentang klaster dari tiap objek menjadi tidak atau kurang
bermakna. Hasil akhir utama dari k-Means paralel (untuk big data) adalah centroids dari klaster-
klaster. Centroids ini kemudian dapat dijadikan model dan digunakan untuk mengelompokkan
objek-objek lain (yang tidak digunakan untuk menghitung centroids).

Pada subbab ini dibahas algoritma k-Means paralel untuk sistem big data Hadoop dan Spark.
Bahasan mengenai Hadoop dan Spark dapat dibaca pada Bab 10 dan Bab 11.

12.4.1. Algoritma k-Means Paralel untuk Lingkungan Sistem Hadoop

Sebagaimana ditunjukkan pada Gambar 12.2 (langkah-langkah) dan Gambar 12.3 (flowchart),
proses pengelompokan objek-objek ke klaster dilakukan berulang-ulang (secara iteratif) sampai
“kondisi stabil” dicapai, dimana tidak ada atau mayoritas objek sudah tidak berpindah klaster
lagi. Jumlah perulangan atau iterasi ini dipengaruhi oleh centroid inisial, yang pada iterasi ke-1
digunakan untuk menentukan objek-objek masuk ke kelompok yang mana. Makin dekat
centroid inisial ke centroid yang sebenarnya, yang dicapai pada kondisi stabil, maka makin
sedikit jumlah iterasi yang perlu dijalankan untuk mencapai kondisi stabil. Sehubungan dengan
hal ini, beberapa teknik atau algoritma untuk menentukan/menghitung centroid inisial telah
dikembangkan.

Salah satu cara penentuan centroid awal adalah dengan mengelompokkan sebagian himpunan
data yang diperoleh melalu teknik sampling secara acak. Karena data hasil sampling berukuran
jauh lebih kecil daripada data asli, maka komputasi untuk mendapatkan centroid final pada
sampel data dapat dilakukan dengan lebih cepat. Centroid dari hasil pengelompokan dengan
 215

sampel data ini, kemudian dijadikan centroid inisial untuk mengelompokkan keseluruhan
himpunan data.

Untuk mengelompokkan big data, penentuan centroid inisial ini penting, karena tiap iterasi
cost/biaya komputasi yang dibutuhkan besar (terkait dengan penggunaan CPU atau core dan
memori komputer yang dapat berjumlah sangat banyak).

Algoritma k-Means pada sistem tersebar Hadoop dapat dijelaskan dengan contoh pada Gambar
12.4 sebagai berikut (Zhao, Ma & Q. He, 2009; Moertini & L. Venica, 2017):
Perhitungan centroid inisial dilakukan dengan mengelompokkan sample dari big data yang
tersimpan sebagai blok-blok pada HDFS. Centroid hasil pengelompokan ini lalu dijadikan
centroid inisial.
Oleh program Job, nilai-nilai inisial centroid disebar ke semua node data (slave node) yang akan
menjalankan map(). Setelah itu, map() dijalankan untuk membaca baris-demi baris (atau objek
demi objek) pada blok data lokal (blok data yang tersimpan di node data tempat map()
dijalankan). Jarak dari objek ini ke setiap centroid (titik pusat) dihitung. Objek akan
“dimasukkan” ke kelompok dengan jarak terdekat. Fungsi map() lalu mengeluarkan pasangan
key-value, dimana key berisi indeks dari centroid (misalnya 0, 1, 2, dst), value berisi objek (dapat
berformat vektor) dan nilai jarak dari objek ke centroid-nya.

Hadoop lalu melakukan proses yang dinamakan “shuffle dan sort”. Keluaran map() yang
memiliki nilai key yang sama akan dikumpulkan menjadi satu, lalu pasangan nilai value (objek
dan jarak) dari key-key tersebut diurutkan dalam bentuk/format list.
Selanjutnya, setiap reduce() menerima satu atau lebih dari nilai key beserta pasangannya yang
berupa list value, yang berisi objek-objek yang terkelompok pada kelompok bernomor key (di
sini, key merepresentasikan nomor kelompok, misalnya kelompok 0, 1, 2, dst).
Setelah reduce() menerima nilai objek-objek dari sebuah key, reduce() akan menghitung titik
pusat (centroid) baru untuk kelompok dengan nomor key tersebut dan jumlah total jarak objek-
objek ke masing-masing centroid.

Selanjutnya, program Job akan menjumlahkan jarak total keluaran tiap reducer menjadi jarak
total (CostTotal). Jarak total digunakan untuk mencek apakah kelompok baru yang terbentuk
sudah “stabil” (dibandingkan kelompok yang terbentuk pada iterasi sebelumnya). Nilai epsilon
akan dihitung dengan mengurangi total jarak pada iterasi sekarang dengan total jarak pada
iterasi sebelumnya (Delta_CostTotal). Jika nilai Delta_CostTotal sudah lebih kecil dari nilai yang
didefinisikan atau jumlah iterasi sudah mencapai iterasi maksimum, maka iterasi akan
dihentikan dan hasil komputasi centroids yang dilakukan oleh reducer() menjadi centroids versi
 216

final lalu “dikeluarkan” atau disimpan sebagai file HDFS. Jika belum, nilai centroids yang baru
akan “disebar” ke node-node data, lalu fungsi map() dan reduce() dijalankan lagi.

Hitung
centroid Big data di HDFS
inisial

C1 ..
C2
Tiap map() membaca
centroids setiap objek dari blok
HDFS, hitung jarak objek
map() map() map() ke setiap centroid,
tentukan klaster objek
key = index-centroid,
value = objek & jarak objek ke centroid Keluaran nilai key-value
tiap map() ditulis ke disk

shuffle & sort

index-centroid-1, Tiap reduce() membaca

index-centroid-2, key-list(values) dari disk
objek-objek pada
objek-objek pada kelompok 2
kelompok 1

reduce() reduce() Tiap reduce() menghitung

centroid baru dan Cost
untuk klaster tertentu

Hitung CostTotal, Delta_CostTotal,

Program Job putuskan apakah iterasi dilanjutkan:
Jika lanjut, sebar centroid baru
sebelum semua map() dijalankan lagi.
Jika berhenti, simpan centroids

Gambar 12.4. Ilustrasi algoritma k-Means paralel pada Hadoop dengan jumlah kelompok = 2.

Untuk mengurangi trafik pada jaringan pada proses shuffle dan sort, dapat ditambahkan fungsi
combine(). Fungsi ini berperan dalam mengumpulkan value-value dengan nilai key yang sama
secara lokal (di sebuah data node). Keluaran combine() berupa pasangan key dan value-value
yang lalu “diumpankan” ke proses shuffle dan sort. Dengan memanfaatkan combine(), jumlah
pasangan key-value yang dikirim ke proses shuffle dan sort berkurang, sehingga mengurangi
trafik pada jaringan Hadoop dan dapat mempercepat eksekusi algoritma k-Means.

Hal yang menjadi kelemahan pada framework MapReduce Hadoop adalah:

1. Pada setiap iterasi, setiap map() membaca blok HDFS dari disk.
2. Pada tahap shuffle dan sort, keluaran dari setiap map() ditulis pada disk. Masing-masing
reduce() yang menangani nilai key tertentu lalu membaca nilai-nilai value dari disk.
 217

3. Pada akhir iterasi: centroid hasil komputasi pada akhir iterasi (sebagai keluaran reduce())
juga selalu disimpan di disk.
Pembacaan dan penulisan data berukuran sangat besar dari dan ke disk secara berulang-ulang
tersebut menyebabkan “biaya” yang tinggi pada algoritma k-Means paralel pada Hadoop. Proses
clustering big data menjadi tidak efisien.

12.4.2. Algoritma k-Means Paralel untuk Lingkungan Sistem Spark

Sebagaimana telah dijelaskan pada Bab 10, Spark dikembangkan untuk memfasilitasi algoritma-
algoritma yang membutuhkan komputasi intensif dan iteratif. Salah satu algoritma tersebut
adalah k-Means, yang sudah menjadi fungsi pada library MLLib maupun ML pada Spark (Karau
et al., 2015; Karau & Warren, 2017). Pada Spark, himpunan big data (dalam bentuk blok-blok
HDFS) dibaca dari disk lalu disimpan di memori-memori komputer yang bertindah sebagai
worker dalam bentuk partisi RDD (Resillient Distributed Dataset). Jika digunakan konfigurasi
default Spark, tiap blok HDFS akan dibuatkan 1 RDD. RDD tersebut dapat disimpan di memori
para worker terus selama aplikasi dijalankan (dengan menggunakan fungsi persist).

Langkah-langkah algoritma k-Means paralel pada Spark (lihat Gambar 12.5):

Analogi dengan k-Means paralel pada Hadoop, perhitungan centroid inisial dilakukan dengan
mengelompokkan sample dari big data (komputasi dapat dilakukan dengan k-Means non-
paralel). Centroid hasil pengelompokan ini lalu dijadikan centroid inisial dan “disebar” ke para
worker.
Tiap mapPartition() pada worker membaca tiap objek dari sebuah RDD, menentukan
kelompoknya, menghitung jarak akumulatasi (cost) dari tiap objek ke centroid-nya, lalu
mengeluarkan pasangan key-value, dimana key = indeks klaster, value = jumlah objek dan cost.
Pemanggilan reduceByKey() pada tiap worker mengakibatkan Spark melakukan proses shuffle
sedemikian rupa sehingga setiap reduceByKey() hanya menangani nilai key tertentu beserta
seluruh value untuk key tersebut. Komputasi yang dilakukan reduceByKey() adalah
menjumlahkan total anggota (NTotal) dan jarak akumulatif tiap klaster (CostTotal).
Hasil perhitungan tiap reduceByKey() pada semua worker lalu dikumpulkan, kemudian
centroids yang baru dihitung. Jika CostTotal saat ini dikurangi CostTotal pada iterasi sebelumnya
bernilai lebih kecil atau sama dengan batas minimum (Eps) atau iterasi maksimum sudah
dicapai, maka iterasi dihentikan. Jika kondisi tersebut tidak dipenuhi, maka centroids diperbarui
(diganti dengan hasil perhitungan pada iterasi ini) dan “disebar” ke para worker, lalu iterasi
diulangi lagi.
 218

Big data di HDFS

Hitung
centroid
inisial RDD-1 RDD-2 RDD-n

centroids
C1 ..
C2

mapPartition:
mP-1(): mP-2(): mP-n():
Untuk tiap objek: Melakukan Melakukan
- cari jarak terdekat ke langkah yang langkah yang
cen troids sama dengan sama dengan
- tentukan klaster objek mapP artition-1() mapP artition-1()
Hitu ng jarak akumu latif
objek-objek ke
cen troid-nya (Cost[])
Hitu ng ju mlah objek
tiap klaster (Nclus[])
Bu at pasangan key -
value: i - Nclus-i, Cost-i

reduceByKey:
shuffle

rBK-1(): rBK-2():
Untuk klaster 1 yan g Untuk klaster 2 yang
ditangani reducer ini: ditangan i reducer ini:
Baca list values lalu Baca list values lalu
- Jumlahkan total anggota - Jumlahkan total an ggota
(Ntotal-1) (Ntotal-2)
- Jumlahkan jarak - Jumlahkan jarak
akumulatif (CostTotal-1) aku mulatif (CostTotal-2)

Kumpulkan NTotal & CosTotal dari 2 reducer

Hitung centroid baru & Delta_CostTotal

Perbarui centroids

Stop?

Simpan centroids

Gambar 12.5. Algoritma k-Means paralel pada Spark dengan kasus jumlah kelompok = 2
(keterangan: mP = mapPartition, rBK = reduceByKey).
 219

12.5. Pengembangan Algoritma k-Means Paralel

12.5.1. Algoritma k-Means untuk Lingkungan Sistem Hadoop

Pada Subbab 12.4 dibahas algoritma k-Means yang dikembangkan untuk lingkungan Hadoop,
dimana pada akhir komputasi menghasilkan model yang berupa centroids atau “titik-titik
tengah” dari klaster-klaster. Model tersebut lalu dapat digunakan untuk memprediksi kelompok
dari objek yang tidak menjadi bagian dari himpunan data yang digunakan untuk menghitung
centroids atau belum digunakan pada proses clustering.

Sebagaimana dipaparkan pada (Han et al., 2012), analisis klaster merupakan salah satu metoda
deskriptif. Sesuai dengan namanya, hasil akhir metoda ini adalah “deskripsi dari himpunan data”
yang berupa nilai-nilai ringkasan statistik. Nilai-nilai itu lalu dapat dievaluasi dan/atau
dibandingkan satu dengan yang lain, dan apabila didapati ada nilai-nilai yang “menarik” lalu
dapat dijadikan pola-pola klaster yang berharga atau bermanfaat (contoh pola sudah diberikan
pada Subbab 12.2).

Nilai-nilai ringkasan statistik yang berpotensi untuk dijadikan pola-pola klaster tersebut apa
saja? Pada (Tsiptsis dan Chorianopoulos, 2009; Chius dan Tavella, 2011) dirumuskan bahwa
nilai ringkasan yang dihitung dari tiap klaster dapat berupa gabungan dari:
• Centroids (nilai rata-rata tiap atribut/fitur)
• Nilai minimum, maximum, standard deviasi dari nilai atribut
• Prosentase objek yang memiliki nilai atribut tertentu
• Jumlah objek yang menjadi anggota.

Berikut ini diberikan sebuah contoh ringkasan statistik. Sebuah bank bermaksud meningkatkan
pemasaran produk-produk yang dijual (misalnya berbagai kredit) dengan menarget calon-calon
nasabah yang potensial. Bank memiliki data nasabah-nasabah beserta kredit yang diambil. Data
tersebut dapat disiapkan untuk dikelompokkan. Di sini, tiap objek mewakili satu nasabah. Dari
hasil penyiapan data, objek-objek pada himpundan data yang dikelompokkan memiliki 5 fitur,
yaitu: Nilai kredit (NK), umur (U), status nikah (SN), jumlah anak (JA) dan pendapatan (P). Setiap
nilai fitur “dinormalisasi” dan memiliki nilai antara 0 s/d 1. (Keterangan: Normalisasi,
transformasi nilai fitur agar memiliki rentang nilai yang sama ini dimaksudkan agar fitur-fitur
berkontribusi setara pada perhitungan jarak objek ke centroidnya atau tidak ada fitur-fitur yang
mendominasi).

Klaster-1:
• Centroids (rata-rata nilai fitur): NK = 0.85, U = 0.81, SN = 0.72, JA = 0.79, P = 0.97
 220

• Nilai minimum: NK = 0.79, U = 0.71, SN = 0.62, JA = 0.68, P = 0.88

• Nilai maksimum: NK = 0.95, U = 0.91, SN = 0.89, JA = 0.96, P = 1.0
• Deviasi: NK = 0.09, U = 0.07, SN = 0.12, JA = 0.01, P = 0.08
• Jumlah objek: 302

Klaster-2:
• Centroids (rata-rata nilai fitur): NK = 0.62, U = 0.31, SN = 0.32, JA = 0.09, P = 0.93
• Nilai minimum: NK = 0.41, U = 0.26, SN = 0.0, JA = 0.0, P = 0.68
• Nilai maksimum: NK = 0.75, U = 0.39, SN = 0.39, JA = 0.2, P = 0.99
• Deviasi: NK = 0.18, U = 0.06, SN = 0.2, JA = 0.01, P = 0.18
• Jumlah objek: 191

Dari kedua contoh klaster di atas, Klaster-1 merepresentasikan nasabah-nasabah umur sekitar
tengah baya, menikah, punya penghasilan dengan rentang besar dan mengambil kredit yang
besar pula. Sebaliknya, Klaster-2, umur sekitar 30-an, sebagian menikah, hanya sedikit yang
sudah memiliki anak, memiliki pendapatan besar, dan mengambil kredit bernilai sedang. Untuk
tujuan pemasaran produk kredit bank, Klaster-1 dipandang menjadi pola yang berharga.
Ditengarai bahwa kredit yang diambil nasabah-nasabah tengah baya tersebut ternyata
digunakan untuk membuka dan menjalankan usaha mandiri. Berdasar temuan pola berharga
ini, bank lalu dapat menarget orang-orang tengah baya dengan penghasilan tinggi, menikah dan
punya anak untuk ditawari produk kredit usaha (untuk berwirausaha).

Pada pengembangan k-Means paralel untuk Hadoop, standar deviasi pada klaster dihitung
secara aproksimasi. Perhitungan deviasi membutuhkan komputasi pengurangan nilai variabel
dengan rata-rata nilai variabel. Ini membutuhkan 2 iterasi: Iterasi pertama untuk menghitung
rata-rata, yang kedua untuk mengurangi selisih nilai variabel dengan rata-rata. Di sini, variabel
adalah fitur objek. Dalam konteks big data, jumlah objek mencapai jutaan atau bahkan milyardan
sehingga komputasi menjadi mahal, terlebih dengan mempertimbangkan bahwa komputasi k-
Means sendiri sudah bersifat iteratif.
Karena itu, komputasi aproksimasi standar deviasi, dilakukan dengan mengambil nilai rata-rata
pada iterasi sebelumnya. Dengan demikian, tidak ada iterasi tambahan pada k-Means pada
Hadoop.

Pada Gambar 12.4 telah ditunjukkan algoritma k-Means paralel yang berbasis MapReduce untuk
Hadoop. Untuk menambahkan komputasi ringkasan statistik di tiap klaster, yang dilakukan
adalah menambahkan komputasi pada reduce() dengan rancangan algoritma yang diberikan di
bawah ini (Moertini & Venica, 2016).
 221

Algoritma: reduce pada k-Means paralel

Input: key, listVal, prevcenters dimana key = indeks klaster, listVal = list value yang terurut, prevcenters = centroids
Output: pasangan <key’, value’), key’ = indeks klaster value’ = string gabungan dari centers[] (centroid semua
klaster), jumlah objek pada tiap klaster, countObj, nilai minimum, maximum, rata-rata, deviasi standar tiap atribut
pada klaster, minAtrVal, maxAtrVal, StdCluster; cost untuk tiap klaster, J
Step:
1. Inisialisasi minAtrVal[], maxAtrVal[], SumDiffAtrPrevCenter[], SumAtr[], StdDev[][], centers[]
2. countObj = 0; J = 0;
3. While(ListVal.hasNext())
4. Ambil nilai-nilai atribut dan dist dari value
5. Tiap nilai atribut digunakan untuk menghitung atau memperbarui minAtrVal[], maxAtrVal[],
SumDiffAtrPrevCenter[], SumAtr[], StdDev[][], centers[]
6. J = J + dist;
7. Hitung centroids baru dengan membagi SumAtr[] dengan countObj lalu simpan di centers
8. Hitung standar deviasi aproksimasi untuk tiap atribut dengan menggunakan SumDiffAtrPrevCenter lalu
simpan di StdDev
9. value’ = gabungan dari centers[],countObj, minAtrVal, maxAtrVal, StdCluster, J
10. keluarkan key-value’

Contoh pemanfaatan algoritma k-Means yang melakukan komputasi ringkasan statistik di tiap
klaster diberikan pada (Moertini & L. Venica, 2017). Pada eksperimen di situ, big data yang
penulis gunakan adalah data cuaca yang diunduh dari website NOAA (National Oceanic and
Atmospheric Administration) yang menyediakan big data hasil perekaman sensor cuaca dari
berbagai negara.

12.5.2. Algoritma k-Means untuk Lingkungan Sistem Spark

Karena k-Means paralel berbasis MapReduce pada Hadoop kurang efisien dalam
mengelompokkan big data, penulis telah mengembangkan k-Means pada Spark (Gambar 12.5)
untuk menghitung ringkasan statistik di tiap klaster. Pengembangan dilakukan dengan
memodifikasi algoritma pada mapPartition(), reduceByKey() maupun pada program utama,
dengan penjelasan di bawah ini:
• Pada mapPartition(): Pada pasangan key-value yang dikeluarkan, value disertai dengan
nilai-nilai fitur dari objek. Dengan demikian, value yang dikeluarkan adalah: indeks klaster,
jarak objek ke centroid-nya dan seluruh nilai fitur objek.
• Pada reduceByKey(): Selain menghitung jumlah total anggota dan jarak akumulatif pada
sebuah klaster, satu task reduceByKey() juga menghitung nilai minimum, maksimum dan
standar deviasi aproksimasi dari setiap fitur objek di sebuah klaster.
• Pada program utama (driver): Setelah mengumpulkan keluaran dari semua reduceByKey(),
menghitung centroid baru dan Delta_CostTotal, jika iterasi tidak dilanjutkan lagi maka data
yang disimpan (ke disk) adalah ringkasan statistik dari tiap klaster.
 222

12.5.3. Perbandingan Kinerja k-Means pada Hadoop vs Spark

Eksperimen untuk mengelompokan big data studi kasus dan membandingkan kinerja,
khususnya kecepatan eksekusi, algoritma k-Means untuk lingkungan Hadoop dan Spark (yang
telah dikembangkan penulis) dilakukan pada jaringan dengan 11 komputer. Hadoop dijalankan
dengan Yarn yang bertugas untuk memanajemen sumber daya pada komputer-komputer dan
menjadwalkan tugas-tugas (tasks) berupa fungsi-fungsi map() dan reduce(). Satu komputer
berperan sebagai master dan sisanya sebagai node data (Gambar 12.6) tempat map() dan
reduce() dijalankan secara paralel dengan mengakses blok-blok HDFS yang tersimpan di disk
pada node ini. Spark juga dikonfigurasi untuk berjalan di atas Yarn dan mengakses file-file HDFS
pada Hadoop. Bagi Spark, node data pada Hadoop dapat menjadi worker tempat menjalankan
tugas-tugas mapPartition() dan reduceByKey() secara paralel. Dalam membaca file HDFS,
(secara default) 1 blok HDFS di worker dijadikan 1 RDD.

Namenode
(Master)

Data Node Data Node Data Node

(Worker-1) (Worker-2) (Worker-10)

Gambar 12.6. Jaringan klaster Hadoop untuk eksperimen.

Eksperimen Perbandingan Kinerja

Secara teoritis, algoritma k-Means paralel pada Spark dipastikan lebih cepat daripada k-Means
paralel pada Hadoop. Namun, bagaimana perbandingan kecepatan eksekusi keduanya? Untuk
mengelompokan big data tertentu, apakah k-Means Hadoop tetap dapat digunakan dengan
cukup efisien? Untuk menjawab pertanyaan ini, penulis eksperimen untuk membandingkan
kinerja keduanya.

Data studi kasus yang digunakan untuk eksperimen adalah hasil rekaman penggunaan energi
listrik di sebuah rumah, yang diunduh dari https://archive.ics.uci.edu/ml/datasets/. Data
tersebut terdiri dari 2.075.259 hasil pengukuran (rekord) pada Desember 2006 s/d November
 223

2010 (47 bulan) dan berukuran 132 Mb. Contoh isi data yang berupa rekord-rekord hasil
pengukuran adalah:
8/6/2007;18:39:00;4.072;0.242;236.750;17.200;37.000;1.000;19.000
8/6/2007;18:40:00;3.754;0.222;236.920;15.800;37.000;2.000;17.000
8/6/2007;18:41:00;3.612;0.076;237.640;15.200;38.000;2.000;17.000
8/6/2007;18:42:00;3.612;0.076;237.820;15.200;37.000;1.000;18.000

Sebagaimana dipaparkan pada (Moertini & L. Venica, 2017), penulis juga mengelompokkan data
tersebut sebagai contoh kasus pemanfaatan k-Means paralel pada Hadoop.

Untuk pengujian kecepatan, himpunan data yang telah di-praolah (sehingga siap untuk
diumpankan ke k-Means) direplikasi beberapa kali sehingga mencapai ukuran 512 Mb dan 1 Gb.
Pengelompokan data dilakukan dengan jumlah klaster 3 dan 9 pada jaringan klaster Hadoop
dengan berturun-turut menggunakan 1, 5 dan 10 komputer data node atau core. Hasil
eksperimen dipaparkan pada Tabel 12.2, Gambar 12.7, Tabel 12.3 dan Gambar 12.8.

Tabel 12.2 Waktu eksekusi k-Means paralel untuk memproses himpunan data dengan 5 fitur dan
berukuran 512 Mb.

Jumlah klaster = 3 Jumlah klaster = 9

Jumlah k-Means k-Means k-Means k-Means Spark
Slave/Core Hadoop Spark Hadoop (detik)
(detik) (detik) (detik)
1 6,179 981 25,422 1,244
5 5,842 198 18,479 281
10 5,348 143 18,342 208
 224

Gambar 12.7. Perbandingan waktu eksekusi k-Means Hadoop vs Spark dengan data 512 Mb.

Tabel 12.3. Waktu eksekusi k-Means paralel untuk memproses himpunan data dengan 10 fitur
dan berukuran 1 Gb.
Jumlah klaster = 3 Jumlah klaster = 9
Jumlah k-Means k-Means k-Means k-Means
Slave/Core Hadoop Spark Hadoop Spark
(detik) (detik) (detik) (detik)
1 17,063 2,016 22,126 2,071
5 11,496 304 13,756 292
10 10,415 255 13,492 209
 225

Gambar 12.8.. Perbandingan waktu eksekusi k-Means Hadoop vs Spark dengan data 1 Gb.

Pada dua tabel dan gambar di atas, baik untuk data berukuran 512 Mb maupun 1 Gb, dimana k-
Means dijalankan pada jaringan Hadoop dan Spark dengan Yarn, kecepatan eksekusi k-Means
paralel Spark berkisar antara 8 sampai 90 kali. Penambahan jumlah core (yang identik dengan
tasks paralel yang dijalankan) pada Spark berdampak signifikan terhadap peningkatan
kecepatan eksekusi. Pada Hadoop, penambahan jumlah workder node hanya sedikit mengurangi
waktu eksekusi. “Biaya” proses pembacaan dan penulisan ke disk, juga proses shuffling dan
sorting (sebelum pasangan data key-value diproses oleh fungsi reduce()) menjadi penyebab dari
kelambatan eksekusi k-Means Hadoop.

Dari hasil perbandingan di atas, dapat disimpulkan bahwa pengelompokan big data lebih cocok
dilakukan dengan menggunakan k-Means paralel pada Spark.

12.6. Penutup

Bab ini telah membahas cara kerja algoritma k-Means asli (yang dapat digunakan untuk
mengelompokan non-big-data) dan pengembangannya menjadi algoritma paralel untuk
memproses big data di lingkungan Hadoop dan Spark. Dari hasil eksperimen perbandingan
 226

kecepatan eksekusi, ternyata k-Means paralel untuk lingkungan Spark secara umum jauh lebih
cepat dibandingkan k-Means pada Hadoop. Dengan demikian, k-Means paralel Spark lebih cocok
untuk manangani big data.

Jika ukuran himpunan data relatif kecil dan jumlah objek-objek yang dikelompokan mencapai
ribuan, juga dibutuhkan untuk “melabeli” tiap objek dengan indeks/nomor klasternya, maka
dapat dipilih k-Means asli (non-paralel) yang sudah diimplementasikan pada beberapa
perangkat lunak (misalnya Matlab, Weka, RapidMiner, dll) dan library bahasa Java, Python, dll.

Tujuan pengelompokan big data pada umumnya adalah untuk mendapatkan model atau pola
dari tiap klaster. Karena jumlah objek dapat mencapai jutaan bahkan milyaran, maka hasil akhir
berupa pelabelan tiap objek menjadi kurang bermanfaat. (Namun, jika dibutuhkan, yang
digunakan biasanya teknik klasifikasi yang dapat memberikan hasil pelabelan kelas yang lebih
akurat. Dalam hal ini dibutuhkan data training, dimana tiap objek sudah dilabeli dengan
kelasnya).

Hal-hal penting untuk diperhatikan ketika memanfaatkan algoritma k-Means:

1. Penyiapan data: Tahap ini merupakan tahap yang krusial dan penting untuk dilakukan
dengan benar. Data “mentah” mungkin masih “kotor”, tidak konsisten, ada yang hilang, atau
nilai-nilainya ada yang tidak cocok untuk ditangani k-Means. Selain itu, data dapat memiliki
banyak atribut/kolom yang jika dikaitkan dengan tujuan pengelompan, ada yang tidak
relevan. Pembersihan, transformasi data dan pemilihan dan/atau pembuatan fitur-fitur
perlu dilakukan sedemikian rupa untuk menghasilkan himpunan data berkualitas bagus
yang siap untuk diumpankan ke k-Means (dan diprediksi dapat menghasilkan luaran yang
diharapkan).
2. Pemilihan jumlah kelompok: Pada k-Means, untuk dapat menghasilkan klaster-klaster yang
bagus (objek-objek dalam satu klaster “berdekatan” dan “berjauhan” dengan objek-objek di
klaster yang lain), jumlah kelompok yang tepat atau terbaik harus “dicari” (cara mencari ini
sudah dibahas sebelumnya.)
3. Evaluasi dan interpretasi hasil pengelompokan: Hasil pengelompokkan (label klaster pada
tiap objek, centroids dan komponen-komponen pola klaster lainnya) perlu dievaluasi dan
diinterpretasikan apakah sudah dapat menjawab tujuan pengelompokan data. Jika ternyata
belum menjawab atau belum memberikan solusi terhadap tujuan, maka proses
pengelompokan perlu diulang lagi mulai dari tahap penyiapan data.

Metoda penyiapan data, evaluasi dan interpretasi hasil pengelompokan dapat dicari dari
literatur-literatur data mining dan Machine Learning beserta aplikasinya. Jika pengelompokan
 227

akan memanfaatkan library Machine Learning pada Spark (MLLib atau ML), tahapan dapat
mengacu ke referensi (Karau & Warren, 2017).

Ucapan Terima Kasih

Ucapan terima kasih ditujukan kepada Direktorat Riset dan Pengabdian Masyarakat, Direktorat
Jenderal Penguatan Riset dan Pengembangan yang telah mendanai penelitian ini melalui skema
Penelitian Dasar Unggulan Perguruan Tinggi (PDUPT), tahun anggaran 2020, dengan nomor
kontrak III/LPPM/2020-04/107-PE-S.

Referensi
(Chius dan Tavella, 2011) S. Chius and D. Tavella; Data Mining and Market Intelligent for Optimal
Marketing Returns, UK: Routledge Pub., 2011.
(Han et al., 2012) J. Han, M. Kamber and J. Pei, Data Mining Concepts and Techniques 3rd Ed., USA: The
Morgan Kaufmann Publ., 2012.
(Holmes, 2012) A. Holmes, Hadoop in Practice, USA: Manning Publications Co., 2012.
(Karau et al., 2015) Holden Karau, Andy Konwinski, Patrick Wendell, and Matei Zaharia, Learning Spark,
O’Reilly Media, Inc., 2015
(Karau & Warren, 2017) Holden Karau and Rachel Warren, High Performance Spark, O’Reilly Media, Inc.,
USA, 2017.
(Moertini & L. Venica, 2017) V. S. Moertini and L. Venica, Parallel k-Means for Big Data: On Enhancing Its
Cluster Metrics and Patterns, Journal of Theoretical and Applied Information Technology, Vol. 95, No.
8, 2017, Pp. 1844-1857.
(Moertini et al., 2018) V. S. Moertini, G. W. Suarjana, L. Venica and G. Karya, Big Data Reduction Technique
using Parallel Hierarchical Agglomerative Clustering, IAENG International Journal of Computer
Science, Vol. 45. No. 1, 2018.
(Moertini & Venica, 2016) V. S. Moertini, L. Venica, “Enhancing parallel k-means using map reduce for
discovering knowledge from big data”, in Proc. of. 2016 IEEE Intl. Conf. on Cloud Computing and Big
Data Analysis (ICCCBDA 2016), Chengdu China, 4-7 July 2016, pp. 81-87.
(Sammer, 2012) E. Sammer, Hadoop Operations, USA: O’Reilly Media, Inc., 2012.
(Tsiptsis dan Chorianopoulos, 2009) K. Tsiptsis and A. Chorianopoulos, Data Mining Techniques in CRM:
Inside Customer Segmentation, UK: John Wiley and Sons, L., 2009.
(Zhao, Ma dan Q. He, 2009) W. Zhao, H. Ma and Q. He, “Parallel k-means clustering based on mapreduce”,
CloudCom 2009, LNCS 5931, pp. 674–679, Berlin Heidelberg: Springer-Verlag, 2009.
(URL-cluster-1) Data Mining - Cluster Analysis,
https://www.tutorialspoint.com/data_mining/dm_cluster_analysis.htm (diakses 17 Februari 2020)
(URL-cluster-2) What is Clustering in Data Mining,
https://bigdata-madesimple.com/what-is-clustering-in-data-mining/ (diakses 17 Februari 2020)