[MRG] Make OPTICS support sparse input #14736

huntzhan · 2019-08-23T04:01:43Z

Reference Issues/PRs

See #12028 (comment), #11982

What does this implement/fix? Explain your changes.

Make OPTICS.fit(self, X, y=None) support the sparse matrix X.

Any other comments?

jnothman · 2019-08-23T05:13:44Z

Please add a test

…

On Fri., 23 Aug. 2019, 2:01 pm Hunt Zhan, ***@***.***> wrote: Reference Issues/PRs See #12028 (comment) <#12028 (comment)>, #11982 <#11982> What does this implement/fix? Explain your changes. Make OPTICS.fit(self, X, y=None) support the sparse matrix X. Any other comments? ------------------------------ You can view, comment on, or merge this pull request online at: #14736 Commit Summary - Try csr support. File Changes - *M* sklearn/cluster/optics_.py <https://github.com/scikit-learn/scikit-learn/pull/14736/files#diff-0> (2) Patch Links: - https://github.com/scikit-learn/scikit-learn/pull/14736.patch - https://github.com/scikit-learn/scikit-learn/pull/14736.diff — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#14736?email_source=notifications&email_token=AAATH23GHNSYA2K22NK3TFLQF5OKVA5CNFSM4IO3NUUKYY3PNVWWK3TUL52HS4DFUVEXG43VMWVGG33NNVSW45C7NFSM4HG6DQ4Q>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAATH2YURNDHD2PGE4J5UQ3QF5OKVANCNFSM4IO3NUUA> .

huntzhan · 2019-08-23T05:20:21Z

Sure. BTW, simply adding accept_sparse won't work. I'm looking into it.

sklearn/tests/test_common.py Estimator OPTICS doesn't seem to fail gracefully on sparse data: it should raise a TypeError if sparse input is explicitly not supported.
F
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> traceback >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

estimator = OPTICS(algorithm='auto', cluster_method='xi', eps=None, leaf_size=30,
       max_eps=inf, metric='minkowski', metric_params=None,
       min_cluster_size=None, min_samples=5, n_jobs=None, p=2,
       predecessor_correction=True, xi=0.05)
check = <function check_estimator_sparse_data at 0x12d122158>

    @pytest.mark.parametrize(
            "estimator, check",
            _generate_checks_per_estimator(_yield_all_checks,
                                           _tested_estimators()),
            ids=_rename_partial
    )
    def test_estimators(estimator, check):
        # Common tests for estimator instances
        with ignore_warnings(category=(DeprecationWarning, ConvergenceWarning,
                                       UserWarning, FutureWarning)):
            set_checking_parameters(estimator)
            name = estimator.__class__.__name__
>           check(name, estimator)

sklearn/tests/test_common.py:100:
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
sklearn/utils/estimator_checks.py:539: in check_estimator_sparse_data
    estimator.fit(X, y)
sklearn/cluster/optics_.py:248: in fit
    max_eps=self.max_eps)
sklearn/cluster/optics_.py:487: in compute_optics_graph
    p=p, max_eps=max_eps)
sklearn/cluster/optics_.py:520: in _set_reach_dist
    dists = pairwise_distances(P, np.take(X, unproc, axis=0),
<__array_function__ internals>:6: in take
    ???
../../../../.pyenv/versions/3.6.9/envs/scikit-learn/lib/python3.6/site-packages/numpy/core/fromnumeric.py:194: in take
    return _wrapfunc(a, 'take', indices, axis=axis, out=out, mode=mode)
../../../../.pyenv/versions/3.6.9/envs/scikit-learn/lib/python3.6/site-packages/numpy/core/fromnumeric.py:58: in _wrapfunc
    return _wrapit(obj, method, *args, **kwds)
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _

obj = <40x10 sparse matrix of type '<class 'numpy.float64'>'
	with 74 stored elements in Compressed Sparse Row format>, method = 'take'
args = (array([ 1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15, 16, 17,
       18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34,
       35, 36, 37, 38, 39]),)
kwds = {'axis': 0, 'mode': 'raise', 'out': None}, wrap = None

    def _wrapit(obj, method, *args, **kwds):
        try:
            wrap = obj.__array_wrap__
        except AttributeError:
            wrap = None
>       result = getattr(asarray(obj), method)(*args, **kwds)
E       IndexError: index 1 is out of bounds for axis 0 with size 1

huntzhan · 2019-08-23T08:16:51Z

sklearn/cluster/optics_.py

@@ -517,7 +517,7 @@ def _set_reach_dist(core_distances_, reachability_, predecessor_,
            # the same logic as neighbors, p is ignored if explicitly set
            # in the dict params
            _params['p'] = p
-        dists = pairwise_distances(P, np.take(X, unproc, axis=0),
+        dists = pairwise_distances(P, X[unproc],


np.take doesn't support the sparse matrix

huntzhan · 2019-08-23T08:18:14Z

sklearn/cluster/optics_.py

@@ -194,7 +194,7 @@ class OPTICS(BaseEstimator, ClusterMixin):
       the Conference "Lernen, Wissen, Daten, Analysen" (LWDA) (2018): 318-329.
    """

-    def __init__(self, min_samples=5, max_eps=np.inf, metric='minkowski', p=2,
+    def __init__(self, min_samples=5, max_eps=np.inf, metric='euclidean', p=2,


The default metric minkowski doesn't accept the sparse matrix.

See https://github.com/huntzhan/scikit-learn/blob/5f7e6de69e425cfdfeeb82cf692b81fe22589dd5/sklearn/metrics/pairwise.py#L1546-L1555

But this won't work if the user changes p. So I'd rather reinterpret the metric as euclidean below when using the metric, rather than changing the default

make sense.

Are you able to add commits to resolve it?

Yeah, I will resolve this issue and add test cases this week.

huntzhan · 2019-08-26T03:16:29Z

sklearn/cluster/optics_.py

@@ -19,6 +19,7 @@
 from ..neighbors import NearestNeighbors
 from ..base import BaseEstimator, ClusterMixin
 from ..metrics import pairwise_distances
+from ..metrics.pairwise import PAIRWISE_DISTANCE_FUNCTIONS


Import directly without exposing as an interface.

huntzhan · 2019-08-26T04:43:07Z

sklearn/cluster/optics_.py

@@ -233,7 +236,12 @@ def fit(self, X, y=None):
        self : instance of OPTICS
            The instance.
        """
-        X = check_array(X, dtype=np.float)
+        # TODO: Support the sparse input for metric = 'precopmuted'.
+        if self.metric != 'precomputed' \


Will have a separated PR for this.

adrinjalali

Not a complete review yet, but looks good.

adrinjalali · 2019-08-27T12:31:04Z

sklearn/cluster/optics_.py

@@ -222,7 +223,9 @@ def fit(self, X, y=None):
        Parameters
        ----------
        X : array, shape (n_samples, n_features), or (n_samples, n_samples)  \
-if metric=’precomputed’.
+if metric=’precomputed’, or sparse matrix (n_samples, n_features) if metric
+            in ['cityblock', 'cosine', 'euclidean', 'haversine', 'l2', 'l1',


Please keep the first line of the X's description short and as usual syntax, and put the information in the comments of the parameter.

adrinjalali · 2019-08-27T12:32:29Z

sklearn/cluster/optics_.py

+        # TODO: Support the sparse input for metric = 'precopmuted'.
+        if self.metric != 'precomputed' \
+                and self.metric in PAIRWISE_DISTANCE_FUNCTIONS:
+            X = check_array(X, accept_sparse='csr')


and dtype=np.float

adrinjalali · 2019-08-27T12:35:53Z

sklearn/cluster/tests/test_optics.py

+    clust = OPTICS(min_samples=3, min_cluster_size=2,
+                   max_eps=20, cluster_method='xi',
+                   xi=0.4, metric='euclidean').fit(sparse.lil_matrix(X))
+    assert_array_equal(clust.labels_, expected_labels)


I think we can parameterize the test for these ones and refactor them a bit

bittremieux · 2020-06-02T17:38:16Z

It would be nice to get OPTICS to work with sparse precomputed distance matrices. The OPTICS documentation says:

Better suited for usage on large datasets than the current sklearn implementation of DBSCAN.

But if your distance matrix doesn't fit in memory as a dense matrix you can't even use OPTICS, whereas that nicely works for DBSCAN.

yskybloue · 2021-08-21T18:22:51Z

I see this is stalled for quite a while; I'm continuing work on this on #20802

Try csr support.

5f7e6de

Change the default metric of OPTICS to euclidean.

18425aa

huntzhan commented Aug 23, 2019

View reviewed changes

Retain the default metric minkowski.

f712b46

huntzhan commented Aug 26, 2019

View reviewed changes

huntzhan added 3 commits August 26, 2019 11:17

Undo tests.

876bb29

Fix flake8.

71b5c1e

Add sparse tests.

6f498a9

huntzhan changed the title ~~[WIP] Make OPTICS support sparse input~~ [MRG] Make OPTICS support sparse input Aug 26, 2019

huntzhan commented Aug 26, 2019

View reviewed changes

adrinjalali reviewed Aug 27, 2019

View reviewed changes

github-actions bot added the module:cluster label Mar 2, 2020

adrinjalali added help wanted Stalled labels Jun 5, 2020

Base automatically changed from master to main January 22, 2021 10:51

yskybloue mentioned this pull request Aug 21, 2021

[MRG] Add sparse input and sparse precomputed distances to sklearn/cluster/_optics.py #20802

Closed

cmarmo added Superseded PR has been replace by a newer PR and removed Stalled help wanted labels Mar 7, 2022

Micky774 mentioned this pull request Mar 27, 2022

ENH Add sparse input support to OPTICS #22965

Merged

jeremiedbb closed this in #22965 May 2, 2022

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

[MRG] Make OPTICS support sparse input #14736

[MRG] Make OPTICS support sparse input #14736

huntzhan commented Aug 23, 2019

jnothman commented Aug 23, 2019 via email

huntzhan commented Aug 23, 2019

huntzhan Aug 23, 2019

huntzhan Aug 23, 2019

jnothman Aug 24, 2019

huntzhan Aug 24, 2019

jnothman Aug 24, 2019

huntzhan Aug 26, 2019

huntzhan Aug 26, 2019

huntzhan Aug 26, 2019

adrinjalali left a comment

adrinjalali Aug 27, 2019

adrinjalali Aug 27, 2019

adrinjalali Aug 27, 2019

bittremieux commented Jun 2, 2020

yskybloue commented Aug 21, 2021

[MRG] Make OPTICS support sparse input #14736

[MRG] Make OPTICS support sparse input #14736

Conversation

huntzhan commented Aug 23, 2019

Reference Issues/PRs

What does this implement/fix? Explain your changes.

Any other comments?

jnothman commented Aug 23, 2019 via email

huntzhan commented Aug 23, 2019

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

adrinjalali left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

bittremieux commented Jun 2, 2020

yskybloue commented Aug 21, 2021