Scribd Logo
Upload

Welcome to Scribd!

  • 97 views

    Decision Tree - Associative Rule Mining

    Uploaded by

    Noh Naim
    Decision trees are a type of predictive model that use a tree-like structure to determine the target variable. The ID3 and CART algorithms are commonly used to build decision trees. ID3 uses information gain to select the best features at each node, evaluating features based on their ability to separate classes. It builds the tree in a top-down, greedy manner. CART uses the Gini index for feature selection and can perform both classification and regression tasks. Market basket analysis examines customer purchasing patterns to determine rules about what products are commonly bought together.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd

    Decision Tree - Associative Rule Mining

    Uploaded by

    Noh Naim
    97 views69 pages
    Decision trees are a type of predictive model that use a tree-like structure to determine the target variable. The ID3 and CART algorithms are commonly used to build decision trees. ID3 uses information gain to select the best features at each node, evaluating features based on their ability to separate classes. It builds the tree in a top-down, greedy manner. CART uses the Gini index for feature selection and can perform both classification and regression tasks. Market basket analysis examines customer purchasing patterns to determine rules about what products are commonly bought together.

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Decision trees are a type of predictive model that use a tree-like structure to determine the target variable. The ID3 and CART algorithms are commonly used to build decision trees. ID3 uses information gain to select the best features at each node, evaluating features based on their ability to separate classes. It builds the tree in a top-down, greedy manner. CART uses the Gini index for feature selection and can perform both classification and regression tasks. Market basket analysis examines customer purchasing patterns to determine rules about what products are commonly bought together.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    97 views69 pages

    Decision Tree - Associative Rule Mining

    Uploaded by

    Noh Naim
    Decision trees are a type of predictive model that use a tree-like structure to determine the target variable. The ID3 and CART algorithms are commonly used to build decision trees. ID3 uses information gain to select the best features at each node, evaluating features based on their ability to separate classes. It builds the tree in a top-down, greedy manner. CART uses the Gini index for feature selection and can perform both classification and regression tasks. Market basket analysis examines customer purchasing patterns to determine rules about what products are commonly bought together.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    You are on page 1of 69

    Decision Tree

    What is a Decision Tree?


    Advantages of Decision Tree
    Are tree based model better than linear models?
    Terminology of Decision Tree
    Types of Decision Tree
    ID3 Algorithm
    ID3 stands for Iterative Dichotomiser 3

    Named such because the algorithm iteratively (repeatedly)


    dichotomizes(divides) features into two or more groups at each step.

    ID3 uses a top-down greedy approach to build a decision tree.

    The top-down approach means that we start building the tree from the top

    The greedy approach means that at each iteration we select the best feature at


    the present moment to create a node.

    Most generally ID3 is only used for classification problems with nominal


    features only.
    Metrics in ID3
    The ID3 algorithm selects the best feature at each step while building a Decision tree.

    ID3 uses Information Gain or just Gain to find the best feature.

    Information Gain calculates the reduction in the entropy and measures how well a given
    feature separates or classifies the target classes. The feature with the highest Information
    Gain is selected as the best one.

    Information gain is given by the formula :-

    IG(S, A) = Entropy(S) - ∑((|Sᵥ| / |S|) * Entropy(Sᵥ))

    Where, 
    Sᵥ is the set of rows in S for which the feature column A has value v
    |Sᵥ| is the number of rows in Sᵥ 
    |S| is the number of rows in S.
    Entropy is the measure of disorder and the Entropy of a dataset is the measure of
    disorder in the target feature of the dataset.

    In the case of binary classification (where the target column has only two types of classes)
    entropy is 0 if all values in the target column are homogenous(similar) and will be 1 if the
    target column has equal number values for both the classes.

    We denote our dataset as S, entropy is calculated as:

    Entropy(S) = - ∑ pᵢ * log₂(pᵢ) ; i = 1 to n
    where,
    n is the total number of classes in the target column (in our case n = 2 i.e YES and NO)
    pᵢ is the probability of class ‘i’ or the ratio of “number of rows with class i in the target
    column” to the “total number of rows” in the dataset.
    ID3 Steps

    1.Calculate the Information Gain of each feature.

    2.Considering that all rows don’t belong to the same class, split the dataset S into subsets
    using the feature for which the Information Gain is maximum.

    3.Make a decision tree node using the feature with the maximum Information gain.

    4.If all rows belong to the same class, make the current node as a leaf node with the class
    as its label.

    5.Repeat for the remaining features until we run out of all features, or the decision tree has
    all leaf nodes.
    Example
    CART Algorithm
    CART Algorithm for Classification
    The tree will be constructed in a top-down approach as follows:

    Step 1: Start at the root node with all training instances

    Step 2: Select an attribute on the basis of splitting criteria (Gini-Index)

    Step 3: Partition instances according to selected attribute recursively

    Partitioning stops when:


     There are no examples left
     All examples for a given node belong to the same class
     There are no remaining attributes for further partitioning – majority class is the leaf
    Example
    Market Basket
    analysis
    What is Market Basket Analysis?
    Why use it?
    Important Terms
    Important Terms
    Associative rule
    mining
    Consider Support as 50% and Confidence as 75 %
    Make 2 candidate item set and write the corresponding frequency
    and support
    All rules are good
    as the confidence
    is 75 %

    You might also like