Индекс Дэвиса-Болдина в кластерном анализе

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

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

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

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

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

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

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

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

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

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

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

Чистота\frac{1}{N} \sum^{k}_{k=1} max_j=1...k |c_k \cap t_j|.

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

Прежде всего отметим, что она содержит деление на 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):

DBI = \frac{1}{K} \sum^{K}_{k=1} max_{j\neq k} [\frac{\sigma_k+\sigma_j}{d(c_k, c_j)}].

Это уравнение похоже на предыдущее уравнение для чистоты – в частности, в качестве показателя мы для всех 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

def get_data(limit=None):

    print(“Reading in and transforming data…”)

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

    data = df.as_matrix()

    np.random.shuffle(data)

    X = data[:, 1:] / 255.0

    Y = data[:, 0]

    if limit is not None:

        X, Y = X[:limit], Y[:limit]

    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

    p = 0

    for k in xrange(K):

        best_target = -1

        max_intersection = 0

        for j in xrange(K):

            intersection = R[Y==j, k].sum()

            if intersection > max_intersection:

                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)

    for k in xrange(K):

        diffs = X – M[k]

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

        weighted_squared_distances = R[:,k]*squared_distances

        sigma[k] = np.sqrt( weighted_squared_distances).mean()

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

    dbi = 0

    for k in xrange(K):

        max_ratio = 0

        for j in xrange(K):

            if k != j:

                numerator = sigma[k] + sigma[j]

                denominator = np.linalg.norm(M[k] – M[j])

                ratio = numerator / denominator

                if ratio > max_ratio:

                    max_ratio = ratio

        dbi += max_ratio

    return dbi / K

 

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

def main():

    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__”:

main()

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

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

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

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

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

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

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

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

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

import numpy as np

import matplotlib.pyplot as plt

from kmeans import plot_k_means, get_simple_data, cost

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

def main():

  X = get_simple_data()

    plt.scatter(X[:,0], X[:,1])

    plt.show()

  costs = np.empty(10)

  costs[0] = None

  for k in xrange(1, 10):

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

    c = cost(X, R, M)

    costs[k] = c

  plt.plot(costs)

  plt.title(“Cost vs K”)

  plt.show()

if __name__ == ‘__main__’:

main()

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

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

Индекс Дэвиса-Болдина в кластерном анализе

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

Индекс Дэвиса-Болдина в кластерном анализе

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

Понравилась статья? Поделить с друзьями:
Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: