BAB II KAJIAN PUSTAKA

BAB II KAJIAN PUSTAKA

Sumber-sumber yang digunakan dalam pembuatan tugas akhir, baik yang diambil dari buku, internet, maupun jurnal diuraikan secara terperinci pada Bab Tinjuan Pustaka. Konsep dan definisi dari data mining serta hubungannya dengan customer relationship management melalui atribut recency, frequency dan monetary, penjelasan Metode K-Means dan Particle Swarm Optimization dijelaskan pula pada Bab ini.

2.1

State of the Art Penelitian mengenai data mining yang berhubungan dengan proses

segmentasi pelanggan telah beberepa kali dilakukan. Penelitian segmentasi pelanggan menggunakan Metode Fuzzy C-Means dan Fuzzy Subtractive serta Model Fuzzy Recency Frequency Monetary (RFM) pada perusahaan retail diteliti oleh Yohana Nugraheni. Pada penelitian tersebut diungkapkan bahwa kekurangan dari Algoritma Fuzzy Subratctive, yaitu tidak dapat membentuk cluster yang tergolong dalam label superstar dan golden customer, sehingga dapat dikatakan Algoritma Fuzzy Subtractive Clustering kurang mendukung proses data mining pada perusahaan retail untuk mendapatkan konsumen potensial (Yohana Nugrahaeni 2011, h. 123). Penelitian sejenis juga dilakukan oleh Ni Putu Putri Yuliari dengan Metode Fuzzy C-Means dan Fuzzy RFM untuk segmentasi pelanggan pada perusahaan furniture. Pada penelitian tersebut diungkapkan bahwa Metode Fuzzy C-Means dapat menghasilkan cluster yang tergolong superstar dengan kombinasi Fuzzy RFM. (Putri Yuliari 2015, h. 107). Metode lain yang dapat digunakan untuk melakukan segmentasi pelanggan adalah Metode Density Based Spatial Clustering of Application with Noise (DBSCAN). Penelitian segmentasi pelanggan menggunakan Metode DBSCAN

6

7

pada perusahaan perhotelan dilakukan oleh Ni Made Anindya Santika Devi. Pada penelitian tersebut diungkapkan bahwa Metode DBSCAN yang digabungkan dengan Model RFM telah dapat menghasilkan proses segmentasi dengan cukup baik, dapat dilihat dari beragam kelas pelanggan yang dihasilkan (Anindya Santika Devi 2015, h. 114). Hasil serupa juga diperoleh melalui penelitian yang dilakukan oleh Luh Putu Dian Shavitri Handayani mengenai segmentasi pelanggan pada perusahaan retail dengan Metode ART 2 dan Model RFM. Algoritma ART 2 yang digabungkan dengan model RFM telah dapat melakukan proses segmentasi dengan cukup baik dapat dilihat dari beragam kelas pelanggan yang dihasilkan (Dian Shavitri Handayani 2012, h. 107). Segmentasi pelanggan pada pelanggan industri telekomunikasi dengan memanfaatkan Metode K-Means dan RFM diteliti oleh Arumawadu, Rathanyaka dan Illangarathne. Pada penelitian tersebut didapat kekurangan dari Metode KMeans dalam menentukan titik pusat cluster sehingga proses clustering menjadi lebih lambat (Arumawadu, Rathnayaka & Illangarathne, 2015, Vol. 3, hh. 63-71). Penelitian mengenai metode kombinasi yang sesuai untuk mengoptimasi Metode K-Means dilakukan oleh Chiu dan kawan-kawan. Metode Particle Swarm Optimization (PSO) diuji coba untuk mengoptimasi Metode K-Means. Pada hasil dari penelitian tersebut dinyatakan bahwa gabungan Metode K-Means dan PSO dapat menghasilkan cluster yang lebih akurat dan efisien (Chiu et al. 2011, vol. 36, hh. 4558-4565). Kinerja PSO dalam mengoptimalkan Metode K-Means juga diteliti oleh G. Komarasamy dan Amitabh Wahi. Dibuktikan pada penelitian tesebut bahwa kelemahan PSO yang cenderung bekerja secara lambat dalam proses menentukan nilai global optimum dapat diimbangi oleh Metode K-Means yang bekerja secara cepat dalam menentukan nilai optimum. Kombinasi kedua algoritma tersebut dapat melengkapi kekurangan satu sama lain terbukti dengan hasil clustering yang lebih baik telah dihasilkan dibandingkan dengan hasil clustering Metode K-Means standar. Nilai titik cluster dapat ditemukan secara otomatis dengan menggunakan

8

nilai optimal number dari setiap cluster (Komarasamy & Wahi 2011, vol 1, hh. 206208). Penelitian mengenai Konsep CRM (Customer Relationship Management) dilakukan oleh Injazz J. Chen dan Karen Popovich. Pada penelitian tersebut diuraikan konsep CRM yang merupakan kombinasi antar manusia, proses dan teknologi. Konsep CRM dapat digunakan untuk memahami karakteristik pelanggan suatu perusahaan melalui pendekatan yang terintegrasi untuk memanajemen hubungan dengan pelanggan (Chen & Popovich 2003, vol. 9, hh. 672-688). Berikut ini adalah daftar penelitian mengenai data mining yang berkaitan dengan segmentasi pelanggan disajikan dalam Tabel 2.1

Tabel 2.1 Daftar State of the Art

No. 1.

2.

3.

4.

5.

6.

Penelitian Yohana Nugrahaeni (2011)

Metode Fuzzy C-Means dan Fuzzy Subtractive

Deskripsi Metode Fuzzy C-Means dan Fuzzy Subtractive digunakan untuk segmentasi pelanggan pada perusahaan retail Ni Putu Yuliari Fuzzy C-Means Segmentasi pelanggan pada (2015) dan Fuzzy RFM perusahaan furniture dilakukan dengan Metode Fuzzy C-Means dan Fuzzy Recency Frequency Monetary (Fuzzy RFM) Ni Made DBSCAN dan Penelitian segmentasi pelanggan Anindya Santika Model RFM dilakukan dengan Metode Devi (2015) DBSCAN pada perusahaan perhotelan Luh Putu Dian ART 2 dan Segmentasi pelanggan pada Shavitri Model RFM perusahaan retail dengan Metode Handayani ART 2 dan Model RFM (2012) Arumawadu, K-Means Proses segmentasi pelanggan Rathanyaka & pada industry telekomunikasi Illangarathne dengan Metode K-Means dan (2015) RFM. Chiu et all (2009) K-Means dan Menguji metode PSO untuk PSO dikombinasikan dengan K-Means.

9

No. 6.

7.

Penelitian G. Komarasamy dan Amitabh Wahi (2011) Injazz J. Chen dan Karen Popovich (2003)

Metode K-Means PSO

Deskripsi dan Menguji kinerja PSO dalam mengoptimalkan Metode KMeans Customer Menguraikan konsep CRM untuk Relationship data mining Management

State of the art diatas menguraikan bahwa belum ada penelitian mengenai segmentasi pelanggan dengan Metode K-Means dan PSO serta Model RFM yang digunakan untuk melakukan segmentasi pelanggan pada perusahaan distributor produk farmasi yang mengambil studi kasus di PT. X. State of the art dari judul tugas akhir ini dapat divisualisasikan pada diagram fishbone yang ditunjukkan Gambar 2.1

Gambar 2.1 Diagram Fishbone

Pada Gambar 2.1, dapat dijelaskan bahwa judul tugas akhir ini mengambil konsep data mining terutama pada metode clustering data mining, sedangkan platform yang digunakan berbasis desktop. Tools yang digunakan adalah MATLAB dengan DBMS yang dipilih adalah SQL Server. Jenis metode clustering yang dipilih adalah Metode K-Means, dikombinasikan dengan salah satu jenis swarm intelligence yaitu Particle Swarm Optimization. Segmentasi pelanggan yang pernah dilakukan antara lain di bidang penjualan pakaian, pulsa, retail dan hotel, sedangkan segmentasi yang akan dilakukan adalah pada perusahaan distributor di bidang

10

produk farmasi. Metode validasi cluster yang akan digunakan adalah Metode Davies-bouldin Index dan Silhouette Index. Diagram fishbone menghasilkan kesimpulan bahwa penelitian mengenai segmentasi pelanggan menggunakan Metode K-Means dan Particle Swarm Optimization belum pernah dilakukan pada perusahaan distributor di bidang produk farmasi.

2.2

Data Mining Data dalam skala besar yang diekstrasi untuk mendapat pengetahuan dan

informasi yang berguna disebut dengan data mining. Data Mining digunakan untuk menyelesaikan masalah dengan melakukan analisis pada data dalam jumlah besar. (Han and Kamber, 2006). Menurut Sumanthi dan Sivanandam (2006, hh. 1-20), penerapan data mining dapat dilakukan di berbagai bidang industri meliputi bidang keuangan, pelayanan kesehatan, manufaktur, transportasi dan lain sebagainya, juga telah menggunakan data mining untuk mengambil manfaat dari analisis historikal data. Istilah data mining dan knowledge discovery in databases (KDD) sering kali digunakan secara bergantian untuk menjelaskan proses penggalian informasi tersembunyi dalam suatu basis data yang besar. Salah satu tahapan dalam keseluruhan proses KDD adalah data mining. Proses KDD secara garis besar dapat dijelaskan sebagai berikut (Fayyad et al, 1996).

Gambar 2.2 Proses KDD Sumber: Fayyad et al, 1996, h.5

11

Gambar 2.2 mengambarkan tahapan KDD. Tahap ini merupakan bagian dari proses KDD yang disebut interpretation. Tahap ini mencakup proses data selection yaitu pemilihan data dari sekumpulan data operasional perlu dilakukan sebelum tahap penggalian informasi dalam KDD dimulai. Proses cleaning yaitu proses cleaning pada data yang menjadi fokus KDD. Proses transformation yaitu transformasi pada data yang telah dipilih, sehingga data tersebut sesuai proses data mining. Proses data mining yaitu proses mencari pola atau informasi menarik dalam data terpilih menggunakan teknik atau metode tertentu. Terakhir, proses interpretation yaitu pola informasi yang dihasilkan dari proses data mining perlu ditampilkan dalam bentuk yang mudah dimengerti oleh pihak yang berkepentingan.

2.3

Hubungan Data Mining dalam Kerangka Kerja CRM CRM adalah strategi untuk membentuk, menata dan memperkuat loyalitas

pelanggan. Kombinasi CRM dan data mining banyak digunakan perusahaanperusahaan untuk mengidentifikasi pelanggan potensial dengan menggunakan segmentasi pelanggan (Tsiptsis & Charianopoulus, 2009). Data mining dapat digunakan untuk menganalisis pelanggan potensial, teknik data mining yang sering digunakan untuk menganalisi pelanggan adalah clustering dan aturan asosiasi. Inti dari kombinasi antara data mining dalam kerangka kerja CRM adalah memanfaatkan data yang telah dimiliki suatu perusahaan agar berguna bagi masa depan perusahaan itu sendiri. Kombinasi ini dapat memperolah gambaran atas kebutuhan, selera dan pelayanan yang diinginkan oleh pelanggan (Ziafat, 2014, Vol. 4, h. 72). Implementasi data mining dalam kerangka CRM harus mengikuti skema Cross Industry Standard Process for Data Mining (CRIPS-DM) yang dapat dilihat pada Gambar 2.3.

12

Gambar 2.3 Skema CRIPS-DM Sumber: Ziafat, 2014, h.73

Tahapan dari skema CRIPS-DM antara lain sebagai berikut: 1.

Business Understanding, sebuah projek data mining harus memahami proses bisnis secara subjektif, agar dapat mendefinisikan dan merencanakan projek yang akan dikembangkan.

2.

Data Understanding, fase ini melibatkan data yang dibutuhkan untuk mengembangkan projek. Fase ini meliputi pengumpulan data dan analisis data untuk menemukan masalah potensial.

3.

Data Preparation, fase ini mengidentifikasi data ke dalam model data mining. Fase ini meliputi integrasi data, transformasi format data ke bentuk yang dibutuhkan oleh projek serta proses cleaning data.

4.

Modelling, pada fase ini, analis harus memilih model yang sesuai proses bisnis, dimana data akan diubah ke dalam bentuk model yang diinginkan dengan menggunakan algoritma untuk mencapai hasil terbaik.

5.

Evaluation, model yang telah dihasilkan kemudian dievaluasi agar sesuai dengan bisnis proses perusahaan.

6.

Deployment, merupakan proses final dimana model yang dihasilkan dapat diterapkan pada proses bisnis perusahaan.

13

2.4

Model RFM Menurut Shajahan (2004, hh. 61-62) Model Recency, Frequency dan

Monetary adalah sebuah pemodelan bisnis yang dapat diaplikasikan di berbagai situasi yang dapat mengambarkan berbagai tindakan atau prilaku pelanggan dengan melakukan survei tertentu. Pelanggan yang melakukan transaksi pada perusahaan tersebut dapat dihitung komponen recency (R) dan frequentcy (F) serta jumlah transaksi terhadap produk tertantu melalui komponen monetary (M). Menurut Hughes (1994), model RFM dapat diuraikan sebagai berikut: 1.

Recency Recency merepresentasikan jarak diantara transaksi terbaru dengan transaksi sebelumnya. Makin kecil jarak transaksi nilai recency akan semakin besar.

2.

Frequency Frequency merepresentasikan jumlah transaksi yang dilakukan dalam periode tertentu. Semakin banyak frekuensi yang ada maka nilai frequency akan semakin besar.

3.

Monetary Monetary merepresentasikan jumlah uang yang telah ditransaksikan pada periode tertentu. Semakin besar jumlah transaksi jumlah monetary akan semakin besar. Implementasikannya recency, frequency dan monetary secara bersama-

sama dapat berdampak pada perusahaan untuk mendapatkan indikator dari ketertarikan pelanggan terhadap produk perusahaan tersebut. Asumsi umum dari proses tersebut adalah sebagai berikut: 1.

Pelanggan yang baru saja bertransaksi, akan lebih senang bertransaksi kembali dibanding pelanggan yang sudah lama tidak melakukan transaksi.

2.

Pelanggan yang bertransaksi secara rutin akan lebih senang bertransaksi daripada pelanggan yang baru saja melakukan satu atau dua transaksi.

3.

Pelanggan yang paling banyak bertransaksi secara total akan lebih senang melakukan transaksi. Menurut Zumstein (2007, h. 40), metode RFM dapat digunakan untuk

mendeskripsikan atribut recency, frequency, dan monetary dengan variabel

14

linguistik. Sebagai contoh, atribut recency dideskripsikan dengan bahasa natural long ago (lama) dan very recent (baru saja). Atribut frequency dideskripsikan dengan bahasa natural rare (jarang) dan frequent (sering). Atribut monetary dideskripsikan dengan bahasa natural low value (rendah) dan high value (tinggi). Menurut Tsiptsis dan Chorianopoulos (2009, hh. 344-345) terdapat enam pembagian pelanggan para perusahaan retail berdasarkan nilai RFM yang didefinisian secara lebih spesifik pada Tabel 2.2.

Tabel 2.2 Klasifikasi Customer

Kelas Pelanggan Superstar

Golden Customer Typical Customer Occational Customer Everyday Shopper

-

Dormant Customer

-

Deskripsi Kelas Pelanggan Customer dengan tingkat loyalitas paling tinggi. Nilai (value) yang paling tinggi. Frekuensi yang paling tinggi. Melakukan transaksi terbesar. Nilai (value) terbesar kedua. Frekuensi tinggi. Melakukan transaksi standar rata-rata. Memiliki nilai (value) dan frekuendi standar rata-rata. Melakukan transaksi standar rata-rata. Memiliki frekuendi terendah setelah dormant Memiliki recency rendah (memiliki waktu yang lama dengan rentang waktu terakhir pembelian) Melakukan transaksi dalam jumlah besar (large basket) Memiliki peningkatan dalam transaksi Melakukan transaksi dalam jumlah kecil (small basket) Memiliki nilai dengan skala menengah (medium) hingga rendah (low) Memiliki frekuensi dan nilai (value) terendah Memiliki waktu yang lama ketika masa terakhir pembelian (recency terendah)

Sumber: Tsiptsis dan Chorianopoulos 2009, hh. 344-345

15

2.5

Normalisasi Data Proses clustering dapat terdiri dari berbagai interval nilai yang

menyebabkan perbedaan jarak antar satu nilai dengan nilai lainnya, diperlukannya proses normaslisasi agar data memiliki nilai rata-rata 0 atau zero mean (Putra, Darma 2010, h.310). Suatu data atau fitur dapat dinormalisasi dengan rumus berikut. 𝑋̌ =

𝑋−𝑋̅ 𝜎𝑥

........................................................................................................... (2.1)

Nilai 𝑋̌ dinyatakan sebagai data atau fitur X yang telah ternormalisasi , 𝑋̅ dinyatakan sebagai rata-rata dari X, dan 𝜎 menyatakan nilai standar deviasi dari X. Sebagai contoh, misalkan vektor data X = (2,3,5,10,15) maka 𝑋̅ = 7, 𝜎 = 5.43, sehingga vektor X yang telah ternormalisasi adalah sebagai berikut. 𝑋̌ = (−0.92, −0.73, −0.37, 0.55, 1.47) Setelah dinormalisasi, pada data dapat dilakukan proses scalling agar nilai data berada pada suatu interval tertentu. Proses scalling berfungsi agar suatu fitur memiliki batas atas S dan batas bawah R dapat diperoleh dengan rumus berikut. 𝑋−𝑋 𝑚𝑖𝑛 𝑋̌ = 𝑋 max − 𝑋 𝑚𝑖𝑛 ∗ (𝑆 − 𝑅) + 𝑅 ...................................................................... (2.2)

Data yang telah ternormalisasi di atas diskalakan dengan batas S = 1 dan batas bawah R = 0 maka: 𝑋̌ =

𝑋 − (−0.92) ∗ (1 − 0) + 0 1.47 − (−0.92)

𝑋̌ =

(−0.92 + 0.92, −0.72 + 0.92, −0.37 + 0.92, 0.55 + 0.92, 1.47 + 0.92) ∗1 1.47 − (−0.92)

𝑋̌ =

(0, 0.2, 0.55, 1.47, 2.39) = (0, 0.8, 0.23, 0.62, 1) 2.39 Dari hasil di atas terlihat nilai fitur data berada dalam interval [0,1].

16

2.6

Metode Clustering Proses dari pengelompokan objek fisik atau abstrak ke dalam kelas yang

memiliki kemiripan disebut dengan proses clustering, sedangkan cluster adalah koleksi data yang memiliki kemiripan satu sama lain dengan objek yang berada pada cluster yang sama dan memiliki perbedaan dengan objek yang berada pada cluster yang lain (Han, Kamber & Pei 2007, h. 108). Menurut Kantardzic (2011, h. 250), analisis cluster didasari oleh pengelompokan secara natural, secara pengukuran atau melihat dari segi kesamaan dan perbedaan objek tersebut. Metode K-Means merupakan salah satu jenis metode clustering yang digunakan untuk melakukan pengelompokkan.

2.7

Metode K-Means Metode clustering yang digunakan dalam tugas akhir ini adalah Metode K-

Means. Metode K-Means melakukan pencarian pusat dan batas cluster melalui proses perulangan (iterative). Kedekatan atau kemiripan (similarity) suatu objek dengan objek lain atau dengan pusat cluster dihitung dengan menggunakan perhitungan jarak. Algoritma ini pertama kali diusulkan oleh MacQueen (1967, hh. 281-297) dengan tujuan untuk dapat membagi data point dalam dimensi kedalam sejumlah cluster, dimana proses clustering dilakukan dengan meminimalkan jarak sum squares antara data dengan masing-masing pusat cluster (centroid-based). Algoritma K-Means dalam penerapannya memerlukan tiga parameter yang seluruhnya ditentukan pengguna yaitu jumlah cluster k, inisialisasi pusat cluster, dan jarak sistem. Tahapan awal, Algoritma K-Means adalah memilih secara acak k buah objek sebagai centroid dalam data, kemudian jarak objek dan centroid dihitung menggunakan Metode Euclidean Distance. Algoritma K-Means secara iterative meningkatkan variasi nilai dalam tiap cluster dimana obyek selanjutnya ditempatkan dalam kelompok yang terdekat, dihitung dari titik tengah cluster. Titik tengah baru ditentukan bila semua data telah ditempatkan dalam cluster terdekat. Proses penentuan titik tengah dan penempatan data dalam cluster diulangi sampai nilai titik tengah dari semua cluster yang terbentuk tidak berubah lagi (Han, Kamber & Pei 2006, hh. 402-404).

17

Menurut Darma Putra (2010, h. 340), langkah-langkah Algoritma K-Means dijelaskan secara lebih rinci dalam uraian berikut: 1.

Inisialisasi K pusat cluster adalah z1(1), z2(2), …, zk(1). Pusat-pusat cluster ini biasanya dipilih secara acak dari sekumpulan data yang akan dikelompokkan.

2.

Pada iterasi ke-k sampel data {x} di antara K domain cluster, dengan menggunakan hubungan sebagai berikut: 2

𝑥 ∈ 𝑆𝑗 (𝑘) jika ‖𝑥 − 𝑧𝑗 (𝑘)‖ < ‖𝑥 − 𝑧𝑖 (𝑘)‖ ........................................... (2.3) Untuk semua I = 1, 2, …K,

I≠j

, dengan Sj(k) menyatakan himpunan sampel

dengan pusat cluster adalah zj (k). 3.

Hasil pada langkah 2, hitung pusat-pusat cluster baru zj (k+1), j = 1, 2, .., K, sehingga jumlah seluruh jarak dari semua titik dalam Sj(k) ke pusat cluster yang baru minimal, dengan kata lain, pusat cluster baru zj (k+1) dihitung sehingga unjuk kerja indeks: 2

𝑗𝑖 = ∑𝑥∈(𝐾)‖𝑥 − 𝑧𝑗 (𝑘 + 1)‖ , j = 1,2, …. K ........................................... (2.4) zj (k+1)

yang

meminimalkan

persamaan

di

atas

adalah

dengan

menyederhanakan nilai rata-rata dari sampel pada Sj(k), maka dari itu, pusat cluster baru ditunjuk oleh: 1

𝑧𝑗 (𝑘 + 1) = 𝑁 ∑𝑥∈𝑆𝑗 (𝑘) 𝑋, j = 1,2,…,K .................................................. (2.5) 𝑗

Dengan Nj menyatakan jumlah sampel dalam Sj(k). 4.

Bila zj (k+1) = zj (k) untuk j = 1, 2, …, K, maka algoritma telah konvergen dan proses berakhir. Bila tidak maka kembali ke langkah 2. Contoh perhitungan dari MetodeK-Means adalah sebagai berikut. Tabel 2.3

merupakan data sumber yang akan digunakan dalam perhitungan. Tabel 2.3 Data Sumber

Objek ke -n Kordinat X 1 1 2 2 3 4 4 5

Kordinat Y 1 1 3 4

18

Tahapan perhitungan adalah sebagai berikut. 1.

Banyak cluster yang digunakan adalah dua, jadi k = 2. Banyaknya cluster lebih kecil dari jumlah data atau k < n.

2.

Tentukan titik pusat (centroid) setiap cluster. Centroid awal ditentukan secara acak dapat dilihat pada Tabel. 2.4

Tabel 2.4 Titik Pusat Iterasi ke-1

Titik Pusat ke-n C1 C2

Kordinat X 1 2

Kordinat Y 1 1

Iterasi selanjutnya tidak menghitung centroid secara acak. Titik pusat ditentukan dengan mencari nilai rata-rata data pada setiap cluster. Jika titik pusat yang didapat berbeda dengan titik pusat sebelumnya maka iterasi tetap dilakukan hingga mendapat titik pusat yang sama dengan iterasi sebelumnya. 3.

Menghitung jarak data dengan titik pusat dapat dilakukan dengan tiga cara, yaitu Euclidean Distance, Manhattan / City Block, Minkowski. Perhitungan jarak yang dapat dilakukan pada Metode K-Means adalah dengan menggunakan Rumus Euclidean Distance. 2

𝑑 = (𝑥𝑗, 𝑐𝑗 ) = √∑𝑛𝑗=1(𝑥𝑗 − 𝑐𝑗 ) ...................................................................... (2.6) d = jarak j = banyaknya data c = centroid x = data Jarak data dengan titik pusat cluster pertama adalah sebagai berikut. 𝑑(𝑥1 , 𝑐1 ) = √(𝑎1 − 𝑐1𝑎 )2 + (𝑏1 − 𝑐1𝑏 )2 = √(1 − 1)2 + (1 − 1)2 = 0 𝑑(𝑥2 , 𝑐1 ) = √(𝑎2 − 𝑐1𝑎 )2 + (𝑏2 − 𝑐1𝑏 )2 = √(2 − 1)2 + (1 − 1)2 = 1 𝑑(𝑥3 , 𝑐1 ) = √(𝑎3 − 𝑐1𝑎 )2 + (𝑏2 − 𝑐1𝑏 )2 = √(4 − 1)2 + (3 − 1)2 = 3.605551 𝑑(𝑥4 , 𝑐1 ) = √(𝑎4 − 𝑐1𝑎 )2 + (𝑏3 − 𝑐1𝑏 )2 = √(5 − 1)2 + (4 − 1)2 = 5 Jarak data dengan titk pusat cluster kedua adalah sebagai berikut.

19

𝑑(𝑥1 , 𝑐2 ) = √(𝑎1 − 𝑐2𝑎 )2 + (𝑏1 − 𝑐2𝑏 )2 = √(1 − 2)2 + (1 − 1)2 = 1 𝑑(𝑥2 , 𝑐2 ) = √(𝑎2 − 𝑐2𝑎 )2 + (𝑏2 − 𝑐2𝑏 )2 = √(2 − 2)2 + (1 − 1)2 = 0 𝑑(𝑥3 , 𝑐2 ) = √(𝑎3 − 𝑐2𝑎 )2 + (𝑏2 − 𝑐2𝑏 )2 = √(4 − 2)2 + (3 − 1)2 = 2.828427 𝑑(𝑥4 , 𝑐2 ) = √(𝑎4 − 𝑐2𝑎 )2 + (𝑏3 − 𝑐2𝑏 )2 = √(5 − 2)2 + (4 − 1)2 = 4.242641 Seterusnya, hitung jarak pada setiap baris data. Hasil perhitungan dapat dilihat pada Tabel 2.5. Tabel 2.5 Hasil Perhitungan Jarak

Objek ke X 1 1 2 2 3 4 4 5 4.

Y

dc1 1 1 3 4

dc2

0 1 3.605551 5

1 0 2.828427 4.242641

c1

c2 Ok Ok Ok Ok

Kembali lagi ke tahap kedua hingga menemukan titik pusat cluster yang sama seperti sebelumnya.

2.8

Metode Particle Swarm Optimization Menurut Talukder (2011, hh. 10-11), Metode Particle Swarm Optimization

(PSO) merupakan algoritma yang memiliki sifat pencarian dengan melibatkan banyak pelaku didalamnya. Pelaku dapat berupa populasi partikel yang merepresentasikan solusi potensial di dalam setiap populasi. Semua partikel melewati ruang pencarian multidimensional yang disesuaikan dengan posisi berdasarkan experience dan tetangga yang dimilikinya. 𝑥𝑖𝑡 menunjuk vektor dari partikel i di ruang pencarian multidimensional pada tahapan waktu t, lalu posisi setiap partikel diperbaharui di ruang pencarian. Semua partikel diinisiasi secara acak, kemudian dievaluasi untuk dikomputasi nilai kecocokannya dengan mencari Personal Best atau nilai terbaik dari setiap partikel dan Global Best nilai terbaik dari keseluruhan populasi. Perulangan dilakukan untuk menemukan solusi optimal. Kecepatan partikel pertama diperbaharui melalui nilai Personal atau Global Best, dan posisi setiap

20

partikel diperbaharui dengan kecepatan yang berlaku. Perulangan berhenti dengan aturan yang ditetapkan di awal. 2.8.1

Personal Best dan Global Best Particle Swarm Optimization Personal Best adalah posisi terbaik setiap individu partikel yang didapat

melalui iterasi perubahan kecepatan gerak partikel. Sebaliknya Global Best adalah posisi terbaik yang ditemukan dari nilai Personal Best partikel secara keseluruhan (Talukder 2011, hh. 11-13). Metode ini menggunakan topologi bintang, seperti Gambar 2.4

Gambar 2.4 Topologi Bintang Sumber: Talukder 2011, h. 11

Topologi ini memungkinkan partikel untuk medapatkan informasi secara keseluruhan mengenai keseluruhan partikel. Setiap partikel individu 𝑖 ∈ [1, … , 𝑛] dimana n > 1 memiliki posisi terbaru di dalam area pencarian xi dan kecepatan terbaru vi serta posisi Personal Best Pbest,i. Posisi Personal Best Pbest,i berkorespondensi dengan posisi di area pencarian dimana partikel i memiliki nilai terkecil yang dipengaruhi oleh fungsi objektif f. Keadaan dimana posisi menghasilkan nilai terkecil diantara posisi Personal Best lainnya maka disebut dengan Global Best yang dinotasikan sebagai Gbest. Posisi Personal Best berikutnya dihitung dengan rumus berikut:

21

𝑡+1 𝑡+1 𝑃𝑏𝑒𝑠𝑡,𝑖 𝑖𝑓 𝑓(𝑋𝑖𝑡+1 ) > 𝑃𝑏𝑒𝑠𝑡,𝑖 𝑡+1 𝑃𝑏𝑒𝑠𝑡,𝑖 = { 𝑡+1 𝑡+1 ............................................................ (2.8) 𝑋𝑖 𝑖𝑓 𝑓(𝑋𝑖𝑡+1 ) ≤ 𝑃𝑏𝑒𝑠𝑡,𝑖

Dimana f :Rn → R adalah fungsi fitness. Posisi Global Best pada tahap waktu t dihitung dengan: 𝑡+1 𝐺𝑏𝑒𝑠𝑡 = min{𝑃𝑏𝑒𝑠𝑡,𝑖 } , 𝑑𝑖𝑚𝑎𝑛𝑎 𝑖 ∈ [1, … , 𝑛] 𝑑𝑎𝑛 𝑛 > 1 ................................ (2.9)

Untuk menghitung kecepatan partikel pada Global Best digunakan rumus berikut: 𝑡+1 𝑡 𝑡+1 𝑡 𝑣𝑖𝑗 = 𝑣𝑖𝑗 + 𝑐1 𝑟𝑖𝑗𝑡 [𝑃𝑏𝑒𝑠𝑡,𝑖 − 𝑋𝑖𝑡+1 ] + 𝑐2 𝑟2𝑗 [𝐺𝑏𝑒𝑠𝑡 − 𝑋𝑖𝑡 ] .............................. (2.10)

2.8.3

Contoh Perhitungan Particle Swarm Optimization Menurut Budi Santosa (2011) contoh perhitungan dengan menggunakan

Metode Particle Swarm Optimization (PSO) adalah sebagai berikut. Misal terdapat persoalan optimasi dengan satu variabel. 𝑓(𝑥) = (100 − 𝑥)2 𝑑𝑖𝑚𝑎𝑛𝑎 60 ≤ 𝑋 ≤ 120 1.

Tentukan jumlah partikel N = 4 Tentukan populasi awal secara random, misalkan didapat 𝑥1 (0) = 80, 𝑥2 (0) = 90, 𝑥3 (0) = 110, 𝑥4 = 75.

2.

Evaluasi nilai fungsi tujuan untuk setiap partikel 𝑥𝑗 (0) untuk j = 1,2,3,4. Dan nyatakan dengan 𝑓1 = 𝑓(80) = 400, 𝑓2 = 𝑓(90) = 100, 𝑓3 = 𝑓(110) = 100, 𝑓4 = 𝑓(75) = 625,

22

3.

Tentukan kecepatan awal 𝑣1 (0) = 𝑣2 (0) = 𝑣3 (0) = 𝑣4 (0) = 0. Tentukan iterasi i = 1.

4.

Temukan 𝑃𝑏𝑒𝑠𝑡,1 = 80, 𝑃𝑏𝑒𝑠𝑡,2 = 90, 𝑃𝑏𝑒𝑠𝑡,3 = 110, 𝑃𝑏𝑒𝑠𝑡,4 = 75, 𝐺𝑏𝑒𝑠𝑡 = 90. Hitung 𝑣(𝑗) dengan 𝑐1 = 𝑐2 = 1. Misalkan nilai random yang didapat, 𝑟1 = 0,4, 𝑟2 = 0,5 dengan rumus 𝑉𝑗 (𝑖) = 𝑉𝑗 (𝑖 − 1) + 𝑐1 𝑟1 [𝑃𝑏𝑒𝑠𝑡.𝑗 − 𝑥𝑗 (𝑖 − 1)] + 𝑐2 𝑟2 [𝐺𝑏𝑒𝑠𝑡.𝑗 − 𝑥𝑗 (𝑖 − 1)] diperoleh: 𝑥1 (1) = 80 + 5 = 85 𝑥2 (1) = 90 + 0 = 90 𝑥3 (1) = 110 − 10 = 100 𝑥4 (1) = 75 + 7.5 = 82.5

5.

Evaluasi nilai fungsi tujuan sekarang pada partikel 𝑥𝑗 (1), 𝑓1 (1) = 𝑓(85) = 225, 𝑓2 (1) = 𝑓(90) = 100, 𝑓3 (1) = 𝑓(100) = 0 𝑓4 (1) = 𝑓(82.5) = 306.25 Sedangkan pada iterasi sebelumnya kita dapatkan 𝑓1 (1) = 𝑓(80) = 400, 𝑓2 (1) = 𝑓(90) = 100, 𝑓3 (1) = 𝑓(110) = 100, 𝑓4 (1) = 𝑓(75) = 625, Nilai dari f dari iterasi sebelumnya tidak ada yang lebih baik sehingga Pbest untuk masing-masing partikel sama dengan nilai x. Gbest =100.

6.

Cek apakah solusi x sudah konvergen, dimana nilai x saling dekat. Jika tidak, tingkatkan ke iterasi berikutnya i = 2. Lanjutkan ke langkah 4.

7.

𝑃𝑏𝑒𝑠𝑡,1 = 85, 𝑃𝑏𝑒𝑠𝑡,2 = 90, 𝑃𝑏𝑒𝑠𝑡,3 = 100, 𝑃𝑏𝑒𝑠𝑡,4 = 75, 𝐺𝑏𝑒𝑠𝑡 = 100. kecepatan baru dengan 𝑟1= 0.3 dan 𝑟2 = 0.6. 𝑣1 (2) = 5 + 0.3(85 − 85) + 0.6(100 − 85) = 14 𝑣2 (2) = 0 + 0.3(90 − 90) + 0.6(100 − 90) = 6 𝑣3 (2) = −10 + 0.3(100 − 100) + 0.6(100 − 100) = −10 𝑣4 (2) = 7.5 + 0.3(82.5 − 82.5) + 0.6(100 − 82.5) = 18

Hitung

23

Sedangkan untuk nilai x adalah 𝑥1 (2) = 85 + 14 = 99 𝑥1 (2) = 90 + 6 = 96 𝑥1 (2) = 100 − 10 = 90 𝑥1 (2) = 82.5 + 18 = 100.5 8.

Evaluasi nilai fungsi tujuan sekarang pada partikel 𝑥𝑗 (2), 𝑓1 (2) = 𝑓(99) = 1, 𝑓2 (2) = 𝑓(96) = 16, 𝑓3 (2) = 𝑓(90) = 100, 𝑓4 (2) = 𝑓(100.5) = 0.25, Jika dibandingkan dengan nilai f dari iterasi sebelumnya, ada nilai yang lebih baik dari nilai f sekarang yaitu 𝑓3 (1) = 0, sehingga 𝑃𝑏𝑒𝑠𝑡 untuk partikel 3 sama dengan 100, dan 𝐺𝑏𝑒𝑠𝑡 dicari dari min{1,16,0,0.25} = 0 yang dicapai pada 𝑥3 (1) = 100. Sehingga untuk iterasi berikutnya 𝑃𝑏𝑒𝑠𝑡 = (99,96,100,100.5) dan 𝐺𝑏𝑒𝑠𝑡 = 100.

9.

Cek apakah solusi sudah konvergen, dimana nilai x saling dekat. Jika tidak konvergen, set i = 3, masuk ke iterasi berikutnya. Lanjutkan ke langkah berikutnya dengan menghitung kecepatan v dan ulangi langkah-langkah selanjutnya sampai mencapai konvergen.

2.9

Validasi Cluster Cluster yang dihasilkan terbentuk dari parameter-parameter yang

diinputkan. Pembentukan jumlah cluster dapat divalidasi dengan menggunakan metode validasi cluster untuk mengetahui input terbaik dalam pembentukan cluster, Metode validasi cluster yang digunakan antara lain Metode Davies-bouldin Index dan Silhouette Index. 2.9.1

Validasi Cluster dengan Davies-bouldin Index Menurut Bouldin dan Davies (1979, h.224) Metode Davies-boulding Index

dapat digunakan untuk menghitung jumlah ideal cluster, berdasarkan nilai rata-rata rasio cluster scatter untuk semua cluster dan jarak diantara dua cluster. Davies-

24

bouldin Index didapatkan berdasarkan kemiripan dari cluster (Rij) yang merupakan ukuran dipersi cluster (si) dan ketidakmiripan (dij). Nilai Rij ditentukan dengan menggunakan cara berikut 𝑅𝑖𝑗 =

𝑠𝑖 + 𝑠𝑗 𝑑𝑖𝑗

................................................................................................... (2.12) 1

𝑑𝑖𝑗 = 𝑑(𝑣𝑖 + 𝑣𝑗 ), 𝑠𝑖 = |𝑐 | ∑𝑥∈𝑐𝑖 𝑑(𝑥, 𝑣𝑖 ) ...................................................... (2.13) 𝑗

Sedangkan rumus dari Metode Davies-bouldin Index didefinisikan sebagai berikut: 1

𝑛𝑐 𝐷𝐵 = 𝑛 ∑𝑖=1 𝑅𝑖, ............................................................................................ (2.14) 𝑐

𝑅𝑖= 𝑚𝑎𝑥, 𝑗 = 1 … 𝑛𝑐, 𝑖 ≠ 𝑗 ............................................................................ (2.15) (𝑅𝑖𝑗 ), 𝑖 = 1 … 𝑛𝑐 .......................................................................................... (2.16)

2.9.2

Validasi Cluster dengan Silhouette Index Menurut Rousseeuw, Peter J (1987) setiap cluster dapat direpresentasikan

kedalam sebuah silhouette. Metode Silhouette dapat menunjukkan cluster terbaik untuk setiap objeknya. Rata-rata silhouette dapat digunakan untuk menunjukkan validasi cluster dan jumlah optimal pembentukan cluter. Proses validasi cluster dengan menggunakan Metode Silhouette adalah sebagai berikut. 1.

Setiap objek i, dihitung rata-rata jarak dari objek i dengan seluruh objek yang berada dalam satu cluster sehingga didapat nilai rata-rata a(i).

2.

Setiap objek i dihitung rata-rata jarak dari objek i dengan objek yang berada di cluster lainnya. Nilai terkecil dari semua rata-rata jarak kemudian digunakan. Nilai tersebut merupakan nilai dari b(i).

3.

Semua variabel kemudian dihitung silhouette coefisien dengan persamaan berikut. 𝑏(𝑖)−𝑎(𝑖)

𝑠(𝑖) = max{𝑎(𝑖),𝑏(𝑖)} ................................................................................ (2.17)

25

2.10

Profil Perusahaan PT. X PT. X dikenal secara nasional telah berdiri semejak Tahun 1973. Pada awal

mulanya perusahaan tersebut terdiri dari empat kantor cabang. Fokus perusahaan adalah terlibat dalam distribusi bahan baku farmasi dan barang jadi, sekarang ini PT. X merupakan salah satu distributor farmasi yang masuk peringkat sepuluh besar distributor farmasi terbaik di Indonesia dengan jumlah cabang tersebar diseluruh Indonesia sebanyak 31 cabang.