Алгоритм поиска кластеров в 1d кластерах, но не обязательно кластеризация всего

Question

Представьте, что у меня есть массив, подобный следующему:

[0.1,0.12,0.14,0.45,0.88,0.91,0.94,14.3,15,16]

Я хотел бы определить шаблоны в этом, так что я могу сравнить его с другим набором данных, чтобы увидеть, соответствует ли он. Например, если я введу 0.89Я хотел бы видеть, что это относится к 0.88-0.94 кластер. Однако, если я войду 0.5Я хотел бы видеть, что это не относится к набору данных, даже если оно близко к 0.45 - аномалия в данных.

(Приведенный выше массив содержит примеры номеров, но в реальной системе я сравниваю свойства кода HTML для их классификации. Я использую Tensorflow для категоризации текста, но некоторые вещи (например, длина CSS, соотношение CSS:HTML) являются числами Хотя в этом есть шаблоны, это неочевидно или в одном месте - например, категория A может иметь много очень высоких значений и низких значений, но почти ни одного между ними. Я не могу дать вам реальные цифры, потому что они определены с помощью введенного кода и препроцессора ML, но мы можем предположить, что числа составляют примерно 10% аномалий, и почти всегда пытаются показать одну или несколько комбинаций среднего, нижнего или верхнего. При "обучении" эти числа берутся из данных и хранится в одном из массивов (представляющих три категории). Затем я хочу взять свой вход и сказать, какой из шаблонов массивов, кажется, совпадает с номером ввода.)

Теперь представьте, что массив состоит из сотен или тысяч элементов. По крайней мере, 10% будут аномалии, и я должен учитывать это. Я предполагаю, что обнаружение кластера не является правильным термином - это в основном избавление от аномалий - но часть, на которой я застрял, имела диапазоны разных размеров. Например, в приведенном выше примере я все еще хотел бы 14.3-16 считаться одним диапазоном / кластером, даже если есть гораздо дальше, чем0.1-0.14,

Я покопался в статье в Википедии ( https://en.m.wikipedia.org/wiki/Anomaly_detection) на эту тему и обнаружил, что наиболее вероятным функциональным и простым подходом будет стиль K-ближайших соседей. анализ плотности. Однако я не смог найти ни одного подключаемого модуля Python, который мог бы легко сделать это для меня - проблема в том, что в этой конкретной задаче так много вариантов, что в принципе невозможно найти именно то, что я ищу. Я также попытался сделать свой собственный базовый алгоритм, чтобы сравнить каждый элемент с соседом и посмотреть, какой из них ближе (к кластеру), или если это расстояние больше 2* среднее значение расстояний между другими элементами в кластеры классифицируют это как аномалию. Тем не менее, это было не очень точно, и все еще имел элемент предвзятости человека (почему 2*, а не 3*?); Более того, он полностью потерял связь в начале и в конце или в массиве. Поэтому, если у кого-то из вас есть рекомендация по быстрому алгоритму, который будет работать еще лучше, или реализация вышеупомянутого, это будет с благодарностью.

Заранее спасибо.

Answer 1

Используйте классические статистические методы, такие как оценка плотности ядра. Хорошо известны эвристики для выбора пропускной способности. KDE - простой и предпочтительный выбор для одномерных данных.

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

Answer 2

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

Для обнаружения аномалий на основе распределения вы должны подобрать модель, которая соответствует вашему конкретному набору проблем. Например, если вы должны знать, что ваш набор данных нормально распределен (общий подход, вы можете проверить, следует ли это, например, используя QQ-plot), вы можете использовать нормальное распределение, чтобы получить вероятность того, что точка данных будет частью вашего набора данных. Затем вы устанавливаете границу (обычно ~0,05) и классифицируете точку как выброс, если вероятность того, что точка будет частью набора данных, меньше 0,05.

Как вы знаете, одно только K-средство не является алгоритмом обнаружения аномалий, даже если бы вы нашли хороший набор центроидов (в вашем примере 0,5 просто классифицировался бы в том же кластере, что и 0,45), вам все равно понадобится дискриминационный аргумент (как упомянутое ранее или одно расстояние, основанное как локальный фактор выброса). Проблема с обнаружением выбросов на основе расстояния состоит в том, что обычно не удается объяснить, почему данные ведут себя так, как они.

В настоящее время вы не предоставляете нам достаточно информации о своей проблеме. Что вы можете сказать нам по вашим данным? Откуда это взялось? Есть ли у вас какие-либо предположения об этом? или вы можете сделать какие-либо гипотезы? Что ты уже пробовал? Как выглядит сюжет? и т.п.

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