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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

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

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

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

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

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

Статистичне тло[ред. | ред. код]

Припустимо, у нас є пари , які приймають значення в множині , де Y — мітка класу точки X, отже для розподілів ймовірностей ). Для заданої норми на і точки , послідовність буде таким переупорядкуванням навчальних даних, що .

Алгоритм[ред. | ред. код]

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

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

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

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

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

Вибір параметрів[ред. | ред. код]

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

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

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

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

Найбільш інтуїтивно зрозумілим класифікатором типу найближчого сусіда є той класифікатор найближчого сусіда, який призначає точці x клас свого найближчого сусіда в просторі ознак, тобто .

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

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

Класифікатор k найближчих сусідів можна розглядати як присвоєння k найближчим сусідам ваги , а всі іншим 0 ваги. Це можна узагальнити на зважені класифікатори найближчих сусідів. Тобто, де i-му найближчому сусіду присвоюється вага , з . Аналогічний результат щодо сильної узгодженості зважених класифікаторів найближчих сусідів також має місце[11].

Нехай позначає зважений найближчий класифікатор з вагами . За умови регулярності  щодо розподілів класів надмірний ризик має наступне асимптотичне розширення[12]

для констант і , де і .

Оптимальна схема зважування , що врівноважує два терми навелені вище, задається таким чином: ,

для і
, для .

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

k-NN викиди[ред. | ред. код]

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

Прокляття розмірності[ред. | ред. код]

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

Див. також[ред. | ред. код]

Примітки[ред. | ред. код]

  1. Fix, Evelyn; Hodges, Joseph L. (1951). Discriminatory Analysis. Nonparametric Discrimination: Consistency Properties (Report Number 4, Project Number 21-49-004). USAF School of Aviation Medicine, Randolph Field, Texas. Архів оригіналу за 26 вересня 2020. Процитовано 23 квітня 2022. 
  2. Altman, Naomi S. (1992). An introduction to kernel and nearest-neighbor nonparametric regression. The American Statistician 46 (3): 175–185. doi:10.1080/00031305.1992.10475879. Архів оригіналу за 11 серпня 2020. Процитовано 23 квітня 2022. 
  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 0-387-95284-5. 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= (довідка)
  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. PMID 17125183. doi:10.1021/ci060149f. 
  10. Hall, Peter; Park, Byeong U.; Samworth, Richard J. (2008). Choice of neighbor order in nearest-neighbor classification. Annals of Statistics 36 (5): 2135–2152. Bibcode:2008arXiv0810.5276H. arXiv:0810.5276. doi:10.1214/07-AOS537. 
  11. Stone, Charles J. (1977). Consistent nonparametric regression. Annals of Statistics 5 (4): 595–620. doi:10.1214/aos/1176343886. 
  12. Samworth, Richard J. (2012). Optimal weighted nearest neighbour classifiers. Annals of Statistics 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. ISBN 1-58113-217-4. doi:10.1145/342009.335437. 
  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. ISSN 1384-5810. doi:10.1007/s10618-015-0444-8. 

Джерела[ред. | ред. код]