Data classification method and data classification device

• US 8,589,397 B2
• Filed: 04/21/2008
• Issued: 11/19/2013
• Est. Priority Date: 09/28/2007
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Fujimaki, Ryohei
• Primary Examiner(s): Spieler, William
• Application Number:
  US12/733,895
• Publication Number:
  US 20100250542A1
• Time in Patent Office: 2,038 Days
• Field of Search: 707/737
• US Class Current: 707/737
• CPC Class Codes: G06F 18/2411 based on the proximity to a decision surface, e.g. support vector machines
• CPC Class Codes: G06F 18/2433 Single-class perspective, e.g. one-against-all classification; Novelty detection; Outlier detection
• CPC Class Codes: G06F 18/2451 linear, e.g. hyperplane
• CPC Class Codes: G06F 18/2453 non-linear, e.g. polynomial classifier
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 20/10 using kernel methods, e.g. support vector machines [SVM]

Abstract

A separation surface set storage part stores information defining a plurality of separation surfaces which separate a feature space into at least one known class region respectively corresponding to at least one known class and an unknown class region. Each of the at least one known class region is separated from outside region by more than one of the plurality of separation surfaces which do not intersect to each other. A data classification apparatus determine a classification of a classification target data whose inner product in the feature space is calculable by calculating to which region of the at least one known class region and the unknown class region determined by the information stored in the separation surface set storage part the classification target data belongs. A method and apparatus for data classification which can simultaneously perform identification and outlying value classification with high reliability in a same procedure are provided.

Claims

1. A data classification apparatus including a computer, the data classification apparatus comprising:

a separation surfaces set storage unit configured to store information defining a plurality of separation surfaces which separate a feature space into at least one known class region respectively corresponding to at least one known class and an unknown class region, wherein each of the at least one known class region is separated from outside region by more than one of the plurality of separation surfaces which do not intersect to each other;

a classification unit configured to determine a classification of a classification target data whose inner product in the feature space is calculable by calculating to which region of the at least one known class region and the unknown class region determined by the information stored in the separation surface set storage unit the classification target data belongs; and

a separation surface set calculation unit configured to calculate the plurality of separation surfaces based on;

a plurality of training data respectively classified into any of the at least one known class and whose inner product in the feature space is calculable; and

a classification of each of the plurality of training data, to store the information which defines the plurality of separation surfaces in the separation surface set storage unit,

wherein the separation surface set calculation unit is configured to calculate the plurality of separation surfaces by setting minimization of a classification error of the plurality of training data, minimization of a complexity of the plurality of separation surfaces, and minimization of an area of each of the at least one known class region as optimization target, and

wherein the optimization target is targeted to solve either one of the following optimization problems;

2. The data classification apparatus according to claim 1, wherein the separation surface set calculation unit further sets maximization of a size of the unknown class region around an origin as the optimization target.

3. The data classification apparatus according to claim 1, wherein the separation surface set calculation unit further sets minimization of overlapping area where the at least one known class are overlapped to each other as the optimization target.

4. The data classification apparatus according to claim 1, wherein each of the plurality of separation surface comprises an open hyperplane in the feature space.

5. The data classification apparatus according to claim 1,

wherein the known classification is centered around the centerpoint of a bounding hypersphere.

6. The data classification apparatus according to claim 1, wherein the

feature space comprises a vector space of a dimension same to the training data and the classification target data.

7. The data classification apparatus according to claim 1, wherein the feature space comprises a space characterized by a non-linear conversion to the training data and the classification target data.

8. The data classification apparatus according to claim 1, wherein the separation surfaces set storage unit, the classification unit, and the data classification part with an outlying value classification function are hardware units.

9. The data classification apparatus according to claim 1, wherein the data classification part with an outlying value classification function calculates a positional relationship between the classification target data and the plurality of separation surfaces by using input classification target data and information of the plurality of separation surfaces by determining a positional relationship with respect to an outer side and inner side from hyperspheres of the plurality of separation surfaces, and

wherein the data classification part with an outlying value classification function reads classification rules stored in the separation surfaces set storage unit and determines which class the classification target data belongs to for output.

10. The data classification apparatus according to claim 1, wherein identification and outlying value classification is performed simultaneously by the data classification part with the outlying value classification function of the classification unit.

11. A data classification method comprising:

inputting classification target data whose inner product in a feature space is calculable;

inputting a plurality of separation surfaces which separate the feature space into at least one known class region respectively corresponding to at least one known class and an unknown class region from a separation surface set storage part, wherein each of the at least one known class region is separated from outside region by more than one of the plurality of separation surfaces which do not intersect to each other;

classifying the classification target data by calculating to which region of the at least one known class region and the unknown class region the classification target data belongs;

calculating the plurality of separation surfaces based on;

a plurality of training data respectively classified into any of the at least one known class and whose inner product in the feature space is calculable; and

a classification of each of the plurality of training data, to store the information which defines the plurality of separation surfaces in the separation surface set storage part,

wherein in the calculating, the plurality of separation surfaces are calculated by setting minimization of a classification error of the plurality of training data, minimization of a complexity of the plurality of separation surfaces, and minimization of an area of each of the at least one known class region as optimization target, and

wherein the optimization target is targeted to solve either one of the following optimization problems;

12. The data classification method according to claim 11, wherein in the calculating the plurality of separation surfaces, maximization of a size of the unknown class region around an origin is further set as the optimization target.

13. The data classification method according to claim 11, wherein in the calculating the plurality of separation surfaces, minimization of overlapping area where the at least one known class are overlapped to each other is further set as the optimization target.

14. The data classification method according to claim 11, wherein identification and outlying value classification is performed simultaneously,

wherein the positional relationship between the plurality of separation surfaces and the classification target data is calculated, then the separation surfaces separate the feature space into one or more class regions corresponding to one or more known classes and the other unknown class region, and then, by calculating which region of one or more class regions and the other unknown class region the classification target data belongs to, the classification target data is classified for output.

15. A separation surface set calculation apparatus including a computer, the separation surface set calculation apparatus comprising:

a training data storage device configured to store a plurality of training data whose inner product in a feature space is calculable and respectively classified into any of at least one known class;

a separation surface set calculation device configured to calculate a plurality of separation surfaces which separate the feature space into at least one known class region respectively corresponding to the at least one known class and an unknown class region, based on;

the plurality of training data stored in the training data storage device, and a classification of each of the plurality of training data,

wherein each of the at least one known class region is separated from outside region by more than one of the plurality of separation surfaces which do not intersect to each other; and

a separation surface set storage device configured to store information defining the plurality of separation surfaces,

wherein the separation surface set calculation device is configured to calculate the plurality of separation surfaces by setting minimization of a classification error of the plurality of training data, minimization of a complexity of the plurality of separation surfaces, and minimization of an area of each of the at least one known class region as optimization target, and

wherein the optimization target is targeted to solve either one of the following optimization problems;

16. The separation surface set calculation apparatus according to claim 15, wherein the separation surface set calculation device further sets maximization of a size of the unknown class region around an origin as the optimization target.

17. The separation surface set calculation apparatus according to claim 15, wherein the separation surface set calculation device further sets minimization of overlapping area where the at least one known class are overlapped to each other as the optimization target.