Как хорошо вы разбираетесь в Data Science? Тест на реальные знания от Tproger и «МегаФон»
8 вопросов-задачек по Data Science. Если ответите правильно больше чем на половину, сможете получить предложение от «МегаФона».
Увлекаетесь Data Science и хотите проверить свои знания? Попробуйте пройти наш тест — 8 вопросов-задачек, которые покажут, разбираетесь ли вы в теме. Это не только тест, но и своеобразный этап отбора: если ответите правильно больше чем на половину вопросов, сможете получить предложение от «МегаФона».
Алгоритмы сэмплирования
Сэмплирование (англ. data sampling) — метод корректировки обучающей выборки с целью балансировки распределения классов в исходном наборе данных. Нужно отличать этот метод от сэмплирования в активном обучении для отбора кандидатов и от сэмплирования в статистике [1] для создания подвыборки с сохранением распределения классов.
Неравномерное распределение может быть следующих типов:
- Недостаточное представление класса в независимой переменной;
- Недостаточное представление класса в зависимой переменной.
Многие модели машинного обучения, например, нейронные сети, дают более надежные прогнозы на основе обучения со сбалансированными данными. Однако некоторые аналитические методы, в частности линейная регрессия и логистическая регрессия, не получают дополнительного преимущества.
Когда в обучающем наборе данных доля примеров некоторого класса слишком мала, такие классы называются миноритарными (англ. minority), другие, со слишком большим количеством представителей, — мажоритарными (англ. majority). Подобные тенденции хорошо заметны в кредитном скоринге, в медицине, в директ-маркетинге.
Следует отметить то, что значимость ошибочной классификации может быть разной. Неверная классификация примеров миноритарного класса, как правило, обходится в разы дороже, чем ошибочная классификация примеров мажоритарного класса. Например, при классификации людей, обследованных в больнице, на больных раком (миноритарный класс) и здоровых (мажоритарный класс) лучше будет отправить на дополнительное обследование здоровых пациентов, чем пропустить людей с раком.
Стратегии сэмплирования
- Cубдискретизация (англ. under-sampling) — удаление некоторого количества примеров мажоритарного класса.
- Передискретизации (англ. over-sampling) — увеличение количества примеров миноритарного класса.
- Комбинирование (англ. сombining over- and under-sampling) — последовательное применение субдискретизации и передискретизации.
- Ансамбль сбалансированных наборов (англ. ensemble balanced sets) — использование встроенных методов сэмплирования в процессе построения ансамблей классификаторов.
Также все методы можно разделить на две группы: случайные (недетерминированные) и специальные (детерминированные).
- Случайное сэмплирование (англ. random sampling) — для этого типа сэмплирования существует равная вероятность выбора любого конкретного элемента. Например, выбор 10 чисел в промежутке от 1 до 100. Здесь каждое число имеет равную вероятность быть выбранным.
- Сэплирование с заменой (англ. sampling with replacement) — здесь элемент, который выбирается первым, не должен влиять на вторую или любую другую выборку. Математически, ковариация равна нулю между двумя выборками. Мы должны использовать выборку с заменой, когда у нас большой набор данных. Потому что, если мы используем выборку без замены, то вероятность для каждого предмета, который будет выбран, будет изменяться, и она будет слишком сложной после определенного момента. Выборка с заменой может сказать нам, что чаще встречается в наших данных.
- Сэмплирование без замены (англ. sampling without replacement) — здесь то, что мы выбираем первым, повлияет на второе. Выборка без замены полезна, если набор данных мал. Математически, ковариация между двумя выборками не равна нулю.
Метод Uncertainty Sampling
Идея: выбирать [math]x_i[/math] с наибольшей неопределенностью [math]a(x_i)[/math] .
Задача многоклассовой классификации:
[math]a(x)=\arg\max\limits_
[math]p_k(x), k=1\ldots\left | Y \right |[/math] — ранжированные по убыванию [math]P(y \mid x), y\in Y[/math] .
- Принцип наименьшей достоверности (англ. least confidence):
- Принцип наименьшей разности отступов (англ. margin sampling):
- Принцип максимума энтропии (англ. maximum entropy):
В случае двух классов эти три принципа эквивалентны. В случае многих классов появляются различия.
Примеры алгоритмов
Рис. [math]1[/math] . Случайное удаление примеров мажоритарного класса
Cубдискретизация (удаление примеров мажоритарного класса)
Случайное удаление примеров мажоритарного класса (англ. Random Undersampling)
Это самый простой алгоритм. Рассчитывается число [math]K[/math] – количество мажоритарных примеров, которое необходимо удалить для достижения требуемого уровня соотношения различных классов. Затем случайным образом выбираются K мажоритарных примеров и удаляются. На рис. [math]1[/math] изображены примеры некоторого набора данных в двумерном пространстве признаков до и после использования алгоритма.
Поиск связей Томека (англ. Tomek Links)
Рис. [math]2[/math] . Удаление мажоритарных примеров, участвующих в связях Томека
Пусть примеры [math]E_i[/math] и [math]E_j[/math] принадлежат к различным классам, [math]d(E_i,E_j)[/math] – расстояние между указанными примерами. Пара [math](E_i,E_j)[/math] называется связью Томека, если не найдется ни одного примера [math]E_l[/math] такого, что будет справедлива совокупность неравенств:
[math] \begin d(E_i,E_l)\lt d(E_i,E_j),\\ d(E_j,E_l)\lt d(E_i,E_j) \end [/math]
Согласно данному подходу, все мажоритарные записи, входящие в связи Томека, должны быть удалены из набора данных. Этот способ хорошо удаляет записи, которые можно рассматривать в качестве «зашумляющих». На рис. [math]2[/math] визуально показан набор данных в двумерном пространстве признаков до и после применения стратегии поиска связей Томека.
Правило сосредоточенного ближайшего соседа (англ. Condensed Nearest Neighbor Rule)
Рис. [math]3[/math] . Удаление примеров мажоритарного класса правилом сосредоточенного ближайшего соседа
Пусть [math]L[/math] – исходный набор данных. Из него выбираются все миноритарные примеры и (случайным образом) один мажоритарный. Обозначим это множество как [math]S[/math] . Все примеры из [math]L[/math] классифицируются по правилу одного ближайшего соседа. Записи, получившие ошибочную метку, добавляются во множество [math]S[/math] (рис. [math]3[/math] ). Таким образом, мы будем учить классификатор находить отличие между похожими примерами, но принадлежащими к разным классам.
Односторонний сэмплинг (англ. One-side sampling, one-sided selection)
Главная идея этой стратегии – это последовательное сочетание предыдущих двух, рассмотренных выше. Для этого на первом шаге применяется правило сосредоточенного ближайшего соседа, а на втором – удаляются все мажоритарные примеры, участвующие в связях Томека. Таким образом, удаляются большие «сгустки» мажоритарных примеров, а затем область пространства со скоплением миноритарных очищается от потенциального шума.
Правило «очищающего» соседа (англ. Neighborhood cleaning rule)
Эта стратегия также направлена на то, чтобы удалить те примеры, которые негативно влияют на исход классификации миноритарных классов. Для этого все примеры классифицируются по правилу трех ближайших соседей. Удаляются следующие мажоритарные примеры:
- получившие верную метку класса;
- являющиеся соседями миноритарных примеров, которые были неверно классифицированы.
Дополнительные
- Under-sampling with Cluster Centroids [2] — уменьшает количество примеров мажоритарного класса, заменяя некоторые кластеры примеров мажоритарного класса их представителем (центроидом кластера).
- NearMiss [math](1 \And 2 \And 3)[/math] [3] — удаляет примеры мажоритарного класса, для которых среднее расстояние до ближайших соседей (KNN) миноритарного класса является наименьшим. Также может использоваться расстояние до самых дальних соседей, либо среднее расстояние до всех соседей.
- Edited Nearest Neighbours [4] — удаляет примеры мажоритарного класса, если при классификации методом KNN они определяются как примеры миноритарного класса.
Передискретизации (увеличение числа примеров миноритарного класса)
Дублирование примеров миноритарного класса (англ. Oversampling)
Самый простой метод – это дублирование примеров миноритарного класса. В зависимости от того, какое соотношение классов необходимо, выбирается количество случайных записей для дублирования.
Рис. [math]4[/math] . Искусственно созданные новые примеры миноритарного класса
SMOTE (англ. Synthetic Minority Oversampling Technique)
Этот алгоритм основан на идее генерации некоторого количества искусственных примеров, которые были бы похожи на имеющиеся в миноритарном классе, но при этом не дублировали их. Для создания новой записи находят разность [math]d=X_b–X_a[/math] , где [math]X_a[/math] , [math]X_b[/math] – векторы признаков «соседних» примеров [math]a[/math] и [math]b[/math] из миноритарного класса. Их находят, используя алгоритм ближайшего соседа KNN. В данном случае необходимо и достаточно для примера [math]b[/math] получить набор из [math]k[/math] соседей, из которого в дальнейшем будет выбрана запись [math]b[/math] . Остальные шаги алгоритма KNN не требуются. Далее из [math]d[/math] путем умножения каждого его элемента на случайное число в интервале [math](0, 1)[/math] получают [math]\hat[/math] . Вектор признаков нового примера вычисляется путем сложения [math]X_a[/math] и [math]\hat[/math] . Алгоритм SMOTE позволяет задавать количество записей, которое необходимо искусственно сгенерировать. Степень сходства примеров [math]a[/math] и [math]b[/math] можно регулировать путем изменения числа ближайших соседей [math]k[/math] . На рис. [math]4[/math] схематично изображено то, как в двумерном пространстве признаков могут располагаться искусственно сгенерированные примеры.
В SMOTE (техника избыточной выборки синтетического меньшинства) мы синтезируем элементы для класса меньшинства в непосредственной близости от уже существующих элементов.
from imblearn.over_sampling import SMOTE
smote = SMOTE(ratio=’minority’)
X_sm, y_sm = smote.fit_sample(X, y)
В библиотеке imblearn есть множество других методов как для недостаточной выборки (Cluster Centroids, NearMiss и т.д.), так и для избыточной выборки (ADASYN и bSMOTE).
Рис. [math]5[/math] . Негативное влияние алгоритма SMOTE
ASMO (англ. Adaptive Synthetic Minority Oversampling)
Рис. [math]6[/math] . Основная идея алгоритма ASMO
Алгоритм SMOTE имеет недостаток в том, что «вслепую» увеличивает плотность примерами в области слабо представленного класса (рис. [math]5[/math] ). В случае, если миноритарные примеры равномерно распределены среди мажоритарных и имеют низкую плотность, алгоритм SMOTE только сильнее перемешает классы. В качестве решения данной проблемы был предложен алгоритм адаптивного искусственного увеличения числа примеров миноритарного класса ASMO:
- Если для каждого [math]i[/math] -ого примера миноритарного класса из [math]k[/math] ближайших соседей [math]g, (g≤k)[/math] принадлежит к мажоритарному, то набор данных считается «рассеянным». В этом случае используют алгоритм ASMO, иначе применяют SMOTE (как правило, [math]g[/math] задают равным [math]20[/math] ).
- Используя только примеры миноритарного класса, выделить несколько кластеров (например, алгоритмом [math]\mathrm[/math] -средних).
- Сгенерировать искусственные записи в пределах отдельных кластеров на основе всех классов. Для каждого примера миноритарного класса находят [math]m[/math] ближайших соседей, и на основе них (также как в SMOTE) создаются новые записи.
Такая модификация алгоритма SMOTE делает его более адаптивным к различным наборам данных с несбалансированными классами. Общее представление идеи алгоритма показано на рис. [math]6[/math] .
Дополнительные
- SMOTENC [5] — в отличие от SMOTE, работает с непрерывными признаками у примеров обучающей выборки.
- Borderline-SMOTE [math](1 \And 2)[/math] [6] — в отличие от SMOTE, для создания новых синтетических примеров используются только примеры на границе классов.
- SVM SMOTE — Support Vectors SMOTE [7] — вариант алгоритма SMOTE, который использует алгоритм SVM для обнаружения примеров, рядом с которыми будут создаваться новые синтетические примеры.
Алгоритм Метрополиса — Гастингса
Алгоритм позволяет семплировать любую функцию распределения. Он основан на создании цепи Маркова, то есть на каждом шаге алгоритма новое выбранное значение зависит только от предыдущего.
- Очередная итерация начинается с состояния [math]x^[/math]
- Выбираем [math]x^<\prime>[/math] по распределению [math]q(x^\prime; x^)[/math]
- Вычисляем:
- С вероятностью [math]a(x^<\prime>, x)[/math] ( [math]1[/math] , если [math]a\geq 1[/math] ) [math]x^:=x^<\prime>[/math] , иначе [math]x^:=x^[/math]
Сэмплирование по Гиббсу
Этот алгоритм является частным случаем алгоритма Метрополиса — Гастингса и назван в честь физика Джозайи Гиббса. Он замечателен тем, что для него не требуется явно выраженное совместное распределение, а нужны лишь условные вероятности для каждой переменной, входящей в распределение. Алгоритм на каждом шаге берет одну случайную величину и выбирает её значение при условии фиксированных остальных.
[math]x_^[/math] выбираем по распределению [math]p(x_\mid x_^,\ldots,x_^,x_^,\ldots,x_^)[/math] и повторяем.
Это частный случай алгоритма Метрополиса для распределений [math]q(x^<\prime>; x)=p(x_^<\prime>\mid x_)[/math] , и вероятность принятия каждого сэмпла полается равна [math]1[/math] . Поэтому сэмплирование по Гиббсу сходится, и, так как это такое же случайное блуждание по сути, верна та же квадратичная оценка. В больших размерностях может оказаться эффективнее сэмплить по несколько переменных сразу, а не по одной — например, часто бывает, что у нас двудольный граф из переменных, в которых все переменные из одной доли связаны со всеми переменными из другой доли (ну или со многими), а между собой не связаны. В такой ситуации следует зафиксировать все переменные одной доли и просэмплировать все переменные в другой доле одновременно (это можно понимать буквально — поскольку при такой структуре все переменные одной доли условно независимы при условии другой, их можно сэмплировать независимо и параллельно), потом зафиксировать все переменные второй доли и так далее.Slice sampling
Выборка среза представляет собой тип алгоритма Монте Карло по схеме марковских цепей для выборки псевдослучайных чисел, т.е. для отбора случайных выборок из статистического распределения. Метод основан на наблюдении, что для выборки случайной величины можно равномерно выбирать из области под графиком ее функции плотности.
Slice sampling, в его самой простой форме, равномерно выбирается из-под кривой [math]f(x)[/math] без необходимости отбрасывать какие-либо точки следующими действиями:
- Выберите начальное значение [math]x_[/math] , для которого [math]f(x_)\gt 0[/math]
- Выберите значение [math]y[/math] равномерно между [math]0[/math] и [math]f(x_)[/math]
- Проведите горизонтальную линию через кривую в этой координате [math]y[/math]
- Выберите точку [math](x, y)[/math] на отрезке в пределах кривой
- Повторите с шага [math]2[/math] , используя новое значение [math]x[/math]
Суть здесь заключается в том, что один из способов равномерной выборки точки из произвольной кривой — это сначала нарисовать тонкие горизонтальные срезы одинаковой высоты по всей кривой. Затем мы можем сэмплировать точку внутри кривой путем случайного выбора среза, который находится в точке или ниже кривой в позиции [math]x[/math] на предыдущей итерации, а затем случайным образом выбрать позицию [math]x[/math] где-нибудь вдоль среза. Используя позицию [math]x[/math] из предыдущей итерации алгоритма, в долгосрочной перспективе мы выбираем срезы с вероятностями, пропорциональными длине их сегментов в пределах кривой. Самая сложная часть этого алгоритма — это поиск границ горизонтального среза, который включает в себя инвертирование функции, описывающей распределение, из которого производится выборка. Это особенно проблематично для мультимодальных распределений, где срез может состоять из нескольких прерывистых частей. Часто можно использовать форму выборки отклонения, чтобы преодолеть это, когда мы производим выборку из более крупного среза, который, как известно, включает в себя требуемый рассматриваемый срез, а затем отбрасываем точки за пределами желаемого среза. Этот алгоритм можно использовать для выборки из области под любой кривой, независимо от того, интегрируется ли функция в [math]1[/math] . Фактически, масштабирование функции по константе не влияет на выборочные [math]x[/math] —позиции. Это означает, что алгоритм может использоваться для выборки из распределения, функция плотности вероятности которого известна только с точностью до константы.
Комбинирование
- SMOTE [math]+[/math] Tomek links [8] — сначала выполняет передискретизацию с использованием SMOTE, а потом субдискретизацию используя Tomek Links.
- SMOTE [math]+[/math] ENN [9] — последовательно использует SMOTE и Edited Nearest Neighbours.
Ансамбль сбалансированных наборов
- Easy Ensemble classifier [10] — независимые классификаторы обучаются на случайных подвыборках, из которых постепенно удаляются правильно классифицирующиеся примеры мажоритарных классов.
- Balanced Random Forest [11] — в отличие от классического случайного леса, может работать на несбалансированных данных.
- Balanced Bagging [12] — в отличие от классического бэггинга, имеет дополнительный шаг субдискретизации обучающей подвыборки.
Реализации
Imbalanced-learn — набор инструментов с открытым исходным кодом на Python, целью которого является предоставление широкого спектра методов для решения проблемы несбалансированного набора данных. На рис. [math]7[/math] представлена таблица реализованных в библиотеке методов.
Пример кода для передискретизации набора данных с использованием SMOTE:
from sklearn.datasets import make_classification from sklearn.decomposition import PCA from imblearn.oversampling import SMOTE # Создание датасета X, y = makeclassification (n_classes=2, weights =[0.1, 0.9], n_features=20, n_samples=5000) Применение SMOTE over-sampling sm = SMOTE(ratio=’auto’, kind=’regular’) X_resampled , y_resampled=sm.fit_sample(X, y)
Рис. [math]7[/math] . Методы imbalanced-learn
См. также
- Метрический классификатор и метод ближайших соседей
- Байесовская классификация
- Активное обучение
- Виды ансамблей
Примечания
- ↑Sampling (statistics)
- ↑Show-Jane Yen, Yue-Shi Lee,Cluster-based under-sampling approaches for imbalanced data distributions, Expert Systems with Applications, Volume 36, Issue 3, Part 1, 2009, Pages 5718-5727, ISSN 0957-4174
- ↑ I. Mani, J. Zhang. “kNN approach to unbalanced data distributions: A case study involving information extraction,” In Proceedings of the Workshop on Learning from Imbalanced Data Sets, pp. 1-7, 2003.
- ↑ D. Wilson, “Asymptotic Properties of Nearest Neighbor Rules Using Edited Data,” IEEE Transactions on Systems, Man, and Cybernetrics, vol. 2(3), pp. 408-421, 1972.
- ↑ N. V. Chawla, K. W. Bowyer, L. O. Hall, W. P. Kegelmeyer, “SMOTE: Synthetic minority over-sampling technique,” Journal of Artificial Intelligence Research, vol. 16, pp. 321-357, 2002.
- ↑ H. Han, W.-Y. Wang, B.-H. Mao, “Borderline-SMOTE: A new over-sampling method in imbalanced data sets learning,” In Proceedings of the 1st International Conference on Intelligent Computing, pp. 878-887, 2005.
- ↑ H. M. Nguyen, E. W. Cooper, K. Kamei, “Borderline over-sampling for imbalanced data classification,” In Proceedings of the 5th International Workshop on computational Intelligence and Applications, pp. 24-29, 2009.
- ↑ G. E. A. P. A. Batista, A. L. C. Bazzan, M. C. Monard, “Balancing training data for automated annotation of keywords: A case study,” In Proceedings of the 2nd Brazilian Workshop on Bioinformatics, pp. 10-18, 2003.
- ↑ G. E. A. P. A. Batista, R. C. Prati, M. C. Monard, “A study of the behavior of several methods for balancing machine learning training data,” ACM Sigkdd Explorations Newsletter, vol. 6(1), pp. 20-29, 2004.
- ↑ X.-Y. Liu, J. Wu and Z.-H. Zhou, “Exploratory undersampling for class-imbalance learning,” IEEE Transactions on Systems, Man, and Cybernetics, vol. 39(2), pp. 539-550, 2009.
- ↑ C. Chao, A. Liaw, and L. Breiman. «Using random forest to learn imbalanced data.» University of California, Berkeley 110 (2004): 1-12.
- ↑ Hido, Shohei & Kashima, Hisashi. (2008). Roughly Balanced Bagging for Imbalanced Data. 143-152. 10.1137/1.9781611972788.13.
Источники информации
- Oversampling and undersampling in data analysis
- Различные стратегии сэмплинга в условиях несбалансированности классов
- Lemaître, G. Nogueira, F. Aridas, Ch.K. (2017) Imbalanced-learn: A Python Toolbox to Tackle the Curse of Imbalanced Datasets in Machine Learning, Journal of Machine Learning Research, vol. 18, no. 17, 2017, pp. 1-5.
- Машинное обучение
- Классификация и регрессия
2.3. Кластеризация ¶
Кластеризация неразмеченных данных можно выполнить с помощью модуля sklearn.cluster.
Каждый алгоритм кластеризации имеет два варианта: класс, реализующий fit метод изучения кластеров на данных поезда, и функция, которая, учитывая данные поезда, возвращает массив целочисленных меток, соответствующих различным кластерам. Для класса метки над обучающими данными можно найти в labels_ атрибуте.
Важно отметить, что алгоритмы, реализованные в этом модуле, могут принимать в качестве входных данных различные типы матриц. Все методы принимают стандартные матрицы данных формы . Их можно получить из классов модуля. Для , и можно также ввести матрицы подобия формы . Их можно получить из функций в модуле. (n_samples, n_features)sklearn.feature_extraction AffinityPropagation SpectralClustering DBSCAN(n_samples, n_samples)sklearn.metrics.pairwise
2.3.1. Обзор методов кластеризации
K-средних часто называют алгоритмом Ллойда. В общих чертах алгоритм состоит из трех шагов. На первом этапе выбираются начальные центроиды, а самый простой метод — выбрать $k$ образцы из набора данных $X$. После инициализации K-средних состоит из цикла между двумя другими шагами. Первый шаг присваивает каждой выборке ближайший центроид. На втором этапе создаются новые центроиды, взяв среднее значение всех выборок, назначенных каждому предыдущему центроиду. Вычисляется разница между старым и новым центроидами, и алгоритм повторяет эти последние два шага, пока это значение не станет меньше порогового значения. Другими словами, это повторяется до тех пор, пока центроиды не переместятся значительно.
K-средних эквивалентно алгоритму максимизации ожидания с маленькой, все равной диагональной ковариационной матрицей.
Алгоритм также можно понять через концепцию диаграмм Вороного. Сначала рассчитывается диаграмма Вороного точек с использованием текущих центроидов. Каждый сегмент на диаграмме Вороного становится отдельным кластером. Во-вторых, центроиды обновляются до среднего значения каждого сегмента. Затем алгоритм повторяет это до тех пор, пока не будет выполнен критерий остановки. Обычно алгоритм останавливается, когда относительное уменьшение целевой функции между итерациями меньше заданного значения допуска. В этой реализации дело обстоит иначе: итерация останавливается, когда центроиды перемещаются меньше допуска.
По прошествии достаточного времени K-средние всегда будут сходиться, однако это может быть локальным минимумом. Это сильно зависит от инициализации центроидов. В результате вычисление часто выполняется несколько раз с разными инициализациями центроидов. Одним из способов решения этой проблемы является схема инициализации k-means++, которая была реализована в scikit-learn (используйте init=’k-means++’ параметр). Это инициализирует центроиды (как правило) удаленными друг от друга, что, вероятно, приводит к лучшим результатам, чем случайная инициализация, как показано в справочнике.
K-means++ также может вызываться независимо для выбора начальных значений для других алгоритмов кластеризации, sklearn.cluster.kmeans_plusplus подробности и примеры использования см. В разделе .
Алгоритм поддерживает выборочные веса, которые могут быть заданы параметром sample_weight . Это позволяет присвоить некоторым выборкам больший вес при вычислении центров кластеров и значений инерции. Например, присвоение веса 2 выборке эквивалентно добавлению дубликата этой выборки в набор данных $X$.
Метод K-средних может использоваться для векторного квантования. Это достигается с помощью метода преобразования обученной модели KMeans .
2.3.2.1. Низкоуровневый параллелизм
KMeans преимущества параллелизма на основе OpenMP через Cython. Небольшие порции данных (256 выборок) обрабатываются параллельно, что, кроме того, снижает объем памяти. Дополнительные сведения о том, как контролировать количество потоков, см. В наших заметках о параллелизме .
- Демонстрация предположений k-средних : демонстрация того, когда k-средних работает интуитивно, а когда нет
- Демонстрация кластеризации K-средних на данных рукописных цифр : Кластеризация рукописных цифр
- «K-means ++: преимущества тщательного посева» Артур, Дэвид и Сергей Васильвицкий, Труды восемнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам , Общество промышленной и прикладной математики (2007)
2.3.2.2. Мини-партия K-средних
Это MiniBatchKMeans вариант KMeans алгоритма, который использует мини-пакеты для сокращения времени вычислений, но при этом пытается оптимизировать ту же целевую функцию. Мини-пакеты — это подмножества входных данных, которые выбираются случайным образом на каждой итерации обучения. Эти мини-пакеты резко сокращают объем вычислений, необходимых для схождения к локальному решению. В отличие от других алгоритмов, которые сокращают время сходимости k-средних, мини-пакетные k-средние дают результаты, которые, как правило, лишь немного хуже, чем стандартный алгоритм.
Алгоритм повторяется между двумя основными шагами, аналогично обычным k-средним. На первом этапе $b$ образцы выбираются случайным образом из набора данных, чтобы сформировать мини-пакет. Затем они присваиваются ближайшему центроиду. На втором этапе обновляются центроиды. В отличие от k-средних, это делается для каждой выборки. Для каждой выборки в мини-пакете назначенный центроид обновляется путем взятия среднего потокового значения выборки и всех предыдущих выборок, назначенных этому центроиду. Это приводит к снижению скорости изменения центроида с течением времени. Эти шаги выполняются до тех пор, пока не будет достигнута сходимость или заранее определенное количество итераций.
MiniBatchKMeans сходится быстрее, чем KMeans , но качество результатов снижается. На практике эта разница в качестве может быть довольно небольшой, как показано в примере и цитированной ссылке.
- Сравнение алгоритмов кластеризации K-средних и MiniBatchKMeans : сравнение KMeans и MiniBatchKMeans
- Кластеризация текстовых документов с использованием k-средних : кластеризация документов с использованием разреженных MiniBatchKMeans
- Онлайн обучение словаря частей лиц
- «Кластеризация K-средних в веб-масштабе» Д. Скалли, Труды 19-й международной конференции по всемирной паутине (2010 г.)
2.3.3. Распространения близости (Affinity Propagation)
AffinityPropagation создает кластеры, отправляя сообщения между парами образцов до схождения. Затем набор данных описывается с использованием небольшого количества образцов, которые определяются как наиболее репрезентативные для других образцов. Сообщения, отправляемые между парами, представляют пригодность одного образца быть образцом другого, который обновляется в ответ на значения из других пар. Это обновление происходит итеративно до сходимости, после чего выбираются окончательные образцы и, следовательно, дается окончательная кластеризация.
Метод Распространения близости может быть интересным, поскольку он выбирает количество кластеров на основе предоставленных данных. Для этой цели двумя важными параметрами являются предпочтение , которое контролирует, сколько экземпляров используется, и коэффициент демпфирования, который снижает ответственность и сообщения о доступности, чтобы избежать числовых колебаний при обновлении этих сообщений.
Главный недостаток метода Распространения близости — его сложность. Алгоритм имеет временную сложность порядка $O(N^2 T)$, где $N$ количество образцов и $T$ — количество итераций до сходимости. Далее, сложность памяти порядка $O(N^2)$ если используется плотная матрица подобия, но может быть сокращена, если используется разреженная матрица подобия. Это делает метод Распространения близости наиболее подходящим для наборов данных малого и среднего размера.
- Демонстрация алгоритма кластеризации распространения близости: метода Распространения близости на синтетических наборах данных 2D с 3 классами.
- Визуализация структуры фондового рынка Финансовые временные ряды метода Распространения близости для поиска групп компаний
Описание алгоритма: сообщения, отправляемые между точками, относятся к одной из двух категорий. Во-первых, это ответственность $r(i,k)$, которое является накопленным свидетельством того, что образец $k$ должен быть образцом для образца $i$. Второе — доступность $a(i,k)$ что является накопленным свидетельством того, что образец $i$ следует выбрать образец $k$ быть его образцом, и учитывает значения для всех других образцов, которые $k$ должен быть образцом. Таким образом, образцы выбираются по образцам, если они (1) достаточно похожи на многие образцы и (2) выбираются многими образцами, чтобы быть репрезентативными.
Более формально ответственность за образец $k$ быть образцом образца i дан кем-то: $$r(i, k) \leftarrow s(i, k) — max [ a(i, k’) + s(i, k’) \forall k’ \neq k ]$$
Где $s(i,k)$ сходство между образцами $i$ а также $k$. Наличие образца $k$ быть образцом образца $i$ дан кем-то: $$a(i, k) \leftarrow min [0, r(k, k) + \sum_>
Начнем с того, что все значения для $r$ и $a$ aустановлены в ноль, и расчет каждой итерации повторяется до сходимости. Как обсуждалось выше, чтобы избежать числовых колебаний при обновлении сообщений, коэффициент демпфирования $\lambda$ вводится в итерационный процесс: $$r_(i, k) = \lambda\cdot r_(i, k) + (1-\lambda)\cdot r_(i, k)$$ $$a_(i, k) = \lambda\cdot a_(i, k) + (1-\lambda)\cdot a_(i, k)$$
где $t$ указывает время итерации.
2.3.4. Средний сдвиг
MeanShift кластеризация направлена на обнаружение капель в образцах с плавной плотностью. Это алгоритм на основе центроидов, который работает, обновляя кандидатов в центроиды, чтобы они были средними точками в данном регионе. Затем эти кандидаты фильтруются на этапе постобработки, чтобы исключить почти дубликаты и сформировать окончательный набор центроидов.
Учитывая центроид кандидата $x_i$ для итерации $t$, кандидат обновляется в соответствии со следующим уравнением: $$x_i^ = m(x_i^t)$$
Где $N(x_i)$ это соседство образцов на заданном расстоянии вокруг $x_i$ а также $m$ — вектор среднего сдвига, который вычисляется для каждого центроида, который указывает на область максимального увеличения плотности точек. Это вычисляется с использованием следующего уравнения, эффективно обновляющего центроид до среднего значения выборок в его окрестности: $$m(x_i) = \fracK(x_j — x_i)x_j>K(x_j — x_i)>$$
Алгоритм автоматически устанавливает количество кластеров, вместо того, чтобы полагаться на параметр bandwidth , который определяет размер области для поиска. Этот параметр можно установить вручную, но можно оценить с помощью предоставленной estimate_bandwidth функции, которая вызывается, если полоса пропускания не задана.
Алгоритм не отличается высокой масштабируемостью, так как он требует многократного поиска ближайшего соседа во время выполнения алгоритма. Алгоритм гарантированно сходится, однако алгоритм прекратит итерацию, когда изменение центроидов будет небольшим.
Маркировка нового образца выполняется путем нахождения ближайшего центроида для данного образца.
- Демонстрация алгоритма кластеризации среднего сдвига: кластеризация среднего сдвига на синтетических наборах данных 2D с 3 классами.
- «Средний сдвиг: надежный подход к анализу пространства признаков». Д. Команичиу и П. Меер, IEEE Transactions on Pattern Analysis and Machine Intelligence (2002)
2.3.5. Спектральная кластеризация
SpectralClustering выполняет низкоразмерное встраивание матрицы аффинности между выборками с последующей кластеризацией, например, с помощью K-средних, компонентов собственных векторов в низкоразмерном пространстве. Это особенно эффективно с точки зрения вычислений, если матрица аффинности является разреженной, а amg решатель используется для проблемы собственных значений (обратите внимание, amg что решающая программа требует, чтобы был установлен модуль pyamg ).
Текущая версия SpectralClustering требует, чтобы количество кластеров было указано заранее. Это хорошо работает для небольшого количества кластеров, но не рекомендуется для многих кластеров.
Для двух кластеров SpectralClustering решает выпуклую релаксацию проблемы нормализованных разрезов на графе подобия: разрезание графа пополам так, чтобы вес разрезаемых рёбер был мал по сравнению с весами рёбер внутри каждого кластера. Этот критерий особенно интересен при работе с изображениями, где вершинами графа являются пиксели, а веса ребер графа подобия вычисляются с использованием функции градиента изображения.
Преобразование расстояния в хорошее сходство
Обратите внимание, что если значения вашей матрицы подобия плохо распределены, например, с отрицательными значениями или с матрицей расстояний, а не с подобием, спектральная проблема будет сингулярной, а проблема неразрешима. В этом случае рекомендуется применить преобразование к элементам матрицы. Например, в случае матрицы расстояний со знаком обычно применяется тепловое ядро:
similarity = np.exp(-beta * distance / distance.std()) См. Примеры такого приложения.
- Спектральная кластеризация для сегментации изображения : сегментирование объектов на шумном фоне с использованием спектральной кластеризации.
- Сегментирование изображения греческих монет по регионам : спектральная кластеризация для разделения изображения монет по регионам.
2.3.5.1. Различные стратегии присвоения меток
Могут использоваться различные стратегии присвоения меток, соответствующие assign_labels параметру SpectralClustering . «kmeans» стратегия может соответствовать более тонким деталям, но может быть нестабильной. В частности, если вы не контролируете random_state , он может не воспроизводиться от запуска к запуску, так как это зависит от случайной инициализации. Альтернативная «discretize» стратегия воспроизводима на 100%, но имеет тенденцию создавать участки довольно ровной и геометрической формы.
2.3.5.2. Графики спектральной кластеризации
Спектральная кластеризация также может использоваться для разбиения графов через их спектральные вложения. В этом случае матрица аффинности является матрицей смежности графа, а SpectralClustering инициализируется с помощью affinity=’precomputed’ :
>>> from sklearn.cluster import SpectralClustering >>> sc = SpectralClustering(3, affinity='precomputed', n_init=100, . assign_labels='discretize') >>> sc.fit_predict(adjacency_matrix)
- «Учебное пособие по спектральной кластеризации» Ульрике фон Люксбург, 2007 г.
- «Нормализованные разрезы и сегментация изображения» Джианбо Ши, Джитендра Малик, 2000 г.
- «Случайный взгляд на спектральную сегментацию» Марина Мейла, Цзяньбо Ши, 2001
- «О спектральной кластеризации: анализ и алгоритм» Эндрю Й. Нг, Майкл И. Джордан, Яир Вайс, 2001 г.
- «Предварительно обусловленная спектральная кластеризация для задачи потокового графа стохастического разбиения блоков» Давид Жужунашвили, Андрей Князев
2.3.6. Иерархическая кластеризация
Иерархическая кластеризация — это общее семейство алгоритмов кластеризации, которые создают вложенные кластеры путем их последовательного слияния или разделения. Эта иерархия кластеров представлена в виде дерева (или дендрограммы). Корень дерева — это уникальный кластер, который собирает все образцы, а листья — это кластеры только с одним образцом. См. Страницу в Википедии для получения более подробной информации.
В AgglomerativeClustering объекте выполняет иерархическую кластеризацию с использованием подхода снизу вверх: каждый начинает наблюдения в своем собственном кластере, и кластеры последовательно объединены вместе. Критерии связывания определяют метрику, используемую для стратегии слияния:
- Ward минимизирует сумму квадратов разностей во всех кластерах. Это подход с минимизацией дисперсии, и в этом смысле он аналогичен целевой функции k-средних, но решается с помощью агломеративного иерархического подхода.
- Максимальное (Maximum) или полное связывание (complete linkage) сводит к минимуму максимальное расстояние между наблюдениями пар кластеров.
- Среднее связывание (Average linkage) минимизирует среднее расстояние между всеми наблюдениями пар кластеров.
- Одиночная связь (Single linkage) минимизирует расстояние между ближайшими наблюдениями пар кластеров.
AgglomerativeClustering может также масштабироваться до большого количества выборок, когда он используется вместе с матрицей связности, но требует больших вычислительных затрат, когда между выборками не добавляются ограничения связности: он рассматривает на каждом шаге все возможные слияния.
В FeatureAgglomeration использует агломерационную кластеризацию группироваться функции , которые очень похоже, тем самым уменьшая количество функций. Это инструмент уменьшения размерности, см. « Уменьшение размерности без учителя» .
2.3.6.1. Различные типы связи: Ward, полный, средний и одиночный связь
AgglomerativeClustering поддерживает стратегии Ward, одиночного, среднего и полного связывания.
Агломеративный кластер ведет себя по принципу «богатый становится богатее», что приводит к неравномерному размеру кластера. В этом отношении одинарная связь — худшая стратегия, и Ward дает самые обычные размеры. Однако сродство (или расстояние, используемое при кластеризации) нельзя изменять с помощью Уорда, поэтому для неевклидовых показателей хорошей альтернативой является среднее связывание. Одиночная связь, хотя и не устойчива к зашумленным данным, может быть вычислена очень эффективно и поэтому может быть полезна для обеспечения иерархической кластеризации больших наборов данных. Одиночная связь также может хорошо работать с неглобулярными данными.
- Различная агломеративная кластеризация по двумерному встраиванию цифр : изучение различных стратегий связывания в реальном наборе данных.
2.3.6.2. Визуализация кластерной иерархии
Можно визуализировать дерево, представляющее иерархическое слияние кластеров, в виде дендрограммы. Визуальный осмотр часто может быть полезен для понимания структуры данных, особенно в случае небольших размеров выборки.
2.3.6.3. Добавление ограничений связи
Интересным аспектом AgglomerativeClustering является то, что к этому алгоритму могут быть добавлены ограничения связности (только соседние кластеры могут быть объединены вместе) через матрицу связности, которая определяет для каждой выборки соседние выборки, следующие заданной структуре данных. Например, в приведенном ниже примере швейцарского рулона ограничения связности запрещают объединение точек, которые не являются смежными на швейцарском рулоне, и, таким образом, избегают образования кластеров, которые проходят через перекрывающиеся складки рулона.
Эти ограничения полезны для наложения определенной локальной структуры, но они также ускоряют алгоритм, особенно когда количество выборок велико.
Ограничения связности накладываются через матрицу связности: scipy разреженную матрицу, которая имеет элементы только на пересечении строки и столбца с индексами набора данных, которые должны быть связаны. Эта матрица может быть построена из априорной информации: например, вы можете захотеть сгруппировать веб-страницы, объединяя только страницы со ссылкой, указывающей одну на другую. Это также можно узнать из данных, например, используя sklearn.neighbors.kneighbors_graph для ограничения слияния до ближайших соседей, как в этом примере , или с помощью, sklearn.feature_extraction.image.grid_to_graph чтобы разрешить слияние только соседних пикселей на изображении, как в примере с монетой.
- Демонстрация структурированной иерархической кластеризации Варда на изображении монет : Кластеризация Варда для разделения изображения монет на регионы.
- Иерархическая кластеризация: структурированная и неструктурированная палата : пример алгоритма Уорда в швейцарской системе, сравнение структурированных подходов и неструктурированных подходов.
- Агломерация признаков против одномерного выбора: пример уменьшения размерности с агломерацией признаков на основе иерархической кластеризации Уорда.
- Агломеративная кластеризация со структурой и без нее
Предупреждение Ограничения по подключению с одиночным, средним и полным подключением
Ограничения связности и одиночная, полная или средняя связь могут усилить аспект агломеративной кластеризации «богатый становится еще богаче», особенно если они построены на sklearn.neighbors.kneighbors_graph . В пределе небольшого числа кластеров они имеют тенденцию давать несколько макроскопически занятых кластеров и почти пустые. (см. обсуждение в разделе «Агломеративная кластеризация со структурой и без нее» ). Одиночная связь — самый хрупкий вариант связи в этом вопросе.
2.3.6.4. Варьируя метрику
Одиночная, средняя и полная связь может использоваться с различными расстояниями (или сходствами), в частности евклидовым расстоянием ( l2 ), манхэттенским расстоянием (или Cityblock, или l1 ), косинусным расстоянием или любой предварительно вычисленной матрицей аффинности.
- Расстояние l1 часто хорошо для разреженных функций или разреженного шума: то есть многие из функций равны нулю, как при интеллектуальном анализе текста с использованием вхождений редких слов.
- косинусное расстояние интересно тем, что оно инвариантно к глобальному масштабированию сигнала.
Рекомендации по выбору метрики — использовать метрику, которая максимизирует расстояние между выборками в разных классах и минимизирует его внутри каждого класса.
2.3.7. DBSCAN
Алгоритм DBSCAN рассматривает кластеры , как участки высокой плотности , разделенных районах с низкой плотностью. Из-за этого довольно общего представления кластеры, обнаруженные с помощью DBSCAN, могут иметь любую форму, в отличие от k-средних, которое предполагает, что кластеры имеют выпуклую форму. Центральным компонентом DBSCAN является концепция образцов керна , то есть образцов, находящихся в областях с высокой плотностью. Таким образом, кластер представляет собой набор образцов керна, каждый из которых находится близко друг к другу (измеряется с помощью некоторой меры расстояния), и набор образцов, не относящихся к керну, которые близки к образцу керна (но сами не являются образцами керна). В алгоритме есть два параметра, min_samples и eps , которые формально определяют, что мы имеем в виду, когда говорим «плотный» . Выше min_samples или ниже eps указывают на более высокую плотность, необходимую для формирования кластера.
Более формально мы определяем образец керна как образец в наборе данных, так что существуют min_samples другие образцы на расстоянии eps , которые определены как соседи образца керна. Это говорит нам о том, что основной образец находится в плотной области векторного пространства. Кластер — это набор образцов керна, который можно построить путем рекурсивного взятия образца керна, поиска всех его соседей, которые являются образцами керна, поиска всех их соседей, которые являются образцами керна, и т. Кластер также имеет набор неосновных выборок, которые представляют собой выборки, которые являются соседями керновой выборки в кластере, но сами не являются основными выборками. Интуитивно эти образцы находятся на периферии кластера.
Любой образец керна по определению является частью кластера. Любая выборка, не являющаяся образцом керна и находящаяся по крайней мере eps на расстоянии от любой выборки керна, считается алгоритмом выбросом.
Хотя параметр в min_samples первую очередь контролирует устойчивость алгоритма к шуму (на зашумленных и больших наборах данных может быть желательно увеличить этот параметр), параметр eps имеет решающее значение для правильного выбора для набора данных и функции расстояния и обычно не может быть оставлен на значение по умолчанию. Он контролирует локальное окружение точек. Если выбран слишком маленький размер, большая часть данных вообще не будет кластеризована (и помечена как -1 для «шума»). Если выбран слишком большой, близкие кластеры будут объединены в один кластер, и в конечном итоге весь набор данных будет возвращен как единый кластер. Некоторые эвристики для выбора этого параметра обсуждались в литературе, например, на основе перегиба на графике расстояний до ближайших соседей (как обсуждается в ссылках ниже).
На рисунке ниже цвет указывает на принадлежность к кластеру, а большие кружки обозначают образцы керна, найденные алгоритмом. Меньшие кружки — это неосновные образцы, которые все еще являются частью кластера. Более того, выбросы обозначены ниже черными точками.
Алгоритм DBSCAN является детерминированным, всегда генерируя одни и те же кластеры, когда им предоставляются одни и те же данные в одном порядке. Однако результаты могут отличаться, если данные предоставляются в другом порядке. Во-первых, даже если основные образцы всегда будут назначаться одним и тем же кластерам, метки этих кластеров будут зависеть от порядка, в котором эти образцы встречаются в данных. Во-вторых, что более важно, кластеры, которым назначены неосновные выборки, могут различаться в зависимости от порядка данных. Это может произойти, если образец неосновного керна находится на расстоянии меньше, чем eps два образца керна в разных кластерах. Согласно треугольному неравенству эти два образца керна должны быть дальше, чем eps друг от друга, иначе они были бы в одном кластере. Неосновная выборка назначается тому кластеру, который сгенерирован первым при передаче данных, поэтому результаты будут зависеть от порядка данных.
Текущая реализация использует шаровые деревья и kd-деревья для определения окрестности точек, что позволяет избежать вычисления полной матрицы расстояний (как это было сделано в версиях scikit-learn до 0.14). Сохранена возможность использования пользовательских метрик; подробности см NearestNeighbors .
Потребление памяти для больших размеров выборки
Эта реализация по умолчанию неэффективна с точки зрения памяти, поскольку она строит полную матрицу попарного сходства в случае, когда нельзя использовать kd-деревья или шаровые деревья (например, с разреженными матрицами). Эта матрица будет потреблять $n^2$ плавает. Вот несколько способов обойти это:
- Используйте кластеризацию OPTICS вместе с параметром cluster_method = ‘dbscan’. Кластеризация OPTICS также вычисляет полную попарную матрицу, но сохраняет в памяти только одну строку (сложность памяти n).
- График окрестностей с разреженным радиусом (где предполагается, что отсутствующие записи находятся вне eps) можно предварительно вычислить эффективным с точки зрения памяти способом, и dbscan можно обработать с помощью metric=’precomputed’ . Смотрите sklearn.neighbors.NearestNeighbors.radius_neighbors_graph .
- Набор данных можно сжать, удалив точные дубликаты, если они встречаются в ваших данных, или используя BIRCH. Тогда у вас будет относительно небольшое количество представителей для большого количества точек. Затем вы можете sample_weight указать при установке DBSCAN.
- «Алгоритм на основе плотности для обнаружения кластеров в больших пространственных базах данных с шумом» Эстер, М., Х. П. Кригель, Дж. Сандер и X. Сюй, в материалах 2-й Международной конференции по открытию знаний и интеллектуальному анализу данных, Портленд, штат Орегон , AAAI Press, стр. 226–231. 1996 г.
- «Новый взгляд на DBSCAN: почему и как вы должны (по-прежнему) использовать DBSCAN. Шуберт, Э., Сандер, Дж., Эстер, М., Кригель, HP, и Сюй, X. (2017). В транзакциях ACM в системах баз данных (TODS), 42 (3), 19.
2.3.8. ОПТИКА
В OPTICS акции алгоритма много общих с DBSCAN алгоритмом, и можно рассматривать как обобщение DBSCAN, что расслабляет eps требование от одного значения до диапазона значений. Ключевое различие между DBSCAN и OPTICS заключается в том, что алгоритм OPTICS строит граф достижимости , который назначает каждой выборке reachability_ расстояние и точку в ordering_ атрибуте кластера ; эти два атрибута назначаются при подборе модели и используются для определения принадлежности к кластеру. Если OPTICS запускается со значением по умолчанию inf, установленным для max_eps , то извлечение кластера в стиле DBSCAN может выполняться повторно за линейное время для любого заданного eps значения с использованием этого cluster_optics_dbscan метода. Параметр max_eps более низкое значение приведет к сокращению времени выполнения, и его можно рассматривать как максимальный радиус окрестности от каждой точки для поиска других потенциальных достижимых точек.
Расстояния достижимости, генерируемые OPTICS, позволяют извлекать кластеры с переменной плотностью в пределах одного набора данных. Как показано на приведенном выше графике, объединение расстояний достижимости и набора данных ordering_ дает график достижимости , где плотность точек представлена на оси Y, а точки упорядочены таким образом, что соседние точки являются смежными. «Вырезание» графика достижимости по одному значению дает результаты, подобные DBSCAN; все точки над «вырезом» классифицируются как шум, и каждый раз, когда есть перерыв при чтении слева направо, означает новый кластер. При извлечении кластеров по умолчанию с помощью OPTICS анализируются крутые уклоны на графике, чтобы найти кластеры, и пользователь может определить, что считается крутым уклоном, используя параметр xi . Существуют также другие возможности для анализа на самом графике, такие как создание иерархических представлений данных с помощью дендрограмм графика достижимости, а иерархия кластеров, обнаруженных алгоритмом, может быть доступна через cluster_hierarchy_ параметр. Приведенный выше график имеет цветовую кодировку, поэтому цвета кластеров в плоском пространстве соответствуют кластерам линейных сегментов на графике достижимости. Обратите внимание, что синий и красный кластеры находятся рядом на графике достижимости и могут быть иерархически представлены как дочерние элементы более крупного родительского кластера.
Сравнение с DBSCAN
Результаты cluster_optics_dbscan метода OPTICS и DBSCAN очень похожи, но не всегда идентичны; в частности, маркировка периферийных и шумовых точек. Отчасти это связано с тем, что первые образцы каждой плотной области, обработанной OPTICS, имеют большое значение достижимости, будучи близкими к другим точкам в своей области, и поэтому иногда будут помечены как шум, а не периферия. Это влияет на соседние точки, когда они рассматриваются как кандидаты на то, чтобы их пометить как периферию или как шум.
Обратите внимание, что для любого отдельного значения eps DBSCAN будет иметь более короткое время выполнения, чем OPTICS; однако для повторных запусков с разными eps значениями один запуск OPTICS может потребовать меньше совокупного времени выполнения, чем DBSCAN. Также важно отметить , что выход ОПТИКА» близок к DBSCAN, только если eps и max_eps близки.
Деревья пространственной индексации используются, чтобы избежать вычисления полной матрицы расстояний и обеспечить эффективное использование памяти для больших наборов выборок. С помощью metric ключевого слова можно указать различные метрики расстояния .
Для больших наборов данных аналогичные (но не идентичные) результаты можно получить с помощью HDBSCAN. Реализация HDBSCAN является многопоточной и имеет лучшую алгоритмическую сложность во время выполнения, чем OPTICS, за счет худшего масштабирования памяти. Для очень больших наборов данных, которые исчерпывают системную память с помощью HDBSCAN, OPTICS будет поддерживатьn (в отличие от $n^2$) масштабирование памяти; тем не менее, max_eps для получения решения в разумные сроки, вероятно, потребуется настройка параметра.
- «ОПТИКА: точки упорядочивания для определения структуры кластеризации». Анкерст, Михаэль, Маркус М. Бройниг, Ханс-Петер Кригель и Йорг Зандер. В ACM Sigmod Record, vol. 28, вып. 2. С. 49-60. ACM, 1999.
2.3.9. BIRCH (сбалансированное итеративное сокращение и кластеризация с использованием иерархий — balanced iterative reducing and clustering using hierarchies)
Для Birch заданных данных он строит дерево, называемое деревом функций кластеризации (CFT). Данные по существу сжимаются с потерями до набора узлов Clustering Feature (CF Nodes). Узлы CF имеют ряд подкластеров, называемых подкластерами функций кластеризации (подкластеры CF), и эти подкластеры CF, расположенные в нетерминальных узлах CF, могут иметь узлы CF в качестве дочерних.
Подкластеры CF содержат необходимую информацию для кластеризации, что избавляет от необходимости хранить все входные данные в памяти. Эта информация включает:
- Количество образцов в подкластере.
- Линейная сумма — n-мерный вектор, содержащий сумму всех выборок.
- Squared Sum — сумма квадратов нормы L2 всех выборок.
- Центроиды — чтобы избежать пересчета линейной суммы / n_samples.
- Квадратная норма центроидов.
Алгоритм BIRCH имеет два параметра: порог и коэффициент ветвления. Фактор ветвления ограничивает количество подкластеров в узле, а порог ограничивает расстояние между входящей выборкой и существующими подкластерами.
Этот алгоритм можно рассматривать как экземпляр или метод сокращения данных, поскольку он сокращает входные данные до набора подкластеров, которые получаются непосредственно из конечных точек CFT. Эти сокращенные данные могут быть дополнительно обработаны путем подачи их в глобальный кластеризатор. Этот глобальный кластеризатор может быть установлен с помощью n_clusters . Если n_clusters установлено значение None, подкластеры из листьев считываются напрямую, в противном случае шаг глобальной кластеризации помечает эти подкластеры в глобальные кластеры (метки), а выборки сопоставляются с глобальной меткой ближайшего подкластера.
Описание алгоритма:
- Новый образец вставляется в корень дерева CF, который является узлом CF. Затем он объединяется с подкластером корня, который имеет наименьший радиус после объединения, ограниченный пороговыми условиями и условиями фактора ветвления. Если у подкластера есть дочерний узел, то это повторяется до тех пор, пока он не достигнет листа. После нахождения ближайшего подкластера в листе свойства этого подкластера и родительских подкластеров рекурсивно обновляются.
- Если радиус подкластера, полученного путем слияния новой выборки и ближайшего подкластера, больше квадрата порога, и если количество подкластеров больше, чем коэффициент ветвления, то для этой новой выборки временно выделяется пространство. Берутся два самых дальних подкластера, и подкластеры делятся на две группы на основе расстояния между этими подкластерами.
- Если у этого разбитого узла есть родительский подкластер и есть место для нового подкластера, то родительский подкластер разбивается на два. Если места нет, то этот узел снова делится на две части, и процесс продолжается рекурсивно, пока не достигнет корня.
BIRCH или MiniBatchKMeans?
- BIRCH не очень хорошо масштабируется для данных большого размера. Как правило, если n_features оно больше двадцати, лучше использовать MiniBatchKMeans.
- Если количество экземпляров данных необходимо уменьшить или если требуется большое количество подкластеров в качестве этапа предварительной обработки или иным образом, BIRCH более полезен, чем MiniBatchKMeans.
Как использовать partial_fit?
Чтобы избежать вычисления глобальной кластеризации, при каждом обращении partial_fit пользователя рекомендуется
- Установить n_clusters=None изначально
- Обучите все данные несколькими вызовами partial_fit.
- Установите n_clusters необходимое значение с помощью brc.set_params(n_clusters=n_clusters .
- Вызов, partial_fit наконец, без аргументов, т.е. brc.partial_fit() который выполняет глобальную кластеризацию.
- Тиан Чжан, Рагху Рамакришнан, Марон Ливни БЕРЕЗА: эффективный метод кластеризации данных для больших баз данных. https://www.cs.sfu.ca/CourseCentral/459/han/papers/zhang96.pdf
- Роберто Пердиши JBirch — Java-реализация алгоритма кластеризации BIRCH https://code.google.com/archive/p/jbirch
2.3.10. Оценка эффективности кластеризации
Оценка производительности алгоритма кластеризации не так тривиальна, как подсчет количества ошибок или точности и отзыва контролируемого алгоритма классификации. В частности, любая метрика оценки должна учитывать не абсолютные значения меток кластера, а, скорее, если эта кластеризация определяет разделения данных, аналогичные некоторому основному набору истинных классов или удовлетворяющему некоторому предположению, так что члены, принадлежащие к одному классу, более похожи чем члены разных классов в соответствии с некоторой метрикой сходства.
2.3.10.1. Индекс Rand
Учитывая знания о назначениях базовых классов истинности labels_true и назначениях нашим алгоритмом кластеризации одних и тех же выборок labels_pred , (скорректированный или нескорректированный) индекс Рэнда — это функция, которая измеряет сходство двух назначений, игнорируя перестановки:
>>> from sklearn import metrics >>> labels_true = [0, 0, 0, 1, 1, 1] >>> labels_pred = [0, 0, 1, 1, 2, 2] >>> metrics.rand_score(labels_true, labels_pred) 0.66.
Индекс Rand не гарантирует получение значения, близкого к 0,0 при случайной маркировке. Скорректированный индекс Rand вносит поправку на случайность и дает такую основу.
>>> metrics.adjusted_rand_score(labels_true, labels_pred) 0.24.
Как и в случае со всеми метриками кластеризации, можно переставить 0 и 1 в предсказанных метках, переименовать 2 в 3 и получить ту же оценку:
>>> labels_pred = [1, 1, 0, 0, 3, 3] >>> metrics.rand_score(labels_true, labels_pred) 0.66. >>> metrics.adjusted_rand_score(labels_true, labels_pred) 0.24.
Более того, оба rand_score adjusted_rand_score они симметричны : замена аргумента не меняет оценок. Таким образом, их можно использовать в качестве критериев консенсуса:
>>> metrics.rand_score(labels_pred, labels_true) 0.66. >>> metrics.adjusted_rand_score(labels_pred, labels_true) 0.24.
Идеальная маркировка оценивается в 1,0:
>>> labels_pred = labels_true[:] >>> metrics.rand_score(labels_true, labels_pred) 1.0 >>> metrics.adjusted_rand_score(labels_true, labels_pred) 1.0
Плохо согласованные ярлыки (например, независимые ярлыки) имеют более низкие оценки, а для скорректированного индекса Rand оценка будет отрицательной или близкой к нулю. Однако для нескорректированного индекса Rand оценка, хотя и ниже, не обязательно будет близка к нулю:
>>> labels_true = [0, 0, 0, 0, 0, 0, 1, 1] >>> labels_pred = [0, 1, 2, 3, 4, 5, 5, 6] >>> metrics.rand_score(labels_true, labels_pred) 0.39. >>> metrics.adjusted_rand_score(labels_true, labels_pred) -0.07.
2.3.10.1.1. Преимущества
- Интерпретируемость : нескорректированный индекс Рэнда пропорционален количеству пар выборок, метки которых одинаковы в обоих labels_pred и / labels_true или различаются в обоих.
- Случайные (единообразные) присвоения меток имеют скорректированный балл индекса Rand, близкий к 0,0 для любого значения n_clusters и n_samples (что не относится, например, к нескорректированному индексу Rand или V-мере).
- Ограниченный диапазон : более низкие значения указывают на разные маркировки, аналогичные кластеры имеют высокий (скорректированный или нескорректированный) индекс Rand, 1,0 — это оценка идеального соответствия. Диапазон оценок составляет [0, 1] для нескорректированного индекса Rand и [-1, 1] для скорректированного индекса Rand.
- Не делается никаких предположений о структуре кластера: (скорректированный или нескорректированный) индекс Rand может использоваться для сравнения всех видов алгоритмов кластеризации и может использоваться для сравнения алгоритмов кластеризации, таких как k-средних, который предполагает изотропные формы капли с результатами спектрального анализа. алгоритмы кластеризации, которые могут найти кластер со «сложенными» формами.
2.3.10.1.2. Недостатки
- Вопреки инерции, (скорректированный или нескорректированный) индекс Рэнда требует знания основных классов истинности, что почти никогда не доступно на практике или требует ручного назначения аннотаторами-людьми (как в условиях контролируемого обучения). Однако (скорректированный или нескорректированный) индекс Rand также может быть полезен в чисто неконтролируемой настройке в качестве строительного блока для консенсусного индекса, который может использоваться для выбора модели кластеризации (TODO).
- Нескорректированный индекс Rand часто близко к 1,0 , даже если самим кластеризациям существенно различаются. Это можно понять, интерпретируя индекс Рэнда как точность маркировки пар элементов, полученную в результате кластеризации: на практике часто существует большинство пар элементов, которым присваивается different метка пары как при прогнозируемой, так и при базовой кластеризации истинности, что приводит к высокой доля парных меток, которые согласны, что впоследствии приводит к высокой оценке.
- Поправка на случайность при оценке производительности кластеризации : анализ влияния размера набора данных на значение показателей кластеризации для случайных назначений.
2.3.10.1.3. Математическая постановка
Если C — это наземное присвоение класса истинности, а K — кластеризация, давайте определим $a$ и $b$ в виде:
- $a$, количество пар элементов, которые находятся в одном наборе в C и в одном наборе в K
- $b$, количество пар элементов, которые находятся в разных наборах в C и в разных наборах в K
Затем нескорректированный индекс Рэнда рассчитывается следующим образом: $$\text = \frac>>$$
где $C_2^>$ — общее количество возможных пар в наборе данных. Не имеет значения, выполняется ли расчет для упорядоченных пар или неупорядоченных пар, если расчет выполняется последовательно.
Однако индекс Rand не гарантирует, что случайные присвоения меток получат значение, близкое к нулю (особенно, если количество кластеров имеет тот же порядок величины, что и количество выборок).
Чтобы противостоять этому эффекту, мы можем дисконтировать ожидаемый RI. $E[\text]$ случайных маркировок путем определения скорректированного индекса Rand следующим образом: $$\text = \frac <\text— E[\text]><\max(\text) — E[\text]>$$
- Сравнение разделов Л. Хуберт и П. Араби, Журнал классификации 1985 г.
- Свойства скорректированного индекса Рэнда Хьюберта- Араби Д. Стейнли, Психологические методы, 2004 г.
- Запись в Википедии для индекса Rand
- Запись в Википедии о скорректированном индексе Рэнда
2.3.10.2. Оценки на основе взаимной информации
Учитывая знания о назначениях базовых классов истинности labels_true и назначениях нашим алгоритмом кластеризации одних и тех же выборок labels_pred , взаимная информация — это функция, которая измеряет согласованность двух назначений, игнорируя перестановки. Доступны две различные нормализованные версии этой меры: нормализованная взаимная информация (NMI) и скорректированная взаимная информация (AMI) . NMI часто используется в литературе, в то время как AMI был предложен совсем недавно и нормируется на случайность :
>>> from sklearn import metrics >>> labels_true = [0, 0, 0, 1, 1, 1] >>> labels_pred = [0, 0, 1, 1, 2, 2] >>> metrics.adjusted_mutual_info_score(labels_true, labels_pred) 0.22504.
Можно переставить 0 и 1 в предсказанных метках, переименовать 2 в 3 и получить тот же результат:
>>> labels_pred = [1, 1, 0, 0, 3, 3] >>> metrics.adjusted_mutual_info_score(labels_true, labels_pred) 0.22504.
Все, mutual_info_score , adjusted_mutual_info_score и normalized_mutual_info_score является симметричным: замена аргумента не меняет рейтинг. Таким образом, их можно использовать в качестве меры консенсуса :
>>> metrics.adjusted_mutual_info_score(labels_pred, labels_true) 0.22504.
Идеальная маркировка оценивается в 1,0:
>>> labels_pred = labels_true[:] >>> metrics.adjusted_mutual_info_score(labels_true, labels_pred) 1.0 >>> metrics.normalized_mutual_info_score(labels_true, labels_pred) 1.0
Это неверно mutual_info_score , поэтому судить о них труднее:
>>> metrics.mutual_info_score(labels_true, labels_pred) 0.69.
Плохие (например, независимые маркировки) имеют отрицательные оценки:
>>> labels_true = [0, 1, 2, 0, 3, 4, 5, 1] >>> labels_pred = [1, 1, 0, 0, 2, 2, 2, 2] >>> metrics.adjusted_mutual_info_score(labels_true, labels_pred) -0.10526.
2.3.10.2.1. Преимущества
- Случайные (унифицированные) присвоения меток имеют оценку AMI, близкую к 0,0 для любого значения n_clusters и n_samples (что не относится, например, к необработанной взаимной информации или V-мере).
- Верхняя граница 1 : значения, близкие к нулю, указывают на два назначения меток, которые в значительной степени независимы, а значения, близкие к единице, указывают на значительное согласие. Кроме того, AMI, равный ровно 1, указывает, что два присвоения меток равны (с перестановкой или без нее).
2.3.10.2.2. Недостатки
- Вопреки инерции, меры на основе MI требуют знания основных классов истинности, хотя на практике они почти никогда не доступны или требуют ручного назначения аннотаторами-людьми (как в условиях контролируемого обучения).
Однако показатели на основе MI также могут быть полезны в чисто неконтролируемой настройке в качестве строительного блока для согласованного индекса, который можно использовать для выбора модели кластеризации
- NMI и MI не подвергаются случайной корректировке.
- Поправка на случайность при оценке производительности кластеризации: анализ влияния размера набора данных на значение показателей кластеризации для случайных назначений. Этот пример также включает скорректированный индекс ранда.
2.3.10.2.3. Математическая постановка
Предположим, что два присвоения метки (одних и тех же N объектов), $U$ а также $V$. Их энтропия — это величина неопределенности для набора разбиений, определяемая следующим образом:
где $P(i) = |U_i| / N$ вероятность того, что объект выбран наугад из $U$ попадает в класс $U_i$. Аналогично дляV:
С участием $P'(j) = |V_j| / N$. Взаимная информация (MI) между $U$ и $V$ рассчитывается по:
где $P(i, j) = |U_i \cap V_j| / N$ вероятность того, что случайно выбранный объект попадает в оба класса $U_i$ а также $V_j$.
Это также может быть выражено в формулировке множества элементов:
Нормализованная взаимная информация определяется как
Это значение взаимной информации, а также нормализованного варианта не скорректировано на случайность и будет иметь тенденцию к увеличению по мере увеличения количества различных меток (кластеров), независимо от фактического количества «взаимной информации» между назначениями меток.
Ожидаемое значение для взаимной информации можно рассчитать с помощью следующего уравнения [VEB2009] . В этом уравнении $a_i = |U_i|$ (количество элементов в $U_i$) а также $b_j = |V_j|$ (количество элементов в $V_j$).
Используя ожидаемое значение, скорректированная взаимная информация может быть затем рассчитана с использованием формы, аналогичной форме скорректированного индекса Rand:
Для нормализованной взаимной информации и скорректированной взаимной информации нормализующее значение обычно представляет собой некоторое обобщенное среднее энтропий каждой кластеризации. Существуют различные обобщенные средства, и не существует твердых правил предпочтения одного по сравнению с другим. Решение в основном принимается отдельно для каждого поля; например, при обнаружении сообществ чаще всего используется среднее арифметическое. Каждый метод нормализации обеспечивает «качественно похожее поведение» [YAT2016] . В нашей реализации это контролируется average_method параметром.
Vinh et al. (2010) назвали варианты NMI и AMI методом их усреднения [VEB2010] . Их средние «sqrt» и «sum» являются средними геометрическими и арифметическими; мы используем эти более общие имена.
- Штрел, Александр и Джойдип Гош (2002). «Кластерные ансамбли — структура повторного использования знаний для объединения нескольких разделов». Журнал исследований машинного обучения 3: 583–617. DOI: 10,1162 / 153244303321897735 .
- Запись в Википедии для (нормализованной) взаимной информации
- Запись в Википедии для Скорректированной взаимной информации
VEB2009 Винь, Эппс и Бейли (2009). «Теоретико-информационные меры для сравнения кластеризации». Материалы 26-й ежегодной международной конференции по машинному обучению — ICML ’09. DOI: 10.1145 / 1553374.1553511 . ISBN 9781605585161.
ВЭБ2010 Винь, Эппс и Бейли (2010). «Теоретико-информационные меры для сравнения кластеризации: варианты, свойства, нормализация и поправка на случайность». JMLR
YAT2016 Ян, Альгешаймер и Тессон (2016). «Сравнительный анализ алгоритмов обнаружения сообществ в искусственных сетях». Научные отчеты 6: 30750. DOI : 10.1038 / srep30750 .
2.3.10.3. Однородность, полнота и V-мера
Зная о назначении основных классов истинности выборкам, можно определить некоторую интуитивно понятную метрику, используя условный энтропийный анализ.
В частности, Розенберг и Хиршберг (2007) определяют следующие две желательные цели для любого кластерного задания:
- однородность : каждый кластер содержит только членов одного класса.
- полнота : все члены данного класса относятся к одному кластеру.
Мы можем превратить эти концепции в партитуры homogeneity_score и completeness_score . Оба ограничены снизу 0,0 и выше 1,0 (чем выше, тем лучше):
>>> from sklearn import metrics >>> labels_true = [0, 0, 0, 1, 1, 1] >>> labels_pred = [0, 0, 1, 1, 2, 2] >>> metrics.homogeneity_score(labels_true, labels_pred) 0.66. >>> metrics.completeness_score(labels_true, labels_pred) 0.42.
Их гармоническое среднее значение, называемое V-мерой , вычисляется по формуле v_measure_score :
>>> metrics.v_measure_score(labels_true, labels_pred) 0.51.
Формула этой функции выглядит следующим образом:
beta по умолчанию используется значение 1.0, но для использования значения менее 1 для бета-версии:
>>> metrics.v_measure_score(labels_true, labels_pred, beta=0.6) 0.54.
больший вес будет приписан однородности, а использование значения больше 1:
>>> metrics.v_measure_score(labels_true, labels_pred, beta=1.8) 0.48.
больший вес будет приписан полноте.
V-мера фактически эквивалентна описанной выше взаимной информации (NMI), при этом функция агрегирования является средним арифметическим [B2011] .
Однородность, полнота и V-мера могут быть вычислены сразу, используя homogeneity_completeness_v_measure следующее:
>>> metrics.homogeneity_completeness_v_measure(labels_true, labels_pred) (0.66. 0.42. 0.51. )
Следующее назначение кластеризации немного лучше, поскольку оно однородное, но не полное:
>>> labels_pred = [0, 0, 0, 1, 2, 2] >>> metrics.homogeneity_completeness_v_measure(labels_true, labels_pred) (1.0, 0.68. 0.81. )
v_measure_score является симметричным : его можно использовать для оценки соответствия двух независимых присвоений одному и тому же набору данных.
Это не относится к completeness_score и homogeneity_score : оба связаны отношениями:
homogeneity_score(a, b) == completeness_score(b, a)
2.3.10.3.1. Преимущества
- Ограниченные баллы : 0,0 — это настолько плохо, насколько это возможно, 1,0 — идеальный балл.
- Интуитивная интерпретация: кластеризацию с плохой V-мерой можно качественно проанализировать с точки зрения однородности и полноты, чтобы лучше понять, какие «ошибки» допускаются при задании.
- Не делается никаких предположений о структуре кластера : может использоваться для сравнения алгоритмов кластеризации, таких как k-среднее, которое предполагает изотропные формы капли, с результатами алгоритмов спектральной кластеризации, которые могут находить кластер со «сложенными» формами.
2.3.10.3.2. Недостатки
- Ранее введенные метрики не нормализованы в отношении случайной маркировки : это означает, что в зависимости от количества выборок, кластеров и основных классов истинности полностью случайная маркировка не всегда будет давать одинаковые значения для однородности, полноты и, следовательно, v-меры.
В частности, случайная маркировка не даст нулевых оценок, особенно когда количество кластеров велико. Эту проблему можно спокойно игнорировать, если количество выборок больше тысячи, а количество кластеров меньше 10. Для меньших размеров выборки или большего количества кластеров безопаснее использовать скорректированный индекс, такой как Скорректированный индекс ранда (ARI) .
- Эти метрики требуют знания основных классов истинности, хотя почти никогда не доступны на практике или требуют ручного назначения аннотаторами-людьми (как в условиях контролируемого обучения).
- Поправка на случайность при оценке производительности кластеризации : анализ влияния размера набора данных на значение показателей кластеризации для случайных назначений.
2.3.10.3.3. Математическая постановка
Оценки однородности и полноты формально даются по формуле:
где $H(C|K)$ является условной энтропией классов с учетом кластерных назначений и определяется выражением:
$$H(C|K) = — \sum_^ <|C|>\sum_^ <|K|>\frac> \cdot \log\left(\frac>\right)$$а также $H(C)$ — энтропия классов и определяется выражением:
$$H(C) = — \sum_^ <|C|>\frac \cdot \log\left(\frac\right)$$с участием n общее количество образцов, $n_c$ а также $n_k$ количество образцов, соответственно принадлежащих к классу c и кластер $k$, и наконец $n_$ количество образцов из класса c назначен кластеру k.
Условная энтропия кластеров данного класса $H(C|K)$ и энтропия кластеров $H(K)$ определены симметричным образом.
Розенберг и Хиршберг далее определяют V-меру как гармоническое среднее однородности и полноты:
$$v = 2 \cdot \frac$$- V-Measure: мера оценки внешнего кластера на основе условной энтропии Эндрю Розенберг и Джулия Хиршберг, 2007 г.
2.3.10.4. Результаты Фаулкса-Мэллоуса
Индекс Фаулкса-Мэллоуса ( sklearn.metrics.fowlkes_mallows_score ) может использоваться, когда известны наземные присвоения классов истинности выборкам. FMI по шкале Fowlkes-Mallows определяется как среднее геометрическое для попарной точности и отзыва:
$$\text = \frac> <\sqrt<(\text+ \text) (\text + \text)>>$$Где TP — количество истинных положительных результатов (True Positive) (т.е. количество пар точек, принадлежащих одним и тем же кластерам как в истинных, так и в предсказанных метках), FP — это количество ложных положительных результатов (False Positive) (то есть количество пар точек, принадлежащих к одинаковые кластеры в истинных метках, а не в предсказанных метках) и FN является количеством ложно-отрицательных (False Negative) (т. е. количеством пар точек, принадлежащих одним и тем же кластерам в предсказанных метках, а не в истинных метках).
Оценка варьируется от 0 до 1. Высокое значение указывает на хорошее сходство между двумя кластерами.
>>> from sklearn import metrics >>> labels_true = [0, 0, 0, 1, 1, 1] >>> labels_pred = [0, 0, 1, 1, 2, 2]
>>> metrics.fowlkes_mallows_score(labels_true, labels_pred) 0.47140.
Можно переставить 0 и 1 в предсказанных метках, переименовать 2 в 3 и получить тот же результат:
>>> labels_pred = [1, 1, 0, 0, 3, 3] >>> metrics.fowlkes_mallows_score(labels_true, labels_pred) 0.47140.
Идеальная маркировка оценивается в 1,0:
>>> labels_pred = labels_true[:] >>> metrics.fowlkes_mallows_score(labels_true, labels_pred) 1.0
Плохие (например, независимые маркировки) имеют нулевые баллы:
>>> labels_true = [0, 1, 2, 0, 3, 4, 5, 1] >>> labels_pred = [1, 1, 0, 0, 2, 2, 2, 2] >>> metrics.fowlkes_mallows_score(labels_true, labels_pred) 0.0
2.3.10.4.1. Преимущества
- Случайное (единообразное) присвоение меток имеет оценку FMI, близкую к 0,0 для любого значения n_clusters и n_samples (что не относится, например, к необработанной взаимной информации или V-мере).
- Верхний предел — 1 : значения, близкие к нулю, указывают на два назначения меток, которые в значительной степени независимы, а значения, близкие к единице, указывают на значительное согласие. Кроме того, значения ровно 0 указывают на чисто независимые присвоения меток, а FMI ровно 1 указывает, что два назначения меток равны (с перестановкой или без нее).
- Не делается никаких предположений о структуре кластера : может использоваться для сравнения алгоритмов кластеризации, таких как k-среднее, которое предполагает изотропные формы капли, с результатами алгоритмов спектральной кластеризации, которые могут находить кластер со «сложенными» формами.
2.3.10.4.2. Недостатки
- Вопреки инерции, меры, основанные на FMI, требуют знания основных классов истинности, хотя почти никогда не доступны на практике или требуют ручного назначения аннотаторами-людьми (как в условиях контролируемого обучения).
- EB Fowkles и CL Mallows, 1983. «Метод сравнения двух иерархических кластеров». Журнал Американской статистической ассоциации. http://wildfire.stat.ucla.edu/pdflibrary/fowlkes.pdf
- Запись в Википедии об Индексе Фаулкса-Маллоуза
2.3.10.5. Коэффициент силуэта
Если наземные метки достоверности неизвестны, оценка должна выполняться с использованием самой модели. Коэффициент силуэта ( sklearn.metrics.silhouette_score ) является примером такой оценки, где более высокий показатель коэффициента силуэта относится к модели с лучше определенными кластерами. Коэффициент силуэта определяется для каждого образца и состоит из двух баллов:
- a : Среднее расстояние между образцом и всеми другими точками того же класса.
- b : Среднее расстояние между образцом и всеми другими точками в следующем ближайшем кластере .
Тогда коэффициент силуэта s для одного образца определяется как:
$$s = \fracКоэффициент силуэта для набора образцов дается как среднее значение коэффициента силуэта для каждого образца.
>>> from sklearn import metrics >>> from sklearn.metrics import pairwise_distances >>> from sklearn import datasets >>> X, y = datasets.load_iris(return_X_y=True)
При обычном использовании коэффициент силуэта применяется к результатам кластерного анализа.
>>> import numpy as np >>> from sklearn.cluster import KMeans >>> kmeans_model = KMeans(n_clusters=3, random_state=1).fit(X) >>> labels = kmeans_model.labels_ >>> metrics.silhouette_score(X, labels, metric='euclidean') 0.55.
- Питер Дж. Руссеу (1987). «Силуэты: графическое средство для интерпретации и проверки кластерного анализа». Вычислительная и прикладная математика 20: 53–65. DOI: 10.1016 / 0377-0427 (87) 90125-7 .
2.3.10.5.1. Преимущества
- Оценка ограничена от -1 за неправильную кластеризацию до +1 за высокоплотную кластеризацию. Баллы около нуля указывают на перекрывающиеся кластеры.
- Оценка выше, когда кластеры плотные и хорошо разделенные, что относится к стандартной концепции кластера.
2.3.10.5.2. Недостатки
- Коэффициент силуэта обычно выше для выпуклых кластеров, чем для других концепций кластеров, таких как кластеры на основе плотности, подобные тем, которые получены с помощью DBSCAN.
- Выбор количества кластеров с анализом силуэта в кластеризации KMeans : в этом примере анализ силуэта используется для выбора оптимального значения для n_clusters.
2.3.10.6. Индекс Калински-Харабаса
Если наземные метки достоверности неизвестны, индекс Калински-Харабаса ( sklearn.metrics.calinski_harabasz_score ) — также известный как критерий отношения дисперсии — можно использовать для оценки модели, где более высокий балл Калински-Харабаса относится к модели с более определенными кластерами.
Индекс представляет собой отношение суммы дисперсии между кластерами и дисперсии внутри кластера для всех кластеров (где дисперсия определяется как сумма квадратов расстояний):
>>> from sklearn import metrics >>> from sklearn.metrics import pairwise_distances >>> from sklearn import datasets >>> X, y = datasets.load_iris(return_X_y=True)
При обычном использовании индекс Калински-Харабаса применяется к результатам кластерного анализа:
>>> import numpy as np >>> from sklearn.cluster import KMeans >>> kmeans_model = KMeans(n_clusters=3, random_state=1).fit(X) >>> labels = kmeans_model.labels_ >>> metrics.calinski_harabasz_score(X, labels) 561.62.
2.3.10.6.1. Преимущества
- Оценка выше, когда кластеры плотные и хорошо разделенные, что относится к стандартной концепции кластера.
- Счет быстро подсчитывается.
2.3.10.6.2. Недостатки
- Индекс Калински-Харабаса обычно выше для выпуклых кластеров, чем для других концепций кластеров, таких как кластеры на основе плотности, подобные тем, которые получены с помощью DBSCAN.
2.3.10.6.3. Математическая постановка
где $tr(B_k)$ является следом межгрупповой дисперсионной матрицы и $tr(W_k)$ является следом матрицы дисперсии внутри кластера, определяемой следующим образом:
$$W_k = \sum_^k \sum_ (x — c_q) (x — c_q)^T$$
$$B_k = \sum_^k n_q (c_q — c_E) (c_q — c_E)^T$$с участием $C_q$ набор точек в кластере $q$, $c_q$ центр кластера $q$, $c_E$ центр $E$, а также $n_q$ количество точек в кластере $q$.
- Калински Т. и Харабаш Дж. (1974). «Дендритный метод кластерного анализа» . Коммуникации в теории статистики и методах 3: 1-27. DOI: 10.1080 / 03610927408827101 .
2.3.10.7. Индекс Дэвиса-Болдина
Если наземные метки истинности неизвестны, для оценки модели можно использовать индекс Дэвиса-Болдина ( sklearn.metrics.davies_bouldin_score ), где более низкий индекс Дэвиса-Болдина относится к модели с лучшим разделением между кластерами.
Этот индекс означает среднее «сходство» между кластерами, где сходство — это мера, которая сравнивает расстояние между кластерами с размером самих кластеров.
Ноль — это наименьший возможный результат. Значения, близкие к нулю, указывают на лучшее разделение.
При обычном использовании индекс Дэвиса-Болдина применяется к результатам кластерного анализа следующим образом:
>>> from sklearn import datasets >>> iris = datasets.load_iris() >>> X = iris.data >>> from sklearn.cluster import KMeans >>> from sklearn.metrics import davies_bouldin_score >>> kmeans = KMeans(n_clusters=3, random_state=1).fit(X) >>> labels = kmeans.labels_ >>> davies_bouldin_score(X, labels) 0.6619.
2.3.10.7.1. Преимущества
- Вычисление Дэвиса-Боулдина проще, чем оценка Силуэта.
- В индексе вычисляются только количества и характеристики, присущие набору данных.
2.3.10.7.2. Недостатки
- Индекс Дэвиса-Боулдинга обычно выше для выпуклых кластеров, чем для других концепций кластеров, таких как кластеры на основе плотности, подобные тем, которые получены из DBSCAN.
- Использование центроидного расстояния ограничивает метрику расстояния евклидовым пространством.
2.3.10.7.3. Математическая постановка
Индекс определяется как среднее сходство между каждым кластером. $C_i$ для $i=1, …, k$ и его самый похожий $C_j$. В контексте этого индекса сходство определяется как мера $R_$ что торгуется:
- $s_i$, среднее расстояние между каждой точкой кластера $i$ и центроид этого кластера — также известный как диаметр кластера.
- $d_$, расстояние между центрами скоплений $i$ а также $j$.
Простой выбор для построения $R_$ так что он неотрицателен и симметричен:
$$R_ = \frac$$ Тогда индекс Дэвиса-Болдина определяется как:
$$DB = \frac \sum_^k \max_ R_$$- Дэвис, Дэвид Л .; Боулдин, Дональд В. (1979). «Мера разделения кластеров» IEEE-транзакции по анализу шаблонов и машинному интеллекту. ПАМИ-1 (2): 224-227. DOI: 10.1109 / TPAMI.1979.4766909 .
- Халкиди, Мария; Батистакис, Яннис; Вазиргианнис, Михалис (2001). «О методах кластеризации валидации» Журнал интеллектуальных информационных систем, 17 (2-3), 107-145. DOI: 10,1023 / А: 1012801612483 .
- Запись в Википедии для индекса Дэвиса-Болдина .
2.3.10.8. Матрица непредвиденных обстоятельств
Матрица непредвиденных обстоятельств ( sklearn.metrics.cluster.contingency_matrix ) сообщает мощность пересечения для каждой истинной / прогнозируемой пары кластеров. Матрица непредвиденных обстоятельств обеспечивает достаточную статистику для всех метрик кластеризации, где выборки независимы и одинаково распределены, и нет необходимости учитывать некоторые экземпляры, которые не были кластеризованы.
>>> from sklearn.metrics.cluster import contingency_matrix >>> x = ["a", "a", "a", "b", "b", "b"] >>> y = [0, 0, 1, 1, 2, 2] >>> contingency_matrix(x, y) array([[2, 1, 0], [0, 1, 2]])
Первая строка выходного массива указывает, что есть три образца, истинный кластер которых равен «a». Из них два находятся в предсказанном кластере 0, один — в 1 и ни один — в 2. И вторая строка указывает, что есть три выборки, истинный кластер которых равен «b». Из них ни один не находится в прогнозируемом кластере 0, один — в 1, а два — в 2.
Матрица неточностей для классификации является квадратной матрицей непредвиденной где порядок строк и столбцов соответствует списку классов.
2.3.10.8.1. Преимущества
- Позволяет изучить распространение каждого истинного кластера по прогнозируемым кластерам и наоборот.
- Вычисленная таблица непредвиденных обстоятельств обычно используется при вычислении статистики сходства (как и другие, перечисленные в этом документе) между двумя кластерами.
2.3.10.8.2. Недостатки
- Матрицу непредвиденных обстоятельств легко интерпретировать для небольшого количества кластеров, но становится очень трудно интерпретировать для большого количества кластеров.
- Он не дает ни одной метрики для использования в качестве цели для оптимизации кластеризации.
2.3.10.9. Матрица неточности пар
Матрица смешения пар ( sklearn.metrics.cluster.pair_confusion_matrix ) представляет собой матрицу подобия 2×2
между двумя кластерами, вычисленными путем рассмотрения всех пар выборок и подсчета пар, которые назначены в один и тот же или в разные кластеры в рамках истинной и прогнозируемой кластеризации.
В нем есть следующие записи:
$C_$: количество пар с обеими кластерами, в которых образцы не сгруппированы вместе
$C_$: количество пар с истинной кластеризацией меток, в которых образцы сгруппированы вместе, но в другой кластеризации образцы не сгруппированы вместе
$C_$: количество пар с истинной кластеризацией меток, в которых образцы не сгруппированы вместе, а другая кластеризация содержит образцы, сгруппированные вместе
$C_$: количество пар с обеими кластерами, имеющими образцы, сгруппированные вместеЕсли рассматривать пару образцов, сгруппированных вместе как положительную пару, то, как и в бинарной классификации, количество истинных отрицательных значений равно $C_$, ложноотрицательные $C_$, истинные положительные стороны $C_$ а ложные срабатывания $C_$.
Идеально совпадающие метки имеют все ненулевые записи на диагонали независимо от фактических значений меток:
>>> from sklearn.metrics.cluster import pair_confusion_matrix >>> pair_confusion_matrix([0, 0, 1, 1], [0, 0, 1, 1]) array([[8, 0], [0, 4]])
>>> pair_confusion_matrix([0, 0, 1, 1], [1, 1, 0, 0]) array([[8, 0], [0, 4]])
Метки, которые назначают все члены классов одним и тем же кластерам, являются полными, но не всегда могут быть чистыми, следовательно, наказываются и имеют некоторые недиагональные ненулевые записи:
>>> pair_confusion_matrix([0, 0, 1, 2], [0, 0, 1, 1]) array([[8, 2], [0, 2]])
Матрица не симметрична:
>>> pair_confusion_matrix([0, 0, 1, 1], [0, 0, 1, 2]) array([[8, 0], [2, 2]])
Если члены классов полностью разделены по разным кластерам, назначение полностью неполное, следовательно, матрица имеет все нулевые диагональные элементы:
>>> pair_confusion_matrix([0, 0, 0, 0], [0, 1, 2, 3]) array([[ 0, 0], [12, 0]])
- Л. Хьюберт и П. Араби, Сравнение разделов, журнал классификации 1985 < https://link.springer.com/article/10.1007%2FBF01908075 > _
Если вы хотите помочь проекту с переводом, то можно обращаться по следующему адресу support@scikit-learn.ru
© 2007 — 2020, scikit-learn developers (BSD License).Классификация, регрессия и другие алгоритмы Data Mining с использованием R
Использование главных компонент для иерархической кластеризации — один из возможных путей гибридизации алгоритмов, которая все чаще привлекает внимание специалистов. Предварительное сжатие пространства признаков — хороший метод сглаживания случайных флуктуаций в данных, что является предпосылкой построения более стабильных кластерных структур. Это особенно важно для матриц с большим количеством признаков, например, в генной инженерии.
В среде R кластеризация на главные компоненты реализована в пакете FactoMineR и состоит из двух шагов. На первом этапе функцией РСА() выполняется обычный анализ главных компонент и выбирается их число. Далее функция HCPC() использует эти результаты и строит иерархическую кластеризацию. При этом используется метод Уорда, который, как и анализ главных компонент, основан на анализе многомерной дисперсии (inertia).
Опять воспользуемся в качестве примера набором Boston из пакета MASS . Выполним снижение исходной размерности данных, определяемой 14 признаками привлекательности земельных участков Бостона, до 5 главных компонент (рис. 10.13):
library(FactoMineR) library(factoextra) data(Boston, package = "MASS") df.scale scale(Boston) res.pca PCA(df.scale, ncp = 5, graph = TRUE) get_eig(res.pca)
Рисунок 10.13: Разложение исходных признаков по осям двух главных компонент
Напомним, что угол между двумя любыми осями (факторов и/или компонент) на рис. 10.13 соответствует уровню корреляции между ними. Заинтересованный читатель может сравнить этот график с иерархической дендрограммой признаков на рис. 10.12.
Выполним теперь иерархическую кластеризацию на главные компоненты. Построим две диаграммы — обычную дендрограмму, совмещенную с графиком “каменистой осыпи” дисперсии ( choice =»tree» ), и трехмерную дендрограмму, совмещенную с ординационной диаграммой ( choice = «3D.map» ):
res.hcpc HCPC(res.pca, graph = FALSE) plot(res.hcpc, choice = "tree") plot(res.hcpc, choice = "3D.map", ind.names = FALSE)
Рисунок 10.14: Дендрограмма с разделением на кластеры (вверху) и гибрид дендрограммы с ординационной диаграммы (внизу)
10.4.2 Метод нечетких k средних (fuzzy analysis clustering)
Традиционные принципы кластерного анализа предполагают, что выделяемые группы представляют собой детерминированные совокупности, т. е. каждый объект может принадлежать только к одному таксону. Ограниченность такого подхода часто приводит к аналитической неопределенности, и поэтому разумной альтернативой понятию абсолютной дискретности является интерпретация компонентов систем как нечетких объектов в составе гибко настраиваемых ординационных структур.
В конце 80-х годов, после того, как основные концепции нечетких множеств (fuzzy sets) были разработаны Лотфи Заде (Zadeh, 1965), началось бурное развитие технических устройств на базе нечетких контроллеров, а нечеткая логика (fuzzy logic) стала неотъемлемой составной частью современных систем искусственного интеллекта.
Множество \(\mathbf\) является нечетким, если существует функция принадлежности (membership function) \(\mu_C(x) = 0\) означает полную несовместимость, т.е. \(x \notin \mathbf\) , а \(\mu_C(x) = 1\) означает полную принадлежность, или \(x \in \mathbf\) . Применительно к кластеризации методом нечетких \(k\) средних функция \(\mu_(\mathbf)\) задает в масштабе от 0 до 1 степень принадлежности каждого объекта \(x_i\) к каждому выделяемому кластеру \(r\) (Bezdek, 1981).
Пусть \(D_ = \sum_j (x_ — \nu_)^2\) — расстояние между каждым \(i\) -м объектом ( \(i = 1, 2, \dots, n\) ), описанным набором признаков \(x_\) , и центрами тяжести \(v_\) каждого из \(k\) кластера ( \(r = 1, 2, \dots, k\) ). Тогда в общем случае кластеризацию объектов \(\mathbf\) можно сформулировать как задачу оптимизации, связанную с нахождением такой матрицы \(\mathbf<\mu>\) , которая минимизировала бы критерий
Экспоненциальный вес ( \(m\) ) в алгоритме нечетких \(k\) средних задает уровень нечеткости получаемых кластеров: чем больше m, тем нечеткое разбиение более “размазано”. “Штатный” диапазон варьирования \(m\) — от 1.2 до 2. Другим важным параметром является количество классов \(k\) , которое принимается из описанных выше соображений.
Выполним построение “нечетких” кластеров для традиционного примера по криминогенной обстановке американских штатов с использованием функции fanny() из пакета cluster :
library(cluster) data("USArrests") set.seed(123) res.fanny fanny(USArrests, k = 4, memb.exp = 1.7, metric = "euclidean", stand = TRUE, maxit = 500) print(head(res.fanny$membership),3)## [,1] [,2] [,3] [,4] ## Alabama 0.639 0.183 0.113 0.0645 ## Alaska 0.337 0.357 0.179 0.1280 ## Arizona 0.213 0.595 0.131 0.0611 ## Arkansas 0.371 0.170 0.264 0.1959 ## California 0.224 0.529 0.160 0.0869 ## Colorado 0.224 0.519 0.174 0.0830res.fanny$coeff## dunn_coeff normalized ## 0.3927126 0.1902834При \(k = 4\) в результате выводится матрица коэффициентов принадлежности, максимальный из которых определяет назначаемый кластер. Так из приведенного фрагмента Алабама и Арканзас включены в кластер 1, а остальные четыре штата — в кластер 2.
Для оценки меры нечеткости полученной классификации используется коэффициент разделения Данна (Dunn):
который принимает минимальное значение при полной нечеткости разбиения, когда расстояния от каждого объекта до центра тяжести любого кластера равновелики: \(\mu = 1/k\) . Напротив, в случае четкой кластеризации ( \(\mu = 1\) или \(\mu = 0\) ) коэффициент Данна \(F_k\) принимает значение 1. Для представленного примера \(F_k = 0.39\) , а его нормированная версия, изменяющаяся от 0 до 1 и характеризующая степень нечеткости \(F_k’ = (kF_k — 1)/(k-1) = 0.19\) .
Построим две диаграммы (рис. 10.15). На первой из них (слева) покажем матрицу \(\sum_^k \mu_^2 / k\) , отсортированную по убыванию (т.е. по степени нечеткости). На второй же (справа) – ординационную диаграмму в пространстве двух главных компонент с результатами кластеризации (аналогична рис. 10.6).
# Визуализация с использованием corrplot library(corrplot) Dunn res.fanny$membership^2 corrplot(Dunn[rev(order(rowSums(Dunn))), ], is.corr = FALSE) # Ординационная диаграмма library(factoextra) fviz_cluster(res.fanny, frame.type = "norm", frame.level = 0.7)
Рисунок 10.15: Матрица степени нечеткости (слева) и ординационная диаграмма (справа), полученные с применением метода нечеткой кластеризации
10.4.3 Статистическая модель кластеризации
Важнейшими свойствами кластеров являются плотность, дисперсия, размер, форма и отделимость (Ким и др., 1989). Характер изменчивости облака экспериментальных точек относительно центроидов искомых кластеров может быть описан статистической моделью со смешанными параметрами (Banfield, Raftery, 1993).
Предположим, что входное множество векторов наблюдений \(x_1, x_2, \dots, x_n\) представляет собой случайные реализации из \(K\) неизвестных распределений \(E_1, E_2, \dots, E_K\) . Допустим, что плотность распределения \(x_i\) , связанная с \(E_k\) , задана функцией \(f_k(x_i, \theta)\) , включающей некоторое неизвестное множество параметров \(\theta\) . Если принять допущение, что классифицируемый объект принадлежит только одному распределению, то можно ввести переменную \(\gamma_I = k\) , если xi принадлежит \(E_k, k = 1, 2, \dots, K\) . Тогда цель оптимизации модели заключается в нахождении таких параметров \(\mathbf\) и \(\mathbf<\gamma>\) , которые максимизируют совокупную вероятность:
Поскольку вероятность \(L(\mathbf)\) основана на смеси \(K\) распределений, то такая модель называется смешанной (mixture model). Если использовать в качестве распределений многомерные нормальные функции, то неизвестные параметры \(\mathbf\) определяются как вектор средних \(\mu_k\) и матрица ковариации \(\Sigma_k\) каждого \(k\) -го распределения.
Если рассматривать изложенный формализм смешанных моделей применительно к кластеризации (model-based clustering), то каждой группе \(k\) соответствует центроид \(\mu_k\) с повышенной плотностью точек в его окрестностях. Геометрические особенности (форма, объем, ориентация) каждого кластера определены матрицей ковариации \(\Sigma_k\) . Главным преимуществом этого подхода, по сравнению с другими методами кластеризации, является возможность автоматической оценки оптимального числа кластеров в процессе подгонки параметров модели.
Выборочные оценки параметров \(\theta\) могут быть получены с использованием алгоритма максимизации математических ожиданий (EM, Expectation-Maximization), который оценивает максимумы вероятности \(L(\mathbf)\) серии моделей: для заданного диапазона значений \(k\) и с различной параметризацией матрицы ковариации. Оптимальная модель обычно отбирается на основе максимума байесовского информационного критерия BIC.
Рассмотрим двумерный набор данных, который содержит время ожидания между извержениями ( waiting ) и продолжительностью извержения ( eruptions ) гейзера “Старый служака” в Йеллоустонском национальном парке. Для иллюстрации характера распределения наблюдаемых данных изобразим диаграмму рассеяния (рис. 10.16):
data(faithful) head(faithful, 3)## eruptions waiting ## 1 3.600 79 ## 2 1.800 54 ## 3 3.333 74library(ggplot2) ggplot(faithful, aes(x = eruptions, y = waiting)) + geom_point() + geom_density2d()
Рисунок 10.16: Диаграмма двумерной плотности распределения данных faithful
Подогнать смешанную модель кластеризации по этим данным можно с использованием функции Mclust() из пакета mclust .
mc mclust::Mclust(faithful) summary(mc)## ---------------------------------------------------- ## Gaussian finite mixture model fitted by EM algorithm ## ---------------------------------------------------- ## ## Mclust EEE (ellipsoidal, equal volume, shape and orientation) model with 3 components: ## ## log.likelihood n df BIC ICL ## -1126.361 272 11 -2314.386 -2360.865 ## ## Clustering table: ## 1 2 3 ## 130 97 45head(mc$z)## [,1] [,2] [,3] ## 1 2.181744e-02 1.130837e-08 9.781825e-01 ## 2 2.475031e-21 1.000000e+00 3.320864e-13 ## 3 2.521625e-03 2.051823e-05 9.974579e-01 ## 4 6.553336e-14 9.999998e-01 1.664978e-07 ## 5 9.838967e-01 7.642900e-20 1.610327e-02 ## 6 2.104355e-07 9.975388e-01 2.461029e-03Мы получили разбиение исходных наблюдений на три кластера с оптимальным BIC = -2314 . Каждому наблюдению назначается кластер с максимальной оцененной вероятностью z . Для визуализации полученных кластеров можно использовать различные варианты функции plot() или fviz_cluster() :
par(mfrow = c(1, 2)) plot(mc, "classification") plot(mc, "uncertainty")
Рисунок 10.17: Распределение наблюдений по кластерам (на графике справа диаметр точек соответствует мере неопределенности — uncertainty )
Как следует из результатов summary() , ковариационные матрицы оптимизированы под вариант структурной организации кластеров EEE (эллипсоидальная с равным объемом, формой и ориентацией). Зависимость критерия BIC от числа кластеров для различных вариантов параметризации можно увидеть на следующем графике:
plot(mc, "BIC")
Рисунок 10.18: Зависимость критерия BIC от числа кластеров для различных вариантов параметризации ковариационной матрицы
Каждая опция модели, представленная на рис. 10.18, описана идентификатором, первый символ которого относится к объему, второй — к форме, а третий — к ориентации. Символы могут принимать значения «E» — равный, «V» — переменный и «I» — расположение относительно осей координат. Так, «VEI» означает, что кластеры имеют разный объем, одинаковую форму и одинаково ориентированы по координатным осям. Подробно о составе и смысле опций можно узнать, выполнив команду ?mclustModelNames .