Вероятно, самый простой алгоритм, который приходит мне на ум, когда я думаю об обучении с учителем, — это алгоритм ближайших соседей. Вам не нужно иметь какой-либо опыт машинного обучения, чтобы понять этот алгоритм. Итак, давайте погрузимся в него и посмотрим, о чем вся эта суета. Я также расскажу об основных вопросах, связанных с ближайшими соседями, которые задают на собеседовании при приеме на работу в сфере машинного обучения. Этот блог лучше послужит вашей цели, если вы подумаете о вопросах, прежде чем сразу переходить к ответу.
Ближайшие соседи
Когда мы говорим о контролируемом машинном обучении, мы имеем в виду, что у нас есть входные данные вместе с метками или истинными выходными значениями. И обучение происходит с помощью обратной связи, которая проверяет, насколько наш прогнозируемый результат отличается от истинного вывода, очень похоже на то, что мы видим в системах управления с обратной связью. Хорошая часть алгоритма ближайших соседей заключается в том, что нам не нужно тренироваться. наши параметры, или другими словами это непараметрическая модель.
Что такое непараметрическая модель?
Во-первых, давайте поговорим о том, что такое параметрическая модель. Когда для вывода модели на этапе тестирования не требуются входные данные, мы можем назвать ее параметрической моделью. Возьмем пример нейронной сети:
Как видно из рис. 2, вес в основном представляет собой силу связи между двумя нейронами. Во время обучения входные данные передаются входному слою, и после обработки он дает прогнозируемый результат, который затем сравнивается с истинным выходом, и ошибка распространяется обратно для вычисления весов. На этапе обучения модель учится на входных данных и соответствующим образом корректирует свой вес. После завершения обучения нам больше не нужны входные данные. У нас уже есть веса, и как только вы пройдете тестовые данные, модель выдаст вам результат. Это параметрическая модель. Но в ближайших соседях для каждых тестовых данных нам нужно иметь доступ ко всем входным данным для расчета выходных данных. Именно поэтому мы называем ее непараметрической моделью.
1. Можете ли вы назвать какой-либо недостаток переноса всех входных данных?
Самый большой недостаток, который я могу придумать, это нехватка места. Ничего страшного, когда мы используем миллионы входных данных для обучения любой модели. Итак, подумайте о встроенной системе, такой как ваш мобильный телефон, которая имеет гораздо больше ограничений по пространству, чем компьютерная система. Для каждых тестовых данных, если вам нужно хранить весь миллион входных данных в своем мобильном телефоне, совершенно очевидно, что это займет много памяти. Чтобы дать вам более глубокое представление об этом, возьмем в качестве примера, что мы классифицируем изображения с помощью ближайших соседей. Допустим, каждое наше изображение имеет размер 1600 * 1200 и имеет все три канала RGB. Мы делаем любую фотографию на наш мобильный телефон и хотим классифицировать ее с помощью алгоритма ближайших соседей.
Сколько памяти потребуется?
1600*1200*24*1 000 000 бит = 125 гигабайт (красный канал — 8 бит, зеленый канал — 8 бит и синий канал — 8 бит). Как вам это, задроты? Потребуется 125 гигабайт памяти, чтобы классифицировать картинку, имеющую 1 млн цветных входных данных (изображений). Вот почему это очень наивный алгоритм, и мы не используем его на практике. Но мы можем использовать его для меньшего набора данных.
Теперь давайте поговорим о том, что мы подразумеваем под ближайшими соседями. Желтые шары и фиолетовые шары на рис. 3 представляют два разных класса и вместе образуют входные данные. Красный шарик — это тестовые данные, которые необходимо отнести к одному из двух классов. Алгоритм измеряет расстояние красного шара до всех входных данных, и в зависимости от того, какой шар ближе всего к нему, красный шар присоединяется к этой группе. На рисунке красный шар находится ближе всего к желтому шару, поэтому красный присоединяется к желтой армии. Имейте в виду, я еще не говорю о k-ближайшем алгоритме. В k-ближайшем алгоритме мы берем голоса k-ближайших точек.
Алгоритм K-ближайших соседей
Как обсуждалось в предыдущем разделе, K-ближайшие соседи учитывают k ближайших соседей, в то время как ближайший сосед учитывает ближайшего соседа. Например: на рис. 3, если мы хотим назначить группу (желтую или фиолетовую) контрольной точке (красная точка) на основе алгоритма ближайшего соседа, мы назначим ей желтую группу, так как желтая точка ближе всего к ней. В то время как, если мы хотим назначить группу на основе k-ближайшего алгоритма (k = 3), красной точке будет назначена фиолетовая группа, поскольку среди трех ближайших к красной точке точек две точки принадлежат фиолетовой группе, и каждая точка считается за один голос, поэтому фиолетовый побеждает. Если мы возьмем k = 6, красная точка будет назначена желтой группе, поскольку среди шести ближайших соседей красной точки есть 4 желтых точки и 2 красные точки. Поскольку каждая точка считается за один голос, побеждает максимум. И поэтому красной точке присваивается желтая группа.
2. Эй, k=3 делает контрольную точку фиолетовым элементом, а k=6 делает контрольную точку желтым элементом. При изменении k меняется метка, это сбивает с толку. Так как же нам определить значение k?
Очень хороший вопрос! Это определяется проверочным набором. Что такое проверочный набор? Вы можете посетить этот блог для полного понимания.
Вкратце, входные данные можно разделить на две части. Обучающий набор используется повсюду для классификации контрольной точки, а проверочный набор используется для настройки любых гиперпараметров. Здесь k — это гиперпараметр, значение которого необходимо правильно настроить! Для k=1,2,3,….,100 мы классифицируем точки в наборе данных проверки и вычисляем, сколько точек правильно классифицировано, поскольку у нас есть метки для набора данных проверки, помните? Значение k, дающее минимальную ошибку или максимальную точность, можно принять за окончательное значение. И тогда мы можем использовать его на тестовом наборе.
3. Помнится, один мой коллега спросил меня, почему мы берем нечетное значение k в бинарной классификации. Я почти уверен, что вы сможете ответить на этот вопрос, но не волнуйтесь, если вы только начинаете.
По сути, когда классификация относится к двум группам (бинарная классификация), может быть ничья, верно? Если k принять за четное число, скажем, 2, то два ближайших соседа могут принадлежать к разным группам, и у нас будет ничья. Итак, мы принимаем значение k как нечетное число, чтобы не столкнуться с ничьей. Но допустим, после настройки гиперпараметров наилучшее значение k оказывается четным числом в двоичной классификации, тогда что делать? Затем мы можем классифицировать контрольную точку как члена любой из групп.
4. Есть ли у нас проблема переобучения или недообучения k-ближайших соседей?
Да! Когда значение k очень мало, модель остается очень чувствительной к выбросам и, таким образом, пытается переобучиться. В то время как, когда значение k очень велико, модель не соответствует.
Как видно из рис. 4, граница очень сложная при K=1 и сглаживается при увеличении K. Позвольте мне привести вам еще один пример, чтобы понять недообучение и переоснащение. Я думаю о недообучении как о предвзятости. Допустим, у нас есть 50 входных точек, из которых 30 точек принадлежат группе 1, а остальные принадлежат группе 2. Теперь, если мы возьмем K-ближайших соседей (K=50), группа с большинством входных точек всегда будет побеждать, несмотря ни на что. . Это означает, что смещение оказывает значительное влияние на классификацию точек данных теста и, следовательно, преобладает недостаточное соответствие. С другой стороны, K=1 соответствует модели.
Какова временная сложность этого алгоритма?
Если мы возьмем евклидово расстояние в качестве способа расчета расстояния, алгоритм будет состоять из трех основных шагов.
1>Рассчитайте расстояние контрольной точки от каждой точки входных данных.
Предположим, что каждая точка входных данных имеет D признаков и имеется N точек входных данных, поэтому сложность этого шага будет равна O(ND).
2> Отсортируйте точки в порядке возрастания, чтобы у нас было k ближайших точек данных к контрольной точке.
Я прилагаю ссылку, где вы можете проверить, как мы можем рассчитать временную сложность сортировки K ближайших точек данных. Короче говоря, это O(NlogK).
Итак, общая сложность = O(ND)+O(NlogK). Это означает, что если у нас много точек данных или большое количество признаков, сложность алгоритма будет увеличиваться линейно.
