Идентификация неизвестного с помощью метрик кластеризации

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

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

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

Понимание кластеризации: краткий пример

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

Сначала несколько общих обозначений и терминов:

• $D$: набор данных
• $A$, $B$: два кластера, которые являются подмножествами нашего набора данных.
• $C$: основная кластеризация $D$, с которой мы будем сравнивать другой кластер.
  • Кластеризация $C$ имеет $K$ кластеров, $C = {C_1, …, C_k}$
• $C'$: вторая кластеризация $D$
  • Кластеризация $C'$ имеет $K'$ кластеров, $C' = {C^\prime_1, …, C^\prime_{k^\prime}}$

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

Чтобы отличить общую кластеризацию $C$ от наших примерных кластеризаций, мы будем использовать строчную букву $c$ для описания наших примерных кластеризаций:

• $c$, с кластерами на основе формы: $c = {c_1, c_2}$, где $c_1$ представляет брюки, а $c_2$ представляет рубашки.
• $c'$ с кластерами по цвету: $c' = {c'_1, c'_2}$, где $c'_1$ представляет красную одежду, а $c'_2$ представляет черную одежду.
• $c''$ с кластерами по форме и цвету: $c'' = {{c^{\prime \prime}}_1, {c^{\prime \prime}}_2, {c^{\prime \prime}}_3, {c^{\prime \prime}}_4}$, где ${c^{\prime \prime}}_1$ представляет красные брюки, ${c^{\prime \prime}}_2 $ представляет черные брюки, ${c^{\prime \prime}}_3$ представляет красные рубашки, а ${c^{\prime \prime}}_4$ представляет черные рубашки.

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

Как видно из нашего примера, метод кластеризации делит все выборки в наборе данных на непустые непересекающиеся подмножества. В кластере $c$ нет изображения, принадлежащего одновременно подмножеству брюк и подмножеству рубашек: $c_1 \cap c_2 = \emptyset$. Эту концепцию можно расширить; никакие два подмножества любого кластера не имеют одинаковых выборок.

Обзор метрик сравнения кластеризации

Большинство критериев сравнения кластеризаций можно описать с помощью матрицы путаницы пары $C, C'$. Матрица путаницы будет представлять собой матрицу $K \times K'$, $kk'$-й элемент которой (элемент в $k$-й строке и $k'$-м столбце) представляет собой количество выборок на пересечении кластеров $ C_k$ из $C$ и $C'_{k'}$ из $C'$:

\[n_{kk'} = |C_k \cap C'_{k'}|\]

Мы разберем это, используя наш упрощенный пример черных и красных брюк и рубашек, предположив, что набор данных $D$ содержит 100 красных брюк, 200 черных брюк, 200 красных рубашек и 300 черных рубашек. Давайте рассмотрим матрицу путаницы $c$ и $c''$:

Так как $K = 2$ и $K'' = 4$, это матрица $2 \times 4$. Выберем $k = 2$ и $k'' = 3$. Мы видим, что элемент $n_{kk'} = n_{23} = 200$. Это означает, что пересечение $c_2$ (рубашки) и ${c^{\prime\prime}}_3$ (красные рубашки) равно 200, что верно, поскольку $c_2 \cap {c^{\prime\prime} }_3$ будет просто набором красных рубашек.

Показатели кластеризации можно разделить на три группы в зависимости от лежащего в основе метода сравнения кластеров:

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

Подсчет пар

Подсчет пар требует изучения всех пар выборок, а затем подсчета пар, в которых кластеризация согласуется и не согласуется. Каждая пара выборок может принадлежать одному из четырех наборов, где количество элементов набора ($N_{ij}$) получается из матрицы путаницы:

• $S_{11}$ с элементами $N_{11}$: элементы пары находятся в одном кластере как в $C$, так и в $C'$
  • Пара из двух красных рубашек окажется ниже $S_{11}$ при сравнении $c$ и $c''$.
• $S_{00}$ с элементами $N_{00}$: элементы пары находятся в разных кластерах как в $C$, так и в $C'$
  • Пара красной рубашки и черных брюк будет стоить менее $S_{00}$ при сравнении $c$ и $c''$.
• $S_{10}$ с элементами $N_{10}$: элементы пары находятся в одном кластере в $C$ и в разных кластерах в $C'$
  • Пара красной и черной рубашек будет меньше $S_{10}$ при сравнении $c$ и $c''$.
• $S_{01}$ с элементами $N_{01}$: элементы пары находятся в разных кластерах в $C$ и в одном кластере в $C'$
  • $S_{01}$ не имеет элементов ($N_{01} = 0$) при сравнении $c$ и $c''$

Индекс Рэнда определяется как $(N_{00} + N_{11})/(n(n-1)/2)$, где $n$ представляет количество выборок; его также можно прочитать как (количество одинаково обработанных пар)/(общее количество пар). Хотя теоретически его значение находится в диапазоне от 0 до 1, на практике его диапазон часто намного уже. Более высокое значение означает большее сходство между кластерами. (Индекс Рэнда, равный 1, будет представлять собой идеальное совпадение, когда две кластеризации имеют идентичные кластеры.)

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

Теория информации

Эти показатели основаны на общих понятиях теории информации. Мы обсудим два из них: энтропию и взаимную информацию (МИ).

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

MI описывает, сколько информации одна кластеризация дает о другой. MI может показать, насколько знание кластера выборки в $C$ уменьшает неопределенность относительно кластера выборки в $C'$.

Нормализованная взаимная информация — это МИ, нормализованная по среднему геометрическому или арифметическому энтропий кластеризаций. Стандартный MI не связан постоянным значением, поэтому нормализованная взаимная информация обеспечивает более интерпретируемую метрику кластеризации.

Еще одна популярная метрика в этой категории — вариация информации (VI), которая зависит как от энтропии, так и от MI кластеризации. Пусть $H(C)$ — энтропия кластеризации, а $I(C, C')$ — МИ между двумя кластеризациями. VI между двумя кластеризациями можно определить как $VI(C,C') = H(C)+H(C')-2I(C,C')$. VI, равный 0, представляет собой идеальное совпадение между двумя кластеризациями.

Установить перекрытие

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

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

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

Применение метрик кластеризации с F-мерой

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

Определение F-меры

Давайте предположим, что $C$ — это наше истинное или оптимальное решение. Для любого $k$-го кластера в $C$, где $k \in [1, K]$, мы вычислим индивидуальную F-меру с каждым кластером в результате кластеризации $C'$. Эта индивидуальная F-мера указывает, насколько хорошо кластер $C^\prime_{k'}$ описывает кластер $C_k$, и может быть определена с помощью точности и полноты (две метрики оценки модели) для этих кластеров. Определим $I_{kk'}$ как пересечение элементов $k$-го кластера $C$ и $k'$-го кластера $C'$, а $\lvert C_k \rvert$ - как число элементов в $k$-м кластере.

• Точность $p = \frac{I_{kk'}}{\lvert C'_{k'} \rvert}$

• Напомним, что $r = \frac{I_{kk'}}{\lvert C_{k} \rvert}$

Затем индивидуальная F-мера $k$-го и $k'$-го кластеров может быть рассчитана как среднее гармоническое точности и полноты для этих кластеров:

\[F_{kk'} = \frac{2rp}{r+p} = \frac{2I_{kk'}}{|C_k|+|C'_{k'}|}\]

Теперь, чтобы сравнить $C$ и $C'$, давайте посмотрим на общую F-меру. Во-первых, мы создадим матрицу, похожую на таблицу непредвиденных обстоятельств, значениями которой являются отдельные F-меры кластеров. Предположим, что мы отобразили кластеры $C$ в виде строк таблицы и кластеры $C'$ в виде столбцов со значениями таблицы, соответствующими отдельным F-мерам. Определите пару кластеров с максимальной индивидуальной F-мерой и удалите строку и столбец, соответствующие этим кластерам. Повторяйте это, пока кластеры не будут исчерпаны. Наконец, мы можем определить общую F-меру:

\[F(C, C') = \frac{1}{n} \sum_{i=1}^K n_imax(F(C_i, C'_j)) \forall j \in {1, K'}\ ]

Как видите, общая F-мера представляет собой взвешенную сумму наших максимальных индивидуальных F-мер для кластеров.

Настройка данных и ожидаемые результаты

Любой блокнот Python, подходящий для машинного обучения, например блокнот Jupyter, будет работать в качестве нашей среды. Прежде чем мы начнем, вы можете изучить README моего репозитория GitHub, расширенный файл примера readme_help_example.ipynb и файл requirements.txt (необходимые библиотеки).

Мы будем использовать образцы данных из репозитория GitHub, состоящего из новостных статей. Данные упорядочиваются с информацией, включая category , headline , date и short_description :

Мы можем использовать pandas для чтения, анализа и обработки данных. Мы отсортируем данные по дате и выберем небольшую выборку (10 000 заголовков новостей) для нашей демонстрации, поскольку полный набор данных велик:

 import pandas as pd df = pd.read_json("./sample_data/example_news_data.json", lines=True) df.sort_values(by='date', inplace=True) df = df[:10000] len(df['category'].unique())

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

Оптимизация функций кластеризации

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

• Обновление текста, чтобы иметь единый регистр.
• Удаление числовых или специальных символов.
• Выполнение лемматизации.
• Удаление стоп-слов.

 import re import nltk from nltk.corpus import stopwords from nltk.stem import WordNetLemmatizer wordnet_lemmatizer = WordNetLemmatizer() nltk.download('stopwords') stop_words = stopwords.words('english') nltk.download('wordnet') nltk.download('omw-1.4') def preprocess(text: str) -> str: text = text.lower() text = re.sub('[^az]',' ',text) text = re.sub('\s+', ' ', text) text = text.split(" ") words = [wordnet_lemmatizer.lemmatize(word, 'v') for word in text if word not in stop_words] return " ".join(words) df['processed_input'] = df['headline'].apply(preprocess)

Результирующие предварительно processed_input заголовки отображаются как processing_input , что вы можете увидеть, снова запустив df.head(4) :

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

 from sklearn.cluster import AgglomerativeClustering, KMeans from sklearn.feature_extraction.text import TfidfVectorizer vectorizer = TfidfVectorizer(max_features=300, tokenizer=lambda x: x.split(' ')) tfidf_mat = vectorizer.fit_transform(df['processed_input']) X = tfidf_mat.todense() X[X==0]=0.00001

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

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

Считая заданные категории новостей оптимальным решением, сравним эти результаты с результатами агломеративной кластеризации (с желаемым количеством кластеров 30, так как в наборе данных 30 категорий):

 clusters_agg = AgglomerativeClustering(n_clusters=30).fit_predict(X) df['class_prd'] = clusters_agg.astype(int)

Мы будем идентифицировать полученные кластеры целочисленными метками; заголовкам, принадлежащим к одному и тому же кластеру, присваивается одна и та же целочисленная метка. Функция cluster_measure из модуля compare_clusters нашего репозитория GitHub возвращает совокупную F-меру и количество идеально совпадающих кластеров, чтобы мы могли увидеть, насколько точным был наш результат кластеризации:

 from clustering.compare_clusters import cluster_measure # 'cluster_measure` requires given text categories to be in the column 'text_category` df['text_category'] = df['category'] res_df, fmeasure_aggregate, true_matches = cluster_measure(df, gt_column='class_gt') fmeasure_aggregate, len(true_matches) # Outputs: (0.19858339749319176, 0)

Сравнивая результаты этих кластеров с оптимальным решением, мы получаем низкую F-меру 0,198 и 0 кластеров, соответствующих фактическим группам классов, показывая, что агломеративные кластеры не соответствуют выбранным нами категориям заголовков. Давайте проверим кластер в результате, чтобы увидеть, как он выглядит.

 df[df['class_prd'] == 0]['category'].value_counts()

Изучив результаты, мы видим, что этот кластер содержит заголовки из всех категорий:

 POLITICS 1268 ENTERTAINMENT 712 THE WORLDPOST 373 HEALTHY LIVING 272 QUEER VOICES 251 PARENTS 212 BLACK VOICES 211 ... FIFTY 24 EDUCATION 23 COLLEGE 14 ARTS 13

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

Метод кластеризации 2: K-средних

Давайте попробуем другой популярный алгоритм кластеризации на том же наборе данных: кластеризация k-средних. Мы создадим новый фрейм данных и снова воспользуемся функцией cluster_measure :

 kmeans = KMeans(n_clusters=30, random_state=0).fit(X) df2 = df.copy() df2['class_prd'] = kmeans.predict(X).astype(int) res_df, fmeasure_aggregate, true_matches = cluster_measure(df2) fmeasure_aggregate, len(true_matches) # Outputs: (0.18332960871141976, 0)

Как и результат агломеративной кластеризации, наш результат кластеризации k-средних сформировал кластеры, которые не похожи на заданные нами категории: он имеет F-меру 0,18 по сравнению с оптимальным решением. Поскольку два результата кластеризации имеют схожие F-меры, было бы интересно сравнить их друг с другом. У нас уже есть кластеризация, поэтому нам просто нужно вычислить F-меру. Во-первых, мы поместим оба результата в один столбец, где class_gt иметь выходные данные агломерационной кластеризации, а class_prd — выходные данные кластеризации k-средних:

 df1 = df2.copy() df1['class_gt'] = df['class_prd'] res_df, fmeasure_aggregate, true_matches = cluster_measure(df1, gt_column='class_gt') fmeasure_aggregate, len(true_matches) # Outputs: (0.4030316435020922, 0)

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

Узнайте больше об улучшенных результатах кластеризации

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

• Сравнение кластеров — обзор Доротеи Вагнер и Силке Вагнер
• Сравнение кластеров — расстояние, основанное на информации , Марина Мейла.
• Теоретико-информационные меры для сравнения кластеризаций: варианты, свойства, нормализация и поправка на случайность Нгуен Суан Винь, Жюльен Эппс и Джеймс Бейли

---

Дальнейшее чтение в блоге Toptal Engineering:

• Наука о графических данных с помощью Python/NetworkX
• Полуконтролируемая классификация изображений с немаркированными данными
• Встраивания в машинное обучение: упрощение сложных данных

Блог Toptal Engineering выражает благодарность Луису Брончалу за рассмотрение примеров кода, представленных в этой статье.