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

直観的に言えば、カーブの両端を結ぶ直線を引いて寝かせ、その直線とカーブの間の距離が大きい地点を探すものと見ればよい。
| アルゴリズム:ニードル $\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。
上のような曲線が与えられているとき、ニードルポイントを一つだけ探すと次のようになる。
二つ探すと次のようになる。
三つ探すと次のようになる。
コード全文
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)))
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 ↩︎
