5
$\begingroup$

I need to choose a model for unsupervised machine learning problem. There are 4 clusters in 3D space. These are my requirements:

  • I will run the same model multiple times with different training data (it is for real-time application).
  • Size of training data is expected to be around 400 points.
  • I can assume that points for each of the clusters are drawn from a Gaussian distribution. This is not necessary requirement to be present in the model.
  • I need to get 4 points that represent "centers" of clusters.
  • In prediction time, for each new point I need some kind of number for each cluster that will represent probablity of belonging to the cluster.
  • I will have a lot of outliers, assume around 30%.

I have tried Gaussian mixture model, and it works very good when I don't have outliers. Unfortunately, this model is very sensitive to outliers.

Any suggestions how to handle the outliers with Gaussian mixture model? Or should I go with completely different model?

$\endgroup$
  • $\begingroup$ I might be misunderstanding something but what stops you from using a (potentially regularised) multinomial (ie. softmax) regression model and just get at running time a vector of number representing the probability of an incoming point to belong to one of the four clusters considered? (I would start with a standard multinomial and then get try ridge, etc.) Additionally, if ~30% of the data are outliers you are probably defining "non-outlier" data in an overly restrictive manner. 5? 10% outliers? Maybe... More than that suggests that probably the modelling assumptions sued are a bit off. $\endgroup$ – usεr11852 Jul 3 '17 at 22:17
  • $\begingroup$ How can I use multinomial regression for unsupervised learning? $\endgroup$ – Luka Jul 4 '17 at 18:08
  • $\begingroup$ You mentioned that you expect four clusters so I assume you know beforehand that there are four categories. No need to hope that these four cluster arise "naturally". Just define the four categories you know you have at training time and during prediction time just use supervised learning. Online-clustering is expensive and hard to ensure the performance off. $\endgroup$ – usεr11852 Jul 4 '17 at 20:05
  • $\begingroup$ I know there are 4 clusters, but I don't know where are their positions. And the whole point is to find where those clusters are $\endgroup$ – Luka Jul 4 '17 at 21:24
  • $\begingroup$ Ah OK! I focused on what will happen "after" you get the clusters at prediction time (your last two steps). Getting "a clustering" is a one-off exercise. Using the clustering afterwards is the issue. $\endgroup$ – usεr11852 Jul 4 '17 at 22:37
2
$\begingroup$

Here are a couple suggestions, given that Gaussian mixture models work well for you in the absence of outliers.

To increase robustness to outliers, you could use a trimmed estimator for Gaussian mixture models instead of fitting with the standard EM algorithm. Some relevant papers:

Instead of Gaussian mixture models, you could also consider student T mixture models. This will give the same properties you want (e.g. ability to compute cluster centroids and membership probabilities). Student T distributions have heavier tails than Gaussians, which increases robustness to outliers. Some relevant papers:

$\endgroup$
1
+50
$\begingroup$

I am assuming that the required four clusters will be of somewhat similar density. If that is the case then you can use a density based clustering approach, DBSCAN has worked well for me. You can find all the clusters that you can during training time and have a threshold on the cluster size to preclude the outliers from being part of your desired clusters.

Using this, and some knowledge about what constitutes as an outlier, you can look into the clusters and see if the outliers (as ~30% seems a bit on the higher end) themselves form a cluster.

Scikit-learn in python has an in-built function for this. sklearn.cluster.DBSCAN

$\endgroup$
1
$\begingroup$

Red flags go off in my head when someone says (paraphrasing heavily)

I can assume property X for my algorithm, but this peroperty X need not be present in the data.

That immediately points to possible performance issues and/ or grounds to revaluate model selection step.

Having said that, I haven't worked with GMM for clustering beyond the base EM algorithm to find density parameters of points. But to my best understanding, clustering using GMM is fuzzy, i.e. depending on implementation methods you can vary cluster assignment based on some criteria of interest.

Working off the above approach I recommend self-organizing maps that semantically group together similar items. As a second step, clustering can be applied on top of it. (Reference)

Also, when working with mixed models, exploring kernel methods can be quite fruitful as now, your decision boundaries can be more expressive in higher dimensional space. Here's a paper that talks theoretically about how to make common clustering methods more robust using kernel, it covers data with mixture of Gaussian densities as well.

$\endgroup$
1
$\begingroup$

Look, this might not be the best idea, but I'll suggest it anyway.

You say that you are dealing with an unsupervised ML problem, but said that:

  • you can assume that in this 4 dimensional space, your data is a multivariate Gaussian;

  • your model works nicely when there aren't many outliers

If you can afford not assigning a class to an outlier observation, go with DBSCAN as mentioned, or HDBSCAN, where you can even work without the Gaussian assumption.

Now, my idea is: based on the fact that your problem works well when there aren't outliers I suggest you turn this problem into a supervised one provided that:

  • you have a consistent number clusters every time you run the clustering algorithm

  • the points are consistently assigned to the same clusters

When you have a labeled data set (after clustering), you can use the most appropriate classification algorithm to assign new points to those clusters, or work based on the predicted probabilities (hint, KNN works wonders in low dimensional spaces, such as yours).

If everything is working, outliers should be classified with a low probability of belonging to any clusters, and you can program your online application to handle these cases.

$\endgroup$
  • $\begingroup$ This intuitively sounds like the k-mediods algorithm. I'd be interested in seeing if all these steps perform better than vanilla k-mediods. $\endgroup$ – DivyaJyoti Rajdev Jul 7 '17 at 20:02
  • $\begingroup$ I don't see how this is similar to k-mediods. (perhaps since I have never studied it thoroughly. Would you mind elaborating a bit more? $\endgroup$ – Guilherme Marthe Jul 7 '17 at 21:15
  • $\begingroup$ Not algorithmic similarity, but kmeans takes random centers and iterates to find a good cluster partition based on square error. kmediods takes points from the data itself and partitions around those using manhattan distance as measure. So when you apply knn on kmeans, you're in essence expanding the cluster boundaries to points that would have possibly been included using kmediods (assumption that knearest neighbors would have smaller manhattan distance to the cluster). It's not 100% sound logic and hence the comment that I'd be curious to see the performance. $\endgroup$ – DivyaJyoti Rajdev Jul 7 '17 at 21:28
  • $\begingroup$ I don't understand this part, how to "turn this problem into a supervised one"? $\endgroup$ – Luka Jul 8 '17 at 5:05
  • $\begingroup$ @Luka, what I mean by that is, but working using the labels of your clustering technique as labels for a classifier, you end up treating your problem as a supervised one, instead of only working in the unlabeled version before clustering. $\endgroup$ – Guilherme Marthe Jul 10 '17 at 16:18
0
$\begingroup$

Only 3 dimensions and 30% of your data are outliers? That does not seem to fit with what I normally think of as an outlier. Perhaps you can simply transform your variables to log scale or "cap" the outliers so that they are no more than 3 or 4 standard deviations from the mean. This may create clusters of points with no variance, though.

$\endgroup$
  • $\begingroup$ What do I with transforming to log scale? $\endgroup$ – Luka Jul 5 '17 at 19:35
  • $\begingroup$ How can I "cap" the outliers if I don't know variance? Actually, my goal is to find means and variances $\endgroup$ – Luka Jul 5 '17 at 19:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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