TY - CHAP
T1 - Infinite Binary Information Systems. Decision Trees of Types 1, 2, and 3
AU - Azad, Mohammad
AU - Chikalov, Igor
AU - Hussain, Shahid
AU - Moshkov, Mikhail
AU - Zielosko, Beata
N1 - KAUST Repository Item: Exported on 2022-12-02
PY - 2022/11/19
Y1 - 2022/11/19
N2 - In this chapter, based on results of test theory, rough set theory, and exact learning, we study arbitrary infinite binary information systems each of which consists of an infinite set of elements and an infinite set of two-valued functions (attributes) defined on the set of elements. We consider the notion of a problem over information system, which is described by a finite number of attributes: for a given element, we should recognize values of these attributes. As algorithms for problem solving, we study decision trees of three types based on attributes from problem description: (1) using only attributes, (2) using only hypotheses, and (3) using both attributes and hypotheses. As time complexity, we use the depth of decision trees. In the worst case, with the growth of the number of attributes in the problem description, the minimum depth of decision trees of type 1 grows either as a logarithm or linearly, and the minimum depth of decision trees of types 2 and 3 either is bounded from above by a constant or grows as a logarithm, or linearly. Based on these results, we divide the set of all infinite binary information systems into four complexity classes.
AB - In this chapter, based on results of test theory, rough set theory, and exact learning, we study arbitrary infinite binary information systems each of which consists of an infinite set of elements and an infinite set of two-valued functions (attributes) defined on the set of elements. We consider the notion of a problem over information system, which is described by a finite number of attributes: for a given element, we should recognize values of these attributes. As algorithms for problem solving, we study decision trees of three types based on attributes from problem description: (1) using only attributes, (2) using only hypotheses, and (3) using both attributes and hypotheses. As time complexity, we use the depth of decision trees. In the worst case, with the growth of the number of attributes in the problem description, the minimum depth of decision trees of type 1 grows either as a logarithm or linearly, and the minimum depth of decision trees of types 2 and 3 either is bounded from above by a constant or grows as a logarithm, or linearly. Based on these results, we divide the set of all infinite binary information systems into four complexity classes.
UR - http://hdl.handle.net/10754/686114
UR - https://link.springer.com/10.1007/978-3-031-08585-7_7
U2 - 10.1007/978-3-031-08585-7_7
DO - 10.1007/978-3-031-08585-7_7
M3 - Chapter
SN - 9783031085840
SP - 83
EP - 98
BT - Decision Trees with Hypotheses
PB - Springer International Publishing
ER -