وبلاگ

شکل۳-۱۵. پیاده‌سازی شرط کامل
شکل۳-۱۶. پیاده‌سازی شرط‌ تو در تو
شکل۳-۱۷. پیاده‌سازی یک شرط کامل در یک شرط ساده
شکل۳-۱۸. پیاده‌سازی یک شرط کامل در یک شرط کامل دیگر
شکل۳-۱۹. پیاده‌سازی حلقه ساده
شکل۳-۲۰. پیاده‌سازی یک حلقه ساده داخل حلقه‌ای دیگر
شکل۳-۲۱. پیاده‌سازی یک حلقه داخل یک شرط کامل
شکل۳-۲۲. پیاده‌سازی یک شرط کامل داخل یک حلقه ساده
در ادامه به بررسی روش ارزیابی گراف استقلال برای محاسبه درجه استقلال دو الگوریتم می‌پردازیم.

۳-۴-۲-۳. ارزیابی گراف استقلال الگوریتم
ابتدا برای ارزیابی درجه استقلال دو الگوریتم به معرفی روشی جهت ذخیره‌سازی گراف آن می‌پردازیم. همان‌گونه که در مثال‌های ذکرشده مشاهده می‌شود همیشه یال‌هایی بدون وزن در گراف وجود دارند که صرفاً برای نمایش عملکرد کامل گراف به‌کاربرده می‌شوند و در امر ارزیابی نیاز به ذخیره آن‌ها نیست لذا برای ذخیره گراف در حافظه از ذخیره‌سازی آن‌ها صرف‌نظر خواهیم کرد تا هم حجم حافظه بهینه استفاده شود و هم سرعت اجرای مقایسه افزایش یابد. در این تحقیق برای ذخیره هر گراف در حافظه از آرایه‌ای به اندازه تمامی یال‌های وزن‌دار آن استفاده می‌شود که وزن هر یال (که می‌تواند شامل چندین خط از نماد‌های جدول نگاشت استاندارد باشد) در یک خانه منحصربه‌فرد ذخیره می‌شود. برای ارزیابی گراف استقلال دو الگوریتم کافی است آرایه‌های آن دو الگوریتم را باهم مقایسه کنیم. جهت ارزیابی آرایه‌های دو الگوریتم، ماتریسی با عنوان ماتریس درجه وابستگی‌ کد^[۱۷۷] یا CDDM را همانند شکل ۳-۲۳ طوری فرض می‌کنیم که هر خانه آن مقایسه‌ای از وزن‌ یال‌های گراف الگوریتم اول باهر کدام از وزن‌ یال‌های گراف الگوریتم دوم باشد.

شکل۳-۲۳. ماتریس درجه وابستگی‌ کد
در شکل ۳-۲۳ متغیر n تعداد خانه‌های آرایه الگوریتم اول و متغیر m تعداد خانه‌های آرایه الگوریتم دوم می‌باشد. مقادیر خانه‌های ماتریس بر اساس رابطه ۳-۷ محاسبه می‌شود.
(۳-۷)
در رابطه ۳-۷ متغیرهای i و j شماره سطر و ستون ماتریس شکل ۳-۲۳ می‌باشند و تابع  بر اساس شبه کد ۳-۲۴ محتوای دو خانه از آرایه‌ها را باهم مقایسه می‌کند.
Function Compare (Cell1, Cell2) Return [CDD]
Count = 0
While we have Symbol in Cell1
Sym1 = Select an Symbol in Cell1
Foreach Sym2 in Cell2
If Sym2 = Sym1 is found then
Count++
Break
End If
End Foreach
End while
MSymbol = Max-Sym (Cell1, Cell2)
Result = Count / MSymbol
شکل۳-۲۴. شبه کد مقایسه محتوای دو خانه از آرایه‌های استقلال الگوریتم
در شکل ۳-۲۴ به ازای هر نماد در هر خانه از آرایه اول به دنبال اولین نماد عیناً مشابه در خانه‌ی آرایه دوم می‌گردد و تعداد نماد‌های مشابه را می‌شمارد. در نهایت جهت نرمال سازی درجه استقلال بین صفر و یک تعداد نماد‌های مشابه را بر مقدار بیشینه تعداد نماد‌های موجود بین خانه اول و دوم تقسیم می‌کند. همان طور که در تعریف شکل ۳-۲۴ نشان داده شده است مقدار به دست آمده از تابع  را با عنوان درجه وابستگی هر خانه^[۱۷۸] یا همان CDD می‌شناسیم.
جهت به دست آوردن مقدار استقلال الگوریتم بر اساس ماتریس وابستگی، فرض می‌کنیم که ماتریس فعلی ماتریس مرحله اول یا همان  نام دارد. در این ماتریس خانه‌ای را پیداکرده که بیش‌ترین مقدار را دارد که ما مقدار آن را به متغیر  تخصیص می‌دهیم. با حذف سطر و ستونی که خانه بیشینه در آن قرار دارد ماتریس  را می‌سازیم و به طریق مشابه خانه‌ای که در آن بیش‌ترین مقدار وجود دارد در  نگهداری کرده و سطر و ستون خانه بیشینه را حذف می‌کنیم تا ماتریس مرحله بعد ساخته شود. این کار را به تعداد n بار می‌توان انجام داد که n حداقل تعداد خانه‌های دورآرایه‌ی الگوریتم اول و دوم می‌باشد. بر اساس تعریف بالا درجه استقلال الگوریتم مطابق با رابطه ۳-۸ محاسبه می‌شود.
(۳-۸)
در رابطه ۳-۸ نمادهای Alg1 و Alg2 به ترتیب نشان دهند آرایه‌های الگوریتم اول و دوم می‌باشد و متغیر m حداکثر تعداد بین خانه‌های آرایه‌های الگوریتم اول و دوم است. طبق این رابطه درجه استقلال دو الگوریتم برابر تفاضل یک از میانگین خانه‌های بیشینه در ماتریس‌های درجه وابستگی کد در مراحل بالا است که جهت نرمال سازی بین صفر و یک بر m تقسیم شده است. از این پس درجه استقلال الگوریتم^[۱۷۹] را با عنوان AID می‌شناسیم.
۳-۴-۳. چهارچوب خوشه‌بندی خردمند مبتنی بر گراف استقلال الگوریتم
شکل۳-۲۵. چهارچوب خوشه‌بندی خردمند مبتنی بر گراف استقلال الگوریتم
همان طور که پیش‌تر به آن اشاره شد در روش پیشنهادی دوم این مقاله استقلال الگوریتم به عنوان وزنی برای ترکیب نتایج نهایی استفاده خواهد شد لذا در شکل ۳-۲۵ بخش ارزیابی استقلال حذف‌شده و پس از ارزیابی پراکندگی هر الگوریتم آن را در مجمع خردمند ذخیره می‌کنیم. در اصل اینجا مجمع خردمند شامل نتایج ارزیابی‌شده (نسبت به پراکندگی) به همراه درجه استقلال آن نتایج (احتمال درستی آن‌ها نسبت به هم) به عنوان وزن جهت ترکیب می‌باشند. همان‌گونه که در شکل نشان داده شده است این چهارچوب نیز غیرمتمرکز بوده و تمامی قوانینی که در بخش عدم تمرکز و ارزیابی پراکندگی در روش اول به آن اشاره شد در اینجا نیز صدق خواهد کرد. از این روی در این بخش تنها به تشریح روش ارزیابی استقلال بر اساس روش مبتنی بر گراف و همچنین روش ترکیب نتایج جمع‌ آوری شده در مجمع خردمند به صورت وزن‌دار بسنده می‌کنیم.
۳-۴-۳-۱. ارزیابی استقلال الگوریتم
مطابق شکل ۳-۲۵ نتایج ارزیابی درجه استقلال الگوریتم‌ها در ماتریس AIDM نگهداری می‌شود. اندازه این ماتریس  است که n تعداد الگوریتم‌هایی هستند که قرار است در خوشه‌بندی شرکت کنند. روش محاسبه سطر و ستون این ماتریس طبق رابطه ۳-۹ محاسبه می‌شود:
(۳-۹)
رابطه ۳-۹ توضیح می‌دهد که اگر دو الگوریتم غیر هم نام باشد مطابق با رابطه ۳-۸ درجه استقلال آن‌ها محاسبه می‌شود، و اگر دو الگوریتم هم نام باشد چون باید همانند روش اول با در نظر گرفتن پارامترهای اساسی آن دو الگوریتم مطابق شبه کد شکل ۳-۲ به محاسبه درجه استقلال ‌بپردازیم درجه استقلال آن را در این ماتریس منفی یک در نظر می‌گیریم تا پس از تولید پارامترهای اساسی حین اجرای الگوریتم به محاسبه آن بپردازیم. در این حالت استقلال الگوریتم هم در سطح عملکرد الگوریتم و هم در سطح پارامتر‌های اساسی الگوریتم در نظر گرفته می‌شود. در شکل ۳-۲۵ پس از اتمام کار انتخاب خوشه‌ها و تشکیل جامعه خردمند، درجه استقلال نهایی برای هر الگوریتم خوشه‌بندی برابر با میانگین مجموع درجه‌های استقلال آن الگوریتم نسبت به الگوریتم‌های غیر هم نام و پارامتر‌های اساسی الگوریتم‌های هم نام می‌باشد. رابطه ۳-۱۰ روش محاسبه درجه استقلال نهایی هر الگوریتم را‌ در حین اجرا نشان می‌دهد:
(۳-۱۰)
در این رابطه Alg_i نشان‌دهنده الگوریتمی است که قرار است درجه استقلال نهایی آن محاسبه شود و WisedCrowd جامعه خردمند و یا همان نتایج اولیه انتخاب‌شده می‌باشد و n تعداد الگوریتم‌های غیر هم ‌نام و m تعداد الگوریتم‌های هم ‌نام با این الگوریتم در جامعه خردمند می‌باشد. در این رابطه به ازای هر الگوریتم غیر هم نام درجه استقلال آن نسبت به الگوریتم از ماتریس AIDM خواند می‌شود و به ازای هر الگوریتم هم نام درجه استقلال آن نسبت به الگوریتم بر اساس پارامتر‌های اساسی الگوریتم که حین اجرا تولید می‌شوند با بهره گرفتن از تابع BPI محاسبه می‌شود. بدیهی است که AI همواره مقداری بین صفر و یک خواهد داشت چون از میانگین اعدادی که همیشه بین صفر و یک هستند به دست می‌آید. همچنین جهت استفاده از درجه استقلال نهایی به دست آمده به عنوان وزن در ترکیب نتایج اولیه آن‌ها را در ماتریسی با عنوان ماتریس استقلال الگوریتم‌ها^[۱۸۰] یا همان AIM نگهداری می‌کنیم. قابل‌ذکر است که این ماتریس فقط و فقط استقلال نهایی الگوریتم‌هایی که موفق به ورود به جامعه خردمند شده‌اند را نگهداری می‌کند و نه تمام الگوریتم‌هایی که در تشکیل نتایج اولیه خوشه‌بندی ترکیبی نقش داشته‌اند.
۳-۴-۳-۲. روش انباشت مدارک وزن‌دار
در سال‌های اخیر بسیاری از مقالات جهت ترکیب نتایج خوشه‌بندی از روش انباشت مدارک به خاطر کالایی بالای آن استفاده کرده‌اند [۸, ۹, ۱۹, ۲۱, ۶۷]. در این روش برای ترکیب نتایج از رابطـه ۲-۵۶ استفاده می‌شود. همان طور که پیش‌تر ذکر شد در این رابطه پارامتر  تعداد دفعاتی است که جفت نمونه‌های  و  باهم در یک خوشه گروه‌بندی شده‌اند و همچنین  تعداد نمونه‌برداری‌هایی است که هر دوی این جفت نمونه‌ها به طور همزمان در آن ظاهرشده‌اند. با توجه به نحوه محاسبه پارامتر  می‌توان گفت شمارش تعداد نمونه‌ها یعنی هر نتیجه با وزن مساوی و برابر با یک در جواب نهایی شرکت می‌کند. در این تحقیق دیدگاه جدیدی در مورد رابطه ۲-۵۶ مطرح خواهد شد که در آن قرار است درجه نهایی استقلال هر الگوریتم به عنوان وزنی برای احتمال درستی هر نتیجه در نظر گرفته شود. از این روی از رابطه ۳-۱۱ که ما آن را با عنوان روش انباشت مدارک وزن‌دار^[۱۸۱] یا همان  نام‌گذاری کرده‌ایم برای ترکیب نتایج استفاده خواهیم کرد.
(۳-۱۱)
در رابطه ۳-۱۱ متغیر  نشان‌دهنده ماتریس درجه استقلال الگوریتم می‌باشد و  تعداد دفعاتی است که جفت نمونه‌های  و  باهم در یک خوشه گروه‌بندی شده‌اند و تابع res مقدار مربوط به نمونه  -ام (که این مقدار برابر با مقدار نمونه  -ام نیز است) را از نتایج اولیه خوشه‌بندی بر می‌گرداند و  شماره‌ی الگوریتمی که دو نمونه  و  را تولید کرده است بر می‌گرداند که متناسب با آن درجه استقلال نهایی آن الگوریتم از ماتریس AIM خوانده خواهد شد. همچنین در این رابطه  تعداد نمونه‌برداری‌هایی است که هر دوی این جفت نمونه‌ها به طور همزمان در آن ظاهرشده‌اند.
۳-۴-۳-۳. شبه کد خوشه‌بندی خردمند مبتنی بر گراف استقلال الگوریتم
همان طور که پیش‌تر اشاره شد شکل ۳-۲۵ چهارچوب روش پیشنهادی دوم این تحقیق را ارائه می‌دهد. این فرایند با تولید نتایج اولیه شروع می‌شود و در ادامه با ارزیابی پراکندگی و وزن‌های به دست آمده از ماتریس استقلال الگوریتم اقدام به تولید جامعه خردمند می‌کنیم. در نهایت با بهره گرفتن از روش انباشت مدارک وزن‌دار افرازهای جمع‌ آوری شده در جامعه خردمند با یکدیگر ادغام‌شده و نتیجه نهایی را تولید می‌کند. شکل ۳-۲۶ نشان‌دهنده شبه کد روش پیشنهادی دوم است.