Гайд по лабе KNN

Выбор датасета с openml.org:

Выбранный датасет должен содержать хотя бы 100 объектов и хотя бы 3 класса. Чем меньше объектов и чем меньше классов, тем быстрее будет происходить перебор параметров регрессии. Выбрав хороший датасет можно сильно упростить себе жизнь, в таком датасете все фичи - вещественные числа и в нем нет пропусков.

Подготовка датасета:

Датасет нужно нормализовать по X(сделать так, чтобы все значения фичей лежали в отрезке [0...1]) и по Y(сделать так, чтобы нумерация классов была 0, 1, 2, ...).

Пример нормализации

Был вот такой датасет с 3-мя объектами, у каждого по 2 фичи(одна строка - один объекта, первые два числа - фичи, третье число - нужный класс):

8 0 1

-2 7 2

0 10 1

Нормализуем X:

1 0 1

0 0.7 2

0.2 1 1

Максимальное число в столбце становится 1, минимальное 0, остальные "растягиваются" между ними в таких же пропорциях как были до нормализации.

Нормализуем Y:
1 0 0

0 0.7 1

0.2 1 0

Сведение к регрессии:

Сейчас наш датасет представляет собой задачу классификации(когда нужно определить к какому классу относится объект). Мы же хотим свести эту задачу к регрессии(когда нужно получить одно вещественное число), потому что KNN работает лучше на регрессиях. А потом по полученному числу хочется понимать к какому классу принадлежит объект(да, вот такой вот финт). И все это можно сделать двумя разными способами:
1) Наивный способ определения класса по вещественному числу:
Смотрим на полученное вещественное число из регрессии, например 1.71, видим, что оно скорее принадлежит к объектам класса 2, а не 1, туда его и определяем.

2) Крутой модный способ с OneHot преобразованием:

Примером понять будет проще, чем на словах.

Пусть был датасет ({X_i} - вектор фичей у объекта с номером i):

{X_0} 1
{X_1} 2
{X_2} 0
{X_3} 1

Мы делаем из него столько новых датасетов бинарной классификации сколько разных классов у нас бывает, в данном случае у нас всего 3 разных класса(0, 1 и 2):
Для класса о

{X_0} 0
{X_1} 0
{X_2} 1
{X_3} 0

Для класса 1

{X_0} 1
{X_1} 0
{X_2} 0
{X_3} 1

Для класса 2

{X_0} 0
{X_1} 1
{X_2} 0
{X_3} 0

По каждому такому датасету и каждому объекту получаем результат регрессии, в итоге у нас получится примерно такая таблица:
0 1 2
{X_0} 0.1 0.8 0.6
{X_1} 0.3 0.4 0.5
{X_2} 0.4 0.1 0.2
{X_3} 0.2 0.6 0.1

Для каждого объекта скажем, что он принадлежит к тому классу, у которого наибольшая вероятность.
{X_0} 1
{X_1} 2
{X_2} 0
{X_3} 1

Настройка(на самом деле перебор) гипермараметров

У нас есть гиперпараметры - функция расстояния, функция ядра, K если ядро не фиксированно, H если фиксированно. Все это нужно перебрать, посчитать Fскор и выбрать наилучшую комбинацию гиперпараметров.
Как считать Fскор? Нам нужна таблица как та, которую нам дали в Bшке на CF. Сами ее строим вот таким методом: поочереди забираем из датасета по одному объекту и предсказываем к какому классу он принадлежит. Это и называется Leave-One-Out перекрестной проверкой.

Еще раз все, но кратко

Для каждого способа сведения задачи к регрессии делаем следущее:

1) Перебираем гиперпараметры

2) Для каждого набора гиперпараметров считаем его Fскор. Как?
От датасета "откусываем" по 1 объекту и смотрим куда мы его распределяем(запуская наш код задачи С с CF) с помощью выбранного способа сведения к регрессии.

3) Выбираем лучшую комбинацию гиперпараметров(чем выше Fскор, тем лучше набор гиперпараметров).

Графики

Не забудьте про них

Советы:

1) Без сданной B и C c CF'а будет трудно.

2) То, что на питоне перебирается часами, на плюсах перебирается за минуты.

3) Если у вас разное кол-во объектов в классе, то не забудьте, что нужно считать взвешенную Fмеру.
4) Сдача проходит довольно легко, если понимаешь, что происходит в коде и писал сам. Препод особо не валит(я например напрочь забыл про графики и мне разрешили донести на след. лабе).