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

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

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

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

Метод локтя

Основная статья: Метод локтя (кластеризация)

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

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

Этот метод можно отнести к предположениям Роберта Л. Торндайка в 1953 году. Хотя идея метода локтя кажется простой и понятной, другие методы (как подробно описано ниже) дают лучшие результаты.

X-средняя кластеризация

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

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

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

Информационно-теоретический подход

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

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

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

Это также среднее расстояние Махаланобиса по измерению между X и ближайшим центром кластера. $c_{X}$. Поскольку минимизация всех возможных наборов центров кластеров непомерно сложна, на практике искажение вычисляется путем создания набора центров кластеров с использованием стандартного алгоритма кластеризации и вычисления искажения на основе результата. Псевдокод для метода перехода с входным набором 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)

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

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

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

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

Метод силуэта

Основная статья: Силуэт (кластеризация)

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

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

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

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

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

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

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

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

Статистика разрыва

Роберт Тибширани , Гюнтер Вальтер и Тревор Хасти предложили оценивать количество кластеров в наборе данных с помощью статистики разрывов. Статистика разрывов, основанная на теоретических основаниях, измеряет, насколько далека объединенная внутрикластерная сумма квадратов вокруг центров кластера от суммы квадратов, ожидаемой при нулевом эталонном распределении данных. Ожидаемое значение оценивается путем моделирования нулевых справочных данных характеристик исходных данных, но без каких-либо кластеров. Оптимальное количество кластеров затем оценивается как значение k, для которого наблюдаемая сумма квадратов падает в наибольшей степени ниже нулевого эталона.

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

Статистика пробелов реализована как функция clusGap в кластера . пакете в Р. ​

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

• Кластерограмма – график кластерной диагностики – для визуальной диагностики выбора количества ( k ) кластеров ( R- код)
• Восемь методов определения оптимального значения k для k анализа -средних . Ответ на stackoverflow, содержащий код R для нескольких методов вычисления оптимального значения k для k -средних. кластерного анализа