Примеры работы алгоритма KNN

Решим задачу классификации для ирисов (используя данные об ирисах Фишера, которые доступны по ссылке). Имеется набор данных, собранных Р. Фишером, о 150 цветках трех классов: Iris Setosa, Iris Versicolour, Iris Virginica, по 50 записей для каждого. Известна длина и ширина чашелистика и лепестка всех этих ирисов.

Для простоты рассмотрим только два входных поля: длина чашелистика и длина лепестка, а также выходное – класс цветка.

Необходимо определить класс двух цветков со следующими значениями длины чашелистика и лепестка в сантиметрах: 5,3 и 1,6 (первый), 6,1 и 4,8 (второй). На рисунке 2 показано размещение новых (светло-зеленая точка – цветок 1, красная – цветок 2) записей среди уже известных.

Рисунок 2 – Диаграмма размещения классов

Рассмотрим первый цветок. Установим значение k = 3. Таким образом, необходимо найти трех ближайших соседей. Для первого цветка это будут цветки со следующими значениями длины чашелистика и лепестка: A (5,3; 1,5), В (5,2; 1,5) и С (5,2; 1,5). Покажем, чему равны расстояния до первого цветка (оба атрибута равнозначны):

d(цветок1, A) =

d(цветок1, В) =

d(цветок1, C) =

Полученные сведения объединим в таблицу 1.

Таблица 1 – 3 ближайших соседа для цветка 1

Теперь определим класс нового цветка. Воспользуемся простым невзвешенным голосованием. Так как все три цветка A, B и C принадлежат к классу Iris-Setosa, то он получает 100% голосов, и первому цветку присваиваем этот класс. Если увеличить (рисунок 3) на диаграмме окрестность около первого цветка, то можно увидеть, что он окружен точками синего цвета, соответствующие цветам класса Iris-Setosa.

Рисунок 3 – Увеличенный фрагмент диаграммы возле первого цветка

Теперь рассмотрим более сложный случай cо вторым цветком.

Зададим k = 3 и предположим, что длина лепестка вдвое важнее длины чашелистика. Ближайшими тремя соседями будут следующие цветки:

A (6,1; 4,7), B (6; 4,8), C (6,2 4,8)

Покажем, чему для них равны расстояния:

d(цветок2, A) =

d(цветок2, B) =

d(цветок2, C) =

В и С – это Iris Virginica, а A – Iris Versicolour.

Объединим полученные сведения в таблицу 2.

Таблица 2 – Три ближайших соседа для цветка 2

Рассмотрим взвешенное голосование.

Так как 200>50, то второй цветок классифицируется как Iris Virginica.