رمزگشایی الگوریتم خوشه بندی طیفی – انجمن DEV

خوشه‌بندی طیفی روشی است برای خوشه‌بندی نقاط داده بر اساس شباهت یا قرابت آنها، نه فاصله یا فشردگی آنها. این الگوریتم از مقادیر ویژه و بردارهای ویژه یک ماتریس شباهت استفاده می کند تا داده ها را در فضایی با ابعاد پایین تر نمایش دهد، جایی که خوشه ها قابل تفکیک تر می شوند. این الگوریتم می‌تواند خوشه‌هایی با اشکال و اندازه‌های دلخواه را مدیریت کند، برخلاف k-means که خوشه‌های کروی را فرض می‌کند.

کار کردن

مرحله 1: یک ماتریس شباهت S برای نقاط داده بسازید، جایی که S[i][j] نشان دهنده شباهت یا قرابت بین i-امین و j-امین نقطه داده است. شباهت را می توان با روش های مختلفی اندازه گیری کرد، مانند هسته گاوسی، k-نزدیک ترین همسایه یا اپسیلون-همسایگی.
گام 2: ماتریس درجه D را برای ماتریس شباهت S محاسبه کنید، جایی که D[i][i] مجموع ردیف i-امین S و D است[i][j] صفر است برای i برابر j نیست. ماتریس درجه نشان دهنده میزان اتصال هر نقطه داده است.
مرحله 3: ماتریس لاپلاسی L را برای ماتریس شباهت S و ماتریس درجه D محاسبه کنید، که در آن L = D – S. ماتریس لاپلاسی تفاوت بین درجه یک نقطه داده و شباهت آن با سایر نقاط داده را نشان می دهد.
مرحله 4: مقادیر ویژه و بردارهای ویژه ماتریس لاپلاسی L را محاسبه کنید و آنها را به ترتیب صعودی مرتب کنید. k کوچکترین مقادیر ویژه و بردارهای ویژه مربوط به آنها را انتخاب کنید، جایی که k تعداد خوشه های مورد نظر است. بردارهای ویژه ویژگی های جدیدی را نشان می دهند که به بهترین شکل ساختار داده ها را به تصویر می کشند.
مرحله 5: با قرار دادن k بردارهای ویژه به عنوان ستون، ماتریس U را تشکیل دهید. هر ردیف U نشان دهنده یک نقطه داده در فضای ویژگی جدید است.
مرحله 6: خوشه بندی k-means را روی ردیف های U اعمال کنید تا خوشه های k را به دست آورید.

شبه کد

# Input: data points X, number of clusters k, similarity measure S
# Output: cluster assignments C

# Step 1: Construct the similarity matrix S
S = similarity_matrix(X, S)

# Step 2: Compute the degree matrix D
D = degree_matrix(S)

# Step 3: Compute the Laplacian matrix L
L = laplacian_matrix(D, S)

# Step 4: Compute the eigenvalues and eigenvectors of L
E, V = eigen(L)

# Sort the eigenvalues and eigenvectors in ascending order
E, V = sort(E, V)

# Choose the k smallest eigenvalues and eigenvectors
E_k = E[:k]
V_k = V[:k]

# Step 5: Form the matrix U by stacking V_k as columns
U = stack(V_k)

# Step 6: Apply k-means clustering on U
C = kmeans(U, k)

# Return the cluster assignments
return C

مزایای

• برخلاف k-means که خوشه های کروی را فرض می کند، می تواند خوشه هایی با اشکال و اندازه های پیچیده را مدیریت کند.
• می‌تواند ساختار کلی داده‌ها را با استفاده از ویژگی‌های طیفی ماتریس شباهت به تصویر بکشد.
• با استفاده از روش های جبر خطی استاندارد به راحتی می توان آن را پیاده سازی کرد.

معایب

• این نیاز به انتخاب k از قبل دارد که می تواند دشوار یا دلخواه باشد.
• نسبت به انتخاب معیار تشابه حساس است که می تواند بر کیفیت و تعداد خوشه ها تأثیر بگذارد.
• این می تواند از نظر محاسباتی گران باشد، زیرا نیاز به محاسبه و تجزیه یک ماتریس شباهت بزرگ دارد.

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

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

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

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

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