Implement ‘Segmented Least Squares’ Dynamic Programming algorithm below in Java.
ID: 3789331 • Letter: I
Question
Implement ‘Segmented Least Squares’ Dynamic Programming algorithm below in Java.
Segmented-Least-squares (n) Array M10 n] Set M[0] 0 For all pairs is j Compute the least squares error ei,j for the segment pi ,pi End for For j 1, 2, n Use the recurrence (6.7) to compute MU] End for Return MInl If j 0 then Output nothing Else Find an i that minimizes ei, C+ Mli-1] output the segment (pi, pil and the result of Find-Segments Ci -1) Endif (6.7) Space-Efficient-Alignment (X,Y) Array B[0 m, 0...11 Initialize Bli, 0] i5 for each i (just as in column 0 of A) For j 1, n. BIO, ij j5 (since this corresponds to entry Alo, jl) For i 1, m Bli, 11 min Bli -1, 01, xiyi End for Move column 1 of B to column 0 to make room for next iteration Update B i, 0] B i, 11 for each i End forExplanation / Answer
import java.awt.geom.Point2D;
import java.util.ArrayList;
public class SegmentedLeastSquares {
ArrayList <LineSegment> lineSegments = new ArrayList<LineSegment>();
Point2D[] points;
int lengthPlusOne=0;
double costSegment; // this is the constant C in the lecture, the cost of each segment
double a[][]; // a[i][j] and b[i][j] will be the coefficients of line y = ax + b + e
double b[][]; // for the segment (xi,..., xj)
double e_ij[][]; // error for the segment (xi, ..., xj)
double opt[]; // java initializes this to 0.
// constructor
// The list of points and the cost of each segment are given by the caller.
public SegmentedLeastSquares(Point2D[] points, double costOfSegment){
this.points = points;
this.costSegment = costOfSegment;
e_ij = new double[points.length][points.length];
a = new double[points.length][points.length];
b = new double[points.length][points.length];
lengthPlusOne = 1 + points.length;
opt = new double[ points.length ];
computeEijAB();
}
public void computeEijAB(){
double denominator;
double[] sumX = new double[ lengthPlusOne ];
double[] sumY = new double[ lengthPlusOne ];
double[] sumX2 = new double[ lengthPlusOne ];
double[] sumY2 = new double[ lengthPlusOne ];
double[] sumXY = new double[ lengthPlusOne ];
for (int i=0; i< points.length; i++){ // Watch out for the 'off by 1' errors
// The sum_ variables index from 1 to N, not 0 to N-1,
// and sum_[0] == 0.
sumX[i+1] = sumX[i] + points[i].getX();
sumY[i+1] = sumY[i] + points[i].getY();
sumX2[i+1] = sumX2[i] + points[i].getX() * points[i].getX();
sumY2[i+1] = sumY2[i] + points[i].getY() * points[i].getY();
sumXY[i+1] = sumXY[i] + points[i].getX() * points[i].getY();
}
for (int i=0; i< points.length; i++){
for (int j = i+1; j < points.length; j++){ // i < j
denominator = (Math.pow(sumX[j+1]-sumX[i],2.0) - (j + 1 - i) * (sumX2[j+1] - sumX2[i]));
if (denominator == 0){
System.out.println("No single minimum exists e.g. the minimum is a line running along an infinitely long valley. ");
a[i][j] = 0.0;
b[i][j] = 0.0;
// In this case, we don't fit a line segment. We take y == 0.
}
else{
a[i][j] = ((sumY[j+1] - sumY[i])*(sumX[j+1] - sumX[i])
- (j + 1 - i) * (sumXY[j+1] - sumXY[i]))/ denominator;
b[i][j] = ((sumX[j+1] - sumX[i])*(sumXY[j+1]- sumXY[i])
- (sumX2[j+1] - sumX2[i])*(sumY[j+1] - sumY[i]) )/ denominator;
e_ij[i][j] = (sumY2[j+1]-sumY2[i])
- 2*a[i][j]* (sumXY[j+1]-sumXY[i])
- 2*b[i][j]* (sumY[j+1] -sumY[i])
+ a[i][j]*a[i][j] * (sumX2[j+1]-sumX2[i])
+ 2*a[i][j]*b[i][j] * (sumX[j+1]-sumX[i])
+ b[i][j]*b[i][j] * (j+1 - i);
}
}
}
}
/******************************************
* Saige McVea's contribution begins here: *
******************************************/
// computes the minimal cost of a least squares fit for the first j samples
public void computeOptIterative( ){
// initialize the first segment to assure that it is included
opt[0] = costSegment;
// begin two for-loops to compute optimal solution
for (int j=1; j<points.length; j++) {
// set initial value to cost of edge (0, j)
opt[j] = e_ij[0][j] + costSegment;
for (int i=1; i<j; i++) {
// dynamic programming aspect relies on previous solutions
if (opt[j] > (opt[i-1] + e_ij[i][j] + costSegment)) {
opt[j] = (opt[i-1] + e_ij[i][j] + costSegment);
}
}
}
}
public double computeOptRecursive(int j){
// same as before, assures that the first line segment (0,0) has a value
if(opt[0] == 0) opt[0]=costSegment;
// memoization aspect avoids recusive calls if a value has already been computed
if (opt[j]>0) return opt[j];
else {
// recursive call
opt[j] = computeOptRecursive(j-1) + e_ij[j-1][j] + costSegment;
// avoids error in calculation with j=1 where costSegment is added twice
if (opt[j] > e_ij[0][j] + costSegment) opt[j] = e_ij[0][j] + costSegment;
// finds minimum exactly as before in the iterative solution
for (int i=0; i<j; i++) {
if (opt[j] > (opt[i] + e_ij[i+1][j] + costSegment)) {
opt[j] = (opt[i] + e_ij[i+1][j] + costSegment);
}
}
return opt[j];
}
}
// computes lineSegments, which is an ArrayList<LineSegment>.
public void computeSegmentation(int j){
// code will not allow for negative number of points
if (j>=0) {
if (opt[j] == e_ij[0][j] + costSegment) lineSegments.add(new LineSegment(0, j, a[0][j], b[0][j], e_ij[0][j]));
// for loop checks if e_ij is part of the optimal segmentation
for (int i = 1; i<=j; i++) {
if (opt[j] == (opt[i-1] + e_ij[i][j]) + costSegment) {
lineSegments.add(new LineSegment(i, j, a[i][j], b[i][j], e_ij[i][j]));
// if-statement checks if the sub-solution is an edge to assure that the first line is drawn
if (opt[i-1] == (e_ij[0][i-1] + costSegment)) {
lineSegments.add(new LineSegment(0, i-1, a[0][i-1], b[0][i-1], e_ij[0][i-1]));
}
// recursive call if the sub-solution has more than one segment
else computeSegmentation(i-1);
}
}
}
}
public ArrayList<LineSegment> solveIterative(){
System.out.println("Solving iteratively...");
computeOptIterative();
computeSegmentation( points.length - 1); // indices of points is 0, ..., N-1
return(lineSegments);
}
public ArrayList<LineSegment> solveRecursive(){
System.out.println(" Solving recursively...");
computeOptRecursive( points.length - 1);
computeSegmentation( points.length - 1); // indices of points is 0, ..., N-1
return(lineSegments);
}
}
class LineSegment{
int i,j;
double a,b,error;
public String toString(){
return " (" + new Integer(i) + "," + new Integer(j) + ") "
+ " line is y = " + String.format("%.2f",a) + " x + "
+ String.format("%.2f ", b) + ", error is " + String.format("%.2f", error);
}
// added this constructor easily add elements to lineSegments
public LineSegment(int i, int j, double a, double b, double error){
this.i = i;
this.j = j;
this.a = a;
this.b = b;
this.error = error;
}
}