24-05-2024, 10:32 PM
الگوریتم DBSCAN خوشه بندی
DBSCAN با یک نقطه شروع دلخواه و بازدید نشده شروع می شود. همسایگی این نقطه با استفاده از فاصله اپسیلون (ε) استخراج می شود. (کلیه نقاط که در فاصله ε قرار دارند نقاط همسایگی هستند). اگر تعداد کافی از نقاط (MinPoint )در این محله وجود داشته باشد ، فرآیند خوشه بندی آغاز می شود و نقطه داده فعلی به اولین نقطه در خوشه جدید تبدیل می شود.
الگوریتم سلسله مراتبی خوشه بندی
روش پایین به بالا یا تجمیعی: در این تکنیک هر نقطه را به یک خوشه خاص، اختصاص می دهد. فرض کنید 11 نقطه داده وجود دارد. هر یک از این نقاط را به یک خوشه اختصاص می دهد و بنابراین در ابتدا 11 خوشه خواهیم داشت. هر نقطه به یک خوشه اختصاص داده می شود. سپس، در هر تکرار، نزدیکترین جفت خوشه، ادغام می شود و این مرحله تکرار می شود تا نهایتاً یک خوشه باقی بماند. ادغام هر دو خوشه نزدیک به هم تا زمانی که فقط یک خوشه داشته باشیم، ادامه می یابد. ما در هر مرحله خوشه ها را ادغام می کنیم. از این رو، این نوع خوشه بندی به عنوان خوشه بندی سلسله مراتبی افزایشی نیز شناخته می شود.
روش بالا به پایین یا تقسیمی: خوشه بندی سلسله مراتبی از بالا به پایین بر عکس عمل می کند. به جای شروع با n خوشه (در صورت n نقطه داده)، با یک خوشه شروع می کند و تمام نقاط را به آن خوشه اختصاص می دهد. بنابراین، مهم نیست که ما 10 یا 1000 نقطه داده داشته باشیم. همه این نقاط در ابتدا متعلق به یک خوشه هستند. اکنون، در هر تکرار، نقاط نزدیک به هم را در یک خوشه قرار می دهد و این روند تکرار می شود تا زمانی که در نهایت هر کدام از نقطه ها به تنهایی درون یک خوشه قرار بگیرند. در این روش خوشه ها در هر مرحله تقسیم می شود. از این رو نام آن خوشه بندی سلسله مراتبی تقسیم کننده است.
DBSCAN با یک نقطه شروع دلخواه و بازدید نشده شروع می شود. همسایگی این نقطه با استفاده از فاصله اپسیلون (ε) استخراج می شود. (کلیه نقاط که در فاصله ε قرار دارند نقاط همسایگی هستند). اگر تعداد کافی از نقاط (MinPoint )در این محله وجود داشته باشد ، فرآیند خوشه بندی آغاز می شود و نقطه داده فعلی به اولین نقطه در خوشه جدید تبدیل می شود.
الگوریتم سلسله مراتبی خوشه بندی
روش پایین به بالا یا تجمیعی: در این تکنیک هر نقطه را به یک خوشه خاص، اختصاص می دهد. فرض کنید 11 نقطه داده وجود دارد. هر یک از این نقاط را به یک خوشه اختصاص می دهد و بنابراین در ابتدا 11 خوشه خواهیم داشت. هر نقطه به یک خوشه اختصاص داده می شود. سپس، در هر تکرار، نزدیکترین جفت خوشه، ادغام می شود و این مرحله تکرار می شود تا نهایتاً یک خوشه باقی بماند. ادغام هر دو خوشه نزدیک به هم تا زمانی که فقط یک خوشه داشته باشیم، ادامه می یابد. ما در هر مرحله خوشه ها را ادغام می کنیم. از این رو، این نوع خوشه بندی به عنوان خوشه بندی سلسله مراتبی افزایشی نیز شناخته می شود.
روش بالا به پایین یا تقسیمی: خوشه بندی سلسله مراتبی از بالا به پایین بر عکس عمل می کند. به جای شروع با n خوشه (در صورت n نقطه داده)، با یک خوشه شروع می کند و تمام نقاط را به آن خوشه اختصاص می دهد. بنابراین، مهم نیست که ما 10 یا 1000 نقطه داده داشته باشیم. همه این نقاط در ابتدا متعلق به یک خوشه هستند. اکنون، در هر تکرار، نقاط نزدیک به هم را در یک خوشه قرار می دهد و این روند تکرار می شود تا زمانی که در نهایت هر کدام از نقطه ها به تنهایی درون یک خوشه قرار بگیرند. در این روش خوشه ها در هر مرحله تقسیم می شود. از این رو نام آن خوشه بندی سلسله مراتبی تقسیم کننده است.