KMeans for big data using preconditioning and sparsification, Matlab implementation
The code provides kmeans_sparsified which is used much like the kmeans function from the Statistics toolbox in Matlab.
There are three benefits:
- The basic implementation is much faster than the Statistics toolbox version. We also have a few modern options that the toolbox version lacks; e.g., we implement K-means++ for initialization.
- We have a new variant, called sparsified KMeans, that preconditions and then samples the data, and this version can be thousands of times faster, and is designed for big data sets that are unmangeable otherwise
- The code also allows a big-data option. Instead of passing in a matrix of data, you give it the location of a .mat file, and the code will break the data into chunks. This is useful when the data is, say, 10 TB and your computer only has 6 GB of RAM. The data is loaded in smaller chunks (e.g., less than 6 GB), which is then preconditioned and sampled and discareded from RAM, andn then the next data chunk is processed. The entire algorithm is one-pass over the dataset.
Every time you start a new Matlab session, run setup_kmeans and it will correctly set the paths. The first time you run it, it may also compile some mex files; for this, you need a valid C compiler (see http://www.mathworks.com/support/compilers/R2015a/index.html).
- Stephen Becker, University of Colorado Boulder (Applied Mathematics)
- Farhad Pourkamali Anaraki, University of Colorado Boulder (Electrical Engineering)