Metode tetangga terdekat: contoh kerja

metode tetangga terdekat adalah metrik classifier termudah yang didasarkan pada evaluasi kesamaan objek yang berbeda.

objek dianalisis termasuk kelas mana mereka berasal subyek sampel pelatihan. Mari kita cari tahu yang merupakan tetangga terdekat. Cobalah untuk memahami masalah rumit, contoh teknik yang berbeda.

metode hipotesis

Metode tetangga terdekat dapat dianggap sebagai algoritma yang paling umum digunakan untuk klasifikasi. Obyek menjalani klasifikasi milik y_i kelas, yang objek terdekat belajar sampel x_i.

Spesifisitas metode tetangga terdekat

k metode tetangga terdekat dapat meningkatkan akurasi klasifikasi. objek dianalisis milik kelas yang sama seperti sebagian besar negara tetangga, yaitu, k dekat dengan itu objek dari sampel x_i dianalisis. Dalam memecahkan masalah dengan dua kelas dari jumlah tetangga akan aneh untuk menghindari situasi ambiguitas, jika jumlah yang sama dari tetangga akan menjadi milik kelas yang berbeda.

Teknik tetangga ditangguhkan

Metode postgresql-dianalisis tsvector tetangga terdekat digunakan ketika jumlah kelas setidaknya tiga, dan Anda tidak dapat menggunakan angka ganjil. Tapi ambiguitas muncul bahkan dalam kasus ini. Kemudian, tetangga-i mendapat berat badan w_i, yang menurun dengan tetangga peringkat i. Hal ini mengacu pada kelas objek, yang akan memiliki berat total maksimum antara tetangga dekat.

Hipotesis kekompakan

Di jantung semua metode di atas adalah hipotesis dari kekompakan. Ini menunjukkan hubungan antara ukuran kesamaan objek dan mereka yang termasuk dalam kelas yang sama. Dalam situasi ini, batas antara berbagai jenis adalah bentuk sederhana, dan membuat kelas dari objek dalam ruang wilayah ponsel kompak. Di bawah daerah seperti dalam analisis matematika diartikan satu set dibatasi ditutup. hipotesis ini tidak berhubungan dengan persepsi sehari-hari kata.

Rumus dasar

Mari kita meneliti lebih tetangga terdekat. Jika pelatihan yang diusulkan jenis sampel "objek-respon» X ^ m = \ {(x_1, y_1), \ titik, (x_m, y_m) \}; jika pluralitas objek untuk menentukan jarak fungsi \ rho (x, x '), yang diwakili dalam bentuk model kesamaan yang memadai benda dengan meningkatkan nilai fungsi menurun kesamaan antara objek x, x'.

Untuk objek apapun, u akan membangun sebuah sampel pelatihan benda x_i dengan meningkatnya jarak ke u:

\ Rho (u, x_ {1; u}) \ leq \ rho (u, x_ {2; u}) \ leq \ cdots \ leq \ rho (u, x_ {m; u}),

mana x_ {i; u} mencirikan sampel pembelajaran objek, yang ke-i sumber tetangga objek u. notasi dan penggunaan tersebut untuk membalas i-th tetangga: y_ {i; u}. Sebagai hasilnya, kami menemukan bahwa setiap objek u memprovokasi remunerasi sampel sendiri.

Penentuan jumlah k tetangga

Metode tetangga terdekat ketika k = 1 mampu memberikan klasifikasi yang salah, tidak hanya pada objek-emisi, tetapi juga untuk kelas lain yang dekat.

Jika kita mengambil k = m, algoritma akan stabil dan akan berubah menjadi nilai konstan. Itulah sebabnya keandalan adalah penting untuk menghindari indeks ekstrim k.

Dalam prakteknya, sebagai optimal indeks k digunakan kriteria geser kontrol.

emisi pemutaran

Objek penelitian sebagian besar tidak sama, tetapi di antara mereka ada orang-orang yang memiliki karakteristik kelas dan disebut sebagai standar. Pada kedekatan subjek dengan model ideal probabilitas tinggi dari milik kelas ini.

Bagaimana rezultativen metode tetangga terdekat? Sebuah contoh dapat dilihat berdasarkan kategori perifer dan non-informatif benda. Hal ini diasumsikan lingkungan padat dari objek wakil lain dari kelas ini. Bila Anda menghapus mereka dari klasifikasi sampling kualitas tidak akan menderita.

Masuk ke sejumlah sampel mungkin suara semburan yang "di tanah" dari sebuah kelas. Menghapus dampak substansial positif pada kualitas klasifikasi.

Jika sampel yang diambil dari benda-benda kebisingan tidak informatif dan menghilangkan, Anda dapat mengandalkan pada hasil positif beberapa pada saat yang sama.

Yang pertama metode interpolasi dari klasifikasi tetangga terdekat memungkinkan untuk meningkatkan kualitas, mengurangi jumlah data yang disimpan, mengurangi waktu klasifikasi, yang dihabiskan untuk pilihan standar berikutnya.

Penggunaan sampel ultra-besar

Metode tetangga terdekat didasarkan pada penyimpanan nyata dari objek pembelajaran. Untuk membuat sangat sampel skala besar menggunakan masalah teknis. Tujuannya tidak hanya untuk menyimpan sejumlah besar informasi, tetapi juga dalam jumlah waktu minimum untuk memiliki waktu untuk menemukan benda u k di antara tetangga terdekat.

Untuk mengatasi dengan tugas ini, dua metode yang digunakan:

• sampel menipis melalui benda debit non-data;
• penggunaan struktur data khusus yang efektif dan kode untuk pencarian instan tetangga terdekat.

Aturan metode seleksi

Klasifikasi di atas dianggap. Metode tetangga terdekat digunakan dalam memecahkan masalah-masalah praktis, yang dikenal di muka jarak fungsi \ rho (x, x '). Dalam benda menggambarkan vektor numerik menggunakan metrik Euclidean. Pilihan ini tidak memiliki justifikasi khusus, tetapi melibatkan pengukuran semua tanda "dalam skala yang sama." Jika faktor ini tidak diperhitungkan, maka metrik akan mendominasi fitur yang memiliki nilai numerik tertinggi.

Jika ada sejumlah besar fitur, menghitung jarak sebagai jumlah deviasi pada gejala tertentu muncul dimensi masalah serius.

Dalam ruang dimensi tinggi jauh dari satu sama lain akan semua benda. Pada akhirnya, setiap sampel akan di sebelah objek yang sedang diteliti k tetangga. dipilih sejumlah kecil fitur informatif untuk menghilangkan masalah ini. Algoritma untuk menghitung perkiraan membangun dasar set berbeda tanda-tanda, dan untuk setiap individu membangun fungsi kedekatan mereka.

kesimpulan

perhitungan matematis sering melibatkan penggunaan berbagai teknik yang memiliki mereka sendiri yang khas karakteristik, kelebihan dan kekurangan. Dilihat metode tetangga terdekat dapat memecahkan masalah yang cukup serius, karena karakteristik dari objek matematika. Konsep eksperimental, berdasarkan metode analisis sedang aktif digunakan dalam kecerdasan buatan.

Dalam sistem pakar perlu tidak hanya untuk mengklasifikasikan obyek, tetapi juga menunjukkan pengguna penjelasan dari klasifikasi yang bersangkutan. Dalam metode ini, penjelasan tentang fenomena ini dinyatakan dalam kaitannya dengan objek dari suatu kelas tertentu serta lokasi relatif terhadap sampel yang digunakan. spesialis industri hukum, ahli geologi, dokter, mengambil ini "preseden" logika aktif menggunakannya dalam penelitian mereka.

Dalam rangka untuk dianalisis metode yang paling diandalkan, efisien, memberikan hasil yang diinginkan, Anda harus mengambil angka k minimum, sementara juga menghindari emisi antara objek-objek dianalisis. Itulah mengapa penggunaan standar dan metode seleksi, serta metrik optimasi.