Skip to main content
4 votes

Finding the maximum sum series in time complexity of O(n)

There is no polynomial-time algorithm for your problem, unless $\mathsf{P}=\mathsf{NP}$. Suppose that such an algorithm $A$ exists. Then we can use $A$ to solve the subset-sum problem (which is known ...
Steven's user avatar
  • 29.5k
3 votes

Time Series Prediction with an LSTM

Yes, you could try applying the LSTM iteratively 20 times. In other words: use the first 200 datapoints to predict the 201th; then use datapoints 2..201 to predict the 202th; and so on, until you ...
D.W.'s user avatar
  • 162k
3 votes

Machine Learning: Identify Patterns in Time-Series Data

Yes, your data is "time-series data", since it's a sequence of measurements of the same variable collected over time. Time-series data can be collected continuously or at discrete intervals. Your ...
rphv's user avatar
  • 1,624
3 votes
Accepted

machine learning classification with financial instrument/time series data

Consider that: a "sliding window" approach can be used with any standard regression / classification algorithm. E.g. given the following time series ...
manlio's user avatar
  • 2,062
2 votes
Accepted

Optimize stacking time series by offsetting start times (feels like a backpack problem?)

I suspect this problem is NP-hard, but haven't been able to prove it. In any case, Integer Linear Programming (ILP) is a good way to solve it. Let $c_1, \dots, c_n$ be the series data. For each valid ...
j_random_hacker's user avatar
2 votes
Accepted

Compare Hidden Markov Model's sample with ground truth data

Compute the likelihood of the observed data, for each model. Then higher the likelihood, the better the fit. The likelihood is just the probability that the model assigns to the observed data, which ...
D.W.'s user avatar
  • 162k
2 votes
Accepted

Asymptotic growth of a series

$$ \begin{align*} \sum_{k=1}^{c \log n - 1} k 2^{- \frac{k}{3}} &\le \sum_{k=1}^{c \log n } k 2^{- \lfloor \frac{k}{3} \rfloor } \le \sum_{k=1}^{\lceil \frac{c}{3} \log n \rceil} 3k 2^{-k+1} \le 6\...
Steven's user avatar
  • 29.5k
2 votes
Accepted

Remove features with too little variation

Step 1. Identify a measure of variation for a feature. Step 2. Remove all features for which this measure is below some threshold (or is below that of msot other features). There are many measures of ...
D.W.'s user avatar
  • 162k
2 votes

How to optimize algorithm to solve the following time series problem?

First, apply the standard reduction: to solve a ratio maximization problem (sometimes called "fractional programming"), binary search on the solution $t$: $$ \max_x \frac{f(x)}{g(x)} \geq t \...
pcpthm's user avatar
  • 2,727
2 votes

Iterating over combinations of 4 timestamps from 2 timelines *efficiently*

Algorithm Step 1: Build the set of all possible distances from the first list, by enumerating all pairs of items from the first list and subtracting. Sort this set, and call $A$ the result. Step 2: ...
D.W.'s user avatar
  • 162k
2 votes
Accepted

How to efficiently code Dynamic Time Warping algorithm with a locality constrain?

There is a $O(nmW)$-time algorithm using dynamic programming. Let $A[i,j] = $ the cost of the best matching of $[s_1,\dots,s_i]$ to $[t_1,\dots,t_j]$ such that $s_i$ is matched to $t_j$. Then $$A[i,...
D.W.'s user avatar
  • 162k
2 votes
Accepted

Temporal alignment of two time series

OK. So the problem is as follows (with different notation): Inputs: disjoint intervals $I_1,\dots,I_k$; disjoint intervals $J_1,\dots,J_m$ Output: disjoint intervals $K_1,\dots,K_n$ that are a "...
D.W.'s user avatar
  • 162k
1 vote

Keywords for classification of 2D time series data?

The one-nearest neighbor classifier is very competitive for time series. http://www.cs.ucr.edu/~eamonn/ICML2006.pdf If you want code or data, I have lots of both. eamonn
eamonn's user avatar
  • 11
1 vote
Accepted

Efficient Way to Calculate Timebased Followership

Here is a pragmatic approach that is quadratic in principle but might be good enough in practice, depending patterns of employee movement from company to company. For each employee, enumerate all ...
D.W.'s user avatar
  • 162k
1 vote

Finding overlapping time under distance condition

Sort the records for each person, by increasing timestamp. Given a pair of people, you can merge the sorted list of records for each of those two people, and then do a linear scan over that sorted ...
D.W.'s user avatar
  • 162k
1 vote

Getting speed difference between signal comparison using Dynamic Time Warping

DTW is designed to handling local changes in timing. Global changes is time are referred to as Uniform Scaling [a]. You can create a FOR loop, loop over all possible Uniform Scalings, and record ...
eamonn's user avatar
  • 11
1 vote

Getting speed difference between signal comparison using Dynamic Time Warping

There is no single "speed difference". The way DTW works is that it checks whether you can find a match by slowing up and/or speeding up one of the signals. For instance, suppose you want to match ...
D.W.'s user avatar
  • 162k
1 vote

Predicting next action to take to reach a final state

You can represent the problem as a directed graph where the nodes are the states and the edges are the action that signifies the transition from one state to another if the action is performed. Once ...
Ankur's user avatar
  • 628
1 vote
Accepted

an algorithm for detecting if noisy univariate data is constant or is sum of step functions

Every possible observation is consistent with a sum of step functions: one can use one step function per data point and fit any possible sequence of observations. So, the question is not well-posed. ...
D.W.'s user avatar
  • 162k
1 vote

Which time series prediction techniques are useful given harmonic properties?

I would suggest to make the correlation plot and observe the dependencies. Yes, ARIMA, is so far the best forecasting model for time series and it should work in this data set too. For the ...
SiluPanda's user avatar
  • 549
1 vote

Constant time range sum query

If the timestamps can take $T$ different values, then it is simple to implement the new, update, and delete operations in time $\Theta(T)$ and the query in time $O(1)$, by maintaining two arrays $val[ ...
Vincenzo's user avatar
  • 3,317
1 vote

How to evaluate the learned prototypes for multivariate time-series (e.g. motion)?

You note " but with more than one prototype per class/cluster." We often call this a polymorphic class. Consider the analogue in text.. C1 = { dpacekfjklwalkflwalkklpacedalyutekwalksfj} C2 = { ...
Eamonn Keogh's user avatar
1 vote
Accepted

Finding a subarray of time series data in which all values are less than X for specified time Y?

You don't need a clever or sophisticated algorithm. It suffices to linearly scan through the time series, in chronological order, and keep track of the length of window of values less than $X$. At ...
D.W.'s user avatar
  • 162k
1 vote

How can I fit a sine function to a SVR?

You could try symbolic regression (SR). The general idea is finding a function that fits the given data points without making any assumptions about the structure of that function. Genetic ...
manlio's user avatar
  • 2,062
1 vote

How can I fit a sine function to a SVR?

Use nonlinear regression: https://en.wikipedia.org/wiki/Nonlinear_regression. Write down a model, e.g., $f(x) = \sin(\alpha x + \beta)$, and then try to find parameters $\alpha,\beta$ that minimize ...
D.W.'s user avatar
  • 162k

Only top scored, non community-wiki answers of a minimum length are eligible