فرمت فایل : WORD (قابل ویرایش)
تعداد صفحات:60
فهرست مطالب:
۱- مقدمه ۱
۲- پروسهی کشف دانش از پایگاه داده ۳
۱-۲- ویژگیهای 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 ۵۴
مراجع و منابع ۵۸
۱- مقدمه
رشد روزافزون و انفجاری دادهها در عصر حاضر، پایگاههای داده را به عنوان جز لاینفکی در همهی زمینههای کامپیوتر قرار داده است. اما با این سیل عظیم اطلاعات و نیازهای گستردهی امروزی تنها نمیتوان به اطلاعات بازیابی شوندهای از بانکهای اطلاعاتی که تنها یک کپی از اطلاعات ذخیره شده در پایگاه داده هستند، دل، خوش کرد، بلکه باید راههایی برای استخراج دانش موجود در این دادهها پیدا کرد.
به این منظور پروسهی کشف دانش از پایگاه داده مطرح شد که یک پروسهی علمی برای شناسایی الگوهای معتبر، نوین، بالقوه مفید و قابل فهم از دادهها میباشد. مهمترین بخش این پروسه، کاوش دادهها میباشد که با استفاده از الگوریتمهای مشخصی یک سری الگوها را از پایگاه داده استخراج میکند.
در این پروژه هدف ما طراحی یک زبان سطح بالای انعطافپذیر برای دادهکاوی اطلاعات میباشد. این کار علاوه بر کمک به محققان این زمینه برای بررسی روشهای جدید و تست سریع و کارای الگوریتمهای کاوش، امکان استفاده از این روشها را به سادگی برای کسانی که اطلاعات اندکی در این زمینه دارند، را نیزفراهم میآورد.
پیادهسازی یک زبا ن دادهکاوی انعطافپذیر، با امکان در اختیار گذاشتن انواع روشهای موجود و امکان وارد کردن پارامترهای جدید، بدون وابستگی خاص به محیط و یا پلاتفرم دیگری و با سرعت اجرای قابلقبول، برای هرکسی که به اهمیت موضوع پی برده باشد، میتواند یک «شهر آرزوها» باشد.
تا کنون تلاشهای بسیاری به همین منظور صورت گرفته است. ولی متاسفانه هر کدام از این تلاشها دارای نقاط ضعف عمدهای میباشد که آنها را عملا برای بسیاری از موارد بلااستفاده ساخته است. مهمترین محصول تولیدی در این قسمت زبان DMQL میباشد، که بر روی محیط خاص DBMiner کار میکند.
همچنین تلاشهای پراکندهای در مورد کلی1 کردن الگوریتمها و یا تبدیل الگوریتمهای موجود به الگوریتمهای بر پایهی SQL انجام شده است، که از آنجمله میتوان به کلی کردن الگوریتمهای پیدا کردن قوانین وابستهسازی در دادهها یا الگوریتم EM اشاره نمود، که در بخش های بعدی مفصلا در مورد آنها صحبت خواهیم کرد.
در این رساله ابتدا در بخش دوم، پروسهی کشف دانش از پایگاه داده را به اجمال همراه با مراحل آن بررسی میکنیم و نگاهی هم به زبانهای دادهکاوی موجود میاندازیم. در بخش سوم انواع معماریهای ممکن برای این منظور را بررسی کرده و معماری مورد نظر خود را ارایه میدهیم. در بخش چهارم آمادهسازی دادهها را تا مرحلهای که بتوان الگوریتمها را بر روی آن اعمال کرد، توضیح داده و همچنین اعمالی را که ما برای این منظور در نظر گرفتهایم بیان میکنیم. بخشهای پنجم تا هفتم به بررسی سه دسته از روشهای اصلی در دادهکاوی، آنها را همراه با جزییات کامل مطالعه کرده و همچنین در هر قسمت، نحوهی پشتیبانی FlexQG را از این روشها بیان میکنیم. در بخش هشتم، توضیح و پیادهسازی الگوریتم کلی کاوش قوانین وابستهسازی، با استفاده از رهیافت SQL آمده است. بخش نهم نیز به توضیح و نحوهی پیادهسازی چارچوب2 کلی الگوریتمهای خوشهبندی تفکیکی (EM) ، بر پایهی SQL، میپردازد نهایتا در بخش آخر به نتیجهگیری کلی خواهیم پرداخت.
۲- پروسهی کشف دانش از پایگاه داده3
یک پایگاه داده یک ذخیرهسازی اطلاعات قابل اطمینان است، یکی از اهداف اولیه و اصلی این ذخیرهسازی بازیابی موثر اطلاعات میباشد. این اطلاعات بازیابی شونده لزوما یک کپی از اطلاعات ذخیره شده در پایگاه داده نیستند، بلکه اطلاعات استنتاجی از آن میباشند. دو نوع استنتاج از اطلاعات یک پایگاه داده داریم: [Holsheimer94]
استنتاج قیاسی4: یک تکنیک برای استنتاج اطلاعات است که یک سلسله مراتب منطقی از اطلاعات پایگاه داده میباشد. اکثر سیستمهای مدیریت پایگاه دادهها5، مانند سیستمهای مدیریت پایگاه دادههای رابطهای، اپراتورهای سادهای را برای استنتاج اطلاعات در اختیار میگذارند. برای مثال یک اپراتور join بین دو جدول Employee-Department و Manager-Department در مجموع یک ارتباط بین کارمندان و مدیران را نتیجه میدهند.
استنتاج استقرایی 6: یک تکنیک برای استنتاج اطلاعاتی است که از اطلاعات موجود در پایگاه داده استنباط7 میشود. برای مثال از جداول Employee-Department و Department-manager مثالِ بالا، ممکن است این نتیجهگیری حاصل شود که هر کارمند یک مدیر دارد.
جستجو برای این اطلاعاتِ سطح بالا (یا در اصطلاح، دانش)، هدف پروسهی KDD میباشد. در پروسهی KDD ما به دنبال الگوهایی با ساختار Association Ruleها یا عبارات منطقی هستیم.
تعریف: KDD یا کشف دانش از پایگاه داده یک پروسهی علمی برای شناسایی الگوهای معتبر، نوین، بالقوه مفید و قابل فهم از دادهها میباشد. [Breiman96]
داده کاوی: یک مرحله از پروسهی KDD میباشد که با استفاده از الگوریتمهای کاوش مشخصی یک سری الگوها را از پایگاه داده استخراج میکند.
۱-۲- ویژگیهای KDD
ویژگیهای زیادی برای یک پروسهی KDD در نوشتجات مختلف ذکر شده است. در اینجا مراحل این پروسه را بر اساس یکی از این نوشتهها بصورت زیر عنوان میکنیم: [John97]
استخراج دادهها
آماده کردن دادهها
مهندسی دادهها
مهندسی الگوریتم و تعیین استراتژیهای کاوش
اجرای الگوریتم کاوش
تحلیل دادهها و ارزیابی