In all fairness I discovered that many people confuse very often clustering with classification, but this is another story, and I promise to treat that in other post :).
What is the core concept to understand deeply the classification problem? ...the complexity of the problem itself!
Let me be more clear, and observe the following scenario:
Imagine that you are interested to divide the blue points from the red points, and more specifically you are interested to a black box taking in input a point, it is able to assign automatically the class (red or blue) to the point.
Well, Imagine that the only tool admitted to divide the plane to separate the points is the linear function.
Mhmm.... as you can see whatever line you try to draw is not able to split the points red from the blue points.
-> A linear function able to divide the plane splitting correctly the blue points from the red points is called linear classifier.
-> A non linear function able to that is called non linear classifier. (in this case the circle equation solve the problem.... but the real world is often more complex...)
Question: is it possible map the points of the original problem in another space more complex (that is having higher dimension) where is possible to divide the points using only a linear classifier?
The answer is YES. The trick is honor of famous mathematicians, but it is very very useful to make up a linear classifier (read easy to develop and easy to reuse in other context!!) and you can find the theory everywhere in internet.
Let me show the effect with the above problem:
I took every points in 2D and i mapped in 3D space using the function (called Kernel function):
[x,y]->[x^2, Sqrt*x*y, y^2]
And I obtained the following:
The red points now are grouped together and with a linear plane (that is a linear function in three dimensional space) we are able to divide again our points!
Here you are the overall problem:
If you are interested to further details I can share the Mathematica notebook I coded to generate the above images.
You don't need the License, you can play also with the player available here:http://www.wolfram.com/products/player/.
Let me cleanup the 10 rows of code and I'll publish the source file.
See you soon!