JP5501896B2 - Pattern extraction apparatus, pattern extraction method, and pattern extraction program - Google Patents

Description

  The present invention relates to supervised machine learning, and more particularly to a pattern extraction method for classifying data such as text and images.

Conventionally, as a pattern extraction method, there has been a technique called linear discriminant analysis as shown in Non-Patent Document 1. In the linear discriminant analysis, patterns z _i εR ^c−1 , c that are easy to classify from given n sets of data x _i εR ^m and their labels y _i ε {1,. <M is extracted.

w _i is selected to maximize the ratio J (w) of the interclass variance to the intraclass variance.

  This can be obtained by solving the following generalized eigenvalue problem.

w _i is the eigenvector of the upper c-1 eigenvalues.

  For example, given class 1 and class 2 data as shown in FIG. 9, the vector w is obtained as a straight line indicated by w in FIG. In this example, the number of classes c = 2, and 1 (= c-1) -dimensional features are obtained. The extracted pattern is as shown in FIG. 10, and it can be seen that class 1 and class 2 are well separated on the x-axis (note that FIG. 10 shows that the results of class 1 and class 2 are easy to see. The value has been shifted.)

C. M.M. Bishop, Hiroshi Motoda, Takio Kurita, Tomoyuki Higuchi, Yuji Matsumoto, Noboru Murata, “Pattern Recognition and Machine Learning”, Springer Japan, December 2007, pp. 177-190.

However, the linear discriminant analysis described above has the following three problems.
1. Only dimensional features of class number c-1 can be obtained.
2. Since each class c data assumes a Gaussian distribution, it does not fit multimodal data.
3. Only features that separate the average values of each class c are obtained.

  In particular, when data of class 1 and class 2 as shown in FIG. 11 are given, the vector w is obtained as a straight line indicated by w in FIG. 11, and the extracted pattern is as shown in FIG. The average values of the data of class 1 and class 2 in FIG. 11 are almost equal, and the data of class 1 are multimodal, so class 1 and class 2 cannot be separated on the x-axis (note that FIG. (The y-axis value is shifted so that the result of class 2 is easy to see.)

  The present invention solves the above-mentioned problems, and it is a main object to provide a pattern extraction device that can obtain features of dimensions more than the number of classes and can also classify even multimodal data.

  One aspect of the pattern extraction apparatus of the present invention is a pattern extraction apparatus that extracts a pattern for class classification from input data, and calculates the intra-class similarity of the input data. A calculation means; an interclass distance calculation means for calculating a distance between classes of the input data; a compression distortion calculation means for calculating a compression distortion that is a difference between the input data and the extracted pattern; and the data And a projection matrix calculation means for obtaining a projection matrix that reduces the compression distortion from the compressed expression and normalizing the projection matrix, and the data and the projection matrix reduce the compression distortion, and the intraclass similarity and the interclass distance And a compressed expression calculation means for calculating a compressed expression that increases, and extracts a pattern for class classification based on the projection matrix and the compressed expression. Characterized in that it.

  One aspect of the pattern extraction method of the present invention is a pattern extraction method for extracting a pattern for class classification from input data, wherein the intra-class similarity calculation means includes an intra-class similarity of the input data. An intra-class similarity calculation step for calculating a degree, an inter-class distance calculation means for calculating an inter-class distance calculation step for calculating an inter-class distance of the input data, and a compression distortion calculation means for extracting the input data and A step of calculating a compression distortion that is a difference from the pattern formed, and a projection matrix calculation means for obtaining a projection matrix that reduces the compression distortion from the data and the compressed expression, and a projection matrix calculation step of normalizing the projection matrix And the compressed expression calculation means reduces the compression distortion from the data and the projection matrix, and the similarity between classes and the distance between classes are Has a compressed representation calculating step of calculating the listening becomes compressed representation, and based on the compressed representation and the projection matrix, and extracts a pattern for performing the classification.

  The present invention can also be configured as a program for causing a computer to function as each means configuring the pattern extraction apparatus. This program may be provided through a network or may be stored in a recording medium.

  According to the present invention, it is possible to provide a pattern extraction device that can obtain features of dimensions more than the number of classes and can also classify multi-modal data.

It is a block diagram of the pattern extraction device in an embodiment. It is a flowchart which shows the process step of the pattern extraction apparatus in embodiment. It is a hardware block diagram of the pattern extraction apparatus of this embodiment. It is a figure which shows the data in the specific example of embodiment. It is a figure which shows the data and W in the specific example (t = 1) of embodiment. It is a figure which shows the data and W in the specific example (t = 2) of embodiment. It is a figure which shows the data and W in the specific example (t = 3) of embodiment. It is a figure which shows the data in the specific example of embodiment. It is a figure which shows the data and w in the conventional pattern extraction method. It is a figure which shows the data in the conventional pattern extraction method. It is a figure which shows the data and w in the conventional pattern extraction method. It is a figure which shows the data in the conventional pattern extraction method.

  The present invention extracts a pattern for class classification from input data. When extracting a pattern, data in a class is arranged close to each other, and data between classes is arranged far away. The pattern is corrected. As a result, the extracted pattern can be easily separated between classes.

  In addition, by reducing the difference (compression distortion) between the given data and the extracted pattern, the information of the original data is held as much as possible. As a result, it is possible to effectively extract features exceeding the number of classes.

[Embodiment]
≪Configuration example≫
The pattern extraction apparatus 1 in this embodiment is demonstrated based on FIGS.

  The pattern extraction apparatus 1 is used for supervised machine learning, and classifies data such as text and images, for example.

  As shown in FIG. 3, the pattern extraction apparatus 1 is constituted by a computer, and includes hardware resources of a normal computer, that is, ROM 11, RAM 12, CPU 13, communication interface (I / F) 14, hard disk drive device 15, storage A medium reader 16 and a storage medium 17 are provided.

  As a result of the cooperation between the hardware resource and the software resource, the pattern extraction apparatus 1 includes a data input unit 2, a management unit 3, an intraclass similarity calculation unit 4, Distance calculation means 5, compression distortion calculation means 6, projection matrix calculation means 7, compression expression calculation means 8, and result output means 9 are provided.

The pattern extraction apparatus 1 in the present embodiment inputs data X (x _i ,..., X _n ) from the data input means 2, and the management means 3 uses the average value μ of all data (x _i ,..., X _n ). And subtract the average value μ from all data (x _i ,..., X _n ).

  Then, the intraclass similarity calculator 4 calculates the similarity of the data in the class, and the interclass distance calculator 5 calculates the distance of the data between classes. The compression distortion calculation means 6 calculates the difference (compression distortion) between the given data and the extracted pattern.

  The projection matrix calculation means 7 obtains a projection matrix W that reduces the compression distortion from the data and the compressed expression H. The compressed representation calculation means 8 obtains a compressed representation H from the data X and the projection matrix W that reduces the compression distortion and increases the intraclass similarity and the interclass distance.

The pattern extraction apparatus 1 according to this embodiment includes data X = (х ₁ ,..., Х _n ), х _i ∈R ^m , labels y∈ {1,... C} (c is the number of classes), and the dimension of the feature to be extracted The input is a number k (0 <k <m), a degree α ≧ 0 that emphasizes intra-class similarity, a degree β ≧ 0 that emphasizes distance between classes, a scale of distance σ> 0, and a repetition number T> 0. , A projection matrix W, an average value μ of all data, and a compressed expression H are output.

FIG. 2 is a flowchart showing the processing steps (S1 to S6) of the pattern extraction apparatus 1 in the present embodiment. The pattern extraction method in the present invention includes the following procedures.
S1: Input data X, label y, feature dimension number k to be extracted, degree α emphasizing intraclass similarity, degree β emphasizing distance between classes, distance scale σ, and number of repetitions T.
S2: Intraclass similarity L ^W , interclass distance L ^B , and compressed representation H are initialized.
(For t = 1 to do)
S3: It is determined whether or not t is smaller than the repetition number T.
S4: A projection matrix W is calculated.
S5: The compressed expression H is calculated.
(End for)
S6: A projection matrix W, an average value μ, and a compressed expression H are output.

  Hereinafter, each of the steps (S1 to S6) will be described in detail.

S1: (Data input)
The data input means 2 receives data Х (х ₁ ,..., Х _n ), label y∈ {1,... C} (c is the number of classes), and parameters (characteristics to be extracted) from a network or a file. Number of dimensions k (0 <k <m), degree α ≧ 0 that emphasizes intra-class similarity, degree β ≧ 0 that emphasizes distance between classes, distance scale σ> 0, and number of repetitions T> 0) input.

S2: (Initialization)
[Management means 3]
An average value μ of all data (x ₁ ,..., X _n ) is calculated by the following equation (9).

As shown in the following equation (10), the average value μ is subtracted from all the data (x ₁ ,..., X _n ).

  The size of the projection matrix W is m × k, and the size of the compressed representation H is k × n. Here, m and n indicate the number of rows and columns of the data X, and k indicates the number of dimensions of features specified at the time of input.

  The initialization of the intraclass similarity calculation means 4 and the interclass distance calculation means 5 is called.

[Intraclass similarity calculation means 4]
The intraclass similarity matrix L ^W is calculated by the following equation (11). In the following equation (11), D ^W represents a frequency matrix of intra-class data, and S ^W represents an intra-class inner product matrix. Here, s _ij ^W below (12) represents the ij element of S ^W, d _ij ^W below (13) shows the ij element of D ^W.

[Distance calculation means 5]
The interclass similarity matrix L ^B is calculated by the following equation (14). Incidentally, D ^B below (14) shows the frequency matrix classes between data, S ^B represents the inter-class inner product matrix. Here, s _ij ^B below (15) represents the ij element of S ^B, d _ij ^B below (16) shows the ij element of D ^B.

[Management means 3]
The compressed representation H is initialized with a random number.

S3: (determination of t ≦ T)
[Management means 3]
It is determined whether t ≦ T. That is, if the processes of S4 and S5 are performed for the designated number of repetitions T, the process proceeds to S6, and otherwise, the process proceeds to S4.

S4: (Calculation of projection matrix W)
[Projection matrix calculation means 7]
The following equation (17) consisting of compression distortion J ^C (W, H), intra-class distance sum J ^W (H), and inter-class distance sum J ^B (H) is optimized for the projection matrix W. To do. That is, when the following equation (17) is differentiated, the following equation (18) is obtained, and the projection matrix W is optimized so that this equation (18) becomes zero.

The compression strain calculation means 6 is called to calculate ∂J ^C / ∂W (term for reducing the difference between the data and the extracted pattern) in the equation (18).

[Compression strain calculation means 6]
In calculating the projection matrix, the differential value of the following equation (19) of the compression distortion J ^C (W, H) is obtained, and the term ∂ J ^C / ∂ W that reduces the difference between the data and the extracted pattern is set as (20) Calculation is performed using an equation and output to the projection matrix calculation means 7.

[Projection matrix calculation means 7]
The following equation (21) is established from the equations (18) and (20). Then, the projection matrix W is obtained by solving simultaneous linear equations for the transposed matrix W ^T of the projection matrix of the following formula (21) by Householder transformation or Gaussian elimination.

  Next, each column vector of the projection matrix W is normalized by the following equation (22).

S5: (Calculation of compressed expression H)
[Compressed expression calculation means 8]
The following expression (23) consisting of compression distortion J ^C (W, H), intra-class distance sum J ^W (H), and inter-class distance sum J ^B (H) is optimized for compressed expression H. . That is, the following expression (23) is differentiated to obtain the following expression (24), and the compressed expression H is optimized so that the following expression (24) becomes zero.

The compression strain calculation means 6, the intraclass similarity calculation means 4, and the interclass distance calculation means 5 are called, and ∂J ^C / ∂H (the term for reducing the difference between the data and the extracted pattern) in the equation (24). ), ∂J ^W / .differential.H (claim to reduce the sum J ^W class within the distance, i.e., terms of increasing the degree of similarity of the class in the data), to increase the ∂J ^B / ∂H (distance interclass data )).

[Compression strain calculation means 6]
In calculating the compressed expression H, the following equation (19) of the compression distortion J ^C (W, H) is differentiated, and the term ∂J ^C / ∂H that reduces the difference between the data and the extracted pattern is expressed as (25) It is calculated by the formula and output to the compressed expression calculation means 8.

[Intraclass similarity calculation means 4]
When calculating the compressed expression H, the following expression (26) of the sum J ^W (H) of the distance within the class is differentiated, and the term ∂ J ^W / ∂H that increases the similarity of the data in the class is expressed by the following expression (27) And output to the compressed expression calculation means 8.

[Distance calculation means 5]
In calculating the compressed expression H, the following equation (28) of the sum of distances between classes J ^B (H) is differentiated, and the term ∂J ^B / ∂H that increases the data distance between classes is expressed by the following equation (29). Calculate and output to the compressed expression calculation means 8.

[Compressed expression calculation means 8]
The following equation (30) is established from the equations (24), (25), (27), and (29). Then, the simultaneous linear equation for vec (H) in the following equation (30) is solved by Householder transformation, Gaussian elimination, or the like to obtain the compressed expression H. Here, A in the equation (30) is the following equation (31), and C is the following equation (32).

  Further, vec (•) is a column vector in which matrix column vectors are vertically stacked. That is, the following expressions (33) and (34) are obtained.

  When the processing steps S4 to S5 are repeated T times, the process proceeds to S6.

S6: (Result output)
[Result output means 9] The projection matrix W last normalized, the average value μ, and the compression expression H obtained last are output to a network or a file.

[Concrete example]
Next, the pattern extraction method of this embodiment will be described based on a specific example.

S1: (Data input)
The data input means 2 inputs the data X and the label y shown in FIG. It is assumed that the dimension of the data basket m = 2 and the number of data n = 200. In addition, as other parameters (number of feature dimensions k specified at the time of input, degree α of importance in intra-class similarity, degree β of importance of distance between classes, distance scale σ, number of repetitions T), the following (35) Expressions (39) are input.

S2: (Initialization)
Management means 3, the data _{(x i, ..., x n} ) calculating an average value μ of, all the data _{(x i, ..., x n} ) subtracting the average value μ from. In this specific example, the average value μ is expressed by the following equation (40).

The management means 3 sets the size of the projection matrix W to 2 (m) × 1 (k) and the size of the compressed expression H to 1 (k) × 200 (n). Then, the initialization of the intraclass similarity calculation means 4 and the interclass distance calculation means 5 is called to calculate the intraclass similarity matrix L ^W and the interclass distance matrix L ^B. Also, the compressed expression H is initialized with a random number.

S3: (determination of t ≦ T)
The management means 3 enters the processing of the loop part (S3 to S5). When t = 1, since t (= 1) <T (= 3), the process proceeds to S4, and the management unit 3 calls the projection matrix calculation unit 7.

S4: (Calculation of projection matrix W)
The projection matrix calculation means 7 calls the compression distortion calculation means 6 to calculate the expression (20) to obtain the projection matrix W and normalize the projection matrix W. The result is the following equation (41), and this projection matrix W is as shown in FIG.

S5: (Calculation of compressed expression H)
The management means 3 calls the compressed expression calculation means 8. The compression expression calculation means 8 calls the compression distortion calculation means 6 to calculate the expression (25), calls the intraclass similarity calculation means 4 to calculate the expression (27), and the interclass distance calculation means 5 To calculate the expression (29) to obtain the compressed expression H.

  S3: When t = 2, since t (= 2) <T (= 3), the process proceeds to S4 and S5, and the management unit 3 calls the projection matrix calculation unit 7 and the compressed expression calculation unit 8.

  S4, S5: The projection matrix W and the compressed expression H are calculated in the same manner as when t = 1. As a result, the projection matrix W becomes a value shown in the following equation (42), as shown in FIG.

  S3: When t = 3, since t (= 3) ≦ T (= 3), the management unit 3 calls the projection matrix calculation unit 7 and the compressed expression calculation unit 8 and proceeds to S4 and S5.

  S4, S5: The projection matrix calculation means 7 and the compressed expression calculation means 8 calculate the projection matrix W and the compressed expression H in the same manner as when t = 1 and 2. As a result, the projection matrix W becomes a value shown in the following equation (43), as shown in FIG.

  S3: When t = 4, since t (= 4)> T (= 3), the management unit 3 ends the loop and proceeds to S6.

  S6: The result output means 9 outputs the projection matrix W normalized by t = 3, the average value μ, and the compressed expression H obtained by t = 3 to the network or file.

  FIG. 8 shows the compressed expression H obtained as a result of the above processing (S1 to S6). It can be seen that class1 and class2 can be separated on the x-axis (note that the y-axis values are shifted so that the results of class1 and class2 are easy to see).

  The new data Х can be obtained by solving the following equation (44) for h.

  As described above, in the present embodiment, the intra-class similarity calculation unit 4 and the inter-class distance calculation unit 5 perform pattern correction so that the data in the class is located near and the data between the classes is located far away. Do. By doing so, the extracted pattern can be easily separated between classes.

  Further, the compression distortion calculation means 6 functions to retain the information of the original data as much as possible by reducing the difference (compression distortion) between the given data and the extracted pattern. By doing so, it is possible to effectively extract features exceeding the number of classes.

  As a result, the dimension of the feature to be extracted can be changed by the parameter k ≦ m, and the difference between the extracted pattern and the original data Х is reduced by the compression distortion calculation means 6, so that an effective feature can be obtained. It is done.

  Further, it is not assumed that the data of each class has a Gaussian distribution, and classification can be performed even if the data of each class is multimodal.

  Furthermore, it does not depend on the average value of each class and can be separated even if the average values are equal.

  The present invention can also be configured as a program that causes a computer to function as part or all of the means 2 to 9 of the pattern extraction apparatus 1. In this case, all or some of the steps S1 to S6 are executed by the computer.

  This program can be provided through a network such as a web site or electronic mail. Further, the program is recorded on a recording medium such as a CD-ROM, DVD-ROM, CD-R, CD-RW, DVD-R, DVD-RW, MO, HDD, Blu-ray Disk (registered trademark), It can also be stored and distributed. This recording medium is read using a recording medium driving device, and the program code itself executes the processing of the above-described embodiment. Therefore, the recording medium also executes the present invention.

DESCRIPTION OF SYMBOLS 1 ... Pattern extraction apparatus 2 ... Data input means 3 ... Management means 4 ... Intraclass similarity calculation means 5 ... Inter-class distance calculation means 6 ... Compression distortion calculation means 7 ... Projection matrix calculation means 8 ... Compression expression calculation means 9 ... Result Output means

Claims (9)

A pattern extraction device for extracting a pattern for classifying from input data,
An intraclass similarity calculation means for calculating an intraclass similarity of the input data;
An interclass distance calculation means for calculating an interclass distance of the input data;
Compression distortion calculation means for calculating a compression distortion that is a difference between the input data and a pattern that is a compressed representation of the data ;
A projection matrix calculating means for obtaining a projection matrix that reduces the compression distortion from the data and a compressed representation of the data, and normalizing the projection matrix;
Compression expression calculating means for calculating a compressed expression of the data from which the compression distortion is reduced and the intraclass similarity and the interclass distance are increased from the data and the projection matrix,
A pattern extraction apparatus for extracting a pattern for classifying from input data, that is, the compressed expression that reduces compression distortion and increases the similarity in class and the distance between classes. The intraclass similarity calculation means calculates a differential value of the sum of the intraclass distances,
The interclass distance calculation means calculates a differential value of the sum of the interclass distances,
The compression strain calculating means calculates a differential value of the compression strain;
The projection matrix calculation means optimizes the expression including the compression distortion, the sum of the distances within the class, and the sum of the distances between the classes with respect to the projection matrix. Obtaining an expression to be optimized with respect to the matrix, further calculating a simultaneous linear equation of a projection matrix consisting of data and a compressed expression based on the differential value of the compression distortion, obtaining a projection matrix from the simultaneous linear equation,
The compressed expression calculation means optimizes the expression including the compression distortion, the sum of the distances within the class, and the sum of the distances between classes with respect to the compressed expression. An expression that optimizes the expression is obtained, and based on the optimized expression, a compression composed of data and a projection matrix based on the differential value of the compression distortion, the differential value of the sum of the distances within the class, and the differential value of the sum of the distances between the classes. 2. The pattern extraction apparatus according to claim 1, wherein a simultaneous linear equation of expression is calculated, and a compressed expression is obtained from the simultaneous linear equation.   Calculation of the differential value of the sum of intra-class distances in the intra-class similarity calculation means, calculation of the differential value of the sum of inter-class distances in the inter-class distance calculation means, calculation of the differential value of compressive strains in the compression strain calculation means The process of the projection matrix calculation means and the process of the compression expression calculation means are repeated a plurality of times, and the pattern for class classification is extracted based on the projection matrix normalized at the end and the compression expression obtained at the end. The pattern extraction device according to claim 2. The projection matrix calculating means and the compressed expression calculating means are:
4. The pattern extraction apparatus according to claim 2, wherein the simultaneous linear equations of the projection matrix and the simultaneous linear equations of the compressed expression are solved by Householder transformation or Gaussian elimination. A pattern extraction method for extracting a pattern for classifying from input data,
An intraclass similarity calculating means for calculating an intraclass similarity of the input data;
An interclass distance calculating means for calculating an interclass distance of the input data;
A step of calculating a compression distortion which is a difference between the input data and a pattern which is a compressed expression of the data ;
A projection matrix calculating means for obtaining a projection matrix that reduces the compression distortion from the data and a compressed representation of the data, and normalizing the projection matrix;
Yes said compressed representation calculation means, from the data and the projection matrix, wherein the compressive strain is reduced, and the compressed representation calculating step of calculating a compressed representation of the data distance between classes in similarity and class increases, the And
A pattern extraction method for extracting a pattern for performing class classification from input data, that is, the compressed expression that reduces compression distortion and increases the intraclass similarity and the interclass distance. The projection matrix calculation step includes:
The compression strain calculating means calculates a differential value of the compression strain;
The projection matrix calculation means optimizes the expression including the compression distortion, the sum of the distances within the class, and the sum of the distances between the classes with respect to the projection matrix. Obtaining an expression to be optimized with respect to the matrix, further calculating a simultaneous linear equation of a projection matrix consisting of data and a compressed expression based on the differential value of the compression distortion, obtaining a projection matrix from the simultaneous linear equation,
The compressed expression calculation step includes:
The intraclass similarity calculation means calculates a differential value of the sum of intraclass distances,
The inter-class distance calculation means calculates a differential value of the sum of the inter-class distances,
The compression strain calculating means calculates a differential value of the compression strain;
The compressed expression calculation means optimizes the expression including the compression distortion, the sum of the distances within the class, and the sum of the distances between the classes with respect to the compressed expression. An expression that optimizes the expression is obtained, and based on the optimized expression, a compression composed of data and a projection matrix based on the differential value of the compression distortion, the differential value of the sum of the distances within the class, and the differential value of the sum of the distances between the classes. 6. The pattern extraction method according to claim 5, wherein a simultaneous linear equation of expression is calculated, and a compressed expression is obtained from the simultaneous linear equation.   The projection matrix calculation step and the compressed expression calculation step are repeated a plurality of times, and a pattern for class classification is extracted based on the projection matrix normalized last and the compression expression calculated last. Item 7. The pattern extraction method according to Item 5 or 6. The projection matrix calculation step and the compressed expression calculation step are:
8. The pattern extraction method according to claim 6, wherein the simultaneous linear equations of the projection matrix and the simultaneous linear equations of the compressed expression are solved by Householder transformation or Gaussian elimination.   The program for functioning a computer as each means which comprises the pattern extraction apparatus of any one of Claims 1-4.

Images