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

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

مي‌تواند با استفاده از افرازهاي ناقص به توليد خوشه‌بندي ترکيبي بپردازد. در برخي از افرازها نتايج خوشه‌بندي مي‌توان شاهد ظاهر شدن زيرمجموعه‌اي از نمونه‌گيري‌ها يا باز نمونه‌گيري از داده باشيم. براي مثال، يک افراز از يک نمونه خود راه‌انداز99 فقط برچسب‌هايي براي نقاط انتخاب‌شده را فراهم مي‌کند. از اين روي، ترکيبي با چنين افرازهايي توسط مجموعه بردارهايي از برچسب خوشه نشان داده مي‌شود که پتانسيل مفقود شدن مؤلفه‌هاي را دارد. علاوه بر اين، احتمالاً بردارهاي متفاوت از برچسب خوشه مؤلفه‌هاي مختلف را از دست مي‌دهد. وقتي برخي از الگوريتم‌هاي خوشه‌بندي‌هاها را به هيچ خوشه‌اي تخصيص نمي‌دهند، اطلاعات ناقص به وجود مي‌آيند. خوشه‌بندي‌هاي مختلف در ترکيب‌هاي گوناگون مي‌توانند نقاط مشابه را به عنوان يک در نظر بگيرند در غير اين صورت، منجر به از دست رفتن مؤلفه‌هاي بردار مي‌شود. هنوز سناريوي برجسته ديگري جهت از دست رفتن اطلاعات مي‌تواند در ترکيب خوشه‌بندي اطلاعات توزيع‌شده يا ترکيب خوشه‌بندي کپي‌هاي غير يکسان از يک داده رخ دهد.
پذيرش الگوريتم در مورد داده‌هاي گم شده، يعني برچسب‌هاي مفقودشده خوشه براي نقاط داده مشابه، امکان‌پذير است [27]. در اين شرايط، هر بردار از به دو بخش مشاهده‌شده و مفقودشده تقسيم مي‌شود. ادغام داده‌هاي گم شده منجر به اصلاح جزئي محاسبه مراحل و مي‌شود. ابتدا، مقادير مورد انتظار حالا از مؤلفه‌هاي مشاهده‌شده از بردار استنباط مي‌شود، به عنوان مثال رويه رابطه (2-44) از برچسب‌هاي شناخته‌شده گرفته مي‌شود:
(2-50)
علاوه بر اين، نياز به محاسبه مقادير مورد انتظار و جانشين کردن آن‌ها، و همچنين ، در M-مرحله براي تخمين مجدد پارامترهاي است. جزئيات بيشتر در مورد داده‌هاي مفقودشده را مي‌توان در [25, 45] يافت. شکل زير شبه کد الگوريتم خوشه‌بندي ترکيبي توسط مدل مخلوط را نشان مي‌دهد. در اين شبه کد، از الگوريتم براي توليد نتايج اوليه استفاده شده است که مي‌توان جاي آن از هر الگوريتم ديگري استفاده کرد.

Begin
for i=1 to H // H – number of clusterings
cluster a dataset k-means(X)
add partition to the ensemble
end
initialize model parameters
do until convergence criterion is satisfied
compute expected values
compute for missing data (if any)
re-estimate parameters
end
index of component of with largest expected value,
return // consensus partition
end
شكل 2-17. زير شبه کد الگوريتم خوشه‌بندي ترکيبي توسط مدل مخلوط

2-۳-2-2. روش مبتني بر ابر گراف
اين روش در [54] معرفي شده است. در روش مبتني بر ابر گراف100، خوشه‏ها با ابر لبه‌هاي101 يک گراف نمايش داده مي‏شوند. رأس‌هاي102 گراف معادل نمونه‏هايي هستند که بايد خوشه‏بندي شوند. مسئله تکه‌تکه کردن اين گراف و ايجاد قسمت متفاوت است که هر قطعه مربوط به يک خوشه مي‌شود. سه نوع الگوريتم متفاوت در اين خانواده وجود دارد که عبارت‌اند از 103، 104 و 105.

شكل 2-18. خوشه‌بندي ترکيبي. تابع توافقي براي ترکيب نتايج خوشه‌بندي () استفاده مي‌شود [54].
جهت توضيح روش‌هاي مبتني بر ابر گراف ابتدا به يک سري از تعاريف پايه مي‌پردازيم. مجموعه‌اي از اشياء، نمونه‌ها يا نقاط است. يک افراز از شي در خوشه را مي‌توان در مجموعه‌ اشياي يا بردار برچسب (که مجموعه اعداد طبيعي است) نشان داد. يک الگوريتم خوشه‌بندي تابعي جهت ارائه بردار برچسب به مجموعه‌اي از اشياء است. شکل (2-18) نشان‌دهنده رويه بنيادي اجراي يک خوشه‌بندي ترکيبي است: يک مجموعه تايي از برچسب‌هاي در برچسب (برچسب توافقي) با استفاده از تابع توافقيترکيب مي‌شوند. بردار ماتريس انتقال با يک بالا نويس در داخل پرانتز نشان داده شده است که براي اين بالا نويس براي بيانگر شماره شاخص است و اين شماره توان آن بردار/ ماتريس انتقال را نشان نمي‌دهد [54].
مرحله اول جهت اجراي روش‌هاي مبتني بر ابر گراف اين است که مجموعه خوشه‌بندي‌ها را به ابر گرافي مناسب تبديل کرد. يک ابر گراف شامل رئوس و ابر لبه‌ها مي‌شود. لبه در گراف عادي دقيقاً دو رأس را به هم وصل مي‌کند. يک ابر لبه به طور کلي همانند يک لبه است که مي‌تواند مجموعه‌اي از رئوس را به هم متصل کند. براي هر برچسب بردار، يک عضو دودويي در ماتريس ايجاد مي‌شود، با يک ستون براي هر خوشه (که حالا با ابر لبه نمايش داده مي‌شود)، شکل (2-19) مثالي از اين روش مي‌باشد [54].

شكل 2-19. نمونه ماتريس، جهت تبديل خوشه‌بندي به ابر گراف [54].
تمام موجوديت‌هاي يک سطر در ماتريس شاخص اعضاي دودويي، اگر مربوط به برچسب شناخته‌شده آن ستون باشد برابر يک و در غير اين صورت برابر با صفر خواهند شد. بلوک چند تيکه‌ي ماتريس، ماتريس مجاورت از يک ابر گراف با رأس و ابر لبه را تعريف مي‌کنند. هر ستون بردار يک ابر لبه را تعريف مي‌کند، که يک نشان مي‌دهد که، رأس متناظر آن سطر بخشي از ابر لبه است و صفر بودن نشان‌دهنده اين است که آن بخشي از ابر لبه نيست. بنابراين ما براي هر يک از خوشه‌ها يک نگاشت به يک ابر لبه و براي مجموعه خوشه‌بندي‌ها يک نگاشت به ابر گراف ارائه کرديم.
2-۳-2-2-1. روش CSPA
با يک ديد کلي، هر دو شي که در يک خوشه باشند داراي شباهت يک خواهند بود و در غير اين صورت مقدار شباهت آن‌ها صفر است. يک ماتريس شباهت براي هر خوشه‌بندي مي‌تواند بر اين اساس ايجاد شود. ميانگين ورودي-هوشمندانه106 از ماتريس تصوير بهتري از بازده کلي دسته‌بندي مجموعه در ماتريس شباهت را نشان مي‌دهد. موجوديت‌هاي، کسري از خوشه‌بندي را نشان مي‌دهد که در آن دو شي عضو يک خوشه مشابه هستند. ماتريس را مي‌توان به صورت يک ضرب ماتريس اسپارس نشان داد. شکل (2-20) حالت عمومي ماتريس شباهت بر اساس خوشه‌بندي را براي مثال شکل (2-19) نشان مي‌دهد.

شكل 2-20. ماتريس شباهت بر اساس خوشه براي مثال شکل (3-5) [54].
با اين روش مي‌توان از ماتريس شباهت براي ايجاد مجدد خوشه از اشياي استفاده کرد. در اين روش براي توليد گراف (رأس = اشيا، وزن لبه = شباهت) از روش که در [38] ارائه شده است به خاطر خواص خيلي قوي و مقياس‌پذير آن، استفاده شده است. روش يکي از ساده‌ترين روش‌هاي مکاشفه‌اي107 جهت ادغام نتايج خوشه‌بندي است ولي پيچيدگي محاسبه و ذخيره‌سازي آن هر دو برابر با درجه دوم است که اين امر در ساير روش‌هاي ابر گراف‌ها نزديک با مقدار خطي است.
2-۳-2-2-2. روش HGPA
در اين روش با فرموله کردن افرازبندي ابر گراف توسط قطع حداقل ابر لبه‌ها اقدام به خوشه‌بندي ترکيبي مي‌کنيم. اين روش الگوريتم افرازبندي ابر گراف () ناميده مي‌شود. در اين روش تمام ابر لبه‌ها و رئوس داراي وزن يکسان مي‌باشد. بايد توجه داشته باشيد که اين راه حل شامل روابط طرفه خواهد شد در صورتي که روش تنها شامل روابط دو به دو مي‌باشد.

شكل 2-21. الگوريتم افرازبندي ابر گراف [54].
حال، همانند شکل (2-21) ما به دنبال جداسازي ابر لبه‌ها براي افرازبندي تايي ابر گراف به مؤلفه‌هاي غير متصل و تقريباً هم سايز هستيم. بايد توجه داشت که اخذ اندازه قابل‌مقايسه افرازها در افرازبندي گراف‌هايي که بر اساس خوشه‌بندي به دست آمده‌اند يک رويکرد استاندارد جهت اجتناب از افرازبندي‌هاي بي‌اهميت است [41]. از طرف ديگر معناي اين تعريف ، اين است که اگر خوشه‌هاي داده طبيعي بسيار نامتعادل باشد، يک رويکرد افرازبندي بر اساس گراف مناسب نخواهد بود. در [54] حداکثر عدم تعادل را با حفظ محدوديت فرض کرده‌اند. افرازبندي ابر گراف‌ها در سال‌هاي اخير يکي از بهترين حوزه‌هاي تحقيقاتي بوده است که مي‌توان جزئيات برخي از اين الگوريتم‌ها را در [38, 65] پيدا کرد. در [54] براي افرازبندي روش را پيشنهاد شده است [41] دليل اين کار کيفيت بالا افرازبندي و مقياس‌پذيري روش مي‌باشد. با اين حال، بايد يادآور شد که افرازبندي ابر گراف‌ها به طور کلي داراي هيچ شرايط و قانون خاصي جهت حذف بخشي از ابر لبه‌ها نيست. اين بدان معني است که هيچ حساسيتي جهت وجود تعداد ابر لبه‌ها در يک گروه مشابه بعد از برش وجود ندارد. اين براي کاربردهاي ما مي‌تواند مشکل‌ساز باشد اين مسئله را در داده شکل (2-19) مي‌توان شرح داد. براي سادگي کار، اجازه دهيد تا فقط سه ابر لبه براي فرض کنيم. دو افرازبندي و هر دو با برش سه ابر لبه ايجاد مي‌شود. افرازبندي اول به طور مستقيم بهتر است، به خاطر اينکه از ابر لبه باقي خواهند ماند ولي در روش دوم اين مقدار به کاهش پيدا مي‌کند. از اين روي، در افرازبندي مبتني بر ابر گراف استاندارد براي تعادل در کيفيت را در حذف هر دو ابر لبه مشابه در نظر مي‌گيريم.
2-۳-2-2-3. روش MCLA
الگوريتم فرا خوشه‌بندي () يکي از بهترين روش‌ها در خوشه ترکيبي مبتني بر ابر گراف است [54]. ايده اصلي الگوريتم فرا خوشه‌بندي بر اساس گروه‌بندي و جداسازي روابط ابر لبه‌ها و تخصيص هر شي به ابر لبه جدا شده است که در آن اين مشارکت قوياً ديده مي‌شود. ابر لبه‌هاي مرتبط در نظر گرفته‌شده براي جداسازي توسط خوشه‌بندي مبتني بر گراف از ابر لبه‌ها معين مي‌شوند. هر خوشه از ابر لبه‌ها به يک ابر خوشه اشاره مي‌کند. جداسازي تعداد ابر لبه‌ها را از به کاهش مي‌دهد. مراحل اجراي الگوريتم فرا خوشه‌بندي به شرح زير است:
ساخت ابر گراف به عنوان يک گراف بدون جهت ديگر تمام را با نمايش مي‌دهيم (ابر گراف‌هاي)، که آن را فرا گراف مي‌ناميم. وزن لبه‌ها را متناسب به شباهت بين رئوس در نظر مي‌گيريم. در اينجا معيار جاکارت108 يکي از مناسب‌ترين معيارها براي اندازه‌گيري شباهت هست، از آنجا که آن نسبت بين اشتراک و اجتماع مجموعه‌اي از اشياء مربوط به دو ابر لبه را نشان مي‌دهد. به عبارت ديگر، وزن لبه بين دو رأس و با معيار جاکارت دودويي مطابق رابطه (2-51) تعريف مي‌شود.
(2-51)
تا زماني که خوشه‌ها هم پوشاني (خيلي زياد) نداشته باشند، هيچ لبه‌اي ميان رئوس خوشه‌بندي مشابه وجود نخواهد داشت و بنابراين، فرا گراف بخشي خواهد بود. شکل (2-22) الگوريتم فرا خوشه‌بندي مثال شکل (2-19) است.

شكل 2-22. الگوريتم فرا خوشه‌بندي
خوشه ابر لبه‌ها109 در اين مرحله ما به دنبال پيدا کردن برچسب‌هاي سازگار در افرازبندي فرا گراف بهفرا خوشه متعادل هستيم. براي اين کار [54] روش را پيشنهاد کرده است. اين نتايج در يک خوشه‌بندي از برداهاي است. هر فرا خوشه تقريباً رأس دارد. از آنجايي که هر رأس در فرا خوشه نشان‌دهنده يک برچسب خوشه متمايز است، يک فرا خوشه نشان‌دهنده يک گروه از برچسب‌هاي متناظر است.
جداسازي فرا خوشه110 براي هر يک از فرا خوشه‌، ابر لبه‌ها براي تبديل به يک فرا لبه جداسازي مي‌شود. هر فرا لبه داراي يک بردار تجمع است که شامل يک ورودي براي هر شي است که سطح تجمع ارتباط فرا خوشه را شرح مي‌دهد. اين سطح برابر با ميانگين تمام شاخص‌هاي بردار از يک فرا خوشه خاص است. هر ورودي صفر و يک به ترتيب نشان‌دهنده قويي‌ترين و ضعيف‌ترين تجمع است.
تخصيص اشياء111 در اين مرحله، هر شي به فرا خوشه‌اي که بيشتر با آن در ارتباط است تخصيص داده مي‌شود: به طور خاص، يک شي به فرا خوشه‌اي که بالاترين ورودي را در بردار اجماع دارد تخصيص داده مي‌شود. روابط به صورت تصادفي شکسته مي‌شوند. اطمينان از يک تخصيص، در سهم برنده اجماع منعکس مي‌شود (نسبت سهم برنده اجماع به جمع همه اجماع‌هاي ديگر). بايد توجه داشت که براي هر فرا خوشه نمي‌توان تضمين داد که حداقل برنده يک شي شود. بنابراين، بيشتر از برچسب در ترکيب نهايي خوشه‌بندي وجود دارد.
شکل (2-22) نشان‌دهنده فرا خوشه مثال شکل (2-19) است که در آن، ، و مي‌باشد. شکل (2-22) نشان‌دهنده يک فرا خوشه با چهار قسمت اصلي است. سه فرا خوشه توسط سمبل‌هاي، و نشان داده

پایان نامه
Previous Entries منابع و ماخذ پایان نامه سلسله مراتب Next Entries منابع و ماخذ پایان نامه سلسله مراتب