decision tree it is not possible to linearly separate the training setbut we can partition the feature space into rectangular regions and assign class (colorto each regionas shown in the right panel of figure points in these regions are classified accordingly as blue or red the partition thus defines classifier (prediction functiong that assigns to each feature vector class "redor "bluefor examplefor [- ](solid black point) ( "blue"since it belongs to blue region of the feature space both the classification procedure and the partitioning of the feature space can be conveniently represented by binary decision tree this is tree where each node corresponds to region (subsetrv of the feature space -the root node corresponding to the feature space itself each internal node contains logical condition that dix < vides rv into two disjoint subregions the leaf nodes (the tertrue minal nodes of the treeare not subdividedand their corresfalse ponding regions form partition of xas they are disjoint and <- their union is associated with each leaf node is also false true regional prediction function gw on rw < the partitioning of figure was obtained from the decision tree shown in figure as an illustratrue false tion of the decision procedureconsider again the input < [ ][- ]the classification process starts true from the tree rootwhich contains the condition as false the second component of is the root condition is satisfied <- and we proceed to the left childwhich contains the condition true false - the next step is similar as - the condition is not satisfied and we proceed to the right child such an evaluation of logical conditions along the tree path will eventually bring us to leaf node and its associated region in this case the process terminates in leaf that corresponds to the figure the decisiontree that corresponds to the left blue region in the right-hand panel of figure partition in figure more generallya binary tree will partition the feature space into as many regions as there are leaf nodes denote the set of leaf nodes by the overall prediction function that corresponds to the tree can then be written as (xgw ( { rw }( ww regional prediction functions where denotes the indicator function the representation ( is very general and depends on ( how the regions {rw are constructed via the logical conditions in the decision treeas well as ( how the regional prediction functions of the leaf nodes are defined simple logical conditions of the form split euclidean feature space into rectangles aligned with the axes for examplefigure partitions the feature space into six rectanglestwo blue and four red rectangles in classification settingthe regional prediction function gw corresponding to leaf node takes values in the set of possible class labels in most casesas in example it is taken to be constant on the corresponding region rw in regression settinggw is realvalued and also usually takes only one value that isevery feature vector in rw leads to