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

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

مثال، دو خوشه‌بندي مي‌توانند با مقايسه يا آنتروپي‌شان مقايسه شوند.
اين فصل تعدادي از مهم‌ترين و رايج‌ترين روش‌هاي به‌کاررفته براي ارزيابي خوشه‌بندي را مرور خواهد كرد.
2-2-2-1. معيار SSE
يك معيار داخلي ارزيابي خوشه‌بندي، مثل، مي‌تواند براي ارزيابي يك خوشه‌بندي نسبت به خوشه‌بندي ديگر به كار رود. به علاوه، يك معيار داخلي اغلب مي‌تواند براي ارزيابي يك خوشه‌بندي كامل يا يك خوشه تنها به استفاده شود. اين اغلب به خاطر اين است كه اين روش، سعي مي‌کند تا ميزان خوبي كلي خوشه‌بندي را به عنوان يك جمع وزن‌دار از خوبي‌هاي هر خوشه در نظر مي‌گيرد. با استفاده از رابطه 2-25 محاسبه مي‌شود [68].
(2-25)
كهيك نقطه داده در خوشه است و، j-امين ويژگي از داده X است. ، j-امين ويژگي از مركز خوشه مي‌باشد. براي مقايسه دو خوشه‌بندي مختلف روي يك داده با يك تعداد مشابه، تنها مقايسه مقدارهاي متناظر آن‌ها كافي است. هر چه مقدار كمتر باشد، آن خوشه‌بندي بهتر خواهد بود. البته، وقتي تعداد نقاط داده در دو خوشه متفاوت باشند، مقايسه مستقيم از روي مقدار خوب نخواهد بود. بنابراين، يك خوشه معيار مناسب تري براي مقايسه است. رابطه 2-26 اين معيار را نشان مي‌دهد كه در آن مقدار تعداد كل نمونه‌هاست [68].
(2-26)
تعداد درست خوشه‌ها در الگوريتم ، اغلب مي‌تواند با استفاده از نگاه كردن به منحني مشخص شود. اين منحني با رسم مقادير به ازايهاي مختلف به دست مي‌آيد. تعداد خوشه‌هاي بهينه با توجه به منحني، اي است كه به ازاي آن نرخ كاهش مقدار، قابل چشم‌پوشي شود. شكل 2-13-ب منحني را براي داده‌هاي شكل 2-13-الف، نشان مي‌دهد.

(الف)

(ب)
شکل2-13. (الف) مجموعه داده با تعداد 10 خوشه واقعي. (ب) منحني مربوطه [68]
همان طور كه از شكل 2-13-ب برمي‌آيد، براي مقاديرهاي از صفر تا 10 شيب منحني نسبت به بقيه مقادير، تندتر مي‌باشد. اين امر نشان‌دهنده آن است كه مقدار يك مقدار بهينه براي تعداد خوشه‌ها مي‌باشد.

(الف)

(ب)
شکل2-14. (الف) مجموعه داده (ب) منحني مربوطه [2]
شكل 2-14-ب نيز منحني را براي داده‌هاي شكل 2-14-الف، نشان مي‌دهد. مشاهده مي‌شود كه در اين داده‌ها، چون تعداد خوشه‌ها نسبت به شكل 2-14-الف کاملاً گويا نيست، بنابراين، منحني آن نيز نرم تر خواهد بود . اما با توجه به شكل 2-14-ب، مي‌توان گفت كه تعداد نسبتاً خوب باشد. چون منحني براي هاي بعد از 8، داراي شيب كندتري خواهد شد. با توجه به نتايج فوق مي‌توان گفت كه اگرچه منحني براي همه مسايل نمي‌تواند جواب بهينه براي تعداد بدهد، اما مي‌تواند به عنوان يك معيار خوب براي اين امر مطرح باشد.
2-2-2-2. معيار اطلاعات متقابل نرمال شده
معيار اطلاعات متقابل (80) توسط كاور و توماس [71] معرفي شد كه يك روش جهت اندازه‌گيري كيفيت اطلاعات آماري مشترك بين دو توزيع است. از آنجايي كه اين معيار وابسته به اندازه خوشه‌ها است در [54] روشي جهت نرمال سازي آن ارائه شده است. فرد و جين [19] روش نرمال سازي اطلاعات متقابل را اصلاح كردند و آن را تحت عنوان اطلاعات متقابل نرمال (81) ارائه داده‌اند. رابطه 2-27 اطلاعات متقابل نرمال شده را نشان مي‌دهد[1, 2, 19] .
(2-27)
در رابطه 2-27 پارامتر كل نمونه‌ها است و يعني افرازهايي كه انديس آن‌ها شامل i با تمام مقادير j مي‌باشد و يعني افرازهايي كه تمام مقادير i با و انديس j را شامل شود. از رابطه 2-28 محاسبه مي‌شود [1, 2, 19].
(2-28)
, ,
در صورتي كه دو افراز به صورت و كه در آن كل داده و خوشه اول و خوشه دوم هر يك از افرازها باشد آنگاه نشان‌دهنده تعداد نمونه‌هاي مشترک موجود در و مي‌باشد، نشان‌دهنده تعداد نمونه‌هاي مشترک موجود در و مي‌باشد، نشان‌دهنده تعداد نمونه‌هاي مشترک موجود در و مي‌باشد و نشان‌دهنده تعداد نمونه‌هاي مشترک موجود در و مي‌باشد. در واقع و به ترتيب بيانگر کل نمونه‌هاي موجود در و مي‌باشد [1].
شكل 2-15 دو افراز اوليه را نشان مي‌دهد که ميزان پايداري براي هر کدام از خوشه‌هاي به دست آمده هم محاسبه شده است. در اين مثال الگوريتم به عنوان الگوريتم خوشه‌بندي اوليه انتخاب شده است و تعداد خوشه‌هاي اوليه برابر با سه نيز به عنوان پارامتر آن از قبل مشخص شده است. همچنين، در اين مثال تعداد افرازهاي موجود در مجموعه مرجع برابر با ۴۰ مي‌باشد. در ۳۶ افراز نتايجي مشابه با شکل 2-15 (a) و در 4 حالت باقيمانده نيز نتايجي مشابه با شکل 2-15 (a) حاصل شده است [1].

شکل2-15. دو افراز اوليه با تعداد سه خوشه. (a) خوشه‌بندي درست (b) خوشه‌بندي نادرست [1]
از آن جايي که در مجموعه مرجع در ۹۰ % مواقع، داده‌هاي متراکم گوشه بالا‐چپ از شکل 2-15 در يک خوشه مجزا گروه‌بندي شده‌اند، بنابراين اين خوشه بايد مقدار پايداري بالايي را به خود اختصاص دهد. اگرچه اين مقدار نبايد دقيقاً برابر با يک باشد (چون در همه موارد اين خوشه درست تشخيص داده نشده است)، مقدار پايداري با روش متداول اطلاعات متقابل نرمال شده مقدار يک را بر مي‌گرداند. از آن جايي که ادغام دو خوشه سمت راست تنها در ۱۰ % موارد مانند شکل 2-15 (b) اتفاق افتاده است، خوشه حاصل بايد مقدار پايداري کمي به دست آورد. اگر چه خوشه حاصل از ادغام دو خوشه سمت راستي، به ندرت ( ۱۰ % موارد) در مجموعه مرجع ديده شده است، مقدار پايداري براي اين خوشه نيز برابر با يک به دست مي‌آيد. در اينجا مشکل روش متداول محاسبه پايداري با استفاده از اطلاعات متقابل نرمال شده ظاهر مي‌شود. از آنجايي که معيار اطلاعات متقابل نرمال شده يک معيار متقارن است، مقدار پايداري خوشه بزرگ ادغامي سمت راست (با ۱۰ % تکرار) دقيقاً برابر با ميزان پايداري خوشه متراکم گوشه بالا‐چپ (با ۹۰ % تکرار) به دست مي‌آيد. به عبارت ديگر در مواردي که داده‌هاي دو خوشه مکمل يکديگر باشند، يعني اجتماع داده‌هاي آن‌ها شامل کل مجموعه داده شود و اشتراک داده‌هاي آن‌ها نيز تهي باشد، مقدار پايداري براي هر دو به يک اندازه برابر به دست مي‌آيد. از ديدگاه ديگر، اين اتفاق زماني رخ مي‌دهد که تعداد خوشه‌هاي تشکيل‌دهنده مجموعه در خوشه‌بندي مرجع عددي بيشتر از يک باشد. هر زمان که با ادغام دو يا بيشتر از خوشه‌ها به دست آيد، منجر به نتايج نادرست در مقدار پايداري مي‌شود. ما اين مشكل را تحت عنوان مشكل تقارن در اطلاعات متقابل نرمال شده مي‌شناسيم. در سال‌هاي اخير روش‌هايي جهت حل اين مشكل ارائه‌شده‌اند كه يكي از آن‌ها را عليزاده و همکاران در [1, 9]ارائه داده‌اند که در‌ آن بزرگ‌ترين خوشه از بين مجموعه مرجع (که بيش از نصف نمونه‌هايش در خوشه مورد مقايسه وجود دارد) جايگزين اجتماع همه خوشه‌ها مي‌شود که ما آن را با عنوان روش Max مي‌شناسيم. روش ديگر جهت رفع اين مشکل معيار 82APMM مي‌باشد. در ادامه به بررسي اين معيار مي‌پردازيم [1, 8, 67].
2-2-2-3. معيار APMM
بر خلاف معياركه براي اندازه‌گيري شباهت دو افراز طراحي شده است معيار روشي براي اندازه‌گيري ميزان شباهت يك خوشه در يك افراز است كه توسط عـليزاده و همكاران [8, 67] معرفي شده است رابطه 2-29 اين معيار را معرفي مي‌کند.
(2-29)
در رابطه 2-29 پارامتر خوشه i-ام در افراز مي‌باشد و افراز متناظر با خوشه در خوشه‌بندي است. پارامتر تعداد کل نمونه‌هاي مجموعه داده و تعداد نمونه‌هاي مشترک بين خوشه‌هاي و مي‌باشد. همچنين، تعداد خوشه‌هاي موجود در افراز مي‌باشد. در اين روش براي محاسبه پايداري خوشه از رابطه 2-30 استفاده مي‌کنيم [8, 67].
(2-30)
در رابطه 2-30 پارامتر نشان‌دهنده j-امين افراز از مجموعه مرجع است و تعداد كل افرازها است [8, 67]. از آنجايي كه اين معيار براي ارزيابي شباهت يك خوشه است مي‌توان هم براي ارزيابي خوشه و هم براي ارزيابي افراز استفاده كرد. جهت استفاده از اين معيار براي ارزيابي يك افراز كافي است آن را براي تک‌تک خوشه‌هاي آن افراز استفاده كنيم و در نهايت از كل مقادير ميانگين بگيريم.
2-۳. خوشه‌بندي ترکيبي
كلمه’Ensemble‘ ريشه فرانسوي دارد و به معني باهم بودن يا در يك زمان مي‌باشد و معمولاً اشاره به واحدها و يا گروه‌هاي مكملي دارد كه باهم در اجراي يك كار واحد همكاري مي‌کنند. تركيب تاريخ طولاني در دنياي واقعي دارد، نظريه هيئت‌منصفه ي کندورست كه در سال 1785 ميلادي مطرح شده است و اين ايده را مطرح مي‌کند كه، احتمال نسبي درستي نظر گروهي از افراد (رأي اکثريت) بيشتر از نظر هر يك از افراد به تنهايي مي‌باشد را مي‌توان دليلي براي تركيب نتايج در دنياي واقعي دانست [10, 27]. خوشه‌بندي ترکيبي روشي جديد در خوشه‌بندي مي‌باشد که از ترکيب نتايج روش‌هاي خوشه‌بندي متفاوت به دست مي‌آيد از آنجايي که اکثر روش‌هاي خوشه‌بندي پايه روي جنبه‌هاي خاصي از داده‌ها تاکيد مي‌کنند، در نتيجه روي مجموعه داده‌هاي خاصي کارآمد مي‌باشند. به همين دليل، نيازمند روش‌هايي هستيم که بتواند با استفاده از ترکيب اين الگوريتم‌ها و گرفتن نقاط قوت هر يک، نتايج بهينه‌تري را توليد کند. هدف اصلي خوشه‌بندي ترکيبي جستجوي نتايج بهتر و مستحکم‌تر، با استفاده از ترکيب اطلاعات و نتايج حاصل از چندين خوشه‌بندي اوليه است [18, 54]. خوشه‌بندي ترکيبي مي‌تواند جواب‌هاي بهتري از نظر استحکام83، نو بودن84، پايداري85 و انعطاف‌پذيري86 نسبت به روش‌هاي پايه ارائه دهد [3, 21, 54, 57]. به طور خلاصه خوشه‌بندي ترکيبي شامل دو مرحله اصلي زير مي‌باشد : [34, 54]
1- توليد نتايج متفاوت از خوشه‌بندي‌ها، به عنوان نتايج خوشه‌بندي اوليه بر اساس اعمال روش‌هاي مختلف که اين مرحله را، مرحله ايجاد تنوع يا پراکندگي87 مي‌نامند.
2- ترکيب نتايج به دست آمده از خوشه‌بندي‌هاي متفاوت اوليه براي توليد خوشه نهايي؛ که اين کار توسط تابع توافقي88 (الگوريتم ترکيب‌کننده) انجام مي‌شود.
2-۳-1. ايجاد تنوع در خوشه‌بندي ترکيبي
در خوشه‌بندي ترکيبي، هرچه خوشه‌بندي‌هاي اوليه نتايج متفاوت تري ارائه دهند نتيجه نهايي بهتري حاصل مي‌شود. در واقع هرچه داده‌ها از جنبه‌هاي متفاوت‌تري مطالعه و بررسي شوند (تشخيص الگوهاي پنهان داده) نتيجه نهايي که از ترکيب اين نتايج حاصل مي‌شود متعاقباً داراي دقت بالاتري خواهد بود كه اين امر منجر به كشف دانش ضمني پنهان در داده نيز خواهد شد. تنوع در اين بخش به اين معنا مي‌باشد که با استفاده از روش‌هاي متفاوت مجموعه داده را از ديدگاه‌هاي گوناگوني مورد بررسي قرار دهيم. در اين فصل براي ايجاد پراکندگي در بين نتايج حاصل چند راه‌کار مختلف پيشنهاد مي‌کنيم و به بررسي مطالعات انجام‌شده در هر يک از آن‌ها مي‌پردازيم. راه‌هاي مختلفي براي ايجاد پراکندگي در خوشه‌بندي ترکيبي وجود دارد که عبارت‌اند از:
1- استفاده از الگوريتم‌هاي متفاوت خوشه‌بندي.
2- تغيير مقادير اوليه و يا ساير پارامترهاي الگوريتم خوشه‌بندي انتخاب‌شده.
3- انتخاب بعضي از ويژگي داده‌ها يا ايجاد ويژگي‌هاي جديد.
4- تقسيم‌بندي داده‌هاي اصلي به زيرمجموعه‌هايي متفاوت و مجزا.
در حقيقت به خاطر ماهيت بدون ناظر بودن مسئله خوشه‌بندي اين اصل که آيا پراکندگي به وجود آمده مفيد مي‌باشد يا مفيد نيست را نمي‌تواند مورد مطالعه قرارداد اما نتايج تجربي نشان داده است كه ايجاد پراکندگي در خوشه‌بندي‌هاي اوليه به طور معمول موجب بهبود خوشه‌بندي در اکثر مواقع مي‌شود لذا در روش‌هاي ارائه‌شده هدف تنها بررسي مجموعه داده از زواياي مختلف است [42] .
2-۳-1-1. استفاده از الگوريتم‌هاي مختلف خوشه‌بندي ترکيبي
به طور معمول بيشتر روش‌هاي خوشه‌بندي ترکيبي از الگوريتم جهت خوشه‌بندي اوليه خود استفاده مي‌کنند [37, 47, 56, 57]. اما در روش‌هاي ارائه‌شده نشان

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