{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "\n# Demo of HDBSCAN clustering algorithm\n.. currentmodule:: sklearn\n\nIn this demo we will take a look at :class:`cluster.HDBSCAN` from the\nperspective of generalizing the :class:`cluster.DBSCAN` algorithm.\nWe'll compare both algorithms on specific datasets. Finally we'll evaluate\nHDBSCAN's sensitivity to certain hyperparameters.\n\nWe first define a couple utility functions for convenience.\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "# Authors: The scikit-learn developers\n# SPDX-License-Identifier: BSD-3-Clause" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "import matplotlib.pyplot as plt\nimport numpy as np\n\nfrom sklearn.cluster import DBSCAN, HDBSCAN\nfrom sklearn.datasets import make_blobs\n\n\ndef plot(X, labels, probabilities=None, parameters=None, ground_truth=False, ax=None):\n if ax is None:\n _, ax = plt.subplots(figsize=(10, 4))\n labels = labels if labels is not None else np.ones(X.shape[0])\n probabilities = probabilities if probabilities is not None else np.ones(X.shape[0])\n # Black removed and is used for noise instead.\n unique_labels = set(labels)\n colors = [plt.cm.Spectral(each) for each in np.linspace(0, 1, len(unique_labels))]\n # The probability of a point belonging to its labeled cluster determines\n # the size of its marker\n proba_map = {idx: probabilities[idx] for idx in range(len(labels))}\n for k, col in zip(unique_labels, colors):\n if k == -1:\n # Black used for noise.\n col = [0, 0, 0, 1]\n\n class_index = np.where(labels == k)[0]\n for ci in class_index:\n ax.plot(\n X[ci, 0],\n X[ci, 1],\n \"x\" if k == -1 else \"o\",\n markerfacecolor=tuple(col),\n markeredgecolor=\"k\",\n markersize=4 if k == -1 else 1 + 5 * proba_map[ci],\n )\n n_clusters_ = len(set(labels)) - (1 if -1 in labels else 0)\n preamble = \"True\" if ground_truth else \"Estimated\"\n title = f\"{preamble} number of clusters: {n_clusters_}\"\n if parameters is not None:\n parameters_str = \", \".join(f\"{k}={v}\" for k, v in parameters.items())\n title += f\" | {parameters_str}\"\n ax.set_title(title)\n plt.tight_layout()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Generate sample data\nOne of the greatest advantages of HDBSCAN over DBSCAN is its out-of-the-box\nrobustness. It's especially remarkable on heterogeneous mixtures of data.\nLike DBSCAN, it can model arbitrary shapes and distributions, however unlike\nDBSCAN it does not require specification of an arbitrary and sensitive\n`eps` hyperparameter.\n\nFor example, below we generate a dataset from a mixture of three bi-dimensional\nand isotropic Gaussian distributions.\n\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "centers = [[1, 1], [-1, -1], [1.5, -1.5]]\nX, labels_true = make_blobs(\n n_samples=750, centers=centers, cluster_std=[0.4, 0.1, 0.75], random_state=0\n)\nplot(X, labels=labels_true, ground_truth=True)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Scale Invariance\nIt's worth remembering that, while DBSCAN provides a default value for `eps`\nparameter, it hardly has a proper default value and must be tuned for the\nspecific dataset at use.\n\nAs a simple demonstration, consider the clustering for a `eps` value tuned\nfor one dataset, and clustering obtained with the same value but applied to\nrescaled versions of the dataset.\n\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "fig, axes = plt.subplots(3, 1, figsize=(10, 12))\ndbs = DBSCAN(eps=0.3)\nfor idx, scale in enumerate([1, 0.5, 3]):\n dbs.fit(X * scale)\n plot(X * scale, dbs.labels_, parameters={\"scale\": scale, \"eps\": 0.3}, ax=axes[idx])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Indeed, in order to maintain the same results we would have to scale `eps` by\nthe same factor.\n\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "fig, axis = plt.subplots(1, 1, figsize=(12, 5))\ndbs = DBSCAN(eps=0.9).fit(3 * X)\nplot(3 * X, dbs.labels_, parameters={\"scale\": 3, \"eps\": 0.9}, ax=axis)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "While standardizing data (e.g. using\n:class:`sklearn.preprocessing.StandardScaler`) helps mitigate this problem,\ngreat care must be taken to select the appropriate value for `eps`.\n\nHDBSCAN is much more robust in this sense: HDBSCAN can be seen as\nclustering over all possible values of `eps` and extracting the best\nclusters from all possible clusters (see `User Guide `).\nOne immediate advantage is that HDBSCAN is scale-invariant.\n\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "fig, axes = plt.subplots(3, 1, figsize=(10, 12))\nhdb = HDBSCAN()\nfor idx, scale in enumerate([1, 0.5, 3]):\n hdb.fit(X * scale)\n plot(\n X * scale,\n hdb.labels_,\n hdb.probabilities_,\n ax=axes[idx],\n parameters={\"scale\": scale},\n )" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Multi-Scale Clustering\nHDBSCAN is much more than scale invariant though -- it is capable of\nmulti-scale clustering, which accounts for clusters with varying density.\nTraditional DBSCAN assumes that any potential clusters are homogeneous in\ndensity. HDBSCAN is free from such constraints. To demonstrate this we\nconsider the following dataset\n\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "centers = [[-0.85, -0.85], [-0.85, 0.85], [3, 3], [3, -3]]\nX, labels_true = make_blobs(\n n_samples=750, centers=centers, cluster_std=[0.2, 0.35, 1.35, 1.35], random_state=0\n)\nplot(X, labels=labels_true, ground_truth=True)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "This dataset is more difficult for DBSCAN due to the varying densities and\nspatial separation:\n\n- If `eps` is too large then we risk falsely clustering the two dense\n clusters as one since their mutual reachability will extend\n clusters.\n- If `eps` is too small, then we risk fragmenting the sparser clusters\n into many false clusters.\n\nNot to mention this requires manually tuning choices of `eps` until we\nfind a tradeoff that we are comfortable with.\n\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "fig, axes = plt.subplots(2, 1, figsize=(10, 8))\nparams = {\"eps\": 0.7}\ndbs = DBSCAN(**params).fit(X)\nplot(X, dbs.labels_, parameters=params, ax=axes[0])\nparams = {\"eps\": 0.3}\ndbs = DBSCAN(**params).fit(X)\nplot(X, dbs.labels_, parameters=params, ax=axes[1])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "To properly cluster the two dense clusters, we would need a smaller value of\nepsilon, however at `eps=0.3` we are already fragmenting the sparse clusters,\nwhich would only become more severe as we decrease epsilon. Indeed it seems\nthat DBSCAN is incapable of simultaneously separating the two dense clusters\nwhile preventing the sparse clusters from fragmenting. Let's compare with\nHDBSCAN.\n\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "hdb = HDBSCAN().fit(X)\nplot(X, hdb.labels_, hdb.probabilities_)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "HDBSCAN is able to adapt to the multi-scale structure of the dataset without\nrequiring parameter tuning. While any sufficiently interesting dataset will\nrequire tuning, this case demonstrates that HDBSCAN can yield qualitatively\nbetter classes of clusterings without users' intervention which are\ninaccessible via DBSCAN.\n\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Hyperparameter Robustness\nUltimately tuning will be an important step in any real world application, so\nlet's take a look at some of the most important hyperparameters for HDBSCAN.\nWhile HDBSCAN is free from the `eps` parameter of DBSCAN, it does still have\nsome hyperparameters like `min_cluster_size` and `min_samples` which tune its\nresults regarding density. We will however see that HDBSCAN is relatively robust\nto various real world examples thanks to those parameters whose clear meaning\nhelps tuning them.\n\n### `min_cluster_size`\n`min_cluster_size` is the minimum number of samples in a group for that\ngroup to be considered a cluster.\n\nClusters smaller than the ones of this size will be left as noise.\nThe default value is 5. This parameter is generally tuned to\nlarger values as needed. Smaller values will likely to lead to results with\nfewer points labeled as noise. However values which too small will lead to\nfalse sub-clusters being picked up and preferred. Larger values tend to be\nmore robust with respect to noisy datasets, e.g. high-variance clusters with\nsignificant overlap.\n\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "PARAM = ({\"min_cluster_size\": 5}, {\"min_cluster_size\": 3}, {\"min_cluster_size\": 25})\nfig, axes = plt.subplots(3, 1, figsize=(10, 12))\nfor i, param in enumerate(PARAM):\n hdb = HDBSCAN(**param).fit(X)\n labels = hdb.labels_\n\n plot(X, labels, hdb.probabilities_, param, ax=axes[i])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### `min_samples`\n`min_samples` is the number of samples in a neighborhood for a point to\nbe considered as a core point, including the point itself.\n`min_samples` defaults to `min_cluster_size`.\nSimilarly to `min_cluster_size`, larger values for `min_samples` increase\nthe model's robustness to noise, but risks ignoring or discarding\npotentially valid but small clusters.\n`min_samples` better be tuned after finding a good value for `min_cluster_size`.\n\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "PARAM = (\n {\"min_cluster_size\": 20, \"min_samples\": 5},\n {\"min_cluster_size\": 20, \"min_samples\": 3},\n {\"min_cluster_size\": 20, \"min_samples\": 25},\n)\nfig, axes = plt.subplots(3, 1, figsize=(10, 12))\nfor i, param in enumerate(PARAM):\n hdb = HDBSCAN(**param).fit(X)\n labels = hdb.labels_\n\n plot(X, labels, hdb.probabilities_, param, ax=axes[i])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### `dbscan_clustering`\nDuring `fit`, `HDBSCAN` builds a single-linkage tree which encodes the\nclustering of all points across all values of :class:`~cluster.DBSCAN`'s\n`eps` parameter.\nWe can thus plot and evaluate these clusterings efficiently without fully\nrecomputing intermediate values such as core-distances, mutual-reachability,\nand the minimum spanning tree. All we need to do is specify the `cut_distance`\n(equivalent to `eps`) we want to cluster with.\n\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "PARAM = (\n {\"cut_distance\": 0.1},\n {\"cut_distance\": 0.5},\n {\"cut_distance\": 1.0},\n)\nhdb = HDBSCAN()\nhdb.fit(X)\nfig, axes = plt.subplots(len(PARAM), 1, figsize=(10, 12))\nfor i, param in enumerate(PARAM):\n labels = hdb.dbscan_clustering(**param)\n\n plot(X, labels, hdb.probabilities_, param, ax=axes[i])" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.9.21" } }, "nbformat": 4, "nbformat_minor": 0 }