TUGAS DATA MINING

RANGKUMAN BAB VII

Oleh: Ni Putu Tessa Intaran 0908605028

PROGRAM STUDI TEKNIK INFORMATIKA JURUSAN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS UDAYANA 2012

Cluster Analisis: Konsep Dasar dan AlgoritmaPengertian Cluster Analisis Menemukan kelompok objek sehingga objek dalam sebuah kelompok akan mirip (atau terkait) satu sama lain dan berbeda (atau tidak berhubungan dengan) objek dalam kelompok lain. Untuk ilustrasinya dapat dilihat pada Gambar 1.1 (lihat pada lampiran). Aplikasi dari Cluster Analisis Understanding (Memahami) Grup yang terkait dengan dokumen untuk browsing, gen kelompok dan protein yang memiliki 2 fungsi serupa, atau saham kelompok dengan fluktuasi harga yang sama. Seperti pada Gambar 1.2 (lihat pada lampiran). Summarization Mengurangi ukuran set data yang besar. Dapat dilihat pada gambar 1.3 (lihat pada lampiran). Yang tidak termasuk Cluster Analisis Supervised classification. Yang dimaksud supervised classification adalah klasifikasi yang memiliki informasi kelas label. Segmentasi sederhana Contohnya seperti membagi siswa menjadi kelompok pendaftaran yang berbeda abjad, sesuai dengan nama belakang. Hasil dari query Pengelompokan yang merupakan hasil dari spesifikasi eksternal Grafik partisi Beberapa relevansi timbal balik dan bersinergi, tetapi daerah yang dimasukkan tidak sama Suatu cluster bisa menjadi ambigu. Contohnya dapat dilihat pada Gambar 1.4 (lihat pada lampiran).

Jenis Clustering Clustering merupakan kumpulan dari cluster. Yang terpenting adalah perbedaan antara hirarki dan partisional set dari cluster. Clustering dapat dibagi menjadi dua yaitu : Partitional clustering Pembagian data objek kedalam non-overlapping subset (himpunan bagian) atau cluster sedemikian rupa sehingga data objek tepat menjadi satu subset. Contoh dari partitionsal clustering dapat dilihat pada Gambar 1.5 (lihat pada lampiran) Hierarchical clustering Satu set cluster bertingkat diatur sebagai sebuah pohon hirarkis. Contoh hierarchical clustering dapat dilihat pada Gambar 1.6 (lihat pada lampiran) Perbedaan lain antara set dari cluster Eksklusif versus non-eksklusif Dalam non-eksklusif clusterings, poin mungkin milik beberapa kelompok. Dapat mewakili beberapa kelas atau 'batas' poin. Fuzzy versus non-fuzzy Dalam fuzzy clustering, titik/point termasuk ke dalam setiap cluster dengan berat antara 0 dan 1 . Bobot yang dijumlahkan harus bernilai 1. Pengelompokan Probabilistik memiliki karakteristik serupa. Parsial versus Lengkap Dlam beberapa kasus, hanya mencluster beberapa data saja. Heterogen versus homogen Cluster dari perbedaan ukuran luas, bentuk dan kepadatan. Jenis-jenis Cluster 1. Well-separated clusters Sekumpulan titik atau point dimana setiap poin di dalam cluster mirip atau hampir sama dengan setiap poin lain di dalam cluster dari pada poin yang terletak di luar cluster. Untuk contoh dapat dilihat pada Gambar 1.7 (lihat pada lampiran). 2. Center-based clusters Sebuah cluster adalah serangkaian objek sehingga objek dalam cluster lebih dekat (lebih mirip) ke "pusat" dari cluster, daripada ke pusat dari setiap cluster lain. Contoh dapat dilihat pada Gambar 1.8 (lihat pada lampiran). Pusat cluster sering merupakan centroid,

rata-rata semua titik dalam cluster, atau medoid, yang paling "mewakili" titik cluster. 3. Contiguous clusters Sebuah cluster adalah kumpulan poin sehingga titik dalam cluster lebih dekat (atau lebih serupa) untuk satu atau lebih titik dalam cluster daripada setiap titik tidak di cluster. Contoh dapat dilihat pada Gambar 1.9 (lihat pada lampiran) 4. Density-based clusters Sebuah cluster adalah wilayah padat poin, yang dipisahkan oleh kepadatan daerah yang rendah, dari daerah lain di kepadatan tinggi. Digunakan ketika kelompok yang tidak teratur atau saling terkait, dan ketika noise dan outlier hadir. Contoh dapat dilihat pada Gambar 1.10 (lihat pada lampiran) 5. Property or Conceptual Menemukan cluster yang membagikan beberapa properti umum atau mewakili konsep tertentu. Contoh dapat dilihat pada Gambar 1.11 (lihat pada lampiran) 6. Described by an Objective Function Menemukan cluster yang meminimalkan atau memaksimalkan fungsi objektif. Menghitung semua kemungkinan cara membagi poin ke cluster dan mengevaluasi goodness dari setiap rangkaian potensi cluster dengan menggunakan fungsi tujuan tertentu(NP Hard). Dapat memiliki tujuan global atau lokal. Algoritma clustering hirarkis biasanya memiliki tujuan lokal sedangkan Algoritma Partitional biasanya memiliki tujuan global. Sebuah variasi dari pendekatan fungsi tujuan global adalah agar sesuai dengan data untuk model parameter. Parameter untuk model ditentukan dari data. Model Campuran berasumsi bahwa data adalah 'campuran' dari banyak distribusi statistik. Peta masalah clustering untuk domain yang berbeda dan memecahkan masalah yang berkaitan dengan domain tersebut. Matriks kedekatan mendefinisikan graf berbobot, di mana node titik-titik yang berkerumun, dan ujung-ujungnya tertimbang mewakili proximities antara poin. Clustering ekuivalen untuk memecahkan grafik menjadi komponen yang terhubung, satu untuk setiap cluster. Meminimalkan bobot sisi diantara cluster dan memaksimalkan bobot sisi dalam cluster.

Karakteristik Penting dari Input Data Jenis ukuran kedekatan atau kepadatan Ini adalah ukuran yang diturunkan, namun penting untuk clustering atau pengelompokan. Sparseness Menentukan jenis kesamaan dan menambah efisiensi. Jenis Atribut Menentukan jenis kesamaan. Jenis Data Menentukan jenis kesamaan, karakteristik lain misalnya autokorelasi. Dimensionality Noise dan Outlier Jenis distribusi

Algoritma Clustering 1. K-means Clustering Pendekatan partitional clustering. Setiap cluster dikaitkan dengan centroid (titik pusat). Setiap titik ditugaskan untuk cluster dengan centroid terdekat. Jumlah cluster K harus ditentukan. Algoritma dasarnya sangat sederhana. Algoritma dari K-means clustering :

Centroid awal sering dipilih secara acak. Cluster diproduksi bervariasi dari yang dijalankan yang lain. Pusat massa adalah (biasanya) mean dari titik-titik di cluster. "Closeness" diukur dengan jarak Euclidean, kosinus kesamaan, korelasi, dll. K-means akan menyatu untuk langkah-langkah kesamaan umum yang disebutkan di atas. Sebagian besar konvergensin terjadi dalam beberapa iterasi pertama. Seringkali kondisi berhenti diubah sampai poin relatif sedikit mengubah cluster. Complexity : O( n * K * I * d )

Dimana : n = number of points K = number of clusters I = number of iterations d = number of attributes Untuk contoh dapat dilihat pada Gambar 1.12, Gambar 1.13, Gambar 1.14 (lihat pada lampiran). Mengevaluasi K-means cluster Ukuran yang paling umum adalah Sum of Squared Error (SSE). Untuk setiap titik, error adalah jarak ke cluster terdekat. Untuk mendapatkan SSE, caranya dengan mengkuadratkan error dengan jumlahnya.

x adalah titik data di cluster Ci dan mi adalah titik representatif untuk klaster Ci . Dapat menunjukkan bahwa mi sesuai dengan pusat (mean) dari cluster. Jika diberikan dua kelompok, kita dapat memilih salah satu dengan kesalahan terkecil. Salah satu cara mudah untuk mengurangi SSE adalah untuk meningkatkan K (Jumlah cluster). Sebuah pengelompokan yang baik dengan K kecil dapat memiliki SSE rendah dari clustering yang buruk dengan K yang lebih tinggi. Untuk contoh dapat dilihat pada Gambar 1.15 dan 1.16 (lihat pada lampiran). Permasalahan pada pemilihan poin awal Jika terdapat K'real' cluster maka peluang memilih salah satu pusat massa dari setiap cluster kecil. Peluang relatif kecil jika K adalah besar. Jika cluster ukurannya sama, n, maka :

Misalnya,

jika

K

=

10,

maka

probabilitas tidak

=

10!/1010

=

0,00036

Kadang-kadang centroid awal akan menyesuaikan diri dengan cara yang 'real', dan kadang-kadang mereka menyesuaikannya.

Pertimbangkan contoh dari lima pasang cluster dapat dilihat pada Gambar 1.17 (lihat pada lampiran). Solusi untuk permasalahan centroid awal Multiple Runs. Membantu tapi terkadang tidak ada di pihak kita. Sampel dan menggunakan pengelompokan hirarki untuk menentukan centroid awal. Pilih lebih dari centroid k awal dan kemudian pilih di antara centroid awal. Pilih yang paling banyak dipisahkan. Postprocessing. Membagi dua K-means. Tidak rentan terhadap masalah inisialisasi. Penanganan Cluster yang kosong Dasar dari algortima K-means adalah dapat menghasilkan cluster kosong. Beberapa strategi yang dapat digunakan : Pilih titik yang paling memberikan kontribusi untuk SSE. Pilih titik dari cluster dengan SSE yang tertinggi. Jika ada cluster kosong maka ulangi beberapa kali langkah-langkah di atas. Updating Centers Incrementally Dalam algoritma dasar K-means, centroid diperbarui setelah semua titik ditugaskan ke sebuah pusat massa. Alternatif adalah untuk memperbarui centroid setelah setiap tugas dibawah ini diselesaikan (pendekatan inkremental): Setiap tugas mengupdate nol atau dua centroid Lebih mahal Memperkenalkan ketergantungan order. Tidak pernah mendapatkan sebuah cluster kosong. Dapat menggunakan "weight" untuk mengubah dampak. Pre-processing dan Post-processing Pre-processing Menormalkan data

Menghilangkan outlayer Post-processing Menghilangkan kelompok kecil yang mungkin merupakan outlier Split 'loose' cluster, yaitu cluster dengan SSE relatif tinggi Merge cluster yang 'dekat' dan yang memiliki SSE yang relatif rendah Dapat menggunakan langkah-langkah selama proses pengelompokan. ISODATA Membagi dua K-means Varian K-means yang dapat menghasilkan sebuah partisi atau clustering hirarkis. Algoritmanya adalah :

Untuk contoh dapat dilihat pada gambar 1.18 (lihat pada lampiran). Keterbatasan K-means K-mean memiliki masalah kerika cluster memiliki perbedaan pada ukuran, densitas, dan bentuk yang non-globural. K-means juga memiliki masalah ketika terdapat data yang outlayer. Untuk contohnya dapat dilihat pada Gambar 1.19 (lihat pada lampiran). Mengatasi keterbatasan K-means Salah satu solusinya adalah menggunakan banyak cluster. Cari bagian dari cluster, tetapi perlu disatukan. Lihat pada Gambar 1.20, untuk contoh dapat dilihal pada Gambar 1.21(lihat pada lampiran). 2. Hierarchical clustering Menghasilkan satu set cluster bertingkat diorganisasikan sebagai sebuah pohon hirarkis. Dapat divisualisasikan sebagai sebuah dendrogram. Sebuah pohon seperti diagram yang mencatat urutan gabungan atau perpecahan. Lihat pada Gambar 1.22.

Kekuatan dari Hierarchical clustering Tidak harus mengansumsikan sejumlah cluster tertentu. Setiap nomor yang dikehendaki dari cluster dapat diperoleh dengan 'memotong' Dendogram pada tingkat yang tepat. Berhubungan dengan taksonomi, Contoh dalam ilmu biologi (misalnya, hewan kerajaan, rekonstruksi filogeni, dll) Hierarchical Dua jenis utama dari clustering hirarkis Agglomerative: Mulailah dengan poin-poin sebagai kelompok individu. Pada setiap langkah, menggabungkan pasangan terdekat cluster sampai hanya satu cluster (atau k cluster) yang tersisa. Divisive: Mulailah dengan satu cluster tetapi mencakup semua. Pada setiap langkah, membagi sebuah cluster sampai setiap cluster berisi titik (atau ada k cluster) Algoritma hirarkis tradisional menggunakan matriks kesamaan atau jarak. Melakukan merger atau membagi satu cluster pada suatu waktu. Agglomerative Clustering Algoritma. Merupakan teknik clustering hierarki yang populer. Algoritma dasarnya sangat mudah yaitu : 1. 2. 3. 4. 5. 6. Menghitung Matrik kedekatan. Biarkan setiap titik data menjadi sebuah cluster Ulangi Menggabungkan dua cluster terdekat Update matrik kedekatan Sampai hanya satu cluster tetap Clustering

Operasi kunci adalah perhitungan kedekatan dua kelompok. Pendekatan yang berbeda untuk mendefinisikan jarak antara cluster membedakan algoritma yang berbeda. Kondisi awal Mulailah dengan cluster poin individu dan matriks kedekatan. Lihat pada Gambar 1.23.

Kondisi Menengah Setelah beberapa langkah penggabungan, maka terbentuklah beberapa cluster. Lihat pada Gambar 1.24. Disini digabungkan dua cluster terdekat (C2 dan C5) dan memperbarui matriks kedekatan. Lihat Gambar 1.25. Kondisi Setelah Penggabungan Cara menentukan kesamaan antar cluster pada Gambar 1.26 adalah : 1. Menentukan MIN . Lihat Gambar 1.27 2. Menentukan MAX. Lihat Gambar 1.28 3. Group average. Lihat Gambar 1.29 4. Jarak antara centroid. Lihat Gambar 1.30 5. Metode lain yang disebabkan oleh fungsi tujuan. Cara Ward yang menggunakan kuadrat error. Kesamaan cluster : MIN atau single link Kesamaan dari dua kelompok didasarkan pada dua titik yang paling mirip (paling dekat) dalam cluster yang berbeda. Ditentukan oleh satu pasangan titik, yakni dengan satu link dalam grafik kedekatan. Lihat pada Gambar 1.31. Nested cluster dan dendogramnya dapat dilihat pada Gambar 1.32. Kekuatan dari MIN adalah dapat menangani bentuk yang non-elliptical. Lihat pada Gambar 1.33. Keterbatasannya adalah sensitif terhadap noise dan outlier. Lihat pada Gambar 1.34. Kesamaan cluster : Max atau complete linkage Kesamaan dari dua kelompok didasarkan pada dua poin setidaknya sama (paling jauh) dalam cluster yang berbeda. Ditentukan oleh semua pasangan poin dalam dua kelompok. Lihat pada Gambar 1.32. Nested cluster dan dendogramnnya dapat dilihat pada Gambar 1.35. Kekuatan dari MAX yaitu kurang rentan terhadap noise dan outlayer Lihat pada Gambar 1.36. Keterbatasannya adalah cenderung memecah kelompok ke kelompok yang besar dan condong ke arah globular cluster. Lihat pada Gambar 1.37. Kesamaan cluster : Group Average Kedekatan dua cluster adalah rata-rata berpasangan kedekatan antara poin dalam dua kelompok.

Perlu

menggunakan

konektivitas

rata-rata

untuk skalabilitas

karena jumlah

kedekatan nikmat kelompok besar. Lihat pada Gambar 1.35. Nested cluster dan dendogramnnya dapat dilihat pada Gambar 1.38. Adanya kompromi antara Single link dan complete link. Kelebihannya kurang rentan terhadap noise dan outlayer. Kekurangannya Bias terhadap globular cluster. Kesamaan Cluster : Metode Ward Kesamaan dari dua kelompok didasarkan pada peningkatan kesalahan kuadrat ketika dua kelompok digabung. Serupa dengan group average jika jarak antara titik adalah jarak kuadrat. Kurang rentan terhadap noise dan outlier. Bias terhadap globular cluster. Analog hirarkis K-means - Dapat digunakan untuk menginisialisasi K-means. Hierarchical Clustering: Masalah dan Keterbatasan Setelah keputusan dibuat untuk menggabungkan dua kelompok, tidak dapat dibatalkan. Tidak ada fungsi tujuan secara langsung diminimalkan. Skema yang berbeda memiliki masalah dengan satu atau lebih hal berikut: Sensitivitas terhadap noise dan outlier Kesulitan menangani cluster berukuran berbeda dan bentuk cembung Melanggar cluster yang besar. MST: Memecah Hierarchical Clustering Membangun MST (Minimum Spanning Tree). Mulailah dengan sebuah pohon yang terdiri dari titik apapun. Dalam langkah-langkah yang berurutan, cari pasangan terdekat poin (p, q) sedemikian rupa sehingga satu titik (p) adalah di pohon saat ini tetapi yang lain (q) tidak. Tambahkan q untuk pohon dan menempatkan keunggulan antara p dan q. Lihat pada Gambar 1.39. Gunakan MST untuk membangun hirarki cluster. Algoritmanya adalah :

DBSCAN DBSCAN adalah algoritma berbasis kepadatan. Kepadatan = jumlah titik dalam radius tertentu (Eps). Titik A adalah titik inti jika memiliki lebih dari jumlah tertentu poin (MinPts) dalam

Eps. Ini adalah poin yang berada di bagian dalam sebuah cluster. Sebuah titik perbatasan memiliki kurang dari MinPts dalam Eps, tetapi di sekitar titik inti. Sebuah titik kebisingan adalah setiap titik yang bukan titik inti atau titik perbatasan. Algoritma Hilangkan poin kebisingan. Lakukan pengelompokan pada poin tersisa. DBSCAN

DBSCAN: Menentukan EPS dan MinPts Ide dasarnya adalah poin dalam cluster, kth nearest neighbor (tetangga terdekat) terdapat di sekitar jarak yang sama. Poin Kebisingan memiliki kth nearest neighbor pada jarak yang jauh. Jadi, alur diurutkan berdasarkan jarak setiap titik ke tetangga kth terdekatnya. Cluster Validitas Untuk pengklasifikasian yang lebih terbimbing, terdapat berbagai ukuran untuk menentukan kwalitas suatu model yaitu Keakuratan, presisi, dan recall. Hal tersebut dilakukan untuk menghindari penemuan pola pada kebisingan (noise), untuk membandingkan algoritma clustering, untuk membandingkan dua set cluster, untuk membandingkan dua cluster. Berbagai Aspek dalam Validasi Cluster 1. Menentukan clustering tendency ( kecenderungan pengelompokkan) sekumpulan data, contohnya membedakan apakah struktur yang non-acak benar-benar terdapat dalam data atau tidak. 2. Membandingkan hasil dari analisa cluster untuk mengetahuai hasilnya secara eksternal, misalnya untuk secara eksternal diberikan class label . 3. Mengevaluasi seberapa baik hasil dari analisis cluster mengacu pada informasi eksternal. 4. Membandingkan hasil dari dua set cluster analisis yang berbeda untuk menentukan yang terbaik. cocok dengan data tanpa

5. Menentukan jumlah yang benar pada cluster.

Pengukuran Validitas Cluster Ukuran-ukuran numerik yang diterapkan untuk menilai berbagai aspek validitas cluster, digolongkan dalam tiga jenis berikut: 1. Eksternal Indeks: Digunakan untuk mengukur sejauh mana label klaster sesuai label kelas eksternal yang disediakan. 2. Indeks internal: Digunakan untuk mengukur kebaikan struktur pengelompokan tanpa sehubungan dengan informasi eksternal. 3. Indeks Relatif: Digunakan untuk membandingkan dua clusterings berbeda atau cluster. Mengukur Validitas Cluster Via Korelasi Terdapat dua matriks yaitu : Proximity matrix Incidence matrix : Satu baris dan satu kolom untuk setiap titik data, entri adalah 1 jika pasangan berhubungan titik termasuk dalam cluster yang sama, entri adalah 0 jika pasangan terkait poin milik cluster yang berbeda. Hitung korelasi antara dua matriks. Karena matriks adalah simetris, hanya korelasi antara n (n-1) / 2 entri perlu dihitung. Korelasi yang tinggi menunjukkan bahwa poin yang termasuk dalam cluster yang sama dekat satu sama lain. Bukan ukuran yang baik untuk beberapa kepadatan atau kelompok berbasis kedekatan. Langkah-langkah internal: Kohesi dan Pemisahan Cluster Cohesion : Mengukur seberapa dekat objek yang terkait di dalam cluster. Contoh : SSE Cluster Separation : mengukur seberapa perbedaan atau pemisahan sebuah cluster dari cluster lain. Contohnya : Squared error Cohesion diukur dengan jumlah cluster yang terdapat dalam kotak (SSE) Langkah-langkah internal: Kohesi dan Pemisahan Contoh : SSE

Langkah-langkah internal: Kohesi dan Pemisahan Sebuah grafik kedekatan berbasis pendekatan juga dapat digunakan untuk kohesi dan pemisahan. Kohesi Cluster adalah jumlah dimana berat semua link dalam sebuah cluster. Pemisahan dan node cluster di luar adalah cluster. jumlah Lihat dari pada bobot Gambar antara 1.40 node pada di cluster lampiran). (lihat

Langkah internal : Silhouette Coefficient Silhouette Coefficient menggabungkkan ide dari kedua kohesi dan pemisahaan, tetapi hanya untuk poin yang individu, sama seperti cluster dan clustering. Untuk poin individu i : Hitung nilai a = jarak rata- rata dari i ke titik-titik dalam cluster. Hitung nilai b = min (jarak rata-rata dari i ke titik di cluster lain) Silhouette coefficient untuk titik ini adalah : S = 1-a/b jika a