Цель этой лекции — рассмотреть более сложные темы, связанные с KNN, и углубиться в детали. Я рекомендую вам прочитать Часть 1, если вы еще этого не сделали.
Темы, затронутые в этой лекции:
- KNN и проклятие многомерности
- Временная и пространственная сложность KNN
- KNN со взвешиванием функций
1. KNN и проклятие размерности
Напомним общий факт: всем алгоритмам машинного обучения нужен плотный набор данных, чтобы точно предсказывать по всему пространству данных. Ошибки возникают во всех алгоритмах, если между данными есть пробелы (разреженные данные). Но разреженность данных еще сложнее, когда речь идет о KNN, вот почему:
Как видно из Части 1, KNN основан на предположении, что аналогичные/близкие входные данные дают аналогичные выходные данные. Таким образом, две точки считаются подобными, если они близки в каждом отдельном измерении. Давайте изучим, как данные становятся более разреженными, когда размерность входного пространства увеличивается:
Таким образом, для алгоритма KNN, берущего контрольную точку P, длина ребра наименьшего куба, содержащего все k ближайших соседей, увеличивается экспоненциально по мере увеличения размерности. Например, пусть установлено k = 10 и n количество обучающих выборок n = 1000, длина ребра наименьшего куба изменяется следующим образом
Очень удивительно, что когда d велико, нам почти нужно все пространство, чтобы найти 10-NN. Это проклятие размерности…
Можно подумать, что за счет увеличения количества обучающих примеров можно обойти эту проблему, но это не всегда возможно, особенно при большом d, потому что нужно количество отсчетов, которое растет экспоненциально с d.
Из этого следует помнить, что в более высоких измерениях:
1. Пространства более высоких измерений пусты
2. Точки в многомерных пространствах изолированы
3. Окрестности больше не являются локальными
4. Исчезает понятие ближайших соседей
2. Пространственно-временная сложность КНС
Пространственная сложность
Мы можем уменьшить сложность пространства, используя уменьшение размерности или выбрав меньшее количество обучающих примеров. Вот некоторые из стратегий:
Редактирование: удалить точки данных, которые не влияют на границы решения. Например, рассмотрим одну точку данных (также известную как «выброс»), окруженную множеством точек данных из другого класса. Если мы выполним прогноз kNN, эта единственная точка данных не повлияет на прогноз метки класса при множественном голосовании; следовательно, мы можем безопасно удалить его. (Мы также можем подумать о переименовании этой точки)
Прототипирование. Идея состоит в том, чтобы заменить выбранные точки данных прототипами, которые суммируют несколько точек данных в плотных регионах. Это можно сделать с помощью некоторого алгоритма кластеризации, такого как K-Means.
Что касается временной сложности, это зависит от того, как мы выполняем поиск k точек и как мы храним обучающие примеры (структуру данных).
Грубая сила:
Предположим, что обучающие примеры хранятся в каком-то списке (матрица — это список строк), каждый элемент списка — экземпляр. У нас есть две версии метода грубой силы:
В этой первой версии мы перебираем обучающие примеры k раз, чтобы найти ближайший элемент, который еще не был добавлен в список K-ближайших соседей. На каждой итерации мы вычисляем расстояния между контрольной точкой и обучающими примерами. Другая версия может вычислять расстояния между контрольной точкой и обучающими примерами один раз и сохранять их, что добавит дополнительную пространственную сложность к той, что была показана ранее. Это вторая версия:
Максимальная куча
Есть улучшение, которое мы можем внести во вторую версию, когда у нас будет список Расстояний. Вместо повторения k раз обучающих примеров мы могли бы использовать max-heap. >(вы не знаете, что такое max-heap? проверьте это) на первом этапе вы собираетесь поместить случайные расстояния в вашу max-heap, за одну итерацию по обучающим примерам, сравните текущее расстояние с корнем максимальной кучи, если оно больше, вы должны пропустить, в противном случае вставьте элемент в максимальную кучу, который принимает log (k). После завершения одной итерации K-ближайшими соседями становятся элементы максимальной кучи. Таким образом, временная сложность составляет O(n*d+n*log(k)).
Умная структура данных (например, k-d Tree)
Вместо того, чтобы хранить обучающие примеры в простом массиве. Мы можем подумать о том, чтобы хранить их в более разумной структуре данных, которая упростит поиск ближайших соседей. Это означает сделать процесс предсказания менее сложным (ускорить), усложнив процесс обучения. Одной из структур данных, которые мы можем использовать, являются деревья K-D. Я не буду подробно останавливаться на этой части; все, что вам нужно знать, это то, что существуют некоторые структуры данных, которые упростили бы поиск во время предсказания ближайших соседей.
Первым шагом является построение дерева kd с временной сложностью O (d * n * log (n)), после чего мы можем использовать его для поиска ближайшего соседа для данной точки, что можно сделать за O ( журнал (п)). K-d Tree не подходит для многомерных пространств, мы можем подумать об использовании локального чувствительного хеширования. Я собираюсь рассказать об этом алгоритме в отдельной лекции.
3. KNN с взвешенными функциями
В этой части мы будем рассматривать евклидово расстояние как нашу метрику расстояния.
Мы используем обучающие примеры для определения весов, таким образом, мы будем придавать большее значение наиболее важным функциям и даже выполним выбор функций, чтобы сделать прогноз, используя только самые важные функции. Этот метод также предоставляет информацию о важности каждой функции.
Это вторая часть серии, посвященной алгоритму KNN.
