Abstract
Most classification algorithms receive as input a set of attributes of the classified objects. In many cases, however, the supplied set of attributes is not sufficient for creating an accurate, succinct and comprehensible representation of the target concept. To overcome this problem, researchers have proposed algorithms for automatic construction of features. The majority of these algorithms use a limited predefined set of operators for building new features. In this paper we propose a generalized and flexible framework that is capable of generating features from any given set of constructor functions. These can be domain-independent functions such as arithmetic and logic operators, or domain-dependent operators that rely on partial knowledge on the part of the user. The paper describes an algorithm which receives as input a set of classified objects, a set of attributes, and a specification for a set of constructor functions that contains their domains, ranges and properties. The algorithm produces as output a set of generated features that can be used by standard concept learners to create improved classifiers. The algorithm maintains a set of its best generated features and improves this set iteratively. During each iteration, the algorithm performs a beam search over its defined feature space and constructs new features by applying constructor functions to the members of its current feature set. The search is guided by general heuristic measures that are not confined to a specific feature representation. The algorithm was applied to a variety of classification problems and was able to generate features that were strongly related to the underlying target concepts. These features also significantly improved the accuracy achieved by standard concept learners, for a variety of classification problems.
Article PDF
Similar content being viewed by others
References
Aha, D. W. (1991). Incremental constructive induction: An instance-based approach. In Proc. 8th International Conference on Machine Learning (pp. 117-121). San Mateo, CA: Morgan Kaufmann.
Aha, D. W., Kibler, D., & Albert, M. K. (1991). Instance-based learning algorithms. Machine Learning, 6, 37-66.
Bala, J. W., Michalski, R., & Wenk, J. (1992). The principal axes method for constructive induction. In Proc. 9th International Conference on Machine Learning (pp. 20-29). San Mateo, CA: Morgan Kaufmann.
Boddy, M. (1991). Anytime problem solving using dynamic programming. In Proceedings of the Ninth National Conference on Artificial Intelligence (Vol. II, pp. 738-743). Menlo Park: AAAI Press/MIT Press.
Boddy, M., & Dean, T. (1994). Decision-theoretic deliberation scheduling for problem solving in time-constrained environments. Artificial Intelligence, 67:2, 245-286.
Breiman, L., Friedman, J., Olshen, R., & Stone, C. (1984). Classification and Regression Trees. Belmont: CA Wadsworth International Group.
Caruana, R., & Freitag, D. (1994). Greedy attribute selection. In Proc. 11th International Conference on Machine Learning (pp. 28-36). San Mateo, CA: Morgan Kaufmann.
Clark, P., & Niblett, T. (1989). The cn2 induction algorithm Machine Learning, 3, 261-283.
De Jong, K. A., Spears, W. M., & Gordon, D. F. (1992). Using genetic algorithms for concept learning. Machine Learning, 8, 5-32.
Fayyad, U., & Irani, K. (1993). Multi-interval discretization of continuous-valued attributes for classifition learning. In Proc. 13th International Conference on Artificial Intelligence (pp. 1022-1027).
Heath, D., Kasif, S., & Salzberg, S. (1993). Learning oblique decision trees. In Proc. 13th International Conference on Artificial Intelligence (pp. 1003-1007).
Hirsh, H., & Japkowicz, N. (1994). Bootstrapping training-data representations for inductive learning: A case study in molecular biology. In Proc. 11th International Conference on Machine Learning (pp. 639-644). San Mateo, CA: Morgan Kaufmann.
Hu, Y.-J., & Kibler, D. (1996). Generation of attributes for learning algorithms. In Proc. 13th International Conference on Machine Learning. San Mateo, CA: Morgan Kaufmann.
Ittner, A., & Schlosser, M. (1996). Discovery of relevant new features by generating non-linear decision trees. In Proc. 2nd International Conference on Knowledge Discovery and Data Mining (KDD'96).
John, G. H., Kohavi, R., & Pfleger, K. (1994). Irrelevant features and subset selection problem. In Proc. 11th International Conference on Machine Learning (pp. 121-129). San Mateo, CA: Morgan Kaufmann.
Kira, K., & Rendell, L. A. (1992). A practical approach to feature selection. In Proc. 9th International Conference on Machine Learning (pp. 249-256). San Mateo, CA: Morgan Kaufmann.
Kohavi, R., & Dan, S. (1995). Feature subset selection using the wrapper model: Overfitting and dynamic search space topology. In U. M. Fayyad and R. Uthurusamy (Eds.), First International Conference on Knowledge Discovery and Data Mining (KDD-95).
Koza, J. (1992). Genetic programming: On the programming of computers by means of natural selection. Master's thesis. Cambirdge, MA: MIT Press.
Koza, J. R., Bennett, F. H., Andre, D., & Kean, M. A. (1996). Four problems for which a computer program evolved by genetic programming is competitive with human performance. In Proceedings of the 1996 IEEE International Conference on Evolutionary Computation (pp. 1-10). Piscataway, NJ: IEEE Press.
Matheus, C. J., & Rendell, L. A. (1989). Constructive induction on decision trees. In Proc. 11th International Conference on Artificial Intelligence (pp. 645-650).
Murphy, P. M., & Pazzani, M. J. (1991). Id2-of-3: Constructive induction of m-of-n concepts for discriminators in decision trees. In Proc. 8th International Conference on Machine Learning (pp. 183-188). San Mateo, CA: Morgan Kaufmann.
Pagallo, G., & Haussler, D. (1990). Boolean feature discovery in empirical learning. In Proc. 7th International Conference on Machine Learning (pp. 71-99). San Mateo, CA: Morgan Kaufmann.
Perez, E., & Rendell, L. A. (1995). Using multidimensional projection to find relations. In Proc. 14th International Conference on Artificial Intelligence (pp. 447-455).
Quinlan, J. R. (1993). C4.5: Programs for Machine Learning. San Mateo, CA: Morgan Kaufmann. Ragavan, H., & Rendell, L. A. (1993). Improving the design of induction methods by analyzing algorithm functionality and data-based concept complexity. In Proc. 13th International Conference on Artificial Intelligence (pp. 952-958).
Ragavan, H., Rendell, L. A., Shaw, M., & Tessmer, A. (1993). Complex concept acquisition through directed search and feature caching. In Proc. 13th International Conference on Artificial Intelligence (pp. 946-951).
Salzberg, S. (1993). Improving classification methods via feature selection. Machine Learning, 99.
Sangiovanni-Vincentelli, A. L. O. A. (1992). Constructive induction using a non-greedy strategy for feature selection. In Proc. 9th International Conference on Machine Learning (pp. 355-360). San Mateo, CA: Morgan Kaufmann.
Schlimner, J. (1987). Concept acquisition through representational adjustment. Ph.D. Thesis, Department of Information and Computer Science, University of California, Irvine, CA.
Sutton, R. S., & Matheus, C. J. (1991). Learning polynomial functions by feature construction. In Proc. 8th International Conference on Machine Learning (pp. 208-212). San Mateo, CA: Morgan Kaufmann.
Todorovski, L., & Dzeroski, S. (1997). Declarative bias in equation discovery. In Proc. 14th International Conference on Machine Learning. San Mateo, CA: Morgan Kaufmann.
Utgoff, P. E., & Brodley, C. E. (1991). Linear machine decision trees. Tech. rep., COINS Technical Report 91-10.
Watanabe, L., & Rendell, L. A. (1991). Feature construction in structural decision trees. In Proc. 8th International Conference on Machine Learning (pp. 218-222). San Mateo, CA: Morgan Kaufmann.
Wenk, J., & Michalski, R. S. (1994). Hypothesis-driven constructive induction in aq17-hci: A method and experiments. Machine Learning, 14, 139-168.
Yang, D.-S., Rendell, L. A., & Blix, G. (1991). Fringe-like feature construction:Acomparative study and a unifying scheme. In Proc. 8th International Conference on Machine Learning (pp. 223-227). San Mateo, CA: Morgan Kaufmann.
Zheng, Z. (1996). Constructing nominal x-of-n attributes. In Proc. 13th International Conference on Machine Learning (pp. 1064-1070). San Mateo, CA: Morgan Kaufmann.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Markovitch, S., Rosenstein, D. Feature Generation Using General Constructor Functions. Machine Learning 49, 59–98 (2002). https://doi.org/10.1023/A:1014046307775
Issue Date:
DOI: https://doi.org/10.1023/A:1014046307775