Klasifikasi Teks Menggunakan K-NN

Pada pembahasan kali ini kita akan memelajari bagaimana cara melakukan Klasifikasi Teks Menggunakan k-NN (k-Nearest Neighbor). Dimana pada artikel sebelumnya, Term Weighting TF-IDF, kita telah mengenal cara skema pembobotan term pada dokumen.

Setelah bobot masing-masing dokumen diketahui, maka dilakukan proses pemeringkatan atau perankingan dokumen berdasarkan besarnya tingkat kerelevanan (kesesuaian) dokumen terhadap query, dimana semakin besar nilai bobot dokumen terhadap query maka semakin besar tingkat similaritas dokumen tersebut terhadap query yang dicari.

Contoh Kasus Sederhana Klasifikasi Teks Menggunakan k-NN

Diketahui terdapat 8 dokumen (D1 s.d D8) sebagai berikut :

D1: Tokoh politik dari berbagai partai mengadakan rapat untuk membahas koalisi baru menjelang pemilu 2014 dan beberapa pilkada 2012 dan 2013.
D2: Partai politik sudah tidak dapat dipercaya. Sebagian besar partai mengutamakan kepentingan partai daripada kebutuhan rakyat.
D3: Partai demokrat memenangkan pemilu 2009 karena figur SBY. Partai Golkar berusaha menang pada 2012. Pertandingan 2 partai ini akan seru.
D4: Pertandingan pertama antara Persema dan Persebaya diadakan di Malang. Ini akan menguntungkan tuan rumah.
D5: Sebagian besar wasit di Indonesia sulit dipercaya. Beberapa pertandingan sepakbola sering tidak adil. Tim nasional perlu pembenahan Total.
D6: Suap menyuap sudah lazim di negeri Ini. Pemilu ada suap. Pilkada juga suap. Mungkin pula saat Pilpres.
D7: Beberapa pertandingan sepakbola yang dilakoni persebaya pada masa kampanye Pilkada 2010 Kota surabaya akan ditunda.
D8: Sepakbola Indonesia memang belum bangkit. Manajemen tim, pertandingan dan tiket perlu ditingkatkan, bukan hanya fokus pada kemenangan tim.

Selanjutnya dokumen-dokumen teks tersebut dikelompokkan (classification) ke dalam dua kelas, C1 (Politik) dan C2 (Olahraga), menggunakan kecerdasan manusia, misalnya tiap kelas hanya boleh beranggotakan 3 dokumen, maka kita memperoleh hasil sebagai berikut :

• C1 akan beranggotakan D1, D2 dan D3
• C2 akan beranggotakan D4, D7 dan D8

Pada klasifikasi teks menggunakan k-NN, fase ini dinamakan fase manual atau training. Kita memilih beberapa dokumen contoh (sample) dan mengelompokkannya secara manual ke dalam kelas-kelas yang telah didefinisikan.

Dengan menggunakan k-NN, tentukan kelas dari dokumen D5

Langkah 1

Lakukan preprocessing terhadap semua (terdapat 7) dokumen yang terlibat, yaitu D5, D1, D2, D3, D4, D7 dan D8.

Langkah 1a – Lakukan tokenisasi, stop words removal dan stemming. Hasilnya diperlihatkan pada tabel berikut :

Dokumen Teks Setelah di Preprocessing (Semua Tanda Baca/Punctuation dihilangkan)

Langkah 1b – Tentukan bobot untuk setiap term dari 7 dokumen yang terlibat. Total dokumen ada 8. Dokumen yang telah terklasifikasi ada 6 dan yang akan diklasifikasikan D5 sehingga total yang terlibat adalah 7. Dokuman D6 tidak dilibatkan, belum terklasifikasi dan dapat dijadikan obyek pada klasifikasi berikutnya. Cara menentukan bobot untuk setiap term dapat dilihat pada tulisan lain yang berjudul Pembobotan Kata atau Term Weighting TF-IDF.

Tabel Term Weighting TF-IDF

Langkah 2

Hitung kemiripan vektor dokumen D5 dengan setiap dokumen yang telah terklasifikasi (D1, D2, D3, D4, D7 dan D8). Kemiripan antar dokumen dapat menggunakan cosine similarity. Rumusnya adalah sebagai berikut :

Rumus Cosine Similarity

Langkah 2a – Hitung hasil perkalian skalar antara D5 dan 6 dokumen yang telah terklasifikasi. Hasilnya perkalian dari setiap dokumen dengan D5 dijumlahkan (sesuai pembilang pada rumus di atas)

Langkah 2b – Hitung panjang setiap dokumen, termasuk D5. Caranya, kuadratkan bobot setiap term dalam setiap dokumen, jumlahkan nilai kuadrat tersebut dan kemudian akarkan. Sisi kiri dari tabel berikut ini mewakili langkah 2a dan sisi kanan memperlihatkan langkah 2b.

Perhitungan Langkah 2A dan 2B

Langkah 2c : Terapkan rumus cosine similarity. Hitung kemiripan D5 dengan D1, D2 dan seterusnya sampai dengan D8.

Cos (D5, D1) = 0/(2,458*2,652) = 0,000
Cos (D5, D2) = 0,3/(2,458*2,528) = 0,048

Dan seterusnya.

Cos (D5, D8) = 1,04/(2,458*2,312) = 0,184

Hasil perhitungan tersebut diperlihatkan tabel berikut :

hasil perhitungan langkah 2c

Langkah 3

Urutkan hasil perhitungan kemiripan, diperoleh :

hasil perhitungan langkah 3

Langkah 4

Ambil sebanyak k (k=4) yang paling tinggi tingkat kemiripannya dengan D5 dan tentukan kelas dari D5. Hasilnya :

hasil perhitungan langkah 4

Dokumen D5 terklasifikasi ke dalam kelas mana ? Pilih kelas yang paling banyak kemunculannya. Apakah C1? Atau C2? Ternyata, untuk k=4, C1 diwakili hanya oleh 1 dokumen yaitu D2,
sedangkan C2, diwakili 3 dokumen, yaitu D8, D7 dan D4.

Kemanakah D5 berlabuh? D5 terklasifikasi ke kelas C2 (Olahraga).

Contoh Kasus Lain

Bagaimana jika nilai cosin di atas seperti ini:

contoh data / nilai knn

Jika di ambil 4 (k = 4) dokumen paling dekat dengan D5, diperoleh D8, D2, D1, D7. Kelas C1 dan C2, masing-masing diwakili oleh 2 dokumen. Ke kelas manakah D5 terklasifikasi? Pada kasus demikian, ada beberapa solusi yang dapat ditempuh, yaitu:

1. Kurangi atau tambahkan k (sebesar 1)

2. K tetap 4, tidak berubah. Jumlahkan tingkat kemiripan dari setiap dokumen untuk kelas yang sama

Nilai C1 = nilai kemiripan (D5, D1) + nilai kemiripan (D5, D2) = 0,035 + 0,04
Nilai C2 = nilai kemiripan (D5, D8) + nilai kemiripan (D5, D7) = 0,184 + 0,03

Nilai C2 lebih besar. D5 harus masuk C2

Kesimpulan

D5 masuk ke dalam C1 atau C2? Jika melihat isi dari D5 maka kita dapat memutuskan bahwa isinya terkait erat dengan olahraga dan harusnya masuk ke dalam C2 (Olahraga), bukan C1, meskipun D5 juga mengandung term-term yang berhubungan dengan Politik (C1).

Pada banyak kasus, klasifikasi teks menggunakan k-NN, jika pemilihan awal (k=4) tidak memberikan solusi klasifikasi, maka dilakukan pengurangan atau penambahan k (sebesar satu). Pada pendekatan ini (sebagaimana di atas), D5 terklasifikasi ke dalam C2 (Olahraga). Pada banyak penelitian, nilai k adalah 3, 4 atau 5, dan terbukti memberikan hasil yang lebih baik.

Semoga artikel berjudul “Klasifikasi Teks Menggunakan K-NN” bisa bermanfaat dan silahkan jika masih ada yang kurang jelas dapat ditanyakan di kolom komentar dibawah ini.

Silahkan Like Fanspage dan Share artikel ini jika menurut kamu bermanfaat untuk kamu dan orang lain.

Artikel Lainnya