دانلود پایان نامه

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

M در اينجا تعداد صفحات وب جستجوشده به وسيلهGoogle، f(x)و f(y)تعداد موقعيت ها، در جستجو عبارتهايx و y هر دو وجود داشتند. اگر اين دو کلمه به هم نزديک نباشد وجدا از هم در صفحه ظاهر شوند، ضريب NGD بي نهايت است و چنانچه هر دو دائما کنار هم ظاهرشوندNGD آنها صفريا برابر با مقداري بين مربع x و مربع y خواهد بود.

استخراج توزيعي کلمات مشابه با استفاده از تکرار وقوع کلماتDISCO48
در اين روش فرض بر اين است که کلمات مشابه در زمينه هاي مشابه استفاده مي شوند. بر همين اساس مجموعه هاي بزرگ متن مورد تجزيه و تحليل آماري قرارمي گيرند تا شباهت توزيعي بين کلمات استخراج شود. درDISCO شباهت توزيعي بين کلمات با استفاده از يک قاب متحرک با اندازه3± براي اندازه گيري دفعات پديدار شدن کلمه، اندازه گيري مي شود .دو معيار DISCO1 و DISCO2 نيز توسعه اي از معيار اصلي هستند به طوري که DISCO1 شباهت دو کلمه را بر اساس ترتيب مجموعه که کلمه در آن است محاسبه مي کند و DISCO2 ميزان تشابه را بر اساس مجموعه کلمات توزيع شده مشابه با کلمات مورد نظر محاسبه مي کند.
3.5.2.تشابه بر پايه دانش
روش هاي مبتني بر دانش بر اساس شناسايي ميزان شباهت بين کلمات با استفاده از اطلاعات بدست آمده از شبکه هاي معنايي عمل مي کنند. 49Wordnet متداول ترين شبکه معنايي است. Wordnet يک پايگاه بزرگ واژه اي در زبان انگليسي است. اسمها، فعل ها، صفت ها و قيدها به صورت مجموعه اي از مترادف هاي مشابه دسته بندي شده اند(synsets) که هر کدام بيان کننده يک مفهوم مجزا هستند .
synsets ها با استفاده از روابط معنايي و مفهومي و روابط لغوي به هم متصل هستند. روش هاي اندازه گيري تشابه بر پايه دانش به دو گروه تقسيم مي شوند: اندازه گيري شباهت معنايي و اندازه گيري ارتباط معنايي. اندازه گيري شباهت معنايي همان گونه که از اسمش بر مي آيد هنگامي قابل اندازه گيري است، که دو کلمه در رابطه معنايي بر پايه شباهت با يکديگر باشند، دو کلمه همانند و متشابه يکديگر باشند اما اندازه گيري بر پايه رابطه معنايي دو کلمه مي پردازد. به عنوان مثال اينکه کلمه اي نوع خاصي از ديگري باشد، يا دو کلمه مخالف هم باشند، يکي بخشي از ديگري باشد يا غيره.
شکل2- 8- انواع الگوريتم های تشابه برپايه دانش
از ميان نه روش ارائه شده اندازه گيري شباهت معنايي(شکل 2-8 ) سه روش بر پايه محتوا اطلاعات و سه روش بر پايه طول مسير اندازه گيري مي شوند سه روش بر پايه رابطه مفهومي به اندازه گيري شباهت مي پردازند. معيار path عددي را به عنوان ميزان شباهت دو کلمه بر مي گرداند که بر کوتاه ترين مسير مفهومي که دو کلمه را به هم متصل مي کند ، دلالت دارد به عنوان مثال father و parent در شبکه جزء يک طبقه بندي متصل هستند يا نه و فاصله مفهومي بين اين دو کلمه چقدر است. در روش HSO زنجيره ي لغوي بين دو کلمه پيدا شده و بر اساس آن رابطه دو کلمه در يکي از سه رشته ارتباطي تعريف مي شود فوق العاده قوي- قوي- متوسط که حداکثر نتيجه براي يک رابطه عدد 16 است.]21[
4.5.2. اندازه گيري شباهت ترکيبي
همانگونه که از اسم اين روش ها بر مي آيد اين روش ها با ترکيب روش هاي قبل سعي به از بين بردن نواقص و کاستي هاي هر روش با روش ديگر کرده اند تا معيارهاي بهينه تري را ارائه دهند. بسياري از تحقيق ها نيز در اين حوزه صورت گرفته تا به حال هشت روش آزمايش شده ارائه شده که دوتاي آنها بر پايه اندازه گيري بر اساس مجموعه، شش تاي ديگر بر اساس اندازه گيري بر پايه دانش مطرح شده اند. روش ارائه شده در ]22[ ابتدا شباهت معنايي بين کلمات از يک پايگاه دانش لغوي و مجموعه استخراج مي شود و سپس در مرحله دوم تاثير ترتيب و جاي کلمه در معناي جمله را در نظر مي گيرد.
در روش STS تشابه متن معنايي ميزان شباهت بين کلمات را با ترکيب اطلاعات معنايي و نحوي اندازه گيري مي کند. STS از دو روش شباهت خطي و شباهت معنايي به همراه روش انتخابي common word order بهره مي گيرد.
STS در]23[ روي سي جفت کلمه روش جديد را آزمايش کرده و با محاسبه ضريب همبستگي پيرسون50 نتايج را بهبود بخشيد. در روش ]24[ نيز از اندازه گيري معنايي بر اساس مجموعه همراه با ميزان شباهت معنايي بر اساس دانش براي کلمات هم نقش در جملات مختلف استفاده شده است. مهمترين خصوصيات اين روش استفاده از مدل هاي يادگيري ماشين مانند رگرسيون خطي و مدل bugging براي بدست اوردن يک درجه شباهت موثر بين جملات است.
در ]25[ دو روش اندازه گيري مفهومي با استفاده از wordnetوNgram را با هم براي ارتباط دادن بين دو روش دستي و اتوماتيک انتخاب شده است.
همان طور که در قبل بيان شد، نمونه ها و بانک دادهاي مورد استفاده در اين تحقيق و ب
ه طور کل در مخازن خطا نرم افزار توسط يک گروه يا کاربر خاص تنظيم و ثبت نمي شوند . اين داده ها توسط تمام کساني که به نوعي در ارتباط با نرم افزار و پروژه هستند ثبت مي شوند. پس طبيعي است که اين متون از نظر نوع نگارش و ديکته لغات با الگو ويزه و اصولي نباشد. از سوي ديگر ممکن است اين متون حاوي کلمات مشابه و هم معنا و حتي گاهي هم معني اما غير مربوط به هم باشند. در اين شرايط براي استخراج دانش و فيلتر کردن داده ها نياز به روشي است که اين مشکلات تاثير چنداني در نتايج آن نداشته باشد. همچنين در تشخيص جملات مشابه هم نياز به دقت محاسباتي در روش هاي خطي و هم نياز به دقت در معنا و نحو جملات و کلمات لازم است .
کلمات تخصصي در اين متون پر اهميت تر از کلمات متداول و اضافه هستند، پس نياز است که اهميت آنها به مراتب بيشتر از کلمات رايج در همه جملات است. روش مورد نظر پاسخگوي همه اين نياز ها خواهد بود همچنين در روش ]23 [نه تنها شباهت ظاهري و معنايي و نحوي کلمات در نظر گرفته مي شود بلکه به کلمات مجاور و حتي غير مجاور آنها که در جمله يا متن ظاهر مي شوند و روابط معنايي آنها با کلمه مورد نظر توجه مي شود.
دلايل فوق باعث انتخاب روش اندازه گيري تشابه معنايي با استفاده از تشابه خطي وتشابه معنايي بر پايه مجموعه، در اين تحقيق شده است. در ادامه به طور کامل اين روش را توضيح مي دهيم. روش مورد نظر شباهت بين دو متن را از نظر معنايي و اطلاعات نحوي (نظم متداول کلمات در زبان ) مورد بررسي قرار مي دهد. براي اين کار از سه تابع شباهت استفاده مي شود.
اول، شباهت رشته ها و شباهت معنايي کلمات محاسبه مي شود. سپس براي ترکيب محاسبات با شباهت نحوي از تابع شباهت کلمات متداول انتخابي استفاده مي کنيم. در نهايت ضريب شباهت دو متن با ترکيب شباهت رشته، شباهت معنايي بين کلمات و شباهت کلمات رايج و نرمال سازي محاسبات بدست مي آيد اين روش STS51نام دارد.
فرض کنيد کلمه اي در دو جمله به کار رفته باشد که اين دو جمله معنا و حوزه مفهومي يکساني داشته باشد اما در يک جمله کلمه مورد نظر اشتباه نوشته شده باشد.
به عنوان مثال دو جمله زير را در نظر بگيرييد
1.Einstein was a German-born theoretical physieist.
2.Einstain was the scientist of physics at 19 century.
در دو جمله بالا Einstein در نقش اسم به کار رفته و هر دو جمله مفهومي نزديک به هم دارند اما در جمله دوم اين کلمه از نظر املايي درست نوشته نشده است. مگر از معيارهاي تشابه مبني بر فرهنگ لغات ديگر براي بررسي ميزان تشابه دو جمله بالا استفاده کنيم به خاطر تفاوت دو کلمه، يا کلمات موجود در جمله ميزان تشابه کمي را نشان مي دهند در حالي که اين دو جمله بر اساس رشته کلمات و مجموعه اي که کلمه مورد نظر در آن است شباهت را اندازه گيري کند. در ادامه به توضيح بخش هاي مختلف مورد استفاده در روش برگزيده خود مي پردازيم.

فصل سوم

استفاده از تکنيکهاي داده کاوي براي کشف و رفع خطاهاي نرم افزار بر پايه ضريب تشابه معنايي متن و خوشه بندي

1.3. مقدمه
مخازن خطاي نرم افزار سالهاست که به کمک مهندسين نرم افزار و مديران براي پياده سازي پروژه ها کوچک و بزرگ نرم افزاري ، متن باز يا بسته آمده است. هر خطا در اين مخازن به صورت فرآيندي جداگانه براي ثبت تمام رويدادها و اعمال نظرهای منطقي وموثر، درطول رفع مشکل و خطا از روي پروژه، از سوي افراد دخيل در پروژه ثبت مي شود. اين کار علاوه بر مزاياي مربوط به پي- گيري روند رفع خطا ، مجموعه اي از دانش نهفته در اين اطلاعات را در اختيار ذينفعان قرار مي دهد. اگر این اطلاعات با حساسيت لازم و دقت کافي استخراج شود در روند تکميل پروژه اثر به سزايي خواهد داشت. از آنجا که اين داده ها بيشتر حاوي متون هستند نياز به الگوريتم ها و معيارهايي براي بررسي متن احساس مي شود. بيشتر اين مخازن و کارهاي قبلي انجام شده از روش های ساده و يا از موتورهاي جستجوگر معمول براي استخراج دانش مفيد استفاده کرده اند.
يکي از نکاتي که پايه اين تحقيق و روش قرار گرفته است، تشابه بين متن توضيحي درباره خطای جديد و متون موجود در موضوع، توضيحات و ديگر متون ثبت شده مربوط به هر خطا است. اين تشابه قابل اندازه گيري است و به يقين متن با تشابه بالاتر مربوط به خطا با تشابه بالاتر به خطای جديد است. اين خطا شانس برطرف کردن خطای جديد را بالاتر برده و زمان رفع آن و در نتيجه هزينه هاي مربوط به آن را کاهش مي دهد. به خاطر دلايلي که در فصل قبل بيان شد، انتخاب يک روش بر پايه تشابه معنايي ضروري است. در اين فصل از روش محاسبه تشابه معنايي بر پايه مجموعه و تشابه خطي براي استفاده در يک بانک خطاي نرم افزاري نمونه براي يافتن راه حل خطا و در نهايت محاسبه پيچيدگي خطا با استفاده از محاسبه طول عمر خطا استفاده مي شود. شکل 3-1 مراحل مختلف روش ارائه شده در اين تحقيق را نشان می دهد .
شکل 3-1- مراحل مختلف روش ارائه شده
در مرحله اول تعدادي خطا به عنوان نمونه کوچکي از يک بانک داده از داده هاي موجود در Bugzilla انتخاب شده. خلاصه، زمان ايجاد و زمان خاتمه (پاسخ قابل قبول) هر کدام استخراج مي شود. در مرحله بعد ميزان تشابه بين نمونه ها با جمله نمونه خطای جديد در پنج مرحله محاسبه و ليست اين تشابهات که اعدادي بين 0 و 1 هستند استخراج مي شود. در مرحله سوم طول عمر خطا ها محاسبه مي شود اين عدد پيچيدگي آنها را نشان مي دهد.(شکل
3-2)

شکل 3-2- مراحل دسته بندی خطا
و در مرحله نهايي اين دو ليست داده عددي خوشه بندي مي شوند تا بتوان نمونه هاي منتخب را براي کمک به حل خطا و نيز پيش بيني مقادير لازم مورد استفاده قرار مي گيرند.

2.3 . محاسبه تشابه معنايي بر پايه مجموعه و تشابه خطي
Islam در روش خود3 روش تشابه را براي برطرف کردن ضعف آنها ترکيب کرد. اين روش روشي متداول در رفع نواقص الگوريتم هاست. براي محاسبه تشابه بين دو جمله يا متن در اين روش سه مرحله کلي وجود دارد. 1. محاسبه تشابه خطي بين کلمات 2. محاسبه تشابه معنايي بر پايه مجموعه 3. محاسبه تشابه بر اساس کلمات متداول 4 . محاسبه تشابه مجموع(محاسبه نهايي).

1.2.3 . شباهت خطي بين کلمات
يکي از روش هاي مورد انتظار در اين نوع اندازه گيري روش طولاني ترين زيردنباله مشترک (LCS )52با کمي تغييرات و نرمال سازي است. سه نسخه اصلاح شده متفاوت از LCS به کار رفته و سپس وزن هاي بدست آمده با هم جمع مي شوند. به اين نکته بايد توجه کرد که نسخه هاي اصلاح شده LCS نتايج بهتري (دقت و جامعيت بالاتر) را نسبت به LCS و يا معيارهاي شباهت ديگر خواهند داشت.

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

اما در اين روش LCS با در نظر گرفتن توامان طول رشته کوتاهتر و بلندتر نرمالسازي مي شود(NLCS)53.

در حالي که در LCS توالي کاراکترها مهم و ضروري نيست، اما اين توالي براي داشتن درجه بالايي از تطبيق در رشته لازم است. اين نکته در روش 54MCLS مورد توجه قرار گرفته است. در اين روش ابتدا با توالي حداقل کاراکتر MCLS1 شروع و تا حداکثر کاراکتر MCLSn پيش مي رود. الگوريتم 1 MCLS1 در زير نشان داده است. همچنين الگوريتم2 MCLSn ، روند کار را مشخص کرده است.
الگوريتم 1MCLS1:( LCSباحداکثرتواليn=1 )

الگوريتم2 :MCLSn ( LCSبا حداکثر تواليn=n )

در الگوريتم اول دو رشته به عنوان ورودي گرفته حداکثر رشته متوالي مشترک در هر دو رشته که با کاراکتر اول رشته کوتاه تر آغاز شده باشد به عنوان خروجي برگردانده مي شود. اگر الگوريتم 2 همين کار را براي تک تک کاراکترها تکرار کرده و بزرگترين رشته متوالي از هر دو رشته را به عنوان خروجي باز مي گرداند. اين دو الگوريتم نيز نرمالسازي مي شوند.
فرمول 3-1
فرمول 3-2
مقادير وزني بدست آمده از سه قبليv₁ و v₂ و v₃ با ضرايب وزنيw₁ وw₂ و w₃ که w₁+w₂+w₃=1 با هم جمع شده و ميزان شباهت دو جمله بدست مي آيد.

در اين جا برايw ها ارزش برابر در نظر گرفته مي شود. به عنوان مثال فرض کنيد که روش را روي دو رشته زير پياده


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