Apa algoritma Apriori?

Diperkenalkan pada tahun 1994 oleh Rakesh Agrawal dan Ramakrishnan Srikant (tautan berada di luar ibm.com) nama 'Apriori' mengakui pengetahuan sebelumnya tentang frequent itemset yang digunakan algoritma dalam komputasi. Algoritma menjalankan iterasi di atas data untuk mengidentifikasi k-itemset, yang berarti k item yang sering terjadi bersama. Algoritma kemudian menggunakan k-itemsets untuk mengidentifikasi item k+1. Algoritma Apriori bergantung pada insight bahwa menambahkan item ke grup yang sering dibeli hanya akan membuatnya lebih jarang dibeli, bukan lebih sering. Proses ini bergantung pada properti Apriori yang menyatakan bahwa jika sebuah itemset sering muncul dalam sebuah kumpulan data, maka semua subsetnya juga harus sering muncul. Sebaliknya, jika itemset diidentifikasi sebagai jarang, maka semua supersetnya dianggap jarang.

Algoritma Apriori dapat diterapkan pada semua jenis kumpulan data, terutama yang dihasilkan oleh database transaksional dan sering digunakan untuk analisis keranjang pasar untuk mendukung sistem rekomendasi. Misalnya, saat menggunakan platform ecommerce yang menjual pakaian dan sepatu, seorang pembeli mencari sepatu dan memutuskan untuk menambahkan sepasang sepatu formal berwarna hitam ke keranjang belanjanya. Pembeli kemudian memperhatikan bahwa antarmuka merekomendasikan item lain untuk dibeli, seperti kaus kaki. Salah satu cara kerja sistem rekomendasi ini adalah mempelajari pola pembelian pelanggan dan mengaitkan barang-barang yang memiliki riwayat kemungkinan dibeli bersamaan.

Salah satu keuntungan terbesar menggunakan algoritma Apriori adalah kesederhanaan dan kemampuan beradaptasi. Namun, algoritma Apriori tidak seefisien saat menangani kumpulan data besar. Proses multi-iterasi pembuatan kandidat itemset dapat menjadi mahal secara komputasi dan intensif memori. Apriori sering dikombinasikan dengan teknik lain untuk mengurangi masalah ini.

Fungsi Apriori diintegrasikan ke dalam banyak bahasa pemrograman populer termasuk Python, Java, dan R, sehingga menghasilkan aturan asosiasi yang berkualitas bersama dengan frequent itemset yang mudah diintegrasikan ke dalam aplikasi atau sistem yang sudah ada.

Setiap langkah utama dalam algoritma Apriori adalah untuk mengidentifikasi itemset dan semua superset yang mungkin, mencari yang paling sering muncul untuk membuat aturan asosiasi.

Algoritma pertama-tama mengidentifikasi item unik, kadang-kadang disebut sebagai 1-itemset, dalam kumpulan data beserta frekuensinya. Kemudian, algoritma menggabungkan item yang muncul bersama dengan probabilitas di atas ambang batas yang ditentukan ke dalam kandidat itemset dan menyaring itemset yang jarang muncul untuk mengurangi biaya komputasi pada langkah selanjutnya. Proses ini, yang dikenal sebagai penambangan frequent itemset, hanya mencari itemset dengan frekuensi yang berarti.

Menggunakan properti Apriori, algoritma menggabungkan lebih lanjut itemset yang sering untuk membentuk itemset yang lebih besar. Kombinasi itemset yang lebih besar dengan probabilitas yang lebih rendah dipangkas. Ini makin mengurangi ruang pencarian dan membuat perhitungan lebih efisien.

Algoritma mengulangi langkah 1 dan 2 hingga semua frequent itemset memenuhi probabilitas ambang batas yang ditentukan dihasilkan secara menyeluruh. Setiap iterasi menghasilkan asosiasi yang lebih kompleks dan komprehensif dalam itemset.

Setelah Apriori membuat itemset, kekuatan asosiasi dan hubungan yang dihasilkan dapat diselidiki.

Algoritma Apriori menggunakan metrik dukungan, kepercayaan, dan lift untuk menentukan kriteria operasinya dan meningkatkan efisiensi kinerja.

Dukungan didefinisikan sebagai rasio berapa kali suatu item muncul dalam transaksi terhadap jumlah total transaksi. Jadi, metrik ini mendefinisikan probabilitas kemunculan setiap item dalam transaksi. Logika yang sama dapat diperluas ke itemset.

$S\left({\mathrm{adalah}}_A\right)=\frac{Occ\left({\mathrm{adalah}}_A\right)}{TotalTransactions}$

di mana IA_adalah item A, Occ(_IA) adalah jumlah kemunculan item A, dan S(_IA ) = dukungan dari item A

Misalnya, di toko retail, 250 dari 2000 transaksi dalam sehari mungkin termasuk pembelian apel. Menggunakan rumus:

$S\left({\mathrm{adalah}}_{Apples}\right)=\frac{250}{2000}=\mathrm{0,125}$

Hasil ini menyiratkan ada kemungkinan 12,5% apel dibeli hari itu.

Anda dapat menunjukkan ambang batas dukungan minimum yang diperlukan saat menerapkan algoritma Apriori. Artinya item atau itemset apa pun dengan dukungan kurang dari dukungan minimum yang ditetapkan akan dianggap jarang.

Metrik kepercayaan mengidentifikasi probabilitas item atau itemset yang terjadi dalam itemset bersama-sama. Misalnya, jika ada dua item dalam suatu transaksi, keberadaan satu item diasumsikan mengarah ke yang lain. Item atau kumpulan item pertama adalah anteseden, dan yang kedua adalah konsekuensinya. Dengan demikian, kepercayaan didefinisikan sebagai rasio jumlah transaksi yang memiliki anteseden dan konsekuen, dengan jumlah transaksi yang hanya memiliki anteseden. Skenario ini direpresentasikan sebagai:

$C(A,B)=\frac{Occ(A\cap B)}{Occ\left(A\right)}$

di mana A adalah anteseden, B adalah konsekuen, dan C(A,B) adalah keyakinan bahwa A mengarah ke B.

Dengan memperluas contoh sebelumnya, asumsikan terdapat 150 transaksi di mana apel dan pisang dibeli secara bersamaan. Keyakinan dihitung sebagai:

$C(Apples,Bananas)=\frac{150}{250}=\mathrm{0,6}$

Hasil ini menunjukkan kemungkinan 60% bahwa pembelian apel kemudian mengarah pada pembelian pisang. Demikian pula, dengan asumsi total 500 transaksi untuk pisang, maka keyakinan bahwa pembelian pisang mengarah pada pembelian apel dihitung sebagai:

$C(Bananas,Apples)=\frac{150}{500}=\mathrm{0,3}$

Di sini, hanya ada kemungkinan 30% bahwa pembelian pisang mengarah pada pembelian apel.

Meskipun kepercayaan adalah ukuran kemungkinan yang baik, itu bukan jaminan hubungan yang jelas antara item. Nilai kepercayaan mungkin tinggi karena alasan lain. Untuk alasan ini, ambang batas kepercayaan minimum diterapkan untuk menyaring kemungkinan asosiasi yang lemah saat menambang dengan aturan asosiasi.

Lift adalah faktor yang menyebabkan kemungkinan item A mengarah ke item B lebih tinggi daripada kemungkinan item A. Metrik ini mengukur kekuatan hubungan antara A dan B. Metrik ini dapat membantu menunjukkan apakah ada hubungan nyata antara item dalam itemset atau apakah item-item tersebut dikelompokkan bersama secara kebetulan. 

$L(A,B)=\frac{C(A,B)}{S\left(A\right)}$ 


Di mana _LA,B adalah lift untuk item A yang mengarah ke item B, C_A,B adalah keyakinan bahwa item A mengarah ke item B, _SA adalah dukungan untuk item A.

Untuk contoh di atas, kita dapat melihat bahwa: 

$L(Apples,Bananas)=\frac{\mathrm{0,6}}{\mathrm{0,125}}=\mathrm{4,8}$

Nilai lift yang tinggi menunjukkan bahwa kemungkinan apel dan pisang dibeli bersamaan adalah 4,8 kali lebih tinggi daripada apel yang dibeli sendiri. Juga, dapat diamati bahwa: 

$L(Bananas,Apples)=\frac{\mathrm{0,3}}{\mathrm{0,25}}=1.2$

Nilai lift yang rendah di sini menunjukkan bahwa pembelian pisang yang mengarah ke pembelian apel mungkin hanya kebetulan.

Dalam banyak kasus, menerapkan pendekatan brute-force (tautan berada di luar ibm.com) untuk menghitung ambang dukungan dan kepercayaan untuk setiap aturan dan kemudian memangkas aturan yang tidak memenuhi ambang batas dapat menjadi penghalang komputasi. Untuk membuat penerapan algoritma Apriori menjadi lebih efisien, algoritma ini sering kali dikombinasikan dengan teknik-teknik association rule mining lainnya. Dua yang paling umum adalah algoritma FP-growth (tautan berada di luar ibm.com) dan variannya FP-max untuk mengurangi kendala memori dan komputasi. Algoritma Apriori juga dapat dikombinasikan dengan decision trees, di mana algoritma Apriori mengidentifikasi itemset yang sering, dan teknik decision trees membantu mengidentifikasi aturan asosiasi.

Varian populer lainnya dari algoritma Apriori adalah Dynamic Itemset Counting (DIC) (tautan berada di luar ibm.com) yang mulai menghitung itemset potensial lebih awal, tanpa menunggu semua transaksi dicatat. DIC membagi kumpulan data menjadi segmen yang lebih kecil dan memproses setiap segmen secara terpisah. Segmentasi ini memungkinkan penghentian lebih awal ketika algoritma tidak dapat mengidentifikasi frequent itemset, tetapi partisi data juga membantu mengurangi biaya komputasi secara signifikan.

Algoritma Apriori juga dapat berguna dalam aplikasi kecerdasan buatan berbasis pembelajaran tanpa pengawasan seperti algoritma pengelompokan ketika data mendukungnya. Algoritma membantu mengidentifikasi hubungan dan asosiasi antara entitas yang tampaknya independen, mengelompokkannya ke dalam kluster yang memungkinkan.

Menemukan dan mengelompokkan itemset memiliki banyak kegunaan dan algoritma Apriori terkadang disebut sebagai hal pertama yang dicoba oleh para penambang data karena keserbagunaannya. Kita akan melihat beberapa contoh penggunaan umum di industri yang berbeda.

Salah satu kegunaan paling umum dari algoritma Apriori adalah melakukan analisis keranjang pasar. Peritel menganalisis riwayat pembelian pelanggan dan mengoptimalkan cara penataan toko dengan menempatkan barang yang sering dibeli di dekat satu sama lain atau di rak yang sama. Platform ecommerce menggunakan algoritma Apriori untuk mempelajari hubungan berbasis produk berdasarkan preferensi pengguna dan analisis penambangan pola pembelian untuk menciptakan sistem rekomendasi pelanggan yang efisien. Jenis analisis yang sama dapat digunakan untuk mengoptimalkan pembelian layanan, misalnya, memilih kursus pelatihan dari katalog, atau merekomendasikan jenis pertanggungan lain saat memilih asuransi.

Algoritma Apriori dapat digunakan untuk menemukan aturan asosiasi yang kuat antara gejala dan penyakit untuk meningkatkan efisiensi diagnosis dan menyusun rencana perawatan yang ditargetkan. Misalnya, pasien mana yang kemungkinan besar akan mengidap diabetes (tautan berada di luar ibm.com) atau peran yang dimainkan oleh diet atau gaya hidup dalam penyakit (tautan berada di luar ibm.com). Ini juga dapat membantu mengidentifikasi faktor-faktor yang terkait dengan reaksi obat yang berbahaya.

Algoritma Apriori juga berlaku dalam database nontransaksional. Analis data akan sering menggunakan Apriori untuk penambangan penggunaan web, untuk menganalisis data clickstream, dan untuk menginterpretasikan perilaku pengguna.

Aplikasi umum lainnya dari algoritma Apriori adalah untuk mengidentifikasi pola penipuan dalam transaksi keuangan. Mengidentifikasi pola pembelian tertentu sebagai kemungkinan penipuan memungkinkan lembaga keuangan bertindak cepat untuk menangguhkan transaksi atau menghubungi pemegang rekening.