14707

14707

ارائه روشي جديد در حل مسئله تركيب خوشه‌بندي با استفاده از روش‌هاي دقيق رياضياتي

كارشناسي ارشد

هوش مصنوعي و رباتيك

بهمن ماه 1392

بهمن ماه 1392

دكتر بهروز مينايي

كامپيوتر

چكيده مسئله‌ي خوشه‌بندييك مجموعه داده‌اي، داراي فضاي پيچيدگي زماني نمايي است و براي رفع اين مشكل در مطالعاتي كه تاكنون انجام شده است، ساده‌سازي‌هاي گوناگوني ارائه شده است. در اين مطالعه روشي براي حل مسئله تركيب خوشه‌بندي در چند گام ارائه مي‌كنيم كه در آن از مفهوم بهينه‌سازي رياضياتي بهره گرفته شده است.در روش پيشنهادي ضمن حفظ بهينگي خوشه‌ها افزايش چشمگيري در سرعت خوشه‌بندي ايجاد شده است.در روش پيشنهادي سه گام پيشنهاد شده است. در گام اول مفهوم جديدي به نام كلوخ (خوشه كوچك و بسيار پايدار)معرفي مي‌شود كه قبل از خوشه‌بندي بر روي مجموعه داده‌اي اعمال مي‌شود و اندازه آن را كوچك مي‌كند. بنابراين چون در مرحله‌ي خوشه‌بندي با مجموعه داده‌اي چند برابر كوچك‌تر مواجه هستيم پس سرعت خوشه‌بندي نيز تا چند برابر سريع‌تر مي‌شود. كلوخ‌ها در واقع تعداد زيادي خوشه‌هاي كوچك و بسيار پايداري هستند كه با استفاده از الگوريتم نگاشت يك بعدي كوهنن از مجموعه داده‌اي اوليه استخراج مي‌شوند.به كلوخ‌هاي ايجاد شده در اين گام خوشه‌بندي پايه گفته مي‌شود و در گام دوم از كلوخ‌ها براي تركيب خوشه‌بندي ايجاد مي‌شوندو مدل‌سازي رياضياتي از مسئله ايجاد مي‌شود. اين مدل‌سازي در واقع حل رياضياتي مسئله تركيب خوشه‌بندي خواهد بود. در گام سوم با بكارگيري ابزار متن باز SCIP مسئله حل شود.روش پيشنهادي خوشه‌بندي بر روي مجموعه‌داده‌هاي دو بعديRAT575, U1060, Pcb3038و چند بعديIRIS و SEGMENTATIONاعمال شده و با روش‌‌هاي مشابه مقايسه شده است كه ضمن حفظ كامل بهينگي توانسته است زمان خوشه‌بندي را بسته به اندازه مجموعه‌داده كاهش دهد. واژه‌هاي كليدي:خوشه‌بندي، تركيب خوشه‌بندي، كلوخ، تابع هدف، بهينه‌سازي