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
