منابع و ماخذ پایان نامه خوشه‌بندي، ترکيب، پراکندگي

دانلود پایان نامه ارشد

ديگر ارزيابي و انتخاب نيز مطرح شده است که ما آن‌ها را به ترتيب زمان ارائه بررسي خواهيم کرد.
2-4-1. خوشه‌بندي تركيبي مبتني بر انتخاب فرن و لين
در اين روش براي خوشه‌بندي ترکيبي از زيرمجموعه‌ي موثرتري از افرازهاي اوليه در ترکيب نهايي استفاده مي‌شود. اگر چه تعداد اعضاي شرکت‌کننده در ترکيب نهايي در اين روش کمتر از يک خوشه‌بندي ترکيبي کامل است، به دليل انتخاب افرازها با کارايي بالاتر، نتايج نهايي بهبود مي‌يابند. پارامترهايي که در اين روش مورد توجه قرارگرفته‌اند، عبارت‌اند از: کيفيت و پراکندگي.
در يادگيري با ناظر مفاهيم کيفيت و پراکندگي خوش‌تعريف هستند، کيفيت دقت اعضاي ترکيب و پراکندگي تفاوت بين پيش‌بيني‌هاي انجام‌شده توسط اعضاي ترکيب را اندازه‌گيري مي‌کنند ولي اين مفاهيم در يادگيري بدون ناظر به صورت واضح تعريف‌نشده‌اند [23]. در اين بخش رويکرد‌هاي روش فرن و لين را جهت حل چالش‌هاي پيش روي شرح مي‌دهيم که در آن ابتدا روش اندازه‌گيري کيفيت و پراکندگي خوشه‌بندي را بيان مي‌کنيم و سپس براي هر دو معيار فوق يک راهکار انتخاب توصيف مي‌کنيم.
2-4-1-1. تعريف معيار کيفيت در روش فرن و لين
در روش‌هاي بدون ناظر، ما هيچ تابع هدف خارجي همانند دقت براي اندازه‌گيري کيفيت راه‌حل‌هاي خوشه‌بندي نداريم. در ادبيات خوشه‌بندي، به طور معمول، يک برچسب کلاس به عنوان جانشين براي ساختار زيربنايي درست استفاده مي‌شود و سپس بر مبناي اين که چگونه اين راه حل برچسب‌هاي کلاس را بازيابي مي‌کند کيفيت خوشه‌بندي اندازه‌گيري مي‌شود. اين روش در خوشه‌بندي ترکيبي مبتني بر انتخاب نمي‌تواند استفاده شود به خاطر اين که اطلاعات با ناظر همانند برچسب کلاس نمي‌تواند در فرآيند خوشه‌بندي استفاده شود. در اينجا، ما يک معيار داخلي کيفيت بر اساس تابع هدف معرفي‌شده توسط استرل و گاوش [54] براي طراحي تابع توافقي پيشنهاد مي‌کنيم. به طور خاص، يک ترکيب از راه حل خوشه‌بندي توسط نشان داده شده است، به دنبال پيدا کردن خوشه‌بندي توافقي که اين معيار را بيشينه مي‌کند:
(2-43)
در اينجا معيار اطلاعات متقابل نرمال شده بين خوشه‌بندي‌هاي و مي‌باشد. اگر دو خوشه‌بندي کاملاً مستقل از يکديگر باشند مقدار برابر با صفر خواهد شد. در مقابل، اگر دو خوشه‌بندي کاملاً مشابه باشد آنگاه مقدار برابر با يک خواهد شد. در اينجا تابع هدف ما برابر با جمع اطلاعات متقابل نرمال شده () است. در اين روش براي يک مجموعه از خوشه‌بندي‌هاي جهت اندازه‌گيري کيفيت هر خوشه از رابطه استفاده مي‌کنيم.
2-۴-۱-2. تعريف معيار پراکندگي در روش فرن و لين
چندين معيار مختلف براي خوشه‌بندي ترکيبي پيشنهاد شده است. فرن و لين [23] معياري که توسط فرن و برودلي [22] ارائه شده است را به عنوان معيار پراکندگي پيشنهاد داده‌اند که بر پايه اطلاعات متقابل نرمال شده دوتايي ميان راه حل خوشه‌بندي‌ها است. به طور خاص، ما تشابه دو جفت خوشه‌بندي را به صورت اندازه گرفته و جمع تمامي تشابهات دوتايي را در ترکيب محاسبه کرده و به عنوان معيار پراکندگي ترکيب در نظر مي‌گيريم. هر چند ارزش کمتر باشد پراکندگي بيشتر است. معيار پراکندگي بالا به اين علت انتخاب شده است چون نشان داده که در عملکرد خوشه‌بندي ترکيبي تأثير مي‌گذارد. بايد متذکر شد که متد انتخابي [23] خود را محدود به هيچ معيار پراکندگي خاصي نمي‌کند.
2-۴-۱-3. راهکار انتخاب خوشه‌ براي تشکيل نتيجه نهايي در روش فرن و لين
کيفيت: در اولين مرحله از اين روش، از معيار‌هاي تعريف‌شده پيشين براي راهنمايي انتخابمان استفاده مي‌کنيم و تنها اين راه‌حل‌ها است که داراي کيفيت بالايي در ترکيب مي‌باشند [23]. به طور خاص، اگر مجموعه راه‌حل‌هاي خوشه‌بندي به ما داده شده باشد، اين راهکار تمامي راه‌حل‌هاي خوشه‌بندي را در رتبه‌بندي کرده که اين عمل را بر پايه کيفيت آن‌ها با استفاده از انجام مي‌دهد و راه حل با رتبه بالا را براي حضور در ترکيب انتخاب مي‌کند، که اندازه دلخواه ترکيب مي‌باشد. ما اين راهکار را کيفيت مي‌ناميم. توجه کنيد که اگر يک راهکار مقدار بالايي داشته باشد، به طور مفهومي، اين راه حل سازگاري بالايي را با روند عمومي که توسط کل مجموعه نشان داده شده است، دارا است. از طرف ديگر، راه‌حل‌هاي خوشه‌بندي باارزش پايين مي‌توانند به عنوان مجموعه در نظر گرفته شوند و ممکن است که براي حضور در ترکيب مفيد باشند. به طور کلي، ترکيب‌هاي انتخاب‌شده توسط کيفيت مي‌توانند افزونگي بالايي را در راه‌حل‌هاي انتخاب‌شده داشته باشد.
پراکندگي، در مقابل، اين روش به دنبال راهکار‌هاي انتخابي مي‌گردد که مقدار پراکندگي را بيشينه کند. اينجا مي‌توان سنگين‌ترين گراف رأسي119 را به عنوان يک مشکل در نظر گرفت. به طور خاص، راه حل خوشه‌بندي در مجموعه به عنوان رئوس در گراف کاملاً متصل، نشان داده مي‌شود و مقدار پراکندگي هر جفت آن‌ها () به عنوان وزن لبه‌هايي که به رئوس متصل‌اند، اختصاص داده مي‌شوند. انتخاب يک ترکيب به اندازه‌ي، با پراکندگي بيشينه مي‌تواند به وسيله يافتن يک زير گراف با رأس که وزن لبه‌هاي آن بيشينه شده مي‌باشد (که همان سنگين‌ترين گراف رأسي مي‌باشد) به دست آيد. با اين وجود، اين مشکل از درجه سختي برخوردار است [39]. در [23] از يک راهکار ساده حريصانه که به صورت زير توصيف شده است استفاده مي‌کنيم.
ما با يک ترکيب که شامل يک راه حل باکيفيت بسيار بالا مي‌باشد شروع مي‌کنيم‌ (همان طور که توسط اندازه‌گيري شده است). سپس آن به صورت افزايشي در هر زمان يک راه حل از کتابخانه براي اضافه کردن به انتخاب مي‌کند. اين عمل به اين دليل انجام مي‌شود که ترکيب نهايي بيش‌ترين پراکندگي را که همان کمترين مقدار مي‌باشد، داشته باشد. اين فرآيند تکرار مي‌شود تا اينکه ما به ترکيب دلخواهمان به سايز برسيم. در ادامه ما اين راهکار را با عنوان پراکندگي مي‌شناسيم.
در ادبيات موضوعي در [23]، الگوريتم مکاشفه‌اي مختلفي براي توليد راه‌حل‌هاي خوشه‌بندي مختلفي براي خوشه‌بندي ترکيبي پيشنهاد شده است و به صورت عمومي اين اعتقاد وجود دارد که متنوع کردن خوشه‌بندي ترکيبي تأثير سودمندي خواهد داشت. زيرا اشتباهاتي که توسط اعضاي مختلف ترکيب انجام مي‌شود ممکن است که همديگر را حذف کنند. راهکار پراکندگي که در اينجا صحبت شد از اين فلسفه پيروي کرده و به طور صريح به دنبال زيرمجموعه‌هاي با پراکندگي بالا از مجموعه، براي شکل دادن ترکيب مي‌گردد. توجه کنيد که مشکل بالقوه در مورد اين روش (متد) اين است که ممکن است منجر به شمول برخي راه‌حل‌ها باکيفيت پايين در ترکيب شود.
2-4-2. الگوريتم هوشمند طبقه‌بندي مجموعه داده‌ها
يكي ديگر از روش‌هايي كه در خوشه‌بندي تركيبي مبتني بر انتخاب ارائه شده است روش عظيمي و همكاران مي‌باشد [7]. در اين روش از مفهوم پراکندگي براي هوشمند نمودن خوشه‌بندي ترکيبي استفاده شده است و به صورت پويا اقدام به انتخاب زيرمجموعه بهينه‌اي از نتايج اوليه در ترکيب نهايي مي‌شود، ابتدا يک خوشه‌بندي ترکيبي ساده انجام مي‌شود و سپس اين روش ميزان شباهت تمام نتايج خوشه‌بندي‌هاي اوليه را نسبت به جواب به دست آمده ارزيابي مي‌کند و سعي در طبقه‌بندي120 مجموعه داده‌ها به سه مجموعه داده راحت121، معمولي122 و سخت123 مي‌کند. در اين طبقه‌بندي، مجموعه داده راحت به مجموعه دادهاي اطلاق مي‌شود که خوشه‌بندي‌هاي اوليه تفاوت چنداني با خوشه‌بندي ترکيبي به دست آمده نداشته باشند. به اين معني که هر خوشه‌بندي ساده بتواند تقريباً مانند خوشه‌بندي ترکيبي نتايج مشابه اي ارائه کند. مجموعه داده معمولي به مجموعه داده‌اي اطلاق مي‌شود که خوشه‌بندي‌هاي اوليه نه تفاوت چنداني و نه تشابه چنداني با نتايج خوشه‌بندي ترکيبي به دست آمده دارند. مجموعه داده سخت به مجموعه دادهاي اطلاق مي‌شود که خوشه‌بندي‌هاي اوليه تشابه چنداني با خوشه‌بندي ترکيبي به دست آمده نداشته باشند. اين رويداد نشان مي‌دهد که داده‌هاي مجموعه مورد نظر کاملاً داراي مرزهاي مشترک هستند و روش‌هاي ساده و معمولي خوشه‌بندي همانند روش‌هاي پيچيده و قدرتمند خوشه‌بندي ترکيبي قادر به جداسازي نمونه‌ها نمي‌باشند. سپس کل نتايج خوشه‌بندي‌هاي اوليه به چهار زيرمجموعه متفاوت بر اساس ميزان تطبيق دقتشان با نتايج خوشه‌بندي ترکيبي ساده تقسيم مي‌شوند و بر اساس رده124 هر مجموعه داده (راحت، معمولي و سخت) اقدام به انتخاب يکي از اين زيرمجموعه‌ها براي ترکيب و به دست آوردن نتيجه نهايي مي‌کنيم [5, 7].
2-4-3. خوشه‌بندي ترکيبي طيفي مبتني بر انتخاب بر اساس شباهت
اين الگوريتم توسط ژيا و همکاران ارائه شده است که در آن مؤلفه‌هاي خوشه‌بندي که توسط الگوريتم‌هاي خوشه‌بندي طيفي توليد مي‌‌شوند، قادر به ايجاد کميته‌هاي پراکندگي125 خواهند بود. همچنين در اين روش، پارامتر مقياس گذاري تصادفي در تقريب نيستروم126 و مقادير تصادفي اوليه الگوريتم براي آشفتن127 الگوريتم خوشه‌بندي طيفي در توليد مؤلفه‌هاي يک ترکيب مورد استفاده قرار مي‌گيرند. علاوه بر آن يک معيار بر اساس ترکيب معيارهاي پراکندگي و کيفيت براي ارزيابي کيفيت تمامي نتايج به دست آمده پيشنهاد شده است و يک روش جديد انتخاب خوشه بر اساس قانون نزديک‌ترين همسايه جهت انتخاب نتايج اوليه معرفي مي‌شود [86].
2-4-3-1. معيار ارزيابي در روش پيشنهادي ژيا
در روش ژيا و همکاران مطابق رابطه زير از تفاضل عدد يک از اطلاعات متقابل نرمال‌ شده به عنوان پراکندگي استفاده شده است [86].
(2-57)
در رابطه بالا هر چه معيار بزرگ‌تر باشد پراکندگي بين دو خوشه‌بندي مورد ارزيابي بيشتر خواهد بود. اين معيار براي هر دو خوشه‌بندي مساوي برابر با صفر مي‌باشد. از طرف ديگر در ساخت يک ترکيب مناسب بايد معيار دقت نيز در نظر گرفته شود تا نتايج نامطلوب، کارايي کل سيستم را مورد تأثير قرار ندهند. از اين روي روش پيشنهادي ژيا يک تابع جديد براي ارزيابي هم زمان دقت و پراکندگي مطابق با رابطه زير با عنوان پيشنهاد کرده است [86].
(2-58)
شکل (2-28) نشان‌دهنده‌ي منحني تابع بر اساس در بازه بين صفر الي يک مي‌باشد. اين شکل نشان مي‌دهد که هر گاه مقدار يک و يا صفر باشد مقدار صفر است. اين تحقيق خوشه‌بندي‌هايي با مقدار صفر را به عنوان نويز در نظر مي‌گيرد و در صورت برابر بودن نتايج دو خوشه‌بندي (که مقدار آن دو برابر يک مي‌باشد) در اين روش يکي از آن‌ دو نتيجه مورد استفاده قرار مي‌گيرد. مطابق تعاريف بالا تنوع نتايج اوليه انتخاب‌شده در اين روش در حد متوسط128 مي‌باشد [86].

شکل 2-28. گراف تابع در بازه بين صفر و يک [86].
2-4-3-2. انتخاب خوشه‌بندي بر اساس قانون نزديک‌ترين همسايه در روش ژيا
در خوشه‌بندي مبتني بر انتخاب پيشنهادي اين تحقيق دو فرآيند انجام مي‌شود. ابتدا افرازبندي يک مجموعه خوشه‌بندي به تعداد زيرمجموعه‌هاي همگن تقسيم مي‌شود و سپس از هر يک از آن‌ها يک خوشه‌بندي نماينده انتخاب مي‌شود. افرازبندي خوشه‌بندي‌ها بر اساس مفاهيم نزديک‌ترين همسايه با استفاده از معيار پراکندگي (که در بخش قبل شرح داده شده است) انجام مي‌شود که در انجام اين کار، ابتدا زوج فاصله‌ي ميان مؤلفه‌هاي‌ خوشه‌بندي‌ را محاسبه مي‌کنيم و سپس بر اساس تعاريف بخش قبل نزديک‌ترين همسايه را حذف مي‌کنيم. اين فرآيند آن قدر تکرار مي‌شود تا تمام خوشه‌هاي باقي‌مانده يا انتخاب شوند يا حذف شوند. در اين روش تعداد خوشه‌‌‌بندي‌هايي که قرار است در فرآيند بالا انتخاب شوند از قبل تعريف مي‌شوند. مطابق اين تعاريف روش پيشنهادي ژيا را به صورت زير تعريف مي‌کنيم: [86]
فرض کنيد که تعداد خوشه‌بندي‌هاي اصلي ‌باشد و مجموعه‌ي اصلي خوشه‌بندي‌ به صورت و فاصله‌ي بين خوشه‌هاي و به صورت تعريف شوند که در آن براي محاسبه معيار از تعاريف بخش قبل ‌استفاده مي‌کنيم و فاصله‌ي بين خوشه‌بندي و نزديک‌ترين همسايه آن در زيرمجموعه

پایان نامه
Previous Entries منابع و ماخذ پایان نامه سلسله مراتب Next Entries منابع و ماخذ پایان نامه خوشه‌بندي، لي‌مين، زير