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

Kỹ thuật phân nhóm theo thứ bậc (Hierarchical Clustering Techniques)

Bài cuối 05-29-2013 03:30 PM của clairsang. 3 trả lời.
Trang 1 trong số 1 (4 nội dung)
Sắp xếp bài viết: Trước Tiếp theo
  • 01-16-2012 02:47 PM

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

    Kỹ thuật phân nhóm theo thứ bậc (Hierarchical Clustering Techniques)

    Kỹ thuật phân nhóm theo thứ bậc (Hierarchical Clustering Techniques)

    Nguyễn Văn Chức – chucnv@ud.edu.vn

    Trong kỹ thuật phân nhóm theo thứ bậc (Hierarchical Clustering Techniques), có 2 phương pháp chính đó là:

    Agglomerative Aapproach (bottom up approach):  Ban đầu, chúng ta xem mỗi đối tượng là 1 nhóm (cluster) và nhóm 2 đối tượng gần nhất thành 1 cluster. Quá trình này lặp lại cho đến khi tất cả các đối tượng được nhóm vào 1 cluster cuối cùng.

    Divisive Approach (top down approach): Quá trình ngược lại với Agglomerative Approach, ban đầu chúng ta xem tất cả các đối tượng thuộc cùng 1 cluster, sau đó tiến hành phân thành 2 nhóm con (thường dựa vào khoảng cách lớn nhất). Quá trình này được thực hiện cho đến khi mỗi nhóm chỉ còn 1 đối tượng.

    Trong phần này sẽ giới thiệu kỹ thuật phân nhóm Agglomerative Approach

    Các bước trong kỹ thuật phân cụm Agglomerative Approach như sau:

    1.      Chuyển đổi các đặc trưng (thuộc tính - Features) của đối tượng (objects) vào ma trận khoảng cách

    2.      Xem mỗi đối tượng là một cluster (chẳn hạn, nếu ta có 4 đối tượng, ban đầu chúng ta sẽ có 4 clusters)

    3.      Lặp lại 2 bước sau cho đến khi số cluster bằng 1

    a.       Gộp 2 cluster gần nhất

    b.      Cập nhật ma trận khoảng cách

    Thuật toán Agglomerative Hierarchical Clustering (gọi tắt là AHC) được mô tả như sau:


     Để hiểu hơn về thuật toán AHC, các bước của thuật toán AHC sẽ được minh họa thông qua ví dụ đơn giản sau.

    Giả sử ta có 6 đối tượng (objects) cần phân nhóm (tên của các đối tượng là A,B,C,D,E,F), mỗi đối tượng có 2 thuộc tính X1 và X2 như sau:


    Chúng ta sẽ dùng thuật toán AHC để phân nhóm các đối tượng này

    Chuyển sang ma trận khoảng cách (From Object Features to Distance Matrix)


    Khoảng cách giữa các đối tượng được biểu diễn bởi ma trận khoảng cách Dist. Khoảng cách Euclidean thường được dung để tính khoảng cách giữ 2 đối tượng như sau:


     

     

    Chú ý: Dist là ma trận đối xứng qua đường chéo chính (vì khoảng cách từ A đến B bằng khoảng cách từ B đến A) nên chúng ta chỉ quan tâm đến phần bên trên hoặc bên dưới đường chéo chính. Trong ma trận khoảng cách, các phần tử trên đường chéo chính bằng 0 (khoảng cách đến chính nó).

    Một cách tổng quát, nếu ta có m đối tượng, số khoảng cách giữa các đối tượng (bên trên hoặc bên dưới đường


     Bây giờ chúng ta đã có ma trận khoảng cách, công việc tiếp theo là tính liên kết giữa các đối tượng như sau:

    Tính liên kết giữa các đối tượng (compute linkages between objects )

    Có rất nhiều cách tính linkage, trong đó các cách sau đây thường được sử dụng

    Single Linkage: Khoảng cách giữa 2 clusters được tính là khoảng cách giữa 2 đối tượng gần nhau nhất trong 2 clusters đó (minimum distance). Xem hình dưới


    Average Group: Khoảng cách giữa 2 clusters được tính là khoảng cách trung bình giữa các đối tượng trong 2 clusters đó (average distance).Xem hình dưới

    Trong ví dụ này, tôi sử dụng Single Linkage  để xác đinhk khoảng cách giữa 2 clusters.

    Trong ví dụ đã cho,  ta có 6 đối tượng (A,B,C,D,E,F). Ban đầu ta xem mỗi đối tượng là 1 cluster. Vì vậy, ban đầu ta có 6 clusters. Mục đích của ta là gộp 6 clusters này lại để đến cuối cùng ta có được 1 cluster bao gồm 6 đối tượng đã cho.


    Trong mỗi bước lặp, chúng ta tìm 2 clusters gần nhau nhất (sử dụng Single Linkage) để gộp thành 1 cluster. Trong ví dụ này, ta có cluster D và F là gần nhau nhất (khoảng cách là 0.50) vì vậy ta nhóm D và F vào 1 cluster (D,F). Sau đó tính lại ma trận khoảng cách Dist. Chú ý là khoảng cách giữa các cluster không được nhóm (A,B,C,E) không thay đổi. vấn đề là làm sao để tỉnh khoảng cách từ cluster mới (D,F) đến các clusters khác?.



    Cập nhật ma trận khoảng cách Dist


    Từ ma trận khoảng cách Dist, ta thấy rằng 2 clusters gần nhau nhất là A và B. Vì vậy ta nhóm A và B thành 1 cluster (A,B)

    Tính lại khoảng cách giữa các clusters


    Cập nhật ma trận khoảng cách


    Ta nhóm 2 clusters E và (D,F) thành 1 cluster ((D, F), E ) vì khoảng cách giữa 2 clusters này là nhỏ nhất (1.0)

    Cập nhật ma trận khoảng cách như sau


     Cập nhật ma trận khoảng cách như sau


    Có thể tổng kết quả các bước tính toán của thuật toán AHC trong ví dụ trên như sau:

    1.      Bắt đầu, ta có 6 clusters : A, B, C, D, E và F

    2.      Gộp 2 clusters  D và  F thành cluster (D, F) với khoảng cách nhỏ nhất là 0.50

    3.      Gộp 2 clusters  A và cluster B thành (A, B) với khoảng cách nhỏ nhất là 0.71

    4.      Gộp 2 clusters  E và  (D, F) thành ((D, F), E) với khoảng cách nhỏ nhất là 1.00

    5.      Gộp 2 clusters ((D, F), E) và  C thành (((D, F), E), C) với khoảng cách nhỏ nhất là 1.41

    6.      Gộp 2 clusters (((D, F), E), C) và (A, B) thành ((((D, F), E), C), (A, B)) với khoảng cách nhỏ nhất là 2.50

    7.      Cluster cuối cùng bao gồm tất cả 6 đối tượng ban đầu, thuật toán dừng

    Quá trình phân cụm theo thuật toán AHC trong ví dụ trên được minh họa như hình sau:


    Thứ tự phân cụm như sau (((D, F), E),C), (A,B).


     Kỹ thuật phân nhóm Hierarchical Clustering hiện nay được triển khai trong rất nhiều phần mềm khai phá dữ liệu (Data Mining Softwares) như Weka, XLSTAT, XLMiner, Clementine (của SPSS),….

     PS. All comments please send to chucnv@ud.edu.vn. Thank you and Welcome!

    • Điểm chủ đề: 50
  • 05-03-2012 09:11 PM trả lời

    • trungnv
    • 500 thành viên năng nổ nhất
    • Tham gia 05-03-2012
    • Điểm 135

    Re: Kỹ thuật phân nhóm theo thứ bậc (Hierarchical Clustering Techniques)

    Em chào anh!
    Em đang tìm hiểu về phân cụm, thật may tìm đc bài viết của anh, rất hay và dễ hiểu.
    Em có 1 thắc mắc là dùng thuật toán thứ tự như trên thì mình có thể chia các phần tử vào số nhóm cho trước đc ko ạ (chẳng hạn mình muốn chia 6 phần tử như vd trên vào 3 nhóm phân biệt rõ ràng).
    cám ơn anh. 
    • Điểm chủ đề: 35
  • 04-02-2013 06:12 PM trả lời

    • tutruong
    • 10 thành viên năng nổ nhất
    • Tham gia 03-30-2013
    • Điểm 255

    Re: Kỹ thuật phân nhóm theo thứ bậc (Hierarchical Clustering Techniques)

    Những bài toán như thế nào thì có thể áp dụng thuật toán phân cụm Agglomerative Approach (bottom up) hoặc Divisive Approach (top down).
    • Điểm chủ đề: 20
  • 05-29-2013 03:30 PM trả lời

    Re: Kỹ thuật phân nhóm theo thứ bậc (Hierarchical Clustering Techniques)

    Anh Chức có thể giải thích cho em về Ward linkage ko ạ?
    Cảm ơn anh.
    • Điểm chủ đề: 20
Trang 1 trong số 1 (4 nội dung)
Powered by Community Server (Commercial Edition), by Telligent Systems