TWI396103B - Method for data clustering - Google Patents

Description

Data grouping method

The present invention relates to a data grouping method, and more particularly to a data grouping method based on a density algorithm.

The conventional density data grouping method mainly uses data point density as the basis for grouping. For example, given a parameter ε (scanning radius) and MinPts (minimum inclusion point), if the data point density of a certain area satisfies the set condition, the expansion search is performed in the area, and the other same density is gradually merged to satisfy the set condition. The region, and finally the final clustering results, representative algorithms include DBSCAN, IDBSCAN or KIDBSCAN. Although the conventional grouping method can effectively detect irregular patterns and filter out noise points, the time required for grouping is relatively increased.

The following is a description of several representative custom density data grouping techniques:

1. DBSCAN data grouping method: Step 1 selects one of the data points in advance as one of the initial seed points by a plurality of data points in the data set; and the second step determines whether the current radius of the initial seed point exceeds the radius MinPts The data points, if the threshold is reached, classify the data points in the current range into the same cluster and serve as seed points, and expand from other seed points in the range; Step 3 continues the foregoing step two until the All data points in the data set 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, etc., but because of the complicated density of each data point. Judging, it is more cumbersome to group.

2. IDBSCAN data grouping method: This method is a density data grouping technique proposed by B. Borah and other scholars in 2004. It mainly focuses on the above-mentioned conventional DBSCAN data grouping method, which is based on the sequential judgment of data points for time-consuming behavior. Improvements were made to adopt a strategy of increasing the speed of grouping 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 the seed point. By reducing the number of seed points, the repeated expansion action can be reduced to overcome the shortcomings of the excessive number of seed points in the DBSCAN data grouping method, but the reduced grouping time is still quite limited. .

In general, the IDBSCAN data grouping method can reduce the number of seed points in an expanded seed point scanning range to no more than 8. However, since the data points close to the expanded seed point cover a large area, if The inclusion of these data points as seed points will increase the time cost of the search. 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.

3, KIDBSCAN data grouping method: KIDBSCAN data grouping method is for the IDBSCAN data grouping method to find the marking boundary point, if the data points read in order from the data set are located in the low density area, it will cause redundant seed points Search for movements that cause poor expansion. In order to reduce the number of sampling times, the KIDBSCAN data grouping method proposes the concept of adding elite points 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 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 data grouping. For the above reasons, it is necessary to further improve the above-described conventional data grouping method.

The present invention provides a data grouping method whose main purpose is to reduce the number of expanded seed points in a data grouping method based on a density algorithm.

A secondary objective of the present invention is to screen for data points that are closer to the expanded core point.

In order to achieve the foregoing object, the technical means and the functions achievable by the technical method include: a data grouping method, wherein the system includes a parameter setting step of setting a scan radius parameter and a minimum inclusion point. a parameter, and one of the data points is read as a diverging core point, and the data points located in the scanning range of the expansion core point are adjacent data points; an expansion query step is searching for the expansion core a data point within the scanning range of the point and defined as a neighboring data point; a noise judging step is to determine whether the number of the neighboring data points is less than the minimum containing point parameter; a boundary point marking step is to scan the expanded core point Setting a plurality of mark boundary points outside the range, and respectively selecting the scanning data points located in the boundary points of the mark points, and the neighboring data points closest to each mark boundary point as the expansion seed points; a screening step is to determine whether there are consecutive numbers The marker boundary points respectively have corresponding expansion seed points. If the determination is "Yes", the consecutive number of labels are deleted. One of the expansion points corresponding to the boundary point, and adding the remaining expanded seed points to a sub-list, and then performing a sub-selection step; if the determination is No, the expanded seed point is added to the seed list. And performing the seed selection step; the seed selection step is performed by using all the expanded seed points in the seed list as the expansion core points, and performing the expansion inquiry step one by one; and a first determining step determining whether all the data points are determined All have been grouped or defined as noise. If the judgment is "No", another data point is read as the expansion core point and the expansion inquiry step is performed; if it is judged as "Yes", it is terminated. Thereby, the present invention can be provided before having high grouping accuracy, effectively reducing the computational cost of the search.

The above and other objects, features and advantages of the present invention will become more <RTIgt; The data grouping method according to the preferred embodiment of the present invention is a computing system in which at least one database is connected by a computer system. The database has a plurality of data points 11 stored therein. The data grouping method of the present invention performs a parameter setting. Step S1, by the computer system setting a scan radius R (Eps) parameter and a minimum inclusion point (Minpts) parameter, and reading one of the data points 11 as an expansion core point 12 from the database. For the convenience of the following description, the term "scanning range" is defined herein as the range covered by scanning with the scanning radius R parameter as a radius.

Referring to Figures 1 and 3, the data grouping method of the preferred embodiment of the present invention performs an expansion query step S2 to search for data points 11 located within the scan range of the expanded core point 12 and define them as neighboring data points. 13. In more detail, in this embodiment, the data point 11 in the database is searched through the computer system, and the data point 11 located in the scanning range of the expanded core point 12 is defined as the neighboring data point 13.

Referring to Figures 1 and 3, the data grouping method of the preferred embodiment of the present invention performs a noise judging step S3 to determine whether the number of adjacent data points 13 is less than the minimum inclusion point parameter. The expansion core point 12 and the adjacent data point 13 are all divided into the same cluster, and a boundary point marking step S4 is performed; if the determination is YES, the expansion core point 12 and the adjacent data point 13 are all identified as miscellaneous. And perform a first determining step S7.

Referring to FIGS. 1 and 4, the boundary point marking step S4 of the data grouping method according to the preferred embodiment of the present invention sets a plurality of marking boundary points 14 outside the scanning range of the expanding core point 12, and then respectively selects each of the marking boundary points. The adjacent data points 13 closest to each of the mark boundary points 14 are within the scanning range of the mark boundary point 14 as the expanded seed point 15, and a screening step S5 is performed after completion. For example, in this embodiment, the extended core point 12 is centered, and the boundary A of the circle is drawn with a radius larger than the boundary radius R′ of the scanning radius R, and preferably is clockwise on the boundary A. The direction is equidistantly set with 8 mark boundary points 14a, 14b, 14c, 14d, 14e, 14f, 14g, 14h' such that any mark boundary point 14 is located outside the scan range of the expanded core point 12, the mark boundary The distance between the point 14 and the expanded core point 12 is greater than the scan radius parameter R and less than twice the scan radius parameter R. Then, scanning is performed by the mark boundary points 14a, 14b, 14c, 14d, 14e, 14f, 14g, 14h. For example, the mark boundary point 14a is first scanned, and among the plurality of adjacent data points 13, A neighboring data point 13 located within the scanning range of the marking boundary point 14a and closest to the marking boundary point 14a is selected as the expanded seed point 15, and the marking boundary points 14b, 14c, 14d, 14e, 14f, 14g, 14h are also The scanning is performed in the same manner, and the corresponding adjacent data points 13 are respectively selected as the expanded seed points 15. As shown in Fig. 4, the mark boundary points 14a, 14b, 14c, 14d, 14f, 14g, 14h have corresponding expanded seed points 15, which are expanded seed points 15a, 15b, 15c, 15d, 15f, 15g, respectively. At 15h, only the marker boundary point 14e has no corresponding expanded seed point 15.

Referring again to FIGS. 1 and 4, in general, the scanning range of the data point 11 near the expanded core point 12 is higher than the scanning range of the expanded core point 12, and since the expanded core point 12 is The number of data points 11 is greater than the minimum inclusion point parameter, so the chance that the data point 11 near the expansion core point 12 is a noise point is generally lower, if the data point 11 closer to the expansion core point 12 is included in the expansion Seed point 15, which will increase the time cost of the search. In the boundary point marking step S4 of the present invention, the marking boundary point 14 is located outside the scanning range of the expanding core point 12, so when the marking boundary points 14 are scanned, the screening can be removed to be closer to the expanding core point. The data point 11 of 12 can effectively reduce the time cost of the search.

Referring to Figures 1, 4 and 5, the screening step S5 of the data grouping method according to the preferred embodiment of the present invention determines whether any consecutive number of marking boundary points 14 on the boundary A have corresponding expanded seed points 15 respectively. If the determination is YES, delete one of the consecutive number of marker boundary points 14 corresponding to the expansion seed point 15, and add the remaining expansion seed point 15 to a sub-list, and then perform a sub-selection step S6; If the determination is "NO", the expanded seed point 15 is added to the seed list, and the seed selection step S6 is performed. More specifically, taking FIG. 4 as an example, the present embodiment selects from the mark boundary point 14a, and successively four consecutive mark boundary points 14a, 14b, 14c, and 14d have corresponding expansion seeds in a clockwise direction. Points 15a, 15b, 15c, 15d are deleted and one of the expanded seed points 15a, 15b, 15c, 15d is deleted. As shown in Fig. 5, among the four expanded seed points 15a, 15b, 15c, 15d, the scanning area of the expanded seed point 15b located in the middle is only scanned by the expanded seed points 15a, 15c. The range is covered; and the scanning range of the other expanded seed point 15c located in the middle is also only the area 152 having a smaller area is not covered by the scanning range of the expanded seed points 15b, 15d. Therefore, if one of the expanded seed points 15b, 15c is deleted, the time cost of the search can be reduced, and a relatively high grouping accuracy can be maintained. This embodiment selects to delete the expanded seed point 15b closest to the first expanded seed point 15a of the successive four expanded seed points 15a, 15b, 15c, 15d.

Referring to Figures 1, 6 and 7, after deleting the expanded seed point 15b, there are still four consecutive mark boundary points 14f, 14g, 14h, 14a respectively having corresponding expanded seed points 15f, 15g, 15h, 15a, therefore, in the same manner, one of the expanded seed points 15g, 15h located in the middle is deleted, since the intermediate expanded seed point 15g is closer to the consecutive four expanded seed points 15f, 15g, 15h, 15a In the first expansion seed point 15f, in this embodiment, the expansion seed point 15g is selected to be deleted. Thus, as shown in Fig. 7, the expanded seed point 15 can be reduced from the original 7 to 5, which can reduce the expansion. The number of seed points 15 . After confirming that there are no consecutive four mark boundary points 14 on the boundary A with corresponding expanded seed points 15, the remaining expanded seed points 15a, 15c, 15d, 15f, 15h are added to the seed list. This seed selection step S6 is performed again. In this way, it is possible to reduce the number of expanded seed points 15 before the high-segment accuracy is maintained, thereby reducing the time cost of subsequent searches.

Referring to Figures 1 and 7, the seed selection step S6 of the data grouping method of the preferred embodiment of the present invention uses the expanded seed points 15 in the seed list as the expansion core points 12, respectively, and performs the expansion one by one. The first determining step S7 is performed by inquiring step S2 until all of the expanded seed points 15 have performed the expansion inquiring step S2 as the expanded core point 12.

Referring to FIGS. 1 and 2, the first determining step S7 of the data grouping method according to the preferred embodiment of the present invention determines whether all the data points 11 have been grouped or defined as noise, and if the determination is "No". Then, a reading step S8 is performed; if the determination is "YES", the processing is terminated. More specifically, if all the data points 11 have been grouped or defined as noise, then the grouping results of the plurality of data points 11 can be obtained.

Referring to FIGS. 1 and 2, the reading step S8 of the data grouping method according to the preferred embodiment of the present invention reads another data point 11 from the data set and performs a second determining step S9.

Referring to FIGS. 1 and 2, the second determining step S9 of the data grouping method according to the preferred embodiment of the present invention determines whether the data point 11 read in the reading step S8 is not grouped, and is not If it is judged as noise, if the determination is YES, the expansion request step S2 is performed using the data point 11 as the expansion core point 12; if the determination is "NO", the reading step S8 is re-executed.

As described above, the data grouping method of the present invention can remove the adjacent data points 13 which are too close to the expansion core point 12 by setting the plurality of mark boundary points 14 outside the scanning range of the expansion core point 12, thereby reducing the subsequent The time cost of the search; furthermore, the present invention removes one of the expanded seed points 15 corresponding to any of the consecutive number of mark boundary points 14 to reduce the number of expanded seed points before maintaining high group accuracy. Reduce the time cost of subsequent searches.

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]

11. . . Data point

12. . . Expansion core point

13. . . Proximity data point

14. . . Mark boundary point

14a to 14b. . . Mark boundary point

15. . . Expanded seed point

15a to 15d. . . Expanded seed point

15f to 15h. . . Expanded seed point

A. . . boundary

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

Figure 2: Schematic diagram of the parameter setting steps of the preferred embodiment of the present invention

Figure 3: Schematic diagram of the expansion query step of the preferred embodiment of the present invention

Figure 4: Schematic diagram of the boundary point marking step of the preferred embodiment of the present invention

Figure 5: Schematic diagram of the screening step of the preferred embodiment of the present invention

Figure 6 is a schematic illustration of the screening steps of a preferred embodiment of the invention

Figure 7 is a schematic view of the preferred embodiment of the present invention to complete the screening step

12. . . Expansion core point

13. . . Proximity data point

14. . . Mark boundary point

14a to 14b. . . Mark boundary point

15. . . Expanded seed point

15a to 15d. . . Expanded seed point

15f to 15h. . . Expanded seed point

Claims (8)

A data grouping method is characterized in that a computer system is connected to at least one database as an execution architecture, comprising: a parameter setting step, setting a scan radius parameter and a minimum inclusion point parameter, and reading one of the plurality of data points The data point serves as an expansion core point, and the data points located in the scanning range of the expansion core point are adjacent data points; an expansion query step searches for data points located within the scanning range of the expansion core point, and is defined as proximity a data point; a noise judging step is to determine whether the number of the neighboring data points is less than the minimum inclusion point parameter. If the determination is "No", the expansion core point and the neighboring data points are all divided into the same cluster, and a boundary is performed. The point marking step, if the determination is "Yes", the expansion core point and the adjacent data points are all identified as noise, and a first determining step is performed; the boundary point marking step is set outside the scanning range of the expanded core point a plurality of mark boundary points, and respectively select the scanning range located at each of the mark boundary points, and are closest to each of the mark boundary points The material point is used as an expansion seed point; a screening step is to determine whether any consecutive label boundary points have corresponding expansion seed points respectively, and if the determination is "Yes", one of the consecutive number of label boundary points is deleted. Expanding the seed point, adding the remaining expanded seed points to a sub-list, and performing a sub-selection step; if the determination is "No", adding the expanded seed point to the seed list, and then performing the seed selection step; The seed selection step is performed by using all the expanded seed points in the seed list as the expansion core points, and performing the expansion query step one by one; and the first determining step determines whether all the data points have been grouped or defined. For the noise, if the judgment is "No", another data point is read as the expansion core point and the expansion inquiry step is performed; if the determination is "Yes", the termination is made. According to the data grouping method described in Item 1 of the patent application scope, in the screening step, it is determined whether any of the four mark boundary points respectively have corresponding expanded seed points. According to the data grouping method described in item 2 of the patent application scope, in the screening step, if the determination is YES, the consecutive four mark boundary points respectively correspond to four consecutive expanded seed points, and the four consecutive expansions are deleted. The seed point is located in the middle of the expanded seed point, and the remaining expanded seed points are added to the seed list, and the seed selection step is performed. According to the data grouping method of claim 1, wherein in the boundary point marking step, the distance between the marking boundary point and the expanding core point is greater than the scanning radius parameter and less than twice the scanning radius parameter. According to the data grouping method described in Item 1 of the patent application scope, the noise inquiry step is performed after the expansion inquiry step is completed. According to the data grouping method described in claim 1, wherein the boundary point marking step is respectively scanning with each marking boundary point, and selecting a vicinity of the scanning boundary of the marking boundary point and closest to the marking boundary point The data point is used as the expansion seed point, and the screening is performed after completion. step. According to the data grouping method of claim 1, wherein in the seed selecting step, after the expansion query step is performed as the expansion core point, the first determining step is performed. According to the data grouping method described in Item 1 of the patent application scope, in the first determining step, if the determination is “No”, after reading another data point, if the other data point is not grouped, and If it is judged as noise, the expansion inquiry step is performed with the other data point as the expansion core point; if the other data point has been grouped, or has been judged as noise, then other data points are read.