مقاله user866

کوتاه‌ترین مسیری که فقط از راس‌های موجود در مجموعه‌ی (k,........,1) استفاده می‌کند.
تعدادی مسیر که از i تا k+1 و سپس از k+1 تا j می‌روند وجود دارد که این مسیر بهتر می‌باشد.
11239597790(1).
ما می‌دانیم که بهترین مسیر از i تا j که فقط از راس‌های بین 1 تا k+1 استفاده می‌کند توسط ShortestPath(i,j,k) تعریف شده است و واضح است که اگر یک مسیر بهتر از i تا k+1 و از k+1 تا j وجود داشته باشد بنابراین طول مسیر بین i,j از الحاق کوتاه‌ترین مسیر از i تا k+1 و کوتاه‌ترین مسیر از k+1 تا j بدست می‌آید. بنابراین تابع ShortestPath(i,j,k) را در فرمول بازگشتی زیر ارائه می‌دهیم:
بنا به تعریف انجام شده، به نظر می‌رسد که الگوریتم وارشال می‌تواند در حل مسأله‌ای مانند یافتن بستار تعدی و وابستگی‌های گذرای گراف وابستگی نرم افزار قابلیت استفاده داشته باشد.
مسأله دیگری که خودنمایی می‌کند، حجم وابستگی‌ها در میان گروهی از گره‌های یک گراف است. در یک گراف جهت‌دار با n گره، میزان وابستگی‌ها می‌تواند در دامنه‌ای از صفر تا n(n-1) قرار بگیرد.
مشخصاً در گرافی که هیچ گونه وابستگی در آن وجود ندارد، ما تنها تعدادی گره مستقل خواهیم داشت. اما گرافی که در آن تمامی گره‌های آن به هم وابستگی دارند، در اصطلاح گراف کامل نامیده می‌شود. به یک گراف و یا زیر گراف کامل، در اصلاح کلیک گفته می‌شود. کلیک مبحثی است که مسائل بسیار زیاد و معروفی با عنوان مسائل کلیک در مورد آن مطرح شده‌اند. بعضی از این مسائل عبارتند از:
یافتن کلیک‌ها با اندازه ثابت در یک گراف.
یافتن تمامی کلیک‌های ماکزیمال در یک گراف.
یافتن تمامی کلیک‌های ماکزیموم در یک گراف.
...
مسأله جذاب و جالب دیگری که در مورد گراف‌ها خودنمایی می‌کند این است که مسأله کلیک، می‌تواند کمک کننده این باشد که قسمت‌هایی از گراف وابستگی نرم‌افزار را که بیشترین چگالی وابستگی ممکن در آن موجود است را پیدا کنیم و ارتباط آن را با خطا نشان دهیم.
کارپ در سال 1947 اثبات کرد که در کل مسائل مربوط به کلیک جزء مسائل ان پی-کامل هستند. به این معنی که هیچ الگوریتم قابل اجرا در زمان چند جمله‌ای برای این مسائل وجود ندارد. این مشکل در جایی خود را بیشتر نشان می‌دهد که گراف وابستگی یک نرم‌افزار معمولی ممکن است شامل چندین هزار گره باشد بنابراین به نظر می‌رسد که مسائل مربوط به کلیک، برخلاف جذابیت بسیاری که در زمینه وابستگی نرم‌افزار از خود نشان می‌دهند، به صورت عملی قابل استفاده نیستند. CITATION Kar75 l 1033 (Karp, 1975)سوال دومی که مطرح می‌شود این است که آیا می‌توان از خصوصیات مسائل مربوط به کلیک در پیدا کردن نقاط مستعد خطای برنامه استفاده نمود یا خیر؟ این سوال از آنجا مطرح می‌شود که وقتی بتوان گروهی از گره‌های یک گراف را پیدا کرد که تشکیل یک کلیک را می‌دهند، در واقع بیشترین وابستگی‌های ممکن بین این گروه از گره‌ها اتفاق افتاده است. سوال این است که آیا این تراکم گره‌ها می‌تواند نشانه‌ای بر مستعد خطا بودن آن بخش از نرم‌افزار باشد یا خیر؟
4-فرضیات:حال سوال این است که هدف از طرح مبحث مورد نظر چیست؟ به عبارتی به چه نتیجه‌ای می‌خواهیم برسیم؟ در پاسخ به این موضوع می‌توان اهدافی را برای ادامه کار مشخص کرد و این اهداف را در اینجا به صورت سوال‌ها و فرضیاتی مطرح می‌کنیم:
الف: آیا درخت وابستگی هیچ‌گونه ارتباطی با خطا دار بودن بخش‌های متناظر در برنامه دارد؟
ب: در صورت بودن ارتباط آیا درخت وابستگی می‌تواند به صورت معیاری برای پیش‌بینی خطا، به صورت عملی مورد استفاده قرار بگیرد؟
ج: عملکرد درخت وابستگی در قیاس با دیگر مشخصه‌های استفاده شده در پیش‌بینی خطا به چه صورتی است؟ آیا عملاً می‌توان بیان کرد که درخت وابستگی، خصوصیتی قابل مقایسه با دیگر مشخصه‌ها و متریک‌های مورد استفاده در پیش‌بینی خطا دارد یا خیر؟
5-جمع آوری داده:برای پاسخگویی به سوالات و فرضیات مطرح شده در بخش قبل، بایستی آن را عملاً مورد آزمایش قرار داد. به همین منظور داده‌ها و ابزارهای مورد نیاز که در این آزمایش مورد استفاده قرار گرفته‌اند در بخش جمع‌آوری داده معرفی می‌شوند.
ابزارهای بسیاری در این راه مورد استفاده قرار گرفت و خروجی‌های متنوعی به دست آمد که در نهایت بخشی از آن‌ها عملاً قابلیت تحلیل و استفاده را در اختیار قرار می‌دادند. برای ابزارها و داده‌های مورد استفاده روند کار را توضیح خواهیم داد.
انتخاب نرم افزار: مقصود از نرم افزار، کد منبعی است که برای انجام آزمایشاتمان مورد باید مورد بررسی قرار بگیرد. با مروری بر انواع برنامه‌ها و مجموعه داده‌های استاندارد که در تحقیقات دیگر مورد بررسی و مطالعه قرار گرفته بود و انواع روش‌های پیش‌بینی خطا و یا تشخیص خطا بر روی آن‌ها آزمایش شده بود، می‌شد به این نتیجه رسید که نسخه‌هایی از برنامه اکلیپس و آپاچی بهترین گزینه برای انجام آزمایشات می‌باشند.
1.1- اکلیپس: یک محیط برنامه‌نویسی چند زبانه می‌باشد که از یک هسته مرکزی ساده تشکیل شده که با افزودن افزونه‌های مختلف به آن، می‌توان امکانات مورد نیاز برای هر توسعه دهنده‌ای را به آن اضافه نمود. این محیط برنامه نویسی در ابتدا برای توسعه برنامه‌های مختلف به زبان جاوا به کار برده می‌شد اما در ادامه با افزودن افزونه‌های مختلف به آن امکان توسعه برنامه‌ها به زبان‌هایی همچون C++، Ruby، Payton و Perl فراهم شد. اکلیپس بر اساس چارچوب مهندسی نرم‌افزار شیء گرا طراحی شده است. از سال 2006، بنیاد اکلیپس نسخه‌هایی را سالانه منتشر کرده و هر نسخه را بر اساس نام ماه‌های سال نام‌گذاری می‌کند. که از آن جمله می‌توان به نسخه‌های ایندیگو، هلیوس، گالیله، گانیمده، اروپا و کالیستو اشاره نمود.
2.1-آپاچی تام کت : یک سرورلت متن باز است که توسط بنیاد نرم‌افزار آپاچی توسعه یافته است. آپاچی تامکت، مشخصه‌های سرورلت جاوا، صفحات JSP و همچنین یک محیط سرور ساده HTTP را پیاده‌سازی می‌نماید.
در کل چند دلیل برای انتخاب مجموعه داده‌های مذکور جهت بررسی و آزمایش بر روی آن‌ها وجود دارد که از قرار زیر است:
نسخه‌های متعددی از ابزارهای مذکور موجود است.
ابزارها همگی متن باز بوده و قابلیت این را دارند که توسط ابزارهای کمکی بر روی آن‌ها آنالیز انجام داد و یا مشخصه‌های مورد نیاز را از آن‌ها استخراج نمود.
در تحقیقات متعددی، محققین از ابزارهای مذکور استفاده کرده‌اند و هرکدام از آن‌ها تقریباً به صورت یک مجموعه داده استاندارد برای تحقیق و آزمایش شناخته می‌شوند.
لیست کلاس‌ها و فایل‌های دارای خطا برای ابزارهای مذکور موجود می‌باشد.
استخراج وابستگی‌های نرم افزار: در ابتدا، برای بررسی وابستگی‌های نرم افزار نیاز داشتیم که بتوانیم این وابستگی‌ها را از کد و یا باینری‌های برنامه، استخراج کنیم و خروجی باید به نحوی باشد که از طریق ابزارهای دیگر قابل بررسی و مطالعه باشد. برای استخراج وابستگی‌های نرم‌افزار، ابزارهای مختلفی مورد بررسی قرار گرفت که در نهایت بهترین ابزاری که بر اساس نوع خروجی انتخاب شد، ابزار CDA بود. CDA مخفف Class Dependency Analyzer است که همان‌طور که از نامش پیداست، ابزاری خاص برای استخراج وابستگی‌های موجود میان کلاس‌های برنامه‌های نوشته شده به زبان جاواست. بزرگ‌ترین نقطه قوت CDA این است که این ابزار می‌تواند وابستگی را در سطوح مختلف بررسی نماید که شامل:
یک کلاس مجزا.
تمامی کلاس‌ها در یک Package
تمامی کلاس‌ها در یک Container
در خروجی نیز نتایج در هر سه سطح Class Level، Package Level و Container Level ارائه می‌شوند. این ابزار همچنین خروجی را که شامل تمامی وابستگی‌های موجود در میان کلاس‌های برنامه ورودی می‌باشد، به صورت یک فایل XML در اختیار قرار می‌دهد.

شکل SEQ شکل_ * ARABIC 3: تصویری از نمای کلی برنامه Class Dependency Analyzerدر بالا تصویری از محیط کلی CDA را مشاهده می‌نمایید. در این تصویر، لیستی از کلاس‌ها و کلاس‌های واسطی را مشاهده می‌نمایید که کلاس ClassTableModel به آن‌ها وابسته است.

شکل SEQ شکل_ * ARABIC 4: نمونه‌ای از کلاس دیاگرام نمایش داده شده در برنامه Class Dependency Analyzerدر بالا، مسیرهای وابستگی از کلاس RepeatedTest به کلاس واسط TestListener نشان داده شده است.

شکل SEQ شکل_ * ARABIC 5: نمایش تمامی کلاس‌های وابسته به یک کلاس خاص در برنامه Class Dependency Analyzerو در تصویر بالا، تمامی کلاس‌هایی را که به کلاس TableEditorModel وابسته هستند، مشاهده می‌نمایید.
تشکیل ماتریس وابستگی: در ادامه، برای بررسی فایل‌های حجیم XML خروجی نیاز به ابزاری بود که بتواند از این فایل، یک گراف وابستگی را بدست آورد. ابزار مورد نظر را به زبان C#.net نوشتیم. ابزار نوشته شده، به گونه‌ای عمل می‌کند که می‌تواند از وابستگی‌های تشخیص داده شده در خروجی CDA یک ماتریس صفر و یک را تشکیل می‌دهد. هر گره یک در ماتریس، وابستگی دو گره مربوط در سطر و ستون را نمایش می‌دهد. از آنجایی که گراف مورد نظر ما یک گراف جهت دار است، بنا بر این سطرها، نشان دهنده گره وابسته در وابستگی به نمایش آمده می‌باشند.
ADBEFC
شکل SEQ شکل_ * ARABIC 6: نمونه‌ای از یک گراف جهت دار.
بنا بر توضیحات ارائه شده، اگر یک گراف وابستگی جهت دار به شکل بالا داشته باشیم، آنگاه ماتریس همسایگی آن به صورت زیر خواهد بود:

شکل SEQ شکل_ * ARABIC 7: ماتریس وابستگی مربوط به گراف جهت دار در شکل شماره 6تشکیل درخت وابستگی برای هر گره: اولین قدم برای تشکیل درخت وابستگی شمارش وابستگی‌های مستقیم گره‌ها می‌باشد. معروف‌ترین راهی که برای شمارش تمامی وابستگی‌های یک گره می‌تواند مطرح باشد، استفاده از الگوریتم وارشال، به شیوه‌ای که در بخش قبل توضیح داده شد می‌باشد. با شمارش وابستگی‌های مستقیم، می‌توان خروجی‌های هر گره را در دست داشت. از طرفی می‌توان به این وابستگی‌ها به چشم یک درخت با عمق 1 نگاه کرد که ریشه آن، گره مورد نظر و برگ‌های آن، گره‌هایی می‌باشند که ریشه به آن‌ها وابسته است.
ایده‌آل‌ترین حالت این است که ابتدا تمامی مسیرهای ممکن را به وسیله الگوریتم وارشال محاسبه بنماییم و سپس شروع به شمارش وابستگی‌های هر گره بکنیم اما وجود دو مشخصه در کار ما مانع از انجام این امر می‌شد:
الگوریتم وارشال یک الگوریتم از درجه 3 می‌باشد.
حجم ماتریس وابستگی در این آزمایشات بسیار بزرگ است به گونه‌ای که ماتریس در برخی مواقع شامل بیش از 12000 سطر و ستون می‌باشد.
زمان اجرای الگوریتم وارشال بر روی گراف‌های با این اندازه بسیار زمان‌بر می‌باشد که با توجه به منابع سخت افزاری محدود در دسترس قادر به اجرای آن نبودیم و علاوه بر آن این روش برای پیدا کردن خطا بهینه نمی‌باشد.
راه حل دیگری که به ذهن می‌رسید، پیاده سازی الگوریتم دیگری بود که مشابه وارشال عمل کند اما میزان پردازش‌ها را تا یک سقف معین محدود نماید. این راه حل دو مزیت به همراه داشت:
ما می‌توانستیم تعداد وابستگی‌ها یا به عبارتی مسیرها را تا هر سطح دلخواه شمارش کرده و از هر کدام از نتایج به دست آمده برای بهبود نتایج پیش‌بینی خطا استفاده نماییم.
الگوریتم بر روی منابع محدودتر قابل پیاده سازی است.
بنا بر این اقدام به پیاده سازی روشی کردیم که همچون الگوریتم وارشال شروع به یافتن تمامی مسیرهای موجود در گراف مورد نظر می‌کند اما این مسیرها را تا عمق محدودی که معین می‌شود، دنبال می‌کند. بنا بر این با استفاده از الگوریتم مورد نظر، شروع به شمارش وابستگی‌های مستقیم گره کردیم و در ادامه وابستگی‌ها را تا عمق‌های 2 و 3 ادامه دادیم.
شیوه شمارش وابستگی‌ها به گونه‌ای است که هر گره به عنوان ریشه انتخاب می‌شود. سپس وابستگی‌های مستقیم ریشه به عنوان برگ‌های اولین درخت تشکیل شده با عمق یک، شمارش شده و نگهداری می‌شود. در ادامه وابستگی‌های موجود در برگ‌های درخت به دست آمده را محاسبه می‌کنیم؛ و اقدام به تشکیل یک درخت جدید با عمق 2 می‌کنیم. در این حالت، تمامی گره‌های درخت دوم را نیز محاسبه کرده و آن را برای استفاده در عمل پیش‌بینی خطا ثبت می‌کنیم. در کل، تشکیل درخت‌های با عمق n با استفاده از درخت‌های یا عمق n-1 به همین شیوه صورت می‌پذیرد و در هر مرحله تمامی گره‌های موجود شمارش شده و برای استفاده در عمل پیش‌بینی خطا نگهداری می‌شود.
بنا بر توضیحات داده شده، اگر روش بالا را برای گره A در گراف شکل (1) پیاده کنیم و درخت آن را تشکیل بدهیم، درخت مورد نظر به صورت زیر نمایش داده خواهد شد:

شکل SEQ شکل_ * ARABIC 8: درخت وابستگی تشکیل شده از روی ماتریس وابستگی شکل 7با نگاهی به گراف شکل (1) مشاهده می‌کنیم که گره A، به سه گره B، E و F وابسته می‌باشد. که در تصویر شماره 3 نیز این وابستگی‌ها مشهود است. نکته دیگری که مورد توجه است، وجود 3 مسیر متفاوت وابستگی از گره A به گره E می‌باشد که در این درخت می‌توان هر سه مسیر وابستگی را مشاهده نمود.
وجود یک عدد مرزی برای در نظر گرفتن محدودیت منابع برای شمارش وابستگی و همچنین در نظر گرفتن وابستگی‌ها در هر سطح مجزا مسأله دیگری است که در مثال ذکر شده مشاهده می‌گردد. برای مثال در شکل بالا ما حداکثر تا عمق 2 وابستگی‌ها را بررسی کرده‌ایم. گرچه برای گراف مذبور عمق وابستگی بیشتر از 2 نیست اما برای گراف‌های بزرگ‌تر با چندین هزار گره مطمئناً محدودیت منابع می‌تواند بسیار چالش بر انگیز باشد و ما مطمئناً به یک عدد مرزی جهت محدود نمودن عمق درخت تشکیل شده برای هر گره، نیازمندیم.
با شمارش تعداد گره‌های هر کدام از درخت‌های به دست آمده در هر سطح می‌توان گروهی از اعداد متناظر با هر فایل را به دست آورد. هر گروه از اعداد را می‌توان به عنوان یک ویژگی در نظر گرفت. با داشتن یک ویژگی در ازای هر درخت می‌توان عمل داده‌کاوی را بر روی داده‌های به دست آمده آزمایش کرد تا ارتباط مسأله و فرضیات طرح شده با خطا دار بودن یا نبودن گره‌ها مشخص گردد.
استخراج متریک‌های استاندارد برای مقایسه و بررسی نتایج: یکی از بهترین راه حل‌ها برای بررسی نتایج به دست آمده از روی داده‌های مختلف، استفاده از متریک‌های استانداردی است که پیش از این مورد استفاده قرار می‌گرفتند. به همین منظور سه دسته از متریک‌های قابل استخراج از برنامه‌های معرفی شده را توسط نرم افزاری به نام Prest استخراج نموده و نتایج را به گونه‌ای که در متن همین پایان نامه توضیح داده خواهد شد مقایسه خواهیم کرد. متریک‌های استخراج شده توسط Prest، در تحقیقات افرادی برجسته‌ای مانند آقای تورهان مورد استفاده و مقایسه قرار گرفته است.
5-تحلیل و مقایسه:در بخش آنالیز و مقایسه، برای بررسی عملکرد ویژگی‌های تعریف شده و بررسی آن از دیدگاه‌های مختلف از چند جنبه مسأله را مورد بررسی قرار می‌دهیم:
بررسی رفتاری: به معنی بررسی رفتار گره‌های مستعد خطای گراف وابستگی در مقابل افزایش یافتن هرکدام از ویژگی‌های تعریف شده.
مقایسه: مقایسه شیوه عملکرد ویژگی‌های تعریف شده، در مقابل شیوه‌های استانداردی که تا پیش از این مورد استفاده قرار گرفته بود.
بررسی رفتاری:
اگر تصور کنیم که یک نرم‌افزار دارای درصد خاصی از خطاها است، برای مثال اگر تصور کنیم که 15 درصد کلاس‌ها یا ماژول‌های یک برنامه خطا دار باشد، با انتخابی تصادفی از میان ماژول‌ها یا کلاس‌ها به طور منطقی پراکندگی خطا در میان کلاس‌های انتخاب شده به صورت میانگین باید عددی نزدیک به 15 باشد؛ و اگر این عمل را به صورت مداوم انجام دهیم، میانگین پراکندگی خطا در هرکدام از دسته‌های انتخاب شده بر روی نمودار به صورت یک خط تقریباً موازی با محور X ها و یا محور Y خواهد داشت. این موضوع به این دلیل است که در انتخاب‌های تصادفی با هر حجمی، نسبت خطا با وجود درصدی فاصله، تقریباً حفظ می‌شود.
حال اگر بتوان معیاری را پیدا کرد که انتخاب گروه‌هایی از گره‌های گراف وابستگی، بر اساس این معیار، به صورت مداوم عددی را نشان دهد که از میزان نسبت گره‌های انتخاب شده تصادفی، به کل گره‌های گراف بیشتر باشد، توانسته‌ایم از یک انتخاب تصادفی موفق‌تر عمل نماییم؛ و البته این موضوع می‌تواند نشانه‌ای باشد بر این موضوع که خطادار بودن یک یا گروهی از گره‌ها، با معیار تعریف شده، ارتباط مستقیم دارد. بنابراین ابتدا به مقایسه رفتار انتخاب دسته‌های تصادفی در مقابل انتخاب دسته‌ها با توجه به مفهوم درخت وابستگی می‌پردازیم.
اگر محور x ها را به عنوان معیار تعداد انجام آزمایشات در نظر بگیریم، هر بار معیار دقت یا Precision را در ازای هر دسته انتخاب شده بررسی می‌کنیم و y هر نقطه از خط ترسیمی را میزان نسبی دقت تشکیل می‌دهد. در اینجا معیار دقت، برابر است با نسبت گره‌های خطادار در ازای کل گره‌های انتخاب شده.
2015490289560
(2).
در فرمول بالا tp نشان دهنده تعداد گره‌های انتخاب شده صحیح است. از آنجایی که در جستجوی گره‌های خطادار هستیم، منظور از گره‌های انتخاب شده صحیح، همان گره‌های خطادار است. fp گره‌های انتخاب شده غلط را نشان می‌دهد. به این معنی که گره‌هایی که در میان دسته‌ها انتخاب شده‌اند و دارای خطا نیستند.
در مورد انتخاب‌های تصادفی، محور x ها تنها نشان دهنده تعداد دفعات انتخاب می‌باشد اما در مورد انتخاب‌ها بر اساس معیارهای درخت وابستگی، هر عدد نشان دهنده یک فیلتر است. فیلتر به این گونه عمل می‌کند که در انتخاب گره‌ها، همیشه تمامی گره‌هایی که تعداد گره‌های درخت متناظرشان از عدد مورد نظر بیشتر باشد انتخاب می‌شوند.
ممکن است این سوال پیش بیاید که چرا یک معیار یکسان برای هردو نوع انتخاب مورد استفاده قرار نگرفته است، و پاسخ این است که در انتخاب‌های تصادفی تعداد گره‌های انتخابی هر عددی که باشد، باز هم نسبت گره‌های خطادار انتخاب شده، تقریباً حفظ می‌شود. ممکن است که در دو انتخاب، این نسبت با هم متفاوت باشد اما در انتخاب‌های زیاد و به طور میانگین، چندان از نسبت کل خطاها به کل گره‌ها دور نمی‌شویم.
با توضیحات داده شده، در سه نمودار زیر به بررسی سوال مطرح شده می‌پردازیم:

نمودار SEQ نمودار_ * ARABIC 2: بررسی رفتار معیار دقت در هنگام افزایش وابستگی درجه 1
نمودار SEQ نمودار_ * ARABIC 3: بررسی رفتار معیار دقت در هنگام افزایش وابستگی درجه 2
نمودار SEQ نمودار_ * ARABIC 4: بررسی رفتار معیار دقت در هنگام افزایش وابستگی درجه 3همان‌طور که در هرکدام از سه نمودار بالا مشهود است، با افزایش یافتن میزان وابستگی‌ها احتمال خطادار بودن یک گره از گراف وابستگی نرم‌افزار نیز افزایش میابد. در اولین نمودار، وابستگی‌های مستقیم مورد بررسی قرار گرفته است و در ادامه وابستگی‌های تک واسطه و دو واسطه در نظر گرفته شده است که هر سه ویژگی ارتباط مستقیم خود را با خطادار بودن یا نبودن گره‌ها در صورت افزایش این نوع وابستگی‌ها نشان می‌دهند.
در بررسی رفتاری به این نتیجه رسیدیم که میزان دقت برای یافتن فایل‌های خطادار با افزایش میزان وابستگی‌ها، افزایش می‌یابد. اما نسبت نشان داده شده، گرچه رشد چند برابری احتمال یافتن خطا را در میان دسته انتخاب شده نشان می‌دهد، اما این میزان، نسبت به کل خطاها می‌تواند بسیار ناچیز باشد. برای مثال وقتی 50% فایل‌های انتخاب شده دارای خطا باشند، این 50% می‌توانند تنها شامل 2% کل خطاهای نرم افزار باشند. به معیاری که میزان خطاهای یافت شده را نسبت به کل خطاها در نظر می‌گیرد اصطلاحاً فراخوان یا Recall گفته می‌شود. نکته قابل تأمل دیگری که مطرح است این است که میزان دقت و فراخوانی که محاسبه می‌گردد تنها در ازای تعداد گره‌هایی در نظر گرفته شده که در واقع به صورت صحیح خطادار شناخته شده‌اند اما به میزان گره‌هایی که به درستی بودن خطا تشخیص داده شده‌اند توجهی نشده است. بنا بر این باید با استفاده از روشی، تمامی این سوال‌ها پاسخ داده شوند. بهترین و رایج‌ترین راه برای پاسخ دادن به این سوالات استفاده از داده‌کاوی است.
در واقع داده کاوی به بهره گیری از ابزارهای تجزیه و تحلیل داده‌ها به منظور کشف الگوها و روابط معتبری که تا کنون ناشناخته بوده‌اند اطلاق می‌شود. این ابزارها ممکن است مدل‌های آماری، الگوریتم‌های ریاضی و روش‌های یاد گیرنده (Machine Laming Method) باشند که کار این خود را به صورت خودکار و بر اساس تجربه‌ای که از طریق شبکه‌های عصبی (Neural Networks) یا درخت‌های تصمیم گیری (Decision Tree) به دست می‌آورند بهبود می‌بخشد.
داده کاوی منحصر به گردآوری و مدیریت داده‌ها نبوده و تجزیه و تحلیل اطلاعات و پیش بینی را نیز شامل می‌شود برنامه‌های کاربردی که با برسی فایل‌های متن یا چند رسانه‌ای به کاوش داده‌ها می‌پردازند پارامترهای گوناگونی را در نظر می‌گیرد که عبارتند از:
رابطه : الگوهایی که بر اساس آن یک رویداد به دیگری مربوط می‌شود مثلاً خرید قلم به خرید کاغذ.
ترتیب : الگویی که به تجزیه و تحلیل توالی رویدادها پرداخته و مشخص می‌کند کدام رویداد رویدادهای دیگری را در پی دارد مثلاً تولد یک نوزاد و خرید پوشک.
دسته بندی : شناسایی الگوهای جدید و مدل سازی برای شناسایی ارتباطات میان دسته‌های مشخصی از ویژگی‌ها با بقیه ویژگی‌های داده.
خوشه بندی : کشف و مستند سازی مجموعه‌ای از حقایق ناشناخته مثلاً موقعیت جغرافیایی خرید محصولی با مارک خاص.
پیش بینی : کشف الگوهایی که بر اساس آن‌ها پیش بینی قابل قبولی از رویدادهای آتی ارایه می‌شود،
از آنجایی که هدف ما از استفاده از داده‌کاوی در این آزمایشات، نشانه گیری گره‌های خطادار است، بهترین استفاده از داده‌کاوی، از طریق دسته بندی عملی خواهد شد. بنا بر این ابتدا یک مرور کلی بر روی تعریف کامل‌تر دسته بندی خواهیم داشت و پس از آن نحوه استفاده از آن را در آزمایشات این پایان نامه بررسی خواهیم نمود.
دسته بندی:
دسته‌بندی در واقع یکی از کاربردهای داده‌کاوی است که به منظور هدف قرار دادن گروهی از کلاس‌ها و یا دسته‌ها، سایر ویژگی‌ها و دسته‌ها را با در نظر گرفتن مدل‌های تصمیم گیری و قوانین خاصی، مورد بررسی قرار می‌دهد. هدف نهایی دسته‌بندی در واقع پیش‌بینی دقیق رفتار کلاس هدف، با توجه به هر شکلی از داده‌های ورودی است. برای مثال، با استفاده از دسته‌بندی می‌توان تشخیص داد که با شرایط در نظر گرفته شده، گرفتن یک وام می‌تواند دارای یک ریسک بالا، متوسط و یا پایین باشد.
در واقع، دسته‌بندی باید با گروهی از کلاس‌ها صورت بگیرد که با کلاس هدف ارتباط داشته باشد. برای مثال اگر برای پیش‌بینی ریسک یک وام جدید از دسته‌بندی استفاده می‌کنیم، باید کلاس‌های دیگر همگی شامل اطلاعات مرتبطی با مسأله بیمه باشند. معمولاً این حجم اطلاعات، در طی زمان و تجارب استفاده کنندگان به دست می‌آیند. البته ممکن است که برخی از این کلاس‌ها در ظاهر با کلاس هدف و با موضوع پیش‌بینی ارتباطی نداشته باشند اما در افزایش دقت پیش‌بینی تأثیر داشته باشند. البته با کمی تحقیق و بررسی همیشه دلایل منطقی پشت این ارتباطات را می‌توان یافت.
از ساده‌ترین مسائل دسته‌بندی می‌توان به دسته‌بندی دودویی اشاره نمود. در این نوع از دسته‌بندی، کلاس هدف تنها شامل دو نوع مقدار است. اگر موضوع این پایان‌نامه را بخواهیم در نظر بگیریم، کلاس هدف ما شامل مقادیر خطادار و بدون خطا می‌باشد. گونه دیگر این کلاس‌ها، کلاس‌های چند مقداری هستند که بیش از دو نوع مقدار را در خود جای می‌دهند.
در مرحله ساخت مدل، الگوریتم دسته‌بندی ارتباط صفات پیش‌بینی کننده را با کلاس هدف به دست می‌آورد. الگوریتم‌های دسته‌بندی مختلف از روش‌های مختلفی برای ساخت مدل استفاده می‌کنند. بعد از این که مدل ساخته شد، می‌توان از آن برای پیش‌بینی وضعیت‌های شناخته نشده جدید استفاده نمود. برای بررسی دقت پیش‌بینی هر کدام از الگوریتم‌های دسته‌بندی، مدل ساخته شده را با گروهی از مقادیر ناشناخته که قبلاً به الگوریتم برای یادگیری داده نشده آزمایش می‌کنیم. بنا بر این، داده‌هایی که برای ساخت و آزمایش یک مدل پیش‌بینی انتخاب می‌شوند، دو دسته هستند:
یک دسته برای آموزش و مدل سازی دسته‌بندی کننده.
یک دسته برای بررسی و تست دسته‌بندی کننده.
برای بررسی نتایج تست دسته بندی از یک سری پارامترها استفاده می‌گردد که پیش از بررسی نتایج آزمایش مورد بحث در این پایان نامه، به توضیح آن می‌پردازیم:
دقت : بعد از انتخاب دسته‌ها بر اساس معیارها و یا مدل‌های مورد نظر، این پارامتر نشان می‌دهد که چند درصد از رکوردهای انتخاب شده، به درستی انتخاب شده‌اند.
فراخوانی : همان‌طور که پیش از این هم توضیح داده شد، Recall یا فراخوانی نشان دهنده انتخاب درست گره‌های خطادار، از میان کلیه گره‌های خطا دار است.
1904365231775
(3).
در فرمول بالا، fn نشان دهنده گره‌های خطا داری هستند که به اشتباه به عنوان گره خطادار شناخته نشده اند.
معیار F: با در نظر گرفتن دو معیار معرفی شده قبلی، یعنی Precision و Recall و بر اساس یک فرمول ساده، امتیازی را محاسبه می‌نماید. این امتیاز در واقع میانگین وزنی بین این دو معیار را در قالب عددی بین صفر و یک نشان می‌دهد به گونه‌ای که 0 نشان دهنده بدترین پاسخ و 1 نشان دهنده بهترین پاسخ است.
1675765224155
(4).
منحنی مشخصه عملکرد سیستم : که وسیله‌ایست که برای مقایسه اهداف پیش‌بینی شده و اهداف واقعی به کار می‌رود. مقدار ROC می‌تواند عددی بین 0 تا 1 باشد. اگر عدد حاصل برابر. یا بیشتر از 0.5 باشد، به این معناست که مدل ما قادر به پیش‌بینی کلاس‌های هدف می‌باشد، و اگر کمتر از 0.5 باشد، به این معناست که عمل پیش‌بینی موفقیت آمیز نیست.
ناحیه زیر منحنی : که مساحت ناحیه زیر منحنی ROC را نشان می‌دهد. ناحیه زیر منحنی در واقع قابلیت تمیز دادن داده‌ها در یک دسته‌بندی دودویی را نشان می‌دهد. هرچه ناحیه زیر منحنی گسترده‌تر باشد به این معناست که احتمال یافتن گره‌های هدف بیشتر، و احتمال حذف گره‌های غیر هدف هم بیشتر است.
صحت : به معنای صحت و دقت می‌باشد. همان‌طور که میدانیم، Precision و Recall با مورد توجه قرار دادن تنها گره‌های هدف سعی در نشان دادن عملکرد دسته‌بندی دارند اما معیار دیگری که با دقت بیشتری می‌تواند نتیجه کار را انجام دهد Accuracy است که با در نظر گرفتن گره‌هایی که به صورت صحیح مورد هدف قرار نگرفته‌اند عمل می‌کند.
1379220-42545(5).
همان‌طور که گفته شد، الگوریتم مختلفی برای عمل دسته‌بندی وجود دارد که در ادامه به آنالیز ویژگی‌های تعریف شده در این پایان نامه به واسطه برخی از این دسته‌بندی کننده‌ها می‌پردازیم.
برای مشخص کردن میزان موفقیت در عملکرد درخت وابستگی در پیش‌بینی خطاها آن را با سه دسته از متریک‌های معروف که پیش از این مورد استفاده قرار گرفته‌اند و در تحقیقات و مقالات بسیاری از آن‌ها استفاده شده، مقایسه خواهیم نمود.
انحراف معیار : انحراف معیار نوعی سنجش پراکندگی برای یک توزیع احتمال یا متغیر تصادفی بوده، و نشان دهنده پخش شدگی مقادیر آن حول مقدار میانگین است. انحراف معیار را معمولاً با σ (حرف کوچک سیگما) نشان می‌دهند. انحراف معیار برابر با ریشه دوم واریانس تعریف می‌شود.
کاپا:

شکل SEQ شکل_ * ARABIC 9: متغیر تصادفی، انحراف معیار σ حول محور μدسته بندی:
آنالیز و مقایسه عملکرد بر روی اکلیپس:
در این بخش آزمایش دسته‌بندی را توسط الگوریتم دسته‌بندی ClassificationViaClustering انجام می‌دهیم. ابتدا به بررسی آنالیزهای حاصل از کار بر روی پروژه‌های اکلیپس که پیش از این توضیح داده شد می‌پردازیم. همان‌طور که پیش از این هم توضیح دادیم، نتایج حاصل از درخت وابستگی را که شامل درخت وابستگی با عمق 1، درخت وابستگی با عمق 2 و درخت وابستگی با عمق 3 می‌شود را با گروهی از متریک‌های خروجی برنامه Prest با عنوان معیارهای پیچیدگی و همچنین مجموعه‌ای شامل 198 متریک که توسط زیمرمن در سال 2007 در کنفرانس ICSE مطرح شد با عنوان Z&Z مقایسه می‌کنیم.
1-1- دقت:

نمودار SEQ نمودار_ * ARABIC 5: مقایسه نتیجه «دقت» در دسته بندی سه نسخه اکلیپس.
1-2- فراخوانی:

نمودار SEQ نمودار_ * ARABIC 6: مقایسه نتیجه «فراخوانی» در دسته بندی سه نسخه اکلیپس.
1-3- صحت:

نمودار SEQ نمودار_ * ARABIC 7: مقایسه نتیجه «صحت» در دسته بندی سه نسخه اکلیپس.
1-4- معیار F:

نمودار SEQ نمودار_ * ARABIC 8: مقایسه نتیجه «معیار F» در دسته بندی سه نسخه اکلیپس.
1-5- منحنی مشخصه عملکرد:

نمودار SEQ نمودار_ * ARABIC 9: مقایسه نتیجه «منحنی مشخصه عملکرد» در دسته بندی سه نسخه اکلیپس.
1-6- کاپا:

نمودار SEQ نمودار_ * ARABIC 10: مقایسه نتیجه «کاپا» در دسته بندی سه نسخه اکلیپس.
1-7- انحراف معیار:

نمودار SEQ نمودار_ * ARABIC 11: مقایسه نتیجه «انحراف معیار» در دسته بندی سه نسخه اکلیپس.

پاسخ دهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *