1
\$\begingroup\$

I want to search for a pattern in a time-series while either ignoring the mean/shift/bias or the scale/standard deviation.

Consequently, I've written two functions.

The first function searches passes through the time-series, incrementally calculating the mean for each search-space sub-sequence and using this mean to normalize the sub-sequence before comparing it to a normalized query.

function euc_dist(data::Vector{Float64}, query::Vector{Float64}, current_best::Float64)::Float64
    sum = 0

    for (dd, qq) in zip(data, query)
        sum += (dd - qq) ^ 2
        if sum >= current_best
            break
        end
    end

    return sum
end


function run_ignore_bias(data::Vector{Float64}, query::Vector{Float64})::Tuple{Float64, Int}
    m = length(query)

    # normalize query in same manner data sub-sequence will be normalized
    query = query .- (sum(query) / m)

    current_best = Inf
    loc = -1

    # Keep current data in a double-size array to avoid using modulo
    # Basically, the data is stored twice and weird indexing arithmetic is used to avoid
    # using a LIFO queue and negative indexing.
    # Computational efficiency benefit unclear.
    t = zeros(Float64, 2*m)
    tz = zeros(Float64, m)

    run_sum = 0.
    run_sum2 = 0.

    for (d_i, dat) in enumerate(data)
        run_sum += dat
        run_sum2 += dat ^ 2

        t_idx = ((d_i - 1) % m) + 1
        t[t_idx] = dat
        t[t_idx + m] = dat

        if d_i >= m
            run_mean = run_sum / m

            # offset for search-space data
            s_off = (d_i % m) + 1
            # offset for search-space bound data
            s_bound_off = (d_i - 1) - (m - 1) + 1

            tz = t[s_off:s_off + m - 1] .- run_mean
            dist = euc_dist(tz, query, current_best)

            if dist < current_best
                current_best = dist
                loc = s_bound_off
            end

            run_sum -= t[s_off]
            run_sum2 -= t[s_off] ^ 2
        end
    end

    return sqrt(current_best), loc
end

The second function does the same, except it normalizes according to the standard deviation.

function run_ignore_scale(data::Vector{Float64}, query::Vector{Float64})::Tuple{Float64, Int}
    m = length(query)

    # normalize scale query
    q_mean = sum(query) / m
    query = query / sqrt(sum(query.^2)/m - q_mean^2)
    current_best = Inf
    loc = -1

    # Keep current data in a double-size array to avoid using modulo
    # Basically, the data is stored twice and weird indexing arithmetic is used to avoid
    # using a LIFO queue and negative indexing.
    # Computational efficiency benefit unclear.
    t = zeros(Float64, 2*m)
    tz = zeros(Float64, m)

    run_sum = 0.
    run_sum2 = 0.

    for (d_i, dat) in enumerate(data)
        run_sum += dat
        run_sum2 += dat ^ 2

        t_idx = ((d_i - 1) % m) + 1
        t[t_idx] = dat
        t[t_idx + m] = dat

        if d_i >= m
            run_mean = run_sum / m
            # occasionally, a floating point error can cause this value to be negative, thus take the absolute value before sqrt
            run_std = sqrt(abs((run_sum2 / m) - (run_mean^2)))

            # offset for search-space data
            s_off = (d_i % m) + 1
            # offset for search-space bound data
            s_bound_off = (d_i - 1) - (m - 1) + 1

            tz = t[s_off:s_off + m - 1] / run_std
            dist = euc_dist(tz, query, current_best)
            @assert dist > 0

            if dist < current_best
                current_best = dist
                loc = s_bound_off
            end

            run_sum -= t[s_off]
            run_sum2 -= t[s_off] ^ 2
        end
    end

    return sqrt(current_best), loc
end

Here are the tests for both functions.

using Test

@testset "ignore bias" begin
    sig = [.2, .3, .5, -.4, .2, .3]
    data = vcat(zeros(2), sig .+ 1., zeros(8), 2*sig, zeros(4))
    val, idx = run_ignore_bias(data, sig)
    # should find shifted signal, but not scaled signal
    @test idx == 3
    @test isapprox(val, 0., atol=0.001)
end


@testset "ignore scale" begin
    sig = [.2, .3, .5, -.4, .2, .3]
    data = vcat(zeros(2), sig .+ 1., zeros(8), 2*sig, zeros(4))
    val, idx = run_ignore_scale(data, sig)
    # should find scaled signal, but not shifted
    @test idx == 17
    @test isapprox(val, 0., atol=0.001)
end


@testset "dist calc" begin
    dist = euc_dist([1., 2., 3.], [4., 5., 6.], Inf)
    @test isapprox(dist, 27.0, atol=0.001)

    dist = euc_dist([1., 2., 3.], [4., 5., 6.], 8.)
    @test isapprox(dist, 9.0, atol=0.001)
end

How do I reduce the code duplication between these two functions?

\$\endgroup\$

This question has an open bounty worth +100 reputation from Seanny123 ending in 5 days.

This question has not received enough attention.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.