{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/23122"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/23122","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Feature construction: An analytic framework and an application to decision trees","abstract":"While similarity-based learning (SBL) methods can be effective for acquiring concept descriptions from labeled examples, their success largely depends upon the quality of the features used to describe the examples. When a learning problem uses low-level features, the complexity of the concept-membership function can make SBL inaccurate, expensive, or simply impossible. One way to overcome this limitation is through feature construction: the construction of new features by the application of constructive operators to existing features. Feature construction can result in an improved instance space in which the concept-membership function is better behaved relative to the inductive biases of SBL algorithms. Feature construction, however, is computationally difficult, primarily because of the intractably large space of potential new features. To assist in the study and advancement of feature construction methods, this thesis presents a feature construction framework based on the aspects of (1) need detection, (2) constructor selection, (3) constructor generalization, and (4) feature evaluation. This framework was used to analyze eight existing systems (BACON, BOGART, DUCE, FRINGE, MIRO, PLSO, STAGGER, and STABB) and to identify promising approaches to feature construction. The framework also served as the basis for the design of CITRE, an inductive system that constructs new features using decision tress. CITRE was tested on five learning problems: l-term kDNF Boolean functions, tic-tac-toe classification, mushroom classification, voting-record classification, and chess-end-game classification. The results demonstrate CITRE's potential for significantly improving hypothesis accuracy and conciseness. The results also reveal substantial benefits obtainable by using simple domain-knowledge constraints and constructor generalization during feature construction.","abstract_html":"While similarity-based learning (SBL) methods can be effective for acquiring concept descriptions from labeled examples, their success largely depends upon the quality of the features used to describe the examples. When a learning problem uses low-level features, the complexity of the concept-membership function can make SBL inaccurate, expensive, or simply impossible. One way to overcome this limitation is through feature construction: the construction of new features by the application of constructive operators to existing features. Feature construction can result in an improved instance space in which the concept-membership function is better behaved relative to the inductive biases of SBL algorithms. Feature construction, however, is computationally difficult, primarily because of the intractably large space of potential new features. To assist in the study and advancement of feature construction methods, this thesis presents a feature construction framework based on the aspects of (1) need detection, (2) constructor selection, (3) constructor generalization, and (4) feature evaluation. This framework was used to analyze eight existing systems (BACON, BOGART, DUCE, FRINGE, MIRO, PLSO, STAGGER, and STABB) and to identify promising approaches to feature construction. The framework also served as the basis for the design of CITRE, an inductive system that constructs new features using decision tress. CITRE was tested on five learning problems: l-term kDNF Boolean functions, tic-tac-toe classification, mushroom classification, voting-record classification, and chess-end-game classification. The results demonstrate CITRE's potential for significantly improving hypothesis accuracy and conciseness. The results also reveal substantial benefits obtainable by using simple domain-knowledge constraints and constructor generalization during feature construction.","abstract_has_math":false,"creators":["Matheus, Christopher John"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Rendell, Larry A."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-05-07T14:02:58Z","date_published":"2011-05-07T14:02:58Z","updated_at":"2026-07-22T22:25:21Z","subjects":["Artificial Intelligence","Computer Science"],"languages":["eng"],"rights":["Copyright 1990 Matheus, Christopher John"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9021727","(UMI)AAI9021727"],"render_values":[{"text":"AAI9021727","href":null,"code":true},{"text":"(UMI)AAI9021727","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/23122","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Rendell, Larry A."]},{"key":"dc:creator","label":"Author","values":["Matheus, Christopher John"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-05-07T14:02:58Z","10000-01-01","1990"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Artificial Intelligence","Computer Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 1990 Matheus, Christopher John"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9021727","(UMI)AAI9021727","http://hdl.handle.net/2142/23122"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["While similarity-based learning (SBL) methods can be effective for acquiring concept descriptions from labeled examples, their success largely depends upon the quality of the features used to describe the examples. When a learning problem uses low-level features, the complexity of the concept-membership function can make SBL inaccurate, expensive, or simply impossible. One way to overcome this limitation is through feature construction: the construction of new features by the application of constructive operators to existing features. Feature construction can result in an improved instance space in which the concept-membership function is better behaved relative to the inductive biases of SBL algorithms. Feature construction, however, is computationally difficult, primarily because of the intractably large space of potential new features. To assist in the study and advancement of feature construction methods, this thesis presents a feature construction framework based on the aspects of (1) need detection, (2) constructor selection, (3) constructor generalization, and (4) feature evaluation. This framework was used to analyze eight existing systems (BACON, BOGART, DUCE, FRINGE, MIRO, PLSO, STAGGER, and STABB) and to identify promising approaches to feature construction. The framework also served as the basis for the design of CITRE, an inductive system that constructs new features using decision tress. CITRE was tested on five learning problems: l-term kDNF Boolean functions, tic-tac-toe classification, mushroom classification, voting-record classification, and chess-end-game classification. The results demonstrate CITRE's potential for significantly improving hypothesis accuracy and conciseness. The results also reveal substantial benefits obtainable by using simple domain-knowledge constraints and constructor generalization during feature construction.","Made available in DSpace on 2011-05-07T14:02:58Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9021727.pdf: 7439240 bytes, checksum: 4b4147f1191f4ef69632547cbe63e3d1 (MD5) Previous issue date: 1990","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T15:02:19Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:29:38-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"]},{"key":"dc:title","label":"Title","values":["Feature construction: An analytic framework and an application to decision trees"]}]}],"canonical_facts":{"dc:contributor":["Rendell, Larry A."],"dc:creator":["Matheus, Christopher John"],"dc:date":["2011-05-07T14:02:58Z","10000-01-01","1990"],"dc:description":["While similarity-based learning (SBL) methods can be effective for acquiring concept descriptions from labeled examples, their success largely depends upon the quality of the features used to describe the examples. When a learning problem uses low-level features, the complexity of the concept-membership function can make SBL inaccurate, expensive, or simply impossible. One way to overcome this limitation is through feature construction: the construction of new features by the application of constructive operators to existing features. Feature construction can result in an improved instance space in which the concept-membership function is better behaved relative to the inductive biases of SBL algorithms. Feature construction, however, is computationally difficult, primarily because of the intractably large space of potential new features. To assist in the study and advancement of feature construction methods, this thesis presents a feature construction framework based on the aspects of (1) need detection, (2) constructor selection, (3) constructor generalization, and (4) feature evaluation. This framework was used to analyze eight existing systems (BACON, BOGART, DUCE, FRINGE, MIRO, PLSO, STAGGER, and STABB) and to identify promising approaches to feature construction. The framework also served as the basis for the design of CITRE, an inductive system that constructs new features using decision tress. CITRE was tested on five learning problems: l-term kDNF Boolean functions, tic-tac-toe classification, mushroom classification, voting-record classification, and chess-end-game classification. The results demonstrate CITRE's potential for significantly improving hypothesis accuracy and conciseness. The results also reveal substantial benefits obtainable by using simple domain-knowledge constraints and constructor generalization during feature construction.","Made available in DSpace on 2011-05-07T14:02:58Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9021727.pdf: 7439240 bytes, checksum: 4b4147f1191f4ef69632547cbe63e3d1 (MD5) Previous issue date: 1990","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T15:02:19Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:29:38-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"],"dc:identifier":["AAI9021727","(UMI)AAI9021727","http://hdl.handle.net/2142/23122"],"dc:language":["eng"],"dc:rights":["Copyright 1990 Matheus, Christopher John"],"dc:subject":["Artificial Intelligence","Computer Science"],"dc:title":["Feature construction: An analytic framework and an application to decision trees"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:21Z"}