بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
کاوش k زیرگراف مکرر از گراف جریانی با استفاده از مدل پنجرهی لغزان وزندار
چکیده
در سالهای اخیر سرعت ایجاد پایگاه داده های گراف موجب شده است که توجه فراوانی به داده کاوی میان گراف یا گرافکاوی جلب شود. بنابراین کشف الگوهای مکرر، به عنوان یکی از فرآیندهای مهم در دانش داده کاوی با چالشهای مختلفی رو به رو است. یکی از این چالش ها کشف زیرگرافهای مکرر اخیر از گرافهای جریانی است که کمتر مورد بررسی و مطالعه قرار گرفتهاند. بر همین اساس در این مقاله، با ارائهی الگوریتم TFWSW (کشف k زیرگراف مکرر با استفاده از مدل پنجرهی لغزان وزندار) و بدون استفاده از پارامتر حداقل حد آستانهی پشتیبانی به استخراج زیرگرافهایی با k بیشترین تکرار جهت تولید قوانین انجمنی پرداختهایم. نتایج آزمایشها بر روی پایگاه داده ی واقعی نشان میدهند که الگوریتم پیشنهادی قابلیت استفاده از نتایج کاوش را در عمل بالا میبرد.
کلید واژه- پنجرهی لغزان وزندار، داده کاوی، زیرگراف با k بیشترین تکرار، گرافکاوی،گراف جریانی.
-1 مقدمه
در سالهای اخیر افزایش سرعت ایجاد پایگاه داده های گراف موجب شده است که توجه فراوانی به داده کاوی میان گرافها یا گرافکاوی جلب شود. پایگاه داده ی گراف نوع خاصی از پایگاه داده است که معمولاً شامل یک گراف بزرگ و یا چندین گراف کوچک میباشد. از میان الگوهای متفاوتی که در بین گرافها وجود دارد، کاوش زیرگرافهای تکراری از اهمیت زیادی برخوردار است. زیرگراف تکراری زیرگرافی است که به صورت مکرر در پایگاه داده های گراف دیده میشود. فرآیند استخراج زیرگرافهای تکراری، فرآیندی تکراری است که معمولاً از دو مرحلهی اصلی تشکیل میشود.[1] مرحلهی اول، تولید کاندید است. در این مرحله زیرگرافهایی که احتمال تکراری بودن آنها وجود دارد، یا به عبارت دیگر کاندید تکراری بودن هستند، تولید میشوند. مرحلهی بعدی، مرحلهی شمارش است.
در این مرحله، تعداد دفعاتی که کاندیدهای تولید شده در پایگاه داده دیده میشوند، شمارش میشود. برای این منظور، باید کاندید مورد نظر در پایگاه داده ی گراف جستجو شود. روش های متعارف کاوش گراف، فرض میکنند که مقدار داده ها محدود است و این فرض ذخیره سازی همه یداده ها را در حافظه یا انبار ثانویهی محلی امکان پذیر میکند. در هر یک از دو حالت هیچ نوع محدودیتی روی زمان پردازش وجود ندارد. ولی در مدل جریان داده محدودیت فضا و زمان وجود دارد. با توجه به تعداد زیاد الگوریتمهای موجود برای کاوش زیرگراف تکراری، انتخاب الگوریتم مناسب بسیار چالش برانگیز خواهد بود. از آنجایی که ادعاهای الگوریتمهای پیشنهادی تنها بر پایگاه داده -های خاصی که روی آن پیاده سازی شدهاند است، نمی توان موفقیت آنها را در پایگاه داده های دیگر تضمین کرد و ارزیابی مطلق الگوریتمها امکان پذیر نیست. تا کنون الگوریتمهای مختلفی برای کاوش زیرگرافهای تکراری در پایگاه داده های گراف ایستا و در نوع داده های مولکولی، ترکیبات شیمیایی ارائه شدهاند و کمتر به کاوش زیرگرافهای مکرر از گرافهای جریانی در پایگاه داده های پویا و داده های غیرشیمیایی پرداخته شده است. با توجه به رشد روز افزون پایگاه داده ها نیاز به الگوریتمی احساس میشود که به خوبی بر روی پایگاه داده های بزرگ و چگال عمل کاوش را انجام دهد. بر اساس نوع پایگاه داده ی گراف (تراکنشی) و با توجه به طیف وسیع کاربردهای کاوش جریان داده از جمله شبکههای حسگر، ارزیابیهای شبکهای و گزارشهای تلفنی و همچنین چالشهای موجود در این زمینه، از بین الگوریتمهای موجود در کاوش زیرگرافهای مکرر در پایگاه داده های ایستا از الگوریتم AGM بهبود یافته به همراه مدل پنجرهی لغزان وزندار جهت کاوش زیرگرافهای مکرر از پایگاه داده ی تراکنشی گراف جریانی استفاده میشود. طبق مطالعات انجام شده در الگوریتمهای مطرح در زمینهی کاوش زیر گرافهای مکرر در گراف جریانی روش ما اولین کاری است که با استفاده از مفهوم پنجرهی لغزان وزندار به کاوش روی گرافهای تراکنشی جریانی میپردازد.
-2 کارهای مرتبط
مسئله ی کاوش الگوهای ترتیبی و مکرر به شدت در ادبیات در مفهوم داده های سبد بازار برای هر دو مورد ایستا و پویا مورد مطالعه قرار گرفتهاند.[4,3,2] این مسأله همچنین در مفهوم جریانهای داده مورد مطالعه قرار گرفته است.[4,3] مسألهی کاوش الگوی مکرر در داده های گراف در کارهای اخیر [8,7,6,5] مورد مطالعه قرار گرفتهاند. الگوریتمهای بسیاری در زمینهی کاوش اقلام مکرر در داده های جریانی مطرح شدهاند. با توجه به مدل پنجرهی لغزان مورد استفاده در این تحقیق برخی الگوریتمهایی که با استفاده از این مدل، به کاوش مجموعه اقلام مکرر در پایگاه داده های جریانی میپردازند و مورد مطالعه قرار گرفتهاند در [13,12,11,10,9] قابل دسترس هستند. همچنین، الگوریتمهای جدید و رایج در زمینهی کاوش زیرگرافهای مکرر در پایگاه داده های گراف ثابت و ایستا در [14] با معیارهای متفاوت مورد مطالعه و مقایسه قرار گرفتهاند. به هر حال این تکنیکها و الگوریتمها نمیتوانند به طور مستقیم برای کاوش زیرگرافهای مکرر ازگراف تراکنشی جریانی مورد استفاده قرار بگیرند. بنابراین با توجه به نوع پایگاه داده های مورد نظر در این تحقیق، از الگوریتم AGM (مبتنی بر اپریوری) استفاده میکنیم، به این دلیل که نتایج آزمایشها در [15] نشان داده اند که این الگوریتم برای پایگاه داده ای از گرافهای چگال و بزرگ و ناهمبند (مجزا) و نیز برای مسائل دنیای واقعی کارایی و راندمان بالایی دارد.
-1-2 روش AGM
در الگوریتم پیشنهادی از روشی بنام [16] AGM، که به طور موثر قوانین انجمنی را از زیر ساختهایی که در یک مجموعه داده به طور مکرر دیده میشوند می یابد، استفاده میکنیم. یک تراکنش گرافی به وسیلهی یک ماتریس مجاورت نمایش داده میشود و الگوهای تکرار شوندهای که در ماتریس ها دیده میشوند از الگوریتم توسعه داده شده تحلیل سبد خرید، استخراج میشوند. کارایی آن برای داده ی شبیه سازی شدهی ساختگی، ارزیابی شده است. راندمان بالای آن برای مسائل دنیای واقعی تأیید شده است .[17]
الگوریتم مورد استفاده، زیرگرافهای استنتاجی را که به طور مکرر در تراکنشهای ساختیافته گرافی هستند را استخراج میکند. مشابه آنالیز سبد خرید، قواعد انجمنی برای شرح بدنه زیرگراف استنتاجی با ریشه زیرگراف استنتاجی دیگر، تحت پشتیبانی و اطمینان مشابهی از الگوریتم اپریوری تعریف شدهاند .[18]
چون ماتریس مجاورت و ماتریس کدگذاری فقط برای بیان گرافی که نودهای برچسبدار دارد، مناسب است و برای نمایش لینکهای برچسبدار و لینکهای خود حلقهای مناسب نیست، نیاز به پیش پردازش برای تبدیل گرافهای اصلی یا کلی به گرافهایی که نودهای برچسبدار، لینک های بدون برچسب و لینکهای بدون خود حلقهای دارند، وجود دارد. همچنین سطرها و ستونهای متناظر با نودهای گراف در ماتریس مجاورت به صورت الفبایی مرتب شدهاند تا ابهام در نمایش گراف را کاهش دهند. چون گرافها با ماتریس مجاورت بیان شدهاند، نیاز دارند
که به صورت منحصر به فرد در پردازشهای استخراج بعدی مرتب بشوند، یک کد برای هر ماتریس مجاورت معرفی شده است. مزیتی که این کدگذاری دارد این است که حافظهی مورد نیاز را کاهش میدهد. نمایش ماتریس حافظه زیادی نیاز دارد در حالی که کدگذاری به این حافظهی زیاد نیاز ندارد. وقتی که گرافها به وسیلهی کدهای ماتریس مجاورت نمایش داده شدند، کدهای زیرگراف استنتاجی تکرارشونده به روش پایین به بالا، مشابه با الگوریتم اپریوری به دست میآیند. ماتریس مجاورت یک گراف منحصر به فرد نیست. یک گراف مشابه را بیش از یک ماتریس مجاورت نشان میدهد. بنابراین ماتریسی که زیرگراف استنتاجی تکرارشونده را نشان می دهد به شکل مخصوصی به نام "فرم نرمال" محدود شده است. مبتنی بر نمایش ماتریس فرم نرمال، "عملگر پیوند" برای استخراج کاندیدهای زیرگرافهای استنتاجی تکرارشوندهای که اندازهی بزرگی دارند، استفاده میشود. پس از تولید کد تمام کاندیدهای زیرگرافهای استنتاجی تکرارشونده، فراوانی آنها با دستیابی به تراکنش گراف شمرده میشود. گرچه تا وقتی که فرمهای نرمال چندگانه، یک گراف را نمایش میدهند، نمایش فرم نرمال هنوز ابهام دارد. نمایش "فرم متعارفی" ماتریس مجاورت و کدهای آن برای جمع آوری تعداد هر زیرگراف استنتاجی تکرارشونده، معرفی شدهاند. برچسبگذاری متعارف چک کردن همریختی را آسان میکند، چون تضمین میکند اگر یک جفت از گرافها همریخت هستند، سپس برچسبگذاری متعارفشان یکسان خواهد بود (کوراموچی و کریپایس .[19] (2001
-3 الگوریتم پیشنهادی
همان طور که در بخش قبل بیان شد، الگوریتم پایهی مبتنی بر اپریوری، AGM، جهت استخراج زیرگرافهای مکرر از پایگاه داده ی گراف ایستا با استفاده از پارامتر حداقل حد آستانه-ی پشتیبانی ارائه شده است. در حالی که در این تحقیق با استفاده از الگوریتم AGM و چهارچوب پیشنهادی (پنجرهی لغزان وزندار)، یک الگوریتم جدید به نام TFWSW ارائه می-دهیم.
-1-3 مراحل الگوریتم TFWSW
در الگوریتم پیشنهادی فرض بر این است که گرافها را در قالب ماتریسهای مجاورت متناظر بر اساس رئوس مرتب شده به صورت تراکنش در اختیار داریم. در الگوریتم ارائه شده، پارامترهای زیر مورد استفاده قرار میگیرند.
:K نشان دهندهی تعداد زیرگرافهای با بیشترین تکرار است. :Max_l حداکثر طول است که تعداد مراحل کاوش را نمایش میدهد. یعنی تمامی زیرگرافهای با طول 1 تا حداکثر طول، در خروجی به عنوان زیرگرافهای مکرر مشخص میشوند.
:W تعداد پنجره ها را نمایش میدهد.
N : تعداد تراکنش های موجود در هر پنجره را مشخص می کند.
وزن پنچرهی iام را نشان میدهد.
بر اساس پارامترهای فوق مراحل الگوریتم پیشنهادی را درزیر بیان میکنیم:
1. ابتدا توسط کاربر در ورودی، مقادیر k و max_l و W و N و تعیین میشود.
2. تعداد N تراکنش در هر پنجره با شناسه ی یکتا قرار می-گیرند.
3. تمامی گرافهای موجود در پنجرهها به فرم نرمال و متعارف تبدیل شده و ذخیره میشوند.
4. پنجرهها یک بار پویش شده و تعداد تکرار تک گرهها در هر پنچره در زمان T1، محاسبه شده و در یک جدول پایه قرار میگیرند و سپس با استفاده از این جدول پایه و مطابق رابطهی (1) وزن هر زیرگراف به اندازه ی k محاسبه شده و در یک جدول دیگر قرار میگیرند.
:Wk وزن هر زیرگراف به سایز k
:Num تعداد تکرار هر زیرگراف در تراکنش های هر پنجره
وزن پنجره iام
.5 با استفاده از مقدار k، k تک گره ی با وزن بیشتر به عنوان زیرگرافهای مکرر به اندازه ی 1 تعیین میشوند و کمترین مقدار وزن به عنوان مینیمم مقدار وزن (MW) جهت تعیین مکرر بودن زیرگراف های به اندازه ی انتخاب میشود و همچنین کمترین مقدار تکرار به عنوان مینیمم مقدار (V) جهت شمارش تکرار زیرگرافهای کاندید توسط الگوریتم AGM مشخص میشود.
.6 در این گام، توسط زیرگرافهای به اندازه ی k´-1 مکرر، زیرگرافهای کاندید مکرر بودن به اندازه یk´ در یک جدولی تهیه شده و تعداد تکرارشان با استفاده از جدول پایه و بدون مراجعه به پنجره ها به دست آورده میشوند. سپس با استفاده از تعداد تکرار محاسبه شده وزن هر زیرگراف کاندید به اندازه ی k´ به دست آورده میشود. و زیرگرافهای با وزن مساوی یا بیشتر از MW به عنوان زیرگرافهای کاندید به الگوریتم AGM داده میشوند تا به وسیلهی آن دو به دو تحت سه شرط موجود در این الگوریتم الحاق شده و ماتریس مجاورت متناظرشان به دست آورده شود. پس از الحاق، نرمال بودن هر کدام از این کاندیدا چک شده و در صورت غیرنرمال بودن به فرم نرمال تبدیل میشوند و سپس به فرم متعارف منتقل میشوند تا با گرافهای به فرم متعارف ورودی قابل مقایسه باشند و تعداد تکرارشان شمارش شود. در صورتی که تعداد تکرار یک زیرگراف به اندازهیk´ با حداقل مقدار v مساوی یا بیشتر از آن باشد، به عنوان زیرگراف مکرر به سایزk´ در زمان T1 مشخص میشود. این گام تا به دست آوردن تمامی زیرگرافهای به سایز 1,2,…,max_l در بازهی زمانی T1 ادامه مییابد.
.7 در این گام، تراکنشهای موجود در قدیمیترین پنجره حذف شده و و پنجرههای باقی مانده اسلاید زده می شوند تا تراکنشهای جدید در پنجرهی اول قرار بگیرند. سپس جهت به دست آوردن تمامی زیرگرافهای مکرر با حداکثر طول max_l در بازهی زمانی Ti و i=2,3,... مراحل 3 تا 6 تکرار میشوند.
بنابراین طبق مراحل بیان شده میتوان k زیرگراف مکرر را در هر بازهی زمانی Ti با استفاده از مدل پنجرهی لغزان وزندار استخراج کرد.
-4 ارزیابی الگوریتم پیشنهادی
جهت انجام آزمایشهای عملی، الگوریتم TFWSW، مورد ارزیابی قرار گرفت. آزمایشها بر روی کامپیوتر همراه با پردازندهی Intel ( R) Core (TM)2 Duo CPU 2GHz و حافظه اصلی 2GB و سیستم عامل Linux Ubuntu 12.10 انجام شد. جهت تست الگوریتم ارائه شده، از پایگاه داده ی واقعی ENRON استفاده شده است.
شبکه ارتباطات :ENRON این پایگاه داده شامل تعداد بسیار زیادی پیام الکترونیکی است که میان کارکنان شرکت ENRON در طول یک بازه 3 ساله رد و بدل شده است. از این پایگاه داده در کاربردهای مختلفی نظیر طبقه بندی متن، فشردهسازی گراف و همین طور تشخیص تغییرات در گراف استفاده شده است. این پایگاه داده شامل 619446 پیام است که میان 158 کاربر در طول این بازه زمانی رد و بدل شده است. در این مقاله، جهت تست الگوریتم ارائه شده، از پیامهای رد و بدل شده بین 100 کاربر استفاده شده است. برای تولید گراف این پایگاه داده به روش زیر عمل میکنیم. در این پایگاه داده هر پیام بین یک فرستنده و چند گیرنده انتقال مییابد و هر پیام یک برچسب زمانی از زمان ارسال این پیامها در خود دارد. بنابراین میتوان فرستنده و گیرندگان هر پیام را یک گره در نظر گرفت و هر پیامی که میان این گرهها رد و بدل میشود را نیز یال میان آنها در نظر گرفت که با این روش هر یال در
