Aluode/PerceptionLabPortable
0
1"""
2Sequential feature selection
3"""
4
5# Authors: The scikit-learn developers
6# SPDX-License-Identifier: BSD-3-Clause
7
8from numbers import Integral, Real
9
10import numpy as np
11
12from ..base import BaseEstimator, MetaEstimatorMixin, _fit_context, clone, is_classifier
13from ..metrics import check_scoring, get_scorer_names
14from ..model_selection import check_cv, cross_val_score
15from ..utils._metadata_requests import (
16 MetadataRouter,
17 MethodMapping,
18 _raise_for_params,
19 _routing_enabled,
20 process_routing,
21)
22from ..utils._param_validation import HasMethods, Interval, RealNotInt, StrOptions
23from ..utils._tags import get_tags
24from ..utils.validation import check_is_fitted, validate_data
25from ._base import SelectorMixin
26
27
28class SequentialFeatureSelector(SelectorMixin, MetaEstimatorMixin, BaseEstimator):
29 """Transformer that performs Sequential Feature Selection.
30
31 This Sequential Feature Selector adds (forward selection) or
32 removes (backward selection) features to form a feature subset in a
33 greedy fashion. At each stage, this estimator chooses the best feature to
34 add or remove based on the cross-validation score of an estimator. In
35 the case of unsupervised learning, this Sequential Feature Selector
36 looks only at the features (X), not the desired outputs (y).
37
38 Read more in the :ref:`User Guide <sequential_feature_selection>`.
39
40 .. versionadded:: 0.24
41
42 Parameters
43 ----------
44 estimator : estimator instance
45 An unfitted estimator.
46
47 n_features_to_select : "auto", int or float, default="auto"
48 If `"auto"`, the behaviour depends on the `tol` parameter:
49
50 - if `tol` is not `None`, then features are selected while the score
51 change does not exceed `tol`.
52 - otherwise, half of the features are selected.
53
54 If integer, the parameter is the absolute number of features to select.
55 If float between 0 and 1, it is the fraction of features to select.
56
57 .. versionadded:: 1.1
58 The option `"auto"` was added in version 1.1.
59
60 .. versionchanged:: 1.3
61 The default changed from `"warn"` to `"auto"` in 1.3.
62
63 tol : float, default=None
64 If the score is not incremented by at least `tol` between two
65 consecutive feature additions or removals, stop adding or removing.
66
67 `tol` can be negative when removing features using `direction="backward"`.
68 `tol` is required to be strictly positive when doing forward selection.
69 It can be useful to reduce the number of features at the cost of a small
70 decrease in the score.
71
72 `tol` is enabled only when `n_features_to_select` is `"auto"`.
73
74 .. versionadded:: 1.1
75
76 direction : {'forward', 'backward'}, default='forward'
77 Whether to perform forward selection or backward selection.
78
79 scoring : str or callable, default=None
80 Scoring method to use for cross-validation. Options:
81
82 - str: see :ref:`scoring_string_names` for options.
83 - callable: a scorer callable object (e.g., function) with signature
84 ``scorer(estimator, X, y)`` that returns a single value.
85 See :ref:`scoring_callable` for details.
86 - `None`: the `estimator`'s
87 :ref:`default evaluation criterion <scoring_api_overview>` is used.
88
89 cv : int, cross-validation generator or an iterable, default=None
90 Determines the cross-validation splitting strategy.
91 Possible inputs for cv are:
92
93 - None, to use the default 5-fold cross validation,
94 - integer, to specify the number of folds in a `(Stratified)KFold`,
95 - :term:`CV splitter`,
96 - An iterable yielding (train, test) splits as arrays of indices.
97
98 For integer/None inputs, if the estimator is a classifier and ``y`` is
99 either binary or multiclass,
100 :class:`~sklearn.model_selection.StratifiedKFold` is used. In all other
101 cases, :class:`~sklearn.model_selection.KFold` is used. These splitters
102 are instantiated with `shuffle=False` so the splits will be the same
103 across calls.
104
105 Refer :ref:`User Guide <cross_validation>` for the various
106 cross-validation strategies that can be used here.
107
108 n_jobs : int, default=None
109 Number of jobs to run in parallel. When evaluating a new feature to
110 add or remove, the cross-validation procedure is parallel over the
111 folds.
112 ``None`` means 1 unless in a :obj:`joblib.parallel_backend` context.
113 ``-1`` means using all processors. See :term:`Glossary <n_jobs>`
114 for more details.
115
116 Attributes
117 ----------
118 n_features_in_ : int
119 Number of features seen during :term:`fit`. Only defined if the
120 underlying estimator exposes such an attribute when fit.
121
122 .. versionadded:: 0.24
123
124 feature_names_in_ : ndarray of shape (`n_features_in_`,)
125 Names of features seen during :term:`fit`. Defined only when `X`
126 has feature names that are all strings.
127
128 .. versionadded:: 1.0
129
130 n_features_to_select_ : int
131 The number of features that were selected.
132
133 support_ : ndarray of shape (n_features,), dtype=bool
134 The mask of selected features.
135
136 See Also
137 --------
138 GenericUnivariateSelect : Univariate feature selector with configurable
139 strategy.
140 RFE : Recursive feature elimination based on importance weights.
141 RFECV : Recursive feature elimination based on importance weights, with
142 automatic selection of the number of features.
143 SelectFromModel : Feature selection based on thresholds of importance
144 weights.
145
146 Examples
147 --------
148 >>> from sklearn.feature_selection import SequentialFeatureSelector
149 >>> from sklearn.neighbors import KNeighborsClassifier
150 >>> from sklearn.datasets import load_iris
151 >>> X, y = load_iris(return_X_y=True)
152 >>> knn = KNeighborsClassifier(n_neighbors=3)
153 >>> sfs = SequentialFeatureSelector(knn, n_features_to_select=3)
154 >>> sfs.fit(X, y)
155 SequentialFeatureSelector(estimator=KNeighborsClassifier(n_neighbors=3),
156 n_features_to_select=3)
157 >>> sfs.get_support()
158 array([ True, False, True, True])
159 >>> sfs.transform(X).shape
160 (150, 3)
161 """
162
163 _parameter_constraints: dict = {
164 "estimator": [HasMethods(["fit"])],
165 "n_features_to_select": [
166 StrOptions({"auto"}),
167 Interval(RealNotInt, 0, 1, closed="right"),
168 Interval(Integral, 0, None, closed="neither"),
169 ],
170 "tol": [None, Interval(Real, None, None, closed="neither")],
171 "direction": [StrOptions({"forward", "backward"})],
172 "scoring": [None, StrOptions(set(get_scorer_names())), callable],
173 "cv": ["cv_object"],
174 "n_jobs": [None, Integral],
175 }
176
177 def __init__(
178 self,
179 estimator,
180 *,
181 n_features_to_select="auto",
182 tol=None,
183 direction="forward",
184 scoring=None,
185 cv=5,
186 n_jobs=None,
187 ):
188 self.estimator = estimator
189 self.n_features_to_select = n_features_to_select
190 self.tol = tol
191 self.direction = direction
192 self.scoring = scoring
193 self.cv = cv
194 self.n_jobs = n_jobs
195
196 @_fit_context(
197 # SequentialFeatureSelector.estimator is not validated yet
198 prefer_skip_nested_validation=False
199 )
200 def fit(self, X, y=None, **params):
201 """Learn the features to select from X.
202
203 Parameters
204 ----------
205 X : array-like of shape (n_samples, n_features)
206 Training vectors, where `n_samples` is the number of samples and
207 `n_features` is the number of predictors.
208
209 y : array-like of shape (n_samples,), default=None
210 Target values. This parameter may be ignored for
211 unsupervised learning.
212
213 **params : dict, default=None
214 Parameters to be passed to the underlying `estimator`, `cv`
215 and `scorer` objects.
216
217 .. versionadded:: 1.6
218
219 Only available if `enable_metadata_routing=True`,
220 which can be set by using
221 ``sklearn.set_config(enable_metadata_routing=True)``.
222 See :ref:`Metadata Routing User Guide <metadata_routing>` for
223 more details.
224
225 Returns
226 -------
227 self : object
228 Returns the instance itself.
229 """
230 _raise_for_params(params, self, "fit")
231 tags = self.__sklearn_tags__()
232 X = validate_data(
233 self,
234 X,
235 accept_sparse="csc",
236 ensure_min_features=2,
237 ensure_all_finite=not tags.input_tags.allow_nan,
238 )
239 n_features = X.shape[1]
240
241 if self.n_features_to_select == "auto":
242 if self.tol is not None:
243 # With auto feature selection, `n_features_to_select_` will be updated
244 # to `support_.sum()` after features are selected.
245 self.n_features_to_select_ = n_features - 1
246 else:
247 self.n_features_to_select_ = n_features // 2
248 elif isinstance(self.n_features_to_select, Integral):
249 if self.n_features_to_select >= n_features:
250 raise ValueError("n_features_to_select must be < n_features.")
251 self.n_features_to_select_ = self.n_features_to_select
252 elif isinstance(self.n_features_to_select, Real):
253 self.n_features_to_select_ = int(n_features * self.n_features_to_select)
254
255 if self.tol is not None and self.tol < 0 and self.direction == "forward":
256 raise ValueError(
257 "tol must be strictly positive when doing forward selection"
258 )
259
260 cv = check_cv(self.cv, y, classifier=is_classifier(self.estimator))
261
262 cloned_estimator = clone(self.estimator)
263
264 # the current mask corresponds to the set of features:
265 # - that we have already *selected* if we do forward selection
266 # - that we have already *excluded* if we do backward selection
267 current_mask = np.zeros(shape=n_features, dtype=bool)
268 n_iterations = (
269 self.n_features_to_select_
270 if self.n_features_to_select == "auto" or self.direction == "forward"
271 else n_features - self.n_features_to_select_
272 )
273
274 old_score = -np.inf
275 is_auto_select = self.tol is not None and self.n_features_to_select == "auto"
276
277 # We only need to verify the routing here and not use the routed params
278 # because internally the actual routing will also take place inside the
279 # `cross_val_score` function.
280 if _routing_enabled():
281 process_routing(self, "fit", **params)
282 for _ in range(n_iterations):
283 new_feature_idx, new_score = self._get_best_new_feature_score(
284 cloned_estimator, X, y, cv, current_mask, **params
285 )
286 if is_auto_select and ((new_score - old_score) < self.tol):
287 break
288
289 old_score = new_score
290 current_mask[new_feature_idx] = True
291
292 if self.direction == "backward":
293 current_mask = ~current_mask
294
295 self.support_ = current_mask
296 self.n_features_to_select_ = self.support_.sum()
297
298 return self
299
300 def _get_best_new_feature_score(self, estimator, X, y, cv, current_mask, **params):
301 # Return the best new feature and its score to add to the current_mask,
302 # i.e. return the best new feature and its score to add (resp. remove)
303 # when doing forward selection (resp. backward selection).
304 # Feature will be added if the current score and past score are greater
305 # than tol when n_feature is auto,
306 candidate_feature_indices = np.flatnonzero(~current_mask)
307 scores = {}
308 for feature_idx in candidate_feature_indices:
309 candidate_mask = current_mask.copy()
310 candidate_mask[feature_idx] = True
311 if self.direction == "backward":
312 candidate_mask = ~candidate_mask
313 X_new = X[:, candidate_mask]
314 scores[feature_idx] = cross_val_score(
315 estimator,
316 X_new,
317 y,
318 cv=cv,
319 scoring=self.scoring,
320 n_jobs=self.n_jobs,
321 params=params,
322 ).mean()
323 new_feature_idx = max(scores, key=lambda feature_idx: scores[feature_idx])
324 return new_feature_idx, scores[new_feature_idx]
325
326 def _get_support_mask(self):
327 check_is_fitted(self)
328 return self.support_
329
330 def __sklearn_tags__(self):
331 tags = super().__sklearn_tags__()
332 tags.input_tags.allow_nan = get_tags(self.estimator).input_tags.allow_nan
333 tags.input_tags.sparse = get_tags(self.estimator).input_tags.sparse
334 return tags
335
336 def get_metadata_routing(self):
337 """Get metadata routing of this object.
338
339 Please check :ref:`User Guide <metadata_routing>` on how the routing
340 mechanism works.
341
342 .. versionadded:: 1.6
343
344 Returns
345 -------
346 routing : MetadataRouter
347 A :class:`~sklearn.utils.metadata_routing.MetadataRouter` encapsulating
348 routing information.
349 """
350 router = MetadataRouter(owner=self.__class__.__name__)
351 router.add(
352 estimator=self.estimator,
353 method_mapping=MethodMapping().add(caller="fit", callee="fit"),
354 )
355 router.add(
356 splitter=check_cv(self.cv, classifier=is_classifier(self.estimator)),
357 method_mapping=MethodMapping().add(caller="fit", callee="split"),
358 )
359 router.add(
360 scorer=check_scoring(self.estimator, scoring=self.scoring),
361 method_mapping=MethodMapping().add(caller="fit", callee="score"),
362 )
363 return router
364