Bài giảng Học máy - Bài 7: Học máy không giám sát - Nguyễn Thanh Tùng

Học máy không giám sát
CSE 445: Học máy | Học kỳ 1, 2016-2017 1
Nguyễn Thanh Tùng
Khoa Công nghệ thông tin – Đại học Thủy Lợi
tungnt@tlu.edu.vn
Bài giảng có sử dụng hình vẽ trong cuốn sách “An Introduction to Statistical Learning with Applications in R” với sự
cho phép của tác giả, có sử dụng slides các khóa học CME250 của ĐH Stanford và IOM530 của ĐH Southern California
Website môn học: https://sites.google.com/a/wru.vn/cse445fall2016/
Học máy không giám sát
CSE 445: Học máy | Học kỳ 1, 2016-2017 2
• Học không giám sát: tập các công cụ thống kê xử
lý dữ liệu chỉ có biến đầu vào, không có biến đích
– Ta chỉ có X’s mà không có các nhãn Y
– Mục tiêu: phát hiện cácmẫu/các đặc tính của dữ liệu
• vd. trực quan hóa hoặc diễn giải dữ liệu nhiều chiều
Học có giám sát vs. không giám sát
Học máy có giám sát: cả X và Y đều đã biết
Học máy không giám sát: chỉ biết X
Học có giám sát Học không giám sát
CSE 445: Học máy | Học kỳ 1, 2016-2017 3
Học không giám sát
CSE 445: Học máy | Học kỳ 1, 2016-2017 4
• Ví dụ ứng dụng:
– Biết các mô ung thư của n bệnh nhân bị ung thư vú, cần xác định
các nhóm nhỏ (subtypes) chưa biết gây nên ung thư vú
– Các thí nghiệm về biểu diễn Gen 
chứa hàng ngàn biến
Figure1.3, ESL
Học không giám sát
• Ví dụ ứng dụng:
– Cho một tập các tài liệu văn bản, cần xác định tập các tài liệu có chung
chủ đề như thể thao, chính trị, ca nhạc,..
– Cho các ảnh khuôn mặt có
số chiều cao, tìm một biểu 
diễn đơn giản/thu gọn của 
các ảnh này để đưa vào bộ 
phân lớp nhận dạng khuôn
mặt
CSE 445: Học máy | Học kỳ 1, 2016-2017 5
(AT&T Laboratories 
Cambridge)
Học không giám sát
CSE 445: Học máy | Học kỳ 1, 2016-2017 6
• Tại sao học không giám sát luôn thách thức lớn?
– Phân tích khám phá dữ liệu (Exploratory data analysis) –
mục tiêu không được định nghĩa rõ ràng
– Khó đánh giá hiệu năng – không biết được đáp án đúng
(“right answer” unknown)
– Xử lý dữ liệu với số chiều lớn
Học không giám sát
CSE 445: Học máy | Học kỳ 1, 2016-2017 7
• Hai cách tiếp cận:
– Phân tích cụm (Cluster analysis)
• Xác định các nhóm mẫu đồng nhất (có các đặc tính chung)
– Giảm chiều dữ liệu (Dimensionality Reduction)
• Tìm cách biểu diễn với số chiều thấp hơn dựa trên tính chất
và trực quan hóa dữ liệu
Phân tích cụm
& K--means
CSE 445: Học máy | Học kỳ 1, 2016-2017 8
Phân cụm
CSE 445: Học máy | Học kỳ 1, 2016-2017 9
• Phân cụm: là tập các phương pháp nhằm tìm ra
các nhóm con trong dữ liệu
– Các mẫu có đặc điểm chung trong cùng 1 nhóm nhưng
khác với các mẫu ở ngoài nhóm
– Việc gom nhóm là phân tích cấu trúc dữ liệu nội tại, 
điều này khác với phân lớp
Phân cụm vs. Phân lớp
CSE 445: Học máy | Học kỳ 1, 2016-2017 10
Phân lớp
CSE 445: Học máy | Học kỳ 1, 2016-2017 11
Lớp “A” Lớp “B”
10
Phân lớp
CSE 445: Học máy | Học kỳ 1, 2016-2017 12
Lớp “A” Lớp “B”
1
Phân cụm
CSE 445: Học máy | Học kỳ 1, 2016-2017 13
Phân cụm
CSE 445: Học máy | Học kỳ 1, 2016-2017 14
Dữ liệu lấy từ: 
Phân cụm
CSE 445: Học máy | Học kỳ 1, 2016-2017 15
Dữ liệu lấy từ: 
Phân cụm
CSE 445: Học máy | Học kỳ 1, 2016-2017 16
• Các kiểu mô hình phân cụm
– Hai môhìnhphân cụmthôngdụng:
– Phươngphápdựa trên tâmcụm(Centroid-based)
– Phương pháp phân cấp (Hierarchical)
– Cácmôhìnhkhác:
– Phâncụmdựatrênmôhình (Model-based)
• Mỗi cụm được thể hiện bằng một phân bố thống kê tham số
• Dữ liệu là một hỗn hợp các phân bố
– Khái niệm phân cụm fuzzy cứng vs. mềm
• Cứng (Hard): Các mẫu được chia thành các cụm riêng biệt
• Mềm (Soft): Các mẫu có thể thuộc nhiều hơn 1 cụm
Phương pháp phân cấp
CSE 445: Học máy | Học kỳ 1, 2016-2017 17
• Phương pháp phân cấp (phân cụm cây)
– Các cụm dựa trên khoảng cách giữa các
mẫu
– Hiển thị theo phân cấp mà không theo cách
phân hoạch dữ liệu
Sørlie, Therese, et al. (2003) "Repeated 
observation of breast tumor subtypes in 
independent gene expression data sets,"PNAS.
Figure10.9 , ISL 2013
PhâncụmK--means
CSE 445: Học máy | Học kỳ 1, 2016-2017 18
• Gom nhóm dữ liệu thành K cụm riêng biệt
– Mỗi cụm K được định nghĩa bởi 1 véc tơ tâm cụm (centroid)
• Tâm cụm: giá trị trung bình của tất cả các đối tượng trong cụm
– Mỗi đối tượng gán cho 1 cụm đơn (tâm cụm gần nhất)
– Yêu cầu số lượng cụm đầu vào K
– “Phân cụm tốt” cực tiểu sự biến đổi giữa các cụm
• “Tính tương tự (Similarity)” đo theo khoảng cách Euclidean
PhâncụmK--means
CSE 445: Học máy | Học kỳ 1, 2016-2017 19
*Một số hình vẽ trong bài
trình bày này được lấy từ
cuốn "An Introduction to
Statistical Learning, with 
applications in R" (Springer, 
2013) với sự đồng ý của các
tác giả: G. James, D. Witten, T. 
Hastie and R. Tibshirani
Figure10.5 , ISL 2013*
PhâncụmK--means
CSE 445: Học máy | Học kỳ 1, 2016-2017 20
Figure10.5 , ISL 2013
PhâncụmK--means
CSE 445: Học máy | Học kỳ 1, 2016-2017 21
• Các tâm cụm cực tiểu sự biến đổi giữa các cụm
– Các tâm cụm (trung tâm của cụm):
• Bài toán cực tiểu hóa này là tối ưu tổ hợp
– Giải pháp cho cực tiểu hóa địa phương ta sử dụng phương pháp lặp
ThuậttoánK--means
CSE 445: Học máy | Học kỳ 1, 2016-2017 22
1) Khởi tạo chọn ngẫu nhiên K tâm cụm
2) Phân hoạch dữ liệu bằng cách gán mỗi đối tượng vào cụm
mà nó gần tâm nhất
3) Tính các tâm cụm mới trong mỗi cụm
4) Lặp lại 2 và 3 cho đến khi thỏa mãn điều kiện
– “thỏa mãn điều kiện” khi các tâm cụm ổn định và các đối tượng
không dịch chuyển giữa các cụm
ThuậttoánK--means
CSE 445: Học máy | Học kỳ 1, 2016-2017 23
Khởi tạo tâm cụm
ThuậttoánK--means
CSE 445: Học máy | Học kỳ 1, 2016-2017 24
Khởi tạo tâm cụm
Gán các cụm ban đầu
ThuậttoánK--means
CSE 445: Học máy | Học kỳ 1, 2016-2017 25
Khởi tạo tâm cụm
Gán các cụm ban đầu
Cập nhật các tâm cụm
ThuậttoánK--means
CSE 445: Học máy | Học kỳ 1, 2016-2017 26
Khởi tạo tâm cụm
Gán các cụm ban đầu
Cập nhật các tâm cụm
Gán lại các cụm
ThuậttoánK--means
CSE 445: Học máy | Học kỳ 1, 2016-2017 27
Khởi tạo tâm cụm
Gán các cụm ban đầu
Cập nhật các tâm cụm
Gán lại các cụm
Cập nhật tâm cụm
ThuậttoánK--means
CSE 445: Học máy | Học kỳ 1, 2016-2017 28
Khởi tạo tâm cụm
Gán các cụm ban đầu
Cập nhật các tâm cụm
Gán lại các cụm
Cập nhật tâm cụm
Gán lại các cụm
ThuậttoánK--means
CSE 445: Học máy | Học kỳ 1, 2016-2017 29
Khởi tạo tâm cụm
Gán các cụm ban đầu
Cập nhật các tâm cụm
Gán lại các cụm
Cập nhật tâm cụm
Gán lại các cụm
Cập nhật tâm cụm
ThuậttoánK--means
CSE 445: Học máy | Học kỳ 1, 2016-2017 30
Khởi tạo tâm cụm
Gán các cụm ban đầu
Cập nhật các tâm cụm
Gán lại các cụm
Cập nhật tâm cụm
Gán lại các cụm
Cập nhật tâm cụm
Gán lại các cụm
ThuậttoánK--means
CSE 445: Học máy | Học kỳ 1, 2016-2017 31
Khởi tạo tâm cụm
Gán các cụm ban đầu
Cập nhật các tâm cụm
Gán lại các cụm
Cập nhật tâm cụm
Gán lại các cụm
Cập nhật tâm cụm
Gán lại các cụm
Thỏamãn điều kiện
ThuậttoánK--means
CSE 445: Học máy | Học kỳ 1, 2016-2017 32
• Khởi tạo không tốt dẫn đến kết quả phân cụm kém
Khởi tạo tâm cụm
CSE 445: Học máy | Học kỳ 1, 2016-2017 33
• Chọn ngẫu nhiên trong K đối tượng
• Phân hoạch ngẫu nhiên dữ liệu
• Chọn K điểm xa nhau “far apart”
• Khởi tạo bằng cách sử dụng kết quả của phương pháp
phân cụm khác
Bao nhiêu cụm?
CSE 445: Học máy | Học kỳ 1, 2016-2017 34
• K-means yêu cầu đầu vào K (# cụm)
– Ta cần hiểu về bài toán ứng dụng để chọn K
– Ngược lại, việc chọn K được xác định từ dữ liệu
CSE 445: Học máy | Học kỳ 1, 2016-2017 35
Bao nhiêu cụm?
CSE 445: Học máy | Học kỳ 1, 2016-2017 36
• Không thể tính được giá trị K để cực tiểu mục tiêu J
– J giảm đồng thời với tăngK
• Phương pháp dựa trên kinh nghiệm (Heuristic):
– Với mỗi giá trị ứng viên của K,
– Tính toán phân cụm bằng K--meansM lần, tìmmụctiêu
nhỏnhất JK
– Tìm điểm “khuỷu tay (elbow)” trong đường mục tiêu
(K vs JK)
Bao nhiêu cụm?
CSE 445: Học máy | Học kỳ 1, 2016-2017 37
Bao nhiêu cụm?
CSE 445: Học máy | Học kỳ 1, 2016-2017 38
CSE 445: Học máy | Học kỳ 1, 2016-2017 39
• Ưu điểm
– Dễ cài đặt
– Luôn hội tụ với số lần lặp ít
– Có thể triển khai trên những tập dữ liệu với số chiều lớn
• Nhược điểm
– Giá trị K là tham số đầu vào (khó xác định tối ưu)
– Thuật toán lặp trả về cực tiểu địa phương*
Thuật toán K--means
CSE 445: Học máy | Học kỳ 1, 2016-2017 40
Thuật toán K--means
CSE 445: Học máy | Học kỳ 1, 2016-2017 4140
Thuật toán K--means
CSE 445: Học máy | Học kỳ 1, 2016-2017 42
• Ưu điểm
– Dễ cài đặt
– Luôn hội tụ với số lần lặp ít
– Có thể triển khai trên những tập dữ liệu với số chiều lớn
• Nhược điểm
– Giá trị K là tham số đầu vào (khó xác định tối ưu)
– Thuật toán lặp trả về cực tiểu địa phương*
– Giả thiết tất cả các cụm hình cầu và có kích thước xấp xỉ nhau *
Thuật toán K--means
CSE 445: Học máy | Học kỳ 1, 2016-2017 43
Thuật toán K--means
CSE 445: Học máy | Học kỳ 1, 2016-2017 44
Thuật toán K--means
CSE 445: Học máy | Học kỳ 1, 2016-2017 45
• Ưu điểm
– Dễ cài đặt
– Luôn hội tụ với số lần lặp ít
– Có thể triển khai trên những tập dữ liệu với số chiều lớn
• Nhược điểm
– Giá trị K là tham số đầu vào (khó xác định tối ưu)
– Thuật toán lặp trả về cực tiểu địa phương*
– Giả thiết tất cả các cụm hình cầu và có kích thước xấp xỉ nhau *
– Nhạy với các phần tử ngoại lai*
Thuật toán K--means
CSE 445: Học máy | Học kỳ 1, 2016-2017 46
Thuật toán K--means
CSE 445: Học máy | Học kỳ 1, 2016-2017 47
Thuật toán K--means
CSE 445: Học máy | Học kỳ 1, 2016-2017 48
• Ưu điểm
– Dễ cài đặt
– Luôn hội tụ với số lần lặp ít
– Có thể triển khai trên những tập dữ liệu với số chiều lớn
• Nhược điểm
– Giá trị K là tham số đầu vào (khó xác định tối ưu)
– Thuật toán lặp trả về cực tiểu địa phương*
– Giả thiết tất cả các cụm hình cầu và có kích thước xấp xỉ nhau *
– Nhạy với các phần tử ngoại lai*
– *một số nhược điểm được khắc phục bằng vài biến thể của K‐means
Thuật toán K--means
CSE 445: Học máy | Học kỳ 1, 2016-2017 49
• Khắc phục nhược điểm
– Khởi tạo không tốt
ta chạy thuật toán nhiều lần
– K-medians: Tâm cụm được tính bằng giá trị trung vị thay
cho giá trị trung bình của K-means
– K--medoids
• Yêu cầu: “tâm cụm” phải là 1 trong các điểm dữ liệu
• xử lý tốt hơn các phần tử ngoại lai
• linh hoạt hơn – có thể dùng nhiều độ đo
• nhưng thời gian tính toán lâu hơn vì phải tính các tâm cụm
ThuậttoánK--means
Ví dụ: Phân đoạn/nén ảnh
CSE 445: Học máy | Học kỳ 1, 2016-2017 50
• Ảnh
điểmảnh (pixels)
 véc tơ RGB (colors)
• Áp dụng K-means tập hợp các véc tơ RGB
– Một véc tơ RGB ứng với 1 điểm ảnh
– Các cụm thể hiện các màu giống nhau
• Thay thế mỗi điểm ảnh bằng một tâm cụm liên
quan
– Kết quả trên ảnh với K màu khác nhau
50
Phân đoạn/nén ảnh
CSE 445: Học máy | Học kỳ 1, 2016-2017 51
Phân đoạn/nén ảnh
CSE 445: Học máy | Học kỳ 1, 2016-2017 52
Phân đoạn/nén ảnh
CSE 445: Học máy | Học kỳ 1, 2016-2017 53
Phân đoạn/nén ảnh
CSE 445: Học máy | Học kỳ 1, 2016-2017 54
Phân đoạn/nén ảnh
CSE 445: Học máy | Học kỳ 1, 2016-2017 55
Phân đoạn/nén ảnh
CSE 445: Học máy | Học kỳ 1, 2016-2017 56
ThuậttoánK--means
CSE 445: Học máy | Học kỳ 1, 2016-2017 57
• Chúng ta thực hiện thuật toán với dữ liệu có 2--3 
thuộc tính (rất dễ để minh họa)
– Trong thực tế, ta thường gặp nhiều hơn 2 thuộc
tính khi phân tích dữ liệu
• Phân cụm sẽ khó khăn hơn rất nhiều khi gặp số
chiều lớn
Phân cụm chữ viết tay
CSE 445: Học máy | Học kỳ 1, 2016-2017 58
MNIST dataset: 
Phân cụm chữ viết tay
CSE 445: Học máy | Học kỳ 1, 2016-2017 59
Phân cụm chữ viết tay
CSE 445: Học máy | Học kỳ 1, 2016-2017 60
• Áp dụng K--means, sử dụng  = 10
Phân cụm chữ viết tay
CSE 445: Học máy | Học kỳ 1, 2016-2017 6061
• Phân cụm theo phương pháp K-Means yêu cầu chọn tham
số đầu vào là số lượng cụm K
• Nếu ta không muốn làm theo cách trên, ta có thể dùng
phương pháp phân cụm phân cấp
• Phân cụm phân cấp có ưu điểm là hiển thị các quan sát
(mẫu) dạng hình cây nên dễ hình dung, được gọi là phân
cụm theo cấu trúc cây (Dendogram)
CSE 445: Học máy | Học kỳ 1, 2016-2017 62
Phân cụm phân cấp
• Đầu tiên nhập các điểm gần nhau nhất (5 và 7)
• Độ cao của việc hợp nhất (theo trục dọc) phản ánh độ tương
tự của các điểm
• Sau khi các điểm được hợp nhất, chúng được xem như 1 
mẫu để tiếp tục tiến hành giải thuật
3
4
1 6
9
2
8
5 7
0
.
0
0
.
5
1
.
0
1
.
5
2
.
0
2
.
5
3
.
0
1
2
3
4
5
6
7
8
9
−1.5 −1.0 −0.5 0.0 0.5 1.0
−
1
.
5
−
1
.
0
−
0
.
5
0
.
0
0
.
5
X 1
X
2
CSE 445: Học máy | Học kỳ 1, 2016-2017 63
Phân cụm phân cấp
Diễn giải phương pháp phân cấp
• Mỗi “lá” của cây phân cấp biểu diễn một
trong 45 mẫu
• Phần đáy của cây, mỗi mẫu là 1 lá riêng biệt. 
Tuy nhiên, càng lên cao các lá sẽ hợp nhất với
nhau. Việc này thể hiện các mẫu có độ tương
tự với các mẫu khác. 
• Khi di chuyển cao lên phần ngọn của cây, số
lượng mẫu đã được hợp nhất. Trước đó
(phần dưới của cây) với 2 mẫu hợp nhất, 
chúng có chung đặc tính (gần) với nhau.
−6 −4 −2 0 2
−
2
0
2
4
X 1
X
2
CSE 445: Học máy | Học kỳ 1, 2016-2017 64
Lựa chọn các cụm
Để chọn các cụm ta kẻ đường thẳng ngang cây phân cấp
Ta có thể chọn số lượng cụm tùy thuộc vào vị trí đường kẻ
One Cluster Two Clusters Three Clusters
CSE 445: Học máy | Học kỳ 1, 2016-2017 65
Giải thuật (trộn các cụm)
Phân cụm bằng cấu trúc cây:
• Khởi tạo với mỗi điểm là 1 cụm riêng biệt (n cụm), chính là 1 
nút trong dendrogram
• Tính toán độ tương tự (gần) giữa các điểm/cụm
• Hợp nhất 2 cụm mà chúng có độ tương tự cao nhất, ta còn
lại n-1 cụm
• Hợp nhất 2 cụm tiếp theo có độ tương tự cao nhất, ta còn
lại n-2 cụm
• Quá trình trên tiếp tục cho đến khi chỉ còn 1 cụm (là nút gốc
trong dendrogram)
CSE 445: Học máy | Học kỳ 1, 2016-2017 66
Ví dụ
Bắt đầu với 9 cụm
Hợp nhất 5 và 7
Hợp nhất 6 và 1
Hợp nhất cụm (5,7) với 8.
Quá trình tiếp tục cho đến
khi tất cả các cụm được hợp
nhất.
1
2
3
4
5
6
7
8
9
−1.5 −1.0 −0.5 0.0 0.5 1.0
−
1
.
5
−
1
.
0
−
0
.
5
0
.
0
0
.
5
1
2
3
4
5
6
7
8
9
−1.5 −1.0 −0.5 0.0 0.5 1.0
−
1
.
5
−
1
.
0
−
0
.
5
0
.
0
0
.
5
1
2
3
4
5
6
7
8
9
−1.5 −1.0 −0.5 0.0 0.5 1.0
−
1
.
5
−
1
.
0
−
0
.
5
0
.
0
0
.
5
1
2
3
4
5
6
7
8
9
−1.5 −1.0 −0.5 0.0 0.5 1.0
−
1
.
5
−
1
.
0
−
0
.
5
0
.
0
0
.
5
X 1X 1
X 1X 1
X
2
X
2
X
2
X
2
CSE 445: Học máy | Học kỳ 1, 2016-2017 67
Ta định nghĩa sự khác biệt ntn?
Việc triển khai phương pháp phân cấp cần giải quyết vấn
đề khá hiển nhiên, đó là làm sao để định nghĩa sự khác
biệt (dissimilarity) hoặc mối liên kết (linkage) giữa cụm
hợp nhất (5, 7) và cụm 8?
Có 4 lựa chọn:
Liên kết đầy (Complete Linkage)
Liên kết đơn (Single Linkage)
Liên kết trung bình giữa các nhóm (Average Linkage)
Liên kết tâm (Centroid Linkage)
CSE 445: Học máy | Học kỳ 1, 2016-2017 68
Các phương pháp liên kết
Liên kết đầy: Khoảng cách giữa 2 cụm là khoảng
cách lớn nhất giữa 2 mẫu tương ứng của 2 cụm đó
• Nhạy cảm (gặp lỗi phân cụm) đối với các ngoại
lai (outliers)
• Có xu hướng sinh ra các cụm có dạng “bụi cây” 
(clumps)
CSE 445: Học máy | Học kỳ 1, 2016-2017 69
+
+
C1
C2
[Liu, 2006]
Các phương pháp liên kết
Liên kết đơn: Khoảng cách giữa 2 cụm là khoảng cách
nhỏ nhất giữa các mẫu (các thành viên) của 2 cụm đó. 
Có xu hướng sinh ra các cụm có dạng “chuỗi dài” (long 
chain)
CSE 445: Học máy | Học kỳ 1, 2016-2017 70
+
+
C1
C2
[Liu, 2006]
Các phương pháp liên kết
Liên kết trung bình: Khoảng cách trong liên kết trung bình (Average-link) là sự thỏa 
hiệp giữa các khoảng cách trong liên kết hoàn toàn (Complete-link) và liên kết đơn
(Single-link)
• Để giảm mức độ nhạy cảm (khả năng lỗi) của phương pháp phân cụm dựa 
trên liên kết đầy đối với các ngoại lai (outliers)
• Để giảm xu hướng sinh ra các cụm có dạng “chuỗi dài” của phương pháp 
phân cụm dựa trên liên kết đơn (dạng “chuỗi dài” không phù hợp với khái 
niệm tự nhiên của một cụm)
■ Khoảng cách giữa 2 cụm là khoảng cách trung bình của tất cả các cặp mẫu (mỗi 
mẫu thuộc về một cụm)
CSE 445: Học máy | Học kỳ 1, 2016-2017 71
Các phương pháp liên kết
Liên kết tâm: Khoảng cách giữa các tâm của các mẫu
tương ứng
CSE 445: Học máy | Học kỳ 1, 2016-2017 72
+
+
C1
C2
Mối liên kết rất quan trọng
Dưới đây ta có 3 kết quả phân cụm trên cùng 1 bộ dữ liệu
Phương pháp tính mối liên kết khác nhau nhưng kết quả đem lại rất khác xa nhau
Phương pháp liên kết đầy và liên kết trung bình dường như có cỡ cụm như nhau, 
tuy nhiên liên kết đơn lại cho số cụm nhiều hơn vì mỗi lá của cây được hợp nhất
từng lần một
CSE 445: Học máy | Học kỳ 1, 2016-2017 73
Câu hỏi?
CSE 445: Học máy | Học kỳ 1, 2016-2017 74
Giảm chiều dữ liệu
CSE 445: Học máy | Học kỳ 2, 2015-2016 75
Giảm chiều dữ liệu
CSE 445: Học máy | Học kỳ 2, 2015-2016 76
S
e
c
o
n
d
p
r
i
n
c
i
p
a
l
c
o
m
p
o
n
e
n
t
−1.0 −0.5 0.0 0.5
First principal component
1.0
−
1
.
0
−
0
.
5
0
.
0
0
.
5
1
.
0
•
•
•
•
•
• •
•
•
••
• • •••
• • •
•••
••
• •• •
•
•
•
•
•
•
• •
•
•
•
•
•
•
•
•
• •
•
• •
••• •
••
•
•
•
•
•
•
•
•
• ••• •
•
•
•
• •
•
•
•
•
••
•
•
• •
•
• •
•
Phép chiếu
CSE 445: Học máy | Học kỳ 2, 2015-2016 77
Phân tích thành phần chính
Principal ComponentAnalysis (PCA)
CSE 445: Học máy | Học kỳ 2, 2015-2016 78
Phân tích thành phần chính
CSE 445: Học máy | Học kỳ 2, 2015-2016 79
• Khi không cần giữ các đặc trưng gốc (feature), PCA là
phương pháp hiệu quả để giảm chiều dữ liệu
• 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ũ
• PCA đảm bảo độ biến thiên (variability) của dữ liệu 
trên mỗi chiều mới
nguồn: 
Phân tích thành phần chính
CSE 445: Học máy | Học kỳ 2, 2015-2016 80
• 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ể 
• 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ũ
• 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 (vẫn biểu diễn tốt dữ liệu 
ban đầu) nguồn: 
Phân tích thành phần chính
CSE 445: Học máy | Học kỳ 2, 2015-2016 81
• 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á 
• Ví dụ: Thị trường ta quan tâm có hàng ngàn mã cổ 
phiếu làm cách nào để khi quan sát dữ liệu từ hàng 
ngàn cổ phiếu này ta hình dung được xu hướng của 
toàn thị trường
nguồn: 
CSE 445: Học máy | Học kỳ 2, 2015-2016 82
Phân tích thành phần chính
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.
nguồn: 
Phân tích thành phần chính
CSE 445: Học máy | Học kỳ 2, 2015-2016 83
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.
nguồn: 
Thuật toán PCA
CSE 445: Học máy | Học kỳ 2, 2015-2016 84
Cho ma trận:  = {	
 ∈ ℛ
×}
1. Tiền xử lý dữ liệu: Chuẩn hóa dữ liệu của ma trận . Có 2 cách
thường dùng:
• Centered PCA: mang tất cả các biến (các cột của ) về cùng 
một gốc tọa độ
• Normed PCA: mang tất cả các biến về cùng một gốc tọa độ, 
đồng thời chuẩn hóa về cùng một độ lệch chuẩn (standard-
deviation) bằng 1
• Sau bước tiền xử lí, ma trận 	sẽ là đầu vào cho bước tiếp theo.
Thuật toán PCA
CSE 445: Học máy | Học kỳ 2, 2015-2016 85
2. Xây dựng không gian mới
• Tính ma trận hiệp phương sai của các đặc trưng (cột) trong 
 =   ∈ ℛ×
• Tính p giá trị riêng λi (i=1..p) và véc-tơ riêng ui của ma trận .
• Sắp xếp giá trị riêng và véc-tơ riêng theo thứ tự giảm dần. Khi
đó các trục của không gian mới chính là các véc-tơ riêng ui
(chúng trực giao-vuông góc đôi một).
Thuật toán PCA
CSE 445: Học máy | Học kỳ 2, 2015-2016 86
3. Chuyển dữ liệu từ không gian ban đầu vào không gian mới
• Thông thường, ta chọn k véc-tơ riêng đầu tiên trong p véc-tơ
xếp theo thứ tự giảm dần (k<p)
• Gọi: 
• Khi đó tọa độ các điểm trong hệ tọa độ mới là:  = 
Questions?
CSE 445: Học máy | Học kỳ 2, 2015-2016 87