مثبت کاذب (FP^[29]) : تعداد نمونه­های غیر استراتژی که به اشتباه استراتژی پیش بینی شده اند.
منفی کاذب (FN^[30]): تعداد نمونه­های استراتژی که به اشتباه استراتژی غلط پیش بینی شده اند.
منفی صحیح (TN^[31]) : تعداد نمونه­هایی که غیر استراتژی بوده ­اند و به درستی پیش بینی شده که استراتژی غلط هستند.
چند معیار کارایی از ماتریس درهم بدست می ­آید که در زیر تشریح می­شوند:
Precision : درصد درستی الگوهایی که شناسایی شده اند.
(۲-۱)
: Accuracy درصد نمونه­های الگو و بدون الگویی که به درستی با نام الگو یا بدون الگو شناسایی شده ­اند.
(۲-۲)
نرخ مثبت صحیح (TPR) : درصد الگوهایی که به درستی شناسایی شده ­اند ( همان Recall است) .
(۲-۳)
معیارهای فوق در این تحقیق به منظور ارزیابی دو عملگر پالایش و تصحیح برچسب استفاده می­شوند.

• • 1. 1. جمع بندی

     

     

در این فصل به طور خلاصه چند طبقه بند که برای ساخت مدل در این تحقیق استفاده شده است، بررسی گردید. در نهایت هم معیارهای ارزیابی مدل­ها ارائه گردید.

فصل سوم

1. 1. مروری بر تحقیقات پیشین

      1. 1. مقدمه

       

       

محققان بسیاری در زمینه­ خودکار یا نیمه خودکار­سازی شناسایی الگوهای طراحی از کد منبع یا طراحی کار کرده ­اند. در ادامه این بخش، به طور خلاصه بر برخی از تحقیقاتی که از نظر هدف و یا شیوه کار شباهت بیشتری به تحقیق ما دارند مروری خواهیم داشت.
کارهای مرتبط
در سال ۱۹۹۸ [۱۰] یک روش سه مرحله­ ای برای شناسایی الگوها ارائه شد. ابتدا از طریق محاسبه­ مقادیر یک سری معیارهای عام شی­گرا، نظیر شمارش تعداد صفات، تعریف­ها، و … برای هر کلاس موجود در کد و هر نقش الگوی مورد جستجو، کاندیدهای هر نقش شناسایی شد. در گام اول، فضای جستجو (از طریق حذف کلاسهایی که کاندید نشدند) تا حد زیادی کاهش داده شد. در مرحله دوم از طریق مسأله­ کوتاهترین مسیر، نزدیکترین مسیر بین کاندیدهایی که می­توانند به هم مرتبط شوند، شناسایی شد. سپس هر ترکیب بدست آمده از مرحله دوم به عنوان کاندیدهای الگوی مورد جستجو شناخته شد. در مرحله سوم به دلیل وجود مثبت کاذب بسیار زیاد در مرحله دوم، از محدودیت واگذاری مسئولیت استفاده شد. چنانچه الگویی باید این محدودیت را داشته باشد، ترکیب بدست آمده از مرحله دو، برای داشتن این محدودیت مورد بررسی قرار داده شد، چنانچه چنین محدودیتی نداشت آن ترکیب حذف می­شد. با این حال، روش [۱۰]، میزان مثبت کاذب بالایی دارد. عیب اصلی [۱۰]، در محوریت اصلی کارشان، استفاده از معیارهای عام شی­گرایی بود که از پایه با هدف سنجش الگوها استخراج نشده بودند.
درسال ۲۰۰۵ [۴]، بجای ابداع یک ابزار جدید، یک روش پالایش ابزار خودکار ارائه داد. ورودی پالایش، خروجی ابزار ۲۰۰۳ [۳] بود که توسط خودشان ابداع شده بود و میزان مثبت کاذب بالایی داشت. در[۴]، براساس انعطاف­پذیری­ها و تنوع پیاده­سازی­های هر الگو، یک سری معیار استخراج شد. این معیارها از پایه با هدف سنجش و بررسی حضور الگوها استخراج شدند. روش کار به این صورت بود که خروجی بدست آمده از ابزار[۳]، به صورت دستی تجزیه و تحلیل شد، و هر نمونه­ شناسایی شده، مورد بازبینی قرار گرفت. بطوریکه اگر نمونه به درستی شناسایی شده بود، برچسب درست، و اگر ابزار در شناسایی آن دچار اشتباه شده بود، برچسب نادرست می­گرفت. سپس یک مجموعه داده تهیه شد. نمونه­ها به عنوان رکوردهای آن، معیارها به عنوان صفات توصیف کننده نمونه­ها، و هویت آنها (درست و نادرست) به عنوان ستون خروجی مجموعه داده قرار گرفت. نهایتا با بهره گرفتن از الگوریتم­های داده ­کاوی و مقادیر معیارها روی نمونه­ها، یک سری قوانین استخراج شد که با کمک آنها می­توان نمونه­های ناشناخته در مجموعه داده را تعیین هویت کرد.
کار[۴] انجام شد تا، نمونه­های مثبت کاذب ابزار شناسایی، و از خروجی حذف شوند. پالایش [۴]، خروجی [۳] را تاحد زیادی بهبود داد، اما معیارهای [۴]، تنها بر اساس تنوع پیاده­سازی­های یک الگو استخراج شده بودند و ساختار و عملکرد مشابه الگوهای دیگر در تولید معیارها در نظر گرفته نشده بودند. از طرفی با اینکه حذف نمونه­های مثبت کاذب خروجی مطمئن­تری را در اختیار توسعه دهنده قرار می­دهد، در همان حال، خیلی از اطلاعات را نیز از بین می­رود.
فرانسیسکا و همکارانش [۱۲][۱۱] ابزاری تحت نام مارپل متشکل از پنج ماژول اصلی را توسعه دادند. این ابزار نه تنها فعالیت شناسایی الگوهای طراحی را بلکه بازسازی^[۳۲] معماری نرم افزار را نیز پشتیبانی می­ کند. اولین ماژول آن، موتور شناسایی^[۳۳] اطلاعات نامیده می­ شود این ماژول مدلی از سیستم می­سازد و یک سری معیارها و ساختارهای ریز را جمع آوری می­ کند. دومین ماژول که وصل کننده ^[۳۴] نامیده می­ شود تمام کاندیدای الگوهای طراحی که معیارهای یک تعریف داده شده از هر الگو را برآورده می­ کنند استخراج می­ کند. سومین ماژول، طبقه بندی است که کمک می­ کند مثبت کاذب های بخش قبلی را شناسایی کرده و شباهت آنها را با پیاده سازی­های صحیح هر الگوی مورد نظر، با انتساب مقادیر اطمینان مختلف^[۳۵] مورد سنجش قرار می­دهد. دو ماژول آخر جهت بازسازی معماری نرم افزار مورد استفاده قرار می­گیرند. معیارهای اندازه گیری شده توسط مارپل، معیار­های شی­گرایی هستند که در تولید بعضی از منظر­های معماری بهره­ گیری می­شوند. بخش یادگیری ماشین از فرایند شناسایی، توسط ماژول سوم پیاده سازی می­ شود که کاندیدای استخراج شده از ماژول دوم را به عنوان ورودی می­گیرد و سپس از الگوریتم­های گروه­ بندی^[۳۶] و طبقه بند موجود در نرم افزار weka^[37] برای پالایش کردن نمونه­های مثبت کاذب استفاده می­ کند. عملیات پالایش این شیوه با محاسبه نمره مشابهت بین نمونه صحیح هر الگو با کاندیدای شناسایی شده انجام می­گیرد. نمره دهی بر حسب مشابهت، به ساختار پایه الگو بسیار محدود می­ شود درحالیکه الگوهای طراحی در خیلی از موقعیت­ها از ساختار پایه­ خود به دلیل انعطاف پذیری که دارند، دور می­شوند.
ستورا و همکارانش [۱۳] شیوه­ای را ارائه دادند که بر اساس آن، کاندیدای نقش­هایی که ترکیب آنها کاندیدهای الگوها را تشکیل می­دهد، با اندازه ­گیری یک سری معیار­ها و تکنیک­های داده ­کاوی، جستجو می­ شود. سپس با آنالیز رابطه­ بین کلاسی کاندید­ها، الگوی مورد نظر شناسایی می­ شود. در این شیوه سعی می­ شود الگوهایی که ساختار مشابهی به یکدیگر دارند از هم تشخیص داده شوند، اما در واقع معیارهای استخراج شده برای الگوهایی با ساختار مشابه را دقیقا یکسان در نظر گرفته­اند و آنها را در یک گروه شناسایی می­ کنند. در این روش از تکنیک شرایط محدود کننده استفاده نمی­ شود و خصوصا به همین دلیل روششان آماده پذیرش مثبت کاذب بسیاری می­باشد.
تی سن تا لیس و همکارانش [۱۲][۹] ابزاری به نام ^[۳۸]SSAارائه دادند. در SSA از یک الگوریتم نمره­دهی که نمره­ مشابهت هر زیر گراف سیستم را (فضای جستجو) با هر گراف الگوی مورد جستجو محاسبه می­کرد، استفاده شد. چون الگوریتم SSA خواص انتقال را در ارث بری و واگذاری مسئولیت در نظر می­گیرد، تنوع پیاده­سازی­های یک الگو که از ساختار پایه خود فاصله گرفته­اند را نیز شناسایی می­ کند. SSA درصد بازیابی بالایی دارد، تعداد زیادی از الگوهای موجود را شناسایی می­ کند، به راحتی قابل استفاده است، و همچنین سرعت بالایی دارد. اما بدلیل اینکه الگوریتم SSA تنها بر قواعد ساختاری تاکید دارد، الگوهایی که ساختار یکسانی دارند و تنها در رفتار متفاوت می­شوند، و یا آنهایی که عملکرد مشابهی دارند، توسط SSA قابل متمایز شدن نیستند و SSA آنها را در یک گروه شناسایی می­ کند (مثل “وضعیت/ استراتژی").
شی و همکارانش [۵] ابزاری به نام ^[۳۹]PINOT ارائه دادند. در تولید ­ PINOT از این اصل استفاده شد،" باتوجه به اینکه هر الگوی طراحی باید هدف مشخصی را برآورده کند، بنابراین باید ازآن هدف، یک تعریف عملی در پیاده­سازی آن الگو وجود داشته باشد“. در [۵] سعی شد تا تعریف عملی مربوط به هدف هر الگو از پیاده­سازی آن الگو بیرون کشیده شود، سپس PINOT برای شناسایی الگوها، تعاریف عملی بیرون کشیده شده را به عنوان محدودیت­های اجباری با آنالیز ایستا، جستجو ­کند. PINOTدرصد بازیابی بالایی دارد، تعداد زیادی از الگوها را شناسایی می­ کند، سرعت کمتری نسبت به SSA دارد، و همانند SSA توانایی متمایز کردن الگوها با ساختار و عملکرد مشابه را ندارد. در این تحقیق از دو ابزار SSA و PINOT برای انجام آزمایشات بهره گیری شده است.
[۱۵] ابزاری با نام ^[۴۰]DPJF ارائه داد. در [۱۵]، برای برخی از الگوها، تعدادی محدودیت یا الزام رفتاری جهت شناسایی­شان، ارائه شد. برخی از محدودیت­های [۱۵]، ثبات و قدرت متمایز کنندگی بالایی دارند. ابزار DPJF ادعا می­ کند، صد در صد دقت دارد. اما بر اساس بررسی­ها و ارتباطات انجام شده با گروه [۱۵]، ابزار DPJF تنها الگوی یگانه^[۴۱]را با چنین دقتی شناسایی می­ کند. مثلا در مورد دقت شناسایی الگوی نماینده، برخی نمونه­های شناسایی شده توسط این ابزار بعد از بررسی و ارتباطات با این گروه مشخص شد که الگوی وضعیت هستند و نه الگوی نماینده. همچنین این ابزار هنوز برای شناسایی الگوهای با ساختار و عملکرد مشابه مثل استراتژی و وضعیت پیاده­سازی نشده است. بنابراین مشخص نیست بعد از پیاده سازی به چنین دقتی دست یابد.
در سال ۲۰۱۳ [۲۶]، در تمام مراحل فرایند شناسایی الگوهای طراحی (کاهش فضای جستجو تا شناسایی کاندیدهای هر الگو) از داده ­کاوی بهره گرفت. در مرجع [۲۶]، ابتدا از تعدادی معیار عام سطح کلاس مثل عمق ارث­بری، تعداد متدهای رونویسی شده، و … به منظور جستجوی کاندیدهای هر نقش تشکیل دهنده­ الگوی مورد نظر در میان کلاس­های موجود در فضای کد، با کمک شیوه ­های داده ­کاوی استفاده کرد. در مرحله­ بعد، با ترکیب کاندیدهای نقش­هایی که می­توانند به هم مرتبط شوند، کاندیدهای الگوی مورد جستجو استخراج شدند. سپس برای بررسی صحت یا عدم صحیت کاندیدهای مرحله دوم، یک مجموعه داده تهیه کردند. بطوریکه رکوردهای آن را کاندیدهای مرحله دو، و صفات توصیف کننده آنها را معیارهای مربوط به بررسی روابط میان کلاسی و معیارهای سطح کلاس مرحله یک تشکیل دادند. سپس برای تعیین هویت هر موجودیت (صحت یا عدم صحت ) از چهار ابزار خودکار شناسایی الگوهای طراحی استفاده شد. بطوریکه اگر حداقل دو ابزار در رابطه با یک کاندیدا رأی مثبتی داشتند، آن کاندید به عنوان نمونه صحیح در نظر گرفته می­شد. سپس از الگوریتم­های داده ­کاوی برای خودکار­سازی فرایند تعیین هویت، به منظور شناسایی درستی نمونه­های جدید استفاده کردند.
با توجه به اینکه در داده ­کاوی مهمترین عناصر، صفات توصیف کننده موجودیت­ها و صحت برچسب زنی قبل از مدل­سازی روی مجموعه داده است، ضعف کار [۲۶] دردرجه اول، در استفاده از تعداد زیاد معیارهایی است که با هدف سنجش الگوها استخراج نشده بودند، و دوم برای برچسب زنی اولیه مجموعه داده، استفاده از ابزارهای موجود شناسایی الگوهای طراحی، که دقت کاملی ندارند و بدیهی است که در فرایند برچسب زنی دچار اشتباه شوند. این روش با دقت نسبتا پایینی متوسط “۴۹%” روبرو شد.
در سال ۲۰۱۳ [۲۸]، یک روش پرس­و­جوی الگوهای طراحی از پایگاه داده ارائه کرد. محور اصلی [۲۸]، بکارگیری شیوه­ اصولی برای سست کردن پرسو­جو­ها بود، پرس­و­جو­ها به دو دسته تقسیم می­شدند، خاص و عام. خاص یعنی تبدیل خصوصیات الگو به یک پر­سو­جوی سخت برای شناسایی الگو­هایی­که از ساختار پایه فاصله نگرفته­اند و عام، تبدیل خصوصیات الگوها به یک پرسو­جوی عام تر (با بهره­ گیری از ویژگی­­های پیاده­سازی متنوع یک الگو) برای نمونه­هایی که از ساختار پایه فاصله گرفته­اند، بطوریکه بتوان تنوع نمونه­های قابل قبول الگوهای طراحی را پیدا کرد. نتایج این کار تنها برای الگوی “یگانه” ارائه شده است. مقایسه­ نتایج با دو ابزار PINOT و DPJF نشان دهنده­ بهبود کارشان نسبت به آن دو روش در تشخیص الگوی یگانه است. اما نتایج ابزار SSAکه در کارشان آورده نشده است از هر سه بهتر است.
در سال ۲۰۱۳ [۲۹]، از یک روش مقایسه­ گراف برای شناسایی الگوهای طراحی استفاده کرد. در [۲۹]، از تئوری چندریختی زیر گراف ­­­ استفاده شد. در واقع مفهوم عام مقایسه­ گراف مشخص می­ کند که آیا دو گراف یکسان هستند یا زیرگرافی از یکی در دیگری موجود است یا خیر. در [۲۹]، برای شناسایی الگوها سه حالت مقایسه را ارائه شد، حالت اول اینکه، اگر گراف الگو با گراف مدل سیستم همریخت باشد، در این صورت الگو موجود است، حالت دوم، اگر زیرگراف همریخت از الگو در گراف مدل موجود باشد، در این حالت، به صورت تقریبی الگو موجود است و حالت سوم الگو زیرگراف هم ریخت از گراف مدل نیست که در چنین حالتی الگو موجود نیست. در [۲۹]، نتایجی ارائه نشده است، اما به طور کلی همانطور که در [۹] نیز ذکر شده است، استفاده از روش­های مقایسه همر­یخت­های زیر­گراف یا گراف یک الگو نمی ­توانند روش مناسبی در شناسایی الگوها باشند، چون اول اینکه الگوها انعطاف­پذیری بالایی دارند و به ندرت در پیاده­سازی، معادل با ساختار پایه باقی می­مانند. دوم، مسأله پیدا کردن کل گراف یا زیر­گراف­های هم ریخت یک گراف یک مسأله NP-Complete است و ممکن است هیچ هم­ریختی پیدا نشود.
برای بهبود خروجی روش­های ارائه شده، استفاده از داده ­کاوی و استخراج معیارهایی جدیدی که بتواند نقص­های موجود در ابزارها را رفع کند لازم است. علت استفاده از داده ­کاوی این است که می­توان هر گونه معیاری را (رفتاری و ساختاری) به راحتی با هم ترکیب کرد و با تولید مقادیر این معیار­ها و تجزیه و تحلیل آنها توسط شیوه ­های داده ­کاوی، قانون­های قدرتمندی رابرای پالایش و تصحیح خروجی ابزارهای تقریبا قوی مثل SSAارائه داد و قدرت آن را در شناسایی تمامی الگوها تکمیل کرد. پالایش به کمک استخراج معیارهای خاص سنجش الگوها در کارهای مشابه انجام شده است. اما هیچ یک معیارهایی استخراج نکرده ­اند که با ترکیب آنها بتوان عملیات تصحیح خروجی (بدون از دست دادن اطلاعات) را انجام داد.
جمع بندی
در این فصل مروری کوتاه و اجمالی بر روش­هایی که ساختار و اهداف تقریبا مشابهی با تحقیق جاری دارند، شد. همچنین محدودیت­ها و مشکلات هر شیوه بیان گردید و دو ابزاری که در این تحقیق جهت انجام آزمایشات از آنها استفاده شده است معرفی گردیدند.
فصل چهارم