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)