BAB II KAJIAN PUSTAKA
Dengan meningkatnya minat terhadap penelitian yang berkaitan dengan mengidentifikasi dan menggali informasi yang berharga dalam sebuah file musik dengan akurasi yang baik, maka telah banyak dihasilkan penelitian yang berkaitan dengan Music Information Retrieval (MIR) dan Music Emotion Recognition (MER). Berikut ini akan dilakukan analisa terhadap beberapa publikasi penelitian yang relevan dengan usulan penelitian ini.
2.1 State of The Art Review Pada tahun 2010 Xiao Hu dalam penelitiannya Music and Mood : Where Theory and Reality Meet melakukan penelitian yang mengangkat aspek afektif (berkaitan dengan perasaan dan emosi) yang kemudian disebut mood atau suasana hati dalam musik, dan hal ini menjadi faktor penting dalam mengorganisir dan mengakses informasi pada musik. Penelitian ini mengulas teori mengenai psikologi musik dan merangkum wawasan yang mendasar yang dapat membantu para peneliti bidang Music Information Retrieval (MIR) dalam memperkirakan suasana hati dalam musik. Penelitian ini juga berasal dari seperangkat kategori suasana hati dalam musik yang diberi tag/label oleh pendengar musik, yang menggunakan kombinasi
dari
sumber
daya
linguistik
dan
keahlian
manusia,
dan
membandingkannya dengan kategori suasana hati yang ada pada teori literatur psikologi. Kategori suasana hati dalam musik yang digunakan adalah model Russell dengan menggunakan 8 cluster kata sifat, dan model Hevner yang menggunakan
11
28 jenis kata sifat yang terbagi dalam dimensi gairah dan valensi. Hasil dari penelitian ini adalah adanya hubungan yang baik antara literatur psikologi musik dengan realitas dalam mendengarkan musik, dimana keduanya sangat membantu para peneliti untuk memperbaiki model teoritis agar lebih sesuai dengan realita suasana hati yang diperoleh oleh pendengar musik (Xiao Hu, 2010). Mudiana Binti Mokhsim, dkk. dalam penelitiannya berjudul Automatic Music Emotion Classification Using Artificial Neural Network Based on Vocal and Instrumental Sound Timbre pada tahun 2014 melakukan penelitian untuk mendeteksi emosi pada musik Melayu menggunakan Artificial Neural Network dengan mengekstraksi fitur timbre/warna suara dari vokal dan musik instrumental. Menggunakan data audio berdurasi 30 detik untuk menghindari kesalahan pemilihan daerah ekstraksi fitur yang dapat menyebabkan ketidakakuratan pelatihan dan klasifikasi data. Ektraksi fitur yang digunakan diantaranya : Spectral Rolloff, Spectral Centroid, dan Zero Cross untuk melakukan klasifikasi emosi pada musik tersebut. Kategori emosi yang digunakan adalah : Happy/ gembira, Anger/ marah, Calmness/ tenang, dan Sad/ sedih. Hasil penlitian dengan menggunakan algoritma klasifikasi ANN ini terbukti berhasil hingga 75% (Mudiana Binti Mokhsim, dkk., 2014). Susheel Sharma dan Rakesh Singh Jadon dalam penelitiannya Mood Based Music Classification pada tahun 2014 melakukan penelitian klasifikasi musik berdasarkan suasana hati. Penelitiannya bertujuan untuk mengelompokkan musik berdasarkan suasana hati (bahagia, marah dan sedih). Dalam tahapan pembelajaran dan klasifikasi mereka menggunakan Neural Network, sedangkan untuk ekstraksi
12
fitur menggunakan : Energy feature, Entropy feature, zero-crossing rate, spectral rolloff, spectral centroid, spectral flux, RMS of signal dan MFCC. Kategori mood/suasana hati yang digunakan : senang, marah, dan sedih. Dalam implementasinya terdapat 90 lagu yang digunakan untuk training set dan 60 untuk pengujian. Hasil eksperimen menunjukkan hampir 75% efektivitas dalam klasifikasi sistem (Susheel Sharma dan Rakesh Singh Jadon, 2014). Samira Pouyanfar dan Hossein Sameti pada penelitiannya tahun 2014 berjudul Music Emotion Recognition Using Two Level Classification, mereka membuat sebuah metode baru yaitu SVM yang bertingkat (Two Level Classification) dalam pengklasifikasian meta data suasana hati dalam musik. Mereka menggunakan data audio berdurasi 30 detik sebagai data latih yang berasal dari 280 data musik yang populer dari www.allmusic.com dengan 4 kategori model emosi Thayer (happy/ gembira, relax/ rileks, angry/ marah, sad/ sedih). Untuk ekstraksi fitur menggunakan : MFCC (Mel-Frequency Cepstral Coefficients), Spectral Centroid, Spectral Rolloff, Zero Crossing Rate. Metode baru yang dibuat mampu meningkatkan tingkat akurasi klasifikasi dari 72,14% pada SVM dan 87,27% pada metode klasifikasi SVM baru yang mereka buat (Samira Pouyanfar dan Hossein Sameti, 2014) Seungwon Oh dan Minsoo Hahn dalam penelitiannya berjudul Music Mood Classification using Intro and Refrain Parts of Lyrics tahun 2013 mereka melakukan estimasi suasana hati hanya dengan mengambil bagian intro dan refrain dari lirik lagu. Selanjutnya dengan menggunakan 8 jenis emosi yang ada pada Plutchik's emotion model (Joy/ gembira, acceptance/ penerimaan, anticipation/
13
antisipasi, anger/ marah, disgust/ marah, sadness/ sedih, surprise/ kejutan, dan fear/ takut. Dengan menggunakan algoritma SVM dalam proses klasifikasi, serta menghitung kesamaan antara delapan emosi dasar. Selain itu, metode ini dapat memberikan rekomendasi lagu sesuai dengan suasana hati pendengar musik (Seungwon Oh dan Minsoo Hahn, 2013). Penelitian dengan metode klasifikasi C4.5 dan Decision Tree dilakukan oleh Vallabha Hampiholi pada tahun 2012 berjudul A method for Music Classification based
on
Perceived
Mood
Detection
for
Indian
Bollywood
Music. Metode yang diusulkan untuk mendeteksi suasana hati dalam musik Bollywood India berdasarkan Thayer's two dimensional emotion model (exuberance/ gembira, serene/ tenang, anxious/ cemas, depression/ depresi). Ekstraksi fitur dengan menggunakan : energy feature, zero crossing rate, dan rhythm feature. Tingkat keberhasilan 60% mendeteksi suasana hati secara akurat untuk musik Bollywood India, dan tingkat keberhasilan (40%) diperoleh ketika mendeteksi suasana hati dalam musik barat (Vallabha Hampiholi, 2012). Selanjutnya penelitian yang dilakukan oleh Kadek Cahya Dewi, dan Luh Arida Ayu Rahning Putri pada tahun 2011 berjudul Music Mood Player Implementation Applied In Daycare Using Self Organizing Map Method, membuat sebuah sistem untuk memutar lagu secara otomatis sesuai dengan suasana hati sesuai aktifitas yang ada pada Daycare. Klasifikasi suasana hati menggunakan metode Self Organizing Map yang selanjutnya hasilnya dicocokkan dengan Thayer's two dimensional emotion model (exuberance/ gembira, contentment/ rileks, anxious/ cemas, dan depression/ depresi). Sistem diuji dengan lagu dari
14
berbagai genre dan suasana hati/mood hasil klasifikasi dibandingkan dengan mood dari pakar psikologi anak. Mood lagu dari sistem dapat diset secara otomatis disesuaikan dengan aktivitas pada Daycare (Kadek Cahya Dewi, dan Luh Arida Ayu Rahning Putri, 2011). Arif Setiawan pada penelitiannya Analisis Klasifikasi Suara Berdasarkan Gender dengan Format WAV Menggunakan Algoritma K-Means tahun 2009, Penelitian ini menghasilkan pengklasifikasian suara berdasarkan jenis kelamin atau gender menggunakan metode K-Means dengan menggunakan ekstraksi fitur : Sort Time Energy, Zero Crossing Rate, Spectral Centroid, dan Spectral Flux (Arif Setiawan, 2009). Dalam penelitian yang berjudul A Music Recommendation System with a Dynamic K-Means Clustering Algorithm oleh Dong-Moon Kim, dkk. tahun 2007, penelitian ini menggunakan K-Means dinamis yang digunakan untuk membantu dalam proses rekomendasi pilihan genre musik dengan mempartisi klip musik untuk mempercepat proses rekomendasi. Penerapan Short Time Fourier Transform untuk menganalisa properti dari musik dan untuk ekstraksi fitur menggunakan : Zero Crossing Rate, Spectral Roll Off, dan Spectral Flux. Hasilnya pada nilai K antara 3 dan 4, metode ini menghasilkan rekomendasi cluster lagu yang cukup bagus, sedangkan waktu pemrosesan akan semakin lama jika nilai K semakin bertambah. Maka dari itu perlu perhatian yang lebih saat akan menentukan nilai K agar rekomendasi musik dapat mendekati sesuai yang diinginkan penggunanya (Dong-Moon Kim, dkk., 2007).
15
Braja Gopal Patra, dkk. melakukan penelitian terhadap lagu Hindi, dimana mereka menggunakan potongan klip lagu berdurasi 30 detik dengan sejumlah 230 lagu sebagai dataset. Dalam proses klasifikasinya menggunakan algoritma Decision Tree (J48), fitur audio yang digunakan diantaranya, ritme, intensitas sinyal audio, dan warna nada. Hasilnya sistem yang dibangun berhasil memperoleh nilai klasifikasi rata-rata sejumlah 51,56% (Braja Gopal Patra, dkk., 2013). Serta penelitian yang dilakukan oleh Garima Vyas, dkk. penelitian yang dilakukan untuk mengidentifikasikan mood/suasana hati dalam musik India dengan menggunakan algoritma K-Means dan ekstraksi fitur menggunakan Mel Frequency Cepstral Coeficients, fitur energi, dan perbedaan puncak energi pada sinyal audio. Ketiga fitur ini yang digunakan untuk proses clustering. Percobaan yang dilakukannya ini menghasilkan akurasi kesesuaian mood yang sangat tinggi yaitu sebesar 90% (Garima Vyas, dkk., 2014). Selanjutnya dapat dilihat pada Tabel 2.1 mengenai rangkuman dari semua penelitian terdahulu yang menjadi dasar penelitian ini. Tabel 2. 1 Rangkuman State of The Art No Judul 1. Music and Mood : Where Theory and Reality Meet
Penulis Xiao Hu, 2010
Metode Kategori suasana hati dalam musik : model Russell (menggunakan 8 cluster kata sifat), model Hevner (dimensi arousal/gairah dan valence/valens, 28 jenis emosi)
Deskripsi Hasil Penelitian ini membahas teori psikologi musik dan merangkum wawasan mendasar yang dapat membantu para peneliti Music Information Retrieval dalam menafsirkan suasana hati dalam musik,
16
dengan membandingkan antara model teoritis dengan semua kategori suasana hati yang muncul dari label sosial. 2.
Automatic Music Emotion Classification Using Artificial Neural Network Based on Vocal and Instrumental Sound Timbre
Mudiana Binti Mokhsim, Nurlaila Binti Rosli, Suzana Zambri, Nor Diana Ahmad, dan Saidatul Rahah Hamidi, 2014
Artificial Neural Network, Menggunakan ektraksi fitur : Spectral Rolloff, Spectral Centroid, dan Zero Cross. Kategori emosi : Happy/ gembira, Anger/ marah, Calmness/ tenang, dan Sad/ sedih.
Penelitian ini mendeteksi emosi pada musik Melayu menggunakan ANN, data audio berdurasi 30 detik, dengan mengekstraksi fitur timbre/warna suara dari vokal dan musik instrumental. Hasilnya ANN ini terbukti berhasil hingga 75%
3.
Mood Based Music Classification
Susheel Sharma, Rakesh Singh Jadon, 2014
Neural Network, menggunakan ekstraksi fitur : Energy feature, Entropy feature, zerocrossing rate, spectral rolloff, spectral centroid, spectral flux, RMS of signal and MFCC. Mood/suasana hati yang digunakan : senang, marah, dan sedih.
Penelitiannya bertujuan untuk mengelompokkan musik berdasarkan suasana hati (bahagia, marah dan sedih). Terdapat 90 lagu yang digunakan untuk training set dan 60 untuk pengujian. Hasil eksperimen menunjukkan hampir 75% efektif.
4.
Music Emotion Recognition Using Two Level Classification
Samira Pouyanfar, Hossein Sameti, 2014
SVM, SVM Two Level Classification, Thayer's two dimensional emotion model
Menggunakan data audio berdurasi 30 detik sebagai data latih. Metode baru yang dibuat mampu
17
(happy/ gembira, relax/ rileks, angry/ marah, sad/ sedih). Ekstraksi fitur : MFCC (Mel-Frequency Cepstral Coefficients), Spectral Centroid, Spectral Rolloff, Zero Crossing Rate.
meningkatkan tingkat akurasi klasifikasi dari 72,14% pada SVM dan 87,27% pada metode klasifikasi SVM baru yang mereka buat (SVM Two level Classification)
5.
Music Mood Classification using Intro and Refrain Parts of Lyrics
Seungwon Oh, Minsoo Hahn, 2013
SVM, Plutchik's emotion model (Joy/ gembira, acceptance/ penerimaan, anticipation/ antisipasi, anger/ marah, disgust/ marah, sadness/ sedih, surprise/ kejutan, dan fear/ takut
Metode yang diusulkan mendeteksi fitur penting yang dikaitkan dengan suasana lagu. Fitur audio diambil dari bagian intro dan refrain pada sebuah lagu. Dengan menghitung kesamaan antara delapan emosi dasar, Selain itu, metode ini dapat memberikan rekomendasi lagu sesuai dengan suasana hati pengguna.
6.
A method for Music Classification based on Perceived Mood Detection for Indian Bollywood Music
Vallabha Hampiholi, 2012
C4.5, Decision Tree, Thayer's two dimensional emotion model (exuberance/ gembira, serene/ tenang, anxious/ cemas, depression/ depresi) Ekstraksi fitur : energy feature,zero crossing rate, dan rhythm feature
Metode yang diusulkan untuk mendeteksi suasana hati dalam musik bollywood India berdasarkan Model suasana hati Thayer. Tingkat keberhasilan 60% mendeteksi mood secara akurat untuk musik bollywood India.
18
Dan tingkat keberhasilan (40%) diperoleh ketika mendeteksi mood dalam musik barat. 7.
Music Mood Player Implementation Applied In Daycare Using Self Organizing Map Method
Kadek Cahya Dewi, Luh Arida Ayu Rahning Putri, 2011
Self Organizing Map, Thayer's two dimensional emotion model (exuberance/ gembira, contentment/ rileks, anxious/ cemas, depression/ depresi), fitur yang digunakan rhythm pattern
Sistem diuji dengan lagu dari berbagai genre dan mood hasil klasifikasi dibandingkan dengan mood dari pakar psikologi anak.
8.
A Music Recommendation System with a Dynamic KMeans Clustering Algorithm
Dong-Moon Kim, Kun-su Kim, KyoHyun Park, Jee-Hyong Lee, dan Keon Myung Lee, 2007
K-Means yang dinamis, STFT untuk menganalisa properti musik. Menggunakan ekstraksi fitur : Zero Crossing Rate, Spectral Roll Off, dan Spectral Flux
Penelitian ini menggunakan KMeans dinamis yang digunakan untuk membantu dalam proses rekomendasi pilihan genre musik
9.
Analisis Klasifikasi Suara Berdasarkan Gender dengan Format WAV Menggunakan Algoritma KMeans
Arif Setiawan, 2009
K-Means, Menggunakan ekstraksi fitur : Sort Time Energy, Zero Crossing Rate, Spectral Centroid, Spectral Flux
Penelitian ini menghasilkan pengklasifikasian suara berdasarkan jenis kelamin atau gender menggunakan metode K-Means dengan ekstraksi fitur berupa sinyal audio.
Garima Vyas, Malay Kishore Dutta, 2014
K-Means, menggunakan ekstraksi fitur: MFCC, fitur energi, dan fitur perbedaan puncak energi sinyal audio
Penelitian ini menghasilkan tingkat akurasi sebesar 90% pada musik India
10. Automatic Mood Detection of Indian Music Using MFCCs and K-means Algorithm
19
Berdasarkan beberapa penelitian yang telah dilakukan, yang telah dirangkum dalam Tabel 2.1, maka dalam penelitian ini diusulkan pendekatan baru yang dapat dilihat pada Gambar 2.1, dimana dalam proses pengelompokan musik terhadap suasana hati menggunakan metode K-Nearest Neighbor dan K-Means dan pembanding pengujian sistem menggunakan Support Vector Machine dan ID3. Serta dalam proses mendapatkan nilai fitur dengan ekstraksi fitur dengan menggunakan metode Fast Fourier Transform dan sembilan jenis Spectral Analysis Features.
20
Gambar 2.1 Diagram Fishbone penelitian Gambar 2. 1 Diagram Fishbone penelitian 21
2.2 Music Information Retrieval (MIR) Music Information Retrieval (MIR) merupakan sebuah bidang ilmu untuk mengambil dan mengolah informasi dari file musik yang berupa metadata ataupun konten. Terdapat beberapa task dari penelitian di bidang Music Information Retrieval berdasarkan The Music Information Retrieval Evaluation eXchange (MIREX), yaitu Klasifikasi Genre, Klasifikasi Mood, Identifikasi Artis, Pengenalan Instrumen, dan Music Annotation (Fu et al, 2011). Chai merangkum penelitian dalam MIR dalam tiga bidang, yaitu Music Searching and Query by Examples, Music Classification, dan Music Segmentation and Summarization (Chai, 2005). Dalam bidang Music Searching and Query by Examples, sistem MIR membantu pengguna mencari musik berdasarkan isinya, berdasarkan informasi dari referensi tertentu. Music Classification adalah salah satu topik populer dalam MIR. Klasifikasi yang dilakukan beragam, bisa berdasarkan genre musik, penyanyi, dan emosi/mood. Music Summarization bertujuan menemukan bagian yang paling representatif dalam musik, hal ini sering diasumsikan pada bagian intro maupun refrain sebagai bagian yang paling sering diulang dari sepotong musik.
2.3 Emosi dan Suasana Hati pada Musik Selanjutnya akan dibahas mengenai pengertian serta perbedaan antara emosi dan suasana hati/mood yang merupakan hal penting menjadi bahan klasifikasi dan clustering dalam penelitian ini.
22
2.3.1 Definisi Emosi Emosi adalah satu set interaksi yang kompleks antara faktor-faktor objektif dan subjektif, dimediasi oleh sistem saraf/hormonal, yang dapat (a) menimbulkan pengalaman afektif seperti perasaan bergairah, kesenangan/ketidaksenangan; (b) menghasilkan proses kognitif seperti efek perseptual yang relevan, penilaian, proses pelabelan; (c) mengaktifkan penilaian yang meluas secara psikologis dengan kondisi serta gairah; dan (d) menyebabkan perilaku yang sering, namun tidak selalu, ekspresif, berorientasi tujuan, dan adaptif (Kleinginna dan Kleinginna, 1981; dikutip dalam Myers 2007). 2.3.2 Definisi Suasana Hati/ Mood Suasana hati atau mood adalah keadaan emosi yang relatif tahan lama. Mood berbeda dari emosi yang sederhana dimana emosi lebih bersifat bersifat kurang spesifik, kurang intens, dan kurang mungkin dipicu oleh stimulus atau peristiwa tertentu (Thayer, 1989). Sudah sejak lama suasana hati dan emosi telah menjadi subjek utama untuk analisis dan didiskusikan oleh para dari psikolog musik untuk menciptakan model terbaik yang mewakili mood/ suasana hati serta emosi dalam musik. Mood dan emosi bersifat subjektif, bervariasi antara satu orang ke orang lainnya dan juga tergantung pada pengaruh budaya dari orang tersebut. Selain itu biasanya ada banyak kata-kata yang dapat mendeskripsikan jenis mood dan emosi. Orang yang berbeda bisa memiliki persepsi yang berbeda pula terhadap mood dalam musik, padahal berasal dari stimulus musik yang sama dan sering menggunakan beberapa kata-kata yang berbeda untuk mengGambarkan pengalaman yang sama.
23
Beberapa model teoritis telah diajukan selama bertahun-tahun oleh Hevner dan Thayer. Model ini dapat dikelompokkan dalam dua pendekatan utama yaitu : model kategoris atau model dimensi. Model kategoris terdiri dari beberapa kategori atau beberapa kondisi emosi, seperti marah, takut, kebahagiaan dan sukacita, salah satu contoh dari hal ini adalah model lingkaran kata sifat yang diusulkan oleh Hevner. Sedangkan untuk model dimensi, menggunakan beberapa sumbu grafik untuk memetakan emosi. Pendekatan yang paling sering menggunakan dua sumbu misalnya gairah dan valensi (Arousal - Valence) atau energi dan stres. Manfaat utama dari model dimensi adalah mengurangi ambiguitas pengelompokan mood jika dibandingkan dengan pendekatan model kategoris (Song et al, 2012). Berikut ini adalah penjelasan lebih detail mengenai model emosi Hevner dan Thayer. A. Model Emosi Hevner Kate Havner dikenal sebagai peneliti terbaik dalam bidang psikologi musik, karena dia yang mengawali penelitian yang berkaitan dengan musik dan mood (Hevner, 1936). Hevner mengemukakan bahwa musik dan emosi memiliki hubungan yang sangat intim hal ini dikarenakan musik selalu membawa makna emosional di dalamnya. Sebagai hasil penelitiannya, dia memperkenalkan model emosi berdasarkan kata sifat yang dikenal sebagai model lingkaran kata sifat Hevner (Gambar 2.2) yang selanjutnya model ini digunakan sebagai dasar penelitian lainnya pada bidang pengelompokan mood dan emosi dalam musik.
24
Gambar 2. 2 Lingkaran kata sifat model emosi Hevner Sumber : Hevner K. 1936 Seperti yang ditunjukkan pada Gambar 2.2 dapat kita lihat bahwa kata sifat dalam setiap cluster memiliki kedekatan makna yang mendalam, dan makna dari setiap cluster yang berdekatan memiliki sedikit perbedaan. Hevner membuat daftar yang terdiri dari 67 kata sifat yang berbeda yang dibuat dalam delapan kelompok yang berbeda dengan cara melingkar. Terdapat sejumlah emosi yang berbeda pada setiap cluster namun sebagian besar dari kata-kata tersebut memiliki makna yang sama. Ambiguitas ini menimbulkan beberapa kesulitan yang terjadi dalam membedakan satu mood dengan lainnya untuk mendapatkan dasar kebenaran.
B. Model Emosi Thayer Pada tahun 1989 Robert Thayer mengusulkan sebuah model mood atau suasana hati secara dua dimensi (Thayer, 1989), model yang diusulkan tersebut menawarkan cara sederhana namun efektif untuk mewakili suasana
25
hati. Thayer mengadopsi pendekatan yang berbeda dari model Hevner. Model Thayer menyatakan suasana hati tergantung pada dua faktor, yaitu : stress
(happines/kebahagiaan
dan
anxiety/kecemasan)
dan
energi
(calm/tenang dan energy/berenergi) dikombinasikan dalam sumbu dua dimensi yang membentuk empat kuadran yang berbeda yaitu : contentment/kepuasan, mewakili jenis mood musik yang tenang dan bahagia; depression/depresi, mewakili jenis mood musik yang cemas dan depresi; exuberance/kegembiraan mewakili jenis mood musik yang mengacu pada bahagia dan energik; dan anxiety/kecemasan mewakili jenis musik yang panik, cemas, dan kalut. Untuk lebih jelasnya dapat dilihat pada Gambar 2.3. dan Gambar 2.4. Salah satu kelemahan dalam model ini adalah rendahnya granularity yang kurang mampu mendefinisikan emosi yang berbeda. Disisi lain keunggulan dari model ini adalah kesederhanaan dalam mengkategorikan mood yang dapat menurunkan ambiguitas makna.
Gambar 2. 3 Model dimensi emosi Thayer Sumber : Thayer
26
Gambar 2. 4 Diagram model emosi arousal-valence Thayer Sumber : Thayer, 1989 2.4 Evaluasi Model Musik Terhadap Mood Salah satu tantangan dalam merepresentasikan musik terhadap mood adalah untuk membedakan mood yang terkandung di dalam musik dengan mood yang dirasakan pada saat pendengar mendengarkan musik tersebut, karena perasaan suasana hati/mood antara kedua hal tersebut belum tentu selaras (Thoumas Eerola, 2011). Maka dari itu berbagai penelitian yang berhubungan dengan musik mengacu pada dua pendekatan dalam klasifikasi musik terhadap suasanahati/mood yaitu pendekatan secara kategoris dengan mengadopsi model Kate Hevner dan model emosi dimensional yang mengadopsi model emosi Thayer. Pendekatan kategoris mengGambarkan mood dengan sejumlah kategori yang umum seperti kebahagiaan, kesedihan, kemarahan, dan ketakutan. Sedangkan model dimensional mengGambarkan semua hal afektif yang timbul dari sistem neurofisiologis seperti
27
dimensi valensi (mood dari negatif hingga positif) dan gairah (mood dari tenang hingga bersemangat). Hevner telah melakukan evaluasi terhadap kesesuaian mood yang terkandung dalam musik dengan persepsi mood yang dirasakan olah pendengarnya. Pada eksperimen tersebut sejumlah responden diminta memberikan anotasi secara manual dengan menuliskan kata sifat yang muncul di pikiran mereka yang paling deskriptif terhadap musik yang diperdengarkan (Hevner, 1936). Eksperimen ini dilakukan utuk memperkuat hipotesis bahwa musik benar-benar membawa arti suasana hati/mood. Namun kelemahan dari penelitian yang menggunakan sejumlah responden ini adalah ketidaksesuaian hasil mood yang diakibatkan bisa saja dari latar belakang budaya, usia, serta pengalaman mendengarkan musik yang berbedabeda pada masing-masing responden. Disisi lain kurangnya validitas terhadap kebenaran database musik yang benar-benar valid untuk penelitian yang berkaitan dengan musik terhadap mood mengakibatkan sebagian besar peneliti menyusun database musik mereka sendiri (Yang, D., 2004). Sehingga terdapat berbagai macam database musik yang berbeda-beda yang telah digunakan sebagai dataset pengenalan suasana hati dalam berbagai penelitian. Hal inilah yang mengakibatkan terjadi banyak perbedaan hasil akurasi klasifikasi yang menggunakan berbagai algoritma pengenalan suasana hati terhadap musik. Pemberian anotasi secara manual adalah salah satu cara yang paling umum untuk melakukan penelitian dalam hal kaitan musik terhadap mood. Seperti metode penelitian yang serupa juga dilakukan oleh Vallabha Hampiholi yang meneliti
28
mengenai keterkaitan suasana hati dengan musik Bollywood (Hampiholi, V.2012). Penelitian dilakukan dengan anotasi manual melibatkan 30 orang pendengar musik (22 pendengar pria, dan 8 pendengar wanita, dengan usia rata-rata 28 tahun) semua pendengar musik tersebut berasal dari budaya India yang sama. Pendengar diminta untuk mendeskripsikan mood yang melekat pada 122 potongan klip musik dengan cara memberikan nilai pada skala 0-9. Pemberian anotasi jenis mood yang berbeda dapat dijelaskan dengan menggunakan istilah yang sama oleh pendengar yang memiliki perbedaan pengalaman mendengarkan musik, hal ini akan dapat menghasilkan prediksi anotasi yang buruk. Namun, dengan munculnya penemuan dalam bidang musik dan teknologi melahirkan situs-situs yang menyediakan rekomendasi musik sesuai mood, seperti www.audionetwork.com, www.allmusic.com dan www.last.fm. dengan mengakses situs-situs tersebut pendengar dapat mengakses informasi musik sesuai dengan anotasi/tag sosial. Anotasi/tag sosial memberikan informasi yang sangat relevan untuk pencarian informasi musik (MIR) dan telah menjadi sumber penting dari manusia yang menghasilkan pengetahuan kontekstual (Xiao Hu, 2007). Anotasi/tag sosial juga memberikan sumber data berkualitas tinggi dan dapat efektif dalam mendapatkan kesamaan musik terhadap mood.
2.5 Fast Fourier Transform Fast Fourier Transform (FFT) yang ditemukan tahun 1965 merupakan pengembangan dari Fourier Transform (FT). Penemu FT adalah J. Fourier pada tahun 1822. FT membagi sebuah sinyal menjadi frekuensi yang berbeda-beda dalam fungsi eksponensial yang kompleks. Definisi Fast Fourier Transform (FFT)
29
adalah metode yang sangat efisien untuk menghitung koefisien dari Fourier diskrit ke suatu sekuen terbatas dari data yang kompleks. Karena substansi waktu yang tersimpan lebih daripada metode konvensional, fast fourier transform merupakan aplikasi temuan yang penting di dalam sejumlah bidang yang berbeda seperti analisis spectrum, speech and optical signal processing, dan design filter digital. Algoritma FFT berdasarkan atas prinsip pokok dekomposisi perhitungan discrete fourier transform dari suatu sekuen sepanjang N ke dalam transformasi diskrit Fourier secara berturut-turut lebih kecil. Cara perhitungan dengan prinsip ini diterapkan ke arah suatu variasi dari algortima yang berbeda, di mana semuanya memperbandingkan peningkatan kecepatan perhitungan. Fast Fourier Transform adalah suatu algoritma untuk menghitung transformasi fourier diskrit dengan cepat dan efisien. Karena banyak sinyal-sinyal dalam sistem komunikasi yang bersifat kontinyu, sehingga untuk kasus sinyal kontinyu seperti sinyal suara dapat menggunakan transformasi fourier. Transformasi Fourier didefinisikan oleh persamaan (2.1): β
π (π) = β«ββ π (π‘)π βπ2πππ‘ ππ‘
(2.1)
Dimana s(f) adalah sinyal dalam domain frekuensi (frequency domain), s(t) adalah sinyal dalam domain waktu (time domain), dan π βπ2πππ‘ adalah konstanta dari nilai sebuah sinyal, f adalah frekuensi dan t adalah waktu. FFT (Fast Fourier Transform) merupakan salah satu metode untuk transformasi sinyal suara dalam domain waktu menjadi sinyal dalam domain frekuensi, artinya proses perekaman suara disimpan dalam bentuk digital berupa gelombang spectrum suara yang berbasis frekuensi sehingga lebih mudah dalam
30
menganalisa spectrum frekuensi suara yang telah direkam. Disisi lain penerapan FFT ini juga membantu dalam proses memfilter sinyal input dengan baik menjadi sinyal frekuensi (Reonaldo YS.,2014).
2.6 Feature Extraction Ekstraksi fitur/Feature Extraction adalah proses yang dilakukan untuk mengambil ciri-ciri dari sebuah data input. Ciri-ciri ini kemudian akan menjadi dasar untuk melakukan suatu pekerjaan tertentu pada tahap yang berbeda. Fiturfitur yang dihasilkan ini akan menentukan kelas dari sinyal input yang masuk. Ekstraksi fitur melibatkan analisis input dari sinyal audio. Ekstraksi fitur audio merupakan langkah yang paling penting dalam tahap pengenalan emosi dan mood dalam musik. Fitur-fitur hasil ekstraksi ini mewakili karakteristik yang terdapat pada sinyal audio dalam file musik. Teknik ekstraksi fitur audio dapat diklasifikasikan menjadi dua yaitu analisis temporal dan teknik analisis spektral. Analisis temporal menggunakan bentuk gelombang dari sinyal audio itu sendiri untuk dilakukan analisis, sedangkan analisis spektral menggunakan representasi spektral dari sinyal audio untuk analisis. Dalam Music Information Retrieval, beberapa peneliti sepakat bahwa ekstraksi fitur memegang peranan yang lebih penting daripada fase lainnya baik untuk tujuan klasifikasi musik maupun untuk tujuan pengenalan musik. Beberapa metode ekstraksi fitur yang digunakan dalam penelitian ini diantaranya (Alexander Lerch, 2012), pertama berdasarkan pada properti statistik (statistical property) dari sinyal audio, dimana fitur audio yang dianalisis berdasarkan panjang blok sinyal audio dan tingkat nada yang diperoleh dari proses
31
ekstraksi. Dalam hal ini nilai fitur audio diperoleh dengan menggunakan analisis spectral skewness dan kurtosis. Kedua, fitur audio diperoleh berdasarkan bentuk spektral (spectral shape) hal ini dapat diketahui berdasarkan timbre (warna suara/audio), pitch (tinggi-rendah nada) dan loudness (kuat-lemah suara). Untuk mendapatkan nilai fitur audio pada spectral shape ini diperoleh dengan spectral centroid, rolloff, slope, spread, decrease, dan flux. Ketiga, fitur audio diperoleh berdasarkan properti sinyal (signal properties) audio, dimana fitur audio yang dianalisis berdasarkan nada disepanjang sinyal audio, hal ini menggambarkan keharmonisan dalam musik. Untuk mendapatkan nilai fitur audio berdasarkan signal properties ini dengan menggunakan spectral flatness. Selanjutnya akan dijelaskan lebih rinci mengenai kesembilan jenis analisis spektral audio yang digunakan dalam penelitian ini. 2.6.1 Spectral Centroid Spectral Centroid merupakan indikator kecerahan spektrum yang ada, dan menunjukkan spektral pusat gravitasi. Spectral centroid menunjukkan tingkat kejernihan suara. Spectral centroid dapat dihitung dengan menggunakan persamaan (2.2; 2.3; 2.4) sebagai berikut π = β« π₯. π(π)ππ₯
(2.2)
dimana untuk menghitung p(f) : π(π) =
π΄(π) βπ π΄(π)
(2.3)
dan untuk menghitung A(f) : π΄(π) = |π [π₯(π‘)]|
(2.4)
32
Variabel x adalah merupakan frekuensi dari sample yang diambil. Sedangkan variabel p( f ) merupakan probabilitas untuk mengamati f. 2.6.2 Spectral Skewness Spectral Skewness adalah ukuran distribusi probabilitas asimetris dari variabel acak bernilai real dalam hal ini adalah spektrum sinyal audio. Fitur ini menunjukkan apakah ada atau tidak spektrum yang condong /skewed ke arah kisaran rata nilai aritmatik tertentu. Untuk sampel dari nilai N membentuk persamaan 2.5, dimana nilai skewness adalah : ππππ€πππ π =
π3 3
β π2 2
=
1 πβ1 .β (π₯(π)βπ₯Μ
)3 π π=0 3β 1 2 ( .βπβ1 (π₯(π)βπ₯Μ
)2) π πβ0
(2.5)
Pada persamaan di atas π₯Μ
menunjukkan rata-rata dari magnitude, π3 adalah sampel pada pusat spektrum ketiga, dan π2 adalah sample varian. 2.6.3 Spectral Rolloff Spectral Rolloff adalah ukuran bandwidth dari blok n yang dianalisa dari sampel audio. Spectral Rollof didefinisikan sebagai frekuensi dibawah akumulasi kekuatan STFT (short time fourier transform) yang mencapai persentase nilai π
tertentu antara 0,85 (85%) atau 0,95 (95%). Persamaan 2.6 untuk spectral rolloff adalah sebagai berikut : π
β
2 πππππ‘πππ π
πππππ = βππ=0|π(π, π)| = π
. βπ=0 |π(π, π)|
(2.6)
33
2.6.4 Spectral Slope Spectral Decrease merepresentasikan jumlah penurunan dari spektral energi sebagai fungsi frekuensi, asumsinya adalah spektrum amplitudo mengikuti model linear yaitu : π΄(π) = ππ + π
(2.7)
Slope m dihitung menggunakan regresi linear persamaan (2.8)
π=
πΎ 2
πΎ β1
πΎ β1
πΎ
β1
2 2 2 βπ=0 βπ=0 ππ΄(π)ββπ=0 π΄(π) πΎ 2
πΎ β1
πΎ β1
(2.8)
2 2 βπ=0 π 2 β(βπ=0 π)
Pada persamaan 2.8 tersebut K adalah jumlah total dari nilai frekuensi, A(k) adalah magnitude spektral dengan indeks frekuensi k. 2.6.5 Spectral Kurtosis Spectral Kurtosis menunjukkan keterpusatan dari spektrum audio, yang dapat digunakan untuk menunjukkan tingkat nada. Dihitung pada iterasi keempat. Untuk menghitung spectral kurtosis menggunakan persamaan 2.9 dan persamaan 2.10 yaitu : π4 = β«( π β π )4 . π(π)ππ₯
(2.9)
Dan nilai kurtosis : πΎ=
π4 π4
(2.10)
dimana, Β΅ = mean dan π = standar deviasi. 2.6.6 Spectral Spread Spectral spread, sering juga disebut sebagai spektral bandwidth instan atau sesaat, spektral ini menggambarkan konsentrasi kekuatan spektrum berada pada 34
sekitar spectral centroid. Hal ini dapat diartikan sebagai nilai standar deviasi dari kekuatan spektrum di sekitar spectral centroid. Persamaan 2.11 sebagai berikut : π
β1
2 (πβπππΆ(π))2.|π(π,π)|2 βπ=0
πππππ‘πππ ππππππ = β
π
(2.11)
β1
2 βπ=0 |π(π,π)|2
2.6.7 Spectral Decrease Spectral Decrease adalah jumlah penurunan dari amplitudo spektral. persamaan ini berasal dari persepsi dan lebih berhubungan dengan frekuensi sesusi persepsi manusia. Rumusnya adalah: πππππ‘πππ π·ππππππ π =
1 βπβ1 π=0 π₯(π)
. βπβ1 π=0
π₯(π)βπ₯(0)
(2.12)
πβ1
Pada persamaan 2.12 ini π₯(π) merepresentasikan nilai bobot frekuensi atau magnitude dari nilai π. 2.6.8 Spectral Flux Spectral Flux digunakan untuk mengukur perubahan bentuk spektral, hal ini didefinisikan sebagai perbedaan rata-rata antara frame pada spektrum audio secara berturut-urut. π
πππππ‘πππ πΉππ’π₯ =
ββ β2β1(|π(π,π)|β|π(π,πβ1)|)2 π=0 π
β 2
(2.13)
Spectral flux dapat diartikan sebagai pendekatan dasar untuk dapat melihat tingkat kekasaran pada spektrum audio. 2.6.9 Spectral Flatness Spectral Flatness adalah ukuran distribusi nada dan kekuatan spektral dalam spektrum audio. Spectral Flatness dihitung dengan membagi rata-rata
35
geometris dari kekuatan spektrum oleh rata-rata aritmetik dari kekuatan spektrum. Spectral Flatness digunakan dalam pengukuran seluruh spektrum. Persamaan 2.14 adalah sebagai berikut : π
πππππ‘πππ πΉπππ‘πππ π =
ββπβ1 π=0 π₯(π) βπβ1 π=0 π₯(π)
(2.14)
π
Dalam persamaan ini, nilai x(n) adalah magnitude nilai n dari kekuatan spektrum dengan panjang N.
2.7 Data Mining Data mining merupakan suatu istilah yang digunakan untuk kegiatan menemukan informasi atau pengetahuan di dalam basis data. Data mining adalah suatu proses yang menggunakan teknik statistik, matematika, kecerdasan tiruan dan machine learning untuk mengekstraksi dan mengidentifikasi informasi yang bermanfaat dan pengetahuan yang terkait dari berbagai database besar. Menurut Gartner Group, data mining adalah suatu proses menemukan hubungan yang berarti, pola dan kecenderungan dengan memeriksa dalam sekumpulan besar data yang tersimpan dalam peyimpanan dengan menggunakan teknik pengenalan pola seperti teknik statistik dan matematika (Larose, 2005). Saat ini, data mining mengalami kemajuan yang luar biasa yang terus berlanjut karena beberapa faktor antara lain : 1.
Pertumbuhan yang cepat dalam kumpulan data
2.
Adanya penyimpanan data dalam Data Warehouse sehingga seluruh perusahaan memiliki hak akses kedalam data base yang handal
3.
Adanya peningkatan akses data melalui navigasi web dan intranet
36
4.
Tekanan kompetisi bisnis untuk meningkatkan penguasaan pasar dalam globalisasi ekonomi
5.
Perkembangan teknologi perangkat lunak untuk data mining (ketersediaan teknologi).
6.
Perkembangan
kemampuan
komputasi
dan
kapasitas
media
penyimpanan. Berry dan Linof dalam buku Mastering Data Mining memberikan pernyataan bahwa dalam data mining otomatisasi tidak menggantikan campur tangan manusia. Manusia harus ikut aktif dalam setiap fase data mining (Kusrini, 2009). Dalam pemanfaatannya, data mining dibagi menjadi beberapa kelompok yaitu (Kusrini, 2009) : a) Deskripsi Dimana peneliti ingin menampilkan pola atau kecenderungan yang terdapat dalam data. Deskripsi atau pola sering memberikan kemungkinan penjelasan untuk suatu pola atau kecenderungan. b) Estimasi Estimasi mirip dengan klasifikasi, hanya saja variabel target dari estimasi lebih mengarah ke numerik daripada kategori.
Model yang
dibangun menggunakan record lengkap yang menyediakan nilai dari variabel target sebagai nilai prediksi. Selanjutnya, pada peninjauan berikutnya estimasi, estimasi nilai dari variabel target dibuat berdasarkan nilai variabel prediksi.
37
c) Prediksi Prediksi memiliki fungsi yang hampir sama dengan klasifikasi dan estimasi, tetapi dalam prediksi, nilai dari hasil akan ada dimasa mendatang. Misalnya prediksi harga gula dalam 6 bulan yang akan datang. Beberapa metode dan teknik yang digunakan dalam klasifikasi dan estimasi dapat pula digunakan untuk prediksi. d) Klasifikasi Dalam klasifikasi, terdapat target variabel kategori. Sebagai contoh penggolongan pendapatan dapat dipisahkan dalam tiga kategori yaitu pendapatan tinggi, pendapatan sedang, pedapatan rendah. Contoh lain klasifikasi adalah menentukan suatu transaksi dengan kartu kredit adalah transaksi yang sah atau penipuan. e) Clustering Cluster adalah kumpulan record yang memiliki kemiripan antara satu dengan yang lainnya dan tidak mirip dengan record-record dalam cluster yang lain. Clustering berbeda dengan klasifikasi karena tidak terdapat variabel target. Dalam clustering, dilakukan pembagian terhadap keseluruhan data menjadi kelompok-kelompok yang memiliki kemiripan (homogen). Contoh dari proses ini adalah memperoleh kelompokkelompok konsumen dengan berdasarkan tingkat pembelian dari konsumen. f) Asosiasi
38
Asosiasi berfungsi untuk menemukan atribut yang muncul dalam satu waktu. Dalam dunia bisnis dikenal dengan analisis keranjang belanja (market basket analysis) Terdapat banyak teknik dalam data mining seperti metode statistik, pohon keputusan, rule based, algoritma genetika, agen cerdas, dan beberapa teknik lain meliputi aturan dan visualisasi data. Dalam data mining, algoritma merupakan hal penting. Ketika berhadapan dengan data perilaku pelanggan yang dapat meliputi ratusan dimensi atau lebih, maka algoritma harus mampu menghadapi secara efektif. Pengetahun terhadap batasan bisnis, hubungan diantara produk-produk dan berbagai perilaku segmen pelanggan merupakan suatu keharusan (Turban, 2005).
2.8 K-Nearest Neighbor Algoritma K-Nearest Neighbor atau yang biasa disebut K-NN merupakan metode pengklasifikasian data yang bekerja relatif dengan cara yang lebih sederhana dibandingkan dengan metode pengklasifikasian data lainnya. Algoritma ini berusaha mengklasifikasikan data baru yang belum diketahui class-nya dengan memilih data sejumlah k yang letaknya terdekat dari data baru tersebut. Class terbanyak dari data terdekat sejumlah k tersebut dipilih sebagai class yang diprediksikan untuk data yang baru. k umumnya ditentukan dalam jumlah ganjil untuk menghindari munculnya jumlah jarak yang sama dalam proses pengklasifikasian. Beberapa hal yang diperhatikan untuk menggunakan algoritma ini dengan efektif dan dapat menghasilkan pengklasifikasian dengan akurasi tinggi antara lain:
39
a. Pemilihan k Pemilihan jumlah k yang paling tepat perlu dijajaki agar error rate bisa diperkecil. b. Feature Selection Untuk meningkatkan tingkat akurasi pengklasifikasian, satu hal yang juga bisa dilakukan adalah dengan melakukan feature selection. Berbeda dengan Neural Network, dimana setiap input diberikan bobot yang berbeda-beda, K-NN tidak memberikan bobot (weight) pada data inputnya. Dengan kata lain, semua data input mempunyai bobot (weight) dengan nilai 1. Untuk menghilangkan feature yang irrelevan, perlu dilakukan feature selection. c. Feature Scaling: berfungsi untuk mengkonversi variabel (feature) asli ke dalam bentuk variabel (feature) bayangan yang merupakan cerminan gabungan
dari
feature-feature
yang
diikutkan
dalam
proses
pengklasifikasian. Cerminan gabungan ini berisikan variabel summary yang terkait
erat
dengan
kelas-kelas
model
yang
menjadi
tujuan
pengklasifikasian. d. Searching Algorithm (Indexing Algorithm): Untuk mempercepat proses pencarian data terdekat sejumlah k, khususnya untuk data dalam jumlah besar, pemilihan searching algorithm dalam bentuk indexing algorithm dapat meningkatkan keefektifan proses pengklasifikasian. Ada beberapa searching algorithm yang bisa digunakan termasuk Linear Scan, Kd-trees, Ball-trees,
Metric-trees,
Locality
Sensitive
Hashing
(LSH)
dan
Agglomerative Nearest Neighbour.
40
K-NN mengambil keputusan bahwa data baru d termasuk dalam kelas C berdasarkan beberapa tetangga terdekat dari d. Jika digunakan jarak Eukledian sebagai ukuran kedekatan maka d akan menjadi pusat hypersphere dengan jari-jari r sama dengan jarak eukledian tersebut. Yang dilakukan adalah menaikkan r sehingga hyperspere memuat k data. Kelas untuk data d diberikan berdasarkan jumlah anggota kelas terbanyak yang muncul dalam hyperspere yang berpusat di d tersebut. Dekat atau jauhnya tetangga biasanya dihitung berdasarkan jarak Euclidean dengan persamaan (2.15) sebagai berikut : π = β(π1 β π1 )2 + (π2 β π2 )2 + β¦ + (ππ β ππ )2 π = ββππ=1(ππ β ππ )2
(2.15)
Klasifikasi K-NN dilakukan dengan mencari k-buah tetangga terdekat dan memilih kelas dengan ki terbanyak pada kelas Οi. Adapun langkah-langkah klasifikasi K-NN adalah sebagai berikut: 1. Jika sekumpulan vektor data latih memiliki N titik data secara keseluruhan, maka kenalilah k-buah tetangga terdekat dari sampel x dimana k merupakan bilangan ganjil. 2. Dari k-buah tetangga terdekat tersebut, identifikasikan jumlah vektor ki pada kelas Οi, i = 1,2,...,m dengan Ξ£i ki = k. 3. Masukkan x pada kelas Οi dengan nilai ki maksimum. 4. Jika terdapat dua atau lebih kelas Οi yang memiliki E tetangga terdekat, maka terjadilah kondisi seimbang (konflik) dan digunakan strategi pemecahan konflik.
41
5. Untuk masing-masing kelas yang terlibat dalam konflik, tentukan jarak di antara x dengan kelas Οi berdasarkan E tetangga terdekat yang ditemukan pada kelas Οi. 6. Jika pola pelatihan ke-m dari kelas Οi yang terlibat dalam konflik ditunjukkan dengan yim = { y1im , β¦., yNim} maka jarak antara x dengan kelas Οi adalah: ππ =
1 πΈ
ππ βπ π=1|(π₯π β π¦π )|
(2.16)
7. Masukkan x ke dalam kelas dengan jarak di paling kecil, yaitu xβ ΟC, jika dC < di untuk i, Cβ[1,...,M] dan i β C.
2.9 K-Means Clustering Klasifikasi dalam tugasnya untuk mengelompokkan data telah memberikan label kelasnya, sehingga dalam tugas berikutnya adalah membuat model yang mampu memprediksi data baru yang kemudian dapat diketahui kelasnya. Berbeda dengan konsep clustering, dalam pengelompokkan data dilakukan dengan pemecahan/segmentasi atau pemisahan data ke dalam jumlah cluster/kelompok menurut karakteristik tertentu yang diinginkan, dalam tugasnya mengelompokan data, label dari setiap data belum dapat diketahui dan dengan proses pengelompokan ini diharapkan dapat diketahui kelompok data untuk kemudian diberikan label sesuai dengan keinginan. Analisa cluster adalah pekerjaan untuk mengelompokkan data yang didasarkan
hanya
pada
informasi
yang
ditentukan
dalam
data
yang
mendeskripsikan objek tersebut dan hubungan diantaranya (Tan, 2006). Tujuannya adalah agar data yang tergabung dalam sebuah kelompok merupakan objek-objek yang mirip/berhubungan satu sama lainnya dan berbeda/tidak berhubungan dengan 42
objek/data pada kelompok lainnya. Semakin besar kemiripan data dalam kelompok dan semakin besar perbedaanya dengan kelompok lain, maka kelompok/cluster tersebut akan semakin baik. Menurut jumlah keanggotaan dalam kelompok/cluster, pengelompokan data dapat dikategorikan eksklusif, artinya sebuah data bisa dipastikan hanya menjadi anggota satu kelompok dan tidak menjadi anggota pada kelompok lainnya. Metode pengelompokan data ini adalah K-Means dan DBSCAN. Algoritma K-Means diperkenalkan pertama kali oleh J.B. MacQueen pada tahun 1976. K-Means adalah suatu metode analisis cluster yang bertujuan untuk mempartisi sejumlah n banyak data observasi ke dalam kelompok k dimana masingmasing data observasi termasuk dalam cluster dengam nilai mean terdekat. KMeans merupakan salah satu algoritma belajar terawasi yang paling sederhana dalam memecahakan masalah clustering. Metode ini mempartisi data ke dalam cluster (kelompok) sehingga data yang memiliki karakteristik yang sama dikelompokkan ke dalam cluster yang sama dan data yang mempunyai karakteristik berbeda dikelompokkan ke dalam kelompok lainnya. Berikut merupakan langkahlangkah dalam algoritma K-Means clustering : a. Menentukan jumlah cluster. b. Menentukan nilai centroid. Dalam menentukan nilai centroid pada awal iterasi, nilai awal dari centroid ditentukan secara acak. Sedangkan pada saat penentuan nilai centroid yang merupakan tahap dari iterasi, maka digunakan persamaan 2.17 : 1
ππ = π βπ₯βπΆπ π₯ π
(2.17)
43
Dimana : x adalah suatu objek (data observasi). Ci adalah cluster ke-i. ci adalah centroid baru dari cluster Ci. mi adalah jumlah objek (data) pada cluster ke-i. c. Menghitung jarak antara titik centroid dengan tiap objek (data). Untuk menghitung jarak tersebut dapat menggunakan euclidean distance untuk mencari jarak terdekat antara titik centroid dengan tiap objek (data). Persamaan ecludean distance dapat dilihat pada persamaan 2.18 : (2.18)
π·π = β(π₯π β π π )2 + (π¦π β π‘π )2 Dimana : π·π adalah Ecludian Distance π adalah banyaknya objek (data) (π₯, π¦) adalah koordinat objek (data) (π , π‘) adalah koordinat centroid d. Pengelompokan objek (data). Untuk
menentukan
anggota
cluster
caranya
adalah
dengan
memperhitungkan jarak minimum objek (data) terhadap tiap cluster yang ada. Nilai diperoleh dalam keanggotaan data pada distance matriks adalah 0 atau 1, dimana nilai 1 untuk data yang dialokasikan ke cluster dengan jarak terpendek dengan data yang diuji dan nilai 0 untuk data yang dialokasikan ke cluster yang lain. e. Kembali ke tahap 2, lakukan perulangan hingga centroid yang dihasilkan
44
tetap (convergen) dan anggota cluster tidak berpindah ke cluster lain. Berikut ini pada Gambar 2.5 merupakan ilustrasi dari setiap langkah-langkah clustering data menggunakan algoritma K-Means. Mulai
Menentukan nilai k sebagai jumlah cluster
Menentukan centroid
Tidak
Menentukan jarak setiap dokumen terhadap centroid
Kelompokkan data berdasarkan jarak terpendek
Objek tidak ada yang berpindah dari grup?
Ya
Selesai
Gambar 2. 5 Diagram alir proses clustering K-Means 2.10 Support Vector Machine Support Vector Machine (SVM) juga merupakan suatu teknik yang relatif baru dikenalkan tahun 1995 untuk melakukan prediksi, baik dalam kasus klasifikasi maupun regresi, yang sangat populer belakangan ini. SVM berada dalam satu kelas dengan Artificial Neural Network (ANN) dalam hal fungsi dan kondisi
45
permasalahan yang bisa diselesaikan. Keduanya masuk dalam kelas supervised learning. Baik para ilmuwan maupun praktisi telah banyak menerapkan teknik ini dalam menyelesaikan permasalahan nyata dalam kehidupan sehari-hari. Terbukti dalam banyak implementasi, SVM memberi hasil yang lebih baik dari ANN, terutama dalam hal solusi yang dicapai. ANN menemukan solusi berupa local optimal sedangkan SVM menemukan solusi yang global optimal. Tidak heran bila kita menjalankan ANN solusi dari setiap training selalu berbeda. Hal ini disebabkan solusi local optimal yang dicapai tidak selalu sama. SVM selalu mencapi solusi yang sama untuk setiap running. Dalam teknik ini, kita berusaha untuk menemukan fungsi pemisah (classifier) yang optimal yang bisa memisahkan dua set data dari dua kelas yang berbeda. 2.10.1 Karakteristik SVM Karakteristik SVM sebagaimana telah dijelaskan pada bagian sebelumnya, dirangkumkan sebagai berikut: 1. Secara prinsip SVM adalah linear classifier. 2. Pattern recognition dilakukan dengan mentransformasikan data pada input space ke ruang yang berdimensi lebih tinggi, dan optimisasi dilakukan pada ruang vektor yang baru tersebut. Hal ini membedakan SVM dari solusi pattern recognition pada umumnya, yang melakukan optimisasi parameter pada ruang hasil transformasi yang berdimensi lebih rendah daripada dimensi input space. 3. Menerapkan strategi Structural Risk Minimization (SRM) 4. Prinsip kerja SVM pada dasarnya hanya mampu menangani klasifikasi dua class.
46
2.10.2 Kelebihan dan Kekurangan SVM Semua teknik klasifikasi memiliki kelebihan dan kekurangan, tapi semua itu lebih bersifat relatif. SVM dapat menjadi alat yang berguna untuk analisis kegagalan, dalam kasus non-linear dalam data, misalnya ketika data tidak teratur didistribusikan atau memiliki distribusi yang tidak diketahui. SVM dapat membantu mengevaluasi informasi, yaitu rasio keuangan yang harus diubah sebelum memasuki skor teknik klasifikasi klasik. Keuntungan dari teknik SVM dapat diringkas sebagai berikut (Laura Auria dkk : 2008): 1. Dengan memperkenalkan kernel, SVMs mendapatkan fleksibilitas dalam pilihan bentuk ambang memisahkan dari perusahaan bangkrut, yang perlu tidak linear dan bahkan kebutuhan tidak memiliki fungsional yang sama formulir untuk semua data, karena fungsinya adalah non-parametrik dan beroperasi secara lokal. Sebagai konsekuensinya mereka dapat bekerja dengan rasio keuangan, yang menunjukkan hubungan non-monoton ke skor dan probabilitas default, atau yang non-linear, dan ini tanpa perlu kerja spesifik pada setiap variabel non-monoton. 2. Sejak kernel implisit mengandung transformasi non-linear, tidak ada asumsi tentang fungsional bentuk transformasi, yang membuat data secara linear terpisah, diperlukan. Transformasi terjadi implisit secara teoritis yang kuat dan penilaian keahlian manusia sebelumnya tidak diperlukan. 3. SVM memberikan out-of-sample generalisasi yang baik, jika parameter C dan r (dalam kasus Gaussian kernel) yang tepat dipilih. Ini berarti bahwa, dengan
47
memilih kelas generalisasi yang tepat,SVM bisa menjadi kuat, bahkan ketika sampel pelatihan memiliki beberapa perbedaan. 4. SVM memberikan solusi yang unik, karena masalah optimalitas cembung. Ini merupakan keuntungan dibandingkan Neural Networks, yang memiliki beberapa solusi terkait dengan minima lokal dan untuk alasan ini mungkin tidak akan kuat lebih sampel yang berbeda. 5. Dengan pilihan kernel yang sesuai, seperti kernel Gaussian, seseorang dapat menempatkan lebih banyak tekanan pada kesamaan antara perusahaan, karena lebih mirip struktur keuangan dari dua perusahaan yaitu, lebih tinggi adalah nilai kernel. Jadi ketika mengklasifikasikan sebuah perusahaan baru, nilai-nilai rasio keuangan dibandingkan dengan yang dari vektor dukungan dari sampel pelatihan yang lebih mirip dengan ini perusahaan baru. Perusahaan ini kemudian diklasifikasikan menurut dengan yang kelompok itu memiliki kesamaan terbesar. Disamping kelebihannya, SVM memiliki kelemahan atau keterbatasan, antara lain: 1.
Sulit dipakai dalam problem berskala besar. Skala besar dalam hal ini dimaksudkan dengan jumlah sample yang diolah.
2.
SVM secara teoritik dikembangkan untuk problem klasifikasi dengan dua class. Dewasa ini SVM telah dimodifikasi agar dapat menyelesaikan masalah dengan class lebih dari dua, antara lain strategi one versus rest dan strategi Tree Structure. Namun demikian, masing-masing strategi ini memiliki kelemahan, sehingga dapat dikatakan penelitian dan pengembangan SVM pada multiclassproblem masih merupakan tema penelitian yang masih terbuka.
48
Konsep SVM dapat dijelaskan secara sederhana sebagai usaha mencari hyperplane terbaik yang berfungsi sebagai pemisah dua buah class pada input space. Gambar 2.5 memperlihatkan beberapa pattern/pola yang merupakan anggota dari dua buah class : +1 dan β1. Pattern yang tergabung pada class β1 disimbolkan dengan kotak hitam, sedangkan pattern pada class +1, disimbolkan dengan lingkaran putih. Problem klasifikasi dapat diterjemahkan dengan usaha menemukan garis (hyperplane) yang memisahkan antara kedua hyperplane dalam ruang vector berdimensi d adalah affine subspace berdimensi d-1 yang membagi ruang vektor tersebut ke dalam dua bagian, yang masing-masing berhubungan pada class yang berbeda kelompok tersebut. Berbagai alternatif garis pemisah (discrimination boundaries) ditunjukkan pada Gambar 2.6 Hyperplane pemisah terbaik antara kedua class dapat ditemukan dengan mengukur margin hyperplane tersebut. dan mencari titik maksimalnya. Margin adalah jarak antara hyperplane dengan pattern terdekat dari masing-masing class. Pattern yang paling dekat ini disebut sebagai support vector. Garis lurus pada Gambar 2.6 menunjukkan hyperplane yang terbaik, yaitu yang terletak tepat pada tengah-tengah kedua class, sedangkan titik merah dan kuning yang berada dalam lingkaran hitam adalah support vector. Usaha untuk mencari lokasi hyperplane ini merupakan inti dari proses pembelajaran pada SVM.
49
Gambar 2. 6 Kemungkinan hyperplane untuk memisahkan kumpulan data linear 2.10.3 Maximum Margin Hyperplanes Gambar 2.5 memperlihatkan plot dataset yang berisi contoh-contoh yang termasuk dua kelas berbeda yang direpresentasikan sebagai kotak dan lingkaran. Himpunan data linear juga dapat dipisahkan, yaitu kita dapat menemukan hyperplane sehingga semua kotak berada pada satu sisi hyperplane dan semua lingkaran berada di sisi lain. Namun, seperti yang ditunjukkan pada Gambar 2.5, ada hyperplanes memungkinkan yang jauh lebih banyak. Meskipun kesalahan pelatihan mereka adalah nol, tidak ada jaminan bahwa hyperplanes akan melakukan sama baik dengan contoh sebelumnya tak terlihat. Classifier harus memilih salah satu hyperplanes untuk mewakili keputusan batas, berdasarkan seberapa baik mereka diharapkan untuk melakukannya pada contoh uji. Untuk mendapatkan gambaran yang lebih jelas tentang bagaimana pilihan yang berbeda dari hyperplanes yang mempengaruhi kesalahan generalisasi, perhatikan dua batas keputusan, B1 dan B2, yang ditunjukkan pada Gambar 2.6. 50
Kedua batas keputusan dapat memisahkan kasus pelatihan ke dalam kelas masingmasing tanpa melakukan kesalahan klasifikasi. Setiap B1 batas keputusan dikaitkan dengan sepasang hyperplane yang masing-masing dinotasikan sebagai b11, dan b12. B11 diperoleh dengan memindahkan hyperplane paralel jauh dari batas keputusan sampai menyentuh persegi terdekat (s), sedangkan b12 diperoleh dengan memindahkan hyperplane sampai menyentuh lingkaran terdekat (s). Jarak antara kedua hyperplane dikenal sebagai margin dari classifier. Dari diagram ditunjukkan pada Gambar 2.7, perhatikan bahwa margin untuk B1 adalah jauh lebih besar dari B2. Dalam contoh ini, B1 ternyata menjadi hyperplane margin maksimum dari contoh pelatihan.
Gambar 2. 7 Margin batas kemungkinan
2.10.4 Linear Support Vector Machine Sebuah SVM dinyatakan sebagai linear classifier yang mencari hyperplane dengan margin terbesar, yang karena itu sering dikenal sebagai classifier margin
51
maksimal. Untuk memahami bagaimana SVM belajar seperti batas, di mulai dengan beberapa pendahuluan pembahasan tentang batas keputusan dan margin dari classifier linier. A. Linear batas keputusan Pertimbangkan masalah klasifikasi biner yang terdiri dari kasus pelatihan N. Setiap contoh dilambangkan dengan sebuah tuple (xi, yi) (i = 1, 2, ..., N), dimana xi = (xi1, xi2, ..., xid)T sesuai dengan atribut set untuk contoh ith. Oleh konvensi, biarkan yi β {-1, 1} menunjukkan label kelasnya. Batas keputusan seorang classifier linier dapat ditulis dalam persamaan 2.19 berikut: w. x + b = 0
(2.19)
dimana w dan b adalah parameter dari model. Gambar 2.8 menunjukkan satu set dua dimensi pelatihan yang terdiri dari kotak dan lingkaran. Sebuah batas keputusan yang membagi dua kasus pelatihan ke kelas mereka masing-masing yang digambarkan dengan garis solid. Contoh apapun yang terletak di sepanjang batas keputusan harus memenuhi persamaan diatas. Misalnya, jika xa dan xb adalah dua titik yang terletak pada batas keputusan, maka : w. xa + b = 0
(2.20)
w. xb + b = 0
(2.21)
Dengan mengurangkan dua persamaan diatas maka akan menghasilkan persamaan berikut: w. (xa β xb) = 0
(2.22)
52
Gambar 2. 8 Batas kemungkinan dan margin dari SVM dimana xb - xa adalah paralel vektor ke batas keputusan dan diarahkan dari xa untuk xb. Karena perkalian titik adalah nol, arah untuk w harus tegak lurus terhadap batas keputusan, seperti yang ditunjukkan pada Gambar 2.8. Untuk setiap xs persegi yang terletak di atas batas keputusan, kita dapat menunjukkan bahwa : w. xs + b = k
(2.23)
di mana k> 0. Demikian pula, untuk setiap xc lingkaran yang terletak di bawah batas keputusan, kita dapat menunjukkan bahwa π€. π₯π + π = π β²
(2.24)
di mana k'<0. Jika kita label semua kotak sebagai kelas +1 dan semua lingkaran sebagai kelas -1, maka kita dapat memprediksi label kelas y untuk setiap contoh uji z dalam mengikuti cara: π¦ = {
1, ππ π€. π§ + π > 0; β1, ππ π€. π§ + π < 0
(2.25)
53
B. Margin dari sebuah classifier linear Perhatikan persegi dan lingkaran yang paling dekat dengan batas keputusan. Sejak daerah yang terletak di atas batas keputusan, maka harus memenuhi persamaan w. xs + b = k untuk beberapa nilai k positif, sedangkan lingkaran harus memenuhi persamaan π€. π₯π + π = π β² untuk beberapa nilai kβ negatif. Kita bisa rescale parameter w dan b dari batas keputusan sehingga dua hyperplanes paralel Bi1 dan Bi2 dapat dinyatakan sebagai berikut: Bi1 : w . x + b =1
(2.26)
Bi2 : w . x + b = -1
(2.27)
Margin dari batas keputusan yang diberikan oleh jarak antara dua hyperplanes. Untuk menghitung margin, maka x1 menjadi titik data yang terletak di Bi1 dan x2 menjadi titik data pada Bi2. Setelah mengganti titiktitik ini ke Persamaan (2.26) dan (2.27), d margin dapat dihitung dengan mengurangkan persamaan kedua dari persamaan pertama: w . (x1 β x2) = 2
(2.28)
||w|| x d = 2
(2.29)
π=
2 βπ€β
(2.30)
C. Pembelajaran Model SVM Linear Tahap pelatihan SVM melibatkan perkiraan parameter w dan b dari batas keputusan dari data pelatihan. Parameter harus dipilih dalam sedemikian rupa dengan memenuhi dua kondisi dibawah ini :
54
w . xi + b β₯ 1 if yi = 1
(2.31)
w. xi + b β€ -1 if yi = -1
(2.32)
Kondisi ini memberlakukan persyaratan bahwa semua contoh pelatihan dari kelas y = 1 (yaitu, kotak) harus berada pada atau di atas hyperplane yang w Β· x + b = 1, sedangkan contoh-contoh dari kelas y = -1 (yaitu, lingkaran) harus berada pada atau di bawah hyperplane w Β· x + b = -1. Kedua ketidaksetaraan dapat diringkas dalam bentuk yang lebih kompak sebagai berikut yi (w . xi + b) β₯ 1, I = 1, 2, β¦, N
(2.33)
Meskipun kondisi sebelumnya juga berlaku untuk setiap pengklasifikasi linear (termasuk perceptrons), SVM memberlakukan persyaratan tambahan bahwa margin batas keputusannya harus maksimal. Memaksimalkan margin, bagaimanapun, adalah setara dengan meminimalkan fungsi tujuan berikut: f(w) =
βπ€β2 2
(2.34)
Tugas belajar di SVM dapat diformalkan sebagai masalah optimasi terkendala berikut: πππ π€ dimana
βπ€β2 2
yi (w . xi + b) β₯ 1, i = 1,2, β¦, N
(2.35) (2.36)
Karena fungsi tujuan adalah kuadrat dan kendala yang linear dalam parameter w dan b, ini dikenal sebagai masalah optimasi cembung, yang dapat diselesaikan dengan menggunakan metode Lagrange multiplier
55
standar. Setelah adalah sketsa singkat tentang ide-ide utama untuk memecahkan masalah optimasi. Pertama, kita harus menulis ulang fungsi tujuan dalam bentuk yang memperhitungkan menjelaskan kendala dikenakan pada solusinya. Fungsi baru Tujuan dikenal sebagai Lagrangian untuk masalah optimasi: πΏπ =
1 2
βπ€β2 β βπ π=1 ππ (π¦π (π€. π₯π + π ) β 1)
(2.37)
dimana Ξ»i parameter yang disebut pengali Lagrange. Istilah pertama dalam Lagrangian adalah sama dengan fungsi tujuan asli, sedangkan yang kedua istilah menangkap kendala ketidaksetaraan. Untuk memahami mengapa tujuan fungsi harus dimodifikasi, pertimbangkan fungsi tujuan asli diberikan dalam persamaan f(w) =
βπ€β2 2
. Sangat mudah untuk menunjukkan
bahwa fungsi diminimalkan ketika w = 0, sebuah nol vektor yang komponen semua nol. Solusi seperti itu, bagaimanapun, melanggar kendala diberikan dalam definisi karena tidak ada solusi yang layak untuk b. Solusi untuk w dan b adalah tidak layak jika mereka melanggar ketidaksamaan kendala; yaitu, jika yi (w Β· xi + b) -1 <0. The Lagrangian diberikan dalam persamaan πΏπ =
1 2
βπ€β2 β βπ π=1 ππ (π¦π (π€. π₯π + π ) β 1) ,
yang
menggabungkan
kendala ini dengan mengurangi istilah dari tujuan fungsi aslinya. Dengan asumsi bahwa Ξ»i β₯ 0, jelas bahwa setiap solusi yang tidak feasible mungkin hanya meningkatkan nilai Lagrangian tersebut. Untuk meminimalkan Lagrangian, harus mengambil turunan dari Lp terhadap w dan b dan atur ke nol :
56
ππΏπ ππ€ ππΏπ ππ
= 0 ==> π€ = βππ=1 ππ πΎπ ππ
(2.38)
= 0 ==> π€ = βππ=1 ππ πΎπ = 0
(2.39)
Karena pengali Lagrange tidak diketahui, masih tidak dapat memecahkan untuk w dan b. Jika Definisi berisi kesetaraan hanya bukan kendala ketimpangan, maka kita dapat menggunakan persamaan N dari kendala kesetaraan bersama dengan Persamaan sebelumnya untuk menemukan solusi yang layak untuk w, b, dan Ξ»i. Perhatikan bahwa pengali Lagrange untuk kendala persamaan adalah parameter bebas yang dapat mengambil nilai-nilai. Salah satu cara untuk menangani kendala ketidaksamaan adalah untuk mengubah mereka ke dalam set kendala kesetaraan. Hal ini dimungkinkan selama pengganda Lagrange dibatasi untuk menjadi nonnegatif. Transformasi tersebut mengarah ke hal berikut kendala pada pengganda Lagrange, yang dikenal sebagai Karush-Kuhn-Tucker (KKT) kondisi: π1 β₯ 0 , π1 [π¦π (π€. π₯π + π) β 1] = 0
(2.40)
Sekilas, mungkin tampak bahwa ada sebanyak Lagrange multipliers karena ada kasus pelatihan. Ternyata banyak dari Lagrange pengganda menjadi nol setelah menerapkan batasan yang diberikan dalam Persamaan 5.42. Menyatakan kendala bahwa pengganda Lagrange Ξ»i harus nol kecuali pelatihan misalnya xi memenuhi persamaan yi (w Β· xi + b) = 1. seperti pelatihan misalnya, dengan Ξ»i> 0, terletak di sepanjang hyperplanes Bi1 atau Bi2 dan dikenal sebagai mendukung vektor. Pelatihan kasus yang tidak
57
bertempat tinggal di sepanjang hyperplanes memiliki Ξ»i = 0. Memecahkan masalah optimasi sebelumnya masih cukup tugas yang menakutkan karena melibatkan sejumlah besar parameter: w, b, dan Ξ»i. Masalahnya dapat disederhanakan dengan mengubah Lagrangian ke fungsi dari Lagrange pengganda saja (ini dikenal sebagai masalah ganda). Hal ini akan menyebabkan perumusan ganda berikut dari masalah optimasi: πΏπ· = βπ π=1 ππ β
1 2
βππ ππ ππ π¦π π¦π π₯π . π₯π
(2.41)
Perbedaan utama antara Lagrangian ganda dan utama adalah sebagai berikut: 1.
Lagrangian ganda hanya melibatkan pengganda Lagrange dan data pelatihan, sedangkan Lagrangian utama melibatkan pengganda Lagrange serta parameter batas keputusan. Namun demikian, solusi untuk kedua masalah optimasi yang setara.
2.
Istilah kuadrat dalam persamaan di atas memiliki tanda negatif, yang berarti bahwa asli masalah minimisasi melibatkan Lagrangian primer, Lp, telah berubah menjadi masalah
maksimisasi melibatkan
Lagrangian ganda, Ld. Untuk set data yang besar, masalah optimasi ganda dapat diselesaikan dengan menggunakan numerik teknik seperti pemrograman kuadratik, sebuah topik yang berada di luar lingkup buku ini. Setelah itu Ξ»i ditemukan, kita dapat menggunakan Persamaan yang telah dibahas sebelumnya untuk mendapatkan solusi yang layak untuk w dan b. Batas keputusan dapat dinyatakan sebagai berikut.
58
(βπ π=1 ππ π¦π π₯π . π₯ ) + π = 0
(2.42)
b diperoleh dengan menyelesaikan persamaan untuk vektor-vektor dukungan. Karena itu Ξ»i dihitung secara numerik dan dapat memiliki kesalahan numerik, nilai dihitung untuk b mungkin tidak unik.. Dalam prakteknya, nilai rata-rata untuk b dipilih menjadi parameter dari batas keputusan. 2.10.5 Nonlinier Support Vector Machine Ketika menerapkan SVM ke data linear yang terpisah kita sudah mulai dengan membuat matriks H dari produk dot variabel masukan: π»ππ = π¦π π¦π π(π₯π , π₯π ) = π₯π . π₯π = π₯ππ π₯π
(2.43)
k (xi, xj) adalah contoh dari keluarga fungsi disebut Kernel Fungsi (k (xi, xj) =π₯ππ π₯π yang dikenal sebagai Kernel Linear). Himpunan fungsi kernel terdiri dari varian dimana mereka semua didasarkan pada perhitungan produk dalam dari dua vektor. Ini berarti bahwa jika fungsi dapat menyusun kembali ke dalam ruang dimensi yang lebih tinggi dengan beberapa fungsi fitur non-linear pemetaan yang berpotensi π₯ β π(π₯), hanya produk dalam dari input yang dipetakan dalam ruang fitur tanpa perlu kita tentukan perhitungan secara eksplisit. Alasan bahwa Kernel Trick berguna adalah bahwa ada banyak masalah klasifikasi / regresi yang tidak dapat dipisahkan secara linear / regressable dalam waktu x input, yang dalam ruang dimensi yang lebih tinggi diberikan sebuah fitur pemetaan yang cocok π₯ β π(π₯).
59
Gambar 2. 9 Data dikotomis yang dipetakan kembali menggunakan Kernel Dasar Radial Mengacu pada Gambar 2.9, jika kita mendefinisikan kernel menjadi:
π(π₯π , π₯π ) = π
βπ₯π β π₯π β ( 2π2
2
)
(2.44)
maka satu set data yang tidak linear terpisah dalam dua ruang data dimensi x (seperti pada sisi kiri dari Gambar 2.9) terpisah di ruang fitur nonlinier (sisi kanan Gambar 2.9) didefinisikan secara implisit oleh fungsi kernel nonlinier yang dikenal sebagai Kernel Dasar Radial. Kernel populer lainnya untuk klasifikasi dan regresi adalah Kernel Polinomial yang didefinisikan sebagai berikut : π(π₯π , π₯π ) = (π₯π . π₯π + π)2
(2.45)
dan sigmoidal kernel π(π₯π , π₯π ) = π‘πβπ (ππ₯π . π₯π β π)
(2.46)
dimana a dan b merupakan parameter yang mendefinisikan kebiasaan dari kernel. Ada banyak fungsi kernel, termasuk yang bertindak atas set, string dan bahkan musik. Ada persyaratan untuk fungsi yang dapat diterapkan sebagai fungsi kernel yang berada di luar lingkup ini pengenalan yang sangat singkat ke daerah. 60
2.10.6 Multi Class SVM SVM pada dasarnya berdasarkan kelas biner, yang artinya SVM pertama kali dikembangkan untuk memecahkan klasifikasi antara dua kelas. Dalam implementasi nyata, kemampuan ini tidak cukup karena adanya banyak variasi permasalahan klasifikasi yang akan ditemui. Misalnya, pada penelitian ini dilakukan untuk mengelompokkan mood/suasana hati terhadap musik secara otomatis, dan ada 4 mood yang diklasifikasi yaitu 1) Contentment/ kepuasan, 2) Exuberance/ gembira, 3) Depression/ depresi, dan 4) Anxious/ cemas; kalut. Oleh karena itu, Multi Class SVM dikembangkan dengan gagasan untuk menciptakan lebih dari satu hyperplane. Ada beberapa metode yang mendukung Multi Class SVM, seperti One-Against-One (OAO), One-Against-All (OAA) dan Directed Acyclic Graph SVM (DAGSVM). Beberapa penelitian telah dilakukan untuk membandingkan metode ini, dan hasilnya menunjukkan bahwa OAO lebih cocok untuk penggunaan Multi Class SVM secara praktis daripada metode lainnya. Hasil penelitian juga menunjukkan bahwa
OAO
adalah
classifier
terbaik
untuk
masalah
besar
dengan
mempertimbangkan semua data sekaligus pada umumnya memerlukan dukungan vektor yang lebih sedikit (Hsu & Lin, 2002). Hasil penelitian yang sama juga diperoleh oleh penelitian Reddy dan Bellary (2012). OAO adalah metode di mana salah satu data dari kelas sedang dibandingkan dengan salah satu data dari kelas lain, dan proses ini diulang untuk kelas yang tersisa lainnya. Diharapkan terdapat tiga kelas dalam klasifikasi yaitu A, B, dan C. OAO berarti bahwa perbandingan akan dilakukan dari A ke B = AB, A ke C = AC,
61
kemudian B ke C = BC. Dengan melakukan ini kita akan mendapatkan tiga hyperplane AB, AC, dan BC. Hasilnya kemudian didefinisikan dengan menggunakan jumlah maksimum data yang diklasifikasikan.
2.11 Decision Tree Decision Tree merupakan salah satu metode data mining yang digunakan, yang merupakan sebuah flowchart seperti struktur pohon, dimana setiap titik pohon merupakan atribut yang telah diuji. Bagian awal dari pohon keputusan ini adalah titik akar (root), sedangkan setiap cabang dari decision tree merupakan pembagian berdasarkan hasil uji, dan titik akhir (leaf) merupakan kelas-kelas yang dihasilkan. Pada umumnya proses dari sistem decision tree adalah mengadopsi strategi pencarian
top-down
untuk
solusi
ruang
pencariannya.
Pada
proses
mengklasifikasikan sampel yang tidak diketahui, nilai atribut akan diuji pada decision tree dengan cara melacak jalur dari titik akar sampai titik akhir, kemudian akan diprediksikan kelas yang ditempati sampel baru tersebut. Decision tree mempunyai 3 tipe simpul yaitu: a. Simpul akar (root node) dimana tidak memiliki cabang yang masuk dan memiliki cabang lebih dari satu, terkadang tidak memiliki cabang sama sekali. b. Simpul internal dimana hanya memiliki 1 cabang yang masuk, dan memiliki lebih dari 1 cabang yang keluar. c. Simpul daun (leaf node) atau simpul akhir dimana hanya memiliki 1 cabang yang masuk, dan tidak memiliki cabang keluar sama sekali yang menandai bahwa simpul tersebut merupakan label dari kelas.
62
Tahap awal dilakukan pengujian simpul akar, jika pada pengujian simpul akar menghasilkan sesuatu maka proses pengujian juga dilakukan pada setiap cabang berdasarkan hasil dari pengujian. Hal ini berlaku juga untuk simpul intemal dimana suatu kondisi pengujian baru akan diterapkan pada simpul daun. 2.10.1 Algoritma ID3 Algoritma ID3 (Iterative Dichotomizer 3) adalah algoritma decision tree learning (algoritma pembelajaran pohon keputusan) yang paling dasar. Algoritma ini melakukan pencarian secara rakus/menyeluruh (greedy) pada semua kemungkinan pohon keputusan. Algoritma ID3 sering digunakan dalam machine learning dan data mining karena kemudahannya untuk digunakan dan keefektifannya. J. Rose Quinlan mengembangkannya pada tahun 1986 berdasarkan algoritma Concept Learning System (CLS). Algoritma ID3 membentuk decision tree dari beberapa data simbolik yang bersifat tetap ataupun historikal untuk melakukan pembelajaran mengklasifikasikan data tersebut dan memprediksi klasifikasi data yang baru. Data harus memiliki beberapa atribut dengan nilai yang berbeda. Selain itu data ini juga harus memiliki beragam standar, class yang diskrit (misal: Yes/No). Decision tree memilih atribut untuk pengambilan keputusan dengan menggunakan Information Gain. Struktur dasar dari ID3 adalah iteratif. Sebuah subset dari training set disebut window,
dipilih secara acak dan dibentuk pohon keputusan. Pohon ini
mengklasifikasikan semua objek pada window, kemudian objek-objek lain pada training set ini kemudian diklasifikasikan menggunakan pohon tersebut. Jika pohon tersebut memberikan jawaban yang benar untuk semua objek, maka dinyatakan
63
benar juga untuk seluruh training set dan selanjutnya seluruh proses dihentikan. Jika tidak, objek terpilih yang belum terklasifikasikan akan ditambahkan ke window dan proses berlanjut. Algoritma ini membentuk pohon keputusan dengan cara pembagian dan menguasai sampel secara rekursif dari atas ke bawah. Algoritma ID3 dimulai dengan semua data yang ada sebagai akar dari pohon keputusan. Sebuah atribut yang dipilih akan menjadi pembagi dari sampel tersebut. Untuk setiap atribut dari cabang yang telah dibentuk, semua sampel yang memiliki nilai yang sama dengan atribut cabang akan masuk dalam anggotanya dan dinamakan anak cabang. Berikut ini merupakan algoritma dari ID3: 1. Masukkan : Data sampel, daftar dari atribut tes 2. Buat node N. 3. Jika sampel berada pada kelas yang sama, maka N akan menjadi leaf node (node akhir) dan diberi nama dengan nama kelas yang sesuai, kemudian proses prosedur ini dihentikan. Jika tidak, maka lanjutkan proses ke langkah 4. 4. Untuk setiap atribut tes, lakukan perhitungan information gain masingmasing atribut tes. 5. Pilih atribut tes, atribut dengan information gain terbesar, sebagai atribut split yang akan digunakan untuk membagi data sampel 6. Beri nama node N dengan atribut split. 7. Untuk setiap nilai yang mungkin (ai) dari atribut split, Lakukan langkah 7 sampai dengan langkah 9.
64
8. Buat sampel baru si dengan kondisi atribut split sama dengan ai. 9. Lakukan pembuatan node menggunakan βProsedur Decision Tree ID3β dengan si sebagai data sampel yang baru, dan daftar atribut adalah dari sampel tersebut Tujuan dari pengukuran nilai information gain adalah untuk memilih atribut yang akan dijadikan cabang pada pembentukan pohon keputusan. Atribut yang memiliki nilai information gain yang tertinggi akan dipilih menjadi atribut uji untuk dijadikan cabang pohon. 2.10.2 Entropy & Information Gain Metode dasar ID3 adalah memilih atribut-atribut untuk klasifikasi dengan menggunakan metode statistik dimulai dari tree bagian atas. Cara memilih atribut adalah dengan menggunakan properti statistikal yang disebut dengan information gain, yang didefinisikan untuk menentukan ukuran nilai dari suatu atribut. Sebelumnya sebuah objek yang diklasifikasikan dalam pohon harus diuji nilai entropinya. Entropy adalah ukuran dari teori informasi yang dapat mengetahui karakteristik dari impurity dan homogenity dari kumpulan data. Dari nilai entropy tersebut kemudian dihitung nilai information gain (IG) masing-masing atribut. Nilai entropy didefinisikan sebagai berikut: πΈ (π) = βπ π βππ β log 2 (ππ )
(2.47)
Dimana Pi adalah rasio dari kelas Ci didalam set data sampel S = {x1,x2,... xk} ππ =
β π₯π βπΆπ π
(2.48)
65
Sebagai contoh, set sampel S mempunyai 14 anggota, dimana didalamnya ada 9 sampel positif dan 5 sampel negatif. Entropy dari S adalah : πΈ (9 + ,5 β) = β (
9 9 5 5 ) β log 2 ( ) β ( ) β log 2 ( ) = 0.940 14 14 14 14
Pada beberapa kasus, jika semua member dari set sampel S memiliki nilai yang sama, maka nilai entropy adalah nol. Hal itu berarti tidak ada klasifikasi yang mempunyai ketidakpastian (uncertainty). Namun jika jumlah sampel positif sama dengan jumlah sampel negatif, maka entropy bernilai 1, berarti ketidakpastian bernilai maksimum. Ini berarti set sampel tidak mempunyai ketidakpastian (keputusan dari decision tree sudah jelas). Jika jumlah sampel positif tidak sama dengan jumlah sampel negatif, maka nilai entropy akan berada diantara 0 dan 1. Dari rumus entropy diatas dapat disimpulkan bahwa definisi entropy (S) adalah jumlah bit yang diperkirakan dibutuhkan untuk dapat mengekstrak suatu kelas (+ atau -) dari sejumlah data acak pada suatu ruang sampel S. Entropy bisa dikatakan sebagai kebutuhan bit untuk menyatakan suatu kelas. Semakin kecil nilai entropy maka semakin baik digunakan dalam mengekstraksi suatu kelas. Setelah mendapat nilai entropy untuk suatu kumpulan data, maka kita dapat mengukur efektivitas suatu atribut dalam mengklasifikasikan data. Ukuran efektifitas ini disebut information gain. Secara matematis, infomation gain dari suatu atribut A, dituliskan sebagai berikut : πΊ(π, π΄) = πΈ (π) β βπ£βππππ’ππ (π΄)
|ππ£ | |π|
πΈ(ππ£ )
(2.49)
dimana : bobot ππ =
|ππ£ | |π|
merupakan rasio dari data dengan atribut v di dalam set sampel
66
A : atribut V : suatu nilai yang mungkin untuk atribut A Values (A) : himpunan yang mungkin untuk atribut A |Sv| : jumlah sampel untuk nilai v |S| : jumlah seluruh sampel data E(Sv) : entropy untuk sampel-sampel yang memilki nilai v
2.12 Pengujian Accuracy untuk Sistem Klasifikasi Dalam bidang Music Information Retrieval tahapan pengujian adalah hal yang penting untuk mengetahui seberapa besar kinerja dari algoritma klasifikasi dan clustering yang digunakan untuk mengelompokkan musik berdasarkan mood/suasana hati yang terdapat dalam musik itu sendiri. Pada penelitian ini menggunakan teknik pengujian accuracy/akurasi. Akurasi didefinisikan sebagai tingkat kedekatan antara nilai prediksi dengan nilai aktual (Putubuku, 2008). Secara umum akurasi untuk pengelompokan jenis musik terhadap mood dapat dirumuskan sebagai berikut: Akurasi Jenis Mood =
Misalkan
Jumlah Data Test Yang Sesuai Jumlah Data Test Jenis Mood
untuk
proses
x 100%
mengukur
kinerja
(2.50)
dari
sebuah
sistem
pengelompokan suasana hati/mood dalam musik yang bertugas memisahkan salah satu jenis suasana mood yang ada dari semua jenis mood yang telah didapat. Untuk mengujinya pada sistem dengan memasukkan 100 file musik dengan jenis mood exuberance/gembira. Hasilnya sistem tersebut memisahkan 88 file musik yang dideteksi sebagai musik dengan mood exuberance.
67
Dari kasus tersebut maka dapat simpulkan bahwa sistem tersebut memiliki akurasi sebesar 88% yang didapatkan dari perhitungan berikut: Jumlah Data Test Yang Sesuai
Akurasi Mood Exuberance = Jumlah Data Test Mood Exuberance x 100%
ππππ’ππππ¦ =
88 π₯ 100% = ππ% 100
Pengujian untuk mengukur persentase akurasi sistem klasifikasi dan clustering ini dilakukan dengan melakukan benchmarking, dimana pengujian yang mengacu kepada standar acuan terhadap objek yang akan dibandingkan. Benchmark adalah suatu metode yang digunakan untuk mengevaluasi kinerja sistem, dan menggunakan hasil evaluasi tadi untuk dibandingkan dengan sistem lainnya. Dalam Hal ini penyusunan dataset training dan dataset testing sudah dikelompokkan
berdasarkan
cluster-cluster
yang
ada
pada
situs
www.audionetwork.com. Sistem klasifikasi dan clustering yang dibangun ini diuji untuk dapat diketahui unjuk kerja sistem yang terdiri dari : pertama, seberapa besar persentase ketepatan klasifikasi oleh sistem pada data testing yang selanjutnya dibandingkan dengan label mood asli dari data testing yang telah ditentukan oleh situs www.audionetwork.com.
Kedua,
mengukur
waktu
kecepatan
proses
pengelompokan yang dilakukan oleh sistem, hal ini diukur mulai saat pengguna menekan tombol
βklasifikasiβ
dalam
antarmuka
sistem
hingga
sistem
memunculkan kotak dialog label mood hasil klasifikasi. Perhitungan kecepatan proses pengelompokan sistem ini dilakukan dalam kode pemrogramanan Matlab yaitu dengan fungsi tic
untuk menjalankan
68
stopwatch awal untuk mencatat waktu internal pelaksanaan perintah klasifikasi. Serta fungsi toc untuk menampilkan waktu yang diperlukan untuk menjalankan proses klasifikasi.
2.13 Pengujian Silhouette Coefficient untuk Sistem Clustering K-Means Silhouette Coefficient digunakan untuk melihat kualitas dan kekuatan cluster, seberapa baik suatu objek ditempatkan dalam suatu cluster. Metode ini merupakan gabungan dari metode cohesion dan separation. Meskipun clustering adalah pengelompokkan data yang memiliki kemiripan data, tetap diperlukan beberapa pengukuran untuk menentukan dua objek mirip atau tidak mirip. Untuk menentukan kemiripan tersebut dapat digunakan pengukuran yang disebut dengan distance measure diantaranya menggunakan Euclidean Distance, Manhattan Distance, dan Chebyshev Distance (M. Anggara, dkk., 2016). Tahapan perhitungan Silhouette Coefficient adalah sebagai berikut : 1. Hitung rata-rata jarak dari suatu data misalkan i dengan semua data lain yang berada dalam satu cluster : π (π ) =
1 |π΄|β1
β π βπ΄,πβ π π (π, π)
(2.51)
2. Hitung rata-rata jarak dari data i tersebut dengan semua data di cluster lain, dan diambil nilai terkecilnya. π (π, πΆ ) =
1 |π΄|
β π β πΆ π (π, π)
(2.52)
dengan d(i,C) adalah jarak rata-rata data i dengan semua objek pada cluster lain C dimana A β C. π(π ) = min πΆ β π΄ π(π, πΆ)
(2.53)
69
3. Nilai Silhouette Coefficient-nya adalah : π (π ) =
π(π)βπ(π)
(2.54)
max(π(π),π(π))
Nilai silhouette coefficient
dapat bervariasi antara -1 hingga 1.
Hasil clustering dikatakan baik jika nilai silhouette coefficient bernilai positif (a(i) < b(i)) dan a(i) mendekati 0, sehingga akan menghasilkan nilai silhouette coefficient yang maksimum yaitu 1 saat a(i) =0. Dengan demikian, jika s(i)=1 berarti objek i sudah berada dalam cluster yang tepat. Jika nilai s(i)= 0 maka objek i berada diantara dua cluster sehingga objek tersebut tidak jelas harus dimasukkan ke dalam cluster A atau cluster B. Akan tetapi, jika s(i) = -1 artinya struktur cluster yang
dihasilkan overlapping,
sehingga
objek i lebih
tepat
dimasukkan ke dalam cluster yang lain (Tahta Alfina, dkk., 2012). Nilai ratarata silhouette dari tiap objek dalam suatu cluster adalah suatu ukuran yang menunjukkan seberapa ketat/fit data dikelompokkan dalam cluster tersebut. Berikut ini adalah ukuran nilai silhouette coefficient (SC) (Kaufman & Rousseeuw,1990): 0.7 < SC <= 1 strong structure 0.5 < SC <= 0.7 medium structure 0.25 < SC <= 0.5 weak structure SC <= 0.25 no structure
70