Phương pháp Phân tích thành phần chính (Principal Component Analysis – PCA)

Posted on 25.12.2013 by Tuấn Lê

(Nguồn: phvu.net)

“Principal component analysis (PCA) is a statistical procedure that uses an orthogonal transformation to convert a set of observations of possibly correlated variables into a set of values of linearly uncorrelated variables called principal components. The number of principal components is less than or equal to the number of original variables.”

Phân tích thành phần chính (Principal Component Analysis – PCA) là một trong những phương pháp phân tích dữ liệu nhiều biến đơn giản nhất. Phần 1 của bài này sẽ nói về động lực và ý tưởng chính của PCA, sau đó trình bày từng bước trong thuật toán PCA. Như thường lệ, để hiểu thuật toán thì cài đặt là cách tốt nhất, do đó một đoạn mã MATLAB minh họa từng bước trong PCA cũng được trình bày. Phần cuối cùng là chi tiết các khai triển Toán học trong PCA. Do mục tiêu ứng dụng nên các phương trình cụ thể được để dành đến phần này, người đọc nếu thật sự quan tâm nguyên lí của PCA, tại sao PCA lại sử dụng những công thức như thế v.v… thì có thể tham khảo phần này để biết thêm chi tiết.

1. Giới thiệu

Như đã nói trong bài trước, trong thống kê, thông thường cần phải “nghiên cứu” dữ liệu trước khi xây dựng các mô hình suy diễn dựa trên dữ liệu đó. Tuy nhiên đôi khi dữ liệu có số chiều lớn, không thể visualize (không biết dịch là gì) trong không gian 2 hay 3 chiều, do đó cần phải tìm cách đưa dữ liệu về không gian có số chiều nhỏ hơn.

PCA là một trong những phương pháp như thế, nhưng hơn thế, PCA còn giống như một Swiss knife với nhiều đặc tính tốt:

Giúp giảm số chiều của dữ liệu,
Thay vì giữ lại các trục tọa độ của không gian cũ, PCA xây dựng một không gian mới ít chiều hơn, nhưng lại có khả năng biểu diễn dữ liệu tốt tương đương không gian cũ, nghĩa là đảm bảo độ biến thiên (variability) của dữ liệu trên mỗi chiều mới.
Các trục tọa độ trong không gian mới là tổ hợp tuyến tính của không gian cũ, do đó về mặt ngữ nghĩa, PCA xây dựng feature mới dựa trên các feature đã quan sát được. Điểm hay là những feature này vẫn biểu diễn tốt dữ liệu ban đầu.
Trong không gian mới, các liên kết tiềm ẩn của dữ liệu có thể được khám phá, mà nếu đặt trong không gian cũ thì khó phát hiện hơn, hoặc những liên kết như thế không thể hiện rõ.

Nói một cách ngắn gọn, mục tiêu của PCA là tìm một không gian mới (với số chiều nhỏ hơn không gian cũ). Các trục tọa độ trong không gian mới được xây dựng sao cho trên mỗi trục, độ biến thiên của dữ liệu trên đó là lớn nhất có thể. Tiếng Việt thì dài dòng, nhưng tiếng Anh thì mục tiêu này gọi là maximize the variability. Ba chữ này gói gọn ý tưởng chính của PCA.

Minh họa PCA: phép chiếu lên các trục tọa độ khác nhau có thể cho cách nhìn rất khác nhau về cùng một dữ liệu.

Một ví dụ kinh điển là hình ảnh về con lạc đà. Cùng là một con lạc đà nhưng nếu nhìn từ bên hông thì ta có được đầy đủ thông tin nhất, trong khi nhìn từ phía trước thì thật khó để nói nó là lạc đà.

Một ví dụ thuyết phục hơn được minh họa trong hình sau

Minh họa PCA: tìm các trục tọa độ mới sao cho dữ liệu có độ biến thiên cao nhất

Giả sử tập dữ liệu ban đầu (tập điểm màu xanh) được quan sát trong không gian 3 chiều (trục màu đen) như hình bên trái. Rõ ràng 3 trục này không biểu diễn được tốt nhất mức độ biến thiên của dữ liệu. PCA do đó sẽ tìm hệ trục tọa độ mới (là hệ trục màu đỏ trong hình bên trái). Sau khi tìm được không gian mới, dữ liệu sẽ được chuyển sang không gian này để được biểu diễn như trong hình bên phải. Rõ ràng hình bên phải chỉ cần 2 trục tọa độ nhưng biểu diễn tốt hơn độ biến thiên của dữ liệu so với hệ trục 3 chiều ban đầu.

Một điểm rất đẹp nữa của PCA là các trục tọa độ trong không gian mới luôn đảm bảo trực giao đôi một với nhau, mặc dù trong không gian ban đầu, các trục có thể không trực giao.

Dài dòng như vậy là đủ, ta sẽ trình bày từng bước thuật toán PCA trong phần tới. Chi tiết về ý tưởng và khai triển toán học được dành lại để trình bày ở cuối bài.

2. Thuật toán PCA

Cho ma trận $\mathbf{X} =\{x_{ij}\} \in \mathcal{R}^{n\times p}$ . Các bước của PCA lần lượt như sau:

1. Tiền xử lí

Dữ liệu ban đầu có thể có giá trị thay đổi bất thường. Ví dụ trên feature 1 (cột 1 của $\mathbf{X}$ ) giá trị thay đổi trong khoảng (0, 1), trên feature 2 lại biến thiên trong đoạn (-100, 100). Rõ ràng cần phải có một bước tiền xử lí để chuẩn hóa giá trị trên các cột của ma trận X. Có 2 cách tiền xử lí thường được dùng cho PCA là Centered PCA và Normed PCA.

Centered PCA mang tất cả các feature (các cột của X) về cùng một gốc tọa độ:

$\displaystyle \hat{\mathbf{X}}=\{\hat{x}_{ij}\}$ ,

$\displaystyle \hat{x}_{ij}=\frac{x_{ij}-g_j}{\sqrt{n}}$ , (1a)

$\displaystyle g_j = \frac{\sum_{i=1}^n{x_{ij}}}{n}$ .

Trong đó n là số dòng của X, $g_j$ là mean của cột thứ j của X, được tính như trên.

Normed PCA mang tất cả các feature về cùng một gốc tọa độ, đồng thời chuẩn hóa về cùng một quãng standard-deviation bằng 1:

$\displaystyle \hat{\mathbf{X}}=\{\hat{x}_{ij}\}$ ,

$\displaystyle \hat{x}_{ij}=\frac{x_{ij}-g_j}{\sqrt{n}\sigma_j}$ . (1b)

Trong đó $\sigma_j$ là độ lệch chuẩn (standard deviation) của cột thứ j trong X.

Thông thường Normed PCA hay được dùng. Sau bước tiền xử lí, ma trận $\hat{\mathbf{X}}$ sẽ là đầu vào cho bước tiếp theo.

2. Xây dựng không gian mới

Tính ma trận hiệp phương sai (covariance) của các feature trong $\hat{\mathbf{X}}$ :

$\displaystyle \mathbf{V} = \hat{\mathbf{X}}^\mathrm{T}\hat{\mathbf{X}}$ (2)

Do là tích của ma trận $\hat{\mathbf{X}}$ với chuyển vị của nó nên $\mathbf{V}\in\mathcal{R}^{p\times p}$ là ma trận positive semidefinite kích thước $p\times p$ . Hơn nữa $\mathbf{V}$ có p trị riêng $\lambda_i \geq 0, i=1..p$ .

Tiếp theo, PCA tìm trị riêng và vector riêng tương ứng của $\mathbf{V}$ , sắp xếp theo thứ tự giảm dần của trị riêng. Giả sử p trị riêng của V là

$\lambda_1 \geq \lambda_2 \geq \cdots \lambda_p$ , (3)

và p vector riêng tương ứng là

$\mathbf{u}_1, \mathbf{u}_2,\cdots ,\mathbf{u}_p$ . (4)

Khi đó các trục của không gian mới chính là các vector riêng $\mathbf{u}_i$ ở trên, đương nhiên các vector riêng hoàn toàn độc lập tuyến tính (nghĩa là trực giao đôi một).

Có thể nói trong PCA, trị riêng và vector riêng có vị trí rất đẹp, thỏa mãn tất cả các yêu cầu của PCA. Bản thân tôi khi đọc đến phần này cũng thấy bất ngờ vì lời giải cho PCA không gì khác lại hoàn toàn trọn vẹn trong trị riêng và vector riêng. Tuy nhiên tại thời điềm này, ta sẽ chấp nhận như vậy. Phần cơ sở Toán học ở cuối bài sẽ giải thích tại sao trị riêng và vector riêng lại xuất hiện (có phần bất ngờ) trong PCA như vậy.

3. Chuyển dữ liệu từ không gian ban đầu vào không gian mới

Thông thường không gian mới không được xây dựng bằng tất cả p vector riêng trong (4), mà thông thường chỉ từ k vector riêng đầu tiên, với k < p. Tại sao là các vector đầu tiên, và chọn k bao nhiêu thì tốt, ta sẽ bàn trong phần cuối.

Như vậy gọi

$\mathbf{U} = \left[\begin{array}{c|c|c|c}\mathbf{u}_1 & \mathbf{u}_2 & \cdots & \mathbf{u}_k\end{array}\right] \in \mathcal{R}^{p\times k}$ .

Khi đó tọa độ các điểm trong hệ tọa độ mới là

$\mathbf{F} = \hat{\mathbf{X}}\mathbf{U}$ (5)

Xong. Ta đã kết thúc giải thuật PCA, không thể đơn giản hơn.

Trong phần này ta chỉ thực hiện phân tích các sample trong không gian tạo bởi các feature. Ta còn có thể thực hiện khảo sát các feature trong không gian tạo bởi các sample. Đương nhiên có thể chuyển vị ma trận X rồi thực hiện tương tự, nhưng đó là cách võ biền, cày bừa. Thực sự không cần phải như vậy, mà nhờ vào những đặc tínhđẹp của trị riêng và vector riêng, ta có thể tính ngay không gian mới của các sample (để biểu diễn các feature) từ các vector riêng trong (4). Trị riêng còn đẹp đến nỗi được dùng trong các tiêu chuẩn để chọn k. Ta sẽ trở lại với 2 vấn đề này trong phần cuối của bài.

Ngoài ra để đánh giá chất lượng của không gian mới tạo bởi PCA, ta dùng 2 độ đo là contribution và squared cosine. Ta cũng dành 2 phần này cho phần cuối bài.

3. Mã nguồn MATLAB

Sau đây là đoạn mã MATLAB minh họa các bước của thuật toán PCA, thực hiện phân tích các observation trong không gian các feature, sau cùng tính các độ đo contribution và squared cosine. Download here.

function [ output_args ] = mypca( X )

m = mean(X);

st = std(X, 1);

sz = size(X);

% sz(1): number of observations

% sz(2): number of features

% normed PCA

Xhat = zeros(sz);

for i=1:sz(2)

Xhat(:,i) = (X(:, i) - m(i))/(sqrt(sz(1))*st(i));

end

display('Normed data:');

display(Xhat);

% correlation matrix

V = Xhat' * Xhat;

display('Correlation between features (columns) of normed data:');

display(V);

%eigenvalues

[eivec, eival] = eig(V);

% display the eigenvalues accumulation and %

% sz(2) == number of eigenvalues of V

eigenInfo = zeros(sz(2), 3);

sum_eival = sum(diag(eival));

acc_eival = 0;

for i=sz(2):-1:1

acc_eival = acc_eival + eival(i, i);

% eigenvalues, accumulate, %

eigenInfo(sz(2)-i+1, : ) = [eival(i, i), acc_eival, acc_eival/sum_eival];

end

display('Eigenvalues Accumulate Acc ');

display(eigenInfo);

%eigenvectors

eivec2 = zeros(size(eivec));

for i=1:size(eivec, 2)

eivec2(:, i) = eivec(:, size(eivec, 2) - i + 1);

end

eivec = eivec2;

display('Full eigenvectors:');

display(eivec);

% Ask for number of new coordinates

respone = input('Number of new coordinates: ');

dim = respone(1);

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%The new observations

F = Xhat*eivec(:, 1:dim);

display('Transformed data (New coordinates of observations):');

display(F);

% Contribution of observations

C = F.^2;

for i=1:size(C, 2)

C(:, i) = C(:, i)/eival(sz(2) - i + 1, sz(2) - i + 1);

end

display('Contribution of observations:');

display(C);

% Squared cosine of observations

SC = F.^2;

for i=1:size(SC, 1)

SC(i, : ) = SC(i, : )/sum(SC(i,: ), 2);

end

display('Squared cosine of observations:');

display(SC);

end

4. Cơ sở Toán học của PCA

Xem tại đây.

5. Kết luận

Một số hạn chế của PCA:

Chỉ làm việc với dữ liệu numeric,
Nhạy cảm với các điểm outlier/extreme,
Không phù hợp với các mô hình phi tuyến, do PCA hoàn toàn dựa trên các biến đổi tuyến tính.

————————–

Xem thêm: http://phvu.net/2011/11/15/pca-intuition-maths/

————-&&————

Filed under: DS & ML & AI, Thống kê |

« Thế nào gọi là bong bóng tài sản? Giới thiệu về phương pháp Principal Component Analysis (PCA) và một số ứng dụng trong tài chính (Phần I) »

MFEDE

Chuyên mục

Thẻ

Bài & Trang được đáng chú ý

Bài viết mới