(Demo) Tìm hiểu thuật toán PCA (Principal Component Analysis)

Machine Learning Foundations

PCA là cách tìm các trục mới giữ lại nhiều phương sai nhất của dữ liệu. Khi chiếu dữ liệu lên các trục này, ta giảm số chiều nhưng vẫn giữ phần thông tin quan trọng.

1. Ý tưởng cốt lõi

Thách thức lớn nhất trong khoa học dữ liệu là lời nguyền đa chiều. PCA giải quyết vấn đề này bằng cách tìm những hướng quan trọng nhất, nơi dữ liệu biến thiên mạnh nhất.

Thông tin = phương sai

Các hướng có phương sai lớn thường chứa nhiều tín hiệu hơn. Các hướng có phương sai nhỏ thường là nhiễu hoặc thông tin dư thừa.

Tính trực giao

Các trục mới phải vuông góc với nhau để tránh đếm trùng thông tin đã được giải thích bởi thành phần trước đó.

2. Quy trình toán học

Hiệu chỉnh trung bình

$$\mathbf{X}_{centered} = \mathbf{X} - \mathbf{\bar{X}}$$

Ma trận hiệp biến

$$\mathbf{C} = \frac{1}{n-1} \mathbf{X}_{centered}^T \mathbf{X}_{centered}$$

Trị riêng và vector riêng

$$\det(\mathbf{C} - \lambda\mathbf{I}) = 0$$

3. Ví dụ minh họa chi tiết

Khảo sát 4 mẫu dữ liệu với 3 đặc trưng: x (chi tiêu), y (thu nhập), và z (tín dụng).

Mẫu	x	y	z
1	10	50	700
2	20	60	710
3	10	50	690
4	20	60	700

Bước 1: Tính trung bình và ma trận centered

$\bar{x} = \frac{10+20+10+20}{4} = 15$

$\bar{y} = \frac{50+60+50+60}{4} = 55$

$\bar{z} = \frac{700+710+690+700}{4} = 700$

$$\mathbf{X}_{centered} = \begin{pmatrix} -5 & -5 & 0 \\ 5 & 5 & 10 \\ -5 & -5 & -10 \\ 5 & 5 & 0 \end{pmatrix}$$

Bước 2: Ma trận hiệp biến

Thực hiện phép nhân $\mathbf{C} = \frac{1}{3} \mathbf{X}_{centered}^T \mathbf{X}_{centered}$:

$$\mathbf{C} = \begin{pmatrix} 33.33 & 33.33 & 33.33 \\ 33.33 & 33.33 & 33.33 \\ 33.33 & 33.33 & 66.67 \end{pmatrix}$$

Bước 3: Giải đa thức đặc trưng

Ta cần tìm $\lambda$ sao cho $\det(\mathbf{C} - \lambda\mathbf{I}) = 0$:

$$P(\lambda) = \begin{vmatrix} 33.33-\lambda & 33.33 & 33.33 \\ 33.33 & 33.33-\lambda & 33.33 \\ 33.33 & 33.33 & 66.67-\lambda \end{vmatrix} = 0$$

1. Quan sát sự phụ thuộc tuyến tính

Cột 1 và cột 2 của ma trận $(\mathbf{C} - \lambda\mathbf{I})$ giống hệt nhau nếu $\lambda = 0$, nên ma trận bị suy biến tại điểm đó.

$$\implies \lambda_3 = 0$$

2. Khai triển định thức

Đặt $a = 33.33$ và $b = 66.67$, phương trình trở thành:

$$(a-\lambda) \cdot [(a-\lambda)(b-\lambda) - a^2] - a \cdot [a(b-\lambda) - a^2] + a \cdot [a^2 - a(a-\lambda)] = 0$$

$$-\lambda^3 + (2a+b)\lambda^2 - (2ab+a^2-a^2)\lambda = 0$$

$$-\lambda^3 + (133.33)\lambda^2 - (3733.33)\lambda = 0$$

3. Giải phương trình bậc 2 còn lại

Vì $\lambda = 0$ là một nghiệm, ta chia đa thức cho $\lambda$:

$$\lambda^2 - 133.33\lambda + 3733.33 = 0$$

Sử dụng công thức nghiệm $ \Delta = b^2 - 4ac $:

$\Delta = (133.33)^2 - 4(3733.33) \approx 17776 - 14933 = 2843$
$\sqrt{\Delta} \approx 53.33$
$\lambda_1 = \frac{133.33 + 53.33}{2} = 93.33$
$\lambda_2 = \frac{133.33 - 53.33}{2} = 40.00$

Kết quả cuối cùng

PC1 (chủ đạo) $\lambda_1 = 93.33$

PC2 (phụ) $\lambda_2 = 40.00$

PC3 (nhiễu/thừa) $\lambda_3 = 0.00$

Toàn bộ thông tin được gói gọn trong 2 chiều PC1 và PC2. Chiều thứ 3 không chứa thêm thông tin do sự phụ thuộc tuyến tính giữa các biến ban đầu.