asosiasi data mining menggunakan algoritma-libre

Upload: jefry-andres-sinaga

Post on 02-Jun-2018

221 views

Category:

Documents


0 download

TRANSCRIPT

  • 8/11/2019 Asosiasi Data Mining Menggunakan Algoritma-libre

    1/8

    1

    ASOSIASIDATA MINING MENGGUNAKAN ALGORITMA

    FP-GROWTHUNTUKMARKET BASKET ANALYSIS

    Fathimah Fatihatul, Atje Setiawan, Rudi RosadiJurusan Matematika FMIPA Universitas Padjadjaran

    Jl. Raya Bandung-Sumedang km 21 Jatinangor 45363. Telp/Fax:022-7794696

    ABSTRAK

    Data transaksi penjualan perusahaan pemasaran yang besar menghasilkan knowledge baru

    yang berguna untuk pengambilan keputusan para decision makerperusahaan tersebut. Dari gudang

    data tersebut dapat dilakukan pengolahan sehingga menghasilkan informasi yang tersembunyi dan

    bermanfaat sehingga dapat disebut sebagai data mining. Informasi baru tersebut dapat

    menganalisis buying habits dari konsumen yang nantinya dapat dimanfaatkan untuk strategi

    pemasaran.

    Terdapat beberapa metode dalam mengolah data mining, salah satunya adalah association

    analysis. Dalam association analysis terdapat beberapa algoritma yang dapat digunakan, salahsatunya adalah algoritmafp-growth. Penelitian ini menghasilkan association rules yang ditemukan

    dengan bantuan software WEKA 3.6.4. Penelitian ini menggunakan data sekunder berupa data

    transaksi penjualan sebuah supermarket dalam suatu periode waktu.

    Hasil dari penelitian ini berupa aturan (rules) yang merupakan kumpulanfrequent itemset

    dengan nilai confidence yang tinggi. Hasil implementasi telah dilakukan dengan menghasilkan

    nilai strong confidence paling tinggi 92 %.

    Kata Kunci : Data Mining, association rules,, Algoritma FP-Growth, frequent itemset,

    support, confidence

    ABSTRACTThe large amount of transaction data of the retail company produce new knowledge

    which is useful to decision process. From the data warehouse can be processed to produce hiddenand useful information that can be referred to as data mining. The new information analysing

    buying habits from consumer so that can be used for marketing strategy.

    There are several methods of data mining to process large amounts of data, one of which

    is association analysis. In association analysis, there are several algorithms that can be used, one

    of which is fp-growth algorithm. This research resulting the association rules which founded by

    support of software WEKA 3.6.4. This research using secondary data thas is transaction data of

    the retail company within a particular period time.

    Result of this research is the rules which are the association of frequent itemset with high

    confidence value. The result have been made which resulting value of highest strong confidence

    92%.

    Keywords: Data Mining, association rules,, FP-Growth algorithm, frequent itemset, support,

    confidence.

    1. PENDAHULUAN

    Bidang ilmu pengetahuan, bisnis dan pemerintahan telah melahirkan tumpukan data yang

    sangat melimpah. Tumpukan data ini yang akhirnya dikumpulkan dan diolah oleh kemampuanteknologi informasi menjadi beberapa pengetahuan baru yang dapat dimanfaatkan. Namun

    metoda analisis dan pengolahan data yang ada, masih kesulitan dalam menangani data dalam

    jumlah besar. Sementara, kebutuhan akan informasi dari gudang data ini memaksa untuk lahirnya

    sebuah teknologi baru yang dapat mengolah data dalam jumlah besar. Maka lahirlah data mining,

    sebuah teknologi baru yang menjawab kebutuhan ini.

  • 8/11/2019 Asosiasi Data Mining Menggunakan Algoritma-libre

    2/8

    2

    Sebuah perusahaan pemasaran dapat mengumpulkan data transaksi dengan cepat sehingga

    menghasilkan data yang sangat besar. Pertumbuhan data yang pesat itu kadang dibiarkan begitu

    saja dan tidak digunakan. Dengan data mining atau lebih tepatnyaMarket Basket Analysis (MBA),data yang banyak itu dapat diolah sehingga didapatkan informasi tersembunyi yang akan

    menghasilkan knowledge yang berguna untuk pengambilan keputusan para decision maker

    perusahaan pemasaran tersebut.

    MBA 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 diperlakukan pada datayang besar seperti misalnya data transaksi sebuah supermarketbesar.

    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 algoritmaApriori, FP-Growth, dan CT-PRO yang dimana ketiga algoritma

    tersebut memiliki kelebihan dan kekurangan masing-masing. Dalam dokumen penelitian ini

    penulis akan menggunakan algoritma FP-Growth.

    2. LANDASAN TEORI

    2.1 Data

    Data merupakan sekumpulan fakta yang nantinya akan menjadi sebuah informasi penting

    apabila diperlakukan dengan proses tertentu. Informasi yang didapatkan harus sesuai dengan

    kebutuhan dan harus dipastikan bahwa informasi tersebut memiliki kualitas yang baik. Adabeberapa faktor yang mempengaruhi kualitas dari sebuah informasi, yaitu keakuratan, kerelevanan,

    tepat waktu dan penyajiannya. Informasi yang nanti didapatkan atau sering disebut dengan

    knowledge, harus memiliki nilai yang baik. Informasi ini akan digunakan untuk penentuan

    keputusan dan kebijakan serta langkah apa yang akan sebaiknya dilakukan selanjutnya, jadi proses

    dalam mendapatkan informasi ini haruslah menggunakan proses dan teknologi yang dapat

    dipercaya kebenarannya.

    2.2 Data MiningData Mining adalah sebuah teknologi baru yang memiliki potensi sangat besar dalam

    penggalian informasi yang tersembunyi. Data mining juga sering didefinisikan sebagai proses

    ekstraksi informasi prediktif tersembunyi dari database yang sangat besar. Teknologi ini

    memungkinkan sebuah perusahaan untuk lebih proaktif dalam penyusunan strategi yang efektif

    dan juga dalam pengambilan keputusan berdasarkan perilaku dan tren masa depan yang dapat

    diprediksi oleh proses data mining.

    Secara umum, data mining memiliki istilah populer yaitu Knowledge Discovery from

    Databases atau disingkat KDD.

    2.3 Jenis-jenis Data Mining Menurut Fungsinya

    Data mining dibagi menjadi beberapa jenis menurut dari fungsinya (Atje Setiawan, 2009),

    yaitu:

    a. Konsep atau kelas descriptionb. Association Analysisc. Klasifikasi dan Prediksi

    d. Cluster Analysis

    e. Outlier Analysis

    f. Evaluation Analysis

    2.4 Association RuleAssosiation 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.

  • 8/11/2019 Asosiasi Data Mining Menggunakan Algoritma-libre

    3/8

    3

    Dalam menentukan suatu Association Rule umumnya terdapat dua ukuran kepercayaan

    (interestingness measure), yaitu supportdan confidence. Kedua ukuran ini akan digunakan untuk

    interesting association rules dengan dibandingkan dengan batasan yang telah ditentukan. Batasaninilah yang terdiri dari minsup dan minconf.

    Assosiation Rule Mining adalah suatu prosedur untuk mencari hubungan antar item dalam

    suatu dataset. Dimulai dengan mencarifrequent itemset, yaitu kombinasi yang paling sering terjadi

    dalam suatu itemsetdan 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 darirumus berikut :

    Support(A) =Jumlah transaksi yang mengandung item A

    Total transaksi(2.1)

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

    Support(A,B) = P (A B) = Jumlah transaksi yang mengandung A dan BTotal 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 (AB) = P (B|A) =Jumlah transaksi yang mengandung A dan B

    Jumlah transaksi yang mengandung A(2.3)

    2.5 Market Basket AnalysisMarket 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

    itemsetyang lain (data mining concept and technique, Jiawei Han).

    Market Basket berdasarkan kumpulan item yang dibeli oleh konsumen dalam sebuahtransaksi. 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 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 konsumenmelaluiMarket Basket Analysis sehingga dapat meningkatkan penjualan perusahaan tersebut.

    2.6 AlgoritmaFP-GrowthAlgoritma FP-Growth merupakan salah satu alternatif algoritma yang cukup efektif untuk

    mencari himpunan data yang paling sering muncul (frequent itemset) dalam sebuah kumpulan data

  • 8/11/2019 Asosiasi Data Mining Menggunakan Algoritma-libre

    4/8

    4

    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-Growthini merupakan salah satu solusi dari algoritma apriori yang memakan waktu yang sangat lama

    karena harus melakukan pattern matching yang secara berulang-ulang. Sedangkan dalam proses

    Algoritma FP-Growth terdapat banyak kelebihan yang terbukti sangat efisien karena hanya

    dilakukan pemetaan data atau scan 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 frequentitemsetdari susunan FP-Tree yang telah terbentuk.

    3. METODE PENELITIAN

    3.1 Data

    Dalam penelitian ini akan digunakan data mentah yaitu sebuah data transaksi penjualan

    sebuah supermarket dalam suatu periode waktu. Data sekunder ini terdiri dari 4627 jumlahtransaksi penjualan dengan 216 jenis item.

    Tabel 1 Sampel Data

    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.

    Bread Spices Biscuits Tea Deodorant Canned

    fruit

    Cheese Breakfast

    food

    Coffee . . .

    .

    Beef

    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

    true ? true ? ? ? ? ? ? ?

    ? ? ? ? ? ? ? true true ?

    ? ? true ? ? ? ? ? ? ?

    true ? true ? ? ? true ? ? true

    true ? true true true ? true true ? true

    ? ? true ? ? ? true ? ? ?

    :

    :

    ? ? ? ? ? ? ? ? ? ?

  • 8/11/2019 Asosiasi Data Mining Menggunakan Algoritma-libre

    5/8

    5

    3.2 Metodologi Penelitian

    Penelitian ini akan dilakukan dengan tahap-tahap yang mengikuti proses Knowledge

    Discovery from Databases (KDD) sebagai berikut:

    1. Data Cleaning

    2. Data Integration

    3. Data Selection

    4. Data Transformation

    5. Data Mining

    6. Pattern Evaluation

    7. Knowledge Presentation

    3.3 Pencarian Aturan Asosiasi Menggunakan AlgoritmaFP-GrowthProses pencarianfrequent itemsetdengan menggunakan algoritma FP-Growth akan dilakukan

    dengan cara membangkitkan struktur data tree atau disebut dengan FP-Tree. Metode FP-Growth

    untuk menghasilkanfrequent item melalui pembangunan struktur pohon keputusan dibagi menjadi

    tiga tahapan utama, yaitu :1. Tahap pembangkitan conditional pattern base

    2. Tahap pembangkitan conditional FP-Tree

    3. Tahap pencarianfrequent itemset.

    4. HASIL DAN PEMBAHASAN

    4.1 ImplementasiSoftwareData transaksi penjualan ini diolah menggunakan software WEKA versi 3.6.4. Untuk bisa

    menggunakan software ini, data yang digunakan sebagai masukan harus dalam format *.arffatau

    *.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.4.

    Gambar 1. Tampilan Utama WEKA 3.6.4

    4.2 PreprocessingSebelum 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:

  • 8/11/2019 Asosiasi Data Mining Menggunakan Algoritma-libre

    6/8

    6

    Gambar 2. Data dengan format *.csv

    Gambar 3. Data dengan format *.arff

    Gambar 4. Preprocessing

  • 8/11/2019 Asosiasi Data Mining Menggunakan Algoritma-libre

    7/8

    7

    4.3 Hasil AlgoritmaFP-Growth

    Gambar 5. Hasil

    Dari hasil yang didapat menggunakan software WEKA 3.6.4 dihasilkan 16 rules dan

    ditampilkan 10 rules yang paling strong. 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, baking needs, frozen foods]: 770 ==> [bread and cake]: 705

    lift:(1.27) lev:(0.03) conv:(3.27)

    4. [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, frozen foods, biscuits]: 797 ==> [bread and cake]: 725

    lift:(1.26) 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 cake]: 877 lift:(1.26) lev:(0.04)

    conv:(2.92)

    4.4 Kegunaan Hasil

    Dari rules yang didapatkan, maka strategi yang dapat digunakan oleh perusahaan pemasaran

    (swalayan) yaitu :

    1. Mengatur penempatan posisi item-item yang saling frequent dengan jarak berdekatan

    sehingga konsumen dapat lebih mudah berbelanja.

  • 8/11/2019 Asosiasi Data Mining Menggunakan Algoritma-libre

    8/8

    8

    2. Atau dapat pula dengan mengatur penempatan posisi item-item yang saling frequent

    dengan jarak yang berjauhan dan menempatkan frequent itemset lain diantaranya,

    sehingga peluang konsumen membeli item lain yang posisinya terletak antara item yangfrequentmenjadi lebih besar.

    5. KESIMPULAN DAN SARAN

    Berdasarkan penelitian yang telah dilakukan sebelumnya, 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 confidencepaling tinggi 92 %

    Saran dari hasil penelitian ini adalah :

    1. Penelitian selanjutnya dapat menggunakan data yang lebih besar lagi sehingga rules

    yang dihasilkan lebih beragam dan lebih berguna untuk pengambilan keputusan.

    Semakin besar data semakin berguna informasi yang dihasilkan.

    2. Penelitian selanjutnya juga bisa mencoba menggunakan algoritma data mining lain

    sehingga dapat dicari algoritma yang paling efisien dan efektif .

    6. DAFTAR PUSTAKA

    Borgelt, Christian. 2005. An Implementation of the FP-Growth Algorithm, (Online),

    http://fuzzy.cs.uni-magdeburg.de/~borgelt/(diakses 28 Juni 2011).

    Bouckaert, Remco., dkk. 2010. WEKA Manual for Version 3-6-2, (Online),

    http://kent.dl.sourceforge.net/project/weka/dokumentation/3.6.x/ (diakses 5 Agustus2011).

    Coenen, F. 2003. The LUCS-KDD FP-Growth Association Rule Mining Algorithm, (Online),

    http://www.cxc.liv.ac.uk/~frans/(diakses 28 Juni 2011).

    Erwin. 2009.Analisis Market Basket Dengan Algoritma Apriori dan FP-Growth, (Online),

    http://uppm.ilkom.unsri.ac.id/ (diakses 5 Juli 2011).

    J. Han and M. Kamber.Data Mining: Concepts and Techniques. Morgan Kaufmann, 2000.

    Setiawan Abdullah, Atje. 2009.Introduction Data Mining. Slide disajikan dalam kuliah Kapita

    Selekta Sistem Informasi bagi mahasiswa matematika di Jatinangor, Matematika UNPAD

    BANDUNG, Jatinangor.

    http://fuzzy.cs.uni-magdeburg.de/~borgelt/http://kent.dl.sourceforge.net/project/weka/dokumentation/3.6.x/http://www.cxc.liv.ac.uk/~frans/http://uppm.ilkom.unsri.ac.id/http://uppm.ilkom.unsri.ac.id/http://www.cxc.liv.ac.uk/~frans/http://kent.dl.sourceforge.net/project/weka/dokumentation/3.6.x/http://fuzzy.cs.uni-magdeburg.de/~borgelt/