{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\n# Multi-class AdaBoosted Decision Trees\n\nThis example shows how boosting can improve the prediction accuracy on a\nmulti-label classification problem. It reproduces a similar experiment as\ndepicted by Figure 1 in Zhu et al [1]_.\n\nThe core principle of AdaBoost (Adaptive Boosting) is to fit a sequence of weak\nlearners (e.g. Decision Trees) on repeatedly re-sampled versions of the data.\nEach sample carries a weight that is adjusted after each training step, such\nthat misclassified samples will be assigned higher weights. The re-sampling\nprocess with replacement takes into account the weights assigned to each sample.\nSamples with higher weights have a greater chance of being selected multiple\ntimes in the new data set, while samples with lower weights are less likely to\nbe selected. This ensures that subsequent iterations of the algorithm focus on\nthe difficult-to-classify samples.\n\n.. rubric:: References\n\n.. [1] :doi:`J. Zhu, H. Zou, S. Rosset, T. Hastie, \"Multi-class adaboost.\"\n    Statistics and its Interface 2.3 (2009): 349-360.\n    <10.4310/SII.2009.v2.n3.a8>`\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "# Authors: The scikit-learn developers\n# SPDX-License-Identifier: BSD-3-Clause"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Creating the dataset\nThe classification dataset is constructed by taking a ten-dimensional standard\nnormal distribution ($x$ in $R^{10}$) and defining three classes\nseparated by nested concentric ten-dimensional spheres such that roughly equal\nnumbers of samples are in each class (quantiles of the $\\chi^2$\ndistribution).\n\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "from sklearn.datasets import make_gaussian_quantiles\n\nX, y = make_gaussian_quantiles(\n    n_samples=2_000, n_features=10, n_classes=3, random_state=1\n)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "We split the dataset into 2 sets: 70 percent of the samples are used for\ntraining and the remaining 30 percent for testing.\n\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "from sklearn.model_selection import train_test_split\n\nX_train, X_test, y_train, y_test = train_test_split(\n    X, y, train_size=0.7, random_state=42\n)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Training the `AdaBoostClassifier`\nWe train the :class:`~sklearn.ensemble.AdaBoostClassifier`. The estimator\nutilizes boosting to improve the classification accuracy. Boosting is a method\ndesigned to train weak learners (i.e. `estimator`) that learn from their\npredecessor's mistakes.\n\nHere, we define the weak learner as a\n:class:`~sklearn.tree.DecisionTreeClassifier` and set the maximum number of\nleaves to 8. In a real setting, this parameter should be tuned. We set it to a\nrather low value to limit the runtime of the example.\n\nThe `SAMME` algorithm build into the\n:class:`~sklearn.ensemble.AdaBoostClassifier` then uses the correct or\nincorrect predictions made be the current weak learner to update the sample\nweights used for training the consecutive weak learners. Also, the weight of\nthe weak learner itself is calculated based on its accuracy in classifying the\ntraining examples. The weight of the weak learner determines its influence on\nthe final ensemble prediction.\n\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "from sklearn.ensemble import AdaBoostClassifier\nfrom sklearn.tree import DecisionTreeClassifier\n\nweak_learner = DecisionTreeClassifier(max_leaf_nodes=8)\nn_estimators = 300\n\nadaboost_clf = AdaBoostClassifier(\n    estimator=weak_learner,\n    n_estimators=n_estimators,\n    random_state=42,\n).fit(X_train, y_train)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Analysis\nConvergence of the `AdaBoostClassifier`\n***************************************\nTo demonstrate the effectiveness of boosting in improving accuracy, we\nevaluate the misclassification error of the boosted trees in comparison to two\nbaseline scores. The first baseline score is the `misclassification_error`\nobtained from a single weak-learner (i.e.\n:class:`~sklearn.tree.DecisionTreeClassifier`), which serves as a reference\npoint. The second baseline score is obtained from the\n:class:`~sklearn.dummy.DummyClassifier`, which predicts the most prevalent\nclass in a dataset.\n\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "from sklearn.dummy import DummyClassifier\nfrom sklearn.metrics import accuracy_score\n\ndummy_clf = DummyClassifier()\n\n\ndef misclassification_error(y_true, y_pred):\n    return 1 - accuracy_score(y_true, y_pred)\n\n\nweak_learners_misclassification_error = misclassification_error(\n    y_test, weak_learner.fit(X_train, y_train).predict(X_test)\n)\n\ndummy_classifiers_misclassification_error = misclassification_error(\n    y_test, dummy_clf.fit(X_train, y_train).predict(X_test)\n)\n\nprint(\n    \"DecisionTreeClassifier's misclassification_error: \"\n    f\"{weak_learners_misclassification_error:.3f}\"\n)\nprint(\n    \"DummyClassifier's misclassification_error: \"\n    f\"{dummy_classifiers_misclassification_error:.3f}\"\n)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "After training the :class:`~sklearn.tree.DecisionTreeClassifier` model, the\nachieved error surpasses the expected value that would have been obtained by\nguessing the most frequent class label, as the\n:class:`~sklearn.dummy.DummyClassifier` does.\n\nNow, we calculate the `misclassification_error`, i.e. `1 - accuracy`, of the\nadditive model (:class:`~sklearn.tree.DecisionTreeClassifier`) at each\nboosting iteration on the test set to assess its performance.\n\nWe use :meth:`~sklearn.ensemble.AdaBoostClassifier.staged_predict` that makes\nas many iterations as the number of fitted estimator (i.e. corresponding to\n`n_estimators`). At iteration `n`, the predictions of AdaBoost only use the\n`n` first weak learners. We compare these predictions with the true\npredictions `y_test` and we, therefore, conclude on the benefit (or not) of adding a\nnew weak learner into the chain.\n\nWe plot the misclassification error for the different stages:\n\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "import matplotlib.pyplot as plt\nimport pandas as pd\n\nboosting_errors = pd.DataFrame(\n    {\n        \"Number of trees\": range(1, n_estimators + 1),\n        \"AdaBoost\": [\n            misclassification_error(y_test, y_pred)\n            for y_pred in adaboost_clf.staged_predict(X_test)\n        ],\n    }\n).set_index(\"Number of trees\")\nax = boosting_errors.plot()\nax.set_ylabel(\"Misclassification error on test set\")\nax.set_title(\"Convergence of AdaBoost algorithm\")\n\nplt.plot(\n    [boosting_errors.index.min(), boosting_errors.index.max()],\n    [weak_learners_misclassification_error, weak_learners_misclassification_error],\n    color=\"tab:orange\",\n    linestyle=\"dashed\",\n)\nplt.plot(\n    [boosting_errors.index.min(), boosting_errors.index.max()],\n    [\n        dummy_classifiers_misclassification_error,\n        dummy_classifiers_misclassification_error,\n    ],\n    color=\"c\",\n    linestyle=\"dotted\",\n)\nplt.legend([\"AdaBoost\", \"DecisionTreeClassifier\", \"DummyClassifier\"], loc=1)\nplt.show()"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "The plot shows the missclassification error on the test set after each\nboosting iteration. We see that the error of the boosted trees converges to an\nerror of around 0.3 after 50 iterations, indicating a significantly higher\naccuracy compared to a single tree, as illustrated by the dashed line in the\nplot.\n\nThe misclassification error jitters because the `SAMME` algorithm uses the\ndiscrete outputs of the weak learners to train the boosted model.\n\nThe convergence of :class:`~sklearn.ensemble.AdaBoostClassifier` is mainly\ninfluenced by the learning rate (i.e. `learning_rate`), the number of weak\nlearners used (`n_estimators`), and the expressivity of the weak learners\n(e.g. `max_leaf_nodes`).\n\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Errors and weights of the Weak Learners\nAs previously mentioned, AdaBoost is a forward stagewise additive model. We\nnow focus on understanding the relationship between the attributed weights of\nthe weak learners and their statistical performance.\n\nWe use the fitted :class:`~sklearn.ensemble.AdaBoostClassifier`'s attributes\n`estimator_errors_` and `estimator_weights_` to investigate this link.\n\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "weak_learners_info = pd.DataFrame(\n    {\n        \"Number of trees\": range(1, n_estimators + 1),\n        \"Errors\": adaboost_clf.estimator_errors_,\n        \"Weights\": adaboost_clf.estimator_weights_,\n    }\n).set_index(\"Number of trees\")\n\naxs = weak_learners_info.plot(\n    subplots=True, layout=(1, 2), figsize=(10, 4), legend=False, color=\"tab:blue\"\n)\naxs[0, 0].set_ylabel(\"Train error\")\naxs[0, 0].set_title(\"Weak learner's training error\")\naxs[0, 1].set_ylabel(\"Weight\")\naxs[0, 1].set_title(\"Weak learner's weight\")\nfig = axs[0, 0].get_figure()\nfig.suptitle(\"Weak learner's errors and weights for the AdaBoostClassifier\")\nfig.tight_layout()"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "On the left plot, we show the weighted error of each weak learner on the\nreweighted training set at each boosting iteration. On the right plot, we show\nthe weights associated with each weak learner later used to make the\npredictions of the final additive model.\n\nWe see that the error of the weak learner is the inverse of the weights. It\nmeans that our additive model will trust more a weak learner that makes\nsmaller errors (on the training set) by increasing its impact on the final\ndecision. Indeed, this exactly is the formulation of updating the base\nestimators' weights after each iteration in AdaBoost.\n\n.. dropdown:: Mathematical details\n\n   The weight associated with a weak learner trained at the stage $m$ is\n   inversely associated with its misclassification error such that:\n\n   .. math:: \\alpha^{(m)} = \\log \\frac{1 - err^{(m)}}{err^{(m)}} + \\log (K - 1),\n\n   where $\\alpha^{(m)}$ and $err^{(m)}$ are the weight and the error\n   of the $m$ th weak learner, respectively, and $K$ is the number of\n   classes in our classification problem.\n\nAnother interesting observation boils down to the fact that the first weak\nlearners of the model make fewer errors than later weak learners of the\nboosting chain.\n\nThe intuition behind this observation is the following: due to the sample\nreweighting, later classifiers are forced to try to classify more difficult or\nnoisy samples and to ignore already well classified samples. Therefore, the\noverall error on the training set will increase. That's why the weak learner's\nweights are built to counter-balance the worse performing weak learners.\n\n"
      ]
    }
  ],
  "metadata": {
    "kernelspec": {
      "display_name": "Python 3",
      "language": "python",
      "name": "python3"
    },
    "language_info": {
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython3",
      "version": "3.11.14"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}