logo

📂アルゴリズム

曲線の屈曲点を検出する方法:ニードルアルゴリズム

概要

特に主成分分析などを行うときがそうだが、データサイエンス全般において曲線の屈曲点を探す機会は頻繁にありながらも、主観的でもある。主観的だからといって必ずしも悪いわけではないが、そのための代表的なアルゴリズムとしてニードルアルゴリズムKneedle algorithmが知られている。

アルゴリズム1

alt text

直観的に言えば、カーブの両端を結ぶ直線を引いて寝かせ、その直線とカーブの間の距離が大きい地点を探すものと見ればよい。

アルゴリズム:ニードル $\mathrm{Kneedle}(D, S)$
Inデータポイント $D = \lbrace (x_i, y_i) \rbrace_{i=1}^{n}$
感度 $S$
1.$D_s \gets \mathrm{Spline}(D)$# スムージング。省略してもよい。
2.for $i = 1, \cdots, n$ do
3.   $x_{\mathrm{sn}_i} \gets \dfrac{x_{s_i} - \min \lbrace x_s \rbrace}{\max \lbrace x_s \rbrace - \min \lbrace x_s \rbrace}$
4.   $y_{\mathrm{sn}_i} \gets \dfrac{y_{s_i} - \min \lbrace y_s \rbrace}{\max \lbrace y_s \rbrace - \min \lbrace y_s \rbrace}$
5.   $x_{d_i} \gets x_{\mathrm{sn}_i}$
6.   $y_{d_i} \gets y_{\mathrm{sn}_i} - x_{\mathrm{sn}_i}$
7.end for# 寝かせる過程
8.$D_{\mathrm{lmx}} \gets \lbrace (x_{d_i}, y_{d_i}) : y_{d_{i-1}} < y_{d_i},\ y_{d_{i+1}} < y_{d_i} \rbrace$# 局所最大値
9.$K \gets \emptyset$
10.for $(x_{\mathrm{lmx}_i}, y_{\mathrm{lmx}_i}) \in D_{\mathrm{lmx}}$ do
11.   $T_{\mathrm{lmx}_i} \gets y_{\mathrm{lmx}_i} - S \cdot \dfrac{\sum_{k=1}^{n-1} \left( x_{\mathrm{sn}_{k+1}} - x_{\mathrm{sn}_k} \right)}{n-1}$# 閾値
12.   for $j = i+1, \cdots, n$ do
13.     if $(x_{d_j}, y_{d_j}) \in D_{\mathrm{lmx}}$ then break
14.     if $y_{d_j} < T_{\mathrm{lmx}_i}$ then
15.       $K \gets K \cup \lbrace x_{\mathrm{lmx}_i} \rbrace$
16.       break
17.     end if
18.     if $y_{d_{j-1}} > y_{d_j} < y_{d_{j+1}}$ then
19.       $T_{\mathrm{lmx}_i} \gets 0$
20.       break
21.     end if
22.   end for
23.end for
Outニードルポイントの集合 $K$

説明

ニードルアルゴリズムのKneedleは、膝を意味する英単語kneeと、干し草の山から針を探すという意味の「needle in a haystack」を混ぜた言葉遊びに由来する。

コード

書くのは難しくないが、わざわざ書く必要もない。例えばJuliaではKneedle.jlパッケージがあるので、それを持ってきて使えばよい2。

plot_87

上のような曲線が与えられているとき、ニードルポイントを一つだけ探すと次のようになる。

plot_88

二つ探すと次のようになる。

plot_89

三つ探すと次のようになる。

plot_90

コード全文

using Kneedle

x = 1:20
y = cumsum(1 ./ rand(20))

kr = kneedle(x, y)
knees(kr)
plot(x, y)
vline(plot(x, y), knees(kneedle(x, y, "convex_inc", 1)))
vline(plot(x, y), knees(kneedle(x, y, "convex_inc", 2)))
vline(plot(x, y), knees(kneedle(x, y, "convex_inc", 3)))

  1. Satopaa, V., Albrecht, J., Irwin, D., & Raghavan, B. (2011, June). Finding a" kneedle" in a haystack: Detecting knee points in system behavior. In 2011 31st international conference on distributed computing systems workshops (pp. 166-171). IEEE. https://doi.org/10.1109/ICDCSW.2011.20 ↩︎

  2. https://github.com/70Gage70/Kneedle.jl ↩︎