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: