BAYESIAN HIREARIRCHAL ALGORITHM (Part 2)

ALGORITMA

Algoritma Bayesian Hirearirchal Clustering dengan metode agglomerative untuk mengelompokkan N objek (item/variabel):

1.      Dimulai dengan banyaknya N cluster, dimana setiap cluster mengandung entiti tunggal dan sebuah matriks simetrik dengan jarak (similiries)  dengan tipe .

2.      Selanjutnya mencari pasangan cluster yang memiliki jarak terdekat (paling mirip). Misalkan jarak terdekat antara cluster U dan V adalah .

3.      Gabungkan cluster U dan V. label cluster baru yang terbentuk adalah . Karena cluster U dan V telah bergabung maka akan dilakukan peng-update-an matriks jarak, yaitu dengan cara:

a. Hapus baris dan kolom yang bersesuaian dengan cluster  dan

b. Tambahkan baris dan kolom yang memberikan jarak-jarak antara cluster  dan cluster-cluster yang tersisa.

4.      Ulangi langkah 2 dan 3 sebanyak  kali. Ketika algoritma berakhir, maka semua objek akan berakhir dalam cluster tunggal.

 

Pada Bayesian Hirearirchal Clustering menggunakan uji hipotesis statistik untuk memilih cluster yang akan digabungkan.

Misalkan  menandakan kumpulan data, dan  untuk setiap data pada titik cabang dari subtree .

Untuk setiap penggabungan, akan dibandingkan dua hipotesis. Hipotesis pertama  adalah semua data yang ada berada di dalam , yang independent dan identik berasal dari model peluang yang sama,  dengan parameter yang tidak diketahui .

Misalkan peluang ini menggunakan model multivariat Gaussian, dengan parameter  meskipun penting untuk menekankan bahwa untuk berbagai jenis data, lebih tepat untuk menggunakan model peluang yang berbeda. Untuk mengetahui kemungkinan hipotesis, terlebih dahulu perlu ditentukan parameter model,  dengan hyperparameters . Selanjutnya kita memiliki komponen utnuk menghitung peluang data  dengan hipotesis :

Perhitungan peluang ini berarti semua data yang ada dalam secara umum berasal dari asusmsi nilai parameter yang sama dari bentuk model . Model ini merupakan model dasar untuk mengukur seberapa baik data dapat digabung menjadi satu cluster. Jika kita memilih model dengan konjugasi prior (misalnya prior Normal-Inverse-Wishart untuk data kontinu Normal atau Dirichlet prior untuk data discrete Multinomial) integral ini dipisahkan.

Hipotesis alternatif untuk adalah data di  memiliki dua atau lebih cluster di dalamnya. Menghitung eksponen banyaknya kemungkinan cara untuk membagi  menjadi dua atau lebih. Jika kita membatasi clustering dengan partisi data adalah konstan dengan substree  dan , kita bisa menghitung jumlah yang efisien dengan menggunakan rekursi.

Peluang dari data pada hipotesis alternative, , berasal dari subtree dapat di tuliskan seabgai berikut:

 

Dengan mengkombinasikan peluang dari data pada hipotesis  dan  dihitung dengan mengasusmsikan semua titik adalah milik satu cluster,diperoleh peluang marjinal untuk data :  

 

Persamaan ini didefinisikan secara rekursif, pada persamaan hipotesis pertama adalah cluster tunggal dalam  dan pada persamaan kedua adalah jumlah semua cluster yang lain dari data yang ada di dalam  yang kosnsiten dengan struktur pohon seperti gambar di bawah ini.

 

Untuk peluang posterior dari hipotesis cluster yang telah bergabung dapat dituliskan sebagai berikut:

 

Persamaan tersebut dapat digunakan untuk memutuskan dua pohon yang akan digabungkan, serta dapat juga digunakan untuk memutuskan cluster gabungan yang akan menjadi sturktur hirarki yang terakhir.

 Secara umum algoritmanya dapat dilihat sebagai berikut: