BAB II TINJAUAN PUSTAKA Short Message Service (SMS) Short Message Service (SMS) adalah sebuah layanan dasar yang membolehkan pertukaran pesan teks singkat antarpelanggan. Pesan ini dapat dikirim dari perangkat mobile GSM/UMTS tetapi bisa juga dikirim dari perangkat lain dengan cakupan yang lebih luas seperti internet host, telex, dan faksimili SMS. Internet host, telex, dan faksimili SMS adalah teknologi yang didukung 100% oleh perangkat GSM dan sebagian besar jaringan GSM di seluruh dunia yang sudah sangat matang (Bodic 2005). Arsitektur SMS yang disediakan oleh jaringan GSM ditunjukkan pada Gambar 1. Sebagai tambahan, terdapat sebuah elemen yang disebut short message entity, biasanya dalam wujud sebuah aplikasi perangkat lunak dalam perangkat mobile, yang penting dalam menangani pesan (pengiriman, penerimaan, penyimpanan, dan lain-lain). Short message entity tidak ditampilkan pada Gambar 1.
Gambar 1 Arsitektur SMS pada Jaringan GSM (Bodic 2005)
8 Elemen yang dapat mengirim dan menerima pesan singkat dinamakan short message entities (SME). Sebuah SME dapat berupa aplikasi perangkat lunak dalam sebuah perangkat mobile tetapi juga bisa berupa perangkat faksimili, peralatan telex, remote internet server, dan lain-lain. Sebuah perangkat mobile harus diatur supaya bekerja dengan baik dalam jaringan mobile. Sebuah SME dapat berupa server yang saling berhubungan langsung atau melalui sebuah gateway yaitu SMS center. Sebuah SME juga dikenal sebagai sebuah External SME (ESME). Sebuah ESME menggambarkan sebuah WAP proxy/server, sebuah email gateway, atau sebuah voice mail server. Untuk pertukaran pesan singkat, SME yang membangkitkan dan mengirim pesan singkat dikenal sebagai originator SME sedangkan SME yang menerima pesan singkat dikenal sebagai recipient SME. Service Center (SC) atau SMS Center (SMSC) memainkan peran penting dalam arsitektur SMS. Fungsi utama dari SMSC adalah menyiarkan pesan singkat diantara SME dan menyimpan dan meneruskan pesan singkat (penyimpanan pesan jika SME penerima tidak tersedia). SMSC mungkin terintegrasi sebagai bagian dari jaringan mobile (misalnya, terintegrasi dengan MSC) atau entitas jaringan yang berdiri sendiri. SMSC mungkin juga dapat ditempatkan diluar jaringan dan diatur oleh organisasi ketiga. Operator jaringan mobile biasanya mempunyai
perjanjian
komersial
yang
saling
menguntungkan
untuk
membolehkan pertukaran pesan antarjaringan. Hal ini berarti sebuah pesan yang dikirim dari sebuah SME yang ada di jaringan A dapat dikirim ke SME lain yang ada di jaringan mobile B. Hal ini memungkinkan pengguna untuk bertukar pesan walaupun mereka tidak terdaftar dalam jaringan yang sama dan terkadang berada di negara yang berbeda, inilah salah satu fitur kunci yang membuat SMS sangat sukses (Bodic 2005). Text Mining Text mining dapat diartikan secara luas sebagai suatu proses pengetahuan intensif dimana pengguna berinteraksi dengan koleksi dokumen dari waktu ke waktu dengan menggunakan seperangkat alat analisis. Dengan cara yang dapat disamakan dengan data mining, text mining berusaha menggali informasi yang
9 berguna dari sumber data melalui identifikasi dan eksplorasi pola yang menarik. Dalam kasus text mining, bagaimanapun, sumber data merupakan koleksi dokumen, dan pola yang menarik yang ditemukan tidak diantara record basis data yang tersusun tetapi dalam data teks tidak terstruktur dalam dokumen yang ada dalam koleksi (Feldman & Sanger 2007). Karena data mining mengambil data yang tersimpan dalam format terstruktur, sebagian besar dari praproses fokus pada dua kegiatan : scrubbing dan normalizing data dan membuat sejumlah tabel penggabungan. Secara berlawanan, untuk sistem text mining, pusat operasi praproses terjadi pada identifikasi dan ekstrasi fitur representatif untuk dokumen bahasa alami. Operasi praproses ini bertanggung jawab untuk mengubah data tidak terstruktur yang tersimpan dalam koleksi dokumen ke dalam format terstruktur lanjutan yang lebih eksplisit, yang merupakan masalah yang tidak relevan untuk sebagian besar sistem data mining (Feldman & Sanger 2007). Metode yang digunakan pada text mining hampir sama dengan metode dalam data mining. Sekali data ditransformasi menjadi format numerik biasa, metode data mining standar dapat diterapkan (Weiss et al. 2005). Klasifikasi, klastering, dan information extraction merupakan metode yang banyak diterapkan dalam text mining. Tema yang mungkin dalam menganalisa data yang kompleks adalah klasifikasi atau kategorisasi. Secara abstrak diuraikan, tugasnya adalah mengklasifikasikan sebuah instance data yang diberikan ke dalam sebuah kategori. Berlaku untuk bidang dari manajemen dokumen, tugas ini dikenal dengan kategorisasi teks, dimana diberikan kumpulan kategori (subyek, topik) dan sebuah koleksi dari dokumen teks, proses menemukan topik yang sesuai untuk setiap dokumen (Feldman & Sanger 2007). Beberapa teknik yang dapat digunakan pada klasifikasi dokumen adalah probabilistic classifier, decision tree classifier, decision rule classifier, nearestneighbor classifier, dan support vector machine classifier. Klastering adalah teknik yang berguna untuk mangatur suatu dokumen teks berjumlah besar yang tidak terurut menjadi sejumlah kecil klaster yang koheren dan berarti. Klastering dokumen teks melakukan pengelompokkan dokumen yang
10 mirip untuk membentuk klaster yang koheren, sedangkan dokumen yang berbeda terpisah menjadi klaster yang berbeda (Huang 2008). Algoritma ROCK (Robust Clustering using links) ROCK
adalah
algoritma
klastering
hirarki
aglomeratif
untuk
mengelompokkan data kategorik. Algoritma ROCK membangun link untuk menggabungkan klaster dan tidak menggunakan jarak seperti algoritma klastering pada umumnya (Guha et al. 2000). Parameter yang digunakan dalam algoritma ROCK adalah : 1.
Tetangga Tetangga dari suatu objek adalah objek lain yang dianggap paling mirip 1 dan 0. Dua objek x dan y , simx,y ≥ θ . θ merupakan parameter yang
dengan objek tersebut. Diberikan suatu nilai ambang (θ) yang bernilai antara dekat hubungan x dan y sehingga kedua objek tersebut dapat dikatakan
ditentukan oleh pengguna yang dapat digunakan untuk mengontrol seberapa
sebagai tetangga. Ukuran kemiripan antarpasangan objek dihitung dengan Jaccard Coefficient 2.
Link Algoritma ROCK menggunakan informasi link sebagai ukuran kemiripan antarobjek. Jika x merupakan tetangga dari z dan z merupakan tetangga dari y maka dikatakan x memiliki link dengan y walaupun x bukan tetangga dari y. Link(x,y) = ∑ tetangga yang dimiliki sekaligus oleh x dan y
Didefinisikan :
Penghitungan link untuk semua kemungkinan pasangan objek dilakukan
berukurann x n, dimana A[ , ] bernilai 1 jika dan merupakan tetangga dengan menggunakan matrik tetangga A. Matrik tetangga A adalah matrik
dan bernilai 0 jika dan bukan tetangga. Jumlah link antarpasangan dan dapat diperoleh dari hasil kali antara baris ke dan kolom ke : linkx,y= ∑nl=1 A x,l *A[l,y]
(1)
Jika nilai link(,) besar, menunjukkan bahwa kemungkinan x dan y berada dalam klaster yang sama juga besar.
11 3.
Goodness Function Algoritma ROCK menggunakan informasi nilai goodness sebagai ukuran kemiripan antarklaster, dan menggabungkan objek/klaster yang memiliki kemiripan terbesar. Didefinisikan ukuran goodness antara klaster Ci dan Cj : gCi ,Cj = link(Ci ,Cj ) (ni +nj )1+2f(θ) - ni
Dimana linkCi ,Cj = ∑xCi,
1+2f(θ)
yCj link(x,y)
1+2f(θ)
- nj
]
(2)
menyatakan banyaknya cross link
(jumlah link dari semua kemungkinan pasangan objek yang ada dalam C dan Cj , ni dan nj masing-masing menyatakan jumlah anggota klaster i dan jumlah
anggota klaster j, dan fθ= 1 ⁄1 .
Langkah-langkah dalam algoritma ROCK yaitu : 1. Menentukan inisialisasi untuk masing-masing data poin sebagai klaster pada awalnya. 2. Menghitung similaritas antarklaster dengan klaster lainnya, menggunakan jaccard coefficient. 3. Menentukan nilai matrik tetangga A dengan menggunakan nilai nilai ambang (θ). A[x,y] bernilai 1 jika sim(x,y) ≥ θ dan bernilai 0 jika sim(x,y) ≤ θ. 4. Menghitung link antarklaster dengan klaster lainnya. Link(Ti, Tj) antarobjek diperoleh dari jumlah tetangga antara Ti dan Tj 5. Menghitung nilai goodness measure untuk setiap klaster dengan klaster lainnya jika link !=0 yang disebut local heap. 6. Memilih nilai maksimum goodness measure antarkolom di baris ke i yang disebut global heap. 7. Ulangi langkah 5 dan 6 hingga mendapatkan nilai maksimum di global heap dan local heap. 8. Selama ukuran data > k, dengan k adalah jumlah kelas yang ditentukan lakukan penggabungan klaster yang memiliki nilai local heap terbesar menjadi satu klaster, tambahkan link antarklaster yang digabungkan, hapus klaster yang digabungkan dari local heap dan update nilai global heap dengan nilai hasil penggabungan. 9. Lakukan langkah 8 hingga menemukan jumlah klaster yang diharapkan atau tidak ada lagi link antara klaster-klasternya.
12 Evaluasi Klaster Evaluasi klaster adalah kemampuan untuk mendeteksi ada atau tidaknya suatu struktur tidak acak dalam data. Beberapa aspek penting dalam evaluasi klaster yaitu (Tan et al. 2005): 1.
Menentukan kecenderungan klaster dari suatu data.
2.
Menentukan jumlah klaster yang tepat.
3.
Mengevaluasi seberapa baik hasil analisis klaster tanpa diberikan informasi eksternal.
4.
Membandingkan hasil analisis klaster terhadap hasil eksternal yang diketahui, misalnya label kelas eksternal.
5.
Membandingkan dua himpunan klaster untuk menentukan klaster yang lebih baik. Perhitungan evaluasi dapat digolongkan menjadi tiga jenis yaitu:
1.
Unsupervised Teknik unsupervised mengukur goodness dari struktur klaster tanpa informasi eksternal. Ukuran yang digunakan dalam teknik unsupervised dibagi menjadi dua, yaitu : cohesion dan separation. Cohesion merupakan ukuran kebaikan klaster yang menentukan seberapa dekat objek-objek di dalam klaster. Separation merupakan ukuran kebaikan klaster yang menentukan perbedaan atau seberapa jau suatu klaster dengan klaster lainnya.
2.
Supervised Teknik supervised mengukur kecocokan struktur hasil pembentukan klaster dengan struktur eksternal.
3.
Relative Teknik relative membandingkan klaster yang berbeda. Ukuran evaluasi klaster relative merupakan teknik unsupervised dan supervised yang digunakan untuk perbandingan. Pada aspek evaluasi klaster kesatu, kedua, dan ketiga termasuk teknik
unsupervised yang tidak diperlukan informasi eksternal, sedangkan aspek keempat termasuk teknik supervised yang memerlukan informasi eksternal. Aspek kelima dapat dilakukan menggunakan teknik unsupervised dan supervised.
13 Algoritma Naive Bayes Klasifikasi Naive Bayes dapat diuraikan sebagai berikut : Asumsi bahwa setiap instance direpresentasikan dengan sebuah vektor X=(x1,x2,…,xn), dimana
x1,x2,…,xn adalah ukuran dari atribut
A1,A2,…,An.
Andaikan terdapat kelas sejumlah m yaitu C1,C2,…,Cm. Diberikan suatu instance X yang belum diketahui kelasnya, dengan menggunakan teorema Bayesian, P(Cl |X) = | ⁄ = | ⁄ ∑ ! |
posterior probability dari X terhadap Cl adalah :
(3)
Class prior probability dapat diduga dengan P(Cl)=" ⁄" , dimana sladalah
jumlah dari data pelatihan dengan kelas Cl dan s adalah jumlah total data pelatihan. Naive Bayes menduga conditionally independent antara satu atribut dan atribut lainnya dengan : P(X|Cl)= ∏%
! $ |
(4)
P(xk|Cl) dapat diduga dari data. Sehingga didapatkan P(Cl|X)= ∏%
! $ | ⁄ ∑' ! &$ |'
(5)
Untuk menggolongkan sebuah data X yang belum diketahui kelasnya, P(Cl|X) dievaluasi untuk setiap kelas Cl. Data X akan dimasukkan dalam kelas Cl jika dan hanya jika P(Cl|X) > P(Cj|X), 1 ≤ j ≤ m, j≠l (Deng & Peng 2006). Proses belajar mengambil sebagai masukan pengumpulan pelatihan, dan terdiri atas langkah-langkah berikut (Sebastiani 2002): 1. Preprocessing. Penghapusan elemen-elemen yang tidak relevan (misalnya, HTML), dan pemilihan segmen yang sesuai pengolahan (misalnya header, tubuh, dan lain-lain). 2. Tokenization. Membagi pesan ke segmen semantik yang koheren (misalnya, kata, string karakter lain, dan lain-lain). 3. Representation. Konversi pesan ke vektor pasangan atribut dan nilai, di mana atribut adalah token yang ditetapkan sebelumnya, dan nilai-nilai mereka dapat biner, (relatif) frekuensi, dan lain-lain.
14 4. Selection. Penghapusan atribut yang kurang prediktif (menggunakan ukuran kualitas misalnya seperti information gain). 5. Learning. Secara otomatis membangun model klasifikasi (classifier) dari koleksi pesan, karena mereka sebelumnya telah diwakili. Word Approximation Word
approximation
merupakan
teknik
yang
digunakan
untuk
menyelesaikan kesalahan typographical dari query dengan menggunakan teknik pencarian yang rapi. Dalam word approximation dilakukan penghitungan nilai kekeliruan sebuah query dari pengguna dengan membandingkan query dari pengguna dengan kata yang terdapat pada kamus. Kata dengan nilai kekeliruan paling sedikit yang akan dikembalikan. Modul word approximation dilakukan berdasarkan penghitungan jarak mengubah string masukan dengan kata kunci yang dikenal. Jika string masukan sama persis dengan sebuah kata kunci, maka kata kunci ini digunakan secara langsung. Selainnya, kata kunci terdekat dipilih sebagai perbaikan kata (Angkawattanawit et al. 2008). Confusion Matrix Confusion matrix merupakan sebuah tabel yang berisi jumlah banyaknya record uji yang diprediksi secara benar dan tidak benar oleh model klasifikasi. Bentuk dari confussion matrix terlihat pada Tabel 1. Setiap entri pada fij pada tabel ini menyatakan banyaknya record dari kelas i yang diprediksi ke dalam kelas j. Tabel 1 Confusion Matrix Kelas yang diprediksi Kelas = 1
Kelas = 0
Kelas
Kelas = 1
f11
f10
aktual
Kelas = 0
f01
f00
Informasi dari confusion matrix diperlukan untuk menentukan kinerja suatu model klasifikasi. Informasi ini dapat diringkas ke dalam suatu nilai seperti akurasi (Tan et al. 2005).
Android
Akurasi = f11 f00 ⁄ f11 f10 f01 f00
15 (6)
Android adalah perangkat lunak yang menyertakan sistem operasi, middleware, dan kunci aplikasi perangkat seluler dengan sekumpulan Application Programming Interface (API) library untuk pembuatan aplikasi perangkat seluler sesuai kebutuhan (Meier 2009). Google mengembangkan sistem operasi Android untuk platform di perangkat mobile atau netbook. Struktur sistem dari Android terdiri dari lapisan aplikasi, lapisan kerangka aplikasi, lapisan runtime sistem, dan lapisan kernel Linux (Xie et al, 2012). Arsitektur Android dapat dilihat pada Gambar 2.
Gambar 2 Arsitektur Android (Xie et al. 2012) Penelitian Terkait Deng & Peng (2006) melakukan penelitian mengenai sistem penyaringan SMS terdistibusi yang diaplikasikan pada jaringan mobile. Sistem penyaringan SMS dikembangkan menggunakan algoritma Naive Bayes. Sistem yang dikembangkan memiliki kemampuan pembelajaran mandiri dan memperbarui pengetahuan. Sistem ini terdiri atas satu SMS processing center dan beberapa SMS filter agent. Bagian pembelajaran dari sistem diletakkan pada SMS
16 processing center. Sedangkan bagian penyaringan SMS diletakkan pada SMS filter agent yang terdapat pada mobile phone. Pembaruan pengetahuan penyaringan dilakukan secara berkala, dengan cara SMS filter agent akan melaporkan SMS yang salah diklasifikasikan ke SMS processing center. Kemudian SMS processing center akan menggunakan informasi tersebut untuk melakukan
pembelajaran
untuk
mendapatkan
pembaruan
pengetahuan
penyaringan. Pembaruan pengetahuan penyaringan ini akan diunduh oleh SMS filter agent untuk kemudian digunakan pada penyaringan SMS selanjutnya. Terdapat atribut baru yang digunakan pada penelitian ini, yaitu panjang pesan dan beberapa aturan yang dibentuk oleh penulis. Tahap penelitian yang dilakukan adalah praproses, pemilihan atribut, penghitungan suatu pesan termasuk kelompok junk message atau legitimate message berdasarkan panjang pesan, penghitungan peluang setiap atribut aturan untuk kelompok junk message dan legitimate message, proses pelatihan dan klasifikasi menggunakan Naive Bayes. Tahap praproses dipecah menjadi beberapa langkah, yaitu tokenizing dan filtering. Pada penelitian ini atribut yang digunakan bukan hanya kata, tetapi juga digunakan atribut abstracting word. Abstracting word adalah rangkaian kata angka atau angka dengan huruf yang memiliki makna. Seperti rangkaian angka yang memiliki makna sebagai nomor telepon dan rangkaian angka dengan huruf yang memiliki makna jumlah uang. Untuk menemukan abstracting word digunakan teknik regular expression. Pemilihan atribut kata dan abstracting word dilakukan dengan menggunakan ukuran Mutual Information (MI). Dari penelitian yang dilakukan, mereka mendapatkan hasil bahwa penambahan atribut panjang dan aturan memberikan akurasi yang lebih tinggi dibandingkan dengan dengan penggunaan penyaringan Naive Bayes pada atribut kata saja. Hasil lainnya adalah konsumsi waktu yang dibutuhkan sistem untuk melakukan klasifikasi adalah kurang dari 3 detik dan proses yang paling banyak membutuhkan waktu adalah tokenizing.