<filename>src/python/turicreate/toolkits/clustering/dbscan.py
# -*- coding: utf-8 -*-
# Copyright © 2017 Apple Inc. All rights reserved.
#
# Use of this source code is governed by a BSD-3-clause license that can
# be found in the LICENSE.txt file or at https://opensource.org/licenses/BSD-3-Clause
"""
Class definition and create method for DBSCAN clustering.
"""
from __future__ import print_function as _
from __future__ import division as _
from __future__ import absolute_import as _

import time as _time
import logging as _logging
import turicreate as _tc
import turicreate.aggregate as _agg
from turicreate.toolkits._model import CustomModel as _CustomModel
import turicreate.toolkits._internal_utils as _tkutl
from turicreate.toolkits._internal_utils import _toolkit_repr_print
from turicreate.toolkits._private_utils import _summarize_accessible_fields
from turicreate.toolkits._model import PythonProxy as _PythonProxy


def create(dataset, features=None, distance=None, radius=1.,
           min_core_neighbors=10, verbose=True):
    """
    Create a DBSCAN clustering model. The DBSCAN method partitions the input
    dataset into three types of points, based on the estimated probability
    density at each point.

    - **Core** points have a large number of points within a given neighborhood.
      Specifically, `min_core_neighbors` must be within distance `radius` of a
      point for it to be considered a core point.

    - **Boundary** points are within distance `radius` of a core point, but
      don't have sufficient neighbors of their own to be considered core.

    - **Noise** points comprise the remainder of the data. These points have too
      few neighbors to be considered core points, and are further than distance
      `radius` from all core points.

    Clusters are formed by connecting core points that are neighbors of each
    other, then assigning boundary points to their nearest core neighbor's
    cluster.

    Parameters
    ----------
    dataset : SFrame
        Training data, with each row corresponding to an observation. Must
        include all features specified in the `features` parameter, but may have
        additional columns as well.

    features : list[str], optional
        Name of the columns with features to use in comparing records. 'None'
        (the default) indicates that all columns of the input `dataset` should
        be used to train the model. All features must be numeric, i.e. integer
        or float types.

    distance : str or list[list], optional
        Function to measure the distance between any two input data rows. This
        may be one of two types:

        - *String*: the name of a standard distance function. One of
          'euclidean', 'squared_euclidean', 'manhattan', 'levenshtein',
          'jaccard', 'weighted_jaccard', 'cosine', 'dot_product' (deprecated),
          or 'transformed_dot_product'.

        - *Composite distance*: the weighted sum of several standard distance
          functions applied to various features. This is specified as a list of
          distance components, each of which is itself a list containing three
          items:

          1. list or tuple of feature names (str)

          2. standard distance name (str)

          3. scaling factor (int or float)

        For more information about Turi Create distance functions, please
        see the :py:mod:`~turicreate.toolkits.distances` module.

        For sparse vectors, missing keys are assumed to have value 0.0.

        If 'distance' is left unspecified, a composite distance is constructed
        automatically based on feature types.

    radius : int or float, optional
        Size of each point's neighborhood, with respect to the specified
        distance function.

    min_core_neighbors : int, optional
        Number of neighbors that must be within distance `radius` of a point in
        order for that point to be considered a "core point" of a cluster.

    verbose : bool, optional
        If True, print progress updates and model details during model creation.

    Returns
    -------
    out : DBSCANModel
        A model containing a cluster label for each row in the input `dataset`.
        Also contains the indices of the core points, cluster boundary points,
        and noise points.

    See Also
    --------
    DBSCANModel, turicreate.toolkits.distances

    Notes
    -----
    - Our implementation of DBSCAN first computes the similarity graph on the
      input dataset, which can be a computationally intensive process. In the
      current implementation, some distances are substantially faster than
      others; in particular "euclidean", "squared_euclidean", "cosine", and
      "transformed_dot_product" are quite fast, while composite distances can be
      slow.

    - Any distance function in the Turi Create library may be used with DBSCAN but
      the results may be poor for distances that violate the standard metric
      properties, i.e. symmetry, non-negativity, triangle inequality, and
      identity of indiscernibles. In particular, the DBSCAN algorithm is based
      on the concept of connecting high-density points that are *close* to each
      other into a single cluster, but the notion of *close* may be very
      counterintuitive if the chosen distance function is not a valid metric.
      The distances "euclidean", "manhattan", "jaccard", and "levenshtein" will
      likely yield the best results.

    References
    ----------
    - <NAME>., et al. (1996) `A Density-Based Algorithm for Discovering
      Clusters in Large Spatial Databases with Noise
      <https://www.aaai.org/Papers/KDD/1996/KDD96-037.pdf>`_. In Proceedings of the
      Second International Conference on Knowledge Discovery and Data Mining.
      pp. 226-231.

    - `Wikipedia - DBSCAN <https://en.wikipedia.org/wiki/DBSCAN>`_

    - `Visualizing DBSCAN Clustering
      <http://www.naftaliharris.com/blog/visualizing-dbscan-clustering/>`_

    Examples
    --------
    >>> sf = turicreate.SFrame({
    ...     'x1': [0.6777, -9.391, 7.0385, 2.2657, 7.7864, -10.16, -8.162,
    ...            8.8817, -9.525, -9.153, 2.0860, 7.6619, 6.5511, 2.7020],
    ...     'x2': [5.6110, 8.5139, 5.3913, 5.4743, 8.3606, 7.8843, 2.7305,
    ...            5.1679, 6.7231, 3.7051, 1.7682, 7.4608, 3.1270, 6.5624]})
    ...
    >>> model = turicreate.dbscan.create(sf, radius=4.25, min_core_neighbors=3)
    >>> model.cluster_id.print_rows(15)
    +--------+------------+----------+
    | row_id | cluster_id |   type   |
    +--------+------------+----------+
    |   8    |     0      |   core   |
    |   7    |     2      |   core   |
    |   0    |     1      |   core   |
    |   2    |     2      |   core   |
    |   3    |     1      |   core   |
    |   11   |     2      |   core   |
    |   4    |     2      |   core   |
    |   1    |     0      | boundary |
    |   6    |     0      | boundary |
    |   5    |     0      | boundary |
    |   9    |     0      | boundary |
    |   12   |     2      | boundary |
    |   10   |     1      | boundary |
    |   13   |     1      | boundary |
    +--------+------------+----------+
    [14 rows x 3 columns]
    """
    import warnings
    
    ## Start the training time clock and instantiate an empty model
    logger = _logging.getLogger(__name__)
    start_time = _time.time()

    if distance == 'dot_product':
        warnings.warn("Using a \"dot_product\" distance is deprecated. This functionality will be removed in the next major release.")

    ## Validate the input dataset
    _tkutl._raise_error_if_not_sframe(dataset, "dataset")
    _tkutl._raise_error_if_sframe_empty(dataset, "dataset")


    ## Validate neighborhood parameters
    if not isinstance(min_core_neighbors, int) or min_core_neighbors < 0:
        raise ValueError("Input 'min_core_neighbors' must be a non-negative " +
                         "integer.")

    if not isinstance(radius, (int, float)) or radius < 0:
        raise ValueError("Input 'radius' must be a non-negative integer " +
                         "or float.")


    ## Compute all-point nearest neighbors within `radius` and count
    #  neighborhood sizes
    knn_model = _tc.nearest_neighbors.create(dataset, features=features,
                                             distance=distance,
                                             method='brute_force',
                                             verbose=verbose)

    knn = knn_model.similarity_graph(k=None, radius=radius,
                                     include_self_edges=False,
                                     output_type='SFrame',
                                     verbose=verbose)

    neighbor_counts = knn.groupby('query_label', _agg.COUNT)


    ### NOTE: points with NO neighbors are already dropped here!

    ## Identify core points and boundary candidate points. Not all of the
    #  boundary candidates will be boundary points - some are in small isolated
    #  clusters.
    if verbose:
        logger.info("Identifying noise points and core points.")

    boundary_mask = neighbor_counts['Count'] < min_core_neighbors
    core_mask = 1 - boundary_mask

    # this includes too small clusters
    boundary_idx = neighbor_counts[boundary_mask]['query_label']
    core_idx = neighbor_counts[core_mask]['query_label']


    ## Build a similarity graph on the core points
    ## NOTE: careful with singleton core points - the second filter removes them
    #  from the edge set so they have to be added separately as vertices.
    if verbose:
        logger.info("Constructing the core point similarity graph.")

    core_vertices = knn.filter_by(core_idx, 'query_label')
    core_edges = core_vertices.filter_by(core_idx, 'reference_label')

    core_graph = _tc.SGraph()
    core_graph = core_graph.add_vertices(core_vertices[['query_label']],
                                         vid_field='query_label')
    core_graph = core_graph.add_edges(core_edges, src_field='query_label',
                                      dst_field='reference_label')


    ## Compute core point connected components and relabel to be consecutive
    #  integers
    cc = _tc.connected_components.create(core_graph, verbose=verbose)
    cc_labels = cc.component_size.add_row_number('__label')
    core_assignments = cc.component_id.join(cc_labels, on='component_id',
                                               how='left')[['__id', '__label']]
    core_assignments['type'] = 'core'


    ## Join potential boundary points to core cluster labels (points that aren't
    #  really on a boundary are implicitly dropped)
    if verbose:
        logger.info("Processing boundary points.")

    boundary_edges = knn.filter_by(boundary_idx, 'query_label')

    # separate real boundary points from points in small isolated clusters
    boundary_core_edges = boundary_edges.filter_by(core_idx, 'reference_label')

    # join a boundary point to its single closest core point.
    boundary_assignments = boundary_core_edges.groupby('query_label',
                    {'reference_label': _agg.ARGMIN('rank', 'reference_label')})

    boundary_assignments = boundary_assignments.join(core_assignments,
                                                 on={'reference_label': '__id'})

    boundary_assignments = boundary_assignments.rename({'query_label': '__id'}, inplace=True)
    boundary_assignments = boundary_assignments.remove_column('reference_label', inplace=True)
    boundary_assignments['type'] = 'boundary'


    ## Identify boundary candidates that turned out to be in small clusters but
    #  not on real cluster boundaries
    small_cluster_idx = set(boundary_idx).difference(
                                                   boundary_assignments['__id'])


    ## Identify individual noise points by the fact that they have no neighbors.
    noise_idx = set(range(dataset.num_rows())).difference(
                                                 neighbor_counts['query_label'])

    noise_idx = noise_idx.union(small_cluster_idx)

    noise_assignments = _tc.SFrame({'row_id': _tc.SArray(list(noise_idx), int)})
    noise_assignments['cluster_id'] = None
    noise_assignments['cluster_id'] = noise_assignments['cluster_id'].astype(int)
    noise_assignments['type'] = 'noise'


    ## Append core, boundary, and noise results to each other.
    master_assignments = _tc.SFrame()
    num_clusters = 0

    if core_assignments.num_rows() > 0:
        core_assignments = core_assignments.rename({'__id': 'row_id',
                                                    '__label': 'cluster_id'}, inplace=True)
        master_assignments = master_assignments.append(core_assignments)
        num_clusters = len(core_assignments['cluster_id'].unique())

    if boundary_assignments.num_rows() > 0:
        boundary_assignments = boundary_assignments.rename({'__id': 'row_id',
                                                       '__label': 'cluster_id'}, inplace=True)
        master_assignments = master_assignments.append(boundary_assignments)

    if noise_assignments.num_rows() > 0:
        master_assignments = master_assignments.append(noise_assignments)


    ## Post-processing and formatting
    state = {'verbose': verbose,
             'radius': radius,
             'min_core_neighbors': min_core_neighbors,
             'distance': knn_model.distance,
             'num_distance_components': knn_model.num_distance_components,
             'num_examples': dataset.num_rows(),
             'features': knn_model.features,
             'num_features': knn_model.num_features,
             'unpacked_features': knn_model.unpacked_features,
             'num_unpacked_features': knn_model.num_unpacked_features,
             'cluster_id': master_assignments,
             'num_clusters': num_clusters,
             'training_time': _time.time() - start_time}

    return DBSCANModel(state)


class DBSCANModel(_CustomModel):
    """
    DBSCAN clustering model. The DBSCAN model contains the results of DBSCAN
    clustering, which finds clusters by identifying "core points" of high
    probability density and building clusters around them.

    This model should not be constructed directly. Instead, use
    :func:`turicreate.clustering.dbscan.create` to create an instance of this
    model.
    """
    _PYTHON_DBSCAN_MODEL_VERSION = 1

    def __init__(self, state):
        self.__proxy__ = _PythonProxy(state)

    @classmethod
    def _native_name(cls):
        return "dbscan"

    def _get_version(self):
        return self._PYTHON_DBSCAN_MODEL_VERSION

    def _get_native_state(self):
        return self.__proxy__.state

    @classmethod
    def _load_version(self, state, version):
        """
        A function to load a previously created DBSCANModel instance.

        Parameters
        ----------
        unpickler : GLUnpickler
            A GLUnpickler file handler.

        version : int
            Version number maintained by the class writer.
        """
        state = _PythonProxy(state)
        return DBSCANModel(state)

    def __str__(self):
        """
        Return a string description of the model to the ``print`` method.

        Returns
        -------
        out : str
            A description of the DBSCANModel.
        """
        return self.__repr__()

    def __repr__(self):
        """
        Print a string description of the model when the model name is entered
        in the terminal.
        """
        width = 40

        sections, section_titles = self._get_summary_struct()
        accessible_fields = {
            "cluster_id": "Cluster label for each row in the input dataset."}

        out = _toolkit_repr_print(self, sections, section_titles, width=width)
        out2 = _summarize_accessible_fields(accessible_fields, width=width)
        return out + "\n" + out2

    def _get_summary_struct(self):
        """
        Return a structured description of the model. This includes (where
        relevant) the schema of the training data, description of the training
        data, training statistics, and model hyperparameters.

        Returns
        -------
        sections : list (of list of tuples)
            A list of summary sections.
              Each section is a list.
                Each item in a section list is a tuple of the form:
                  ('<label>','<field>')
        section_titles: list
            A list of section titles.
              The order matches that of the 'sections' object.
        """
        model_fields = [
            ('Number of examples', 'num_examples'),
            ('Number of feature columns', 'num_features'),
            ('Max distance to a neighbor (radius)', 'radius'),
            ('Min number of neighbors for core points', 'min_core_neighbors'),
            ('Number of distance components', 'num_distance_components')]

        training_fields = [
            ('Total training time (seconds)', 'training_time'),
            ('Number of clusters', 'num_clusters')]

        section_titles = ["Schema", "Training summary"]
        return([model_fields, training_fields], section_titles)

<filename>src/python/turicreate/toolkits/clustering/dbscan.py
# -*- coding: utf-8 -*-
# Copyright © 2017 Apple Inc. All rights reserved.
#
# Use of this source code is governed by a BSD-3-clause license that can
# be found in the LICENSE.txt file or at https://opensource.org/licenses/BSD-3-Clause
"""
Class definition and create method for DBSCAN clustering.
"""
from __future__ import print_function as _
from __future__ import division as _
from __future__ import absolute_import as _

import time as _time
import logging as _logging
import turicreate as _tc
import turicreate.aggregate as _agg
from turicreate.toolkits._model import CustomModel as _CustomModel
import turicreate.toolkits._internal_utils as _tkutl
from turicreate.toolkits._internal_utils import _toolkit_repr_print
from turicreate.toolkits._private_utils import _summarize_accessible_fields
from turicreate.toolkits._model import PythonProxy as _PythonProxy


def create(dataset, features=None, distance=None, radius=1.,
           min_core_neighbors=10, verbose=True):
    """
    Create a DBSCAN clustering model. The DBSCAN method partitions the input
    dataset into three types of points, based on the estimated probability
    density at each point.

    - **Core** points have a large number of points within a given neighborhood.
      Specifically, `min_core_neighbors` must be within distance `radius` of a
      point for it to be considered a core point.

    - **Boundary** points are within distance `radius` of a core point, but
      don't have sufficient neighbors of their own to be considered core.

    - **Noise** points comprise the remainder of the data. These points have too
      few neighbors to be considered core points, and are further than distance
      `radius` from all core points.

    Clusters are formed by connecting core points that are neighbors of each
    other, then assigning boundary points to their nearest core neighbor's
    cluster.

    Parameters
    ----------
    dataset : SFrame
        Training data, with each row corresponding to an observation. Must
        include all features specified in the `features` parameter, but may have
        additional columns as well.

    features : list[str], optional
        Name of the columns with features to use in comparing records. 'None'
        (the default) indicates that all columns of the input `dataset` should
        be used to train the model. All features must be numeric, i.e. integer
        or float types.

    distance : str or list[list], optional
        Function to measure the distance between any two input data rows. This
        may be one of two types:

        - *String*: the name of a standard distance function. One of
          'euclidean', 'squared_euclidean', 'manhattan', 'levenshtein',
          'jaccard', 'weighted_jaccard', 'cosine', 'dot_product' (deprecated),
          or 'transformed_dot_product'.

        - *Composite distance*: the weighted sum of several standard distance
          functions applied to various features. This is specified as a list of
          distance components, each of which is itself a list containing three
          items:

          1. list or tuple of feature names (str)

          2. standard distance name (str)

          3. scaling factor (int or float)

        For more information about Turi Create distance functions, please
        see the :py:mod:`~turicreate.toolkits.distances` module.

        For sparse vectors, missing keys are assumed to have value 0.0.

        If 'distance' is left unspecified, a composite distance is constructed
        automatically based on feature types.

    radius : int or float, optional
        Size of each point's neighborhood, with respect to the specified
        distance function.

    min_core_neighbors : int, optional
        Number of neighbors that must be within distance `radius` of a point in
        order for that point to be considered a "core point" of a cluster.

    verbose : bool, optional
        If True, print progress updates and model details during model creation.

    Returns
    -------
    out : DBSCANModel
        A model containing a cluster label for each row in the input `dataset`.
        Also contains the indices of the core points, cluster boundary points,
        and noise points.

    See Also
    --------
    DBSCANModel, turicreate.toolkits.distances

    Notes
    -----
    - Our implementation of DBSCAN first computes the similarity graph on the
      input dataset, which can be a computationally intensive process. In the
      current implementation, some distances are substantially faster than
      others; in particular "euclidean", "squared_euclidean", "cosine", and
      "transformed_dot_product" are quite fast, while composite distances can be
      slow.

    - Any distance function in the Turi Create library may be used with DBSCAN but
      the results may be poor for distances that violate the standard metric
      properties, i.e. symmetry, non-negativity, triangle inequality, and
      identity of indiscernibles. In particular, the DBSCAN algorithm is based
      on the concept of connecting high-density points that are *close* to each
      other into a single cluster, but the notion of *close* may be very
      counterintuitive if the chosen distance function is not a valid metric.
      The distances "euclidean", "manhattan", "jaccard", and "levenshtein" will
      likely yield the best results.

    References
    ----------
    - <NAME>., et al. (1996) `A Density-Based Algorithm for Discovering
      Clusters in Large Spatial Databases with Noise
      <https://www.aaai.org/Papers/KDD/1996/KDD96-037.pdf>`_. In Proceedings of the
      Second International Conference on Knowledge Discovery and Data Mining.
      pp. 226-231.

    - `Wikipedia - DBSCAN <https://en.wikipedia.org/wiki/DBSCAN>`_

    - `Visualizing DBSCAN Clustering
      <http://www.naftaliharris.com/blog/visualizing-dbscan-clustering/>`_

    Examples
    --------
    >>> sf = turicreate.SFrame({
    ...     'x1': [0.6777, -9.391, 7.0385, 2.2657, 7.7864, -10.16, -8.162,
    ...            8.8817, -9.525, -9.153, 2.0860, 7.6619, 6.5511, 2.7020],
    ...     'x2': [5.6110, 8.5139, 5.3913, 5.4743, 8.3606, 7.8843, 2.7305,
    ...            5.1679, 6.7231, 3.7051, 1.7682, 7.4608, 3.1270, 6.5624]})
    ...
    >>> model = turicreate.dbscan.create(sf, radius=4.25, min_core_neighbors=3)
    >>> model.cluster_id.print_rows(15)
    +--------+------------+----------+
    | row_id | cluster_id |   type   |
    +--------+------------+----------+
    |   8    |     0      |   core   |
    |   7    |     2      |   core   |
    |   0    |     1      |   core   |
    |   2    |     2      |   core   |
    |   3    |     1      |   core   |
    |   11   |     2      |   core   |
    |   4    |     2      |   core   |
    |   1    |     0      | boundary |
    |   6    |     0      | boundary |
    |   5    |     0      | boundary |
    |   9    |     0      | boundary |
    |   12   |     2      | boundary |
    |   10   |     1      | boundary |
    |   13   |     1      | boundary |
    +--------+------------+----------+
    [14 rows x 3 columns]
    """
    import warnings
    
    ## Start the training time clock and instantiate an empty model
    logger = _logging.getLogger(__name__)
    start_time = _time.time()

    if distance == 'dot_product':
        warnings.warn("Using a \"dot_product\" distance is deprecated. This functionality will be removed in the next major release.")

    ## Validate the input dataset
    _tkutl._raise_error_if_not_sframe(dataset, "dataset")
    _tkutl._raise_error_if_sframe_empty(dataset, "dataset")


    ## Validate neighborhood parameters
    if not isinstance(min_core_neighbors, int) or min_core_neighbors < 0:
        raise ValueError("Input 'min_core_neighbors' must be a non-negative " +
                         "integer.")

    if not isinstance(radius, (int, float)) or radius < 0:
        raise ValueError("Input 'radius' must be a non-negative integer " +
                         "or float.")


    ## Compute all-point nearest neighbors within `radius` and count
    #  neighborhood sizes
    knn_model = _tc.nearest_neighbors.create(dataset, features=features,
                                             distance=distance,
                                             method='brute_force',
                                             verbose=verbose)

    knn = knn_model.similarity_graph(k=None, radius=radius,
                                     include_self_edges=False,
                                     output_type='SFrame',
                                     verbose=verbose)

    neighbor_counts = knn.groupby('query_label', _agg.COUNT)


    ### NOTE: points with NO neighbors are already dropped here!

    ## Identify core points and boundary candidate points. Not all of the
    #  boundary candidates will be boundary points - some are in small isolated
    #  clusters.
    if verbose:
        logger.info("Identifying noise points and core points.")

    boundary_mask = neighbor_counts['Count'] < min_core_neighbors
    core_mask = 1 - boundary_mask

    # this includes too small clusters
    boundary_idx = neighbor_counts[boundary_mask]['query_label']
    core_idx = neighbor_counts[core_mask]['query_label']


    ## Build a similarity graph on the core points
    ## NOTE: careful with singleton core points - the second filter removes them
    #  from the edge set so they have to be added separately as vertices.
    if verbose:
        logger.info("Constructing the core point similarity graph.")

    core_vertices = knn.filter_by(core_idx, 'query_label')
    core_edges = core_vertices.filter_by(core_idx, 'reference_label')

    core_graph = _tc.SGraph()
    core_graph = core_graph.add_vertices(core_vertices[['query_label']],
                                         vid_field='query_label')
    core_graph = core_graph.add_edges(core_edges, src_field='query_label',
                                      dst_field='reference_label')


    ## Compute core point connected components and relabel to be consecutive
    #  integers
    cc = _tc.connected_components.create(core_graph, verbose=verbose)
    cc_labels = cc.component_size.add_row_number('__label')
    core_assignments = cc.component_id.join(cc_labels, on='component_id',
                                               how='left')[['__id', '__label']]
    core_assignments['type'] = 'core'


    ## Join potential boundary points to core cluster labels (points that aren't
    #  really on a boundary are implicitly dropped)
    if verbose:
        logger.info("Processing boundary points.")

    boundary_edges = knn.filter_by(boundary_idx, 'query_label')

    # separate real boundary points from points in small isolated clusters
    boundary_core_edges = boundary_edges.filter_by(core_idx, 'reference_label')

    # join a boundary point to its single closest core point.
    boundary_assignments = boundary_core_edges.groupby('query_label',
                    {'reference_label': _agg.ARGMIN('rank', 'reference_label')})

    boundary_assignments = boundary_assignments.join(core_assignments,
                                                 on={'reference_label': '__id'})

    boundary_assignments = boundary_assignments.rename({'query_label': '__id'}, inplace=True)
    boundary_assignments = boundary_assignments.remove_column('reference_label', inplace=True)
    boundary_assignments['type'] = 'boundary'


    ## Identify boundary candidates that turned out to be in small clusters but
    #  not on real cluster boundaries
    small_cluster_idx = set(boundary_idx).difference(
                                                   boundary_assignments['__id'])


    ## Identify individual noise points by the fact that they have no neighbors.
    noise_idx = set(range(dataset.num_rows())).difference(
                                                 neighbor_counts['query_label'])

    noise_idx = noise_idx.union(small_cluster_idx)

    noise_assignments = _tc.SFrame({'row_id': _tc.SArray(list(noise_idx), int)})
    noise_assignments['cluster_id'] = None
    noise_assignments['cluster_id'] = noise_assignments['cluster_id'].astype(int)
    noise_assignments['type'] = 'noise'


    ## Append core, boundary, and noise results to each other.
    master_assignments = _tc.SFrame()
    num_clusters = 0

    if core_assignments.num_rows() > 0:
        core_assignments = core_assignments.rename({'__id': 'row_id',
                                                    '__label': 'cluster_id'}, inplace=True)
        master_assignments = master_assignments.append(core_assignments)
        num_clusters = len(core_assignments['cluster_id'].unique())

    if boundary_assignments.num_rows() > 0:
        boundary_assignments = boundary_assignments.rename({'__id': 'row_id',
                                                       '__label': 'cluster_id'}, inplace=True)
        master_assignments = master_assignments.append(boundary_assignments)

    if noise_assignments.num_rows() > 0:
        master_assignments = master_assignments.append(noise_assignments)


    ## Post-processing and formatting
    state = {'verbose': verbose,
             'radius': radius,
             'min_core_neighbors': min_core_neighbors,
             'distance': knn_model.distance,
             'num_distance_components': knn_model.num_distance_components,
             'num_examples': dataset.num_rows(),
             'features': knn_model.features,
             'num_features': knn_model.num_features,
             'unpacked_features': knn_model.unpacked_features,
             'num_unpacked_features': knn_model.num_unpacked_features,
             'cluster_id': master_assignments,
             'num_clusters': num_clusters,
             'training_time': _time.time() - start_time}

    return DBSCANModel(state)


class DBSCANModel(_CustomModel):
    """
    DBSCAN clustering model. The DBSCAN model contains the results of DBSCAN
    clustering, which finds clusters by identifying "core points" of high
    probability density and building clusters around them.

    This model should not be constructed directly. Instead, use
    :func:`turicreate.clustering.dbscan.create` to create an instance of this
    model.
    """
    _PYTHON_DBSCAN_MODEL_VERSION = 1

    def __init__(self, state):
        self.__proxy__ = _PythonProxy(state)

    @classmethod
    def _native_name(cls):
        return "dbscan"

    def _get_version(self):
        return self._PYTHON_DBSCAN_MODEL_VERSION

    def _get_native_state(self):
        return self.__proxy__.state

    @classmethod
    def _load_version(self, state, version):
        """
        A function to load a previously created DBSCANModel instance.

        Parameters
        ----------
        unpickler : GLUnpickler
            A GLUnpickler file handler.

        version : int
            Version number maintained by the class writer.
        """
        state = _PythonProxy(state)
        return DBSCANModel(state)

    def __str__(self):
        """
        Return a string description of the model to the ``print`` method.

        Returns
        -------
        out : str
            A description of the DBSCANModel.
        """
        return self.__repr__()

    def __repr__(self):
        """
        Print a string description of the model when the model name is entered
        in the terminal.
        """
        width = 40

        sections, section_titles = self._get_summary_struct()
        accessible_fields = {
            "cluster_id": "Cluster label for each row in the input dataset."}

        out = _toolkit_repr_print(self, sections, section_titles, width=width)
        out2 = _summarize_accessible_fields(accessible_fields, width=width)
        return out + "\n" + out2

    def _get_summary_struct(self):
        """
        Return a structured description of the model. This includes (where
        relevant) the schema of the training data, description of the training
        data, training statistics, and model hyperparameters.

        Returns
        -------
        sections : list (of list of tuples)
            A list of summary sections.
              Each section is a list.
                Each item in a section list is a tuple of the form:
                  ('<label>','<field>')
        section_titles: list
            A list of section titles.
              The order matches that of the 'sections' object.
        """
        model_fields = [
            ('Number of examples', 'num_examples'),
            ('Number of feature columns', 'num_features'),
            ('Max distance to a neighbor (radius)', 'radius'),
            ('Min number of neighbors for core points', 'min_core_neighbors'),
            ('Number of distance components', 'num_distance_components')]

        training_fields = [
            ('Total training time (seconds)', 'training_time'),
            ('Number of clusters', 'num_clusters')]

        section_titles = ["Schema", "Training summary"]
        return([model_fields, training_fields], section_titles)

# -*- coding: utf-8 -*- # Copyright © 2017 Apple Inc. All rights reserved. # # Use of this source code is governed by a BSD-3-clause license that can # be found in the LICENSE.txt file or at https://opensource.org/licenses/BSD-3-Clause Class definition and create method for DBSCAN clustering. Create a DBSCAN clustering model. The DBSCAN method partitions the input     dataset into three types of points, based on the estimated probability     density at each point.      - **Core** points have a large number of points within a given neighborhood.       Specifically, `min_core_neighbors` must be within distance `radius` of a       point for it to be considered a core point.      - **Boundary** points are within distance `radius` of a core point, but       don't have sufficient neighbors of their own to be considered core.      - **Noise** points comprise the remainder of the data. These points have too       few neighbors to be considered core points, and are further than distance       `radius` from all core points.      Clusters are formed by connecting core points that are neighbors of each     other, then assigning boundary points to their nearest core neighbor's     cluster.      Parameters     ----------     dataset : SFrame         Training data, with each row corresponding to an observation. Must         include all features specified in the `features` parameter, but may have         additional columns as well.      features : list[str], optional         Name of the columns with features to use in comparing records. 'None'         (the default) indicates that all columns of the input `dataset` should         be used to train the model. All features must be numeric, i.e. integer         or float types.      distance : str or list[list], optional         Function to measure the distance between any two input data rows. This         may be one of two types:          - *String*: the name of a standard distance function. One of           'euclidean', 'squared_euclidean', 'manhattan', 'levenshtein',           'jaccard', 'weighted_jaccard', 'cosine', 'dot_product' (deprecated),           or 'transformed_dot_product'.          - *Composite distance*: the weighted sum of several standard distance           functions applied to various features. This is specified as a list of           distance components, each of which is itself a list containing three           items:            1. list or tuple of feature names (str)            2. standard distance name (str)            3. scaling factor (int or float)          For more information about Turi Create distance functions, please         see the :py:mod:`~turicreate.toolkits.distances` module.          For sparse vectors, missing keys are assumed to have value 0.0.          If 'distance' is left unspecified, a composite distance is constructed         automatically based on feature types.      radius : int or float, optional         Size of each point's neighborhood, with respect to the specified         distance function.      min_core_neighbors : int, optional         Number of neighbors that must be within distance `radius` of a point in         order for that point to be considered a "core point" of a cluster.      verbose : bool, optional         If True, print progress updates and model details during model creation.      Returns     -------     out : DBSCANModel         A model containing a cluster label for each row in the input `dataset`.         Also contains the indices of the core points, cluster boundary points,         and noise points.      See Also     --------     DBSCANModel, turicreate.toolkits.distances      Notes     -----     - Our implementation of DBSCAN first computes the similarity graph on the       input dataset, which can be a computationally intensive process. In the       current implementation, some distances are substantially faster than       others; in particular "euclidean", "squared_euclidean", "cosine", and       "transformed_dot_product" are quite fast, while composite distances can be       slow.      - Any distance function in the Turi Create library may be used with DBSCAN but       the results may be poor for distances that violate the standard metric       properties, i.e. symmetry, non-negativity, triangle inequality, and       identity of indiscernibles. In particular, the DBSCAN algorithm is based       on the concept of connecting high-density points that are *close* to each       other into a single cluster, but the notion of *close* may be very       counterintuitive if the chosen distance function is not a valid metric.       The distances "euclidean", "manhattan", "jaccard", and "levenshtein" will       likely yield the best results.      References     ----------     - <NAME>., et al. (1996) `A Density-Based Algorithm for Discovering       Clusters in Large Spatial Databases with Noise       <https://www.aaai.org/Papers/KDD/1996/KDD96-037.pdf>`_. In Proceedings of the       Second International Conference on Knowledge Discovery and Data Mining.       pp. 226-231.      - `Wikipedia - DBSCAN <https://en.wikipedia.org/wiki/DBSCAN>`_      - `Visualizing DBSCAN Clustering       <http://www.naftaliharris.com/blog/visualizing-dbscan-clustering/>`_      Examples     --------     >>> sf = turicreate.SFrame({     ...     'x1': [0.6777, -9.391, 7.0385, 2.2657, 7.7864, -10.16, -8.162,     ...            8.8817, -9.525, -9.153, 2.0860, 7.6619, 6.5511, 2.7020],     ...     'x2': [5.6110, 8.5139, 5.3913, 5.4743, 8.3606, 7.8843, 2.7305,     ...            5.1679, 6.7231, 3.7051, 1.7682, 7.4608, 3.1270, 6.5624]})     ...     >>> model = turicreate.dbscan.create(sf, radius=4.25, min_core_neighbors=3)     >>> model.cluster_id.print_rows(15)     +--------+------------+----------+     | row_id | cluster_id |   type   |     +--------+------------+----------+     |   8    |     0      |   core   |     |   7    |     2      |   core   |     |   0    |     1      |   core   |     |   2    |     2      |   core   |     |   3    |     1      |   core   |     |   11   |     2      |   core   |     |   4    |     2      |   core   |     |   1    |     0      | boundary |     |   6    |     0      | boundary |     |   5    |     0      | boundary |     |   9    |     0      | boundary |     |   12   |     2      | boundary |     |   10   |     1      | boundary |     |   13   |     1      | boundary |     +--------+------------+----------+     [14 rows x 3 columns] ## Start the training time clock and instantiate an empty model ## Validate the input dataset ## Validate neighborhood parameters ## Compute all-point nearest neighbors within `radius` and count #  neighborhood sizes ### NOTE: points with NO neighbors are already dropped here! ## Identify core points and boundary candidate points. Not all of the #  boundary candidates will be boundary points - some are in small isolated #  clusters. # this includes too small clusters ## Build a similarity graph on the core points ## NOTE: careful with singleton core points - the second filter removes them #  from the edge set so they have to be added separately as vertices. ## Compute core point connected components and relabel to be consecutive #  integers ## Join potential boundary points to core cluster labels (points that aren't #  really on a boundary are implicitly dropped) # separate real boundary points from points in small isolated clusters # join a boundary point to its single closest core point. ## Identify boundary candidates that turned out to be in small clusters but #  not on real cluster boundaries ## Identify individual noise points by the fact that they have no neighbors. ## Append core, boundary, and noise results to each other. ## Post-processing and formatting DBSCAN clustering model. The DBSCAN model contains the results of DBSCAN     clustering, which finds clusters by identifying "core points" of high     probability density and building clusters around them.      This model should not be constructed directly. Instead, use     :func:`turicreate.clustering.dbscan.create` to create an instance of this     model. A function to load a previously created DBSCANModel instance.          Parameters         ----------         unpickler : GLUnpickler             A GLUnpickler file handler.          version : int             Version number maintained by the class writer. Return a string description of the model to the ``print`` method.          Returns         -------         out : str             A description of the DBSCANModel. Print a string description of the model when the model name is entered         in the terminal. Return a structured description of the model. This includes (where         relevant) the schema of the training data, description of the training         data, training statistics, and model hyperparameters.          Returns         -------         sections : list (of list of tuples)             A list of summary sections.               Each section is a list.                 Each item in a section list is a tuple of the form:                   ('<label>','<field>')         section_titles: list             A list of section titles.               The order matches that of the 'sections' object.