PENGGUNAAN KNN (K-NEARST NEIGHBOR) UNTUK KLASIFIKASI TEKS BERITA YANG TAK-TERKELOMPOKKAN PADA SAAT PENGKLASTERAN OLEH STC (SUFFIX TREE CLUSTERING)

Edisi Juni 2015 Volume IX No. 1

ISSN 1979-8911

PENGGUNAAN KNN (K-NEARST NEIGHBOR) UNTUK KLASIFIKASI TEKS BERITA YANG TAK-TERKELOMPOKKAN PADA SAAT PENGKLASTERAN OLEH STC (SUFFIX TREE CLUSTERING) Jumadi, Edi Winarko

Abstrak Dokumen teks yang dipublikasi di internet dari hari ke hari semakin banyak jumlahnya. Salah satu teknologi internet yang paling sering terjadi proses pemuktahiran konten dokumen teks ini, adalah microblogging yang dijadikan sebagai sarana untuk membangun komunitas di dunia maya dan penyebar informasi yang praktis dan cepat. Salah satunya adalah Twitter yang merupakan salah satu social media dengan jumlah tweet yang dipublikasi dalam hitungan jam oleh para pemilik akun tersebut, khususnya para jurnalis. Berita-berita yang dipublikasi oleh para jurnalis melaui Twitter terkadang kurang nyaman untuk dibaca oleh para pembaca berita. Karena berita-berita tersebut ditampilkan secara tersusun beruntun ke bawah pada halaman web tersebut. Tetapi setelah tweet-tweet yang ada dikelompokkan secara tematik jadi semakin menarik karena pembaca dapat memilih berita-berita tertentu yang telah dikelompokkan oleh Algoritma Suffix Tree Clustering (STC). Tetapi pada algoritma ini, masih tetap menghasilkan dokumen-dokumen yang tidak memiliki kelompok. Pada Penelitian ini, dokumen-dokumen tersebut mencoba untuk di klasifikasikan ke dalam kelompok yang ada dengan menggunakan Algoritma K-Nearset Neighbor (KNN). Kata-kata kunci: Clasification, Clustering, TF-IDF, KNN, STC

ini

Pendahuluan Berdasarkan

penelitian

yang

dilakukan oleh Zamir dan Etzioni (1998), algoritma yang digunakan untuk melakukan pengklastran dokumen web kali

pertama

adalah

Suffix

Tree

Clustering (STC), algoritma klasterisasi

memiliki

waktu

mengelompokkan

linear

dalam

dokumen

hasil

pencarian ke dalam bentuk group-group atau klaster berdasarkan kata atau frase yang terdapat di dalam dokumen yang ada. Kemudian Osiński

dan Weiss

(2004), mengembangkan Open Source Framework

dengan

nama

Carrot2. 50


ISSN 1979-8911

Kesuksesan dan popularitas aplikasi

sering dijumpai banyak dokumen yang

Carrot2 adalah mengorganisir hasil dari

tidak terkelompokkan. Mengacu pada

pencaraian di internet agar lebih mudah

konsep yang dibahas oleh Liao (2002),

dalam

bentuk

untuk mengatasi permasalahan ini perlu

pengelompokan secara tematik hasil

adanya proses klasifikasi dokumen teks

pencarian

menggunakan

tersebut denga Algoritma K-NN ke

browser internet, yang dikenal dengan

dalam kelompok yang terbentuk oleh

proses klasterisasi.

Algoritma STC sebelumnya.

menjelajah

pada

digunakan

dalam

saat

Algoritma

dalam

yang proses

Teori pengelompokan ini, diantaranya adalah Algoritma

Suffix

Tree

Clustering

menggunakan algoritma Suffix Tree (STC) Clustering. Selanjutnya, penelitian yang Inti dari suatu hasil pencarian telah dilakukan oleh Arifin dkk.(2008), yang menerapkan clustering adalah dengan menggunakan Algoritma Suffix penggunaan

algoritma

clustering.

Tree Clustering dalam pengelompokkan Algoritma Suffix Tree Clustering (STC) berita

dalam

Bahasa

Indonesia, memiliki dua kunci utama, yaitu :

memiliki tingkat precision yang sangat 1. Menggunakan phrase sebagai tinggi, yaitu 80%.Hal ini dikarenakan dasar pembentukan clusternya. dalam Algoritma ini, menggunkaan 2. phrase

sebagai dasar

Menggunakan

suatu

definisi

pembentukan cluster sederhana.

cluster. Suffix Tree Clustering memiliki Tetapi, kinerja algoritma STC 2

dua langkah utama. Dalam langkah

yang dikembangkan oleh Carrot masih pertama, pencarian shared phrase untuk memiliki kekurangan.

Hasil proses semua dokumen berita yang dikoleksi.

pengklasteran dengan algoritma ini, 51


ISSN 1979-8911

Kita menyebut shared phrase sebagai

pengelompokkan dokumen berdasarkan

phrase cluster atau base cluster, yang

phrase. Phrase juga bermanfaat untuk

ditemukan dengan menggunakan suatu

membangun uraian dan keakuratan

struktur data yang dinamakan suffix

deskripsi dari klaster. Kedua, tidak

tree.

kita

tergantung pada model data. Hal itu

mengkombinasikan base cluster-base

mengasumsikan hanya dokumen dengan

cluster

topik yang sama yang akan memiliki

Dalam

ke

langkah

dalam

kedua,

suatu

klaster.

Penggabungan antar dua base cluster

shared

phrase.

Ketiga,

didasarkan pada jumlah dokumen yang

memperbolehkan

melakukan overlap diantara kedua base

cluster. Hal itu sangat penting untuk

cluster tersebut (Zamir &

Etzioni,

menghindari pembatasan bahwa setiap

1998). Suatu phrase yang dimaksud

dokumen hanya memiliki satu klaster

dalam konteks algoritma ini adalah

saja, karena sering kita jumpai satu

urutan satu atau lebih kata-kata. STC

dokumen mempunyai lebih dari satu

memiliki tiga langkah utama, yaitu :

topik,

adanya

dengan

overlaping

demikian

kemiripan

2.Identifikasi

kelompok dokumen. Keempat, STC

cluster

menggunakan suffix tree.

menggunakan

3. Mengkombinasikan base cluster ke dalam suatu cluster. Beberapa

lebih

terdapat

1. Pembersihan (cleaning) dokumen. base

yang

STC

dari

definisi klaster

satu

yang

sederhana. Semua dokumen yang berisi salah satu phrase cluster akan menjadi

yang

anggota dari klaster tersebut. STC

membuat Suffix Tree Clustering cocok

menggunakan phrase untuk mendeteksi

digunakan

kemiripan

dokumen.

karakteristik

untuk

pengelompokkan

Pertama

adalah

membangkitkan klaster-klaster untuk

antar

menggunakan

dokumen.

suffix

tree

STC untuk

mengidentifikasi phrase. Fitur yang 52


membuat

suksesnya

STC

ISSN 1979-8911

sebagai

Algoritma stemming untuk Bahasa

algoritma clustering adalah adanya

Indonesia dengan nama Porter Stemmer

overlaping cluster.

Kualitas klaster

for Bahasa Indonesia dikembangkan

yang terbentuk dari algoritma STC ini

oleh Talla (2003) dan implementasi

akan menurun jika tanpa menggunakan

berdasarkan English Porter Stemmer

multiword

tidak

yang dikembangkan oleh Frakes (1992).

overlaping

Beberapa modifikasi Porter Stemmer

phrase

memperbolehkan

dan

adanya

cluster.

Bahasa Inggris telah dilakukan agar

Pembersihan

dokumen

(document

dapat digunakan untuk mengolah teks Bahasa

cleaning) Document

Cleaning

Indonesia.

Rancangan

adalah

algoritmaPorter Stemmer for Bahasa

tahap awal dalam algoritma Suffix tree

Indonesia dapat dilihat pada Gambar 1.

Clustering. Pada tahap ini, dokumen

Algoritma Porter stemming for Bahasa

yang telah didapat dari proses download

Indonesia bekerja berdasarkan struktur

akan

dipersiapkan

kata Bahasa Indonesia. Struktur kata

untuk tahap selanjutnya. Proses untuk

pada Bahasa Indonesia terdiri dari

mempersiapkan

prefix, root, suffix, possessive_pronoun

dibersihkan

dan

dokumen

meliputi

proses pembersihan dokumen dari tag-

dan

tag HTML, proses analisa leksikal teks,

dimaksud

proses

opsional kata dalam format:

penghapusan stopword,

dan

proses stemming.

particle.

Struktur

ditulis

dalam

kata

yang

rangkaian

[prefix1]+[prefix2]+root+[suffix]+[poss essive_pronoun]+[particle]

Stemming

dalam

Bahasa

Indonesiadengan Algoritma Porter

53


ISSN 1979-8911

Tabel 2 Peraturan kedua untuk inflectional possesive pronouns (Talla, 2003) Suffix Replacement Measure Additional Examples Condition Condition ku NULL 2 NULL bukukubuku

Gambar 1 Rancangan dasar Porter

mu

NULL

2

NULL

bukumubuku

nya

NULL

2

NULL

bukunyabuku

Stemmerfor Bahasa Indonesia (Talla, 2003)

Tabel 3 Peraturan untuk first order of derivational prefixes (Talla, 2003)

Pada Gambar 1 terlihat beberapa langkah removal menurut aturan yang

Suffi x

ada pada Tabel 1 sampai dengan Tabel 5. Dengan demikian algoritma Porter Stemming

for

Bahasa

Indonesia

terdapat 5 langkah pengecekan untuk

Men g Men y Men

melakukan proses removal sehingga Men

Repla Mea Addi ceme sure tiona nt Con l ditio Con n ditio n NUL 2 NUL L L s 2 v… NUL L t

2 2

NUL L v…

2

v…

2

NUL L NUL L NUL L v…

mampu mendapatkan kata dasar (root) Mem p pada kata-kata teks Bahasa Indonesia. Mem NUL L Me NUL inflectional particles (Talla, 2003) L Peng NUL Replacement Measure Additional Examples L Condition Condition Peny S NULL 2 NULL bukukahbuku NULL 2 NULL dialahdiaPen NUL NULL 2 NULL bukupunbuku L Tabel 1 Peraturan pertama untuk

Suffix kah lah pun

2 2 2 2

NUL L

Examples

mengukur ukur menyapus apu mendugad uga menuduht uduh memilahp ilah membaca baca merusakru sak pengukur ukur menyapus apu pendugad uga 54


Pen

T

2

v…

Pem

P

2

v…

Pem

NUL L NUL L NUL L NUL L

2

NUL L NUL L NUL L NUL L

Di Ter Ke

2 2 2

penuduhtu duh pemilahpi lah pembacab aca diukuruku r tersapusap u kekasihka sih

ISSN 1979-8911

n

{ke, peng}

an

NUL

2

i

NUL

2

tarik (meng) ambilkan ambil prefix makanan {di, makan meng, (per) ter} janjianja nji V|K…c Tandait anda 1c2, (men) c1s, c2i dapatida and  pat {ber, warnaw ke, arnai peng}

Tabel 4 Peraturan keempat untuk second order of derivational prefixes (Talla, 2003)

Identifikasi BaseCluster Suffi x

Repla ceme nt

Ber

Mea sure Con ditio n NULL 2

Additi Examples onal Condi tion

Bel

NULL 2

NUL L ajar

Be

NULL 2

k*er..

Per

NULL 2

Pel

NULL 2

NUL L ajar

Pe

NULL 2

NUL L

berlarila ri belajaraj ar bekerjak erja perjelasjelas pelajaraj ar pekerjak erja

Tabel 5 Peraturan kelima untuk derivational suffixes (Talla, 2003) Suf Repl Meas fix acem ure ent Condi tion ka NUL 2

Additio nal Conditi on prefix

Examples

Tahap identifikasi base cluster merupakan

terpenting

dalam

algoritma suffix tree clustering, karena pada tahap ini akan menghasilkan klaster-klaster dasar (Zamir & Etzioni, 1998).

Pembentukkan

basecluster

dilakukan dengan cara menemukan share phrase antar dokumen. Untuk menemukan share phrase digunakan struktur

data

suffix

tree.

Dengan

menggunakan struktur data ini, maka setiap dokumen akan direpresentasikan menjadi

Tarikkan

tahap

menemukan

suatu base

kalimat. cluster

Untuk dapat 55


ISSN 1979-8911

dilakukan dengan cara membuat suatu

Tabel 6. Base cluster yang terbentuk

invert index dari phrase untuk semua

(Zamir & Etzioni, 1998)

dokumen. Pembentukkan suffix tree untuk kalimat cat ate cheese, mouse ate cheese too, dan cat ate mouse too diperlihatkan pada Gambar 2 yang

Base Cluster a b c d e f

menunjukkan adanya internal node yang terbentuk.

Setiap

merepresentasikan

internal

terbentuk

Documents

cat ate ate cheese mouse Too ate cheese

1, 3 1, 2, 3 1, 2 2, 3 2, 3 1, 2

base

memiliki

cluster

yang

suatu

score.

kelompok

Penghitungan score merupakan suatu

dokumen dan share phrase untuk

fungsi dari jumlah dokumen yang

kelompok tersebut. Oleh karena itu,

masuk anggota base cluster dan jumlah

setiap

juga

kata yang menyusun phrase dari base

yang

cluster. Fungsi untuk menghitung skor

internal

merepresentasikan

suatu

node

Setiap

Phrase

node basecluster

terbentuk. Semua base cluster yang

base

terbentuk dapat ditunjukkan pada Tabel

Persamaan (1).

6.

s(B)

cluster

ditunjukkan

=

oleh

|B|.f(|P|)

(1) dimana pada Persamaan (1) : |B| adalah jumlah dokumen di dalam base cluster B dan |P| adalah jumlah kata yang menyusun Gambar 2 Generate Suffix Tree (Zamir & Etzioni, 1998)

frase P. f(|P| = 0, jika |P| = 1 dan f(|P| = 6, jika |P| = 6 56


ISSN 1979-8911

|Bm| dan |Bn| masing-masing adalah

Kombinasi Base Cluster Tahap

ini

digunakan

untuk

menangani overlaping cluster. Dalam tahap ini, phrase tidak dipertimbangkan.

jumlah dokumen dalam base cluster Bm dan Bn. Dalam Persamaan 2 dan 3,

Sebelum melakukan kombinasi antar

menunjukkan

basecluster (Zamir & Etzioni, 1998),

threshold 0,5 karena nilai tersebut

kita

nilai

merupakan nilai tengah antara 0 sampai

similiarity antar base cluster yang

1. Jika Persamaan (2) dan (3) bernilai

didasarkan pada jumlah dokumen yang

benar maka similiarity akan bernilai 1

overlap. Adanya overlaping dokumen

sehingga antara kedua base cluster

ini

dokumen

tersebut akan terhubung. Jika salah satu

memiliki lebih dari satu topik sehingga

dari Persamaan (2) dan (3) bernilai

dokumen dapat memiliki lebih dari satu

benar atau keduanya bernilai salah maka

shared phrase.

similiarity akan bernilai 0 sehingga

harus

menghitung

didasarkan

Ukuran

karena

nilai

dulu

penggunaan

nilai

similiarity

antara kedua base cluster tersebut tidak

menggunakan nilai biner. Rumus untuk

terhubung. Keterhubungan antar base

menghitung nilai similiarity antar base

cluster dapat diceritakan dalam bentuk

cluster ditunjukkan pada Persamaan (2)

base cluster graph yang ditunjukkan

dan (3)

pada Gambar 3

|BmBn| / |Bm| > 0,5

(2)

|BmBn| / |Bn| > 0,5

(3)

dengan |BmBn| adalah jumlah dokumen yang overlap terhadap base cluster Bm dan Bn.

Gambar 3 Base Cluster Graph (Zamir & Etzioni, 1998) 57


ISSN 1979-8911

Dari Gambar 3 menunjukkan

Algoritma

Nearest

bahwa antar base cluster terhubung

Neighbormerupakan

sehingga dari 6 base cluster tersebut

melakukan

akan membentuk satu cluster tunggal.

kedekatan lokasi (jarak) suatu data

Untuk pembentukkan cluster digunakan

dengan data yang lain. Klasifikasi

algoritma single link dimana nilai

merupakan suatu pekerjaan menilai

similiarity minimal antar base cluster

objek

sebagai

kedalam kelas tertentu dari sejumlah

kriteria

berhenti.

Kita

menggunakan algoritma ini, digunakan

ini

hanya

menemukan

klasifikasi

data

untuk

yang

berdasarkan

memasukkannya

kelas yang tersedia.

dalam domain base cluster dimana algoritma

algoritma

Tujuan dari algoritma Nearest Neighbor

adalah

mengklasifikasikan

keterhubungan antara base cluster yang

obyek baru bedasarkan atribut dan

terkecil.

training sample. Diberikan suatu titik

Nearest Neighbor

query,

selanjutnya

akan

ditemukan

Nearest Neighbor merupakan

sejumlah K obyek atau (titik training)

suatu pengelompokkan suatu data baru

yang paling dekat dengan titik query.

berdasarkan jarak data baru ke beberapa

Nilai prediksi dari query instanceakan

data atau tetangga terdekat (Santosa,

ditentukan

2007:53). Menurut Kusrini dan Luthfi,

ketetanggaan.

(2009:94) Nearest Neighbor adalah

Pada

berdasarkan

algoritma

klasifikasi

Nearest

suatu pendekatan untuk mencari kasus

Neighbor, jarak antara satu data ke data

dengan menghitung kedekatan antara

yang lain dapat dihitung. Nilai jarak

kasus baru dengan kasus lama, yaitu

inilah yang digunakan sebagai nilai

berdasarkan pada pencocokan bobot

kedekatan atau kemiripan antara data uji

dari sejumlah fitur yang ada.

dengan data latih. Nilai K pada Nearest 58


ISSN 1979-8911

Neighbor berarti K-data terdekat dari

dengan jumlah yang sama tersebut

data uji. Gambar 5 memberikan contoh

secara acak.

algoritma

Nearest

Neighbor,

tanda

lingkaran untuk kelas 0, tanda plus untuk kelas 1. Seperti yang ditunjukan pada Gambar 3.4 (a), jika K bernilai 1, kelas dari 1 data latih sebagai tetangga terdekat (terdekat pertama) dari data uji

Gambar 4 K- Nearest Neighbor dengan nilai k-tetangga terdekat (Kusrini dan Luthfi, 2009)

tersebut akan diberikan sebagai kelas untuk data uji, yaitu kelas 1 . Jika K Salah

bernilai 2, akan diambil 2 tetangga terdekat dari data latih. Begitu juga jika nilai K adalah 3,4,5 dan sebagainya. Jika dalam K-tetangga ada dua kelas yang berbeda, akan diambil kelas dengan jumlah data terbanyak (voting mayoritas), seperti yang ditunjukan pada Gambar 3.4 (c). Pada Gambar Gambar 4 (c) terlihat bahwa kelas 0 mempunyai jumlah yang lebih banyak daripada kelas 1 sehingga kelas 1 akan dikategorikan kedalam kelas 0. Jika kelas dengan data terbanyak ada dua atau lebih, akan diambil kelas dari data

dihadapi

satu

Nearest

masalah Neighbor

yang adalah

pemilihan nilai K yang tepat. Cara voting mayoritas dari K-tetangga untuk nilai K yang besar bisa mengakibatkan distorsi data yang besar, seperti yang ditunjukkan pada Gambar 3.5. misalnya diambil K bernilai 13, pada Gambar 3.5, kelas 0 dimiliki oleh 7 tetangga yang jauh, sedangkan kelas 1 dimiliki oleh 6 tetangga yang lebih dekat. Hal ini karena

setiap

tetangga

mempunyai

bobot yang sama terhadap data uji, sedangkan K yang terlalu kecil bisa

59


ISSN 1979-8911

menyebabkan algoritma terlalu sensitif

dokumen, yang biasanya merupakan

terhadap noise.

string

karakter,

menjadi

sebuah

representasi yang cocok untuk algoritma pembelajaran pengklasifikasian.

dan

tugas Representasi

dokumen yang paling umum digunakan Gambar 5 K- Nearest Neighbor dengan

adalah Vector Space Model (VSM).

nilai K yang besar (Kusrini dan Luthfi,

Dalam model ini, setiap dokumen direpresentasikan/diwakilkan

2009) Metode

Pengelompokkan

Teks

Pengkategorian teks Liao (2002) proses

kata-kata.

Matriks

A yang

merupakan kata-berdasarkan-dokumen

Menggunakan Nearest Neighbor

adalah

vektor

oleh

pengelompokkan

digunakan sebagai koleksi dokumen, contohnya

dimana

dokumen teks menjadi satu atau lebih

adalah bobot dari kata i pada dokumen j.

kategori

Ada beberapa cara untuk menentukan

yang

telah

ditetapkan

berdasarkan isi kontennya. Sejumlah

bobot

. Pada saat ini, berasumsikan

teknik klasifikasi statistik dan mesin

merupakan frekuensi kata i pada

pembelajaran telah diterapkan untuk

dokumen j. N adalah jumlah dokumen

pengkategorisasian

teks,

dalam koleksi, M adalah jumlah kata

adalahRegression

Model,

Classifier,

Decision

diantaranya

yang berbeda dalam koleksi, dan

Nearest

adalah total banyaknya kata i muncul di

Neighbor Classifier, Neural Networks,

seluruh koleksi. Pendekatan yang paling

danSupport Vector Machines (SVM).

sederhana adalah pembobotan boolean,

Langkah

Tree,

Bayesian

pertama

dalam

yang

menetapkan

bobot

dari

pengkategorian teks adalah mengubah 60


ISSN 1979-8911

menjadi 1 jika kata tersebut muncul

(penghapusan

dalam

dokukmen

dan

sebaliknya.

Pendekatan

sederhana

adalah

frekuensi

kata

dan

teknik

0

untuk

pengurangan dimensi tambahan, seleksi

lain

yang

fitur atau re-parameterisasi, biasanya

menggunakan

dalam

contohnya

suffix),

digunakan.

dokumen,

. Pendekatan bobot

Untuk

mengklasifikasi

class-

unknown pada dokumen X, algoritma

yang lebih umum adalah pembobotan tf

pengklasifikasian

k-Nearest

- idf (term

mengurutkan/merangking

dokumen

frequency - inverse

tetangga

document frequency):

diantara

vektor-vektor

dokumen pelatihan, dan menggunakan

(4)

label kelas dari k-tetangga paling mirip Sedikit

variasi

Kwok

(1998)

dari untuk memprediksi kelas dokumen baru.

pembobotan

tf

-

idf

,

yang Kelas-kelas tetangga ini dibobot dengan

memperhitungkan

kemungkinan menggunakan persamaan dari masing-

dokumen-dokumen memiliki panjang masing

tetangga

ke

X,

di

mana

yang berbeda, adalah sebagai berikut : persamaan

diukur

dengan

jarak

(5) Euclidean atau nilai kosinus antara dua Untuk matriks A, jumlah baris sesuai dengan jumlah kata M dalam koleksi dokumen. Mungkin ada ratusan ribu

kata

yang

vektor dokumen. Persamaan kosinus didefinisikan sebagai berikut: (6)

berbeda.Untuk dimana X adalah dokumen tes, yang

mengurangi

dimensi

yang

tinggi, direpresentasikan sebagai suatu vektor;

penghapusan stop-word (kata-kata yang adalah dokumen pelatihan ke j; sering muncul yang tidak membawa informasi),

word

stemming

adalah kata yang berasal dari X dan

;

61


adalah bobot dari kata adalah

bobot

dari

ISSN 1979-8911

tokenizing, penghapusan stop word dan

dalam X;

kata

dalam

dokumen

; adalah

normalisasi dari X, dan

adalah

stoplist serta stemming for Bahasa Indonesia.

Hasil

praproses

akan

disimpan pada media penyimpanan yang ada karena akan digunakan juga pada proses klasifikasi. Pada kasus ini,

normalisasi dari

. dokumen-dokumen

Hasil dan diskusi

algoritma

D1: @mcsugm Sugeng bertemu

Suffix

dengan

Tree

Edwinhttp://t.co/ri0IffQ7qe

Clustering (STC)

D2: Rini menemui Edwin juga

Pada proses ini, akan dijelaskan tahapan-tahapan pengelompokkan data

D3:

dengan

menemui Rini juga

menggunakan

pengklasteran

(clustering)

sistem

@mcsugm

Sugeng

Tokenizing Tujuan dari tokenizing adalah

Clustering (STC). Tahap pertama: Memfrase dokumen Tahap pertama yang dilakukan adalah menyiapkan dokumen teks yang akan dikelompokkan menjadi klasterklaster. Sebelum dokumen diproses lebih lanjut, dokumen tersebut harus praproses

RT

dengan

menggunakan algoritma Suffix Tree

melalui

menjadi

contoh adalah sebagai berikut:

Proses perhitungan secara manual pada

yang

yang

meliputi;

untuk memecah kalimat menjadi kata perkata secara terpisah yang dikenal dengan term. Hasil dari proses ini, adalah D1:

@mcsugm Sugeng bertemu dengan Edwin http://t.co/ri0IffQ7qe

62


D2:

ISSN 1979-8911

Rini menemui Edwin juga

Proses penghapusan stoplist Proses menghilakan

D3:

RT @mcsugm Sugeng menemui Rini juga

ini

bertujuan

kata-kata

yang

untuk tidak

bermanfaat atau tidak mempengaruhi proses utama. Kata-kata yang masuk dalam kategori ini, diantaranya tanda baca, karakter dan kata khusus pada

Penghapusan stopword twitter yang telah didefinisikan sebagai Proses

ini

bertujuan

untuk stoplist. Hasil dari proses ini, adalah

menghilangkan kata-kata yang tidak D1:

Sugeng bertemu Edwin

D2:

Rini menemui Edwin

D3:

Sugeng menemui Rini

bermanfaat atau tidak mempengaruhi proses utama. Kata-kata yang masuk dalam kategori ini, diantaranya tanda baca, karakter dan kata khusus pada twitter yang telah didefinisikan sebagai stopword. Hasil dari proses ini, adalah

Stemming D1:

Sugeng bertemu dengan Edwin

Proses

stemming

bertujuan

untuk mendapatkan kata dasar dari kata kerja yang telah mendapatkan imbuhan

D2:

D3:

Rini menemui Edwin juga Sugeng menemui Rini juga

atau

keterangan

Stemming

for

lainnya. Bahasa

Porter Indonesia

merupakan algoritma stemming yang digunakan

pada

praproses.

Pada

implementasinya hasil stemming ini

63


ISSN 1979-8911

dicek pada Daftar Kata Dasar yang ada.

dalam rangkaian opsional kata dalam

Hasil dari stemming ini, adalah

format:

D1:

D2:

D3:

Sugeng temu Edwin

+[possessive_pronoun]+[particle]

Rini temu Edwin

Tahap kedua: Mengidentifikasi frase

Sugeng temu Rini Secara

[prefix1]+[prefix2]+root+[suffix]

dokumen Pada tahap ini, hal utama yang keseluruha

proses dilakukan adalah mentukan kata sebagai

stemming

dngan

menggunakan base

cluster

dan

menentukan

algoritma Porter Stemming for Bahasa hubungannya dengan kata yang lainnya Indonesia dapat dilihat pada Gambar 1 pada dokumen yang ada. Alat yang Berdasarkan Gambar

1 yang digunakan dalam proses ini, dalam

menjelasakan 5 (lima) proses stemming mempresentasikan term-term yang ada yang terjadi pada algoritma Porter pada setiap dokumen, adalah struktur stemming for Bahasa Indonesia. Prosesdata Suffix Tree. proses yang ada berkaitan dengan Dokumen-dokumen yang telah penerapan 5 (lima) aturan yang ada melalui praproses selanjutnya akan pada algoritma ini. Algoritma Porter direpresntasikan dalam bentuk pohon stemming for Bahasa Indonesia bekerja Suffix berdasarkan

struktur

kata

Tree.

Dokumen

yang

akan

Bahasa digunakan pada proses init, adalah

Indonesia. Struktur kata pada Bahasa D1: Sugeng temu Edwin Indonesia terdiri dari prefix, root, suffix, D2: Rini temu Edwin possessive_pronoun

dan

particle. D3: Sugeng temu Rini

Struktur kata yang dimaksud ditulis

64


ISSN 1979-8911

Hasil dari pemodelan dari ketiga

dari |B| merupakan jumlah dokumen

dokumen tersebut, dapat dilihat pada

dalam base-cluster, dan f(|P|) adalah

Gambar 6

jumlah kata yang menyusun frase P.

Tahap ketiga: Menggabungkan Base Cluster Tahap ini, bertujuan menentukan

Gambar 6 Pembentukan Suffix Tree

klaster-klaster

yang

dengan

menggabungkan

cara

akan

dibentuk base

cluster yang ada sesuai dengan aturan Hasil analisis dari Gambar 4.2

similarity yang ada. Penjelasan aturan

dapat dilihat pada Tabel 7. Hasil ini,

ini,

berupa

antara

memperhatikan pada simpul a, terdapat

simpul, frase yang ada dan dokumen

2 buah dokumen yang berhubungan,

yang terlibat.

maka ditulis |Ba|=2, yaitu D1 dan D2.

rekapan

keterkaitan

dapat

dimulai

dengan

Tabel 7 Hubungan antara Simpul dan

Sedangkan pada simpul b, terdapat 3

Frase serta dokumen

buah dokumen, sehingga ditulis |Bb|=3,

No Simpul Frase 1 A Edwin 2 B Temu

Skor 2 3

yaitu D1, D2 dan D3. Kedua simpul,

3

C

4

himpunan

4 5

D E

1 2

dokumen yang berada di kedua simpul a

Dokumen D1, D2 D1, D2, D3 Sugeng D1, D3 temu Rini D2 temu D1, D2 Edwin

yaitu a dan b. Jika dioperasikan irisan maka

dapat

diperoleh

dan b. Dengan demikian dapat diperoleh |BaBb|=2, yaitu D1 dan D2 terdapat

Nilai skor s(B) diperoleh dengan pada kedua simpul. Pada akhirnya nilai rumus, |B| dikali dengan f(|P|). Nilai similarity

kedua

dokumen

dapat 65


ISSN 1979-8911

diketahui dengan menggunakan rumus untuk menentukan keterhubungan kedua simpul tersebut, dengan syarat sesuai Persamaan (2) dan (3). Pada

kasus

ini,

|BaBb|/|Ba|=2/2=1,

dan

|BaBb|/|Bb|=2/3=0.67 demikiam

kedua

dengan

simpul

memiliki

similarity, jadi antara simpul a dan b berhubungan dan dapat berada dalam satu klaster atau kelompok. Rekap perhitungan dengan rumus similarity antar term-term pada dokumen yang ada, dapat dilihat hasil secara keseluruhan

Tabel 8 Nilai Similarity antar Simpul a 0.67 0.50 0.50 1.00

Tabel

Rancangan

Proses

Perhitungan

secara Manual pada Algoritma Nearest Neighbor Perhitungan algoritma

Nearst

manual

pada

Neighbor

dengan

menggunakan dokumen teks anggota klaster Other Topics sebagai inputannya, akan dijelaskan secara detail yang

pada Tabel 8

Simpul A B C D E

Gambar 7 Graph Klaster Frase

b 1.00 1.00 1.00 1.00

8

c 0.50 0.67 0.50 0.50

d 0.50 0.67 1.00 1.00

menunjukan

e 1.00 0.67 1.00 0.50 -

nilai

similarity antar simpul-simpul yang ada. Sehingga nilai-nilai yang berkaitan ini, dapat direpresentasikan dalam bentuk graph seperti tertera pada Gambar 7

meliputi deskripsi input, proses dan output yang dihasilkannya. Kumpulan

teks

sebagai

inputan

untuk Algoritma Nearst Neighbor Data

yang

digunakan

pada

proses klasifikasi dengan menggunakan algoritma Nearest Neighbor, merupakan hasil dari proses pengklasteran oleh pustaka

Carrot2

menggunakan

algoritma Suffix Tree Clustering (STC). 66


Tabel

4.3

berisi

kumpulan

ISSN 1979-8911

teks

23 24

bebahasa Indonesia sebagai data inputan 25 awal pada sistem pengelompokkan. Tabel 9 Kumpulan data teks No 1 2 3 4

Data Sugeng bertemu dengan Edwin Rini menemui Edwin juga Sugeng menemui Rini juga UGM singkatan dari Universitas Gadjah Mada Tabel 9 Kumpulan data teks (lanjutan)

26 27 28 29 30 31 32 33 34

No 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

21 22

Data UGM berlokasi di Yogyakarta UGM mempunyai Jurusan Ilmu Komputer Mahasiswa sering mendapatkan cemilan di Kantin Mahasiswa sering menjelajah internet di perpustakaan UGM memiliki akun twitter Jurusan Ilmu Komputer memiliki akun twitter juga Sugeng dan Rini pergi ke kantor setiap hari Sugeng sedang duduk di atas kursi sekarang Yogyakarta berlokasi di pulau Jawa Muiz menyukai kopi Muiz memiliki mobil baru Muiz adalah seorang guru Yoyok berbicara Bahasa Inggris dengan lancer Yoyok bukan guru kursus Bahasa Inggris Kuncoro telah pergi belanja kemarin Yoyok berbicara Bahasa Inggris dan Sugeng berbicara Bahasa Jawa Setelah Akas mendapatkan sarapan, dia pergi ke sekolah Akas dan Ocha pergi ke Bandung

35 36 37 38 39 40

Cibaduyut berlokasi di Bandung Akas dan Dika sedang bermain game Ada pohon jeruk di kebunnya Akas Akas telah dilahirkan di Bandung Ocha telah dilahirkan di Bandung Keukeu pernah ke kota Pemalang Kota Pemalang berlokasi di Jawa Tengah Ocha memiliki kucing dan ikan Kucing memakan ikan Tikus memakan ikan Akas dan Ocha berbicara Bahasa Sunda Akas pergi ke sekolah dengan mobil Akas ingin menjadi dokter Akas dan ibunya pergi ke Yogyakarta Akas memiliki saudara Yoyok dilahirkan di Yogyakarta Yoyok memiliki akun twitter Pemerintah Yogyakarta memiliki akun twitter dan facebook

Hasil proses pembentukan klaster oleh STC Kumpulan data berjumlah 40 buah pada Tabel 10 diproses oleh algoritma Suffix Tree Clustering (STC) menghasilkan

4

klaster,

termasuk

klaster other topics. Hasil algoritma ini dapat dilihat pada Tabel 10,11, 12 dan Tabel 13

67


ISSN 1979-8911

Tabel 10 Daftar anggota Klaster

Dokumen

C1 ”Akas” No Kode Teks Dokumen Setelah Akas mendapatkan sarapan, 1 D19 diapergi ke sekolah Akas dan Ocha pergi 2 D20 ke Bandung Akas dan Dika 3 D22 bermain game Akas dilahirkan 4 D24 Bandung Akas dan Ocha berbicara Bahasa 5 D31 Sunda Akas pergi ke sekolah 6 D32 dengan mobil Akas ingin menjadi 7 D33 dokter Akas dan ibunya 8 D34 pergi ke Yogyakarta Akas memiliki 9 D35 saudara

Tabel 11 Daftar anggota Klaster C2 “Akun twitter” No Kode Teks Dokumen UGM memiliki akun 1 D6 twitter Jurusan Ilmu Komputer memiliki 2 D7 akun twitter juga Yoyok memiliki akun 3 D37 twitter

Tabel 12 Daftar anggota Klaster C3 “Yoyok” No Kode

1

D15

2

D16

3

D18

4

D36

5

D37

Yoyok berbicara Bahasa Ingris dengan lancar Yoyok bukan guru kursus Bahasa Inggris Yoyok berbicara Bahasa Inggris dan Sugeng berbicara Bahasa Jawa Yoyok dilahirkan di Yogyakarta Yoyok memiliki akun twitter

Tabel 13 Daftar anggota Klaster C4 “Other Topics” No Kode Teks Dokumen Sugeng menemui 1 D0 Rini juga UGM berlokasi di 2 D1 Yogyakarta UGM memiliki Jurusan Ilmu 3 D2 Komputer UGM singkatan dari Universitas Gadjah 4 D3 Mada Mahasiswa sering mendapatkan cemilan 5 D4 di kantin Mahasiswa sering menjelajah internet di 6 D5 perpustakaan Sugeng bertemu 7 D8 dengan Edwin Sugeng and Rini pergi ke kantor setiap 8 D9 hari Sugeng sedang duduk 9 D10 di atas kursi sekarang Yogyakarta berlokasi 10 D11 di pulau Jawa

Teks 68


ISSN 1979-8911

Tabel 13 Daftar anggota Klaster C4 “Other Topics” (lanjutan)

perbandingan

No Kode Teks Dokumen 11 D12 Muiz menyukai kopi Muiz memiliki mobil 12 D13 baru Muiz adalah seorang 13 D14 guru Kuncoro telah pergi 14 D17 belanja kemarin Cibaduyut berlokasi 15 D21 di Bandung Ada pohon jeruk di 16 D23 kebunnya Akas Ocha dilahirkan di 17 D25 Bandung Keukeu pernah ke 18 D26 Kota Pemalang Kota Pemalang berlokasi di Jawa 19 D27 Tengah Ocha memiliki 20 D28 kucing dan ikan Kucing memakan 21 D29 ikan 22 D30 Tikus memakan ikan Pemerintah Yogyakarta memiliki 23 D38 akun twitter dan facebook Rini menemui Edwin 24 D39 juga

b. Klaster

tujuan

klasifikasi

berserta anggota Kumpulan

dokumen

sebagai data training dalam proses

teks

anggota klaster yang ada, selain klaster other topics dapat dilihat pada Tabel 14. Data pada Tabel 14 akan digunakan

untuk

setiap

anggota

klaster other topics terhadap dokumen teks yang ada pada setiap kelas sebagai kelas tujuan dari proses perpindahan dokumen anggota other topics. Tabel 14 Daftar anggota klaster C1, C2 dan C3 hasil klasterisasi dengan STC No Kode Kode Teks Klaster Dokumen C1 Setelah Akas mempunyai sarapan, dia pergi ke 1 D19 sekolah C1 Akas dan Ocha pergi 2 D20 ke Bandung C1 Akas dan Dika bermain 3 D22 game C1 Akas dilahirkan 4 D24 di Bandung C1 Akas dan Ocha berbicara Bahasa 5 D31 Sunda C1 Akas pergi ke sekolah dengan 6 D32 mobil C1 Akas ingin menjadi 7 D33 dokter C1 Akas dan ibunya 8 D34 pergi ke 69


C1 9

D35 C2

10

D6 C2

11

D7 C2

12

D37 C3

13

D15 C3

14

D16 C3

15

D18 C3

16

D36 C3

17

D37

Yogyakarta Akas memiliki saudara UGM memiliki akun twitter Jurusan Ilmu Komputer memiliki akun twitter juga Yoyok memiliki akun twitter Yoyok berbicara Bahasa Inggris dengan lancar Yoyok bukan guru kursus Bahasa Inggris Yoyok berbicara Bahasa Inggris dan Sugeng berbicara Bahasa Jawa Yoyok dilahirkan di Yogyakarta Yoyok memiliki akun twitter

c. Proses klasifikasi dokumen teks anggota klaster other topics

ISSN 1979-8911

Seandainya proses pengklaster dokumen teks dengan menggunakan STC menghasilkan 4 klaster termasuk klaster other topics dengan kode C4 dan seandainya juga jumlah anggota setiap masing-masing

klaster

yaitu

C1

memiliki 4 anggota, C2 memiliki 3 anggota, klaster C3 memiliki 5, dan klaster C4 memiliki 24 anggota. Pada tahap klasifikasi akan dilakukan proses klasifikasi terhadap semua dokumen anggota klaster “other topics” yang berjumlah 24 untuk diklasifikasikan ke salah satu klaster C1, C2, C3 atau C4. Pada contoh kasus ini, akan melakukan percobaan

proses pengklasifikasian

terhadap salah satu dokumen anggota klaster other topics dengan kode D38 dan teks tersebut berisikan kalimat sebagai

berikut

“Pemerintah

Yogyakarta memiliki akun twitter dan facebook”. “Apakah

Pertanyaanya dokumen

D38

adalah ini

akan

diklasifikasikan ke klaster dengan label “Akas”, “Akun Twitter” atau “Yoyok”. 70


ISSN 1979-8911

Langkah awal yang dilakukan untuk menjawab

pertanyaan

ini,

adalah

dengan terlebih dahulu menggabungkan

C1

setelah Akas sarapan dia pergi 2 D19 sekolah Tabel 15 Hasil praproses (lanjutan)

dokumen teks D38 dengan anggota klaster C1, C2 dan C3 untuk diproses dalam perhitungan TF/IDF. Tabel 15 merupakan kumpulan data yang telah melalui proses preprocessing,

meliputi

stopword dan stoplist,

penghapusan dan proses

stemming dengan menggunakan Porter stemming for Bahasa Indonesia. Hasil praproses yang digunakan dalam proses klasifikasi

ini

sebelum

proses

pengklasteran STC telah disimpan. Pada proses klasifikasi data praproses yang telah

tersimpan

akan

dipergunkan

kembali untuk dihitung dengan fungsi TF/IDF. Data hasil praproses dapat dilihat pada Tabel 15 Tabel 15 Hasil praproses No Kode Kode Teks Klaster Dokumen Pemerintah Yogyakarta 1 C4 D38 miliki akun twitter facebook

No Kode Kode Teks Klaster Dokumen C1 Akas Ocha pergi 3 D20 Bandung C1 Akas Dika bermain 4 D22 game C1 Akas lahir 5 D24 Bandung C1 Akas Ocha bicara 6 D31 Sunda C1 Akas pergi sekolah 7 D32 mobil C1 Akas ingin 8 D33 dokter C1 Akas ibu pergi 9 D34 Yogyakarta C1 Akas milik 10 D35 saudara C2 UGM milik 11 D6 akun twitter C2 Jurusan Ilmu Komputer milik akun 12 D7 twitter C2 Yoyok milik 13 D37 akun twitter C3 Yoyok bicara Inggris 14 D15 lancar C3 Yoyok bukan guru kursus Bahasa 15 D16 Inggris 16 C3 D18 Yoyok 71


C3 17

D36 C3

18 D37 d. Menghitung TF/IDF

ISSN 1979-8911

bicara Inggris Sugeng bicara Jawa Yoyok lahir Yogyakarta Yoyok miliki akun twitter

Langkah menentukan

berikutnya,

bobot,

dengan

adalah istilah

weight documentterm (wdt). Nilai bobot berasal dari nilai idf untuk setiap term yang ada, kemudian dikalikan dengan nilai tf untuk setiap term di semua

Semua dokumen teks yang ada

dokumen

yang ada.

Hasil operasi

pada Tabel 15 dipisahkan (tokenizing)

perkalian nilai idf dan nilai tf dari term-

kata demi kata. Kata-kata yang ada

term yang ada dapat dilihat sebagai nilai

diinventarisir agar tidak dicatat berulang

bobot untuk semua term di setiap

kali, kemudian disebut dengan term

dokumen yang digunakan termasuk satu

tunggal. Term-term tunggal yang ada

dokumen anggota teks berita klaster

kemudian

other

dihitung

frekuensi

topics

sebagai

query

atau

kemunculan term pada setiap dokumen.

dokumen teks yang akan dibandingkan

Frekuensi

kemunculan

dengan dokumen teks yang ada pada

term-term tunggal pada setiap dokumen,

klaster-klaster yang ada lainnya. Proses

dikenal term frequency (tf) dan nilai

yang dilakukan setelah ditemukan nilai

frekuensi dokumen terhadap tf, yang

idf adalah penentuan nilai bobot dengan

dikenal dengan document frequency (df).

rumus

Sehingga nilai invers dari frekuensi

d adalah document dan t adalah term.

kemunculan

setiap dokumen, yang dikenal dengan invers

document

frequency

, W adalah weight,

Nilai bobot dokumen pada salah

dapat

satu anggota klaster other topics, dalam

dihitung dengan rumus log(n/df) dengan

hal ini adalah D38 yang ada kemudian

n adalah jumlah dokumen. Nilai-nilai tf,

akan dikalikan dengan nilai bobot term-

df, dan idf .

term untuk setiap dokumen yang ada 72


ISSN 1979-8911

pada klaster lainnya. Perkalian nilai

dengan mengkuadratkan nilai bobot

bobot term-term dokumen D38 dengan

yang ada pada setiap term dan dokumen

term-term angota klaster yang ada

yang ada. Proses perhitungan untuk

lainnya dapat ditentukan. Nilai bobot

mendapatkan nilai vektor dokumen D38

setiap term untuk setiap dokumen

sebagai anggota other topics terhadap

berdasarkan nilai tf dan idf, nilai bobot

dokumen anggota klaster yang ada,

ini kemudian akan dihitung pada proses

dengan

berikutnya untuk mendapatkan panjang

yang ada pada setiap term dan dokumen

vektornya.

yang ada.

e. Proses

Perhitungan

mengkuadratkan

nili

bobot

Tabel 16 merupakan nilai akar

Panjang

rekap total nilai untuk setiap dokumen

Vektor Hasil

perhitungan

panjang

yang ada. Panjang vektor Dj didapat

vektor didapat dari hasil kuadrat bobot

dengan

yang

panjang vektor untuk term-term yang

ada

termasuk

pada dokumen

setiap

dokumen,

anggota

klaster

ada

melakukan

disetiap

penjumlahan

dokumen

dengan

other topics. Pada proses pembobotan

menggunakan fungsi SUM dan mencai

ini dilakukan dengan proses perkalian

nilai akar dari fungsi SUM untuk setiap

antara nilia tf dengan nilai idf untuk

dokumennya

masing-masing term-term yang ada pada setiap dokumen yang dilibatkan pada proses penentuan nilai tf/idf. Hasil pembobotan

terhadap

term.

Proses

perhitungan selanjutnya berfungsi untuk mendapatkan

nilai

vektor

semua

dengan

rumus

, d adalah dokumen, t adalah term yang ada, i adalah indeks term dan j sebagai dokumen, sedangkan w adalah nilai bobot (weight). Panjang

vektor

q

dilakukan

dengan menjumlahkan untuk term-term

dokumen anggota pada klaster yang ada, 73


ISSN 1979-8911

yang ada dengan menggunakan fungsi

17 18

1.3203 1.1282

D36 D37

SUM dan mencai nilai akar dari fungsi SUM untuk setiap dokumennya dengan rumus

,

d

adalah

f. Menghitung Kemiripan Dokumen Teks Nilai-nilai yang ada digunakan

dokumen, t adalah term yang ada, i adalah indeks term dan q sebagai dokumen anggota klaster other topics, sedangkan w adalah nilai bobot (weight). Tabel

16

pada

Kolom

1

(satu)

menunjukan nilai vektor untuk setiap nilai term-term dokumen D38 sebagai query atau dokumen anggota other

Tabel 16 Nilai Akar dari Summary Panjang Vektor

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

dokumen D38 salah satu anggota klaster other

topics

terhadap

dokumen-

dokumen anggota klaster yang ada, dengan menggunakan rumus cosine similary. Persamaan (6) merupakan rumus

yang

digunakan

dalam

perhitungan nilai kemiripan. Data nilai

topics.

No

untuk menghitung nilai kemiripan antar

Kode Dokumen D38 D19 D20 D22 D24 D31 D32 D33 D34 D35 D6 D7 D37 D15 D16 D18

Nilai Similarity 3.0745 2.1811 1.5864 2.1947 1.3825 2.0376 1.7837 1.8004 1.6961 1.4055 1.6189 2.3119 1.1282 1.8217 2.3578 2.7615

kemiripan dokumen-dokumen anggota klaster yang ada terhadap dokumen D38 anggota klaster other topics. Nilai kemiripan

ini

didapat

berdasarkan

rumus similarity Persamaan (6). Maka, diperoleh data sebagai berikut :

74


ISSN 1979-8911

Tabel 17 merupakan daftar nilai cosine

similarity

dokumen

yang

dari

ada

dokumen-

ada,

terhadap

dokumen D38 dan memiliki nilai lebih dari 0. Tabel 17 Nilai Cosine Similarity dokumen lebih besar dari 0 C1 C2 C2 C2 C3 C3 D35 D6 D7 D37 D36 D37 0.161 0.4450.196 0.6380.24 0.638 g. Proses

Klasifikasi

dengan

K-

Nearest Neighbor Tabel 17 merupakan daftar nilai cosine similarity sebanyak 7 dokumen (k=7) berdasarkan Tabel 18 dan telah diurutkan dari nilai terbesar sampai dengan nilai terkecil. Tabel 18 Nilai Cosine Similarity secara terurut Hasil kemiripan

perhitungan dokumen

D38

nilai sebagai

C2 C3 C2 C3 C2 C1 C1 D37 D37 D6 D36 D7 D34 D35 0.6380.638 0.4450.24 0.196 0.1870.161 Tabel 19 merupakan rekap dari

dokumen query yang berada di klster hasil other

topics

dibandingkan

perhitungan

dari

banyaknya

dengan jumlah dokumen anggota klaster C1, C2

dokumen yang ada pada klaster-klaster dan C3yang memiliki nilai kemiripan yang ada, dapat dilihat pada Tabel 17. terhadap dokumen D38 salah satu

75


ISSN 1979-8911

anggota klaster other topics. Pada

agar berpindah dari klaster other topics

klaster C1 ada 2 (dua) dokumen yang

ke klaster dengan label “Akun Twitter”.

memiliki kemiripan dengan dokumen

Dengan demikian dokumen teks other

D38, klaster C2 terdapat 3 dokumen

topics dengan kode D38 yang berisi

yang mirip dan klaster C3 hanya ada 1

kalimat

dokumen

memiliki akun

yang

anggota

klasternya

“Pemerintah

Yogyakarta

twitter dan facebook”

memiliki kemiripan dengan dokumen

menjadi anggota klaster dengan kode

D38. Dengan demikian klaster C2

C2 yang bernama “Akun Twitter”.

adalah klaster yang memiliki jumlah Berdsarkan

hasil

proses

terbanyak dokumen anggotanya yang klasifikasi anggota klaster other topics memiliki kemiripan dengan dokumen yang dapat diklasifikasikan ke klaster D38 dan kalster C2 ditetapkan sebagai lainnya yang ada, secara teoritis dapat klaster tujuan klasifikasi dari dokumen dibuktikan. Dengan dengan demikain D38. proses klasifikasi dengan menggunakan algoritma

Nearest

Neighbor

diimplementasikan

akan untuk

Tabel 18 Hasil Akhir mengklasifikasi semua dokumen teks No Kode Klaster 1 C1 2 C2 3 C3

Hasil

Jumlah Dokumen 2 3 1

akhir

dari

klaster other topics hasil dari proses klasterisasi

kode

klaster

menggunakan

algoritma suffix tree clustering. proses

pengklasifikasian ini adalah klaster C2 merupakan

dengan

yang

direkomendasikan untuk dokumen D38

Secara umum proses klasifikasi anggota klaster other topics dapat dilihat pada

Gambar

pengklasifikasian

8. teks

Proses dokumen 76


ISSN 1979-8911

anggota klaster other topics berdasarkan

cara menghitung dengan fungsi log dari

Gambar 8, dapat diketahui bahwa

jumlah dokumen keseluruhan dibagi

inputan berupa dokumen teks dari

dengan nilai idf untuk setiap term-term

klaster-klaster yang ada dan dokumen

yang ada.

teks klaster other topics yang disebut

Nilai-nilai idf yang dimiliki oleh

dengan query dengan simbol q. Semua

term-term yang ada kemudian dikalikan

dokumen teks yang ada harus dipenggal

dengan nilai tf, hasil dari perkalian ini

kata perkata agar dapat dikumpulkan

disebut dengan bobot yang disimbolkan

semua kata-kata yang ada dan dicatat

dengan W. Nilai bobot yang ada setiap

tanpa ada pengulangan yang kemudian

term dan dokumen yang ada, dapat

disebut dengan term. Dokumen teks

dicari nilai skalar dan panjang vektor

berasal dari hasil proses klasterisasi

dari dokumen klaster yang ada yang

menggunakan

disimbolkan dengan dj dan dokumen

clustering

algoritma

dan

telah

suffix

tree

mengalami

praproses dokumen teks yang disimpan pada database.

anggota

klaster

other

topics

yang

disimbolkan dengan q. Setelah didapat nilai skalar dan

Term-term yang ada kemudian

panjang vektor dokumen dj dan q, maka

dihitung kemunculannya pada setiap

nilai-nilai

ini

dokumen yang ada. Jumlah kemunculan

menghitung

kemiripan

ini, disebut dengan term frequency (tf).

dengan dokumen q. Sehingga didapat

Sedangkan

yang

nilai similarity antara dokumen dj dan q

mengandung term-term tertentu disebut

dengan menggunakan Persamaan (6).

dengan

Proses perbandingan untuk mengukur

Sehingga

jumlah

document nilai

dokumen

frequency invers

(df).

dokument

frequency (idf) dapat ditentukan dengan

kemiripan

ini,

digunakan

untuk

dokumen

dilakukan

dj

secara

berulang untuk semua dokumen klaster 77


ISSN 1979-8911

other topics yang ada terhadap dokumen semua teks dokumen dj yang tersebar di

similarity

yang

ada,

Klaster “Other Topics ”

Klast er “Y”

d

d

klster-klaster yang ada. Nilai

Klast er “X”

q

Tokenizing Dokumen Teks

diurutkan dari besar ke kecil, kemudian

td,

dihitung jumlah dokumen dj pada setiap

Menghitung TF, DF, IDF

klaster.

Klaster

dengan

TFd, TFq, IDF , IDF

jumlah

banyaknya dokumen yang memiliki kemiripan sebagai

ini,

kemudian

dijadikan

klaster

tujuan

klasifikasi

sehingga kode klaster dokumen other topic saat itu, yaitu q diubah kode klasternya

ke

ditetapkan

sebagai

perpindahan

klaster

dokumen

yang

klaster q.

Menentukan Bobot (Weight) TF*IDF

Wij Mengitun g panjang vektor dj dan q

telah

Menentuk an skalar dj dan q

Menghitung Similarity q terhadap dj

tujuan Hal

C

ini

Sim(d ,q) Menentukan klaster

dilakukan untuk semua anggota klaster

dengan jumlah anggota terbanyak yang memiliki kemiripan dengan dokumen q

other topics. Sehingga klaster other topics tidak memiliki anggota.

Gambar 8 Diagram Proses klasifikasi dokumen klster other topics

Kesimpulan Proses

pengklasteran

teks

berita

dengan menggunakan Algoritma Suffix

78


Tree

Clustering

(STC)

ISSN 1979-8911

mampu

mengkelompokkan berita secara tematik, tetapi masih banyak

menghasilkan

dokumen yang tak terkelompokkan. Sehingga

dokumen

Berita dengan Menggunakan Algoritma

Suffix

Tree

Clustering,

Seminar

Sistem

Informasi

Indonesia,

Surabaya.

tersebut, [2] Budhi,

dikelompokkan klasifikasi

ulang

dengan

pada

proses

menggunakan

Algoritma K-Nearest Neighbor (K-NN) dan

akhirnya

ITS,

K-NN

mampu

mengkelompokkan dokumen tersebut

G.

S., Gunawan I.,

Yuwono F., 2006, Algoritma Porter Stemmer for Bahasa Indonesia

untuk

processing

Text

Mining

Metode

Market

Berbasis

Pre-

Basket Analysis.

ke dalam kelompok yang ada. [3] Cao G., Song D., Bruza P., 2003, Suffix Tree Clustering on Post-

Ucapan terima kasih

retrieval Penulis mengucapkan terima kasih kepada

Bapak

Edi

Winarko

atas

Document,

Distributed

System

Technology

Center,

The

University of Queensland kesediaanya

dalam

mensukseskan

penelitian ini. Kemudian, dukungan yang telah penulis terima dari pihak

[4] Esko,

U.,

1995,

On-Line

Construction of Suffix Trees. In: Algorithmica, Vol. 14, No.

Laboratorium Komputer JIKE FMIPA

3., pp. 249-260.

UGM. [5] Farach. M., 1997, Optimal Suffix Referensi

Tree Construction with Large Proc.

38th

Symposium

on

Alphabets, [1] Arifin, A. Z., Darwanto, R., Navastara,

D.

A.,

Annual

In

Foundations

Ciptaningtyas, H. T., 2008,

Science

Klasifikasi Online Dokumen

IEEE

,

of

Computer

pages

137–143.

79


ISSN 1979-8911

events/sec02/full_papers/liao/l [6] Frakes, W.B., and Baeza R., 1992, Information Retrieval, Data

Structures

iao_html/node4.htm,

diakses

21 Agustus 2013

and

Algorithms.Prentice Hall.

[12] Nagwani N. K. dan Verma S., 2011,

Software

Bug

[7] Gusfield D., 1997, Linear-Time

Classification using Suffix Tree

Construction of Suffix Tree,

Clustering (STC) Algorithm,

University

IJCST vol. 2, Department of

of

California,

Cambridge University Press

CS&E, National Institute of Technology Raipur

[8] Kusrini dan Luthfi, E.T, 2009, Algoritma Data Mining, Andi Offset, Yogyakarta

[13] Salton, G., 1983, Introduction to

Modern

Retrieval, [9] Kwok, J. T.-Y., 1998, Automatic Text

Categorization

Support

Vector

Information McGraw-Hill

BookCompany, New York.

Using

Machine,

[14] Sandi, F. R., 2012, Klasifikasi

Proceedings of International

Posting

Conference

Neural

Lalu Lintas Kota Bandung

Information Processing, 347-

Menggunakan Naïve Bayesian

351.

Classification, Tesis, Program

on

Studi [10] Kwon O., Lee J., 2003, Text

Twitter

S2

Kemacetan

Ilmu

Komputer,

FMIPA, UGM.

Categorization Based on kNearest Neighbor Approach

[15] Santosa B., 2007, Data Mining

for Web Site Classification,

Teknik

Pemanfaatan

data

Elsevier Science Ltd.

untuk Keperluan Bisnis, Graha Ilmu.

[11] Liao Y., 2002, Review of KNearest

Neighbor

Categorization

Text

[16] Snowsill

T.,

2012,

Data

Method,

Mining in Text Stream using

https://www.usenix.org/legacy/

Suffix Tree, Disertasi, Jurusan 80


ISSN 1979-8911

Matematika Teknik, Fakultas

Clustering,

Jurusan

Teknik, Universitas Bristol,

Informatika, ITS

Teknik

United Kingdom. [22] Yang R., Xie H., dan Zhu Q., [17] Pribadi A.A., Martiana E.,

2011, Sentence-based Suffix

2012, Pencarian Judul TA

Tree

menggunakan Text Mining dan

Documents,

Metode Suffix Tree, Jurusan

Computer Science, Chongqing

Tekknik Informatika, ITS

University, Hongtao

[18] Tala, F. Z., 2003, A Study of

Clustering

for

Web

College

of

[23] Zamir, O., Etzioni, O., 1998,

Stemming

Effects

on

Web document clustering: a

Information

Retrieval

in

feasibility demonstration. In:

Bahasa Indonesia, Universiteit van Amsterdam, Netherland

SIGIR 1998, pp. 46-54 Jumadi* Informatics Department, Faculty of

[19] Weiss D., Osinki S., 2004, 2

Carrot

Clustering

Framework, University

Poznan of

Science and Technology UIN Sunan Gunung Djati Bandung [email protected]

Technology, Edi Winarko

Poznan Poland

Computer [20] Weiner,

P.,

1973,

Linear

pattern matching algorithms, in Proceedings of the 14th Annual IEEE Symposium on Switching

and

Automata

Science

and

Electronics

Department, Faculty of Mathematics and Natural Sciences Universitas Gadjah Mada, Yogyakarta [email protected] *Corresponding author

Theory, pp. 1–11,

[21] Wicaksono Mining Dokumen

T.,

2012,

untuk

Pencarian

Bahasa

menggunakan

Text

Suffix

Inggris Tree 81

PENGGUNAAN KNN (K-NEARST NEIGHBOR) UNTUK KLASIFIKASI TEKS BERITA YANG TAK-TERKELOMPOKKAN PADA SAAT PENGKLASTERAN OLEH STC (SUFFIX TREE CLUSTERING)

Recommend Documents