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

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

آشنایی با الگوریتم های خوشه بندی کی از مهم ترین بخش های دوره یادگیری عمیق است . پیش از شروع یادگیری مفهوم خوشه بندی سلسله مراتبی لازم است تا با مفهوم خوشه بندی و الگوریتم های آن آشنا باشید.  خوشه بندی سلسله مراتبی یکی از الگوریتم‌ های یادگیری بدون نظارت است که از آن برای گروه‌ بندی نقاط داده که دارای مشخصه‌ های مشابه هستند، استفاده می‌شود. الگوریتم‌ های خوشه بندی سلسله مراتبی به دو دسته تقسیم می‌ شوند که عبارتند از الگوریتم‌ های سلسله مراتبی جمع کننده (روش پایین به بالا) که در این گروه از الگوریتم‌ ها، هر نقطه داده به عنوان یک خوشه واحد در نظر گرفته می‌ شود و سپس به صورت متوالی با جفتی از خوشه‌ ها یکپارچه می‌شود. همچنین الگوریتم‌ های سلسله مراتبی تقسیم کننده (روش بالا به پایین) که در الگوریتم‌ های سلسله مراتبی تقسیم کننده همه نقاط داده به عنوان یک خوشه بزرگ در نظر گرفته می‌ شوند و روال خوشه بندی شامل تقسیم یک خوشه بزرگ به چندین خوشه کوچک است. همچنین روش‌ های خوشه بندی مبتنی بر سلسله مراتب نیز  عبارتند از الگوریتم خوشه بندی Birch، الگوریتم خوشه بندی DIANA، الگوریتم خوشه بندی AGNESو الگوریتم خوشه بندی Chameleon که در ادامه آن را توضیح می دهیم.

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

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

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

الگوریتم Birch دارای 4 فاز است که داده‌های زیر را به عنوان ورودی دریافت می‌کند.

1. یک مجموعه از N نقطه داده که به صورت یک بردار حقیقی نمایش داده می‌شود.
2. عدد K که نشان‌دهنده تعداد خوشه‌هاست.

فاز اول: الگوریتم Birch در این فاز یک درخت CF که یک درخت متوازن است و به صورت زیر تعریف می‌شود را از نقاط داده ایجاد می‌نماید:

• فرض کنید یک مجموعه از N نقطۀ دادۀ d بعدی وجود دارد، در این صورت ویژگی خوشه CF مجموعه داده به صورت یک سه تایی CF=(N,LS,SS) تعریف می‌گردد که در آن LS جمع خطی و SS جمع مربعی می‌باشد.
• ویژگی‌های خوشه بندی در یک درخت CF که درختی متوازن با دو پارامتر فاکتور انشعاب B(factor branching) و آستانه T (threshold) است تنظیم می‌شود. هر گره غیر برگ حداکثر B مدخل به صورت

دارد که در آن

یک اشاره‌گر به i امین فرزند و

ویژگی خوشه بندی برای زیر خوشۀ مورد نظر می‌باشد. هر گره برگ حداکثر دارای L ورودی به شکل

است. علاوه بر این، جهت ایجاد زنجیر بین گره‌ های برگ دو اشاره‌ گر perv و next دارد. اندازه درخت هم به پارامتر T بستگی دارد. یک گره باید در یک صفحه به اندازه P واقع شود، توسط این پارامتر B و L تعیین می‌ شوند. از این رو P می‌ تواند جهت تنظیم عملکرد تغییر نماید. این در واقع نمایشی متراکم از مجموعه داده می‌ باشد، چرا که هر ورودی در یک گره برگ یک نقطه داده تکی نمی‌ باشد ولی یک زیر خوشه محسوب می‌ شود.

فاز دوم: الگوریتم در این فاز برای ایجاد یک درخت CF کوچکتر، همه ورودی‌ های برگ را در درخت CF اولیه پویش می‌ کند، در حالی‌ که زیر شاخه‌ هایی را که مفید نیستند دور انداخته و زیر شاخه‌ هایی را که شلوغ هستند را در زیر شاخه‌ های بزرگتر گروه‌بندی می‌ نماید. توجه داشته باشید که در نمایش اصلی الگوریتم birch این مرحله اختیاری در نظر گرفته می‌ شود.

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

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

الگوریتم خوشه بندی DIANA(الگوریتم خوشه بندی پایین رونده)

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

الگوریتم خوشه بندی AGNES(الگوریتم خوشه بندی بالا رونده)

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

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

الگوریتم خوشه بندی Chameleon شامل دو مرحله زیر است:

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

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

معمولا پیش از آغاز مراحل خوشه بندی سلسله مراتبی جمع کننده، برای سرعت بخشیدن در امر محاسبات از یک ماتریس فاصله (Distance Matrix) یا ماتریس شباهت(Similarity Matrix) استفاده می‌ شود. این ماتریس نشان دهنده این است که فاصله بین هر زوج از مشاهدات چه اندازه است. البته باید گفت نوع تابعی که باید به وسیله آن فاصله اندازه‌گیری گردد در مقدارهای موجود در این ماتریس موثر خواهد بود. در خوشه بندی سلسله مراتبی جمع کننده(HAC) با توجه به مقدارهای این ماتریس، مشاهدات و یا خوشه‌ هایی که کمترین فاصله یا به عبارتی بیشترین شباهت را دارند با هم ادغام شده و خوشه جدیدی را ایجاد می‌کنند. در مرحله بعد مجددا فاصله بین مشاهدات و یا خوشه‌ های جدید، به وسیله ماتریس فاصله که بروز رسانی شده، محاسبه شده و کار ادغام ادامه می‌ یابد تا فقط یک خوشه باقی بماند.

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

1. میزان فاصله بین زوج مشاهدات: در این حالت توابع فاصله برای داده‌ های کمی و کیفی قابل استفاده می‌ باشند. 

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

• فاصله اقلیدسی(Euclidean Distance): برای محاسبه فاصله اقلیدسی می‌ توان از فرمول زیر استفاده کرد:

• فاصله منهتن(Manhattan Distance): فرمول محاسبه فاصله منهتن به شرح زیر است:

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

• مربع فاصله اقلیدسی(Squared Euclidean Distance)

• فاصله حداکثر(Maximum Distance)

• فاصله ماهالانویس(Mahalanobis)

s^(-1) ماتریس کواریانس و T ترانهاده ماتریس می‌ باشد.

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

برای داده‌ های کیفی هم می‌ توان یکی از روش‌ های زیر را به کار برد:

• میزان انطباق ساده(Simple Matching)
• فاصله همینگ(Hamming Distance)

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

2 . میزان فاصله بین خوشه‌ ها (روش‌ های پیوند): معیارهای گوناگونی را می‌ توان برای سنجش فاصله بین خوشه‌ ها به کار گرفت. مثلا می‌ توان فاصله بین نزدیکترین یا دورترین مشاهدات بین دو خوشه را در نظر گرفت که هر کدام از این معیارها معایب و مزایای مخصوص به خود را دارند. اما توجه به ساختار داده‌ ها از جمله الگوی پراکندگی مشاهدات، وجود داده‌های پرت و غیره می‌ تواند معیاری برای انتخاب یکی از روش‌ های پیوند باشد. برای اندازه‌گیری فاصله بین خوشه‌ ها می‌ توان یکی را از روش‌ های زیر را به کار برد.

فرض: اندازه‌گیری فاصله بین دو خوشه M و N

d       تابع فاصله دلخواه است(از یکی از توابع فاصله معرفی شده در بالا انتخاب می‌شود).

• Single linkage( connectedness یا روش minimum : نزدیکترین فاصله یا پیوند تکی)

• Complete linkage( diameter یا روش maximum : دورترین فاصله یا پیوند کامل)

• Average linkage(پیوند میانگین)

• UPGMC(پیوند مرکزی یا فاصله بین نقاط مرکزی هر خوشه)

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

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

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

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

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

قبل از هر چیز لازم است تا پکیج های مورد نیاز نصب شوند

library(stats)
library(factoextra)  // امکان نمایش ماتریس فاصله و درخت‌واره را فراهم می‌کند‌
n=10
k=5     //تعداد خوشه‌ها
data=iris[c(sample(x=1:100,size=n),sample(x=101:200,size=n),sample(x=201:300,size=n)),1:6]                               

DistanceMethod=c('euclidean')

LinkageMethod= c("average")

interval=dist(data, DistanceMethod)

Khorchi=hclust(y= interval,method= LinkageMethod)

Interval
fviz_dist(dist.obj= Interval)     //ماتریس فاصله را به صورت تصویری نمایش می‌دهد

Khorchi

fviz_dend(x= Khorchi,k=k)      // درخت‌واره نگار را نمایش می‌دهد

Khorchi$merge                     //با این دستور مراحل ادغام خوشه‌ها دیده می‌شود

کد بالا برای ایجاد تعداد k=5  خوشه برای یک نمونه 15 تایی از داده‌های iris نوشته شده است. در داده‌ های مذکور 5 دسته گل وجود دارد از این رو به صورت رندوم(تصادفی) از هر دسته 100 تایی یک نمونه n=10 تایی تهیه شده است تا خروجی‌ های خوشه‌ بندی سلسله مراتبی و همچنین نمودار به خوبی مشاهده گردد. برای اندازه‌گیری فاصله بین مشاهدات و خوشه‌ ها از فاصله اقلیدسی استفاده شده است و معیار پیوند هم پیوند میانگین می‌ باشد. توسط دستور dist ماتریس فاصله تولید شده و در متغیر interval قرار داده می‌ شود. خروجی دستور hclust که عملیات خوشه بندی را انجام می‌دهد در متغیر Khorchi قرار می‌گیرد.

توجه داشته باشید که چون تعداد خوشه‌ ها 5 در نظر گرفته شده است نمودار به 5 رنگ مختلف اعضای هر خوشه را جدا می‌کند.

سخن پایانی

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

در پایان آموزش یادگیری ماشین با استفاده از R و پایتون به شما پیشنهاد می شود.