| (۱-۱۱) | |
پس از حل مسئله بهینهسازی بالا و یافتن ضرایب لاگرانژ، w با بهره گرفتن از رابطه زیر محاسبه میشود.
(۱-۱۲)
بردارهای پشتیبان بزرگتر از صفر و نقاط دیگر صفر خواهد بود. بنابراین با توجه به فرمول (۱-۱۲) و صفر بودن مربوط به هایی که بردار پشتیبان نیستند، برای بهدست آوردن مرز تصمیمگیری فقط نیاز به تعداد محدودی از نقاط آموزشی که همان بردارهای پشتیبان هستند میباشد و همه آنها لازم نیستند.
(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))
در نتیجه طبقهبندی تصاویر با بهره گرفتن از ماشین بردار پشتیبان به تعداد محدودی نقطه آموزشی نیاز خواهد داشت. پس از یافتن w با بهره گرفتن از رابطه زیر مقدار b بهازای بردارهای پشتیبان مختلف محاسبه شده و b نهایی با میانگینگیری از bهای حاصل بهدست میآید.
(۱-۱۳)
طبقهبندیکننده نهایی از (۱-۱۳) بهدست میآید.
(۱-۱۴)
۱-۲-۹-خوشه بندی سلسله مراتبی[۲۴]
خوشهبندی سلسلهمراتبی تکنیکی است که در گروهبندی یا دستهبندی دادهها بهکار میرود [۹]. نقاط دادهها در این روش در دسته ها و زیردستههایی براساس معیار شباهت قرار میگیرند. در روش خوشهبندی سلسلهمراتبی، به خوشههای نهایی براساس میزان عمومیت آنها ساختاری سلسله مراتبی، معمولا بهصورت درختی نسبت داده میشود.
عملکرد خوشهبندی سلسله مراتبی با بهره گرفتن از مجموعه دادههای دوبعدی در شکل (۱-۵) نشان داده شدهاست. این شکل، هفت الگو با برچسبهای A، B، C، D، E، F و G را درون سه خوشه نشان میدهد.
شکل(۱-۵) ساختار درختی بهدست آمده بهوسیله الگوریتم تک پیوندی[۹]
الگوریتمهای سلسله مراتبی، الگوها را با یک ساختار درختگونه و گروهبندیهای تودرتو نمایش میدهند. شکل (۱-۵) یک ساختار درختگونه برای نمونههای موجود توسط الگوریتم تکپیوندی را نمایش میدهد. میتوان برای بهدست آوردن خوشهبندیهای متفاوت، این درخت را به سطوح مختلف شکست.
روش کار تکنیکهای خوشهبندی سلسلهمراتبی معمولا براساس الگوریتمهای حریصانه[۲۵] و بهینگی مرحلهای[۲۶] است. روشهای خوشهبندی بر اساس ساختار سلسله مراتبی ایجاد شده توسط آنها معمولا به دو دسته زیر تقسیم میشوند، بالا به پایین[۲۷] یا تقسیم کننده یا پایین به بالا[۲۸] یا متراکم شونده.
۱-۲-۹-۱-بالا به پایین یا تقسیم کننده
در این روش ابتدا تمام دادهها بهعنوان یک خوشه در نظر گرفته میشوند و سپس در طی یک فرایند تکراری در هر مرحله دادههایی که شباهت کمتری بههم دارند به خوشههای مجزایی شکسته میشوند و این روال تا رسیدن به خوشههایی که دارای یک عضو هستند ادامه پیدا میکند [۱۰].
۱-۲-۹-۲-پایین به بالا یا متراکم شونده[۲۹]
در این روش ابتدا هر داده بهعنوان خوشهای مجزا در نظر گرفته میشود و در طی فرآیندی تکراری در هر مرحله خوشههایی که شباهت بیشتری با یکدیگر دارند، ترکیب میشوند تا در نهایت یک خوشه و یا تعداد مشخصی خوشه حاصل شود. اکثر الگوریتمهای سلسله مراتبی، گونههای مختلفی از الگوریتمهای تک پیوندی[۳۰] [۱۱]، پیوند کامل[۳۱] [۱۲] و کمترین واریانس[۳۲] [۱۳] و [۱۴] هستند. الگوریتمهای تک پیوندی و پیوند کامل رایجتر از گونه دیگر میباشند. تفاوت میان این دو روش در تعریف میان این دو روش از تابع شباهت میان یک زوج الگو است. در روش تکپیوندی، فاصله میان دو خوشه، کمترین فاصله میان تمام زوج نمونههای ممکن از آن دو خوشه میباشد ( یک نمونه از خوشه اول و دیگری از خوشه دوم). در مقابل در روش پیوند کامل، فاصله میان دو خوشه براساس بیشترین فاصله میان زوج نمونههای دو خوشه تعیین میشود. الگوریتم پیوند کامل خوشههای متراکم و با کرانهای مشخص [۱۵] و الگوریتم تک پیوندی خوشههای پراکنده و کشیدهای را تولید میکند. شکلهای (۱-۶) و (۱-۷) دو خوشه را نشان میدهند که نمونههای آن توسط یک پل از نمونههای دارای نویز از یکدیگر جدا شدهاند.
شکل(۱-۶) یک خوشهبندی تکپیوندی از نمونههایی با برچسبهای ۱و۲ که بهوسیله نمونههای دارای نویز(*) از یکدیگر جدا شدهاند [۱۶].
شکل (۱-۷) یک خوشهبندی پیوند کامل از نمونههایی با برچسبهای ۱و۲ که بهوسیله نمونههای دارای نویز * از یکدیگر جدا شدهاند[۱۶].
خوشهبندی موجود در شکل (۱-۶) بهوسیله الگوریتم تکپیوندی و خوشهبندی موجود در شکل (۱-۷) نیز توسط الگوریتم پیوند کامل تولید شدهاند.
۱-۲-۹-۳-خوشهبندی جمع شونده در مقابل تقسیم شونده[۳۳]
در این دیدگاه، عملکرد و ساختار الگوریتمی تکنیکها بیان میگردد [۱۷]. یک روش جمع شونده، عمل خوشهبندی را با خوشههای حاوی تنها یک نمونه آغاز کرده و در هر مرحله خوشهها را با یکدیگر ترکیب میکند تا جاییکه الگوریتم خاتمه یابد. در مقابل روش تقسیم شونده، عمل خوشهبندی را با یک خوشه حاوی تمام نمونهها آغاز کرده و در ادامه با تقسیم خوشهها کار را تا جایی ادامه میدهد که در هر خوشه تنها یک نمونه قرار گیرد.
۱-۲-۹-۴-روشهای سلسله مراتبی در مقابل روشهای غیر سلسله مراتبی
در روشهای سلسله مراتبی خوشهها بهشکل سلسله مراتبی از خوشههای بزرگ تا کوچک و یا برعکس از خوشههای کوچک تا بزرگ تعیین میشوند. بهعبارت دیگر در این روشها نقاط در یک خوشه قرار میگیرند که خود این خوشه نیز به خوشههای دیگری تقسیم میشود [۱۸]. در روشهای غیر سلسله مراتبی نقاط بهطور مستقیم در خوشههای متفاوتی قرار میگیرند. یکی از مزیتهای روشهای سلسله مراتبی این است که در هر سطح از سلسله مراتب میتوان اطلاعات مشخصی را استخراج کرد.
۱-۲-۱۰-خوشهبندی افرازبندی
الگوریتمهای خوشهبندی افرازبندی بر خلاف روشهای سلسله مراتبی که یک ساختار خوشهبندی را ارائه میکنند، یک تقسیمبندی تنها از دادهها را نمایش میدهند. روشهای افرازبندی در محیطهایی با مجموعه دادههای بزرگ که تقریبا غیر ممکن میباشند، ترجیح داده میشوند. یکی از مشکلات پیش روی روشهای افرازبندی، انتخاب تعداد خوشهها برای دادهها میباشد [۱۹]. روشهای افرازبندی معمولا از طریق بهینهسازی یک تابع هدف به یکی از دو شکل محلی (روی زیر مجموعهای از الگوها) یا سراسری (روی تمام مجموعه داده)، خوشههای نهایی را تولید میکنند. ترکیبهای مختلف از مجموعه داده برای رسیدن به یک مقدار بهینه برای تابع هدف از نظر محاسباتی غیرممکن است. از این رو در واقعیت، الگوریتمها با مقداردهیهای اولیه مختلفی اجرا میشوند و در نهایت بهترین ترکیب بهدست آمده از این اجراها بهعنوان خوشهبندی نهایی در نظر گرفته میشود.
۱-۲-۱۱- الگوریتم [۳۴]BIRCH
ژانگ درسال ۱۹۹۶ یک الگوریتم سلسلهمراتبی تجمیعی بهنام BIRCH (خوشهبندی و کاهش تکراری متوازن با سلسله مراتبها) برای خوشهبندی مجموعه دادههای شمارشی خیلی بزرگ در فضاهای اقلیدسی پیشنهاد کرد [۲۰]. این الگوریتم اولین الگوریتم خوشهبندی در ناحیه پایگاه داده نیز هست و اولین الگوریتم خوشهبندیی است که به نویز نیز توجه کرده است معماری BIRCH بهگونهای است که در آن موازی سازی نیز امکانپذیر است.
مزیت مهم BIRCH، مناسب بودن آن برای مجموعه دادههای خیلی بزرگ میباشد. این الگوریتم با ایجاد محدودیتهایی در زمان و حافظه، برای مجموعه دادههای خیلی بزرگ قابل استفاده میشود. الگوریتم BIRCH بهصورت محلی انجام می شود و در آن خوشهبندی بدون بررسی تمام نقاط داده و خوشههای موجود انجام میشود و بهاین منظور از مقیاسهایی که نزدیکی نقاط را نشان میدهند استفاده میکند.
BIRCH از حافظه موجود بهطور کامل استفاده میکند و از آن طریق بهترین خوشههای ممکن را ایجاد میکند و هزینه I/O را بهمنظور تضمین کارایی مینیمم میسازد.
در الگوریتم BIRCH از یک بردار ویژگی خوشهبندی[۳۵] برای خلاصه کردن اطلاعات هر خوشه استفاده میشود. درآغاز یک درخت CF با ورود دادههای جدید بهصورت پویا ساخته میشود. بعد از اینکه درخت CF ساخته شد یک الگوریتم خوشهبندی سلسله مراتبی تجمیعی بهطور مستقیم بهکار گرفته میشود تا گرهها را با بردارهای CF آنها نمایش دهد. سپس برای هر خوشه یک مرکز ثقل در نظر گرفته میشود. سرانجام یک مجموعه خوشه جدید با توزیع دوباره هر نقطه داده با نزدیکترین مرکز ثقل خود تشکیل میشود.
وقتی خوشهها محدب یا شکل کروی و سایز همشکل دارند الگوریتم BIRCH خوب کار میکند، ولی وقتی خوشهها اندازههای متفاوت یا شکلهای غیرکروی دارند، استفاده از این الگوریتم مناسب نیست. مزایای اصلی BIRCH دولایه بودن، توانایی برخورد با مجموعه دادههای مقیاس بزرگ و قدرت دور از مرکز بودن است.
۱-۲-۱۰-روش خوشهبندی K-means
این روش علیرغم سادگی آن یک روش پایه برای بسیاری از روشهای خوشهبندی دیگر (مانند خوشهبندی فازی) محسوب میشود. این روش، روشی انحصاری و مسطح محسوب میشود. برای این الگوریتم شکلهای مختلفی بیان شدهاست. ولی همهی آنها دارای روالی تکراری هستند که برای تعدادی ثابت از خوشهها سعی در تخمین موارد زیر دارند:
بهدست آوردن نقاطی بهعنوان مراکز خوشهها که این نقاط در واقع همان میانگین نقاط متعلق به هر خوشه هستند. نسبت دادن هر نمونه داده به یک خوشه که آن داده کمترین فاصله تا مرکز آن خوشه را دارا باشد.
