سلسله مراتبی و سلسله مراتب

دانلود پایان نامه

الگوریتم های خوشه بندی
مهم ترین روش های خوشه بندی به شرح ذیل می باشند(مرشدلو، 1386):
روش افرازی ( تقسیم بندی)
روش سلسله مراتبی
روش مبتنی بر چگالی
روش مبتنی بر مشبک کردن فضا
روش مبتنی بر مدل
روش افرازی ( تقسیم بندی)
روش های خوشه بندی که به روش تقسیم بندی عمل می کنند، داده های موجود در یک مجوعه داده را به K خوشه تقسیم می کنند، به طوری که هر خوشه 2 خصوصیت زیر را داراست:
هر خوشه یا گروه حداقل شامل یک داده باشد.
هر داده موجود در مجموعه داده دقیقاً به یک گروه یا خوشه تعلق دارد.
معیار اصلی در چنین مجموعه داده هایی میزان شباهت داده های قرار گرفته در هر خوشه می باشد. در حالی که داده های قرار گرفته در دو خوشه مختلف از نظر شباهت با یکدیگر فاصله زیادی دارند. مقدار K که به عنوان پارامتر استفاده می گردد، هم می تواند به صورت پویا تعیین گردد و هم می توان قبل از شروع الگوریتم خوشه بندی مقدار آن را مشخص کرد.
برای دست یابی به خوشه بندی بهینه به شمارش همه افرازهای ممکن نیاز خواهد بود. یعنی تمام حالات ممکن باید بررسی شوند که این روش برای پایگاه داده های بزرگ ناممکن است. معمولا از یکی از الگوریتم های K-means یا K-medoids استفاده می شود در الگوریتم K-means هر خوشه با میانگین اشیا آن خوشه (مرکز خوشه) و در الگوریتم K-medoids با یکی از اشیا که در نزدیکی مرکز خوشه جای گرفته است، نشان داده می شود.
الگوریتم K-means
الگوریتم K-means یکی از پرکاربردترین الگوریتم های خوشه بندی می باشد(شهرابی، 1390). این الگوریتم K ( تعداد خوشه ها) را به عنوان ورودی می گیرد و مجموعه n شی را به K خوشه افراز می کند، به صورتی که سطح شباهت داخلی خوشه ها را بالا برده و سطح شباهت اشیا بین خوشه ها را کاهش دهد.
روش کار در این الگوریتم بدین صورت است:
به صورت تصادفی K شی را به عنوان مراکز خوشه هایی ابتدایی انتخاب می کند.
هر شی را با توجه به بیشترین شباهت آن به مراکز خوشه ها، به خوشه ها تخصیص می دهد.
مراکز خوشه ها را به روز می کند. به این معنی که برای هر خوشه مقدار متوسط اشیا آن خوشه را محاسبه می نماید.
تا هنگامی که هیچ تغییری در خوشه ها رخ ندهد به مرحله 2 رجوع می کند.
روش های سلسله مراتبی
روش های سلسله مراتبی به دو دسته کلی: روش های Bottom-up و روش های Top-down تقسیم می شوند. روش های سلسله مراتبی Bottom-up به این صورت عمل می کنند که در شروع، هر کدام از داده ها را در یک خوشه جداگانه قرار می دهد و در طول اجرا سعی می کند تا خوشه هایی نزدیک به یکدیگر را با هم ادغام نماید. این عمل ادغام تا زمانی که تنها یک خوشه داشته باشیم و یا این که شرط خاتمه برقرار گردد، ادامه می یابد. روش های Top-down دقیقاً به طریقه ی عکس عمل می نمایند، به این طریق که ابتدا تمام داده ها را در یک خوشه قرار می دهند و در هر تکرار از الگوریتم، هر خوشه به خوشه های کوچکتر شکسته می شود و این کار تا زمانی ادامه می یابد که یا هر کدام از خوشه ها تنها شامل یک داده باشند و یا شرط خاتمه الگوریتم برقرار گردد. شرط خاتمه معمولا تعداد کلاستر یا خوشه می باشد.
روش های مبتنی بر چگالی
اکثر روش های خوشه بندی که به روش تقسیم بندی عمل می کنند، معمولاً از تابع فاصله به عنوان تابع معیار خود بهره می برند. استفاده از چنین معیاری باعث می گردد که الگوریتم خوشه بندی تنها قادر به ایجاد خوشه هایی با اشکال منظم باشد. در صورتی که اگر خوشه های واقعی در داده ها دارای اشکال غیر منظمی باشند، این الگوریتم ها در خوشه بندی آن ها با مشکل مواجه می گردند. برای حل این گونه مشکلات، یک سری از روش های خوشه بندی پیشنهاد گردیده اند که عمل خوشه بندی را بر مبنای چگالی داده ها انجام می مدهند. ایده اصلی در این روش ها بر این اساس است که خوشه ها تا زمانی که داده های قرار گرفته درهمسایگی خوشه ها از حد معینی بیشتر باشد، رشد می کنند و بزرگ می شوند. چنین روش هایی قادرند خوشه هایی با شکل های نامنظم نیز ایجاد نمایند.
البته دسته دیگری از روش های خوشه بندی مانند روش های مبتنی بر مشبک کردن فضا، روش های مبتنی بر مدل و … نیز وجود دارند که در این تحقیق مورد بررسی قرار نگرفته اند.
الگوریتم های وابستگی قواعد