BTL ĐSTT [PDF]

Zitiervorschau

TRƯỜNG ĐẠI HỌC BÁCH KHOA HCM

BÁO CÁO BÀI TẬP LỚN Môn: Đại số tuyến tính

ĐỀ TÀI: PHÂN TÍCH THÀNH PHẦN CHÍNH (PCA: PRINCIPLE COMPONENT ANALYSIS). ỨNG DỤNG CỦA PHÂN TÍCH PCA ĐỂ HỒI QUY TUYẾN TÍNH (LINEAR REGRESSION)

Lớp: DD20LT02 Nhóm thực hiện: Nhóm 11 Giáo viên: TS. Đặng Văn Vinh Năm học: 2020 - 2021

DANH SÁCH THÀNH VIÊN Nhóm 11 Số thứ tự

Họ và tên

Mã số sinh viên

1

Nguyễn Hữu Tiến

2010690

2

Phan Đoàn Phi Tiến

2010692

3

Đinh Công Tiến

2010687

4

Trần Như Toàn

2010708

5

Lê Anh Trí Tri

2010726

6

Nguyễn Lâm Trí

2010735

7

Lê Kỳ Trung

2010085

8

Lê Công Tú

2010762

9

Phan Xuân Anh Tú

2010766

10

Ngũ Thế Tuấn

2010757

1

MỤC LỤC I. Phương pháp phân tích thành phần chinh PCA 1. Sơ lược về phương pháp PCA .................................................................................. 3 2. Một số thuật khái niệm toán trong thống kê ............................................................. 3 3. Cơ sở lý thuyết .......................................................................................................... 4 4. Các bước phân tích PCA .......................................................................................... 5 5. Mô phỏng thuật toán ................................................................................................. 6 6. Nhược điểm của phương pháp PCA ......................................................................... 6 7. Một số ứng dụng trong lĩnh vực khác ....................................................................... 7

II. Ứng dụng PCA trong hồi quy tuyến tính: 1. Định nghĩa hồi quy tuyến tính .................................................................................. 7 2. Mô tả thuật toán ........................................................................................................ 7 3. Ví dụ minh họa ......................................................................................................... 7 III. Tài liệu tham khảo ................................................................................. 9

2

I.

Phương pháp phân tích thành phần chính PCA: 1. Sơ lược về phương pháp PCA

Trong công tác nghiên cứu thực nghiệm, ta thu thập được những bộ dữ liệu thường được thể hiện dưới dạng bảng các giá trị số của nhiều cá thể. Chúng tạo thành “đám mây số liệu” khá phức tạp và việc tìm hiểu thông tin từ đó gặp khó khăn. Chúng ta cần một phương pháp nào đó để có thể giải quyết khó khăn trên, mà trong đó ta có thể nhìn rõ hơn về sự tương quan giữa các chiều dữ liệu với nhau. Từ đó, ta dễ dàng đưa ra các liên kết ẩn của các chiều và làm việc với dữ liệu hiệu quả hơn. Với những ý tưởng ban đầu, ta xây dựng được phương pháp phân tích thành phần chính PCA. Phương pháp trên đóng vai trò quan trọng trong các ngành khoa học, kĩ thuật, thống kê, kinh tế,... Động lực nghiên cứu phương pháp phân tích thành phần chính: + 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ũ. + 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ũ. + 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. 2. Một số khái niệm toán trong thống kê: • Kỳ vọng (mean): giá trị mong muốn, biểu diễn giá trị trung bình của một biến. 𝑋=

𝑥1 + 𝑥2 + …+𝑥𝑁 𝑁

• Độ lệch chuẩn (standard deviation): thuật ngữ để đo tính biến động của giá trị mang tính thống kê. Nó cho thấy sự chênh lệch về giá trị của từng thời điểm đánh giá so với giá trị trung bình. 𝑋̂ = 𝑋 − 𝑋 • Phương sai (variance): một đại lượng đặc trưng cho độ phân tán của các dữ liệu so với giá trị trung bình của nó. Từ đó chúng ta dễ dàng hình dung được dữ liệu chúng ta đang xét. 𝜎 2 = (𝑋 − 𝑋)

2

• Hiệp phương sai (covariance): một đại lượng đo sự biến thiên cùng nhau của hai biến ngẫu nhiên (phân biệt với phương sai – đo mức độ biến thiên của 1 biến). Ký hiệu: cov(X, Y). 𝑐𝑜𝑣(𝑋, 𝑌) = (𝑋 − 𝑋)(𝑌 − 𝑌) • Ma trận hiệp phương sai: Trong thống kê, ta cần một thuật ngữ để thể hiện đầy đủ phương sai và hiệp phương sai của các biến với nhau. Từ đó, ta tạo ra ma trận hiệp

3

phương sai của tập hợp m biến ngẫu nhiên là một ma trận vuông hạng (m × m), trong đó các phần tử nằm trên đường chéo (từ trái sang phải, từ trên xuống dưới) lần lượt là phương sai tương ứng của các biến này, trong khi các phần tử còn lại (không nằm trên đường chéo) là các hiệp phương sai của đôi một hai biến ngẫu nhiên khác nhau trong tập hợp. 3. Cơ sở lý thuyết: • Nhận xét: - Với những ý tưởng ban đầu, ta mong muốn có thể tạo ra một không gian mới nhỏ hơn mà vẫn có thể giữ lại được các thông tin quan trọng. Nhưng ta gặp rắc rối với việc cân nhắc rằng ta có thể giảm được bao nhiêu chiều và đó là những chiều nào. Vì thế, ta xây dựng lên thuật ngữ phương sai hay còn gọi là độ phân tán của dữ liệu. Dựa vào so sánh giá trị phương sai giữa các chiều ta đưa đến mức độ quan trọng lượng thông tin mà chiều đó chứa được. Từ đó, ta có thể lược bỏ đi các chiều không quan trọng - có phương sai không đáng kể (≈ 0). - Theo định nghĩa của phương sai, phương sai của một bảng dữ liệu X ban đầu có giá trị xác định không đổi và bằng tổng phương sai theo từng chiều. Dữ liệu ban đầu X (D chiều) có phương sai theo từng chiều có giá trị đáng kể, có thể nói các chiều ban đầu của dữ liệu X đều có mực độ quan trọng nhất định. Ta không thể lược bỏ đi chiều của nó. Vì thế ta cần một phép biển đổi nào đó để quay các chiều của dữ liệu X đến khi có K chiều nhận giá trị phương sai lớn nhất. Vì phương sai của dữ liệu X là hằng số nên ta có thể nói (D – K) chiều còn lại có mức độ quan trọng rất ít (phương sai không đáng kể) và ta được phép lược bỏ các chiều đó đi. Cuối cùng, ta có thể biểu diễn X trên cơ sở mới với độ “mất mát” ít nhất trong không gian với số chiều nhỏ hơn. • Phương sai lớn nhất: Mục tiêu của chúng ta là chọn một phép biến đổi tuyến tính P của V sao cho phương sai của ảnh của X qua một phép biến đổi là lớn nhất. Giá trị trung bình của dữ liệu là: 𝑋 =

𝑥1 + 𝑥2 + …+𝑥𝑁 𝑁

.

Để đơn giản, ta xét phép biến đổi P lên không gian một chiều được sinh ra bởi vecto đơn vị u1, tức là u1Tu1 = 1. Phương sai của ảnh của X qua phép biến đổi là: 1 𝑁

𝑇 𝑇 2 𝑇 ∑𝑁 𝑛=1{𝑢1 𝑥𝑛 − 𝑢1 𝑥 } = 𝑢1 𝑆𝑢1, với

𝑆=

1 𝑁−1

𝑇

∑𝑁 𝑛=1(𝑥𝑛 − 𝑋) (𝑥𝑛 − 𝑋).

Tìm giá trị lớn nhất của 𝑢1𝑇 𝑆𝑢1 với điều kiện 𝑢𝑇 𝑢 = 1.

4

Sử dụng phương pháp nhân tử Lagrange của giải tích hàm nhiều biến, ta có hàm Lagrange: 𝐿 = 𝑢1𝑇 𝑆𝑢1 + 𝜆1 (1 − 𝑢1𝑇 𝑢1 ) = 0. Điểm dừng của hàm lagrange xảy ra khi 𝑆𝑢1 = 𝜆1 𝑢1 , hay 𝜆1 là trị riêng của S và u1 là vecto riêng của S tương ứng với trị riêng 𝜆1. Ngoài ra ta có 𝑢1𝑇 𝑆𝑢1 = 𝑢1𝑇 𝜆1 𝑢1 = 𝜆1 𝑢1𝑇 𝑢1 = 𝜆1 . Tóm lại, giá trị lớn nhất của phương sai bằng 𝜆1, khi ta chọn vecto u1 là vecto riêng của S tương ứng với trị riêng 𝜆1. Vecto riêng u1 được gọi là thành phần chính thứ nhất. 4. Các bước phân tích PCA: • Bước 1: Tính giá trị trung bình 𝑋 của X * Chú thích: Chuẩn hóa dữ liệu, tìm tọa độ mới của dữ liệu. • Bước 2: Tính vectơ 𝑋̂ = 𝑋 − 𝑋. Tính ma trận hiệp phương sai 𝑆 =

1 𝑁−1

𝑋̂ 𝑇 𝑋̂.

* Chú thích: Khi biểu diễn ma trận X trong không gian Rm, ta nhận thấy rằng các điểm dữ liệu sẽ phân tán xung quanh điểm giá trị trung bình. Để thuận tiện cho việc tính toán, ta tiến hành chuẩn hóa ma trận ban đầu về quanh gốc tọa độ. Việc thay đổi này không ảnh hưởng đến bản chất của hệ dữ liệu ban đầu. Khi này độ phân tán của hệ dữ liệu mới biểu diễn bởi 𝑋̂ quanh quanh gốc tọa độ O hoàn toàn giống với độ phân tán của hệ dữ liệu ban đầu X quanh điểm giá trị trung bình. Bước 3: Tìm trị riêng của S và sắp xếp theo giá trị giảm dần 𝜆1 > 𝜆2 > .... > 𝜆m và tìm các vecto riêng đơn vị ứng với các trị riêng. * Chú thích: Theo điểm dừng của hàm Lagrange, phương sai lớn nhất theo một chiều u1 nào đó chính là trị riêng. Việc sắp xếp các trị riêng theo giá trị giảm dần giúp ta hiệu quả trong việc so sánh và chọn ra các vecto có phương sai đáng kể (mức độ quan trọng đáng kể). • Bước 4: Chọn K trị riêng ban đầu và K vecto riêng đơn vị ứng với các trị riêng này. Lập ma trận A có các cột là các vecto riêng đã chọn. Ma trận A là phép biến đổi cần tìm. * Chú thích: Chọn ra K trị riêng có giá trị đáng kể để tạo ra không gian mới có K chiều thể hiện tốt nhất độ phân tán của dữ liệu X trên không gian mới. • Bước 5: Tính ảnh 𝐴𝑇 𝑋̂ 𝑇 của vecto 𝑋̂ . Dữ liệu X ban đầu được xấp xỉ bởi 𝑋 ≈ 𝐴𝑋̂ + 𝑋. Mỗi cột của A𝑋̂ 𝑇 chứa tọa độ của các hàng của ma trận 𝑋̂ trong cơ sở từ các cột của ma trận P (P là ma trận trực giao).

5

* Chú thích: Diễn đạt dữ liệu X trên chiều không gian mới, dấu xấp xỉ là do chúng ta đã lược bớt các chiều có phương sai không đáng kể nên dữ liệu X vẫn được thể hiện tốt nhất nhưng trên chiều dữ liệu nhỏ hơn. 5. Mô phỏng thuật toán:

6. Nhược điểm của phương pháp PCA: • Giả thiết về độ quan trọng của chiều dữ liệu: Mô hình PCA dựa trên giả thiết rằng chiều quan trọng dữ liệu là chiều có phương sai độ dữ liệu lớn. Tuy vậy trong thực tế, không phải lúc nào chiều phân bố dữ liệu lớn nhất cũng mang lại hiệu quả tốt nhất cho việc phân tích dữ liệu. • PCA rất nhạy cảm với nhiễu: Vẫn do giả thiết là phương sai của dữ liệu ảnh hưởng đến việc chọn ra chiều mới. Khi nhiễu xuất hiện, do độ lệch của điểm nhiễu này mà chiều có phương sai của dữ liệu lớn cũng bị ảnh hưởng rất đáng kể. • Thiếu sót thông tin: Mặc dù phân tích PCA sẽ giữ lại những chiều quan trọng nhất đối với bộ dữ liệu,

6

tuy vậy nếu sai sót trong việc chọn số chiều giữ lại thì lượng thông tin mà ta đánh mất sau quá trình phân tích này sẽ rất đáng kể. 7. Một số ứng dụng trong lĩnh vực khác: - Giảm dung lượng dữ liệu - Công nghệ thông tin (Machine learning) - Nhận diện khuôn mặt Ví dụ: Trong nhận diện khuôn mặt: + Tiền xử lý: Chuẩn hóa kích cỡ giữa ảnh trong cơ sở dữ liệu + Tách khuôn mặt: khuôn mặt trên ảnh được tách ra phần mặt, nó sẽ là các khuôn mặt cần tìm và chứng năng trích chọn đặc trưng sẽ sử dụng các ảnh được tách ra này. + Trích chọn đặc trưng: Tìm ra các đặc trưng chính của ảnh mặt, từ các đặc trưng này hình thành các vector đặc trưng, các vector này sẽ được sử dụng để đối sánh sự giống nhau giữa ảnh mặt cần tìm và ảnh mặt trogn CSDL. +Đối sánh: So sánh giữa các vector đặc trưng để chọn ra độ tương tự giữa ảnh cần tìm và ảnh trong CSDL.

II. Ứng dụng PCA trong hồi quy tuyến tính: 1. Định nghĩa: "Hồi quy tuyến tính" là một phương pháp thống kê để hồi quy dữ liệu với biến phụ thuộc có giá trị liên tục trong khi các biến độc lập có thể có một trong hai giá trị liên tục hoặc là giá trị phân loại. Nói cách khác "Hồi quy tuyến tính" là một phương pháp để dự đoán biến phụ thuộc (Y) dựa trên giá trị của biến độc lập (X). Nó có thể được sử dụng cho các trường hợp chúng ta muốn dự đoán một số lượng liên tục. Ví dụ, dự đoán giao thông ở một cửa hàng bán lẻ, dự đoán thời gian người dùng dừng lại một trang nào đó hoặc số trang đã truy cập vào một website nào đó v.v... 2. Mô tả thuật toán: Trong mô hình hồi quy tuyến tính, để tìm được đường thẳng (hay mặt phẳng) cuối cùng "khớp nhất" với bộ dữ liệu, ta phải tối thiểu "sự sai khác" giữa các điểm dữ liệu với các điểm mà mô hình hồi quy dự đoán. Các bài toán hồi thường được giải bằng phương pháp “bình phương cực tiểu”. Nhưng ngoài ra, trong một số mô hình hồi quy tuyến tính đơn giản, PCA cung cấp cho ta một định nghĩa của dạng sai khác là tổng bình phương khoảng cách từ các điểm dữ liệu tới "mặt phẳng" tạo bởi các thành phần chính sau khi phân tích PCA, Từ đó đưa cho hướng giải quyết khác để tìm đường thẳng (mặt phẳng) khớp nhất. 3. Ta đến với ví dụ minh họa hiểu rõ hơn về ứng dụng trên: Một công ty thức ăn nhanh phân tích dữ liệu của 6 năm gần đây và nhận thấy lợi nhuận hằng năm phụ thuộc vào số tiền dành cho quảng cáo. Ta thấy sự phụ thuộc này được biểu diễn bởi gần với hàm bậc nhất y = B0 + B1*x. Dưới đây là bảng số liệu thống kê (13; 60),(15; 75),(17; 90),(20; 96),(25; 102),(30, 120), đơn vị tính là

7

triệu đồng. Tìm đường hồi quy tuyến tính và dự đoán và dự đoán nếu công ty sử dụng 100 triệu tiền quảng cáo thì lợi nhuận trong năm đó công ty thu được là bao nhiêu. Bước 1: Giá trị trung bình của x1 là 𝑥 1 = 20, Giá trị trung bình của x2 là 𝑥 2 = 90.5 Bước 2: ̂=𝑋−X Tính vectơ X −5 −3 0 5 ̂ = [ −7 X −30.5 −15.5 −0.5 5.5 11.5 Bước 3: Tính ma trận hiệp phương sai 1 1 208 645 ] 𝑆= 𝑋̂ 𝑇 𝑋̂ = [ 𝑁−1 5 645 2203.5

10 ] 29.5

Bước 4: Xác định vecto riêng của ma trận hiệp sai, ta được e1 = [

0.2830 ] ứng với 0.9591

−0.9591 ] ứng với trị riêng còn lại. 0.2830 Kết luận: Theo định nghĩa PCA, đường hồi quy chính có chiều là thành phần chính ̂ thứ nhất e1 và đi qua giá trị trung bình X trị riêng lớn nhất và e2 = [

Vậy đường thẳng hồi quy là y =

0.9591 0.2830

x + 22.72 =3.389x + 22.72.

Dự đoán lợi nhuận nếu công ty sử dụng 100 triệu tiền quảng cáo: y(100) ≈ 361.62 triệu đồng. Vậy ngoài phương pháp “bình phương cực tiểu”, ta có thể sử dụng PCA để tìm đường hồi quy trong các mô hình hồi quy đơn giản. Hình ảnh trực quan của dữ liệu

8

III.

Tài liệu tham khảo: [1] Đặng Văn Vinh. Giáo Trình Đại Số Tuyến Tính. Nhà Xuất Bản Đại Học Quốc Gia TP.Hồ Chí Minh, 2020. [2] I.T. Jolliffe. Principal Component Analysis. Springer, 2nd edition, 2002. [3] Wikipedia contributors. Principal component analysis — Wikipedia, the free encyclopedia, 2020. [4] Naresh Kumar. Advantages and disadvantages of principal component analysis in machine learning, the professionals point. https://theprofessionalspoint.blogspot.com/2019/03/advantages-anddisadvantages-of4.html, 2020. [5] G. Strang. Introduction to Linear Algebra. Wellesley-Cambridge Press, 2003. [6] Wikipedia contributors. Linear regression — Wikipedia, the free encyclopedia, 2020. [7] Lexi Perez. Principal component analysis to address multicollinearity. https://www.whitman.edu/Documents/Academics/Mathematics/2017/Perez.pdf, 2017. [8] Trần Thanh Bình, Lê Quang Kỳ, Đỗ Nhật Hoàng, Võ Thục Khánh Huyền. Principal component analysis. https://pimavn.github.io/pdf/2018/student-papers/pca.pdf, 2018. [9] https://123doc.net/document/5869540-tieu-luan-mon-danh-gia-cam-quan-thuc-pham-

tim-hieu-veung-dung-cua-pca-trong-phan-tich-mo-ta-dinh-luong.htm. [10] https://www.slideshare.net/TuanRemy/thuat-toan-pca-full-2452017. [11] Wikipedia contributors. Total least squares — Wikipedia, the free encyclopedia, 2020. [12] Wikipedia contributors. Covariance matrix — Wikipedia, the free encyclopedia, 2020. [13] Wikipedia contributors. Covariance — Wikipedia, the free encyclopedia, 2020. [14] Machine Learning cơ bản contributors. Principal components analysis — Machine Learning cơ bản, 2020.

9