Есть ли более 1 кластера?

Question

[Сергей Соколов]

Есть одномерный набор значений. Например:
[1, 2, 1, 0, 1, 1, 0, -1, 0, 21, 22]

В нём может быть два четко различимых кластера, как в примере - пара значений [21,22] сильно отличных от остальной массы. А может и не быть.

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

upd. Задача, оказывается, типичная: определение числа кластеров (на англ.)

Answer 1

[dmshar]

Вообще то есть такой раздел Data Mining, как кластерный анализ. И для решения задач типа вaшей разработано наверное десятков пять различных методов. В том числе - и "без ручного задания порога" (скажу по секрету - можно обойтись вообще без какого-бы то ни было задания порога).
Ваш случай - простейший, одномерный. В жизни встречаются задачи намного сложнее. Но в любом случае, выбор подхода и конкретного метода кластеризации зависит от данных - и от того, в какой шкале они измерены, и сколько их, и известно-ли их распределения, и какие меры близости можно ввести в пространстве признаков. Там же рассматривается вопрос, а как ОБОСНОВАНО выбрать количество, на которых разбивается выборка и как выявить аномалии-выбросы. В довершении всего имеются методы сравнения методов между собой.
Если говорить конкретно про Ваш пример, что данных настолько мало и кластеры настолько выражены, что тут сомнений нет. Но а если Вас проблема интересует более глубоко - то без изучения теории не обойтись. Часто кластеризацию изучают как одно из направлений в рамках машинного обучения и рассматривают в соответствующих книгах/курсах. Могу порекомендовать в качестве "затравки"-

https://habrahabr.ru/post/101338/
https://habrahabr.ru/company/ods/blog/325654/
Флах _"Машинное обучение - наука и искусство построения алгоритмов",
Барсегян "Анализ данных и процессов"
и более серьезные источники:
Мандель "Кластерный анализ"
Ким "Факторный, дискриминантный и кластерный анализ"
Миркин "Методы кластер-анализа"
Aggarwal, Chandan K. "Reddy-Data Clustering_ Algorithms and Applications"

и пр.пр.пр. Источников по теме -море.
Удачи.

Comments

[Сергей Соколов]

Так в приведённом простейшем случае, не обкладываясь книгами, зная по секрету все секреты и пройдя несколько курсов по кластерному анализу, вы бы как решали задачку элементарную?

[dmshar]

На глаз :-)
Серьезно, именно в приведенном выше случае, если надо просто разделить указанную выборку на две части,если потом вы не собираетесь использовать ее в качестве классификатора и еще при множестве всяких "не", вы сами дали ответ -(21,22) и все остальное. И самое интересное, даже самый умный алгоритм кластеризации в данном случае просто обязан дать тот-же ответ :-).
А вот если вам надо и далее делить ВНОВЬ поступающие точки например, то тогда без метода кластеризации, хотя-бы простейшего не обойтись.
Ну например, метод k-means - элементарно объясняется, миллион статей в интернете, самому запрограммировать - двадцать минут работы, есть стандартные реализации на Python и R, есть реализация даже в EXCEL.
И кстати, в нем - никакой точки отсечения (порога) нет и работает он даже в случае если кластеров больше двух (даже на прямой).

[Сергей Соколов]

dmshar, опять намутили воду, много воды, и ничего по делу. k-means я уже применяю в других задачах по этому датасету. Тут дело в том, что куча строк. В некоторых такое четкое деление на 2 кластера есть. В некоторых нет. И я у опытных дата сайентистов интересуюсь, каким методом лучше это есть/нет определять. python, pandas, sklearn.

[dmshar]

Ну, если вы человек с опытом, то непонятно, чем конкретно вам не угодил, например scipy.cluster.vq.kmeans или sklearn.cluster.KMeans ?
И если вы применяете k-means то почему спрашиваете о пороге?
А если спрашиваете о пороге, то не путате-ли вы задачи кластеризации с задачей классификации?

[Сергей Соколов]

dmshar, разделив на два кластера, как оценить, что да, есть четкая большая пустота между двумя, или же нет её?

[dmshar]

1. Если вы уже использовали k-means, то очевидно хорошо понимаете, что в этом алгоритме "пустоты" не оцениваются никак, ибо он относится к алгоритмам на основе анализа метрик, а не на основе анализа плотностей.
К алгоритмам на основе анализа плотностей относится, например, алгоритм DBSCAN.
2. Если вы человек с опытом в анализе данных, то очевидно понимаете, что практически все алгоритмы не оценивают что-то после своей работы, а наоборот, они строят кластеры так, чтобы удовлетворить каким-то наперед заданным критериям. Другими словами, если вы применяете алгоритм, вы не должны проверять "а есть-ли пустота между кластерами", вы должны понимать, что алгоритм именно так и построен, что результатом его работы будет набор максимально возможных "плотных" на заданном наборе данных скоплений точек.
3. Но если вам все таки вдруг очень захотелось определить где именно на вашей оси есть пустота, а где нет, и нет желания применять алгоритм кластеризации - то в вашем конкретном (одномерном) случае я бы посоветовал просто оценить плотность точек на всем интервале возможных значений. (Впрочем, DBSCAN в одномерном случае именно это и делает). Обратите внимание, что к поиску "порога" это опять не имеет никакого отношения.

[Сергей Соколов]

Спасибо, посмотрю подробнее DBSCAN.

Коммент опять переполнен водой и обращением к личности, а не теме вопроса. Здесь принятно писать по существу. Переписать коммент можно было бы так:
----
«
1. в k-means "пустоты" не оцениваются никак, ибо он относится к алгоритмам на основе анализа метрик, а не на основе анализа плотностей.
К алгоритмам на основе анализа плотностей относится, например, алгоритм DBSCAN.
2. практически все алгоритмы не оценивают что-то после своей работы, а наоборот, они строят кластеры так, чтобы удовлетворить каким-то наперед заданным критериям. Не нужно проверять "а есть-ли пустота между кластерами", алгоритм построен так, что результатом его работы будет набор максимально возможных "плотных" на заданном наборе данных скоплений точек.
3. в конкретном одномерном случае я бы посоветовал просто оценить плотность точек на всем интервале возможных значений. DBSCAN в одномерном случае именно это и делает.
»

Answer 2

[codemania]

Среднеквадратичное отклонение?

Comments

[Сергей Соколов]

ну посчитал я сигму, «и че?». Имеете в виду, посмотреть, есть ли значения за пределами N сигм?

Может быть вариант равного количества значений в двух кластерах: [1, 1, 100, 100]

Answer 3

[Данил]

Правило 3х сигм - 99% всего распределение меньше 3*sigma, все что больше можно считать за выброс.

https://basegroup.ru/community/glossary/3-sigma

Comments

[Сергей Соколов]

В приведённом примере mean = 4.36, sigma * 3 = 25.53, таким образом [21,22] не считаются выбросом, а хотелось бы..

[Данил]

Для расчета sigma Вам нужно взять распределение без выбросов. Простыми словами - система не сможет определить выбросы, если не знает, как выглядит правильное (эталонное) распределение.

[Сергей Соколов]

Данил, в этом и состоит задача - unsupervised learning, типа - определить, есть ли аномалии, без участия человека, без эталона и подсказок.

[Данил]

Возможно подойдет EllipticEnvelope

ee = EllipticEnvelope(contamination=0.2)
xxx = np.array([1, 2, 1, 0, 1, 1, 0, -1, 0, 21, 22])

ee.fit(xxx.reshape(-1, 1))
predictions = ee.predict(xxx.reshape(-1, 1))

Все predictions = -1 соответствуют выбросам.

Два замечания:

1. contamination - нужно подбирать данный параметр
   
2. Машинное обучение - это всегда вероятность. То есть, возможны ложные срабатывания
   

Answer 4

[Андрей Федосеев]

Построить график, искать всплески.