1

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

2

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).

3

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 nilai-

nilai 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,

4

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 = 2,5. Untuk setiap kasus, plot hasil clustering dan buat

kesimpulan.

Petunjuk

Untuk membangkitkan inisialisasi clustering acak ketik

Untuk membangkitkan inisialisasi clustering menggunakan algoritma BSAS, ketik

5

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 dari a, tepat untuk mengungkap struktur

pengelompokan/clustering yang benar dari X3.

Latihan 7.6.5

Ulangi Latihan 7.6.4 untuk himpunan data X5 yang dihasilkan dalam Contoh 7.5.3.

Petunjuk

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.5

2,2

2,. . , 8

2..

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).

6

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

7

Dan, untuk membangkitkan kelompok ketiga, ketik

Langkah 2. Untuk nilai-nilai a dalam rentang [42, 6

2], 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.

8

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.

9

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.

10

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

11

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 (<k) cluster, jika masing-masing cluster dalam adalah bagian dari

cluster di ’. Sebagai contoh, clustering 1 = {{x1, x2}, { x3}, {x4, x5}} adalahbersarang di clustering

2 = {{x1, x2, x3}, {x4, x5}}?, tapi 1 tidak bersarang dalam 3 = {{x1, x3}, {x2}, {x4, x5}} atau

dalam 4 = {{x1, x3, x4}, {x2, x5}}.

12

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

13

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.

14

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.

15

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.

16

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.

17

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,

18

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 tunggal dan jalur lengkap pada X12 dan gambarkan dendrogram

(ketaksamaan)yang sesuai.

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

19

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

20

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.

21

DAFTAR PUSTAKA

[1] Theodoridies, Sergios., and Koutroumbas, Kostantinos., 2010, An Introduction to Pattern Recognition:

A MATLAB Approach, Academic Press, Burlington USA.

22