فصل اول
کليات
1.1.مقدمه
آنچه که بين تمام علوم مشترک است، حجم وسيعي از اطلاعات و داده به شکلهاي مختلف است، که همراه با پيشرفت و وسعت علوم بزرگتر و ارزشمندتر ميشود. با رشد سريع علوم کامپيوتر و استفاده از آن در چند دهه اخير، تقريبا همه سازمانها در پروژههاي مختلف خود حجم عظيمي داده در پايگاههاي داده ذخيره ميکنند. اين سازمانها و کساني که به نوعي در پروژهها سهيم هستند به فهم اين دادهها و بهتر بگوييم کشف دانش نهفته در آن نيازمندند. اين نياز، باعث بهوجود آمدن حوزه جديد ميان رشتهاي کشف دانش و دادهکاوي1 شده است، که حوزههاي مختلف همچون پايگاه داده، آمار، يادگيري ماشين را براي کشف دانش ارزشمند نهفته در اطلاعات و دادهها را با هم تلفيق ميکند. اصطلاح Data Mining همانطور که از ترجمه آن به معني دادهکاوي مشخص مي‌شود، به مفهوم استخراج اطلاعات نهان، و يا الگوها وروابط مشخص در حجم زيادي از داده‌ها در يک يا چند بانک اطلاعاتي بزرگ است.
هر نرمافزار در طول فرآيندتوليد و پس از آن، انبوهي از اطلاعات و مستندات دارد که قابل کاوش و استفاده مفيد است. اين دادهها معمولا در پايگاه دادههايي بهنام مخازن نرمافزاري2 ذخيره و نگهداري ميشوند. مخازن نرمافزاري نمايش دقيقي از مسيرتوليد يک سيستم نرمافزاري ارائه ميدهند]1 .[هدف ازکاوش مخازن نرمافزاري3MSR استفاده هوشمند از تحليل دادههاي نهفته در آنها براي کمک به تصميمگيري هاي بهتر و سريعتر در پروژه توليد و پشتيباني آنها است. آنچه که در اينجا مورد توجه اين تحقيق است، استخراج اطلاعات مهم براي همه ذينفعان پروژه نرمافزاري است. اين اطلاعات از مجموعه دادههاي مرتبط با خطاهاي رخ داده در طول توليد و پشتيباني پروژه استخراج مي شود.
در سالهای گذشته مدلهاي مختلفي با استفاده از الگوريتمهاي دادهکاوي، تشابه متن و دستهبندي و خوشهبندي دادهها ارائه شده. اما از آنجا که جستجو و استخراج اطلاعات از ميان دادههاي متني نيازمند روشي هوشمند براي تطبيق جنبههاي معنايي و دستوري است، نياز به مدلهايي که از الگوريتمها معنايي استفادهکنند وجود دارد.در تحقيقهاي مورد مطالعه اين نياز حس ميشود.

سعي بر اين شده که با استفاده از الگوريتم معنايي برپايه مجموعه تشابه جملات4بر پايه LCS5]3[ و تشابه کلمات (SOC-PMI6 )]3[، روي مستندات ذخيره شده در مخازن خطاي نرمافزار، مانند راهحلهاي ارائه شده براي خطاهاي مشابه مدلهاي قبلي را تکميلکرده و جوابي بهينه و سريعتر براي خطای پيش آمده پيدا کنيم. همچنين ميتوان زماني تخميني نيز براي تصحيح خطا پيشبيني کرد تا راهنماي تيم توسعه و ذينفعان ديگر نرمافزار باشد. همچنين ديد بهتري نسبت به روند پيشرفت و تکامل نرمافزار مورد نظر ارائه شود.

2.1. تعريف مسئله
يکي از مراحل مهم و اساسي در مهندسي و توليد نرمافزار مرحله يافتن و رفع خطاهاي موجود در نرمافزار است. اين مرحله از توليد نرمافزار جزء وقتگيرترين و پرهزينه ترين مراحل به حساب ميآيد]4[. سالهاست که دانش دادهکاوي و استخراج دانش به کمک مهندسين نرمافزار آمدهاست. رفع خطا در فرآيند توليد بسته به مدل توسعه نرمافزار چندين بار انجام ميگيرد. خطاها و مشکلات برطرف شده معمولا به روشهاي مختلف تحت عنوان مخازن خطاي نرم افزار، مستندسازي و ذخيره ميشود. اين مخازن منابع عظيم دانش هستند، که کمک بزرگي در تسريع زمان توليد نرمافزار و پايينآوردن هزينهها خواهدبود]5[. روشهايي نيازاست که اين دانش و اطلاعات مفيد استخراج شود. در اين تحقيق روشي براي سرعت بخشيدن به رفعخطاي جديد با استفاده از اطلاعات موجود در مخازن خطاي نرمافزار، ارائه شدهاست. مدلهاي زيادي تا بهحال ارائهشده که يا مکمل هم بوده يا از الگوريتمهاي جديد استفاده شدهاست. مدلهاي پيشنهادي با استفاده از تشابه متن همگي از الگوريتمهاي معمولي و ساده استفاده کرده اند. در اين مدل ها به اين نکته مهم کمتر توجه شده که مخازن حجم بالا و پيچيدهاي از اطلاعات را شامل ميشوند، که بعضاً تشابه بين کلمات و معاني مختلف يک جمله نتيجهگيري را سختتر ميکند. پس نياز به الگوريتمهاي معنايي در بررسي تشابه متن احساس ميشود. همچنين بايد به اين نکته مهم توجه کرد که الگوريتم معنايي انتخاب شده بهينه است و قادر باشد ميان اين حجم اطلاعات که از سوي کاربران مختلف ثبت ميشود، بهترين جواب با تشابه بيشتر را انتخاب کند. اگرچه تا بهحال روشهاي بسياري براي تکميل مخازن خطا و استفاده از دانش نهفته در آن صورتگرفته اما ميتوان گفت که ضرورت اهميت به تشابه معنايي بين دادهها در نظر گرفته نشده است. در اين تحقيق سعي شده که اين ضعف در جستجو و بهرهگيري دانش نهفته در اين مخازن داده پوشش داده شود.
مدل ارائه شده در اينجا ابتدا ليستي از خطاهاي مشابه خطای جديد با استفاده ازيک الگوريتم تشابه معنايي مناسب، با توجه به اطلاعات متني ذخيرهشده ارائه ميدهد. در مرحله بعد اين خطاها براساس چرخه عمر خطا با استفاده از روش خوشهبندي K-means، خوشه بندي ميشوند.
همچنين ميانگين تشابه هر دسته به خطای جديد، گروه منتخب را مشخص مي کند. خطاهاي موجود در اين گروه، راه حلهاي پيشنهادي براي هر کدام، کمکي براي تسهيل و تسريع در رفع خطا است و ميانگين طولعمر گروه تخميني بر پيچيدگي و زمان حلمشکل خواهد بود.
3.1. پیشینه تحقيقاتي
شايد بتوان گفت که بنيان MSR و نرمافزارهاي رديابيخطا7با توليد 8GNATS در سال1992 نهاده شد. پس از آن نرمافزارهايمتعددي به ياري مهندسينرمافزار شتافتهاست. در اين مدت سعي و اهتمام محققان بر تکميل مدلها و موتورهايجستجو مورد استفاده در اين نرمافزارها بوده است. در سال 2000 مدلي با استفادهاز رگرسيون فازي9 براي تخمين تعداد خطاهاي موجود در نرمافزار ارائهشد]6[. در]5[ همين کار با استفاده از شبکههايعصبي انجامشد. درسال 2007 LucasD.Panjerدادهکاوي را براي تخمين زمانخطا با مقايسه پنج الگوريتم دستهبندي دادهها مطرح کرد]7[. Suma.V و همکارانش به سراغ روشهاي خوشهبندي رفته و ثابتکردند که روش K-mean در ميان روشهاي مورد بررسي آنها بهينهتر بوده است]8[. CathrinWeiß و همکارانش از روش نزديکترين همسايه و تشابه جملات با استفاده از موتورارزيابيLucene10 استفاده کردند]9[.Lucene خود از SVM و يک مدل بولي11 براي جستجو و ارزيابي متون استفاده ميکند. Nagwani نيزدرمدلهاي مختلفي از الگوريتم هاي دادهکاوي متعددي براي اهداف مختلف استفادهکرد]10[،]11[،]12[. اما همه اين روشها يا به جنبه معنايي تشابه متون و کلمات توجه نداشتند. يا براي استخراج ضريب تشابه دو متن از الگوريتمهاي مناسب براي اين محيط بهره نبردند. الگوريتمهاي استفاده شده بيشتر به تاثير يک متن و يافتن ضريب تشابه آنها با متن کاربرتوجه داشتند، معمولا استاتيک بودند و هرگز به بهرهوري روش در محيط با حجم بالا توجه نداشتند. نوآوري کار تحقيقاتي ارائهشده نسبت به مدلهاي قبلي استفاده از يک الگوريتم بهينه با دقت بيشتر در اندازهگيري تشابه ميان دو متن است بهطوريکه با حجم زياد مستندات و کلمههاي مشابه در مخازن نرمافزاري سازگار باشد. اين الگوريتم تشابه جملات و تشابه معنايي بين کلمات را با هم ترکيب ميکند. بهطوريکه، مشابهترين جملات را، با توضيحات دادهشده براي خطا از سوي کاربر، از ميان دادههاي قبلي در مخزن استخراج کند.
4.1. فرضیه های تحقیق
مخازن خطای هر نرم افزار منابع ارزشمند دانش هستند.
اطلاعات ثبت شده در مخازن خطا به پيشبرد سريعتر و کم هزينه تر فرآيند توليد نرم افزار کمک می کند
ثبت روش حل مشکل يا خطا در طول فرآيند توليد می تواند به توسعه دهنده پروژه برای حل خطا جديد کمک کند.
برای پيش بينی قسمتی از زمان انجام پروژه و هزينه آن می توان از اين اطلاعات استفاده کرد.
5.1. اهداف تحقیق
از آنجا که در روش ارائه شده در اين تحقيق سعي بر آن شده تا کاستيهاي موجود در روشهاي قبلي به نوعي پوشش داده شود ، بهدنبال بهترين و مناسب ترين الگوريتم براي جستجو و محاسبه تشابه متون و مستندات در يک مخزن با حجمعظيمداده هستيم. به طوريکه با بالارفتن اين حجم دچار مشکل پيچيدگيمحاسبه و بالارفتن زمانپاسخگويي نشود. همچنين تشابه بين دو متن بايد شامل تشابهمعنايي باشد. بهجز تشابه بين کلمات تشابه به صورت مجموعه کلمات. يعني جملات بايد بررسي شود. با توجهبه مطالب ذکرشده يافتههاي اصلي اين تحقيق را ميشود در مطالب زير خلاصه کرد.
ارائه يک روش براي کاوش مخازن خطاي نرمافزار که کاستيهاي روشهاي قبلي در اندازهگيري ميزان تشابه بين نمونه و خطا را پوششدهد.
يافتن خطاهاي مشابه با خطای جديدواستفاده از آنها براي تخمين زمان لازم براي رفعخطا
تعيين ميزان پيچيدگي خطای جديدبا محاسبه ميانگين طول عمر خطاهايي با شباهت بيشتر
استفاده ازراهکارهاي رفع خطا با جستجوی خطاهايي با ضريب تشابه بالاتر با خطای جديد
هدف نهايي کاهش هزينههای مالی پروژههای نرمافزاری و تسريع درفرآيند مهندسینرمافزار است.
6.1. نوآوری تحقیق
آنچه بيش از همه بهعنوان نوآوری در کار و بهبود روشهای گذشته مطرح است:
استفاده از يک الگوريتم معنايي مناسب بههمراه تشابه خطی در مرحله اول
استفاده از الگوريتمهای خوشهبندی در مرحله دوم.
در اين تحقيق برای بالا بردن دقت و سرعت در استفاده از اطلاعات از الگوريتم پيشرفته تر نسبت به کارهای قبلی استفاده شده است. الگوريتم ترکيبی که به جنبه معنايي تشابه نيز توجه داشته باشد. همچنين نتايج نهايی برای بررسی راحت تر و دقيق تر با استفاده از يک روش بهينه خوشه بندی طبقه بندی ميشوند، تا دسترسی کاربر به اطلاعات نهايی راحتر و سريعتر باشد. به بياني ساده تر اطلاعات نهايي خوانا وجامع باشند.
7.1. ساختار پايان نامه
اين تحقيق شامل 5 فصل است که ترتيب فصول و موضوعات مطرح شده بهصورت کلي در زير بيان شدهاست:
1.7.1. فصل اول: کليات(همين فصل)
در اين فصل يک مقدمه از حوزه اين تحقيق ارائه شده و در آن مشخصشده که هدف از اين تحقيق چيست و خواهان پاسخگويي به چه سوالي هستيم. در ادامه همين فصل يک توضيح مختصر از تحقيقات انجامشده در مورد موضوع اين تحقيق ارائه شده است. در نهايت نيز يک ديد کلي از فصلهاي مختلف اين تحقيق ذکر شدهاست.

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

3.7.1. فصل سوم : استفاده از تکنيکهاي دادهکاوي براي کشف و رفع خطاهاي نرمافزار بر پايه ضريب تشابه معنايي متن و خوشهبندي
ضريب تشابه رشته اي يا خطي بر پايه LCS ، روش SOC-PMI بهعنوان يک روش معنايي و تشابه جملات بر اساس عبارات مشترک معرفيمي شوند. و در نهايت روش اندازهگيري شباهت ترکيبي با ادغام و بهينهسازي اين روشها معرفي ميشود. روشهاي خوشهبندي و محاسبه ميانگين دادهها مورد نياز اين تحقيق هم بيان ميشوند. روش پيشنهادي با استفادهاز استراتژيها و روشهاي انتخابشده که با محيط دادهاي مخازن سازگار هستند، براي يافتن خطاي مشابهتر با خطای جديد تشريح ميشود و توضيحميدهيم که چگونه با يک خوشهبندي و محاسبه ميتوانيم ميزان پيچيدگي و تخميني براي زمان رفعخطا ارائهکرد.
4.7.1.فصل چهارم: اعتبارسنجي و توسعه
پياده سازي روش بر روي نمونه داده هاي واقعي که از مخزن خطا استخراج شده با استفاده از برنامهنويسي و نرمافزار Rapid miner12، مقايسه روش از نظر زمان و دقت پاسخگويي با روشهاي ديگر. همچنين روش ارائه شده را با روشهاي قبلي مورد مقايسه و تحليل موضوعي قرار ميدهيم.
5.7.1. فصل پنجم : نتيجه گيري
در اين فصل به جمعبندي، نتيجهگيري و تبيين دستاوردها و کارهاي آينده پرداخته ميشود. ويژگيهای اين روش با روشهاي ديگر مقايسه شده و زمينههاي بهبود و نتايج به صورت موردي بيان ميشود. از آنجا که استفاده از تشابه معنايي در اين زمينه در قدمهاي اوليه قرار دارد، در آينده زمينههاي زيادي براي کار بيشتر وجود دارد که به چند مورد در اين فصل اشاره خواهد شد.
فصل دوم
ادبيات تحقيق

1.2. فرآيند مهندسي نرمافزار
به زبان ساده فرآيند توليد نرمافزار به مراحل مختلف براي توليد و توسعه يک محصول نرم افزاري انجام ميشود اشاره دارد. به صورت کلي فرآيند مهندسي نرم افزار شامل سه مرحله اصلي است: برنامه ريزي (امکان سنجي)، پياده سازي آزمايش، تست و مستندسازي، استقرار ونگهداري سيستم. آنچه که مد نظر ماست قسمتي از مرحله پيادهسازي، آزمايش، تست و مستند سازي است.

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

2.2. انواع مخازن داده
1.2.2.کد اصلي:
کد اصلی بخش قابل اجرا و رفتار يک توسعه نرمافزاري است. که در نهايت به صورت فرمت اجرايي به مشتري تحويل داده ميشود. که عموما به عنوان مهمترين داده از سوي توسعهدهندگان مورد توجه قرار ميگيرد. مخزن حاوي اين اطلاعات شامل تعدادي از منابع کد و اسناد در يک يا چند زبان مختلف برنامهنويسي است. اين اسناد معمولا به موجوديتهاي منطقي به نامهاي ماژول13يا بسته گروهبندي ميشوند. تمام اين مجموعه اطلاعات کد اصلي سيستم ناميده ميشود. براي کاوش اين متون تمرکز روي شناسهها (متغير، نام)، توضيحات و رشتههاي اصلي داخل کد اصلي است. معمولا کلمات کليدي و نمادها در نظر گرفته نميشوند.

2.2.2. مخازن خطا(سيستم رديابي خطا BTS14)
اين مخازن براي ذخيره اطلاعات مربوط به ايجاد و حل خطا، مشخصات ارتقاء سيستم و کليه اقدامات ديگر در مرحله تعمير و نگهداري استفاده ميشوند. معمولا هنگاميکه توسعهدهندگان و کاربران به مشکل يا خطايي در يک سيستم نرمافزاري مواجه ميشوند، يادداشتي درباره اين خطا در پايگاه داده خطا در موضوع مربوطه ذخيره ميشود. اين اطلاعات شامل: علت و مکان وقوع خطا در برنامه و اينکه چگونه خطا باعث ايجاد اشکال و خلل در روند برنامه شده است. پس از آن يک يا چند متخصص، موضوع ايجاد شده را براي رفع مشکل بررسي ميکنند. چنانچه خطا برطرف شود موضوع در فرم مربوطه بسته ميشود. تمام اين اطلاعات در مخازن و پايگاههاي خطا ذخيره ميشوند. عموميترين سيستمهاي مخازن خطا Bugzilla ، Trac هستند.
اگرچه تا به امروز سيستمهاي متعددي ساخته شدهاند. در حالت عادي بين خطا15، نقص16، عيب17 تفاوت قائل ميشويم، اما در اين تحقيق همه را با لفظ خطا و هم معني در نظر ميگيريم.
3.2.2. ليست نامهها و گفتگوهاي ثبت شده
ليست ايميلها (يا آرشيو بحثها) همراه با گفتگوهاي ثبت شده بين افراد دخيل در يک پروژه آرشيوي از ارتباطات متني توسعهدهندگان ، مديران و ذينفعان آن پروژه هستند. ليست متني متشکل از بستههاي الکترونيکي که شامل سه قسمت:
سرآيند (فرستنده ،گيرنده و زمان ارسال)
بدنه پيغام(متن داخل ايميل)
مجموعهاياز فايلهاي پيوستشده(مستندات اضافي که همراه ايميل فرستاده میشود) ميباشد.
شرح گفتگوها شامل ثبت مکالمات فوري بين ذينفعان پروژه، که بر حسب زمان يا نويسنده دستهبندي شدهاند، ميباشد.
4.2.2 .پايگاه داده کنترل منبع (پايگاه داده کنترل ويرايش ها)
سيستمي براي ثبت تاريخ تغييرات (ويرايشها) بههمراه خود ويرايش و اطلاعات ديگر به صورت اسناد و اطلاعات متني است. توسعهدهندگان معمولا تاريخ و زمان ويرايش يک کد اصلي را در پايگاه دادههايي ذخيره ميکنند. پايگاه دادههاي کنترل کد رايج مانند] cvs 13[ و] svn 14[ ، به توسعه دهندگان اجازه ميدهند به يک کپي از مخزن سراسري و جهاني، در سيستم فايلهاي محلي خود، دسترسي داشته باشند. اسناد موجود را ويرايش کند، يا اطلاعاتي اضافه يا کم کند و يا ساختار دايرکتوري اين مخازن را تغيير دهند. همچنين ميتواند در مخزن اصلي سند يا اطلاعات جديد محلي ايجاد کند.
بنابراين کنترل بازبينيها دو نتيجه مهم در بر خواهد داشت:
اول اينکه به توسعهدهندگان اجازه ميدهد، مستقل از کساني که به مخازن دسترسي دارند، فايلهاي روي سيستمهاي خود را تغيير دهند . پس از آن که تغييرات تاييد شده ايجاد شد بقيه ميتوانند اين تغيرات را بررسيکنند. اين استقلال کاري اجازه ميدهد که يک چرخه کار موازي بدون نياز به ارسال ايميل و گفتگو و نيز بدون تغيرات ورژن برنامه به عقب و جلو تشکيل شود.
دوم اينکه زمان و تاريخ همه اطلاعات و مستندات به صورت خودکار ثبت و نگهداري ميشود. اگر نسخههاي قبل نرمافزار نياز بود، توسعهدهندگان بهراحتي ميتوانند به نسخههاي قبل سيستم دسترسي داشته باشند و سيستم را به نسخه قبلي برگردانند.
5.2.2. اطلاعات طراحي و نيازمنديهاي سيستم
مستندات نيازمنديها، معمولا در ارتباط با مشتري و يا با تاييدهاي او تنظيم ميشود. اين اسناد ليستي از نيازهاي مشتري است که خواهان انجام آن توسط سيستم است. اين نيازها به دو صورت دستهبندي ميشوند. اينکه چه نيازهايي را سيستم بايد برطرف کند و چگونه و با چه کيفيتي موردانتظار مشتري است. اطلاعات طراحي نيز شامل تمام اطلاعات مربوط به طراحيمعماري و الگوريتمهاي مهم و مورد استفاده18 سيستم است. طراحي سيستم ميتواند به شکل نمودار(مانند UML) و يا بهصورت متون جريان کار نمايش داده شوند.

6.2.2. مخازن شرح اجرا
اطلاعات مربوط به خروجي يک برنامه در حين يک يا چند بار اجرا، بر حسب آن چه که در قسمت تست مشخص شده ثبت ميشود. اين اطلاعات شامل ليستي از زمان و دليل اجرا شدن متدهاي يک سيستم، مقادير قطعي متغيرها و جزئيات مربوط به شرايط اجراست. اين ليست هنگامي مفيد است که فرآيند اشکالزدايي در مقياس وسيع همزمان با هزاران يا ميليونها فرآيند ديگر از سوي افراد مختلف انجام شود. در اين هنگام پيدا کردن اشکالات فردي لازم اما کاري دشوار و زمان بر است. اين مخازن کمک ميکنند به تک تک اين اجراها با جزئيات دسترسي داشته باشيم.
7.2.2. مخازن سيستم نرم افزار
مخازن سيستم نرمافزار شامل مجموعهاي از سيستمهاي مختلف به همراه کد اصلي آنها که افراد علاقهمند ميتوانند بهراحتي در آن جستجو کرده و از آنها استفاده نمايند. از مخازن مهم رايج در اين حوزه ميتوان به Source Forge ]15 [وGoogle Code ]16[ اشاره کرد.
اين مخازن شامل آرايه وسيعي از اطلاعات در حوزههاي مختلف پروژههاي نرمافزاري است که ميتوان اطلاعات غني را در فازهاي مختلف آن استخراج کرد. آنچه بهعنوان منابع داده در اين تحقيق مورد استفاده قرار ميگيرد همان مخازن خطا است. که با استفاده از يک سيستم رديابي خطا نمونههاي آماري لازم استخراج مي شود]17[.

3.2. خطای نرمافزاري
اشکال نرمافزاري، خطا، نقص و يا شکست ايجاد شده در برنامه کامپيوتري است، که باعث توليد يک نتيجه نادرست يا غيرمنتظره ميشود. يا باعث بروز رفتار ناخواسته از سيستم ميگردد. رفع اين مشکلات در پروژههاي نرمافزاري از سختترين و پر هزينهترين مراحل مهندسي نرمافزار است. اين خطاها ميتواند در پروژههاي بزرگ ومخصوصا پروژههاي متن باز19 از سوي همه کاربران و توسعهدهندگان گزارش شوند. از اين رو نرم افزارهاي رديابي خطا به کمک آمده تا بتوان اين گزارشات را ثبت و پيگيري کرد. خاطر نشان ميکنم که در اين تحقيق همانطور که قبلا گفتيم مشکلات اعم از نقص، شکست يا خطا با عنوان خطاي نرمافزاري معرفي ميشود.

1.3.2.سيستم رديابي خطا
سيستم رديابي خطا يک برنامه نرمافزاري است که براي کمک در سهولت پيگيري خطاهاي نرم افزاري در طول عمر پروژه طراحي و ارائه شدهاست. اين سيستم يک نرمافزار کاربردي براي تيم توسعه است بهطوري که به آنها در تضمين کيفيت و کاهش هزينه ها و پيشرفت سريع پروژه کمک ميکند. اين سيستمها به کليه افراد دخيل در يک پروژه اعم از کاربران، توسعهدهندگان و ذينفعان ديگر اجازه ميدهد که خطاي رويت شده در نرمافزار را در هر مرحله از روند توليد که باشد گزارش داده و پيگيري کنند. بسياري از پروژههاي بزرگ از اين نرمافزارها استفادهکرده و پروژههاي خود را در نسخههاي مختلف ارائه ميدهند. تا در مراحل مختلف از ارائه نسخه جديد خطاهاي نسخه قبلي که ديگران گزارش دادهاند پيگيري و رفع کنند. پروژه در هر حالتي ارائه شود، چه بهصورت مرحلهاي يا کامل، متنباز يا بسته و با هر متد استفاده شده در مهندسي نرمافزار ، يک سيستم رديابي خطا در پيشبرد بهتر و سريعتر فرآيند مهندسي نرمافزار بسيار ارزشمند است.
بسياري از اين نرمافزارها براي استفاده عموم طراحي شده و بقيه تنها براي استفاده در يک پروژه طراحي ميشوند. معمولا سيستمهاي رديابي خطا با ديگر اپليکيشنهاي مديريت پروژه يکپارچه و مجتمع ميشوند]18[. مهمترين قسمت اين سيستمها مخازن اطلاعاتي آنهاست که کليه اطلاعات مربوط به خطا را در خود ذخيره ميکنند. بايد ديد در يک سيستم رديابي خطا ايدهال چه اتفاقي ميافتد و يک خطا چه چرخهاي را در طول عمر خود در آن طي ميکند. بهعنوان مثال باگزيلا20يک سيستم رديابي خطا است که در سال 1998 توسط تري ويسمن21 براي شرکت موزيلا22 نوشته شد.
در ابتدا باگزيلا بهعنوان يک سيستم رديابي خطا متنباز از داخل خانه براي کاربران مرتبط با نت اسکيپ23 طراحي شد. ابتدا به زبان TCL24 و سپس به Perl براي راحتي و سهولت استفاده و دخالت همگان در پيشرفت کار برگردانده شد. اين سيستم براي استفاده در پروژههاي متن باز بهينهسازي شد. بهطوري که شرکتها و پروژههاي بزرگي چون ياهو، ناسا،Gnome ، KDE ، Apache ، RedHat، ويکي مديا و خود موزيلا از آن استفاده کردند هر خطا يک شناسه(ID)، عنوان، تاريخ، وضعيت، نام محصول و مولفه، ميزان شدت سختي و پيچيدگي، اولويت و غيره را در خصوصيات خود دارد]9 [(شکل2-1).
شکل2- 1-مشخصات يک موضوع (خطا)در نرم افزار Bugzilla

يک خطا از زمان ايجاد تا زمان بستهشدن(حل مشکل) چرخهاي را در سيستم دارد(شکل2-2) نمودار فعاليت برای يک مخزن خطا در شکل2-3 نشان داده شدهاست.

شکل2- 2 – چرخه يک خطا در يک سيستم مديريت خطا]19[

شکل2- 3 – نمودار جريان کار25 يک سيستم رديابی خطا
خطا جديد (NEW ) يا تاييد شده وارد سيستم ميشود(unconfirmed) اگر اعتبار خطا توسط يکي از اعضاي تيم يا هسته مديريتي تاييد شد، بهعنوان يک گروه جديد ثبت ميشود.
مديران وکساني که مسئول ارزيابي خطاها هستند بايد وجود خطا را تاييد کنند. اعتبار و غيرتکراري بودن آن را نيز بررسيکنند. اگر خطا تاييد شد به قسمت تاييد شدهها (Assigned) رفته، تا در اختيار تيم توسعه براي حل و فصل و رفع خطا قرار گيرد. در غير اين صورت به قسمت تاييد نشده ( unconfirmed ) براي بررسي بيشتر ميرود.
اگر خطا رفع شد برچسب حل شده ( Resolved ) خورده و آن را به وضعيت حل شده انتقال ميدهند.
اعضاي تيم ممکن است يک خطا حلشده را به يکي از حالتهاي سازگار(Verified) و سپس بسته (Closed) اتصال دهند. يا دوباره به شکلي در رابطه با اين خطا مواجه شدند و آن را به حالت دوباره باز يا تاييد شده بفرستند.
خطاهايي که به مرحله Resolved بازگردانده ميشوند يا نامعتبرند يا تکراري هستند و نياز به بررسي مجدد دارند و يا بهطور کامل رفع شدهاند. چرخه عمر يک خطا از مرحلهی جديد تا مرحله خروج از حل تعريف ميشود. شکل2-4 وظايف هر يک از اشخاص در ارتباط با مخزن خطا را نشان میدهد. دو كادر قرمز دردو نمودار شکل2-4 و شکل2-3 محدوده كاري اين تحقيق را نشان ميدهند.

شکل2-4- نمودار مورد کاربرد26 يک سيستم رديابی خطا
همانطور که در شکل2-5 ميبينيد، يک خطا داراي مشخصات متني است. برچسب، وضعيت خلاصه و در قسمت جزئيات توضيحات و راهحلهاي ارائه شده با ذکر نام نويسنده و تاريخ براي هر خطا درج شده است. همين اطلاعات و متون ثبت شده دامنه کار تحقيقاتي ماست. اين دادهها منبع غني اطلاعات و دانش سودمند است. اينکه چگونه اين دادهها را کاوش کنيم و چه اطلاعاتي در آنها نهفته است، گامهاي تحقيق ما را ميسازند. از آنجايي که اين دادهها توسط افراد مختلف و با استفاده از قوانين نحوي صحيح و ناصحيح و گاه کلمات مشابه دريک حوزه استفاده شدهاند نياز به يک جستجو معنايي به شدت احساس ميشوند.
شکل2- 5-مشخصات يک خطا
پايه و اساس اين تحقيق جستجو جملات مشابه معنايي است. بهصورتي که آندسته از جملات که داراي تشابه معنايي بيشتري با جمله يا کلمه کانديداي ما هستند، جداسازي شوند. چگونگي اين کار در سه مرحله خلاصه مي شود: ابتدا با استفاده از تکنيکهايي که در ادامه پيشنهاد ميشود از ميان دادههاي آماريکه از يک مخزن خطا انتخاب شده، ميزان تشابه هر خطا (بر اساس دادههاي متني مانند توضيحات، سرآمد، راهحل و غيره) با خطای جديد اندازهگيري ميشود. در مرحله بعد اين خطا با استفاده از يک الگوريتم خوشهبندي که سعي شده يک الگوريتم بهينه باشد به دستههاي جدا بر اساس ضريب تشابه محاسبه شده تقسيم ميشوند.
اين کار به کاربر کمک ميکند که نمونههاي مشابه گزينش شده را در خوشههاي طبقهبندي شده از نظر سختي و پيچيدگي کار در اختيار داشتهباشد.گاهي ممکن است کاربر خود بر اساس تجربه حدس بزند که مشکل زياد پيچيده نيست. يا برعکس مشکل به زمان زيادي براي حل نياز داشته باشد، در اين حالت اين خوشهبندي ميتواند در کاستن زمان يافتن راهحل کمک قابل توجهي داشته باشد. آنچه اين کار را از کارهاي انجام شده قبلي متمايز ميکند توجه به بهرهوري و بهبود کارايي است. يک مخزن خطا مجموعهاي گسترده و بزرگ از دادههاست که هر روز بزرگتر ميشود. با بزرگ شدن نمونه آماري و نياز به دقت در کار ابعاد پيچيدگي اين عمل روشن خواهد شد. هدف اصلي اين کار استفاده از تکنيکي است که دقت بالاتري داشته باشد. جستجو در يک بانک داده که متون در آن از قانون خاص براي رعايت اصول تحرير و قواعد نحوي استفاده نشده است، و کساني که دادهها را ثبت کردهاند ممکن است از کلمات مشابه زيادي استفاده کرده باشند، نياز بيشتري به يک جستجوی معنايي دارد.

4.2.تحقيقات پيشين در حوزه دادهکاوي در مخازن خطا
در سال 1992 اولين نرمافزار رديابي خطا GNATS27 شروعي براي MSR بود. با ارائه اولين نرمافزار رديابي خطا، مديريت و استفاده از دانش نهفته در خطاها اولين قدمهاي خود را برداشت. در اين مدت محققان سعيکردند براي استخراج بهينه و مفيدتر دانش، مدلها و روشهاي جديدي با استفاده از الگوريتمهاي مختلف ارائه کنند. بيشتر اين روشها از الگوريتمهاي دستهبندي براي دستهبندي اطلاعات و استفاده از دانش آنها بهصورت طبقهبندي شده استفاده کردند. ابتدا مروري کوتاه بر تحقيقات قبلي و روش هاي بررسي شده خواهيم داشت. نواقص و کمبودهايي که به موجب آن ها اين تحقيق انجام شده و روش ارائه شدهاست نيز بررسی خواهد شد.
سال 2000، JunzoWatada به منظور برآورد تعداد خطاها در يک پروژه نرمافزاري از رگرسيون فازي استفادهکرد]6[. وي مجموعه سئوالاتي را براي استفاده در سيستم فازي در مراحل مختلف از يک پروژه مطرح کرد. در اين روش تمام دادهها براي جستجو هدف قرار نميگيرد و اين خود ضعف بزرگي است.
Lucas D.Panger در سال 2007 مقايسهاي براي دستهبندي مخازن خطا با استفاده از پنج الگوريتم دسته بندي 0-R ،1-R، درخت تصميمگيري C4.5 ،Naïve Bayes و رگرسيون لجستيک، در دادههاي گرفته شده از Bugzilla انجام دادهاست]5[. اين کار با محاسبه درصد خطاهايي که دستهبندي شدهاند و ضريب Kappa براي هر کدام با استفاده از نرمافزار Weka انجام داده است. دادهها بر اساس طول عمروتوضيحات متني دستهبندي شدهاند. اين تحقيق تنها مقايسهاي بين الگوريتمهاي مختلف در يک دستهبندي ساده براي دادههاي موجود در يک مخزن است، که کمتر به شباهت بين يک خطا جديد و خطاهاي ديگر پرداخته شده است.
در همان سال CathrinWeib و همکارانش با استفاده از دادههاي گرفته شده از JBoss در سه مرحله طول عمر خطای جديد را تخمين زدند]9[. ابتدا بهکمک الگوريتم نزديکترين همسايهKNN-α گزارشهاي مشابه را از منبع استخراج ميکند و در مرحله بعد با استفاده از موتور جستجوLucene دادهها با شباهت متني بيشتر استخراج ميشود. Lucene ازSVM و يک مدل بولي28 براي جستجو و ارزيابي متون استفاده ميکند. در اين تحقيق اگر موضوع با شباهت با توضيحات خطای جديد پيدا نشد، باز الگوريتم نزديکترين همسايه KNN-α را براي استخراج داده استفاده ميشود پس از اين مراحل دادههاي فيلترشده ميتواند در تخمين طول عمر خطا جديد و حل آن کمک ميکند. اين روش جزء روشهاي ابتدايي با بهکارگيري اندازهگيري تشابه بين متون بود. اما موتور و الگوريتم آن نهتنها به معناي کلمات توجه نميکرد بلکه جزه روشهاي ابتدايي جستجو در متون متشابه بود.
Nagwani در سال 2009 روشي را با دامنه خطاهاي حوزه GUI ارائه کرد. در اين تحقيق خطاهاي مربوط به GUI را از پروژه مختلف را به عنوان داده در نظر گرفت. از نظر او خطا در طول فرآيندی رخ مي دهد که اين فرآيند شامل چند رويداد متوالي است]1[. مدل وي در سه مرحله داده ها را فيلتر مي کند. در مرحله اول داده ها بر اساس رويداد، در مرحله بعد براي قسمتهاي مختلف هر رويداد مقايسه ميشوند. در مرحله آخر براساس ملزومات هر قسمت تفکيک و با هم مقايسه ميشوند. در اين روش خطاهايي که از نظر مرحله و رويدادهاي موجود در فرآيند داراي تشابه بيشتر با خطاي جديد هستند از منابع استخراج ميشود. اين روش اگرچه به مفاهيم و معاني توضيحات هر موضوع خطا بيشتر توجه کرده، اما در پيادهسازي موانع زيادي وجود دارد. مراحل توسط نيروي انساني مجزا و مشخص شوند و تمام اين رويدادها در طول يک فرآيند خطا دار بايد مشخص باشند. همچنين محدود به خطاهايي از که در يک فرآيند مشخص در GUI است.
يک سال بعد Nagwani وBhansali با استفاده از الگوريتمK-means مجموعهاي از دادهها شامل طول عمر و شماره داده را به خوشههايي تقسيم کردند، تا بتوانند ميزان پيچيدگييک خطا را با تخمين ذهني طول عمر يک خطای جديد را مشخص کند. به اين ترتيب ابتدا کاربر براي طول عمر خطا جديد تخميني ميزند و اين تخمين با مراکز خوشههاي ايجاد شده بر اساس طول عمر دادهها، پيچيدگي خطا جديد را مشخص ميکند]11[. اين روش دو مورد مهم توجه نشده اول اينکه تخمين ذهني طول عمر يک خطا زياد اصولي و دقيق نيست. دوم اينکه تعيين ميزان پيچيدگي يک خطا با يک پسزمينه ذهني کمک چنداني در پيشرفت پروژه و بهرهوري در هزينه و زمان آن ندارد.
در تحقيقي ديگر در همان سال، وي با استفاده از سه الگوريتم تشابه جاکارد، کسينوسي و TF-IDF ميانگيني از تشابه موجود بين قسمتهاي متني مختلف از خطای جديد و خطاهاي ديگر در منبع خطا را محاسبه ميکند]10.[ نتايج را براي هر الگوريتم با هم مقايسه کرده است. اين کار با محاسبه تشابه بين بخش موضوع، توضيحات و ديگر بخشهاي متني از هر موضوع موجود در منبع خطا را با خطایجديد، بهصورت جداگانه محاسبه ميکند. اين نتايج با ضرايب وزني مشابه با هم جمع ميشوند و به عنوان ميزان شباهت خطایجديد با خطا داخل مخزن در نظر گرفته ميشود. برنامهاي که Nagwani ارائه کرده است اين کار را با استفاده از هرسه الگوريتم انجام ميدهد.
براي نمونه در اين تحقيق، با استفاده از ضريب کسينوسي براي يک نمونه جديد، نتايج محاسبه و چهارخطا با شباهت بيشتر، بهعنوان کمک براي حل خطا و محاسبه ميانگين طول عمر آنها، بهعنوان تخميني براي طول عمر خطا استخراج شدهاست. در اين روش براي بررسي ميزان تشابه بين متون خطا جديد و داخل مخزن از روشهاي خطي استفاده شده که براي شروع مناسب است، اما کافي نيست. اين الگوريتمها معايبي دارند که الگوريتمهاي بهتري را ميتوان استفادهکرد.
بهعنوان مثال الگوريتمهاي معنايي که در آنها علاوه بر تشابه لغوي و نحوي تشابه معنايي بين جملات و متون را در نظر گرفته ميشود.
در سال 2011، Nagwani تحقيق خود را روي نويسندگان و توسعهدهندگان ثبت شده در مخزن خطا وموضوعاتي که جوابگوي آنها بودهاند يا نظرات موثري در رفع خطا داشتهاند، متمرکز کردند]12[. بهاينصورت که روي تعدادي داده که از Bugzilla استخراج شده بود کلمات تکراري مهم در اين موضوعها را بهعنوان داده استخراج ميکند. ليستي ازتوسعهدهندگان و کاربران ثبت کننده به تفکيک کلمات اصلي تکرار شده ليست ميشود. در اين حالت ميتوان کساني را که در حوزه موضوع خطای جديد کار کردهاند، براي کمک به حل مشکل شناسايي کرد. در اين روش تشخيص موضوع اصلي و کلمات مهم بايد مطابق با مجموعه و در مقايسه با آن استخراج شود. انتخاب و يا تشکيل مجموعه بهينه خود نيازمند ارائه روشي مناسب است.
Suma.V و همکارانش در سال 2012 به استفاده ازچند روش خوشهبندي و مقايسه آنها اکتفا کرد.آنها هشت الگوريتم را براي دستهبندي دادهها در مخازن خطا استفاده کردند که در ميان آنها K-means در برابر افزايش دادهها نتايج بهينهتري در اختيار کاربر ميگذارد]8[. الگوريتمها با استفاده از نرمافزار Weka پيادهسازي شدهاند. اين روش نيز تنها به دستهبندي ساده اکتفا شده و به نوع دادهها که متني هستند توجه نشده است.
Nagwani در جديدترين تحقيق خود در 2013 الگوريتمهايNB ، J84 ،SVM ، CC و CLUBAS را روي دادههاي گرفته شده از پروژه Mozilla براي دستهبندي استفاده کرد و نتايج را تحليل کردهاست]20[. بهعنوان نتيجه نشان دادهاست که NB و J84 با زياد شدن حجم دادهها افت دقت ندارد.
پس از مطالعهاي اجمالي روي BTS ها و روشهايي که تاکنون براي جستجو و استفاده دانش موجود در اين سيستمها نشان ميدهد، که سير پيشرفت آن مدتي است که متوقف شده. در واقع پيشرفتي چشمگير در آنها ديده نميشود. آنچه نبودش بيش از همه درکاوش در دادههاي مهم موجود در اين مخازن، به چشم مي آيد، هوشمند سازی اين کاوش هاست . داده هاي موجود در اين مخازن مجموعه اي از متون و ارقام است. پس جستجو و کاوش پيشرفته با در نظر گرفتن جنبه هاي معنايي موجود در آنها، مطمئنا نتايج بهتري را در اختيار کاربران قرار خواهد داد .
در اين تحقيق سعي شده به اين جنبه از داده کاوي مخازن، يعني استفاده از الگوريتم هايي که به مفهوم و معناي داده ها و استخراج دانشي بهينه و مختصرتر توجه شود.

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

1.5.2.شباهت خطي
معيار شباهت خطي بر پايه توالي و موقعيت کاراکتر ها بنا شده است. در اندازه گيري اين شباهت ميزان (فاصله) شباهت دو جمله بر اساس همين دو معيار يعني توالي خطي و موقعيت کلمه در جمله اندازه گيري مي شود. از چهارده روش و معيار اندازه گيري ارائه شده در طول تحقيقات عمومي، در اين گروه هفت معيار مربوط به گروه توالي خطي29و هفت معيار و روش به گروه موقعيت کلمه30 تعلق دارند.(شکل2-6)

شکل2- 6 – انواع الگوريتم های تشابه خطي
1.1.5.2.اندازه گيري شباهت بر پايه کاراکتر31
بزرگترين زير دنباله مشترک(LCS) 32
روشي است براي پيدا کردن بزرگترين زير دنباله در مجموعه اي از دنباله ها. معيار شباهت بزرگترين رشته پيوسته از کاراکترهاست که در هر دو جمله موجود باشند. هدف در اين روش مقايسه دو رشته S₁ و S₂ است به طوري که رشته S₃ با حفظ ترتيب، و نه لزوما متوالي در هر رشته موجود باشد.
Dameran-LevelShtien
تعريف فاصله بين دو رشته با شمارش حداقل تعداد عمليات مورد نياز براي تبديل يک رشته به ديگري که در آن عمليات بايد درج، حذف و يا جايگزيني يک واحد يا جابجايي در حرف مجاور باشد.
Jaro وJaro-Winkler
بر پايه تعداد و ترتيب کاراکترهاي مشترک بين دو رشته تعريف مي شود به طوري که فاصله دو کلمه مشترک با توالي يکسان دردو خط هر چه کوتاه تر باشد دو جمله شباهت بيشتري دارند.

m تعداد کل کاراکترهاي مشترک وt تعداد کاراکترهايي است که جا به جا شده اند. در فرمول دوم که ضريب Jaro-Winkler است ، ضريب Jaro و تعداد کاراکترهاي ثابت قبل اولين کاراکترجابه جا شده و p ضريب ثابت تفکيک است که بايد بيشتر از 0.25 باشد.
نيدلمن-رانچ33
يک همترازي برابري بر دو ترتيب متوالي (مانندA وB ) انجام مي دهد. اين الگوريتم نمونه اي از برنامه نويسي پوياست. اين معيار براي جملات و رشته هاي هم اندازه دو شباهت قابل توجه کاربردي است.
اسميت واترمن34
اين الگوريتم، الگوريتم نيدلمن رانچ را بهينه مي کند به اين صورت که به جاي در نظر گرفتن تمام توالي کاراکتري، اين الگوريتم سعي مي کند با در نظر گرفتن بخشهاي مختلف با همه طولهاي ممکن ميزان شباهت را بهينه کند. اين الگوريتم براي متوني که به نظر شبيه نيستند اما ممکن است قسمت هاي کوچکي از آنها به هم شبيه باشد مناسب است.
n-gram
زير دنباله اي n موردي از دو رشته يا متن را با هم مقايسه مي کند. مثلا 1-gram کلمه به کلمه جملات را در نظر مي گيرد يا 2-gram دو کلمه با هم از هر رشته، و به همين ترتيب فاصله و شباهت n-gram از هر رشته را تا حداکثر n اندازه گيري مي کند.
2.1.5.2. شباهت بر پايه توالي35
فاصله بلوک يا فاصله منهتن
اين الگوريتم فاصله بين دو نقطه روي يک مسير مشبک را محاسبه مي کند. در شباهت بين دو جمله اين فاصله با اندازه گيري مجموع تفاوت بين اجزاء مترادف نظير به نظير بدست مي آيد.

شباهت کسينوسي
ا ندازه گيري فاصله داخلي دو بردار متقاطع در فضا با استفاده از اندازه گيري کسينوس زاويه بين دو بردار. در اندازه گيري شباهت بين دو جمله يا رشته هر جمله نماد يک بردار است و ارزش هر يک، براي نمونه تعداد دفعات، تکرار يک توالي، کاراکترها يا يک کلمه خاص در جمله، در نظر گرفته مي شود.

ضريب تاس36
اين ضريب به صورت دو برابر عبارات مشترک در رشته هاي مورد مقايسه تقسيم بر تعداد کل عبارت هاي در نظر گرفته شده در هر دو رشته محاسبه مي شود.

فاصله اقليدسي37
يا فاصله L2 که همان فاصله بين دو نقطه در مختصات دکارتي است. براي شباهت بين دو جمله اين فاصله جذر مجموع تفاوت بين عبارات متناظر در دو رشته در نظر گرفته مي شود.
ضريب تشابه جاکارد38
نسبت مجموع عبارات مشابه و مشترک در دو رشته به عبارات غير مشترک

ضريب تطبيق39
يک ضريب تشابه بسيار ساده. اندازه عبارات مشترک به کل عبارات.
ضريب همپوشاني40
شبيه به ضريب تاس با اين تفاوت که شباهت بين دو رشته را در حالي اندازه مي گيرد که کلمه اي از يکي زيرمجموعه اي از ديگري باشد.

2.5.2. تشابه بر پايه مجموعه
سنجش تشابه دو متن بر پايه مجموعه يک معيار سنجش تشابه معنايي است، که شباهت بين کلمات را بر اساس اطلاعات مفيد موجود در يک مجموعه بدست مي آورد. اين مجموعه حجم انبوهي از دست نوشته ها و متون گفتاري است که براي تحقيقات زباني مورد استفاده قرار مي گيرند. مي توان گفت که ميزان تشابه وابسته به مجموعه اي است که کلمات و جملات از آنها استخراج شده است. شکل2-7 انواع روش هاي سنجش تشابه بر پايه مجموعه را نشان مي دهد، که در ادامه به اختصار معرفي مي شوند.
شکل2- 7- انواع الگوريتم های تشابه بر پايه مجموع

Hyperspace Analoue to Language (HAL)
در اين روش يک فضاي معنايي از کلمات موجود در مجموعه ساخته مي شود به اين شکل که يک ماتريس کلمه در کلمه تشکيل مي شود. به طوري که مقادير آن نشان دهنده ميزان ارتباط بين کلمه سطر و ستون متناظر با آن مقدار است. سپس آنتروپي پايين در ستون ماتريس توسط کاربر استخراج مي شود. در تجزيه تحليل متن براي استخراج ماتريس يک قالب n کلمه اي را در نظر مي گيريم.
(مثلا n=1 ) سپس فاصله وقوع هر کلمه با کلمه اولي شمارش مي شود. وزن مقادير ماتريس رابطه معکوس با فاصله وقوع هر کلمه با کلمه ابتدايي دارد .کلمه اي که به کلمه ابتدايي نزديک تر باشد از نظر معنايي رابطه نزديکتري و در نتيجه وزن بيشتري دارد. HAL همچنين به ترتيب قرارگيري نيز توجه مي کند. يعني اينکه همسايه قبل از کلمه مورد نظر است يا بعد از آن به اين منظور حالت همسايه مختلف را ثبت مي کند.

Latent Semantic Analysis (LSA )
تحليل معنايي نهفته متداول ترين روش در ميان روش هاي مبتني بر مجموعه اصلي است. به ويژه براي تحليل رابطه معنايي بين دستهاي از متون مورد استفاده قرارمي گيرد. روش کار به اختصار اينگونه است ،که ابتدا ماتريس کلمه و سطر يا پاراگراف تشکيل مي- شود، که رديف ها نشان دهنده کلمات منحصر به فرد و ستون ها نشان دهنده سطرهاست. پس از روش تجزيه مقدار دهي منفرد 41(SVD)به منظور کاهش سطر و ستون ماتريس در حالي که ساختار شباهت بين رديف ها حفظ مي شود، استفاده مي کند.د پس از آن کلمات با محاسبه کسينوس رابطه بين دو بردار تشکيل شده توسط هر دو رديف مقايسه مي شوند. مقادير هر چه به يک نزديک تر باشد، دو کلمه به هم شبيه تر بوده و هر چه به صفر نزديک- تر باشد، شباهت کمتري دارند.
تعميم تحليل معنايي نهفته42 GLSA
يک چارچوب براي محاسبه ميزان اهميت عبارات و سند حاوي آن . در اين روش که بر پايه LSA است، توجه بر ارزش سند حاوي عبارت به جاي روش ارائه شده در LSA شده که به تعداد کلمات موجود در سطرها و مقايسه آنها توجه کرد. GLSA به اين منظور نياز به محاسبه ميزان تشابه معنايي بين عبارات و نيز استفاده از روش هاي کاهش ابعاد مورد مقايسه دارد. براي رسيدن به نتيجه مطلوب بهترين و کارآمدترين روش ها را با هم ترکيب مي کند و در آخر ماتريس عبارات موجود در اسناد که در LSA معرفي شده، براي محاسبه وزن در ترکيب بردارهاي خطي از عبارات مورد استفاده قرار مي گيرد.
تحليل معنايي صريح ESA43
معياري براي محاسبه ارتباط معنايي بين دو متن دلخواه است. ESA به عنوان روشي براي بهبود طبقه بندي متون معرفي شده است. در اين روش يک ماتريس tf-idf تشکيل مي شود که مقادير آن نشان دهنده رابطه معنايي ميان دو متن است که توسط اندازه گيري کسينوسي محاسبه مي شود.

تحليل صريح معنايي متقابل زبانيCL-ESA44
يک تعميم چند زبانه از ESAاست. که از يک متن چند زبانه به عنوان مرجع در مرکز چندين متن ديگر که از نظر زباني مستقل هستند استفاده مي کند. ارتباط اين اسناد و ميزان وابستگي آن ها به سن مرجع از طريق اندازه گيري کسينوسي محاسبه مي شود. ويکيپديا از اين روش براي دسته بندي و اتصال اسناد متني خود استفاده مي کند.
بازيابي اطلاعات متقابل نقطه به نقطهPMI-IR45
روشي است براي محاسبه شباهت بين کلمات است. موتور جستجو آستاويستا از اين روش براي محاسبه احتمال در جستجو پيشرفته استفاده مي کند. دو کلمه که در يک صفحه وب نزديک ترين موقعيت را نسبت به هم داشته باشد نمره تشابه بالاتري درPMI-IR خواهد داشت.
بازيابي اطلاعات متقابل نقطه به نقطه نوع دومSCO-PMI46
در اين روش شباهت معنايي در واژه، با ليست کردن کلمات همسايه با آن در واژه در متن کلي انجام مي شود. مزيت اين روش در اين است که مي توان شباهت بين دو کلمه را که در همسايگي هم نيستند اما رابطه معنايي دارند را نيز اندازه گيري کرد.
فاصله نرمال گوگل NGD47
اندازه گيري شباهت معنايي که از بازديدهاي صورت گرفته به وسيله موتور جستجو گوگل براي يک مجموعه از کلمات کليدي بدست آمده است. در موتور جستجو فاصله دو کلمه کليدي با معني يکسان يا نزديک به هم در زبان طبيعي رابطه نزديکتري نسبت به دو کلمه



قیمت: تومان

دسته بندی : مقاله و پایان نامه

دیدگاهتان را بنویسید