«Адвент-календарь» машинного обучения. День 4: k-средние в Excel

Как реализовать алгоритм обучения, который наконец станет похож на «настоящее» машинное обучение

Делиться

Добро пожаловать в четвертый день Адвент-календаря машинного обучения.

В течение первых трех дней мы изучали дистанционные модели контролируемого обучения:

• регрессор k-NN ,
• классификатор k-NN ,
• и классификатор ближайшего центроида .

Во всех этих моделях идея была одинаковой: мы измеряем расстояния и определяем выходные данные на основе ближайших точек или ближайших центров.

Сегодня мы придерживаемся той же идеи. Но используем расстояния без учителя: метод k-средних .

Теперь один вопрос для тех, кто уже знаком с этим алгоритмом: на какую модель больше похож алгоритм k-means, на классификатор k-NN или на классификатор ближайшего центроида?

И если вы помните, во всех моделях, которые мы видели до сих пор, на самом деле не было фазы «обучения» или настройки гиперпараметров.

• Для k-NN обучение вообще не требуется.

• Для LDA, QDA или GNB обучение сводится лишь к вычислению средних значений и дисперсий. Кроме того, здесь нет реальных гиперпараметров.

Теперь с помощью k-средних мы реализуем алгоритм обучения, который наконец станет похож на «настоящее» машинное обучение.

Начнём с небольшого одномерного примера. Затем перейдём к двухмерному.

Цель метода k-средних

В обучающем наборе данных начальные метки отсутствуют .

Целью метода k-средних является создание осмысленных меток путем группировки точек, расположенных близко друг к другу.

Давайте посмотрим на иллюстрацию ниже. Вы можете ясно увидеть две группы точек. Каждый центроид (красный и зелёный квадраты) находится в центре своего кластера, и каждая точка соответствует ближайшему к нему центроиду.

Это дает очень наглядное представление о том, как метод k-средних обнаруживает структуру, используя только расстояния.

И здесь k означает количество центров, которые мы пытаемся найти.

Теперь ответим на вопрос: к какому алгоритму ближе k-means, к классификатору k-NN или к классификатору ближайшего центроида?

Не позволяйте букве k в аббревиатурах k-NN и k-means вводить вас в заблуждение.
Они не означают одно и то же:

• в k-NN k — это число соседей, а не число классов;
• в алгоритме k-средних k — число центроидов.

Метод K-средних гораздо ближе к классификатору ближайшего центроида .

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

Разница, конечно, состоит в том, что в классификаторе «Ближайший центроид» мы уже знаем центроиды, поскольку они берутся из помеченных классов.

В алгоритме k-средних мы не знаем центроидов. Вся цель алгоритма — найти подходящие центроиды непосредственно из данных.

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

В алгоритме k-средних значение k (количество центроидов) неизвестно. Поэтому оно становится гиперпараметром , который можно настраивать.

k-means только с одной особенностью

Начнём с небольшого одномерного примера, чтобы всё было видно на одной оси. И выберем значения настолько тривиально, что сразу увидим два центроида.

1, 2, 3, 11, 12, 13

Да, 2 и 12.

Но откуда компьютеру знать? Машина будет «учиться», угадывая шаг за шагом.

Вот алгоритм, называемый алгоритмом Ллойда .

Мы реализуем это в Excel с помощью следующего цикла:

1. выбрать начальные центроиды
2. вычислить расстояние от каждой точки до каждого центроида
3. присвоить каждой точке ближайший центроид
4. пересчитать центроиды как среднее значение точек в каждом кластере
5. повторяйте шаги 2–4, пока центроиды не перестанут двигаться

1. Выберите начальные центроиды

Выберите два начальных центра, например:

• с_1 = 2,5
• с_2 = 3

Они должны находиться в пределах диапазона данных (от 1 до 13).

2. Вычислить расстояния

Для каждой точки данных x:

• вычислить расстояние до c_1,
• вычислить расстояние до c_2.

Обычно мы используем абсолютное расстояние в 1D.

Теперь у нас есть два значения расстояния для каждой точки.

3. Назначить кластеры

Для каждой точки:

• сравните два расстояния,
• назначить кластер наименьшего из них (1 или 2).

В Excel это простая логика, основанная на ЕСЛИ или МИН.

4. Вычислить новые центроиды

Для каждого кластера:

• возьмите баллы, присвоенные этому кластеру,
• вычислить их среднее значение,
• это среднее значение становится новым центроидом.

5. Повторять до достижения сходимости.

Теперь в Excel, благодаря формулам, мы можем просто вставить новые значения центроидов в ячейки исходных центроидов.

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

Мы также можем записывать каждый шаг в Excel, чтобы видеть, как центроиды и кластеры меняются с течением времени.

k-средних с двумя признаками

Теперь воспользуемся двумя характеристиками. Процесс тот же самый: мы просто используем евклидово расстояние в двумерном пространстве.

Вы можете либо скопировать и вставить новые центроиды как значения (обновив всего несколько ячеек),

или вы можете отобразить все промежуточные шаги , чтобы увидеть полную эволюцию алгоритма.

Визуализация движущихся центроидов в Excel

Чтобы сделать процесс более наглядным, полезно создать графики, показывающие движение центроидов.

К сожалению, Excel или Google Таблицы не идеальны для такого рода визуализации, и таблицы данных быстро становятся сложными для организации.

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

Как вы можете видеть на рисунке, рабочий лист стал совершенно неорганизованным, особенно по сравнению с предыдущей таблицей, которая была очень простой.

Выбор оптимального k: метод локтя

Итак, теперь можно попробовать k = 2 и k = 3 в нашем случае и вычислить инерцию для каждого из них. Затем мы просто сравниваем значения.

Мы даже можем начать с k=1.

Для каждого значения k:

• мы запускаем k-Means до сходимости,
• вычислить инерцию , которая представляет собой сумму квадратов расстояний между каждой точкой и назначенным ей центроидом.

В Excel:

• Для каждой точки возьмите расстояние до ее центроида и возведите его в квадрат.
• Сложите все эти квадраты расстояний.
• Это дает инерцию для этого k.

Например:

• при k = 1 центроид — это просто общее среднее значение x1 и x2,
• для k = 2 и k = 3 мы берем сходящиеся центроиды из листов, на которых вы запустили алгоритм.

Затем мы можем построить график инерции как функции k, например, для (k = 1, 2, 3).

Для этого набора данных

• от 1 до 2 инерция сильно падает,
• от 2 до 3 улучшение гораздо меньше.

«Локоть» — это значение k, после которого уменьшение инерции становится незначительным. В данном примере это означает, что k = 2 достаточно.

Заключение

Алгоритм K-средних очень интуитивно понятен, если вы увидите его пошагово в Excel.

Мы начинаем с простых центроидов, вычисляем расстояния, присваиваем точки, обновляем центроиды и повторяем. Теперь мы видим, как «машины обучаются», верно?

Что ж, это только начало: мы увидим, что разные модели «учатся» по-разному.

А вот и переход к завтрашней статье: неконтролируемая версия классификатора ближайшего центроида — это действительно k-средних .

Так что же представляет собой неконтролируемая версия LDA или QDA ? Мы ответим на этот вопрос в следующей статье.

Источник: towardsdatascience.com