8000 [MRG+1] Fix OPTICS processing order by kno10 · Pull Request #12357 · scikit-learn/scikit-learn · GitHub
[go: up one dir, main page]
Skip to content

[MRG+1] Fix OPTICS processing order #12357

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 2 commits into from
Oct 14, 2018
Merged

[MRG+1] Fix OPTICS processing order #12357

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
2 commits
Select commit Hold shift + click to select a range
dd95eba
Add a test case for OPTICS bug (closes #12134)
kno10 Sep 22, 2018
43a8770
ENH Fix processing order in OPTICS. See #12090
kno10 Sep 22, 2018
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
4 changes: 2 additions & 2 deletions doc/whats_new/v0.21.rst
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -45,8 +45,8 @@ Support for Python 3.4 and below has been officially dropped.

- |MajorFeature| A new clustering algorithm: :class:`cluster.OPTICS`: an
algoritm related to :class:`cluster.DBSCAN`, that has hyperparameters easier
to set and that scales better, by :user:`Shane <espg>` and
:user:`Adrin Jalali <adrinjalali>`.
to set and that scales better, by :user:`Shane <espg>`,
:user:`Adrin Jalali <adrinjalali>`, and :user:`Erich Schubert <kno10>`.

:mod:`sklearn.preprocessing`
............................
Expand Down
38 changes: 0 additions & 38 deletions sklearn/cluster/_optics_inner.pyx
View file
Open in desktop

This file was deleted.

25 changes: 19 additions & 6 deletions sklearn/cluster/optics_.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -20,7 +20,6 @@
from ..neighbors import NearestNeighbors
from ..base import BaseEstimator, ClusterMixin
from ..metrics import pairwise_distances
from ._optics_inner import quick_scan


def optics(X, min_samples=5, max_eps=np.inf, metric='euclidean',
Expand All @@ -37,6 +36,13 @@ def optics(X, min_samples=5, max_eps=np.inf, metric='euclidean',
neighborhood radius. Better suited for usage on large point datasets than
the current sklearn implementation of DBSCAN.

This implementation deviates from the original OPTICS by first performing
k-nearest-neighborhood searches on all points to identify core sizes, then
computing only the distances to unprocessed points when constructing the
cluster order. It also does not employ a heap to manage the expansion
candiates, but rather uses numpy masked arrays. This can be potentially
slower with some parameters (at the benefit from using fast numpy code).

Read more in the :ref:`User Guide <optics>`.

Parameters
Expand Down Expand Up @@ -190,6 +196,11 @@ class OPTICS(BaseEstimator, ClusterMixin):
neighborhood radius. Better suited for usage on large point datasets than
the current sklearn implementation of DBSCAN.

This implementation deviates from the original OPTICS by first performing
k-nearest-neighborhood searches on all points to identify core sizes, then
computing only the distances to unprocessed points when constructing the
cluster order.

Read more in the :ref:`User Guide <optics>`.

Parameters
Expand Down Expand Up @@ -313,15 +324,15 @@ class OPTICS(BaseEstimator, ClusterMixin):
``clust 8000 .reachability_[clust.ordering_]`` to access in cluster order.

ordering_ : array, shape (n_samples,)
The cluster ordered list of sample indices
The cluster ordered list of sample indices.

core_distances_ : array, shape (n_samples,)
Distance at which each sample becomes a core point, indexed by object
order. Points which will never be core have a distance of inf. Use
``clust.core_distances_[clust.ordering_]`` to access in cluster order.

predecessor_ : array, shape (n_samples,)
Point that a sample was reached from.
Point that a sample was reached from, indexed by object order.
Seed points have a predecessor of -1.

See also
Expand Down Expand Up @@ -516,9 +527,11 @@ def _set_reach_dist(self, point_index, processed, X, nbrs):
self.reachability_[unproc[improved]] = rdists[improved]
self.predecessor_[unproc[improved]] = point_index

# Define return order based on reachability distance
return (unproc[quick_scan(np.take(self.reachability_, unproc),
dists)])
# Choose next based on smallest reachability distance
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Maybe add a comment like this : if there're multiple points with the same reachability distance, then we ...

# (And prefer smaller ids on ties).
# All unprocessed points qualify, not just new neighbors ("unproc")
return (np.ma.array(self.reachability_, mask=processed)
.argmin(fill_value=np.inf))

def extract_dbscan(self, eps):
"""Performs DBSCAN extraction for an arbitrary epsilon.
Expand Down
4 changes: 0 additions & 4 deletions sklearn/cluster/setup.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -23,10 +23,6 @@ def configuration(parent_package='', top_path=None):
sources=['_dbscan_inner.pyx'],
include_dirs=[numpy.get_include()],
language="c++")
config.add_extension('_optics_inner',
sources=['_optics_inner.pyx'],
include_dirs=[numpy.get_include()],
libraries=libraries)

config.add_extension('_hierarchical',
sources=['_hierarchical.pyx'],
Expand Down
Loading
0