Classification method of labeled ordered trees using support vector machines

• US 7,130,833 B2
• Filed: 03/10/2003
• Issued: 10/31/2006
• Est. Priority Date: 03/08/2002
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Koyanagi, Teruo, Kashima, Hisashi
• Primary Examiner(s): Knight, Anthony
• Assistant Examiner(s): Datskovskiy, Sergey
• Application Number:
  US10/385,268
• Publication Number:
  US 20030172352A1
• Time in Patent Office: 1,331 Days
• Field of Search: 706/12
• US Class Current: 706/12
• CPC Class Codes: G06F 18/24323 Tree-organised classifiers

Abstract

To achieve classification of semistructured data with a Kernel method for labeled ordered trees, instances having a labeled ordered tree structure are input and their inner product is computed, the result of which is used for classification learning of the instances. In the inner product computation, a sum of matches is computed for descendant nodes of non-leaf nodes of the labeled ordered trees by applying dynamic programming based on correspondence in which order of the nodes is maintained.

Claims

1. A data processing method for controlling a computer to classify XML semi-structured data instances in a database, said XML semi-structured data instances each having a vector representable structure having vector representable substructures as attributes, the method comprising:

a first step of inputting the vector representable structure instances including their substructure instances; and

a second step of successively computing an inner product of successive vector representable structure instances including their substructure instances and storing the successively computed inner products, the method further comprising the steps of;

based on structures of positive instances and structures of negative instances stored in memory, obtaining a classification rule for classifying the positive instances and the negative instances and storing the classification rule in memory, each structure of the positive instances being a labeled ordered tree in which a node indication mark is added to a node to be indicated, and each structure of the negative instances being a labeled ordered tree in which a node indication mark is added to a node not to be indicated;

adding a node indication mark to a node in the labeled ordered tree to be processed and classifying the labeled ordered tree as positive or negative based on the classification rule stored in the memory; and

in response to the classification result, outputting a processing result of the labeled ordered tree with the node indication mark added to a node, to thereby create a classification rule;

wherein the first step further comprises, if the given substructures includes lower substructures, computing a sum of matches for the substructures.

2. The data processing method according to claim 1, wherein the first step comprises, if the given substructures includes lower substructures, computing a sum of complete matches for the lower substructure by applying dynamic programming based on information specific to the lower substructure.

3. The data processing method according to claim 1, wherein the first step comprises, if the given substructures includes lower substructures, computing a sum of matches for the lower substructure according to correspondence in which order in the lower substructures is maintained.

4. The data processing method according to claim 1, wherein the second step comprises inputting instances having a labeled ordered tree structure.

5. The data processing method according to claim 1 wherein the step of obtaining the classification rule and storing it in the memory comprises the steps of:

inputting the labeled ordered trees to compute their inner product and storing the computation result in memory; and

obtaining the classification rule for the labeled ordered trees with the computation result stored in the memory.

6. The method of claim 1 further comprising controlling a computer to compute an inner product of labeled ordered trees, the method comprising:

a first step of matching leaf nodes of the labeled ordered trees and storing the result in memory;

a second step of matching nonleaf nodes of the labeled ordered trees by computing a sum of matches for descendant nodes of the nonleaf nodes and storing the result in memory; and

a third step of computing the inner product of the labeled ordered trees based on the matching results of the first and second steps stored in the memory.

7. The data processing method according to claim 6, wherein the second step comprises computing a sum of matches for the descendant nodes by applying dynamic programming according to correspondence in which order of the descendant nodes is maintained.

8. A program product encoded on a computer readable meddium and comprising code for controlling a computer to execute classifying XML semi-structured data instances in a database, said XML semi-structured data instances each having a vector representable structure having vector representable substructures as attributes, the method comprising:

a first step of inputting the vector representable structure instances including their substructure instances; and

a second step of successively computing an inner product of successive vector representable structure instances including their substructure instances and storing the successively computed inner products, the method further comprising the steps of;

based on structures of positive instances and structures of negative instances stored in memory, obtaining a classification rule for classifying the positive instances and the negative instances and storing the classification rule in memory, each structure of the positive instances being a labeled ordered tree in which a node indication mark is added to a node to be indicated, and each structure of the negative instances being a labeled ordered tree in which a node indication mark is added to a node not to be indicated;

adding a node indication mark to a node in the labeled ordered tree to be processed and classifying the labeled ordered tree as positive or negative based on the classification rule stored in the memory; and

in response to the classification result, outputting a processing result of the labeled ordered tree with the node indication mark added to a node, to thereby create a classification rule;

wherein the first step further comprises, if the given substructures includes lower substructures, computing a sum of matches for the substructures.

9. The program product according to claim 8, wherein the first step executed by the computer comprises, when computing the sum of matches for the descendant nodes of the node, determining that the descendant nodes match even if their labels are different from corresponding nodes.

10. The program product according to claim 8, wherein the first step executed by the computer comprises determining that the descendant nodes match if relative positions between corresponding nodes are maintained.

11. A computer readable recording medium in which a program for controlling a computer to classify XML semi-structured data instances in a database, said XML semi-structured data instances each having a vector representable structure having vector representable substructures as attributes, the method comprising:

a first step of inputting the vector representable structure instances including their substructure instances; and

a second step of successively computing an inner product of successive vector representable structure instances including their substructure instances and storing the successively computed inner products, the method further comprising the steps of;

based on structures of positive instances and structures of negative instances stored in memory, obtaining a classification rule for classifying the positive instances and the negative instances and storing the classification rule in memory, each structure of the positive instances being a labeled ordered tree in which a node indication mark is added to a node to be indicated, and each structure of the negative instances being a labeled ordered tree in which a node indication mark is added to a node not to be indicated;

adding a node indication mark to a node in the labeled ordered tree to be processed and classifying the labeled ordered tree as positive or negative based on the classification rule stored in the memory; and

in response to the classification result, outputting a processing result of the labeled ordered tree with the node indication mark added to a node, to thereby create a classification rule;

wherein the first step further comprises, if the given substructures includes lower substructures, computing a sum of matches for the substructures.