The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [decision-tree]

The tag has no usage guidance.

19 questions
Filter by
Sorted by
Tagged with
14 views

Same Result of KNN and Decision Tree

Given a decision tree, is it possible to find a KNN classifier giving the exact same classification?
72 views

Decision Tree for searching an element in an n*n matrix

I just learnt decision tree concept in class. I have a question for homework. It says to prove that for searching an element in n*n matrix the lower bound is logn and prove it using decision tree. My ...
18 views

Lower bound for merging $m$ sorted arrays (decision tree leaves count - permutations)

I need some help understanding how to calculate the lower bound on the time complexity of merging $m$ sorted arrays of length $n$. The bound should be $nm \lg(m)$. I need to prove this using a ...
12 views

Can an optimal global classification tree be constructed from trees for single categories?

Suppose we have a set of objects, each belonging to one of the disjoint categories $c_1, ... , c_n$. Suppose further that for every single category $c_i$ there is a corresponding set $T_i$ that ...
15 views

how can i find that the size of tree which is built by C5.0 algorithm is good?

I built C5.0 for balancing data with 16 attributes. and the size of my model is 125 and it used 15 attributes for building model.how can i find the size is good?
55 views

How to calculate information gain in ID3?

I am trying to implement a decision tree classifier using ID3 algorithm. According to Aritificial Intelligence - A Modern Approach, information gain of attribute A ...
144 views

Random Forest - Conditional Permutation Importance

I've been looking for the most unbiased algorithm to find out the feature importances in random forests if there are correlations among the input features. Besides the most commonly preferred ...
32 views

Finding maximum takes at least $\lceil n/2 \rceil$ comparisons

We are given an array $A$ with $n$ elements, $n \in \mathbb{N}$ and all elements are in the set $\{1,2,3, \cdots, n \}$. I want to prove that finding the maximum in $A$ (that is, outputting the index ...
16 views

decision trees and numeric attributes

I have been reading a book about Decision Trees and it caught my attention the following part: In case of numeric attributes, decision trees can be geometrically interpreted as a collection of ...
26 views

Classify/Distinguish between 8008 binary grids, with 13 queries

I have $8008$ binary grids of size $6 \times 10$ (they are all grids with the property described below), which I want to distinguish between with at most $13$ queries. A query will determine if the ...
25 views

Attribute Selection for minimum number of clusters

I have a table consisting of some headers $P, Q, R, S$ (shown in blue in Table 1). According to the headers, the column $T$ is populated using some predefined logic. Now, any of the headers $P,Q,R,S$ ...
33 views

What do Arora and Barak mean by $x|_S$ in their definition of certificate complexity?

I am having much trouble understanding the following definition (of certificate complexity - for decision trees) from Arora and Barak's book Computational Complexity: A Modern Approach. Perhaps there ...
29 views

Avoiding collisions in space and time

Say I have an image, represented as a 2D array of pixel values. Also, say I have a set of points on that image where each has a current (x, y) position and a Destination (x, y) associated with it. I ...
922 views

What machine learning training algorithm to use for this kind of string dataset?

I am working on a project where I have to train the following data-set using machine learning algorithm. One of my friend suggested decision tree, but I have never seen a situation where independent ...
39 views

Decision Tree Learning Deviation - Russell and Norvig

I am working through the Russell and Norvig AI book and came across the following on the top of page 706. The section concerns Decision Tree pruning and testing a given attribute against the null ...
514 views

What is the main difference between binary decision tree and binary decision diagram(BDD)?

What is the main difference between binary decision tree and binary decision diagram(BDD)? From what I can tell I only understand that a binary decision diagram is a more compact representation ...
35 views

Connected Components - Linear Decision Trees

What does connected components mean in the context of non-graphs? Graphs have vertices and the vertices are connected by edges. Hence, you can build a spanning tree (for example) by systematically ...
I am currently studying for a test on data structures. I have to find the lower and upper bounds for the following problem: An array is called a zigzag array if there are $1 \leq i \leq j \leq n$ ...
I am currently studying for a test on data structures. I have to find the lower and upper bounds for the following problem: Input: an array with $n$ numbers. Output: boolean answer for the ...