e-kolokium : Self Organizing Feature Maps

[presentasi di e-kolokium sc-ina@yahoogroups.com 1-15 Juli 2008, updated July 7 2008, 17.47]

Rekan-rekan yth.
Maaf, saya terlambat menjelaskan isi dari materi e-kolokium kali ini. Terima kasih atas saran mas Surya. File sudah saya konversikan ke pdf, dan telah diupload di yahoogroups. File saya pecah jadi 3:

  • som_part1.pdf (6 slide, 169 kB) menjelaskan teori SOM
  • som_part2.pdf (8 slide, 415 kB) menjelaskan contoh aplikasi SOM pada peta kemakmuran dunia & WebSOM, berasal dari situs WebSOM (http://websom.hut.fi)
  • som_part3.pdf (14 slide, 438 kB) menjelaskan eksperimen saya dengan SOM pada huruf Kanji, berasal dari paper saya :
    A.S. Nugroho, S. Kuroyanagi, A. Iwata : Mathematical perspective of CombNET and its application to meteorological prediction, Special Issue of Meteorological Society of Japan on Mathematical Perspective of Neural Network and its Application to Meteorological Problem, Meteorological Research Note, No.203, pp.77-107, October 2002 (Japanese Edition)
    Judul asli:
    “CombNETの数理と気象予測への応用”, 日本気象学会気象研究ノート特集号:”ニューラルネットワークの数理と気象への応用”,203号(上), pp.77-107, 2002年

Silakan rekan-rekan mendownloadnya. Berikut presentasi saya :

(1) Teori Self Organizing Feature Maps

Self Organizing Feature Maps, atau disingkat SOM adalah salah satu jenis neural network yang dikembangkan oleh Teuvo Kohonen (professor Helsinki University). SOM bekerja dengan memetakan data yang berasal dari ruang dimensi tinggi, ke ruang vektor 1 dimensi atau 2 dimensi, dengan tetap mempertahankan topologi data itu. Maksudnya, dua data yang pada dimensi asal terletak berjauhan, akan dipetakan ke dua titik yang berjauhan juga di ruang 1D atau 2D. Sebaliknya, dua data yang pada dimensi asal terletak berdekatan, akan dipetakan ke dua titik yang berdekatan juga di ruang 1D atau 2D.

Slide p.3 pada file som_part1.pdf memperlihatkan model neuron yang dipakai dalam algoritma SOM. Sebuah neuron memiliki reference vector yang berdimensi N, sebanyak M buah (dinotasikan sbg. m_1, m_2, …,m_M). Sedangkan input yang berasal dari training set dinotasikan sebagai x_1, x_2, … x_K, dimana K adalah banyaknya input data. Input data merupakan vektor yang berdimensi N juga. Output dari tiap neuron merupakan jarak/distance dari sebuah input pattern x_k dengan reference vektor yang dimiliki neuron itu (m_i). Distance di sini bisa memakai pengukuran cosinus sudut yang dibentuk kedua vektor, euclidean distance, maupun distance metric yang lain.

Slide 4 menjelaskan algoritma SOM.

  1. Pertama-tama reference vector diinisiasi secara random. Misalnya pola mapping yang diambil adalah 2 dimensi (data akan dipetakan ke 2D-SOM), diatur pada posisi grid 12×12 (berarti banyaknya neuron M=144 buah).
  2. Untuk tiap data dari training set, misalnya x_i, dihitung jaraknya terhadap semua reference vector neuron SOM (m_1, m_2, …, m_M). Tentukan neuron yang memiliki jarak terdekat dengan x_i. Neuron ini disebut winner/pemenang (misalnya winner itu dinotasikan sebagai m_c)
  3. Update-lah reference vector dari neuron winner (m_c), DAN juga tetangganya. “Tetangga” di sini dimaksudkan dengan neuron yang posisinya di grid 2 dimensi terletak berdekatan dengan m_c. Agar lebih jelas, silakan lihat di slide som_part1.pdf, p.6. Misalnya neuron yang di tengah menjadi winner, maka pada step-1, tetangganya adalah yang berada di area yang berarsir warna hijau muda. Neighborhood function pada step-1 (t=1) dinotasikan sebagai N_c(t_1).
  4. Step 2 dan 3 diulang hingga diterapkan pada semua data dari training set (x_1, x_2, …, x_K)
  5. Kemudian secara bertahap, kurangkanlah learning-rate dan radius neighborhood function lewat satu persamaan tertentu, dan ulangi lagi tahap 2, 3 dan 4 di atas.
  6. Proses training dihentikan jika iterasi-nya mencapai nilai tertentu.

Catatan:

  1. Layer dimana neuron diatur ke grid 12×12 ini disebut map layer
  2. strategi pembelajaran dimana neuron-neuron berkompetisi agar menjadi pemenang terhadap sebuah input yang sama ini disebut sebagai sebagai Competitive learning.
  3. Dalam SOM, winner hanya dipilih sebuah saja. Strategi ini populer disebut “winner take all”. Tim riset Prof.Hagiwara (Keio Univ.) pernah memperkenalkan varian dari SOM misalnya dengan menentukan lebih dari 1 neuron sebagai winner.
  4. Persamaan untuk meng-update reference vector didefinisikan di p.5 file som_part1.pdf. Untuk neuron yang termasuk dalam radius neighboring function, reference vector yang baru dihitung sebagaimana persamaan (1). SInterpretasi geometris dari persamaan tersebut adalah, reference vector yang termasuk dalam radius neighborhood function itu “ditarik” pada porsi tertentu mendekat ke arah x_k (input pattern). Porsi pergeseran itu dikontrol lewat parameter alfa (learning rate).
  5. Eq.3 memperlihatkan contoh learning rate function, sedangkan Eq.4 memperlihatkan contoh Neighborhood function. Neighborhood function tidak selalu berbentuk lingkaran, tetapi bisa juga berbentuk polygon dsb.

(2) Aplikasi pada pembuatan poverty map

Aplikasi SOM yang populer adalah pembuatan poverty map (peta kemakmuran) negara-negara di seluruh dunia. Slide pp.2-4 dari file som_part2.pdf berasal dari http://www.cis.hut.fi/research/som-research/worldmap.html
Data kemakmuran tiap negara berasal dari world bank statistics, pada tahun 1992. Tingkat kemakmuran tiap negara diukur dengan 39 indikator yang menunjukkan QOL (Quality of Life) seperti kesehatan, gizi, layanan pendidikan, dsb. Data yang berdimensi tinggi ini kemudian divisualisasikan oleh SOM sebagaimana pada http://www.cis.hut.fi/research/som-research/povertymap.gif

Pada gambar tsb. Indonesia yang disimbolkan dengan IDN terletak pada region berwarna pink. Pada tahun 1992, Indonesia masih dekat tingkat kemakmurannya dengan CHN (China), Turkey, Birma, dan Madagaskar. Tahun 1992, seingat saya kita masih cukup “bergaung” sebagai salah satu macan Asia yang akan menyusul Jepang, Singapura, Korea dsb. Jepang terletak pada sisi kiri, berwarna kuning tua. Tingkat kemakmuran Jepang berdekatan dengan Netherlands, Italia, Belgi, Swedia, Yugoslavia, Spanyol, Irlandia dan Finlandia. USA dekat dengan Canada, dan sedikit terpaut dengan Israel dan Australia. Kalau mengikuti perkembangan Cina yang sangat pesat, tentunya saat ini Cina telah meninggalkan cluster Indonesia,
dan dekat dengan tingkat kemakmuran Jepang.

Dalam aplikasi ini SOM memperlihatkan kemampuannya mengkombinasikan non linear projection & clustering pada sebuah ordered vector quantization graph.

Gambar pada slide p.3 berasal dari http://www.cis.hut.fi/research/som-research/worldmap.gif
memperlihatkan hasil pewarnaan tiap negara dengan tingkat kemakmuran yang diperoleh dari gambar sebelumnya.

(3) Aplikasi pada WebSOM (http://websom.hut.fi/websom/)

WebSOM salah satu teknik untuk mengorganisasikan koleksi teks secara otomatis, dimana teks itu akan dipetakan terurut (ordered map), yang membantu proses mining maupun information retrieval. Yang membedakannya dengan algoritma clustering yang lain adalah artikel yang isinya memiliki tingkat similarity yang tinggi, akan terletak berdekatan pada peta tersebut. Demo dari WebSOM dapat dilihat dari http://websom.hut.fi/

Gambar pada slide adalah contoh tampilan websom dari situs http://websom.hut.fi/websom/comp.ai.neural-nets-new/html/root.html yang diperoleh dari 12088 posting di usenet newsgroup comp.ai.neural-nets, sejak Juni 1995 sampai Maret 1997. Jika salah satu kata kunci pada gambar tersebut diklik, berturut-turut akan ditampilkan perbesaran wilayah tersebut, hingga akhirnya diperoleh posting/artikel yang diinginkan. Perbedaan warna pada peta tersebut menunjukkan density, semakin terang berarti semakin banyak dokumen pada cluster tersebut. Misalnya kita memiliki sebuah artikel, yang dianalisa statistik kemunculan katanya, kemudian dimasukkan ke WebSOM, maka dokumen itu akan dipetakan ke satu node yang konten artikel pada node tsb. maupun node-node tetangganya mirip dengan konten artikel tadi.

(3) Aplikasi pada huruf Kanji

Pada slide ketiga, memuat hasil eksperimen saya dengan huruf Kanji [3]. Huruf kanji yang dipakai dalam eksperimen sebanyak 2965 jenis (JIS-1), font size 12pt, yang discan pada resolusi 400 dpi, dikonversikan ke 60×60 dot, dan dinormalisasikan ke 16×16 gray-scale (mesh feature). SOM yang dipakai berukuran 12×12 (2 dimensi). Pada slide berikutnya dapat dilihat perubahan reference vector pada fase pembelajaran. Saat iterasi sampai ke-10, mulai terlihat bentuk huruf Kanji yang terletak pada urutan terakhir (2965). Ini dikarenakan di fase awal pembelajaran radius neighborhood function sangat besar, sehingga hampir seluruh neuron diupdate reference vector-nya. Efeknya, hampir seluruh reference vector merefleksikan bentuk huruf yang mirip satu sama lain. Saat sampai iterasi ke-80, sudah terlihat jelas perbedaan reference vector satu sama yang lain. Pada kondisi ini clustering sudah mulai stabil, dan radius neighborhood function semakin kecil. Proses pembelajaran dihentikan pada saat 100x iterasi. Terlihat dengan jelas, pola root dari huruf Kanji (kimbeng, ninben pada baris pertama, sansui hen pada baris pertama kanan, dst.). Topological mapping yang dibentuk oleh SOM dapat terlihat dari gambar tsb. dimana root yang memiliki bentuk mirip akan dipetakan ke neuron yang berdekatan.

Referensi

  1. Teuvo Kohonen, Self-Organizing Maps, 3rd Ed. Springer, 2001
  2. Situs WebSOM : http://websom.hut.fi/
  3. A.S. Nugroho, S. Kuroyanagi, A. Iwata : “Mathematical perspective of CombNET and its application to meteorological prediction,”Special Issue of Meteorological Society of Japan on Mathematical Perspective of Neural Network and its Application to Meteorological Problem, Meteorological Research Note, No.203, pp.77-107, October 2002 (Japanese Edition)

Source code SOM dapat didownload dari http://www.cis.hut.fi/research/som_pak/

Iklan

Tentang Anto Satriyo Nugroho

My name is Anto Satriyo Nugroho. I am working as research scientist at Center for Information & Communication Technology, Agency for the Assessment & Application of Technology (PTIK-BPPT : Pusat Teknologi Informasi & Komunikasi, Badan Pengkajian dan Penerapan Teknologi). I obtained my doctoral degree (Dr.Eng) from Nagoya Institute of Technology, Japan in 2003. My office is located in Serpong, Tangerang Selatan City. My research is on pattern recognition and image processing with applied field of interests on biometrics identification & development of computer aided diagnosis for Malaria. Should you want to know further information on my academic works, please visit my professional site at http://asnugroho.net
Pos ini dipublikasikan di neuro, research, talk & seminars. Tandai permalink.

4 Balasan ke e-kolokium : Self Organizing Feature Maps

  1. putra berkata:

    Pak Anto bisakah Bapak kirimkan materi
    # som_part1.pdf (6 slide, 169 kB) menjelaskan teori SOM
    # som_part2.pdf (8 slide, 415 kB) menjelaskan contoh aplikasi SOM pada peta kemakmuran dunia & WebSOM, berasal dari situs WebSOM
    karena saya tidak bisa mendownload. Terima kasih sebelumnya

  2. Mas Putra,
    Bisa saja saya kirim, tetapi sayangnya file itu ada di PC saya di kantor. Hari Senin baru bisa saya kerjakan. Atau bisa juga didownload langsung dari milis sc-ina, di bagian files. Untuk mendownload-nya perlu mendaftar dulu sebagai anggota milis, dengan mengirim email ke sc-ina-subscribe@yahoogroups.com

  3. fafa fauziah berkata:

    pak anto, mungkin permintaan saya hampir sama dengan mas putra.
    bisa tidak pak saya dikirimkan filenya
    # som_part1.pdf (6 slide, 169 kB) menjelaskan teori SOM
    # som_part2.pdf (8 slide, 415 kB) menjelaskan contoh aplikasi SOM pada peta kemakmuran dunia & WebSOM, berasal dari situs WebSOM
    karena saya tidak bisa mendownload. Terima kasih sebelumnya

  4. frianto berkata:

    mohon mas anto dapat kiranya di emailkan seperti permintan di atas.

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s