Algoritma Genetika

1 06 2016

Algoritma Genetika merupakan suatu metode optimasi untuk mencari solusi yang optimal dari suatu permasalahan. Algoritma Genetika banyak digunakan untuk mencari solusi masalah optimasi penjadwalan. Penjadwalan yang umumnya bersifat kompleks tidak mengijinkan sisi otak manusia untuk mencarikan solusi yang optimal dengan mudah. Dengan Algoritma Genetika, hal-hal yang perlu dihindarkan dalam pembuatan jadwal bisa dihilangkan, dan semua bentuk solusi yang menguntungkan pihak-pihak yang terkait akan lebih mudah untuk didapatkan.

Algoritma Genetika mempunyai metodologi optimasi sederhana sebagai berikut:
1. Menentukan populasi solusi sejumlah tertentu
2. Menghitung nilai fitnes function semua solusi yang ada di dalam populasi
3. Memilih beberapa solusi dengan nilai fitnes function yang paling tinggi
4. Melakukan optimasi dengan cara mutasi dan crossover sebanyak yang diperlukan
5. Menentukan solusi terbaik sebagai solusi terhadap permasalahan yang dioptimasi

Dalam menerapkan Algoritma Genetika untuk memecahkan masalah optimasi, perlu dilakukan analisa terhadap permasalahan yang akan dicarikan solusinya. Dalam menganalisa permasalahan, ada dua istilah yang muncul:
1. Hard Constraint: yang merupakan batasan yang ada dalam permasalahan yang akan dicarikan solusi, yang tidak boleh dilanggar sama sekali. Solusi yang akan menjadi bagian dari populasi, adalah solusi yang tidak melanggar Hard Constraint ini.
2. Soft Constraint: yang merupakan batasan yang ada dalam permasalahan yang akan dicarikan solusi, tetapi dalam pencarian solusi, batasan ini masih bisa dilanggar.

Dari kedua istilah tersebut, yang mempengaruhi bagaimana suatu solusi akan dikatakan lebih baik dari solusi yang lain adalah dengan melihat kadar pelanggaran yang dilakukan terhadap Soft Constraint. Makin banyak Soft Constraint yang dilanggar, makin buruk nilai dari solusi tersebut. Nilai dari solusi yang dimaksud di sini sering diistilahkan dengan nama Fitness Function. Fitness Function ini merupakan akumalasi dari nilai penalti yang didapat dari pelanggaran terhadap Soft Constraint yang yang ada.

Selain pelanggaran terhadap Soft Constraint, nilai dari Fitness Function ini juga bisa didapatkan dari penambahan nilai bonus terhadap hal-hal ideal yang bisa dimasukkan dalam pembentukan solusi. Solusi yang bisa memberikan benefit kepada organisasi baik secara perorangan maupun secara keseluruhan organisasi, umumnya bisa dianggap memberikan nilai tambah terhadap solusi yang dibentuk.

Langkah selanjutnya yang dilakukan dalam proses penerapan Algoritma Genetika adalah analisa dan disain sistem. Analisa dan disain sistem terbentuk dari pendefinisian proses-proses yang tercakup dalam sistem, pembentukan basis data, dan juga disain antar muka pengguna. Untuk tulisan ini, analisa dan disain yang dibahas terbatas pada bagaimana membentuk basis data yang diperlukan dalam pemodelan permasalahan optimasi menggunakan Algoritma Genetika.

Umumnya bentuk basis data yang diperlukan dalam penerapan Algoritma Genetika adalah:
1. Tabel Detail Solusi (Gen)
2. Tabel Solusi (Kromosom)
3. Tabel Master yang mendukung isian Tabel Detail Solusi dan Tabel Solusi

Beberapa istilah yang muncul dalam Algoritma Genetika yang juga sering membingungkan pengguna adalah istilah-istilah yang kaitannya dengan Ilmu Biologi seperti istilah Gen dan Kromosom. Dalam pembentukan disain basis data sudah disebutkan bahwa Gen merupakan Detail Solusi, sedangkan Kromosom adalah Solusi. Salah satu contoh penggunaan istilah Gen dan Kromosom dalam memecahkan masalah penjadwalan: bentuk Kromosom (Solusi) dari permasalahan tersebut misalnya adalah Jadwal Mengajar di Sekolah A Selama Seminggu, sedangkan bentuk Gen (Detail Solusi)-nya adalah Guru A Mengajar Matematika di Kelas IA Pada Hari Senin Sesi Pertama. Dimana, sejumlah Gen (Detail Solusi) yang ada akan membentuk suatu Kromosom (Solusi). Jadi istilah ilmiah yang ada merupakan representasi dari permasalahan yang diangkat untuk dicarikan solusinya.

Isian dari Tabel Master yang mendukung pengembangan sistem Algoritma Genetika ini sangat tergantung pada hal-hal yang muncul pada saat melakukan analisa permasalahan. Beberapa hal yang muncul pada Hard Constraint, Soft Constraint, serta Nilai Bonus terhadap solusi akan menjadi bagian dalam pembentukan informasi yang tertampung di dalam Tabel Master yang diperlukan dalam penerapan Algoritma Genetika. Dari contoh bentuk Gen (Detail Solusi) yang diberikan di atas (Guru A Mengajar Matematika di Kelas IA Pada Hari Senin Sesi Pertama), Tabel Master yang diperlukan dalam sistem termasuk Tabel Master Guru, Tabel Master Mata Pelajaran, Tabel Master Kelas, dan Tabel Master Waktu Mengajar.

Dari tulisan di atas, hal-hal utama yang diperlukan untuk menerapkan Algoritma Genetika dalam permasalahan optimasi sudah diberikan. Beberapa hal yang juga sering dibahas dalam penjelasan Algoritma Genetika adalah metode-metode yang digunakan untuk melakukan Mutasi dan Crossover, yang tentunya perlu dipelajari tersendiri, walaupun untuk tingkat pemula, mungkin cukup menggunakan metode sederhana misalnya metode random.

Demikian sedikit tulisan tentang penerapan Algoritma Genetika dalam mencari solusi yang paling optimal dari suatu permasalahan optimasi. Semoga bermanfaat.

Advertisements




Data Warehousing

3 09 2014

Data Warehousing adalah sebuah sistem yang mempunyai tujuan untuk mempermudah pengguna mendapatkan data summary terhadap aktivitas entitas yang terkait dengan suatu perusahaan. Data Warehousing merupakan suatu konsep yang muncul karena sulitnya para manajer mendapatkan data yang diperlukan dalam proses pengambilan keputusan, kalau dengan hanya bermodalkan pada konsep sistem informasi atau sistem pemrosesan transaksi. Dengan penerapan Data Warehousing, data yang umumnya bisa ditampilkan dengan memakan waktu yang panjang, dapat ditampilkan dalam hitungan detik dalam bentuk tabel dan grafik dalam berbagai kombinasi.

Data Warehouse Concept

Data Warehousing merupakan konsep OLAP (OnLine Analytical Processing) yang melakukan pemrosesan data secara online. Penamaan ini sebenarnya agak menyimpang, karena sebenarnya data yang ditampilkan menggunakan konsep data warehouse ini tidak diakses secara langsung (online) ke record datanya, tetapi data/informasi yang diinginkan dipersiapkan terlebih dulu (atau dalam istilah Data Warehouse, di-ETL (Extraction Transformation Loading) terlebih dulu) dari record data transaksi yang tersedia. Proses ETL ini merupakan kunci dari konsep Data Warehouse ini, karena data yang ada dalam jumlah besar bisa diformat sesuai dengan keinginan para manajer, sebelum mereka benar-benar menggunakannya untuk analisa. Dengan konsep itu, data yang diinginkan oleh manajer melalui data warehouse dapat diakses dengan cepat, layaknya kita melakukan penganalisaan secara online.

Data Warehousing memperkenalkan konsep tabel Fakta dan tabel Dimensi, yang sedikit berbeda dengan konsep database secara umumnya, walaupun bentuk penyimpanan data dalam data warehouse merupakan bentuk database juga.

  • Tabel Fakta menyimpan berbagai fakta informasi yang ingin ditampilkan nantinya dalam bentuk tabel ataupun grafik. Contoh isi dari tabel fakta, misalnya dalam data warehouse retail adalah: jumlah barang terjual, jumlah omset, jumlah pajak yang dibayarkan dll.
  • Tabel Dimensi mempunyai struktur yang benar-benar berbeda dengan tabel fakta, dimana tabel dimensi ini terisi dengan data-data terkait dimensi informasi fakta yang ingin ditampilkan. Contoh isi dari tabel dimensi misalnya: tahun, bulan, tanggal, lokasi toko, kategori barang (Makanan atau Non Makanan) dll.

Sehingga kalau kedua tabel tersebut dikombinasikan, data warehouse retail ini akan bisa menjawab permintaan manajer terkait informasi tentang misalnya: trend omset penjualan barang kategori makanan per tahun dari tahun 2000 – 2014 di toko seluruh Denpasar, baik dalam bentuk tabel maupun grafik.

Sebagai kelanjutannya, dalam konsep data warehouse, dalam melakukan penampilan data baik dalam bentuk tabel maupun grafik, dikenal juga istilah roll up and drill down, dan, slice and dice.

  • Roll up and drill down digunakan untuk melihat data lebih rinci atau lebih global. Misalnya, dari dimensi waktu, data omset misalnya bisa dilihat per tahun, atau lebih detail per bulan, atau lebih detail lagi per tanggal. Demikian pula dengan dimensi tempat, data omset bisa dilihat per provinsi, kabupaten/kota, atau per tokonya.
  • Berbeda dengan roll up dan drill down, slice and dice mengenalkan konsep memilah dan memutar. Memilah (slice) artinya, data yang ditampilkan bisa dipilah-pilah. Misalnya kita mempunyai data omset dari tahun 1980 – 2004, tapi yang ditampilkan bisa dipilah, misalnya hanya dari tahun 2000 – 2014. Memutar (dice) artinya, dimensi data yang ditampilkan bisa diputar-putar. Misalnya dari contoh di paragraf sebelumnya, dimana sumbu x-nya adalah lokasi, dan sumbu y-nya adalah waktu, bisa diputar menjadi misalnya: omset penjualan barang kategori makanan di toko seluruh denpasar dari tahun 2000 – 2014, dimana sumbu x-nya adalah waktu, dan sumbu y-nya adalah lokasi.

Dalam pemanfaatannya, sekarang ini banyak yang memperkenalkan sebuah konsep Dashboard Systems. Konsep dashboard system merupakan suatu bentuk penampilan yang lain dari sistem data warehouse. Konsep dalam hal menampilkan informasi fakta yang diinginkan, sesuai dimensi yang disediakan, tetap menjadi konsep dasar dari suatu sistem dashboard system, tetapi tampilannya agar sedikit berbeda dan lebih menyerupai sebuah dashboard mobil. Tampilan ini lebih menarik untuk kasus-kasus pemantauan progress atau kondisi suatu penyelesaian permasalahan.

Dashboard Systems

Sebagai kesimpulan, data warehouse merupakan suatu konsep yang sangat bagus dan merupakan suatu konsep yang dapat menguntungkan pengguna, karena data yang telah tertumpuk dan tidak termanfaatkan bisa digunakan dengan tepat sasaran dan bisa termanfaatkan dengan hasil guna tinggi. Pemanfaatan data warehouse dengan instensif oleh suatu perusahaan akan memberikan suatu kelebihan (competitive advantage) bagi perusahaan tersebut kalau ingin bersaing dengan perusahaan competitornya.

Keywords: Data Warehouse, Extraction Transformation Loading (ETL), Tabel Fakta, Tabel Dimensi, Roll Up and Drill Down, Slice and Dice, Dashboard System





2014 Montpellier Internship

23 08 2014

This year, there are two internships from Polytech of Montpellier, France: Adrien Claudin and Florian Guihard. They are working on a template project for a web system which includes a generic user administration module, a data maintenance module, a data warehouse module, and data mining modules implementing two data mining methods: naive bayes and k-means algorithm. They are staying in Bali for three months (June 2nd – August 28th, 2014).

Today (August 23rd, 2014), they presented their work in front of students and lecturers, in conjunction to a final project presentation by Forth year student group at Stikom Bali’s Dual Degree program. The project went well, despite of new technologies that they have to implement. The user administration module is a generic module to administrate users of the systems. The data warehouse module is also new to them, and they make to the end an analysis of user activity data warehouse systems. For the data mining module, they manage to implement two methods out of three methods I have asked them in the beginning. All applications are implemented using the Java EE with the Model View Controller (MVC) concept as well as Data Access Object (DAO) design pattern. They also implemented the JFreeChart library for graph display and the WEKA library for implementing the naive Bayes data mining method. The whole project is intended to become a system template for students who will be taking web application, data warehouse, and data mining subjects, so they do not have to build a system from scratch for the sake of learning Data Warehouse or Data Mining alone.

This year. the result of the internship is very good, and very useful for the next teaching as well as the next internship program.

Despite of the hard working, the two internships have also enjoyed to stay in Bali. They have played the things that they have planned such as kite surfing and diving. Hope they will have a lot of memories and experiences while staying in Bali both in terms of the Balinese culture and the technology learning.

This is a picture taken at the end of their presentation time. Form the left: Adrien Claudine, Me, Nico Bruhne (Forth Year Stikom Bali’s Dual Degree Program), Florian Guihard, Putu Sri Sasmitha Dewi (Forth Year Stikom Bali’s Dual Degree Program), and Klinton Putra B.B.M. (Forth Year Stikom Bali’s Dual Degree Program).
2004 France Internship





Minimum Message Length

4 07 2014

Melihat dari namanya Minimum Message Length sering dikonotasikan dengan pengiriman data melalui media telekomunikasi, yang kalau diterjemahkan langsung dalam Bahasa Indonesia akan mempunyai arti Panjang Pesan Minimum. Melihat arti langsungnya ini, memang prinsip Minimum Message Length berkaitan erat dengan bagaimana suatu pesan dikirimkan. Akan tetapi, konsep Minimum Message Length ini, sebenarnya tidak mengharuskan kita untuk mengirimkan pesan secara riil, tetapi hanya melakukan perkiraan, apabila kita harus mengirim data melalui media telekomunikasi, akan lebih hemat kalau kita mencari bentuk yang paling minimal dari data yang ingin dikirimkan, sehingga data akan bisa dikirimkan dengan lebih efisien.

Prinsip Minimum Message Length sebenarnya merupakan teori optimasi yang berbasis pada Teori Bayesian dan Teori Informasi. Teori ini banyak digunakan untuk melakukan kegiatan estimasi parameter suatu distribusi statistik dan pemilihan model dalam suatu proses pemodelan. Dalam prinsip Minimum Message Length ini, Teori Bayesian digunakan untuk menentukan suatu estimasi atau model dengan memikirkan, pertama, data yang sedang dianalisa (berupa likelihood function) dan kedua, pengetahuan yang ada tentang nilai estimasi atau nilai pemodelan di masa yang lalu (prior probability). Karena secara umum, Teori Bayesian disimbolkan dengan rumus sebagai berikut:

posterior probability = prior probability x likelihood function

Sedangkan, penggunaan Teori Informasi dalam prinsip Minimum Message Length adalah bahwa data dalam bentuk apapun dapat ditransfer melalui suatu channel informasi dalam bentuk bits (log2). Akan tetapi, informasi yang dikirimkan kalau tidak disederhanakan, akan menjadi proses transfer yang panjang dan memerlukan waktu yang lama. Oleh karena itu, prinsip Minimum Message Length berusaha untuk mencari bentuk pengiriman data dalam bentuk bits (log2) dengan kondisi yang paling pendek, sehingga proses transfer menjadi optimal dan memerlukan waktu yang minimal.

Prinsip Minimum Message Length, dalam context estimasi parameter, sama dengan prinsip Maximum Likelihood dengan tambahan pemikiran penambahan konsep prior probability. Prinsip Maximum Likelihood juga sering dikatakan sudah memikirkan nilai prior probability, dimana nilai dari prior probability tersebut diseimbangkan dengan nilai Fisher Information. Hal ini akhirnya menyebabkan kedua nilai (prior dan Fisher) saling cancel out, sehingga nilai estimasi hanya tergantung pada nilai likelihood function dari data yang dianalisa saja.

Untuk bisa mendapatkan estimasi dengan memperhitungkan prior dan likelihood, tidaklah mudah. Beberapa hal yang sudah diusulkan adalah dengan menggunakan Compact Coding untuk melakukan estimasi dan pemilihan model. Compact Coding ini mencakup pencarian second derivative dari log2 prior dan log2 likelihood, yang dalam pembentukan Compact Coding, direpresentasikan dalam bentuk Fisher Information. Akan tetapi, pendekatan Compact Coding ini juga hanya memungkinkan apabila bentuk distribusi dari data yang sedang diestimasi atau dimodel adalah sederhana seperti distribusi Normal atau multinomial. Untuk distribusi yang lain seperti Gamma, Student t, dan distribusi kompleks lainnya, dan khususnya yang bersifat multivariat, agak sedikit sulit untuk diterapkan. Hal ini disebabkan karena adanya bagian yang tereliminasi dalam Compact Coding yang dihasilkan, yang dapat mengakibatkan hasil estimasi dan pemilihan model menjadi kurang akurat.

Penerapan prinsip Minimum Message Length, dengan memanfaatkan likelihood function dari data yang dimiliki dan prior probability dari nilai estimasi ini, juga dapat dilakukan dengan menciptakan sebanyak mungkin sample estimasi dari distribusi posterior terhadap data yang kita miliki. Selanjutnya, dari estimasi yang didapatkan tersebut, dipilih estimasi yang fit dan berada dalam batas wilayah estimasi dalam prinsip Minimum Message Length. Karena estimasi dari prinsip Maximum Likelihood merupakan nilai estimasi maximum, maka estimasi tersebut menjadi sample estimasi yang pertama yang dipastikan masuk di dalam batas wilayah estimasi sesuai prinsip Minimum Message Length. Dari semua estimasi yang didapatkan dan yang memenuhi prinsip batas wilayah nilai estimasi dari prinsip Minimum Message Length tersebut, maka akan didapat nilai estimasi Minimum Message Length dengan menghitung nilai rata-rata dari semua estimasi yang sudah dikonfirmasi valid tersebut.

Secara teori, kelihatan memang, bahwa estimasi atau model terpilih tidak begitu mudah untuk didapatkan dengan menggunakan prinsip Minimum Message Length. Hal ini terjadi karena prinsip Minimum Message Length menganut nilai kesempuraan yang tidak hanya melihat data yang ada di tangan, tetapi juga kemungkinan data-data lain yang tidak muncul, sebagai bagian dari populasi yang ada secara keseluruhan. Hal ini menekankan bahwa, kalau memang data yang kita miliki adalah berasal dari data sensus, maka prinsip Maximum Likelihood bisa digunakan. Akan tetapi apabila data yang kita miliki hanya merupakan sample dari sebuah populasi secara keseluruhan, maka sangat perlu untuk memikirkan data-data lain yang tidak terkena sample. Sehingga dalam melakukan estimasi data survei, pemanfaatan prinsip Minimum Message Length sangat diperlukan.

Tulisan selengkapnya dari Prinsip Minimum Message Length ini dapat dilihat dari PhD Thesis saya di Chapter III, IV, dan V.





Analytical Hierarchy Process (AHP)

23 02 2014

Analytical Hierarchy Process (AHP) adalah suatu metode pengambilan keputusan dengan melakukan perbandingan berpasangan antara kriteria pilihan dan juga perbandingan berpasangan antara pilihan yang ada. Permasalahan pengambilan keputusan dengan AHP umunya dikomposisikan menjadi kriteria, dan alternative pilihan.

Contoh permasalahan:
Bagian terpenting dari proses analisis adalah 3 (tiga) tahapan berikut:
1. Nyatakan tujuan analisis: Memilih mobil baru
2. Tentukan kriteria: style, kehandalan, dan konsumi bahan bakar
3. Tentukan alternative pilihan: Avansa, Xenia, Ertiga, Grand Livina
Informasi ini kemudian disusun membentuk pohon bertingkat
Pembentukan Pohon Bertingkat

Informasi yang ada kemudian di-sintesis untuk menentukan peringkat relative dari alternative pilihan yang ada. Kriteria dari jenis qualitative dan quantitative dapat diperbandingkan menggunakan informed judgement untuk menghitung bobot dan prioritas.

Bagaimana menentukan tingkat kepentingan relative dari kriteria yang ada?

Hal ini dapat dilakukan dengan judgement untuk menentukan peringkat dari kriteria. Dalam sebuah sistem berbasis AHP, judgement ini diberikan oleh user pengguna sistem dan dilakukan pada saat user bermaksud melakukan proses AHP dan melihat rekomendasi.

Misalnya:
1. Kehandalan 2 kali lebih penting dari style
2. Style 3 kali lebih penting dari konsumsi bahan bakar
3. Kehandalan 4 kali lebih penting dari konsumsi bahan bakar

Selanjutnya dengan pairwise comparison (perbandingan berpasangan), tingkat kepentingan satu kriteria dibandingkan dengan yang lain dapat diekspresikan.

Nilai yang digunakan:
1: equal
2: moderate
3: strong
4: very strong
5: extreme

Dari judgement di atas bisa dibuatkan tabel perbandingan berpasangan sebagai berikut:
Preferensi User

Bagaimana mengubah matrik berpasangan ini menjadi peringkat dari kriteria? Jawabannya: Eigenvector

Berikut cara untuk mencari solusi eigenvector:
1. Cara komputasi yang singkat yang bisa digunakan untuk mendapatkan peringkat adalah dengan menggunakan matrik berpasangan ini sebagai sebagai dasar penghitungan kuadrat matrik berpasangan setiap saat.
2. Jumlah setiap baris dihitung dan dinormalisasi
3. Perhitungan dihentikan apabila perbedaan dari jumlah-jumlah ini dalam dua penghitungan yang berturutan lebih kecil dari suatu angka.

Tahan 1: Kuadratkan Matrik Berbasangan

Preferensi User 02

Perhitungan Eigen Vector 01

Tahap 2: Hitung Eigenvector pertama

1. Jumlahkan baris
2. Jumlahkan jumlah dari baris-baris yang ada
3. Normalisasi nilai jumlah dari masing-masing baris

Perhitungan Eigen Vector 02
Perhitungan Eigen Vector 03

Angka normalisasi pertama yang sebesar 0.3194 didapatkan dengan membagi angka 12.75/39.9165

Jadi eigenvector yang pertama adalah:

Perhitungan Eigen Vector 04

Proses ini terus diulang: kuadrat, jumlahkan, dan normalisasikan

Perhitungan Eigen Vector 05

Dikuadratkan, dijumlah, dan dinormalisasi menjadi:

Perhitungan Eigen Vector 06
Perhitungan Eigen Vector 07
Perhitungan Eigen Vector 08

Jadi eigenvector yang kedua adalah:

Perhitungan Eigen Vector 09

Perbedaannya memang sudah kecil, apalagi kalau dihitung satu putaran lagi:

Perhitungan Eigen Vector 10

Apa arti nilai eigenvector ini? Melihat pada nilai dari eigenvector bisa dikatakan bahwa:
kriteria yang pertama adalah peringkat nomor 2 terpenting,
kriteria yang kedua adalah peringkat 1 terpenting, dan
kriteria yang ketiga adalah peringkat nomor 3 terpenting

Berikut adalah pohon dengan bobot pada kriterianya:

Pembentukan Pohon Bobot Kriteria

Selanjutnya, bagaimana menentukan peringkat alternative pilihan?

Untuk alternative pilihan, juga dilakukan perbandingan berpasangan terhadap kriteria masing-masing. Judgement dalam proses ini umumnya dilakukan berbasis pada data/informasi tentang alternative pilihan (quantitative approach) atau kalau tidak tersedia data/informasi tersebut, dapat dilakukan dengan judgement dari pakar terkait pemilihan alternative tersebut (qualitative approach).

Di dalam sebuah sistem, proses untuk menentukan nilai kriteria dari masing-masing alternative pilihan dan perhitungan peringkat dilakukan pada saat melakukan entry dan edit data variabel dan kriteria alternative pilihan.

Dalam kasus ini, yang memberikan judgement untuk kriteria style dan kehandalan adalah pakar tentang mobil dengan informasi bersifat qualitative.

Style
Perbandingan Alternatif Thd Kriteria 01

Kehandalan
Perbandingan Alternatif Thd Kriteria 02

Dari matrik ini dihitung eigenvector, untuk menentukan peringkat dari alternative pilihan untuk masing-masing kriteria.

Peringkat Style
Eigen Vector Kriteria 01

Peringkat Kehandalan
Eigen Vector Kriteria 02

Untuk kriteria konsumsi bahan bakar, ditentukan dengan informasi yang bersifat quantitative sebagai berikut:
Konsumsi Bahan Bakar
Eigen Vector Kriteria 03 Berupa Bobot

Dengan menormalisasi informasi bersifat quantitative, akan bisa didapatkan peringkat konsumsi bahan bakar untuk masing-masing alternative pilihan.

Dengan demikian bobot kriteria dan alternative pilihan sudah terlengkapi, sehingga pohon keputusan tergambar menjadi:

Pembentukan Pohon Bobot Kriteria dan Alternatif

Untuk mendapatkan hasil keputusan, masing-masing bobot untuk alternative pilihan dikalikan dengan bobot dari kriteria dalam bentuk perkalian matrik sebagai berikut:
Perhitungan AHP 01

Sehingga perhitungan untuk mobil Avanza keseluruhan nilai masing-masing alternative pilihan adalah sebagai berikut:
Perhitungan AHP 02 dan Hasil AHP

Sehingga pilihan yang paling bagus untuk kasus pengambilan keputusan ini adalah mobil dengan tipe Grand Livina.





Update KNS&I2011

22 11 2011

Pelaksanaan Konferensi Nasional Sistem dan Informatika 2011 (KNS&I2011) sudah selesai. Untuk pelaksanaan kali ini, saya tidak begitu banyak terlibat, karena harus mengikuti meeting di Jakarta dan Bandung. Pekerjaan sudah diserahkan untuk dihandle pegawai lain, dan kelihatannya pelaksanaan berjalan cukup lancar.

Makalah yang diterbitkan dalam KNS&I2011 adalah yang terbanyak dari segi jumlah sejak pelaksanaannya tahun 2006. Sungguh prestasi yang mengagumkan. Mudah-mudahan konferensi ini dapat lebih maju dan semarak lagi di tahun yang ke depan.

Bagi yang ingin mendapatkan makalah yang diterbitkan dalam KNS&I2011 ini dapat mengaksesnya melalui halaman KNS&I di blog ini.





Document Clustering Algorithm

20 09 2011

Untuk melakukan proses clustering pada document, bisa digunakan beberapa metode clustering yang telah umum digunakan seperti k-means clustering algorithm, atau variasinya: bisecting k-means, dan hierarchical clustering algorithm, baik Agglomerative atau Divisive.

Dalam melakukan proses clustering, perbandingan kesamaan (similarity) juga perlu diukur. Dalam kegiatan Document Clustering similarity measure yang banyak digunakan adalah cosine measure yang didefinisikan sebagai berikut:

cosine (d1, d2) = (d1 . d2) / (||d1|| ||d2||)

dimana . adalah vector dot product dan ||d|| adalah panjang dari vector d.

Untuk menghitung centroid dari cluster digunakan rumus berikut ini:

c = 1/|S| sum_(d in S) d

yang tidak lain merupakan vector yang didapatkan dengan merata-ratakan weight dari berbagai macam terms yang ada di dalam dokumen S.

Goodness of fit dalam document clustering yang menggunakan cosine sebagai similarity measure adalah sebagai berikut:

1/|S|^2 sum_(d in S, d’ in S) cosine (d’, d) = ||c||^2

Untuk mengukur kualitas cluster dapat digunakan
1. Entropy: memanfaatkan probabilitas dari cluster yang terbentuk yang dihitung dengan rumus E_j = – sum_i p_(ij) log p_(ij) dimana p_(ij) adalah probabilitas suatu anggota di cluster j untuk masuk ke cluster i.
2. F Measure: memanfaatkan ide presisi dan recall, dimana recall(i,j) = n_ij/n_i dan precision(i,j) = n_(ij)/n_j. n adalah jumlah anggota cluster. F Measure dihitung dengan rumus F(i,j) = (2 * recall(i,j) * precision(i,j)) / ((precision(i,j) + recall(i,j)).

Referensi:
Michael Steinbach, George Karypis, dan Vipin Kumar (2000). A Comparison of Document Clustering Techniques. Technical Report #00-034, Department of Computer Science and Engineering, University of Minnesota.