پایان نامه رشته مهندسی کامپیوتر با عنوان طراحی یک زبان سطح بالای انعطاف‌پذیر برای داده‌کاوی اطلاعات

کامپیوتر و IT
پایان نامه رشته مهندسی کامپیوتر با عنوان طراحی یک زبان سطح بالای انعطاف‌پذیر برای داده‌کاوی اطلاعات چکیده : پروسه‌ی كشف دانش از پایگاه داده، یك پروسه‌ی علمی‌ برای شناسایی الگوهای معتبر، نوین، بالقوه مفید و قابل فهم از داده‌ها می‌‌باشد. مهم‌ترین بخش این پروسه، کاوش داده‌ها می‌باشد که با استفاده از الگوریتم‌های مشخصی یك سری الگوها را از پایگاه داده استخراج می‌‌كند.در این پروژه هدف ما طراحی یک زبان سطح بالای انعطاف‌پذیر برای داده‌کاوی اطلاعات می‌باشد. این کار علاوه بر کمک به محققان این زمینه برای بررسی روش‌های جدید و تست سریع و کارای الگوریتم‌های کاوش، امکان استفاده از این روش‌ها را به سادگی برای کسانی که اطلاعات اندکی در این زمینه دارند، نیزفراهم می‌آورد.در این رساله پروسه‌ی كشف دانش از پایگاه داده، همراه با مراحل آن، زبان‌های داده‌کاوی موجود و انواع معماری‌های ممکن برای این زبان‌ها بررسی شده است. سپس معماری مورد نظر ارایه شده است. در ادامه سعی شده است تا روش‌های مختلف کاوش، عام شده و جهت بکارگیری در زبان Flexible Query Generator (FlexQG)، آماده شوند.پس از تکمیل گرامر زبان، با هدف‌های مورد نظر، جهت تکمیل کار، دو نمونه از روش‌های کاوش کلی، با زبان SQL، پیاده‌سازی شده‌اند. کلمات کلیدی: زبان FlexQG خوشه بندی داده‌کاوی اطلاعات شناسایی الگوهای معتبر طراحی یک زبان سطح بالا مقدمه رشد روزافزون و انفجاری داده‌ها در عصر حاضر، پایگاه‌های داده را به عنوان جز لاینفکی در همه‌ی زمینه‌های کامپیوتر قرار داده است. اما با این سیل عظیم اطلاعات و نیازهای گسترده‌ی امروزی تنها نمی‌توان به اطلاعات بازیابی شونده‌ای از بانک‌های اطلاعاتی که تنها یك كپی از اطلاعات ذخیره شده در پایگاه داده هستند، دل، خوش کرد، بلکه باید راه‌هایی برای استخراج دانش موجود در این داده‌ها پیدا کرد.به این منظور پروسه‌ی كشف دانش از پایگاه داده مطرح شد که یك پروسه‌ی علمی‌ برای شناسایی الگوهای معتبر، نوین، بالقوه مفید و قابل فهم از داده‌ها می‌‌باشد. مهم‌ترین بخش این پروسه، کاوش داده‌ها می‌باشد که با استفاده از الگوریتم‌های مشخصی یك سری الگوها را از پایگاه داده استخراج می‌‌كند.در این پروژه هدف ما طراحی یک زبان سطح بالای انعطاف‌پذیر برای داده‌کاوی اطلاعات می‌باشد. این کار علاوه بر کمک به محققان این زمینه برای بررسی روش‌های جدید و تست سریع و کارای الگوریتم‌های کاوش، امکان استفاده از این روش‌ها را به سادگی برای کسانی که اطلاعات اندکی در این زمینه دارند، را نیزفراهم می‌آورد. فهرست مطالب ۱- مقدمه ۱ ۲- پروسه‌ی كشف دانش از پایگاه داده ۳ ۱-۲- ویژگی‌های KDD ۴ ۱-۱-۲- استخراج داده‌ها ۴ ۲-۱-۲- آماده کردن داده‌ها ۵ ۳-۱-۲- مهندسی داده‌ها ۵ ۴-۱-۲- مهندسی الگوریتم و تعیین استراتژی‌های کاوش ۵ ۵-۱-۲- اجرای الگوریتم كاوش و ارزیابی نتایج ۶ ۲-۲- زبان‌های پرسشی داده‌کاوی : ۶ -۳ معماری FlexQG ۹ ۱-۳- دلایل اقبال و رویكرد ما به روش‌ها و الگوریتم‌های بر پایه‌ی SQL: ۱۰ ۲-۳- چه مشكلاتی در سر راه پیاده‌سازی این رهیافت وجود دارند؟ ۱۱ ۳-۳- انواع معماری‌های ممکن ۱۲ ۱-۳-۳- خواندن مستقیم از DBMS ۱۲ ۲-۳-۳- استفاده از توابع تعریف كاربر ۱۲ ۴-۳- معماری مورد استفاده ۱۳ ۵-۳- روش‌های کاوش مورد پشتیبانی ۱۳ ۴- آماده‌سازی داده‌ها ۱۵ ۱-۴- جمع‌آوری داده‌ها ۱۵ ۲-۴- پیش‌پردازش داده‌ها ۱۵ ۱-۲-۴- طبقه‌بندی کردن ویژگی‌های عددی ۱۵ ۲-۲-۴- تبدیل ویژگی‌های رشته‌ای با مقادیر خاص به ویژگی عددی ۱۶ ۳-۲-۴- پاك‌سازی داده‌ها ۱۷ ۴-۲-۴- گرامر آماده‌سازی داده‌ها در FlexQG ۱۷ ۵- کلاسه‌بندی و پیشگویی داده‌ها ۱۸ ۱-۵- انواع روش‌های کلاسه‌بندی ۱۹ ۲-۵- مراحل یک الگوریتم کلاسه‌بندی ۱۹ ۳-۵- ارزیابی روش‌های کلاسه‌بندی ۲۰ ۴-۵- روش درخت تصمیم در کلاسه‌بندی ۲۰ ۱-۴-۵- انواع درخت‌های تصمیم ۲۱ ۱-۱-۴-۵- (Classification and Regression Tree) CART ۲۱ ۱-۱-۱-۴-۵- نحوه‌ی هرس كردن درخت ۲۲ ۲-۱-۴-۵- (Chi - Squared Automatic Iteration Decision tree) CHAID ۲۲ ۱-۲-۱-۴-۵- نحوه محاسبه‌ی χ2 ۲۳ ۲-۲-۱-۴-۵- شرط پایان ۲۳ ۵-۵- الگوریتم‌های کلاسه‌بندی و FlexQG ۲۳ ۶-۵- گرامر پیشنهادی ۲۵ ۶- كاوش قوانین وابسته سازی ۲۶ ۱-۶- اصول كاوش قوانین وابسته سازی ۲۷ ۲-۶- اصول استقرا در كاوش قوانین وابسته سازی ۲۷ ۳-۶- كاوش قوانین وابسته سازی و FlexQG ۲۹ ۴-۶- گرامر پیشنهادی برای کاوش قوانین وابسته‌سازی ۳۰ ۷- خوشه‌بندی ۳۱ ۱-۷- تعریف فرآیند خوشه‌بندی : ۳۲ ۲-۷- کیفیت خوشه‌بندی ۳۲ ۳-۷- روش ها و الگوریتم‌های خوشه‌بندی : ۳۳ ۱-۳-۷- الگوریتم‌های تفكیك ۳۳ ۲-۳-۷- الگوریتم‌های سلسله‌مراتبی ۳۴ ۳-۳-۷- روش‌های متكی برچگالی ۳۵ ۴-۳-۷- روش‌های متكی بر گرید ۳۵ ۵-۳-۷- روش‌‌های متكی بر مدل ۳۶ ۶-۳-۷- تكنیك‌های خوشه‌بندی دیگر ۳۶ ۴-۷- دسته‌بندی ویژگی‌های الگوریتم‌های خوشه‌بندی ۳۶ ۵-۷- الگوریتم‌های خوشه‌بندی و FlexQG ۳۷ ۱-۵-۷- بررسی پارامترهای لازم برای الگوریتم‌های خوشه‌بندی تفکیکی ۳۷ ۲-۵-۷- بررسی پارامترهای لازم برای الگوریتم‌های خوشه‌بندی سلسله مراتبی ۳۹ ۳-۵-۷- گرامر پیشنهادی ۳۹ ۸- الگوریتم کلی کاوش قوانین وابسته‌سازی، با استفاده از رهیافت SQL ۴۰ ۱-۸- قوانین وابسته‌سازی ۴۰ ۲-۸- کاوش اجزای وابسته ۴۰ ۳-۸- الگوریتم Apriori ۴۱ ۴-۸- وابسته سازی در SQL ۴۲ ۵-۸- شمارش پشتیبانی برای پیدا كردن مجموعه عناصر تکراری ۴۳ ۹- پیاده‌سازی چارچوب کلی الگوریتم‌های خوشه‌بندی تفکیکی، بر پایه‌ی SQL ۴۶ ۱-۹- ورودی‌های الگوریتم ۴۶ ۲-۹- خروجی‌های الگوریتم ۴۶ ۳-۹- مدل احتمال به کار رفته ۴۶ ۴-۹- الگوریتم EM ۴۸ ۵-۹- قدم اول: ساده‌سازی و بهینه کردن الگوریتم ۴۹ ۶-۹- پیاده‌سازی SQL استاندارد الگوریتم EM : ۴۹ ۱۰- نتیجه‌گیری و پیشنهادات ۵۳ پیوست الف: گرامر کلی زبان FlexQG ۵۴ مراجع و منابع ۵۸