TWI402701B - Method for density-based data clustering - Google Patents

Description

Density-based data grouping method

The invention relates to a data grouping method, in particular to a density based data grouping method.

Data Mining mainly provides users with the useful information hidden in the original data to find the features and relationships implied between the data in a large data set to establish a complete data analysis model. In this way, it can be applied to various fields such as business transaction behavior analysis, spatial data analysis, file management and network intrusion behavior analysis to effectively explore hidden and useful information, and provide reference for decision makers. In addition, the data grouping technology in data exploration allows users to quickly know the correlation between the nature of the data, such as customer purchase behavior, age market segmentation and so on. Data grouping refers to the classification of data with high similarity into their respective groups based on some custom dimensional characteristics in the original database.

However, as services become more diverse and there are more hidden messages that must be captured, today's data-sorting technologies are beginning to trend toward the ability to easily process extremely large amounts of data as a significant factor in assessing performance. The following is a description of several representative data clustering methods:

1. K-means data grouping method: Step 1 pre-randomly selects k data points (that is, the number of data clusters generated after grouping operations), and sets the k data points as the initial centroids of k data clusters. Point; step 2 is to calculate the distance between each data point x according to each initial centroid point, that is, to find the closest initial centroid point for each data point x, and add each data point x to the nearest one. The initial centroid point is used for grouping action; the third step is to recalculate the preferred centroid point from the current data point x distribution; finally, repeat steps 2 and 3 until the centroids of all data clusters are When there is no longer any change, the data grouping operation is terminated.

However, although the conventional K-means data grouping method is quite fast, the clustering results are not stable at all because of the initial selection of the initial centroid points, and in the process of step two. Only simple distance judgment is used, which results in poor grouping results.

2, DBSCAN data grouping method: Step 1 is to select one of the data points as the initial seed point in advance by several data points in a data set; Step 2 is to determine whether the current radius of the initial seed point exceeds the radius MinPts If the threshold is reached, the data points in the current range are classified into the same cluster and used as seed points, and expanded from other seed points in the range; Step 3 continues the foregoing step 2 until the data All the data points in the collection are classified. The conventional DBSCAN data grouping method is grouped in a more logical density judgment manner, so it can be used to filter out noise and data points suitable for irregular patterns.

However, the above-mentioned conventional DBSCAN data grouping method is complicated because of the complicated expansion and density judgment of each data point.

3, IDBSCAN data grouping method: mainly for the above-mentioned conventional DBSCAN data grouping method is to gradually judge the data points to spread and time-consuming behavior improvement, and adopt the strategy of improving the grouping speed by reducing the number of queries. The conventional IDBSCAN data grouping method is to set eight mark boundary points equidistantly on the scan range boundary of the expanded seed point radius ε, and the data points in the scan range of the expanded seed point radius ε are only selected closest to the eight mark boundaries. The data point of the point is used as a seed point, so that the number of seed points can be reduced, and the repeated expansion action can be reduced to overcome the shortcoming of the excessive number of seed points in the conventional DBSCAN data grouping method.

However, the above-mentioned conventional IDBSCAN data grouping method has a large coverage area of data points close to the expanded seed point, and if these data points are included as seed points, the time cost of searching is increased. Moreover, even if the number of seed points in the scanning range of the expanded seed is not more than 8, the adjacent seed points have a higher overlapping ratio of scanning ranges, and the proportion of repeated expansion is also relatively high, thereby increasing the time cost.

4. KIDBSCAN data grouping method: mainly for the above-mentioned known IDBSCAN data grouping method, when searching for the boundary point of the mark, if the data points read in from the data set are located in the low-density area, the redundant seed point search will be caused. The action that caused the poor expansion. In order to reduce the number of sampling times, the conventional KIDBSCAN data grouping method proposes the concept of adding an elite point for expansion. The three parameters to be set are: elite point (K), radius (ε) and minimum inclusion point (MinPts). The execution steps are as follows: (1) Firstly use the K-means algorithm to find the K center of gravity points in the data set, and then find the K data points closest to these center of gravity points to define it as the elite point; (2) K The elite points are moved to the forefront of the data set; (3) the IDBSCAN data grouping method is implemented. This speeds up the grouping of data, but the grouping time that can be reduced is still quite limited.

5. NPUST data grouping method: mainly for the above-mentioned conventional DBSCAN, IDBSCAN and KIDBSCAN data grouping methods, when each data point is expanded, it is necessary to expand the query of all data points in the data set, which will result in poor expansion. . In order to reduce the number of expansion queries, the conventional NPUST data grouping method proposes the concept of expansion using the conventional K-means and IDBSCAN data grouping methods; the three parameters to be set are: group number (K), radius (ε) and Minimum inclusion point (MinPts). The execution steps are as follows: (1) Firstly, the data set distribution space is cut into K subspaces by using the conventional K-means data grouping method; (2) using the conventional IDBSCAN data grouping method to perform grouping in K subspaces respectively. When performing the expansion query, the scanning range of the conventional IDBSCAN data grouping method is limited to the subspace of itself; (3) defining the boundary points of each cluster, and calculating the distance between any two boundary points, the closest boundary of the distance The clusters to which the points belong are merged into a group, and the merge is repeated until the total number of clusters reaches the set number of groups (K), that is, the grouping action is completed, so that the expansion query of all the data points by the conventional IDBSCAN data grouping method can be reduced. Speed up the speed of grouping.

However, the number of groups (K) of the above-mentioned conventional NPUST data grouping method must be determined according to the number of clusters included in the data set. If the number of groups (K) is set to be larger, the smaller each subspace after cutting is performed, that is, The scope of the expansion inquiry is relatively small, and the execution efficiency will naturally increase. However, when the number of clusters of the unknown data set is set, if the number of groups (K) is too different from the number of clusters of the data set, an incorrect clustering result will result.

For the above reasons, it is necessary to further improve the above-described conventional data grouping method.

The object of the present invention is to improve the above disadvantages to provide a density-based data grouping method for limiting the search of data points to data points within a query range.

The object of the present invention is to provide a density-based data grouping method, which has the ability to improve grouping efficiency.

In order to achieve the foregoing object, the technical content of the present invention is as follows: a density-based data grouping method includes a setting step of setting a scan radius parameter, a minimum inclusion point parameter, and a sub-list; a cutting step, According to the scanning radius parameter, the distribution space of the data set having several data points is cut to obtain a plurality of meshes, so that the data points are distributed in the meshes; and a reading step is performed in the data set Reading a data point as a core point; an expansion query step is to define the grid where the core point is located and the surrounding adjacent grid as a query range, and the data points located in the query range are defined as query points, and respectively calculate this The distance between the core point and the query points defines a query point whose distance is less than or equal to the scan radius parameter as a neighboring point; a group judgment step determines whether the number of the neighboring points is less than the minimum included point parameter, If the judgment is "No", the core point and the neighboring point are regarded as the same cluster, and a boundary marking step is performed. If the judgment is "Yes" The core point and the neighboring point are regarded as noise, and a first determining step is performed; the boundary marking step marks a plurality of boundary marks on the boundary of the scan range of the core point, and the closest to the boundary marks is The neighboring point is added to the seed list, and the seed list is read as a core point, and the expansion query step is re-executed; the first determining step determines whether the seed in the seed list completes the expansion query step. If the determination is "Yes", a termination determination step is performed. If the determination is "No", then one of the seed lists is read as a core point, and the expansion inquiry step is performed again; and the termination determination step is determined. Whether all the data points have been grouped or regarded as noise, if it is judged as "Yes", it will terminate. If the judgment is "No", the reading step will be repeated.

The above and other objects, features and advantages of the present invention will become more <RTIgt; Preferably, the density-based data grouping method according to the preferred embodiment of the present invention connects at least one database as an execution architecture by using a computer system, and the data library has a data set 1 stored in the database. The density data grouping method of the present invention comprises a setting step S1, a cutting step S2, a reading step S3, an expansion query step S4, a grouping determining step S5, A boundary marking step S6, a first determining step S7 and a termination determining step S8. Through the above steps, the data grouping operation can be completed quickly and correctly.

Referring to FIG. 1 and FIG. 2, a setting step S1 of the density-based data grouping method according to the preferred embodiment of the present invention is used to set a scan radius (Eps) parameter R and a minimum inclusion point (Minpts) in the computer system. ) parameters and a sublist. More specifically, the scan radius parameter R and the minimum inclusion point parameter are in a proportional relationship. When the value of the scan radius parameter R is set larger, the value of the minimum inclusion point parameter is also set to be larger, and vice versa. The smaller the value of the scan radius parameter R is set, the smaller the value of the minimum included point parameter is, so as to improve the correct rate of data grouping. In addition, for convenience of the following description, the term "scanning range S" is defined herein as the range covered by scanning with the scanning radius parameter R as the center centering on any of the data points 11 of the data set 1.

Referring to FIG. 1 and FIG. 3, the cutting step S2 of the density-based data grouping method according to the preferred embodiment of the present invention cuts the distribution space having the plurality of data points 11 according to the scanning radius parameter R. Obtaining a plurality of grids 2, the data points 11 are distributed in the grids 2, and the scanning radius parameter R represents the size of the grid 2; for example, a two-dimensional plane coordinate is taken as an example for illustration. The plurality of data points 11 are all distributed in a two-dimensional plane space. Therefore, each data point 11 corresponds to a two-dimensional plane coordinate (X, Y), and the cutting step S2 is for each data point 11 for each dimension. The coordinates (X coordinate or Y coordinate) are used to find the maximum value of the coordinate, and calculate the number of meshes that the dimension is cut as shown in the following formula (1):

Where G _{i is} the number of grids of the i dimension, C _{i-Max is} the maximum value of the i coordinate, and i=X, Y, Z, etc., R is the scan radius parameter, and S represents a constant term. Equation (2) as described below indicates:

More specifically, in the two-dimensional plane coordinates, i is X and Y, meaning that G _X represents the number of grids in the X dimension, G _Y represents the number of grids in the Y dimension, and C _X-Max is the maximum value of the X coordinate. , C _Y-Max is the maximum value of the Y coordinate, and the maximum values C _X-Max and C _{Y-Max are respectively} divided by the scanning radius parameter R, and the obtained "quotient" is obtained by "Gaussian symbol []" An integer indicates that if divisible, the resulting "quotient" is the number of grids in the X or Y dimension, and the constant term S is not added; if it is not divisible, the resulting "quotient" is added to the constant term. S is the number of grids in the X or Y dimension. Thereby, after the distribution space of the data point 11 is cut, the obtained plurality of meshes 2 are equal in size, and all the data points 11 in the data set 1 are located in the meshes 2.

Referring to FIGS. 1 and 3, the reading step S3 of the density-based data grouping method according to the preferred embodiment of the present invention reads one of the data points 11 as the core point 12 from the data set 1, and The expansion inquiry step S4 is performed.

Referring to Figures 1, 4 and 5, the expansion query step S4 of the density-based data grouping method according to the preferred embodiment of the present invention defines the grid 2a and the number of adjacent grids 2b of the core point 12 as A query range, and the data point 11 located in the query range is defined as the query point 13 (as shown in FIG. 4), and the distance between the core point 12 and the query points 13 is calculated respectively, and the distance is less than or equal to The query point 13 of the scan radius parameter R is defined as the neighboring point 14 (as shown in Figure 5).

Referring to FIG. 4 again, for example, in the case of a grid-like distribution, the definition of the query range is as follows: First, the grid 2a of the core point 12 can be explicitly Find 8 adjacent grids 2b; second, the grid 2a' where the core points 12' are located can clearly find 3 adjacent grids 2b'; third, the grid 2a of the core points 12" can be clear Find 5 adjacent meshes 2b"; more specifically, the "query range" defined by the present invention is the range covered by the mesh 2a of the core point 12 and the adjacent meshes 2b; The core point 12 only needs to calculate the distance for the query point 13 in the query range to reduce the number of times the core point 12 calculates the distance from all the data points 11, thereby saving the time cost of searching for a large number of data points 11 in the data set 1. .

Referring to FIG. 1 and FIG. 5, the grouping judging step S5 of the density-based data grouping method according to the preferred embodiment of the present invention determines whether the number of the neighboring points 14 is less than the minimum inclusion point parameter, and if it is determined to be If no, the core point 12 and the neighboring points 14 are regarded as the same cluster, and a boundary marking step S6 is performed; if the determination is YES, the core point 12 and the neighboring points 14 are regarded as The noise is transmitted, and a first judgment step S7 is performed.

Referring to FIGS. 1 and 6, the boundary labeling step S6 of the density-based data grouping method according to the preferred embodiment of the present invention is performed on the boundary of the scanning range S of the core point 12 of the cluster obtained in the grouping determining step S5. Marking a plurality of boundary marks 3, in the scan range S of the core point 12, adding the neighboring points 14 closest to the boundary marks 3 to the seed list as a seed, and then reading a sub-category as a core from the seed list Point 12, and repeat the expansion query step S4; for example, the embodiment is on the scan range S boundary of the core point 12 of the cluster, and 8 boundary marks 3a, 3b are arranged in a clockwise direction in an equidistant manner. 3c, 3d, 3e, 3f, 3g, and 3h; then, calculate the boundary marks 3a, 3b, 3c, 3d, 3e, 3f, 3g, and 3h and all adjacent points in the scan range S of the core point 12, respectively. The distance between 14 is added to the seed list by adjacent points 14a, 14b, 14c, 14d, 14e, 14f and 14g which are closest to the boundary marks 3a, 3b, 3c, 3d, 3e, 3f, 3g and 3h, respectively. As a seed; in addition, please refer to Figure 6, if there are two 3 marks the boundary (as shown in FIG. 6 is a two boundary marks 3f and 3g) of the nearest adjacent points corresponding to the same line 14f, 14f adjacent points than the only added to the list of primary seeds.

Referring to FIG. 7, in general, the scan range S' of the adjacent point 14 near the core point 12 overlaps with the scan range S of the core point 12, and the scan range S of the core point 12 is also The number of data points 11 in the data point is greater than or equal to the minimum inclusion point parameter. Therefore, the probability that the data point 11 in the scanning range S' of the neighboring point 14 near the core point 12 is regarded as noise is generally low, if it is to be close The neighboring point 14 of the core point 12 joins the seed list as a seed, which increases the time cost of execution. However, the scanning range S'' of the neighboring point 14a and the scanning range S of the core point 12 overlap to a lower ratio; therefore, referring to FIG. 6, the boundary marking step S6 of the present invention only selects the closest one at a time. A neighboring point 14 of the boundary mark 3 is added to the seed list as a seed, and the neighboring point 14 closer to the core point 12 can be selected and removed, so that the cluster can be effectively improved while maintaining high group accuracy. The efficiency of the work.

Referring to FIGS. 1 and 2, the first determining step S7 of the density-based data grouping method according to the preferred embodiment of the present invention determines whether the seed in the seed list has completed the expansion query step S4. If the determination is YES, a termination determination step S8 is performed; if the determination is "NO", another seed is read from the seed list as the core point 12, and the expansion inquiry step S4 is performed again; more specifically, The seed in the seed list is deleted from the seed list after performing the expansion query step S4. However, in the boundary point marking step S6, the number of data points 11 continues to be added to the seed list. Therefore, the seed list is continuously The data point 11 is deleted or added until the seed list has no seeds to perform the expansion inquiry step S4, that is, a cluster diffusion operation is completed, and the termination determination step S8 is performed.

Referring to FIG. 1 and FIG. 2, the termination determining step S8 of the density-based data grouping method according to the preferred embodiment of the present invention determines whether all the data points 11 have been grouped or regarded as noise, and if it is determined to be If "Yes", the termination is completed, that is, the grouping operation of the entire data set 1 is completed; if the determination is "NO", the reading step S3 is re-executed.

In addition, as shown in FIG. 8, a cluster C is obtained in the expansion query step S4 and the cluster determination step S5, and the neighboring points 14 of the cluster C are added to the seed list by using the boundary labeling step S6. And the seed list is read as a core point 12, in the case of performing the expansion query step S4 and the grouping determining step S5, if the neighboring point in the scanning range S of the core point 12 is determined in the grouping determining step S5 When the number of 14 is less than the minimum inclusion point parameter, then all the neighboring points 14 in the scanning range S of the core point 12 and the core point 12 are regarded as noise. However, the scan range S of the core point 12 overlaps with the cluster C such that the scan range S of the core point 12 and the cluster C have a number of intersections 11a, since all neighbors 14 of the cluster C have been viewed For the same cluster, therefore, when all the neighboring points 14 in the scanning range S of the core point 12 are regarded as noise, the number of intersections 11a of the overlapping area of the cluster C and the scanning range S of the core point 12 is still regarded as Belongs to the cluster C.

In order to verify that the data grouping method of the present invention has the advantage of high grouping efficiency, the data sets A to F are grouped and compared with the conventional K-means, DBSCAN, IDBSCAN, KIDBSCAN and NPUST data grouping methods. Among them, data sets A to F have 575,000 data points and contain 75,000 noise points. Among them, the data sets A to F are different, and the correct number of clusters included are 10, 5, 2, 4, 4 and 4; in addition, the equipment used in this experiment simulation includes CPU [Intel Pentium D3 .4GHz], memory [2GB], and Java as the implementation language of the algorithm; in addition, this experiment simulates the parameters set for different data sets as shown in Table 1, each data set A to F After the experiment was performed for 30 times, the average value was as shown in Table 2.

Referring to Table 2, comparing the conventional data grouping method with the density-based data grouping method simulation result of the present invention, it can be known that the density-based data grouping method of the present invention can maintain a relatively high group correcting rate. Under the premise of noise filtering rate, the cost of execution time is greatly reduced, and it can be verified that the data grouping method of the present invention does have a good grouping effect.

The density-based data grouping method of the present invention divides the distribution space of the data points into a grid shape, and distributes the data points in the grids, and the grid and the surrounding area of the core points The proximity grid defines the scope of the query, and defines a number of query points within the scope of the query to limit the search of the data points to the power of the query points within the scope of the query.

The density-based data grouping method of the present invention is to limit the search of the data points to the query points in the query range, and only needs to calculate the distance between the core points and the query points to define the neighboring points. In order to facilitate the judging whether to group or treat the noise in the group judging step, the density-based data grouping method of the present invention has the effect of improving the grouping efficiency.

While the invention has been described in connection with the preferred embodiments described above, it is not intended to limit the scope of the invention. The technical scope of the invention is protected, and therefore the scope of the invention is defined by the scope of the appended claims.

[this invention]

1. . . Data set

11. . . Data point

12. . . Core point

12’. . . Core point

12’’. . . Core point

13. . . Query point

14. . . Adjacent point

14a to 14g. . . Adjacent point

2. . . grid

2a. . . grid

2a’. . . grid

2a’’. . . grid

2b. . . Adjacent grid

2b’. . . Adjacent grid

2b’’. . . Adjacent grid

3. . . Boundary mark

3a to 3h. . . Boundary mark

C. . . Cluster

S. . . Scanning range

S’. . . Scanning range

S’’. . . Scanning range

Figure 1 is a flow chart of a data grouping method in accordance with a preferred embodiment of the present invention.

Figure 2 is a schematic illustration of the scanning range of a preferred embodiment of the invention.

Figure 3 is a schematic illustration of the cutting steps of a preferred embodiment of the invention.

Figure 4 is a schematic illustration of the steps of the expansion query in accordance with a preferred embodiment of the present invention.

Figure 5 is a schematic illustration of the steps of the expansion query in accordance with a preferred embodiment of the present invention.

Figure 6 is a schematic illustration of the boundary marking steps of a preferred embodiment of the invention.

Figure 7 is a schematic illustration of the boundary marking steps of a preferred embodiment of the invention.

Figure 8 is a schematic diagram showing the steps of grouping judging in accordance with a preferred embodiment of the present invention.

Claims (4)

A density-based data grouping method includes: a setting step of setting a scan radius parameter, a minimum inclusion point parameter, and a sub-list; and a cutting step, the data having a plurality of data points according to the scan radius parameter The set distribution space is cut to obtain a plurality of grids, so that the data points are distributed in the grids; a reading step, reading a data point as a core point in the data set; and an expansion query step, The grid of the core point and the number of adjacent grids are defined as a query range, and the data points located in the query range are defined as query points, and the distance between the core points and the query points is calculated separately, and the distance is determined. A query point less than or equal to the scan radius parameter is defined as a neighboring point; a group judging step is to determine whether the number of the neighboring points is less than the minimum inclusion point parameter, and if the determination is "No", the core point and the neighboring point are The point is regarded as the same cluster, and a boundary marking step is performed. If the determination is yes, the core point and the neighboring point are regarded as noises, and a first judgment is made. The boundary marking step is centered on the core point, and the boundary points of the range covered by the scan radius parameter are marked with a plurality of boundary marks, and the neighboring points closest to the boundary marks are added to the seed list. And reading, by the seed list, a child as a core point, and performing the expansion inquiry step again; the first determining step is to determine whether the seed in the seed list is finished In the expansion inquiry step, if the determination is YES, a termination determination step is performed, and if the determination is "NO", a sub-sub-read is read from the seed list as a core point, and the expansion inquiry step is performed again; The termination judgment step determines whether all the data points have been grouped or regarded as noise. If the determination is "Yes", the process is terminated. If the determination is "No", the reading step is repeated. The density-based data grouping method according to claim 1, wherein the cutting step finds a maximum value of coordinates of each dimension in the distribution space, and calculates the dimension according to the formula described below. Number of grids being cut: Where G _{i is} the number of grids of the i dimension, and S represents a constant term, as expressed by the formula described below: In the above formula, C _{i-Max is} the maximum value of the i coordinate, and R is the scan radius parameter. According to the density-based data grouping method according to Item 1 or 2 of the patent application, wherein the adjacent points corresponding to the two or more boundary marks in the boundary marking step are the same, only the neighboring points are added to the Seed list once. The density-based data grouping method according to claim 1 or 2, wherein the first determining step reads a list from the seed list After the seed performs the expansion query step as a core point, the seed is removed from the seed list.