[Bách Khoa Machine Learning] Phân cụm trong Khai phá dữ liệu - Các thuật toán Phân tích cụm (Clustering)

Trong bài viết này, chúng ta sẽ nghiên cứu về Phân tích cụm (Cluster Analysis) trong Khai phá dữ liệu. Đầu tiên, chúng ta sẽ tìm hiểu khái niệm, phần giới thiệu và các yêu cầu đối với việc phân cụm. Tiếp theo, chúng ta sẽ thảo luận về các ứng dụng và thuật toán, cũng như các phương pháp và cách tiếp cận phổ biến hiện nay.

Hãy cùng bắt đầu khám phá về Phân cụm trong Khai phá dữ liệu.

1. Giới thiệu về Phân tích cụm

a. Phân cụm (Clustering) trong Khai phá dữ liệu là gì?

Nhìn chung, đây là việc nhóm các đối tượng trừu tượng thành các lớp (classes) chứa các đối tượng tương tự nhau. Chúng ta coi một cụm dữ liệu như một nhóm duy nhất.

Khi thực hiện phân tích cụm, đầu tiên chúng ta phân chia tập dữ liệu thành các nhóm dựa trên sự tương đồng của dữ liệu, sau đó gán nhãn cho các nhóm đó. Lợi thế chính của phân cụm so với phân loại (classification) là nó có khả năng thích ứng với các thay đổi và giúp chỉ ra các đặc điểm hữu ích để phân biệt các nhóm khác nhau.

b. Phân tích cụm (Cluster Analysis) là gì?

Đó là việc tìm kiếm các nhóm đối tượng sao cho các đối tượng trong cùng một nhóm sẽ giống nhau và khác biệt với các đối tượng ở các nhóm khác.

2. Ứng dụng của Phân tích cụm trong Khai phá dữ liệu

Phân tích cụm dữ liệu được sử dụng trong nhiều ứng dụng như:

• Nghiên cứu thị trường: Giúp các nhà tiếp thị khám phá các nhóm khách hàng riêng biệt và đặc trưng hóa họ dựa trên thói quen mua sắm.
• Sinh học: Dùng để xây dựng hệ thống phân loại thực vật và động vật, phân loại gen có chức năng tương tự và tìm hiểu cấu trúc vốn có của quần thể.
• Quan sát Trái đất: Giúp xác định các khu vực có mục đích sử dụng đất tương tự nhau trong cơ sở dữ liệu quan sát địa lý.
• Quy hoạch đô thị: Giúp xác định các nhóm nhà trong thành phố dựa trên loại nhà, giá trị và vị trí địa lý.
• Web: Phân loại các tài liệu trên web để phục vụ việc khám phá thông tin.
• Phát hiện ngoại lệ (Outlier detection): Ứng dụng trong việc phát hiện gian lận thẻ tín dụng.

Với vai trò là một chức năng khai phá dữ liệu, phân tích cụm đóng vai trò như một công cụ để hiểu rõ hơn về sự phân phối dữ liệu và quan sát đặc điểm của từng cụm.

3. Các yêu cầu đối với Phân cụm trong Khai phá dữ liệu

Dưới đây là các yêu cầu quan trọng khi thực hiện phân cụm:

• a. Khả năng mở rộng (Scalability): Cần các thuật toán có khả năng mở rộng cao để xử lý các cơ sở dữ liệu lớn.
• b. Khả năng xử lý các loại thuộc tính khác nhau: Thuật toán phải áp dụng được cho mọi loại dữ liệu (dữ liệu khoảng, dữ liệu phân loại, dữ liệu nhị phân...).
• c. Phát hiện các cụm có hình dạng bất kỳ: Thuật toán không nên chỉ bị giới hạn bởi các phép đo khoảng cách (vốn thường chỉ tìm thấy các cụm hình cầu kích thước nhỏ).
• d. Số chiều cao (High dimensionality): Thuật toán cần xử lý được không gian dữ liệu nhiều chiều, không chỉ dữ liệu ít chiều.
• e. Khả năng xử lý dữ liệu nhiễu: Dữ liệu có thể chứa nhiễu, thiếu sót hoặc sai lệch. Thuật toán cần tránh việc tạo ra các cụm chất lượng kém do dữ liệu nhiễu.
• f. Khả năng diễn giải (Interpretability): Kết quả phân cụm phải có khả năng giải thích được, dễ hiểu và có thể sử dụng thực tế.

4. Các phương pháp Phân cụm trong Khai phá dữ liệu

Các phương pháp này được phân thành các loại chính sau:

a. Phương pháp Phân hoạch (Partitioning Method)

Giả sử chúng ta có cơ sở dữ liệu gồm 'n' đối tượng. Phương pháp phân hoạch sẽ xây dựng 'k' phần chia dữ liệu, trong đó mỗi phần đại diện cho một cụm (k ≤ n). Nó phải thỏa mãn các yêu cầu:

• Mỗi nhóm chứa ít nhất một đối tượng.
• Mỗi đối tượng phải thuộc về duy nhất một nhóm.
• Lưu ý: Phương pháp này thường bắt đầu với một phân hoạch ban đầu, sau đó sử dụng kỹ thuật lặp lại để di chuyển các đối tượng giữa các nhóm nhằm cải thiện chất lượng.

b. Phương pháp Phân bậc (Hierarchical Method)

Tạo ra một sự phân rã theo cấu trúc hình cây của tập dữ liệu. Có hai cách tiếp cận:

• Cách tiếp cận Hợp nhất (Agglomerative - Bottom-up): Bắt đầu với mỗi đối tượng là một cụm riêng biệt, sau đó liên tục gộp các cụm gần nhau lại cho đến khi tất cả nằm trong một cụm lớn hoặc thỏa mãn điều kiện dừng.
• Cách tiếp cận Phân chia (Divisive - Top-down): Bắt đầu với tất cả đối tượng trong cùng một cụm lớn, sau đó chia nhỏ cụm thành các cụm nhỏ hơn ở mỗi vòng lặp cho đến khi mỗi đối tượng là một cụm hoặc thỏa mãn điều kiện dừng.
• Nhược điểm: Phương pháp này khá cứng nhắc, một khi việc gộp hoặc chia đã thực hiện thì không thể hoàn tác.

c. Phương pháp dựa trên Mật độ (Density-Based Method)

Dựa trên khái niệm về mật độ. Ý tưởng là tiếp tục phát triển cụm chừng nào mật độ trong "vùng lân cận" còn vượt quá một ngưỡng nhất định. Với mỗi điểm dữ liệu trong một cụm, bán kính của vùng lân cận phải chứa ít nhất một số lượng điểm tối thiểu.

d. Phương pháp dựa trên Lưới (Grid-Based Method)

Không gian đối tượng được chia thành một số lượng hữu hạn các ô tạo thành cấu trúc lưới.

• Ưu điểm: Tốc độ xử lý cực nhanh, thời gian xử lý chỉ phụ thuộc vào số lượng ô trong mỗi chiều của không gian lưới mà không phụ thuộc vào số lượng đối tượng dữ liệu.

e. Phương pháp dựa trên Mô hình (Model-Based Method)

Một mô hình được giả định cho mỗi cụm để tìm sự phù hợp nhất của dữ liệu với mô hình đó. Phương pháp này xác định các cụm bằng cách phân cụm hàm mật độ, phản ánh sự phân bố không gian của các điểm dữ liệu. Nó cũng giúp xác định số lượng cụm dựa trên các số liệu thống kê tiêu chuẩn, tính đến cả nhiễu và ngoại lệ.

f. Phương pháp dựa trên Ràng buộc (Constraint-Based Method)

Việc phân cụm được thực hiện bằng cách kết hợp các ràng buộc từ phía người dùng hoặc ứng dụng. Ràng buộc thể hiện mong đợi của người dùng và cung cấp cách thức tương tác với quá trình phân cụm.

5. Cái gì không phải là Phân tích cụm?

• Phân loại có giám sát (Supervised classification): Vì đã có thông tin nhãn lớp.
• Phân đoạn đơn giản (Simple segmentation): Ví dụ như chia danh sách sinh viên theo chữ cái đầu của tên.
• Kết quả của một truy vấn: Nhóm các đối tượng chỉ đơn giản dựa trên một đặc điểm cụ thể bên ngoài.
• Phân chia đồ thị (Graph partitioning): Mặc dù có sự liên quan nhưng về bản chất không hoàn toàn đồng nhất với phân cụm.

Kết luận

Phân cụm là một kỹ thuật quan trọng giúp nhóm các điểm dữ liệu tương đồng, từ đó tìm ra các quy luật ẩn mà mắt thường khó nhận thấy. Không giống như phân loại, phân cụm không cần dữ liệu được dán nhãn sẵn (đây là một dạng của Học không giám sát - Unsupervised learning). Các thuật toán phổ biến nhất bao gồm K-Means, Hierarchical Clustering và DBSCAN. Chúng được ứng dụng rộng rãi trong nghiên cứu thị trường, xử lý hình ảnh và phân tích mạng xã hội.