распознавать уровни данных 1D, зная только количество уровней
Привет, ребята,
У меня есть датчик, который выводит данные состоит из одного атрибута (моно значение). Пример набора последовательных данных выглядит следующим образом:
образец:
199
200
205
209
217
224
239
498
573
583
583
590
591
594
703
710
711
717
+719
721
836
840
845
+849
855
855
+856
+857
+858
+858
928
+935
+936
+936
+942
+943
+964
+977
Вы можете увидеть данные с первого изображения вход.
Данные делятся на уровни. Количество уровней дано для меня (5 уровней в этом примере). Тем не менее, количество выборок для каждого уровня неизвестно, а также расстояния между уровнями также неизвестны.
Мне нужно исключить выбросы и определить центр каждого уровня (посмотрите на второе изображение выход.
Красные образцы представляют выбросы, а желтые представляют центры уровней). Есть ли какой-либо алгоритм, математическая формула, код C ++ может помочь мне выполнить это требование?
Я попробовал KMeans (с K = 5 в этом примере), и я получил плохой результат из-за случайных начальных K центроидов. В большинстве случаев некоторые первичные центроиды имеют один и тот же уровень, что позволяет этому уровню стать двумя кластерами, тогда как два других уровня принадлежат одному кластеру. Если я установлю начальные центроиды вручную, выбрав один центроид с каждого уровня, я получу очень хорошие результаты.
Любая помощь будет оценена!
Решение
Это продолжение ответа @KarthikeyanMV. +1. Да, вы должны быть в состоянии определить значение для Delta. Вот процесс, который сделает это. Я пишу свой код на R, но думаю, что процесс будет понятен.
Предположительно, разрывы между группами больше, чем разрывы в любой группе, поэтому просто посмотрите на разницу между последовательными точками и спросите, где большие разрывы. Поскольку вы считаете, что должно быть 5 групп, должно быть 4 больших пробела, так что посмотрите на 4-ую самую большую разницу.
## Your data
dat = c(199, 200, 205, 209, 217, 224, 239, 498, 573, 583,
583, 590, 591, 594, 703, 710, 711, 717, 719, 721,
836, 840, 845, 849, 855, 855, 856, 857, 858, 858,
928, 935, 936, 936, 942, 943, 964, 977)
(Delta = sort(diff(dat), decreasing=TRUE)[4])
[1] 75
это похоже Дельта должна быть 75, но мы не смогли учесть выбросы. Есть ли какие-либо точки, которые больше, чем Delta, как в следующем пункте выше? а также ниже? Да.
BigGaps = diff(dat) >= Delta
(Outliers = which(c(BigGaps, T) & c(T, BigGaps)))
[1] 8
Пункт 8 слишком далеко, чтобы принадлежать к группе выше или ниже. Итак, давайте удалим его и попробуем еще раз.
dat = dat[-Outliers]
(Delta = sort(diff(dat), decreasing=TRUE)[4])
[1] 70
BigGaps = diff(dat) >= Delta
(Outliers = which(c(BigGaps, T) & c(T, BigGaps)))
integer(0)
После того, как мы удалим точку 8, новая дельта равна 70. Мы проверяем выбросы, используя новую дельту (70), и не находим ничего. Итак, давайте кластеризуем, используя Delta = 70.
Cluster = cumsum(c(1, diff(dat)>=Delta))
plot(dat, pch=20, col=Cluster+1)
В основном это кластеры, которые вы хотите Кроме что он включает в себя последние две точки в самом высоком кластере, а не объявляет их выбросами. Я не понимаю, почему они должны быть выбросами, а не частью этой группы. Может быть, вы могли бы уточнить, почему вы думаете, что они не должны быть включены.
Я надеюсь, что это помогает.
Другие решения
если разница между двумя последовательными точками данных превышает определенное значение (рассмотрим это как Delta), то оно относится к другому кластеру.
для этого набора данных: 199 200 205 209 217 224 239 498 573 583 583 590 591 594 703 710 711 717 719 721 836 840 845 849 855 855 856 857 858 858 928 935 936 936 942 943 964 964 977 977
предположим, что дельта равна 15 (точная настройка на основе датчика), если разность последовательных точек данных не превышает 15, то они принадлежат одному кластеру. Вы можете найти центральную точку, найдя среднее значение кластера.
если точка имеет близлежащую точку с разницей дельты, то это можно рассматривать как выброс. Другие варианты: мы можем варьировать дельту на основе текущего значения набора данных.
Я бы предложил DBSCAN вместо K-Means.
Это алгоритм кластеризации на основе плотности, который группирует точки данных, которые находятся в той же близости друг к другу, без необходимости определять начальные k или центроиды, такие как K-средние.
В DBSCAN расстояние и k-соседи определяются пользователем.
Если вы знаете, что индекс имеет постоянный интервал, DBSCAN может подойти для решения вашей проблемы.
Я заметил, что эти уровни выглядят как линии. Вы могли бы сделать что-то подобное:
1. sort the points
2. take the first two unprocessed points into an ordered set called the current line
3. lay a line between the first and last point of the set
4. test whether the line formed by the first point and the next unprocessed point
form a line that has an angle lower than some threshold to the other line
5. If yes, add the point and go to 3
6. If no, store the current line somewhere and start again at 2
Вы также можете начать с проверки, имеют ли первые две точки такой линии угол к оси x, который находится выше другого порога, и, если это так, сохранить первую точку как нечто особенное. Выбросы.
Другой вариант будет идти только по углу соединения двух точек с осью X. При изменении уровня будет гораздо больший угол (наклон, уклон), чем между двумя точками на уровне.