scikit-learn/scikit-learn — pull request #4025 by cemoody (2014-12-29 06:37:30+00:00)
Title: Cemoody/bhtsne

## Introduction

This PR presents the Barnes-Hut implementation of t-SNE. t-SNE is used to visualize high-dimensional data in a low dimensional space that attempts preserve the pairwise high-dimensional similarities in a low-dimensional embedding. The Barnes-Hut algorithm, which is used by astrophysicists to perform N-body simulations, allows the calculation of the t-SNE embedding in O(NlogN) time instead of O(N^2).

This effectively allows us to learn embeddings of data sets with millions of elements instead of tens of thousands.

## Example

An iPython Notebook is available where we've put together simple install instructions & a demo of both methods:
http://nbviewer.ipython.org/urls/gist.githubusercontent.com/cemoody/01135ef2f26837548360/raw/76ce7f0bac916a516501ead719b513b22430cad0/Barnes-Hut%20t-SNE%20Demo.ipynb

![bhtsne](https://cloud.githubusercontent.com/assets/3419930/5566392/24d8b7dc-8edb-11e4-9e67-4f319fc6dc59.png)

## Performance
This compares the timings for the Barnes-Hut approximation against the current method (note the log y-axis).
![timing](https://cloud.githubusercontent.com/assets/3419930/5566359/f0c7579c-8ed9-11e4-974e-903a839fe9cd.png)

The following diagram shows the relative speedup between both versions:
![speedup](https://cloud.githubusercontent.com/assets/3419930/5566360/f4802f94-8ed9-11e4-891c-da999a0426e8.png)

## TODO

- [ ] Create fit & transform methods to update using new data
- [ ] Change sparse inputs to use method='standard'
- [ ] Change dimension > 4 to use method='standard'
- [ ] Warnings for 64bit being transformed to 32bit
- [ ] Do we have memory leaks?
- [ ] Segfaults on data larger than 50k elements
- [x] PEP8 the code
- [x] Include usage documentation
- [x] Remove extra imports, print statements, pdb statements
- [x] Ensure python 3 works
- [x] Ensure output dimensionality works for 2D or 3D
- [x] Am I using memviews or returning full arrays appropriately?
- [x] Incorporate into SKLearn
- [x] Remove GIL as much as possible in Cython code
- [x] Add answer tests
- [x] Ensure old t-SNE tests works
- [x] Changed perplexity calculation to nearest neighbors
- [x] Changed positive gradient calc to nearest neighbors

## Learn

- You can read more about the technique in general here:

http://lvdmaaten.github.io/tsne/

- The Barnes-Hut approximation is here:

http://lvdmaaten.github.io/publications/papers/JMLR_2014.pdf