Is there a clustering algorithm that can make n clusters and the n+1 “others” cluster?

As far as I know all clustering algorithms assume that all delivered data points have to find its cluster.

My question is, is there an algorithm that could focus only on n clusters (number stated by user) and try to dismiss the rest of the points that (according to algorithm) do not belong to n clusters, like in the picture shown below? Where we know that there are for example 2 classes that we need to cluster (red and green) and the rest (blue) we do not need in any cluster and therefore algorithm does not try to assign them to any cluster?

For example if we would have 1 000 pictures of animals, of which 200 are dogs, 200 are cats and the rest are all other animals known to men and we want to make 1 cluster for cats, 1 for dogs and maybe another for collectively all others that do not match dogs or cats.

So, I've prepared some data that resembles your sketch:

n , u = np.random.normal , np.random.uniform
x = np.concatenate([ n(1.0,0.2,100), n(3.0,0.3,100), u(0,10.0,100)])
y = np.concatenate([ n(7.0,0.4,100), n(5.0,0.3,100), u(0,10.0,100)])
# lets shuffle it a bit
idx = np.arange(x.shape[0])
np.random.shuffle(idx)
data = np.array([x,y])[:,idx]


And then I just tried using sklearn.mixture.GaussianMixture with n+1 = 3 components and default parameters:

gmm = GaussianMixture(n_components=3).fit(data.T)
cls = gmm.predict_proba(data.T).argmax(axis=1)

# Plotting
color = [['r','k','g'][i] for i in cls]
scatter(data[0],data[1],c=color, marker='.')
scatter(gmm.means_[:,0],gmm.means_[:,1],c='b',marker='o')


That seems awfully lot like the thing you've sketched.

• Nice demonstration of what Gaussian mixture models can be used for! – Mike NZ May 9 at 4:04