PENGEMBANGAN PENDEKATAN MULTIPLE MINIMUM SUPPORT UNTUK

MENGGALI FREQUENT CLOSED ITEMSET

*Endah Purwanti, **Eva Hariyanti

Program Studi Sistem Informasi, Fakultas Sains dan Teknologi,

Universitas Airlangga Kampus C Unair

Jl. Mulyosari Surabaya 60115

E-Mail: *endahpurwanti@fst.unair.ac.id, **eva.hariyanti@fst.unair.ac.id

Abstrak

Frequent closed itemsets merupakan himpunan itemset yang berperan dalam proses penggalian rule pada association rule mining. Penggalian frequent pattern seringkali menghasilkan sejumlah besar frequent itemsets dan rule, sehingga mengurangi efisiensi dan keefektifan dari proses mining karena user harus menyaring sejumlah besar rule hasil penggalian untuk menemukan rule yang penting. Oleh karena itu proses penggalian dapat diwakili hanya pada frequent closed itemsets. Penggunaan multiple minimum support bertujuan untuk menampung adanya perbedaan sifat dan frekuensi yang ada pada tiap item. Pada penelitian ini digunakan pengembangan pendekatan multiple minimum support untuk menggali frequent closed itemset. Multiple minimum support dihitung dengan memperhatikan nilai ‘support difference’ (SD). Pendekatan ini dilakukan agar item yang jarang bisa ikut tergali sebagai frequent itemset. Algoritma yang dikembangkan menggunakan struktur Multiple Item Support Tree (MIS-tree) untuk menyimpan pola yang ringkas dan penting tentang frequent pattern. Uji coba dilakukan pada tiga buah dataset, dengan memberikan nilai yang berbeda-beda pada parameter α yaitu 0.9, 0.5, dan 0.25, ë diisi dengan nilai rata-rata. Variasi nilai α menyebabkan nilai MIS juga bervariasi. Hasil uji coba menunjukkan bahwa frequent closed itemsets yang berhasil digali jumlah menurun selaras dengan meningkatnya nilai MIS.

Kata kunci: datamining, association rule, frequent closed itemsets, multiple minimum support.

Abstract

Frequent closed itemset is an itemset set the play in the process of extracting the association rule mining rule. Mining frequent pattern often produces a large number of frequent itemsets and rules, thereby reducing the efficiency and effectiveness of the mining process because the user have a large number of rules. Therefore the mining process can be represented only on frequent closed itemsets. The use of multiple minimum support aims to accommodate the differences in the nature and frequency for each item. This paper used multiple minimum support development approach to explore frequent closed itemset. Multiple minimum support is calculated by taking into account the value of 'support difference’ (SD). This approach is a rare item that can come as a frequent itemset mined. The algorithm was developed using Multiple Item Support Tree structure (MIS-tree) to store a concise and important pattern of frequent patterns. Tests carried out on three datasets, by giving different values to the parameter α. The trial results showed that the frequent closed itemsets unearthed decreasing amount in line with the rising value of SD.

Key word: datamining, association rule, frequent closed itemsets, multiple minimum support.

PENDAHULUAN

Datamining merupakan proses penggalian pola yang penting dan tersembunyi dari data yang sangat besar. Salah satu topik penting dalam datamining adalah association rule mining. Association rule mining [1] digunakan untuk menemukan relasi antar item yang ada pada database transaksi. Sejak association rule mining dikenalkan, telah banyak penelitian yang dilakukan untuk menemukan metode yang efektif untuk melakukan penggalian frequent itemset. Telah diakui bahwa penggalian frequent pattern memegang peranan penting pada proses association rule mining.

Frequent pattern mining seringkali menghasilkan sejumlah besar frequent itemsets dan rule, yang mengurangi tidak hanya efisiensi namun juga keefektifan dari proses mining karena user harus menyaring sejumlah besar rule hasil penggalian untuk menemukan rule yang penting. Pasquier dkk [2] telah melakukan penelitian dan menyatakan bahwa sebagai ganti mining complete set dari frequent itemset, association rule mining hanya perlu untuk menemukan frequent closed itemsets. Penggalian hanya pada frequent closed itemsets mampu mengurangi jumlah rule yang redundan yang dihasilkan dan menaikkan efisiensi dan keefektifan dari proses mining itu sendiri.

Elemen kunci yang membuat association rule mining dapat dijalankan adalah minimum support (minsup). Minsup digunakan untuk memangkas atau memperkecil ruang pencarian frequent itemsets dan juga untuk membatasi jumlah rule yang akan dihasilkan. Menggunakan single minsup secara implisit mengasumsikan bahwa semua item pada database memiliki sifat dan frekuensi yang sama. Padahal tidak demikian pada kenyataannya. Pada basis data retail, biasanya item yang berhubungan dengan keperluan sehari-hari, barang konsumsi dan barang-barang dengan harga rendah akan dibeli lebih sering daripada barang mewah atau barang dengan harga mahal. Pada situasi tersebut, jika minsup yang digunakan terlalu tinggi, semua pola yang ditemukan akan berhubungan dengan barang-barang harga murah. Padahal barang tersebut hanya memberikan keuntungan sedikit. Namun jika minsup yang diberikan telalu rendah, maka rule yang dihasilkan akan sangat banyak, yang mungkin saja banyak yang tidak berguna. Dan akan

menyebabkan kesulitan bagi pengambil keputusan untuk memahami pola yang ada yang dihasilkan dari datamining.

Untuk menyelesaikan masalah tersebut, [3] telah mengembangkan model association rule yang memperbolehkan user untuk menggunakan multiple minimum support. Multiple minimum support digunakan untuk menggambarkan sifat dasar dan frekuensi yang berbeda dari item-item yang ada. Pendekatan yang digunakan disebut dengan Multiple Support Apriori (MSApriori). Ternyata MSApriori masih belum bisa menangani ‘rule missing’ dan ‘rule explosion’. Jika nilai α tinggi, nilai MIS untuk item jarang secara relatif akan lebih mendekati nilai supportnya dibandingkan dengan frequent item. Akibatnya, itemset yang berisi item jarang akan gagal memenuhi nilai support. Sehingga himpunan frequent yang berisi item jarang akan terlewatkan. Selanjutnya apabila nilai α rendah, akan menyebabkan frequent item berasosiasi dengan semua item, akibatnya akan menghasilkan himpunan frequent item yang banyak.

Pada penelitian ini akan dilakukan pengembangan pendekatan untuk menemukan multiple minimum support, yaitu dengan menggunakan notasi ‘support difference’ (SD) yang diusulkan oleh [8]. Nilai SD memastikan perbedaan konstan antara item support dan nilai minsup untuk setiap item. ukan penggalian frequent closed itemsets dengan menggunakan multiple minimum support. Penggalian akan dilakukan dengan menggunakan struktur Multiple Item Support Tree (MIS-Tree) dan algoritma CLOSET [4]. MIS-tree merupakan struktur pohon yang dikembangkan serupa dengan struktur FP-tree untuk menyimpan informasi yang ringkas dan penting mengenai frequent pattern. Algoritma CLOSET merupakan algoritma untuk menggali frequent closed itemsets, namun dengan menggunakan single minimum support.

Association Rule Mining

Sebuah transaksi I={i1,i2,i3,...,id} adalah himpunan item yang ditransaksikan dan T={t1,t2,t3,...,tn} adalah himpunan transaksi. Setiap transaksi ti terdiri dari item yang merupakan subset dari I. Sebuah itemset X adalah himpunan bagian tidak kosong dari I.

Support dari sebuah itemset X, disimbolkan dengan sup(X), adalah jumlah transaksi yang

mengandung itemset X. Association rule R: X

4 Y adalah implikasi antara dua itemset X dan Y dimana X, Y c I dan X n Y=fly. Nilai support dari rule disebut dengan sup(X4Y), didefinisikan sebagai sup(Xv Y). Confidence dari rule, disebut dengan conf(X4Y),

sup(        )

X v Y

didefinisikan sebagai                      (X) . Untuk

sup

menemukan association rule dari sebuah transaksi, diperlukan nilai batasan yaitu minimum support (minsup) dan minimum confidence (minconf).

Frequent Closed Itemset

Menurut Liu et al [3], sebuah itemset Y adalah closed itemsets jika Y adalah frequent dan tidak terdapat superset langsung Y’ D Y sedemikian hingga sup(Y’)=sup(Y). Frequent itemsets sendiri adalah itemsets yang nilai support-nya lebih besar atau sama dengan minsup yang telah ditentukan.

Misalkan diketahui sebuah transaksi I={i1,i2,i3,...,id} adalah himpunan item yang ditransaksikan dan T={t1,t2,t3,...,tn} adalah himpunan transaksi. Setiap transaksi ti terdiri dari item yang merupakan subset dari I. Sebuah itemset X adalah himpunan bagian tidak kosong dari I. Support dari sebuah itemset X, disimbolkan dengan sup(X), adalah jumlah transaksi yang mengandung itemset X. Sebuah itemset Y adalah closed itemset jika Y adalah frequent itemset dan tidak terdapat superset langsung Y’ Y sedemikian hingga Dsup(Y’)=sup(Y). Frequent closed itemset yang dapat digali dari database transaksi pada Tabel 1 yaitu {f, c, b, fb, cb, cp, fcam, fcamp}.

Tabel 1. Database Transaksi

TID         Item       Item terurut        sesuai

MIS

100        a c f m p               f c a m p

200        a c d f m p           f c a m p d

300        a b c f g m           f c a b g m

400        b f i        f b i

500        b c n p   c b p n

MIS-Tree

Pada model ini, definisi umum dari minimum support diubah. Secara umum nilai minsup adalah sama untuk semua item, namun pada model ini setiap item dalam database dapat memiliki nilai minsup-nya sendiri¬sendiri yang disebut dengan minimum item support (MIS). Artinya user dapat memberikan

nilai MIS yang berbeda untuk item-item yang berbeda. Dengan memberikan nilai MIS yang berbeda untuk setiap item, maka hal tersebut akan merefleksikan sifat alamiah dari item itu sendiri dan mengakomodasikan adanya variasi frekuensi dalam database.

MIS-tree [5] adalah pengembangan dari struktur FP-tree, merupakan struktur pohon yang digunakan untuk menyimpan frequent item dengan multiple minimum support

Multiple Item Support

Misalkan I={a1, a2, ..., am} adalah himpunan item dan MIS(ai) menunjukkan nilai MIS untuk item ai. Maka nilai MIS dari itemset A={a1, a2, ..., ak} (1<k<m) adalah: min[MIS(a1), MIS(a2), ..., MIS(ak)]. [5]

Contoh 1:

Dalam database terdapat item bread, shoes, dan clothes. Dengan nilai MIS yang telah ditentukan sebagai berikut: MIS(bread)=2%, MIS(shoes)=0.1%, dan MIS(clothes)=0.2%. Jika nilai support dari itemset {clothes, bread}=0.15% maka itemset {clothes, bread} adalah infrequent. Karena nilai MIS dari itemset {clothes, bread} = min[MIS(clothes), MIS(bread)]=0.2%, yaitu lebih besar dari 0.15%.

Tabel 2. Nilai MIS Tiap Item

Item       MIS

F             4             (80%)

C             4             (80%)

A             3             (60%)

B             3             (60%)

G            3             (60%)

M           3             (60%)

P             2             (40%)

D            2             (40%)

I              2             (40%)

N            2             (40%)

Berikut ini langkah-langkah untuk membuat MIS-tree dari data transaksi pada Tabel 1 dengan nilai MIS tiap item pada Tabel 2. Langkah pertama adalah membuat tabel header yang berisi nilai MIS tiap item. Pada MIS-tree, item-item yang infequent tetap dimasukkan dalam tabel header, namun nanti akan dihapus pada proses pruning. Setiap item pada tabel header dihubungkan ke node pada tree yang mempunyai nama yang sama melalui head of node-link. Setelah tabel header terbentuk langkah selanjutnya adalah membuat

root dengan nilai null. Kemudian baca transaksi pertama dari database untuk membuat cabang pertama dari MIS-tree: ((f:1), (c:1), (a:1), (m:1), (p:1)). Transaksi kedua (f,

c, a, m, p, d) memiliki prefix yang sama (f, c, a, m, p) dengan jalur yang sudah ada. Sehingga count dari setiap node sepanjang prefix dinaikkan 1 dan sisa item (d) pada transaksi kedua akan dibuatkan node baru sebagai anak dari node p:2. Demikian seterusnya sampai dengan transaksi dalam database habis. Demikian seterusnya sampai dengan transaksi dalam database habis.

Karena dalam tabel header masih terdapat item yang tidak frequent, maka diperlukan sebuah proses pemangkasan (pruning). Item yang tidak frequent yaitu {d, i, n} karena nilai support-nya lebih kecil daripada nilai MIS. Struktur pohon juga mengalami penyesuaian karena penghapusan item-item tersebut dari tabel header. Setelah proses pemangkasan, dimungkinkan node-node dari MIS-tree mempunyai nama yang sama, sehingga perlu dilakukan proses penggabungan (merge). Untuk membuat bentuk kompak dilakukan penelusuran pada pohon dan ditemukan bahwa node (m:2) mempunyai dua anak dengan nama yang sama yaitu p. Dilakukan penggabungan dua node tersebut menjadi sebuah node item-name = p, dan count diisi dengan jumlah count dari kedua node tersebut. Bentuk MIS-tree yang lengkap dan kompak bisa dilihat pada Gambar 1.

F 4

C 4

A 3

B 3

G 3 M 3 P 2

Gambar 1. MIS-tree Lengkap dan Kompak Algoritma CLOSET

Ide dasar untuk menggali frequent closed itemsets pada algoritma CLOSET adalah dengan menggunakan teknik devide and conquer. Caranya adalah sebagai berikut :

Membuat conditional pattern base dan conditional FP-Tree untuk setiap item yang frequent secara bottom up dengan mengacu pada tabel header.

Mengulangi proses pada langkah a untuk setiap conditional FP-Tree yang terbentuk sampai dengan FP-Tree kosong atau tinggal memiliki 1 jalur saja.

Conditional pattern base harus dibangun untuk semua item yang terdapat pada tabel header. Dari conditional FP-tree yang terbentuk akan ditemukan kandidat frequent closed itemsets. Algoritma penggalian frequent closed itemsets dapat dituliskan seperti berikut ini:

ALGORITMA:      Frequent              Closed

Itemsets dengan Multiple minimum support (FCI_MIS)

INPUT: 1. database transaksi, 2. nilai MIS untuk setiap item, 3. MIS-tree

OUTPUT: himpunan lengkap frequent closed itemsets

METODE:             Panggil  fungsi

FCI_MIS(MIS-tree, null) Procedure FCI_MIS(tree, f)

{              for f anggota tabel header do

{              bangun proyeksi MIS-tree β

dengan prefiks f

Update tabel header

If tree β ≠null then Get_FCI_MIS(tree β, f, }}

Get_FCI_MIS(tree,           f,

anggota header tabel do

{ buat conditional database

dengan prefiks f

Update tabel header

If tree β ≠null then

{              Get FCI MIS(tree

_ _

β, f, MIS(f))

If            f.support             ≠

f.superset.support and f bukan subset dari frequent closed itemsets yang telah ditemukaan

               Close=true;         }}}

Support Difference

Support difference (SD) merujuk pada simpangan yang masih dapat diterima oleh sebuah item dari frekuensi atau supportnya.

Sehingga sebuah itemset dapat dianggap sebagai frequent itemset. Perhitungan minsup untuk setiap item ij (MIS(ij)) dapat dilihat pada persamaan (1).

MIS(ij)    = S(ij) – SD, jika (S(ij) – SD)

< LS = LS , untuk yang lainnya       (1)

Keterangan:

LS = nilai support terendah yang didefinisikan sebelumnya

SD = X(1-a)

X = parameter yang bisa diisi dengan nilai rata-rata, median, atau modus

a = parameter yang bernilai antara 0 dan 1 yang ditentukan sendiri oleh user

Nilai X dan a memegang peranan penting dalam mendefinisikan SD. Kedua nilai tersebut dapat disesuaikan dengan sifat statistik dari data.

HASIL DAN PEMBAHASAN

Uji coba dilakukan dengan menggunakan dataset yang biasa digunakan untuk menguji algoritma association rule mining yaitu basis data transaksi yang terdapat secara on-line. Dataset yang digunakan yaitu T1014D100K, Mushroom, dan Gazelle. Masing-masing dataset tersebut memiliki karakteristik yang berbeda. Karakteristik dari dataset-dataset besar ini dituliskan pada Tabel 2. Nilai a yang digunakan dalam uji coba adalah 0.9; 0.5; dan 0.25, sedangkan X diisi dengan nilai rata-rata. Mula-mula digunakan a kecil (a=0.25), dengan persamaan (1) nilai SD mendekati nilai rata-rata (X), untuk item jarang nilai MIS akan sama dengan LS. Hal ini dilakukan dengan harapan item jarang akan masuk dalam frequent itemsets. Pada a=0.9, nilai SD menjadi kecil sekali, sehingga MIS mendekati nilai support. Hal ini menyebabkan item jarang tidak akan berhasil masuk sebagai frequent itemset. Hasil penggalian frequent closed itemset dapat dilihat pada Gambar 2.

Tabel 2. Karakteristik Dataset

Dataset # Tuples               # Item

Mushroom          8124      120

Gazelle  59601    498

T1014D100k       100k      433329169

Gambar 2. Grafik Jumlah Frequent Closed Itemsets dengan variasi nilai a Pada ketiga Dataset

Hasil uji coba pada Gambar 2 menunjukkan bahwa jumlah frequent closed itemsets yang berhasil digali menurun selaras dengan meningkatnya nilai SD. Ketika nilai a=0.25, nilai MIS pada item jarang menjadi sama dengan LS, sehingga banyak frequent closed itemset yang berhasil digali. Sebaliknya ketika nilai a=0.9, nilai MIS mendekati nilai supportnya sehingga jumlah frequent closed itemsets yang berhasil digali menjadi kecil. Berkurangnya jumlah frequent closed itemsets menunjukkan bahwa penggunaan multiple minimum support mampu menaikkan efisiensi dari proses penggalian aturan asosiasi. Hasil frequent closed itemsets ini akan digunakan dalam proses penggalian aturan asosiasi selanjutnya.

KESIMPULAN

               Pada      penelitian            ini           digunakan

pengembangan pendekatan multiple minimum support untuk menggali frequent closed itemset. Multiple minimum support dihitung dengan memperhatikan nilai ‘support difference’ (SD). Pendekatan ini dilakukan agar item yang jarang bisa ikut tergali sebagai

               frequent              itemset.               Algoritma            yang

dikembangkan menggunakan struktur Multiple Item Support Tree (MIS-tree) untuk menyimpan pola yang ringkas dan penting tentang frequent pattern. Pada uji coba dipilih nilai a 0.9; 0.5; dan 0.25. Nilai ini dipilih untuk memberikan variasi pada nilai MIS, untuk a kecil, nilai MIS pada item jarang menjadi sama dengan LS. Sebaliknya pada a besar nilai MIS akan mendekati nilai supportnya. Hasil uji coba menunjukkan bahwa frequent closed itemsets yang berhasil digali jumlah meningkat selaras dengan menurunnya nilai MIS.

Untuk pengembangan lebih lanjut dari penelitian ini dapat dititikberatkan pada pemberian nilai LS (Low Support) dengan menggunakan suatu formula tertentu yang mampu mengakomodasi kepentingan item-item yang jarang.

SUMBER PUSTAKA

[1]          Agrawal, R., Imielinski, T., and Swami, A. (1993), “Mining association rules between sets of items in large databases”, In Proc. 1993 ACM-SIGMOD Int. Conf. Management of Data (SIGMOD’93), Washington, DC, pp. 207–216.

[2]          Han, J., Pei, J.dan Yin, Y., (2000), ”Mining Frequent Pattern Without Candidate Generation”, In Proc. 2000 ACM-SIGMOD Int. Conf. Management of Data (SIGMOD’00), Dallas, TX.

[3]          Liu, B., Hsu, W. dan Ma, Y., (1999)”Mining Association Rules with Multiple minimum support”, Proceedings of the ACM SIGKDD In. Conf. on Knowledge Discovery and Data Mining (KDD-99), San Diego, CA, USA.

[4]          Pasquier, N., Bastide, Y., Taouil, R., dan Lakhal, L., (1999), ” Discovering Frequent Closed Itemsets for association Rules”, In Proc. 7th Int. Conf. Database Theory (ICDT’99), pages 398-416, Jerusalem, Israel.

[5]          Pei, J., Han, J., Mao, R., (2000), "CLOSET: An efficient algorithm for mining frequent closed itemsets", Proceedings of the 2000 ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery, Dallas, Texas.

[6]          Purwanti, E., Arif, D., (2009) “Penggalian Frequent Closed Itemsets dengan Menggunakan Multiple Minimum Suppot”, Proceeding Seminar Nasional Pascasarjana ITS 2009, Surabaya.

[7]          Tan, P., Steinbach, M., Kumar, V.(2006), “Introduction to Data Mining”, Pearson Education, Boston.

[8]          Kiran U., Krishna R, (2009), “An Improved Multiple minimum support Based Approach to Mine Rare Association Rules”, Computational Intelligence and Data Mining, CIDM ’09, pages 340-347

[9]          Wang, J. , Han, J., Pei J., (2003), “CLOSET+: Searching for Best Strategies for Mining Frequent Closed Itemset”, Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'03), Washington, D.C., USA, hal 236-345.

[10]        Ya-Han Hu, Yen-Liang Chen, (2006),

“ Mining Association Rules with Multiple minimum supports: a New Mining Algorithm and a Support Tuning Mechanism ”, Decision Support Systems, Volume 42, Issue 1, Pages 1-24.