Large scale clustering

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

ما در این پروژه الگوریتم خوشه‌بندی موازی و مقیاس‌پذیری را به نام MapReduce Summarized Single-Link) MRSSL) با استفاده از چارچوب نگاشت‌کاهش ارائه می‌دهیم که می‌تواند بزرگ‌داده‌ها را به‌طور مؤثر و کارا خوشه‌بندی کند. الگوریتم پیشنهادی با تطبیق یک روش خلاصه‌سازی با چارچوب نگاشت‌کاهش، مجموعه داده‌ها را به‌طور موازی به مجموعه‌ای از نقاط نماینده که در داخل حافظه اصلی ماشین‌های خوشه جای می‌گیرند کاهش داده و سپس آن‌ها را خوشه‌بندی می‌کند. ما MRSSL را با استفاده از اسپارک که چارچوبی سریع و نوین برای پردازش بزرگ‌داده‌ها محسوب می‌شود توسعه دادیم. استفاده از این چارچوب و توانایی بالای آن در پردازش درون حافظه‌ای این امکان را فراهم می‌کند تا بر روی خوشه‌ای با تعداد زیادی ماشین خوشه‌بندی با سرعت و مقیاس‌پذیری بالا انجام گیرد. ما همچنین راهکاری کارآمد برای موازی‌سازی ماتریس فاصله در الگوریتم‌های سلسله مراتبی با استفاده از چارچوب اسپارک ارائه دادیم. نتایج آزمایش‌های ما با مجموعه داده‌های متنوع و حجیم شامل میلیون‌ها نقطه داده با ابعاد بالا تأکید می‌کند که MRSSL از توانایی لازم برای خوشه‌بندی بزرگ‌داده‌ها با مقیاس‌پذیری و سرعت بالا برخوردار است.

در زیر برخی از مجموعه‌داده‌های مورد استفاده در این پروژه نشان داده شده است.