JP2013020290A - Pattern extraction device, pattern extraction method and pattern extraction program - Google Patents

Abstract

A pattern extraction apparatus capable of appropriately classifying a class is provided.
A similarity calculation unit that calculates a first similarity between learning data and a second similarity between the learning data and new data, and a set of data belonging to the same class of learning data In the original space, a high degree of similarity in the original space calculates the degree of aggregation so that the distance after the conversion becomes small, and the degree of similarity is calculated in the original space for a set of data belonging to different classes. For those having a low level, an interclass separation degree calculation unit 104 that calculates a separation degree so that a distance after data conversion becomes large, and conversion to a feature space in which the data aggregation degree in the class and the data separation degree between classes become large A projection information calculation unit 105 that calculates information; a data conversion unit 107 that converts new data into a feature space using the second similarity and conversion information; and the conversion information and the conversion information It was provided with a result output unit 108 for outputting the new data.
[Selection] Figure 1

Description

  The present invention relates to supervised machine learning, and more particularly to a pattern extraction apparatus and 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.

z _i = W ^T x _i , i = 1,..., n (1)
Here, W = (w ₁ ,..., W _c-1 ), w _i ∈R ^m . Note that c represents the number of classes, m represents the number of dimensions of the features to be extracted (data dimensions), and R represents the space.

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

That is, w = argmax _w J (w).

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

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

  For example, when data of class 1 and class 2 are given as shown in FIG. 4 representing a data set in the input space, 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 shown in FIG. According to FIG. 5, it can be seen that class 1 and class 2 are well separated on the x-axis (in FIG. 5, the y-axis values are shifted so that the results of class 1 and class 2 can be easily seen).

C. M.M. Bishop, “Pattern Recognition and Machine Learning,” Springer Japan, pp. 177-190

In the linear discriminant analysis described above,
1. Only features that separate the average value of each class are obtained. 2. Only dimensional features of class number -1 can be obtained. Since each class assumed a Gaussian distribution, there was a problem that it did not fit multimodal data.

In particular, when data of class 1 and class 2 as shown in FIG. 6 are given, the average values of class 1 and class 2 become equal, so that S _B becomes a zero matrix, and the solution of equation (8) is obtained. As a result, the class separating feature cannot be obtained.

  SUMMARY OF THE INVENTION The present invention solves the above-described problems, and an object thereof is to provide a pattern extraction apparatus, method, and program that can perform class classification appropriately.

  A pattern extraction device of the present invention for solving the above-mentioned problem is a pattern extraction device for classifying input data, wherein the first similarity between learning data input during learning, the learning data, Similarity calculation means for calculating the second similarity between new data input at the time of classification, and data sets belonging to the same class that are input at the time of learning are those having high similarity in the original space Intraclass aggregation degree calculation means for calculating the degree of aggregation so that the distance after conversion becomes small, and a set of data belonging to different classes input during learning, those with low similarity in the original space are after data conversion Class separation degree calculating means for calculating the degree of separation so that the distance between the classes increases, and the data aggregation degree and the class separation degree within the class calculated by the intra-class aggregation degree calculation means Projection information calculation means for calculating conversion information into a feature space in which the degree of data separation between classes calculated by the calculation means is large, and second data calculated by the similarity calculation means for new data input at the time of classification. Using the conversion information calculated by the similarity and projection information calculation means, the data conversion means for converting into a feature space in which the degree of aggregation of data within a class and the degree of separation of data between classes are large, and the projection information calculation And a result output means for outputting the conversion information calculated by the means and the new data converted by the data conversion means.

  According to the above configuration, the intra-class aggregation degree calculation means is not a variance of each class, but evaluates an object with high similarity in the original space so that the distance after the conversion becomes small. Can handle distribution data. In addition, since the interclass separation degree calculation means of the present invention is not the average of each class, but evaluates an object having a low similarity in the original space so that the distance after conversion becomes large, the average value of each class is equal. Can also be supported.

  In addition, the projection information calculation means of the present invention calculates the feature space based on the relationship between the data obtained by the similarity calculation means, not the relationship between the average values of each class, and thus obtains a feature that exceeds the number of classes. be able to.

  Furthermore, the data conversion means of the present invention converts the data into the feature amount space using the information calculated by the projection information calculation means. In this way, new data can be converted into a feature amount space suitable for classification.

According to the present invention, the following effects can be obtained.
(1) It does not depend on the average value of each class and can be separated even if the average values are equal.
(2) The dimension of the feature to be extracted can be changed by the number of dimensions k (≦ m), and a feature effective for classification can be obtained.
(3) Since the process of Gaussian distribution is not performed, it fits to multimodal data.

1 is a block diagram of a pattern extraction device according to an example embodiment of the present invention. The flowchart at the time of the learning which shows the pattern extraction method by one Embodiment of this invention. The flowchart at the time of the classification | category which shows the pattern extraction method by one Example of this invention. It is the 1st figure explaining the conventional method, and is explanatory drawing showing the data set of 2 classes in input space. It is a 2nd figure explaining the conventional method, and is explanatory drawing of the pattern extracted. It is a figure explaining the problem of the conventional method, and explanatory drawing showing the data set of 2 classes in input space. It is a 1st figure explaining operation | movement of this invention, and is explanatory drawing showing projection information (alpha) ¹ . It is the 2nd figure explaining operation | movement of this invention, and is explanatory drawing which shows that the characteristic effective for a classification is obtained with respect to new data.

  Hereinafter, embodiments of the present invention will be described with reference to the drawings, but the present invention is not limited to the following embodiments. As shown in the block diagram of FIG. 1, the pattern extraction apparatus of the present invention includes a data input unit 101 for capturing various input data and parameters, a similarity calculation unit 102 as a similarity calculation unit, and an intra-class aggregation level calculation unit. An intra-class aggregation degree calculation unit 103, an inter-class separation degree calculation unit 104 as an inter-class separation degree calculation unit, a projection information calculation unit 105 as a projection information calculation unit, a storage unit 106 in which various data and parameters are stored, A data conversion unit 107 as data conversion means and a result output unit 108 as result output means are provided.

The pattern extraction algorithm implemented by the pattern extraction apparatus of FIG.
Algorithm 1 Learning Procedure Required: X, y, k, τ, ζ, η
1: Calculation of similarity matrix 2: Calculation of intra-class aggregation degree 3: Calculation of separation between classes 4: Calculation of projection information 5: Accumulation of X, k, τ, α ^j , b 6: Output of α ^j

Algorithm 2 Classification Request: Z
1: Calculation of similarity matrix 2: Execution of data conversion 3: Output of f (z _u )

The above “procedure for learning Algorithm 1” is shown in steps S201 to S207 in the flowchart of FIG. 2, and the “procedure for sorting Algorithm 2” is shown in steps S301 to S304 of the flowchart in FIG.

  The pattern extraction apparatus of FIG. 1 is configured by a computer, for example, and includes hardware resources of a normal computer such as a ROM, a RAM, a CPU, an input device, an output device, a communication interface, a hard disk, a recording medium, and a driving device thereof. .

  As a result of the cooperation between the hardware resource and the software resource (OS, application, etc.), the pattern extraction apparatus according to the present embodiment has a data input unit 101, a similarity calculation unit 102, an in-class as shown in FIG. An aggregation degree calculation unit 103, an interclass separation degree calculation unit 104, a projection information calculation unit 105, a storage unit 106, a data conversion unit 107, and a result output unit 108 are mounted.

  It is assumed that the storage unit 106 includes a storage unit / storage unit such as a hard disk or a RAM.

Next, the details of the apparatus configured as described above will be specifically described. In this embodiment, at the time of learning, data X = (x ₁ ,..., X _n ), x _i ∈R ^m , label y = (y ₁ ,..., Y _n ), y _i ∈ {1,. } (C is the number of classes), dimension number k of extracted features (0 <k <m), similarity calculation parameter τ> 0, intraclass aggregation parameter ζ ≧ 0, and interclass separation parameter η ≧ 0 is input, projection information α ^j , b _j , j = 1,..., K calculated by the projection information calculation unit 105 is output. At the time of classification, new data Z is input and converted by the data conversion unit 107 The new data f (z _u ) thus output is output.

  The data input unit 101 inputs learning data X, label y, parameters k, τ, ζ, and η during learning from a network or a file, and inputs new data Z during classification.

The storage unit 105 stores data X, parameters k and τ input from the data input unit 101, and projection information α ^j , b _j , j = 1,..., K calculated by the projection information calculation unit 105. The

The similarity calculation unit 102 inputs the similarity matrix Ω (first similarity) of the learning data X input at the time of learning and the similarity matrix Ω ^new (the first similarity data between the learning data X and the new data Z input at the time of classification). 2).

ω _ij = exp {−τ‖x _i −x _j ‖} (9)
Is the similarity between the learning data x _i and the learning data x _j .

ω _ij ^new = exp {−τ‖x _i −z _j ‖} (10)
Is the similarity between the learning data x _i and the new data z _j .

  Here, ‖ and ‖ are Euclidean norms.

The intra-class aggregation degree calculation unit 103 calculates the degree of aggregation so that the distance between the data sets that belong to the same class input at the time of learning is high in the original space so that the distance after data conversion becomes small And calculate an intra-class intensity matrix L ^W , that is, a term for arranging data belonging to the same class nearby.

L ^W = D ^W −S ^W (11)
here,

  Indicates the similarity between data belonging to the same class.

  Also,

  Is a term for emphasizing data that is dense within the same class (that is, is referenced with high similarity from data within the same class).

The interclass separation degree calculation unit 104 calculates the degree of separation so that the distance after data conversion becomes large for a set of data belonging to different classes input at the time of learning and having a low similarity in the original space The interclass separation matrix L ^B , that is, a term for disposing data belonging to different classes far away is calculated.

L ^B = D ^B −S ^B (14)
here,

  Indicates the degree of dissimilarity between data belonging to different classes (the value increases as the distance increases, and the value decreases as the distance decreases).

  Also,

  Is a term for emphasizing data having a large gap between classes (that is, referred to at a distance far from data of different classes).

The projection information calculation unit 105 has a feature space in which the data intensity within the class calculated by the intra-class aggregation degree calculation unit 103 and the data separation degree between classes calculated by the inter-class separation degree calculation unit 104 are increased. And conversion information into the feature space, that is, projection information α ^j , b _j , j = 1,..., K is calculated.

Here, α ^j is learning data converted into a space in which the degree of aggregation of data within a class and the degree of separation of data between classes are increased.

Further, b _j is a parameter for converting new data into a space in which the degree of aggregation of data in a class and the degree of separation of data between classes are increased.

  This can be obtained by solving the following eigenvalue problem.

LMΩα = λα (17)
α ^j is an eigenvector corresponding to the top k eigenvalues.

  here,

  Also,

The data converter 107 uses the similarity matrix Ω ^new between the learning data X and the new data Z calculated by the similarity calculator 102 and the projection information α ^j and b _j calculated by the projection information calculator 105. ,

The result output unit 108 outputs projection information α ^j , b _j , j = 1,..., K stored in the storage unit 106 during learning to a network or a file, and the data conversion unit 107 during classification. The new data f (z ₁ ),..., F (z ₁ ) converted by the above is output.

  Next, the operation of the apparatus configured as described above will be described with reference to FIG. 2 showing a flowchart for learning and FIG. 3 showing a flowchart for classification.

<During learning>
At the time of learning, the data input unit 101 inputs, for example, the learning data X and the label y shown in Table 1 (the same as in FIG. 6). Here, the data dimension m = 2 and the number of data n = 20.

Other parameters k = 1 (23)
τ = 1 (24)
ζ = 1 (25)
η = 1 (26)
Is input (step S201).

  Next, the similarity calculation unit 102 calculates the similarity matrix Ω of the learning data X according to the equation (9) (step S202).

Next, the intra-class aggregation degree calculation unit 103 calculates the intra-class aggregation degree L ^W according to the equation (11) (step S203).

Next, the inter-class separation degree calculation unit 104 calculates the inter-class separation degree L ^B according to the equation (14) (step S204).

  Next, the projection information calculation unit 105 calculates the projection information by solving the eigenvalue problem of the equation (17) (step S205). Since k = 1, the eigenvector corresponding to the maximum eigenvalue is obtained.

The maximum eigenvalue is calculated as λ ₁ = 6.664998, and the eigenvector α ¹ corresponding to the maximum eigenvalue is shown in Table 2.

Next, when b ₁ is calculated according to the equation (21), b ₁ = −7.51549 × 10 ⁻¹⁶ is obtained.

In step S <b> 206, the data X, parameters k, τ, and projection information α ¹ , b ₁ are stored in the storage unit 106.

Next, the result output unit 108 outputs the projection information α ¹ (step S207).

The projection information α ¹ is shown in FIG. The projection information α ¹ is learning data converted into a space in which the degree of aggregation of data within a class and the degree of separation of data between classes are large. According to FIG. 7, class 1 and class 2 are well separated on the x axis. (In FIG. 7, the y-axis value is shifted so that the results of class 1 and class 2 are easy to see).

<At the time of classification>
At the time of classification, the data input unit 101 inputs new data Z = (z ₁ ,..., Z _l ) (step S301). Z is a point of [-1, 4] x [-1, 4].

Next, the similarity calculation unit 102 calculates a similarity matrix Ω ^new between the learning data X and the new data Z according to the equation (10) (step S302). The learning data X and τ are acquired from the storage unit 106.

Next, the data converter 107 converts the input data z _u into f (z _u ) εR ^k according to the equation (22) (step S303). At this time, k, α, and b are acquired from the storage unit 106, and Ω ^new is acquired from the similarity calculation unit 102. In this example, k = 1.

A value f (Z) corresponding to the new data Z is shown in FIG. Since the data conversion unit 107 converts the input new data z _u into a space R ^{k in} which the degree of aggregation of the data in the class and the degree of separation of the data between the classes are increased, the data of the class 1 as shown in FIG. The value is larger than 0 (close to white) in the nearby region, and the value is smaller than 0 (close to black) in the region near class 2.

  Therefore, according to FIG. 8, it can be seen that features effective for classification are obtained even for new data.

  In addition, a part or all of the functions of each unit in the pattern extraction apparatus of the present embodiment can be configured by a computer program, and the program can be executed using the computer to realize the present invention. It goes without saying that the procedure in the pattern extraction method can be configured by a computer program and the program can be executed by the computer, and the program for realizing the function by the computer can be read by a computer-readable recording medium such as an FD. (Floppy (registered trademark) Disk), MO (Magneto-Optical disk), ROM (Read Only Memory), memory card, CD (Compact Disk) -ROM, DVD (Digital Versati) e Disk) -ROM, CD-R, CD-RW, HDD, and recorded in a removable disk, or stored, it is possible or distribute. It is also possible to provide the above program through a network such as the Internet or electronic mail.

DESCRIPTION OF SYMBOLS 101 ... Data input part 102 ... Similarity calculation part 103 ... Intraclass aggregation degree calculation part 104 ... Interclass separation degree calculation part 105 ... Projection information calculation part 106 ... Accumulation part 107 ... Data conversion part 108 ... Result output part

Claims (5)

A pattern extraction device for classifying input data,
Similarity calculating means for calculating a first similarity between learning data input during learning and a second similarity between the learning data and new data input during classification;
With respect to a set of data belonging to the same class input at the time of learning, an intra-class aggregation degree calculation means for calculating an aggregation degree so that a distance after data conversion is small in a high similarity in the original space,
For a set of data belonging to different classes input at the time of learning, an inter-class separability calculating means for calculating a separability so that the distance after data conversion is large for those with low similarity in the original space,
Projection information calculation means for calculating conversion information into a feature space in which the data intensity within the class calculated by the intra-class aggregation degree calculation means and the data separation degree between classes calculated by the class separation degree calculation means are large. When,
Using the second similarity calculated by the similarity calculation means and the conversion information calculated by the projection information calculation means, the degree of data aggregation within the class and the data between classes are used. Data conversion means for converting into a feature space in which the degree of separation of
A result output means for outputting the conversion information calculated by the projection information calculation means and the new data converted by the data conversion means;
A pattern extraction apparatus comprising: The learning data label is y, the dimension number of features to be extracted is k, the similarity calculation parameter is τ, the intra-class aggregation parameter is ζ, and the inter-class separation parameter is η,
The similarity calculation means obtains the first similarity by calculating a similarity matrix Ω of learning data X input at the time of learning, and the similarity between the learning data X and new data Z input at the time of classification By calculating the degree matrix Ω ^new , the second similarity is obtained,
The intra-class aggregation degree calculation means calculates the similarity between data belonging to the same class.
age,
A section for emphasizing dense data within the same class
And the intra-class aggregation matrix L ^W = D ^W −S ^W
The interclass separation degree calculation means calculates the dissimilarity between data belonging to different classes.
age,
A term for emphasizing data with large gaps between classes
And the interclass separation matrix L ^B = D ^B −S ^B is calculated as the separation,
The projection information calculation means has the following eigenvalue problem, that is,
LMΩα = λα (17)
The learning data α ^j converted to a feature space that increases the degree of data aggregation and the degree of data separation between classes, and the new data A parameter b _j (where j = 1,..., K) for conversion into a feature space with a high degree of separation is calculated as the conversion information;
The data conversion means includes
The pattern extraction apparatus according to claim 1, wherein the new data is converted into a feature space R ^{k in} which the degree of aggregation of data within a class and the degree of separation of data between classes are increased by calculating A pattern extraction method for classifying input data,
A first similarity calculating step in which a similarity calculating means calculates a first similarity between learning data input at the time of learning;
Intra-class aggregation level calculation means, for a set of data belonging to the same class that was input during learning, those with high similarity in the original space calculate the aggregation level so that the distance after data conversion is small An aggregation calculation step;
Inter-class separability calculation means calculates the separability of data sets that belong to different classes that were input during learning so that the distance after data conversion is greater for those with low similarity in the original space A separation degree calculating step;
Projection information calculation means includes conversion information to a feature space in which the data intensity within the class calculated by the intra-class aggregation degree calculation means and the data separation degree between classes calculated by the inter-class separation degree calculation means are increased. A projection information calculation step to calculate,
A first result output step in which the result output means outputs the conversion information calculated by the projection information calculation means;
A second similarity calculating step in which a similarity calculating means calculates a second similarity between the learning data and the new data input at the time of classification;
The data conversion means uses the second similarity calculated by the similarity calculation means and the conversion information calculated by the projection information calculation means for the new data input at the time of classification, and the degree of data aggregation in the class And a data conversion step for converting to a feature space that increases the degree of separation of data between classes,
A second result output step in which the result output means outputs the data converted by the data conversion means;
A pattern extraction method characterized by comprising: The learning data label is y, the dimension number of features to be extracted is k, the similarity calculation parameter is τ, the intra-class aggregation parameter is ζ, and the inter-class separation parameter is η,
In the first similarity calculation step, the first similarity is obtained by calculating a similarity matrix Ω of learning data X input during learning,
In the intra-class aggregation degree calculation step, similarity between data belonging to the same class is calculated.
age,
A section for emphasizing dense data within the same class
And the intra-class aggregation matrix L ^W = D ^W −S ^W
In the interclass separation degree calculation step, dissimilarity between data belonging to different classes is calculated.
age,
A term for emphasizing data with large gaps between classes
And the interclass separation matrix L ^B = D ^B −S ^B is calculated as the separation,
The projection information calculation step includes the following eigenvalue problem:
LMΩα = λα (17)
The learning data α ^j converted to a feature space that increases the degree of data aggregation and the degree of data separation between classes, and the new data A parameter b _j (where j = 1,..., K) for conversion into a feature space with a high degree of separation is calculated as the conversion information;
The first result output step outputs conversion information α ^j and b _j calculated by the projection information calculation means,
In the second similarity calculation step, the second similarity is obtained by calculating a similarity matrix Ω ^new between the learning data X and the new data Z input at the time of classification,
The data conversion step includes
To convert the new data into a feature space R ^k that increases the degree of aggregation of data within the class and the degree of data separation between classes,
The pattern extraction method according to claim 3, wherein the second result output step outputs new data converted by the data conversion unit. A pattern extraction program for causing a computer to function as each means according to claim 1.