TUGAS UAS

INFORMATION RETRIEVAL

MAKALAH TENTANG KLASTERING

 

 

 

 

DISUSUN OLEH :

ANJAR SAPUTRA 15.01.55.0010

 

  

FAKULTAS TEKNOLOGI INFORMASI

SISTEM INFROMASI

2018

 

KATA PENGANTAR

            Puji syukur kehadirat Tuhan Yang Maha Esa atas segala rahmat-NYA sehingga makalah ini dapat tersusun hingga selesai . Tidak lupa kami juga mengucapkan banyak terimakasih atas bantuan dari pihak yang telah berkontribusi dengan memberikan sumbangan baik materi maupun pikirannya.

                Dan harapan saya semoga makalah ini dapat menambah pengetahuan dan pengalaman bagi para pembaca, Untuk ke depannya dapat memperbaiki bentuk maupun menambah isi makalah agar menjadi lebih baik lagi.  

                Karena keterbatasan pengetahuan maupun pengalaman kami, Kami yakin masih banyak kekurangan dalam makalah ini, Oleh karena itu kami sangat mengharapkan saran dan kritik yang membangun dari pembaca demi kesempurnaan makalah ini.       

                                                                                                                                                Semarang, 13 Juli 2018

                                                                                                                                                Penyusun,

BAB I PENDAHULUAN

  1. Latar Belakang

Clustering merupakan suatu metode untuk mencari dan mengelompokkan data yang memiliki kemiripan karakteristik (similarity) antara satu data dengan data yang lain. Clustering merupakan salah satu metode data mining yang bersifat tanpa arahan (unsupervised). Yang dimaksud metode unsupervised yaitu metode ini diterapkan tanpa adanya latihan (training) dan guru (teacher) serta tidak memerlukan target output. Dalam data mining ada dua jenis metode clustering yang digunakan dalam pengelompokan data, yaitu hierarchical clustering dan non-hierarchical clustering (Santosa, 2009).         

Teknik klustering saat ini juga telah banyak digunakan untuk mengatasi permasalahan yang terkait dengan segementasi data. Implementasi clustering ini dapat diterapkan pada berbagai bidang sebagai contoh dalam hal text mining. Teknik clustering dapat digunakan sebagai metode dalam mengelompokkan dokumen teks yang memiliki kesamaan konten/isi dan tema dari teks tersebut. Tujuan utama dari metode cluster adalah pengelompokan sejumlah data atau obyek ke dalam cluster (kelompok) sehingga dalam setiap cluster akan berisi data yang memiliki kesamaan karakteristik dari data tersebut. Pada pengelompokan dokumen, sekumpulan dokumen yang belum diberi label kelasnya akan dikelompokkan sesuai dengan karakteristik-karakteristik kata yang dimiliki setiap dokumen tersebut. Hal tersebut dilakukan untuk memudahkan pengorganisiran dokumen pada kebutuhan lebih lanjut.

Untuk melakukan proses clustering terdapat sebuah algoritma yang sering digunakan karena sifatnya yang relatif cepat dan mudah beradaptasi yaitu algoritma K-Means. Algoritma K-Means merupakan algoritma pengelompokan iteratif yang melakukan partisi set data ke dalam sejumlah K cluster yang sudah ditetapkan di awal. Pemilihan K titik data sebagai pusat cluster awal juga mempengaruhi hasil clustering. Sifat tersebut menjadi karakteristik alami K-Means yang dapat mengakibatkan hasil cluster yang didapat pada percobaan berbeda dengan hasil setelah proses clustering. Kondisi tersebut dikenal sebagai solusi local optimum, yang 2 artinya algoritma K-Means sangat sensitif terhadap lokasi awal pusat cluster. (Prasetyo, 2012).        

  1. Manfaat
  • Identifikasi obyek (Recognition) :Dalam bidang mage Processing , Computer Vision atau robot vision
  • Decission Support System dan data mining Segmentasi pasar, pemetaan wilayah, Manajemen marketing
  • Berbasis Fuzzy : Fuzzy C-Means
  • Berbasis Neural Network : Kohonen SOM, LVQ
  • Metode lain untuk optimasi centroid atau lebar cluster : Genetik Algoritma (GA)

 

BAB II PEMBAHASAN

Di dalam bab pembahasan ini penulis akan menjelakan mengenai macam-macam dari klastering dan bagaimana cara pengerjaannya dimasing masing macam-macam klastering. Penggunaan klastering itu dilihat dari kebutuhannya dan tujuannya. Dibawah ini penulis akan membahas tentang materi pembahasan klastering.

  1. Clustering Dengan Pendekatan Partisi

K-Means

Salah satu metode yang banyak digunakan dalam melakukan clustering dengan partisi ini adalah metode k-means. Secara umum metode k-means ini melakukan proses pengelompokan dengan prosedur sebagai berikut:

  • Tentukan jumlah cluster
  • Alokasikan data secara random ke cluster yang ada
  • Hitung rata-rata setiap cluster dari data yang tergabung di dalamnya
  • Alokasikan kembali semua data ke cluster terdekat
  • Ulang proses nomor 3, sampai tidak ada perubahan atau perubahan yang terjadi masih sudah di bawah treshold

Prosedur dasar ini bisa berubah mengikuti pendekatan pengalokasian data yang diterapkan, apakah crisp atau fuzzy. Setelah meneliti clustering dari sudut yang lain, saya menemukan bahwa k-means clustering mempunyai beberapa kelemahan.       Hal-hal terkait dengan metode k-means saya rangkum dalam tulisan saya yang dapat di-download di sini 

Mixture Modelling (Mixture Modeling)

Mixture modelling (mixture modeling) merupakan metode pengelompokan data yang mirip dengan k-means dengan kelebihan penggunaan distribusi statistik dalam mendefinisikan setiap cluster yang ditemukan. Dibandingkan dengan k-means yang hanya menggunakan cluster center, penggunaan distribusi statistik ini mengijinkan kita untuk:

  • Memodel data yang kita miliki dengan setting karakteristik yang berbeda-beda
  • Jumlah cluster yang sesuai dengan keadaan data bisa ditemukan seiring dengan proses pemodelan karakteristik dari masing-masing cluster
  • Hasil pemodelan clustering yang dilaksanakan bisa diuji tingkat keakuratannya

Distribusi statistik yang digunakan bisa bermacam-macam mulai dari yang digunakan untuk data categorical sampai yang continuous, termasuk di antaranya distribusi binomial, multinomial, normal dan lain-lain. Beberapa distribusi yang bersifat tidak normal seperti distribusi Poisson, von-Mises, Gamma dan Student t, juga diterapkan untuk bisa mengakomodasi berbagai keadaan data yang ada di lapangan. Beberapa pendekatan multivariate juga banyak diterapkan untuk memperhitungkan tingkat keterkaitan antara variabel data yang satu dengan yang lainnya.

Clustering dengan Pendekatan Hirarki

Clustering dengan pendekatan hirarki mengelompokkan data yang mirip dalam hirarki yang sama dan yang tidak mirip di hirarki yang agak jauh. Ada dua metode yang sering diterapkan yaitu agglomerative hieararchical clustering dan divisive hierarchical clustering. Agglomerative melakukan proses clustering dari N cluster menjadi satu kesatuan cluster, dimana N adalah jumlah data, sedangkan divisive melakukan proses clustering yang sebaliknya yaitu dari satu cluster menjadi N cluster.

Beberapa metode hierarchical clustering yang sering digunakan dibedakan menurut cara mereka untuk menghitung tingkat kemiripan. Ada yang menggunakan Single Linkage, Complete Linkage, Average Linkage, Average Group Linkage dan lain-lainnya. Seperti juga halnya dengan partition-based clustering, kita juga bisa memilih jenis jarak yang digunakan untuk menghitung tingkat kemiripan antar data.

Salah satu cara untuk mempermudah pengembangan dendogram untuk hierarchical clustering ini adalah dengan membuat similarity matrix yang memuat tingkat kemiripan antar data yang dikelompokkan. Tingkat kemiripan bisa dihitung dengan berbagai macam cara seperti dengan Euclidean Distance Space. Berangkat dari similarity matrix ini, kita bisa memilih lingkage jenis mana yang akan digunakan untuk mengelompokkan data yang dianalisa.

Clustering Dengan Pendekatan Automatic Mapping

Self-Organising Map (SOM)

Self-Organising Map (SOM) merupakan suatu tipe Artificial Neural Networks yang di-training secara unsupervised. SOM menghasilkan map yang terdiri dari output dalam dimensi yang rendah (2 atau 3 dimensi). Map ini berusaha mencari property dari input data. Komposisi input dan output dalam SOM mirip dengan komposisi dari proses feature scaling (multidimensional scaling).

Walaupun proses learning yang dilakukan mirip dengan Artificial Neural Networks, tetapi proses untuk meng-assign input data ke map, lebih mirip dengan K-Means dan kNN Algorithm. Adapun prosedur yang ditempuh dalam melakukan clustering dengan SOM adalah sebagai berikut:

  • Tentukan weight dari input data secara random
  • Pilih salah satu input data
  • Hitung tingkat kesamaan (dengan Eucledian) antara input data dan weight dari input data tersebut dan pilih input data yang memiliki kesamaan dengan weight yang ada (data ini disebut dengan Best Matching Unit (BMU))
  • Perbaharui weight dari input data dengan mendekatkan weight tersebut ke BMU dengan rumus:

Wv(t+1) = Wv(t) + Theta(v, t) x Alpha(t) x (D(t) – Wv(t))

Dimana:

    • Wv(t): Weight pada saat ke-t
    • Theta (v, t): Fungsi neighbourhood yang tergantung pada Lattice distance antara BMU dengan neuron v. Umumnya bernilai 1 untuk neuron yang cukup dekat dengan BMU, dan 0 untuk yang sebaliknya. Penggunaan fungsi Gaussian juga memungkinkan.
    • Alpha (t): Learning Coefficient yang berkurang secara monotonic
    • D(t): Input data
    • Tambah nilai t, sampai t < Lambda, dimana Lambda adalah jumlah iterasi

Variasi Metode Clustering

  • Quality Threshold Clustering Method
  • Locality Sensitive Hashing
  • Algoritma Rock
  • Hierarchical Frequent Term-Base Clustering
  • Suffix Tree Clustering
  • Single Pass Clustering
  • Neighborhood Clustering
  • Sequence Clustering
  • Spectral Clustering
  • Clustering on Frequent Tree
  • Latent Class Cluster Analysis a.k.a. Latent Profile Analysis a.k.a. Mixture Model for Continuous Variabel
  • Latent Class Analysis a.k.a. Mixture Model for Categorical Variable

Hal-hal Terkait Dengan Clustering

  • Analisa Faktor
  • Singular Value Decomposition
  • Eigen Value and Eigen Vector
  • Similarity Measure
  • Feature Discretisation
  • Feature Selection
  • Feature Scaling
  • Indexing Method For Searching

Clustering Implementation

  • Document Clustering Algorithm, Document Feature Extraction
  • Image Clustering

 

BAB III PENUTUP

Demikian yang dapat kami paparkan mengenai materi yang menjadi pokok bahasan dalam makalah ini, tentunya masih banyak kekurangan dan kelemahannya, kerena terbatasnya pengetahuan dan kurangnya rujukan atau referensi yang ada hubungannya dengan judul makalah ini.

Penulis banyak berharap para pembaca yang budiman dusi memberikan kritik dan saran yang membangun kepada penulis demi sempurnanya makalah ini dan dan penulisan makalah di kesempatan-kesempatan berikutnya. Semoga makalah ini berguna bagi penulis pada khususnya juga para pembaca yang budiman pada umumnya.

Referensi

 

  1. https://yudiagusta.wordpress.com/clustering/
  2. clustering, edy satrianto,M.Si
  3. Heni Sulastri1, Acep Irham Gufroni, Penerapan data mining dalam pengelompokan penderita thalassaemia