انواع خوشه‌بندی

مسائل خوشه‌بندی را می‌توان به دو نوع اصلی دسته‌بندی کرد: خوشه‌بندی فازی و خوشه‌بندی سخت. در خوشه‌بندی فازی ، نقاط داده می‌توانند با احتمال بین 0 و 1، به بیش از یک خوشه متعلق باشند (J. Bezdek, J. Keller, R. Krishnapuram, and N. Pal ، 1992)، (D. Karaboga and C. Ozturk ، 2010) که نشان‌دهنده قدرت روابط بین نقاط داده و یک خوشه‌ی خاص است. یکی از محبوب‌ترین الگوریتم‌های خوشه‌بندی فازی الگوریتم فازی C-mean است. (Bezdek ، 1981)، (J. Bezdek and N. Pal ، 1999)، (F. Hoppner, F. Klawonn, R. Kruse, and T. Runkler ، 1999). در خوشه‌بندی سخت، نقاط داده به خوشه‌های مجزا تقسیم می‌شوند، که در آن هر نقطه‌ی داده، می‌تواند به یک و تنها یک خوشه متعلق باشد.

خوشه‌بندی سخت به الگوریتم‌های سلسله مراتبی و بخش‌بندی تقسیم می‌شود. الگوریتم‌های سلسله مراتبی روابط تودرتوی خوشه‌ها را ایجاد می‌کنند که می‌توانند به‌عنوان یک ساختار درختی به نام دندروگرام درنظر گرفته شوند (گان و همکاران، 2007). الگوریتم‌های سلسله مراتبی را می‌توان به الگوریتم‌های سلسله مراتبی متراکم و تقسیم‌کننده تقسیم نمود. خوشه‌بندی سلسله مراتبی متراکم با هر نقطه داده‌ در یک خوشه‌ی واحد شروع می‌شود. سپس ادغام جفت‌های مشابه خوشه‌ها را تا زمانی که تمام نقاط داده در یک خوشه قرار بگیرند، تکرار می‌کند،خوشه‌بندی ارتباط کامل (D. Defays ، 1977) و خوشه بندی ارتباط واحد (R. Sibson ، 1973). CURE (S. Guha, R. Rastogi ، 1998) ، ROCK (گوها و همکاران، 2000) ، BIRCH (T. Zhang, and H. Qu, ، 1996) و Chameleon (G. Karypis and V. Kumar ، 1998) نمونه‌هایی از این الگوریتم سلسله مراتبی می‌باشند. الگوریتم سلسله مراتبی تقسیم‌کننده، عملیات‌های خوشه‌بندی متراکم را معکوس می‌کند، این الگوریتم با تمام نقاط داده‌ی در یک خوشه شروع می‌شود و تقسیم کردن خوشه‌های بزرگ به کوچک‌تر را تا زمانی که هر نقطه‌ی داده به یک خوشه‌ی واحد تعلق داشته باشد، تکرار می‌کند مانند الگوریتم خوشه‌بندی DIANA (L. Kaufman, and P. Rousseeuw ، 1990).

در مقابل، الگوریتم خوشه‌بندی بخش‌بندی، مجموعه داده را به مجموعه‌ای از خوشه‌های منفصل تقسیم می‌کند، مانند Kmeans (J. MacQueen ، 1967) ، (E. Forgy ، 1965) PAM (] L. Kaufman, and P. Rousseeuw ، 1990) و CLARA (] L. Kaufman, and P. Rousseeuw ، 1990). علاوه بر این، الگوریتم‌های بخش‌بندی، برای برنامه‌های کاربردی با مجموعه داده‌ی بزرگ مناسب‌تر است، که در آن ساختمان دندروگرام ازنظر محاسباتی گران است (W.-Y. Chen, Y. Song, H. Bai, C.-J. Lin, E. Chang ، 1999)، (X. Zhou, and Y. Shi ، 2005). یکی از مسائل در کاربرد روش بخش‌بندی، انتخاب تعداد خوشه‌های درون مجموعه داده‌های معین است که در آن تعیین تعداد خوشه‌ها، یکی از مشکل‌سازترین مسائل در  خوشه­بندی داده است (L. van der Maaten, E. Postma, and H. van den Herik ، 2007). الگوریتم‌های بخش‌بندی اغلب از یک تابع هدف خاص استفاده می‌کنند و با بهینه‌سازی این تابع هدف خوشه‌های دلخواهی را تولید می‌کنند (P. Hansen and B. Jaumard ، 1997).

الگوریتم‌های خوشه‌بندی که بر پایه‌ی برآورد چگالی‌های نقاط داده استوار هستند، به‌عنوان روش‌های مبتنی بر چگالی شناخته می‌شوند. DBSCAN یکی از الگوریتم‌های خوشه‌بندی مبتنی بر چگالی است (, M. Ester, H. P. Kriegel, J. Sander1996). این الگوریتم چگالی را به وسیله‌ی شمارش تعداد نقاط داده در یک منطقه‌ی مشخص‌شده توسط یک شعاع از پیش تعریف‌شده‌ی در اطراف نقطه‌ی داده، به نام اپسیلون، تعریف می‌کند. اگر یک نقطه‌ی داده، تعداد بیشتر یا مساوی با حداقل نقاط از پیش تعریف‌شده، به نام MinPts، را داشته باشد، سپس با این نقطه، به‌عنوان نقطه‌ی هسته رفتار می‌شود. با نقاط داده‌ی غیر هسته که در شعاع از پیش تعریف‌شده نقطه‌ی داده‌ی هسته ندارند، به‌عنوان نویز رفتار می‌شود. سپس خوشه‌ها در اطراف نقاط داده‌ی هسته تشکیل می‌شوند و به‌صورت مجموعه‌ای از نقاط داده‌ی متصل با چگالی تعریف می‌شوند که با توجه به قابل‌دسترس بودن چگالی حداکثر می‌گردند. DBSCAN، می‌تواند به دلیل تعریف ضعیفش از چگالی نقاط داده و پارامترهای کلی از پیش تعریف‌شده‌ی ε و MinPts اش، ضعیف عمل کند. (Ankerst, M. Breunig, H. P. Kriegel, and J. Sander ، 1999)، (Borah, and D.K. Bhattacharyya ، 2008؛ Ram, S. Jalal, A. S. Jalal, and M. Kumar ، 2010؛ K. Mumtaz and K. Duraiswamy ، 2010؛ A. Fahim, A. Salem, F. Torkey, and M. Ramadan 2007؛ S. Kisilevich, F. Mansmann, and D. Keim ، 2010).