در الگوریتم خوشه بندی k-means ما با چالش های خاصی رو برو هستیم برای مثال الگوریتم k-means همیشه سعی میکند خوشه هایی با اندازه های یکسان بسازد همچنین ما باید تعداد خوشه ها را ابتدای الگوریتم مشخص کنیم
در حالت ایده آل ما نمیدانیم چه تعداد خوشه باید درابتدای الگوریتم داشته باشیم با استفاده از روش سلسله مراتبی مشکل تعیین تعداد خوشه ها در ابتدای الگوریتم را از بین میبریم
الگوریتم سلسله مراتبی چیست ؟
خوشه بندی سلسلخه مراتبی یک تکنیک یادگیری بدون نظارت است که برای گروه بندی اشیا مشابه در خوشه ها استفاده میشود
خوشه بندی سلسله مراتبی اشیا مشابه را در یک دندروگرام گروه بندی میکند
ابتدا هر نقطه به صورت جداگانه خود یک خوشه است سپس خوشه های مشابه به طور مکرر ادغام میشوند این ساختار درخت مانند ایجاد میکند
دندروگرام از خوشه بندی سلسله مراتبی , سلسله مراتب خوشه ها را در سطوح مختلف نشان میدهد و گروه بندی های طبیعی را در داده ها برجسته میکند
- یک نمایش بصری از روابط بین خوشه ها را ارائه میکند
- به شناسایی الگو ها و نقاط پرت کمک میکند
📌انواع خوشه بندی سلسله مراتبی :
- Agglomerative Hierchical Cludtring
- Divisive Hierchical Clustring
📌 خوشه بندی سلسله مراتبی تجمعی (AHC) :
- در این الگوریتم هر نقطه را به یک خوشه اختصاص میدهیم
- سپس در هر تکرار نزدیک ترین جفت خوشه ها را ادغام میکنیم آن قدر این مرحله را انجام میدهیم تا تنها یک خوشه برای ما باقی بماند
به طور مکرر: دو گروهی که کمترین تفاوت را دارند ادغام کنید.
در یک دنباله خوشه بندی به شرح زیر است:
Step 1: {1}, {2}, {3}, {4}, {5}, {6}, {7};
Step 2: {1}, {2, 3}, {4}, {5}, {6}, {7};
Step 3: {1, 7}, {2, 3}, {4}, {5}, {6};
Step 4: {1, 7}, {2, 3}, {4, 5}, {6};
Step 5: {1, 7}, {2, 3, 6}, {4, 5};
Step 6: {1, 7}, {2, 3, 4, 5, 6};
Step 7: {1, 2, 3, 4, 5, 6, 7}.
ما همچنین میتوانیم دنباله تکالیف خوشه‌بندی را به صورت دندروگرام نشان دهیم:
توجه داشته باشید که برش دندروگرام به صورت افقی داده ها را پارتیشن بندی خوشه ها اشاره می کند
📌 خوشه بندی سلسله مراتبی (DHC) :
- این الگوریتم بر عکس عمل میکند تمام نقاط را داخل یک خوشه قرار میدهد
- در هر مرحله دورترین نقطه در خوشه را تقسیم میکنیم و به یک خوشه تبدیل میکنیم
- آن قدر این مرحله را انجام میدهیم تا انتها یک خوشه برای ما باقی بماند
به طور مکرر: تقسیم کردن را به دو دسته تقسیم کنید که منجر به بزرگترین عدم تشابه می شود
تمام نقاط داده را به عنوان یک خوشه واحد در نظر بگیرید.
- تقسیم به خوشه با استفاده از هر روش خوشه بندی مسطح، می گویند K-Means.
- بهترین خوشه را در میان خوشه ها برای تقسیم بیشتر انتخاب کنید، خوشه ای را انتخاب کنید که بیشترین مجموع خطای مربع (SSE) را داشته باشد.
- مراحل 2 و 3 را تکرار کنید تا یک خوشه واحد تشکیل شود.
- داده ها نشان می دهد 1.2,… 6 به خوشه بزرگ اختصاص داده شده است.
- پس از محاسبه ماتریس مجاورت، بر اساس عدم ناهمسانی، نقاط به خوشه های جداگانه تقسیم می شوند.
- ماتریس مجاورت دوباره محاسبه می شود تا زمانی که هر نقطه به یک خوشه اختصاص داده شود.
ماتریس مجاورت و تابع پیوند از همان روش خوشه بندی تراکمی پیروی می کنند، از انجا که خوشه بندی تقسیم شده در بسیاری از مکان ها استفاده نمی شود، هیچ کلاس / تابع از پیش تعریف شده ای در هیچ کتابخانه پایتون وجود ندارد.
📌 تشخیص نقاط مشابه و ادغام آنها :
- فاصله ی بین مرکز خوشه ها را در نظر میگیریم
- نقاط که کمترین فاصله را از هم دارند نقاط مشابه هستند پس میتوانیم این نقاط را ادغام کنیم
📌 ماتریس مجاورت ( Proximity Matrix) :
- یک ماتریس nxn است که فاصله ی هر یک از نقاط را به ما میدهد
- فاصله ی نقاط را از طریق فاصله ی اقلیدوسی محاسبه میکنیم به این ترتیب ماتریس مجاورت ما که یک ماتریس فاصله است ساخته میشود
📌 مراحل انجام خوشه بندی سلسله مراتبی :
- ابتدا تمام نقاط را به یک خوشه اختصاص میدهیم هر نقطه یک خوشه مجزا است
- ماتریس مجاورت را تشکیل میدهیم
- کوچکترین فاصله در ماتریکس مجاورت را پیدا میکنیم
- نقاط را با کمترین فاصله ادغام میکنیم (همان نقاطی که فاصل شان کوچکترین بود)
- ماتریس مجاورت را بروزرسانی میکنیم
- مجدد مرحله های 3 و 4 را تکرار میکنیم
- آن قدر این مراحل را تکرار میکنیم تا تنها یک خوشه باقی بماند
📌 بدست آوردن تعداد خوشه ها در روش سلسله مراتبی :
برای بدست آوردن تعداد خوشه ها از دندروگرام ها استفاده میکنیم
هرگاه دو خوشه را که شبیه هم هستند باهم ادغام میکنیم دندروگرام فاصله ی بین این دو خوشه را ثبت میکند اما این ثبت فاصله را به چه صورت انجام میدهم ؟
ما نقاط را در محور x و فاصله را در محور y داریم
هرگاه دو خوشه باهم ادغام شوند آنهارا در دندروگرام بهم پیوند میدهیم و ارتفاع اتصال فاصله ی بین خوشه ها خواهد بود پس از رسم دندروگرام خط آستانه را مشخص میکنیم
سعی کنید خط آسنانه ای که رسم میکنید بلندترین ارتفاع را قطع کنید
حال به تعداد خط های عمودی که آستانه ی افقی ما را قطع کرده است خوشه داریم
📌 Dendrogram چیست ؟
دندروگرام: گرافیک مناسب برای نمایش یک توالی سلسله مراتبی
از تکالیف خوشه بندی
این به سادگی یک درخت است که در آن:
هر گره نشان دهنده یک گروه است
هر گره برگ یک تک تن است (یعنی گروهی حاوی یک نقطه داده واحد)
Root node گروهی است که کل مجموعه داده را در بر می گیرد
هر گره داخلی دارای دو گره دختر (فرزندان) است.
نشان دهنده گروه هایی است که برای تشکیل آن ادغام شدند
Python Example
با تجسم برخی از نقاط داده شروع کنید:
import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import AgglomerativeClustering
x = [4, 5, 10, 4, 3, 11, 14 , 6, 10, 12]
y = [21, 19, 24, 17, 16, 25, 24, 22, 21, 21]
data = list(zip(x, y))
hierarchical_cluster = AgglomerativeClustering(n_clusters=2, affinity='euclidean', linkage='ward')
labels = hierarchical_cluster.fit_predict(data)
plt.scatter(x, y, c=labels)
plt.show()
داده ها را به مجموعه ای از نقاط تبدیل کنید . ارتباط بین تمام نقاط مختلف را محاسبه کنید. در اینجا ما از یک اندازه گیری فاصله اقلیدسی ساده و ارتباط وارد استفاده می کنیم که به دنبال به حداقل رساندن واریانس بین خوشه ها است. در نهایت، نتایج را در یک دندروگرام رسم کنید. این طرح سلسله مراتب خوشه ها را از پایین (نقاط فردی) به بالا (یک خوشه واحد شامل تمام نقاط داده) نشان می دهد.
import numpy as np
import matplotlib.pyplot as plt
from scipy.cluster.hierarchy import dendrogram, linkage
x = [4, 5, 10, 4, 3, 11, 14 , 6, 10, 12]
y = [21, 19, 24, 17, 16, 25, 24, 22, 21, 21]
data = list(zip(x, y))
linkage_data = linkage(data, method='ward', metric='euclidean')
dendrogram(linkage_data)
plt.show()
