This is a theoritical question about decision trees. I believe that the question is very explicit in the title of the question. My thoughts on this question follow below.

If the region we are dealing with can be separated using directions that are orthogonal to the axis, then we model such region with a decision tree that has 100% acuraccy.

Some examples of such regions are the two pictures below.

enter image description here

enter image description here

On the other hand, if the region we are dealing with is not separable using directions that are orthogonal to the axis, then we might assume that we CAN'T model this region with a 100% accuracy decision tree. Below I present an example of such regions.

enter image description here

Essentialy, what I am asking is:

Let's say we are given some two-dimensional region. When can we guarantee that this region we are given can be modeled by a decision tree that has 100% acuraccy?

Is my thinking presented above correct?

Thanks for any help in advance.

  • $\begingroup$ In what sense is your second region not "linearly separable"? It evidently consists of two portions of a square delimited by a line segment, and that's about as linear as anything can get. If anything, the second image would be the best candidate for a non-linear separation. I would guess that what you are trying to get at is some idea related to "decisions based on one variable at a time" rather than linearity. $\endgroup$
    – whuber
    Commented Apr 19, 2023 at 15:49
  • $\begingroup$ @whuber Thanks for your comment. The images and the thinking posted above is purely my thinking, it might be wrong! By "linear separable" I meant that I can split the regions using orthogonal directions relatively to the axis. The last picture consists of a separation that's clearly not perpendicular to the axis, while the two pictures above have separations which are orthogonal to the axis. Sorry for any confusion. $\endgroup$
    – xyz
    Commented Apr 19, 2023 at 15:55
  • 1
    $\begingroup$ Right now we're not discussing right or wrong, but only verifying you are asking the question you want to ask. Consider editing your post to include the information from your comment. $\endgroup$
    – whuber
    Commented Apr 19, 2023 at 15:57
  • $\begingroup$ @whuber Thanks for the feedback. I have updated the question based on my comment and added a final confirmation of the question I am asking. $\endgroup$
    – xyz
    Commented Apr 19, 2023 at 16:02
  • $\begingroup$ Your question is closely related to quadtrees. See my post at gis.stackexchange.com/a/31879/664 for a description and illustrations. It might help to know that the quadtree is a class of data structures used in geographic information systems to represent and spatially organize any 2D dataset. $\endgroup$
    – whuber
    Commented Apr 19, 2023 at 16:06


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.