곡선에서 꺾인 지점을 탐지하는 방법: 니들 알고리즘
개요
특히 주성분분석 등을 할 때 그렇지만, 데이터과학 전반에서 곡선의 꺾인 지점을 찾을 일은 자주 있으면서도 주관적이기도 하다. 주관적이라서 꼭 나쁜 건 아니지만 이를 위한 대표적인 알고리즘으로 니들 알고리즘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"을 섞은 말장난에서 유래했다.
코드
짜기 어렵지는 않은데 굳이 짤 것도 없다. 예로써 줄리아에서는 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 ↩︎

저희들의 저서 「줄리아 프로그래밍」이 2024 세종도서 학술부문에 선정되었습니다!

