شکل ۲-۱۱. خوشه‌بندی کاهشی
۲-۲-۱-۲-۵. الگوریتم خوشه‌بندی Median K-Flat
الگوریتم Median K-Flat یا به اختصار MKF مجموعه داده‌ی  را به K خوشه‌ی  افراز می‌کند که هر خوشه یک شبه فضای^[۵۸] d-بُعدی تقریباً خطی می‌باشد. پارامتر‌  با فرض  ماتریسی با ابعاد  می‌باشد، که هر یک از خانه‌های آن تخمین شبه فضای خطی متعامد^[۵۹]  می‌باشد. قابل به ذکر است که  می‌باشد. در این جا تخمین شبه فضای خوشه‌های  را  نام‌گذاری می‌کنیم. مطابق تعاریف بالا تابع انرژی برای افرازهای ‌  بر اساس شبه فضای  به شکل زیر تعریف می‌شود [۷۷].

( اینجا فقط تکه ای از متن فایل پایان نامه درج شده است. برای خرید متن کامل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. )

(۲-۱۳)
این الگوریتم سعی می‌کند تا مجموعه داده را به خوشه‌های  ‌تبدیل کند به نحوی که تابع انرژی کمینه باشد. تا وقتی که سطوح تخت اساسی^[۶۰] به شکل شبه فضای خطی هستند ما می‌توانیم به صورت فرضی المان‌های X را در یک حوضه واحد نرمال کنیم به طوری که  برای  و تابع انرژی را به شکل زیر بیان کنیم: [۷۷]
(۲-۱۴)
این الگوریتم برای کمینه‌سازی تابع انرژی الگوریتمMKF از روش کاهش گرادیان تصادفی استفاده می‌کند. مشتق تابع انرژی بر اساس ماتریس  به شرح زیر است:
(۲-۱۵)
این الگوریتم نیاز به تطبیق  بر اساس مؤلفه‌ی متعامد مشتق  دارد. بخشی از مشتق که با شبه فضای  موازی است به شرح زیر می‌باشد.
(۲-۱۶)
از این روی مؤلفه متعامد برابر است با رابطه ۲-۱۷ می‌باشد.
(۲-۱۷)
در رابطه بالا  برابر با رابطه ۲-۱۸ است.
(۲-۱۸)
با در نظر گرفتن محاسبات بالا، الگوریتم MKF تصمیم می‌گیرد که داده تصادفی  از مجموعه داده، عضو کدام  باشد، و از این طریق شروع به چیدن داده‌ها می‌کند. آن گاه، الگوریتم تابع  را به‌روز کند که در آن  (مرحله زمانی) پارامتری است که توسط کاربر تعیین می‌شود. این فرایند آن قدر تکرار می‌شود تا ضابطه همگرایی دیده شود. آنگاه هر نقطه از مجموعه داده به نزدیک‌ترین شبه فضای  که تعیین‌کننده خوشه‌هاست اختصاص داده می‌شود. شبه کد زیر فرایند الگوریتم MKF را نشان می‌دهد [۷۷].

Input:
: Data, normalized onto the unit sphere, d: dimension of subspaces K: number of subspaces,  the initialized subspaces.  : step parameter.
Output: A partition of X into K disjoint clusters
Steps:
۱. Pick a random point  in X
۲. Find its closest subspace  , where
۳. Compute  by
۴. Update
۵. Orthogonalize
۶. Repeat steps 1-5 until convergence
۷. Assign each xi to the nearest subspace

شکل ۲-۱۲. شبه‌کد الگوریتم MKF [77]
۲-۲-۱-۲-۶. الگوریتم خوشه‌بندی مخلوط گوسی
یک مخلوط گوسی^[۶۱] یا همان  را می‌توان ترکیب محدبی^[۶۲] از چگالی‌های گوسی دانست. یک چگالی گوسی در فضای d-بُعدی به ازای میانگین  ، توسط ماتریس هم‌وردایی^[۶۳]  با ابعاد  به صورت زیر تعریف می‌شود: [۸۳]
(۲-۱۹)
در رابطه بالا  پارامتر‌های  و  را تعریف می‌کند. از این روی  مؤلفه  به صورت زیر تعریف می‌شود:
(۲-۲۰)
در رابطه (۲-۲۰) پارامتر  وزن مخلوط کردن^[۶۴] و  مؤلفه مخلوط می‌باشد. از آنجا که در مقایسه با تخمین چگالی غیر پارامتری، تعداد کمتری از توابع چگالی در تخمین چگالی مخلوط باید ارزیابی شود، از این روی ارزیابی چگالی کارآمدتر خواهد بود. علاوه بر آن، استفاده از اجرای محدودیت هموار کردن^[۶۵] بر روی برخی از مؤلفه‌های مخلوط در نتیجه‌ی چگالی به ما اجازه می‌دهد تا چگالی مستحکم‌تری را تخمین بزنیم. الگوریتم حداکثر-انتظار^[۶۶] یا همان  به ما اجازه به‌روز کردن پارامتر‌های  مؤلفه‌ی مخلوط را مطابق با مجموعه داده  به ازای هر  می‌دهد، به طوری که احتمال  هرگز کوچک‌تر از مخلوط جدید نشود. به‌روز کردن الگوریتم می‌تواند در یک فرایند تکراری برای تمامی مؤلفه‌های  مطابق با رابطه‌های زیر انجام شود: [۸۳]
(۲-۲۱)
(۲-۲۲)
(۲-۲۳)
(۲-۲۴)
در این تحقیق از روش پیشنهادی بومن و همکاران^[۶۷] برای پیاده‌سازی الگوریتم مخلوط گوسی استفاده شده است. از آنجایی که روش پیاده‌سازی و توضیحات مربوط به الگوریتم مخلوط گوسی در روش ترکیب مبتنی بر مخلوط استفاده می‌شود از این روی در بخش روش‌های ترکیب نتایج با تابع توافقی آن را بررسی خواهیم کرد.
۲-۲-۲. معیارهای ارزیابی
در یادگیری با ناظر^[۶۸] ارزیابی راحت تر از یادگیری بدون ناظر است. برای مثال آن چیز که ما در رده‌بندی^[۶۹] باید ارزیابی کنیم مدلی است که ما توسط داده‌های^[۷۰] یادگیری به الگوریتم هوش مصنوعی^[۷۱] آموزش^[۷۲] داده‌ایم. در روش‌های با ناظر ورودی و خروجی داده معلوم است و ما بخشی از کل داده را برای آزمون جدا کرده و بخش دیگر را به عنوان داده یادگیری استفاده می‌کنیم و پس از تولید مدل مطلوب ورودی داده آزمون^[۷۳] را در مدل وارد کرده و خروجی مدل را با خروجی واقعی می‌سنجیم^[۷۴]. از این روی معیارهای بسیاری برای ارزیابی روش‌های با ناظر ارائه‌شده‌اند.
در یادگیری بدون ناظر روش متفاوت است. در این روش هیچ شاخص معینی در داده جهت ارزیابی وجود ندارد و ما به دنبال دسته‌بندی کردن داده‌ها بر اساس شباهت‌ها و تفاوت‌ها هستیم. از این روی برخلاف تلاش‌های خیلی از محققان، ارزیابی خوشه‌بندی خیلی توسعه داده نشده است و به عنوان بخشی از تحلیل خوشه‌بندی رایج نشده است. در واقع، ارزیابی خوشه‌بندی یکی از سخت‌ترین بخش‌های تحلیل خوشه‌بندی است [۳۳]. معیارهای عددی، یا شاخص‌هایی که برای قضاوت جنبه‌های مختلف اعتبار یک خوشه به کار می روند، به سه دسته کلی تقسیم می‌شوند: