Машинное обучение в основном включает в себя 3 типа обучения: обучение с учителем, обучение без учителя и обучение с подкреплением. Среди них неконтролируемое обучение является наиболее эффективным, поскольку оно помогает находить неизвестные закономерности в данных и намного быстрее и дешевле по сравнению с контролируемым обучением.

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

· Они не могут работать с невыпуклым множеством

· Требуется несколько итерационных шагов и перезапусков

Чтобы преодолеть указанные выше недостатки алгоритма K-средних, была разработана спектральная кластеризация. Теперь давайте посмотрим, что именно означает спектральный кластер.

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

Кластеризация на основе сходства и разрезы на графике

Пусть кластеризуемые точки V = {1, . . . n} — узлы графа G, а ребра графа представлены парами i , j с Sij› 0, где матрица сходства = [Sij ] . Само подобие можно рассматривать как вес ребраij.

G = (V, E), E = {(i, j), Sij > 0} ⊆ V × V (1)

Таким образом, G — неориентированный взвешенный граф. Разделение узлов графа на K кластеров известно как разрез графа (K-way), поэтому кластеризацию на основе подобия можно рассматривать как нахождение разреза в графе G.

Алгоритм

Спектральный кластер можно сформировать, выполнив три основных шага, т.е.

Шаг 1: Постройте график подобия, такой как KNN, для всех точек данных.

Шаг 2: Вставьте точки данных в низкоразмерное пространство с помощью спектрального встраивания, так как это помогает нам вычислять собственные векторы.

Шаг 3. Классические алгоритмы кластеризации, такие как K-средние, могут быть применены для разделения встраивания.

Матричное представление графика

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

Матрица смежности матрицы NxN

Наш следующий шаг — определить диагональную матрицу, которая получается путем сложения всех весов, присутствующих в строках матрицы смежности.

Например, рассмотрим матрицу смежности A

Диагональная матрица получается

Из полученной выше диагональной матрицы (D) и матрицы смежности (A) мы можем вычислить матрицу Лапласа (L) следующим образом:

L=D — A

Лапласиан может выбирать такие значения, что

Если мы продолжим с приведенным выше примером, мы получим матрицу Лапласа, подобную этой

Собственные значения и собственные векторы

Для матрицы L λ является собственным значением Lif для некоторого вектора v,

Lv=λv

Где v - собственный вектор, соответствующий собственному значению λ

Для графа G с n узлами его смежность имеет n собственных значений {λ1, λ2, λ3, λ4……λn}, где λ1‹= λ2‹= λ3‹= λ4‹=……‹=λn. И n соответствующих собственных векторов {x1,x2,x3,…..xn}

Если λ1‹= λ2‹= λ3‹= λ4‹=……‹=λn=0, то он называется спектром лапласиана

Собственные значения, которые мы рассчитали, раскрывают глобальные свойства графа, которые не видны из структуры ребер, такие как:

  • Если 0 является собственным значением L с k различными собственными векторами, то есть λ1= λ2= λ3= λ4=……=λk=0, это означает, что будет k компонент связности
  • Если граф связен λn›0 и λn — алгебраическая связность G

Двойное разбиение с помощью спектральных методов

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

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

Пример

Рассмотрим граф G

Из этого графика мы можем составить матрицу Лапласа

Из матрицы Лапласа мы можем получить ее собственное значение и собственные векторы

Затем мы выбираем наименьшее собственное значение и заменяем узлы собственными векторами

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

Заключение

Спектральная кластеризация рассматривается как метод уменьшения размеров в обучении без учителя, поскольку он способен воспроизвести то, что на самом деле делает PCA в методах обучения с учителем. Спектральная кластеризация также создает жесткие, неперекрывающиеся кластеры, и лучше всего работает, когда число k не слишком велико (до K = 10).

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

Оставайтесь с нами, и если вам понравилась эта статья, пожалуйста, поставьте 👏!