بخشی از مقاله
چکیده
امروزه روشهای آماری اعمال نفوذ سنتی برای تحلیل حجم بزرگی از دادههای فضایی، بار محاسباتی بالایی دارد. برای حل این مسئله، اخیراً تکنیکهای داده کاوی نسبتاٌ پیشرفتهای در روش های تحلیل فضایی متفاوت با هدف استخراج دانش از حجم بالای دادههای فضایی استفاده شده است.
در این تحقیق، علاوه بر معرفی اجمالی و ذکر روشهای رایج در داده کاوی فضایی به موضوع خوشهبندی هیبریدی که از ترکیب دو الگوریتم خوشهبندی k-means و AGNES به وجود آمده است، می پردازیم. روش ترکیبی شرح داده شده پیچیدگی محاسباتی کمتری نسبت به الگوریتمهای والد خود دارد.
-1 مقدمه
به موازات پیشرفتهای صورت گرفته در زمینه ساختمان دادهها و پایگاه دادههای فضایی و نیز تکنیکهای جمع آوری دادهها، حجم بسیار وسیعی از دادهها توسط سامانه سنجش از راه دور، سامانههای تجارت الکترونیک و سایر ابزارهای جمع آوری داده، گردآوری می شوند که با توجه به پیچیدگی انواع داده های فضایی و حجم بسیار بالا و روش های دسترسی به آن ها، توسعه ی ابزارهای کشف دانش از این پایگاه دادههای بزرگ، امری ضروری تلقی میشود. به دلیل مناسب نبودن روش-های قدیمی در تحلیل دادهها ی فضایی که مبتنی بر رویکردهای آماری بودند نیاز به الگوریتمهایی داریم که مختص به داده کاوی فضایی باشد و در آنها روابط مکانی و روش های دسترسی فضایی، خصوصیات فضایی دادهها و تحلیل و اجرای پرس و جوهای فضایی مدنظر قرار گیرد. دانش به دست آمده از دادههای فضایی در حوزههای مختلفی مانند: علوم فضایی، سنجش از راه دور، ترافیک، هواشناسی، جرم شناسی و غیره کاربرد دارد.
پیشرفتهای تحقیقاتی در زمینهی ساختمانهای داده فضایی و پایگاه داده فضایی، اجرای کارآمد پرس و جوها بر روی پایگاه-های داده فضایی را امکان پذیر نموده است. این پیشرفتها به همراه پیشرفتهای داده کاوی و انبار دادهها در پایگاههای داده رابطهای، ما را به تحقیق در زمینه داده کاوی فضایی ترغیب مینمایند. تا قبل از دهه 90، بسیاری از روشهای تحلیل دادههای فضایی از رویکردهای آماری بهره گرفتهاند، اما روشهای آماری برای تحلیل حجمهای بالای دادههای مکانی مناسب نمی-باشند.[1]داده کاوی فضایی فرآیند کشف الگوهای جالب و ناشناخته، اما مفید از مجموعه دادههای فضایی بزرگ است.
ویژگیهای مخصوص دادههای جغرافیایی، مانع استفاده از هدف کلی الگوریتمهای داده کاوی است که عبارتند از: -1 روابط فضایی بین متغیرها -2 ساختار فضایی خطاها -3 وجود توزیع ترکیبی به جای توزیع نرمال -4 مشاهدات مستقل و توزیع نشده -5 هم مکانی فضایی بین ویژگی ها و -6 فعل و انفعالات غیر خطی در فضای ویژگی.
-2 دادههای فضایی
به دادههایی مربوط به اشکال و موقعیتهای مکانی و ارتباط آنها با یکدیگر که از طریق سامانه های GIS، CAD، روباتیک و برنامههای بینایی ماشین، محاسبات موبایل و زیست شناسی به دست میآیند دادههای فضایی میگویند. دادهها در داده کاوی فضایی بسیار پیچیدهتر از دادها در داده کاوی کلاسیک هستند زیرا شامل نقطهها،خطها و چندضلعیها میباشند.
دو نوع متفاوت از ویژگیهای دادهها در داده کاوی فضایی :ویژگیهای غیر فضایی و ویژگیهای فضایی. ویژگیهای غیر فضایی از قبیل نام، جمعیت و نرخ بیکاری افراد برای یک شهر و ویژگیهای فضایی از قبیل طول و عرض و ارتفاع جغرافیایی.
-3 روشهای کاوش داده های فضایی
برای کاوش دادههای فضایی چهار روش مهم اعمال میشود که عبارتند از:
-1-3 کشف انحراف فضایی
دادههای پرت در واقع دادههای مشاهده شده در یک مجموعه دادهای هستند که به نظر میرسد در تضاد با باقی ماندهی دادهها در آن مجموعه دادهای میباشند. به دادههای پرت فضایی، انحراف فضایی گفته میشود که در واقع یک شی فضایی مورد ارجاع میباشد، به طوری که ویژگیهای غیر فضایی آن تفاوت عمدهای با اشیاء فضایی همسایه آن دارند. به طور مثال ویژگی غیرفضایی "قدمت خانه" برای خانه جدید ساخته شده در منطقهای قدیمی در همسایگی ناحیه مرکزی شهر یک انحراف فضایی است.
روشهای تشخیص انحراف سراسری، از موقعیت فضایی هر نقطه دادهای را در نظر نمیگیرد و مدل توزیع را با مقدار ویژگی غیر فضایی، متناسب میکند. همچنین برای بهبود کیفیت تشخیص انحراف فضایی که به جداسازی ویژگیهای فضایی از ویژگیهای غیر فضایی میپردازد، به نمونههایی از قبیل Variogram-Cloud Scatterplot و Moran Scatterplot میتوان اشاره کرد
-2-3 قواعد هممکانی فضایی
در واقع قواعد هممکانی فضایی، وجود یا عدم وجود ویژگیهای فضایی بولی انواع اشیای جغرافیایی را در موقعیتهای مکانی مختلف در فضاهای دوبعدی و سه بعدی مانند سطح زمین بررسی میکنند.برای نمونه می توان به انواع جادهها یا انواع مختلف تجارتها اشاره کرد.
الگوهای هممکانی زیر مجموعهای از ویژگیهای فضایی بولی را ارائه میکند که نمونههای آن بیشتر در موقعیتهای جغرافیایی مجاور واقع شدهاند مانند جادهها و بزرگراهها در نقشه جادههای شهری. قواعد هممکانی، مدلهایی به منظور تشخیص وجود ویژگیهای فضایی بولی در همسایگی نمونههای دیگر ویژگیهای فضایی بولی، میباشند. به عنوان مثال، قاعده " پرندگان مهاجر ماهیان سفیدرود" حضور پرندگان مهاجر در ناحیهای که ماهیان سفیدرودی واقع شدهاند را پیش بینی میکند.
به طور کلی کشف قواعد هممکانی، فرآیند تشخیص الگوهای هممکانی از مجموعههای دادهای فضایی بزرگ با تعداد زیادی ویژگیهای بولی است. این فرآند شباهت زیادی به قواعد انجمنی در داده کاوی سنتی دارد. البته تفاوتهای زیادی از قبیل نوع رویکرد و دادههای مورد بحث به علت عدم وجود تراکنش در قواعد هممکانی نیز وجود دارد. سه رویکرد اصلی در این راستا، همراه با ویژگیها و جزئیات آنها در جدول 1 ارائه شده است
جدول .1 معیارهای تحقق در سه روش اصلی کشف قواعد هم مکانی
-3-3 مدلهای پیشگویانه
پیشبینی حوادث با موقعیت جغرافیایی از اهمیت بسیار زیادی برخوردار است. نمونههایی از قبیل تحلیل جرایم، شبکههای سلولی و حوادث طبیعی مانند سیل و خشکسالی و زمین لرزهها نیاز به پیش بینیهای مکانی دارند. دو روش اساسی برای انجام این گونه پیش بینی در زمینه داده کاوی فضایی عبارتند از:مدل خود بازگشت فضایی - SAR - که یک طبقه بندی را به دو بخش به نام های خودبازگشتی فضایی و انتقال منطقی تقسیم میکند و فیلدهای تصادفی مارکوف - MRF - که یک مدل احتمالی بر روی گرافهای بدون جهت است.
جدول .2 روشهای رایج در طبقه بندی فضایی و مدلهای پیشگویانه
