1.اهداف یادگیری
در پایان این فصل، انتظار میرود خواننده بتواند:
- جایگاه الگوریتم AGNES را در خانواده روشهای خوشهبندی توضیح دهد.
- تفاوت خوشهبندی سلسلهمراتبی تجمیعی با روشهای افرازگرا مانند K-Means را تحلیل کند.
- منطق ادغام مرحلهبهمرحله خوشهها در AGNES را درک و تفسیر کند.
- معیارهای پیوند (Linkage Criteria) مختلف را از نظر ریاضی و رفتاری مقایسه کند.
- دندروگرام (Dendrogram) را بخواند و از آن برای استخراج خوشهها استفاده کند.
- پیچیدگی زمانی و حافظهای الگوریتم را تحلیل کند.
- AGNES را در Python پیادهسازی و خروجی آن را تفسیر کند.
- مزایا، محدودیتها و کاربردهای واقعی این الگوریتم را با نگاه انتقادی بررسی کند.
2. چکیده
الگوریتم AGNES که مخفف Agglomerative Nesting است، یکی از شناختهشدهترین روشهای خوشهبندی سلسلهمراتبی تجمیعی (Hierarchical Agglomerative Clustering) بهشمار میآید. این الگوریتم از پایین به بالا عمل میکند؛ بدین معنا که در آغاز، هر مشاهده بهعنوان یک خوشه مستقل در نظر گرفته میشود و سپس در هر گام، دو خوشهای که بر اساس یک معیار شباهت یا عدمشباهت به یکدیگر نزدیکتر هستند، با هم ادغام میشوند. حاصل این فرایند، ساختاری درختی به نام دندروگرام است که روابط سلسلهمراتبی میان دادهها را در سطوح مختلف نشان میدهد.
اهمیت AGNES در این است که برخلاف بسیاری از روشهای خوشهبندی افرازگرا، الزاماً نیازی به تعیین تعداد خوشهها در ابتدای کار ندارد و امکان مشاهده ساختار داده در چند سطح مختلف را فراهم میسازد. همین ویژگی آن را به ابزاری مناسب برای تحلیل اکتشافی داده، زیستاطلاعات، تحلیل اسناد، بازاریابی و بسیاری از مسائل علمی و صنعتی تبدیل کرده است. با این حال، هزینه محاسباتی و حافظهای بالا، حساسیت به معیار فاصله و پیوند، و برگشتناپذیربودن ادغامها از جمله محدودیتهای مهم آن محسوب میشوند. در این فصل، AGNES از منظر مفهومی، نظری، ریاضی، محاسباتی و کاربردی بهصورت نظاممند بررسی میشود.
.
3. مقدمه
خوشهبندی (Clustering) یکی از بنیادیترین مسائل در یادگیری بدون ناظر (Unsupervised Learning) است. در این مسئله، هدف آن است که مجموعهای از دادهها به گروههایی تقسیم شوند که درون هر گروه، اعضا تا حد امکان به یکدیگر شبیه و میان گروهها تا حد امکان متفاوت باشند. با وجود سادگی ظاهری این تعریف، خوشهبندی یکی از دشوارترین مسائل در تحلیل داده است؛ زیرا مفهوم «شباهت» در حوزههای مختلف متفاوت است و ساختار دادهها نیز میتواند بسیار پیچیده، چندمقیاسی و حتی مبهم باشد.
بسیاری از دانشجویان نخستین بار خوشهبندی را با الگوریتم K-Means میشناسند. K-Means الگوریتمی ساده، سریع و اثرگذار است، اما یک محدودیت مهم دارد: خروجی آن یک افراز تخت (Flat Partition) است. به بیان دیگر، K-Means تنها یک تقسیم نهایی از دادهها ارائه میدهد و اطلاعاتی درباره ساختار درونی و سلسلهمراتبی روابط میان نمونهها در اختیار ما نمیگذارد. در مقابل، در بسیاری از مسائل واقعی، دادهها ماهیتی سلسلهمراتبی دارند. برای مثال، در زیستشناسی، گونهها در جنسها، جنسها در خانوادهها و خانوادهها در راستهها قرار میگیرند. در تحلیل اسناد، متنها میتوانند از موضوعات فرعی به موضوعات کلیتر سازمان یابند. پس در بازارشناسی نیز مشتریان ممکن است ابتدا به گروههای رفتاری بزرگ و سپس به زیرگروههای ظریفتر تقسیم شوند.
در چنین شرایطی، خوشهبندی سلسلهمراتبی (Hierarchical Clustering) اهمیت پیدا میکند. این خانواده از روشها بهجای تولید یک پاسخ واحد، ساختاری چندسطحی از دادهها فراهم میکنند. الگوریتم AGNES یکی از مهمترین نمایندگان این خانواده است. این الگوریتم با رویکردی پایینبهبالا (Bottom-Up) کار میکند و در هر مرحله، نزدیکترین خوشهها را با هم ادغام میکند. نتیجه این فرایند، یک دندروگرام است که میتوان آن را در ارتفاعهای مختلف برش داد و خوشهبندیهایی با درجات مختلف از ریزدانگی به دست آورد.
.
4. تاریخچه و انگیزه توسعه الگوریتم
ریشههای خوشهبندی سلسلهمراتبی به دهههای میانی قرن بیستم بازمیگردد. در آمار، روانسنجی، زیستشناسی و طبقهبندی علمی، پژوهشگران به روشهایی نیاز داشتند که بتوانند ساختار شباهت میان اشیا یا نمونهها را بدون فرض تعداد ثابت خوشهها آشکار کنند. مقالات کلاسیکی مانند Johnson (1967) و Ward (1963) پایههای نظری و الگوریتمی مهمی برای روشهای سلسلهمراتبی ایجاد کردند. بعدها، روشهای کارآمدتری نیز برای linkageهای خاص توسعه یافتند؛ برای نمونه، Sibson (1973) الگوریتم SLINK را برای single linkage و Defays (1977) روشهایی کارآمد برای complete linkage ارائه کردند.
با این حال، معرفی AGNES بهعنوان یک الگوریتم آموزشی و نظاممند، بیش از هر چیز با کتاب اثرگذار Kaufman و Rousseeuw (1990) گره خورده است. این دو پژوهشگر در کتاب Finding Groups in Data مجموعهای از الگوریتمهای مهم تحلیل خوشهای را با نگاهی همزمان نظری، محاسباتی و کاربردی معرفی کردند. در این چارچوب، AGNES بهعنوان صورتبندی روشن و قابلفهمی از خوشهبندی سلسلهمراتبی تجمیعی مطرح شد.
انگیزه اصلی توسعه و ترویج AGNES را میتوان در چند نکته خلاصه کرد:
- نیاز به روشی که تعداد خوشهها را از ابتدا تحمیل نکند.
- نیاز به درک ساختار چندسطحی دادهها، نه صرفاً یک افراز نهایی.
- نیاز به روشی تفسیرپذیر که بتواند روابط میان نمونهها و خوشهها را بهصورت تصویری نشان دهد.
- امکان استفاده از معیارهای فاصله و پیوند مختلف برای انواع دادهها و کاربردها.
به این ترتیب، AGNES نه بهعنوان یک «اختراع ناگهانی»، بلکه بهعنوان نتیجه بلوغ یک سنت پژوهشی در خوشهبندی سلسلهمراتبی پدیدار شد. ارزش آن نیز دقیقاً در همین است که پلی میان نظریه کلاسیک خوشهبندی و کاربردهای عملی تحلیل داده برقرار میکند.
.
5. جایگاه الگوریتم در یادگیری ماشین
AGNES در دسته الگوریتمهای یادگیری بدون ناظر قرار میگیرد. در این دسته، برخلاف یادگیری نظارتشده (Supervised Learning)، برچسبهای از پیش تعیینشده برای دادهها وجود ندارد و الگوریتم باید ساختارهای پنهان در داده را کشف کند.
از منظر طبقهبندی روشها، میتوان جایگاه AGNES را چنین صورتبندی کرد:
- حوزه کلان: یادگیری ماشین
- زیرحوزه: یادگیری بدون ناظر
- مسئله: خوشهبندی
- خانواده روش: خوشهبندی سلسلهمراتبی
- نوع رویکرد: تجمیعی (Agglomerative)
- نوع خروجی: ساختار درختی سلسلهمراتبی و امکان استخراج افراز تخت
در مقایسه با روشهای افرازگرا مانند K-Means و K-Medoids، AGNES مستقیماً یک تقسیم نهایی از دادهها تحمیل نمیکند، بلکه تاریخچه ادغام خوشهها را نیز حفظ میکند.پس در مقایسه با روشهای مبتنی بر چگالی مانند DBSCAN، AGNES بیش از آنکه بر کشف نواحی پرتراکم تمرکز داشته باشد، بر سازماندهی سلسلهمراتبی روابط شباهت متمرکز است. در مقایسه با مدلهای احتمالاتی مانند Gaussian Mixture Model، AGNES نیازمند فرض صریحی درباره توزیع دادهها نیست.
از دیدگاه آموزشی، AGNES یکی از مناسبترین الگوریتمها برای آموزش این نکته است که «خوشهبندی» یک مفهوم واحد و مطلق نیست، بلکه به نحوه تعریف فاصله، قاعده ادغام و سطح تحلیل بستگی دارد. همین امر آن را به الگوریتمی مهم برای دورههای دادهکاوی، یادگیری ماشین و تحلیل داده تبدیل کرده است.
.
6. تعاریف و مفاهیم پایه
پیش از ورود به جزئیات AGNES، باید چند مفهوم بنیادین را بهدقت روشن کرد.
6.1 خوشهبندی
خوشهبندی فرایند گروهبندی دادهها بهگونهای است که اعضای یک گروه از نظر یک معیار شباهت، به یکدیگر نزدیکتر از اعضای گروههای دیگر باشند. این تعریف ساده است، اما در عمل به انتخاب متریک فاصله، مقیاس ویژگیها و ساختار داده وابسته است.
6.2 شباهت و عدمشباهت
در بسیاری از متون، شباهت (Similarity) و عدمشباهت (Dissimilarity) دو روی یک سکهاند. شباهت هرچه بیشتر باشد، فاصله کمتر است. AGNES معمولاً بر مبنای یک ماتریس عدمشباهت یا ماتریس فاصله عمل میکند. این فاصله میتواند اقلیدسی، منهتنی، کسینوسی، همینگ یا هر معیار مناسب دیگری باشد.
6.3 خوشهبندی سلسلهمراتبی
در خوشهبندی سلسلهمراتبی، خروجی صرفاً یک تقسیم نهایی نیست، بلکه مجموعهای از روابط تو در تو میان خوشههاست. این ساختار معمولاً با دندروگرام نمایش داده میشود. دندروگرام نشان میدهد که کدام خوشهها در چه سطحی با یکدیگر ادغام شدهاند.
6.4 رویکرد تجمیعی
در رویکرد تجمیعی، الگوریتم از تعداد زیادی خوشه کوچک آغاز میکند و آنها را بهتدریج ادغام میکند. این رویکرد در برابر روش تقسیمی (Divisive) قرار دارد که از یک خوشه بزرگ آغاز میکند و آن را مرحلهبهمرحله میشکند.
6.5 دندروگرام
دندروگرام یک نمایش درختی از فرایند ادغام خوشههاست. محور عمودی آن معمولاً فاصله یا هزینه ادغام را نشان میدهد. هرچه ارتفاع ادغام دو خوشه بیشتر باشد، یعنی آن دو خوشه کمتر به یکدیگر شبیه بودهاند. برش دندروگرام در ارتفاعهای مختلف، تعداد خوشههای متفاوتی تولید میکند.
6.6 معیار پیوند
وقتی دو خوشه شامل بیش از یک عضو باشند، دیگر فاصله میان آنها بهصورت یکتا تعریف نمیشود. اینجا معیار پیوند (Linkage Criterion) وارد میشود. معیار پیوند مشخص میکند فاصله دو خوشه چگونه از روی فاصله اعضای آنها محاسبه شود. رایجترین معیارها عبارتاند از:
- Single Linkage: کمترین فاصله بین دو عضو از دو خوشه
- Complete Linkage: بیشترین فاصله بین دو عضو
- Average Linkage: میانگین فاصله تمام زوجها
- Ward Linkage: ادغامی که افزایش واریانس درونخوشهای را کمینه کند
6.7 الگوریتم حریصانه
AGNES یک الگوریتم حریصانه (Greedy Algorithm) است. در هر مرحله، بهترین تصمیم محلی، یعنی ادغام نزدیکترین دو خوشه، اتخاذ میشود. این تصمیم برگشتناپذیر است. در نتیجه، کیفیت خروجی نهایی به تصمیمهای مراحل اولیه وابسته است.
.
7. مسئلهای که الگوریتم حل میکند
AGNES مسئلهای را حل میکند که میتوان آن را چنین بیان کرد:
«چگونه میتوان بدون داشتن برچسب، ساختار گروهبندی چندسطحی میان دادهها را بر اساس شباهت میان آنها کشف کرد؟»
این مسئله زمانی اهمیت مییابد که:
- تعداد خوشهها از قبل معلوم نیست.
- دادهها ممکن است در چند سطح مختلف گروهبندی شوند.
- پژوهشگر میخواهد نه فقط خوشه نهایی، بلکه روابط درونی میان خوشهها را نیز ببیند.
- ساختار سلسلهمراتبی برای تفسیر موضوع اهمیت دارد.
برای مثال، در تحلیل ژنها، ممکن است ابتدا مجموعهای از ژنها به دو خانواده بزرگ تقسیم شوند و سپس هر خانواده به زیرخانوادههایی کوچکتر تجزیه شود. AGNES دقیقاً برای آشکارکردن چنین ساختارهایی مفید است.
.
8. اهمیت و ضرورت
اهمیت AGNES را نباید صرفاً در این دید که «یک الگوریتم خوشهبندی دیگر» است. ضرورت این الگوریتم از چند منظر روشن میشود.
نخست، بسیاری از مسائل واقعی ماهیت سلسلهمراتبی دارند. اگر الگوریتمی فقط یک افراز تخت تولید کند، بخش مهمی از ساختار داده از دست میرود. AGNES این کمبود را جبران میکند.
دوم، در مراحل ابتدایی تحلیل داده، پژوهشگر اغلب نمیداند چند خوشه باید وجود داشته باشد. الگوریتمهایی که از ابتدا نیازمند تعیین تعداد خوشهاند، در این مرحله محدودکننده هستند. AGNES اجازه میدهد ابتدا ساختار کلی دیده شود و سپس درباره تعداد خوشه تصمیمگیری شود.
سوم، AGNES از منظر تفسیرپذیری اهمیت دارد. در بسیاری از کاربردهای علمی، صرف تولید یک پاسخ کافی نیست؛ پژوهشگر باید بداند چرا نمونهها کنار هم قرار گرفتهاند و خوشهها چگونه شکل گرفتهاند. دندروگرام چنین امکانی را فراهم میکند.
چهارم، AGNES از منظر آموزش مفاهیم بنیادی بسیار مهم است. این الگوریتم دانشجو را وادار میکند درباره متریک فاصله، نقش مقیاسبندی، مفهوم شباهت و اثر تصمیمهای الگوریتمی بهصورت عمیقتر فکر کند.
.
9. مبانی نظری
مبنای نظری AGNES بر این ایده استوار است که ساختار شباهت در داده را میتوان با یک فرایند ادغام تدریجی بازسازی کرد. اگر در ابتدا هر داده را یک خوشه مستقل فرض کنیم و در هر مرحله نزدیکترین دو خوشه را با هم ادغام کنیم، آنگاه رشتهای از ادغامها شکل میگیرد که تاریخچه همبستگی میان دادهها را در خود حفظ میکند.
از منظر نظری، AGNES بر سه مؤلفه استوار است:
- بازنمایی داده از طریق فاصله یا عدمشباهت:
دادهها باید بهگونهای نمایش داده شوند که بتوان میزان نزدیکی یا دوری میان آنها را سنجید.
- قاعده ادغام خوشهها:
باید مشخص شود که فاصله میان دو خوشه چگونه محاسبه میشود. این همان نقش linkage است.
- ساختار درختی حاصل از ادغامهای متوالی:
هر ادغام یک سطح جدید از تجمیع میسازد و مجموعه این سطوح، یک ساختار سلسلهمراتبی را پدید میآورد.
نکته نظری مهم آن است که AGNES لزوماً بهینهسازی یک تابع هدف واحد و جهانی را مانند K-Means دنبال نمیکند. در واقع، در بسیاری از صورتبندیهای آن، رفتار الگوریتم بیشتر به قواعد محلی ادغام وابسته است تا حل یک مسئله بهینهسازی صریح. این ویژگی هم یک مزیت است و هم یک محدودیت: مزیت از آن جهت که روش را انعطافپذیر و قابلتفسیر میکند؛ محدودیت از آن جهت که تضمین بهینهبودن سراسری ارائه نمیدهد.
.
10. مبانی ریاضی
فرض کنید مجموعه داده ما شامل n مشاهده باشد:
در آغاز الگوریتم، هر مشاهده یک خوشه مستقل است:
همچنین یک تابع عدمشباهت یا فاصله تعریف میکنیم:
که فاصله بین دو مشاهده xi و xj را اندازه میگیرد. در هر مرحله، لازم است فاصله بین دو خوشه A و B محاسبه شود. این فاصله بسته به linkage تغییر میکند.
در گام t، اگر مجموعه خوشهها را باCt نشان دهیم، الگوریتم زوج خوشههای A و B را طوری انتخاب میکند که:
سپس این دو خوشه با هم ادغام میشوند:
این فرایند تا زمانی ادامه مییابد که تنها یک خوشه باقی بماند یا شرط توقف دیگری اعمال شود.
.
11. فرمولها و تعریف تمام نمادها
در این بخش، مهمترین روابط ریاضی AGNES را بهصورت منظم ارائه میکنیم.
11.1 فاصله تکپیوندی (Single Linkage)
در این رابطه:
- A و B: دو خوشه
- x: عضوی از خوشه A
- y: عضوی از خوشه B
- d(x,y) : فاصله بین دو مشاهده
تفسیر: فاصله دو خوشه برابر کمترین فاصله بین هر عضو از خوشه اول و هر عضو از خوشه دوم است.
11.2 فاصله کاملپیوندی (Complete Linkage)
تفسیر: فاصله دو خوشه برابر بیشترین فاصله بین اعضای آنهاست. این معیار تمایل دارد خوشههای فشردهتری ایجاد کند.
11.3 فاصله میانگینپیوندی (Average Linkage)
در این رابطه:
- ∣A∣: تعداد اعضای خوشه A
- ∣B∣: تعداد اعضای خوشه B
تفسیر: فاصله دو خوشه برابر میانگین فاصله همه زوجهای ممکن میان اعضای آنهاست.
11.4 پیوند وارد (Ward Linkage)
در روش وارد، معیاری که کمینه میشود، افزایش پراکندگی درونخوشهای است. یک صورت رایج آن چنین است:
در این رابطه:
تفسیر: خوشههایی ادغام میشوند که کمترین افزایش را در مجموع مربعات درونخوشهای ایجاد کنند.
11.5 ماتریس فاصله
اگر n مشاهده داشته باشیم، ماتریس فاصله به شکل زیر است:
این ماتریس معمولاً متقارن است و قطر اصلی آن صفر است.
.
12. شهود ریاضی
برای فهم شهودی AGNES، تصور کنید دادهها روی صفحهای پراکندهاند و هر نقطه در آغاز کاملاً تنهاست. حال از خود میپرسیم: «کدام دو نقطه یا دو گروه از نقاط، بیش از همه شبیهاند؟» طبیعی است که نخست نزدیکترین دو نقطه با هم گروه شوند. پس از آن، دوباره همین سؤال را درباره خوشههای موجود میپرسیم. این روند تا جایی ادامه مییابد که تمام دادهها زیر یک ساختار کلی قرار گیرند.
اما نکته ظریف اینجاست که پاسخ به سؤال «فاصله دو خوشه چیست؟» ساده نیست. اگر دو خوشه هر کدام چند عضو داشته باشند، آیا باید نزدیکترین دو عضو را ملاک گرفت؟ یا دورترین دو عضو را؟ یا میانگین همه فاصلهها را؟ همین انتخاب است که رفتار الگوریتم را عوض میکند.
برای مثال، single linkage خوشههایی را که از طریق یک زنجیره از نقاط نزدیک به هم وصل شدهاند، بهسادگی ادغام میکند. به همین دلیل گاهی ساختارهای کشیده و زنجیرهای تولید میکند. complete linkage برعکس، خوشههای فشردهتر میسازد؛ زیرا دورترین اعضا را در نظر میگیرد. average linkage رفتاری میانه دارد و Ward linkage بیشتر به دنبال خوشههای کمپراکندگی است.
از این رو، AGNES را نباید یک الگوریتم با پاسخ یکتا تصور کرد. AGNES یک سازوکار کلی برای ساختن سلسلهمراتب خوشههاست و روح واقعی آن در ترکیب «فاصله + linkage + داده» نهفته است.
.
13. مراحل اجرای الگوریتم
الگوریتم AGNES را میتوان بهصورت گامبهگام چنین توصیف کرد:
- مجموعه داده را دریافت کنید.
- معیار فاصله بین نمونهها را انتخاب کنید.
- ماتریس فاصله بین تمام زوج دادهها را محاسبه کنید.
- در ابتدا، هر مشاهده را یک خوشه مستقل در نظر بگیرید.
- فاصله بین همه زوج خوشهها را بر اساس linkage انتخابی محاسبه کنید.
- نزدیکترین دو خوشه را پیدا کنید.
- این دو خوشه را با هم ادغام کنید.
- فاصله خوشه جدید با سایر خوشهها را بهروزرسانی کنید.
- مراحل 6 تا 8 را تکرار کنید تا تنها یک خوشه باقی بماند یا تعداد خوشه مطلوب حاصل شود.
- دندروگرام را رسم یا تحلیل کنید.
- با برش دندروگرام در ارتفاع مناسب، خوشهبندی نهایی را استخراج کنید.
.
14. شبهکد
Algorithm AGNES(X, distance, linkage)
Input:
X: dataset with n samples
distance: point-to-point distance function
linkage: cluster-to-cluster distance rule
Output:
A dendrogram or hierarchy of merges
1. Initialize each sample as a singleton cluster
2. Compute the pairwise distance matrix D
3. Let C be the current set of clusters
4. while |C| > 1 do
5. Find clusters A, B in C with minimum linkage distance
6. Merge A and B into a new cluster M = A ∪ B
7. Remove A and B from C
8. Add M to C
9. Update distances between M and all other clusters
10. end while
11. Return the hierarchy of merges
این شبهکد ساختار اصلی الگوریتم را نشان میدهد. در پیادهسازیهای عملی، تفاوت اصلی در نحوه ذخیره و بهروزرسانی فاصلهها و نیز در نوع linkage است.
15. تحلیل پیچیدگی زمانی و حافظه
15.1 پیچیدگی زمانی
در پیادهسازی ساده، در هر مرحله باید نزدیکترین دو خوشه از میان تمام زوجها پیدا شوند و سپس فاصلهها بهروزرسانی شوند. اگر n تعداد نمونهها باشد، پیچیدگی زمانی کلاسیک الگوریتم معمولاً در بدترین حالت در حدود زیر است:
در برخی پیادهسازیهای بهینهتر، بهویژه برای linkageهای خاص، میتوان این پیچیدگی را تا حدود
کاهش داد (Murtagh & Contreras, 2012). با این حال، درک آموزشی مهم آن است که AGNES در مقایسه با روشهایی مانند K-Means، از نظر زمانی معمولاً سنگینتر است.
15.2 پیچیدگی حافظه
چون اغلب لازم است ماتریس فاصله بین همه زوج نمونهها ذخیره شود، پیچیدگی حافظه معمولاً برابر است با:
این محدودیت برای مجموعهدادههای بزرگ بسیار مهم است. برای مثال، اگر 100,000n = باشد، ذخیره کامل ماتریس فاصله عملاً میتواند بسیار پرهزینه یا ناممکن شود.
.
16. ابرپارامترها و روش تنظیم آنها
برخلاف برخی الگوریتمها، AGNES ابرپارامترهای بسیار زیادی ندارد؛ اما همان چند انتخاب موجود تأثیر عمیقی بر نتیجه میگذارند.
16.1 معیار فاصله
رایجترین گزینهها:
- Euclidean
- Manhattan
- Cosine
- Hamming
راهنمای تنظیم:
اگر دادهها عددی و پیوسته باشند، فاصله اقلیدسی رایج است. برای دادههای با ابعاد بالا یا متون، فاصله کسینوسی گاه مناسبتر است. برای دادههای دودویی، همینگ انتخاب طبیعیتری است.
16.2 معیار پیوند
گزینههای متداول:
- Single
- Complete
- Average
- Ward
راهنمای تنظیم:
- اگر ساختارهای زنجیرهای مدنظر باشد، single linkage ممکن است مفید باشد.
- اگر خوشههای فشرده مدنظر باشد، complete یا Ward مناسبتر است.
- اگر تعادل مدنظر باشد، average linkage گزینه خوبی است.
- Ward معمولاً برای دادههای عددی با ساختار نسبتاً کروی رفتار مناسبی دارد.
16.3 تعداد خوشه نهایی
AGNES ذاتاً تعداد خوشه را از پیش نیاز ندارد، اما برای استخراج یک افراز نهایی باید دندروگرام برش داده شود.
روشهای تنظیم:
- تحلیل دیداری دندروگرام
- شاخص silhouette
- دانش حوزه
- بررسی فاصلههای ادغام و یافتن جهشهای بزرگ
16.4 پیشپردازش و مقیاسبندی
اگر ویژگیها مقیاسهای متفاوت داشته باشند، فاصلهها گمراهکننده میشوند. بنابراین، استانداردسازی (Standardization) یا نرمالسازی (Normalization) معمولاً ضروری است.
.
17. مثال شهودی
برای درک شهودی AGNES، یک کلاس درس را در نظر بگیرید که استاد میخواهد دانشجویان را بر اساس شباهت در سبک یادگیری گروهبندی کند. در ابتدا هیچ اطلاعی از تعداد گروهها وجود ندارد. بنابراین، استاد هر دانشجو را یک گروه مستقل فرض میکند.
سپس از خود میپرسد: «کدام دو دانشجو از نظر الگوی مطالعه، عملکرد در آزمونها و علاقهمندیهای آموزشی بیشترین شباهت را دارند؟» این دو دانشجو در یک گروه قرار میگیرند. در مرحله بعد، دوباره همه گروههای موجود بررسی میشوند؛ ممکن است یک دانشجوی تنها با یک گروه دو نفره ادغام شود، یا دو گروه کوچک با هم ترکیب شوند. این روند ادامه مییابد تا در نهایت همه دانشجویان در یک ساختار درختی قرار گیرند.
نکته مهم این است که استاد مجبور نیست از ابتدا بگوید «کلاس باید دقیقاً به سه گروه تقسیم شود». او ابتدا ساختار شباهتها را میبیند و سپس تصمیم میگیرد که در چه سطحی گروهها را از هم جدا کند. این همان منطق اصلی AGNES است.
در این مثال:
- هر دانشجو معادل یک مشاهده xi است.
- شباهت میان دانشجویان معادل فاصله یا عدمشباهت است.
- ادغام دانشجویان یا گروهها معادل عملیات تجمیع خوشههاست.
- نمودار نهایی شباهتها معادل دندروگرام است.
این مثال نشان میدهد چرا AGNES برای تحلیل اکتشافی مفید است. در بسیاری از مسائل، ما هنوز نمیدانیم ساختار اصلی داده چیست. AGNES به ما اجازه میدهد این ساختار را مرحلهبهمرحله مشاهده کنیم.
.
18. مثال عددی ساده
در این بخش، الگوریتم AGNES را روی یک مجموعه داده بسیار کوچک اجرا میکنیم تا منطق ادغامها کاملاً روشن شود.
فرض کنید چهار نقطه یکبعدی داریم:
X={1 , 2 , 6 , 8}
این چهار مشاهده را بهترتیب با A، B، C و D نشان میدهیم:
A=1 , B=2 , C=6 , D=8
از فاصله اقلیدسی در فضای یکبعدی استفاده میکنیم:
18.1 تشکیل ماتریس فاصله
ماتریس فاصله برابر است با:
تفسیر ماتریس:
- فاصله A و B برابر 1 است.
- فاصله C و D برابر 2 است.
- فاصله A و D برابر 7 است.
در آغاز، هر نقطه یک خوشه مستقل است:
{A} , {B} , {C} , {D}
18.2 گام اول ادغام
کمترین فاصله در ماتریس، فاصله بین A و B است:
d(A , B) = 1
پس خوشههای A و B ادغام میشوند:
{A,B} , {C} , {D}
18.3 گام دوم ادغام با Single Linkage
اکنون باید فاصله خوشه A , B } } را با C و D محاسبه کنیم. از single linkage استفاده میکنیم:
با جایگذاری مقادیر:
همچنین:
و فاصله C و D برابر است با:
d(C,D)=2
پس کمترین فاصله بین C و D است. آنها ادغام میشوند:
{A,B},{C,D}
18.4 گام سوم ادغام نهایی
اکنون فقط دو خوشه داریم. فاصله آنها با single linkage چنین است:
بنابراین دو خوشه نهایی در ارتفاع 4 با هم ادغام میشوند:
{A , B , C , D}
18.5 جدول مراحل ادغام
| گام | خوشههای ادغامشده | ارتفاع ادغام |
| 1 | A و B | 1 |
| 2 | C و D | 2 |
| 3 | {A,B} و {C,D} | 4 |
18.6 تفسیر آموزشی
اگر دندروگرام را در ارتفاعی بین 2 و 4 برش دهیم، دو خوشه به دست میآید:
{A,B} , {C,D}
یعنی نقاط 1 و 2 در یک گروه، و نقاط 6 و 8 در گروه دیگر قرار میگیرند. این نتیجه با شهود ما نیز سازگار است.
.
19. مثال عددی پیشرفته
اکنون یک مثال دوبعدی را بررسی میکنیم تا تفاوت میان معیارهای پیوند بهتر روشن شود.
فرض کنید دادههای زیر را داریم:
از فاصله اقلیدسی استفاده میکنیم:
19.1 محاسبه چند فاصله اولیه
- فاصله بینx1 وx2
- فاصله بین x3وx4
- فاصله بین x4 و x5
- فاصله بین x3 و x5
19.2 ادغامهای اولیه
در ابتدا هر نقطه یک خوشه است:
{x1},{x2},{x3},{x4},{x5}
دو فاصله کمینه برابر 1 هستند:
فرض میکنیم ابتداx1 وx2 ادغام شوند:
و سپسx3وx4 ادغام شوند:
اکنون خوشهها عبارتاند از:
19.3 مقایسه Single Linkage و Complete Linkage
اکنون فاصله C2 , C3
را با دو معیار محاسبه میکنیم.
Single Linkage
Complete Linkage
بنابراین، single linkage فاصله دو خوشه را کمتر میبیند؛ زیرا تنها نزدیکترین دو عضو را ملاک قرار میدهد. complete linkage محتاطتر است و دورترین فاصله را معیار قرار میدهد.
19.4 تفسیر
در دادههایی که نقاط بهصورت زنجیرهای قرار گرفتهاند، single linkage ممکن است خوشههایی کشیده ایجاد کند. این پدیده در منابع خوشهبندی با عنوان اثر زنجیرهای (Chaining Effect) شناخته میشود (Jain et al., 1999). در مقابل، complete linkage معمولاً خوشههایی فشردهتر ایجاد میکند، اما ممکن است نسبت به نقاط دورتر حساستر باشد.
این مثال نشان میدهد که در AGNES، انتخاب linkage یک تصمیم فنی ساده نیست؛ بلکه مستقیماً بر ماهیت خوشههای نهایی اثر میگذارد.
.
20. پیادهسازی کامل در Python
در این بخش، AGNES را با استفاده از کتابخانههای استاندارد Python پیادهسازی میکنیم. برای پیادهسازی عملی، از scikit-learn و scipy استفاده میشود. کتابخانه scikit-learn یکی از رایجترین ابزارهای یادگیری ماشین در Python است و پیادهسازی استانداردی از خوشهبندی تجمیعی ارائه میدهد (Pedregosa et al., 2011). کتابخانه SciPy نیز ابزارهای کاملی برای رسم دندروگرام و تحلیل خوشهبندی سلسلهمراتبی فراهم میکند (Virtanen et al., 2020).
20.1 نصب کتابخانهها
در صورت نیاز، کتابخانهها را میتوان با دستورهای زیر نصب کرد:content_copy
pip install numpy pandas matplotlib scipy scikit-learn
20.2 کد کامل
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.preprocessing import StandardScaler
from sklearn.cluster import AgglomerativeClustering
from sklearn.metrics import silhouette_score
from scipy.cluster.hierarchy import linkage, dendrogram
def create_sample_data():
"""
Create a small two-dimensional dataset for demonstrating
agglomerative hierarchical clustering.
Returns
-------
X : np.ndarray
A 2D NumPy array containing sample points.
labels : list
Names of observations for dendrogram visualization.
"""
X = np.array([
[1.0, 1.0],
[1.2, 1.1],
[0.8, 0.9],
[5.0, 5.0],
[5.2, 5.1],
[4.9, 4.8],
[9.0, 1.0],
[9.2, 1.2],
[8.8, 0.9]
])
labels = [f"x{i+1}" for i in range(len(X))]
return X, labels
def plot_original_data(X):
"""
Plot the original data points.
"""
plt.figure(figsize=(7, 5))
plt.scatter(X[:, 0], X[:, 1], s=80)
for i, point in enumerate(X):
plt.text(point[0] + 0.05, point[1] + 0.05, f"x{i+1}")
plt.title("Original Data Points")
plt.xlabel("Feature 1")
plt.ylabel("Feature 2")
plt.grid(True, alpha=0.3)
plt.show()
def plot_dendrogram(X_scaled, labels, method="ward"):
"""
Plot dendrogram using SciPy linkage.
Parameters
----------
X_scaled : np.ndarray
Standardized feature matrix.
labels : list
Labels of observations.
method : str
Linkage method. Common choices: 'ward', 'single', 'complete', 'average'.
"""
linkage_matrix = linkage(X_scaled, method=method)
plt.figure(figsize=(9, 5))
dendrogram(linkage_matrix, labels=labels)
plt.title(f"Dendrogram Using {method.capitalize()} Linkage")
plt.xlabel("Observations")
plt.ylabel("Linkage Distance")
plt.grid(True, alpha=0.3)
plt.show()
return linkage_matrix
def run_agnes_clustering(X_scaled, n_clusters=3, linkage_method="ward"):
"""
Run agglomerative clustering using scikit-learn.
Parameters
----------
X_scaled : np.ndarray
Standardized feature matrix.
n_clusters : int
Desired number of clusters.
linkage_method : str
Linkage criterion.
Returns
-------
cluster_labels : np.ndarray
Cluster labels assigned to each observation.
"""
model = AgglomerativeClustering(
n_clusters=n_clusters,
linkage=linkage_method
)
cluster_labels = model.fit_predict(X_scaled)
return cluster_labels
def plot_clustered_data(X, cluster_labels):
"""
Plot clustered data with assigned cluster labels.
"""
plt.figure(figsize=(7, 5))
scatter = plt.scatter(
X[:, 0],
X[:, 1],
c=cluster_labels,
cmap="viridis",
s=100
)
for i, point in enumerate(X):
plt.text(point[0] + 0.05, point[1] + 0.05, f"x{i+1}")
plt.title("AGNES Clustering Result")
plt.xlabel("Feature 1")
plt.ylabel("Feature 2")
plt.grid(True, alpha=0.3)
plt.colorbar(scatter, label="Cluster")
plt.show()
def main():
"""
Main execution function.
"""
X, labels = create_sample_data()
print("Original Dataset:")
df = pd.DataFrame(X, columns=["Feature_1", "Feature_2"], index=labels)
print(df)
plot_original_data(X)
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)
linkage_matrix = plot_dendrogram(
X_scaled,
labels,
method="ward"
)
cluster_labels = run_agnes_clustering(
X_scaled,
n_clusters=3,
linkage_method="ward"
)
df["Cluster"] = cluster_labels
print("\nClustered Dataset:")
print(df)
score = silhouette_score(X_scaled, cluster_labels)
print(f"\nSilhouette Score: {score:.3f}")
plot_clustered_data(X, cluster_labels)
if __name__ == "__main__":
main() 12. تحلیل خروجی برنامه
21.1 تحلیل کلی داده
مجموعه داده شامل 9 نقطه دوبعدی است. این نقاط بهصورت شهودی در سه ناحیه قرار دارند:
- نقاطx1, x2, x3در نزدیکی مختصات (1,1)
- نقاطx4, x5, x6در نزدیکی مختصات (5,5)
- نقاطx7, x8, x9 در نزدیکی مختصات (9,1)
بنابراین، انتظار داریم الگوریتم سه خوشه تولید کند.
21.2 نقش استانداردسازی
در کد، پیش از اجرای خوشهبندی، دادهها با StandardScaler استاندارد میشوند. استانداردسازی باعث میشود هر ویژگی میانگین صفر و واریانس یک داشته باشد. این مرحله در الگوریتمهای مبتنی بر فاصله بسیار مهم است؛ زیرا اگر یک ویژگی دامنه عددی بسیار بزرگتری از ویژگی دیگر داشته باشد، فاصلهها را تحت سلطه خود قرار میدهد.
21.3 تحلیل دندروگرام
دندروگرام نشان میدهد که نقاط نزدیک ابتدا با هم ادغام میشوند. برای مثال، در حالت معمول انتظار میرود:
- x1, x2, x3زودتر با هم ادغام شوند.
- x4, x5, x6یک خوشه محلی تشکیل دهند.
- x7, x8, x9 نیز خوشهای جداگانه تشکیل دهند.
ارتفاع ادغامها نشاندهنده فاصله یا هزینه ادغام است. اگر در دندروگرام یک جهش بزرگ در ارتفاع مشاهده شود، میتواند نشانهای از تعداد مناسب خوشهها باشد.
21.4 تحلیل برچسبهای خوشه
خروجی AgglomerativeClustering برای هر مشاهده یک برچسب خوشه تولید میکند. برای مثال ممکن است خروجی چنین باشد:
x1 -> Cluster 2
x2 -> Cluster 2
x3 -> Cluster 2
x4 -> Cluster 0
x5 -> Cluster 0
x6 -> Cluster 0
x7 -> Cluster 1
x8 -> Cluster 1
x9 -> Cluster 1
شماره خوشهها معنای ترتیبی ندارند. یعنی خوشه 0 لزوماً «اولین» یا «بهترین» خوشه نیست. شمارهها فقط شناسه گروهها هستند.
21.5 تحلیل شاخص سیلوئت
در کد، از شاخص سیلوئت (Silhouette Score) برای ارزیابی کیفیت خوشهبندی استفاده شده است. این شاخص برای هر نمونه بررسی میکند که نمونه تا چه اندازه به خوشه خود نزدیک و از خوشههای دیگر دور است (Rousseeuw, 1987).
مقدار سیلوئت معمولاً در بازه زیر قرار دارد:
−1≤s(i)≤1
اگر مقدار نزدیک به 1 باشد، نمونه بهخوبی در خوشه خود قرار گرفته است. پس اگر مقدار نزدیک به 0 باشد، نمونه در مرز میان خوشههاست. اگر مقدار منفی باشد، احتمالاً نمونه به خوشه نادرستی تخصیص یافته است.
21.6 تحلیل خطبهخط کد
کد با واردکردن کتابخانههای اصلی آغاز میشود. numpy برای محاسبات عددی، pandas برای نمایش جدولی دادهها، و matplotlib برای رسم نمودارها استفاده شده است.
- تابع create_sample_data دادههای نمونه را تولید میکند. استفاده از تابع مستقل برای تولید داده باعث میشود کد خواناتر و قابل توسعهتر باشد.
- تابع plot_original_data دادهها را پیش از خوشهبندی نمایش میدهد. این مرحله از نظر آموزشی مهم است؛ زیرا به خواننده اجازه میدهد خروجی الگوریتم را با ساختار بصری داده مقایسه کند.
- تابع plot_dendrogram از تابع linkage در SciPy استفاده میکند. این تابع ماتریس ادغامها را تولید میکند و سپس با dendrogram ساختار سلسلهمراتبی رسم میشود.
- تابع run_agnes_clustering مدل خوشهبندی تجمیعی را اجرا میکند. در اینجا تعداد خوشهها برابر 3 در نظر گرفته شده است.
- تابع plot_clustered_data خروجی نهایی را بهصورت رنگی نمایش میدهد تا خوشههای تشخیصدادهشده قابل مشاهده باشند.
- در تابع main، کل فرایند از تولید داده تا استانداردسازی، رسم دندروگرام، اجرای خوشهبندی و ارزیابی خروجی انجام میشود.
21.7 تحلیل زمانی و حافظه برنامه
برای n نمونه و p ویژگی:
- استانداردسازی دادهها حدوداً پیچیدگی زمانی (O(np) دارد.
- محاسبه فاصلهها و اجرای خوشهبندی سلسلهمراتبی در حالت عمومی میتواند تا O(n2)یا بیشتر نیاز داشته باشد.
- ذخیره فاصلهها معمولاً به حافظه O(n2) نیاز دارد.
در این مثال کوچک، هزینه محاسباتی ناچیز است. اما برای دادههای بزرگ، همین ساختار میتواند محدودکننده باشد.
.
22. کاربردهای واقعی
AGNES به دلیل تفسیرپذیری و توانایی نمایش ساختار سلسلهمراتبی، در حوزههای متعددی کاربرد دارد.
22.1 زیستاطلاعات و تحلیل ژن
در زیستاطلاعات، پژوهشگران اغلب میخواهند ژنهایی را که الگوهای بیان مشابه دارند، گروهبندی کنند. خوشهبندی سلسلهمراتبی برای این کار بسیار رایج است؛ زیرا میتواند روابط چندسطحی میان ژنها یا نمونههای زیستی را نشان دهد. دندروگرام در این حوزه نهتنها یک ابزار محاسباتی، بلکه یک ابزار تفسیری مهم است.
22.2 تحلیل مشتریان
در بازاریابی و مدیریت ارتباط با مشتری، AGNES میتواند برای گروهبندی مشتریان بر اساس رفتار خرید، ارزش طول عمر مشتری، میزان وفاداری یا الگوی تعامل استفاده شود. مزیت آن این است که مدیران میتوانند گروهبندی را در سطوح مختلف ببینند؛ مثلاً ابتدا مشتریان را به چند گروه بزرگ و سپس هر گروه را به زیرگروههای دقیقتر تقسیم کنند.
22.3 تحلیل اسناد و متن
در متنکاوی، میتوان اسناد را بر اساس شباهت محتوایی خوشهبندی کرد. اگر اسناد با بردارهای TF-IDF یا embeddingهای متنی نمایش داده شوند، خوشهبندی سلسلهمراتبی میتواند ساختار موضوعی مجموعه اسناد را آشکار کند. در این حالت، فاصله کسینوسی معمولاً گزینهای مناسبتر از فاصله اقلیدسی است.
22.4 تحلیل تصویر
در پردازش تصویر، خوشهبندی سلسلهمراتبی میتواند برای گروهبندی نواحی مشابه، بخشبندی تصویر، یا تحلیل ویژگیهای استخراجشده از تصاویر استفاده شود. البته در تصاویر بزرگ، به دلیل هزینه محاسباتی بالا، معمولاً از نسخههای تقریبی یا روشهای ترکیبی استفاده میشود.
22.5 پزشکی و سلامت
در پزشکی، AGNES میتواند برای کشف زیرگروههای بیماران بر اساس شاخصهای آزمایشگاهی، علائم بالینی یا دادههای ژنتیکی استفاده شود. اهمیت این کاربرد در آن است که زیرگروههای کشفشده میتوانند به فرضیهسازی پژوهشی یا طراحی مسیرهای درمانی دقیقتر کمک کنند. البته تفسیر پزشکی چنین خوشههایی باید با احتیاط و همراه با اعتبارسنجی تخصصی انجام شود.
22.6 تحلیل شبکههای اجتماعی
در تحلیل شبکههای اجتماعی، میتوان افراد، حسابها یا گروهها را بر اساس ویژگیهای رفتاری یا ساختاری خوشهبندی کرد. اگرچه AGNES مستقیماً برای دادههای گرافی طراحی نشده است، اما پس از استخراج ویژگیها یا محاسبه فاصله میان گرهها میتوان از آن برای تحلیل سلسلهمراتبی استفاده کرد.
.
23. مطالعات موردی
23.1 مطالعه موردی آموزشی: خوشهبندی مشتریان فروشگاه آنلاین
فرض کنید یک فروشگاه آنلاین دادههای زیر را از مشتریان خود ثبت کرده است:
- تعداد خرید ماهانه
- میانگین مبلغ خرید
- تعداد بازدید از سایت
- نرخ بازگشت کالا
- میزان استفاده از تخفیف
هدف این است که مشتریان به گروههایی معنادار تقسیم شوند. در ابتدا مشخص نیست چند نوع مشتری وجود دارد. استفاده از K-Means مستلزم تعیین تعداد خوشههاست، اما AGNES میتواند ابتدا ساختار سلسلهمراتبی را نشان دهد.
فرایند پیشنهادی:
- پاکسازی دادهها
- استانداردسازی ویژگیها
- محاسبه فاصله اقلیدسی یا فاصله مناسب دیگر
- اجرای AGNES با average یا Ward linkage
- رسم دندروگرام
- انتخاب سطح برش بر اساس جهشهای بزرگ در ارتفاع دندروگرام
- تحلیل ویژگیهای هر خوشه
خروجی ممکن است گروههایی مانند موارد زیر را آشکار کند:
- مشتریان وفادار با خرید بالا
- مشتریان حساس به تخفیف
- مشتریان کمتعامل
- مشتریان پرریسک از نظر بازگشت کالا
در این مطالعه، ارزش AGNES در این است که مدیر بازاریابی فقط یک برچسب نهایی دریافت نمیکند؛ بلکه میتواند سلسلهمراتب شباهت میان گروههای مشتریان را نیز مشاهده کند.
23.2 مطالعه موردی پژوهشی: تحلیل دادههای ژنبیان
در دادههای ژنبیان، هر ژن با برداری از مقادیر بیان در شرایط یا نمونههای مختلف نمایش داده میشود. هدف میتواند یافتن ژنهایی باشد که الگوی بیان مشابه دارند.
در چنین کاربردی:
- هر ژن یک نمونه است.
- هر وضعیت آزمایشگاهی یک ویژگی است.
- فاصله میتواند بر پایه همبستگی یا فاصله اقلیدسی تعریف شود.
- دندروگرام میتواند خانوادههایی از ژنهای همرفتار را نشان دهد.
این نوع تحلیل در بسیاری از مطالعات زیستی بهعنوان بخشی از تحلیل اکتشافی استفاده میشود. با این حال، نتیجه خوشهبندی باید با دانش زیستی، آزمونهای آماری و اعتبارسنجی تجربی همراه شود.
23.3 مطالعه موردی صنعتی: نگهداری و تعمیرات پیشبینانه
در صنعت، ماشینآلات با حسگرهای متعدد پایش میشوند. هر ماشین میتواند بر اساس ویژگیهایی مانند دما، ارتعاش، فشار، مصرف انرژی و نرخ خطا توصیف شود. AGNES میتواند ماشینها را بر اساس الگوهای رفتاری مشابه گروهبندی کند.
کاربردهای ممکن:
- شناسایی ماشینهایی با رفتار غیرعادی
- گروهبندی تجهیزات مشابه برای برنامهریزی تعمیرات
- کشف الگوهای پنهان خرابی
- مقایسه عملکرد خطوط تولید
در چنین کاربردهایی، AGNES میتواند برای تحلیل اولیه مفید باشد، اما برای دادههای بسیار بزرگ یا جریانپیوسته، باید با روشهای مقیاسپذیرتر ترکیب شود.
