PENGGUNAAN METODE MARKET BASKET ANALYSIS UNTUK MENINGKATKAN KEMAMPUAN SEARCH ENGINE ONLINE BUKU TUGAS AKHIR PADA PERPUSTAKAAN UK PETRA

oleh:Gregorius S. Budhi1 ; Ibnu Gunawan2 ; Ferry Yuwono3

1) Dosen UK Petra Jurusan Teknik InformatikaEmail: greg@petra.ac.id

2) Dosen UK Petra Jurusan Teknik InformatikaEmail: ibnu@petra.ac.id

3) Alumni UK Petra Jurusan Teknik Informatika

ABSTRAKAplikasi Search Engine Online untuk buku tugas akhir pada perpustakaan UK Petra hanya dapat menyajikan daftar judul buku tugas akhir yang bagain abstraknya mengandung kata - kata yang dicari. Dengan mengaplikasikan metode Text Mining, peneliti mencoba meningkatkan kemampuan Search Engine tersebut. Harapannya agar Search Engine dapat pula menemukan judul - judul Tugas Akhir yang ber-asosiasi dengan kata - kata yang dicari, walaupun pada abstrak buku tersebut tidak mengandung kata - kata yang dicari.Pada aplikasi ini digunakan metode Keyword-Based Association Analysis sebuah metode Text Mining yang dikembangkan dari metode Market Basket Analysis. Algortima Apriori dari Market Basket Analysis digunakan untuk menggali data dalam bentuk Compact Transaction menjadi rule - rule asosiasi. Compact Transaction didapat dari pemrosesan awal terhadap teks abstrak TA menggunakan Algoritma Porter Stemmer for Bahasa Indonesia. Rule - rule asosiasi yang dihasilkan memberikan informasi asosiasi antar keyword dari sekumpulan abstrak TA yang diproses. Sorting list judul TA yang berasosiasi didasarkan atas simililarity judul tersebut dengan keyword - keyword yang dicari menggunakan rumus Minimum Distance dari Hierarchical Clustering.Dari hasil pengujian dapat disimpulkan bahwa dengan penerapan metode Keyword-Based Association Analysis, Search Engine dapat pula menyajikan daftar judul TA yang bagian abtraknya berasosiasi dengan kata - kata yang dicari.

Kata kunci:Text Mining, Keyword-Based Association Analysis, Market Basket Analysis, Algoritma

Apriori, Association Rules, Minimum Distance, Search Engine Online

1. PendahuluanSearch Engine Online adalah sebuah alternatif yang diberikan oleh perpustakaan

Universitas Kristen Petra untuk mencari koleksi buku laporan Tugas Akhir, selain untuk

mencari koleksi buku lainnya. Layanan search engine tersebut hanya dapat melakukan

pencarian berdasarkan judul, nama penulis, abstrak dan kata kunci (keyword).

Kelemahan dari Search Engine ini adalah, dia hanya dapat menampilkan daftar judul

buku tugas akhir yang secara explisit mengandung kata yang dicari pada bagian judul,

nama pengarang, abstrak dan keyword-nya. Buku - buku tugas akhir yang memiliki

1

topik sejenis atau asosiasi dengan kata yang dicari, namun tidak mengandung kata

tersebut didalamnya, tidak dapat ditampilkan pada hasil pencarian.

Penulis dengan menggunakan dua buah metode Text Mining yaitu Keyword-Based

Association Analysis, sebuah metode yang dikembangkan dari metode Market Basket

Analysis, dan Text Clustering mencoba meningkatkan kemampuan Search Engine

Online perpustakaan UK Petra agar dapat pula menampilkan daftar judul buku laporan

TA yang secara implisit memiliki 'hubungan' atau asosiasi dengan kata yang dicari.

2. Teori Penunjang2.1. Knowledge Discovery (Data Mining)Data Mining atau KDD adalah proses untuk menemukan interesting knowledge dari

sejumlah besar data yang disimpan baik di dalam databases, data warehouses atau

tempat penyimpanan informasi lainnya[3].

2.2. Text Mining : Keyword-Based Association AnalysisKeyword-Based Association Analysis, sebuah metode Text Mining yang dikembangkan

dari Market Basket Analysis, merupakan sebuah analisa yang mengumpulkan

keywords atau terms (istilah) yang sering muncul secara bersamaan dan kemudian

menemukan hubungan asosiasi dan korelasi di antara keywords atau terms itu[3].

Seperti halnya metode data mining yang lain, sebelumnya association analysis perlu

melakukan pre-processing terhadap text data dengan cara parsing, stemming,

removing stopwords, dan sebagainya. Setelah itu baru menjalankan algoritma

association mining. Di dalam sebuah document database, setiap dokumen dapat

dianggap sebagai sebuah transaksi, sedangkan sekumpulan keywords di dalam

document dapat dianggap sebagai sekumpulan items di dalam sebuah transaksi.

Sehingga pada database akan mempunyai format sebagai berikut[3]: {document_id,

a_set_of _keywords}. Format seperti ini biasa disebut format Compact Transaction.

2.3. Association Rule MiningAssociation rule mining adalah suatu prosedur untuk mencari hubungan antar item

dalam suatu data set yang ditentukan[3]. Association Rule Mining meliputi dua tahap:

a. Mencari kombinasi yang paling sering terjadi dari suatu itemset (frequent itemset).

b. Meng-generate Association Rule dari frequent itemset yang telah dibuat

sebelumnya.

Umumnya ada dua ukuran kepercayaan (interestingness measure) yang digunakan

dalam menentukan suatu association rule, yaitu Support dan Confidence[3].

2

2.4. Algoritma Apriori untuk Menemukan Frequent ItemsetsApriori adalah suatu algoritma untuk melakukan pencarian frequent itemsest untuk

mendapatkan association rules. Sesuai dengan namanya, algoritma ini menggunakan

prior knowledge mengenai frequent itemset properties yang telah diketahui

sebelumnya, untuk memproses informasi selanjutnya. Apriori menggunakan

pendekatan secara iterative yang disebut juga sebagai level-wise search dimana k-

itemset digunakan untuk mencari (k+1)-itemset[1].

2.5. Hierarchical Cluster pada Text MiningHierarchical Cluster menggunakan pendekatan berbasis set (set-based approach).

Root dari hirarkinya adalah sebuat set untuk semua koleksi dokumen, dan Leaf-nya

adalah set - set yang berisi sebuah dokumen saja. Teknik pengelompokan yang

digunakan berbasis pada kesamaan (similarity) dari keyword - keyword yang ada pada

dua buah dokumen[7]. Ada beberapa cara yang dapat digunakan untuk mengukur

jarak (distance) atara dua cluster, salah satunya adalah rumus berikut ini[3]:

Minimum Distance: dmin(Ci, Cj) = minpCi,p'Cj |p - p'| ........................ (1)

Dimana: |p - p'| adalah jarak dari 2 point obyek di dalam dua Cluster yang

berbeda Ci dan Cj.

3. Desain Sistem

Gambar 1: DFD Level 1 untuk Sistem Text Mining

3

Pada paper ini penulis hanya membahas tentang tahap Proses Generate Association

Rules dan Proses Search Keyword. Sementara itu untuk tahap Pre-processing Abstrak

TA dibahas tersendiri dalam paper oleh penulis yang sama, dengan judul "Algoritma

Porter Stemmer For Bahasa Indonesia untuk Pre-Processing Text Mining berbasis

metode Market Basket Analysis”.

3.1. Tahap Proses Generate Association RulesDesain dari proses ini dapat dilihat pada gambar 2. Tahap proses ini terdiri dari dua

subproses yaitu subproses Generate Frequent Itemsets dengan Apriori dan subproses

Generate Association Rules dari Frequent Itemsets.

1. Subproses Generate Frequent Itemsets memproses input data berupa data dari

tabel transaksi dan minimum support count dari administrator, untuk menghasilkan

output data frequent itemsets yang disimpan pada tabel Frequent Itemset.

Algoritma yang digunakan untuk mendapatkan Frequent Itemset adalah algortima

AprioriTID yang diciptakan oleh Agrawal dan Srikant pada tahun 1994[1]. Isi tabel

transaksi dapat dilihat pada gambar 3.

2. Pada subproses Generate Association Rule, Frequent itemsets dari tabel

diproses untuk menghasilkan data output berupa rule - rule asosiasi, dan disimpan

pada tabel association rules. Untuk memproses rule - rule asosiasi, administrator

perlu menentukan minimum confidence terlebih dahulu. Untuk meng-generate rule

asosiasi ini digunakan prosedur Ap-Genrules yang diciptakan oleh Agrawal dan

Srikant, tahun 1994[1].

Gambar 2: DFD Level 2 Proses Generate Association Rules

Tahap Proses Generate Association Rule adalah aplikasi berbasis Windows 2000 ke

atas, dan dibangun menggunakan software kompilasi Delphi 7.

4

Gambar 3: Isi Tabel Transaksi untuk input proses Generate Frequent Itemset

3.2. Tahap Proses Search KeywordsTahap ini didisain dalam bentuk aplikasi berbasis Web dan dibangun dengan

pemrograman web PHP3 menggunakan software Dreamweaver MX.

Mula - mula inputan dari user yang berupa string dikenai proses Parsing, yaitu memilah

string tersebut kata per kata. Selanjutnya dilakukan proses Stemming dan Stopwords

Removal, sehingga yang tersisa dari inputan user adalah keyword - keyword saja.

Pemrosesan string inputan user ini sama dengan tahap pre-processing sistem, dan

dibahas tersendiri dalam paper yang ditulis oleh penulis yang sama dengan judul

"Algoritma Porter Stemmer For Bahasa Indonesia untuk Pre-Processing Text Mining

berbasis metode Market Basket Analysis ". Desain dari proses ini dapat dilihat pada

gambar 4.

5

Gambar 4: DFD Level 2 Proses Search Keywords

Ada dua tahap pada proses pencarian abstrak TA, yaitu:

a. Tahap Pertama, pencarian abstrak TA yang mengandung keyword - keyword

inputan user. Pada tahap ini keyword inputan user dibandingkan dengan tabel

transaksi, yang berisi nomor TA dan keyword - keyword pada abstrak TA tersebut,

bila ada maka judul TA akan ditampilkan pada user. Daftar judul TA ini diurutkan

secara descending, bobot yang digunakan adalah banyaknya macam keyword user

yang terkandung didalam abstrak TA itu ( dalam tabel transaksi).

b. Tahap kedua adalah pencarian abstrak TA yang berasosiasi dengan keyword -

keyword inputan user. Pada tahap ini keyword dari user dibadingkan dengan sisi

premis (IF) dari rule - rule asosiasi yang disimpan pada tabel association rules. Bila

sebuah rule telah diketemukan, maka semua kata yang berada pada sisi konklusi

(THEN) rule tersebut akan disimpan pada penyimpan sementara. Hal ini terus

dilakukan berulang - ulang sampai semua rule asosiasi telah dibandingkan.

Selanjutnya daftar kata yang berasosiasi dengan keyword - keyword user itu, kata

yang berada pada sisi konklusi rule, dibandingkan dengan isi tabel transaksi, bila

ada maka judul TA akan ditampilkan pada user. Daftar judul TA ini diurutkan

secara descending, bobot yang digunakan adalah derajat asosiasi (confidence)

dari keyword - keyword yang ada pada abstrak TA terhadap keyword inputan user.

3.2.1. Mengukur derajat asosiasi keyword abstrak TA dan keyword User

6

Metode yang digunakan untuk menentukan bobot pengurutan data judul TA yang ber-

asosiasi dengan keyword - keyword dari user diadopsi dari metode Hierarchical Cluster

untuk Text Mining. Dalam hal ini kumpulan keyword dari user dan juga kumpulan

keyword pada abstrak - abtrak TA yang ada dianggap sebagai sekumpulan Cluster Of

Keywords. Cluster yang berisi keyword - keyword dari user dianggap sebagai cluster

pusat, kemudian diukur derajat asosiasi antara cluster ini dengan cluster - cluster yang

lain (abstrak TA) menggunakan rumus Minimum Distance. Untuk menghitung nilai

jarak antara dua point keyword pada Cluster-User-Keyword dan Cluster-Abstrak-TA

digunakan rumus:

|p - p'| = 1 - Confidence(Rule: IF Ki THEN Kj) ............................................ (2)

Dimana: Ki adalah keyword inputan dari user dan Kj adalah keyword pada

abstrak TA.

Rule yang valid adalah bila sisi premis rule tersebut berisi keyword dari user dan sisi

konklusi berisi keyword pada dokumen. Untuk lebih jelasnya, dapat dilihat ilustrasi

pada gambar 5.

Gambar 5: Ilustrasi perhitungan derajat asosiasi

3.3. Desain DatabaseDisain database dapat dilihat pada gambar 6. Tabel tabelnya adalah sebagai berikut:

- Tabel TA_Skripsi_Civitas, TA_Civitas dan TA_Skripsi didapat dari tabel database

yang telah ada pada perpustakaan UK Petra. Ketiga tabel ini berisi data - data

buku laporan TA semua jurusan di UK Petra.

7

- Tabel TA_Master_Jurusan, TA_Rule, TA_If dan TA_Then digunakan untuk

menyimpan rule - rule asosiasi yang dihasilkan sistem.

- Tabel Transaksi untuk menyimpan keyword - keyword dari abstrak TA dalam

bentuk Compact Transaction, setelah dilakukan tahap pre-processing. Pada tabel -

tabel ini istilah 'Keyword' diganti dengan 'Kata Penting' untuk membedakannya

dengan field 'Csubject_Keyword' pada tabel TA_Skripsi yang berisi 'kata kunci' dari

laporan TA tersebut.

- Tabel TA_Master_Kata_Penting digunakan untuk menyimpan daftar Keyword /

Kata Penting. Tabel TA_Stop untuk menyimpan daftar Stopword yang ada.

Gambar 6: ERD database yang digunakan pada sistemUntuk penyimpan data digunakan software database MS SQL Sever 2000.

4. PengujianPengujian dengan dilakukan menggunakan spesifikasi Hardware dan Software berikut:

Processor : Pentium IV 1.5 GHz

Memory : 256 MB

Operating System : MS Windows XP

Database: : MS SQL Server 2000

Hasil pengujian dapat dilihat pada gambar 7 sampai dengan gambar 11.

8

Gambar 7: Tampilan Rule Asosiasi yang dihasilkan

Gambar 8: Web Search Engine TA, halaman awal

Gambar 9: Hasil Search untuk TA yang mengandung User’s Keywords

Gambar 10: Hasil Search untuk TA yang berasosiasi dengan User’s Keywords

Gambar 11: Halaman Web Detail data buku TA (judul, ruang lingkup,

abstrak, dll)

5. Kesimpulan Semakin tinggi batasan minimum support count yang ditentukan maka association

rules yang dihasilkan semakin sedikit sehingga menurunkan kuantitas dari keyword

rekomendasi yang dihasilkan namun lebih meningkatkan asosiasi di antara user’s

keyword dengan keyword rekomendasi.

9

Bila dipilih jurusan yang tidak sesuai dengan topik yang diharapkan user, pencarian

judul TA yang berasosiasi dengan Keyword User akan menghasilkan daftar yang

‘missleading’. Hal ini karena banyak kata - kata yang sama namun memiliki arti

berbeda untuk jurusan – jurusan yang berbeda.

Metode Keyword-Based Association Analysis dapat digunakan untuk mendapatkan

judul – judul TA yang ‘direkomendasikan’ (memiliki asosiasi) dengan keyword –

keyword inputan dari user.

Daftar Pustaka1. Agrawal, Rakesh, Ramakrishnan Srikant, 1994, Fast Algorithms for Mining

Association Rules, Proceeding Of The 1994 International Conference Very Large

Data Bases, Santiago, Chile, September 1994.

2. Dhillon, Inderjit S., Dharmendra S. Modha, 2001, Concept Decompositions for

Large Sparse Text Data using Clustering, Machine Learning, vol. 42, no. 1, pp.

143-175, January 2001.

3. Han, Jiawei, Micheline Kamber, 2001, Data Mining : Concepts and Techniques.

Morgan Kaufmann.

4. Hand, David, Heikki Mannila, Padhraic Smyth, 2001, Priciples Of Data Mining, The

MIT Press.

5. Tala, Fadillah Z., 2003, A Study of Stemming Effects on Information Retrieval in

Bahasa Indonesia, Institute for Logic, Language and Computation Universeit Van

Amsterdam.

6. Tan, A., 1999, Text mining: The state of the art and the challenges, In Proceedings

of the Pacific Asia Conference on Knowledge Discovery and Data mining,

PAKDD'99 workshop on Knowledge Discovery from Advanced Databases.

7. Wakil, Mohammed El, 2002, Introducing Text Mining, 9th Scientific Conference for

Information Systems and Information Technology (ISIT02), Feb. 2002.

Gregorius S. Budhi, memperoleh gelar S.T. dari Teknik Elektro ITATS Surabaya

tahun 1993. Tahun 2001 memperoleh gelar M.T. dari Teknik Informatika ITS Surabaya.

Saat ini sebagai staf pengajar tetap Teknik Informatika UK Petra, Surabaya.

Ibnu Gunawan, memperoleh gelar S.T. dari Teknik Elektro UK Petra Surabaya tahun

2002. Saat ini sebagai staf pengajar tetap Teknik Informatika UK Petra, Surabaya.

Ferry Yuwono, memperoleh gelar S.Kom dari Teknik Informatika UK Petra Surabaya

tahun 2005. Saat ini sebagai staf di departemen IT sebuah perusahaan di Surabaya.

10