بخشی از مقاله
چکیده :
اولین عنصر راه آهن که مسافر در ابتداي شروع سفر خود با آن مواجه می شود، ایستگاه است واگر این ایستگاه به خوبی طراحی شده باشد وداراي پارامترهاي از پیش تعریف شده باشد ، باعث جذب مسافرین وافزایش رونق حمل ونقل ریلی وبه تبع آن بهره گیري از مزایایی چون مصرف انرژي کمتر، حمل ونقل انبوه ،ایمنی بالاتر وحفظ محیط زیست خواهد شد بنابراین یکی از مسائل مهم در شرکت قطارهاي مسافري رجاء، موضوع طبقه بندي ایستگاههاي مسافري به منظور تعیین امکانات رفاهی مورد نیاز هر یک از ایستگاههاي مسافري می باشد .
هدف این تحقیق بررسی ایستگاه هاي مسافري راه آهن جمهوري اسلامی ایران و دسته بندي انها بر اساس اهمیت ایستگاه ها می باشد . در دسته بندي ایستگاه ها بر اساس اهمیت ایستگاه ، شاخص هایی چون میانگین تعداد مسافر روزانه ، مرکز استان بودن ، ایستگاه مبدا و مقصد بودن در نظر گرفته شده است .این خوشه بندي با استفاده از الگوریتم مورچه ها انجام شده و نتایج ان با نتایج حاصل از الگوریتم k-means مقایسه گردیده است .
کلمات کلیدي :
خوشه بندي ،ایستگاه هاي مسافري،شرکت رجا، الگوریتم مورچه ها، الگوریتم k-means
مقدمه :
در دو دهه قبل توانایی بشر براي تولید و جمع آوري داده ها به سرعت افزایش یافته است لذا داده ها و اطلاعات اولیه از اهمیت زیادي برخوردار نیستند ، لیکن فراوري و بازپروري داده ها و تولید دانش و استخراج گزاره هاي آن داراي اهمیت می باشد . "داده کاوي فرایند کشف روابط ناشناخته و الگوها در داده است . " [1]
تکنیک هاي داد کاوي را می توان در کل به دو دسته تقسیم بندي کرد: طبقه بندي و خوشه بندي[2]
k-means به عنوان یکی از معروفترین الگوریتم هاي خوشه بندي اغلب مبناي اعتبارسنجی الگوریتم هاي ارائه شده براي خوشه بندي داده ها مورد استفاده قرار می گیرد.
روش خوشه بندي مورچه اي که الهام گرفته از رفتار مورچه ها در طبیعت می باشد ، اولین بار در ژظب براي مجموعه اي ار ربات ها که اشیاء را دسته بندي می کردند ارائه شد و این الگوریتم در ژلب براي خوشه بندي و تصحیح داده ها ارائه گشت . در روش خوشه بندي مورچه اي از تعدادي مورچه با عملکرد ساده و بدون کنترل مرکزي استفاده می شود.
در این مقاله ایستگاه هاي مسافري راه آهن جمهوري اسلامی ایران با استفاده از دو روش k-means و کلونی مورچه ها ، خوشه بندي شده و نتایج حاصل از آنها مورد مقایسه قرار گرفته است.
الگوریتم : K-means
این الگوریتم پارامتر k را به عنوان ورودي می گیرد و مجموعه n شیء را به k خوشه افزار می کند بطوریکه سطح شباهت داخلی خوشه ها بالا برده و سطح شباهت اشیاء بین خوشه ها پایین باشد. شباهت هر خوشه نسبت به متوسط اشیاء آن خوشه سنجیده می گردد که این متوسط ، مرکز خوشه نیز نامیده می شود. ورودي الگوریتم تعداد خوشه ها ( k) و یک پایگاه داده شامل n شیء و خروجی آن یک مجموعه از k خوشه است که معیار مربع خطی را مینیمم می کند.
مراحل الگوریتم به صورت زیر است:
(a به صورت دلخواه (تصادفی) k شیء را به عنوان مراکز خوشه هاي ابتدایی انتخاب کند.
(b تکرار کن
(c هر شیء را با توجه به بیشترین شباهت آن به مراکز خوشه ها، به خوشه ها تخصیص بده.
(dمراکز خوشه ها را بروز کن به این معنی که براي هر خوشه مقدار متوسط اشیاء آن خوشه را محاسبه کن. (eتا هنگامی تلرلنس تغییرات مرکز خوشه نزدیک به صفر شود ، برو به .b
معیار مربع خطا که در فوق ذکر شد، عبارتست از :
کهE مجموع مربع خطا براي تمام اشیاء پایگاه داده می باشد. p نقطه اي در فضاست که نمایانگر یک شیء می باشد و mi مقدار متوسط خوشه Ci می باشد (هم p و هم mi چند بعدي هستند) .[2]
روش کلونی مورچه ها :
انسان همیشه براي الهام گرفتن به جهان زنده پیرامون خود نگریسته است. روش خوشه بندي مورچه اي نیز روشی الهام گرفته از طبیعت می باشد که از مطالعات و مشاهدات روي کلونی مورچه ها حاصل شده است.
یکی از مهمترین و جالبترین رفتار مورچه ها، رفتار آنها براي یافتن غذا است. مورچه ها هنگام راه رفتن از خود ردي از ماده شیمیایی فرومون((Pheromone بجاي می گذارند البته این ماده بزودي تبخیر می شد ولی در کوتاه مدت بعنوان رد مورچه بر سطح زمین باقی می ماند.
یک رفتار پایه اي ساده در مورچه ها وجود دارد. آنها هنگام انتخاب بین دو مسیر ، مسیري را انتخاب می کنند که فرومون بیشتري داشته باشد یا بعبارت دیگر مورچه هاي بیشتري قبلا از آن عبور کرده باشند [6]ل این نوع رفتار مورچه ها داراي نوعی هوشمندي توده اي است که اخیرا مورد توجه دانشمندان قرار گرفته است.
در هوشمندي اجتماعی عناصر میزانی از هوشمندي را دارا هستند در حالیکه در هوشمندي توده اي عناصر رفتاري تصادفی دارند و بین آن ها هیچ نوع ارتباط مستقیمی وجود ندارد و آنها تنها بصورت غیر مستقیم و با استفاده از نشانه ها با یکدیگر در تماس هستند. الگوریتمی که در ادامه به آن اشاره خواهد شد یکی از الگوریتم هایی است که در [5] براي خوشه بندي مورچه اي مورد استفاده قرار گرفته است .
الگوریتم کلونی مورچه ها:
می خواهیم N شیء به K خوشه تخصیص دهیم در حالیکه اشیاء داراي n خصیصه می باشد. براي ایجاد هر solution جدید یک گروه R تایی از مورچه هاي مصنوعی را به سوي خوشه ها روانه می کنیم .
در ابتداي الگوریتم ، ماتریس فرومون (δ) با مقادیر اولیه بسیار کوچک عدد دهی می شود.در این ماتریس یعنی غلظت فرومون شیء ام که به خوشه اختصاص داده شده است پس ماتریس فرومون یک ماتریس N*K است.براي ایجاد هر solution جدید مورچه هاي مصنوعی به صورت زیر به خوشه ها تخصیص داده می شوند.
(1 عدد q را در حالیکه 0<q<1 است تعریف می کنیم(در خوشه بندي ایستگا هها q=0.80 در نظر گرفته شده است) ف (2 به تعداد اشیاء اعداد تصادفی با توزیع یکنواخت در بازه (0,1) تولید می شود.
3) اگر عدد تصادفی تولید شده براي هر شیء کمتر از باشد ، شیء را به خوشه اي اختصاص می دهیم که داراي بشترین فرومون است
4) اگر عدد تصادفی شئ اي بیشتر از q بود . ماتریس Pij که یک ماتریس N*K است تشکیل می گردد.
مجددا براي شیء مذکور عدد تصادفی با توزیع یکنواخت در بازه (0,1) تولید می گردد . این شئ به خوشه اي تعلق خواهد گرفت که عدد تصادفی تولید شده در محدوده تجمعی عدد حاصل در ماتریس Pij قرار داشته باشد.[7]
پس از ایجاد R تا solution جدید ، یک جستجوي محلی براي بهبود solution هاي ایجاد شده صورت می گیرد. در ابتداي جستجوي محلی ، براي هر solution ایجاد شده میزان ارزش خوشه بندي با صورت زیر محاسبه می شود :
v امین خصیصه ء i امین شئ و m jvمیانگینی از ارزش v امین خصیصهء تمام اشیاء در خوشه j ام می باشد که به صورت زیر محاسبه می گردد:
Solutionهاي ایجاد شده بر اساس میزان ارزش خوشه بندي به صورت صعودي sortمی شوند سپس جستجوي محلـی بـر روي L درصـد از بهترین جواب ها که معمولا L=20% صورت می گیرد وSolutionهاي ایجاد شده تعدیل می گردند بـه ایـن صـورت کـه Pls در بـازه((0,1 بـه صورت پیش فرض تعریف می شود در اینجا Pls=0.4 در نظر گرفته شده است .
به تعداد اشیاء عدد تصادفی یکنواخت در بازه (0,1) تولید می شود . اگر عدد تصادفی تولید شده براي شی اي کمتر از Pls باشد ، شئ مـذکور بـه صورت تصادفی به خوشه دیگري غیر از خوشه اي که در آن قرار گرفته اختصاص داده می شود. براي solution هـاي جدیـد مجـددا ارزش خوشـه بندي محاسبه می شود و در صورتی که solution جدید نسبت به قبلی بهبود یافته باشد جایگزین آن خواهد شد.[8]
پس از انجام جستجوي محلی ماتریس فرومون بر اساس نتایج حاصل از بهترین solution ایجاد شده به روز می شود و به این ترتیب یک تکرار از الگوریتم پایان می یابد و بر اساس ماتریس فرومون تعدیل شده این مراحل تا رسیدن به شرط پایان الگوریتم ادامه می یابد. ماترسی فرومـون بـه صورت زیر تعدیل می گردد:
ρ که عددي در بازه (0,1) است ، نشان دهنده سرعت تبخیر فرمون است و (1-ρ) میزان دوام و پایداري فرمون خواهد بود.
شاخص هاي مورد استفاده :
در گزارش حاضر، کلیه ایستگاه هاي مسافري موجود در راه آهن سرتاسر کشور جمهوري اسلامی ایران ، که مشتمل بر یکصد و یازده مورد 111)ایستگاه) می باشند، مورد طبقه بندي قرار گرفته اند. ایستگا هاي تهران و مشهد با توجه به اینکه معیارهاي بکار رفته در این خوشه بندي شامل سه خصیصه می باشند .
معیارهاي مورد نظر عبارتند از:
موقعیت ایستگاه ؛ یعنی آیا ایستگاه مورد نظر، داراي موقعیت محلی می باشد یا داراي موقعیت مرکز استانی یا ناحیه اي می باشد.
تعدادا مسافرین ایستگاه ها ؛ یعنی تعداد مسافرین ایستگاه مورد نظر در شبانه روز (مجموع تعداد مسافرین سوار شونده و مسافرین پیاده شونده)،
چقدر می باشند .
ایستگاه مبداومقصد:یعنی ایا ایستگاه مورد نظر ،به عنوان مبدااولیه ویا مقصد نهایی قطار ها محسوب می شود.
همانطوریکه ملاحظه می شود بر اساس جدول فوق، معیارهاي مرکزي ، یعنی میانگین و میانه اختلافهاي قابل ملاحظه اي با یکدیگر دارند که نشانگر یک توزیع چوله براي شاخص تعداد مسافرین ایستگاه هاي راه آهن در شبانه روز می باشد. همچنین معیار آماري انحراف معیار نشانگر وضعیت پراکندگی شاخص مذکور، حول میانگین توزیع مقادیر می باشد. حداکثر تعداد مسافرین در شبانه روز، 35000 نفر مربوط به ایستگاه مسافربري تهران است که این مقدار با توجه به اختلاف فاحشی که با سایر مقادیر دارد، بعنوان یکی از مقادیرپرت محسوب می شود؛ چراکه تعدادي از معیارهاي آماري شدیداً تحت تأثیر آن قرار گرفته اند .
علاوه بر ایستگاه مسافربري تهران، ایستگاه مشهد با 10000 نفر مسافر در شبانه روز، نیز باتوجه به علل ذکر شده در بالا، بعنوان دومین مقدار پرت در نظر گرفته شده است. همچنین چارك اول نشانگر آنست که 25 درصد از ایستگاهها داراي تعداد مسافرین کمتر از 40 نفر در شبانه روز می باشند و چارك دوم (یا میانه) نشان دهندة تعداد مسافرین کمتر از 120 نفر در شبانه روز براي نیمی از ایستگاه هاي مسافري می باشد و در انتها، چارك سوم نیز نشانگر آنست که 75 درصد از ایستگاههاي مسافري کمتر از 600 نفر مسافر در شبانه روز می باشند. بنابراین ایستگاه هاي تهران و مشهد در گروه ویزه قرار داده شده و سایر ایستگاه ها در سه گروه خوش بندي شده اند .
