JP6707946B2 - Data clustering method, information processing apparatus, and data clustering program - Google Patents

Description

The present invention relates to a data clustering method and the like.

The clustering process is an important technique that is the basis of artificial intelligence information processing, such as image processing, voice recognition, natural language processing, sensor data processing, and DNA sequence mining. Such clustering processing is roughly classified into a hierarchical clustering method represented by the self-organizing map and the Ward method and a non-hierarchical clustering method represented by the k-means method.

Regarding the hierarchical clustering method, the self-organizing map has a drawback that the convergence of the operation cannot be guaranteed and it is difficult to handle, and the Ward method needs to calculate the distance between all the data points, which is especially large scale. It has the drawback of being difficult to calculate for data.

On the other hand, regarding the non-hierarchical clustering method, the k-means method has a problem that it is difficult to apply it to an unknown environment because it is necessary to give the number of clusters in advance. In recent years, based on the non-parametric Bayes method which is a probabilistic model, a DP-means method has been proposed which automatically determines the number of clusters according to the complexity of data. Although such a method is a non-hierarchical clustering method, it has the advantages that the number of clusters can be dynamically determined and that it is easy to handle unlike the hierarchical clustering method.

Here, an outline of the DP-means method will be described with reference to FIG. FIG. 35 is a diagram showing an outline of the DP-means method. As shown in FIG. 35, the DP-means method allocates each data point to the nearest cluster. Then, if the distance between the data point and the nearest cluster is λ or more, a new cluster is generated. Then, the centroid of the assigned data points is calculated for each cluster, and the centroid of each cluster is updated.

The DP-means method updates the center of gravity of clusters and the number of clusters so as to optimize the objective function value φ(x, λ) shown in the following equation (1). Here, x is an input d-dimensional data point group, k is the number of clusters, and λ is a hyperparameter that determines the number of clusters.
φ(x, λ)=ΣD(x, u)+λ ² k (1)
D(x,u) is a distance function, and for example, the squared Euclidean distance represented by the following equation (2) corresponds to it.

However, since the DP-means method uses all data points when optimizing the objective function value φ(x, λ), it is necessary to hold all data points. In addition, since the calculation amount of the calculation process increases in proportion to the number of held data points, when the clustering process is performed on a large number of data points, the calculation amount becomes very large. The method of performing the clustering process with all the data points held in this way is referred to as "batch clustering".

On the other hand, a method of extracting representative points from all data points and performing clustering processing using the representative points is called "streaming clustering".

International Publication No. 2011/142225 JP, 2002-304626, A JP, 2010-134632, A JP, 2013-182341, A Japanese Patent Laid-Open No. 10-171823

B. Kulis and M. Jordan, “Revisiting k-means: New Algorithms via Bayesian Nonparametrics”, In ICML2012.

However, in order to perform the streaming clustering, it is necessary to select the representative points by some means, but if the representative points are simply selected at random (random sampling), there is a problem that the accuracy of clustering decreases. This is because random sampling causes imbalance in input data points, and when there is a cluster with a small number of data points, information of this cluster is easily lost.

An example in which the clustering accuracy is reduced by streaming clustering will be described with reference to FIG. FIG. 36 is a diagram illustrating an example in which the clustering accuracy is reduced in streaming clustering. In FIG. 36, it is assumed that the data points included in each cluster exist unbalanced, and each cluster holds 898 points, 100 points, and 2 data points. Here, it is assumed that 1/10 data points are selected as representative points at the same rate for all clusters. Then, in a cluster including only two data points, none of the points is selected, and the cluster information is lost. Therefore, the number of clusters different from the case where batch clustering is performed is output, and the accuracy of clustering is greatly reduced.

In one aspect, the present invention aims at suppressing a decrease in accuracy in streaming clustering.

In one aspect, the data clustering method is the method of data clustering in streaming clustering, in which a feature amount space in which input data points are arranged is divided into local regions, and the local regions in which one or more data points exist are independent of each other. When a data point is added to the local area where the representative point exists next, weighting is performed based on the representative point and the added data point, a new representative point is determined, and a new representative point is determined. Each process that controls the number of clusters using the representative points is executed.

According to the one embodiment, it is possible to suppress a decrease in accuracy in streaming clustering.

FIG. 1 is a functional block diagram of the configuration of the information processing apparatus according to the first embodiment. FIG. 2 is a diagram illustrating a grid. FIG. 3 is a diagram showing an example of the data structure of the grid list. FIG. 4 is a diagram illustrating an example of the data structure of the representative point list according to the first embodiment. FIG. 5 is a diagram illustrating the representative point update process according to the first embodiment. FIG. 6 is a diagram illustrating clustering using the representative point updating process according to the first embodiment. FIG. 7A is a diagram showing an example of a grid. FIG. 7B is a diagram showing another example of the grid. FIG. 8 is a diagram showing an example of a method of determining the maximum number of points to be held. FIG. 9 is a diagram illustrating a flowchart of the representative point updating process according to the first embodiment. FIG. 10 is a diagram illustrating a flowchart of representative point compression processing according to the first embodiment. FIG. 11 is a diagram illustrating a flowchart of the clustering process using the representative point update process according to the first embodiment. FIG. 12 is a diagram illustrating a flowchart of the clustering process according to the first embodiment. FIG. 13 is a diagram illustrating online clustering using the representative point updating process according to the first embodiment. FIG. 14 is a diagram illustrating a case where the representative point is divided. FIG. 15 is a functional block diagram of the configuration of the information processing apparatus according to the second embodiment. FIG. 16 is a diagram illustrating an example of the data structure of the representative point list according to the second embodiment. FIG. 17 is a diagram illustrating a representative point range according to the second embodiment. FIG. 18 is a diagram illustrating conditions for dividing the representative point according to the second embodiment. FIG. 19 is a diagram illustrating a flowchart of representative point division processing according to the second embodiment. FIG. 20 is a diagram illustrating a flowchart of the clustering process according to the second embodiment. FIG. 21 is a functional block diagram of the configuration of the information processing apparatus according to the third embodiment. FIG. 22 is a diagram illustrating an example of the data structure of the cost function table according to the third embodiment. FIG. 23 is a diagram illustrating an example of the data structure of the representative point/cluster correspondence table according to the third embodiment. FIG. 24 is a diagram illustrating an example of the data structure of the cluster center set according to the third embodiment. FIG. 25 is a diagram illustrating an example of the flow of clustering processing according to the third embodiment. FIG. 26 is a diagram illustrating conditions for integrating representative points according to the third embodiment. FIG. 27 is a diagram illustrating a premise for deriving the cost function according to the third embodiment. FIG. 28 is a diagram illustrating a flowchart of the clustering process according to the third embodiment. FIG. 29 is a diagram illustrating an outline of the clustering process according to the fourth embodiment. FIG. 30 is a diagram illustrating an example of the flow of clustering processing according to the fourth embodiment. FIG. 31 is a diagram illustrating a premise for deriving the cost function according to the fourth embodiment. FIG. 32 is a diagram illustrating a flowchart of the clustering process according to the fourth embodiment. FIG. 33 is a diagram illustrating an example of a computer that executes a data clustering program. FIG. 34 is a diagram showing an outline of the DP-means method. FIG. 35 is a diagram showing an example in which the clustering accuracy is reduced by streaming clustering.

Hereinafter, embodiments of a data clustering method, an information processing apparatus, and a data clustering program disclosed in the present application will be described in detail with reference to the drawings. The present invention is not limited to the examples.

[Configuration of Information Processing Device According to First Embodiment]
FIG. 1 is a functional block diagram of the configuration of the information processing apparatus according to the first embodiment. The information processing apparatus 1 shown in FIG. 1 divides a feature amount space in which input data points are arranged into local areas (hereinafter referred to as “grids”), and represents at least one or more representative points in a grid area in which data points exist. Hold the points. The information processing device 1 determines whether or not the number of representative points exceeds a certain number for each local area, and compresses (thinning out) the representative points in the local area where the number of the representative points exceeds a certain number. As a result, the information processing device 1 secures at least one point at the location where each cluster exists, and thus it is possible to prevent the loss of information of the cluster having a small number of points. Further, in the information processing device 1, since the number of representative points does not exceed a certain number at the location where each cluster exists, the number of representative points held can be suppressed to a certain number. As a result, the information processing device 1 can perform accurate clustering without always holding all data points.

The information processing device 1 includes a control unit 10 and a storage unit 20.

The control unit 10 corresponds to an electronic circuit such as a CPU (Central Processing Unit). The control unit 10 has an internal memory for storing programs and control data that define various processing procedures, and executes various processing by these. The control unit 10 includes a data acquisition unit 11, a representative point updating unit 12, a representative point compressing unit 13, and a clustering unit 14.

The storage unit 20 is, for example, a RAM, a semiconductor memory device such as a flash memory, or a storage device such as a hard disk or an optical disk. The storage unit 20 has a grid list 21 and a representative point list 22. The grid list 21 shows information on the grid holding the representative points. The representative point list 22 shows information on the representative points held in the grid. The information on the representative point includes, for example, the coordinates of the representative point and the weight. The data structures of the grid list 21 and the representative point list 22 will be described later.

Here, the grid will be described with reference to FIG. FIG. 2 is a diagram for explaining the grid. As shown in FIG. 2, the grid is a local area obtained by dividing the feature amount space in which the input data points are arranged into a predetermined size. The grid is created where the data points reside. The generated grid is stored in the grid list 21 described later. A representative point is selected from the input data points. The coordinate of the representative point means a parameter as a feature amount of the representative point selected from the input data points. The weight of the representative point is a parameter that increases when other data points are merged into the representative point. The coordinates of the representative points and the weights of the representative points are stored in the representative point list 22 described later. As an example, at the representative point p1, the coordinates of the representative point are (xi, yi) and the weight of the representative point is 10.0.

The weight of the representative point is a parameter for preventing the center of gravity position from changing before and after the representative point compression processing, and is added to the representative point information. In the example of FIG. 2, when compressing p21, p22, p23, and p24, a parameter indicating a weight is added to the information of the representative point p2 (p22) as the information of the data point to be compressed. The weight corresponds, for example, to the number of data points. Therefore, here, “4” is added to the information of the representative point p2 as a parameter of the weight w. By using this weight parameter, the center of gravity position after compressing (thinning) the data points is almost the same as the center of gravity position using all the data points.

Here, the data structure of the grid list 21 will be described with reference to FIG. FIG. 3 is a diagram showing an example of the data structure of the grid list. As shown in FIG. 3, the grid list 21 stores a grid ID 21a and a grid coordinate 21b in association with each other. The grid ID (IDentfier) 21a is an identifier that uniquely identifies the grid. The grid coordinate 21b indicates the position (coordinate) of the local area in the feature amount space of the grid.

The data structure of the representative point list 22 will be described with reference to FIG. FIG. 4 is a diagram showing an example of the data structure of the representative point list. As shown in FIG. 4, the representative point list 22 stores the representative point coordinates 22b and the representative point weights 22c in association with the grid ID 22a. The grid ID 22a is a grid identification ID. The representative point coordinates 22b are the coordinates of the representative point. The representative point weight 22c is the weight of the representative point.

Returning to FIG. 1, the data acquisition unit 11 acquires data points to be clustered. For example, the data acquisition unit 11 acquires a data point input from the outside. The data points to be clustered are, for example, acoustic signals quantized at 16 kHz and 16 bits (hereinafter referred to as sound data), but are not limited to sound data.

The representative point updating unit 12 updates the representative points so that the number of representative points on the grid does not exceed a certain number. The fixed number here indicates the number of data points that can be held in the grid, and will be referred to as the “maximum number of held points” hereinafter. For example, the representative point update unit 12 receives the data points acquired by the data acquisition unit 11. The number of data points to be accepted may be one or plural. The representative point updating unit 12 determines whether or not the grid stored in the grid list 21 includes a grid including the coordinates of the received data points. If the representative point updating unit 12 determines that a grid including the coordinates of the data points exists in the grids stored in the grid list 21, the representative point updating unit 12 adds the data points to the grid. At this time, the representative point updating unit 12 sets the weight of the data point to 1. If the representative point updating unit 12 determines that the grid stored in the grid list 21 does not include a grid including the coordinates of the data points, a new grid including the coordinates of the data points is generated, Add this data point to the generated grid. At this time, the representative point updating unit 12 sets the weight of the data point to 1 and adds the newly generated grid to the grid list 21. After adding the received data points to the grid, the representative point updating unit 12 determines whether or not the number of representative points exceeds the maximum number of held points for each grid stored in the grid list 21. If the number of representative points exceeds the maximum number of held points, the representative point updating unit 12 executes the representative point compression processing so that the number of representative points does not exceed the maximum number of held points in the target grid, and the representative point compression processing is performed. Update points. The representative point compression processing is executed by the representative point compression unit 13.

When the number of representative points in the grid exceeds the maximum number of holding points, the representative point compressing unit 13 compresses the representative points so that the number of representative points in the grid does not exceed the maximum number of holding points. For example, the representative point compression unit 13 selects a new representative point from the representative points included in the grid. The representative point compression unit 13 selects a representative point closest to the new representative point from the representative points included in the grid. The representative point compression unit 13 adds 1 to the weight of the new representative point and deletes the closest representative point. That is, the representative point compressing unit 13 compresses the new representative point and the representative point closest to the new representative point, so that the number of representative points in the grid finally becomes equal to or less than the maximum number of representative points. To do so. As a method of selecting a new representative point, a method of randomly sampling the representative points included in the grid or a method of selecting the representative point when the number of clusters is a fixed value, such as the k-means method, is used. Is also good. The maximum number of points to be held may be a fixed number that differs for each grid or the same fixed number for each grid. An example of the method of determining the maximum holding score will be described later.

Here, the representative point updating process by the representative point updating unit 12 will be described with reference to FIG. FIG. 5 is a diagram illustrating the representative point update process according to the first embodiment. As shown in FIG. 5, the representative point updating unit 12 merges the new data points with the grid of the representative points stored in the representative point list 22. The representative point updating unit 12 newly generates a grid when a new data point is entered in a portion where there is no grid.

That is, the representative point updating unit 12 adds a new data point to the grid stored in the grid list 21 if a grid including the coordinates of the new data point exists in the grid. Then, the representative point updating unit 12 generates a new grid if the grid stored in the grid list 21 does not include a grid including the coordinates of the new data point, and creates a new grid. Add a new data point. Here, the new data point group with the code p100 is merged into the grid g1, and the new data group with the code p200 is merged into the grid g2. Then, the new data point group with the code p300 is added to the newly generated grid g4.

After merging the new data points into the grid, the representative point updating unit 12 determines whether or not the number of representative points exceeds the maximum number of retained points for each grid, and exceeds the maximum number of retained points. Select the grid you are viewing. Here, it is assumed that the maximum number of holding points is 10 points, which is the same fixed number for each grid. It is assumed that it is determined that the grids g1, g3, and g4 do not exceed the maximum number of holding points of 10. The grid g2 has 20 points, and it is assumed that it is determined that the maximum number of held points 10 is exceeded. Then, the grid g2 is selected as the grid that exceeds the maximum number of holding points.

Then, the representative point compressing unit 13 selects representative points in a grid exceeding the maximum number of representative points, and compresses the selected representative point and the representative point closest to the selected representative point. The representative point compression unit 13 adds 1 to the weight of the selected representative point and deletes the closest representative point. The representative point compression unit 13 repeats the compression process until the number of representative points in the grid reaches the maximum number of representative points. Here, the representative point compression unit 13 selects the representative point p4 in the grid g4 and compresses the selected representative point p4 and the representative point p5 closest to the representative point p4. The representative point compression unit 13 adds 1 to the weight of the representative point p4 and deletes the representative point p5. As a result, the weight of the representative point p4 is 2.

Returning to FIG. 1, the clustering unit 14 executes the batch clustering process using the representative points included in the grid in the grid list 21 as input. For example, the clustering unit 14 acquires the representative points included in the grid in the grid list 21 from the representative point list 22, and executes the DP-means method using the acquired representative points as an input. Since the DP-means method uses weighted representative points, the DP-means method here is referred to as a “weighted DP-means method”. Although the clustering unit 14 uses the DP-means method as the clustering process, it is not limited to the DP-means method and can be applied to a clustering method in which the number of clusters is variable. For example, as a hard clustering method, a method in which a clustering method with a fixed number of clusters such as the K-means method is applied to a plurality of cluster numbers and one of them is adopted as a result is applicable. is there. Further, the HDP-means method that assumes a hierarchical relationship of clusters can be applied. As the stochastic soft clustering method, DPM (Dirichlet Process Mixture), HDP (Hierarchical Dirichlet Process), and NDP (Nested Dirichlet Process) can be applied.

Here, the clustering processing by the clustering unit 14 will be described with reference to FIG. FIG. 6 is a diagram illustrating a clustering process according to the first embodiment. As shown in FIG. 6, first, the representative point updating unit 12 repeats the processing of acquiring a part of the data points and updating the representative points, and again acquiring a part of the data points and updating the representative points. Then, the clustering unit 14 performs batch clustering processing on the finally updated representative points. The clustering unit 14 substitutes the centroids of all representative points into the cluster center set. The clustering unit 14 extracts the center whose representative point is the closest in the cluster center set. The “distance” described here refers to, for example, the Euclidean distance. If the distance between the representative point and the extracted center is smaller than the threshold λ (parameter that determines the granularity of the cluster), the clustering unit 14 allocates the representative point to the cluster having this center. If the distance between the representative point and the extracted center is greater than or equal to the threshold λ, the clustering unit 14 substitutes this representative point into the cluster center set as a new cluster center. Then, the clustering unit 14 extracts the cluster center from the cluster center set, and updates the extracted coordinate value of the cluster center to the weighted center of gravity value of the representative point.

Here, an example of the grid will be described with reference to FIG. 7A. FIG. 7A is a diagram showing an example of a grid. The example of the grid shown in FIG. 7A is a d-dimensional hypercube in the feature space. That is, in the case of two dimensions, the grid is square, in the case of three dimensions, the grid is a cube, and in the case of four dimensions, the grid is a regular octahedron. If λ is a parameter that determines the grain size of the cluster, for example, the diameter of the cluster, then the length of one side of the grid is preferably λ/√d or less. As a precondition, it is assumed that a new cluster is generated when the distance between data points is λ or more. Then, if the length of one side of the grid is λ/√d or less, it is guaranteed that the possible distance between the data points included in the same grid is λ or less. In other words, the point that has the maximum distance among the points included in the grid is located on the diagonal line, and the length of the diagonal line at this time is (length of one side of hypercube λ√d×√d=)λ Become. Therefore, since the data points included in one grid are λ or less, they are included in one cluster and not included in another cluster. As a result, even if the representative point compressing unit 13 performs the representative point compressing process on each grid, it is guaranteed that the cluster will not disappear in the clustering process. That is, if the length of one side of the grid is λ/√d or less, leaving one data point on the grid does not cause the cluster to disappear.

Another example of the grid will be described with reference to FIG. 7B. FIG. 7B is a diagram showing another example of the grid. An example of the grid shown in FIG. 7B is a d-dimensional hypersphere in the feature amount space. If λ is a parameter that determines the grain size of the cluster, for example, the diameter of the cluster, it is desirable that the diameter of the grid be λ or less. As a precondition, it is assumed that a new cluster is generated when data points are separated by λ or more. Then, if the diameter of the grid is λ or less, it is guaranteed that the data points included in the same grid can have a distance of λ or less. That is, the point having the maximum distance among the points included in the grid is located on the diameter, and the length of the diameter at this time is λ. Therefore, since the data points included in one grid are λ or less, they are included in one cluster and not included in another cluster. As a result, even if the representative point compressing unit 13 performs the representative point compressing process on each grid, it is guaranteed that the cluster will not disappear in the clustering process. That is, if the diameter of the grid is λ or less, leaving one data point on the grid does not cause the cluster to disappear.

Next, an example of a method of determining the maximum holding score will be described with reference to FIG. FIG. 8 is a diagram showing an example of a method of determining the maximum number of points to be held. The maximum number of holding points of each grid can be set as an arbitrary number, but if the dimension number d in the feature amount space is 1, it may be 2, and if the dimension number d is 2 or more, it may be d (the number of dimensions). desirable. This is because, as shown in FIG. 8, if the dimension is two or more, it is guaranteed that the maximum number of cluster centers included in the grid is less than the dimension number d+1. However, in the case of one dimension, the number is two or less, that is, the number of dimensions d+1 or less. This can be shown recursively as follows: First, when the dimension number d is 1, it is optimal to set the center of the cluster at a distance d on the numerical straight line, which is self-evident. When the number of dimensions d is 2 or more, it is assumed that the assumption is made in the d dimension (the center of the cluster is d), and the number of the center of the cluster is d+2 or more in the d+1 dimension. Then, the number of cluster centers is d+1 or more in a certain subspace, which is inconsistent with the assumption. Therefore, it suffices that each grid holds a number of representative points in the number of dimensions.

In other words, as shown in FIG. 8, in the case of two dimensions, a cluster having three vertices of an equilateral triangle as the center of the cluster can be arranged in one grid. However, in such a case, the clusters will overlap. Therefore, in order to prevent the clusters from overlapping, the center of the largest cluster included in the grid needs to be less than 3, that is, 2 or less. This is the same even if it is two-dimensional or more. Therefore, in the case of two or more dimensions, it is guaranteed that the cluster will not disappear even if the representative point compression processing is performed, if the representative points are left in the grid by the number of dimensions d as the maximum number of retained points. As a result, it is possible to prevent deterioration of the accuracy of the clustering process.

Furthermore, as described above, since the maximum number of representative points held in the grid is sufficient to be d, it is sufficient to perform a clustering process assuming that d fixed clusters exist in the grid. By doing so, it is possible to prevent the accuracy of the cluster centroid from deteriorating. For example, when a fixed number of clusters such as the k-means method is known, the error of the position of the center of gravity of the cluster can be suppressed to a constant multiple. Therefore, the k-means method is used as a compression algorithm and the cluster If the compression process is performed with the number d, the clustering process can be performed with high accuracy. At this time, the maximum number of representative points held by the k-means method may be 3d×log(d).

[Flowchart of representative point update processing]
Next, a flowchart of the representative point updating process according to the first embodiment will be described with reference to FIG. FIG. 9 is a diagram illustrating a flowchart of the representative point updating process according to the first embodiment. The representative point updating unit 12 acquires the data point group X, the parameter λ that determines the granularity of the cluster, and the grid list 21 as input parameters. The data point group X here is not limited to all the data used for the final clustering process, and may be a part of the data used for the final clustering process.

First, the representative point updating unit 12 extracts the data point x from the data point group X (step S11). The representative point updating unit 12 determines whether or not there is a grid that includes the data point x in the grid list 21 (step S12). When it is determined that there is no grid including the data point x in the range (step S12; No), the representative point updating unit 12 generates a new grid including the data point x in the range, and the grid coordinates of the generated grid. 21b is added to the grid list 21 (step S13). Then, the representative point updating unit 12 moves to step S14.

On the other hand, when it is determined that there is a grid including the data point x in the range (step S12; Yes), the representative point updating unit 12 adds the data point x having a weight of 1.0 to the grid (step S12). S14). The representative point updating unit 12 determines whether all the data points x have been extracted from the data point group X (step S15). When it is determined that all the data points x have not been extracted (step S15; No), the representative point updating unit 12 proceeds to step S11 to extract the next data point.

On the other hand, when it is determined that all the data points x have been extracted (step S15; Yes), the representative point updating unit 12 performs grid optimization processing if necessary (step S16). When the representative point updating unit 12 generates a grid, the center of the grid may not be optimum. This is because a large number of grids may be saved, which may unnecessarily require a storage area.

Subsequently, the representative point updating unit 12 extracts a grid from the grid list 21 (step S17). The representative point updating unit 12 determines whether the number of representative points included in the grid is less than or equal to the maximum number of held points (step S18). When it is determined that the number of representative points included in the grid is equal to or less than the maximum number of retained points (step S18; Yes), the representative point updating unit 12 does not execute the representative point compression processing, and proceeds to step S20.

If it is determined that the number of representative points included in the grid is not less than or equal to the maximum number of retained points, that is, greater than the maximum number of retained points (step S18; No), the representative point updating unit 12 executes representative point compression processing (step S18). S19). The flowchart of the representative point compression processing will be described later. Then, the representative point updating unit 12 moves to step S20.

In step S20, the representative point updating unit 12 determines whether or not all grids have been extracted from the grid list 21 (step S20). If it is determined that all grids have not been extracted (step S20; No), the representative point updating unit 12 proceeds to step S17 to extract the next grid.

On the other hand, when it is determined that all the grids have been extracted (step S20; Yes), the representative point updating unit 12 ends the representative point updating process and outputs the grid list 21 as an output parameter.

[Flowchart of representative point compression processing]
Next, a flowchart of representative point compression processing according to the first embodiment will be described with reference to FIG. FIG. 10 is a diagram illustrating a flowchart of representative point compression processing according to the first embodiment. The representative point compression unit 13 acquires, as input parameters, the coordinates of the representative points included in the grid determined to be larger than the maximum number of retained points, the weight of the representative point, and the maximum number of retained points.

The representative point compression unit 13 selects a new representative point having the maximum number of held points from the representative points acquired as the input parameters (step S21). Examples of the method of selecting a new representative point include random sampling and the k-means method. Then, the representative point compressing unit 13 clears the weight of the new representative point to 0 (step S22).

Then, the representative point compressing unit 13 sequentially selects the old representative points x held in the grid (step S23). The representative point compression unit 13 selects a new representative point closest to the selected old representative point x (step S24). The representative point compressing unit 13 adds 1 to the weight of the representative point of the selected new representative point (step S25). Then, the representative point compression unit 13 deletes the selected old representative point x from the representative point list 22 (step S26).

Subsequently, the representative point compression unit 13 determines whether or not all the old representative points have been selected (step S27). If it is determined that all the old representative points have not been selected (step S27; No), the representative point compression unit 13 proceeds to step S23 to select the next old representative point. On the other hand, when it is determined that all the old representative points have been selected (step S27; Yes), the representative point compression unit 13 ends the representative point compression processing and outputs the coordinates and weights of the new representative point as output parameters. To do.

[Flowchart of clustering process]
Next, a flowchart of the clustering process using the representative point updating process according to the first embodiment will be described with reference to FIG. FIG. 11 is a diagram illustrating a flowchart of the clustering process using the representative point update process according to the first embodiment. The information processing apparatus 1 acquires the data point group X and the parameter λ that determines the granularity of the cluster as input parameters.

First, the information processing device 1 sets the grid list 21 to an empty set (step S31). Then, the information processing device 1 updates the grid list 21 in the representative point update process (step S32). The flowchart of the representative point updating process is the one shown in FIG.

Then, the information processing device 1 executes the clustering process using the representative points (coordinates, weights) in the grid list 21 as input (step S33). For the clustering process, for example, the weighted DP-means method is applied. The flowchart of the clustering process will be described later.

Then, the information processing device 1 ends the clustering process using the representative point update process, and outputs the clustering result as an output parameter.

FIG. 12 is a diagram illustrating a flowchart of the clustering process according to the first embodiment. Note that FIG. 12 illustrates a case where the weighted DP-means method is applied and the squared Euclidean distance is used as the distance function used when determining addition of a cluster. The clustering unit 14 acquires, as input parameters, the representative point group X, the representative point weight w, and the parameter λ that determines the cluster granularity.

The clustering unit 14 substitutes the centroids of all the representative points into the center set U of the cluster (step S41). The clustering unit 14 determines whether or not they have converged (step S42). When it is determined that they have not converged (step S42; No), the clustering unit 14 extracts the representative point x from the representative point group X (step S43). Then, the clustering unit 14 extracts the center u having the shortest distance from the cluster center set U (step S44).

The clustering unit 14 determines whether or not the distance between the representative point x and the center u is λ ² or more (step S45). When it is determined that the distance between the representative point x and the center u is λ ² or more (step S45; Yes), the clustering unit 14 adds the representative point x to the center set U of the cluster (step S46). Then, the clustering unit 14 proceeds to step S47.

On the other hand, the distance between the representative point x and the center u is not lambda ² or more, i.e. when it is determined that lambda ² smaller (step S45; No), the clustering unit 14 proceeds to step S47. In step S47, the clustering unit 14 updates the label of the representative point x to the label of the nearest cluster (step S47).

Then, the clustering unit 14 determines whether or not all the representative points x have been extracted from the representative point group (step S48). When it is determined that all the representative points x have not been extracted (step S48; No), the clustering unit 14 proceeds to step S43 in order to extract the next representative point.

On the other hand, when it is determined that all the representative points x have been extracted (step S48; Yes), the clustering unit 14 extracts the cluster center u from the cluster center set U (step S49). The clustering unit 14 updates the extracted coordinate value of u to the weighted centroid value of the representative point labeled with u (step S50).

Then, the clustering unit 14 determines whether the centers u of all the clusters have been extracted from the center set U of the clusters (step S51). When it is determined that the centers u of all the clusters are not extracted (step S51; No), the clustering unit 14 proceeds to step S49 to extract the centers of the next clusters. On the other hand, when it is determined that the centers u of all the clusters have been extracted (step S51; Yes), the clustering unit 14 proceeds to step S42 to make a convergence determination.

When it is determined in step S42 that the clusters have converged (step S42; Yes), the clustering unit 14 outputs the central set U of clusters (step S52), and ends the clustering process.

Note that the information processing apparatus 1 may perform online clustering processing by performing clustering processing at regular time intervals (independently) using the representative points updated by the representative point updating processing according to the first embodiment. it can. Online clustering using the representative point update processing according to the first embodiment will be described with reference to FIG. FIG. 13 is a diagram illustrating online clustering using the representative point updating process according to the first embodiment.

As shown in FIG. 13, when the time point t is 0, the information processing device 1 receives the input data point. The information processing apparatus 1 performs representative point update processing on the received input data points. That is, the information processing apparatus 1 adds this input data point as a representative point to this grid if a grid including the input data point already exists. If there is no grid including the input data point in the range, the information processing apparatus 1 creates a new grid and adds this input data point to the newly created grid as a representative point. The information processing apparatus 1 performs representative point compression processing and updates the representative points so that the number of representative points in each grid does not exceed the maximum number of held points. Then, the information processing device 1 performs the batch clustering process using the updated representative point as an input.

When the time passes and the time point t becomes 1, the information processing device 1 receives the input data point. The information processing apparatus 1 performs a representative point update process on the received input data points and the representative points updated when the time point t was 0. That is, the information processing apparatus 1 adds this input data point as a representative point to this grid if a grid including the input data point already exists. If there is no grid including the input data point in the range, the information processing apparatus 1 creates a new grid and adds this input data point to the newly created grid as a representative point. The information processing device performs representative point compression processing and updates the representative points so that the number of representative points in each grid does not exceed the maximum number of held points. Then, the information processing device 1 performs the batch clustering process using the updated representative point as an input.

When the time passes and the time point t reaches 2, the information processing device 1 receives the input data point. The information processing apparatus 1 performs representative point update processing on the received input data points and the representative points updated when the time point t was 1. That is, the information processing apparatus 1 adds this input data point as a representative point to this grid if a grid including the input data point already exists. If there is no grid including the input data point in the range, the information processing apparatus 1 creates a new grid and adds this input data point to the newly created grid as a representative point. The information processing device performs representative point compression processing and updates the representative points so that the number of representative points in each grid does not exceed the maximum number of held points. Then, the information processing device 1 performs the batch clustering process using the updated representative point as an input.

In this way, the information processing device 1 can perform online clustering processing by independently performing clustering processing at each time point on data points input in a time-division manner.

[Effect of Example 1]
According to the first embodiment, the information processing device 1 performs streaming clustering as follows. That is, the information processing device 1 divides the feature amount space in which the input data points are arranged into grids. The information processing device 1 independently determines a representative point for a grid having one or more data points, and when the data point is added to the grid having the representative point next, the information point is added as the representative point. A new representative point is determined by weighting based on the data points. Then, the information processing device 1 controls the number of clusters using the new representative point. According to such a configuration, the information processing device 1 can suppress deterioration of clustering accuracy in streaming clustering. That is, the information processing device 1 determines a representative point weighted as a representative of the input data points and performs clustering, as compared with the case where the number of data points is randomly reduced, and thus it is possible to suppress a decrease in clustering accuracy. Become.

Further, according to the first embodiment, the information processing apparatus 1 sets the feature amount space to λ/√d (λ: a threshold value that determines the granularity of the cluster, d: the number of dimensions of the feature amount space) as the length of one side. Divide into a grid that is a d-dimensional hypercube. According to this configuration, the information processing apparatus 1 determines that the length of the diagonal line of the d-dimensional hypercube is (threshold value that determines the granularity of the cluster) λ, so that the cluster does not disappear if the grid includes data points. Become. As a result, the information processing apparatus 1 can prevent the cluster from disappearing and the error in the number of clusters becoming large when the representative points are randomly determined.

Moreover, according to the first embodiment, the information processing apparatus 1 is a grid that is a d-dimensional hypersphere (d: the number of dimensions of the feature amount space) whose feature amount space has a diameter of a threshold λ that determines the granularity of the cluster. Split into. According to this configuration, the information processing apparatus 1 has the diameter length of the d-dimensional hypersphere as (threshold value that determines the granularity of the cluster) λ. Therefore, if the grid includes data points, the cluster may not disappear. Guaranteed. As a result, the information processing apparatus 1 can prevent the cluster from disappearing and the error in the number of clusters becoming large when the representative points are randomly determined.

Further, according to the first embodiment, the information processing device 1 sets the maximum number of points held in the grid to the dimension number d. According to this configuration, if the information processing apparatus 1 leaves the representative points by the dimension number d as the maximum number of holding points in the grid, the representative points remain even if the representative point compression processing is performed, so that the cluster does not disappear. Is guaranteed. As a result, the information processing apparatus 1 can prevent the cluster from disappearing and the error in the number of clusters becoming large when the representative points are randomly determined.

Further, according to the first embodiment, the information processing apparatus 1 determines a new representative point for the time-divided data point based on the already-represented representative point and the time-divided data point. According to such a configuration, the information processing device 1 can perform the online clustering process using the representative point update process, and can suppress the decrease in the accuracy of the online clustering.

Further, according to the first embodiment, the information processing device 1 sets the maximum number of points held in the grid to 3×d×log(d). According to this configuration, the information processing apparatus 1 can perform clustering processing with high accuracy if the maximum number of representative points held by the k-means method is 3d×log(d).

By the way, in the first embodiment, the case where the information processing apparatus 1 generates a new cluster when the distance between the representative points is λ or more is described. However, the information processing apparatus 1 is not limited to this, and when falling into a local solution, the representative points may be divided and the cluster may be divided. The local solution is a state in which the optimum solution cannot be reached.

[When splitting representative points]
Here, the case of dividing the representative point will be described with reference to FIG. FIG. 14 is a diagram illustrating a case where the representative point is divided. First, in the DP-means method, the center of gravity of clusters is updated and the number of clusters is updated so that the value of the objective function becomes the minimum value. The objective function here is expressed by the following equation (3). Note that x is a data point belonging to the input d-dimensional data point group X, u is a cluster center belonging to the cluster center set C, k is the number of clusters, and λ is a parameter that determines the granularity of the cluster. Let λ be the diameter of the cluster in FIG.

The distance function represented by the cluster center u and the data point x uses the squared Euclidean distance, but the distance function is not limited to this. For example, the distance function may be one that satisfies symmetry such as Manhattan distance or L∞ distance, or one that does not satisfy symmetry such as KL divergence, Mahalanobis distance, or Itakura Saito distance.

As shown in FIG. 14, when there is one cluster, the cluster center u is (0,0), so the distance between the input data point (-1,0) and the cluster center u is 1, and the input data is The distance between the point (1,0) and the cluster center u is 1. The input data point (-1,0) has a weight of 10,000, and the input data point (1,0) has a weight of 10,000. Then, the objective function L(X, C) (=20000×1 ² +10 ² ×1) becomes 20100.

On the other hand, when there are two clusters, the cluster center u is (-1,0), (1,0). Since (-1,0) and (1,0) as the input data points are assigned to the nearest clusters, the distance between the input data point (-1,0) and the cluster center u is 0, and the input data point is The distance between the point (1,0) and the cluster center u is 0. Then, the objective function L(X,C) (=20000×0 ² +10 ² ×2) becomes 200. When there are two clusters, the objective function value is smaller than when there is one cluster. When the number of clusters is one, the objective function does not reach the minimum value and falls into a local solution.

It is assumed that the input data point (-1,0) has a weight of 10 and the input data point (1,0) has a weight of 10. Then, when there is one cluster, the objective function L(X,C) (=20×1 ² +10 ² ×1) becomes 120. On the other hand, when there are two clusters, the objective function L(X,C) (=200×0 ² +10 ² ×2) is 200. When there is one cluster, the objective function value is smaller than when there are two clusters. When there is one cluster, the optimal solution is reached. In other words, if the weight of the representative points included in the cluster increases, a local solution may occur, so it may be better to divide the cluster.

Therefore, in the second embodiment, a case will be described in which the information processing device 1 divides the representative points when the weight of the representative points increases in the clustering using the weighted representative points.

[Configuration of Information Processing Device According to Second Embodiment]
FIG. 15 is a functional block diagram of the configuration of the information processing apparatus according to the second embodiment. The same components as those of the information processing device 1 shown in FIG. 1 are designated by the same reference numerals, and the description of the overlapping components and operations will be omitted. The difference between the first embodiment and the second embodiment is that a representative point dividing unit 31 is added. Further, the difference between the first embodiment and the second embodiment is that the clustering unit 14 is changed to the clustering unit 14A. Further, the difference between the first embodiment and the second embodiment is that the representative point list 22 is changed to the representative point list 22A.

The data structure of the representative point list 22A will be described with reference to FIG. FIG. 16 is a diagram showing an example of the data structure of the representative point list. As shown in FIG. 16, the representative point list 22A stores the representative point coordinates 22b, the representative point weight 22c, and the representative point range 22d in association with the grid ID 22a. The grid ID 22a is a grid identification ID. The representative point coordinates 22b are the coordinates of the representative point. The representative point weight 22c is the weight of the representative point. The representative point range 22d indicates the range of data points included in the representative point. The representative point range 22d may be the maximum value/minimum value of the dimension of the representative point, or may be the variance. Hereinafter, the representative point range 22d will be described as the maximum value/minimum value of the dimension of the representative point.

Here, the representative point range 22d will be described with reference to FIG. FIG. 17 is a diagram illustrating a representative point range according to the second embodiment. As shown in FIG. 17, when the representative point is selected from the data points, the range of a plurality of data points included in the representative point (representative point range) other than the coordinates and the weight is the representative point list. 22A is added. Here, as an example, with respect to the representative point, (0, 0) is set as the center, 5 points are set as the weight, -5 to 5 are set in the x-axis direction, and -2 to 2 are set in the y-axis direction. That is, the representative point includes data points of −5 to 5 in the x-axis direction and −2 to 2 in the y-axis direction. The representative point is added to the representative point list 22A by the representative point dividing unit 31 described later.

Returning to FIG. 15, the representative point dividing unit 31 determines the number of representative points in the dimension n to be 2 when the range in the dimension n satisfies the condition of the following Expression (4) with respect to the representative point having the weight w. Divide into two. It is assumed that w is a weight and λ is a parameter that determines the cluster grain size. σ _n is an n-dimensional range, and σ _n = _pn −q _n ( _pn , q _n : maximum value and minimum value in dimension n).
w≧16 (λ/σ _n ) ² (4)

The reason why the condition for dividing the representative point is set to Expression (4) is that the expected value of the objective function after the division becomes smaller than that before the division when the condition is satisfied. Here, the conditions for dividing the representative point will be described with reference to FIG. FIG. 18 is a diagram illustrating conditions for dividing the representative point.

As shown in FIG. 18, the left diagram shows the state before dividing the representative point, and the case where there is one representative point. In such a case, assuming that the data points included in the cluster have a uniform distribution, the expected value of the error term in each dimension is σ _n ² /12. The term “error term” as used herein refers to a partial term of Σmin(x−u) ² of the objective function shown in Expression (18). The expected value of the error term is obtained by the following formula of the expected value of uniform distribution.
^{V (x) = (b-} a) 2/12 (a: lower limit, b: upper limit)

The right figure shows a state after the representative point is divided, and there are two representative points. In such a case, assuming that the data points included in the cluster have a uniform distribution, the expected value of the error term in the divided direction is σ _n ² /48(= It becomes ^{_{(σ n / 2) 2/}} 12). The condition that the expected value of the error term when the number of representative points is two is smaller than the expected value when the number of representative points is one is the above formula (4) from the following formula (5). In addition, in the equation (5), the expected values of the error terms of each dimension are added.
^{_{w (σ 1 2/12 +}} ··· + σ n 2/12 + ···) + λ 2 ≧ w (σ 1 2/12 + ··· + σ n 2/48 + ···) + 2λ 2 ··· (5)

The above equation (5) can be expressed by the following equation (32). In Expression (32), w ₁ is the weight of the representative point 1 of one cluster in the case of being divided, and w ₂ is the weight of the representative point 2 of the other cluster in the case of being divided.
w (expected value of distance between data point and representative point)≧w ₁ (expected value of distance of data point included in representative point 1 after division)+w ₂ (of data point included in representative point 2 after division) Expected value of distance) + λ ² (32)

Returning to FIG. 15, in the case where the representative point dividing unit 31 satisfies the condition of Expression (4), an example in which the representative point is divided into two around the representative point with the dimension n satisfying the condition will be described below. Show. For example, it is assumed that the (center, weight, maximum value, minimum value) of the original representative point is (u _old , w _old , p _old , q _old ). u _old includes a one-dimensional value u(1) to a d-dimensional value u(d). p _old includes one-dimensional value p(1) to d-dimensional value p(d). q _old includes a one-dimensional value q(1) to a d-dimensional value q(d).

It is assumed that the representative point is divided into two in the nth dimension. At this time, the values (u ₁ , w ₁ , p ₁ , q ₁ ) and (u _r , w _r , p _r , q _r ) of the two representative points after the division are equal to or less than the values of the nth dimension, respectively. The equations (6) to (13) are updated, and the values of the original representative points are inherited except for the n-th dimension.
u ₁ (n)=(u(n)+q(n))/2 (6)
_{w 1 = w old (u (} n) -q (n)) / (p (n) -q (n)) ··· (7)
p ₁ (n)=u(n) (8)
q ₁ (n)=q(n) (9)
_{u r (n) = (u} (n) + p (n)) / 2 ··· (10)
w _r =w _old (p(n)-u(n))/(p(n)-q(n)) (11)
_pr (n)=p(n)...(12)
q _r (n)=u(n) (13)

Further, when adding a data point to a certain representative point, the representative point dividing unit 31 sequentially updates the representative point. For example, it is assumed that the (center, weight, maximum value, minimum value) of the representative point is (u _old , w _old , p _old , q _old ). Let the input data point be x. Then, the (center, weight, maximum value, minimum value) of the updated representative point becomes (u _new , w _new , p _new , q _new ). u _new , w _new , p _new , and q _new are represented by the following equations (14) to (17), respectively.
u _new =(w _old u _old +x)/(w _old +1) (14)
w _new =w _old +1 (15)
p _new =max(p _old ,x) (16)
q _new =min(q _old , x) (17)

The clustering unit 14A executes the batch clustering process using the weighted representative points included in the grid in the grid list 21 as input. However, in the case of a weighted representative point, the objective function changes from Expression (3) to Expression (18) below. Note that x is an input d-dimensional data point group, u is the center of the cluster, k is the number of clusters, and λ is a parameter that determines the granularity of the cluster. And w is a weight.

In this way, since the objective function changes, the condition for generating a new cluster changes so as to generate a new cluster when the Euclidean distance is λ/√w or more. That is, the clustering unit 14A adds the representative point to the central set of the cluster when the distance between the representative point and the center having the shortest distance in the central set of the cluster is λ/√w or more. That is, the clustering 14A generates a new cluster centered on this representative point. Note that the above condition is the case where Euclidean distance is used as the distance function for determining the cluster addition condition, and equivalent conditions exist even when other functions are used. For example, when the square Euclidean distance is used as the distance function, the condition for generating a new cluster is λ ² /w, but the square Euclidean distance is the square of the Euclidean distance. It is equivalent to the conditions used.

[Flowchart of representative point division processing]
Next, a flowchart of representative point division processing according to the second embodiment will be described with reference to FIG. FIG. 19 is a diagram illustrating a flowchart of representative point division processing according to the second embodiment. It should be noted that the representative point dividing unit 31 acquires a representative point point group X, a representative point weight w, a representative point range R, a parameter λ defining the cluster granularity, and an input data point x as input parameters.

First, the representative point dividing unit 31 sets the corresponding representative point candidate x_a to null as an initial value, and sets the nearest distance d_a to λ ² (step S61). The corresponding representative point candidate means a representative point candidate to be divided and corresponding.

The representative point dividing unit 31 determines whether or not all the representative points have been extracted from the representative point group X (step S62). When it is determined that all the representative points have not been extracted (step S62; No), the representative point dividing unit 31 extracts the coordinate x_c, weight w_c, and range r_c of one representative point from the representative point group X (step S62). S63).

The representative point dividing unit 31 calculates the distance between the coordinate x_c of the representative point and the input data point x, and sets the calculated distance to d_c (step S64). The representative point dividing unit 31 determines whether or not the distance d_c is smaller than the nearest distance d_a (step S65). When it is determined that the distance d_c is not smaller than the nearest distance d_a (step S65; No), the representative point dividing unit 31 proceeds to step S62 to retrieve the next representative point.

On the other hand, when it is determined that the distance d_c is smaller than the nearest distance d_a (step S65; Yes), the representative point dividing unit 31 adds the input data point x to the current representative point, and updates the range. Calculate r_a (step S66). For example, the representative point dividing unit 31 uses Equation (16) and Equation (17) to calculate the updated range when the current representative point is updated.

The representative point dividing unit 31 calculates the diameter σ_a of the representative point from the updated range r_a (step S67), and extracts the maximum diameter from the calculated diameter σ_a (step S68). Then, the representative point dividing unit 31 determines whether w_c+1≧16(λ/σ_a) ² and the input data point x is outside the current representative point range r_c (step S69). If it is determined that w_c+1≧16(λ/σ_a) ² and the input data point x is outside the current representative point range r_c (step S69; Yes), the representative point dividing unit 31 determines the next representative point. In order to take out, the process proceeds to step S62. That is, even if w_c+1≧16(λ/σ_a) ² is satisfied, the representative point dividing unit 31 does not consider it as a corresponding representative point candidate if the current representative point range r_c is outside. Transition.

On the other hand, if it is determined that w_c+1<16(λ/σ_a) ² or the input data point x is not outside the current representative point range r_c (step S69; No), the representative point dividing unit 31 determines that the corresponding representative point is the corresponding representative point. The candidate x_a is set to the current representative point x_c (step S70). Then, the representative point dividing unit 31 proceeds to step S62 to retrieve the next representative point.

When it is determined in step S62 that all the representative points have been extracted (step S62; Yes), the representative point dividing unit 31 determines whether the corresponding representative point candidate x_a is null (step S71). When it is determined that the corresponding representative point candidate x_a is null (step S71; Yes), the representative point dividing unit 31 adds the input data point x to the representative point group X as a representative point. At this time, the representative point dividing unit 31 sets the weight w of the representative point to 1, and sets the range R of the representative point to x as the maximum value and x as the minimum value (step S72). Then, the representative point dividing unit 31 ends the representative point dividing process.

On the other hand, when it is determined that the corresponding representative point candidate x_a is not null (step S71; No), the representative point dividing unit 31 updates the coordinates, weight, and range of the corresponding representative point candidate x_a (step S73). That is, the representative point dividing unit 31 adds the input data point x to the corresponding representative point candidate x_a. For example, the representative point dividing unit 31 adds the input data point x to the corresponding representative point candidate x_a and updates the coordinates of the corresponding representative point candidate x_a by using Expression (14). Using the equation (15), the representative point dividing unit 31 adds the input data point x to the corresponding representative point candidate x_a and updates the weight w_a of the corresponding representative point candidate x_a. Using the equation (16), the representative point dividing unit 31 adds the input data point x to the corresponding representative point candidate x_a and updates the maximum value of the corresponding representative point candidate x_a. Using the equation (17), the representative point dividing unit 31 adds the input data point x to the corresponding representative point candidate x_a and updates the minimum value of the corresponding representative point candidate x_a.

Then, the representative point division unit 31 determines whether the updated weight w_a and diameter σ_a satisfy w_a≧16(λ/σ_a) ² (step S74). When it is determined that the updated weight w_a and the diameter σ_a satisfy w_a≧16(λ/σ_a) ² (step S74; Yes), the representative point dividing unit 31 determines the representative point of the corresponding representative point candidate x_a. Divide (step S75). For example, the representative point dividing unit 31 divides the representative point of the corresponding representative point candidate x_a by using the equations (6) to (13). Then, the representative point dividing unit 31 ends the representative point dividing process.

When it is determined that the updated weight w_a and the diameter σ_a do not satisfy w_a≧16(λ/σ_a) ² (step S74; No), the representative point dividing unit 31 determines the representative point of the corresponding representative point candidate x_a. The representative point dividing process is terminated without dividing the.

[Flowchart of clustering process]
FIG. 20 is a diagram illustrating a flowchart of the clustering process according to the second embodiment. Note that FIG. 20 illustrates a case where the weighted DP-means method is applied and the Euclidean distance is used as the distance function used when determining addition of a cluster. The clustering unit 14A acquires, as input parameters, the representative point group X, the representative point weight w, and the parameter λ that defines the cluster granularity.

The clustering unit 14A substitutes the centroids of all the representative points into the center set U of the cluster (step S81). The clustering unit 14A determines whether or not they have converged (step S82). When it is determined that they have not converged (step S82; No), the clustering unit 14A extracts the representative point x from the representative point group (step S83). Then, the clustering unit 14A extracts the center u having the shortest distance from the cluster center set U (step S84).

The clustering unit 14A determines whether or not the distance between the representative points x and u is λ/√w or more (step S85). When it is determined that the distance between the representative points x and u is λ/√w or more (step S85; Yes), the clustering unit 14A adds the representative points x to the central set U of the clusters (step S86). .. Then, the clustering unit 14A proceeds to step S87.

On the other hand, when it is determined that the distance between the representative points x and u is not greater than or equal to λ/√w, that is, less than λ/√w (step S85; No), the clustering unit 14A proceeds to step S87. In step S87, the clustering unit 14A updates the label of the representative point x to the label of the nearest cluster (step S87).

Subsequently, the clustering unit 14A determines whether all representative points x have been extracted from the representative point group (step S88). When it is determined that all the representative points x have not been extracted (step S88; No), the clustering unit 14A proceeds to step S83 in order to extract the next representative point.

On the other hand, when it is determined that all the representative points x have been extracted (step S88; Yes), the clustering unit 14A extracts the cluster center u from the cluster center set U (step S89). The clustering unit 14A updates the extracted coordinate value of u to the weighted centroid value of the representative point labeled with u (step S90).

Then, the clustering unit 14A determines whether the centers u of all clusters have been extracted from the cluster center set U (step S91). When it is determined that the centers u of all the clusters have not been extracted (step S91; No), the clustering unit 14A proceeds to step S89 in order to extract the centers of the next clusters. On the other hand, when it is determined that the centers u of all the clusters have been extracted (step S91; Yes), the clustering unit 14A proceeds to step S82 to make a convergence determination.

Then, the clustering unit 14A proceeds to step S82 so as to make a convergence determination. When it is determined in step S82 that the values have converged (step S82; Yes), the clustering unit 14A outputs the central set U of clusters (step S92) and ends the clustering process.

[Effect of Embodiment 2]
According to the second embodiment, the information processing device 1 holds the range of data points included in the new representative point. When the weighting of the new representative point exceeds a value that is inversely proportional to the square of the parameter indicating the range of data points included in the new representative point, the information processing apparatus 1 sets the new representative point as a different cluster. To divide. According to such a configuration, the information processing apparatus 1 performs clustering such that the objective function value becomes small by dividing the representative points into different clusters when the numerical value of the data points exceeds a predetermined value. be able to. That is, the information processing device 1 can perform clustering without lowering the accuracy even when using the representative points.

Further, according to the second embodiment, the information processing apparatus 1 sets the threshold of the distance from the cluster center that is allowed as the same cluster when performing the clustering processing using the weighted representative points, as the square root of the weight of the representative points. The value is inversely proportional to. With this configuration, when performing the weighted clustering, the information processing apparatus 1 performs the clustering with high accuracy by setting the threshold value of the distance from the cluster center that is allowed as the same cluster in consideration of the weighting. be able to.

By the way, in the second embodiment, the clustering unit 14A has been described as executing the batch clustering process by inputting the weighted representative points and changing the objective function from Expression (3) to Expression (18). That is, the clustering unit 14A allocates each representative point to the nearest cluster, and if the distance between the input weighted representative point and the center of the nearest cluster is λ/√w or more, a new cluster is generated. To do. Note that w is the weight of the input representative point, and λ is a parameter that determines the granularity of the cluster. However, the clustering unit 14A is not limited to this, and may cluster (integrate) two nearby weighted representative points.

Therefore, in a third embodiment, in clustering using weighted representative points, a case will be described in which nearby weighted representative points are clustered (integrated).

[Configuration of Information Processing Device According to Third Embodiment]
FIG. 21 is a functional block diagram of the configuration of the information processing apparatus according to the third embodiment. The same components as those of the information processing device 1 shown in FIG. 15 are designated by the same reference numerals, and the description of the overlapping components and operations will be omitted. The difference between the second embodiment and the third embodiment is that the clustering unit 14A is changed to the clustering unit 14B. The difference between the second embodiment and the third embodiment is that a cost function table 23, a representative point/cluster correspondence table 24, and a cluster center set 25 are added to the storage unit 20.

The clustering unit 14B selects and integrates two representative points from the plurality of representative points. For example, the clustering unit 14B selects two representative points from the plurality of representative points using the cost function, and integrates the two representative points when the condition for integrating the two representative points is met. . The cost function here is a function for calculating the improvement width when the two representative points are provisionally integrated. The details of the cost function and the condition for integrating the two representative points will be described later. Further, the process of selecting and integrating two objects can be realized by the Merge algorithm. As an example, the Merge algorithm can use the technique described in “J. Lee et al., “Online video segmentation by Bayesian split-merge clustering”, In ECCV 2012.”.

Here, the data structure of the cost function table 23 will be described with reference to FIG. FIG. 22 is a diagram illustrating an example of the data structure of the cost function table according to the third embodiment. As shown in FIG. 22, the cost function table 23 stores cost function values for two representative point IDs. The representative point ID is an ID (Identifier) for identifying the representative point. As an example, the cost function value for two representative point IDs “1” and “2” is −0.5. The cost function value for the two representative point IDs “1” and “3” is 0.3. The cost function value depends on the design of the cost function. For example, the smaller the cost function value, the larger the improvement range.

The data structure of the representative point/cluster correspondence table 24 will be described with reference to FIG. FIG. 23 is a diagram illustrating an example of the data structure of the representative point/cluster correspondence table according to the third embodiment. As shown in FIG. 23, the representative point/cluster correspondence table 24 stores representative point IDs and cluster IDs in association with each other. The representative point ID is an ID for identifying the representative point. The cluster ID is an ID that identifies a cluster. As an example, when the representative point ID is “1”, “1” is stored as the cluster ID. When the representative point ID is "2", "1" is stored as the cluster ID. That is, the clusters having the representative point IDs “1” and “2” are the same.

The data structure of the cluster center set 25 will be described with reference to FIG. FIG. 24 is a diagram illustrating an example of the data structure of the cluster center set according to the third embodiment. As shown in FIG. 24, the cluster center set 25 stores cluster IDs and cluster centers in association with each other. The cluster ID is an ID that identifies a cluster. The cluster center is the center coordinate of the cluster. As an example, when the cluster ID is “1”, (0.1, 0.2, 0.3,...) Is stored as the center of the cluster.

[One Example of Flow of Clustering Processing]
FIG. 25 is a diagram illustrating an example of the flow of clustering processing according to the third embodiment. It is assumed that the larger the improvement width, the smaller the value of the cost function.

As shown in the left diagram of FIG. 25, the clustering unit 14B calculates the improvement width of the cost function when the two representative points are temporarily integrated. As an example, the clustering unit 14B selects the representative point d ₁₁ of “1” and the representative point d ₁₃ of “3” as the representative point numbers, and shows the improvement range of the cost function when the two selected representative points are integrated. calculate. Here, the value of the cost function of the representative point d ₁₁ of the representative point number “1” and the representative point d ₁₃ of the representative point number “3” is 0.3. Clustering unit 14B selects a representative point d ₁₁ of "1" representative points d ₁₂ of "2" as the representative point number, to calculate the improved width of the cost function in the case of integrating the two representative points selected. Here, the value of the cost function of the representative point d ₁₁ of the representative point number “1” and the representative point d ₁₂ of the representative point number “2” is −0.5. Similarly, the clustering unit 14B calculates the improvement width of the cost function when the other two representative points are temporarily integrated.

As shown in the middle diagram of FIG. 25, the clustering unit 14B selects two representative points with the largest improvement in the cost function. Here, the two representative points having the largest improvement in the cost function are the two representative points indicated by the representative point d ₁₁ of the representative point number “1” and the representative point d ₁₂ of the representative point number “2”.

As shown in the right diagram of FIG. 25, the clustering unit 14B integrates two selected representative points when the selected two representative points meet the integration condition. Here, the clustering section 14B integrates the representative point d ₁₁ and the representative point representative point d ₁₂ of number "2" of the representative point number "1", representative point number representative points d ₁₂ of the representative point number "2" It is assumed that the representative point d ₁₁ of “1” is integrated. Then, the clustering unit 14B is a representative point d ₁₁ of the representative point number "1", a weighted center of gravity of the two representative points cluster ID is updated to "1" and the weighted center of gravity d ₁₁ to be _'. Then, the clustering unit 14B recalculates the integrated representative point d ₁₁ ′ and the cost functions of the other representative points.

Then, the clustering unit 14B uses the recalculated result to select two representative points with the largest improvement in the cost function, and continues the clustering process until the selected two representative points do not satisfy the integration condition. ..

[Conditions for integrating representative points]
Here, the conditions for integrating the representative points will be described with reference to FIG. FIG. 26 is a diagram illustrating conditions for integrating representative points according to the third embodiment.

As shown in FIG. 26, the left diagram shows a state before the representative points are integrated, and the case where there are two representative points. The right figure shows the state after the representative points are integrated, and the case where there is one representative point. In such a case, the condition for integrating the representative points is that the expected value of the objective function is smaller when the representative points are integrated than before the representative points are integrated, due to the same discussion as the condition for dividing the representative points. .. That is, if the expected value of the objective function when the two representative points are integrated into one is smaller than the expected value of the objective function of the two representative points as they are, it is better to integrate the two representative points.

When the representative point is weighted, the expected value of the objective function is calculated by the formula (18) using the product of the weight of the representative point and the expected value of the distance. That is, the expected value of the objective function when the two representative points are integrated into one is the sum of the weights of the two representative points and the expectation of the distance between the data points included in the two representative points and the representative point of the integration destination. It is calculated using the product of the value and the term calculated from the parameters that define the cluster granularity. When the two representative points are not integrated into one point, the expected value of the objective function is the weight of one representative point (first representative point) and the distance between the data point included in the first representative point and the first representative point. The cluster granularity is determined by summing the product of the expected values, the weight of the other representative point (second representative point) and the product of the expected values of the distances between the data points included in the second representative point and the second representative point. And the term calculated from the parameters.

[Cost function]
Here, the cost function when the representative points have a uniform distribution is represented by, for example, the following Expression (19). Note that C ₁ and C ₂ are representative points, respectively. w ₁ is the weight of C ₁ and w ₂ is the weight of C ₂ . d ₁ is the distance between the representative point after integration (weighted center of gravity of C ₁ and C ₂ ) and C _1, and d ₂ is the representative point after integration (weighted center of gravity of C ₁ and C ₂ ) It is the distance from C ₂ . λ is a parameter that determines the granularity of the cluster.
_{S COST (C 1, C 2} ) = w 1 × d 1 2 + w 2 × d 2 2 -λ 2 ··· (19)

Derivation of the cost function represented by Expression (19) will be described with reference to FIG. FIG. 27 is a diagram illustrating a premise for deriving the cost function according to the third embodiment.

As shown in FIG. 27, the left diagram shows a state before the representative points are integrated, and the case where there are two representative points. C ₁ is a representative point having a weight of w ₁ . σ _1n is an n-dimensional range of the representative point C ₁ . C ₂ is a representative point having a weight of w ₂ . σ _2n is an n-dimensional range of the representative point C ₂ . Under such a premise, the expected value of the error of the data point included in the representative point C ₁ is represented by the following formula (20). In addition, in Expression (20), the expected values of the error terms of each dimension are added.
Expected value of data point error k ₁ =(σ ₁₁ ² _{/12+...+σ 1n} ² /12+...) (20)

Similarly, the expected value of the error of the data point included in the representative point C ₂ is expressed by the following equation (21). In addition, in the expression (21), the expected values of the error terms of each dimension are added.
Expected value of data point error k ₂ =(σ ₂₁ ² /12+...+σ _2n ² /12+...) (21)

The right figure shows the state after the representative points are integrated, and the case where there is one representative point. C ₁ and C ₂ are the same as in the left figure. σ′ _1n is a range between the representative point after the n-dimensional integration and the representative point C ₁ , and d ₁ is the distance between the representative point after the integration and C ₁ . σ′ _2n is the range between the representative point and the representative point C ₂ after the n-dimensional integration, and d ₂ is the distance between the representative point and the C ₂ after the integration. Under such a premise, the expected value of the error of the dimension n with the data point included in the representative point C ₁ is represented by the following formula (22).

Therefore, the expected value of the error of the data point included in the representative point C ₁ is expressed by the following equation (23). Note that in the equation (23), the expected values of the error terms of each dimension are added.
Expected value of the error data points ^{_{g 1 = (σ '11 2}} + ··· + σ' 1n 2 + ···) + (σ 11 2/12 + ··· + σ 1n 2/12 + ···) ··· (23)
^{_{Incidentally, (σ '11 2 + ···}} + σ' 1n 2 + ···) correspond to _d ^{1 2} illustrating the distance between the representative point and _{C 1} after integration.

Similarly, the expected value of the error of the data point included in the representative point C ₂ is expressed by the following equation (24). Note that in the equation (24), the expected values of the error terms of each dimension are added.
Expected value of the error data points ^{_{g 2 = (σ '21 2}} + ··· + σ' 2n 2 + ···) + (σ 21 2/12 + ··· + σ 2n 2/12 + ···) ··· (24)
Note that (σ′ ₂₁ ² +... +σ′ _2n ² +...) Corresponds to d ₂ ² indicating the distance between the representative point after integration and C ₂ .

The expected value M ₁ of the objective function when the number of the representative points is 1 is obtained by substituting the equations (23) and (24) into the objective function for the weighted representative point shown in the equation (18). 25).
M ₁ =w ₁ ×g ₁ +w ₂ ×g ₂ +λ ² ={d ₁ ² +(σ ₁₁ ² _{/12+...+σ 1n} ² _{/12+...)}+w 2} ×{d ₂ ² +(σ ^{_{21 2/12 + ··· + σ}} 2n 2/12 + ···)} + λ 2 ··· (25)

The expected value M ₂ of the objective function when the number of representative points is 2 can be obtained by substituting Equation (20) and Equation (21) into the objective function for the weighted representative point shown in Equation (18). 26).
_{M 2 = w 1 × k 1} + w 2 × k 2 + 2λ 2 = w 1 × (σ 11 2/12 + ··· + σ 1n 2/12 + ···)} + w 2 × (σ 21 2/12 + ··· +σ _2n ² /12+...) +2λ ² ... (26)

The cost function S _COST (C ₁ , C ₂ ) is calculated from the expected value M ₁ of the objective function when the number of representative points is 1 (25) to the expected value M ₂ of the objective function when the number of representative points is 2 ( Since it is a formula obtained by subtracting 26), it can be expressed by formula (19). That is, if the cost function S _COST (C ₁ , C ₂ ) is 0 or less, it is better to integrate the _two representative points C ₁ and C ₂ .

Note that it has been described that the expected value of the error of the data point is calculated using the distance d between the representative point after integration and the representative point K. The expected value of the error of the data point is not limited to this, and the information of the representative point before integration is stored, and the distance between the representative point K and the representative point before integration and the representative point K and the representative point after integration are stored. An error with the distance may be calculated. Such cost function in the case of using the expected value of the error data points _{S COST (C 1, C 2} ) is expressed by the following equation (27). It should be noted that d _old,K indicates the distance between the representative point K and the representative point before integration (cluster center), and d _new,K indicates the distance between the representative point K and representative point after integration (cluster center). Show.

As a result, by using the information of the representative points before and after the integration when the data is integrated as the expected value of the error of the data points, it is possible to prevent the error from accumulating due to the loss of the representative points before the integration. ..

[Flowchart of clustering process]
FIG. 28 is a diagram illustrating a flowchart of the clustering process according to the third embodiment. Note that FIG. 28 illustrates a case where the Merge algorithm is applied and the Euclidean distance is used as the distance function used when determining addition of a cluster. The clustering unit 14B acquires the representative point group X, the representative point weight w, and the maximum allowable cluster diameter λ as input parameters. The maximum allowable cluster diameter corresponds to a parameter that defines the cluster grain size.

The clustering unit 14B calculates the cost function value S _COST when the representative points x _i and x _j are integrated, and substitutes the calculated result into the cost function table 23 (step S101). Note that i and j are representative point IDs (representative point numbers). The clustering unit 14B substitutes the representative point group X into the center set U of the cluster (step S102). Then, the clustering unit 14B initializes the value of each cluster ID in the representative point/cluster correspondence table 24 with the representative point ID (step S103).

Subsequently, the clustering unit 14B acquires the pair (i, j) of the representative point IDs when the cost function becomes the minimum from the cost function table 23 (step S104). The clustering unit 14B determines whether the cost function value (i, j) is 0 or more (step S105). When it is determined that the cost function value (i, j) is 0 or more (step S105; Yes), the clustering unit 14B proceeds to step S110.

On the other hand, when determining that the cost function value (i, j) is less than 0 (step S105; No), the clustering unit 14B determines that the representative point ID is “j” in the representative point/cluster correspondence table 24. The cluster ID that is "" is changed to "i" (step S106). The clustering unit 14B may change the cluster ID whose representative point ID is "i" to "j".

Then, the clustering unit 14B sets the centroid of the cluster having the cluster ID “i” in the cluster center set 25 as the weighted centroid of the representative points having the cluster ID “i” in the representative point/cluster correspondence table 24. Update (step S107). The clustering unit 14B deletes the cluster (representative point) whose cluster ID is "j" in the cluster center set 25 (step S108).

Then, the clustering unit 14B recalculates the cost function value S _COST from the updated cluster information, and updates the value of the cost function table 23 (step S109). Then, the clustering unit 14B moves to step S104.

In step S110, the clustering unit 14B outputs the cluster center set 25 (step S110). Then, the clustering unit 14B ends the clustering process.

[Effect of Example 3]
According to the third embodiment, the information processing apparatus 1 selects two representative points when performing the clustering process using the representative points, and expects the objective function when the two representative points are integrated into one point. When the value is smaller than the expected value of the objective function when the two representative points are not integrated into one point, the two representative points are integrated into one point. With such a configuration, the information processing device 1 can perform clustering without lowering the accuracy even when using the representative points.

By the way, in the third embodiment, the clustering unit 14B integrates the two representative points, when the two representative points meet the condition of integration, and sets the integration-destination representative point to the weighted center of gravity of the two representative points. To update. However, the clustering unit 14B is not limited to this, and may update the integration-destination representative point to either one of the representative points when the two representative points meet the integration condition.

Therefore, the clustering unit 14B according to the fourth embodiment integrates these two representative points and updates the representative point of the integration destination to either one of the representative points when the two representative points meet the condition of integration. A case will be described.

[Configuration of Information Processing Device According to Fourth Embodiment]
Since the configuration of the information processing device 1 according to the fourth embodiment is the same as that of the information processing device 1 according to the third embodiment, the same reference numerals are used and the description of the overlapping configuration is omitted.

[Overview of clustering process]
FIG. 29 is a diagram illustrating an outline of the clustering process according to the fourth embodiment. As shown in FIG. 29, when the two representative points are integrated, the clustering unit 14B does not integrate them into the center of gravity of the two representative points, but integrates into one of the two representative points. Here, the clustering section 14B, when integrating the representative point _{d 21} and the representative point _{d 22,} integrated into the representative point _{d 21} of the representative point _{d 21, d 22.} As a result, the clustering unit 14B does not move the representative point of the integration destination even if the integration is performed, so that there is no problem that the coordinates of the representative points move due to the integration and the representative points that should be originally integrated are not integrated. .. That is, when the representative point moves in the integration operation, the clustering unit 14B does not have the problem that the integration condition is satisfied if it is not moved, but the moving point is not satisfied.

[One Example of Flow of Clustering Processing]
FIG. 30 is a diagram illustrating an example of the flow of clustering processing according to the fourth embodiment. It is assumed that the larger the improvement width, the smaller the value of the cost function.

As shown in the upper left diagram of FIG. 30, the clustering unit 14B calculates the improvement width of the cost function when the two representative points are provisionally integrated. As an example, the clustering unit 14B selects the representative point d ₁₁ of “1” and the representative point d ₁₃ of “3” as the representative point numbers, and shows the improvement range of the cost function when the two selected representative points are integrated. calculate. Here, the value of the cost function of the representative point d ₁₁ of the representative point number “1” and the representative point d ₁₃ of the representative point number “3” is 0.3. Clustering unit 14B selects a representative point d ₁₁ of "1" representative points d ₁₂ of "2" as the representative point number, to calculate the improved width of the cost function in the case of integrating the two representative points selected. Here, the value of the cost function of the representative point d ₁₁ of the representative point number “1” and the representative point d ₁₂ of the representative point number “2” is −0.5. Similarly, the clustering unit 14B calculates the improvement width of the cost function when the other two representative points are temporarily integrated.

As shown in the middle diagram in the upper part of FIG. 30, the clustering unit 14B selects two representative points with the largest improvement in the cost function. Here, the two representative points having the largest improvement in the cost function are the two representative points indicated by the representative point d ₁₁ of the representative point number “1” and the representative point d ₁₂ of the representative point number “2”.

As shown in the upper right diagram of FIG. 30, the clustering unit 14B integrates two selected representative points when the selected two representative points meet the integration condition. Here, the clustering unit 14B integrates the representative point d ₁₁ having the representative point number “1” and the representative point d ₁₂ having the representative point number “2”, and the representative point d ₁₂ having the representative point number “2” is used as the representative point number. It is assumed that the representative point d ₁₁ of “1” is integrated. Then, the clustering unit 14B updates, in the cost function table 23, only the value of the cost function having one of the representative points of the representative point number “2” that disappears due to the integration. Here, in the cost function table 23, the value of the cost function having one of the representative points with the representative point number “2” is updated to “∞”. That is, the clustering section 14B is in this timing, the representative point d ₁₁ of the representative point number "1", a weighted center of gravity of the two representative points cluster ID does not update the weighted centroid becomes "1". Then, the clustering unit 14B further selects two representative points with the largest improvement in the cost function, and continues the clustering process until the selected two representative points do not satisfy the integration condition.

As shown in the lower left diagram in FIG. 30, the clustering unit 14B adopts the weighted center of gravity of representative points integrated into the same representative point as the coordinates of a new representative point, even if the integration occurs even once. Here, the clustering unit 14B updates the weighted center of gravity of the representative point d ₁₁ of the representative point number “1” integrated into the same representative point to the coordinate g ₀ at which the cluster ID is “1”.

[Cost function]
Here, the cost function when the representative points have a uniform distribution according to the fourth embodiment is represented by, for example, the following Expression (28). Note that C ₁ and C ₂ are representative points, respectively. w ₁ is the weight of C ₁ and w ₂ is the weight of C ₂ . d is the distance between the representative point C ₁ and the representative point C ₂ . λ is a parameter that determines the granularity of the cluster.
S _mCOST (C ₁ , C ₂ )=w ₂ ×d ² −λ ² (28)

Derivation of the cost function represented by Expression (28) will be described with reference to FIG. FIG. 31 is a diagram illustrating a premise for deriving the cost function according to the fourth embodiment.

As shown in FIG. 31, the left diagram shows a state before the representative points are integrated, and the case where there are two representative points. C ₁ is a representative point having a weight of w ₁ . σ _1n is an n-dimensional range of the representative point C ₁ . C ₂ is a representative point having a weight of w ₂ . σ _2n is an n-dimensional range of the representative point C ₂ . Under such a premise, the expected value of the error of the data point included in the representative point C ₁ is the same as in Expression (20). Similarly, the expected value of the error of the data point included in the representative point C ₂ is the same as that in Expression (21).

The right figure shows the state after the representative points are integrated, and the case where there is one representative point. C ₁ and C ₂ are the same as in the left figure. σ′ _n is the range between the representative point C ₁ and the representative point C ₂ in the n-dimensional dimension, and d is the distance between the representative point C ₁ and the representative point C ₂ . Under such a premise, the expected value of the error of the dimension n having the data point included in the representative point C ₂ is represented by the following formula (29).

Therefore, the expected value of the error of the data point included in the representative point C ₂ is represented by the following formula (30). In addition, in the expression (30), the expected values of the error terms of each dimension are added.
Expected value of the error data points ^{_{g 3 = (σ '1 2}} + ··· + σ' n 2 + ···) + (σ 21 2/12 + ··· + σ 2n 2/12 + ···) ··· (30)
It should be noted that (σ′ ₁ ² +... +σ′ _n ² +...) Corresponds to d ² indicating the distance between the representative point C ₁ and the representative point C ₂ .

The expected value of the error of the data point included in the representative point C ₁ is the same as that in Expression (20).

The expected value M ₃ of the objective function when the number of the representative points is 1 is obtained by substituting the equation (30) and the equation (20) into the objective function for the weighted representative point shown in the equation (18). 31).
M ₃ =w ₁ ×k ₁ +w ₂ ×g ₃ =w ₁ ×(σ ₁₁ ² _{/12+...+σ 1n} ² _{/12+...)}+w 2} ×{d ² +(σ ₂₁ ² /12+・) ^{_{·· + σ 2n 2/12 +}} ···)} + λ 2 ··· (31)

The expected value of the objective function when the number of representative points is 2 is the same as that of M ₂ represented by the equation (26).

The cost function S _mCOST (C ₁ , C ₂ ) is the expected value M ₃ of the objective function when the number of representative points is 1 (from the equation (31), the expected value M ₂ of the objective function when the number of representative points is 2) Since it is an expression obtained by subtracting (26), it can be expressed by Expression (28), that is, if the cost function S _mCOST (C ₁ , C ₂ ) is 0 or less, two representative points C ₁ and It is better to integrate C ₂ .

[Flowchart of clustering process]
FIG. 32 is a diagram illustrating a flowchart of the clustering process according to the fourth embodiment. Note that, in FIG. 32, a case will be described in which the Merge algorithm is applied and the Euclidean distance is used as the distance function used when determining addition of a cluster. The clustering unit 14B acquires the representative point group X, the representative point weight w, and the maximum allowable cluster diameter λ as input parameters. The maximum allowable cluster diameter corresponds to a parameter that defines the cluster grain size.

The clustering unit 14B calculates the cost function value S _mCOST when the representative points x _i and x _j are integrated, and substitutes the calculated result into the cost function table 23 (step S121). Note that i and j are representative point IDs (representative point numbers). The clustering unit 14B substitutes the representative point group X into the center set U of the cluster (step S122). Then, the clustering unit 14B initializes the value of each cluster ID in the representative point/cluster correspondence table 24 with the representative point ID (step S123).

Subsequently, the clustering unit 14B acquires the pair (i, j) of the representative point IDs when the cost function becomes the minimum from the cost function table 23 (step S124). The clustering unit 14B determines whether the cost function value (i, j) is 0 or more (step S125). When it is determined that the cost function value (i, j) is 0 or more (step S125; Yes), the clustering unit 14B proceeds to step S129.

On the other hand, when it is determined that the cost function value (i, j) is less than 0 (step S125; No), the clustering unit 14B determines that the representative point ID is “j” in the representative point/cluster correspondence table 24. The cluster ID which is "" is changed to "i" (step S126). The clustering unit 14B may change the cluster ID whose representative point ID is "i" to "j".

Then, the clustering unit 14B deletes the cluster having the cluster ID “j” in the cluster center set 25 (step S127). The clustering unit 14B updates the value of the cost function table 23 whose subscript includes "j" to "∞" (step S128). Then, the clustering 14B moves to step S124.

In step S129, the clustering unit 14B determines whether the integration has occurred once or more (step S129). When it is determined that the integration has occurred once or more (step S129; Yes), the clustering unit 14B performs the following process on the cluster corresponding to the representative point where the integration has occurred. That is, the clustering unit 14B updates the cluster centers in the cluster center set 25 to the weighted center of gravity of the representative points assigned to the cluster in the representative point/cluster correspondence table 24 (step S130).

Then, the clustering unit 14B _{recalculates the} cost function value S _mCOST from the updated cluster information, and updates the values in the cost function table 23 (step S131). Then, the clustering unit 14B moves to step S124.

On the other hand, when it is determined that the integration has not occurred once or more (step S129; No), the clustering unit 14B outputs the cluster center set 25 (step S132). Then, the clustering unit 14B ends the clustering process.

[Effect of Embodiment 4]
According to the fourth embodiment, the information processing apparatus 1 selects one of the two representative points as the representative point of the integration destination, and further, when the integration operation ends, the information of the representative point of the integration destination. Is used to recalculate the coordinates of the representative point of the integration destination. According to this configuration, the information processing device 1 does not move the coordinates of the representative point of the integration destination until the integration operation ends. As a result, the information processing apparatus 1 can prevent the representative points that should have been originally integrated from being unintegrated if the coordinates of the representative points are moved by the integration operation. Further, the information processing device 1 can perform clustering without lowering the accuracy even when using the representative points.

Here, the value of the objective function optimized by each clustering process described in Examples 3 to 4 is calculated as follows by an experiment. First, the value of the objective function optimized by the clustering process by the DP-means method is 7.33×10 ¹¹ , and the calculation time is 321.1219 seconds. The value of the objective function optimized by the clustering process according to the third embodiment is 3.32×10 ¹¹ , and the calculation time is 435.4864 seconds. The value of the objective function optimized by the clustering process according to the fourth embodiment is 3.24×10 ¹¹ , and the calculation time is 434.2837 seconds.

As a result, the value of the objective function optimized by the clustering processing of the third and fourth embodiments becomes smaller than that of other methods. That is, a smaller objective function is obtained when the integration operation using the Merge algorithm is performed. That is, the value of the objective function is improved when the integration operation using the Merge algorithm is performed.

[Other]
In the first embodiment, the clustering unit 14 executes the batch clustering process using the weighted representative points in the grid list 21 as input. At this time, the clustering unit 14 has been described as executing the objective function as Expression (3). However, the clustering unit 14 is not limited to this, and may execute the objective function as Expression (18).

In addition, in the first embodiment, the representative point compressing unit 13 sets another representative point selected from the representative points included in the grid in order to prevent the number of representative points in the grid from exceeding the maximum number of held points. It has been explained that the representative points are merged into a new representative point. However, the representative point compressing unit 13 is not limited to this, and may select neighboring representative points, calculate an average of the positions of the selected representative points, and use the average position as a new representative point.

Further, each component of the illustrated information processing device 1 does not necessarily have to be physically configured as illustrated. That is, the specific mode of distribution/integration of the information processing device 1 is not limited to that shown in the drawings, and all or part of the information processing device 1 may be functionally or physically arranged in arbitrary units according to various loads and usage conditions. It can be distributed and integrated. For example, the representative point updating unit 12 and the representative point compressing unit 13 may be integrated as one unit. Further, the representative point updating unit 12 may be dispersed into a generating unit that generates a grid, an adding unit that adds data points to the grid, and a compressing unit that causes the representative point compressing unit 13 to compress data. The storage unit 20 may be connected as an external device of the information processing device 1 via a network.

The various processes described in the above embodiments can be realized by executing a prepared program on a computer such as a personal computer or a workstation. Therefore, an example of a computer that executes a data clustering program that realizes the same function as the information processing device 1 illustrated in FIG. 1 will be described below. FIG. 33 is a diagram illustrating an example of a computer that executes a data clustering program.

As shown in FIG. 33, the computer 200 includes a CPU 203 that executes various types of arithmetic processing, an input device 215 that receives data input from a user, and a display control unit 207 that controls the display device 209. The computer 200 also includes a drive device 213 that reads a program and the like from a storage medium, and a communication control unit 217 that exchanges data with another computer via a network. The computer 200 also has a memory 201 for temporarily storing various information and an HDD 205. The memory 201, the CPU 203, the HDD 205, the display control unit 207, the drive device 213, the input device 215, and the communication control unit 217 are connected by the bus 219.

The drive device 213 is, for example, a device for the removable disk 211. The HDD 205 stores a data clustering program 205a and data clustering related information 205b.

The CPU 203 reads the data clustering program 205a, expands it in the memory 201, and executes it as a process. Such a process corresponds to each functional unit of the information processing device 1. The data clustering related information 205b corresponds to the grid list 21 and the representative point list 22. Then, for example, the removable disk 211 stores each information such as the data clustering program 205a.

Note that the data clustering program 205a does not necessarily have to be stored in the HDD 205 from the beginning. For example, the program is stored in a “portable physical medium” such as a flexible disk (FD), a CD-ROM, a DVD disk, a magneto-optical disk, or an IC card that is inserted into the computer 200. Then, the computer 200 may read the data clustering program 205a from these and execute it.

DESCRIPTION OF SYMBOLS 1 Information processing apparatus 10 Control part 11 Data acquisition part 12 Representative point update part 13 Representative point compression part 14,14A, 14B Clustering part 20 Storage part 21 Grid list 22,22A Representative point list 23 Cost function table 24 Representative point/cluster correspondence Table 25 Cluster center set 31 Representative point division unit

Claims (19)

In the method of data clustering in streaming clustering, the computer
The feature space where the input data points are placed is divided into local regions,
The representative point is independently determined for each local area where one or more data points exist,
Next, when a data point is added to the local area where the representative point exists, a new representative point is determined by weighting based on the representative point and the added data point,
A data clustering method characterized by executing each process for controlling the number of clusters using a new representative point. In the dividing process, the feature space is a local region that is a d-dimensional hypercube having a side length of λ/√d (λ: a threshold value that determines the granularity of the cluster, d: the number of dimensions of the feature space). The data clustering method according to claim 1, wherein the data clustering method is divided into The dividing process divides the feature amount space into local regions that are d-dimensional hyperspheres (d: the number of dimensions of the feature amount space) having a diameter of a threshold λ that determines the granularity of clusters. The data clustering method according to claim 1. In the process of determining the representative point and the process of determining the new representative point, the maximum number of holding points held in the local area is set to the dimension number d. The described data clustering method. The process of determining the new representative point is to determine the new representative point based on the already-represented representative point and the time-divided data point with respect to the time-divided data point. The data clustering method according to any one of claims 1 to 4. The process for determining the representative point and the process for determining the new representative point are such that the maximum number of points held in the local area is 3×d×log(d). The data clustering method according to Item 3. Retain the range of data points included in the new representative point,
When the weighting of the new representative point becomes equal to or larger than the value inversely proportional to the square of the parameter indicating the range of the data points included in the new representative point, the new representative point is divided into different clusters. The data clustering method according to claim 1, wherein: If the expected value of the objective function when the representative point is set to 1 with respect to the new representative point is equal to or larger than the expected value of the objective function when the representative point is divided into two points, The data clustering method according to claim 1, wherein the points are divided. For the new representative point, a value obtained by weighting the representative point and a product of an expected value of a distance between the data point included in the representative point and the representative point is a first value obtained when the representative point is divided. Weighting of representative points, product of expected value of distance between data points included in the first representative point and the first representative point, weighting of the second representative point when the representative point is divided, and the second representative If the product of the expected value of the distance between the data point included in the point and the second representative point and the sum of the term calculated from the threshold value that determines the cluster granularity is greater than or equal to the representative point, the representative point The data clustering method according to claim 1, wherein When performing the clustering process using the representative point group including the representative points divided by the dividing process, the threshold value of the distance from the cluster center allowed as the same cluster is a value inversely proportional to the square root of the weighting of the representative points. The data clustering method according to any one of claims 7 to 9. Expectation of the objective function when two representative points are selected and the two representative points are integrated into one point when performing the clustering processing using the representative point group including the representative points divided by the dividing processing The two representative points are integrated into one point when the value is smaller than the expected value of the objective function when the two representative points are not integrated into one point. The data clustering method according to any one of 1. In the process of selecting the two representative points, the expected value of the objective function when the two representative points are not integrated into one point is calculated from the expected value of the objective function when the two representative points are integrated into one point. The data clustering method according to claim 11, wherein a cost function having a subtracted value is defined, and the two representative points having the minimum value of the cost function are selected. The data clustering according to claim 12, wherein when the value of the cost function of the two representative points selected by the selecting process is 0 or less, the two representative points are integrated into one point. Method. As the expected value of the objective function when the two representative points are integrated into one point, the sum of the weights of the two representative points and the distance between the data points included in the two representative points and the representative point of the integration destination are calculated. Using the product of the expected value and the term calculated from the threshold value that determines the cluster granularity, as the expected value of the objective function when the two representative points are not integrated into one point, the weighting of the first representative point and the first representative point are performed. The product of the expected value of the distance between the data point included in one representative point and the first representative point, the weighting of the second representative point, and the distance between the data point included in the second representative point and the second representative point. 13. The data clustering method according to claim 11 or 12, wherein a sum calculated from a product of expected values of and a term calculated from a threshold value that determines the cluster granularity is used. The cost function is calculated from a threshold value by multiplying the weight of the two representative points by the product of the coordinates of the two representative points and the distance of the coordinates of the representative points when the two representative points are integrated. The data clustering method according to claim 12, wherein the number of terms is reduced. As a method of calculating the product of the weight of the representative point and the expected value of the distance between the representative point and a predetermined data point, information of the representative point before integration, which is integrated into a certain representative point, even if integration occurs Is stored, and an error between the distance between the representative point before the integration and the predetermined data point and the distance between the representative point after the integration and the predetermined data point is used. The described data clustering method. As the expected value of the objective function when the two representative points are integrated into one point, the sum of the weights of the two representative points and the distance between the data points included in the two representative points and the representative point of the integration destination are calculated. Using the product of the expected value and the term calculated from the threshold value that determines the cluster granularity, as the expected value of the objective function when the two representative points are not integrated into one point, the weighting of the first representative point and the first representative point are performed. The product of the expected value of the distance between the data point included in one representative point and the first representative point, the weighting of the second representative point, and the distance between the data point included in the second representative point and the second representative point. And a term calculated from a threshold value that defines the cluster grain size,
The cost function is to subtract the term calculated from the threshold from the product of the weight of the representative point to be integrated and the distance between the representative point to be integrated and the representative point of the integration destination,
One of the selected two representative points is selected as the representative point of the integration destination, and when the integration operation is completed, the representative of the integration destination is used by using the information of the representative point of the integration destination. Recalculate point coordinates
The data clustering method according to claim 12, wherein: A dividing unit that divides the feature amount space in which the input data points are arranged into local regions,
A first determining unit that independently determines a representative point for a local region having one or more data points;
Next, when a data point is added to the local area where the representative point exists, a second deciding unit that decides a new representative point by weighting based on the representative point and the added data point,
An information processing apparatus, comprising: a control unit that controls the number of clusters using a new representative point. In the data clustering program in streaming clustering, in the computer,
The feature space where the input data points are placed is divided into local regions,
The representative point is independently determined for each local area where one or more data points exist,
Next, when a data point is added to the local area where the representative point exists, a new representative point is determined by weighting based on the representative point and the added data point,
A data clustering program that executes a process for controlling the number of clusters using a new representative point.

Images