بخشی از مقاله
چکیده:
در طی پیشرفت فناوریهای پایگاهداده و تکنیکهای جمعآوری دادهها، حجم بسیار وسیعی از دادهها تجمیع و انباشته شده است. داده کاوی به استخراج اطلاعات ضمنی، ناشناخته و مفید از دادهها گفته میشود. حجم بسیار بالای دادههای فضایی، پیچیدگی انواع دادههای فضایی و روشهای دسترسی به آنها، کارایی را به یک چالش تحقیقاتی مهم در زمینه الگوریتمهای داده کاوی فضایی مبدل میسازد . در این مقاله به بررسی مسائل مطرح در داده کاوی قوانین وابستگی از دادههای فضایی پرداخته و یک راه حل تحت عنوان "اصلاح تدریجی" با استفاده از سلسله مراتب مفهومی برای بالابردن کارایی این فرایند ارائه میگردد.
واژگان کلیدی: داده کاوی، فضایی، پایگاه دانش، استخراج قوانین
.1 مقدمه1
انفجار دادهها استخراج خودکار اطلاعات و معرفت، از دادهها را لازم و ضروری مینماید، که نهایتا به حوزه جدید "داده کاوی" و یا "اکتشاف دانش از پایگاههای داده" منتهی شده است. در واقع داده کاوی تلفیقی از حوزههای مختلف شامل یادگیری ماشین، سامانههای پایگاهداده، مصورسازی داده، آمار و تئوری اطلاعات است 6]،.[1پیشرفتهای تحقیقاتی در زمینه ساختمانهای داده فضایی و پایگاههای داده فضایی، اجرای کارآمد پرسوجوها روی پایگاههای داده فضایی را امکان پذیر نموده است.[4] این پیشرفتها به همراه پیشرفتهای دادهکاوی و انباردادهها در پایگاههای داده رابطهای، ما را به تحقیق در زمینه دادهکاوی فضایی ترقیب مینمایند.حجم بسیار بالای دادههای جمعآوری شده توسط سامانههای سنجش از دور، سامانههای تجارت الکترونیک و سایر ابزارهای جمعآوری دادهها، توسعه ابزارهای اکتشاف معرفت از پایگاههای داده بزرگ را به یک امر ضروری و حیاتی تبدیل نموده است.
.2 دادهکاوی قوانین وابستگی از دادههای فضایی
تحلیل وابستگی روابط بین اقلام داده را بر اساس وقوع مشترک آنها مییابد. به عنوان مثال تحلیل کالاهایی که در یک تراکنش با یکدیگر فروخته میشوند، بر اساس الگوریتم وابستگی انجام میشود.در این تحقیق روی دادهکاوی فضایی با استفاده از الگوریتمهای تحلیل وابستگی تمرکز خواهیم نمود. مسائل، مشکلات، تکنیکها و راه حلهای مختلف در توسعه یک الگوریتم مناسب داده کاوی فضایی قوانین وابستگی و کاربرد آن روی دادههای فضایی مورد بررسی قرار خواهند گرفت. همانطور که ذکر شد، مسئله کارایی مهمترین موضوع در اعمال روشهای متداول دادهکاوی روی دادههای فضایی است. فرایند پالایش تدریجی دادهکاوی با استفاده از گزارههای فضایی در شکل - - 1 تشریح شده است.[8]
در مرحله اول این فرایند - - A پرسوجوی کاربر که به زبان GMQL است پردازش میشود. این زبان براساس زبان DMQL، پیشنهاد شده است که در آزمایشگاه تحقیقات پایگاهداده هوشمند توسعه یافته است. در مرحله دوم - - B توصیفهای تخمینی گزارههای مکانی مورد استفاده قرار میگیرند. به عنوان مثال بهجای رابطه close_to از رابطه g_close_to استفاده میشود.[4] دادههای تخمینی با استفاده از بخش تحلیل برخط تجمیع می-شوند. سپس مربوط بودن گزارهها به فرایند دادهکاوی تحلیل میشود. محاسبات روی گزارههای تخمینی بسیار سریعتر از گزارههای دقیق صورت میگیرد. تنها گزارههایی که شرایط مورد نظر را ارضاء مینمایند به مرحله محاسبات جزئی داده میشوند. از آنجایی که معمولا بسیاری از گزارهها به فرایند دادهکاوی وارد نمیشوند، با حذف گزارههای نا مربوط در مرحله تخمینی و نه در مرحله دقیق، زمان پردازش زیادی حفظ میگردد.
فرایند پالایش تدریجی میتواند با اعمال روشهای دیگر تخمینی گسترش یابد. - حلقه . - O در مرحله بعدی - - C گزارههای دقیق مطلوب محاسبه میشوند و در مرحله - - D الگوهای فضایی بر اساس گزارههای بهدست آمده، استخراج میگردند. که ما در اینجا قوانین وابستگی فضایی را مورد بررسی قرار میدهیم. در نهایت در مرحله - - E نتایج فرایند دادهکاوی به کاربر ارائه داده میشوند. پایگاهداده فضایی ذکر شده و مؤلفه تحلیل برخط میتوانند در هرکدام از مراحل مزبور مورد استفاده قرار گیرند.[2]در واقع در قواینین وابستگی فضایی یک مجموعه خصوصیات نتیجه یک مجموعه دیگر خصوصیاتی معرفی میشوند. به عنوان مثال یک قانون وابستگی فضایی میتواند قیمت منازل در یک محدوده مکانی را وابسته به خصوصیات فضایی اطراف آن، مانند سواحل نماید.
.3 سلسله مراتب مفهومی
یکی از تکنیکهای متداول در یادگیری ماشین و دادهکاوی، روش تعمیم است. اکتشاف دانش براساس تعمیم، نیازمند یک دانش پیشزمینه به صورت سلسله مراتب مفهومی است. در مورد پایگاههای داده فضایی دو نوع سلسله مراتب مفهومی قابل استفاده خواهند بود: غیر فضایی و فضایی. این سلسله مراتب مفهومی میتوانند به صورت صریح توسط کاربر داده شوند و یا در مواردی با تحلیل دادهها، بهصورت خودکار تولید شوند.[10] مثالی از سلسله مراتب مفهومی برای "کاربری اراضی کشاورزی" در شکل زیر ارائه شده است. درحال صعود در درخت، اطلاعات بیشتر و بیشتر عمومیت مییابند، اما هنوز با سطوح مفهومی پایینتر سازگار باقی میمانند.
شکل - - 2 مثالی از سلسله مراتب مفهومی برای کاربری اراضی کشاورزی سلسله مراتب مشابهی میتواند برای دادههای فضایی بهکار برده شود. به عنوان مثال در فاریند تعمیم، نواحی که شهرستانها را مشخص میکنند،میتوانند ترکیب و به استان تبدیل شوند، و استانها در محدودههای بزرگتری ادغام گردند. در فرایند تعمیم، سطح مطلوب تعمیم در زمانی به-دست میآید که تعداد مقادیر مختلف در جدول تعمیمیافته از "مقدار آستانه تعمیم" برای آن خصوصیت بیشتر نباشد.
.4الگوریتم استخراج قوانین وابستگی فضایی با اصلاح تدریجی
یک قانون وابستگی فضایی، که در ادامه بیشتر به آن خواهیم پرداخت، یک قانون است که دلالت مجموعهای از خصوصیات را بر مجموعهای دیگر از خصوصیات در پایگاهداده فضایی را، بیان میکند. به عنوان مثال یک قانون مانند »اکثر شهرای کانادا به مرز کانادا-آمریکا نزدیک هستند«، یک قانون وابستگی فضایی است.همانطور که در بخش قبل ذکر شد، گزارههای فضایی مورد مناسبی برای کاربرد در قوانین وابستگی فضایی دارند. به عنوان مثال معرفت استخراج شده به صورت: 92" درصد از شهرهای درون ایالت BC و نزدیک به آب، به آمریکا نزدیک هستند" به صورت گزارههای زیر نمایش و کشف میگردد:
اما از آنجایی که کاوش قوانین وابستگی فضایی، نیازمند بررسی روابط فضایی متعدد بین مقادیر بسیار بالایی از اشیاء فضایی است، پردازش مورد نظر میتواند بسیار پر هزینه باشد. در اینجا تکنیکی با عنوان "پالایش تدیرجی" معرفی میگردد که با یک رویکرد افزایش دقت، کارایی دادهکاوی فضایی را در حد قابل توجهی بهبود میبخشد:[7]تعریف: یک قانون وابستگی فضایی بهصورت:
است که حداقل یکی از گزارهها، یک گزاره مکانی باشد و درصد اطمینان قانون c باشد. اما از آنجایی که میزان روابط در سطوح مفهومی مختلف، متفاوت است، برای هرکدام از سطوح متناسب با سطح تعمیم آن، مقدار آستانه اطمینان خاصی تخصیص مییابد. به عنوان مثال یافتن رابطه ما بین یک خانه خاص و یک ساحل، احتمالا کار سختی خواهد بود، اما به احتمال زیاد روابط قوی بین خانههای گران قیمت و سواحل خاصی وجود داشته باشد14]و.[7در اینجا برای توضیح کامل این روش دادهها و خصوصیات مورد نظر ذکر میشوند:
