1
$\begingroup$

Suppose I have two cluster points

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

Mathematica graphics

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]]

Mathematica graphics

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?

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – Sascha
    May 24, 2017 at 6:07
  • $\begingroup$ @Sascha Yes,I try to implement SVM,and I hope to get that equation of the line. Dose any vague expression in my post? $\endgroup$
    – yode
    May 24, 2017 at 6:31
  • $\begingroup$ Maybe you can use the SVM implementation from Classify $\endgroup$
    – Sascha
    May 24, 2017 at 6:44
  • $\begingroup$ @Sascha But I don't know how to.. $\endgroup$
    – yode
    May 24, 2017 at 6:51
  • 1
    $\begingroup$ Do you assume that a line that separates the clusters always exists? $\endgroup$ May 24, 2017 at 10:02

2 Answers 2

5
$\begingroup$

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}]]

image

$\endgroup$
4
  • $\begingroup$ The SVM will find a line which has the minimum total distance with all points before this.. $\endgroup$
    – yode
    May 24, 2017 at 8:37
  • $\begingroup$ @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). $\endgroup$
    – Sascha
    May 24, 2017 at 8:47
  • $\begingroup$ @sascha can you show the equation of the line and minimum distance value? $\endgroup$
    – george2079
    Jun 16, 2017 at 17:30
  • 1
    $\begingroup$ 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. $\endgroup$ Jun 16, 2017 at 18:37
0
$\begingroup$

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]]]]}]

enter image description here

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

$\endgroup$
4
  • $\begingroup$ 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.. $\endgroup$
    – yode
    Jun 16, 2017 at 15:54
  • $\begingroup$ 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 ) $\endgroup$
    – george2079
    Jun 16, 2017 at 17:36
  • $\begingroup$ 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. $\endgroup$
    – yode
    Jun 16, 2017 at 17:38
  • $\begingroup$ 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. $\endgroup$
    – george2079
    Jun 16, 2017 at 20:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.