Mining Itemset using Vertical Data Format (Menghitung Closed Itemset )

Satu bab yang cukup rumit pada mata kuliah Data Mining adalah Mining Itemset using Vertical Data Format. Berikut ini adalah contoh soal dengan 5 buah transaksi:

• T1: a,b,c
• T2: a,b,c,d
• T3: c,d
• T4: a,e
• T5: a,c

Pertanyaannya adalah:

1. Cari closed sets!
2. Jika minimum support =2, cari closed frequent dan maximal frequent set –nya.

Cara mengerjakannya adalah mengikuti soal tersebut, karena pertanyaan 1 dan 2 merupakan urutannya. Pertama-tama kita rinci terlebih dahulu closed sets dari item-itemnya, dimulai dari yang set terkecil (satu).

Set    Support    closed set/tidak ?

1. {a}    4        closed set
2. {b}    2        bukan closed set
3. {c}    4        closed set
4. {d}    2        bukan closed set
5. {e}    1        bukan closed set

Mengapa {b} bukan closed set? Karena dia memiliki super-itemset yang jumlahnya juga dua (yaitu {a,b,c} dan {a,b,c,d}). Syarat closed itemset adalah supportnya harus lebih besar dari super-itemsetnya. Untuk sementara diperoleh closed sets = {{a}, {c}} dan karena keduanya di atas nilai minimum support (dua), maka sets tersebut juga closed frequent.

Berikutnya untuk yang jumlah setnya dua.

Set    Support    closed set/tidak?

1. {a,b}    2        bukan closed set
2. {a,c}    3        closed set
3. {a,d}    1        bukan closed set
4. {a,e}    1        closed set
5. {b,c}    2        bukan closed set
6. {b,d}    1        bukan closed set
7. {b,e}    –        bukan closed set
8. {c,d}    2        closed set
9. {c,e}    –        bukan closed set
10. {d,e}    –        bukan closed set

Closed Frequent = {{a,c}, {c,d}}. Mengapa {a,e} walaupun closed set tetapi tidak frequent? Karena supportnya hanya satu maka tidak memenuhi persyaratan frequent yaitu lebih besar atau sama dengan minimum supportnya (dua). Berikutnya untuk jumlah item tiga.

1. {a,b,c}    2
2. {a,b,d}    1
3. {a,c,d}    1
4. {b,c,d}    1

Dan diperoleh Closed Frequent ={{a,b,c}} karena yang lainnya di bawah min_support. Jadi diperoleh Closed Frequent sets = {{a},{c},{a,c},{c,d},{a,b,c}}.

Untuk soal no.2 kita diminta mencari Maximal Frequent Sets yaitu sets yang frequent, misal X, dan tidak memiliki Super-Itemsets yg frequent juga, Y, dimana Y ᴐ X.

Jawabannya adalah {{c,d},{a,b,c}}.

Mengapa {c,d}? lihat di transaksi, {c,d} tidak memiliki super-itemset, dan item tersebut frequent, jadi {c,d} adalah maximal. Bagaimana dengan {a,b,c}? walaupun dia memiliki super-itemsets {a,b,c,d} tetapi itemset ini tidak frequent (di bawah min_support).

Untuk yang ingin mendalami lebih jauh, bisa baca jurnalnya di sini.