Clustering processor

Description: TECHNICAL FIELD [Detailed description of the invention]

【0001】

[Industrial application field]

The present invention relates to a clustering processing device that generates clusters according to the distribution of a data group, and relates to a clustering processing device that automatically sets an initial cluster spread width at the time of clustering.

【0002】

[Conventional technology]

In a system that acquires information processing operations from the obtained cases (data), the input data covers a very wide range and the amount is large compared to the amount of data that can be acquired. Here, if the input data is classified and the data is acquired in the classified state, the amount of acquired data can be reduced. As described above, there is clustering as a method of classifying the input data. Clustering is the merging of similar input data into several groups, or clusters. Classification by clustering is performed by measuring and quantifying the degree of similarity of each data forming a set, and collecting data having a high degree of similarity in the same group (cluster).

【0003】

FIG. 6 is a configuration diagram showing a configuration of a conventional clustering processing device, which is a device for clustering input data as described above. In the figure, 1 is a data input unit, 2 is a cluster generation determination unit that determines whether or not to generate a new cluster for the input data, 3 is a cluster generation unit that newly generates a cluster of input data, and 4 is a cluster generation unit. A cluster control unit that adjusts clusters based on input data, 5 is a cluster fusion judgment unit that determines whether or not multiple clusters should be merged based on input data, and 6 is a cluster fusion that fuses multiple clusters. It is a department. Further, reference numeral 7 denotes a storage unit for storing parameters and clustering information required when a cluster is newly generated or when the clusters are adjusted or fused, and is composed of a clustering parameter storage unit 8 and a clustering information storage unit 9. Will be done.

【0004】

FIG. 7 is an explanatory diagram showing a processing status in such a clustering processing apparatus. For example, when the input data group up to a certain point in time is in the situation shown in FIG. 7 (a), the clustering result is shown in FIG. 7. It is done as shown in (c). After that, as the characteristics of the input data group gradually change to the situation shown in Fig. 7 (b) with the passage of time, the clusters in Fig. 7 (c) are adjusted and fused, or Fig. 7 (c). A new cluster is created in the cluster of, and as a result, clustering is performed as shown in Fig. 7 (e). That is, this apparatus generates clusters corresponding to input data groups that increase with time, and can generate, adjust, and fuse clusters according to sequentially input data.

【0005】

In the clustering processing apparatus shown in FIG. 6, first, the data (signal) input via the data input unit 1 is either newly generated by the cluster generation determination unit 2 or attributed to a cluster that has already been generated. Is determined. In general, there are the Euclidean distance shown in Eq. (1) and the Mahalanobis distance shown in Eq. (2) as a ruler for calculating the degree of attribution of the input data to each cluster.

【0006】

[Number 1]

<img file="JPH06274635A_D0001.tif" />【0007】

[Number 2]

<img file="JPH06274635A_D0002.tif" />【0008】

Here, in equation (2), σx² , σy² Indicates the variance value, which is represented by equations (3) and (4), respectively. Note that n is the number of data and μ is the average value.

【0009】

[Number 3]

<img file="JPH06274635A_D0003.tif" />【0010】

[Number 4]

<img file="JPH06274635A_D0004.tif" />【0011】

This Mahalanobis distance is used when obtaining a normal distribution used in probability or statistics, and therefore the calculation is complicated and the calculation time becomes long. Therefore, it is not suitable for online processing that requires rapid processing. Since this clustering processing device enables online processing, when calculating the degree of attribution of the input signal to the cluster, the calculation time is shortened and the memory capacity is increased by using the Euclidean distance of only four arithmetic operations. I try to suppress it.

【0012】

Here, as the distribution for defining the degree of attribution of the input data to each cluster, the distribution of triangles, which is often used as a membership function of fuzzy control, is used. As shown in FIG. 8, the one-dimensional triangular distribution has the spread α of the distribution as a parameter, and the position of the center coordinate μ is defined as the degree of attribution 1. In the case of multiple dimensions, the same distribution is given independently in each axial direction. Next, the outline of the one-dimensional clustering processing algorithm will be described using the triangular distribution shown in FIG.

【0013】

In the above triangular distribution, the region of the cluster that has already been generated is defined as, and the region around it is divided into each region. Here, X is the input data, μ is the center position of the cluster, and α is the spread from the center of the cluster. K1 is a parameter related to the expansion range of the cluster, and K2 is a parameter related to the expansion range of the cluster, which are stored in the clustering parameter storage unit 8 (FIG. 6). If the data X input in the data input unit 1 corresponds to the range of the area, a new cluster is generated in the cluster generation unit 3. If the input data X falls within the range of the area, the cluster control unit 4 performs expansion processing for the expansion of the cluster. Also, if the input data X falls within the range of the area, the cluster spread is not changed. If the input data X falls within the range of the area (central part of the cluster), the cluster adjustment unit 4 performs reduction processing for the expansion of the cluster. If the input data X corresponds to the range of the area ~, the center position of the cluster is also changed.

【0014】

Next, the cluster generation algorithm in the cluster generation unit 3 will be described. As described above, when the data X input in the data input unit 1 corresponds to the range of the area and there is no cluster to which the data X belongs, or when the cluster has not been generated yet, the input data is set as the center position μ. A cluster having an attribution distribution as shown in FIG. 9 is generated and stored in the clustering information storage unit 9. In this case, the degree of attribution F (x) is given by Eq. (5), and its maximum value is "1". Note that α is a parameter indicating the initial spread of the cluster, and is stored in the clustering parameter storage unit 8.

【0015】

[Number 5]

<img file="JPH06274635A_D0005.tif" />【0016】

Next, the adjustment algorithm in the cluster adjustment unit 4 will be described with reference to FIG. As shown in FIG. 10 (a), when the input data X corresponds to the range of the area, the cluster adjustment unit 4 expands and adjusts the cluster expansion as shown in FIG. 10 (b). Is done. In this case, the cluster control unit 4 first calculates the cluster spread α new based on Eq. (6).

【0017】

[Number 6]

<img file="JPH06274635A_D0006.tif" />【0018】

Next, the new center position μnew of the expanded cluster is calculated based on the equations (7) and (8), respectively, and the result is stored in the clustering information storage unit 9 as clustering information.

【0019】

[Number 7]

<img file="JPH06274635A_D0007.tif" />【0020】

[Number 8]

<img file="JPH06274635A_D0008.tif" />【0021】

Next, FIGS. 10 (c) and 10 (d) are diagrams showing the reduction adjustment of the cluster. As described above, when the input data X corresponds to the range of the area (central part of the cluster), the cluster adjustment unit 4 adjusts the reduction of the cluster as shown in FIG. 10 (d). First, the center position μnew is calculated based on Eq. (9). Note that Cold in Eq. (9) indicates the number of data input to the clusters up to this time, and n indicates the reciprocal of the number of clusters to which the input data X should belong.

【0022】

[Number 9]

<img file="JPH06274635A_D0009.tif" />【0023】

Next, assuming that the parameter related to reduction stored in the clustering parameter storage unit 8 is K3, the cluster spread α new is calculated based on Eq. (10).

【0024】

[Number 10]

<img file="JPH06274635A_D0010.tif" />【0025】

When the input data X corresponds to the range of the area, the spread of the cluster is not changed, and only the center position is changed based on the equation (9). Next, the fusion algorithm in the cluster fusion unit 6 will be described. There are multiple clusters to be attributed, each cluster is paired, and the minimum attribution degree of the intersection on each axis of the common part of each pair is set as the attribution degree of each cluster pair, and the maximum attribution degree is a preset threshold value. When the cluster fusion determination unit 5 determines that the TH has been exceeded, the cluster fusion unit 6 fuses the cluster pairs selected by the following algorithm. That is, in this case, the cluster spread is redefined so that the new cluster spread α new can include all the original cluster spread α old. However, since the cluster area will continue to expand as it is, the number of data N (new) is calculated based on the following equation (11), assuming that the end of the cluster is not so important. Furthermore, based on equations (12) and (13), the center position μ (new) and the cluster spread α (new) are calculated independently for each axis.

【0026】

[Number 11]

<img file="JPH06274635A_D0011.tif" />【0027】

[Number 12]

<img file="JPH06274635A_D0012.tif" />【0028】

[Number 13]

<img file="JPH06274635A_D0013.tif" />【0029】

FIG. 11 is a diagram showing a situation when two clusters A and B are fused. That is, as shown in Fig. (A), the input data X is in the range of the common area of the clusters A and B, and the minimum attribution of the intersections on each axis of this common area exceeds the threshold value TH. If it is determined that the clusters A and B are fused, they are generated as cluster C as shown in FIG. 11 (b). In this case, assuming that the number of data in clusters A and B is NA and NB, the number of data NC in the fused cluster C is calculated based on the equation (14).

【0030】

[Number 14]

<img file="JPH06274635A_D0014.tif" />【0031】

Further, the center position μC and the spread αC of the fused cluster C are calculated based on the equations (15) and (16), respectively.

【0032】

[Number 15]

<img file="JPH06274635A_D0015.tif" />【0033】

[Number 16]

<img file="JPH06274635A_D0016.tif" />【0034】

Even if the input data X is within the range of the common area of the clusters A and B, the minimum attribution of the intersections on each axis of the common area exceeds the threshold value TH as shown in FIG. 11 (c). If not, clusters A and B will not be merged.

【0035】

Here, an example in which this clustering processing apparatus is made to correspond to a color image processing apparatus is shown below. The color image processing device converts the RGB signal obtained from a color video camera or the like that is capturing the image into the Irg space, and the input data of the color image is a vector represented by r and g on the rg plane in this space. It is formed as a distribution of. The Irg space consists of the intensity I, which is the sum of the signals R, G, and B, r, which is the R (red) signal divided by the intensity I, and g, which is the G (green) signal divided by the intensity I. It is a thing. A certain image is obtained by clustering the distribution of the color data of the reference input image formed on the rg plane, which is obtained by this color image processing device, as shown in FIG. 12 by the clustering processing device to form a reference cluster. It is possible to judge whether it is the same as the reference image.

【0036】

That is, first, the reference image is captured by the camera, and the distribution of the reference image data converted by the color image processing apparatus is clustered by the clustering processing apparatus and set as the reference cluster. Next, when the image to be recognized is captured by the camera, the distribution state of the recognized image data converted by the color image processing device matches the reference image of the image to be recognized depending on how much it matches the reference cluster. The degree can be calculated.

【0037】

[Problems to be Solved by the Invention]

Conventionally, since it was configured as described above, there were the following problems. First, when clustering the distribution of the data of the reference image obtained by the color image processing apparatus described above, a human being looks at the distribution of this data and determines the initial value α of the spread width of the cluster. There was a problem that it was necessary. Then, when the dimension of the data to be clustered exceeds 4, it is almost impossible for a human to determine the initial value α of the spread width of the cluster.

【0038】

In addition, the spread of the generated cluster is one parameter (α, α)._new ), Since the initial cluster was square, there was a problem that an appropriate initial cluster was not given depending on the distribution of the data group to be clustered. For example, when the distribution of the data of the reference image obtained by the color image processing device is as shown in FIG. 12 (a), all the distribution states are approximately uniformly distributed in the r direction and the g direction on the rg plane. Therefore, there is not much problem even if the initial cluster is square. However, when the distribution of the reference image data obtained by the color image processing device is as shown in FIG. 12 (b), the state of all the distributions of the reference image data is in the r-axis direction. Since it is spread out, if the initial cluster is square, there is a problem that it takes time to generate a cluster suitable for this distribution state.

【0039】

Further, in the past, since the initial cluster was a square, in the data of the color image processing apparatus described above, the values in the horizontal axis direction and the vertical axis direction of the plane showing the distribution, that is, the values in each dimension indicating the data to be input. Needed to be normalized.

【0040】

The present invention has been made to solve the above problems, and an object of the present invention is to enable an initial cluster to be automatically generated according to the distribution of input data.

【0041】

[Means for solving problems]

The clustering processing apparatus of the present invention sequentially arbitrarily extracts three or more data from a clustering data group, calculates the absolute value of the difference between the extracted data and the data to be extracted next to this data, and calculates the absolute value of the difference. Has an initial cluster spread determination means that arranges the data in the order in which they should descend, calculates the absolute value of his difference in this order, and determines the size of the newly generated cluster using the maximum value among the calculated values. It is characterized by that.

【0042】

[Action]

When a new cluster is generated from the obtained data, the size of this cluster matches the state of the distribution of the clustering data group.

【0043】

[Example]

Hereinafter, one embodiment of the present invention will be described with reference to the drawings. FIG. 1 is a configuration diagram showing a configuration of a clustering processing apparatus of the present invention. In the figure, 10 automatically determines the spread width of the initial cluster generated when the cluster to which the data input in the data input unit 1 belongs does not exist or when the cluster has not been generated yet, depending on the state of the input data. It is the initial cluster spread width determination part determined in, and the others are the same as in Fig. 6.

【0044】

Next, the operation of the initial cluster spread width determining unit 10 of this clustering apparatus will be described. First, 10 data are arbitrarily extracted from the data group to be clustered via the data input unit 1, and the absolute value of the difference is obtained in the order of extraction between each of these data. Here, "3", "25", "5", "27", "7", "1", "4", "32", "34", "8" in the order in which the arbitrarily extracted data is extracted. The case where was.

【0045】

When the difference is taken in the order in which these arbitrarily extracted data are extracted, the absolute value of this difference is "22", "20", "21", "20", "6", "3", "28". , "3", "26". Next, the absolute values of the obtained differences are rearranged in the order of descending, "28", "26", "22", "21", "20", "20", "6", "3", "3". , And take the absolute value of the difference between the values in these order again, and set 1/2 of the maximum value of "14" as the initial cluster spread width. In this case, the initial cluster spread width α is 7. Then, the initial cluster spread width α thus obtained is stored in the clustering parameter storage unit 8, and the cluster generation unit 3 generates an initial cluster using this value.

【0046】

When the initial cluster spread width determination unit 10 determines the initial cluster spread width α for clustering data showing the color distribution of the reference input image formed on the rg plane by the color image processing device described above, r and g. On the other hand, as described above, the initial cluster spread width is determined. As a result, in the case of Fig. 2 (a) in which all distribution states are distributed approximately uniformly in the r direction and g direction on the rg plane, a square initial cluster 21 is generated as in the conventional case, and the reference image is displayed. In the case of Fig. 2 (b) where the state of all distributions of data spreads in the r-axis direction, a horizontally long rectangular initial cluster 22 is generated unlike the conventional case. As described above, according to the clustering processing apparatus of the present invention, the initial clusters that actually match the distribution are generated, so that the clustering processing becomes faster.

【0047】

Here, consider a state in which the clustering data group is divided into two regions and distributed as shown in FIG. Here, the case where there is one dimension will be described. In this case, if the data is arbitrarily extracted from the data group as described above, the data in the region 31 and the data in the region 32 should be extracted in a state approximately close to this distribution. When the difference is taken in the order in which the extracted data are extracted, it is considered that some of the absolute values are close to the distance a, the distance b, the distance c, and the distance d shown in FIG. Therefore, when the differences between these extracted data are arranged in descending order and the absolute values of the differences are taken in that order, the maximum value D among them is the distance d, the distance c, the distance a, and the distance b arranged in the descending order. It becomes a value close to the maximum value L in which the absolute value of the difference is taken in the order of.

【0048】

Here, as shown in FIG. 3, when the distribution state of the clustering data group is such that the region 31 and the region 32 are sufficiently separated from the size of each region, the difference between the distance c and the distance a is the maximum value. It is L. If half of this maximum value L is the width α of the initial cluster, even if the initial cluster 33 is generated with the maximum value data X in the area 31, this cluster 33 does not cover the area 32. Therefore, even if the width α of the initial cluster is set to half the value of the maximum value D, which is smaller than the maximum value L, and the initial cluster of this width α is similarly generated from the maximum value data of the region 31, this initial cluster will be It does not cover area 32.

【0049】

Example 2. By the way, in the above-described embodiment, the case where the data to be clustered does not change with the passage of time has been described, but the scope of application of the clustering apparatus of the present invention is not limited to this. If the initial cluster spread width determination unit 10 periodically generates the initial cluster spread width α at predetermined time intervals, the data to be clustered will actually be distributed even if the data changes with the passage of time. A suitable initial cluster can be generated.

【0050】

When data is generated at any time, the distribution of data changes with time, as shown in Fig. 4 and Fig. 5. FIG. 4 is a distribution map showing a state in which the actual distribution 41 at a certain time changes to a more dispersed distribution 42 with the passage of time, and FIG. 5 shows a state in which the actual distribution 51 changes to a more aggregated distribution with the passage of time. It is a distribution map which shows.

【0051】

When clustering data whose distribution changes as shown in Fig. 4, if the initial cluster 43 is fixed as in the past, as shown in Fig. 4 (b), there are many small clusters for the distribution 42. It will be generated. In this way, even if the clusters in the state shown in FIG. 4 (b) are generated, the clusters repeatedly fuse with each other as explained in the section of the conventional technology, and as a result, FIG. 4 (a) In some cases, a cluster as shown in is generated, but this takes time for the clustering process. Also, if the size of the initial clusters is significantly different from the actual distribution, many small clusters will remain. On the other hand, if the initial cluster spread width α is set according to the distribution state of the data at that time as in the clustering processing apparatus of the second embodiment, it is appropriate for the distribution 42 as shown in FIG. 4 (a). It will generate cluster 44.

【0052】

Next, when clustering data in which the initial distribution 51 changes to the distribution 52 as shown in FIG. 5, if the initial cluster 53 is fixed as in the conventional case, the distribution 52 is shown in FIG. 5 (b). Will generate a large number of large clusters. And, as a result, even though the distribution 52 is formed from three regions, it may generate one cluster. On the other hand, if the initial cluster spread width α is set according to the distribution state of the data at that time as in the clustering processing apparatus of the second embodiment, the distribution 52 is as shown in FIG. 5 (a). Will generate the appropriate cluster 54. In this way, when clustering a data group whose distribution changes with the passage of time, a cluster that is not suitable for the actual distribution may be generated in the past, but the clustering process of Example 2 The device performs an appropriate clustering process that reflects the actual distribution of data.

【0053】

[Effect of the invention]

As described above, according to the present invention, even if there are many data dimensions of the data group to be clustered, the size of the cluster (initial cluster) when a new cluster is generated can be determined by the human sense. It has the effect of being able to make decisions without relying on. Conventionally, when the dimension of data is 4 or more, it is impossible to determine the size of the initial cluster that matches the distribution of the clustering data group, but this invention makes it possible. Moreover, even if there are many dimensions of data to be input, there is an effect that it is not necessary to normalize them.

【0054】

Then, there is an effect that an initial cluster having a size suitable for the distribution of the data group to be clustered can be generated. Therefore, the result of the clustering process accurately reflects the distribution state of the data group, and even if the distribution of the data group to be clustered changes with time, the distribution state is accurately reflected. Clustering processing becomes possible.

[Simple explanation of drawings]

[Figure 1]

It is a block diagram which shows the structure of the clustering processing apparatus which is 1 Example of this invention.

[Figure 2]

It is a distribution map which shows the state of the distribution of the data of the reference image obtained by the color image processing apparatus which performs clustering processing by the clustering processing apparatus of FIG. 1, and the state of the initial cluster generated.

[Fig. 3]

It is explanatory drawing for demonstrating the basic concept of operation of the initial cluster spread width determination part 10.

[Fig. 4]

It is a distribution map which shows the data group which the state of the distribution changes with the passage of time.

[Fig. 5]

It is a distribution map which shows the data group which the state of the distribution changes with the passage of time.

[Fig. 6]

It is a block diagram which shows an example of the conventional clustering processing apparatus.

[Fig. 7]

It is a figure which shows the state of the clustering process of the clustering apparatus of FIG.

[Fig. 8]

It is a distribution diagram for demonstrating the outline of the clustering processing algorithm of the clustering apparatus of FIG.

[Fig. 9]

It is explanatory drawing for demonstrating the cluster generation algorithm of the clustering apparatus of FIG.

[Fig. 10]

It is explanatory drawing for demonstrating the algorithm of the expansion adjustment and reduction adjustment of the cluster of the clustering apparatus of FIG.

[Fig. 11]

It is explanatory drawing for demonstrating the cluster fusion algorithm of the clustering apparatus of FIG.

[Fig. 12]

It is a distribution diagram which shows the state of the distribution of the data of the reference image obtained by the color image processing apparatus which performs clustering processing by the clustering apparatus of FIG.

[Explanation of symbols]

1 Data entry section 2 Cluster generation judgment unit 3 Cluster generator 4 Cluster control unit 5 Cluster fusion judgment unit 6 Cluster fusion section 7 Memory 8 Parameter storage for clustering 9 Clustering information storage unit 10 Initial cluster spread width determination unit