بخشی از مقاله
چکیده
با توجه به اینکه نیاز به یافتن همسایگی و ارتباط بین نقاط برای حوزههای خوشهبندی و دستهبندی دادهها غیرقابلانکار است، بنابراین رویکردی نوین برای یافتن همسایگی بین نقاط - دادهها - ، مسئلهای چالشبرانگیز است. یافتن همسایگی دادهها در دادههای عظیم و دادهکاوی بهصورت کلی باید منجر به دستهبندی دقیق داده بر روی انواع پایگاه دادهها گردد. برای این منظور، نوعی همسایگی کاربردی باید در تحلیل و گروهبندی دادههای مشابه مشخص گردد. اساس بیشتر الگوریتمهای ارائهشده در این زمینه بر الگوریتمهای یافتن همسایگی نقاط - دادهها - ، روشهای تحلیل فاصله و مدلهای آماری استوار است.
مدلهایی که تاکنون ارائهشدهاند قابلیت تحلیل همزمان و بررسی دقیق مکانهای هندسی دادهها و ارتباطات هندسی بین آنها را ندارند و همچنین بیشتر مدلهای مطرحشده به تنظیم پارامترهایی همچون تعداد همسایگی و ناحیهی همسایگی وابسته هستند. نیازمندی به تحلیل ارتباطات دادهها و تأثیر آنها در دقت یافتن همسایگی نقاط با محاسبات قابل قبول غیرقابل انکار است.
تمرکز روش پیشنهادی بر روی ارائهی مدل هندسی کاربردی و بررسی اتصالات برای اولین بار با الگوی دایرهی آپولونیوسی در تحلیل هندسی الگوهای همسایگی است. هدف یافتن همسایگی دقیق بر اساس دایرهی آپولونیوسی و ارائهی روشی نوین برای یافتن ارتباطات بین دادهها است که میتوانند وضعیت همسایگی نقاط دادهها در حوزههای مورد ذکر را مشخص کنند. در مرحلهی نخست دادهها در یک صفحهی اقلیدسی ذخیره میشوند، سپس با اعمال روش یافتن همسایگی نقاط بر اساس دایرهی آپولونیوسی الگوهای همسایگی و ارتباطات بین آنها استخراج میگردد.
مقدمه
از ویژگیهای برجستهی دادهکاوی، تجزیهوتحلیل دادهها و گروهبندی آنها در دستههای مشابه با بررسی خاصیت همسایگی بین دادهها به شکلی دقیق است. خاصیت همسایگی معیاری برای ساخت مدلهای دقیق همسایگی نقاط داده با تغییرات گرایش داده به دستههای مشابه است. منظور از شباهت، وابستگی ذاتی درون دادهها و تأمین ارتباط دستههای مشابه بهصورت خودکار است. بهعبارتدیگر تعریف همسایگی برای دادهها از حیث شباهت و ارتباط صورت میپذیرد، بهطوریکه دقت حاصلشده به تقاضای فعلی دادهکاوی در حوزههای گوناگون پاسخگو باشد. میتوان گفت که هدف در جهت کشف اطلاعات پنهان و روابط موجود در بین دادههای فعلی و پیشبینی موارد نامعلوم و یا مشاهده نشده است.
الگوریتم1k-NN یکی از پرکاربردترین الگوریتمها در تعریف همسایگی و دستهبندی هست که بر اساس فاصلهی اقلیدسی تصمیم به انتخاب دادههای مشابه میگیرد - به تعداد k نزدیکترین همسایهی نقاط رأیگیری صورت میگیرد و همه-ی نقاط نفوذ و تأثیر یکسانی در رأیگیری دارند - و سپس تعیین کلاس انجام خواهد شد. اگرچه این الگوریتم روش ساده و مؤثری هست ولی تعیین همسایگی توسط این الگوریتم تنها بر اساس فاصله صورت میپذیرد و از محل قرارگیری هندسی نقاط و هرگونه قاعدهی آماری چشمپوشی میگردد و پارامتر k نقش بسزایی در تعریف همسایگی و کلاسبندی خواهد داشت.
روشهای متعدد دیگری برای بهبود دقت دستهبندی بر اساس گراف و همسایگی ارائهشده است. گرافهایی از قبیل گراف گابریل [48,47]، - اسکلت و گراف نزدیکترین همسایگی2RNG در تعریفی از همسایگی مورداستفاده قرار میگیرند که روشهای گراف گابریل و گراف نزدیکترین همسایگیRNG نیازی به تنظیم پارامتر ندارند. ولی ایراد این دو روش ناحیهی همسایگی ثابت هست که باعث عدم بهینه-سازی کارایی یافتن همسایگی نقاط داده میشود اما در روش- اسکلت برای تعیین ناحیهی همسایگی مقدار پارامتر باید مشخص گردد.[3 ,2] در هندسه محاسباتی و نظریه گراف هندسی، بتا اسکلت یک گراف بدون جهت است که بر روی مجموعهای از نقاط هندسهی اقلیدسی تعریف میشود. دو نقطه B و A در صورتی توسط یک یال به یکدیگر متصل میشوند که همه زاویههای ABC از آستانه تعیینشده توسط پارامتر عددی کمتر باشد.
روش دیگری بنام3ANG طبقهبندی را بر اساس زاویهی بین دادهها انجام میدهد این روش بر اساس روابط هندسی و با تعریف پارامتر زاویه ارتباط مستقیم و غیرمستقیم را انجام میدهد و زاویههای مختلفی را بررسی مینماید از معایب این روش تنظیم پارامتر زاویه و محاسبات سنگین هست و از مزایای آن سایز همسایگی است که قابل تنظیم هست که برای تعیین بهترین دقت طبقهبندی کارآمد هست.
الگوریتم ماشین بردار پشتیبانی 4SVM نیز یک روش طبقهبندی از نوع با ناظر است. این روش ازجمله روشهای نسبتاً جدیدی است که در سالهای اخیر کارایی خوبی نسبت به روشهای قدیمیتر برای طبقهبندی ازجمله، شبکههای عصبی پرسپترون نشان داده است. دراین الگوریتم آموزش نسبتاً ساده است برخلاف شبکههای عصبی در ماکزیممهای محلی گیر نمیافتد. برای دادههاییبا ابعاد بالا تقریباً خوب جواب میدهد. مصالحه بین پیچیدگی دستهبندی کننده و میزان خطا بهطور واضح کنترل میشود. به یک تابع کرنل خوب و انتخاب پارامتر C نیاز دارد.
روش ساده ی همسایگی اپسیلون، همسایگی را بر اساس یک شعاع کوچک و بر اساس پارامتر اپسیلون تعیین مینماید و در این ناحیه از همسایگی دادهها کلاسبندی میشوند که با انتخاب نامناسب پارامتر اپسیلون کارایی رویکرد کاهش پیدا خواهد کرد .
الگوریتم 5 که یک روش طبقهبندی گراف هست و در مرحلهی اول از فاصلهی بین نودها و تشکیل گراف کامل استفاده میکند و در مرحلهی دوم درخت پوشای دادهها را به دست میآورد، نودهای پرتراکم را مشخص مینماید و برای هر نود - بر اساس هزینهی فاصلهی بین دو نود، هزینهی صفر برای خود نودهای پرتراکم مشخصشده و هزینه بینهایت برای نودهای عادی - هزینهای را محاسبه میکند که در مرحلهی آموزش بر اساس کمینه و بیشینه کردن این هزینهها طبقه-بندی صورت میگیرد و در مرحلهی تست نیز بر اساس کمینه و بیشینه بین هزینههای گروه برنده، گره تست مشخص می-گردد.
الگوریتم 6KAOG با تعداد همسایگی از یک شروع میکند و در هر گام تعداد k را افزایش میدهد و برای هر گروه تشکیلشده از نودها میزان خلوص را محاسبه میکند که بر اساس درجهی ورودی و خروجی نودها و تعداد آنها در گروه صورت میگیرد و در هر گام افزایش k، ممکن است گروهها باهم ترکیب شوند - دوباره خلوص محاسبه شود - و در صورت افزایش یک ترکیب مناسب حاصل میشود در غیر این صورت دو گروه ترکیب نخواهند شد .
روش نمودار - دیاگرام - bicentric از متد مصورسازی برای نشان دادن ارتباطات مستقیم و غیرمستقیم نودها استفاده میکند و نودها را بر روی دوایر دارای نود مرکزی توزیع می-نماید و لایههای مختلف ارتباطی را برای تعیین گام همسایگی تعریف میکند. مراکز دوایر حاوی دو نود اصلی قابلبررسی در پایگاه داده میباشند که ارتباط سایر نودهای مصور شده بر اساس این مراکز میباشد داخلیترین لایهها، ارتباطات نزدیک و بیرونیترین لایهها ارتباطات دور را نشان میدهند. بدین شکل نودهای مستقیم و غیرمستقیم استخراج میشوند.
الگوریتم کشف کلاسترینگ بر اساس ویژگی گرافها و ارائهی یک معیار ارزیابی کیفیتی از مجموعه کلاسترها 7RM-CRAG بیانشده است که علاوه بر بهکارگیری توپولوژی خود گراف در خوشهبندی از ویژگیهای خود نودها - خصیصهی مشترک بین افراد - نیز برای خوشه-بندی استفادهشده است و یکسری یالهای مصنوعی بر اساس شباهت ویژگی ذاتی نودها به یالهای اصلی اضافه میگردد و ارزیابی شباهت بین یک مجموعه از زیر کلاسترها بر اساس آنتروپی از کلاسترینگ صورت میپذیرد. اگر ارتباط بین دو زیر کلاستر ارتباط قوی باشد باهم ترکیب و تشکیل یک کلاستر بزرگتر را خواهند داد، در غیر این صورت در ترکیب قبلی باقی خواهند ماند.
الگوریتم CP-Cluster برای پایگاه دادههای بسیار بزرگ با ابعاد بالا از پردازش موازی در مراحل کلاسترینگ استفاده میکند و با تعریف پارامترهای آستانه گیری، دادهها را بر اساس فاصلهشان از نقاط آستانه به دو زیرمجموعهی کلی تقسیم مینماید و با تعریف ساختار درختی و توابع Map Reduce اقدام به ساخت زیرگروهها بهصورت موازی در دو زیرمجموعهی ساختهشده مینماید
از روشهای متاهیورستیک برای کلاسترینگ شبکه-های اجتماعی در مقیاس بزرگ استفاده مینمایند. بر اساس اینکه شبکههای اجتماعی بر اساس رفتار اجتماعی و ارتباطات اجتماعی ساختهشدهاند در گراف شبکههای اجتماعی از کلاسترینگ سلسله مراتبی، کلاسترینگ طیفی و رویکردهای پارتیشنال استفاده میشود بنابراین از الگوریتمهای همانندPSO, ACO برای استخراج ساختارهای انجمنی استفاده شده است. از موقعیت و سرعت ذرات برای تجزیهی توپولوژی شبکه و ساخت زیر گرافها استفادهشده است و با معیار ماجولاریتی کیفیت زیر گرافها سنجیده می-شوند
در این مقالات با توجه به تکرار نسلهای جمعیت، انعطافپذیری مدل کمتر بوده و نمیتوان الگوهای دقیق همسایگی را استخراج نمود. همچنین مدلهای متاهیورستیک جوابهای گوناگونی را در هر بار اجرا بهعنوان خروجی مشخص مینمایند و هزینهی محاسباتی را نیز اگر داشته باشند زمان را نیز در سیستمهای طبقهبندی افزایش میدهند. نیاز به تنظیم پارامترهای مختلف نیز از ایرادات این روشها میباشد. از یافتن همسایگی نقاط داده در زمینههای مختلفی چون تحلیل و آنالیز داده در دادهکاوی [22]، تشخیص انجمنها در شبکههای اجتماعی [23-25] و بسته-بندی یالها در مصورسازی دادهها[27 ,26] استفادهشده است. همچنین مقالههای28] ،[6 از ترکیب الگوریتمهای تکاملی و خوشه بندی استفاده کرده اند.
