Phương pháp phân tích thành phần chính dựa trên hàm nhân

1. Giới thiệu

Trong những năm gần đây với sự phát triển mạnh mẽ của khoa học kỹ thuật nói chung và công nghệ thông tin nói riêng đã khiến cho dữ liệu mà chúng ta thu thập được ngày càng trở nên phong phú và đa dạng. Các nguồn dữ liệu được tạo ra ngày càng nhiều và phức tạp. Điều này khiến cho quá trình khai phá dữ liệu trên nguồn thông tin khổng lồ mất rất nhiều thời gian, công sức và chi phí. Vì vậy cần thiết phải thu gọn việc biểu diễn dữ liệu và kỹ thuật giảm số chiều của dữ liệu được sử dụng phổ biến nhằm: Giúp loại bỏ các đặc trưng không liên quan, giảm nhiễu, lỗi của dữ liệu;  Giảm chi phí về thời gian và bộ nhớ cho quá trình khai phá dữ liệu; Cho phép hiển thị hóa dữ liệu một cách rõ ràng và tốt hơn.

Đã có nhiều những công trình nghiên cứu về việc giảm bớt số chiều dữ liệu dựa trên các kỹ thuật khác nhau như LDA, ICA, SVD, LSI, SOM, PCA... Tuy nhiên các phương pháp này mới chỉ dừng ở mức độ xử lý các bài toán tuyến tính đơn giản. Phương pháp Phân tích thành phần chính dựa trên  hàm nhân tiếp cận giải quyết các bài toán phi tuyến phức tạp. Đây là phương pháp do Scholkopf và các đồng nghiệp của ông phát triển còn được biết đến với tên gọi là KPCA [1,2,4] (PCA dựa trên hàm nhân).

            Phương pháp hàm nhân bắt nguồn từ việc xử lý dữ liệu bằng một ánh xạ phi tuyến Φ, sau đó áp dụng thuật toán tuyến tính trên không gian đặc trưng của Φ. Lúc này trên không gian đặc trưng ta có thể phân lớp dữ liệu bằng một hàm tuyến tính thuận tiện.

            Hàm nhân tuy là hàm tuyến tính trong không gian đặc trưng được định nghĩa bởi ánh xạ Φ nhưng khi nhìn vào không gian ban đầu thì đó lại là một hàm phi tuyến nếu ánh xạ Φ là một hàm phi tuyến.

            Trong không gian hai chiều bằng ánh xạ phi tuyến việc đầu tiên ta cần làm là ánh xạ dữ liệu sang không gian đặc trưng bằng ánh xạ Φ mà trên không gian đặc trưng đó ta có thể phân loại dữ liệu bằng một hàm tuyến tính.

Một hàm K là một hàm nhân khi và chỉ khi với mọi x,z thuộc X ta có:

Với Φ là một ánh xạ từ không gian đầu vào sang không gian đặc trưng.

            Không gian đặc trưng thường có số chiều rất lớn thậm chí là vô hạn chiều lúc này ta không thể tính trực tiếp ánh xạ Φ được. Tuy nhiên, ta lại có thể tính được tích vô hướng trong không gian này (dữ liệu chỉ xuất hiện trong tích vô hướng). Thậm chí không cần quan tâm ánh xạ Φ mà chỉ cần quan tâm đến hàm nhân [3,5,6].

2. Phương pháp Phân tích thành phần chính dựa trên hàm nhân

Phương pháp Phân tích thành phần chính dựa trên hàm nhân thực hiện biến đổi phi tuyến trên hệ tọa độ bằng cách tìm các phần tử cơ bản có liên hệ phi tuyến với các giá trị đầu vào.

Giả sử giá trị đầu vào là tập tập véc tơ dữ liệu N chiều:. Khi đó việc tìm  K véc tơ trực giao tốt nhất để biểu diễn dữ liệu: (Với K N; K có thể là ; được gọi là không gian đặc trưng) sử dụng Phương pháp KPCA được thực hiện theo các bước sau:

Bước 1: Biểu diễn tập dữ liệu huấn luyện thành tập các véc tơ Ii. Chuẩn hóa kích thước của tập dữ liệu huấn luyện.

Bước 3:   Tính ma trận hiệp

Bước 5: Xác định các thành phần chính. Sắp xếp các trị riêng theo thứ tự giảm dần. Các véc tơ đặc trưng ứng với các trị riêng lớn nhất.

Bước 6: Biểu diễn lại tập  dữ liệu huấn luyện trong không gian đặc trưng được hình thành từ các thành phần chính và tập vecto đặc trưng.

3. Ưu nhược điểm của phương pháp Phân tích thành phần chính dựa trên hàm nhân

Ưu điểm:

- Trong nhiều bài toán phi tuyến phức tạp, KPCA sử dụng một hàm nhân tạo ra một không gian đặc trưng nhiều chiều và trên không gian đặc trưng có thể phân lớp dữ liệu bằng một hàm tuyến tính và 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  của dữ liệu trên mỗi chiều mới.

- Giảm thời gian tính toán cũng như giảm độ nhiễu của tín hiệu đầu vào mang lại độ chính xác và hiệu quả cao trong việc xử lý các bài toán phi tuyến . 

- Các trục tọa độ trong không gian mới là tổ hợp tuyến tính và phi tuyến của không gian cũ, do đó về mặt ngữ nghĩa, KPCA vẫn biểu diễn rất tốt dữ liệu ban đầu.

- Trong không gian đặc trưng, các liên kết tiềm ẩn của dữ liệu có thể được phát hiện và thể hiện, nếu đặt trong không gian ban đầu thì khó phát hiện, hoặc không thể hiện rõ.

Nhược điểm: Cần xây dựng, lựa chọn các hàm nhân phù hợp với từng bài toán cụ thể.

4. Kết luận

    Trong lĩnh vực nghiên cứu về khai phá dữ liệu nói chung cũng như nghiên cứu về thuật toán phân lớp nói riêng, vấn đề xử lý dữ liệu lớn ngày càng trở thành vấn đề cấp thiết và đóng vai trò chủ đạo trong giải quyết các bài toán thực tế. Hiện nay, phương pháp hàm nhân đã được sử dụng để tăng khả năng áp dụng PCA khi giải quyết các bài toán phi tuyến.

Điểm cốt lõi của phương pháp này việc lựa chọn hàm nhân. Thông thường ta hay sử dụng lại những hàm nhân đã có sẵn như: Hàm Gauss, Hàm đa thức, Hàm Euclidean. Tuy nhiên cũng có thể xây dựng hàm nhân mới dựa vào những hàm nhân đã có sẵn. Việc xây dựng hàm nhân phù hợp với những mô hình thực nghiệm trong lĩnh vực Tin-Sinh học sẽ tiếp tục được nghiên cứu và phát triển trong thời gian tới.

Tài liệu tham khảo

1. B. Scholkopf, A. Smola, and K. Muller. Kernel Principal component Analysis. In B. Scholkopf, C. Burges, and A. Smola, editors, Advances in Kernel Methods - Support Vector Learning, MIT Press, Cambridge, MA, 1999, pages 327 - 352.

2. B. Scholkopf, A. Smola, and K. Muller, Nonlinear Component Analysis as a Kernel Eigenvalue Problem, Neural Computation, vol. 10, 1998, pages 1299-1319.

3. K. Muller, S. Mika, G. Ratsch, K. Tsuda, and B. Scholkopf, An introduction to kernel - based learning algorithms, IEEE Trans. Neural Networks, Mar 2001, vol. 12, no.2, pages 181-202.

4. S. Mika, B. Scholkopf, A. Smola, K. Muller, R. Scholz, G. Ratsch, Kernel PCA and de-noising in feature spaces. In: Advances in Neural Information Processing Systems 11. MIT Press, 1999, pages 536-542.

5. R. Ganadesikan, Methods for Statistical Data Analysis of Multivariate Observations, Wiley, New York, 1977.

6. S. Taylor and Cristianini: Kernel Methods for Pattern Analysis. Cambridge University Press, 2004.