نسبت دادن هر نمونه داده به یک خوشه که آن داده کمترین فاصله تا مرکز آن خوشه را دارا باشد.
الگوریتم K میانگین به عنوان یادگیری بدون نظارت است که تعداد خوشه‌ها از قبل تعیین نشده‌اند و خوشه‌ها با یکدیگر فصل مشترکی ندارند‌. مقدارهای اولیه متفاوت برای الگوریتم K میانگین، می‌تواند منجر به خوشه‌بندی‌های مختلفی شود. به خاطر اینکه، این الگوریتم مبتنی بر فاصله اقلیدسی است، می‌تواند به مینیمم محلی^[۵] همگرا شود. معمولاً برای خوشه‌هایی که به طور خیلی خوب از هم تفکیک نمی‌شوند، این امر صادق است. نشان داده شده است که هیچ تضمینی برای همگرایی یک الگوریتم تکراری به یک بهینه سراسری نیست [۱۲]. سرعت همگرائی بالا از مهمترین مزیت این الگوریتم است، اما روالی مشخص برای محاسبه اولیه مراکز خوشه‌ها وجود ندارد و اگر در تکراری از الگوریتم، تعداد داده‌های متعلق به خوشه‌ای صفر شد راهی برای تغییر و بهبود ادامه روش وجود ندارد.
(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))

به طور خلاصه می‌توان ویژگی‌های الگوریتم K میانگین را به صورت زیر بر شمرد:
بر اساس فاصله اقلیدسی تمامی ویژگی‌ها محاسبه می‌شود.
منجر به تولید خوشه‌هایی به صورت دایره، کره و یا ابر کره می‌شود.
نسبت به روش‌های دیگر خوشه‌بندی، ساده و سریع است.
مشکل بزرگی که خوشه‌بندی K میانگین را تهدید می‌کند، همگرایی آن به یک بهینه محلی می‌باشد، اما تضمینی برای همگرایی به بهینه سراسری وجود ندارد.
نسبت به مقدار دهی اولیه مراکز خوشه‌ها خیلی حساس است.
حساسیت شدیدی به داده‌های دور افتاده دارد که باعث کاهش کارایی الگوریتم می‌شود.
۱-۲-۲ روش کار خوشه‌بندی فازی
در فلوچارت زیر روند کلی کار آمده است:
انتخاب تعداد خوشه‌ها و تولید ماتریس عضویت اولیه
محاسبه مراکز خوشه‌ها
محاسبه تابع هدف
بروز رسانی ماتریس عضویت
بررسی شرط توقف
تعیین خوشه‌های بهینه
شکل ۱-۴ : روش کار خوشه‌بندی فازی[۶]
در این الگوریتم تعداد خوشه‌هااز قبل مشخص شده است. تابع هدفی که برای این الگوریتم تعریف شده است بصورت زیر می باشد[۷]:
J=(1-5)
در فرمول فوق m یک عدد حقیقی بزرگتر از ۱ است که در اکثر موارد برای m عدد ۲ انتخاب می‌شود. X_{k ­} نمونه k ام است و V_i نماینده یا مرکز خوشه i ام است. U_ik میزان تعلق نمونه i ام در خوشه k ام را نشان می‌دهد. از روی U_ik می‌توان یک ماتریس U تعریف کرد که دارای c سطر و n ستون می‌باشد و مولفه‌های آن هر مقداری بین ۰ تا ۱ را می‌توانند اختیار کنند. اگر تمامی مولفه‌های ماتریس U بصورت ۰ و یا ۱ باشند الگوریتم مشابه c میانگین کلاسیک خواهد بود. با اینکه مولفه‌های ماتریس U می‌توانند هر مقداری بین ۰ تا ۱ را اختیار کنند اما مجموع مولفه‌های هر یک از ستونها باید برابر ۱ باشد و داریم:
(۱-۶)
معنای این شرط این است که مجموع تعلق هر نمونه به c خوشه باید برابر ۱ باشد. با بهره گرفتن از شرط فوق و مینیمم کردن تابع هدف خواهیم داشت:
(۱-۷)
و همچنین برای داریم:
(۱-۸)
مراحل الگوریتم:
مقداردهی اولیه برای c، m و U⁰. خوشه‌های اولیه حدس زده شوند.
مراکز خوشه‌ها محاسبه شوند (محاسبه v_iها).
محاسبه ماتریس تعلق از روی خوشه‌های محاسبه شده در ۲٫
اگر Ul1Ul الگوریتم خاتمه می‌یابد و در غیر اینصورت برو به مرحله ۲٫
خوشه‌بندی تفاضلی
در مواقعی که دیدگاه واضحی از تعداد خوشه‌هایی که بایستی برای مجموعه داده‌ای مشخص شود، وجود نداشته باشد این الگوریتم روشی سریع برای یافتن تعداد خوشه‌ها و همچنین مراکز آنها محسوب می‌شود.
گاهی اوقات مراکزی که توسط این روش تخمین زده شده‌اند به عنوان نقاط اولیه برای دیگر الگوریتم‌های خوشه‌بندی مورد استفاده قرار می‌گیرند. این تکنیک از آن جهت بکار گرفته شده است که بتواند نقاط کلیدی یا نمونه‌های متمایز را از میان انبوهی از رکوردهای مجموعه داده‌ها که هر رکورد حاوی ویژگی‌های یک نقطه کلیدی است، استخراج نماید.
خوشه‌بندی تفاضلی در اصل یک فرم تغییر یافته از روش Mountain است[۹] . در الگوریتم هر نقطه به عنوان یک پتانسیل برای مرکز خوشه در نظر گرفته می‌شود که اندازه‌گیری پتانسیل طبق معادله (۱-۹) بدست می‌آید این روش می‌تواند هم به عنوان روش مستقل برای خوشه‌بندی استفاده شود و هم می‌تواند به عنوان پیش‌پردازشی برای الگوریتم‌های خوشه‌بندی دیگر مطرح گردد.( در این مورد می‌توانیم در روند کار تصمیم بگیریم)
مراحل الگوریتم به صورت زیر مطرح است:
مجموعه‌ای از n داده در فضای M بعدی را در نظر بگیرید. هر نقطه از این مجموعه به عنوان کاندید مراکز خوشه‌ها، اندازه‌ی چگالی در نقاط داده‌ی به صورت زیر محاسبه می‌شود:
(۱-۹)
یک عدد ثابت مثبت است که شعاع همسایگی را مشخص می‌کند. از این رو یک نقطه از داده‌ها مقدار چگالی بالا خواهد داشت اگر تعداد نقاط زیادی در همسایگی داشته باشد.
اولین مرکز خوشه به عنوان نقطه‌ای که بیشترین مقدار چگالی انتخاب می‌شود. سپس، مقدار چگالی هر نقطه به صورت زیر ارزیابی مجدد می‌شود:
(۱-۱۰)
پس از محاسبه مجدد چگالی برای هر نقطه از داده‌ها مرکز بعدی انتخاب می‌شود و دوباره همه‌ی محاسبات برای چگالی نقاط داده‌ها اصلاح می‌شود. این روند تا زمانی ادامه می‌یابد که تعداد کافی از نقاط مراکز خوشه‌ها تولید گردد. خروجی خوشه‌بندی کاهشی، یک سیستم استنتاج فازی سوگنو می‌باشد.

ماشین بردار پشتیبان
یکی از روش‌هایی که در حال حاضر به صورت گسترده‌ای برای مسئله دسته‌بندی مورد استفاده قرار می‌گیرد، روش ماشین بردار پشتیبان (SVM) است. اولین الگوریتم برای طبقه‌بندی و دسته‌بندی الگوها در سال ۱۹۳۶ توسط Fisher ارائه شد و معیار آن برای بهینه بودن ، کم کردن خطای طبقه‌بندی الگوهای آموزشی بوده است . بسیاری از الگوریتم‌ها و روشهایی نیز که تاکنون برای طراحی طبقه‌بندی کننده های الگو ارائه شده است ، از همین استراتژی پیروی می کنند.[۱۰]
محقق روسی بنام Vladimir Vapnilk در سال ۱۹۶۵ گامی بسیار مهم در طراحی دسته‌بندی کننده‌ها برداشت [۱۱] و نظریه آماری یادگیری را بصورت مستحکم تری بنا نهاد و ماشین‌های بردار پشتیبان را بر این اساس ارائه داد .
۱-۴-۱ روش کار ماشین بردار پشتیبان
فرض کنید تعدادی از بردارهای ویژگی یا الگوهای آموزشی بصورت {x_1,x₂,…,x_N} داریم که هر کدام یک بردار ویژگی d بعدی بوده و دارای برچسب y_i است و y_i .
هدف حل یک مسأله دسته بندی دو کلاسه بصورت بهینه است . فرض کنید این دو کلاس را با تابع تمایز f(x) با یک ابر صفحه H با معادله زیر بخواهیم از هم جدا کنیم:
(۱-۱۱) H: w.x+b=0