Apa algoritma Apriori?

Diperkenalkan pada tahun 1994 oleh Rakesh Agrawal dan Ramakrishnan Srikant namanya, 'Apriori', menyatakan pengetahuan sebelumnya tentang kumpulan item yang sering terjadi, yang digunakan algoritma dalam komputasi. Algoritma menjalankan iterasi pada data untuk mengidentifikasi k-itemset, yang berarti k item yang sering terjadi bersama. Algoritma kemudian menggunakan k-itemset untuk mengidentifikasi kumpulan 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 kumpulan item sering muncul dalam sebuah kumpulan data, semua subsetnya juga harus sering muncul. Sebaliknya, jika kumpulan item diidentifikasi sebagai jarang muncul, maka semua supersetnya dianggap jarang.

Algoritma Apriori dapat diterapkan pada semua jenis kumpulan data, terutama yang dihasilkan oleh basis data transaksional dan sering digunakan untuk analisis keranjang pasar untuk mendukung sistem rekomendasi. Misalnya, saat menggunakan platform e-commerce yang menjual pakaian dan sepatu, seorang pembeli mencari sepatu dan memutuskan untuk menambahkan sepasang sepatu resmi 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 item 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(I_A\right)=\frac{Occ\left(I_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(I_{Apples}\right)=\frac{250}{2000}=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}=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}=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{0.6}{0.125}=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{0.3}{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 untuk menghitung batas ambang dukungan dan keyakinan untuk setiap aturan dan kemudian memangkas aturan yang tidak memenuhi ambang batas, dapat menghalangi komputasi. Untuk menjadikan penerapan algoritma Apriori lebih efisien, algoritma ini sering kali dikombinasikan dengan berbagai teknik penambangan aturan asosiasi lainnya. Dua teknik yang paling umum adalah algoritma pertumbuhan FP dan variannya FP-max untuk mengurangi kendala memori dan komputasi. Algoritma Apriori juga dapat dikombinasikan dengan struktur keputusan, di mana algoritma Apriori mengidentifikasi kumpulan item yang sering terjadi dan teknik struktur keputusan membantu mengidentifikasi aturan asosiasi.

Varian algoritma Apriori lainnya yang populer adalah Dynamic Itemset Counting (DIC) yang mulai menghitung kumpulan item potensial lebih awal, tanpa menunggu pencatatan semua transaksi. DIC membagi kumpulan data menjadi segmen yang lebih kecil dan memproses setiap segmen secara terpisah. Segmentasi ini memungkinkan penghentian awal ketika algoritma tidak dapat mengidentifikasi kumpulan item yang sering muncul, 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 ini membantu mengidentifikasi hubungan dan asosiasi antara entitas yang tampaknya independen, mengelompokkannya ke dalam klaster 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 akan menderita penyakit diabetes atau peran diet atau gaya hidup dalam penyakit. Algoritma ini juga dapat membantu mengidentifikasi 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.