Автор оригинала: Volodymyr Lut.
Обычно я вижу, что многие студенты и разработчики, пытающиеся проникнуть в машинное обучение, путаются со сложными темами, с которыми они сталкиваются в самом начале своего пути. Я хочу сделать глубокое, но понятное введение в алгоритм, который настолько прост и элегантен, что вам понравится. Если вы инженер по машинному обучению, но имеете ограниченное представление об этом, было бы также полезно прочитать его.
Я работал разработчиком программного обеспечения в течение многих лет, и все вокруг меня говорили об этой совершенно новой науке о данных и машинном обучении (позже я понял, что на этой планете нет ничего нового), поэтому я решил получить степень магистра в университете, чтобы познакомиться с ней.
Наш первый модуль был общим вводным курсом по науке о данных, и я помню, как сидел и пытался понять, что происходит. Я немного знал о самой области, ее истории и потенциале, и мне было трудно понять, как она работает.
Поэтому мне было интересно: как машина может определить, есть ли на картинке котенок или собака? Мои инструменты как программиста были переменными, функциями, условиями, циклами, абстракциями в течение многих лет. Мне было очень комфортно с ними, но как я могу на самом деле применить эти знания к такого рода проблемам? Все сценарии были предопределены мной как программистом. Я знал все выходы. Как отличить котенка от собаки?
Ну, я видел их много в своей жизни. Я, вероятно, не могу отличить одну рыбу от другой, но я довольно хорошо классифицирую домашних животных. Я видел сотни кошек и собак в своей жизни, и они для меня разные – разные глаза, разные уши, лапы и хвосты, разные звуки. Эти вещи называются функциями . Машина также должна полагаться на некоторые функции. Одна собака похожа на другую – у них есть общие черты . Спам-письма имеют определенные общие слова.
Ладно, ближе к алгоритмам. Существует интуиция, что если правильно нанесены на график, элементы одного класса создадут кластеры на графике.
Следовательно, если элемент неизвестного класса – из тестового набора данных – мы могли бы сказать с некоторой степенью уверенности , что он будет иметь тот же класс, что и большинство его __ k ближайших соседей__ на графике. Это KNN в двух словах. Ничего больше.
Если 4 человека вокруг меня во время обеда – студенты Data Science и один-студент-психолог, то я, скорее всего, тоже студент программы Data Science.
Пока все просто, давайте усложним ситуацию: KNN можно использовать и для регрессии проблем. Возвращаясь к котятам: речь идет не о предсказании класса, в который попадает животное, а скорее о предсказании массы животного по глубине и размеру следа на снегу. В случае регрессии оценка значения элемента будет представлять собой среднее значение значений его k ближайших соседей.
Что это за “соседи”? Полегче! Это точки из обучающего набора данных с известным значением целевой переменной!
Вы чувствуете, что это правильно – алгоритм KNN не требует обучения. Он будет выполнять все вычисления во время выполнения классификации или регрессии.
Некоторые из вас, возможно, уже чувствуют что-то плохое по поводу этого “голосования большинством”. Если в населении гораздо больше записей одного класса, чем записей другого класса, это большинство голосов может быть фактически скомпрометировано из – за большей плотности записей, которые могут привести к неправильной классификации элементов KNN-та же история, что и неправильная классификация Плутона как планеты, потому что у нас было очень ограниченное знание о существовании пояса Койпера.
Кроме того, вы можете задаться вопросом об этом слово расстояния . О каком расстоянии мы говорим?
Вы правы – существует множество способов рассчитать расстояние. Для простоты мы бы говорили о простом старом евклидовом (расстояние L2) в этом посте, но вам нужно будет знать (это было безумие для меня), что существуют другие методы вычисления расстояния (см. Эту статью и Геометрию такси ). Способ вычисления расстояния, который вы выбрали бы , может повлиять на набор ближайших соседей, выбранных для точной точки данных. Более подробную информацию можно найти в этих слайдах – изображение ниже взято из них.
По определению , Евклидово расстояние между двумя точками (в евклидовом пространстве) – это длина прямой, соединяющей эти две точки.
Давайте перейдем прямо к практике, чтобы быть более ясными.
Рассмотрим набор данных Iris , содержащий 50 образцов от каждого из трех видов ириса (Iris setosa, Iris virginica и Iris versicolor), содержащий данные о длине и ширине чашелистиков и лепестков .
Цель состоит в том, чтобы классифицировать цветок ириса в соответствии с этими измерениями. Вот пример этого набора данных:
5.5,3.5,1.3,0.2,Iris-setosa 7.7,2.6,6.9,2.3,Iris-virginica 7.2,3.6,6.1,2.5,Iris-virginica
Всегда разумно сначала взглянуть на визуализацию данных, чтобы увидеть, верна ли интуиция о том, что существует существенная разница между цветами трех классов. Посмотрите на эти сюжеты из Страница Википедии об Айрис
Цветы создают три отличительные группы – другими словами, цветные точки не выглядят как беспорядочный хаос. Это хороший знак того, что мы добьемся успеха.
Мы имеем дело с 4-мерным евклидовым пространством. Обозначим цветок из известного набора данных как
p ( p 1 = l e n g t h s e p a l , p 2 = w i d t h s e p a l , p 3 = l e n g t h p e t a l , p 4 = w i d t h p e t a l , ) p(p_1{sepal},{sepal},{лепесток},{лепесток},) p ( p 1 = l e n g t h s e p a l , p 2 = w i d t h s e p a l , p 3 = l e n g t h p e t a l , p 4 = w i d t h p e t a l , )
q ( q 1 = l e n g t h s e p a l , q 2 = w i d t h s e p a l , q 3 = l e n g t h p e t a l , q 4 = w i d t h p e t a l , ) q(q_1{sepal},{sepal},{лепесток},{лепесток},) q ( q 1 = l e n g t h s e p a l , q 2 = w i d t h s e p a l , q 3 = l e n g t h p e t a l , q 4 = w i d t h p e t a l , )
Используя формулу евклидова расстояния, мы можем вычислить евклидово расстояние между этими точками в пространстве ( Я обещаю, что это будет последняя математическая формула здесь ).
d i s t a n c e ( p , q ) = ∑ i = 1 n ( p i − q i ) 2 расстояние(p, q) =}^n(p_i – q_i)^2} d i s t a n c e ( p , q ) = ⎷ i = 1 ∑ n ( p i − q i ) 2
В нашем случае у нас есть 4 функции (
d i s t a n c e ( p , q ) = ( p 1 − q 1 ) 2 + ( p 2 − q 2 ) 2 + ( p 3 − q 3 ) 2 + ( p 4 − q 4 ) 2 расстояние(p, q) = \sqrt{(p_1 – q_1)^2 + (p_2 – q_2)^2 + (p_3 – q_3)^2 + (p_4 – q_4)^2} d i s t a n c e ( p , q ) = √ ( p 1 − q 1 ) 2 + ( p 2 − q 2 ) 2 + ( p 3 − q 3 ) 2 + ( p 4 − q 4 ) 2
Хорошо, последняя оставшаяся без ответа часть-это “Как мы выбираем это волшебное к”? Ответ-idk. Меньшие значения k в большинстве случаев сильно подвержены влиянию шума в наборе данных – это называется моделью с высокой дисперсией или просто переоборудованной моделью . Большие значения k приводят к большему смещению модели, что означает, что она будет игнорировать обучающий набор данных. Общий подход заключается в использовании
В зависимости от случайного разделения (не фактического размера разделения, а выполненного случайного упорядочения) этот простой алгоритм даст точность от 98% до 100% в тестовом наборе.
Хорошо, это было круто, но что произойдет, если мы будем использовать больший набор данных? Ответ печален: нам нужно было бы вычислять каждое расстояние снова и снова, и это было бы намного медленнее. Это самое сильное ограничение алгоритма KNN – он просто не эффективен для больших наборов данных. Он ничего не “узнает” из данных. Из этой проблемы вытекает другая – она плохо обобщается. Кроме того, выбор подхода к расчету расстояния и числа k может значительно повлиять на точность. Не забывайте, что зашумленные данные также сделают их менее точными или просто не функционирующими вообще (как, впрочем, и тонны других, более сложных алгоритмов).
Что мы можем сделать, если граница двух классов очень запутана элементами разных классов? Ну, один из стандартных способов-применить веса к “голосам”, таким как
Тем не менее, этот алгоритм имеет много практического применения – от старых спам-фильтров до приложений для проверки транзакций, в которых KNN используется для анализа данных регистра транзакций, чтобы обнаружить и указать на подозрительную активность.
Спасибо.