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][2]][2]

[![1 cluster devoted to one outlier instead of a high-frequency cluster][3]][3]


  [2]: https://i.sstatic.net/UNSzf.png
  [3]: https://i.sstatic.net/WfGFO.png