Машинное обучение — спектральная кластеризация

искусственный интеллект

Это 16-й день моего участия в августовском испытании обновлений.Подробности о событии:Испытание августовского обновления

Введение в спектральную кластеризацию

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

Принцип спектральной кластеризации

Алгоритм спектральной кластеризации — это алгоритм, который проще в использовании, но в принципе не так прост для понимания. Для алгоритма спектральной кластеризации мы можем обобщить его в следующие шаги:
Вход: набор выборок D=(x1,x2,...,xn), метод генерации матрицы подобия, размерность k1 ​​после уменьшения размерности, метод кластеризации, размерность k2 после кластеризации
Вывод: раздел кластера C(c1,c2,...ck2).\

  1. Матрица сходства S\ выборки строится по методу генерации входной матрицы сходства

2) Построить матрицу смежности W по матрице подобия S и построить матрицу степеней D
3) Вычислить матрицу Лапласа L
4) Построить нормированную матрицу Лапласа D−1/2LD−1/2
5) Вычислить собственный вектор f, соответствующий наименьшему k1 собственному значению D−1/2LD−1/2
6) Нормируем матрицу, составленную из соответствующего собственного вектора f по строке, и, наконец, формируем n×k1-мерную собственную матрицу F
7) Возьмите каждую строку в F как k1-мерную выборку, всего n выборок, и используйте входной метод кластеризации для кластеризации, а размерность кластеризации равна k2.
8) Получите раздел кластера C(c1,c2,...ck2).
Конкретный принцип алгоритма спектрального кластеризации требует определенной основы, связанной с теорией графа, поэтому он не будет расширен здесь. Для подробного объяснения, пожалуйста, обратитесь к содержанию пятого урока курса CS224W STANFORD Университета Стэнфорда. Для изучения курса, пожалуйста, обратитесь к [Ссыловая ссылка 2], Или вы можете прочитать [Ссылка 3], чтобы понять Содержание курса.

Краткое изложение алгоритмов спектральной кластеризации

Основные преимущества спектральной кластеризации

  1. Для спектральной кластеризации требуется только матрица подобия между данными, поэтому она эффективна для кластеризации с разреженными данными. Это сложно для традиционных алгоритмов кластеризации, таких как K-Means.
  2. Из-за использования уменьшения размерности сложность выше, чем у традиционных алгоритмов кластеризации при работе с кластеризацией многомерных данных.

Основной недостаток спектральной кластеризации

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

Реализация спектральной кластеризации в Sklearn

Реализация алгоритма спектральной кластеризации предоставляется в sklearn:

sklearn.cluster.SpectralClustering(n_clusters=8, *, eigen_solver=None, n_components=None, random_state=None, n_init=10, gamma=1.0, affinity='rbf', n_neighbors=10, eigen_tol=0.0, assign_labels='kmeans', degree=3, coef0=1, kernel_params=None, n_jobs=None, verbose=False)

Детали параметра:

'n_clusters' - размерность проецируемого подпространства, то есть количество кластеров после кластеризации также равно k в принципе
«eigen_solver» — это используемая стратегия декомпозиции собственных значений, необязательные параметры: «arpack», «lobpcg», «amg». AMG требует установки pyamg. Это может быть быстрее на очень больших разреженных задачах, но также может привести к нестабильности. Если нет, также можно использовать «arpack».
«random_state» — это генератор псевдослучайных чисел для разложения собственных векторов в K-средних.
RBF 'Gamma' представлял, поли, сигмоид, лаплац и коэффициент ядра ядра
Здесь перечислены только часть используемых параметров.Полные параметры см. в официальной документации, а именно [Ссылка 4] или [Ссылка 5], чтобы понять значение и принцип действия параметров.

Категории