{"action":"created","comment":{"url":"https://api.github.com/repos/scikit-learn/scikit-learn/pulls/comments/23848078","id":23848078,"diff_hunk":"@@ -0,0 +1,682 @@\n+# cython: boundscheck=False\n+# cython: wraparound=False\n+# cython: cdivision=True\n+# Author: Christopher Moody <chrisemoody@gmail.com>\n+# Author: Nick Travers <nickt@squareup.com>\n+# Implementation by Chris Moody & Nick Travers\n+# See http://homepage.tudelft.nl/19j49/t-SNE.html for reference\n+# implementations and papers describing the technique\n+\n+\n+from libc.stdlib cimport malloc, free\n+from libc.stdio cimport printf\n+from libc.math cimport sqrt\n+cimport numpy as np\n+import numpy as np\n+\n+cdef extern from \"math.h\":\n+    float fabsf(float x) nogil\n+\n+# Round points differing by less than this amount\n+# effectively ignoring differences near the 32bit \n+# floating point precision\n+cdef float EPSILON = 1e-6\n+\n+# This is effectively an ifdef statement in Cython\n+# It allows us to write printf debugging lines\n+# and remove them at compile time\n+cdef enum:\n+    DEBUGFLAG = 0\n+\n+cdef extern from \"time.h\":\n+    # Declare only what is necessary from `tm` structure.\n+    ctypedef long clock_t\n+    clock_t clock() nogil\n+    double CLOCKS_PER_SEC\n+\n+\n+cdef struct Node:\n+    # Keep track of the center of mass\n+    float[3] cum_com\n+    # If this is a leaf, the position of the particle within this leaf \n+    float[3] cur_pos\n+    # The number of particles including all \n+    # nodes below this one\n+    long cum_size\n+    # Number of particles at this node\n+    long size\n+    # Index of the particle at this node\n+    long point_index\n+    # level = 0 is the root node\n+    # And each subdivision adds 1 to the level\n+    long level\n+    # Left edge of this node, normalized to [0,1]\n+    float[3] le\n+    # The center of this node, equal to le + w/2.0\n+    float[3] c\n+    # The width of this node -- used to calculate the opening\n+    # angle. Equal to width = re - le\n+    float[3] w\n+\n+    # Does this node have children?\n+    # Default to leaf until we add particles\n+    int is_leaf\n+    # Keep pointers to the child nodes\n+    Node *children[2][2][2]","path":"sklearn/manifold/_barnes_hut_tsne.pyx","position":65,"original_position":65,"commit_id":"955ac8b7b7c6339053a2f5daaa11868ac2fc1df3","original_commit_id":"955ac8b7b7c6339053a2f5daaa11868ac2fc1df3","user":{"login":"ogrisel","id":89061,"avatar_url":"https://avatars.githubusercontent.com/u/89061?v=3","gravatar_id":"","url":"https://api.github.com/users/ogrisel","html_url":"https://github.com/ogrisel","followers_url":"https://api.github.com/users/ogrisel/followers","following_url":"https://api.github.com/users/ogrisel/following{/other_user}","gists_url":"https://api.github.com/users/ogrisel/gists{/gist_id}","starred_url":"https://api.github.com/users/ogrisel/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ogrisel/subscriptions","organizations_url":"https://api.github.com/users/ogrisel/orgs","repos_url":"https://api.github.com/users/ogrisel/repos","events_url":"https://api.github.com/users/ogrisel/events{/privacy}","received_events_url":"https://api.github.com/users/ogrisel/received_events","type":"User","site_admin":false},"body":"I would add a comment to explain that for a quad tree, only the first element of the last dimension is used, while for octree both elements of the 3 dimensions are used.","created_at":"2015-01-30T15:16:41Z","updated_at":"2015-01-30T15:16:41Z","html_url":"https://github.com/scikit-learn/scikit-learn/pull/4025#discussion_r23848078","pull_request_url":"https://api.github.com/repos/scikit-learn/scikit-learn/pulls/4025","_links":{"self":{"href":"https://api.github.com/repos/scikit-learn/scikit-learn/pulls/comments/23848078"},"html":{"href":"https://github.com/scikit-learn/scikit-learn/pull/4025#discussion_r23848078"},"pull_request":{"href":"https://api.github.com/repos/scikit-learn/scikit-learn/pulls/4025"}}},"pull_request":{"url":"https://api.github.com/repos/scikit-learn/scikit-learn/pulls/4025","id":26633619,"html_url":"https://github.com/scikit-learn/scikit-learn/pull/4025","diff_url":"https://github.com/scikit-learn/scikit-learn/pull/4025.diff","patch_url":"https://github.com/scikit-learn/scikit-learn/pull/4025.patch","issue_url":"https://api.github.com/repos/scikit-learn/scikit-learn/issues/4025","number":4025,"state":"open","locked":false,"title":"[MRG] Cemoody/bhtsne Barnes-Hut t-SNE","user":{"login":"cemoody","id":3419930,"avatar_url":"https://avatars.githubusercontent.com/u/3419930?v=3","gravatar_id":"","url":"https://api.github.com/users/cemoody","html_url":"https://github.com/cemoody","followers_url":"https://api.github.com/users/cemoody/followers","following_url":"https://api.github.com/users/cemoody/following{/other_user}","gists_url":"https://api.github.com/users/cemoody/gists{/gist_id}","starred_url":"https://api.github.com/users/cemoody/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/cemoody/subscriptions","organizations_url":"https://api.github.com/users/cemoody/orgs","repos_url":"https://api.github.com/users/cemoody/repos","events_url":"https://api.github.com/users/cemoody/events{/privacy}","received_events_url":"https://api.github.com/users/cemoody/received_events","type":"User","site_admin":false},"body":"## Introduction\r\n\r\nThis 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). \r\n\r\nThis effectively allows us to learn embeddings of data sets with millions of elements instead of tens of thousands.\r\n\r\n## Example\r\n\r\nAn IPython Notebook is available where we've put together simple install instructions & a demo of both methods:\r\nhttp://nbviewer.ipython.org/urls/gist.githubusercontent.com/cemoody/01135ef2f26837548360/raw/76ce7f0bac916a516501ead719b513b22430cad0/Barnes-Hut%20t-SNE%20Demo.ipynb\r\n\r\n![bhtsne](https://cloud.githubusercontent.com/assets/3419930/5566392/24d8b7dc-8edb-11e4-9e67-4f319fc6dc59.png)\r\n\r\n## Performance\r\nThis compares the timings for the Barnes-Hut approximation against the current method (note the log y-axis).\r\n\r\n![timing](https://cloud.githubusercontent.com/assets/3419930/5566592/9f8ba956-8ee2-11e4-88e9-2504485f06c2.png)\r\n\r\nThe following diagram shows the relative speedup between both versions:\r\n![speedup](https://cloud.githubusercontent.com/assets/3419930/5566360/f4802f94-8ed9-11e4-891c-da999a0426e8.png)\r\n\r\n## TODO \r\n\r\n- [x] Create fit & transform methods to update using new data\r\n- [x] Add test for transform called before fit\r\n- [x] Add test for skip_num_points\r\n- [x] Raise error if method='barnes_hut' and using sparse data\r\n- [x] Raise error if method='barnes_hut' and embedding dim > 3 \r\n- [x] Transform 64bit input floats to 32bit\r\n- [x] Update the narrative documentation in doc/modules/manifold.rst\r\n- [x] Add toy data to test perplexity\r\n- [x] Fix failing tests\r\n- [x] Expose tree consistency checks as unit tests\r\n- [x] Fix memory leaks\r\n- [x] Segfaults on data larger than 50k elements\r\n- [x] PEP8 the code\r\n- [x] Include usage documentation\r\n- [x] Remove extra imports, print statements, pdb statements\r\n- [x] Ensure python 3 works\r\n- [x] Ensure output dimensionality works for 2D or 3D\r\n- [x] Am I using memviews or returning full arrays appropriately?\r\n- [x] Incorporate into SKLearn\r\n- [x] Remove GIL as much as possible in Cython code\r\n- [x] Add answer tests\r\n- [x] Ensure old t-SNE tests works\r\n- [x] Changed perplexity calculation to nearest neighbors\r\n- [x] Changed positive gradient calc to nearest neighbors\r\n\r\n## Learn\r\n\r\n- You can read more about the technique in general here:\r\n\r\nhttp://lvdmaaten.github.io/tsne/\r\n\r\n- The Barnes-Hut approximation is here:\r\n\r\nhttp://lvdmaaten.github.io/publications/papers/JMLR_2014.pdf\r\n","created_at":"2014-12-29T06:37:30Z","updated_at":"2015-01-30T15:16:41Z","closed_at":null,"merged_at":null,"merge_commit_sha":"c2c84e7ce44c761c4c3ffb10634399140b41c8e5","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/scikit-learn/scikit-learn/pulls/4025/commits","review_comments_url":"https://api.github.com/repos/scikit-learn/scikit-learn/pulls/4025/comments","review_comment_url":"https://api.github.com/repos/scikit-learn/scikit-learn/pulls/comments/{number}","comments_url":"https://api.github.com/repos/scikit-learn/scikit-learn/issues/4025/comments","statuses_url":"https://api.github.com/repos/scikit-learn/scikit-learn/statuses/955ac8b7b7c6339053a2f5daaa11868ac2fc1df3","head":{"label":"cemoody:cemoody/bhtsne","ref":"cemoody/bhtsne","sha":"955ac8b7b7c6339053a2f5daaa11868ac2fc1df3","user":{"login":"cemoody","id":3419930,"avatar_url":"https://avatars.githubusercontent.com/u/3419930?v=3","gravatar_id":"","url":"https://api.github.com/users/cemoody","html_url":"https://github.com/cemoody","followers_url":"https://api.github.com/users/cemoody/followers","following_url":"https://api.github.com/users/cemoody/following{/other_user}","gists_url":"https://api.github.com/users/cemoody/gists{/gist_id}","starred_url":"https://api.github.com/users/cemoody/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/cemoody/subscriptions","organizations_url":"https://api.github.com/users/cemoody/orgs","repos_url":"https://api.github.com/users/cemoody/repos","events_url":"https://api.github.com/users/cemoody/events{/privacy}","received_events_url":"https://api.github.com/users/cemoody/received_events","type":"User","site_admin":false},"repo":{"id":28122569,"name":"scikit-learn","full_name":"cemoody/scikit-learn","owner":{"login":"cemoody","id":3419930,"avatar_url":"https://avatars.githubusercontent.com/u/3419930?v=3","gravatar_id":"","url":"https://api.github.com/users/cemoody","html_url":"https://github.com/cemoody","followers_url":"https://api.github.com/users/cemoody/followers","following_url":"https://api.github.com/users/cemoody/following{/other_user}","gists_url":"https://api.github.com/users/cemoody/gists{/gist_id}","starred_url":"https://api.github.com/users/cemoody/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/cemoody/subscriptions","organizations_url":"https://api.github.com/users/cemoody/orgs","repos_url":"https://api.github.com/users/cemoody/repos","events_url":"https://api.github.com/users/cemoody/events{/privacy}","received_events_url":"https://api.github.com/users/cemoody/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/cemoody/scikit-learn","description":"scikit-learn: machine learning in Python","fork":true,"url":"https://api.github.com/repos/cemoody/scikit-learn","forks_url":"https://api.github.com/repos/cemoody/scikit-learn/forks","keys_url":"https://api.github.com/repos/cemoody/scikit-learn/keys{/key_id}","collaborators_url":"https://api.github.com/repos/cemoody/scikit-learn/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/cemoody/scikit-learn/teams","hooks_url":"https://api.github.com/repos/cemoody/scikit-learn/hooks","issue_events_url":"https://api.github.com/repos/cemoody/scikit-learn/issues/events{/number}","events_url":"https://api.github.com/repos/cemoody/scikit-learn/events","assignees_url":"https://api.github.com/repos/cemoody/scikit-learn/assignees{/user}","branches_url":"https://api.github.com/repos/cemoody/scikit-learn/branches{/branch}","tags_url":"https://api.github.com/repos/cemoody/scikit-learn/tags","blobs_url":"https://api.github.com/repos/cemoody/scikit-learn/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/cemoody/scikit-learn/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/cemoody/scikit-learn/git/refs{/sha}","trees_url":"https://api.github.com/repos/cemoody/scikit-learn/git/trees{/sha}","statuses_url":"https://api.github.com/repos/cemoody/scikit-learn/statuses/{sha}","languages_url":"https://api.github.com/repos/cemoody/scikit-learn/languages","stargazers_url":"https://api.github.com/repos/cemoody/scikit-learn/stargazers","contributors_url":"https://api.github.com/repos/cemoody/scikit-learn/contributors","subscribers_url":"https://api.github.com/repos/cemoody/scikit-learn/subscribers","subscription_url":"https://api.github.com/repos/cemoody/scikit-learn/subscription","commits_url":"https://api.github.com/repos/cemoody/scikit-learn/commits{/sha}","git_commits_url":"https://api.github.com/repos/cemoody/scikit-learn/git/commits{/sha}","comments_url":"https://api.github.com/repos/cemoody/scikit-learn/comments{/number}","issue_comment_url":"https://api.github.com/repos/cemoody/scikit-learn/issues/comments/{number}","contents_url":"https://api.github.com/repos/cemoody/scikit-learn/contents/{+path}","compare_url":"https://api.github.com/repos/cemoody/scikit-learn/compare/{base}...{head}","merges_url":"https://api.github.com/repos/cemoody/scikit-learn/merges","archive_url":"https://api.github.com/repos/cemoody/scikit-learn/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/cemoody/scikit-learn/downloads","issues_url":"https://api.github.com/repos/cemoody/scikit-learn/issues{/number}","pulls_url":"https://api.github.com/repos/cemoody/scikit-learn/pulls{/number}","milestones_url":"https://api.github.com/repos/cemoody/scikit-learn/milestones{/number}","notifications_url":"https://api.github.com/repos/cemoody/scikit-learn/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/cemoody/scikit-learn/labels{/name}","releases_url":"https://api.github.com/repos/cemoody/scikit-learn/releases{/id}","created_at":"2014-12-17T05:24:16Z","updated_at":"2015-01-20T15:33:55Z","pushed_at":"2015-01-22T01:07:40Z","git_url":"git://github.com/cemoody/scikit-learn.git","ssh_url":"git@github.com:cemoody/scikit-learn.git","clone_url":"https://github.com/cemoody/scikit-learn.git","svn_url":"https://github.com/cemoody/scikit-learn","homepage":"http://scikit-learn.org","size":59897,"stargazers_count":1,"watchers_count":1,"language":"C","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":1,"mirror_url":null,"open_issues_count":1,"forks":1,"open_issues":1,"watchers":1,"default_branch":"master"}},"base":{"label":"scikit-learn:master","ref":"master","sha":"d9ecf46f41d77a235b064a6c842079114b80ec5d","user":{"login":"scikit-learn","id":365630,"avatar_url":"https://avatars.githubusercontent.com/u/365630?v=3","gravatar_id":"","url":"https://api.github.com/users/scikit-learn","html_url":"https://github.com/scikit-learn","followers_url":"https://api.github.com/users/scikit-learn/followers","following_url":"https://api.github.com/users/scikit-learn/following{/other_user}","gists_url":"https://api.github.com/users/scikit-learn/gists{/gist_id}","starred_url":"https://api.github.com/users/scikit-learn/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/scikit-learn/subscriptions","organizations_url":"https://api.github.com/users/scikit-learn/orgs","repos_url":"https://api.github.com/users/scikit-learn/repos","events_url":"https://api.github.com/users/scikit-learn/events{/privacy}","received_events_url":"https://api.github.com/users/scikit-learn/received_events","type":"Organization","site_admin":false},"repo":{"id":843222,"name":"scikit-learn","full_name":"scikit-learn/scikit-learn","owner":{"login":"scikit-learn","id":365630,"avatar_url":"https://avatars.githubusercontent.com/u/365630?v=3","gravatar_id":"","url":"https://api.github.com/users/scikit-learn","html_url":"https://github.com/scikit-learn","followers_url":"https://api.github.com/users/scikit-learn/followers","following_url":"https://api.github.com/users/scikit-learn/following{/other_user}","gists_url":"https://api.github.com/users/scikit-learn/gists{/gist_id}","starred_url":"https://api.github.com/users/scikit-learn/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/scikit-learn/subscriptions","organizations_url":"https://api.github.com/users/scikit-learn/orgs","repos_url":"https://api.github.com/users/scikit-learn/repos","events_url":"https://api.github.com/users/scikit-learn/events{/privacy}","received_events_url":"https://api.github.com/users/scikit-learn/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/scikit-learn/scikit-learn","description":"scikit-learn: machine learning in Python","fork":false,"url":"https://api.github.com/repos/scikit-learn/scikit-learn","forks_url":"https://api.github.com/repos/scikit-learn/scikit-learn/forks","keys_url":"https://api.github.com/repos/scikit-learn/scikit-learn/keys{/key_id}","collaborators_url":"https://api.github.com/repos/scikit-learn/scikit-learn/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/scikit-learn/scikit-learn/teams","hooks_url":"https://api.github.com/repos/scikit-learn/scikit-learn/hooks","issue_events_url":"https://api.github.com/repos/scikit-learn/scikit-learn/issues/events{/number}","events_url":"https://api.github.com/repos/scikit-learn/scikit-learn/events","assignees_url":"https://api.github.com/repos/scikit-learn/scikit-learn/assignees{/user}","branches_url":"https://api.github.com/repos/scikit-learn/scikit-learn/branches{/branch}","tags_url":"https://api.github.com/repos/scikit-learn/scikit-learn/tags","blobs_url":"https://api.github.com/repos/scikit-learn/scikit-learn/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/scikit-learn/scikit-learn/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/scikit-learn/scikit-learn/git/refs{/sha}","trees_url":"https://api.github.com/repos/scikit-learn/scikit-learn/git/trees{/sha}","statuses_url":"https://api.github.com/repos/scikit-learn/scikit-learn/statuses/{sha}","languages_url":"https://api.github.com/repos/scikit-learn/scikit-learn/languages","stargazers_url":"https://api.github.com/repos/scikit-learn/scikit-learn/stargazers","contributors_url":"https://api.github.com/repos/scikit-learn/scikit-learn/contributors","subscribers_url":"https://api.github.com/repos/scikit-learn/scikit-learn/subscribers","subscription_url":"https://api.github.com/repos/scikit-learn/scikit-learn/subscription","commits_url":"https://api.github.com/repos/scikit-learn/scikit-learn/commits{/sha}","git_commits_url":"https://api.github.com/repos/scikit-learn/scikit-learn/git/commits{/sha}","comments_url":"https://api.github.com/repos/scikit-learn/scikit-learn/comments{/number}","issue_comment_url":"https://api.github.com/repos/scikit-learn/scikit-learn/issues/comments/{number}","contents_url":"https://api.github.com/repos/scikit-learn/scikit-learn/contents/{+path}","compare_url":"https://api.github.com/repos/scikit-learn/scikit-learn/compare/{base}...{head}","merges_url":"https://api.github.com/repos/scikit-learn/scikit-learn/merges","archive_url":"https://api.github.com/repos/scikit-learn/scikit-learn/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/scikit-learn/scikit-learn/downloads","issues_url":"https://api.github.com/repos/scikit-learn/scikit-learn/issues{/number}","pulls_url":"https://api.github.com/repos/scikit-learn/scikit-learn/pulls{/number}","milestones_url":"https://api.github.com/repos/scikit-learn/scikit-learn/milestones{/number}","notifications_url":"https://api.github.com/repos/scikit-learn/scikit-learn/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/scikit-learn/scikit-learn/labels{/name}","releases_url":"https://api.github.com/repos/scikit-learn/scikit-learn/releases{/id}","created_at":"2010-08-17T09:43:38Z","updated_at":"2015-01-30T14:40:16Z","pushed_at":"2015-01-30T14:40:15Z","git_url":"git://github.com/scikit-learn/scikit-learn.git","ssh_url":"git@github.com:scikit-learn/scikit-learn.git","clone_url":"https://github.com/scikit-learn/scikit-learn.git","svn_url":"https://github.com/scikit-learn/scikit-learn","homepage":"http://scikit-learn.org","size":109696,"stargazers_count":4939,"watchers_count":4939,"language":"C","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":2887,"mirror_url":null,"open_issues_count":564,"forks":2887,"open_issues":564,"watchers":4939,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/scikit-learn/scikit-learn/pulls/4025"},"html":{"href":"https://github.com/scikit-learn/scikit-learn/pull/4025"},"issue":{"href":"https://api.github.com/repos/scikit-learn/scikit-learn/issues/4025"},"comments":{"href":"https://api.github.com/repos/scikit-learn/scikit-learn/issues/4025/comments"},"review_comments":{"href":"https://api.github.com/repos/scikit-learn/scikit-learn/pulls/4025/comments"},"review_comment":{"href":"https://api.github.com/repos/scikit-learn/scikit-learn/pulls/comments/{number}"},"commits":{"href":"https://api.github.com/repos/scikit-learn/scikit-learn/pulls/4025/commits"},"statuses":{"href":"https://api.github.com/repos/scikit-learn/scikit-learn/statuses/955ac8b7b7c6339053a2f5daaa11868ac2fc1df3"}}}}