| /* ----------------------------------------------------------------------- */ |
| /** |
| * Licensed to the Apache Software Foundation (ASF) under one |
| * or more contributor license agreements. See the NOTICE file |
| * distributed with this work for additional information |
| * regarding copyright ownership. The ASF licenses this file |
| * to you 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. |
| * |
| * @file dbscan.sql_in |
| * @brief Partitions a set of observations into clusters of arbitrary shape based on the density of nearby neighbors. |
| * @date May 2020 |
| * |
| */ |
| /* ----------------------------------------------------------------------- */ |
| |
| |
| /** |
| @addtogroup grp_dbscan |
| |
| <div class="toc"><b>Contents</b> |
| <ul> |
| <li class="level1"><a href="#cluster">Clustering Function</a></li> |
| <li class="level1"><a href="#assignment">Cluster Assignment</a></li> |
| <li class="level1"><a href="#examples">Examples</a></li> |
| <li class="level1"><a href="#literature">Literature</a></li> |
| <li class="level1"><a href="#related">Related Topics</a></li> |
| </ul> |
| </div> |
| |
| @brief Partitions a set of observations into clusters of arbitrary |
| shape based on the density of nearby neighbors. |
| |
| Density-based spatial clustering of applications with noise (DBSCAN) |
| is a data clustering algorithm designed to discover clusters of arbitrary |
| shape [1]. It places minimum requirements on domain knowledge to determine |
| input parameters and has good efficiency on large databases. |
| |
| Given a set of points, DBSCAN groups together points that are closely packed with many |
| nearby neighbors (\em core), and marks points that lie alone in |
| low-density regions with few nearby neighbors (\em border). Other points in the dataset |
| that are not core or border are considered as \em noise. |
| This method tends to be good for data which contains clusters |
| of similar density. |
| |
| @anchor cluster |
| @par Clustering Function |
| |
| <pre class="syntax"> |
| dbscan( source_table, |
| output_table, |
| id_column, |
| expr_point, |
| eps, |
| min_samples, |
| metric, |
| algorithm, |
| algorithm_params |
| ) |
| </pre> |
| |
| \b Arguments |
| <dl class="arglist"> |
| <dt>source_table</dt> |
| <dd>TEXT. Name of the table containing the input data points. |
| </dd> |
| |
| <dt>output_table</dt> |
| <dd>TEXT. Name of the table containing the clustering results. |
| </dd> |
| |
| <dt>id_column</dt> |
| <dd>TEXT. Name of the column containing a unique integer id for each training point. |
| </dd> |
| |
| <dt>expr_point</dt> |
| <dd>TEXT. Name of the column with point coordinates in array form, |
| or an expression that evaluates to an array of point coordinates. |
| </dd> |
| |
| <dt>eps</dt> |
| <dd>FLOAT8. Maximum distance between two samples for one to |
| be considered in the neighborhood of the other. (Note this is not a maximum |
| bound on the distances of points within a cluster.) This is an |
| important parameter to choose appropriately and should consider both the |
| nature of the data set and the distance function. |
| </dd> |
| |
| <dt>min_samples (optional)</dt> |
| <dd>INTEGER, default: 5. Number of samples in a neighborhood for a point |
| to be considered as a core point. This includes the point itself. |
| This parameter controls how tolerant the algorithm is towards |
| noise, so on noisy data sets it may be useful to increase |
| the magnitude of this parameter. |
| </dd> |
| |
| @note |
| The parameters 'eps' and 'min_samples' together define the density of a cluster. |
| A core point is where there exist 'min_samples' other points within a distance of 'eps', |
| which are defined as neighbors of the core point. |
| A higher value of 'min_samples' or a lower value of 'eps' indicate that higher density |
| is needed to form a cluster. |
| |
| <dt>metric (optional)</dt> |
| <dd>TEXT, default: 'squared_dist_norm2'. The name of the function used |
| to calculate the distance between data points. The following distance |
| functions can be used: |
| <ul> |
| <li><b>\ref dist_norm1</b>: 1-norm/Manhattan (element-wise median). |
| MADlib does not provide a median aggregate function for |
| performance reasons.</li> |
| <li><b>\ref dist_norm2</b>: 2-norm/Euclidean (element-wise mean)</li> |
| <li><b>\ref squared_dist_norm2</b>: squared Euclidean distance (element-wise mean)</li> |
| <li><b>\ref dist_angle</b>: angle (element-wise mean of normalized points)</li> |
| <li><b>\ref dist_tanimoto</b>: tanimoto (element-wise mean of normalized points)</li> |
| </dd> |
| |
| <dt>algorithm TBD??? (optional)</dt> |
| <dd>TEXT, default: 'brute_force'. The name of the algorithm |
| used to compute clusters. The following options are supported: |
| <ul> |
| <li><b>\ref brute_force</b>: Produces an exact result by searching |
| all points in the search space. Brute force can be slow and is intended |
| to be used for small datasets only. You can also use a short |
| form "b" or "brute" etc. to select brute force.</li> |
| <li><b>\ref kd_tree</b>: Uses a tree structure to reduce the amount |
| of search required to form clusters |
| The depth of the kd-tree to search is specified |
| by the "algorithm_params" below. |
| You can also use a short |
| form "k" or "kd" etc. to select kd-tree.</li></ul></dd> |
| |
| <dt>algorithm_params (optional)</dt> |
| <dd>TEXT, default: 'depth=3'. This parameters apply to the |
| kd-tree algorithm only. Increasing the depth of the tree will |
| decrease the run-time but reduce the accuracy. TBD???</dd> |
| |
| </dl> |
| |
| <b>Output</b> |
| <br> |
| The output table for DBSCAN module has the following columns: |
| <table class="output"> |
| <tr> |
| <th>id_in</th> |
| <td>INTEGER. Test data point id.</td> |
| </tr> |
| <tr> |
| <th>cluster_id</th> |
| <td>INTEGER. Cluster id associated with the test data point.</td> |
| </tr> |
| <tr> |
| <th>is_core_point</th> |
| <td>BOOLEAN. Indicates if the test data point is core |
| If it is not a core point and listed in the output table, |
| it is a border point. Noise points are not shown in this |
| table.</td> |
| </tr> |
| <tr> |
| <th>points</th> |
| <td>TEXT. Column or expression for the data point.</td> |
| </tr> |
| </table> |
| |
| @anchor assignment |
| @par Cluster Assignment |
| |
| After clustering, the cluster assignment for each data point can be computed: |
| |
| <pre class="syntax"> |
| dbscan_predict( dbscan_table, |
| source_table, |
| id_column, |
| expr_point, |
| output_table |
| ) |
| </pre> |
| |
| <b>Arguments</b> |
| <dl class="arglist"> |
| |
| <dt>dbscan_table</dt> |
| <dd>TEXT. Name of the table created by running DBSCAN.</dd> |
| |
| <dt>source_table</dt> |
| <dd>TEXT. Name of the table containing the input data points. |
| </dd> |
| |
| |
| <dt>id_column</dt> |
| <dd>TEXT. Name of the column containing a unique integer id for each training point. |
| </dd> |
| |
| <dt>expr_point</dt> |
| <dd>TEXT. Name of the column with point coordinates in array form, |
| or an expression that evaluates to an array of point coordinates. |
| </dd> |
| |
| <dt>output_table</dt> |
| <dd>TEXT. Name of the table containing the clustering results. |
| </dd> |
| |
| <b>Output TBD</b> |
| <br> |
| The output is a table with the following columns: |
| <table class="output"> |
| <tr> |
| <th>id_column</th> |
| <td>INTEGER. ID column passed to the function.</td> |
| </tr> |
| <tr> |
| <th>cluster_id</th> |
| <td>INTEGER. Cluster assignment (zero-based, i.e., 0,1,2...).</td> |
| </tr> |
| <tr> |
| <th>distance</th> |
| <td>DOUBLE PRECISION. Distance to the cluster centroid.</td> |
| </tr> |
| </table> |
| |
| @anchor examples |
| @par Examples |
| |
| -# Create input data: |
| <pre class="example"> |
| DROP TABLE IF EXISTS dbscan_train_data; |
| CREATE TABLE dbscan_train_data (pid int, points double precision[]); |
| INSERT INTO dbscan_train_data VALUES |
| (1, '{1, 1}'), |
| (2, '{2, 1}'), |
| (3, '{1, 2}'), |
| (4, '{2, 2}'), |
| (5, '{3, 5}'), |
| (6, '{3, 9}'), |
| (7, '{3, 10}'), |
| (8, '{4, 10}'), |
| (9, '{4, 11}'), |
| (10, '{5, 10}'), |
| (11, '{7, 10}'), |
| (12, '{10, 9}'), |
| (13, '{10, 6}'), |
| (14, '{9, 5}'), |
| (15, '{10, 5}'), |
| (16, '{11, 5}'), |
| (17, '{9, 4}'), |
| (18, '{10, 4}'), |
| (19, '{11, 4}'), |
| (20, '{10, 3}'); |
| CREATE TABLE dbscan_test_data (pid int, points double precision[]); |
| INSERT INTO dbscan_test_data VALUES |
| (1, '{1, 2}'), |
| (2, '{2, 2}'), |
| (3, '{1, 3}'), |
| (4, '{2, 2}'), |
| (10, '{5, 11}'), |
| (11, '{7, 10}'), |
| (12, '{10, 9}'), |
| (13, '{10, 6}'), |
| (14, '{9, 5}'), |
| (15, '{10, 6}'); |
| </pre> |
| -# Run DBSCAN using the brute force method with a Euclidean |
| distance function: |
| <pre class="example"> |
| DROP TABLE IF EXISTS dbscan_result, dbscan_result_summary; |
| SELECT madlib.dbscan( |
| 'dbscan_train_data', -- source table |
| 'dbscan_result', -- output table |
| 'pid', -- point id column |
| 'points', -- data point |
| 1.75, -- epsilon |
| 4, -- min samples |
| 'dist_norm2', -- metric |
| 'brute_force'); -- algorithm |
| SELECT * FROM dbscan_result ORDER BY pid; |
| </pre> |
| <pre class="result"> |
| pid | cluster_id | is_core_point | __points__ |
| -----+------------+---------------+------------ |
| 1 | 0 | t | {1,1} |
| 2 | 0 | t | {2,1} |
| 3 | 0 | t | {1,2} |
| 4 | 0 | t | {2,2} |
| 6 | 1 | f | {3,9} |
| 7 | 1 | t | {3,10} |
| 8 | 1 | t | {4,10} |
| 9 | 1 | t | {4,11} |
| 10 | 1 | f | {5,10} |
| 13 | 2 | t | {10,6} |
| 14 | 2 | t | {9,5} |
| 15 | 2 | t | {10,5} |
| 16 | 2 | t | {11,5} |
| 17 | 2 | t | {9,4} |
| 18 | 2 | t | {10,4} |
| 19 | 2 | t | {11,4} |
| 20 | 2 | t | {10,3} |
| (17 rows) |
| </pre> |
| There are three clusters created. All points are core points |
| except for 6 and 10 which are border points. The noise points |
| do not show up in the output table. If you want to see the noise points |
| you can use a query like: |
| <pre class="example"> |
| SELECT l.* FROM dbscan_train_data l WHERE NOT EXISTS |
| (SELECT NULL FROM dbscan_result r WHERE r.pid = l.pid) |
| ORDER BY l.pid; |
| </pre> |
| <pre class="result"> |
| pid | points |
| -----+-------- |
| 5 | {3,5} |
| 11 | {7,10} |
| 12 | {10,9} |
| </pre> |
| The summary table lists the 'eps' value and the distance metric used: |
| <pre class="example"> |
| SELECT * FROM dbscan_result_summary; |
| </pre> |
| <pre class="result"> |
| id_column | eps | metric |
| -----------+------+------------ |
| pid | 1.75 | dist_norm2 |
| </pre> |
| -# Find the cluster assignment. In this example we use the same source |
| points for demonstration purposes: |
| <pre class="example"> |
| |
| SELECT madlib.dbscan_predict( |
| 'dbscan_result', -- from DBSCAN run |
| 'dbscan_test_data', -- test dataset |
| 'pid', -- point id column |
| 'points', -- data point |
| 'dbscan_predict_out' -- output table |
| ); |
| |
| </pre> |
| <pre class="result"> |
| TBD??? |
| </pre> |
| -# Now let's run DBSCAN using the kd-tree method with a Euclidean |
| distance function: |
| <pre class="example"> |
| DROP TABLE IF EXISTS dbscan_result_kd, dbscan_result_kd_summary; |
| SELECT madlib.dbscan( |
| 'dbscan_train_data', -- source table |
| 'dbscan_result_kd', -- output table |
| 'pid', -- point id column |
| 'points', -- data point |
| 1.75, -- epsilon |
| 4, -- min samples |
| 'dist_norm2', -- metric |
| 'kd_tree', -- algorithm |
| 'depth=3'); -- depth of kd-tree |
| SELECT * FROM dbscan_result_kd ORDER BY pid; |
| </pre> |
| <pre class="result"> |
| TBD??? |
| </pre> |
| |
| @anchor literature |
| @literature |
| |
| @anchor related |
| @par Related Topics |
| |
| */ |
| |
| |
| m4_include(`SQLCommon.m4') |
| |
| CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.dbscan( |
| source_table VARCHAR, |
| output_table VARCHAR, |
| id_column VARCHAR, |
| expr_point VARCHAR, |
| eps DOUBLE PRECISION, |
| min_samples INTEGER, |
| metric VARCHAR, |
| algorithm VARCHAR |
| ) RETURNS VOID AS $$ |
| PythonFunction(dbscan, dbscan, dbscan) |
| $$ LANGUAGE plpythonu VOLATILE |
| m4_ifdef(`\_\_HAS_FUNCTION_PROPERTIES\_\_', `MODIFIES SQL DATA', `'); |
| |
| CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.dbscan( |
| source_table VARCHAR, |
| output_table VARCHAR, |
| id_column VARCHAR, |
| expr_point VARCHAR, |
| eps DOUBLE PRECISION, |
| min_samples INTEGER, |
| metric VARCHAR |
| ) RETURNS VOID AS $$ |
| SELECT MADLIB_SCHEMA.dbscan($1, $2, $3, $4, $5, $6, $7, NULL); |
| $$ LANGUAGE sql VOLATILE |
| m4_ifdef(`\_\_HAS_FUNCTION_PROPERTIES\_\_', `MODIFIES SQL DATA', `'); |
| |
| CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.dbscan( |
| source_table VARCHAR, |
| output_table VARCHAR, |
| id_column VARCHAR, |
| expr_point VARCHAR, |
| eps DOUBLE PRECISION, |
| min_samples INTEGER |
| ) RETURNS VOID AS $$ |
| SELECT MADLIB_SCHEMA.dbscan($1, $2, $3, $4, $5, $6, NULL, NULL); |
| $$ LANGUAGE sql VOLATILE |
| m4_ifdef(`\_\_HAS_FUNCTION_PROPERTIES\_\_', `MODIFIES SQL DATA', `'); |
| |
| CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.dbscan( |
| source_table VARCHAR, |
| output_table VARCHAR, |
| id_column VARCHAR, |
| expr_point VARCHAR, |
| eps DOUBLE PRECISION |
| ) RETURNS VOID AS $$ |
| SELECT MADLIB_SCHEMA.dbscan($1, $2, $3, $4, $5, NULL, NULL, NULL); |
| $$ LANGUAGE sql VOLATILE |
| m4_ifdef(`\_\_HAS_FUNCTION_PROPERTIES\_\_', `MODIFIES SQL DATA', `'); |
| |
| CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.dbscan_predict( |
| dbscan_table VARCHAR, |
| source_table VARCHAR, |
| id_column VARCHAR, |
| expr_point VARCHAR, |
| output_table VARCHAR |
| ) RETURNS VOID AS $$ |
| PythonFunction(dbscan, dbscan, dbscan_predict) |
| $$ LANGUAGE plpythonu VOLATILE |
| m4_ifdef(`\_\_HAS_FUNCTION_PROPERTIES\_\_', `MODIFIES SQL DATA', `'); |
| |
| |
| CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.dbscan( |
| message VARCHAR |
| ) RETURNS VARCHAR AS $$ |
| PythonFunction(dbscan, dbscan, dbscan_help) |
| $$ LANGUAGE plpythonu VOLATILE |
| m4_ifdef(`\_\_HAS_FUNCTION_PROPERTIES\_\_', `MODIFIES SQL DATA', `'); |
| |
| CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.dbscan( |
| ) RETURNS VARCHAR AS $$ |
| PythonFunction(dbscan, dbscan, dbscan_help) |
| $$ LANGUAGE plpythonu VOLATILE |
| m4_ifdef(`\_\_HAS_FUNCTION_PROPERTIES\_\_', `MODIFIES SQL DATA', `'); |
| |
| CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.dbscan_predict( |
| message VARCHAR |
| ) RETURNS VARCHAR AS $$ |
| PythonFunction(dbscan, dbscan, dbscan_predict_help) |
| $$ LANGUAGE plpythonu VOLATILE |
| m4_ifdef(`\_\_HAS_FUNCTION_PROPERTIES\_\_', `MODIFIES SQL DATA', `'); |
| |
| CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.dbscan_predict( |
| ) RETURNS VARCHAR AS $$ |
| PythonFunction(dbscan, dbscan, dbscan_predict_help) |
| $$ LANGUAGE plpythonu VOLATILE |
| m4_ifdef(`\_\_HAS_FUNCTION_PROPERTIES\_\_', `MODIFIES SQL DATA', `'); |
