8 КЛАСТЕРНЫЙ АНАЛИЗ

Оценка чистоты кластеризации с помощью индекса Дэвиса-Болдина

Здравствуйте и вновь добро пожаловать на занятия по теме «Кластерный анализ и машинное обучение без учителя на языке Python».

Для начала отметим: замечательно, что функция затрат уменьшается при каждом проходе. Это имеет важный смысл – ведь мы хотим, чтобы наши точки, представляющие данные, были поближе к центру кластера, к которому они принадлежат. Тогда, как следствие, квадрат расстояния будет малым, когда вероятность принадлежности к кластеру является высокой. Другими словами, нам нужны малые «внутрикластерные» и большие «межкластерные» расстояния – на рисунке они обозначены красной и зелёной линиями соответственно.

Но у этого метода есть ряд недостатков.

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

Кроме того, она чувствительна к масштабам данных. Так, если все наши данные находятся в диапазоне между 0 и 1, то и все наши k-средние будут находиться между 0 и 1, что, в свою очередь, будет означать, что все наши квадраты расстояний будут меньше единицы. А теперь представьте, что все наши данные находятся в пределах от 0 до миллиона – то есть 106. Тогда наши квадраты расстояния могут быть порядка 1012! Таким образом, получаемая нами функция затрат не является чем-то таким, где точность является универсальной величиной, не зависящей от рассматриваемых данных. Она становится зависимой от самих данных.

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

Резюмируем. Недостаток первый – значение функции затрат увеличивается с увеличением количества данных – причём и от количества примеров, и от количества признаков. Его можно нивелировать путём деления на N и D.

Недостаток второй – масштаб данных прямо влияет на значение функции затрат. Мы можем компенсировать его путём нормализации данных перед кластеризацией методом k-средних – например, сначала разделить данные на их общее среднее значение или на стандартное отклонение.

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

Существует один интересный способ оценки кластеризации, который называется чистотой:

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

Прежде всего отметим, что она содержит деление на N, что очень хорошо, так как уравновешивает величину по количеству имеющихся примеров. Далее, что такое c и t. Ck означает набор данных, принадлежащих кластеру k (тогда как K означает количество кластеров). Tj означает набор данных, принадлежащих целевому классу j. Мы должны найти максимум относительно j; это будет означать, что мы найдём класс целевых переменных, которые, вероятнее всего, принадлежат к данному кластеру, поскольку они имеют наибольшее количество точек пересечения. Разумеется, формулу придётся несколько видоизменить, поскольку принадлежность к кластеру, заданное набором данных, в случае «мягкого» метода k-средних, не является однозначной, а имеет вероятностный характер.

Рассмотрим в качестве примера базу MNIST, где каждый класс представляет собой цифру от 0 до 9. В этом случае у нас есть 10 центров кластеров, но мы понятия не имеем, что к чему относится. Чтобы определить это, мы рассматриваем каждый из целевых классов, и если обнаружим наилучшее пересечение данных с данными, представляющими цифру 5, то это будет означать, что данный кластер, вероятнее всего, представляет цифру 5. Вследствие этого лучшая чистота, которую можно получить, равна единице; это значит, что в каждом кластере данные, приписанные ему, соответствуют истинной метке.

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

Многие другие показатели, включая rand-показатель, F-показатель, коэффициент Жаккара и метод нормализованной взаимной информации, также требуют целевых переменных. Эти методы, требующие использования меток, называются методами внешней проверки (external validation).

В более правдоподобном случае, когда мы берёмся за обучение без учителя, мы, вероятнее всего, не имеем меток, но всё равно хотим уметь проверить, насколько хороша кластеризация. Для этого существуют так называемые методы внутренней проверки (internal validation), которые не требуют наличия меток. Примером такого метода является индекс Дэвиса-Болдина (Davies-Bouldin index):

Это уравнение похоже на предыдущее уравнение для чистоты – в частности, в качестве показателя мы для всех k точно так же ищем максимум относительно j.

В данном уравнении  означает среднее расстояние от каждой точки до центра её кластера k. Как видите, в данном случае σ – весьма удачный символ, поскольку намекает на схожесть с стандартным отклонением. означает то же самое, только для кластера j. Обратите внимание, что поскольку мы фокусируемся на «мягком» методе k-средних, необходимо удостовериться, что все σ вычислены правильно, с учётом вероятностного характера принадлежности к кластеру.

Далее,  представляет собой расстояние от центра кластера k до центра кластера j.

В идеале нам нужно чтобы числитель в выражении был малым, а знаменатель – большим, поскольку мы хотим, чтобы всё, что внутри одного кластера было как можно ближе друг к другу, тогда как один кластер отстоял от другого, наоборот, как можно дальше. Отсюда следует, что тем меньше величина индекса Дэвиса-Болдера, тем лучше.

Таким образом, как вы можете видеть, все рассмотренные показатели измеряют одно и то же, только разными способами.

Применение метода k-средних на действующей базе MNIST

Прежде всего отметим, если вы не знаете, что такое база данных MNIST, то это база написанных от руки цифр от 0 до 9. Они являются изображениями, но, как вы знаете, мы работаем с векторами, поэтому каждое изображение размером 28×28 будет преобразовано в 784-размерный вектор. Саму базу данных вы можете получить, перейдя по адресу https://www.kaggle.com/c/digit-recognizer. Там же размещены и дополнительные сведения о базе на случай, если вы ещё никогда не имели с ней дела. Кроме того, весьма несложно и вывести на экран данные изображения, просто преобразовав их в формат 28×28 и использовав функцию plt.imshow().

Обратите внимание, что мы используем файл train.csv, поскольку файл test.csv не содержит меток – он предназначен для оценки алгоритмов на kaggle. Не забудьте также, что наши данные должны находиться в папке large_files, размещённой по соседству с нашей учебной папкой.

Теперь перейдём к рассмотрению кода.

Первая функция – get_data. В ней используется библиотека pandas для загрузки csv-файла. Мы также используем функцию as_matrix для преобразования данных в Numpy-массив. Затем мы перемешиваем данные, чтобы они попадались в случайном порядке. Далее, данные содержат целые числа в диапазоне от 0 до 255, тогда как нам надо преобразовать их так, чтобы они находились в диапазоне от 0 до 1. Если вы лично просматривали файлы данных, вы знаете, что первый столбец содержит метки, тогда как остальные – данные об изображении. Поэтому мы установим в качестве X всё, кроме первого столбца, а Y – первый столбец. И ещё нужно установить предел, чтобы метод k-средних не занял чересчур много времени. Лично я не заметил особой разницы между 1 000 примеров в наборе данных и 10 000 примеров, поэтому будем рассматривать лишь 1 000.

import numpy as np

import pandas as pd

import matplotlib.pyplot as plt

from kmeans import plot_k_means, get_simple_data

from datetime import datetime

df = pd.read_csv(‘./large_files/train.csv’)

data = df.as_matrix()

if limit is not None:

return X, Y

Следующей идёт функция purity. Ей требуются только данные о принадлежности к кластерам и Y, являющемся метками. Всё, что мы здесь делаем, – это циклы относительно k по всем кластерам и относительно j по всем целевым меткам от 0 до K. Рассматривая матрицу R, мы получим необходимое пересечение. Не забывайте, что размерность матрицы составляет N×K. Нам нужны только те строки, которые соответствуют целевым меткам, то есть j. Это и есть первый индекс.

Второй же индекс показывает, какой кластер K рассматривается в данный момент.

Далее мы находим сумму всех этих принадлежностей в зависимости от того, сколько точек данных принадлежит данному кластеру. Обратите внимание, что и в случае «жёсткого» метода k-средних, содержащего значения лишь 0 и 1, это выражение остаётся в силе.

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

И последнее – делим всё на N, чтобы значение было независимо от количества данных.

def purity(Y, R):

N, K = R.shape

for k in xrange(K):

best_target = -1

max_intersection = 0

for j in xrange(K):

max_intersection = intersection

best_target = j

p += max_intersection

return p / N

Следующая функция вычисляет индекс Дэвиса-Болдина. Для неё необходимы все наши данных X, средние значения M и принадлежности к кластерам R. Первый цикл вычисляет сигмы. Не забывайте, что они обозначают среднее расстояние между точками данных в кластере K до его центра. Но в связи с тем, что каждая точка потенциально может быть частью этого кластера, нам нужны все X.

def DBI(X, M, R):

K, D = M.shape

sigma = np.zeros(K)

squared_distances = (diffs * diffs).sum(axis=1)

Во втором цикле вычисляется собственно индекс Дэвиса-Болдина с использованием ранее вычисленных сигм. Заметьте, что уравнение связано с K и что чем значение индекса меньше – тем лучше, то есть если K будет большим, то мы получим лучший результат. Что, впрочем, не страхует нас от банального случая, когда N = K, то есть когда каждая точка данных является своим собственным кластером.

dbi = 0

max_ratio = 0

if k != j:

ratio = numerator / denominator

max_ratio = ratio

dbi += max_ratio

return dbi / K

Наконец, в самом низу у нас разместилась функция main. Как вы помните, мы ограничиваем количество данных одной тысячей, поскольку в противном случае метод k-средних будет занимать слишком много времени. Разумеется, мы знаем, что наше K равно 10, ведь у нас 10 цифр. Но чтобы лучше понять чистоту и индекс Дэвиса-Болдина, советую поэкспериментировать с разными значениями K. Вы можете также попробовать их и на других наборах данных, особенно искусственных, правильное решение для которых вам уже известно.

X, Y = get_data(10000)

print(“Number of data points:”, len(Y))

M, R = plot_k_means(X, len(set(Y)))

print(“Purity:”, purity(Y, R))

print(“DBI:”, DBI(X, M, R))

if __name__ == “__main__”:

Один способ подобрать значение K

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

Сейчас мы рассмотрим очень простой и лёгкий способ выбрать K – количество кластеров.

Как вы могли заметить, при увеличении K наша функция затрат всегда уменьшается. Не забывайте, что это сумма квадратов ошибок в кластере. Это значит, что чем ближе все точки к центру кластера, тем меньше будет ошибка. Увеличивая количество кластеров, вы «помогаете» точке оказаться у центра кластера.

Если это не совсем понятно, представьте себе предельный случай, когда K = N, то есть количество кластеров равно количеству данных. В этом случае каждая точка является центром своего собственного кластера, а сам кластер будет состоять из одной этой точки. Тогда общее значение функции затрат будет равно нулю.

Но перебирая значения K от 1 до N, можно заметить кое-что любопытное. График функции затрат приобретает схожесть с хоккейной клюшкой – то есть сначала идёт крутое снижение значения, а затем – очень плавное. Таким образом, существует некоторая точка, после которой увеличение значения K даёт нам лишь незначительное улучшение. Именно в ней данные лучше всего подходят для кластеризации. В этой точке уменьшение K даёт резкое возрастание ошибки, зато увеличение K даёт лишь незначительное уменьшение ошибки, не оправдывающее дальнейшего увеличения K. Вот это значение K, находящееся на изломе «клюшки» и является нужным количеством кластеров.

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

В наведенном ниже учебном коде мы продемонстрируем этот эффект. Если вы не хотите писать код самостоятельно, то соответствующий файл на github называется choose_k.py.

Итак, начнём с импорта необходимых библиотек.

from kmeans import plot_k_means, get_simple_data, cost

И далее идёт простенькая программа. Мы берём простейшие данные и перебираем количество кластеров от 1 до 10 (поскольку количество кластеров, равное нулю, не имеет смысла).

X = get_simple_data()

costs = np.empty

for k in xrange(1, 10):

M, R = plot_k_means(X, k, show_plots=False)

c = cost(X, R, M)

plt.title(“Cost vs K”)

if __name__ == ‘__main__’:

Запустим программу и посмотрим, что получится.

Вначале мы видим наши данные, сгенерированные вокруг трёх гауссовых облаком.

Затем график функции затрат относительно K.

Как вы можете видеть, крутое снижение заканчивается, когда K = 3. Таким образом, K = 3 – это нужное количество кластеров.

Задать вопрос эксперту

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

Оценка качества кластеризации временных рядов является неотъемлемой частью процесса исследования. Существует несколько мер, которые помогают в оценке качества полученных кластеров и определении оптимального числа кластеров. Ниже представлены некоторые из них:

Индекс Дэвиса-Болдина (Davies-Bouldin index)

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

Индекс силуэта (Silhouette index)

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

Коэффициент корреляции Силуэта (Silhouette coefficient)

Коэффициент корреляции Силуэта также используется для оценки качества кластеризации временных рядов. Он основан на индексе силуэта и вычисляется как среднее значение коэффициентов силуэта для всех объектов, нормализованные от -1 до 1.

Rand index

Рэндовский индекс (Rand index) является мерой, позволяющей оценить сходство между двумя кластеризациями. Он вычисляется как сумма чисел True Positive и True Negative, поделенная на сумму всех возможных пар объектов.

Adjusted Rand index

Скорректированный Рэндовский индекс (Adjusted Rand index) представляет собой модифицированную версию обычного Рэндовского индекса, который учитывает шансовую согласованность между случайными кластеризациями.

Normalized Mutual Information (NMI)

Нормализованная взаимная информация (NMI) — мера, используемая для оценки сходства между двумя кластеризациями. Она основана на взаимной информации между кластеризацией и истинной разметкой данных.

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

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

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

Индекс Дэвиса-Болдина (DBI)

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

Индекс Силуэта рассчитывается для каждого объекта в кластере и представляет собой меру близости объекта с его собственным кластером по сравнению с другими кластерами. Величина индекса Силуэта изменяется от -1 до 1, где значения ближе к 1 указывают на более четкое разделение данных на кластеры.

Индекс Коэна (C-index)

Индекс Коэна, также известный как индекс последовательностей (Sequence index) или индекс однородности (Homogeneity index), предназначен для оценки качества разделения кластеров при учете их геометрической структуры. Он основан на оценке сравнения между выделенными кластерами и исходными группами.

Разделение индексов на 3 группы

Для определения идеального числа кластеров можно разделить индексы на 3 группы, которые помогут вам принять решение:

Разделение индексов на 3 группы позволит вам получить более полное представление о качестве разделения данных на кластеры и определить идеальное количество кластеров.

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

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

Внутренняя оценка

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

Внешняя оценка

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

Смешанные подходы

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

Заключение

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

Наглядное введение в агломерационную иерархическую кластеризацию

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

Итак, рассмотрим алгоритм!

Предположим, у нас ряд точек данных a, b, c, d, e и f. Сгруппируем их согласно «жадной стратегии». Мы видим, что b и c, а также d и e находятся ближе всего друг к другу, а потому объединяем их в первую очередь. Далее мы видим, что f ближе всего к кластеру de, поэтому объединяем их всех в кластер def. Далее, ближайшим к кластеру def является кластер bc, поэтому объединяем их в bcdef. И, наконец, объединяем этот крупный кластер с оставшимся в одиночестве a в один большой кластер abcdef.

Тут вы можете спросить: так какие же из кластеров являются правильными? Которые из них выбирать?

Для ответа на этот вопрос мы должны создать график кластеризации – то, что называется дендрограммой. На рисунке вы можете увидеть пример большой дендрограммы. В действительности настоящие кластеры легко распознать, имея обширную дендрограмму вроде приведённой на рисунке. Но, как правило, высота каждого узла в древе пропорциональна расстоянию между двумя объединяемыми кластерами, то есть высота кластера A/B равно расстоянию между кластером A и кластером B. Таким образом, если вы наткнётесь на большой пропуск в дендрограмме, то будете знать, что два данных кластера находятся далеко друг от друга, а потому можно считать их отдельными. Разумеется, в какой-то момент вам нужно будет сделать оценку кластеризации, основываясь на визуальных данных или с использованием численного критерия, такого как порог.

Варианты агломерационной кластеризации

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

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

Итак, вот некоторые популярные показатели расстояния:

– евклидово расстояние, которое, я уверен, вам всем хорошо знакомо:

– квадрат евклидова расстояния, являющийся всего лишь возведением в квадрат предыдущей формулы:

– манхэттенская метрика, известная также как расстояние городских кварталов, в которой расстояние между точками является просто суммой модулей разностей их координат:

– максимальное расстояние, являющееся просто нахождением максимума модуля между двумя любыми точками:

– и расстояние Махаланобиса – более сложное расстояние, использующее ковариацию S:

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

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

На самом деле это требование не так уж и очевидно, но подумайте, что получится, если мы позволим возникать отрицательным расстояниям?

Следующим является требование, чтобы расстояние между x и y было равно нулю тогда и только тогда, когда x = y:

Эти два критерия определяют так называемую положительно определённую функцию.

Третий критерий состоит в том, что расстояние между x и y должно быть равно расстоянию между y и x:

И последний критерий – так называемое неравенство треугольника:

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

Поговорим теперь о различных способах объединения кластеров.

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

Первый вариант называется методом одиночной связи (другое название – метод ближайшего соседа). В этом случае мы рассматриваем каждую точку кластера 1 и ищем ближайшую к ней точку из кластера 2. Минимумы всех этих точек и являются расстоянием между кластерами. В виде кода это может выглядеть примерно так:

min_dist = Infinity

for p1 in cluster1:

for p2 in cluster2:

min_dist = min( d(p1, p2), min_dist )

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

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

max_dist = 0

max_dist = max( d(p1, p2), max_dist )

Третий способ измерения расстояния между кластерами – метод средней связи – является, вероятно, наиболее интуитивно близким и понятным. В нём мы просто берём среднее расстояние. Его часто ещё называют методом UPGMA. В коде он может выглядеть так:

dist = dist / ( len(cluster1)*len(cluster2) )

И последнее, что мы рассмотрим – метод (или критерий) Уорда. В нём мы берём каждую пару кластеров и смотрим, насколько увеличится дисперсия, если мы их объединим:

Увеличение ошибки тогда составит

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

Иерархическая кластеризация на языке Python и интерпретация дендрограмм

В этой лекции мы рассмотрим иерархическую кластеризацию в коде. Мы не будем самостоятельно писать код, а используем соответствующую библиотеку и посмотрим, что с её помощью можно сделать. Если вам не хочется изучать код, а просто посмотреть уже написанный, вы можете сделать это, открыв файл hcluster.py, который можно найти, перейдя по адресу https://github.com/lazyprogrammer/machine_learning_examples. Нужная папка называется unsupervised_class.

Итак мы начинаем с функции main и импорта пары основных библиотек. Кроме того, для выполнения данного кода нам также понадобится библиотека SciPy с функциями dendrogram и linkage. Чуть позже мы увидим, как их использовать.

from scipy.cluster.hierarchy import dendrogram, linkage

Прежде всего установим значения переменных для размерностей. Я выбрал такие же значения, как и в первом примере с методом k-средних, поэтому часть кода просто перенесём оттуда:

N = 900 # number of samples

X = np.zeros((N, D))

Далее начинаются отличия. Мы вызовем функцию linkage, использующую в качестве аргументов X и особый параметр, который указывает, какой именно метод определения межкластерного расстояния будет использоваться. В данном случае это будет метод Уорда. Функция возвращает значение переменной Z. Z является матрицей, так что выведем сразу на экран и форму этой матрицы. В общем случае Z имеет формат индекс1, индекс2 (эти два индекса X представляют объединяемые на данный момент точки), третий столбец показывает расстояние – насколько далеко были два кластера до их объединения, а четвёртый столбец представляет счётчик примеров – то есть показывает количество точек в данном кластере. Таким образом, размерность Z будет равна N-1×4. И сразу выведем результат на экран.

Z = linkage(X, ‘ward’)

print “Z.shape:”, Z.shape

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

Z = linkage(X, ‘single’)

Z = linkage(X, ‘complete’)

Итак, с самого начала мы можем убедиться, что размерность Z равна N-1×4. На первой дендрограмме ясно видно, что в данных присутствуют три истинных кластера. Это метод Уорда.

Следующим мы применили метод одиночной связи, и на графике видно, как проявился «цепной эффект».

Третьим у нас был метод полной связи. Он также нашёл три истинных кластера, но не так чётко, как метод Уорда.

From Wikipedia, the free encyclopedia

Given n dimensional points, let Ci be a cluster of data points. Let Xj be an n-dimensional feature vector assigned to cluster Ci.

Here is the centroid of Ci and Ti is the size of the cluster i. is the qth root of the qth moment of the points in cluster i about the mean. If then is the average distance between the feature vectors in cluster i and the centroid of the cluster. Usually the value of p is 2, which makes the distance a Euclidean distance function. Many other distance metrics can be used, in the case of manifolds and higher dimensional data, where the euclidean distance may not be the best measure for determining the clusters. It is important to note that this distance metric has to match with the metric used in the clustering scheme itself for meaningful results.

is a measure of separation between cluster and cluster .

Here k indexes the features of the data, and this is essentially the Euclidean distance between the centers of clusters i and j when p equals 2.

Let Ri,j be a measure of how good the clustering scheme is. This measure, by definition has to account for Mi,j the separation between the ith and the jth cluster, which ideally has to be as large as possible, and Si, the within cluster scatter for cluster i, which has to be as low as possible. Следовательно, индекс Дэвиса–Булдина определяется как соотношение Si и Mi,j, при котором эти свойства сохраняются:

При такой формулировке, чем ниже значение, тем лучше разделение кластеров и «плотность» внутри кластеров.

Решением, удовлетворяющим этим свойствам, является:

Используется для определения Di:

Если N — количество кластеров:

ДБ называется индексом Дэвиса–Булдина. Это зависит как от данных, так и от алгоритма. Di выбирает наихудший сценарий, и это значение равно Ri,j для кластера, наиболее похожего на кластер i. У этой формулировки может быть множество вариаций, например, выбор среднего значения сходства кластера, средневзвешенного значения и т. д.

Более низкие значения индекса указывают на лучший результат кластеризации. Индекс улучшается (понижается) за счет увеличения разделения между кластерами и уменьшения вариаций внутри кластеров.

Эти условия ограничивают определенный таким образом индекс симметричным и неотрицательным. Из-за того, как оно определяется как функция отношения разброса внутри кластера к разделению между кластерами, более низкое значение будет означать, что кластеризация лучше. Это среднее сходство между каждым кластером и его наиболее похожим, усредненное по всем кластерам, где сходство определяется как Si выше. Это подтверждает идею о том, что ни один кластер не должен быть похож на другой, и, следовательно, лучшая схема кластеризации по существу минимизирует индекс Дэвиса-Булдина. Определенный таким образом индекс представляет собой среднее значение по всем i кластерам, и, следовательно, хорошей мерой определения того, сколько кластеров на самом деле существует в данных, является отображение его в зависимости от количества кластеров, по которым он рассчитывается. Число i, для которого это значение является наименьшим, является хорошей мерой количества кластеров, на которые в идеале можно классифицировать данные. Это имеет применение при определении значения k в алгоритме kmeans, где значение k неизвестно априори.

Реализация Java находится в ELKI, и ее можно сравнить со многими другими индексами качества кластеризации.

Примечания и ссылки

В этом уроке мы рассмотрим индекс Дэвиса-Булдина и его применение для оценки кластеризации K-Means в Python.

Оглавление

Введение

Индекс Дэвиса-Булдина (DBI) является одним из показателей оценки алгоритмов кластеризации. Чаще всего он используется для оценки качества разделения с помощью алгоритма кластеризации K-Means для заданного количества кластеров.

Ранее мы обсуждали индекс Данна и индекс Калински-Харабаша, а индекс Дэвиса-Булдина является еще одним показателем для оценки эффективности кластеризации.

Что такое индекс Дэвиса-Булдина?

Индекс Дэвиса-Булдина рассчитывается как среднее сходство каждого кластера с наиболее похожим на него кластером.

Как вы интерпретируете индекс Дэвиса-Булдина?

Чем индекс Дэвиса-Булдина (ниже среднее сходство), тем лучше кластеры разделены и тем лучше результат выполненной кластеризации.

В следующем разделе процесс расчета DBI подробно описан на нескольких примерах.

pip install sklearn
pip установить matplotlib

Книги, которые я рекомендую:

Объяснение индекса Дэвиса-Булдина

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

Рассчитать внутрикластерную дисперсию

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

: обычно значение (q) устанавливается равным 2 ((q = 2)), которое вычисляет евклидово расстояние между центроидом кластера и каждым отдельным вектором кластера (наблюдение).

Предположим, что кластеризация K-средних, выполненная на некотором наборе данных, создала три кластера. Используя приведенную выше формулу, внутрикластерная дисперсия будет рассчитана для каждого из кластеров, и мы получим значения для (S_1), (S_2) и (S_3).

Рассчитать меру разделения

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

: когда (p) установлено на 2 ((p = 2)), приведенная выше формула вычисляет евклидово расстояние между центроидами кластеров (i) и (j).

Вычислить сходство между кластерами

Дэвис Д. и Боулдин Д. (1979) определяют:

Рассчитать индекс Дэвиса-Булдина

Рассчитайте индекс Дэвиса-Булдина как:

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

В большинстве ресурсов вы увидите формулу индекса Дэвиса-Булдина, записанную как:

где (D) то же самое, что (R) в нашем примере.

Пример индекса Дэвиса-Булдина в Python

В этом разделе мы рассмотрим пример расчета индекса Дэвиса-Булдина для алгоритма кластеризации K-Means в Python.

Сначала импортируйте необходимые зависимости:

из ​​sklearn.datasets import load_iris
из sklearn.cluster импорт KMeans
из sklearn.metrics import davies_bouldin_score
импортировать matplotlib.pyplot как plt

Вы можете использовать любые данные с кодом ниже. Для простоты мы будем использовать встроенный набор данных Iris, а именно первые две функции: «ширина чашелистика» и «длина чашелистика»:

Начнем с цели K-Means из 3 кластеров:

kmeans = KMeans(n_clusters=3, случайное_состояние=30)
метки = kmeans.fit_predict(X)

И проверьте индекс Дэвиса-Булдина для получения приведенных выше результатов:

db_index = davies_bouldin_score(X, метки)
печать(db_index)

Вы должны увидеть итоговую оценку: 0,7675522686571647 или примерно 0,77.

Чтобы представить себе, как выглядят кластеры, давайте визуализируем их:

Похоже, некоторые кластеры выражены лучше, чем другие.

Пока что мы рассчитали индекс Дэвиса-Булдина только для 3 кластеров. Эту меру можно использовать аналогично методу локтя, чтобы определить оптимальное количество кластеров.

Мы можем выполнить расчет для любого количества кластеров, большего или равного 2. Давайте попробуем до 10 кластеров:

и представьте это:

plt.plot(list(results.keys()), list(results.values())))
plt.xlabel(«Количество кластеров»)
plt.ylabel(«Индекс Дэвиса-Боулдинга»)
plt.show()

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

Заключение

В этой статье мы обсудили, как рассчитать индекс Дэвиса-Булдина для оценки кластеризации в Python с использованием библиотеки sklearn.

Не стесняйтесь оставлять комментарии ниже, если у вас есть какие-либо вопросы или предложения по некоторым изменениям, а также ознакомьтесь с другими моими статьями по программированию на Python.

: Дэвис Д. и Боулдин Д. (1979). Мера разделения кластеров. I EEE Transactions по анализу шаблонов и машинному интеллекту, PAMI-1

, 224–227. https://doi.org/10.1109/TPAMI.1979.4766909