I came across the below interview question on Glassdoor:
A scatter graph of points on a page, draw a horizontal line across the page such the the perpendicular y distance to the line from all points in aggregate is minimized. Describe an algorithm for placing this line optimally
My approach:
I think we can compute the mean of y-distances and place the line there.
However, I am not sure if this is correct or if there is a better approach to solving this problem.
First, since we only care about the y-distance and will be drawing a horizontal line, we only need to think about the y-coordinates of the points and the y-coordinate that defines the line. The distance between a point and our line will be the absolute difference between the y-coordinate of the point and the y-coordinate that defines the line.
So, rephrasing the problem, we have a set of numbers, y_1 to y_n, and need a number, z, that minimizes the aggregate of the absolute differences between z and the points y_1 to y_n. Instead of minimizing the aggregate, we can just minimize the sum and get the correct result (aggregate = sum / number_of_points).
It turns out that it is the median that does this, not the mean.
https://math.stackexchange.com/questions/113270/the-median-minimizes-the-sum-of-absolute-deviations
For intuition, have points at y-coordinates 10, 10, 10 and 110. The median is 10, aggregate distance is (0+0+0+100)/4=25. The mean is 140/4=35, aggregate distance is (25+25+25+75)/4=37,5. In fact moving the line any distance, d, away from y-coordinate 10 towards 100 increased the distance to 3 points (with d) while only decreasing the distance to 1 point (with d) and hence increasing the aggregate.
(If we would take squares of distances then the mean would be the correct answer)
The method you use to calculate the line depends on the cost function you minimize. You can use the mean y-value which sets the sum of the distances (measured as positive when a point is above the line and negative when the point is below the line) to zero.
You could use a 'minimum sum of the squares of the distances' cost function, which would provide a different answer.
Both those are straight-forward to calculate. You could use a 'minimum sum of the absolute distances'; that is trickier to compute, and in general yields a different answer from the other two methods.
You can also devise your own cost function to minimize. Have fun!
For your purposes, I think the mean is a sensible choice.
As Jonathan points out there are are a number of different cost functions you can minimize but from the perpendicular y distance to the line from all points in aggregate is minimized i'd assume we were looking for the 'minimum sum of the absolute distance'.
This isn't too bad to calculate if you happen to know that this is the same as the median, proof (I suspect this makes it a poor question for a general development position, and one more suited for data science)
to find the median one could sort the points by co-ord then take either the middle point from the list or average the two middle points.
