Variable density-based clustering on data streams

Patent metadata

Field	Value
Publication number	US-11630855-B2
Application number	US-202117444395-A
Country	US
Kind code	B2
Filing date	Aug 4, 2021
Priority date	Aug 4, 2021
Publication date	Apr 18, 2023
Grant date	Apr 18, 2023

Abstract

In some implementations, a device may receive, from a data stream, a set of data points arranged in a dimensional data space. The device may compare the set of data points to identify one or more clusters using values of a distance parameter for data points included in the set of data points, wherein the values of distance parameter includes different values of the distance parameter for different data points. The device may transmit an indication of the one or more clusters to cause a device to display information associated with the one or more clusters. The device may receive, from the device, feedback information associated with at least one data point, wherein the feedback information indicates that at least one data point is associated with an error. The device may modify a value of the distance parameter associated with the at least one data point to a modified value.

First claim

What is claimed is:

1. A system for variable density-based clustering on data streams, the system comprising:
one or more memories; and
one or more processors, coupled to the one or more memories, configured to:
receive, from a data stream, a set of data points arranged in a dimensional data space;
analyze the set of data points to identify one or more clusters from the set of data points, wherein analyzing the set of data points includes:
comparing a first data point and a second data point from the set of data points;
determining if a distance between the first data point and the second data point, in the dimensional data space, satisfies a value of a distance parameter; and
correlating the first data point and the second data point in a first cluster if the distance between the first data point and the second data point satisfies value of the distance parameter,
wherein the value of the distance parameter is specific to at least one of the first data point or the second data point, and
wherein analyzing the set of data points includes analyzing the set of data points using different values for the distance parameter for different data points;

determine if a first radius of a new data point arranged in the dimensional data space, defined by a first value of the distance parameter associated with the new data point, intersects with a second radius of a closest data point to the new data point in the dimensional data space, defined by a second value of the distance parameter associated with the closest data point;
add the new data point to a second cluster, of the one or more clusters, associated with the closest data point if the first radius intersects with the second radius;
transmit, to a client device, an indication of the one or more clusters;
receive, from the client device, feedback information associated with at least one data point, wherein the feedback information indicates that the at least one data point is not correctly clustered; and
modify a value of the distance parameter associated with the at least one data point, based on the feedback information, to a modified value of the distance parameter.

2. The system of claim 1 , wherein the one or more processors are further configured to:
store, in a data store, the set of data points and the one or more clusters after analyzing the set of data points.

3. The system of claim 1 , wherein the one or more processors are further configured to:
receive, via the data stream, another new data point arranged in the dimensional data space; and
analyze the other new data point and the set of data points to determine if the other new data point is to be included in the first cluster, wherein analyzing the other new data point includes determining whether a distance between the other new data point and any data point in the first cluster satisfies a value of the distance parameter associated with the other new data point.

4. The system of claim 1 , wherein the one or more processors are further configured to:
receive, via the data stream, the new data point; and
identify the closest data point.

5. The system of claim 1 , wherein the one or more processors, to modify the value of the distance parameter associated with the at least one data point, are configured to:
increase the value associated with the distance parameter to obtain the modified value of the distance parameter if the feedback information indicates that the at least one data point should be included in a cluster; or
decrease the value associated with the distance parameter to obtain the modified value of the distance parameter if the feedback information indicates that the at least one data point should not be included in the cluster.

6. The system of claim 1 , wherein the one or more processors are further configured to:
identify an amount of time since a data point has been added to a third cluster of the one or more clusters;
determine if the amount of time satisfies a time threshold; and
remove the third cluster from the dimensional data space if the amount of time satisfies the time threshold, wherein removing the third cluster from the dimensional data space includes clearing the third cluster and any data points associated with the third cluster from the one or more memories.

7. The system of claim 6 , wherein the one or more processors are further configured to:
store, in a data store, the third cluster and any data points associated with the third cluster, based on removing the third cluster from the dimensional data space.

8. The system of claim 1 , wherein the one or more processors, to transmit the indication of the one or more clusters, are configured to:
transmit, to the client device, user interface information to cause information associated with the one or more clusters to be displayed by the client device.

9. A method for variable density-based clustering, comprising:
receiving, by a device and from a data stream, a set of data points arranged in a dimensional data space;
comparing, by the device, the set of data points to identify one or more clusters using values of a distance parameter for data points included in the set of data points, wherein the values of the distance parameter includes different values of the distance parameter for different data points, and wherein comparing the set of data points includes comparing a first data point and a second data point from the set of data points using a first value of the data point associated with the first data point and a second value of the data point associated with the second data point;
determining, by the device, if a first radius of a new data point, arranged in the dimensional data space, and a second radius associated with a closest data point to the new data point, in the dimensional data space, intersect,
wherein the first radius is defined by a first value of the distance parameter associated with the new data point, and
wherein the second radius is defined by a second value of the distance parameter associated with the closest data point;

adding, by the device, the new data point to a second cluster, of the one or more clusters, associated with the closest data point if the first radius and the second radius intersect;
transmitting, by the device and to a client device, an indication of the one or more clusters to cause the client device to display information associated with the one or more clusters;
receiving, by the device and from the client device, feedback information associated with at least one data point, wherein the feedback information indicates that the at least one data point is associated with an error; and
modifying, by the device, a value of the distance parameter associated with the at least one data point to a modified value of the distance parameter, based on the feedback information.

10. The method of claim 9 , further comprising:
receiving, via the data stream, a new data point arranged in the dimensional data space; and
analyzing the new data point and the set of data points to identify if the new data point should be included in a cluster of the one or more clusters, wherein analyzing the new data point includes analyzing the new data point using a value of the distance parameter that is specific to the new data point.

11. The method of claim 9 , further comprising:
receiving, via the data stream, the new data point; and
identifying the closest data point.

12. The method of claim 9 , wherein modifying the distance parameter associated with the at least one data point comprises:
increasing the value associated with the distance parameter to obtain the modified value of the distance parameter if the fe

Assignees

• Capital One Services Llc

Inventors

• Allen Thomas
• Patel Milind
• Howe James

Classifications

• G06F16/906 Primary

  Clustering; Classification · CPC title

• G06F16/287 Primary

  Visualization; Browsing · CPC title

• G06N20/00

  Machine learning · CPC title

• G06F16/24568

  Data stream processing; Continuous queries · CPC title

• G06F18/232

  Non-hierarchical techniques · CPC title