折れ線グラフの特徴を損なわずに簡略化する方法

SKYDIV Desktop Clientのパフォーマンス確認機能において、折れ線グラフの特徴を損なわずにデータを簡略化する方法について説明しています。特に、Largest Triangle Three Bucketsアルゴリズムを用いたダウンサンプリング手法を紹介し、その利点とデメリットについて解説しています。

本日はSKYDIV Desktop Clientの機能に利用されている折れ線グラフの特徴を損なわずに簡略化する方法 について紹介いたします。

１．機能の概要と実現にあたる課題

これはSKYDIVのパフォーマンス確認機能の画面です。

パフォーマンス確認機能はサーバーのCPU使用率やメモリ使用量について
時間ごとに折れ線グラフで表現しますが、 1週間分のデータは何万プロット分もあるため、そのままのデータを処理して描画すると非常に処理コストがかかってしまいます。 (さらに、グラフをたくさん表示する必要もあります。)

２．機械的に簡略化するとグラフの特徴が失われる

SKYDIV Desktop Clientのパフォーマンス確認機能では、それほど大きな領域にグラフを描画しないためデータを間引く必要がありますが、下記のようなサンプルデータを・・・

機械的にプロットを1/10に間引きます。

このように、機械的に間引くとピーク値が採用されない場合が発生するため折れ線グラフの特徴が失われるのです。 （データを間引くことを界隈では「ダウンサンプリング」とも表現します）

３．特徴を失わずにデータを間引く

そのためSKYDIVでは折れ線グラフのような時系列のデータプロットを間引く方法として Largest Triangle Three Bucketsというアルゴリズムを採用しました。

アルゴリズムを簡単に説明します。
①データを分割する
たとえば10,000個あるプロットデータを1500個まで間引くなら20個ずつのデータ集合に分割します。 ※最終的に集合内から3点採用するので、最終的なプロット数/3で元データを割ってデータ分割単位を求める必要があります。

②分割したグループ内で3点の組み合わせを全通り作成する
前述の20個のプロットデータ集合(P1～P20)から3個ずつ組み合わせて、

S1：(P1,P2,P3) S2：(P1,P2,P4) S3：(P1,P2,P5) ・・・ S1140(P18,P19,P20)
※順番は関係ないので20C3で合計1,140個のプロット集合になります
⇒20!/{(20-3)! * 3!}=1140

③それぞれの面積を計算します。
Shoelace公式を使って下記のようにそれぞれのプロット集合（三角形）の面積を計算します。
//C++での三角形の面積計算
double calculateTriangleArea(const Point& p1, const Point& p2, const Point& p3) { return 0.5 * std::abs(p1.x * (p2.y - p3.y) + p2.x * (p3.y - p1.y) + p3.x * (p1.y - p2.y)); }

④プロット集合のうち面積が最大となる3点を採用

①で分割したデータに対して②～④を繰り返しますが繰り返し時の2つ目以降のポイントデータセットの左点は直前のデータセットで確定した右点座標を設定して3座標データセットを作る必要があります。

４．実際にデータを間引いて簡略化する

それではLargest Triangle Three Buckets アルゴリズムを利用してデータを間引いて簡略化しましょう！
※サンプルプログラムはCSVファイルからプロットを読み取り、指定したデータ数までLargest Triangle Three Bucketsでプロットデータを間引いてCSVファイルに保存し、Excelでグラフ化しています。

こちらはCPU使用率1週間分の45000プロットです。（X軸は600ピクセル程です。）