داده‌كاوی موازی فازی در محیط محاسباتی گرید

داده‌كاوی موازی فازی در محیط محاسباتی گرید

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

داده کاوی به منظور دسته بندی اطلاعات جهت ارائه بهتر آنها به مدیران، پیش بینی اطلاعات و یا تعیین اعتبار داده ها از روی اطلاعات قبلی استفاده می شود. یکی از شاخه های پرکاربرد داده کاوی، درخت های تصمیم گیری می باشد. درخت های تصمیم گیری قادر خواهند بود کل داده‌ها را به صورت درختواره نمایش دهند. الگوریتم های بسیار زیادی در این زمینه ایجاد شده‌اند که تمامی آنها در راستای ارائه راه حل‌هایی جهت بهینه‌سازی ایجاد درخت در زمینه بالاتر بردن دقت، سرعت و پشتیبانی حجم داده‌های زیاد (جهت پردازش) بوده‌اند. الگوریتم های ابتدایی (از قبیل C4.5 [Qui93]) دارای محدودیتی بودند که تمامی داده ها باید در حافظه اصلی قرار می‌گرفتند و پردازش آنها به صورت سری اجرا می‌شد. با ارائه راه حل های بعدی (از جمله SLIQ [Man96] و SPRINT [Sha96]) اجرا به صورت موازی انجام می شود ولی مشکل محدودیت در حجم داده ها همچنان باقی مانده است. در الگوریتم های بعدی (از جمله ScalParC [Jos98]) کل این محدودیت ها برداشته شده و نسبتا الگوریتم مناسبی جهت پردازش داده های با حجم زیاد ارائه گردیده است.
وقتی تعداد رکوردهایی که در داده کاوی شرکت دارند بسیار زیاد شوند، نمی توان آنها را در یک کامپیوتر اجرا کرد و باید از شبکه های قوی‌تر از جمله کلاستر و گرید استفاده نمود. تفاوت عمده کلاستر و گرید در نوع نودهای آنها و همچنین سرویس‌هایی است كه روی آنها وجود دارد می باشد. در کلاسترهای همگن کلیه نودها از یک قدرت برخوردارند ولی در شبکه گرید، نودها می توانند توانایی های متفاوتی داشته باشند. مشکلی که در الگوریتم های ارائه شده بر روی گرید وجود دارد، این است که به آن مانند کلاستر همگن نگاه شده است و حجم کاری نودهای ضعیف و قوی با یکدیگر یکسان هستند که مشکل بزرگی است.
الگوریتم‌هایی نیز در بستر گرید برای ایجاد درختان تصمیم‌گیری ارائه شده‌اند از قبیل [Cha05, Hof04, Shu04] . كاری كه در این روش‌ها انجام شده فقط تطبیق الگوریتم SPRINT با شبكه گرید بوده‌است برای مثال برای ارتباطات میان نودهای شبكه روش وب سرویس را پیشنهاد داده‌اند و از مشكل اصلی این شبكه یعنی مقیاس بسیار زیاد آن و انواع مختلف نود در آن غافل بوده‌اند.
1-2- داده‌كاوی سری
معمولا داده‌كاوی از لحاظ كاربرد به دو دسته تقسیم می‌شوند:
– توصیف داده‌ها : از روی داده‌ها الگوهایی كه برای كاربران قابل فهم باشد را استخراج می‌كند و نمایش می‌دهد.
– پیش‌بینی اطلاعات : بعد از اینكه عمل داده‌كاوی روی داده‌ها انجام گرفت، اگر داده جدیدی وارد شود و بعضی از فیلدهای آن مشخص نباشد، می‌توان آنها را تخمین زد.
تكنیك‌های معروفی كه در این زمینه وجود دارند عبارتند از:
1. دسته‌بندی (پیش‌بینی)
2. خوشه‌سازی (توصیفی)
3. اكتشاف قانون وابستگی (توصیفی)
4. اكتشاف ترتیبی الگو (توصیفی)
5. رگرسیون (پیش‌بینی)
6. اكتشاف انحراف (پیش‌بینی)
از میان روش‌های فوق روش دسته‌بندی دارای اهمیت خاصی است كه از بین روش‌های دسته‌بندی نیز درختان تصمیم‌گیری دارای جایگاه خاصی است كه از جمله دلایل آن می‌توان به موارد ذیل اشاره نمود:
1- ایجاد آن به هزینه زیادی احتیاج ندارد.
2- ركوردها با اینكه از قبل حتی ساختارشان مشخص نیست بسیار سریع دسته‌بندی می‌شوند. به این منظور كه از قبل احتیاجی نیست بدانیم ركوردها دارای چند فیلد و محتوای آنهای چه چیزهایی است و خود الگوریتم آنها را خودكار شناسایی می‌كند.
3- تفسیر و استفاده از درختانی كه حجم كمی دارند بسیار آسان است.
4- در اكثر كاربردها دقت بسیار زیادی نسبت به سایر روش‌ها دارد.
برای اینكه بتوان درختان تصمیم‌گیری را ایجاد نمود در ابتدا الگوریتم‌های سری بسیاری از جمله الگوریتم‌های CART [Bre84]، ID3 و C4.5 [Qui93] و SLIQ [Man96] را می‌توان نام برد.

1-3- داده‌كاوی موازی
الگوریتم‌هایی كه ارائه شده‌اند اكثرا بر روی افزایش سرعت و بالابردن دقت درختان تصمیم‌گیری بوده‌است. در كارهای ارائه شده انواع روش‌های ایجاد درخت، هرس درخت و نحوه پیدا كردن فیلدهای محوری و كلا مسائل مربوط به ایجاد درختان تصمیم‌گیری مورد بررسی قرار گرفته است.
وقتی موضوع داده‌های با حجم بسیار زیاد مطرح گردید الگوریتم‌های فوق نتوانستند جواب دهند. زیرا برای پردازش آنها در ابتدا باید كلیه ركوردها در حافظه قرار بگیرند و بعد بتوان روی آنها عمل داده‌كاوی را انجام داد و اگر تعداد ركوردها از حافظه موجود در رایانه بیشتر می‌بودند، الگوریتم اجرا نمی‌شد. بنابراین الگوریتم‌های جدیدی ارائه شدند كه سعی كردند این مسئله را با روش موازی سازی حل كنند كه بهترین آنها الگوریتم SPRINT [Man96] می‌باشد. در این الگوریتم همان روش سری SLIQ [Man96] مبنا قرار داده شده و سعی شده با ارائه ساختارهای جدید آن را موزای كند. الگوریتم ارائه شده به دلیل توانایی‌های بسیار زیادی كه دارد كه مهمترین آنها حفظ دقت ایجاد درخت متناسب با روش سری آن، در اكثر كاربردها ومقالات به صورت مبنا قرار گرفته است.
الگوریتم SPRINT در ابتدا كلیه داده‌ها را به طور مساوی بین كلیه نودهای شبكه تقسیم كرده و نودهای شبكه با ارتباطاتی كه با یكدیگر دارند مسئله داده‌كاوی را با دقت بالا حل می‌كند.
در این الگوریتم ابتدا كلیه ركوردها بر اساس فیلدهای مختلف مرتب شده و در هر نود به ترتیب و به تعداد مساوی بین آنها تقسیم می‌شوند و الگوریتم به صورت موازی اجرا می‌شود تا اینكه فیلد محوری و مقدار تفكیك مشخص گردد. در این هنگام هر نود موظف است جداول صفتی كه در اختیار دارد را بشكند و مشخص كند هر كدام از آنها مربوط به كدام برگ جدید درخت هستند. عمل تقسیم در مورد فیلد محوری در نودها مشكلی را به وجود نمی‌آورد و با توجه به شرط تفكیك آنها تقسیم می‌شوند و مسئله اساسی تفكیك ركوردهای موجود در سایر جداول صفت است كه آن را با ارائه یك جدول هش حل كرده است. كه هر نود اطلاعاتی را كه از ركوردها بر اساس تفكیك فیلد محوری بدست آورده است را در این جدول قرار می‌دهد و در نهایت یك جدول كامل از كلیه ركوردها بوجود می‌آید و سپس این جدول هش بین كلیه نودها توزیع شده و از روی آن سایر جداول صفت تفكیك می‌شوند.
مشكل الگوریتم فوق همان قسمت آخر آن یعنی استفاده از جدول هش می‌باشد كه به طور كلی مقیاس‌پذیری را از الگوریتم گرفته است و ممكن است همین جدول هش نتواند در حافظه قرار بگیرد. بنابراین الگوریتم جدیدی به نام ScalParC [Jos98] ارائه گردید كه در آن از روش جدیدی برای تبادل اطلاعات استفاده كرده‌اند. در الگوریتم فوق كلیه ابعاد مقیاس‌پذیری توسط ارائه دهندگان آن مورد توجه قرار گرفته بوده به نحوی كه می‌توان ادعا كرد كه این الگوریتم از كلیه ابعاد مقیاس‌پذیر است.

 فایل فشرده حاوی  یک فایل:

فهرست مطالب:
1-1- مقدمه 7
1-2- داده‌كاوی سری 8
1-3- داده‌كاوی موازی 10
1-4- داده‌كاوی فازی 11
1-5- داده‌كاوی در گرید 12
1-6- مشكل داده‌كاوی در گرید 13
فصل 2- كارهای دیگران 15
2-1- ایجاد درختان در محیط محاسباتی گرید 15
2-2- داده‌كاوی در GridMiner-Core 18
2-3- SLIQ به عنوان پایه‌ترین الگوریتم ایجاد درخت 19
2-3-1- ایجاد درخت 20
2-3-2- تفكیك نودها 21
2-3-3- به روز رسانی جدول كلاس 24
2-3-4- بهبود عملكرد 24
2-3-5- پیدا كردن زیرمجموعه‌ها در متغیرهای گسسته 24
2-3-6- هرس درخت 25
2-4- SPRINT روش موازی ایجاد درختان 28
2-4-1- حالت سری 29
2-4-2- پیدا كردن نقطه تقسیم 31
2-4-3- تقسیم نود 33
2-4-4- حالت موازی 33
2-4-5- توزیع داده‌ها 33
2-4-6- پیدا كردن نقاط تقسیم 34
2-4-7- تقسیم‌بندی 34
2-5- ScalParC 35
2-5-1- طراحی مدل ScalParC 36
2-5-2- توزیع داده‌ها و تعادل بار 36
2-6- ایجاد درخت به دو صورت همزمان و جزء بندی 40
2-6-1- ایجاد درخت به صورت همزمان 40
2-6-2- ایجاد درخت با استفاده از جزءبندی 41
2-6-3- روش تركیبی 43
2-7- ایجاد درخت‌ها بوسیله نخ‌ها 43
2-8- ایجاد درختان تصمیم‌گیری از منابع داده‌ای مختلف توزیع شده 44
2-9- نتیجه گیری 45
فصل 3- پیش‌زمینه 47
3-1- مقدمه 47
3-2- محیط محاسباتی گرید 48
3-2-1- سازمان‌های مجازی 52
3-2-2- ماهیت گرید 54
3-2-3- توصیف معماری گرید 57
3-2-4- لایه Fabric : واسط‌ها برای كنترل محلی 58
3-2-5- لایه Connectivity: ارتباط آسان و امن 61
3-2-6- لایه Resource: اشتراك منابع تكین 62
3-2-7- لایه Collective: ارتباط و هماهنگی بین چندین منبع 64
3-2-8- لایه Application 67
3-2-9- معماری عملیاتی گرید 68
3-2-10- مدل تبادل اطلاعات در بین گریدهای گوناگون 69
3-2-11- اشتراکات با سایر فناوریهای مهم 69
3-2-12- وب جهانگستر 70
3-2-13- ASP و SSP 71
3-2-14- محاسبات نظیر به نظیر (P2P) 72
3-2-15- سایر ابعاد گرید 72
3-3- سیستم‌های چند عامله 73
3-3-1- تعریف عامل 73
3-3-2- ساختار سیستم‌های چند عامله 76
3-4- داده‌كاوی 76
3-4-1- دسته‌بندی 77
3-4-2- خوشه‌سازی 79
3-4-3- اكتشاف قانون وابستگی 79
3-4-4- اكتشاف الگوی ترتیبی 80
3-4-5- رگرسیون 81
3-4-6- اكتشاف انحراف 81
3-4-7- معیارها در داده‌كاوی 81
3-4-8- داده‌ها 82
3-4-9- پردازش داده 83
3-4-10- تجمع 84
3-4-11- نمونه‌گیری 84
3-4-12- كاهش ابعاد 85
3-4-13- انتخاب زیرمجموعه‌ای از ویژگی‌ها 86
3-4-14- ایجاد ویژگی جدید 87
3-4-15- گسسته‌سازی 88
3-4-16- تبدیل صفت 88
3-4-17- شباهت و عدم شباهت 88
3-4-18- فاصله اقلیدسی 89
3-4-19- فاصله Minkowski 90
3-4-20- چگالی 91
3-4-21- دسته‌بندی 91
3-4-22- درخت تصمیم‌گیری 93
3-4-23- ایجاد درخت 95
3-4-24- انتخاب فیلد محوری 96
3-4-25- پیدا كردن بهترین تفكیك 97
3-4-26- Gini Index 97
3-4-27- پیدا كردن مقدار تفكیك برای فیلدهای محوری پیوسته 98
3-4-28- Entropy (INFO) 99
3-4-29- تعیین شرط توقف ایجاد درخت 101
3-4-30- برتری‌های درخت تصمیم‌گیری 101
3-4-31- مسائل جانبی مربوط به دسته‌بندی 102
مراجع 103