CLUSTERING

DEFINISI

Clustering :

Proses mengelompokkan suatu set objek ke dalam

kelompok-kelompok objek yang sejenis

Bentuk yang paling umum digunakan adalah

unsupervised learning

# Unsupervised learning belajar dari data

# Supervised learning contoh yang telah diklasifikasikan

Merupakan topik yang penting dan banyak diaplikasikan

pada IR

CLUSTERING

Algoritma clustering akan membagi suatu objek

menjadi subset objek, dimana tiap subset berisi

objek yang dianggap sejenis

CLUSTERING

Clustering dapat digunakan untuk mengorganisasikan

dokumen yang diperoleh

ALASAN PERLUNYA DOKUMEN

DIKELOMPOKKAN

Analisa keseluruhan Korpus

User interface yang lebih bagus (yang dicluster koleksinya)

Untuk visualisasi koleksi dokumen dan topiknya

Untuk memperbaiki recall pada hasil pelacakan

Hasil pelacakan yang lebih baik (yang dicluster hasil perolehan dokumen)

Untuk navigasi yang lebih baik dari hasil pelacakan

User recall akan lebih tinggi

ANALISA KESELURUHAN KORPUS

Koleksi dipecah menjadi beberapa kelompok

berdasarkan isi dokumen yang sejenis

User dapat melakukan browsing pada topik-topik yang

ada pada koleksi

Perlu diberi label tertentu dari setiap node topik yang

ada

Contoh : Di yahoo hirarki secara manual

Sering tidak ada informasi dari koleksi yang baru

ANALISA KESELURUHAN KORPUS

Contoh hirarki pada Yahoo

VISUALISASI DOKUMEN DAN TOPIKNYA

MEMPERBAIKI RECALL DARI PELACAKAN

Hipotesa cluster :

Dokumen dengan teks yang mirip adalah berkaitan

Untuk memperbaiki recall :

Kelompokkan dokumen pada korpus sebelumnya

Jika suatu query cocok dengan dok D maka berikan

juga dokumen yang sekelompok dengan dok D

Harapannya : jika ada query “pakaian” maka akan

diberikan juga dokumen tentang “baju”

Karena clustering akan menggelompokkan dokumen

tentang baju dan pakaian dalam satu kelompok

NAVIGASI YANG LEBIH BAIK DARI HASIL

PELACAKAN

Untuk mengelompokkan hasil pelacakan sesuai

dengan temanya

Clusty.com

NAVIGASI YANG LEBIH BAIK DARI HASIL

PELACAKAN

Lebih visual

Kartoo.com

CONTOH CLUSTERING

CONTOH CLUSTERING

ISU PADA CLUSTERING

Bagaimana representasi pada clustering?

Representasi dokumen

Perlu ukuran kemiripan / jarak

Berapa jumlah cluster

Jumlah tetap yang sudah adilakuakn pada korpus?

Sepenuhnya tergantung pada data?

Hindari cluster terlalu besar atau kecil

Jika terlalu besar tambahan satu klik dari user jadi sia-sia

APA YANG MEMBUAT DOKUMEN “ BERKAITAN”

Ideal : semantic similarity

Praktis : statistical similarity

Misal menggunakan cosine similarity

Dokumen sebagai vektor

Kebanyakan algoritma lebih mudah jika berpikir ada

jarak diantara dokumen (dari pada similarity)

JENIS-JENIS ALGORITMA CLUSTERING

Berdasarkan hubungan antara :

Cluster kelompok yang dihasilkan

Objek sesuatu yang ditempatkan pada kelompok

Properties cara kita merepresentasikan sesuatu

Properti :

feature yang direpresentasikan dari sebuah dokumen

Isi properti kata (kata/frase)

Dapat memanfaatkan anotasi (nama, lokasi, organisasi,

kejadian, hubungan)

Dapat menggunakan metadata (penulis, tanggal, genre,

kata kunci )

Hubungan antara properties dengan cluster

Monothetic : semua item pada cluster punya properties yang sama (mis : burung)

Polythetic : semua item pada cluster punya sebagian besar properties (dokumen punya banyak kata)

Hubungan antara objek dengan cluster

Eksklusif : setiap objek menjadi anggota satu cluster

Overlapping : setiap objek dapat menjadi anggota dari beberapa cluster

Hubungan antara cluster dan cluster

Ordered : ada cluster yang menjadi bagian dari cluster lain (hirarki)

Unordered : setiap cluster dibuat sama

JENIS-JENIS ALGORITMA CLUSTERING

JENIS-JENIS ALGORITMA CLUSTERING

HIERARCHICAL VS FLAT

Hierarchical

Digunakan untuk analisa detail

Memberikan lebih banyak informasi daripada flat

Tidak ada algoritma yang paling baik

Kurang efisien

Ada dua jenis : Bottom-up (agglomerative) dan Top-down (divisive)

Flat

Biasanya dimulai dengan suatu partisi acak (partial)

Digunakan untuk efisiensi

K-means sangat sederhana

K-means tidak masuk akal untuk beberapa jenis data (misal : nama)

HIERARCHICAL CLUSTERING :

TOP-DOWN VS BOTTOM-UP

BOTTOM-UP CLUSTERING : MENENTUKAN

SIMILARITY ANTAR CLUSTER

MENGUKUR SIMILARITY

Digunakan untuk membandingkan dua objek

Properti yang diinginkan sesuai dengan fungsi

similarity, S(X,Y)

S(X,Y) bertambah jika X dan Y mempunyai feature yang

sama

Biasanya S(X,Y) = 0 jika X dan Y tidak mempunyai

feature yang sama

Ada berbagai fungsi similarity

Secara umum tidak ada fungsi yang paling baik

CONTOH PENGUKURAN SIMILARITY

SIMILARITY DARI PASANGAN DOKUMEN

(COSINE NORMALIZATION)

+

DOKUMEN / MATRIKS DOKUMEN

SINGLE LINK

COMPLETE LINK

AVERAGE LINK

CONTOH HIERARCHICAL CLUSTERING

CONTOH : SINGLE LINK

CONTOH : SINGLE LINK (LANJUTAN)

CONTOH (LANJUTAN)

CONTOH : SINGLE –LINK (LANJUTAN)

CONTOH : SINGLE LINK

CONTOH : SINGLE LINK (LANJUTAN)

DENDOGRAM : HIERACHICAL CLUSTERING

APA YANG MEMBUAT CLUSTERING BAIK?

FLAT CLUSTERING : K - MEANS

FLAT CLUSTERING : K-MEANS

K-MEANS : PARTISINYA CEPAT

K-MEANS

cx

xcuc

||

1)(

CONTOH K-MEANS (K=2)

KONDISI PEMBERHENTIAN

Diantaranya :

Posisi centroid tidak berubah

Partisi dokumen tidak berubah

PEMILIHAN SEED

DESKRIPSI CLUSTER

MENGEVALUASI CLUSTER

MENGEVALUASI CLUSTER

BERAPA JUMLAH CLUSTER?

PEMILIHAN FEATURE

BIG ISSUE : LABELING

BAGAIMANA MEMBERI LABEL PADA CLUSTER?

PELABELAN