По учёбе возникла такая задачка, есть заданная таблицей функция f(t), строго говоря, равноотстоящий временной ряд. Информации много, десятки миллионов значений. Нужно находить определённым образом "похожие" участки этого временного ряда, причём участки небольшой фиксированной длины L (L порядка 10-40). С ходу придумал следующий алгоритм: заводим множество "кластеров", изначально оно пустое. Затем каждый следующий кусочек нужной длины пытаемся засунуть во все кластеры. Мы можем это сделать, если он подходит по определённым критериям, т. е. похож на объекты в кластере (сейчас я использую просто среднеквадратичное отклонение). Если "объект" не совпал ни с одним из кластеров, создаём новый кластер с единственным объектом в нём.
У этого метода много недостатков, но самое главное: считается всё по несколько часов. Я знаю, многие здесь работают в проектах, связанных с анализом данных и т. п. Знатоки, пожалуйста, подкиньте пару идей, а ещё лучше помогите найти хорошую литературу по моей разновидности кластерного анализа (можно на английском).
Хеш?
Сорри, не правильно угадал, что такое "похожие".
upd: ниже написана неправда
Если допустимо считать "похожими" участки, соответствующие элементы которых отличаются не более, чем на некоторую величину eps, можно округлить значения функции до этой величины и сравнивать участки точно, с помощью хешей.
А как округлять?
Например, так: [x/eps]*eps.
Eps/2 3/2eps. Это вроде 0 и 1.
Не понял, что имеется в виду.
Проверить две функции eps/2 и 3/2eps. Твоя величина это 0 и 1. Что-то не так
Да, согласен, ошибся.
Нет, хеш не подходит. Отвечу ещё внизу, может недостаточно ясно объяснил, что требуется.
Вот такую статейку нагуглил: Fast subsequence matching in Time-Series Databases. По Abstract — вроде похоже. Надеюсь чем-нибудь поможет или послужит какой-то отправной точкой (гуглинг по словам subsequence in Time-Series Databases дает еще статьи).
Спасибо, вроде близко к тематике, почитаю)
А что есть "похожесть" из модели? СКО/угол между векторами/... ?
Задачу кластеризации на 10м векторов длины 10-40 решать вроде просто ужасно.
Потом, участки — это подстроки такой длины?
Дальше, нужно проверить векторы на редукцию, нужны статистические характеристики в задаче. Что вообще представляют из себя отсчеты? Может быть, можно провести предварительную кластеризацию, сведя задачу к одномерной/двумерной?
Предварительную кластеризацию провести не получается, слишком много может быть разных кластеров.
Похожесть я измеряю просто как среднеквадратичное отклонение (немного модифицированное) между "эталонным" объектом кластера и текущим объектом. Если оно меньше какого-то значения, значит объект "похож" на эталонный. Чисто визуально, на удивление, работает хорошо. Можно считать и как угол между n-мерными векторами, сути это не меняет. Возможно есть более эффективные критерии, но я их ещё не исследовал.
Отсчёты — числа с плавающей точкой в общем случае. Пробовал округлять и считать в целых кое-что, но проблема всё-равно в подходе, асимптотика приближается к размерности входных данных в квадрате.
Я бы порекомендовал забыть о том, что это временной ряд и решать задачу отдельно для каждой размерности. В этом случае вам нужно кластеризовать 10^7 векторов в пространстве фиксированной размерности. Для этого придумано достаточно много стандартных алгоритмов. Если я правильно понимаю и вас интересует возможность найти несколько самых популярных кластеров, то можно воспользоваться http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D1%81%D0%B5%D0%BC%D0%B5%D0%B9%D1%81%D1%82%D0%B2%D0%B0_FOREL — это один из самых простых с точки зрения реализации алгоритмов такого рода