lOMoARcPSD| 36667950
THUẬT TOÁN PHÂN CỤM K-TRUNG BÌNH •Giới thiệu •Mô tả dữ liệu •Hàm mất mát và bài toán tối ưu •Mô tả bài toán •Ưu iểm, nhược
… những bước chập chững vào thế giới Dữ liệu lớn … TS. Trịnh Hoàng Nam 1 lOMoARcPSD| 36667950
THUẬT TOÁN PHÂN CỤM K-TRUNG BÌNH •Giới thiệu
– Một trong những thuật toán cơ bản nhất trong học không giám sát
– Phân dữ liệu thành các cụm (cluster) khác nhau saocho dữ liệu
trong cùng một cụm có tính chất giống nhau
• Không biết nhãn của từng iểm dữ liệu
• Một cụm có thể ược ịnh nghĩa là tập hợp các iểm có vector ặc trưng gần nhau.
• Việc tính toán khoảng cách phụ thuộc vào từng loại dữ liệu,trong ó khoảng cách
Euclid ược sử dụng phổ biến nhất
… những bước chập chững vào thế giới Dữ liệu lớn … TS. Trịnh Hoàng Nam
THUẬT TOÁN PHÂN CỤM K-TRUNG BÌNH •Giới thiệu
Điểm dữ liệu (mới) gần tâm của cụm nào nhất sẽ thuộc cụm ó
… những bước chập chững vào thế giới Dữ liệu lớn … TS. Trịnh Hoàng Nam 2 lOMoARcPSD| 36667950
THUẬT TOÁN PHÂN CỤM K-TRUNG BÌNH •Giới thiệu – Mục ích • Từ dữ liệu ịnh tâm mỗi cụm và phân các – Giả ịnh • Mỗi
… những bước chập chững vào thế giới Dữ liệu lớn … TS. Trịnh Hoàng Nam
THUẬT TOÁN PHÂN CỤM K-TRUNG BÌNH •Mô tả dữ liệu – Đầu vào • N
ược ghép lại thành ma trận X = [x1, x ,
…, x (mỗi x là một iểm dữ liệu d chiều) • K < N là số cụm – Đầu ra
• Các tâm cụm m , m , …, m ∈R và nhãn yi = k của mỗi iểm dữ liệu xi (k {1..K})
… những bước chập chững vào thế giới Dữ liệu lớn … TS. Trịnh Hoàng Nam 3 lOMoARcPSD| 36667950
THUẬT TOÁN PHÂN CỤM K-TRUNG BÌNH •Mô tả dữ liệu – Ma trận i nhãn Y ∈R • Nhãn k của iểm dữ liệu x ược thể hiện dưới dạng một vector yi∈R1×K, sao cho: • Ví dụ: – Nếu – Nếu
… những bước chập chững vào thế giới Dữ liệu lớn … TS. Trịnh Hoàng Nam
THUẬT TOÁN PHÂN CỤM K-TRUNG BÌNH
•Hàm mất mát và bài toán tối ưu
– Gọi mk∈Rd là tâm của cụm thứ k. Giả sử một iểm dữ liệu xi ược
phân vào cụm k, sai số trong trường hợp này là (xi−mk).
– Vector sai số này càng gần với vector không càng tốt,hay khoảng
cách Euclid 𝑥𝑥 − 𝑥𝑥 càng nhỏ càng tốt 𝑥𝑥 − 𝑥𝑥
= 𝑥𝑥𝑥 𝑥𝑥 − 𝑥𝑥 =
𝑥𝑥𝑥 𝑥𝑥 − 𝑥𝑥
do xi phân vào cụm k nên yik=1 và yij=0 với j k
… những bước chập chững vào thế giới Dữ liệu lớn … TS. Trịnh Hoàng Nam 4 lOMoARcPSD| 36667950
THUẬT TOÁN PHÂN CỤM K-TRUNG BÌNH
•Hàm mất mát và bài toán tối ưu
– Vector sai số này càng gần với vector không càng tốt,hay khoảng
cách Euclid 𝑥𝑥 − 𝑥𝑥 càng nhỏ càng tốt 𝑥𝑥 − 𝑥𝑥
= 𝑥𝑥𝑥 𝑥𝑥 − 𝑥𝑥 =
𝑥𝑥𝑥 𝑥𝑥 − 𝑥𝑥
– Sai số cho toàn bộ dữ liệu (hàm mất mát) 1 𝑥 𝑥, 𝑥 =
𝑥𝑥𝑥 𝑥𝑥 − 𝑥𝑥 𝑥
… những bước chập chững vào thế giới Dữ liệu lớn … TS. Trịnh Hoàng Nam
THUẬT TOÁN PHÂN CỤM K-TRUNG BÌNH •Hàm mất mát và bài toán tối ưu thỏa mãn – Hướng tiếp cận
… những bước chập chững vào thế giới Dữ liệu lớn … TS. Trịnh Hoàng Nam 5 lOMoARcPSD| 36667950
THUẬT TOÁN PHÂN CỤM K-TRUNG BÌNH •Mô tả thuật toán
– Đầu vào: Ma trận dữ liệu X∈Rd×N và số cụm cần tìm K– Đầu ra: Ma trận tâm cụm M∈Rd×K và ma trận nhãn Y∈RN×K. 1. Chọn K
iểm bất kỳ trong tập huấn luyện làm tâm cụm ban ầu.
2. Phân mỗi iểm dữ liệu vào cụm có tâm gần nó nhất.
3. Nếu việc phân cụm dữ liệu vào từng cụm ở bước 2 không thay ổi so với vòng
lặp trước nó thì dừng thuật toán.
4. Cập nhật tâm cụm bằng cách lấy trung bình cộng của các iểm ã ược gán vào cụm ó sau bước 2. 5. Quay lại bước 2.
… những bước chập chững vào thế giới Dữ liệu lớn … TS. Trịnh Hoàng Nam
THUẬT TOÁN PHÂN CỤM K-TRUNG BÌNH •Ví dụ Tính khoảng cách từ
… những bước chập chững vào thế giới Dữ liệu lớn … TS. Trịnh Hoàng Nam 6 lOMoARcPSD| 36667950
THUẬT TOÁN PHÂN CỤM K-TRUNG BÌNH •Ví dụ D1= 0 1 3.6 5 c1(1,1) 3.1 2.4 0.5 1.9 c2(11/3,8/3) A B C D 1 2 4 5 X 1 1 3 4 Y Tính khoảng cách từ
… những bước chập chững vào thế giới Dữ liệu lớn … TS. Trịnh Hoàng Nam 7 lOMoARcPSD| 36667950
THUẬT TOÁN PHÂN CỤM K-TRUNG BÌNH •Ví dụ
D2= 0.5 0.5 3.2 4.6 C1 (1.5,1) Tính khoảng cách từ 4.3 3.5 0.7 0.7 C2 (4.5, 3.5) A B C D 1 2 4 5 X Bước 7: Tính lại 1 1 3 4 Y tâm C1 (1.5,1) C2 (4.5,3.5) Bước 9:
Nhóm các ối tượng vào nhóm gần nhất
… những bước chập chững vào thế giới Dữ liệu lớn … TS. Trịnh Hoàng Nam
THUẬT TOÁN PHÂN CỤM K-TRUNG BÌNH •Ví dụ
… những bước chập chững vào thế giới Dữ liệu lớn … TS. Trịnh Hoàng Nam 8 lOMoARcPSD| 36667950
THUẬT TOÁN PHÂN CỤM K-TRUNG BÌNH •Ưu iểm, nhượciểm – Ưu iểm • Đơn giản, dễ thực hiện • Dễ giải thích kết quả – Nhược iểm ầu iểm dữ liệu ngang nhau
… những bước chập chững vào thế giới Dữ liệu lớn … TS. Trịnh Hoàng Nam
BỘ PHÂN LOẠI NAÏVE BAYES •Giới thiệu •Mô tả bài toán •Điều kiện •Ưu iểm, nhược
… những bước chập chững vào thế giới Dữ liệu lớn … TS. Trịnh Hoàng Nam 9 lOMoARcPSD| 36667950
BỘ PHÂN LOẠI NAÏVE BAYES •Giới thiệu
– Xét các bài toán phân loại với C nhãn khác nhau. – Xác ịnh xác suất ể
iểm dữ liệu x có nhãn là c
• p(y = c|x), hoặc viết gọn thành p(c|x).
– Theo ó, nhãn của mỗi iểm dữ liệu là nhãn có xác suất rơi vào cao nhất 𝑥 = argmax 𝑥(𝑥|𝑥) ∈{ … }
… những bước chập chững vào thế giới Dữ liệu lớn … TS. Trịnh Hoàng Nam
BỘ PHÂN LOẠI NAÏVE BAYES •Giới thiệu 𝑥 = argmax 𝑥(𝑥|𝑥) ∈{ … } Quy tắc Bayes 𝑥 𝑥 𝑥 𝑥(𝑥) 𝑥 = argmax ∈{ … } 𝑥(𝑥)
p(x) không phụ thuộc vào c
𝑥 = argmax 𝑥 𝑥 𝑥 𝑥(𝑥) ∈{ … }
… những bước chập chững vào thế giới Dữ liệu lớn … TS. Trịnh Hoàng Nam 10 lOMoARcPSD| 36667950
BỘ PHÂN LOẠI NAÏVE BAYES •Giới thiệu
𝑥 = argmax 𝑥 𝑥 𝑥 𝑥(𝑥) ∈{ … }
– Nếu tập huấn luyện lớn, p(c) ược tính theo phương pháp ước
lượng hợp lý cực ại (Maximum Likelihood Estimation - MLE)
– Ngược lại, p(c) ược tính theo phương pháp ước lượng hậu nghiệm cực
ại (Maximum a Posteriori Estimation – MAP)
… những bước chập chững vào thế giới Dữ liệu lớn … TS. Trịnh Hoàng Nam
BỘ PHÂN LOẠI NAÏVE BAYES •Giới thiệu Giả ịnh naïve Bayes
… những bước chập chững vào thế giới Dữ liệu lớn … TS. Trịnh Hoàng Nam 11 lOMoARcPSD| 36667950
BỘ PHÂN LOẠI NAÏVE BAYES •Giới thiệu
– Xét các bài toán phân loại với C nhãn khác nhau. – Xác ịnh xác suất ể
iểm dữ liệu x có nhãn là c
• p(y = c|x), hoặc viết gọn thành p(c|x). – Giả ịnh naïve Bayes
• Các thành phần của biến ngẫu nhiên x ộc lập với nhau khi ã biết c
– Bộ phân loại naïve Bayes (NBC)
• Phương pháp xác ịnh nhãn của dữ liệu dựa trên giả ịnh naïve Bayes
… những bước chập chững vào thế giới Dữ liệu lớn … TS. Trịnh Hoàng Nam
BỘ PHÂN LOẠI NAÏVE BAYES •Mô tả thuật toán – Mỗi ví dụ học x
ược biểu diễn bởi 2 thành phần:
• Mô tả của ví dụ x = (x1, x2, …, xd), trong ó xi R
• Nhãn lớp c ( C, với C là tập các nhãn lớp ược xác ịnh trước) – Bước huấn luyện
• Các phân phối p(c) và p(xi|c), i=1…d ược xác ịnh dựa vào dữ liệu huấn luyện.
– Bước kiểm tra: nhãn của một iểm dữ liệu mới x ược xác ịnh bởi 𝑥 = argmax 𝑥(𝑥) 𝑥(𝑥𝑥|𝑥) ∈{ … }
… những bước chập chững vào thế giới Dữ liệu lớn … TS. Trịnh Hoàng Nam 12 lOMoARcPSD| 36667950
BỘ PHÂN LOẠI NAÏVE BAYES • Mô tả thuật toán – Bước huấn luyện
• Các phân phối p(c) và p(xi|c), i=1…d
ược xác ịnh dựa vào dữ liệu huấn luyện.
– Bước kiểm tra: nhãn của một iểm dữ liệu mới x ược xác ịnh bởi 𝑥 = argmax 𝑥(𝑥) 𝑥(𝑥𝑥|𝑥) ∈{ … }
Giải quyết sai số khi d lớn và các xác suất nhỏ
Log là hàm ồng biến, không thay ổi kết quả 𝑥 = argmax(log 𝑥 𝑥 + log ( 𝑥(𝑥𝑥|𝑥))) ∈{ … }
… những bước chập chững vào thế giới Dữ liệu lớn … TS. Trịnh Hoàng Nam
BỘ PHÂN LOẠI NAÏVE BAYES •Mô tả thuật toán
– Cách tính p(xi|c) phụ thuộc loại dữ liệu • Gaussian naïve Bayes:
– Sử dụng trong loại dữ liệu mà thành phần là các biến liên tục • Multinomial naïve Bayes: –
Sử dụng trong bài toán phân loại văn bản mà vector ặc trưng ược xây dựng dựa trên ý tưởng bag of words • Bernoulli naïve Bayes: –
Sử dụng cho các loại dữ liệu mà mỗi thành phần là một giá trị nhị phân
… những bước chập chững vào thế giới Dữ liệu lớn … TS. Trịnh Hoàng Nam 13 lOMoARcPSD| 36667950
BỘ PHÂN LOẠI NAÏVE BAYES •Ví dụ
… những bước chập chững vào thế giới Dữ liệu lớn … TS. Trịnh Hoàng Nam
BỘ PHÂN LOẠI NAÏVE BAYES •Ví dụ
… những bước chập chững vào thế giới Dữ liệu lớn … TS. Trịnh Hoàng Nam 14 lOMoARcPSD| 36667950
… những bước chập chững vào thế giới Dữ liệu lớn … TS. Trịnh Hoàng Nam
… những bước chập chững vào thế giới Dữ liệu lớn … TS. Trịnh Hoàng Nam 15 lOMoARcPSD| 36667950
BỘ PHÂN LOẠI NAÏVE BAYES •Ví dụ
… những bước chập chững vào thế giới Dữ liệu lớn … TS. Trịnh Hoàng Nam
BỘ PHÂN LOẠI NAÏVE BAYES •Điều kiện áp dụng
– NBC thường ược sử dụng trong các bài toán phân loại văn bản
– NBC có thể hoạt ộng với các vector ặc trưng mà một phần là liên
tục (sử dụng Gaussian naive Bayes), phần còn lại ở dạng rời rạc (sử dụng multinomial hoặc Bernoulli)
… những bước chập chững vào thế giới Dữ liệu lớn … TS. Trịnh Hoàng Nam 16 lOMoARcPSD| 36667950
BỘ PHÂN LOẠI NAÏVE BAYES •Ưu iểm, nhược iểm – Ưu iểm
• Dễ dàng và nhanh chóng ể dự oán lớp của tập dữ liệu thử nghiệm. Nó
cũng hoạt ộng tốt trong dự oán nhiều lớp
• Với giả ịnh ộc lập giữa các ặc trưng, bộ phân loại Naive Bayes hoạt ộng
tốt hơn so với các mô hình khác với ít dữ liệu huấn luyện hơn. – Nhược iểm
• Độ chính xác của NBC nếu so với các thuật toán khác thì khôngược cao.
• Trong thế giới thực, hầu như không xảy ra khả năng các ặc trưng của dữ
liệu kiểm tra là ộc lập với nhau
… những bước chập chững vào thế giới Dữ liệu lớn … TS. Trịnh Hoàng Nam 17