Язык Python часто используют в области Machine Learning. Давайте тоже напишем простейший алгоритм классификации, который поможет нам отличить слонов от бегемотов — метод N ближайших соседей.
Для упрощения задачи будем считать, что слоны и гиппопотамы характеризуются тремя действительными параметрами: весом (в тоннах), ростом (в метрах) и цветом (в градациях серого: 0.0 — чёрный, 1.0 — белый), которые в совокупности составляют 3-мерный вектор X. Пусть у нас есть данные о M животных: известны их параметры Х и известно, к каким типам они относятся (тип описывается целым числом — 0 для бегемота, 1 для слона).
Допустим, что у нас есть измеренный вектор параметров Y животного, тип которого мы хотим определить. Вычислим евклидовы расстояния от вектора Y до каждого из векторов X из известных данных: Тогда, для определения типа исследуемого животного возьмём N самых близких по параметрам животных и усредним значения, обозначающие типы. Например, если при N=3 оказалось, что 3 самых близких животных это 2 слона (обозначаемые цифрой 1) и один бегемот, то средним будет значение 2/3. Далее, если усреднённое значение больше 0.5, то считаем, что животное — слон, иначе — бегемот.
Формат ввода В двух отдельных строках параметр N, затем параметр M. Далее M строк, в каждой 3 значения: вес, рост, цвет животного. Далее строка из M целых чисел, обозначающих тип каждого животного, параметры которых вводились на предыдущем шаге. Далее строка из 3-х элементов с параметрами животного, тип которого мы хотим определить.
Формат вывода Строка с определённым алгоритмом типом животного — ‘elephant’ или ‘hippopotamus’, в зависимости от усреднённого значения.
| Ввод | Результат |
|---|---|
| 3 5 1.92 1.6 0.56 2.79 1.92 0.24 2.36 1.89 0.15 1.93 1.5 0.5 1.15 1.6 0.25 0 1 1 0 0 2.63 2.02 0.2 | elephant |