پایان نامه "Classification and Clustering of Vector Space Embedded Graphs"

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

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

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

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

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

لینک دانلود پایان نامه