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

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

Для определенного класса алгоритмов кластеризации (в частности k-средства, k-медоиды и алгоритм ожидания – максимизации ) существует параметр, обычно называемый k который указывает количество обнаруживаемых кластеров. Другие алгоритмы, такие как DBSCAN и Алгоритм ОПТИКИ не требуют указания этого параметра; иерархическая кластеризация полностью избегает проблемы.

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

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

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

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

Этот метод можно проследить до предположений Роберт Л. Торндайк в 1953 г.[3]

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

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

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

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

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

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

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

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

JumpMethod (X): Позволять Y = (p / 2) В этом список D размера n + 1 Позволять D [0] = 0 За k = 1 ... n: Кластер X с k кластерами (например, с k-средними) Позволять d = искажение результирующей кластеризации D [k] = d ^ (- Y) Определять J (i) = D [i] - D [i-1] Возвращаться k между 1 и n, который максимизирует J (k)

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

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

Обобщая результаты выше, можно видеть, что для достаточно высоких значений п, преобразованное искажение приблизительно равен нулю для K < грамм, затем резко подскакивает и начинает линейно возрастать в течение K ≥ грамм. Алгоритм прыжка для выбора K использует это поведение для определения наиболее вероятного значения истинного количества кластеров.

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

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

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

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

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

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

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

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

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

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

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

Библиография

  1. ^ См., Например, Дэвид Дж. Кетчен младший; Кристофер Л. Шук (1996). «Применение кластерного анализа в исследованиях стратегического управления: анализ и критика». Журнал стратегического управления. 17 (6): 441–458. Дои:10.1002 / (SICI) 1097-0266 (199606) 17: 6 <441 :: AID-SMJ819> 3.0.CO; 2-G.[мертвая ссылка ]
  2. ^ См., Например, рисунок 6 в
  3. ^ Роберт Л. Торндайк (Декабрь 1953 г.). «Кто в семье?». Психометрика. 18 (4): 267–276. Дои:10.1007 / BF02289263.
  4. ^ Д. Пеллег; А. В. Мур. X-means: расширение K-средних с помощью эффективной оценки количества кластеров (PDF). Материалы семнадцатой международной конференции по машинному обучению (ICML 2000). Получено 2016-08-16.
  5. ^ Сирил Гутте, Ларс Кай Хансен, Мэтью Г. Липтрот и Эгилл Роструп (2001). «Кластеризация пространства признаков для метаанализа фМРТ». Картирование человеческого мозга. 13 (3): 165–183. Дои:10.1002 / hbm.1031. ЧВК  6871985. PMID  11376501. Архивировано из оригинал на 2012-12-17.CS1 maint: несколько имен: список авторов (связь) особенно см. рисунок 14 и приложение.
  6. ^ Екатерина А. Сахар; Гарет М. Джеймс (2003). «Определение числа кластеров в наборе данных: теоретико-информационный подход». Журнал Американской статистической ассоциации. 98 (Январь): 750–763. Дои:10.1198/016214503000000666.
  7. ^ Питер Дж. Руссеу (1987). «Силуэты: графическое средство для интерпретации и проверки кластерного анализа». Вычислительная и прикладная математика. 20: 53–65. Дои:10.1016/0377-0427(87)90125-7.
  8. ^ Р. Ллети; M.C. Ортис; Лос-Анджелес Сарабия; РС. Санчес (2004). "Выбор переменных для k-Средний кластерный анализ с использованием генетического алгоритма, оптимизирующего силуэты ». Analytica Chimica Acta. 515: 87–100. Дои:10.1016 / j.aca.2003.12.020.
  9. ^ R.C. де Аморим и К. Хенниг (2015). «Восстановление количества кластеров в наборах данных с шумовыми характеристиками с использованием коэффициентов масштабирования функций». Информационные науки. 324: 126–145. arXiv:1602.06989. Дои:10.1016 / j.ins.2015.06.039.
  10. ^ См. Например «Нахождение нужного количества кластеров в k-средних и электромагнитная кластеризация: перекрестная проверка v-Fold». Электронный учебник статистики. StatSoft. 2010 г.. Получено 2010-05-03.
  11. ^ Can, F .; Озкарахан, Э. А. (1990). «Концепции и эффективность методологии кластеризации на основе коэффициента покрытия для текстовых баз данных». Транзакции ACM в системах баз данных. 15 (4): 483. Дои:10.1145/99935.99938. HDL:2374.MIA / 246. особенно см. раздел 2.7.
  12. ^ Хонархах, М; Каерс, Дж (2010). «Стохастическое моделирование паттернов с использованием дистанционного моделирования паттернов». Математические науки о Земле. 42 (5): 487–517. Дои:10.1007 / s11004-010-9276-7.
  • Ральф Вагнер, Сорен В. Шольц, Райнхольд Деккер (2005): Число кластеров в сегментации рынка, в: Даниэль Байер, Райнхольд Декер; Ларс Шмидт-Тим (ред.): Анализ данных и поддержка принятия решений, Берлин, Springer, 157–176.

внешняя ссылка