Сучасна диджитал-освіта для дітей — безоплатне заняття в GoITeens ×
Mazda CX 5
×

Отобрать данные до первого скачка

Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті

Привет, подкинте идею. Туплю что-то:
есть такие данные
dd =

0
0
0
0
0
0.000000000000007
0.000000000000007
0.000000000000007
0.000000000000007
0.000000000000010
0.000000000000010
0.000000000000010
0.000000000000016
2.633178105165787
2.633178105165793
2.680338721029984
2.680338721029991
3.144253292363524
3.144253292363535
3.455539083982646
3.455539083982655
3.873979942104087
3.873979942104087
4.528412667307488
4.528412667307488
5.056041061279163
5.441634246240676
5.758589072778007
5.758589072778007
6.137339061337809
6.137339061337809
7.989230919664730
7.989230919664736
8.191873370806375
8.191873370806375
8.402427059525337
9.707983670817743
10.562709034023758
11.427275957156656
Нужно выбрать только те, что до резкого скачка
Т.е. Первые 13

Данные не всегда такие красивые, но скачок всегда есть.
И это не временной ряд, все данные есть на входе.
Пока две идеи пробовать через кластеризацию (но надо как-то определиться с порогом кластеризации) или через производную (опять же определиться с порогом) или через скользящие моменты распределения (но данных для построения устойчивого распределения мало).
Количество входных данных сравнимо с тем набором, что выше.
Пока останавливаюсь на правдоподобии. Вот такое получилось:
ll =

-13.105293350528012
-13.240609592596869
-13.659024651211627
-13.502098701675456
-13.206721834521678
-13.244738665313239
-13.505455978785387
-13.522732968941405
-13.511127567606469
-13.240789755371507
-13.798559548303617
-13.691555931493168
-13.573244341540235
6.603315646942734
3.875958591015428
3.075434849768514
2.633776258214172
2.905142429691629
2.608936961044623
2.720330126389209
2.523698354592342
2.752623121883026
2.583559961695585
3.006005956547924
2.816568868585229
3.091584938154992
3.214691567946383
3.267418073769537
3.087376365394090
3.205942286026062
3.060299771500777
4.215112866901573
3.896308064346476
3.793002196063312
3.598083253479741
3.562127752295348
4.148456415309861
4.403440218679242
4.617387225517268

Выглядит неплохо.

👍ПодобаєтьсяСподобалось0
До обраногоВ обраному0
LinkedIn
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

— первый проход — ищешь максимум разницы между двумя соседними элементами
— второй проход — выводишь все элементы до найденного в первом цикле

я бы юзал кластеризацию по разнице

Тебе надо словить тренд, правильно? Иначе говоря, усреднить? Или скачёк ОЧЕНЬ резкий, такой что РАЗНИЦА выше средней разницы по N предыдущим?

Кластеризация — это понятно, это общая задача. Но у тебя, как мы помним, стоит задача производительности, а не только теоретически выполнить алгоритм. Итого — тебе просто нужен критерий этого скачка. Математический критерий.

Во-первых, данные у тебя сортированы. Или нет? Просто сортировка — процесс не быстрый на самом деле, и тебе гораздо выгоднее определиться с ТОЧНОСТЬЮ, по которой ты ловишь. Что ты делаешь: ты берёшь целочисленный показатель от 0 до 255, а то и побитово выдираешь ДВОИЧНЫЙ ПОРЯДОК из своего double, и по нему кластирезируешь или проводишь иную обработку (отсев, выборочную индексацию, оцениваешь среднее и отклонение).

Что ты получаешь таким способом:
1) быстро от 0 до 255 оцениваешь среднее и области (границы) расположения пиков, не теряя самих данных и не манипулируя ими. То есть быстро, конвейром, строишь или двоичное дерево, или гистограмму, или какую другую хрень. Обычно суть подобной задачи — отделить сигнал от шума.
2) Узнаешь, какие наборы данных вообще не нуждаются в обработке, где их результат грубо соответствует предсказанию, то есть там привычный шум и нехер ловить. Это даёт тебе сосредоточиться (выделить больше процессорного времени) на те матрицы, где сигнал есть.
3) Не паришься с кластеризацией. Тебе достаточно количественных показателей: среднее, СКО (или какая другая другая функция пошустрее). Нужно ли говорить, что эти показатели при однобайтной точности считаются крайне быстро. Особенно если сделаешь не абсолютный показатель, а логарифмический, тот самый двоичный порядок от double тебе как раз подойдёт.

Если не веришь — преставь свои числа в двоичном виде, в виде белых и чёрных точек вертикальным рядом. И красной точкой отметь местоположение плавающей точки. Сам увидишь, что место этой самой точки имеет решающее значение, и другого показателя тебе в принципе не нужно. В десятичном виде оно не так очевидно, что у тебя в руках уже есть готовый маркер кластеризации. И да, ты УЖЕ РАСПЛАТИЛСЯ за его получение, когда приводил показатели в double. Это ведь не бесплатная операция, и ты бы про это знал, если бы на вход брал RAW-данные с первоисточника.

А не переусложнили ли Вы себе задачу? Максимальное правдоподобие — там же могут возникнуть жесткие требования и ограничения, нарушение которых чревато искажанием результатов.
Просто взял да прокласстеризовал Ваши данные, методом построения дендорограмм и методом к-средних. Результат тождественен. Хотите на два кластера (это если Вам один скачек нужен), хотите — на несколько (если, например, будет «шаговое» изменение). На R делается в три строчки за три минуты. (Ну например, на три кластера получилось точки 1:13, 14:31, 32:39 — но легко можно и на большее число «шагов изменения»). Как бонус, можно и меры расстояния менять (хотя в Вашем случае это и не надо, но — а вдруг) и алгоритмы подстраивать, еще икартинки соотвествующие — при необходимости — рисовать.

Есть способы выбора количества кластеров для к-means. Ну а по дендрограмме — вообще сразу видно, где там большие скачки, а где нет и сколько их.
Про экспоненциальный рост — с правдоподобием надо быть крайне осторожным. Действительно, деление на основе макс. правдоподобия теоретически оптимальный (!) способ разделения выборок, при условии, что их распределения до и после скачка — нормальны и не меняется дисперсия. У Вас — эти требования нарушены.
А вообще-то одна из задач, которой я сейчас плотненько занимаюсь — выявления checkpoints в временных рядах при нарушении «всех мыслимых и немыслимых» :-) предварительных ограничениях. Похоже, правда? ;-)

Попробуй как то так (не могу проверить потому что нет матлаба):

[peaks, loc] = findpeaks(diff(data));


new_data = data(1:loc(1));

Ну, раз в условии задачи порог в определении не проблема, а требований по памяти и перформансу нет, а стримом не пахнет — можно грязно и «в лоб» на Spark 2.
Предполагаю что при дельте 0.0001 и более мы имеем порог

//rdd содержит ваш массив чисел
// см. sc.parallelize или sc.textfile или spark.read.csv........

val l = rdd.zipWithIndex.toDF("val","idx")
val r = rdd.zipWithIndex.map({case (v,i) => (v,i-1)}).toDF("val","idx")
val j = l.join(r, l.col("idx") === r.col("idx«), «left»)
.withColumn("delta", r.col("val")-l.col("val"))
.select(col("delta"),l.col("idx"))
.sort("idx")

val answer = j.collect.takeWhile(row => row.getDouble(0)<0.0001)

Если же интересует более оптимальное решение — то имхо просто проход по buffered stream.
Ну или просто мастер-методом в логарифм вложитсья:
www.geeksforgeeks.org/...​-a-peak-in-a-given-array

Ну или туплю я, предлагая вам наивности :)

Опять-таки, если идти «в лоб» через Spark, а порог нужно определить динамически — rdd.mean, rdd.stddev будут в помощь

Ще б було не погано дати визначення, що таке «стрибок» в рамках даної задачі.

І що буде стрибком, наприклад в такому ряду:
5
7
9
11

Якщо послідовність неспадна, чому б не обчислити частки від ділення сусідніх пар послідовності та знайти серед них максимум. Це і буде шуканим «скачком».

Підписатись на коментарі