BAB III ANALISIS Bab ini membahas analisis yang dilakukan pada Tugas Akhir ini, mencakup analisis permasalahan secara garis besar, yaitu bagaimana menggunakan sistem pembelajaran mesin untuk membentuk pola improvisasi musik jazz.
3.1 Analisis Teknik Improvisasi yang Dikaji Pada penelitian ini, teknik improvisasi musik jazz yang dikaji adalah improvisasi pembentukan melodi. Pola melodi yang dibentuk adalah pola melodi secara horizontal (unisono) dengan hanya mempertimbangkan 2 buah atribut yaitu progresi akor masukan dan melodi asli lagu. Teknik improvisasi berdasarkan melodi asli lagu dilakukan dengan cara menghias melodi asli sedemikian rupa sehingga terbentuk melodi baru yang tidak jauh berbeda dengan melodi asli. Sedangkan, teknik improvisasi berdasarkan progresi akor masukan menjamin bahwa nada-nada improvisasi yang dipilih merupakan anggota dari nada-nada pada suatu tangga nada yang cocok dengan progresi akor masukan. Asosiasi yang terjadi antara tangga nada dengan akor tertentu terbentuk karena melodi yang dipilih dari tangga nada tersebut dianggap enak didengar jika disertai dengan permainan akor yang bersesuaian. 3.1.1 Teknik Improvisasi Melodi dengan Memodifikasi Melodi Asli Teknik improvisasi dengan memodifikasi melodi asli merupakan teknik improvisasi yang paling awal yang digunakan oleh para musisi jazz. Teknik ini biasa digunakan pada awal perkembangan musik jazz di awal tahun 1900-an [FUR07]. Pola melodi improvisasi yang dibentuk sangat sederhana dan hanya sebatas menghias melodi asli dengan mengubah letak jatuhnya melodi, menambah atau mengurangi durasi suatu melodi, dan menambah melodi baru. Selain itu, tidak ada aturan atau panduan khusus yang dibuat untuk melakukan modifikasi melodi. Semuanya bergantung pada cita rasa dari musisi yang melakukan improvisasi.
Gambar III-1 merupakan contoh pembentukan melodi improvisasi 2 bar pertama hasil modifikasi dari melodi aslinya. III-1
III-2
Gambar III-1 Melodi Improvisasi Hasil Modifikasi Melodi Asli
Pada perkembangan berikutnya, berdasarkan pengalaman dan kebiasaan yang dilakukan oleh para musisi jazz, disertai dengan faktor selera dari para penikmat jazz, terdapat sebuah panduan sederhana untuk menentukan pemilihan not-not yang terdengar “buruk”. Pada terminologi musik jazz, not-not yang terdengar “buruk“ tersebut disebut sebagai avoid notes. Berikut ini daftar beberapa avoid notes untuk kasus-kasus tertentu yang berperan sebagai panduan konvensional bagi musisi jazz dalam berimprovisasi . 1. Not ke-4 dari tangga nada major pada setiap akor major (Contoh: not F pada akor C major), kecuali pada akor major 11th atau sus 4. 2. Not ke-3 dari tangga nada major pada setiap akor minor (Contoh: not E pada akor C minor). 3. Not ke-3 dari tangga nada minor pada setiap akor major 7th (Contoh: not Eb atau D# pada akor C major 7th). 4. Not dasar (root note) sebagai sustained note pada setiap akor akor major 7th. 5. Not b9th pada setiap akor major 7th atau akor minor (Contoh: not Db pada akor C major 7th atau C minor). 6. Not b6th pada setiap akor major 7th atau akor minor (Contoh: not Ab pada akor C major 7th atau C minor). 7. Not ke-7 pada setiap akor minor 7th atau akor dominan 7th (Contoh: not B pada akor C minor 7th atau C7).
Namun demikian, terkadang avoid notes seringkali digunakan untuk menambah ornamen melodi yang terbentuk. Pada terminologi musik jazz, avoid notes yang dipaksa untuk digunakan biasa dinamakan dengan passing notes. Berikut ini contoh penggunaan passing notes yang ditambahkan sebagai ornamen pola melodi pada akor C major 7th.
III-3
Gambar III-2 Penggunaan Passcfing Notes pada Akor Cmaj7
Pada Gambar III-2, nada D# dan nada Db merupakan passing note karena nada-nada tersebut termasuk avoid notes untuk akor C major 7th (aturan 3 dan 5). Nada-nada tersebut seharusnya dihindari untuk digunakan karena diklaim sebagai nada yang terdengar “buruk” apabila dimainkan pada akor C major 7th. Namun demikian, penggunaan nada-nada “buruk” tersebut pada saat yang tepat, seperti gambar 12, dapat menimbulkan efek dramatis atau emosional. Perlu ditekankan bahwa tidak ada aturan khusus mengenai passing notes. Penggunaan passing notes yang enak didengar atau dramatis biasanya dicapai oleh para musisi jazz yang memiliki kemampuan tingkat tinggi dan pengalaman yang cukup. 3.1.2 Teknik Improvisasi Melodi berdasarkan Pemilihan Tangga Nada dan Akor Seiring dengan perkembangan musik jazz, aturan-aturan yang sebelumnya hanya berfungsi sebagai panduan sederhana mengenai avoid notes kemudian berkembang menjadi aturan yang lebih luas dan kompleks. Aturan-aturan tersebut mencakup hubungan antara progresi akor dengan melodi pada tangga nada yang cocok. Kemungkinan hubungan yang dibentuk antara tangga nada yang cocok dengan suatu akor dapat dikatakan tidak terbatas. Namun, pada musik jazz tradiosional terdapat beberapa hubungan antara tangga nada dan akor yang lazim dipakai untuk melakukan improvisasi. Berikut ini Tabel III-1 yang menunjukkan tangga nada-tangga nada yang sering dipakai untuk melakukan improvisasi per akor masukan pada nada dasar C.
III-4
Tabel III-1 Hubungan Akor-Tangga Nada pada Musik Jazz [SAB92]
Akor
Tangga Nada
Cmaj7, Cmaj9, C6, C Cmaj7#11
C major, C lydian, C major bebop, C major pentatonic, G major pentatonic C lydian, B in sen
Cm7, Cm9, Cm11, Cm
C dorian, C minor bebop, C minor pentatonic, F major pentatonic, Bb major pentatonic, Eb major bebop, C blues, C minor
Cm6, Cm
Cm-maj7
C dorian, C melodic minor, C minor pentatonic, F major pentatonic, Bb major pentatonic, C minor bebop, Eb major bebop, D in sen C melodic minor, C harmonic minor, Eb major bebop
Cm7b6
C minor, Ab major pentatonic
Cm7b9
C phrygian, C phrygian #6
C7, C9, C13, C
C mixolydian, C lydian dominant, C dominant bebop, C blues, C major pentatonic C mixolydian, C suspended pentatonic, F major pentatonic
C7sus, Csus, C11, Bb/C, Gm7/C C7#11, C7
C lydian dominant
C7alt, C7#9#5, C7#9
C altered, F harmonic minor, F melodic minor
C7b9b5, C7b9
C HW diminished, F harmonic minor, F melodic minor
C7aug, C7+, C7#5
C whole tone
Cm7b5
C locrian #2, C locrian
Cdim7
C WH diminished
Cphryg
C phrygian, C phrygian #6, C Spanish phrygian, C in sen
Cmaj7#5
C lydian augmented, C major bebop
C7susb9
C phrygian #6, C phrygian
III-5
Bagi para musisi jazz, hubungan antara tangga nada dan akor yang ditunjukkan pada tabel diatas merupakan standar pengetahuan yang harus dipahami dan dikuasai. Namun demikian, hubungan tersebut tidak bersifat kaku. Pengetahuan mengenai hubungan antara tangga nada dan akor dapat dianalogikan sebagai grammar(tata bahasa). Sedangkan, kegiatan berimprovisasi dapat dianalogikan sebagai komunikasi. Untuk dapat berkomunikasi dengan baik diperlukan penguasaan tata bahasa yang baik pula. Sebuah aturan pada suatu tata bahasa dapat memungkinkan komunikan untuk membentuk berbagai macam kalimat. Begitu pula halnya dengan pengetahuan hubungan tangga nada dan akor. Satu tangga nada dapat memungkinkan musisi jazz membentuk berbagai kombinasi melodi yang sesuai dengan akor masukan.
3.2 Analisis Metode atau Aplikasi yang Berkaitan dengan Pembangunan Pola Improvisasi Musik Jazz Berikut ini analis terhadap metode atau aplikasi yang sudah dijelaskan pada subbab 2.3 Metode Pendekatan dan Aplikasi yang Berkatian dengan Pembangunan Pola Improvisasi Musik Jazz : 1. Model kreatifitas permainan jazz The Reasoner merupakan sebuah model ideal dalam mengaplikasikan sebuah mesin berlaku layaknya seperti musisi jazz sungguhan. Model ini layaknya model OSI Layer pada dunia jaringan yang sangat sulit untuk diimplementasikan. Hampir semua aspek improvisasi musik jazz tercakup dalam model ini. Namun demikian, model ini belum mencakup hal yang berkaitan dengan konsep pembelajaran yang dilakukan oleh mesin yaitu bagaimana sebuah mesin improvisasi jazz dapat bertambah kemampuannya jika diberikan pengalaman tertentu. 2. Aplikasi Band-In-A-Box dan pendekatan rule-based merupakan sistem bermain jazz yang memiliki pengetahuan statik. Selama aturan main belum diubah oleh programmer manusia, maka sistem ini tidak bertambah kemampuannya. Jadi, kedua aplikasi ini hanya cocok sebagai asisten dari musisi jazz untuk membantu kegiatan menggubah lagu jazz, bukan sebagai sistem bermain jazz yang berdiri sendiri. 3. Pendekatan genetic-based sudah mengaplikasikan konsep pembelajaran mesin karena menggunakan algoritma genetika dalam pembentukan pola improvisasi
III-6
melodinya. Namun demikian, sistem ini membutuhkan seorang mentor manusia yang membimbing sistem untuk meningkatkan kemampuannya dengan cara memberitahu apakah pola yang dibentuk sistem memiliki kualitas improvisasi yang baik atau buruk. Oleh karena itu, dapat dikatakan bahwa pendekatan genetic-based ini dari sudut pembelajaran mesin masih bersifat semi-learner.
Dari hasil analisis mengenai metode atau aplikasi sistem bermain jazz yang telah disebutkan, maka pada penelitian kali ini akan dirancang sebuah sistem yang benarbenar mengaplikasikan konsep pembelajaran mesin secara penuh. Sistem ini bersifat independen seperti layaknya seorang musisi jazz yang terus belajar untuk meningkatkan pengetahuannya. Pengetahuan dari sistem ini akan bersifat dinamis sesuai dengan pengalaman pembelajaran yang dialaminya.
3.3 Definisi
Formal
Permasalahan
Pembelajaran
Pola
Improvisasi Musik Jazz Tujuan utama dari sistem pembelajaran pola improvisasi musik jazz ini adalah mempelajari berbagai pola improvisasi melodi sehingga mampu membentuk pola improvisasi yang lebih baik. Sebelum dapat melakukan analisis dan perancangan sistem pembelajaran pola improvisasi, diperlukan spesifikasi yang jelas terhadap permasalahan pembelajaran, yaitu 1. bagaimana rincian mekanisme pembelajaran yang dilakukan, 2. kegiatan pembentukan pola improvisasi yang seperti apakah yang dilakukan, 3. tolok ukur apakah yang digunakan sehingga sistem dapat dikatakan telah membentuk pola improvisasi yang “lebih baik”.
Mengacu kepada definisi masalah pembelajaran oleh Tom Mitchel [MIT97], sebuah permasalahan pembelajaran pola improvisasi musik jazz dapat didefinisikan sebagai tuple yang memiliki 3 buah atribut pembelajaran yaitu kelas aktifitas (class of tasks),
, ,
dimana
merupakan
merupakan ukuran kinerja (performance measure), dan
merupakan pengalaman pelatihan (training experience). Sistem pembelajaran pola improvisasi dapat dikatakan “belajar” dari pengalaman
jika kinerja dari aktifitas
III-7
yang diukur oleh
meningkat sesuai
yang dialami. Deskripsi rinci dari masing-
masing atribut tersebut adalah sebagai berikut. •
: membentuk pola improvisasi melodi musik jazz secara horizontal (unisono) berdasarkan akor masukan dan melodi lagu asli.
•
: tingkat kesetaraan pembentukan pola melodi dengan permainan improvisasi dari musik jazz asli.
•
: pembelajaran terhadap berbagai contoh berkas musik jazz asli.
3.3.1 Kelas Aktifitas (T ) Aktifitas pembentukan pola melodi improvisasi yang dilakukan hanya sebatas pembentukan pola melodi secara horizontal (unisono). Sedangkan, pembentukan pola melodi secara vertikal (harmoni) tidak dilakukan pada penelitian ini. Secara heuristik, pembentukan pola melodi secara horizontal lebih mudah dilakukan dibandingkan dengan secara vertikal atau kedua-duanya. Selain itu, teknik pembentukan pola melodi secara horizontal cenderung lebih sering digunakan oleh para musisi jazz dan dapat mencakup ke semua jenis alat musik bernada. Hanya alat-alat musik bernada tertentu saja yang dapat memainkan pola melodi secara vertikal, seperti pada piano/keyboard, gitar, beberapa alat musik gesek, dan sebagainya.
3.3.2 Ukuran Kinerja (P) Dikarenakan permasalahan pembelajaran pola improvisasi musik jazz termasuk bentuk permasalahan kreatifitas, pengukuran kinerja merupakan hal yang paling sulit untuk ditentukan secara eksplisit. Walaupun terdapat berbagai panduan yang digunakan dalam menentukan pembentukan pola melodi yang baik (lihat subbab 3.1), namun secara garis besar tidak terdapat suatu ukuran global yang menentukan apakah suatu pola improvisasi yang dibentuk benar atau salah. Keputusan penentuan pembentukan pola melodi yang dilakukan oleh seorang musisi jazz ditentukan oleh selera pribadi dan pendengar.
Oleh karena itu, pendekatan ukuran kinerja
yang dirumuskan untuk permasalahan
pembelajaran improvisasi jazz ini hanya sebatas seberapa mirip pola yang dihasilkan dengan pola improvisasi dari lagu jazz yang asli. Dengan demikian, kinerja dari sistem
III-8
pembelajaran akan bergantung pada kualitas data pelatihan yang dimiliki. Jika data pelatihannya berasal dari lagu-lagu jazz yang dianggap baik, maka sistem akan mampu menghasilkan pola improvisasi yang dianggap baik pula, dan sebaliknya. 3.3.3 Pengalaman Pembelajaran (E) Selama proses pembelajaran, sistem akan mendapatkan pengalaman pembelajaran dengan melakukan pembacaan terhadap berkas lagu-lagu berimprovisasi. Berkas data lagu pembelajaran harus memiliki atribut-atribut yang menentukan pembentukan pola improvisasi melodi yang dikaji pada penelitian ini, yaitu melodi asli, akor masukan beserta melodi improvisasinya.
3.4 Perancangan Sistem Pembelajaran Pola Improvisasi 3.4.1 Deskripsi Umum Sistem Pembelajaran Musik sebagai input utama dari sistem pembelajaran pola improvisasi musik Jazz harus direpresentasikan menjadi masukan yang dapat dibaca oleh algoritma pembelajaran mesin, sehingga musik masukan dapat diproses untuk mempelajari pola improvisasi. Karena tipe improvisasi yang akan dilakukan pembelajaran adalah tipe improvisasi berdasarkan akor masukan dan melodi asal, maka elemen musik yang direpresentasikan pada algoritma pembelajaran mesin adalah frasa melodi per akor.
Sebuah musik dapat dipandang sebagai susunan frasa melodi dan akor dimana 1
terhingga yang terdiri dari
. Sebuah frasa terdiri dari melodi yang dimulai dari
masuknya suatu akor dan berakhir sesaat sebelum akor berikutnya. Bentuk melodi pada suatu frasa yang diterima hanya berbentuk unisono. Melodi yang berbentuk harmoni (susunan melodi secara vertikal atau melodi-melodi yang dimainkan secara bersamaan pada suatu waktu) tidak termasuk kajian pada penelitian ini. Sebelum dibaca oleh alogritma pembelajaran mesin, perseptor musik (lihat gambar III-5) akan memilahmilah berkas musik masukan menjadi frasa-frasa per akor.
Terdapat 2 jenis frasa melodi per akor yang akan menjadi masukan yaitu frasa melodi asli dan frasa melodi improvisasi. Frasa melodi asli berasal dari musik asli dan frasa melodi improvisasi berasal dari musik yang telah terimprovisasi. Karena panjang lagu
III-9
atau durasi lagu dan progresi akor dari musik improvisasi sama dengan musik asli, maka setiap frasa melodi asli berkorespondensi dengan frasa melodi terimprovisasi.
Gambar III-3 Representasi Frasa Melodi Asli per Akor
Gambar III-4 Representasi Frasa Melodi Improvisasi per Akor
Pada Gambar III-3 dan Gambar III-4, frasa 1 pada representasi melodi asli maupun melodi improvisasi memiliki akor dan durasi yang sama namun dengan melodi yang berbeda. Begitu juga dengan frasa 2, 3, 4, dan 5. Selain itu, dapat dilihat bahwa pola melodi improvisasi yang dihasilkan tidak bersifat acak, melainkan berdasarkan akor masukan serta karakteristik melodi asli. Untuk progresi akor yang sama namun melodi asli yang berbeda, dapat dihasilkan pola improvisasi yang berbeda pula.
Untuk mengaplikasikan sistem pembelajaran mesin pada permasalahan pembelajaran pola improvisasi, terdapat beberapa hal yang harus didefinisikan, yaitu 1. Masukan Masukan utama dari sistem pembelajaran pola improvisasi adalah musik tanpa improvisasi yang akan diimprovisasi yang berperan sebagai instance. Selain itu, masukan lain yang dibutuhkan adalah berkas musik asli beserta improvisasinya yang berfungsi sebagai data pelatihan. Kemudian, masukan berupa berkas musik
III-10
akan diolah sedemikian rupa sehingga dapat menjadi masukan yang dapat diterima oleh algoritma pembelajaran mesin. Masukan musik didapatkan dari berkas MusicXML. 2. Keluaran Keluaran yang akan dihasilkan oleh sistem pembelajaran pola improvisasi ini adalah musik improvisasi yang dilakukan oleh mesin pembelajar. Musik keluaran yang dihasilkan juga berupa berkas MusicXML. 3. Proses Pemrosesan pembelajaran terhadap musik data pelatihan dilakukan dengan menggunakan beberapa algoritma pembelajaran mesin. Hasil pembelajaran yang didapatkan akan digunakan sebagai dasar untuk membentuk pola improvisasi baru yang dilakukan terhadap musik tanpa improvisasi.
Sistem pembelajaran pola improvisasi yang akan dibangun diadopsi dari model The Reasoner yang dijelaskan pada subbab 2.2. Secara umum, terdapat 2 fase penggunaan algoritma pembelajaran mesin, yaitu fase pembelajaran dan fase pembentukan pola melodi. Pada fase pembelajaran akan dilakukan pembelajaran dari data latihan. Setelah fase pembelajaran selesai dilakukan, sistem pembelajaran siap untuk melakukan fase pembentukan pola melodi. Fase pembentukan pola melodi tidak dapat dilakukan tanpa adanya fase pembelajaran. 3.4.2 Fase Pembelajaran Pada fase pembelajaran ini, tipe pembelajaran akan dilakukan dengan supervised learning dengan mempersiapkan data latihan yang akan digunakan sebagai bahan pembelajaran. Data-data pelatihan yang digunakan berupa tupel-tupel data yang terdiri dari: 1. Musik Asli Musik asli atau musik yang terdiri dari melodi dan akor asal lagu tanpa improvisasi. 2. Musik Improvisasi Musik yang telah terimprovisasi yang panjang/durasinya dan progresi akornya sama dengan musik asal.
Proses pembentukan pola melodi dilakukan seperti pada Gambar III-5.
III-11
Gambar III-5 Fase Pembelajaran
Untuk dapat menggunakan data pelatihan agar mampu dipakai untuk melakukan pelatihan terhadap algoritma pembelajaran mesin, data pelatihan yang berformat MusicXML tersebut diolah terlebih dahulu oleh perseptor untuk menghasilkan format yang sesuai dengan masukan algoritma pembelajaran mesin yang digunakan. Dengan demikian, mekanisme konversi data yang dilakukan oleh perseptor akan berbeda-beda bergantung pada karakteristik algoritma pembelajaran mesin yang digunakan. Masukan musik untuk algoritma pembelajaran mesin adalah per durasi akor. 3.4.3 Fase Pembentukan Pola Melodi Pada fase pembentukan pola melodi, algoritma pembelajaran mesin juga tidak dapat berdiri sendiri. Musik asal yang akan diimprovisasi akan diubah dahulu menjadi format yang dapat diterima oleh algoritma pembelajaran mesin. Proses pembentukan pola melodi dilakukan seperti pada Gambar III-6.
Gambar III-6 Fase Pembentukan Pola Melodi
III-12
Algoritma pembelajaran mesin yang berfungsi sebagai pembentuk pola melodi improvisasi memerlukan masukan berupa musik asal berbentuk MusicXML. Seperti pada proses pembelajaran, musik asal akan diproses oleh perseptor sehingga menghasilkan deretan masukan bagi algoritma pembelajaran mesin per durasi akor.
Deretan masukan tersebut akan digunakan oleh algoritma pembelajaran mesin yang sudah terlatih untuk membentuk deretan keluaran berupa pola improvisasi per durasi akor. Kemudian, eksekutor akan menyusun kembali keluaran yang didapatkan dari hasil pemrosesan algoritma pembelajaran mesin sehingga durasi musik dan progresi akornya sama dengan musik asal, lalu mengubah keluaran tersebut menjadi format MusicXML. 3.4.4 Perseptor dan Eksekutor Perseptor adalah bagian dari sistem pembelajaran pola improvisasi yang bertugas untuk melakukan konversi representasi dari format masukan berupa MusicXML menjadi format yang dapat diolah oleh algoritma pembelajaran mesin. Sedangkan, eksekutor adalah bagian dari sistem pembelajaran pola improvisasi yang bertugas untuk melakukan konversi hasil proses algoritma pembelajaran mesin menjadi format yang dapat dipahami oleh manusia (MusicXML).
3.5 Analisis Penggunaan Algoritma Pembelajaran Mesin Mengetahui
karakteristik
non-deterministik
yang
dimiliki
oleh
permasalahan
pembelajaran pola improvisasi musik jazz (lihat subbab 2.2), fungsi target global dari permasalahan pembelajaran ini menjadi sulit untuk ditentukan secara eksplisit. Selain itu, pada dasarnya karakteristik pembelajaran awal yang dilakukan oleh musisi Jazz adalah dengan cara mengingat pola improvisasi sebanyak-banyaknya (memorizing). Oleh karena itu, jenis metode pembelajaran mesin yang paling sesuai menurut penulis secara heuristik untuk menyelesaikan permasalahan pembelajaran ini adalah InstanceBased Learning.
Instance-Based Learning merupakan metode pembelajaran yang fungsi targetnya tidak ditentukan diawal, melainkan melakukan penggeneralisasian tujuan setelah menerima instance permasalahan. Metodi ini hanya menyimpan data-data pelatihan dan menunda penggeneralisasian hingga sebuah instance akan diklasifikasikan. Setiap kali sebuah
III-13
instance ditemukan, sistem akan mengecek keterhubungan instance tersebut dengan data-data pelatihan yang ada untuk menentukan fungsi target. Dengan demikian, metode Instance-Based Learning memungkinkan sistem pembelajaran untuk mengestimasi berbagai fungsi target lokal dan berbeda untuk setiap instance yang ditemukan sehingga sesuai untuk menyelesaikan permasalahan unsur kreatifitas yang terdapat pada musik Jazz.
Salah satu kekurangan dari pendekatan instance-based adalah kompleksitas alogritma untuk mengklasifikasikan berbagai instance baru dapat menjadi tinggi. Hal ini disebabkan
karena
proses
komputasi
yang
intensif
dilakukan
pada
saat
pengklasifikasian instance, tidak seperti halnya pendekatan lainnya yang melakukan komputasi intensif pada saat fase pembelajaran.
Pada penelitian ini, algoritma pembelajaran mesin berbasis instance-based yang dipilih adalah algoritma k-Nearest Neighbor (kNN).
3.6 Analisis k-Nearest Neighbor (kNN) 3.6.1 Gambaran Umum Algoritma k-Nearest Neighbor (kNN) Algoritma k-Nearest Neighbor (kNN) merupakan algoritma berbasis instance-based yang paling sederhana. Pada algoritma ini, semua instance diasumsikan sebagai titik pada koordinat kartesius berdimensi n. Tetangga terdekat didefinisikan dengan persamaan jarak Euclidean.
Untuk lebih jelasnya, dapat misalkan sebuah instance sebarang dengan vektor
,
,…,
dimana
ke- dari instance . Jarak antara 2 buah instance
yang dideskripsikan
menunjukkan nilai dari atribut dan
didefinisikan oleh
,
dimana ,
∑
……………..……........................... (3.1)
Selain itu, pada algoritma k-Nearest Neighbor setiap instance memiliki fungsi target yang berbeda dan nilainya dapat berupa nilai diskrit atau nilai riil. Untuk nilai diskrit,
III-14
fungsi target dapat didefiniskan sebagai : terbatas
1, … ,
dimana
merupakan himpunan
. Untuk mengaproksimasi nilai fungsi target
dimana
merupakan sebuah instance baru, dapat digunakan persamaan : ∑
dimana
,
,
1 jika
…………………………… (3.2) ,
dan
0 jika
Seperti yang ditunjukkan pada persamaan 3.2, nilai dari
hanya merupakan nilai
yang paling sering muncul diantara -buah contoh pelatihan yang paling dekat dengan 1, maka algoritma 1-Nearset Neighbor akan mengisi nilai
. Jika kita memilih dengan
dimana
merupakan instance pelatihan yang paling dekat dengan
.
Algoritma k-Nearest Neighbor memiliki 2 fase, yaitu fase pembelajaran dan fase klasifikasi. Berikut ini algoritma pelatihan dan pengklasifikasian yang dilakukan. K-NEAREST NEIGHBOR Algoritma Pelatihan •
,
Untuk setiap contoh pelatihan
, tambahkan instance tersebut ke daftar
training_examples. Algoritma Klasifikasi •
Diberikan sebuah query instance ,
- Hitung
yang akan diklasifikasi, lalu
dimana
merupakan seluruh instance dari
training_example - Urutkan hasil - Ambil
,
buah nilai
dari yang terkecil hingga terbesar ,
yang dipilih merupakan
terkecil, yang menunjukkan bahwa tetangga terdekat dari
- Hitung nilai fungsi target Gambar III-7 Algoritma k-Nearest Neighbor [MIT97]
…
III-15
Gambar III-8 Diagram Pengklasifikasian Instance pada k-Nearest Neighbor [MIT97]
Gambar III-8 mengilustrasikan operasi dari algoritma k-Nearest Neighbor untuk kasus dimana instance direpresentasikan dengan titik-titik pada ruang 2 dimensi dan target fungsi berupa nilai boolean. Contoh-contoh pelatihan positif dan negatif ditunjukkan dengan simbol “+” dan “-“. Dapat dilihat pada gambar sebelah kiri, jika nilai dipilih adalah 1, maka nilai
yang
akan diklasifikasikan sebagai contoh positif. Sedangkan, jika
yang dipilih adalah 5, maka
akan diklasifikasikan sebagai contoh negatif.
Dari karakteristik perhitungan nilai fungsi
, dapat dilihat bahwa algoritma k-
Nearest Neighbor tidak pernah membentuk sebuah fungsi target global secara eksplisit. Nilai
didapatkan berdasarkan nilai-nilai fungsi target tetangga terdekat dan
dihitung jika ditemukan instance baru
. Namun demikian, kita tetap dapat
merumuskan fungsi target global secara implisit atau klasifikasi apa saja yang akan muncul jika kita tetap mempertahankan data contoh pelatihan yang konstan dan melakukan query terhadap algoritma dengan setiap instance yang mungkin pada
.
Pada sisi sebelah kanan gambar III-8 menunjukkan bentuk permukaan keputusan yang diinduksi oleh algoritma 1-Nearest Neighbor terhadap keseluruhan ruang instance. Permukaan keputusan merupakan kombinasi dari convex polyhedra yang melingkupi setiap data contoh pelatihan. Untuk setiap data contoh pelatihan, sebuah polyhedron menunjukkan kumpulan titik query yang pengklasifikasiannya sepenuhnya ditentukan oleh data contoh pelatihan tersebut. Sedangkan, kumpulan titik query yang berada diluar polyhedron tersebut diklasifikasikan oleh data contoh pelatihan lainnya. Bentuk diagram seperti ini disebut sebagai Voronoi diagram dari kumpulan data contoh pelatihan.
III-16
3.6.2 Representasi Masukan Masalah Pembelajaran Pola Improvisasi dengan Menggunakan k-Nearest Neighbor Terkait dengan penggunaan algoritma k-Nearest Neighbor pada permasalahan pola improvisasi musik jazz, berdasarkan analisis teknik improvisasi yang dikaji pada subbab 3.2, sebuah instance
memiliki dua buah atribut
,
serta fungsi target
dimana: 1. atribut
merepresentasikan akor masukan dari instance .
2. atribut
merepresentasikan frasa ,
3. fungsi target
merepresentasikan frasa melodi improvisasi yang digunakan
oleh instance .
Pada keadaan nyata, kombinasi dari akor dan frasa melodi asli maupun improvisasi yang terbentuk berjumlah tidak terbatas. Selain itu, sebuah lagu memiliki nada dasar (root) yang dapat dimainkan dengan 12 cara, sesuai dengan jumlah nada yang terdapat pada 1 oktaf. Untuk mereduksi jumlah kombinasi akor dan frasa melodi serta mengefisienkan proses pembelajaran, maka nada-nada yang menyusun akor atau frasa melodi dinyatakan secara relatif terhadap nada dasar, seperti yang ditulis pada partitur not angka. Sebagai ilustrasi representasi dari nada relatif, misalkan terdapat sebuah lagu yang memiliki nada dasar C. Maka, nada C direpresentasikan sebagai I (‘do’), nada D direpresentasikan dengan II (‘re’), nada F# direpresentasikan dengan IV# (‘fi’), dan seterusnya. Jika nada dasar lagu tersebut diubah menjadi F, maka representasi dari nada-nada yang menyusun lagu tersebut akan berubah. Nada C tidak lagi direpresentasikan sebagai I, tetapi sebagai V. Sedangkan, yang menjadi nada I adalah nada F, sesuai dengan nada dasarnya, seperti yang diilustrasikan pada Gambar III-9 dan Gambar III-10.
Gambar III-9 Hubungan Not Absolut dan Relatif pada Nada Dasar C
III-17
Gambar III-10 Hubungan Not Absolut dan Relatif pada Nada Dasar F
Dengan merepresentasikan nada menjadi not relatif, maka proses pengklasifikasian akan menjadi lebih efisien untuk dilakukan. Misalkan sistem pembelajaran menerima instance contoh pelatihan yang didapatkan dari berkas lagu “Fly Me To The Moon” yang dimainkan pada nada dasar C. Representasi nada sebagai not relatif memungkinkan sistem dapat membentuk pola improvisasi di semua nada dasar. Sistem tidak perlu menunggu ketersediaan instance pelatihan lagu “Fly Me To The Moon” pada nada dasar F untuk dapat membentuk pola improvisasi di nada dasar F. Hal ini tidak dapat dilakukan apabila nada direpresentasikan dengan not absolut. Untuk itu, sebelum instance masuk ke daftar contoh pelatihan, perlu dilakukan transposisi terlebih dahulu dari not absolut ke not relatif terhadap nada dasarnya.
Selain itu, representasi not relatif juga akan mereduksi jumlah atribut sebanyak 12 kali lebih sedikit dibandingkan dengan representasi not absolut, karena sistem pembelajaran tidak perlu mempertimbangkan 12 kemungkinan nada dasar yang dapat dimainkan terhadap sebuah lagu. Bagi sistem pembelajaran, nada dasar yang dimiliki hanyalah 1 buah. 3.6.3 Representasi Akor Masukan Representasi akor masukan yang dipilih adalah berupa himpunan yang berisi domain berupa informasi numerik dari interval nada-nada penyusun akor terhadap nada I (“do”). Hal ini akan memudahkan dalam mengidentifikasi jenis akor. Informasi interval yang dipilih adalah interval semitone (setengah nada). Interval 1 pada suatu nada n menunjukkan bahwa nada tersebut berjarak 1/2 di atas nada dasar.
Sebuah himpunan akor
dapat didefinisikan sebagai berikut. ,
,…,
,
,
3
III-18
Sebuah akor memiliki jumlah elemen paling sedikit sebanyak 3 buah. Elemen ,
,…,
merepresentasikan bilangan interval yang terurut menaik. Cakupan nilai
(domain) dari bilangan tersebut antara 0 – 11 (1 oktaf). Sebagai ilustrasi, misalnya akor I major direpresentasikan dengan 0,4,7 , akor I# major direpresentasikan dengan 1,5,8 , akor II major direpresentasikan dengan 2,6,9 , akor I minor direpresentasikan dengan 0,3,7 , akor I major 7 direpresentasikan dengan 0,4,7,11 , dan seterusnya. 3.6.4 Representasi Frasa Melodi Representasi frasa melodi yang dipilih adalah berupa himpunan yang berisi informasi pitch not-not relatif dari melodi dan tanda istirahat dengan aturan sebagai berikut. 1. Terdapat not-not relatif yang memiliki cakupan nilai pitch antara 1 - 96 (8 oktaf). Jika nada dasar yang diberikan adalah nada C, maka not 1 merepresentasikan nada “do” pada oktaf pertama, not 2 merepresentasikan nada “di” atau ”do#” pada oktaf pertama, not 3 merepresentasikan nada “re” pada oktaf pertama, not 13 merepresentasikan nada “do” pada oktaf kedua, dan seterusnya. 2. Tanda istirahat dinyatakan dengan angka 0. 3. Sebuah himpunan frasa melodi anggota-anggotanya terurut berdasarkan waktu dimainkannya not-not dan tanda istirahat. 4. Informasi musik lainnya seperti durasi not, tanda legato, pola ritmis, artikulasi, ekspresi, dan sebagainya, tidak diperhitungkan.
Sebuah himpunan frasa melodi
didefinisikan sebagai berikut. ,
,…,
,
1
Sebuah frasa melodi memiliki elemen paling sedikit sebanyak 1 buah. Elemen ,
,…,
merepresentasikan bilangan pitch nada yang mencakup bilangan 0 … 96
(8 oktaf nada ditambah bilangan 0 sebagai tanda istirahat) yang terurut berdasarkan waktu dimainkannya nada. Pemilihan cakupan pitch nada mengacu kepada cakupan oktaf pada piano yang sudah mencakup oktaf yang dimiliki oleh seluruh alat musik
III-19
diatonis yang ada saat ini. Gambar III-11 menunjukkan cakupan pitch nada dari oktaf ke-3 hingga oktaf ke-6 pada nada dasar C.
Gambar III-11 Cakupan Not dari Oktaf ke-3 hingga ke-6
Gambar III-12 menunjukkan sebuah frasa musik per akor masukan dari sebuah lagu beserta representasi frasa melodi dan akornya pada nada dasar C. Dapat dilihat pada gambar tersebut bahwa tidak semua not pada frasa musik memiliki durasi yang sama. Mengacu kepada aturan frasa melodi yang telah ditentukan, informasi mengenai durasi not serta pola ritmis (tanda triol) tidak diperhitungkan. Frasa melodi hanya menyimpan informasi pitch dari melodi yang diberikan.
Gambar III-12 Representasi Frasa Melodi dan Akor dari Sebuah Frasa Musik
3.6.5 Hubungan Ketetanggaan antara Frasa Melodi dan Akor Agar instance permasalahan pembelajaran pola improvisasi dapat diasumsikan dengan titik pada ruang Euclidean sehingga jaraknya dapat dihitung, maka perlu untuk mendefinisikan dengan jelas hubungan ketetanggaan antara atribut-atribut yang dimiliki oleh dua buah instance, yaitu frasa melodi dan akor masukan. ,
Diberikan 2 buah himpunan frasa melodi yaitu ,
,…,
berikut.
. Hubungan ketetanggaan antara
dan
,…,
dan
dapat didefinisikan sebagai
III-20
1. Identik dan
dapat dikatakan identik jika
dan
,
,…,
. 2. Serupa dan
dapat dikatakan serupa jika
- minimal terdapat 3/4 dari anggota pitch nada
yang sama dengan
,
untuk - frasa
identik dengan subfrasa dari
, untuk
3. Setipe dan
dapat dikatakan setipe jika
- Frasa
memiliki anggota pitch nada berbeda dengan frasa
namun
memiliki interval yang searah. 4. Jauh dan
dapat dikatakan jauh jika tidak memenuhi hubungan ketetanggaan
identik, serupa, dan setipe.
Gambar III-13 Hubungan Ketetanggaan Identik
Gambar III-14 Hubungan Ketetanggaan Serupa
III-21
Gambar III-15 Hubungan Ketetanggaan Setipe
Gambar III-16 Hubungan Ketetanggaan Jauh
Agar hubungan ketetanggaan tersebut dapat dimengerti oleh algoritma k-Nearest Neighbor,
dibuatlah
sebuah
pendekatan
menggunakan
fungsi
riil
yang
merepresentasikan hubungan ketetanggaan secara kuantitatif. Fungsi tersebut harus dapat merepresentasikan jarak antar frasa melodi. Semakin kecil nilai keluaran dari fungsi tersebut maka hubungan ketetanggaan antarfrasa melodi semakin dekat, dan sebaliknya.
Hubungan ketetanggaan antarfrasa melodi dapat didefinisikan pada
Gambar III-17. Diberikan ,
2
buah
,…,
himpunan
frasa
,
melodi
,…,
, maka terdapat 2 buah fungsi riil :
,
12
,
1
1
dan min ,
Fungsi
dan
|
,
|
max
| ,
menyatakan jarak antar 2 buah melodi Gambar III-17 Persamaan Jarak antara 2 Melodi
|
III-22
Secara deskriptif, fungsi
merupakan akar kuadrat dari penjumlahan terhadap kuadrat
selisih nilai 2 buah pitch nada dari 2 frasa yang berbeda. Persamaan
dapat
dianalogikan sebagai jarak antara 2 buah frasa atau subfrasa melodi yang berfungsi untuk mencari subfrasa melodi dari
yang paling dekat dengan
. Persamaan ini juga
menegaskan bahwa perbedaan nada antara 2 buah frasa menunjukkan ketetanggaan yang cukup jauh walaupun jalur interval antarfrasa tersebut sama. Hal ini ditunjukkan dengan dengan dikuadratkannya selisih antara 2 buah nada yang menyebabkan meningkatnya nilai
secara kuadratis untuk pertambahan selisih yang linear.
Selanjutnya, dari nilai
,
untuk dipakai pada persamaan subfrasa dari
,
terkecil akan diambil
. Hal ini dirancang untuk memastikan bahwa ada
yang lebih dekat dengan frasa
lainnya, dimana frasa frasa
yang telah didapatkan, nilai
dibandingkan subfrasa-subfrasa
memiliki anggota pitch nada yang lebih banyak dibandingkan
. Mekanisme penghitungan
dikembangkan dari algoritma pencocokan pola
(pattern matching). Perbedaan antara penghitungan
dengan algoritma pencocokan
pola biasa terletak pada saat pemberhentian iterasi. Pada algoritma pencocokan pola biasa, iterasi dihentikan saat ditemukannya subpola yang sama dengan pola masukan, seperti pada metode pencarian frasa kata. Sedangkan, pada metode penghitungan
,
iterasi berhenti hingga akhir operasi penghitungan yang kemudian akan diambil dengan nilai terkecil. Dari sudut pandang kompleksitas algoritma, dapat dikatakan bahwa penghitungan
merupakan kasus terburuk dari algoritma pencocokan pola
ditambah dengan operasi pencarian nilai minimum.
Selain itu, pada fungsi
12 yang menjamin bahwa selisih
juga terdapat atribut
terbesar antara 2 buah pitch nada hanya 1 oktaf. Dengan demikian, jika terdapat sebuah frasa yang selisih semua pitch nadanya berselisih 1 oktaf dari frasa lainnya dan jumlah kedua frasa tersebut sama banyak, maka kedua frasa tersebut dianggap identik.
Fungsi
,
merepresentasikan nilai ketetanggan dari frasa
Semakin kecil nilai yang dihasilkan oleh antara frasa
dengan
,
dengan
.
, maka hubungan ketetanggaan
semakin dekat. Adapun atribut nilai mutlak dari selisih jumlah
III-23
anggota
dan ,
|) yang dimaksudkan untuk membedakan nilai keluaran dari
(|
antara hubungan ketetanggan identik dengan serupa.
Sebagai ilustrasi dari penggunaan operasi
dan
, terdapat frasa identik (Gambar
III-13) yang anggotanya berjumlah 6 buah yang direpresentasikan dengan 68,61,63,65,66,68 jika lagu dimainkan pada nada dasar C. Maka, ,
12
12
12
12 68
68
12
12
61
61
63
63
12 65
65
66
66
68
68
0 Karena 1
6
merupakan nilai
6
1
1, maka hanya terdapat 1 buah
terkecil. Selanjutnya, akan dicari nilai
yaitu
juga
dengan penghitungan
sebagai berikut. | max
,
0 |6 6| max 6,6
| ,
0 6
0
Dengan demikian, 2 buah frasa yang identik akan menghasilkan nilai jarak ,
0.
Pada Gambar III-14 di bagian sebelah kanan, terdapat 2 buah frasa serupa dengan jumlah anggota pitch nada yang berbeda. Frasa-frasa tersebut direpresentasikan sebagai 68,61,63 menghitung 7.071,
68,61,63,65,66,68 . Dengan cara yang sama untuk
dan
pada ilustrasi sebelumnya, maka didapatkan 7.681 . Dari semua
yang didapatkan,
0,
7.550,
menjadi nilai terkecil yaitu
0. Jadi, ,
| max
| ,
0
| 3 6 | max 6,6
3 6
0.5
III-24
Dari kedua ilust\rasi tersebut, dapat dilihat bahwa hubungan ketetanggaan identik menghasilkan nilai
lebih kecil dibandingkan dengan ketetanggaan serupa.
Sementara itu, hubungan ketetanggaan antarakor juga harus didefinisikan secara jelas. Hubungan ketetanggaan antarakor dapat ditentukan dengan cara mengidentifikasi seberapa banyak anggota interval dari suatu himpunan akor yang juga merupakan anggota dari himpunan akor tetangga. Semakin banyak himpunan anggota akor yang beririsan, maka semakin dekat hubungan ketetanggaan antar akor tersebut. Secara formal, penghitungan hubungan ketetanggaan antar 2 buah akor dapat didefinisikan dengan pendekatan operasi himpunan seperti yang ditunjukkan pada Gambar III-18. ,
Diberikan 2 buah himpunan akor anggota-anggota dari
dan
,…,
dan
,
,…,
dimana
sudah terurut dari nilai interval terkecil ke terbesar.
Didefinisikan himpunan : •
dengan
merupakan banyaknya anggota dari
•
dengan
merupakan banyaknya anggota dari
dan fungsi : ,
|
Fungsi
|
|
|
menyatakan jarak antar 2 buah akor Gambar III-18 Representasi Formal dari Akor
Proses penghitungan hubungan ketetanggaan antarakor mengeliminasi anggota-anggota interval yang beririsan dan hanya memperhitungkan anggota interval yang berbeda serta perbedaan jumlah antar 2 buah himpunan akor. Semakin kecil nilai
yang
dihasilkan maka hubungan ketetanggaan antar 2 buah akor tersebut semakin dekat, dan sebaliknya.
Sebagai ilustrasi hubungan ketetanggaan antarakor, diberikan 2 buah akor yang anggota intervalnya sudah terurut yaitu
0,4,7,8 dan
1,5,7,8 . Maka, 0,4 1,5
dan
III-25
,
|
|2
Pembelajaran
dan
|
3.6.6 Proses
2|
|0
1|
|4
5|
Pengklasifikasian
0
2
Frasa
Melodi
Improvisasi Pada dasarnya, penggunaan algoritma k-Nearest Neighbor tidak melakukan proses pembelajaran
secara
khusus.
Proses
pembelajaran
dilakukan
hanya
dengan
mengumpulkan data pelatihan berbentuk frasa musik sebanyak-banyaknya. Sebuah frasa musik data pelatihan terdiri atas atribut akor, frasa melodi asli, dan frasa melodi improvisasi. Secara lojik, data pelatihan akan membentuk hubungan antar atributatributnya seperti pada Gambar III-19.
Gambar III-19 Hubungan Lojik antara Akor, Melodi Asli dan Improvisasi
Pembelajaran terhadap sebuah frasa musik akan mendapatkan informasi sebuah akor. Jika pembelajaran dilakukan secara berulang-ulang terhadap berbagai frasa musik dengan berbagai kombinasi akor, frasa melodi asli maupun improvisasi, maka dapat dihasilkan relasi-relasi lojik sebagai berikut.
III-26
•
Sebuah akor dapat memiliki banyak frasa melodi asli
•
Frasa melodi asli yang sama dapat memiliki akor yang berbeda-beda
•
Akor dan frasa melodi asli yang sama dapat memiliki frasa melodi improvisasi yang berbeda-beda
Proses pengklasifikasian dilakukan apabila ditemukan sebuah instance baru yang akan ditentukan melodi improvisasinya. Melodi improvisasi yang dipilih untuk instance baru tersebut merupakan melodi improvisasi milik tetangga terdekat. Secara umum, dikarenakan pembentukan melodi improvisasi ditentukan oleh 2 buah atribut, yaitu akor dan melodi asli, penentuan tetangga terdekat akan dilakukan melalui 2 tahap penghitungan jarak, yaitu 1. menghitung jarak antar akor instance baru dengan semua instance data pelatihan, 2. menghitung jarak antar frasa melodi asli instance baru dengan semua frasa melodi asli instance data pelatihan dengan akor tertentu.
Penghitungan jarak antar akor digunakan untuk menyeleksi instance data pelatihan sebelum dilakukan penghitungan jarak antar frasa melodi asli sehingga penghitungan jarak antar frasa melodi asli tidak dilakukan terhadap semua instance data pelatihan. Untuk menyederhanakan permasalahan, jarak antar akor dan jarak anta frasa melodi asli dihitung dengan hanya mempertimbangkan 1 buah tetangga (1-Nearest Neighbor).
Jika setelah mendapatkan akor dan frasa melodi asli data pelatihan yang paling dekat ditemukan banyak frasa melodi improvisasi kandidat solusi yang mungkin diberikan untuk instance baru tersebut, maka akan dilakukan tahap pemrosesan tambahan yaitu pemilihan frasa melodi improvisasi yang sesuai untuk instance baru tersebut. Salah satu skenario pemilihan frasa melodi improvisasi yang dapat dilakukan adalah dengan memilih salah satu frasa melodi improvisasi kandidat solusi yang terdekat dengan frasa melodi asli instance baru dengan menghitung nilai hubungan ketetanggaan ( antara kedua frasa tersebut.
)
III-27
Jadi, terdapat 3 tahap penghitungan jarak yang dilakukan pada algoritma klasifikasi, yaitu 1. penghitungan jarak antara akor instance baru dengan akor data pelatihan, 2. penghitungan jarak antara melodi asli instance baru dengan melodi asli data pelatihan, 3. penghitungan jarak antara melodi asli instance baru dengan melodi improvisasi data pelatihan.
Gambar III-20 menunjukkan algoritma klasifikasi yang dirancang untuk penyelesaian masalah pembelajaran pola improvisasi musik jazz. Algoritma Klasifikasi Sistem Pembelajaran Pola Improvisasi •
Didefinisikan : -
,y,w : instance dari sebuah frasa musik, , ,
-
: jumlah instance pada data pelatihan
-
, ,
: himpunan dari instance
: ruang instance (semesta) dari frasa musik
-
: akor dari instance
-
: frasa melodi asli dari instance : frasa melodi improvisasi dari instance
-
: ruang improvisasi kandidat yang beranggotakan himpunan-himpunan frasa melodi improvisasi kandidat solusi
•
:
: fungsi target lokal atau aproksimasi untuk query instance. berupa frasa musik yang terdiri dari melodi asli
Diberikan sebuah query instance
dan akor tanpa melodi improvisasi, maka lakukan langkah-langkah berikut. 1. Didefinisikan 2. 3.
,…,
argmin
,
argmi
4. Didefinisikan 5.
,
argmi
, sehingga ,
,
, sehingga
,
,…,
,
,…,
,…, ,
Gambar III-20 Algoritma Klasifikasi Sistem Pembelajaran Pola Improvisasi
III-28
3.6.7 Analisis Kompleksitas Algoritma Pembelajaran dan Klasifikasi Dengan penggunaan algoritma k-Nearest Neighbor terhadap penyelesaian masalah pembelajaran pola improvisasi, maka kompleksitas terbesar terletak pada proses pengklasifikasian, jauh lebih besar dibandingkan proses pembelajaran. Dengan demikian, kompleksitas proses pembelajaran yang hanya menyimpan data pelatihan dapat diabaikan.
Untuk melakukan analisis terhadap kompleksitas algoritma klasifikasi, didefinisikan variabel-variabel sebagai berikut. •
,
•
,
•
,
,…, ,…, ,…,
• • • •
, :
• •
Mengacu kepada algoritma klasifikasi k-Nearest Neighbor yang telah ditunjukkan pada Gambar III-20, terdapat 3 buah operasi utama yang dilakukan yaitu penghitungan jarak antar akor, jarak antar melodi asli, dan jarak antar melodi improvisasi. Selanjutnya akan dilakukan analisis kompleksitas algoritma terhadap ketiga buah operasi tersebut.
Misalnya diberikan sebuah instance baru
yang akan diklasifikasikan atau dicari
frasa melodi improvisasinya. Pada operasi penghitungan jarak antar 2 buah akor, misalnya antara akor
dan
, tiap-tiap anggota interval dari akor
dibandingkan dengan tiap-tiap anggota interval dari akor
akan
. Dengan demikian, terjadi
operasi perbandingan. Jika operasi penghitungan jarak antar akor ini dilakukan pada semua instance pada data pelatihan, maka akan terjadi .
operasi perbandingan. Jadi,
kompleksitas operasi penghitungan jarak antar akor adalah sebesar
.
.
III-29
Pada operasi penghitungan jarak antar 2 buah frasa melodi asli, frasa melodi asli instance
akan dihitung nilai ketetanggan dengan tiap-tiap frasa melodi asli data
pelatihan dengan akor sejenis (lihat Gambar III-21). Didefnisikan bahwa banyaknya anggota nada dari frasa melodi asli yang lebih sedikit jumlahnya sebagai lebih banyak jumlahnya sebagai
dan yang
. Maka, banyaknya operasi perkalian yang terjadi
pada saat mencari nilai ketetanggaan antar 2 buah frasa melodi asli adalah . 1 . Karena operasi penghitungan jarak antar frasa melodi asli hanya melibatkan frasafrasa melodi asli pada akor yang sejenis, maka akan terjadi operasi perkalian sebanyak . .
1 . Pada kasus terburuk, jumlah instance data pelatihan dengan akor
sejenis sama dengan total jumlah instance data pelatihan keseluruan. Maka, operasi perkalian pada kasus terburuk akan terjadi sebanyak dibulatkan ke atas menjadi .
. .
1
atau dapat
. Dengan demikian, kompleksitas operasi penghitungan
jarak antar frasa melodi asli adalah sebesar
.
.
Gambar III-21 Akor berdasarkan Nada Dasar
Pada operasi penghitungan jarak antara frasa melodi asli dari instance
dengan tiap-
tiap frasa melodi improvisasi kandidat solusi, kompleksitas operasi ini akan analog dengan kompleksitas operasi penghitungan jarak antar 2 buah frasa melodi asli yang sudah dijelaskan sebelumnya. Jika terdapat
buah frasa melodi improvisasi kandidat
solusi, maka kompleksitas operasi ini adalah sebesar
.
.
III-30
Dengan demikian, kompleksitas total dari ketiga proses pencarian ketetanggaan pada adalah :
fase klasifikasi sebuah instance baru .
.
Karena laju pertambahan .
, maka .
dan .
.
.
.
.
.
akan lebih dominan dibandingkan dengan
.
dan
dapat diabaikan sehingga untuk mengklasifikasikan 1 buah
instance baru memiliki kompleksitas algoritma sebesar : .
.
Jika pada sebuah lagu terdapat
.
.
buah frasa yang akan diklasifikasikan, maka
kompleksitas algoritma klasifikasi untuk sebuah lagu adalah sebesar : .
.
. .
Nilai p diperkirakan tidak akan bertambah secara signifikan karena jarang sekali ditemukan kasus adanya frasa yang sangat panjang atau bertambahnya panjang frasa rata-rata terhadap pertambahan jumlah frasa pelatihan. Oleh karena itu, laju pertumbuhan nilai demikian, .
akan relaitf lebih kecil dibandingkan laju pertumbuhan . Dengan
dapat diabaikan sehingga kompleksitas algoritma klasifikasinya menjadi
. Jika diasumsikan bahwa nilai
konstan, maka algoritma klasifikasi k-Nearset
Neighbor untuk membentuk pola improvisasi melodi jazz memiliki kompleksitas algoritma yang linear atau
.
