OPENLAB-IMAGE PROCESSING
Bạn có muốn phản ứng với tin nhắn này? Vui lòng đăng ký diễn đàn trong một vài cú nhấp chuột hoặc đăng nhập để tiếp tục.

Principal Component Analysis_PCA

2 posters

Go down

Principal Component Analysis_PCA Empty Principal Component Analysis_PCA

Bài gửi by jackauk Sun Aug 16, 2015 11:46 pm

Xuất phát từ phép biến đổi Karhunen-Loeve, PCA đưa ra một vector s- chiều biểu diễn mỗi một khuôn mặt trong tập ảnh huấn luyên, nhằm hướng tới việc tìm ra một không gian nhỏ hơn t-chiều với những vector cơ bản tương ứng với  chiều biến thiên lớn nhất của biến trong không gian ảnh gốc. Không gian nhỏ mới thông thường có số chiều nhỏ hơn  (t<<s). Nếu xem như các thành phần của ảnh là những biến ngẫu nhiên, thì vector cơ bản PCA được định nghĩa là những vector trị riêng của ma trận phân tán.
Tài liệu tham khảo chính:
M. Turk, A. Pentland, Eigenfaces for Recognition, Journal of Cognitive Neurosicence, Vol. 3, No. 1, 1991, pp. 71-86


M.A. Turk, A.P. Pentland, Face Recognition Using Eigenfaces, Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 3-6 June 1991, Maui, Hawaii, USA, pp. 586-591


A. Pentland, B. Moghaddam, T. Starner, View-Based and Modular Eigenspaces for Face Recognition, Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 21-23 June 1994, Seattle, Washington, USA, pp. 84-91

H. Moon, P.J. Phillips, Computational and Performance aspects of PCA-based Face Recognition Algorithms, Perception, Vol. 30, 2001, pp. 303-321

Bản gốc:


Các bài viết trong chủ đề:
1/ Thuật toán PCA
2/ Thuật toán QR để tìm trị riêng (eigenvalue) và vector trị riêng (eigenvector)
jackauk
jackauk
Thành viên thường

Tổng số bài gửi : 63
Điểm danh tiếng : 2
Join date : 16/08/2015
Age : 35
Đến từ : TP Hồ Chí Minh

Về Đầu Trang Go down

Principal Component Analysis_PCA Empty Thuật toán PCA

Bài gửi by jackauk Mon Aug 17, 2015 11:57 am

Principal Component Analysis (PCA)  được Karl Pearson tạo ra năm 1901. Đến những năm 80, Sirovich và Kirby đã phát triển kỹ thuật này để thể hiện khuôn mặt một cách hiệu quả. Đưa ra sự giống nhau giữa nhiều hình ảnh khuôn mặt khác nhau, kĩ thuật này tìm ra những thành phần cơ bản của sự phân bố trên khuôn mặt, thể hiện bằng các eigenvectors. Từng khuôn mặt trong một tập hợp các khuôn mặt sau đó có thể tính xấp xỉ bằng sự kết hợp tuyến tính giữa những eigenvector lớn nhất, được biết tới như eigenfaces.

Hình 2.12: Phương pháp phân tích thành phần chính PCA
2.2.4.1 THUẬT TOÁN PCA
Đặc tính của thuật toán là:
- 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ể.


Hình 2.13: PCA giảm số chiều dữ liệu vẫn giữ đặc trưng tốt nhất
Cụ thể thuật toán này có thể diễn giải như sau:
Cho ma trận   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 đặc trưng 1 (cột 1 của   ) giá trị thay đổi trong khoảng (0, 1), trên đặc trưng 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 đặc trưng (các cột của X) về cùng một gốc tọa độ:
(2.6)
(2.7)
(2.Cool
Trong đó n là số dòng của  X,   ɡ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 đặc trưng về cùng một gốc tọa độ, đồng thời chuẩn hóa về cùng một quãng lệch chuẩn bằng 1:
(2.9)
(2.10)
Trong đó σ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   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 đặc trưng trong  :
               (2.11)
Do là tích của ma trận với chuyển vị của nó nên  là ma trận positive semidefinite kích thước  p x p. Hơn nữa V có p trị riêng λi ≥ 0, i=1…p .
Tiếp theo, PCA tìm trị riêng và vector riêng tương ứng của  , 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à
λ1 ≥ λ2 ≥ … ≥ λp (2.12)
và p vector riêng tương ứng là
        u1, u2, … , up
Khi đó các trục của không gian mới chính là các vector riêng  ở 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
(2.13)
Khi đó tọa độ các điểm trong hệ tọa độ mới là
            (2.14)
jackauk
jackauk
Thành viên thường

Tổng số bài gửi : 63
Điểm danh tiếng : 2
Join date : 16/08/2015
Age : 35
Đến từ : TP Hồ Chí Minh

Về Đầu Trang Go down

Principal Component Analysis_PCA Empty Thuật toán QR

Bài gửi by jackauk Tue Aug 25, 2015 11:50 pm

Trong đại số tuyến tính số học, các thuật toán QR là một thuật toán eigenvalue. Đó là một thủ tục để tính toán các giá trị riêng và vector riêng của ma trận. Việc chuyển đổi QR đã được phát triển vào cuối những năm 1950 bởi John GF Francis (Anh) và Vera N. Kublanovskaya (Liên Xô), làm việc độc lập. Ý tưởng cơ bản là để thực hiện một phân giải QR là viết lại các ma trận như là một kết quả của một ma trận trực giao và một ma trận tam giác trên, nhân các phần tử trong thứ tự ngược lại, và lặp.
Từ khóa: Ma trận trực giao, ma trận đường chéo, ma trận tam giác trên, Hermitian
Giải thuật:

MATLAB code:
V C++ code:


Được sửa bởi jackauk ngày Sat Sep 05, 2015 6:21 pm; sửa lần 2.
jackauk
jackauk
Thành viên thường

Tổng số bài gửi : 63
Điểm danh tiếng : 2
Join date : 16/08/2015
Age : 35
Đến từ : TP Hồ Chí Minh

Về Đầu Trang Go down

Principal Component Analysis_PCA Empty Re: Principal Component Analysis_PCA

Bài gửi by phan gia luân Sun Aug 30, 2015 8:57 pm

edit cái icon kìa anh "Cool"

phan gia luân

Tổng số bài gửi : 7
Điểm danh tiếng : 7
Join date : 20/08/2015
Age : 28
Đến từ : tp.hcm

Về Đầu Trang Go down

Principal Component Analysis_PCA Empty Re: Principal Component Analysis_PCA

Bài gửi by Sponsored content


Sponsored content


Về Đầu Trang Go down

Về Đầu Trang


 
Permissions in this forum:
Bạn không có quyền trả lời bài viết