====== 6.3. Segmented Least Squares: Multi-way Choices ====== With this problem, at each step we have a polynomial number of possibilities to consider the structure of the optimal solution.\\ \\ ===== The Problem ===== >>>>>>>>>>>>>>>>>> Suppose our data consists of a set P of n points in the plane,:\\ >>>>>>>>>>>>>>>>>> (x₁y₁),(x₂y₂),...,(x_ny_n), where x₁ < x₂,...,< x_n\\ >>>>>>>>>>>>>>>>>> Given a line L with equation y = ax + b, we say that an "error" of L with respect to P is the sum of all of its squared distances to the points in P:\\ >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Error(L,P) = ∑_{from i =1 to n} (y_i - ax_i- b) ²\\ >>>>>>>>>>>>>>>>>> Thus naturally, we are bound to finding the line with minimum error.\\ >>>>>>>>>>>>>>>>>> The solution turns out to be a line y = ax + b, where:\\ >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> a = [(n∑_i x_iy_i) - (∑_ix_i)(∑_i y_i)]/[(n∑_i x_i²) - (∑_i x_i)²]\\ >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> And b = (∑_i y_i- a∑_i x_i)/n\\ \\ >>>>>>>>>>>>>>>>>> However, our problem is different from the above mentioned which these (above) formulas solve.\\ ** Formulating our problem** \\ >>>>>>>>>>>>>>>>>> Given a sequence of data points, we need to identify a few points in the sequence at which a discrete change occurs.--> In our specific case, a change from one linear approximation to another.\\ >>>>>>>>>>>>>>>>>> So, we have a set of points P = {(x₁,y₁),(x₂,y₂),...,(x_n,y_n)} with x₁ < x₂,..., x_n.\\ >>>>>>>>>>>>>>>>>> p_i denotes the point (x_i,y_i)\\ >>>>>>>>>>>>>>>>>> We must first partition P into some number of segments.\\ >>>>>>>>>>>>>>>>>> Each segment is a subset of P that represents a contiguous set of x-coordinates of the form {p_i,p_i+1,...,p_j-1,p_j} for some indices i≤j.\\ >>>>>>>>>>>>>>>>>> For each segment S in our partition P, we compute the line minimizing the error with respect to the points in S using the formula we found above(where we wrote the value of a and b in the line y = ax + b).\\ >>>>>>>>>>>>>>>>>> The penalty of a partition is defined to be the sum of:\\ >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> The number of segments into which we partition P, times a fixed, given multiplier C>0.\\ >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> For each segment, the error value of the optimal line through that segment.\\ >>>>>>>>>>>>>>>>>> Our goal is to find the a partition of minimum penalty.\\ ===== Designing the Algorithm ===== >>>>>>>>>>>>>>>>>> INPUT: n, p₁,...,p_N, C\\ >>>>>>>>>>>>>>>>>> Segmented-Least-Squares()\\ >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> M[0] = 0\\ >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> e[0][0] = 0\\ >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> for j = 1 to n\\ >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> for i = 1 to j\\ >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> e[i][j] = least square error for the segment p_i,...,p_j\\ >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> for j = 1 to n\\ >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> M[j] = min _{1 ≤ i ≤ j} (e[i][j] + c + M[i-1])\\ >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> return M[n]\\ \\ Just like the Weighted Interval Scheduling Problem, we need to find an algorithm that gives us the solution itself.\\ ** Algorithm to give for the solution itself** \\ >>>>>>>>>>>>>>>>>> FindSegments(j):\\ >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> if j = 0:\\ >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> output nothing\\ >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> else:\\ >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Find an i that minimizes e_i,j + C + M[i-1]\\ >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Output the segment {p_i, …, p_j} and the result of \\ >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> FindSegments(i-1) >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> End if ===== Algorithm Analysis ===== \\ The running time of the algorithm is O(n²) since filling in the array M[j] takes us O(n) time for each j.\\ I give this section 7/10.