Analisis Komparatif Metode K-Means dan K-NN dalam Peringkasan Teks

 

Latar Belakang

Terdapat banyak teknik / metode yang dapat diterapkan untuk memuat sebuah sistem aplikasi peringkasan teks, setiap metode memiliki kelebihan dan kekurangannya masing masing dikarenakan alur dan tahapan tahapan di dalamnya yang memang berbeda, begitu juga dengan hasil ringkasan dari suatu metode akan berbeda dengan metode lainnya. Secara garis besar proses peringkasan terbagi menjadi 2 kategori berdaasarkan hasil yang dikeluarkannya, yaitu ekstraktif dan abstraktif, dalam pembahasan ini, yang digunakan adalah metode ekstraktif (K-means dan K- NN). Dalam kasus ini saya membandingkan 2 artikel dimana artikel pertama menggunakan metode K-means dan artikel kedua menggunakan metode K-NN. Artikel yang menggunakan metode K- means berjudul “Peringkasan Multi-dokumen berbasis clustering berbasis Sistem Temu Kembali Berita Online Menggunakan Metode K-means”, sedangkan yang menggunakan metode K-NN berjudul “Peringkasan Teks Otomatis Pada Artikel Berita Kesehatan Menggunakan K – Nearest Neighbor Berbasis Fitur Statistik”.

 

Peringkasan Teks

Proses menghasilkan teks yang berisi informasi inti yang bersifat penting dari teks sumber tanpa menghilangkan kandungan topic utama untuk memperkecil waktu yang dihabiskan pengguna    untuk membaca keseluruhan teks dalam proses pencarian informasi disebut peringkasan teks, sedangkan sistem yang melakukan aktivitas tersebut biasa disebut peringkas teks otomatis Dikategorikan menjadi 2 jenis berdasarkan hasil ringkasannya yaitu metode ekstraktif atau terkadang disebut juga dengan metode statistic, linguistic, dan heuristic (ringkasan dihasilkan dari sebagian kalimat yang terdapat dalam teks sumber dan metode abstraktif dimana ringkasan yang dihasilkan tidak sama persis dengan teks sumber tapi menginterpretasikan teks sumbernya

 

Preprocessing

Proses ini seolah sudah menjadi organ penting dari kedua metode tersebut (K-means dan K-NN). Terdapat beberapa tahapan preprocessing, akan tetapi dalam pembahasan ini yang digunakan hanya 2 yaitu tokenizing dan filtering. Kedua tahapan preprocessing tersebut dilakukan setelah melakukan case folding yaitu proses penyamaan karakter menjadi huruf besar maupun huruf kecil. Adapun tokenizing adalah proses membentuk kata-kata dari urutan karakter dalam suatu dokumen. Biasanya proses ini dilakukan dengan mendeteksi kumpulan karakter alphanumeric berukuran lebih dari tiga buah, yang diakhiri oleh spasi atau suatu karakter special^[3]. Kemudian filtering biasanya diartikan sebagai proses eliminasi berbagai kata yang tidak definitif / tidak mengandung informasi.

 

Term weighting with TF – IDF 

Sama halnya seperti preprocessing, TF – IDF adalah sesuatu yang tidak dapat dipisahkan jika kita membahas K-means dan K-NN, karena TF – IDF termasuk bagian penting dari kedua metode tersebut. Adapun definisi dari TF – IDF adalah suatu proses pembobotan terhadap setiap term / kata (term weighting) dalam teks / dokumen dimana bobot ini diperoleh dengan menghitung frekuensi kemunculan suatu term (kata) di suatu dokumen (Term Frequency/TF) dan kemungkinan suatu dokumen memiliki suatu kata (Inverse Document Frequency/IDF)^[4]. Beberapa variasi dari skema pembobotan TF-IDF sering digunakan dalam kasus information retrieval. Kemungkinan suatu dokumen memiliki suatu kata dapat dihitung dengan rumus yang terdapat pada persamaan berikut 

 

 

 

Dimana N adalah jumlah dokumen yang berisi term (t) dan df adalah jumlah kemunculan (frekuensi) term terhadap dokumen (D). Adapun algoritma yang digunakan untuk menghitung bobot (w) masing-masing dokumen terhadap kata kunci (query) menggunakan persamaan di bawah ini :

 

 

Cosine Simmilarity        

            Bersama dengan preprocessing dan TF – IDF (term weighting), cosine similiarity menjadi 3 pilar utama yang menopang konsep K-means dan K-NN, dimana cosine similiarity itu sendiri adalah proses pemodelan teks ke dalam suatu vektor term dan menghitung nilai cosine dari dua buah term dalam vektor yang terbentuk. Term yang digunakan dapat berupa kata, paragraf, atau bahkan keseluruhan teks sumber. Setelah melalui perhitungan, biasanya bobot Cosine akan diurutkan. Nilai cosine yang tinggi menunjukkan tingkat kesamaan yang besar. Dalam penelitian ini, Cosine Similarity dihitung dengan menggunakan Persamaan 3, dimana t menunjukkan indeks penunjuk term kalimat, Wt.b1 menunjukkan bobot term t dalam blok b1, dan Wt.b2 menunjukkan bobot term t dalam blok b2^[5].

 

K-Means

                 K-means digunakan digunakan untuk mendapatkan dekripsi dari sekumpulan data dengan cara mengungkapkan kecenderungan setiap individu data untuk berkelompok dengan individu-individu data lainnya. Kecenderungan pengelompokan tersebut didasarkan pada kemiripan karakteristik individu-individu data yang ada (Prilianti & Wijaya, 2014). Algoritma K-Means selanjutnya akan melakukan pengulangan langkah-langkah berikut sampai terjadi kestabilan (tidak ada obyek yang dapat dipindahkan) (Deshpande & L, 2013) 

 

1. Menentukan koordinat titik tengah setiap cluster

2. Menentukan jarak setiap obyek terhadap koordinat titik tengah

3. Mengelompokkan obyek-obyek tersebut berdasarkan pada jarak minimumnya

 

Rumus yang digunakan untuk menghitung jarak data dengan centroid adalah rumus Euclidean Distance. Adapun rumus Euclidean Distance dapat dilihat pada persamaan berikut :

Keterangan :

 

𝑑 = jarak data dengan centroid

𝑗 = banyaknya data

𝑘 = dimensi

𝑐 = centroid

𝑥 = data

 

K-NN

             Konsep dasar K-NN adalah mengelompokkan kategori pada query yang diberikan bukan hanya berdasar kedekatan dokumen terdekat dalam ruang dokumen, namun pada kategori dari k dokumen yang terdekat (Bijalwan dkk., 2014). Berikut merupakan langkah-langkah algoritma k- Nearest Neighbor antara lain:

 

1.      Masukkan data latih dan data uji

2.      Tentukan julah nilai k tetangga terdekat

3.     Hitung jarak antara data uji dengan data latih menggunakan Euclidian distance

4.     Urutkan hasil jarak berdasarkan nilai terkecil

5.     Mengambil data latih sejumlah k tetangga terdekat

6.     Menentukan kelas data baru berdasarkan mayoritas k tetangga terdekat.

 

Pada tahap ini, kalimat akan dipilih menjadi suatu ringkasan berdasarkan kedekatan jarak antara data uji ke data latih dengan mengacu pada nilai hasil ekstraksi fitur. Posisi kalimat hasil ringkasan akan sama urutannya dengan kalimat asli dari dokumen (Desai & Shah, 2016)^[7].

 

Alur

 

·         K-NN

 

·         K-Means

 

 

 

Kesimpulan

 

o    Kedua metode peringkasan teks atau dokumen tersebut memiliki alur / tahapan yang sama secara garis besar

 

       Referensi/ Jurnal Yg di Review 

 

1. Akaresti, Amalia Kusuma, Mochammad Ali Fauzi, and Fitra Abdurrachman Bachtiar. "Peringkasan Multi-Dokumen Berbasis Clustering pada Sistem Temu Kembali Berita Online Menggunakan Metode K-Means." Jurnal Pengembangan Teknologi Informasi dan Ilmu Komputer e-ISSN 2548 (2018): 964X.

 

2. Indrianto, Rachmad, M. Ali Fauzi, and Lailil Muflikhah. "Peringkasan Teks Otomatis Pada Artikel Berita Kesehatan Menggunakan K-Nearest Neighbor Berbasis Fitur Statistik." Jurnal Pengembangan Teknologi Informasi dan Ilmu Komputer 1.11 (2017): 1198-1203.