Перегляд вихідного коду сторінки Метод k-найближчих сусідів

{{DISPLAYTITLE:Метод ''k''-найближчих сусідів}}
{{Машинне навчання|Виявляння аномалій}}
'''Ме́тод ''k''-найбли́жчих сусі́дів''' ({{lang-en|k-nearest neighbor method}})&nbsp;— це {{Нп|Непараметрична статистика|непараметричний||Nonparametric statistics}} метод [[Кероване навчання|керованого навчання]], вперше розроблений {{Нп|Евелін Фікс|Евеліном Фіксом||Evelyn Fix}} та {{Нп|Джозеф Ходжес|Джозефом Ходжесом||Joseph Lawson Hodges Jr.}} у 1951 році<ref>{{Cite report | last1=Fix | first1=Evelyn | last2=Hodges | first2=Joseph L. | title=Discriminatory Analysis. Nonparametric Discrimination: Consistency Properties | issue=Report Number 4, Project Number 21-49-004 | year=1951 | url=https://apps.dtic.mil/dtic/tr/fulltext/u2/a800276.pdf | publisher=USAF School of Aviation Medicine, Randolph Field, Texas | accessdate=23 квітня 2022 | archive-date=26 вересня 2020 | archive-url=https://web.archive.org/web/20200926212807/https://apps.dtic.mil/dtic/tr/fulltext/u2/a800276.pdf }}</ref>, а пізніше розвинутий [[Томас Ковер|Томасом Ковером]]<ref>{{Cite journal|last=Altman|first=Naomi S.|author-link=Naomi Altman|year=1992|title=An introduction to kernel and nearest-neighbor nonparametric regression|url=https://ecommons.cornell.edu/bitstream/1813/31637/1/BU-1065-MA.pdf|journal=The American Statistician|volume=46|issue=3|pages=175–185|doi=10.1080/00031305.1992.10475879|hdl-access=free|accessdate=23 квітня 2022|archive-date=11 серпня 2020|archive-url=https://web.archive.org/web/20200811214729/https://ecommons.cornell.edu/bitstream/handle/1813/31637/BU-1065-MA.pdf;jsessionid=BE2DA6ED40372E08203A77591971D746?sequence=1}}</ref>. Метод використовується як для [[Задача класифікації|класифікації]], так і для [[Регресійний аналіз|регресії]]. В обох випадках вхідні дані складаються з ''k'' найближчих навчальних прикладів у [[Набір даних|наборі даних]]. Результат залежить від того, для чого використовується ''k''-НС для класифікації чи регресії:

:* При ''класифікації k-НС'' результатом є належність класу. Об'єкт класифікується за допомогою множини голосів його сусідів, при цьому об'єкт належить до класу, найбільш поширеного серед його ''k'' найближчих сусідів (''k''&nbsp;— ціле додатне [[Цілі числа|число]], як правило, невелике). Якщо ''k''&nbsp;=&nbsp;1, то об'єкт просто приписується до класу цього єдиного найближчого сусіда.

:* При ''k-НС регресії'' результатом є числове значення властивості об'єкта. Це значення є середнім із значень ''k'' найближчих сусідів.

''k''-НС&nbsp;— це тип [[Задача класифікації|класифікації]], де функція локально лише апроксимується, а всі обчислення відкладаються до оцінки функції. Оскільки цей алгоритм покладається на [[Метрика (математика)|функцію відстані]] для класифікації, то у випадку, коли [[Ознака (машинне навчання)|ознаки]] представляють різні фізичні одиниці або мають дуже різні масштаби, то {{Нп|Нормалізація (статистика)|нормалізація||Normalization (statistics)}} навчальних даних може значно підвищити їх точність<ref name=":0">{{Cite journal|last=Piryonesi S. Madeh|last2=El-Diraby Tamer E.|date=2020-06-01|title=Role of Data Analytics in Infrastructure Asset Management: Overcoming Data Size and Quality Problems|journal=Journal of Transportation Engineering, Part B: Pavements|volume=146|issue=2|pages=04020022|doi=10.1061/JPEODX.0000175}}</ref><ref>{{Cite book
|title=The elements of statistical learning : data mining, inference, and prediction : with 200 full-color illustrations
|url=https://archive.org/details/elementsofstatis0000hast
|last=Hastie, Trevor.
|date=2001
|publisher=Springer
|location=New York
|isbn=0-387-95284-5
|oclc=46809224
}}</ref>.

Як для класифікації, так і для регресії, корисним може бути призначення вагових значень внеску сусідів, щоб внесок у середнє у найближчих сусідів був більше, ніж у віддалених. Для прикладу, загальна схема зважування полягає в тому, щоб надати кожному сусіду вагу 1/''d'', де ''d''&nbsp;— відстань до сусіда<ref>Ця схема є узагальненням лінійної інтерполяції.</ref>.

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

Особливістю алгоритму ''k''-НС є те, що він чутливий до локальної структури даних.

== Статистичне тло ==
Припустимо, у нас є пари <math>(X_1,Y_1), (X_2,Y_2), \dots, (X_n, Y_n) </math>, які приймають значення в множині <math>\mathbb{R}^d \times \{1,2\}</math>, де {{Mvar|Y}}&nbsp;— мітка класу точки {{Mvar|X}}, отже <math>X|Y=r \sim P_r</math> для <math>r=1,2</math> (і [[Розподіл імовірностей|розподілів ймовірностей]] <math>P_r</math>). Для заданої норми <math>\|\cdot\|</math> на <math>\mathbb{R}^d</math> і точки <math>x \in \mathbb{R}^d</math>, послідовність <math>(X_{(1)},Y_{(1)}), \dots, (X_{(n)}, Y_{(n)}) </math> буде таким переупорядкуванням навчальних даних, що <math> \|X_{(1)}-x\| \leq \dots \leq \|X_{(n)}-x\| </math>.

== Алгоритм ==
[[Файл:KnnClassification.svg|праворуч|міні| Приклад ''k''-НС класифікації. Тестовий зразок (зелене коло) повинен бути класифікований як синій квадрат або як червоний трикутник. Якщо k = 3, то класифікується як червоний трикутник, тому що всередині меншого кола 2 трикутника і тільки 1 квадрат. Якщо k = 5, то він буде класифікований як синій квадрат (3 квадрата проти 2-ох трикутників всередині більшого кола).]]
Навчальними прикладами є вектори багатовимірного [[Ознака (машинне навчання)|ознаки]] [[Ознака (машинне навчання)#Розширення|простору ознак]], кожен має мітку класу. Фаза навчання алгоритму складається лише із збереження векторів ознак і міток класів навчальних вибірок.

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

Часто використовуваною метрикою відстані для [[Неперервна функція|неперервних змінних]] є [[евклідова відстань]]. Для дискретних змінних, наприклад, для класифікації тексту, можна використовувати інший показник, наприклад '''метрику перекриття''' (або [[відстань Геммінга]]). У контексті мікромасивів даних [[Експресія генів|експресії генів]], наприклад, ''k''-НС використовувався з коефіцієнтами кореляції, такими як Пірсон і Спірмен, у якості метрики<ref>{{Cite journal|last=Jaskowiak|first=Pablo A.|last2=Campello|first2=Ricardo J. G. B.|title=Comparing Correlation Coefficients as Dissimilarity Measures for Cancer Classification in Gene Expression Data|journal=Brazilian Symposium on Bioinformatics (BSB 2011)|pages=1–8|citeseerx=10.1.1.208.993}}</ref>. Часто точність класифікації ''k''-НС можна значно підвищити, якщо навчатися функції відстані за допомогою спеціалізованих алгоритмів, таких як {{Нп|найближчий сусід з великим полем|||Large margin nearest neighbor}} або {{Нп|аналіз компонентів сусідства|||Neighbourhood components analysis}}.

Основна проблема при класифікації за допомогою «голосування більшості» трапляється, коли розподіл класів перекошений. Тобто, приклади більш частого класу, як правило, домінують у передбаченні нового прикладу, оскільки вони, як правило, поширені серед ''k'' найближчих сусідів через їх велику кількість<ref name="Coomans_Massart1982">{{Cite journal|last=Coomans|first=Danny|last2=Massart|first2=Desire L.|year=1982|title=Alternative k-nearest neighbour rules in supervised pattern recognition : Part 1. k-Nearest neighbour classification by using alternative voting rules|journal=[[Analytica Chimica Acta]]|volume=136|pages=15&ndash;27|doi=10.1016/S0003-2670(01)95359-0}}
</ref>. Одним із способів подолання цієї проблеми є зважування класифікації, беручи до уваги відстань від контрольної точки до кожного з її ''k'' найближчих сусідів. Клас (або значення в задачах регресії) кожної з ''k'' найближчих точок множиться на вагу, пропорційну оберненій відстані від цієї точки до контрольної точки. Іншим способом подолання перекосу є абстракція у представленні даних. Наприклад, у [[Самоорганізаційна Карта Кохонена|самоорганізаційній карті Кохонена]] (СКК) кожен вузол є представником (центром) кластера подібних точок, незалежно від їх щільності в вихідних навчальних даних. Потім ''k''-НС можна застосувати до СКК.

== Вибір параметрів ==
Найкращий вибір ''k'' залежить від даних; загалом, більші значення ''k'' зменшують вплив шуму на класифікацію<ref>Everitt, Brian S.; Landau, Sabine; Leese, Morven; and Stahl, Daniel (2011) «Miscellaneous Clustering Methods», in ''Cluster Analysis'', 5th Edition, John Wiley & Sons, Ltd., Chichester, UK</ref>, але роблять границі між класами менш чіткими. Гарне значення ''k'' можна вибрати різними [[Евристичний алгоритм|евристичними]] методами (див. [[оптимізація гіперпараметрів]]). Окремий випадок, коли клас прогнозу є класом найближчої навчальної вибірки (тобто, коли ''k'' = 1), називається алгоритмом найближчого сусіда.

Точність алгоритму ''k''-НС може бути значно погіршена через наявність шумних або невідповідних ознак, або якщо масштаби ознак не відповідають їх важливості. Багато дослідницьких зусиль було зосереджено на [[Обирання ознак|виборі]] або [[Масштабування ознак|масштабуванні]] ознак для покращення класифікації. Особливо популярний&nbsp; підхід&nbsp;— це використання [[Еволюційний алгоритм|еволюційних алгоритмів]] для оптимізації масштабування ознак<ref>{{Cite journal|last=Nigsch|first=Florian|last2=Bender|first2=Andreas|last3=van Buuren|first3=Bernd|last4=Tissen|first4=Jos|last5=Nigsch|first5=Eduard|last6=Mitchell|first6=John B. O.|year=2006|title=Melting point prediction employing k-nearest neighbor algorithms and genetic parameter optimization|journal=Journal of Chemical Information and Modeling|volume=46|issue=6|pages=2412–2422|doi=10.1021/ci060149f|pmid=17125183}}</ref>. Іншим популярним підходом є масштабування функцій за допомогою [[Взаємна інформація|взаємної інформації]] навчальних даних із навчальними класами.&nbsp;

У задачах бінарної (два класи) класифікації корисно вибрати ''k'' як непарне число, оскільки це дозволяє уникнути ситуації коли голоси можуть бути рівними (цього можна уникнути, якщо при рівній кількості голосів брати до уваги відстань до точок). Одним із популярних способів вибору емпірично оптимального ''k'' в цьому параметрі є метод [[Статистичний бутстреп|бутстрепінгу]]<ref name="HPS2008">{{Cite journal|last=Hall|first=Peter|last2=Park|first2=Byeong U.|last3=Samworth|first3=Richard J.|year=2008|title=Choice of neighbor order in nearest-neighbor classification|url=https://archive.org/details/sim_annals-of-statistics_2008-10_36_5/page/2135|journal=[[Annals of Statistics]]|volume=36|issue=5|pages=2135–2152|arxiv=0810.5276|bibcode=2008arXiv0810.5276H|doi=10.1214/07-AOS537}}
</ref>.

== Класифікатор {{Math|1}}-найближчого сусіда ==
Найбільш інтуїтивно зрозумілим класифікатором типу найближчого сусіда є той класифікатор найближчого сусіда, який призначає точці {{Mvar|x}} клас свого найближчого сусіда в просторі ознак, тобто <math>C_n^{1nn}(x) = Y_{(1)}</math>.

Оскільки розмір навчального набору даних наближається до нескінченності, класифікатор одного найближчого сусіда гарантує коефіцієнт помилок, який не перевищує подвійну {{Нп|частота помилок Байєса|частоту помилок Байєса||Bayes error rate}} (мінімально досяжний рівень помилок з урахуванням розподілу даних).

== Зважений класифікатор найближчих сусідів ==
Класифікатор {{Mvar|k}} найближчих сусідів можна розглядати як присвоєння {{Mvar|k}} найближчим сусідам ваги <math>1/k</math>, а всі іншим {{Mvar|0}} ваги. Це можна узагальнити на зважені класифікатори найближчих сусідів. Тобто, де {{Mvar|i}}-му найближчому сусіду присвоюється вага <math>w_{ni}</math>, з <math>\sum_{i=1}^n w_{ni} = 1</math>. Аналогічний результат щодо сильної узгодженості зважених класифікаторів найближчих сусідів також має місце<ref name="Stone">{{Cite journal|last=Stone|first=Charles J.|year=1977|title=Consistent nonparametric regression|url=https://archive.org/details/sim_annals-of-statistics_1977-07_5_4/page/595|journal=[[Annals of Statistics]]|volume=5|issue=4|pages=595–620|doi=10.1214/aos/1176343886|doi-access=free}}
</ref>.

Нехай <math>C^{wnn}_n</math> позначає зважений найближчий класифікатор з вагами <math>\{w_{ni}\}_{i=1}^n</math>. За умови регулярності  щодо розподілів класів надмірний ризик має наступне асимптотичне розширення<ref name="Samworth12">{{Cite journal|last=Samworth|first=Richard J.|year=2012|title=Optimal weighted nearest neighbour classifiers|url=https://archive.org/details/sim_annals-of-statistics_2012-10_40_5/page/2733|journal=[[Annals of Statistics]]|volume=40|issue=5|pages=2733–2763|arxiv=1101.5783|doi=10.1214/12-AOS1049}}
</ref>

: <math>\mathcal{R}_\mathcal{R}(C^{wnn}_{n}) - \mathcal{R}_{\mathcal{R}}(C^{Bayes}) = \left(B_1 s_n^2 + B_2 t_n^2\right) \{1+o(1)\},</math>

для констант <math>B_1</math> і <math>B_2</math>, де <math>s_n^2 = \sum_{i=1}^n w_{ni}^2</math> і <math>t_n = n^{-2/d}\sum_{i=1}^n w_{ni}\{i^{1+2/d} - (i-1)^{1+2/d}\}</math>.

Оптимальна схема зважування <math>\{w_{ni}^*\}_{i=1}^n</math>, що врівноважує два терми навелені вище, задається таким чином: <math>k^* = \lfloor B n^{\frac 4 {d+4}} \rfloor</math>,

: <math>w_{ni}^* = \frac 1 {k^*} \left[1 + \frac d 2 - \frac d {2{k^*}^{2/d}} \{ i ^{1+2/d} - (i-1)^{1+2/d}\}\right] </math> для <math>i=1,2,\dots,k^*</math> і
: <math> w^*_{ni} = 0 </math>, для <math> i = k^*+1,\dots,n</math>.

При оптимальних вагах домінуючим членом в асимптотичному розкладанні надлишкового ризику є <math>\mathcal{O}(n^{-\frac 4 {d+4}})</math>. Подібні результати справедливі при використанні для [[Бутстрепова агрегація|агрегації класифікатора найближчого сусіда]].

== ''k''-НС викиди ==
Відстань до ''k''-го найближчого сусіда також можна розглядати як оцінку локальної щільності, і, таким чином, також є популярним показником викиду при [[Виявлення аномалій|виявленні аномалій]]. Чим більша відстань до ''k''-НС, чим нижча локальна щільність, і тим більша ймовірність, що точка запиту є викидом<ref>{{cite conference |doi=10.1145/342009.335437 |title=Efficient algorithms for mining outliers from large data sets |conference=Proceedings of the 2000 ACM SIGMOD international conference on Management of data – SIGMOD '00 |pages=427 |year=2000 |last1=Ramaswamy |first1=Sridhar |last2=Rastogi |first2=Rajeev |last3=Shim |first3=Kyuseok |isbn=1-58113-217-4 }}</ref>. Ця модель викидів, хоча й досить проста, разом з іншим класичним методом аналізу даних, [[Фактор локального відхилення|фактором локального відхилення]], працює досить добре в порівнянні з більш сучасними та складнішими підходами, згідно з широкомасштабним експериментальним аналізом<ref name="CamposZimek2016">{{Cite journal|last=Campos|first=Guilherme O.|last2=Zimek|first2=Arthur|last3=Sander|first3=Jörg|last4=Campello|first4=Ricardo J. G. B.|last5=Micenková|first5=Barbora|last6=Schubert|first6=Erich|last7=Assent|first7=Ira|last8=Houle|first8=Michael E.|year=2016|title=On the evaluation of unsupervised outlier detection: measures, datasets, and an empirical study|journal=Data Mining and Knowledge Discovery|volume=30|issue=4|pages=891–927|doi=10.1007/s10618-015-0444-8|issn=1384-5810}}</ref>.

== Прокляття розмірності ==
Цей класифікатор робить припущення, що подібні точки мають подібні мітки. На жаль, у високорозмірнісних просторах, точки, вибрані з [[Розподіл імовірностей|розподілу ймовірностей]], майже ніколи не опиняються близько одна до одної.

== Див. також ==
* [[Граф найближчих сусідів]]

== Примітки ==
{{reflist|30em}}

== Джерела ==
* {{Глосарій термінів з хімії}}
* [http://om.univ.kiev.ua/users_upload/15/upload/file/pr_lecture_03.pdf Лекція з методу ''k''-найближчих сусідів]

{{Stat-stub}}
{{Datastructure-stub}}

[[Категорія:Алгоритми класифікації]]
[[Категорія:Алгоритми пошуку]]
[[Категорія:Алгоритми машинного навчання]]
[[Категорія:Статистична класифікація]]
[[Категорія:Непараметрична статистика]]