فایل ورد کامل تحقیق روش‌های استخراج ویژگی و تحلیل علمی الگوریتم‌های خطی و غیرخطی در دسته‌بندی داده‌ها

توجه : به همراه فایل word این محصول فایل پاورپوینت (PowerPoint) و اسلاید های آن به صورت هدیه ارائه خواهد شد

 فایل ورد کامل تحقیق روش‌های استخراج ویژگی و تحلیل علمی الگوریتم‌های خطی و غیرخطی در دسته‌بندی داده‌ها دارای ۲۱ صفحه می باشد و دارای تنظیمات در microsoft word می باشد و آماده پرینت یا چاپ است

فایل ورد فایل ورد کامل تحقیق روش‌های استخراج ویژگی و تحلیل علمی الگوریتم‌های خطی و غیرخطی در دسته‌بندی داده‌ها  کاملا فرمت بندی و تنظیم شده در استاندارد دانشگاه  و مراکز دولتی می باشد.

توجه : در صورت  مشاهده  بهم ریختگی احتمالی در متون زیر ،دلیل ان کپی کردن این مطالب از داخل فایل ورد می باشد و در فایل اصلی فایل ورد کامل تحقیق روش‌های استخراج ویژگی و تحلیل علمی الگوریتم‌های خطی و غیرخطی در دسته‌بندی داده‌ها،به هیچ وجه بهم ریختگی وجود ندارد

---

بخشی از متن فایل ورد کامل تحقیق روش‌های استخراج ویژگی و تحلیل علمی الگوریتم‌های خطی و غیرخطی در دسته‌بندی داده‌ها :

روشهای استخراج ویژگی و روشهای خطی و غیر خطی دستهبندی

۱) چکیده:

در این تمرین روشهای استخراج ویژگی و روشهای خطی و غیر خطی دستهبندی را مورد مطالعه قرار می‌دهیم. در ابتدا روشهای مختلف استخراج ویژگی که از آن جمله PCA، LDA، روش قاب بندی و چند روش دیگر هستند را و سپس برای ویژگیهای استخراج شده از روشهای دستهبندی خطی بیزین و SVM خطی و سپس روشهای غیر‌خطی RBF ، MLP و همچنین SVM غیر‌خطی برای دستهبندی استفاده شده‌ است. بسته به روش شناسایی بکار گرفته شده، معمولا

ویژگیهای متفاوتی از دنباله نقاط استخراج می شود. در اکثر روش های موجود استخراج ویژگی، ویژگیها از روی مختصات نقاط نمونهبرداری شده ورودی استخراج میشوند. از مجموعه ی ویژگی های استخراج شده معمولاً تعدادی مفید تر و موثرترند. ما برای تشخیص و انتخاب ویژگی های تاثیرگذارتر از یک الگوریتم ژنتیک استفاده کرده ایم. اما پس از استخراج و انتخاب ویژگیها نوبت به دسته بندی می رسد. در ابتدا از چند دسته بند خطی استفاده کرده ایم. به راحتی می‌توان نشان داد که ناحیه‌های تصمیم‌گیری یک ماشین خطی محدودند و این محدودیت انعطاف‌پذیری و دقت دسته‌بند را کاهش می‌دهد. مسایل

بسیاری وجود دارد که توابع جداساز خطی برای داشتن حداقل خطا در آنها کافی نیستند. علاوه بر این مرزهای تصمیم‌گیری که کلاسها را از یکدیگر تفکیک می‌کنند ممکن است همیشه خطی نباشند و پیچیدگی مرزها گاهی اوقات نیاز به استفاده از سطح‌های کاملاً غیر خطی را دارند. بنابراین در ادامه ی کار از چند دسته بند غیرخطی نیز استفاده نمودیم. در استفاده از شبکه‌های عصبی چندلایه، شکل غیر خطی بودن از مجموعه‌ی آموزش فرا گرفته می‌شود. در روشهای RBF و SVM غیرخطی مشکل اصلی انتخاب توابع هسته غیر خطی مناسب است.

۲) مقدمه

 

اولین الگوریتم دسته‌بندی در سال ۱۹۳۶ توسط Fisher ارایه شد و معیارهای آن برای بهینه بودن، کم کردن خطای دسته‌بندی کننده‌های الگو‌های آموزشی بود. بسیاری از استراتژی‌های موجود نیز از همین روش پیروی می‌کنند. در ساده‌ترین شکل ممکن، دسته بند‌های خطی می‌توانند دو دسته‌ی متفاوت را تفکیک کنند. با توجه به این موضوع مساله‌ای را جدایی‌پذیر خطی می‌نامند که با یک ابرصفحه بتوان محدوده‌ی تصمیم را به دو گروه تقسیم‌بندی کرد. در عمل می‌توان دسته بند‌های خطی‌ای را طراحی کرد که بیش از دو گروه را از هم تفکیک کنند. این عمل را با تنظیم محدوده‌های تصمیم متعدد و آزمون‌های چندگانه بر اساس شرایط موجود می‌توان انجام داد. ما در این مساله یک دسته بندی با ۲۶ کلاس را داریم.

 

در روش بیزین احتمال شرطی تعلق بررسی می‌شود. به این ترتیب که الگوی مورد نظر به دسته‌ای تخصیص داده می‌شود که احتمال شرطی تعلق بردار مشخصه‌ی الگو به آن دسته ازتمام دسته‌های دیگر بیشتر باشد. روش بیزین به طور کلی می تواند برای کارایی بسیار مطلوب بهینه شوند. این روش مزایای دیگری نیز دارد که استفاده‌ی از آن را توجیه می‌کند. این روش می‌تواند با چند فرض ساده در مورد داده‌ها کاملاً به شکل روشهای ساده‌ی خطی عمل کند، به علاوه این کار می‌تواند به گونه‌ای انجام شود که در پایان، مدل قطعی بدون هیچ گونه رجوع به آمار به دست آید. در روش بیزین مشکل کار تعریف احتمالات شرطی مورد نظر قاعده‌ی بیز است.

یک محقق روسی به نام Vladimir Vapnik در سال ۱۹۶۵ گام مهمی در طراحی دسته‌بندها برداشت [۱] و نظریه‌ی آماری یادگیری را بصورت مستحکم‌تری بنا نهاد و ماشین بردار پشتیبان را ارایه کرد. ماشین‌های بردار پشتیبان در دو حالت جدایی‌پذیر و جدایی‌ناپذیر برای دسته‌بندی الگوهای یک مساله‌ی چندکلاسه از چند مرز جداکننده‌ی خطی یا ابرصفحه استفاده می‌کنند و در واقع حاصلضرب داخلی بردار ورودی با هر یک از بردارهای پشتیبان در فضای d بعدی ورودی محاسبه می‌شود. Vapnik نشان داد که می‌توان بردار ورودی را با یک تبدیل غیرخطی به یک فضای با بعد زیاد انتقال داد و در آن فضا حاصلضرب داخلی را بدست آورد که با این شرایط هسته‌ی مفیدی را خواهیم داشت.

روش RBF یک دسته‌بندی و تقریب‌ساز تابعی الگوست و شامل دو لایه می‌باشد که نرون‌های خروجی ترکیبی خطی از توابع پایه‌ای را به وجود می‌آورند که توسط نرون‌های لایه‌ی پنهان محاسبه شده‌اند. زمانی که ورودی در ناحیه‌ی تعیین شده‌ی کوچک از فضای ورودی قرار گیرد، توابع اساسی(غیر خطی) در لایه‌ی پنهان، پاسخ غیر صفری به محرک ورودی می‌دهند. همچنین این مدل به عنوان یک شبکه‌ی دریافت‌کننده‌ی ناحیه‌ای شناخته شده است. ما در روش RBF از معمول‌ترین تابع هسته‌ی غیر خطی یعنی سیگموئید استفاده کرده‌ایم.

 

به طور کلی شبکه‌های پرسپترون چند‌لایه شامل چندین پرسپترون ساده هستند که به طور ساختار سلسله‌مراتبی، یک شکل پیش‌خورد با یک و یا چند لایه‌ی میانی (لایه‌های پنهان) بین لایه‌های ورودی و خروجی را شکل می‌دهد. تعداد لایه‌ی پنهان و تعداد نرون‌های هر لایه ثابت نیستند. هر لایه ممکن است از نرون‌های مختلفی تشکیل شده باشد که این موضوع به کار آنها بستگی دارد. الگوریتم‌های آموزشی متفاوتی در روش چند لایه استفاده می‌شوند.

۳) روشهای به کار رفته در این گزارش

در این قسمت روشهای استخراج ویژگی، روشهای انتخاب ویژگی ها جهت بهینه کردن آنها و کم کردن ابعاد مساله با کاهش تعداد آنها و روشهای دسته‌بندی (خطی و غیرخطی) به کار رفته بررسی شده‌اند.

 

۳-۱) روشهای استخراج ویژگی

در این قسمت انواع روشهای استخراج ویژگی ها ذکر شده است. ذکر این نکته لازم است که برخی الگوریتمهای استخراج برای انتخاب ویژگیهای موثر نیز استفاده میشوند ازجملهی آنها PCA و LDA هستند. اما در این گزارش ما برای بهینه کردن ویژگیها و کم کردن تعداد آنها و یا به عبارت دیگر برای کاهش ابعاد (Curse of Dimensionality) از الگوریتم ژنتیک استفاده نمودهایم.

 

۳-۱-۱) روش 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 تائید میشود که در یافتن بردارهای مشخصه نتیجه میشود.( حاصل معکوس ماتریس پراکندگی و ماتریس پراکندگی بین کلاسی ). معیار دیگر همراه با بررسی (Supervised) برای چگالیهای شرایط کلاس غیرگاوسی بر پایهی فاصله Patrick-Fisher با استفاده از برآورد چگالی Parzen است.

 

۳-۱-۲) روش Kernel PCA (PCA با هسته یا PCA غیرخطی)

چندین روش برای تعریف روشهای استخراج ویژگی غیرخطی وجود دارد. یکی از این روشها که مستقیماً به PCA مربوط است، Kernel PCA نام دارد. ایدهی اصلی KPCA نگاشتن دادههای ورودی بر روی برخی از فضاهای ویژگی F جدید بطور معمولی با استفاده از تابع غیرخطی و سپس اعمال یک PCA خطی در فضای نگاشت شده است. به هر حال فضایF معمولاً ابعاد بسیار زیادی دارد. برای دوری از محاسبات نگاشت سادهی ، KPCA تنها هستههای Mercel که میتوانند به یک نقطه تجزیه شوند را بکار میگیرد.

به عنوان یک نتیجه فضای هسته یک متریک با تعریف مناسب دارد. نمونههای هستههای Mercer شامل چندجملهایهای مرتبه P بصورت و هسته گاوسی هستند.

فرض میکنیم که X یک ماتریس الگوی n×d نرمال شده با میانگین صفر است و یک ماتریس الگو در فضای F باشد. PCA خطی در فضای F بردارهای مشخصهی ماتریس همبستگی را حل میکند که همچنین ماتریس هسته نیز نامیده میشود. در KPCA در ابتدا m بردار ویژگی از بدست میآیند تا یک ماتریس انتقال E را تعریف کنند (E یک ماتریس n×m است که m تعداد ویژگیهای دلخواه است و m<=d است). الگوهای جدید x با نگاشت میشوند که اکنون با وابستگی به

مجموعه آموزش بازنمایی میشوند و نه با مقادیر ویژگی ویژگیهای اندازهگیریشده. باید توجه داشت که برای یک بازنمایی کامل تا m بردار مشخصه در E (بسته به تابع هسته) توسط KPCA ممکن است نیاز باشد در حالی که در PCA خطی یک مجموعه از d بردار مشخصه فضای اصلی ویژگیها را ارائه میکند. انتخاب تابع هسته برای یک کاربرد مشخص هنوز یک مساله باز است.

۳-۱-۳) روش مقیاسگذاری چندبعدی(MDS)

مقیاسگذاری چند بعدی (MDS)یک روش غیرخطی دیگر برای استخراج ویژگیهاست. هدف این روش بازنمایی یک مجموعهی چندبعدی در دو یا سه بعد است مثل آنچه ماتریس فاصله در فضای اصلی ویژگیهای d بعدی به طور کاملاً ثابت در فضای تصویرشده باقی مانده است. توابع تاکید فراوانی برای اندازهگیری کارایی این نگاشت استفاده شدهاند. یک مشکل MDS این است که یک تابع نگاشت ساده و روشن را ارئه نمیکند بنابراین ممکن نیست که یک الگوی جدید را در یک نگاشت برای یک مجموعهی آموزش مشخص بدون تکرار جایگذاری کند. چندین روش برای عنوان کردن این نقص که از درون یابی خطی تا آموزش شبکه عصبی محدود است مورد بررسی قرار گرفته است. همچنین امکان دارد که الگوریتم MDS مجدداً تعریف شود بنابراین مستقیماً یک نگاشت را تهیه میکند که ممکن است برای الگوهای آزمون جدید استفاده شود.

 

۳-۱-۴) روش شبکه عصبی روبه جلو (Feed-Forward Neural Network)

یک شبکهی عصبی روبهجلو یک روال جامع را برای استخراج ویژگیهاو دستهبندی پیشنهاد میکند. خروجی هر لایهی مخفی ممکن است به عنوان یک مجموعهی جدید و اغلب غیرخطی از ویژگیها تعریف شود که در لایهی مخفی برای دستهبندی ارائه میشوند. در این شرایط شبکههای استفاده شده توسط Fukushima و Lecun که اصطلاحاً آن را لایههای وزنی مشترک نامیدهاند، در حقیقت فیلترهایی برای استخراج ویژگیها در تصاویر دوبعدی هستند. در طول آموزش فیلترها با دادهها برای بیشینه کردن کارایی دستهبندی وفق داده شدهاند.

 

شبکههای عصبی میتوانند بطور مستقیم برای استخراج ویژگیها در یک شکل بدون بررسی (Unsupervised) استفاده شوند. شکل (a-1) معماری یک شبکه که قادر به پیدا کردن زیرفضای PCA است را نشان میدهد. به جای سیگموئیدها نرونها توابع انتقال خطی دارند. این شبکه d ورودی و d خروجی دارد که d تعداد مشخصشدهی ویژگیهاست. ورودیها همچنین برای رسیدن به هدف نیز با مجبور کردن لایهی خروجی به ساخت مجدد فضای ورودی تنها با

استفاده از لایهی مخفی بکار گرفته شدهاند. سه گره در لایهی مخفی اولین سه جزء اصلی را ضبط میکنند. اگر دو لایهی غیرخطی با واحدهای مخفی سیگموئیدی نیز وجود داشته باشند ( شکل (b-4))، آنگاه یک زیرفضای غیرخطی در لایهی میانی یافت خواهد شد (که همچنین لایهی گلوگاه هم نامیده میشود). غیرخطی بودن توسط اندازهی این لایههای اضافی محدود میشود. شبکههای PCA غیر خطی یا اصطلاحاً خودشرکتپذیرها ی ابزار قوی را برای آموزش و تشریح زیرفضای غیرخطی پیشنهاد میکند. محققی به نام Oja نشان داد که چگونه شبکههای خودشرکتپذیر میتوانند برای ICA استفاده شوند.

شکل ۱:شبکههای خودشرکتپذیر برای پیدا کردن یک زیرفضای سه بعدی. (a) خطی و (b) غیرخطی (تمام اتصالات نشان داده نشدهاند).

۳-۱-۵) روش نگاشت خودسازمانده (Self-Organizing Map)

روش نگاشت خودسازمانده ی(SOM) یا نگاشت Kohonen نیز میتواند به عنوان یک روش غیرخطی استخراج ویژگیها استفاده شود. در SOM نرونها در یک شبکهی توری مانند m بعدی مرتب شدهاند که m معمولاً ۱، ۲ و یا ۳ میباشد.هر نرون به تمام d واحد ورودی متصل است. وزنها بر روی اتصالات برای هر نرون از یک بردار وزن d بعدی گرفته شدهاند. در طول مرحلهی آموزش الگوها با یک ترتیب تصادفی به شبکه ارائه میشوند. در هر ارائه، برنده که بردار وزنی نزدیکتری به بردار ورودی دارد به عنوان اولین مورد شناخته میشود. سپس تمام نرونها در همسایگی برنده (که در شبکه تعریف شدهاند) بهروزرسانی میشوند که بردارهای وزن آنها به سمت ورودی حرکت میکند. در نتیجه پس از اتمام آموزش بردارهای وزنی نرونهای همسایه در شبکه احتمالاً الگوهایی از ورودی که نزدیکتر به فضای اصلی ویژگیها هستند را بازنمایی میکنند. بنابراین یک نگاشت محافظ وضعیت تشکیل میشود. زمانی که شبکه در فضای اصلی مطرح شد، اتصالات شبکه با توجه به چگالی دادههای آموزشی میتوانند بیشتر یا کمتر تحت فشار قرار گیرند. بنابراین SOM یک نقشه m بعدی با یک اتصال فضایی را پیشنهاد میکند که میتواند به عنوان یک استخراجکنندهی ویژگی تفسیر شود. SOM با LVQ متفاوت است چون در LVQ هیچ همسایهای تعریف نمیشود.

 

۳-۱-۶) استفاده از الگوریتم ژنتیک برای کاهش ابعاد مساله

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

شکل۲: نمایش یک کروموزوم و نحوه‌ی انتخاب ویژگی‌ها

آمیزش[۲] با تولید یک عدد صحیح تصادفی بین ۱ و ۱۶ انجام می‌شود. جهش[۳] نیز با تولید یک عدد تصادفی بین ۱و ۱۶ و تغییر مقدار ژن از یک به صفر یا بالعکس انجام می‌شود. تولید نسل جدید با انتخاب ۵۰ درصد از نسل قبلی به صورت تصادفی با روش چرخ رولت و ۵۰ درصد با آمیزش بین والدین تصادفی از

جمعیت قبل انجام می‌شود. سپس روی ۱۵ درصد از این جمعیت به‌طور تصادفی جهش اعمال می‌شود. با اعمال الگوریتم ژنتیک در چند نسل و انتخاب کروموزوم با کمترین مقدار تابع برازش ویژگی‌های مناسب به‌دست می‌آیند.

همانطور که گفته شد روند اجرای الگوریتم ژنتیک خصوصاً برای این منظور خاص بسیار زمانبر می‌باشد. تصور کنید که بعد از تولید هر کروموزوم باید تابع برازش آن محاسبه شود. محاسبه تابع برازش به این صورت است که دسته‌بند بیزین جدید با ویژگی‌های پیشنهادی باید ساخته شود، سپس آموزش ببیند و در نهایت خطای آن محاسبه شود و این خطا به‌عنوان تابع برازش این کروموزوم انتخاب شود. این پروسه باید برای تمام کروموزوم‌های موجود در هر نسل تکرار شود که مسلما بسیار زمانبر است. اما پس از تولید چند نسل تعداد ویژگی‌ها کاهش پیدا کرده و ابعاد مساله کم شده، سرعت و خطای دسته‌بندی در مرحله تست

به‌ترتیب افزایش و کاهش چشم‌گیر دارد. در واقع هرچه برای آموزش زمان و هزینه گذاشته شود در مرحله تست و کاربرد سیستم جبران خواهد شد. الگوریتم ژنتیک تضمین می‌کند که تاثیرگذارترین ویژگی‌ها را انتخاب کند و بهینه‌ترین حالت ممکن را به کاربر بدهد با در نظر گرفتن این مشکل که بسیار زمانبر و کند است. بعد از اجرای الگوریتم ژنتیک و ۴۵ نسل کروموزوم با کمترین برازندگی(کمترین خطا)، ویژگی‌های مناسب را نشان می‌دهد. تعداد ویژگی‌ها از ۱۶ ویژگی به ۱۰ ویژگی کاهش یافته است. جمعیت اولیه حدود ۲۰ کروموزوم است.

 

۳-۲) روشهای دسته‌بندی

در این گزارش از روشهای خطی و غیرخطی استفاده شده است و در این قسمت روش‌های دستهبندی که مورد استفاده قرار گرفتهاند تشریح شدهاند.

۳-۲-۱) روشهای دسته‌بندی خطی

در شکل (۳) می‌توان نمای کلی از یک دسته‌بند خطی را دید. دسته‌بند‌های خطی می‌توانند بیش از دو گروه را نیز از هم تفکیک کنند.
شکل ۳: نمای کلی یک دسته‌بند خطی
در شکل (۴) تفکیک‌پذیری ذکر شده‌ی فوق برای ۴ کلاس انجام شده است.

شکل ۴: مرزهای تصمیم‌گیری برای یک مساله با ۴ کلاس متفاوت. ناحیه‌های با رنگ متفاوت در مرکز، ناحیه‌های مبهم هستند

۳-۲-۱-۱) دسته‌بند بیزین

در بیزین فرض می‌کنیم پارامترهای روش، تصادفی هستند. یعنی خود پارامترها دارای توزیع می‌باشند و ما می‌خواهیم توزیع آنها را بدست آوریم. مسلماً براساس تعداد داده‌ها و متفاوت خواهند بود.

توابع جداساز مرزهای تصمیم‌گیری ما هستند. مرزهایی که تعیین می‌کنند ورودی x جزء کدام دسته قرار دارد. پروسه‌ی تصمیم‌گیری را می‌توانید در شکل(۵) ببینید.

شکل۵: پروسه‌ی تصمیم‌گیری بیزی.

x = (x1, x2, …, xd)t (t stands for the transpose vector form)
m = (m1, m2, …, md)t mean vector
S = d*d covariance matrix
|S| and S-1 are determinant and inverse respectively
۳-۲-۲) روش‌های دستهبندی غیرخطی

کلاً روش‌های جداسازی غیرخطی بر دو نوع هستند. روش‌های جداساز غیرخطی بر پایه‌ی هسته که در آنها از توابع هسته‌ی غیرخطی استفاده می‌شود و روشهای جداساز غیرخطی که بر پایه‌ی Projection هستند[۲].

یکی از روش‌های غیرخطی بر پایه‌ی Projection، شبکه‌ی عصبیMLP است که در ادامه معرفی می‌شود.

۳-۲-۲-۱) دسته‌بند پرسپترون چند لایه

الگوریتم‌های آموزشی متفاوتی در روش پرسپترون چند لایه استفاده می‌شوند. پرسپترون چند‌لایه را می‌توان برای پیاده‌سازی مسایل مختلف با دو یا سه لایه به کار برد. شکل الگوریتم استفاده شده به صورت زیر است.

شکل ۶: پرسپترون چندلایه‌ی استفاده شده

روش تعلیم شبکه های عصبی پرسپترون چند لایه:

منظور از تعلیم یک شبکه عصبی آنست که وزن‌ها (یا قدرت ارتباط بین نرون‌ها) و بعضاً تعداد نرون‌ها را بگونه‌ای تعیین کنیم تا شبکه به گروه خاصی از داده‌ها پاسخ‌های مطلوبی بدهد. بعبارت ریاضی‌، فرض کنیم که تعداد P بردار ورودی Xi متعلق به Rn و P بردار پاسخ مطلوب ydi متناظر متعلق به Rm بعنوان الگو برای تعلیم به شبکه عصبی در اختیار داشته باشیم :

X=[ x1 x2 …. Xp ]

y=[ yd1 yd2 …. ydp ]

می‌خواهیم بردارپارامترهای شبکه عصبی شامل وزن‌ها و مقادیر آستانه‌ای آن W را بگونه‌ای تعیین کنیم که :

f (xi , w) = ydi i=1,2, … , p

که در آن تابع f(x , w) نشان دهنده نگاشت بین ورودی و خروجی شبکه عصبی می‌باشد‌.

روش انتشار معکوس خطا (Back Propagation)

این روش یک روش بهینه‌سازی تندترین شیب (Steepest Descent) است‌. در این روش فرض بر آن است که یک مجموعه از زوج الگوهای ورودی و خروجی در اختیار است‌. شبکه د‌ر ابتدا بر اساس بردار ورودی، بردار خروجی خود را تولید می‌کند و آنرا با بردار خروجی مطلوب یا هدف مقایسه می‌نماید‌. اگر اختلافی وجود نداشت، احتیاجی به تعلیم نیست‌. در غیر اینصورت وزن‌ها بگونه‌ای تغییر داده می‌شود که اختلاف کاهش یابد‌.

۴) شبیه‌سازی و ارائه‌ی نتایج تجربی:

در این قسمت ابتدا معرفی خلاصه ای از داده‌ها صورت می‌گیرد و سپس نتایجی را که با هر یک از روش‌ها بدست آمده را ذکر کرده‌ام.

۴-۱)مجموعه داده

فیلدها یا ویژگیهای استخراج شده

از هر کاراکتر با ۲۰ قلم متفاوت داده جمع‏آوری شده و به صورت تصادفی هر کاراکتر تغییر شکل داده شده است. بدین گونه ۲۰۰۰۰ رکورد متفاوت جمع‏آوری شده است. هر داده توسط ۱۶ ویژگی اولیه استخراج شده، نشان داده شده است

Attribute Information:

۱ lettr capital letter (26 values: A-Z)
۲. x-box horizontal position of box (integer)
۳. y-box vertical position of box (integer)
۴. width width of box (integer)
۵. high height of box (integer)
۶. onpix total # on pixels (integer)
۷. x-bar mean x of on pixels in box (integer)
۸. y-bar mean y of on pixels in box (integer)
۹. x2bar mean x variance (integer)
۱۰. y2bar mean y variance (integer)
۱۱. xybar mean x y correlation (integer)
۱۲. x2ybr mean of x * x * y (integer)
۱۳. xy2br mean of x * y * y (integer)
۱۴. x-ege mean edge count left to right (integer)
۱۵. xegvy correlation of x-ege with y (integer)
۱۶. y-ege mean edge count bottom to top (integer)
۱۷. yegvx correlation of y-ege with x (integer)
لازم به ذکر است که بدلیل حجم زیاد پایگاه داده این مساله فقط قسمت محدودی از این رکوردها در جدول(۱) آورده شده است.
جدول۱: نمونه‏ای از رکوردهای مجموعه داده‏ها

T
۲
۸
۳
۵
۱
۸
۱۳
۰
۶
۶
۱۰
۸
۰
۸
۰
۸
I
۵
۱۲
۳
۷
۲
۱۰
۵
۵
۴
۱۳
۳
۹
۲
۸
۴
۱۰
D
۴
۱۱
۶
۸
۶
۱۰
۶
۲
۶
۱۰
۳
۷
۳
۷
۳
۹
N
۷
۱۱
۶
۶
۳
۵
۹
۴
۶
۴
۴
۱۰
۶
۱۰
۲
۸
G
۲
۱
۳
۱
۱
۸
۶
۶
۶
۶
۵
۹
۱
۷
۵
۱۰
S
۴
۱۱
۵
۸
۳
۸
۸
۶
۹
۵
۶
۶
۰
۸
۹
۷
B
۴
۲
۵
۴
۴
۸
۷
۶
۶
۷
۶
۶
۲
۸
۷
۱۰
A
۱
۱
۳
۲
۱
۸
۲
۲
۲
۸
۲
۸
۱
۶
۲
۷
J
۲
۲
۴
۴
۲
۱۰
۶
۲
۶
۱۲
۴
۸
۱
۶
۱
۷
M
۱۱
۱۵
۱۳
۹
۷
۱۳
۲
۶
۲
۱۲
۱
۹
۸
۱
۱
۸
X
۳
۹
۵
۷
۴
۸
۷
۳
۸
۵
۶
۸
۲
۸
۶
۷
O
۶
۱۳
۴
۷
۴
۶
۷
۶
۳
۱۰
۷
۹
۵
۹
۵
۸
G
۴
۹
۶
۷
۶
۷
۸
۶
۲
۶
۵
۱۱
۴
۸
۷
۸
M
۶
۹
۸
۶
۹
۷
۸
۶
۵
۷
۵
۸
۸
۹
۸
۶
پراکندگی کلاسها در زیر آورده شده است.

تعداد دادههای موجود برای هر دسته در این مجموعه به صورت زیر است:

Number of Instances: 20000
Missing Attribute Values: None
Number of Attributes: 17 (Letter category and 16 numeric features)

Class Distribution:
۷۸۹ A 766 B 736 C 805 D 768 E 775 F 773 G
۷۳۴ H 755 I 747 J 739 K 761 L 792 M 783 N
۷۵۳ O 803 P 783 Q 758 R 748 S 796 T 813 U
۷۶۴ V 752 W 787 X 786 Y 734 Z
این مجموعه داده را می توان از سایت معتبر UCI [3] دریافت کرد.

۴-۲) شبیه‌سازی روشهای استخراج ویژگی و ارائه نتایج تجربی

در این قسمت نتایج مربوط به شبیه‌‌سازی روش‌های استخراج ویژگی را ذکر کرده ام. در هر روش پس از پیاده‌سازی و اجرا بر روی ویژگی‌ها تعدادی از ویژگی‌ها به عنوان ویژگی های منتخب برگزیده شده ‌اند تا با استفاده از آنها عملیات دسته‌بندی صورت گیرد. در روش‌های PCA ، LDA و KPCA تعدادی ویژگی انتخاب می‌شود که تعداد آنها تقریباً با یکدیگر برابر است اما نمی‌توان گفت که بهترین‌ها را برگزیده‌اند چون ویژگی‌های انتخاب شده توسط الگوریتم ژنتیک نرخ تشخیص دسته‌بندی بالاتری را دارند. در روش خوشه‌بندی ما جای رکورد‌ها را با ستون‌ها تعویض کرده‌ایم تا به جای خوشه‌بندی داده‌ها، ویژگی‌ها را خوشه‌بندی کنیم. با اجرای این کار و انجام چند تکرار و مقایسه‌ی ویژگی‌های منتخب می‌بینیم که بهترین حالت برای انتخاب ویژگی‌های نماینده‌ی هر خوشه مشابه به همان روش الگوریتم ژنتیک است. نتایج این انتخاب‌ها در جدول (۲) آورده شده است.

جدول ۲: نتایج انتخاب ویژگی‌های مفید همراه با تعداد آنها برای هر روش
Feature Extraction Method
PCA
LDA
KPCA
GA
K-Means
Number of Features
۱۱
۱۰
۱۲
۹
۴
Reduction Rate of Feature
۳۲%
۳۷.۵%
۲۵%
۴۴%
۷۵%

همانطور که در جدول فوق مشاهده می‌شود بیشترین کاهش تعداد ویژگی را در روش خوشه بندی داشتیم. علت این است که ما ۱۶ ویژگی موجود را در ۴ خوشه قرار داده‌ایم و نماینده‌ی هر خوشه را به عنوان یک ویژگی در نظر گرفته‌ایم و این کاهش زیاد همیشه نمی‌تواند موجب ایجاد نرخ مناسبی برای دسته‌بندی شود. در روش ژنتیک کاهش تعداد ویژگی‌ها ایده‌آل است و البته همانطور که در ادامه خواهید دید نتیجه نیز ایده‌آل خواهد بود.

۴-۳) شبیه‌سازی روشهای دسته‌بندی و ارائه نتایج تجربی

در این قسمت نتایج حاصل از دو روش دسته‌بندی بیزین و پرسپترون چندلایه برای هر یک از حالات ویژگی‌های استخراج شده استفاده کرده‌ام و نتایج حاصل از دسته‌بندی را بدست آورده‌ام این نتایج در جدول زیر آورده شده است.

جدول ۳: نتایج دسته‌بندی برای مجموعه ویژگی‌های استخراج شده
Classification Method
Feature Extraction Method
Bayesian
MLP
Recognition rate
PCA
۸۵.۶۳%
۹۰.۲۵%
LDA
۸۲.۵%
۸۸%
KPCA
۸۹.۱۵%
۹۳.۶۳%
K-Means
۹۳.۷۵%
۹۵.۵۰%
GA
۹۷.۵۸%
۹۸.۸%
Recognition rate
Mean of All
۸۹.۷۲%
۹۳.۲۴%
Error rate
Mean of All
۱۰.۲۸%
۷.۷۶%

همانطور که در جدول (۳) هم مشاهده می شود بهترین نرخ تشخیص مربوط به الگوریتم ژنتیک است و کمترین نرخ در ویژگی‌های استخراج شده توسط LDA مشاهده می‌شود. البته نرخ تشخیص اکثر انتخاب‌های روش K-Means نرخ تشخیص بسیار بدی داشتند، نرخی در حدود ۲۰%. علت این است که نماینده‌های انتخاب شده جزو ویژگی‌های غیرمفید هستند و در نهایت من بهترین نرخ کسب شده توسط این روش را ذکر کرده‌ام.

۴-۴) مقایسه کمی نتایج تجربی روشهای به کار گرفته شده.

در مقایسه روش‌های استفاده شده همانطور که در جدول (۴) نیز مشاهده خواهید کرد روش استخراج ویژگی با الگوریتم ژنتیک بهترین روش در بین همه‌ی روش‌ها می‌باشد. چون تعداد ویژگی‌ها را به میزان معقولی کاهش داده است و همچنین ویژگی‌هایی را در لیست نهایی انتخاب‌شده قرار داده است که مسلماً بهترین‌ها هستند. همچنین در بین روش‌های دسته‌بندی نیز روش پرسپترون چندلایه از روش بیزین جواب بهتری را کسب کرده است.

جدول ۴: مقایسه‌ی نتایج کلیه روش‌های بکار گرفته شده.
Feature Extraction Method
Number of Features
Bayesian Error Rate
MLP Error Rate
PCA
۱۱
۱۴.۳۷%
۹.۷۵%
LDA
۱۰
۱۷.۵۰%
۱۲.۰۰%
KPCA
۱۲
۱۰.۸۵%
۶.۳۷%
K-Means
۴
۶.۲۵%
۴.۵۰%
GA
۹
۲.۴۲%
۱.۲۰%

۵) نتیجه‌گیری و بحث:

۵-۱) مقایسه کیفی نتایج این گزارش و روشهای گزارش قبل

در گزارش‌های قبل از روش‌های دسته‌بندی بیزین و پسپترون چندلایه استفاده کرده بودیم. تا کنون ما برای دسته‌بندی از همان ویژگی‌های استخراج شده‌ی پیش‌فرض استفاده می‌کردیم اما در این گزارش ویژگی‌هایی را برگزیدیم که خوشبختانه در برخی موارد نرخ تشخیص بالاتر رفت و این نشان بر این است که در مجموعه‌ی ویژگی‌های داده شده ویژگی‌هایی نیز وجود دارند که مفید نیستند و بلکه موجب کاهش نرخ تشخیص و دسته‌بندی می‌شوند. حال با مقایسه کردن دو جدول زیر مشاهده می‌کنیم که در هر دو روش در برخی حالات با کاهش تعداد ویژگی‌ها نرخ تشخیص را بالا برده‌ایم. جدول (۵) نتایج حاصل از همین دو روش دسته‌بندی هستند که ما قبلاً و با ویژگی‌های قبلی یعنی همان ۱۶ ویژگی بدست آورده ایم را نشان می‌دهد.

جدول ۵: نتایج روش‌های بکار گرفته شده با استفاده از ۱۶ ویژگی اولیه.
Classification
Method
Bayesian
MLP
Recognition
Rate
۸۴.۶%
۹۳.۶۲%
Error Rate
۱۵.۴%
۳.۳۸%
جدول (۶) نیز موارد بهبودیافته را با انتخاب بهینه‌ی ویژگی‌ها نشان می‌دهد. در این جدول مواردی که نرخ تشخیص آنها نسبت به قبل بهبود یافته است با رنگ تیره مشخص شده اند.

جدول ۶: نتایج با استفاده از ویژگی‌های بهینه شده.
Classification Feature Method
Extraction Method
Bayesian
MLP
PCA
۸۵.۶۳%
۹۰.۲۵%
LDA
۸۲.۵%
۸۸%
KPCA
۸۹.۱۵%
۹۳.۶۳%
K-Means
۹۳.۷۵%
۹۵.۵۰%
GA
۹۷.۵۸%
۹۸.۸%

۵-۲) مقایسه کیفی با نتایج تجربی سایر مقالات (معتبر).

در مرجع [۴] با استفاده از روش MLP در تشخیص کاراکتر ها استفاده شده است. در این ژورنال از الگوریتم تعدیل میزان ازبین رفتن دینامیک برای آموزش شبکه عصبی استفاده می شود. این روش بر روی ۳ مجموعه داده از جمله مجموعه داده UCI ارزیابی شده است. لازم به ذکر است که در این ژورنال الگوریتم دسته‌بندی پرسپترون چندلایه با همان ۱۶ ویژگی اولیه انجام شده است و البته نتایج ما با آنها قابل مقایسه است. این نتایج در ادامه در جدول (۷) آورده شده است.
جدول ۷: نتایج دسته‌بندی همراه با نرخ خطا
Classification Method
MLP
Dataset
Letter
Recognition rate
۷۶.۴۱%
Error rate
۲۳.۵۹%
در مرجع [۵] با استفاده از روش Bayesian در تشخیص کاراکتر ها استفاده شده است. در این ژورنال از الگوریتم تعدیل میزان ازبین رفتن دینامیک برای آموزش شبکه عصبی استفاده می شود. این روش بر روی مجموعه داده UCI ارزیابی شده است. نتایج این مقاله در ادامه در جدول (۸) آورده شده است.
جدول ۸: نتایج دسته‌بندی همراه با نرخ خطا
Classification Method
Bayesian
Dataset
UCI
Recognition rate
۶۹.۸%
Error rate
۳۰.۲%

در مرجع [۶] نیز روش MLP برای دسته‌بندی داده‌ها با استفاده از دو مجموعه ویژگی مختلف بکار گرفته شده است. در این مقاله روش‌های استخراج ویژگی برای دو حالت مختلف ذکر نشده است. این نتایج در ادامه آورده شده است. نتایج کسب شده در این روش غیرخطی از نتایج ما کمترند. جدول (۹) این موضوع را نشان می‌دهد.
جدول ۹: نتایج دسته‌بندی برای دو مجموعه‌ی متفاوت از ویژگی‌ها.
Feature set
Classification Method
MLP
A
Recognition rate
۷۹%
B
۸۱%

۶) مراجع

[۱] Support Vector Networks, Machine Learning, Vol 20. C. Cortes, V. Vapnik. 2995. pp. 273-297.

[۲] Statistical Pattern Recognition, Second Edition. Andrew R. Webb, QinetiQ Ltd., Malvern, UK.

[۳] UCI Dataset Website: http://www.fizyka.umk.pl/~duch/software.html

[۴] Improving RBF-DDA Performance on Optical Character Recognition through Weights Adjustment, Adriano L. I. Oliveira Member, IEEE, and Silvio R. L. Meira, 2006 International Joint Conference on Neural Networks. Sheraton Vancouver Wall Centre Hotel, Vancouver, BC, Canada, July 16-21, 2006. – 0-7803-9490-9/06/$20.00/©۲۰۰۶ IEEE.

[۵] A Weighted Combination of Classifiers Employing Shared and Distinct Representations, J. Kittler, S.A. Hojjatoleslami, Computer Vision and Pattern Recognition, 1998. Proceedings. 1998 IEEE Computer Society Conference. ©۱۹۹۸ IEEE.

[۶] A New Multiple Classifiers Combination Algorithm, Jianpei Zhang, Lili Cheng, and Jun Ma, College of Computer Science and Technology, Harbin Engineering University, China, Proceedings of the First International Multi-Symposiums on Computer and Computational Sciences (IMSCCS’06), 0-7695-2581-4/06 $20.00 © ۲۰۰۶ IEEE.

با تشکر از حسن توجه شما- سید مجید غفوری

۴/۱۱/۱۳۸۶

[۱] Fitness function

[۲] Crossover

[۳] Mutation