Подпоследовательности запроса в данных последовательности временных рядов

Я столкнулся с проблемой, и я чувствую, что есть решение в теории графов или базах данных графов. Мои знания в этих областях очень ограничены. Я надеюсь, что кто-то сможет распознать мою проблему и, возможно, указать мне название метода, использованного для ее решения.

Упрощенный пример:

Я имею дело с временными рядами состояний. Простой пример, где всего два состояния:

TS    State
t0    T
t1    F
t2    F
t3    F
t4    T
t5    T
t6    T
t7    F
t...  ...

Я мог бы преобразовать это в некоторый граф с двумя узлами (T и F), и где «время пребывания» в состоянии является атрибутом (в скобках):

T(1) -> F(3) -> T(3) -> F(1)

Пример моей проблемы - написать «запрос», который извлекает любую подпоследовательность, соответствующую этому шаблону F(>=2) -> T(<10). В моем примере выше мой запрос извлекал бы подпоследовательность: F(3) -> T(3)

Но если бы он присутствовал в наборе данных, запрос также мог бы извлекать такие последовательности, как:

F(2) -> T(8)
F(20) -> T(3)

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

`T(>2) -> [loops of F(1)->T(1)] -> T(<10)`

Где мой цикл, возможно, можно было бы ограничить, чтобы он не занимал более 10 итераций или не более 10 единиц времени. Глазурью на торте было бы найти такие последовательности

T(n)->F(<n)

Что переводится как: последовательности, которые начинаются с T (и остаются в T в течение n единиц времени), за которыми следует состояние F, где они остаются в F менее n ( т.е. F короче предыдущего T)

Что я пробовал:

Первоначально я думал преобразовать это в строку и использовать RegEx для извлечения совпадений. Regex может делать все, что мне нужно, но не может понять арифметику типа «больше чем». Думаю, я мог бы сохранить свои необработанные временные ряды состояний (TFFFTTTF) и сделать для этого регулярное выражение ... но это кажется довольно уродливым.

На ум приходят такие области, как Обработка естественного языка, Теория графов, Графические базы данных, как те, в которых были бы схожие проблемы. Я не знаю, как бы я закодировал атрибут «продолжительность состояния» в моем графике. Я не знаю, существует ли какой-то «стандартный» язык запросов для поиска подпоследовательностей в графовых базах данных.

Вопросы:

-Есть ли структура для решения этих проблем извлечения подпоследовательностей, если да, то как она называется? Есть ли «лучшая практика»? Как мне структурировать свои данные? Есть ли язык запросов для запроса подпоследовательностей в базе данных последовательностей?


nlp sequence graph-databases graph-theory graph-data-science
person Ant    schedule 28.05.2020    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Я мог бы решить проблему. Вы указали, что это данные временного ряда. Учитывая это, я мог бы создавать новый узел состояния каждый раз, когда состояние изменяется. Затем я закодировал бы время ожидания в предыдущем узле и связал бы новый узел с узлом предыдущего состояния, создав связанный список в базе данных графа. С такой структурой ваш шаблонный запрос становится простым.

Objectivity / DB - это основанная на схеме база данных объектов / графов с полным набором возможностей для запросов навигации по графам. У него есть собственный язык запросов, называемый декларативной объективностью или DO.

Начнем с определения схемы:

UPDATE SCHEMA { 
    CREATE CLASS State{
        label       : String,
        dwellTime   : INTEGER { Storage: B32 },               
        prev        : Reference { referenced: State, Inverse: next },
        next        : Reference { referenced: State, Inverse: prev}
    }           
};

Затем мы можем выполнить запрос DO следующим образом:

MATCH p = (:State {label == 'T' AND dwellTime > 5})
           -->(:State {label == 'F' AND dwellTime > 5})
           -->(:State {label == 'T' AND dwellTime < 2})
           -->(:State {label == 'T' AND dwellTime > 100})
           -->(:State {label == 'F' AND dwellTime > 100})
           RETURN p;

Этот тип запроса найдет все шаблоны TFTTF, которые соответствуют указанному времени ожидания.

person djhallx    schedule 27.02.2021