As the ball tree class implementation of scikit-learn for Euclidean (for
example) and for large amount of data has an acceptable time, I just want to
get sure if I do so, the performance will get considerably better? If yes, so
it's just worth that I give it a try. I need a time less that a minute in case
of 40000 (for example), like the ball tree class. If your answer is yes, please
if you have, at least give me a reference for getting to know how to start it.
On Friday, May 15, 2015 1:59 AM, Jacob Vanderplas
<jake...@cs.washington.edu> wrote:
If you're computing neighbors of very high dimensional data, you might
consider an approximate search instead, for example one based on Locality
Sensitive Hashing. There are some papers out there about kernelized LSH which
allow a wide range of kernels, and many metrics can be approximated with a
judiciously chosen kernel, Jake
Jake VanderPlas Director of Research – Physical Sciences eScience Institute,
University of Washington http://www.vanderplas.com
On Thu, May 14, 2015 at 4:54 PM, Jacob Vanderplas <jake...@cs.washington.edu>
wrote:
Sorry – I should have better specified what I meant.
A user-defined metric passed as a python function will always be slow, no
matter how you define that python function.
If you want to create a custom metric that works quickly within BallTree,
you'll have to write it in cython *within* the scikit-learn source: that is,
you must modify the actual .pyx files in sklearn/neighbors/*.pyx and *.pxd,
write a new metric in Cython, make this accessible via an appropriate string
argument to the BinaryTree class, and then re-compile the entire scikit-learn
package.
The procedure is not well-documented, because this is not an anticipated use of
the code and I wouldn't necessarily recommend it. That said, if you're very
familiar with using cython you should be able to proceed by using one of the
other implemented metrics as a template. Jake
Jake VanderPlas Director of Research – Physical Sciences eScience Institute,
University of Washington http://www.vanderplas.com
On Thu, May 14, 2015 at 4:10 PM, nafise mehdipoor <mehdipour...@yahoo.com>
wrote:
I just tried the one with compiling my metric with Cython and it still is too
far away from what I need it to be (around 60 seconds)! Still for the previous
code:
using 'Euclidean' metric: 30 secmetric as a function: 43 minmetric as a python
module: 27 mindo you have any other solution that I can try. I re-mention that
I still haven' applied my real metric and I just comparing the Euclidean metric
with the same user-defined one.
On Thursday, May 14, 2015 11:24 PM, nafise mehdipoor
<mehdipour...@yahoo.com> wrote:
Thank you so much. It was an example and the real metric will be defined
within ball-tree-valid-metric conditions.
The best.
On Thursday, May 14, 2015 5:47 PM, Jacob Vanderplas
<jake...@cs.washington.edu> wrote:
User-defined metrics will always be slow, because they rely on the Python
layer for callbacks. The only way to improve it is to write your own metric in
Cython and re-compile the ball tree/kd tree code with your new addition.
Furthermore, you have to make sure your metric actually meets the definition of
a true metric, or the tree code will not produce the right results. Jake
Jake VanderPlas Director of Research – Physical Sciences eScience Institute,
University of Washington http://www.vanderplas.com
On Thu, May 14, 2015 at 8:31 AM, nafise mehdipoor <mehdipour...@yahoo.com>
wrote:
Thank you all for the explanation.Here I am trying to implement the balltree
based DBSCAN algorithm and I am using the balltree class. Finally, as I meant
to use the user-defined metric, I tried it with the code below. The time for
this case is awfulDo you have any advice to improve it?Thank you.
Total time: 0:16:58.820000
-------------------------------------------------------import numpy as npfrom
sklearn.neighbors import BallTree,DistanceMetric
D = 20N =40000def myDistance(x,y): return np.sqrt(sum((x - y)**2))
beginTime = datetime.datetime.now()
dataSet = np.random.random((N, D))point = np.random.random((1, D))balltree =
BallTree(dataSet, leaf_size = 3, metric='pyfunc',func = myDistance)for i in
xrange(0,40000): ind = balltree.query_radius(point, r = 0.2) time =
datetime.datetime.now() - beginTime
print 'Total time: ', time
On Thursday, May 14, 2015 4:05 PM, Michael Eickenberg
<michael.eickenb...@gmail.com> wrote:
Using EuclideanDistance: this can actually explain a factor of 10 (probably
dimensionality-dependent)
In [56]: d = sklearn.neighbors.dist_metrics.EuclideanDistance()
In [57]: %timeit d.pairwise(x, y)
100 loops, best of 3: 6.04 ms per loop
In [58]: %timeit d.pairwise(x, y)
100 loops, best of 3: 5.93 ms per loop
In [59]: d = sklearn.neighbors.dist_metrics.MinkowskiDistance(2)
In [60]: %timeit d.pairwise(x, y)
10 loops, best of 3: 66.9 ms per loop
In [61]: d = sklearn.neighbors.dist_metrics.MinkowskiDistance(3)
In [62]: %timeit d.pairwise(x, y)
1 loops, best of 3: 377 ms per loop
On Thu, May 14, 2015 at 4:00 PM, Michael Eickenberg
<michael.eickenb...@gmail.com> wrote:
Oops, I overlooked that the comparison was against EuclideanDistance proper.
But as Jake says, some optimization does happen in the l2 case and in the
example I gave it explains a factor of 5-6.
On Thu, May 14, 2015 at 3:44 PM, Michael Eickenberg
<michael.eickenb...@gmail.com> wrote:
There may also be some implicit optimization going on. Without looking at the
(non pure-python) source of the Minkowski
metric, a few tests hint at the fact that p=2 and p=1 are probably treated
differently from the rest, because some mathematical tricks can be applied that
avoid calculating the full distance vector. So maybe some of the speed
difference is already explainable by that, but I am not sure which is the most
prevalent here, since I am unfamiliar with the internals of BallTree and how
many of these evaluations it actually does.
Michael
In [38]: d = sklearn.neighbors.dist_metrics.MinkowskiDistance(2)
In [39]: x = np.random.randn(100, 200)
In [40]: y = np.random.randn(200, 200)
In [41]: %timeit d.pairwise(x, y)
10 loops, best of 3: 66.8 ms per loop
In [42]: d = sklearn.neighbors.dist_metrics.MinkowskiDistance(2.1)
In [43]: %timeit d.pairwise(x, y)
1 loops, best of 3: 352 ms per loop
In [44]: d = sklearn.neighbors.dist_metrics.MinkowskiDistance(1.9)
In [45]: %timeit d.pairwise(x, y)
1 loops, best of 3: 353 ms per loop
In [46]: d = sklearn.neighbors.dist_metrics.MinkowskiDistance(1)
In [47]: %timeit d.pairwise(x, y)
10 loops, best of 3: 60.4 ms per loop
In [48]: d = sklearn.neighbors.dist_metrics.MinkowskiDistance(1.1)
In [49]: %timeit d.pairwise(x, y)
1 loops, best of 3: 357 ms per loop
In [50]: d = sklearn.neighbors.dist_metrics.MinkowskiDistance(10)
In [51]: %timeit d.pairwise(x, y)
1 loops, best of 3: 386 ms per loop
In [52]: d = sklearn.neighbors.dist_metrics.MinkowskiDistance(100)
In [53]: %timeit d.pairwise(x, y)
1 loops, best of 3: 403 ms per loop
In [54]: d = sklearn.neighbors.dist_metrics.MinkowskiDistance(1000)
In [55]: %timeit d.pairwise(x, y)
1 loops, best of 3: 472 ms per loop
In [56]:
On Thu, May 14, 2015 at 3:14 PM, Jacob Vanderplas <jake...@cs.washington.edu>
wrote:
Hi Nafise,In general, yes the execution time will depend on the metric, and in
a way that can be very difficult to predict.
One reason is that because the euclidean metric is the most common, that case
is slightly optimized. But that won't lead to a factor of ten.
The Ball Tree works by dividing the metric space into spherical nodes, and
depending on which metric you use, there can be more or less overlap between
the resulting nodes. As you increase the p value of a minkowski metric, there
will generally be more overlap between nodes because in some sense the amount
of space covered by a ball of radius R increases. Any node overlap means that
you're less likely to throw away branches when querying the tree, meaning that
more distance computations need to be done. All of this is highly dependent on
the precise dimension and structure of the data you're querying: e.g. if you
have uniformly-distributed data in high dimensions, there will be a larger
slowdown than if you have highly-structured low-dimensional data.
Without knowing more details about the data you're looking at, I think that's
probably what's going on. Note that if you're interested in fast queries for a
minkowski metric in particular, I'd try the KD Tree: the node overlap issue
shouldn't come up here. Jake
Jake VanderPlas Director of Research – Physical Sciences eScience Institute,
University of Washington http://www.vanderplas.com
On Thu, May 14, 2015 at 12:48 AM, nafise mehdipoor <mehdipour...@yahoo.com>
wrote:
Hi everyone,If the complexity of the balltree implementation depends on the
metric? When I run my code to cluster my points and use 'minkowski' metric
instead of 'euclidean', the time jumps from 0.8 s to 8 s!!Thank you.
------------------------------------------------------------------------------
One dashboard for servers and applications across Physical-Virtual-Cloud
Widest out-of-the-box monitoring support with 50+ applications
Performance metrics, stats and reports that give you Actionable Insights
Deep dive visibility with transaction tracing using APM Insight.
http://ad.doubleclick.net/ddm/clk/290420510;117567292;y
_______________________________________________
Scikit-learn-general mailing list
Scikit-learn-general@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/scikit-learn-general
------------------------------------------------------------------------------
One dashboard for servers and applications across Physical-Virtual-Cloud
Widest out-of-the-box monitoring support with 50+ applications
Performance metrics, stats and reports that give you Actionable Insights
Deep dive visibility with transaction tracing using APM Insight.
http://ad.doubleclick.net/ddm/clk/290420510;117567292;y
_______________________________________________
Scikit-learn-general mailing list
Scikit-learn-general@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/scikit-learn-general
------------------------------------------------------------------------------
One dashboard for servers and applications across Physical-Virtual-Cloud
Widest out-of-the-box monitoring support with 50+ applications
Performance metrics, stats and reports that give you Actionable Insights
Deep dive visibility with transaction tracing using APM Insight.
http://ad.doubleclick.net/ddm/clk/290420510;117567292;y
_______________________________________________
Scikit-learn-general mailing list
Scikit-learn-general@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/scikit-learn-general
