{"action":"created","issue":{"url":"https://api.github.com/repos/scikit-learn/scikit-learn/issues/2008","labels_url":"https://api.github.com/repos/scikit-learn/scikit-learn/issues/2008/labels{/name}","comments_url":"https://api.github.com/repos/scikit-learn/scikit-learn/issues/2008/comments","events_url":"https://api.github.com/repos/scikit-learn/scikit-learn/issues/2008/events","html_url":"https://github.com/scikit-learn/scikit-learn/pull/2008","id":14800000,"number":2008,"title":"WIP Elkan k-means","user":{"login":"amueller","id":449558,"avatar_url":"https://avatars.githubusercontent.com/u/449558?v=3","gravatar_id":"","url":"https://api.github.com/users/amueller","html_url":"https://github.com/amueller","followers_url":"https://api.github.com/users/amueller/followers","following_url":"https://api.github.com/users/amueller/following{/other_user}","gists_url":"https://api.github.com/users/amueller/gists{/gist_id}","starred_url":"https://api.github.com/users/amueller/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/amueller/subscriptions","organizations_url":"https://api.github.com/users/amueller/orgs","repos_url":"https://api.github.com/users/amueller/repos","events_url":"https://api.github.com/users/amueller/events{/privacy}","received_events_url":"https://api.github.com/users/amueller/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":1,"created_at":"2013-05-27T14:19:17Z","updated_at":"2015-04-09T21:09:43Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/scikit-learn/scikit-learn/pulls/2008","html_url":"https://github.com/scikit-learn/scikit-learn/pull/2008","diff_url":"https://github.com/scikit-learn/scikit-learn/pull/2008.diff","patch_url":"https://github.com/scikit-learn/scikit-learn/pull/2008.patch"},"body":"This is an old pr for an accelerated K-Means implementation.\r\nI am not sure why I thought it was slow, it actually looks not too shabby:\r\n\r\nbenchmarking [here](https://gist.github.com/amueller/dce0841b9bda4a597335):\r\n```\r\n\r\nn_clusters = 3\r\ndigits\r\nlloyd time: 0.028653 inertia: 1733032.689910\r\nelkan time: 0.017471 inertia: 1733032.689910\r\niris\r\nlloyd time: 0.002176 inertia: 78.945066\r\nelkan time: 0.002279 inertia: 78.945066\r\nmnist\r\nlloyd time: 21.133714 inertia: 213604863631.214050\r\nelkan time: 3.947992 inertia: 219624625318.684296\r\nmnist.T\r\nlloyd time: 12.684101 inertia: 223006838798.008301\r\nelkan time: 5.028256 inertia: 229492418949.734283\r\n\r\nn_clusters = 10\r\ndigits\r\nlloyd time: 0.055593 inertia: 1165142.004619\r\nelkan time: 0.020247 inertia: 1165142.004619\r\niris\r\nlloyd time: 0.001268 inertia: 26.582819\r\nelkan time: 0.001245 inertia: 26.582819\r\nmnist\r\nlloyd time: 134.436917 inertia: 178462558367.345459\r\nelkan time: 3.798663 inertia: 185425965229.923004\r\nmnist.T\r\nlloyd time: 15.768814 inertia: 179957987722.406860\r\nelkan time: 5.269035 inertia: 176726576301.085938\r\n\r\nn_clusters = 100\r\ndigits\r\nlloyd time: 0.206861 inertia: 590828.045549\r\nelkan time: 0.051845 inertia: 588733.951315\r\niris\r\nlloyd time: 0.002030 inertia: 2.720000\r\nelkan time: 0.002651 inertia: 2.766667\r\nmnist\r\nlloyd time: 1502.579576 inertia: 127426420029.702515\r\nelkan time: 17.265350 inertia: 128080224680.242188\r\nmnist.T\r\nlloyd time: 172.475294 inertia: 78912667991.498444\r\nelkan time: 22.524726 inertia: 78459207541.870010\r\n```\r\n\r\n\r\nThere seem to be some slight differences in the results, caused by slightly different stopping criteria, I think.\r\n\r\nI need to rebase."},"comment":{"url":"https://api.github.com/repos/scikit-learn/scikit-learn/issues/comments/91356813","html_url":"https://github.com/scikit-learn/scikit-learn/pull/2008#issuecomment-91356813","issue_url":"https://api.github.com/repos/scikit-learn/scikit-learn/issues/2008","id":91356813,"user":{"login":"amueller","id":449558,"avatar_url":"https://avatars.githubusercontent.com/u/449558?v=3","gravatar_id":"","url":"https://api.github.com/users/amueller","html_url":"https://github.com/amueller","followers_url":"https://api.github.com/users/amueller/followers","following_url":"https://api.github.com/users/amueller/following{/other_user}","gists_url":"https://api.github.com/users/amueller/gists{/gist_id}","starred_url":"https://api.github.com/users/amueller/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/amueller/subscriptions","organizations_url":"https://api.github.com/users/amueller/orgs","repos_url":"https://api.github.com/users/amueller/repos","events_url":"https://api.github.com/users/amueller/events{/privacy}","received_events_url":"https://api.github.com/users/amueller/received_events","type":"User","site_admin":false},"created_at":"2015-04-09T21:09:43Z","updated_at":"2015-04-09T21:09:43Z","body":"I ran the substantially faster MNIST with 100 clusters with higher tol, to see how well we do when trying to reproduce the lloyd algorithm results.\r\nWith ``tol=1e-6`` I get\r\nelkan time: 44.1879 inertia: 127430761035.275131\r\nwhich is not entirely as good, but seems pretty close."}}