Новая, улучшенная версия алгоритма K-ближайших соседей
Улучшите свои результаты с помощью KNN, используя регуляризацию
Введение
На днях, при написании этой статьи по алгоритму KNN, я заметил одну вещь: расстояния между наблюдениями рассчитываются без учета важности каждого признака для общей задачи.
Даже если вы отфильтруете нерелевантные функции, оставшиеся все равно будут иметь разные уровни важности для прогнозирования определенной целевой переменной, и это не учитывается при определении ближайших соседей.
Затем я попытался найти реализации KNN или статьи, которые могли бы это сделать, но ничего не вышло (я нашел эту статью, которая, кажется, делает что-то похожее, но не очень ясно, как выполняется взвешивание, и в ней нет никаких сведений). выполнение). В конце концов, я решил сделать это сам, проверить, может ли это улучшить результаты, а затем опубликовать его, чтобы другие люди могли его улучшить.
Затем в этой статье будет представлена теория, лежащая в основе этого метода «регуляризации» для KNN, код Python для его реализации, результаты для игрушечного набора данных и предложения по дальнейшему улучшению.
КНН
Пусть x будет новым наблюдением, для которого мы хотим оценить значение целевой переменной y. Алгоритм KNN работает следующим образом:
1. Вычислить расстояние между x и всеми другими точками данных, для которых известно значение y.
2. Упорядочить расстояния в порядке возрастания
3. По положительному целому числу k выберите первые k расстояний из упорядоченного списка
4. Выберите k точек, соответствующих этим расстояниям
5. Если это задача классификации, пометьте x мажоритарным классом среди k наблюдений. Если это задача регрессии, оцените y, используя среднее значение y для k наблюдений.
Мера расстояния, используемая на шаге 1, может варьироваться в зависимости от поставленной задачи и типа данных, но наиболее распространенными являются евклидово расстояние, расстояние Манхэттена, расстояние Минковского и расстояние Махаланобиса.
Интуитивно это означает, что когда мы хотим предсказать значение для нового наблюдения, мы находим похожие наблюдения, для которых у нас есть эта информация, и основываем наше предсказание на этих известных значениях.
Регулярная версия
В алгоритме KNN регуляризация может быть выполнена на этапе 1 при вычислении меры расстояния между x и другими точками.
Чтобы учесть взаимосвязь между каждой переменной и целью, у нас есть несколько альтернатив. В этой статье мы будем использовать абсолютное значение коэффициента корреляции Пирсона в качестве веса для каждого признака, скорректированного с помощью параметра регуляризации:
где j представляет ранг рассматриваемого признака, а λ представляет параметр регуляризации. Чем больше параметр регуляризации, тем больше он штрафует функции, не коррелирующие с целевой переменной, и тем меньше они будут весить при расчете расстояния.
Это имеет то преимущество, что оно неотрицательно и легко интерпретируется. С другой стороны, он не будет должным образом учитывать нелинейные отношения.
Затем можно сформировать весовой вектор w из весов каждого признака, а затем применить к расстоянию Минковского:
Или на расстояние Махаланобиса:
Выполнение
Для оценки предсказательной способности регуляризованного KNN были выполнены следующие шаги:
1. Для каждой метрики расстояния (манхэттенской, евклидовой и минковского) локальное оптимальное значение k было рассчитано в пределах некоторого произвольного пространства поиска с использованием нерегламентированная версия KNN и оптимизация для MSE (среднеквадратичной ошибки)
2. То же значение k было применено к регуляризованной версии с использованием других значений λ
3. Показатели MSE, полученные обоими алгоритмами Затем сравнили, чтобы найти оптимальное решение.
Полученные результаты
Чтобы проверить его прогностическую силу, регуляризованная версия была протестирована на наборе данных о диабете, включенном в sklearn.
Набор данных содержит информацию о показателях здоровья и диабете с 442 экземплярами и 10 атрибутами, один из которых является целевой переменной для нашей задачи регрессии: количественная мера прогрессирования заболевания через год после исходного уровня. Все остальные переменные являются числовыми или бинарными и включают такую информацию, как возраст, ИМТ и уровень сахара в крови.
Регуляризация алгоритма KNN дала лучшие результаты для всех трех показателей расстояния, а наилучшая общая MSE (3314) была получена с регуляризованной версией расстояния Махаланобиса:
Как мы видим, результаты могут значительно различаться в зависимости от значения, используемого для λ (параметр регуляризации), но это все же показывает, что регуляризация алгоритма KNN может привести к улучшениям.
Выводы и дальнейшие исследования
Потенциальной областью дальнейшего улучшения может быть замена коэффициента корреляции Пирсона другим показателем, учитывающим нелинейные отношения. Если у вас есть какие-либо предложения, пожалуйста, прокомментируйте их ниже!
Полный код, использованный для тестов, и более подробную статью на эту тему можно найти здесь.
Если вам понравилась эта статья, возможно, вам понравятся и эти:
Не стесняйтесь обращаться ко мне в LinkedIn, если вы хотите продолжить обсуждение, это будет приятно (честно).
