Метод K-ближайших соседей (KNN). Принцип работы, разновидности и реализация с нуля на Python

[Flokis_guy]

Хоть по KNN и много статей, но перечисление различных подходов к построению модели это хорошо. Я бы добавил ещё про Kernel KNN, да, он проигрывает по скорости классическому алгоритму, и на больших данных он не так эффективен из-за расходов, но на маленьких и для большей точности как раз подойдёт.

[egaoharu_kensei]

Верно подмечено. Спасибо дополнение. Однако я в статье решил упомянуть подходы к построению KNN в контексте реализации scikit-learn. Возможно, стоило рассказать побольше: честно, как-то не подумал об этом :)

[lrdprdx]

Спасибо за статью, но ИМХО краткое объяснение, что такое Ball Tree, вызывает больше вопросов, и, подозреваю, вообще ошибочно. После чтения интернетов (в том числе одной из статей, приведенных в конце поста) я вижу, что расстояние между гиперсферами вообще не используется. Используется же расстояние от тестовой точки до гиперсферы, которое определяется иным способом, нежели указанным в посте.

Вы описываете также алгоритм образования дочерних гиперсфер. Мне он тоже не совсем понятен. Я подозреваю имелся в виду следующий:

1) Находим диаметр множества точек

2) Проецируем все точки множества на направление диаметра

3) Отмечаем медиану (точку на диаметре, по обе стороны от которой одно и то же кол-во точек множества)

4) Далее в каждой из половин строим сферу с центром (например) в центре масс и радиусом, равным расстоянию наиболее удаленной точки от центра масс

И это только один из возможных способов разбиения.

В общем, я бы либо опустил пункты описания и оставил бы общие слова (в каком-то смысле это напоминает обычный бинарный поиск), либо уточнил описание.

[egaoharu_kensei]

Расстояние между гиперсферами в алгоритме BallTree нужно не для поиска ближайших соседей, а для определения пересекающихся гиперсфер (могут возникнуть по разным причинам), информация о которых помогает лучше изучить полученную древовидную структуру для её дальнейшей оптимизации. Этот момент я только что обозначил в статье отдельно, чтобы не было недопониманий.

Я же описал основной принцип работы деревьев, а для более глубокого понимания, на мой взгляд, стоит писать отдельную статью с обзором и реализацией с нуля подходов к построению KNN, поскольку они не ограничиваются лишь теми, что используются в реализации scikit-learn.

Если вам интересна данная тема и вам есть про это что рассказать, не хотите ли написать про это статью? Думаю, многие сочтут это полезным.