Chương 1: Thuật toán phân cụm K-Means (K-Means Clustering) 1. Định nghĩa thuật ngữ học không giám sát (Unsupervised Learning) Học không giám sát là một nhóm thuật toán hay phương pháp kỹ thuật cho phép máy tự học hỏi và tìm ra một mô hình hay cấu trúc nào đó ẩn trong một bộ dữ liệu không được gắn nhãn trước. Điều này đồng nghĩa với việc chúng ta chỉ có bộ dữ liệu đầu vào và hoàn toàn không biết kết quả đầu ra là gì.1: Sự khác nhau giữa máy học có giám sát và máy học không giám sát 1. Định nghĩa phân cụm K-Means Phân cụm K-Means là một thuật toán học không giám sát đơn giản được sử dụng để giải quyết các vấn đề phân cụm.
Nó tuân theo một thủ tục đơn giản là phân loại một tập dữ liệu nhất định thành một số cụm, được xác định bằng ký tự "k", được cố định trước. Sau đó, các cụm được định vị dưới dạng điểm và tất cả các điểm quan sát hoặc điểm dữ liệu được liên kết với cụm gần nhất, được tính toán, điều chỉnh và sau đó quá trình bắt đầu lại bằng cách sử dụng các điều chỉnh mới cho đến khi đạt được kết quả mong muốn. Các trường hợp sử dụng thuật toán Ví dụ phổ biến cho thuật toán này đó là việc phân loại khách hàng. Các khách hàng có những đặc điểm tương đồng về mặt thông tin hoặc dựa trên lịch sử mua hàng, hành vi mua hàng có thể phân thành các loại khách hàng khác nhau.
Nói cách khác mỗi loại khách hàng sẽ có những đặc điểm chung giống nhau, và những đặc điểm đó được phát hiện thông qua thuật toán phân cụm Ngoài ra có một ví dụ khác mà chúng ta cũng hay bắt gặp, đó là các mạng xã hội luôn tìm cách phân cụm những người có cùng sở thích, thói quen để đưa ra những gợi ý kết bạn hay tham gia một nhóm nào đó. Nội dung của thuật toán 1. Một số khái niệm dùng trong thuật toán Hình 1.2: Mô tả khái niệm dùng trong thuật toán - Cluster (cụm): là một nhóm các điểm dữ liệu tương tự nhau. - k: là số lượng của các cụm.
- Centroid: là trung tâm của 1 cụm dữ liệu. - Khoảng cách Euclidean: là độ dài của đoạn thẳng nối hai điểm trong không gian Euclide.3: Khoảng cách Euclidean Với hai điểm bất kỳ có tọa độ Descartes cho trước trong không gian Euclide n chiều, khoảng cách giữa chúng là: 𝑑 (𝑝, 𝑞) = √(𝑝1 − 𝑞1 )2 + (𝑝2 − 𝑞2 )2 + ⋯ + (𝑝𝑖 − 𝑞𝑖 )2 + ⋯ + (𝑝𝑛 − 𝑞𝑛 )2 1. Các phương pháp xác định K (số lượng cụm) 1. Phương pháp Elbow Phương pháp Elbow là phương pháp dùng để xác định số lượng cụm tối ưu nhất cho tập dữ liệu.
Mô hình Elbow thực hiện để xác định giá trị k trong K-Means như sau: 1. Khởi tạo giá trị ban đầu cho k. Tăng giá trị của k. Tính tổng bình phương khoảng cách giữa mỗi điểm và tâm trong một cụm (WCSS - Within-Cluster Sum of Square) từ mỗi giá trị của k.
k WCSS = d(x, mi ) 2 i =1 xCi Trong đó: • Ci: là cụm thứ i. • mi: là centroid của cụm Ci. Vẽ biểu đồ từ WCSS và giá trị k, phân tích tổng các kết quả WCSS từ giá trị k đã giảm mạnh. Xác định vị trí mà WCSS giảm mạnh sau đó đồ thị bắt đầu di chuyển gần như song song với trục x và đặt điểm k.
Phương pháp Average Silhouette Hệ số Silhouette là thước đo mức độ tương tự của một điểm dữ liệu trong cụm (liên kết) so với các cụm khác. Để vẽ biểu đồ Silhouette ta cần 2 bước: - Chọn một đoạn giá trị của k (giả sử từ 1 đến 10). - Vẽ đồ thị thể hệ số Silhouette ứng với mỗi giá trị k, để vẽ đồ thị ta cần hệ số Silhouette tại một điểm dữ liệu và trung bình silhouette cho mỗi k. Phương trình trình tính toán hệ số Silhouette tại một điểm dữ liệu cụ thể như sau: 𝑏(𝑖) − 𝑎(𝑖) 𝑆 (𝑖 ) = max{𝑎(𝑖), 𝑏(𝑖)} Trong đó: • S(i) là hệ số hình bóng của điểm dữ liệu i.
• a(i) là khoảng cách trung bình giữa i và tất cả các điểm dữ liệu khác trong cụm mà i thuộc về. • b(i) là khoảng cách trung bình từ i đến tất cả các điểm dữ liệu khác trong những cụm mà i không thuộc về.5: Minh họa a(i) Hình 1.6: Minh họa b(i) Sau đó, ta sẽ tính toán trung bình silhouette cho mỗi k. 𝐴𝑣𝑒𝑟𝑎𝑔𝑒𝑆𝑖𝑙ℎ𝑜𝑢𝑒𝑡𝑡𝑒 = 𝑚𝑒𝑎𝑛{𝑆(𝑖)} Cuối cùng, ta biểu đồ giữa trung bình silhouette và k. Chọn k cụm tại giá trị của k sao cho trung bình silhouette lớn nhất.
Phương pháp Gap Statistic Phương pháp này có thể được áp dụng cho bất kỳ phương pháp phân cụm nào (K-means clustering, hierarchical clustering). Gap Statisstic so sánh tổng biến thể trong cụm đối với các giá trị khác nhau của k với giá trị dự kiến của chúng trong phân phối tham chiếu rỗng của dữ liệu (tức là phân phối không có phân nhóm rõ ràng). Tập dữ liệu tham chiếu được tạo bằng cách sử dụng mô phỏng Monte Carlo của quá trình lấy mẫu. Đó là, cho mỗi biến (xi) trong tập dữ liệu, chúng tôi tính toán phạm vi của nó [min(xi), max(xi)] và tạo ra các giá trị cho n điểm một cách đồng nhất trong khoảng thời gian từ min đến max.
Đối với dữ liệu quan sát và dữ liệu tham chiếu, tổng biến thể nội bộ được tính bằng cách sử dụng các giá trị khác nhau của k. Thống kê khoảng cách cho k cho trước được định nghĩa như sau: 𝐺𝑎𝑝𝑛 (𝑘 ) = 𝐸𝑛∗ log(𝑊𝑘 ) − log(𝑊𝑘 ) Trong đó, 𝐸𝑛∗ biểu thị kỳ vọng dưới cỡ mẫu n từ phân phối tham chiếu. 𝐸𝑛∗ được xác định thông qua bootstrapping (B) bằng cách tạo B bản sao của bộ dữ liệu tham chiếu và bằng cách tính toán giá trị trung bình log(𝑊𝑛∗ ). Gap statistic đo lường độ lệch của quan sát được giá trị Wk từ giá trị kỳ vọng của nó theo giả thuyết.
Ước tính của các cụm tối ưu (k) sẽ là giá trị tối đa hóa Gapn(k). Điều này có nghĩa là cấu trúc phân cụm nằm xa sự phân bố đồng đều của các điểm. Thuật toán bao gồm các bước sau: 1. Cụm dữ liệu quan sát, thay đổi số lượng cụm từ k=1, …, k=max và tính toán tương ứng Wk 2.
Tạo tập dữ liệu tham chiếu B và phân cụm từng nhóm với số lượng cụm khác nhau k=1, …, k=max. Tính toán Gapn(k) ước tính: 𝐺𝑎𝑝𝑛 (𝑘 ) = 𝐸𝑛∗ log(𝑊𝑘 ) − log(𝑊𝑘 ) 3. Chọn số cụm là k nhỏ nhất sao cho 6 𝐺𝑎𝑝(𝑘 ) ≥ 𝐺𝑎𝑝(𝑘 + 1) − 𝑠𝑘+1 Hình 1.8: Biểu đồ Gap Statistic 1. Tóm tắt các bước của thuật toán Hình 1.9: Sơ đồ thuật toán K-Means Đầu vào: N điểm dữ liệu X = [x1, x2, x3, .xN] chưa có nhãn vector và số lượng cụm cần tìm k.
7 Đầu ra: Các trung tâm K = [m1, m2, m3, .mK] và nhãn vector cho từng điểm dữ liệu. Chú thích: x, mi là các ký hiệu vector của các điểm dữ liệu và điểm trung tâm Ci là cụm thứ i, mi là trung tâm của cụm Ci. Các bước thực hiện thuật toán: 1. Chọn số k cụm và chọn ngẫu nhiên k điểm làm trung tâm.
Sử dụng các phương pháp để tìm được số k tối ưu nhất. Gán mỗi điểm dữ liệu về cụm có trung tâm cụm gần nhất. Ta xác định nhãn cho từng điểm dữ liệu bằng cách tính toán khoảng cách của từng điểm dữ liệu tới tâm cụm của nó, thực hiện bằng phương pháp tính khoảng cách Euclidean. Một điểm dữ liệu x được phân vào một cụm Ci có trung tâm là mi (trung tâm được chọn ở bước 1) 𝑑 = 𝑎𝑔𝑟𝑚𝑖𝑛𝑖 ||𝑥 − 𝑚𝑖 ||2 Trong đó: • x là một điểm dữ liệu được phân vào một cụm Ci.
• mi là trung tâm của Ci. • agrmini là tìm giá trị nhỏ nhất của biến số để hàm số đó đạt giá trị nhỏ nhất. sau đó chọn khoảng cách ngắn nhất và gán x1 cho trung tâm mi tương ứng. Tương tự ta tính khoảng cách và gán các điểm x2, x3, …, xn cho các trung tâm tương ứng.
Tính toán lại vị trí trung tâm cho từng cụm. Sau khi các cụm được hình thành có tâm và các điểm dữ liệu được gán cho nó. Ta xác định lại vị trí trung tâm mới cho các cụm đó bằng cách tính trung bình cộng của các điểm dữ liệu trong cụm, trung bình cộng đó sẽ là trung tâm mới của cụm. 1 𝑚𝑖 = ∑𝑥 |𝑐𝑖 | 𝑥∈𝐶𝑖 Trong đó: • x là một điểm dữ liệu được phân vào một cụm Ci.
• |Ci| là kích thước của cụm Ci. 8 • mi là trung tâm của cụm Ci. Lặp lại bước 2 và 3 tới khi vị trí các trung tâm cụm không đổi. Đặc điểm của thuật toán K-Means là một thuật toán dựa trên centroid, hoặc một thuật toán dựa trên khoảng cách, tính toán khoảng cách để gán một điểm cho một cụm.
Trong K-Means, mỗi cụm được liên kết với một trung tâm. Chất lượng của thuật toán K-Means phụ thuộc nhiều vào các tham số đầu vào như: số cụm k, và k vector trọng tâm khởi tạo ban đầu. Trong trường hợp các vector trọng tâm khởi tạo ban đầu mà quá lệch so với các trọng tâm cụm tự nhiên thì kết quả phân cụm của K-Means là rất thấp, nghĩa là các cụm dữ liệu được khám phá rất lệch so với các cụm trong thực tế. Trên thực tế, chưa có một giải pháp nào để chọn tham số đầu vào, giải pháp thường được sử dụng nhất là thử nghiệm với các giá trị đầu vào k khác nhau rồi sau đó chọn giải pháp tốt nhất.
Ví dụ Ví dụ 1: Ngân hàng muốn phân khúc khách hàng dựa trên thu nhập và số nợ của họ: Hình 1.10: Biểu đồ thể hiện khách hàng dựa trên thu nhập và số nợ Chúng ta có thể phân tách thành 2 cụm: Khách hàng có thu nhập thấp thuộc 1 cụm và khách hàng có thu nhập cao thuộc cụm thứ 2.11: Phân tách khách hàng thành 2 cụm Chúng ta cũng có thể phân tách thành 4 cụm: - Thu nhập thấp, nợ ít. - Thu nhập thấp, nợ nhiều. - Thu nhập cao, nợ ít. - Thu nhập cao, nợ nhiều.12: Phân tách khách hàng thành 4 cụm Ví dụ 2: Biểu đồ, trong đó trục x là số lượng các cụm (Clusters), trục y là số liệu đánh giá (Inertia: là một độ đo về mức độ gắn kết nội bộ trong một cụm) 10 Hình 1.13: Biểu đồ với trục x là Clusters, trục y là Inertia Giả sử ban đầu, Clusters là 2 và Inertia là 1000.14:Biểu đồ với Cluster là 2 và Inertia là 1000 Sau đó, tăng Clusters lên.