کلیه مطالب این سایت فاقد اعتبار و از رده خارج است. تعطیل کامل

روش پیشنهادی دوم این تحقیق سعی دارد تا دو بخش از روش اول را بهبود بخشد. این روش در ابتدا این ایده را بررسی می‌کند که الگوریتم‌های غیر هم نام کاملاً مستقل نیستند. در این راستای برای محاسبه درجه استقلال دو الگوریتم با بهره گرفتن از ایده تبدیل کد به گراف در تست نرم‌افزار به ارائه روشی با عنوان مدل‌سازی گراف استقلال الگوریتم می‌پردازیم. با مقایسه گراف‌های به دست آمده (درجه استقلال) در این روش می‌توان یک وزن برای احتمال صحت جواب‌های به دست آمده پیشنهاد داد. از این روی در این روش به جای ارزیابی و آستانه‌گیری از استقلال الگوریتم‌ها، آن‌ها را به عنوان وزنی برای ترکیب نتایج در نظر می‌گیریم بدین وسیله نیاز به آستانه‌گیری برای استقلال الگوریتم‌ها از بین می‌رود. جهت ترکیب نتایج اولیه در این روش رابطه‌ای جدید بر اســاس رابطـه ۲-۵۶ با عنوان روش انباشت مدارک وزن‌دار یا به اختصار ^[۱۶۹]WEAC معرفی می‌شود.

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

۳-۴-۱. بررسی مکانیزم حل مسائل توسط الگوریتم‌های خوشه‌بندی
در سال‌های اخیر دسته‌بندی‌های زیادی برای الگوریتم‌های خوشه‌بندی در کتب‌ و مقالات مختلف ارائه شده است [۳۷, ۶۸, ۷۱, ۷۲, ۷۳]. یکی از دیدگاه‌های غالب در این بحث روشی است که توسط جین و همکاران [۳۷] پیشنهاد شده است. در این روش، دسته‌بندی الگوریتم‌ها بر اساس تابع هدف^[۱۷۰] الگوریتم‌ها صورت می‌گیرد. شکل ۳-۵ دسته‌بندی پیشنهادشده توسط جین و همکاران را نشان می‌دهد.
شکل۳-۵. دسته‌بندی الگوریتم‌های خوشه‌بندی [۳۷].
نتایج تجربی جین و همکاران نشان می‌دهد که روش عملکرد هر دسته از الگوریتم‌های خوشه‌بندی که در یک گروه قرار دارند (دارای تابع ‌هدف مشابه هستند) بر روی یک سری داده‌های خاص تقریباً یکسان است [۳۷]. از طرف دیگر، می‌توان بسیاری از الگوریتم‌های خوشه‌بندی را یافت که روشی توسعه‌یافته‌ از روی یک الگوریتم پایه می‌باشند. شاید معروف‌ترین مثال‌هایی که بتوان از این‌گونه الگوریتم‌ها نام برد الگوریتم‌های سری  می‌باشند که جین [۷۴] پنجاه سال تکامل و انواع آن را بررسی کرده است و یا سری الگوریتم‌های پیوندی که ما پیش‌تر به چند نمونه از آن اشاره‌کرده‌ایم. در بیشتر این سری از الگوریتم‌ها فرایند کلی حل مسئله ثابت است و تنها بخشی از الگوریتم اضافه، تغییر، حذف و یا بهبود داده ‌شده است. از این روی با توجه به این رابطه خاص بین برخی از انواع الگوریتم‌ها روش پیشنهادی دوم این تحقیق فرآیندی را برای مدل‌سازی شیوه کار الگوریتم‌های خوشه‌بندی پیشنهاد می‌دهد تا بر اساس آن استقلال و یا وابستگی الگوریتم‌های خوشه‌بندی به نحوی دقیق‌تر از روش پیشنهادی اول، جهت کنترل تأثیرات آن‌ها بر روی تولید نتایج اولیه خوشه‌بندی ترکیبی مورد توجه قرار گیرند.
برای ارزیابی و سنجش درجه استقلال و یا وابستگی الگوریتم‌های خوشه‌بندی ابتدا نیاز است آن‌ها را مدل‌سازی کنیم. این مدل‌سازی باید بر شیوه‌ای استوار باشد که بتوان فقط و فقط عواملی که بر استقلال و یا وابستگی یک الگوریتم تأثیر دارند همانند شیوه کار الگوریتم، مولد‌های اعداد تصادفی، روابط ریاضی، توابع مکاشفه‌ای و غیره را بتوان بدون کمترین تأثیری از سایر بخش‌های غیر مرتبط همانند کدهای ورودی، خروجی و نمایش و غیره مدل‌سازی کند. در این تحقیق بر اساس ایده روش مدل‌سازی کد برنامه به گراف که در تست نرم‌افزار^[۱۷۱] استفاده می‌شود روشی جهت مدل‌سازی فرایند کار الگوریتم برای ارزیابی استقلال پیشنهاد می‌شود که ما آن را با عنوان “مدل‌سازی گراف استقلال الگوریتم” می‌شناسیم. در ادامه به بررسی این روش خواهیم پرداخت.
۳-۴-۲. مدل‌سازی گراف استقلال الگوریتم
تست نرم افزا یکی از مهم‌ترین بخش‌های ساخت نرم‌افزار می‌باشد که تقریباً شصت درصد از کل هزینه تولید یک نرم‌افزار به آن تخصیص داده می‌شود. یکی از روش‌های تست نرم افزا مدل‌سازی نرم‌افزار می‌باشد که به چهار بخش مدل‌های مبتنی بر نَحو^[۱۷۲] کد برنامه، فضای ورودی، منطق عملکرد و گراف تقسیم می‌شود. از بین این روش‌ها، مدل‌سازی مبتنی بر گراف می‌تواند یک دیدگاه نمایش گرافیکی از روی کد منبع، طراحی، مشخصات یا مورد‌های استفاده^[۱۷۳] ارائه دهد از این روی این روش برای بررسی مکانیزم کار یک الگوریتم بسیار مفید می‌باشد [۷۵]. در این تحقیق ما از مفاهیم و ایده مدل‌سازی مبتنی بر گراف در تست نرم‌افزار جهت محاسبه درجه استقلال الگوریتم‌های خوشه‌بندی استفاده می‌کنیم. قبل از اینکه به تشریح روش ساخت گراف استقلال بپردازیم باید به دو سؤال در ساخت این گراف کمی دقیق‌تر پاسخ داد.
اول، گراف استقلال باید بر اساس چه منبعی ساخته شود؟
برای پاسخ به این سؤال باید یادآور شد که گراف استقلال فرایند روش حل مسئله در الگوریتم خوشه‌بندی را مدل‌سازی می‌کند لیکن باید آن را از روی کد و یا شبه کد پیاده‌سازی الگوریتم ساخت تا بتوان رابطه‌ی بین این کدها را شناسایی کرد و از روی آن‌ها استقلال الگوریتم را ارزیابی کنیم.
دوم، آیا کل کد‌های پیاده‌سازی یک الگوریتم خوشه‌بندی باید در مدل‌سازی بکار رود؟
همان طور که پیش‌تر نیز اشاره شد هر الگوریتم شامل بخش‌هایی برای تهیه‌ی ورودی، خروجی و نمایش داده به کاربر می‌باشد. علاوه بر آن همیشه کد‌های الگوریتم شامل بخش‌هایی برای تعریف متغیرها، ثابت‌ها‌ و غیره هستند که در بیشتر مواقع فایده‌ای برای ارزیابی درجه استقلال ندارند. این موارد در شبه کدها کمتر به چشم می‌خورند ولی با این حال همیشه وجود دارند. از آنجایی که روش پیشنهادی این تحقیق به این تعاریف حساس می‌باشد. از این روی در این تحقیق روشی برای هرس کردن کد و تبدیل آن به قالبی مناسب تشخیص استقلال با عنوان “زبان استقلال الگوریتم‌ خوشه‌بندی^[۱۷۴]” یا به اختصار  پیشنهاد خواهیم کرد.
۳-۴-۲-۱. زبان استقلال الگوریتم‌ خوشه‌بندی
در زبان استقلال الگوریتم‌ خوشه‌بندی به جای استفاده از کد یا شبه کد الگوریتم‌ها از نماد‌هایی توافقی استفاده ‌می‌شود. مهمترین دلایل این کار را می‌توان موارد ذیل دانست. اولا، از آن جایی که معمولاً کد‌ها و یا شبه کدها به زبان استانداردی نوشته نمی‌شوند لذا برای مقایسه باید تمامی آن‌ها را به یک شکل همگن کرد. علاوه بر آن چون در بسیاری از موارد معادلات ریاضی و شبه کدها در مقالات واضح بیان نمی‌شوند اگر قرار باشد بر اساس آن‌ها به مدل‌سازی یک الگوریتم بپردازیم باید به شیوه‌ای عمل کنیم تا حساسیت به جزئیات پیاده‌سازی کم شود. در این تحقیق پس از طی یک سری فرایند استاندارد تمامی کدها به کدی استاندارد برای ارزیابی استقلال تبدیل می‌شود. این فرایند به شرح زیر است:
۱- ابتدا تمامی کد‌های اضافی از جمله تعریف متغیرها و ثابت‌ها، توضیحات اضافی، دستورات مربوط به ورودی، خروجی و نمایش اطلاعات، تمامی دستورات مربوط به کنترل حلقه‌ها و شروط در صورتی که تغییری در شرایط اجرای الگوریتم ایجاد نکنند و سایر کد‌هایی که در فرایند خوشه‌بندی داده نقشی ندارند را حذف می‌کنیم. برای مثال در صورتی که پیاده‌سازی تابعی خاص که در کد اصلی از آن استفاده شده است همانند معیار‌های ارزیابی همچون NMI و یا APMM و غیره در کد اصلی وجود داشته باشد پیاده‌سازی آن را حذف می‌کنیم چون در نماد گزاری به راحتی می‌توان کل آن را با یک نماد توافقی نشان داد.
۲- چون بخش منطقی عملگر‌های شرطی و حلقه‌ها تأثیری در شکل گراف نمی‌گذارند آن‌ها را حذف می‌کنیم.
۳- با حذف بخش منطقی عملگر‌های شرطی و حلقه‌ها استفاده از انواع عملگر شرطی‌ (همانند If، elsif، case و غیره) و همچنین به‌کارگیری انواع عملگر حلقه (همانند حلقه‌های for، while و غیره) نیاز نیست. قابل به ذکر است که کلیه این دستورات برای تسریع سرعت پیاده‌سازی کد الگوریتم توسط برنامه‌نویس به کار می‌روند ولی در نهایت همگی آن‌ها جزئی از دو گروه عملگر‌های شرطی و حلقه‌ها می‌باشند. چون در مدل‌سازی الگوریتم فرایند کار الگوریتم مدل‌ می‌شود و نه نحوه پیاده‌سازی تک‌تک کدها، از این روی دستور بکار رفته در کد اهمیتی ندارند بلکه فقط و فقط ماهیت آن‌ها مهم می‌‌باشد. در نتیجه این تحقیق پیشنهاد می‌کند برای سادگی مدل تنها از یک دستور قراردادی به عنوان عملگر شرط و یک دستور قراردادی برای عملگر حلقه استفاده کنیم. این تحقیق برای هر نوع شرطی از نماد‌های If Else End و برای هر نوع حلقه‌ای‌ از نماد‌های While Break End استفاده می‌کند.
۴- به منظور سادگی و همگن کردن کد‌ها و همچنین تسریع در عمل مقایسه و ارزیابی آن‌ها در این تحقیق از جدولی قراردادی برای تبدیل کد‌های اصلی به کد‌های استاندارد استفاده می‌شود. این جدول که ما آن را با عنوان “جدول نگاشت استاندارد کد^[۱۷۵]” و یا  می‌شناسیم می‌تواند با حفظ قالب اصلی خود متناسب باهر پیاده‌سازی‌ تهیه شود. در ادامه چند قانون قراردادی را برای تولید این جدول بیان می‌کنیم.
۵- جهت وضوح بیشتر کد تهیه‌شده ابتدای آن با کلمه Begin و انتهای آن با کلمه End معین می‌شود.
به منظور سهولت در انتخاب نماد در جدول نگاشت استاندارد کد، پیشنهاد می‌شود تا دستورات ابتدا گروه‌بندی شده و برای هر دستور در گروه منحصربه‌فرد آن یک برچسب عددی در نظر گرفته شود. در اینجا گروه‌ها با حروف انگلیسی و برچسب‌ها در مقابل آَن داخل پرانتز نوشته خواهد شد. این گروه‌بندی و برچسب‌گذاری می‌تواند به هر صورت دلخواهی انجام شود ولی حتماً باید برای حل یک مسئله خاص برچسب‌گذاری و گروه‌بندی تمامی الگوریتم‌ها یکتا باشند. برای مثال می‌توان گروه مولد اعداد تصادفی را با R، گروه روابط ریاضی را با M، روابط مکاشفه‌ای را با H و گروه تخصیص برچسب خوشه به داده‌ را با G نشان داد. در جدول ۳-۲ مثالی از یک نمونه بسیار ساده از جدول نگاشت استاندارد کد به تصویر کشیده شده است.
جدول۳-۲. یک نمونه از جدول نگاشت استاندارد کد