КNN (1)

1.

Машинное обучение и
нейросетевые
технологии

2.

Кол-во
Кол-во
аудиторных часов лекционных часов
92
50
Кол-во часов
практических
занятий
42
Формы
промежуточной
аттестации
Контрольная,
экзамен

3.

Содержание
Алгоритм k-NN.
Модель k-NN.
Метрика.
Построение kd-дерева и поиск в нем.

4.

Алгоритм k-ближайших соседей
Метод k-ближайших соседей (k-NN),
предложенный Ковером и Хартом в 1968 году,
является базовым методом классификации и
регрессии.
Для задачи классификации. Входными данными kNN является вектор признаков, соответствующий
точке в пространстве признаков. Выходными
данными является класс элемента. K-NN
предполагает, что класс элемента определен для
заданного набора обучающих данных.
При классификации нового экземпляра данных
класс предсказывается на основе класса k
элементов из обучающей выбоки, ближайших к нему.

5.

Алгоритм k-ближайших соседей
k-NN не имеет явного процесса обучения. Он использует
набор обучающих данных для разделения пространства
векторов признаков и служит «моделью» для своей
классификации.
Основными элементами k-NN являются:
выбор значения k,
метрики расстояния,
правила принятия решений по классификации.
При классификации нового входного элемента задается
обучающий набор данных . Осуществляется поиск k
ближайших к нему элементов в обучающем наборе данных.
Если большинство из этих k ближайших экземпляров
принадлежат определенному классу, новый входной
экземпляр будет классифицирован в этот класс.

6.

Алгоритм k-ближайших соседей
Алгоритм k-ближайших соседей:
Вход: обучающий набор данных T={(x1, y1),(x2, y2), ...,(xN, yN)},
где xi∈X⊆Rn является вектором признаков, yi∈Y={с1, с2,…, сk,}
класс элемента, i=1,2,...,N; и скорость обучения α (0 < α ≤ 1).
Выход: y, класс к которому принадлежит объект х.
1.
Согласно заданной метрике расстояния, в обучающем наборе T
находятся k точек, ближайших к x, а окрестность точки x,
содержащая эти k точек, обозначается как Nk(x);
2.
Определяется y − класс x в Nk(x) в соответствии с правилами
принятия решений (например, большинством голосов):