Structural data classification
View Patent ↗Techniques for classifying structural data with skewed distribution are disclosed. By way of example, a method classifying structural input data comprises a computer system performing the following steps. Multiple classifiers are constructed, wherein each classifier is constructed on a subset of training data, using one or more selected composite features from the subset of training data. A consensus among the multiple classifiers is computed in accordance with a voting scheme such that at least a portion of the structural input data is assigned to a particular class in accordance with the computed consensus. Such techniques for structured data classification are capable of handling skewed class distribution and partial feature coverage issues.
1. A method for classifying structural input data, the method comprising a computer system performing steps of:
constructing multiple classifiers, wherein each classifier is constructed on a subset of training data, using selected composite features from the subset of training data, the composite features being selected by iteratively applying a feature selection step wherein multiple disjoint feature sets are identified to represent the structural input data in different feature spaces, and the structural input data, when characterized by a skewed prior class distribution, being subjected to a sampling step to obtain a balanced class distribution; and
computing a consensus among the multiple classifiers in accordance with a voting scheme such that at least a portion of the structural input data is assigned to a particular class in accordance with the computed consensus;
wherein the computer system comprises a memory and a processor device operatively coupled to the memory.
2. The method of claim 1 , wherein the subset of training data is selected from a full training dataset, among which positive and negative data are balanced.
3. The method of claim 1 , wherein the composite features are not the same across different classifiers.
4. The method of claim 1 , wherein the composite features are selected so as to differentiate training data.
5. The method of claim 4 , wherein the composite features are selected such that feature discrimination and class labels are considered.
6. The method of claim 4 , wherein the composite features are substructures directly mined from structural datasets.
7. The method of claim 1 , wherein the structural data comprises skewed structural data.
8. The method of claim 7 , wherein the skewed structural data comprises skewed graph data.
9. Apparatus for classifying structural input data, the apparatus comprising:
a memory; and
a processor operatively coupled to the memory and configured to: construct multiple classifiers, wherein each classifier is constructed on a subset of training data, using selected composite features from the subset of training data, the composite features being selected by iteratively applying a feature selection step wherein multiple disjoint feature sets are identified to represent the structural input data in different feature spaces, and the structural input data, when characterized by a skewed prior class distribution, being subjected to a sampling step to obtain a balanced class distribution; and compute a consensus among the multiple classifiers in accordance with a voting scheme such that at least a portion of the structural input data is assigned to a particular class in accordance with the computed consensus.
10. The apparatus of claim 9 , wherein the subset of training data is selected from a full training dataset, among which positive and negative data are balanced.
11. The apparatus of claim 9 , wherein the composite features is not the same across different classifiers.
12. The apparatus of claim 9 , wherein the composite features are selected so as to differentiate training data.
13. The apparatus of claim 12 , wherein the composite features are selected such that feature discrimination and class labels are considered.
14. The apparatus of claim 12 , wherein the composite features are substructures directly mined from structural datasets.
15. The apparatus of claim 9 , wherein the structural data comprises skewed structural data.
16. The apparatus of claim 15 , wherein the skewed structural data comprises skewed graph data.
17. An article of manufacture for classifying structural input data, the article comprising a computer readable storage medium having one or more programs embodied therewith wherein the one or more programs, when executed by a computer, perform steps of:
constructing multiple classifiers, wherein each classifier is constructed on a subset of training data, using selected composite features from the subset of training data, the composite features being selected by iteratively applying a feature selection step wherein multiple disjoint feature sets are identified to represent the structural input data in different feature spaces, and the structural input data, when characterized by a skewed prior class distribution, being subjected to a sampling step to obtain a balanced class distribution; and
computing a consensus among the multiple classifiers in accordance with a voting scheme such that at least a portion of the structural input data is assigned to a particular class in accordance with the computed consensus.