Looking at the failure, it seems that this is not only a renaming. I need to investigate what the difference between the two functions in the SciPy documentation.

So apparently the definition of the metric is not the same as shown in the small example snippet in the documentation:

kulczynski1 vs. kulsinski

I am a bit blocked with the remaining error: it should be a test checking that the ball tree query provides the same results as the brute force. It seems that this is not the case with the newly implemented metric. I am wondering if there is not something fishy with the bound inf and nan when it comes to building the tree but I don't know much about the BallTree code.

Uhm no luck if the nan and inf case, so certainly something else in the BallTree.

I found the reason for the failure in the BallTree and it is indeed linked to some inf upper bound.

In the BallTree, each node defines a centroid and a radius. This radius is based on the distance between the centroid and the furthest point.

The Kulczynski distance works on data that are binarized. However, centroids are not defined with binary values. The metric itself considers that whatever value is not zero should be cast to one. We, therefore, end up in a situation where the distance between the centroid and the further point is generally inf. This will impact the search for the nearest centroids since the balls are therefore ill-defined.

Just to confirm this intuition, I modified slightly the way centroids are computed in the ball tree:

        for j in range(n_features):
            centroid[j] /= n_points
            if centroid[j] > 0.5:
                centroid[j] = 1.0
            else:
                centroid[j] = 0.0

In this case, the centroids are values expected by the metric and the test is passing.
However, I don't know if it makes sense to threshold the centroids this way.

Does it makes sense to have BallTree support "kulsinski" or even boolean distance metrics?

Does it makes sense to have BallTree support "kulsinski" or even boolean distance metrics?

It is my original question :)

We should investigate closely what happens with the Hamming distance and what is the reason for the test passing. I assume that the distance does not output inf and it makes the test pass but the results are rubbish because the median for each ball is not a binary sample and we should always compare vectors of full 1s.

Based on the context given by #20582, BallTree might have been designed for the Euclidean Distance metric case and then extended to support other distance metrics.

I agree we need to take some time to assess:

• if using BallTree with other (boolean) distance metrics makes sense.
• if kulczynski1 can be used as a proxy/replacement for kulczynski

What do you think?

I think that Ball-Tree should work for any proper metric, that is that:

• d(x, x) = 0,
• d(x, y) > 0 if x != y,
• d(x, y) = d(y, x)
• d(x, y) <= d(x, z) + d(z, y)

As noted in #25212 (review), the kulczynski1 dissimilarity is certainly not a valid metric.

So let's not include it as part of the list of valid metrics for the Ball Tree method.

As for the suitability of ball-tree for bool metrics in general, it's indeed likely that the centroid init implemented in init_node is not well adapted to them but maybe it still works thanks to a silent rounding operation to 0.0 or 1.0 in the distance computation itself for those metrics?

To keep the PR focused and not delay the fix, let's not change this as part of this PR and rather open a dedicated follow-up issue to investigate if the current ball-tree implementation is correct for boolean metrics and data. At least the test suite should be updated to test the boolean metrics (e.g. the equivalence of ball-tree vs brute) on boolean data.

To address #25202, I think the best would just be to conditionally resolve metric="kulsinski" to KulsinskiDistance{,32} which is already present in the code base (we do not need to introduce kulczynski1 for this).

#25285 has been opened in this regards.

To address #25202, I think the best would just be to conditionally resolve metric="kulsinski" to KulsinskiDistance{,32} which is already present in the code base (we do not need to introduce kulczynski1 for this).

But kulczynski1 is different from kulsinski. We should stop providing support for kulsinkski so I don't think conditionally resolving our implementation is a wise choice here.

I can see the following items to go forward:

• stop exposing kulsinski if SciPy does not. We use their deprecation cycle in this manner.
• allow kulczynski1 in pairwise distances computation by using SciPy.
• remove KulsinskiDistance because it does not implement the right "metric"
• stop exposing KulsinskiDistance as a valid metric in the BallTree
• decide whether or not to implement Kulczynski1Distance in DistanceMetric.

Can we remove support for "kulsinski" and not bring explicit support for "kulczynski1"?

Can we remove support for "kulsinski" and not bring explicit support for "kulczynski1"?

Why not? Apparently they do not compute the same thing.

The plan proposed in #25212 (comment) sounds good to me.

We can probably split it into 2 or more PRs to ease review.

We losing coverage because we are testing the future (SciPy 1.11) for which we don't collect coverage.

@glemaitre: to you, which parts of the plan proposed in #25212 (comment) should we treat in this PR?

I think this PR can focus on:

• stop exposing kulsinski if SciPy does not. We use their deprecation cycle in this manner.
• stop exposing KulsinskiDistance as a valid metric in the BallTree

What do you think?

By splitting the PR, I have no hope to introduce kulzynski1 by the lack of reviewers.

allow kulczynski1 in pairwise distances computation by using SciPy.

I prefer to disallow kulczynski1 even if SciPy supports it. Given that kulczynski1 is a dissimilarity and gives d(x, x) == inf (as shown in #25212 (review)), the diagonal of the pairwise distance matrix would be inf.

I prefer to disallow kulczynski1 even if SciPy supports it.

I am find with that as well. We can always introduce it in a later version if users ask for it.