Prosiding Seminar Nasional Manajemen Teknologi IX Program Studi MMT-ITS, Surabaya 14 Pebruari 2009
PENGGALIAN POLA CLOSED SEQUENTIAL PADA BASIS DATA YANG BERTAMBAH SECARA BERTAHAP Budanis Dwi Meilani* dan Arif Djunaidy** Jurusan Teknik Informatika ITS, Surabaya 60111, email: **
[email protected], **
[email protected]
ABSTRAK Pencarian urutan yang sering muncul (pola sekuensial) adalah menemukan semua sub-urutan yang frekuensi kejadiannya dalam set urutan tidak kurang dari minimum support (frequent sub-sequence) yang ditentukan sebelumnya. Kebanyakan penelitian yang telah dilakukan pada saat ini diberlakukan pada basis data proses statik, dimana sebuah basis data yang mengalami perubahan (update) memerlukan proses penemuan kembali semua pola sekuensial yang baru dari basis data yang telah berubah. Salah satu cara untuk mengatasi pengulangan proses penemuan kembali dapat dilakukan dengan menggunakan teknik pemeliharaan urutan (maintaining sequences) pada saat terjadi perubahan basis data (database updates). Teknik tersebut merupakan suatu algoritma untuk menangani basis data yang bertambah secara bertahap (incremental) yang dikembangkan untuk pola sekuensial terutama ketika pertumbuhan urutan secara bertahap menyebabkan pembuatan pola baru dalam kaitan dengan interaksi pertumbuhan sub-urutan dari basis data asli. Proses yang dilakukan algoritma incremental adalah ketika ada penambahan basis data (database updated) maka penggalian pola dilakukan pada basis data baru yang ditambahkan, kemudian dilakukan pengujian terhadap pola yang disimpan di buffering, sehingga menghasilkan pola yang baru (gabungan pola yang lama dan pola yang baru). Pola Closed Sequential (closed sequential pattern), salah satu cara untuk mengatasi duplikasi pola pada pola sekuensial yang sudah dihasilkan. Untuk menghasilkan pola closed sequential dilakukan proses pengujian dari pola sequential. Pengujian dilakukan dengan pencarian subpola yaitu menguji apakah suatu pola yang baru ditemukan dapat diserap oleh suatu penggalian pola closed sequential dan pencarian super pola yaitu pengujian apakah pola yang ditemukan dapat menyerap beberapa pola closed sequential yang telah digali. Hasil dari penelitian ini adalah waktu komputasi yang diperlukan algoritma incremental closed sequential untuk data yang telah mengalami perubahan lebih cepat daripada waktu yang diperlukan untuk algoritma closed sequential karena proses penggalian pola tidak dilakukan pada keseluruhan basis data yang berubah, melainkan penggalian pola dilakukan pada basis data yang ditambahkan saja yang kemudian dilakukan pengujian terhadap pola yang disimpan di buffering, sehingga menghasilkan pola yang baru (gabungan pola yang lama dan pola yang baru). Kata Kunci : Penggalian Pola Close sequential, frequent sequential, pola sequential
PENDAHULUAN Pencarian urutan yang sering muncul (pola sekuensial) adalah suatu pencarian data yang penting dan juga merupakan suatu tema penelitian yang menarik dalam data mining. Jika diberikan suatu basis data urutan di mana masing-masing urutan adalah daftar transaksi yang diurut berdasarkan waktu transaksi dan masing-masing transaksi adalah satu set item, dan diberikan suatu ambang batas dukungan (support) minimum,
Prosiding Seminar Nasional Manajemen Teknologi IX Program Studi MMT-ITS, Surabaya 14 Pebruari 2009
maka pencarian pola sekuensial akan berupaya untuk menemukan semua sub-urutan yang frekuensi kejadiannya dalam set urutan tidak kurang dari minimum support (frequent sub-sequence) (Agrawal, 1995). Penemuan pola sekuensial dalam basis data adalah suatu masalah data mining yang penting. Kebanyakan penelitian yang telah dilakukan pada saat ini diberlakukan pada basis data proses static dimana sebuah basis data yang mengalami perubahan (update) memerlukan penemuan kembali semua pola sekuensial yang baru. Untuk menemukan pola yang baru, proses yang dilakukan adalah membaca kembali (scanning) keseluruhan basis data yang telah berubah (dari lama ke baru). Proses yang demikian akan menghabiskan waktu komputasi untuk pencarian kembali pola sekuensial yang baru. Kejadian ini sebenarnya tidak diinginkan untuk penggalian pola sekuensial (mine sequential pattern) terutama untuk setiap kali urutan (sequence) tumbuh atau urutan baru ditambahkan ke dalam basis data. Salah satu cara untuk mengatasi masalah tersebut, dilakukan suatu teknik untuk pemeliharaan urutan (maintaining sequences) pada perubahan basis data (database updates). Teknik tersebut merupakan algoritma untuk menangani basis data yang bertambah secara bertahap (incremental) yang dikembangkan untuk pola sekuensial terutama ketika pertumbuhan urutan secara bertahap menyebabkan pembuatan pola baru dalam kaitan dengan interaksi pertumbuhan sub-urutan dari basis data asli (Cheng, 2004). Proses yang dilakukan algoritma incremental adalah ketika ada penambahan basis data (database updated) maka pembacaan dilakukan hanya pada basis data baru yang ditambahkan, sehingga proses tersebut akan mengurangi waktu komputasi untuk pencarian kembali pola sekuensial yang baru. Salah satu permasalahan yang timbul dalam pencarian pola sekuensial adalah kemungkinan dihasilkannya jumlah pola yang eksponensial, terutama untuk urutan yang panjang dan urutan tersebut sering muncul (frequent sequence) dalam basis data. Kemungkinan beberapa sub-urutan mempunyai dukungan yang sama pada urutan yang panjang, sehingga dapat terjadi duplikasi pola. Salah satu cara untuk mengatasi duplikasi pola pada pola sekuensial, dapat dilakukan dengan mencari frequent closed subsequences, yang tidak berisi superurutan dengan dukungan yang sama sehingga dapat mencari pola closed sequential [Yan, 2003]. Suatu pola sekuensial s dikatakan closed jika tidak ada sub-pola s dengan nilai dukungan yang sama dalam basis data. Dalam mencari pola frequent closed sequential pencarian hanya dilakukan pada urutan yang sering muncul pada basis data transaksi yang hanya bersifat closed dimana tidak ada super-pola s dengan nilai dukungan yang sama dalam basis data sehingga pola yang dihasilkan lebih sedikit dari pada pola sekuensial. Pencarian pola sekuensial pada basis data yang selalu dinamis merupakan permasalahan dalam data mining. Untuk menyelesaikan permasalahan tersebut maka algoritma untuk bertambahnya data secara bertahap (Incremental) pada basis data merupakan solusi dimana proses tersebut lebih efisien terutama dapat memperkecil waktu komputasi untuk pencarian pola sekuensial yang baru. Untuk pertimbangan efektivitas dan efisiensi maka penelitian ini akan membuat algoritma untuk penggalian pola closed sequential pada basis data yang mengalami penambahan data secara bertahap (Incremental). Ide yang harus dibangun adalah dengan menggabungkan dua algoritma yaitu algoritma untuk penggalian penambahan data secara bertahap (Incremental Mining) dan algoritma Closed Sequential Pattern sehingga diharapkan dapat memperkecil waktu pencarian pola.
ISBN : 978-979-99735-7-3 C-5-2
Prosiding Seminar Nasional Manajemen Teknologi IX Program Studi MMT-ITS, Surabaya 14 Pebruari 2009
METODA Dalam bab ini dijelaskan mengenai desain algoritma pencarian pola sequential terhadap adanya penambahan data secara bertahap yang meliputi sistem secara keseluruhan, desain modul pencarian pola closed sequential dan modul pencarian pola closed sequential terhadap adanya penambahan data bertahap.
closed desain desain secara
Sistem Secara Keseluruhan Pencarian Pola Closed Sequential Terhadap Adanya Penambahan Data Secara Bertahap Sistem pencarian pola closed sequential terhadap adanya penambahan data secara bertahap terdiri dari dua modul, antara lain: (a) modul pencarian pola closed sequential, dan (b) modul pencarian pola closed sequential terhadap adanya penambahan data secara bertahap. Tabel customer sequence SDB, min_sup dan
pencarian pola closed sequential
Tabel customer sequence SDB’
pola closed sequential dan pola semi closed sequential
pencarian pola closed sequential terhadap adanya penambahan data secara bertahap
Gambar 1. Blok Diagram Sistem Pencarian Pola Closed Sequential terhadap adanya penambahan data secara bertahap
Blok diagram sistem keseluruhan pencarian pola closed sequential terhadap adanya penambahan data secara bertahap ditunjukkan pada Gambar 1. Masukan dari sistem pencarian pola closed sequential terhadap adanya penambahan data secara bertahap ini dibatasi berupa tabel transaksi customer sequence yang terdiri dari customer ID dan customer sequence, minimum support dan faktor dimana 1. Faktor digunakan untuk menghasilkan buffer semi closed sequential pattern yaitu pola closed sequential yang hampir sering muncul, dengan menggunakan pendekatan statistics-based. Teknik ini menggunakan lower min_sup dengan buffer ratio 1. Sedangkan hasil luaran sistem adalah pola closed sequential dan pola semi closed sequential. Pola closed sequential adalah pola yang sesungguhnya dihasilkan sedangkan pola semi closed sequential adalah pola yang akan disimpan di buffer untuk proses selanjutnya apabila ada penambahan data secara bertahap. Pencarian Pola Closed Sequential Sistem pencarian pola closed sequential terdiri dari dua algoritma, antara lain: (a) algoritma pencarian pola closed sequential, dan (b) algoritma subroutine Bideku.
ISBN : 978-979-99735-7-3 C-5-3
Prosiding Seminar Nasional Manajemen Teknologi IX Program Studi MMT-ITS, Surabaya 14 Pebruari 2009
Tabel customer sequence SDB min_sup dan
pencarian pola closed sequential
pola closed sequential dan pola semi closed sequential
Subroutine Bideku
Gambar 2. Blok Diagram Modul Pencarian Pola Closed Sequential
Blok diagram modul pencarian pola closed sequential ditunjukkan pada Gambar 2. Masukan modul pencarian pola closed sequential adalah tabel transaksi customer sequence SDB yang terdiri dari customer ID dan customer sequence, minimum support threshold min_sup, dan faktor dimana 1. Sedangkan hasil luaran sistem adalah pola closed sequential dan pola semi closed sequential. 1. 2. 3. 4. 5. 6. 7. 8. 9.
FCS = 0 dan SCS = 0 F1 = scan basis data SDB untuk menemukan frequent dan semi frequent 1 sequence FOR (masing-masing frequent dan semi frequent 1 sequence dalam F1) SDBf1 = membangun pseudo proyeksi basis data FOR (perlakukan masing-masing frequent dan semi frequent 1 sequence f1 dalam F1 sebagai prefix) IF (menggunakan metode BackScan pruning untuk memeriksa jika dapat pruning, jika tidak) BEI = menghitung banyaknya backward extension item memanggil subroutine bideku(SDBf1 , f1, min_sup, , BEI, FCS,SCS) return
Gambar 3. Algoritma Pencarian Pola Closed Sequential
Algoritma di atas menunjukkan algoritma mencari pola closed sequential. Pertama pemberian nilai awal nol untuk FCS atau frequent closed sequential dan SCS atau semi frequent closed sequential. Kemudian scan basis data SDB sekali untuk menemukan frequent dan semi frequent satu sequences F1. Frequent satu sequences (urutan yang sering muncul) adalah sequences satu item yang supportnya tidak kurang dari minimum_support, sedangkan Semi Frequent satu sequences (urutan yang hampir sering muncul) adalah sequences satu item yang supportnya tidak kurang dari minimum_support * . Setelah menemukan frequent dan semi frequent satu sequences F1 kemudian membangun pseudo proyeksi basis data untuk masing-masing frequent dan semi frequent satu sequences SDBf1. Langkah selanjutnya perlakukan masingmasing frequent dan semi frequent satu sequences fi dalam F1 sebagai prefix dan menggunakan metoda BackScan pruning untuk memeriksa jika dapat pruned. Jika tidak, maka proses dilanjutkan dengan menghitung banyaknya backward-extension-items, dan kemudian memanggil subroutine bideku(Sp_SDB, Sp, min_sup, , BEI, FCS.SCS). Masukan algoritma subroutine bideku adalah proyeksi basis data Sp_SDB, sebuah prefix sequence Sp, minimum support, nilai dari faktor , nilai backward extension item BEI. Sedangkan hasil luaran sistem adalah pola closed sequential FCS dan pola semi closed sequential SCS.
ISBN : 978-979-99735-7-3 C-5-4
Prosiding Seminar Nasional Manajemen Teknologi IX Program Studi MMT-ITS, Surabaya 14 Pebruari 2009
1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14.
LFI = scan proyeksi basis data Sp_SDB untuk menemukan lokal item frequent dan semi frequent FEI = menghitung banyaknya forward extension item untuk LFI IF ( (BEI + FEI) = 0 ) IF (support Sp < min_sup) SCS = SCS {Sp} ELSE FCS = FCS {Sp} FOR ( untuk masing – masing i dalam LFI ) Spi = menumbuhkan Sp dalam lexicographical order untuk mendapatkan prefix baru SDBSpi = membangun pseudo proyeksi basis data untuk prefix yang baru FOR ( untuk masing-masing prefix baru) IF (periksa jika dapat pruning, jika tidak) BEI = menghitung backward extension item (Spi, SDBSpi) memanggil dirinya sendiri bideku (SDBSpi , Spi, min_sup, , BEI, FCS, SCS)
Gambar 4. Algoritma Subroutine Bideku
Subroutine bideku(Sp_SDB, Sp, min_sup, , BEI, FCS,SCS) secara berulang memanggil dirinya sendiri dan bekerja sebagai berikut: Untuk prefix S p, scan proyeksi basis data Sp_SDB sekali untuk menemukan lokal frequent item LFI, kemudian menghitung banyaknya forward-extension items FEI. Jika tidak ada backwardextension-item BEI maupun forward-extension-item FEI, dan nilai support Sp < minimum support maka tambahkan output Sp sebagai Semi Closed Sequence SCS, jika tidak maka tambahkan output Sp sebagai Frequent Closed Sequence FCS. Proses selanjutnya menumbuhkan Sp dalam lexicographical order pada masing-masing i dalam lokal frequent item LFI untuk mendapatkan prefix baru Spi dan membangun pseudo proyeksi database untuk prefix yang baru SDBSpi. Kemudian untuk masing-masing prefix baru Spi, diperiksa jika dapat pruned, jika tidak, menghitung banyaknya backward-extension-items BEI dan memanggil bideku (SDBSpi , Spi, min_sup, , BEI, FCS,SCS). Metoda BackScan Pruning Algoritma pola Closed Sequential adalah algoritma yang menemukan frequent sequence yang kemudian memeriksa pola frequent Sequential yang ditemukan apakah closed untuk menghasilkan himpunan lengkap non-redundant frequence sequence. Walaupun closure checking schema atau proses pemeriksaan apakah closed dapat mendorong kearah hasil set yang lebih ringkas, tetapi tidak bisa meningkatkan efisiensi penggalian. FOR (masing-masing sequence yang ada pada basis data SDB) Mencari Sp_SDB_awal untuk item pada Sp dan dihitung supportnya FOR (masing-masing Sp_SDB awal untuk item pada Sp) IF(ada item diawal item Sp yang mempunyai support sama dengan item Sp) return (dipruning) ELSE return(tidak dipruning)
Gambar 5. Algoritma BackScan Pruning
ISBN : 978-979-99735-7-3 C-5-5
Prosiding Seminar Nasional Manajemen Teknologi IX Program Studi MMT-ITS, Surabaya 14 Pebruari 2009
Menghitung Backward-Extension-Items Menghitung Backward-Extension-Items (BEI) adalah menghitung item yang berada di belakang prefix sequence Sp yang supportnya tidak kurang atau sama dengan support prefix sequence Sp. Menghitung Forward-Extension-Items Menghitung Forward-Extension-Items (FEI) adalah menghitung item yang berada di awal prefix sequence Sp yang supportnya tidak kurang dari support prefix sequence Sp. Menghitung Lokal Item Frequence Lokal Item Frequence (LFI) adalah menghitung item yang berada di belakang prefix sequence Sp yang supportnya tidak kurang dari minimum support. Pencarian Pola Closed Sequential Terhadap Adanya Penambahan Data Secara Bertahap Sistem pencarian pola closed sequential terhadap adanya penambahan data secara bertahap terdiri dari tiga algoritma, antara lain: (a) algoritma pencarian pola closed sequential terhadap adanya penambahan data secara bertahap, (b) algoritma subroutine Incrementalku dan (c) algoritma subroutine gabung. pola closed sequential dan pola semi closed sequential
Tabel customer sequence SDB’ min_sup dan
pencarian pola closed sequential terhadap adanya penambahan data secara bertahap
Subroutine Incrementalku
Subroutine Gabung
Gambar 6. Blok Diagram modul Pencarian Pola Closed Sequential terhadap adanya Penambahan Data Secara Bertahap
Blok diagram modul pencarian pola closed sequential terhadap adanya penambahan data secara bertahap ditunjukkan pada gambar 6. Untuk penambahan data secara bertahap dibatasi pada penambahan appended yaitu penambahan pada sequence yang sudah ada. Masukan modul pencarian pola closed sequential terhadap adanya penambahan data secara bertahap adalah tabel transaksi customer sequence SDB’ yaitu tabel customer sequence yang bertambah secara bertahap terdiri dari customer ID dan customer sequence, minimum_support, , pola closed sequential FCS dan pola semi closed sequential SCS. Sedangkan hasil luaran sistem adalah pola closed sequential FCS’ dan pola semi closed sequential SCS’.
ISBN : 978-979-99735-7-3 C-5-6
Prosiding Seminar Nasional Manajemen Teknologi IX Program Studi MMT-ITS, Surabaya 14 Pebruari 2009
1. 2. 3. 4. 5. 6.
7. 8.
F1 = scan basis data yang mengalami penambahan (SDB + SDB’) untuk menemukan frequent dan semi frequent 1 sequence SDB lama =SDB yang akan mengalami penambahan data FOR (masing-masing frequent dan semi frequent 1 sequence dalam F1) SDBf1 = membangun pseudo proyeksi basis data FOR (perlakukan masing-masing frequent dan semi frequent 1 sequence f1 dalam F1 sebagai prefix) IF (menggunakan metode BackScan pruning untuk memeriksa jika dapat pruning, jika tidak) memanggil subroutine Incrementalku(SDBf1 , f1, min_sup, ) return Gambar 7. Algoritma Pencarian Pola Closed Sequential Terhadap Adanya Penambahan Data Secara Bertahap
Algoritma di atas menunjukkan algoritma mencari pola closed sequential terhadap adanya penambahan data secara bertahap. Langkah pertama melakukan scan basis data yang mengalami penambah (SDB + SDB’) untuk mencari frequent dan semi frequent item 1 sequence F1. Frequent satu sequences (urutan yang sering muncul) adalah sequences satu item yang supportnya tidak kurang dari minimum_support, sedangkan Semi Frequent satu sequences (urutan yang hampir sering muncul) adalah sequences satu item yang supportnya tidak kurang dari minimum_support * dan support kurang dari minimum_support. Setelah menemukan frequent dan semi frequent satu sequences F1, maka membaca SDB lama adalah SDB yang akan mengalami penambahan data. Kemudian untuk masing-masing frequent dan semi frequent item 1 sequence F1 sebagai prefix dilakukan pengujian apakah dapat dipruning, jika tidak dapat dipruning melakukan pemanggilan subroutine Incrementalku(SDBf1, f1, min_sup, ). Masukan algoritma subroutine Incrementalku adalah proyeksi basis data Sp_SDB, sebuah prefix sequence Sp, minimum support, nilai dari faktor . Sedangkan hasil luaran sistem adalah pola closed sequential FCS dan pola semi closed sequential SCS. 1.
2. 3. 4. 5. 6. 7. 8. 9. 10.
LFI = scan proyeksi basis data Sp_SDB untuk menemukan lokal item frequent dan semi frequent IF (Sp terdapat pada SDB lama) Lakukan penyesuaian nilai support IF (support Sp >= 1 ) memanggil subroutine Gabung(Sp, support, min_sup, , FCS, SCS) FOR ( untuk masing – masing i dalam LFI ) Spi = menumbuhkan Sp dalam lexicographical order untuk mendapatkan prefix baru SDBSpi = membangun pseudo proyeksi basis data untuk prefix yang baru FOR ( untuk masing-masing prefix baru Spi) memanggil dirinya sendiri Incrementalku (SDBSpi , Spi, min_sup, , FCS, Gambar 8. Algoritma subroutine Incrementalku SCS)
Algoritma di atas menunjukkan algoritma subroutine Incrementalku. Langkah pertama melakukan scan basis data Sp_SDB untuk menemukan lokal item frequent dan
ISBN : 978-979-99735-7-3 C-5-7
Prosiding Seminar Nasional Manajemen Teknologi IX Program Studi MMT-ITS, Surabaya 14 Pebruari 2009
semi frequent (LFI). Kemudian dilakukan pengujian Sp apakah terdapat pada SDB lama, Jika Ya lakukan penyesuaian nilai support. Jika nilai suport >= 1 maka memanggil subroutine gabung(Sp, support, min_sup, , FCS, SCS). Untuk masingmasing i pada LFI menumbuhkan Sp dalam lexicographical order untuk mendapatkan prefix baru dan membangun pseudo proyeksi basis data Sp sebagai prefix baru. Untuk masing-masing prefix baru memanggil dirinya sendiri subroutine Incrementalku(Sp_SDB, Sp, min_sup, , FCS, SCS). Subroutine Gabung(Sp, support, min_sup, , FCS, SCS), masukan algoritma subroutine Gabung adalah Sp, nilai support Sp, minimum support, nilai dari faktor . Sedangkan hasil luaran sistem adalah pola closed sequential FCS dan pola semi closed sequential SCS. 1. IF (pola Sp ada pada FCS atau SCS) 2. lakukan penyesuaian support pola Sp pada FCS atau SCS 3. IF pola Sp pada SCS support >= minimum_support 4. pindahkan pola Sp pada FCS 5. ELSE 6. IF pola Sp terdapat pada SDB 7. tambahkan nilai supportnya 8. IF (pola Sp merupakan superpola pada FCS atau SCS) 9. tambahkan Sp pada FCS atau SCS dan hapus subpola nya 10. ELSE 11. IF (pola Sp merupakan subpola pada FCS atau SCS) 12. return 13. ELSE 14. IF pola Sp supportnya >= min_sup 15. tambahkan pola Sp pada FCS 16. ELSE 17. IF pola Sp supportnya >= min_sup * 18. tambahkan pola Sp pada SCS Gambar 9. Algoritma subroutine Gabung
Algoritma di atas menunjukkan algoritma subroutine Gabung. Langkah pertama melakukan pengujian apakah pola Sp terdapat pada FCS atau SCS, jika ya lakukan penyesuaian support pada pola FCS atau SCS. Jika pola Sp pada SCS supportnya >= min_support maka pindahkan pola Sp pada FCS. Jika pola Sp tidak terdapat pada FCS atau SCS maka lakukan pengujian apakah pola SP terdapat pada SDB, jika ya lakukan penambahan nilai support. Lakukan pengujian untuk Sp apakah merupakan superpola pada FCS atau SCS, jika Ya tambahkan Sp pada FCS atau SCS dan hapus subpolanya. Jika tidaka lakukan pengujian apakah merupakan subpola pada FCS atau SCS, Jika Ya abaikan. Jika Tidak maka lakukan pengujian apakah pola Sp support >= min_sup, jika ya tambahkan pola Sp pada FCS, jika suppoort >= min_sup* maka tambahkan pola Sp pada SCS. HASIL DAN DISKUSI Sesuai dengan scenario, pelaksanaan dan hasil uji coba maka analisis hasil uji coba dikelompokkan berdasarkan konfigurasi basis data dengan menggunakan algoritma Closed Sequential dan algoritma Incremental Closed Sequential. Analisis hasil uji coba dengan algoritma Closed Sequential, pengujian dilakukan menggunakan
ISBN : 978-979-99735-7-3 C-5-8
Prosiding Seminar Nasional Manajemen Teknologi IX Program Studi MMT-ITS, Surabaya 14 Pebruari 2009
basis data A dan B dengan min_support yang bervariasi menunjukkan bahwa dengan nilai minimum support yang tinggi akan menghasilkan waktu komputasi lebih cepat dibanding dengan min_support yang nilainya lebih rendah. Analisis hasil uji coba dengan algoritma Incremental Closed Sequential, pengujian pertama-tama dilakukan dengan menggunakan basis data tanpa adanya penambahan basis data dengan menggunakan algoritma Closed Sequential dan algoritma Incremental Closed Sequential. Hasil uji coba mengatakan bahwa waktu yang dihasilkan dengan minimum support yang bervariasi menunjukkan bahwa algoritma Closed Sequential menghasilkan waktu lebih cepat daripada algoritma Incremental Closed Sequential dikarenakan untuk algoritma Incremental Closed Sequential selain mencari frequent Closed Sequential juga mencari Semi Frequent closed Sequential yang nantinya akan disimpan di buffer. Pengujian kedua dilakukan dengan menggunakan basis data yang bertambah 25%, 50% dan 80%. Pengujian penambahan basis data dengan algoritma Incremental Closed Sequential dengan minimum support yang bervariasi. Dengan penambahan basis data tersebut menggunakan algoritma Incremental Closed Sequential akan menghasilkan waktu komputasi lebih cepat dari pada menggunakan algoritma Closed Sequential. KESIMPULAN Penggalian Closed Sequential pattern yang diharapkan dari penelitian ini menghasilkan pola Frequent Closed Sequential yang tidak mengandung duplikasi. Dengan menggunakan algoritma Closed Sequential Pattern dan algoritma Incremental Closed Sequential Pattern dibuktikan bahwa pola yang dihasilkan adalah sama. Waktu komputasi yang diperlukan oleh algoritma incremental closed sequential untuk data yang telah mengalami perubahan lebih cepat daripada waktu yang diperlukan untuk algoritma closed sequential karena proses penggalian pola tidak dilakukan pada keseluruhan basis data yang berubah, melainkan proses penggalian pola dilakukan pada basis data yang ditambahkan saja yang kemudian digabungkan dengan pola yang sudah tersimpan di buffering (gabungan pola yang lama dan pola yang baru) sehingga menghasilkan pola closed sequential yang baru. DAFTAR PUSTAKA F. Masseglia, P. Ponceret M. Teisseire, 2002, Incremental Mining of Sequential Pattern in Large Databases, Universite de Versailles 45 des Etats-Unis 78035 Versailles Cedex, France. Hong Cheng, Xifeng Yan, Jiawei Han, 2004, IncSpan: Incremental Mining of Sequential Pattern in Large Database, Departement of Computer Science University of illiosi at Urbana-Champaign, Illinois, U.S.A. Jianyong Wang and Jiawei Han, 2004, BIDE: Efficient Mining of Frequent Closed Sequences, Departement of Computer Science University of illiosi at UrbanaChampaign, Illinois, U.S.A. R. Agrawal and R. Srikant, 1995, Mining Sequential Pattern, IBM Almaden Research Center 650 Harry Road, San Jose, CA 95120 S. Parthasarathy, M. J. Zaki, M. Ogihara, S. Dwarkadas, 1999, Incremental and Interactive Sequence Mining, Computer Science Dept., U. of Rochester, Rochester. Xifeng Yan, Jiawei Han, Ramin Afshar, 2004, CloSpan: Closed Sequential Pattern in Large Datasets, Departement of Computer Science University of illiosi at Urbana-Champaign, Illinois, U.S.A.
ISBN : 978-979-99735-7-3 C-5-9