1
$\begingroup$

I am looking for an algorithm that can assert something similar to the following:

Let all clusters in the data (for some definition of cluster) that contain more than $\theta$ fraction of the datapoints be high-frequency clusters. If we allow the algorithm to return $O(\theta^{-1})$ centers it will return a point in each of those high-frequency clusters with high probability.

For example, a cluster could be a group of points s.t. all points are within some distance $d$. If I had a few highly concentrated regions but also tons of outliers, an algorithm like k-means would have to put centers relatively close to those outliers so as to minimize the total cost, and would not be able to guarantee what I want. In contrast, an algorithm like the one I'm looking for would forget about the outliers because they don't belong to any high-frequency cluster.

A couple illustrations to make my point: None of the high-frequency (>33% of points) clusters has a center close enough

1 cluster devoted to one outlier instead of a high-frequency cluster

Improve this question
$\endgroup$
1
  • $\begingroup$ What do you think about self-organizing maps (SOM)? They try to cover all the input space according to the density of data samples, i.e., there would be several SOM nodes spread over the upper left corner of the figures in your question. Thus it would be much more likely to sample a node that belongs to that dense region. $\endgroup$
    – felipeduque
    Commented Feb 19, 2017 at 20:03

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.