This might do the trick: apply Lloyd’s algorithm to get k centroids. Sort the centroids by descending size of their associated clusters in an array. For i = 1 through k-1, push the data points in cluster i with minimal distance to any other centroid j (i < j ≤ k) off to j and recompute the centroid i (but don’t recompute the cluster) until the cluster size is n / k.
The complexity of this postprocessing step is O(k² n lg n).
Related Contents:
- Unsupervised clustering with unknown number of clusters
- Python k-means algorithm
- Extremely small or NaN values appear in training neural network
- Write a program to find 100 largest numbers out of an array of 1 billion numbers
- What algorithm can be used for packing rectangles of different sizes into the smallest rectangle possible in a fairly optimal way?
- Given a number, find the next higher number which has the exact same set of digits as the original number
- What are the differences between segment trees, interval trees, binary indexed trees and range trees?
- An algorithm for inflating/deflating (offsetting, buffering) polygons
- Is it possible to specify your own distance function using scikit-learn K-Means Clustering?
- Breadth First Vs Depth First
- What is a good Hash Function?
- What is the advantage to using Bloom filters?
- John Carmack’s Unusual Fast Inverse Square Root (Quake III)
- Cache Invalidation — Is there a General Solution?
- recursion versus iteration
- Fast permutation -> number -> permutation mapping algorithms
- Difference between Prim’s and Dijkstra’s algorithms?
- Time complexity of Euclid’s Algorithm
- Is there a perfect algorithm for chess? [closed]
- What is O(log* N)?
- Worst case in Max-Heapify – How do you get 2n/3?
- Find all paths between two graph nodes
- Efficient list intersection algorithm
- Explain Merkle Trees for use in Eventual Consistency
- Finding out nth fibonacci number for very large ‘n’
- Programming theory: Solve a maze
- How do I scale one rectangle to the maximum size possible within another rectangle?
- Best data structure for implementing a dictionary?
- What distribution do you get from this broken random shuffle?
- Graph auto-layout algorithm
- Algorithm to determine how positive or negative a statement/text is
- Algorithm to mix sound
- Getting the submatrix with maximum sum?
- Javascript data structures library [closed]
- How to efficiently compute average on the fly (moving average)?
- How much do two rectangles overlap?
- why is merge sort preferred over quick sort for sorting linked lists
- How do I efficiently determine if a polygon is convex, non-convex or complex?
- Problem: Bob’s Sale
- Good algorithm and data structure for looking up words with missing letters?
- Difference between average case and amortized analysis
- Why in a heap implemented by array the index 0 is left unused?
- Collision detection of huge number of circles
- Quicksort superiority over Heap Sort
- Given two arrays, find the permutations that give closest distance between two arrays
- Finding anagrams for a given word
- Why is the runtime of the selection algorithm O(n)?
- Smoothing values over time: moving average or something better?
- Iterative deepening vs depth-first search
- Random points inside a parallelogram