منابع و ماخذ پایان نامه عدم تمرکز

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

G(1)
M(2)
End
End
شکل3-6. کد الگوريتم K-means به زبان استقلال الگوريتم‌ خوشه‌بندي
همان طور که مشاهده مي‌کنيد کد شکل 3-6 فاقد هر گونه جزئيات اضافي و غير مرتبط مي‌باشد و به خوبي فرآيند اجراي الگوريتم به همراه دستورات موثر در استقلال آن را به بيان مي‌کند. علاوه بر آن، با توجه به جدول 3-2 مي‌توان گفت که يکي ديگر از ويژگي‌هاي مهم جدول نگاشت استاندارد کد اين است که در تهيه اين جدول مي‌توان همزمان از بخشي از کد برنامه يک الگوريتم و شبه کد الگوريتمي ديگر در کنار يکديگر استفاده کرد بدون آن که در همگن بودن کد نهايي مشکلي پيش آيد. در بخش “مدل‌سازي الگوريتم‌ها به زبان استقلال الگوريتم‌” جدول نگاشت استاندارد کد استفاده‌شده جهت مدل‌سازي الگوريتم‌هاي اين تحقيق و کد‌هاي مدل‌سازي شده آن الگوريتم‌ها به قالب استاندارد زبان استقلال الگوريتم‌ خوشه‌بندي ارائه مي‌شود.
3-4-2-2. تبديل کد به گراف استقلال الگوريتم
جهت ساخت گراف استقلال الگوريتم از روي کدي با قالب استاندارد زبان استقلال الگوريتم از روش تبديل ‌کد به گراف در مباحث‌ تست نرم‌افزار [75] استفاده مي‌کنيم. چون کاربرد گراف استقلال خاص منظوره است و کد تهيه‌شده نيز داراي يک قالب استاندارد مي‌باشد از اين روي روش ساخت گراف مطرح‌شده در اين تحقيق کاملاً مشابه روش‌هاي ساخت گراف در تست نرم‌افزار نيست بلکه روشي سفارشي شده بر اساس ايده تبديل کد به گراف متناسب با نياز‌هاي ارزيابي استقلال الگوريتم مي‌باشد. در اين روش، اتصالات176 کد (که مطابق با تعاريف بخش قبل شامل نقاط شروع، پايان، شرط و حلقه و بخش‌هاي زيرمجموعه‌ي آن‌ها مي‌باشند) را طوري در نظرخواهيم گرفت که هر کدام مطابق با فرآيند کارشان به چند نود و يال‌هاي ميان آن‌ها تقسيم شوند. در اين روش براي نشان دادن روند اجراي برنامه از گراف جهت‌دار همانند روش تست نرم‌افزار استفاده خواهيم کرد. از طرف ديگر، در روش تست نرم‌افزار کد ميان اتصالات در بخش گره‌ها نشان داده مي‌شوند و روي يال‌ها غالباً بخش منطقي عملگر‌هاي شرطي و يا حلقه‌ نوشته مي‌شود ولي به خاطر اين که اولاً ما بخش منطقي عملگر‌ها را حذف کرده‌ايم ثانياً در اين ارزيابي روند اجراي کد مهم است و ثالثاً کد‌ها به شکل هرس شده و با نماد‌هاي استاندارد پياده‌سازي شده‌اند، پس براي سادگي و وضوح بيشتر کد به جاي نوشتن کد‌ها در داخل گره‌ها آن‌ها را روي يال‌هاي ما قبل گره که دقيقاً جريان همان کد را نشان مي‌دهد نوشته و به عنوان وزن (غير عددي) آن يال در نظرخواهيم گرفت. روش نوشتن هر بخش از اين کد‌ها به عنوان وزن در گراف بايد با همان ترتيبي که در کد اصلي نوشته شده است باشد. بديهي است که به سادگي مي‌توان شکل و نماد‌هاي گراف‌هاي تهيه‌شده براي دو الگوريتم را باهم مقايسه کرد و ميزان شباهت و يا تفاوت اين گراف‌ها نشان‌دهنده روش عملکرد آن‌ها (روش حل مسئله) مي‌باشد. با مقايسه نمودن اين گراف‌ها مي‌توان ميزان استقلال الگوريتم‌هاي خوشه‌بندي را ارزيابي کرد. در ادامه ابتدا روش تبديل هر اتصال در کد را به گراف و حالت‌هاي خاص به وجود آمده را بررسي مي‌کنيم و سپس چند مثال پرکاربرد را براي تبديل کد به گراف نشان مي‌دهيم.
گراف بخش شروع و پايان شکل 3-7 روش تبديل کد‌هاي شروع و پايان به گراف را نشان مي‌دهد. در اين شکل دايره‌ها، گره‌هاي گراف مي‌باشند و شکل مربع شامل تمامي گره‌ها و يال‌هايي است که از روي کد نوشته‌شده بين دو کلمه کليدي به گراف تبديل شده است.

شکل3-7. تبديل کد‌هاي شروع و پايان به گراف

گراف عملگر شرط شکل 3-8 نشان‌دهنده تبديل ساده‌ترين نوع عملگر شرطي به گراف مي‌باشد.

شکل3-8. تبديل عملگر شرط ساده به گراف

شکل 3-9 نمايش گراف معروف‌ترين نوع عملگر شرط مي‌باشد که ما آن را با عنوان عملگر شرط کامل مي‌شناسيم.

شکل3-9. تبديل عملگر شرط کامل به گراف
شکل 3-10 را با عنوان گراف عملگر شرط تو در تو مي‌شناسيم که پياده‌سازي کدهاي چند شرطي و يا Switch Case به گراف پس از تبديل به زبان استقلال الگوريتم مي‌باشد.

شکل3-10. تبديل عملگر شرط تو در تو به گراف
گراف عملگر حلقه شکل 3-11 نشان‌دهنده تبديل ساده‌ترين نوع عملگر حلقه به گراف مي‌باشد.

شکل3-11. تبديل عملگر حلقه ساده به گراف
شکل 3-12 نشان‌دهنده تبديل عملگر حلقه با پرش به گراف مي‌باشد.

شکل3-12. تبديل عملگر حلقه با پرش به گراف

در ادامه به ذکر چند مثال پرکاربرد از کد‌هاي تبديل‌شده به گراف مي‌پردازيم. همان طور که در کد‌ اين مثال‌ها نمايش داده شده است براي وضوح بيشتر مثال‌ها به جاي استفاده از نمادهاي جدول نگاشت از حرف که به ترتيب شماره‌گذاري شده است استفاده مي‌شود. بديهي است که نماد‌هاي به‌کاررفته در کد واقعي استقلال الگوريتم جايگزين اينها خواهد شد. شکل 3-13 الي 3-22 مثال‌هايي از کد‌هاي پرکاربرد مطابق با قالب استاندارد کد استقلال الگوريتم مي‌باشد.

شکل3-13. پياده‌سازي شرط ساده بدون هيچ کد اضافي

شکل3-14. پياده‌سازي شرط ساده با کدهاي قبل و بعد آن

شکل3-15. پياده‌سازي شرط کامل

شکل3-16. پياده‌سازي شرط‌ تو در تو

شکل3-17. پياده‌سازي يک شرط کامل در يک شرط ساده

شکل3-18. پياده‌سازي يک شرط کامل در يک شرط کامل ديگر

شکل3-19. پياده‌سازي حلقه ساده

شکل3-20. پياده‌سازي يک حلقه ساده داخل حلقه‌اي ديگر

شکل3-21. پياده‌سازي يک حلقه داخل يک شرط کامل

شکل3-22. پياده‌سازي يک شرط کامل داخل يک حلقه ساده
در ادامه به بررسي روش ارزيابي گراف استقلال براي محاسبه درجه استقلال دو الگوريتم مي‌پردازيم.
3-4-۲-۳. ارزيابي گراف استقلال الگوريتم
ابتدا براي ارزيابي درجه استقلال دو الگوريتم به معرفي روشي جهت ذخيره‌سازي گراف آن مي‌پردازيم. همان‌گونه که در مثال‌هاي ذکرشده مشاهده مي‌شود هميشه يال‌هايي بدون وزن در گراف وجود دارند که صرفاً براي نمايش عملکرد کامل گراف به‌کاربرده مي‌شوند و در امر ارزيابي نياز به ذخيره آن‌ها نيست لذا براي ذخيره گراف در حافظه از ذخيره‌سازي آن‌ها صرف‌نظر خواهيم کرد تا هم حجم حافظه بهينه استفاده شود و هم سرعت اجراي مقايسه افزايش يابد. در اين تحقيق براي ذخيره هر گراف در حافظه از آرايه‌اي به اندازه تمامي يال‌هاي وزن‌دار آن استفاده مي‌شود که وزن هر يال (که مي‌تواند شامل چندين خط از نماد‌هاي جدول نگاشت استاندارد باشد) در يک خانه منحصربه‌فرد ذخيره مي‌شود. براي ارزيابي گراف استقلال دو الگوريتم کافي است آرايه‌هاي آن دو الگوريتم را باهم مقايسه کنيم. جهت ارزيابي آرايه‌هاي دو الگوريتم، ماتريسي با عنوان ماتريس درجه وابستگي‌ کد177 يا CDDM را همانند شکل 3-23 طوري فرض مي‌کنيم که هر خانه آن مقايسه‌اي از وزن‌ يال‌هاي گراف الگوريتم اول باهر کدام از وزن‌ يال‌هاي گراف الگوريتم دوم باشد.

شکل3-23. ماتريس درجه وابستگي‌ کد
در شکل 3-23 متغير n تعداد خانه‌هاي آرايه الگوريتم اول و متغير m تعداد خانه‌هاي آرايه الگوريتم دوم مي‌باشد. مقادير خانه‌هاي ماتريس بر اساس رابطه 3-7 محاسبه مي‌شود.
(3-7)
در رابطه 3-7 متغيرهاي i و j شماره سطر و ستون ماتريس شکل 3-23 مي‌باشند و تابع بر اساس شبه کد 3-24 محتواي دو خانه از آرايه‌ها را باهم مقايسه مي‌کند.
Function Compare (Cell1, Cell2) Return [CDD]
Count = 0
While we have Symbol in Cell1
Sym1 = Select an Symbol in Cell1
Foreach Sym2 in Cell2
If Sym2 = Sym1 is found then
Count++
Break
End If
End Foreach
End while
MSymbol = Max-Sym (Cell1, Cell2)
Result = Count / MSymbol
شکل3-24. شبه کد مقايسه محتواي دو خانه از آرايه‌هاي استقلال الگوريتم
در شکل 3-24 به ازاي هر نماد در هر خانه از آرايه اول به دنبال اولين نماد عيناً مشابه در خانه‌ي آرايه دوم مي‌گردد و تعداد نماد‌هاي مشابه را مي‌شمارد. در نهايت جهت نرمال سازي درجه استقلال بين صفر و يک تعداد نماد‌هاي مشابه را بر مقدار بيشينه تعداد نماد‌هاي موجود بين خانه اول و دوم تقسيم مي‌کند. همان طور که در تعريف شکل 3-24 نشان داده شده است مقدار به دست آمده از تابع را با عنوان درجه وابستگي هر خانه178 يا همان CDD مي‌شناسيم.
جهت به دست آوردن مقدار استقلال الگوريتم بر اساس ماتريس وابستگي، فرض مي‌کنيم که ماتريس فعلي ماتريس مرحله اول يا همان نام دارد. در اين ماتريس خانه‌اي را پيداکرده که بيش‌ترين مقدار را دارد که ما مقدار آن را به متغير تخصيص مي‌دهيم. با حذف سطر و ستوني که خانه بيشينه در آن قرار دارد ماتريس را مي‌سازيم و به طريق مشابه خانه‌اي که در آن بيش‌ترين مقدار وجود دارد در نگهداري کرده و سطر و ستون خانه بيشينه را حذف مي‌کنيم تا ماتريس مرحله بعد ساخته شود. اين کار را به تعداد n بار مي‌توان انجام داد که n حداقل تعداد خانه‌هاي دورآرايه‌ي الگوريتم اول و دوم مي‌باشد. بر اساس تعريف بالا درجه استقلال الگوريتم مطابق با رابطه 3-8 محاسبه مي‌شود.
(3-8)
در رابطه 3-8 نمادهاي Alg1 و Alg2 به ترتيب نشان دهند آرايه‌هاي الگوريتم اول و دوم مي‌باشد و متغير m حداکثر تعداد بين خانه‌هاي آرايه‌هاي الگوريتم اول و دوم است. طبق اين رابطه درجه استقلال دو الگوريتم برابر تفاضل يک از ميانگين خانه‌هاي بيشينه در ماتريس‌هاي درجه وابستگي کد در مراحل بالا است که جهت نرمال سازي بين صفر و يک بر m تقسيم شده است. از اين پس درجه استقلال الگوريتم179 را با عنوان AID مي‌شناسيم.

3-4-3. چهارچوب خوشه‌بندي خردمند مبتني بر گراف استقلال الگوريتم

شکل3-25. چهارچوب خوشه‌بندي خردمند مبتني بر گراف استقلال الگوريتم
همان طور که پيش‌تر به آن اشاره شد در روش پيشنهادي دوم اين مقاله استقلال الگوريتم به عنوان وزني براي ترکيب نتايج نهايي استفاده خواهد شد لذا در شکل 3-25 بخش ارزيابي استقلال حذف‌شده و پس از ارزيابي پراکندگي هر الگوريتم آن را در مجمع خردمند ذخيره مي‌کنيم. در اصل اينجا مجمع خردمند شامل نتايج ارزيابي‌شده (نسبت به پراکندگي) به همراه درجه استقلال آن نتايج (احتمال درستي آن‌ها نسبت به هم) به عنوان وزن جهت ترکيب مي‌باشند. همان‌گونه که در شکل نشان داده شده است اين چهارچوب نيز غيرمتمرکز بوده و تمامي قوانيني که در بخش عدم تمرکز و ارزيابي پراکندگي در روش اول به آن اشاره شد در اينجا نيز صدق خواهد کرد. از اين روي در اين بخش تنها به تشريح روش ارزيابي استقلال بر اساس روش مبتني بر گراف و همچنين روش ترکيب نتايج جمع‌آوري شده در مجمع خردمند به صورت وزن‌دار بسنده مي‌کنيم.
3-4-3-1. ارزيابي استقلال الگوريتم
مطابق شکل 3-25 نتايج ارزيابي درجه استقلال الگوريتم‌ها در ماتريس AIDM نگهداري مي‌شود. اندازه اين ماتريس است که n تعداد الگوريتم‌هايي هستند که قرار است در خوشه‌بندي شرکت کنند. روش محاسبه سطر و ستون اين ماتريس طبق رابطه 3-9 محاسبه مي‌شود:
(3-9)

رابطه 3-9 توضيح مي‌دهد که اگر دو الگوريتم غير هم نام باشد مطابق با رابطه 3-8 درجه استقلال آن‌ها محاسبه مي‌شود، و اگر دو الگوريتم هم نام باشد چون بايد همانند روش اول با در نظر گرفتن پارامترهاي اساسي آن دو الگوريتم مطابق شبه کد شکل 3-2 به محاسبه درجه استقلال ‌بپردازيم درجه استقلال آن را در اين ماتريس منفي يک در نظر مي‌گيريم تا پس از توليد پارامترهاي اساسي حين اجراي الگوريتم به محاسبه آن بپردازيم. در اين حالت استقلال الگوريتم هم در سطح عملکرد الگوريتم و هم در سطح پارامتر‌هاي اساسي الگوريتم در نظر گرفته مي‌شود. در شکل 3-25 پس از اتمام کار انتخاب خوشه‌ها و تشکيل جامعه خردمند، درجه استقلال نهايي براي هر الگوريتم خوشه‌بندي برابر با ميانگين مجموع درجه‌هاي استقلال آن الگوريتم نسبت به الگوريتم‌هاي غير هم نام و پارامتر‌هاي اساسي الگوريتم‌هاي هم نام مي‌باشد. رابطه 3-10 روش محاسبه

پایان نامه
Previous Entries منابع و ماخذ پایان نامه الگوريتم، خوشه‌بندي، مدل‌سازي Next Entries منابع و ماخذ پایان نامه عدم تمرکز