Aluode/PerceptionLabPortable
0
1"""Approximate kernel feature maps based on Fourier transforms and count sketches."""
2
3# Authors: The scikit-learn developers
4# SPDX-License-Identifier: BSD-3-Clause
5
6import warnings
7from numbers import Integral, Real
8
9import numpy as np
10import scipy.sparse as sp
11from scipy.fft import fft, ifft
12from scipy.linalg import svd
13
14from .base import (
15 BaseEstimator,
16 ClassNamePrefixFeaturesOutMixin,
17 TransformerMixin,
18 _fit_context,
19)
20from .metrics.pairwise import KERNEL_PARAMS, PAIRWISE_KERNEL_FUNCTIONS, pairwise_kernels
21from .utils import check_random_state
22from .utils._param_validation import Interval, StrOptions
23from .utils.extmath import safe_sparse_dot
24from .utils.validation import (
25 _check_feature_names_in,
26 check_is_fitted,
27 validate_data,
28)
29
30
31class PolynomialCountSketch(
32 ClassNamePrefixFeaturesOutMixin, TransformerMixin, BaseEstimator
33):
34 """Polynomial kernel approximation via Tensor Sketch.
35
36 Implements Tensor Sketch, which approximates the feature map
37 of the polynomial kernel::
38
39 K(X, Y) = (gamma * <X, Y> + coef0)^degree
40
41 by efficiently computing a Count Sketch of the outer product of a
42 vector with itself using Fast Fourier Transforms (FFT). Read more in the
43 :ref:`User Guide <polynomial_kernel_approx>`.
44
45 .. versionadded:: 0.24
46
47 Parameters
48 ----------
49 gamma : float, default=1.0
50 Parameter of the polynomial kernel whose feature map
51 will be approximated.
52
53 degree : int, default=2
54 Degree of the polynomial kernel whose feature map
55 will be approximated.
56
57 coef0 : int, default=0
58 Constant term of the polynomial kernel whose feature map
59 will be approximated.
60
61 n_components : int, default=100
62 Dimensionality of the output feature space. Usually, `n_components`
63 should be greater than the number of features in input samples in
64 order to achieve good performance. The optimal score / run time
65 balance is typically achieved around `n_components` = 10 * `n_features`,
66 but this depends on the specific dataset being used.
67
68 random_state : int, RandomState instance, default=None
69 Determines random number generation for indexHash and bitHash
70 initialization. Pass an int for reproducible results across multiple
71 function calls. See :term:`Glossary <random_state>`.
72
73 Attributes
74 ----------
75 indexHash_ : ndarray of shape (degree, n_features), dtype=int64
76 Array of indexes in range [0, n_components) used to represent
77 the 2-wise independent hash functions for Count Sketch computation.
78
79 bitHash_ : ndarray of shape (degree, n_features), dtype=float32
80 Array with random entries in {+1, -1}, used to represent
81 the 2-wise independent hash functions for Count Sketch computation.
82
83 n_features_in_ : int
84 Number of features seen during :term:`fit`.
85
86 .. versionadded:: 0.24
87
88 feature_names_in_ : ndarray of shape (`n_features_in_`,)
89 Names of features seen during :term:`fit`. Defined only when `X`
90 has feature names that are all strings.
91
92 .. versionadded:: 1.0
93
94 See Also
95 --------
96 AdditiveChi2Sampler : Approximate feature map for additive chi2 kernel.
97 Nystroem : Approximate a kernel map using a subset of the training data.
98 RBFSampler : Approximate a RBF kernel feature map using random Fourier
99 features.
100 SkewedChi2Sampler : Approximate feature map for "skewed chi-squared" kernel.
101 sklearn.metrics.pairwise.kernel_metrics : List of built-in kernels.
102
103 Examples
104 --------
105 >>> from sklearn.kernel_approximation import PolynomialCountSketch
106 >>> from sklearn.linear_model import SGDClassifier
107 >>> X = [[0, 0], [1, 1], [1, 0], [0, 1]]
108 >>> y = [0, 0, 1, 1]
109 >>> ps = PolynomialCountSketch(degree=3, random_state=1)
110 >>> X_features = ps.fit_transform(X)
111 >>> clf = SGDClassifier(max_iter=10, tol=1e-3)
112 >>> clf.fit(X_features, y)
113 SGDClassifier(max_iter=10)
114 >>> clf.score(X_features, y)
115 1.0
116
117 For a more detailed example of usage, see
118 :ref:`sphx_glr_auto_examples_kernel_approximation_plot_scalable_poly_kernels.py`
119 """
120
121 _parameter_constraints: dict = {
122 "gamma": [Interval(Real, 0, None, closed="left")],
123 "degree": [Interval(Integral, 1, None, closed="left")],
124 "coef0": [Interval(Real, None, None, closed="neither")],
125 "n_components": [Interval(Integral, 1, None, closed="left")],
126 "random_state": ["random_state"],
127 }
128
129 def __init__(
130 self, *, gamma=1.0, degree=2, coef0=0, n_components=100, random_state=None
131 ):
132 self.gamma = gamma
133 self.degree = degree
134 self.coef0 = coef0
135 self.n_components = n_components
136 self.random_state = random_state
137
138 @_fit_context(prefer_skip_nested_validation=True)
139 def fit(self, X, y=None):
140 """Fit the model with X.
141
142 Initializes the internal variables. The method needs no information
143 about the distribution of data, so we only care about n_features in X.
144
145 Parameters
146 ----------
147 X : {array-like, sparse matrix} of shape (n_samples, n_features)
148 Training data, where `n_samples` is the number of samples
149 and `n_features` is the number of features.
150
151 y : array-like of shape (n_samples,) or (n_samples, n_outputs), \
152 default=None
153 Target values (None for unsupervised transformations).
154
155 Returns
156 -------
157 self : object
158 Returns the instance itself.
159 """
160 X = validate_data(self, X, accept_sparse="csc")
161 random_state = check_random_state(self.random_state)
162
163 n_features = X.shape[1]
164 if self.coef0 != 0:
165 n_features += 1
166
167 self.indexHash_ = random_state.randint(
168 0, high=self.n_components, size=(self.degree, n_features)
169 )
170
171 self.bitHash_ = random_state.choice(a=[-1, 1], size=(self.degree, n_features))
172 self._n_features_out = self.n_components
173 return self
174
175 def transform(self, X):
176 """Generate the feature map approximation for X.
177
178 Parameters
179 ----------
180 X : {array-like}, shape (n_samples, n_features)
181 New data, where `n_samples` is the number of samples
182 and `n_features` is the number of features.
183
184 Returns
185 -------
186 X_new : array-like, shape (n_samples, n_components)
187 Returns the instance itself.
188 """
189
190 check_is_fitted(self)
191 X = validate_data(self, X, accept_sparse="csc", reset=False)
192
193 X_gamma = np.sqrt(self.gamma) * X
194
195 if sp.issparse(X_gamma) and self.coef0 != 0:
196 X_gamma = sp.hstack(
197 [X_gamma, np.sqrt(self.coef0) * np.ones((X_gamma.shape[0], 1))],
198 format="csc",
199 )
200
201 elif not sp.issparse(X_gamma) and self.coef0 != 0:
202 X_gamma = np.hstack(
203 [X_gamma, np.sqrt(self.coef0) * np.ones((X_gamma.shape[0], 1))]
204 )
205
206 if X_gamma.shape[1] != self.indexHash_.shape[1]:
207 raise ValueError(
208 "Number of features of test samples does not"
209 " match that of training samples."
210 )
211
212 count_sketches = np.zeros((X_gamma.shape[0], self.degree, self.n_components))
213
214 if sp.issparse(X_gamma):
215 for j in range(X_gamma.shape[1]):
216 for d in range(self.degree):
217 iHashIndex = self.indexHash_[d, j]
218 iHashBit = self.bitHash_[d, j]
219 count_sketches[:, d, iHashIndex] += (
220 (iHashBit * X_gamma[:, [j]]).toarray().ravel()
221 )
222
223 else:
224 for j in range(X_gamma.shape[1]):
225 for d in range(self.degree):
226 iHashIndex = self.indexHash_[d, j]
227 iHashBit = self.bitHash_[d, j]
228 count_sketches[:, d, iHashIndex] += iHashBit * X_gamma[:, j]
229
230 # For each same, compute a count sketch of phi(x) using the polynomial
231 # multiplication (via FFT) of p count sketches of x.
232 count_sketches_fft = fft(count_sketches, axis=2, overwrite_x=True)
233 count_sketches_fft_prod = np.prod(count_sketches_fft, axis=1)
234 data_sketch = np.real(ifft(count_sketches_fft_prod, overwrite_x=True))
235
236 return data_sketch
237
238 def __sklearn_tags__(self):
239 tags = super().__sklearn_tags__()
240 tags.input_tags.sparse = True
241 return tags
242
243
244class RBFSampler(ClassNamePrefixFeaturesOutMixin, TransformerMixin, BaseEstimator):
245 """Approximate a RBF kernel feature map using random Fourier features.
246
247 It implements a variant of Random Kitchen Sinks.[1]
248
249 Read more in the :ref:`User Guide <rbf_kernel_approx>`.
250
251 Parameters
252 ----------
253 gamma : 'scale' or float, default=1.0
254 Parameter of RBF kernel: exp(-gamma * x^2).
255 If ``gamma='scale'`` is passed then it uses
256 1 / (n_features * X.var()) as value of gamma.
257
258 .. versionadded:: 1.2
259 The option `"scale"` was added in 1.2.
260
261 n_components : int, default=100
262 Number of Monte Carlo samples per original feature.
263 Equals the dimensionality of the computed feature space.
264
265 random_state : int, RandomState instance or None, default=None
266 Pseudo-random number generator to control the generation of the random
267 weights and random offset when fitting the training data.
268 Pass an int for reproducible output across multiple function calls.
269 See :term:`Glossary <random_state>`.
270
271 Attributes
272 ----------
273 random_offset_ : ndarray of shape (n_components,), dtype={np.float64, np.float32}
274 Random offset used to compute the projection in the `n_components`
275 dimensions of the feature space.
276
277 random_weights_ : ndarray of shape (n_features, n_components),\
278 dtype={np.float64, np.float32}
279 Random projection directions drawn from the Fourier transform
280 of the RBF kernel.
281
282 n_features_in_ : int
283 Number of features seen during :term:`fit`.
284
285 .. versionadded:: 0.24
286
287 feature_names_in_ : ndarray of shape (`n_features_in_`,)
288 Names of features seen during :term:`fit`. Defined only when `X`
289 has feature names that are all strings.
290
291 .. versionadded:: 1.0
292
293 See Also
294 --------
295 AdditiveChi2Sampler : Approximate feature map for additive chi2 kernel.
296 Nystroem : Approximate a kernel map using a subset of the training data.
297 PolynomialCountSketch : Polynomial kernel approximation via Tensor Sketch.
298 SkewedChi2Sampler : Approximate feature map for
299 "skewed chi-squared" kernel.
300 sklearn.metrics.pairwise.kernel_metrics : List of built-in kernels.
301
302 Notes
303 -----
304 See "Random Features for Large-Scale Kernel Machines" by A. Rahimi and
305 Benjamin Recht.
306
307 [1] "Weighted Sums of Random Kitchen Sinks: Replacing
308 minimization with randomization in learning" by A. Rahimi and
309 Benjamin Recht.
310 (https://people.eecs.berkeley.edu/~brecht/papers/08.rah.rec.nips.pdf)
311
312 Examples
313 --------
314 >>> from sklearn.kernel_approximation import RBFSampler
315 >>> from sklearn.linear_model import SGDClassifier
316 >>> X = [[0, 0], [1, 1], [1, 0], [0, 1]]
317 >>> y = [0, 0, 1, 1]
318 >>> rbf_feature = RBFSampler(gamma=1, random_state=1)
319 >>> X_features = rbf_feature.fit_transform(X)
320 >>> clf = SGDClassifier(max_iter=5, tol=1e-3)
321 >>> clf.fit(X_features, y)
322 SGDClassifier(max_iter=5)
323 >>> clf.score(X_features, y)
324 1.0
325 """
326
327 _parameter_constraints: dict = {
328 "gamma": [
329 StrOptions({"scale"}),
330 Interval(Real, 0.0, None, closed="left"),
331 ],
332 "n_components": [Interval(Integral, 1, None, closed="left")],
333 "random_state": ["random_state"],
334 }
335
336 def __init__(self, *, gamma=1.0, n_components=100, random_state=None):
337 self.gamma = gamma
338 self.n_components = n_components
339 self.random_state = random_state
340
341 @_fit_context(prefer_skip_nested_validation=True)
342 def fit(self, X, y=None):
343 """Fit the model with X.
344
345 Samples random projection according to n_features.
346
347 Parameters
348 ----------
349 X : {array-like, sparse matrix}, shape (n_samples, n_features)
350 Training data, where `n_samples` is the number of samples
351 and `n_features` is the number of features.
352
353 y : array-like, shape (n_samples,) or (n_samples, n_outputs), \
354 default=None
355 Target values (None for unsupervised transformations).
356
357 Returns
358 -------
359 self : object
360 Returns the instance itself.
361 """
362 X = validate_data(self, X, accept_sparse="csr")
363 random_state = check_random_state(self.random_state)
364 n_features = X.shape[1]
365 sparse = sp.issparse(X)
366 if self.gamma == "scale":
367 # var = E[X^2] - E[X]^2 if sparse
368 X_var = (X.multiply(X)).mean() - (X.mean()) ** 2 if sparse else X.var()
369 self._gamma = 1.0 / (n_features * X_var) if X_var != 0 else 1.0
370 else:
371 self._gamma = self.gamma
372 self.random_weights_ = (2.0 * self._gamma) ** 0.5 * random_state.normal(
373 size=(n_features, self.n_components)
374 )
375
376 self.random_offset_ = random_state.uniform(0, 2 * np.pi, size=self.n_components)
377
378 if X.dtype == np.float32:
379 # Setting the data type of the fitted attribute will ensure the
380 # output data type during `transform`.
381 self.random_weights_ = self.random_weights_.astype(X.dtype, copy=False)
382 self.random_offset_ = self.random_offset_.astype(X.dtype, copy=False)
383
384 self._n_features_out = self.n_components
385 return self
386
387 def transform(self, X):
388 """Apply the approximate feature map to X.
389
390 Parameters
391 ----------
392 X : {array-like, sparse matrix}, shape (n_samples, n_features)
393 New data, where `n_samples` is the number of samples
394 and `n_features` is the number of features.
395
396 Returns
397 -------
398 X_new : array-like, shape (n_samples, n_components)
399 Returns the instance itself.
400 """
401 check_is_fitted(self)
402
403 X = validate_data(self, X, accept_sparse="csr", reset=False)
404 projection = safe_sparse_dot(X, self.random_weights_)
405 projection += self.random_offset_
406 np.cos(projection, projection)
407 projection *= (2.0 / self.n_components) ** 0.5
408 return projection
409
410 def __sklearn_tags__(self):
411 tags = super().__sklearn_tags__()
412 tags.input_tags.sparse = True
413 tags.transformer_tags.preserves_dtype = ["float64", "float32"]
414 return tags
415
416
417class SkewedChi2Sampler(
418 ClassNamePrefixFeaturesOutMixin, TransformerMixin, BaseEstimator
419):
420 """Approximate feature map for "skewed chi-squared" kernel.
421
422 Read more in the :ref:`User Guide <skewed_chi_kernel_approx>`.
423
424 Parameters
425 ----------
426 skewedness : float, default=1.0
427 "skewedness" parameter of the kernel. Needs to be cross-validated.
428
429 n_components : int, default=100
430 Number of Monte Carlo samples per original feature.
431 Equals the dimensionality of the computed feature space.
432
433 random_state : int, RandomState instance or None, default=None
434 Pseudo-random number generator to control the generation of the random
435 weights and random offset when fitting the training data.
436 Pass an int for reproducible output across multiple function calls.
437 See :term:`Glossary <random_state>`.
438
439 Attributes
440 ----------
441 random_weights_ : ndarray of shape (n_features, n_components)
442 Weight array, sampled from a secant hyperbolic distribution, which will
443 be used to linearly transform the log of the data.
444
445 random_offset_ : ndarray of shape (n_features, n_components)
446 Bias term, which will be added to the data. It is uniformly distributed
447 between 0 and 2*pi.
448
449 n_features_in_ : int
450 Number of features seen during :term:`fit`.
451
452 .. versionadded:: 0.24
453
454 feature_names_in_ : ndarray of shape (`n_features_in_`,)
455 Names of features seen during :term:`fit`. Defined only when `X`
456 has feature names that are all strings.
457
458 .. versionadded:: 1.0
459
460 See Also
461 --------
462 AdditiveChi2Sampler : Approximate feature map for additive chi2 kernel.
463 Nystroem : Approximate a kernel map using a subset of the training data.
464 RBFSampler : Approximate a RBF kernel feature map using random Fourier
465 features.
466 SkewedChi2Sampler : Approximate feature map for "skewed chi-squared" kernel.
467 sklearn.metrics.pairwise.chi2_kernel : The exact chi squared kernel.
468 sklearn.metrics.pairwise.kernel_metrics : List of built-in kernels.
469
470 References
471 ----------
472 See "Random Fourier Approximations for Skewed Multiplicative Histogram
473 Kernels" by Fuxin Li, Catalin Ionescu and Cristian Sminchisescu.
474
475 Examples
476 --------
477 >>> from sklearn.kernel_approximation import SkewedChi2Sampler
478 >>> from sklearn.linear_model import SGDClassifier
479 >>> X = [[0, 0], [1, 1], [1, 0], [0, 1]]
480 >>> y = [0, 0, 1, 1]
481 >>> chi2_feature = SkewedChi2Sampler(skewedness=.01,
482 ... n_components=10,
483 ... random_state=0)
484 >>> X_features = chi2_feature.fit_transform(X, y)
485 >>> clf = SGDClassifier(max_iter=10, tol=1e-3)
486 >>> clf.fit(X_features, y)
487 SGDClassifier(max_iter=10)
488 >>> clf.score(X_features, y)
489 1.0
490 """
491
492 _parameter_constraints: dict = {
493 "skewedness": [Interval(Real, None, None, closed="neither")],
494 "n_components": [Interval(Integral, 1, None, closed="left")],
495 "random_state": ["random_state"],
496 }
497
498 def __init__(self, *, skewedness=1.0, n_components=100, random_state=None):
499 self.skewedness = skewedness
500 self.n_components = n_components
501 self.random_state = random_state
502
503 @_fit_context(prefer_skip_nested_validation=True)
504 def fit(self, X, y=None):
505 """Fit the model with X.
506
507 Samples random projection according to n_features.
508
509 Parameters
510 ----------
511 X : array-like, shape (n_samples, n_features)
512 Training data, where `n_samples` is the number of samples
513 and `n_features` is the number of features.
514
515 y : array-like, shape (n_samples,) or (n_samples, n_outputs), \
516 default=None
517 Target values (None for unsupervised transformations).
518
519 Returns
520 -------
521 self : object
522 Returns the instance itself.
523 """
524 X = validate_data(self, X)
525 random_state = check_random_state(self.random_state)
526 n_features = X.shape[1]
527 uniform = random_state.uniform(size=(n_features, self.n_components))
528 # transform by inverse CDF of sech
529 self.random_weights_ = 1.0 / np.pi * np.log(np.tan(np.pi / 2.0 * uniform))
530 self.random_offset_ = random_state.uniform(0, 2 * np.pi, size=self.n_components)
531
532 if X.dtype == np.float32:
533 # Setting the data type of the fitted attribute will ensure the
534 # output data type during `transform`.
535 self.random_weights_ = self.random_weights_.astype(X.dtype, copy=False)
536 self.random_offset_ = self.random_offset_.astype(X.dtype, copy=False)
537
538 self._n_features_out = self.n_components
539 return self
540
541 def transform(self, X):
542 """Apply the approximate feature map to X.
543
544 Parameters
545 ----------
546 X : array-like, shape (n_samples, n_features)
547 New data, where `n_samples` is the number of samples
548 and `n_features` is the number of features. All values of X must be
549 strictly greater than "-skewedness".
550
551 Returns
552 -------
553 X_new : array-like, shape (n_samples, n_components)
554 Returns the instance itself.
555 """
556 check_is_fitted(self)
557 X = validate_data(
558 self, X, copy=True, dtype=[np.float64, np.float32], reset=False
559 )
560 if (X <= -self.skewedness).any():
561 raise ValueError("X may not contain entries smaller than -skewedness.")
562
563 X += self.skewedness
564 np.log(X, X)
565 projection = safe_sparse_dot(X, self.random_weights_)
566 projection += self.random_offset_
567 np.cos(projection, projection)
568 projection *= np.sqrt(2.0) / np.sqrt(self.n_components)
569 return projection
570
571 def __sklearn_tags__(self):
572 tags = super().__sklearn_tags__()
573 tags.transformer_tags.preserves_dtype = ["float64", "float32"]
574 return tags
575
576
577class AdditiveChi2Sampler(TransformerMixin, BaseEstimator):
578 """Approximate feature map for additive chi2 kernel.
579
580 Uses sampling the fourier transform of the kernel characteristic
581 at regular intervals.
582
583 Since the kernel that is to be approximated is additive, the components of
584 the input vectors can be treated separately. Each entry in the original
585 space is transformed into 2*sample_steps-1 features, where sample_steps is
586 a parameter of the method. Typical values of sample_steps include 1, 2 and
587 3.
588
589 Optimal choices for the sampling interval for certain data ranges can be
590 computed (see the reference). The default values should be reasonable.
591
592 Read more in the :ref:`User Guide <additive_chi_kernel_approx>`.
593
594 Parameters
595 ----------
596 sample_steps : int, default=2
597 Gives the number of (complex) sampling points.
598
599 sample_interval : float, default=None
600 Sampling interval. Must be specified when sample_steps not in {1,2,3}.
601
602 Attributes
603 ----------
604 n_features_in_ : int
605 Number of features seen during :term:`fit`.
606
607 .. versionadded:: 0.24
608
609 feature_names_in_ : ndarray of shape (`n_features_in_`,)
610 Names of features seen during :term:`fit`. Defined only when `X`
611 has feature names that are all strings.
612
613 .. versionadded:: 1.0
614
615 See Also
616 --------
617 SkewedChi2Sampler : A Fourier-approximation to a non-additive variant of
618 the chi squared kernel.
619
620 sklearn.metrics.pairwise.chi2_kernel : The exact chi squared kernel.
621
622 sklearn.metrics.pairwise.additive_chi2_kernel : The exact additive chi
623 squared kernel.
624
625 Notes
626 -----
627 This estimator approximates a slightly different version of the additive
628 chi squared kernel then ``metric.additive_chi2`` computes.
629
630 This estimator is stateless and does not need to be fitted. However, we
631 recommend to call :meth:`fit_transform` instead of :meth:`transform`, as
632 parameter validation is only performed in :meth:`fit`.
633
634 References
635 ----------
636 See `"Efficient additive kernels via explicit feature maps"
637 <http://www.robots.ox.ac.uk/~vedaldi/assets/pubs/vedaldi11efficient.pdf>`_
638 A. Vedaldi and A. Zisserman, Pattern Analysis and Machine Intelligence,
639 2011
640
641 Examples
642 --------
643 >>> from sklearn.datasets import load_digits
644 >>> from sklearn.linear_model import SGDClassifier
645 >>> from sklearn.kernel_approximation import AdditiveChi2Sampler
646 >>> X, y = load_digits(return_X_y=True)
647 >>> chi2sampler = AdditiveChi2Sampler(sample_steps=2)
648 >>> X_transformed = chi2sampler.fit_transform(X, y)
649 >>> clf = SGDClassifier(max_iter=5, random_state=0, tol=1e-3)
650 >>> clf.fit(X_transformed, y)
651 SGDClassifier(max_iter=5, random_state=0)
652 >>> clf.score(X_transformed, y)
653 0.9499...
654 """
655
656 _parameter_constraints: dict = {
657 "sample_steps": [Interval(Integral, 1, None, closed="left")],
658 "sample_interval": [Interval(Real, 0, None, closed="left"), None],
659 }
660
661 def __init__(self, *, sample_steps=2, sample_interval=None):
662 self.sample_steps = sample_steps
663 self.sample_interval = sample_interval
664
665 @_fit_context(prefer_skip_nested_validation=True)
666 def fit(self, X, y=None):
667 """Only validates estimator's parameters.
668
669 This method allows to: (i) validate the estimator's parameters and
670 (ii) be consistent with the scikit-learn transformer API.
671
672 Parameters
673 ----------
674 X : array-like, shape (n_samples, n_features)
675 Training data, where `n_samples` is the number of samples
676 and `n_features` is the number of features.
677
678 y : array-like, shape (n_samples,) or (n_samples, n_outputs), \
679 default=None
680 Target values (None for unsupervised transformations).
681
682 Returns
683 -------
684 self : object
685 Returns the transformer.
686 """
687 X = validate_data(self, X, accept_sparse="csr", ensure_non_negative=True)
688
689 if self.sample_interval is None and self.sample_steps not in (1, 2, 3):
690 raise ValueError(
691 "If sample_steps is not in [1, 2, 3],"
692 " you need to provide sample_interval"
693 )
694
695 return self
696
697 def transform(self, X):
698 """Apply approximate feature map to X.
699
700 Parameters
701 ----------
702 X : {array-like, sparse matrix}, shape (n_samples, n_features)
703 Training data, where `n_samples` is the number of samples
704 and `n_features` is the number of features.
705
706 Returns
707 -------
708 X_new : {ndarray, sparse matrix}, \
709 shape = (n_samples, n_features * (2*sample_steps - 1))
710 Whether the return value is an array or sparse matrix depends on
711 the type of the input X.
712 """
713 X = validate_data(
714 self, X, accept_sparse="csr", reset=False, ensure_non_negative=True
715 )
716 sparse = sp.issparse(X)
717
718 if self.sample_interval is None:
719 # See figure 2 c) of "Efficient additive kernels via explicit feature maps"
720 # <http://www.robots.ox.ac.uk/~vedaldi/assets/pubs/vedaldi11efficient.pdf>
721 # A. Vedaldi and A. Zisserman, Pattern Analysis and Machine Intelligence,
722 # 2011
723 if self.sample_steps == 1:
724 sample_interval = 0.8
725 elif self.sample_steps == 2:
726 sample_interval = 0.5
727 elif self.sample_steps == 3:
728 sample_interval = 0.4
729 else:
730 raise ValueError(
731 "If sample_steps is not in [1, 2, 3],"
732 " you need to provide sample_interval"
733 )
734 else:
735 sample_interval = self.sample_interval
736
737 # zeroth component
738 # 1/cosh = sech
739 # cosh(0) = 1.0
740 transf = self._transform_sparse if sparse else self._transform_dense
741 return transf(X, self.sample_steps, sample_interval)
742
743 def get_feature_names_out(self, input_features=None):
744 """Get output feature names for transformation.
745
746 Parameters
747 ----------
748 input_features : array-like of str or None, default=None
749 Only used to validate feature names with the names seen in :meth:`fit`.
750
751 Returns
752 -------
753 feature_names_out : ndarray of str objects
754 Transformed feature names.
755 """
756 # Note that passing attributes="n_features_in_" forces check_is_fitted
757 # to check if the attribute is present. Otherwise it will pass on this
758 # stateless estimator (requires_fit=False)
759 check_is_fitted(self, attributes="n_features_in_")
760 input_features = _check_feature_names_in(
761 self, input_features, generate_names=True
762 )
763 est_name = self.__class__.__name__.lower()
764
765 names_list = [f"{est_name}_{name}_sqrt" for name in input_features]
766
767 for j in range(1, self.sample_steps):
768 cos_names = [f"{est_name}_{name}_cos{j}" for name in input_features]
769 sin_names = [f"{est_name}_{name}_sin{j}" for name in input_features]
770 names_list.extend(cos_names + sin_names)
771
772 return np.asarray(names_list, dtype=object)
773
774 @staticmethod
775 def _transform_dense(X, sample_steps, sample_interval):
776 non_zero = X != 0.0
777 X_nz = X[non_zero]
778
779 X_step = np.zeros_like(X)
780 X_step[non_zero] = np.sqrt(X_nz * sample_interval)
781
782 X_new = [X_step]
783
784 log_step_nz = sample_interval * np.log(X_nz)
785 step_nz = 2 * X_nz * sample_interval
786
787 for j in range(1, sample_steps):
788 factor_nz = np.sqrt(step_nz / np.cosh(np.pi * j * sample_interval))
789
790 X_step = np.zeros_like(X)
791 X_step[non_zero] = factor_nz * np.cos(j * log_step_nz)
792 X_new.append(X_step)
793
794 X_step = np.zeros_like(X)
795 X_step[non_zero] = factor_nz * np.sin(j * log_step_nz)
796 X_new.append(X_step)
797
798 return np.hstack(X_new)
799
800 @staticmethod
801 def _transform_sparse(X, sample_steps, sample_interval):
802 indices = X.indices.copy()
803 indptr = X.indptr.copy()
804
805 data_step = np.sqrt(X.data * sample_interval)
806 X_step = sp.csr_matrix(
807 (data_step, indices, indptr), shape=X.shape, dtype=X.dtype, copy=False
808 )
809 X_new = [X_step]
810
811 log_step_nz = sample_interval * np.log(X.data)
812 step_nz = 2 * X.data * sample_interval
813
814 for j in range(1, sample_steps):
815 factor_nz = np.sqrt(step_nz / np.cosh(np.pi * j * sample_interval))
816
817 data_step = factor_nz * np.cos(j * log_step_nz)
818 X_step = sp.csr_matrix(
819 (data_step, indices, indptr), shape=X.shape, dtype=X.dtype, copy=False
820 )
821 X_new.append(X_step)
822
823 data_step = factor_nz * np.sin(j * log_step_nz)
824 X_step = sp.csr_matrix(
825 (data_step, indices, indptr), shape=X.shape, dtype=X.dtype, copy=False
826 )
827 X_new.append(X_step)
828
829 return sp.hstack(X_new)
830
831 def __sklearn_tags__(self):
832 tags = super().__sklearn_tags__()
833 tags.requires_fit = False
834 tags.input_tags.positive_only = True
835 tags.input_tags.sparse = True
836 return tags
837
838
839class Nystroem(ClassNamePrefixFeaturesOutMixin, TransformerMixin, BaseEstimator):
840 """Approximate a kernel map using a subset of the training data.
841
842 Constructs an approximate feature map for an arbitrary kernel
843 using a subset of the data as basis.
844
845 Read more in the :ref:`User Guide <nystroem_kernel_approx>`.
846
847 .. versionadded:: 0.13
848
849 Parameters
850 ----------
851 kernel : str or callable, default='rbf'
852 Kernel map to be approximated. A callable should accept two arguments
853 and the keyword arguments passed to this object as `kernel_params`, and
854 should return a floating point number.
855
856 gamma : float, default=None
857 Gamma parameter for the RBF, laplacian, polynomial, exponential chi2
858 and sigmoid kernels. Interpretation of the default value is left to
859 the kernel; see the documentation for sklearn.metrics.pairwise.
860 Ignored by other kernels.
861
862 coef0 : float, default=None
863 Zero coefficient for polynomial and sigmoid kernels.
864 Ignored by other kernels.
865
866 degree : float, default=None
867 Degree of the polynomial kernel. Ignored by other kernels.
868
869 kernel_params : dict, default=None
870 Additional parameters (keyword arguments) for kernel function passed
871 as callable object.
872
873 n_components : int, default=100
874 Number of features to construct.
875 How many data points will be used to construct the mapping.
876
877 random_state : int, RandomState instance or None, default=None
878 Pseudo-random number generator to control the uniform sampling without
879 replacement of `n_components` of the training data to construct the
880 basis kernel.
881 Pass an int for reproducible output across multiple function calls.
882 See :term:`Glossary <random_state>`.
883
884 n_jobs : int, default=None
885 The number of jobs to use for the computation. This works by breaking
886 down the kernel matrix into `n_jobs` even slices and computing them in
887 parallel.
888
889 ``None`` means 1 unless in a :obj:`joblib.parallel_backend` context.
890 ``-1`` means using all processors. See :term:`Glossary <n_jobs>`
891 for more details.
892
893 .. versionadded:: 0.24
894
895 Attributes
896 ----------
897 components_ : ndarray of shape (n_components, n_features)
898 Subset of training points used to construct the feature map.
899
900 component_indices_ : ndarray of shape (n_components)
901 Indices of ``components_`` in the training set.
902
903 normalization_ : ndarray of shape (n_components, n_components)
904 Normalization matrix needed for embedding.
905 Square root of the kernel matrix on ``components_``.
906
907 n_features_in_ : int
908 Number of features seen during :term:`fit`.
909
910 .. versionadded:: 0.24
911
912 feature_names_in_ : ndarray of shape (`n_features_in_`,)
913 Names of features seen during :term:`fit`. Defined only when `X`
914 has feature names that are all strings.
915
916 .. versionadded:: 1.0
917
918 See Also
919 --------
920 AdditiveChi2Sampler : Approximate feature map for additive chi2 kernel.
921 PolynomialCountSketch : Polynomial kernel approximation via Tensor Sketch.
922 RBFSampler : Approximate a RBF kernel feature map using random Fourier
923 features.
924 SkewedChi2Sampler : Approximate feature map for "skewed chi-squared" kernel.
925 sklearn.metrics.pairwise.kernel_metrics : List of built-in kernels.
926
927 References
928 ----------
929 * Williams, C.K.I. and Seeger, M.
930 "Using the Nystroem method to speed up kernel machines",
931 Advances in neural information processing systems 2001
932
933 * T. Yang, Y. Li, M. Mahdavi, R. Jin and Z. Zhou
934 "Nystroem Method vs Random Fourier Features: A Theoretical and Empirical
935 Comparison",
936 Advances in Neural Information Processing Systems 2012
937
938 Examples
939 --------
940 >>> from sklearn import datasets, svm
941 >>> from sklearn.kernel_approximation import Nystroem
942 >>> X, y = datasets.load_digits(n_class=9, return_X_y=True)
943 >>> data = X / 16.
944 >>> clf = svm.LinearSVC()
945 >>> feature_map_nystroem = Nystroem(gamma=.2,
946 ... random_state=1,
947 ... n_components=300)
948 >>> data_transformed = feature_map_nystroem.fit_transform(data)
949 >>> clf.fit(data_transformed, y)
950 LinearSVC()
951 >>> clf.score(data_transformed, y)
952 0.9987...
953 """
954
955 _parameter_constraints: dict = {
956 "kernel": [
957 StrOptions(set(PAIRWISE_KERNEL_FUNCTIONS.keys()) | {"precomputed"}),
958 callable,
959 ],
960 "gamma": [Interval(Real, 0, None, closed="left"), None],
961 "coef0": [Interval(Real, None, None, closed="neither"), None],
962 "degree": [Interval(Real, 1, None, closed="left"), None],
963 "kernel_params": [dict, None],
964 "n_components": [Interval(Integral, 1, None, closed="left")],
965 "random_state": ["random_state"],
966 "n_jobs": [Integral, None],
967 }
968
969 def __init__(
970 self,
971 kernel="rbf",
972 *,
973 gamma=None,
974 coef0=None,
975 degree=None,
976 kernel_params=None,
977 n_components=100,
978 random_state=None,
979 n_jobs=None,
980 ):
981 self.kernel = kernel
982 self.gamma = gamma
983 self.coef0 = coef0
984 self.degree = degree
985 self.kernel_params = kernel_params
986 self.n_components = n_components
987 self.random_state = random_state
988 self.n_jobs = n_jobs
989
990 @_fit_context(prefer_skip_nested_validation=True)
991 def fit(self, X, y=None):
992 """Fit estimator to data.
993
994 Samples a subset of training points, computes kernel
995 on these and computes normalization matrix.
996
997 Parameters
998 ----------
999 X : array-like, shape (n_samples, n_features)
1000 Training data, where `n_samples` is the number of samples
1001 and `n_features` is the number of features.
1002
1003 y : array-like, shape (n_samples,) or (n_samples, n_outputs), \
1004 default=None
1005 Target values (None for unsupervised transformations).
1006
1007 Returns
1008 -------
1009 self : object
1010 Returns the instance itself.
1011 """
1012 X = validate_data(self, X, accept_sparse="csr")
1013 rnd = check_random_state(self.random_state)
1014 n_samples = X.shape[0]
1015
1016 # get basis vectors
1017 if self.n_components > n_samples:
1018 # XXX should we just bail?
1019 n_components = n_samples
1020 warnings.warn(
1021 "n_components > n_samples. This is not possible.\n"
1022 "n_components was set to n_samples, which results"
1023 " in inefficient evaluation of the full kernel."
1024 )
1025
1026 else:
1027 n_components = self.n_components
1028 n_components = min(n_samples, n_components)
1029 inds = rnd.permutation(n_samples)
1030 basis_inds = inds[:n_components]
1031 basis = X[basis_inds]
1032
1033 basis_kernel = pairwise_kernels(
1034 basis,
1035 metric=self.kernel,
1036 filter_params=True,
1037 n_jobs=self.n_jobs,
1038 **self._get_kernel_params(),
1039 )
1040
1041 # sqrt of kernel matrix on basis vectors
1042 U, S, V = svd(basis_kernel)
1043 S = np.maximum(S, 1e-12)
1044 self.normalization_ = np.dot(U / np.sqrt(S), V)
1045 self.components_ = basis
1046 self.component_indices_ = basis_inds
1047 self._n_features_out = n_components
1048 return self
1049
1050 def transform(self, X):
1051 """Apply feature map to X.
1052
1053 Computes an approximate feature map using the kernel
1054 between some training points and X.
1055
1056 Parameters
1057 ----------
1058 X : array-like of shape (n_samples, n_features)
1059 Data to transform.
1060
1061 Returns
1062 -------
1063 X_transformed : ndarray of shape (n_samples, n_components)
1064 Transformed data.
1065 """
1066 check_is_fitted(self)
1067 X = validate_data(self, X, accept_sparse="csr", reset=False)
1068
1069 kernel_params = self._get_kernel_params()
1070 embedded = pairwise_kernels(
1071 X,
1072 self.components_,
1073 metric=self.kernel,
1074 filter_params=True,
1075 n_jobs=self.n_jobs,
1076 **kernel_params,
1077 )
1078 return np.dot(embedded, self.normalization_.T)
1079
1080 def _get_kernel_params(self):
1081 params = self.kernel_params
1082 if params is None:
1083 params = {}
1084 if not callable(self.kernel) and self.kernel != "precomputed":
1085 for param in KERNEL_PARAMS[self.kernel]:
1086 if getattr(self, param) is not None:
1087 params[param] = getattr(self, param)
1088 else:
1089 if (
1090 self.gamma is not None
1091 or self.coef0 is not None
1092 or self.degree is not None
1093 ):
1094 raise ValueError(
1095 "Don't pass gamma, coef0 or degree to "
1096 "Nystroem if using a callable "
1097 "or precomputed kernel"
1098 )
1099
1100 return params
1101
1102 def __sklearn_tags__(self):
1103 tags = super().__sklearn_tags__()
1104 tags.input_tags.sparse = True
1105 tags.transformer_tags.preserves_dtype = ["float64", "float32"]
1106 return tags
1107