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

Description

  The present invention relates to a clustering device, method, and program, and more particularly, to a clustering device, method, and program for determining a cluster to which a data point belongs.

  As shown in FIG. 28, when classifying each of a plurality of data points to be classified into a plurality of clusters, optimization is performed by alternately searching for the cluster center and updating the cluster center. A plurality of data are classified for, and the cluster center is output.

  As shown in FIG. 29, the search for the cluster center searches the cluster center closest to the data point for each of a plurality of data points, and assigns the data point to the cluster. In the example of FIG. 29, since the cluster center of cluster (2) is closer to the data point to be processed, one data point belonging to cluster (1) moves to cluster (2). It becomes.

  In the cluster center update process, the center of gravity of the data points belonging to each cluster is reset as a new cluster center. The cluster center search process and the cluster center update process are alternately optimized until convergence.

  Conventionally, the Lloyd method (Non-patent document 1), the Elkan method (Non-patent document 2), the Hammerly method (Non-patent document 3), and the like are used.

Least squares quantization in PCM, IEEE Transaction on Information Theory, 1982 Using the Triangle Inequality to Accelerate k-Means, ICML 2003, 2003 Making k-means even faster, SDM 2010, 2010

  However, the cost of the distance calculation in the search process for the cluster center to which it belongs 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 Calculate a distance from the center position of each of a plurality of clusters, and determine a cluster to which the data point belongs based on each of the calculated distances, and each of the plurality of clusters , Updating the center position of the cluster based on the position of the data point determined to belong to the cluster by the cluster center search unit, and calculating the movement distance of the center position of the cluster before and after the update For each of the plurality of data points, the calculated movement distance of the center position of the cluster to which the data point belongs Therefore, a cluster center update unit that determines the frequency of performing the process of determining a cluster to which the data point belongs by the belonging cluster center search unit, and the belonging cluster center search unit until a predetermined convergence condition is satisfied And a convergence determination unit that repeats the determination by the cluster center update unit, and the cluster center search unit for each of the plurality of data points by the cluster center update unit Based on the frequency determined for the data point, it is determined whether to determine a cluster to which the data point belongs, and for each of the data points determined to determine the cluster to belong to, the center of each of the plurality of clusters A distance to the position is calculated, and based on each of the calculated distances, a cluster to which the data point belongs is determined. A constant.

  A clustering method according to a second aspect of the present invention is a clustering method in a clustering apparatus for clustering a plurality of data points into a plurality of clusters, including an affiliated cluster center search unit, a cluster center update unit, and a convergence determination unit. , The belonging cluster center search unit calculates a distance between the position of the data point and the center position of each of the plurality of clusters for each of the plurality of data points, and based on each of the calculated distances Determining a cluster to which the data point belongs, and the cluster center updating unit, for each of the plurality of clusters, based on the position of the data point determined to belong to the cluster by the belonging cluster center search unit, Update the center position of the cluster and 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 the calculated movement distance of the center position of the cluster to which the data point belongs, a process of determining the cluster to which the data point belongs by the belonging cluster center search unit. Determining the frequency to perform, wherein the convergence determination unit repeats the determination by the belonging cluster center searching unit and the determination by the cluster center updating unit until a predetermined convergence condition is satisfied, The center search unit determines, for each of the plurality of data points, whether to determine a cluster to which the cluster belongs, based on the frequency determined for the data point by the cluster center update unit, For each of the data points determined to be determined, the distance from the center position of each of the plurality of clusters is measured. And, based on each of the calculated distance to determine the cluster to which belongs the data points.

  According to the first and second inventions, the assigned cluster center search unit calculates the distance between the position of the data point and the center position of each of the plurality of clusters for each of the plurality of data points, and the calculated distance Based on each of the above, determine the cluster to which the data point belongs, the cluster center update unit, for each of a plurality of clusters, based on the position of the data point determined to belong to the cluster by the belonging cluster center search unit, Update the center position of the cluster, calculate the movement distance of the cluster center position before and after the update, and for each of multiple data points, based on the calculated movement distance of the cluster center position to which the data point belongs And determining the frequency of performing the process of determining the cluster to which the data point belongs by the cluster center search unit for the data point. To meet, repeat the determination by the cluster membership center search unit, and a decision by the cluster center updating unit.

  Thus, for each of a plurality of data points, the cluster to which the data point belongs is determined, and for each of the plurality of clusters, the center position of the cluster is updated based on the position of the data point determined to belong to the cluster. Calculating 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 the movement distance of the center position of the cluster to which the calculated data point belongs, Determines the frequency of performing the process of determining the cluster to which it belongs, and repeats the determination of the cluster to which it belongs and the determination of the frequency of determining the cluster to which the data point belongs until a predetermined convergence condition is satisfied Thus, even if the number of data points and the number of clusters are large values, a plurality of data points can be clustered at high speed.

In the first invention, the cluster center updating unit sets the coefficient of the data point x _i to k _i, and sets the frequency of performing the determining process on the data point x _i.

And the ratio of the movement distance of the center position of the cluster to which the data point x _i belongs is the denominator and the predetermined value is the numerator.

As described above, the value of the processing count t of the cluster center search 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−γ 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 .

Further, in the first invention, the belonging cluster center search unit, for each of the data points determined to determine the cluster to which the member belongs, the center position of the cluster to which the data point belongs and the center of the cluster to which the member belongs When the distance between the center position of the cluster having the closest center position to the position is at least twice the upper limit of the distance between the data point and the center position of the cluster to which the data point belongs, the data point and the plurality of clusters The cluster to which the data point belongs may be determined without calculating the distance from each center position.

Further, in the first invention, the belonging cluster center search unit, for each of the data points determined to determine the cluster to which it belongs, the center position of the cluster to which the data point belongs and the data point does not belong When the distance from the center position of the cluster is at least twice the upper limit value of the distance between the data point and the center position of the cluster to which the cluster belongs, or the upper limit value of the distance is the data point and the attribute If the distance is below the lower limit of the distance from the center position of the non-cluster, the distance between the data point and the center position of the non-belonging cluster and the distance between the data point and the center position of the cluster to which the data point belongs are calculated. The distance between the center position of the cluster to which the data point belongs and the center position of the cluster to which the data point does not belong is the distance between the data point and the cluster to which the data point belongs. If the distance between the data point and the center position of the cluster to which the data point belongs is less than or equal to the lower limit value of the distance, The cluster to which the data point belongs may be determined without calculating the distance from the center position.

Further, in the first invention, the belonging cluster center search unit, for each of the data points determined to determine the cluster to which it belongs, the data point and the center position of the cluster closest to the data point, Is lower than the upper limit value of the distance between the data point and the center position of the cluster to which the data point belongs, or the center position of the cluster to which the data point belongs and the center position of the cluster to which the data point belongs. And the distance between the center position of the cluster having the closest center position is more than twice the distance between the data point and the center position of the cluster to which the data point belongs, or the data point and the data When the distance from the center position of the cluster to which the point belongs is less than or equal to the lower limit of the distance, the distance between the data point and the center position of each of the plurality of clusters is calculated. Not to may be determined clusters belonging of the data points.

  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, a cluster to which a data point belongs is determined for each of a plurality of data points, and each cluster is determined to belong to a cluster. Update the center position of the cluster based on the position of the data point calculated, calculate the distance traveled by the center position of the cluster before and after the update, and assign the calculated data point to each of the multiple data points Based on the movement distance of the center position of the cluster to be determined, determine the frequency of performing the process of determining the cluster to which the data point belongs, and determine the cluster to which the data point belongs and the data point until a predetermined convergence condition is satisfied The number of data points and the number of clusters are large by repeating the process of determining the cluster to which the cluster belongs. Even, it is possible to cluster multiple data points at high speed.

It is a figure which shows an example in which dispersion | variation arises in the movement distance of each cluster center. It is a figure which shows an example of the relationship between the update process of a cluster in update frequency, and a period. It is a figure which shows the functional structure of the clustering apparatus which concerns on 1st Embodiment. It is a flowchart figure of the clustering process in the clustering apparatus which concerns on 1st Embodiment. It is a flowchart figure of the initialization process in the clustering apparatus which concerns on 1st Embodiment. It is a flowchart figure of the affiliation cluster center search process in the clustering apparatus which concerns on 1st Embodiment. It is a flowchart figure of the cluster center update process in the clustering apparatus which concerns on 1st Embodiment. It is a flowchart figure of the cluster center update process in the clustering apparatus which concerns on 1st Embodiment. It is a figure which shows an example of the frequency | count of omission. It is a figure which shows an example which abbreviate | omits calculation by Elkan method. It is a figure which shows an example which abbreviate | omits calculation by Elkan method. It is a figure which shows an example which abbreviate | omits calculation by Elkan method. It is a figure which shows an example which abbreviate | omits calculation by Elkan method. It is a figure which shows an example which abbreviate | omits calculation by Elkan method. It is a block diagram which shows the functional structure of the clustering apparatus which concerns on 2nd Embodiment. It is a flowchart figure of the clustering process in the clustering apparatus which concerns on 2nd Embodiment. It is a flowchart figure of the initialization process in the clustering apparatus which concerns on 2nd Embodiment. It is a flowchart figure of the affiliation cluster center search process in the clustering apparatus which concerns on 2nd Embodiment. It is a flowchart figure of the cluster center update process in the clustering apparatus which concerns on 2nd Embodiment. It is a flowchart figure of the cluster center update process in the clustering apparatus which concerns on 2nd Embodiment. It is a figure which shows an example which abbreviate | omits calculation by the Hammerly method. It is a figure which shows an example which abbreviate | omits calculation by the Hammerly method. It is a figure which shows an example which abbreviate | omits calculation by the Hammerly method. It is a figure which shows the functional structure of the clustering apparatus which concerns on 3rd Embodiment. It is a flowchart figure of the clustering process in the clustering apparatus which concerns on 3rd Embodiment. It is a flowchart figure of the initialization process in the clustering apparatus which concerns on 3rd Embodiment. It is a flowchart figure of the member cluster center search process in the clustering apparatus which concerns on 3rd Embodiment. It is a flowchart figure of the cluster center update process in the clustering apparatus which concerns on 3rd Embodiment. It is a figure which shows an example of clustering. It is a figure which shows an example which makes a data point belong to a cluster.

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

<Principle of this embodiment>
In the process of searching the cluster center to which the data point belongs, the method for reducing the distance calculation cost is as follows: (1) a method for reducing the number of periods until the algorithm converges, and (2) a calculation cost per one distance calculation. And (3) a method of reducing the number of distance calculations per cycle. In the present embodiment, the method (3) is used.

  In this embodiment, as shown in FIG. 1, the movement distance of each cluster center is likely to vary, and the data point belonging to the cluster center with the shortest movement distance is relatively likely to change the cluster center. Focus on the low. For this reason, in this embodiment, the determination frequency of whether the cluster center to which the data point belongs changes is adjusted according to the movement distance of the cluster center to which the data point belongs, thereby improving the efficiency of the algorithm.

Specifically, based on the update frequency (hierarchical time step) Delta] t _i which is set for each data point x _i, performs assignment determination cluster for each data point x _i. The update frequency Δt _i is an update frequency according to the moving distance from one cycle before the cluster center to which the data point x _i belongs, as shown in the following equation (1). Assume that the number of clusters is C.

  Here, the movement distance is

Represented by A _i is a variable representing the cluster to which the data point x _i belongs, and a _i is included in C. The coefficient k _i (= 0, 1,..., K _max ) is updated by the following equations (2), (3), and (4). Γ 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.

(2) - (4), the frequency of updating the clusters of the current data point x _i is the moving distance of the cluster a _i that in the previous process, the previous data point x _i was a member

The movement distance in the previous processing of cluster a _i

Compared to raise the frequency of updating the associated cluster of this data point x _i if the movement distance is increased in the process, if smaller data point x _i belongs to a cluster of update processing Represents a decrease in frequency. FIG. 2 shows the relationship between the frequency of performing cluster update processing and the period when Δt _i is 1, 2, and 4.

  Hereinafter, the clustering apparatus according to the first embodiment will be described in detail. In the first embodiment, additional processing is added to the Lloyd method. In addition, the number of calculations per cycle in the Lloyd 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 1: SP Lloyd. Least). squares quantization in PCM, IEEE Transaction on Information Theory, 1982). The Lloyd method is a method for calculating the distance between all data and all cluster centers for each period.

<Configuration of Clustering Device According to First Embodiment>
Next, the configuration of the clustering apparatus according to the first embodiment will be described. As shown in FIG. 3, the clustering apparatus 100 according to the first embodiment includes 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. can do. This clustering apparatus is functionally configured to include 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 into C clusters, and outputs the division result. 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. Represent.

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

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

The parameter storage unit 22, D-dimensional coordinates of each data point x _i accepted in the input unit 10, and calculates the upper limit value k _max update frequency coefficients, the initialization unit 24 or cluster centers updating unit 28 will be described later The D-dimensional coordinate position of each position of the cluster center c _j 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 of the cluster centers c _j calculated by the cluster center updating unit 28 described later _, and each of the data points x _i in the period t calculated by the belonging cluster center searching unit 26 described later. And the distance from each of the cluster centers c _j is stored. The period t represents the number of repetitions of the process by the cluster center search 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.

Cluster membership center searching 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 search the cluster a _i belonging of the data points x _i, a distance between each of the data points x _i and the cluster center c _j It is determined whether or not the process of calculating can be omitted.

Moreover, belonging cluster center searching 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, for each data point x _i , the cluster a _i to which it belongs is determined.

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 It is determined that the data point x _i directly belongs to the cluster a _i to which it currently belongs.

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. Based on each of the above, the cluster a _i to which the data point x _i belongs is updated according to the following equation (6).

The cluster center updating unit 28 includes the cluster a _{i to} which each of the data points x _i acquired by the belonging cluster center searching unit 26 belongs, and the D-dimensional coordinate position of each of the data points x _i stored in the parameter storage unit 22. Then, 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. Also, the cluster center update unit 28, for each data point x _i, and each of the respective single cluster a _i data points x _i obtained in cluster membership center searching unit 26, for each of the calculated cluster j of The update frequency coefficient k _i is updated based on the movement distance p _{j, t,} and the update frequency Δt _i is updated based on the updated update frequency coefficient k _i .

Specifically, first, for each cluster j, based on the respective single cluster a _i data points x _i obtained in cluster membership center searching unit 26, each data point x _i belonging to the cluster j To get. Next, clusters For each of j, stored in the parameter storage unit 22, based on the D-dimensional coordinate position of the data point x _i included in the acquired the cluster j, in accordance with the following equation (7), the cluster j The D-dimensional coordinate position of the cluster center c _j, t in period t is updated 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 is calculated and stored in the parameter storage unit 22.

Next, for each data point x _i , the calculated cluster center of the cluster a _i to which the data point x _i belongs

Distance traveled

Based on, based on the above (2) to (4), updates the update frequency coefficients k _i, are 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. In the first embodiment, an evaluation function _{F t-1} of period t-1, the absolute value of the difference between the evaluation function _{F t} of the period _{t | F t -F t-1} | is predetermined threshold If it is below, it is determined that the convergence condition is satisfied.

If the convergence determination unit 30 determines that the convergence condition is satisfied, the classification result of the cluster a _i to which each data point x _i belongs, obtained by the belonging cluster center search unit 26 in the period t, The D-dimensional coordinate position of each cluster center c _j calculated by the cluster center update 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 belonging cluster center search unit 26, the process of the cluster center update unit 28, and the process of the convergence determination unit 30.

  The evaluation function Ft 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 According to First Embodiment>
Next, the operation of the clustering apparatus 100 according to the first embodiment will be described. First, the input unit 10, a set X of data points, and D-dimensional coordinates of each data point x _i in the set X of the upper limit value k _max and the receiving the data point update frequency coefficients, update frequency coefficients _Is stored in the parameter storage unit 22. When the cluster number C is received at the input unit 10, the clustering apparatus 100 executes the clustering processing routine shown in FIGS.

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

Next, in step S <b> 102, the belonging cluster center search unit 26 searches for the cluster a _i to which the data point x _i belongs for each of the data points x _i received in 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

Based on the above, it is determined whether or not the convergence condition is satisfied. 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 determines the classification result of the cluster a _i to which each data point x _i acquired in step S102 belongs and the cluster center c _j of each cluster j acquired in step S104. The D-dimensional 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. 5, 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 reads the upper limit value k _max update frequency coefficients.

  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 belonging cluster center search process in step S102 will be described in detail with reference to FIG.

  In step S300 of FIG. 6, the assigned cluster center search unit 26 sets the value of i to 1.

  Next, in step S302, the assigned cluster center search unit 26 sets the value of t to t + 1.

  Next, in step S304, the belonging cluster center search unit 26 sets the value of j to 1.

  Next, in step S306, the belonging cluster center search unit 26 determines whether or not the value of i is larger than N. If the belonging cluster center search unit 26 determines that the value of i is N or less, the belonging cluster center search process proceeds to step S308. On the other hand, if the belonging cluster center search unit 26 determines that the value of i is greater than N, the belonging cluster center search process ends.

Next, in step S308, the assigned cluster center search 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. If the belonging cluster center search unit 26 determines that the above equation (5) is satisfied, the belonging cluster center searching process proceeds to step S310. On the other hand, if the belonging cluster center search unit 26 determines that the above equation (5) is not satisfied, the data point x _i is assumed to belong to the cluster a _i to which it currently belongs as it is, and the process proceeds to step S318.

  Next, in step S310, the belonging cluster center search unit 26 determines whether the value of j is C or less. If the belonging cluster center search unit 26 determines that the value of j is C or less, the belonging cluster center search process proceeds to step S312. On the other hand, if the belonging cluster center search unit 26 determines that the value of j is greater than C, the belonging cluster center search process proceeds to step S316.

Next, in step S312, the belonging cluster center searching unit 26, a D-dimensional coordinates of the acquired data points _{x i} in step S200, step S202, or cluster centers of the cluster j obtained in 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 assigned cluster center search unit 26 sets the value of j to j + 1, and the assigned cluster center search process proceeds to step S310.

In step S316, the belonging cluster center search unit 26, based on 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, The cluster a _i to which the data point x _i belongs is updated according to the above equation (6).

  Next, in step S318, the assigned cluster center search 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. 7, the cluster center updating 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 centers updating unit 28 acquired in step S200, step S308, and based on each of D-dimensional coordinate position of the data point _{x i} belonging to the cluster j obtained in step S316, the The D-dimensional coordinate position of the cluster center c _{j, t} is calculated according to the equation (7) 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, if 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 S412.

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

  Next, in step S412, the cluster center updating unit 28 sets the value of i to 1.

Next, in step S414, the cluster center updating unit 28 determines whether or not the movement distance of the cluster a _i acquired in step S406 satisfies the above 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 movement distance of the cluster a _i acquired in step S406 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. 8 To do.

  In step S500 of FIG. 8, 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 movement distance of the cluster a _i acquired in step S406 satisfies the above 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 S414 in FIG.

  As described above, according to the clustering device according to the first embodiment, the cluster to which the data point belongs is determined for each of the plurality of data points, and each of the plurality of clusters is determined to belong to the cluster. The center position of the cluster is updated based on the position of the data point, the movement distance of the center position of the cluster before and after the update is calculated, and the calculated data point belongs to each of the plurality of data points. Based on the movement distance of the cluster center position, determine the frequency of performing the process of determining the cluster to which the data point belongs, determine the cluster to which the data point belongs, and Even if the number of data points and the number of clusters are large, by repeating the process of determining the cluster to which they belong, A plurality of data points can be clustered at a high speed.

Further, while the number of calculations per cycle of conventional Lloyd method is NC times, using the clustering apparatus 100 according to the first embodiment, to the number of calculations per cycle N _{I C} Can do. However,

And FIG. 9 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 a restriction on whether or not to be a distance calculation target according to the movement distance immediately before the cluster center, the number of data points for distance calculation is reduced and the total number of distance calculations is reduced. ing.

  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, in the first embodiment, the case where it is determined whether or not the convergence condition is satisfied based on the evaluation function has been described. However, the present invention is not limited to this, and other convergence conditions such as the number of periods are set. It may be used.

  Next, a clustering apparatus according to the second embodiment will be described.

  The second embodiment is different from the first embodiment in that an additional process is added to the Elkan method, which is a k-means speed-up method using a triangle inequality. In addition, about the structure and effect | action similar to the clustering apparatus which concerns on 1st Embodiment, the same code | symbol is attached | subjected and description is abbreviate | omitted.

  First, the omission of calculation by the Elkan method will be described.

The omission of the first calculation, as shown in FIG. 10, the cluster centers of the cluster a _i data points x _i, the data points x _i belongs

, And cluster center

If the nearest cluster center c _j is present, if the following equation (9) is satisfied, the cluster center of the belonging cluster a _i

There, it can be said that the closest to the data point x _i. Therefore, the distance calculation between the data point x _i and all cluster centers can be omitted. Note that u (i) shown in the following equation (10) is the cluster center before update.

The distance between the data points x _i, belonging to the cluster center of the updated

And the upper limit value of the distance between the data point x _i and the cluster center of the cluster.

The omission of the second calculation, as shown in FIG. 11, the cluster centers of the cluster a _i data points x _i, the data points x _i belongs

, And other cluster centers c _j other than the belonging cluster, if the following equation (11) is satisfied, the cluster center of the belonging cluster a _i

Is closer to the data point x _i than the other cluster centers c _j . Therefore, it is possible to omit the distance calculation between the between the data points x _i and other cluster center.

The omission of the third calculation, as shown in FIG. 12, the cluster centers of the cluster a _i data points x _i, the data points x _i belongs

, And other cluster centers c _j other than the belonging cluster, if the following equation (12) is satisfied, the cluster center of the belonging cluster a _i

Is closer to the data point x _i than the other cluster centers c _j . Therefore, it is possible to omit the distance calculation between the between the data points x _i and other cluster center. Incidentally, what l shown below (13) (i, j) is the distance of the other cluster center c _j and the data point x _i before updating, by subtracting the moving distance of the other cluster centers the updated , and the representative of the lower limit of the distance between the cluster membership centered data point x _i.

The omission of the fourth calculation, as shown in FIG. 13, the cluster centers of the cluster a _i data points x _i, the data points x _i belongs

, And other cluster centers c _j other than the belonging cluster, if the following equation (14) is satisfied, the cluster center of the belonging cluster a _i

Is closer to the data point x _i than the other cluster centers c _j . Therefore, it is possible to omit the distance calculation between the between the data points x _i and other cluster center.

The omission of the fifth calculation, as shown in FIG. 14, the cluster centers of the cluster a _i data points x _i, the data points x _i belongs

, And other cluster centers c _j other than the belonging cluster, if the following equation (15) is satisfied, the cluster center of the belonging cluster a _i

Is closer to the data point x _i than the other cluster centers c _j . Therefore, it is possible to omit the distance calculation between the between the data points x _i and other cluster center.

<Configuration of Clustering Device According to Second Embodiment>
Next, the configuration of the clustering apparatus according to the second embodiment will be described. As shown in FIG. 15, the clustering apparatus 200 according to the second embodiment is configured by a computer including a CPU, a RAM, and a ROM that stores a program for executing a clustering processing routine described later and various data. can do. Functionally, the clustering apparatus includes an input unit 10, a calculation unit 220, and an output unit 90 as shown in FIG.

  The calculation unit 220 includes a parameter storage unit 222, an initialization unit 224, a belonging cluster center search unit 226, a cluster center update unit 228, and a convergence determination unit 30.

The parameter storage unit 222, each of the D-dimensional coordinate position of the data point x _i accepted in the input unit 10, and calculates the upper limit value k _max update frequency coefficients, the initialization unit 224 or cluster centers updating unit 228 will be described later has been D-dimensional coordinates of each position of the cluster centers c _j, the distance each between cluster centers c _j of a combination of all of the clusters, and the cluster center c of the closest clusters for each of all the clusters j distance s and (j) between the _j, of each of the calculated data points _{x i} by the initialization unit 224 or cluster centers updating unit 228 to be described later update frequency Delta] t _i, update frequency coefficients _{k i,} a cluster _{a i} belonging cluster center and the upper limit value u of the distance between the data point x _i (i), and the lower limit value of the distance between each of the cluster center and the data point x _i in cluster j (I, j) and each of the moving distance p _j from period t-1 for each of the cluster centers c _j calculated by the cluster centers updating unit 228 to be described later to the period _t, and _t, belonging cluster centers the search to be described later The distance between each of the data points x _i and the cluster center c _j in the period t calculated in the unit 226 is stored.

The initialization unit 224 randomly selects C 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 point x _i to D of the cluster center c _j of the cluster _j . The dimension coordinate position is stored in the parameter storage unit 222. The initialization unit 224 stores the value of the update frequency Δt _i for each data point x _i as 1 in the parameter storage unit 222. Further, the initialization unit 224 stores the value of the update frequency coefficient k _i for each data point x _i as 0 in the parameter storage unit 222. Further, the initialization unit 224 calculates the cluster center distance d (c _j , c _{j ′} ) between each of all the clusters j ( _j ′ ≠ j) and stores it in the parameter storage unit 222. In addition, the initialization unit 224 determines, for each cluster j, the calculated cluster center distance d (c _j , c _{j ′} ) that has the shortest distance to the nearest cluster center of the cluster j. (J) is stored in the parameter storage unit 222. In addition, the initialization unit 224 randomly sets the cluster a _i to which the data point x _i belongs.

Next, the initialization unit 224 receives the D-dimensional coordinate position of each data point x _i received by the input unit 10 stored in the parameter storage unit 222 and the D-dimensional coordinate of each cluster center c _j of the cluster _j. based on the position, for each data point _{x i,} calculate the distance d _{(x i, c j)} and each of the data points _{x i} and cluster j. Then, for each data point _{x i,} the distance d _{(x i, a i)} of the cluster _{a i} of the data points _{x i} belongs to, the upper limit of the distance between the between the affiliation cluster center with the data points _{x i} The value is stored in the parameter storage unit 222 as the value u (i). Then, for each data point _{x i,} of each of the distance d _{(x i, c j)} and the data points _{x i} and the cluster j to the cluster center _{c j} of the data points _{x i} and the cluster j cluster center c _: Stored in the parameter storage unit 222 as each lower limit value l (i, j) of the distance to j.

Cluster membership center search unit 226, 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 unit 222 based on the update frequency Delta] t _i and the current period t at the point x _i, it is judged whether or not the condition equation (5). Moreover, belonging cluster center search unit 226, for each data point x _i, belonging cluster center with the data points x _i of the data points x _i stored in the parameter storage unit 222

Recently, based on the distance between the cluster center c _j beside s (a _i), determining whether or not the condition (9) below the upper limit value u (i), and cluster membership a _i in the distance between the To do. For the data point x _i that does not satisfy the condition of the above expression (5) or satisfies the condition of the above expression (9), the belonging cluster center search unit 226 calculates the _relationship between the data point x _i and all the cluster centers c _j . It is determined that the distance calculation can be omitted. In this case, the data point x _i belongs to the currently belonging cluster a _i as it is.

Next, the belonging cluster center search unit 226 acquires the data point x _i for each data point xi that satisfies the condition of the above expression (5) or does not satisfy the condition of the above expression (9). _i data point x _i and cluster center

And the distance between the center positions of the cluster a _i and the specific cluster j stored in the parameter storage unit 222.

Based on the above, it is determined whether or not the condition of the above expression (11) is satisfied. Moreover, belonging cluster center search unit 226, for each data point x _i to be processed, between the data points x _i and a particular cluster center of the data points x _i stored in the parameter storage unit 222 The lower limit l (i, j) of the distance, the data point x _i of the acquired data point x _i and the cluster center

On the basis of the upper limit value u (i) of the distance between the above and (12). For the combination of the data point x _i and the cluster j that satisfy the condition of the expression (11) or the expression (12), the belonging cluster center search unit 226 determines the data point x _i and the cluster center of the cluster j. c The distance calculation with _j is omitted.

Next, the assigned cluster center search unit 226 is a data point x _i that satisfies the condition of the above expression (5) and does not satisfy the condition of the above expression (9), and further includes the above expression (11). , and for each combination of the cluster j that does not satisfy the condition of equation (12), D-dimensional coordinate position of the data point x _i stored in the parameter storage unit 222, and belongs to the corresponding data points x _i Cluster center of cluster a _i

Based on the D-dimensional coordinate position of the data point and the cluster center

And calculate the distance. Here, stored in the parameter storage unit 222 the calculated distance as u (i) of the data points x _i.

Next, the belonging cluster center search unit 226 is each of the data points x _i that satisfy the above equation (5) and do not satisfy the condition of the above equation (9), and further, the above equation (11), and For each combination with cluster j that does not satisfy the condition of equation (12) above, the calculated data point x _i and the cluster center to which it belongs

And the cluster center of the cluster a _i to which the data point x _i stored in the parameter storage unit 222 belongs

And the distance from the specific cluster center c _j , it is determined whether or not the condition of the above expression (14) is satisfied. Further, the belonging cluster center search unit 226 is a data point x _i that satisfies the condition of the above expression (5) and does not satisfy the condition of the above expression (9), and further includes the above expression (11). , And for each combination with the cluster j that does not satisfy the condition of the above equation (12), the calculated data point x _i and the assigned cluster center

And the lower limit value l (i, l) of the distance between the data point x _i and the specific cluster center c _j stored in the parameter storage unit 222, the above equation (15) It is determined whether or not the above condition is satisfied. For the combination of the data point x _i and the cluster j satisfying the condition of the above equation (14) or the above equation (15), the belonging cluster center search unit 226 is between the data point x _i and the cluster center c _j. The distance calculation of is omitted.

Next, belonging cluster center search unit 226, for each combination of the determined data points x _i and the cluster j and do not skip the computational processing in the above, the data points x _i stored in the parameter storage section 22 The distance between the data point x _i and each of the cluster centers c _j is calculated based on the D-dimensional coordinate positions of the cluster centers and the D-dimensional coordinate positions of the cluster centers c _j . Here, the calculated distance is stored in the parameter storage unit 222 as the lower limit value l (i, l) of the distance between the data point x _i and the specific cluster center c _j .

For each of the data points x _i for which the distance from at least one cluster center c _j is calculated among each of the data points x _i , the calculated data point x _i and each of the cluster centers c _j Distance, the data point x _i and the cluster center to which the data belongs before update

And the cluster a _i to which the data point x _i belongs is updated based on the above equation (6). Note that the data point x _i and the cluster center to which the data belongs before update

Distance between uses distance calculated in the middle of the process of determination of the omission of the calculation of the distance between the other cluster center c _j and the data points x _i.

The cluster center updating unit 228 includes a cluster a _{i to} which each of the data points x _i acquired by the belonging cluster center searching unit 226 belongs and a D-dimensional coordinate position of each of the data points x _i stored in the parameter storage unit 222. Based on the above, the D-dimensional coordinate position of each cluster center c _j of the cluster _j is updated. In addition, the cluster center update unit 228 calculates the movement distance of the D-dimensional coordinate position of the cluster center c _j from the period t−1 to the period t for each of the clusters j. Also, the cluster center updating unit 228, for each data point x _i, the moving distance for each of the clusters a _i for each belonging data point x _i obtained in cluster membership center searching unit 226, the calculated cluster j And the update frequency coefficient k _i is updated, and the update frequency Δt _i is updated based on the updated update frequency coefficient k _i .

Further, the cluster center updating unit 228 calculates the distances between all the cluster centers c _j after the update, and stores them in the parameter storage unit 222. Further, the cluster center updating unit 228 stores, for each cluster j, the smallest distance among all the calculated distances between the cluster centers c _{j in the} parameter storage unit 222 as s (j) of the cluster j. . Also, the cluster center updating unit 228, for each data point _{x i,} the data points _{x i} of u (i), and updates the l (i, j) of each cluster center _{c j.}

Specifically, first, for each data point x _i , it is determined whether or not the cluster a _i to which the data point x _i belongs is changed in the period t−1 and the period t. Here, when the single cluster a _i is changed, the u (i) of the data points x _i, calculated the data points x _i and the cluster membership center in affiliation cluster center search unit 226

And the distance traveled by the calculated cluster center

Is set as u (i) of the data point x _i and stored in the parameter storage unit 222. On the other hand, if the cluster a _{i to} which the member belongs has not been changed, u (i) of the data point x _i stored in the parameter storage unit 222 and the calculated cluster center to which the member belongs.

Distance traveled

Sum of the stores in the parameter storage unit 222 as u (i) of the data points _{x i.} Next, the lower limit value l (i, j) of the distance between each cluster center c _j of the data points x _i each, from the lower limit value l (i, j), the moving distance p of the cluster center c _{j The} value obtained by subtracting _{j, t} is stored in the parameter storage unit 222 as the lower limit l (i, l).

<Operation of Clustering Device According to Second Embodiment>
Next, the operation of the clustering apparatus 200 according to the second embodiment will be described. First, the input unit 10, a set X of data points, and D-dimensional coordinates of each data point x _i in the set X of the upper limit value k _max and the receiving the data point update frequency coefficients, update frequency coefficients _Is stored in the parameter storage unit 222. When the cluster number C is received at the input unit 10, the clustering apparatus 200 executes the clustering processing routine shown in FIGS. 16 to 20.

  First, in step S600 of FIG. 16, the initialization unit 224 sets initial values of various parameters.

Next, in step S <b> 602, the belonging cluster center search unit 226 searches the cluster a _i to which the data point x _i belongs for each of the data points x _i received by the input unit 10.

Next, in step S604, the cluster center updating unit 228 updates the cluster center c _{j, t} of the cluster j for each cluster j. Further, in step S604, the cluster centers updating unit 228, 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.}

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

In step S204 of FIG. 17, the initialization unit 224, 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. Further, the cluster a _i to which each data point x _i belongs and the cluster center to which the data point x _i belongs

Is stored in the parameter storage unit 222.

In step S700, the initialization unit 224 determines the distance between the cluster centers of the combinations between all the clusters of the cluster j based on the D-dimensional coordinate position of each cluster center c _{j, t} of the cluster j acquired in step S204. Is calculated and stored in the parameter storage unit 222.

  Next, in step S702, the initialization unit 224 determines a minimum distance for the cluster j for each cluster j based on the distances between the cluster centers of all combinations of the clusters j acquired in step S700. Obtained as a distance s (j) between cluster centers, and stored in the parameter storage unit 222.

  In step S704, the initialization unit 224 sets the value of j to 1.

  Next, in step S706, the initialization unit 224 determines whether the value of j is C or less. If the initialization unit 224 determines that the value of j is C or less, the process proceeds to step S708. On the other hand, if the initialization unit 224 determines that the value of j is greater than C, the process proceeds to step S714.

Next, in step S 708, the initialization unit 224, based on the D-dimensional coordinates of the acquired data points _{x i} in step S200, to the D-dimensional coordinate position of the cluster centers _{c j} of the cluster j obtained in step S204 , The distance d (x _i , c _j ) between the data point x _i and the cluster center c _j is calculated.

  Next, in step S710, the initialization unit 224 sets the value of j to j + 1, and proceeds to step S706.

Then, the cluster in step S714, the initialization unit 224, each of the distance between each of the acquired data points _{x i} and the cluster center _{c j} in step S 708, and belonging to the data points _{x i} obtained in step S204 a _i and the cluster center

, U (i) of the data point x _i is acquired and stored in the parameter storage unit 222.

  Next, in step S716, the initialization unit 224 sets the value of j to 1.

Next, in step S717, the initialization unit 224 determines whether j ≠ _ai . If the initialization unit 224 determines that j ≠ a _i , the initialization process proceeds to step S718. On the other hand, if the initialization unit 224 determines that j = a _i , the initialization process proceeds to step S722.

  In step S718, the initialization unit 224 determines whether the value of j is C or less. If the initialization unit 224 determines that the value of j is C or less, the initialization process proceeds to step S720. On the other hand, if the initialization unit 224 determines that the value of j is greater than C, the initialization process proceeds to step S212.

In step S720, the initialization unit 224, the distance d _{(x i, c j)} of each of the acquired data points _{x i} and the cluster center _{c j} in step S708 based on, and the data point _{x i} and cluster j L (i, j) of the combinations is determined.

  Next, in step S722, the initialization unit 224 sets the value of j to j + 1, and proceeds to step S717.

  The belonging cluster center search process in step S602 will be described in detail with reference to FIG.

In step S800 of FIG. 18, the assigned cluster center search unit 226 performs u (i) of the data point x _i acquired in step S714, step S904 in the process of cycle t−1, or step S914, and step S702, Alternatively, based on s (a _i ) acquired in step S928 in the process of cycle t−1, it is determined whether or not the condition of the above expression (9) is satisfied. If the belonging cluster center search unit 226 determines that the condition of the above equation (9) is satisfied, the belonging cluster center searching process is assumed to belong to the cluster a _i currently belonging to the data x _i as it is. The process proceeds to S318. On the other hand, when the belonging cluster center search unit 226 determines that the condition of the above expression (9) is not satisfied, the belonging cluster center search process moves to step S801.

Next, in step S801, the belonging cluster center search unit 226 determines whether or not the value of j is a _i . If the belonging cluster center search unit 226 determines that the value of j is not a _i , the belonging cluster center search process proceeds to step S310. On the other hand, if the belonging cluster center search unit 226 determines that the value of j is a _i , the belonging cluster center search process proceeds to step S314.

In step S802, the cluster center search unit 226 belongs to the cluster center to which the data point x _i acquired in step S700 or the process of step S926 in the process of the period t−1 belongs.

And the distance between the cluster center c _j

To get.

Next, in step S804, the belonging cluster center search unit 226 performs u (i) of the data point x _i acquired in step S714 or step S904 in the process of cycle t−1 or step S914, and in step S802. Obtained distance

Based on the above, it is determined whether or not the condition of the above expression (11) is satisfied. If the belonging cluster center search unit 226 determines that the condition of the above expression (11) is satisfied, the belonging cluster center searching process proceeds to step S314. On the other hand, if the belonging cluster center search unit 226 determines that the condition of the above expression (11) is not satisfied, the belonging cluster center search process moves to step S806.

In step S806, the assigned cluster center search unit 226 determines u (i) of the data point x _i acquired in step S714 or step S904 or step S914 in the process of cycle t−1, and step S720 or cycle t. Based on the data point x _i acquired in step S910 in step −1 or step S920 and l (i, j) of the combination of cluster j, it is determined whether or not the above equation (12) is satisfied. When the belonging cluster center search unit 226 determines that the condition of the above expression (12) is satisfied, the belonging cluster center searching process proceeds to step S314. On the other hand, if the belonging cluster center search unit 226 determines that the condition of the above expression (12) is not satisfied, the belonging cluster center search process moves to step S808.

In step S808, the belonging cluster center search unit 226 determines the D-dimensional coordinate position of the data point x _i obtained in step S200 and the cluster of the belonging cluster a _i obtained in step S204 or step S404 in the process of cycle t-1. center

Based on the D-dimensional coordinate position of a data point x _i, a cluster a _i belonging of the data points x _i cluster center

Distance to

Calculate

  Next, in step S810, the belonging cluster center search unit 226 determines the distance acquired in step S808.

Is stored in the parameter storage unit 222 as u (i) of the data point x _i .

  Next, in step S812, the cluster center search unit 226 belongs to the distance acquired in step S808.

And the distance acquired in step S802

Based on the above, it is determined whether or not the condition of the above expression (14) is satisfied. When the belonging cluster center search unit 226 determines that the condition of the above expression (14) is satisfied, the belonging cluster center searching process proceeds to step S314. On the other hand, if the belonging cluster center search unit 226 determines that the condition of the above expression (14) is not satisfied, the belonging cluster center search process moves to step S814.

  Next, in step S814, the cluster center search unit 226 belongs to the distance acquired in step S808.

And the above formula (15) based on l (i, j) of the combination of the data point x _i and the cluster j acquired in step S720, or in step S910 in step t920 or in step S920. Determine whether the condition is met. If the belonging cluster center search unit 226 determines that the condition of the above equation (15) is satisfied, the process proceeds to step S314. On the other hand, if the belonging cluster center search unit 226 determines that the condition of the above equation (15) is not satisfied, the process proceeds to step S312.

In step S816, the assigned cluster center search unit 226 sets the parameter storage unit as d (x _i , c _{j, t} ) acquired in step S312 as l (i, j) of the combination of the data point x _i and the cluster j. 222.

In step S818, the belonging cluster center search unit 226 determines each of the distances d (x _i , c _{j, t} ) acquired in step S312 and the distance acquired in step S808.

Based on the above, the cluster a _i to which the data point x _i belongs is determined according to the above equation (6).

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

In step S899 of FIG. 19, the cluster center updating unit 228 acquired in step S200, step S308, based step S800, and each of the D-dimensional coordinate position of the data point _{x i} belonging to the cluster j obtained in step S818 Then, the D-dimensional coordinate position of the cluster center c _{j, t} is calculated according to the above equation (7), and stored in the parameter storage unit 222.

  In step S900, the cluster center update unit 228 determines whether the value of i is N or less. If the cluster center update unit 228 determines that the value of i is N or less, the cluster center update process proceeds to step S902. On the other hand, if the cluster center updating unit 228 determines that the value of i is greater than N, the cluster center updating process proceeds to step S926.

Next, in step S902, the cluster center updating unit 228 determines whether or not the cluster a _i to which the data point x _i belongs has been changed from the period t−1 in step S818. If the cluster center update unit 228 determines that the cluster center has been changed, the cluster center update process proceeds to step S904. On the other hand, when the cluster center update unit 228 determines that the change has not been made, the cluster center update process proceeds to step S914.

Next, in step S904, the cluster center updating unit 228 determines the distance between the data point x _i acquired in step S312 and the cluster center of the cluster a _i to which it belongs and the cluster center of the cluster a _i acquired in step S406. The sum with the movement distance is set as u (i) of the x _i and stored in the parameter storage unit 222.

  Next, in step S906, the cluster center updating unit 228 sets the value of j to 1.

Next, in step S907, the cluster center updating unit 228 determines whether the value of j is not a _i . If the cluster center updating unit 228 determines that the value of j is not a _i , the process proceeds to step S908. On the other hand, if the cluster center updating unit 228 determines that the value of j is a _i , the process proceeds to step S912.

  Next, in step S908, the cluster center update unit 228 determines whether the value of j is C or less. When the cluster center update unit 228 determines that the value of j is C or less, the cluster center update process proceeds to step S910. On the other hand, when the cluster center updating unit 228 determines that the value of j is larger than C, the cluster center updating process proceeds to step S924.

Next, in step S910, the cluster centers updating unit 228, the combination of l (i, j) between the data points _{x i} and the cluster j stored in the parameter storage unit 222 and, in the cluster j obtained in step S406 Based on the movement distance of the cluster center c _j , the combination l (i, j) of the data point x _i and the cluster j is updated and stored in the parameter storage unit 222. If the cluster j is the cluster a _i belonging to the data point x _{i in} the period t−1, the distance acquired in step 808 of FIG.

Based on the movement distance of the cluster center c _j of the corresponding cluster j acquired in step S406, it is stored in the parameter storage unit 222 as l (i, j) of the combination of the data point x _i and the cluster j. .

  Next, in step S912, the cluster center update unit 228 sets the value of j to j + 1, and proceeds to step S907.

In step S914, the cluster centers updating unit 228, the upper limit value u of the data points _{x i} stored in the parameter storage unit 222 (i), based on the moving distance of the cluster _{a i} obtained at step S406, the data The upper limit value u (i) of the point x _i is updated and stored in the parameter storage unit 222.

  Next, in step S916, the cluster center updating unit 228 sets the value of j to 1.

Next, in step S917, the cluster center update unit 228 determines whether the value of j is not a _i . If the cluster center updating unit 228 determines that the value of j is not a _i , the process proceeds to step S918. On the other hand, when the cluster center updating unit 228 determines that the value of j is a _i , the process proceeds to step S922.

  Next, in step S918, the cluster center update unit 228 determines whether the value of j is C or less. If the cluster center update unit 228 determines that the value of j is C or less, the cluster center update process proceeds to step S920. On the other hand, when the cluster center updating unit 228 determines that the value of j is larger than C, the cluster center updating process proceeds to step S924.

Next, in step S920, the cluster centers updating unit 228, the combination of l (i, j) between the data points _{x i} and the cluster j stored in the parameter storage unit 222 and, in the cluster j obtained in step S406 Based on the movement distance of the cluster center c _j , the combination l (i, j) of the data point x _i and the cluster j is updated and stored in the parameter storage unit 222.

  Next, in step S922, the cluster center update unit 228 sets the value of j to j + 1, and proceeds to step S917.

  In step S924, the cluster center updating unit 228 sets the value of i to i + 1, and proceeds to step S900.

  In step S926, the cluster center update unit 228 calculates the distance between the cluster centers of all combinations of clusters j based on the D-dimensional coordinate positions of each cluster j acquired in step S899, and the parameter storage unit 222. To remember.

  Next, in step S928, the cluster center updating unit 228 acquires s (j) for each of the clusters j based on the distances between the cluster centers of all the combinations of clusters j acquired in step S926. It memorize | stores in the memory | storage part 222, and transfers to step S414 of FIG.

  As described above, according to the clustering apparatus according to the second embodiment, the cluster to which the data point belongs is determined for each of the plurality of data points, and each of the plurality of clusters is determined to belong to the cluster. The center position of the cluster is updated based on the position of the data point, the movement distance of the center position of the cluster before and after the update is calculated, and the calculated data point belongs to each of the plurality of data points. Based on the movement distance of the cluster center position, determine the frequency of performing the process of determining the cluster to which the data point belongs, determine the cluster to which the data point belongs, and Even if the number of data points and the number of clusters are large, by repeating the process of determining the cluster to which they belong, A plurality of data points can be clustered at a high speed.

Further, while the number of calculations per cycle of conventional Elkan methods are N _{E C} E _D times, the use of the clustering apparatus 200 according to the second embodiment, the number of calculations per cycle N _{I , E} C _E D. However, N _{I, E} <N _E <N, C _E <C.

  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.

  Next, a clustering apparatus according to the third embodiment will be described.

  The third embodiment is different from the first and second embodiments in that additional processing is added to the Hammerly method, which is a k-means speed-up method using a triangle inequality. In addition, about the structure and effect | action similar to the clustering apparatus which concerns on 1st and 2nd embodiment, the same code | symbol is attached | subjected and description is abbreviate | omitted.

  First, the omission of calculation by the Hammerly method will be described. The Hammerly method is a k-means speed-up method that uses the triangle inequality and saves the memory of the Elkan method.

The omission of the first calculation, as shown in FIG. 10, the cluster centers of the cluster a _i data points x _i, the data points x _i belongs

, And cluster center

If the nearest cluster center c _j is present, if the above equation (9) is satisfied, the cluster center of the belonging cluster a _i

There, it can be said that the closest to the data point x _i. Therefore, the distance calculation between the data point x _i and all cluster centers can be omitted. Note that u (i) shown in the above equation (10) is the cluster center before update.

The distance between the data points x _i, belonging to the cluster center of the updated

And the upper limit value of the distance between the data point x _i and the cluster center of the cluster.

The omission of the second calculation, as shown in FIG. 21, the cluster centers of the cluster a _i data points x _i, the data points x _i belongs

, And the cluster center c _{j that} is second closest to the data point x _i other than the cluster belonging to the cluster, and if the following equation (16) is satisfied, the cluster center of the cluster a _i belonging

Can be said to be closer to the data point x _i than the second closest cluster center c _j .

Therefore, the distance calculation between the data point x _i and all cluster centers can be omitted. Incidentally, l shown in the above (16) (i) is the distance between the pre-update data points _{x i} and the cluster center _{c j} and the data points _{x i} second nearest data points _{x i} after updating and 2 th is obtained by subtracting the moving distance of the near cluster center, it represents the lower limit of the distance between the between the data points x _i and the data point x _i and second close cluster center.

The omission of the third calculation, as shown in FIG. 22, the cluster centers of the cluster a _i data points x _i, the data points x _i belongs

, And cluster center

And the nearest cluster center c _j, if the following equation (17) is satisfied, the cluster center of the belonging cluster a _i

Can be said to be closer to the data point x _i than the nearest cluster center c _j . Therefore, the distance calculation between the data point x _i and all cluster centers can be omitted.

The omission of the fourth calculation, as shown in FIG. 23, the cluster centers of the cluster a _i data points x _i, the data points x _i belongs

, And the cluster center c _{j that} is second closest to the data point x _i , the cluster center of the cluster a _i belonging to the cluster a _i if the following equation (18) is satisfied

Can be said to be closer to the data point x _i than the second closest cluster center c _j .

Therefore, the distance calculation between the data point x _i and all cluster centers can be omitted.

<Configuration of Clustering Device According to Third Embodiment>
Next, the configuration of the clustering apparatus according to the third embodiment will be described. As shown in FIG. 24, the clustering apparatus 300 according to the third embodiment is configured by a computer including a CPU, a RAM, and a ROM that stores a program for executing a clustering processing routine described later and various data. can do. Functionally, the clustering apparatus includes an input unit 10, a calculation unit 320, and an output unit 90 as shown in FIG.

  The calculation unit 320 includes a parameter storage unit 322, an initialization unit 324, an assigned cluster center search unit 326, a cluster center update unit 328, and a convergence determination unit 30.

The parameter storage unit 322 calculates the D-dimensional coordinate position of each data point x _i received by the input unit 10 and the upper limit value k _max of the update frequency coefficient, and the initialization unit 324 or the cluster center update unit 328 described later. has been D-dimensional coordinates of each position of the cluster centers c _j, the distance each between cluster centers c _j of a combination of all of the clusters, and the cluster center c of the closest clusters for each of all the clusters j distance s and (j) between the _j, of each of the calculated data points _{x i} by the initialization unit 324 or cluster centers updating unit 328 to be described later update frequency Delta] t _i, update frequency coefficients _{k i,} a cluster _{a i} belonging The upper limit u (i) of the distance between the cluster center and the data point x _i and the distance between the data center x _i and the second closest cluster center to the data point x _i Each of the lower limit value l (i) of each of these, the movement distance p _{j, t} of each of the cluster centers c _j calculated by the cluster center updating unit 328, which will be described later, from the period t-1 to the period t _, and the cluster to be described later and each data point x _i in the calculated period t at the center searching unit 326, the distance between each of the cluster center c _j is stored.

The initialization unit 324 randomly selects C 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 point x _i to D of the cluster center c _j of the cluster _j . The dimensional coordinate position is stored in the parameter storage unit 322. In addition, the initialization unit 324 stores the value of the update frequency Δt _i for each data point x _i as 1 in the parameter storage unit 322. In addition, the initialization unit 324 stores the value of the update frequency coefficient k _i for each data point x _i as 0 in the parameter storage unit 322. Further, the initialization unit 324 calculates a cluster center distance d (c _j , c _{j ′} ) between each of all the clusters j ( _j ′ ≠ j) and stores it in the parameter storage unit 322. In addition, the initialization unit 324 determines, for each cluster j, the calculated cluster center distance d (c _j , c _{j ′} ) that has the smallest distance from the nearest cluster center of the cluster j. (J) is stored in the parameter storage unit 322. Further, the initialization unit 324 randomly sets the cluster a _i to which each data point x _i belongs.

Next, the initialization unit 324 receives the D-dimensional coordinate position of each data point x _i received by the input unit 10 stored in the parameter storage unit 322 and the D-dimensional coordinate of each cluster center c _j of the cluster _j. based on the position, for each data point _{x i,} calculate the distance d _{(x i, c j)} and each of the data points _{x i} and cluster j. Then, for each data point _{x i,} the distance d _{(x i, a i)} of the cluster _{a i} of the data points _{x i} belongs to, the upper limit of the distance between the between the affiliation cluster center with the data points _{x i} The value is stored in the parameter storage unit 222 as the value u (i). Then, for each data point _{x i,} a distance between the data point _{x i} and the cluster center _{c j} close to the second d _{(x i, c j)} and the data points _{x i} and the cluster center closest to the second c _: Stored in the parameter storage unit 322 as the lower limit value l (i) of the distance to _j .

For each of a plurality of data points x _i included in the data point set X received by the input unit 10, the belonging cluster center search unit 326 stores the data stored in the parameter storage unit 322 for the data point x _i. based on the update frequency Delta] t _i and the current period t at the point x _i, it is judged whether or not the condition equation (5). Moreover, belonging cluster center searching unit 326, for each data point x _i, belonging cluster center with the data points x _i of the data points x _i stored in the parameter storage unit 322

Recently, based on the distance between the cluster center c _j beside s (a _i), determining whether or not the condition (9) below the upper limit value u (i), and cluster membership a _i in the distance between the To do.

In addition, the belonging cluster center search unit 326 stores, for each data point x _i , the acquired upper limit value u (i) of the distance between the data point x _i and the belonging cluster center, and the parameter storage unit 322. , based on the lower limit of the distance between the initial section 324 or the cluster j and the data points x _i close to the acquired data points x _i and second in cluster center updating unit 328 of the previous process l (i), It is determined whether or not the condition of the above equation (16) is satisfied. The cluster center search unit 326 belongs to all the cluster centers c _j for the data point x _i that does not satisfy the above expression (5) or satisfies the condition of the above expression (9) or (16). It is determined that the distance calculation can be omitted. In this case, the data point x _i belongs to the currently belonging cluster a _i as it is.

Here, how to specify the second closest cluster j will be described. First, in the first process, the second smallest distance among the distances between each of the data points x _i calculated by the initialization unit 324 and stored in the parameter storage unit 322 and each of the cluster centers c _j. corresponding cluster j is the cluster j the second closest to the data point x _i on. On the other hand, in the second and subsequent processing, the timing of the cluster j is changed closer to the second particular data point x _i is the timing of the cluster a _i is changed that belong to a particular data point x _i. Therefore, in the processing, since the distance between the data point x _i and all the cluster centers c _j is calculated, the second of the calculated distances between the specific data point x _i and the cluster center c _j A cluster j corresponding to a small distance is identified as the second closest cluster j.

Next, the belonging cluster center search unit 326 performs a parameter storage unit for each data point x _i that satisfies the condition of the expression (5) and does not satisfy the conditions of the expression (9) and the expression (16). 322 are stored, D-dimensional coordinate position of the data point x _i, and on the basis of the D-dimensional coordinate position of the cluster centers of the cluster a _i that belongs of the data points x _i, belonging to the data points x _i Calculate the distance from the cluster center. Here, stored in the parameter storage unit 322 the calculated distance as u (i) of the data points x _i.

Next, the belonging cluster center search unit 326 performs a parameter storage unit for each data point x _i that satisfies the condition of the expression (5) and does not satisfy the conditions of the expression (9) and the expression (16). 322 are stored, and s of cluster _{a i} belonging of the data points _{x i (a i),} belonging cluster center and calculated data points _{x i}

And whether or not the condition of the above equation (17) is satisfied. In addition, the belonging cluster center search unit 326 satisfies the condition of the above equation (5) and the parameter storage unit 322 for each data point x _i that does not satisfy the conditions of the above equation (9) and the above equation (16). the lower limit of the distance between the stored initialization section 324 or the previous process of cluster centers update the data points acquired in the unit 328 x _i and the cluster j and the data points x _i second closest to the l (i ), The calculated data point x _i and the cluster center

And whether or not the condition of the above equation (18) is satisfied. The belonging cluster center search unit 326 determines that the distance calculation with respect to all cluster centers c _j can be omitted for the data point x _i satisfying the condition of the expression (18) or the expression (17). . In this case, the data point x _i belongs to the currently belonging cluster a _i as it is.

Next, the belonging cluster center search unit 326, for the data point x _i determined not to omit the calculation processing in the above, the D-dimensional coordinate position of the data point x _i stored in the parameter storage unit 22, and the cluster based on the D-dimensional coordinate position of each of the center c _j, calculating the corresponding data points x _i, a distance between each cluster center c _j.

Then, of each data point x _i, the distance for each of the cluster centers c _j data points x _i where the distance between each calculated, and the calculated corresponding data points x _i, with each of the cluster center c _j And the data point x _i and the cluster center to which the data belongs before update

And the cluster a _i to which the data point x _i belongs is updated based on the above equation (6). Note that the data point x _i and the cluster center to which the data belongs before update

Distance between uses distance calculated in the middle of the process of determination of the omission of the calculation of the distance between the other cluster center c _j and the data points x _i.

<Operation of Clustering Device According to Third Embodiment>
Next, the operation of the clustering apparatus 300 according to the third embodiment will be described. First, the input unit 10, a set X of data points, and D-dimensional coordinates of each data point x _i in the set X of the upper limit value k _max and the receiving the data point update frequency coefficients, update frequency coefficients _Is stored in the parameter storage unit 222. When the cluster number C is received by the input unit 10, the clustering apparatus 300 executes the clustering processing routine shown in FIGS. 20, 25A, 25B, 26, and 27.

  In step S950 of FIG. 25A, the initialization unit 324 sets initial values of various parameters.

Next, in step S1000, for each data point x _i received by the input unit 10, the belonging cluster center search unit 326 searches for the cluster a _i to which the data point x _i belongs.

Next, in step S1002, the cluster center updating unit 328 updates the cluster center c _{j, t} of the cluster j for each cluster j. Further, in step S1002, the cluster centers updating unit 328, 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.}

  The initialization process in step S950 will be described in detail with reference to FIG. 25B.

In step S952 of FIG. 25B, the initialization unit 324 determines that the data point x _i and the cluster center c _j are the second closest cluster c based on each of the distances d (x _i , c _j ) acquired in step S708. the distance between the _{j d (x i, c j} ) as l (i) of the data points _{x i,} stored in the parameter storage unit 322.

  The belonging cluster center search process in step S1000 will be described in detail with reference to FIG.

In step S1102 of FIG. 26, the cluster center searching unit 326 belongs to u (i) of the data point x _i acquired in step S714 or step S904 in the process of cycle t−1 or step S914, and the parameter storage unit. 322 based on the l (i) of the data points x _i which is stored in, it is judged whether or not the condition of the above (16). If the belonging cluster center search unit 326 determines that the condition of the above expression (16) is satisfied, the belonging cluster center searching process proceeds to step S318. On the other hand, if the affiliated cluster center search unit 326 determines that the condition of the above expression (16) is not satisfied, the affiliated cluster center search process proceeds to step S808.

  In step S1104, the cluster center search unit 326 belongs to the distance acquired in step S808.

Based on s (j) of the cluster a _i to which it belongs stored in the parameter storage unit 222, it is determined whether or not the condition of the above equation (17) is satisfied. If the belonging cluster center search unit 326 determines that the condition of the above expression (17) is satisfied, the belonging cluster center searching process proceeds to step S318. On the other hand, if the belonging cluster center search unit 326 determines that the condition of the above equation (17) is not satisfied, the belonging cluster center search process moves to step S1106.

  Next, in step S1106, the belonging cluster center search unit 326 determines the distance acquired in step S808.

If, based on the l of the data points x _i stored in the parameter storage unit 322 (i), above (18) determines whether the type of conditions are satisfied, belongs cluster center search unit 326, If it is determined that the condition of the above equation (18) is satisfied, the belonging cluster center search process proceeds to step S318. On the other hand, if the belonging cluster center search unit 326 determines that the condition of the above equation (18) is not satisfied, the belonging cluster center search process moves to step S801.

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

In step S1199 in FIG. 27, the cluster center updating unit 228 acquires the data point x _i belonging to the cluster j acquired in step S308, step S800, step S818, step S1102, step S1104, and step S1106 acquired in step S200. Based on each D-dimensional coordinate position, the D-dimensional coordinate position of the cluster center c _{j, t} is calculated according to the above equation (7) and stored in the parameter storage unit 322.

In step S1200 of FIG. 27, the cluster center updating unit 328 sets the cluster j that is the second smallest distance among the distances d (x _i , c _j ) acquired in step S312 to the data point x _i second. A near cluster center c _j , a distance d (x _i , c _j ) between the data point x _i acquired in step S312 and the cluster center c _j, and a movement distance of the cluster center c _j acquired in step S406 Based on the above, l (i) of the data point x _i is updated and stored in the parameter storage unit 322.

In step S1202, the cluster centers updating unit 328 periodically t-1 in step S1200, or the l (i) of the data points _{x i} obtained in step S1202, the acquired in step S406, the corresponding relevant data points _{x i} If based on the moving distance between the cluster center c _j close to the second, it updates the l (i) of the data points x _i, stored in the parameter storage unit 322.

  In step S928 of FIG. 27, the cluster center updating unit 328 acquires s (j) for each of the clusters j based on the distances between the cluster centers of all the combinations of clusters j acquired in step S926. It memorize | stores in the memory | storage part 222, and transfers to step S414 of FIG.

  As described above, according to the clustering device according to the third embodiment, the cluster to which the data point belongs is determined for each of the plurality of data points, and each of the plurality of clusters is determined to belong to the cluster. The center position of the cluster is updated based on the position of the data point, the movement distance of the center position of the cluster before and after the update is calculated, and the calculated data point belongs to each of the plurality of data points. Based on the movement distance of the cluster center position, determine the frequency of performing the process of determining the cluster to which the data point belongs, determine the cluster to which the data point belongs, and Even if the number of data points and the number of clusters are large, by repeating the process of determining the cluster to which they belong, A plurality of data points can be clustered at a high speed.

In addition, the number of calculations per cycle in the conventional Hamery method is N _H CD, whereas the number of calculations per cycle can be calculated as N _{I, H} by using the clustering apparatus 300 according to the third embodiment. It can be a CD. However, NI _{, H} <N _H <N.

  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.

  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 Operation part 22 Parameter storage part 24 Initialization part 26 Affiliation cluster center search part 28 Cluster center update part 30 Convergence determination part 90 Output part 100 Clustering apparatus 200 Clustering apparatus 220 Operation part 222 Parameter storage part 224 Initialization part 226 Affiliated cluster center search unit 228 Cluster center update unit 300 Clustering device 320 Calculation unit 322 Parameter storage unit 324 Initialization unit 326 Affiliated cluster center search unit 328 Cluster center update unit

Claims (7)

A clustering device for clustering a plurality of data points into a plurality of clusters,
For each of the plurality of data points, the distance between the position of the data point and the center position of each of the plurality of clusters is calculated, and the cluster to which the data point belongs is determined based on each of the calculated distances. A cluster center search unit to be determined;
For each of the plurality of clusters, the center position of the cluster is updated based on the position of the data point determined to belong to the cluster by the belonging cluster center search unit, and the cluster before and after the update is updated. Calculate the movement distance of the center position,
For each of the plurality of data points, based on the calculated movement distance of the center position of the cluster to which the data point belongs, a process of determining the cluster to which the data point belongs by the belonging cluster center search unit. A cluster center updater that determines how often to perform,
A convergence determination unit that repeats the determination by the cluster center search unit and the determination by the cluster center update unit until a predetermined convergence condition is satisfied,
Including
The belonging cluster center search unit determines, for each of the plurality of data points, whether to determine a cluster to belong to based on the frequency determined for the data point by the cluster center update unit, For each of the data points determined to determine a cluster to be determined, a distance from the center position of each of the plurality of clusters is calculated, and based on each of the calculated distances, the cluster to which the data point belongs is calculated. Determine the clustering device. 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 the ratio of the movement distance of the center position of the cluster to which the data point x _i belongs is the denominator and the predetermined value is the numerator.


As described above, the value of the processing count t of the cluster center search 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−γ 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. The belonging cluster center search unit has a center position of a cluster to which the data point belongs and a center position closest to the center position of the belonging cluster for each of the data points determined to determine the belonging cluster. The distance between the data point and the center position of each of the plurality of clusters when the distance from the center position of the cluster is at least twice the upper limit of the distance between the data point and the center position of the cluster to which it belongs; The clustering apparatus according to claim 1 or 2, wherein a cluster to which the data point belongs is determined without calculating. The belonging cluster center search unit, for each of the data points determined to determine the cluster to which it belongs,
The distance between the center position of the cluster to which the data point belongs and the center position of the cluster to which the data point does not belong is at least twice the upper limit of the distance between the data point and the center position of the cluster to which the data point belongs. Or if the upper limit of the distance is less than or equal to the lower limit of the distance between the data point and the center position of the cluster that does not belong,
Do not calculate the distance between the data point and the center position of the cluster that does not belong, and the distance between the data point and the center position of the cluster to which the data point belongs,
When the distance between the center position of the cluster to which the data point belongs and the center position of the cluster to which the data point does not belong is more than twice the distance between the data point and the center position of the cluster to which the data point belongs, or If the distance between the data point and the center position of the cluster to which the data point belongs is equal to or less than the lower limit of the distance, the data point and the center position of the cluster that does not belong are not calculated and the data is calculated. The clustering apparatus according to claim 3, wherein a cluster to which a point belongs is determined. The belonging cluster center search unit, for each of the data points determined to determine the cluster to which it belongs,
When the lower limit value of the distance between the data point and the center position of the cluster closest to the data point is not less than the upper limit value of the distance between the data point and the center position of the cluster to which the data point belongs, or The distance between the center position of the cluster to which the data point belongs and the center position of the cluster having the center position closest to the center position of the cluster to which the data point belongs are the data point and the center position of the cluster to which the data point belongs. If the distance between the data point and the center position of the cluster to which the data point belongs is less than or equal to the lower limit of the distance, the data point and the plurality of clusters 4. The clustering apparatus according to claim 3, wherein a cluster to which the data point belongs is determined without calculating a distance from each center position. A clustering method in a clustering apparatus for clustering a plurality of data points into a plurality of clusters, including a belonging cluster center search unit, a cluster center update unit, and a convergence determination unit,
The belonging cluster center search unit calculates a distance between the position of the data point and the center position of each of the plurality of clusters for each of the plurality of data points, and based on each of the calculated distances, Determine the cluster to which the data point belongs;
The cluster center updating unit updates the center position of the cluster based on the position of the data point determined to belong to the cluster by the belonging cluster center search unit for each of the plurality of clusters. And the movement distance of the center position of the updated cluster,
For each of the plurality of data points, based on the calculated movement distance of the center position of the cluster to which the data point belongs, a process of determining the cluster to which the data point belongs by the belonging cluster center search unit. Determine how often,
The convergence determination unit repeats the determination by the belonging cluster center search unit and the determination by the cluster center update unit until a predetermined convergence condition is satisfied,
Including
The belonging cluster center search unit determines, for each of the plurality of data points, whether to determine a cluster to belong to based on the frequency determined for the data point by the cluster center update unit, For each of the data points determined to determine a cluster to be determined, a distance from the center position of each of the plurality of clusters is calculated, and based on each of the calculated distances, the cluster to which the data point belongs is calculated. Determine the clustering method.   The program for functioning a computer as each part of the clustering apparatus of any one of Claims 1-5.