بخشی از مقاله
چکیده
بنیان اصلی پردازش و بهینهسازی الگوهای پرسوجوهای مکرر XML بر مبنای ساختار درختی آن بنا شده است و این بدان معنی است که ساختار و محتوا در این سندها در کنار یکدیگر هستند. با افزایش چشمگیر اسناد XML اهمیت پردازش بهبود پرسوجوهای XML بیشتر به چشم میخورد .اغلب روشهای کاوش قوانین انجمنی در مرحله اول کار خود کلیه اقلام پرتکرار را از بین تمام اقلام موجود در دادهها جستجو میکنند که این امر نیازمند خواندن مکرر کل داده ها از حافظه است.
الگوریتم های زیادی برای کشف قوانین انجمنی تاکنون ارائه شده اند. بخش عمده و نسبتا زمانگیر در اکثر الگوریتم های موجود از جمله سه روش مد نظر در این مقاله Apriori - ، - TOP-K , FP -Growth ، جستجوی اقلام پر تکرار است. برای بهینه سازی این فرایند الگوریتم های پیشنهاد شده رویکردهای متفاوتی دارند. تلاش بسیاری از روشها بر کاهش تعداد دفعات مراجعه به حافظه جهت خواندن داده ها است .
در این مقاله سعی بر این شده تا با بررسی سه الگوریتم کشف الگوهای پرسوجوی مکرر، آنها را از لحاظ سه معیار اصلی سرعت، حافظه و زمان اجرا بررسی نماییم و یک مقایسه کلی درباره الگوهای پرسوجوی مکرر مطرح شده در اسناد XML داشته باشیم. نتایج حاصل از تحقیق نشان می دهد که الگوریتم Top-k در اکثر موارد بسته به پیمایش نسبت به دو الگوریتم دیگر از لحاظ معیارهای ذکر شده عملکرد بهتری دارد.
-1 مقدمه
XML1 زبان استانداردی برای جابجایی اطلاعات میان برنامههای گسترده بر روی شبکه جهانی اینترنت میباشد. ولی کاربرد اصلی و مهم XML تبادل اطلاعات بر روی اینترنت است.
اطلاعات ذخیره شده بصورت XML را میتوان با حالات متفاوت و اعمال سناریوهای متفاوت نمایش داد. برخلاف HTML تکتولوژی XML دارای اطلاعات از قبل تعریف شده و مشخصی برای نحوه نمایش اطلاعات نیست. تگهای تعریف شده در یک سند XML ، بصراحت ساختار و محتویات را ارائه خواهند داد.
پس از آنکه XML به یکی از قالب های مهم برای ذخیره و تبادل داده ها بر روی وب معنایی تبدیل شد و مورد پذیرش گسترده قرار گرفت، تعداد و حجم اسناد XML افزایش یافت و در نتیجه پایگاه دادههایی برای مدیریت اسناد XML به وجود آمدند. با افزایش چشمگیر اسناد XML اهمیت پردازش بهبود پرسوجوهای XML بیشتر به چشم میخورد. سندهای XMLذاتاً درختی - گرافی شکل - هستند و این بدان معنی است که ساختار و محتوا در این سندها در کنار یکدیگر هستند
در این مقاله با استفاده از دیتاست DBLP ، ابتدا پیش پردازشی یر روی دیتاست با استفاده از زبان C++ انجام می دهیم .به این صورت که ابتدا فایل دیتاست را به یک فایل متنی تبدیل کنیم و با پردازش متن کلیه تراکنش های موجود را استخراج نماییم، نتیجه این پیش پردازش در فایلی به اسم output.txt ذخیره می شود و به عنوان ورودی در کدهای متلب مورد استفاده قرار می گیرد. سپس الگوریتم های Apriori، FP_Growth ، Top-k در نرم افزار متلب پیاده سازی می شوند و در نهایت معیارهای حافظه ، سرعت و زمان اجرا را مورد بررسی قرار می دهیم؛ و یک مقایسه کلی بین این سه الگوریتم انجام خواهد شد.
-2 تحقیقات مرتبط
الگوریتمهای زیادی برای کشف قوانین انجمنی تاکنون ارائه شدهاند. بخش عمده ونسبتاً زمانگیر در اکثر الگوریتمهای موجود از جمله سه روش مد نظر در این مقاله، جستجوی اقلام پر تکرار است. برای بهینهسازی این فرایند الگوریتمهای پیشنهاد شده رویکردهای متفاوتی دارند. تلاش بسیاری از روشها بر کاهش تعداد دفعات مراجعه به حافظه جهت خواندن دادهها است. از کاراترین روشهای موجود میتوان به روشهای Apriori، FP-Growth و TOP-K اشاره کرد.
Apriori به دلیل مراجعاتنسبتاً زیاد به حافظه کاراییاش نسبت به روشهای دیگر پایینتر است. روش FP-Growth در فرایند جستجوی اقلام پرتکرار ، هیچ قلم کاندیدی تولید نمیکند. در این الگوریتم در مجموع دادهها 3 بار پیمایش میشوند و بعد از آن ساختمان داده خاصی از جنس درخت درهمساز در حافظه ساخته میشود که تمام اقلام پر تکرار را میتوان مستقماًی با پیمایشهای خاصی بر روی این درخت به دست آورد، بدون اینکه نیازی به تولید اقلام کاندید باشد. اشکال عمده این روش نیاز به حافظه زیاد در ارتباط با مجموعه دادههای بسیار حجیم است کهعملاً در بعضی مواقع اجرای الگوریتم را غیر عملی میسازد .
- حقجو سانیجی ، - 1386 در روش پیشنهادیاش، تعداد اسنادی که پرسوجو روی آنها اجرا میشود را کم نموده و در نتیجه زمان اجرای پرسوجو کاهش مییابد . در این روش با تبدیل درخت اسناد XML به درخت دودویی و با ارائه الگوریتمی از ویژگی درختان دودویی برای طبقه بندی اسناد XML استفاده نموده است.
- رضوان، - 1392 طی تحقیقی که نمود بیان داشت که، یکی از مهمترین کارهایی که در زمینه پیدا کردن الگوهای درختی پرتکرار صورت گرفته ، یافتن روابط وابستگی است ؛ الگوریتم های بسیاری برای یافتن الگوهای درختی پرتکرار پیشنهاد شده است که یکی از آنها، الگوریتم Apriori میباشد. همچنین به بررسی انواع الگوها در مسأله کاوش الگوهای پرتکرار می پردازد ؛ و در نهایت به کاوش الگوهای پرتکرار بر روی داده های معمولی و داده های بزرگ پرداخت.
- فخراحمد ، - 1387 ،بعد از کشف کلیه اقلام پرتکرار از مجموعه دادهها، گام بعد یعنی تولید قانون به روشی مستقیم و سریع صورت میگیرد. بنابراین روشهای مختلفی که ارائه میشود، در واقع تفاوتشان در نحوه کشف اقلام پرتکرار است.
روشهای نامبرده Apriori - ، FP-Growth، Top-K ، و غیره - ، همگی از روش جستجوی پایین به بالا استفاده میکنند. بدین معنی که لیست مجموعه اقلام پرتکرار کشف شده در ابتدا خالی است و هر قلم دادهای که به عنوان پرتکرار شناخته شود، به لیست اضافه میگردد.
سپس در هر مرحله ترکیبات مختلف از اقلام پرتکرار مراحل قبل مورد بررسی قرار میگیرند. این عمل تا جایی ادامه مییابد که بزرگترین ترکیب پرتکرار از اقلام شناخته شود. در مجموع مشکلات عمده روشهای ذکر شده، نیاز به دسترسیهای متعدد به حافظه و همچنین شمارشهای زمانبر اقلام داده جهت کشف مجموعه اقلام پرتکرار است.
- می و همکاران ، - 2007 از الگوریتم FP_Growht برای سرعت بخشیدن به استخراج الگوهای پرسوجوی مشابه در مورد ساختار دادههای XML استفاده نمودند. چون در روش Apriori باید تمام آیتمها در پایگاه داده join شوند و سپس در هر مرحله اسکن انجام شود، در این مقاله به منظور کاهش زمان و پیچیدگی از روش FP-Growth برای پیداکردن الگوهای پرسوجوی مشابه XML استفاده میشود.
- تسو و همکارش ، - 2010 به یافتن الگوریتم مؤثر به نام TXMiner ، برای پیدا کردن الگوهای پرسوجوی مکرر XML پرداختند. برخلاف الگوریتمهای موجود، پیشنهاد شد ایدههای جدید، تنها با شمارش و تست زیر درختان کاندید از پرسوجو با تکرار کم XML در الگوریتم TXminer انجام شود. نتایج شبیه سازی نشان داد که TXminer بهتر از الگوریتمهای دیگر در زمان اجرا است. این روش ترکیبی از پرسوجوهای ارائه شده XML و تجمع تعدادی از این پرسوجوها در پایگاه داده میباشد.
- گرگانی ، - 1385 روش بهینه برای پردازش پرسوجوهای XML را، استفاده از راهنمای پرسوجو و راهنمای تطبیق الگو بیان نمود؛ با این مضمون که گرههایی پردازش میشوند کهحتماً قسمتی از جواب نهایی را تولید میکنند. با ارائه این ایده ابتدا پرس و جو روی راهنمای پرس و جو انجام می شود؛ نتیجه این اجرا تولید راهنمای تطبیق الگو است. در نهایت راهنمای تطبیق الگو با داده های واقعی در سند محاسبه می شود و جواب نهایی به دست می آید.
- چن ، - 2012 برای کشف الگوهای پرسوجوی مکرر XML برای برنامهریزیهای کاربردی ebXML یک الگوریتم استخراج مؤثر به نام ebxminer را پیشنهاد نمود، که جمعآوری پرسوجوهای XML و سپس شمارش پرسوجوهای کاندید کم تکرار XML در ebxminer می باشد .
- آیدا و همکاران ، - 2012 برای کشف الگوهای پرسوجوی مکرر الگوریتمی به نام POTminer ارائه نمودند که به دلیل کمبود حافظه در زمان استخراج الگوهای پرسوجوی مکرر، و برطرف نمودن آن، الگوریتمی مقیاس پذیر میباشد .
- لی و همکاران ، - 2009 از یک الگوریتم کارآمد به نام Esprit به منظور یافتن الگوهای پیدرپی برای بهره وری از استخراج الگوهای مکرر استفاده کردند که این الگوریتم به یافتن تدریجی توالیهای مکرر معتبر برای تراکنشهای در حال تکامل پایگاه داده با ترکیب دو شاخص جدید میپرداخت؛ همچنین چندین تکنیک بهینهسازی را مورد بررسی قرار دادند؛ از جمله بازنویسی پرسوجوهای ذخیرهسازی جستجو و ذخیرهسازی و جایگزینی برای بهبود عملکردها.
- ونگ و همکاران ، - 2003 روشی به نام holistic twig optimal ارائه نمودند که این روش سعی میکرد حجم گرههای میانی را کم کند و عمل شکستن پرسوجو را انجام ندهد. تاکید این نویسندگان تنها بر این بود که گره های برگ موجود در پرس و جو را پردازش کند و تعداد مقایسه هایی را که مابین گره های برگ پرس و جو انجام می شود را به کمترین حالت ممکن برساند به طوری که در حالت ایده آل هر مقایسه یک قسمت از جواب را تولید می کند .
- یان ، - 2014 روش Top-K را پیشنهاد داد که عملکرد برجستهای از نظر زمان اجرا، حافظه و مقیاس پذیری دارد. وی با استفاده از روش ترکیبی کاهشی - CRM - ، با سرعت بیشتری به کشف الگوهای پرتکرار می پردازد .
