scikit-learn · glemaitre · Nov 10, 2022 · Oct 24, 2022 · Oct 24, 2022 · Oct 24, 2022
diff --git a/doc/whats_new/v1.2.rst b/doc/whats_new/v1.2.rst
@@ -520,6 +520,11 @@ Changelog
   :pr:`10468` by :user:`Ruben <icfly2>` and :pr:`22993` by
   :user:`Jovan Stojanovic <jovan-stojanovic>`.
 
+- |Enhancement| :class:`neighbors.NeighborsBase` now accepts
+  Minkowski semi-metric (i.e. when :math:`0 < p < 1` for
+  `metric="minkowski"`) for `algorithm="auto"` or `algorithm="brute"`.
+  :pr:`24750` by :user:`Rudresh Veerkhare <RudreshVeerkhare>`
+
 - |Efficiency| :class:`neighbors.NearestCentroid` is faster and requires
   less memory as it better leverages CPUs' caches to compute predictions.
   :pr:`24645` by :user:`Olivier Grisel <ogrisel>`.

diff --git a/sklearn/neighbors/_base.py b/sklearn/neighbors/_base.py
@@ -382,7 +382,7 @@ class NeighborsBase(MultiOutputMixin, BaseEstimator, metaclass=ABCMeta):
         "radius": [Interval(Real, 0, None, closed="both"), None],
         "algorithm": [StrOptions({"auto", "ball_tree", "kd_tree", "brute"})],
         "leaf_size": [Interval(Integral, 1, None, closed="left")],
-        "p": [Interval(Real, 1, None, closed="both"), None],
+        "p": [Interval(Real, 0, None, closed="right"), None],
         "metric": [StrOptions(set(itertools.chain(*VALID_METRICS.values()))), callable],
         "metric_params": [dict, None],
         "n_jobs": [Integral, None],
@@ -447,12 +447,6 @@ def _check_algorithm_metric(self):
                     SyntaxWarning,
                     stacklevel=3,
                 )
-            effective_p = self.metric_params["p"]
-        else:
-            effective_p = self.p
-
-        if self.metric in ["wminkowski", "minkowski"] and effective_p < 1:
-            raise ValueError("p must be greater or equal to one for minkowski metric")
 
     def _fit(self, X, y=None):
         if self._get_tags()["requires_y"]:
@@ -596,6 +590,12 @@ def _fit(self, X, y=None):
                 self._fit_method = "brute"
             else:
                 if (
+                    # TODO(1.3): remove "wminkowski"
+                    self.effective_metric_ in ("wminkowski", "minkowski")
+                    and self.effective_metric_params_["p"] < 1
+                ):
+                    self._fit_method = "brute"
+                elif (
                     self.effective_metric_ == "minkowski"
                     and self.effective_metric_params_.get("w") is not None
                 ):
@@ -619,6 +619,29 @@ def _fit(self, X, y=None):
                 else:
                     self._fit_method = "brute"
 
+        if (
+            # TODO(1.3): remove "wminkowski"
+            self.effective_metric_ in ("wminkowski", "minkowski")
+            and self.effective_metric_params_["p"] < 1
+        ):
+            # For 0 < p < 1 Minkowski distances aren't valid distance
+            # metric as they do not satisfy triangular inequality:
+            # they are semi-metrics.
+            # algorithm="kd_tree" and algorithm="ball_tree" can't be used because
+            # KDTree and BallTree require a proper distance metric to work properly.
+            # However, the brute-force algorithm supports semi-metrics.
+            if self._fit_method == "brute":
+                warnings.warn(
+                    "Mind that for 0 < p < 1, Minkowski metrics are not distance"
+                    " metrics. Continuing the execution with `algorithm='brute'`."
+                )
+            else:  # self._fit_method in ("kd_tree", "ball_tree")
+                raise ValueError(
+                    f'algorithm="{self._fit_method}" does not support 0 < p < 1 for '
+                    "the Minkowski metric. To resolve this problem either "
+                    'set p >= 1 or algorithm="brute".'
+                )
+
         if self._fit_method == "ball_tree":
             self._tree = BallTree(
                 X,

diff --git a/sklearn/neighbors/tests/test_neighbors.py b/sklearn/neighbors/tests/test_neighbors.py
@@ -1498,6 +1498,63 @@ def test_neighbors_validate_parameters(Estimator):
         nbrs.predict([[]])
 
 
+@pytest.mark.parametrize(
+    "Estimator",
+    [
+        neighbors.KNeighborsClassifier,
+        neighbors.RadiusNeighborsClassifier,
+        neighbors.KNeighborsRegressor,
+        neighbors.RadiusNeighborsRegressor,
+    ],
+)
+@pytest.mark.parametrize("n_features", [2, 100])
+@pytest.mark.parametrize("algorithm", ["auto", "brute"])
+def test_neighbors_minkowski_semimetric_algo_warn(Estimator, n_features, algorithm):
+    """
+    Validation of all classes extending NeighborsBase with
+    Minkowski semi-metrics (i.e. when 0 < p < 1). That proper
+    Warning is raised for `algorithm="auto"` and "brute".
+    """
+    X = rng.random_sample((10, n_features))
+    y = np.ones(10)
+
+    model = Estimator(p=0.1, algorithm=algorithm)
+    msg = (
+        "Mind that for 0 < p < 1, Minkowski metrics are not distance"
+        " metrics. Continuing the execution with `algorithm='brute'`."
+    )
+    with pytest.warns(UserWarning, match=msg):
+        model.fit(X, y)
+
+    assert model._fit_method == "brute"
+
+
+@pytest.mark.parametrize(
+    "Estimator",
+    [
+        neighbors.KNeighborsClassifier,
+        neighbors.RadiusNeighborsClassifier,
+        neighbors.KNeighborsRegressor,
+        neighbors.RadiusNeighborsRegressor,
+    ],
+)
+@pytest.mark.parametrize("n_features", [2, 100])
+@pytest.mark.parametrize("algorithm", ["kd_tree", "ball_tree"])
+def test_neighbors_minkowski_semimetric_algo_error(Estimator, n_features, algorithm):
+    """Check that we raise a proper error if `algorithm!='brute'` and `p<1`."""
+    X = rng.random_sample((10, 2))
+    y = np.ones(10)
+
+    model = Estimator(algorithm=algorithm, p=0.1)
+    msg = (
+        f'algorithm="{algorithm}" does not support 0 < p < 1 for '
+        "the Minkowski metric. To resolve this problem either "
+        'set p >= 1 or algorithm="brute".'
+    )
+    with pytest.raises(ValueError, match=msg):
+        model.fit(X, y)
+
+
 # TODO: remove when NearestNeighbors methods uses parameter validation mechanism
 def test_nearest_neighbors_validate_params():
     """Validate parameter of NearestNeighbors."""