 |
Метод K-ближайших соседей для решения задачи классификации
|
|
|
|
Метод K-ближайших соседей для решения задачи классификации
Метод K-ближайшего соседа (англ.: k-nearest neighbors method, k-NN) - один из методов решения задачи классификации.
В основе k-NN лежит следующее правило: объект считается принадлежащим тому классу, к которому относится большинство его ближайших соседей. Под " соседями" здесь понимаются объекты, близкие к исследуемому в том или ином смысле.
Метод k-ближайших соседей (непараметрический метод)
Этот метод работает с помощью поиска кратчайшей дистанции между тестируемым объектом и ближайшими к нему классифицированным объектами из обучающего набора. Классифицируемый объект будет относится к тому классу, к которому принадлежит ближайшие k соседей (объектов).
Выбор оптимального значения k для knn
Результат, получаемый методом k-NN, сильно зависит от выбора параметра k.
Возникает вопрос: как выбрать значение параметра k, чтобы минимизировать количество неверных ответов, полученных методом k-NN?
Не существует конкретного способа определить наилучшее значения для k. Поэтому нужно пробовать несколько значений, чтобы найти наилучшее из них. На практике чаще всего полагают
k =√ n,
где n - общее число объектов.
Метрика (функция расстояния)
Необходимо уметь определять, насколько объекты близки друг к другу, т. е. уметь измерять " расстояние" между объектами.
По умолчанию в R для непрерывных признаков используется расстояние Евклида
dist =корень[(x2 − x1)2 + (y2 − y1)2]
В качестве метрики может быть и любая мера близости объектов, например, по цвету, форме, вкусу, запаху, интересам, особенностям поведения и т. д.
Нормализация данных
Важной составляющей многих методов является нормализация данных. Разные признаки обычно представлены в разных масштабах и изменяются в разных диапазонах. Например, возраст 0-100, доход 15000-100000, концентрация Ca 0. 01-0. 05. В этом случае значения дистанции могут сильно зависеть от признаков с большими диапазонами.
|
|
|
Z - нормализация (scale)
X’ =(x − M(X))/σ (X)
MinMax - нормализация -> (0, 1)
X’ =(x − min(X))/(max(X) − min(X))
Метод K-ближайших соседей в R
install. packages(" class" )
library(class)
knn(train, test, train-class, k)
30. Кластеризация
Кластерный анализ (Data clustering) — задача разбиения заданной выборки данных (объектов) так, чтобы каждый кластер состоял из схожих объектов, а объекты разных кластеров значительно отличались друг от друга.
Кластеризация предназначена для разбиения совокупности объектов на однородные группы (кластеры или классы). Если данные выборки представить как точки в признаковом пространстве, то задача кластеризации сводится к определению " сгущений точек".
Кластеризация является описательной процедурой, она не делает никаких статистических выводов, но дает возможность провести разведочный анализ и изучить " структуру данных".
Кластер (cluster, " скопление" ) можно охарактеризовать как группу объектов, имеющих общие свойства.
Характеристиками кластера можно назвать два признака:
внутренняя однородность;
внешняя изолированность.
Методы кластерного анализа
Существует около 100 разных алгоритмов кластеризации, однако, наиболее часто используемые иерархический кластерный анализ и кластеризация методом k-средних.
В результате применения различных методов кластеризации могут быть получены неодинаковые результаты, это нормально и является особенностью работы того или иного алгоритма.
Основные этапы кластерного анализа
1. выбор признаков (столбцов Xi), по которым будет проводиться сравнение;
|
|
|
2. вычисление меры сходства(метрики) между объектами (строками);
3. группировка объектов в кластеры с помощью того или иного метода кластеризации;
4. проверка применимости полученного кластерного решения.
(!!! ) И выбор объектов, и выбор признаков, и выбор метрики вместе с процедурой кластеризации существенно влияют на конечный результат.
Иерархический кластерный анализ
Для визуального представления результатов кластеризации используется дендрограмма - дерево, построенное по матрице мер близости между кластерами.
При этом длина ребра соответствует расстоянию между кластерами.
Алгоритм иерархической кластеризации
Дерево строится от листьев к корню.
В начальный момент времени каждый объект содержится в собственном кластере. Далее происходит итеративный процесс слияния двух ближайших кластеров до тех пор, пока все кластеры не объединятся в один или не будет найдено необходимое число кластеров. На каждом шаге необходимо уметь вычислять расстояние между кластерами и пересчитывать расстояние между новыми кластерами.
Этапы кластерного анализа
1 Рассчитать расстояние между всеми объектами с помощью выбранной метрики (расстояние Евклида)
2 Произвести объединение наиболее близких точек
3 Согласно одному из алгоритмов объединения (метод одиночной связи, метод полной связи, ... ) произвести последовательное (на каждом шаге присоединяется 1 объект) объединение всех исследуемых объектов в кластеры (группы);
4 Построить график расстояний объединения объектов (дендрограмму)
5 Определить на дендрограмме количество кластеров, которые следует выделить для указанных объектов исследования.
|
|
|
