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

راه حل دیگری که به ذهن می‌رسید، پیاده سازی الگوریتم دیگری بود که مشابه وارشال عمل کند اما میزان پردازش‌ها را تا یک سقف معین محدود نماید. این راه حل دو مزیت به همراه داشت:
ما می‌توانستیم تعداد وابستگی‌ها یا به عبارتی مسیرها را تا هر سطح دلخواه شمارش کرده و از هر کدام از نتایج به دست آمده برای بهبود نتایج پیش‌بینی خطا استفاده نماییم.
الگوریتم بر روی منابع محدودتر قابل پیاده سازی است.
بنا بر این اقدام به پیاده سازی روشی کردیم که همچون الگوریتم وارشال شروع به یافتن تمامی مسیرهای موجود در گراف مورد نظر می‌کند اما این مسیرها را تا عمق محدودی که معین می‌شود، دنبال می‌کند. بنا بر این با بهره گرفتن از الگوریتم مورد نظر، شروع به شمارش وابستگی‌های مستقیم گره کردیم و در ادامه وابستگی‌ها را تا عمق‌های ۲ و ۳ ادامه دادیم.
شیوه شمارش وابستگی‌ها به گونه‌ای است که هر گره به عنوان ریشه انتخاب می‌شود. سپس وابستگی‌های مستقیم ریشه به عنوان برگ‌های اولین درخت تشکیل شده با عمق یک، شمارش شده و نگهداری می‌شود. در ادامه وابستگی‌های موجود در برگ‌های درخت به دست آمده را محاسبه می‌کنیم؛ و اقدام به تشکیل یک درخت جدید با عمق ۲ می‌کنیم. در این حالت، تمامی گره‌های درخت دوم را نیز محاسبه کرده و آن را برای استفاده در عمل پیش‌بینی خطا ثبت می‌کنیم. در کل، تشکیل درخت‌های با عمق n با بهره گرفتن از درخت‌های یا عمق n-1 به همین شیوه صورت می‌پذیرد و در هر مرحله تمامی گره‌های موجود شمارش شده و برای استفاده در عمل پیش‌بینی خطا نگهداری می‌شود.
بنا بر توضیحات داده شده، اگر روش بالا را برای گره A در گراف شکل (۱) پیاده کنیم و درخت آن را تشکیل بدهیم، درخت مورد نظر به صورت زیر نمایش داده خواهد شد:
شکل ۸: درخت وابستگی تشکیل شده از روی ماتریس وابستگی شکل ۷
با نگاهی به گراف شکل (۱) مشاهده می‌کنیم که گره A، به سه گره B، E و F وابسته می‌باشد. که در تصویر شماره ۳ نیز این وابستگی‌ها مشهود است. نکته دیگری که مورد توجه است، وجود ۳ مسیر متفاوت وابستگی از گره A به گره E می‌باشد که در این درخت می‌توان هر سه مسیر وابستگی را مشاهده نمود.
وجود یک عدد مرزی برای در نظر گرفتن محدودیت منابع برای شمارش وابستگی و همچنین در نظر گرفتن وابستگی‌ها در هر سطح مجزا مسأله دیگری است که در مثال ذکر شده مشاهده می‌گردد. برای مثال در شکل بالا ما حداکثر تا عمق ۲ وابستگی‌ها را بررسی کرده‌ایم. گرچه برای گراف مذبور عمق وابستگی بیشتر از ۲ نیست اما برای گراف‌های بزرگ‌تر با چندین هزار گره مطمئناً محدودیت منابع می‌تواند بسیار چالش بر انگیز باشد و ما مطمئناً به یک عدد مرزی جهت محدود نمودن عمق درخت تشکیل شده برای هر گره، نیازمندیم.
با شمارش تعداد گره‌های هر کدام از درخت‌های به دست آمده در هر سطح می‌توان گروهی از اعداد متناظر با هر فایل را به دست آورد. هر گروه از اعداد را می‌توان به عنوان یک ویژگی در نظر گرفت. با داشتن یک ویژگی در ازای هر درخت می‌توان عمل داده‌کاوی را بر روی داده‌های به دست آمده آزمایش کرد تا ارتباط مسأله و فرضیات طرح شده با خطا دار بودن یا نبودن گره‌ها مشخص گردد.
استخراج متریک‌های استاندارد برای مقایسه و بررسی نتایج: یکی از بهترین راه حل‌ها برای بررسی نتایج به دست آمده از روی داده‌های مختلف، استفاده از متریک‌های استانداردی است که پیش از این مورد استفاده قرار می‌گرفتند. به همین منظور سه دسته از متریک‌های قابل استخراج از برنامه‌های معرفی شده را توسط نرم افزاری به نام Prest استخراج نموده و نتایج را به گونه‌ای که در متن همین پایان نامه توضیح داده خواهد شد مقایسه خواهیم کرد. متریک‌های استخراج شده توسط Prest، در تحقیقات افرادی برجسته‌ای مانند آقای تورهان مورد استفاده و مقایسه قرار گرفته است.
۵-تحلیل و مقایسه:
در بخش آنالیز و مقایسه، برای بررسی عملکرد ویژگی‌های تعریف شده و بررسی آن از دیدگاه‌های مختلف از چند جنبه مسأله را مورد بررسی قرار می‌دهیم:
بررسی رفتاری: به معنی بررسی رفتار گره‌های مستعد خطای گراف وابستگی در مقابل افزایش یافتن هرکدام از ویژگی‌های تعریف شده.
مقایسه: مقایسه شیوه عملکرد ویژگی‌های تعریف شده، در مقابل شیوه‌های استانداردی که تا پیش از این مورد استفاده قرار گرفته بود.
بررسی رفتاری:
اگر تصور کنیم که یک نرم‌افزار دارای درصد خاصی از خطاها است، برای مثال اگر تصور کنیم که ۱۵ درصد کلاس‌ها یا ماژول‌های یک برنامه خطا دار باشد، با انتخابی تصادفی از میان ماژول‌ها یا کلاس‌ها به طور منطقی پراکندگی خطا در میان کلاس‌های انتخاب شده به صورت میانگین باید عددی نزدیک به ۱۵ باشد؛ و اگر این عمل را به صورت مداوم انجام دهیم، میانگین پراکندگی خطا در هرکدام از دسته‌ه ای انتخاب شده بر روی نمودار به صورت یک خط تقریباً موازی با محور X ها و یا محور Y خواهد داشت. این موضوع به این دلیل است که در انتخاب‌های تصادفی با هر حجمی، نسبت خطا با وجود درصدی فاصله، تقریباً حفظ می‌شود.
حال اگر بتوان معیاری را پیدا کرد که انتخاب گروه‌هایی از گره‌های گراف وابستگی، بر اساس این معیار، به صورت مداوم عددی را نشان دهد که از میزان نسبت گره‌های انتخاب شده تصادفی، به کل گره‌های گراف بیشتر باشد، توانسته‌ایم از یک انتخاب تصادفی موفق‌تر عمل نماییم؛ و البته این موضوع می‌تواند نشانه‌ای باشد بر این موضوع که خطادار بودن یک یا گروهی از گره‌ها، با معیار تعریف شده، ارتباط مستقیم دارد. بنابراین ابتدا به مقایسه رفتار انتخاب دسته‌ه ای تصادفی در مقابل انتخاب دسته‌ ها با توجه به مفهوم درخت وابستگی می‌پردازیم.
اگر محور x ها را به عنوان معیار تعداد انجام آزمایشات در نظر بگیریم، هر بار معیار دقت یا Precision را در ازای هر دسته انتخاب شده بررسی می‌کنیم و y هر نقطه از خط ترسیمی را میزان نسبی دقت تشکیل می‌دهد. در اینجا معیار دقت، برابر است با نسبت گره‌های خطادار در ازای کل گره‌های انتخاب شده.
(۲).
در فرمول بالا tp نشان دهنده تعداد گره‌های انتخاب شده صحیح است. از آنجایی که در جستجوی گره‌های خطادار هستیم، منظور از گره‌های انتخاب شده صحیح، همان گره‌های خطادار است. fp گره‌های انتخاب شده غلط را نشان می‌دهد. به این معنی که گره‌هایی که در میان دسته‌ ها انتخاب شده‌اند و دارای خطا نیستند.
در مورد انتخاب‌های تصادفی، محور x ها تنها نشان دهنده تعداد دفعات انتخاب می‌باشد اما در مورد انتخاب‌ها بر اساس معیارهای درخت وابستگی، هر عدد نشان دهنده یک فیلتر است. فیلتر به این گونه عمل می‌کند که در انتخاب گره‌ها، همیشه تمامی گره‌هایی که تعداد گره‌های درخت متناظرشان از عدد مورد نظر بیشتر باشد انتخاب می‌شوند.
ممکن است این سوال پیش بیاید که چرا یک معیار یکسان برای هردو نوع انتخاب مورد استفاده قرار نگرفته است، و پاسخ این است که در انتخاب‌های تصادفی تعداد گره‌های انتخابی هر عددی که باشد، باز هم نسبت گره‌های خطادار انتخاب شده، تقریباً حفظ می‌شود. ممکن است که در دو انتخاب، این نسبت با هم متفاوت باشد اما در انتخاب‌های زیاد و به طور میانگین، چندان از نسبت کل خطاها به کل گره‌ها دور نمی‌شویم.
با توضیحات داده شده، در سه نمودار زیر به بررسی سوال مطرح شده می‌پردازیم:
نمودار ۲: بررسی رفتار معیار دقت در هنگام افزایش وابستگی درجه ۱
نمودار ۳: بررسی رفتار معیار دقت در هنگام افزایش وابستگی درجه ۲
نمودار ۴: بررسی رفتار معیار دقت در هنگام افزایش وابستگی درجه ۳
همان‌طور که در هرکدام از سه نمودار بالا مشهود است، با افزایش یافتن میزان وابستگی‌ها احتمال خطادار بودن یک گره از گراف وابستگی نرم‌افزار نیز افزایش میابد. در اولین نمودار، وابستگی‌های مستقیم مورد بررسی قرار گرفته است و در ادامه وابستگی‌های تک واسطه و دو واسطه در نظر گرفته شده است که هر سه ویژگی ارتباط مستقیم خود را با خطادار بودن یا نبودن گره‌ها در صورت افزایش این نوع وابستگی‌ها نشان می‌دهند.
در بررسی رفتاری به این نتیجه رسیدیم که میزان دقت برای یافتن فایل‌های خطادار با افزایش میزان وابستگی‌ها، افزایش می‌یابد. اما نسبت نشان داده شده، گرچه رشد چند برابری احتمال یافتن خطا را در میان دسته انتخاب شده نشان می‌دهد، اما این میزان، نسبت به کل خطاها می‌تواند بسیار ناچیز باشد. برای مثال وقتی ۵۰% فایل‌های انتخاب شده دارای خطا باشند، این ۵۰% می‌توانند تنها شامل ۲% کل خطاهای نرم افزار باشند. به معیاری که میزان خطاهای یافت شده را نسبت به کل خطاها در نظر می‌گیرد اصطلاحاً فراخوان یا Recall گفته می‌شود. نکته قابل تأمل دیگری که مطرح است این است که میزان دقت و فراخوانی که محاسبه می‌گردد تنها در ازای تعداد گره‌هایی در نظر گرفته شده که در واقع به صورت صحیح خطادار شناخته شده‌اند اما به میزان گره‌هایی که به درستی بودن خطا تشخیص داده شده‌اند توجهی نشده است. بنا بر این باید با بهره گرفتن از روشی، تمامی این سوال‌ها پاسخ داده شوند. بهترین و رایج‌ترین راه برای پاسخ دادن به این سوالات استفاده از داده‌کاوی است.
در واقع داده کاوی به بهره گیری از ابزارهای تجزیه و تحلیل داده‌ها به منظور کشف الگوها و روابط معتبری که تا کنون ناشناخته بوده‌اند اطلاق می‌شود. این ابزارها ممکن است مدل‌های آماری، الگوریتم‌های ریاضی و روش‌های یاد گیرنده (Machine Laming Method) باشند که کار این خود را به صورت خودکار و بر اساس تجربه‌ای که از طریق شبکه‌های عصبی (Neural Networks) یا درخت‌های تصمیم گیری (Decision Tree) به دست می‌آورند بهبود می‌بخشد.
داده کاوی منحصر به گردآوری و مدیریت داده‌ها نبوده و تجزیه و تحلیل اطلاعات و پیش بینی را نیز شامل می‌شود برنامه‌های کاربردی که با برسی فایل‌های متن یا چند رسانه‌ای به کاوش داده‌ها می‌پردازند پارامترهای گوناگونی را در نظر می‌گیرد که عبارتند از:
رابطه^[۶۸] : الگوهایی که بر اساس آن یک رویداد به دیگری مربوط می‌شود مثلاً خرید قلم به خرید کاغذ.
ترتیب^[۶۹] : الگویی که به تجزیه و تحلیل توالی رویدادها پرداخته و مشخص می‌کند کدام رویداد رویدادهای دیگری را در پی دارد مثلاً تولد یک نوزاد و خرید پوشک.
دسته بندی^[۷۰] : شناسایی الگوهای جدید و مدل سازی برای شناسایی ارتباطات میان دسته‌ه ای مشخصی از ویژگی‌ها با بقیه ویژگی‌های داده.
خوشه بندی^[۷۱] : کشف و مستند سازی مجموعه‌ای از حقایق ناشناخته مثلاً موقعیت جغرافیایی خرید محصولی با مارک خاص.
پیش بینی^[۷۲] : کشف الگوهایی که بر اساس آن‌ها پیش بینی قابل قبولی از رویدادهای آتی ارائه می‌شود،
از آنجایی که هدف ما از استفاده از داده‌کاوی در این آزمایشات، نشانه گیری گره‌های خطادار است، بهترین استفاده از داده‌کاوی، از طریق دسته بندی عملی خواهد شد. بنا بر این ابتدا یک مرور کلی بر روی تعریف کامل‌تر دسته بندی خواهیم داشت و پس از آن نحوه استفاده از آن را در آزمایشات این پایان نامه بررسی خواهیم نمود.
دسته بندی:
دسته‌بندی در واقع یکی از کاربردهای داده‌کاوی است که به منظور هدف قرار دادن گروهی از کلاس‌ها و یا دسته‌ ها، سایر ویژگی‌ها و دسته‌ ها را با در نظر گرفتن مدل‌های تصمیم گیری و قوانین خاصی، مورد بررسی قرار می‌دهد. هدف نهایی دسته‌بندی در واقع پیش‌بینی دقیق رفتار کلاس هدف، با توجه به هر شکلی از داده‌های ورودی است. برای مثال، با بهره گرفتن از دسته‌بندی می‌توان تشخیص داد که با شرایط در نظر گرفته شده، گرفتن یک وام می‌تواند دارای یک ریسک بالا، متوسط و یا پایین باشد.
در واقع، دسته‌بندی باید با گروهی از کلاس‌ها صورت بگیرد که با کلاس هدف ارتباط داشته باشد. برای مثال اگر برای پیش‌بینی ریسک یک وام جدید از دسته‌بندی استفاده می‌کنیم، باید کلاس‌های دیگر همگی شامل اطلاعات مرتبطی با مسأله بیمه باشند. معمولاً این حجم اطلاعات، در طی زمان و تجارب استفاده کنندگان به دست می‌آیند. البته ممکن است که برخی از این کلاس‌ها در ظاهر با کلاس هدف و با موضوع پیش‌بینی ارتباطی نداشته باشند اما در افزایش دقت پیش‌بینی تأثیر داشته باشند. البته با کمی تحقیق و بررسی همیشه دلایل منطقی پشت این ارتباطات را می‌توان یافت.
از ساده‌ترین مسائل دسته‌بندی می‌توان به دسته‌بندی دودویی اشاره نمود. در این نوع از دسته‌بندی، کلاس هدف تنها شامل دو نوع مقدار است. اگر موضوع این پایان‌نامه را بخواهیم در نظر بگیریم، کلاس هدف ما شامل مقادیر خطادار و بدون خطا می‌باشد. گونه دیگر این کلاس‌ها، کلاس‌های چند مقداری هستند که بیش از دو نوع مقدار را در خود جای می‌دهند.
در مرحله ساخت مدل، الگوریتم دسته‌بندی ارتباط صفات پیش‌بینی کننده را با کلاس هدف به دست می‌آورد. الگوریتم‌های دسته‌بندی مختلف از روش‌های مختلفی برای ساخت مدل استفاده می‌کنند. بعد از این که مدل ساخته شد، می‌توان از آن برای پیش‌بینی وضعیت‌های شناخته نشده جدید استفاده نمود. برای بررسی دقت پیش‌بینی هر کدام از الگوریتم‌های دسته‌بندی، مدل ساخته شده را با گروهی از مقادیر ناشناخته که قبلاً به الگوریتم برای یادگیری داده نشده آزمایش می‌کنیم. بنا بر این، داده‌هایی که برای ساخت و آزمایش یک مدل پیش‌بینی انتخاب می‌شوند، دو دسته هستند:
یک دسته برای آموزش و مدل سازی دسته‌بندی کننده.
یک دسته برای بررسی و تست دسته‌بندی کننده.
برای بررسی نتایج تست دسته بندی از یک سری پارامترها استفاده می‌گردد که پیش از بررسی نتایج آزمایش مورد بحث در این پایان نامه، به توضیح آن می‌پردازیم: