IFD : Image Forgery Detection

خوشه بندی سلسله مراتبی

خوشه بندی سلسله مراتبی یکی از پرکاربردترین روش های خوشه بندی است.

خوشه بندی سلسله مراتبی تکنیکی است که در گروه بندی یا دسته بندی داده ها به کار می رود.  نقاط داده ها در این روش در دسته ها و زیر دسته هایی بر اساس معیار شباهت قرار می گیرند.

در این روش به خوشه ی نهایی بر اساس میزان عمومیت آنها ساختاری سلسله مراتبی، معمولا به صورت درختی نسبت داده می شود. به این درخت سلسله مراتبی دندوگرام می گویند. تکنیک کار این نوع خوشه بندی معمولا بر اساس الگوریتم های حریصانه  است. از مزیت های خوشه بندی سلسله مراتبی، سادگی و قابلیت درک برای تمامی پژوهشگران است. این روش شامل مد لهای متنوعی است که میتواند نیازهای متعددی  را رفع کند.

برای خوشه بندی مشاهدات با توجه به متغیرهای اندازه گیری شده برای هر مشاهده، فاصله ی بین مشاهدات را با متری که معمولا متر اقلیدسی است اندازه گیری می کنند. فاصله اقلیدسی فاصله ی بین دو مشاهده i و j را محاسبه می کند. روش محاسبه ی فاصله ی دو مشاهده با استفاده از فاصله اقلیدسی به صورت زیر است:

با استفاده از این روش فاصله ی بین مشاهدات را به صورت دو به دو محاسبه می کنیم و فاصله های بدست آمده را در ماتریس فاصله قرار می دهیم. بعد از تشکیل ماتریس فاصله، کوچکترین عدد در ماتریس فاصله را پیدا می کنیم. این عدد نشان دهند هی ایناست که دو مشاهده ی فوق کم ترین فاصله ی بین مشاهدات را از یکدیگر دارند، لذا می توان دو مشاهده را در قالب یک خوشه قرار داد. سپس از یکی از روش های ادغام استفاده می کنیم و آنها را ترکیب می کنیم. و در نهایت در درخت دندوگرام  نمایش می دهیم.

دندوگرام یک نمودار دو بعدی است که هم به صورت عمودی هم افقی می توان آنرا رسم کرد نتایج در هر دو صورت یکسان است.

برای تعیین تعدادخوشه می توان دندوگرام را در یک نقطه مناسب برش داد. در این نمودار آنچه که اهمیت دارد ارتفاع است. هر چه خوشه های تشکیل شده در ارتفاع پایینتری ایجاد شده باشند خوشه ها یا مشاهدات به یکدیگر شبیه تر و بالعکس هستند.

خوشه بندی سلسله مراتبی در داد  با بُعد بالا، به دلیل زمان زیادی که صرف محاسبات می نماید، مقرون به صرفه و گاهی نیز قابل محاسبه نیست. البته این مشکل را با خوشه بندی K-MEANS رفع می کنند.

مزیت این روش این است که به اطلاعات قبلی راجع به تعدادخوشه ها نیازی ندارد و عیبش، عدم وجود انتصاب مجدد در آن است.

این نوع خوشه بندی خود دارای دو روش بالا به پایین (تقسیم کننده) و پایین به بالا (تجمعی) می باشد که در پستهای بعدی به شرح آنها میپردازیم.


منبع:

دانلود خوشه بندی و روشهای آن

دانلود خوشه بندی K-means  و سلسله در نرم افزارها

دانلود تحلیل خوشه بندی(ppt)

نظرات (0)
امکان ثبت نظر جدید برای این مطلب وجود ندارد.