بخشی از مقاله
چکیده
رشد فزایندهی تکنولوژیهای جمعآوری اطالعات و امکان دسترسی به حجم عظیمی از داده نیازمند روشهایی برای تجزیه و تحلیل و استخراج اطالعات مفید از آن میباشد. چگونگی استخراج اطالعات مفید از میان این حجم عظیم داده همواره یکی از سواالت اساسی در علوم کامپیوتر بوده و دادهکاوی یکی از مهمترین روشهای موجود است. که در این بین خوشهبندی داده نیز از پرکاربردترین زمینههای دادهکاوی محسوب میشود. در سالهای اخیر مسئلهی خوشهبندی مسیر اشیاء متحرک به دلیل کاربردهای مختلف شهرت بسیاری پیدا کرده و الگوریتمهای بسیاری در این زمینه پیشنهاد داده شده است.
از آنجا که الگوریتمهای خوشهبندی کالسیک موجود هنگام مواجه شدن با دادههای پیچیده مانند مسیر در بهینهی محلی گرفتار شده و جواب قابل قبولی بدست نمیدهند، همواره استفاده از روشهای نوین یکی از چالشهای موجود در مبحث دادهکاوی بوده است. در این تحقیق یک روش جدید خوشه-بندی مختص دادهی مسیر و با هدف جبران نقاط ضعف الگوریتم خوشهبندی کالسیک پرکاربرد Fuzzy K-Medoids پیشنهاد داده شد. از آنجا که امروزه الگوریتمهای مبتنی بر هوش جمعی در حوزهی داده-کاوی و خوشهبندی مورد توجه زیادی قرار گرفته و نتایج حاصل به خوبی توانایی این روشها را در حل مسئلهی خوشهبندی نشان داده است، در این تحقیق از الگوریتم مبتنی بر هوش جمعی انبوه ذرات به منظور ترکیب با الگوریتم خوشهبندی Fuzzy K-Medoids و با استفاده از تابع فاصله اقلیدسی استفاده شد. روش پیشنهادی بر روی مجموعه داده حرکت خودروهای یک پارکینگ پیادهسازی شد و پس از مقایسه با روش خوشهبندی Fuzzy K-Medoids کارایی آن به اثبات رسید.
واژههای کلیدی: دادهکاوی، خوشه بندی Fuzzy K-Medoids، ،الگوریتم انبوه ذرات، داده های مسیر.
-1 مقدمه
مکان و زمان ثبت شده در حرکت یک شیء متحرک نشاندهندهی یک مسیر است. به عبارتی دیگر دادهی مسیر عبارت است از یک سری زمانی از موقعیتهای متفاوت. مسیرها جزء دادههای مکانی -زمانی میباشند که عالوه بر اطالعات موقعیتی ممکن است شامل ویژگیهایی مانند موقعیت هندسی، جهت، سرعت، مدت زمان، طول عمر و غیره نیز باشند. مطالعه روی این نوع دادهها کاربردهای وسیعی در علوم مختلف داشته است. به عنوان مثال کارشناسان محیط زیست بر روی حرکت حیوانات مطالعه میکنند تا در مورد رشد جمعیت، روابط اجتماعی و الگوهای مهاجرتی آنها اطالعاتی کسب کنند. مهندسین کامپیوتر از اطالعات مسیرها برای فهم چگونگی پخش ویروسهای الکترونیکی استفاده میکنند. مهندسین شهرسازی از اطالعات حرکتی انسانها برای انجام تبلیغات هدفمند، پیشبینی ترافیک و ... استفاده کرده و اینگونه اطالعات زمینهی برنامهریزی شهری را فراهم میآورد .]1[
یکی از تکنیکهای تجزیه و تحلیل بر روی دادهی مسیر تکنیک خوشهبندی میباشد. عمل خوشه بندی مسیر مجموعه دادههای مسیر را با استفاده از یک مدل مناسب به گروههای متشابه تقسیم میکند. این عمل با انتقال مسیرها به یک فضای مناسب و سپس تعریف معیار مناسب به منظور اندازهگیری فاصله بین مسیرها صورت میگیرد. گام بعدی، سازماندهی دادهها در کالسها بر اساس معیار شباهت است .]2[ به عبارت دیگر با توجه به مراکز خوشههای حاصل ازخوشهبندی یک مجموعه داده شامل مسیر، ساختار کلی حرکتی موجود در مجموعه داده کشف میشود و در حقیقت یک مجموعه دادهی حجیم خالصه سازی میگردد.
تکنیکهای خوشهبندی با دو روش برای رسیدن به دو هدف مختلف انجام میشوند. در روش اول که سیستم کشف گروهی نامیده میشود هدف کشف مسیرهایی است که ساختار حرکتی مشابه دارند. به عنوان مثال از اطالعات مربوط به الگوی حرکتی مشتریان در یک فروشگاه، میتوان برای بهینه سازی ترتیب و چگونگی قرارگیری کاالها استفاده کرد. روش دوم مربوط به کشف مسیرهایی میباشد که الگوی حرکتی متفاوتی از دیگران دارند و متعلق به هیچکدام از کالس اشیاء نیستند. در یک سیستم امنیتی افراد مشکوک در ایستگاه یا فرودگاه از این روش پیدا میشوند .]3[تاکنون الگوریتمهای مختلفی برای حل مسئلهی خوشهبندی دادههای مکانی-زمانی ارائه شدهاند. اخیرا خانوادهای از الگوریتمهای الهام گرفته از طبیعت با نام هوش جمعی توجه محققین بسیاری را در زمینهی خوشهبندی و الگوشناسی به خود جلب کردهاند.
بدلیل گستردگی فضای جستجو، ماهیت بهینهسازی و عدم وجود اطالعات قبلی راجع به ساختار داخلی پایگاه داده در مسئلهی خوشهبندی و از طرفی توانایی الگوریتمهای هوش جمعی در غلبه بر مسائل پیچیده و چندهدفه، عدم نیاز به درک و مدلسازی دقیق پدیده، شکل تصادفی جستجو در فضا و مدلسازی پدیده های دینامیک به علت امکان تولد، فعالیت و مرگ ذرات، تکنیکهای خوشهبندی به کمک این روشها عملکرد بهتری را نسبت به روش-های کالسیک پارتیشنبندی مجموعه دادههای پیچیده در دنیای واقعی نشان میدهند .]4[روش خوشهبندی Fuzzy K-Medoids یکی از الگوریتمهای خوشهبندی کالسیک معروف میباشد که یکی از معایب اصلی این روش خطر افتادن در بهینهی محلی میباشد. زمانی که دادههای مورد استفاده از نوع دادهی پیچیدهی مسیر باشند، احتمال افتادن در بهینهی محلی در این الگوریتم افزایش مییابد .]2[ در این تحقیق با استفاده از الگوریتم بهینه سازی انبوه ذرات به عنوان یکی از الگوریتمهای مشهور1 در حوزهی هوش جمعی به جبران نقاط ضعف روش خوشهبندی میپردازیم.
-2 پیشینه پژوهش
رانا و همکاران یک روش ترکیبی بر اساس الگوریتمهای PSO و K-Means پیشنهاد دادند که این روش معایب دو الگوریتم یاد شده را برطرف کرده و احتمال گیر کردن در بهینهی محلی را کاهش میدهد. در این الگوریتم پردازش اولیه بوسیله الگوریتم PSO بدلیل سرعت همگرایی باال آغاز میشود و نتایج بوسیلهی روش K-Means بهبود مییابد .]5[هیما و همکاران یک روش ترکیبی مبتنی بر PSO و الگوریتم ژنتیک برای خوشهبندی اسناد ارائه کردند. در پیادهسازی این الگوریتم از دو روش موازی و انتقالی استفاده شد. در روش موازی به ازای تعداد تکرارهای تعریف شده توسط کاربر، دو الگوریتم به طور همزمان اجرا میشوند و تعداد مشخصی ذره با بهترین مقدار بهینگی انتخاب میشوند. در روش انتقالی یک الگوریتم با تعداد تکرار مشخص - توسط کاربر - اجرا شده و پس از آن الگوریتم دیگر شروع به کار میکند .]6[
هوانگ و همکاران اظهار داشتند که یکی از بزرگترین مشکالت موجود در مسئلهی خوشهبندی مشخص نبودن تعداد خوشهها در ابتدای پروسهی خوشهبندی و تعیین آن توسط کاربر میباشد. بر این اساس آنها روشی را بر پایهی الگوریتم PSO و با استفاده از تئوری فازی پیشنهاد کردند که به صورت اتوماتیک تعداد خوشهها و مراکز آنها را تعیین میکند. نتایج نشاندهندهی دقت این روش در تعیین تعداد خوشهها بود .]7[ ایزکیان و همکاران یک روش خوشهبندی مسیر با ترکیب روش خوشهبندی FCM و الگوریتم انبوه ذرات پیشنهاد دادند. در روش پیشنهادی آنها از روش ضرایب کسینوسی گسسته به منظور کاهش مجهوالت مسئله استفاده شد. در نهایت روش پیشنهادی بر روی چندین مجموعه دادهی واقعی و شبیه-سازی شده پیادهسازی شده و مورد ارزیابی قرار گرفت .]8[
-3 روش پژوهش
الگوریتم بهینهسازي ازدحام ذرات یک خانواده از روشهاي هوش جمعي و یکي از الگوریتمهاي موفق در زمینه بهینه-سازي پیوسته ميباشد. این روش بهینهسازي با الهام از رفتار جمعي پرندگان و بکارگیري مفاهیم الگوریتمهاي تکاملي،معرفي شد. الگوریتم بهینهسازي ازدحام ذرات مشابه با الگوریتمهاي تکاملي یک الگوریتم جمعیتي بوده که در آن تعدادي ذره که راهحلهاي کاندیداي یک مسئله هستند، یک جمعیت را تشکیل ميدهند. این ذرات در فضاي مسئله حرکت کرده و بر اساس تجربیات فردي و جمعي سعي ميکنند تا راهحل بهینه در فضاي جستجو را بیابند .]9[ در این الگوریتم ذرات از حرکات بقیه ذرات ایده گرفته و حرکت خود را بهبود میبخشند، این ذرات میتوانند از ذرات زیر الگو بگیرند: - 1 حرکت فعلی، - 2 بهترین جواب در کل تکرارها برای خود ذره، - 3 بهترین جواب همسایهها و - 4بهترین جواب کلی که در بین همه ذرات وجود دارد.
به عنوان موقعیت ذرهای در فضای جستجو در مرحلهی زمانی در نظر گرفته شود، موقعیت هر ذره به وسیلهی اضافه کردن سرعت به موقعیت کنونی آن، طبق معادله زیر به روز میشود :]10[
در اینجا 1 وزن اولیه، 2 و 3 ثابتهای شتاب و 1 و 2 نیز مقادیری اتفاقی در بازهی صفر و یک هستند. 1 یا وزن اولیه مانند یک حافظه عمل میکند که سرعتهای قبلی ذره را نگهداری و تاثیر سرعتهای قبلی بر ذره را کنترل میکند. یا سرعت اولیه به عنوان اطالعاتی از جهت و اندازهی پرواز اولیه میباشد. این ترم از تغییر ناگهانی جهت ذره جلوگیری میکند و منجر میشود که بایاس شدیدی نسبت به موقعیت فعلی ذره نداشته باشد. 2 1 - − - یا جزء شخصی بیانگر تفاوت بین موقعیت کنونی و بهترین اجراهای قبلی ذره میباشد. این ترم باعث میشود که ذرات به سمت بهترین موقعیت خود کشیده شوند. 3 2 - − - یا جزء اجتماعی بیانگر موقعیت ذره نسبت به همسایگانش میباشد. جزء اجتماعی باعث میشود که هر ذره به سمت بهترین موقعیت پیدا شده توسط همسایگان خود کشیده میشود.
در صورتی که خوشهبندی را به عنوان یک مسئلهی بهینهسازی در نظر بگیریم، امکان استفاده از الگوریتمهای بهینه-سازی همچون PSO برای استخراج مراکز خوشهها و سپس نسبت دادن دادههای موجود در مجموعه داده به نزدیکترین مرکز خوشهی کشف شده وجود دارد. یکی از ویژگیهای مهم PSO مقابله با بهینهی محلی به وسیلهی نگهداری، ترکیب و مقایسهی همزمان چندین راه حل کاندید به طور همزمان میباشد. روشهای جستجوی محلی قطعی مانند K-Means نیز همواره به نزدیکترین بهینهی محلی که از آغاز جستجو پیدا شد، همگرا میشوند. الگوریتم خوشهبندی مبتنی بر روش PSO اولین بار توسط وندرمرو و انگلبرت معرفی شد .]11[ آنها برای بررسی عملکرد روش خود از quantization error مطابق رابطه - 1 - استفاده کردند.
Ci مرکز iامین خوشه و ni عبارت است از تعداد دادههای نقطهای متعلق به خوشهی iام. هر ذره در الگوریتم PSO نشان-دهندهی یک مجموعهی ممکن از k مرکز خوشه است و در شکل 1 نمایش داده میشود.Vi,p نمایشگر p امین مرکز کالستر در i امین ذره میباشد. کیفیت هر ذره با استفاده از تابع بهینگی زیر سنجیده میشود.در رابطهی Rmax - 2 - عبارت است از بیشترین مقدار موجود در مجموعه داده و Mi ماتریسی است که تخصیص ساختارهای موجود در مجموعه داده را در ذرهی iام نشان میدهد. هر المان mi,k,p درجهی تعلق ساختار Xp به خوشهی Ck در ذرهی iام را نشان میدهد. ضرایب w1، w2 و w3 توسط کاربر تعیین میشوند و وزن مربوط به زیر هدفها را مشخص میکنند.
