خلاصه پایان نامه گسترش ابزار های خودکار شناسایی الگو های طراحی با عملیات پالایش و تصحیح برچسب
پایان نامه کارشناسی ارشد در رشته مهندسی کامپیوتر(نرم افزار)
چکیده
گسترش ابزار های خودکار شناسایی الگو های طراحی با عملیات پالایش و تصحیح برچسب
الگوهای طراحی، راهحلهای اثبات شده و قابل اطمینانی هستند که، برای پاسخ به برخی از مسائل با رخداد مکرر در طراحی نرم افزار شیگرا، ارائه شدهاند. شناسایی آنها درکد، به منزله بازیابی طرح و هدف مخفی طراح و سهولت در امر نگهداشتپذیری است. از آنجاییکه سهولت در نگهداشتپذیری سیستم بسیار مهم و اجتناب ناپذیر است، لذا تولید ابزارهای خودکار برای شناسایی الگوها، مورد توجه قرار گرفت. اکثر ابزارهای شناسایی کنونی درصد بازیابی بالایی دارند. اما در شناسایی الگوها، به ویژه با ساختار و عملکرد مشابه، مثبت کاذب بالایی تولید میکنند. از اینرو عملگر پالایش نیز پیشنهاد شد. پالایش، سعی بر شناسایی مثبتهای کاذب، و حذف آنها دارد. در این کار، یک عملگر جدید به نام "تصحیح برچسب" ارائه شده است. این عملگر ابتدا مثبتهای کاذب را شناسایی، سپس بجای اینکه آنها را از خروجی حذف کند، هویت صحیح آنها را به کمک یک مجموعه معیارجدید معرفی شده در این کار، تشخیص و برچسب مثبت کاذب را تصحیح میکند. خودکارسازی عملگر با داده کاوی است. نتایج حاصل از روش ارائه شده، با دقت یادگیری 97.8% در دستهبندی "چندبرچسبه"، با متوسط 99.3% در دسته بندی "یکی درمقابل همه"و متوسط 99.6% در دستهبندی "دو به دو" خروجی ابزارها را تصحیح میکند.
فصل اول
مقدمه
اگرچه طراحی یک نرمافزار شیگرا دشواری های خاص خود را دارد، دشوارتر از آن، طراحی یک نرمافزار شیگرا با قابلیت استفاده مجدد است. الگوهای طراحی، استفاده از طراحیها و معماریهای موفق را آسان میکنند [1]. الگوهای طراحی راهحلهای اثبات شده و قابل اطمینان هستند که به منظور حل مسائلی که به طور مکرر در طراحی یک نرم افزار شیگرا رخ میدهد، مورد استفاده قرار میگیرند. یک الگوی طراحی هدف و ساختار واحد خودش را دارد. الگوها نقشها، مسئولیتها، نحوه همکاری کلاسها و نمونههای شرکت کننده در این همکاری را توصیف میکنند. بنابراین با استخراج الگوهای طراحی از کد منبع، قادر به آشکار کردن هدف و طرح یک سیستم نرمافزاری هستیم [5].
بکارگیری صحیح الگوهای طراحی در توسعه یک نرمافزار شیگرا، میتواند به طور چشمگیری کیفیت کد منبع را بر حسب نگهداشت پذیری و قابلیت استفاده مجدد بهبود دهد. مهمترین مساله نگهداشتپذیری سیستمهای نرمافزاری خصوصا سیستمهای قدیمی این است که فاقد سند کامل از طرح سیستم و اهداف آن هستند. بنابراین شناسایی الگوهای طراحی به صورت خودکار یا نیمه خودکار، سندسازی سیستم، نگهداشتپذیری و قابلیت استفاده مجدد آن را تسهیل میکند.
محققان بسیاری در زمینه شناسایی الگوهای طراحی، کار کردهاند (خودکار یا نیمه خودکار). اما هیچ کدام نتوانستهاند یک خروجی مطمئن و بدون مثبت کاذب را در اختیار توسعهدهندگان قرار دهند. به طورکلی شیوههای شناسایی الگوهای طراحی به دودسته تقسیم میشوند. آنهایی که بر اساس جنبههای ساختاری الگوها، کار شناسایی را انجام میدهند و آنهایی که از جنبههای رفتاری موجود در الگوها نیز جهت شناسایی بهره میگیرند [5].
هدف قرار دادن جنبه های ساختاری
برخی از شیوه ها، برای شناسایی الگوها، تنها جنبه ساختاری آنها را در نظر میگیرند. ابتدا خصوصیات ساختاری هرکلاس موجود در کد منبع با هر نقش تشکیل دهنده یک الگو مقایسه و کاندیدهای هر نقش شناسایی میشود. سپس کاندیدهای نقشهایی که میتوانند به هم مرتبط شوند، ترکیب میشوند. در نهایت روابط میان کلاسی را بدون توجه به خصوصیات رفتاری، تجزیه و تحلیل و با الگوها مقایسه میکنند. روابط میان کلاسی شامل ارث بری، انواع برگشتی، تعریف[1]، تعمیم[2]، پیوند[3]، و ... میشوند. به عنوان مثال SPOOL [19]،DP++ [18]، Osprey [20]، و [21] به شیوه ساختاری فوق، الگوها را شناسایی میکنند.
بالانیا و همکارانش [3] با استفاده ازیک چارچوب به نام کولامبوس، گراف های معنایی منتزع[4] را استخراج، و برای شناسایی الگوها بر اساس مقایسه گرافها[5] عمل کردند [5]. همچنین [2] از معناشناسی صریح[6] برای پیدا کردن الگوها روی گراف معنایی منتزع بهره میگیرد. در هر حال برای شناسایی الگوها، علاوه بر خصوصیات ساختاری، تجزیه و تحلیل خصوصیات رفتاری نیز ضروری است.
هدف قرار دادن جنبه های رفتاری
شیوه های بحث شده در بخش قبل قادر به تشخیص الگوهایی که از نظر ساختاری یکسان اما رفتار متفاوتی دارند نظیر الگوی" استراتژی" در مقابل الگوی"وضعیت " نیستند. شیوههایی که جنبههای رفتاری را هدف قرار میدهند، سعی میکنند این مساله را با استفاده از یادگیری ماشین، تحلیل پویا[7] [24] یا تحلیل ایستا[8] حل کنند [5].
تجزیه و تحلیل پویا
این شیوه ها از دادههای زمان اجرا[9] برای تشخیص جنبههای رفتاری الگوها استفاده میکنند. کی تی [22]، تنها از تجزیه و تحلیل پویا برای تشخیص الگوی "زنجیره مسئولیتها[10]" استفاده کرد اما نتیجهاش موفقیتآمیز نبود (به دلیل نامناسب بودن مکانیزم رخداد نگارى کردن پیام[11] و ناکافی بودن داده آزمایش). تجزیه و تحلیل پویا به پوشش خوبی از داده آزمایش به منظور اعمال هر مسیر اجرایی ممکن نیازمند است. چنین داده آزمایش اغلب موجود نیست. حتی اگر داده آزمایش هم موجود باشد، نتایج زمان اجرا ممکن است گمراه کننده باشند. چون چنین دادههایی اصولا برای تشخیص دادن رفتار الگوهای خاص، طراحی نشدهاند [5].
تجزیه وتحلیل ایستا
این روشها اصولا شیوه های تجزیه و تحلیل ایستا را به درخت معنایی منتزع[12] در بدنه متدها اعمال میکنند. مرجع [25] بیانیههای "ایجاد شی غیرحساس به مسیر"[13] را برای تشخیص الگوهای "[14]کارخانه انتزاعی" و"متد کارخانه"[15] استفاده کرد. برای شناسایی الگوها با ساختار و عملکرد مشابه، بیرون کشیدن هدف الگو در پیادهسازی، به منظور متمایزسازی آنها بسیار مهم است. اما اکثر چنین شیوههایی قادر نیستند هدف برنامه را بیرون بکشند [5].
در این کار، ابزارهای خودکار شناسایی الگوهای طراحی با دو عمل "پالایش" و "تصحیح برچسب" گسترش مییابند. عمل پالایش، بیشترین یا حتی همه مثبت کاذبهای تولید شده در خروجی ابزارهای خودکار را شناسایی میکند. درحالیکه تصحیح برچسب، هویت صحیح نمونه مثبت کاذب را (بر حسب اینکه مثبت کاذب، به دلیل شباهت با کدام الگو مثبت کاذب شده است) با استفاده از معیارهای تعریف شده در این کار و روشهای دادهکاوی شناسایی میکند. به طور مثال اگر نمونه شناسایی شده توسط ابزارهای خودکار، با برچسب "استراتژی" شناسایی شده است اما در حقیقت این نمونه استراتژی نبوده، ابتدا به عنوان مثبت کاذب شناخته میشود (پالایش)، سپس برچسب صحیح آن (بر حسب مقادیر معیارها) تشخیص داده میشود.
به طورمثال برچسب صحیح آن ممکن است الگوی "وضعیت" باشد. بنابراین برچسب استراتژی به وضعیت تغییر میکند. با استفاده از این معیارها و روشهای دادهکاوی علاوه برنمونههای مثبتکاذب، نمونههای منفیکاذب نیز در برخی موقعیتها کاهش مییابند. چون وقتی یک برچسب تصحیح میشود مثلا از استراتژی به وضعیت، ممکن است این نمونه وضعیت جزء نمونههای شناسایی شده برای الگوی وضعیت نباشد، بنابراین این نمونه وضعیت یک منفیکاذب شمرده شده که با شناسایی آن، یک منفی کاذب را حذف کردهایم.
با توجه به اینکه ابزارها و روش های پیشین، بیشترین مثبت کاذب را در شناسایی الگو های با ساختار و عملکرد مشابه تولید میکنند، در اینکار، سعی شده تا خروجی ابزارها با توانایی شناسایی چنین الگوهایی تصحیح گردد. لذا، تصحیح برچسب روی نمونههای استخراج شده الگوی استراتژی (به دلیل داشتن شباهتهای ساختاری و عملکردی با الگوهای دیگر، بر حسب خروجی ابزارها بیشترین مثبت کاذب در شناسایی آن تولید شده است) انجام میشود. ابتدا براساس روشهای عرف دادهکاوی، با نمونههای مثبت کاذب و مثبت صحیح الگوی استراتژی بدست آمده توسط ابزارها، یک مجموعه داده تهیه شده است. سپس بر اساس مستندات موجود و همچنین بازبینی دستی، به منظور پیشبینی هویت صحیح هر نمونه، دو ستون در مجموعه داده تعیین شده است. یک ستون با "درست" و "نادرست" (درست، در صورت شناسایی صحیح توسط ابزارها و نادرست در صورت مثبت کاذب بودن) برچسب میخورد، و ستون دیگر با نام الگو صحیح آن نمونه یا در صورت ناشناس بودن، با بدون الگو برچسب میگیرد. سپس مقادیر معیارها یا پیشبینی کنندههای استخراج شده در این کار، روی هر نمونه محاسبه میشوند و نهایتآَ مجموعه داده در اختیار الگوریتمهای دادهکاوی جهت مدلسازی قرار میگیرند. در مدلسازی سعی میشود دانش موجود در دادهها، در قالب یک سری قوانین استخراج شوند. این قوانین برای شناسایی نمونههای ناشناخته (جدید) در مجموعه داده مورد استفاده قرار میگیرند.
آزمایشها، با استفاده از سه الگوریتم یادگیری ماشینC5.0 ، Boostingو SVMانجام شده است. روش پیشنهادی روی سه نرم افزارمتن باز jhotdraw6[6]، jrefactory[7] و javaio [8] انجام شده است. الگوهای پیاده شده در این پروژهها از ساختار پایهای که برای آنها در کتابها معرفی شده است بسیار فاصله گرفتهاند (الگو ها بسیار انعطاف پذیر هستند و توسط هر برنامهنویس میتوانند به روشهای متفاوتی پیادهسازی شوند و هم چنین ترکیب شوند) بنابراین شناسایی چنین الگوهایی دشواریهای خاص خودش را دارد [2].
در این کار، معیارهای جدید به عنوان پیشگویی کنندههای عملیات تصحیح برچسب و پالایش، روی نمونههای خروجی الگوی طراحی "استراتژی" یافت شده توسط ابزارهای [9] SSA و [5] PINOT استفاده شدهاند. ابتدا مثبت کاذبهای استراتژی تشخیص داده میشوند و سپس الگوی طراحی صحیح موجود در نمونه مثبت کاذب شناسایی میشود. نمونههای مثبت کاذب به سمت نمونههای مثبت صحیح با تشخیص آنها از الگوهای "وضعیت[16]"، "استراتژی[17]"، "تطبیقدهنده[18]"، "فرمان[19]"، "ملاقاتکننده[20]"، "میانجی[21]"، "آذیین کننده[22]"، "ترکیب[23]" و"کارخانه انتزاعی[24]"حرکت میکنند. همچنین این معیارها میتوانند الگوهایی که ساختار کاملا مشابهی به یکدیگر دارند نظیر"وضعیت از استراتژی "، "تطبیق دهنده از فرمان"، "آذیین کننده از ترکیب" و استراتژی را از هشت الگوی دیگر مورد مطالعه در این تحقیق متمایز کنند. این الگوها در نظر گرفته شدند، چون بیشترین مثبت کاذب موجود در نتایج الگوی استراتژی با اشتباه گرفتن با این الگوها بر حسب ساختار و عملکرد مشابه تولید شده است.
به طور کلی غیر از الگوهایی که از پایه ساختار یکسانی دارند بقیه الگوها به دلیل انعطاف، وقتی که از ساختار پایه دور میشوند ساختار مشابهی به برخی الگوهای دیگر پیدا میکنند. در واقع معیارهای استخراج شده در این کار، با استفاده از الگوریتمهای دادهکاوی، نقصها و کمبودهای دیده نشده در ابزارها را رفع میکنند.
ادامه این تحقیق به بخشهای زیر سازماندهی میشود. در بخش دوم بر چند مقاله که اهداف و شیوه مشابهای با شیوه و هدف این تحقیق دارند، مروری خواهیم داشت. در بخش سوم الگوهای مورد مطالعه در این تحقیق و معیارهای استخراج شده شرح داده میشوند. در بخش چهارم نگاهی بر شیوههای دادهکاوی و مجموعه داده ایجاد شده خواهیم داشت. در بخش پنجم نتایج ارائه خواهند شد و نهایتا در بخش ششم نتیجهگیری و کارهای آتی پیشنهاد میشوند.
فرضیات و محدودیت های مساله
فهرست پایان نامه گسترش ابزار های خودکار شناسایی الگو های طراحی با عملیات پالایش و تصحیح برچسب
فهرست:
مقدمه............................................................................................................8
فرضیات و محدودیت های مساله.......................................................................12
ضرورت انجام تحقیق............................................................................................13
هدف از انجام تحقیق............................................................................................13
سرفصل مطالب......................................................................................................14
تعاریف و مفاهیم اولیه....................................................................................17
مقدمه.....................................................................................................................17
تکنیک های طبقه بندی....................................................................................18
معیارهای ارزیابی کارایی....................................................................................19
جمع بندی............................................................................................................21
مروری بر تحقیقات پیشین..........................................................................23
مقدمه.............................................................................................23
مطالعات قبلی در شناسایی خودکار و نیمه خودکار الگوهای طراحی و محدودیت هایشان............................................................................................24
جمع بندی.........................................................................................................28
تولید مجموعه داده ......................................................................................30
مقدمه.................................................................................................................30
معیارهای استخراج شده................................................................................31
چارچوب آنالیز جهت شناسایی اولیه و تصحیح برچسب الگوهای طراحی........................................................................................................48
جمع بندی.......................................................................................50
آزمایشات و نتایج عددی...............................................................................51
مقدمه.........................................................................................................52
کارایی یادگیری.......................................................................................52
جمع بندی.................................................................................................56
نتیجه گیری و کارهای آتی.............................................................................58
فهرست منابع و مآخذ.....................................................................................59
چکیده به زبان انگلیسی ................................................................................62
منبع:
فهرست منابع و مآخذ
[1] E. Gamma, R. Helm, R. Johnson, and J. Vlissides. Design Patterns : Elements of Reusable Object-Oriented Software. Addison-Wesley Pub Co, 1995.
[2] J.M. Smith and D. Stotts, “SPQR: Flexible Automated Design Pattern Extraction from Source Code,” Proc. 18th IEEE Int’l Conf. Automated Software Eng. (ASE ’03), Oct. 2003.
[3] Z. Balanyi and R. Ferenc. Mining Design Patterns from C++ Source Code. In Proceedings of the 19th International Conference on Software Maintenance (ICSM 2003), pages 305–314. IEEE Computer Society, Sept. 2003.
[4] R. Ferenc, ´A. Besz´edes, L. Fulop, and J. Lele. Design pattern mining enhanced by machine learning. In ICSM, pages 295–304, 2005.
[5] N. Shi and R. A. Olsson, “Reverse engineering of design patterns from java source code,” in ASE’06. Washington, USA: IEEE Computer Society, 2006, pp. 123–134.
[6]http://www.javaworld.com/javaworld/jw-02-2001/jw-0216-jhotdraw.html, Accessed April 2013.
[7] Jrefactory, http://jrefactory.sourceforge.net/,2006, Accessed April 2013.
[8] http://sewiki.iai.uni-bonn.de/research/dpd/benchmarks/start, Accessed April 2013.
[9] N. Tsantalis, A. Chatzigeorgiou, G. Stephanides, and S. T. Halkidis, “Design pattern detection using similarity scoring,” IEEE TSE, vol. 32, no. 11, pp. 896–909, 2006.
[10] G. Antoniol, R. Fiutem, and L. Cristoforetti. Using Metrics to Identify Design Patterns in Object-Oriented Software. In Proceedings of the Fifth International Symposium on Software Metrics (METRICS98), pages 23–34. IEEE Computer Society, Nov. 1998.
[11] M. Zanoni. MARPLE: discovering structured groups of classes for design pattern detection. Master’s thesis, Università degli studi di Milano-Bicocca, Milano, Italy, July 2008.
[12] M. Zanoni. Data mining techniques for design pattern detection. PhD’s thesis, Università degli Studi di Milano Bicocca, 2012.
[13] S. Uchiyama, H. Washizaki, Y. Fukazawa and A. Kubo, Design Pattern Detection using Software Metrics and Machine Learning.
[14] J. Cooper, design patterns java companion, Addison- Wesley, 1998.
[15]A. Binun and G. Kniesel. Joining Forces for Higher Precision and Recall of Design Pattern Detection, in proceeding of the 16th conference on software maintenance and reengineering (CSMR2012), March 27-30, Washington, DC, USA, 2012. IEEE Computer society.
[16] Clementine 12, copyright(c) integral solutions ltd, help-modeling nodes, (1994-2007)
[17] J. Han, M. Kamber and J. Pei, Data Mining third edition: concepts and techniques, M. Kaufmann pub, 2011.
[18] J. Bansiya. Automating design-pattern identification –DP++ is a tool for C++ programs. Dr. Dobbs Journal, 1998.
[19] R. Keller, R. Shauer, S. Robitaille, and P. Pag´e. Patternbased reverse-engineering of design components. In Proc. Of the 21st International Conference on Software Engineering, pages 226–235. IEEE Computer Society Press, May 1999.
[20] A. Asencio, S. Cardman, D. Harris, and E. Laderman. Relating expectations to automatically recovered design patterns.In WCRE, pages 87–96, 2002.
[21] M. Vok´aˇc. An efficient tool for recovering design patterns from C++ code. Journal of Object Technology, 5(2), March-April 2006.
[22] K. Brown. Design Reverse Engineering and Automated DesignPattern Detection inSmallTalk. Master’s thesis, North Carolina State University, 1998.
[23] http://courses.cs.vt.edu/cs2604/spring04/Notes/C04.AlgorithmAnalysis.pdf
[24] M. Birkner, object oriented design pattern detection using static and dynamic analysis in java software, master thesis, university of applied sciences bonn-rhein-sieg sankt augustin, Germany august 2007.
[25] FUJABA. http://www.fujaba.de, Accessed May 2013
[26] S. Alhusain, S. Coupland, R. John AND M. Kavanagh. Towards Machine Learning Based Design Pattern Recognition. Computational intellingent, (UKCI) 2013.
[27] Y. Freund AND R.E. Schapire. A Short Introduction to Boosting, Proc. Journal of Japanese Society for Artificial Intelligence, 14(5):771-780, September, 1999.
[28] P. W˛egrzynowicz and K. Stencel. "Relaxing Queries to Detect Variants of Design Patterns". Computer Science and Information Systems (FedCSIS), 2013 Federated Conference.
[29] R.S. Rao and M. Gupta. "Design Pattern Detection by Sub Graph Isomorphism Technique". International Journal of Engineering and Computer Science, 2013.