ADM-03: Association Rule - Market Basket Analysis

People influence people. Nothing influences people more than a recommendation from a trusted friend. A trusted referral influences people more than the best broadcast message. A trusted referral is the Holy Grail of advertising. ~Mark Zuckerberg~
image source: Rina Piccolo [Link]

• Video: https://youtu.be/dt2N4U4xtUA

• Download dan install Orange installer dari sini: https://orangedatamining.com/download/ 
• Data (Orange & Python - mlxtend) + Script Orange: https://github.com/taudataid/eLearning/raw/master/data/ADM-03-Data-MLXTend-Orange-Script-OWS.zip
• Code Python (Google Colab - mlxtend): https://colab.research.google.com/github/taudataid/eLearning/blob/master/adm-03-Code.ipynb

Di link tersebut anda langsung bisa merubah code dan menjalankannya. Keterangan lebih lanjut di video yang disertakan. Sangat disarankan untuk membuka code dan video "side-by-side" untuk mendapatkan pengalaman belajar yang baik (Gambar dibawah). Silahkan modifikasi (coba-coba) hal lain, selain yang ditunjukkan di video untuk mendapatkan pengalaman belajar yang lebih mendalam. Tentu saja juga silahkan akses berbagai referensi lain untuk memperkaya pengetahuan lalu diskusikan di forum yang telah disediakan.

"Side-by-Side": Ilustrasi bagaimana menggunakan code dan video dalam pembelajaran di tau-data. untuk mendapatkan pengalaman belajar yang baik.

Pendahuluan

Di era industri 4.0 bisnis penjualan barang secara daring (marketplace) tumbuh secara pesat (Gambar 1). Sebut saja C2C (customer-to-customer) marketplace seperti Tokopedia, Bukalapak, Lazada, dan Shopee yang berkembang menjadi perusahaan-perusahaan startup yang sukses tumbuh berkembang bahkan menjadi perusahaan startup "unicorn". Selain C2C, e-commerce dapat juga berupa B2C (business-to-customer) seperti Bhinneka dan BliBli atau B2B (business-to-business) seperti shopify.

Gambar 1. Contoh beberapa marketplace yang berkembang di Indonesia.
image source: [Link 1, Link2].

Salah satu mekanisme dalam meningkatkan penjualan dan memenangkan kompetisi bisnis di bidang ini adalah merekomendasikan sesuatu produk yang memiliki nilai jual lebih tinggi (up-selling) atau menawarkan produk lain sehingga didapatkan transaksi lebih besar (cross-selling). Namun di jaman big data seperti saat ini terdapat ratusan ribu atau bahkan jutaan produk yang dapat direkomendasikan. Untuk membantu penentuan produk yang (paling) baik untuk direkomendasikan sebuah perusahaan kepada pelanggan, berbagai model rekomendasi yang ada di data science dapat digunakan.

Terdapat berbagai teknik model rekomendasi di data science. Content based filtering (CBF) menggunakan berbagai property/feature dari suatu produk untuk menentukan produk lain yang serupa. Feature ini dapat berupa deskripsi, metadata produk, maupun informasi visual. Cara lain untuk membuat model rekomendasi adalah dengan menggunakan informasi dari asosiasi antara produk dan-atau pelanggan (Collaborative filtering technique - CFT) atau kombinasi dari keduanya (hybrid).

Gambar 2. Berbagai model rekomendasi di Data Science.
image source: [Link].

Gambar 3 dapat digunakan untuk memperjelas perbedaan antara model rekomendasi CBF dan CFT.

Gambar 3. Perbedaan antara model rekomendasi CBF dan CFT.
image source: [Link].

Pada kesempatan kali ini kita akan membahas CFT, khususnya model-based filtering technique Association Rule atau sering juga disebut sebagai Market basket Analysis. Pertanyaan yang ingin dijawab dari model ini adalah:

1. Barang apa yang biasa dibeli pelanggan?
2. Produk apa yang paling (tidak) laku?
3. Produk apa yang biasa dibeli secara bersamaan?

Pertanyaan-pertanyaan diatas akan dijawab dengan mengamati pola belanja (cart/basket) pelanggan lewat data transaksi perusahaan (toko).

Gambar 4. Ilustrasi Permasalahan Market Basket Analysis.

Module ADM-03: Association Rule (Market Basket Analysis)

Association Rule (AR) adalah salah satu metode klasik di data mining (science) untuk mengolah data transactional (misal transaksi di pusat perbelanjaan) untuk mendapatkan rekomendasi barang-barang apa saja yang biasanya dibeli secara bersamaan. Salah satu aplikasi yang paling populer dari AR adalah Market Basket Analysis (MBA). Untuk mendapatkan asosiasi ini AR/MBA menggunakan perhitungan probablititas bersayarat sederhana seperti yang kita temukan di Statistika dasar. Aplikasi dari AR/MBA bisa berupa tata letak produk di sebuah toko agar pembeli tidak terlupa barang-barang yang perlu untuk dibeli (Gambar 5), atau promo pembelian paket produk (misal beli produk A, maka discount 10% untuk pembelian produk B).

Gambar 5. Salah satu permasalahan yang dapat diselesaikan oleh model AR/MBA.
image source: [Link]

Di literature setidaknya terdapat 3 macam model AR:

1. Association discovery (tidak terurut - yang akan dibahas di module ini)
2. Sequential pattern discovery (terurut/Sequential)
3. Similar time discovery (ada informasi waktu - misal log analysis)

AR berusaha menemukan semua himpunan ITEM (ITEMSETS) yang memiliki SUPPORT lebih besar dari MINIMUM SUPPORT, kemudian menggunakan itemsets yang signifikan untuk menghasilkan RULES yang memiliki CONFIDENCE lebih besar dari suatu MINIMUM CONFIDENCE. Rules ini akan dinilai berharga (signifikan) berdasarkan nilai LIFT-nya.

Items dan Itemsets

• Data AR berbentuk "transaksi": himpunan itemsets yang masing-masing elemen himpunannya adalah items
• Items: Bread, Milk, Coke, dll
• Itemset: {Bread, Milk}
• Contoh transaksi pada suatu hari di sebuah toko:

TID	Items
1	Bread, Milk
2	Bread, Diaper, Beer, Eggs
3	Milk, Diaper, Beer, Coke
4	Bread, Milk, Diaper, Beer
4	Bread, Milk, Diaper, Coke

Secara Formal (Ringkasan Teori AR)

• Item adalah elemen himpunan dari data, contoh: Milk,Bread,Eggs
• Itemset adalah kemungkinan subset yang dibentuk dari item, contoh:  {Milk,Bread,Eggs} atau {Milk, Eggs}.
• Frekuensi kemunculan item atau itemset dalam data disebut Support:
• Jika support > dari suatu nilai ambang (threshold) maka itemset tersebut disebut frequent itemset.
• Sebuah Rule berbentuk X⇒Y dimana X (Antecedent) dan Y (Consequent) adalah itemsets. Contoh:
• {Milk,Diaper}⇒{Beer}
• Support dari sebuah rule adalah banyaknya transaksi yang memuat X dan Y.
• s(X⇒Y)=s(X∪Y)
• Dalam association rule mining, kita ingin mencari Rules yang memiliki  support and confidence yang signifikan. 
• Nilai expected confidence tak bersyarat di AR disebut juga sebagai "lift:"
• Lift<1 dianggap "negatif" (less than expected)
  Lift = 1 : netral
• ["lift"] S. Brin, R. Motwani, J. D. Ullman, and S. Tsur. Dynamic itemset counting and implication rules for market basket data

Contoh Rule:

Mie Instant ==> Saos Sambal

Rules digunakan dalam marketing untuk membuat berbagai keputusan, beberapa contohnya:

• Letakkan kedua barang berdekatan (agar ndak lupa keduanya untuk dibeli)
• Letakkan kedua barang berjauhan (agar konsumen akan melihat-lihat barang yang lain)
• Satukan kedua barang dalam sebuah promo (promo akan jadi lebih menarik karena konsumen memang membutuhkan keduanya)
• Satukan kedua barang dengan barang lain yang kurang laku (Cross selling)
• Naikkan barang yang satu dan turunkan yang lain (teknik kompetisi dengan "toko sebelah")
• Jangan iklankan kedua barang bersamaan.
• Tawarkan promo saos dalam bentuk sachet gratis setiap membeli mie instan premium.

Rule, Support, Confidence, Lift by Example

Gambar 6. Contoh sederhana Perhitungan Support, confidence, dan rule dari sebuah rule.
image source: [Link]

Support

Support rule A==>B adalah probabilitas A dan B muncul bersamaan:
$$ Support(A==>B) = \frac{|A \wedge B|}{|T|} $$
dimana $|A\wedge B|$ adalah jumlah transaksi yang mengandung produk A dan B dan $|T|$ adalah total transaksi yang ada.

Confidence

Confidence rule A=>B adalah probabilitas bersyarat dari B jika diketahui A, atau $P(B|A)=\frac{P(A \cap B)}{P(B)}$. Di AR dihitung sebagai:
$$ Confidence(A=>B) = \frac{|A\wedge B|}{|B|}$$

Lift

Lift rule A=>B adalah sebuah ukuran seberapa lebih sering A dan B muncul bersamaan dibandingkan jika mereka saling bebas secara statistika. Jika A dan B saling bebas maka Lift(A=>B)=1 dan jika lift positif maka dikatakan A dan B berkorelasi positif dan negatif untuk sebaliknya.
Lift(A=>B) dihitung sebagai:
$$ lift(A=>B)=\frac{confidence(A=>B)}{P(B)}=\frac{P\cap B}{P(A)P(B)}$$
Perhatikan Lift bersifat simetris: Lift(A=>B) = Lift(B=>A)

Leverage

Leverage mirip dengan lift, hanya saja Leverage menghitung perbedaan (selisih instead of perbandingan seperti lift) antara frekuensi A dan B muncul bersamaan dan frekuensi A dan B jika ia independent. Nilai leverage = 0 menandakan saling bebas antara A dan B. Leverage dihitung sebagai:
$$ Leverage(A=>B)= Support(A=>B) - Support(A) \times Support(B)$$
Referensi untuk Leaverage: Piatetsky-Shapiro, G., Discovery, analysis, and presentation of strong rules. Knowledge Discovery in Databases, 1991: p. 229-248.

Rangkuman

Semua aturan diatas dengan apik dirangkum sebagai berikut:

Sumber gambar: http://rasbt.github.io/mlxtend/user_guide/frequent_patterns/association_rules/

Pemilihan Rules

Pada aplikasinya AR akan menghasilkan banyak sekali Rules dari data. Namun demikian tentu saja tidak semua rules ini akan digunakan dalam pengambilan kebijakan. Untuk mengurangi jumlah rule, sebaiknya barang-barang (sejenis) dikategorikan/kelompokkan terlebih dahulu. Kemudian akan dipilih rule-rule yang memenuhi kriteria berikut (mengapa? Silahkan diskusikan di Forum):

• Rule dengan Lift besar dan kecil.
• Items yang paling sering (dan jarang) muncul.

Prinsip Apriori (Sifat anti-monotone)

Jika sebuah itemset sering muncul, maka semua subset-nya juga pasti sering muncul. Begitupula kebalikannya juga berlaku, jika sebuah itemset jarang muncul, maka semua superset-nya pasti juga jarang muncul. Secara formal dituliskan
$$ \forall A, B : (A \subset B) => s(A) \geq s(B) $$
Atau dengan kata lain support itemset tidak akan pernah melebihi support dari subset-nya. Sifat ini menjadi sangat penting nanti untuk mengurangi komputasi (Computational Complexity) dari perhitungan rules dari data.

Algoritma Association Rules:

Walau teori dari AR cukup sederhana, namun terdapat cukup banyak algoritma di AR, diantaranya AIS, Apriori, SETM, AprioriTid, Apriori Hybrid. Kebanyakan dari algoritma ini berbeda karena perbedaan upaya untuk mengurangi komputasi. Di kesempatan ini hanya akan dibahas secara sekilas algoritma AIS dan Apriori.

Algoritma AIS

• Kandidat itemset dihasilkan dan dihitung frekuensinya seiring dengan munculnya data baru.
• Untuk setiap transaksi, ditentukan itemset besar mana yang terdapat dalam transaksi ini berdasarkan data yang ada (dan suatu nilai ambang/threshold/minimum support yang sudah ditentukan sebelumnya).
• Kandidat itemset baru yang lebih besar/panjang dihasilkan dengan memperluas itemset-itemset yang ada dengan item-tem lain di dalam transaksi yang ada.
• Kekurangan algoritma AIS adalah menghasilkan terlalu banyak kandidat itemset yang ternyata bernilai kecil.
• Lebih jelasnya dapat dilihat pada gambar berikut:

Gambar 7. Algoritma AIS.
image source: [Link].

Untuk lebih jelasnya algoritma AIS dapat juga disajikan dalam bentuk graph sebagai berikut:

Gambar 8. ilustrasi algoritma AIS dan pengaplikasian minimum support untuk mengurangi komputasi.
image source: [Link]

Algoritma Apriori

1. Kandidat itemset hanya di hitung menggunakan itemset terbesar tanpa memperhatikan data transaksi di database.
2. Itemset besar dari "pass"/proses sebelumnya digunakan untuk membentuk itemset lain dengan suatu min support/threshold tertentu (misal >1).
3. Itemsets yang tidak memenuhi min support diabaikan/hapus. Sisa itemset adalah candidate itemsets.

Gambar 9. Iustrasi algoritma Apriori.
image Source: [Link].

Referensi

[1]: J. Han, J. Pei, Y. Yin, R. Mao.Mining Frequent Patterns without Candidate Generation: A Frequent-Pattern Tree Approach. 2004.https://www.cs.sfu.ca/~jpei/publications/dami03_fpgrowth.pdf

[2]: R. Agrawal, C. Aggarwal, V. Prasad.Depth first generation of long patterns. 2000. http://www.cs.tau.ac.il/~fiat/dmsem03/Depth%20First%20Generation%20of%20Long%20Patterns%20-%202000.pdf

[3]: R. Agrawal, et al.Fast Discovery of Association Rules. 1996. http://cs-people.bu.edu/evimaria/cs565/advances.pdf