۲-۲۱-۲- مشکلات استنتاج با توزیع توام کامل و راه ‌حل آنها

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

۲-۲۱-۳- مثالی از شبکه‌های بیزی

حال به توضیح مطالب ذکر شده با یک مثال می ‌پردازیم. فرض کنید شما به تازگی یک آژیر دزدی خریده‌اید که در صورت وقوع دزدی، امکان زیادی دارد که به صدا در آید. علاوه بر این، در صورت وقوع زلزله‌های ضعیف هم ممکن است که آژیر به صدا درآید. همچنین، شما دو همسایه به نام‌های ماری و جان دارید که قول‌ داده‌اند در صورت شنیدن صدای آژیر با شما در محل کارتان تماس بگیرند. جان همیشه در صورت به صدا درآمدن آژیر به شما تلفن می‌زند. ولی ممکن است که صدای تلفن شما را گاهی با آژیر اشتباه بگیرد و دراین صورت هم تلفن بزند. ماری موسیقی را با صدای بلند دوست دارد و ممکن است گاهی صدای آژیر را نشنود. حالا با توجه به مشاهده اینکه چه کسی تلفن زده است یا نزده است، می‌خواهیم احتمال دزدی را محاسبه کنیم. شبکه بیزی این قلمرو در شکل (۲-۲)آمده است.[۲۰]
شکل ۲-۲: شبکه بیزی قلمرو دستگاه آژیر [۲۰]
در ابتدا، ساختار این شبکه را توضیح می‌دهیم و بعد در مورد جدول‌های احتمالات شرطی توضیحاتی می‌دهیم. با توجه به شبکه می‌توان دید که دزدی و زلزله به طور مستقیم بر روی به صدا درآمدن آژیر تاثیر می‌گذارند، ولی بر روی تلفن زدن جان یا ماری تاثیر ندارد، زیرا آنها تنها با شنیدن آژیر تلفن می‌زنند که این موضوع در دو یال خارج شده از گره مربوط به آژیر در شبکه معلوم است. بنابراین شبکه نشان می‌دهد که آنها از وقوع زلزله خفیف آگاه نمی‌شوند.
باید توجه داشت که گره‌ای برای نشان دادن اینکه ماری به موسیقی گوش می‌دهد و یا تلفن زنگ می‌زند در شبکه نیست. این موارد در عدم قطعیت (احتمالی بودن) مربوط به یال‌های خروجی از گره به صدار درآمدن آژیر تاثیر داده شده است. به طور کلی روشی برای اینکه به چه عواملی باید در شبکه گره اختصاص داد، وجود ندارد. در واقع، احتمالات شرطی، تمامی عواملی که در شبکه صریحاً نیامده‌اند، را به طور خلاصه در خود دارند. به این طریق، یک عامل[۱۲] ساده می‌تواند به طور تقریبی با یک دنیای پیچیده را مدل کند. میزان این تقریب را می‌توان با اضافه کردن اطلاعات مرتبط به شبکه افزایش داد. توزیع‌های شرطی گره‌ها را با جدول‌های احتمالات شرطی نشان می‌دهند (البته اگر توزیع‌ها پیوسته باشد از روش‌هایی دیگری استفاده می‌شود که بعداً به آنها اشاره خواهد شد). هر سطر در این جدول‌ها نشان دهنده مقدار احتمال مقادیر متغیر راس برای یک حالت شرطی خاصی می‌باشد. هر حالت شرطی یکی از مقدار دهی‌های ممکن به والدین راس را نشان می‌دهد. در جدول آخرین مقدار ممکن برای متغیر راس نمایش داده نمی‌شود، زیرا برابر یک منهای جمع احتمال بقیه مقادیر است. به طور کلی، یک جدول برای یک متغیر بولی با  والد بولی،  مقدار باید داشته باشد. یک راس که هیچ والدی ندارد تنها شامل یک سطر است که احتمالات اولیه مقادیر متغیر راس را نشان می‌دهند.

۲-۲۲- مفاهیم شبکه‌های بیزی

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

۲-۲۲-۱- نمایش توزیع توام کامل

یک شبکه یک توصیف کامل از قلمرو را ارائه می‌دهد. هر عنصر توزیع احتمال توام کامل (که از این به بعد کامل را برای خلاصه‌سازی حذف می‌کنیم)، با استفاده از اطلاعات درون شبکه قابل محاسبه است. یک عنصر در توزیع را می‌توان به صورت عطف مقداردهی متغیر مانند  در نظر گرفت. با توجه به اطلاعات شبکه مقدار یک عنصر را به وسیله رابطه (۶-۲) می توان محاسبه نمود: [۲۰]
(۶-۲)
محاسبه می‌شود که  مقادیر متغیرهای درون  را نشان می‌دهد. بنابراین، هرعنصر توزیع توام به صورت ضرب تعدادی از عناصر جدول‌های احتمالات شرطی محاسبه می‌شود و این جدول‌ها به نوعی تجزیه توزیع توام را انجام می‌دهد. برای نشان دادن این موضوع، احتمال به صدا در آمدن آژیر در حالی که نه زلزله آمده است و نه دزدی شده است در حالیکه جان و ماری هر دو تماس گرفته‌اند را با رابطه (۷-۲) حساب می‌کنیم. از حرف اول متغیرها برای نشان دادن آنها استفاده می‌کنیم:
(۷-۲)
با استفاده از رابطه (۶-۲) می‌توان ایده‌ای برای ساختن ساختار شبکه بیزی بدست آورد. این رابطه مشخص می‌کند که یک شبکه بیزی چه معنی‌ای دارد، ولی به طور صریح روش ساختن شبکه را طوری که یک نمایش مناسب از قلمرو باشد، معلوم نمی‌سازد. باید توجه داشت در یک شبکه فرض بر نوع خاصی از وابستگی بین متغیرها است که لزوماً با واقعیت تطابق ندارد. بنابراین، ما تنها دنبال یک شبکه خوب می‌گردیم نه شبکه‌ای که دقیقاً توزیع توام را مدل کند (چون ممکن است ممکن نباشد). حال نشان می‌دهیم که رابطه(۶-۲) منجر به فرضی در مورد استقلال‌های شرطی می‌شود که به فرایند ساخت شبکه کمک می‌کند.
با توجه به قانون زنجیره‌ای(chain rule) در احتمالات، می‌توانیم احتمال یک عنصر توزیع توام را به صورت:
بنویسیم. با مقایسه این رابطه با رابطه (۶-۲)، پی می‌بریم که شبکه بیزی وقتی دقیقاً برابر توزیع توام است که برای هر متغیر  در شبکه مطایق رابطه (۸-۲) را داشته باشیم:
(۸-۲)
با این فرض که  باشد. رابطه (۸-۲) مشخص می‌کند که شبکه بیزی تنها وقتی دقیقاً برابر توزیع توام است که هر متغیر به طور شرطی مستقل از تمامی متغیرهای رئوس بعدی در ترتیب اندیس رئوس باشد. بنابراین، در صورتی که بخواهیم یک شبکه بیزی خوب بسازیم که تا حدی خوبی به توزیع توام نزدیک باشد، نیاز داریم تا والدهای هر راس را طوری انتخاب کنیم که این خاصیت حفظ شود. یعنی باید والدین راس منتسب به متغیر  را، از رئوس منتسب به  که بر روی  تاثیر مستقیم دارند انتخاب کنیم. برای مثال، فرض کنید، قسمتی از شبکه شکل (۳-۲) را ساخته‌ایم و تنهاتعیین والدین MaryCalls باقیمانده است. والدین راس این متغیر را باید از متغیرهای قبل از این متغیر انتخاب کنیم که چون تنها Alarm به صورت مستقیم بر آن تاثیر می‌گذارد، به عنوان والد آن انتخاب می‌شود. شبکه‌های بیزی با در نظر گرفتن استقلال متغیرها می‌توانند در همان حال که توزیع توام را به خوبی نشان می‌دهند، از نظر محاسباتی هم قابل قبول باشند. اما در قلمروهایی که استقلال بین متغیرها کم است، این شبکه‌ها نیز نمی‌توانند کمکی کنند. در بعضی موارد، وابستگی بین متغیرهایی که آنچنان قوی نیست در نظر گرفته نمی‌شود، تا در مقابل از دست رفتن مقداری از دقت، شبکه از نظر محاسباتی قابل قبول شود. علاوه بر این، ترتیب اضافه کردن متغیرها برای ساختار شبکه هم بسیار موثر و می‌تواند برای قلمرو‌ای که می‌تواند شبکه مناسبی داشته باشد یک شبکه با یال‌های زیاد و غیرقابل قبول از لحاظ محاسباتی نتیجه دهد. این شبکه‌ها نه تنها یال‌های بیشتری دارند، بلکه ما را با سختی حساب احتمالاتی روبرو می‌کنند که بسیار پیچیده می‌تواند باشد (مثلاً احتمال وقوع زلزله در صورت به صدا درآمدن آژیر و صورت گرفتن دزدی).

۲-۲۲-۲- رابطه‌ های استقلال شرطی در شبکه‌های بیزی

تا کنون یک مفهوم عددی برای شبکه‌های بیزی ارائه کردیم و نشان دادیم چگونه استفاده از این مفهوم می‌توان ساختار شبکه بیزی را بدست آورد. در حقیقت، ما برعکس این کار را هم می‌توانیم انجام دهیم. ما می‌توانیم از مفاهیم ساختاری (که وابستگی‌های شرطی کد شده در ساختار گرافی را نشان می‌دهد) برای بدست آوردن جدول‌های احتمالات شرطی و در نتیجه، بدست آوردن مفاهیم عددی استفاده کنیم.
مفاهیم ساختاری با یکی از دو صورت زیر که معادل هستند می‌تواند داده شود :
۱ـ یک گره به صورت شرطی مستقل از گره‌های غیربچه خود است در صورتی که والدهای آن را داده باشند و برای مثال در شکل( ۲-۲)، JohnCalls از Burglary و Earthquake در صورت داده شده بودن مقدار Alarm مستقل است.
۲ـ یک گره به صورت شرطی مستقل از تمامی گره‌های دیگر شبکه در صورت داده شده بودن والدهای آن، فرزندان و والدهای فرزندان آن (یا به عبارت دیگر در صورت داده شده بودن پوشش مارکوفی(MarkovBlanket) آن‌ است. مثلاًBurglary مستقل از JohnCalls و MaryCalls در صورتی که مقادیر Alarm و Earthquake داده شده باشند، است.
توصیفی از این دو نوع نمایش در شکل (۳-۲) آمده است. از این نوع بیان استقلال‌ها و جداول احتمالات شرطی می‌توان توزیع توام را بدست آورد. بنابراین مفاهیم عددی و مفاهیم ساختاری معادل هستند.
 
شکل۳-۲ : ارائه مفاهیم ساختاری به دو صورت معمول[۲۰]

۲-۲۲-۳- نمایش کارآمد توزیع‌های شرطی

در مورد تعیین جدول احتمالات شرطی باید توجه داشت که حتی اگر تعداد والدهاییک گره یک عدد کوچک  باشد، باید  مقدار برای آن گره حساب شود که به دانش زیادی برای تعیین این تعداد مقدار نیاز است. در حقیقت، این بدترین حالات است که فرض کنیم رابطه فرزندان و والدین دلخواه است و بسیاری مواقع یک رابطه مشخص و استاندارد بین مقادیر والدها و بچه برقرار است که کار تعیین توزیع شرطی را ساده می‌کند. مثلاً یک گره ممکن است لزوماً فصل مقادیر بولی والدین خود باشد. علاوه بر این، بسیاری از مسائل دنیای واقعی متغیرهایی پیوسته‌ دارند. نمایش این احتمالات شرطی این متغیرها به صورت جدول ممکن نمی‌باشد. در اینگونه موارد دو روش کلی استفاده می‌شود. یک روش گسسته کردن مقادیر متغیرهای پیوسته است و ایجاد جدول‌های احتمالات شرطی برای مقادیر گسسته آنها است. مشکل این روش این است که کارایی روش و دقت آن به شدت افت می‌کند و علاوه بر آن، اندازه جداول نیز بسیار بزرگ می‌شود. روش دیگر استفاده از توزیع‌های پیوسته استاندارد که با مجموعه‌ای متناهی از پارامترها تعریف می‌شوند، است. مثلاً یک توزیع نرمال شامل دو پارامتر  است و بسیار بکار می‌رود. [۲۰]

۲-۲۳- یادگیری شبکه‌ های بیزی

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

۲-۲۴- استنتاج دقیق در شبکه‌ های بیزی

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

۲-۲۵- استنتاج بوسیله محاسبه تک ‌تک عناصر احتمالی

۲-۲۸-۲- نمونه‌گیری وزن‌دار

دومین دسته روش از روش‌های نمونه‌گیری مستقیم، نمونه‌گیری وزن‌دار می‌باشد که برای حل مشکل نمونه‌گیری با ردکردن طراحی شده است. یکی از مشکلات بزرگ روش نمونه‌گیری با ردکردن این است که ممکن است، احتمال وقوع مشاهدات کم باشد و در نتیجه، یک قسمت اصلی از نمونه‌ها رد می‌شود. این باعث باقیماندن نمونه‌های خیلی کمی می‌شود که برای تقریب خوب، مناسب نمی‌باشند و عملاً استفاده از این روش در قلمروهای پیچیده امکان‌پذیر نمی‌باشد. نمونه‌گیری وزن‌دار مشکل نمونه‌گیری با ردکردن را به این شکل رفع می‌کند که تنها نمونه‌هایی ایجاد می‌کند که سازگار با مشاهدات هستند. این روش مقادیر متغیرهای E را ثابت در نظر می‌گیرد و تنها از مقادیر متغیرهای X و Y نمونه‌گیری می‌کند. باید توجه داشت که این نوع نمونه‌گیری توجه یکسانی به نمونه‌ها نمی‌کند و نمی‌توان تنها تعداد نمونه‌ها را برای محاسبه احتمالات موردنظر درخواست‌ها استفاده کرد. به همین دلیل به هر نمونه‌ وزنی متناسب با احتمال وقوع مشاهدات با توجه به مقادیر متغیرهای دیگر نسبت می‌گیرد و از جمع وزن‌های نمونه‌ها برای محاسبه احتمال موردنظر درخواست استفاده می‌شود. این الگوریتم در شکل (۷-۲) آمده است. باید توجه داشت که این روش نمونه‌گیری، تقریبی سازگار را نتیجه می‌دهد. [۲۳]
شکل ۷-۲ : الگوریتم نمونه‌گیری وزن‌دار[۲۳]
FUNCTION LIKELIHOOD-WEGHTING(X,e,bn,N) returns an estimate of P
Local variables : W, a vector of weighted counts over X , initially Zero
For j = 1 to N do
X , w  Weighted-sample(bn)
W[x]  W[x] + w where x is the value of X in x
Return NORMALIZE(W[x])
FUNCTION WEGHTED –SAMPLE(bn,e) returns an event and a weight
X  an event with n elements: w  ۱
For i= 1 to n do
If X , has a value in e
Then w  w
Else  a random sample from
Return x,w

۲-۲۸-۳- نمونه‌گیری زنجیره مارکوفی

دو روش توضیح داده شده در نمونه‌گیری مستقیم، برای تولید هر نمونه تمامی مقادیر را از ابتدا نمونه‌گیری می‌کنند که ممکن است از نظر زمانی هزینه‌بر باشد. در مقابل، روش‌های مبتنی بر زنجیره مارکوفی هر نمونه را با یک تغییر تصادفی در نمونه قبلی بدست می‌آوردند. به طور دقیق‌تر، هر نمونه جدید به صورت تصادفی از تغیر یکی از متغیرهای غیرمشاهده‌ای نمونه قبلی بدست می‌آید. برای این کار از آن متغیر با فرض داده شده بودن مقدار مقادیر متغیرهای پوشش مارکوفی آن در نمونه قبلی، نمونه‌برداری می‌شود. به این ترتیب نمونه‌گیری زنجیره مارکوفی به حرکت در فضای نمونه‌ها (مقادیر مختلف متغیر‌های غیرمشاهده شده) می‌پردازد. الگوریتم ساده‌ای براساس این ایده در شکل ۸ دیده می‌شود. می‌توان ثابت کرد که نمونه‌گیری زنجیره مارکوفی نیز جز نمونه‌گیرهای سازگار می‌باشد. [۲۳]

شکل ۸-۲ : الگوریتم نمونه‌گیری وزن‌دار[۲۳]

۲-۲۸-۴- جمع‌ بندی شبکه‌های بیزی

Function MCMC-ASK(X,e,bn,N) returns an estimate of P
Local variables : N[X],a vector of counts over X , initially Zero
Z , the nonevidence variables in bn
X , the current state of the network , initially copied from e
Initialize x with random values for the variables in Y
For j = 1 to N do
For each Z, in Z do
Sample the value of in x from P
Given the values M B() in x
N[x]  N[x] +1 where x is the value of X in x

*

T10

*

همانطور که در نگاه اول به شکل (۳-۱) و جدول (۳-۱) متوجه این موضوع می‌شویم که هرکدام از ماژول‌ها توسط یکی از موارد آزمون پوشش داده می‌شوند به نقاط ضعف موجود در آن هم پی می‌بریم. به جهت پیدا کردن خطاهای شدید در موعد مقرر و مناسب، باید موارد آزمون را اولویت بندی کنیم . اولویت بندی کردن موارد آزمون به عنوان مرحله ای از تست رگرسیون نیست، در اینجا، آن دسته از تکنیک های اولویت بندی که تکیه بر اطلاعات موجود در این نوع تست دارند نمی‌تواند در اینجا کاربرد داشته باشند و مفید واقع شوند. علاوه بر این، به دلیل اینکه هریک از موارد آزمونبه همان تعداد از ماژول‌ها را پوشش می‌دهد و ما قادر به شناسایی اولویت موارد آزمون از لحاظ تعداد ماژول تحت پوشش هرکدام از موارد آزمون نخواهیم بود. بنابراین، برای بهبود بخشیدن به سرعت تشخیص یا شناسایی خطاهای شدید برای این مجموعه تست نرم افزار، شاخص‌های اولویت بندی دیگری را باید در اینجا مدنظر قرار دهیم که ما در ادامه معیارها و متریک هایی را که جهت مشخص کردن اولویت موارد آزمون مورد استفاده قرار داده‌ایم را به تفصیر شرح خواهیم داد.

۳-۱- رویکرد پیشنهادی

۳-۱-۱- روند کلی در رویکرد پیشنهادی

رویکرد پیشنهاد شده در این پایان نامه از ۳ بخش تشکیل شده است که در ادامه نمایش می‌دهیم. ما در رویکرد پیشنهادی خود برای حل کردن مشکل تکنیک های اولویت بندی ارائه شده بر تصمیم گیری بر اساس معیارها و فاکتورهای اولویت بندی تمرکز نموده و برای رفع آن نیز از استخراج معیارها و محاسبه هرکدام از معیارهای مورد نظر در بخش‌ها و اطلاعات مختلف بهره می‌بریم، منابع جمع آوری این اطلاعات عبارتند از: کد برنامه، ساختار برنامه، اطلاعات قبلی در دسترس و نظر افراد کارشناس یا متخصص در این حوزه. و همچنین پس از بدست آوردن اطلاعات مورد نیاز جهت تصمیم گیری و اولویت بندی از شبکه‌های بیزی استفاده می‌کنیم تا در نهایت اولویت بندی کارآمد تری را ارائه دهیم. مطالعات تجربی انجام گرفته بر روی شبکه‌های بیزی و همچنین نتایج حاصله از بکار گیری شبکه‌های بیزی ما را به دستیابی به نتایج بهتر از روش‌های دیگر اولویت بندی موارد تست و کارآمد بودن نهایی تست نرم افزار امیدوار می‌کنند. شکل (۳-۲) یک شمای کلی و سطح بالا از روش پیشنهادی ما در این پایان نامه را نشان می‌دهد. در ادامه به شرح هر یک از مراحل کار می‌ پردازیم.
شکل۳-۲ : یک پیاده سازی عمومی برای چارچوب مبتنی بر شبکه‌های بیزی
همانطور که در شکل فوق نشان داده شده ورودی‌های این مدل را ساختار برنامه و داده‌های دردسترس تشکیل می‌دهند. که در مقایسه با دیگر روش‌های اولویت بندی که تا کنون پیشنهاد شده‌اند تفاوت دارد و تفاوت آن هم اینکه نیاز ما را از حیث از قبل دانستن برخی اطلاعات و اینکه شروع فرایند مستلزم وجود آنها باشد را بر طرف می‌کند. همچنین اولین قدم در اولویت بندی چیزی نیست جز جمع آوری تمامی اطلاعاتی که به هرچه کارآمدتر شدن فرایند اولویت بندی کمک می ‌کند. کارآمدتر شدن اولویت بندی را با یک مثال شرح می‌دهیم.فرض کنید برای اینکه برای انجام کاری تصمیم گیری کنید در ابتدا اطلاعات کمی در اختیار دارید و همچنین به همراه این اطلاعات کم نیز اطلاعاتی ناقص و ناکافی هم وجود دارند، حال فرآیند تصمیم گیری بر اساس این اطلاعات صورت می‌گیرد اما حال به نظر شما تصمیم گیری بر اساس این اطلاعات کارامد خواهد بود؟ اما اگر اطلاعات به خوبی و از منابع درست جمع آوری شوند و از افراد کارشناس و متخصص بهره ببریم قطعاَ نتیجه‌ی بهتری از تصمیم گیری خواهیم گرفت.
از دیگر مزایای مدل پیشنهادی ما برای اولویت بندی موارد تست این است که شبکه‌های بیزی در مواردی که اطلاعات نا کافی یا اطلاعات ناقص وجود دارند هم به دلیل بهره بردن از احتمالات شرطی قادر به تصمیم گیری بر اساس اطلاعات موجود خواهد بود.ما در روش خود با در نظر گرفتن منابع اطلاعاتی همچون کد برنامه، اطلاعات قبلی موارد تست اجرا شده، اطلاعات تغییرات، نظرات کارشناسان خبره در این حوزه و ساختار برنامه بهره خواهیم برد.
۳-۲- محاسبه و استخراج شاخص‌ها برای ماژول‌ ها
در این بخش از فرآیند در مدل پیشنهادی خود به ارزیابی معیارهای مورد توجه در این پایان نامه جهت تعیین اولویت موارد آزمون می‌پردازیم. که در ارزیابی هریک از این معیارها با توجه به داده‌های در دسترس(به عنوان مثال، نیازمندی‌های کاربر، تغییرات کد برنامه، داده‌های اجرای قبلی موارد تست ها ( می ‌پردازیم. قبل از اینکه وارد بحث ارزیابی متریک ها شویم معیارهای مورد توجه در این پایان نامه را معرفی می‌کنیم و سپس هر کدام را جداگانه شرح می‌دهیم. در نهایت با یکپارچه سازی این اطلاعات بدست آمده در مدل شبکه بیزی اولویت بندی را انجام می‌دهیم.

Low Severity

۰

شدت کم

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

۳-۵- ساخت شبکه بیزی

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

۳-۶- ایجاد ساختار گراف

شکل ۳-۳ : گراف شبکه بیزی تست کارآمد نرم افزار
در اینجا گراف (۳-۳) که از مرحله قبل ساخته شده است را نمایش می‌دهیم. ارتباطات و وابستگی‌هایی که در گراف فوق مشاهده می‌کنید با توجه به کارهای مشابه و نظرات افراد خبره در حوزه تست نرم افزار تعیین شده است. گراف شبکه بیزی پیشنهاد شده در شکل فوق دارای ویژگی‌های مناسبی است. یکی از مهم‌ترین این ویژگی ها این است که گراف پیشنهادی از استقلال شرطی بسیار خوبی برخوردار است. استقلال شرطی یک مفهوم بسیار مهم است که دانستن آن سبب ساده سازی بسیار خوب مدل می ‌گردد. حتی اگر در مواردی استقلال شرطی واقعا وجود نداشته باشد، فرض وجود استقلال شرطی سبب می ‌شود که بهبود بسیاری در مدل احتمالاتی مورد استفاده صورت گیرد. ولی مدل ارائه شده در اینجا از استقلال شرطی بسیار خوبی برخوردار است. زیرا هر کدام از فاکتورها که در گراف فوق قرار گرفته‌اند با توجه به مفهوم تست به دیگر فاکتورهای در این مدل وابسته‌اند یا اینکه مستقل از آنها هستند که این امر نیز به راحتی از طریق مشاهده گراف قابل درک است. به طور خلاصه می‌توان گفت شبکه بیزی ، نمایش با معنی روابط نامشخص ما بین پارامتر ها در یک حوزه می‌باشد . شبکه بیزی گراف جهت دار غیر حلقوی از نودها برای نمایش متغیرهای تصادفی و کمان‌ها برای نمایش روابط احتمالی ما بین متغیرها به شمار می‌رود . فقدان لبه‌ها در شبکه بیزی نشانگر جملات مستقل از هم می ‌باشد .

۳-۷- محاسبه جداول احتمال شرطی

شبکه بیزی برای نمایش توزیع احتمالی ویژه و اتصال توزیع بر روی همه متغیرها به صورت نودها در گراف نمایش داده می‌شود . این توزیع با یک مجموعه از جدول احتمال شرطی[۱۷] مشخص می‌شود. هر نود به جدول احتمال شرطی منتسب شده و توسط اطلاعات احتمالی کمی مشخص می‌گردد. همانند جدولی احتمالات در وضعیت ممکن از نود در ترکیب ممکن از والدینش مشخص می‌گردد . برای نودهای بدون والد احتمالات بر روی نودهای دیگر بدون قید و شرط می‌باشند که این نودها احتمالات اولیه بر روی متغیرها نامیده می‌شوند . ویژگی‌های فرعی و فاکتورهای مورد نظر تست پیشنهاد شده در این پایان نامه رامی‌توان به دو روش کاملاَ متفاوت در نظر گرفت. در روش اول تأثیر ویژگی‌های فرعی بر روی فاکتور تست مورد نظرشان یکسان است. در مقابل در روش دوم تأثیر ویژگی‌های فرعی بر روی فاکتور مورد نظرشان یکسان نیست و ویژگی‌ها با توجه به وزنشان روی فاکتور مورد نظر تأثیر دارند. اینکه در پروژه ای نرم افزاری ویژگی‌های فرعی هم وزن هستند یا نه، و اینکه وزن هرکدام از ویژگی‌های فرعی و تأثیر آنها روی فاکتور مربوطه چقدر است را متخصصان تست نرم افزار تعیین می ‌کنند. در حالت کلی و استاندارد متخصصان حوزه تست و مهندسان تست روش اول را که در آن همه ‌ی ویژگی‌های فرعی یک فاکتور هم وزن بوده و تأثیر یکسان دارند را در نظر می ‌گیرند.
هر کدام از ویژگی‌های فرعی و فاکتورهای تست و همینطور خود کارآمدی نهایی تست را می ‌توان به اندازه ‌های مختلف درجه بندی نمود. تقسیم بندی‌های صفات کیفی می‌تواند دو تایی ، سه تایی، چهارتایی، پنج تایی باشد. هرچه تعداد این تقسیم بندی ‌ها بیشتر باشد جواب نهایی دقیق‌تر و با جزئیات بیشتری بوده و قابلیت اتکای بیشتری خواهد داشت. اما اگر بخواهیم تعداد صفات کیفی را زیاد کنیم تا دقت جواب نهایی را بالاتر ببریم، در مقابل هم زمان انجام کار و هم افزونگی داده‌ها افزایش می‌یابد. همانطور که با افزایش تعداد تقسیم بندی‌ها، دقت مدل بیشترمی‌شود در مقابل نیز پیاده سازی مدل سخت‌تر از حالت قبل می‌شود. دراین پایان نامه تاکید روی تقسیم بندی سه تایی است. در تقسیم بندی سه تایی اندازه‌ی صفت‌های کیفی، مقادیر در نظر گرفته شده عبارتنداز: کم، متوسط و زیاد .
تعدادحالت‌های مختلف یک فاکتور یا به عبارت دیگر تعداد سطرهای جداول احتمال شرطی فاکتورها به دو مولفه بستگی دارد. یکی تعداد و یژگی‌های فرعی آن فاکتور تست و دوم تعداد حالت‌هایی است که برای آن ویژگی‌های فرعی در نظر گرفته‌ایم . چون تعداد حالت‌های همه‌ی ویژگی‌های فرعی در این پایان نامه به صورت برابر در نظر گرفته شده (سه حالته)پس می‌توان با استفاده از رابطه تعداد سطرهای جداول احتمال شرطی فاکتورها را بدست آورد که در آن P تعداد ویژگی‌های فرعی یک فاکتور تست است و n نیز تعداد حالت‌های مختلف هر کدام از ویژگی‌های فرعی است. برای مثال فاکتور تعداد خطا که دارای سه ویژگی فرعی است. اگر هر یک از ویژگی‌های فرعی را دو حالته در نظر بگیریم جدول تعداد خطا دارای ۸ سطر و اگر هر ویژگی فرعی را سه حالته در نظر بگیریم جدول تعداد خطا دارای ۲۷ سطر خواهد بود و اگر که هر ویژگی فرعی را پنج حالته در نظر بگیریم جدول تعداد خطا دارای ۱۲۵ سطر خواهد بود. آنچه مشخص است این است که تعداد حالت‌هایویژگی‌های فرعی به شدت روی تعداد سطرهای جدول فاکتورها تاثیر خواهد گذاشت. در جدول زیر برای نمایش این وضعیت‌ها و روشن شدن موضوع حالت‌های مختلف برای هر یک از فاکتورها را محاسبه کرده‌ایم و نشان می‌دهیم.
جدول شماره ۳-۳ : تعداد سطرهای جدول احتمال شرطی فاکتورهای تست

در جدول (۳-۳) تعداد سطرهای جدول احتمال شرطی را به تفکیک معیار یا فاکتورهای تست بیان کردیم. جدول احتمال شرطی نهایی برای تست کارآمد نرم افزار در زمانی که فاکتور ها دو حالته باشند ۶۴ سه حالته باشند ۷۲۹ و پنج حالته باشند ۱۵۶۲۵ سطر خواهند داشت. این امر مشخص است که زمانی که فاکتورها را پنج حالته در نظر بگیریم پر کردن جداول احتمال شرطی کاری سخت و دشوار و خیلی زمان بر خواهد بود و چه بسا غیر عملی. زیرا تعداد سطرها بسیار زیاد است و همچنین امکان ورود داده‌های اشتباه در جداول هم افزایش می‌یابد. پس برای پر کردن جداول احتمال شرطی با صفت‌های پنج حالته بایستی از نرم افزارهایی مانند BNJ (پیاده سازی شبکه‌های بیزی با استفاده از JAVA) و BNT (پیاده سازی شبکه‌های بیزی با استفاده از MATLAB ) استفاده نمود. زیرا با استفاده از روش برنامه نویسی می‌توان به صورت خودکار و با استفاده از حلقه‌های تکرار جداول احتمال شرطی را پر نمود.
پس از تقسیم بندی صفت‌های کیفی می ‌بایست آنها را به مقیاس‌های کمی تبدیل نماییم تا بتوانیم فاکتورهای اثر گذار بر فرایند تست نرم افزار و همچنین کارآمد بودن اولویت بندی موارد تست رامحاسبه نماییم. محاسبه‌ی فاکتورها دراین مدل به این صورت است که ابتدا مقادیر بدست آمده از ویژگی‌های فرعی به گونه ای که در ادامه شرح داده خواهد شد به مقادیر کمی تبدیل می‌گردند. از روی محاسبات انجام شده روی این مقادیر کمی، اندازه‌ی فاکتور مربوطه را محاسبه می‌نماییم. به همین طریق و با استفاده از فاکتورهای تست می‌توان کارآمدی تست را با اولویت بندی موارد تست بدین گونه مشخص نمود. با عملکردی این چنین ما قادر خواهیم بود با استفاده از شبکه‌های بیزی و احتمالات کارآمدی از نحوه‌ی اولویت بندی موارد تست را نشان دهیم.

۳-۸- تبدیل اندازه‌ی کیفی صفت‌ها به مقادیرکمی

برای تبدیل اندازه کیفی صفت‌ها به مقادیر کمی ما در رویکردمان دو روش پیشنهادی را نشان می‌دهیم و با یکدیگر مقایسه می‌کنیم. برای توضیح روش‌های پیشنهادی از حالت صفت‌های سه حالته استفاده می‌کنیم زیرا با صفت های کمتر دقت افت می کند و اگر تعداد صفات را زیاد در نظر بگیریم باعث افزایش اضافه کاری و حجم داده زیاد می شود.

۳-۹- روش اول برای صفت‌های سه حالته

در روش اول بدین صورت عمل می‌کنیم که ، ابتدا به هر کدام از ویژگی‌های فرعی مربوط به معیارها یا فاکتورها با توجه به جدول زیر مقدار مربوط به اندازه صفت کیفی را نسبت می‌دهیم.
جدول شماره ۳-۴ : انتساب مقدار عددی به اندازه‌های کیفی در صفت‌های سه حالته

سپس میانگین صفت‌ها را محاسبه می‌نماییم. میانگین بدست آمده در یکی از بازه‌های جدول زیر قرار خواهد گرفت و با توجه به بازه مقدار کیفی صفت مربوطه بدست خواهد آمد. سطر جدول احتمال شرطی مربوطه نیز به این صورت خواهد بود که اندازه‌ی مقدار کیفی بدست آمده برابر ۱۰۰ و مقدار کیفی برای دو مقدار کیفی دیگر برابر ۰ خواهد بود.
جدول شماره ۳-۵ : بازه‌های تبدیل میانگین به اندازه‌های کیفی در صفت‌های سه حالته