Оценка качества кластеризации

У меня есть алгоритм кластеризации (не k-средних) с входным параметром (количество кластеров). После выполнения кластеризации я бы хотел получить количественную оценку качества этой кластеризации. Алгоритм кластеризации имеет одно важное свойство. Для если я введу точек данных без какого-либо существенного различия между ними в этом алгоритме, в результате я получу один кластер, содержащий точек данных, и один кластер с точкой данных. Очевидно, это не то, что я хочу. Поэтому я хочу рассчитать этот показатель качества, чтобы оценить целесообразность этой кластеризации. В идеале я смогу сравнить эти меры для разных . Так что я буду запускать кластеризацию в диапазоне$k$$k=2$$N$$N-1$$1$$k$$k$и выберите тот, который имеет лучшее качество. Как рассчитать такой показатель качества?

ОБНОВИТЬ:

Вот пример, когда плохая кластеризация. Допустим, на плоскости есть 3 точки, образующие равносторонний треугольник. Разбить эти точки на 2 кластера, очевидно, хуже, чем разбить их на 1 или 3 кластера.$(N-1, 1)$

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

Другие рассматривают кластеризацию как попытку сгруппировать точки с одинаковыми значениями атрибутов, и в этом случае применимы такие меры, как SSE и т. Д. Однако я нахожу это определение кластеризации довольно неудовлетворительным, поскольку оно только говорит вам кое-что о конкретной выборке данных, а не что-то обобщающее о базовых распределениях. То, как методы работают с перекрывающимися кластерами, представляет собой особую проблему с этим представлением (для представления «процесс генерирования данных» это не вызывает реальной проблемы, вы просто получаете вероятности принадлежности к кластеру).

Поскольку кластеризация не контролируется, сложно априори определить, какая кластеризация лучше всего. Это тема исследования. У Гэри Кинга, известного количественного социолога, есть предстоящая статья на эту тему.

Здесь у вас есть пара мер, но есть еще много:

SSE: сумма квадратичной ошибки от элементов каждого кластера.

Межкластерное расстояние: сумма квадратного расстояния между центроидами каждого кластера.

Внутрикластерное расстояние для каждого кластера: сумма квадратного расстояния от элементов каждого кластера до его центроида.

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

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

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

А. Банерджи и Р. Н. Дейв. Проверка кластеров с использованием статистики хопкинса. 2004 IEEE Международная конференция по нечетким системам IEEE Cat No04CH37542, 1: p. 149–153, 2004.

Он основан на принципе, что если кластер действителен, то точки данных равномерно распределены внутри кластера.

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

S. Saitta, B. Raphael и IFC Smith. Комплексный индекс достоверности для кластеризации. Интелл. Данные Анал., 12 (6): с. 529–548, 2008.

Как уже отмечали другие, существует множество показателей кластеризации «качества»; большинство программ минимизируют SSE. Ни одно число не может многое рассказать о шуме в данных, или о шуме в методе, или о плоских минимумах - низких точках в Саскачеване.

Поэтому сначала попытайтесь визуализировать, почувствовать данную кластеризацию, прежде чем уменьшать ее до «41». Затем сделайте 3 пробега: вы получаете SSE 41, 39, 43 или 41, 28, 107? Каковы размеры кластеров и радиусы?

(Добавлено :) Взгляните на графики силуэтов и оценки силуэтов, например, в книге Изенмана « Современные многомерные статистические методы» (2008, 731, isbn 0387781889).

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

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

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

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

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

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

Повторение этого для многих моделей позволит вам различать модели.

Это может быть реализовано в R.

случайный лес доступен в R

Если алгоритм кластеризации не является детерминированным, попробуйте измерить «стабильность» кластеров - выясните, как часто каждые два наблюдения относятся к одному кластеру. Это довольно интересный метод, полезный для выбора k в алгоритме kmeans.