Clustering Kholistianingsih, 10/306701/PTK/06919 Jurusan Teknik Elektro FT UGM, Yogyakartaan
7.6.ALGORITMA CLUSTERING YANG LAIN Pada bagian ini, kita mempertimbangkan algoritma yang menghasilkan cluster tunggal dan tidak termasuk kategori optimisasi fungsi harga atau sekuensial. Competitive Leaky Learning Algorithm Competive Leaky Learning (LLA) merupakan algorithm yang cocok untuk mengungkap cluster seragam. Jumlah cluster, m, dari himpunan data X, diasumsikan telah diketahui. Tujuan dari LLA adalah untuk memindahkan m vektor parameter berdimensi l, wj , j = 1,. . . , M, ke daerah yang "padat" dalam titik-titik dari X. Setiap parameter vektor menggambarkan satu daerah "padat" (cluster). Strateginya adalah kompetisi antara wj tersebut. Algorithmis LLA bersifat iterative yaitu dimulai dengan beberapa perkiraan awal w1 (0),. . . , wm (0), untuk w1,. . . , wm,. Pada setiap iterasi, t, vektor x disajikan pada algoritma dan wj (t -1) yang lebih dekat dengan x daripada wk(t -1) lainnya, untuk k = 1. . . , m (k ≠j)didentifikasi. wj (t -1) adalah pemenang dalam kompetisi pada x, dan wj (t) dihitung dengan persamaan 7.2. (7.2) Sedangkan wk(t) yang lain dihitung dengan persamaan 7.3. (7.3) Dengan w >> l. Cluster Cj(t), pada clustering yang dibentuk pada itersi ke-t, terdiri dari semua xX dimana wj(t) yang lebih dekat dibandingkan dengan bobot yang lain dengan j=1,…,m. Harus dipastikan bahwa, dalam satu epoch, yang terdiri dari N iterasi brerturut-turut, semua vektor data yang akan diperhatikan oleh LLA. Konvergensi dicapai bila nilai-nilai wj tersebut hampir tidak berubah antara dua epoch yang berurutan atau jumlah maksimum epoch telah dicapai. Keluaran adalah perkiaraan nilai-nilai wj dan clustering yang sesuai dimana setiap cluster yang terdiri Cj terdiri dari semua vektor x dari X yang terletak lebih dekat dengan wj daripada bobot lainnya. Untuk menerapkan LLA pada himpunan data X, ketik
1
dimana:
X berisi vektor data dalam kolom-kolomnya, w_ini berisi perkiraan awal dari bobot di kolom-kolomnya, m adalah jumlah bobot (digunakan hanya ketika w_ini kosong), eta_vec adalah vektor dua dimensi yang berisi parameter ηw dan ηl dari algoritma, sed adalah "seed" untuk built-inMATLAB fungsi rand, max_epoch adalah jumlah epoch maksimum pada algoritma yang diperbolehkan, e_thres adalah parameter (skalar) yang digunakan dalam kondisi akhir, init_ proc didefinisikan sebagai di PCM, w berisi perkiraan akhir dari bobot di kolom-kolomnya, bel adalah vektor berdimensi N yang elemen ke-I berisi indeks dari bobot yang terletak paling dekat dengan xi, epoch adalah bilangan epoch yang dilakukan oleh algoritma dalam rangka untuk mencapai kondisi konvergen. Keterangan
Parameter Pesat Pembelajaran ηw dan ηl dipilih pada rentang [0, 1] dengan ηw >> ηl.
Secara geometris berbicara, semua bobot bergerak menuju vektor data x dengan berdasar algoritma. Namun, yang kalah, bergerak dengan pesat yang lebih lambat daripada pemenang, seperti yang ditunjukkan dengan pilihan nilai ηw dan ηl.
LLA "memaksakan" struktur pengelompokan/clustering pada X, seperti halnya dengan sebagian besar algoritma yang telah dibahas.
LLA tidak terlalu sensitif terhadap inisialisasi dari wj karena, bahkan jika wj pada awal terletak jauh dari daerah dimana vektor-vektor data berada, secara bertahap akan bergerak ke wilayah tersebut sebagaimana pada Pers. (7.3). Oleh karena itu, kemungkinan untuk menang di suatu x yang diberikan terjadi setelah beberapa iterasi.
Untuk ηl = 0, skema pembelajaran dasar kompetitif dicapai. Dalam hal ini, hanya pemenang diperbarui (Yaitu, bergerak ke arah vektor data x ), sedangkan nilai-nilai dari bobot lainnya tetap tidak berubah. Hal ini membuat sensitifitas algoritma terhadap inisialisasi kurang karena jika wj awal terletak jauh dari daerah mana vektor-vektor data berada, kemungkinan untuk kalah dalam semua kompetisi untuk vektor-vektor dari X. Dalam hal ini, tidak ada cara dapat bergerak mendekat ke daerah di mana data berada dan sehingga tidak memiliki kemampuan untuk mewakili secara fisik cluster yang terbentuk di X (sehingga wj adalah juga disebut bobot mati).
•Algoritma pembelajaran kompetitif lain telah diusulkan dalam literatur ini. Dalam Algoritma yang mirip adalah adalah skema self-organizing map (SOM). Namun, dalam bobot-bobot SOM, WJ saling terkait [Theo 09, Bagian 15.3].
Latihan 7.6.1 1. Terapkan LLA pada himpunan data X3 yang dihasilkan dalam Contoh 7.5.1, untuk m, = 4 m = 3, dan m=6. Gunakan ηw = 0,1 dan ηl = 0,0001, max_epoch = 100, dan e_thres = 0,0001. Gunakan fungsi MATLAB distant_init inisialisasi wj. Untuk setiap kasus, plot titik data (semua dengan warna yang sama) serta wj (perkiraan akhir). 2
2. Ulangi langkah 1 untuk m = 4, di mana sekarang ηl = 0,01. Perhatikan bahwa, dalam kasus di mana jumlah bobot yang dibawah atau diatas perkiraan, clustering yang dihasilkan tidak sesuai dengan struktur clustering sebenarnya dari titik di X3. Selain itu, jika ηl tidak jauh lebih kecil dari ηw, algoritma memberikan hasil yang buruk, bahkan jika m adalah sama dengan jumlah cluster yang benar. Latihan 7.6.2 Terapkan LLA pada himpunan data X5 yang dihasilkan dalam Contoh 7.5.3, untuk m = 2, mengadopsi nilainilai parameter yang digunakan dalam Latihan 7.6.1. Petunjuk Perhatikan bahwa berhasil mengidentifikasi dua cluster meskipun mereka memiliki ukuran yang secara signifikan berbeda, dengan kata lain , k-means dan FCM. Latihan 7.6.3 Terapkan LLA pada himpunan data X3 yang dihasilkan dalam Contoh 7.5.1, untuk m = 4 di mana sekarang wj diinisialisasi sebagai w1 (0) = [5,5 , 4,5] T, w2 (0) = [4,5, 5,5] T, w3 = [5 , 5] T, dan w4 = [50, 50] T. Gunakan ηw = 0,1 dan (a) ηl = 0,0001 dan (b) ηl = 0 (skema belajar kompetitif dasar). Perhatikan bahwa untuk ηl = 0,0001, semua bobot mewakili cluster di X3, meskipun bobot w4 telah diinisialisasi jauh dari daerah di mana titik X3 berada. Untuk ηl = 0, bagaimanapun, W4 tidak berubah. Valley-Seeking Clustering Algorithm Berdasarkan metode ini (dikenal sebagai VS), cluster dianggap sebagai puncak dari pdf, p (x), yang menggambarkan X, terpisahkan oleh lembah-lembah. Berbeda dengan algoritma-algoritma sebelumnya, di sini tidak ada bobot-bobot (vektor-vektor parameter) yang digunakan. Sebaliknya, pengelompokan/ clustering didasarkan pada daerah lokal, V (x), sekitar setiap vektor data x ∈ X. Metode yang terakhir didefinisikan sebagai himpunan vektor-vektor di X (termasuk x) yang terletak dengan jarak dari x kurang daripada a, di mana a adalah parameter yang ditetapkan pengguna. Sebagai ukuran jarak, Jarak Euclidean mungkin digunakan (jarak lain dapat juga digunakan). VS juga membutuhkan suatu nilai (di atas perkiraan) jumlah cluster, m. Algoritma bersifat iteratif, dimulai dengan tugas awal dari vektor X untuk m cluster; pada setiap epoch (N iterasi yang berurutan) semua vektor data yang disajikan sekali. Selama epoch ke-t dan untuk setiap xi dalam X, i = 1,. . . , N,daerah V(xi) ditentukan dan cluster di mana sebagian besar vektor data yang merupakan milik V (xi) diidentifikasi dan disimpan. Setelah semua vektor data yang telah disajikan (selama epoch ke-t), reclustering/pengelompokkan kembali berlangsung dan setiap xi sekarang ditugaskan ke cluster yang memiliki jumlah titik terbesar dalam V (xi). Algoritma berakhir ketika tidak terjadi reclustering lagi antara dua epoch yang berurutan. Untuk menerapkan algoritma VS pada himpunan data X, ketik dimana:
X berisi vektor data dalam kolom-kolomnya,
a adalah parameter yang menentukan ukuran dari lingkungan ketetanggaan V (x) dari titik data x,
3
bel_ini adalah sebuah vektor berdimensi yang koordinat ke-I berisi label dari cluster dimana vektor xi diinisialisasi,
max_iter adalah jumlah iterasi maksimum yang diperbolehkan,
bel adalah vektor berdimensi N yang memiliki struktur yang sama seperti bel_ini, yang dijelaskan sebelumnya dan berisi label cluster xi setelah konvergen,
iter adalah jumlah iterasi yang dilakukan sampai konvergensi tercapai.
Keterangan
Dalam kasus tertentu, VS dapat mengatasi cluster tidak seragam.
Algoritma sensitive dengan pilihan nilai a. Salah satu cara untuk mengatasi sensitivitas ini adalah dengan menjalankan algoritma untuk beberapa nilai a dan hati-hati menginterpretasikan hasil.
Algorithma sensitif terhadap inisialisasi tugas dari vektor data untuk cluster. Inisialisasi yang buruk menghasilkan clustering yang buruk. Salah satu penyelesaian adalah dengan menjalankan algoritma yang lain (misalnya, algoritma sekuensial) dan menggunakan clustering hasil sebagai harga awal untuk VS.
VS adalah algoritma mode-seeking. Artinya, jika digunakan nilai yang melebihi jumlah cluster sebenarnya dari X sebagai nilai awal, maka pada prinsipnya, setelah konvergensi, beberapa dari mereka akan menjadi kosong. Ini berarti bahwa VS tidak memaksakan struktur pengelompokan pada X. Dalam hal ini, menyerupai PCM.
Latihan 7.6.4 Pertimbangkan himpunan data X3 yang dihasilkan dalam Contoh 7.5.1. Gunakan kuadrat jarak Euclidean dan terapkan algoritma VS untuk a = 12,1.52,22,. . . , 82. Untuk definisi pengelompokan/clustering awal (a) gunakan m = 7 cluster dengan inisialisasi acak, dan (b) output dari algoritma BSAS dengan kesimpulan.
= 2,5. Untuk setiap kasus, plot hasil clustering dan buat
Petunjuk Untuk membangkitkan inisialisasi clustering acak ketik
Untuk membangkitkan inisialisasi clustering menggunakan algoritma BSAS, ketik
4
Untuk menerapkan VS pada X3 dan untuk plot hasil clustering, ketik
VS dengan inisialisasi acak gagal untuk mengidentifikasi struktur pengelompokan/clustering X3; sebaliknya ketika inisialisasi dengan BSAS. Hal ini terjadi karena, dalam kasus di mana adalah "kecil," BSAS cenderung untuk menghasilkan beberapa compact cluster kecil tanpa overlap yang signifikan. Penerapan VS antara lain pada clustering akan menggabungkan cluster tetangga yang kecil menjadi bagian dari cluster yang lebih besar. Sebaliknya, dengan inisialisasi acak, pengelompokan/clustering awal cenderung memiliki beberapa cluster yang overlap, yang lebih sulit untuk menangani (dalam hal ini, setiap V (xi) mungkin berisi titik-titik dari semua cluster). Perhatikan bahwa tidak semua nilai-nilai pengelompokan/clustering yang benar dari X3.
dari
a,
X5
yang
tepat
untuk
mengungkap
struktur
Latihan 7.6.5 Ulangi Latihan Petunjuk
7.6.4
untuk
himpunan
data
dihasilkan
dalam
Contoh
7.5.3.
Perhatikan bahwa VS berhasil mengidentifikasi dua kelompok yang mempunyai ukuran yang berbeda secara signifikan. Contoh 7.6.1 1. Bangkitkan dan plot data set X8, yang berisi 650 vektor data berdimensi 2. 300 pertama berada sekitar setengah lingkaran dengan jari-jari r = 6, yang berpusat di (-15,0), dan memiliki koordinat kedua positif. 200 berikutnya terletak sekitar ruas garis dengan titik akhir (10, -7) dan (10,7). 100 berikutnya terletak sekitar setengah lingkaran dengan jari-jari r = 3, yang berpusat di (21,0), dan memiliki koordinat kedua negatif. Akhirnya, 50 titik terakhir milik spiral Archimedes dan didefinisikan sebagai (x, y) = (aspθ cos (θ), aspθ sin (θ)), di mana asp = 0,2 (parameter yang ditetapkan pengguna) dan θ = π, π + s, π +2 s,. . , 6π, di mana s = 5π/49. 2. Gunakan kuadrat jarak Euclidean dan menerapkan algoritma VS X8 untuk a = 12,1.52,22,. . , 82.. Untuk definisi pengelompokan/clustering awal, menggunakan output dari algoritma BSASdengan =2,5. Gambarkan kesimpulan anda. 3. Pertimbangkan hasil dari VS jika setengah lingkaran di X8, yang sesuai dengan kelompok ketiga dati titik-titik, dipusatkan di (12,0).
5
Penyelesaian. Ambil langkah-langkah berikut: Langkah 1. Untuk membangkitkan kelompok pertama dari titik-titik di X8, ketik
Untuk membangkitkan kelompok kedua, ketik
Untuk membangkitkan kelompok ketiga, ketik
6
Dan, untuk membangkitkan kelompok ketiga, ketik
Langkah 2. Untuk nilai-nilai a dalam rentang [42, 62], VS berhasil mengidentifikasi cluster-cluster pada X8 (lihat Gambar 7.9 (a)). Langkah 3. Untuk skenario alternatif (Gambar 7.9 (b)), VS gagal (mengidentifikasi dua cluster paling kanan sebagai sebuah cluster tunggal). Dengan demikian, kami menyimpulkan bahwa VS dapat menangani dengan cluster bentuk tidak teratur hanya di bawah asumsi bahwa mereka benar-benar terpisah satu sama lain.
Gbr 7.9. Clustering yang dihasilkan oleh algoritma VS dalam Contoh 7.6.1: (a) langkah 2(empat cluster); (b) langkah 3 (tiga cluster). Titik-titik dari cluster yang berbeda ditunjukkan dengan lambing/baying-bayang abu-abu yang berbeda. Clustering Spektral Algoritma pengelompokan/clustering spektral memanfaatkan konsep-konsep teori graph dan kriteria optimasi tertentu yang mengacu pada teori matrik. Lebih khusus, algoritma semacam ini membangun sebuah graf berbobot, G, di mana (a) masing-masing titik, vi, sesuai dengan titik, xi, dari himpunan data X, dan kemudian (b) asosiasi sebuah bobot wij dengan tepi eij yang menghubungkan dua simpul, vi dan vj. 7
Bobot wij merupakan indikasi dari "jarak" antara titik data yang sesuai xi dan xj. Tujuannya adalah untuk memotong grafik dalam m komponen terputus melalui optimasi kriteria. Komponen ini mengidentifikasi kelompok/cluster dibawah X. Dalam sekuelnya, kita mempertimbangkan kasus 2-cluster (yaitu, m = 2); kriteria yang akan dioptimalkan adalah dipotong yang disebut normalized cut atau potongan ternormalisasi, atau Ncut [Theo 09, Bagian 15.2.4]. Sebelum menjelaskan algoritma, dijelaskan dulu beberapa definisi. Di antara berbagai cara untuk mendefinisikan bobot dari grafik, yang umum adalah (7.4) di mana e dan σ2 parameter yang ditetapkan pengguna dan | | · | | menunjukkan jarak Euclidean. Dengan kata, diberikan titik data xi, untuk semua titik xj yang terletak dari xi sebuah jarak yang lebih besar daripada e, kita memberikan wij = 0. Untuk titik xj yang jarak dari xi kurang dari e, bobot wij menurun sesuai jarak antara xi dan kan xj meningkat. Jadi, bobot-bobot mengkodekan informasi yang berkaitan dengan jarak antara titik-titik pada X. Setelah graf berbobot telah dibentuk, tujuannya adalah untuk membagi (memotong) menjadi dua bagian, katakanlah A dan B, sehingga titik di A dan B memiliki kesamaan paling kecil dibandingkan dengan bipartitioning lainnya. Kesamaan dalam hal ini adalah diukur dalam hal jarak bobot terkait. Berdasarkan kriteria normalized cut, pemisahan dua bagian dari grafik (cluster) sangat berperan sehingga tepi-tepi yang menghubungkan dua bagian memiliki jumlah bobot minimum (mengindiksikan cluster terpisahkan sebanyak mungkin berdasarkan dengan kriteria yang digunakan). Kriteria normalized cut juga mempertimbangkan "volume" dari cluster dan perhatikan untuk menghindari pembentukan kelompok kecil yang terisolir. Optimasi masing-masing ternyata menjadi NP-hard. Hal ini diatasi dengan sedikit formulasi ulang masalah, yang kemudian menjadi masalah eigenvalue-eigenvector dari matriks Laplace dari grafik. Matriks Laplace secara langsung berkaitan bobot asosiasi dengan grafik, yaitu, ia mengkodekan informasi jarak antara titik yang dapat dikelompokkan [Theo 09, Bagian 15.2.4]. Untuk menerapkan algoritma yang dijelaskan pada himpunan data X, ketik
dimana:
X vektor berisi data dalam kolom-kolomnya,
e adalah parameter yang mendefinisikan ukuran dari lingkungan ketetanggaan sekitar setiap vektor,
sigma2 adalah parameter yang ditetapkan pengguna yang mengontrol lebar dari fungsi Gaussian dalam Pers. (7.4),
bel adalah vektor berdimensi N yang berisi elemen ke-i beriri label dari cluster data vektor ke-i diberikan.
8
Keterangan
algoritma pengelompokan/clustering spektral memaksakan struktur pengelompokan/clustering pada X. Pada prinsipnya, algoritma pengelompokan spektral dapat memulihkan cluster berbagai bentuk algoritma. Pengelompokan spektral lain yang berasal optimasi kriteria seperti yang disebut ratio-cut telah diusulkan [Theo 09, Bagian 15.2.4]. Sebuah diskusi tentang kualitas clustering bahwa hasil dari metode pengelompokan spektral dapat ditemukan di [Guat 98]. Dalam kasus di mana lebih dari dua cluster yang diharapkan, skema sebelumnya dapat digunakan secara hierarkis. Artinya, di setiap langkah menghasilkan cluster yang dipartisi lagi menjadi dua kelompok [Shi 00]. Sebuah pendekatan yang berbeda dapat ditemukan di [Luxb 07].
Latihan 7.6.6 Perhatikan himpunan data X2 dari Latihan 7.4.1 dan terapkan algoritma sebelumnya yang menggunakan e = 2 dan sigma2 = 2. Gambarkan kesimpulan. Petunjuk Perhatikan bahwa algoritma memaksakan struktur pengelompokan/clustering berdasarkan X2, meskipun X2 tidak memiliki struktur pengelompokan/clustering. Latihan 7.6.7 1. Bangkitkan dan plot himpunan data X9, yang terdiri dari 200 vektor berdimensi 2. 100 pertama dari distribusi Gaussian dengan mean [0, 0] T; titik yang tersisa berasal dari distribusi Gaussian dengan mean [5, 5] T. Kedua distribusi berbagi matriks kovarians identitas. 2. Terapkan algoritma clustering spektral sebelumnya pada X9 menggunakan e = 2 dan sigma2=2. Gambarkan kesimpulan. Petunjuk Perhatikan bahwa algoritma dengan benar mengidentifikasi kelompok dalam X9. Contoh 7.6.2. Lakukan hal berikut: 1. Bangkitkan dan plot himpunan data X10 yang terdiri dari 400 titik data yang terletak di sekitar dua lingkaran. Secara khusus, 200 titik pertama yang berada di lingkaran dengan jari-jari r1 = 3, yang berpusat di (0,0); sisa titik terletak di sekitar lingkaran dengan jari-jari r2 = 6, yang berpusat di (1,1). 2. Terapkan algoritma clustering spektral pada X10 untuk e = 1,5 dan sigma2 = 2 dan plot hasilnya. 3. Ulangi hal ini untuk e = 3. Berikan komentar pada hasil.
9
Penyelesaian. Ambil langkah-langkah berikut: Langkah 1. Untuk menghasilkan himpunan data X10, ketik
Plot himpunan data dengan mengetikan
Langkah 2. Untuk menerapkan algoritma clustering spectral, ketik
10
Gbr 7.10. Hasil clustering dari penerapan algoritma clustering spectral pada himpunan data X10 pada Contoh 7.6.2 ketika (a)e=1,5 dan (b)e=3. Titik-titik yang diberikan cluster yang sama ditunjukkan dengan lambing yang sama. Terlihat peka terhadap pilihan parameter. Plot hasil clustering (lihat Gbr 7.10.(a)), ketik
Langkah 3. Bekerja seperti pada langkah 2, pengaturan e sama dengan 3 (Gambar 7.10 (b)). Membandingkan Gambar 7.10(a) dan7.10(b), perhatikan pengaruh nilai-nilai parameter pada kualitas clustering yang dihasilkan.Menyediakan penjelasan fisik untuk itu. Latihan 7.6.8 Ulangi Contoh 7.6.2 untuk kasus di mana lingkaran kedua ini berpusat di (3,3), untuk berbagai nilai e dan sigma2. Berikan komentar pada hasil. Petunjuk Perhatikan bahwa, dalam kasus ini, algoritma gagal untuk mengidentifikasi dua cluster (overlap). 7.7. ALGORITMA CLUSTERING HIRARKI Berbeda dengan algoritma pengelompokan/clustering yang telah dibahas sejauh ini, yang kembali pada clustering tunggal, algoritma pada bagian ini adalah hierarchy ofN nested clustering, di mana N adalah jumlah titik data dalam X. Sebuah pengelompokan/clustering , , Terdiri dari k cluster , dikatakan bersarang di clustering ’, berisi r (
Dua kategori utama dari algoritma pengelompokan hirarki adalah: agglomerative. Dengan clustering awal 0 terdiri dari N cluster, masing-masing berisi satu elemen X. Clustering 1 diperoleh pada langkah berikutnya, berisi (N -1) cluster dan0 bersarang di dalamnya. Akhirnya, N-1 clustering diperoleh, yang berisi sebuah cluster tunggal (seluruh himpunan data X). Divisive/memecah belah. Di sini jalur balik diikuti. Cluster awal 0 terdiri dari cluster tunggal (seluruh himpunan data X). Pada langkah selanjutnya clustering 1 adalah dibuat, yang terdiri dari dua cluster dan bersarang di 0. Akhirnya, N-1 clustering diperoleh, yang terdiri dari N cluster, masing-masing berisi satu elemen dari X. Untuk selanjutnya , kita hanya mempertimbangkan pengelompokan algoritma agglomerative.khususnya, (a) skema algoritma agglomerative umum dan (b) algoritma tertentu yang berkaitan dengan yang dibahas. 7.7.1 Skema Agglomerative Umum Skema (dikenal sebagai GAS) dimulai dengan clustering 0 yang terdiri dari N cluster, masing-masing berisi vektor data tunggal. Clustering t (hirarki clustering pada tingkat ke-t ) terdiri dari (a)cluster dibentuk oleh penggabungan dari dua cluster "paling mirip" ("jarak paling kecil") clustering t-1. Dan (b) semua cluster sisa dari clustering t-1 . Clustering yang dihasilkan t sekarang berisi (N-t) cluster (perhatikan bahwat-1mengandung (N-t +1) cluster). Algoritma berlanjut sampai clustering N-t dibuat, di mana semua titik menjadi milik cluster tunggal. Ia mengembalikan hirarki clustering. Keterangan
Jika dua titik sama-sama dalam sebuah cluster tunggal pada clustering t (level ke-t pada hirarki clustering), mereka akan tetap berada dalam cluster yang sama untuk semua clustering berikutnya (yaitu, untuk t+1,..., N-1). Jumlah operasi yang diperlukan oleh GAS adalah O (N3).
Isu penting yang terkait dengan GAS adalah definisi dari sebuah ukuran kedekatan antara cluster. Untuk selanjutnya , kita membahas definisi rekursif dari jarak (dinotasikan dengan d (·)) antara dua cluster, khususnya, jarak antara setiap pasangan cluster dalam clustering t didefinisikan dalam hal jarak antara pasangan-pasangan pada cluster t-1. Hal ini menimbulkan beberapa algoritma agglomerative hirarkis yang paling banyak digunakan. Jika d (xi, xj) menunjukkan jarak antara dua vektor data. Menurut definisi, jarak antara dua elemen cluster tunggal didefinisikan sebagai jarak antara elemen-elemen mereka: d({xi}, {xj}) ≡ d (xi, xj). Mempertimbangkan dua cluster Cq, Cs pada clustering t, t> 0 level ke-t hirarki):
Jika kedua Cq dan Cs termasuk dalam clustering t-1 (level ke-t-1), Jarak mereka tetap tidak berubah di t. Jika Cq adalah hasil dari penggabungan cluster Ci dan Cj dalam clustering t-1, dan Cs adalah cluster lain yang berbeda dari Ci dan Cj dalam t-1, maka d (Cq, Cs) didefinisikan sebagai (7.5)
Pilihan yang berbeda dari parameter ai, aj, b, dan c menimbulkan pengukuran jarak yang berbeda antar
12
cluster dan akibatnya menyebabkan algoritma pengelompokan/clustering yang berbeda. Dua diantaranya mengikuti. 7.7.2 Algoritma Clustering Agglomerative Tertentu Jalir tunggal: Ini hasil dari GAS jika dalam Pers. (7.5) kita atur ai = aj = 0,5, b = 0, dan c =- 0,5. Dalam hal ini Persamaan (7.5) menjadi (7.6) Persamaan (7.6) juga dapat ditulis sebagai (7.7) Jalur Lengkap: Ini hasil dari GAS jika dalam Persamaan (7.5) kita atur ai = aj = 0,5, b = 0, dan c = 0,5. Dalam hal ini Persamaan (7,5) menjadi (7.8) Ternyata Persamaan (7.8) juga dapat ditulis sebagai (7.9) Contoh 7.7.1. Pertimbangkan himpunan data set X11 = {x1, x2, x3, x4, x5, x6} dan
menjadi matriks 6 × 6 yang elemen(i, j), dij, adalah jarak antara vektor data xi dan xj (lihat Gambar 7.11). 1. Terapkan, langkah demi langkah, algoritma jalur tunggal di X11. 2. Ulangi langkah 1 untuk algoritma jalur lengkap.
Gbr. 7.11 Himpunan data yang dipertimbangkan dalam Contoh 7.7.1. Angka (1, 3, 3,5, 3,6, 3,7) menunjukkan jarak masing-masing. Besar nilai jarak tidak ditampilkan.
13
Penyelesaian . Ambil langkah-langkah berikut: Langkah 1. Algoritma jalur tunggal. Inisialisasi 0 = {{x1}, {x2}, { x3}, {x4}, {x5}, {x6}} (clustering hirarki level 0). Dua kelompok terdekat pada 0 adalah { x1}dan {x2}, dengan d ({x1}, {x2}) = 1. Ini digabungkan untuk membentuk pengelompokan berikutnya, 1 = {{x1, x2}, { x3}, {x4 }, {x5}, {x6}} (level 1). Karena cluster yang paling dekat dalam 1 adalah {x1, x2} dan {x3} , dengan Persamaan (7.7), d ({x1, x2}, { x3}) = min (d ({x1}, {x3}), d ({x2}, {x3})) = 3 adalah jarak minimum antara setiap pasang cluster 1. Jadi, 2 = {{x1, x2, x3}, {x4}, {x5}, {x6}} (level 2). Cluster terdekat pada 2 adalah {x4 } dan {x5} karena d ({x4}, {x5}) = 3.5 adalah jarak minimum antara setiap pasang cluster 2. Jadi, jarak minimum antara setiap pasang cluster 3 = {{x1, x2, x3}, {x4, x5}, {x6}} (level 3). Demikian pula, cluster yang paling dekat dalam jarak minimum antara setiap pasang cluster 3 adalah {x4, x5} dan {x6}, karena d ({x4, x5}, {x6}) = min (d ({x4}, {x6}), d ({x5}, {x6 }) = 3,6 adalah jarak minimum antara setiap pasangan cluster di jarak minimum antara setiap pasang cluster 3 , dan jarak minimum antara setiap pasang cluster 4 = {{x1, x2, x3}, {x4, x5, x6}} (level 4). Akhirnya, dua kelompok dalam jarak minimum antara setiap pasang cluster 4 yang bergabung untuk membentuk pengelompokan akhir, jarak minimum antara setiap pasang cluster 5 = {{x1, x2, x3, x4, x5, x6}} (level 5). Perhatikan bahwa d ({x1, x2, x3}, {x4, x5, x6}) = Min i = 1, 2, 3, j = 4, 5, 6 d (xi, xj) = 20. Langkah 2. algoritma jalur lengkap. Inisialisasi 0 = {{x1}, {x2}, { x3}, {x4}, {x5}, {x6}} (clustering hirarki level 0). Dua kelompok terdekat pada 0 adalah { x1}dan {x2}, dengan d ({x1}, {x2}) = 1. Ini digabungkan untuk membentuk pengelompokan berikutnya, 1 = {{x1, x2}, { x3}, {x4 }, {x5}, {x6}} (level 1). Karena cluster yang paling dekat dalam 1 adalah {x4 } dan {x5} karena d ({x4}, {x5}) = 3.5, yang merupakan jarak minimum antara semua pasangan cluster dalam 1 (sesuai dengan Pers. (7.9), d ({x1, x2}, { x3}) = max (d ({x1}, { x3}), d ({x2}, { x3})) = 4). Jadi, 2 = {{x1, x2}, {x3}, { x4,x5}, {x6}} (Level 2). Cluster terdekat 2 adalah {x4, x5} dan {x6} karena d ({x4, x5}, {x6}) = max (d ({x4}, {x6}), d ({x5}, {x6})) = 3,7 adalah jarak minimum antara setiap pasang kelompok dalam 2. Jadi, 3 ={{x1, x2}, {x3}, {,x4,x5, x6}} (level 3). Demikian pula, cluster terdekat 3 adalah {x1, x2} dan { x3} karena d ({x1, x2}, {} x3) = max (d ({x1}, { x3}), d ({x2}, { x3}) = 4 adalah jarak minimum antara sepasang kelompok dalam 3. Jadi, 4 = {{x1, x2, x3}, {x4, x5, x6}} (level 4). Akhirnya, dua kelompok dalam 4 yang bergabung untuk membentuk pengelompokan akhir, 5= {{x1, x2, x3, x4, x5, x6}} (level 5). Perhatikan bahwa d ({x1, x2, x3}, {x4, x5, x6}) = max i = 1, 2, 3, j = 4, 5, 6 d (xi, xj) = 26. Dendrogram Sebuah isu yang sering timbul pada algoritma clustering hirarki yang memperhatikan visualisasi dari hierarki yang terbentuk. Satu alat yang sering digunakan disebut proximity dendogram/dendrogram kedekatan (lebih spesifik, dendogram ketaksamaan(kesamaan) ukuran jarak ketaksamaa(kesamaan) antar cluster digunakan). Ini memiliki struktur pohon seperti yang ditunjukkan pada Gambar 7.12, yang menunjukkan dendrogram ketaksamaan pada hirarki clustering setelah menerapkan algoritma jalur tunggal untuk himpunan data X11. 14
Pada level 0 hirarki, masing-masing vektor data membentuk cluster tunggal. Pada tingkat 1, {x1} dan {x2} digabungkan menjadi cluster tunggal, membentuk clustering 1 . ini digambarkan dengan bergabung mereka dengan sambungan yang ditunjukkan pada gambar, yang sesuai dengan ketaksamaan tingkat 1. Kita mengatakan bahwa clustering 1 dibentuk di ketaksamaan tingkat 1. Pada tingkat kedua dari hirarki, cluster {x1, x2 } dan { x3} digabungkan dan sambungan di ketaksamaan tingkat 3 dimasukkan. Jadi, clustering 2 terbentuk pada ketaksamaan tingkat 3. Melanjutkan dengan prinsip ini, kita dapat melihat bagaimana bagian yang tersisa dari dendrogram dibangun. 0 ,1 , 2, 3 , 4 , 5 dibuat pada ketaksamaan tingkat 0 1, 3, 3,5, 3,6, 20, masing-masing.
Gbr 7.12 Dendrogram Ketaksamaan yang dihasilkan oleh algoritma jalur tunggal bila diterapkan pada himpunan data X11dalam Contoh 7.7.1.
Gbr 7.13 Dendrogram Ketaksamaan diperoleh dengan algoritma jalur lengkap bila diterapkan pada himpunan data X11 pada Contoh 7.7.1.
15
Jelaslah, dendrogram kedekatan merupakan alat yang berguna dalam memvisualisasikan informasi mengenai hirarki clustering. Kegunaannya menjadi lebih jelas dalam kasus di mana jumlah titik data yang besar (Gambar 7.13 menunjukkan dendrogram ketaksamaan yang dibentuk oleh algoritma jalur lengkap ketika diterapkan pada himpunan data X11). Untuk menjalankan skema agglomerative umum (GAS), ketik Dimana
prox_mat adalah matrik ketaksamaan N × N untuk N vektor dari himpunan data X, (Prox_mat (i, j) adalah jarak antara xi dan xj vektor), code adalah bilangan bulat yang menunjukkan algoritma clustering yang digunakan (1 singkatan jalur tunggal; 2 singkatan untuk jalur lengkap), bel adalah matriks N × N yang elemen (i, j) berisi label cluster untuk vektor ke-j dalam clustering ke-i. (Baris pertama dari bel sesuai dengan pengelompokan N-cluster, baris kedua, pengelompokan (N -1)-cluster, dan baris N, untuk pengelompokan cluster tunggal), thres adalah vektor berdimensi N yang mengandung tingkat ketaksamaan di mana setiap pengelompokan baru terbentuk. Keterangan
Clustering dihasilkan oleh algoritma jalur tunggal dibentuk pada tingkat ketaksamaan yang lebih rendah, sementara yang dihasilkan oleh algoritma jalur lengkap terbentuk pada tingkat ketaksamaan yang lebih tinggi. Hal ini disebabkan fakta bahwa operator min dan max digunakan untuk menentukan ukuran jarak mereka. Semua algoritma yang lain berkompromi antara kasus-kasus ekstrim tersebut. Algoritma seperti unweighted pair group method average (UPGMA), unweighted pair group method centroid (UPGMC), Ward, atau varians minimum semua berasal dari Persamaan. (7.5) untuk pilihan yang berbeda dari parameter [ ,Theo 09 Bagian 13.2.2]. Suatu hal yang penting dengan algoritma hirarki adalah kemonotonan. Kita mengatakan bahwa suatu hirarki dari clustering yang dihasilkan oleh seperti algoritma menampilkan properti monotonisitas jika tingkat ketaksamaan dimana hirarki clustering ke-t, 1 , terbentuk lebih besar dari tingkat ketaksamaan dari semua clustering terbentu pada tingkat sebelumnya. Kemonotonan adalah properti dari algoritma clustering, bukan dari kumpulan data. Hal ini dapat ditunjukkan bahwa algoritma jalur tunggal dan jalur lengkap menampilkan properti monotonisitas, sementara algoritma agglomerative lain tidak (misalnya, UPGMC, dijelaskan pada [, Theo 09 Bagian 13.2.2]). Hubungan tunggal dan lengkap-link algoritma, serta sejumlah orang lain, mungkin berasal dari kerangka teori grafik [Theo 09, Bagian 13.2.5]. Dalam kasus di mana terdapat hubungan (yaitu, lebih dari sepasang cluster berbagi jarak minimum yang sama pada tingkat ke-t dari hirarki pengelompokan), satu pasang secara acak dipilih untuk digabung. Pilihan ini berpengaruh, secara umum, hirarki pengelompokan dibentuk oleh jalur lengkap dan semua algoritma pengelompokan lainnya yang berasal dari Persamaan(7.5). Kecuali algoritma jalur tunggal. 16
7.7.3 Pemilihan Clustering Terbaik Ketika sebuah hirarki clustering/pengelompokan tersedia, sebua isu penting adalah pilihan clustering/pengelompokan tertentu yang paling mewakili struktur clustering untuk himpunan data X. Beberapa metode telah diusulkan untuk masalah ini. Salah satu metode yang sederhana adalah untuk mencari hirarki untuk cluster yang memiliki masa hidup yang lama. Masa hidup suatu cluster didefinisikan sebagai perbedaan mutlak antara tingkat kedekatan di mana cluster terbentuk dan tingkat kedekatan di mana itu diserap ke dalam cluster yang lebih besar. Dalam dendrogram pada Gambar 7.12 ,misalnya, cluster {x1, x2, x3} dan {x4, x5, x6} memiliki masa hidup yang lama, yang menunjukkan bahwa clustering yang paling mewakili himpunan data yang sesuai adalah {{x1, x2, x3}, {x4, x5, x6}}. Pendapat serupa berlaku untuk yang dendrogram pada Gambar 7.13. Dua metode lain yang diusulkan dalam [Bobe 93] dan juga dibahas dalam [Theo 09]. Dalam pembahasan ini, kami mempertimbangkan versi lanjutan salah satu dari mereka. Menurut metode ini, dimana clustering yang paling representatif dari X dalam hirarki berisi cluster yang menunjukkan "ketaksamaan rendah" di antara anggotanya. "Derajat ketidaksamaan" dalam cluster C diukur dari segi kuantitas
dimana d (x, y) adalah ketaksamaan antara vektor-vektor x dan y. Selain itu, ambang batas ketaksamaan, θ, digunakan. Kriteria untuk pemilihan clustering dalam hirarki yang paling menggambarkan struktur clustering dari X dapat dinyatakan sebagai “Pemilihan clustering t jika terdapat sebuah cluster C dalan clustering t+1 dengan h(C) > .” Parameter θ dapat didefinisikan sebagai di mana μ dan σ adalah mean dan deviasi standar dari ketaksamaan-ketaksamaan antara titik-titik data X dan λ adalah parameter yang ditetapkan pengguna. Jelaslah bahwa pilihan nilai λ sangat penting. Untuk menghindari risiko ketergantungan pada nilai tunggal λ, kita dapat bekerja sebagai berikut. Jika λ memindai rentang nilai dan diperoleh, untuk setiap nilai tersebut, clustering t yang memenuhi kriteria sebelumnya. Kemudian, tidak termasuk kasus-kasus di mana? 0 dan N-1 telah dipilih, hitung fraksi dari berapa kali jumlah clustering masing-masing telah dipilih dan, akhirnya, pertimbangkan clustering terpilih yang paling besar frekuensinya sebagai yang paling mungkin untuk mewakili himpunan data dalam studi. Namun, perhatikan bahwa, sejalan dengan clustering terpilih berdasarkan frekuensi paling besar, clustering terpilih berdasarkan frekuensi lebih sedikit berikutnya mungkin sesuai data dengan baik (terutama jika mereka telah memilih angka frekuensi yang signiikan). Setelah semua, ini adalah manfaat utama clustering hirarki -itu dianjurkan lebih dari clustering yang sesuai dengan data dengan alasan yang cukup baik. Ini mungkin berguna dalam memberikan sebuah "gambar" yang lebih lengkap dari struktur clustering X. Untuk menerapkan teknik yang dijelaskan sebelumnya, ketik Dimana
prox_mat dan bel didefinisikan sebagai dalam fungsi agglom, 17
lambda adalah vektor dari nilai-nilai parameter λ, yang clustering (selain0 dan N) diperoleh, cut_point_tot adalah vektor yang berisi indeks dari clustering yang dipilih untuk nilai λ yang diberikan, hist_cut adalah vektor yang komponen ke-t berisi jumlahberapa kali clustering telah dipilih (termasuk clustering1-cluster dan cluster N).
Fungsi ini juga menghasilkan plot histogram yang sesuai. Contoh 7.7.2. Bangkitkan dan plot himpunan data X12, menggunakan langkah-langkah yang diikuti dalam Contoh 7.5.1. Di sini masing-masing dari empat cluster terdiri dari 10 titik. Lalu 1. Hitunglah matriks yang berisi (kuadrat Euclidean) jarak antara setiap pasangan vektor pada X12 dan vektor yang mengakumulasi elemen-elemen baris diagonal atas . 2. Terapkan algoritma jalur (ketaksamaan)yang sesuai.
tunggal dan jalur
lengkap
pada X12 dan gambarkan
dendrogram
3. Tentukan clustering yang terbaik sesuai dengan struktur clustering pada X12. Beri komentar pada hasil. Penyelesaian Untuk membangkitkan himpunan data X12, ketik
Plot X12 (lihat Gbr 7.14(a), ketik Kemudian diproses sebagai berikut Langkah 1. Untuk menghitung matrik jarak untuk vektor data pada X12, ketik
18
Gbr. 7.14. (a) himpunan data X12, dipertimbangkan dalam Contoh 7.7.2. (b)-(c). Dendogram ketaksamaan diperoleh dengan algoritma jalur tunggal dan jalur lengkap, masing-masing, ketika mereka diterapkan pada X12. Sumbu horizontal berisi label vektor data. Untuk menumpuk jarak terhitung pada sebuah vektor data, ketik
Langkah 2. Untuk menerapkan algoritma jalur tunggal pada X12 dan menggambar dendogram ketaksamaan yang sesuai (lihat Gbr. 7.14(b)), ketik
19
Fungsi linkage adalah fungsi MATLAB built-in, yang melakukan clustering/pengelompokan agglomerative dan mengembalikan hasilnya ke format yang berbeda (lebih kompak namun kurang dapat dipahami), dibandingkan dengan bentuk yang diadopsi dalam fungsi agglom. Selain itu, fungsi dendrogram juga MATLAB built-in, yang mengambil sebagai input, output dari linkage dan menggambar dendrogram yang sesuai.Kesamaan bekerja dalam jalur lengkap, di mana sekarang argumen kedua dalam fungsi agglom akan sama dengan 2 dan argumen kedua dari fungsi linkage sama dengan ‘complete’. (Lihat juga Gambar 7.14 (c)) Langkah 3. Untuk menentukan clustering hirarki yang dihasilkan oleh algoritma jalur tunggal yang paling sesuai dengan struktur X12, ketik
Fungsi ini membentuk histogram dengan frekuensi pemilihan setiap cluster (lihat Gambar 7.15 (a)). Perhatikan bahwa batang pertama sesuai dengan kasus clustering/pengelompokan 2-cluster. Histogram yang sesuai untuk algoritma jalur lengkap ditunjukkan pada Gambar 7.15 (b). Dari Gambar 7.14 (b) dan (c), maka bahwa clusterings dalam hirarki yang dihasilkan oleh algoritma jalur lengkap yang terbentuk pada tingkat ketaksamaan lebih tinggi dibandingkan dengan clustering yang dihasilkan oleh algoritma jalur tunggal. Meskipun begitu dan perbedaan kecil lainnya, kedua dendrogram menunjukkan bahwa clustering 2-cluster dan 4-klaster yang paling sesuai dengan struktur pengelompokan pada X12. Hal ini dibuktikan dengan histogram pada Gambar 7.15 dan ini sejalan dengan intuisi kita (Lihat Gambar 7.14 (a)).
Gbr 7.15. Pemilihan clustering yang struktur clustering-nya paling cocok dengan X12. (a) - (b) histogram menunjukkan pemilihan frekuensi clustering pada hirarki yang dihasilkan algoritma jalur tunggal dan jalur lengkap, masing-masing, ketika mereka diterapkan pada himpunan data X12 (yang clustering 0 dan N-1 telah dikecualikan). Latihan 7.7.1 Bangkitkan dan plot himpunan data X13, menggunakan cara yang diikuti pada Contoh 7.6.1, di sini dengan empat cluster terdiri dari 30,, 20 10, dan 51 titik, masing-masing. Ulangi Contoh 7.7.2 untuk X13. Gambarkan kesimpulan. Perhatikan bahwa algoritma jalur tunggal dan lengkap pada prinsipnya dapat mendeteksi cluster berbagai bentuk asalkan terpisahkan dengan baik. 20
DAFTAR PUSTAKA [1] Theodoridies, Sergios., and Koutroumbas, Kostantinos., 2010, An Introduction to Pattern Recognition: A MATLAB Approach, Academic Press, Burlington USA.
21
22
