Раскрашивание с помощью кластеризации K-средних
Кластеризация K-средних - это алгоритм классификации, который пытается сгруппировать все точки данных в K групп. Это полезно для:
- обнаружение выбросов,
- сегментация изображения,
- присвоение меток немаркированным данным,
- распознавание шаблонов в языках,
- многие, многие другие…
Процесс
- Выберите K случайных точек в качестве центроидов (не обязательно точки в ваших данных). Группы будут состоять из всех точек, назначенных одному центроиду.
- Назначьте каждую точку данных центроиду, к которому она ближе всего.
Это делается путем нахождения евклидова расстояния между точкой и центроидом. Следовательно, вам нужно убедиться, что все ваши переменные находятся в одном масштабе, чтобы их можно было рассматривать одинаково.
3. Обновите расположение всех центроидов, усреднив все точки, входящие в его группу.
4. Повторяйте шаги 2 и 3, пока центроиды не сойдутся в определенном месте. Когда центроиды перестают двигаться, это означает, что алгоритм минимизировал сумму всех квадратов расстояний в кластере для всех кластеров.
Выбор подходящего количества кластеров
Правильное количество кластеров не является универсальным для всех наборов данных. Выбор правильного количества кластеров важен, чтобы избежать недостаточной и чрезмерной подгонки.
Для этого мы должны сначала запустить алгоритм с разным количеством кластеров и построить график количества кластеров против соответствующего SSE (суммы квадратов ошибок). График для указанного выше набора данных выглядит следующим образом:
Теперь мы выбираем количество кластеров, которое находится на «изгибе» этого графика. Любые значения перед изгибом будут иметь слишком большое значение SSE, чтобы быть точной моделью, и любые значения после изгиба начнут переоценивать наши данные обучения и также будут плохой моделью.
Мини-пакетная кластеризация K-средних
Кластеризация K-средних требует доступа к каждой точке в наборе данных во время каждой итерации. Это значительно замедляет алгоритм, когда размер набора данных становится очень большим. Чтобы обойти это, снова можно использовать алгоритм k-средних мини-пакетов. Он будет выполнять все те же шаги, что и обычный алгоритм, но вместо использования полного набора данных он будет использовать случайно выбранные подмножества того же размера. Каждая последующая партия будет меньше весить и меньше влиять на центроиды. Реализация Mini Batch в Scikit-learn имеет допуск, который завершает алгоритм раньше, если центроиды существенно не изменяются после пары пакетов. Однако, поскольку пакеты выбираются случайным образом, модели, созданные в результате многократного запуска алгоритма, могут незначительно отличаться, а в некоторых случаях могут случайно останавливаться раньше после рассмотрения только средних случаев.
Трюк с ядром
Алгоритм кластеризации K-средних предполагает, что все границы кластера линейны, поэтому при данных наблюдениях, требующих более сложных границ, будут некоторые ошибки классификации. Один из способов обойти это - использовать уловку с ядром. Суть уловки с ядром заключается в том, что даже если набор данных в настоящее время не делится линейно, он может быть в более высоком измерении.
Раскраска Покемон
Мы можем использовать кластеризацию K-средних для группировки пикселей с похожими цветами в изображениях. После обучения нашей модели с одним изображением, в результирующих центрах все пиксели схожего цвета будут сгруппированы вместе, и они будут перекрашены в средний цвет для всей группы. Давайте попробуем это с моим любимым закуском первого поколения, Бульбазавром!
Если мы попытаемся просто сгруппировать изображение как есть, оно не сможет нарисовать линейные границы вокруг цветов, поэтому мы можем использовать трюк с ядром и поднять каждый пиксель на размер, сопоставляя их со значениями RGB. Ниже приводится диаграмма рассеяния каждого пикселя изображения Бульбазавра, построенная на его значениях RGB.
Теперь мы можем обучить нашу модель кластеризации K-средних группировать эти цвета. Я решил использовать 16 групп, чтобы имитировать старую 16-битную раскраску. Окончательная модель будет набором из 16 центроидов, который минимизирует SSE цветов.
Теперь, используя эти центры, мы можем перекрасить любого другого покемона (или любое изображение, но давайте придерживаться темы), используя те же 16 цветов. Он делает это, просматривая все пиксели нового изображения, а затем перекрашивая пиксели в зависимости от цвета ближайшего к нему центра. Мы можем использовать это для улучшения второго лучшего стартера поколения 1.
