1. نتیجه گیری و کارهای آتی…………………………………………………………………..۵۸

• فهرست منابع و مآخذ………………………………………………………………………….۵۹
• چکیده به زبان انگلیسی ……………………………………………………………………..۶۲

فهرست جدول ها

عنوان صفحه

جدول۲-۱ماتریس درهم……………………………………………………………………………………………….۱۹

جدول ۴-۱بخش کوچکی از مجموعه داده برای عملگر تصحیح برچسب……………………۴۹

جدول۴-۲ بخش کوچکی از مجموعه داده برای عملگر پالایش…………………………………۵۰

جدول ۵-۱ارزیابی دقت بکارگیری معیارها و روش داده ­کاوی C5.0 با روش یکی در مقابل همه………………………………………………………………………………………………………………………………………..۵۳

جدول ۵-۲ ارزیابی دقت بکارگیری روش داده ­کاوی SVMو معیارها با روش یکی در مقابل همه………………………………………………………………………………………………………………………………………..۵۳

جدول ۵-۳ ارزیابی دقت بکارگیری روش داده­کاویBoosting و معیارها با روش یکی در مقابل همه……………………………………………………………………………………………………………………………..۵۴

جدول ۵-۴ ارزیابی دقت بکارگیری روش داده ­کاوی SVM و معیارها با روش دو در دو…………………………………………………………………………………………………………………………………………..۵۵

جدول ۵-۵ ارزیابی دقت بکارگیری روش داده ­کاوی Boosting و معیارها با روش دو در دو…………………………………………………………………………………………………………………………………………..۵۵

جدول ۵-۶ ارزیابی دقت بکارگیری روش­های داده ­کاوی و معیارها با روش چند برچسب………………………………………………………………………………………………………………………………….۵۵

فهرست شکل ها

عنوان صفحه

شکل۴-۱الگوی استراتژی………………………………………………………………………………۳۲

شکل۴-۲یک نمونه الگوی استراتژی حقیقی………………………………………………۳۲

شکل۴-۳ رابط های یک نمونه الگوی استراتژی حقیقی……………………………..۳۳

شکل۴-۴ترتیب فراخوانی از رابط های یک استراتژی حقیقی………………………۳۳

شکل ۴-۵ الگوی وضعیت…………………………………………………………………………….۳۵

شکل ۴-۶الگوی تطبیق دهنده شی…………………………………………………………..۳۷

شکل۴-۷الگوی کارخانه انتزاعی……………………………………………………………….۳۹

شکل۴-۸الگوی فرمان………………………………………………………………………………۴۰

شکل۴-۹شباهت ساختاری الگوی فرمان و تطبیق دهنده شی………………..۴۱

شکل۴-۱۰ الگوی ملاقات کننده……………………………………………………………….۴۲

شکل۴-۱۱ الگوی میانجی………………………………………………………………………….۴۳

شکل۴-۱۲الگوی آذیین کننده……………………………………………………………………۴۴

شکل۴-۱۳الگوی ترکیب…………………………………………………………………………..۴۶

شکل ۴-۱۴ مراحل ایجاد مدل­های تصمیم ­گیری……………………………………..۴۹

شکل ۵-۱ بهبود روی ابزار شناسایی خودکار الگوهای طراحی ” SSA”…..55

شکل ۵-۲ بهبود روی ابزار شناسایی خودکار الگوهای طراحی ” PINOT “…56

فصل اول

۱-مقدمه

اگرچه طراحی یک نرم­افزار شی­گرا دشواری­های خاص خود را دارد، دشوار­تر از آن، طراحی یک نرم­افزار شی­گرا با قابلیت استفاده مجدد است. الگوهای طراحی، استفاده از طراحی­ها و معماری­های موفق را آسان می­ کنند [۱]. الگوهای طراحی راه­ حل­های اثبات شده و قابل اطمینان هستند که به منظور حل مسائلی که به طور مکرر در طراحی یک نرم افزار شی­گرا رخ می­دهد، مورد استفاده قرار می­گیرند. یک الگوی طراحی هدف و ساختار واحد خودش را دارد. الگوها نقش­ها، مسئولیت ­ها، نحوه­ همکاری کلاس­ها و نمونه­های شرکت کننده در این همکاری را توصیف می­ کنند. بنابراین با استخراج الگو­های طراحی از کد منبع، قادر به آشکار کردن هدف و طرح یک سیستم نرم­افزاری هستیم [۵].

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

محققان بسیاری در زمینه شناسایی الگوهای طراحی، کار کرده ­اند (خودکار یا نیمه خودکار). اما هیچ کدام نتوانسته­اند یک خروجی مطمئن و بدون مثبت کاذب را در اختیار توسعه­دهندگان قرار دهند. به طورکلی شیوه ­های شناسایی الگو­های طراحی به دودسته تقسیم می­شوند. آنهایی که بر اساس جنبه­ های ساختاری الگوها، کار شناسایی را انجام می­ دهند و آنهایی که از جنبه­ های رفتاری موجود در الگو­ها نیز جهت شناسایی بهره می­گیرند [۵].

هدف قرار دادن جنبه­ های ساختاری

برخی از شیوه ­ها، برای شناسایی الگوها، تنها جنبه­ ساختاری آنها را در نظر می­گیرند. ابتدا خصوصیات ساختاری هرکلاس موجود در کد منبع با هر نقش تشکیل­ دهنده­ یک الگو مقایسه و کاندیدهای هر نقش شناسایی می­ شود. سپس کاندیدهای نقش­هایی که می­توانند به هم مرتبط شوند، ترکیب می­شوند. در نهایت روابط میان کلاسی را بدون توجه به خصوصیات رفتاری، تجزیه و تحلیل و با الگوها مقایسه می­ کنند. روابط­ میان کلاسی شامل ارث بری، انواع برگشتی، تعریف^[۱]، تعمیم^[۲]، پیوند^[۳]، و … می­شوند. به ­عنوان­ مثال­ SPOOL [19]،DP++ [18]، Osprey [20]، و [۲۱] به شیوه ساختاری فوق، الگوها را شناسایی می­ کنند.

بالانیا و همکارانش [۳] با استفاده ازیک چارچوب به نام کولامبوس، گراف­های معنایی منتزع^[۴] را استخراج، و برای شناسایی الگو­ها بر اساس مقایسه گراف­ها^[۵] عمل کردند [۵]. همچنین [۲] از معناشناسی صریح^[۶] برای پیدا کردن الگوها روی گراف معنایی منتزع بهره می­گیرد. در هر حال برای شناسایی الگوها، علاوه بر خصوصیات ساختاری، تجزیه و تحلیل خصوصیات رفتاری نیز ضروری است.

هدف قرار دادن جنبه های رفتاری

شیوه ­های بحث شده در بخش قبل قادر به تشخیص الگوهایی که از نظر ساختاری یکسان اما رفتار متفاوتی دارند نظیر الگوی” استراتژی” در مقابل الگوی”وضعیت ” نیستند. شیوه­ هایی که جنبه­ های رفتاری را هدف قرار می­ دهند، سعی می­ کنند این مساله را با بهره گرفتن از یاد­گیری ماشین، تحلیل پویا^[۷] [۲۴] یا تحلیل ایستا^[۸] حل کنند [۵].

تجزیه و تحلیل پویا

این شیوه ­ها از داده ­های زمان اجرا^[۹] برای تشخیص جنبه­ های رفتاری الگو­ها استفاده می­ کنند. کی تی [۲۲]، تنها از تجزیه و تحلیل پویا برای تشخیص الگوی “زنجیره مسئولیت ­ها^[۱۰]” استفاده کرد اما نتیجه­اش موفقیت­آمیز نبود (به دلیل نامناسب بودن مکانیزم رخداد نگارى کردن پیام^[۱۱] و ناکافی بودن داده آزمایش). تجزیه و تحلیل پویا به پوشش خوبی از داده­ آزمایش به منظور اعمال هر مسیر اجرایی ممکن نیازمند است. چنین داده آزمایش اغلب موجود نیست. حتی اگر داده­ آزمایش هم موجود باشد، نتایج زمان اجرا ممکن است گمراه کننده باشند. چون چنین داده­هایی اصولا برای تشخیص دادن رفتار الگو­های خاص، طراحی نشده­اند [۵].

تجزیه وتحلیل ایستا

‌‌‌این روش­ها اصولا شیوه ­های تجزیه و تحلیل ایستا را به درخت معنایی منتزع^[۱۲] در بدنه متدها اعمال می­ کنند. مرجع [۲۵] بیانیه­های “ایجاد شی غیرحساس به مسیر”^[۱۳] را برای تشخیص الگوهای “^[۱۴]کارخانه­ انتزاعی” و”متد کارخانه”^[۱۵] استفاده کرد. برای شناسایی الگوها با ساختار و عملکرد مشابه، بیرون کشیدن هدف الگو در پیاده­­سازی، به منظور متمایزسازی آنها بسیار مهم است. اما اکثر چنین شیوه­ هایی قادر نیستند هدف برنامه را بیرون بکشند [۵].

در این کار، ابزارهای خودکار شناسایی الگوهای طراحی با دو عمل “پالایش” و “تصحیح برچسب” گسترش می­یابند. عمل پالایش، بیشترین یا حتی همه­ مثبت کاذب­های تولید شده در خروجی ابزارهای خودکار را شناسایی می­ کند. در­حالیکه تصحیح برچسب، هویت صحیح نمونه مثبت کاذب را (بر حسب اینکه مثبت کاذب، به دلیل شباهت با کدام الگو مثبت کاذب شده است) با بهره گرفتن از معیارهای تعریف شده در این کار و روش­های داده ­کاوی شناسایی می­ کند. به طور مثال اگر نمونه­ شناسایی شده توسط ابزارهای خودکار، با برچسب “استراتژی” شناسایی شده است اما در حقیقت این نمونه استراتژی نبوده، ابتدا به عنوان مثبت کاذب شناخته می­ شود (پالایش)، سپس برچسب صحیح آن (بر حسب مقادیر معیارها) تشخیص داده می­ شود.

به طور­مثال بر­چسب صحیح آن ممکن است الگوی “وضعیت” باشد. بنابراین برچسب استراتژی به وضعیت تغییر می­ کند. با­ استفاده از این معیار­ها و روش­های داده ­کاوی علاوه برنمونه­های مثبت­­­کاذب، نمونه­های منفی­کاذب نیز در برخی موقعیت­ها کاهش می­یابند. چون وقتی یک برچسب تصحیح می­ شود مثلا از استراتژی به وضعیت، ممکن است این نمونه وضعیت جزء نمونه­­های شناسایی شده برای الگوی وضعیت نباشد، بنابراین این نمونه­ وضعیت یک منفی­کاذب شمرده شده که با شناسایی آن، یک منفی کاذب را حذف کرده­ایم.

با توجه به اینکه ابزارها و روش­های پیشین، بیشترین مثبت کاذب را در شناسایی الگوهای با ساختار و عملکرد مشابه تولید می­ کنند، در این­کار، سعی شده تا خروجی ابزارها با توانایی شناسایی چنین الگوهایی تصحیح گردد. لذا، تصحیح برچسب روی نمونه­های استخراج شده­ الگوی استراتژی (به دلیل داشتن شباهت­های ساختاری و عملکردی با الگوهای دیگر، بر حسب خروجی ابزارها بیشترین مثبت کاذب در شناسایی آن تولید شده است) انجام می­ شود. ابتدا براساس روش­های عرف داده ­کاوی، با نمونه­های مثبت کاذب و مثبت صحیح الگوی استراتژی بدست آمده توسط ابزارها، یک مجموعه داده­ تهیه شده است. سپس بر اساس مستندات موجود و همچنین بازبینی دستی، به منظور پیش ­بینی هویت صحیح هر نمونه، دو ستون در مجموعه داده تعیین شده است. یک ستون با “درست” و “نادرست” (درست، در صورت شناسایی صحیح توسط ابزارها و نادرست در صورت مثبت کاذب بودن) برچسب می­خورد، و ستون دیگر با نام الگو صحیح آن نمونه یا در صورت ناشناس بودن، با بدون الگو برچسب می­گیرد. سپس مقادیر معیارها یا پیش­­بینی کننده­ های استخراج شده در این کار، روی هر نمونه محاسبه می­شوند و نهایتآَ مجموعه داده در اختیار الگوریتم­های داده ­کاوی جهت مدل­سازی قرار می­گیرند. در مدل­سازی سعی می­ شود دانش موجود در داده ­ها، در قالب یک سری قوانین استخراج شوند. این قوانین برای شناسایی نمونه­های ناشناخته (جدید) در مجموعه داده­ مورد استفاده قرار می­گیرند.

آزمایش­ها، با بهره گرفتن از سه الگوریتم یادگیری ماشینC5.0 ، Boostingو SVMانجام شده است. روش پیشنهادی روی سه نرم افزارمتن باز jhotdraw6[6]، jrefactory[7] و javaio [8] انجام شده است. الگوهای پیاده شده در این پروژه­ ها از ساختار پایه­ای که برای آنها در کتاب­ها معرفی شده است بسیار فاصله گرفته­اند (الگو ها بسیار انعطاف پذیر هستند و توسط هر برنامه­نویس می­توانند به روش­های متفاوتی پیاده­سازی شوند و هم چنین ترکیب شوند) بنابراین شناسایی چنین الگوهایی دشواری­های خاص خودش را دارد [۲].

در این کار، معیارهای جدید به عنوان پیش­گویی کننده­ های عملیات تصحیح برچسب و پالایش، روی نمونه­های خروجی الگوی طراحی “استراتژی” یافت شده توسط ابزار­های [۹] SSA و [۵] PINOT استفاده شده ­اند. ابتدا مثبت کاذب­های استراتژی تشخیص داده می­شوند و سپس الگوی طراحی صحیح موجود در نمونه مثبت کاذب شناسایی می­ شود. نمونه­های مثبت کاذب به سمت نمونه­ها­ی مثبت صحیح با تشخیص آنها از الگوهای “وضعیت^[۱۶]“، “استراتژی^[۱۷]“، “تطبیق­دهنده^[۱۸]“، “فرمان^[۱۹]“، “ملاقات­کننده^[۲۰]“، “میانجی^[۲۱]“، “آذیین کننده^[۲۲]“، “ترکیب^[۲۳]” و”کارخانه انتزاعی^[۲۴]“حرکت می­ کنند. همچنین این معیارها می­توانند الگوهایی که ساختار کاملا مشابهی به یکدیگر دارند نظیر”وضعیت از استراتژی “، “تطبیق دهنده از فرمان”، “آذیین کننده از ترکیب” و استراتژی را از هشت الگوی دیگر مورد مطالعه در این تحقیق متمایز کنند. این الگوها در نظر گرفته شدند، چون بیشترین مثبت کاذب موجود در نتایج الگوی استراتژی با اشتباه گرفتن با این الگو­ها بر حسب ساختار و عملکرد مشابه تولید شده است.

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

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

• 1. فرضیات و محدودیت های مساله

الگوها با قرار­گیری در موقعیت­های متفاوت مسائل حقیقی، در اکثر مواقع تا حد زیادی ممکن است از ساختار پایه خود فاصله بگیرند. الگوها با دست برنامه نویس برای حل یک مساله­ عمومی در یک زمینه­ خاص سمت و سو می­گیرند. از طرفی الگوها علاوه بر جنبه­ ساختاری دارای جنبه­ های رفتاری متفاوتی نیز هستند. بطوریکه گاهی فقط رفتار است که دو الگو را از هم متمایز می­ کند. یکی از محدودیت­های الگوهای طراحی، انعطاف­پذیری و ساختار و عملکرد مشابه بین آنها است. بنابراین در این پایان نامه سعی شده است که مجموعه کاملی از انعطاف­پذیری­های هر الگو به علاوه­ یک سری ویژگی­های رفتاری متمایز کننده دیده شود و معیارهایی پابرجا برای بیان ثابتی از اینکه همه­ یک مجموعه انعطافات به کدام الگو مرتبط می­شوند استخراج شود و نهایتا این معیار­ها به عنوان پیش­گویی کننده­ها همراه با تکنیک­های داده ­کاوی برای جستجو و تصحیح مثبت کاذب­های الگوهای شناسایی شده توسط ابزار­های خودکار استفاده شوند. در هر صورت این احتمال می­رود که انعطافات بیشتری برای هر الگو موجود باشد که در این تحقیق دیده نشده است.

• 1. ضرورت انجام تحقیق

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

• 1. هدف از انجام تحقیق

هدفی که در این پایان نامه دنبال می­ شود ارائه روشی برای رسیدن به حداکثر بهبود (حداقل مثبت و منفی کاذب) روی شناسایی الگوی طراحی و ایجاد خروجی بدون ابهام و صحیح برای استفاده توسط توسعه دهنده می­باشد. به علاوه جهت تسهیل در امر نگهداشت­پذیری و استفاده مجدد نرم افزار نه تنها از نظر فهم راحت طرح و هدف سیستم، بلکه ­از نظر صرف وقت و هزینه می­باشد.

• 1. سرفصل مطالب

مطالب بیان شده در این پایان نامه در قالب شش فصل گردآوری شده اند که به طور خلاصه به شرح زیر است.

فصل دوم : تعاریف و مفاهیم اولیه

دراین فصل مختصری بر روی مفاهیم اولیه روش­های داده ­کاوی و معیار­های ارزیابی مدل­های پیش بینی کننده در این تحقیق خواهیم داشت.

فصل سوم : مروری بر تحقیقات پیشین

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

فصل چهارم : تولید مجموعه داده ها

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

فصل پنجم : آزمایشات و نتایج عددی

دراین فصل با بهره گرفتن از معیار­های استخراج شده و تکنیک­های داده ­کاوی، مجموعه ­ای از آزمایش­ها جهت انجام عملیات پالایش و تصحیح برچسب الگوی استراتژی روی نتایج دو ابزار خودکارشناسایی الگوهای طراحی SSA و PINOTانجام گرفته شرح داده می­ شود. نتایج تولیدی این ابزار­ها مربوط به عمل شناساییشان روی سه پروژه ی متن باز jhotdraw ،­ jrefactory و javaio می باشد. به علاوه نتایج عددی حاصل از این آزمایش­ها و معیار­های استخراج شده در این فصل ارائه می­گردد.

فصل ششم : نتیجه گیری و پیشنهادات

جمع بندی مطالب گفته شده در پایان نامه در این فصل انجام شده و همچنین پیشنهاداتی برای ادامه پژوهش در این زمینه ارائه شده است.

فصل دوم

1. تعاریف و مفاهیم اولیه

   1. مقدمه

دراین فصل مختصری بروی مفاهیم و تعاریف اولیه­ روش­های داده ­کاوی و معیارهای ارزیابی مدل­های پیش بینی­کننده در این تحقیق خواهیم داشت.

• 1. تکنیک های طبقه بندی^[۲۵]

در داده ­کاوی با دو مجموعه داده مواجه هستیم، داده­ آموزشی و داده آزمایشی. صفات داده­ آموزشی را مجموعه معیارهایی تشکیل می­ دهند که هویت موجودیت­های قرارگرفته درر­کورد­ها را پیشگویی می­ کنند. موجودیت­های داده­ی آموزشی، مشاهداتی هستند که از قبل هویت­شان شناسایی شده­ است. داده­ی آموزشی حاوی یک ستون پیش­گویی است. مقادیر این ستون، با برچسب­هایی پر می­شوند که هویت اصلی موجودیت­ها را نشان می­دهد (مثلا درست یا غلط). داده­ آزمایشی حاوی مشاهداتی است که هویت اصلیشان شناخته شده نیست. با تجزیه ­و­ تحلیلی که به واسطه­ الگوریتم­های داده ­کاوی روی داده­ی آموزشی صورت می­گیرد مدل­هایی ساخته می­ شود. مدل­سازی، دانش موجود در مشاهدات داده­ آموزشی را در قالب یک سری قوانین استخراج می­ کند. داده­ آزمایشی برای ارزیابی دقت پیش­گویی مدل ساخته شده روی داده­ آموزشی بکار برده میشود. در واقع پیشگویی یک فرایند دو مرحله­ ای دارد، فاز یادگیری و فاز دسته­بندی.

‌‌‌در فاز یادگیری بر اساس مجموعه داده­ی آموزشی، مدل طبقه­بند ساخته می­ شود و در فاز طبقه ­بندی بر اساس مدل ساخته شده در فاز قبل، مجموعه داده­ جدید که در فاز یادگیری استفاده نشده است (مجموعه داده آزمایشی) دسته­بندی می­ شود (پیش­گویی می­ شود که مشاهدات جدید چه برچسبی به خود بگیرند). جهت خودکار سازی عملگر تصحیح برچسب در این تحقیق، از روش­های داده ­کاوی (الگوریتم­های طبقه بندی) استفاده شده است [۱۷].

دقت مدل، درصد نمونه­هایی از مجموعه داده آزمایش است که به درستی طبقه بندی شده ­اند. مجموعه داده لازم جهت ساخت مدل طبقه بندی، از متغیر­های مستقل و وابسته تشکیل شده است. متغیر­های مستقل همان خصیصه­ها هستند که جهت طبقه بندی متغیر وابسته که در واقع بر چسب کلاس­ها می باشد، مورد استفاده قرار می­گیرند [۱۷]. توضیح مختصری در مورد انواع طبقه ­بندی­هایی که در این تحقیق مورد استفاده قرار گرفته اند در ادامه آمده است.

۲-۲-۱- طبقه بند C5.0

این طبقه بند در واقع براساس تقسیم مبتنی بر نمونه روی فیلدی که بیشترین سود اطلاعاتی را با خود دارد، کار می­ کند. سپس هر زیرنمونه تعریف شده با اولین تقسیم، دوباره تقسیم می­ شود (معمولا بر اساس یک فیلد متفاوت). این فرایند تکرار می­ شود تا اینکه هیچ زیرنمونه قابل تقسیم نداشته باشیم. سرانجام پایین ترین سطح تقسیم ها دوباره بررسی می شوند. آنهایی که تاثیر قابل توجهی بر مقدار مدل ندارند حذف یا هرس می­شوند [۱۶].

۲-۲-۲- طبقه بند SVM

یک طبقه بند و الگوریتم رگرسیون است که از تئوری یادگیری ماشین با حداکثر دقت پیش بینی بدون” اُور فیتینگ^[۲۶] ” داده ها استفاده می­ کند. این روش از یک تبدیل غیر خطی بر داده های یادگیری استفاده می­ کند، و با جستجوی برای تساوی های رگرسیون در داده ­های تبدیل شده کلاس­ها (اهداف) را جدا می­ کنند.SVM خصوصا برای آنالیز داده ­ها با تعداد زیادی از فیلد­های پیش گویی کننده مناسب می­باشد [۱۶].

۲-۲-۳- طبقه بند BOOSTED C5.0

یک الگوریتم داده ­کاوی است که برای کاهش خطای الگوریتم­های یادگیری ضعیف (به آرامی به سمت طبقه بندی صحیح میل می­ کنند) مورد استفاده قرار می­گیرد و آنها را به یک الگوریتم یادگیری قوی تبدیل می­ کند. در این کار برای قدرت بیشتر بخشیدن به الگوریتم تصمیم گیری C5.0 استفاده شده است [۲۷].

• 1. معیارهای ارزیابی کارایی

ارزیابی دقت مدل­های پیش ­بینی­کننده این تحقیق برای عملگر تصحیح برچسب، برحسب نسبت تعداد تصمیم گیری­های درست از سیستم­های یادگیری در مقایسه با طبقه بندی دستی به تعداد کل کاندیدا است. ماتریس درهم^[۲۷] جهت ارزیابی طبقه بندی­های دودویی می­باشد که در این تحقیق برای ارزیابی بخش پالایش نمونه­ها وتصحیح برچسب استفاده می­ شود [۱۷]. همانطور که در جدول ۲-۱ مشاهده می شود ماتریس درهم کلاس های واقعی را در مقابل کلاس های پیش بینی شده در داده آزمایش نشان می­دهد.

جدول۲-۱٫ جدول درهم شامل کلاس های واقعی در مقابل کلاس های پیش بینی شده

ماتریس درهم شامل چهار قسمت می باشد :

مثبت صحیح (TP^[28]) : تعداد نمونه­های استراتژی که به درستی استراتژی پیش بینی شده ­اند.

مثبت کاذب (FP^[29]) : تعداد نمونه­های غیر استراتژی که به اشتباه استراتژی پیش بینی شده اند.

منفی کاذب (FN^[30]): تعداد نمونه­های استراتژی که به اشتباه استراتژی غلط پیش بینی شده اند.

منفی صحیح (TN^[31]) : تعداد نمونه­هایی که غیر استراتژی بوده ­اند و به درستی پیش بینی شده که استراتژی غلط هستند.

چند معیار کارایی از ماتریس درهم بدست می ­آید که در زیر تشریح می­شوند:

Precision : درصد درستی الگوهایی که شناسایی شده اند.

(۲-۱)

: Accuracy درصد نمونه­های الگو و بدون الگویی که به درستی با نام الگو یا بدون الگو شناسایی شده ­اند.

(۲-۲)

نرخ مثبت صحیح (TPR) : درصد الگوهایی که به درستی شناسایی شده ­اند ( همان Recall است) .

(۲-۳)

معیارهای فوق در این تحقیق به منظور ارزیابی دو عملگر پالایش و تصحیح برچسب استفاده می­شوند.

• 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ارائه داد و قدرت آن را در شناسایی تمامی الگوها تکمیل کرد. پالایش به کمک استخراج معیارهای خاص سنجش الگوها در کارهای مشابه انجام شده است. اما هیچ یک معیارهایی استخراج نکرده ­اند که با ترکیب آنها بتوان عملیات تصحیح خروجی (بدون از دست دادن اطلاعات) را انجام داد.

جمع بندی

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

فصل چهارم

1. تولید مجموعه داده ها

   1. مقدمه

برای آماده ­سازی مجموعه داده مورد نیاز جهت خودکار­کردن عملیات تصحیح برچسب و پالایش، دو فعالیت مهم باید صورت بگیرد. اول، مجموعه کاملی از الگوهایی که با قرار­گیری در موقعیت­های متفاوت از ساختار پایه دور شده ­اند و توسط ابزارهای خودکار شناسایی با الگویی نظیر استراتژی اشتباه گرفته شده ­اند و همچنین مجموعه کاملی از انعطافاتی که مربوط به هر الگو می­باشد، باید فراهم گردد. سپس تولید مقادیر برای معیارهای استخراج شده در این تحقیق که همان پیش ­بینی کننده­ها می­باشند انجام می­گیرد. بنابراین در این فصل ابتدا تمام معیارهای استخراج شده در این تحقیق شرح داده می­ شود. سپس توضیحی در مورد چگونگی تولید مجموعه داده برای عملیات تصحیح برچسب و پالایش فراهم می­گردد.

• 1. معیارهای استخراج شده

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