# How to find a line which has the minimum total distance to separate two cluster points

Suppose I have two cluster points

SeedRandom[2]
pts = RandomReal[1, {50, 2}];
cluster = FindClusters[pts, 2, RandomSeeding -> 1];
ListPlot[cluster]


I want to find a line to separate this two cluster point sets,and this line has the minimum total distance with all points. I think Mathematica maybe have some in-built methods can implement it.This is my current try

trainning = Flatten[MapIndexed[Thread[#1 -> First[#2]] &, cluster]];
c = Classify[trainning, Method -> "SupportVectorMachine"];
ClassifierInformation[c, "Function"]


Missing[PropertyNotAvailable,Function]

But I cannot get an available result.So I have to implement it manually.

sol = ArgMin[{Total[Abs[a # - #2 + b]/Sqrt[a^2 + 1] & @@@ pts],
a # + b < #2 & @@@ Last[cluster],
a # + b > #2 & @@@ First[cluster]}, {a, b}];
Show[ContourPlot[
Evaluate[# x + #2 == y & @@ sol], {x, 0, 1}, {y, 0, 1}],
ListPlot[cluster]]


I will get the result and some error information simultaneously.I cannot sure the result is what I want exactly.I mean I don't know the total distance is smallest or not.Is there better solution can do this?

• Not exactly what you asked, but a SVM does something similar in that it tries to find a line that seperates both point clouds by some margin. I expect the result to be very similar in your case. – Sascha May 24 '17 at 6:07
• @Sascha Yes,I try to implement SVM,and I hope to get that equation of the line. Dose any vague expression in my post? – yode May 24 '17 at 6:31
• Maybe you can use the SVM implementation from Classify – Sascha May 24 '17 at 6:44
• @Sascha But I don't know how to.. – yode May 24 '17 at 6:51
• Do you assume that a line that separates the clusters always exists? – Anton Antonov May 24 '17 at 10:02

As indicated by your comment you are not strictly looking for the line that has the minimum total distance with all points. If you just like to find a line that separates your data well you could use a SVM. Since I haven't played to much with Classify to be able and tell how easy it is to get the parameters out, I though of another similar approach. I will show how to solve this with the simplest neural net possible: a single perceptron.

The perceptron is simply:

p = NetChain[{1, LogisticSigmoid}, "Input" -> 2, "Output" -> NetDecoder["Scalar"]]


To generate the training data we assign the the label 0 to the first and the label 1 to the second cluster.

trainingData = cluster // MapIndexed[Thread[Rule[#1, First@#2 - 1]] &] // Flatten


Now we can train our perceptron with

trained = NetTrain[perceptron, trainingData ]


and extract the weights and bias term with

{{{w1, w2}}, {bias}} = NetExtract[trained, {{ 1, "Weights"}, {1, "Biases"}}]


The line defined by $w_1 \cdot x + w_2 \cdot y + bias$ can be plotted together with the original points via

Show[ListPlot[cluster], Plot[y /. Solve[w1 x + w2 y + bias == 0, y], {x, 0, 1}]]


• The SVM will find a line which has the minimum total distance with all points before this.. – yode May 24 '17 at 8:37
• @yode I know that a SVM is closer to what you were looking for, I posted this answer just because there isn't a "Hello World" - single perceptron answer on mathematica.stackexchange yet (as far as I know). – Sascha May 24 '17 at 8:47
• @sascha can you show the equation of the line and minimum distance value? – george2079 Jun 16 '17 at 17:30
• it's worth noting that as long as the two clusters really are linearly separable, the perceptron is guaranteed to converge on a separating line even though it's fit using iterative optimization. – Michael Curry Jun 16 '17 at 18:37

here is an implementation as a standard constrained optimization

d[a_?NumericQ, b_?NumericQ] :=
Total[RegionDistance[Line[{{0, a}, {1, b}}]] /@ pts]
result = FindMinimum[{d[a, b],
And @@ (Interpolation[{{ 0, a}, {1, b}},
InterpolationOrder -> 1][#[[1]]] >= #[[2]] & /@
cluster[[1]]) &&
And @@ (Interpolation[{{ 0, a}, {1, b}},
InterpolationOrder -> 1][#[[1]]] <= #[[2]] & /@
cluster[[2]]) && 0 < a < 1 && 0 < b < 1}, {{a, .5}, {b, .5}},
MaxIterations -> 2000]


{11.6243, {a -> 0.509647, b -> 0.390072}}

 Show[{ListPlot[cluster],
Graphics[Line[{{ 0, a}, {1, b}} /. result[[2]]]]}]


this does throw convergence warnings, so i guess we are left wondering if it is actually a global minimum.

• I'm sure it is not a globel minimum.Because as I know the expected line will not very close with any point,but there are three points in the line almostly.. – yode Jun 16 '17 at 15:54
• I don't see how you conclude the minimum must not be close to any points? As I understand the question, the clustering is given and we need to find the line (I notice @sascha 's answer has a different clustering ) – george2079 Jun 16 '17 at 17:36
• Oh,I see that conclusion in my textbook..it not my summary. :)If the Minimize work here,it will give the anser we want to get. – yode Jun 16 '17 at 17:38
• actually it can be proved that the solution is guaranteed to hit at least one point (unless the clusters contain exactly the same number of points). If you think that's not the case there must be some misunderstanding in the problem formulation. – george2079 Jun 16 '17 at 20:43