بسم‌ الله الرحمن الرحيم


















طراحي يک زبان توليد پرس‌وجوي انعطاف‌پذير براي داده‌کاوي
(FlexQG)









تهيه‌کننده: جعفر محمدي
استاد راهنما: دکتر محمدرضا کنگاوري

زمان ارايه: آبان ۸۲


چکيده

پروسه‌ي كشف دانش از پايگاه داده، يك پروسه‌ي علمي‌ براي شناسايي الگوهاي معتبر، نوين، بالقوه مفيد و قابل فهم از داده‌ها مي‌‌باشد. مهم‌ترين بخش اين پروسه، کاوش داده‌ها مي‌باشد که با استفاده از الگوريتم‌هاي مشخصي يك سري الگوها را از پايگاه داده استخراج مي‌‌كند.
در اين پروژه هدف ما طراحي يک زبان سطح بالاي انعطاف‌پذير براي داده‌کاوي اطلاعات مي‌باشد. اين کار علاوه بر کمک به محققان اين زمينه براي بررسي روش‌هاي جديد و تست سريع و کاراي الگوريتم‌هاي کاوش، امکان استفاده از اين روش‌ها را به سادگي براي کساني که اطلاعات اندکي در اين زمينه دارند، نيزفراهم مي‌آورد.
در اين رساله پروسه‌ي كشف دانش از پايگاه داده، همراه با مراحل آن، زبان‌هاي داده‌کاوي موجود و انواع معماري‌هاي ممکن براي اين زبان‌ها بررسي شده است. سپس معماري مورد نظر ارايه شده است. در ادامه سعي شده است تا روش‌هاي مختلف کاوش، عام شده و جهت بکارگيري در زبان 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 ۵۴
مراجع و منابع ۵۸




۱- مقدمه

رشد روزافزون و انفجاري داده‌ها در عصر حاضر، پايگاه‌هاي داده را به عنوان جز لاينفکي در همه‌ي زمينه‌هاي کامپيوتر قرار داده است. اما با اين سيل عظيم اطلاعات و نيازهاي گسترده‌ي امروزي تنها نمي‌توان به اطلاعات بازيابي شونده‌اي از بانک‌هاي اطلاعاتي که تنها يك كپي از اطلاعات ذخيره شده در پايگاه داده هستند، دل، خوش کرد، بلکه بايد راه‌هايي براي استخراج دانش موجود در اين داده‌ها پيدا کرد.
به اين منظور پروسه‌ي كشف دانش از پايگاه داده مطرح شد که يك پروسه‌ي علمي‌ براي شناسايي الگوهاي معتبر، نوين، بالقوه مفيد و قابل فهم از داده‌ها مي‌‌باشد. مهم‌ترين بخش اين پروسه، کاوش داده‌ها مي‌باشد که با استفاده از الگوريتم‌هاي مشخصي يك سري الگوها را از پايگاه داده استخراج مي‌‌كند.
در اين پروژه هدف ما طراحي يک زبان سطح بالاي انعطاف‌پذير براي داده‌کاوي اطلاعات مي‌باشد. اين کار علاوه بر کمک به محققان اين زمينه براي بررسي روش‌هاي جديد و تست سريع و کاراي الگوريتم‌هاي کاوش، امکان استفاده از اين روش‌ها را به سادگي براي کساني که اطلاعات اندکي در اين زمينه دارند، را نيزفراهم مي‌آورد.
پياده‌سازي يک زبا ن داده‌کاوي انعطاف‌پذير، با امکان در اختيار گذاشتن انواع روش‌هاي موجود و امکان وارد کردن پارامترهاي جديد، بدون وابستگي خاص به محيط و يا پلاتفرم ديگري و با سرعت اجراي قابل‌قبول، براي هرکسي که به اهميت موضوع پي برده باشد، مي‌تواند يک «شهر آرزوها» باشد.
تا کنون تلاش‌هاي بسياري به همين منظور صورت گرفته است. ولي متاسفانه هر کدام از اين تلاش‌ها داراي نقاط ضعف عمده‌اي مي‌باشد که آن‌ها را عملا براي بسياري از موارد بلااستفاده ساخته است. مهمترين محصول توليدي در اين قسمت زبان DMQL مي‌‌باشد، که بر روي محيط خاص DBMiner کار مي‌کند.
همچنين تلاش‌هاي پراکنده‌اي در مورد کلي کردن الگوريتم‌ها و يا تبديل الگوريتم‌هاي موجود به الگوريتم‌هاي بر پايه‌ي SQL انجام شده است، که از آن‌جمله مي‌توان به کلي کردن الگوريتم‌هاي پيدا کردن قوانين وابسته‌سازي در داده‌ها يا الگوريتم EM اشاره نمود، که در بخش هاي بعدي مفصلا در مورد آن‌ها صحبت خواهيم کرد.
در اين رساله ابتدا در بخش دوم، پروسه‌ي كشف دانش از پايگاه داده را به اجمال همراه با مراحل آن بررسي مي‌کنيم و نگاهي هم به زبان‌هاي داده‌کاوي موجود مي‌اندازيم. در بخش سوم انواع معماري‌هاي ممکن براي اين منظور را بررسي کرده و معماري مورد نظر خود را ارايه مي‌دهيم. در بخش چهارم آماده‌سازي داده‌ها را تا مرحله‌اي که بتوان الگوريتم‌ها را بر روي آن اعمال کرد، توضيح داده و همچنين اعمالي را که ما براي اين منظور در نظر گرفته‌ايم بيان مي‌کنيم. بخش‌هاي پنجم تا هفتم به بررسي سه دسته از روش‌هاي اصلي در داده‌کاوي، آنها را همراه با جزييات کامل مطالعه کرده و همچنين در هر قسمت، نحوه‌ي پشتيباني FlexQG را از اين روش‌ها بيان مي‌کنيم. در بخش هشتم، توضيح و پياده‌سازي الگوريتم کلي کاوش قوانين وابسته‌سازي، با استفاده از رهيافت SQL آمده است. بخش نهم نيز به توضيح و نحوه‌ي پياده‌سازي چارچوب کلي الگوريتم‌هاي خوشه‌بندي تفکيکي (EM) ، بر پايه‌ي SQL، مي‌پردازد نهايتا در بخش آخر به نتيجه‌گيري کلي خواهيم پرداخت.




۲- پروسه‌ي كشف دانش از پايگاه داده


يك پايگاه داده ‌يك ذخيره‌سازي اطلاعات قابل اطمينان است، يكي از اهداف اوليه و اصلي اين ذخيره‌سازي بازيابي موثر اطلاعات مي‌‌باشد. اين اطلاعات بازيابي شونده لزوما يك كپي از اطلاعات ذخيره شده در پايگاه داده نيستند، بلكه اطلاعات استنتاجي از آن مي‌باشند. دو نوع استنتاج از اطلاعات يك پايگاه داده داريم: [Holsheimer94]
• استنتاج قياسي : يك تكنيك براي استنتاج اطلاعات است كه ‌يك سلسله مراتب منطقي از اطلاعات پايگاه داده مي‌‌باشد. اكثر سيستم‌هاي مديريت پايگاه داده‌ها ، مانند سيستم‌هاي مديريت پايگاه داده‌هاي رابطه‌اي، اپراتورهاي ساده‌اي را براي استنتاج اطلاعات در اختيار مي‌‌گذارند. براي مثال يك اپراتور join بين دو جدول Employee-Department و Manager-Department در مجموع يك ارتباط بين كارمندان و مديران را نتيجه مي‌‌دهند.
• استنتاج استقرايي : يك تكنيك براي استنتاج اطلاعاتي است كه از اطلاعات موجود در پايگاه داده استنباط مي‌‌شود. براي مثال از جداول Employee-Department و Department-manager مثالِ بالا، ممكن است اين نتيجه‌گيري حاصل شود كه هر كارمند يك مدير دارد.
جستجو براي اين اطلاعاتِ سطح بالا (يا در اصطلاح، دانش)، هدف پروسه‌ي KDD مي‌‌باشد. در پروسه‌‌ي KDD ما به دنبال الگوهايي با ساختار Association Ruleها يا عبارات منطقي هستيم.
تعريف: KDD يا كشف دانش از پايگاه داده‌ يك پروسه‌ي علمي‌ براي شناسايي الگوهاي معتبر، نوين، بالقوه مفيد و قابل فهم از داده‌ها مي‌‌باشد. [Breiman96]

داده كاوي: يك مرحله از پروسه‌ي KDD مي‌‌باشد كه با استفاده از الگوريتم‌هاي كاوش مشخصي يك سري الگوها را از پايگاه داده استخراج مي‌‌كند.


۱-۲- ويژگي‌هاي KDD
ويژگي‌هاي زيادي براي يك پروسه‌ي KDD در نوشتجات مختلف ذكر شده است. در اينجا مراحل اين پروسه را بر اساس يكي از اين نوشته‌ها بصورت زير عنوان مي‌‌كنيم: [John97]
• استخراج داده‌ها
• آماده کردن داده‌ها
• مهندسي داده‌ها
• مهندسي الگوريتم و تعيين استراتژي‌هاي کاوش
• اجراي الگوريتم كاوش
• تحليل داده‌ها و ارزيابي





شکل ۱-۲: مراحل پروسه‌ي کشف دانش

۱-۱-۲- استخراج داده‌ها
موقعي كه ‌يك مساله تعريف شد، بايد داده‌هاي وابسته به آن مساله جمع‌آوري شوند. در بسياري از موارد، داده‌هاي مورد نياز از يك پايگاه داده ‌يا انبار داده‌ها استخراج مي‌‌گردند. معمولا الگوريتم‌هاي داده‌كاوي نمي‌‌توانند مستقيما روي داده‌هاي بانك اطلاعات اجرا شوند، در اينگونه موارد بايد داده‌ها قبل از اعمال الگوريتم‌ها، آماده شوند.

۲-۱-۲- آماده کردن داده‌ها
از آنجايي كه داده‌هاي مورد نظر جمع‌آوري شده‌اند، خيلي مهم است كه آگاه باشيم كه اين داده‌ها نياز به پاكسازي دارند و ما بايد زمان زيادي را صرف اين‌ كار بكنيم. زيرا بسياري از منابع خطا، مي‌‌توانند هنگام جمع‌آوري داده‌ها از چندين پايگاه داده در يك پايگاه داده تحليلي، موجود باشند و يك تحليلگر خوب ناچار است بسياري از بررسي‌هاي اعتبار داده‌اي را بر روي داده‌هاي استخراج شده، انجام دهد. بسيار نادر اتفاق مي‌‌افتد كه داده‌هاي جمع‌آوري شده داراي مشكل نباشند.[Berger2001]

۳-۱-۲- مهندسي داده‌ها
بعد از انجام مراحل فوق سه مشكل اصلي هنوز وجود دارد:[Berger2001]
• ممكن است چشمپوشي از تعدادي از ويژگي‌هاي داده‌ها براي ما سودمند باشد. چون ممكن است كه بخواهيم noiseها را از داده‌ها جدا كنيم.
• ممكن است مجبور باشيم به دليل ناكارآمدي الگوريتم‌هاي داده‌‌کاوي داده‌هايمان را به‌يك مجموعه داده‌ي ساده‌تر تقليل دهيم.
• بسياري از داده‌ها ممكن است كه بصورت ديگري غير از اين شكل بيان شوند كه بسيار مفيدتر باشند. مثلا براي خصوصيت جنسيت، مي‌‌توانيم اگر اين ويژگي متني باشد، آن‌را به دودويي ‌تبديل كرده و female را مثلا صفر و male را يک در نظر بگيريم.

۴-۱-۲- مهندسي الگوريتم و تعيين استراتژي‌هاي کاوش
تعداد الگوريتم‌هاي بسيار زيادي كه در زيرِ هر كدام از متدها قرار مي‌‌گيرند، مي‌‌توانند حتي براي افراد حرفه‌اي هم گيج‌كننده باشند. اين نكته بايد ذكر شود كه همه‌ي اين الگوريتم‌ها داراي تكنيك‌هاي پايه‌ايِ يكساني هستند.[Fayyad96]
انواع مختلفي از الگوريتم‌هاي داده‌كاوي وجود دارند. مدل‌هاي مشهور، از قوانين و درخت‌هاي تصميم، رگرسيون و كلاسه‌بندي غيرخطي، متدهاي مبتني بر مثال (شامل متدهاي نزديكترين همسايه و استنتاج بر اساس مورد )، مدل‌هاي آماري (نظير شبكه‌هاي بيز، تابع توزيع احتمال نرمال، تابع توزيع احتمال χ2 و...) و مدل‌هاي يادگيري رابطه‌اي (نظير برنامه‌نويسي منطقي استنتاجي)، استفاده مي‌‌كنند. لازم به ذكر است كه هر تكنيك براي انواع مختلفي از مسايل بهتر از ساير تكنيك‌ها عمل مي‌‌كند. براي مثال كلاسه‌بندي‌هاي درخت تقسيم براي پيدا كردن ساختار در فضاهاي با ابعاد بالا و همچنين در مسايل با داده‌هايي كه مي‌‌توانند پيوسته‌يا طبقه بندي شده باشند، مفيد خواهد بود (زيرا متدهاي بر پايه‌ي درخت نياز به فواصل متريك ندارند)، در حالي‌كه اين درخت‌ها براي مسايلي كه نياز به مرزبندي دقيق بين كلاس‌ها دارند، مفيد نمي‌‌باشد. بنابراين هيچ متد داده‌ كاوي واحدي نمي‌‌تواند وجود داشته باشد و انتخاب يك الگوريتم مشخص براي كاربردهاي ويژه نياز به مهارتهاي خاصي دارد.
در عمل به علت گستردگي، پيچيدگي و حجم بسيار بالاي داده‌هاي موجود براي يك كاربرد خاص و نياز به بهينه‌سازي انها، دامنه متدهاي مفيد محدود شده است.[Fayyad96]
اين مرحله يعني اينکه مفيدتر است كه براي يك منظور خاص و بر روي يك سري داده‌هاي ويژه، چه الگوريتمي‌ اعمال شود كه بهترين كارايي را براي ما داشته باشد؟

۵-۱-۲- اجراي الگوريتم كاوش و ارزيابي نتايج
مرحله‌ي اجراي الگوريتم مرحله‌اي است كه كافي است الگوريتم به اجرا كننده داده شود و ما راحت به صندلي تكيه دهيم و نتايج را نگاه كنيم. مساله‌اي كه در اين مرحله قابل توجه است نحوه‌ي تقسيم كرده داده‌ها به مجموعه‌ي آموزشي و مجموعه‌ي تست مي‌‌باشد، كه اين كار مشمول زبان پرس‌وجوي ما نمي‌‌شود.

۲-۲- زبان‌هاي پرسشي داده‌کاوي :
با رشد سريع انبارهاي داده و افزايش اطلاعات موجود در شكبه‌هاي اطلاعاتي، به روش‌هاي جديدي در زمينه بازيابي اطلاعات با ارزش نياز مي‌باشد. قاعدتاً با ارايه تكنيك‌هاي نوين و زبان‌هاي پرسشي داده‌کاوي پيشرفته،
كاربردانبارهاي داده نيز به مراتب افزايش مي‌يابد.
در گذشته و حال، به منظور جمع‌آوري مستندات مورد نظر، تكنيك‌هاي مختلف بازيابي اطلاعات و موتورهاي جستجو مورد استفاده قرار گرفته است. اما هيچكدام از اين ابزار، قادر به استخراج دانش نبوده، به همين خاطر کارايي مطلوب چندان مناسبي از خود نشان نداده‌اند. به عنوان نمونه موتورهاي جستجو مانند YAHOO بر اساس شاخص‌ها، شبكه را مورد بازنمايي قرار داده، با تركيب نتايج، پاسخ‌هاي بدست آمده را نمايش مي‌دهند. اما اين ابزار جستجو به اطلاعات ساختاري و سازماندهي مستندات به بخش‌هاي كوچكتر، توجهي مبذول نمي‌دارند. ضمنا تعداد پاسخ‌هاي ارايه شده بسيار زياد مي‌باشد به‌طوري‌كه يافتن مسيرهاي صحيح براي پاسخ بسيار مشكل است. [Gam96]
امروزه روشهاي ايندكس‌گذاري بهتر، استفاده از عامل‌هاي جمع‌آوري اطلاعات خاص، روش‌هاي فيلتركردن بهبود كارايي در عمل جستجو، در قالب زبان‌هايي به نام زبان‌هاي پرسشي سطح بالا و با هدف استخراج دانش ارايه شده است. يكي از زمينه‌هاي جديد تحقيقاتي در راستاي بازيابي اطلاعات پرس‌وجو و زبان پرس‌و‌جو مي‌باشد.
طبقه‌بندي زبان‌هاي پرس‌وجو، با توجه به محيط و نوع بانك اطلاعات و انبار داده‌ي مورد نياز، عبارتست از:
• زبان‌هاي پرسشي تعريف شده بر روي داده‌هاي غير ساختاري
زبان‌هاي پرسشي تعريف شده بر روي داده‌هاي غير ساختاري زبان‌هايي هستند كه بر روي انواع مختلف داده‌هاي غير ساختاري مانند بانك‌اي اطلاعات متني، فضايي و غيره تعريف شده‌‌اند. مانند زبان‌هاي كاوش UnQL، WebSQL، WebOQL.
• زبان هاي پرسشي تعريف شده بر روي داده‌هاي ساخت يافته
اين دسته از انواع زبان‌هاي پرسشي داده‌کاوي، عمل كاوش و استخراج دانش را بر روي بانك اطلاعات انجام مي‌دهند. زبان داده‌کاوي DMQL مثالي از اين دسته مي‌باشد.
زبان پرسشي داده‌کاوي DMQL نمونه‌اي متعلق به دسته اخير مي‌باشد. اين زبان قابليت داده‌کاوي درچند سطح را بر روي بانك‌هاي اطلاعات رابطه‌اي دارا بوده، تعاملي و با واسطه‌ي كاربر انعطاف‌پذير مي‌باشد. در اين زبان پرسشي داده‌کاوي، مواردي همچون خلاصه‌سازي داده‌ها، كاوش قوانين از نوع وابسته‌سازي، کلاسه‌بندي، خوشه‌بندي و يافتن الگوهاي ويژه، منظور شده است. واسطه‌ي كاربر مربوط به اين زبان، به صورتي انعطاف‌پذير، قابليت اشكال‌زدايي و جستجوي چند سطحي را براي كاربران ميسرنموده، امكاناتي همچون جداول، چارت‌ها، راهنما و انتخاب‌هاي پويا را در اختيار آنان قرار مي دهد. [Han96] اين زبان، بر روي سيستم DBMiner قابل اجرا مي‌باشد.



-۳ معماري FlexQG

در اين قسمت مي‌خواهيم ويژگي‌ها، مشخصات و معماري زبان خود را بيان نماييم. ما زبان پرس‌وجوي انعطاف‌پذير و سطح بالايي مي‌خواهيم که الگوريتم‌هاي کاوش را براي ما اجرا کنند. براي اجراي اين پرس‌وجوها، دو راه انتخاب وجود دارد، يکي اينکه ابتدا مجموعه داده‌هايي که مي بايستي روي آنها پردازش صورت بگيرد، توسط يک عبارت SQL استخراج گرديده و سپس در يک محيط برنامه‌نويسي روي اين داده‌ها پردازش‌هاي لازم صورت پذيرد و سپس نتايج برگشت داده شوند. دومين راه ممکن اين است که کل عبارات انتخاب‌گر داده‌هاي مورد نظر، همراه با الگوريتمي که مي‌خواهيم اعمال کنيم به يک عبارت SQL استاندارد ترجمه شده و سپس با اتصال به يک DBMS، اين عبارت، مثل يک عبارت SQL معمولي اجرا مي‌گردد.
در مورد انتخاب محيط پياده‌سازي مناسب، بايد ذکر گردد که محيطي که قرار است انتخاب شود، کاملا بستگي به استراتژي‌اي دارد که در مرحله‌ي اول اتخاذ مي‌کنيم، براي هر دو گزينه‌ي فوق راه‌هاي زير پيشنهاد مي‌شود:
• اگر رهيافت اول مورد استفاده قرار گيرد: در اين صورت محيط برنامه‌نويسي مناسب، محيطي مي‌باشد که ضمن توانمندي بالا، امکانات کار با بانک‌هاي اطلاعاتي و استفاده‌ي راحت، داراي سرعت بالايي نيز باشد. چون در اين رهيافت، بار کاري روي قسمت پردازش مي‌باشد، پس زبان ما بايد، داراي امکانات پردازشي بالايي باشد.
• اگر رهيافت دوم مورد استفاده قرار گيرد: در اين صورت ادامه‌ي کار يعني کار کردن بر روي عبارات SQL وتوليد عبارت‌هاي خروجي و در نهايت گذاشتن بار کاري پردازشي بر روي DBMS.
امروزه، پايگاه داده‌هايي، با صدها فيلد و جدول و ميليون‌ها ركورد، با چند گيگا بايت اندازه، بسيار معمول شده‌اند. پايگاه داده‌هاي با اندازه‌ ترابايت (12 بايت) نيز در حال ظهور هستند. حجم عظيم از داده‌ها، حتي بسياري از الگوريتم‌ها وحتي روش‌ها را نيز به دليل سرعت پايين پردازش‌هاي آن‌ها، ناكارامد كرده است. بهمين دليل اگر سرعت رشد بهمين صورت ادامه پيدا كند، هم از لحاظ سرعت و هم از لحاظ فضاهاي اضافي مورد نياز روش‌هاي غير SQL–Based، ناكارامدتر از گذشته خواهند شد. [Fayyad96]
ما بنا به دلايل زير مايل به استفاده از رهيافت اول هستيم:

۱-۳- دلايل اقبال و رويكرد ما به روش‌ها و الگوريتم‌هاي بر پايه‌ي SQL:
اولا ذکر اين نکته ضروري است که تفاوت بين پياده‌سازي‌ها وقتي خود را نشان مي‌دهند كه اين واقعيت را بياد آوريم كه ما در داده‌كاوي معمولا با مجموعه‌ي داده‌هايي بسيار بزرگ با حجم و ابعاد بالا سر و كار داريم. در زير مختصرا چند تا از دلايل خود را براي استفاده از SQL ذكر مي‌كنيم :
• عدم نياز به حافظه‌هاي اضافي. تعداد زيادي از الگوريتم‌ها هنگام مواجهه با حجم بسيار بالاي داده‌ها، از لحاظ حافظه‌ي اصلي مورد، نياز به مشکل برمي‌خورند. در حاليکه استفاده از رهيافت SQL به حافظه‌ي اضافي نيازي ندارند، زيرا الگوريتم‌ها در همان فضاي DBMS اجرا مي‌گردند.
• انتقال داده‌ها از انبارهاي داده‌اي كه بستر اصلي پياده‌سازي اين الگوريتم‌ها هستند به محيط‌هاي زبان‌هاي ديگر، كاري است بسيار زمانبر، با احتمال رخداد خطاي بالا و در ضمن مشكل. براي مثال اگر در نظر بگيريم كه ما مي‌خواهيم يك الگوريتم خوشه‌بندي داده‌ها را روي يك جدول با بيش از يكصد ميليون ركورد انجام دهيم، مشاهده مي‌كنيم كه مديريت صحيح اين داده‌ها و نقل و انتقال آن‌ها، خود مساله‌ي پيچيده‌تر از اعمال الگوريتم مي‌باشد. توليد كردن عبارات SQL در خروجي يعني فقط تكيه كردن بر روي DBMSها براي داده‌هايي كه بر روي DBMSها هستند و همچنين يعني جدا كردن مديريت الگوريتم‌ها از مديريت داده‌ها.
• بعلّت پشتيباني بسياري از DBMSها از Queryهاي موازي، پياده‌سازي بروش SQL مي‌‌تواند به آساني بطور موازي اجرا گردد.
• امكان استفاده از توانايي‌هاي ايندكس گذاري پايگاه داده و پردازش پرس‌و‌جو . [Sarawagi]
• باعث مي‌‌شود كه سيستم‌ها قوي، قابل حمل و قابل گسترش شوند.[Sarawagi, Rajamani98]
• پشتيباني DBMS براي Checkpointing و مديريت فضا براي الگوريتم‌هاي داده كاوي، مي‌‌توانند بسيار ارزشمند باشند. [Sarawagi]
• در بسياري از موارد ممكن است كدهاي خروجي حاصل از الگوريتم‌ها، غير بهينه بوده و از لحاظ هزينه‌ي اجرايي ناكارامد باشند، در حالي كه اگر كليه‌ي الگوريتم‌هاي ما با عبارات SQL بيان شده باشد و اين خروجي‌ها برروي DBMS هايي اجرا گردند كه داراي بهينه‌گرهاي پرس‌وجوهاي SQL باشند-امروزه اكثر DBMSهاي مشهور داراي بهينه‌گرها مي‌باشند- خودبه‌خود كدهاي ما بهينه گرديده و سرعت كار بالا مي‌رود.
• و آخرين نكته اينكه، چون فاز اجراي الگوريتم‌هاي ما را DBMSها بر عهده دارند، هرگاه امكانات و قابليت‌هاي Queryگيري‌هاي اين ابزارها اضافه گردد، خودبخود Query‌هاي ما نيز از کارايي بيشتري برخوردار خواهند شد [Rajamani98]

۲-۳- چه مشكلاتي در سر راه پياده‌سازي اين رهيافت وجود دارند؟
عليرغم كليه‌ي خوبي‌هايي كه در اينجا مشاهده كرديم، در اين راه به مشكلات اساسي بر خواهيم خورد اهم مشكلاتي كه پيش‌بيني مي‌گردند، بصورت زير ليست مي‌گردند:
• SQL بر پايه‌ي مدل رابطه‌اي بوده، قادر به اجراي عملكرهاي رابطه‌اي مي‌باشد و از عملكرهاي جبر خطي پشتيباني نمي‌كند، در حاليکه در الگوريتم‌هاي داده‌کاوي اين عملگرها شديدا مورد نياز بوده و بوفور استفاده مي‌شوند.
• در DBMS هاي رابطه‌اي كه ما با آن‌ها سر و كار داريم، داده‌ها در جداول ذخيره مي‌شوند، بنابراين موجودي به نام آرايه در اين بين وجود نخواهد داشت در حالي‌كه تصور پياده‌سازي اكثر الگوريتم‌هاي داده كاوي، بدون استفاده از آرايه، بيشتر به يك كابوس شباهت دارند تا واقعيت.
• براي عبارت SQL يك محدوديت ماكزيمم طول براي Queryها را داريم، در حالي‌كه Queryهايي كه نتيجه‌ي كارِ ما مي‌باشند، معمولا از اين مقدار حدي تجاوز خواهند كرد.
• و آخرين مشكل اساسي اينكه DBMS، عبارات SQL را بصورت موازي اجرا كرده و ممکن است نتايجي را كه برگشت مي‌دهد، در يك ترتيب غير قابل پيش بيني ‌باشند.

۳-۳- انواع معماري‌هاي ممکن
حال که به ويژگي‌هاي مثبت SQL پي برديم، در اينجا انواع معماري‌هاي ممکن را براي اين منظور بررسي مي‌کنيم:

۱-۳-۳- خواندن مستقيم از DBMS: داده‌ها مستقيم گروه گروه از DBMS به كرنل كاوش خوانده مي‌‌شوند. براي اين‌كار دو رهيافت وجود دارد:[Sarawagi]
• رهيافت Loose-Coupling، كه DBMS روي يك فضاي آدرس متفاوت از پروسه‌ي كاوش اجرا مي‌‌شود. اين رهيافت در اكثر سيستم‌هاي كاوش موجود مورد استفاده قرار مي‌‌گيرد. يك مشكل بالقوه در اين رهيافت، هزينه‌ي بسيار بالاي راه‌گزيني بين DBMS و كرنل كاوش مي‌‌باشد، عليرغم اين‌كه در بسياري از سيستم‌ها بهينه‌سازي‌هايي براي خواندن بلاك‌هاي داده انجام شده است.
• رهيافت Stored Procedure : كه در آن الگوريتم كاوش به صورت يك روال ذخيره شده بسته‌بندي مي‌شود و در همان فضاي آدرس DBMS اجرا مي‌شود. مزيت‌ هر دو روش فوق‌ انعطاف‌پذيري بالاي آن‌ها و عدم استفاده از فضاي اضافي مي‌‌باشد. نتايج نيز در همان DBMS ذخيره مي‌‌گردند.

۲-۳-۳- استفاده از توابع تعريف كاربر : در اين معماري يك الگوريتم كاوش به صورت مجموعه‌اي از UDF ‌ها بيان مي‌‌شود، كه در Query ‌هاي SQL قرار دارند. UDF‌ها در فضاي آدرس DBMS اجرا مي‌‌شوند. اين پياده‌سازي در [Agrawal96] معرفي شده است. جاذبه و برتري اصلي اين روش بر روش‌ روال‌هاي ذخيره شده اين است كه فرستادن گروه و ركورد‌هاي داده‌اي به‌يك روال ذخيره شده كندتر از ارسال آن‌ها به‌يك UDF است، ولي ساير پردازش‌هايي كه اتفاق مي‌‌افتاد در هر دو روش يكسان است.

۴-۳- معماري مورد استفاده
معماري‌‌اي كه در نظر گرفته‌ايم در شكل زير نشان داده شده است. پرس و جوها از طريق يك واسطه‌ي كاربر گرافيكي به سيستم اعمال شده، پس از تفسير پرس‌و‌جوهاي FlexQG، نتيجه‌ به صورت پرس‌و‌جوهاي استاندارد SQL در قالب UDF ارائه مي‌گردد.
اين پرس‌و‌جوهاي خروجي، در DBMSهاي رابطه‌اي از جمله SQL Server قابل اجرا مي‌باشند. با استفاده از امکاناتي نظيرOLAP در SQL Server مي‌توان نتيجه‌ي پرس و جوها را در قالب نمودارهاي آماري و در اشكال گوناگون به نمايش گذاشت.





شکل ۱-۳: معماري FlexQG
FlexQG Compiler، ترجمه‌ي SQL مناسب را براي الگوريتم خاص معرفي شده توسط پرس‌و‌جوي FlexQG توليد مي‌‌كند. اين ترجمه قابل اجرا بر روي يك موتور ارتباطي SQL-92 خو اهد بود. در اين موتور SQL موردنظر، مي‌‌بايستي توابع تعريف شده توسط كاربر پشتيباني شوند.

۵-۳- روش‌هاي کاوش مورد پشتيباني

از بين تمامي روش‌هاي موجود کاوش داده‌ها، سه روش در تقسيم‌بندي کلي مي‌گنجند که ما هر ه روش را پشتيباني خواهيم کرد: قوانين کلاسه بندي، وابسته‌سازي و خوشه‌بندي.
يك قانون کلاسه‌بندي ، يك مجموعه از قوانيني است كه مجموعه داده‌هاي مربوطه را كلاسه‌بندي مي‌‌كنند و سپس يك مجموعه از قوانين وابسته با هر كلاس يا زير كلاس را بر مي‌‌گرداند. [han96]
يك قانون وابسته‌سازي ، روابط وابستگي بين يك مجموعه از داده‌ها را توصيف مي‌‌كند. [han96]
خوشه‌بندي به فرآيند تقسيم مجموعه‌اي از داده‌ها (يا اشيا) به زير كلاس‌هايي با مفهوم خوشه‌ اتلاق مي‌شود. به اين ترتيب يك خوشه‌ يك‌ سري داده‌هاي مشابه مي‌باشد كه همانند يك گروه واحد رفتاري مي‌كنند. لازم به ذكر است خوشه‌بندي همان کلاسه‌بندي است با اين تفاوت كه كلاس‌ها از پيش‌تعريف‌شده و معين نمي‌باشند و عمل گروه‌بندي داده‌ها بدون نظارت انجام مي‌گيرد. [HK 2000 ch8]



۴- آماده‌سازي داده‌ها


۱-۴- جمع‌آوري داده‌ها
اولين فعاليت براي شروع يک عمليات کاوش جمع‌آوري داده‌ها مي‌باشد. اين داده‌ها مي‌توانند از يک يا چندين پايگاه داده‌ي مختلف تامين گردند. ما در اينجا فرض مي کنيم که اين داده‌ها تنها از جداول مختلف يک پايگاه داده استخراج مي‌گردند. عمليات جمع آوري داده‌ها در FlexQG به‌صورت زير انجام مي‌پذيرد:
CollectingData := OpenDBStatement LimitedSQLQuery ";"

OpenDBStatement := “USE” “DATABASE” Ident
LimitedSQLQuery := …


عبارت LimitedSQLQuery، يک عبارت SQL مدود شده مي‌باشد که به صورت کامل در پيوست الف آمده است.

۲-۴- پيش‌پردازش داده‌ها
قبل از انجام هر الگوريتم کاوشي، مي‌بايستي يک سري پيش‌پردازش‌ها روي داده‌ها انجام پذيرد، چون به ندرت پيش مي‌آيد که داده‌ها، آماده‌ي اعمال الگوريتم‌هاي کاوش بر روي خود باشند. در مرحله‌ي پيش‏پردازش داده‌ها، بايد عمليات‌هاي زير روي داده‌ها انجام پذيرند:
• طبقه‌بندي کردن ويژگي‌هاي عددي
• تبديل ويژگي‌هاي رشته‌اي با مقادير خاص به ويژگي عددي
• پاك‌سازي داده‌ها

۱-۲-۴- طبقه‌بندي کردن ويژگي‌هاي عددي
جهت طبقه‌بندي ويژگي‌هاي با مقادير عددي، هم مي‌توان مقادير اين ويژگي‌ها را طبقه‌بندي کرد و هم اينکه آن‌ها را در فاصله‌ي [0,1] يا [-1,1] نرمال کرد. چون در رهيافت اولي ويژگي‌هاي کمتري از داده‌ها از بين مي‌روند، اين رهيافت با اقبال بيشتري مواجه شده است و ما نيز اين رهيافت را مورد بررسي قرار مي‌دهيم. براي اين‌کار فاصله‌اي از مقادير، بايستي به تعدادي زيربازه‌ي عددي شكسته شوند. اين کار مي‌‌تواند توسط خود كامپايلريا توسط يك شخص باتجربه انجام پذيرد. اين عمليات در اكثر الگوريتم‌هاي شناخته شده انجام مي‌‌پذيرد (مثلC4,CART,AQ15,CN2,Assistant86 ).
در FlexQG، اين کار بصورت زير انجام‌ مي‌پذيرد:

NumericalCategorizaion := FieldCategorize ";" { FieldCategorize ";"}
FieldCategorize := "CATEGORIZE" FieldName "WITH" Bounds "TO" CategoriesNumber
FieldName := DerivedColumn
Bounds := "LOWER" "=" Integer "," "HIGHER" "=" Integer
CategoriesNumber := "CategoriesNumber" "=" Integer

در اينجا عبارت DerivedColumn، اسم يکي از ستون‌هاي داده‌هاي انتخاب شده‌ي عبارت Select در قسمت جمع‌آوري داده‌ها مي‌باشد.

۲-۲-۴- تبديل ويژگي‌هاي رشته‌اي با مقادير خاص به ويژگي عددي
مقادير يک ستون از داده‌ها مي‌تواند، مقادير رشته‌اي خاصي را بگيرد که قابل تبديل شدن مقادير عددي باشد. مثلا ويژگي جنسيت مي‌تواند مقادير Male يا Female را بگيرد، که چون اين مقادير ماهيتا عددي هستند، مي‌توان آن‌ها را با مقادير مثالا ۱ و ۲ جايگزين کرد.
براي اين منظور در FlexQG داريم:

StrToIntStatement := FieldConvert ";" {FieldConvert ";"}
FieldConvert := "CONVERT" FieldName "VALUES" ValueList
ValueList := "{" Ident {"," Ident} "}"
FieldName := DerivedColumn

در اينجا نيز عبارت DerivedColumn، اسم يکي از ستون‌هاي داده‌هاي انتخاب شده‌ي عبارت Select در قسمت جمع‌آوري داده‌ها مي‌باشد. مقادير معرفي شده در ValueList به ترتيب با مقادير ۱و ۲و ... جايگزين مي‌گردند. اگر در بين داده‌ها، ويژگي‌اي وجود داشت که مقدار آن با هيچ‌يک از مقادير معرفي شده برابر نبود، آن ويژگي مقدار ۰ بخود مي‌گيرد.

۳-۲-۴- پاك‌سازي داده‌ها
مي‌‌توان مجموعه‌ي آموزشي را از داده‌هاي نويزدار و ناسازگار پاكسازي كرد تا يك مجموعه آموزشي خوب بدست آيد. مي‌‌توان پاكسازي ‌داده‌ها را به عنوان يك عمل اختياري در اختيار كاربر قرار داد كه آن را Enable يا Disable كند. داده‌هاي ناسازگار مثلا مي‌‌توانند هر داده‌اي باشد كه به طور مشخص و دقيقي با الگوريتم بيز كلاسه‌بندي نشوند، که ما نيز از همين ويژگي استفاده مي‌کنيم.[Gamz87]
در FlexQG داريم:
DataClean := "CLEAN" Fields
Fields := DerivedColumn {"," DerivedColumn }

۴-۲-۴- گرامر آماده‌سازي داده‌ها در FlexQG
با توجه به مطالب گفته شده‌ي فوق، گرامر مربوط به اين قسمت به صورت زير در مي‌آيد:

PrepocessingData := [NumericalCategorizaion] [StrToIntStatement] [DataClean]

NumericalCategorizaion := FieldCategorize ";" { FieldCategorize ";"}
FieldCategorize := "CATEGORIZE" FieldName "WITH" Bounds "TO" CategoriesNumber
FieldName := DerivedColumn
Bounds := "LOWER" "=" Integer "," "HIGHER" "=" Integer
CategoriesNumber := "CategoriesNumber" "=" Integer

StrToIntStatement := FieldConvert ";" {FieldConvert ";"}
FieldConvert := "CONVERT" FieldName "VALUES" ValueList
ValueList := "{" Ident {"," Ident} "}"

DataClean := "CLEAN" Fields
Fields := DerivedColumn {"," DerivedColumn }


توجه داشته باشيد که کليه‌ي داده‌هاي موجود جهت کاوش بايد عددي باشند، در نتيجه از بين مراحل فوق، مرحله‌ي تبديل داده‌هاي رشته‌اي به عددي، اجباري مي‌باشد.




۵- کلاسه‌بندي و پيشگويي داده‌ها


هدف کلاسه‌بندي داده‌ها، سازماندهي و تخصيص داده‌ها به كلاس‌هاي مجزا مي‌باشد. در اين فرآيند بر اساس داده‌هاي توزيع شده، مدل اوليه‌اي ايجاد مي‌گردد. سپس اين مدل براي طبقه‌بندي داده‌هاي جديد مورد استفاده قرار مي‌گيرد، به اين ترتيب با بكارگيري مدل بدست آمده، تعلق داده‌هاي جديد به كلاس معين قابل پيشگويي مي‌باشد. كلاسه‌بندي در مورد مقادير گسسته و پيشگويي آنها به‌كار مي‌رود. [HK 2000 chV]
هدف پيشگويي، پيش‌بيني و دريافت مقدار يك خصيصه بر اساس خصيصه‌هاي ديگر مي‌باشد. بر اساس داده‌هاي توزيعي، در ابتدا يك مدل ايجاد مي گردد، سپس از اين مدل در پيشگويي مقادير ناشناخته استفاده مي‌شود. در داده‌کاوي، کلاسه‌بندي، به پيشگويي مقادير گسسته، و پيشگويي به تخمين مقادير پيوسته اتلاق مي‌شود
در فرآيند کلاسه‌بندي، اشيا موجود به كلاس‌هاي مجزا با مشخصه‌هاي تفكيك‌شده (ظروف جداگانه) طبقه‌بندي و به صورت يك مدل معرفي مي‌گردند. سپس با در نظر گرفتن ويژگي‌هاي هر طبقه، شي‌ جديد به آنها تخصيص يافته، برچسب و نوع آن پيشگويي مي گردد.
در کلاسه‌بندي، مدل ايجاد شده بر پايه‌ي يك‌سري داده‌هاي آموزشي، (اشيا داده‌هايي كه بر چسب كلاس آنها مشخص و شناخته شده است) حاصل مي آيد. مدل بدست آمده در اشكال گوناگون مانند قوانين کلاسه‌بندي (If-Then)، درخت‌هاي تصميم، فرمول‌هاي رياضي و شبكه‌هاي عصبي قابل نمايش مي‌باشد. يك درخت تصميم، يك ساختار درختي سلسله مراتبي است كه هر گره‌ي آن نشان دهنده‌ي تست مقدار خصيصه بوده، هر انشعاب يك خروجي تست را نمايش مي‌دهد. برگ‌هاي درخت نيز، كلاس‌ها يا توزيع‌هاي كلاس را مشخص مي‌نمايند. اين نوع درخت تصميم قابل تبديل به قوانين کلاسه‌بندي مي‌باشد. از کلاسه‌بندي مي توان براي پيشگويي كلاس اشيا داده‌ها استفاده كرد.
در برخي موارد نيز افراد ترجيح ميدهند مقدار يك خصيصه و نه كلاس آن را پيشگويي نمايند كه به يافتن مقدار يك خصيصه، پيشگويي اتلاق مي‌گردد. در هر حال پيشگويي، تخمين مقدار و برچسب كلاس را با هم در بر مي گيرد. کلاسه‌بندي و پيشگويي با استفاده از تحليل ارتباط ، خصيصه‌هايي را كه در فرآيند مورد نظر، بي‌تاثير و قابل حذف مي‌باشند، شناسايي مي‌كنند.
به عنوان مثال فرض كنيد مدير فروشگاهي در نظر دارد مجموعه‌ي بزرگي از داده‌ها را بر اساس ميزان فروش به زياد، متوسط و كم طبقه‌بندي كند. وي مي‌بايست مدلي ايجاد كند كه بر اساس خصيصه‌هاي كالا مانند قيمت، مارك، محل ساخت و نوع كالا، كلاس مربوط به آن نوع كالا را تعيين نمايد. طبقه‌بندي نهايي مي‌بايست به طور ماكزيمال هر كلاسي را از ديگري تشخيص داده، تصوير سازماندهي شده‌اي از داده‌ها را به نمايش در آورد. اگر خروجي به صورت يك درخت تصميم باشد، خصيصه‌ها به ترتيب اولويت بررسي شده، بقيه خصيصه‌ها در اولويت بعدي بررسي مي‌گردند. چنين مدلي در طرح‌هاي آتي فروشگاه مي تواند بسيار موثر واقع شود. [HK2000ch1]
از كاربردهاي کلاسه‌بندي مي توان بازاريابي، تشخيص بيماري، تحليل اثرات معالجه، تشخيص خرابي در صنعت و تعيين اعتبار را نام برد. [HK 2000 ch7]

۱-۵- انواع روش‌هاي کلاسه‌بندي
کلاسه‌بندي به روش‌هاي زير انجام‌پذير است:
• استنتاج بر اساس درخت تصميم
• طبقه‌بندي بيز
• الگوريتم‌هاي ژنتيك
• شبكه‌هاي عصبي
• مجموعه‌هاي فازي
• طبقه‌بندي بر اساس وابسته‌سازي

۲-۵- مراحل يک الگوريتم کلاسه‌بندي
الگوي عمومي‌ براي الگوريتم‌هاي آموزش از طريق مثال با فرايند كلاسه‌بندي به سه مرحله تقسيم مي‌‌شوند:[Gams87]
• پيش‌پردازش داده‌ها که در بخش ۴ توضيح داده شد.
• ساخت و ارزيابي قوانين كلاسه‌بندي و هرس كردن قوانين اضافي که هدف ما مي‌باشد.
• كلاسه‌بندي نمونه‌هاي جديد.

۳-۵- ارزيابي روش‌هاي کلاسه‌بندي
ارزيابي روش‌هاي کلاسه‌بندي با معيارهاي زير انجام مي‌پذيرد:
• ميزان دقت درپيشگويي، از جمله معيارهاي ارزيابي روش‌هاي مذكور در کلاسه‌بندي مي‌باشد كه ميزان قابليت و توانايي يك مدل را در پيشگويي صحيح برچسب يك كلاس، مشخص مي‌كند.
• سرعت و توسعه‌پذيري از نظر زماني كه براي ايجاد يك مدل و زمان استفاده از آن مدل لازم مي‌باشد، از معيارهاي ديگر ارزيابي روش در کلاسه‌بندي مي‌باشد.
• قوي بودن معيار مهمي است كه ميزان توانايي يك مدل را در برخورد با نويز و مقادير حذف شده تعيين مي كند.
• توسعه‌پذيري معيار ديگري است كه از نقطه نظر ميزان کارايي در بانك‌هاي اطلاعاتي بزرگ و نه داده‌هاي مقيم در حافظه مورد بررسي قرار مي گيرد.
• قابل تفسير بودن يعني ميزان و سطح درك ايجاد شده توسط مدل از ديگر مواردي است كه مي‌بايست در بررسي روش‌هاي کلاسه‌بندي در نظر گرفت.
• شكل قوانين و نحوه نمايش آنها از جمله سايز درخت تصميم و فشردگي و پيوستگي قوانين، معيار ديگري است كه در بررسي روش‌هاي کلاسه‌بندي موثر مي‌باشد. [HK 2000ch7]

۴-۵- روش درخت تصميم در کلاسه‌بندي
يك درخت تصميم يك ساختار سلسله مراتبي مي‌باشدکه در آن، گره‌هاي مياني براي تست يك خصيصه به كار مي روند. شاخه‌ها نشانگر خروجي تست بوده، برگ‌ها برچسب كلاس و يا توزيع بر چسب كلاس را مشخص مي‌نمايند. نكات اساسي براي هر درخت تصميم به شرح زير هستند: [Kennedy97]
• ملاك استفاده شده براي ساخت درخت چه عواملي هستند؟ يعني كدام متغير بايد براي شكستن انتخاب گردد و اين متغير چگونه بايد شكسته شود؟
• ملاک براي متوقف كردن رشد درخت کدام‌ها هستند؟ يعني چه موقعي بايد عمل شاخه شاخه شدن يك نود بايد متوقف شود؟
• چگونه بايد شاخه‌هاي درخت بدست آمده هرس شوند تا بيشترين کارايي را در كلاسه‌‌بندي داشته باشيم؟

۱-۴-۵- انواع درخت‌هاي تصميم
درخت‌هاي تصميم بر دو نوعند:
• درختان تصميم دودويي كه در هر نود، فقط دو شاخه‌ي انشعابي از آن را داريم، مانند CART.
• درختان تصميم خطي ، كه هر نود مي‌‌تواند به چند شاخه منشعب شود، مثل CHAID. که اگر ضريب انشعاب دو باشد به درخت تصميم دودويي تبديل مي‌شود.

۱-۱-۴-۵- : (Classification and Regression Tree) CART [Kennedy97]
بهترين ملاك شكست در يك نود مشخص از اين درخت، از رابطه‌ي زير بدست مي‌آيد:

كه در آن S بهترين قانون شكست مي‌‌باشد و
=
مجموع تعداد الگوهاي موجود در بچه‌ي چپ
مجموع تعداد الگوهاي موجود در داده‌هاي آموزشي

=
مجموع تعداد الگوهاي موجود در بچه‌ي راست
مجموع تعداد الگوهاي موجود در داده‌هاي آموزشي

P (j/LeftChild) = مجموع تعداد الگوهاي كلاس j در بچه‌ي چپ
مجموع تعداد الگوهاي در نود فعلي

‍P (j/RightChild) = مجموع تعداد الگوهاي كلاس j در بچه‌ي راست
مجموع تعداد الگوها درنود فعلي

۱-۱-۱-۴-۵- نحوه‌ي هرس كردن درخت:
تابع g(t) (تابع Strength) رابراي هر نود غير برگ حساب مي‌‌كنيم. سپس مي‌‌توان زير درختي را كه داراي كمترين g(t) مي‌‌باشد از درخت هرس كرد:

كه در آن:
) مجموع الگوهاي موجود در گره‌ي T )( تعداد الگوهاي با کلاس j در گره‌ي T R(t)=( Maxi
مجموع الگوهاي موجود در داده‌هاي آموزشي مجموع الگوهاي موجود در گره‌ي T
تعداد گره‌هاي برگ در زير درخت با ريشه‌ي T = T'


۲-۱-۴-۵- (Chi - Squared Automatic Iteration Decision tree) CHAID:[Kennedy97]
نحوه‌ي شكستن گره‌ها: كدام متغير بايد شكسته شود و مقدار شكست چقدر است؟ در اين الگوريتم جواب اين سوال بر پايه‌ي توزيع χ2 ِ متغيرهاي ورودي و خروجي مي‌‌باشد. صورت كلي اين شكست به صورت زير مي‌‌باشد:

if Variable < SplitValue1 then branch#1
else if Variable < SplitValue2 then branch#2
.
.
.

اگر فقط دو شاخه داشته باشيم، به همان درخت دودويي تبديل مي‌‌شود، در غير اين‌صورت درخت خطي را داريم. توجه داشته باشيم كه مقادير، بايد به صورتي تقسيم شوند كه هر مقدار به طور يكتا در يك شاخه جاي بگيرد و هر مقدار حتما به‌يك شاخه بتواند نسبت داده شود. (البته ممكن است كه چندين مقدار به‌يك شاخه assign شوند) حال بايد به اين سوال جواب داده شود:
حال که نود کانديدا براي شکست انتخاب شد، نحوه‌ي تقسيم‌بندي مقادير به طبقه‌ يا طبقه‌ها (البته توجه داشته باشيم كه تعداد شاخه‌ها مشخص است ) چگونه بايد باشد؟ ما اين‌كار را بر اساس روش تقسيم يك بازه به زير بازه‌هاي مساوي انجام مي‌‌دهيم.

۱-۲-۱-۴-۵- نحوه محاسبه‌ي χ2:

كه در آن:
، تعداد كل صفرها، ، تعداد كل يك‌ها، ، تعداد اعضاي طبقه‌ي i، ، صفرهاي طبقه‌ي i و ، يك‌هاي طبقه‌يi مي‌‌باشد.

۲-۲-۱-۴-۵- شرط پايان
زماني كه همه‌ي متغيرها در يك گره، مقادير زير يك مقدار آستانه‌اي خاصي را بگيرند، الگوريتم را متوقف مي‌‌كنيم. (اين مقدار اگر بخواهد بهينه باشد بايد از طريق آزمايش و خطا آن را پيدا كنيم.)
درخت CHAID نيز مي‌‌تواند هرس شود.

۵-۵- الگوريتم‌هاي کلاسه‌بندي و FlexQG
بر اساس ملاک‌هاي ارزيابي توزيع داده شده و با توجه به ويژگي‌ها و موارد استفاده‌ي الگوريتم‌ها ما براي الگوريتم‌هاي کلاسه‌بندي، از ساختار‌هاي درخت تصميم، استفاده مي‌کنيم که قابل تبديل به قوانين کلاسه‌بندي نيز مي‌باشند.
منتها نحوه‌ي استفاده‌ي ما از اين درخت‌هاي تصميم بايد به صورتي باشد، که بازه‌ي گسترده‌اي از الگوريتم‌هاي کلاسه‌بندي و حتي‌الامکان، اکثر الگوريتم‌هاي عمومي را پوشش دهند. براي اين منظور اولين نکته‌اي که به آن توجه مي‌کنيم، استفاده از درختان تصميم خطي مي‌باشد، که حالت‌هاي خاص آن‌ها، درختان تصميم دودويي، مي‌باشند. مثلا CHAID با فاکتور انشعاب دو به CART، تبديل مي‌شود. پس اولين پارامتري را هم که از کاربر دريافت مي‌کنيم، همين ضريب انشعاب مي‌باشد.
مهمترين پارامتري که روش‌هاي مختلف کلاسه‌بندي را از هم جدا مي‌کند، نحوه‌ي انتخاب و شکست گره‌هاي موجود مي‌باشد.
مدل‌هاي احتمالي که مي توانيم به‌کار ببريم، توزيع‌هاي آماري شناخته‌شده‌اي مي‌باشد که فرض مي‌کنند که مجموعه‌ي داده‌ها، مي‌توانند به عنوان يک ترکيب خطي از توزيع‌هاي چند متغره درآيند. براي اين منظور مي‌توان از توزيع‌هاي پيوسته‌ي هم‌خانواده‌ي توزيع نرمال مثل توزيع F، Student'sT، χ2 و... استفاده کرد. هر کدام از اين توزيع‌ها، در شرايطي بهتر از ديگران عمل مي‌کند، که اين شرايط اغلب به تعداد داده‌هايي که توزيع روي آن‌ها اعمال مي‌شود، بستگي دارد. توزيع‌هاي آماري خاصي نيز به منظور استفاده در الگوريتم‌هاي کلاسه‌بندي معرفي شده‌اند، که عبارتند از: Information Gain، Gini Index و Gain Ratio. اگر درخت تصميم ما براي تصميم‌گيري نحوه‌ي شکست گره‌ها، امکان در اختيار گذاشتن همه‌ي اين توزيع‌ها را فراهم نمايد، در اينصورت مي‌توان از لحاظ کلي و انعطاف‌پذير بودن زبانمان در اين قسمت نيز، مطمئن باشيم.
پارامتر ديگري که براي ساخت درخت نياز داريم و بايد از کاربر دريافت کنيم، مقدار آستانه، براي توقف رشد درخت مي‌باشد، که بدون هيچگونه دغدغه‌اي مي‌توان آن‌را براي همه‌ي الگوريتم‌ها يکسان در نظر گرفت.
آخرين قسمتي را هم که بايد در اين قسمت به آن توجه نمود، اين است که امکان هرس درخت را به صورت يک گزينه‌ي اختياري براي کاربر، در زبانمان تعبيه کنيم. براي هرس درخت نيز، تابع Strength ارايه شده در بخش ۱-۱-۱-۴-۵، مناسب مي‌باشد.


۶-۵- گرامر پيشنهادي
ClassificationRules := "CLASSIFICATION" "RULES" "USING" ClassificationAlgorithm

ClassificationAlgorithm := ( "DTREE" | "DRULE" ) "WITH" ClassificationParameters
ClassificationParameters := "BRANCHINGFACTOR" "=" Integer ","
"STOPTHRESHOLD" "=" Integer
["," "DISTRIBUTION" "=" ClassificationDestributionName]
["WITH" "PRUNNING" ]

ClassificationDestributionName := "INFORMATIONGAIN" | "GINIINDEX" | "GAINRATIO" | "NORMAL" | "STUDENTST" | "F" | "CHISQYARED" | …








۶- كاوش قوانين وابسته سازي


هدف از كاوش قوانين از نوع وابسته‌سازي، يافتن ارتباطات بين اجزا يك مجموعه مي‌باشد. به اين ترتيب، جستجو و يافتن وابستگي‌ها، همبستگي‌‌ها و ساختارهاي علي و معلولي موجود بين يك‌سري اجزا و يا اشياي موجود در بانك‌هاي اطلاعات تراكنشي رابطه‌اي و ساير انبارهاي اطلاعاتي در اين مقوله جاي مي‌گيرد. [HK 2000 ch6]
فرض کنيد مجموعه‌اي از داده‌ها داريم كه در آن، هر ركورد داده شامل اجزا كوچك‌تري مي‌باشد. فرآيند كاوش قوانين وابسته‌سازي، قوانين وابستگي‌اي را توليد مي‌نمايد كه انجام يك جز به انجام جزيي ديگر منوط است. شكل اين قوانين به صورت زير مي‌باشد:
] ضريب اطمينان، ضريب پشتيباني [ تالي → مقدم
ضريب پشتيباني، احتمال اينكه شمول مقدم و تالي در يک تراکنش مي‌باشد. اين ضريب را با علامت S نمايش مي‌دهيم.
ضريب اطمينان، احتمال اينكه اگر تراكنشي، شرايط مقدم را ارضا كند، آنگاه شرايط تالي را نيز ارضا مي‌نمايد، مي‌باشد. اين ضريب را با علامت C نمايش مي دهيم. به عنوان مثال قانون زير را در نظر بگيريد:
]%65 , %6/0 [ ("شير , " X ) خريد → ( "نان" , X ) خريدن
اين قانون نشان مي دهد که اگر شخصي "نان "خريداري كند به احتمال 65 درصد "شير" هم خريداري مي‌نمايد.
قوانين وابسته‌سازي به فرم X→Y و يا مي‌باشند كه Aiو Bj ها زوج‌هاي خصيصه –ارزش مي‌باشند. قانون وابسته سازي X→Y به مفهوم زير است :‌
«يك ركورد بانك اطلاعات كه شرايط X را ارضا كند آنگاه شرايط Y را نيز ارضا مي نمايد.»
در سالهاي اخير در زمينه كاوش كارآيي قوانين وابسته سازي تحقبقات و الگوريتم‌هاي زيادي بررسي شده است. [HK2000ch1]

۱-۶- اصول كاوش قوانين وابسته سازي
در ابتدا اين نكته را يادآور شويم كه در اينجا، توجه ما بر قوانين وابسته‌سازي تك‌بعدي مي‌باشد. فرض مي‌گردد ورودي، يك بانك از تراكنش‌ها بوده، هر تراكنش ليستي از عناصر مي‌باشد. هدف يافتن كليه‌ي قوانين وابسته به يكديگراست. به عنوان مثال در يك مجموعه‌ي بزرگ از داده‌هاي يك فروشگاه، قوانين مشابه با قانون زير جستجو و كاوش مي‌شوند:
«98 درصد افرادي كه لاستيك و فرمان خودرو خريداري مي‌كنند، سرويس و خدمات نيز نياز دارند»
كاوش اجزا وابسته و مرتبط با يكديگر در دوگام به شرح زير انجام مي‌پذيرد:
1. يافتن مجموعه عناصر تكراري :‌در اين گام مي‌بايست مجموعه اجزايي كه حداقل ضريب پشتيباني را دارا هستند با توجه به نكات زيرتعيين شوند:
• اول اينكه زير مجموعه‌اي از مجموعه عناصر تكراري، خود يك مجموعه عناصر تكراري مي‌باشد، يعني اگر {A,B} يك مجموعه عنصر تكراري باشد آنگاه {A} و {B} نيز هر كدام مجموعه عنصر تكراري مجزا هستند.
• دوم اينكه به صورت تكراري مي توان مجموعه عناصر تكراري باكارديناليتي بالاتر، توليد نمود.
2. استفاده از مجموعه عناصر تكراري : در اين گام براي توليد قوانين وابسته‌سازي از مجموعه عناصر تكراري حاصل آمده استفاده مي گردد. [DK 2000]

۲-۶- اصول استقرا در كاوش قوانين وابسته سازي
جمع‌آوري تعدادي از اجزا و ايجاد بخش‌هاي بزرگتر، بعنوان مثال يافتن عناصر دوعضوي و مبنا قرار دادن آنها، سپس تهيه عناصر دو عضوي ديگر و عناصر سه عضوي و بهمين ترتيب تهيه عناصر چند عضوي. نكته قابل ذكر اينكه مي بايست تمامي زير مجموعه‌هاي يك مجموعه عناصر تكراري نيز منظور گردند.
هدف، در يک روش کاوش قوانين وابسته سازي، پيدا كردن تمامي‌ قوانين وابسته‌سازي‌اي است كه داراي شرايط حداقل ضريب پشتيباني و حداقل ضريب اطمينان تعريف شده توسط کاربر باشند.
مثالي از اين مساله را در اينجا مي‌آوريم ، فرض کنيد در جدول «People» که در زير آورده شده است،هدف پيدا کردن کليه‌ي قوانين وابسته‌سازي با حداقل ضريب پشتيباني 40%، و حداقل ضريب اطمينان 50% باشد: [Sikant95]

NumCars Married Age RecordID
0 No 23 100
1 Yes 25 200
1 No 29 300
2 Yes 34 400
2 Yes 38 500
جدول ۱-۶: جدولPeople

در اينجا دو ويژگي كمي‌ وجود دارند، Age و NamCars. فرض كنيد كه در اولين مرحله ما فرض كنيم كه تصميم گرفته‌ايم كه Age را به 4 بازه تقسيم‌بندي كنيم:

Interval
20 .. 24
25 .. 29
30 .. 34
35 .. 39
جدول ۲-۶: افراز Age
نتايج كار در زير نشان داده شده است:
NumCars Married Age RecordID
0 No 20 .. 24 100
1 Yes 25 .. 29 200
1 No 25 .. 29 300
2 Yes 30 .. 34 400
2 Yes 35 .. 39 500
جدول ۳-۶: جدول People بعد از افراز Age

حال نوبت به نگاشت مقادير مي‌‌رسد. نحوه‌ي نگاشت را بصورت زير در نظر مي‌گيريم:
Integer Value
1 Yes
2 No
Integer Interval
1 20 .. 24
2 25 .. 29
3 30 .. 34
4 35 .. 39



جدول ۴-۶: نگاشت Age و Married

نتايج اعمال اين نگاشت بصورت زير مي‌باشد:
NumCars Married Age RecordID
0 2 1 100
1 1 2 200
1 2 2 300
2 1 3 400
2 1 4 500
جدول ۵-۶: جدول People بعد از اعمال نگاشت

براي اين مثال نمونه‌اي از مجموعه عناصر تکراري به شکل زير مي‌باشد:
Support Itemset
3 {< Age: 20 .. 29>}
2 {< Age: 30 .. 39>}
3 {< Married: Yes>}
2 {< Married: No>}
3 {< NumCars: 0 .. 1>}
2 {< Age: 30 .. 39>,< Married: Yes>}
جدول ۶-۶: نمونه‌هايي از مجموعه عناصر تکراري

با فرض اينكه حداقل پشتيباني 40% و حداقل اطمينان 50%، مد نظر ما بوده است، جدول زير نتايج را به ما نشان مي‌‌دهد:
Confidence Support Rule
100% 40% < Age: 30 .. 39 > and < Married: Yes >  < NumCars: 2 >
66.6% 50% < Age: 20 .. 29 >  < NumCars: 0 .. 1 >
جدول ۷-۶: نمونه‌هايي از قوانين توليد شده

۳-۶- كاوش قوانين وابسته سازي و FlexQG
مفاهيم پايه در يافتن قوانين وابستگي يکسان مي‌باشد. هر چند الگوريتم‌هاي زيادي براي اين‌کار پيشنهاد شده‌اند ولي خروجي همه‌ي آن‌ها يکسان مي‌باشد. به‌همين دليل، تنها کافي است که صورت کلي اين الگوريتم را بصورت SQL در آورده و بر روي DBMS اجرا نماييم. در فصل هشتم، اين کار با جزييات کامل، همراه با پياده‌سازي توضيح داده شده است.
تنها پارامترهايي که در کاوش قوانين وابسته‌سازي نياز داريم، ضريب پشتيباني و ضريب اطمينان مي‌باشد.

۴-۶- گرامر پيشنهادي براي کاوش قوانين وابسته‌سازي
گرامر پيشنهادي براي اين قسمت بصورت زير پيشنهاد مي‌شود:
ExtractAssociationRules := "ASSOCIATION" "RULES" "WITH" AssociationParameters
AssociationParameters := "SUPPORT" "=" Integer ","
"CONFIDENCE" "=" Integer



۷- خوشه‌بندي


پديده‌ي خوشه‌بندي كه يكي ديگر از اهداف داده‌کاوي مي‌باشد، به فرآيند تقسيم مجموعه‌اي از داده‌ها (يا اشيا) به زير كلاس‌هايي با مفهوم خوشه‌ اتلاق مي‌شود. به اين ترتيب يك خوشه‌، يك‌ سري داده‌هاي مشابه مي‌باشد كه همانند يك گروه واحد رفتار مي‌كنند. لازم به ذكر است خوشه‌بندي همان کلاسه‌بندي است، با اين تفاوت كه كلاس‌ها از پيش‌تعريف‌شده و معين نمي‌باشند و عمل گروه‌بندي داده‌ها بدون نظارت انجام مي‌گيرد. [HK 2000 ch8]
فرض كنيد كه مجموعه داده‌هاي X موردنظر ما از نقاط داده‌اي (يا مترادف آن اشيا، موارد، الگوها، تراكنش‌ها، گروه‌ها يا ركوردها)، در فضاي ويژگي A تشكيل شده باشند. يعني كه در ان i=1..N و هر جز يك داده عددي يا ويژگي طبقه‌بندي شده‌ي اسمي‌ باشد. اين فرمت داده-‌‌‌ ويژگي مفهوما متناظراست با يك ماتريس N×D. هدف خوشه‌بندي پيدا كردن سگمنت‌هايي در ماتريس فوق مي‌‌باشد، كه اجتماع همه‌ي آن‌ها كل ماتريس باشد و دو بدوي آن‌ها نقطه اشتراكي نداشته باشند.
X=C1υC2υ…υCk ,Cj1∩Cj2 = ø

بر خلاف کلاسه‌بندي و پيشگويي كه اشيا داده‌ها را براساس كلاس‌ها تحليل مي كنند، خوشه‌بندي اشيا داده‌ها را بدون در نظر گرفتن برچسب‌هاي كلاس، تحليل و آناليز مي نمايد. عمدتا برچسب كلاس‌ها در داده‌هاي آموزشي به آساني مشخص نيست زيرا اين كلاس‌ها شناخته شده نمي‌باشند. خوشه‌بندي گاهي براي تعيين و توليد چنين برچسب هايي بكار مي رود. اشياي خوشه‌بندي‌ شده بر اساس اصل ماكزيمم شباهت بين اعضاي هر کلاس و مينيمم شباهت بين کلاس‌هاي مختلف گروه‌بندي مي‌شوند، يعني خوشه‌ها به‌گونه‌اي تنظيم مي‌شوند که اشياي داخل هر خوشه‌ بيشترين شباهت را با يكديگر داشته باشند. هر خوشه‌ به عنوان يك كلاس مي‌باشد كه قوانين از آن مشتق مي شوند. ضمنا خوشه‌بندي مي تواند امكان طبقه‌بندي تشكيلات را فراهم كند، يعني سازماندهي مذكور، به صورت سلسله‌مراتبي از كلاس‌هاست كه هر كلاس شامل حوادث مشابه يكديگر مي‌باشد.

۱-۷- تعريف فرآيند خوشه‌بندي :
خوشه‌بندي فرآيند تقسيم يك‌سري از داده‌ها يا اشيا به زير كلاس‌هايي به نام خوشه‌ مي‌باشد كه توسط اين رويه فهم ساختار داده‌ها و گروه‌بندي آنها ساده مي‌گردد. هر خوشه‌، شامل يك‌سري داده‌هاي مشابه مي‌باشد كه به صورت يك گروه رفتار مي‌كنند. مي‌توان خوشه‌بندي را به صورت کلاسه‌بندي تعريف كرد، با اين تفاوت كه كلاس‌ها و برچسب آنها از پيش تعريف شده نبوده، عمل کلاسه‌بندي بدون نظارت انجام مي‌گيرد.

۲-۷- کيفيت خوشه‌بندي
كيفيت خوشه‌بندي بر اصول زير متكي است:
• داده‌هاي داخل يك كلاس بيشترين تشابه وداده‌هاي كلاس‌هاي متمايز بيشترين تفاوت را دارا باشند.
• استفاده از معيارهاي صحيحِ يافتن تشابهات در متدها و پياده‌سازي آن روش‌ها.
• كيفيت خوشه‌بندي، بر توانايي استخراج برخي الگوهاي مخفي موجود در داده‌ها متكي است.
• چگونگي تعريف و نمايش خوشه‌هاي انتخابي نيز، معيار مهم ديگر در كيفيت خوشه‌بندي مي‌باشد. [HK2000ch8]

در داده‌کاوي و در زمينه‌ي خوشه‌بندي مي‌بايست ملاحظات زير را منظور كرد:
• توسعه‌پذيري
• بتوان خوشه‌ها را با هر شكل دلخواه استخراج نمود.
• در تصميم گيري پارامترهاي داخلي، نياز به دانش زمينه‌ي حداقل باشد.
• عدم آسيب‌پذيري در مواجهه با خطا.
• عدم حساسيت به ترتيب ركوردهاي ورودي و يا عدم تاثير مخرب ركوردهاي آتي بر ركوردهاي فعلي.
• پشتيباني انواع مختلف خصيصه‌ها.
• پشتيباني ابعاد بزرگ داده‌ها.


۳-۷- روش ها و الگوريتم‌هاي خوشه‌بندي :
دو دسته‌ي کلي از الگوريتم‌هاي خوشه‌بندي، سلسله‌مراتبي و تفکيکي مي‌باشند. الگوريتم‌هاي سلسله مراتبي خوشه‌ها را به تدريج مي‌‌سازند (مانند كريستال‌ها رشد مي‌‌كنند) ولي الگوريتم‌هاي تقسيم كننده مستقيما خوشه‌بندي را انجام مي‌‌دهند. آنها سعي مي‌‌كنند كه خوشه‌ها را با جايگذاري مجدد نقطه‌ها بين زيرمجموعه‌ها كشف كنند. در يک تقسيم‌بندي جزيي‌تر اين الگوريتم‌ها به صورت زير دسته‌بندي مي‌گردند:

۱-۳-۷- الگوريتم‌هاي تفكيك
يكي از انواع الگوريتم‌هاي خوشه‌بندي است كه درابتدا مجموعه‌ي داده‌ها را به بخش‌هايي تبديل كرده، سپس با استفاده از برخي معيارها آن دسته‌بندي را مورد ارزيابي قرار مي‌دهد و در صورت لزوم در دسته‌بندي اوليه تغييراتي ايجاد مي‌نمايد. رايج‌ترين الگوريتم‌هاي خوشه‌بندي در اين دسته قرار مي گيرند.
اين الگوريتم‌ها داده‌ها را به چندين زير مجموعه تقسيم مي‌‌كنند. به علت اين‌كه چك كردن همه‌ي زير مجموعه‌هاي ممكن، امكانپذير نيست. تابع‌هاي مكاشفه‌اي حريصانه‌ي خاصي به كار گرفته مي‌‌شوند. در اين الگوريتم‌ها به صورت تكراري نقاط بين k خوشه جابجا مي‌‌شوند تا در نهايت به بهترين خوشه ممكن نسبت داده شوند. بر خلاف متدهاي سلسله مراتبي كه خوشه‌ها بعد از ساخته شدن بازبيني نمي‌‌شود، اين الگوريتم‌ها مرتبا خوشه‌ها را به منظور بهبود بخشيدنشان تغيير مي‌‌دهند، به همين دليل در اين روش‌ها نهايتا خوشه‌هايي با كيفيت بالا خواهيم داشت.
نقش اصلي را در اين متدها روش‌هاي آماري و احتمالي دارند، به همين دليل‌ خوشه‌هاي توليد شده داراي قابليت تفسيرپذير بالايي بوده و بسيار مورد قبول مي‌‌باشند.
بهينه‌سازهاي تكراريِ الگوريتم‌هاي افراز به دو نوع تقسيم مي‌‌شوند: k-means , k-medoids. که در اولي يكي از نقاط خوشه، معرفي كننده‌ي آن خوشه است ولي در دومي‌، مركز ثقل آن خوشه. ما در اينجا تمايل داريم که با حالت كاراتر اين دو، يعني k-means كار ‌‌كنيم. الگوريتم Expectation-Maximization كه در سال 1997 ارايه شده است[Mitchell97]، يك چارچوب كلي براي الگوريتم‌هاي آماري مي‌‌باشد كه‌يكي از حالت‌هاي خاص آن الگوريتم k-means محبوب مي‌‌باشد. اين الگوريتم با توزيع نرمال كار مي‌‌كند.

۲-۳-۷- الگوريتم‌هاي سلسله‌مراتبي ‌
نوع ديگري از الگوريتم‌هاي خوشه‌بندي است كه در ابتدا با در نظر گرفتن برخي معيارها به تجزيه‌ي سلسله مراتبي داده‌ها مي‌پردازد و سپس با روش‌هاي اجماع و تقسيم تغييراتي در دسته‌بندي اوليه ايجاد مي‌نمايد. الگوريتم‌هاي BIRCH و CHRE در اين گروه جاي دارند. الگوريتم‌هاي سلسله مراتبي به دو گونه تقسيم مي‌‌شوند. الگوريتم‌هاي تجميعي (پايين به بالا) و تقسيمي (بالا به پايين). در خوشه‌بندي تجميعي، كار با خوشه‌هايي با يک داده شروع مي‌‌شود ( تعداد خوشه‌ها در ابتدا به اندازه‌ي تعداد داده‌هاي موجود مي‌‌باشد). در هر مرحله دو يا چند خوشه‌ي مناسب با هم تركيب شده و خوشه‌ي جديدي را بوجود مي‌آورند. در خوشه‌بندي تقسيمي عمل خوشه‌بندي با يك خوشه شروع مي‌‌شود. اين خوشه به صورت بازگشتي به دو يا چند خوشه تقسيم مي‌‌‌گردد و به همين ترتيب عمل خوشه‌بندي ادامه پيدا مي‌‌كند.
براي هر دو نوع از الگوريتم‌هاي بالا ما نياز به‌يك شرط پاياني داريم اين شرط اغلب رسيدن به k خوشه مي‌‌باشد.
ادغام يا تقسيم خوشه‌ها به شباهت يا عدم شباهت عناصرخوشه‌ها وابسته است يكي از مهمترين ملاك‌هاي شباهت، فاصله‌ي بين عناصر دو خوشه باشد. يعني، فاصله‌ي دو زير مجموعه از يك خوشه (براي هر تركيب دوتايي از عناصر آن زيرمجموعه از خوشه‌ها ) محاسبه مي‌‌گردد.
براي بدست آوردن فاصله‌ي دو خوشه، ابتدا x درصد از اعضاي خوشه اول و y درصد از اعضاي خوشه دوم انتخاب مي‌‌گردند (معمولا x وy را با هم برابر مي‌‌گيريم) سپس اين دو زير مجموعه را با هم Cross-join كرده و فاصله‌ي تك تك عناصر را محاسبه مي‌‌كنيم. فاصله‌ي دو زير مجموعه از رابطه‌ي زير بدست مي‌آيد:

كه در آن Operation مي‌‌توانند يكي از عملگرهاي minimum يا maximum يا averageباشد كه مثلا اگر Operation = minimum باشد، الگوريتم SLINK را خواهم داشت، اگر Operation = maximum باشد، الگوريتم CLINK را خواهيم داشت و اگر Operatio = average باشد، الگوريتم Voorhees را خواهيم داشت.
روش‌هايي كه مبتني بر فاصله‌ي اقليدسي مي‌‌باشند (مثل روش‌هاي بالا) خوشه‌هايي با شكل منظم مي‌‌سازند، ولي در عمل بسياري از خوشه‌ها از منحني‌هايي در اشكالشان استفاده مي‌‌شود. براي اين منظور چند الگوريتم بوجود آمده است ولي از آنجايي كه هر كدام از اين الگوريتم‌ها ورودي خاص خود را دارند و بر روش خاصي تكيه مي‌‌كنند، قابل کلي كردن نيستند. از اين قسمت نيز به دليل كلي نبودن الگوريتم‌هاي آن صرف‌نظر مي‌‌شود. (لااقل در نسخه‌هاي اوليه).

۳-۳-۷- روش‌هاي متكي برچگالي
يكي از روش‌هاي خوشه‌بندي است كه مجموعه‌ي داده‌ها را بر اساس معيارهايي همچون توابع همسايگي و چگالي دسته‌بندي كرده، مورد ارزيابي قرار مي‌دهد OPTICS , CLIQUE , DBScon از جمله مثال‌هاي اين نوع خوشه‌بندي مي‌باشند. اين الگوريتم‌ها از لحاظ تشكيل شكل‌هاي نامنظم الگويي، انعطاف پذيرتر هستند ولي اغلب فقط بر روي داده‌هاي عددي و با ابعاد پايين كار مي‌‌كنند.

۴-۳-۷- روش‌هاي متكي بر گريد
در اين متدها، داده‌ها ابتدا خلاصه شده و سگمنت مي‌‌شوند، سپس عمل افراز روي فضاهاي بدست آمده انجام مي‌‌پذيرد و نهايتا فضاهاي خوشه‌بندي شده منجر به داده‌هاي خوشه‌بندي شده مي‌‌شود. هدف از اين عمليات بالا بردن کارايي مي‌‌باشد چون ديگر لازم نيست كه با كل فضاهاي داده‌اي كار كنيم و فقط بايد به سگمنت‌ها كار كنيم. بعد از بدست آمدن سگمنت‌ها، كل كار به همان صورت قبلي دنبال مي‌‌شود. يعني مي‌‌توان اين متدها را معادل ساير متدها منتها با يك مرحله‌ي پيش‌پردازش در نظر گرفت.

۵-۳-۷- روش‌‌هاي متكي بر مدل
يك نوع از روش‌هاي خوشه‌بندي است كه براي هر خوشه‌، مدلي فرضي را در نظر مي‌گيرد و هدف آن يافتن مناسب‌ترين مدل براي هر خوشه‌ مي‌باشد. Cod Web , Denclue و AutoClass مثا‌ل‌هايي از اين نوع روش خوشه‌بندي مي‌باشند.[Berkhin2002]

۶-۳-۷- تكنيك‌هاي خوشه‌بندي ديگر
الگوريتم‌هاي بسيار ديگري وجود دارند، تعدادي از ان‌ها به منظور برطرف كردن نيازهاي كاربردي خاصي بوجود امده‌اند. خوشه‌بندي‌هاي بر اساس محدوديت از اين گونه‌اند. تعدادي فقط از لحاظ تيوري مطرح شده‌اند و كاربردهاي ان بيشتر در زمي‌نه‌هاي ديگر بوده و به اين قسمت نيز كشانده شده‌اند.

۴-۷- دسته‌بندي ويژگي‌هاي الگوريتم‌هاي خوشه‌بندي
در حالت كلي ويژگي‌هايي كه اين الگوريتم‌ها را از همديگر متمايز مي‌‌سازند عبارتند از: [berkhin2002]
• نوع ويژگي‌هايي كه الگوريتم‌ مي‌‌تواند با آن‌ها كار كند. ما علاقمند به الگوريتم‌هايي هستيم كه با داده‌هاي عددي و داده‌هاي طبقه‌بندي شده (در حالت كلي در همان دسته‌ي داده‌هاي عددي مي‌‌گنجند)، بتوانند كار كنند.
• حجم داده‌هايي كه مي‌‌توانند با آن كار كنند. ما علاقمند به الگوريتم‌هايي هستيم كه بتوانند با حجم بسيار بالاي داده‌هاي انفجاري عصر حاضر بتوانند كار كنند.
• ابعاد داده‌‌اي كه مي‌‌توانند با آن كار كنند. الگوريتم‌هايي مطلوب ما هستند كه داده‌هاي با ابعاد بالا را نيز پشتيباني مي‌‌كنند.
• پيچيدگي زماني. تعدادي از الگوريتم‌ها با توجه به حجم بالاي اطلاعات امروزه كارايي خود را از دست داده و در مدت زمان معقول و قابل قبول قادر به جوابگويي نيستند و بايگاني شده‌اند.
• پيچيدگي‌الگوريتم : ما مايل به استفاده از الگوريتم‌هايي هستيم كه با اعمال رابطه‌اي بانك‌هاي داده‌اي با موتور RDBMS قابل پياده‌سازي باشند.

۵-۷- الگوريتم‌هاي خوشه‌بندي و FlexQG
با توجه به ويژگي‌هايي که در بالا ذکر شد، ما باد از بين همه‌ي روش‌ها روش‌هايي را انتخاب کنيم، که دامنه‌ي کاربرد آن‌ها گسترده بوده، بتوانند با داده‌هاي با ابعاد بالا و حجم زياد در زماني قابل‌قبول، کار کنند. بنابراين در بين روش‌هاي ارايه شده در بالا، ما روش‌هاي تفکيکي و سلسله‌مراتبي را براي پشتيباني در نضر مي‌گيريم:

۱-۵-۷- بررسي پارامترهاي لازم براي الگوريتم‌هاي خوشه‌بندي تفکيکي
براي الگوريتم‌هاي تفکيکي ما از چارچوب کلي ارايه شده‌ي EM، استفاده مي کنيم. اين الگوريتم در فصل نهم بطور کامل توضيح داده شده و پياده‌سازي آن با عبارات SQL نيز آمده است. پارامترهاي لازم براي اين الگوريتم عبارتند از:
• K: تعداد خوشه‌ها
• Y : مجموعه‌اي از داده‌هاي P بعدي كه الگوريتم را روي آنها اجرا مي‌كنيم : {y1,y2,…,yn} Y=
• P: تعداد ابعاد هر داده
• E : يك تلورانس براي LogLikelihood.
• MaxIteration : ماكزيمم مقدار تكرار حلقه‌ي خارجي.

پارامتر K ، براي مشخص کردن تعداد خوشه‌‌هاي توليدي لازم است (NumberOfClusters)، Y، داده‌هاي مورد نظر و P تعداد ابعاد داده مي‌باشد، که هر دو از عبارت Select (در قسمت جمع‌آوري داده‌ها) بدست مي‌آيند.
اگرچه ما تعداد خوشه‌‌ها را داريم، ولي اين نمي‌تواند به عنوان تنها شرط پايان بکار برود، چون حتي بعد از رسيدن به اين تعداد خوشه‌، اين الگوريتم‌ها مرتبا خوشه‌ها را به منظور بهبود بخشيدنشان تغيير مي‌‌دهند. پس ما نياز به شرط توقف نيز داريم. براي اينکار ما نياز به دريافت يک تلورانس از کاربر هستيم که که مشخص کننده‌ي اين است که فاصله‌ي خوشه‌ها از همديگر حداکثر چقدر مي‌تواند باشد(TopLimitedDistanceValue)؟ اگر در هر مرحله اين فاصله‌ي بين خوشه‌ها بيشتر از اين مقدار بود، الگورتم بايد ادامه پيدا کند. ولي چون ممکن است که اين حداکثر فاصله براي بعضي از داده‌ها قابل دستيابي نباشد، نياز به گرفتن پارامتر ديگري نيز داريم که تضمين کند که الگوريتم حتما متوقف مي‌شود. اين پارامتر حداکثر تعداد لوپ‌هايي است که الگوريتم بايد بعد از رسيدن به K خوشه، انجام دهد(MaxIterations). رسيدن الگوريتم به هر کدام از دو شرط فوق به منزله‌ي توقف الگوريتم مي‌باشد. اگر کاربر اين دو پارامتر را مشخص نکند، بطور پيش‌فرض، بلافاصله بعد از رسيدن به K خوشه، الگوريتم متوقف مي‌شود (يعني ماکزيمم لوپ‌ها،صفر در نظر گرفته مي‌شود.).

همچنين پارامترهاي زير نياز به مقداردهي اوليه دارند، که نظر به اينکه ماتريسي مي‌باشند، در نظر مي‌گيريم که کاربر کليه‌ي عناصر ماتريس را به ترتيب و بصورت سطري وارد مي‌کند:
• C[p×k] : ماتريس ميانه‌هاي(Means) خوشه‌ها (k خوشه‌ p بعدي )
• [p×p]R : كوواريانس(Covariance) هر كدام از ابعاد ( كواريانس‌ها بين خوشه‌ها مشترك است. ) اين ماتريس قطري است.
• [k×1]W : وزن‌هاي(Weight) خوشه‌ها.

اگر کاربر مقادير اوليه را براي هر کدام از اين پارامترها وارد نکند،بصورت پيش‌فرض جهت مقدار دهي اوليه بصورت زير عمل كنيم :
• C ← μ-Random()
• R ← I
• W ← 1/k

همچنين کاربر مي‌تواند تعيين کند که مقاديري را که براي هر کدام از اين پارامترها وارد کرده، در طول الگوريتم مي تواند تغيير کند يا نه؟ اين کار انعطاف‌پذيري و قابليت خوبي به برنامه مي‌دهد. مثلا الگوريتم محبوب و مشهور k-Means يك حالت خاص از EM است وقتي كه R,W ثابت بوده و برابر باشند با W=1/k و R=I.

خروجي‌هايي که اين الگوريتم به ما مي دهد عبارتند از:
• C[p×k] : ماتريس ميانه‌هاي خوشه‌ها (k خوشه‌ p بعدي )
• [p×p]R : كوواريانس هر كدام از ابعاد ( كواريانس‌ها بين خوشه‌ها مشترك است. ) اين ماتريس قطري است.
• [k×1]W : وزن‌هاي خوشه‌ها.
• [n,k]X : ماتريس احتمال عضويت هر داده در خوشه‌ها.

اين خروجي‌ها، در رهيافت ما بصورت جداولي در پايگاه داده ذخيره مي‌شوند.

مدل احتمال به‌کاررفته در اين الگوريتم، توزيع آماري نرمال مي‌باشد، زيرا فرض مي‌کند که مجموعه‌ي داده‌ها، مي‌توانند به عنوان يک ترکيب خطي از توزيع نرمال چند متغره درآيند. سوالي که در اينجا مطرح است اين است که آيا مي‌توان از ساير توزيع‌هاي آماري نيز براي بهبود نتايج و کلي کردن الگوريتم‌ها استفاده کرد يا نه؟ جواب اين سوال مثبت مي باشد. براي اين منظور مي‌توان از توزيع‌هاي پيوسته‌ي هم‌خانواده‌ي توزيع نرمال مثلا توزيع F، Student'sT، χ2 و... استفاده کرد. هر کدام از اين توزيع‌ها در شرايطي بهتر از ديگران عمل مي‌کند، که اين شرايط اغلب به تعداد داده‌هايي که توزيع روي آن‌ها اعمال مي‌شود، بستگي دارد. پس اين عامل هم مي‌تواند به عنوان عامل خوبي براي کلي کردن الگوريتم، در نظر گرفته شود.


۲-۵-۷- بررسي پارامترهاي لازم براي الگوريتم‌هاي خوشه‌بندي سلسله مراتبي
همانطور که در قسمت ۲-۳-۷ توضيح داده شد، اين الگوريتم‌ها مي‌توانند تجميعي (agglomorative) و تقسيمي (divise) تقسيم مي‌شوند. شرط پاياني هر دو گروه، رسيدن به K خوشه‌، مي‌باشد. معيار لازم براي شکست يا ادغام خوشه‌ها در هر دو فاصله‌ي بين خوشه‌ها مي‌باشد. در هر دو براي بدست آوردن فاصله از X درصد داده‌هاي خوشه‌ها استفاده مي‌شود. که عملگر تعيين فاصله در آن داده‌ها، minimum، maximum يا average مي‌باشد.

۳-۵-۷- گرامر پيشنهادي
Clustering := "CLUSTERING" "USING" ( HierarchicalClustering | PartitioningClustering ) "BY" FieldName

HierarchicalClustering := ( "AGGLOMORATIVE" | "DIVISE" ) "HIERARCHICAL" "WITH" HierarchicalParameters
PartitioningClustering := "PARTITIONING" "WITH" PartitioningParameters

HirarchicalParameters := "NOOFCLUSTERS" "=" Integer ","
"DataPerClusterPersentage" "=" Integer ","
"Operator" "=" OpName
OpName := "MINIMUM" | "AVERAGE" | "MAXIMUM"

PartitioningParameters := "NOOFCLUSTERS" "=" Integer ","
"TOPLIMITEDDISTANCEVALUE" "=" Integer ","
"MAXITERATION" "=" Integer
["," "MEANS" ["CONSTANT"] ["VALUES" "=" MatrixValues ] ]
["," "COVARIANCES" ["CONSTANT"] ["VALUES" "=" MatrixValues ] ]
["," "WEIGHTS" ["CONSTANT"] ["VALUES" "=" MatrixValues ] ]
["," "DISTRIBUTION" "=" ClusteringDestributionName]
MatrixValues := Number { "," Number }
ClusteringDestributionName := "NORMAL" | "STUDENTST" | "F" | "CHISQYARED" | …





۸- الگوريتم کلي کاوش قوانين وابسته‌سازي، با استفاده از رهيافت SQL



۱-۸- قوانين وابسته‌سازي
مجموعه‌اي از تراكنش‌ها داده شده است كه هر تراكنش مجموعه‌اي از عناصر مي‌‌باشد يك قانون وابسته‌سازي يك عبارت مي‌‌باشد كه x و y مجموعه‌اي از عناصر مي‌ باشند و معني آن اين است كه تراكنش‌هايي كه شامل عناصر موجود در x هستند همچنين شامل عناصر موجود در y نيز مي‌‌باشند يك نمونه از چنين قانوني اين است كه «30% از تراكنش‌هايي كه شامل خريد ماست هستند. شامل خريد نان نيز مي‌‌باشند و 2 % از كل تراكنش‌ها شامل هر دو قلم مي‌‌باشند.» در اين‌جا به 30% ضريب اطمينان و به 2% ضريب پشتيباني گفته مي‌‌شود.
صورت مساله در كاوش قوانين وابسته‌سازي پيدا كردن تمامي‌ قوانيني مي‌‌باشد كه حداقل اطمينان و حداقل پشتيباني‌اي كه توسط كاربر تعريف مي‌‌شوند را برآورده سازند.

۲-۸- کاوش اجزاي وابسته
مساله‌ي كاوش قوانين وابسته‌سازي مي‌‌تواند به دو زير مساله تقسيم شود:[ Srawagi]
1ـ پيدا كردن همه‌ي تركيب‌هاي عناصر كه پشتيباني آن‌ها از حداقل پشتيباني بيشتر باشد كه به آن مجموعه عناصر تکراري گفته مي‌‌شود. اين بخش زمانبرترين بخش الگوريتم مي‌باشد.
2ـ استفاده از مجموعه عناصر تکراري براي توليد قوانين موردنظر. ايده‌ي اصلي در اين‌جا اين است كه اگر AB و ABCD عضو اين مجموعه باشند، در اين‌صورت قانون در صورتي برقرار است كه نسبت پشتيباني
ABCD به پشتيباني AB بزرگتر يا مساوي مقدار اطمينان باشد. توجه داشته باشيد كه اين قانون حداقل پشتيباني را دارد، زيرا ABCD عنصر مجموعه‌ي تکراري بوده است.

۳-۸- الگوريتم Apriori
مفاهيم پايه در يافتن قوانين وابستگي يکسان مي‌باشد. الگوريتم‌هاي متفاوتي براي اين‌کار پيشنهاد شده‌اند که خروجي همه‌ي آن‌ها يکسان مي‌باشد. به‌همين دليل اصرار به استفاده از الگوريتم خاصي نداريم. براي اين منظور از معروف‌ترين و پرکاربردترين آن‌ها يعني الگوريتم Apriori استفاده مي‌کنيم. حال سوالي که مطرح است اين است که ما به چه نحو به بهترين شكل مي‌‌توانيم ساختار الگوريتم Apriori را با يك پايگاه داده مجتمع كنيم؟ الگوريتم Apriori براي پيدا كردن مجموعه عناصر تکراري، چندين گذر بر روي داده‌ها انجام مي‌‌دهد. در K اُمين گذر، اين الگوريتم همه‌ي مجموعه عناصر داراي k عنصر را پيدا مي‌كند كه به آن k-itemset مي‌‌گويند. هر گذر از دو فاز تشكيل مي‌‌شود. با فرض اين‌كه نشان‌دهنده‌ي عناصر موجود در k-itemset و مجموعه‌ي كانديداهاي k-itemset باشد، داريم:
• فاز اول: فاز توليد كانديداها كه مجموعه‌ي همه‌ي عناصر (k-1)-itemset يعني مي‌‌باشد كه در (k-1) اُمين فاز پيدا شده‌اند. اين عناصر براي توليد مجموعه كانديداهاي به كار مي‌‌روند. روال توليد كانديدا ما را مطمين مي‌‌سازد كه يك Superset براي عناصر k-itemset مي‌‌باشد، يك ساختار داده‌ي خاص از درخت Hash كه در حافظه نگهداري مي‌‌شود براي ذخيره مورد استفاده قرار مي‌‌گيرد.
• فاز دوم: پيمايش كردن داده‌ها در فاز شمارش پشتيباني . براي هر تراكنش، كانديداهاي موجود در كه در آن تراكنش نيز وجود دارند، براي الحاق به درخت hash معين مي‌‌شوند و سپس شماره‌ي پشتيباني آن‌ها افزايش پيدا مي‌ كند. در آخرين فاز براي اين‌كه داده‌هاي موجود در ، كه مي‌‌توانند در نيز باشند شناسايي شوند،اين مجموعه مورد جستجو قرار مي‌ گيرد.
شرط پاياني الگوريتم اين است كه يا خالي شوند.
فرمت ورودي: جدول تراكنش‌هاي T داراي دو ويژگي مي‌ باشد: شناسه‌ي تراكنش (tid) و شناسه‌ي عنصر (item). تعداد عناصر هر tid متغير بوده و در زمان ساخت جدول مشخص نيست.

۴-۸- وابسته سازي در SQL
هر گذر k ازالگوريتم Apriori ابتدا يك مجموعه itemset كانديدا از مرحله‌ي قبل توليد مي‌‌كند.
در مرحله‌ي Join يك Supreset از بوسيله join كردن با خودش توليد مي‌‌گردد:


Insert into Ck select I1.item1, …, I1.itemk-1, I2.itemk-1
From Fk-1 I1, Fk-1 I2
Where I1.item1 = I2.item1 and
.
.
.
I1.itemk-2 = I2.itemk-2 and
I1.itemk-1 < I2.itemk-1


بعنوان مثال فرض كنيد باشد. بعد از مرحله‌ي join مجموعه‌ي برابر خواهد بود با: .
مرحله‌ي ‌بعدي مرحله‌ي هرس مي‌‌باشد. هر مجموعه عنصر كه بعضي از زير مجموعه‌هاي k-1 عنصري آن‌ها در نباشد حذف خواهد شد. مثلا در مثال فوق {1,3,4,5} بدليل اين‌كه زير مجموعه‌ي{1,4,5} آن در نيست حذف خواهد شد. بنابراين تنها مجموعه عنصر عضو مجموعه {1,2,3,4} خواهد بود.
ما مي‌‌توانيم مرحله‌ي هرس را نيز در همان پرس‌و‌جوي فوق بگنجانيم و آن را به صورت يك k-way Join به صورت زير نشان دهيم. بعد از join كردن I1 و I2، ما k مجموعه عنصر كه از (I1.item1, …, I1.itemk-1, I2.itemk-1) تشكيل شده‌اند را داريم. براي اين مجموعه عناصر، دو تا از زيرمجموعه‌هاي با طول k-1، از آنجايي كه از دو مجموعه عنصر موجود در ساخته شده‌اند، Frequent مي‌‌باشد. در نتيجه ما با join‌هاي اضافي k-2 زير مجموعه‌ي باقيمانده را چك مي‌‌كنيم. اساس كار بر اين است كه در هر لحظه از يكي از عناصر، از مجموعه‌ي k-itemset صرف‌نظر مي‌‌كنيم. ابتدا از item1 صرف‌نظر كرده و چك مي‌‌كنيم كه آيا زير مجموعه‌ي (I1.item2, …, I1.itemk-1, I2.itemk-1) به تعلق دارد يا نه (در پرس‌و‌جوي زير ما اين‌كار را با join كردن با انجام مي‌‌دهيم: در حالت كلي هنگام join كردن با ما از عنصر r-2 صرف‌نظر مي‌‌كنيم. ساخت يك ايندکس اوليه بر روي (item1, …, itemk-1) از به كاراتر كردن اين عمليات، خيلي کمک مي‌کند.
بعضي از مراحل مختلف فوق توسط همروندهاي DBMS‌ها به صورت همزمان اجرا مي‌‌گردند.






شکل ۱-۸: ساختن کانديداها براي هر K

۵-۸- شمارش پشتيباني براي پيدا كردن مجموعه عناصر تکراري
اين بخش زمانبرترين قسمت از الگوريتم قوانين وابسته‌سازي مي‌‌باشد. ما براي شمارش پشتيباني عناصر از مجموعه عناصر و داده‌هاي جدول T استفاده مي‌‌كنيم ما در اينجا براي پياده سازي SQL، دو رهيافت بر پايه‌ي SQL-92 ارايه مي‌‌دهيم:

۱-۵-۸- k-way Jains:
Insert into Fk select item1,. .., itemk, count (*)
From Ck, T t1,. .., T tk
Where t1.item = Ck.item and
.
.
.
tk.item = Ck.item and
t1.tid = t2.tid and
.
.
.
tk-1.tid = tk.tid
Group by item1, item2,. .., itemk
Having count(*) > :minsup







شکل ۲-۸: شمارش پشتيباني با روش K-way join

۱-۵-۸- Subquery-based:
Insert into fk Select item1,. .., itemk, count(*)
From (Subquery Qk) t
Group by item1, item2,. .., itemk
Having count (*) > :minsup


Subquery Q1 (for any l between 1 and k):
Select item1,. .., iteml, tid
From T tl, (Subquery Ql-1) as rl-1
(Select distinct item1, …, iteml from Ck ) as dl
Where rl-1.item1 = dl.item1 and
.
.
.
rl-1.iteml-1 = dl.iteml-1 and
rl-1.tid = tl.tid and
tl.item = dl.iteml


Subquery Q0: No Subquery Q0






شکل ۳-۸: شمارش پشتيباني با روش Subquery-based
در [Srawagi98] براي اين روشِ پياده‌سازي علاوه بر دو رهيافت فوق، دو رهيافت ديگر و ۶ رهيافت هم براي پياده‌سازي بر اساس SQL-OR پيشنهاد و توضيح داده شده است. جهت اطلاعات بيشتر مي‌‌توانيد به مقاله‌ي فوق مراجعه نماييد.


۹- پياده‌سازي چارچوب کلي الگوريتم‌هاي خوشه‌بندي تفکيکي، بر پايه‌ي SQL


در اينجا الگوريتم EM ( Expectation–Maximization ) را تشريح كرده و به ترجمه‌ي آن به SQL استاندارد مي‌پردازيم[Ordonez2000]:

۱-۹- ورودي‌هاي الگوريتم
ورودي‌هاي اين الگوريتم بشرح زير مي‌باشند :
• K: تعداد خوشه‌ها
• Y : مجموعه‌اي از داده‌هاي P بعدي كه الگوريتم را روي آنها اجرا مي‌كنيم : {y1,y2,…,yn} Y=
• P: تعداد ابعاد هر داده
• E : يك تلورانس براي LogLikelihood.
• MaxIteration : ماكزيمم مقدار تكرار حلقه‌ي خارجي.

۲-۹- خروجي‌هاي الگوريتم
انتظار داريم كه اين الگوريتم خروجي‌هاي زير را به ما بدهد:
• C[p×k] : ماتريس ميانه‌هاي خوشه‌ها (k خوشه‌ p بعدي )
• [p×p]R : كوواريانس هر كدام از ابعاد ( كواريانس‌ها بين خوشه‌ها مشترك است. ) اين ماتريس قطري است.
• [k×1]W : وزن‌هاي خوشه‌ها.
• [n,k]X : ماتريس احتمال عضويت هر داده در خوشه‌ها.

۳-۹- مدل احتمال به کار رفته
تابع چگالي احتمال كه در اين الگوريتم بكار مي‌رود به صورت زير است:

: تابع چگالي احتمال توزيع نرمال در يک بعد

كه در آن :



كه اين تابع براي داده‌هاي P بعدي (x تعداد بعدهايش، p تاست)، بصورت زير در‌مي‌آيد:


كه در آن :
يک بردار P بعدي است:
ماتريس کوواريانس‌ها که P×P بعدي است

ما در الگوريتم‌هاي EM با پارامترهاي p بعدي سر و كار داريم، پس از تابع چگالي فوق استفاده مي‌كنيم. بصورت ساده‌تر، اين تابع را مي‌توان بصورت زير نوشت :

كه را فاصله‌ي ماهانوبيس گوييم و داريم :

و چون در اينجا داده‌هاي ما تركيبي از k خوشه‌ از داده‌هاي p بعدي هستند، در نتيجه تابع احتمال مدل تركيبي نرمال، بصورت زير خواهد بود :

P(x|i): توزيع نرمال براي هر کلاستر
wi: وزني از داده‌هاي کلي که اين کلاستر آن را معرفي مي‌کند.

۴-۹- الگوريتم EM
حال كه شناختي از پارامتر‌هاي مختلف EM بدست ‌آورديم، خود الگوريتم را در اينجا ذكر مي‌كنيم :

1. INITIALIZE: Set Initial values for C,R,W (Rendom or approximate solution from sample).
2. WHILE change in LogLikelihood llh is greater than є and MaxIteration has not been reached Do E and M Steps.
E step
C'=0, R'=0, W'=0, llh=0
For i =1 to n
Sumpi = 0
For j=1 to k
δij = (yi - cj)T R-1 (yi - cj)
Pij = [wi/((2π)p/2|R|1/2)] exp [-1/2 δij]
Sumpi = sumpi + pij
End for
Xi = pi/sumpi
llh = llh + ln(sumpi)
C' = C'+ yi xiT
W' = W' + x i
End for

M step
For j=1 to k
Cj = C'j / W'j
For i=1 to n
R' = R' + (yi - cj) xij (yi - cj)T
End for
R = R' / n
W = W' / n

الگوريتم محبوب و مشهور k-Means يك حالت خاص از EM است وقتي كه R,W ثابت بوده و برابر باشند با :
W=1/k
R=I


۵-۹- قدم اول: ساده‌سازي و بهينه کردن الگوريتم
ابتدا تا جايي كه مي‌توانيم الگوريتم را ساده و بهينه مي‌كنيم :
اولين چيزي كه به آن توجه مي‌كنيم، نحوه‌ي محاسبه‌ي فاصله‌ي ماهانوبيس مي‌باشد، داشتيم :

مي‌دانيم كه R يك ماتريس قطري است، پس مي‌توان بصورت ساده‌تر نوشت:


نكته‌ي بعدي اين است كه ازآنجايي كه R در طول مرحله‌ي E تغيير نمي‌كند، مي‌تواند فقط يكبار و در ابتدا محاسبه شود. به مشابه قسمت اول براي مرحله‌ي M، مي‌توان نوشت :
R' = R' + (yi - cj) xij (yi-cj)T ≡ R' = R' + xij (yij - cij)2

ساير نكته‌هايي كه در مورد الگوريتم مي‌بايستي مورد توجه واقع شوند :
1- از متغيرهاي موقتي زير استفاده كرده‌ايم :
• δ[n×k] : فاصله‌هاي ماهانوبيس
• P[n×k] : احتمال‌هاي نرمال
• llh : LogLikelihood
• C', R', W'

2- جهت مقدار دهي اوليه مي‌توان به عنوان مثال بصورت زير عمل كنيم :
• C ← μ-Random()
• R ← I
• W ← 1/k

با توجه به نوشته‌هاي فوق، حال دنبال يك پياده‌سازي SQL براي اين الگوريتم مي‌گرديم.

۶-۹- پياده‌سازي SQL استاندارد الگوريتم EM :
براي اينكه اين الگوريتم صرفا با عبارات SQL قابل پياده‌‌سازي باشد، به جداول اطلاعاتي زير نياز داريم :
Contents Size Columns Primary Key Table
داده‌هاي مورد نظر n y1..yn RowID(Auto) Y
فاصله‌هاي ماهانوبيس n d1..dn RowID(Auto) YD
مقادير توابع احتمال n p1..pn / sump RowID(Auto) YP
جواب‌ها n x1..xn , llh RowID(Auto) YX
ميانه‌ها 1 y1..yp -- C1..CK
کوواريانس‌ها 1 y1..yp -- R
وزن‌ها 1 w1..wk ,llh -- W
ساير پارامترها 1 n, twopipdiv2, sqrtdetR -- GMM

جدول ۱-۹: ليست جداول مورد نياز براي پياده‌سازي نسخه‌ي اوليه الگوريتم EM

با توجه به جداول فوق، مرحله‌ي E از الگوريتم فوق را بعنوان مثال مي‌توان بصورت زير نوشت:
Insert into YD Select
RID, (Y.y1 - C1.y1) ** 2 / R.y1 + … + (Y.yp - C1.yp) ** 2/R.yp,
(Y.y1 - C2.y1) ** 2 / R.y1 + … + (Y.yp - C2.yp) ** 2/R.yp,
.
.
.
(y.y1 - Ck.y1) ** 2 / R.y1 + … + (Y.yp - Ck.yp) ** 2/R.yp
From Y, C1, C2, …, Ck, R

Insert Into YP select
RID , W1 / (twopipdiv2 * sqrtdetR) * exp (-0.5 * d1) As P1
, W2 / (twopipdiv2 * sqrtdetR) * exp (-0.5 * d2) As P2
.
.
.
, Wk / (twopipdiv2 * sqrtdetR) * exp (-0.5 + dk) As Pk
, P1 + P2 + … + Pk As sump
From YD, GMM, W

Insert into Yx Select
RID, p1 / sump, p2 / sump, …, pk / sump, ln(sump) from YP

مشكلي كه در اين رهيافت با آن مواجه مي‌شويم يك مشكل عملي است و نه تئوري و آن طول عبارت‌هاي SQL‌ي است كه توضيح داده شد. مثلا در عبارت Insert فوق فرض كنيد كه در يك مساله بخواهيم يك سري داده را كه هر كدام 100 بعد دارند، به 50 خوشه‌ تقسيم كنيم (k=50, p=100 ). ما مجبوريم كه مربع تفاضل‌ها را روي P عبارت حساب كنيم كه هر كدام در بهترين حالت 10 كاراكتر طول خواهند داشت. اين عبارت‌هاي 10 كاراكتره بايد p بار با هم جمع شوند که k تا از آنها را داريم، يعني در اين حالت طول عبارت SQL به ۵۰۰۰۰ (يعني 10*50*100) كاراكتر مي‌رسد كه هندل كردن آن را هيچ DBMSي نمي‌پذيرد، پس نياز به رهيافت ديگري داريم كه بتواند اين مشكل را حل كند.
براي حل اين مشكل، الگوريتم ديگري را مطرح مي‌كنيم. ساختمان جداول مورد نياز را به شكل زير معرفي مي‌كنيم :
Contents Size Columns Primary Key Table
داده‌ها Pn Values RID, v Y
فاصله‌هاي ماهانوبيس Kn D RID, i YD
چگالي‌هاي احتمال Kn P RID, i YP
جواب‌ها Kn X RID, i YX
ميانه‌ها Pk Values i,v C
کوواريانس‌ها P Values v R
وزن‌ها K W i W
ساير پارامترها 1 n, twopipdiv2, sqrtdetR -- GMM
جدول ۲-۹: ليست جداول مورد نياز براي پياده‌سازي نسخه‌ي بهبود يافته‌ي الگوريتم EM

با توجه به جداول فوق، مرحله‌ي E از الگوريتم فوق را مي‌توان بصورت زير نوشت :
Insert into Yd Select
RID, C.i / sum ((Y.val – C.val) ** 2 / R.val) As d
From Y, C, R
Where Y.V = C.V and C.v = R.v
Group By RID, C.i

Insert into Yp Select
RID, Yd.i, W / (twopipdiv2 * sqrtdetR) * exp (-0.5 * d) As P
From Yd, W, GMM
Where Yd.i = W.i

Insert into Yx Select
RID, C.i, P / Ysump.sump
From Yp, YSump
Where Yp.RID = Ysump.RID

روش فوق از لحاظ انعطاف‌پذيري روش بسيار خوبي مي‌باشد، اما سربار زيادي در جدول‌هاي موقتي ساخته شده براي Joinهاي مورد نياز، دارد. ولي با ترکيب اين روش با روش قبلي مي‌توان به يک روش پيوندي (Hybrid)، دست يافت که مزيت‌هاي هر دو روش را در خود جمع داشته باشد. براي مشاهده اين روش و گرفتن اطلاعات و توضيحات بيشتري در مورد چگونگي پياده‌سازي روش EM بر پايه‌ي SQL مي‌توانيد به مقاله [Ordonez2000]، مراجعه نماييد.


۱۰- نتيجه‌گيري و پيشنهادات

با بررسي کليه‌ي جوانب الگوريتم هاي داده‌کاوي، يک زبان سطح بالاي انعطاف‌پذير و قابل گسترش را طراحي کرديم. جهت نحو‌ه‌ي پياده‌سازي و استفاده ار آن پيشنهاد مي شود که اين زبان در قالب يک وب‌سايت پياده‌سازي و ارايه شود، که براي همگان در دسترس بوده و همچنين امکان معرفي آن به خوبي فراهم‌ شود.
طراحي زبان در قالب يک گرامر ارايه شد، اين بدان معني نيست که وقت و نيروي زيادي براي نوشتن اسکنر و کامپايلري براي آن، صرف شود، بلکه هدف اين بوده که با يک گرامر واضح، تمامي جوانب و پارامتر‌هاي مختلف زبان، بخوبي نمايش داده‌ شود. کافي است محيطي فراهم شود که با يک واسط کاربر گرافيکي اطلاعات لازم، از کاربر دريافت گردد و نتيجه به صورت يک متن UDF به کاربر ارايه شود. پياده‌سازي زبان، جهت ارايه‌ي يک الگوريتم کامل داده‌کاوي با جزييات کامل، در قالب يک UDF کار بسيار دقيق و زمانبري مي‌باشد. به همين دليل پيشنهاد مي‌شود که افراد يا گروههاي بعدي، هر کدام يکي از قسمت‌هاي زبان را ادامه دهند و بعد از پياده‌سازي آن، جهت تست و آزمايش نتيجه بر روي DataSetهاي موجود در اينترنت، اقدام نمايند.
بعلت نبود امکاناتي مشابه اين زبان، پيش‌بيني مي‌شود که استقبال خوبي از آن به عمل آيد. همچنين بعلت اينکه بسياري از روش ها با انواع پارامتر‌هاي ورودي مختلف در اختيار کاربر قرار داده مي شود، هزينه‌ي تحقيقات و تست روش‌هاي جديدي که با تغيير اين پارامترها بدست ‌مي‌آيند، بسيار پايين مي‌‌آيد.


پيوست الف: گرامر کلي زبان FlexQG




COMPILER FlexQG

(*-- Scanner Specification --*)
CHARACTERS
Letter := "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
Digit := "0123456789"
Eol := CHR(13)
Tab := CHR(9)

TOKENS
Ident := Letter { Letter | Digit }
Integer := Digit { Digit }
Real := Digit { Digit } "." { Digit } ["E" [ "+" | "-" ] Digit {Digit} ]
Number := Integer | Real
QIdent := ( "@" | Letter ) { Letter | Digit | " !" | "@" | "#" }

IGNORE CASE
IGNORE Eol + Tab

COMMENTS FROM "(*" TO "*)" NESTED
COMMENTS FROM "//" TO Eol


(*-- Parser Specification --*)
PRODUCTIONS

FlexQG := CollectingData PreprocessingData "FIND" ( ClassificationRules | AssociationRules | Clustering) ";"


CollectingData := OpenDBStatement LimitedSQLQuery
OpenDBStatement := “USE” “DATABASE” Ident



PrepocessingData := [NumericalCategorizaion] [StrToIntStatement] [DataClean]

NumericalCategorizaion := FieldCategorize ";" { FieldCategorize ";"}
FieldCategorize := "CATEGORIZE" FieldName "WITH" Bounds "TO" CategoriesNumber
FieldName := DerivedColumn
Bounds := "LOWER" "=" Integer "," "HIGHER" "=" Integer
CategoriesNumber := "CategoriesNumber" "=" Integer

StrToIntStatement := FieldConvert ";" {FieldConvert ";"}
FieldConvert := "CONVERT" FieldName "VALUES" ValueList
ValueList := "{" Ident {"," Ident} "}"

DataClean := "CLEAN" Fields
Fields := DerivedColumn {"," DerivedColumn }



ClassificationRules := "CLASSIFICATION" "RULES" "USING" ClassificationAlgorithm

ClassificationAlgorithm := ( "DTREE" | "DRULE" ) "WITH" ClassificationParameters
ClassificationParameters := "BRANCHINGFACTOR" "=" Integer ","
"STOPTHRESHOLD" "=" Integer
["," "DISTRIBUTION" "=" ClassificationDestributionName]
["WITH" "PRUNNING" ]

ClassificationDestributionName := "INFORMATIONGAIN" | "GINIINDEX" | "GAINRATIO" | "NORMAL" | "STUDENTST" | "F" | "CHISQYARED" | …



ExtractAssociationRules := "ASSOCIATION" "RULES" "WITH" AssociationParameters
AssociationParameters := "SUPPORT" "=" Integer ","
"CONFIDENCE" "=" Integer

Clustering := "CLUSTERING" "USING" ( HierarchicalClustering | PartitioningClustering ) "BY" FieldName

HierarchicalClustering := ( "AGGLOMORATIVE" | "DIVISE" ) "HIERARCHICAL" "WITH" HierarchicalParameters
PartitioningClustering := "PARTITIONING" "WITH" PartitioningParameters

HirarchicalParameters := "NOOFCLUSTERS" "=" Integer ","
"DataPerClusterPersentage" "=" Integer ","
"Operator" "=" OpName
OpName := "MINIMUM" | "AVERAGE" | "MAXIMUM"

PartitioningParameters := "NOOFCLUSTERS" "=" Integer ","
"TOPLIMITEDDISTANCEVALUE" "=" Integer ","
"MAXITERATION" "=" Integer
["," "MEANS" ["CONSTANT"] ["VALUES" "=" MatrixValues ] ]
["," "COVARIANCES" ["CONSTANT"] ["VALUES" "=" MatrixValues ] ]
["," "WEIGHTS" ["CONSTANT"] ["VALUES" "=" MatrixValues ] ]
["," "DISTRIBUTION" "=" ClusteringDestributionName]
MatrixValues := Number { "," Number }
ClusteringDestributionName := "NORMAL" | "STUDENTST" | "F" | "CHISQYARED" | …


LimitedSQLQuery := "SELECT" [ "ALL" | "DISTINCT" ] SelectList TableExpression
SelectList := "*" | DerivedColumn { "," DerivedColumn }
DerivedColumn := ScalarExp [ "As" QIdent ]

TableExpression := FromClause [ WhereClause ] [ GroupByClause ] [ HavingClause ]
FromClause : := "FROM" TableReference { "," TableReference }

TableReference := TableName [[ "AS" ] QIdent] | SubQuery ["AS"] Qident | JoinedTable
TableName := QIdent ["." QIdent ["." QIdent]] |QIdent "." "." QIdent
JoinedTable := CrossJoin | QualifiedJoin

CrossJoin := TableReference "CROSS" "JOIN" TableReference
QualifiedJoin := TableReference [ "NATURAL" ] [ JoinType ] "JOIN" TableReference [ JoinCondition ]
JoinType := "INNER" | OuterJoinType [ "OUTER" ] | "UNION"

OuterJoinType := "LEFT" | "RIGHT" | "FULL"
JoinCondition := "ON" SearchCondition

WhereClause := "WHERE" SearchCondition
GroupByClause := "GROUP" "BY" ColumnRef { "," ColumnRef }
HavingClause := "HAVING" SearchCondition

SearchCondition := SearchCondition "OR" SearchCondition | SearchCondition "AND" SearchCondition
| "NOT" SearchCondition | "(" SearchCondition ")" | Predicate

ColumnRef := ( QIdent ["." QIdent ["." QIdent]] | QIdent "." "." QIdent ) [ "." "*" ]
| QIdent "." QIdent "." QIdent "." QIdent
| "*"

Predicate := ScalarExp ["NOT"] "BETWEEN" ScalarExp "AND" ScalarExp | ColumnRef "IS" ["NOT"] "NULL"
| "EXISTS" SubQuery | InPredicate | ScalarExp
InPredicate := ScalarExp ["NOT"] "IN" SubQuery | ScalarExp ["NOT"] "IN" "(" ScalarExp {"," ScalarExp} ")"

SubQuery := "(" LimitedSQLQuery ")"

ScalarExp := ScalarExp BinaryOperation ScalarExp | UnaryOperation ScalarExp
| Qident | ColumnRef | "(" ScalarExp { "," ScalarExp } ")"

BinaryOperation := "+" | "-" | "*" | "/" | "%" | "&" | "|" | "^" | " := " | ">" | "<" | "< := " | "> := " | "<>" | "! := " | "!<" | "!>" | "AND" | "OR" |

UnaryOperation := "+" | "-" | "~"


END FlexQG.



• صورت کلي الگوريتم‌هاي کلاسه‌بندي به صورت زير در مي‌‌آيد:

USE DATABASE DatabaseName
Select …

CATEGORIZE FieldName WITH LOWER=LowerValue , HIGHER=HigherValue TO CATEGORIESNUMBER=CatNo;
.
.
.
CATEGORIZE FieldName WITH LOWER=LowerValue , HIGHER=HigherValue TO CATEGORIESNUMBER=CatNo;

CONVERT FieldName VALUES {Str1, Str2, …, Strn}
.
.
.
CONVERT FieldName VALUES {Str1, Str2, …, Strn}

CLEAN FieldName, FieldName, …, FieldName

FIND CLASSIFICATION RULES USING (DTREE/RTREE) WITH
BRANCHINGFACTOR = Integer,
STOPTHRESHOLD = Integer
[,DISTRIBUTION = ClassificationDestributionName]
[WITH PRUNING] ;



• صورت کلي الگوريتم‌هاي کاوش قوانين وابسته‌سازي به صورت زير در مي‌‌آيد:

USE DATABASE DatabaseName
Select …

CATEGORIZE FieldName WITH LOWER=LowerValue , HIGHER=HigherValue TO CATEGORIESNUMBER=CatNo;
.
.
.
CATEGORIZE FieldName WITH LOWER=LowerValue , HIGHER=HigherValue TO CATEGORIESNUMBER=CatNo;

CONVERT FieldName VALUES {Str1, Str2, …, Strn}
.
.
.
CONVERT FieldName VALUES {Str1, Str2, …, Strn}

CLEAN FieldName, FieldName, …, FieldName

FIND ASSOCIATION RULES WITH
SUPPORT = Integer,
CONFIDENCE = Integer ;

• صورت کلي الگوريتم‌هاي خوشه‌بندي تفکيکي به صورت زير در مي‌‌آيد:

USE DATABASE DatabaseName
Select …

CATEGORIZE FieldName WITH LOWER=LowerValue , HIGHER=HigherValue TO CATEGORIESNUMBER=CatNo;
.
.
.
CATEGORIZE FieldName WITH LOWER=LowerValue , HIGHER=HigherValue TO CATEGORIESNUMBER=CatNo;

CONVERT FieldName VALUES {Str1, Str2, …, Strn}
.
.
.
CONVERT FieldName VALUES {Str1, Str2, …, Strn}

CLEAN FieldName, FieldName, …, FieldName

FIND CLUSTERING USING PARTITIONINIG WITH
NOOFCLUSTERS = Integer,
TOPLIMITEDDISTANCEVALUE = Integer
[, MEANS [CONSTANT] [VALUES = Num1, Num2, …, Numn]]
[, COVARIANCES [CONSTANT] [VALUES = Num1, Num2, …, Numn]]
[, WEIGHTS [CONSTANT] [VALUES = Num1, Num2, …, Numn]]
[, DISTRIBUTION = ClusteringDistributionName]
BY FieldName;


• صورت کلي الگوريتم‌هاي خوشه‌بندي سلسله‌مراتبي به صورت زير در مي‌‌آيد:

USE DATABASE DatabaseName
Select …

CATEGORIZE FieldName WITH LOWER=LowerValue , HIGHER=HigherValue TO CATEGORIESNUMBER=CatNo;
.
.
.
CATEGORIZE FieldName WITH LOWER=LowerValue , HIGHER=HigherValue TO CATEGORIESNUMBER=CatNo;

CONVERT FieldName VALUES {Str1, Str2, …, Strn}
.
.
.
CONVERT FieldName VALUES {Str1, Str2, …, Strn}

CLEAN FieldName, FieldName, …, FieldName

FIND CLUSTERING USING (AGGLOMORATIVE/DIVISE) HIERARCHICAL WITH
NOOFCLUSTERS = Integer,
DATAPERCLUSTERPERCENTAGE = Integer,
OPERATOR = OpName
BY FieldName;







مراجع و منابع


[Agrawal96] Agrawal, Shim, Developing tightly-coupled Data Mining Applications on a Relational Database System, 1996.

[Berger 2001] Gideon Berger, Knowledge Discovery in Databases for Introsion Disease Classification and Beyoud, 2001.

[Berkhin2002] P. Berkhin, Survay of clustering Data Mining Techniques, Accrue Software, CA. 2002.

[Breiman96] Leo Breiman. Bias, Variance and Arcing Classifiers, 1996.

[C2001] C.Clifton, Security Issues in Data Mining, CS590 M Fall 2001.

[DK2000] D.Kondo, Data Mining and Data-Intensive Computing , CSE225, 2000.

[Fayyad96] Usama Fayyad, Shapiro, Smyth, Knowledge discovery and Data Mining: Towards a unifying framework, 1996.

[Gama] Gama, Bradzil, Characterization of Classification Algorithms.

[Gams87] Matjaz Gams, Nada Lavarc, Review Of Five Emperical Learning Systems Whitin a Proposal Schemata,1987 , EWSL87.

[Han96] Jiawey Han, Fu, Wang, Koperski, Zaiane, DMALm A Data Mining Query Language For Relational Database, 1996.

[HK 2000ch1] J.Han, M.Kamber, Date Mining: Goncepts and Techinqeus, JimGray, Series Editor Morgan Kaufmann Publishers, Augest 2000.

[Hogl2001] Hogl, Stoyan, Muller, The Knowledge Discovery Assistant: Making Data Mining Available for Business Users, 2001.

[Holsheimer94] Holsheimer, siebes, Data Mining: The Search for Knowledge in Databases, 1994.

[John97] G. H. John, Enhancements to the Data Mining Process, 1997.

[Kennedy97] Ruby L. Kennedy, Yuchung Li, Benjamin Van Roy, Christopher D. Reed, Dr. Richard P. Lippmann, Solving Data Mining Problems Through Pattern Recognition, 1997.

[Mannila97] Heikki Mannila, Methods And Problems in Data Minig, 1997.

[Mitchel97] Mitchell, T. M. 1997. Machine Learning. McGraw-Hill, Inc.

[Morzy97] Tadeusz Morzy, Maciey Zakrzewicz, SQL-Like Language for Database Mining, 1997.

[Ordonez2000] Carlos Ordonez, Paul Cereghini, SQLEM: Fast Clustering in SQL using the EM Algorithm, 2000.

[Rajamani98] Karthik Rajamani, Alan Cox, Efficient Mining For Association Rules With Relational Database Systems, 1998.

[RK 98] R. Rastogi, K. Shim, Public: A Decision Tree Classifier that Integrates Building and Pruning, Bell Laboratories. Murray Hill, NJ 07974, 1998.

[Sarawagi98] Sarawagi, Thomas, Agrawal, Integrating Association Rule Mining with Relational Database Systems: Alternative and Implecations.

[SHK98] A.Srivastave, E.Han, V. Kumar, Parallel Formulation of Decisio-Tree Classification Algorithms, 1998 .

[Srikant95] Ramakrishnan Srikant, Rakesh Agrawal, Mining Quanitative Associattion Rules in Large Relational Tables, 1995.

[Thomas98] Shiby Thomas, Sunita Sarawagi, MiningGeneralaized Association Rules and Sequential Patterns Using SQL Queries, Ammerican Association for Artificial Intelligence, 1998.