چکیده :
پروسهی کشف دانش از پایگاه داده، یک پروسهی علمی برای شناسایی الگوهای معتبر، نوین، بالقوه مفید و قابل فهم از دادهها میباشد. مهمترین بخش این پروسه، کاوش دادهها میباشد که با استفاده از الگوریتمهای مشخصی یک سری الگوها را از پایگاه داده استخراج میکند.در این پروژه هدف ما طراحی یک زبان سطح بالای انعطافپذیر برای دادهکاوی اطلاعات میباشد.
این کار علاوه بر کمک به محققان این زمینه برای بررسی روشهای جدید و تست سریع و کارای الگوریتمهای کاوش، امکان استفاده از این روشها را به سادگی برای کسانی که اطلاعات اندکی در این زمینه دارند، نیزفراهم میآورد.در این رساله پروسهی کشف دانش از پایگاه داده، همراه با مراحل آن، زبانهای دادهکاوی موجود و انواع معماریهای ممکن برای این زبانها بررسی شده است. سپس معماری مورد نظر ارایه شده است. در ادامه سعی شده است تا روشهای مختلف کاوش، عام شده و جهت بکارگیری در زبان Flexible Query Generator (FlexQG)، آماده شوند.پس از تکمیل گرامر زبان، با هدفهای مورد نظر، جهت تکمیل کار، دو نمونه از روشهای کاوش کلی، با زبان SQL، پیادهسازی شدهاند.
مقدمه
رشد روزافزون و انفجاری دادهها در عصر حاضر، پایگاههای داده را به عنوان جز لاینفکی در همهی زمینههای کامپیوتر قرار داده است. اما با این سیل عظیم اطلاعات و نیازهای گستردهی امروزی تنها نمیتوان به اطلاعات بازیابی شوندهای از بانکهای اطلاعاتی که تنها یک کپی از اطلاعات ذخیره شده در پایگاه داده هستند، دل، خوش کرد، بلکه باید راههایی برای استخراج دانش موجود در این دادهها پیدا کرد.به این منظور پروسهی کشف دانش از پایگاه داده مطرح شد که یک پروسهی علمی برای شناسایی الگوهای معتبر، نوین، بالقوه مفید و قابل فهم از دادهها میباشد. مهمترین بخش این پروسه، کاوش دادهها میباشد که با استفاده از الگوریتمهای مشخصی یک سری الگوها را از پایگاه داده استخراج میکند.در این پروژه هدف ما طراحی یک زبان سطح بالای انعطافپذیر برای دادهکاوی اطلاعات میباشد. این کار علاوه بر کمک به محققان این زمینه برای بررسی روشهای جدید و تست سریع و کارای الگوریتمهای کاوش، امکان استفاده از این روشها را به سادگی برای کسانی که اطلاعات اندکی در این زمینه دارند، را نیزفراهم میآورد.
فهرست مطالب
۱- مقدمه ۱
۲- پروسهی کشف دانش از پایگاه داده ۳
۱-۲- ویژگیهای 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 ۵۴
مراجع و منابع ۵۸