مقدمه‌ای بر خوشه‌بندی سلسله‌مراتبی در پایتون

انگیزه

تصور کن یک دانشمند داده هستی که برای یک شرکت خرده‌فروشی کار می‌کنی. رئیست ازت می‌خواد مشتری‌ها رو بر اساس رفتار خریدشون به گروه‌های زیر تقسیم کنی: مشتری‌های کم‌مصرف، متوسط، معمولی یا پلاتینیوم، تا بتونید بازاریابی هدفمند و پیشنهاد محصول بهتری داشته باشید.

با توجه به اینکه هیچ برچسب تاریخی برای این مشتری‌ها وجود نداره، چطور ممکنه اون‌ها رو دسته‌بندی کنیم؟ 

اینجاست که خوشه‌بندی می‌تونه کمک کنه. خوشه‌بندی یک تکنیک یادگیری ماشین بدون نظارت (Unsupervised Machine Learning) هست که برای گروه‌بندی داده‌های بدون برچسب در دسته‌های مشابه استفاده می‌شه. 

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

در نهایت، پیاده‌سازی مرحله به مرحله در پایتون با استفاده از کتابخونه محبوب Scipy رو بهت یاد می‌دیم.

تعریف خوشه‌بندی سلسله‌مراتبی

روش خوشه‌بندی سلسله‌مراتبی بر اساس تعیین خوشه‌های متوالی با استفاده از خوشه‌های قبلی کار می‌کنه. این تکنیک بیشتر برای گروه‌بندی داده‌ها در یک درخت از خوشه‌ها به نام دندروگرام (dendrogram) طراحی شده که رابطه سلسله‌مراتبی بین خوشه‌ها رو به‌صورت گرافیکی نشون می‌ده.

مقایسه خوشه‌بندی سلسله‌مراتبی با سایر تکنیک‌های خوشه‌بندی

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

بیا بررسی کنیم که چطور می‌شه این روش رو با انواع دیگه خوشه‌بندی مثل K-means و خوشه‌بندی مبتنی بر مدل مقایسه کرد. تکنیک‌های خیلی بیشتری وجود دارن، اما این دو مورد، در کنار خوشه‌بندی سلسله‌مراتبی، به‌طور گسترده استفاده می‌شن و چارچوبی فراهم می‌کنن تا بقیه روش‌ها رو بهتر درک کنی. 

می‌تونی در مقاله اختصاصی ما که پنج الگوریتم ضروری خوشه‌بندی رو پوشش می‌ده، درباره خوشه‌بندی در یادگیری ماشین در فینکا بیشتر یاد بگیری. 

خوشه‌بندی سلسله‌مراتبی در برابر خوشه‌بندی K-Means

برخلاف خوشه‌بندی سلسله‌مراتبی، خوشه‌بندی K-means به دنبال تقسیم داده‌های اولیه به K گروه یا خوشه‌ست که در اون کاربر مقدار K رو از قبل مشخص می‌کنه. 

ایده کلی اینه که دنبال خوشه‌هایی بگردیم که مجموع مجذور فاصله اقلیدسی همه نقاط از مرکز روی تمام ویژگی‌ها کمینه بشه و این نقاط رو به‌صورت تکرارشونده ادغام کنه.

آموزش خوشه‌بندی K-means در پایتون با Scikit-learn فینکا بهت کمک می‌کنه تا با یک مطالعه موردی جالب، نحوه کارکرد داخلی این الگوریتم رو درک کنی.

مزایا 

• از نظر محاسباتی نسبت به خوشه‌بندی سلسله‌مراتبی کارآمدتره و می‌تونه برای تحلیل مجموعه داده‌های بزرگ استفاده بشه.
• درک و پیاده‌سازی K-means آسون‌تره.

معایب

• انعطاف‌پذیری کمتری نسبت به خوشه‌بندی سلسله‌مراتبی داره، چون کاربر رو مجبور می‌کنه تعداد خوشه‌ها رو از قبل مشخص کنه که ممکنه در بعضی شرایط واضح نباشه.  
• نتیجه پایدار نیست و برای یک مجموعه داده مشخص، از یک تکرار به تکرار دیگه تغییر می‌کنه.
• نسبت به داده‌های پرت (outliers) حساس‌تره، چون استفاده از داده‌های پرت در مجموعه روی میانگین خوشه تأثیر می‌ذاره. 
• هم الگوریتم k-means و هم خوشه‌بندی سلسله‌مراتبی قادر به مدیریت مستقیم داده‌های دسته‌ای نیستن و ممکنه با داده‌هایی که پیوسته نیستن یا واریانس خیلی بالایی دارن، خوب کار نکنن.

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

خوشه‌بندی مبتنی بر مدل

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

• تصمیم‌گیری درباره مدل آماری مورد استفاده و انتخاب تعداد خوشه‌ها 
• برازش مدل روی داده‌ها
• شناسایی خوشه‌ها بر اساس پارامترهای مدل

مزایا 

• خوشه‌بندی مبتنی بر مدل از خوشه‌بندی سلسله‌مراتبی انعطاف‌پذیرتره چون اجازه می‌ده از مدل‌های مختلفی برای شناسایی انواع مختلف خوشه‌ها استفاده کنیم. 
• روی داده‌هایی با اشکال یا ساختارهای پیچیده بهتر کار می‌کنه.

معایب

• از نظر محاسباتی نسبت به خوشه‌بندی سلسله‌مراتبی گرون‌تره، مخصوصا برای داده‌های بزرگ.
• نیاز به درک بهتری از تکنیک‌های مدل‌سازی آماری داره چون انتخاب مدل می‌تونه روی نتیجه نهایی تأثیر بذاره.
• همون‌طور که در K-means دیدیم، اینجا هم لازمه که تعداد خوشه‌ها از قبل مشخص بشه.

کاربردهای خوشه‌بندی سلسله‌مراتبی

خوشه‌بندی سلسله‌مراتبی کاربردهای متنوعی در زندگی روزمره ما داره، از جمله (اما نه محدود به) زیست‌شناسی، پردازش تصویر، بازاریابی، اقتصاد و تحلیل شبکه‌های اجتماعی.

زیست‌شناسی

خوشه‌بندی توالی‌های DNA یکی از بزرگ‌ترین چالش‌ها در بیوانفورماتیکه.

زیست‌شناسان می‌تونن از خوشه‌بندی سلسله‌مراتبی برای مطالعه روابط ژنتیکی بین ارگانیسم‌ها استفاده کنن تا اون‌ها رو در گروه‌های طبقه‌بندی قرار بدن. این کار برای تحلیل سریع و مصورسازی روابط پنهان مفیده.

پردازش تصویر

خوشه‌بندی سلسله‌مراتبی می‌تونه در پردازش تصویر برای گروه‌بندی نواحی یا پیکسل‌های مشابه تصویر از نظر رنگ، شدت یا سایر ویژگی‌ها انجام بشه. این کار می‌تونه برای وظایف بعدی مثل بخش‌بندی تصویر، طبقه‌بندی تصویر و تشخیص شیء مفید باشه.

بازاریابی

متخصصان بازاریابی می‌تونن از خوشه‌بندی سلسله‌مراتبی برای رسم یک سلسله‌مراتب بین انواع مختلف مشتریان بر اساس عادات خریدشون استفاده کنن تا استراتژی‌های بازاریابی و پیشنهاد محصولات بهتری داشته باشن. مثلا می‌شه محصولات مختلفی رو در خرده‌فروشی‌ها بر اساس اینکه مشتری‌ها چقدر خرج می‌کنن (کم، متوسط یا زیاد) بهشون پیشنهاد داد.

تحلیل شبکه‌های اجتماعی

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

الگوریتم خوشه‌بندی سلسله‌مراتبی

در این بخش، سه مفهوم اصلی رو بررسی می‌کنیم. مراحل الگوریتم سلسله‌مراتبی، بررسی دو نوع خوشه‌بندی سلسله‌مراتبی (تجمعی و تقسیمی) و در نهایت، چند تکنیک برای انتخاب معیار فاصله مناسب.

مراحل انجام الگوریتم خوشه‌بندی سلسله‌مراتبی

الگوریتم خوشه‌بندی سلسله‌مراتبی از معیارهای فاصله برای تولید خوشه‌ها استفاده می‌کنه. این فرآیند تولید شامل مراحل اصلی زیر می‌شه: 

داده‌ها رو با حذف داده‌های از دست رفته و انجام کارهای اضافی پیش‌پردازش کن تا داده‌ها تا حد امکان تمیز بشن. این مرحله برای بیشتر کارهای یادگیری ماشین عمومیت داره. 

1. ماتریس فاصله شامل فاصله بین هر جفت نقطه داده رو با استفاده از یک معیار فاصله خاص مثل فاصله اقلیدسی، فاصله منهتن یا شباهت کسینوسی محاسبه کن. البته معیار فاصله پیش‌فرض، فاصله اقلیدسیه.
2. دو خوشه‌ای که نزدیک‌ترین فاصله رو دارن با هم ادغام کن. 
3. ماتریس فاصله رو با توجه به خوشه‌های جدید به‌روزرسانی کن.  
4. مراحل 1، 2 و 3 رو تکرار کن تا تمام خوشه‌ها با هم ادغام بشن و یک خوشه واحد ساخته بشه. 

مثال‌های خوشه‌بندی سلسله‌مراتبی 

ما می‌تونیم خوشه‌بندی تجمعی و تقسیمی رو مثل یک آینه برای هم در نظر بگیریم. بیا با دقت بیشتری ببینیم هر کدوم چطور کار می‌کنن و یک مثال از خوشه‌بندی سلسله‌مراتبی رو با مصورسازی گرافیکی بررسی کنیم.

خوشه‌بندی سلسله‌مراتبی تجمعی

سناریوی اول مربوط به روشیه که بالاتر توضیح داده شد. این روش با در نظر گرفتن هر نمونه به‌عنوان یک خوشه تک‌عضوی (خوشه‌ای با تنها یک نقطه داده) شروع می‌شه. بعد به‌صورت تکرارشونده خوشه‌ها رو ادغام می‌کنه تا زمانی که فقط یک خوشه باقی بمونه. این فرآیند به‌عنوان رویکرد پایین‌به‌بالا (bottom-up) هم شناخته می‌شه. 

همون‌طور که در تصویر زیر نشون داده شده: 

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

انتخاب معیار فاصله مناسب

انتخاب معیار فاصله یک قدم مهم در خوشه‌بندی محسوب می‌شه و به مسئله‌ای که می‌خوای حل کنی بستگی داره. با در نظر گرفتن سناریوی زیر، ما می‌تونیم دانش‌آموزان رو بر اساس روش‌های مختلفی خوشه‌بندی کنیم، مثل: 

• کشور محل تولد
• جنسیت
• سوابق تحصیلی قبلی

این‌ها همگی خوشه‌های معتبری هستن اما در معنی تفاوت دارن.

با اینکه فاصله اقلیدسی رایج‌ترین فاصله مورد استفاده در بیشتر نرم‌افزارهای خوشه‌بندیه، اما معیارهای فاصله دیگه‌ای هم مثل فاصله منهتن، فاصله کانبرا، همبستگی پیرسون یا اسپیرمن، و فاصله مینکوفسکی وجود دارن.

چگونه خوشه‌ها رو قبل از ادغام اندازه‌گیری کنیم؟

فاصله‌هایی که قبلا گفته شد مربوط به آیتم‌ها هستن. در این بخش، سه روش استاندارد (و نه همه روش‌ها) رو برای اندازه‌گیری نزدیک‌ترین جفت از خوشه‌ها قبل از ادغامشون بررسی می‌کنیم:

1. پیوند تکی (Single linkage)
2. پیوند کامل (Complete linkage)
3. پیوند میانگین (Average linkage)

پیوند تکی

از بین تمام فواصل جفتی بین آیتم‌های درون دو خوشه C1 و C2، پیوند تکی کمترین فاصله بین خوشه‌ها رو در نظر می‌گیره. 

فاصله (C1, C2) = {جایی که آیتم i درون C1 هست و آیتم j درون C2 هست | d(i, j)} Min

از بین تمام جفت آیتم‌های این دو خوشه، مواردی که با رنگ سبز برجسته شدن، کمترین فاصله رو دارن.

پیوند کامل

از بین تمام فواصل جفتی بین آیتم‌های درون دو خوشه C1 و C2، پیوند کامل فاصله بین خوشه‌ها رو به‌عنوان بیشترین فاصله در نظر می‌گیره. 

فاصله (C1, C2) = {جایی که آیتم i درون C1 هست و آیتم j درون C2 هست | d(i, j) } Max

از بین تمام جفت آیتم‌های این دو خوشه، مواردی که با رنگ سبز برجسته شدن، بیشترین فاصله رو دارن.

پیوند میانگین

در خوشه‌بندی با پیوند میانگین، فاصله بین دو خوشه مشخص C1 و C2 با میانگین فواصل بین تمام جفت‌های آیتم‌ها در این دو خوشه برابره.

فاصله (C1, C2) = تعداد کل فواصل / Sum{ d(i, j) }

سپس خوشه‌بندی با پیوند میانگین به این صورت انجام می‌شه:

d(a,j) + d(a,h) + d(a,n) + d(d,j) + d(d,h) + d(d,n)  

که در اون تعداد کل فواصل = ۶

پیاده‌سازی خوشه‌بندی سلسله‌مراتبی در پایتون

حالا درک درستی از نحوه کار خوشه‌بندی سلسله‌مراتبی پیدا کردی. در این بخش، ما روی پیاده‌سازی فنی با استفاده از پایتون تمرکز می‌کنیم.

اگر بیشتر دوست داری این پیاده‌سازی رو با زبان برنامه‌نویسی R انجام بدی، آموزش خوشه‌بندی سلسله‌مراتبی در R فینکا نقطه شروع خوبی برای توست.

راه‌اندازی محیط کار 

برای شروع، باید پایتون رو روی سیستم نصب کرده باشی، در کنار کتابخونه‌های زیر:

• کتابخونه Pandas برای بارگذاری دیتافریم
• کتابخونه Scikit-learn برای انجام نرمال‌سازی داده‌ها
• کتابخونه‌های Seaborn و matplotlib برای مصورسازی
• کتابخونه Scipy برای اعمال الگوریتم خوشه‌بندی

می‌تونی این کتابخونه‌ها رو با استفاده از مدیر بسته پایتون یعنی pip به این شکل نصب کنی:

خب حالا بریم سراغ این‌که ماژول‌های لازم رو وارد کنیم و دیتاست رو لود کنیم.

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

درک داده‌ها

این مجموعه داده دارای ۹,۵۰۰ وام با اطلاعاتی درباره ساختار وام، وام‌گیرنده و اینکه آیا وام به‌طور کامل بازپرداخت شده یا نه. ما قراره ستون هدف not.fully.paid رو حذف کنیم تا شرط بدون نظارت بودن رو رعایت کرده باشیم.

دستور زیر نشون می‌ده که داده‌ها دارای ۹,۵۷۸ سطر و ۱۴ ستون از نوع عددی هستن؛ به‌جز ستون purpose که از نوع object هست و توضیحات متنی درباره هدف وام می‌ده.

پیش‌پردازش داده‌ها 

قبل از اجرای الگوریتم خوشه‌بندی، داده‌ها باید پیش‌پردازش بشن تا اطلاعات گم‌شده مدیریت، مقادیر ستون‌ها نرمال‌سازی و ستون‌های نامربوط حذف بشن.

برخورد با مقادیر گم‌شده

از خروجی زیر، متوجه می‌شیم که هیچ مقدار از دست رفته‌ای در داده‌ها وجود نداره.

حذف ستون‌های اضافی

قراره داده‌های وام رو با استفاده از تمام ستون‌ها تجزیه و تحلیل کنیم، به‌جز این موارد: 

• هدف وام
• ستون Not.fully.paid، چون این در واقع برچسبیه که می‌گه وام‌گیرنده پرداخت کامل داشته یا نه.

متغیر cleaned_data معادل داده‌ها بدون در نظر گرفتن ستون‌های بالاست.

تصویر زیر اطلاعات مربوط به داده‌های جدید رو نشون می‌ده.

تحلیل داده‌های پرت

یکی از نقاط ضعف خوشه‌بندی سلسله‌مراتبی حساس بودن اون به داده‌های پرته. توزیع هر متغیر توسط نمودار جعبه‌ای نشون داده می‌شه.

موجودی حساب در گردش وام‌گیرنده (revol_bal) تنها ویژگی‌ایه که نقاط داده اون از بقیه خیلی دورتره. 

با استفاده از روش دامنه بین‌چارکی، می‌تونیم تمام نقاطی که بیرون از بازه تعریف‌شده با چارک‌های 1.5± * IQR قرار دارن رو حذف کنیم که در اون IQR به معنای دامنه بین چارکیه. 

این کار با کمک تابع کمکی زیر انجام می‌شه. 

حالا می‌تونیم این تابع رو روی مجموعه داده اعمال کنیم.

حالا می‌تونیم نمودار جعبه‌ای جدید رو بررسی کنیم و اون رو با نمودار قبل از حذف داده‌های پرت مقایسه کنیم.

اکنون ابعاد داده‌ها شامل ۹,۳۱۹ سطر و ۱۲ ستونه. یعنی ۲۵۹ مورد مشاهده‌شده داده‌های پرت بودن که حذف شدن. 

تغییر مقیاس داده‌ها

از اونجایی که خوشه‌بندی سلسله‌مراتبی از فاصله اقلیدسی استفاده می‌کنه و این فاصله نسبت به کار با متغیرهایی با مقیاس‌های مختلف خیلی حساسه، کار هوشمندانه‌ایه که مقیاس تمام متغیرها رو قبل از محاسبه فاصله یکسان کنیم. 

این کار با استفاده از کلاس StandardScaler از کتابخونه sklearn انجام می‌شه.

شکل داده‌ها یکسان باقی می‌مونه (۹,۳۱۹ سطر، ۱۲ ستون) چون نرمال‌سازی تأثیری روی اندازه داده‌ها نداره. 

اعمال الگوریتم خوشه‌بندی سلسله‌مراتبی 

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

در این مرحله، می‌تونیم تصمیم بگیریم که کدوم روش پیوند رو برای خوشه‌بندی در ویژگی method از متد linkage() اعمال کنیم. تو این بخش، هر سه تکنیک پیوند رو با استفاده از فاصله اقلیدسی بررسی می‌کنیم. 

این کار بعد از وارد کردن کتابخونه‌های مربوطه، با کمک کدهای زیر انجام می‌شه.

زمانی که هر سه خوشه‌بندی رو محاسبه کردیم، دندروگرام‌های مربوطه به شکل زیر نشون داده می‌شن و با خوشه‌بندی کامل شروع می‌کنیم.

تفسیر نتایج (مصورسازی دندروگرام، تعیین تعداد خوشه‌ها)

برای هر رویکرد پیوند، دندروگرام ساخته می‌شه و در نهایت هر نقطه داده داخل یک خوشه قرار می‌گیره. 

• محور X در دندروگرام نشون‌دهنده نمونه‌های موجود در داده‌هاست.
• محور Y نشان‌دهنده فاصله بین این نمونه‌هاست. هرچه خط بالاتر باشه، تفاوت بین این نمونه‌ها یا خوشه‌ها بیشتره.
• با کشیدن یک خط افقی که از بلندترین خط عمودی عبور می‌کنه، تعداد مناسب خوشه‌ها رو به دست میاریم و تعداد تقاطع‌ها با خطوط عمودی برابر با تعداد خوشه‌هاست.

تعداد بهینه خوشه‌ها رو می‌شه با پیدا کردن بلندترین خط عمودی که هیچ تقاطعی با سایر خوشه‌ها (خطوط افقی) نداره، به دست بیاره. چنین خطی در تصویر پایین با یک دایره قرمز و تیک سبز رنگ پیدا شده.

• برای پیوند کامل، این خط همون خط آبی در سمت راسته که سه خوشه تولید می‌کنه.

• برای پیوند میانگین، این همون خط عمودی آبی رنگ اولیه‌ست که دو خوشه تولید می‌کنه.

برای پیوند تکی، این خط عمودی اولیه‌ست که فقط یک خوشه تولید می‌کنه.

با توجه به مشاهدات بالا، به نظر می‌رسه پیوند میانگین بهترین خوشه‌بندی رو ارائه می‌ده، برعکسِ پیوند تکی و کامل که به ترتیب پیشنهاد می‌دن یک خوشه و سه خوشه در نظر بگیریم. همچنین عدد بهینه دو خوشه، با اطلاعات قبلی ما از مجموعه داده همخوانی داره، چون ما دو نوع وام‌گیرنده داریم.

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

از نمودار جعبه‌ای بالا می‌تونیم مشاهده کنیم که: 

• وام‌گیرندگان خوشه ۰ بالاترین امتیاز اعتباری رو دارن.  
• در حالی که وام‌گیرندگان خوشه ۱ امتیاز اعتباری کمتری دارن.

دوره تحلیل خوشه در پایتون در فینکا می‌تونه قدم بعدی خوبی باشه تا با استفاده از کتابخونه Scipy، عمیق‌تر با K-means و خوشه‌بندی سلسله‌مراتبی آشنا بشی.

نتیجه‌گیری

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

امیدواریم این مقاله مهارت‌های لازم رو در اختیارت قرار داده باشه تا بتونی داده‌های بدون برچسب رو برای تصمیم‌گیری‌های عملی به‌طور مؤثری خوشه‌بندی کنی.