مقاله کشف قوانین وابستگی داده کاوی به صورت موازی با استفاده از OPEN MP

بخشی از مقاله

*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***

کشف قوانین وابستگی داده کاوي به صورت موازي با استفاده از OPEN MP
چکیده
امروزه حجم بسیار زیادي از دادهها در پایگاه هاي داده اي ذخیره گردیدهاند. براي یافتن اطلاعات و شناسایی بسیاري از الگوهاي پنهان شده در این دادهها، نیازمند ابزار و تکنیکهاي جدیدي میباشیم. بسیاري از سازمان ها پایگاه داده هاي فوق العاده بزرگی از داده هاي تجاري و علمی ایجاد کرده اند، پیشرفت علم و متعاقب آن تکنولوژي نوع جدیدي از داده ها را معرفی نموده است که بسیار پر تکرار، سریع و در عین حال نامحدود می باشند که این نوع داده ها جریان داده data stream نامیده می شوند.با توجه به ماهیت جریان داده اي ، امکان ذخیره سازي داده هاي ورودي و مرور دوباره آنها وجود نداشته و می بایست به جاي جواب هاي دقیق به دنبال جواب هاي نسبی باشیم که تا حد امکان به جواب هاي دقیق نزدیک باشند.
استخراج معادن از الگوهاي پرتکرار نوعی جالب از داده کاوي است.ما در اینجا الگوریتمی ارائه می دهیم که به صورت موازي پیاده سازي شده است. براي موازي سازي این برنامه از OPEN MP استفاده کرده ایم. . OMP نسخه اي از MPI است ولی در عین حال قدرتمند ترو توانمندتر مسایل موازي سازي را انجام می دهد .
کلمات کلیدي : داده کاوي ، قوانین وابستگی ، الگوریتم موازي، Apriori ، Open Mp

مقدمه
با در دسترس بودن ذخیره سازي ارزان قیمت و پیشرفت در فن آوري دریافت اطلاعات، بسیاري از سازمان ها پایگاه داده هاي فوق العاده بزرگی از داده هاي تجاري و علمی ایجاد کرده اند، پیشرفت علم و متعاقب آن تکنولوژي نوع جدیدي از داده ها را معرفی نموده است که بسیار پر تکرار، سریع و در عین حال نامحدود می باشند که این نوع داده ها جریان داده ( ( data stream نامیده می شوند.با توجه به ماهیت جریان داده اي ، امکان ذخیره سازي داده هاي ورودي و مرور دوباره آنها وجود نداشته و می بایست به جاي جواب هاي دقیق به دنبال جواب هاي نسبی باشیم که تا حد امکان به جواب هاي دقیق نزدیک باشند.
کشف قوانین وابستگی یک مسئله مهم در داده کاوي می باشد ]١.[ اخیرا، تحقیقات قابل توجهی در طراحی الگوریتم هاي سریع براي این کار انجام شده است .[8] [7] [6] [5] [4] [3] [2] [1] کار هاي انجام شده تا کنون بر روي طراحی الگوریتم هاي سري متمرکز شده است. از آنجا که پایگاه داده هایی که کاوش می شوند اغلب بسیار بزرگ هستند (و با گیگابایت و حتی ترابایت اندازه گیري می شوند)، الگوریتم هاي موازي مورد نیاز می باشند.
مساله کشف قوانین وابستگی، پیدا نمودن دسته اي از اقلام می باشد که در صورت فروش رفتن بخش خاصی از داده هاي دسته، بخش دیگر نیز با احتمال بالایی به فروش برسد. قانون وابستگی }شیر  پنیر{ را در نظر بگیرید. این بدین معنا می باشد که در صورت وجود کالاي شیر در سبد خرید مشتري ، به احتمال مشخصی این مشتري کالاي پنیر را نیز خریداري نموده است. دانستن اینچنین قوانینی در مدیریت فروش سوپر مارکت بسیار حائز اهمیت خواهد بود[9]
این مقاله کاوش موازي قوانین وابستگی را با استفاده open mp بررسی می کند.وسازماندهی بقیه مقاله به شرح زیر می باشد بخش 2 به بررسی مختصري از Open Mp می پردازد که الگوریتم پیشنهادي با کمک آن حل شده است و در بخش 3 به بررسی مختصري از مساله کاوش قوانین وابستگی [1]و الگوریتم Apriori می پردازد و بخش 4 الگوریتم موازي را شرح می دهد.و در بخش 5 عملکرد نسبی معادلات و در بخش6 الگوریتمFP-growth را مورد بررسی قرار داده است. و بخش 7 قطعه کدهاي الگوریتم موازي را شرح می دهد ونتایج حاصل را بخش 8 ارائه می دهد.

-2 معرفی Open Mp
در اوایل دهه 90 تعدادي از فروشندگان ماشینهاي حافظه اشتراکی،یک هدف مشترك را مشخص ساختند که تولید یک زبان برنامه نویسی براساس فرترن بود، هدف از ساخت این زبان عبارت بود از:
-1کاربر بتواند در آن برنامه عادي سریال فرترن را نوشته و سپس با استفاده ازdirective ها مشخص سازد که چه حلقهاي باید موازي پیاده سازي شود .
- 2 موازيسازي حلقه در میان پردازندههاي smp) چند هسته اي ) وظیفه کامپایلر بوده و باید بهصورت خودکار انجام شود.
در کد برنامه قسمتی که باید بهصورت موازي اجرا شود توسط دستورات خاص مشخص میشود. سپس با توجه به خواسته هاي برنامه وظایف رشتههاي پردازشی معلوم شده وهرکدام به یک پردازنده نسبت داده میشوند. پس ازپایان کار رشتههاي پردازشی بهصورت موازي، عمل Join انجام شده و دوباره کنترل کار به master thread برمیگردد.
پیش از شروع در نظر داشته باشید که کدهایی که در این مقاله آورده شدهاند، به زبان C++ هستند، اما به راحتی میتوان ساختار کلی را براي زبان هاي دیگر نیز بسط داد. ازمزایاي اصلی Open MP میتوان به شباهت فراوان کد موازي برنامه و کد سریال آن اشاره کرد. در واقع، با استفاده از Open MP کد سریال را با اضافه شدن چند خط directive میتواند به یک کد موازي تبدیل کند. همچنین از مزایاي دیگر Open MP میتوان از سادگی، استاندارد بودن، تطابق با پلتفرمهاي مختلف و محبوبیت ویژه در میان جامعه برنامهنویسان یاد کرد.
باید توجه داشت، Open MP تضمین نمیکند که از حافظه اشتراکی استفاده بهینه خواهد کرد. همچنین مواردي مانند وابستگی دادهها، race conditions یا deadlock ها باید توسط خود برنامه نویس در کد برنامه کنترل شود و Open MPعموماً نمیتواند کاري درباره آنها انجام دهد. همزمان سازي ورودي و خروجی هنگام دسترسی موازي و چک کردن ترتیب اجراي کد برنامه نیز از جمله وظایف برنامه نویس است و از عهده Open MP خارج است. بهاین ترتیب، برنامهنویس باید ساختار کد و الگوریتم خود را کاملاً کنترل کرده و اطمینان حاصل کند که موارد ذکر شده در اجراي برنامه رخ نخواهد داد.
فرمت اصلی directive هاي کامپایلر در C++ به این صورت است:
# pragma omp directive-name [clauses] newline
-3مروري بر الگوریتم Appriori
امروزه یافتن قوانین وابستگی در بسیاري از کاربردها چون کاوش اطلاعات به دست آمده از کاربران وب، شناسایی نفوذها در شبکه و همچنین داده هاي بیوانفورماتیک بسیار کاربرد دارد. این مساله براي اولین بار توسط آقاي آگراول و در سال 1993 تحت الگوریتم Appriori براي داده هاي ایستا معرفی گردید.
مسئله اصلی پیدا کردن قوانین وابستگی همان طور که در [1] معرفی شده است به شرح زیر می باشد. فرض کنید که ا را به عنوان مجموعه اي از اقلام باشد، که به آنها آیتم می گویند. فرض کنید D مجموعه اي از تراکنش ها باشد، آن هر تراکنش T یک مجموعه آیتم می باشد به طوري که . ما می گوییم یک تراکنش T شامل X است، مجموعه اي از برخی از آیتم هاي موجود در I ، اگر باشد. یک قانون وابستگی به شکل بیان می گردد، که در آن است. . مجموعه اقلام به ترتیب مقدم (سمت چپ) و تالی (سمت راست) قانون وابستگی نامیده می شوند. براي روشن شدن مفهوم ما از یک مثال ساده مانند فروشگاه مواد غذایی استفاده می کنیم.. مجموعه اي از اقلام ورودي در فروشگاه شاملI={milk,bread,butter} می باشد و یک دیتا بیس از اقلام ورودي در جدول زیر نشان داده شده است.

عدد 1 بیانگر وجود آن محصول و عدد 0 بیانگر عدم وجود آن محصول است که یک قلم داده اي خاص در یک تراکنش می
باشد. یک قانون وابستگی نمونه براي سوپر مارکت می تواند به شکل زیر باشد که به این معنی است که اگر butter و bread فروخته شده اند، مشتري همچنین milk را نیز خواهد خرید .
میزان پشتیبان یک مجموعه داده اي بیانگر کسري از تراکنش ها در پایگاه داده است که شامل مجموعه داده x میباشند . می باشند. در مثال فوق داراي ساپورت است . این مجموعه داده اي در 20 درصد از تراکنش ها مشاهده شده اند .
میزان اعتماد یک قانون به صورت زیر تعریف می گردد. و بیانگر کسري از داده هایی است که در آن با مشاهده مجموعه داده اي X مجموعه داده اي Y نیز مشاهده شده است.

درمثال بالا قانون داراي اعتماد می باشد که این بدین معنی است، 50 درصد از تراکنش هایی که شامل و می باشند. یعنی در 50 درصد مواردي که milk و bread بایکدیگرخریداري شده است، مشتري butter را نیز خریداري کرده است. در واقع میزان اعتماد می تواند به عنوان تخمین احتمال نیز ارزیابی شود.
قوانین وابستگی می بایست میزان حداقل پشتیبان و میزان حداقل اعتماد تعیین شده توسط کاربر را با یکدیگر برآورده سازند.
مساله یافتن قوانین وابستگی به دو مرحله جداگانه تقسیم بندي می گردد . اول. ابتدا مینیمم پشتیبان براي یافتن مجموعه هاي داده اي پرتکرار در پایگاه داده استفاده می گردد و تمامی اقلام داده اي پرتکرار استخراج می گردد. دوم. این اقلام داده اي پرتکرارو مینیمم اعتماد براي تشکیل قوانین وابستگی مورد استفاده قرار می گیرند.

الگوریتم Apriori

ما در الگوریتم با یک مثال براي پارتیشن بندي Lk به صورت زیر اینگونه شرح می دهیم :

تمام اعضاي آن همگی داراي پیشوند مشترك AB می باشند. توجه داشته باشید که کاندید هاي ABCD، ABCE، ABDE و ABCDE نیز داراي پیشوند AB می باشند. روند ایجاد کاندید Apriori (بخش (3 این کاندید ها را تنها توسط اتصال آیتم ها در ایجاد می کند .
-4 الگوریتم هاي موازي
ما ابتدا سه الگوریتم موازي براي اولین زیر مسئله - مسئله پیدا کردن تمام مجموعه آیتم هاي مکرر - ارائه می کنیم.
الگوریتم ها را یک ساختار غیر مشترك فرض می کنیم، که در آن هر کدام از پردازنده هاي N داراي حافظه خصوصی و یک دیسک خصوصی می باشند. پردازنده ها توسط یک شبکه ارتباطی متصل می شوند و تنها می توانند با انتقال پیام ارتباط برقرار کنند. مبناي ارتباطات (عنصرهاي پایه ارتباطی) مورد استفاده توسط الگوریتم ما بخشی ازMPI (رابط انتقال پیام) مجموع برنامه هاي ارتباطات پشتیبانی در SP2 می باشند و در حال حاضر کاندید هاي مرتبط با یک انتقال پیام ارتباطی استاندارد مورد بحث می باشند . داده ها به طور مساوي بر روي دیسک هاي متصل به پردازنده ها توزیع می شوند، یعنی هر دیسک پردازنده داراي تقریبا تعداد مساوي از مبادلات می باشد.

-4-1 الگوریتم :1 توزیع شمار
این الگوریتم از یک اصل ساده مجاز (محاسبات تکراري به صورت موازي در عوض پردازنده هاي بی اثر براي جلوگیري از ارتباط) استفاده می کند. پاس اول خاص است. براي تمام پاس هاي دیگر 1 <K، الگوریتم به شرح زیر عمل می کند:

1. هر پردازنده Pi با استفاده از مجموعه آیتم کامل مکرر Lk-1 ایجادشده در انتهاي پاسK-1 یک Ck کامل را ایجاد می کند. مشاهده می کنید که تا زمانی که هر پردازنده داراي Lk-1 یکسانی است، آنها Ck یکسانی را ایجاد می کنند.

2. پردازنده Pi یک پاس بیشتر از داده هاي پارتیشن Di خود ایجاد می کند و شمارهاي پشتیبانی موضعی براي کاندید ها در Ck را توسعه می دهد.

3. پردازنده Pi شمارهاي Ck را با تمام پردازنده هاي دیگر به منظور توسعه شمارهاي Ck کلی مبادله می کند. پردازنده ها در این مرحله مجبور به همگام سازي می باشند.

4. اکنون هر پردازنده Pi، Lk را از Ck محاسبه می کند.

هر پردازنده Pi به طور مستقل براي خاتمه دادن یا ادامه دادن به پاس بعدي تصمیم گیري می کند. تصمیم گیري در مورد اینکه تمام پردازنده ها داراي Lk یکسان باشند یکسان خواهد بود .

-4-2 الگوریتم :2 توزیع داده
از ویژگی هاي جذاب الگوریتم توزیع شمارشی این است که هیچ داده چند تایی بین پردازنده ها رد و بدل نمی شود – تنها شمارها رد و بدل می شوند. به این ترتیب، پردازنده ها می تواند به طور مستقل و غیر همزمان در هنگام خواندن داده ها عمل کنند. با این حال، نقطه ضعف این است که این الگوریتم به طور موثر از حافظه کل سیستم استفاده نمی کند. فرض می کنید هر پردازنده داراي حافظه اندازه |M| است. تعدادي از کاندید ها که می توانند در یک پاس شمارش شوند توسط |M| تعیین می شوند. همانطور که ما تعداد پردازنده ها را از 1 به N افزایش می دهیم، سیستم داراي N × |M| حافظه کلی می باشد، اما ما هنوز هم همان تعداد کاندید هاي موجود در یک پاس را می شماریم، همان طور که هر پردازنده کاندید هاي یکسان را می شمارد. الگوریتم توزیع شمارشی نسبت به الگوریتم سري کاندید هاي زیادي را در هر پاس نمی شمارد.
الگوریتم توزیع داده ها براي استفاده بهتر کل حافظه سیستم طراحی می شوند همان طور که تعداد پردازنده ها افزایش می یابند.
در این الگوریتم، هر پردازنده کاندید هاي دو به دو ناسازگار را می شمارد. بنابراین، همان طور که تعداد پردازنده ها افزایش می یابد، تعداد بیشتري از کاندید ها می توانند در یک پاس شمارش شوند .
-4-3 الگوریتم :3 توزیع کاندید
یکی از محدودیت هاي دو الگوریتم توزیع شمارشی و توزیع داده این است که چون هر مبادله پایگاه داده می تواند هر