Thuật toán phân cụm - Tổng quan

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

Các phương pháp phân cụm là một trong những phương pháp ML không giám sát hữu ích nhất. Các phương pháp này được sử dụng để tìm sự tương đồng cũng như các mẫu mối quan hệ giữa các mẫu dữ liệu và sau đó phân cụm các mẫu đó thành các nhóm có sự tương đồng dựa trên các tính năng.

Phân cụm rất quan trọng vì nó quyết định việc nhóm nội tại giữa các dữ liệu không được gắn nhãn hiện tại. Về cơ bản, họ đưa ra một số giả định về các điểm dữ liệu để tạo nên sự giống nhau của chúng. Mỗi giả định sẽ xây dựng các cụm khác nhau nhưng đều hợp lệ.

Ví dụ: dưới đây là sơ đồ cho thấy hệ thống phân cụm được nhóm cùng loại dữ liệu tương tự trong các cụm khác nhau -

Phương pháp hình thành cụm

Không nhất thiết các cụm sẽ được hình thành ở dạng hình cầu. Tiếp theo là một số phương pháp hình thành cụm khác -

Dựa trên mật độ

Trong các phương pháp này, các cụm được hình thành dưới dạng vùng dày đặc. Ưu điểm của các phương pháp này là có độ chính xác cũng như khả năng ghép hai cụm tốt. Ví dụ. Phân cụm không gian dựa trên mật độ của các ứng dụng có tiếng ồn (DBSCAN), Điểm thứ tự để xác định cấu trúc phân cụm (OPTICS), v.v.

Dựa trên phân cấp

Trong các phương pháp này, các cụm được hình thành như một cấu trúc kiểu cây dựa trên hệ thống phân cấp. Chúng có hai loại cụ thể là Agglomerative (Cách tiếp cận từ dưới lên) và Phân chia (Cách tiếp cận từ trên xuống). Ví dụ. Phân cụm bằng cách sử dụng Đại diện (CURE), Phân cụm lặp lại cân bằng Giảm phân cụm bằng cách sử dụng Cấu trúc phân cấp (BIRCH), v.v.

Phân vùng

Trong các phương pháp này, các cụm được hình thành bằng cách phân chia các đối tượng thành k cụm. Số lượng cụm sẽ bằng số lượng phân vùng. Ví dụ. K-means, Nhóm các ứng dụng lớn dựa trên Tìm kiếm ngẫu nhiên (CLARANS).

Lưới

Trong các phương pháp này, các cụm được hình thành như một cấu trúc giống như lưới. Ưu điểm của các phương pháp này là tất cả các hoạt động phân cụm được thực hiện trên các lưới này là nhanh chóng và không phụ thuộc vào số lượng đối tượng dữ liệu. Ví dụ. Lưới thông tin thống kê (STING), Nhóm trong nhiệm vụ (CLIQUE).

Đo lường hiệu suất phân cụm

Một trong những cân nhắc quan trọng nhất liên quan đến mô hình ML là đánh giá hiệu suất của nó hoặc bạn có thể nói chất lượng của mô hình. Trong trường hợp thuật toán học có giám sát, việc đánh giá chất lượng mô hình của chúng tôi rất dễ dàng vì chúng tôi đã có nhãn cho mọi ví dụ.

Mặt khác, trong trường hợp các thuật toán học tập không được giám sát, chúng tôi không có nhiều may mắn vì chúng tôi xử lý dữ liệu không được gắn nhãn. Nhưng chúng tôi vẫn có một số số liệu cung cấp cho người thực hành cái nhìn sâu sắc về sự thay đổi trong các cụm tùy thuộc vào thuật toán.

Trước khi đi sâu vào các số liệu như vậy, chúng ta phải hiểu rằng các số liệu này chỉ đánh giá hiệu suất so sánh của các mô hình với nhau chứ không phải đo lường tính hợp lệ của dự đoán của mô hình. Tiếp theo là một số chỉ số mà chúng tôi có thể triển khai trên các thuật toán phân cụm để đo chất lượng của mô hình -

Phân tích Silhouette

Phân tích Silhouette được sử dụng để kiểm tra chất lượng của mô hình phân cụm bằng cách đo khoảng cách giữa các cụm. Về cơ bản, nó cung cấp cho chúng tôi một cách để đánh giá các thông số như số lượng cụm với sự trợ giúp củaSilhouette score. Điểm này đo lường mức độ gần của mỗi điểm trong một cụm với các điểm trong các cụm lân cận.

Phân tích điểm Silhouette

Phạm vi của điểm Silhouette là [-1, 1]. Phân tích của nó như sau:

+1 Score - Gần +1 Silhouette score chỉ ra rằng mẫu ở xa cụm lân cận của nó.
0 Score - 0 Silhouette score chỉ ra rằng mẫu nằm trên hoặc rất gần ranh giới quyết định ngăn cách hai cụm lân cận.
-1 Score & trừ đi -1 Silhouette score chỉ ra rằng các mẫu đã được chỉ định vào các cụm sai.

Việc tính điểm Silhouette có thể được thực hiện bằng công thức sau:

= (-) / (,)

Đây, = khoảng cách trung bình đến các điểm trong cụm gần nhất

Và, = nghĩa là khoảng cách trong cụm đến tất cả các điểm.

Chỉ số Davis-Bouldin

Chỉ số DB là một số liệu tốt khác để thực hiện phân tích các thuật toán phân cụm. Với sự trợ giúp của chỉ mục DB, chúng ta có thể hiểu những điểm sau về mô hình phân cụm:

Thời tiết các cụm có cách xa nhau hay không?
Mật độ của các cụm là bao nhiêu?

Chúng ta có thể tính toán chỉ số DB với sự trợ giúp của công thức sau:

$$ DB = \ frac {1} {n} \ displaystyle \ sum \ limit_ {i = 1} ^ n max_ {j \ neq {i}} \ left (\ frac {\ sigma_ {i} + \ sigma_ {j }} {d (c_ {i}, c_ {j})} \ right) $$

Đây, = số cụm

σ _i = khoảng cách trung bình của tất cả các điểm trong cụm tính từ trung tâm cụm.

Chỉ số DB ít hơn, mô hình phân cụm tốt hơn.

Chỉ số Dunn

Nó hoạt động giống như chỉ mục DB nhưng có những điểm sau mà cả hai đều khác nhau:

Chỉ số Dunn chỉ xem xét trường hợp xấu nhất tức là các cụm gần nhau trong khi chỉ số DB xem xét sự phân tán và tách biệt của tất cả các cụm trong mô hình phân cụm.
Chỉ số Dunn tăng khi hiệu suất tăng lên trong khi chỉ số DB trở nên tốt hơn khi các cụm có khoảng cách tốt và dày đặc.

Chúng ta có thể tính toán chỉ số Dunn với sự trợ giúp của công thức sau:

$$ D = \ frac {min_ {1 \ leq i <{j} \ leq {n}} P (i, j)} {mix_ {1 \ leq i <k \ leq n} q (k)} $$

Đây, ,, = mỗi chỉ số cho các cụm

= khoảng cách giữa các cụm

q = khoảng cách trong cụm

Các loại thuật toán phân cụm ML

Sau đây là các thuật toán phân cụm ML quan trọng và hữu ích nhất -

K-có nghĩa là phân cụm

Thuật toán phân cụm này tính toán các centroid và lặp lại cho đến khi chúng tôi tìm thấy centroid tối ưu. Nó giả định rằng số lượng các cụm đã được biết trước. Nó còn được gọi là thuật toán phân cụm phẳng. Số lượng các cụm được xác định từ dữ liệu bằng thuật toán được biểu thị bằng 'K' trong K-mean.

Thuật toán Mean-Shift

Nó là một thuật toán phân cụm mạnh mẽ khác được sử dụng trong học tập không giám sát. Không giống như K-mean clustering, nó không đưa ra bất kỳ giả định nào do đó nó là một thuật toán phi tham số.

Phân cụm theo thứ bậc

Đó là một thuật toán học tập không giám sát khác được sử dụng để nhóm các điểm dữ liệu không được gắn nhãn có đặc điểm tương tự lại với nhau.

Chúng ta sẽ thảo luận chi tiết về tất cả các thuật toán này trong các chương sắp tới.

Các ứng dụng của phân cụm

Chúng ta có thể thấy phân cụm hữu ích trong các lĩnh vực sau:

Data summarization and compression- Phân cụm được sử dụng rộng rãi trong các lĩnh vực mà chúng ta yêu cầu tổng hợp, nén và giảm dữ liệu. Các ví dụ là xử lý hình ảnh và lượng tử hóa vector.

Collaborative systems and customer segmentation - Vì phân cụm có thể được sử dụng để tìm các sản phẩm tương tự hoặc cùng một loại người dùng, nó có thể được sử dụng trong lĩnh vực hệ thống cộng tác và phân khúc khách hàng.

Serve as a key intermediate step for other data mining tasks- Phân tích cụm có thể tạo ra một bản tóm tắt dữ liệu nhỏ gọn để phân loại, kiểm tra, tạo giả thuyết; do đó, nó cũng đóng vai trò là bước trung gian quan trọng cho các tác vụ khai thác dữ liệu khác.

Trend detection in dynamic data - Phân cụm cũng có thể được sử dụng để phát hiện xu hướng trong dữ liệu động bằng cách tạo các cụm xu hướng tương tự khác nhau.

Social network analysis- Phân cụm có thể được sử dụng trong phân tích mạng xã hội. Các ví dụ đang tạo chuỗi trong hình ảnh, video hoặc âm thanh.

Biological data analysis - Phân cụm cũng có thể được sử dụng để tạo thành các cụm hình ảnh, video do đó nó có thể được sử dụng thành công trong phân tích dữ liệu sinh học.