JP6334455B2 - Clustering apparatus, method, and program - Google Patents

Description

  The present invention relates to a clustering apparatus, method, and program, and more particularly, to a clustering apparatus, method, and program for determining the degree of attribution of a data point to a plurality of clusters.

  As shown in FIG. 12, when classifying each of a plurality of data points to be classified into a plurality of clusters according to the degree of belonging, optimization is performed by alternately updating the cluster belonging degree and updating the cluster center. For each of the clusters, a plurality of data is classified and the cluster membership is output.

  As shown in FIG. 13, in the cluster membership update, the membership to a plurality of clusters is updated for each of a plurality of data points based on the distance to the plurality of clusters and the softening parameter.

  In the cluster center update process, each cluster center is reset based on the position of each data point and the degree of attribution of each data point to each cluster. The cluster membership update process and the cluster center update process are alternately optimized until convergence.

  Conventionally, with respect to each data point, the Lloyd method (Non-patent Document 1) that limits the number of clusters to one to each cluster is extended by giving the degree of belonging to each cluster as a continuous value from 0 to 1. The performed FCM method (Non-patent Document 2) is used.

Least squares quantization in PCM, IEEE Transaction on Information Theory, 1982 FCM-The Fuzzy c-Means Clustering Algorithm, Computers & Geosciences, 1984

  However, the cost of distance calculation in the cluster membership degree update process is proportional to the number of data N, the number of clusters C, and the number of data dimensions D.

  Therefore, there is a problem that the larger the number of data, the number of clusters, and the number of data dimensions, the greater the amount of calculation, that is, the calculation time, is required until the result is output.

  The present invention has been made to solve the above problems, and a clustering device capable of clustering a plurality of data points at high speed even if the number of data points and the number of clusters are large values, It is an object to provide a method and a program.

  To achieve the above object, a clustering device of a first invention is a clustering device for clustering a plurality of data points into a plurality of clusters, and for each of the plurality of data points, the position of the data point and the data point A cluster that calculates a distance from the center position of each of a plurality of clusters, and determines the degree of belonging to each cluster of the data points based on each of the calculated distances and a predetermined softening parameter For each of the plurality of clusters, all positions of the plurality of data points, and attribution of each of the plurality of data points calculated by the cluster membership degree updating unit to each of the clusters And the center position of the cluster is updated based on the softening parameter and the distance of movement of the center position of the cluster before and after the update. For each of the plurality of data points, using the movement distance of all the central positions of the plurality of clusters, the degree of attribution of the data points to each cluster, and the softening parameter. Based on the function value, the cluster center update unit for determining the frequency of performing the process of determining the degree of membership to each cluster by the cluster membership level update unit for the data point, until a predetermined convergence condition is satisfied, A convergence determination unit that repeats the determination by the cluster membership degree updating unit and the determination by the cluster center updating unit, wherein the cluster membership level updating unit includes the cluster center updating unit for each of the plurality of data points. Whether to update the degree of belonging to each of the plurality of clusters based on the frequency determined for the data point by For each of the data points determined to update the degree of belonging to each of a plurality of clusters, calculate the distance between the position of the data point and the center position of each of the plurality of clusters, The degree of belonging to each cluster of the data points is determined based on each and the softening parameter.

  A clustering method according to a second invention is a clustering method in a clustering apparatus for clustering a plurality of data points into a plurality of clusters, including a cluster membership degree updating unit, a cluster center updating unit, and a convergence determining unit. The cluster membership degree updating unit calculates, for each of the plurality of data points, a distance between the position of the data point and the center position of each of the plurality of clusters, and each of the calculated distances, And determining a degree of belonging to each cluster of the data points based on the determined softening parameters, the cluster center update unit, for each of the plurality of clusters, all the positions of the plurality of data points and The degree of attribution of each of the plurality of data points calculated by the cluster membership degree updating unit to each of the clusters, and the softwareization Based on the parameters, the center position of the cluster is updated, the movement distance of the center position of the cluster before and after the update is calculated, and for each of the plurality of data points, all the center positions of the plurality of clusters are calculated. Based on a function value calculated using the moving distance of the data point, the degree of attribution of the data point to each cluster, and the softening parameter, the cluster membership degree update unit for the data point assigns each cluster to the cluster. Determining the frequency of performing the process of determining the degree of attribution, the convergence determination unit repeats the determination by the cluster membership degree update unit and the determination by the cluster center update unit until a predetermined convergence condition is satisfied, The cluster membership degree updating unit determines the degree of membership of each of the data points with respect to each of the plurality of data points. Based on the frequency determined for the data point by the cluster center updating unit, it is determined whether to update the degree of belonging to each of the plurality of clusters, and update the degree of belonging to each of the plurality of clusters. Then, for each of the determined data points, a distance between the position of the data point and the center position of each of the plurality of clusters is calculated, and based on each of the calculated distances and the softening parameter The degree of attribution of each data point to each cluster is determined.

  According to the first and second inventions, for each of the plurality of data points, the plurality of clusters based on the frequency determined for the data point by the cluster center updating unit by the cluster membership degree updating unit. Whether to update the degree of belonging to each of the plurality of clusters, and for each of the data points determined to update the degree of belonging to each of the plurality of clusters, the position of the data points and the plurality of clusters A distance to each center position is calculated, and based on each of the calculated distances and the softening parameter, a degree of belonging to each cluster of the data points is determined, and a cluster center update unit includes For each of the plurality of clusters, all the positions of the plurality of data points and the cluster of each of the plurality of data points calculated by the cluster membership degree update unit. Update the center position of the cluster based on the degree of membership and the softening parameter, calculate the movement distance of the center position of the cluster before and after the update, and for each of the plurality of data points , Based on a function value calculated using the movement distance of all the center positions of the plurality of clusters, the degree of belonging to each cluster of the data point, and the softening parameter, the data point for the data point The frequency of performing the process of determining the degree of belonging to each cluster is determined by the cluster membership degree updating unit, and the convergence determination unit determines the cluster membership degree updating unit until the convergence condition is satisfied, and the cluster The determination by the center update unit is repeated.

  In this way, for each of the plurality of data points, the degree of belonging to each cluster of the data points is determined, and for each of the plurality of clusters, the position of each data point and each calculated by the cluster membership degree updating unit Based on the degree of attribution of each data point to each cluster, the center position of the cluster is updated, and the movement distances of the center positions of the plurality of clusters before and after the update are calculated. Each cluster by the cluster membership level updating unit for the plurality of data points based on a function value calculated using the calculated degrees of membership to the plurality of clusters and the calculated movement distances of the plurality of cluster centers. The frequency of performing the process of updating the degree of membership in the cluster is determined, and the determination by the cluster membership degree updating unit and the determination by the cluster center updating unit are performed until a predetermined convergence condition is satisfied. Be returned by Ri, the number of the number and cluster of data points is a large value, it is possible to cluster multiple data points at high speed.

Further, in the first invention, the cluster membership degree updating unit sets the coefficient of the data point x _i as k _i, and sets the frequency of performing the determination processing of the data point x _i.

And, to a moving distance of all of the center position of the plurality of clusters, and degree of belonging to each cluster of the data points x _i, the denominator of the calculated function values using said softening parameter, predefined The ratio of the calculated value as the numerator

As described above, the value of the processing count t of the cluster membership degree update unit is

If you do not have a surplus with respect to the said k _i is updated as k _i +1, the ratio

That's it, and

If less than, update k _i to k _i −γ and the ratio is

That's it, and

If not, the frequency for the data point x _i may be determined by not updating the k _i .

  Moreover, the program of this invention is a program for functioning a computer as each part which comprises said clustering apparatus.

  As described above, according to the clustering apparatus, method, and program of the present invention, the degree of belonging to each cluster of data points is determined for each of a plurality of data points, and each data for each of the plurality of clusters is determined. Based on the position of the point and the degree of membership of each data point calculated by the cluster membership degree updating unit, the center position of the cluster is updated, and the center positions of the plurality of clusters before and after the update are updated. Based on the function value calculated using the calculated degree of belonging to the plurality of clusters and the calculated movement distance of the plurality of cluster centers for each of the plurality of data points. Determine the frequency of performing the process of updating the degree of belonging to each cluster by the cluster degree of update for the plurality of data points, until a predetermined convergence condition is satisfied, A decision by the raster membership updating unit, by repeating the determination by cluster center updating unit, the number of the number and cluster of data points is a large value, it is possible to cluster multiple data points at high speed.

It is a figure explaining the difference between the existing technique (Lloyd method, FCM method) and the technique of this Embodiment. It is a figure explaining reduction of the number of times of distance calculation which is one of subjects. It is a figure explaining attribution to a plurality of clusters which is one of problems. It is a figure which shows an example of the relationship between the update process of the attribution degree in update frequency, and a period. It is a figure which shows the functional structure of a clustering apparatus. It is a flowchart figure of the clustering process in a clustering apparatus. It is a flowchart figure of the initialization process in a clustering apparatus. It is a flowchart figure of the cluster membership degree update process in a clustering apparatus. It is a flowchart figure of the cluster center update process in a clustering apparatus. It is a flowchart figure of the cluster center update process in a clustering apparatus. It is a figure which shows an example of the frequency | count of omission. It is a figure which shows an example of clustering. It is an example of alternate optimization of cluster membership degree update processing and cluster center update processing.

  Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings.

<Principle of this embodiment>
In the process of updating the degree of belonging to each cluster of data points, the method for reducing the cost of distance calculation is as follows: (1) a method for reducing the number of periods until the algorithm converges, and (2) a distance calculation per time. There are a method for reducing the calculation cost and (3) a method for reducing the number of distance calculations per cycle. In the present embodiment, the method (3) is used.

  In the present embodiment, as shown in FIGS. 1 to 3, the goal is to simultaneously reduce the number of distance calculations between each data and the center of each cluster and allow the attribution to multiple clusters. Therefore, in the present embodiment, the efficiency of the algorithm is improved by adjusting the determination frequency of whether or not the cluster membership degree changes according to the movement distance of each cluster center and the attribution degree of each data to the corresponding cluster. Yes.

Specifically, based on the update frequency (hierarchical time step) Delta] t _i which is set for each data point x _i, performs assignment determination for each cluster for each data point x _i. The update frequency Δt _i is a function value f _i calculated from the degree of attribution of the data point x _i to each cluster and the moving distance from the previous cycle of each cluster center, as shown in the following equation (1). _{, t} (p, u) is the update frequency. Assume that the number of clusters is C.

  Here, the movement distance of cluster j is

Represented by The degree of attribution of the data point x _{i to} the cluster j is represented by u _{i, j} . Also, f _{i, t} (p, u) is set as follows, for example.

The coefficient k _i (= 0, 1,..., K _max ) is updated by the following equations (2), (3), and (4). C is the number of clusters, m is a softening parameter (m> 1 real number), γ is an integer, η is a constant, and t is a period. D (e, f) represents the distance between two points e and f in the Euclidean space.

The above equation (2) expresses the variable η / f _{i, t} (p with the function value f _{i, t} (p, u) as the denominator for the frequency of the membership update processing for the current data point x _i to each cluster. , u) satisfies the relationship included in the range of the constant threshold 2 ^ki-γ or more and less than 2 ^{ki-γ + 1} (γ = 1, 2, 3,...), the attribution of the data point x _i to each cluster This indicates that the process of increasing the frequency of the update process is performed. The above equation (3) is such that the variable η / f _{i, t} (p, u) is included in the range of the constant threshold 2 ^{ki + 1} or more and the remainder of 2 ^{ki + 1} with respect to the period t is 0. If satisfying, indicating that performing the process for lowering the frequency of membership updating process for each cluster of data points x _i. The above expression (3) represents that the process of maintaining the current frequency of the attribution update process is performed when neither the condition of the expression (1) nor the condition of the expression (2) is satisfied.

FIG. 4 shows the relationship between the frequency of performing cluster update processing and the cycle when Δt _i is 1, 2, and 4.

  Hereinafter, the clustering apparatus will be described in detail. In the clustering device, additional processing is added to the FCM method. In addition, the number of calculations per cycle in the FCM method is NC times when the number of data is N and the number of clusters is C when no additional processing is added (Non-Patent Document 2: JCBezdek. FCM). -The Fuzzy c-Means Clustering Algorithm, Computers & Geosciences, 1984.). The FCM method is a method for calculating the distance between all data and all cluster centers for each period.

<Configuration of clustering device>
Next, the configuration of the clustering apparatus will be described. As shown in FIG. 5, the clustering apparatus 100 can be configured by a computer including a CPU, a RAM, and a ROM that stores a program for executing a cluster processing routine described later and various data. Functionally, the clustering apparatus includes an input unit 10, a calculation unit 20, and an output unit 90 as shown in FIG.

The clustering apparatus 100 is supplied with a set X of data points of N data dimensions D in the Euclidean space and a number C (C <N) of clusters that divide the set X. Clustering apparatus 100, each data point x _i included in the input set X, divided by the form of the degree of membership to the C clusters, and outputs the calculation result of the degree of membership. Each data point is represented by a data point x _i (i = 1 to N), each cluster is represented by a cluster j (j = 1 to C), and the center position of the cluster j is defined as a cluster center c _j. And the degree of attribution of data point x _i to cluster _j is represented as u _{i, j} .

The input unit 10 receives a set X of data points, the number C of clusters, a softening parameter m, and an upper limit value k _max of the update frequency coefficient. The input unit 10 includes a D-dimensional coordinates of each data point x _i in the set X of the received data points, and the upper limit value k _max update frequency coefficients, the parameter storage unit 22 and a softening parameter m To remember.

  The calculation unit 20 includes a parameter storage unit 22, an initialization unit 24, a cluster membership degree update unit 26, a cluster center update unit 28, and a convergence determination unit 30.

The parameter storage unit 22, each of the D-dimensional coordinate position of the data point x _i accepted in the input unit 10, the soft parameter m, and the upper limit value k _max update frequency coefficients, the initialization unit 24 or the cluster center will be described later The D-dimensional coordinate position of each position of the cluster center c _j calculated by the update unit 28 and the update frequency Δt _i of each data point x _i calculated by the initialization unit 24 or the cluster center update unit 28 described later, And the update frequency coefficient k _i , the movement distance p _{j, t} of each cluster center c _j calculated by the cluster center update unit 28 described later _, and the data in the period t calculated by the cluster membership update unit 26 described later and each point x _i, and the distance between each of the cluster center c _j, data in the calculated period t in clusters membership update unit 26 described below membership u _i to cluster j of x _i, and a _j are stored. The period t represents the number of repetitions of the process by the cluster membership degree update unit 26, the process of the cluster center update unit 28, and the process of the convergence determination unit 30. The initial value of the period t is 1, and the process is repeated. Assume that 1 is added to the value of the period t every time.

The initialization unit 24 randomly selects C data points from each of the data points x _i received by the input unit 10, and sets the D-dimensional coordinate position of the selected data points x _i to D of the cluster center c _j of the cluster _j . The dimension coordinate position is set and stored in the parameter storage unit 22. In addition, the initialization unit 24 stores the value of the update frequency Δt _i for each data point x _i as 1 in the parameter storage unit 22. The initialization unit 24 stores the value of the update frequency coefficient k _i for each data point x _i as 0 in the parameter storage unit 22. The initialization unit 24 stores the softening parameter m received by the input unit 10.

Cluster membership update unit 26, for each of a plurality of data points x _i in the set X of the received data points in the input unit 10, for the data points x _i, the data stored in the parameter storage section 22 based on the update frequency Delta] t _i and the current period t at the point x _i, in order to update the degree of belonging to each cluster of the data points x _i, and each of the data points x _i and the cluster center c _j It is determined whether or not the process for calculating the distance can be omitted.

Also, the cluster membership update unit 26, for each of the determined can not skip the process of calculating data points x _i, D dimension coordinates of the data points x _i stored in the parameter storage unit 22, and the cluster based on the distance between each of the D-dimensional coordinate position of the center c _j, calculating the corresponding data points x _i, the distance between the cluster center c _j. Then, the degree of membership u _{i, j} to each cluster is determined for each data point x _i determined that the calculation process cannot be omitted.

Specifically, first, based on the update frequency Δt _i of the data point x _i stored in the parameter storage unit 22 and the period t, it is determined whether or not the following equation (5) is satisfied.

Update frequency Delta] t _i of the data points x _i is if it satisfies the above equation (5), for the data points x _i, can not skip the process of calculating the distance between each of the data points x _i and the cluster center c _j Is determined. On the other hand, the update frequency Delta] t _i of the data points x _i If the does not satisfy the equation (5), when it is possible to omit the process of calculating the distance between each of the data points x _i and the cluster center c _j Determination is made, and the degree of belonging to each cluster of the data point x _i is left as it is.

Next, for each data point x _i determined that the process of calculating the distance between the data point x _i and each of the cluster centers c _j cannot be omitted, the data point x stored in the parameter storage unit 22 _i D-dimensional coordinates, and based on each of D-dimensional coordinate position of the cluster centers c _j, calculating the respective distances between the data points x _i, with each of the cluster center c _j. Here, the distance between the data point x _i and the cluster center c _j in the period t is expressed as d (x _i , c _{j, t} ).

Then, the calculated distance d (x _i , c _{j, t} ) is calculated for each data point x _i determined that the process of calculating the distance between the data point x _i and each of the cluster centers c _j cannot be omitted. And the degree of attribution u _{i, j} of the data point x _{i to} the cluster _j is updated for each cluster j according to the following equation (6).

The cluster center updating unit 28 determines the degree of attribution u _{i, j of} the data point x _i acquired in the cluster membership degree updating unit 26 to the cluster j and each of the data points x _i stored in the parameter storage unit 22. Based on the dimensional coordinate position, the D dimensional coordinate position of each cluster center c _j of the cluster _j is updated. In addition, the cluster center updating unit 28 calculates the movement distance p _{j, t} of the D-dimensional coordinate position of the cluster center c _j from the period t−1 to the period t for each cluster j. In addition, the cluster center updating unit 28 _assigns , for each data point x _i , the degree of membership u _{i, j of} the data point x _i acquired by the cluster membership degree updating unit 26 to the cluster j and each calculated cluster j. The update frequency coefficient k _i is updated on the basis of the movement distance p _{j, t} and the update frequency Δt _i is updated on the basis of the updated update frequency coefficient k _i .

Specifically, first, for each cluster j, the degree of membership u _{i, j} of the data point x _i acquired in the cluster membership degree update unit 26 to the cluster j is acquired for all data points. Next, for each cluster j, the degree of membership u _{i, j of} all the acquired data points x _i stored in the parameter storage unit 22 to the cluster j and the D-dimensional coordinates of all the data points x _i are stored. Based on the position, the D-dimensional coordinate position of the cluster center c _{j, t} in the period t of the cluster _j is updated according to the following equation (7) and stored in the parameter storage unit 22.

Next, for each cluster j, the D-dimensional coordinate position of the cluster center c _{j, t−1} of the period t−1 stored in the parameter storage unit 22 and the calculated cluster center c _{j, t} of the period t Based on the D-dimensional coordinate position, the movement distance p _{j, t} of the cluster center before and after the update is calculated and stored in the parameter storage unit 22.

Then, for each data point x _i, the moving distance p _j of cluster _centers, and _t, membership u _i to cluster j data point x _i, and _j, the function value determined by using the software parameter m Using f _{i, t} (p, u), the update frequency coefficient k _i is updated based on the equations (2) to (4) and stored in the parameter storage unit 22. Here, when the value of the calculated update frequency coefficient k _i is larger than k _max stored in the parameter storage unit 22, the update frequency coefficient k _i = k _max is set and the calculated update is performed. When the value of the frequency coefficient k _i is smaller than 0, the update frequency coefficient k _i = 0 is set. Then, for each data point x _i, based on the update frequency coefficients k _i of the calculated the data points x _i, according to the above (1), and updates the update frequency Delta] t _i of the data points x _i, the parameter Store in the storage unit 22.

The convergence determination unit 30 determines whether or not a predetermined convergence condition is satisfied. An evaluation function _{F t-1} of period t-1, the absolute value of the difference between the evaluation function _{F t} of period t _| a converging condition is satisfied if the below a predetermined threshold of | F t _{-F t-1} judge.

In addition, when the convergence determination unit 30 determines that the convergence condition is satisfied, the calculation result of the belonging degree to each cluster of the data point x _i obtained by the cluster belonging degree update unit 26 and the cluster center in the period t. The D-dimensional coordinate position of each cluster center c _j of the cluster j calculated by the updating unit 28 is output to the output unit 90. On the other hand, when it is determined that the convergence condition is not satisfied, the convergence determination unit 30 repeats the process of the cluster membership degree update unit 26, the process of the cluster center update unit 28, and the process of the convergence determination unit 30.

The evaluation function F _t is calculated according to the following equation (8) and stored in the parameter storage unit 22.

Here, for data point x _i in period t

Is not present in the parameter storage unit 22, the value of t stored in the parameter storage unit 22 for the data point x _i is the largest.

Will be used.

<Operation of clustering device>
Next, the operation of the clustering apparatus 100 will be described. First, the input unit 10, a set X of data points, and the upper limit value k _max update frequency coefficient, D dimension coordinates of each data point x _i in the set X of the data points accepts soft parameter m Then, the upper limit value k _max of the update frequency coefficient and the softening parameter m are stored in the parameter storage unit 22. When the cluster number C is received by the input unit 10, the clustering apparatus 100 executes the clustering processing routine shown in FIGS.

  First, in step S100 of FIG. 6, the initialization unit 24 sets initial values of various parameters.

Next, in step S102, the cluster membership degree update unit 26 updates the membership degree u _{i, j} to the cluster j to which the data point x _i belongs for each data point x _i received by the input unit 10. .

Next, in step S104, the cluster center updating unit 28 updates the cluster center c _{j, t} of the cluster j for each cluster j. Further, in step S104, the cluster centers update unit 28, for each data point x _i, and updates the update frequency coefficients k _i of the data points x _i, based on the updated update frequency coefficients k _i, the data to update the update frequency Δt _i of a point _{x i.}

Next, in step S106, the convergence determining unit 30 for each data point x _i stored in the parameter storage section 22

And for each data point x _i and for cluster j

And whether or not the convergence condition is satisfied is determined based on the softening parameter m. When the convergence determination unit 30 determines that the convergence condition is satisfied, the clustering process proceeds to step S108. On the other hand, when the convergence determination unit 30 determines that the convergence condition is not satisfied, the clustering process proceeds to step S102 and repeats the processes from step S102 to step S106.

Next, in step S108, the convergence determining unit 30, a degree of membership calculation results to the clusters of the acquired data points _{x i} in step S102, D dimension of each cluster center _{c j} of the cluster j obtained in step S104 The coordinate position is output to the output unit 90, and the clustering process is terminated.

  The initialization process in step S100 will be described in detail with reference to FIG.

In step S200 of FIG. 7, the initialization unit 24, each of the D-dimensional coordinate position of the data point x _i stored in the parameter storage unit 22, and the upper limit value k _max update frequency coefficients _and soft parameter m Read.

  Next, in step S202, the initialization unit 24 sets the value of the period t to 0.

Next, in step S204, the initialization unit 24, the N data points _{x i} accepted in the input unit 10, select the C-number of data points _{x i,} obtained in step S200, the selected data points Are determined as the D-dimensional coordinate positions of the cluster centers c _{j, t} of the cluster _{j, and} stored in the parameter storage unit 22.

  Next, in step S206, the initialization unit 24 sets the value of i to 1.

Next, in step S208, the initialization unit 24 sets the update frequency Delta] t _i data points _{x i} 1 and is stored in the parameter storage unit 22.

Next, in step S210, the initialization unit 24, the update frequency coefficients _{k i} of the data points _{x i} is set to 0, is stored in the parameter storage unit 22.

  Next, in step S212, the initialization unit 24 determines whether or not the value of i is N. If the initialization unit 24 determines that the value of i is less than N, the initialization process proceeds to step S214. On the other hand, when the initialization unit 24 determines that the value of i is N, the initialization process ends.

  Next, in step S214, the initialization unit 24 sets the value of i to i + 1, and proceeds to step S208.

  The cluster membership degree update process in step S102 will be described in detail with reference to FIG.

  In step S300 of FIG. 8, the cluster membership degree update unit 26 sets the value of i to 1.

  Next, in step S302, the cluster membership degree update unit 26 sets the value of t to t + 1.

  Next, in step S304, the cluster membership degree update unit 26 sets the value of j to 1.

  Next, in step S306, the cluster membership degree update unit 26 determines whether the value of i is greater than N. When the cluster membership level update unit 26 determines that the value of i is N or less, the cluster membership level update process proceeds to step S308. On the other hand, if the cluster membership degree update unit 26 determines that the value of i is greater than N, the cluster membership degree update process ends.

Next, in step S308, the cluster membership degree update unit 26 sets the value of t acquired in step S302 and the update frequency Δt _i of the data point x _i acquired in step S208 or step S509 in the previous clustering process. Based on this, it is determined whether or not the above equation (5) is satisfied. When the cluster membership level update unit 26 determines that the above expression (5) is satisfied, the cluster membership level update process proceeds to step S310. On the other hand, if the cluster membership level update unit 26 determines that the above equation (5) is not satisfied, the cluster membership level regarding the data point x _i is left as it is, and the process proceeds to step S318.

  Next, in step S310, the cluster membership degree update unit 26 determines whether the value of j is C or less. When the cluster membership degree update unit 26 determines that the value of j is C or less, the cluster membership degree update process proceeds to step S312. On the other hand, when the cluster membership degree update unit 26 determines that the value of j is greater than C, the cluster membership degree update process proceeds to step S316.

Next, in step S312, the cluster membership updating unit 26, a D-dimensional coordinates of the acquired data points _{x i} in step S200, step S202, or cluster centers of the acquired cluster j at step S404 of the previous clustering process based on the D-dimensional coordinate position of c _j, the distance _{d (x i, c j,} t) is calculated.

  Next, in step S314, the cluster membership degree update unit 26 sets the value of j to j + 1, and the cluster membership degree update process proceeds to step S310.

In step S316, the cluster membership degree updating unit 26 acquires the distance d (x _i , c _{j, t} ) between the data point x _i and each of the cluster centers c _{j, t} acquired in step S312, and the softening parameter m. Based on the above, the degree of membership u _{i, j} of the data point x _{i to} the cluster j is updated for each cluster j according to the above equation (6).

  Next, in step S318, the cluster membership degree updating unit 26 sets the value of i to i + 1, and proceeds to step S304.

  The cluster center update process in step S104 will be described in detail with reference to FIGS.

  In step S400 of FIG. 9, the cluster center update unit 28 sets the value of j to 1.

Next, in step S _< b> 402, the cluster center update unit 28 reads the D-dimensional coordinate position of the cluster center c _{j, t−1} in the period t−1 stored in the parameter storage unit 22.

Next, in step S404, the cluster center updating unit 28 converts each D-dimensional coordinate position of the data point x _i acquired in step S200, the softening parameter m, and the cluster j of the data point x _i acquired in step S316. The D-dimensional coordinate position of the cluster center c _{j, t} is calculated according to the above equation (7) based on the degree of membership u _{i, j} and stored in the parameter storage unit 22.

Next, in step S406, the cluster center updating unit 28 determines the D-dimensional coordinate position of the cluster center c _{j, t−1} acquired in step S402 and the D-dimensional coordinate position of the cluster center c _{j, t} acquired in step S404. Based on the above, the movement distance p _{j, t} of the cluster center c _j from the period t−1 to the period _t is calculated.

  Next, in step S408, the cluster center update unit 28 determines whether the value of j is smaller than the value of C. When the cluster center updating unit 28 determines that the value of j is smaller than the value of C, the process proceeds to step S410. On the other hand, when the cluster center updating unit 28 determines that the value of j is greater than or equal to the value of C, the process proceeds to step S411.

  In step S410, the cluster center update unit 28 sets j to j + 1, and proceeds to step S402.

  In step S411, the cluster center updating unit 28 sets the value of i to 1.

Next, in step S412, for the data point x _i , the degree of membership u _{i, j of the} data point x _i acquired in step S316 to each cluster j and the cluster center c _j acquired in step S406 are determined. A function value f _{i, t} (p, u) is calculated based on the movement distance p _{j, t} from one cycle before and stored in the parameter storage unit 22.

Next, in step S414, the cluster center updating unit 28 determines whether or not the function value f _{i, t} (p, u) acquired in step S412 satisfies the condition (3). When the cluster center updating unit 28 determines that the condition (3) is satisfied, the cluster center updating process proceeds to step S416. On the other hand, when the cluster center updating unit 28 determines that the condition (3) is not satisfied, the cluster center updating process proceeds to step S419.

Next, in step S416, the cluster centers updating unit 28 updates the update frequency coefficients _{k i} of the data points _{x i} to _k i +1.

Next, in step S417, the cluster center updating unit 28 determines whether or not the update frequency coefficient k _i of the data point x _i acquired in step S416 is larger than the value of k _max acquired in step S200. Cluster center updating unit 28, when the update frequency coefficients k _i of the data points x _i is determined to less than the value of the acquired k _max in step S200, the cluster centers update processing, stores k _i in the parameter storage section 22 Then, the process proceeds to step S509 in FIG. On the other hand, the cluster center updating unit 28, when the update frequency coefficients _{k i} of the data points _{x i} is greater than the value of _{k max} obtained in step S200, the cluster centers updating process proceeds to step S418.

Next, in step S418, the cluster center updating unit 28 sets the value of the update frequency coefficient k _i of the data point x _i acquired in step S416 as the value of k _max acquired in step S200, and stores it in the parameter storage unit 22. .

In step S419, the cluster center updating unit 28 determines whether or not the function value f _{i, t} (p, u) acquired in step S412 satisfies the condition (4). If the cluster center update unit 28 determines that the condition (4) is satisfied, the cluster center update process proceeds to step S420. On the other hand, when the cluster center updating unit 28 determines that the condition (4) is not satisfied, the cluster center updating process proceeds to step S500 in FIG.

Next, in step S420, the cluster centers updating unit 28, the update frequency coefficients _{k i} of the data points _{x i} and _{k i,} stored in the parameter storage unit 22, the cluster center updating process proceeds to step S509 in FIG. 10 To do.

  In step S500 of FIG. 10, the cluster center updating unit 28 sets the value of γ to 1.

Next, in step S502, the cluster center updating unit 28 determines whether or not the function value f _{i, t} (p, u) acquired in step S412 satisfies the condition (2). When the cluster center update unit 28 determines that the condition (2) is satisfied, the cluster center update process proceeds to step S506. On the other hand, when the cluster center updating unit 28 determines that the condition (2) is not satisfied, the cluster center updating process proceeds to step S504.

  Next, in step S504, the cluster center updating unit 28 sets the value of γ to γ + 1.

Next, in step S506, the cluster centers updating unit 28, the update frequency coefficients _{k i} of the data points _{x i} and _k i-gamma.

Next, in step S507, the cluster center updating unit 28 determines whether or not the update frequency coefficient k _i of the data point x _i acquired in step S506 is smaller than a value of 0. Cluster center updating unit 28, when it is determined that the update frequency coefficients k _i of the data points x _i is less than the value of zero, cluster centers updating process proceeds to step S508. On the other hand, the cluster center updating unit 28, when the update frequency coefficients k _i of the data points x _i is a value of 0 or greater, the cluster centers updating process stores the k _i in the parameter storage unit 22, to step S509 Transition.

In step S508, the cluster center update unit 28 sets the update frequency coefficient k _i of the data point x _i acquired in step S506 to 0 and stores it in the parameter storage unit 22.

Next, in step S509, the cluster center updating unit 28, based on the update frequency coefficient k _i of the data point x _i acquired in step S416, step S418, step S420, step S506, or step S508, the above (1). The update frequency Δt _i of the data point xi is updated according to the equation and stored in the parameter storage unit 22.

  Next, in step S510, the cluster center update unit 28 determines whether or not the value of i is smaller than N. When the cluster center update unit 28 determines that the value of i is smaller than N, the cluster center update process proceeds to step S512. On the other hand, when the cluster center updating unit 28 determines that the value of i is smaller than N, the cluster center updating process ends.

  In step S512, the cluster center update unit 28 sets the value of i to i + 1, and proceeds to step S412 in FIG.

  As described above, according to the clustering device according to the first embodiment, the degree of belonging to each cluster of data points is determined for each of a plurality of data points, and all data for each of the plurality of clusters is determined. Update the center position of the cluster based on the position of the point, the degree of attribution of all data points to the corresponding cluster, and the softwareization parameters, and calculate the movement distance of the center position of the cluster before and after the update. For each of the data points, the degree of attribution of each data point to each cluster is calculated based on the movement distance of each cluster center, the degree of attribution of each data point to each cluster, and the function value calculated by the softening parameter. Determines the frequency of the process to be determined, and performs the process of determining the degree of belonging to each cluster and the degree of belonging to the data points until a predetermined convergence condition is satisfied. By repeating the determination of the frequency, the number of the number and cluster of data points is a large value, it is possible to cluster multiple data points at high speed.

In addition, while the number of calculations per cycle in the conventional FCM method is NC, the number of calculations per cycle is set to N _IF C by using the clustering apparatus 100 according to the first embodiment. Can do. However, N _IF <N. FIG. 11 shows an example of the number of times omitted from the conventional method.

  In addition, the algorithm execution time can be shortened and the calculation speeded up.

  In addition, by adding restrictions on whether or not to calculate the distance based on the distance traveled by each cluster, the degree of attribution of the corresponding data point to each cluster, and the function value calculated by the softwareization parameter, The number of data points to be calculated is reduced, and the total number of distance calculations is reduced.

  Note that the present invention is not limited to the above-described embodiment, and various modifications and applications are possible without departing from the gist of the present invention.

  For example, although the case where it is determined whether or not the convergence condition is satisfied based on the evaluation function has been described, the present invention is not limited to this, and other convergence conditions such as the number of periods may be used.

  Further, in the present specification, the embodiment has been described in which the program is installed in advance. However, the program can be provided by being stored in a computer-readable recording medium or provided via a network. It is also possible to do.

DESCRIPTION OF SYMBOLS 10 Input part 20 Calculation part 22 Parameter memory | storage part 24 Initialization part 26 Cluster membership degree update part 28 Cluster center update part 30 Convergence determination part 90 Output part 100 Clustering apparatus

Claims (4)

A clustering device for clustering a plurality of data points into a plurality of clusters,
For each of the plurality of data points, calculate a distance between the position of the data point and the center position of each of the plurality of clusters, and based on each of the calculated distances and a predetermined softening parameter A cluster membership degree update unit for determining the degree of membership of each data point to each cluster,
For each of the plurality of clusters, all positions of the plurality of data points, the degree of membership of each of the plurality of data points calculated by the cluster membership degree updating unit, and the softwareization Based on the parameters, update the center position of the cluster, calculate the movement distance of the center position of the cluster before and after the update,
For each of the plurality of data points, based on a function value calculated using the movement distance of all the central positions of the plurality of clusters, the degree of belonging to each cluster of the data points, and the softening parameter A cluster center updating unit that determines the frequency of performing the process of determining the degree of belonging to each cluster by the cluster membership degree updating unit for the data point;
A convergence determination unit that repeats the determination by the cluster membership update unit and the determination by the cluster center update unit until a predetermined convergence condition is satisfied,
Including
Whether the cluster membership degree updating unit updates the membership degree to each of the plurality of clusters based on the frequency determined for the data point by the cluster center updating unit for each of the plurality of data points. And for each of the data points determined to update the degree of belonging to each of the plurality of clusters, the distance between the position of the data point and the center position of each of the plurality of clusters is calculated. A clustering device that determines the degree of attribution of each data point to each cluster based on each of the calculated distances and the softening parameter. The cluster center updating unit sets the coefficient of the data point x _i to k _i, and sets the frequency of performing the determination process on the data point x _i.
And, to a moving distance of all of the center position of the plurality of clusters, and degree of belonging to each cluster of the data points x _i, the denominator of the calculated function values using said softening parameter, predefined The ratio of the calculated value as the numerator
As described above, the value of the processing count t of the cluster membership degree update unit is
If you do not have a surplus with respect to the said k _i is updated as k _i +1, the ratio
That's it, and
If less than, update k _i to k _i −γ and the ratio is
That's it, and
The clustering device according to claim 1, wherein the frequency for the data point x _i is determined by not updating the k _i if it is less than the value. A clustering method in a clustering apparatus for clustering a plurality of data points into a plurality of clusters, including a cluster membership degree update unit, a cluster center update unit, and a convergence determination unit,
The cluster membership degree update unit calculates a distance between a position of the data point and a center position of each of the plurality of clusters for each of the plurality of data points, and determines each of the calculated distances in advance. And the degree of attribution of the data points to each cluster based on the softening parameters determined,
The cluster center updating unit includes, for each of the plurality of clusters, all positions of the plurality of data points, and each of the plurality of data points calculated by the cluster membership degree updating unit to each of the clusters. Based on the degree of attribution and the softening parameter, update the center position of the cluster, calculate the movement distance of the center position of the cluster before and after the update,
For each of the plurality of data points, based on a function value calculated using the movement distance of all the central positions of the plurality of clusters, the degree of belonging to each cluster of the data points, and the softening parameter Determining the frequency of performing the process of determining the degree of belonging to each cluster by the cluster degree of update for the data point,
The convergence determination unit repeats the determination by the cluster membership degree update unit and the determination by the cluster center update unit until a predetermined convergence condition is satisfied,
Including
The cluster membership degree updating unit determines the degree of membership of each of the data points to each cluster based on the frequency determined for the data point by the cluster center updating unit for each of the plurality of data points. Determining whether to update the degree of belonging to each of the plurality of clusters, and for each of the data points determined to update the degree of belonging to each of the plurality of clusters, A clustering method that calculates a distance from a center position of each of the plurality of clusters, and determines the degree of belonging to each cluster of the data points based on each of the calculated distances and the softening parameter.   The program for functioning a computer as each part of the clustering apparatus of Claim 1 or 2.