Гіпотеза методу
Метод найближчого сусіда можна вважати найбільш поширеним алгоритмом, використовуваних для класифікації. Об'єкт, що піддається класифікації належить до того класу y_i, до якого відноситься найближчий об'єкт навчальної вибірки x_i.Специфіка методики найближчих сусідів
Метод k-найближчих сусідів дозволяє підвищувати достовірність класифікації. Аналізований об'єкт належить до того ж класу, що і основна маса його сусідів, тобто k близьких до нього об'єктів аналізованої вибірки x_i. При вирішенні задач з двома класами кількість сусідів буде непарною, щоб виключити ситуацію неоднозначності, якщо одне і те ж число сусідів буде належати до різних класів.Методика зважених сусідів
Аналізований postgresql-метод найближчих сусідів tsvector використовується, коли кількість класів не менше трьох, і можна скористатися нечетностью. Але неоднозначність виникає навіть у цих випадках. Тоді i-й сусід отримує вага w_i, який зменшується зі збільшенням рангу сусіда i. Належить об'єкт до класу, який буде мати максимальний сумарний вага серед близьких сусідів.Гіпотеза компактності
В основі всіх вищевказаних методів знаходиться гіпотеза компактності. Вона передбачає зв'язок між мірою подібності об'єктів і належністю їх до одного класу. У подібній ситуації межа між різними видами має нескладну форму, а класи створюють у просторі об'єктів компактні мобільні області. Під такими областями в математичному аналізі прийнято розуміти замкнені обмежені множини. Дана гіпотеза не пов'язана з повсякденним сприйняттям цього слова.Основна формула
Розберемо докладніше метод найближчого сусіда. Якщо запропонована навчальна вибірка виду «об'єкт-відповідь» X^m = {(x_1y_1),dots,(x_m,y_m)}; якщо для безлічі об'єктів задають функцію відстані rho(x,x'), яка представлена у вигляді адекватної моделі подібності об'єктів, при збільшенні значення даної функції знижується схожість між об'єктами x, x'. Для будь-якого об'єкта u вибудуємо об'єкти навчальної вибірки x_i по мірі зростання відстаней до u: rho(u,x_{1; u}) leq rho(u,x_{2; u}) leq cdots leq rho(u,x_{m; u}), де x_{i; u} характеризує об'єкт навчальної вибірки, що є i-му сусідом вихідного об'єкта u. Подібне позначення використовуємо і для відповіді на i-му сусіда: y_{i; u}. У підсумку отримуємо, що довільний об'єкт u провокує зміну нумерації власної вибірки.Визначення числа сусідів k
Метод найближчого сусіда при k = 1 здатний давати помилкову класифікацію, причому не тільки на об'єктах-викиди, але і для інших класів, які розташовані поблизу. Якщо взяти k = m, алгоритм буде максимально стійким і виродиться в постійну величину. Саме тому для достовірності важливо не допускати крайніх показників k. На практиці в якості оптимального показника k застосовують критерій ковзного контролю.Відсів викидів
Об'єкти навчання в основному є нерівноцінними, але серед них є такі, які володіють характерними ознаками класу і іменуються еталонами. При близькості розглянутого предмета до ідеального зразка висока ймовірність його приналежності до даного класу.Наскільки результативний метод найближчих сусідів? Приклад можна подивитися на основі периферійних і неінформативних категорій об'єктів. Передбачається щільне оточення розглянутого об'єкта іншими представниками даного класу. При видаленні їх з взятої вибірки якість класифікації не постраждає. Потрапити в таку вибірку може певне число шумових викидів, які знаходяться «в гущавині» іншого класу. Видалення в основному позитивно відбивається на якості проведеної класифікації. Якщо з взятої вибірки усувають неінформативні і шумові об'єкти, можна розраховувати на кілька позитивних результатів одночасно. В першу чергу інтерполяція методом найближчого сусіда дозволяє підвищувати якість класифікації, скорочувати обсяг збережених даних, зменшувати час класифікації, яке витрачається на вибір найближчих еталонів.
Застосування надвеликих вибірок
Метод найближчих сусідів базується на реальному зберіганні навчальних об'єктів. Для створення надвеликих вибірок використовують технічні проблеми. Ставиться завдання не просто зберегти суттєвий обсяг інформації, але і в мінімальний часовий проміжок встигати знаходити довільний об'єкт u серед k найближчих сусідів. Для того щоб впоратися з поставленою задачею, застосовують два способи:Правила підбору методики
Вище була розглянута класифікація. Метод найближчого сусіда застосовують при вирішенні практичних завдань, в яких відома заздалегідь функція відстані rho(x,x'). При описі об'єктів числовими векторами використовують евклидову метрику. Подібний вибір не має спеціального обґрунтування, але передбачає вимірювання всіх ознак «в єдиному масштабі». Якщо не врахувати цей фактор, то в метриці буде переважати ознака, що має найбільші числові значення.При наявності значної кількості ознак, обчислення відстані у вигляді суми відхилень за конкретними ознаками з'являється серйозна проблема розмірності. У просторі високої розмірності далекими один від одного виявляться всі об'єкти. В кінцевому підсумку довільній буде вибірка найближчих для досліджуваного об'єкта k сусідів. Для усунення подібної проблеми відбирається невелике число інформативних ознак. Алгоритми розрахунку оцінок вибудовують на основі різних наборів ознак, причому для кожного окремого вибудовують свою функцію близькості.