1) چکیده:
در این تمرین روش های استخراج ویژگی و روش های خطی و غیر خطی دسته بندی را مورد مطالعه قرار می‌دهیم. در ابتدا روش های مختلف استخراج ویژگی که از آن جمله PCA، LDA، روش قاب بندی و چند روش دیگر هستند را و سپس برای ویژگی های استخراج شده از روش های دسته بندی خطی بیزین و SVM خطی و سپس روش های غیرخطی RBF ، MLP و همچنین SVM غیرخطی برای دسته بندی استفاده شده است. بسته به روش شناسایی بکار گرفته شده، معمولا ویژگی های متفاوتی از دنباله نقاط استخراج می شود. در اکثر روش های موجود استخراج ویژگی، ویژگی ها از روی مختصات نقاط نمونه برداری شده ورودی استخراج می شوند. از مجموعه ی ویژگی های استخراج شده معمولاً تعدادی مفید تر و موثرترند. ما برای تشخیص و انتخاب ویژگی های تاثیرگذارتر از یک الگوریتم ژنتیک استفاده کرده ایم. اما پس از استخراج و انتخاب ویژگی ها نوبت به دسته بندی می رسد. در ابتدا از چند دسته بند خطی استفاده کرده ایم. به راحتی می‌توان نشان داد که ناحیه‌های تصمیم‌گیری یک ماشین خطی محدودند و این محدودیت انعطاف‌پذیری و دقت دسته‌بند را کاهش می‌دهد. مسایل بسیاری وجود دارد که توابع جداساز خطی برای داشتن حداقل خطا در آنها کافی نیستند. علاوه بر این مرزهای تصمیم‌گیری که کلاسها را از یکدیگر تفکیک می‌کنند ممکن است همیشه خطی نباشند و پیچیدگی مرزها گاهی اوقات نیاز به استفاده از سطح‌های کاملاً غیر خطی را دارند. بنابراین در ادامه ی کار از چند دسته بند غیرخطی نیز استفاده نمودیم. در استفاده از شبکههای عصبی چندلایه، شکل غیر خطی بودن از مجموعه‌ی آموزش فرا گرفته می‌شود. در روشهای RBF و SVM غیرخطی مشکل اصلی انتخاب توابع هسته غیر خطی مناسب است.
2) مقدمه
اولین الگوریتم دسته‌بندی در سال 1936 توسط Fisher ارایه شد و معیارهای آن برای بهینه بودن، کم کردن خطای دسته‌بندی کننده‌های الگوهای آموزشی بود. بسیاری از استراتژی‌های موجود نیز از همین روش پیروی می‌کنند. در ساده‌ترین شکل ممکن، دسته بند‌های خطی می‌توانند دو دسته‌ی متفاوت را تفکیک کنند. با توجه به این موضوع مساله‌ای را جدایی‌پذیر خطی می‌نامند که با یک ابرصفحه بتوان محدوده‌ی تصمیم را به دو گروه تقسیم‌بندی کرد. در عمل می‌توان دسته بند‌های خطی‌ای را طراحی کرد که بیش از دو گروه را از هم تفکیک کنند. این عمل را با تنظیم محدوده‌های تصمیم متعدد و آزمون‌های چندگانه بر اساس شرایط موجود می‌توان انجام داد. ما در این مساله یک دسته بندی با 26 کلاس را داریم.
در روش بیزین احتمال شرطی تعلق بررسی می‌شود. به این ترتیب که الگوی مورد نظر به دسته‌ای تخصیص داده می‌شود که احتمال شرطی تعلق بردار مشخصه‌ی الگو به آن دسته ازتمام دسته‌های دیگر بیشتر باشد. روش بیزین به طور کلی می تواند برای کارایی بسیار مطلوب بهینه شوند. این روش مزایای دیگری نیز دارد که استفاده‌ی از آن را توجیه می‌کند. این روش می‌تواند با چند فرض ساده در مورد داده‌ها کاملاً به شکل روشهای ساده‌ی خطی عمل کند، به علاوه این کار می‌تواند به گونه‌ای انجام شود که در پایان، مدل قطعی بدون هیچ گونه رجوع به آمار به دست آید. در روش بیزین مشکل کار تعریف احتمالات شرطی مورد نظر قاعده‌ی بیز است.
یک محقق روسی به نام Vladimir Vapnik در سال 1965 گام مهمی در طراحی دسته‌بندها برداشت [1] و نظریه‌ی آماری یادگیری را بصورت مستحکم‌تری بنا نهاد و ماشین بردار پشتیبان را ارایه کرد. ماشین‌های بردار پشتیبان در دو حالت جدایی‌پذیر و جدایی‌ناپذیر برای دسته‌بندی الگوهای یک مساله‌ی چندکلاسه از چند مرز جداکننده‌ی خطی یا ابرصفحه استفاده می‌کنند و در واقع حاصلضرب داخلی بردار ورودی با هر یک از بردارهای پشتیبان در فضای d بعدی ورودی محاسبه می‌شود. Vapnik نشان داد که می‌توان بردار ورودی را با یک تبدیل غیرخطی به یک فضای با بعد زیاد انتقال داد و در آن فضا حاصلضرب داخلی را بدست آورد که با این شرایط هسته‌ی مفیدی را خواهیم داشت.
روش RBF یک دسته‌بندی و تقریب‌ساز تابعی الگوست و شامل دو لایه میباشد که نرون‌های خروجی ترکیبی خطی از توابع پایه‌ای را به وجود می‌آورند که توسط نرون‌های لایه‌ی پنهان محاسبه شده‌اند. زمانی که ورودی در ناحیه‌ی تعیین شده‌ی کوچک از فضای ورودی قرار گیرد، توابع اساسی(غیر خطی) در لایه‌ی پنهان، پاسخ غیر صفری به محرک ورودی می‌دهند. همچنین این مدل به عنوان یک شبکه‌ی دریافت‌کننده‌ی ناحیه‌ای شناخته شده است. ما در روش RBF از معمول‌ترین تابع هسته‌ی غیر خطی یعنی سیگموئید استفاده کرده‌ایم.
به طور کلی شبکههای پرسپترون چندلایه شامل چندین پرسپترون ساده هستند که به طور ساختار سلسله‌مراتبی، یک شکل پیش‌خورد با یک و یا چند لایه‌ی میانی (لایه‌های پنهان) بین لایه‌های ورودی و خروجی را شکل می‌دهد. تعداد لایه‌ی پنهان و تعداد نرون‌های هر لایه ثابت نیستند. هر لایه ممکن است از نرون‌های مختلفی تشکیل شده باشد که این موضوع به کار آنها بستگی دارد. الگوریتم‌های آموزشی متفاوتی در روش چند لایه استفاده می‌شوند.
3) روشهای به کار رفته در این گزارش
در این قسمت روشهای استخراج ویژگی، روشهای انتخاب ویژگی ها جهت بهینه کردن آنها و کم کردن ابعاد مساله با کاهش تعداد آنها و روشهای دسته‌بندی (خطی و غیرخطی) به کار رفته بررسی شده‌اند.
3-1) روشهای استخراج ویژگی
در این قسمت انواع روشهای استخراج ویژگی ها ذکر شده است. ذکر این نکته لازم است که برخی الگوریتم های استخراج برای انتخاب ویژگی های موثر نیز استفاده می شوند ازجمله ی آنها PCA و LDA هستند. اما در این گزارش ما برای بهینه کردن ویژگی ها و کم کردن تعداد آنها و یا به عبارت دیگر برای کاهش ابعاد (Curse of Dimensionality) از الگوریتم ژنتیک استفاده نموده ایم.
3-1-1) روش PCA خطی
روشهای استخراج ویژگی یک زیرفضای مناسب m بعدی در فضای اصلی ویژگی ها از d بعد را تعیین می کنند(m<=d). تبدیل خطی مثل PCA، آنالیز فاکتور، LDA و تعقیب تصویر بطور گسترده در شناسایی الگو برای استخراج ویژگی ها و کاهش ابعاد استفاده شده اند. بهترین استخراج کننده ی ویژگی شناخته شدهPCA یا توسعه یافته ی Karhunen-loeve است که m بردار مشخصه بزرگتر را از ماتریس کوواریانس d×d از n الگوی d بعدی محاسبه می کند. تبدیل خطی به شکل Y=XH تعریف شده است که X ماتریس الگوی n×d داده شده و Y از ماتریس الگوی n×m مشتق شده است . H ماتریس d×m از تبدیل خطی است که ستون های آن بردارهای مشخصه هستند. قبل از اینکه PCA از ویژگی های پرمعنی تر استفاده کند (بردار ویژگی های با بزرگترین مقدار ویژه)، بطور کاملاً موثر داده ها را با یک زیرفضای خطی با استفاده از معیار خطای میانگین مربعات تخمین می زند. سایر روش ها مانندتعقیب تصویر و ICA برای توزیع های غیرگاوسی تا وقتی که به مشخصه ی مرتبه ی دوم داده ها مربوط نباشد مناسب ترند. ICA با موفقیت برای جداسازی منابع دیده نشده استفاده شده است. استخراج ترکیب خطی ویژگی ها منابع نابسته را تعریف می کند. این جداسازی در صورتی امکان پذیر است که حداکثر یکی از منابع دارای توزیع گاوسی باشد.
از آجا که PCA یک روش بدون بررسی استخراج ویژگی هاست (Unsupervised)، تحلیل جداسازی از یک اطلاعات گروهی در رابطه با هر الگو برای استخراج (خطی) ویژگی های با قابلیت جداسازی زیاد استفاده می کند. در LDA جداسازی بین کلاسی با جابجایی کل ماتریس کوواریانس در PCA با یک معیار جداسازی عمومی مانند معیار Fisher تائید می شود که در یافتن بردارهای مشخصه s_w^(-1) s_b^ نتیجه می شود.( حاصل معکوس ماتریس پراکندگی s_w^ و ماتریس پراکندگی بین کلاسی s_b^ ). معیار دیگر همراه با بررسی (Supervised) برای چگالی های شرایط کلاس غیرگاوسی بر پایه ی فاصله Patrick-Fisher با استفاده از برآورد چگالی Parzen است.
3-1-2) روش Kernel PCA (PCA با هسته یا PCA غیرخطی)
چندین روش برای تعریف روش های استخراج ویژگی غیرخطی وجود دارد. یکی از این روش ها که مستقیماً به PCA مربوط است، Kernel PCA نام دارد. ایده ی اصلی KPCA نگاشتن داده های ورودی بر روی برخی از فضاهای ویژگی F جدید بطور معمولی با استفاده از تابع غیرخطی ∅ و سپس اعمال یک PCA خطی در فضای نگاشت شده است. به هر حال فضایF معمولاً ابعاد بسیار زیادی دارد. برای دوری از محاسبات نگاشت ساده ی ∅، KPCA تنها هسته های Mercel که می توانند به یک نقطه تجزیه شوند را بکار می گیرد.
k(x,y)=∅(x).∅(y)
به عنوان یک نتیجه فضای هسته یک متریک با تعریف مناسب دارد. نمونه های هسته های Mercer شامل چندجمله ای های مرتبه P بصورت 〖(x-y)〗^p و هسته گاوسی هستند.
e^(〖-‖x-y‖〗^2/c)
فرض می کنیم که X یک ماتریس الگوی n×d نرمال شده با میانگین صفر است و ∅(x) یک ماتریس الگو در فضای F باشد. PCA خطی در فضای F بردارهای مشخصه ی ماتریس همبستگی ∅(x) 〖.∅(y)〗^T را حل می کند که همچنین ماتریس هسته K(X,X) نیز نامیده می شود. در KPCA در ابتدا m بردار ویژگی از K(X,X) بدست می آیند تا یک ماتریس انتقال E را تعریف کنند (E یک ماتریس n×m است که m تعداد ویژگی های دلخواه است و m<=d است). الگوهای جدید x با K(X,X).E نگاشت می شوند که اکنون با وابستگی به مجموعه آموزش بازنمایی می شوند و نه با مقادیر ویژگی ویژگی های اندازه گیری شده. باید توجه داشت که برای یک بازنمایی کامل تا m بردار مشخصه در E (بسته به تابع هسته) توسط KPCA ممکن است نیاز باشد در حالی که در PCA خطی یک مجموعه از d بردار مشخصه فضای اصلی ویژگی ها را ارائه می کند. انتخاب تابع هسته برای یک کاربرد مشخص هنوز یک مساله باز است.
3-1-3) روش مقیاس گذاری چندبعدی(MDS)
مقیاس گذاری چند بعدی (MDS)یک روش غیرخطی دیگر برای استخراج ویژگی هاست. هدف این روش بازنمایی یک مجموعه ی چندبعدی در دو یا سه بعد است مثل آنچه ماتریس فاصله در فضای اصلی ویژگی های d بعدی به طور کاملاً ثابت در فضای تصویرشده باقی مانده است. توابع تاکید فراوانی برای اندازه گیری کارایی این نگاشت استفاده شده اند. یک مشکل MDS این است که یک تابع نگاشت ساده و روشن را ارئه نمی کند بنابراین ممکن نیست که یک الگوی جدید را در یک نگاشت برای یک مجموعه ی آموزش مشخص بدون تکرار جایگذاری کند. چندین روش برای عنوان کردن این نقص که از درون یابی خطی تا آموزش شبکه عصبی محدود است مورد بررسی قرار گرفته است. همچنین امکان دارد که الگوریتم MDS مجدداً تعریف شود بنابراین مستقیماً یک نگاشت را تهیه می کند که ممکن است برای الگوهای آزمون جدید استفاده شود.
3-1-4) روش شبکه عصبی روبه جلو (Feed-Forward Neural Network)
یک شبکه ی عصبی روبه جلو یک روال جامع را برای استخراج ویژگی هاو دسته بندی پیشنهاد می کند. خروجی هر لایه ی مخفی ممکن است به عنوان یک مجموعه ی جدید و اغلب غیرخطی از ویژگی ها تعریف شود که در لایه ی مخفی برای دسته بندی ارائه می شوند. در این شرایط شبکه های استفاده شده توسط Fukushima و Lecun که اصطلاحاً آن را لایه های وزنی مشترک نامیده اند، در حقیقت فیلترهایی برای استخراج ویژگی ها در تصاویر دوبعدی هستند. در طول آموزش فیلترها با داده ها برای بیشینه کردن کارایی دسته بندی وفق داده شده اند.
شبکه های عصبی می توانند بطور مستقیم برای استخراج ویژگی ها در یک شکل بدون بررسی (Unsupervised) استفاده شوند. شکل (a-1) معماری یک شبکه که قادر به پیدا کردن زیرفضای PCA است را نشان می دهد. به جای سیگموئیدها نرون ها توابع انتقال خطی دارند. این شبکه d ورودی و d خروجی دارد که d تعداد مشخص شده ی ویژگی هاست. ورودی ها همچنین برای رسیدن به هدف نیز با مجبور کردن لایه ی خروجی به ساخت مجدد فضای ورودی تنها با استفاده از لایه ی مخفی بکار گرفته شده اند. سه گره در لایه ی مخفی اولین سه جزء اصلی را ضبط می کنند. اگر دو لایه ی غیرخطی با واحدهای مخفی سیگموئیدی نیز وجود داشته باشند ( شکل (b-4))، آنگاه یک زیرفضای غیرخطی در لایه ی میانی یافت خواهد شد (که همچنین لایه ی گلوگاه هم نامیده می شود). غیرخطی بودن توسط اندازه ی این لایه های اضافی محدود می شود. شبکه های PCA غیر خطی یا اصطلاحاً خودشرکت پذیرها ی ابزار قوی را برای آموزش و تشریح زیرفضای غیرخطی پیشنهاد می کند. محققی به نام Oja نشان داد که چگونه شبکه های خودشرکت پذیر می توانند برای ICA استفاده شوند.
شکل 1:شبکه های خودشرکت پذیر برای پیدا کردن یک زیرفضای سه بعدی. (a) خطی و (b) غیرخطی (تمام اتصالات نشان داده نشده اند).
3-1-5) روش نگاشت خودسازمانده (Self-Organizing Map)
روش نگاشت خودسازمانده ی(SOM) یا نگاشت Kohonen نیز می تواند به عنوان یک روش غیرخطی استخراج ویژگی ها استفاده شود. در SOM نرون ها در یک شبکه ی توری مانند m بعدی مرتب شده اند که m معمولاً 1، 2 و یا 3 می باشد.هر نرون به تمام d واحد ورودی متصل است. وزن ها بر روی اتصالات برای هر نرون از یک بردار وزن d بعدی گرفته شده اند. در طول مرحله ی آموزش الگوها با یک ترتیب تصادفی به شبکه ارائه می شوند. در هر ارائه، برنده که بردار وزنی نزدیک تری به بردار ورودی دارد به عنوان اولین مورد شناخته می شود. سپس تمام نرون ها در همسایگی برنده (که در شبکه تعریف شده اند) به روزرسانی می شوند که بردارهای وزن آنها به سمت ورودی حرکت می کند. در نتیجه پس از اتمام آموزش بردارهای وزنی نرون های همسایه در شبکه احتمالاً الگوهایی از ورودی که نزدیک تر به فضای اصلی ویژگی ها هستند را بازنمایی می کنند. بنابراین یک نگاشت محافظ وضعیت تشکیل می شود. زمانی که شبکه در فضای اصلی مطرح شد، اتصالات شبکه با توجه به چگالی داده های آموزشی می توانند بیشتر یا کمتر تحت فشار قرار گیرند. بنابراین SOM یک نقشه m بعدی با یک اتصال فضایی را پیشنهاد می کند که می تواند به عنوان یک استخراج کننده ی ویژگی تفسیر شود. SOM با LVQ متفاوت است چون در LVQ هیچ همسایه ای تعریف نمی شود.
3-1-6) استفاده از الگوریتم ژنتیک برای کاهش ابعاد مساله
همانطور که گفته خواهد شد از هر کاراکتر دست‌نویس 16 ویژگی استخراج شده است. در این سیستم با استفاده از الگوریتم ژنتیک از بین 16 ویژگی استخراج شده از تصویر کاراکتر، ویژگی‌های مناسب برای دسته‌بندی حروف انتخاب می‌شوند. برای این 16 ویژگی کروموزمی باینری به طول 16 تعریف شده است. یک بودن هر ژن به معنی استفاده و صفر بودن آن به معنی عدم استفاده از آن ویژگی در دسته‌بندی حروف است(شکل(2)). برای تشکیل جمعیت اولیه الگوریتم ژنتیک، کروموزوم‌های باینری به‌طور تصادفی تولید می‌شوند. سپس برای هر کروموزوم مقدار برازندگی آن با استفاده از تابع برازش محاسبه می‌شود که در ادامه نحوه محاسبه آن آورده خواهد شد. تابع برازش به فاصله صفر و یک نگاشت می‌شود. برای انتخاب والدین مناسب از روش چرخ رولت استفاده می‌شود.
شکل2: نمایش یک کروموزوم و نحوه‌ی انتخاب ویژگی‌ها
آمیزش با تولید یک عدد صحیح تصادفی بین 1 و 16 انجام می‌شود. جهش نیز با تولید یک عدد تصادفی بین 1و 16 و تغییر مقدار ژن از یک به صفر یا بالعکس انجام می‌شود. تولید نسل جدید با انتخاب 50 درصد از نسل قبلی به صورت تصادفی با روش چرخ رولت و 50 درصد با آمیزش بین والدین تصادفی از جمعیت قبل انجام می‌شود. سپس روی 15 درصد از این جمعیت به‌طور تصادفی جهش اعمال می‌شود. با اعمال الگوریتم ژنتیک در چند نسل و انتخاب کروموزوم با کمترین مقدار تابع برازش ویژگی‌های مناسب به‌دست میآیند.
همانطور که گفته شد روند اجرای الگوریتم ژنتیک خصوصاً برای این منظور خاص بسیار زمانبر میباشد. تصور کنید که بعد از تولید هر کروموزوم باید تابع برازش آن محاسبه شود. محاسبه تابع برازش به این صورت است که دسته‌بند بیزین جدید با ویژگی‌های پیشنهادی باید ساخته شود، سپس آموزش ببیند و در نهایت خطای آن محاسبه شود و این خطا بهعنوان تابع برازش این کروموزوم انتخاب شود. این پروسه باید برای تمام کروموزوم‌های موجود در هر نسل تکرار شود که مسلما بسیار زمانبر است. اما پس از تولید چند نسل تعداد ویژگی‌ها کاهش پیدا کرده و ابعاد مساله کم شده، سرعت و خطای دسته‌بندی در مرحله تست به‌ترتیب افزایش و کاهش چشم‌گیر دارد. در واقع هرچه برای آموزش زمان و هزینه گذاشته شود در مرحله تست و کاربرد سیستم جبران خواهد شد. الگوریتم ژنتیک تضمین می‌کند که تاثیرگذارترین ویژگی‌ها را انتخاب کند و بهینه‌ترین حالت ممکن را به کاربر بدهد با در نظر گرفتن این مشکل که بسیار زمانبر و کند است. بعد از اجرای الگوریتم ژنتیک و 45 نسل کروموزوم با کمترین برازندگی(کمترین خطا)، ویژگی‌های مناسب را نشان می‌دهد. تعداد ویژگی‌ها از 16 ویژگی به 10 ویژگی کاهش یافته است. جمعیت اولیه حدود 20 کروموزوم است.
3-2) روشهای دسته‌بندی
در این گزارش از روش های خطی و غیرخطی استفاده شده است و در این قسمت روشهای دسته بندی که مورد استفاده قرار گرفته اند تشریح شده اند.
فرمت این مقاله به صورت Word و با قابلیت ویرایش میباشد
تعداد صفحات این مقاله 16 صفحه
پس از پرداخت ، میتوانید مقاله را به صورت انلاین دانلود کنید
دانلود مقاله روش های استخراج ویژگی و روش های خطی و غیر خطی دسته بندی
