Phương pháp khuỷu tay phân cụm phân cấp Python

Việc xác định số cụm tối ưu trong tập dữ liệu là một vấn đề cơ bản trong phân cụm phân vùng, chẳng hạn như phân cụm k-mean, yêu cầu người dùng chỉ định số cụm k sẽ được tạo

Thật không may, không có câu trả lời dứt khoát cho câu hỏi này. Số lượng cụm tối ưu theo cách nào đó mang tính chủ quan và phụ thuộc vào phương pháp được sử dụng để đo lường sự tương đồng và các tham số được sử dụng để phân vùng.
Một giải pháp đơn giản và phổ biến bao gồm việc kiểm tra chương trình dendro được tạo bằng cách sử dụng phân cụm theo thứ bậc để xem liệu nó có gợi ý một số cụm cụ thể hay không. Thật không may, cách tiếp cận này cũng chủ quan.

Trong chương này, chúng tôi sẽ mô tả các phương pháp khác nhau để xác định số lượng cụm tối ưu cho k-mean, k-medoids [PAM] và phân cụm theo thứ bậc

Các phương pháp này bao gồm phương pháp trực tiếp và phương pháp kiểm tra thống kê

1. phương pháp trực tiếp. bao gồm tối ưu hóa một tiêu chí, chẳng hạn như tổng bình phương trong cụm hoặc hình bóng trung bình. Các phương thức tương ứng được đặt tên tương ứng là các phương thức khuỷu tay và hình bóng
2. Phương pháp kiểm định thống kê. bao gồm so sánh bằng chứng chống lại giả thuyết không. Một ví dụ là thống kê khoảng cách

Ngoài các phương pháp thống kê khuỷu tay, hình bóng và khoảng cách, còn có hơn ba mươi chỉ số và phương pháp khác đã được xuất bản để xác định số lượng cụm tối ưu. Chúng tôi sẽ cung cấp mã R để tính toán tất cả 30 chỉ số này nhằm quyết định số lượng cụm tốt nhất bằng cách sử dụng “quy tắc đa số”

Đối với mỗi phương pháp này

• Chúng tôi sẽ mô tả ý tưởng cơ bản và thuật toán
• Chúng tôi sẽ cung cấp mã R dễ sử dụng với nhiều ví dụ để xác định số lượng cụm tối ưu và trực quan hóa đầu ra

nội dung

sách liên quan

phương pháp khuỷu tay

Nhớ lại rằng, ý tưởng cơ bản đằng sau các phương pháp phân vùng, chẳng hạn như phân cụm theo phương tiện k, là xác định các cụm sao cho tổng biến thể bên trong cụm [hoặc tổng bình phương bên trong cụm [WSS]] được giảm thiểu. Tổng WSS đo lường mức độ nhỏ gọn của cụm và chúng tôi muốn nó càng nhỏ càng tốt

Phương pháp Elbow xem tổng WSS là một hàm của số lượng cụm. Người ta nên chọn một số cụm để việc thêm một cụm khác không cải thiện tốt hơn nhiều so với tổng WSS

Số lượng cụm tối ưu có thể được xác định như sau

1. Tính toán thuật toán phân cụm [e. g. , k-nghĩa là phân cụm] cho các giá trị khác nhau của k. Chẳng hạn, bằng cách thay đổi k từ 1 đến 10 cụm
2. Đối với mỗi k, hãy tính tổng bình phương trong cụm [wss]
3. Vẽ đường cong của wss theo số cụm k
4. Vị trí của một khúc cua [đầu gối] trong ô thường được coi là một chỉ báo về số lượng cụm thích hợp

Lưu ý rằng, phương pháp khuỷu tay đôi khi không rõ ràng. Một phương pháp thay thế là phương pháp bóng trung bình [Kaufman và Rousseeuw [1990]] cũng có thể được sử dụng với bất kỳ phương pháp phân cụm nào

Phương pháp bóng trung bình

Phương pháp hình bóng trung bình chúng ta sẽ được mô tả toàn diện trong thống kê xác thực cụm chương. Tóm lại, nó đo lường chất lượng của một cụm. Nghĩa là, nó xác định mức độ tốt của từng đối tượng nằm trong cụm của nó. Chiều rộng hình bóng trung bình cao cho thấy sự phân cụm tốt

Phương pháp bóng trung bình tính toán bóng trung bình của các quan sát cho các giá trị khác nhau của k. Số cụm k tối ưu là số tối đa hóa hình bóng trung bình trên một loạt các giá trị có thể có của k [Kaufman và Rousseeuw 1990] .

Thuật toán tương tự như phương pháp khuỷu tay và có thể được tính toán như sau

1. Tính toán thuật toán phân cụm [e. g. , k-nghĩa là phân cụm] cho các giá trị khác nhau của k. Chẳng hạn, bằng cách thay đổi k từ 1 đến 10 cụm
2. Đối với mỗi k, hãy tính hình bóng trung bình của các quan sát [ avg. si ].
3. Viết đường cong của avg. sil theo số cụm k.
4. Vị trí của cực đại được coi là số lượng cụm thích hợp

Phương pháp thống kê khoảng cách

Thống kê khoảng cách đã được xuất bản bởi R. Tibshirani, G. Walther và T. Hastie [Đại học Stanford, 2001]. Cách tiếp cận có thể được áp dụng cho bất kỳ phương pháp phân cụm nào

Thống kê khoảng cách so sánh tổng số trong biến thể trong cụm đối với các giá trị khác nhau của k với các giá trị dự kiến ​​của chúng trong phân phối tham chiếu null của dữ liệu. Ước tính của các cụm tối ưu sẽ là giá trị tối đa hóa thống kê khoảng cách [i. e, mang lại thống kê khoảng cách lớn nhất]. Điều này có nghĩa là cấu trúc phân cụm khác xa với sự phân bố điểm đồng đều ngẫu nhiên

Thuật toán hoạt động như sau

1. Phân cụm dữ liệu được quan sát, thay đổi số lượng cụm từ k = 1, …, kmax và tính toán tổng số tương ứng trong phạm vi nội bộ . Wk.
2. Tạo tập dữ liệu tham chiếu B với phân phối đồng đều ngẫu nhiên. Nhóm từng tập dữ liệu tham chiếu này với số lượng cụm khác nhau k = 1, …, kmax và tính toán tổng số tương ứng trong phạm vi thay đổi trong cụm Wkb.
3. Tính toán thống kê khoảng cách ước tính là độ lệch của giá trị Wk quan sát được so với giá trị dự kiến ​​ Wkb . under the null hypothesis: \[Gap[k] = \frac{1}{B} \sum\limits_{b=1}^B log[W_{kb}^*] - log[W_k]\ . Tính cả độ lệch chuẩn của thống kê. . Compute also the standard deviation of the statistics.
4. Chọn số cụm là giá trị nhỏ nhất của k sao cho thống kê khoảng cách nằm trong một độ lệch chuẩn của khoảng cách tại k+1. Khoảng cách[k]≥Gap[k + 1]−sk + 1 .

Lưu ý rằng, sử dụng B = 500 cho kết quả khá chính xác để biểu đồ khoảng cách về cơ bản không thay đổi sau một lần chạy khác

Tính toán số lượng cụm bằng R

Trong phần này, chúng tôi sẽ mô tả hai chức năng để xác định số cụm tối ưu

1. Hàm fviz_nbclust[] [trên thực tế là gói R bổ sung]. Nó có thể được sử dụng để tính toán ba phương pháp khác nhau [thống kê khuỷu tay, hình bóng và khoảng cách] cho bất kỳ phương pháp phân cụm phân vùng nào [K-means, K-medoids [PAM], CLARA, HCUT]. Lưu ý rằng hàm hcut[] chỉ có trong gói factoextra. Nó tính toán phân cụm theo thứ bậc và cắt cây thành k cụm được chỉ định trước
2. Hàm NbClust[] [ trong gói NbClust R] [Charrad et al. 2014] . Nó cung cấp 30 chỉ số để xác định số lượng cụm có liên quan và đề xuất cho người dùng sơ đồ phân cụm tốt nhất từ ​​các kết quả khác nhau thu được bằng cách thay đổi tất cả các kết hợp số lượng cụm, thước đo khoảng cách và phương pháp phân cụm. Nó có thể tính toán đồng thời tất cả các chỉ số và xác định số lượng cụm trong một lệnh gọi hàm.

Gói R bắt buộc

Chúng tôi sẽ sử dụng các gói R sau

• factoextra để xác định các cụm số tối ưu cho một phương pháp phân cụm nhất định và để trực quan hóa dữ liệu
• NbClust để tính toán khoảng 30 phương thức cùng một lúc, để tìm số lượng cụm tối ưu

Để cài đặt các gói, gõ cái này

pkgs