Chào mừng đến với BIS Đăng nhập | Đăng ký | Trợ giúp
trong Tìm kiếm

Vấn đề xác định số cụm k trong bài toán phân cụm dữ liệu

Bài cuối 06-27-2018 01:49 PM của chucnv. 0 trả lời.
Trang 1 trong số 1 (1 nội dung)
Sắp xếp bài viết: Trước Tiếp theo
  • 06-27-2018 01:49 PM

    • chucnv
    • 10 thành viên năng nổ nhất
    • Tham gia 12-05-2008
    • Điểm 9,920

    Vấn đề xác định số cụm k trong bài toán phân cụm dữ liệu

    Vấn đề xác định số cụm k trong bài toán phân cụm dữ liệu

    chuc1803@gmail.com; http://bis.net.vn

    Trong các thuật toán phân cụm dữ liệu (ví dụ k-means), trong đó k là số cụm phải được xác định trước khi tiến hành phân cụm. Câu hỏi đặt ra là với dataset đã có phân thành bao nhiêu cụm là hợp lý (tối ưu)? Bài viết này giới thiệu về cách sử dụng R để thực hiện 3 phương pháp thường dùng để chọn số cụm k trong bài toán phân cụm dữ liệu là Elbow, Average silhouette Gap statistic

    Elbow method

    Tư tưởng chính của phương pháp phân cụm phân hoạch (như k-means) là định nghĩa 1 cụm sao cho tổng biến thiên bình phương khoảng cách trong cụm là nhỏ nhất, tham số này là WSS (Within-cluster Sum of Square)

    Elbow method chọn số sụm k sao cho khi thêm vào  một cụm khác thì không làm cho WSS thay đổi nhiều.

    Qui trình triển khai Elbow method như sau:

    1.      Triển khai thuật toán phân cụm (ví dụ k-mean) với các số cụm k thay đổi (ví dụ từ 1 đến 10)

    2.      Với mỗi giá trị k, tính giá trị WSS

    3.      Vẽ Elbow curve theo các giá trị k.

    4.      Dựa vào Elbow curve chọn số k thích hợp, là vị trí ở khúc cua (bend|knee)

    Average silhouette method

    Average silhouette dùng để đo lường chất lượng của một cụm. Nó xác định mức độ phù hợp của một đối tượng trong một cụm.

    Qui trình triển khai Average silhouette method như sau:

    1.      Triển khai thuật toán phân cụm (ví dụ k-mean) với các số cụm k thay đổi (ví dụ từ 1 đến 10)

    2.      Với mỗi gái trị k, tính giá trị average silhouette (avg.sil)

    3.      Vẽ đồ thị avg.sil  theo các giá trị k.

    4.      Vị trí có avg.sil lớn nhất là số cụm k cần tìm

    Gap statistic method

    Gap statistic lựa chọn giá trị k dựa vào so sánh độ biến động trong các cụm (total within intra-cluster variation) đối với các giá trị k khác nhau.

    Xem chi tiết về Gap statistic method tại đây: https://datasciencelab.wordpress.com/tag/gap-statistic/

    Minh họa xác định số cụm k trong R

    Yêu cầu:

    Sử dụng 2 packages trong R là factoextraNbClust

    Dataset demo: USArrests (dữ liệu về tình hình tội phạm của các bang ở Mỹ, xem giải thích tại đây: https://stat.ethz.ch/R-manual/R-devel/library/datasets/html/USArrests.html)

    Download Code R xác định số cụm k tại ĐÂY


     

    #Install and load requirement pacakges

    install.packages("factoextra")

    install.packages("NbClust")

    library(factoextra)

    library(NbClust)

    # standardizing the data to make variables comparable

    df <- scale(USArrests)

    # Elbow method

    fviz_nbclust(df, kmeans, method = "wss") + geom_vline(xintercept = 4, linetype = 2)+

      labs(subtitle = "Elbow method")


     

    # Silhouette method

    fviz_nbclust(df, kmeans, method = "silhouette")+labs(subtitle = "Silhouette method")


     

    # Gap statistic

    set.seed(123)

    fviz_nbclust(df, kmeans, nstart = 25,  method = "gap_stat", nboot = 50)+

      labs(subtitle = "Gap statistic method")


     

    Số cụm của các phương pháp xác định như sau:

    Elbow method: 4; Silhouette method: 2; Gap statistic method: 4

    Với dataset USArrests thì số cụm k=4 là tối ưu

    NbClust() function: gồm 30 chỉ số để chọn số cụm tốt nhất (xem về package NbClust tại đây: https://cran.r-project.org/web/packages/NbClust/index.html)

    #min.nc, max.nc: minimal and maximal number of clusters, respectively

    #method: The cluster analysis method to be used including “single”, “complete”, “average”, “kmeans”

    library("NbClust")

    nb <- NbClust(df, distance = "euclidean", min.nc = 2, max.nc = 10, method = "kmeans")


     

    #The result of NbClust using the function fviz_nbclust() [in factoextra]:

    library("factoextra")

    fviz_nbclust(nb)


     

    XEM VIDEO HƯỚNG DẪN TẠI ĐÂY

     

    • Điểm chủ đề: 20
Trang 1 trong số 1 (1 nội dung)
Powered by Community Server (Commercial Edition), by Telligent Systems