.. ******************************************************************************
.. * Copyright 2021 Intel Corporation
.. *
.. * Licensed under the Apache License, Version 2.0 (the "License");
.. * you may not use this file except in compliance with the License.
.. * You may obtain a copy of the License at
.. *
.. * http://www.apache.org/licenses/LICENSE-2.0
.. *
.. * Unless required by applicable law or agreed to in writing, software
.. * distributed under the License is distributed on an "AS IS" BASIS,
.. * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
.. * See the License for the specific language governing permissions and
.. * limitations under the License.
.. *******************************************************************************/
.. highlight:: cpp
.. default-domain:: cpp
.. re-use for math equations:
.. |x| replace:: :math:`x`
.. |y| replace:: :math:`y`
.. _alg_dbscan:
======
DBSCAN
======
.. include:: ../../../includes/clustering/dbscan-introduction.rst
------------------------
Mathematical formulation
------------------------
.. _dbscan_c_math:
Computation
-----------
Given the set :math:`X = \{x_1 = (x_{11}, \ldots, x_{1p}), \ldots, x_n = (x_{n1}, \ldots, x_{np})\}`
of :math:`n` :math:`p`-dimensional feature vectors (further referred as observations),
a positive floating-point number ``epsilon`` and a positive integer ``minObservations``,
the problem is to get clustering assignments for each input observation, based on the definitions below [Ester96]_:
two observations |x| and |y| are considered to be in the same cluster if there is a :term:`core observation` :math:`z`,
and |x| and |y| are both :term:`reachable` from :math:`z`.
Each cluster gets a unique identifier, an integer number from :math:`0` to :math:`\text{total number of clusters } – 1`.
Each observation is assigned an identifier of the :term:`cluster` it belongs to,
or :math:`-1` if the observation considered to be a :term:`noise observation`.
---------------------
Programming Interface
---------------------
Refer to :ref:`API Reference: DBSCAN `.
----------------
Distributed mode
----------------
The algorithm supports distributed execution in SPMD mode (only on GPU).
-------------
Usage Example
-------------
.. include:: ../../../includes/clustering/dbscan-usage-examples.rst
--------
Examples
--------
.. include:: ../../../includes/clustering/dbscan-examples.rst