apache / apache/otava

Push window_len down into the core e-divisive computation

Open
#84 1 comment 0 reactions 0 assignees View on GitHub
Dominant language
Python
Stars
177
Forks
35
Avg merge
3d 16h
Merged PRs (30d)
6

Description

In Otava, Piotr introduced window_len as a user facing parameter, and for a given data point, only `window_len/2` data points are included in the computation. This gives better quality results, in particular it makes it possible to find two adjacent change points. This is because computation is focused on the local neighborhood of each candidate change point, and data points far away are completely ignored.

In Piotr's version, the input data is split into `2*datapoints/window_len` windows and the regular e-divisive is run on each window. After this there is a process to merge the small windows together. The windows also overlap, so the same point could be found once or twice, with different p-value for each.

Mathematically it would be more elegant, and consistent, and potentially also a performance improvement (because we don't count every point twice because no need for overlap) to rather just do a single pass, as in the original e-divisive, but incorporate window length into the core e-divisive code. This could be something like this:

https://github.com/mongodb/signal-processing-algorithms/blob/74d6a8fa3a377ee5dce4821ba9dfd2f2528790b2/src/signal_processing_algorithms/e_divisive.py#L222-L250

length = window_len
n = 1 # Note: this is 2 in the quoted code, but that is unnecessarily conservative.
w_start = max( n - window_len / 2, 0)
w_stop = min( n + window_len / 2, len(series) )
m = w_stop - n

# term1 = sum(diffs[i][j] for i in range(w_start, n) for j in range(n, w_stop))
term1 = np.sum(diffs[w_start:n, n:w_stop])

# term2 = sum(diffs[i][k] for i in range(w_start, n) for k in range(i + 1, n))
term2 = np.sum(np.triu(diffs[w_start:n, w_start:n], 0))

# term3 = sum(diffs[j][k] for j in range(n, w_stop)
# for k in range(j + 1, w_stop))
term3 = np.sum(np.triu(diffs[n:w_stop, n + 1 : w_stop], 0))

qhat_values[n] = self.calculate_q(term1, term2, term3, m, n)

for n in range(3, (length - 2)):
w_start = max( n - window_len / 2, 0)
w_stop = min( n + window_len / 2, len(series) )
m = w_stop - n

# TODO: may need a +1 and / or -1 somewhere
column_delta = np.sum(diffs[n - 1, w_start : n - 1])
row_delta = np.sum(diffs[n:w_stop, n - 1])

term1 = term1 - column_delta + row_delta
term2 = term2 + column_delta
term3 = term3 - row_delta

qhat_values[n] = self.calculate_q(term1, term2, term3, m, n-w_start)

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.