# Tag Info

7

Sure. There's a straightforward way to convert an unnormalized distance metric into a normalized similarity measure. Basically, use $$S(x,y) = \frac{M - D(x,y)}{M},$$ where $D(x,y)$ is the distance between $x$ and $y$, $S$ is the normalized similarity measure between $x$ and $y$, and $M$ is the maximum value that $D(x,y)$ could be. In the case of ...

5

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 to be $\mathsf{NP}$-complete) in polynomial time. Let $\langle X, t\rangle$ be an instance of subset-sum where $X = \langle X_1, \dots, X_n\rangle$ is a ...

3

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 predict the 220th. You'll have to evaluate how well this works on a test set; it might work, or it might not. This could still fail badly. It could even be that ...

3

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 sample data can be expressed as a function of time - maybe it helps to think of the "function" as the process that produces the measured output, the input to the ...

3

Consider that: a "sliding window" approach can be used with any standard regression / classification algorithm. E.g. given the following time series Time High Low Open Close Volume 1 H1 L1 O1 C1 V1 2 H2 L2 O2 C2 V2 ... i Hi Li Oi Ci Vi you can feed the ML algorithm with these examples: O0, H1, L1, O1, C1, V1, H2,...

2

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,j] = \min\{c(s_i,t_j) + A[i-1,j-k] : k=0,1,\dots,W\}.$$ If you consider $W$ a constant, then you obtain a $O(nm)$-time algorithm. I don't know if the factor ...

2

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 "refinement" of the $I,J$-intervals The $I$-intervals are not necessarily disjoint from the $J$-intervals. We want the $K$-intervals to have the following property:...

2

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 start time $i$, create a variable $x_i$ to hold the number of copies to start at this time and add the constraint $x_i \ge 0$. For each minute of time $i$ (now ...

2

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 for HMMs can be computed using dynamic programming. Be prepared that the more complex the model, the higher the likelihood will be, but that doesn't ...

2

 \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\sum_{k=0}^{\infty} k 2^{-k} \\ &\le 6\sum_{k=0}^{\infty} \left( \frac{3}{2} \right)^k 2^{-k} = 6 \sum_{k=0}^{\infty} \left( \frac{3}{4} \right)^k = 6 \...

2

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 variability that you could use in step 1: standard deviation, interquartile range, range (max minus min), median absolute deviation, and more. Any of these are ...

1

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 implementation, in R, there is auto ARIMA, which automatically takes the best suited valued for the parameters( p: The number of lag observations included in the ...

1

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[ ]$ and $q[]$ of size $T$. The array $q[]$ is initially filled with zero values. new(x, v): set $val[x] = v$ and increment each $q[y]$ with $y\ge x$ by $v$; ...

1

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 = { jhjhleapashljumpokdjklleaphfleapfjjumpacgd} Here the class 1 prototypes are polymorphic {walk OR pace}, and so is class 2 {leap or jump}. You can learn these ...

1

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 time $t$, remember the length of the longest window ending at time $t$ such that all values in the window are less than $X$. At time $t+1$, when you see the ...

1

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 programming (GP) is well suited to this sort of task since it makes no such assumptions. SR was one of the earliest applications of GP and continues to be widely studied. ...

1

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 the regression error (the sum of the squared error at each point; i.e., square of difference between model's prediction and observed value). You can use ...

1

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

1

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 the one that has the lowest distance (under either euclidean distance, or DTW, or both [b]) That degree of Uniform Scaling is then your prediction of the speed ...

1

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 signal X to signal Y, which last 3 minutes. It's possible that the best match might involve speeding up signal Y for the first minute, slowing it down for the ...

1

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 this is done you can use various graph path finding algorithms to find the sequence of actions to reach a specific state from a starting state.

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