Indie Lagu :: Lagu Tarbaru

Saturday, April 11, 2009

Force Directed Approach

Solusi kedua yang dapat digunakan untuk menampilkan N-Dimensi data ke dalam representasi 2D adalah Force Directed Approach.  Di dalam pendekatan ini, dokumen disajikan dalam bentuk graph.

Tujuan dari pendekatan ini adalah menemukan layout yang baik dari graph (low energy states).  Pada kondisi awal kita akan membuat layout inisial yang bersifat random, kemudian dengan memberikan gaya/forces pada layout awal ini, kita mencoba mencapai layout yang diharapkan.  Proses pembentukan layout dari kondisi awal/acak menjadi layout yang baik, ditunjukkan gambar berikut:

Gaya yang diberikan diantara node dan edge mirip dengan fenomena pegas.  Jika kita menarik salah satu sisi, maka sisi yang lain juga akan tertarik.  Proses tarik menarik (proses saling mempengaruhi) yang disebabkan oleh karena gaya eksternal yang diberikan akan berakhir disaat kita mencapai low energy states.  Pada kondisi ini posisi relatif dari setiap node tidak akan berubah lagi dari iterasi ke iterasi berikutnya.  Yang perlu diingat dari pendekatan ini adalah gaya yang diberikan pada layout awal (kondisi acak) yang menyebabkan adanya proses saling mempengaruhi di antara semua node dan edge, tidak akan mengubah relasi antara node yang sudah terbentuk.

Keuntungan
  1. Representasi 2D dari pendekatan ini sangat bagus dan memenuhi kriteria estetika seperti keseragaman panjang edge, keseragaman distribusi node dan adanya kesimetrian.
  2. Tingkah laku dari pendekatan ini mudah diprediksi dan dipahami karena mengikuti fenomena alam yang sering kita lihat, fenomena pegas.
Kerugian
Membutuhkan waktu eksekusi yang yang tinggi kurang lebih O(V3). Dimana V adalah jumlah node di dalam graph.

Referensi:

  1. Prof. Dr.-Ing. Jürgen Ziegler, Interacitve Systeme Informationsvisualisierung, Duisbug-Essen University, 2008
  2. Wikipedia : Force-based_algorithms

Sumber gambar:

http://cobra.ee.ntu.edu.tw/~sanlin/sanlin/slides/IV2005-EEReplusion.ppt

No comments: