Pemilihan fitur

Pemilihan fitur (feature selection) atau turut dikenali sebagai pemilihan atribut merupakan sebahagian daripada konsep yang terdapat dalam bidang perlombongan data. Ia sering dilaksanakan dalam fasa prapemprosesan data. Objektif proses pemilihan fitur adalah bagi memilih subset fitur optimum daripada set fitur asal dengan cara menyingkirkan fitur yang tidak relevan, lewah (redundant) dan hingar (noise).^[1] Penggunaan subset fitur yang optimum dalam model pembelajaran mesin mampu meningkat ketepatan ramalan, mengurangkan kompleksiti model serta mengurangkan kos pengkomputeran.^[1]

Pemilihan fitur juga merupakan salah satu teknik yang dilaksanakan bagi mengelakkan berlakunya curse of dimentionality.^[2] Suatu model dikatanya menghadapi isu curse of dimentionality apabila semakin tinggi dimensi fitur, prestasi model semakin merosot. Curse of dimentionality mengakibatkan terjadinya isu terlebih padanan iaitu keadaan di mana model yang dibangunkan hanya menunjukkan prestasi yang baik apabila menggunakan data ujian namun sebaliknya berlaku apabila data baharu digunakan.

Secara umumnya kaedah pemilihan fitur dikategorikan kepada penapis (filter), pembalut (wrapper) dan hibrid^[3]. Perincian mengenai kaedah pemilihan fitur diterangkan dalam subtopik berikutnya.

Kaedah pemilihan

Penapis

Kaedah penapis (filter) merupakan kaedah pemilihan fitur yang paling ringkas di mana ujian statistik tertentu dilaksanakan bagi menentukan pemeringkatan fitur (feature ranking). Ia dilaksanakan sama ada berdasarkan ukuran kesandaran, jarak atau konsistensi di antara suatu fitur dengan kelas sasaran. Information gain dan Pearson’s correlation merupakan contoh ujian statistik yang menggunakan ukuran kesandaran manakala algoritma Relief adalah contoh yang menggunakan ukuran jarak. Pemilihan ujian statistik untuk digunakan perlu bersesuaian dengan jenis fitur yang ingin diproses sebagai contoh information gain hanya sesuai untuk fitur berjenis nominal manakala Pearson’s correlation sesuai digunakan untuk data numerik dan binomial sahaja.

Pemilihan fitur menerusi kaedah penapis dilaksanakan dalam dua langkah seperti berikut:

Langkah 1: Ujian statistik tertentu dilaksanakan terhadap semua fitur bagi mendapatkan skor setiap fitur.

Langkah 2: Subset fitur dengan skor terbaik dipilih manakala fitur selebihnya disingkirkan berdasarkan nilai ambang yang ditetapkan.

Antara kaedah yang digunakan untuk menentukan nilai ambang adalah berdasarkan jurang terbesar nilai skor di antara dua fitur berturutan yang disusun secara bertingkat^[4] atau menyingkirkan fitur dengan skor yang melebihi dua varians daripada nilai min skor^[5].

Kelebihan ketara kaedah pemilihan fitur secara penapis adalah penggunaan kos pengkomputeran yang minimum dan masa pemprosesan yang sangat pantas. Oleh itu ia amat sesuai digunakan untuk memilih subset fitur daripada set data yang bersaiz besar. Namun disebabkan keringkasan kaedah penapis yang tidak mengambil kira interaksi di antara fitur-fitur, terdapat kebarangkalian wujudkan masalah kelewahan fitur apabila subset fitur dipilih.

Pembalut

Berbeza dengan kaedah penapis, kaedah pembalut (wrapper) menggunakan algoritma pembelajaran seperti Pohon Keputusan, Naive Bayes, Hutan Rawak dan lain-lain bagi menjana subset fitur. Secara umumnya, empat langkah utama yang terlibat dalam proses pemilihan fitur kaedah pembalut adalah seperti berikut:

Langkah 1: Jana subset dengan menggunakan strategi carian (search strategy) tertentu, iaitu sama ada strategi carian menyeluruh (exhaustive), strategi carian berjujukan atau strategi carian rawak^[5].


Startegi carian	Penerangan
Strategi carian menyeluruh	Proses janaan subset menggunakan strategi carian menyeluruh Dalam strategi carian secara menyeluruh, semua kombinasi fitur dijana dan dinilai bagi mendapatkan subset fitur optimum. Bagi set data dengan sejumlah j fitur, bilangan subset yang perlu dijana dan dinilai adalah sebanyak 2^j-1. Contohnya bagi set data dengan 4 fitur iaitu {a, b, c, d}, sebanyak 2⁴-1 = 15 subset dijana dan dinilai. Proses janaan dan penilaian dimulakan dengan subset yang mengandungi satu fitur sahaja iaitu {a}, {b} ... {d}. Kemudian diikuti dengan subset yang terdiri daripada dua fitur iaitu {a, b}, {a,c} ... {c,d}. Proses janaan dan penilaian subset diulang sehingga subset dengan semua fitur dipilih. Proses janaan subset diilustrasi seperti dalam Rajah di sebelah. Contoh strategi carian secara menyeluruh adalah kaedah Brute-Force. Kelebihan strategi carian secara menyeluruh adalah subset optimum sentiasa dapat ditemukan. Walau bagaimanapun kelemahan ketara strategi ini adalah ia memerlukan kos pengkomputeran yang sangat tinggi, oleh itu hanya sesuai digunakan untuk set fitur yang kecil^[6]
Strategi carian berjujukan	Dalam strategi carian secara berjujukan, fitur dipilih atau disingkirkan satu persatu secara berjujukan sehingga subset optimum diperoleh. Tiga variasi strategi carian berjujukan adalah: Pemilihan ke depan (forward selection) Penyingkiran undur (backward elimination) Dua arah (bi-direction). Pemilihan ke depan Proses janaan subset dimulakan dengan set kosong. Seterusnya secara berjujukan, fitur dengan nilai fungsi objektif tertinggi apabila digabungkan dengan fitur-fitur yang telah dipilih ditambah ke dalam subset. Penyingkiran undur Proses janaan subset dimulakan dengan keseluruhan set data. Seterusnya fitur yang menyebabkan pengurangan nilai fungsi objektif yang paling rendah disingkirkan secara berjujukan satu persatu daripada set data. Kaedah penyingkiran undur sesuai digunakan bagi menjana subset fitur optimum yang mengandungi bilangan fitur yang banyak kerana proses janaan subset dimulakan dengan keseluruhan set data. Dua arah Merupakan gabungan antara pemilihan ke depan dan penyingkiran undur yang dilaksanakan secara serentak. Bagi mengelakkan pemilihan ke depan dan penyingkiran undur daripada memilih dan menyingkirkan fitur yang sama, algoritma dua arah mensyaratkan supaya fitur yang telah dipilih oleh pemilihan ke depan tidak lagi boleh disingkirkan oleh penyingkiran undur dan begitu juga sebaliknya. Contohnya sebelum pemilihan ke depan menambah suatu fitur, ia akan menyemak terlebih dahulu sama ada fitur tersebut telah disingkirkan oleh penyingkiran undur. Jika ya, pemilihan ke depan akan mengabaikan fitur tersebut dan akan menambah fitur kedua terbaik. Secara umumnya, ketiga-tiga kaedah janaan subset secara berjujukan pemilihan ke depan, penyingkiran undur dan dua arah adalah lebih ringkas dan pantas untuk dilaksanakan berbanding kaedah janaan subset fitur secara menyeluruh (exhaustive) kerana ia tidak mengambil kira setiap kombinasi fitur. Namun begitu, kaedah janaan subset secara berjujukan mempunyai potensi untuk menghadapi isu local optima.
Strategi carian rawak	Bagi set data yang mengandungi sehingga ribuan fitur seperti dalam aplikasi pemprosesan teks, bahasa tabii dan bioinformatik, proses carian subset yang melibatkan keseluruhan feature space adalah tidak praktikal kerana memerlukan sumber pemprosesan yang tinggi. Dalam aplikasi sebegini, strategi pemilihan secara rawak adalah lebih efisien untuk digunakan kerana ia melaksanakan pemilihan fitur pada sebahagian feature space sahaja. Menerusi strategi carian secara rawak, pemilihan fitur dibuat berdasarkan prinsip pemilihan semula jadi yang mengandungi ciri rawak. Ciri-ciri rawak yang digunakan ini menyebabkan isu local optima dapat dielakkan^[2]. Contoh strategi carian secara rawak adalah algoritma genetik (genetic algorithm). Algoritma genetik merupakan satu teknik yang diinspirasikan daripada proses evolusi semula jadi seperti pewarisan (inheritance), penyilangan (crossover), mutasi dan pemilihan^[7]. Algoritma genetik menggunakan istilah kromosom sebagai perwakilan penyelesaian masalahnya. Langkah janaan subset menerusi strategi carian rawak adalah seperti berikut: Proses algoritma genetik bermula dengan penjanaan kromosom populasi awal secara rawak yang melahirkan sebilangan individu. Tahap kecergasan setiap individu kemudiannya dinilai untuk pemilihan baka yang berkualiti. Individu yang mempunyai tahap kecergasan yang tinggi selalunya terpilih untuk dijadikan induk. Kromosom induk kemudiannya akan bergabung untuk melahirkan generasi baru yang disebut anak. Proses penggabungan ini yang dinamakan sebagai proses penyilangan. Sebahagian kromosom anak mungkin mengalami mutasi yang memperlihatkan perbezaan ketara tahap kecergasannya berbanding dengan anak yang lain. Anak yang mempunyai tahap kecergasan yang rendah akan tersingkir sebelum generasi baru bermula. Anak yang mempunyai tahap kecergasan yang tinggi sebaliknya akan terus kekal dalam populasi dan mungkin akan dipilih untuk dijadikan induk bagi melahirkan generasi yang seterusnya. Contoh proses penyilangan dan mutasi Rajah 2.12 menunjukkan algoritma janaan subset dengan strategi carian berjujukan algoritma genetik. Penyilangan dan mutasi merupakan dua parameter penting dalam algoritma genetik. Rajah 2.13 menggambarkan contoh proses penyilangan dan mutasi. Merujuk kepada Rajah 2.13, proses penyilangan dilaksanakan menggunakan kaedah titik penyilangan tunggal dan proses mutasi dilaksanakan dengan menukar nilai individu.

Langkah 2: Nilai prestasi subset yang dijana menggunakan fungsi penilaian tertentu bagi membandingkan prestasi subset fitur, antaranya IG dan jarak Euclidean.

Langkah 3: Tetapan kriteria berhenti (stopping criterion). Beberapa cara yang boleh digunakan untuk menentukan kriteria berhenti. Antaranya adalah proses janaan dan penilaian subset ditamatkan apabila penambahan atau pengurangan fitur yang seterusnya tidak lagi menunjukkan peningkatan prestasi, bilang tertentu fitur telah dipilih atau bilangan tertentu proses janaan dan penilaian subset telah dilaksanakan (Bolón-Canedo 2015).

Langkah 4: Langkah terakhir adalah proses validasi subset fitur yang dipilih.

Dalam kaedah pemilihan fitur secara pembalut ini, langkah pertama iaitu jana subset merupakan antara elemen penting. Penerangan lanjut berkaitan strategi carian yang boleh digunakan bagi menjana subset dihuraikan dalam sub topik berikutnya.

Kaedah hibrid

Satu lagi kaedah pemilihan fitur yang sering digunakan adalah gabungan antara kaedah penapis dan pembalut iaitu dikenali sebagai kaedah hibrid. Kaedah hibrid diperkenalkan bagi memanfaatkan kelebihan yang ada pada kaedah penapis iaitu efisien dan ciri lazim kaedah pembalut iaitu ketepatan.

Dalam kaedah hibrid, pemilihan fitur dilaksanakan dalam dua peringkat.

Peringkat 1 - Kaedah penapis digunakan terlebih dahulu bagi mengurangkan dimensi fitur dengan memilih subset fitur.
Peringkat 2 - Proses pemilihan fitur dilaksanakan sekali lagi menggunakan kaedah pembalut terhadap subset fitur yang dipilih menerusi peringkat 1. Kombinasi mana-mana jenis penapis dan pembalut boleh digunakan untuk menghasilkan kaedah hibrid.

Rujukan

^ ^a ^b Huan Liu & Lei Yu. 2005. Toward integrating feature selection algorithms for classification and clustering. IEEE Transactions on Knowledge and Data Engineering, vol. 17, no. 4, pp. 491-502.
^ ^a ^b De Silva, A.M. & Leong. P.H.W. 2015. Grammar-based feature generation for time-series prediction. SpringerBriefs in Computational Intelligence.
^ Huan Liu & Lei Yu. 2005. Toward integrating feature selection algorithms for classification and clustering. IEEE Transactions on Knowledge and Data Engineering, vol. 17, no. 4, pp. 491-502.
^ Mejia-Lavalle, M., Sucar, E. & Arroyo, G. 2006. Feature selection with a perceptron neural net. In International Workshop on Feature Selection for Data Mining, pages 131–135.
^ ^a ^b Belanche, L. A., & González, F. F. 2011. Review and evaluation of feature selection algorithms in synthetic problems.
^ M. Dash & H. Liu. 1997. Feature selection for classification. Intelligent Data Analysis: An Int’l J., vol. 1, no. 3, pp. 131-156, 1997.
^ Li Zhuo, Jing Zheng, Fang Wang, Xia Li, Bin Ai and Junping Qian, et al. 2008. A genetic algorithm based wrapper feature selection method for classification of hyperspectral images using support vector machine.Geoinformatics 2008 and Joint Conference on GIS and Built Environment: Classification of Remote Sensing Images. International Society for Optics and Photonics, 2008.

[:0-1] Huan Liu & Lei Yu. 2005. Toward integrating feature selection algorithms for classification and clustering. IEEE Transactions on Knowledge and Data Engineering, vol. 17, no. 4, pp. 491-502.

[:1-2] De Silva, A.M. & Leong. P.H.W. 2015. Grammar-based feature generation for time-series prediction. SpringerBriefs in Computational Intelligence.

[3] Huan Liu & Lei Yu. 2005. Toward integrating feature selection algorithms for classification and clustering. IEEE Transactions on Knowledge and Data Engineering, vol. 17, no. 4, pp. 491-502.

[4] Mejia-Lavalle, M., Sucar, E. & Arroyo, G. 2006. Feature selection with a perceptron neural net. In International Workshop on Feature Selection for Data Mining, pages 131–135.

[:2-5] Belanche, L. A., & González, F. F. 2011. Review and evaluation of feature selection algorithms in synthetic problems.

[6] M. Dash & H. Liu. 1997. Feature selection for classification. Intelligent Data Analysis: An Int’l J., vol. 1, no. 3, pp. 131-156, 1997.

[7] Li Zhuo, Jing Zheng, Fang Wang, Xia Li, Bin Ai and Junping Qian, et al. 2008. A genetic algorithm based wrapper feature selection method for classification of hyperspectral images using support vector machine.Geoinformatics 2008 and Joint Conference on GIS and Built Environment: Classification of Remote Sensing Images. International Society for Optics and Photonics, 2008.

[1]

[2]

[3]

[4]

[5]

[6]

[7]