ダウンサンプリング

データ群からデータを間引く「ダウンサンプリング（Downsampling）」には様々な手法があります。
今回は 時系列データ の 可視化表現（折れ線グラフ）のためのダウンサンプリングアルゴリズム Largest Triangle Three Buckets を紹介します。

ダウンサンプリングを行うことで、データの通信量やグラフの生成時間を削減することができます。

Largest Triangle Three Buckets (LTTB)

Largest Triangle Three Buckets（以下、LTTB）はSveinn Steinarsson氏の書いた論文
Downsampling Time Series for Visual Representation
に掲載されています。

本人のgithubにFlotでLTTBを使うためのプラグインが置いてあります。
https://github.com/sveinn-steinarsson/flot-downsample
他にもC#, Elixir, Go, node.js, Java, Scala, R, Javascript, PHP, Python, Perl, C++, Ruby, Swift, Rustのライブラリへのリンクもgithubに乗ってます。

実際使うとどうなるか

実際に1日の温度データをLTTBでダウンサンプリングしたのが下の画像です。一番上のデータがオリジナルデータ、その下3つがLTTBによってダウンサンプリングされたデータです。右列は元のデータを10分単位(上)または1時間単位(下)で平均してデータ点数を減らしたグラフです（比較用）。

平均によるダウンサンプリング(右)に比べてLTTBによるダウンサウンプリング(左)の方が元のグラフの見た目を保っているのが分かります。

アルゴリズムの使い方

データの配列とthreshold（整数）を与えると、サンプリングされたデータが得られます。
thresholdがサンプリング後のデータ点数になります。
データ群の最初の点と最後の点はサンプリング後も必ずプロットされます。
thresholdの最大値は元のデータ点数、最小値は2です。（threshold=2の場合、最初の点と最後の点を結んだ線になります）

アルゴリズムの使い方（サンプル）

各言語によって多少差異はありますが、基本は（時刻,値）のデータ配列とthresholdを渡すとサンプリングデータが返される関数が用意されています。
あとデータ配列が時刻でソートされていること前提のものが多い気がします。

サンプルとして実際に使ったコードを以下に書いておきます。

Javascript

// largest-triangle-three-buckets.v0.1.0.min.jsを読み込んだ状態

const datasource = [
  {"datetime": "2019-04-27 00:00:15", "value": 18.5},
  {"datetime": "2019-04-27 00:01:15", "value": 18.6},
  ...（省略）...
];

// 日時をDateオブジェクトに変換する
const dataset = datasource.map( d => ({ "datetime": new Date(d.datetime), "value": d.value }) );

// largestTriangleThreeBuckets(data, threshold, xAccessor, yAccessor)
const sampledDataset = largestTriangleThreeBuckets(dataset, 144, "datetime", "value");

Highcharts用プラグインや Chart.js用プラグインもあります。

Python

https://github.com/devoxi/lttb-py
（Python3専用）

from lttb import largest_triangle_three_buckets
from datetime import datetime

datasource = [
  ("2019-04-27 00:00:15", 18.5),
  ("2019-04-27 00:01:15", 18.6),
  ...（省略）...
]

# 日時をUNIX時間に変換する
dataset = []
for d in datasource:
  dataset.append((datetime.strptime(d[0], "%Y-%m-%d %H:%M:%S").timestamp(), d[1]))

# largest_triangle_three_buckets(data, threshold)
sampled_dataset = largest_triangle_three_buckets(dataset, 144)

Numpy用のライブラリもあります。

アルゴリズムの説明

Downsampling Time Series for Visual Representation（リンク先はアイスランド語ですが論文は英語で書かれています）

簡単に言うとLTTBはVisvalingam–Whyatt Algorithmの概念を使って時系列データを なるべく見た目を保ったまま 効率的にダウンサンプリングするためのアルゴリズムです。

メリット・デメリットおよび利用シーン

数個のパラメーターを渡すだけで扱うことができ、非常に便利なアルゴリズムだと思います。
ですが、以下にあげるデメリットから用途が絞られるアルゴリズムでもあります。

メリット

ピークの値を保ったままサンプリングしてくれる。
細かく上下に振れるデータをサンプリングしても見た目で振れてることが分かりやすい。（平均によるダウンサンプリングだと平坦なグラフになってしまう）

デメリット

あくまで見た目重視の間引きアルゴリズムなので、サンプリングしたデータを使って何らかの解析をしたりするのは御法度。（平均によるダウンサウンプリング結果は「平均した値」としての利用価値があるが、LTTBによるダウンサウンプリング結果には「グラフにした時に見た目が元のデータに近い」という価値しかない）
以上の理由からグラフでよくある「マウスを点に近づけると、その点のデータが表示される」などの見せ方も避けた方がいい。（折れ線グラフ＋各点に丸印のような見せ方も避けたい）

軽量なサムネイル画像のような感じで「漠然と元のグラフの形が分かる軽量なグラフ」を作る際に非常に便利なダウンサンプリングアルゴリズムですが、グラフから具体的な（もしくは意味のある）値を読み取ることは難しくなりますので、利用シーンを考えて使っていきたいアルゴリズムです。

グラフのデータをいい感じに間引くLargest Triangle Three Bucketsアルゴリズム