Algoritma K-Means Clustering

 K-Means adalah teknik yang cukup sederhana dan cepat dalam pekerjaan pengelompokkan data (clustering). Prinsip utama dari teknik ini adalah menyusun k buah prototipe/pusat massa (centroid)/rata-rata (mean) dari sekumpulan data berdimensi n. Teknik ini mensyaratkan nilai k sudah diketahui sebelumnya (a priori). Algoritma k-means dimulai dengan pembentukan prototipe cluster di awal kemudian secara iteratif prototipe cluster ini diperbaiki hingga konvergen (tidak terjadi perubahan yang signifikan pada prototipe cluster). Perubahan ini diukur menggunakan fungsi objektif J yang umumnya didefinisikan sebagai jumlah atau rata-rata jarak tiap item data dengan pusat massa kelompoknya. Secara lebih detil algoritma k-means adalah seperti berikut :

1. inisialisasi nilai J (misal MAXINT)
2. Tentukan prototipe cluster awal (bisa secara acak ataupun dipilih salah satu secara acak dari koleksi data)
3. Masukkan tiap satuan data ke dalam kelompok yang jarak dengan pusat massa-nya paling dekat
4. ubah nilai pusat massa tiap cluster sebagai rata-rata (mean) dari seluruh anggota kelompok tersebut
5. Hitung fungsi objektif J
6. jika nilai J sama dengan sebelumnya, berhenti atau ulangi langkah 3

Sumber: Buku Konsep Data Mining

Data Mining: Clustering

Clustering adalah proses mengelompokkan objek berdasarkan informasi yang diperoleh dari data yang menjelaskan hubungan antar objek dengan prinsip untuk memaksimalkan kesamaan antar anggota satu kelas dan meminimumkan kesamaan antar kelas/cluster. Tujuannya menemukan cluster yang berkualitas dalam waktu yang layak. Clustering dalam data mining berguna untuk menemukan pola distribusi di dalam sebuah data set yang berguna untuk proses analisa data. Kesamaan objek biasanya diperoleh dari kedekatan nilai-nilai atribut yang menjelaskan objek-objek data, sedangkan objek-objek data biasanya direpresentasikan sebagai sebuah titik dalam ruang multidimensi.

Dengan menggunakan clustering, dapat diidentifikasi daerah yang padat, pola-pola distribusi secara keseluruhan dan keterkaitan yang menarik antara atribut-atribut data. Dalam data mining usaha difokuskan pada metode-metode penemuan untuk cluster pada basisdata berukuran besar secara efektif dan efisien. Banyaknya pendekatan clustering menyulitkan dalam menentukan ukuran kualitas yang universal. Namun, beberapa hal yang perlu diperhatikan adalah input parameter yang tidak menyulitkan user, cluster hasil yang dapat dianalisa, dan skalabilitas terhadap penambahan ukuran dimensi dan record dataset. Secara garis besar ada beberapa kategori algoritma clustering yang dikenal yaitu:

a. Metode Partisi, dimana pemakai harus menentukan jumlah k partisi yang diinginkan lalu setiap data dites untuk dimasukkan pada salah satu partisi sehingga tidak ada data yang overlap dan satu data hanya memiliki satu cluster. Contohnya: algoritma K-Means.

b. Metode Hierarki, yang menghasilkan cluster yang bersarang artinya suatu data dapat memiliki cluster lebih dari satu. Metode ini terbagi menjadi dua yaitu buttom-up yang menggabungkan cluster kecil menjadi cluster lebih besar dan top-down yang memecah cluster besar menjadi cluster yang lebih kecil. Kelemahan metode ini adalah bila salah satu penggabungan/pemecahan dilakukan pada tempat yang salah, tidak akan didapatkan cluster yang optimal. Contohnya: Agglomerative (FINDIT, PROCLUS), Divisive Hierarchical Clustering (CLIQUE, MAFIA, ENCLUE).

Sumber: Buku Konsep Data Mining

Algoritma CT-Pro

Algoritma CT-PRO merupakan salah satu algoritma pengembangan dari FP-Growth. Perbedaannya terdapat pada langkah kedua dimana FP-Growth membuat FP-Tree sedangkan CT-PRO membuat Compressed FP-Tree (CFP- Tree )[8]. Pada tahap mining algoritma CT-PRO juga menggunakan pendekatan bottom-up dimana item pada item tabel dan CFP-Tree dilakukan scan dari jumlah terkecil hingga terbesar. Algoritma CT-PRO memiliki tiga tahap yaitu:

1. Menemukan item-item yang frequent

2. Membuat struktur data CFP-Tree

3. Melakukan mining frequent patterns
Langkah-langkah kerja algoritma CT-Pro:

1.      Mencari Frequent item, pada tahap ini terjadi proses-proses sebagai berikut:

-          Dari dataset yang ada, dilakukan seleksi berdasarkan minimum support yang ditentukan sehingga menghasilkan frequent item.

-          Dari frequent item yang telah terbentuk, dihitung frekuensi kemunculan setiap item sehingga menghasilkan Global Item tabel.

2.      Membangun CFP-Tree, pada tahap ini terjadi proses-proses sebagai berikut:

-          Frequent item yang telah didapatkan, diurutkan berdasarkan Global Item tabel yang ada secara menurun (diurutkan mulai dari item berfrekuensi terbesar hingga terkecil).

-          Dengan frequent item yang telah terurut ini dibentuk Global CFP-Tree, aturan pembentukan Global CFP-Tree sebagai berikut:

a.       CFP-Tree terdiri dari tree yang memiliki root yang mewakili index dari item dengan tingkat kemunculan tertinggi dan kumpulan subtree sebagai anak dari root.

b.      Jika I = {i1,i2, …, ik} adalah kumpulan dari frequent item dalam transaksi, item dalam transaksi akan dimasukkan  ke dalam CFP-Tree dimulai dari root subtree yang merupakan i1 dalam

b.item tabel.

c.       Root dari CFP-Tree merupakan level-0 dari tree.

d.      Setiap node dalam CFP-Tree memiliki empat field utama yakni item-id, parent-id, count yang merupakan jumlah item pada node tersebut, dan level yang menunjukkan struktur data tree pada node tersebut dimulai dari item yang terdapat pada item tabel dengan level yang terdapat pada CFP-Tree .

3.      Mining, pada tahap ini terjadi proses-proses sebagai berikut:

-          Pada tahap mining ini, algoritma CT-Pro bekerja dengan melakukan bottom -up mining sehingga Global Item tabel diurutkan mulai dari item berfrekuensi terkecil hingga terbesar.

-          Untuk setiap item yang terdaftar pada Global Item tabel yang telah diurutkan, dilakukan pencarian  node yang berkaitan dengan item tersebut pada Global CFP-Tree. Dari semua node yang ditemukan untuk setiap item inilah yang disebut dengan Local Frequent item dan digunakan untuk membuat Local Item Tabel.

-          Pada pembuatan local item tabel ini juga dilakukan berdasarkan jumlah minimum support yang telah ditentukan.

-          Setelah itu, dibuat Local CFP-Tree berdasarkan Local Item Tabel yang terbentuk. Aturan pembentukan Local CFP-Tree sama dengan pembentukan Global CFP-Tree, yang membedakan adalah pada Global CFP-Tree yang digunakan dalam pembentukan tree-nya adalah  Global Item tabel yang terbentuk dari Global Item tabel data sedangkan pada Local CFP-Tree yang digunakan dalam pembentukan tree-nya adalah Local Item tabel yang terbentuk dari Local Frequent item.

-          Dari Local CFP-Tree dibentuk frequent pattern sesuai dengan item yang dimining.

Dari frequent pattern dihitung masing-masing item yang memenuhi dihitung confidencenya. Apabila memenuhi minimum confidence maka masing-masing item yang bersangkutan dijadikan sebagai knowledge.

Sumber: Buku TA-Parama Fadli Kurnia (IT Telkom/113090065)

Algoritma FP-Growth

Algoritma FP-Growth adalah cara alternatif untuk menemukan itemsets sering tanpa menggunakan generasi calon, sehingga meningkatkan kinerja. Untuk begitu banyak menggunakan membagi-dan-menaklukkan strategi  . Inti dari metode ini adalah penggunaan struktur data khusus bernama sering-pola pohon (FP-pohon), yang mempertahankan informasi asosiasi itemset.

Dengan kata sederhana, algoritma ini bekerja sebagai berikut: pertama kompres database masukan menciptakan sebuah instance FP-Tree untuk mewakili item sering. Setelah langkah pertama membagi database dikompresi menjadi satu set database kondisional, masing-masing terkait dengan satu pola yang sering. Akhirnya, masing-masing database tersebut ditambang secara terpisah. Menggunakan strategi ini, FP-Growth mengurangi biaya pencarian mencari pola singkat rekursif dan kemudian concatenating kemudian dalam pola yang sering panjang, menawarkan selektivitas yang baik.

Dalam database besar, itu tidak mungkin untuk memegang FP-pohon di memori utama. Sebuah strategi untuk mengatasi masalah ini adalah untuk pertama partisi database menjadi satu set database yang lebih kecil (disebut database diproyeksikan), dan kemudian membangun sebuah FP-pohon dari masing-masing database yang lebih kecil.

Sumber: Buku Konsep Data Mining

Algoritma Aplriori

Persoalan association rule mining terdiri dari dua sub persoalan :
a. Menemukan semua kombinasi dari item, disebut dengan frequent itemsets, yang memiliki support     yang lebih besar daripada minimum support.
b. Gunakan frequent itemsets untuk men-generate aturan yang dikehendaki.Semisal,  ABCD dan AB adalah frequent, maka didapatkan aturan AB -> CD jika rasio dari upport(ABCD) terhadap support(AB) sedikitnya sama dengan minimum confidence. Aturan ini memiliki minimum support karena ABCD adalah frequent.
          Algoritma Apriori yang bertujuan untuk menemukan frequent itemsets dijalankan pada sekumpulan data. Pada iterasi ke -k, akan ditemukan semua itemsets yang memiliki k items, disebut dengan k -itemsets. Tiap iterasi berisi dua tahap. Misal Oracle Data Mining Fk merepresentasikan himpunan dari frequent k -itemsets, dan Ck adalah himpunan candidate k-itemsets (yang potensial untuk menjadi frequent itemsets). Tahap pertama adalah men-generate kandidat, dimana himpunan dari semua frequent (k- 1) itemsets, Fk-1, ditemukan dalam iterasi ke-(k-1), digunakan untuk men-generate candidate itemsets Ck. Prosedur generate candidate memastikan bahwa Ck adalah superset dari himpunan semua frequent k-itemsets. Struktur data hash-tree digunakan untuk menyimpan Ck. Kemudian data di-scan dalam tahap penghitungan support. Untuk setiap transaksi, candidates dalam Ck diisikan ke dalam transaksi, ditentukan dengan menggunakan struktur data hash-tree hashtree dan nilai penghitungan support dinaikkan. Pada akhir dari tahap kedua, nilai Ck diuji untuk menentukan yang mana dari candidates yang merupakan frequent. Kondisi penghitung (terminate condition) dari algoritma ini dicapai pada saat Fk atau Ck+1 kosong.

Sumber: Buku Konsep Data Mining

Association Rule Mining

Mining association rules atau pencarian aturan-aturan hubungan antar item dari suatu basis data transaksi atau basis data relasional, telah menjadi perhatian utama dalam masyarakat basis data. Tugas utamanya adalah untuk menemukan suatu himpunan hubungan antar item dalam bentuk A1A...AAm => B1A...ABn dimana A, ( for i E {1,...,m}) dan B; ( for j C {1,...,n} ) adalah himpunan atribut nilai, dari sekumpulan data yang relevan dalam suatu basis data. Sebagai contoh, dari suatu himpunan data transaksi, seseorang mungkin menemukan suatu hubungan berikut, yaitu jika seorang pelanggan membeli selai, ia biasanya juga membeli roti dalam satu transaksi yang sama. Oleh karena proses untuk menemukan hubungan antar item ini mungkin memerlukan pembacaan data transaksi secara berulang-ulang dalam sejumlah besar data-data transaksi untuk menemukan pola-pola hubungan yang berbeda-beda, maka waktu dan biaya komputasi tentunya juga akan sangat besar, sehingga untuk menemukan hubungan tersebut diperlukan suatu algoritma yang efisien dan metodemetode tertentu.

         Analisis asosiasi atau association rule mining adalah teknik data mining untuk menemukan aturan assosiatif antara suatu kombinasi item. Contoh dari aturan assosiatif dari analisa pembelian di suatu pasar swalayan adalah dapat diketahuinya berapa besar kemungkinan seorang pelanggan membeli roti bersamaan dengan susu. Dengan pengetahuan tersebut pemilik pasar swalayan dapat mengatur penempatan barangnya atau merancang kampanye pemasaran dengan memakai kupon diskon untuk kombinasi barang tertentu. Karena analisis asosiasi menjadi terkenal karena aplikasinya untuk menganalisa isi keranjang belanja di pasar swalayan, analisis asosiasi juga sering disebut dengan istilah market basket analysis 

          Fungsi Association Rules seringkali disebut dengan "market basket analysis", yang digunakan untuk menemukan relasi atau korelasi diantara himpunan item. Market Basket Analysis adalah Analisis dari kebiasaan membeli customer dengan mencari asosiasi dan korelasi antara item-item berbeda yang diletakkan customer dalam keranjang belanjaannya. Fungsi ini paling banyak digunakan untuk menganalisa data dalam rangka keperluan strategi pemasaran, desain katalog, dan proses pembuatan keputusan bisnis. Tipe association rule bisa dinyatakan sebagai misal : "70% dari orangorang yang membeli mie, juice dan saus akan membeli juga roti tawar". Aturan asosiasi mengcapture item atau kejadian dalam data berukuran besar yang berisi data transaksi. Dengan kemajuan teknologi, data penjualan dapat disimpan dalam jumlah besar yang disebut dengan "basket data." Aturan asosiasi yang didefinisikan pada basket data, digunakan untuk keperluan promosi, desain katalog, segmentasi customer dan target pemasaran. Secara tradisional, aturan asosiasi digunakan untuk menemukan trend bisnis dengan menganalisa transaksi customer.
          Berdasarkan definisi di [6] maka pencarian pola kaidah asosiasi mengunakan dua buah parameter nilai yaitu dukungan (support) dan keterpercayaan (confidence) yang memiliki nilai antara 0% - 100 %. Berikut sedikit penjelasan mengenai dukungan dan keterpercayaan.
          Sebagai contoh terdapat relasi I berisi sejumlah kumpulan item yang kemudian dikatakan sebagai itemset, dimana masing–masing itemset terdiri dari sekumpulan atribute bertipe boolean I1, I2, …, In. Dan basis data transaksi D yang berisi transaksi T, adalah himpunan dari I atau T Í I. Dimana transaksi T pada basis data transaksi D memiliki sebuah atribut yang unik yang dinotasikan dengan TID. Dalam konteks ini, A dan B merupakan itemset dari transaksi T, jika dan hanya jika A Í T dan B Í T. Sehingga jumlah A dinotasikan ó (A) merupakan jumlah Support (support count) itemset A pada basis data transaksi D. Kaidah asosiasi A› B, jika dan hanya jika A I, B I dan A B 0. Sehingga A› B memiliki Support s pada transaksi T, dimana S merupakan persentase itemset A È B pada basis data transaksi D. Dan A› B memiliki Confidence C pada transaksi T, dimana C merupakan persentase jumlah itemset A yang terdapat pada relasi I, yang diikuti itemset B. Dukungan kaidah asosiasi A› B dinyatakan dengan :
           Support (A› B) = P(AÈB) (xx)
           Sedangkan keterpercayaan kaidah asosiasi A› B
           dinyatakan dengan :
           Confidence (A› B) = P(A|B) (xx)
           dimana :A dan B adalah frequent itemset memiliki jumlah dukungan lebih besar
sama dengan batas ambang dukungan minimum).

Sumber: Buku Konsep Data Mining

Model Data Mining

Macam - Macam Model Data Mining

A. Metode Prediksi
Dengan menggunakan beberapa variabel untuk memprediksi nilai yang belum diketahui (unknown) atau nilai selanjutnya (future) atau variabel lain.

Contoh :

1. Classification

• Pada persoalan klasifikasi, kita memiliki sejumlah kasus (sampel data) dan ingin mempresiksi beberapa class yang ada pada sampel data tersebut.
• Tiap isntan data berisi banyak atribut, dimana masing-masing atribut memiliki satu dari beberapa kemungkinan nilai.
• Hanya satu atribut diantara banyak aribut tersebut yang disebut atribut target, sedangkan atribut yang lain disebut sebagai atribut prediktor.

2. Regression
3. Deviation Detection

B. Metode Deskripsi
Menemukan pola pendeskripsian data yang dapat diinterpretasikan oleh manusia.

Contoh :

1. Clustering

• Teknik yang berguna untuk mengeksplorasi data
• digunakan pada saat banyak kasus dan tidak memiliki pengelompokan secara alami. (Dalam hal ini algoritma data mining dapat digunakan untuk mencari pengelompokan yang ada pada peta).
• Clustering model berbeda dari model prediktif dikarenakan pada clustering tidak perlu ada atribut target.
• Clustering juga dapat diorganisasi ke dalam sturktur hirarkikal akan mendefinisikan taksonomi dari data.

2. Association Rule Discovery

• Sering disebut "Market Basket Analysis" yang digunakan untk menemukan relasi atau korelasi diantara himpunan item-item.
• Fungsi ini paling banyak digunakan untuk menganalisa data dalam rangka keperluan strategi pemasaran, desain katalog, dan proses pembuatan keputusan bisnis.
• Bisa dinyatakan sebagai, misal : "70 % dari orang-orang yang memebeli mie, juice dan saus akan membeli juga roti tawar."

3. Sequential Pattern Discovery

Sumber: Buku Konsep Data Mining

Data Mining

Pengertian Data Mining menurut para ahli :
Definisi data mining berdasarkan [JK06] adalah proses mengekstraksi pola-pola yang menarik (tidak remeh-temeh, implisit, belum diketahui sebelumnya, dan berpotensi untuk bermanfaat) dari data yang berukuran besar. Ada beberapa istilah yang mempunyai kemiripan dengan data mining, yaitu ekstraksi pengetahuan, analisis pola, pengerukan data, dan lain-lain. Ada yang berpendapat data mining merupakan sinonim dari istilah knowledge discovery in database (KDD).

Data mining adalah serangkaian proses untuk menggali nilai tambah berupa informasi  yang selama ini tidak diketahui secara manual dari suatu basisdata.  Informasi yang dihasilkan diperoleh dengan cara mengekstraksi dan mengenali pola yang penting atau menarik dari data yang terdapat dalam basisdata.

Manfaat Data Mining :
Classification, Menentukan karakteristik dari kelompok tertentu.
Clustering, Identifikasi kelompok/groups dari item-tem yangberbagi satu karakteristik. Clustering berbeda dengan classification,dimana tidak ada penentuan terlebih dulu karakteristik
Association, Identifikasi relationships antara event-event yangterjadi pada suatu saat.
Sequencing, Identifies relationships yang ada sepanjang satuperiode waktu.
Forecasting, Estimasi nilai2 masadatang berdasarkan patternsdalam sekumpulan besar data.
Regression, Memetakan sebuah data item pada satu variableprediksi.
Time Series analysis, menguji sebuah nilai atas variasinya sepanjang waktu.

Tujuan Data Mining :
tujuan dari data mining adalah menemukan hubungan-hubungan ataupola-pola yang mungkin memberikan indikasi yang bermanfaat. Kehadiran data mining dilatar belakangi oleh berlimpahnya data(overload data) yang dialami oleh berbagai institusi, perusahaanatau organisasi. Berlimpahnya data ini merupakan akumulasi datatransaksi yang terekam bertahun-tahun. Data–data tersebut merupakan  data  transaksi yang umumnya diproses menggunakan aplikasi komputer yang biasa disebut On Line Transaction Processing).

Data mining juga dilatarbelakangi oleh atau adanya ledakan informasi (explotion information) dari berbagai media terutama internet. Delapan puluh persen informasi yang disajikan media internet dalam bentuk tak terstruktur (unstructured information). Media internet menyajikan informasi dalam berbagai format file, bahasa, dan bentuk penyajian seperti teks, gambar, suara ataupun  video. Kendala lainyang melatarbelakangi adalah tidak dilengkapinya informasi dengan metadata yang terstandarisasi atau bahkan tidak menyertakannya sama sekali.

Pertumbuhan yang pesat dari akumulasi data/informasi itu telah menciptakan kondisi dimana suatu institusi memiliki bergunung-gunung data tetapi  miskin informasi yang bermaanfaat(“rich of data but poor of information”). Tidak jarang “gunung” data itu dibiarkan begitu saja seakan-akan menjadi  “kuburan data” (datatombs). Pertanyaannya sekarang, apakah gunung data tersebut akan dibiarkan, tidak berguna lalu dibuang, ataukah dapat ditambang untuk menemukan “emas” yaitu informasi yang lebih bermanfaat. Jawabnya ya, data mining hadir untuk menjawab tantangan tersebut.

Sumber: Buku Konsep Data Mining