دسته‌بندی نشده
تجزیه و تحلیل خوشه‌بندی سلسله‌مراتبی
مروری بر تجزیه‌وتحلیل خوشه‌بندی سلسله‌مراتبی
تحلیل خوشه‌بندی سلسله‌مراتبی الگوریتمی است که برای گروه‌بندی نقاط داده با ویژگی‌های مشابه استفاده می‌شود. این گروه‌ها به عنوان خوشه نامیده می‌شوند. در نتیجه‌ی خوشه‌بندی سلسله‌مراتبی، مجموعه‌ای از خوشه‌هایی را خواهیم داشت که با یکدیگر متفاوت هستند. خوشه‌بندی این داده‌ها به عناوین زیر طبقه‌بندی می‌شوند:
خوشه‌بندی تجمعی (شامل تجزیه خوشه با استفاده از استراتژی پایین به بالا)
و خوشه‌بندی تقسیمی (شامل تجزیه خوشه با استفاده از استراتژی از بالا به پایین)
انواع مختلفی از تجزیه‌وتحلیل خوشه‌بندی وجود دارد. یکی از این انواع، خوشه‌بندی سلسله‌مراتبی است.
خوشه‌بندی سلسله‌مراتبی به ایجاد خوشه‌ها در نظم/سلسله‌مراتب مناسب کمک می‌کند. به‌عنوان‌مثال، رایج‌ترین مثال روزمره‌ای که می‌بینیم این است که چگونه فایل‌ها و پوشه‌های خود را در رایانه خود با سلسله‌مراتب مناسب مرتب می‌کنیم.
انواع خوشه‌بندی سلسله‌مراتبی
خوشه‌بندی سلسله‌مراتبی به دو نوع تقسیم می‌شود، یعنی خوشه‌بندی تجمعی و خوشه‌بندی تقسیمی (DIANA).
خوشه‌بندی تجمعی
در این حالت از خوشه‌بندی، تجزیه سلسله‌مراتبی با کمک استراتژی از پایین به بالا انجام می‌شود، به این شکل که با ایجاد خوشه‌های اتمی (کوچک) و افزودن یک شیء داده شروع می‌شود و سپس آنها را با هم ادغام می‌کند تا در پایان یک خوشه بزرگ تشکیل شود. این رویه تکرار می‌شود تا زمانی که تمام نقاط داده تحت یک خوشه بزرگ قرار گیرند.
AGNES (AGglomerative NESting) نوعی از خوشه‌بندی تجمعی است که اشیاء داده را در یک خوشه بر اساس شباهت ترکیب می‌کند. نتیجه این الگوریتم یک ساختار درختی به نام دندروگرام است. در اینجا از معیارهای فاصله برای تصمیم‌گیری اینکه کدام نقاط داده باید با کدام خوشه ترکیب شوند استفاده می‌کند. اساساً یک ماتریس فاصله ایجاد می‌شود و جفت خوشه‌هایی با کمترین فاصله با هم ترکیب می‌شوند.
بر اساس نحوه اندازه‌گیری فاصله بین هر خوشه، می‌توانیم 3 روش مختلف داشته باشیم:
پیوند منفرد: جایی که کمترین فاصله بین دو نقطه در هر خوشه به عنوان فاصله بین خوشه‌ها تعریف می‌شود.
پیوند کامل: در این حالت، ما بیشترین فاصله بین نقاط هر خوشه را به عنوان فاصله بین خوشه‌ها در نظر می‌گیریم.
میانگین پیوند: در اینجا، میانگین بین هر نقطه در یک خوشه را با هر نقطه دیگر در خوشه دیگر به دست می‌آوریم.
حال بیایید نقاط قوت و ضعف در AGNES را مورد بحث قرار دهیم. این الگوریتم دارای پیچیدگی زمانی حداقل O(n2) است. ازاین‌رو در مقیاس‌بندی خوب عمل نمی‌کند. یکی دیگر از اشکالات مهم آن، این است که هر کاری انجام شده در آن هرگز قابل بازگرداندن نیست، یعنی اگر هر خوشه‌ای را به اشتباه در مرحله اولیه الگوریتم گروه‌بندی کنیم، در ادامه نمی‌توانیم نتیجه را تغییر دهیم و یا آن را اصلاح کنیم. اما این الگوریتم جنبه مثبت و روشن هم دارد زیرا در روند آن خوشه‌های کوچک‌تر زیادی تشکیل شده است. ترتیب ایجاد شده می‌تواند در تجسم و تصویرسازی بسیار مفید واقع شود.
خوشه‌بندی تقسیمی (DIANA)
Diana اساساً مخفف تجزیه‌وتحلیل تقسیمی است. این روش، نوع دیگری از خوشه‌بندی سلسله‌مراتبی است که بر اساس اصل رویکرد از بالا به پایین (معکوس) AGNES کار می‌کند که در آن الگوریتم با تشکیل یک خوشه بزرگ شروع می‌شود و به صورت بازگشتی غیر مشابه‌ترین خوشه را به دو قسمت تقسیم می‌کند و تا زمانی ادامه می‌یابد که همه نقاط داده مشابه به خوشه‌های مربوطه خود تعلق پیدا کنند. این الگوریتم‌های تقسیم‌کننده منجر به سلسله مراتب بسیار دقیق‌تری نسبت به رویکرد تجمعی می‌شوند، اما از نظر محاسباتی گران هستند.
خوشه‌بندی سلسله‌مراتبی چند فازی
برای بهبود کیفیت خوشه‌های تولید شده توسط تکنیک‌های خوشه‌بندی سلسله‌مراتبی فوق، ما تکنیک‌های خوشه‌بندی سلسله‌مراتبی خود را با سایر تکنیک‌های خوشه‌بندی به نام خوشه‌بندی چند فازی ادغام می‌کنیم. انواع مختلف خوشه‌بندی چند فازی به شرح زیر است:
• BIRCH (کاهش و خوشه‌بندی متوازن تکراری با استفاده از سلسله‌مراتب)
• ROCK (خوشه‌بندی RObust با استفاده از پیوندها)
• CHAMELEON
1. کاهش و خوشه‌بندی متوازن تکراری با استفاده از سلسله‌مراتب
این روش عمدتاً برای خوشه‌بندی حجم عظیمی از داده‌های عددی با ادغام خوشه‌بندی سلسله‌مراتبی/ریز در فاز اولیه و خوشه‌بندی کلان/پارتیشن‌بندی تکراری در فاز بعدی استفاده می‌شود. این روش به غلبه بر مشکل مقیاس‌پذیری که در AGNES با آن مواجه بودیم و ناتوانی در لغو کاری که در مرحله قبل انجام شد کمک می‌کند. BIRCH از دو مفهوم مهم در الگوریتم خود استفاده می‌کند
الف. ویژگی خوشه‌بندی (به جمع‌بندی خوشه کمک می‌کند)
CF به صورت <n, LS, SS> تعریف می‌شود ( n تعداد نقاط داده در خوشه، مجموع خطی n نقطه، مجموع مربع n نقطه). ذخیره کردن ویژگی یک خوشه به جلوگیری از ذخیره اطلاعات دقیق در مورد آن کمک می‌کند و CF ماهیت افزایشی برای خوشه‌های مختلف دارد.
CF1 + CF2 = <n1+n2, LS1+LS2, SS1+SS2>
ب. درخت ویژگی خوشه‌بندی (به نمایش یک خوشه به عنوان یک سلسله‌مراتب کمک می‌کند)
درخت CF درختی متعادل با فاکتور انشعاب B (حداکثر تعداد فرزندان) و آستانه (T حداکثر تعداد زیر خوشه‌هایی است که می‌توان در گره‌های برگ ذخیره کرد)
الگوریتم اساساً در 2 فاز کار می‌کند. در فاز 1 پایگاه داده را اسکن می‌کند و یک درخت CF در حافظه ایجاد می‌کند و در فاز 2 از الگوریتم خوشه‌بندی استفاده می‌کند که با حذف نقاط پرت (خوشه‌های پراکنده) به خوشه‌بندی گره‌های برگ کمک می‌کند و خوشه را با حداکثر چگالی گروه‌بندی می‌کند. تنها اشکال این الگوریتم این است که فقط نوع داده‌های عددی را کنترل می‌کند.
2. خوشه‌بندی Robust با استفاده از پیوندها
پیوند به عنوان تعداد همسایه‌های مشترک بین دو شی تعریف می‌شود. الگوریتم ROCK نوعی الگوریتم خوشه‌بندی است که از این مفهوم پیوند با مجموعه داده‌های طبقه‌بندی شده استفاده می‌کند. همان‌طور که می‌دانیم الگوریتم‌های خوشه‌بندی فاصله اندازه‌گیری شده، خوشه‌های باکیفیت بالا را برای مجموعه داده طبقه‌ای ارائه نمی‌کنند، اما در مورد ROCK، همسایگی نقاط داده را نیز در نظر می‌گیرد، یعنی اگر دو نقطه داده همسایگی یکسانی داشته باشند، پس آنها به‌احتمال زیاد به یک خوشه تعلق دارند. الگوریتم در مرحله اول با درنظرگرفتن ماتریس شباهت با مفهوم همسایگی و آستانه تشابه یک نمودار پراکنده می‌سازد. مرحله دوم از تکنیک خوشه‌بندی سلسله‌مراتبی تجمعی بر روی نمودار پراکنده استفاده می‌کند.
3. Chameleon
این نوع الگوریتم خوشه‌بندی سلسله‌مراتبی از مفهوم مدل‌سازی پویا (دینامیک) استفاده می‌کند. تعجب می‌کنید که چرا به آن پویا می‌گویند؟ زیرا می‌تواند به طور خودکار با ویژگی‌های خوشه داخلی با ارزیابی شباهت خوشه سازگار شود، یعنی اینکه نقاط داده در یک خوشه و در مجاورت خوشه‌ها چقدر به هم متصل هستند. یکی از اشکالات Chameleon این است که هزینه پردازش آن بسیار زیاد است .
نتیجه
در این مقاله عناوینی چون خوشه و تجزیه‌وتحلیل خوشه، انواع تکنیک‌های خوشه‌بندی سلسله‌مراتبی و مزایا و معایب آنها را آموختیم. هر یک از تکنیک‌هایی که مورد بحث قرار گرفت، نقاط مثبت و منفی خاص خود را دارد. ازاین‌رو، ما باید داده‌های خود را با تجزیه‌وتحلیل داده‌های اکتشافی مناسب درک کنیم و قبل از ادامه الگوریتم، الگوریتم را بااحتیاط انتخاب کنیم.
منبع
مترجم:مریم محجوب
