بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
پردازش موازی در داده کاوی
چکیده
با افزایش روز افزون و نمایی دادهها در وب، علوم و تجارت، دیگر روشی محاسبات خطی پاسخگوی نیاز تحلیل ترکیبی در
داده کاوی، برای این حجم از اطلاعات نبوده و استفاده از روشهای محاسبات و پردازش موازی ضروریست. از میان مسائل مطرح در
داده کاوی در این مقاله مسأله آنالیز مجموعه آیتمها برای کشف قوانین انجمنی با الگوریتم استقرایی و الگوریتم کی مینز خوشه بندی در دو حالت خطی و موازی مطرح شده و کارکرد هر یک در فضای نمونه مقایسه گردیده است.
واژههای کلیدی: داده کاوی، پردازش موازی، الگوریتم کی مینز موازی، الگوریتم کشف انجمنی موازی
مقدمه
در گذشته مجموعه دادههای آماری شامل ۳۰۰ مشاهده بر روی ۳ تا ۴ متغیر بود اما امروزه با گسترش استفاده از کامپیوتر و مجموعه داده های وبی، مجموعه داده های آماری ده ها میلیون و هزاران متغیر را شامل میگردد. بنابراین محاسبات خطی پاسخگوی نیاز تحلیل ترکیبی نبوده و روشهای محاسبات موازی ضروریست. داده کاوی به معنای پیدا کردن ارتباط میان متغیرهاست که این یک مساله اماری قدیمی Matl ll] .it
تجزیه و تحلیل مجموعه ای از آیتم ها جزء مسائل مطرح در داده کاوی می باشد و مسأله معروف سبد خرید مثالی در این حوزه است. به طور مثال در یک فروشگاه کتاب که خرید از طریق سایت انجام می گیرد. سبد خرید بصورت ماتریسی S قابل تعریف است. در این ماتریس آیتم (Sij = (i,j مقادیر صفر یا یک را دارد که i امین سطر خرید مربوط به ستون کتاب j را نشان می دهد. مقدار یک نشان دهنده شامل شدن کتاب مربوط و خرید می باشد. اگر عناوین کتاب Tb-1 ، ... ،T0 باشد، سبد خرید شامل زیر مجموعه ای از عناوین کتب می باشد. در این مسأله مطلوب معرفی کتابهایی بصورت تبلیغی به مشتریان است که غالبا در کنار کتابهای دیگر بفروشی می رسد. قانون وابستگی: وابستگی دو آیتم i و j را به صورت - 1 بیان می دارد. درجه پشتیبانی : میزان وجود i و j کنارهم می باشد. اگر درجه پشتیبانی کم باشد بدین معناست که i و به ندرت کنار هم قرار می گیرند. درجه اطمینان " : (P(iii احتمال اینکه خریداری که کتاب i را خریده است تمایل به خرید کتاب نیز دارد. اگر درجه اطمینان بالا باشد بدین معناست که اگر در یک سبد خرید i وجود داشته باشد به احتمال زیاد نیز وجو دارد. درجه اطمینان بالا در کنار درجه پشتیبانی بالا مفید خواهد بود. برای داده کاوی ابتدا باید حدی برای درجه اطمینان و درجه پشتیبانی تعیین کنیم سپس هدف یافتن تمامی قوانین وابستگی میان مجموعی آیتم ها که مقادیر حدی راگذارنده باشد. آیتم جدید با استفاده از رخدادهای موجود در (TSK04). Ass. مجموعه آیتمهای دیگر رامی دهد.
2-1- الگوریتم استقرایی خطی
الگوریتمهای متنوعی برای یافتن مجموعه آیتم های تکرار شونده و قوانین وابستگی وجود دارد. معروفترین نوع آن الگوریتم استقرائی است. این الگوریتم بر پایه جستجو در عرض درخت می باشد. در ریشه درخت ما بدنبال سبد خرید با یک آیتم تکرار شونده می گردیم. برای نمونه ر یک فروشگاه برخط کتاب، ریشه شامل کتابهای تکی که حداقل به اندازه T رکورد تراکنش فروش را داشته باشد.(Tمیزان حدی برای درجه پشتیبانی است) در سطح دوم ما بدنبال سبد خرید با دو آیتم تکرار شونده می گردیم که یک آیتم آن از سطح اول باشد. به طور مثال این حالت همه جفت کتابهایی را شامل میگردد که حداقل به اندازه T رکورد فروش را داشته باشند. به ازای اجتماع تمام مجموعه های سطح 1-i ام با سطح اول مجموعههای i عضوی که حداقل به اندازه T رکورد فروش را داشته باشند، سطح i ام را تشکیل میدهند. نکته پایانی این که اگر یک مجموعه ایتم میزان تکرار شوندگی آن از مقدار حدی درجه پشتیبانی کوچکتر باشد، این مجموعه ایتم ها از درخت هرسی می شود. شبه کد این الگوریتم در ذیل آمده است.
بیان دیگر ما مجموعه آیتم با اندازه i را از روی مجموعه آیتم با اندازه 1-i می سازیم. با افزودن تمامی انتخابها ممکن که از مجموعه آیتم i-I. برای بهبود این الگوریتم راهکارهای زیادی وجود دارد تا از تکرار کارها جلوگیری شده و منجر به افزایش سرعت گردد. برای مثال برای پرهیز از بررسی مجدد دو مجموعه آیتم {2,1} ,{2 ,1 } میتوان مجموعه آیتم ها را در ترتیب الفبایی نگاهداشت.
۲- ۲- الگوریتم استقرایی موازی
در این مسأله بستر زیادی برای موازی سازی وجود دارد. دو حلقه تو در تو داخل الگوریتم مستقیماً میتواند موازی اجرا گردد. این مدل اجرای موازی عجولانه " می باشد. در این مسأله مناطق بحرانی حافظه مشترک و انتقال پیام ها می باشند که با تخصیص یک نود مدیر برای ذخیره Le Fi مشابه الگوریتمی که برای خوشه بندی بیان خواهد شد، قابل حل خواهد بود.
۳- تخمین چگالی احتمال اگر ما نمونه هایی مانند Xn و... ,X1, X2 از متغیر تصادفی X داشته باشیم در نتیجه هیستوگرامی از مقادیر این متغیر خواهیم داشت. هدف این مساله تخمین تابع f از روی هیستوگرام و استفاده از محاسبات موازی برای کاهش زمان این تخمین می باشد. اگر ما مقادیر بیشتری از X داشته باشیم هیستوگرام به f نزدیکتر و نزدیکتر خواهد شد.
۳- ۱- تخمین مرکزی محاسبه هیستوگرام به مسأله محاسبه تعداد Xiدر فواصل شکسته می شود. مهم نیست اندازه این
فواصل چقدر باشد در هر صورت هیستوگرام شامل گروهی از مستطیلی خواهد شد که می تواند یک منحنی را تخمین بزند. به طور مثال برای تخمین (25.8)f ما به سراغ فاصله [ ۲۶۰۰، ۰, ۲۴] میرویم اگر ۵۴ نقطه در این فاصله باشد به طور تقریبی نزدیکترین
نقطه با بیشترین وزن به 25.8 تخمین خوبی خواهد بود. برای تنظیم مقادیر وزن از تابع مرکزی K ستفاده می شود
بر این اساسی تابع تخمین ما بصورت زیر خواهد بود که تخمینی برای ورودی تابع، با خواهد بود
در اینجا مقادیر نامحدودی از ااً بعنوان ورودی منجر به مقادیر نامحدودی از (T(t خواهد شد. در این رابطه مقدارh پهنای باند "مسأله می باشد که بسته به عرض فاصله در هیستوگرام می باشد. همانطور که در هیستوگرام عرض هر ستون را انتخاب کنیم در این رابط مقدار h را باید انتخاب نمود.
برای مثال برای تخمین تابع چگالی به ازای = |اً5.8 = h در صورتیکه ما مقدار تابع به ازای t 88 = را داشته باشیم 1209.1=X88 چون مقدار u به نسبت بزرگ خواهد شد (K(u کوچک خواهد شد.
۳- ۲- الگوریتم موازی تخمین چگالی احتمال
۲- آزمون مقادیر مختلف h برای رسیدن به نزدیکترین تخمین، که میتوان به ازای مقدار مختلف h الگوریتم را برای یک پردازنده جداگانه اجرا نمود.
۳- استفاده از تبدیل فوریه
۴- خوشه بندی
خوشه بندی به معنای کلاس بندی مجموعه ای از دادههاست که کلاسها از قبل تعیین شده نیستند به عبارت دیگر خوشه بندی گروه بندی اشیاء مشابه و در نتیجه مجموعه ای از افراز دادهها که با حداقل عدم تجانس ایجاد شدهاند. هدف خوشه بندی تشخیص این گروهها می باشد. خوشه بندی در زمینه های مختلف مانند پردازش تصویر در بخش بندی تصویر، تشخیصی لبهها، تشخیصی صورت، تشخیص الگو و تئوری یادگیری به کار میرود. [1 Matl]
فرض می کنیم مجموعه ای از نقاط با مختصات (X,Y) داریم که طرحی شبیه زیر تشکیل دادهاند. در این شکل دو یا سه گروه از نقاط مشاهده می شود. در این مثال ما دو متغیر قد و وزن افراد را در نظر گرفته ایم. در حالت کلی ما متغیرهای زیادی خواهیم داشت. اگر تعداد متغیرها p باشد ما یک مسأله خوشه بندی p بعدی خواهیم داشت. رسم شکل برای مسأله خوشه بندی بیشتر از ۳ بعد کار ساده ای نیست. اما حداقل می توان یک الگوی عضویت از آن را ارائه داد. مثال جان و مری عضو گروه ۱ و جنی عضو گروه ۲ و ... انواع زیادی از الگوریتم های خوشه بندی وجود دارد که در ساختار درختی زیر نشان داده شده است.
در این جا ما الگوریتم K-meanS که توسط جیم مک کوئین ارائه شده است را بحث می کنیم.
۱-۴- الگوریتم خوشه بندی k-Innea In S مفروضات ما مجموعه S که از N بردار D بعدی تشکیل یافته و هیچگونه اطلاعات قبلی نسبت به آنه نداریم. هدف این الگوریم تشخیص Kزیر مجموعه 3 C1C2.C3,...CK (Ci)4-–-5 au SVij, lisi sK, 1s.js Ci│ (Vij)Jt-...L»ley, کمترین فاصله (فاصله اقلیدسی) تا میانگین (X) را نسبت به هم داشته باشند. در مثال ما اگوریم ۲۵ نفطه را به ۴ گروه، خوشه بندی می نماید.[KaL00]
ارزیابی الگوریتم k-meanS با دو معیار درون خوشهای و معیار زیر خوشه ای انجام می پذیرد. معیار درون خوشه ای برای تعیین میزان خوبی یک خوشه استفاده میگردد. انواع معیارهای درون خوشه ای(نتیجه داخلی) عبارتند از: محاسبه قطر، شعاع، واریانسی، ، واریانس ضربدر آCi) و فاصله واریانس ضربدر Cl اقلیدسی و مربع خطاها (E) می باشد. ما در اینجا از تابع مربع خطا بدلیل کارایی بهتر در الگوریتم موازی و عمومیت در میان همه خوشه ها استفاده می نماییم.
معیار زیر خوشه ای(نتیجه خارجی) تعریف میزان هزینه نهایی خوشه بندی k را تعریف می کند.
دو تعریف:
نزدیکترین فاصله: در یک فضای p بعدی نزدیکترین فاصله از رابطه فاصله اقلیدسی محاسبه میگردد. فاصله از نقطه (:a1 :.ap .) تا ( b1) bp:... از رابطه زیر محاسبه میگردد.
مرکز ثقل: مرکز گروه به نام مرکز ثقلی شناخته شده و بر اساسی میانگین مقادیر در ابعاد محاسبه میگردد. در هنگامی که p برابر ۲ باشد میانگین X ها و Y ها در یک گروه مرکز ثقل را میسازد.
las k-means riss---f این الگوریتم از مراحل زیر تشکیل شده است
۱- بصورت تصادفی K زیر مجموعه از S با تعداد اعضای N/K انتخاب می نماییم. ۲
- برای هر زیر مجموعه مرکز ثقلی را محاسبه می نماییم.
۳-K زیرمجموعه را بر اساس نزدیکترین نقاط به مراکز ثقل بازسازی می نماییم. ثقلی دیگر جابجا نشوند.
