کاهش و خوشه‌بندی ترازمند و بازکردی با بهره‌گیری از رده‌بندی

کاهش و خوشه‌بندی ترازمند و بازکردی با بهره‌گیری از رده‌بندی (balanced iterative reducing and clustering using hierarchies) که در زبان انگلیسی به شکل مخفف به آن BIRCH گفته می‌شود، یک الگوریتم خوشه‌بندی سلسله‌مراتبی می‌باشد. این روش یکی از روش‌های یادگیری خودران می‌باشد که از آن جهت داده‌کاوی روی دادگان بزرگ و حجیم استفاده می‌شود.

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

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

الگوریتم

ورودی‌های این الگوریتم مجموعه‌ای از بردارهای حقیق به اندازه $N$ و عدد $K$ که به نشان‌دهنده تعداد خوشه‌ها است، هستند. الگوریتم شامل ۴ مرحله می‌باشد:

• مرحله اول: درخت ویژگی خوشه‌بندی روی داده‌ها تشکیل می‌شود. نحوهٔ تشکیل این درخت به شرح زیر است:
  • ویژگی خوشه‌بندی داده‌ها به شکل یک سه‌تایی $CF=(N,{\overrightarrow {LS}},SS)$ تعریف می‌شود که در آن ${\overrightarrow {LS}}=\sum _{i=1}^{N}{\overrightarrow {X_{i}}}$ جمع خطی بردارها و $SS=\sum _{i=1}^{N}({\overrightarrow {X_{i}}})^{2}$ جمع مربع بردارها می‌باشد.
  • ویژگی‌های خوشه‌بندی در یک درخت ویژگی خوشه‌بندی چیده می‌شوند. این درخت، درختی با ارتفاع متعادل. این درخت شامل دو پارامتر $B$ و $T$ می‌باشد که به ترتیب ضریب انشعاب درخت و یک متغیر آستانه می‌باشند. هر راس غیر برگ در این درخت حداکثر شامل $B$ عضو مانند$[CF_{i},child_{i}]$ می‌باشد که در آن $child_{i}$ یک اشاره‌گر به به فرزند $i$ام آن راس و $CF_{i}$ ویژگی خوشه متناظر با زیرخوشهٔ مربوط به آن فرزند می‌باشد. همچنین برگ‌های درخت شامل حداکثر $L$ عضو هرکدام به شکل $CF_{i}$ می‌شود. همچنین در برگ‌ها اشاره‌گرهایی به برگ‌ها قبلی و بعدی نیز وجود دارد که تمامی برگ‌های درخت را به یکدیگر متصل می‌کنند.
• مرحله دوم: الگوریتم با بررسی تمامی برگ‌های درخت تشکیل شده در مرحله قبل یک درخت ویژگی خوشه جدید می‌سازد که از درخت قبلی کوچک‌تر است. در همین حین الگوریتم داده‌های پرت را حذف می‌کند و خوشه‌های پیشین را به یکدیگر ملحق می‌کند. دقت کنید که می‌توان این مرحله را اجرا نکرد. درواقع اجرای این مرحله انتخابی می‌باشد.
• مرحله سوم: در این مرحله، الگوریتم با استفاده از یکی از خوشه‌های موجود، همهٔ اعضای برگ‌ها را خوشه‌بندی می‌کند. این کار با استفاده از اجرای یک الگوریتم خوشه‌بندی agglomerative به شکل مستقیم روی زیرخوشه‌های درخت ویژگی خوشه انجام می‌پذیرد.
• مرحله چهارم: مرکز خوشه‌های به دست آمده در مرحله سوم به عنوان seed استفاده می‌شود و داده‌ها بازتوزیع می‌شوند تا به یک مجموعه جدید از خوشه‌ها برسیم.

نقاط قوت الگوریتم

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