Curse of Dimensionality (Kutukan dimensi tinggi)

Materi ini saya rangkumkan dari beberapa literatur yang tercantum pada bagian “referensi”, sebagai bahan diskusi di milis indo-dm, sc-ina dan statcom-indo.

Salah satu masalah yang sering dijumpai dalam aplikasi pattern recognition pada real-world domain, adalah tingginya dimensi data yang diolah. Misalnya data observasi meteorologi untuk menentukan muncul tidaknya kabut berkisar 26 atribut. Data biomedis yang dipakai untuk memprediksi efektifitas terapi interferon pada pasien hepatitis C kronis berkisar 30. Dimensi input data hasil feature extraction pada tulisan tangan adakalanya lebih dari 700 (feature extraction memakai Peripheral Distributed Contributivity, menghasilkan data berdimensi 768 dari mesh 64×64). Bahkan ada diantaranya yang berdimensi ribuan, seperti data microarray, karena gen manusia berkisar 22 ribu.

Mengapa tingginya dimensi ini membuat masalah jadi sulit ? Bukankah semakin banyak item yang diobservasi, akan membuat klasifikasi suatu data menjadi mudah ? Misalnya saja, untuk membedakan atlit tinju dan atlit sepakbola, selain berat badan dan tinggi, mungkin kalau kita tambahkan observasi mengenai lebar bahu, lingkar perut, dan berbagai informasi dari observasi ciri fisik yang lain, akan membuat kedua atlit itu lebih mudah dibedakan ? Pendapat ini ada benarnya. Umumnya penambahan atribut pada suatu data akan membuat proses klasifikasi menjadi lebih mudah. Tetapi jika jumlah atribut terus bertambah, sedangkan jumlah sampel data terbatas, maka akurasi klasifikasi ini pada titik tertentu akan menurun. Fenomena inilah yang disebut “Curse of dimensionality” (dalam bahasa Jepang disebut jigen noroi 次元呪い), yang pertama kali dibahas oleh Bellman di papernya th.1961.

Penjelasannya, adalah demikian. Misalnya dari data pada training set, kita ingin membuat model pemetaan non linear, dari satu titik yang dinyatakan dalam D variabel (x1, x2, …,xD) ke satu target output y. Dengan demikian tiap titik terdapat pada ruang vektor berdimensi D. Selanjutnya tiap sumbu variabel itu dibagi ke dalam interval yang sama. Misalnya kalau x1 dibagi 10 bagian, akan menjadi x1,1, x1,2, …, x1,10. Hal yang sama diterapkan pada sumbu yang lain (x2, dst). Kalau jumlah variabelnya 3 (D=3), berarti tiap titik training set akan berada pada ruang vektor berdimensi 3 yang telah dibagi-bagi dalam kubus kecil (selanjutnya disebut sel) sebanyak 10*10*10 = 1000. Gambar di bawah menunjukkan sel-sel yang terdapat pada ruang vektor berdimensi 3 setelah dibagi dalam interval tertentu. Dengan memakai model pemetaan itu, jika ada suatu titik baru (dari test set) yang ingin kita ketahui hasil pemetaannya, maka kita cukup memeriksa pada sel manakah (dari 1000 sel pada ruang vektor) titik baru itu berada. Misalnya titik baru itu terletak pada sel dengan koordinat (3,5,7). Selanjutnya kita periksa ke nilai output y berapakah data training set yang terletak pada sel (3,5,7) itu dipetakan. Tentunya pemetaan ini bisa berjalan dengan baik, apabila tiap sel itu memiliki setidaknya sebuah data dari training set. Dengan demikian, pada contoh kasus ini, diperlukan setidaknya 1000 sampel data yang dipakai sebagai training set.

Apabila tingkat resolusi pembagian tiap sumbu itu kita tingkatkan, misalnya dari 10 ke 20 (x1 dibagi ke dalam 20 bagian, dan demikian juga x2 dan sumbu yang lain), maka ruang vektor yang sama akan dibagi kedalam 20*20*20 = 8 ribu sel. Kalau saja training set yang ada mencukupi untuk memenuhi tiap sel, maka kita dapat berharap memiliki model yang lebih akurat.

Kesimpulan : Jika dimensi data D, dan tiap sumbu variabel dibagi ke dalam M interval, diperlukan setidaknya M^D data pada training set yang mengisi tiap sel, agar pemetaan non linear itu bisa berjalan dengan baik.

Konsekuensi dari kesimpulan di atas, jika dimensi data itu ditingkatkan menjadi D+1, maka banyaknya data yang diperlukan akan menjadi M^D * M = M^(D+1) , dengan kata lain data yang diperlukan meningkat secara eksponensial seiring dengan meningkatnya dimensi data. Padahal umumnya data yang tersedia dan dapat dipakai sebagai training set berjumlah terbatas. Hal ini mengakibatkan, jika tidak semua sel pada ruang vektor itu terisi oleh data, dengan kata lain, keberadaan data sangat sparse. Ini menyebabkan model pemetaan yang dibangun tidak akan bekerja dengan optimal atau baik.

– bersambung –

Referensi:

1. Cristopher M. Bishop, Neural Network for Pattern Recognition, Oxford University Press, 1995

Diskusi & tanggapan dari rekan-rekan di milis indo-dm@yahoogroups.com, sc-ina@yahoogroups.com

1. Maman Djauhari
   Pak Anto,Saya senang sekali masalah tersebut diangkat dalam mailing list ini. Ini masalah yang selalu akan menjadi topik sentral di dunia riset information science & statistics. Saya sendiri biasa kerja denganvery large data sets yang berdimensi p sangat tinggi (p berorderibuan).Salah satu masalah terbesar adalah mencari robust estimation yang akan
   menjamin reliable information. Teknologi-teknologi yang ada hingga saat ini yang memberikan robust estimates, selalu melibatkan determinan dan atau inverse matriks yang berukuran pxp. Padahal p sangat besar.Masalahnya: “Bagaimana kita ciptakan mathematical structure sehingga kita terlepas dari masalah perhitungan determinan dan inverse tersebut?” Sayaakan sangat bergembira bila bisa share our ideas tentang masalah ini. Insya Allah ini akan merupakan kontribusi orisinal to information science & statistics.Salam,
   Maman A. Djauhari
   d/h Departemen Matematika ITB
2. Soesianto Fransiskus
   TS yth -Kutukan dimensi tinggi hendaklah jangan ditafsirkan sebagai kutukan — namun hendaklah dilihat sebagai tantangan: Bellman pun sebenarnya melihat hal itu sebagai hal yang wajar dalam pemikiran pemrograman dinamiknya. Dan itulah sebabnya mengapa pemrograman dinamik tampak mandeg = tidak ada terobosan baru lagi. Tentang hal ini semoga saya salah, karena sudah lama saya tidak mengikuti perkembangannya.
   Kita tahu bahwa metode kofaktor (Cramer) bukanlah metode yang pas untuk menginvers sebuah matrix dimensi besar. Namun kita juga tahu bahwa ada metode lain yang jauh jauh lebih jozh, bukan?! Saya melihat hal itu sebagai karunia Allah yang patut kita syukuri.
   Demikian juga untuk matrix berdimensi sangat besar. Secara matematis dapat saja difikirkan hadirnya persoalan itu. Dan itu memang tantangan dalam bidang matematika (murni). Namun dalam pemahaman saya, matrix seperti itu biasanya datang dalam konteks persoalan konkret yang pasti diikuti oleh sifat atau ciri khas yang langsung mengindikasikan cara efektif untuk menyelesaikannya. Tegasnya, matrix berdimensi besar (katakanlah: 10 juta kali 10 juta, misalnya), biasanya bersifat jarang = ‘sparse’. Ciri ‘sparse’ itulah yang membuat komputasi yang dibayangkan sebagai ‘sangat tidak mungkin dikerjakan’ menjadi ‘sangat pasti dapat dikerjakan’, apalagi oleh teknologi komputer dewasa ini. — ‘Sparsity’ merupakan berkat yang dengan cuma-cuma diberikan oleh Allah kepada kita.
   Semoga catatan kecil ini berguna.
   Salam, pak Soes
3. Anto S. Nugroho
   Pak Soes, Pak Maman dan rekan sejawat yth.

   Terima kasih atas tanggapannya. Tema ini salah satu minat riset saya, dan semoga bisa sebagai penyegaran di perguliran tahun 2007-2008. Mengenai “sparsity”, hal itu memang sering terjadi dalam data yang berdimensi sangat tinggi. Paper-paper yang menganalis data microarray, misalnya, seringkali hanya memakai beberapa puluh sampel saja. Padahal dimensi data yang diolah sekitar 7 ribu-an. Data yang dipakai dalam riset biomedis sering mengalami kendala demikian: jumlah sampel sangat sedikit, dan hampir tidak mungkin ditambah lagi. Karena :
   1. Biaya pengadaan sampel sangat mahal. Untuk microarray,misalnya, per sampel bisa sampai ribuan USD.
   2. Tidak mudah mencari pasien yang memiliki karakteristik data yang diperlukan oleh model matematika yang dibangun. Hal ini menyebabkan kita tergiring dalam permasalahan lain : imbalanced data problem (one of the class is heavily represented compared to the other).

   Curse dimensionality menjelaskan bahwa model yang dibangun dengan data yang sparse cukup berbahaya. Saya kirimkan sambungan tulisan sebagaimana di bawah.

   Sebenarnya ini rangkuman dari berbagai literatur, sebagai pelengkap materi “The role of feature selection in datamining” yang saya presentasikan dalam diskusi di STTTelkom kemarin. Ada gambar yang ingin saya tampilkan, tapi karena milis tidak  menerima attachment, silakan rekan-rekan melihat pada URL yang diberikan.

   Selamat tahun baru 2008. Semoga di tahun 2008, kita dapat lebih intensif dalam bersinergi mengejar kemajuan bersama, khususnya di bidang keilmuan yang kita cintai ini.

   Wassalam

   Anto S. Nugroho, Dr.Eng
   Pusat Teknologi Informasi & Komunikasi, BPP Teknologi
   URL: http://asnugroho.net

4. Budi Santosa
   Saya kebetulan pernah menggunakan beberapa metoda untuk melakukan varible
   selection atau feature sel. Metoda statistik biasanya perlu waktu lama
   (computation time) karena biasanya menggunakan pendekatan korelasi var
   input dengan output.
   Saya lebih suka menggunakan machine learning. Dalam penelitian saya (yang
   didanai Dikti lewat Hibah Fundamental 2007) saya menggunakan linear SVM
   untuk memilih variabel yang signifikan untuk memprediksi output dalam
   kasus klasifikasi multikelas.
   Dengan Linear SVM, waktu komputasi menjadi berkurang secara signifikan
   dengan akurasi yang tetap tinggi.
   Untuk kasus nonlinear banyak orang mengembangkan feat sel menggunakan
   kernel-SVM (Chapelle dan Vapnik dkk, Mangasarian, S. Canu   and A.
   Rakotomamony, dll).
   Saya nggak tahu Pak anto memakai pendekatan apa?

   salam
   Budi

5. Anto S. Nugroho
   Pak Budi, sekedar konfirmasi. Apakah metode yang dipakai ini sebagaimana dikenalkan oleh Isabelle Guyon (groupnya Vapnik), y.i. Recursive Feature Elimination ?
   I. Guyon, J. Weston, S. Barnhill, and V. Vapnik. Machine Learning, Vol. 46, pp. 389–422, 2002
   > Untuk kasus nonlinear banyak orang mengembangkan feat sel menggunakan
   > kernel-SVM (Chapelle dan Vapnik dkk, Mangasarian, S. Canu   and A.
   > Rakotomamony, dll).  Saya nggak tahu Pak anto memakai pendekatan apa?

   Salah satu riset yg kami lakukan adalah :
   – memakai margin sebagai subset evaluation criterion
   – untuk selection algorithm memakai Sequential Backward Selection.
   Jadi prinsipnya, metode tsb.
   – mengandung bias, karena kualitas subset yang dipilih ditentukan dari hasil akurasi klasifikasi memakai metode tertentu (SVM).
   – termasuk kategori wrapper, karena kualitas subset yang dipilih diukur dengan akurasi classifier. Dengan demikian akan menyebabkannya lebih kompleks daripada metode filter yang mendasarkan intrinsic properties dari data.
   – multivariate, karena kualitas diukur pada level subset, bukan feature secara individual
   – hanya bisa diterapkan untuk classification memakai SVM
   Papernya dapat didownload dari homepage saya:
   “Feature Subset Selection for Support Vector Machines using  Confident Margin,”International Joint Conference on Neural Network 2005, pp.907-912, Montreal, Canada (2005)

   Untuk studi saya yang terakhir, yaitu analisa data interferon, saya pernah
   juga mencoba beberapa metode dengan mengkombinasikan
   – Feature Selection Algorihtm :
   Sequential Forward Selection, Sequential Backward Selection, Sequential Floating Selection dan Individual Merit Based Method
   – Subset evaluation criterion:
   Mahalanobis Distance, 1-nearest neighbour classification rate,  dan Fisher Criterion

   Saya coba baik pendekatan wrapper maupun filter, untuk mencari yang terbaik diantara keduanya. Hasil terbaik saya peroleh saat memakai pendekatan tipe filter, yaitu individual merit based algorithm dengan memakai Fisher Criterion untuk mengevaluasi kontribusi tiap feature secara individual terhadap class separability.
   Paper:
   “Efficacy of Interferon Treatment for Chronic Hepatitis C Predicted by Feature Subset Selection and Support Vector Machine”, Journal of Medical Systems, 007 Apr;31(2):117-23, Springer PMID: 17489504 (PMID:PubMed Unique Identifier)
   Sekiranya ada rekan yg berminat akan saya kirimkan via japri.

6. –
   

Iklan