Метод k-ближайших соседей (K-nearest neighbor)

Разделы: Алгоритмы

Loginom: Кластеризация (обработчик)

Метод решения задачи классификации, который относит объекты к классу, которому принадлежит большинство из его ближайших соседей в многомерном пространстве признаков. Это один из простейших алгоритмов обучения классификационных моделей.

Число – это количество соседних объектов в пространстве признаков, которое сравнивается с классифицируемым объектом. Иными словами, если , то каждый объект сравнивается с 10-ю соседями. Метод широко применяется в технологиях Data Mining для решения задач классификации.

В процессе обучения алгоритм просто запоминает все векторы признаков и соответствующие им метки классов. При работе с реальными данными, т.е. наблюдениями, метки класса которых неизвестны, вычисляется расстояние между вектором нового наблюдения и ранее запомненными. Затем выбирается ближайших к нему векторов, и новый объект относится к классу, которому принадлежит большинство из них.

Выбор параметра противоречив. С одной стороны, увеличение его значения повышает достоверность классификации, но при этом границы между классами становятся менее четкими. На практике хорошие результаты дают эвристические методы выбора параметра , например, перекрестная проверка.

Несмотря на свою относительную алгоритмическую простоту метод показывает хорошие результаты. Главным его недостатком является высокая вычислительная трудоемкость, которая увеличивается квадратично с ростом числа записей в наборе данных.

results matching ""

    No results matching ""