Сила предсказания - простой, но относительно неизвестный способ оценки кластеризации
Узнайте, как работает критерий и как реализовать его на Python с нуля!
Существует множество материалов (книги, сообщения в блогах, учебные пособия и т. Д.) О кластеризации в целом и различных способах нахождения оптимального количества кластеров в алгоритмах, таких как кластеризация k-средних: статистика разрыва, оценка силуэта, печально известный локтевой (осыпной) сюжет и многое другое.
Благодаря COVID-19 и недавно найденным кускам дополнительного свободного времени я, наконец, смог вернуться к своей очереди книг и дочитать превосходную книгу Андрея Буркова Сотостраничную книгу по машинному обучению. Книга дает очень хороший обзор различных аспектов машинного обучения и побуждает читателей глубже погрузиться в интересующие их темы. Читая главу о неконтролируемом обучении и алгоритмах кластеризации, я столкнулся с новым (для меня) способом оценки производительности алгоритмов кластеризации - силой предсказания.
После быстрого поиска я не нашел похожих статей и считаю, что метод довольно интересный и заслуживает отдельной статьи. Итак, приступим!
Теоретическое введение
Многие из популярных методов, используемых для определения оптимального количества кластеров для таких алгоритмов, как k-среднее, основаны на сумме квадратов внутри кластера (WSS). Эта метрика основана на расстоянии между наблюдениями и центроидами кластера. В целом, чем ниже WSS, тем ближе результаты наблюдений к центроидам, что указывает на лучшее соответствие. Однако нам нужно найти баланс между WSS и количеством кластеров, поскольку неограниченное увеличение количества кластеров (вплоть до количества наблюдений) всегда должно приводить к лучшему соответствию.
Подход силы предсказания, предложенный в [1], рассматривает проблему определения оптимального количества кластеров с точки зрения машинного обучения.
Мы разбиваем алгоритм на следующие шаги:
- Разделите набор данных на обучающий (X_tr) и тестовый (X_te) наборы.
- Запустите алгоритм кластеризации для обоих наборов, используя определенное значение k (количество кластеров).
- Создайте матрицу совместного членства D [C (X_tr, k), X_te] размером
n_testxn_test, гдеn_test- количество наблюдений в тестовом наборе, а C (X_tr, k) - это алгоритм кластеризации (в нашем случае k-means), подходящий для обучающей выборки. - Установите для ii’-го элемента матрицы совместного членства значение 1, если элементы i и i ’тестового набора попадают в один и тот же кластер, в противном случае установите значение 0.
- Чтобы измерить, насколько хорошо центроиды обучающего набора предсказывают совместное членство в тестовом наборе. Для каждой пары тестовых наблюдений, которые назначены одному и тому же тест-кластеру (значение 1 в матрице совместного членства), мы определяем, назначены ли они также одному и тому же кластеру, на основе центроидов обучающего набора.
Следующее изображение из [1] иллюстрирует эту идею:
6. Сила предсказания кластеризации C (., K) определяется как:
где n_kj - количество наблюдений в j -м кластере.
7. Для каждого из тестовых кластеров мы вычисляем долю пар наблюдений в этом кластере, которые также назначены одному и тому же кластеру, используя центроиды обучающего набора. Сила прогноза - это минимум этого количества по k тестовым кластерам.
Выполним шаги 2–7 описанного выше алгоритма для всех рассмотренных размеров кластера. Затем мы выбираем максимальный размер кластера, для которого сила предсказания превышает определенный порог. Эксперименты, проведенные авторами, предполагают 0,8–0,9 как хорошее значение для порога.
Это может показаться непростым делом, поэтому я рекомендую пройтись по алгоритму несколько раз, чтобы понять суть. Также будет полезно взглянуть на код в более поздней части.
Чтобы упростить процесс, я попытаюсь дать интуитивное объяснение подхода силы предсказания. Предположим, что выбранное количество кластеров равно истинному количеству кластеров в наборе данных. Тогда обучающие кластеры будут похожи на тестовые и будут хорошо их предсказывать. В результате сила предсказания будет высокой.
И наоборот, когда выбранное количество кластеров больше оптимального, дополнительные обучающие и тестовые кластеры, скорее всего, будут разными, что приведет к более низким значениям силы предсказания.
Реализация на Python
Пришло время реализовать алгоритм силы предсказания на Python. Мы будем использовать критерий, чтобы выбрать оптимальное количество кластеров в кластеризации k-средних на игрушечном наборе данных. Кроме того, мы также покажем для сравнения классический подход к графику локтя. Сначала импортируем все необходимые библиотеки:
Затем мы используем make_blobs для создания двухмерного набора данных игрушек с 3 четко разделенными кластерами. Фиксируем случайное состояние для воспроизводимости.
На следующем изображении представлен сгенерированный набор данных.
Сгенерировав данные, мы применяем кластеризацию k-средних. Сначала мы используем подход диаграммы локтя, чтобы определить оптимальное количество кластеров. Мы устанавливаем 9 как максимальное количество кластеров.
В scikit-learn реализации кластеризации k-средних атрибут inertia_ хранит общую сумму квадратов внутри кластера (WSS). Наносим результаты на график:
Мы четко видим точку «локтя» - она соответствует трем кластерам, что соответствует нашим искусственно сгенерированным данным.
Пришло время реализовать алгоритм силы предсказания. Моя реализация основана на реализации, представленной в [3], с некоторыми изменениями, чтобы сделать код более простым и понятным. Начнем с разделения данных на обучающие и тестовые наборы. Для этого мы используем функцию train_test_split из scikit-learn. Мы применяем расслоение 80–20 слоев.
Прежде чем заняться основной функцией, нам нужно определить одну вспомогательную функцию. Он используется для определения ближайшего центроида к данному наблюдению (с использованием евклидова расстояния).
Теперь мы определяем основную функцию. В первой половине мы создаем и заполняем матрицу совместного членства. Мы используем вложенный цикл и набор условий для определения правильного значения для каждого элемента матрицы. Во второй половине мы вычисляем силу предсказания для каждого из кластеров и выбираем минимальное значение в качестве конечного результата.
Подготовив функции, мы подбираем кластеризацию k-средних для каждого размера кластера и вычисляем силу прогноза. Имейте в виду, что на каждой итерации нам фактически нужно подогнать два алгоритма k-средних - для обучающего и тестового наборов отдельно.
Ниже мы можем увидеть результаты на графике. Следуя логике алгоритма, мы должны выбрать максимальный размер кластера, для которого значение силы предсказания выше заданного порога (0,8 в данном случае). Мы видим, что рекомендуемый размер кластера - 3.
Выводы
В этой статье я представил относительно неизвестный критерий оценки для алгоритмов кластеризации - силу предсказания - и показал, как реализовать его как настраиваемую функцию в Python. Вы можете попробовать это в следующий раз, когда будете работать над проблемой кластеризации!
Немного другую, но эквивалентную реализацию алгоритма (на R) см. В [2]. Этому подходу может быть немного проще следовать, поскольку автор уменьшил количество вложенных циклов и условий для проверки.
Еще одна вещь, которую мы могли бы применить к нашему игрушечному примеру - особенно для недетерминированных алгоритмов кластеризации - это доверительные интервалы. Они основаны на многократном вычислении силы предсказания и вычислении среднего и стандартного отклонения полученных результатов. Помните, что для этого мы должны удалить фиксированные случайные состояния из класса кластеризации k-средних.
Вы можете найти код, использованный для этой статьи, на моем GitHub. Как всегда, приветствуются любые конструктивные отзывы. Вы можете связаться со мной в Твиттере или в комментариях.
Если вам эта статья показалась интересной, вам также могут понравиться:
использованная литература
[1] Тибширани Р. и Вальтер Г. (2005). Проверка кластера по силе прогноза. Журнал вычислительной и графической статистики, 14 (3), 511–528. - https://www.stat.washington.edu/wxs/Stat592-w2011/Literature/tibshirani-walther-prediction-strength-2005.pdf
[2] https://github.com/echen/prediction-strength
[3] https://github.com/aburkov/theMLbook/blob/master/prediction_strength.py
