3
TINJAUAN PUSTAKA Gambaran Umum Analisis Gerombol Analisis gerombol merupakan salah satu metode analisis peubah ganda yang bertujuan untuk mengelompokkan objek kedalam kelompok – kelompok tertentu yang relatif homogen berdasarkan kemiripan atau ketidakmiripan karakteristik– karakteristik yang dimiliki (Hair et al, 1998). Ukuran kemiripan yang digunakan adalah fungsi jarak antara dua objek. Bila antar peubah yang digunakan saling bebas digunakan jarak euclidean
-
korelasi antar peubah digunakan jarak mahalanobis dengan
sedangkan bila terdapat -
-
-
adalah matriks ragam peragam. Secara umum terdapat dua metode
penggerombolan yang menggunakan ukuran jarak, yaitu metode penggerombolan berhirarki dan metode penggerombolan tak berhirarki (Johnson, 1998). a.
Metode berhirarki Metode penggerombolan berhirarki dimulai dengan mengelompokkan dua
atau lebih objek yang memiliki kesamaan terdekat menjadi suatu gerombol baru sehingga jumlah gerombol berkurang satu pada setiap tahap, atau dengan menganggap seluruh objek berasal dari satu gerombol kemudian ketidakmiripan yang paling tinggi dipisah hingga tiap observasi menjadi gerombol sendiri– sendiri. Metode ini digunakan bila jumlah gerombol yang akan dibentuk belum diketahui sebelumnya. b.
Metode tak berhirarki Metode penggerombolan tak berhirarki digunakan bila banyaknya gerombol
yang akan dibentuk sudah diketahui sebelumnya. K-rataan merupakan metode tak berhirarki yang paling banyak digunakan. Penentuan objek kedalam gerombol tertentu pada metode ini berdasarkan rataan terdekat, yang terdiri dari tiga tahap. Tahap pertama mengambil k unit data pertama yang digunakan sebagai k pusat gerombol awal. Tahap kedua, menggabungkan setiap (n-k) data yang merupakan sisa objek ke pusat gerombol terdekat, kemudian dihitung masing-masing pusat (rataan) gerombol baru yang terbentuk dari hasil gabungan. Pada tahap ketiga, pusat gerombol yang terbentuk dijadikan sebuah titik pusat (rataan) gerombol
4
kemudian dilakukan penggabungan kembali dari setiap unit data ke dalam titik pusat terdekat. Ketiga tahap ini dilakukan hingga diperoleh gerombol yang konvergen yaitu adanya titik pusat yang tetap dan tidak ada lagi perubahan anggota di setiap gerombol. Metode penggerombolan tak berhirarki lainnya adalah metode penggerombolan berbasis model campuran. Penggerombolan Berbasis Model Metode penggerombolan berbasis model campuran mengasumsikan bahwa sebaran data yang digunakan adalah sebaran campuran dengan setiap subpopulasi mewakili suatu gerombol yang berbeda, sehingga dalam mendefinisikan setiap gerombol yang terbentuk digunakan distribusi statistik (Fraley,1998). Tujuan dari metode ini adalah untuk mengoptimalkan kemiripan antar objek dengan menggunakan pendekatan model peluang. Pendekatan tersebut dapat memodelkan data yang dimiliki dengan menerapkan pengaturan karakteristik yang berbedabeda dan menentukan jumlah gerombol yang sesuai dengan data seiring proses pemodelan karakteristik dari masing-masing gerombol tersebut. Berbeda dengan k-rataan yang perpindahan objek secara berulang dari satu gerombol ke gerombol lain mulai dari partisi awal berdasarkan jarak metrik, tehnik perpindahan objek pada analisis gerombol berbasis model didasarkan pada algoritma EM. Penentuan banyaknya gerombol dalam metode ini ditentukan dengan menggunakan BIC. Sebaran campuran merupakan campuran dari beberapa sebaran statistik, dimana contoh berasal dari populasi yang tidak sama. Sebaran ini digunakan dalam dua keadaan yaitu struktur campuran dari populasi diketahui dan struktur campuran dari populasi tidak diketahui. Dengan demikian pada keadaan pertama dapat diduga sebaran masing – masing subpopulasi dan proporsinya, sedangkan pada keadaan kedua dapat dilakukan klasifikasi data ke dalam subpopulasi berdasarkan
peluang
akhir
(Mclachlan
dan
Basford
1988).
Misalkan
adalah contoh acak peubah ganda p dari suatu populasi, dimana p menyatakan dimensi data dan n menyatakan banyaknya objek pengamatan yang dianggap berasal dari campuran G sub populasi, dengan fungsi kepekatan campurannya adalah ;
, dimana .
;
adalah fmp atau fkp campuran,
,
5
adalah proporsi subpopulasi ke-
dan
adalah fmp atau fkp subpopulasi.
Fungsi kepekatan campuran (fkp) dari subpopulasi tidak harus memiliki parameter dan sebaran yang sama, namun dalam penelitian ini digunakan fkp subpopulasi yang memiliki sebaran yang sama dan parameter yang berbeda. Dengan demikian fkp campuran untuk beberapa vektor parameter
yang tidak diketahui yaitu: (1)
Dengan asumsi contoh acak kepekatan objek
bebas stokastik dan identik, dengan fungsi
dari gerombol ke-k yaitu
, maka fungsi kepekatan
campuran pada persamaan (1) didefinisikan sebagai: (2) dimana
merupakan peluang suatu pengamatan berada pada komponen ke-k .
Dalam penelitian ini digunakan sebaran normal ganda yang dinotasikan dengan
(
, sehingga jika
merupakan fungsi kepekatan peubah
ganda campuran normal dengan parameter vektor rataan
dan matriks peragam
dapat dinyatakan dalam bentuk
Algoritma EM Dalam analisis gerombol berbasis model, algoritma EM dapat digunakan sebagai tehnik perpindahan objek sehingga dapat memutuskan hasil gerombol. Menurut Dempster (1977), algoritma ini merupakan metode perhitungan iterasi yang sangat cocok untuk pendugaan parameter dari fungsi kemungkinan maksimum pada data tidak lengkap seperti yang terdapat pada sebaran campuran. Pada sebaran campuran dinyatakan bahwa data terdiri dari n pengamatan peubah ganda yang diperoleh dari dan
, dengan
merupakan peubah yang teramati
merupakan peubah yang tidak teramati.
gerombol dimana
memetakan objek ke dalam
yang didefinisikan dengan dan
(3
6
diasumsikan saling bebas dan terdistribusi identik menurut sebaran multinomial dari G kategori dengan peluang
dan fkp dari
dengan
adalah
. Setiap iterasi pada algoritma EM terdiri atas dua tahap yaitu expectation-step (tahap E) dan maximization-step (tahap M). Diketahui bahwa contoh acak
saling bebas dan
yang
menentukan objek dari gerombol mana berasal, maka
dengan
Fungsi kemungkinan yang diperoleh yaitu
Jika digunakan fungsi kepekatan peubah ganda campuran normal, maka fungsi kemungkinannya adalah: -
-
-
-
-
-
Tahap E Pada tahap E merupakan tahap untuk menghitung nilai harapan bersyarat dari loglikelihood. Dengan demikian, diperoleh:
-
-
-
-
-
-
dengan
Tahap M Pada tahap M merupakan tahap untuk memaksimalkan nilai harapan bersyarat dari loglikelihood. Paramater yang diduga yaitu proporsi campuran ( ), rata-rata ( ), dan matrik kovarian (
).
7
-
-
-
-
-
Terdapat dua metode pendugaan parameter yang bisa digunakan dalam tahap ini, yaitu metode kemungkinan maksimum dan metode Bayes. a.
Metode kemungkinan maksimum Pendugaan
parameter
dengan
menggunakan
metode
kemungkinan
maksimum bertujuan untuk mencari nilai fungsi loglikelihood yang paling maksimum (Fraley, 2002). Fungsi kemungkinan maksimum untuk peubah ganda yaitu
normal (n objek) -
-
-
-
-
-
-
(4
-
Pada model campuran dengan G komponen, fungsi kemungkinan maksimum likelihood didefinisikan sebagai:
Jika fkp dari pengamatan
yang diberikan oleh
adalah
, maka
loglikelihood data lengkap adalah: (5) Fraley & Raftery (2002) mengemukakan bahwa penduga parameter yang memaksimalkan
dihitung menggunakan
yang diperoleh pada
tahap E, dengan formula parameter sebagai berikut:
b.
Metode Bayes Pendugaan
parameter
dengan
menggunakan
metode
Bayes
yaitu
menggabungkan informasi yang dikandung dalam sampel dengan informasi lain yang telah tersedia sebelumnya. Asumsi yang digunakan dalam metode ini yaitu setiap parameter itu bervariasi menurut sebaran peluang tertentu yang disebut sebagai sebaran awal (Walpole, 1992). Sebaran peluang tersebut digunakan bersama-sama untuk menghitung sebaran posterior bagi parameter. Berdasarkan Fraley,2007 guna mencari penduga parameter yang dapat memaksimumkan posterior digunakan conjugate prior (konjugasi sebaran awal). Konjugasi sebaran
8
awal yang dimaksud untuk peubah ganda normal yaitu sebaran normal untuk kondisi rata-rata dengan syarat matriks peragam dan sebaran kebalikan wishart untuk kondisi matriks peragam. Dengan demikian fkp sebaran awal merupakan hasil kali dari sebaran normal dengan sebaran kebalikan wishart. Sebaran awal untuk rata-rata adalah sebaran normal (bersyarat pada matriks peragam), didefinisikan sebagai
-
-
(6)
dan sebaran awal matriks peragam yaitu sebaran kebalikan wishart, didefinisikan sebagai . (7)
dan
diasumsikan sama untuk semua komponen, dengan rincian
sebagai berikut: : rata-rata dari data : 0,01 (pemulusan bagian kurva BIC) : p+2 (untuk model spherical dan diagonal) :
(
dan
(untuk model ellipsoidal) adalah matriks peragam.
Fraley (2007) mengemukakan bahwa formula parameter yang digunakan guna memaksimalkan posterior, yang dihitung menggunakan
pada tahap E sebagai
berikut:
Iterasi ini berlangsung hingga diperoleh nilai loglikelihood atau nilai posterior yang konvergen.
9
Algoritma EM membutuhkan inisialisasi nilai awal dalam algoritmanya. Tingkat konvergensi bisa sangat lama apabila tidak digunakan nilai inisialisasi awal yang wajar. Banfiled (1993) menggunakan metode analisis gerombol berhirarki sebagai inisialisasi nilai awal
, kemudian secara iteratif dugaan nilai parameter akan
diperbaharui. Berdasarkan Fraley (2010), penentuan nilai awal
berdasarkan
penggabungan objek dilakukan berdasarkan jarak minimum. Karakteristik Geometrik Model Setiap gerombol yang terbentuk berpusat di
dan matriks peragam
yang dihasilkan akan menentukan karakteristik geometrik yaitu bentuk, volume dan orientasi (Fraley dan Raftery 2002). Pencirian sebaran geometrik (orientasi, bentuk, volume) mungkin akan diperoleh dari berbagai macam bentuk gerombol atau terbatas pada gerombol yang sama. Bentuk komponen matriks peragam terdiri atas tiga macam yaitu spherical, diagonal dan ellipsoidal. Fraley (2007) mengemukakan formula berdasarkan metode pendugaan parameter yang digunakan, yaitu: a.
Metode kemungkinan maksimum 1.
2.
Bentuk spherical (sebanding dengan matriks identitas) -
Spherical sama
-
Spherical berbeda
Bentuk diagonal (sejajar sumbu) -
Diagonal sama
-
Diagonal berbeda
10
3.
b.
Bentuk ellipsoidal -
Diagonal sama
-
Diagonal berbeda
Metode bayes 1.
2.
Bentuk spherical (sebanding dengan matriks identitas) -
Spherical sama
-
Spherical berbeda
Bentuk diagonal (sejajar sumbu) -
Diagonal sama
-
Diagonal berbeda
3 3.
dengan
Bentuk ellipsoidal -
Diagonal sama
-
Diagonal berbeda
-
-
11
Guna mendefinisikan kelas metode penggerombolan berhirarki berdasarkan geometri lintas gerombol, Branfield dan Raftery (1993) menyatakan matriks peragam melalui suku-suku dekomposisi akar ciri untuk komponen
gerombol
model campuran peubah ganda dalam bentuk: (9 dimana adalah matriks vektor ciri adalah akar ciri terbesar dari adalah matriks diagonal dengan elemennya proporsional terhadap akar ciri dari
, yaitu
dimana
Ketiga suku dekomposisi diatas mencirikan karakteristik geometrik dimana mencirikan orientasi dari k gerombol,
mencirikan ukuran dan
mencirikan
bentuk. Ukuran tersebut diartikan sebagai volume dari cluster dalam p peubah yang berisi objek. Pencirian sebaran geometrik (orientasi, bentuk, volume) mungkin akan diperoleh dari berbagai macam bentuk gerombol atau terbatas pada gerombol yang sama. Matriks peragam untuk semua komponen bisa sama atau bervariasi, yang secara umum dapat dilihat pada Tabel 1. Penentuan Jumlah Gerombol Jumlah gerombol terbaik dapat ditentukan dengan memilih model terbaik melalui nilai BIC terbesar. Fraley (1998) menyatakan bahwa pemilihan model terbaik dilakukan dengan membandingkan model parameterisasi matriks peragam yang berbeda dan banyaknya gerombol yang berbeda. Secara umum formulasi yang digunakan adalah sebagai berikut: (10) dimana = loglikelihood yang dimaksimalkan untuk model dan data = jumlah parameter bebas yang diduga dalam model = jumlah observasi dalam data.
12
Tabel 1
Matriks peragam untuk model campuran normal ganda dan interpretasi geometrik
Simbol Mclust EII VII EEI VEI EVI VVI EEE VEE
Bentuk
Prior
Spherical Spherical Diagonal Diagonal Diagonal Diagonal Ellipsoidal
Dipakai untuk
Inverse gamma Inverse gamma Inverse gamma Setiap anggota diagonal
Inverse gamma Setiap anggota diagonal Inverse wishart Inverse gamma Inverse wishart
EVE VVE EEV VEV EVV
Ellipsoidal Ellipsoidal Inverse gamma Setiap anggota diagonal Ellipsoidal Inverse gamma Setiap anggota diagonal Ellipsoidal Ellipsoidal Inverse gamma Inverse wishart VVV Ellipsoidal Inverse wishart Sumber: (Fraley, 2007). Jika pada algoritma EM ingin dihasilkan nilai maksimum posterior yang konvergen, maka
pada persamaan diatas diganti dengan nilai
posterior (Fraley,2007). Dalam perhitungan nilai BIC setiap model dibutuhkan informasi mengenai jumlah parameter bebas yang diduga, yang secara garis besar dapat dilihat pada Tabel 2. Tabel 2
Parameter bebas tiap model
Model
Parameter Bebas
( ( ( ( Sumber: (Celeux,2006)
(
13
Fraley
(2002)
membuat
strategi
metode
berbasis
model
dengan
mengkombinasikan penggerombolan hirarki, algoritma EM dan faktor bayes, dengan langkah–langkah sebagai berikut: 1.
Tentukan banyak gerombol maksimum ( ) dari himpunan model campuran
2.
Lakukan penggerombolan secara hirarki penggabungan, untuk setiap model campuran normal ganda. Hasil gerombol ini ditransformasikan ke dalam peubah indikator, yang kemudian digunakan sebagai nilai awal untuk algoritma EM
3.
Lakukan algoritma EM untuk setiap model dan setiap gerombol
3
,
yang dimulai dengan klasifikasi dari gerombol berhirarki 4.
Hitung nilai BIC untuk kasus satu gerombol pada setiap model dan model campuran, dengan parameter optimal dari algoritma EM untuk gerombol
3
