Classification Tree Generation Constrained with Variable Weights - Foundations on Natural and Artificial Computation - page 282

5Conluon
In this paper we presented a hierarchical classification methodology that is able
to generate or test classification trees of entities whose features may have differ-
ent importance. This is achieved by adopting a distance function between the
entities where the contribution of the different features can be weighted. Despite
the potentially combinatorial number of trees, our constraint based method al-
lows discarding most of them and generate an acceptable number when the
weights are adequately constrained. We have also discussed the computational
complexity of our method and shown that it can be applied to a moderate large
number of entities. These characteristics were illustrated with examples from
biology and linguistics, but the method is quite general and can be used in any
domain, namely in situations where the classification of a set of entities depends
on the relevance of a number of features that represent them, allowing the users
to establish such relevance.
References
1. Blockeel, H., De Raedt, L., Ramon, J.: Top-Down Induction of Clustering Trees.
ICML, 55-63 (1998)
2. Cavalli-Sforza, L.L., Feldman, M.: Cultural Transmission and Evolution. Princeton
University Press, Princenton (1981)
3. Farris, J.S.: Estimating phylogenetic trees from distance matrices. Am. Nat. 106,
645-668 (1972)
4. Fitch, W., Margoliash, E.: Construction of Phylogenetic Trees. Science 155(3760),
279-284
5. Kimura, M.: Evolutionary rate at the molecular level. Nature 217(5129), 624-626
6. Makarenkov, V.: T-Rex: reconstructing and visualizing phylogenetic trees and retic-
ulation networks. Bioinformatics 17, 664-668 (2001)
7. Quinlanm, J.R.: Induction of Decision Trees. Mach. Learn. 1(1), 81-106 (1986)
8. Saitou, N., Nei, M.: The Neighbor-joining Method: A New Method for Reconstruct-
ing Phylogenetic Trees. Mol. Biol. Evol. 4(4), 406-425 (1987)
9. Seiffert, E., et al.: Convergent evolution of anthropoid-like adaptations in Eocene
adapiform primates. Science 461, 1118-1121 (2009)