scipy/scipy — pull request #3683 by richardtsai (2014-05-26 07:12:21+00:00)
Title: ENH: cluster: rewrite and optimized `vq` in Cython

Rewrite the underlying part of cluster.vq in Cython.

Besides, an optimized algorithm is implemented and it will improve the
performance for datasets with large nfeat when built with an optimized
BLAS library.

I tested the new algorithm on datasets of different size and I noticed that there's almost no speedup (even worse) when nfeat is small. So I switch back to naive algorithm when nfeat < 5.

![speedup_test](https://cloud.githubusercontent.com/assets/1297550/3079612/4705370e-e49f-11e3-9106-21e92ebcdaf5.png)

(N is #obs, M is #feat, K is #codes)

Performance comparison is as follows. (`vq.kmeans(obs, k)`, ATLAS 3.11.13, i5-3470)

|dataset|old (ms)|new (ms)|speedup|
|-------|--------|--------|-------|
|30000 x 100, k = 10, float64|28636.2594|16950.3884|1.69|
|30000 x 100, k = 10, float32|13575.0532|6483.4734|2.09|
|10000 x 30, k = 10, float64|1923.3946|1146.7348|1.68|
|10000 x 30, k = 10, float32|1491.8790|989.2090|1.51|
|100000 x 3, k = 4, float64|1663.1430|1181.5912|1.41|
|100000 x 3, k = 4, float32|1278.0330|967.4396|1.32|
|10000 x 1, k = 3, float64|117.6908|94.0622|1.25|
|10000 x 1, k = 3, float32|110.2874|98.6826|1.12|
|1000 x 3, k = 4, float64|29.2300|28.6970|1.02|
|1000 x 3, k = 4, float32|27.5242|29.2488|0.94|

The speedup of `vq.kmeans` is not so significant as that of `vq.vq`. It is because the update step of kmeans is still time-consuming.