title: Efficient clustering algorithm for nearly uniformly distributed data
body: <p>I'm playing around with natural language processing and I'm trying to cluster news article titles. I turned the titles into vectors, but they are nearly uniformly distributed. There are small clusters of 2-3 news articles, but most news articles should be in their own clusters.</p>
  
  <p>I tried using k-means, but articles rarely change clusters because the data is fairly uniform. The initial random clusters end up being the final clusters.</p>
  
  <p>I tried agglomerative clustering and it works great for a small data set (a few hundred articles). However, it takes a long time because it's at least O(n^2).</p>
  
  <p>Is there any efficient algorithm to cluster nearly uniformly distributed data?</p>
  
  <p>For example, if my data is a set of real numbers, it could look like this:</p>
  
  <p>1 2 3 4 4.1 5 6</p>
  
  <p>In this case, the clusters should be: (1), (2), (3), (4, 4.1), (5), (6).
  Is there a better way to do this than agglomerative clustering?</p>