{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\n# Greedy and probing strategies in CRFE\n\n:class:`~tagarnina.crfe.CRFE` removes features in steps. At each step it must\nchoose which of the least important features can be removed together while the\nconstraints still hold. The ``strategy`` parameter controls how that choice is\nmade:\n\n- ``\"greedy\"`` tries to remove all candidates of the step at once. If that is\n  infeasible, the search stops.\n- ``\"probing\"`` tests the candidates one by one, from least to most important.\n  A candidate that cannot be removed is blocked for the rest of the search, and\n  the search continues.\n\nWithout constraints both strategies select the same features. The choice matters\nwhen the constraints bind. This example uses the German credit dataset from the\nbasic example, with an\n:class:`~tagarnina.optimization.constraints.AllOrNoneConstraint` on the one-hot\ncolumns of each categorical feature.\n\nThe dataset is public and is available on OpenML (ID 31). Please cite it as:\nDr. Hans Hofmann, Statlog (German Credit Data), UCI Machine Learning Repository,\n1994.\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Load the data and build the constraints\nThe one-hot encoding and the all-or-none constraints are the same as in the\nbasic example.\n\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "import warnings\n\nimport pandas as pd\nfrom sklearn.compose import ColumnTransformer, make_column_selector\nfrom sklearn.datasets import fetch_openml\nfrom sklearn.preprocessing import OneHotEncoder\n\nfrom tagarnina.optimization.constraints import AllOrNoneConstraint, Constraints\n\nwarnings.filterwarnings(\"ignore\")\n\nX, y = fetch_openml(data_id=31, as_frame=True, return_X_y=True, parser=\"auto\")\ny = (y == \"good\").astype(int)\ncategorical_features = X.select_dtypes(\"category\").columns.tolist()\n\npreprocessor = ColumnTransformer(\n    transformers=[\n        (\"cat\", OneHotEncoder(), make_column_selector(dtype_include=\"category\"))\n    ],\n    remainder=\"passthrough\",\n    verbose_feature_names_out=False,\n)\nX_transformed = pd.DataFrame(\n    data=preprocessor.fit_transform(X),\n    columns=preprocessor.get_feature_names_out(),\n)\n\nconstraints = Constraints(\n    constraints=[\n        AllOrNoneConstraint(\n            features=[c for c in X_transformed.columns if c.startswith(f\"{feature}_\")]\n        )\n        for feature in categorical_features\n    ],\n)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Run both strategies\nBoth runs select 20 features. The summary reports how the search ended, the\nnumber of infeasible probes, and the number of features blocked from removal.\nGreedy has no probes, so its counts are 0.\n\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "from sklearn.ensemble import RandomForestClassifier\n\nfrom tagarnina.crfe import CRFE\n\n\ndef make_crfe(*, strategy, n_features_to_select, constraints):\n    return CRFE(\n        estimator=RandomForestClassifier(\n            max_depth=10, min_samples_leaf=0.2, random_state=0\n        ),\n        constraints=constraints,\n        step=0.1,\n        n_features_to_select=n_features_to_select,\n        scoring=\"roc_auc\",\n        strategy=strategy,\n    )\n\n\nruns = {}\nfor strategy in [\"greedy\", \"probing\"]:\n    crfe = make_crfe(\n        strategy=strategy, n_features_to_select=20, constraints=constraints\n    ).fit(X_transformed, y)\n    runs[strategy] = crfe\n    summary = crfe.summary_\n    print(\n        f\"{strategy:8s} termination: {summary['termination']}, \"\n        f\"features: {len(crfe.get_feature_names_out())}, \"\n        f\"infeasible probes: {summary['n_infeasible_probes']}, \"\n        f\"blocked: {summary['n_blocked']}\"\n    )"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Greedy stops with more features than requested. Its last step tried to remove\nall candidates at once, and that was infeasible under the constraints. Probing\ntested the same candidates one by one, blocked those it could not remove, and\nreached the target.\n\nThe support sizes at each step show where the two searches separate:\n\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "for strategy, crfe in runs.items():\n    print(strategy, crfe.history_[\"n_features\"].astype(int).tolist())"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Effect of the target size\nThe gap depends on the target size. The table repeats the run for several target\nsizes. At 15 both strategies reach the target. From 20 upward greedy stops 1 or\n2 features above the target, while probing reaches each target.\n\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "rows = []\nfor n_features_to_select in [15, 20, 30, 40, 50]:\n    for strategy in [\"greedy\", \"probing\"]:\n        crfe = make_crfe(\n            strategy=strategy,\n            n_features_to_select=n_features_to_select,\n            constraints=constraints,\n        ).fit(X_transformed, y)\n        rows.append(\n            {\n                \"target\": n_features_to_select,\n                \"strategy\": strategy,\n                \"termination\": str(crfe.summary_[\"termination\"]),\n                \"features\": len(crfe.get_feature_names_out()),\n                \"infeasible_probes\": crfe.summary_[\"n_infeasible_probes\"],\n            }\n        )\n\nresults = pd.DataFrame(rows)\nprint(results.to_string(index=False))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "The same results as a plot. The dashed line is the target, so points on the line\nreached it.\n\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "import matplotlib.pyplot as plt\n\nfig, ax = plt.subplots()\nfor strategy, marker in [(\"greedy\", \"s\"), (\"probing\", \"o\")]:\n    subset = results[results[\"strategy\"] == strategy]\n    ax.plot(subset[\"target\"], subset[\"features\"], marker=marker, label=strategy)\nax.plot(\n    results[\"target\"].unique(),\n    results[\"target\"].unique(),\n    linestyle=\"--\",\n    color=\"grey\",\n    label=\"target\",\n)\nax.set_xlabel(\"Target number of features\")\nax.set_ylabel(\"Features selected\")\nax.legend()\nfig.tight_layout()"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Without constraints the strategies agree\nWith no constraints every candidate can be removed, so greedy and probing make\nthe same choices. The same check confirms that the strategy only matters when\nthe constraints bind.\n\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "unconstrained = {\n    strategy: make_crfe(\n        strategy=strategy, n_features_to_select=20, constraints=None\n    ).fit(X_transformed, y)\n    for strategy in [\"greedy\", \"probing\"]\n}\nsame = list(unconstrained[\"greedy\"].get_feature_names_out()) == list(\n    unconstrained[\"probing\"].get_feature_names_out()\n)\nprint(f\"Same selected features without constraints: {same}\")"
      ]
    }
  ],
  "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.13.17"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}