دانشکده مهندسي برق و کامپيوتر
پايان نامه کارشناسي ارشد در رشته مهندسي کامپيوتر(نرم افزار)
گسترش ابزارهاي خودکار شناسايي الگوهاي طراحي با عمليات پالايش و تصحيح برچسب
به کوشش:
زينب اسمعيل پور
استاد راهنما :
دکتر اشکان سامي
اسفند 1392
به نام خدا
اظهارنامه
اينجانب زينب اسمعيلپور (909653) دانشجوي رشته مهندسي كامپيوتر گرايش نرمافزار دانشکده مهندسي برق و كامپيوتر اظهار ميكنم كه اين پاياننامه حاصل پژوهش خودم بوده و هر جايي كه از منابع ديگران استفاده كردهام، نشاني دقيق ومشخصات كامل آن را نوشتهام. همچنين اظهار ميكنم كه تحقيق و موضوع پايان نامهام تکراري نيست و تعهد مينمايم كه بدون مجوز دانشگاه دستاوردهاي آن را منتشر ننموده و يا در اختيار غير قرار ندهم. كليه حقوق اين اثر مطابق با آيين نامه مالکيت فکري و معنوي، متعلق به دانشگاه شيراز است.
نام و نام خانوادگي: زينب اسمعيل پور
تاريخ و امضا
19/12/92
تقديم به : خدايي که آفريد
. جهان را، انسان را، عقل را، علم را، معرفت را، عشق را
خداوندا به ما توفيق تلاش در شکست، صبر در نوميدي، رفتن بي همراه، جهاد بي سلاح، کار بي پاداش، فداکاري در سکوت، دين بي دنيا، مذهب بي عوام، عظمت بي نام، خدمت بي نان، ايمان بي ريا، خوبي بي نمود، گستاخي بي خامي، مناعت بي غرور، عشق بي هوس، تنهايي در انبوه جمعيت و دوست داشتن بي آنکه دوست بداند، را عنايت فرما

سپاسگذارم از :
آنان که ناتوان شدند تا ما به توانايي برسيم…
موهايشان سپيد شد تا ماروسفيد شويم…
و عاشقانه سوختند تا گرمابخش وجود ما و روشنگر راهمان باشند…
پدرم ، مادرم و استادانم.
سپاس آن خدايي که آفريد حرکت و برکت را.
تشکر و سپاس ويژه را بعد از خداي عزوجل تقديم به استادان گرانقدر م جناب آقاي دکتر سامي ،جناب آقاي دکتر بوشهريان و جناب آقاي دکتر فخر احمد که دراين تحقيق مرا ياري کردند ، دارم.
چکيده
گسترش ابزارهاي خودکار شناسايي الگوهاي طراحي با عمليات پالايش و تصحيح برچسب
به کوشش
زينب اسمعيل پور
الگوهاي طراحي، راهحلهاي اثبات شده و قابل اطميناني هستند که، براي پاسخ به برخي از مسائل با رخداد مکرر در طراحي نرم افزار شيگرا، ارائه شدهاند.‌ شناسايي آنها درکد، به منزله بازيابي طرح و هدف مخفي طراح و سهولت در امر نگهداشتپذيري است. از آنجاييکه سهولت در نگهداشتپذيري سيستم بسيار مهم و اجتناب ناپذير است، لذا توليد ابزارهاي خودکار براي شناسايي الگوها، مورد توجه قرار گرفت. اکثر ابزارهاي شناسايي کنوني درصد بازيابي بالايي دارند. اما در شناسايي الگوها، به ويژه با ساختار و عملکرد مشابه، مثبت کاذب بالايي توليد ميکنند. از اينرو عملگر پالايش نيز پيشنهاد شد. پالايش، سعي بر شناسايي مثبتهاي کاذب، و حذف آنها دارد. در اين کار، يک عملگر جديد به نام “تصحيح برچسب” ارائه شده است. اين عملگر ابتدا مثبتهاي کاذب را شناسايي، سپس بجاي اينکه آنها را از خروجي حذف کند، هويت صحيح آنها را به کمک يک مجموعه معيارجديد معرفي شده در اين کار، تشخيص و برچسب مثبت کاذب را تصحيح ميکند. خودکارسازي عملگر با دادهکاوي است. نتايج حاصل از روش ارائه شده، با دقت يادگيري 97.8% در دستهبندي “چندبرچسبه”، با متوسط 99.3% در دستهبندي “يکي درمقابل همه”و متوسط 99.6% در دستهبندي “دو به دو” خروجي ابزارها را تصحيح ميکند.
فهرست مطالب
عنوان صفحه
1- مقدمه………………………………………………………………………………………………8
1-1- فرضيات و محدوديت هاي مساله……………………………………………………………..12
1-2- ضرورت انجام تحقيق………………………………………………………………………………..13
1-3- هدف از انجام تحقيق………………………………………………………………………………..13
1-4- سرفصل مطالب…………………………………………………………………………………………14
2- تعاريف و مفاهيم اوليه…………………………………………………………………………17
2-1- مقدمه………………………………………………………………………………………………………17
2-2- تکنيک هاي طبقه بندي…………………………………………………………………………18
2-3- معيارهاي ارزيابي کارايي…………………………………………………………………………19
2-4- جمع بندي………………………………………………………………………………………………21
3- مروري بر تحقيقات پيشين………………………………………………………………..23
3-1- مقدمه…………………………………………………………………………………23
3-2- مطالعات قبلي در شناسايي خودکار و نيمه خودکار الگوهاي طراحي و محدوديت هايشان………………………………………………………………………………..24
3-3- جمع بندي……………………………………………………………………………………………28
4- توليد مجموعه داده …………………………………………………………………………..30
4-1- مقدمه…………………………………………………………………………………………………..30
4-2- معيارهاي استخراج شده……………………………………………………………………..31
4-3- چارچوب آناليز جهت شناسايي اوليه و تصحيح برچسب الگوهاي طراحي…………………………………………………………………………………………..48
4-4- جمع بندي……………………………………………………………………………50
5- آزمايشات و نتايج عددي…………………………………………………………………….51
5-1- مقدمه……………………………………………………………………………………………52
5-2- کارايي يادگيري……………………………………………………………………………52
5-3- جمع بندي…………………………………………………………………………………….56
6- نتيجه گيري و کارهاي آتي…………………………………………………………………..58
– فهرست منابع و مآخذ………………………………………………………………………….59
– چکيده به زبان انگليسي ……………………………………………………………………..62

فهرست جدول ها
عنوان صفحه
جدول2-1ماتريس درهم……………………………………………………………………………………………….19
جدول 4-1بخش کوچکي از مجموعه داده براي عملگر تصحيح برچسب……………………49
جدول4-2 بخش کوچکي از مجموعه داده براي عملگر پالايش…………………………………50
جدول 5-1ارزيابي دقت بکارگيري معيارها و روش دادهکاوي C5.0 با روش يکي در مقابل همه………………………………………………………………………………………………………………………………………..53
جدول 5-2 ارزيابي دقت بکارگيري روش دادهکاوي SVMو معيارها با روش يکي در مقابل همه………………………………………………………………………………………………………………………………………..53
جدول 5-3 ارزيابي دقت بکارگيري روش دادهکاويBoosting و معيارها با روش يکي در مقابل همه……………………………………………………………………………………………………………………………..54
جدول 5-4 ارزيابي دقت بکارگيري روش دادهکاوي SVM و معيارها با روش دو در دو…………………………………………………………………………………………………………………………………………..55
جدول 5-5 ارزيابي دقت بکارگيري روش دادهکاوي Boosting و معيارها با روش دو در دو…………………………………………………………………………………………………………………………………………..55
جدول 5-6 ارزيابي دقت بکارگيري روشهاي دادهکاوي و معيارها با روش چند برچسب………………………………………………………………………………………………………………………………….55
فهرست شکل ها
عنوان صفحه
شکل4-1الگوي استراتژي………………………………………………………………………………32
شکل4-2يک نمونه الگوي استراتژي حقيقي………………………………………………32
شکل4-3 رابط هاي يک نمونه الگوي استراتژي حقيقي……………………………..33
شکل4-4ترتيب فراخواني از رابط هاي يک استراتژي حقيقي………………………33
شکل 4-5 الگوي وضعيت…………………………………………………………………………….35
شکل 4-6الگوي تطبيق دهنده شي…………………………………………………………..37
شکل4-7الگوي کارخانه انتزاعي……………………………………………………………….39
شکل4-8الگوي فرمان………………………………………………………………………………40
شکل4-9شباهت ساختاري الگوي فرمان و تطبيق دهنده شي………………..41
شکل4-10 الگوي ملاقات کننده……………………………………………………………….42
شکل4-11 الگوي ميانجي………………………………………………………………………….43
شکل4-12الگوي آذيين کننده……………………………………………………………………44
شکل4-13الگوي ترکيب…………………………………………………………………………..46
شکل 4-14 مراحل ايجاد مدلهاي تصميمگيري……………………………………..49
شکل 5-1 بهبود روي ابزار شناسايي خودکار الگوهاي طراحي ” SSA”…..55
شکل 5-2 بهبود روي ابزار شناسايي خودکار الگوهاي طراحي ” PINOT “…56
فصل اول
1-مقدمه
اگرچه طراحي يک نرمافزار شيگرا دشواريهاي خاص خود را دارد، دشوارتر از آن، طراحي يک نرمافزار شيگرا با قابليت استفاده مجدد است. الگوهاي طراحي، استفاده از طراحيها و معماريهاي موفق را آسان ميکنند [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″حرکت ميکنند. همچنين اين معيارها ميتوانند الگوهايي که ساختار کاملا مشابهي به يکديگر دارند نظير”وضعيت از استراتژي “، “تطبيق دهنده از فرمان”، “آذيين کننده از ترکيب” و استراتژي را از هشت الگوي ديگر مورد مطالعه در اين تحقيق متمايز کنند. اين الگوها در نظر گرفته شدند، چون بيشترين مثبت کاذب موجود در نتايج الگوي استراتژي با اشتباه گرفتن با اين الگوها بر حسب ساختار و عملکرد مشابه توليد شده است.
به طور کلي غير از الگوهايي که از پايه ساختار يکساني دارند بقيه الگوها به دليل انعطاف، وقتي که از ساختار پايه دور ميشوند ساختار مشابهي به برخي الگوهاي ديگر پيدا ميکنند. در واقع معيارهاي استخراج شده در اين کار، با استفاده از الگوريتمهاي دادهکاوي، نقصها و کمبودهاي ديده نشده در ابزارها را رفع ميکنند.
ادامه اين تحقيق به بخشهاي زير سازماندهي ميشود. در بخش دوم بر چند مقاله که اهداف و شيوه مشابهاي با شيوه و هدف اين تحقيق دارند، مروري خواهيم داشت. در بخش سوم الگوهاي مورد مطالعه در اين تحقيق و معيارهاي استخراج شده شرح داده ميشوند. در بخش چهارم نگاهي بر شيوههاي دادهکاوي و مجموعه داده ايجاد شده خواهيم داشت. در بخش پنجم نتايج ارائه خواهند شد و نهايتا در بخش ششم نتيجهگيري و کارهاي آتي پيشنهاد ميشوند.
1-1- فرضيات و محدوديت هاي مساله
الگوها با قرارگيري در موقعيتهاي متفاوت مسائل حقيقي، در اکثر مواقع تا حد زيادي ممکن است از ساختار پايه خود فاصله بگيرند. الگوها با دست برنامه نويس براي حل يک مساله عمومي در يک زمينهي خاص سمت و سو ميگيرند. از طرفي الگوها علاوه بر جنبه ساختاري داراي جنبههاي رفتاري متفاوتي نيز هستند. بطوريکه گاهي فقط رفتار است که دو الگو را از هم متمايز ميکند. يکي از محدوديتهاي الگوهاي طراحي، انعطافپذيري و ساختار و عملکرد مشابه بين آنها است. بنابراين در اين پايان نامه سعي شده است که مجموعه کاملي از انعطافپذيريهاي هر الگو به علاوه يک سري ويژگيهاي رفتاري متمايز کننده ديده شود و معيارهايي پابرجا براي بيان ثابتي از اينکه همه يک مجموعه انعطافات به کدام الگو مرتبط ميشوند استخراج شود و نهايتا اين معيارها به عنوان پيشگويي کنندهها همراه با تکنيکهاي دادهکاوي براي جستجو و تصحيح مثبت کاذبهاي الگوهاي شناسايي شده توسط ابزارهاي خودکار استفاده شوند. در هر صورت اين احتمال ميرود که انعطافات بيشتري براي هر الگو موجود باشد که در اين تحقيق ديده نشده است.
1-2- ضرورت انجام تحقيق
الگوهاي طراحي راهحلهاي اثبات شده و قابل اطمينان هستند که به منظور حل مسائلي که به طور مکرر در طراحي يک نرمافزار شيگرا رخ ميدهد، مورد استفاده قرار ميگيرند. بکارگيري صحيح الگوهاي طراحي و سند کردن آنها ميتواند به حد زيادي موجب بهبود صفات کيفيتي سيستم نظير قابليت استفاده مجدد و نگهداشت پذيري شود. اما بسياري از سيستم هاي نرمافزاري بزرگ به ويژه سيستمهاي نرم افزاري قديمي يا اصلا سند نشدهاند و يا اينکه سندکامل و دقيقي ندارند. بنابراين خودکارکردن شناسايي الگوهاي طراحي ميتواند مطلوب و مفيد واقع شود. تاکنون در زمينه شناسايي خودکار الگوهاي طراحي شيوههاي متنوعي پيشنهاد و پيادهسازي شده است اما هيچ يک از متدها نتوانستهاند خروجي بدون مثبت کاذب يا کمترين مثبت کاذب را داشته باشد. خصوصا براي الگوهايي که از نظر ساختاري با هم مشابه هستند و در رفتارشان متفاوت ميشوند و يا اينکه عملکرد مشابهي دارند، مثبت کاذب بيشتري در خروجي اين ابزارها ديده ميشود. بنابراين وجود شيوهاي که بتواند مثبت کاذب و منفي کاذب را در نتيجه شناسايي الگوها به حداقل برساند ميتواند کمک بسياري به حاصل شدن اطمينان توسعهدهنده در نگهداشت پذيري و قابليت استفاده مجدد بهتر نرمافزار کند.
1-3- هدف از انجام تحقيق
هدفي که در اين پايان نامه دنبال ميشود ارائه روشي براي رسيدن به حداکثر بهبود (حداقل مثبت و منفي کاذب) روي شناسايي الگوي طراحي و ايجاد خروجي بدون ابهام و صحيح براي استفاده توسط توسعه دهنده ميباشد. به علاوه جهت تسهيل در امر نگهداشتپذيري و استفاده مجدد نرم افزار نه تنها از نظر فهم راحت طرح و هدف سيستم، بلکه از نظر صرف وقت و هزينه ميباشد.
1-4- سرفصل مطالب
مطالب بيان شده در اين پايان نامه در قالب شش فصل گردآوري شده اند كه به طور خلاصه به شرح زير است.
فصل دوم : تعاريف و مفاهيم اوليه
دراين فصل مختصري بر روي مفاهيم اوليه روشهاي دادهکاوي و معيارهاي ارزيابي مدلهاي پيش بيني کننده در اين تحقيق خواهيم داشت.
فصل سوم : مروري بر تحقيقات پيشين
در اين بخش مروري بر مطالعات و تحقيقاتي که در زمينه شناسايي الگوهاي طراحي بيشترين شباهت از نظر هدف به کار ما را دارند خواهيم داشت.
فصل چهارم : توليد مجموعه داده ها
در اين فصل نحوه توليد مجموعه دادههاي لازم با استفاده از معيارهاي استخراج شده جهت عمليات پالايش و تصحيح برچسب ارائه ميشود.
فصل پنجم : آزمايشات و نتايج عددي
دراين فصل با استفاده از معيارهاي استخراج شده و تکنيکهاي دادهکاوي، مجموعهاي از آزمايشها جهت انجام عمليات پالايش و تصحيح برچسب الگوي استراتژي روي نتايج دو ابزار خودکارشناسايي الگوهاي طراحي SSA و PINOTانجام گرفته شرح داده ميشود. نتايج توليدي اين ابزارها مربوط به عمل شناساييشان روي سه پروژه ي متن باز jhotdraw ، jrefactory و javaio مي باشد. به علاوه نتايج عددي حاصل از اين آزمايشها و معيارهاي استخراج شده در اين فصل ارائه ميگردد.
فصل ششم : نتيجه گيري و پيشنهادات
جمع بندي مطالب گفته شده در پايان نامه در اين فصل انجام شده و همچنين پيشنهاداتي براي ادامه پژوهش در اين زمينه ارائه شده است.
فصل دوم
2- تعاريف و مفاهيم اوليه
2-1- مقدمه
دراين فصل مختصري بروي مفاهيم و تعاريف اوليه روشهاي دادهکاوي و معيارهاي ارزيابي مدلهاي پيش بينيکننده در اين تحقيق خواهيم داشت.

2-2- تکنيک هاي طبقه بندي25
در دادهکاوي با دو مجموعه داده مواجه هستيم، داده آموزشي و داده آزمايشي. صفات داده آموزشي را مجموعه معيارهايي تشکيل ميدهند که هويت موجوديتهاي قرارگرفته دررکوردها را پيشگويي ميکنند. موجوديتهاي دادهي آموزشي، مشاهداتي هستند که از قبل هويتشان شناسايي شده است. دادهي آموزشي حاوي يک ستون پيشگويي است. مقادير اين ستون، با برچسبهايي پر ميشوند که هويت اصلي موجوديتها را نشان ميدهد (مثلا درست يا غلط). داده آزمايشي حاوي مشاهداتي است که هويت اصليشان شناخته شده نيست. با تجزيه و تحليلي که به واسطه الگوريتمهاي دادهکاوي روي دادهي آموزشي صورت ميگيرد مدلهايي ساخته ميشود. مدلسازي، دانش موجود در مشاهدات داده آموزشي را در قالب يک سري قوانين استخراج ميکند. داده آزمايشي براي ارزيابي دقت پيشگويي مدل ساخته شده روي داده آموزشي بکار برده ميشود. در واقع پيشگويي يک فرايند دو مرحلهاي دارد، فاز يادگيري و فاز دستهبندي.
‌‌‌در فاز يادگيري بر اساس مجموعه دادهي آموزشي، مدل طبقهبند ساخته ميشود و در فاز طبقهبندي بر اساس مدل ساخته شده در فاز قبل، مجموعه داده جديد که در فاز يادگيري استفاده نشده است (مجموعه داده آزمايشي) دستهبندي ميشود (پيشگويي ميشود که مشاهدات جديد چه برچسبي به خود بگيرند). جهت خودکار سازي عملگر تصحيح برچسب در اين تحقيق، از روشهاي دادهکاوي (الگوريتمهاي طبقه بندي) استفاده شده است [17].
دقت مدل، درصد نمونههايي از مجموعه داده آزمايش است که به درستي طبقه بندي شدهاند. مجموعه داده لازم جهت ساخت مدل طبقه بندي، از متغيرهاي مستقل و وابسته تشکيل شده است. متغيرهاي مستقل همان خصيصهها هستند که جهت طبقه بندي متغير وابسته که در واقع بر چسب کلاسها مي باشد، مورد استفاده قرار ميگيرند [17]. توضيح مختصري در مورد انواع طبقهبنديهايي که در اين تحقيق مورد استفاده قرار گرفته اند در ادامه آمده است.
2-2-1- طبقه بند C5.0
اين طبقه بند در واقع براساس تقسيم مبتني بر نمونه روي فيلدي که بيشترين سود اطلاعاتي را با خود دارد، کار ميکند. سپس هر زيرنمونه تعريف شده با اولين تقسيم، دوباره تقسيم ميشود (معمولا بر اساس يک فيلد متفاوت). اين فرايند تکرار ميشود تا اينکه هيچ زيرنمونه قابل تقسيم نداشته باشيم. سرانجام پايين ترين سطح تقسيم ها دوباره بررسي مي شوند. آنهايي که تاثير قابل توجهي بر مقدار مدل ندارند حذف يا هرس ميشوند [16].
2-2-2- طبقه بند SVM
يک طبقه بند و الگوريتم رگرسيون است که از تئوري يادگيري ماشين با حداکثر دقت پيش بيني بدون” اُور فيتينگ26 ” داده ها استفاده ميکند. اين روش از يک تبديل غير خطي بر داده هاي يادگيري استفاده ميکند، و با جستجوي براي تساوي هاي رگرسيون در دادههاي تبديل شده کلاسها (اهداف) را جدا ميکنند.SVM خصوصا براي آناليز دادهها با تعداد زيادي از فيلدهاي پيش گويي کننده مناسب ميباشد [16].
2-2-3- طبقه بند BOOSTED C5.0
يک الگوريتم دادهکاوي است که براي کاهش خطاي الگوريتمهاي يادگيري ضعيف (به آرامي به سمت طبقه بندي صحيح ميل ميکنند) مورد استفاده قرار ميگيرد و آنها را به يک الگوريتم يادگيري قوي تبديل ميکند. در اين کار براي قدرت بيشتر بخشيدن به الگوريتم تصميم گيري C5.0 استفاده شده است [27].
2-3- معيارهاي ارزيابي کارايي
ارزيابي دقت مدلهاي پيشبينيکننده اين تحقيق براي عملگر تصحيح برچسب، برحسب نسبت تعداد تصميم گيريهاي درست از سيستمهاي يادگيري در مقايسه با طبقه بندي دستي به تعداد کل کانديدا است. ماتريس درهم27 جهت ارزيابي طبقه بنديهاي دودويي ميباشد که در اين تحقيق براي ارزيابي بخش پالايش نمونهها وتصحيح برچسب استفاده ميشود [17]. همانطور که در جدول 2-1 مشاهده مي شود ماتريس درهم کلاس هاي واقعي را در مقابل کلاس هاي پيش بيني شده در داده آزمايش نشان ميدهد.
ماتريس درهم شامل چهار قسمت مي باشد :
مثبت صحيح (TP28) : تعداد نمونههاي استراتژي که به درستي استراتژي پيش بيني شدهاند.
مثبت کاذب (FP29) : تعداد نمونههاي غير استراتژي که به اشتباه استراتژي پيش بيني شده اند.
منفي کاذب (FN30): تعداد نمونههاي استراتژي که به اشتباه استراتژي غلط پيش بيني شده اند.
منفي صحيح (TN31) : تعداد نمونههايي که غير استراتژي بودهاند و به درستي پيش بيني شده که استراتژي غلط هستند.
چند معيار کارايي از ماتريس درهم بدست ميآيد که در زير تشريح ميشوند:
Precision : درصد درستي الگوهايي که شناسايي شده اند.
: Accuracy درصد نمونههاي الگو و بدون الگويي که به درستي با نام الگو يا بدون الگو شناسايي شدهاند.
نرخ مثبت صحيح (TPR) : درصد الگوهايي که به درستي شناسايي شدهاند ( همان Recall است) .
معيارهاي فوق در اين تحقيق به منظور ارزيابي دو عملگر پالايش و تصحيح برچسب استفاده ميشوند.
2-4- جمع بندي
در اين فصل به طور خلاصه چند طبقه بند که براي ساخت مدل در اين تحقيق استفاده شده است، بررسي گرديد. در نهايت هم معيارهاي ارزيابي مدلها ارائه گرديد.
فصل سوم
3- مروري بر تحقيقات پيشين
3-1- مقدمه
محققان بسياري در زمينه خودکار يا نيمه خودکارسازي شناسايي الگوهاي طراحي از کد منبع يا طراحي کار کردهاند. در ادامه اين بخش، به طور خلاصه بر برخي از تحقيقاتي که از نظر هدف و يا شيوه کار شباهت بيشتري به تحقيق ما دارند مروري خواهيم داشت.
3-2- کارهاي مرتبط
در سال 1998 [10] يک روش سه مرحلهاي براي شناسايي الگوها ارائه شد. ابتدا از طريق محاسبه مقادير يک سري معيارهاي عام شيگرا، نظير شمارش تعداد صفات، تعريفها، و … براي هر کلاس موجود در کد و هر نقش الگوي مورد جستجو، کانديدهاي هر نقش شناسايي شد. در گام اول، فضاي جستجو (از طريق حذف کلاسهايي که کانديد نشدند) تا حد زيادي کاهش داده شد. در مرحله دوم از طريق مسأله کوتاهترين مسير، نزديکترين مسير بين کانديدهايي که ميتوانند به هم مرتبط شوند، شناسايي شد. سپس هر ترکيب بدست آمده از مرحله دوم به عنوان کانديدهاي الگوي مورد جستجو شناخته شد. در مرحله سوم به دليل وجود مثبت کاذب بسيار زياد در مرحله دوم، از محدوديت واگذاري مسئوليت استفاده شد. چنانچه الگويي بايد اين محدوديت را داشته باشد، ترکيب بدست آمده از مرحله دو، براي داشتن اين محدوديت مورد بررسي قرار داده شد، چنانچه چنين محدوديتي نداشت آن ترکيب حذف ميشد. با اين حال، روش [10]، ميزان مثبت کاذب بالايي دارد. عيب اصلي [10]، در محوريت اصلي کارشان، استفاده از معيارهاي عام شيگرايي بود که از پايه با هدف سنجش الگوها استخراج نشده بودند.
درسال 2005 [4]، بجاي ابداع يک ابزار جديد، يک روش پالايش ابزار خودکار ارائه داد. ورودي پالايش، خروجي ابزار 2003 [3] بود که توسط خودشان ابداع شده بود و ميزان مثبت کاذب بالايي داشت. در[4]، براساس انعطافپذيريها و تنوع پيادهسازيهاي هر الگو، يک سري معيار استخراج شد. اين معيارها از پايه با هدف سنجش و بررسي حضور الگوها استخراج شدند. روش کار به اين صورت بود که خروجي بدست آمده از ابزار[3]، به صورت دستي تجزيه و تحليل شد، و هر نمونه شناسايي شده، مورد بازبيني قرار گرفت. بطوريکه اگر نمونه به درستي شناسايي شده بود، برچسب درست، و اگر ابزار در شناسايي آن دچار اشتباه شده بود، برچسب نادرست ميگرفت. سپس يک مجموعه داده تهيه شد. نمونهها به عنوان رکوردهاي آن، معيارها به عنوان صفات توصيف کننده نمونهها، و هويت آنها (درست و نادرست) به عنوان ستون خروجي مجموعه داده قرار گرفت. نهايتا با استفاده از الگوريتمهاي دادهکاوي و مقادير معيارها روي نمونهها، يک سري قوانين استخراج شد که با کمک آنها ميتوان نمونههاي ناشناخته در مجموعه داده را تعيين هويت کرد.
کار[4] انجام شد تا، نمونههاي مثبت کاذب ابزار شناسايي، و از خروجي حذف شوند. پالايش [4]، خروجي [3] را تاحد زيادي بهبود داد، اما معيارهاي [4]، تنها بر اساس تنوع پيادهسازيهاي يک الگو استخراج شده بودند و ساختار و عملکرد مشابه الگوهاي ديگر در توليد معيارها در نظر گرفته نشده بودند. از طرفي با اينکه حذف نمونههاي مثبت کاذب خروجي مطمئنتري را در اختيار توسعه دهنده قرار ميدهد، در همان حال، خيلي از اطلاعات را نيز از بين ميرود.
فرانسيسکا و همکارانش [12][11] ابزاري تحت نام مارپل متشکل از پنج ماژول اصلي را توسعه دادند. اين ابزار نه تنها فعاليت شناسايي الگوهاي طراحي را بلکه بازسازي32 معماري نرم افزار را نيز پشتيباني ميکند. اولين ماژول آن، موتور شناسايي33 اطلاعات ناميده ميشود اين ماژول مدلي از سيستم ميسازد و يک سري معيارها و ساختارهاي ريز را جمع آوري ميکند. دومين ماژول که وصل کننده 34 ناميده ميشود تمام کانديداي الگوهاي طراحي که معيارهاي يک تعريف داده شده از هر الگو را برآورده ميکنند استخراج ميکند. سومين ماژول، طبقه بندي است که کمک ميکند مثبت کاذب هاي بخش قبلي را شناسايي کرده و شباهت آنها را با پياده سازيهاي صحيح هر الگوي مورد نظر، با انتساب مقادير اطمينان مختلف35 مورد سنجش قرار ميدهد. دو ماژول آخر جهت بازسازي معماري نرم افزار مورد استفاده قرار ميگيرند. معيارهاي اندازه گيري شده توسط مارپل، معيارهاي شيگرايي هستند که در توليد بعضي از منظرهاي معماري بهرهگيري ميشوند. بخش يادگيري ماشين از فرايند شناسايي، توسط ماژول سوم پياده سازي ميشود که کانديداي استخراج شده از ماژول دوم را به عنوان ورودي ميگيرد و سپس از الگوريتمهاي گروه بندي36 و طبقه بند موجود در نرم افزار weka37 براي پالايش کردن نمونههاي مثبت کاذب استفاده ميکند. عمليات پالايش اين شيوه با محاسبه نمره مشابهت بين نمونه صحيح هر الگو با کانديداي شناسايي شده انجام ميگيرد. نمره دهي بر حسب مشابهت، به ساختار پايه الگو بسيار محدود ميشود درحاليکه الگوهاي طراحي در خيلي از موقعيتها از ساختار پايه خود به دليل انعطاف پذيري که دارند، دور ميشوند.
ستورا و همکارانش [13] شيوهاي را ارائه دادند که بر اساس آن، کانديداي نقشهايي که ترکيب آنها کانديدهاي الگوها را تشکيل ميدهد، با اندازهگيري يک سري معيارها و تکنيکهاي دادهکاوي، جستجو ميشود. سپس با آناليز رابطهي بين کلاسي کانديدها، الگوي مورد نظر شناسايي ميشود. در اين شيوه سعي ميشود الگوهايي که ساختار مشابهي به يکديگر دارند از هم تشخيص داده شوند، اما در واقع معيارهاي استخراج شده براي الگوهايي با ساختار مشابه را دقيقا يکسان در نظر گرفتهاند و آنها را در يک گروه شناسايي ميکنند. در اين روش از تکنيک شرايط محدود کننده استفاده نميشود و خصوصا به همين دليل روششان آماده پذيرش مثبت کاذب بسياري ميباشد.
تي سن تا ليس و همکارانش [12][9] ابزاري به نام 38SSAارائه دادند. در SSA از يک الگوريتم نمرهدهي که نمره مشابهت هر زير گراف سيستم را (فضاي جستجو) با هر گراف الگوي مورد جستجو محاسبه ميکرد، استفاده شد. چون الگوريتم SSA خواص انتقال را در ارث بري و واگذاري مسئوليت در نظر ميگيرد، تنوع پيادهسازيهاي يک الگو که از ساختار پايه خود فاصله گرفتهاند را نيز شناسايي ميکند. SSA درصد بازيابي بالايي دارد، تعداد زيادي از الگوهاي موجود را شناسايي ميکند، به راحتي قابل استفاده است، و همچنين سرعت بالايي دارد. اما بدليل اينکه الگوريتم SSA تنها بر قواعد ساختاري تاکيد دارد، الگوهايي که ساختار يکساني دارند و تنها در رفتار متفاوت ميشوند، و يا آنهايي که عملکرد مشابهي دارند، توسط SSA قابل متمايز شدن نيستند و SSA آنها را در يک گروه شناسايي ميکند (مثل “وضعيت/ استراتژي”).
شي و همکارانش [5] ابزاري به نام 39PINOT ارائه دادند. در توليد PINOT از اين اصل استفاده شد،” باتوجه به اينکه هر الگوي طراحي بايد هدف مشخصي را برآورده کند، بنابراين بايد ازآن هدف، يک تعريف عملي در پيادهسازي آن الگو وجود داشته باشد”. در [5] سعي شد تا تعريف عملي مربوط به هدف هر الگو از پيادهسازي آن الگو بيرون کشيده شود، سپس PINOT براي شناسايي الگوها، تعاريف عملي بيرون کشيده شده را به عنوان محدوديتهاي اجباري با آناليز ايستا، جستجو کند. PINOTدرصد بازيابي بالايي دارد، تعداد زيادي از الگوها را شناسايي ميکند، سرعت کمتري نسبت به SSA دارد، و همانند SSA توانايي متمايز کردن الگوها با ساختار و عملکرد مشابه را ندارد. در اين تحقيق از دو ابزار SSA و PINOT براي انجام آزمايشات بهره گيري شده است.
[15] ابزاري با نام 40DPJF ارائه داد. در [15]، براي برخي از الگوها، تعدادي محدوديت يا الزام رفتاري جهت شناساييشان، ارائه شد. برخي از محدوديتهاي [15]، ثبات و قدرت متمايز کنندگي بالايي دارند. ابزار DPJF ادعا ميکند، صد در صد دقت دارد. اما بر اساس بررسيها و ارتباطات انجام شده با گروه [15]، ابزار DPJF تنها الگوي يگانه41را با چنين دقتي شناسايي ميکند. مثلا در مورد دقت شناسايي الگوي نماينده، برخي نمونههاي شناسايي شده توسط اين ابزار بعد از بررسي و ارتباطات با اين گروه مشخص شد که الگوي وضعيت هستند و نه الگوي نماينده. همچنين اين ابزار هنوز براي شناسايي الگوهاي با ساختار و عملکرد مشابه مثل استراتژي و وضعيت پيادهسازي نشده است. بنابراين مشخص نيست بعد از پياده سازي به چنين دقتي دست يابد.

در سال 2013 [26]، در تمام مراحل فرايند شناسايي الگوهاي طراحي (کاهش فضاي جستجو تا شناسايي کانديدهاي هر الگو) از دادهکاوي بهره گرفت. در مرجع [26]، ابتدا از تعدادي معيار عام سطح کلاس مثل عمق ارثبري، تعداد متدهاي رونويسي شده، و … به منظور جستجوي کانديدهاي هر نقش تشکيل دهنده الگوي مورد نظر در ميان کلاسهاي موجود در فضاي کد، با کمک شيوههاي دادهکاوي استفاده کرد. در مرحله بعد، با ترکيب کانديدهاي نقشهايي که ميتوانند به هم مرتبط شوند، کانديدهاي الگوي مورد جستجو استخراج شدند. سپس براي بررسي صحت يا عدم صحيت کانديدهاي مرحله دوم، يک مجموعه داده تهيه کردند. بطوريکه رکوردهاي آن را کانديدهاي مرحله دو، و صفات توصيف کننده آنها را معيارهاي مربوط به بررسي روابط ميان کلاسي و معيارهاي سطح کلاس مرحله يک تشکيل دادند. سپس براي تعيين هويت هر موجوديت (صحت يا عدم صحت ) از چهار ابزار خودکار شناسايي الگوهاي طراحي استفاده شد. بطوريکه اگر حداقل دو ابزار در رابطه با يک کانديدا رأي مثبتي داشتند، آن کانديد به عنوان نمونه صحيح در نظر گرفته ميشد. سپس از الگوريتمهاي دادهکاوي براي خودکارسازي فرايند تعيين هويت، به منظور شناسايي درستي نمونههاي جديد استفاده کردند.
با توجه به اينکه در دادهکاوي مهمترين عناصر، صفات توصيف کننده موجوديتها و صحت برچسب زني قبل از مدلسازي روي مجموعه داده است، ضعف کار [26] دردرجه اول، در استفاده از تعداد زياد معيارهايي است که با هدف سنجش الگوها استخراج نشده بودند، و دوم براي برچسب زني اوليه مجموعه داده، استفاده از ابزارهاي موجود شناسايي الگوهاي طراحي، که دقت کاملي ندارند و بديهي است که در فرايند برچسب زني دچار اشتباه شوند. اين روش با دقت نسبتا پاييني متوسط “49%” روبرو شد.
در سال 2013 [28]، يک روش پرسوجوي الگوهاي طراحي از پايگاه داده ارائه کرد. محور اصلي [28]، بکارگيري شيوهي اصولي براي سست کردن پرسوجوها بود، پرسوجوها به دو دسته تقسيم ميشدند، خاص و عام. خاص يعني تبديل خصوصيات الگو به يک پرسوجوي سخت براي شناسايي الگوهاييکه از ساختار پايه فاصله نگرفتهاند و عام، تبديل خصوصيات الگوها به يک پرسوجوي عام تر (با بهرهگيري از ويژگيهاي پيادهسازي متنوع يک الگو) براي نمونههايي که از ساختار پايه فاصله گرفتهاند، بطوريکه بتوان تنوع نمونههاي قابل قبول الگوهاي طراحي را پيدا کرد. نتايج اين کار تنها



قیمت: تومان


پاسخ دهید