Dm_akhir_f_117006282.docx

TUGAS AKHIR DATA MINING

Data Mining Menggunakan Algoritma Fp-Growth Untuk Market Basket Analysis

Hidrian Oma Suharman 117006282

MBA (Market Basket Analysis) merupakan salah satu contoh dari data mining yang digunakan untuk menganalisa kebiasaan konsumen dalam berbelanja. MBA bisa menjadi tidak berguna ketika dihadapkan pada data yang kecil, namun akan menghasilkan informasi yang berharga ketika dipergunakan pada data yang besar seperti misalnya data transaksi sebuah supermarket besar. Salah satu teknik dalam data mining yang terkenal dan cocok untuk MBA adalah association rule mining. Association rule mining memiliki beberapa algoritma yang sudah sering digunakan, diantaranya algoritma Apriori, FPGrowth, dan CT-PRO yang dimana ketiga algoritma tersebut memiliki kelebihan dan kekurangan masing-masing. Dalam dokumen percobaan ini penulis akan menggunakan algoritma FP-Growth (Frequent Pattern Growth).

Association Rule Association Rule merupakan suatu proses untuk menemukan semua aturan assosiatif yang memenuhi syarat minimum untuk support (minsup) dan syarat minimum untuk confidence (minconf) pada sebuah database. Dalam menentukan suatu Association Rule umumnya terdapat dua ukuran kepercayaan (interestingness measure), yaitu support dan confidence. Kedua ukuran ini akan digunakan untuk interesting association rules dengan dibandingkan dengan batasan yang telah ditentukan. Batasan inilah yang terdiri dari minsup dan minconf. Assosiation Rule Mining adalah suatu prosedur untuk mencari hubungan antar item dalam suatu dataset. Dimulai dengan mencari frequent itemset, yaitu

1

kombinasi yang paling sering terjadi dalam suatu itemset dan harus memenuhi minimum support. Dalam tahap ini akan dicari kombinasi item yang memnuhi syarat minimum dari nilai support dalam database. Untuk mendapatkan nilai support untuk sebuah item A dapat diperoleh dari rumus berikut: Support (A) =

Jumlah transaksi yang mengandung item A Total transaksi

Sementara itu, untuk mencari nilai support dari 2-item dapat diperoleh dari rumus berikut :

Support (A,B) = P (A∩ B) =

Jumlah transaksi yang mengandung A dan B Total transaksi

(2.2)

Setelah semua frequent item dan Large itemset ditemukan, dapat dicari semua Association Rules yang memenuhi syarat minimum untuk confidence (minconf) dengan menggunakan rumus berikut ini :

Confidence (A B) = P (B|A) =

Jumlah transaksi yang mengandung A dan B Jumlah transaksi yang mengandung A

(2.3)

Market Basket Analysis Market Basket Analysis adalah salah satu teknik pemodelan dalam data mining berdasarkan teori yang mana jika anda membeli suatu grup item, anda akan memiliki kemungkinan membeli itemset yang lain (data mining concept and technique, Jiawei Han). Market Basket berdasarkan kumpulan item yang dibeli oleh konsumen dalam sebuah transaksi. Dalam hal ini, kuantitas dari sebuah item yang dibeli konsumen tidak mempengaruhi proses analisis ini. Market Basket Analysis hanya berdasarkan tipe-tipe item yang berbeda, tidak peduli seberapa banyak kuantitasnya. Dalam Market Basket Analysis akan dianalisis akumulasi kumpulan transaksi dari sejumlah besar konsumen dalam periode waktu yang telah

2

berlangsung. Proses ini menganalisis buying habits dari para konsumen dengan menemukan hubungan assosiasi antar item-item yang berbeda yang seringkali dibeli oleh konsumen. Hasil dari proses analisis ini nantinya akan sangat berguna bagi perusahaan retail khususnya seperti toko swalayan dan supermarket untuk mengembangkan strategi pemasaran dan proses pengambilan keputusan dengan melihat item-item berbeda yang sering dibeli secara bersamaan oleh konsumen dalam satu waktu. Beberapa kombinasi item yang sering dibeli konsumen memang terkadang sangat mudah untuk ditebak, contohnya seringkali konsumen membeli susu bayi dan popok secara bersamaan. Pola ini sangat biasa terjadi dan mudah ditebak karena susu bayi dan popok memiliki hubungan yang sangat dekat. Namun terkadang pola seperti deterjen dan telur jarang terfikirkan karena deterjen dan telur tidak mempunyai hubungan sama sekali. Melalui Market Basket Analysis, pola-pola yang terkadang tidak terfikirkan ini dapat ditemukan dengan mudah sehingga akan membantu pengambilan keputusan dan proses pengembangan strategi bagi perusahaan retail. Masalah-masalah seperti kehabisan stok akan diminimalisir dengan diketahuinya pola pembelian konsumen melalui Market Basket Analysis sehingga dapat meningkatkan penjualan perusahaan tersebut.

Algoritma FP-Growth Algoritma FP-Growth merupakan salah satu alternatif algoritma yang cukup efektif untuk mencari himpunan data yang paling sering muncul (frequent itemset) dalam sebuah kumpulan data yang besar. Algoritma FP-Growth merupakan algoritma Association Rules yang cukup sering dipakai. Algoritma FP-Growth ini dikembangkan dari algoritma apriori. Algoritma apriori menghasilkan kombinasi yang sangat banyak sehingga sangat tidak efisien. Algoritma FP-Growth ini merupakan salah satu solusi dari algoritma apriori yang memakan waktu yang sangat lama karena harus melakukan pattern matching yang secara berulangulang. Sedangkan dalam proses Algoritma FP-Growth terdapat banyak kelebihan yang terbukti sangat efisien karena hanya dilakukan pemetaan data atau scan

3

database sebanyak 2 kali untuk membangun struktur ”tree”. Maka dari itu, Algoritma FP-Growth dikenal juga dengan sebutan algoritma FP-Tree. Dengan menggunakan struktur FP-Tree, algoritma FP-Growth dapat langsung mengekstrak frequent itemset dari susunan FP-Tree yang telah terbentuk.

Dalam percobaan ini akan digunakan data mentah yaitu sebuah data transaksi penjualan sebuah supermarket dalam suatu periode waktu. Data sekunder ini terdiri dari 4627 jumlah transaksi penjualan dengan 216 jenis item.

Tabel 1 Sampel Data Bread Spices Biscuits Tea Deodorant

Canned Cheese Breakfast Coffee . . . Beef fruit

food

.

true

?

true

?

?

?

true

?

true

?

?

?

?

?

true

true

?

?

?

?

true

?

true

?

true

?

?

?

?

true

true

?

true

?

?

?

true

true

?

true

true

?

?

true

?

?

?

?

true

true

true

true

true

true

?

true

?

true

?

?

true

?

true

true

true

true

true

true

?

?

true

?

true

?

?

?

?

?

true

?

?

?

?

?

?

?

?

?

?

?

true

?

true

?

?

true

?

?

?

true

true

?

true

?

?

true

true

true

true

true

true

?

?

?

true

true

true

?

?

true

true

?

true

?

?

?

?

true

true

?

?

?

?

?

?

?

?

?

?

?

true

?

true

?

?

?

true

true

?

?

true

?

true

true

?

true

?

true

?

?

?

?

true

true

?

true

true

?

?

true

4

Dalam tabel di atas, baris paling atas menunjukkan item-item yang dijual, sementara baris-baris selanjutnya menunjukkan transaksi pembelian konsumen, setiap baris mewakili satu kali transaksi. Sementara dalam kolom transaksi, kode (true) memiliki arti konsumen membeli item tersebut, sementara kode (?) berarti konsumen tidak membeli item tersebut. Data transaksi penjualan ini diolah menggunakan software WEKA versi 3.6. Untuk bisa menggunakan software ini, data yang digunakan sebagai masukan harus dalam format *.arff atau *.csv. Untuk mengganti format data dapat digunakan pengolah data Microsoft Excel untuk mengganti menjadi format *.csv dan dengan menggunakan software WEKA itu sendiri untuk mengganti menjadi format *.arff. Berikut tampilan utama WEKA 3.6.

Preprocessing Sebelum melakukan proses mining, terlebih dahulu dilakukan tahap preprocessing, yaitu merubah format data agar dapat digunakan dalam software. Berikut tampilan langkah-langkah dan hasil yang diperoleh:

5

Tampilan dengan format *.csv

Tampilan ini diperoleh dari hasil membuat data transaksi supermarket menggunakan excel, kemudian di save dengan format *.csv

Tampilan dengan format *.arff

6

Tampilan tersebut merupakan format data transaksi supermarket yang telah dirubah ke dalam format *.arff.

Tampilan preprocessing pada WEKA 3.6.

Hasil proses menggunakan algorimta FP-Growth

7

=== Run information === Scheme:

weka.associations.FPGrowth -P 2 -I -1 -N 10 -T 0 -C

0.9 -D 0.05 -U 1.0 -M 0.1 Relation:

supermarket

Instances:

4627

Attributes:

217

[list of attributes omitted] === Associator model (full training set) === FPGrowth found 16 rules (displaying top 10) 1. [fruit=t, frozen foods=t, biscuits=t, total=high]: 788 ==> [bread and cake=t]: 723

lift:(1.27) lev:(0.03)

conv:(3.35) 2. [fruit=t, baking needs=t, biscuits=t, total=high]: 760 ==> [bread and cake=t]: 696

lift:(1.27) lev:(0.03)

conv:(3.28) 3. [fruit=t, baking needs=t, frozen foods=t, total=high]: 770 ==> [bread and cake=t]: 705

lift:(1.27) lev:(0.03)

conv:(3.27) 4.

[fruit=t,

vegetables=t,

[bread and cake=t]: 746

biscuits=t,

total=high]:

815

==>

lift:(1.27) lev:(0.03)

conv:(3.26) 5. [fruit=t, party snack foods=t, total=high]: 854 ==> [bread and cake=t]: 779

lift:(1.27) lev:(0.04) conv:(3.15)

6. [vegetables=t, frozen foods=t, biscuits=t, total=high]: 797 ==> [bread and cake=t]: 725

lift:(1.26) lev:(0.03)

conv:(3.06) 7. [vegetables=t, baking needs=t, biscuits=t, total=high]: 772 ==> [bread and cake=t]: 701

lift:(1.26) lev:(0.03)

conv:(3.01) 8. [fruit=t, biscuits=t, total=high]: 954 ==> [bread and cake=t]: 866

lift:(1.26) lev:(0.04) conv:(3)

9. [fruit=t, vegetables=t, frozen foods=t, total=high]: 834 ==> [bread and cake=t]: 757

lift:(1.26) lev:(0.03)

conv:(3)

8

10. [fruit=t, frozen foods=t, total=high]: 969 ==> [bread and cake=t]: 877

lift:(1.26) lev:(0.04) conv:(2.92)

Dari hasil yang didapat menggunakan software WEKA 3.6. dihasilkan 16 rules, namun hanya ditampilkan rules yang menduduki posisi 10 besar saja. Berikut rules yang ditemukan: 1.

[fruit, frozen foods, biscuits]: 788 ==> [bread and cake]: 723 lift:(1.27) lev:(0.03) conv:(3.35)

2.

[fruit, baking needs, biscuits]: 760 ==> [bread and cake]: 696 lift:(1.27) lev:(0.03) conv:(3.28)

3.

[fruit, and

4.

baking

needs,

frozen

foods]:

770

==>

[bread

cake]:705 lift:(1.27) lev:(0.03) conv:(3.27)

[fruit, vegetables, biscuits]: 815 ==> [bread and cake]: 746 lift:(1.27) lev:(0.03) conv:(3.26)

5.

[fruit, party snack foods]: 854 ==> [bread and cake]: 779 lift:(1.27) lev:(0.04) conv:(3.15)

6.

[vegetables, and

frozen

cake]:

725

foods,

biscuits]:



797

==>

lift:(1.26)

[bread

lev:(0.03)

conv:(3.06)

7.

[vegetables, baking needs, biscuits]: 772 ==> [bread and cake]: 701 lift:(1.26) lev:(0.03) conv:(3.01)

8.

[fruit, biscuits]: 954 ==> [bread and cake]: 866 lift:(1.26) lev:(0.04) conv:(3)

9.

[fruit, vegetables, frozen foods]: 834 ==> [bread and cake]: 757

lift:(1.26) lev:(0.03) conv:(3)

10. [fruit,

frozen

foods]:

969

==>

[bread

and

lift:(1.26) lev:(0.04) conv:(2.92)

Analisis hasil perhitungan WEKA Dengan mengambil contoh rule no 1 yaitu:

9

cake]:

877

[fruit, frozen foods, biscuits]: 788 ==> [bread and cake]: 723 lift:(1.27) lev:(0.03) conv:(3.35)

Dapat disimpulkan bahwa dari beberapa departemen yang ada di supermarket, ternyata department yang paling produktif atau sering dikunjungi adalah departemen bread and cake dengan jumlah transaksi sebanyak 723 dari 4627 jumlah transaksi penjualan yang ada. Maksud dari pernyataan tersebut adalah, “ketika berbelanja, konsumen akan membeli (paling tidak) salah satu produk dari departemen bread and cake.” Dan dari 216 jenis item yang ada di supermarket, transaksi untuk item fruit, frozen foods dan biscuits sering terjadi dalam satu transaksi, yakni dalam 788 transaksi konsumen membeli ketiga item tersebut secara bersamaan. Dari hasil tersebut dapat dihitung nilai confidence-nya: confidence =

[bread and cake] [fruit, frozen foods, biscuits]

confidence =

723 = 0.91751269 ~ 0.92 788

dari perhitungan tersebut dapat disimpulkan bahwa nilai confidence dari rule tersebut adalah 0.92 atau jika dalam bentuk persentase adalah 92%. Sehingga pihak supermarket dapat menggunakan rule tersebut untuk diimplementasikan karena tingkat akurasinya mendekati 100%.

Kegunaan Hasil Dari rules yang didapatkan, maka strategi yang dapat digunakan oleh supermarket itu adalah: 1. Mengatur penempatan posisi item-item yang saling frequent dengan jarak berdekatan sehingga konsumen dapat lebih mudah berbelanja. 2. Mengatur penempatan posisi item-item yang saling frequent dengan jarak yang berjauhan dan menempatkan frequent itemset lain diantaranya,

10

sehingga peluang konsumen membeli item lain yang posisinya terletak antara item yang frequent menjadi lebih besar. 3. Menambah stok pajangan item-tem yang saling frequent, sehingga keuntungan supermarket dapat meningkat. Berdasarkan percobaan yang telah dilakukan, maka dapat ditarik beberapa kesimpulan sebagai berikut: 1. Dengan menggunakan algoritma FP-Growth dengan bantuan software WEKA 3.6.4 didapatkan hasil berupa aturan (rules) yang merupakan kumpulan frequent itemset dengan nilai confidence yang tinggi. 2. Dengan didapatkannya rules ini maka perusahaan pemasaran dapat menggunakan rules tersebut dalam membuat strategi-strategi untuk meningkatkan penjualan. 3. Hasil implementasi telah dilakukan dengan menghasilkan nilai strong confidence paling tinggi 92 %

11