Саморазвитие

k-ближайших соседей

Время прочтения: 3 мин.

Есть таблица со значениями 2-ух параметров, по которым некоторые объекты разделяется на типы: «хорошо», «плохо», «средне». Есть объект, у которого известно значение параметров (5.2;3.1), но не известно какого он типа.

Для понимания создадим на том же листе в excel точечную диаграмму, в качестве значений по оси X зададим данные из второго столбца, а качестве оси Y – из первого.

Для того, чтобы лучше видеть наши значения можно ограничить значения по осям и добавить подписи. Должно получиться примерно так:

Добавим и наш объект, тип которого нужно определить. Основная идея метода, который мы хотим применить, состоит в расчете расстояний между нашим объектом и объектами, тип которых уже определен.

Для того, чтобы вычислить это расстояние, воспользуемся формулой для расчета расстояния в многомерном пространстве (Евклидово расстояние):

В excel это будет выглядеть так:

«Протянем» формулу на все строки, где есть значения параметров. В соседнем столбце слева можно ранжировать значение каждого расстояния среди остальных значений расстояний с помощью функции «=РАНГ(), а в правый просто копируем значение типа. Должно получиться так:

Теперь для того, чтобы определить тип нашего объекта достаточно выбрать k-первых значений из получившегося массива (по возрастанию). В качестве числа k возьмем максимальное целое число, которое меньше корня квадратного из числа заданных значений. Для нас это будет число 3.

Можно заметить, что наибольшее количество (в данном случае все) k-ближайших соседей относятся к «плохо». Следовательно, наш объект тоже относится к «плохо».

Для того, чтобы сделать «куличик» в песочнице, не следует подгонять экскаватор. Есть ситуации, например, когда вы строите дом, где без спецтехники не обойтись. Но в случае с куличиком результат будет похож на ковш и весьма вероятно накроет собой всю песочницу.

Иными словами, некоторые задачи Data mining не требуют ни «космической сложности алгоритмов», ни глубоких познаний в высшей математике, не предполагают также использования «разнообразных framework-ов с пугающими названиями» и доступны любому, кто умеет пользоваться важнейшим из инструментов «уверенного пользователя ПК» — excel.

Советуем почитать