Event Detection Banjir pada Microblogging Twitter dengan Algoritma DBSCAN

Event Detection Banjir pada Microblogging Twitter dengan Algoritma DBSCAN (Flood Event Detection in Twitter Microblogging with DBSCAN Algorithm) 1

Rendy, 2Yudi Wibisono, 3Rosa Ariani Sukamto

Program Studi Ilmu Komputer, Fakultas Pendidikan Matematika dan Ilmu Pengetahuan Alam, Universitas Pendidikan Indonesia Jl. Dr. Setiabudhi No. 229 Bandung 40154 Jawa Barat – Indonesia [email protected], [email protected], [email protected]

Abstrak- Twitter merupakan sebuah situs microblogging yang populer dibandingkan dengan situs microblogging lainnya. Twitter mampu mengirimkan pesan pendek 140 karakter. Isi dari pesan yang dikirim atau dinamakan tweet umumnya berisi laporan mengenai kejadian sehari-hari. Pada paper ini, penulis memfokuskan penelitian untuk mendeteksi adanya banjir melalui Twitter. Teknik yang dapat digunakan untuk memanfaatkan hal tersebut salah satunya dengan teknik clustering. Metode clustering yang digunakan yaitu metode Density-based Clustering dengan Algoritma DBSCAN. Metode Density-based Clustering melakukan pengelompokkan berdasarkan tingkat kepadatan dari suatu tweet. Cluster akan dipisahkan berdasarkan area yang memiliki kepadatan tinggi dengan area yang memiliki kepadatan rendah. Setiap cluster merepresentasikan satu event. Dari setiap event yang terdeteksi diambil informasi mengenai lokasi banjir dan deskripsi banjir tersebut menggunakan Named Entity Recognition (NER). Deteksi event menggunakan algoritma DBSCAN memberikan hasil yang baik, terbukti dengan nilai evaluasi cluster yang besar (0.86) dari data sebanyak 5354 tweet dengan jumlah event yang terdeteksi sebanyak 24 event. Kata Kunci : Event Detection, Clustering, DBSCAN, Twitter, Named Entitiy Recognition Abstract— Twitter is the popular microblogging site's than others. Twitter allows user to send short messages contains 140 characters. The Twitter post, called tweets, typically contains about real-life events. In this paper, the authors focus on the study to detect flooding through Twitter. The technique can be used is clustering. The authors uses Density-based Clustering with DBSCAN algorithm to group tweets. Density-based clustering methods perform clustering based on the density of a tweet. Clusters are separated by areas that have a high density area with a low density. Each cluster represents a single event. Each of detected event, extract information about the location and description of the flood using Named Entity Recognition (NER). Event detection using DBSCAN gives good results as evidenced by the large cluster evaluation value (0.86) of 5354 tweets with 24 number of events detected. Keywords: Event Detection, Clustering, DBSCAN, Twitter, Named Entitiy Recognition

I. PENDAHULUAN 1.1 Latar Belakang Twitter merupakan sebuah situs microblogging yang paling populer dibandingkan dengan situs microblogging lainnya. Hal ini terlihat dari jumlah pengguna Twitter yang mencapai 105 juta pada April 2010 dengan jumlah posting 55 juta tweet per hari [1]. Twitter merupakan media sosial yang digunakan oleh banyak orang untuk dapat terhubung dengan orang-orang disekelilingnya dan seluruh dunia melalui komputer dan perangkat mobile. Twitter sebagai salah satu situs microblogging mampu mengirimkan sebuah pesan pendek (140 karakter) tentang apa yang mereka lakukan, apa yang ada di sekeliling mereka, kejadian yang sedang terjadi, dan hal lainnya yang dapat dilihat oleh semua orang. Pesan tersebut biasa disebut dengan tweet. Oleh karena itu, Twitter dikategorikan sebagai microblogging service. Microblogging merupakan sebuah bentuk blog dimana penggunanya dapat mengirimkan sebuah pesan teks (status update) yang singkat. Indonesia merupakan negara ketiga penghasil tweet terbesar dengan jumlah enam juta tweet per hari [2]. Ini bisa menjadi potensi informasi yang sangat besar untuk dimanfaatkan. Misalnya, untuk mendeteksi adanya bencana banjir. Twitter menyediakan sumber informasi yang begitu besar yang tidak mudah didapatkan di tempat lain. Ada banyak informasi dalam Twiiter yang sifatnya up-to-date dan tentu sangat bermanfaat untuk sebagian orang. Namun, ada juga tweet yang sama sekali tidak menarik bagi sebagian orang. Dibutuhkan sebuah cara untuk menentukan informasi yang reliable dengan adanya kejadian di Twitter. Dalam hal ini, informasi atau kejadian yang terdapat pada Twitter dapat diidentifikasi, sehingga nantinya informasi tersebut akan bermanfaat untuk dikonsumsi. Dengan adanya cara tersebut dapat membantu menemukan kejadian yang sudah terjadi, sedang terjadi, atau mungkin yang akan terjadi.

Maka dari itu, penelitian ini melakukan analisis tweet dengan keyword “banjir" untuk diproses lebih lanjut sehingga menghasilkan informasi yang dapat bermanfaat dan digunakan sebaik-baiknya, misalkan mengetahui kejadian banjir yang umum terjadi pada rentang waktu tertentu. Banjir ini dijadikan sebagai objek penelitian karena merupakan salah satu bencana alam terbesar di Indonesia selain gempa bumi. 1.2 Identifikasi Masalah Merujuk dari latar belakang di atas, ada beberapa permasalahan yang timbul dalam melakukan identifikasi adanya bencana: 1. Bagaimana algoritma DBSCAN dapat membantu mendeteksi adanya event melalui Twitter? 2. Bagaimana melakukan pengambilan informasi dari setiap event berdasarkan kumpulan tweet yang terbentuk sehingga dapat menyimpulkan dimana lokasi adanya event? 1.3 Tujuan Tujuan yang ingin dicapai dalam paper ini: 1. Dapat mendeteksi adanya banjir berdasarkan tweet dengan metode density-based clustering menggunakan algoritma DBSCAN. 2. Dapat mengambil informasi penting dari setiap event berdasarkan kumpulan tweet yang terbentuk dengan menggunakan teknik Named Entity Recognition.

II. LANDASAN TEORI 2.1 Twitter dan Twitter API Twitter merupakan sebuah jejaring sosial yang muncul pada tahun 2006. Twitter didirikan oleh Jack Dorsey. Dari tahun ke tahun, pengguna Twitter terus bertambah, bahkan dalam sebuah jurnal [3] dikatakan bahwa pertumbuhan pengguna Twitter mencapai 1382% setiap tahunnya. Twitter menyediakan informasi yang bersifat real-time terhadap segala sesuatu hal, baik itu tentang fakta, pendapat, bencana alam, dan lain-lain. Kini Twitter tidak hanya dapat diakses di web browser saja, banyak aplikasi third-party yang mampu mengakses Twitter kapanpun dan dimanapun. Twitter merupakan situs microblogging terbesar di dunia dengan jumlah pengguna sekitar 105 juta pada April 2010 [1]. Twitter mampu mengirimkan sebuah pesan (kemudian disebut tweet) yang hanya terbatas 140 karakter. Twitter dapat diakses melalui website resmi Twitter dan juga aplikasi third-party berbasis web, mobile, dan desktop. Third-party adalah instansi lain atau pihak ketiga selain Twitter yang membuat Twitter client dengan memanfaatkan API Twitter. Contoh third-party seperti TweetDeck, MetroTwit, dan Seesmic. Kemudahan akses Twitter seperti inilah yang menjadikan Twitter memiliki jumlah data yang besar. Popularitas Twitter bertambah seiring dengan pertambahan jumlah pengguna yang saling follow.

Ada sekitar 55 juta tweet per hari [1], besarnya angka tersebut menjadikan Twitter sebagai sumber informasi yang ideal untuk mencari informasi menarik mengenai suatu kejadian (event detection). Terdapat dua alasan mengapa Twitter menjadi sumber informasi yang ideal. Pertama, karena sifatnya yang real-time dan pembatasan jumlah karakter dalam setiap tweet (140 karakter). Kedua, karena Twitter telah melakukan penyaringan tweet terhadap data spam yang akan dikonsumsi oleh publik. Twitter menyediakan sejumlah API berisi kumpulan fungsi untuk melakukan pencarian tweet berdasarkan lokasi, maupun berdasarkan keyword yang ingin dicari. Twitter API inilah yang dimanfaatkan penulis untuk mengumpulkan data. Ada tiga jenis Twitter API: 1. REST API 2. Search API. 3. Streaming API 2.2 Text Mining Text Mining adalah suatu proses pengambilan informasi berkualitas tinggi dari sejumlah teks. Informasi berkualitas tinggi biasanya diperoleh melalui peramalan pola dan kecenderungan melalui pembelajaran statistik. Tahapan yang diperlukan dalam text mining, yaitu (Even, Y. dan Zohar., 2002) [4]: 1. Pengumpulan data 2. Text Preprocessing 3. Transformasi Teks 4. Feature Selection 5. Penemuan Pola 6. Interpretasi 2.3 Event Detection Event dapat diartikan sebagai kejadian yang terjadi secara signifikan diluar kebiasaan sistem. Sistem itu sendiri didefinisikan oleh International Council on Systems Engineering (INCOSE) sebagai kombinasi dari interaksi komponen-komponen yang terorganisasi untuk mencapai satu atau lebih tujuan (INCOSE, 2006). Dalam sistem yang sesungguhnya kebanyakan sesuatu terjadi secara normal, namun dalam waktu yang singkat, sesuatu diluar kebiasaan normal dapat terjadi dan bisa membahayakan kehidupan itu sendiri. Oleh karena itu, event dapat diidentifikasi melalui proses yang disebut dengan event detection. Event detection merupakan proses untuk menemukan adanya kejadian menarik yang sedang, sudah, atau akan terjadi. Banyak hal yang bisa dimanfaatkan oleh event detection ini misalnya mengamati adanya suatu gejala alam atau penyakit tertentu, penemuan ilmiah, bencana alam, serangan teroris. Event detection dapat diamati secara langsung maupun tidak langsung. Contoh event detection yang dapat diamati secara langsung misalnya untuk mengetahui apakah akan terjadi hujan atau tidak, maka dapat diamati dengan melihat kondisi cuaca di luar ruangan. Sedangkan, event detection yang tidak dapat diamati secara langsung misalnya untuk mengetahui suhu tubuh manusia apakah berada dalam rentang yang normal atau tidak, maka dibutuhkan termometer. Pada contoh

yang kedua, termometer dianggap sebagai sensor pendeteksi adanya event. Event detection seperti itu dinamakan sensorbased event detection. Sensor-based event detection memiliki dua kesulitan [5]: 1. Membutuhkan komputasi yang tinggi 2. Membutuhkan media penyimpanan yang besar 2.3.1. Event Detection pada Twitter Untuk mendeteksi event pada Twitter dibutuhkan data-data berkualitas yang diambil dari Twitter. Artinya data yang diambil setidaknya mengandung target event yang ingin dideteksi. Misalnya, target event yang akan dideteksi adalah banjir, maka setidaknya tweet yang diambil mengandung kata ‘banjir’ sebagai kata kunci. Tweet bisa didapatkan ketika pengguna Twitter membuat tweet yang menyebutkan target event. Dalam hal ini, pengguna Twitter dikatakan sebagai social sensor. Social sensor ini bertugas sebagai pengamat akan adanya suatu event yang terjadi. Social sensor memiliki beberapa karakteristik, yaitu sebagian sensor secara aktif melakukan pengamatan (membuat tweet) spesifik terhadap event tertentu dan sebagian sensor lainnya secara aktif melakukan pengamatan (membuat tweet) terhadap event yang lebih global. Ketika pengguna Twitter membuat tweet dengan menyebutkan banjir, maka pengguna Twitter tersebut dianggap sebagai sensor yang mendeteksi adanya banjir. Tweet tersebut bisa didapatkan dengan memanfaatkan Search API pada Twitter [3]. Berikut ilustrasi event detection melalui Twitter.

Gambar 1. Ilustrasi event detection

2.3.2. Hambatan Umum pada Event Detection Kompleksitas dari event detection menimbulkan beberapa tantangan. Terdapat beberapa tantangan umum dalam pengembangan dan penerapan metode event detection. Berikut adalah beberapa tantangan umum tersebut [5].

1) Domain-dependence Permasalahan event detection sangat bergantung pada kondisi. Beberapa kasus dapat dikatakan serupa, tapi tak ada satupun yang persis sama. Baik parameter, variabel, dan keluaran yang dipilih untuk menyelesaikan satu permasalahan event detection mungkin tidak akan bisa diimplementasikan pada kasus lain yang serupa. Namun, pendekatan untuk memecahkan masalah event detection antara satu dan yang lainnya bisa diterapkan. Contohnya event detection bencana alam gempa bumi dan event detection bencana alam angin topan adalah dua kasus serupa yakni event detection namun dalam penyelesaiannya tentu banyak karakteristik yang tidak bisa disamakan. 2) Critically of Application Permasalahan event detection pada umumnya dipakai untuk aplikasi yang bersifat kritis. Contoh dari aplikasi bersifat kritis misalnya mendeteksi gejala penyakit yang berbahaya atau mendeteksi potensi bencana alam yang akan terjadi dalam waktu dekat. Hal tersebut tentu membutuhkan hasil presisi yang tinggi agar hasilnya akurat. 2.3.3. Algoritma Event Detection Tweet dijadikan sebagai sumber pengamatan terhadap terjadinya event. Maka dari itu, tweet dianggap sebagai sensor. Tujuan dari event detection melalui Twitter adalah mengelompokkan tweet ke dalam event. Berikut langkahlangkahnya [6]. 1) Tweet yang sudah terkumpul disimpan dalam database atau file teks. 2) Kelompokkan tweet yang memiliki kemiripan isi ke dalam satu cluster. 3) Dari hasil setiap cluster akan mewakili 1 event dan masing-masing event memiliki atribut seperti lokasi, waktu, deskripsi event. 4) Ekstrak informasi dari satu tweet yang paling representatif. 2.4 Clustering Clustering adalah proses pengelompokkan objek berdasarkan ciri atau atribut tertentu ke dalam sejumlah cluster. Pengelompokkan dilakukan dengan prinsip tersebut memaksimalkan kedekatan antar objek dalam satu cluster dan meminimumkan kesamaan antar cluster. Dengan prinsip dan algoritma clustering, sejumlah objek dapat dikelompokkan secara mudah berdasarkan ciri atau atribut tertentu. Clustering bersifat unsupervised learning, yang berarti analisis cluster menemukan pola dari data dengan tidak memanfaatkan label yang sudah ada sebelumnya. Clustering dalam data mining berguna untuk menemukan pola distribusi dalam sebuah data set yang berguna untuk proses analisis data. Kesamaan objek biasanya diperoleh dari kedekatan nilai-nilai atribut yang menjelaskan objek-objek data, sedangkan objekobjek data direpresentasikan sebagai sebuah titik dalam ruang multidimensi [7].

2.4.1 Text Clustering Text Clustering merupakan salah satu fungsi penting dari Text Mining. Text Clustering bertujuan untuk membagi kumpulan teks ke dalam beberapa kelompok. Kumpulan teks yang memiliki kesamaan topik akan dikelompokkan dalam satu kelompok [8]. Dalam text clustering, data teks tersedia dalam berbagai macam format (plain text, DOC, PDF, XML). Data tersebut harus dikonversi menjadi model representasi yang umum agar bisa diproses, misalnya pemodelan dengan Vector Space Model (VSM). Dalam VSM, teks direpresentasikan dalam bentuk vektor . Setiap term ti mewakili sebuah kata. Kumpulan teks akan direpresentasikan dalam satu set vektor yang dapat ditulis sebagai matriks.

Data Teks

𝑥11 ⋮ 𝑥𝑗1 ⋮ [𝑥𝑛1

⋯ 𝑥1𝑖 ⋮ ⋮ ⋯ 𝑥𝑗𝑖 ⋮ ⋮ ⋯ 𝑥𝑛𝑖

⋯ 𝑥1𝑚 ⋮ ⋮ ⋯ 𝑥𝑗𝑚 ⋮ ⋮ ⋯ 𝑥𝑛𝑚 ]

Setiap baris pada matriks merepresentasikan kumpulan teks dan setiap kolom merepresentasikan kata di dalam teks j. Setiap elemen Xji, merepresentasikan bobot TFIDF. 𝑡𝑓𝑖𝑑𝑓(𝑑𝑗 , 𝑡𝑖 ) = 𝑡𝑓(𝑑𝑗 , 𝑡𝑖 ) × log

termasuk titik pusat ataupun titik batas. Berikut dijelaskan beberapa konsep yang memiliki peranan penting dalam DBSCAN. 1) Directly-density reachable Titik p dikatakan directly density-reachable dari titik q, jika titik p berada di dalam ketetanggaan titik q dengan jarak tertentu (Ɛ) dan titik q merupakan titik pusat, serta jumlah ketetanggan dari titik pusat q memenuhi MinPts. Konsep ini berlaku untuk sepasang titik pusat. 2) Density-reachable Titik p dikatakan density-reachable dari titik q (memenuhi syarat Ɛ dan MinPts) jika terdapat rantai yang menghubungkan titik p1, ..., pn dengan p1 = q, pn = p dan pi+1 directly density-reachable dari pi. 3) Density-connectivity Titik p density-connectivity terhadap titik q (memenuhi syarat Ɛ dan MinPts) jika titik p dan q density-reachable dari titik r. Density-connectivity bersifat simetris terhadap suatu objek dengan objek lainnya. Untuk lebih jelasnya, gambar 2 mengilustrasikan penjelasan ketiga konsep di atas.

𝐷 𝑑𝑓(𝑡𝑖 )

Nilai 𝑡𝑓(𝑑𝑗 , 𝑡𝑖 ) merupakan frekuensi kemunculan term ti dalam dokumen dj, D merupakan jumlah dokumen, dan 𝑑𝑓(𝑡𝑖 ) merupakan jumlah dokumen yang memiliki term ti. 2.4.2 Density-based Clustering Density-based Clustering membagi sejumlah data berdasarkan daerah kepadatannya (density). Metode ini menganggap cluster sebagai suatu area yang berisi objekobjek yang padat, yang dipisahkan oleh area yang memiliki kepadatan rendah [9]. Salah satu algoritma dalam densitybased clustering, yaitu DBSCAN. DBSCAN (Density-Based Spatial Clustering of Applicatoin with Noise) mendefinisikan cluster sebagai himpunan maksimum dari kumpulan titik-titik yang terkoneksi (density-connected). Semua objek yang tidak masuk ke dalam cluster dianggap noise. Pengelempokkan dilakukan terhadap titik-titik yang berada dalam radius (Ɛ) tertentu yang harus memenuhi jumlah titik minimum (MinPts). Pembentukan ketetanggaan antar titik dapat ditentukan melalui fungsi jarak antara dua buah titik, yaitu Euclidean Distance.

Gambar 2. Konsep Algoritma DBSCAN

𝑑(𝑃1, 𝑃2) = √(𝑥2 − 𝑥1 )2 + (𝑦2 − 𝑦1 )2

Lingkaran pada gambar di atas mengilustrasikan sebuah objek dengan radius (Ɛ) dan nilai MinPts=3. Dari gambar di atas terdapat empat core object yang diberi label m, p, o, dan r. Disebut core object karena jumlah ketetanggan (Ɛneighborhood) objek tersebut berisi setidaknya nilai MinPts, 3 titik. Titik q directly density-reachable dari titik m. Titik m directly density-reachable dari titik p. Begitu juga sebaliknya. Titik q (indirectly) density-reachable dari titik p karena titik q directly density-reachable dari titik m directly densityreachable dari titik p. Tetapi titik p tidaklah density-reachable dari titik q karena titik q bukan core object. Begitupun dengan titik r dan s, keduanya density-reachable dari titik o, dan titik o density-reachable dari titk r. Titik o, r, dan s adalah densityconnected [7].

DBSCAN menggunakan konsep titik pusat (core point), titik batas (border point), dan noise. Titik yang memiliki sejumlah titik tetangga dan memenuhi jumlah titik minimum, serta berada dalam jarak tertentu disebut sebagai titik pusat. Sedangkan titik batas memiliki jumlah titik tetangga namun tidak memenuhi jumlah titik minimum. Kriteria suatu titik dikatakan sebagai noise yaitu pada saat titik tersebut tidak

2.5 Named Entity Recognition Named Entity Recognition (NER) merupakan salah satu bagian penting dalam ekstraksi informasi dan berhubungan dengan NLP (Natural Language Processing) yang bertujuan untuk mengidentifikasi entitas pada suatu teks dan mengklasifikasikannya ke dalam beberapa entitas tersebut. Entitas dalam NER meliputi entitas nama (nama orang, lokasi,

organisasi), ekspresi waktu (tanggal, waktu, durasi), dan ekspresi bilangan (uang, persen, numerik, kardinal) pada kumpulan teks. Ekstraksi Informasi itu sendiri merupakan proses penemuan informasi dari kumpulan kumpulan dokumen atau teks berbahasa alami sebagai masukannya dan menghasilkan informasi yang berguna berupa informasi yang terstruktur dengan format tertentu [10]. Teks: 17:35 | Kopo banjir setinggi 50 cm. Cari jalan alternatif! Hasil dari pengenalan Entitas: <Waktu>17:55Kopo banjir setinggi 50cm.

III. HASIL PENELITIAN 3.1 Pembahasan Penelitian Pada penelitian ini digunakan metode Density-based Clustering dengan algoritma DBSCAN dalam melakukan analisis cluster. Dalam penelitian ini dilakukan tahapan-tahapan untuk melakukan analisis cluster terhadap data tweet, yaitu sebagai berikut: 1. 2. 3. 4. 5.

Pengumpulan data Preprocessing Clustering Evaluasi Cluster Ekstraksi Event

1. Pengumpulan data Data yang digunakan diambil dari situs microblogging Twitter. Tweet yang penulis gunakan untuk eksperimen ini sebanyak 5354 tweet. 2. Preprocessing Pada tahap ini dilakukan dilakukan pemrosesan awal teks untuk menghilangkan tanda baca, penghilangan user (@username) dan hashtag (#hashtag), tokenisasi, penghilangan stopwords, penggantian kata dengan sinonim, mengubah teks menjadi lowercase, dan mengurangi data duplikasi. Penghilangan sebagian kata akan digantikan dengan karakter spasi untuk mempermudah pemenggalan kata pada tahap berikutnya. Data yang digunakan pada tahap ini hanya data yang diambil pada bulan Januari 2013. Jadi, semua event yang terdeteksi merupakan event yang terdapat pada Twitter pada bulan Januari 2013.

Tabel 1. Hasil Preprocessing Teks Awal @infojakarta buncit - mampang mulai di siram hujan 11:03am tiati macet dan banjir, #jktcuaca 13.25: BANJIR CILEGON dekat Kawasan Krakatau Steel arah Anyer . http://t.co/MWhsbR9W

Hasil Preprocessing buncit mampang mulai di siram hujan 11 03am tiati macet dan banjir 13 25 banjir cilegon dekat kawasan krakatau steel arah anyer

Setelah tahap preprocessing, langkah selanjutnya adalah melakukan pembobotan dengan menggunakan vector space model. Vector space model (VSM) merupakan teknik pembobotan yang merepresentasikan teks sebagai kumpulan titik di dalam suatu ruang vektor. Pembobotan dihitung dengan menggunakan TF-IDF (Term Frequency – Inverse Document Frequency). Contoh pembobotan untuk kata “bandung”, jika kata tersebut muncul sebanyak 8 kali pada 100 tweet dan kata tersebut muncul sebanyak 2 kali pada tweet yang akan dilakukan pemodelan, maka bobot kata untuk kata “bandung”: 𝑡𝑓𝑖𝑑𝑓 = 2 × log

100 = 2,193 8

Pembobotan kata dilakukan untuk setiap kata di dalam tweet. Hasil pembobotan pada VSM ini selanjutnya akan digunakan pada algoritma clustering. Tabel 2. Hasil Pembobotan Teks Awal @infojakarta buncit mampang mulai di siram hujan 11:03am tiati macet dan banjir, #jktcuaca

13.25: BANJIR CILEGON dekat Kawasan Krakatau Steel arah Anyer . http://t.co/MWhsbR9W

Hasil Preprocessing banjir=3.7342606075725816;sir am=3.36679638328673;mampa ng=3.36679638328673;tiati=3.3 6679638328673;macet=1.32147 34045000724;11=2.8896751285 670677;hujan=0.840457105896 8859;03am=3.36679638328673; buncit=3.36679638328673; banjir=3.7342606075725816;kr akatau=3.36679638328673;cileg on=2.287615137239105;anyer= 2.8896751285670677;25=3.366 79638328673;steel=3.36679638 328673;13=3.065766387622748 6;kawasan=1.070131193025198 9;arah=1.861646404966824;

3. Clustering Hasil proses pada tahap preprocessing sangatlah penting sebagai inputan pada tahap clustering. Semakin baik kualitas data semakin baik pula hasil clustering. Algoritma clustering yang diimplementasikan pada tahap ini adalah DBSCAN.

DBSCAN akan melakukan cluster sesuai dengan parameter masukkannya, yaitu eps (Ɛ) dan MinPts. Jumlah cluster yang dihasilkan oleh DBSCAN sangat bergantung pada kedua parameter tersebut. Pada tahap awal, DBSCAN akan mengelompokkan semua titik sebagai kelompok UNCLASSIFIED. Lalu, secara iteratif setiap titik diuji kedekatannya dengan titik lain. DBSCAN akan membuat suatu region dengan radius senilai eps sehingga region tersebut akan berisi titik-titik yang berjarak eps (Ɛ) dari titik uji. Jika di dalam region tersebut terdapat sejumlah titik yang banyaknya lebih dari nilai MinPts, maka semua titik di dalam region tersebut dimasukkan ke dalam cluster yang sama. Jika jumlah titik di dalam suatu region lebih kecil dari nilai MinPts, maka titik uji dianggap sebagai noise. Sebelum pergantian iterasi, setiap titik yang berada dalam region yang memiliki jumlah titik lebih dari nilai MinPts, diuji kembali kedekatannya terhadap titik lain karena proses cluster dalam DBSCAN ini adalah untuk mencari titik density-reachable. Dalam hal ini, pemilihan parameter eps (Ɛ) dan MinPts sangat berperan terhadap hasil cluster. 4. Evaluasi Cluster Kumpulan cluster yang dihasilkan oleh algoritma clustering dijadikan input untuk melakukan evaluasi. Pada eksperimen ini, evaluasi dilakukan dengan menggunakan overall similarity. Nilai overall similarity pada eksperimen ini sangat bergantung pada parameter eps dan MinPts. Hasil dari overall similarity ini berkisar dari 0 – 1. Semakin mendekati 1 artinya kualitas cluster semakin baik atau kemiripan antar anggota cluster sangat dekat. Nilai overall similarity dari hasil cluster dapat dilihat pada Tabel 3. 5. Ekstraksi Event Kumpulan cluster yang dihasilkan oleh algoritma DBSCAN memiliki sejumlah tweet didalamnya. Dengan menggunakan teknik Named Entity Recognition (NER), dapat diambil informasi dari tweet yang representatif di dalam setiap cluster misalnya mengambil nama tempat atau lokasi banjir. Implementasi yang digunakan untuk melakukan tugas NER pada eksperimen ini adalah menggunakan regular expression atau regex. 3.2 Hasil Eksperimen Hasil dari eksperimen yang didapatkan dijelaskan sebagai berikut. Tabel 3. Hasil Eksperimen Jumlah Tweet Uji

Jumlah Tweet Preprocessing

Jumlah Noise

Eps

MinPts

Jumlah Cluster

Overall Similarity

5354 5354 5354 5354

3632 3632 3632 3632

1758 1096 2286 2848

1 1.5 0.5 0.5

8.00 8.00 8.00 15

65 45 69 24

0.5541 0.3366 0.7858 0.8579

Berikut merupakan contoh dari hasil event yang dideteksi dari setiap cluster.

Gambar 3. Hasil Ekstraksi Event Dari hasil eksperimen yang telah dilakukan (lihat Tabel 3), pemilihan variabel Eps dan MinPts sangat berpengaruh terhadap hasil cluster dan nilai overall similarity. Semakin besar nilai Eps, mengakibatkan jumlah cluster yang terbentuk semakin sedikit. Akan tetapi, parameter dari Eps ini tidak berdiri sendiri dalam menentukan hasil cluster. Dalam tabel 3 terlihat bahwa meskipun nilai Eps diperkecil tetapi nilai dari MinPts diperbesar akan menghasilkan jumlah cluster yang berbeda dengan nilai Eps yang sama. Artinya, kedua parameter Eps dan MinPts merupakan pasangan paramater yang harus dikombinasikan dengan baik sehingga menghasilkan suatu cluster yang baik pula. Baik atau tidaknya kualitas cluster dapat dilihat dari nilai overall similarity yang terbentuk. Pada tabel 3 terlihat bahwa nilai eps 0.5 dan MinPts 15 menghasilkan kualitas cluster yang paling baik, yakni 0.8623. Pada eksperimen ini, hasil dari sebuah cluster merepresentasikan sebuah event banjir. Misalnya, jika hasil dari clustering ditemukan 24 cluster maka terdeteksi sebanyak 24 cluster terkait dengan banjir. Pada kenyataannya dari setiap cluster yang terbentuk tidak selalu tweet dalam satu cluster tersebut berisikan event yang sama. Misalnya, suatu cluster merepresentasikan banjir di daerah Jakarta, namun ada beberapa tweet dalam cluster tersebut yang tidak membicarakan banjir di daerah Jakarta melainkan daerah lainnya. Hasil dari algoritma DBSCAN ini bergantung pada dua parameter, yakni Eps dan MinPts. Pemilihan parameter ini pun bergantung pada tujuan yang ingin dicapai dari proses clustering. Jika menginginkan jumlah cluster yang banyak maka nilai dari MinPts perlu diperkecil. Sebaliknya, jika menginginkan jumlah cluster yang sedikit namun berukuran besar maka nilai MinPts perlu diperbesar. Perlu diingat bahwa DBSCAN ini menggunakan fungsi jarak dalam perhitungannya sehingga dalam pemilihan nilai Eps pun tidak bisa sembarangan. Untuk mendapatkan informasi dari setiap cluster yang telah terbentuk digunakan regular expression (regex) untuk mengambil lokasi dari event yang terbentuk. Dari setiap cluster, diambil satu data yang paling representatif, kemudian dari data tersebut didapatkan informasi mengenai lokasi banjir dengan memanfaatkan regular expression (regex). IV. PENUTUP 4.1 Kesimpulan 1. Algoritma DBSCAN membantu mendeteksi adanya event dengan cara mengelompokkan sebuah data berdasarkan tingkat kepadatannya sehingga cluster akan dipisahkan dengan data-data dengan tingkat kepadatan

yang rendah. DBSCAN membutuhkan dua parameter input untuk melakukan clustering, yaitu eps dan MinPts. Kedua parameter tersebut sangat berpengaruh terhadap hasil cluster. Sebuah cluster hasil dari DBSCAN ini merepresentasikan sebuah event yang ingin dideteksi sehingga satu cluster berarti satu event. 2. Pengambilan informasi event dapat dilakukan dengan teknik Named Entity Recognition (NER). Implementasi NER yang digunakan yaitu pemanfaatan regular expression (regex). Regex akan mengambil informasi dengan mencocokan pola string tertentu dengan data hasil cluster. Jika terdapat kecocokan, maka dapat diambil informasi mengenai lokasi dan deskripsi dari event yang terdeteksi. 4.2 Saran Untuk pengembangan lebih lanjut, saran-saran yang diberikan pada penelitian ini yaitu sebagai berikut: 1. Perlu dilakukan adanya klasifikasi terlebih dahulu terhadap data tweet yang akan diproses pada tahap clustering. Klasifikasi bertujuan untuk memisahkan data yang memiliki makna banjir sebagai bencana dan makna banjir sebagai kiasan. 2. Perlu dilakukan penelitian lebih lanjut dengan menggunakan algoritma lain dari metode density-based clustering dan membandingkan hasilnya dengan algoritma DBSCAN. 3. Perlu dilakukan penelitian lebih lanjut untuk mengambil informasi dari setiap cluster (ekstraksi informasi) sehingga data nama dan lokasi kejadian suatu event lebih presisi, misalnya dengan menggunakan teknik NER berdasarkan pembelajaran mesin (machine learning). 4. Perlu dilakukan penelitian lebih lanjut dalam penghitungan pembobotan TFIDF dan fungsi jarak selain menggunakan Euclidean Distance. Hal ini untuk

mengantisipasi kelemahan DBSCAN yang tidak mampu melakukan clustering terhadap variasi perbedaan jarak yang besar antar objek data.

UCAPAN TERIMA KASIH Penulis menyadari bahwa terselesaikannya penelitian ini tidak lepas dari peranan, dukungan, dan bantuan dari berbagai pihak: Allah SWT, pembimbing dan keluarga. DAFTAR PUSTAKA [1] [2] [3]

[4]

[5]

[6]

[7] [8] [9] [10]

Jackoway A., Samet H., dan Jagan S., Identification of Life Events using Twitter, Journal of ACM. 2011 Wibisono Y., Sistem Analisis Opini Microblogging Berbahasa Indonesia, Jurnal FPMIPA UPI, 2011 Sakaki T., Okazaki M., dan Matsuo Y., Earthquake Shakes Twitter Users: Real-time Event Detection by Social Sensors, [Online]. Tersedia di http://ymatsuo.com/papers/www2010.pdf [3 Februari 2012], 2010 Even Y. dan Zohar, Introduction To Text Mining, [Online], Tersedia: http://www.docstoc.com/docs/25443990/Introduction-to-Text-Mining [16 Februari 2012], 2002 Kerman M.C., Jiang W., Blumberg A.F., dan Buttrey S.E., Event Detection Challenges, Methods, and Applications in Natural and Artificial Systems, 14th International Command and Control Research and Technology Symposium, 2009 Sun Y. Event Detection Tutorial for Twitter Project, [Online], Tersedia di: https://wiki.engr.illinois.edu/download/attachments/200016061/Tutoria l+on+Event+Detection+for+Twitter+Project.pptx [4 Januari 2013], 2012 Han J. dan Kamber M., Data Mining Concepts and Techniques, San Francisco: Morgan Kaufmann Publishers, 2006 Huang J. Z., Michael Ng., dan Jing L., Text Clustering: Algorithms, Semantics, and Systems, PAKDD Tutorial, 2006 S. Michael, K. George, dan K. Vipin, A Comparison of Document Clustering Techniques, Journal of Citerseerx, 2000 Chincor N., MUC-7 Named Entity Task Definition, Version 3.5, 1997