Кластеризация — это задача группировки данных сходного характера. Он включает в себя выявление особенностей, в которых данные в группе или кластере имеют что-то общее. Кластеризация приводит к множеству групп данных, где каждый член группы похож внутри группы, но отличается от других членов группы. Алгоритмы обработки кластеризации пытаются найти это сходство различными методами.

Вот некоторые из алгоритмов группировки:
1. K-средних, также называемых методами разделения
2. Алгоритм иерархической кластеризации
3. Алгоритм DBScan

Каждый из приведенных выше алгоритмов определяет сходство одного члена с другим, используя разные свойства. Сегодня я расскажу о k-средних.

К-значит и семья

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

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

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

Шаги назначения и оптимизации продолжаются до тех пор, пока выбранный центроид не окажется истинным центроидом после шага назначения. Это известно как конвергенция. На этом мы останавливаемся, и последние кластеры — это группы, которые, по мнению алгоритма, существуют в наборе данных. (Обратите внимание, что обычно действие состоит в том, чтобы ограничить его определенным количеством повторений, чтобы программа не работала вечно, если она не может перейти в состояние, в котором выбранный центроид равен истинному центроиду).

Итак, почему я называю это семейством, ведь существуют разные способы выбора «центроида» на этапе оптимизации.

  • Это может быть среднее (или среднее) всех расстояний от членов группы. (K-значит)
  • Это может быть медиана членов. (K-медианы)
  • (к-медоид)

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

  1. Убедитесь, что данные очищены (отсутствующие значения удалены, нужные столбцы выбраны)
  2. Масштабировать данные
  3. Проверьте, могут ли данные быть эффективно кластеризованы
  4. K-means требует заранее знать значение «k».

Масштабирование данных

Если некоторые функции данных имеют более высокий диапазон значений, чем другие функции (например, если столбец функций A имеет значения в диапазоне от 1 до 1000, а столбец функций B имеет значения от 1 до 0, результат будет сильно зависеть от A) .

Доступно несколько механизмов масштабирования. Те, которые я использовал, это

Мин-макс масштабатор

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

Стандартный скейлер

Мы знаем среднее значение и стандартное отклонение данных. Масштабированные данные будут иметь среднее значение 0 и будут выражены как кратное стандартному отклонению данных около 0 (может быть отрицательным или положительным).

Как узнать, можно ли эффективно кластеризовать набор данных?

Прежде чем мы приступим к алгоритму кластеризации, нам нужно проверить, есть ли в имеющихся у нас данных какие-либо возможные кластеры, т. е. внутри членов должны быть некоторые функции, которые похожи для одних, но отличаются для других. Это позволяет создавать различные группы. Итак, необходимо измерить кластерную тенденцию набора данных.

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

Статистический алгоритм Хопкинса

  1. Тест Хопкинса выполняется на выборочном наборе входных данных и повторяется несколько раз, чтобы проверить, является ли набор данных случайным.
  2. Размер набора выборки должен составлять 1/10 от общего размера набора (?), давайте назовем набор выборки как m (что равно n/10, где n — общий размер)
  3. Выберите случайный набор из m выборок из входных функций (значения для этого будут взяты из набора данных, мы назовем его U)
  4. Выберите набор равномерно распределенных случайным образом значений в диапазоне от максимального до минимального значения этой функции. (Значения для этого не обязательно должны быть в наборе данных, мы будем называть его W)
  5. Вычислите расстояние от каждой выборки в U (которая, скорее всего, не является частью набора данных, поскольку мы выбрали значения случайным образом) до ближайшей выборки в исходном наборе данных.
  6. Вычислите расстояние от каждой выборки в W (которая является частью исходного набора данных, поскольку мы выбрали элементы случайным образом) до ее ближайшего соседа.
  7. Суммируйте результаты шагов 5 и 6 — мы назовем это Sum_U и Sum_W.
  8. Найдите Sum_U/(Sum_W+Sum_U) — это статистика Хопкина (H).
  9. Если H близко к 0,5, это означает, что Sum_U и Sum_W похожи, поэтому данные, вероятно, распределены более равномерно (потому что мы знаем, что U было из равномерного распределения).
  10. Если H близко к 1, это означает, что Sum_U намного выше, чем Sum_W, это указывает на то, что однородные случайные данные из U намного дальше, чем выборки по сравнению со случайно выбранными элементами, которые относительно намного ближе к своим соседям, что указывает на то, что члены данных имеют чувство близости.
  11. Если H близко к 0, это означает, что Sum_U намного меньше, чем Sum_W, что необычно, поскольку это означало бы, что случайно выбранные значения были намного ближе к существующим выборкам, чем случайно выбранные фактические члены.

Если набор данных показывает статистику Хопкинса, близкую к 1, это указывает на то, что данные не являются равномерно случайными, но есть некоторая близость между его элементами. Обычно данные выше 0,75 считаются хорошими. Выполнение теста несколько раз поможет получить правильную статистику Хопкинса.

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

Как узнать К?

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

Если мы выберем слишком мало кластеров, мы можем в конечном итоге сгруппировать 2 непохожие группы в одну группу… ИЛИ … если мы выберем слишком много кластеров, мы можем в конечном итоге сгруппировать похожих участников в 2 разные группы. Таким образом, поиск правильного значения k важен для анализа.

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

Для измерения компактности кластера мы можем использовать 2 метода

  1. Метод кривой локтя
  2. Метод оценки силуэта

Метод кривой локтя

  1. После завершения кластеризации измерьте расстояние от каждого члена до его собственного центра кластера.
  2. Выполните шаг 1 для всех кластеров.
  3. Сложите результаты всех участников, это также называется инерцией в KMeans sklearn.
  4. Вычислите показатель инерции для каждого значения k и нанесите его на график с осью x, представляющей значение k, и осью y, представляющим показатель инерции для каждого k.
  5. Мы будем искать оптимальное значение k, чтобы найти компромисс между количеством кластеров и более низким значением инерции.
  6. Найдите это k, где, если мы продолжим увеличивать k на 1, снижение показателя инерции уже будет недостаточно значительным.

Метод оценки силуэта

  1. Найдите среднее сходство. Это среднее расстояние от элемента до всех других элементов в том же кластере. Назовем это - а
  2. Найдите среднее несоответствие. Это среднее расстояние от члена до всех членов каждого из других кластеров. Вычислите его для каждого другого кластера, а затем выберите минимальное значение, это соседний кластер. Назовем это - б
  3. Оценка силуэта для члена вычисляется как — (b-a)/max(b,a)
  4. Диапазон значений от -1 → +1 — с отрицательными значениями, указывающими, что элемент больше похож на соседний кластер, чем на свой собственный, потому что b‹a, а положительный показатель указывает на обратное.
  5. Возьмите среднее значение оценки силуэта всех точек данных.
  6. Получаем средний характер результата, сильный положительный балл говорит о том, что кластеризация хорошая.

Кластеризация с использованием оптимального значения k

Из метода кривой локтя мы обнаружили, что k = 3 или 4 предлагает наилучшее значение k, а из метода силуэта мы видим, что k = 2,3,4,5 также хороши.

Объединив оба результата, мы можем выбрать k=3.

Ссылки

  1. Код Python для расчета статистики Хопкинса для набора данных: https://matevzkunaver.wordpress.com/2017/06/20/hopkins-test-for-cluster-tendency/
  2. Различные методы масштабирования данных: https://machinelearningmastery.com/standardscaler-and-minmaxscaler-transforms-in-python/