Метод k найближчих сусідів

Ме́тод k-найбли́жчих сусі́дів (англ. k-nearest neighbor method) — це ^[en] метод керованого навчання, вперше розроблений ^[en] та ^[en] у 1951 році, а пізніше розвинутий Томасом Ковером. Метод використовується як для класифікації, так і для регресії. В обох випадках вхідні дані складаються з k найближчих навчальних прикладів у наборі даних. Результат залежить від того, для чого використовується k-НС для класифікації чи регресії:

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

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

k-НС — це тип класифікації, де функція локально лише апроксимується, а всі обчислення відкладаються до оцінки функції. Оскільки цей алгоритм покладається на функцію відстані для класифікації, то у випадку, коли ознаки представляють різні фізичні одиниці або мають дуже різні масштаби, то ^[en] навчальних даних може значно підвищити їх точність.

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

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

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

Статистичне тло

Припустимо, у нас є пари ${\displaystyle (X_{1},Y_{1}),(X_{2},Y_{2}),\dots ,(X_{n},Y_{n})}$, які приймають значення в множині ${\displaystyle \mathbb {R} ^{d}\times \{1,2\}}$, де Y — мітка класу точки X, отже ${\displaystyle X|Y=r\sim P_{r}}$ для ${\displaystyle r=1,2}$ (і розподілів ймовірностей ${\displaystyle P_{r}}$). Для заданої норми ${\displaystyle \|\cdot \|}$ на ${\displaystyle \mathbb {R} ^{d}}$ і точки ${\displaystyle x\in \mathbb {R} ^{d}}$, послідовність ${\displaystyle (X_{(1)},Y_{(1)}),\dots ,(X_{(n)},Y_{(n)})}$ буде таким переупорядкуванням навчальних даних, що ${\displaystyle \|X_{(1)}-x\|\leq \dots \leq \|X_{(n)}-x\|}$.

Алгоритм

Приклад k-НС класифікації. Тестовий зразок (зелене коло) повинен бути класифікований як синій квадрат або як червоний трикутник. Якщо k = 3, то класифікується як червоний трикутник, тому що всередині меншого кола 2 трикутника і тільки 1 квадрат. Якщо k = 5, то він буде класифікований як синій квадрат (3 квадрата проти 2-ох трикутників всередині більшого кола).

Навчальними прикладами є вектори багатовимірного ознаки(простору ознак), кожен має мітку класу. Фаза навчання алгоритму складається лише із збереження векторів ознак і міток класів навчальних вибірок.

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

Часто використовуваною метрикою відстані для неперервних змінних є евклідова відстань. Для дискретних змінних, наприклад, для класифікації тексту, можна використовувати інший показник, наприклад метрику перекриття (або відстань Геммінга). У контексті мікромасивів даних експресії генів, наприклад, k-НС використовувався з коефіцієнтами кореляції, такими як Пірсон і Спірмен, у якості метрики. Часто точність класифікації k-НС можна значно підвищити, якщо навчатися функції відстані за допомогою спеціалізованих алгоритмів, таких як ^[en] або ^[en].

Основна проблема при класифікації за допомогою «голосування більшості» трапляється, коли розподіл класів перекошений. Тобто, приклади більш частого класу, як правило, домінують у передбаченні нового прикладу, оскільки вони, як правило, поширені серед k найближчих сусідів через їх велику кількість. Одним із способів подолання цієї проблеми є зважування класифікації, беручи до уваги відстань від контрольної точки до кожного з її k найближчих сусідів. Клас (або значення в задачах регресії) кожної з k найближчих точок множиться на вагу, пропорційну оберненій відстані від цієї точки до контрольної точки. Іншим способом подолання перекосу є абстракція у представленні даних. Наприклад, у самоорганізаційній карті Кохонена (СКК) кожен вузол є представником (центром) кластера подібних точок, незалежно від їх щільності в вихідних навчальних даних. Потім k-НС можна застосувати до СКК.

Вибір параметрів

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

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

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

Класифікатор 1-найближчого сусіда

Найбільш інтуїтивно зрозумілим класифікатором типу найближчого сусіда є той класифікатор найближчого сусіда, який призначає точці x клас свого найближчого сусіда в просторі ознак, тобто ${\displaystyle C_{n}^{1nn}(x)=Y_{(1)}}$.

Оскільки розмір навчального набору даних наближається до нескінченності, класифікатор одного найближчого сусіда гарантує коефіцієнт помилок, який не перевищує подвійну ^[en] (мінімально досяжний рівень помилок з урахуванням розподілу даних).

Зважений класифікатор найближчих сусідів

Класифікатор k найближчих сусідів можна розглядати як присвоєння k найближчим сусідам ваги ${\displaystyle 1/k}$, а всі іншим 0 ваги. Це можна узагальнити на зважені класифікатори найближчих сусідів. Тобто, де i-му найближчому сусіду присвоюється вага ${\displaystyle w_{ni}}$, з ${\displaystyle \sum _{i=1}^{n}w_{ni}=1}$. Аналогічний результат щодо сильної узгодженості зважених класифікаторів найближчих сусідів також має місце.

Нехай ${\displaystyle C_{n}^{wnn}}$ позначає зважений найближчий класифікатор з вагами ${\displaystyle \{w_{ni}\}_{i=1}^{n}}$. За умови регулярності  щодо розподілів класів надмірний ризик має наступне асимптотичне розширення

${\displaystyle {\mathcal {R}}_{\mathcal {R}}(C_{n}^{wnn})-{\mathcal {R}}_{\mathcal {R}}(C^{Bayes})=\left(B_{1}s_{n}^{2}+B_{2}t_{n}^{2}\right)\{1+o(1)\},}$

для констант ${\displaystyle B_{1}}$ і ${\displaystyle B_{2}}$, де ${\displaystyle s_{n}^{2}=\sum _{i=1}^{n}w_{ni}^{2}}$ і ${\displaystyle t_{n}=n^{-2/d}\sum _{i=1}^{n}w_{ni}\{i^{1+2/d}-(i-1)^{1+2/d}\}}$.

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

${\displaystyle 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]}$ для ${\displaystyle i=1,2,\dots ,k^{*}}$ і

${\displaystyle w_{ni}^{*}=0}$, для ${\displaystyle i=k^{*}+1,\dots ,n}$.

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

k-НС викиди

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

Прокляття розмірності

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

Див. також

• Граф найближчих сусідів

Примітки

1. Fix, Evelyn; Hodges, Joseph L. (1951). (PDF) (Звіт). № Report Number 4, Project Number 21-49-004. USAF School of Aviation Medicine, Randolph Field, Texas. Архів оригіналу (PDF) за 26 вересня 2020. Процитовано 23 квітня 2022.
2. (1992). . The American Statistician. 46 (3): 175—185. doi:10.1080/00031305.1992.10475879. Архів оригіналу (PDF) за 11 серпня 2020. Процитовано 23 квітня 2022. {{}}: |hdl-access= вимагає |hdl= ()
3. Piryonesi S. Madeh; El-Diraby Tamer E. (1 червня 2020). Role of Data Analytics in Infrastructure Asset Management: Overcoming Data Size and Quality Problems. Journal of Transportation Engineering, Part B: Pavements. 146 (2): 04020022. doi:10.1061/JPEODX.0000175.
4. Hastie, Trevor. (2001). The elements of statistical learning : data mining, inference, and prediction : with 200 full-color illustrations. New York: Springer. ISBN . OCLC 46809224.
5. Ця схема є узагальненням лінійної інтерполяції.
6. Jaskowiak, Pablo A.; Campello, Ricardo J. G. B. Comparing Correlation Coefficients as Dissimilarity Measures for Cancer Classification in Gene Expression Data. Brazilian Symposium on Bioinformatics (BSB 2011): 1—8. CiteSeerX 10.1.1.208.993.
7. Coomans, Danny; Massart, Desire L. (1982). Alternative k-nearest neighbour rules in supervised pattern recognition : Part 1. k-Nearest neighbour classification by using alternative voting rules. Analytica Chimica Acta. 136: 15—27. doi:10.1016/S0003-2670(01)95359-0.
8. 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
9. Nigsch, Florian; Bender, Andreas; van Buuren, Bernd; Tissen, Jos; Nigsch, Eduard; Mitchell, John B. O. (2006). Melting point prediction employing k-nearest neighbor algorithms and genetic parameter optimization. Journal of Chemical Information and Modeling. 46 (6): 2412—2422. doi:10.1021/ci060149f. PMID 17125183.
10. Hall, Peter; Park, Byeong U.; Samworth, Richard J. (2008). Choice of neighbor order in nearest-neighbor classification. . 36 (5): 2135—2152. arXiv:0810.5276. Bibcode:2008arXiv0810.5276H. doi:10.1214/07-AOS537.
11. Stone, Charles J. (1977). Consistent nonparametric regression. . 5 (4): 595—620. doi:10.1214/aos/1176343886.
12. Samworth, Richard J. (2012). Optimal weighted nearest neighbour classifiers. . 40 (5): 2733—2763. arXiv:1101.5783. doi:10.1214/12-AOS1049.
13. Ramaswamy, Sridhar; Rastogi, Rajeev; Shim, Kyuseok (2000). Efficient algorithms for mining outliers from large data sets. Proceedings of the 2000 ACM SIGMOD international conference on Management of data – SIGMOD '00. с. 427. doi:10.1145/342009.335437. ISBN .
14. Campos, Guilherme O.; Zimek, Arthur; Sander, Jörg; Campello, Ricardo J. G. B.; Micenková, Barbora; Schubert, Erich; Assent, Ira; Houle, Michael E. (2016). On the evaluation of unsupervised outlier detection: measures, datasets, and an empirical study. Data Mining and Knowledge Discovery. 30 (4): 891—927. doi:10.1007/s10618-015-0444-8. ISSN 1384-5810.

Джерела

• Глосарій термінів з хімії / уклад. Й. Опейда, О. Швайка ; Ін-т фізико-органічної хімії та вуглехімії ім. Л. М. Литвиненка НАН України, Донецький національний університет. — Дон. : Вебер, 2008. — 738 с. — .
• Лекція з методу k-найближчих сусідів