وبلاگ

۱- الگوریتم‌های سلسله مراتبی^[۳۳]
۲- الگوریتم‌های افرازبندی^[۳۴]
الگوریتم‌های سلسله مراتبی، یک روال برای تبدیل یک ماتریس مجاورت به یک دنباله از افرازهای تو در تو، به صورت یک درخت است. در این روش‌ها، مستقیماً با داده‌ها سروکار داریم و از روابط بین آن‌ها برای به دست آوردن خوشه‌ها استفاده می‌کنیم. یکی از ویژگی‌های این روش قابلیت تعیین تعداد خوشه‌ها به صورت بهینه می‌باشد. در نقطه مقابل الگوریتم‌های سلسله مراتبی، الگوریتم‌های افرازبندی قرار دارند. هدف این الگوریتم‌ها، تقسیم داده‌ها در خوشه‌ها، به گونه‌ای است که داده‌های درون یک خوشه بیش‌ترین شباهت را به همدیگر داشته باشند؛ و درعین‌حال، بیش‌ترین فاصله و اختلاف را با داده‌های خوشه‌های دیگر داشته باشند. در این فصل تعدادی از متداول‌ترین الگوریتم‌های خوشه‌بندی، در دو دسته سلسله مراتبی و افرازبندی، مورد بررسی قرار می‌گیرند. از روش سلسله‌ مراتبی چهار الگوریتم‌ از سری الگوریتم‌های پیوندی^[۳۵] را مورد بررسی قرار می‌دهیم. و از الگوریتم‌های افرازبندی K-means، FCM و الگوریتم طیفی را مورد بررسی خواهیم داد.

(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))

۲-۲-۱-۱. الگوریتم‌های سلسله مراتبی
همان‌گونه که در شکل ۲-۱ مشاهده می‌شود، روال الگوریتم‌های خوشه‌بندی سلسله مراتبی را می‌تواند به صورت یک دندوگرام^[۳۶] نمایش داد. این نوع نمایش تصویری از خوشه‌بندی سلسله مراتبی، برای انسان، بیشتر از یک لیست از نمادها قابل‌درک است. در واقع دندوگرام، یک نوع خاص از ساختار درخت است که یک تصویر قابل‌فهم از خوشه‌بندی سلسله مراتبی را ارائه می‌کند. هر دندوگرام شامل چند لایه از گره‌هاست، به طوری که هر لایه یک خوشه را نمایش می‌دهد. خطوط متصل‌کننده گره‌ها، بیانگر خوشه‌هایی هستند که به صورت آشیانه‌ای^[۳۷] داخل یکدیگر قرار دارند. برش افقی یک دندوگرام، یک خوشه‌بندی را تولید می‌کند [۳۳]. شکل ۲-۱ یک مثال ساده از خوشه‌بندی و دندوگرام مربوطه را نشان می‌دهد.
شکل ۲-۱. یک خوشه‌بندی سلسله مراتبی و درخت متناظر
اگر الگوریتم‌های خوشه‌بندی سلسله مراتبی، دندوگرام را به صورت پایین به بالا بسازند، الگوریتم‌های خوشه‌بندی سلسله مراتبی تراکمی^[۳۸] نامیده می‌شوند. همچنین، اگر آن‌ها دندوگرام را به صورت بالا به پایین بسازند، الگوریتم‌های خوشه‌بندی سلسله مراتبی تقسیم‌کننده^[۳۹] نامیده می‌شوند [۲۶]. مهم‌ترین روش‌های خوشه‌بندی سلسله مراتبی الگوریتم‌های سری پیوندی می‌باشد که در این بخش تعدادی از کاراترین آن‌ها مورد بررسی قرار خواهند گرفت که عبارت‌اند از:

1. 1. الگوریتم پیوندی منفرد^[۴۰]

1. 1. الگوریتم پیوندی کامل^[۴۱]

1. 1. الگوریتم پیوندی میانگین^[۴۲]

1. 1. الگوریتم پیوندی بخشی^[۴۳]

۲-۲-۱-۱-۱. تعاریف و نماد‌ها
شکل ۲-۲. ماتریس مجاورت
قبل از معرفی این الگوریتم‌ها، در ابتدا نمادها و نحوه نمایش مسئله نمایش داده خواهد شد. فرض کنید که یک ماتریس مجاورت متقارن داریم. وارده در هر سمت قطر اصلی قرار دارد که شامل یک جای گشت اعداد صحیح بین ۱ تا است. ما مجاورت‌ها را عدم شباهت در نظر می‌گیریم. به این معنی است که اشیاء ۱ و ۳ بیشتر از اشیاء ۱ و ۲ به هم شبیه‌اند. یک مثال از ماتریس مجاورت معمول برای است که در شکل ۲-۲ نشان داده شده است. یک گراف آستانه^[۴۴]، یک گراف غیر جهت‌دار و غیر وزن‌دار، روی گره، بدون حلقه بازگشت به خود^[۴۵] یا چند لبه است. هر نود یک شیء را نمایش می‌دهد. یک گراف آستانه برای هر سطح عدم شباهت به این صورت تعریف می‌شود: اگر عدم شباهت اشیاء و از حد آستانه کوچک‌تر باشد، با واردکردن یک لبه بین نودهای و یک گراف آستانه تعریف می‌کنیم.
(۲-۱)if and only if
شکل ۲-۳ یک رابطه دودویی به دست آمده از ماتریس مربوط به شکل ۲-۲ را برای مقدار آستانه ۵ نشان می‌دهد. نماد “*” در موقعیت ماتریس، نشان می‌دهد که جفت متعلق به رابطه دودویی می‌باشد. شکل ۲-۴، گراف‌های آستانه برای ماتریس را نمایش می‌دهد.
شکل ۲-۳. رابطه دودویی و گراف آستانه برای مقدار آستانه ۵.
شکل ۲-۴. گراف‌های آستانه برای ماتریس
۲-۲-۱-۱-۲. الگوریتم پیوندی منفرد
این الگوریتم روش کمینه و روش نزدیک‌ترین همسایه نیز نامیده می‌شود [۲۶]. اگر و خوشه‌ها باشند، در روش پیوندی منفرد، فاصله آن‌ها برابر خواهد بود با:
(۲-۲)
که نشان‌دهنده فاصله (عدم شباهت) بین نقاط a و b در ماتریس مجاورت است. شکل ۲-۵ این الگوریتم را نمایش می‌دهد. شکل ۲-۶ دندوگرام حاصل از روش پیوندی منفرد را برای ماتریس ، را نشان می‌دهد.

Step 1. Begin with the disjoint clustering implied by threshold graph , which contains no edges and which places every object in a unique cluster, as the current clustering. Set .
Step 2. From threshold graph .
If the number of comonents (maximally connected subgraphs) in , is less than the number of clusters in the current clustering, redefiene the current clustering by naming each component of as a cluster.
Step 3. If consists of a single connected graph, stop. Else, set and go to step 2.

شکل ۲-۵. الگوریتم خوشه‌بندی سلسله مراتبی تراکمی پیوندی منفرد
شکل ۲-۶. دندوگرام پیوندی منفرد برای ماتریس
۲-۲-۱-۱-۳. الگوریتم پیوندی کامل
این الگوریتم روش بیشینه یا روش دورترین همسایه نیز نامیده می‌شود. الگوریتم پیوندی کامل می‌گوید که وقتی دو خوشه و شبیه به هم هستند که بیشینه روی تمام ها در و کوچک باشد. به عبارت دیگر، در این الگوریتم، برای یکی کردن دو خوشه، همه جفت‌ها در دو خوشه باید شبیه به هم باشند [۲۶]. اگر و خوشه‌ها باشند، در روش پیوندی کامل، فاصله آن‌ها برابر خواهد بود با:
(۲-۳)
که نشان‌دهنده فاصله(عدم شباهت) بین نقاط a و در ماتریس مجاورت است. شکل ۲-۷ این الگوریتم و شکل ۲-۸ دندوگرام حاصل از این روش را برای ماتریس ، را نشان می‌دهد.

Step 1. Begin with the disjoint clustering implied by threshold graph , which contains no edges and which places every object in a unique cluster, as the current clustering. Set .
Step 2. From threshold graph .
If two of the current clusters from a clique (maximally complete sub graph) in , redefine the current clustering by merging these two clusters into a single cluster.
Step 3. If , so that is the complete graph on the nodes, stop. Else, set and go to step 2.