JP5255484B2 - Clustering distance learning device and program thereof, and clustering device - Google Patents

Description

  The present invention relates to a clustering distance learning device that learns a parameter of a distance between data used as a similarity when performing clustering, a program thereof, and a clustering device using the same.

  2. Description of the Related Art Conventionally, a clustering technique for classifying a plurality of pieces of data with unknown classification categories into similar identical clusters in image processing, language processing, and the like (see, for example, Patent Document 1). In such a clustering technique, the distance between data is used as the similarity in determining whether or not the data are similar. As this distance, Euclidean distance or cosine distance is generally used, and the distance scale is generally fixed.

In addition, in the conventional clustering, an unsupervised method for performing classification without using teacher data has been established, but recently, a supervised method is used, and research is being conducted as semi-supervised clustering (Non-patent Document 1). reference). This semi-supervised clustering is a method in which information related to the cluster is given to some of the data to be clustered in advance to perform learning related to clustering in advance, and other data to be clustered is clustered according to the learning result. It is. In this learning, in order to obtain better clustering performance, it is desirable to set the distance measure according to the learning data.
Therefore, conventionally, in this learning, a method has been proposed in which the Mahalanobis distance is used as a distance and a distance scale, that is, a parameter of the Mahalanobis distance is estimated by an iterative solution (see Non-Patent Document 2).

Japanese Patent No. 2967312

S. Basu, M. Bilenko and R. J. Mooney: “A probabilistic framework for semi-supervised clustering”, Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 59-68 (2004). E. P. Xing, A. Y. Ng, M. I. Jordan and S. Russell: “Distance metric learning, with application to clustering with side-information”, Neural Information Processing Systems (NIPS) (2003).

In the conventional method of performing clustering with the distance scale fixed using the Euclidean distance or the cosine distance, there is no parameter to be adjusted according to the learning data. Therefore, the conventional method has a problem that optimal clustering according to data to be clustered (for example, according to data distribution characteristics) cannot be performed.
Moreover, in the method of estimating the parameter of Mahalanobis distance beforehand from learning data using the conventional Mahalanobis distance, iterative calculation is performed when performing the estimation. Therefore, the conventional method has a problem that it takes time to estimate the parameter of the Mahalanobis distance.

  The present invention has been made in view of the above problems, and is a clustering distance learning device capable of estimating Mahalanobis distance parameters used for semi-supervised clustering from learning data without performing iterative operations. It is an object to provide a program and a clustering apparatus thereof.

  The present invention was devised to achieve the above object. First, the clustering distance learning device according to claim 1 performs clustering of a plurality of data based on a distance that is a similarity of data feature amounts. A clustering distance learning device that learns the Mahalanobis distance parameters used in the above configuration, and includes a cluster center storage unit, a learning data input unit, and a parameter calculation unit.

  In this configuration, the clustering distance learning device stores the cluster center value in the data feature amount space for each cluster in the cluster center storage unit. The cluster center is a coordinate value in the feature amount space for each cluster when data is clustered. The feature amount space is a coordinate space using one or more feature amounts of data as vectors. Here, the feature amount of data is an index for classifying each data. For example, in the case of language processing, cepstrum coefficients extracted by analyzing speech data and morphological analysis of document data are performed. The appearance frequency of the extracted morpheme.

  Then, the clustering distance learning device inputs learning data that is known data as to which cluster belongs to the learning data input means. Here, the learning data is the same kind of data as the data to be clustered, and is used to estimate the Mahalanobis distance parameter. In order to make the learning data cluster known, the learning data input means may input the learning data collectively for each cluster after the cluster is designated. Alternatively, the learning data itself may include the cluster information. It is good also as inputting by adding.

  Then, the clustering distance learning device provides a predetermined constraint condition on the sum of diagonal components of the product of the matrix for calculating the Mahalanobis distance and the transposed matrix of the matrix by the parameter calculation means, and the learning data input means A matrix is calculated as a Mahalanobis distance parameter based on the input learning data and the cluster center stored in the cluster center storage unit corresponding to the cluster of the learning data. That is, the clustering distance learning apparatus specifies a matrix that is a parameter for calculating the Mahalanobis distance without iterative calculation by providing a predetermined constraint condition in the parameter calculation means.

Further, the clustering distance learning device according to claim 2 is the clustering distance learning device according to claim 1, wherein the constraint condition for the matrix A is tr (A ^T A) = 1, where A is the matrix. And the parameter calculation means sets the learning data to x, the subscript of x identifying the learning data to n, n ′, the cluster center to μ, and the subscript of μ to identify the cluster at the cluster center to k, k ′. , R _nk and r _{n′k ′} are attribute values having a value “1” when the learning data x of the subscripts n and n ′ belong to the cluster of the subscripts k and k ′, and a value “0” _otherwise . When the above example A is expressed,

It was set as the structure which calculates by.

In such a configuration, by providing the constraint condition, the estimation of the parameter of the Mahalanobis distance can be solved as a minimization problem with a constraint condition that minimizes the Mahalanobis distance in the learning data. Therefore, the clustering distance learning device estimates the parameter (matrix) of the Mahalanobis distance by calculating the example A which is a solution to the constraint condition minimization problem by the parameter calculation means.
In this way, the clustering distance learning device estimates the Mahalanobis distance parameter (matrix) using a unique expression, and thus does not need to perform iterative calculations.

  Further, the clustering distance learning program according to claim 3 is configured to input a learning data into a computer in order to learn a Mahalanobis distance parameter used when clustering a plurality of data based on a distance that is a similarity of data feature amounts. And function as a parameter calculation means.

In such a configuration, the clustering distance learning program inputs learning data that is known data to which cluster it belongs by the learning data input means. Then, the clustering distance learning program sets the constraint condition for the matrix A to tr (A ^T A) = 1, the learning data x, and A, where A is a matrix for calculating the Mahalanobis distance by the parameter calculation means. The subscripts of x for identifying the learning data are n, n ', the cluster center for each cluster in the feature amount space of the data stored in the cluster center storage means is μ, and the subscript of μ for identifying the cluster at the cluster center is k. , k ', the subscript n, n' learning data x is the subscript k of, k 'value "1" if it belongs to a cluster of, and the other takes the value "0" when the attribute value _r nk, _{r n'} When represented by _{k ′} , example A is

Calculate by

  Further, the clustering device according to claim 4 includes a distance learning unit that learns a parameter of the Mahalanobis distance in a clustering device that clusters a plurality of data using the Mahalanobis distance for the similarity of the feature amount of the data, The distance learning unit includes a cluster center storage unit, a learning data input unit, and a parameter calculation unit.

  In such a configuration, the clustering apparatus stores the cluster center value in the data feature space for each cluster in the cluster center storage means. Further, the clustering apparatus inputs learning data, which is known data to which cluster belongs, by the learning data input means. The clustering device provides a predetermined constraint condition for the sum of diagonal components of the product of the matrix for calculating the Mahalanobis distance and the transposed matrix of the matrix by the parameter calculation means, and is input by the learning data input means. The matrix is calculated as a Mahalanobis distance parameter based on the learned data and the cluster center stored in the cluster center storage unit corresponding to the cluster of the learned data.

Furthermore, the clustering device according to claim 5 is the clustering device according to claim 4, wherein when the matrix is A, the constraint condition for the matrix A is tr (A ^T A) = 1, and parameter calculation is performed. The means is x for the learning data, n and n ′ for the x for identifying the learning data, μ for the cluster center, k and k ′ for the cluster for identifying the cluster at the cluster center, and n, When the learning data x of n ′ is represented by r _nk , r _{n′k ′} , the attribute value taking the value “1” when it belongs to the cluster of subscripts k and k ′, and the value “0” _otherwise . Example line A

It was set as the structure which calculates by.

  In such a configuration, by providing the constraint condition, the estimation of the parameter of the Mahalanobis distance can be solved as a minimization problem with a constraint condition that minimizes the Mahalanobis distance in the learning data. Therefore, the clustering apparatus estimates the Mahalanobis distance parameter (matrix) by calculating the example A which is the solution of the constraint-conditional minimization problem by the parameter calculation means.

The present invention has the following excellent effects.
According to the first to third aspects of the present invention, the Mahalanobis distance parameter (matrix) used for clustering can be adjusted according to the learning data. Thereby, in the clustering apparatus, it is possible to estimate a parameter capable of accurately clustering data to be clustered. According to the first to third aspects of the present invention, the estimation of the Mahalanobis distance parameter (matrix) can be obtained without iterative calculation. As a result, the CPU load can be reduced and the parameter estimation time can be shortened.

  According to the fourth and fifth aspects of the present invention, the Mahalanobis distance parameter (matrix) used for clustering can be adjusted according to the learning data, and the clustering target data can be clustered with high accuracy. Further, according to the fourth and fifth aspects of the present invention, the estimation of the Mahalanobis distance parameter (matrix) can be obtained without iterative calculation. As a result, the CPU load can be reduced and the parameter estimation time can be shortened.

It is a schematic block diagram which shows the whole structure of the clustering apparatus which concerns on embodiment of this invention. It is a detailed block diagram which shows the whole structure of the clustering apparatus which concerns on embodiment of this invention. It is a flowchart which shows the learning operation | movement (parameter estimation operation | movement) in the distance learning means of the clustering apparatus which concerns on embodiment of this invention. It is a flowchart which shows the clustering execution operation | movement in the clustering execution means of the clustering apparatus concerning embodiment of this invention.

Hereinafter, embodiments of the present invention will be described with reference to the drawings.
[Overview of clustering equipment]
First, an overview of a clustering apparatus including distance learning means (clustering distance learning apparatus) according to an embodiment of the present invention will be described with reference to FIG.
The clustering apparatus 1 shown in FIG. 1 uses a distance learning unit 2 to estimate a Mahalanobis distance parameter (a symmetric positive definite matrix) to be used for the distance that is the similarity of the data feature amount from the learning data.
The Mahalanobis distance M (a, b) between the vectors a and b is a distance defined by the following equation (1) using a matrix (symmetric positive definite matrix) A. T represents a transposed matrix.

That is, the Mahalanobis distance is a distance specified by the matrix A. Therefore, the clustering apparatus 1 uses the distance learning unit 2 to estimate the matrix A used for calculating the Mahalanobis distance from the learning data as a parameter.
At this time, the distance learning means 2 estimates the parameter without performing the iterative calculation by providing a constraint condition in advance for the parameter (symmetric positive definite matrix).

  Then, the clustering device 1 uses the Mahalanobis distance having the parameter (matrix A) estimated by the distance learning unit 2 as the distance between the cluster center and the data in the feature amount space by the clustering execution unit 3, and k-average (k The data is clustered for each cluster by the -means) method.

As described above, the clustering device 1 realizes a semi-supervised clustering method that estimates the Mahalanobis distance parameter (symmetric positive definite matrix) from the given learning data and performs clustering using the Mahalanobis distance. is there.
Hereinafter, the configuration and operation of the clustering apparatus according to the embodiment of the present invention will be sequentially described.

[Configuration of clustering device]
First, the configuration of the clustering apparatus according to the embodiment of the present invention will be described with reference to FIG. The clustering device 1 is a device that clusters a plurality of data by using the Mahalanobis distance as the similarity of the feature amount of the data. Here, the clustering apparatus 1 includes distance learning means 2 and clustering execution means 3.

  The distance learning means (clustering distance learning apparatus) 2 learns (estimates) the Mahalanobis distance parameter used in the clustering execution means 3 described later. Here, the distance learning unit 2 includes a storage unit 21, a learning data input unit 22, a feature amount extraction unit 23, and a parameter calculation unit 24.

The storage means (cluster center storage means) 21 stores a cluster center value for each predetermined number of data classifications (number of clusters), and is a general storage device such as a hard disk.
The cluster center value stored in the storage means 21 is not particularly limited as long as a predetermined number (K) of clusters is prepared. For example, all cluster centers μ _k (k = 1, 2,..., K) are set as origins in the feature amount space as shown in the following equation (2).

  The storage means 21 also stores a line example (parameter) A of Mahalanobis distance calculated by the parameter calculation means 24 described later.

  The learning data input means 22 inputs learning data for learning a parameter of Mahalanobis distance from the outside. This learning data is data in which the cluster belongs is known. For example, the learning data input unit 22 may input the learning data collectively for each cluster after the cluster is specified, or may input the learning data itself by adding the cluster information.

  The learning data is the same type of data that is clustered by the clustering execution means 3. Note that the learning data may be any data as long as the data can be classified by the feature amount, such as image data, audio data, document data, and the like. The learning data input unit 22 outputs the input learning data to the feature amount extraction unit 23.

The feature amount extraction unit 23 extracts the feature amount of the learning data input by the learning data input unit 22. Note that the feature quantity extraction means 23 determines the type of feature quantity to be extracted from the learning data in advance according to the type of learning data. Alternatively, when the type of learning data is fixed, a predetermined unique feature amount may be extracted.
For example, when the learning data is image data, the feature amount extraction unit 23 can extract a color distribution, a motion vector, and the like as feature amounts. Further, when the learning data is speech data, a cepstrum coefficient or the like, and when the learning data is document data, the appearance frequency or the like of the morpheme can be used as the feature amount.

The one or more feature amounts extracted by the feature amount extraction unit 23 are represented by vectors on the feature amount space. That is, one learning data is represented by one point on the feature amount space. Then, the feature quantity extraction unit 23 outputs the feature quantity extracted for each learning data to the parameter calculation unit 24. In the following description, the feature amount extracted for each learning data is referred to as a vector, and the learning data represented by the feature amount vector is expressed as x _n (n = 1, 2,..., N).

The parameter calculation means 24 is input to the learning data x _n (n = 1, 2,..., N), which is input by the learning data input means 22 and extracted by the feature quantity extraction means 23, and the learning data cluster. Correspondingly, based on the cluster centers μ _k (k = 1, 2,..., K) stored in the storage means 21, a Mahalanobis distance matrix is calculated as a parameter.

The parameter calculation means 24 writes and stores the matrix obtained by the calculation in the storage means 21. The matrix A stored in the storage means 21 is used to calculate the Mahalanobis distance from the cluster center μ _k when the clustering execution means 3 clusters data.
Specifically, the parameter calculation means 24 calculates the Mahalanobis distance matrix A by the following equation (3).

In this equation (3), the learning data is represented by _xn which is a vector notation. The subscript n is information for identifying the learning data and is {1, 2,..., N}. The cluster center is represented by μ _k which is a vector notation. The subscript k is information for identifying a cluster and is {1, 2,..., K}. Further, here, the attribute value is represented by r _nk . This attribute value is expressed in a 1-of-k notation that takes the value “1” when the data of the subscript n belongs to the cluster of the subscript k, and the value “0” otherwise. In the equation (3), the subscripts n ′ and k ′ have the same meaning as the subscripts n and k, respectively, and are used to distinguish the variable of the double summation symbol Σ. T represents a transposed matrix, and tr (•) represents the sum (trace) of diagonal components in the matrix in parentheses.

As described above, the parameter calculation unit 24 calculates the matrix A by using the learning data _xn and the cluster center μ _k without performing iterative calculation. The reason why the matrix of the Mahalanobis distance can be estimated by this calculation will be described later.

  The clustering execution means (clustering execution apparatus) 3 uses the Mahalanobis distance parameter (matrix) estimated by the distance learning means 2 to cluster the data to be clustered by the k-means method. is there. Here, the clustering execution unit 3 includes a data input unit 31, a feature amount extraction unit 32, a cluster generation unit 33, a cluster center update unit 34, and a cluster determination unit 35.

  The data input means 31 is for inputting data to be clustered from the outside. This data is the same type of learning data used for learning the Mahalanobis distance parameter in the distance learning means 2. In other words, this data may be any data as long as it can be classified by the feature amount, such as image data, audio data, document data, and the like. The data input unit 31 outputs the input data to the feature amount extraction unit 32.

  The feature quantity extraction unit 32 extracts the feature quantity of the data input by the data input unit 31. The feature quantity extraction means 32 determines the type of feature quantity to be extracted from the data in advance according to the type of data. Alternatively, when the data type is fixed, a predetermined characteristic amount may be extracted. The feature amount extracted by the feature amount extraction unit 32 is the same type as the feature amount extracted by the feature amount extraction unit 32 of the distance learning unit 2.

The one or more feature quantities extracted by the feature quantity extraction unit 32 are represented by vectors in the feature quantity space. That is, one piece of data is represented by one point on the feature amount space. Then, the feature quantity extraction unit 32 outputs the feature quantity extracted for each data to the cluster generation unit 33. In the following description, a feature amount extracted for each data is referred to as a vector, and data represented by the feature amount vector is expressed as z _m (m = 1, 2,..., M).

The cluster generation means 33 is estimated by the distance learning means 2 for the data z _m (m = 1, 2,..., M) input by the data input means 31 and extracted by the feature quantity extraction means 32. A cluster is generated using the Mahalanobis distance parameter (matrix A).

Here, the cluster generation means 33 calculates the distance between the cluster center μ _k and the data z _m by the above equation (1) using the matrix A estimated by the distance learning means 2, and the data z _m By assigning (classifying) to the near cluster center μ _k , K clusters are generated. The cluster generation unit 33 expands the generated K clusters in a memory (not shown) in association with the cluster center μ _k and the data z _m . Note that the initial value of the cluster center in the cluster generation means 33 is the center of the cluster assigned by dividing the data z _m by the number K of clusters. For example, the average of the data belonging to each cluster on the feature amount space is used.

Further, the cluster generation unit 33 outputs a cluster developed in a memory (not shown) as a cluster result when an end of cluster generation is instructed by the cluster determination unit 35 described later. The cluster generation unit 33 performs clustering of the data z _m using the updated cluster center in the cluster center update unit 34 described later when the cluster determination unit 35 described later instructs the continuation of cluster generation. .

The cluster center update unit 34 updates the cluster center based on the cluster generated by the cluster generation unit 33. That is, the cluster center updating unit 34 obtains the center of gravity of the data z _m belonging to the cluster in the feature amount space for each cluster generated by the cluster generating unit 33, thereby setting the new cluster center of the cluster. The cluster center update unit 34 writes the new cluster center in a memory (not shown) in association with the old cluster center.

The cluster determination unit 35 determines the end of clustering based on the distance (Euclidean distance) between the cluster center updated by the cluster center update unit 34 and the old cluster center. For example, when the distance (update amount) between the updated cluster center and the old cluster center is equal to or less than a predetermined distance (threshold value), the cluster determination unit 35 determines that the clustering has been completed. Further, when it is determined that the clustering has been completed, the cluster determination unit 35 instructs the cluster generation unit 33 to end the cluster generation.
Note that the cluster determination unit 35 may perform clustering of data at the updated cluster center in the cluster generation unit 33, and may determine that clustering has been completed when there is no change in the assigned cluster.

  As described above, the clustering device 1 can estimate the Mahalanobis distance parameter based on the learning data as semi-supervised clustering, and cluster the clustering target data using the parameter. At this time, the clustering apparatus 1 can estimate the Mahalanobis distance parameter without iterative calculation in the distance learning means 2, and can estimate the parameter at high speed from the learning data.

  Further, the clustering apparatus 1 can be realized by a general computer having a CPU and a memory (not shown). At this time, the clustering apparatus 1 can be operated by a clustering program that causes the computer to function as each of the means described above.

Although the embodiment of the present invention has been described above, the present invention is not limited to this embodiment. For example, here, the clustering device 1 is configured to include the feature amount extraction units 23 and 32 in the distance learning unit 2 and the clustering execution unit 3, respectively. However, the clustering device 1 is configured as one unit, and input data (learning data, The output destination (parameter calculation means 24 or cluster generation means 33) may be switched according to the cluster target data.
Further, the feature amount extraction means 23 and 32 may be omitted from the configuration when learning data from which feature amounts have been extracted in advance or cluster target data is input from the outside.

Here, the value of the cluster center μ _k stored in the storage means 21 is the origin on the feature amount space as shown in the equation (2), but as shown in the following equation (4), It is good also as the average (global average) on the feature-value space of the learning data _xn whole.

Alternatively, the value of the cluster center μ _k may be an average (cluster average) in the feature amount space of the learning data x _n for each cluster k as shown in the following equation (5).

  Here, the clustering device 1 is composed of the distance learning means 2 and the clustering execution means 3, but each of these means may be configured as an independent device (clustering distance learning device, clustering execution device). Good.

  In this case, the clustering distance learning device (distance learning means 2) and the clustering execution device (clustering execution means 3) can each be realized by a general computer equipped with a CPU and memory not shown. Further, the clustering distance learning device (distance learning means 2) can be operated by a clustering distance learning program that causes the computer to function as each means described in the distance learning means 2. Further, the clustering execution device (clustering execution means 3) can be operated by a clustering execution program that causes the computer to function as each means described in the clustering execution means 3.

[Operation of clustering device]
Next, with reference to FIGS. 3 and 4, the operation of the clustering apparatus according to the embodiment of the present invention will be described. Here, the operation of the clustering apparatus 1 will be described by dividing it into a learning operation (parameter estimation operation) performed in the distance learning means 2 and a clustering execution operation performed in the clustering execution means 3.

(Learning action)
First, a learning operation (parameter estimation operation) of the clustering apparatus 1 (distance learning means 2) will be described with reference to FIG. Here, it is assumed that the origin on the feature amount space is stored in advance in the storage unit 21 as K cluster centers μ _k .

First, the clustering device 1 inputs learning data with a known cluster for learning the Mahalanobis distance parameter from the outside by the learning data input unit 22 of the distance learning unit 2 (step S10).
Then, the clustering apparatus 1 extracts the feature amount of the learning data input in step S10 by the feature amount extraction unit 23 of the distance learning unit 2 (step S11).

Thereafter, the clustering device 1 applies the learning data x _n (n = 1, 2,..., N) from which the feature amount is extracted in step S11 by the parameter calculation unit 24 of the distance learning unit 2 and the cluster of the learning data. Correspondingly, based on the cluster centers μ _k (k = 1, 2,..., K) stored in the storage means 21, a matrix A of Mahalanobis distances is calculated by the equation (3) (step S12). .
Then, the clustering apparatus 1 writes and stores the Mahalanobis distance matrix A obtained by the calculation in step S12 in the storage unit 21 by the parameter calculation unit 24 of the distance learning unit 2 (step S13).

With the above operation, the clustering apparatus 1 can estimate the matrix A used for calculating the Mahalanobis distance by learning.
Here, the description has been made assuming that K cluster centers μ _k are stored in the storage means 21 in advance. However, as shown in the above equations (4) and (5), according to the learning data, The cluster center value may be calculated and stored in the storage unit 21. In this case, after step S11, the clustering apparatus 1 performs the above-described equations (4) and (5) based on the learning data _xn from which the feature amount is extracted in step S11 by the parameter calculation unit 24 of the distance learning unit 2. The cluster center μ _k is calculated by performing the calculation shown in FIG.

(Clustering execution operation)
Next, the clustering execution operation of the clustering apparatus 1 (clustering execution means 3) will be described with reference to FIG. 4 (refer to FIG. 2 as appropriate for the configuration).
First, the clustering device 1 inputs data to be clustered from the outside by the data input means 31 of the clustering execution means 3 (step S20).
Then, the clustering device 1 extracts the feature amount of the data input in step S20 by the feature amount extraction unit 32 of the clustering execution unit 3 (step S21).

Thereafter, the clustering device 1 divides the data z _m (m = 1, 2,..., M) from which the feature amount is extracted in step S21 by the cluster generation unit 33 of the clustering execution unit 3 by the number of clusters K, respectively. The initial value of the cluster center is calculated by obtaining the average of the data belonging to the cluster in the feature amount space (step S22).

The clustering apparatus 1 then determines the distance between the cluster center μ _k and the data z _m (m = 1, 2,..., M) from which the feature amount is extracted in step S21 by the cluster generation unit 33 of the clustering execution unit 3. Is calculated by the equation (1) using the matrix A estimated by the distance learning means 2 and stored in the storage means 21, and the data z _m is assigned (classified) to the nearest cluster center μ _k. Thus, K clusters are generated (step S23).

Then, the clustering apparatus 1, the cluster centers updating means 34 clustering execution unit 3, for each cluster generated in step S23, by obtaining the centroid in the feature quantity space of the data z _m belonging to the cluster, the cluster center Update to a new cluster center (step S24).
Here, the clustering apparatus 1 determines that the distance difference (update amount) between the cluster center updated in step S24 and the old cluster center by the cluster determination unit 35 of the clustering execution unit 3 is equal to or less than a predetermined distance (threshold). It is determined whether or not (step S25).

When the distance difference (update amount) is equal to or smaller than the threshold (Yes in Step S25), the clustering apparatus 1 outputs the cluster result by the cluster generation unit 33 of the clustering execution unit 3 (Step S26). On the other hand, when the distance difference (update amount) is larger than the threshold value (No in step S25), the clustering apparatus 1 returns to step S23 and performs an operation of generating a cluster with the updated cluster center by the cluster generation unit 33. To do.
With the above operation, the clustering apparatus 1 can cluster data for each cluster using the Mahalanobis distance by the k-means method.

  Here, the end of cluster generation is determined in step S25 depending on whether the distance difference (update amount) between the updated cluster center and the old cluster center is equal to or smaller than a predetermined distance (threshold). However, it is not limited to this method. For example, when a cluster is generated at the updated cluster center in step S23, it may be determined to end when there is no change in the allocated cluster.

[Explanation of Mahalanobis distance parameter estimation method]
Next, the clustering device 1 can obtain the parameter (matrix) used for the calculation of the Mahalanobis distance by the calculation of the equation (3) without performing the iterative calculation in the parameter calculation unit 24 of the distance learning unit 2. The reason will be explained.

Learning the Mahalanobis distance M (see the above equation (1)) that clusters the learning data x _n with the highest accuracy is regarded as a problem of minimizing the function J of the matrix A and the cluster center μ _k shown in the following equation (6). be able to.

This function J sums the sum of the Mahalanobis distance M between the cluster center μ _k of the cluster k and the learning data x _n belonging to the cluster k for all clusters k (k = 1, 2,..., K). It is a function. Note that r _nk takes a value “1” when the learning data of the subscript n belongs to the cluster of the subscript k, and takes a value “0” otherwise.
Here, when the function J (A, μ _k ) is partially differentiated by the matrix A, the following expression (7) is obtained.

The right side of the equation (7) is a covariance matrix. That is, the diagonal component of the covariance matrix is positive unless x _n = μ _k , and the value of equation (7) continues to increase, so there is no minimum solution. Therefore, the following equation (8) is introduced as a constraint condition for limiting the size of the matrix A.

T represents a transposed matrix, and tr (•) represents the sum (trace) of diagonal components of the matrix in parentheses.
Since the problem of determining the matrix A that minimizes the expression (6) under the constraint condition of the equation (8) is a constraint condition minimization problem, the Lagrange undetermined multiplier α is introduced and (9) Equation (9) should be minimized.

  Here, when this equation (9) is partially differentiated by the matrix A, the following equation (10) is obtained.

  The matrix A in which the expression (10) has a value “0” is obtained by the following expression (11).

  Here, when the matrix A obtained by the equation (11) is substituted into the constraint condition of the equation (8), the following equation (12) is obtained.

  The following equation (13) is obtained by modifying the equation (12).

By substituting the result of the equation (13) into the equation (11), the matrix A of the equation (3) can be obtained.
As described above, by providing a constraint condition on the matrix A, the matrix A shown in the equation (3) becomes a matrix for calculating the Mahalanobis distance M for clustering the learning data _xn with the highest accuracy. Accordingly, the parameter calculation unit 24 of the distance learning unit 2 described with reference to FIG. 2 can learn a matrix for accurately clustering the learning data by the calculation of the equation (3) without iterating the matrix A. it can.

Here, as a constraint condition, the value of tr (A ^T A) is set to “1”, but this value does not have to be “1” and may be an arbitrary constant.
That is, when the constant is c, the constraint condition is the following equation (14).

  In this case, the matrix A shown in the equation (15) can be obtained by modifying the equations similar to the equations (12) and (13).

  Therefore, the parameter calculation unit 24 of the distance learning unit 2 described in FIG. 2 may calculate the matrix A using the equation (15) instead of the equation (3). However, in equation (15), since the decimal point operation is performed by 1 / c, it can be said that the constant c is preferably “1” in order to reduce the load on the CPU.

DESCRIPTION OF SYMBOLS 1 Clustering apparatus 2 Distance learning means (clustering distance learning apparatus)
21 Storage means (cluster center storage means)
22 learning data input means 23 feature quantity extraction means 24 parameter calculation means 3 clustering execution means (clustering execution apparatus)
31 Data Input Unit 32 Feature Extraction Unit 33 Cluster Generation Unit 34 Cluster Center Update Unit 35 Cluster Determination Unit

Claims (5)

A clustering distance learning device for learning a Mahalanobis distance parameter used when clustering a plurality of data according to a distance that is a similarity of a feature amount of data,
Cluster center storage means for storing a cluster center value in the feature amount space of the data for each cluster;
Learning data input means for inputting learning data which is known data to which cluster belongs,
A predetermined constraint condition is provided for the sum of diagonal components of the product of the matrix for calculating the Mahalanobis distance and the transposed matrix of the matrix, the learning data input by the learning data input means, and the learning data Parameter computing means for computing the matrix as the parameter based on the cluster center stored in the cluster center storage means corresponding to the cluster;
A clustering distance learning device comprising: When the matrix is A, the constraint condition for the matrix A is tr (A ^T A) = 1,
The parameter calculation means is
The learning data is x, the subscript of x identifying the learning data is n, n ′, the cluster center is μ, the subscript of μ identifying the cluster at the cluster center is k, k ′, and the subscripts n, n ′. When the learning data x is represented by r _nk and r _{n′k ′ as} attribute values having a value “1” when the learning data x belongs to a cluster of subscripts k and k ′, and the value “0” _otherwise. The

The clustering distance learning device according to claim 1, wherein calculation is performed by: In order to learn the Mahalanobis distance parameter used when clustering a plurality of data according to the distance that is the similarity of the feature amount of the data,
Learning data input means for inputting learning data which is known data to which cluster belongs,
When the matrix for calculating the Mahalanobis distance is A, the constraint condition for the matrix A is tr (A ^T A) = 1,
The learning data is x, the subscripts of x identifying the learning data are n, n ′, the cluster center for each cluster in the feature amount space of the data stored in the cluster center storage means is μ, and the cluster at the cluster center Is an attribute that takes the value “1” when the learning data x of the subscripts k and k ′, the subscripts n and n ′ belong to the cluster of the subscripts k and k ′, and the value “0” otherwise. When the value is represented by r _nk , r _{n′k ′} , the line example A is

Parameter calculation means for calculating by
Clustering distance learning program characterized by functioning as In a clustering apparatus that clusters a plurality of data using the Mahalanobis distance for the similarity of the data feature amount,
A distance learning means for learning the Mahalanobis distance parameter;
The distance learning means includes
Cluster center storage means for storing a cluster center value in the feature amount space of the data for each cluster;
Learning data input means for inputting learning data which is known data to which cluster belongs,
A predetermined constraint condition is provided for the sum of diagonal components of the product of the matrix for calculating the Mahalanobis distance and the transposed matrix of the matrix, the learning data input by the learning data input means, and the learning data Parameter computing means for computing the matrix as the parameter based on the cluster center stored in the cluster center storage means corresponding to the cluster;
A clustering apparatus comprising: When the matrix is A, the constraint condition for the matrix A is tr (A ^T A) = 1,
The parameter calculation means is
The learning data is x, the subscript of x identifying the learning data is n, n ′, the cluster center is μ, the subscript of μ identifying the cluster at the cluster center is k, k ′, and the subscripts n, n ′. When the learning data x is represented by r _nk and r _{n′k ′ as} attribute values having a value “1” when the learning data x belongs to a cluster of subscripts k and k ′, and the value “0” _otherwise. The

The clustering apparatus according to claim 4, wherein the calculation is performed by:

Images