# 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. May 24, 2017 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, 2017 at 6:31
• Maybe you can use the SVM implementation from Classify May 24, 2017 at 6:44
• @Sascha But I don't know how to..
– yode
May 24, 2017 at 6:51
• Do you assume that a line that separates the clusters always exists? May 24, 2017 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, 2017 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). May 24, 2017 at 8:47
• @sascha can you show the equation of the line and minimum distance value? Jun 16, 2017 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. Jun 16, 2017 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, 2017 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 ) Jun 16, 2017 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, 2017 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. Jun 16, 2017 at 20:43