Bài giảng Học máy - Các phương pháp học không giám sát

Học Máy

(Machine Learning)

Ngô Văn Linh

[email protected].vn

Viện Công nghệ thông tin và Truyền thông

Trường Đại Học Bách Khoa Hà Nội

Năm 2018

Nội dung môn học:

◼ Giới thiệu chung

◼ Các phương pháp học không giám sát

◼ Giới thiệu về phân cụm

◼ Phương pháp k-Means

◼ Online k-Means cho dữ liệu lớn

◼ Các phương pháp học có giám sát

◼ Đánh giá hiệu năng hệ thống học máy

2

1. Hai bài toán học

◼ Học có giám sát (Supervised learning)

❑ Tập dữ liệu học (training data) bao gồm các quan sát (examples,

observations), mà mỗi quan sát được gắn kèm với một giá trị đầu

ra mong muốn.

❑ Ta cần học một hàm (vd: một phân lớp, một hàm hồi quy,...) phù

hợp với tập dữ liệu hiện có.

❑ Hàm học được sau đó sẽ được dùng để dự đoán cho các quan sát

mới.

◼ Học không giám sát (Unsupervised learning)

❑ Tập học (training data) bao gồm các quan sát, mà mỗi quan sát

không có thông tin về nhãn lớp hoặc giá trị đầu ra mong muốn.

❑ Mục đích là tìm ra (học) các cụm, các cấu trúc, các quan hệ tồn tại

ẩn trong tập dữ liệu hiện có.

3

Ví dụ về học không giám sát (1)

◼ Phân cụm (clustering)

❑ Phát hiện các cụm dữ liệu, cụm tính chất,…

◼ Community detection

◼ Phát hiện các cộng đồng trong mạng xã hội

4

Ví dụ về học không giám sát (2)

◼ Trends detection

❑ Phát hiện xu hướng, thị yếu,…

◼ Entity-interaction analysis

5

2. Phân cụm

◼ Phân cụm (clustering)

❑ Đầu vào: một tập dữ liệu {x₁, …, x_M} không có nhãn (hoặc giá trị

đầu ra mong muốn)

❑ Đầu ra: các cụm (nhóm) của các quan sát

◼ Một cụm (cluster) là một tập các quan sát

❑ Tương tự với nhau (theo một ý nghĩa, đánh giá nào đó)

❑ Khác biệt với các quan sát thuộc các cụm khác

Sau khi phân cụm

6

Phân cụm

◼ Giải thuật phân cụm

• Dựa trên phân hoạch (Partition-based clustering)

• Dựa trên tích tụ phân cấp (Hierarchical clustering)

• Bản đồ tự tổ thức (Self-organizing map – SOM)

• Các mô hình hỗn hợp (Mixture models)

• …

◼ Đánh giá chất lượng phân cụm (Clustering quality)

• Khoảng cách/sự khác biệt giữa các cụm → Cần được cực đại hó a

• Khoảng cách/sự khác biệt bên trong một cụm → Cần được cực

tiểu hó a

7

3. Phương pháp K-means

◼ K-means được giới thiệu đầu tiên bởi Lloyd năm 1957.

◼ Là phương pháp phân cụm phổ biến nhất trong các

phương pháp dựa trên phân hoạch (partition-based

clustering)

◼ Biểu diễn dữ liệu: D={x₁,x₂,…,x_r}

•x_ilà một quan sá t (một vectơ trong một không gian n chiều)

◼ Giải thuật K-means phân chia tập dữ liệu thành kcụm

• Mỗi cụm (cluster) có một điểm trung tâm, được gọi là centroid

•k (tổng số các cụm thu được) là một giá trị được cho trước

(vd: được chỉ định bởi người thiết kế hệ thống phân cụm)

8

k-Means: Các bước chính

Đầu vào: tập học D, số lượng cụm k, khoảng cách d(x,y)

• Bước 1. Chọn ngẫu nhiên kquan sá t (được gọi là cá c

hạt nhân – seeds) để sử dụng làm các điểm trung tâm

ban đầu (initial centroids) của k cụm.

• Bước 2. Lặp liên tục hai bước sau cho đến khi gặp điều

kiện hội tụ (convergence criterion):

❑ Bước 2.1. Đối với mỗi quan sá t, gán nó vào cụm (trong số k

cụm) mà có tâm (centroid) gần nó nhất.

❑ Bước 2.2. Đối với mỗi cụm, tính toán lại điểm trung tâm của

nó dựa trên tất cả các quan sá t thuộc vào cụm đó.

9

K-means(D, k)

D: Tập học

k: Số lượng cụm kết quả (thu được)

Lựa chọn ngẫu nhiên k quan sát trong tập D để làm các điểm trung

tâm ban đầu (initial centroids)

while not CONVERGENCE

for each xD

Tính các khoảng cách từ x đến các điểm trung tâm (centroid)

Gá n x vào cụm có điểm trung tâm (centroid) gần x nhất

end for

for each cụm

Tính (xác định) lại điểm trung tâm (centroid) dựa trên các quan

sá t hiện thời đang thuộc vào cụm này

end while

return {k cụm kết quả}

10

K-means: Minh họa (1)

[Liu, 2006]

11

K-means: Minh họa (2)

[Liu, 2006]

12

K-means: Điều kiện hội tụ

Quá trình phân cụm kết thúc, nếu:

• Không có (hoặc có không đáng kể) việc gán lại các quan sá t vào

các cụm khác, hoặc

• Không có (hoặc có không đáng kể) thay đổi về các điểm trung tâm

(centroids) của các cụm, hoặc

• Giảm không đáng kể về tổng lỗi phân cụm:

k

Error =

d(x,m )²

 

i

i=1 xC_i

▪ C_i: Cụm thứ i

▪ m_i: Điểm trung tâm (centroid) của cụm C_i

▪ d(x, m_i): Khoảng cách (khác biệt) giữa quan sá t x và điểm

trung tâ m m_i

13

K-means: Điểm trung tâm, hàm khoảng cách

◼ Xác định điểm trung tâm: Điểm trung bình (Mean centroid)

1

m_i=

x



C_i

xC_i

• (vectơ) m_ilà điểm trung tâm (centroid) của cụm C_i

• |C_i| kích thước của cụm C_i(tổng số quan sát trong C_i)

◼ Hàm khoảng cách: Euclidean distance

2

d(x,m_i) = x −m_i=

(

x₁− m_i1

)

+

(

x₂− m_i2

)

²+...+

(

x_n−m_in

)

• (vectơ) m_ilà điểm trung tâm (centroid) của cụm C_i

• d(x,m_i) là khoảng cách giữa x và điểm trung tâm m_i

14

K-means: hàm khoảng cách

◼ Hàm khoảng cách

❑

Mỗi hàm sẽ tương ứng với một cách nhìn về dữ liệu.

Vô hạn hàm!!!

Chọn hàm nào?

◼ Có thể thay bằng độ đo

tương đồng

(similarity measure)

15

K-means: Các ưu điểm

◼ Đơn giản: dễ cài đặt, rất dễ hiểu

◼ Rất linh động: cho phép dùng nhiều độ đo khoảng cách

khá c nhau → phù hợp với các loại dữ liệu khác nhau.

◼ Hiệu quả (khi dùng độ đo Euclide)

• Độ phức tạp tính toán tại mỗi bước ~ O(r.k)

▪ r: Tổng số các quan sá t (kích thước của tập dữ liệu)

▪ k: Tổng số cụm thu được

◼ Thuật toán có độ phức tạp trung bình là đa thức.

◼ K-means là giải thuật phân cụm được dùng phổ biến nhất

16

K-means: Các nhược điểm (1)

◼ Số cụm kphải được xác định trước

◼ Thường ta không biết chính xác !

◼ Giải thuật K-means nhạy cảm (gặp lỗi) với cá c quan sá t

ngoại lai (outliers)

• Cá c quan sá t ngoại lai là các quan sá t (rất) khác biệt với tất các

quan sá t khá c

• Cá c quan sá t ngoại lai có thể do lỗi trong quá trình thu thập/lưu dữ

liệu

• Cá c quan sá t ngoại lai có các giá trị thuộc tính (rất) khác biệt với

các giá trị thuộc tính của các quan sá t khá c

17

K-means: ngoại lai

[Liu, 2006]

18

Giải quyết vấn đề ngoại lai

• Giải pháp 1: Trong quá trình phân cụm, cần loại bỏ một số các

quan sá t quá khác biệt với (cách xa) các điểm trung tâm

(centroids) so với các quan sá t khá c

─ Để chắc chắn (không loại nhầm), theo dõi các quan sá t ngoại lai

(outliers) qua một vài (thay vì chỉ 1) bước lặp phân cụm, trước khi

quyết định loại bỏ

• Giải pháp 2: Thực hiện việc lấy ngẫu nhiên (random sampling)

một tập nhỏ từ D để học K cụm

─ Do đây là tập con nhỏ của tập dữ liệu ban đầu, nên khả năng một

ngoại lai (outlier) được chọn là nhỏ

─ Gá n cá c quan sá t còn lại của tập dữ liệu vào các cụm tùy theo

đánh giá về khoảng cách (hoặc độ tương tự)

19

K-means: Các nhược điểm (2)

◼ Giải thuật K-means phụ thuộc vào việc chọn các điểm trung tâm ban

đầu (initial centroids)

1^stcentroid

2^ndcentroid

[Liu, 2006]

20

Bài giảng Học máy - Các phương pháp học không giám sát - Ngô Văn Linh