Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

High-Dimensional Data and the Curse of Dimensionality

Mahmood Amintoosi, Fall 2026

Computer Science Dept, Ferdowsi University of Mashhad

The geometric facts on this page are those of The Elements of Statistical Learning (Hastie et al. (2009)), §2.5, and chapter 6 of Zaki’s Data Mining and Machine Learning (Zaki & Meira (2020)).

Learning objectives. By the end you should be able to

  1. compute the volume of a ball and of a cube in dd dimensions and explain why their ratio tends to zero;

  2. explain why a neighbourhood containing a fixed fraction of the data is not local in high dimensions, and compute its edge length ed(r)=r1/de_d(r) = r^{1/d};

  3. show that in high dimension the nearest and the farthest neighbour are almost equally far away, and say what that does to k-NN;

  4. explain why most of the volume of a ball is in a thin shell, and why Gaussian samples concentrate at radius d\sqrt{d};

  5. sample points uniformly inside a ball and on its surface (why the naive radius is wrong);

  6. measure the effect of the dimension on a k-NN classifier, with and without more data.

English · فارسی
English · فارسی

Introduction

In modern data mining and machine learning we often deal with data in very high-dimensional spaces (images, text embeddings, genomic data). A dataset is typically represented as an n×dn \times d matrix D\mathbf{D}: nn points, dd features.

High-dimensional space, or hyperspace, does not behave like the geometry of two or three dimensions. The collection of effects that follow from this is called the curse of dimensionality. The five phenomena we look at are:

  1. Volume concentration: the volume of a hypersphere vanishes relative to the hypercube that contains it.

  2. The problem of local neighborhoods: a “local” neighbourhood of a fixed fraction of the data is not local any more, so methods such as k-NN lose their meaning (ESL §2.5).

  3. Distance concentration: the nearest and the farthest neighbour are almost at the same distance, so ranking neighbours becomes meaningless.

  4. The thin shell: almost all of the volume of a ball sits near its surface.

  5. Orthogonality and Gaussian behaviour: random vectors are nearly orthogonal, and Gaussian samples concentrate in a thin shell at radius d\sqrt{d}.

Throughout, dd is the number of dimensions. The figures taken from ESL label it pp; the text here uses dd consistently.

<Figure size 900x500 with 1 Axes>
d =  1:  ball volume = 2.000e+00   ratio ball/cube = 1.000e+00
d =  2:  ball volume = 3.142e+00   ratio ball/cube = 7.854e-01
d =  3:  ball volume = 4.189e+00   ratio ball/cube = 5.236e-01
d = 10:  ball volume = 2.550e+00   ratio ball/cube = 2.490e-03
d = 20:  ball volume = 2.581e-02   ratio ball/cube = 2.461e-08

Geometry of Hyperspace: Cubes and Balls

The Hypercube

The data space is often taken as a dd-dimensional hypercube. For a hypercube Hd(l)H_d(l) of side length ll the volume is simply

Vol⁡(Hd(l))=ld.\operatorname{Vol}\big(H_d(l)\big) = l^d .

The Ball and the Sphere

Two different objects are needed, and confusing them is a classic source of errors:

  • the ball Bd(r)={x:∥x∥≤r}B_d(r) = \{\mathbf{x} : \|\mathbf{x}\| \le r\} is the solid; its volume is

Vol⁡(Bd(r))=Kd rd,Kd=πd/2Γ ⁣(d2+1);\operatorname{Vol}\big(B_d(r)\big) = K_d\, r^d, \qquad K_d = \frac{\pi^{d/2}}{\Gamma\!\left(\frac{d}{2}+1\right)} ;
  • the sphere Sd−1(r)={x:∥x∥=r}S^{d-1}(r) = \{\mathbf{x} : \|\mathbf{x}\| = r\} is only the surface — a set of measure zero — and is written with d−1d-1 because it is a (d−1)(d-1)-dimensional object living in Rd\mathbb{R}^d. Its area is dKdrd−1d K_d r^{d-1}, the derivative of the volume with respect to rr.

Γ\Gamma is the Gamma function; for integer arguments Γ(m)=(m−1)!\Gamma(m) = (m-1)!.

Figure 6.4. A hypersphere inscribed in a hypercube: (a) two and (b) three dimensions (Zaki, ch. 6).

The Empty Center (the “Porcupine” Effect)

Take the largest ball that fits inside a cube of side l=2rl = 2r, that is Bd(r)B_d(r). The ratio of their volumes is

Vol⁡(Bd(r))Vol⁡(Hd(2r))=πd/22d Γ ⁣(d2+1)  →d→∞  0.\frac{\operatorname{Vol}\big(B_d(r)\big)}{\operatorname{Vol}\big(H_d(2r)\big)} = \frac{\pi^{d/2}}{2^d\,\Gamma\!\left(\frac{d}{2}+1\right)} \;\xrightarrow[d \to \infty]{}\; 0 .

Implication. As the dimension grows, the ball becomes negligible compared with the cube: almost all of the volume of the cube is in its corners, and the center is essentially empty. In dd dimensions there are 2d2^d corners.

Corners in High Dimension

Conceptual view of high-dimensional space: (a) two, (b) three, (c) four and (d) higher dimensions. In dd dimensions there are 2d2^d corners; the radius of the inscribed ball is what makes the difference between the volume of the cube and of the ball visible (Zaki, ch. 6).

The Problem of Local Neighborhoods

One of the most consequential manifestations of the curse of dimensionality is that “local” methods such as k-nearest neighbours stop being local.

The Edge Length of a Neighborhood

Suppose the inputs are uniformly distributed in the unit hypercube [0,1]d[0,1]^d and we want a neighbourhood that contains a fraction rr of the observations. That neighbourhood must cover a fraction rr of the volume, and if it is a subcube of edge length ed(r)e_d(r) then

(ed(r))d=r⟹ed(r)=r1/d.\big(e_d(r)\big)^d = r \qquad\Longrightarrow\qquad e_d(r) = r^{1/d} .

Figure 2.6 (ESL). The side length of the subcube needed to capture a fraction rr of the volume of the data, for different dimensions pp (the figure labels the dimension pp; here it is dd). In ten dimensions we must cover 80% of the range of each coordinate to capture 10% of the data.

<Figure size 700x500 with 1 Axes>

Analysis. With d=10d = 10 and r=0.1r = 0.1 we need e10(0.1)=0.10.1≈0.80e_{10}(0.1) = 0.1^{0.1} \approx 0.80: to capture 10% of the data we must cover 80% of the range of every coordinate. Such a neighbourhood is not local in any useful sense — it is most of the space.

Distance to the Boundary

Sampling density is sparse for a second reason. For NN points drawn uniformly in the unit ball Bd(1)B_d(1), the median distance from the origin to the closest data point is

d(d,N)=(1−(12)1/N)1/d.d(d, N) = \left(1 - \left(\tfrac{1}{2}\right)^{1/N}\right)^{1/d} .

Where the formula comes from. The probability that a single uniform point falls in the ball of radius tt is tdt^d, so the probability that it falls outside is 1−td1 - t^d, and the probability that all NN points fall outside is (1−td)N(1 - t^d)^N. The median of the distance to the closest point is the tt for which that probability equals 1/21/2:

(1−td)N=12  ⟹  t=(1−(12)1/N)1/d.(1 - t^d)^N = \tfrac{1}{2} \;\Longrightarrow\; t = \left(1 - \left(\tfrac{1}{2}\right)^{1/N}\right)^{1/d} .

For N=500N = 500 and d=10d = 10 this gives ≈0.52\approx 0.52: more than halfway to the boundary. Hence most data points are closer to the boundary of the sample space than to any other data point, and prediction is a problem of extrapolation rather than of interpolation.

Distance Concentration

The phenomenon that hurts k-NN most directly is not the edge length but the distances themselves. For a query point, let dmin⁡d_{\min} be the distance to its nearest neighbour and dmax⁡d_{\max} the distance to the farthest point of the sample. In one dimension the ratio dmin⁡/dmax⁡d_{\min}/d_{\max} is small: there is a genuinely close point. In high dimensions the ratio tends to 1: the closest point is almost as far as the farthest one, so “nearest” is a statement about noise rather than about similarity.

The experiment below draws nn points uniformly in the unit cube for d=2,10,100,1000d = 2, 10, 100, 1000, takes one random query point, and reports the mean ratio dmin⁡/dmax⁡d_{\min}/d_{\max} over many queries.

<Figure size 700x400 with 1 Axes>
d =    2:  mean d_min/d_max = 0.016
d =   10:  mean d_min/d_max = 0.269
d =  100:  mean d_min/d_max = 0.700
d = 1000:  mean d_min/d_max = 0.893

Read the numbers: in two dimensions the nearest neighbour is typically a small fraction of the farthest distance, so ranking neighbours is informative. In a thousand dimensions the ratio is close to 1 — every point is almost equidistant from every other point. Two consequences:

  • The neighbour ranking is dominated by noise: which point is “nearest” changes with tiny perturbations of the data, so a k-NN vote is unstable.

  • A ball around the query that contains kk neighbours is so large that it contains a good part of the data, so the “local” average is not local.

This is the theoretical reason behind the experiment at the end of this page.

The Thin Shell Argument

Where is the volume inside a ball? Consider a thin shell of width ϵ\epsilon just inside the surface of a ball of radius rr. Its volume is

Vol⁡(Bd(r))−Vol⁡(Bd(r−ϵ))=Kd(rd−(r−ϵ)d),\operatorname{Vol}\big(B_d(r)\big) - \operatorname{Vol}\big(B_d(r-\epsilon)\big) = K_d\left(r^d - (r-\epsilon)^d\right),

so the fraction of the volume in the shell is

Vol⁡(shell)Vol⁡(Bd(r))=1−(1−ϵr)d  →d→∞  1.\frac{\operatorname{Vol}(\text{shell})}{\operatorname{Vol}\big(B_d(r)\big)} = 1 - \left(1 - \frac{\epsilon}{r}\right)^{d} \;\xrightarrow[d\to\infty]{}\; 1 .

Figure 6.6 (Zaki, ch. 6): the shell of a ball concentrates the volume as dd grows.

For a disk (d=2d=2) with r=1r=1 and ϵ=0.01\epsilon=0.01 the shell holds 1−0.992≈2%1-0.99^2 \approx 2\% of the area. For d=100d=100 the same shell holds 1−0.99100≈0.631-0.99^{100} \approx 0.63 — almost two thirds.

Conclusion. In high dimensions, for a shell of fixed relative thickness ϵ/r\epsilon/r, almost 100% of the volume — and of the probability mass of a uniform distribution — is concentrated near the surface. The interior is essentially empty.

<Figure size 900x500 with 1 Axes>
d =  2:  shell fraction = 0.360
d = 10:  shell fraction = 0.893
d = 30:  shell fraction = 0.999

Aside: Sampling Points Uniformly in a Ball

Generating points uniformly inside a ball in high dimensions is a good illustration of the volume facts above, and it is needed by many simulation experiments.

Rejection sampling — generate points uniformly in the cube and keep those inside the ball — has an acceptance rate equal to the ratio of the two volumes, which goes to zero (the porcupine effect). Beyond about ten dimensions it is computationally useless. The table below measures the acceptance rate for d=2,…,10d = 2, \dots, 10 with 2000 accepted points, and compares it with the theoretical value Kd/2dK_d/2^d.

<Figure size 800x500 with 1 Axes>
d =  2:  measured = 0.8003   theory = 0.7854   candidates per accepted point =      1.2
d =  3:  measured = 0.5255   theory = 0.5236   candidates per accepted point =      1.9
d =  4:  measured = 0.3163   theory = 0.3084   candidates per accepted point =      3.2
d =  5:  measured = 0.1687   theory = 0.1645   candidates per accepted point =      5.9
d =  6:  measured = 0.0811   theory = 0.0807   candidates per accepted point =     12.3
d =  7:  measured = 0.0371   theory = 0.0369   candidates per accepted point =     27.0
d =  8:  measured = 0.0158   theory = 0.0159   candidates per accepted point =     63.2
d =  9:  measured = 0.0062   theory = 0.0064   candidates per accepted point =    160.0
d = 10:  measured = 0.0025   theory = 0.0025   candidates per accepted point =    408.0

The measured rate falls off geometrically and follows Kd/2dK_d/2^d: by d=10d=10 only about one candidate point in four hundred lands inside the ball, and the cost per accepted point keeps doubling with every extra dimension.

Points on the Surface: Gaussian Directions

The trick that makes uniform sampling easy is to use the spherical symmetry of the Gaussian distribution. If xi∼N(0,1)x_i \sim \mathcal{N}(0,1) independently, the joint density is

f(x)=∏i=1d12πe−xi2/2=1(2π)d/2e−∥x∥2/2,f(\mathbf{x}) = \prod_{i=1}^d \frac{1}{\sqrt{2\pi}} e^{-x_i^2/2} = \frac{1}{(2\pi)^{d/2}} e^{-\|\mathbf{x}\|^2/2},

which depends on the length ∥x∥\|\mathbf{x}\| only, never on the direction. The distribution is therefore invariant under rotations (isotropic), all directions are equally likely, and

y=x∥x∥\mathbf{y} = \frac{\mathbf{x}}{\|\mathbf{x}\|}

is uniformly distributed on the unit sphere Sd−1(1)S^{d-1}(1).

<Figure size 500x500 with 1 Axes>

Points Inside the Ball

Scaling a direction by a uniform random number ρ∼U(0,1)\rho \sim U(0,1) is wrong: the volume of a shell at radius tt grows like td−1t^{d-1}, so most of the volume is near the surface and a uniform radius bunches the points near the center.

The right radius. For the uniform distribution inside the ball, the probability that a point lies within radius tt must be proportional to the volume it encloses:

F(t)=P(R≤t)=Vol⁡(Bd(t))Vol⁡(Bd(1))=KdtdKd=td.F(t) = P(R \le t) = \frac{\operatorname{Vol}(B_d(t))}{\operatorname{Vol}(B_d(1))} = \frac{K_d t^d}{K_d} = t^d .

Inverse transform sampling with a∼U(0,1)a \sim U(0,1) then gives ρ=F−1(a)=a1/d\rho = F^{-1}(a) = a^{1/d}. For d=2d=2, ρ=a\rho = \sqrt{a}:

a∼U(0,1)a \sim U(0,1)0.000.100.250.500.751.00
ρ=a\rho = \sqrt{a}0.0000.3160.5000.7070.8661.000

Algorithm for uniform points in the ball Bd(1)B_d(1):

  1. draw x∼N(0,Id)\mathbf{x} \sim \mathcal{N}(0, I_d);

  2. normalise, y=x/∥x∥\mathbf{y} = \mathbf{x}/\|\mathbf{x}\| — a uniform direction;

  3. draw a∼U(0,1)a \sim U(0,1);

  4. return a1/d ya^{1/d}\,\mathbf{y}.

<Figure size 1100x500 with 2 Axes>
d =  2, naive  : fraction with rho < 0.5 = 0.4967   (expected 0.2500)
d =  2, correct: fraction with rho < 0.5 = 0.2479   (expected 0.2500)
d =  3, naive  : fraction with rho < 0.5 = 0.4966   (expected 0.1250)
d =  3, correct: fraction with rho < 0.5 = 0.1240   (expected 0.1250)
d = 10, naive  : fraction with rho < 0.5 = 0.5015   (expected 0.0010)
d = 10, correct: fraction with rho < 0.5 = 0.0009   (expected 0.0010)

Nearly Orthogonal Directions

Another counter-intuitive property is that in high dimensions “every direction is orthogonal to every other one”, or more precisely: random vectors are nearly orthogonal.

The Diagonal of the Hypercube

Consider the main diagonal of the cube, 1=(1,1,…,1)⊤\mathbf{1} = (1, 1, \dots, 1)^\top. The angle θd\theta_d between it and a coordinate axis e1=(1,0,…,0)⊤\mathbf{e}_1 = (1, 0, \dots, 0)^\top satisfies

cos⁡θd=e1⊤1∥e1∥ ∥1∥=1d  →d→∞  0,\cos\theta_d = \frac{\mathbf{e}_1^\top \mathbf{1}}{\|\mathbf{e}_1\|\,\|\mathbf{1}\|} = \frac{1}{\sqrt{d}} \;\xrightarrow[d\to\infty]{}\; 0,

so θd→90∘\theta_d \to 90^\circ: the diagonal is almost orthogonal to every axis.

Random Vectors

The same holds for two independent random vectors, and the reason is the law of large numbers: for x,y\mathbf{x}, \mathbf{y} with independent zero-mean, unit-variance entries,

x⊤y∥x∥ ∥y∥≈∑ixiyid d,\frac{\mathbf{x}^\top \mathbf{y}}{\|\mathbf{x}\|\,\|\mathbf{y}\|} \approx \frac{\sum_i x_i y_i}{\sqrt{d}\,\sqrt{d}},

whose numerator is a sum of dd independent zero-mean terms of variance 1 and therefore of size d\sqrt{d} — the ratio is O(1/d)O(1/\sqrt{d}).

cosine similarities of 10 random pairs in 200-D:
[-0.0401  0.0349 -0.0056 -0.0042 -0.075  -0.0497 -0.0402  0.0836  0.0071
  0.1518]
max |cosine| = 0.1518   (1/sqrt(d) = 0.0707)

Gaussian Distribution in High Dimensions

From Geometric Shells to Statistical Shells

The geometric effects above were about the volume of a ball. The Gaussian distribution shows the same phenomenon statistically: even though its density is maximal at the origin, almost no sample lands near the origin.

Why Gaussian Points Do Not Cluster Near the Mean

Let x=(x1,…,xd)∼N(0,Id)\mathbf{x} = (x_1, \dots, x_d) \sim \mathcal{N}(0, I_d). In one dimension many samples lie “close to zero”, and ∣x∣|x| is usually small. This intuition breaks down from two dimensions on: the density is highest at the origin, but the volume available near the origin is negligible.

  • In one dimension “the center” is a point and there is no volume growth.

  • In dd dimensions the volume of a shell grows like rd−1r^{d-1}, so the number of points at radius rr is density ×\times volume.

The center has the highest density but almost no volume, so almost no sample lands there.

Distance of a Gaussian Vector from the Origin

A single identity explains the behaviour:

∥x∥2=∑i=1dxi2∼χd2,E∥x∥2=d,E∥x∥≈d.\|\mathbf{x}\|^2 = \sum_{i=1}^d x_i^2 \sim \chi^2_d, \qquad \mathbb{E}\|\mathbf{x}\|^2 = d, \qquad \mathbb{E}\|\mathbf{x}\| \approx \sqrt{d}.

So ∥x∥≈0.8\|\mathbf{x}\| \approx 0.8 for d=1d=1, ≈1.41\approx 1.41 for d=2d=2, ≈3.16\approx 3.16 for d=10d=10 and ≈14.1\approx 14.1 for d=200d=200 (see chi-squared distribution). Increasing the dimension pushes all samples outward, not just the outliers: the whole distribution sits in a thin shell around radius d\sqrt{d}.

<Figure size 1100x400 with 2 Axes>
mean norm = 14.12   std = 0.70   sqrt(d) = 14.14
fraction of samples with norm within 10% of sqrt(d): 0.96

The two histograms are the statistical version of the geometric thin-shell effect: one- dimensional Gaussian data sit at the mean, two-hundred-dimensional Gaussian data sit on a sphere of radius 14.1 with a width that does not grow with dd.

The Gaussian Annulus Phenomenon

The formal statement is:

With overwhelming probability a Gaussian sample lies within d±O(1)\sqrt{d} \pm O(1) of the origin — a thin annulus whose thickness does not grow with dd.

As dd increases the radius grows like d\sqrt{d} while the thickness stays constant, so the relative thickness tends to zero. This is the reason Gaussian vectors are used in theory: they are the geometry of high-dimensional space, in the same way that uniform points in a ball are.

Connection with the Previous Sections

earlier resultGaussian version
the center of the ball is emptyGaussian mass avoids the origin
uniform volume concentrates at the surfaceGaussian mass concentrates at d\sqrt{d}
uniform sampling needs ρ=a1/d\rho = a^{1/d}Gaussian sampling does this automatically
random vectors are nearly orthogonalnormalised Gaussian vectors are near-orthogonal

Why This Matters

Because almost all Gaussian vectors have length ≈d\approx \sqrt{d}, two independent Gaussian vectors x,y\mathbf{x}, \mathbf{y} satisfy ∥x−y∥2≈2d\|\mathbf{x} - \mathbf{y}\|^2 \approx 2d, with a relative spread that shrinks as dd grows: pairwise distances are stable, and dot products between normalised vectors are small. These two facts are what makes random projections work, and they are the properties we come back to when we discuss random projections and the Johnson–Lindenstrauss lemma later in the course.

k-NN under the Curse of Dimensionality

The distance-concentration argument predicts that k-NN degrades as the dimension grows — and that the degradation can be compensated by more data. The experiment below tests both predictions on synthetic data with make_classification:

  • row 1: nn fixed (n=600n = 600) while dd grows from 2 to 200. Only two features are informative (n_informative=2); the remaining d−2d-2 are noise. With nn fixed, more dimensions mean more noise and fewer points per dimension.

  • row 2: nn grows with dd (n=100 dn = 100\,d), so the number of points per dimension stays constant. If the curse is about density rather than about dimension itself, this should recover the accuracy.

Each configuration is repeated over five seeds, and the plots show the mean accuracy with a ±1\pm 1 standard-deviation band. The classifier is 5-NN on standardised features.

fixed n = 600 d =   2  n =    600   accuracy = 0.934 +- 0.039
fixed n = 600 d =   5  n =    600   accuracy = 0.903 +- 0.040
fixed n = 600 d =  10  n =    600   accuracy = 0.850 +- 0.039
fixed n = 600 d =  25  n =    600   accuracy = 0.773 +- 0.034
fixed n = 600 d =  50  n =    600   accuracy = 0.667 +- 0.052
fixed n = 600 d = 100  n =    600   accuracy = 0.608 +- 0.041
fixed n = 600 d = 200  n =    600   accuracy = 0.594 +- 0.022
n = 100 d     d =   2  n =    200   accuracy = 0.963 +- 0.036
n = 100 d     d =   5  n =    500   accuracy = 0.929 +- 0.057
n = 100 d     d =  10  n =   1000   accuracy = 0.878 +- 0.048
n = 100 d     d =  25  n =   2500   accuracy = 0.824 +- 0.075
n = 100 d     d =  50  n =   5000   accuracy = 0.737 +- 0.047
n = 100 d     d = 100  n =  10000   accuracy = 0.671 +- 0.016
n = 100 d     d = 200  n =  20000   accuracy = 0.627 +- 0.029
<Figure size 800x500 with 1 Axes>

The first curve falls as the dimension grows although the informative structure never changes: the two useful features are still there, but they are buried among d−2d-2 noise features, and the distances that k-NN trusts are dominated by the noise.

The second curve tests whether more data is the cure. It helps — every value is a little better than the corresponding point of the first curve — but it does not stop the decay: the accuracy still falls from about 0.96 at d=2d=2 to about 0.63 at d=200d=200, with 33 times more data. More data buys density, and density was not the binding constraint here: the binding constraint is that nearly all coordinates are noise, so the distance concentration of the previous sections is a property of the distribution, not only of the sample size.

The practical consequence is the one ESL draws in §2.5: for high-dimensional data, k-NN must be preceded by something that removes or down-weights the uninformative directions — feature selection, PCA, or a learned metric. Adding points is useful, but it is not a substitute.

Summary

  • High-dimensional space is empty in the center: the volume of the ball is negligible compared with the cube, and almost all of the cube’s volume is in its 2d2^d corners.

  • A neighbourhood holding a fixed fraction rr of the points has edge length ed(r)=r1/de_d(r) = r^{1/d}: in ten dimensions, 10% of the data needs 80% of the range of every coordinate.

  • Distances concentrate: dmin⁡/dmax⁡→1d_{\min}/d_{\max} \to 1, so neighbour rankings become noise and k-NN degrades — unless nn grows with dd.

  • Most of the volume of a ball is in a thin shell of fixed relative thickness, and Gaussian samples concentrate at radius d\sqrt{d} with a thickness that does not grow with dd.

  • Uniform sampling in a ball needs the radius ρ=a1/d\rho = a^{1/d}; the easy way is a Gaussian direction times that radius. Rejection sampling dies exponentially.

  • Random vectors are nearly orthogonal, and pairwise distances are stable — the properties behind random projections.

References

  • Hastie et al. (2009), §2.5 (local methods in high dimensions, Figure 2.6) and §2.9 (model assessment).

  • Zaki & Meira (2020), chapter 6 (high-dimensional space, Figures 6.4–6.6).

  • Blum, Hopcroft and Kannan, Foundations of Data Science, chapter 2 (concentration of measure, random projections).

References
  1. Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction (2nd ed.). Springer.
  2. Zaki, M. J., & Meira, W. (2020). Data Mining and Machine Learning: Fundamental Concepts and Algorithms (2nd ed.). Cambridge University Press. https://www.cambridge.org/9781108497367