DENSITY-BASED DATA CLUSTERING METHOD

• US 20110055212A1
• Filed: 01/06/2010
• Published: 03/03/2011
• Est. Priority Date: 09/01/2009
• Status: Active Grant

• Current Assignee: National Pingtung University of Science and Technology
• Original Assignee: National Pingtung University of Science and Technology
• Inventors: Wu, Chien-Tsung, TSAI, Cheng-Fa
• Granted Patent: US 8,171,025 B2
• Time in Patent Office: Days
• US Class Current: 707/737
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 18/232 Non-hierarchical techniques
• CPC Class Codes: G06F 18/24147 Distances to closest patterns, e.g. nearest neighbour classification

Abstract

A density-based data clustering method, comprising a parameter-setting step for setting a scanning radius and a minimum threshold value, a dividing step for dividing a space of a plurality of data points according to the scanning radius, a data-retrieving step for retrieving one data point out of the plurality of data points as a core data point, a searching step for calculating a distance between the core data point and each of the query points, a grouping determination step for determining whether a number of the neighboring points is smaller than the minimum threshold value.

Claims

1. A density-based data clustering method, comprising:

a parameter-setting step for setting a scanning radius and a minimum threshold value;

a dividing step for dividing a space of a plurality of data points according to the scanning radius to obtain a plurality of grids, wherein the plurality of data points is distributed in the plurality of grids;

a data-retrieving step for retrieving one data point out of the plurality of data points as a core data point, and defining a grid where the core data point is located, as well as grids that surround the grid, as a query range, wherein the data points located in the query range are query points;

a searching step for calculating a distance between the core data point and each of the query points, determining a portion of the query points with the distance to the core data point equal to or smaller than the scanning radius, and defining the portion of the query points as neighboring points;

a grouping determination step for determining whether a number of the neighboring points is smaller than the minimum threshold value, defining the core data point and the neighboring points as noise points and re-performing the data-retrieving step if the number of the neighboring points is smaller than the minimum threshold value, and defining the core data point and the neighboring points as a cluster and performing a first determination step if the number of the neighboring points is not smaller than the minimum threshold value,

wherein the first determination step determines whether the cluster overlaps with other clusters, performs a second determination step if the cluster overlaps with other clusters, and defining the cluster as a new cluster and re-performs the data-retrieving step if the cluster does not overlap with other clusters,

wherein the second determination step determines the data points located within an overlapped area of the clusters as cross core points, determines whether a number of the data points located within a searching range radially extended from any of the cross core points with a radius of the scanning radius is smaller than the minimum threshold value, re-performs the data-retrieving step if the number of the data points located within the searching range is smaller than the minimum threshold value, merges the overlapped clusters into the same cluster and performs a termination determination step if the number of the data points located within the searching range is not smaller than the minimum threshold value,

wherein the termination determination step determines whether all of the data points are clustered or defined as noise points, terminates the density-based data clustering method if all of the data points are clustered or defined as noise points, and re-performs the data-retrieving step if not all of the data points are clustered or defined as noise points.

2. The density-based data clustering method as claimed in claim 1, wherein the second determination step further comprises:

calculating a distance between the cross core point and each of the query points located within a query range of the cross core point; and

defining the portion of the query points with the distance to the cross core point equal to or smaller than the scanning radius as neighboring points.

3. The density-based data clustering method as claimed in claim 1, wherein the size of the divided grids is the scanning radius.