Page 1Neural Networks 24 (2011) 824-830 Daftar isi yang tersedia di SciVerse ScienceDirect Jaringan Syaraf homepage jurnal: www.elsevier.com/locate/neunet 2011 Edisi Khusus Algoritma LVQ dengan contoh pembobotan untuk generasi aturan berbasis prototipe Marcin Blachnik a, * , Włodzisław Duch b , c sebuah Departemen Manajemen dan Informatika, Silesian University of Technology, Katowice, Krasinskiego 8, Polandia b Jurusan Teknik Informatika, Universitas Nicolaus Copernicus, Polandia c Fakultas Ilmu Komputer, Nanyang Technological University, Singapura articleinfo Kata Kunci: Learning Vector Quantization Pengelompokan berbasis pengetahuan Aturan berbasis prototipe Metode berbasis Kesamaan abstrak Aturan Crisp dan fuzzy logic-digunakan untuk representasi dipahami data, namun aturan berdasarkan kesamaan dengan prototipe sama-sama berguna dan jauh lebih dikenal. Metode berbasis kesamaan milik pendekatan data mining yang paling akurat. Sekelompok besar metode tersebut didasarkan pada seleksi contoh dan optimasi, dengan Learning Vector Quantization (LVQ) algoritma menjadi contoh yang menonjol. Akurasi LVQ sangat tergantung pada inisialisasi yang tepat dari prototipe dan mekanisme optimasi. Makalah ini memperkenalkan prototipe inisialisasi berdasarkan konteks pengelompokan tergantung dan modifikasi fungsi biaya LVQ yang memanfaatkan informasi tambahan tentang distribusi tergantung kelas pelatihan vektor. Pendekatan ini diilustrasikan pada beberapa dataset patokan, menemukan model yang sederhana dan akurat data dalam bentuk aturan berbasis prototipe. © 2011 Elsevier Ltd.. 1. Perkenalan Salah satu masalah dengan aplikasi jaringan saraf di

situasi keamanan-kritis adalah '' black-box alam 'dari solusi. Penjelasan terbaik dari struktur data jelas tergantung pada masalah tertentu, pada standar yang biasa diterima di diberikan lapangan. Kebanyakan penelitian tentang struktur pemahaman data menggunakan saraf jaringan telah difokuskan pada penggalian aturan logika proposisional ( Duch, Adamczak, & Grabczewski, 2001; Duch, Setiono, & Zurada, 2004) , namun aturan tersebut, dalam bentuk renyah atau tidak jelas, tidak selalu Cara terbaik untuk memahami data. Kekuatan ekspresif renyah atau tidak jelas aturan (C-aturan dan F-aturan) memiliki keterbatasan yang serius. The '' Mayoritas suara 'konsep' diungkapkan oleh C-aturan atau F-aturan membutuhkan bilangan berpangkat kondisi, namun mudah diimplementasikan dalam umum, bentuk tertimbang oleh M-of-N aturan ambang batas, asalkan oleh perceptrons. Aturan berbasis prototipe menggunakan langkah-langkah yang canggih kesamaan yang mungkin menangkap beberapa bentuk intuitif evaluasi, seperti yang digunakan misalnya dalam diagnosa medis. Kategorisasi manusia dari benda-benda alam sebagian besar didasarkan pada menghafal banyak contoh, digantikan oleh prototipe yang memungkinkan generalisasi contoh-contoh ini ( Roth & Bruce, 1995 ). Dalam kehidupan nyata '' intuitif Pemahaman '' mencerminkan pengalaman ahli yang digunakan lebih sering daripada logika proposisional dan bekerja dengan baik dalam agak sederhana situasi dan dalam ilmu abstrak. Sementara literatur tentang aturan fuzzy sangat besar, P-aturan jauh kurang populer dan tampaknya ada beberapa prasangka terhadap mereka * Sesuai penulis. Alamat E-mail: marcin.blachnik@polsl.pl (M. Blachnik). comprehensibility. P-aturan dapat mewakili khas atau biasa kasus, meliputi banyak contoh, atau kasus-kasus tertentu yang dekat dengan de- perbatasan presisi, dengan fungsi kesamaan dengan hanya mereka-ciri membangun struktur yang penting untuk membuat diskriminasi lokal di sekitar setiap prototipe. Banyak argumen yang mendukung P-aturan sebagai com- dikupas ke-aturan C dan F-aturan telah diberikan di Blachnik dan Duch ( 2008 ) Dan Duch dan Grudziński ( 2001 ). Mereka termasuk lebih fleksibel perbatasan keputusan, kemampuan untuk menangani pengecualian dengan cara yang mudah, stabilitas set aturan, sehubungan dengan basis set ekspansi reg- Jaringan ularization ( Lowe, 1995; Poggio & Girosi, 1990 ), Vec- tor kuantisasi dan jaringan terorganisir diri ( Kohonen, 1984 ). P-aturan memberikan bentuk yang paling umum dari pengetahuan perwakilan tion: F-aturan yang setara dengan P-aturan dengan kesamaan dipisahkan metrik ( Duch & Blachnik 2004 ) Dan C-aturan adalah kasus khusus dari F-aturan dengan fungsi jarak Chebychev. P-aturan juga mungkin-wakil membenci M-of-N aturan dengan cara alami menggunakan prototipe ambang aturan main ( Blachnik & Duch 2006 ). Dua jenis umum P-aturan mungkin, dengan batas keputusan didasarkan baik pada pro- terdekat totypes, atau pada kesamaan ambang untuk prototipe yang diberikan. Untuk Misalnya, aturan prototipe ambang tunggal memberikan lebih 97,5% akurat

cabul pada terkenal Wisconsin Kanker Payudara (WBC) patokan dataset ( Grabczewski & Duch 2002 ), Memilih fitur penting untuk membedakan '' terburuk '' prototipe ganas dari menjadi- yang kasus nign. Ini adalah deskripsi sederhana dan paling akurat struktur data WBC ditemukan sejauh ini. Meskipun argumen ini aturan berbasis prototipe masih banyak kurang populer daripada bentuk lain dari aturan. Penggunaan prototipe berbasis sistem pemerintahan dengan fungsi linear untuk kontrol ( Tang & Lawry 2010 ) dapat menggunakan label linguistik tetapi hanya ekspansi basis set Teknik yang tidak menimbulkan gambaran dipahami dari 0893-6080 / $ - lihat hal depan © 2011 Elsevier Ltd.. doi: 10,1016 / j.neunet.2011.05.013

Halaman 2M. Blachnik, W. Duch / Neural Networks 24 (2011) 824-830 825 Data. Metode kesamaan Berbasis menawarkan kerangka kaya ( Duch, 2000; Duch, Adamczak, & Diercksen 2000 ) Untuk konstruksi metode tersebut. Banyak metode yang digunakan untuk analisis data dapat dengan mudah ditampung dalam kerangka kerja ini, termasuk saraf Jaringan ( Duch, Adamczak, & Diercksen 1999 ), Probabilistik dan metode Fuzzy ( Duch & Blachnik 2004 ), Kernel pendekatan dan banyak metode lain ( Pekalska & Duin 2005 ). Berbasis prototipe- Aturan juga termasuk golongan ini metode, khususnya bertujuan untuk mewakili pengetahuan yang tersembunyi dalam data dalam dipahami cara. Hal ini dicapai dengan pengurangan jumlah prototipe vektor (pemilihan prototipe), minimalisasi jumlah fitur yang digunakan untuk membuat model akhir, dan penggunaan sederhana metrik kesamaan. The Learning Vector Quantization (LVQ) algoritma biasanya disajikan dalam bentuk jaringan saraf, tetapi juga milik kerangka Metode Kesamaan Berbasis. Beberapa algoritma LVQ menjadi populer setelah penerbitan buku 'Kohonen yang' Self Organisasi dan asosiatif Memory '' ( Kohonen, 1984 ). Mereka adalah sederhana dan biasanya cukup akurat, dengan menggunakan aturan tetangga terdekat untuk klasifikasi. Model keputusan LVQ karena itu didasarkan pada kesamaan (atau perbedaan, yaitu jarak) ukuran antara tes objek dan referensi vektor, disebut vektor codebook (p saya s ), atau prototipe. Label output dari benda uji adalah sama dengan label dari codebook terdekat: k =

arg min saya s ( D ( x . p saya s )) C ( x ) ← C ( p k ) (1) di mana D (·, ·) adalah fungsi jarak. Alun-alun jarak D (·, ·) 2 juga dapat digunakan karena tidak mengubah jarak relatif pemesanan dan komputasi lebih efisien, x adalah benda uji, dan C (·) adalah indikator label atau kelas objek tertentu. Jarak atau tindakan kesamaan dapat digunakan dalam aturan keputusan, menggantikan arg min oleh max arg. Proses pembelajaran dari jaringan LVQ menentukan Posisi optimal prototipe. Untuk mencapai tujuan ini seseorang pertama ke: • mendefinisikan fungsi tujuan; • menentukan ukuran jarak yang tepat; • membangun algoritma optimasi; • memilih nomor optimal vektor codebook; • menentukan posisi awal vektor codebook untuk menghindari sub

solusi optimal. Banyak varian dari algoritma LVQ telah dibuat, tergantung pada solusi khusus untuk poin yang tercantum di atas. LVQ juga memiliki banyak aplikasi yang berbeda. Ini dapat menentukan posisi pusat fungsi basis radial di dasar radial function (RBF) pelatihan jaringan saraf ( Schwenker, Kestler, & Palm, 2001 ). Pusat-pusat fungsi dasar dioptimalkan oleh LVQ mencerminkan batas klasifikasi nyata, bukan hanya pengelompokan dari vektor input ditentukan dengan mengelompokkan metode. LVQ terhubung dalam banyak cara untuk kernel algoritma. Metode Kernel memiliki besar kemampuan generalisasi, tetapi juga memiliki beberapa kelemahan. Untuk dataset besar kompleksitas komputasi tinggi (sebanding dengan O ( n 2 ) untuk n sampel) berakhir dengan sejumlah besar potensial vektor dukungan. Beberapa solusi dari masalah ini ada ( Lee & Huang, 2007 ), Mengurangi jumlah vektor dukungan ketika mencoba untuk melestarikan batas keputusan asli. Meskipun reformulasi fungsi tujuan untuk pelatihan SVM adalah mungkin, lebih sederhana solusi didasarkan pada pengelompokan atau LVQ algoritma untuk seleksi calon yang baik untuk vektor dukungan ( Blachnik & Duch 2008 ). Pendekatan LVQ dapat digunakan sebagai model untuk pelatihan neuro model fuzzy. Hal ini tidak sulit untuk menunjukkan ( Kuncheva, 1996 ) Bahwa Jaringan syaraf LVQ setara dengan Takagi-Sugeno Fuzzy-aturan sistem berbasis operator agregasi didefinisikan sebagai max (·) . LVQ jaringan juga telah diterapkan untuk preprocessing gambar. A representasi umum dari sifat gambar didasarkan pada histogram fitur, berasal dari patch sampling gambar dan Binning intensitas, warna, tekstur, ujung-orientasi dan fitur lainnya. Itu paling umum metode yang digunakan untuk menentukan sampel yang relevan berdasarkan clustering, tapi LVQ optimalisasi vektor codebook Hasil diskriminasi jauh lebih tinggi dari gambar berdasarkan mereka histogram ( Blachnik & Laaksonen 2008 ). Beragam berbagai aplikasi yang disebutkan di atas menunjukkan universalitas Pendekatan LVQ. Konsep aturan berbasis prototipe telah diusulkan dalam Duch dan Grudziński ( 2001 ). Setelah pemilihan satu set kecil vektor referensi p saya s aturan tetangga terdekat digunakan untuk menghubungkan mereka dengan label kelas atau informasi keluaran lainnya:

jika p = argmin p ' ∈ P D ( x . p ' ) maka y = C ( p ). (2) Dalam bentuk yang lebih umum aturan fuzzy terkait dengan setiap proto jenis, dan operator agregasi digunakan untuk menentukan de- akhir keputusannya. Fungsi jarak diganti dengan estimasi kesamaan (Misalnya aktivasi node Gaussian yang menghitung jarak S ( x . p ) = exp - D ( x . p ) 2 ) Memperkirakan kesamaan antara vec- yang tor x dan p prototipe dalam arti kabur. Anggota masing-masing pasangan - prototipe dan label kelas yang sesuai - terkait dengan masing-masing lain dengan aturan kabur tunggal: (

1 ) jika x p 1 maka y 1 C ( p 1 ) ( 2 ) jika x p 1 maka y 2 C ( p 2 ) ··· (V) jika x p v maka y v C ( p v ) di mana menunjukkan '' ini mirip dengan '' operasi hanya dihitung sebagai S ( x . p ) . Operator agregasi dapat menerapkan fungsi max

tion yang mengarah ke model prototipe terdekat atau fungsi Softmax, menjumlahkan aktivitas semua node yang berhubungan dengan kelas tertentu dan membaginya atas aktivitas total, tetapi ada banyak pilihan lain ( Kuncheva, 2004 ). Tujuan utama dari pendekatan semacam itu melampaui sekedar klasifikasi atau pendekatan (y ( x ; p ) = C ( p ) dapat digunakan untuk pendekatan lokal). Menemukan prototipe terdekat berguna dalam banyak cara ( Duch et al., 2000 ), Memberikan informasi untuk kasus- penalaran berbasis ( Rissland, 2006 ). Misalnya, dalam hukum, medis atau diagnosa mesin mengambil kasus yang paling mirip dapat memberikan Informasi lebih dari diagnosis hanya sederhana atau prediksi dari hasil yang diharapkan. Comprehensibility sistem P-aturan tergantung pada penurunan yang signifikan dari jumlah referensi kasus dengan algoritma LVQ. Langkah-langkah kesamaan canggih mungkin menangkap evaluasi intuitif ahli yang bisa sulit untuk menjelaskan dalam bentuk aturan proporsional. Keakuratan pengklasifikasi lemah ditingkatkan kuat menggunakan teknik meningkatkan ( Schapire & Singer, 1999 ) Yang memperkenalkan bobot untuk kasus pelatihan. Ini adalah relatif belum diselidiki aspek dari algoritma LVQ. Bobot yang tepat dapat membimbing optimalisasi posisi codebook, mengurangi pengaruh outlier dengan meningkatkan pentingnya contoh dekat dengan perbatasan. Bagian selanjutnya didedikasikan untuk masalah codebook inisialisasi vektor, termasuk penggunaan tergantung konteks clustering. Dalam Bagian 3 beberapa modifikasi dari fungsi biaya LVQ diperkenalkan, Bagian 4 dikhususkan untuk masalah misalnya pembobotan, dan dalam Bagian 5 jaringan LVQ tertimbang dibandingkan dengan pendekatan LVQ standar pada beberapa dataset. Final Bagian 6 berisi diskusi singkat. 2. Inisialisasi vektor codebook LVQ Semua model jaringan saraf memerlukan inisialisasi jaringan parameter. Pendekatan LVQ membutuhkan spesifikasi awal

Halaman 3826 M. Blachnik, W. Duch / Neural Networks 24 (2011) 824-830

posisi codebook dalam ruang fitur. Untuk mengatasi masalah ini banyak solusi yang berbeda telah diusulkan. Pilihan acak dari buku kode dari set contoh pelatihan tidak efisien, mengarah ke varians dan rendah akurasi besar model setelah pelatihan. Beberapa metode yang digunakan untuk mengurangi jumlah referensi vektor dalam algoritma kNN dapat digunakan untuk codebook inisialisasi. Algoritma seleksi yang bekerja dalam mode top-down meliputi: • Diedit Tetangga terdekat (ENN) ( Wilson, 1972 ) Algoritma yang menghapus dari contoh training set yang salah diklasifikasikan oleh kNN untuk k ≥ 3; • DROP3 ( Wilson & Martinez, 2000 ) Menghapus contoh x dari training set jika tidak mengubah klasifikasi kasus yang x adalah salah satu k tetangga terdekat; • Iteratif Kasus Filtering (ICF) ( Brighton & Mellish 2002 ) Mulai dari DROP3 dan menciptakan hyperspheres dengan contoh dari kelas tunggal. Lain algoritma pemilihan contoh meliputi: • Bottom-up kental Neighbor aturan terdekat (CNN) ( Hart, 1968 ) dimulai dengan satu vektor per kelas, dan menambahkan contoh pelatihan yang yang salah diklasifikasikan oleh referensi set saat ini. • Gabriel Editing (GE) algoritma berbasis grafik ( Bhattacharya, Mukherjee, & Toussaint, 2005 ) Menggunakan grafik Gabriel untuk menghapus dari dataset training semua contoh dari kelas yang sama seperti semua tetangga mereka, hanya menyisakan contoh-contoh yang mendefinisikan batas keputusan antara kelas yang berbeda. • Algoritma memperkirakan probabilitas kepadatan, seperti Diedit Normalized RBF (NRBF) ( Jankowski & Grochowski 2004 ) Kembali bergerak contoh x konsisten dengan kepadatan probabilitas estima- tion sekitar titik x. Untuk kajian mendalam dari algoritma ini melihat ( Grochowski & Jankowski, 2004 ; Jankowski & Grochowski 2004 ; Wilson & Martinez, 2000 ). Metode inisialisasi codebook berdasarkan pengelompokan memiliki kompleksitas komputasi yang lebih rendah dibandingkan dengan metode seleksi contoh, namun mereka biasanya kurang akurat. Untuk meningkatkan konteks akurasi pengelompokan terikat adalah digunakan sebagai pengganti algoritma klasterisasi klasik. Algoritma tersebut dipandu oleh misalnya bobot yang memberikan pengaruh lokal di

Proses pengelompokan di area yang diinginkan. Dalam masalah klasifikasi harus fokus pada deskripsi yang tepat dari perbatasan kelas daerah, dikombinasikan dengan aturan berbasis prototipe umum yang mencakup cluster besar data kelas murni. Konteks pengelompokan tergantung menggunakan informasi konteks untuk memandu proses clustering. Dalam konteks kasus yang paling sederhana digambarkan oleh variabel eksternal yang memperkirakan pentingnya masing-masing vektor digambarkan oleh sebuah contoh berat. Bersyarat Fuzzy C-Means (CFCM) ( Pedrycz, 2005 ) Adalah perluasan dari pengelompokan FCM algoritma, dengan variabel tambahan y, ditetapkan untuk setiap vektor x, yang membantu untuk cluster data terkait. Untuk setiap vektor x saya s kekuatan hubungan dengan variabel y eksternal saya s didefinisikan oleh fungsi f saya s = Μ A ( y ) ∈ [ 0 . 1 ] , Di mana μ A ( y ) ditafsirkan sebagai keanggotaan Fungsi untuk beberapa himpunan fuzzy A, atau hanya sebagai pemberat yang menciptakan Kondisi pengelompokan dalam konteks A. FCM dan CFCM didasarkan pada minimalisasi fungsi biaya didefinisikan sebagai: J m ( U . V ) = v

- k = 1 n - saya s = 1 ( u ki ) m ‖ x saya s - p k ‖ 2 A (3) di mana v adalah jumlah cluster yang berpusat di p k (Pusat tersebut akan digunakan sebagai vektor referensi atau classifier LVQ), n adalah nomor vektor, m > 1 menentukan pengelompokan ketidakjelasan, dan U = ( u ki ) adalah v × n keanggotaan dimensi matriks dengan elemen u ki ∈ [ 0 . 1

] mendefinisikan derajat keanggotaan vektor x saya s dalam cluster p k . Matriks U harus memenuhi tiga syarat: 1 ◦ setiap vektor x saya s adalah anggota dari k th cluster untuk gelar antara 0 dan 1: u ki ∈ [ 0 . 1 ]; k = 1 , ..., V; saya s = 1 , ..., n (4) 2 ◦ jumlah nilai keanggotaan saya th vektor x saya s di semua kelompok adalah sama dengan f saya s v - k = 1 u ki = f

saya s ; saya s = 1 , ..., n (5) 3 ◦ cluster yang tidak kosong, dan satu cluster tidak mencakup seluruh ruang: n - saya s = 1 u ki ∈ ( 0 . n ); k = 1 , ..., V. (6) Pusat cluster dihitung sebagai: p k = n - saya s = 1 ( u ki ) m x saya s

n - saya s = 1 ( u ki ) m ; k = 1 , ..., V. (7) Matriks partisi kemudian dihitung dengan menggunakan pusat-pusat cluster, dan fungsi biaya (3) diminimalkan iteratif: u ki = f saya s C - k = 1 ‖ x saya s - p k ‖ ‖ x saya s - p k ‖ 2 / (

m - 1 ) ; saya s = 1 , ..., n ; k = 1 , ..., V. (8) 3. Memperkenalkan konteks algoritma LVQ Fungsi biaya algoritma LVQ1 dasar didefinisikan sebagai: E ( P ) = 1 2 v - k = 1 n - saya s = 1 1 ( x saya s ∈ R k ) 1 (

C ( x saya s ) = C ( p k )) ‖ x saya s - p k ‖ 2 - 1 2 v - k = 1 n - saya s = 1 1 ( x saya s ∈ R k ) 1 ( C ( x saya s ) ̸ = C

( p k )) ‖ x saya s - p k ‖ 2 (9) di mana 1 ( L ) adalah fungsi switching, ia mengembalikan 1 ketika kondisi L adalah benar, dan 0 sebaliknya. C ( x ) kembali label kelas vektor x, dan R k adalah daerah Voronoi ditetapkan untuk prototipe p k . Hubungan ini bisa juga diartikan sebagai x saya s ∈ R k jika p k = argmin l = 1 , ..., V ( D ( x saya s .

p l )) . Biaya ini Fungsi diminimalkan sehubungan dengan posisi semua prototipe P. Menentukan turunan dari fungsi biaya mengarah ke dua rumus yang mewakili pembaruan berulang prototipe Posisi: p k = p k + Α ( j ) 1 ( C ( x saya s ) = C ( p k )) ( x saya s - p k ) p k = p k - Α ( j ) 1 ( C (

x saya s ) ̸ = C ( p k )) ( x saya s - p k ) (10) di mana α ( j ) ∈ [ 0 . 1 ] adalah monoton menurun langkah ukuran fungsi tion dan j adalah jumlah iterasi. Dalam algoritma LVQ asli hanya informasi lokal diambil memperhitungkan, oleh karena itu sangat sensitif terhadap kehadiran outlier. Pengaruh outlier dapat dikurangi dengan mendefinisikan Misalnya beban dengan cara yang sama seperti dalam konteks tergantung clustering. F ( x saya s ) Faktor harus memasukkan informasi tentang distribusi keseluruhan vektor dari kelas yang berbeda, memberikan outlier dan vektor yang jauh dari perbatasan keputusan kurang berpengaruh pada nilai fungsi biaya. Faktor-faktor ini diperhitungkan melalui reformulasi fungsi tujuan:

Page 4M. Blachnik, W. Duch / Neural Networks 24 (2011) 824-830 827 E ( P

) = 1 2 v - k = 1 n - saya s = 1 1 ( x saya s ∈ R k ) 1 ( C ( x saya s ) = C ( p k )) f ( x saya s ) ‖ x saya s - p k ‖ 2

- 1 2 v - k = 1 n - saya s = 1 1 ( x saya s ∈ R k ) × 1 ( C ( x saya s ) ̸ = C ( p k )) f ( x saya s ) ‖ x saya s - p k ‖ 2

. (11) Fungsi biaya dapat diminimalkan dengan memodifikasi rumus (10) untuk penyesuaian prototipe: p k = p k + Α ( j ) f ( x saya s ) 1 ( C ( x saya s ) = C ( p k )) ( x saya s - p k ) p k = p k - Α ( j ) f ( x

saya s ) 1 ( C ( x saya s ) ̸ = C ( p k )) ( x saya s - p k ) (12) di mana konteks faktor f ( x saya s ) menggambarkan tergantung kelas- distribusi vektor sekitar x saya s . F ( x saya s ) Nilai juga bisa dipahami sebagai sebuah contoh berat menggambarkan pentingnya bahwa contoh selama proses pelatihan. Sketsa algoritma LVQ tertimbang (WLVQ) disajikan di Algoritma 1. Karena bobot dihitung hanya pada mulai, kompleksitas komputasi algoritma baru adalah jumlah kompleksitas bagian perhitungan berat badan, dan dasar LVQ algoritma O ( n · V · z

) , Di mana z adalah jumlah iterasi, biasanya tidak melebihi jumlah sampel. Algoritma Algoritma 1 WLVQ Membutuhkan: T, P, α , Z w ← determine_instance_weights ( T ) n ← instances_of ( T ) ; v ← instances_of ( P ) ; untuk k = 1 ... z lakukan untuk i = 1 ... n lakukan untuk j = 1 ... V melakukan d j ← D

T saya s . P j end untuk saya s ← arg min j = 1 , ..., V d j jika C ( T saya s ) == C ( P saya s ) kemudian P saya s = P saya s + Α · w saya s · ( T saya s - P saya s ) lain P

saya s = P saya s - Α · w saya s · ( T saya s - P saya s ) akhir jika end untuk α = α / ( 1 + Α) end untuk kembali P 4. Menentukan bobot contoh Mendefinisikan contoh bobot yang tepat akan membantu untuk menemukan jumlah minimum prototipe LVQ menyediakan sederhana namun Model akurat data. Mesin dukungan vektor bekerja dengan baik karena mereka fokus pada daerah perbatasan, memberikan hyperplanes dengan margin lebar dan mendefinisikan batas keputusan yang tajam. Vektor dukungan dalam tindakan ruang kernel sebagai prototipe p saya s , Dengan kernel nilai K ( x . p saya s ) melayani sebagai jarak tertimbang dari prototipe tersebut. Sehubungan Dengan Itu bobot contoh pelatihan harus menekankan pentingnya daerah perbatasan. Ada banyak solusi yang berbeda yang dapat digunakan untuk tujuan itu, dan dalam prakteknya classifier apapun dapat digunakan untuk mengidentifikasi bobot contoh. Di sini kita akan menyelidiki menggunakan dua algoritma pembobotan, yang didasarkan pada inter-intra kelas fungsi kesamaan, dan satu lagi untuk menggunakan Diedit terdekat Aturan Tetangga algoritma seleksi (ENN) misalnya. 4.1. Konteks antar-intra kelas kesamaan berdasarkan Untuk mendorong pilihan prototipe yang terletak dekat dengan

perbatasan keputusan, misalnya bobot didefinisikan dengan bantuan koefisien w k menggambarkan distribusi posisi vektor sekitar x k dalam yang sama, dan relatif ke kelas-kelas lain. Ini adalah didefinisikan oleh rasio dalam waktu kelas pencar untuk out-of-kelas pencar: w saya s = W ( x saya s ) = ( n - n c ) n c Σ j . C ( x saya s ) = C ( x j ) x saya s - x j 2

Σ j . C ( x saya s ) ̸ = C ( x j ) x saya s - x j 2 . (13) Berikut C ( x saya s ) menunjukkan label kelas dari vektor x saya s , Dengan n c vektor di kelas ini. Normalisasi w saya s koefisien (berada di jarak [ 0 ··· 1 ] ) Mencapai nilai-nilai yang mendekati 0 untuk vektor dalam kelompok homogen besar, dan dekat dengan 1 jika vektor x

saya s aku s dekat vektor kelas yang berlawanan dan jauh dari vektor lainnya dari kelas yang sama (misalnya, jika itu adalah outlier). Untuk menghindari seperti situasi berat harus berpusat di sekitar μ ∈ [ 0 . 6 . 1 ] , Dengan Distribusi Gaussian mendefinisikan faktor konteks: f saya s = f ( x saya s ) = exp -γ (w ( x saya s ) - Μ) 2 . (14) Nilai γ ∈ [ 0 . 4 . 0 . 8 ] dianjurkan, ditentukan empirik dihabiskan untuk berbagai dataset. Itu μ Parameter mana prototipe akan ditempatkan; untuk kecil

μ mereka lebih dekat dengan pusat cluster dan untuk yang lebih besar μ lebih dekat ke perbatasan keputusan. Kisaran di mana mereka dicari ditentukan oleh γ -parameter eter. Karena algoritma ini membutuhkan perhitungan jarak antara semua kasus kompleksitas komputasi adalah kuadrat jumlah sampel O n 2 . Fungsi ini digunakan untuk menentukan konteks pengelompokan untuk pengelompokan CFCM di LVQ tertimbang Algoritma (WLVQ). 4.2. Konteks berbasis ENN The Diedit terdekat Tetangga (ENN) Aturan ini didasarkan pada meninggalkan satu tes keluar. Dalam algoritma asli semua vektor yang salah diklasifikasikan oleh classifier kNN (k ≥ 3) ditandai untuk penghapusan. Kami telah digunakan di sini versi modifikasi dari pendekatan ini diadopsi untuk menentukan bobot contoh. Versi modifikasi ini tidak tidak menghapus kasus apapun, melainkan kepercayaan prediksi adalah digunakan sebagai contoh berat badan. Diagram dari program ini ditampilkan di Algoritma 2, di mana T menunjukkan training set, dan con (·) aku s kepercayaan kelas diprediksi, sama dengan fraksi k tetangga yang termasuk ke dalam kelas mayoritas C ( x saya s ) . Seperti pada sebelumnya metode bobot w saya s harus berpusat di sekitar μ dengan Gaussian distribusi. Algoritma 2 Modifikasi algoritma ENN

Membutuhkan: T . k n ← instances_of ( T ) ; w saya s ← 0; untuk i = 1 ... n lakukan C ( x saya s ) = kNN ({ T \ x saya s }, x saya s ) ; w saya s = con ( C ( x saya s )); end untuk

untuk i = 1 ... n lakukan f saya s = exp -γ (w saya s - Μ) 2 end untuk kembali f Algoritma ENN dapat digunakan untuk codebook simultan inisiasi tialization dan contoh pembobotan untuk pelatihan LVQ. Sayangnya bobot ditentukan oleh algoritma ini biasanya sensitif terhadap keluar- liers. Serupa dengan prosedur pembobotan dijelaskan dalam sebelumnya

Halaman 5828 M. Blachnik, W. Duch / Neural Networks 24 (2011) 824-830 Gambar. 1. Data flow diagram. Bagian algoritma ini juga memerlukan perhitungan jarak menjadi- tween semua contoh, sehingga kompleksitas komputasi adalah pesanan O n 2 . 5. Perhitungan Ilustrasi Dalam rangka untuk menyelidiki sifat dari algoritma yang dijelaskan dalam bagian sebelumnya, beberapa tes telah dilakukan pada tujuh ukur mark dataset yang diambil dari gudang UCI ( Asuncion & New- man, 2007 ) (Sonar, Wisconsin Kanker Payudara (WBC), Spambase, Diabetes (Pima Indian), penyakit jantung (Cleveland), Ionosfer dan Apendisitis). Tiga dataset dibahas secara rinci: Sonar, WBC, Spambase, dan hasil terbaik untuk sisa empat ditunjukkan pada Tabel 2. Tabel 3 juga menunjukkan perbandingan dengan lainnya algoritma mesin pembelajaran populer seperti pohon keputusan C4.5, dan SVM dengan linear dan kernel Gaussian. Beberapa Karakteristik dasar tics dataset ini disediakan di Tabel 1 .

Semua percobaan telah dilakukan dengan cara yang sama menggunakan 10 kali lipat prosedur cross-validasi, dengan semua algoritma tertanam dalam crossvalidation lipatan untuk mencapai berisi estimasi kesalahan generalisasi. Diagram menyajikan data aliran dalam percobaan komputasi disajikan di Gambar. 1 . Di eksperimen ini akurasi terdekat-prototipe classifier dengan prototipe yang diperoleh dari algoritma LVQ klasik telah dibandingkan dengan yang didasarkan pada prototipe dioptimalkan menggunakan algoritma WLVQ. Dalam kedua kasus prototipe / buku kode yang diinisialisasi dengan menggunakan algoritma pengelompokan CFCM. Salib Proses validasi telah diulang dua kali, akibatnya deviasi standar akurasi dan telah dihitung dari 20 hasil yang berbeda. Dalam kasus algoritma WLVQ, nilai-nilai optimal dari γ dan μ dipilih dengan menggunakan algoritma pencarian serakah, untuk Inte-Intra kelas metode kesamaan dari nilai-nilai γ = [ 0 . 3 . 0 . 6 . 0 . 9 ] dan nilai-nilai μ = [ 0 . 4 . 0 . 6 . 0 . 8 .

1 ] , Dan untuk metode ENN dari nilai-nilai γ = [ 0 . 4 . 0 . 6 . 0 . 8 ] dan 4 nilai μ = [ 0 . 0 . 1 . 0 . 2 . 0 . 3 ] . Jumlah tetangga terdekat dalam algoritma ENN ditetapkan untuk k = 10. Hasil disajikan dalam Gambar. 2-4 . Setiap grafik menunjukkan rata-rata akurasi dan varians sebagai fungsi dari nomor yang dipilih prototipe per kelas. Dalam semua plot garis tipis yang solid merupakan akurasi algoritma referensi LVQ dan garis putus-putus tebal merupakan rata-rata akurasi yang diperoleh dengan algoritma WLVQ untuk bobot ditentukan oleh kedua jenis algoritma. Untuk Sonar dataset perbedaan yang signifikan antara algoritma tertimbang dan non-tertimbang hilang untuk lebih tinggi jumlah prototipe per kelas (#codebooks

≥ 9). Untuk kedua fungsi pembobotan peningkatan akurasi lebih dari 10% untuk sejumlah kecil prototipe. Solusi ini memberikan yang paling berharga P-aturan, dan dengan demikian penting untuk memaksimalkan akurasi. Menggunakan hanya 1 prototipe per kelas menambahkan akurasi sekitar 13%, namun masih lebih buruk pada sekitar 7% dibandingkan dengan hasil satu tetangga terdekat classifier 2 . Untuk dataset WBC kedua fungsi pembobotan berperilaku hampir identik. Satu prototipe per kelas optimal, dengan ENN bobot Gambar. 2. Hasil untuk data Sonar. Gambar. 3. Hasil untuk data Kanker Payudara WBC. memungkinkan untuk kecil (statistik tidak signifikan) perbaikan akurasi. Menambahkan prototipe tidak membenarkan meningkat kompleksitas model. Akurasi rata tertimbang dari versi selalu lebih tinggi maka itu dari algoritma LVQ murni, tetapi perbedaan ini agak kecil. Perbedaan yang paling signifikan telah diperoleh untuk terbesar dataset ini, data Spam. Untuk dataset ini baik tertimbang versi dari algoritma LVQ bekerja lebih baik daripada standar LVQ, dan tiga prototipe per kelas gain statistik signifikan, lebih dari 4%. Meskipun penuh 1-NN masih lebih baik sekitar 3%, yang signifikan, pengurangan besar dalam kompleksitas telah dicapai pada data yang agak sulit. Perbandingan semua hasil dilaporkan di sini disajikan dalam Tabel 2 .

Halaman 6M. Blachnik, W. Duch / Neural Networks 24 (2011) 824-830 829 Tabel 1 Ringkasan dataset yang digunakan dalam percobaan. Judul #Fitur #Samples #Samples Per kelas Sumber Sonar 60 208 111 / 97 Asuncion dan Newman ( 2007 ) WBC 9 683

444 / 239 Asuncion dan Newman ( 2007 ) Spambase 57 4601 1813 / 2788 Asuncion dan Newman ( 2007 ) Diabetes Indian Pima 8 758 500 / 268 Asuncion dan Newman ( 2007 ) Cleveland 13 297 160 / 137 Asuncion dan Newman ( 2007 ) Ionosfir 33 351 225 / 126 Asuncion dan Newman ( 2007 ) Radang usus buntu 7 106 85 / 21 Shalom Weiss Gambar. 4. Hasil untuk data Spam. 6. Kesimpulan Deskripsi sederhana struktur data biasanya berusaha menggunakan klasik atau tidak jelas aturan logika ( Duch et al., 2004 ). Aturan Main yang dipahami jika jumlah mereka kecil dan kondisi sederhana. Aturan berbasis prototipe memberikan penjelasan alternatif data yang mungkin lebih sederhana dan lebih intuitif daripada proposisional

aturan main. Salah satu metode untuk menghasilkan yang baik P-aturan didasarkan pada algoritma LVQ. Sebuah prototipe tunggal dengan keputusan ambang Aturan dapat bekerja dengan baik untuk data yang memiliki sekitar Gaussian distribusi sampel (misalnya, pada Payudara Wisconsin Dataset kanker patokan Grabczewski & Duch 2002 ), Yang membutuhkan prototipe yang mewakili baik khas atau kasus ekstrim di masing-masing kelas. Dalam metode diskriminasi situasi linear seperti juga akan bekerja cukup baik. Namun, dalam kasus yang lebih kompleks, ketika metode kernel nonlinier menunjukkan keunggulan mereka, lebih prototipe terkonsentrasi di sekitar daerah perbatasan diperlukan. Metode Kernel cenderung menggunakan banyak vektor dukungan sepanjang perbatasan keputusan sebagai referensi, secara implisit memberikan baru kernel-space fitur z saya s ( x ) = K ( x . p saya s ) bahwa '' meratakan '' batas keputusan ( Maszczyk & Duch, 2010 ). Hyperplanes di ruang ini memberikan diskriminasi baik dari data, tetapi interpretasi hasil menjadi sulit karena data Model menjadi agak rumit. Dalam makalah ini perbaikan dari algoritma LVQ berdasarkan Misalnya bobot telah diusulkan. Tujuannya adalah untuk mengurangi kompleksitas Model tanpa kehilangan akurasi. Tergantung konteks pengelompokan telah diterapkan untuk inisialisasi prototipe LVQ, dengan dua algoritma pembobotan yang digunakan untuk pelatihan: yang didasarkan pada kelas kesamaan antar-intra, dan satu lagi berdasarkan Diedit Aturan Tetangga algoritma seleksi contoh terdekat. Hasil menunjukkan kombinasi ini dapat menciptakan solusi sederhana dengan relatif sejumlah kecil prototipe yang terletak dekat perbatasan. Dalam kasus ini Sonar data dengan bobot antar-intra hanya dua prototip per kelas yang cukup, sedangkan untuk WBC dan Spam Data ENN memberikan lebih deskripsi komprehensif. Tabel 2 Perbandingan akurasi rata-rata dan jumlah vektor prototipe untuk 6 terdekat algoritma berbasis tetangga. Dataset Model Ketepatan #Refs.

Sonar 1NN 87 ± 6.8 208 ENN + 1NN 81,2 ± 6.5 174 CNN + 1NN 85,8 ± 8.5 63 WLVQ (inter-intra) 81,7 ± 3.9 2 WLVQ (ENN) 81,7 ± 5.1 2 LVQ 82,2 ± 5.0 20 WBC 1NN 95,9 ± 1.8 683 ENN + 1NN 96,9 ±

1.9 661 CNN + 1NN 94,7 ± 2.1 67 WLVQ (inter-intra) 97,2 ± 1.2 2 WLVQ (ENN) 97,4 ± 1.3 4 LVQ 96,0 ± 2 10 Spam 1NN 89 ± 1.3 4600 ENN + 1NN 90,3 ± 1.9 4165 CNN + 1NN 88,4 ± 1.5 1055 WLVQ (inter-intra) 87.6

± 1.6 12 WLVQ (ENN) 88,0 ± 1.2 6 LVQ 86,9 ± 2.0 8 Pima Indian 1NN 66,3 ± 4.9 268 ENN + 1NN 76.2.2 ± 5.2 4165 CNN + 1NN 66,3 ± 5.0 334 WLVQ (inter-intra) 77,7 ± 4.2 2 WLVQ (ENN) 77,4 ± 4.3 4 LVQ 75.0 ±

2.7 2 Cleveland 1NN 75,1 ± 10.6 297 ENN + 1NN 81,2 ± 7.7 4165 CNN + 1NN 75,1 ± 10.6 104 WLVQ (inter-intra) 83.2.6 ± 4.3 2 WLVQ (ENN) 83.2 ± 4.3 2 LVQ 82,8 ± 3.7 4 Ionosfir 1NN 86,6 ± 4.9 351 ENN + 1NN

84,9 ± 3.8 4165 CNN + 1NN 86,6 ± 4.9 67 WLVQ (inter-intra) 89,2 ± 2.0 4 WLVQ (ENN) 89,2 ± 2.3 4 LVQ 87,2 ± 3.1 4 Radang usus buntu 1NN 75,5 ± 10.2 106 ENN + 1NN 88,7 ± 7.35 4165 CNN + 1NN 75,5 ± 10.2 31

WLVQ (inter-intra) 88,7 ± 8.4 2 WLVQ (ENN) 88,7 ± 8.4 2 LVQ 87,8 ± 7.8 2 Tabel 3 Perbandingan akurasi rata-rata selama 3 algoritma tidak didasarkan pada aturan tetangga terdekat. Dataset C.45 SVM-RBF SVM-linear Sonar 71.2 ± 7.1 90,39 ± 5.1 77,8 ± 8.4 WBC 94,6 ± 3.6 97,21 ± 1.1 96,9 ± 2.1 Spam 92,9 ± 1.2

93,6 ± 0,9 92,9 ± 0,6 Kencing Manis 73,8 ± 5.7 77,9 ± 2.4 76,8 ± 4.0 Cleveland 77,8 ± 8.8 84,15 ± 3.4 83,8 ± 6.3 Ionosfir 91,5 ± 3.3 95,45 ± 2.0 89,5 ± 4.0 Radang usus buntu 86.1 ± 11.9 87,7 ± 4.2 88,6 ± 5.9

Untuk data dimensi tinggi, pemilihan contoh harus dilengkapi dengan pilihan fitur yang digunakan oleh LVQ yang

Halaman 7830 M. Blachnik, W. Duch / Neural Networks 24 (2011) 824-830 metrik kesamaan, dan ini dilakukan dengan cara yang elegan menggunakan estimasi relevansi adaptif ( Schneider, Hammer, & Biehl 2009 ). LVQ tertimbang juga dapat digunakan dengan SVM kernel pendekatan mengurangi jumlah vektor dukungan. PCA umumnya digunakan untuk pengurangan dimensi, namun kombinasi linear dari futures mungkin tidak memberikan informasi sebanyak fitur berdasarkan jarak. Kunci keberhasilan metode kernel terletak pada penciptaan ruang fitur berdasarkan jarak ke prototipe. Fitur tambahan sangat meningkatkan informasi yang tersedia dalam ruang fitur, memungkinkan untuk pembangunan model sederhana berdasarkan linear diskriminasi dan teknik lain ( Maszczyk & Duch, 2010 ). Saya T telah mengemukakan bahwa metode kernel mungkin berguna dalam pemodelan kategori manusia belajar dalam ilmu kognitif ( Jäkel, Schölkopf, & Wichmann 2009 ), Namun aturan berbasis prototipe tampaknya memberikan penjelasan yang lebih masuk akal melestarikan keuntungan penting dari metode kernel.