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

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

کاهش‌يافته را با نشان مي‌دهيم. شبه‌ کد شکل زير مراحل اجراي روش پيشنهادي ژيا را نشان مي‌دهد: [86]

Step 1: Initialize the reduced subset to the original set O;
Step 2: For each clustering, compute
Step 3: Find clustering for which is the minimum.
Retain it in and discard its nearest neighbors (Note: denotes the clustering for which removing its nearest neighbors will cause minimum error among all clusterings in).
Step 4: Repeat steps 2 and 3 until the predefined number of clusterings is achieved.
Step 5: Return to as the reduced clustering set.
After the selection process, we apply a consensus function to this subset and get a consensus partition.
شکل 2-29. الگوريتم خوشه‌بندي ترکيبي طيفي مبتني بر انتخاب بر اساس شباهت [86]

در شکل بالا ابتدا زيرمجموعه کاهش‌يافته ايجاد مي‌شود. سپس براي هر خوشه‌بندي مقدار محاسبه مي‌شود. آنگاه خوشه‌بندي به نحوي انتخاب مي‌شود که مقدار آن کمينه باشد. دو فرآيند محاسبه و پيدا کردن آن قدر تکرار مي‌شود تا مطابق با تعداد از قبل تعريف‌شده نتيجه‌ي خوشه‌بندي به دست آوريم. در انتها با استفاده از يک تابع توافقي خوشه‌بندي‌ها را باهم ترکيب کرده و نتيجه نهايي را به دست مي‌آوريم [86].
2-4-4. خوشه‌بندي ترکيبي انتخابي لي‌مين
اين الگوريتم توسط لي‌مين و همکاران ارائه شده است که ما آن را با عنوان خوشه‌بندي ترکيبي انتخابي129 لي‌مين مي‌شناسيم. در اين الگوريتم ابتدا به اين موضوع اشاره مي‌شود ‌که چون معمولاً در روش‌هاي مبتني بر انتخاب تمامي مقايسه‌ها بر اساس يک افزار مرجع صورت مي‌گيرد، کيفيت اين افراز بر روي نتايج نهايي تأثير به سزايي دارد. از اين روي در اين روش دو رويکرد پيشنهاد مي‌شود: ابتدا براي انتخاب بهترين افراز مرجع بر اساس ارزيابي اعتبار خوشه‌بندي راه‌حلي پيشنهاد مي‌شود و سپس يک راهکار انتخاب خوشه‌ي جديد با استفاده از وزن اعضا پيشنهاد مي‌شود. در ادامه روش پيشنهادي لي‌مين و همکاران را شرح مي‌دهيم: [85]
فرض کنيد مجموعه‌يتايي از نقــــاط داده و مجموعه‌يتايي افراز‌هاي خوشه‌بندي‌ بر روي اين مجموعه داده‌ مي‌باشد. هر افراز شامل مجموعه خوشه‌هاي مي‌باشد که تعداد خوشه‌هاي افراز است و رابطه همواره برقرار مي‌باشد. هدف اين روش انتخاب زيرمجموعه‌ي بر اساس راهکار انتخاب خوشه پيشنهادي آن (که در ادامه بررسي خواهيم کرد) از مجموعه و ساخت نتيجه نهايي مطابق با زيرمجموعه‌ي با استفاده از تابع توافقي مي‌باشد [85].
2-4-4-1. انتخاب افراز مرجع در روش لي‌مين
همان طور که پيش‌تر ذکر شد انتخاب افزار مرجع در خوشه‌بندي مبتني بر انتخاب مهم مي‌باشد و تأثير به سزايي در کيفيت نتيجه نهايي دارد. هر چه افراز مرجع باکيفيت‌تر باشد مي‌تواند تأثير کيفيت پايين نتايج توليدشده را از بين ببرد. از اين روي باکيفيت‌ترين افراز بايد به عنوان افراز مرجع انتخاب شود. معمولاً بهترين خوشه‌بندي را به صورتي که اعضاي داخل خوشه نسبت به هم شبيه‌تر و نسبت به اعضاي ساير خوشه‌ها متفاوت‌تر باشند تعريف مي‌کنيم. در روش پيشنهادي لي‌مين از غلظت130 و جدايي131 به عنوان معيار کيفيت استفاده شده است که ما آن را شرح مي‌دهيم. ابتدا ميانگين مجموعه داده‌ي‌‌ را به صورت و وردايي132 مجموعه داده را به صورت محاسبه مي‌کنيم که در آن فاصله‌ي دو داده‌ي و مي‌باشد. مطابق تعاريف بالا غلظت افراز به صورت رابطه زير تعريف مي‌شود [85].
(2-59)
اين الگوريتم براي بر اساس توزيع گوسي جدايي را مطابق رابطه زير تعريف مي‌کند:
(2-60)
در رابطه بالا ثابت گوسي (بر اساس تنظيم مي‌شود) و پارامتر‌هايو به ترتيب مراکز و مي‌باشد. براي اعتبارسنجي کيفيت خوشه‌ها روش لي‌مين مطابق رابطه زير دو معيار غلظت و جدايي را در يک تابع مشترک ادغام مي‌کند: [85]
(2-61)
در اين رابطه پارامتر براي کنترل تأثيرات دو معيار غلظت و جدايي است که در اين روش در نظر گرفته شده است تا تأثيرات دو معيار برابر باشد. در ادامه اين روش مقدار را براي تمامي محاسبه کرده و افرازي که مقدار آن کمينه باشد را به عنوان افراز مرجع در نظر مي‌گيرد و آن را نام‌گذاري مي‌کند [85].
2-4-4-2. راهکار انتخاب خوشه در روش‌ لي‌مين
منظور از راهکار انتخاب خوشه، گزينش بهترين افراز‌هاي خوشه‌بندي از ميان تمامي افراز‌هاي توليدشده مي‌باشد. انتخاب راهکار مناسب موجب مي‌شود که در افراز‌هاي انتخاب‌شده ويژگي‌هاي ضمني مجموعه داده منعکس شود و عملکرد خوشه‌بندي را بهبود يابد. روش لي‌مين يک راهکار بر اساس معيار کيفيت و پراکندگي براي انتخاب خوشه پيشنهاد مي‌کند که ما آن را در ادامه بررسي خواهيم کرد [85].
در روش‌هاي بدون ناظر، مسئله خوشه‌بندي بدون برچسب عمل مي‌کند. بنابراين تناظر روشني بين نتايج فراهم‌شده با استفاده از خوشه‌هاي مختلف نيست. براي مثال نتايج دو خوشه‌بنديو مشابه در نظر گرفته مي‌شوند. براي حل اين مشکل اين روش يک ماتريس اتصال133 را تعريف مي‌کند. در اين تعريف مجموعه افراز‌هاي به صورت رابطه زير به ماتريس اتصال تبديل مي‌شود: [85]
(2-62)
مطابق رابطه بالا شکل زير ماتريس اتصال مثال ذکرشده (براي افراز‌هاي و) را نشان مي‌دهد:

شکل 2-30. مثالي از ماتريس اتصال [85].
حال فرض کنيد براي مجموعه افراز‌هاي و افراز مرجع به ترتيب ماتريس‌هاي اتصال و موجود مي‌باشند. شباهت خوشه‌بندي‌ها به صورت رابطه زير تعريف مي‌شود:
(2-63)
در رابطه بالا توافق134 (اشاره به معيار توافقي براي ارزيابي) بين دو ماتريس است که رويکرد‌هاي متنوعي براي محاسبه آن وجود دارد. روش پيشنهادي لي‌مين از معيار براي محاسبه استفاده مي‌کند. مطابق با رابطه بالا مي‌توان نتيجه گرفت که شبيه‌ترين به و باکيفيت‌ترين داراي بالاترين مقدار مي‌باشد. به طور مشابه، پراکندگي خوشه‌بندي به صورت رابطه زير تعريف مي‌شود: [85]
(2-64)
بديهي است که با بيش‌ترين پراکندگي داراي بالاترين مقدار مي‌باشد. در روش لي‌مين استفاده همزمان معيار کيفيت و پراکندگي به عنوان يک راهکار مناسب جهت انتخاب خوشه معرفي مي‌شود. از آنجايي که گاهي اوقات اين دو عامل متناقض در نظر گرفته مي‌شوند، اين روش يک تناظر135 بين اين دو معيار در افرازبندي‌ها برقرار مي‌کند. از اين روي رابطه زير توسط لي‌مين براي ترکيب کيفيت و پراکندگي پيشنهاد مي‌شود: [85]
(2-65)
در رابطه بالا پارامتر براي متعادل کردن معيار‌هاي پراکندگي و کيفيت استفاده مي‌شود که در اين روش پيشنهادي در نظر گرفته شده است. با محاسبه رابطه (1-7) براي تمامي افراز‌ها در خوشه‌بندي‌ها مطابق روش لي‌مين مي‌توان يک ارزيابي از خوشه‌ها داشت که بر اساس آنتا از بهترين افراز‌ها () جهت ساخت کميته136 ترکيب انتخاب مي‌شود. قابل‌ذکر است که اگر برابر با باشد تمامي افراز‌ها در ترکيب نهايي شرکت مي‌کنند و اگر برابر با يک باشد فقط يک افزار نتيجه نهايي را مي‌سازد و در صورتي که باشد متناسب با تعادل بين دقت و پراکندگي افراز‌ها انتخاب مي‌شوند [85].
2-4-4-3. چهارچوب الگوريتم خوشه‌بندي انتخابي لي‌مين
از آنجايي که اثر انتخاب افراز‌ها در نتيجه خوشه‌بندي نهايي متفاوت است در اين روش يک وزن براي کنترل الگوريتم پيشنهاد مي‌شود. براي هر افراز انتخاب‌شده، ميانگين مقادير تابع مطابق با رابطه 1-7 به عنوان وزن آن افزار به صورت زير انتخاب مي‌شود: [85]
(2-66)
افرازي که بيش‌ترين تأثير در ساخت نتايج نهايي را دارد داراي مقدار بيشينه خواهد بود. بنابراين رابطه وزن به صورت زير تعريف مي‌شود:
(2-67)
که براي نرمال سازي وزن استفاده مي‌شود. از اين روي و مي‌باشد. در اين روش بعد از اختصاص وزن به تمامي افراز‌هاي انتخاب‌شده، آن‌ها را با استفاده از تابع توافقي ادغام مي‌کنيم. شکل زير شبه کد الگوريتم پيشنهادي لي‌مين را نشان مي‌دهد [85].

Step1: Using some clustering algorithm (runs H times) to get H clustering partitions.
Setp2: Calculating objective function OBJ of all available clustering partitions and choosing the minimum (that is) as the reference partition.
Setp3: Calculating criterion function and choosing K best clustering partitions.
Setp4: Calculating the weight of K best clustering partitions.
Setp5: Using the CSPA consensus function to produce the final result.
شکل 2-31. شبه کد خوشه‌بندي ترکيبي انتخابي لي‌مين [85]

2-4-5. خوشه‌بندي بر اساس معيار MAX با استفاده از مجموعه‌اي از خوشه‌هاي يک افراز
اين روش توسط عليزاده و همكاران ارائه شده است كه در آن به جاي ارزيابي افراز به صورت كامل (استفاده از تمامي خوشههاي افراز) به ارزيابي خوشهها به صورت مجزا ميپردازد و سپس با استفاده از مجموعهاي از آن خوشهها جواب نهايي را تشكيل ميدهد. در اين روش براي حل مشكل NMI راهكاري با عنوان روش MAX ارائه ميشود [9]. در ادامه ابتدا به بررسي راهكارهاي پيشنهادي در اين روش ميپردازيم.
2-4-5-1. راهكار ارزيابي خوشهي MAX

شكل 2-32. روش ارزيابي خوشهي يك افراز در روش MAX
شكل 2-32 روش ارزيابي خوشه را با خوشهاي از ساير افرازهاي ساختهشده براي تركيب نشان ميدهد. در اين شكل براي حل مشكل تقارن NMI بـقيه خوشههاي افرازي كه در آن وجود دارد را با عـنوان ميشناسيم و خوشهاي كه قرار است با خوشهي مقايسه شود را و ساير خوشههاي افراز مقايسه شونده را ميناميم. عليزاده و همكاران در [9] اثبات كردهاند كه در اين حالت مشكل تقارن در NMI حل ميشود. همچنين در اين روش معياري تحت عنوان پايداري براي ارزيابي خوشهها ارائه شده است.
(2-68)
در رابطه بالا پارامتر M تعداد خوشههاي افراز مرجع را نشان ميدهد و اطلاعات متقابل نرمال شده مطابق رابطه 2-69 به ازاي و ساير خوشههاي افراز مرجع محاسبه ميشود.
(2-69)
در رابطه بالا n تعداد كل نمونهها و تعداد الگوهاي مشترك بين و و تعداد الگوهاي خوشهي i از افراز a و تعداد الگوهاي خوشهي j از افراز b ميباشد.
2-4-5-2. روش انباشت مدارك توسعهيافته
از آن جايي كه در روش MAX تمامي خوشه‌هاي يک افراز در ساخت نتيجه نهايي وجود ندارد نمي‌توان از روش کلاسيک براي ساخت ماتريس همبستگي استفاده کرد، از اين روي عليزاده و همکاران روش انباشت مدارک توسعه‌يافته (137) را معرفي کردند [8, 9, 67] که براي ساخت ماتريس همبستگي از رابطه (2-70) استفاده مي‌کند.
(2-70)
در اين رابطهتعداد دفعاتي است که نمونهدر خوشه‌هاي انتخاب‌شده ظاهر شده است. به طور مشابه نيز، تعداد دفعاتي است که نمونهدر خوشه‌هاي انتخاب‌شده ظاهر شده است. همچنين تعداد دفعاتي است که جفت نمونه‌هاي و باهم در يک خوشه از خوشه‌هاي انتخاب‌شده ظاهرشده‌اند. بديهي است که با در نظر گرفتن تعداد خوشه‌هاي ثابت در خوشه‌بندي‌هاي اوليه همواره و کمتر از تعداد کل افرازهاي اوليه و همچنين، تعداد کل خوشه‌هاي ممکن مي‌باشد.
2-4-6. خوشه‌بندي بر اساس معيار APMM با استفاده از مجموعه‌اي از خوشه‌هاي يک افراز
اين روش توسط عليزاده و همکاران بر اساس معيار APMM (رابطه 2-29) ارائه شده است كه در آن همانند روش MAX، تـعدادي از خـوشههاي يك افراز در تهيه نتيجه نـهايي به كـار گـرفته

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