TESIS I Wayan Budi Sentana Nrp. 5108 201 025
DOSEN PEMBIMBING Prof. Dr.Ir. Joko Lianto Buliali, M.Sc.
Pendahuluan Analisis Cluster sudah dimanfaatkan dengan sangat
luas untuk segmentasi pasar (Huang dkk, 2007; Liu dkk, 2008) Permasalahan utama Berapa Cluster / segment yang tepat ? Variabel mana yang valid?
Beberapa penelitian melibatkan algoritma genetik
untuk mengatasi permasalahan tersebut(Kim dkk,2008 ; Liu dkk, 2008; Kuo dkk, 2006)
K-means GA (Liu dkk, 2008)
K-means GA (Liu dkk, 2008)
K-prototype (Huang, 1998)
K-prototype&2PGA
2PGA (Martikaenan, 2006)
Perumusan Masalah Bagaimana membuat sebuah sistem yang dapat
memanfaatkan 2PGA dan k-prototype untuk menghasilkan valid variable dan menentukan jumlah cluster optimal pada dataset dengan tipe campuran numerik dan kategorikal, sehingga teknik clustering diharapkan dapat menghasilkan segmentasi pasar yang lebih baik?
Tujuan Penelitian Mengimplementasikan metode gabungan k-prototype
dengan 2PGA untuk segementasi pasar Membandingkan K-means GA (Liu dkk, 2008) dengan k-prototype 2PGA Jumlah cluster optimal Pemilihan valid variabel
Membandingkan k-prototype SPGA dengan k-
prototype 2PGA Kecepatan konvergensi
Manfaat Penelitian Manfaat : terciptanya segmentasi pasar yang lebih akurat, sehingga para pelaku bisnis dapat membuat strategi pemasaran yang lebih fokus kepada segment tertentu dengan melihat karakteristik yang ada pada setiap segment
Kontribusi Penelitian Kontribusi : Diterapkannya metode gabungan k-prototype 2PGA untuk mendapatkan variabel valid dan menemukan jumlah cluster optimal, serta menghasilkan tingkat konvergensi yang lebih cepat pada data dengan tipe campuran numerik dan kategorikal, sehingga hasil clustering dapat menjadi lebih baik.
2-Population Genetic Algorithm (2PGA) (Martikainen, 2006) Elite Population Initial Population
Rang.
Fitness
Rang.
Fitness
1
450
1
450
2
425
2
425
3
400
3
400
4
380
4
380
5
350
6
320
7
290
8
285
9
285
10
270
11
240
12
220
13
150
14
90
Plain Population Rang.
Fitness
1
350
2
320
3
290
4
285
5
285
6
270
7
240
8
220
9
150
10
90
Reproduksi 2PGA Generasi n Generasi n + 1 Elite Population Rang.
Fitness
1
450
2
425
3
400
4
380
Elite Population
Parent untuk n + 1
Ke plain population
Rang.
Fitness
1
550
2
415
3
450
4
425
Offspring baru Parent dari elite population sebelumnya
Plain Population Rang.
Fitness
1
350
2
320
3
290
4
285
5
285
6
270
7
240
8
220
9
150
10
90
Plain Population
Parent untuk n + 1
Rang.
Fitness
1
400
2
380
3
250
4
430
5
220
6
350
7
350
8
320
9
290
10
285
Dari elite population sebelumnya
Offspring baru
Chromosom sebelumnya dari plain population
Migrasi 2PGA Plain Population
Elite Population Rang.
Fitness
1
1000
2
950
3
900
4
900
If elite.1 cm x plain 1
If elite.1 cm x plain 1
Rang.
Fitness
1
1150
2
950
3
800
4
650
5
650
6
270
7
240
8
220
9
150
10
90
Algoritma k-prototype Tentukan pusat cluster secara acak 2. Ukur setiap object ke semua cluster, tempatkan setiap object ke cluster terdekat 3. Hitung ulang pusat cluster 4. Ulangi langkah 2 dan 3 sampai tidak ada perubahan pusat cluster 1.
Pusat cluster k-prototype Prototype Centroid + medoids Prototype Numerik Prototype Categorical Numerik means Categorical modus
Jarak dalam k-prototype mr
mc
j 1
j 1
d ( X i , Ql ) ( xijr qljr ) 2 l ( xijc , qljc )
dimana (p,q) = 0 untuk p = q
(p,q) = 1 untuk pq. l = bobot untuk atribut kategorikal pada cluster ke l.
Mulai
Kprototype-2PGA
Inisialisasi populasi awal secara acak
Mixed Type Dataset
Clustering menggunakan K-Prototype
Evaluasi nilai fitness menggunakan CF Criterion
Pre-processing
Hasil segmentasi
Mengurutkan Nilai Fitness
Populasi Elite
Populasi Plain
Clustering Elite dengan K-Prototype
Clustering Plain dengan K-Prototype
Evaluasi Fittness Elite dengan CF Criterion
Evaluasi Fitness Plain dengan CF Criterion
Memenuhi stoping criteria?
ya
tidak tidak Seleksi Elite
Selesai
Migrasi
Seleksi Plain
Pindah silang dan mutasi Elite
Pindah silang dan mutasi Plain
Individu Baru Elite
Individu Baru Plain
Data Pre-Processing Menghilangkan Class label Normalisasi data bertipe numerik Mengganti representasi data
bertipe kategorical ke dalam numerik Menyimpan hasil Pre-processing untuk dipergunakan aplikasi segmentasi
Inisialisasi Populasi Membuat kromosom awal yang dilakukan secara
acak sejumlah populasi yang dimasukkan oleh user
Bentuk Kromosom 1
0
1
1
1
0
0
1
0
1
Panjangnya sama dengan jumlah variabel dataset, 1 menandakan bahwa variabel yang terwakili akan disertakan dalam clustering , sedangkan 0 adalah sebaliknya
0
….
1
5
Mewakili jumlah cluster
Pre-Evaluasi
Clustering menggunakan k-prototype
mulai Inisialiasasi prototype Ukur jarak object ke semua prototype, tempatkan object pada cluster terdekat Hitung ulang prototype
Terjadi perubahan prototype? tidak
Selesai
ya
Evaluasi Nilai Fitness Cost Function Criterion (Huang, 1998) n
mr
n
mc
i 1
j 1
i 1
j 1
El yil ( xijr qljr ) r l yil ( xijc , qljc ) k
E ( Elr Elc ) l 1
Mengurutkan Nilai Fitness
Iterasi Reproduksi 2PGA
Eksekusi Program Studi Kasus German Credit Dataset yang didonasikan oleh Prof. Hofman dari Hamburg University, Jerman. terdiri dari 1000 record 20 variabel,
13 variabel bertipe categorical 7 variabel bertipe numerik.
2 kali percobaan utama :
Percobaan 1 100 populasi ; 1000 generasi Percobaan 2 500 populasi ; 200 generasi
Hasil Eksekusi
0.0012 0.001
0.0008 0.0006
Perc. 1 Perc.2
0.0004 0.0002
1 57 113 169 225 281 337 393 449 505 561 617 673 729 785 841 897 953
0
Percb. 1 konvergen pada generasi ke-695 Percb. 2 konvergen pada generasi ke-77 Fitness tertinggi 0.001101967 Bentuk Kromosom terbaik : 1 0
2 1
3 0
4 0
5 1
6 1
7 0
8 1
9 1
10 1
11 1
12 0
13 1
14 1
15 1
16 1
17 0
18 1
19 1
20 1
k 8
Pengujian Akurasi Hasil Cluster Ketepatan Pemilihan Variabel Kecepatan Konvergensi
Akurasi Hasil Cluster Nama
Model Kromosom
Model X
111111111111111111114
Model Y
111111111111111111118
Model Liu Model yang diusulkan
111110111101101011014 010011011110111101118
Keterangan Semua variabel disertakan : k =4 Semua variabel disertakan : k =8 Variabel bernilai 1 disertakan :k=4 Variabel bernilai 1 disertakan :k=8
Membandingkan model-model tersebut dalam
Total Cost Index Categorical Variance Criterion
Categorical Variance Criterion(Hsu & Chen, 2007) CV
CU 1 Variance
| Ck | CU P( Ai Vij | Ck ) 2 P( Ai Vij ) 2 k | D| i j
2 k
1 (Vijk Vi ,kavg ) 2 | Ck | i j
Hasil Pengujian akurasi Nama Model X Model Y Model Liu Model yang diusulkan
Total Cost CV Criterion 2.69E+03 2.08E-01 2.45E+03 2.26E-01 2.07E+03 2.19E-01 9.51E+02
2.45E-01
Uji Ketepatan Pemilihan variabel Perhitungan multinomial logit( Liu dkk, 2008) No 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Nama Variabel Status of existing checking account Duration in month Credit History Purpose Credit ammount Saving account / bonds Present employment since Installment rate in percentage of disposable income Personal status and sex Other debtors / guarantors Present residence since Property Age in year Other installment plans Housing Numer of existing credit at this bank Job Number of people being liable to provide maintenance for Telephone Foreign worker
DF 3 1 4 1 1 4 4 3 3 2 3 3 1 2 2 3 3 1 1 1
2 35.8151 49.0403 36.7832 8.2535 85.6894 1.1025 4.2079 38.376 10.7201 15.828 8.3771 6.6498 0.9853 0.1461 38.4126 1.7591 13.4009 5.0959 0.0399 34.2417
PValue <.0001*** <.0001*** <.0001*** 0.0041*** <.0001*** 0.8939 0.2399 <.0001*** 0.0299** 0.0004*** 0.0388** 0.0839* 0.3209 0.9296 <.0001*** 0.6239 0.0038*** 0.024** 0.8416 <.0001***
Hasil Uji pemilihan variabel Multinomial dkk,2008)
Logit
(Liu Hasil dari (Liu dkk, 2008)
Hasil dari Metode yang diusulkan
Saving account / bonds
Number of existing credit at Status of existing checking this bank account
Other installment plans
Present residence since
Credit history
Number of existing credit at Saving account /bonds this bank
Purpose
Telephone
Telephone
Present employment since
Present employment since
Other installment plans
Property
Age in year
Job
Uji Kecepatan Konvergensi Membandingkan k-prototype SPGA dengan k-prototype 2PGA
K-prototype SPGA Kondisi Prob. Mutasi Kondisi 1 Kondisi 2 Kondisi 3
Prob. Crossover 0.3 0.5 0.8
0.3 0.5 0.8
K-prototype 2PGA Model Kondisi1 Kondisi 2 Kondisi3 Kondisi4
Prob. Prob. Crossover Mutasi Elite Elite 0.3 0.3 0.5 0.5 0.5 0.3 0.5 0.8
Prob. Mutasi Plain 0.5 0.8 0.5 0.5
Prob. Crossover Plain 0.5 0.8 0.3 0.8
Start
K-prototype SPGA, Pembanding untuk uji kecepatan konvergensi
Parameter Initialization
Random Population Initialization
German Credit Dataset
Clustering using k-prototype
Evaluasi fitness menggunakan CFC
Segmentati on Result
yes
Satisfying stopping criteria?
No Finish
Selection
Crossover
Mutation
New Parameter Population
Hasil Uji Konvergensi K-prototype SPGA Run1 Run2 Run3 Run4 Run5 Rerata Gnrs Kondisi 1 112 93 84 123 101 102.6 Kondisi 2 109 127 159 139 121 131 Kondisi 3 79 177 157 136 133 136.4
K-prototype 2PGA Kondisi 1 Kondisi 2 Kondisi 3 Kondisi 3
Run1 Run2 Run3 Run4 Run5 Rerata Gnrs 81 94 107 101 87 94 96 135 89 92 137 109.8 117 103 93 87 107 101.4 127 167 137 118 135 136.8
Hasil uji
kecepatan konvergensi dengan berbagai kondisi pada model k-prototype SPGA dan k-prototype 2PGA
Analisis Hasil Akurasi CV Criterion adalah index yang mengukur kesamaan nilai object
yang ada di dalam satu cluster, jika nilai CV criterion semakin bagus, hal tersebut berarti bahwa kesamaan ciri-ciri yang dimiliki object di dalam satu cluster adalah semakin besar. cost function menghitung jarak setiap object ke cluster terdekat, semakin kecil nilai cost berarti jarak antara kumpuluan object di dalam suatu cluster akan semakin dekat. Hal ini berarti juga tingkat kesamaan ciri-ciri dari object juga akan semakin sama. Jika dikaitkan dengan segmentasi pasar, maka metode yang diusulkan dalam penelitian ini telah membentuk kelompok atau segment yang semakin kompak, dimana kesamaan ciri-ciri customer yang ada di dalam segment tersebut semakin besar.
Analisis Hasil Pemilihan variabel metode yang diusulkan dalam penelitian ini tidak
memberikan hasil pemilihan variabel yang lebih baik clustering criterion tidak pernah memperhitungkan data target yang terdapat pada variabel response, seperti halnya yang dilakukan oleh metode multinomial logit Clustering criterion yang dijadikan sebagai alat analisis fungsi fitness hanya memperhitungkan kedekatan antar object berdasarkan fungsi jarak tertentu,
Analisis Kecepatan Konvergensi Dari sisi kecepatan konvergensi, metode K-prototype 2PGA
memiliki tingkat konvergensi yang lebih baik jika dibandingkan dengan K-prototype SPGA. Rerata generasi yang diperlukan untuk mencapai konvergen pada metode K-prototype 2PGA terlihat paling kecil pada kondisi probabilitas mutasi dan pindah silang populasi Elite sebesar 30% dan kondisi probabilitas mutasi dan pindah silang populasi Plain sebesar 50%, generasi ke 94. Probabilitas mutasi dan pindah silang yang terlalu tinggi menyebabkan munculnya kromosom yang monoton pada generasi-generasi berikutnya.
Kesimpulan Metode
k-prototype 2PGA memberikan hasil akurasi cluster atau segmen yang lebih baik dari penelitian yang ada sebelumnya, hal ini terlihat dari total cost yang lebih rendah dan nilain index clustering criterion yang lebih tinggi. Ketelitian hasil pemilihan variabel dari model k-prototype 2PGA tidak lebih baik dari penelitian yang dilakukan oleh (Liu dkk, 2008). Hal ini disebabkan karena clustering criterion yang digunakan dalam penelitian ini tidak pernah memperhitungkan keterkaitan antara variabel dengan variabel response. Pada kondisi probabilitas mutasi dan pindah silang tertentu, metode k-prototype 2PGA menunjukkan tingkat konvergensi yang lebih tinggi jika dibandingkan dengan metode k-prototype SPGA.
