Given n data points in R^d, an appropriate edge-weighted graph connecting the data points finds application in solving clustering, classification, and regresssion problems. The graph proposed by Daitch, Kelner and Spielman (ICML 2009) can be computed by quadratic programming and hence in polynomial time. While in practice a more efficient algorithm would be preferable, replacing quadratic programming is challenging even for the special case of points in one dimension. We develop a dynamic programming algorithm for this case that runs in O($n^2$) time. Its practical efficiency is also confirmed in our experimental results.
d차의 n개의 데이터가 주어졌을 때, 데이터를 연결하는 적절한 가중 그래프를 이용해서, 분류문제, 군집화 문제 그리고 회귀문제를 풀 수 있다. Daitch, Kelner, Spielman(ICML-2009)이 제안한 그래프를 이용하면 쿼드라틱 프로그래밍으로 다항식 시간안에 계산할 수 있다. 실제 데이터에 대해서 계산을 수행하기 위해 더욱 효율적인 알고리즘이 필요하지만, 특수한 1차원 데이터에서조차 쿼드라틱 프로그래밍을 대신하는 알 고리즘을 찾는 것은 어렵다. 하지만 본 논문에서 1차원 데이터에 대해서 O($n^2$)의 시간복잡도를 가지는 동적 프로그래밍 알고리즘을 제안한다. 또한, 실험을 통해서 제안한 알고리즘이 성능을 크게 향상시킴을 보인다.