بخشی از مقاله
داده کاوی اسناد XML با استفاده از استخراج قواعد انجمنی
چکیده – امروزه XML زبان انتخاب شده برای نمایش، ذخیرهسازی و مبادله در بسیاری از قلمروها همچون تکنولوژی، سرویسهای اقتصادی، سیستمهای پزشکی، هوانوردی و دفاع است. در نتیجه بسیاری از گروههای تحقیقاتی برای یافتن یک تکنولوژی جهت ذخیرهسازی، کشف دانش و آنالیز اسناد مرتبط با XML ، تحقیقاتی را آغازکرده اند. استخراج قواعد انجمنی یکی از تکنیکهای به کار گرفته شده در دادهکاوی به منظور کشف دانش به ویژه در دادههای رابطهای میباشد. در سالهای اخیر به منظور دادهکاوی اسناد XML از این تکنیک و روشهای ایجاد شده بر پایه آن استفاده شده است. همچنین در تحقیقات و کارهای فراوانی کوشیده شده است که روشهای استخراج قواعد انجمنی روی اسناد XML کاراتر و سریعتر گردند. در این مقاله بر آن هستیم تا به بررسی روش استخراج قواعد انجمنی از اسناد XML و دو الگوریتم متداول این روش بپردازیم.
کلید واژه- اسناد XML ، الگوریتم Apriori ، الگوریتم FP-Growth ، درخت FP-Tree ، Association Rules Mining ، XQuery
-1 مقدمه
با گسترش روز افزون اینترنت، میزان استفاده از مستندات XML بویژه در مبادله داده بسیار زیاد شده و تعداد مستندات XML موجود در اینترنت روز به روز در حال افزایش می باشد. زبان XML به زبان عصر اینترنت تبدیل شده و اکثر مستندات موجود در اینترنت با فرمت XML یا فرمتهای مشابه مثل زبان HTML هستند. امروزه زبان XML در طیف وسیعی از موارد شامل بازنمایی، ذخیرهسازی و انتقال اطلاعات بکار گرفته شده است، بنابراین با توجه به حجم و تعداد بسیار زیاد اینگونه مستندات وجود روشهایی جهت دادهکاوی از مستندات XML بسیار ضروری و مورد نیاز است. XML زبانی تودرتو و به سادگی دارای قابلیت تعریف ساختار خود بدون از دست دادن انعطاف پذیری میباشد.
دادهکاوی در اواخر دهه 80 میلادی نمایان شده و در دهه 90 بهبود و گسترش یافته است. این بهبود و گسترش بخصوص در زمینه تبدیل مقدار زیاد داده به دانشِ مفید بوده و انتظار میرود در آینده نیز با سرعت ادامه پیدا کند. با این وجود در مقایسه با کارایی موفق کاوش دادههای خوش ساختار همچون پایگاههای داده رابطهای و شیگرا، کاوش در دادههای نیمهساختاریافته همچون XML هنوز در مراحل اولیه خود میباشد و به دلیل ویژگیهای ذاتی آن در دو زمینه ساختار و معنا با مشکلات فراوانی مواجه است. اولین بار روش استخراج قواعد انجمنی در سال 1993 میلادی معرفی گردید.[1] از آن زمان کارهای زیادی در شاخههای مختلف این زمینه انجام گرفته است، اما استفاده از این روش بر روی دادهها و اسناد مرتبط به XML برای اولین بار در سال 2001 میلادی معرفی شد.[2] لازم به ذکر است که همین ایده اما با پیادهسازی توسط XQuery در سال 2003 میلادی ارائه شد.[3]
ساختار این مقاله به ترتیب به صورت زیر است:
در بخش دوم به تعریف مسئله استخراج قواعد انجمنی، تعریف قانون انجمنی پرداخته و پس از معرفی دو الگوریتم Apriori و FP-Growth به بررسی عملکرد آنها خواهیم پرداخت. در بخش سوم نیز دو الگوریتم را مقایسه میکنیم. در بخش چهارم که قسمت پایانی این مقاله است به نتیجهگیری و کارهای آینده XML کاوی با استفاده از استخراج قواعد انجمنی خواهیم پرداخت.
-2 مسئله استخراج قواعد انجمنی
اســتخراج قواعــد انجمنــی یــا بــه اختصــار ARM یکــی از مهمترین و تحقیقاتیترین روشهای دادهکاوی است. هدف از این روش یافتن همبستگیهای مـورد علاقـه و مـورد نیـاز، الگوهـای پرتکرار و یـافتن سـاختارهای غیرضـروری در میـان آیـتمهـا در تراکنشهای پایگاه داده یا سـاختارهای دیگـر داده اسـت. قواعـد انجمنی، قوانینی هستند که بـه رابطـههـایی همچـون وابسـتگی قطعی میان اشیاء مانند اتفاقهای همزمان اشـاره مـیکنـد. ایـن وابستگی بین آیتمها، در میان مجموعه تراکنشهـایی اسـت کـه شامل مجموعهای از این آیتمها میشود.[1]
به عبـارتی دیگـر اسـتخراج قواعـد انجمنـی یـافتن قـوانین همبستگی است که کمینه پشتیبانی و اطمینان از پـیش تعریـف شده را در پایگاه داده مورد نظر تامینکنند. این مسـئله معمـولاً به دو زیر مسئله تجزیـه مـیشـود. مسـئله اول یـافتن مجموعـه آیتمهایی است که اتفـاق افتـادن آنهـا بـیش از آسـتانه از پـیش تعریف شده در پایگاه داده اسـت کـه ایـن مجموعـه آیـتمهـا را پرتکرار یا مجموعه آیتمهای بزرگ مینامنـد. مسـئله دوم ایجـاد یک سری قوانین و رابطهها از مجموعه آیتمهای بزرگ بـه دسـت آمده با در نظر گرفتن کمینه اطمینان آنها میباشد. در ادامـه بـه بررسی بیشتر این دو مسئله میپردازیم.[4]
اولین مرحله در استخراج قواعد انجمنی، تشخیص مجموعـه آیتمهای پرتکرار است. مجموعههایی از آیـتمهـا کـه معمـولا بـا یکدیگر رخ میدهند و برای جستجوی بیشـتر در مراحـل بعـدی استفاده میشوند. به دلیل مقیـاس نمـایی فضـای جسـتجو، ایـن مرحله بـدون شـک نیازمنـد محاسـباتی قدرتمنـد و اسـتفاده از الگوریتمها و ساختار داده کـارا مـیباشـد. ایـن عامـلهـا هنگـام استفاده از دادههای بیدرنگ بسیار مهم میباشد. در این قسـمت مفاهیم و تعریفهای پایه استخراج قواعد انجمنی را بیان میکنیم و به بررسی الگوریتمهای Apriori و FP-Growth میپردازیم. در اینجا به این نکتـه بایـد توجـه شـود کـه بـرای توصـیف داده، از تراکنش و آیتم استفاده میشود.
-1-2 تعریف یک قانون انجمنی
همانگونه که اشاره شد مسئله اسـتخراج قواعـد انجمنـی در سال 1993 مـیلادی بـرای دادههـا در جـدول رابطـهای معرفـی گردید. تعریف رسمی این مسئله به شکل زیر است: [5]
فرض کنید I = {i 1, i2, . . ., im} مجموعـه آیـتمهـا هسـتند. همچنین D مجموعه تراکنشها میباشد و هر تراکنش T شـامل مجموعهای از آیتمها است بـه طـوری کـه T ⊆ I مـیباشـد. هـر تراکنش دارای مشخصه منحصـر بـه فـردی اسـت کـه مشخصـه تراکنش نامیـده شـده و بـه صـورت TID نشـان داده مـیشـود. همچنین گفته میشود تراکنش T شـامل A اسـت اگـر A ⊆ T A ) زیرمجموعهای از بعضی آیتمها در .( I
یک قانون انجمنی به صورت A ⇒ B نمایش داده مـیشـود بطوریکه B ⊆ I , A ⊆ I وA ∩ B =Ø میباشد. مجموعـه A را پیشین یا بدنه قانون و مجموعـه B را برآینـد ، نتیجـه و یـا سـر قانون مینامند. چنین قانونی به عنوان قوانین مورد علاقه خواهند بود اگر دارای چندین ویژگـی باشـد. دو ویژگـی اساسـی کـه بـه صورت فراوان در اسـتخراج قواعـد انجمنـی مـورد اسـتفاده قـرار میگیرد "پشتیبانی" و "اطمینان" قانون میباشد.
پشتیبانی بـرای قـانون A ⇒ B کـه بـه صـورت s(A ⇒ B) نمایش داده میشود، نسبت تعداد تراکنشهایی که شـامل تمـام آیتمهای مجموعه A U B به تعداد تمام تراکنشهای D میباشد. بنابراین:
دو تابع δ بر مجموعه آیتم A ، تعداد تراکنشهایی در D است که شامل تمام آیتمهای مجموعه A میباشد و به صورت δ (A) نمایش داده شده و با عنوان تعداد تکرار A نیز نامیده میشود.
همچنین اطمینان قانون A ⇒ B که به صورت c(A ⇒ B) نمایش داده میشود، نسبت تعداد پشتیبانی مجموعه A U B بر تعداد تراکنشهایی که تنها شامل مجموعه پیشین A هستند میباشد. بنابراین:
از آنجا که تمامی قوانین ممکن به دست آمده مفید نیسـتند و تعداد این قوانین ممکن مـیتوانـد بسـیار زیـاد باشـد بنـابراین وظیفــه اســتخراج قواعــد انجمنــی ایجــاد آن دســته از قــوانین از مجموعه دادههای D است که دارای مقدار پشتیبانی و اطمینـان بیشتر یا مساوی با کمینه پشیبانی و کمینه اطمینان تعریف شده باشد.[4]
یک مجموعه از آیتمها را itemset مینامند. یک itemset که دارای k آیتم است به صورت k-itemset نمایش داده میشود. یک k-itemset پرتکرار یا بزرگ نامیده میشود اگر:
یک 1-itemset پرتکرار نیز آیتم پرتکرار نامیده میشود چـرا که تنها دارای یک آیتم میباشد. همچنین قانون A ⇒ B را یـک "قانون نیرومند" میگویند اگر و فقـط اگـر A U B در مجموعـه آیتمهای بزرگ باشد و دارای اطمینان بزرگتر یا مسـاوی کمینـه اطمینان باشد.[4]
-2-2 نمونه قانون انجمنی در جدول تراکنشها
فرض کنید smin = 0.4 و cmin = 0.6 میباشد. میتوان مشاهده کرد که قانون { i2, i4 } ⇒ { i3 } دارای پشتیبانی 0.4 و اطمینان 0.66 میباشد. بنابراین این قانون به عنوان قانون انجمنی معتبر تامین کننده کمینه پشتیبانی و کمینه اطمینان میباشد.[5]
جدول :1 نمونه جدول تراکنشها [5]
-3-2 مراحل استخراج قواعد انجمنی
در واقــع وظیفــه اســتخراج قواعــد انجمنــی از مقــادیر زیــاد مجموعه داده، در فرآیند دو مرحلهای زیر خلاصه میشود: [6]
.1کشف تمامی مجموعـه آیـتمهـای پرتکـرار یـا بـزرگ در مجموعه تراکنشهای D ، کـه تـامین کننـده کمینـه پشـتیبانی هســتند. بــرای حــل ایــن زیرمســئله از الگــوریتمهــایی همچــون الگوریتم Apriori استفاده میشود.
.2استفاده از مجموعه آیتمهـای بـزرگ بـه دسـت آمـده در مرحله قبل برای ایجاد قوانین نیرومند که معمـولا الگـوریتم ایـن قسمت آسان میباشد. میتوان آن را به این صورت بیان کرد کـه برای هر مجموعه آیتم بزرگ l1، تمام مجموعه آیتمهای بـزرگ l2 یافتــه مــیشــود بــه طــوری کــه دارای دو شــرط l2 ⊆ l1 و support(l1 U l2) / support(l2) ≥ minconf باشند برای چنـین مجموعه آیتم بزرگ دارای خروجی قانون بصـورت l2 ⇒ (l1 - l2) خواهیم بود.
