Modul Data Warehouse dan Data Mining
Download Modul Data Warehouse dan Data Mining Bab 11 - Data Mining
Bab 11 - Data Mining
Abstract
Menjelaskan tentang pengertian data mining
Kompetensi
Mahasiswa mampu memahami konsep data mining
Pendahuluan
Perkembanganteknologidewasainikhususnya internet berkembangsangatpesat. Hal ini diiringi juga dengan
semakin berkembangnya teknologi informasi yang dibutuhkan oleh pengguna sehingga mengakibatkan
munculnya suatu cabang ilmu baru dalam teknologi informasi, yaitupencarian informasi (information
retrieval). Information Retrieval adalah “studi tentang sistem pengindeksan, pencarian, dan mengingat data,
khususnya teks atau bentuk tidak terstruktur lainnya” [virtechseo.com] sedangkan arti menurut Wikipedia,
“Information Retrieval adalah seni dan ilmumencari informasi dalam dokumen, mencari dokumen itu sendiri,
mencari metadata yang menjelaskan dokumen, atau mencari dalam database, apakah relasional database
itu berdiri sendiri atau database hypertext jaringan seperti Internet atau intranet, untuk teks, suara, gambar,
atau data”.
Penggalian Data (Data Mining)
Penggalian data (bahasa Inggris: data mining) adalah ekstraksi pola yang menarik dari data dalam jumlah
besar. Suatu pola dikatakan menarik apabila pola tersebut tidak sepele, implisit, tidak diketahui sebelumnya,
dan berguna. Pola yang disajikan haruslah mudah dipahami, berlaku untuk data yang akan diprediksi dengan
derajat kepastian tertentu, berguna, dan baru. Penggalian data memiliki beberapa nama alternatif, meskipun
definisi eksaknya berbeda, seperti KDD (knowledge discovery in database), analisis pola, arkeologi data,
pemanenan informasi, dan intelegensia bisnis. Penggalian data diperlukan saat data yang tersedia terlalu
banyak (misalnya data yang diperoleh dari sistem basis data perusahaan, e-commerce, data saham, dan data
bioinformatika), tapi tidak tahu pola apa yang bisa didapatkan.
Proses PencarianPola
Penggalian data adalahsalahsatubagiandari proses pencarianpola. Berikutiniurutan proses pencarianpola:
1. Pembersihan Data: yaitu menghapus data pengganggu (noise) dan mengisi data yang hilang.
2. Integrasi Data: yaitu menggabungkan berbagai sumber data.
3. Pemilihan Data: yaitu memilih data yang relevan.
4. Transformasi Data: yaitu mentransformasi data ke dalam format untuk diproses dalam penggalian
data.
5. Penggalian Data: yaitu menerapkan metode cerdas untuk ekstraksi pola.
6. Evaluasi pola: yaitu mengenali pola-pola yang menarik saja.
7. Penyajian pola: yaitu memvisualisasi pola ke pengguna.
Definisi Text Mining
Text mining memilikidefinisimenambang data yang berupateksdimanasumber data
biasanyadidapatkandaridokumen, dantujuannyaadalahmencari kata-kata yang
dapatmewakiliisidaridokumensehinggadapatdilakukananalisaketerhubunganantardokumen.Sedangkanmenu
rutsituswikipedia,Penambanganteks (bahasaInggris: text mining) adalah proses
ekstraksipolaberupainformasidanpengetahuan yang bergunadarisejumlahbesarsumberdatateks,
sepertidokumenWord, PDF, kutipanteks, dll. Jenismasukanuntukpenambanganteksinidisebut data
takterstrukturdanmerupakanpembedautamadenganpenambangan data yang menggunakan data
terstrukturataubasis datasebagaimasukan.Penambanganteksdapatdianggapsebagai proses duatahap yang
diawalidenganpenerapanstrukturterhadapsumber data
teksdandilanjutkandenganekstraksiinformasidanpengetahuan yang relevandari data
teksterstrukturinidenganmenggunakanteknikdanalat yang samadenganpenambangan data. Proses yang
umumdilakukanolehpenambanganteks di antaranyaadalahperangkumanotomatis, kategorisasidokumen,
penggugusanteks, dll.
Tujuan dari text mining adalah untuk mendapatkan informasi yang berguna dari sekumpulan dokumen. Jadi,
sumber data yang digunakan pada text mining adalah kumpulan teks yang memiliki format yang tidak
terstruktur atau minimal semi terstruktur. Adapun tugas khusus dari text mining antara lain yaitu
pengkategorisasian teks (text categorization) dan pengelompokan teks text clustering).
Text Mining
Text mining merupakan penerapan konsep dan teknik data mining untuk mencari pola dalam teks,
yaitu proses penganalisisan teks guna menyarikan informasi yang bermanfaat untuk tujuan tertentu.
Berdasarkan ketidakteraturan struktur data teks, maka proses text mining memerlukan beberapa
tahap awal yang pada intinya adalah mempersiapkan agar teks dapat diubah menjadi lebih terstruktur.
Tahapan Text Mining
Masalah Umum yang ditangani
Klasifikasi Dokumen
Information Retrieval
Pengorganisasian dan Clustering Dokumen
Information Extraction
Clustering Dokumen
Analisis Cluster
Analisis cluster adalah pengorganisasian kumpulan pola ke dalam cluster (kelompok-kelompok)
berdasar atas kesamaannya.
Pola-pola dalam suatu cluster akan memiliki kesamaan ciri/sifat daripada pola-pola dalam cluster yang
lainnya.
Clustering bermanfaat untuk melakukan analisis pola-pola yang ada, mengelompokkan, membuat
keputusan dan machine learning, termasuk data mining, document retrieval, segmentasi citra, dan
klasifikasi pola.
Metodologi clustering lebih cocok digunakan untuk eksplorasi hubungan antar data untuk membuat
suatu penilaian terhadap strukturnya.
Information Retrieval
Konsep dasar dari IR adalah pengukuran kesamaan
sebuah perbandingan antara dua dokumen, mengukur sebearapa mirip keduanya.
Setiap input query yang diberikan, dapat dianggap sebagai sebuah dokumen yang akan dicocokan dengan
dokumen-dokumen lain.
Pengukuran kemiripan serupa dengan metode klasifikasi yang disebut metode nearest-neighbour.
Information Extraction
Information Extraction bermanfaat untuk menggali struktur informasi dari sekumpulan dokumen.
Dalam menerapkan IE, perlu sekali dilakukan pembatasan domain problem.
IE sangat memerlukan NLP untuk mengetahui gramatikal dari setiap kalimat yang ada.
Sebagai contoh:
o “Indonesia dan Singapore menandatangani MoU kerjasama dalam bidang informasi dan
komunikasi.”
o KerjaSama(Indonesia, Singapore, TIK)
Dengan IE, kita dapat menemukan:
o concepts (CLASS)
o concept inheritance (SUBCLASS-OF)
o concept instantiation (INSTANCE-OF)
o properties/relations (RELATION)
o domain and range restrictions (DOMAIN/RANGE)
o equivalence
Algoritma yang digunakan pada text mining, biasanya tidak hanya melakukan perhitungan hanya pada
dokumen, tetapi pada juga feature. Empat macam feature yang sering digunakan:
Character, merupakan komponan individual, bisa huruf, angka, karakter spesial dan spasi, merupakan
block pembangun pada level paling tinggi pembentuk semantik feature, seperti kata, term dan concept.
Pada umumnya, representasi character-based ini jarang digunakan pada beberapa teknik pemrosesan
teks.
Words.
Terms, merupakan single word dan frasa multiword yang terpilih secara langsung dari corpus.
Representasi term-based dari dokumen tersusun dari subset term dalam dokumen.
Concept, merupakan feature yang di-generate dari sebuah dokumen secara manual, rule-based, atau
metodologi lain. Pada tugas akhir ini, konsep di-generate dari argument atau verb yang sudah diberi
label pada suatu dokumen.
Proses text mining meliputi proses tokenizing, filtering, stemming, dan tagging.
Tokenizing
Tokenizing adalah proses penghilangan tanda baca pada kalimat yang ada dalam dokumen sehingga
menghasilkan kata-kata yang berdiri sendiri-sendiri.
Filtering
Tahap filtering adalah tahap pengambilan kata-kata yang penting dari hasil tokenizing. Tahap filtering ini
dapat menggunakan algoritma stoplist atau wordlist. Stoplist yaitu penyaringan (filtering) terhadap kata-kata
yang tidak layak untuk dijadikan sebagai pembeda atau sebagai kata kunci dalam pencarian dokumen
sehingga kata-kata tersebut dapat dihilangkan dari dokumen. Sedangkan wordlist adalah daftar kata-kata
yang mungkin digunakan sebagai kata kunci dalam pencarian dokumen.
Stemming
Stemming adalah proses mengubah kata menjadi kata dasarnya dengan menghilangkan imbuhan-imbuhan
pada kata dalam dokumen atau mengubah kata kerja menjadi kata benda. Stem (akar kata) adalah bagian dari
kata yang tersisa setelah dihilangkan imbuhannya (awalan dan akhiran).
Contoh: connect adalah stem dari connected, connecting, connection, dan connections.
Gambar. Bagan metode stemming
Porter stemmermerupakan algoritma penghilangan akhiran morphological dan infleksional yang umum dari
bahasa Inggris. Step-step algoritma Porter
Stemmer:
1. Step 1a : remove plural suffixation
2. Step 1b : remove verbal inflection
3. Step 1b1 : continued for -ed and -ing rules
4. Step 1c : y and i
5. Step 3
6. Step 4 : delete last suffix 4
7. Step 5a : remove e
8. Step 5b : reduction
Tagging
Tahap tagging adalah tahap mencari bentuk awal / root dari tiap kata lampau atau kata hasil stemming.
Analyzing
Tahap analyzing merupakan tahap penentuan seberapa jauh keterhubungan antar kata-kata dengan
dokumen yang ada.
Automatic Clustering
Clustering adalah proses membuat pengelompokan sehingga semua anggota dari setiap partisi mempunyai
persamaan berdasarkan matrik tertentu. Sebuah cluster adalah sekumpulan objek yang digabung bersama
karena persamaan atau kedekatannya. Clustering atau klasterisasi merupakan sebuah teknik yang sangat
berguna karena akan mentranslasi ukuran persamaan yang intuitif menjadi ukuran yang kuantitatif.
CLHM (Centroid Linkage Hierarchical Method)
Centroid Linkage adalah proses pengklasteran yang didasarkan pada jarak antar centroidnya [6]. Metode ini
baik untuk kasus clustering dengan normal data set distribution. Akan tetapi metode ini tidak cocok untuk
data yang mengandung outlier. Algoritma Centroid Linkage Hierarchical Method adalah sebagai berikut:
1. Diasumsikan setiap data dianggap sebagai cluster. Kalau n=jumlah data dan c=jumlah cluster, berarti ada
c=n.
2. Menghitung jarak antar cluster dengan Euclidian distance.
3. Mencari 2 cluster yang mempunyai jarak centroid antar cluster yang paling minimal dan digabungkan
(merge) kedalam cluster baru (sehingga c=c-1).
4. Kembali ke langkah 3, dan diulangi sampai dicapai cluster yang diinginkan.
Analisa Cluster
Analisa cluster adalah suatu teknik analisa multivariate (banyak variabel) untuk mencari dan mengorganisir
informasi tentang variabel tersebut sehingga secara relatif dapat dikelompokkan dalam bentuk yang
homogen dalam sebuah cluster. Secara umum, bisa dikatakan sebagai proses menganalisa baik tidaknya suatu
proses pembentukan cluster. Analisa cluster bisa diperoleh dari kepadatan cluster yang dibentuk (cluster
density). Kepadatan suatu cluster bisa ditentukan dengan variance within cluster (Vw) dan variance between
cluster (Vb). Varian tiap tahap pembentukan
cluster bisa dihitung dengan rumus:
...(1)
Dimana:
Vc2 = varian pada cluster c
c = 1..k, dimana k = jumlah cluster
nc = jumlah data pada cluster c
yi = data ke-i pada suatu cluster
yi = rata-rata dari data pada suatu cluster
Selanjutnya dari nilai varian diatas, kita bisa menghitung nilai variance within cluster (Vw) dengan rumus:
...(2)
Dimana, N = Jumlah semua data
ni = Jumlah data cluster i
Vi = Varian pada cluster i
Dan nilai variance between cluster (Vb) dengan rumus:
...(3)
Dimana, y = rata-rata dari yi
Salah satu metode yang digunakan untuk menentukan cluster yang ideal adalah batasan variance, yaitu
dengan menghitung kepadatan cluster berupa variance within cluster (Vw) dan variance between cluster (Vb).
Cluster yang ideal mempunyai Vw minimum yang merepresentasikan internal homogenity dan maksimum Vb
yang menyatakan external homogenity.
...(4)
Hill Climbing
Pada Hill-climbing didefinisikan bahwa kemungkinan mencapai global optimum terletak pada tahap ke-i, jika
memenuhi persamaan berikut:
Vi+1 >α. Vi ........... (5)
Dimana, α adalah nilai tinggi.
Nilai tinggi digunakan untuk menentukan seberapa mungkin metode ini mencapai global optimum. Nilai α
yang biasa digunakan adalah 2,3, dan 4. Persamaan diatas, diperoleh berdasar analisa pergerakan varian pola
Hill climbing yang ditunjukkan pada gambar berikut:
Gambar. Pola nilai beda Hill-climbing
Berikut tabel 1 yang menunjukkan polapolavalley tracing dan hill climbingyang mungkinmencapai global
optimum. Pola yang mungkin ditandai dengansimbol √.
Tabel. Tabel kemungkinan pola hill climbing mencapai global optimum
Selanjutnya, dengan pendekatan metode hill climbing dilakukan identifikasi perbedaan nilai tinggi (∂) pada
tiap tahap, yang didefinisikan dengan:
∂ = Vi+1 . (Vi * α) ...(6)
Nilai ∂ digunakan untuk menghindari local optima, dimana persamaan ini diperoleh dari maksimum ∂ yang
dipenuhi pada persamaan 6. Untuk membentuk cluster secara otomatis, yaitu cluster yang mencapai global
optima, digunakan nilai ë sebagai threshold, sehingga cluster secara
otomatis terbentuk ketika memenuhi:
max(∂) ≥ .....(7)
Untuk mengetahui keakuratan dari suatu metode pembentukan cluster pada hierarchical method, dengan
menggunakan hill climbing digunakan persamaan sebagai berikut:
...(8)
Dimana nilai terdekat ke max (∂) adalah nilai kandidat max(∂) sebelumnya. Nilai ö yang lebih besar atau sama
dengan 2 (ö≥2), menunjukkan cluster yang terbentuk merupakan cluster yang wellseparated (terpisah dengan
baik).
Implementasi
Gambar. Use case utama (Architecturally Significant)
Gambar diatas adalah gambaran sistem secara garis besar yang dibedakan menjadi lima proses utama, yaitu
proses searching dan simpan dokumen online, proses text mining, proses pengklasteran dengan algoritma
Centroid Linkage Hierarchical Method, proses pembentukan jumlah cluster secara otomatis (automatic
clustering) dan bagaimana menampilkan hasil pencarian dokumen.
Gambar. Use case diagram proses pencarian dan penyimpanan dokumen dari internet
Gambar ini adalah merupakan use-case diagram untuk proses pencarian dan penyimpanan dokumen yang
diambil dari internet.
Gambar. Use case diagram proses text mining
Gambar di atas adalah use-case diagram untuk proses text mining dimana user yang akanmelakukan
pencarian dokumen harus memasukkan keywords (kata kunci) terlebih dahulu kemudian sistem akan
melakukan proses dari text mining.
Gambar. Use case diagram proses clustering dengan CLHM
Gambar ini menunjukkan proses clustering dengan menggunakan metode CLHM (CentroidLinkage
Hierarchical Method). Kata kunci yang dimasukkan oleh user akan dicari jumlahnyaoleh sistem pada
dokumen kemudian jumlah ini yang akan menentukan proses clustering berikut.
Gambar. Use case diagram proses automatic clustering dengan hill climbing
Gambar tersebut menunjukkan proses dari pembentukan automatic clustering denganmelihat pola
pergerakan varian yang ada. Dengan menggunakan metode hill climbingmaka dianalisa posisi global optimum
yang mungkin sehingga bisa dibentuk jumlah clusteryang tepat.
Gambar. Use case diagram proses hasil pencarian dokumen sesuai kata kunci
Gambar terakhir menunjukkan hasil akhir dari proses clustering engine ini. Yaitu menampilkan hasil
dokumen yang tepat sesuai dengan kata kunci yang diinputkan oleh user.
Kesimpulan
Dari hasil uji coba dan analisa yang telah dilakukan, maka dapat diambil kesimpulan:
1. Penggunaan text mining untuk pengkategorisasian teks dokumen bahasa Inggris memudahkan dalam
pencarian dokumen yang sesuai dengan keinginan dari pengguna.
2. Pencarian dokumen dengan menggunakan algoritma Centroid Linkage Hierarchical Method dengan
pola analisa varian Hill Climbing dapat digunakan untuk mengelompokkan dokumen secara otomatis
dengan jumlah cluster yang tepat.
3. Pola analisa varian dengan menggunakan metode Hill Climbing memerlukan waktu yang lebih cepat
dalam melakukan analisa jumlah cluster jika dibandingkan dengan metode valley tracing. Hal ini
disebabkan karena pengclusteran hasil dari Hill Climbing mendukung akses kecepatan penghitungan
dokumen pada tiap clusternya.
4. Pola analisa varian dengan menggunakan metode Hill Climbing sangat sesuai untuk pencarian
dokumen dengan jumlah yang sangat besar dan kata kunci yang panjang. Hal ini berpotensi
untukimplementasi program dalam skala yang lebih luas.
Sumber :
Modul Perkuliahan - Data Warehouse dan Data Mining - Program Studi Sistem Informasi - Fakultas Ilmu Komputer - Universitas Mercu Buana
