دانشگاه آزاد اسلامی
واحد تهران جنوب
دانشكده تحصیلات تكمیلی
سمینار برای دریافت درجه كارشناسی ارشد “M.Sc“
مهندسی كامپیوتر – نرم افزار
عنوان :
تطبیق رشته ای برای شناسایی ساختاری الگو
برای رعایت حریم خصوصی اسامی استاد راهنما،استاد مشاور و نگارنده درج نمی شود
تکه هایی از متن به عنوان نمونه :
(ممکن است هنگام انتقال از فایل اصلی به داخل سایت بعضی متون به هم بریزد یا بعضی نمادها و اشکال درج نشود ولی در فایل دانلودی همه چیز مرتب و کامل است)
چكیده :
روشهای تشخیص الگو بصورت آماری ، نحوی و ساختاری مطرح میشوند. در روشهای
ساختاری تشخیص الگو ، از یك مجموعه نمادهای اولیه (سمبول ها) برای شناسایی الگوها استفاده
میشود. كه این سمبول ها ، خود نیز از الگوها استخراج میشوند. پس از آن مجموعه نمادهای اولیه با
رشته مورد نظر مقایسه شده و فاصله ویرایشی بین آنها بدست میآید ، آنگاه سمبولی كه كمترین فاصله
را با الگوی اصلی داشته باشد برنده این تطبیق است. ساختارهای دادهای كه برای تشخیص ساختاری
الگو مورد استفاده قرار میگیرند ، رشتهها ، درختها و گرافها را شامل میشوند. كاربردهای تشخیص
یک مطلب دیگر :
الگوی ساختاری در شناسائی شئهای دو بعدی ، سه بعدی ، كاراكترها ، تشخیص گفتار ، شناسایی
لغات مشابه در بانك اطلاعاتی لغت نامه و شناخت اجزای ماشین مطرح میشود.
مقدمه :
این مطلب یك ایده متعارف برای تعداد متفاوتی از روشهایی است كه جهت تشخیص الگو بكار
میروند و اهمیت ندارد كه آن الگوها آماری ، تركیبی یا ساختاری باشند. این یك مقایسه از الگویی
ناشناخته با یك عدد بطور نمونه یا با نمونه الگوی اولیه با استفاده از فاصله یا ( میزان ) شباهت یا تفاوت
است. یعنی هر الگوی ناشناخته را بصورت نمونه با یك رشته عددی تقریب زده و آن رشته را با رشته
عددی الگوی اولیه مقایسه می كنیم. ابتدا ارائه یك عدد از نمونههای اولیه كه به كلاس مربوط به آن
نمونههای اولیه شناخته شده مرتبط است ، و سپس دسته بندی یك الگوی ناشناخته بوسیله تعیین
كردن بیشترین شباهت الگوی تصمیم گیری برای آن كلاس است كه دست یافتنی است. پس برای هر
نمونه اولیه یك عدد در نظر میگیریم كه آن عدد با كلاسهای این نمونههای شناخته شده در ارتباط
است و دسته بندی الگوهای ناشناخته بوسیله تعیین كردن بیشترین شباهت الگو و تصمیم گیری درباره
كلاس آن حاصل میشود.
در دسته بندی آماری ، نمونهها به وسیله عامل مشترك از یك تابع تصمیم گیری ارزیابی
شدهاند. پارامترها از یك احتمال توزیع شده نقاط ، در یك فضای ویژگی تعریف شده ، و مفهوم شباهت
نیز بر اساس فاصله تعریف شده است. و توابع تصمیم گیری در فضای n بعدی از اعداد حقیقی كار
میكنند. اگر ساختار الگو لازم باشد ، گرامرهای رسمی (قراردادی) یك مفهوم مفید هستند. تابع
متداول بصورت دستی یا بصورت اتوماتیك یك گرامر از یك بسته نمونه را نتیجه می دهد. بنابراین یك
الگوی ورودی ناشناخته به یك تجزیه كننده تحویل داده شده و مطابق با این گرامر تحلیل میشود. در
این روش نه فقط یك دسته بندی ، بلكه همچنین یك شرح ساختاری از الگوی ناشناخته میتوان فراهم
كرد. تحلیل گر نحوی میتواند مانند یك تابع ویژه برای تصمیمگیری شباهت ساختاری تفسیر شود.
مطابق ساختارهای دادهای متفاوت كه برای تشخیص الگو مورد استفاده قرار میگیرند ، فقط رشته
گرامرها بررسی نمیشود ، بلكه درخت ، گراف و آرایه گرامرها در یك قاعده مهم تشخیص الگو فعالیت
دارند.
اینها مواردی از تعدادی از مثالهای آماده بسیار كوچك هستند كه كاربردشان برای نتیجهگیری
دستوری است ، یا در جایی است كه تمام توان یك پیشروی دستوری نیاز نیست. یعنی كاربرد این
مثالهای آماده بسیار كوچك برای استنتاجی بر اساس قواعد ، و یا استنتاجی در مكانی كه نیازی نیست
از تمام توان قواعد استنتاجی استفاده كرد میباشد. اگر ساختار الگو مورد نیاز باشد ، با این حال ، شاید
تكنیك تطبیق ساختاری مفید باشد.
ایده پایهای تطبیق ساختاری ، به سوی بازنمایی مستقیم نمونههای اولیه است ، بخوبی الگوهای
ورودی ناشناخته ، كه بوسیله معانی یك ساختار داده مناسب و بسوی مقایسه این ساختارها در ترتیبی
برای یافتن شباهت نمونه اولیه با یك الگوی ناشناخته ورودی حركت می كند. این حركت به جلو
نیازمند یك عدد قراردادی از شباهت بین دو ساختار ارائه شده است. تعدادی از برخی اعداد در برخی از
نوشتهها پیشنهاد شده است. آنها میتوانند به گروههای بزرگی طبق ساختارهای دادهای تقسیم بشوند
كه برای تشخیص الگو استفاده شدهاند. بیشتر ساختارهای دادهای مهم ، رشتهای ، درختی ، گراف و
آرایهای هستند. وابستگی به دامنه مسائل خاص برای همه این ساختارهای دادهای میتواند بوسیله
ویژگیهایشان افزایش یابد.
با یك محاسبه پیچیده ، رشتهها خیلی كارآمد هستند ، از آنجائیكه بررسی میزان شباهت بین
رشتهها میتواند كاملا سریع انجام شود ، اگر چه رشتهها به تعداد نمایششان محدود هستند. در موارد
خیلی زیاد گرافها بیشترین قدرت رسیدن به بازنمایی الگوی ساختاری را دارند. اگر چه تطبیق گراف
بطور مفهومی نسبتا پیچیده است ، و به نسبت قیمت محاسبات ، گران است. بنابراین یك تعادلی بین
[دوشنبه 1399-08-12] [ 06:58:00 ب.ظ ]
|