AHC Clustering Algorithm Demystified – DEV Community

AHC مخفف Agglomerative Hierarchical Clustering است که یک الگوریتم خوشه بندی سلسله مراتبی است که درختی از خوشه ها را با ادغام خوشه های کوچکتر به خوشه های بزرگتر ایجاد می کند. الگوریتم بر خلاف k-means یا GMM نیازی به تعیین تعداد خوشه ها از قبل ندارد. در عوض، امکان انتخاب هر تعداد خوشه را با بریدن درخت در سطح مناسب فراهم می کند.

کار کردن

مرحله 1: هر نقطه داده را به عنوان یک خوشه تک تنی در نظر بگیرید و ماتریس فاصله بین همه جفت خوشه ها را محاسبه کنید.
گام 2: جفت خوشه هایی را با کمترین فاصله پیدا کنید و آنها را در یک خوشه جدید ادغام کنید. با حذف سطرها و ستون های خوشه های ادغام شده و افزودن سطر و ستون برای خوشه جدید، ماتریس فاصله را به روز کنید.
مرحله 3: مرحله 2 را تکرار کنید تا فقط یک خوشه که ریشه درخت است باقی بماند.

شبه کد

# Input: data points X, distance measure D
# Output: cluster tree T

# Step 1: Initialize n singleton clusters and n X n distance matrix
C = singleton_clusters(X)
M = distance_matrix(C, D)

# Initialize cluster tree
T = empty_tree()

# Loop until there is only one cluster left
while C.size > 1:

    # Step 2: Find the pair of clusters with the smallest distance and merge them
    i, j = argmin(M)
    new_cluster = merge(C[i], C[j])

    # Update the distance matrix
    M = update_matrix(M, i, j, new_cluster, D)

    # Update the cluster list
    C = update_list(C, i, j, new_cluster)

    # Step 3: Add the merged cluster to the tree
    T = add_node(T, new_cluster)

# Return the final cluster tree
return T

مزایای

• برخلاف k-means یا GMM که خوشه های مسطح تولید می کنند، می تواند سلسله مراتب و ساختار داده ها را به تصویر بکشد.
• برخلاف k-means که خوشه های کروی را فرض می کند، می تواند خوشه هایی با اشکال و اندازه های مختلف را مدیریت کند.
• برخلاف k-means یا GMM که به k به عنوان ورودی نیاز دارند، می‌تواند هر تعداد خوشه را با بریدن درخت در سطح مناسب انتخاب کند.

معایب

• از نظر محاسباتی گران است، زیرا نیاز به محاسبه و به روز رسانی یک ماتریس فاصله بزرگ در هر تکرار دارد.
• به نویز و نقاط پرت حساس است، زیرا می توانند بر اندازه گیری فاصله و فرآیند ادغام تأثیر بگذارند.
• رسیدگی به تراکم های مختلف خوشه دشوار است، زیرا ممکن است بسته به اندازه گیری فاصله، خوشه ها را خیلی زود یا خیلی دیر ادغام کند.

مراجع و مطالعه بیشتر

این یک سری چند قسمتی خواهد بود که با الگوریتم‌های خوشه‌بندی بیشتر با عملکرد، شبه کد، مزایا و معایب آن‌ها دنبال می‌شود.

لطفاً منتظر مطالب بیشتر از این دست باشید.

اگر این پست را دوست داشتید، لطفاً آن را با دوستان و توسعه دهندگان خود به اشتراک بگذارید. و فراموش نکنید که برای آموزش های برنامه نویسی و نمونه های بیشتر ما را دنبال کنید! 😊

و همچنین،
نگاهی بیندازید👀 @ نمونه کارها من
کد👨‍💻 با هم @ Github
اتصال @ LinkedIn