CHƯƠNG 1: CƠ SỞ LÝ THUYẾT PHÂN CỤM DỮ LIỆU 1. Tổng quan học máy 1. Khái niệm học máy Học máy (tiếng anh: Machine Learning) là một lĩnh vực của Trí tuệ nhân tạo liên quan đến việc nghiên cứu và xây dựng các kĩ thuật cho phép các hệ thống "học" tự động từ dữ liệu để giải quyết những vấn đề cụ thể. Máy học là cách trích xuất kiến thức từ dữ liệu, là một lĩnh vực tập trung vào sự phức tạp của các giải thuật trong việc thực thi tính toán, nghiên cứu ở giao điểm của Thống kê, Trí tuệ nhân tạo và Khoa học máy tính và còn được gọi là phân tích dự đoán hoặc học thống kê.
Các kĩ thuật trong Học máy a. Học có giám sát Học có giám sát (Supervised Learning) là một kĩ thuật của ngành học máy để xây dựng một hàm (Function) từ dữ liệu huấn luyện. Dữ liệu huấn luyện bao gồm các cặp gồm đối tượng đầu vào (thường dạng Vectơ), và đầu ra mong muốn. Đầu ra của một hàm có thể là một giá trị liên tục (Hồi quy), hay có thể là dự đoán một nhãn phân loại cho một đối tượng đầu vào (Phân loại).
Nhiệm vụ của chương trình học có giám sát là dự đoán giá trị của hàm cho một đối tượng bất kì là đầu vào hợp lệ, sau khi đã xem xét một số ví dụ huấn luyện (nghĩa là, các cặp đầu vào và đầu ra tương ứng). • Xác định cấu trúc của hàm chức năng cần tìm và giải thuật học tương ứng. • Hoàn thành thiết kế. 4 Ưu diểm: Học có giám sát cho phép thu thập dữ liệu và tạo ra dữ liệu đầu ra từ những kinh nghiệm trước đó.
Giúp tối ưu hóa các tiêu chí hiệu suất với sự trợ giúp của kinh nghiệm và giúp giải quyết nhiều vấn đề trong thực tế Nhược điểm: Việc đào tạo các mô hình giải quyết bài toàn cho học có giám sát cần rất nguồn lực và thời gian để có thể tính toán việc này đòi hỏi rất nhiều thời gian. Bài toán hồi quy: dự đoán một giá trị dựa trên đặc trưng đầu vào. Nguồn: Tác giả biên tập từ [1] b. Học không giám sát Học không giám sát (Unsupervised Learning) là một phương pháp của ngành học máy nhằm tìm ra một mô hình mà phù hợp với các quan sát.
Nó khác biệt với học có giám sát ở chỗ là đầu ra đúng tương ứng cho mỗi đầu vào là không biết trước. Trong học không có giám sát, một tập dữ liệu đầu vào được thu thập. Học không có giám sát thường đối xử với các đối tượng đầu vào như là một tập các biến ngẫu nhiên. Sau đó, một mô hình mật độ kết hợp sẽ được xây dựng cho tập dữ liệu đó.
5 Học không có giám sát có thể được dùng kết hợp với suy luận Bayes để cho ra xác suất có điều kiện (nghĩa là học có giám sát) cho bất kì biến ngẫu nhiên nào khi biết trước các biến khác. Học không có giám sát cũng hữu ích cho việc nén dữ liệu: về cơ bản, mọi giải thuật nén dữ liệu hoặc là dựa vào một phân bố xác suất trên một tập đầu vào một cách tường minh hay không tường minh. Một dạng khác của học không có giám sát là phân nhóm dữ liệu, nó đôi khi không mang tính xác suất. Các thuật toán của Học không giám sát: • K-mean • Mô hình hỗn hợp Gaussian • Phân cụm phân cấp • PCA / T-SNE Hình 1.
Bài toán Phân loại khách hàng. Nguồn: Tác giả biên tập từ [1] 6 c. Học bán giám sát Học bán giám sát (Semi-supervised learning) là phương pháp học máy mà dữ liệu được dùng để huấn luyện bao gồm dữ liệu gán nhãn và chưa gán nhãn. Học bán giám sát được áp dụng nhiều vào phân lớp và phân cụm.
Nhiệm vụ của học bán giám sát: là huấn luyện tập phân lớp tốt hơn Học có giám sát từ dữ liệu gán nhãn và chưa gán nhãn. Học bán giám sát với hai lớp (hình tam giác và hình vuông) và các mẫu chưa gán nhãn (hình tròn). Nguồn: Tác giả biên tập từ [1] 1. Tổng quan phân cụm dữ liệu 1.
Khái niệm kỹ thuật phân cụm dữ liệu Phân cụm (clustering) là một kỹ thuật rất quan trọng trong học không giám sát (unsupervised learning), kỹ thuật này giúp phân nhóm các mẫu dữ liệu vào các nhóm khác nhau (clusters) dựa trên các đặc tính (features). Mục tiêu của phân cụm dữ liệu là tìm ra các nhóm có tính chất tương tự nhau và khác với các nhóm khác. 7 Do vậy, phân cụm dữ liệu là quá trình phân chia một tập dữ liệu ban đầu thành các dụm dữ liệu sao cho các đối tượng trong một cụm thì sẽ có sự “tương tự (Similar)” với nhau và các đối tượng trong các cụm khác nhau thì “phi tương tự (Dissimilar)” với nhau. [ppp] Trong kỹ thuật phân cụm dữ dữ liệu tùy vào cách thứ phân chia mẫu dữ liệu vào các nhóm mà được chia thành 2 nhóm là “Phân cụm cứng” và “Phân cụm mềm”.
Minh họa phân cụm dữ liệu Nguồn: Sưu tập 1. Phân cụm cứng và phân cụm mờ a. Phân cụm cứng Phân cụm cứng (hard clustering) là một phương pháp trong học không giám sát (unsupervised learning) giúp phân loại các mẫu dữ liệu vào các nhóm (clusters) dựa trên các đặc trưng (features) của chúng. Các mẫu dữ liệu được chia thành các nhóm không trùng lặp và mỗi mẫu dữ liệu chỉ thuộc vào một nhóm.
8 Phân cụm cứng thực hiện việc gán các mẫu dữ liệu vào các nhóm bằng cách tính toán khoảng cách giữa mỗi mẫu dữ liệu và các trung tâm của các nhóm đã được xác định trước. Một mẫu dữ liệu sẽ được gán vào nhóm có trung tâm gần nhất với nó. Kết quả phân cụm cứng là một tập hợp các nhóm, trong đó mỗi nhóm chứa các mẫu dữ liệu có tính chất tương tự nhau. Các phương pháp phân cụm cứng phổ biến bao gồm K-means và Hierarchical Clustering.
Phân cụm cứng thường được sử dụng trong các bài toán mà dữ liệu được phân biệt rõ ràng giữa các nhóm. Ví dụ, trong phân tích khách hàng, các khách hàng được phân loại vào các nhóm dựa trên các đặc trưng như tuổi, giới tính, thu nhập và sở thích mua hàng. Phân cụm mềm Phân cụm mềm (soft clustering) là một phương pháp trong học không giám sát (unsupervised learning) giúp phân loại các mẫu dữ liệu vào các nhóm (clusters) dựa trên các đặc trưng (features) của chúng, nhưng khác với phân cụm cứng (hard clustering) thì mỗi mẫu dữ liệu có thể thuộc vào nhiều nhóm với một mức độ xác suất khác nhau thay vì chỉ thuộc về duy nhất một nhóm như phân cụm cứng. Kết quả phân cụm mềm được biểu diễn bằng một ma trận có kích thước là số mẫu dữ liệu x số nhóm, trong đó mỗi phần tử trong ma trận thể hiện mức độ xác suất mà một mẫu dữ liệu thuộc về một nhóm cụ thể.
Các phần tử này được gọi là các giá trị ẩn (hidden values) hoặc các đại lượng latents. Phân cụm mềm thường được sử dụng trong các bài toán mà dữ liệu không phân biệt rõ ràng giữa các nhóm, hoặc các mẫu dữ liệu có thể thuộc vào nhiều nhóm khác nhau với một mức độ xác suất khác nhau. Ví dụ, trong phân tích hình ảnh, một vật thể có thể được xem là thuộc vào nhiều lớp khác nhau, tùy thuộc vào các đặc 9 trưng của nó. Các phương pháp phân cụm mềm phổ biến bao gồm Fuzzy C-means và GMM (Gaussian Mixture Model).
Khác biệt giữa phân cụm cứng và phân cụm mờ Sự khác biệt giữa phân cụm cứng và phân cụm mềm là cách thức phân chia các mẫu dữ liệu vào các nhóm. • Phân cụm cứng: Mỗi mẫu dữ liệu chỉ thuộc về một nhóm duy nhất. Khi thực hiện phân cụm cứng, mỗi mẫu dữ liệu được gán vào nhóm có trung tâm gần nhất. Ví dụ, trong phân cụm K-means, mỗi mẫu dữ liệu chỉ được phân vào một nhóm duy nhất.
• Phân cụm mềm: Mỗi mẫu dữ liệu có thể thuộc về nhiều nhóm với mức độ khả năng (degree of membership) khác nhau. Khi thực hiện phân cụm mờ, mỗi mẫu dữ liệu được đại diện bởi một vector mà mỗi phần tử của vector là một giá trị từ 0 đến 1 biểu thị mức độ thuộc về từng nhóm. Ví dụ, trong phân cụm Fuzzy C-means, mỗi mẫu dữ liệu được biểu diễn bởi một vector mà tổng các phần tử của vector bằng 1. Cả phân cụm cứng và phân cụm mờ đều có ưu điểm và nhược điểm riêng, và sự lựa chọn giữa hai phương pháp này phụ thuộc vào bài toán và đặc tính của dữ liệu.
Phân cụm cứng thường đơn giản và dễ hiểu, tuy nhiên, nó có thể bị ảnh hưởng bởi các nhiễu (outliers) trong dữ liệu. Phân cụm mờ thường cho kết quả phân cụm chính xác hơn và có khả năng giúp phân chia các mẫu dữ liệu "lõi" (core) của các nhóm tốt hơn, tuy nhiên, việc giải thích kết quả phân cụm mờ thường khó hơn. Quy trình thực hiện kỹ thuật phân cụm dữ liệu Các bước thực hiện phân cụm dữ liệu bao gồm: 10 • Chuẩn bị dữ liệu: Lựa chọn các đặc trưng (features) của dữ liệu và tiền xử lý dữ liệu (nếu cần). • Chọn thuật toán phân cụm: Lựa chọn thuật toán phân cụm phù hợp với dữ liệu và mục tiêu của bài toán.
• Xác định số cụm (clusters): Xác định số lượng cụm cần phân chia, có thể sử dụng các phương pháp như Elbow method hoặc Silhouette method để đưa ra quyết định này. • Thực hiện phân cụm: Áp dụng thuật toán phân cụm để phân chia các điểm dữ liệu thành các cụm. Các thuật toán phân cụm dữ liệu 1. Thuật toán Kmean a.
Giới thiệu thuật toán Kmean Thuật toán phân cụm dữ liệu K-means (K-means Clustring) thuộc phương pháp phân cụm Phân hoạch do James MacQueen đề xuất trong lĩnh vữc thống kê vào năm 1967. K-means là thuật toán rất quan trọng và được sử dụng phổ biến trong kỹ thuật phân cụm. Thuật toán dựa trên độ đo khoảng cách của các đối tượng dữ liệu đến phần tử là trung tâm của cụm chứa dữ liệu đó. Thuật toán K-means lấy tham số đầu vào là K (với K là số cụm được xác định từ trước, K nguyên dương) và phân chia một tập n đối tượng (objects) từ một cơ sở dữ liệu D vào trong K cụm để cho kết quả độ tương đồng trong cụm là cao trong khi độ tương đồng ngoài cụm là thấp.
Phân tích toán học • Input (Đầu vào): Các điểm dữ liệu và số cụm cần xác định. 11 • Output (Đầu ra): Tâm cụm của mỗi cụm và phân các điểm dữ liệu vào nhóm tương ứng. • Điều kiện: Mỗi một điểm dữ liệu chỉ thuộc về một cụm duy nhất.