Khiva

Khiva - high-performance time series algorithms - for Ruby

:fire: Runs on GPUs (even on Mac) and CPUs

Build Status

Installation

First, install Khiva. For Homebrew, use:

brew install khiva

Add this line to your application’s Gemfile:

gem 'khiva'

Getting Started

Calculate the matrix profile between two time series

a = Khiva::Array.new([11, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11], type: :f32)
b = Khiva::Array.new([9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 9], type: :f32)
m = 3 # subsequence length
profile, index = Khiva::Matrix.stomp(a, b, m)

Find motifs (repeated patterns)

n = 2 # number of motifs to extract
distances, indices, subsequences = Khiva::Matrix.find_best_n_motifs(profile, index, m, n)

Find discords (anomalies)

n = 2 # number of discords to extract
distances, indices, subsequences = Khiva::Matrix.find_best_n_discords(profile, index, m, n)

Examples

Anomaly Detection

Detect anomalies in a time series

# generate a random time series with anomalies from position 100-109
series = 1000.times.map { |i| i >= 100 && i <= 109 ? 0.5 : rand }

# calculate the matrix profile with subsequence length 10
a = Khiva::Array.new(series, type: :f32)
m = 10
profile, index = Khiva::Matrix.stomp_self_join(a, m)

# find and print the position of the most anomalous subsequence
_, _, subsequences = Khiva::Matrix.find_best_n_discords(profile, index, m, 1)
pos = subsequences.to_a.first
p pos

Use matplotlib.rb for visualization

require "matplotlib/pyplot"
plt = Matplotlib::Pyplot

# series
plt.figure(0)
plt.title("Series")
plt.plot(series)

# matrix profile
plt.figure(1)
plt.title("Matrix Profile")
plt.plot(profile.to_a)

# most anomalous subsequence and its closest subsequence
plt.figure(2)
plt.title("Subsequences")
plt.plot(series[pos, m], label: "Anomalous")
plt.plot(series[index.to_a[pos], m], label: "Closest")
plt.legend

Find a similar pattern in time series

series = [1, 1, 1, 3, 4, 1, 1, 1, 1]
query = [1, 2, 3]

s = Khiva::Array.new(series, type: :f32)
q = Khiva::Array.new(query, type: :f32)
_, indices = Khiva::Matrix.find_best_n_occurrences(q, s, 1)
pos = indices.to_a.first
similar_subsequence = series[pos, query.size] # [1, 3, 4]

Modules

Array

Create an array from a Ruby array

Khiva::Array.new([1, 2, 3])

Specify the type - :b8, :f32, :f64, :s16, :s32, :s64, :u8, :u16, :u32, :u64

Khiva::Array.new([1, 2, 3], type: :s64)

Get the type and dimensions

a.type
a.dims

Perform operations on arrays

a + b
a - b
a * b
a / b
a % b
a ** b

Compare arrays

a.eq(b)
a.ne(b)
a.lt(b)
a.gt(b)
a.le(b)
a.ge(b)

Clustering

k-means algorithm

centroids, labels = Khiva::Clustering.k_means(tss, k)

k-Shape algorithm

centroids, labels = Khiva::Clustering.k_shape(tss, k)

Dimensionality

Piecewise Aggregate Approximation (PAA)

Khiva::Dimensionality.paa(a, bins)

Perceptually Important Points (PIP)

Khiva::Dimensionality.pip(a, number_ips)

Piecewise Linear Approximation (PLA Bottom Up)

Khiva::Dimensionality.pla_bottom_up(a, max_error)

Piecewise Linear Approximation (PLA Sliding Window)

Khiva::Dimensionality.pla_sliding_window(a, max_error)

Ramer-Douglas-Peucker (RDP)

Khiva::Dimensionality.ramer_douglas_peucker(a, epsilon)

Symbolic Aggregate ApproXimation (SAX)

Khiva::Dimensionality.sax(a, alphabet_size)

Visvalingam

Khiva::Dimensionality.visvalingam(a, num_points)

Distances

Dynamic time warping (DTW) distance

Khiva::Distances.dtw(tss)

Euclidean distance

Khiva::Distances.euclidean(tss)

Hamming distance

Khiva::Distances.hamming(tss)

Manhattan distance

Khiva::Distances.manhattan(tss)

Shape-based distance (SBD)

Khiva::Distances.sbd(tss)

Squared Euclidean distance

Khiva::Distances.squared_euclidean(tss)

Features

Sum of square values

Khiva::Features.abs_energy(tss)

Absolute sum of changes

Khiva::Features.absolute_sum_of_changes(tss)

Aggregated autocorrelation

Khiva::Features.aggregated_autocorrelation(tss, aggregation_function)

Approximate entropy

Khiva::Features.approximate_entropy(tss, m, r)

Autocorrelation

Khiva::Features.auto_correlation(tss, max_lag, unbiased)

Auto-covariance

Khiva::Features.auto_covariance(tss, unbiased: false)

Binned entropy

Khiva::Features.binned_entropy(tss, max_bins)

Schreiber, T. and Schmitz, A. (1997) measure of non-linearity

Khiva::Features.c3(tss, lag)

Estimate of complexity defined by Batista, Gustavo EAPA, et al (2014)

Khiva::Features.cid_ce(tss, z_normalize)

Number of values above the mean

Khiva::Features.count_above_mean(tss)

Number of values below the mean

Khiva::Features.count_below_mean(tss)

Cross-correlation

Khiva::Features.cross_correlation(xss, yss, unbiased)

Cross-covariance

Khiva::Features.cross_covariance(xss, yss, unbiased)

Energy ratio by chunks

Khiva::Features.energy_ratio_by_chunks(arr, num_segments, segment_focus)

The spectral centroid (mean), variance, skew, and kurtosis of the absolute fourier transform spectrum

Khiva::Features.fft_aggregated(tss)

First location of the maximum value

Khiva::Features.first_location_of_maximum(tss)

First location of the minimum value

Khiva::Features.first_location_of_minimum(tss)

Maximum is duplicated

Khiva::Features.has_duplicate_max(tss)

Minimum is duplicated

Khiva::Features.has_duplicate_min(tss)

Any elements are duplicated

Khiva::Features.has_duplicates(tss)

Index of the mass quantile

Khiva::Features.index_mass_quantile(tss, q)

Kurtosis

Khiva::Features.kurtosis(tss)

Standard deviation above threshold

Khiva::Features.large_standard_deviation(tss, r)

Last location of the maximum value

Khiva::Features.last_location_of_maximum(tss)

Last location of the minimum value

Khiva::Features.last_location_of_minimum(tss)

Length of the series

Khiva::Features.length(tss)

Local maximals

Khiva::Features.local_maximals(tss)

Length of the longest consecutive subsequence above the mean

Khiva::Features.longest_strike_above_mean(tss)

Length of the longest consecutive subsequence below the mean

Khiva::Features.longest_strike_below_mean(tss)

Maximum

Khiva::Features.maximum(tss)

Mean

Khiva::Features.mean(tss)

Mean absolute change

Khiva::Features.mean_absolute_change(tss)

Mean change

Khiva::Features.mean_change(tss)

Mean of a central approximation of the second derivative

Khiva::Features.mean_second_derivative_central(tss)

Median

Khiva::Features.median(tss)

Minimum

Khiva::Features.minimum(tss)

Number of m-crossings

Khiva::Features.number_crossing_m(tss, m)

Number of peaks of at least support n

Khiva::Features.number_peaks(tss, n)

Partial autocorrelation

Khiva::Features.partial_autocorrelation(tss, lags)

Percentage of unique values present more than once

Khiva::Features.percentage_of_reoccurring_datapoints_to_all_datapoints(tss, sorted)

Percentage of values present more than once

Khiva::Features.percentage_of_reoccurring_values_to_all_values(tss, sorted)

Quantile

Khiva::Features.quantile(tss, q, precision: 100000000)

Count of values within the interval [min, max]

Khiva::Features.range_count(tss, min, max)

Ratio of values more than r sigma away from the mean

Khiva::Features.ratio_beyond_r_sigma(tss, coeff)

Ratio of unique values

Khiva::Features.ratio_value_number_to_time_series_length(tss)

Sample entropy

Khiva::Features.sample_entropy(tss)

Skewness

Khiva::Features.skewness(tss)

Cross power spectral density at different frequencies

Khiva::Features.spkt_welch_density(tss, coeff)

Standard deviation

Khiva::Features.standard_deviation(tss)

Sum of all data points present more than once

Khiva::Features.sum_of_reoccurring_datapoints(tss, sorted: false)

Sum of all values present more than once

Khiva::Features.sum_of_reoccurring_values(tss, sorted: false)

Sum of values

Khiva::Features.sum_values(tss)

If looks symmetric

Khiva::Features.symmetry_looking(tss, r)

Time reversal asymmetry

Khiva::Features.time_reversal_asymmetry_statistic(tss, lag)

Number of occurrences of a value

Khiva::Features.value_count(tss, v)

Variance

Khiva::Features.variance(tss)

If variance is larger than one

Khiva::Features.variance_larger_than_standard_deviation(tss)

Library

Get backend info

Khiva::Library.backend_info

Get current backend

Khiva::Library.backend

Get available backends

Khiva::Library.backends

Set backend - :default, :cpu, :cuda, :opencl

Khiva::Library.set_backend(:cpu)

Set device

Khiva::Library.set_device(device_id)

Get device id

Khiva::Library.device_id

Get device count

Khiva::Library.device_count

Set device memory in GB

Khiva::Library.set_device_memory_in_gb(1.5)

Get version

Khiva::Library.version

Linalg

Khiva::Linalg.lls(a, b)

Matrix

Find discords

distances, indices, subsequences = Khiva::Matrix.find_best_n_discords(profile, index, m, n)

Find motifs

distances, indices, subsequences = Khiva::Matrix.find_best_n_motifs(profile, index, m, n)

Find best occurences

distances, indices = Khiva::Matrix.find_best_n_occurrences(q, t, n)

Mueen’s Algorithm for Similarity Search (MASS)

distances = Khiva::Matrix.mass(q, t)

Calculate the matrix profile between ta and tb using a subsequence length of m with the STOMP algorithm

profile, index = Khiva::Matrix.stomp(ta, tb, m)

Calculate the matrix profile between t and itself using a subsequence length of m with the STOMP algorithm

profile, index = Khiva::Matrix.stomp_self_join(t, m)

Calculate the matrix profile between ta and tb using a subsequence length of m

profile, index = Khiva::Matrix.matrix_profile(ta, tb, m)

Calculate the matrix profile between t and itself using a subsequence length of m

profile, index = Khiva::Matrix.matrix_profile_self_join(t, m)

Get chains

Khiva::Matrix.chains(tss, m)

Normalization

Decimal scaling

Khiva::Normalization.decimal_scaling_norm(tss)
Khiva::Normalization.decimal_scaling_norm!(tss)

Max min

Khiva::Normalization.max_min_norm(tss)
Khiva::Normalization.max_min_norm!(tss)

Mean

Khiva::Normalization.mean_norm(tss)
Khiva::Normalization.mean_norm!(tss)

Znorm

Khiva::Normalization.znorm(tss)
Khiva::Normalization.znorm!(tss)

Polynomial

Least squares polynomial fit

Khiva::Polynomial.polyfit(x, y, deg)

Regression

Linear least squares regression

slope, intercept, rvalue, pvalue, stderrest = Khiva::Regression.linear(xss, yss)

Regularization

Khiva::Regularization.group_by(tss, aggregation_function, columns_key: 1, n_columns_value: 1)

Statistics

Covariance

Khiva::Statistics.covariance(tss, unbiased: false)

Kurtosis

Khiva::Statistics.kurtosis(tss)

Ljung-Box

Khiva::Statistics.ljung_box(tss, lags)

Moment

Khiva::Statistics.moment(tss, k)

Quantile

Khiva::Statistics.quantile(tss, q, precision: 1e-8)

Quantiles cut

Khiva::Statistics.quantiles_cut(tss, quantiles, precision: 1e-8)

Standard deviation

Khiva::Statistics.sample_stdev(tss)

Skewness

Khiva::Statistics.skewness(tss)

Khiva Installation

Linux - Ubuntu

Install ArrayFire:

sudo apt-key adv --fetch-key https://repo.arrayfire.com/GPG-PUB-KEY-ARRAYFIRE-2020.PUB
echo "deb [arch=amd64] https://repo.arrayfire.com/ubuntu $(. /etc/os-release && echo $VERSION_CODENAME) main" | sudo tee /etc/apt/sources.list.d/arrayfire.list
sudo apt-get update
sudo apt-get install arrayfire-unified3 arrayfire-cpu3-openblas arrayfire-opencl3-openblas

And install Khiva:

wget https://github.com/shapelets/khiva/releases/download/v0.5.0/khiva-khiva_0.5.0_amd64.deb
sudo dpkg -i khiva-khiva_0.5.0_amd64.deb
sudo ldconfig

Linux - Other

See instructions.

Mac

Run:

brew install khiva

Windows

See instructions.

Credits

This library is modeled after the Khiva-Python API.

History

View the changelog

Contributing

Everyone is encouraged to help improve this project. Here are a few ways you can help:

To get started with development:

git clone https://github.com/ankane/khiva-ruby.git
cd khiva-ruby
bundle install
bundle exec rake test