Minggu, 29 Mar 2015

Saat ini, ada banyak tugas di mana diperlukan untuk membuat beberapa keputusan tergantung pada keberadaan objek dalam gambar atau untuk mengklasifikasikannya. Kemampuan untuk "mengenali" dianggap sebagai properti utama makhluk biologis, sementara sistem komputer tidak sepenuhnya memiliki properti ini.

Pertimbangkan elemen umum dari model klasifikasi.

Kelas- satu set objek yang memiliki sifat umum. Untuk objek dari kelas yang sama, kehadiran "kesamaan" diasumsikan. Untuk tugas pengenalan, jumlah kelas yang sewenang-wenang dapat ditentukan, lebih dari 1. Jumlah kelas dilambangkan dengan angka S. Setiap kelas memiliki label pengidentifikasi kelasnya sendiri.

Klasifikasi- proses pemberian label kelas ke objek, menurut beberapa deskripsi properti objek ini. Classifier adalah perangkat yang menerima sekumpulan fitur dari suatu objek sebagai input dan menghasilkan label kelas sebagai hasilnya.

Verifikasi- proses mencocokkan instance objek dengan model objek tunggal atau deskripsi kelas.

Di bawah jalan kita akan memahami nama area di ruang atribut, di mana banyak objek atau fenomena dunia material ditampilkan. tanda- deskripsi kuantitatif dari properti tertentu dari objek atau fenomena yang diteliti.

ruang fitur ini adalah ruang dimensi-N yang ditentukan untuk tugas pengenalan yang diberikan, di mana N adalah sejumlah fitur terukur yang tetap untuk objek apa pun. Vektor dari ruang fitur x yang sesuai dengan objek masalah pengenalan adalah vektor berdimensi-N dengan komponen (x_1,x_2,…,x_N), yang merupakan nilai fitur untuk objek yang diberikan.

Dengan kata lain, pengenalan pola dapat didefinisikan sebagai penugasan data awal ke kelas tertentu dengan mengekstraksi fitur atau properti penting yang mencirikan data ini dari massa umum detail yang tidak relevan.

Contoh masalah klasifikasi adalah:

• pengenalan karakter;
• pengenalan suara;
• menegakkan diagnosis medis;
• Prakiraan Cuaca;
• pengenalan wajah
• klasifikasi dokumen, dll.

Paling sering, bahan sumbernya adalah gambar yang diterima dari kamera. Tugas dapat dirumuskan sebagai mendapatkan vektor fitur untuk setiap kelas dalam gambar yang dipertimbangkan. Proses tersebut dapat dilihat sebagai proses pengkodean, yang terdiri dari pemberian nilai untuk setiap fitur dari ruang fitur untuk setiap kelas.

Jika kita mempertimbangkan 2 kelas objek: dewasa dan anak-anak. Sebagai fitur, Anda dapat memilih tinggi dan berat badan. Sebagai berikut dari gambar, kedua kelas ini membentuk dua set yang tidak berpotongan, yang dapat dijelaskan oleh fitur yang dipilih. Namun, tidak selalu mungkin untuk memilih parameter terukur yang benar sebagai fitur kelas. Misalnya, parameter yang dipilih tidak cocok untuk membuat kelas pemain sepak bola dan pemain bola basket yang tidak tumpang tindih.

Tugas pengenalan kedua adalah pemilihan fitur atau properti karakteristik dari gambar asli. Tugas ini dapat dikaitkan dengan preprocessing. Jika kita mempertimbangkan tugas pengenalan suara, kita dapat membedakan fitur-fitur seperti vokal dan konsonan. Atribut harus menjadi properti karakteristik dari kelas tertentu, sementara menjadi umum untuk kelas ini. Tanda yang menjadi ciri perbedaan antara – tanda antar kelas. Fitur umum untuk semua kelas tidak membawa informasi yang berguna dan tidak dianggap sebagai fitur dalam masalah pengenalan. Pilihan fitur adalah salah satu tugas penting yang terkait dengan pembangunan sistem pengenalan.

Setelah fitur ditentukan, maka perlu ditentukan prosedur keputusan yang optimal untuk klasifikasi. Pertimbangkan sistem pengenalan pola yang dirancang untuk mengenali berbagai kelas M, dilambangkan sebagai m_1,m_2,…,m 3. Kemudian kita dapat mengasumsikan bahwa ruang gambar terdiri dari M daerah, masing-masing berisi titik-titik yang sesuai dengan gambar dari satu kelas. Kemudian masalah pengenalan dapat dianggap sebagai konstruksi batas yang memisahkan kelas M berdasarkan vektor pengukuran yang diterima.

Penyelesaian masalah preprocessing citra, ekstraksi ciri dan masalah mendapatkan solusi dan klasifikasi yang optimal biasanya dikaitkan dengan kebutuhan untuk mengevaluasi sejumlah parameter. Hal ini menyebabkan masalah estimasi parameter. Selain itu, jelas bahwa ekstraksi fitur dapat menggunakan informasi tambahan berdasarkan sifat kelas.

Perbandingan objek dapat dilakukan atas dasar representasi mereka dalam bentuk vektor pengukuran. Lebih mudah untuk mewakili data pengukuran sebagai bilangan real. Kemudian persamaan vektor ciri dari dua objek dapat digambarkan dengan menggunakan jarak Euclidean.

di mana d adalah dimensi dari vektor fitur.

Ada 3 kelompok metode pengenalan pola:

• Perbandingan sampel. Golongan ini meliputi klasifikasi menurut mean terdekat, klasifikasi menurut jarak ke tetangga terdekat. Metode pengenalan struktural juga dapat dimasukkan dalam kelompok pembanding sampel.
• Metode Statistik. Sesuai dengan namanya, metode statistik menggunakan beberapa informasi statistik ketika memecahkan masalah pengenalan. Metode menentukan milik suatu objek ke kelas tertentu berdasarkan probabilitas.Dalam beberapa kasus, ini turun untuk menentukan probabilitas a posteriori suatu objek milik kelas tertentu, asalkan fitur dari objek ini telah mengambil yang sesuai nilai-nilai. Contohnya adalah metode aturan keputusan Bayesian.
• Jaringan saraf. Kelas terpisah dari metode pengenalan. Ciri khas dari orang lain adalah kemampuan untuk belajar.

Klasifikasi menurut cara terdekat

Dalam pendekatan klasik pengenalan pola, di mana objek yang tidak diketahui untuk klasifikasi direpresentasikan sebagai vektor fitur dasar. Sistem pengenalan berbasis fitur dapat dikembangkan dengan berbagai cara. Vektor-vektor ini dapat diketahui sistem terlebih dahulu sebagai hasil pelatihan atau diprediksi secara real time berdasarkan beberapa model.

Algoritma klasifikasi sederhana terdiri dari pengelompokan data referensi kelas menggunakan vektor harapan kelas (mean).

di mana x(i,j) adalah fitur referensi ke-j dari kelas i, n_j adalah jumlah vektor referensi dari kelas i.

Kemudian objek yang tidak diketahui akan menjadi milik kelas i jika lebih dekat dengan vektor harapan kelas i daripada dengan vektor harapan kelas lain. Metode ini cocok untuk masalah di mana titik-titik setiap kelas terletak secara kompak dan jauh dari titik-titik kelas lainnya.

Kesulitan akan muncul jika kelas memiliki struktur yang sedikit lebih kompleks, misalnya seperti pada gambar. Dalam hal ini, kelas 2 dibagi menjadi dua bagian yang tidak tumpang tindih, yang digambarkan dengan buruk oleh nilai rata-rata tunggal. Selain itu, kelas 3 terlalu memanjang, sampel kelas 3 dengan nilai koordinat x_2 yang besar lebih dekat dengan nilai rata-rata kelas 1 daripada kelas 3.

Masalah yang dijelaskan dalam beberapa kasus dapat diselesaikan dengan mengubah perhitungan jarak.

Kami akan mempertimbangkan karakteristik "hamburan" nilai kelas - _i, di sepanjang setiap arah koordinat i. Standar deviasi sama dengan akar kuadrat dari varians. Jarak Euclidean berskala antara vektor x dan vektor harapan x_c adalah

Rumus jarak ini akan mengurangi jumlah kesalahan klasifikasi, tetapi pada kenyataannya, sebagian besar masalah tidak dapat diwakili oleh kelas yang begitu sederhana.

Klasifikasi berdasarkan jarak ke tetangga terdekat

Pendekatan lain untuk klasifikasi adalah dengan menetapkan vektor fitur x yang tidak diketahui ke kelas yang vektor ini paling dekat dengan sampel terpisah. Aturan ini disebut aturan tetangga terdekat. Klasifikasi tetangga terdekat bisa lebih efisien bahkan ketika kelasnya kompleks atau ketika kelas tumpang tindih.

Pendekatan ini tidak memerlukan asumsi tentang model distribusi vektor fitur dalam ruang. Algoritme hanya menggunakan informasi tentang sampel referensi yang diketahui. Metode solusi didasarkan pada penghitungan jarak x ke setiap sampel dalam database dan mencari jarak minimum. Keuntungan dari pendekatan ini jelas:

• kapan saja Anda dapat menambahkan sampel baru ke database;
• struktur data pohon dan kisi mengurangi jumlah jarak yang dihitung.

Selain itu, solusinya akan lebih baik jika Anda mencari di database bukan untuk satu tetangga terdekat, tetapi untuk k. Kemudian, untuk k > 1, ini memberikan sampel terbaik dari distribusi vektor dalam ruang d-dimensi. Namun, efisiensi penggunaan nilai k tergantung pada apakah ada cukup di setiap wilayah ruang. Jika ada lebih dari dua kelas, maka lebih sulit untuk membuat keputusan yang tepat.

literatur

• M.Castrilon, . O. Deniz, . D. Hernández dan J. Lorenzo, “Sebuah perbandingan wajah dan fitur wajah detektor berdasarkan Viola-Jones kerangka umum deteksi objek,” International Journal of Computer Vision, no 22, hlm. 481-494, 2011.
• Y.-Q. Wang, "Analisis Algoritma Deteksi Wajah Viola-Jones," Jurnal IPOL, 2013.
• L. Shapiro dan D. Stockman, Visi komputer, Binom. Lab Pengetahuan, 2006.
• Z.N.G., Metode pengenalan dan penerapannya, radio Soviet, 1972.
• J. Tu, R. Gonzalez, Prinsip Matematika Pengenalan Pola, Moskow: "Mir" Moskow, 1974.
• Khan, H. Abdullah dan M. Shamian Bin Zainal, "Algoritme deteksi mata dan mulut yang efisien menggunakan kombinasi viola jones dan deteksi piksel warna kulit" International Journal of Engineering and Applied Sciences, no. Vol. 3 tidak 4, 2013.
• V. Gaede dan O. Gunther, "Metode Akses Multidimensi," Survei Komputasi ACM, hlm. 170-231, 1998.

→

Bab 3: Tinjauan Analitis Metode Pengenalan Pola dan Pengambilan Keputusan

Teori pengenalan pola dan otomatisasi kontrol

Tugas utama pengenalan pola adaptif

Pengenalan adalah proses informasi yang dilaksanakan oleh beberapa pengubah informasi (saluran informasi cerdas, sistem pengenalan) yang memiliki input dan output. Masukan dari sistem adalah informasi tentang fitur apa saja yang dimiliki objek yang disajikan. Keluaran dari sistem menampilkan informasi tentang kelas mana (gambar umum) yang ditugaskan untuk objek yang dapat dikenali.

Saat membuat dan mengoperasikan sistem pengenalan pola otomatis, sejumlah tugas diselesaikan. Mari kita secara singkat dan sederhana mempertimbangkan tugas-tugas ini. Perlu dicatat bahwa perumusan masalah ini, dan himpunan itu sendiri, tidak sesuai dengan penulis yang berbeda, karena sampai batas tertentu tergantung pada model matematika tertentu yang menjadi dasar sistem pengenalan ini atau itu. Selain itu, beberapa tugas dalam model pengenalan tertentu tidak memiliki solusi dan, karenanya, tidak diajukan.

Tugas memformalkan area subjek

Padahal, tugas ini adalah tugas coding. Daftar kelas umum dikompilasi, yang mungkin mencakup implementasi objek tertentu, serta daftar fitur yang pada prinsipnya dapat dimiliki oleh objek ini.

Tugas membentuk sampel pelatihan

Sampel pelatihan adalah database yang berisi deskripsi implementasi objek tertentu dalam bahasa fitur, dilengkapi dengan informasi tentang kepemilikan objek ini ke kelas pengenalan tertentu.

Tugas melatih sistem pengenalan

Sampel pelatihan digunakan untuk membentuk gambar umum dari kelas pengenalan berdasarkan generalisasi informasi tentang fitur apa yang dimiliki objek sampel pelatihan yang termasuk dalam kelas ini dan kelas lainnya.

Masalah pengurangan dimensi ruang fitur

Setelah melatih sistem pengenalan (memperoleh statistik tentang distribusi frekuensi fitur berdasarkan kelas), menjadi mungkin untuk menentukan setiap fitur nilainya untuk memecahkan masalah pengenalan. Setelah itu, fitur yang paling tidak berharga dapat dihapus dari sistem fitur. Kemudian sistem pengenalan harus dilatih kembali, karena sebagai akibat dari penghapusan beberapa fitur, statistik distribusi fitur yang tersisa berdasarkan kelas berubah. Proses ini dapat diulang, mis. menjadi iteratif.

tugas pengakuan

Objek sampel dikenali diakui, yang, khususnya, dapat terdiri dari satu objek. Sampel yang dapat dikenali dibentuk mirip dengan sampel pelatihan, tetapi tidak mengandung informasi tentang kepemilikan objek ke kelas, karena inilah yang ditentukan dalam proses pengenalan. Hasil pengenalan setiap objek adalah distribusi atau daftar semua kelas pengenalan dalam urutan derajat kesamaan objek yang dikenali dengan mereka.

Tugas kontrol kualitas pengakuan

Setelah pengakuan, kecukupannya dapat ditetapkan. Untuk objek sampel pelatihan, ini dapat dilakukan segera, karena bagi mereka hanya diketahui dari kelas mana mereka berada. Untuk objek lain, informasi ini dapat diperoleh nanti. Bagaimanapun, probabilitas kesalahan rata-rata aktual untuk semua kelas pengenalan dapat ditentukan, serta probabilitas kesalahan saat menetapkan objek yang dikenali ke kelas tertentu.

Hasil pengenalan harus ditafsirkan dengan mempertimbangkan informasi yang tersedia tentang kualitas pengenalan.

Tugas adaptasi

Jika, sebagai hasil dari prosedur pengendalian kualitas, ditemukan bahwa itu tidak memuaskan, maka deskripsi objek yang salah dikenali dapat disalin dari sampel yang dapat dikenali ke sampel pelatihan, dilengkapi dengan informasi klasifikasi yang memadai, dan digunakan untuk membentuk kembali keputusan. aturan, yaitu diperhitungkan. Selain itu, jika objek-objek ini tidak termasuk dalam kelas pengenalan yang sudah ada, yang dapat menjadi alasan untuk pengenalan yang salah, maka daftar ini dapat diperluas. Akibatnya, sistem pengenalan beradaptasi dan mulai mengklasifikasikan objek-objek ini secara memadai.

Masalah pengenalan terbalik

Tugas pengenalan adalah bahwa untuk objek tertentu, menurut fitur yang diketahui, sistem menetapkan miliknya ke beberapa kelas yang sebelumnya tidak diketahui. Dalam masalah pengenalan terbalik, sebaliknya, untuk kelas pengenalan yang diberikan, sistem menentukan fitur mana yang paling khas dari objek kelas ini dan mana yang bukan (atau objek sampel pelatihan mana yang termasuk dalam kelas ini).

Tugas cluster dan analisis konstruktif

Cluster adalah sekelompok objek, kelas atau fitur yang di dalam setiap cluster mereka semirip mungkin, dan di antara cluster yang berbeda mereka sedapat mungkin berbeda.

Sebuah konstruk (dalam konteks yang dipertimbangkan dalam bagian ini) adalah sistem dari cluster yang berlawanan. Jadi, dalam arti tertentu, konstruksi adalah hasil dari analisis klaster dari klaster.

Dalam analisis cluster, tingkat kesamaan dan perbedaan objek (kelas, fitur) diukur secara kuantitatif, dan informasi ini digunakan untuk klasifikasi. Hasil dari analisis klaster adalah pengklasifikasian objek berdasarkan klaster. Klasifikasi ini dapat direpresentasikan dalam bentuk jaringan semantik.

Tugas analisis kognitif

Dalam analisis kognitif, informasi tentang persamaan dan perbedaan kelas atau fitur menarik bagi peneliti itu sendiri, dan bukan untuk menggunakannya untuk klasifikasi, seperti dalam analisis klaster dan konstruktif.

Jika dua kelas pengenalan dicirikan oleh fitur yang sama, maka ini berkontribusi pada kesamaan kedua kelas ini. Jika untuk salah satu kelas fitur ini tidak seperti biasanya, maka ini berkontribusi pada perbedaan.

Jika dua tanda berkorelasi satu sama lain, maka dalam arti tertentu mereka dapat dianggap sebagai satu tanda, dan jika mereka antikorelasi, maka berbeda. Mempertimbangkan keadaan ini, kehadiran fitur yang berbeda di kelas yang berbeda juga memberikan kontribusi tertentu pada kesamaan dan perbedaannya.

Hasil analisis kognitif dapat disajikan dalam bentuk diagram kognitif.

Metode pengenalan pola dan karakteristiknya

Prinsip klasifikasi metode pengenalan pola

Pengenalan pola adalah tugas membangun dan menerapkan operasi formal pada representasi numerik atau simbolik dari objek dunia nyata atau ideal, yang hasil penyelesaiannya mencerminkan hubungan ekivalensi antara objek-objek ini. Relasi ekuivalensi mengekspresikan kepemilikan objek yang dievaluasi ke beberapa kelas, yang dianggap sebagai unit semantik independen.

Ketika membangun algoritma pengenalan, kelas kesetaraan dapat ditetapkan oleh seorang peneliti yang menggunakan ide-ide bermaknanya sendiri atau menggunakan informasi tambahan eksternal tentang kesamaan dan perbedaan objek dalam konteks masalah yang sedang dipecahkan. Kemudian seseorang berbicara tentang "pengakuan dengan guru". Jika tidak, yaitu ketika sistem otomatis memecahkan masalah klasifikasi tanpa melibatkan informasi pelatihan eksternal, seseorang berbicara tentang klasifikasi otomatis atau "pengenalan tanpa pengawasan". Sebagian besar algoritma pengenalan pola membutuhkan daya komputasi yang sangat signifikan, yang hanya dapat disediakan oleh teknologi komputer berkinerja tinggi.

Berbagai penulis (Yu.L. Barabash, V.I. Vasiliev, A.L. Gorelik, V.A. Skripkin, R. Duda, P. Hart, L.T. Kuzin, F.I. Peregudov, F.P. Tarasenko, F. E. Temnikov, J. Tu, R. Gonzalez, P. Winston, K. Fu, Ya. Z. Tsypkin dan lain-lain) memberikan tipologi metode pengenalan pola yang berbeda. Beberapa penulis membedakan antara metode parametrik, nonparametrik, dan heuristik, sementara yang lain memilih kelompok metode berdasarkan aliran sejarah dan tren di lapangan. Misalnya, dalam karya yang memberikan gambaran akademis tentang metode pengenalan, tipologi metode pengenalan pola berikut digunakan:

• metode berdasarkan prinsip pemisahan;
• metode statistik;
• metode yang dibangun berdasarkan "fungsi potensial";
• metode untuk menghitung nilai (voting);
• metode berdasarkan kalkulus proposisional, khususnya pada peralatan aljabar logika.

Klasifikasi ini didasarkan pada perbedaan dalam metode formal pengenalan pola, dan oleh karena itu pertimbangan pendekatan heuristik untuk pengenalan, yang telah menerima pengembangan penuh dan memadai dalam sistem pakar, dihilangkan. Pendekatan heuristik didasarkan pada pengetahuan dan intuisi peneliti yang sulit diformalkan. Pada saat yang sama, peneliti sendiri menentukan informasi apa dan bagaimana sistem harus digunakan untuk mencapai efek pengenalan yang diinginkan.

Tipologi metode pengenalan yang serupa dengan berbagai tingkat detail ditemukan di banyak karya tentang pengenalan. Pada saat yang sama, tipologi terkenal tidak memperhitungkan satu karakteristik yang sangat signifikan, yang mencerminkan kekhususan cara pengetahuan tentang bidang subjek diwakili menggunakan beberapa algoritma pengenalan pola formal.

D.A. Pospelov (1990) mengidentifikasi dua cara utama untuk merepresentasikan pengetahuan:

• intensional, berupa skema hubungan antar atribut (fitur).
• ekstensional, dengan bantuan fakta spesifik (objek, contoh).

Representasi intensional menangkap pola dan hubungan yang menjelaskan struktur data. Berkenaan dengan tugas diagnostik, fiksasi tersebut terdiri dalam menentukan operasi pada atribut (fitur) objek yang mengarah pada hasil diagnostik yang diperlukan. Representasi intensional diimplementasikan melalui operasi pada nilai atribut dan tidak menyiratkan operasi pada fakta informasi tertentu (objek).

Pada gilirannya, representasi pengetahuan ekstensional dikaitkan dengan deskripsi dan fiksasi objek tertentu dari area subjek dan diimplementasikan dalam operasi, yang elemen-elemennya adalah objek sebagai sistem integral.

Adalah mungkin untuk menarik analogi antara representasi pengetahuan yang intensional dan ekstensional dan mekanisme yang mendasari aktivitas belahan kiri dan kanan otak manusia. Jika belahan kanan dicirikan oleh representasi prototipikal holistik dari dunia sekitarnya, maka belahan kiri beroperasi dengan pola yang mencerminkan hubungan atribut dunia ini.

Dua cara mendasar dari representasi pengetahuan yang dijelaskan di atas memungkinkan kami untuk mengusulkan klasifikasi metode pengenalan pola berikut:

• metode intensional berdasarkan operasi dengan atribut.
• metode ekstensional berdasarkan operasi dengan objek.

Perlu ditekankan bahwa keberadaan dua (dan hanya dua) kelompok metode pengenalan ini: yang beroperasi dengan fitur dan yang beroperasi dengan objek, sangat alami. Dari sudut pandang ini, tidak satu pun dari metode ini, yang diambil secara terpisah dari yang lain, memungkinkan untuk membentuk refleksi yang memadai dari area subjek. Menurut penulis, antara metode ini ada hubungan saling melengkapi dalam arti N. Bohr, oleh karena itu, sistem pengenalan yang menjanjikan harus memastikan penerapan kedua metode ini, dan bukan hanya salah satunya.

Dengan demikian, klasifikasi metode pengenalan yang dikemukakan oleh D. A. Pospelov didasarkan pada hukum-hukum dasar yang melandasi cara kognisi manusia pada umumnya, yang menempatkannya pada posisi yang sangat istimewa (istimewa) dibandingkan dengan klasifikasi lain yang terlihat lebih ringan dan artifisial.

Metode Intensional

Ciri khas dari metode intensional adalah bahwa mereka menggunakan karakteristik yang berbeda dari fitur dan hubungan mereka sebagai elemen operasi dalam konstruksi dan penerapan algoritma pengenalan pola. Elemen tersebut dapat berupa nilai individual atau interval nilai fitur, nilai rata-rata dan varians, matriks hubungan fitur, dll., di mana tindakan dilakukan, dinyatakan dalam bentuk analitik atau konstruktif. Pada saat yang sama, objek dalam metode ini tidak dianggap sebagai unit informasi integral, tetapi bertindak sebagai indikator untuk menilai interaksi dan perilaku atributnya.

Kelompok metode pengenalan pola intensional sangat luas, dan pembagiannya menjadi subclass agak sewenang-wenang.

Metode berdasarkan perkiraan kepadatan distribusi nilai fitur

Metode pengenalan pola ini dipinjam dari teori klasik keputusan statistik, di mana objek studi dianggap sebagai realisasi dari variabel acak multidimensi yang didistribusikan dalam ruang fitur menurut beberapa hukum. Mereka didasarkan pada skema pengambilan keputusan Bayesian, yang mengacu pada probabilitas apriori objek milik satu atau lain kelas yang dapat dikenali dan kepadatan distribusi bersyarat dari nilai vektor fitur. Metode ini direduksi untuk menentukan rasio kemungkinan di berbagai area ruang fitur multidimensi.

Pengelompokan metode berdasarkan estimasi densitas distribusi nilai ciri berhubungan langsung dengan metode analisis diskriminan. Pendekatan Bayesian untuk pengambilan keputusan adalah salah satu yang paling berkembang dalam statistik modern, yang disebut metode parametrik, di mana ekspresi analitis dari hukum distribusi (dalam hal ini, hukum normal) dianggap diketahui dan hanya sebagian kecil jumlah parameter (vektor rata-rata dan matriks kovarians) perlu diestimasi.

Kesulitan utama dalam menerapkan metode ini adalah kebutuhan untuk mengingat seluruh sampel pelatihan untuk menghitung perkiraan kepadatan distribusi probabilitas lokal dan sensitivitas yang tinggi terhadap ketidakterwakilan sampel pelatihan.

Metode berdasarkan asumsi tentang kelas fungsi keputusan

Dalam kelompok metode ini, bentuk umum dari fungsi keputusan dianggap diketahui dan kualitas fungsionalnya diberikan. Berdasarkan fungsional ini, pendekatan terbaik dari fungsi keputusan ditemukan dari urutan pelatihan. Yang paling umum adalah representasi dari fungsi keputusan dalam bentuk polinomial nonlinier linier dan umum. Kualitas fungsional aturan keputusan biasanya dikaitkan dengan kesalahan klasifikasi.

Keuntungan utama dari metode berdasarkan asumsi tentang kelas fungsi keputusan adalah kejelasan rumusan matematis dari masalah pengenalan sebagai masalah menemukan ekstrem. Keragaman metode kelompok ini dijelaskan oleh berbagai fungsi kualitas aturan keputusan yang digunakan dan algoritma pencarian ekstrem. Generalisasi dari algoritma yang dipertimbangkan, yang meliputi, khususnya, algoritma Newton, algoritma tipe perceptron, dll., adalah metode pendekatan stokastik.

Kemungkinan algoritma gradien untuk menemukan ekstrem, terutama dalam kelompok aturan keputusan linier, telah dipelajari dengan cukup baik. Konvergensi algoritma ini telah dibuktikan hanya untuk kasus ketika kelas objek yang dapat dikenali ditampilkan dalam ruang fitur oleh struktur geometris yang kompak.

Kualitas aturan keputusan yang cukup tinggi dapat dicapai dengan menggunakan algoritme yang tidak memiliki bukti matematis yang ketat tentang konvergensi solusi ke ekstrem global. Algoritma tersebut mencakup sekelompok besar prosedur pemrograman heuristik yang mewakili arah pemodelan evolusioner. Pemodelan evolusioner adalah metode bionik yang dipinjam dari alam. Ini didasarkan pada penggunaan mekanisme evolusi yang diketahui untuk menggantikan proses pemodelan bermakna dari objek kompleks dengan pemodelan fenomenologis evolusinya. Perwakilan terkenal dari pemodelan evolusioner dalam pengenalan pola adalah metode akuntansi kelompok argumen (MGUA). GMDH didasarkan pada prinsip pengaturan diri, dan algoritma GMDH mereproduksi skema seleksi massal.

Namun, pencapaian tujuan praktis dalam hal ini tidak disertai dengan ekstraksi pengetahuan baru tentang sifat objek yang dapat dikenali. Kemungkinan mengekstraksi pengetahuan ini, khususnya pengetahuan tentang mekanisme interaksi atribut (fitur), pada dasarnya dibatasi di sini oleh struktur tertentu dari interaksi tersebut, yang ditetapkan dalam bentuk fungsi yang menentukan yang dipilih.

Metode Boolean

Metode logika pengenalan pola didasarkan pada peralatan aljabar logis dan memungkinkan untuk beroperasi dengan informasi yang terkandung tidak hanya dalam fitur individu, tetapi juga dalam kombinasi nilai fitur. Dalam metode ini, nilai atribut apa pun dianggap sebagai peristiwa dasar.

Dalam bentuk yang paling umum, metode logis dapat dicirikan sebagai semacam pencarian pola logis dalam sampel pelatihan dan pembentukan sistem aturan keputusan logis tertentu (misalnya, dalam bentuk konjungsi peristiwa dasar), masing-masing dari yang memiliki bobot sendiri. Kelompok metode logis beragam dan mencakup metode berbagai kompleksitas dan kedalaman analisis. Untuk fitur dikotomis (boolean), yang disebut pengklasifikasi seperti pohon, metode pengujian buntu, algoritma Bark, dll. sangat populer.

Algoritma Kora, seperti metode logis lainnya dari pengenalan pola, cukup melelahkan dalam hal perhitungan, karena enumerasi lengkap diperlukan saat memilih konjungsi. Oleh karena itu, ketika menerapkan metode logis, persyaratan tinggi ditempatkan pada organisasi yang efisien dari proses komputasi, dan metode ini bekerja dengan baik dengan dimensi ruang fitur yang relatif kecil dan hanya pada komputer yang kuat.

Metode linguistik (struktural)

Metode linguistik pengenalan pola didasarkan pada penggunaan tata bahasa khusus yang menghasilkan bahasa yang dapat digunakan untuk menggambarkan seperangkat properti objek yang dapat dikenali.

Untuk kelas objek yang berbeda, elemen non-turunan (atom) (subgambar, tanda) dan kemungkinan hubungan di antara mereka dibedakan. Tata bahasa mengacu pada aturan untuk membangun objek dari elemen non-turunan ini.

Jadi, setiap objek adalah kumpulan elemen non-turunan, "terhubung" satu sama lain dalam satu atau lain cara, atau, dengan kata lain, oleh "kalimat" dari beberapa "bahasa". Saya ingin menekankan nilai ideologis yang sangat signifikan dari pemikiran ini.

Dengan mem-parsing (mengurai) sebuah "kalimat", "kebenaran" sintaksisnya ditentukan, atau, secara setara, apakah beberapa tata bahasa tetap yang menggambarkan suatu kelas dapat menghasilkan deskripsi objek yang ada.

Namun, tugas memulihkan (mendefinisikan) tata bahasa dari serangkaian pernyataan (kalimat - deskripsi objek) tertentu yang menghasilkan bahasa tertentu sulit untuk diformalkan.

Metode Ekstensi

Dalam metode kelompok ini, berbeda dengan arah intensional, setiap objek yang dipelajari diberikan nilai diagnostik independen pada tingkat yang lebih besar atau lebih kecil. Pada intinya, metode ini dekat dengan pendekatan klinis, yang menganggap orang bukan sebagai rantai objek yang diberi peringkat menurut satu atau lain indikator, tetapi sebagai sistem integral, yang masing-masing bersifat individual dan memiliki nilai diagnostik khusus. Sikap hati-hati terhadap objek studi tidak memungkinkan seseorang untuk mengecualikan atau kehilangan informasi tentang setiap objek individu, yang terjadi ketika menerapkan metode arah yang disengaja, menggunakan objek hanya untuk mendeteksi dan memperbaiki pola perilaku atributnya.

Operasi utama dalam pengenalan pola menggunakan metode yang dibahas adalah operasi menentukan kesamaan dan perbedaan objek. Objek dalam kelompok metode tertentu memainkan peran preseden diagnostik. Pada saat yang sama, tergantung pada kondisi tugas tertentu, peran preseden individu dapat bervariasi dalam batas terluas: dari partisipasi utama dan menentukan hingga partisipasi yang sangat tidak langsung dalam proses pengakuan. Pada gilirannya, kondisi masalah mungkin memerlukan partisipasi sejumlah preseden diagnostik yang berbeda untuk solusi yang berhasil: dari satu di setiap kelas yang dapat dikenali hingga seluruh ukuran sampel, serta cara yang berbeda untuk menghitung ukuran kesamaan dan perbedaan objek. Persyaratan ini menjelaskan pembagian lebih lanjut dari metode ekstensional ke dalam subkelas.

Metode perbandingan prototipe

Ini adalah metode pengenalan ekstensional yang paling sederhana. Ini digunakan, misalnya, dalam kasus ketika kelas yang dikenali ditampilkan di ruang fitur dengan pengelompokan geometris yang kompak. Dalam hal ini, pusat pengelompokan geometris kelas (atau objek yang paling dekat dengan pusat) biasanya dipilih sebagai titik prototipe.

Untuk mengklasifikasikan objek yang tidak diketahui, prototipe yang paling dekat dengannya ditemukan, dan objek tersebut termasuk dalam kelas yang sama dengan prototipe ini. Jelas, tidak ada gambar kelas umum yang terbentuk dalam metode ini.

Berbagai jenis jarak dapat digunakan sebagai ukuran kedekatan. Seringkali untuk fitur dikotomis, jarak Hamming digunakan, yang dalam hal ini sama dengan kuadrat jarak Euclidean. Dalam hal ini, aturan keputusan untuk mengklasifikasikan objek setara dengan fungsi keputusan linier.

Fakta ini harus diperhatikan secara khusus. Ini dengan jelas menunjukkan hubungan antara prototipe dan representasi indikatif informasi tentang struktur data. Menggunakan representasi di atas, misalnya, setiap skala pengukuran tradisional, yang merupakan fungsi linier dari nilai-nilai fitur dikotomis, dapat dianggap sebagai prototipe diagnostik hipotetis. Pada gilirannya, jika analisis struktur spasial kelas yang dikenali memungkinkan kita untuk menyimpulkan bahwa mereka kompak secara geometris, maka cukup untuk mengganti masing-masing kelas ini dengan satu prototipe, yang sebenarnya setara dengan model diagnostik linier.

Dalam praktiknya, tentu saja, situasinya seringkali berbeda dari contoh ideal yang digambarkan. Seorang peneliti yang bermaksud menerapkan metode pengenalan berdasarkan perbandingan dengan prototipe kelas diagnostik menghadapi masalah yang sulit.

Pertama, itu adalah pilihan ukuran kedekatan (metrik), yang secara signifikan dapat mengubah konfigurasi spasial dari distribusi objek. Kedua, masalah independen adalah analisis struktur multidimensi data eksperimen. Kedua masalah ini sangat akut bagi peneliti dalam kondisi ruang fitur berdimensi tinggi, yang khas untuk masalah nyata.

k metode tetangga terdekat

Metode k tetangga terdekat untuk memecahkan masalah analisis diskriminan pertama kali diusulkan kembali pada tahun 1952. Ini adalah sebagai berikut.

Saat mengklasifikasikan objek yang tidak diketahui, ditemukan sejumlah (k) objek lain yang secara geometris paling dekat dengannya di ruang fitur (tetangga terdekat) dengan kelas yang dapat dikenali yang sudah diketahui. Keputusan untuk menetapkan objek yang tidak diketahui ke kelas diagnostik tertentu dibuat dengan menganalisis informasi tentang keanggotaan yang diketahui dari tetangga terdekatnya, misalnya, menggunakan penghitungan suara sederhana.

Awalnya, metode k tetangga terdekat dianggap sebagai metode nonparametrik untuk memperkirakan rasio kemungkinan. Untuk metode ini, estimasi teoritis efektivitasnya diperoleh dibandingkan dengan pengklasifikasi Bayesian yang optimal. Terbukti bahwa peluang kesalahan asimtotik untuk metode k tetangga terdekat melebihi kesalahan aturan Bayes tidak lebih dari dua kali.

Saat menggunakan metode k tetangga terdekat untuk pengenalan pola, peneliti harus memecahkan masalah sulit dalam memilih metrik untuk menentukan kedekatan objek yang didiagnosis. Masalah ini dalam kondisi ruang fitur berdimensi tinggi menjadi sangat parah karena cukup rumitnya metode ini, yang menjadi signifikan bahkan untuk komputer berperforma tinggi. Oleh karena itu, di sini, seperti dalam metode perbandingan prototipe, perlu untuk memecahkan masalah kreatif dalam menganalisis struktur multidimensi data eksperimen untuk meminimalkan jumlah objek yang mewakili kelas diagnostik.

Kebutuhan untuk mengurangi jumlah objek dalam sampel pelatihan (preseden diagnostik) adalah kerugian dari metode ini, karena mengurangi keterwakilan sampel pelatihan.

Algoritma untuk menghitung nilai ("voting")

Prinsip pengoperasian algoritma evaluasi (ABO) adalah menghitung prioritas (skor kesamaan) yang mencirikan "kedekatan" dari objek yang dikenali dan referensi menurut sistem ansambel fitur, yang merupakan sistem himpunan bagian dari serangkaian fitur yang diberikan. .

Tidak seperti semua metode yang dipertimbangkan sebelumnya, algoritme untuk menghitung perkiraan beroperasi dengan deskripsi objek dengan cara yang secara fundamental baru. Untuk algoritma ini, objek ada secara bersamaan di subruang yang sangat berbeda dari ruang fitur. Kelas ABO membawa gagasan untuk menggunakan fitur ke tujuan logisnya: karena tidak selalu diketahui kombinasi fitur mana yang paling informatif, di ABO tingkat kesamaan objek dihitung dengan membandingkan semua kemungkinan atau kombinasi fitur tertentu. termasuk dalam deskripsi objek.

Kombinasi fitur (subruang) yang digunakan disebut oleh penulis sebagai set pendukung atau set deskripsi parsial objek. Konsep kedekatan umum antara objek yang dikenali dan objek sampel pelatihan (dengan klasifikasi yang diketahui), yang disebut objek referensi, diperkenalkan. Kedekatan ini diwakili oleh kombinasi kedekatan objek yang dapat dikenali dengan objek referensi yang dihitung pada kumpulan deskripsi parsial. Dengan demikian, ABO adalah perluasan dari metode k tetangga terdekat, di mana kedekatan objek dianggap hanya dalam satu ruang fitur yang diberikan.

Perpanjangan lain dari ABO adalah bahwa dalam algoritma ini masalah penentuan kesamaan dan perbedaan objek dirumuskan sebagai satu parametrik dan tahap pengaturan ABO sesuai dengan sampel pelatihan dipilih, di mana nilai optimal dari ABO dipilih. parameter yang dimasukkan dipilih. Kriteria kualitas adalah kesalahan pengenalan, dan secara harfiah semuanya diparameterisasi:

• aturan untuk menghitung kedekatan objek dengan fitur individu;
• aturan untuk menghitung kedekatan objek di subruang fitur;
• tingkat kepentingan objek referensi tertentu sebagai preseden diagnostik;
• signifikansi kontribusi setiap set fitur referensi untuk penilaian akhir kesamaan objek yang dikenali dengan kelas diagnostik apa pun.

Parameter pendingin udara ditetapkan dalam bentuk nilai ambang batas dan (atau) sebagai bobot komponen yang ditentukan.

Kemungkinan teoritis ABO setidaknya tidak lebih rendah daripada algoritma pengenalan pola lainnya, karena dengan bantuan ABO semua operasi yang dapat dibayangkan dengan objek yang diteliti dapat diimplementasikan.

Tetapi, seperti yang biasanya terjadi, perluasan potensi menghadapi kesulitan besar dalam implementasi praktisnya, terutama pada tahap konstruksi (penyetelan) algoritma jenis ini.

Kesulitan terpisah dicatat sebelumnya ketika membahas metode k tetangga terdekat, yang dapat ditafsirkan sebagai versi ABO yang terpotong. Ini juga dapat dipertimbangkan dalam bentuk parametrik dan masalahnya dapat direduksi menjadi menemukan metrik berbobot dari jenis yang dipilih. Pada saat yang sama, sudah di sini untuk masalah dimensi tinggi, pertanyaan teoretis kompleks dan masalah yang terkait dengan organisasi proses komputasi yang efisien muncul.

Untuk ABO, jika Anda mencoba menggunakan kemampuan algoritma ini secara penuh, kesulitan ini meningkat berkali-kali lipat.

Masalah yang dicatat menjelaskan bahwa dalam praktik penggunaan ABO untuk memecahkan masalah berdimensi tinggi disertai dengan pengenalan batasan dan asumsi heuristik. Secara khusus, ada contoh penggunaan ABO dalam psikodiagnostik, di mana jenis ABO diuji, yang sebenarnya setara dengan metode k tetangga terdekat.

Kolektif Aturan yang Menentukan

Di akhir tinjauan metode pengenalan pola, mari kita membahas satu pendekatan lagi. Inilah yang disebut tim aturan keputusan (CRC).

Karena algoritma pengenalan yang berbeda berperilaku berbeda pada sampel objek yang sama, pertanyaan secara alami muncul dari aturan keputusan sintetis yang secara adaptif menggunakan kekuatan algoritma ini. Aturan keputusan sintetik menggunakan skema pengenalan dua tingkat. Pada tingkat pertama, algoritma pengenalan pribadi bekerja, yang hasilnya digabungkan pada tingkat kedua di blok sintesis. Metode yang paling umum dari kombinasi semacam itu didasarkan pada alokasi area kompetensi algoritma tertentu. Cara paling sederhana untuk menemukan bidang kompetensi adalah dengan apriori membagi ruang atribut berdasarkan pertimbangan profesional dari ilmu tertentu (misalnya, stratifikasi sampel menurut beberapa atribut). Kemudian, untuk setiap area yang dipilih, algoritma pengenalannya sendiri dibangun. Metode lain didasarkan pada penggunaan analisis formal untuk menentukan area lokal dari ruang fitur sebagai lingkungan dari objek yang dapat dikenali dimana keberhasilan algoritma pengenalan tertentu telah terbukti.

Pendekatan paling umum untuk membangun blok sintesis menganggap indikator yang dihasilkan dari algoritma tertentu sebagai fitur awal untuk membangun aturan keputusan umum yang baru. Dalam hal ini, semua metode arah intensional dan ekstensional di atas dalam pengenalan pola dapat digunakan. Efektif untuk memecahkan masalah membuat seperangkat aturan keputusan adalah algoritma logis dari tipe "Kora" dan algoritma untuk menghitung perkiraan (ABO), yang membentuk dasar dari apa yang disebut pendekatan aljabar, yang menyediakan penelitian dan deskripsi konstruktif dari algoritma pengenalan, di mana semua jenis algoritma yang ada cocok.

Analisis komparatif metode pengenalan pola

Mari kita bandingkan metode pengenalan pola yang dijelaskan di atas dan mengevaluasi tingkat kecukupannya dengan persyaratan yang dirumuskan dalam Bagian 3.3.3 untuk model SDA untuk sistem kontrol otomatis adaptif untuk sistem yang kompleks.

Untuk memecahkan masalah nyata dari kelompok metode arah intensional, metode parametrik dan metode berdasarkan proposal dalam bentuk fungsi yang menentukan memiliki nilai praktis. Metode parametrik membentuk dasar metodologi tradisional untuk membangun indikator. Penerapan metode ini dalam masalah nyata dikaitkan dengan pengenaan pembatasan kuat pada struktur data, yang mengarah pada model diagnostik linier dengan perkiraan parameter yang sangat mendekati. Ketika menggunakan metode berdasarkan asumsi tentang bentuk fungsi keputusan, peneliti juga terpaksa beralih ke model linier. Hal ini disebabkan oleh dimensi tinggi dari ruang fitur, yang khas untuk masalah nyata, yang, dengan peningkatan derajat fungsi keputusan polinomial, memberikan peningkatan besar dalam jumlah anggotanya dengan peningkatan bermasalah seiring dalam kualitas pengakuan. Dengan demikian, memproyeksikan area penerapan potensial metode pengenalan intensional ke masalah nyata, kami mendapatkan gambaran yang sesuai dengan metodologi tradisional model diagnostik linier yang mapan.

Sifat-sifat model diagnostik linier, di mana indikator diagnostik diwakili oleh jumlah bobot fitur awal, dipelajari dengan baik. Hasil dari model ini (dengan normalisasi yang sesuai) diinterpretasikan sebagai jarak dari objek yang diteliti ke beberapa hyperplane di ruang fitur atau, secara ekuivalen, sebagai proyeksi objek ke beberapa garis lurus dalam ruang yang diberikan. Oleh karena itu, model linier hanya memadai untuk konfigurasi geometris sederhana dari wilayah ruang fitur di mana objek dari kelas diagnostik yang berbeda dipetakan. Dengan distribusi yang lebih kompleks, model ini pada dasarnya tidak dapat mencerminkan banyak fitur dari struktur data eksperimental. Pada saat yang sama, fitur tersebut dapat memberikan informasi diagnostik yang berharga.

Pada saat yang sama, penampilan dalam setiap masalah nyata dari struktur multidimensi sederhana (khususnya, distribusi normal multidimensi) harus dianggap sebagai pengecualian daripada sebagai aturan. Seringkali, kelas diagnostik dibentuk berdasarkan kriteria eksternal yang kompleks, yang secara otomatis memerlukan heterogenitas geometris kelas-kelas ini dalam ruang fitur. Hal ini terutama berlaku untuk kriteria "kehidupan" yang paling sering ditemui dalam praktik. Dalam kondisi seperti itu, penggunaan model linier hanya memperbaiki pola informasi eksperimental yang paling "kasar".

Penggunaan metode ekstensional tidak dikaitkan dengan asumsi tentang struktur informasi eksperimental, kecuali bahwa dalam kelas yang diakui harus ada satu atau lebih kelompok objek yang agak mirip, dan objek dari kelas yang berbeda harus berbeda satu sama lain dalam beberapa hal. jalan. Jelas bahwa untuk setiap dimensi terbatas dari sampel pelatihan (dan tidak boleh berbeda), persyaratan ini selalu dipenuhi hanya karena ada perbedaan acak antara objek. Berbagai ukuran kedekatan (distance) objek dalam ruang fitur digunakan sebagai ukuran kesamaan. Oleh karena itu, penggunaan efektif metode pengenalan pola ekstensional bergantung pada seberapa baik ukuran kedekatan ini ditentukan, serta objek sampel pelatihan mana (objek dengan klasifikasi yang diketahui) memainkan peran preseden diagnostik. Solusi yang berhasil dari masalah ini memberikan hasil yang mendekati batas efisiensi pengenalan yang dapat dicapai secara teoritis.

Keuntungan dari metode ekstensional pengenalan pola ditentang, pertama-tama, oleh kompleksitas teknis yang tinggi dari implementasi praktisnya. Untuk ruang fitur berdimensi tinggi, tugas yang tampaknya sederhana untuk menemukan pasangan titik terdekat berubah menjadi masalah serius. Juga, banyak penulis mencatat sebagai masalah kebutuhan untuk mengingat sejumlah besar objek yang mewakili kelas yang dapat dikenali.

Dalam dirinya sendiri, ini bukan masalah, tetapi dianggap sebagai masalah (misalnya, dalam metode k tetangga terdekat) dengan alasan bahwa ketika mengenali setiap objek, enumerasi lengkap semua objek dalam sampel pelatihan terjadi.

Oleh karena itu, disarankan untuk menerapkan model sistem pengenalan, di mana masalah penghitungan lengkap objek sampel pelatihan selama pengenalan dihilangkan, karena itu dilakukan hanya sekali ketika membentuk gambar umum dari kelas pengenalan. Dalam pengenalan itu sendiri, objek yang diidentifikasi hanya dibandingkan dengan gambar umum dari kelas pengenalan, yang jumlahnya tetap dan tidak bergantung sama sekali pada dimensi sampel pelatihan. Pendekatan ini memungkinkan Anda untuk meningkatkan dimensi sampel pelatihan hingga kualitas gambar umum yang disyaratkan tercapai, tanpa rasa takut bahwa hal ini dapat menyebabkan peningkatan waktu pengenalan yang tidak dapat diterima (karena waktu pengenalan dalam model ini tidak bergantung pada dimensi pelatihan sama sekali).

Masalah teoritis penerapan metode pengenalan ekstensional terkait dengan masalah pencarian kelompok fitur yang informatif, menemukan metrik yang optimal untuk mengukur kesamaan dan perbedaan objek, dan menganalisis struktur informasi eksperimental. Pada saat yang sama, solusi sukses dari masalah ini memungkinkan tidak hanya merancang algoritma pengenalan yang efektif, tetapi juga membuat transisi dari pengetahuan ekstensional tentang fakta empiris ke pengetahuan intensional tentang pola strukturnya.

Transisi dari pengetahuan ekstensional ke pengetahuan intensional terjadi pada tahap ketika algoritma pengenalan formal telah dibangun dan efektivitasnya telah ditunjukkan. Kemudian studi tentang mekanisme yang digunakan untuk mencapai efisiensi yang diperoleh. Studi semacam itu, terkait dengan analisis struktur geometris data, dapat, misalnya, mengarah pada kesimpulan bahwa cukup untuk mengganti objek yang mewakili kelas diagnostik tertentu dengan satu perwakilan tipikal (prototipe). Ini setara, seperti disebutkan di atas, untuk menetapkan skala diagnostik linier tradisional. Mungkin juga cukup untuk mengganti setiap kelas diagnostik dengan beberapa objek yang bermakna sebagai perwakilan khas dari beberapa subkelas, yang setara dengan membangun kipas skala linier. Ada opsi lain, yang akan dibahas di bawah.

Dengan demikian, tinjauan metode pengenalan menunjukkan bahwa sejumlah metode pengenalan pola yang berbeda telah dikembangkan secara teoritis saat ini. Literatur memberikan klasifikasi rinci dari mereka. Namun, untuk sebagian besar metode ini, implementasi perangkat lunaknya tidak ada, dan ini sangat alami, bahkan dapat dikatakan "ditentukan sebelumnya" oleh karakteristik metode pengenalan itu sendiri. Hal ini dapat dinilai dari fakta bahwa sistem seperti itu sedikit disebutkan dalam literatur khusus dan sumber informasi lainnya.

Akibatnya, pertanyaan tentang penerapan praktis dari metode pengenalan teoretis tertentu untuk memecahkan masalah praktis dengan dimensi data nyata (yaitu, cukup signifikan) dan pada komputer modern nyata masih kurang berkembang.

Keadaan di atas dapat dipahami jika kita mengingat kembali bahwa kompleksitas model matematika secara eksponensial meningkatkan kompleksitas implementasi perangkat lunak dari sistem dan pada tingkat yang sama mengurangi kemungkinan bahwa sistem ini akan bekerja dalam praktik. Ini berarti bahwa hanya sistem perangkat lunak berdasarkan model matematika yang cukup sederhana dan "transparan" yang dapat diimplementasikan di pasar. Oleh karena itu, pengembang yang tertarik untuk mereplikasi produk perangkat lunaknya mendekati masalah pemilihan model matematika bukan dari sudut pandang ilmiah murni, tetapi sebagai seorang pragmatis, dengan mempertimbangkan kemungkinan implementasi perangkat lunak. Ia percaya bahwa model harus sesederhana mungkin, yang berarti harus dilaksanakan dengan biaya lebih rendah dan dengan kualitas yang lebih baik, dan juga harus bekerja (secara praktis efektif).

Dalam hal ini, tugas menerapkan dalam sistem pengenalan mekanisme untuk menggeneralisasi deskripsi objek yang termasuk dalam kelas yang sama, mis. mekanisme untuk pembentukan gambar umum yang kompak. Jelas bahwa mekanisme generalisasi seperti itu akan memungkinkan "mengompresi" sampel pelatihan apa pun dalam hal dimensi ke dasar gambar umum yang diketahui sebelumnya dalam hal dimensi. Ini juga akan memungkinkan kita untuk menetapkan dan memecahkan sejumlah masalah yang bahkan tidak dapat dirumuskan dalam metode pengenalan seperti perbandingan dengan metode prototipe, metode k tetangga terdekat, dan ABO.

Ini adalah tugas-tugasnya:

• menentukan kontribusi informasi fitur ke potret informasi dari gambar umum;
• analisis cluster-konstruktif dari gambar umum;
• penentuan beban semantik atribut;
• analisis semantik cluster-konstruktif fitur;
• perbandingan yang bermakna dari gambar kelas umum satu sama lain dan fitur satu sama lain (diagram kognitif, termasuk diagram Merlin).

Metode yang memungkinkan untuk mencapai solusi dari masalah ini juga membedakan sistem perspektif berdasarkan itu dari sistem lain, sama seperti compiler berbeda dari interpreter, karena karena pembentukan gambar umum dalam sistem perspektif ini, waktu pengenalan tidak tergantung pada ukuran sampel pelatihan. Diketahui bahwa keberadaan ketergantungan inilah yang menyebabkan pengeluaran waktu komputer yang praktis tidak dapat diterima untuk pengenalan dalam metode seperti metode k tetangga terdekat, ABO, dan CRP pada dimensi sampel pelatihan seperti itu, ketika seseorang dapat berbicara tentang cukup statistik.

Sebagai kesimpulan dari tinjauan singkat tentang metode pengenalan, kami menyajikan esensi di atas dalam tabel ringkasan (Tabel 3.1), yang berisi deskripsi singkat tentang berbagai metode pengenalan pola dalam parameter berikut:

• klasifikasi metode pengenalan;
• bidang penerapan metode pengenalan;
• klasifikasi keterbatasan metode pengenalan.

Klasifikasi metode pengenalan		Area aplikasi	Keterbatasan (kekurangan)
Metode pengenalan intensif	Metode berdasarkan perkiraan kepadatan distribusi nilai fitur (atau persamaan dan perbedaan antara objek)	Masalah dengan distribusi yang diketahui, biasanya normal, kebutuhan untuk mengumpulkan statistik yang besar	Kebutuhan untuk menghitung keseluruhan set pelatihan selama pengenalan, sensitivitas tinggi terhadap non-representatif dari set pelatihan dan artefak
	Metode berdasarkan asumsi tentang kelas fungsi keputusan	Kelas harus dapat dipisahkan dengan baik, sistem fitur harus ortonormal	Bentuk fungsi keputusan harus diketahui terlebih dahulu. Ketidakmungkinan untuk mempertimbangkan pengetahuan baru tentang korelasi antar fitur
	Metode Boolean		Ketika memilih aturan keputusan logis (konjungsi), enumerasi lengkap diperlukan. Kompleksitas komputasi yang tinggi
	Metode linguistik (struktural)	Masalah dimensi kecil ruang fitur	Tugas memulihkan (mendefinisikan) tata bahasa dari serangkaian pernyataan (deskripsi objek) tertentu sulit untuk diformalkan. Masalah teoretis yang belum terselesaikan
Metode pengenalan ekstensional	Metode perbandingan prototipe	Masalah dimensi kecil ruang fitur	Ketergantungan yang tinggi dari hasil klasifikasi pada ukuran jarak (metrik). Metrik optimal tidak diketahui
	k metode tetangga terdekat		Ketergantungan yang tinggi dari hasil klasifikasi pada ukuran jarak (metrik). Kebutuhan untuk enumerasi lengkap dari sampel pelatihan selama pengakuan. Kompleksitas komputasi
	Algoritma untuk menghitung nilai (voting) AVO	Masalah dimensi kecil dalam hal jumlah kelas dan fitur	Ketergantungan hasil klasifikasi pada ukuran jarak (metrik). Kebutuhan untuk enumerasi lengkap dari sampel pelatihan selama pengakuan. Kompleksitas teknis yang tinggi dari metode ini
	Kolektif Aturan Tegas (CRC)	Masalah dimensi kecil dalam hal jumlah kelas dan fitur	Kompleksitas teknis metode yang sangat tinggi, sejumlah masalah teoretis yang belum terselesaikan, baik dalam menentukan bidang kompetensi metode tertentu, maupun dalam metode tertentu itu sendiri.

Tabel 3.1 - Tabel ringkasan klasifikasi metode pengenalan, perbandingan area aplikasi dan batasannya

Peran dan tempat pengenalan pola dalam otomatisasi manajemen sistem yang kompleks

Sistem kontrol otomatis terdiri dari dua bagian utama: objek kontrol dan sistem kontrol.

Sistem kontrol melakukan fungsi-fungsi berikut:

• identifikasi keadaan objek kontrol;
• pengembangan tindakan kontrol berdasarkan tujuan manajemen, dengan mempertimbangkan keadaan objek kontrol dan lingkungan;
• memberikan efek kontrol pada objek kontrol.

Pengenalan pola tidak lebih dari identifikasi keadaan beberapa objek.

Oleh karena itu, kemungkinan penggunaan sistem pengenalan pola pada tahap mengidentifikasi keadaan objek kontrol tampaknya cukup jelas dan alami. Namun, ini mungkin tidak diperlukan. Oleh karena itu, muncul pertanyaan dalam kasus mana disarankan untuk menggunakan sistem pengenalan dalam sistem kontrol otomatis, dan di mana tidak.

Menurut data literatur, dalam banyak sistem kontrol otomatis yang dikembangkan sebelumnya dan modern dalam subsistem untuk mengidentifikasi keadaan objek kontrol dan menghasilkan tindakan kontrol, model matematika deterministik "penghitungan langsung" digunakan, yang secara jelas dan sederhana menentukan apa yang harus dilakukan. lakukan dengan objek kontrol jika memiliki parameter eksternal tertentu.

Pada saat yang sama, pertanyaan tentang bagaimana parameter ini terkait dengan keadaan tertentu dari objek kontrol tidak diangkat atau diselesaikan. Posisi ini sesuai dengan sudut pandang, yang terdiri dari fakta bahwa hubungan satu-ke-satu mereka diterima "secara default". Oleh karena itu, istilah: "parameter objek kontrol" dan "keadaan objek kontrol" dianggap sebagai sinonim, dan konsep "keadaan objek kontrol" tidak diperkenalkan secara eksplisit sama sekali. Namun, jelas bahwa dalam kasus umum, hubungan antara parameter yang diamati dari objek kontrol dan keadaannya adalah dinamis dan probabilistik.

Dengan demikian, sistem kontrol otomatis tradisional pada dasarnya adalah sistem kontrol parametrik, yaitu sistem yang mengelola bukan status objek kontrol, tetapi hanya parameter yang dapat diamati. Keputusan tentang tindakan kontrol diambil dalam sistem seperti itu seolah-olah "secara membabi buta", yaitu. tanpa membentuk gambaran holistik dari objek kontrol dan lingkungan dalam keadaan mereka saat ini, serta tanpa memprediksi perkembangan lingkungan dan reaksi objek kontrol terhadap tindakan kontrol tertentu di atasnya, bertindak secara bersamaan dengan pengaruh lingkungan yang diprediksi. .

Dari posisi yang dikembangkan dalam makalah ini, istilah "pengambilan keputusan" dalam pengertian modern hampir tidak dapat diterapkan pada sistem kontrol otomatis tradisional. Faktanya adalah bahwa "pengambilan keputusan", setidaknya, melibatkan visi holistik dari suatu objek di lingkungan, dan tidak hanya dalam keadaan mereka saat ini, tetapi juga dalam dinamika, dan dalam interaksi baik satu sama lain maupun dengan sistem kontrol, melibatkan pertimbangan berbagai alternatif pilihan untuk pengembangan keseluruhan sistem ini, serta mempersempit keragaman (pengurangan) alternatif-alternatif tersebut berdasarkan kriteria sasaran tertentu. Tidak satu pun dari ini, jelas, tidak dalam ACS tradisional, atau memang demikian, tetapi dalam bentuk yang disederhanakan.

Tentu saja, metode tradisional sudah memadai dan penerapannya cukup tepat dan dibenarkan dalam kasus di mana objek kontrol memang merupakan sistem yang stabil dan ditentukan secara kaku, dan pengaruh lingkungan terhadapnya dapat diabaikan.

Namun, dalam kasus lain, metode ini tidak efektif.

Jika objek kontrol bersifat dinamis, maka model yang mendasari algoritme kontrolnya dengan cepat menjadi tidak memadai, karena hubungan antara parameter input dan output berubah, serta kumpulan parameter penting itu sendiri. Intinya, ini berarti bahwa sistem kontrol otomatis tradisional dapat mengontrol keadaan objek kontrol hanya di dekat titik keseimbangan melalui tindakan kontrol yang lemah di atasnya, yaitu. dengan metode gangguan kecil. Jauh dari keadaan ekuilibrium, dari sudut pandang tradisional, perilaku objek kontrol terlihat tak terduga dan tak terkendali.

Jika tidak ada hubungan yang jelas antara parameter input dan output dari objek kontrol (yaitu, antara parameter input dan keadaan objek), dengan kata lain, jika hubungan ini memiliki sifat probabilistik yang nyata, maka model deterministik, dalam yang diasumsikan bahwa hasil pengukuran parameter tertentu hanyalah angka, awalnya tidak berlaku. Selain itu, bentuk hubungan ini mungkin tidak diketahui, dan kemudian perlu untuk melanjutkan dari asumsi yang paling umum: bahwa itu probabilistik, atau tidak terdefinisi sama sekali.

Sistem kontrol otomatis yang dibangun di atas prinsip-prinsip tradisional hanya dapat bekerja berdasarkan parameter, pola hubungan yang sudah diketahui, dipelajari, dan tercermin dalam model matematika, dalam penelitian ini tugas ditetapkan untuk mengembangkan metode tersebut untuk merancang kontrol otomatis. sistem yang memungkinkan pembuatan sistem yang dapat mengidentifikasi dan menetapkan parameter paling signifikan, dan menentukan sifat hubungan antara parameter tersebut dan status objek kontrol.

Dalam hal ini, perlu untuk menerapkan metode pengukuran yang lebih berkembang dan memadai untuk situasi nyata:

• klasifikasi atau pengenalan pola (pembelajaran berdasarkan sampel pelatihan, kemampuan beradaptasi dari algoritma pengenalan, kemampuan beradaptasi set kelas dan parameter yang dipelajari, pemilihan parameter yang paling signifikan dan pengurangan dimensi deskripsi sambil mempertahankan redundansi yang diberikan, dll.);
• pengukuran statistik, ketika hasil pengukuran parameter tertentu bukan angka tunggal, tetapi distribusi probabilitas: perubahan variabel statistik tidak berarti perubahan nilainya itu sendiri, tetapi perubahan karakteristik distribusi probabilitas dari nilai-nilainya.

Akibatnya, sistem kontrol otomatis berdasarkan pendekatan deterministik tradisional praktis tidak bekerja dengan objek kontrol multi-parameter dinamis kompleks yang ditentukan dengan lemah, seperti, misalnya, sistem makro dan mikro-sosial-ekonomi dalam ekonomi dinamis " masa transisi”, hierarki elit dan kelompok etnis, masyarakat dan pemilih, fisiologi dan jiwa manusia, ekosistem alam dan buatan, dan banyak lainnya.

Cukup signifikan bahwa pada pertengahan 80-an, sekolah I.Prigozhin mengembangkan pendekatan, yang menurutnya dalam pengembangan sistem apa pun (termasuk seseorang), periode bergantian di mana sistem berperilaku baik sebagai "kebanyakan deterministik", atau sebagai "kebanyakan acak." Secara alami, sistem kontrol nyata harus secara stabil mengelola objek kontrol tidak hanya pada bagian "deterministik" dari sejarahnya, tetapi juga pada titik-titik ketika perilaku selanjutnya menjadi sangat tidak pasti. Ini saja berarti bahwa perlu untuk mengembangkan pendekatan untuk pengelolaan sistem dalam perilaku yang ada elemen besar keacakan (atau apa yang saat ini secara matematis digambarkan sebagai "keacakan").

Oleh karena itu, komposisi sistem kontrol otomatis yang menjanjikan yang menyediakan kontrol sistem deterministik lemah multi-parameter dinamis yang kompleks, sebagai tautan fungsional penting, tampaknya akan mencakup subsistem untuk mengidentifikasi dan memprediksi keadaan lingkungan dan objek kontrol, berdasarkan metode kecerdasan buatan. (terutama pengenalan pola), metode pendukung pengambilan keputusan dan teori informasi.

Mari kita pertimbangkan secara singkat masalah penggunaan sistem pengenalan gambar untuk membuat keputusan tentang tindakan kontrol (masalah ini akan dibahas lebih rinci nanti, karena ini adalah kunci untuk pekerjaan ini). Jika kita mengambil target dan keadaan lain dari objek kontrol sebagai kelas pengenalan, dan faktor-faktor yang mempengaruhinya sebagai fitur, maka ukuran hubungan antara faktor dan keadaan dapat dibentuk dalam model pengenalan pola. Ini memungkinkan memperoleh informasi tentang faktor-faktor yang berkontribusi atau menghalangi transisinya ke keadaan ini, berdasarkan keadaan tertentu dari objek kontrol, dan, atas dasar ini, mengembangkan keputusan tentang tindakan kontrol.

Faktor-faktor tersebut dapat dibagi menjadi beberapa kelompok berikut:

• mengkarakterisasi prasejarah objek kontrol;
• mengkarakterisasi keadaan objek kontrol saat ini;
• faktor lingkungan;
• faktor teknologi (dikelola).

Dengan demikian, sistem pengenalan gambar dapat digunakan sebagai bagian dari sistem kontrol otomatis: dalam subsistem untuk mengidentifikasi keadaan objek kontrol dan menghasilkan tindakan kontrol.

Ini berguna ketika objek kontrol adalah sistem yang kompleks.

Membuat keputusan tentang tindakan kontrol dalam sistem kontrol otomatis

Solusi dari masalah sintesis sistem kontrol otomatis adaptif oleh sistem yang kompleks dibahas dalam makalah ini, dengan mempertimbangkan banyak analogi yang mendalam antara metode pengenalan pola dan pengambilan keputusan.

Di satu sisi, tugas pengenalan pola adalah keputusan tentang kepemilikan objek yang dapat dikenali ke kelas pengenalan tertentu.

Di sisi lain, penulis mengusulkan untuk mempertimbangkan masalah pengambilan keputusan sebagai masalah kebalikan dari decoding atau masalah kebalikan dari pengenalan pola (lihat bagian 2.2.2).

Kesamaan ide-ide dasar yang mendasari metode pengenalan pola dan pengambilan keputusan menjadi sangat jelas ketika mempertimbangkannya dari sudut pandang teori informasi.

Berbagai tugas pengambilan keputusan

Pengambilan keputusan sebagai realisasi dari sebuah tujuan

Definisi: membuat keputusan ("pilihan") adalah tindakan pada serangkaian alternatif, sebagai akibatnya rangkaian alternatif awal menyempit, mis. itu berkurang.

Pilihan adalah tindakan yang memberikan tujuan pada semua aktivitas. Melalui tindakan pilihan bahwa subordinasi dari semua kegiatan untuk tujuan tertentu atau satu set tujuan yang saling terkait diwujudkan.

Jadi, agar tindakan pilihan menjadi mungkin, berikut ini diperlukan:

• generasi atau penemuan satu set alternatif untuk membuat pilihan;
• penentuan tujuan untuk pencapaian pilihan yang dibuat;
• pengembangan dan penerapan metode untuk membandingkan alternatif satu sama lain, yaitu penentuan peringkat preferensi untuk setiap alternatif menurut kriteria tertentu, memungkinkan secara tidak langsung menilai bagaimana setiap alternatif memenuhi tujuan.

Pekerjaan modern di bidang pendukung keputusan telah mengungkapkan situasi karakteristik, yang terdiri dari fakta bahwa formalisasi lengkap untuk menemukan solusi terbaik (dalam arti tertentu) hanya mungkin untuk masalah yang dipelajari dengan baik dan relatif sederhana, sedangkan dalam praktiknya, masalah terstruktur lemah lebih umum, yang algoritma yang sepenuhnya diformalkan belum dikembangkan (kecuali untuk enumerasi lengkap dan coba-coba). Namun, para profesional yang berpengalaman, kompeten, dan cakap sering kali membuat pilihan yang ternyata cukup bagus. Oleh karena itu, tren saat ini dalam praktik pengambilan keputusan dalam situasi alami adalah menggabungkan kemampuan seseorang untuk memecahkan masalah yang tidak formal dengan kemampuan metode formal dan pemodelan komputer: sistem pendukung keputusan interaktif, sistem pakar, adaptif manusia-mesin otomatis. sistem kontrol, jaringan saraf, dan sistem kognitif.

Pengambilan keputusan sebagai penghilangan ketidakpastian (pendekatan informasi)

Proses memperoleh informasi dapat dianggap sebagai penurunan ketidakpastian sebagai akibat dari penerimaan sinyal, dan jumlah informasi - sebagai ukuran kuantitatif dari tingkat penghapusan ketidakpastian.

Tetapi sebagai hasil dari memilih beberapa subset alternatif dari set, yaitu sebagai akibat dari pengambilan keputusan, hal yang sama terjadi (penurunan ketidakpastian). Ini berarti bahwa setiap pilihan, setiap keputusan menghasilkan sejumlah informasi tertentu, dan oleh karena itu dapat dijelaskan dalam istilah teori informasi.

Klasifikasi masalah pengambilan keputusan

Banyaknya tugas pengambilan keputusan disebabkan oleh fakta bahwa setiap komponen situasi di mana pengambilan keputusan dilakukan dapat diimplementasikan dengan cara yang berbeda secara kualitatif.

Berikut adalah beberapa opsi ini:

• himpunan alternatif, di satu sisi, bisa terbatas, dapat dihitung atau terus-menerus, dan di sisi lain, itu bisa tertutup (yaitu, diketahui sepenuhnya) atau terbuka (termasuk elemen yang tidak diketahui);
• evaluasi alternatif dapat dilakukan menurut satu atau lebih kriteria, yang, pada gilirannya, dapat kuantitatif atau kualitatif;
• mode pilihan bisa tunggal (satu kali), atau ganda, berulang, termasuk umpan balik atas hasil pilihan, yaitu. memungkinkan pembelajaran algoritma pengambilan keputusan, dengan mempertimbangkan konsekuensi dari pemilihan sebelumnya;
• konsekuensi dari memilih setiap alternatif dapat diketahui secara pasti sebelumnya (choice under Certainty), memiliki sifat probabilistik ketika probabilitas hasil yang mungkin terjadi setelah pilihan dibuat (choice under risk) atau memiliki hasil yang ambigu dengan probabilitas yang tidak diketahui (choice under ketidakpastian). );
• tanggung jawab untuk pilihan mungkin tidak ada, menjadi individu atau kelompok;
• tingkat konsistensi tujuan dalam pilihan kelompok dapat bervariasi dari kepentingan pihak-pihak yang kebetulan sepenuhnya (pilihan kooperatif) hingga kebalikannya (pilihan dalam situasi konflik). Pilihan menengah juga dimungkinkan: kompromi, koalisi, konflik yang berkembang atau memudar.

Berbagai kombinasi dari pilihan-pilihan ini menyebabkan banyak masalah pengambilan keputusan yang telah dipelajari pada tingkat yang berbeda-beda.

Bahasa untuk menggambarkan metode pengambilan keputusan

Satu dan fenomena yang sama dapat dibicarakan dalam bahasa yang berbeda dengan berbagai tingkat keumuman dan kecukupan. Sampai saat ini, ada tiga bahasa utama untuk menggambarkan pilihan.

Yang paling sederhana, paling berkembang dan paling populer adalah bahasa kriteria.

Bahasa kriteria

Nama bahasa ini dikaitkan dengan asumsi dasar bahwa setiap alternatif individu dapat dievaluasi oleh beberapa (satu) nomor tertentu, setelah itu perbandingan alternatif direduksi menjadi perbandingan nomor yang sesuai.

Misalkan, (X) adalah himpunan alternatif, dan x adalah beberapa alternatif pasti yang termasuk dalam himpunan ini: x∈X. Kemudian dianggap bahwa untuk semua x suatu fungsi q(x) dapat diberikan, yang disebut kriteria (kriteria kualitas, fungsi tujuan, fungsi preferensi, fungsi utilitas, dll.), yang memiliki sifat bahwa jika alternatif x 1 adalah lebih disukai daripada x 2 (dilambangkan: x 1 > x 2), lalu q (x 1) > q (x 2).

Dalam hal ini, pilihan direduksi menjadi mencari alternatif dengan nilai tertinggi dari fungsi kriteria.

Namun, dalam praktiknya, penggunaan hanya satu kriteria untuk membandingkan tingkat preferensi alternatif ternyata merupakan penyederhanaan yang tidak dapat dibenarkan, karena pertimbangan alternatif yang lebih rinci mengarah pada kebutuhan untuk mengevaluasinya tidak menurut satu, tetapi menurut banyak orang. kriteria yang dapat bersifat berbeda dan secara kualitatif berbeda satu sama lain.

Misalnya, ketika memilih jenis pesawat yang paling dapat diterima untuk penumpang dan organisasi operasi pada jenis rute tertentu, perbandingan dilakukan secara bersamaan sesuai dengan banyak kelompok kriteria: teknis, teknologi, ekonomi, sosial, ergonomis, dll.

Masalah multikriteria tidak memiliki solusi umum yang unik. Oleh karena itu, banyak cara yang diusulkan untuk memberikan masalah multikriteria bentuk tertentu yang memungkinkan solusi umum tunggal. Secara alami, solusi ini umumnya berbeda untuk metode yang berbeda. Oleh karena itu, mungkin hal utama dalam memecahkan masalah multikriteria adalah pembenaran jenis perumusannya.

Berbagai pilihan untuk menyederhanakan masalah seleksi multikriteria digunakan. Mari kita daftar beberapa dari mereka.

1. Maksimisasi bersyarat (bukan ekstrem global dari kriteria integral yang ditemukan, tetapi ekstrem lokal dari kriteria utama).
2. Cari alternatif dengan properti yang diberikan.
3. Menemukan himpunan Pareto.
4. Pengurangan masalah multikriteria menjadi satu kriteria dengan memperkenalkan kriteria integral.

Mari kita pertimbangkan secara lebih rinci formulasi formal metode pengurangan masalah multi-kriteria menjadi satu kriteria.

Kami memperkenalkan kriteria integral q 0 (x) sebagai fungsi skalar dari argumen vektor:

q 0 (x) = q 0 ((q 1 (x), q 2 (x), ..., q n (x)).

Kriteria integral memungkinkan pengurutan alternatif dengan q 0 , dengan demikian menyoroti yang terbaik (dalam pengertian kriteria ini). Bentuk fungsi q 0 ditentukan oleh seberapa spesifik kita membayangkan kontribusi setiap kriteria terhadap kriteria integral. Biasanya fungsi aditif dan perkalian digunakan:

q 0 = a i q i /s i

1 - q 0 = (1 - b i q i /s i)

Koefisien yang saya berikan:

1. Tanpa dimensi atau satu dimensi dari bilangan a i q i /s i (kriteria tertentu yang berbeda mungkin memiliki dimensi yang berbeda, dan kemudian tidak mungkin untuk melakukan operasi aritmatika pada mereka dan mereduksinya menjadi kriteria integral).
2. Normalisasi, mis. ketentuan kondisi: b i q i /s i<1.

Koefisien a i dan b i mencerminkan kontribusi relatif dari kriteria tertentu q i terhadap kriteria integral.

Jadi, dalam pengaturan multi-kriteria, masalah pengambilan keputusan untuk memilih salah satu alternatif direduksi menjadi memaksimalkan kriteria integral:

x * = arg max(q 0 (q 1 (x), q 2 (x), ..., q n (x)))

Masalah utama dalam perumusan multikriteria dari masalah pengambilan keputusan adalah bahwa perlu untuk menemukan bentuk analitik dari koefisien a i dan b i , yang akan memberikan sifat-sifat model berikut:

• tingkat kecukupan yang tinggi dari bidang studi dan sudut pandang para ahli;
• kesulitan komputasi minimal dalam memaksimalkan kriteria integral, yaitu perhitungannya untuk alternatif yang berbeda;
• stabilitas hasil memaksimalkan kriteria integral dari gangguan kecil dari data awal.
• Stabilitas solusi berarti bahwa perubahan kecil pada data awal harus menyebabkan perubahan kecil dalam nilai kriteria integral, dan, dengan demikian, perubahan kecil dalam keputusan yang dibuat. Jadi, jika data awal praktis sama, maka keputusan harus dibuat sama atau sangat dekat.

Bahasa Seleksi Biner Sekuensial

Bahasa hubungan biner adalah generalisasi dari bahasa multikriteria dan didasarkan pada kenyataan bahwa ketika kita mengevaluasi beberapa alternatif, penilaian ini selalu relatif, yaitu. secara eksplisit atau lebih sering secara implisit, alternatif lain dari himpunan yang diteliti atau dari populasi umum digunakan sebagai dasar atau kerangka acuan untuk perbandingan. Pemikiran manusia didasarkan pada pencarian dan analisis yang berlawanan (konstruk), sehingga selalu lebih mudah bagi kita untuk memilih salah satu dari dua opsi yang berlawanan daripada satu opsi dari himpunan yang besar dan sama sekali tidak teratur.

Dengan demikian, asumsi utama bahasa ini bermuara pada hal berikut:

• satu alternatif tidak dievaluasi, mis. fungsi kriteria tidak diperkenalkan;
• untuk setiap pasangan alternatif, dapat ditentukan dengan cara tertentu bahwa salah satunya lebih disukai daripada yang lain, atau bahwa mereka setara atau tidak dapat dibandingkan;
• hubungan preferensi dalam setiap pasangan alternatif tidak bergantung pada alternatif lain yang disajikan untuk pilihan.

Ada berbagai cara untuk menentukan hubungan biner: langsung, matriks, menggunakan grafik preferensi, metode bagian, dll.

Hubungan antara alternatif satu pasangan diekspresikan melalui konsep ekivalensi, keteraturan, dan dominasi.

Fungsi bahasa pilihan umum

Bahasa fungsi pilihan didasarkan pada teori himpunan dan memungkinkan seseorang untuk beroperasi dengan pemetaan himpunan ke himpunan bagiannya yang sesuai dengan pilihan yang berbeda tanpa perlu menghitung elemen. Bahasa ini sangat umum dan berpotensi memungkinkan pilihan apa pun untuk dijelaskan. Namun, peralatan matematika fungsi pilihan umum saat ini sedang dikembangkan dan diuji terutama pada masalah yang telah diselesaikan dengan menggunakan kriteria atau pendekatan biner.

pilihan kelompok

Biarlah ada sekelompok orang yang memiliki hak untuk mengambil bagian dalam pengambilan keputusan kolektif. Misalkan kelompok ini sedang mempertimbangkan beberapa set alternatif, dan setiap anggota kelompok membuat pilihannya sendiri. Tugasnya adalah mengembangkan solusi yang dengan cara tertentu mengoordinasikan pilihan individu dan dalam arti tertentu mengungkapkan "pendapat umum" kelompok, yaitu. diambil sebagai pilihan kelompok.

Secara alami, keputusan kelompok yang berbeda akan sesuai dengan prinsip yang berbeda untuk mengoordinasikan keputusan individu.

Aturan untuk mengoordinasikan keputusan individu dalam pilihan kelompok disebut aturan pemungutan suara. Yang paling umum adalah "aturan mayoritas", di mana keputusan kelompok diambil oleh alternatif yang menerima suara terbanyak.

Harus dipahami bahwa keputusan seperti itu hanya mencerminkan prevalensi sudut pandang yang berbeda dalam kelompok, dan bukan pilihan yang benar-benar optimal, yang tidak boleh dipilih sama sekali oleh siapa pun. "Kebenaran tidak ditentukan oleh pemungutan suara."

Selain itu, ada yang disebut "paradoks pemungutan suara", yang paling terkenal adalah paradoks Arrow.

Paradoks-paradoks ini dapat menyebabkan, dan kadang-kadang memang mengarah, ke fitur yang sangat tidak menyenangkan dari prosedur pemungutan suara: misalnya, ada kasus ketika kelompok tidak dapat membuat keputusan sama sekali (tidak ada kuorum atau semua orang memberikan suara untuk opsi unik mereka sendiri, dll. .), dan terkadang ( dalam pemungutan suara bertingkat) minoritas dapat memaksakan kehendaknya pada mayoritas.

Pilihan di bawah Ketidakpastian

Kepastian adalah kasus khusus dari ketidakpastian, yaitu: ketidakpastian mendekati nol.

Dalam teori pilihan modern, diyakini bahwa ada tiga jenis ketidakpastian utama dalam masalah pengambilan keputusan:

1. Ketidakpastian informasional (statistik) dari data awal untuk pengambilan keputusan.
2. Ketidakpastian konsekuensi dari pengambilan keputusan (pilihan).
3. Ketidakjelasan dalam deskripsi komponen proses pengambilan keputusan.

Mari kita pertimbangkan mereka secara berurutan.

Ketidakpastian informasi (statistik) dalam data awal

Data yang diperoleh tentang area subjek tidak dapat dianggap benar-benar akurat. Selain itu, jelas bahwa data ini menarik bagi kita bukan untuk dirinya sendiri, tetapi hanya sebagai sinyal yang, mungkin, membawa informasi tertentu tentang apa yang benar-benar kita minati. Jadi, lebih realistis untuk mempertimbangkan bahwa kita berurusan dengan data yang tidak hanya berisik dan tidak akurat, tetapi juga tidak langsung, dan mungkin tidak lengkap. Selain itu, data ini tidak menyangkut seluruh populasi (umum) yang diteliti, tetapi hanya sebagian tertentu darinya, yang sebenarnya dapat kami kumpulkan datanya, tetapi pada saat yang sama kami ingin menarik kesimpulan tentang seluruh populasi, dan kami juga ingin mengetahui tingkat keandalan kesimpulan ini.

Dalam kondisi ini, teori keputusan statistik digunakan.

Ada dua sumber utama ketidakpastian dalam teori ini. Pertama, tidak diketahui distribusi apa yang dipatuhi oleh data asli. Kedua, tidak diketahui distribusi apa yang memiliki himpunan (populasi umum) yang ingin kita tarik kesimpulan dari himpunan bagiannya yang membentuk data awal.

Prosedur statistik adalah prosedur pengambilan keputusan yang menghilangkan kedua jenis ketidakpastian ini.

Perlu dicatat bahwa ada sejumlah alasan yang menyebabkan penerapan metode statistik yang salah:

• kesimpulan statistik, seperti yang lainnya, selalu memiliki keandalan atau kepastian yang pasti. Namun, tidak seperti banyak kasus lainnya, keandalan temuan statistik diketahui dan ditentukan dalam penelitian statistik;
• kualitas solusi yang diperoleh sebagai hasil penerapan prosedur statistik tergantung pada kualitas data awal;
• data yang tidak bersifat statistik tidak boleh diproses secara statistik;
• perlu menggunakan prosedur statistik yang sesuai dengan tingkat informasi apriori tentang populasi yang diteliti (misalnya, Anda tidak boleh menerapkan metode analisis varians pada data non-Gaussian). Jika distribusi data asli tidak diketahui, maka seseorang harus menetapkannya, atau menggunakan beberapa metode berbeda dan membandingkan hasilnya. Jika mereka sangat berbeda, ini menunjukkan tidak dapat diterapkannya beberapa prosedur yang digunakan.

Ketidakpastian Konsekuensi

Ketika konsekuensi dari memilih alternatif secara unik ditentukan oleh alternatif itu sendiri, maka kita tidak dapat membedakan antara alternatif dan konsekuensinya, menerima begitu saja bahwa memilih alternatif, kita benar-benar memilih konsekuensinya.

Namun, dalam praktik nyata, seseorang sering kali harus menghadapi situasi yang lebih kompleks, ketika pilihan satu atau alternatif lain secara ambigu menentukan konsekuensi dari pilihan yang dibuat.

Dalam kasus satu set diskrit alternatif dan hasil pilihan mereka, asalkan himpunan hasil yang mungkin adalah umum untuk semua alternatif, kita dapat mengasumsikan bahwa alternatif yang berbeda berbeda satu sama lain dalam distribusi probabilitas hasil. Distribusi probabilitas ini, dalam kasus umum, mungkin bergantung pada hasil pilihan alternatif dan hasil yang sebenarnya terjadi sebagai akibat dari ini. Dalam kasus yang paling sederhana, hasilnya sama-sama mungkin. Hasil itu sendiri biasanya memiliki arti keuntungan atau kerugian dan diukur.

Jika hasilnya sama untuk semua alternatif, maka tidak ada yang bisa dipilih. Jika mereka berbeda, maka alternatif dapat dibandingkan dengan memperkenalkan perkiraan kuantitatif tertentu untuk mereka. Keragaman masalah dalam teori permainan dikaitkan dengan pilihan karakteristik numerik yang berbeda dari kerugian dan keuntungan sebagai akibat dari pilihan alternatif, tingkat konflik yang berbeda antara pihak yang memilih alternatif, dll.

Pertimbangkan jenis ketidakpastian ini sebagai ketidakpastian yang tidak jelas

Setiap masalah pilihan adalah penyempitan tujuan dari kumpulan alternatif. Baik deskripsi formal alternatif (daftarnya sendiri, daftar atribut atau parameternya) dan deskripsi aturan untuk perbandingannya (kriteria, hubungan) selalu diberikan dalam satu atau lain skala pengukuran (bahkan ketika orang yang apakah ini tidak tahu tentang ini).

Diketahui bahwa semua skala kabur, tetapi pada tingkat yang berbeda-beda. Istilah "kabur" mengacu pada properti timbangan, yang terdiri dari kenyataan bahwa selalu mungkin untuk menyajikan dua alternatif yang dapat dibedakan, yaitu. berbeda dalam satu skala dan tidak dapat dibedakan, yaitu identik, di sisi lain - lebih kabur. Semakin sedikit gradasi dalam skala tertentu, semakin kabur.

Dengan demikian, kita dapat dengan jelas melihat alternatif dan pada saat yang sama mengklasifikasikannya secara samar, yaitu. menjadi ambigu untuk kelas mana mereka berasal.

Sudah dalam karya pertama mereka tentang pengambilan keputusan dalam situasi kabur, Bellman dan Zadeh mengajukan gagasan bahwa tujuan dan kendala harus direpresentasikan sebagai himpunan kabur (kabur) pada serangkaian alternatif.

Pada beberapa keterbatasan pendekatan optimasi

Dalam semua masalah pemilihan dan metode pengambilan keputusan yang dipertimbangkan di atas, masalahnya adalah menemukan yang terbaik di set awal dalam kondisi tertentu, yaitu. alternatif yang optimal dalam arti tertentu.

Ide optimalitas adalah ide sentral dari sibernetika dan telah dengan kuat memasuki praktik merancang dan mengoperasikan sistem teknis. Pada saat yang sama, gagasan ini membutuhkan sikap hati-hati ketika kita mencoba mentransfernya ke bidang pengelolaan sistem yang kompleks, besar, dan ditentukan secara lemah, seperti misalnya, sistem sosial-ekonomi.

Ada alasan bagus untuk kesimpulan ini. Mari kita pertimbangkan beberapa di antaranya:

1. Solusi optimal seringkali ternyata tidak stabil, mis. perubahan kecil dalam kondisi masalah, input data atau kendala dapat menyebabkan pemilihan alternatif yang berbeda secara signifikan.
2. Model optimasi dikembangkan hanya untuk kelas sempit dari tugas yang cukup sederhana yang tidak selalu secara memadai dan sistematis mencerminkan objek kontrol nyata. Paling sering, metode optimasi memungkinkan untuk mengoptimalkan hanya subsistem yang cukup sederhana dan dijelaskan secara formal dari beberapa sistem besar dan kompleks, mis. memungkinkan hanya optimasi lokal. Namun, jika setiap subsistem dari beberapa sistem besar bekerja secara optimal, ini tidak berarti bahwa sistem secara keseluruhan juga akan bekerja secara optimal. Oleh karena itu, optimasi subsistem tidak selalu mengarah pada perilakunya, yang diperlukan ketika mengoptimalkan sistem secara keseluruhan. Selain itu, terkadang optimasi lokal dapat menyebabkan konsekuensi negatif bagi sistem secara keseluruhan. Oleh karena itu, ketika mengoptimalkan subsistem dan sistem secara keseluruhan, perlu untuk menentukan pohon tujuan dan subtujuan serta prioritasnya.
3. Seringkali, memaksimalkan kriteria optimasi menurut beberapa model matematika dianggap sebagai tujuan optimasi, tetapi pada kenyataannya tujuannya adalah untuk mengoptimalkan objek kontrol. Kriteria optimasi dan model matematika selalu berhubungan dengan tujuan hanya secara tidak langsung, yaitu kurang lebih memadai, tetapi selalu mendekati.

Dengan demikian, gagasan optimalitas, yang sangat bermanfaat untuk sistem yang memungkinkan formalisasi matematis yang memadai, harus ditransfer ke sistem yang kompleks dengan hati-hati. Tentu saja, model matematika yang terkadang dapat diusulkan untuk sistem seperti itu dapat dioptimalkan. Namun, kita harus selalu mempertimbangkan penyederhanaan yang kuat dari model-model ini, yang dalam kasus sistem yang kompleks tidak dapat lagi diabaikan, serta fakta bahwa tingkat kecukupan model ini dalam kasus sistem yang kompleks sebenarnya tidak diketahui. . Oleh karena itu, tidak diketahui apa arti praktis dari pengoptimalan ini. Kepraktisan tinggi optimasi dalam sistem teknis seharusnya tidak menimbulkan ilusi bahwa itu akan sama efektifnya dalam mengoptimalkan sistem yang kompleks. Pemodelan matematika yang berarti dari sistem yang kompleks sangat sulit, perkiraan dan tidak akurat. Semakin kompleks sistemnya, semakin berhati-hati tentang ide pengoptimalannya.

Oleh karena itu, ketika mengembangkan metode kontrol untuk sistem yang kompleks, besar, dan ditentukan dengan lemah, penulis mempertimbangkan hal utama tidak hanya optimalitas pendekatan yang dipilih dari sudut pandang matematika formal, tetapi juga kecukupannya untuk tujuan dan sifat alami dari objek kontrol.

Metode Seleksi Ahli

Dalam studi sistem yang kompleks, masalah sering muncul yang, karena berbagai alasan, tidak dapat diajukan dan diselesaikan secara ketat menggunakan peralatan matematika yang dikembangkan saat ini. Dalam kasus ini, layanan pakar (analis sistem) digunakan, yang pengalaman dan intuisinya membantu mengurangi kompleksitas masalah.

Namun, harus diperhitungkan bahwa para ahli itu sendiri adalah sistem yang sangat kompleks, dan aktivitas mereka juga bergantung pada banyak kondisi eksternal dan internal. Oleh karena itu, dalam metode pengorganisasian penilaian ahli, banyak perhatian diberikan untuk menciptakan kondisi eksternal dan psikologis yang menguntungkan bagi pekerjaan para ahli.

Faktor-faktor berikut mempengaruhi pekerjaan seorang ahli:

• tanggung jawab atas penggunaan hasil pemeriksaan;
• mengetahui bahwa ahli lain terlibat;
• ketersediaan informasi kontak antar ahli;
• hubungan interpersonal para ahli (jika ada kontak informasi di antara mereka);
• kepentingan pribadi ahli dalam hasil penilaian;
• kualitas pribadi para ahli (harga diri, konformitas, kemauan, dll.)

Interaksi antara para ahli dapat merangsang atau menghambat aktivitas mereka. Oleh karena itu, dalam kasus yang berbeda, metode pemeriksaan yang berbeda digunakan, yang berbeda dalam sifat interaksi para ahli satu sama lain: survei dan kuesioner anonim dan terbuka, rapat, diskusi, permainan bisnis, curah pendapat, dll.

Ada berbagai metode pengolahan matematis pendapat ahli. Para ahli diminta untuk mengevaluasi berbagai alternatif baik dengan satu atau dengan sistem indikator. Selain itu, mereka diminta untuk mengevaluasi tingkat kepentingan setiap indikator ("bobot" atau "kontribusinya"). Para ahli itu sendiri juga diberi tingkat kompetensi yang sesuai dengan kontribusi mereka masing-masing terhadap pendapat kelompok yang dihasilkan.

Metode yang dikembangkan untuk bekerja dengan para ahli adalah metode "Delphi". Ide utama dari metode ini adalah bahwa kritik dan argumentasi memiliki efek menguntungkan pada ahli, jika harga dirinya tidak terpengaruh dan kondisi disediakan yang mengecualikan konfrontasi pribadi.

Harus ditekankan bahwa ada perbedaan mendasar dalam sifat penggunaan metode pakar dalam sistem pakar dan dalam pendukung keputusan. Jika dalam kasus pertama, para ahli diminta untuk memformalkan metode pengambilan keputusan, maka dalam kasus kedua - hanya keputusan itu sendiri, seperti itu.

Karena para ahli terlibat dalam implementasi fungsi-fungsi yang saat ini tidak disediakan oleh sistem otomatis sama sekali, atau dilakukan lebih buruk daripada oleh manusia, arah yang menjanjikan dalam pengembangan sistem otomatis adalah otomatisasi maksimum dari fungsi-fungsi ini.

Sistem pendukung keputusan otomatis

Seseorang selalu menggunakan asisten dalam membuat keputusan: mereka hanyalah penyedia informasi tentang objek kontrol, dan konsultan (penasihat) yang menawarkan opsi untuk keputusan dan menganalisis konsekuensinya. Orang yang membuat keputusan selalu membuatnya dalam lingkungan informasi tertentu: untuk komandan militer, ini adalah markas, untuk rektor, dewan akademik, untuk menteri, untuk kolegium.

Saat ini, infrastruktur informasi pengambilan keputusan tidak terpikirkan tanpa sistem otomatis untuk evaluasi keputusan berulang, dan terutama sistem pendukung keputusan (DDS - Sistem Pendukung Keputusan), yaitu. sistem otomatis yang dirancang khusus untuk menyiapkan informasi yang dibutuhkan seseorang untuk membuat keputusan. Pengembangan sistem pendukung keputusan dilakukan, khususnya, dalam kerangka proyek internasional yang dilakukan di bawah naungan Institut Internasional untuk Analisis Sistem Terapan di Laxenburg (Austria).

Pilihan dalam situasi nyata membutuhkan kinerja sejumlah operasi, beberapa di antaranya dilakukan lebih efisien oleh seseorang, dan lainnya oleh mesin. Kombinasi yang efektif dari keuntungan mereka dengan kompensasi kekurangan simultan diwujudkan dalam sistem pendukung keputusan otomatis.

Seseorang membuat keputusan lebih baik daripada mesin di bawah kondisi ketidakpastian, tetapi untuk membuat keputusan yang tepat, ia juga membutuhkan informasi yang memadai (lengkap dan andal) yang menjadi ciri area subjek. Namun, diketahui bahwa seseorang tidak dapat mengatasi dengan baik sejumlah besar informasi "mentah" yang belum diproses. Oleh karena itu, peran mesin dalam pendukung keputusan mungkin untuk melakukan persiapan awal informasi tentang objek kontrol dan faktor-faktor yang tidak dapat dikendalikan (lingkungan), untuk membantu melihat konsekuensi dari pengambilan keputusan tertentu, dan juga untuk menyajikan semua informasi ini secara visual. dan cara yang nyaman untuk membuat keputusan.

Dengan demikian, sistem pendukung keputusan otomatis mengkompensasi kelemahan seseorang, membebaskannya dari pemrosesan awal informasi yang rutin, dan memberinya lingkungan informasi yang nyaman di mana ia dapat menunjukkan kekuatannya dengan lebih baik. Sistem ini tidak terfokus pada otomatisasi fungsi pembuat keputusan (dan, sebagai akibatnya, mengasingkan fungsi-fungsi ini darinya, dan karenanya tanggung jawab atas keputusan yang dibuat, yang seringkali tidak dapat diterima), tetapi pada penyediaan bantuan untuk menemukan solusi yang baik.

Sistem kehidupan, termasuk manusia, secara konstan dihadapkan pada tugas pengenalan pola sejak awal. Secara khusus, informasi yang berasal dari organ indera diproses oleh otak, yang, pada gilirannya, menyortir informasi, memastikan pengambilan keputusan, dan kemudian, menggunakan impuls elektrokimia, mentransmisikan sinyal yang diperlukan lebih lanjut, misalnya, ke organ gerakan. , yang mengimplementasikan tindakan yang diperlukan. Kemudian terjadi perubahan lingkungan, dan fenomena di atas terjadi lagi. Dan jika Anda perhatikan, maka setiap tahap disertai dengan pengakuan.

Dengan perkembangan teknologi komputer, menjadi mungkin untuk memecahkan sejumlah masalah yang muncul dalam proses kehidupan, untuk memudahkan, mempercepat, meningkatkan kualitas hasil. Misalnya, pengoperasian berbagai sistem pendukung kehidupan, interaksi manusia-komputer, munculnya sistem robot, dll. Namun, kami mencatat bahwa saat ini tidak mungkin untuk memberikan hasil yang memuaskan dalam beberapa tugas (pengenalan objek serupa yang bergerak cepat , teks tulisan tangan).

Tujuan pekerjaan: untuk mempelajari sejarah sistem pengenalan pola.

Menunjukkan perubahan kualitatif yang terjadi di bidang pengenalan pola, baik teoretis maupun teknis, dengan menunjukkan alasannya;

Diskusikan metode dan prinsip yang digunakan dalam komputasi;

Berikan contoh prospek yang diharapkan dalam waktu dekat.

1. Apa itu pengenalan pola?

Studi pertama dengan teknologi komputer pada dasarnya mengikuti skema klasik pemodelan matematika - model matematika, algoritma dan perhitungan. Ini adalah tugas pemodelan proses yang terjadi selama ledakan bom atom, menghitung lintasan balistik, aplikasi ekonomi dan lainnya. Namun, selain ide klasik dari seri ini, ada juga metode yang didasarkan pada sifat yang sama sekali berbeda, dan seperti yang ditunjukkan oleh praktik penyelesaian beberapa masalah, mereka sering memberikan hasil yang lebih baik daripada solusi berdasarkan model matematika yang terlalu rumit. Ide mereka adalah untuk meninggalkan keinginan untuk membuat model matematis lengkap dari objek yang diteliti (selain itu, seringkali praktis tidak mungkin untuk membangun model yang memadai), dan bukannya puas dengan jawaban hanya untuk pertanyaan spesifik yang menarik bagi kami, dan jawaban-jawaban ini harus dicari dari pertimbangan-pertimbangan yang umum hingga kelas masalah yang luas. Penelitian semacam ini mencakup pengenalan citra visual, peramalan hasil, ketinggian sungai, masalah membedakan antara bantalan minyak dan akuifer menggunakan data geofisika tidak langsung, dll. Jawaban spesifik dalam tugas ini diperlukan dalam bentuk yang agak sederhana, seperti, misalnya, apakah suatu objek termasuk dalam salah satu kelas yang telah diperbaiki sebelumnya. Dan data awal dari tugas-tugas ini, sebagai suatu peraturan, diberikan dalam bentuk informasi terpisah-pisah tentang objek yang diteliti, misalnya, dalam bentuk satu set objek yang telah diklasifikasikan sebelumnya. Dari sudut pandang matematis, ini berarti bahwa pengenalan pola (dan kelas masalah ini dinamai di negara kita) adalah generalisasi luas dari gagasan ekstrapolasi fungsi.

Pentingnya formulasi semacam itu untuk ilmu-ilmu teknis tidak diragukan lagi, dan ini dengan sendirinya membenarkan banyak penelitian di bidang ini. Namun, masalah pengenalan pola juga memiliki aspek yang lebih luas untuk ilmu pengetahuan alam (namun, akan aneh jika sesuatu yang begitu penting untuk sistem sibernetik buatan tidak penting untuk yang alami). Konteks ilmu ini secara organik mencakup pertanyaan yang diajukan oleh para filsuf kuno tentang sifat pengetahuan kita, kemampuan kita untuk mengenali gambar, pola, situasi dunia di sekitar kita. Faktanya, praktis tidak ada keraguan bahwa mekanisme untuk mengenali gambar paling sederhana, seperti gambar pemangsa atau makanan berbahaya yang mendekat, terbentuk jauh lebih awal daripada bahasa dasar dan perangkat logika formal muncul. Dan tidak ada keraguan bahwa mekanisme seperti itu juga cukup berkembang pada hewan tingkat tinggi, yang, dalam aktivitas vitalnya, juga sangat membutuhkan kemampuan untuk membedakan sistem tanda-tanda alam yang agak rumit. Jadi, di alam, kita melihat bahwa fenomena berpikir dan kesadaran jelas didasarkan pada kemampuan untuk mengenali pola, dan kemajuan lebih lanjut dari ilmu kecerdasan berhubungan langsung dengan kedalaman pemahaman tentang hukum dasar pengenalan. Memahami fakta bahwa pertanyaan-pertanyaan di atas jauh melampaui definisi standar pengenalan pola (dalam literatur bahasa Inggris, istilah pembelajaran yang diawasi lebih umum), perlu juga dipahami bahwa mereka memiliki hubungan yang dalam dengan ini yang relatif sempit (tetapi masih jauh). dari kelelahan) arah.

Bahkan sekarang, pengenalan pola telah memasuki kehidupan sehari-hari dengan kuat dan merupakan salah satu pengetahuan paling penting dari seorang insinyur modern. Dalam kedokteran, pengenalan pola membantu dokter membuat diagnosis yang lebih akurat; di pabrik, pengenalan pola digunakan untuk memprediksi cacat pada batch barang. Sistem identifikasi pribadi biometrik sebagai inti algoritmiknya juga didasarkan pada hasil disiplin ini. Pengembangan lebih lanjut dari kecerdasan buatan, khususnya desain komputer generasi kelima yang mampu berkomunikasi lebih langsung dengan seseorang dalam bahasa alami untuk orang-orang dan melalui ucapan, tidak terpikirkan tanpa pengenalan. Di sini, robotika, sistem kontrol buatan yang berisi sistem pengenalan sebagai subsistem vital, mudah dijangkau.

Itulah sebabnya banyak perhatian tertuju pada pengembangan pengenalan pola sejak awal oleh para spesialis dari berbagai profil - sibernetika, neurofisiologis, psikolog, matematikawan, ekonom, dll. Sebagian besar karena alasan ini, pengenalan pola modern itu sendiri didasarkan pada ide-ide dari disiplin ini. Tanpa mengklaim lengkap (dan tidak mungkin mengklaimnya dalam esai pendek), kami akan menjelaskan sejarah pengenalan pola, ide-ide kunci.

definisi

Sebelum melanjutkan ke metode utama pengenalan pola, kami memberikan beberapa definisi yang diperlukan.

Pengenalan gambar (objek, sinyal, situasi, fenomena, atau proses) adalah tugas untuk mengidentifikasi objek atau menentukan propertinya berdasarkan gambarnya (pengenalan optik) atau rekaman audio (pengenalan akustik) dan karakteristik lainnya.

Salah satu yang mendasar adalah konsep himpunan yang tidak memiliki rumusan khusus. Di komputer, satu set diwakili oleh satu set elemen yang tidak berulang dari jenis yang sama. Kata "tidak berulang" berarti bahwa beberapa elemen dalam himpunan ada atau tidak ada. Himpunan universal mencakup semua elemen yang mungkin untuk masalah yang diselesaikan, himpunan kosong tidak mengandung apapun.

Citra adalah suatu pengelompokan klasifikasi dalam suatu sistem klasifikasi yang menyatukan (single out) suatu kelompok objek tertentu menurut beberapa atribut. Gambar memiliki sifat khas, yang memanifestasikan dirinya dalam kenyataan bahwa kenalan dengan sejumlah fenomena terbatas dari himpunan yang sama memungkinkan untuk mengenali sejumlah besar perwakilannya secara sewenang-wenang. Gambar memiliki sifat objektif yang khas dalam arti bahwa orang yang berbeda yang belajar dari bahan pengamatan yang berbeda, sebagian besar, mengklasifikasikan objek yang sama dengan cara yang sama dan secara independen satu sama lain. Dalam rumusan klasik masalah pengenalan, himpunan semesta dibagi menjadi bagian-gambar. Setiap pemetaan objek apa pun ke organ penerima dari sistem pengenalan, terlepas dari posisinya relatif terhadap organ-organ ini, biasanya disebut gambar objek, dan kumpulan gambar tersebut, disatukan oleh beberapa sifat umum, adalah gambar.

Metode menugaskan elemen ke gambar apa pun disebut aturan keputusan. Konsep penting lainnya adalah metrik, cara untuk menentukan jarak antara elemen-elemen dari himpunan universal. Semakin kecil jarak ini, semakin mirip objek (simbol, suara, dll.) yang kita kenal. Biasanya, elemen ditentukan sebagai kumpulan angka, dan metrik ditentukan sebagai fungsi. Efisiensi program tergantung pada pilihan representasi gambar dan implementasi metrik, satu algoritma pengenalan dengan metrik yang berbeda akan membuat kesalahan dengan frekuensi yang berbeda.

Belajar biasanya disebut proses mengembangkan dalam beberapa sistem reaksi tertentu terhadap kelompok sinyal identik eksternal dengan berulang kali mempengaruhi sistem koreksi eksternal. Penyesuaian eksternal seperti itu dalam pelatihan biasanya disebut "dorongan" dan "hukuman". Mekanisme untuk menghasilkan penyesuaian ini hampir sepenuhnya menentukan algoritma pembelajaran. Belajar mandiri berbeda dari belajar di sini informasi tambahan tentang ketepatan reaksi terhadap sistem tidak dilaporkan.

Adaptasi adalah proses mengubah parameter dan struktur sistem, dan mungkin juga mengontrol tindakan, berdasarkan informasi terkini untuk mencapai keadaan sistem tertentu dengan ketidakpastian awal dan kondisi operasi yang berubah.

Belajar adalah suatu proses, sebagai akibatnya sistem secara bertahap memperoleh kemampuan untuk merespons dengan reaksi yang diperlukan terhadap serangkaian pengaruh eksternal tertentu, dan adaptasi adalah penyesuaian parameter dan struktur sistem untuk mencapai kualitas yang diperlukan. kontrol dalam kondisi perubahan terus menerus dalam kondisi eksternal.

Contoh tugas pengenalan pola: - Pengenalan huruf;

Dan tanda-tanda. Tugas seperti itu cukup sering diselesaikan, misalnya, saat menyeberang atau mengemudi di lampu lalu lintas. Mengenali warna lampu lalu lintas yang menyala dan mengetahui aturan jalan memungkinkan Anda membuat keputusan yang tepat tentang apakah akan menyeberang jalan atau tidak saat ini.

Dalam proses evolusi biologis, banyak hewan memecahkan masalah dengan bantuan alat visual dan pendengaran. pengenalan pola cukup baik. Pembuatan sistem buatan pengenalan pola tetap menjadi masalah teoretis dan teknis yang sulit. Kebutuhan akan pengakuan semacam itu muncul di berbagai bidang - mulai dari urusan militer dan sistem keamanan hingga digitalisasi semua jenis sinyal analog.

Secara tradisional, tugas pengenalan gambar termasuk dalam lingkup tugas kecerdasan buatan.

Arah dalam pengenalan pola

Ada dua arah utama:

• Studi tentang kemampuan pengenalan yang dimiliki makhluk hidup, penjelasan dan pemodelannya;
• Pengembangan teori dan metode untuk membangun perangkat yang dirancang untuk memecahkan masalah individu dalam masalah terapan.

Pernyataan resmi dari masalah

Pengenalan pola adalah penugasan data awal ke kelas tertentu dengan menyoroti fitur penting yang mencirikan data ini dari total massa data non-esensial.

Ketika mengatur masalah pengenalan, mereka mencoba menggunakan bahasa matematika, mencoba, tidak seperti teori jaringan saraf tiruan, di mana dasarnya adalah untuk mendapatkan hasil melalui percobaan, untuk menggantikan percobaan dengan penalaran logis dan bukti matematis.

Paling sering, gambar monokrom dipertimbangkan dalam masalah pengenalan pola, yang memungkinkan untuk mempertimbangkan gambar sebagai fungsi pada bidang. Jika kita mempertimbangkan set titik di pesawat T, dimana fungsi x(x,kamu) mengekspresikan pada setiap titik gambar karakteristiknya - kecerahan, transparansi, kerapatan optik, maka fungsi seperti itu adalah catatan formal gambar.

Himpunan semua fungsi yang mungkin x(x,kamu) di permukaan T- ada model kumpulan semua gambar X. Memperkenalkan konsep kesamaan antara gambar, Anda dapat mengatur tugas pengenalan. Bentuk khusus dari pengaturan tersebut sangat tergantung pada tahap-tahap selanjutnya dalam pengenalan sesuai dengan satu atau lain pendekatan.

Metode pengenalan pola

Untuk pengenalan gambar optik, Anda dapat menerapkan metode iterasi pada jenis objek pada berbagai sudut, skala, offset, dll. Untuk huruf, Anda perlu mengulangi font, properti font, dll.

Pendekatan kedua adalah menemukan kontur objek dan memeriksa propertinya (konektivitas, keberadaan sudut, dll.)

Pendekatan lain adalah dengan menggunakan jaringan saraf tiruan. Metode ini memerlukan sejumlah besar contoh tugas pengenalan (dengan jawaban yang benar), atau struktur jaringan saraf khusus yang memperhitungkan kekhususan tugas ini.

Perceptron sebagai metode pengenalan pola

F. Rosenblatt, memperkenalkan konsep model otak, yang tugasnya menunjukkan bagaimana fenomena psikologis dapat muncul dalam beberapa sistem fisik, yang struktur dan sifat fungsionalnya diketahui - dijelaskan paling sederhana eksperimen diskriminasi. Eksperimen ini sepenuhnya terkait dengan metode pengenalan pola, tetapi berbeda karena algoritma solusi tidak deterministik.

Eksperimen paling sederhana, atas dasar yang memungkinkan untuk memperoleh informasi yang signifikan secara psikologis tentang sistem tertentu, bermuara pada fakta bahwa model disajikan dengan dua rangsangan berbeda dan diperlukan untuk menanggapinya dengan cara yang berbeda. Tujuan dari eksperimen tersebut mungkin untuk mempelajari kemungkinan diskriminasi spontan mereka oleh sistem tanpa adanya intervensi dari eksperimen, atau, sebaliknya, untuk mempelajari diskriminasi paksa, di mana eksperimen berusaha untuk mengajarkan sistem untuk melaksanakan klasifikasi yang diperlukan.

Dalam eksperimen pembelajaran, perceptron biasanya disajikan dengan urutan gambar tertentu, yang mencakup perwakilan dari masing-masing kelas untuk dibedakan. Menurut beberapa aturan modifikasi memori, pilihan reaksi yang benar diperkuat. Kemudian stimulus kontrol dipresentasikan ke perceptron dan probabilitas memperoleh respon yang benar untuk stimulus kelas ini ditentukan. Bergantung pada apakah stimulus kontrol yang dipilih cocok atau tidak cocok dengan salah satu gambar yang digunakan dalam urutan pelatihan, hasil yang berbeda diperoleh:

• 1. Jika stimulus kontrol tidak sesuai dengan stimulus belajar mana pun, maka eksperimen tidak hanya dikaitkan dengan diskriminasi murni, tetapi juga termasuk elemen generalisasi.
• 2. Jika stimulus kontrol menggairahkan seperangkat elemen sensorik tertentu yang sama sekali berbeda dari elemen-elemen yang diaktifkan di bawah pengaruh rangsangan yang disajikan sebelumnya dari kelas yang sama, maka eksperimen adalah studi generalisasi murni .

Perceptron tidak memiliki kapasitas untuk generalisasi murni, tetapi mereka berfungsi cukup memuaskan dalam eksperimen diskriminasi, terutama jika stimulus kontrol cukup cocok dengan salah satu pola yang telah dikumpulkan oleh perceptron beberapa pengalaman.

Contoh masalah pengenalan pola

• Pengenalan huruf.
• Pengenalan kode batang.
• Pengenalan plat nomor.
• Pengenalan wajah.
• Pengenalan suara.
• Pengenalan gambar.
• Pengakuan daerah lokal kerak bumi di mana deposit mineral berada.

Program pengenalan pola

Lihat juga

Catatan

Tautan

• Yuri Lifshit. Kursus "Masalah Modern Informatika Teoretis" - kuliah tentang metode statistik pengenalan pola, pengenalan wajah, klasifikasi teks
• Jurnal Penelitian Pengenalan Pola (Journal of Pattern Recognition Research)

literatur

• David A. Forsyth, Jean Pons Visi komputer. Pendekatan Modern = Computer Vision: Pendekatan Modern. - M.: "Williams", 2004. - S. 928. - ISBN 0-13-085198-1
• George Stockman, Linda Shapiro Visi komputer = Visi Komputer. - M.: Binom. Laboratorium Pengetahuan, 2006. - S.752. - ISBN 5947743841

• A.L. Gorelik, V.A. Skripkin, Metode Pengakuan, M.: Sekolah Tinggi, 1989.
• S.-K. Cheng, Prinsip-prinsip desain sistem informasi visual, M.: Mir, 1994.

Yayasan Wikimedia. 2010 .

- dalam teknologi, arah ilmiah dan teknis yang terkait dengan pengembangan metode dan konstruksi sistem (termasuk berbasis komputer) untuk menetapkan kepemilikan suatu objek (subjek, proses, fenomena, situasi, sinyal) ke salah satu dari pra ... ... Kamus Ensiklopedis Besar

Salah satu daerah baru sibernetika. Isi dari teori R. tentang. adalah ekstrapolasi properti objek (gambar) milik beberapa kelas ke objek yang dekat dengan mereka dalam arti tertentu. Biasanya, ketika mengajar robot R. tentang. ada ... ... Ensiklopedia Geologi

Bahasa inggris pengakuan, gambar; Jerman Gestalt alterkennung. Cabang dari sibernetika matematika yang mengembangkan prinsip dan metode untuk mengklasifikasikan dan mengidentifikasi objek yang dijelaskan oleh serangkaian fitur terbatas yang menjadi ciri mereka. Antinazi. Ensiklopedia ... ... Ensiklopedia Sosiologi

Pengenalan pola- metode mempelajari objek kompleks dengan bantuan komputer; terdiri dari pemilihan fitur dan pengembangan algoritma dan program yang memungkinkan komputer untuk secara otomatis mengklasifikasikan objek menurut fitur ini. Misalnya untuk menentukan ... ... Kamus Ekonomi dan Matematika

- (teknis), arah ilmiah dan teknis yang terkait dengan pengembangan metode dan konstruksi sistem (termasuk yang berbasis komputer) untuk menetapkan kepemilikan suatu objek (subjek, proses, fenomena, situasi, sinyal) ke salah satu sebelum ... ... kamus ensiklopedis

PENGENALAN POLA- bagian dari sibernetika matematika yang mengembangkan metode untuk mengklasifikasikan, serta mengidentifikasi objek, fenomena, proses, sinyal, situasi dari semua objek yang dapat dijelaskan oleh serangkaian fitur atau properti tertentu yang terbatas, ... ... Ensiklopedia sosiologi Rusia

pengenalan pola- 160 pengenalan pola: Identifikasi representasi bentuk dan konfigurasi menggunakan cara otomatis

• tutorial

Untuk waktu yang lama saya ingin menulis artikel umum yang berisi dasar-dasar Pengenalan Gambar, semacam panduan tentang metode dasar, memberi tahu kapan harus menerapkannya, tugas apa yang mereka selesaikan, apa yang bisa dilakukan di malam hari di lutut, dan apa yang lebih baik untuk tidak dipikirkan tanpa memiliki tim yang terdiri dari 20 orang.

Saya telah menulis beberapa artikel tentang Pengenalan Optik untuk waktu yang lama, jadi beberapa kali sebulan berbagai orang menulis kepada saya dengan pertanyaan tentang topik ini. Terkadang Anda merasa bahwa Anda hidup bersama mereka di dunia yang berbeda. Di satu sisi, Anda memahami bahwa seseorang kemungkinan besar adalah seorang profesional dalam topik terkait, tetapi hanya tahu sedikit tentang metode pengenalan optik. Dan hal yang paling menjengkelkan adalah dia mencoba menerapkan metode dari bidang pengetahuan terdekat, yang logis, tetapi tidak berfungsi sepenuhnya dalam Pengenalan Gambar, tetapi tidak memahami ini dan sangat tersinggung jika dia mulai mengatakan sesuatu kepadanya dari awal. sangat mendasar. Dan mengingat menceritakan dari dasar adalah banyak waktu, yang seringkali tidak ada, itu menjadi lebih menyedihkan.

Artikel ini dirancang agar seseorang yang belum pernah berurusan dengan metode pengenalan gambar dapat, dalam 10-15 menit, membuat di kepalanya gambaran dasar tertentu tentang dunia yang sesuai dengan topik, dan memahami ke arah mana ia harus menggali. Banyak metode yang dijelaskan di sini dapat diterapkan pada radar dan pemrosesan audio.
Saya akan mulai dengan beberapa prinsip yang selalu kami sampaikan kepada calon pelanggan, atau orang yang ingin mulai melakukan Pengenalan Optik:

• Saat memecahkan masalah, selalu lakukan dari yang paling sederhana. Jauh lebih mudah untuk menggantung label oranye pada seseorang daripada mengikuti seseorang, menyorotnya dalam kaskade. Jauh lebih mudah untuk mengambil kamera dengan resolusi lebih tinggi daripada mengembangkan algoritme resolusi super.
• Pernyataan masalah yang ketat dalam metode pengenalan optik adalah urutan besarnya lebih penting daripada dalam masalah pemrograman sistem: satu kata tambahan di TK dapat menambahkan 50% dari pekerjaan.
• Dalam masalah pengenalan, tidak ada solusi universal. Anda tidak dapat membuat algoritme yang hanya akan "mengenali prasasti apa pun." Tanda di jalan dan selembar teks pada dasarnya adalah objek yang berbeda. Mungkin saja membuat algoritme umum (ini adalah contoh bagus dari Google), tetapi ini akan membutuhkan banyak pekerjaan dari tim besar dan terdiri dari lusinan subrutin yang berbeda.
• OpenCV adalah alkitab, yang memiliki banyak metode, dan dengannya Anda dapat menyelesaikan 50% dari volume hampir semua masalah, tetapi OpenCV hanyalah sebagian kecil dari apa yang dapat dilakukan dalam kenyataan. Dalam satu penelitian, tertulis dalam kesimpulan: "Masalahnya tidak diselesaikan dengan metode OpenCV, oleh karena itu, tidak dapat dipecahkan." Cobalah untuk menghindari hal ini, jangan malas dan dengan bijaksana mengevaluasi tugas saat ini setiap kali dari awal, tanpa menggunakan template OpenCV.

Sangat sulit untuk memberikan semacam saran universal, atau memberi tahu cara membuat semacam struktur di mana Anda dapat membangun solusi untuk masalah penglihatan komputer yang sewenang-wenang. Tujuan artikel ini adalah untuk menyusun apa yang dapat digunakan. Saya akan mencoba memecah metode yang ada menjadi tiga kelompok. Kelompok pertama adalah pra-penyaringan dan persiapan gambar. Kelompok kedua adalah pemrosesan logis dari hasil penyaringan. Kelompok ketiga adalah algoritma pengambilan keputusan berdasarkan pemrosesan logis. Batas antar kelompok sangat arbitrer. Untuk memecahkan suatu masalah, jauh dari selalu perlu menerapkan metode dari semua kelompok; kadang-kadang dua cukup, dan kadang-kadang bahkan satu.

Daftar metode yang disajikan di sini tidak lengkap. Saya mengusulkan untuk menambahkan dalam komentar metode kritis yang saya tidak menulis dan atribut 2-3 kata yang menyertainya untuk masing-masing.

Bagian 1. Penyaringan

Dalam grup ini, saya menempatkan metode yang memungkinkan Anda memilih area yang menarik dalam gambar tanpa menganalisisnya. Sebagian besar metode ini menerapkan beberapa jenis transformasi seragam ke semua titik dalam gambar. Pada tingkat pemfilteran, citra tidak dianalisis, tetapi titik-titik yang difilter dapat dianggap sebagai area dengan karakteristik khusus.

Binerisasi ambang batas, pemilihan area histogram

Transformasi paling sederhana adalah binarisasi gambar dengan ambang batas. Untuk gambar RGB dan skala abu-abu, ambang batas adalah nilai warna. Ada masalah ideal di mana transformasi seperti itu sudah cukup. Misalkan Anda ingin memilih item secara otomatis pada selembar kertas putih:




Pilihan ambang di mana binarisasi berlangsung sangat menentukan proses binarisasi itu sendiri. Dalam hal ini, gambar dibinerisasi dengan warna rata-rata. Biasanya, binarisasi dilakukan dengan algoritma yang secara adaptif memilih ambang batas. Algoritma semacam itu bisa menjadi pilihan harapan atau mode. Dan Anda dapat memilih puncak histogram terbesar.

Binarisasi dapat memberikan hasil yang sangat menarik ketika bekerja dengan histogram, termasuk situasi jika kita mempertimbangkan gambar tidak dalam RGB, tetapi dalam HSV. Misalnya, segmen warna yang menarik. Berdasarkan prinsip ini, dimungkinkan untuk membuat detektor label dan detektor kulit manusia.

Pemfilteran klasik: Fourier, LPF, HPF

Metode penyaringan klasik dari radar dan pemrosesan sinyal dapat berhasil diterapkan dalam berbagai tugas Pengenalan Pola. Metode tradisional di radar, yang hampir tidak pernah digunakan dalam gambar dalam bentuk murni, adalah transformasi Fourier (lebih khusus, FFT). Salah satu dari sedikit pengecualian di mana transformasi Fourier 1D digunakan adalah kompresi gambar. Untuk analisis gambar, transformasi satu dimensi biasanya tidak cukup, Anda perlu menggunakan transformasi dua dimensi yang jauh lebih intensif sumber daya.

Hanya sedikit orang yang benar-benar menghitungnya, biasanya jauh lebih cepat dan lebih mudah menggunakan konvolusi wilayah yang diinginkan dengan filter siap pakai yang dipertajam ke frekuensi tinggi (HPF) atau rendah (LPF). Metode seperti itu, tentu saja, tidak memungkinkan analisis spektrum, tetapi dalam tugas pemrosesan video tertentu, biasanya bukan analisis yang diperlukan, tetapi hasil.


Contoh paling sederhana dari filter yang menekankan frekuensi rendah (filter Gaussian) dan frekuensi tinggi (filter Gabor).
Untuk setiap titik gambar, sebuah jendela dipilih dan dikalikan dengan filter dengan ukuran yang sama. Hasil dari konvolusi tersebut adalah nilai baru dari titik tersebut. Saat mengimplementasikan LPF dan HPF, gambar jenis ini diperoleh:

Wavelet

Tetapi bagaimana jika kita menggunakan beberapa fungsi karakteristik arbitrer untuk konvolusi dengan sinyal? Kemudian akan disebut "Transformasi Wavelet". Definisi wavelet ini tidak benar, tetapi secara tradisional, di banyak tim, analisis wavelet adalah pencarian pola arbitrer dalam gambar menggunakan konvolusi dengan model pola ini. Ada satu set fungsi klasik yang digunakan dalam analisis wavelet. Ini termasuk wavelet Haar, wavelet Morlet, wavelet topi Meksiko, dan seterusnya. Primitif Haar, yang tentangnya ada beberapa artikel saya sebelumnya ( , ), merujuk pada fungsi seperti itu untuk ruang dua dimensi.


Di atas adalah 4 contoh wavelet klasik. Wavelet Haar 3D, wavelet Meyer 2D, wavelet Topi Meksiko, wavelet Daubechies. Contoh yang baik untuk menggunakan interpretasi yang diperluas dari wavelet adalah masalah menemukan kilatan di mata, di mana kilau itu sendiri adalah wavelet:

Wavelet klasik biasanya digunakan untuk kompresi gambar, atau untuk klasifikasinya (akan dijelaskan di bawah).

Korelasi

Setelah interpretasi bebas dari wavelet di pihak saya, perlu disebutkan korelasi aktual yang mendasarinya. Saat memfilter gambar, ini adalah alat yang sangat diperlukan. Aplikasi klasik adalah korelasi aliran video untuk menemukan offset atau aliran optik. Detektor pergeseran paling sederhana juga, dalam arti tertentu, merupakan korelator perbedaan. Di mana gambar tidak berkorelasi, ada gerakan.

Pemfilteran fungsi

Kelas filter yang menarik adalah fungsi penyaringan. Ini adalah filter matematika murni yang memungkinkan Anda mendeteksi fungsi matematika sederhana dalam gambar (garis, parabola, lingkaran). Gambar akumulatif dibangun, di mana untuk setiap titik gambar asli, satu set fungsi yang menghasilkannya digambar. Transformasi yang paling klasik adalah transformasi Hough untuk garis. Dalam transformasi ini, untuk setiap titik (x;y), satu set titik (a;b) dari garis y=ax+b digambar, yang persamaannya benar. Dapatkan gambar yang indah:


(nilai tambah pertama untuk orang yang pertama menemukan tangkapan dalam gambar dan definisi semacam itu dan menjelaskannya, nilai tambah kedua untuk orang yang pertama mengatakan apa yang ditunjukkan di sini)
Transformasi Hough memungkinkan Anda menemukan fungsi yang dapat diparameterisasi. Misalnya lingkaran. Ada transformasi yang dimodifikasi yang memungkinkan Anda mencari bentuk apa pun. Transformasi ini sangat disukai para matematikawan. Tetapi saat memproses gambar, sayangnya, tidak selalu berhasil. Kecepatan sangat lambat, sensitivitas sangat tinggi terhadap kualitas binarisasi. Bahkan dalam situasi ideal, saya lebih suka bertahan dengan metode lain.
Rekan dari transformasi Hough untuk garis adalah transformasi Radon. Ini dihitung melalui FFT, yang memberikan peningkatan kinerja dalam situasi di mana ada banyak poin. Selain itu, dapat diterapkan pada gambar non-binerisasi.

Penyaringan kontur

Kelas filter yang terpisah adalah filter perbatasan dan kontur. Path sangat berguna ketika kita ingin berpindah dari bekerja dengan gambar ke bekerja dengan objek di gambar itu. Ketika suatu objek cukup kompleks, tetapi dibedakan dengan baik, maka seringkali satu-satunya cara untuk bekerja dengannya adalah dengan memilih konturnya. Ada sejumlah algoritma yang memecahkan masalah pemfilteran kontur:

Yang paling umum digunakan adalah Kenny, yang bekerja dengan baik dan yang implementasinya di OpenCV (Sobel juga ada, tetapi dia mencari kontur yang lebih buruk).

Filter lainnya

Di atas adalah filter, modifikasi yang membantu menyelesaikan 80-90% tugas. Tapi selain itu, ada filter yang lebih jarang digunakan dalam tugas lokal. Ada lusinan filter seperti itu, saya tidak akan mencantumkan semuanya. Yang menarik adalah filter iteratif (misalnya, model penampilan aktif), serta transformasi ridgelet dan curvlet, yang merupakan paduan penyaringan dan analisis wavelet klasik di bidang transformasi radon. Transformasi beamlet bekerja dengan baik pada batas transformasi wavelet dan analisis logis, memungkinkan Anda untuk menyorot kontur:

Tetapi transformasi ini sangat spesifik dan disesuaikan untuk tugas-tugas langka.

Bagian 2. Pemrosesan logis dari hasil penyaringan

Penyaringan memberikan satu set data yang cocok untuk diproses. Namun seringkali Anda tidak bisa begitu saja mengambil dan menggunakan data ini tanpa memprosesnya. Di bagian ini, akan ada beberapa metode klasik yang memungkinkan Anda beralih dari gambar ke properti objek, atau ke objek itu sendiri.

Morfologi

Transisi dari filtering ke logika, menurut saya, adalah metode morfologi matematika ( , , ). Faktanya, ini adalah operasi paling sederhana untuk meningkatkan dan mengikis gambar biner. Metode ini memungkinkan Anda untuk menghilangkan noise dari gambar biner dengan menambah atau mengurangi elemen yang tersedia. Berdasarkan morfologi matematis, terdapat algoritma contouring, tetapi biasanya mereka menggunakan beberapa jenis algoritma hybrid atau algoritma dalam hubungannya.

analisis kontur

Di bagian penyaringan, algoritma untuk mendapatkan batas telah disebutkan. Batas yang dihasilkan cukup sederhana diubah menjadi kontur. Untuk algoritma Canny ini terjadi secara otomatis, untuk algoritma lain diperlukan binarisasi tambahan. Anda bisa mendapatkan kontur untuk algoritma biner, misalnya, dengan algoritma kumbang.
Kontur merupakan ciri khas suatu objek. Seringkali ini memungkinkan Anda untuk mengidentifikasi objek di sepanjang kontur. Ada alat matematika yang kuat yang memungkinkan Anda melakukan ini. Alat tersebut disebut analisis kontur ( , ).

Sejujurnya, saya belum pernah berhasil menerapkan analisis kontur dalam masalah nyata. Kondisi yang terlalu ideal diperlukan. Entah tidak ada perbatasan, atau ada terlalu banyak kebisingan. Namun, jika Anda perlu mengenali sesuatu dalam kondisi ideal, maka analisis kontur adalah pilihan yang bagus. Ia bekerja sangat cepat, matematika yang indah dan logika yang dapat dimengerti.

Poin tunggal

Keypoint adalah karakteristik unik dari suatu objek yang memungkinkan objek untuk diasosiasikan dengan dirinya sendiri atau dengan kelas objek yang serupa. Ada lusinan cara untuk memilih titik tersebut. Beberapa metode menyorot titik khusus dalam bingkai yang berdekatan, beberapa setelah jangka waktu yang lama dan saat pencahayaan berubah, beberapa memungkinkan Anda menemukan titik khusus yang tetap demikian bahkan ketika objek berputar. Mari kita mulai dengan metode yang memungkinkan kita menemukan titik khusus yang tidak begitu stabil, tetapi dihitung dengan cepat, dan kemudian kita akan meningkatkan kompleksitas:
Kelas satu. Poin tunggal yang stabil selama beberapa detik. Titik tersebut digunakan untuk memandu objek antara bingkai video yang berdekatan, atau untuk menyatukan gambar dari kamera tetangga. Titik-titik ini termasuk maxima lokal dari gambar, sudut dalam gambar (detektor terbaik, mungkin, detektor Haris), titik di mana dispersi maxima tercapai, gradien tertentu, dll.
Kelas kedua. Titik tunggal yang stabil saat mengubah pencahayaan dan gerakan kecil objek. Poin-poin tersebut berfungsi terutama untuk pelatihan dan klasifikasi tipe objek selanjutnya. Misalnya, pengklasifikasi pejalan kaki atau pengklasifikasi wajah adalah produk dari sistem yang dibangun hanya pada titik-titik tersebut. Beberapa dari wavelet yang disebutkan sebelumnya mungkin menjadi dasar untuk poin tersebut. Misalnya, Haar primitif, pencarian silau, pencarian fitur spesifik lainnya. Titik-titik ini termasuk titik-titik yang ditemukan dengan metode histogram gradien arah (HOG).
Kelas ke tiga. titik stabil. Saya hanya tahu tentang dua metode yang memberikan stabilitas lengkap dan tentang modifikasinya. Ini adalah SURF dan SIFT. Mereka memungkinkan Anda untuk menemukan poin-poin penting bahkan ketika Anda memutar gambar. Perhitungan poin tersebut membutuhkan waktu lebih lama dari metode lain, tetapi untuk waktu yang agak terbatas. Sayangnya, metode ini dipatenkan. Meskipun, di Rusia tidak mungkin untuk mematenkan algoritma, jadi gunakan untuk pasar domestik.

Bagian 3. Pelatihan

Bagian ketiga dari cerita akan dikhususkan untuk metode yang tidak bekerja secara langsung dengan gambar, tetapi yang memungkinkan Anda untuk membuat keputusan. Pada dasarnya, ini adalah berbagai metode pembelajaran mesin dan pengambilan keputusan. Baru-baru ini, Yandyks memposting kursus tentang topik ini di Habr, ada pilihan yang sangat bagus di sana. Ini dia dalam versi teks. Untuk studi serius tentang subjek, saya sangat menyarankan Anda melihatnya. Disini saya akan mencoba mengidentifikasi beberapa metode dasar yang digunakan secara khusus dalam pengenalan pola.
Dalam 80% situasi, esensi pembelajaran dalam masalah pengenalan adalah sebagai berikut:
Ada sampel uji di mana ada beberapa kelas objek. Biarlah ada / tidaknya seseorang di foto. Untuk setiap gambar, terdapat sekumpulan fitur yang telah ditonjolkan oleh beberapa fitur, baik itu Haar, HOG, SURF, atau beberapa wavelet. Algoritma pembelajaran harus membangun model seperti itu, yang menurutnya akan dapat menganalisis gambar baru dan memutuskan objek mana yang ada dalam gambar.
Bagaimana itu dilakukan? Setiap gambar uji adalah titik di ruang fitur. Koordinatnya adalah bobot setiap fitur dalam gambar. Biarkan tanda-tanda kami menjadi: "Kehadiran mata", "Kehadiran hidung", "Kehadiran dua tangan", "Kehadiran telinga", dll. Kami akan mengalokasikan semua tanda ini dengan detektor yang kami miliki, yang dilatih pada bagian tubuh yang mirip dengan manusia. Untuk seseorang di ruang seperti itu, titik yang benar adalah . Untuk monyet, titik untuk kuda. Pengklasifikasi dilatih pada sampel contoh. Tetapi tidak semua foto menunjukkan tangan, yang lain tidak memiliki mata, dan pada foto ketiga monyet memiliki hidung manusia karena kesalahan pengklasifikasi. Pengklasifikasi manusia yang dapat dilatih secara otomatis membagi ruang fitur sedemikian rupa untuk mengatakan: jika fitur pertama terletak pada kisaran 0,5 Pada intinya, tujuan dari pengklasifikasi adalah untuk menggambar di ruang fitur karakteristik area dari objek klasifikasi. Ini adalah bagaimana aproksimasi berturut-turut untuk jawaban untuk salah satu pengklasifikasi (AdaBoost) dalam ruang dua dimensi akan terlihat seperti:


Ada banyak pengklasifikasi. Masing-masing bekerja lebih baik dalam beberapa tugasnya. Tugas memilih pengklasifikasi untuk tugas tertentu sebagian besar merupakan seni. Berikut adalah beberapa gambar bagus tentang topik ini.

Kasing sederhana, pemisahan satu dimensi

Mari kita ambil contoh kasus klasifikasi yang paling sederhana, ketika ruang fitur adalah satu dimensi, dan kita perlu memisahkan 2 kelas. Situasi ini terjadi lebih sering daripada yang terlihat: misalnya, ketika Anda perlu membedakan dua sinyal, atau membandingkan pola dengan sampel. Katakanlah kita memiliki sampel pelatihan. Dalam hal ini, gambar diperoleh, di mana sumbu X akan menjadi ukuran kesamaan, dan sumbu Y akan menjadi jumlah peristiwa dengan ukuran tersebut. Ketika objek yang diinginkan mirip dengan dirinya sendiri, diperoleh Gaussian kiri. Bila tidak mirip - benar. Nilai X=0,4 memisahkan sampel sehingga keputusan yang salah meminimalkan kemungkinan membuat keputusan yang salah. Ini adalah pencarian pemisah seperti itu yang merupakan tugas klasifikasi.


Catatan kecil. Kriteria yang meminimalkan kesalahan tidak akan selalu optimal. Grafik berikut adalah grafik sistem pengenalan iris mata yang sebenarnya. Untuk sistem seperti itu, kriteria dipilih sedemikian rupa untuk meminimalkan kemungkinan salah masuknya orang luar ke objek. Probabilitas seperti itu disebut "kesalahan jenis pertama", "probabilitas alarm palsu", "positif palsu". Dalam literatur bahasa Inggris "False Access Rate".
) AdaBusta adalah salah satu pengklasifikasi yang paling umum. Misalnya, kaskade Haar dibangun di atasnya. Biasanya digunakan ketika klasifikasi biner diperlukan, tetapi tidak ada yang menghalangi pengajaran untuk lebih banyak kelas.
SVM ( , , , ) Salah satu pengklasifikasi paling kuat dengan banyak implementasi. Pada prinsipnya, pada tugas-tugas pembelajaran yang saya temui, cara kerjanya mirip dengan adabusta. Ini dianggap cukup cepat, tetapi pelatihannya lebih sulit daripada Adabusta dan membutuhkan pilihan kernel yang benar.

Ada juga jaringan saraf dan regresi. Tetapi untuk mengklasifikasikan mereka secara singkat dan menunjukkan perbedaannya, diperlukan artikel yang jauh lebih besar dari ini.
________________________________________________
Saya harap saya dapat memberikan gambaran singkat tentang metode yang digunakan tanpa menyelami matematika dan deskripsi. Mungkin ini akan membantu seseorang. Meskipun, tentu saja, artikelnya tidak lengkap dan tidak ada sepatah kata pun tentang bekerja dengan gambar stereo, atau tentang LSM dengan filter Kalman, atau tentang pendekatan Bayesian yang adaptif.
Jika Anda menyukai artikel ini, maka saya akan mencoba membuat bagian kedua dengan pilihan contoh bagaimana masalah ImageRecognition yang ada diselesaikan.

Dan akhirnya

Apa yang harus dibaca?
1) Suatu ketika saya sangat menyukai buku "Digital Image Processing" oleh B. Yana, yang ditulis dengan sederhana dan jelas, tetapi pada saat yang sama hampir semua matematika diberikan. Baik untuk membiasakan diri dengan metode yang ada.
2) Genre klasik adalah R Gonzalez, R. Woods "Pemrosesan Gambar Digital". Untuk beberapa alasan, itu lebih sulit bagi saya daripada yang pertama. Lebih sedikit matematika, tetapi lebih banyak metode dan gambar.
3) "Pemrosesan dan analisis gambar dalam masalah penglihatan mesin" - ditulis berdasarkan kursus yang diajarkan di salah satu departemen PhysTech. Banyak metode dan deskripsi rincinya. Tapi menurut saya, buku ini memiliki dua kekurangan besar: buku ini sangat fokus pada paket perangkat lunak yang menyertainya, dalam buku itu terlalu sering deskripsi metode sederhana berubah menjadi hutan matematika, dari mana sulit untuk mengambilnya. keluar diagram struktural dari metode. Tetapi penulis telah membuat situs yang nyaman, di mana hampir semua konten disajikan - wiki.technicalvision.ru Tambahkan tag