Это седьмой день моего участия в августовском испытании обновлений, подробности о мероприятии:Испытание августовского обновления
Обзор алгоритма
Алгоритм k-ближайших соседей — это метод классификации путем измерения расстояния между различными собственными значениями. Идея состоит в том, что если большинство из k наиболее похожих (соседних) выборок в пространстве признаков принадлежат какому-то классу, то эта выборка также принадлежит этому классу. В алгоритме K-ближайших соседей выбранные соседи уже являются правильно классифицированными объектами. Мы только решаем, какую категорию выборки разделить в соответствии с категорией k (обычно не более 20) соседних выборок.
Поток алгоритма
Общий поток алгоритма k-ближайших соседей:
- Сбор данных
- Рассчитайте расстояние между тестируемыми данными и обучающими данными (обычно с использованием евклидова расстояния).
- Сортировка рассчитанных расстояний
- Найдите значения k с наименьшим расстоянием
- Рассчитать частоту нахождения каждой категории в значении
- Вернуть категорию с наибольшей частотой
Особенности алгоритма
преимущество:
- Принцип прост, его легко понять, и здесь нет сложной математической теории;
- Предположений нет, сфера применения широкая;
- Меньше подвержен выбросам.
недостаток:
- предъявляет высокие требования к скорости вычислений и объему памяти компьютера, особенно в случае большого объема данных;
- Пример дисбаланса проблемы. Когда номер определенной метки особенно велик, это вызовет отклонение, однако в действительности некоторые данные трудно получить, и их количество действительно относительно невелико.
выбор к
Значение K может напрямую влиять на эффект предсказания. Что касается того, как выбрать подходящий K, нет фиксированного метода расчета, но полагайтесь на опыт.Например, оптимальное значение K может быть получено с использованием метода перекрестной проверки.
расчет расстояния
Существует множество способов измерения значений расстояний, в том числе манхэттенское расстояние, расстояние Махаланобиса, расстояние Чебышева и т. д. В общем, классическийЕвклидово расстояние, который в вычислительном отношении невелик, легко интерпретируется и достаточно точен.
улучшение проблемы
(1), взвешенное расстояние
После нахождения k ближайших соседей решение прямого голосования может быть неточным. Это эквивалентно тому, что каждая соседняя точка оказывает одинаковое влияние на точку измерения. Но вообще говоря, измеряемая точка должна быть более «похожей» на точки выборки, которые находятся рядом с ней, и менее «похожа» на точки выборки, которые находятся дальше. Это требует дальнейшего анализа значения расстояния, добавления веса ближней точке и уменьшения влияния дальней точки на принятие решения. Ниже описаны два метода измерения веса.
- Обратная функция
- Гауссова функция
(2), дерево КД
использованная литература
zhuanlan.zhihu.com/p/268873551