Discrimination apparatus and method using a decision tree
View Patent ↗An apparatus for discrimination includes a memory, an alignment unit configured to align nodes of a decision tree in the memory, wherein a node in which depth from a root node is not greater than a threshold is aligned in accordance with a breadth of first order, and a node in which depth from a root node is greater than a threshold is aligned in accordance with a depth of first order, and a discrimination unit, receiving an inputted data, configured to discriminate a class of the inputted data using the nodes aligned in the memory.
1. A discrimination apparatus comprising:
a memory;
an alignment unit configured to align nodes of a decision tree in the memory, wherein a node in which depth from a root node is not greater than a threshold is aligned in accordance with a breadth of first order, and a node in which depth from a root node is greater than a threshold is aligned in accordance with a depth of first order; and
a discrimination unit, receiving an inputted data, configured to discriminate a class of the inputted data using the nodes aligned in the memory;
wherein the memory comprises a cache memory configured to hold at least part of the decision tree; and
wherein the alignment unit decides the threshold based on an available memory of the cache memory, and decides the threshold so that a total data size of the nodes is less than the available memory of the cache memory.
2. The apparatus according to claim 1 , wherein the alignment unit aligns the nodes in the memory before the discrimination unit discriminates the class of the inputted data.
3. The apparatus according to claim 1 , further comprising an estimation unit configured to estimate a probability to move from a parent node to child node respectively, wherein the alignment unit aligns child nodes whose parent node is the same in a decreasing order of the probability.
4. The apparatus according to claim 3 , wherein the estimation unit calculates the probability based on a number of formerly discriminated data reaching each node.
5. The apparatus according to claim 3 , wherein the estimation unit calculates the probability based on a number of a learning sample of formerly discriminated data reaching each node.
6. A discrimination method comprising:
receiving an inputted data;
aligning, by an alignment unit, nodes of a decision tree in a memory, wherein a node in which depth from a root node is not greater than a threshold is aligned in accordance with a breadth of first order, and a node in which depth from a root node is greater than a threshold is aligned in accordance with a depth of first order; and
discriminating a class of the inputted data using the nodes aligned in the memory;
wherein the memory comprises a cache memory configured to hold at least part of the decision tree, the method further comprising:
deciding in the alignment unit, the threshold based on an available memory of the cache memory, and deciding the threshold so that a total data size of the nodes is less than the available memory of the cache memory.
7. The method according to claim 6 , wherein the aligning, in the alignment unit, aligns the nodes in the memory before the discriminate unit discriminates the class of the inputted data.
8. The method according to claim 6 , further comprising estimating a probability to move from a parent node to child node respectively, wherein the aligning, in the alignment unit, aligns child nodes whose parent node is the same in a decreasing order of the probability.
9. The method according to claim 8 , wherein the estimating calculates the probability based on a number of formerly discriminated data reaching each node.
10. The method according to claim 8 , wherein the estimating calculates the probability based on a number of a learning sample of formerly discriminated data reaching each node.
11. A discrimination apparatus comprising:
a memory;
means for aligning nodes of a decision tree in the memory, wherein a node in which depth from a root node is not greater than a threshold is aligned in accordance with a breadth of first order, and a node in which depth from a root node is greater than a threshold is aligned in accordance with a depth of first order; and
means for receiving an inputted data, and for discriminating a class of the inputted data using the nodes aligned in the memory;
wherein the memory comprises a cache memory configured to hold at least part of the decision tree;
and the means for aligning decides the threshold based on an available memory of the cache memory, and decides the threshold so that a total data size of the nodes is less than the available memory of the cache memory.
12. The apparatus according to claim 11 , wherein the means for aligning aligns the nodes in the memory before the discriminate unit discriminates the class of the inputted data.
13. The apparatus according to claim 11 , further comprising means for estimating a probability to move from a parent node to child node respectively, wherein the means for aligning aligns child nodes whose parent node is the same in a decreasing order of the probability.
14. The apparatus according to claim 13 , wherein the means for estimating calculates the probability based on a number of formerly discriminated data reaching each node.
15. The apparatus according to claim 13 , wherein the means for estimating calculates the probability based on a number of a learning sample of formerly discriminated data reaching each node.