МЕТОД K-найближчих| СУСІДІВ

При класифікації невідомого об'єкту знаходиться|перебуває| задане число (k) геометрично найближчих до нього в просторі|простір-час| ознак інших об'єктів (найближчих сусідів) з|із| вже відомою приналежністю до розпізнаваних класів. Рішення про віднесення невідомого об'єкту до того або іншого діагностичного класу приймається шляхом аналізу інформації про цю відому приналежність його найближчих сусідів, наприклад, за допомогою простого підрахунку голосів.

Спочатку метод до-найближчих сусідів розглядався як непараметричний метод оцінювання відношення правдоподібності. Для цього методу отримані теоретичні оцінки його ефективності порівняно з оптимальним байесовским класифікатором. Доведено, що асимптотична вірогідність помилки для методу до-найближчих сусідів перевищує помилки правила Байеса не більше ніж в два рази.

Як наголошувалося вище, в реальних задачіх|задачах| часто доводиться оперувати об'єктами, які описуються великою кількістю якісних (дихотомічних) ознак. При цьому розмірність простору|простір-час| ознак соизмерима| або перевищує об'єм|обсяг| досліджуваної вибірки. У таких умовах зручно інтерпретувати кожен об'єкт навчальної вибірки, як окремий лінійний класифікатор. Тоді той або інший діагностичний клас представляється не одним прототипом, а набором лінійних класифікаторів. Сукупна взаємодія лінійних класифікаторів дає у результаті кусочно-лінійну поверхню, що розділяє в просторі|простір-час| ознак розпізнавані класи. Вигляд|вид| розділяючої поверхні, що складається з шматків гіперплощин, може бути всіляким|різноманітним| і залежить від взаємного розташування совокупностей|, що класифікуються.

При використанні методу до-найближчих сусідів для розпізнавання образів дослідникові доводиться вирішувати складну проблему вибору метрики для визначення близькості об'єктів, що діагностуються. Ця проблема в умовах високої розмірності простору ознак надзвичайно загострюється унаслідок достатньої трудомісткості даного методу, яка стає значимою навіть для високопродуктивних комп'ютерів. Тому тут так само, як і в методі порівняння з прототипом, необхідно вирішувати творчу задачу аналізу багатовимірної структури експериментальних даних для мінімізації числа об'єктів, що представляють діагностичні класи.

На думку авторів необхідність зменшення числа об'єктів в повчальній вибірці (діагностичних прецедентів) є недоліком|нестачею| даного методу, оскільки зменшує показність навчальної вибірки.

2.2.2.3. АЛГОРИТМИ ОБЧИСЛЕННЯ|підрахунку| ОЦІНОК (ГОЛОСУВАННЯ)

Принцип дії алгоритмів обчислення|підрахунку| оцінок (АВО|) полягає в обчисленні|підрахунку| пріоритеті (оцінок схожості), що характеризують “близькість” розпізнаваного і еталонних об'єктів за системою ансамблів ознак, що є системою підмножин заданої множинаі ознак.

На відміну від всіх раніше розглянутих|розглядувати| методів алгоритми обчислення|підрахунку| оцінок принципово по-новому оперують описами об'єктів. Для цих алгоритмів об'єкти існують одночасно в самих різних підпросторах|простір-час| простору|простір-час| ознак. Клас АВО доводить ідею використання ознак до логічного кінця: оскільки не завжди відомо, які поєднання ознак найбільш інформативні, то в АВО міра|ступінь| схожості об'єктів обчислюється|вичисляє| при зіставленні всіх можливих або визначених поєднань ознак, що входять в описи об'єктів [46].

Ще одним розширенням АВО є те, що в даних алгоритмах задачі|задача| визначення схожості і відмінності об'єктів формулюється як параметрична і виділений етап налаштування АВО по повчальній вибірці, на якому підбираються оптимальні значення введених|запроваджувати| параметрів. Критерієм якості служить помилка розпізнавання, а параметризується буквально все:

правила обчислення|підрахунку| близькості об'єктів по окремих ознаках

правила обчислення|підрахунку| близькості об'єктів в підпросторах|простір-час| ознак

міра|ступінь| важливості того або іншого еталонного об'єкту як діагностичного прецеденту

значущість вкладу|внеску| кожної опорної множинаі ознак в підсумкову оцінку схожості розпізнаваного об'єкту з|із| яким-небудь діагностичним класом.

Параметри АВО задаються у вигляді значень порогів і (або) як ваги вказаних складових.

Теоретичні можливості АВО перевищують або, принаймні, не нижче за можливості будь-якого іншого алгоритму розпізнавання образів, оскільки за допомогою АВО можуть бути реалізовані всі гадані операції з досліджуваними об'єктами. Але, як це зазвичай буває, розширення потенційних можливостей натрапляє на великі труднощі їх практичного втілення, особливо на етапі побудови (налаштування) алгоритмів даного типа. Окремі труднощі наголошувалися раніше при обговоренні методу до-найближчих сусідів, який можна було інтерпретувати як усічений варіант АВО. Його теж можна розглядати в параметричному вигляді і звести задачі до пошуку зваженої метрики вибраного типа. В той же час вже тут для високорозмірних завдань виникають складні теоретичні питання і проблеми, пов'язані з організацією ефективного обчислювальному процесу. Для АВО, якщо спробувати використовувати потенційні можливості даних алгоритмів в повному об'ємі, вказані труднощі зростають багато разів.

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
МЕТОДИ, ЗАСНОВАНІ НА ОЦІНКАХ ЩІЛЬНОСТІ РОЗПОДІЛУ ЗНАЧЕНЬ ОЗНАК	\|	Принципи побудови системи інформаційної безпеки об'єкту

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.004 сек.