Hierarchical classifier for data classification
View Patent ↗Described herein is a framework for constructing a hierarchical classifier for facilitating classification of digitized data. In one implementation, a divergence measure of a node of the hierarchical classifier is determined. Data at the node is divided into at least two child nodes based on a splitting criterion to form at least a portion of the hierarchical classifier. The splitting criterion is selected based on the divergence measure. If the divergence measure is less than a predetermined threshold value, the splitting criterion comprises a divergence-based splitting criterion which maximizes subsequent divergence after a split. Otherwise, the splitting criterion comprises an information-based splitting criterion which seeks to minimize subsequent misclassification error after the split.
1. A method of generating a hierarchical classifier on a computer system for classifying digitized data, comprising:
determining a divergence measure of a node of the hierarchical classifier, wherein the node represents a set of digitized data;
determining a splitting criterion based on the divergence measure, wherein
if the divergence measure is below a threshold value, the splitting criterion comprises a divergence-based splitting criterion which maximizes subsequent divergence after a split, and
if the divergence measure is about or above the threshold value, the splitting criterion comprises an information-based splitting criterion which minimizes subsequent misclassification error after the split; and
dividing, based on the splitting criterion, the data at the node into at least two child nodes to form at least a portion of the hierarchical classifier.
2. The method of claim 1 wherein the dividing the data comprises dividing the data at the node into two child nodes to form at least a portion of a binary decision tree.
3. The method of claim 1 wherein the dividing the data comprises dividing the data at the node into more than two child nodes to form at least a portion of a non-binary decision tree.
4. The method of claim 1 further comprises recursively repeating the steps of determining the divergence and dividing the data until a stopping criterion is satisfied.
5. The method of claim 4 wherein the stopping criterion comprises reaching a desired maximum depth.
6. The method of claim 1 wherein the hierarchical classifier comprises one or more random forests.
7. The method of claim 1 wherein the set of digitized data comprises image data samples.
8. The method of claim 7 wherein the image data samples comprise boundary image samples and non-boundary image samples.
9. The method of claim 7 wherein the image data samples comprise medical image samples.
10. The method of claim 1 wherein determining the divergence measure comprises determining a Kullback-Leibler type divergence.
11. The method of claim 10 wherein determining the divergence measure comprises determining a weighted Kullback-Leibler divergence.
12. The method of claim 10 wherein determining the divergence measure comprises determining a Jensen-Shannon divergence.
13. The method of claim 1 wherein the divergence-based splitting criterion is based on a Kullback-Leibler type divergence.
14. The method of claim 13 wherein the divergence-based splitting criterion is based on a weighted Kullback-Leibler divergence.
15. The method of claim 13 wherein the divergence-based splitting criterion is based on a Jensen-Shannon divergence.
16. The method of claim 1 wherein the information-based splitting criterion is based on an entropy measure.
17. The method of claim 1 wherein the information-based splitting criterion is based on a Gini index.
18. The method of claim 1 wherein the information-based splitting criterion is based on a likelihood ratio.
19. A non-transitory computer readable medium embodying a program of instructions executable by a machine to perform steps for generating a hierarchical classifier for classifying digitized data, the steps comprising:
determining a divergence measure of a node of the hierarchical classifier, wherein the node represents a set of digitized data;
determining a splitting criterion based on the divergence measure, wherein
if the divergence measure is below a threshold value, the splitting criterion comprises a divergence-based splitting criterion which maximizes subsequent divergence, and
if the divergence measure is about or above the threshold value, the splitting criterion comprises an information-based splitting criterion which minimizes subsequent misclassification error; and
dividing, based on the splitting criterion, the data at the node into at least two child nodes to form at least a portion of the hierarchical classifier.
20. A system for generating a hierarchical classifier for classifying digitized data, comprising:
a memory device for storing computer readable program code; and
a processor in communication with the memory device, the processor being operative with the computer readable program code to:
determine a divergence measure of a node of the hierarchical classifier, wherein the node represents a set of digitized data;
determine a splitting criterion based on the divergence measure, wherein
if the divergence measure is below a threshold value, the splitting criterion comprises a divergence-based splitting criterion which maximizes subsequent divergence, and
if the divergence measure is about or above the threshold value, the splitting criterion comprises an information-based splitting criterion which minimizes subsequent misclassification error; and
divide, based on the splitting criterion, the data at the node into at least two child nodes to form at least a portion of the hierarchical classifier.