I am faced with a challenging problem and I was wondering whether someone could point me in the right direction of existing research literature.

The problem is the following: Given a stream of data points, cluster them into equivalent clusters with no knowledge of what the clusters are.

This resembles the online clustering problem, where data points need to be clustered together. However, clustering is an unsupervised algorithm and the data points are usually clustered based on a distance measure between pairs of them.

In my case, the data points are not simple text documents, although a part of their features is sparse. Instead they contain very important individual features and more feature engineering could be done to improve the representation. As I believe that the problem of assigning these data points to clusters is rather challenging I have doubts that an unsupervised distance metric would be able to do well enough, especially since good performance is vital.

The idea I have is to replace the distance metric in an online clustering algorithm with a classification or a regression model. The model would predict whether the two data points belong to the same cluster. A clustering algorithm might perform better if a continuous number was output which can be interpreted as a distance.

My question are:

  1. Is this an established approach and if so could you point me to research literature? I do not know where to start looking.
  2. If not, does the approach sound reasonable or am I overlooking something?
  3. If yes, do you have any suggestions on how to formulate the model?

Thanks a lot for your help.

Updated description: To describe the problem differently, you can think of the underlying problem as a process that creates a stream of distinct hidden states. Each data point that we observe is a noisy description of one such hidden state. A data point can be thought of as a report of a hidden state occurring, which means that it will happen at some point after the hidden state occurs with decreasing probability over time (and never before the hidden state happens). Each hidden state may have many descriptions in the form of data points associated with it or just one (potentially zero as well, but not much we can do about those). The goal is to identify the true hidden states by associating data points to them, with as high reliability as possible. The data points are described with a number of features, and importantly, they have a time associated with them (as do the hidden states).

Two further complexities can arise: (1) although difficult to formalize, there is a notion of similarity between hidden states and some will be more difficult to distinguish from one another than others, and (2) a further goal is to infer true properties of the hidden state from the noisy descriptions of the data points (instead of just relying on a group of data points to provide a sufficient description).

Update 2: The hidden states may or may not be dependent on each other. In a simplified view, we can assume that the states are generated independently of each other and there are no transitions between states. A system can be in a number of them at any point. Thinking about it, states is probably not the right terminology, but I do not know what is.

  • $\begingroup$ All you want, and more: A tutorial on Bayesian nonparametric models $\endgroup$ – Emre Jun 17 '15 at 17:29
  • $\begingroup$ What do you mean by "equivalent clusters"? Is this referring to the size of the clusters, the stability of established clusters (decision boundaries), or something else? $\endgroup$ – Jason Sanchez Jun 17 '15 at 19:22
  • $\begingroup$ @JasonSanchez By equivalent clusters I mean that the data points in a single cluster are all descriptions of the same true state. $\endgroup$ – Matic Jun 18 '15 at 9:39
  • $\begingroup$ @Emre I edited the above post to offer a more generative story of the problem. $\endgroup$ – Matic Jun 18 '15 at 10:01
  • 1
    $\begingroup$ @Matt could you give more of a flavour about what the data look like, and what types of decisions you hope to make off the back of them? $\endgroup$ – conjectures Jun 18 '15 at 10:24

Your Answer

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

Browse other questions tagged or ask your own question.