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

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

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

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

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

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

فهرست مطالب:
۱-۱- مقدمه ۷
۱-۲- داده‌کاوی سری ۸
۱-۳- داده‌کاوی موازی ۱۰
۱-۴- داده‌کاوی فازی ۱۱
۱-۵- داده‌کاوی در گرید ۱۲
۱-۶- مشکل داده‌کاوی در گرید ۱۳
فصل ۲- کارهای دیگران ۱۵
۲-۱- ایجاد درختان در محیط محاسباتی گرید ۱۵
۲-۲- داده‌کاوی در GridMiner-Core 18
2-3- SLIQ به عنوان پایه‌ترین الگوریتم ایجاد درخت ۱۹
۲-۳-۱- ایجاد درخت ۲۰
۲-۳-۲- تفکیک نودها ۲۱
۲-۳-۳- به روز رسانی جدول کلاس ۲۴
۲-۳-۴- بهبود عملکرد ۲۴
۲-۳-۵- پیدا کردن زیرمجموعه‌ها در متغیرهای گسسته ۲۴
۲-۳-۶- هرس درخت ۲۵
۲-۴- SPRINT روش موازی ایجاد درختان ۲۸
۲-۴-۱- حالت سری ۲۹
۲-۴-۲- پیدا کردن نقطه تقسیم ۳۱
۲-۴-۳- تقسیم نود ۳۳
۲-۴-۴- حالت موازی ۳۳
۲-۴-۵- توزیع داده‌ها ۳۳
۲-۴-۶- پیدا کردن نقاط تقسیم ۳۴
۲-۴-۷- تقسیم‌بندی ۳۴
۲-۵- ScalParC 35
2-5-1- طراحی مدل ScalParC 36
2-5-2- توزیع داده‌ها و تعادل بار ۳۶
۲-۶- ایجاد درخت به دو صورت همزمان و جزء بندی ۴۰
۲-۶-۱- ایجاد درخت به صورت همزمان ۴۰
۲-۶-۲- ایجاد درخت با استفاده از جزءبندی ۴۱
۲-۶-۳- روش ترکیبی ۴۳
۲-۷- ایجاد درخت‌ها بوسیله نخ‌ها ۴۳
۲-۸- ایجاد درختان تصمیم‌گیری از منابع داده‌ای مختلف توزیع شده ۴۴
۲-۹- نتیجه گیری ۴۵
فصل ۳- پیش‌زمینه ۴۷
۳-۱- مقدمه ۴۷
۳-۲- محیط محاسباتی گرید ۴۸
۳-۲-۱- سازمان‌های مجازی ۵۲
۳-۲-۲- ماهیت گرید ۵۴
۳-۲-۳- توصیف معماری گرید ۵۷
۳-۲-۴- لایه Fabric : واسط‌ها برای کنترل محلی ۵۸
۳-۲-۵- لایه Connectivity: ارتباط آسان و امن ۶۱
۳-۲-۶- لایه Resource: اشتراک منابع تکین ۶۲
۳-۲-۷- لایه Collective: ارتباط و هماهنگی بین چندین منبع ۶۴
۳-۲-۸- لایه Application 67
3-2-9- معماری عملیاتی گرید ۶۸
۳-۲-۱۰- مدل تبادل اطلاعات در بین گریدهای گوناگون ۶۹
۳-۲-۱۱- اشتراکات با سایر فناوریهای مهم ۶۹
۳-۲-۱۲- وب جهانگستر ۷۰
۳-۲-۱۳- ASP و SSP 71
3-2-14- محاسبات نظیر به نظیر (P2P) 72
3-2-15- سایر ابعاد گرید ۷۲
۳-۳- سیستم‌های چند عامله ۷۳
۳-۳-۱- تعریف عامل ۷۳
۳-۳-۲- ساختار سیستم‌های چند عامله ۷۶
۳-۴- داده‌کاوی ۷۶
۳-۴-۱- دسته‌بندی ۷۷
۳-۴-۲- خوشه‌سازی ۷۹
۳-۴-۳- اکتشاف قانون وابستگی ۷۹
۳-۴-۴- اکتشاف الگوی ترتیبی ۸۰
۳-۴-۵- رگرسیون ۸۱
۳-۴-۶- اکتشاف انحراف ۸۱
۳-۴-۷- معیارها در داده‌کاوی ۸۱
۳-۴-۸- داده‌ها ۸۲
۳-۴-۹- پردازش داده ۸۳
۳-۴-۱۰- تجمع ۸۴
۳-۴-۱۱- نمونه‌گیری ۸۴
۳-۴-۱۲- کاهش ابعاد ۸۵
۳-۴-۱۳- انتخاب زیرمجموعه‌ای از ویژگی‌ها ۸۶
۳-۴-۱۴- ایجاد ویژگی جدید ۸۷
۳-۴-۱۵- گسسته‌سازی ۸۸
۳-۴-۱۶- تبدیل صفت ۸۸
۳-۴-۱۷- شباهت و عدم شباهت ۸۸
۳-۴-۱۸- فاصله اقلیدسی ۸۹
۳-۴-۱۹- فاصله Minkowski 90
3-4-20- چگالی ۹۱
۳-۴-۲۱- دسته‌بندی ۹۱
۳-۴-۲۲- درخت تصمیم‌گیری ۹۳
۳-۴-۲۳- ایجاد درخت ۹۵
۳-۴-۲۴- انتخاب فیلد محوری ۹۶
۳-۴-۲۵- پیدا کردن بهترین تفکیک ۹۷
۳-۴-۲۶- Gini Index 97
3-4-27- پیدا کردن مقدار تفکیک برای فیلدهای محوری پیوسته ۹۸
۳-۴-۲۸- Entropy (INFO) 99
3-4-29- تعیین شرط توقف ایجاد درخت ۱۰۱
۳-۴-۳۰- برتری‌های درخت تصمیم‌گیری ۱۰۱
۳-۴-۳۱- مسائل جانبی مربوط به دسته‌بندی ۱۰۲
مراجع ۱۰۳