Пошаговое руководство по обеспечению эффективности, точности и действенности вашего алгоритма кластеризации.

В мире искусственного интеллекта один алгоритм следует за другим. Каждый алгоритм или модель предназначены для решения различных проблем, которые могут быть автоматизированы, решены или улучшены за счет использования этих моделей. Любой, кто не видел подъем машинного обучения, не знает, куда движется мир. Продвижение именно в этой области не только неоспоримо, но неизбежно и необходимо.

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

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

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

Зачем нужны индексы достоверности/оценки кластера?

Причины, по которым мы должны проверить, действительны ли алгоритмы кластеризации или нет (насколько хороши кластеры?), можно свести к следующим трем:

  • Сравнить два набора кластеров.
  • Сравнить два кластера и определить, какой из них более компактен и связан.
  • Чтобы увидеть, есть ли в данных какая-либо случайная структура из-за шума.

Классификация показателей достоверности кластера

Показатели валидности кластера часто делятся на три категории:

1) Внутренняя проверка кластера: результат кластеризации оценивается исключительно на основе кластеризованных данных (внутренней информации) без ссылки на внешние данные.

2) Внешняя проверка кластера: результаты кластеризации оцениваются с использованием внешне известного результата, такого как метки классов, предоставленные пользователем.

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

Нам также необходимо знать о межкластерном расстоянии d(a, b) между двумя кластерами a, b и внутрикластерном индексе D(a) кластера a, в дополнение к термину индекс достоверности кластера.

Есть несколько категорий, в которые можно отнести межкластерное расстояние d(a, b) между двумя кластерами a и b:

  • Single Linkage Distance: Это ближайшее расстояние между двумя объектами, принадлежащими a и b.
  • Полное расстояние связи: это расстояние между двумя наиболее удаленными объектами, принадлежащими a и b.
  • Среднее расстояние связи: это среднее расстояние между всеми объектами, принадлежащими a и b.
  • Расстояние центроидной связи: это расстояние между центроидами двух кластеров a и b.

Внутрикластерное расстояние D(a) кластера a может быть:

  • Полное расстояние связи диаметра: это расстояние между двумя самыми дальними объектами, принадлежащими кластеру a.
  • Среднее расстояние связи диаметра: это среднее расстояние между всеми объектами, принадлежащими кластеру a.
  • Расстояние связи диаметра центроида: это удвоенное среднее расстояние между всеми объектами и центроидом кластера a.

Метрики для оценки алгоритмов кластеризации

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

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

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

Метрики или методы для оценки алгоритмов кластеризации:

Индекс Дэвиса-Булдина

Следующая формула рассчитывает индекс БД:

где n обозначает количество кластеров, а σi обозначает среднее расстояние всех точек внутри кластера i от центроида кластера ci.

Индекс БД воплощает идею о том, что кластеры, которые:

1) на большом расстоянии друг от друга

2) Плотные сами по себе, вероятно, будут «отличными» кластерами.

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

Подводя итог, этот индекс/оценка/метрика измеряет сходство кластеров. Это означает, что чем ниже оценка, тем лучше разделение между вашими кластерами.

Его можно рассчитать/реализовать с помощью scikit-learn следующим образом:

Индекс Данна

Следующая формула соответствует индексу Данна:

где i, j и k — это индексы, обозначающие кластеры, а d измеряет расстояние между кластерами. , а d' измеряет разницу внутри кластера.

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

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

Выбор между двумя подходами, будь то индекс DB или индекс Данна, полностью зависит от вас.

Его можно реализовать/рассчитать с помощью библиотеки jqmcvi, используя следующий код Python:

Коэффициент силуэта

Коэффициент Силуэта рассчитывается следующим образом:

где a(i) — среднее расстояние между точкой i и всеми другими точками в ее кластере, а b(i) — кратчайшее среднее расстояние между точкой i и всеми остальными точками в любом другом кластере. Чтобы уточнить, b(i) вычисляется путем измерения среднего расстояния i от каждой точки в кластере A, а затем измерения среднего расстояния i от каждой точки в кластере B, затем берется меньшее из двух значений.

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

Коэффициент силуэта показывает, насколько хорошо назначена каждая отдельная точка. Если S(i) близко к 0, точка перегиба между двумя кластерами присутствует. Нам определенно было бы лучше отнести его к другому кластеру, если бы он был ближе к -1. Если S(i) близко к 1, точка была правильно назначена и может считаться частью «подходящего» кластера.

Подводя итог, диапазон значений индекса силуэта S(i) будет лежать между [-1, 1]:

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

Коэффициент силуэта — это инновационное и простое измерение расстояния. Его недостатком является то, что вычисления для всех n точек могут быть довольно дорогими. Это связано с тем, что для каждого i мы должны вычислить расстояние i от каждой другой точки n — 1, что приводит к сложности O (n2).

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

Способ реализации/расчета коэффициента силуэта с использованием scikit-learn в python:

Индекс Калински-Харабаз

Когда наземные метки истинности неизвестны, для оценки модели можно использовать индекс Калински-Харабаша (CH) (разработанный Калински и Харабашем). Индекс CH (также известный как критерий отношения дисперсии) — это метрика, которая сравнивает, насколько объект похож на свой собственный кластер (сплоченность) на другие кластеры (разделение). Расстояния между точками данных в кластере и центроидом кластера используются для оценки связности. Напротив, расстояние между центроидами кластера и глобальным центроидом используется для оценки разделения. (a. Разделение)/(b. Сплоченность) — формула для индекса CH, где a и b — веса.

Индекс CH для K кластеров в наборе данных D = [ d1 , d2 , d3 , … dN ] определяется как:

где nk и ck — это нет. точек и центроид k-го кластера соответственно, c — глобальный центроид, N — общее количество. точек данных.

Хотя для индекса CH не существует «хорошего» порогового значения, более высокое значение указывает на то, что кластеры плотные и хорошо разделены. На линейном графике индексов CH мы должны выбрать решение, которое дает пик или, по крайней мере, крутой изгиб. Однако, если линия гладкая (горизонтальная, восходящая или нисходящая), нет причин выбирать один вариант вместо другого.

Реализация индекса CH в python показана ниже:

V-мера

Одним из наиболее существенных недостатков любого метода кластеризации является сложность оценки его эффективности. Поэтому еще одна метрика, созданная для решения этой проблемы, — V-Measure.

Значение V-Measure рассчитывается по следующей формуле:

где

h - однородность

и

c - полнота

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

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

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

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

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

Предположим, что имеется N выборок данных, C различных меток классов, K кластеров и количество точек данных, принадлежащих классу c и кластеру k. Тогда однородность h определяется следующим:

Реализация V-Measure в python:

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

Ссылка: https://www.geeksforgeeks.org

https://odsc.medium.com/assessment-metrics-for-clustering-algorithms-4a902e00d92d

https://stephenallwright.com/good-clustering-metrics

https://pafnuty.wordpress.com/2013/02/04/interpretation-of-silhouette-plots-clustering/