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

Какой метод кластеризации?

Существует множество различных методов кластеризации, от часто используемой кластеризации k-средних до непараметрических алгоритмов на основе плотности, таких как DBSCAN и OPTICS — просто посмотрите список, предоставленный scikit-learn.

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

Поэтому имеет смысл выбрать набор псевдосамонастраивающихся алгоритмов для автоматизированного тестирования. Одна вещь, которая показалась мне странной, — это явное ограничение на количество кластеров, основанное на входном параметре в функции спектральной кластеризации sklearn.

Спектральная кластеризация — как это работает?

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

† Вместо матрицы смежности можно использовать матрицу сходства, описывающую, насколько похожи две точки в пространстве.

Затем мы вычисляем собственные значения и собственные векторы, используя выбранный нами решатель, и преобразуем входные данные в n-мерное пространство. Теперь мы можем применить ряд методов определения размера кластера, чтобы получить оптимальное число, o, где o < ncluster_input .

Наконец, мы дискретизируем метки, ища матрицу/кластеризацию раздела, которая больше всего напоминает вложение собственного вектора. Для получения дополнительной информации о том, как работает спектральная кластеризация, посмотрите эта ссылка.

Сколько кластеров?

Для определения оптимального количества кластеров мы применяем методологию, описанную Ульрике в его Учебнике по спектральной кластеризации: https://arxiv.org/pdf/0711.0189.pdf

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

  1. Если есть только крошечные числа, все ниже порога 1e-3 мы ищем изменение знака. Это отделяет небольшие числовые значения (~-0) от фактических нулей (+0).
  2. Если существуют значения выше порога, мы ищем наибольшее изменение, используя скользящую разницу:int(argmax(numpy.diff(lambdas))+1.)
  3. В случаях, когда числа однородны (без явных изменений), мы можем просто использовать первое ненулевое значение (аналогично 1).
  4. Наконец, если ничего из вышеперечисленного не существует, мы продолжаем использовать исходный номер кластера и больше его не уменьшаем.

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

n_auto : bool, optional, default=False
   If not False (or zero), an eigenvalue evaluation is undergone to   
   better fit/reduce the maximum number of clusters based on the 
   work in `A Tutorial on Spectral Clustering, 2007 Ulrike von 
   Luxburg 
   http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.165.9323`.

Код

Обновленный код, содержащий мои изменения, можно найти в следующей ветке (в какой-то момент в будущем она будет очищена) :: https://github.com/wolfiex/scikit-learn/tree/spectral_autocluster

Анализ и тестирование

Величайшее изменение

При использовании эвристики собственного разрыва (анализ точки изменения для поиска наибольшего разрыва в собственных значениях) разрыв часто будет очень очевиден в четко разделенных данных и, скорее всего, виден в пределах диагонали упорядоченной матрицы сходства. Здесь мы рассмотрим различные наборы распределений собственных значений, с которыми мы можем столкнуться для набора примеров. Напечатанные значения были округлены до 3 dp, где «-0» означает небольшое число ›0.

Разделение собственного значения

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

Все нули

Однако во многих случаях у нас может быть постоянное изменение во всем или во всех нулях (числа ‹ порог). Когда это происходит, мы можем взять разделение между числовыми значениями и числами с нулевым значением. В случае очень маленьких чисел это происходит между -0 и +0.

Переоснащение

К сожалению, даже автокорректирующие классификаторы страдают от переобучения. В случае большого количества кластеров для небольшой системы мы не можем провести достаточно четкое различие между собственными значениями и результатом с выходом 7, который все еще меньше, чем исходные 20, но не так хорош, как в приведенном выше примере.

Выводы

В заключение мы показали, что мы можем использовать собственные значения решенного лапласиана, чтобы лучше настроить количество меток, назначенных в методе спектральной кластеризации, и что мы можем применить это к реализации в пакете python scikit-learn.

использованная литература