Phân cụm dữ liệu (hay Phân cụm; Học không nhãn,tiếng Anh Data Clustering) là quá trình chia một tập các đối tượng (vật lý hoặc trừu tượng) thành các nhóm hay các lớp, cụm đối tượng dữ liệu có tính chất tương tự nhau. Một cụm, hay một lớp (cluster) là một tập các đối tượng dữ liệu trong đó các đối tượng trong cùng một cụm có sự tương tự hoặc giống nhau và ít tương tự hoặc khác nhau so với các đối tượng thuộc cụm khác. Độ tương tự được xác định theo một tiêu chuẩn nào đó, tuỳ thuộc vào từng ứng dụng cụ thể và được xác định trước. Không giống như trong quá trình phân loại (classification), thường biết trước tính chất hay đặc điểm của các đối tượng trong cùng một lớp (cụm) và dựa vào đó để ấn định một đối tượng mới vào lớp này hay lớp khác. Thay vào đó, trong quá trình phân cụm ta không biết trước tính chất của các cụm mà phải dựa vào mối quan hệ giữa các đối tượng để tìm ra sự giống nhau đặc trưng cho mỗi cụm giữa các đối tượng theo một độ đo nào đó.

Phân cụm là một bài toán cơ bản trong học máy (machine learning). Với bài toán này, các mô hình được thiết lập sẽ tự phân chia dữ liệu thành các cụm khác nhau. Bài toán này còn được gọi là học không giám sát, hay học không nhãn (unsupervised learning), có nghĩa rằng dữ liệu để huấn luyện mô hình không được gán nhãn trước (xt. Học máy).

Phương pháp K-MEANS

Có rất nhiều các phương pháp phân cụm, mỗi một phương pháp đều có nhiều thuật toán tương ứng. Tuỳ thuộc vào từng bài toán cụ thể mà ta có thể áp dụng các thuật toán khác nhau. Việc chọn lựa một thuật toán thích hợp phụ thuộc vào kiểu dữ liệu cần thực hiện cũng như mục đích của ứng dụng.

Khi nói đến phân cụm, K-MEANS là phương pháp kinh điển được sử dụng rất rộng rãi trong thực tế và nó có thể được biến đổi để thích hợp cho từng bài toán cụ thể, và nó nằm trong nhóm các phương pháp phân hoạch. Ý tưởng chính của phương pháp phân hoạch là xác định số cụm trước và xác định luôn tính chất của từng cụm. Sau đó với mỗi một điểm dữ liệu tìm cách đưa điểm dữ liệu đó vào cụm thích hợp nhất. Phương pháp này được J. B. MacQueen đưa ra vào năm 1967. Phương pháp K-MEANS được thể hiện bằng các bước sau:

• Bước 1: chọn k điểm dữ liệu làm điểm tâm (center), (ví dụ như thuật toán MacQueen là lấy k điểm dữ liệu đầu tiên). Trong những trường hợp tổng quát, việc chọn tâm cụm là những điểm có khoảng cách không gian giữa chúng lớn để có thể đáp ứng được việc phân cụm tốt hơn.

• Bước 2: phân mỗi điểm dữ liệu vào cụm có tâm gần nó nhất về mặt khoảng cách.

• Bước 3: tính lại điểm tâm của các cụm. Một cách đơn giản để tính lại điểm tâm của cụm là xác định trung bình cộng của tất cả các điểm trong cụm.

• Bước 4: lặp lại quá trình trên bắt đầu từ Bước 2 cho đến khi không có sự thay đổi về cụm của các điểm dữ liệu (nghĩa là điểm tâm sẽ không thay đổi trong một sai số cho phép).

Mặc dù thuật toán K-MEANS khá đơn giản và thuật toán sẽ dừng sau một số hữu hạn vòng lặp, nhưng thuật toán này có một số hạn chế như sau:

1/ Cần biết trước số lượng cụm;

2/ Nghiệm cuối cùng phụ thuộc vào các tâm được khởi tạo ban đầu;

3/ Các cụm cần có số lượng điểm gần bằng nhau;

4/ Các cụm phải có hình dạng lồi;

5/ Không phân cụm được khi một cụm nằm phía trong một cụm khác. Để giải quyết các hạn chế của K-MEANS, đã có nhiều nghiên cứu và các đề xuất thuật toán cải tiến.

Các phương pháp phân cụm được chia thành các cách tiếp cận chính sau: phương pháp phân hoạch (K-MEANS, CLARANS), phương pháp phân cấp (từ dưới lên hay từ trên xuống như CURE, Chameleon, BIRCH), phương pháp dựa vào mật độ (DBSCAN, OPTICS, DENCLUE), phương pháp chia lưới (STING, Wave Cluster, CLIQUE), phương pháp dựa vào mô hình (xác định các lớp bằng cách xây dựng một hàm mật độ phản ánh sự phân bố không gian của các điểm dữ liệu). Các thuật toán dạng này dựa vào giả định rằng dữ liệu thường được phân bố theo một phân bố xác suất nào đó. Các phương pháp phân cụm dựa vào mô hình thường theo hai cách tiếp cận: cách tiếp cận thống kê và tiếp cận dùng mạng nơron.

Việc đánh giá độ hiệu quả, xác định tính “chính xác” của phân cụm là một bài toán không có lời giải chính xác, đặc biệt trong bối cảnh của Dữ liệu lớn. Có nhiều độ đo được đưa ra để xác định hiệu quả của phân cụm.

Thuật ngữ "K-MEANS" được James MacQueen sử dụng lần đầu tiên vào năm 1967, mặc dù ý tưởng này được xuất phát từ Hugo Steinhaus vào năm 1956. Thuật toán tiêu chuẩn được đề xuất lần đầu tiên bởi Stuart Lloyd của Bell Labs vào năm 1957 như một kỹ thuật cho điều chế mã xung, mặc dù nó không được xuất bản dưới dạng một bài báo cho đến năm 1982. Năm 1965, Edward W. Forgy đã công bố về cơ bản cùng một phương pháp, đó là lý do tại sao nó đôi khi được gọi là Lloyd-Forgy.

Vai trò

Phân cụm được sử dụng trong rất nhiều bài toán xử lý dữ liệu, vì nó có thể đưa ra một cái nhìn tổng thể cho toàn bộ dữ liệu, và là một hoạt động quan trọng của con người. Khi còn bé, con người học cách phân biệt giữa các đồ vật, giữa động vật và thực vật bằng cách liên tục thay đổi nhận thức trong quan niệm phân chia các đối tượng dựa vào mối tương quan giữa chúng. Việc phân cụm đã được sử dụng rộng rãi trong các ứng dụng của nhiều lĩnh vực, bao gồm nhận dạng mẫu, phân tích dữ liệu, xử lý ảnh và phân tích thị trường. Trong kinh doanh, phân cụm có thể giúp các nhà nghiên cứu thị trường phát hiện được các nhóm khách hàng khác nhau và đặc tính của từng nhóm khách hàng dựa vào dữ liệu mua bán. Trong sinh học, phân cụm được dùng để chia nhóm các loài thực vật và động vật, phân loại gen có chức năng tương tự nhau và có được những thông tin chi tiết hơn về cấu trúc các vùng dân cư. Phân cụm cũng giúp cho việc nhận dạng các mẫu đất giống nhau dựa trên cơ sở dữ liệu quan sát trái đất, phân chia các nhóm nhà trong thành phố theo các tiêu chí như giá trị, vị trí địa lý của ngôi nhà. Đồng thời phân cụm còn sử dụng để phân chia các nhóm tài liệu trên Web dựa vào nội dung thông tin.

Với vai trò là chức năng trong khai phá dữ liệu, phân cụm có thể sử dụng như là một công cụ độc lập để thu thập thông tin về sự phân bố dữ liệu, để quan sát các đặc tính của một lớp nhờ đó tập trung được vào từng lớp cụ thể cho các bước phân tích sau. Như trên đã chỉ ra, còn nhiều thách thức và hạn chế của thuật toán phân cụm, nên nhiều nghiên cứu đã tập trung giải quyết các vấn đề trên.

Phân cụm không chỉ được nghiên cứu và ứng dụng trên thế giới mà cũng được cài đặt áp dụng rộng rãi tại Việt Nam. Một số nhà nghiên cứu người Việt cũng đã có những đóng góp nhất định trong phát triển phương pháp tìm tâm khởi tạo ban đầu, tối ưu hóa các hàm mục tiêu và phần đông cộng đồng phát triển sử dụng phân cụm như là một công cụ để phục vụ giải các bài toán của mình.

Tài liệu tham khảo

1. Tom M Mitchell et al. Machine Learning, McGraw Hill, 1997.
2. Rui Xu; D. Wunsch, Survey of clustering algorithms, IEEE Transactions on Neural Networks, Volume: 16, Issue: 3, May 2005.
3. Dongkuan Xu & Yingjie Tian, A Comprehensive Survey of Clustering Algorithms, Annals of Data Science volume 2, pages165–193 (2015).
4. Pulkit Sharma, The Most Comprehensive Guide to K-Means Clustering You’ll Ever Need, Analytics Vydhya, August 19, 2019.