You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@madlib.apache.org by GitBox <gi...@apache.org> on 2020/05/04 18:12:44 UTC

[GitHub] [madlib] orhankislal opened a new pull request #496: DBSCAN: Add new module DBSCAN

orhankislal opened a new pull request #496:
URL: https://github.com/apache/madlib/pull/496


   This commit adds the DBSCAN module. It includes the brute force
   implementation of DBSCAN as well as a prediction function. In
   addition their associated tests and online documentation are
   included.
   
   <!--  
   
   Thanks for sending a pull request!  Here are some tips for you:
   1. Refer to this link for contribution guidelines https://cwiki.apache.org/confluence/display/MADLIB/Contribution+Guidelines
   2. Please Provide the Module Name, a JIRA Number and a short description about your changes.
   -->
   
   - [ ] Add the module name, JIRA# to PR/commit and description.
   - [ ] Add tests for the change. 
   
   


----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

For queries about this service, please contact Infrastructure at:
users@infra.apache.org



[GitHub] [madlib] fmcquillan99 edited a comment on pull request #496: DBSCAN: Add new module DBSCAN

Posted by GitBox <gi...@apache.org>.
fmcquillan99 edited a comment on pull request #496:
URL: https://github.com/apache/madlib/pull/496#issuecomment-624228952


   (5)
   To be consistent with knn, can we please make the algorithm `brute_force` as the base.  It seems you can do `brute` but `brute_force` does not work:
   ```
   SELECT madlib.dbscan( 
   				'dbscan_train_data',	-- source table
   				'dbscan_result',		-- output table
   				'pid',					-- point id column
   				'pointsxx',				-- data point
   				 1.75,					-- epsilon
   				 4,						-- min samples
   				 'dist_norm2',	-- metric
   				'brute_force');			-- algorithm
   
   ERROR:  plpy.Error: dbscan Error: algorithm has to be one of the following: brute, kd-tree (plpython.c:5038)
   CONTEXT:  Traceback (most recent call last):
     PL/Python function "dbscan", line 21, in <module>
       return dbscan.dbscan(**globals())
     PL/Python function "dbscan", line 38, in dbscan
     PL/Python function "dbscan", line 184, in _validate_dbscan
     PL/Python function "dbscan", line 123, in _assert
   PL/Python function "dbscan"
   ```
   
   
   (6) 
   It seems the column header `points` does not work, maybe in conflicts with an internal name?
   I think it could be a common col name so we should fix this.
   ```
   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');			-- algorithm
   
   ERROR:  plpy.SPIError: column reference "points" is ambiguous
   LINE 3:             SET points = points
                                    ^
   QUERY:  
               UPDATE dbscan_result AS t1
               SET points = points
               FROM dbscan_train_data AS t2
               WHERE t1.pid = t2.pid
           
   CONTEXT:  Traceback (most recent call last):
     PL/Python function "dbscan", line 21, in <module>
       return dbscan.dbscan(**globals())
     PL/Python function "dbscan", line 109, in dbscan
   PL/Python function "dbscan"
   ```


----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

For queries about this service, please contact Infrastructure at:
users@infra.apache.org



[GitHub] [madlib] fmcquillan99 commented on pull request #496: DBSCAN: Add new module DBSCAN

Posted by GitBox <gi...@apache.org>.
fmcquillan99 commented on pull request #496:
URL: https://github.com/apache/madlib/pull/496#issuecomment-624228952


   (5)
   To be consistent with knn, can we please make the algorithm `brute_force` as the base.  It seems you can do `brute` but `brute_force` does not work:
   ```
   SELECT madlib.dbscan( 
   				'dbscan_train_data',	-- source table
   				'dbscan_result',		-- output table
   				'pid',					-- point id column
   				'pointsxx',				-- data point
   				 1.75,					-- epsilon
   				 4,						-- min samples
   				 'dist_norm2',	-- metric
   				'brute_force');			-- algorithm
   
   ERROR:  plpy.Error: dbscan Error: algorithm has to be one of the following: brute, kd-tree (plpython.c:5038)
   CONTEXT:  Traceback (most recent call last):
     PL/Python function "dbscan", line 21, in <module>
       return dbscan.dbscan(**globals())
     PL/Python function "dbscan", line 38, in dbscan
     PL/Python function "dbscan", line 184, in _validate_dbscan
     PL/Python function "dbscan", line 123, in _assert
   PL/Python function "dbscan"
   ```
   
   
   (6) 
   It seems the column header `points` does not work, maybe in conflicts with an internal name?
   I think it could be a common col name so we should fix this.
   ```
   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');			-- algorithm
   
   ERROR:  plpy.SPIError: column reference "points" is ambiguous
   LINE 3:             SET points = points
                                    ^
   QUERY:  
               UPDATE dbscan_result AS t1
               SET points = points
               FROM dbscan_train_data AS t2
               WHERE t1.pid = t2.pid
           
   CONTEXT:  Traceback (most recent call last):
     PL/Python function "dbscan", line 21, in <module>
       return dbscan.dbscan(**globals())
     PL/Python function "dbscan", line 109, in dbscan
   PL/Python function "dbscan"
   ```
   
   
   (7)
   Please remove the verbose output unless you need it for debugging and such:
   ```
   ALTER        ANALYZE      BEGIN        CHECKPOINT   CLOSE        CLUSTER      COMMENT      COMMIT       COPY         
   CREATE       DEALLOCATE   DECLARE      DELETE FROM  DISCARD      DO           DROP         END          EXECUTE      
   EXPLAIN      FETCH        GRANT        INSERT       LISTEN       LOAD         LOCK         MOVE         NOTIFY       
   PREPARE      REASSIGN     REINDEX      RELEASE      RESET        REVOKE       ROLLBACK     SAVEPOINT    SELECT       
   SET          SHOW         START        TABLE        TRUNCATE     UNLISTEN     UPDATE       VACUUM       VALUES       
   WITH         ABORT     
   etc.   
   ```


----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

For queries about this service, please contact Infrastructure at:
users@infra.apache.org



[GitHub] [madlib] orhankislal commented on pull request #496: DBSCAN: Add new module DBSCAN

Posted by GitBox <gi...@apache.org>.
orhankislal commented on pull request #496:
URL: https://github.com/apache/madlib/pull/496#issuecomment-624215893


   @fmcquillan99 Thanks for the comments. Here is an example on how to run the prediction on a table:
   `select id_in, madlib.dbscan_predict('out1',data) from dbscan_train_data ;`


----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

For queries about this service, please contact Infrastructure at:
users@infra.apache.org



[GitHub] [madlib] fmcquillan99 edited a comment on pull request #496: DBSCAN: Add new module DBSCAN

Posted by GitBox <gi...@apache.org>.
fmcquillan99 edited a comment on pull request #496:
URL: https://github.com/apache/madlib/pull/496#issuecomment-624228952


   (5)
   To be consistent with knn, can we please make the algorithm `brute_force` as the base.  It seems you can do `brute` but `brute_force` does not work:
   ```
   SELECT madlib.dbscan( 
   				'dbscan_train_data',	-- source table
   				'dbscan_result',		-- output table
   				'pid',					-- point id column
   				'pointsxx',				-- data point
   				 1.75,					-- epsilon
   				 4,						-- min samples
   				 'dist_norm2',	-- metric
   				'brute_force');			-- algorithm
   
   ERROR:  plpy.Error: dbscan Error: algorithm has to be one of the following: brute, kd-tree (plpython.c:5038)
   CONTEXT:  Traceback (most recent call last):
     PL/Python function "dbscan", line 21, in <module>
       return dbscan.dbscan(**globals())
     PL/Python function "dbscan", line 38, in dbscan
     PL/Python function "dbscan", line 184, in _validate_dbscan
     PL/Python function "dbscan", line 123, in _assert
   PL/Python function "dbscan"
   ```
   
   
   (6) 
   It seems the column header `points` does not work, maybe in conflicts with an internal name?
   I think it could be a common col name so we should fix this.
   ```
   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');			-- algorithm
   
   ERROR:  plpy.SPIError: column reference "points" is ambiguous
   LINE 3:             SET points = points
                                    ^
   QUERY:  
               UPDATE dbscan_result AS t1
               SET points = points
               FROM dbscan_train_data AS t2
               WHERE t1.pid = t2.pid
           
   CONTEXT:  Traceback (most recent call last):
     PL/Python function "dbscan", line 21, in <module>
       return dbscan.dbscan(**globals())
     PL/Python function "dbscan", line 109, in dbscan
   PL/Python function "dbscan"
   ```
   
   (7)
   Please check the logic with the following example from
   https://dbs.ifi.uni-heidelberg.de/files/Team/eschubert/lectures/KDDClusterAnalysis17-screen.pdf#page=215
   
   I think there should only be 3 clusters created
   
   ```
   DROP TABLE IF EXISTS dbscan_train_data;
   CREATE TABLE dbscan_train_data (pid int, pointsxx 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}');
   
   DROP TABLE IF EXISTS dbscan_result;
   SELECT madlib.dbscan( 
   				'dbscan_train_data',	-- source table
   				'dbscan_result',		-- output table
   				'pid',					-- point id column
   				'pointsxx',				-- data point
   				 1.75,					-- epsilon
   				 4,						-- min samples
   				'dist_norm2',	        -- metric
   				'brute');     			-- algorithm
   
   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;
   
    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 |          3 | t             | {9,4}
     18 |          3 | t             | {10,4}
     19 |          4 | t             | {11,4}
     20 |          5 | t             | {10,3}
   (17 rows)
   ```
   


----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

For queries about this service, please contact Infrastructure at:
users@infra.apache.org



[GitHub] [madlib] fmcquillan99 edited a comment on pull request #496: DBSCAN: Add new module DBSCAN

Posted by GitBox <gi...@apache.org>.
fmcquillan99 edited a comment on pull request #496:
URL: https://github.com/apache/madlib/pull/496#issuecomment-624228952


   (5)
   To be consistent with knn, can we please make the algorithm `brute_force` as the base.  It seems you can do `brute` but `brute_force` does not work:
   ```
   SELECT madlib.dbscan( 
   				'dbscan_train_data',	-- source table
   				'dbscan_result',		-- output table
   				'pid',					-- point id column
   				'pointsxx',				-- data point
   				 1.75,					-- epsilon
   				 4,						-- min samples
   				 'dist_norm2',	-- metric
   				'brute_force');			-- algorithm
   
   ERROR:  plpy.Error: dbscan Error: algorithm has to be one of the following: brute, kd-tree (plpython.c:5038)
   CONTEXT:  Traceback (most recent call last):
     PL/Python function "dbscan", line 21, in <module>
       return dbscan.dbscan(**globals())
     PL/Python function "dbscan", line 38, in dbscan
     PL/Python function "dbscan", line 184, in _validate_dbscan
     PL/Python function "dbscan", line 123, in _assert
   PL/Python function "dbscan"
   ```
   
   
   (6) 
   It seems the column header `points` does not work, maybe in conflicts with an internal name?
   I think it could be a common col name so we should fix this.
   ```
   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');			-- algorithm
   
   ERROR:  plpy.SPIError: column reference "points" is ambiguous
   LINE 3:             SET points = points
                                    ^
   QUERY:  
               UPDATE dbscan_result AS t1
               SET points = points
               FROM dbscan_train_data AS t2
               WHERE t1.pid = t2.pid
           
   CONTEXT:  Traceback (most recent call last):
     PL/Python function "dbscan", line 21, in <module>
       return dbscan.dbscan(**globals())
     PL/Python function "dbscan", line 109, in dbscan
   PL/Python function "dbscan"
   ```
   
   (7)
   Please check the logic with the following example from
   https://dbs.ifi.uni-heidelberg.de/files/Team/eschubert/lectures/KDDClusterAnalysis17-screen.pdf#page=215
   
   I think there should only be 3 clusters created
   
   ```
   DROP TABLE IF EXISTS dbscan_train_data;
   CREATE TABLE dbscan_train_data (pid int, pointsxx 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}');
   
   DROP TABLE IF EXISTS dbscan_result;
   SELECT madlib.dbscan( 
   				'dbscan_train_data',	-- source table
   				'dbscan_result',		-- output table
   				'pid',					-- point id column
   				'pointsxx',				-- data point
   				 1.75,					-- epsilon
   				 4,						-- min samples
   				'dist_norm2',	        -- metric
   				'brute');     			-- algorithm
   
   SELECT * FROM dbscan_result ORDER BY pid;
   
    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 |          3 | t             | {9,4}
     18 |          3 | t             | {10,4}
     19 |          4 | t             | {11,4}
     20 |          5 | t             | {10,3}
   (17 rows)
   ```
   


----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

For queries about this service, please contact Infrastructure at:
users@infra.apache.org



[GitHub] [madlib] orhankislal commented on pull request #496: DBSCAN: Add new module DBSCAN

Posted by GitBox <gi...@apache.org>.
orhankislal commented on pull request #496:
URL: https://github.com/apache/madlib/pull/496#issuecomment-625452328


   jenkins retest this


----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

For queries about this service, please contact Infrastructure at:
users@infra.apache.org



[GitHub] [madlib] reductionista commented on a change in pull request #496: DBSCAN: Add new module DBSCAN

Posted by GitBox <gi...@apache.org>.
reductionista commented on a change in pull request #496:
URL: https://github.com/apache/madlib/pull/496#discussion_r421099375



##########
File path: src/ports/postgres/modules/dbscan/dbscan.py_in
##########
@@ -0,0 +1,331 @@
+# coding=utf-8
+#
+# 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.
+
+import plpy
+
+from utilities.control import MinWarning
+from utilities.utilities import _assert
+from utilities.utilities import unique_string
+from utilities.utilities import add_postfix
+from utilities.utilities import NUMERIC, ONLY_ARRAY
+from utilities.utilities import is_valid_psql_type
+from utilities.utilities import is_platform_pg
+from utilities.validate_args import input_tbl_valid, output_tbl_valid
+from utilities.validate_args import is_var_valid
+from utilities.validate_args import cols_in_tbl_valid
+from utilities.validate_args import get_expr_type
+from utilities.validate_args import get_algorithm_name
+from graph.wcc import wcc
+
+BRUTE_FORCE = 'brute_force'
+KD_TREE = 'kd_tree'
+
+def dbscan(schema_madlib, source_table, output_table, id_column, expr_point, eps, min_samples, metric, algorithm, **kwargs):
+
+    with MinWarning("warning"):
+
+        min_samples = 5 if not min_samples else min_samples
+        metric = 'squared_dist_norm2' if not metric else metric
+        algorithm = 'brute' if not algorithm else algorithm
+
+        algorithm = get_algorithm_name(algorithm, BRUTE_FORCE,
+            [BRUTE_FORCE, KD_TREE], 'DBSCAN')
+
+        _validate_dbscan(schema_madlib, source_table, output_table, id_column,
+                         expr_point, eps, min_samples, metric, algorithm)
+
+        dist_src_sql = ''  if is_platform_pg() else 'DISTRIBUTED BY (__src__)'
+        dist_id_sql = ''  if is_platform_pg() else 'DISTRIBUTED BY ({0})'.format(id_column)
+        dist_reach_sql = ''  if is_platform_pg() else 'DISTRIBUTED BY (__reachable_id__)'
+
+        # Calculate pairwise distances
+        distance_table = unique_string(desp='distance_table')
+        plpy.execute("DROP TABLE IF EXISTS {0}".format(distance_table))
+
+        sql = """
+            CREATE TABLE {distance_table} AS
+            SELECT __src__, __dest__ FROM (
+                SELECT  __t1__.{id_column} AS __src__,
+                        __t2__.{id_column} AS __dest__,
+                        {schema_madlib}.{metric}(
+                            __t1__.{expr_point}, __t2__.{expr_point}) AS __dist__
+                FROM {source_table} AS __t1__, {source_table} AS __t2__) q1
+            WHERE __dist__ < {eps}
+            {dist_src_sql}
+            """.format(**locals())
+        plpy.execute(sql)
+
+        # Find core points
+        core_points_table = unique_string(desp='core_points_table')
+        plpy.execute("DROP TABLE IF EXISTS {0}".format(core_points_table))
+        sql = """
+            CREATE TABLE {core_points_table} AS
+            SELECT * FROM (SELECT __src__ AS {id_column}, count(*) AS __count__
+                           FROM {distance_table} GROUP BY __src__) q1
+            WHERE __count__ >= {min_samples}
+            {dist_id_sql}
+            """.format(**locals())
+        plpy.execute(sql)
+
+        # Find the connections between core points to form the clusters
+        core_edge_table = unique_string(desp='core_edge_table')
+        plpy.execute("DROP TABLE IF EXISTS {0}".format(core_edge_table))
+        sql = """
+            CREATE TABLE {core_edge_table} AS
+            SELECT __src__, __dest__
+            FROM {distance_table} AS __t1__, (SELECT array_agg({id_column}) AS arr
+                                              FROM {core_points_table}) __t2__
+            WHERE __t1__.__src__ = ANY(arr) AND __t1__.__dest__ = ANY(arr)
+            {dist_src_sql}
+        """.format(**locals())
+        plpy.execute(sql)
+
+        # Run wcc to get the min id for each cluster
+        wcc(schema_madlib, core_points_table, id_column, core_edge_table, 'src=__src__, dest=__dest__',
+            output_table, None)
+        plpy.execute("""
+            ALTER TABLE {0}
+            ADD COLUMN is_core_point BOOLEAN,
+            ADD COLUMN __points__ DOUBLE PRECISION[]
+            """.format(output_table))
+        plpy.execute("""
+            ALTER TABLE {0}
+            RENAME COLUMN component_id TO cluster_id
+            """.format(output_table))
+        plpy.execute("""
+            UPDATE {0}
+            SET is_core_point = TRUE
+        """.format(output_table))
+
+        # Find reachable points
+        reachable_points_table = unique_string(desp='reachable_points_table')
+        plpy.execute("DROP TABLE IF EXISTS {0}".format(reachable_points_table))
+        sql = """
+            CREATE TABLE {reachable_points_table} AS
+                SELECT array_agg(__src__) AS __src_list__,
+                       __dest__ AS __reachable_id__
+                FROM {distance_table} AS __t1__,
+                     (SELECT array_agg({id_column}) AS __arr__
+                      FROM {core_points_table}) __t2__
+                WHERE __src__ = ANY(__arr__) AND __dest__ != ALL(__arr__)
+                GROUP BY __dest__
+                {dist_reach_sql}
+            """.format(**locals())
+        plpy.execute(sql)
+
+        sql = """
+            INSERT INTO {output_table}
+            SELECT  __reachable_id__ as {id_column},
+                    cluster_id,
+                    FALSE AS is_core_point,
+                    NULL AS __points__
+            FROM {reachable_points_table} AS __t1__ INNER JOIN
+                 {output_table} AS __t2__
+                 ON (__src_list__[1] = {id_column})
+            """.format(**locals())
+        plpy.execute(sql)
+
+        # Add features of points to the output table to use them for prediction
+        sql = """
+            UPDATE {output_table} AS __t1__
+            SET __points__ = {expr_point}
+            FROM {source_table} AS __t2__
+            WHERE __t1__.{id_column} = __t2__.{id_column}
+        """.format(**locals())
+        plpy.execute(sql)
+
+        # Update the cluster ids to be consecutive
+        sql = """
+            UPDATE {output_table} AS __t1__
+            SET cluster_id = new_id-1
+            FROM (
+                SELECT cluster_id, row_number() OVER(ORDER BY cluster_id) AS new_id
+                FROM {output_table}
+                GROUP BY cluster_id) __t2__
+            WHERE __t1__.cluster_id = __t2__.cluster_id
+        """.format(**locals())
+        plpy.execute(sql)
+
+        output_summary_table = add_postfix(output_table, '_summary')
+        plpy.execute("DROP TABLE IF EXISTS {0}".format(output_summary_table))
+
+        sql = """
+            CREATE TABLE {output_summary_table} AS
+            SELECT  '{id_column}'::VARCHAR AS id_column,
+                    {eps}::DOUBLE PRECISION AS eps,
+                    '{metric}'::VARCHAR AS metric
+            """.format(**locals())
+        plpy.execute(sql)
+
+        plpy.execute("DROP TABLE IF EXISTS {0}, {1}, {2}".format(
+                     distance_table, core_points_table, reachable_points_table))
+
+
+def dbscan_predict(schema_madlib, dbscan_table, new_point, **kwargs):
+
+    with MinWarning("warning"):
+
+        dbscan_summary_table = add_postfix(dbscan_table, '_summary')
+        summary = plpy.execute("SELECT * FROM {0}".format(dbscan_summary_table))[0]
+
+        eps = summary['eps']
+        metric = summary['metric']
+        sql = """
+            SELECT cluster_id,
+                   {schema_madlib}.{metric}(__points__, ARRAY{new_point}) as dist
+            FROM {dbscan_table}
+            WHERE is_core_point = TRUE
+            ORDER BY dist LIMIT 1
+            """.format(**locals())
+        result = plpy.execute(sql)[0]
+        dist = result['dist']
+        if dist < eps:
+            return result['cluster_id']
+        else:
+            return None
+
+def _validate_dbscan(schema_madlib, source_table, output_table, id_column, expr_point, eps, min_samples, metric, algorithm):
+
+    input_tbl_valid(source_table, 'dbscan')
+    output_tbl_valid(output_table, 'dbscan')
+    output_summary_table = add_postfix(output_table, '_summary')
+    output_tbl_valid(output_summary_table, 'dbscan')
+
+    cols_in_tbl_valid(source_table, [id_column], 'dbscan')
+
+    _assert(is_var_valid(source_table, expr_point),
+            "dbscan error: {0} is an invalid column name or "
+            "expression for expr_point param".format(expr_point))
+
+    point_col_type = get_expr_type(expr_point, source_table)
+    _assert(is_valid_psql_type(point_col_type, NUMERIC | ONLY_ARRAY),
+            "dbscan Error: Feature column or expression '{0}' in train table is not"
+            " an array.".format(expr_point))

Review comment:
       Maybe this error message should say something like "... in train table should be a numeric array", to handle the case where someone accidentally passes a column with a type like `TEXT[]`

##########
File path: src/ports/postgres/modules/dbscan/dbscan.py_in
##########
@@ -0,0 +1,331 @@
+# coding=utf-8
+#
+# 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.
+
+import plpy
+
+from utilities.control import MinWarning
+from utilities.utilities import _assert
+from utilities.utilities import unique_string
+from utilities.utilities import add_postfix
+from utilities.utilities import NUMERIC, ONLY_ARRAY
+from utilities.utilities import is_valid_psql_type
+from utilities.utilities import is_platform_pg
+from utilities.validate_args import input_tbl_valid, output_tbl_valid
+from utilities.validate_args import is_var_valid
+from utilities.validate_args import cols_in_tbl_valid
+from utilities.validate_args import get_expr_type
+from utilities.validate_args import get_algorithm_name
+from graph.wcc import wcc
+
+BRUTE_FORCE = 'brute_force'
+KD_TREE = 'kd_tree'
+
+def dbscan(schema_madlib, source_table, output_table, id_column, expr_point, eps, min_samples, metric, algorithm, **kwargs):
+
+    with MinWarning("warning"):
+
+        min_samples = 5 if not min_samples else min_samples
+        metric = 'squared_dist_norm2' if not metric else metric
+        algorithm = 'brute' if not algorithm else algorithm
+
+        algorithm = get_algorithm_name(algorithm, BRUTE_FORCE,
+            [BRUTE_FORCE, KD_TREE], 'DBSCAN')
+
+        _validate_dbscan(schema_madlib, source_table, output_table, id_column,
+                         expr_point, eps, min_samples, metric, algorithm)
+
+        dist_src_sql = ''  if is_platform_pg() else 'DISTRIBUTED BY (__src__)'
+        dist_id_sql = ''  if is_platform_pg() else 'DISTRIBUTED BY ({0})'.format(id_column)
+        dist_reach_sql = ''  if is_platform_pg() else 'DISTRIBUTED BY (__reachable_id__)'
+
+        # Calculate pairwise distances
+        distance_table = unique_string(desp='distance_table')
+        plpy.execute("DROP TABLE IF EXISTS {0}".format(distance_table))
+
+        sql = """
+            CREATE TABLE {distance_table} AS
+            SELECT __src__, __dest__ FROM (
+                SELECT  __t1__.{id_column} AS __src__,
+                        __t2__.{id_column} AS __dest__,
+                        {schema_madlib}.{metric}(
+                            __t1__.{expr_point}, __t2__.{expr_point}) AS __dist__
+                FROM {source_table} AS __t1__, {source_table} AS __t2__) q1
+            WHERE __dist__ < {eps}
+            {dist_src_sql}
+            """.format(**locals())
+        plpy.execute(sql)
+
+        # Find core points
+        core_points_table = unique_string(desp='core_points_table')
+        plpy.execute("DROP TABLE IF EXISTS {0}".format(core_points_table))
+        sql = """
+            CREATE TABLE {core_points_table} AS
+            SELECT * FROM (SELECT __src__ AS {id_column}, count(*) AS __count__
+                           FROM {distance_table} GROUP BY __src__) q1
+            WHERE __count__ >= {min_samples}
+            {dist_id_sql}
+            """.format(**locals())
+        plpy.execute(sql)
+
+        # Find the connections between core points to form the clusters
+        core_edge_table = unique_string(desp='core_edge_table')
+        plpy.execute("DROP TABLE IF EXISTS {0}".format(core_edge_table))
+        sql = """
+            CREATE TABLE {core_edge_table} AS
+            SELECT __src__, __dest__
+            FROM {distance_table} AS __t1__, (SELECT array_agg({id_column}) AS arr
+                                              FROM {core_points_table}) __t2__
+            WHERE __t1__.__src__ = ANY(arr) AND __t1__.__dest__ = ANY(arr)
+            {dist_src_sql}
+        """.format(**locals())
+        plpy.execute(sql)
+
+        # Run wcc to get the min id for each cluster
+        wcc(schema_madlib, core_points_table, id_column, core_edge_table, 'src=__src__, dest=__dest__',
+            output_table, None)
+        plpy.execute("""
+            ALTER TABLE {0}
+            ADD COLUMN is_core_point BOOLEAN,
+            ADD COLUMN __points__ DOUBLE PRECISION[]
+            """.format(output_table))
+        plpy.execute("""
+            ALTER TABLE {0}
+            RENAME COLUMN component_id TO cluster_id
+            """.format(output_table))
+        plpy.execute("""
+            UPDATE {0}
+            SET is_core_point = TRUE
+        """.format(output_table))
+
+        # Find reachable points
+        reachable_points_table = unique_string(desp='reachable_points_table')
+        plpy.execute("DROP TABLE IF EXISTS {0}".format(reachable_points_table))
+        sql = """
+            CREATE TABLE {reachable_points_table} AS
+                SELECT array_agg(__src__) AS __src_list__,
+                       __dest__ AS __reachable_id__
+                FROM {distance_table} AS __t1__,
+                     (SELECT array_agg({id_column}) AS __arr__
+                      FROM {core_points_table}) __t2__
+                WHERE __src__ = ANY(__arr__) AND __dest__ != ALL(__arr__)
+                GROUP BY __dest__
+                {dist_reach_sql}
+            """.format(**locals())
+        plpy.execute(sql)
+
+        sql = """
+            INSERT INTO {output_table}
+            SELECT  __reachable_id__ as {id_column},
+                    cluster_id,
+                    FALSE AS is_core_point,
+                    NULL AS __points__
+            FROM {reachable_points_table} AS __t1__ INNER JOIN
+                 {output_table} AS __t2__
+                 ON (__src_list__[1] = {id_column})
+            """.format(**locals())
+        plpy.execute(sql)
+
+        # Add features of points to the output table to use them for prediction
+        sql = """
+            UPDATE {output_table} AS __t1__
+            SET __points__ = {expr_point}
+            FROM {source_table} AS __t2__
+            WHERE __t1__.{id_column} = __t2__.{id_column}
+        """.format(**locals())
+        plpy.execute(sql)
+
+        # Update the cluster ids to be consecutive
+        sql = """
+            UPDATE {output_table} AS __t1__
+            SET cluster_id = new_id-1
+            FROM (
+                SELECT cluster_id, row_number() OVER(ORDER BY cluster_id) AS new_id
+                FROM {output_table}
+                GROUP BY cluster_id) __t2__
+            WHERE __t1__.cluster_id = __t2__.cluster_id
+        """.format(**locals())
+        plpy.execute(sql)
+
+        output_summary_table = add_postfix(output_table, '_summary')
+        plpy.execute("DROP TABLE IF EXISTS {0}".format(output_summary_table))
+
+        sql = """
+            CREATE TABLE {output_summary_table} AS
+            SELECT  '{id_column}'::VARCHAR AS id_column,
+                    {eps}::DOUBLE PRECISION AS eps,
+                    '{metric}'::VARCHAR AS metric
+            """.format(**locals())
+        plpy.execute(sql)
+
+        plpy.execute("DROP TABLE IF EXISTS {0}, {1}, {2}".format(
+                     distance_table, core_points_table, reachable_points_table))

Review comment:
       Add `core_edge_table` to list of tables to DROP.  I noticed this sticks around after running it.
   Also, should we be using CREATE TEMP TABLE for these?  (In which case I think they get dropped automatically?)




----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

For queries about this service, please contact Infrastructure at:
users@infra.apache.org



[GitHub] [madlib] fmcquillan99 commented on pull request #496: DBSCAN: Add new module DBSCAN

Posted by GitBox <gi...@apache.org>.
fmcquillan99 commented on pull request #496:
URL: https://github.com/apache/madlib/pull/496#issuecomment-628849217


   LGTM


----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

For queries about this service, please contact Infrastructure at:
users@infra.apache.org



[GitHub] [madlib] reductionista commented on a change in pull request #496: DBSCAN: Add new module DBSCAN

Posted by GitBox <gi...@apache.org>.
reductionista commented on a change in pull request #496:
URL: https://github.com/apache/madlib/pull/496#discussion_r421143072



##########
File path: src/ports/postgres/modules/dbscan/dbscan.py_in
##########
@@ -0,0 +1,331 @@
+# coding=utf-8
+#
+# 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.
+
+import plpy
+
+from utilities.control import MinWarning
+from utilities.utilities import _assert
+from utilities.utilities import unique_string
+from utilities.utilities import add_postfix
+from utilities.utilities import NUMERIC, ONLY_ARRAY
+from utilities.utilities import is_valid_psql_type
+from utilities.utilities import is_platform_pg
+from utilities.validate_args import input_tbl_valid, output_tbl_valid
+from utilities.validate_args import is_var_valid
+from utilities.validate_args import cols_in_tbl_valid
+from utilities.validate_args import get_expr_type
+from utilities.validate_args import get_algorithm_name
+from graph.wcc import wcc
+
+BRUTE_FORCE = 'brute_force'
+KD_TREE = 'kd_tree'
+
+def dbscan(schema_madlib, source_table, output_table, id_column, expr_point, eps, min_samples, metric, algorithm, **kwargs):
+
+    with MinWarning("warning"):
+
+        min_samples = 5 if not min_samples else min_samples
+        metric = 'squared_dist_norm2' if not metric else metric
+        algorithm = 'brute' if not algorithm else algorithm
+
+        algorithm = get_algorithm_name(algorithm, BRUTE_FORCE,
+            [BRUTE_FORCE, KD_TREE], 'DBSCAN')
+
+        _validate_dbscan(schema_madlib, source_table, output_table, id_column,
+                         expr_point, eps, min_samples, metric, algorithm)
+
+        dist_src_sql = ''  if is_platform_pg() else 'DISTRIBUTED BY (__src__)'
+        dist_id_sql = ''  if is_platform_pg() else 'DISTRIBUTED BY ({0})'.format(id_column)
+        dist_reach_sql = ''  if is_platform_pg() else 'DISTRIBUTED BY (__reachable_id__)'
+
+        # Calculate pairwise distances
+        distance_table = unique_string(desp='distance_table')
+        plpy.execute("DROP TABLE IF EXISTS {0}".format(distance_table))
+
+        sql = """
+            CREATE TABLE {distance_table} AS
+            SELECT __src__, __dest__ FROM (
+                SELECT  __t1__.{id_column} AS __src__,
+                        __t2__.{id_column} AS __dest__,
+                        {schema_madlib}.{metric}(
+                            __t1__.{expr_point}, __t2__.{expr_point}) AS __dist__
+                FROM {source_table} AS __t1__, {source_table} AS __t2__) q1
+            WHERE __dist__ < {eps}
+            {dist_src_sql}
+            """.format(**locals())
+        plpy.execute(sql)
+
+        # Find core points
+        core_points_table = unique_string(desp='core_points_table')
+        plpy.execute("DROP TABLE IF EXISTS {0}".format(core_points_table))
+        sql = """
+            CREATE TABLE {core_points_table} AS
+            SELECT * FROM (SELECT __src__ AS {id_column}, count(*) AS __count__
+                           FROM {distance_table} GROUP BY __src__) q1
+            WHERE __count__ >= {min_samples}
+            {dist_id_sql}
+            """.format(**locals())
+        plpy.execute(sql)
+
+        # Find the connections between core points to form the clusters
+        core_edge_table = unique_string(desp='core_edge_table')
+        plpy.execute("DROP TABLE IF EXISTS {0}".format(core_edge_table))
+        sql = """
+            CREATE TABLE {core_edge_table} AS
+            SELECT __src__, __dest__
+            FROM {distance_table} AS __t1__, (SELECT array_agg({id_column}) AS arr
+                                              FROM {core_points_table}) __t2__
+            WHERE __t1__.__src__ = ANY(arr) AND __t1__.__dest__ = ANY(arr)
+            {dist_src_sql}

Review comment:
       Somehow a comment I left here got dropped when I submitted.
   
   I was just wondering, maybe we should add `AND __t1__.__src__ != __t1__.__dest__` to the WHERE clause?  It don't know that it hurts anything to have an extra 0-length edge for each core point, but maybe adds some minor extra work for wcc to do having them in there.  Or, maybe the filter should go earlier where the distance is computed instead?




----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

For queries about this service, please contact Infrastructure at:
users@infra.apache.org



[GitHub] [madlib] fmcquillan99 commented on pull request #496: DBSCAN: Add new module DBSCAN

Posted by GitBox <gi...@apache.org>.
fmcquillan99 commented on pull request #496:
URL: https://github.com/apache/madlib/pull/496#issuecomment-623785188


   (1)
   ```
   madlib=# select madlib.dbscan('usage')                                                                                        ;
                                       dbscan                                     
   -------------------------------------------------------------------------------
                                                                                  
    -----------------------------------------------------------------------       
                                USAGE                                             
    -----------------------------------------------------------------------       
    SELECT madlib.dbscan(                                                         
        source_table,       -- Name of the training data table                    
        output_table,       -- Name of the output table                           
        id_column,          -- Name of id column in source_table                  
        expr_point,         -- Column name or expression for data points          
        eps,                -- The minimum radius of a cluster                    
        min_samples,        -- The minimum size of a cluster                      
        metric              -- The name of the function to use to calculate the   
                            -- distance                                           
        algorithm           -- The algorithm to use for dbscan.                   
        ); 
   ```
   Missing comma after metric
   
   
   (2)
   ```
   madlib=# select madlib.dbscan_predict('usage')                                                                                ;
   ERROR:  function madlib.dbscan_predict(unknown) does not exist
   LINE 1: select madlib.dbscan_predict('usage')
                  ^
   HINT:  No function matches the given name and argument types. You might need to add explicit type casts.
   ```  
   This usage function seems to be missing
   
   
   (3) Suggest make following params optional:
   ```
   min_samples, default: 5
   metric, default: 'squared_dist_norm2'
   algorithm, default: 'brute_force'
   ```
   
   
   (4) Can you give me an example of how you would do batch prediction?
   
   
   
   
   
   
   
   
   


----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

For queries about this service, please contact Infrastructure at:
users@infra.apache.org