Определение количества кластеров в наборе данных - Determining the number of clusters in a data set

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

Для определенного класса алгоритмов кластеризации (в частности K -средних, к -medoids и алгоритм ожидания максимизации ), есть параметр обычно упоминается как к , указывающее количество кластеров для обнаружения. Другие алгоритмы, такие как DBSCAN и алгоритм OPTICS , не требуют указания этого параметра; иерархическая кластеризация полностью устраняет проблему.

Правильный выбор k часто неоднозначен, интерпретация зависит от формы и масштаба распределения точек в наборе данных и желаемого разрешения кластеризации пользователя. Кроме того, увеличение k без штрафа всегда будет уменьшать количество ошибок в результирующей кластеризации до крайнего случая нулевой ошибки, если каждая точка данных считается своим собственным кластером (то есть, когда k равно количеству точек данных, n ). Тогда интуитивно понятно, что оптимальный выбор k обеспечит баланс между максимальным сжатием данных с использованием одного кластера и максимальной точностью путем назначения каждой точки данных ее собственному кластеру . Если подходящее значение k не является очевидным из предварительных знаний о свойствах набора данных, его нужно как-то выбрать. Есть несколько категорий методов для принятия этого решения.

Локтевой метод

Объясненное отклонение. «Локоть» обозначен красным кружком. Таким образом, количество выбранных кластеров должно быть 4.

Метод локтя рассматривает процент дисперсии, объясняемую как функцию количества кластеров: следует выбрать количество кластеров, чтобы добавление еще одного кластера не давало лучшего моделирования данных. Точнее, если построить график зависимости процента дисперсии, объясняемой кластерами, от количества кластеров, первые кластеры добавят много информации (объяснят большую дисперсию), но в какой-то момент предельный выигрыш упадет, давая угол в график. На этом этапе выбирается количество кластеров, отсюда и «критерий локтя». Этот «локоть» не всегда можно однозначно идентифицировать, что делает этот метод очень субъективным и ненадежным. Процент объясненной дисперсии - это отношение дисперсии между группами к общей дисперсии, также известное как F-тест . Небольшая вариация этого метода отображает кривизну внутригрупповой дисперсии.

Этот метод восходит к предположению Роберта Л. Торндайка в 1953 году.

X-означает кластеризацию

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

Информационно-критериальный подход

Другой набор методов для определения количества кластеров - это информационные критерии, такие как информационный критерий Акаике (AIC), байесовский информационный критерий (BIC) или информационный критерий отклонения (DIC) - если возможно построить функцию правдоподобия для модель кластеризации. Например: модель k- средних является «почти» моделью гауссовой смеси, и можно построить вероятность для модели гауссовой смеси и, таким образом, также определить значения информационных критериев.

Теоретико-информационный подход

Теория искажения скорости была применена для выбора k, называемого методом «скачка», который определяет количество кластеров, которые максимизируют эффективность при минимизации ошибок по стандартам теории информации . Стратегия алгоритма состоит в том, чтобы сгенерировать кривую искажения для входных данных путем запуска стандартного алгоритма кластеризации, такого как k-среднее для всех значений k между 1 и n , и вычисления искажения (описанного ниже) результирующей кластеризации. Затем кривая искажения преобразуется с помощью отрицательной мощности, выбранной на основе размерности данных. Скачки в результирующих значениях означают разумный выбор для k , причем самый большой скачок представляет лучший выбор.

Искажение кластеризации некоторых входных данных формально определяются следующим образом : Пусть набор данных быть смоделирован как р - мерная случайная величина , X , состоящие из распределения смеси из G компонентов с общей ковариантностью , $Г$ . Если мы допустим набор из K центров кластеров с ближайшим центром к заданной выборке X , то минимальное среднее искажение на измерение при подборе K центров к данным будет: ${\ Displaystyle c_ {1} \ ldots c_ {K}}$ ${\ displaystyle c_ {X}}$

{\ displaystyle d_ {K} = {\ frac {1} {p}} \ min _ {c_ {1} \ ldots c_ {K}} {E [(X-c_ {X}) ^ {T} \ Gamma ^ {- 1} (X-c_ {X})]}}

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

JumpMethod(X):
    Let Y = (p/2)
    Init a list D, of size n+1
    Let D[0] = 0
    For k = 1 ... n:
        Cluster X with k clusters (e.g., with k-means)
        Let d = Distortion of the resulting clustering
        D[k] = d^(-Y)
    Define J(i) = D[i] - D[i-1]
    Return the k between 1 and n that maximizes J(k)

Выбор мощности преобразования мотивирован асимптотическими рассуждениями с использованием результатов теории искажения скорости. Пусть данные X имеют единственное произвольно p -мерное гауссовское распределение и пусть фиксированное для некоторого $α$ больше нуля. Тогда искажение кластеризации K кластеров в пределе, когда p стремится к бесконечности, равно . Можно видеть , что асимптотический, искажение кластеризации к мощности пропорционально , который по определению приблизительно число кластеров K . Другими словами, для одного гауссова распределения увеличение K сверх истинного числа кластеров, которое должно быть равно одному, вызывает линейный рост искажения. Такое поведение важно в общем случае смеси нескольких компонентов распределения. ${\ Displaystyle Y = (p / 2)}$ ${\ Displaystyle К = \ lfloor \ alpha ^ {p} \ rfloor}$ ${\ displaystyle \ alpha ^ {- 2}}$ ${\ Displaystyle (-p / 2)}$ ${\ displaystyle \ alpha ^ {p}}$

Пусть X - смесь G p -мерных гауссовских распределений с общей ковариацией. Тогда для любого фиксированного K, меньшего, чем G , искажение кластеризации при стремлении p к бесконечности бесконечно. Интуитивно это означает, что кластеризация меньшего, чем правильное количество кластеров не может описывать асимптотически многомерные данные, что приводит к неограниченному увеличению искажения. Если, как описано выше, сделать K возрастающей функцией p , а именно, будет достигнут тот же результат, что и выше, с величиной искажения в пределе, когда p стремится к бесконечности, равным . Соответственно, существует та же пропорциональная зависимость между трансформированным искажением и количеством кластеров, K . ${\ Displaystyle К = \ lfloor \ alpha ^ {p} \ rfloor}$ ${\ displaystyle \ alpha ^ {- 2}}$

Ввод результатов выше вместе, можно видеть , что при достаточно больших значениях р , преобразованная искажение приблизительно равно нулю для K < G , то прыгает внезапно и начинает линейно увеличивается для K ≥ G . Алгоритм перехода для выбора K использует это поведение, чтобы определить наиболее вероятное значение для истинного количества кластеров. ${\ displaystyle d_ {K} ^ {- p / 2}}$

Хотя математическая поддержка метода дается в виде асимптотических результатов, алгоритм был эмпирически подтвержден, чтобы хорошо работать в различных наборах данных с разумной размерностью. В дополнение к методу локализованного перехода, описанному выше, существует второй алгоритм для выбора K с использованием тех же преобразованных значений искажения, известный как метод ломаной линии. Метод ломаной линии определяет точку скачка на графике преобразованного искажения, выполняя простую аппроксимацию методом наименьших квадратов ошибок двух отрезков, которые теоретически будут падать вдоль оси x для K < G , и вдоль линейно возрастающей фазы. преобразованного искажения участка для K ≥ G . Метод ломаной линии более надежен, чем метод скачка, поскольку его решение является глобальным, а не локальным, но он также полагается на предположение о гауссовых компонентах смеси, тогда как метод скачка является полностью непараметрическим и доказал свою жизнеспособность для общие распределения смеси.

Силуэтный метод

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

Перекрестная проверка

Можно также использовать процесс перекрестной проверки для анализа количества кластеров. В этом процессе данные делятся на v частей. Затем каждая из частей по очереди откладывается как тестовый набор, модель кластеризации, вычисляемая на других обучающих наборах v - 1, и значение целевой функции (например, сумма квадратов расстояний до центроидов для k -среднее) рассчитано для тестовой выборки. Эти значения v вычисляются и усредняются для каждого альтернативного количества кластеров, а номер кластера выбирается таким образом, чтобы дальнейшее увеличение количества кластеров приводило только к небольшому снижению целевой функции.

Определение количества кластеров в текстовых базах данных

В текстовых базах данных набор документов, определяемый документом по матрице D (размера m на n, m: количество документов, n: количество терминов), количество кластеров можно приблизительно оценить по следующей формуле, где t - количество ненулевых записей в D. Обратите внимание, что в D каждая строка и каждый столбец должны содержать по крайней мере один ненулевой элемент. ${\ displaystyle {\ tfrac {mn} {t}}}$

Анализ матрицы ядра

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

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

дальнейшее чтение

Ральф Вагнер , Серен В. Шольц, Райнхольд Декер (2005): Число кластеров в сегментации рынка, в: Даниэль Байер, Райнхольд Декер; Ларс Шмидт-Тим (ред.): Анализ данных и поддержка принятия решений, Берлин, Springer, 157–176.

Внешние ссылки

Clustergram - график диагностики кластера - для визуальной диагностики выбора количества ( k ) кластеров ( код R )
Восемь методов определения оптимального значения k для анализа k- средних - Ответ на stackoverflow, содержащий код R для нескольких методов вычисления оптимального значения k для кластерного анализа k- средних
Разделение и кластеризация: сколько классов? Бесплатный семинарский документ доступен на сервере HAL, id = hal-02124947: представлены два непараметрических метода (предоставляются библиографические ссылки), один для числовых переменных (работает с массивом расстояний, не обязательно евклидовым), один для категориальных переменных ( оптимальное разбиение; работает также со знаковыми несходствами).

Languages

In other projects