Website Mata Kuliah Pengenalan Pola
Dosen: Dr. Agus Zainal Arifin
Email: agus.za (at) its-sby . edu
Kelas: A dan X
Kode: CI1423
Jurusan: Teknik Informatika, FTIF, ITS

CLUSTERING ALGORITHMS VIA FUNCTION OPTIMIZATION

• Clustering disini diasumsikan sebagai? gambaran sebuah parameter model yang spesifik, dimana parameternya? tidak diketauhi.(semua parameter dimasukkan dalam? sebuah vector, yang dilambangkan dengan θ ).
• Contoh :
  • Compact cluster.
    Masing-masing cluster Ci ditampilkan dalam sebuah poin m, pada dimensi l. Dimana θ=[m1 T, m2 T, …, mm T ]T.
  • Ring-Shaped ClusterDimana masing-masing cluster Ci dimodelkan dengan hipersphere D(ci,ri), dimana ci dan ri adalah pusat dan jari-jarinya. Dimana nilai? θ=[c1T, r1, c2T, r2, …, cmT, rm]T.
  • Nilai dari J(θ) ditetapkan sebagai fungsi dari data vector di X dan θ. Pengoptimalan nilai J(θ) yang akan berpengaruh terhadap hasil θ, pada θ yang bernilai optimal, pengclusterannya berdasarkan X.
• Mixture Decomposition
  • Alasan utama menggunakan algoritma ini adalah kebiasaan kita terhadap teori bayes, disini kita ansumsikan bahwa ada m cluster, Cj, j = 1.....m. dengan nilai m sudah ditetapkan atau diketaihi. Masing-masing vector xi, I = 1,…., N, termasuk dalam cluster Cj dengan nilai kemungkinan P(Cj|Xi). sebuah vector xi dimasukkan dalam cluster Cj jika? P(Cj| xi)>P(Ck| xi),?? k=1,…,m, k≠j.
  • Perbedaan antara pengelompokan pada chapter 2 adalah:
    • tidak tersedia data training yang diketauhi pelabelan clustering-nya.
    • Kemungkinan awalnnya P(Ci) = Pj juga tidak diketauhi.
• FUZZY CLUSTERING
  • Kegiatan yang fital dalam pengenalan pola adalah kegiatan klasifikasi dari ruang feature yang diperoleh dari kegiatan seleksi dan ekstrak feature. Metode yang lebih baik dari metode clustering secara tegas adalah aplikasi teori fuzzy dalam proses kluster (fuzzy clustering). Proses? kluster secara fuzzy (fuzzy clustering) menunjukkan hasil yang lebih baik dan lebih alami dibandingkan dengan proses kluster dengan pendekatan tegas.
  • Fuzzy clustering berbasis fungsi tujuan persoalan mencari kluster terbaik akan identik dengan persoalan optimasi fungsi tujuan. Penggunaan algoritma genetika untuk fuzzy clustering dimungkinkan dapat meningkatkan unjuk kerja fuzzy clustering. Penerapan GFS pada fuzzy clustering terutama Fuzzy-C-Means Clustering (FCM) adalah untuk mengoptimasi parameter-parameter dalam FCM.
• Fuzzy-C-Means clustering
  • Algoritma pendekatan tegas dengan jumlah kluster k Clustering dan pusat kluster ditentukan dengan cara rata -rata ini sering disebut sebagai K-Means. Pada pendekatan fuzzy metode klustering berdasarkan kenyataan bahwa objek-objek tertentu mungkin secara tegas tidak dapat dikelompokkan pada kluster tertentu. Dengan pendekatan fuzzy setiap objek ke-k (k=1,2,..,n) dianggap menjadi anggota dari semua kluster ke-i (i=1,2,..,c) dengan fungsi keanggotaan antara 0 sampai 1.
  • Pada penyesuaian iterasi mula-mula dibangkitkan vektor pusat kluster secara acak dan kemudian iterasi dilakukan untuk mengupdate matrik U. Iterasi dilakukan sampai matrik U relatif tidak berubah. Berikut adalah nilai U dan V berturut-turut yang digunakan dalam iterasi
• Classification rate.
  • eberhasilan clustering terkadang? diukur juga melalui kemampuan clustering tersebut dalam klasifikasi objek. Hal ini dapat ditentukan apabila objek-objek yang diklasifikasi telah diketahui berasal dari suatu klas tertentu. Banyaknya objek yang dapat diklasifikasikan dengan tepat sesuai dengan klas dari mana objek tersebut berasal disebut sebagai classification rate
• Algoritma Fuzzy clustering konvensional (FCM).
  • Berikut diuraikan algoritma fuzzy clustering konvensional, yaitu penyelesaian fuzzy clustering dengan cara iteratif dengan melakukan update pada matrik keanggotan U dan matrik prototipe kluster V. Dalam algoritma diperlukan : Sampel objek sebanyak n, tiap objek p parameter, dituliskan : X={x1,x2,…,xn} xi? ?Rp , i=1,2,…,n. Ditentukan dalam proses penyelesaian melalui iterasi :
    U=[?ik] matrik ukuran cxn ; i=1,2,…,c ;
    k=1,2,…,n; V={v1,v2,…,vc} i=1,2,…,c

    Berikut adalah algoritma yang diajukan :

    • Initialization step :

      • Tentukan: n=cacah objek yang akan dikluster ; p=cacah parameter dalam tiap objek; c=cacah kluster; t=0 (iterasi ke); m=derajat fuzziness = dipilih 2; ?=nilai yang cukup kecil mendekati 0 Tentukan secara acak : U(0) dan V(0)

    • Iteration step

      • Dengan menggunakan U(t) , hitung pusat kluster V(t) menurut rumus :

      • Dengan menggunakan V(t) , update membership U(t) ,dengan rumus?

      • Jika max( |?ik (t) - ?ik (t-1) | ) < ??berhenti, Jika tidak ulangi langkah 2.a). Diagram alir untuk Fuzzy Clustering seperti tersaji dalam Gambar :
        
        

• Algoritma K-Means
  • Algoritma K-Means adalah Metode clustering berbasis jarak yang membagi data ke dalam sejumlah cluster dan algoritma ini hanya bekerja pada atribut numerik.
  • Pada dasarnya penggunaan algoritma dalam melakukan proses clustering tergantung dari data yang ada dan konklusi yang ingin dicapai. Untuk itu digunakan Algoritma K-Means yang di dalamnya memuat aturan sebagai berikut :
    • Jumlah cluster perlu diinputkan.
    • Hanya memiliki atribut bertipe numerik.
    • Jumlah atribut sedikit (<100)
  • Algoritma K-Means merupakan Metode nonheirarchial yang pada awalnya mengambil sebagian dari banyaknya komponen dari populasi untuk dijadikan pusat cluster awal.
    Algoritma K-Means pada dasarnya melakukan 2 proses yakni :
    • Proses Pertama:Proses pendeteksian lokasi pusat tiap?? cluster.
    • Proses Kedua? :Proses pencarian anggota dari tiap-tiap cluster.
  • Algoritma K-Means
    • Tentukan Jumlah K cluster.
    • Inisialisasi k pusat cluster sebagai seed points, Pusat ini dapat diperoleh secara acak.
    • Untuk setiap data pelanggan telkomnet instant,cari data yang lebih dekat dengan pusat cluster dan tandai titik data tersebut di pusat cluster yang terdekat dan posisi pusat cluster dihitung kembali dengan rata-rata anggota dari setiap cluster.
    • Cek semua data sekali lagi dan taruh setiap data yang terdekat dengan pusat cluster (pusat cluster tidak dihitung lagi). Jika anggota dari tiap pusat cluster tidak berubah,berhenti dan jika masih berubah kembali ke Step ke-2).?
• Algoritma Clara?
  • Lebih cocok digunakan pada data sets yang besar ?
  • Strategy
    • Gambar contoh secara acak X’ dari ukuran N’ dari semua data set.
    • Jalankan algoritma PAM untuk menunjukkan Θ?? yang menghasilkan ‘ terbaik.
    • Gunakan Θ?? pada Θ untuk menghasilkan seluruh? data set X.
      
  • Algoritma
    • Gambar contoh s subsets pada size N’ dari X, ditunjukkan dengan X?1,…,X?s (typically s = 5, N? = 40+2m).
    • Jalankan PAM pada tiap sample dan identify Θ?1,…,Θ?s.
    • Pilih set Θ?j? yang diminimized
  • Algoritma Clarans???
    • Lebih cocok digunakan pada data sets yang besar
    • Mengikuti filosofi dari PAM dengan perbedaan hanya pada? q(<m(N-m))? dari neighbors pada medoids set yang telah diperhitungkan.
    • Proses menjalankan (s) dimulai dari inisial kondisi? for Θ yang berbeda.

Contoh Paper 1

Contoh Paper 2