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

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

تحقيق که در بخش ارزيابي ارائه مي‌شود نشان داده است که اين روش بهترين دقت را دارد. در اينجا تابع Average-Linkage نشان‌دهنده الگوريتم پيوندي ميانگين است و همچنين تابع Cluster بر اساس تعداد خوشه تعيين‌شده نتيجه نهايي را از روي دندوگرام تشکيل مي‌دهد.

Function WOCCE (Dataset, Kb, iT, dT, cT) Return [Result, nCrowd]
Initialized nCrowd to zero
While we have base cluster
[idx, Basic-Parameter] = Generate-Basic-Algorithm (Dataset, Kb*cT)
If (Independence (Basic-Parameter) iT) then
If (Diversity (idx) dT) then
Insert idx to Crowd-Partitions
Crowd = Crowd + 1
End if
End if
End while
Co-Acc = Make-Correlation-Matrix (Crowd-Partition)
Z = Average-Linkage (Co-Acc)
Result = Cluster (Z, Kb)
شکل3-4. شبه کد خوشه‌بندي خردمند با استفاده از آستانه‌گيري

جدول 3-1 نشان‌دهنده نگاشت لغات لاتين در ادبيات حوزه خوشه‌بندي ترکيبي به نظريه خرد جمعي مي‌باشد.

جدول3-1. نگاشت لغات لاتين در خوشه‌بندي ترکيبي به نظريه خرد جمعي
WOC Terminology
Cluster Ensemble Terminology
Primary opinion
Primary partition
People
Base algorithm
Wise crowd
Primary clustering results
Diversity of Opinion
Diversity of primary clustering results
Opinion independence
Independence of clustering algorithms that generate primary partitions
Decentralization
Decentralization in cluster generation

3-4. خوشه‌بندي خردمند مبتني بر گراف استقلال الگوريتم
روش پيشنهادي دوم اين تحقيق سعي دارد تا دو بخش از روش اول را بهبود بخشد. اين روش در ابتدا اين ايده را بررسي مي‌کند که الگوريتم‌هاي غير هم نام کاملاً مستقل نيستند. در اين راستاي براي محاسبه درجه استقلال دو الگوريتم با استفاده از ايده تبديل کد به گراف در تست نرم‌افزار به ارائه روشي با عنوان مدل‌سازي گراف استقلال الگوريتم مي‌پردازيم. با مقايسه گراف‌هاي به دست آمده (درجه استقلال) در اين روش مي‌توان يک وزن براي احتمال صحت جواب‌هاي به دست آمده پيشنهاد داد. از اين روي در اين روش به جاي ارزيابي و آستانه‌گيري از استقلال الگوريتم‌ها، آن‌ها را به عنوان وزني براي ترکيب نتايج در نظر مي‌گيريم بدين وسيله نياز به آستانه‌گيري براي استقلال الگوريتم‌ها از بين مي‌رود. جهت ترکيب نتايج اوليه در اين روش رابطه‌اي جديد بر اســاس رابطـه 2-56 با عنوان روش انباشت مدارک وزن‌دار يا به اختصار 169WEAC معرفي مي‌شود.
3-4-1. بررسي مکانيزم حل مسائل توسط الگوريتم‌هاي خوشه‌بندي
در سال‌هاي اخير دسته‌بندي‌هاي زيادي براي الگوريتم‌هاي خوشه‌بندي در کتب‌ و مقالات مختلف ارائه شده است [37, 68, 71, 72, 73]. يکي از ديدگاه‌هاي غالب در اين بحث روشي است که توسط جين و همکاران [37] پيشنهاد شده است. در اين روش، دسته‌بندي الگوريتم‌ها بر اساس تابع هدف170 الگوريتم‌ها صورت مي‌گيرد. شکل 3-5 دسته‌بندي پيشنهادشده توسط جين و همکاران را نشان مي‌دهد.

شکل3-5. دسته‌بندي الگوريتم‌هاي خوشه‌بندي [37].
نتايج تجربي جين و همکاران نشان مي‌دهد که روش عملکرد هر دسته از الگوريتم‌هاي خوشه‌بندي که در يک گروه قرار دارند (داراي تابع ‌هدف مشابه هستند) بر روي يک سري داده‌هاي خاص تقريباً يکسان است [37]. از طرف ديگر، مي‌توان بسياري از الگوريتم‌هاي خوشه‌بندي را يافت که روشي توسعه‌يافته‌ از روي يک الگوريتم پايه مي‌باشند. شايد معروف‌ترين مثال‌هايي که بتوان از اين‌گونه الگوريتم‌ها نام برد الگوريتم‌هاي سري مي‌باشند که جين [74] پنجاه سال تکامل و انواع آن را بررسي کرده است و يا سري الگوريتم‌هاي پيوندي که ما پيش‌تر به چند نمونه از آن اشاره‌کرده‌ايم. در بيشتر اين سري از الگوريتم‌ها فرآيند کلي حل مسئله ثابت است و تنها بخشي از الگوريتم اضافه، تغيير، حذف و يا بهبود داده ‌شده است. از اين روي با توجه به اين رابطه خاص بين برخي از انواع الگوريتم‌ها روش پيشنهادي دوم اين تحقيق فرآيندي را براي مدل‌سازي شيوه کار الگوريتم‌هاي خوشه‌بندي پيشنهاد مي‌دهد تا بر اساس آن استقلال و يا وابستگي الگوريتم‌هاي خوشه‌بندي به نحوي دقيق‌تر از روش پيشنهادي اول، جهت کنترل تأثيرات آن‌ها بر روي توليد نتايج اوليه خوشه‌بندي ترکيبي مورد توجه قرار گيرند.
براي ارزيابي و سنجش درجه استقلال و يا وابستگي الگوريتم‌هاي خوشه‌بندي ابتدا نياز است آن‌ها را مدل‌سازي کنيم. اين مدل‌سازي بايد بر شيوه‌اي استوار باشد که بتوان فقط و فقط عواملي که بر استقلال و يا وابستگي يک الگوريتم تأثير دارند همانند شيوه کار الگوريتم، مولد‌هاي اعداد تصادفي، روابط رياضي، توابع مکاشفه‌اي و غيره را بتوان بدون کمترين تأثيري از ساير بخش‌هاي غير مرتبط همانند کدهاي ورودي، خروجي و نمايش و غيره مدل‌سازي کند. در اين تحقيق بر اساس ايده روش مدل‌سازي کد برنامه به گراف که در تست نرم‌افزار171 استفاده مي‌شود روشي جهت مدل‌سازي فرآيند کار الگوريتم براي ارزيابي استقلال پيشنهاد مي‌شود که ما آن را با عنوان “مدل‌سازي گراف استقلال الگوريتم” مي‌شناسيم. در ادامه به بررسي اين روش خواهيم پرداخت.
3-4-2. مدل‌سازي گراف استقلال الگوريتم
تست نرم افزا يکي از مهم‌ترين بخش‌هاي ساخت نرم‌افزار مي‌باشد که تقريباً شصت درصد از کل هزينه توليد يک نرم‌افزار به آن تخصيص داده مي‌شود. يکي از روش‌هاي تست نرم افزا مدل‌سازي نرم‌افزار مي‌باشد که به چهار بخش مدل‌هاي مبتني بر نَحو172 کد برنامه، فضاي ورودي، منطق عملکرد و گراف تقسيم مي‌شود. از بين اين روش‌ها، مدل‌سازي مبتني بر گراف مي‌تواند يک ديدگاه نمايش گرافيکي از روي کد منبع، طراحي، مشخصات يا مورد‌هاي استفاده173 ارائه دهد از اين روي اين روش براي بررسي مکانيزم کار يک الگوريتم بسيار مفيد مي‌باشد [75]. در اين تحقيق ما از مفاهيم و ايده مدل‌سازي مبتني بر گراف در تست نرم‌افزار جهت محاسبه درجه استقلال الگوريتم‌هاي خوشه‌بندي استفاده مي‌کنيم. قبل از اينکه به تشريح روش ساخت گراف استقلال بپردازيم بايد به دو سؤال در ساخت اين گراف کمي دقيق‌تر پاسخ داد.
اول، گراف استقلال بايد بر اساس چه منبعي ساخته شود؟
براي پاسخ به اين سؤال بايد يادآور شد که گراف استقلال فرآيند روش حل مسئله در الگوريتم خوشه‌بندي را مدل‌سازي مي‌کند ليکن بايد آن را از روي کد و يا شبه کد پياده‌سازي الگوريتم ساخت تا بتوان رابطه‌ي بين اين کدها را شناسايي کرد و از روي آن‌ها استقلال الگوريتم را ارزيابي کنيم.
دوم، آيا کل کد‌هاي پياده‌سازي يک الگوريتم خوشه‌بندي بايد در مدل‌سازي بکار رود؟
همان طور که پيش‌تر نيز اشاره شد هر الگوريتم شامل بخش‌هايي براي تهيه‌ي ورودي، خروجي و نمايش داده به کاربر مي‌باشد. علاوه بر آن هميشه کد‌هاي الگوريتم شامل بخش‌هايي براي تعريف متغيرها، ثابت‌ها‌ و غيره هستند که در بيشتر مواقع فايده‌اي براي ارزيابي درجه استقلال ندارند. اين موارد در شبه کدها کمتر به چشم مي‌خورند ولي با اين حال هميشه وجود دارند. از آنجايي که روش پيشنهادي اين تحقيق به اين تعاريف حساس مي‌باشد. از اين روي در اين تحقيق روشي براي هرس کردن کد و تبديل آن به قالبي مناسب تشخيص استقلال با عنوان “زبان استقلال الگوريتم‌ خوشه‌بندي174” يا به اختصار پيشنهاد خواهيم کرد.
3-4-2-1. زبان استقلال الگوريتم‌ خوشه‌بندي
در زبان استقلال الگوريتم‌ خوشه‌بندي به جاي استفاده از کد يا شبه کد الگوريتم‌ها از نماد‌هايي توافقي استفاده ‌مي‌شود. مهمترين دلايل اين کار را مي‌توان موارد ذيل دانست. اولا، از آن جايي که معمولاً کد‌ها و يا شبه کدها به زبان استانداردي نوشته نمي‌شوند لذا براي مقايسه بايد تمامي آن‌ها را به يک شکل همگن کرد. علاوه بر آن چون در بسياري از موارد معادلات رياضي و شبه کدها در مقالات واضح بيان نمي‌شوند اگر قرار باشد بر اساس آن‌ها به مدل‌سازي يک الگوريتم بپردازيم بايد به شيوه‌اي عمل کنيم تا حساسيت به جزئيات پياده‌سازي کم شود. در اين تحقيق پس از طي يک سري فرآيند استاندارد تمامي کدها به کدي استاندارد براي ارزيابي استقلال تبديل مي‌شود. اين فرآيند به شرح زير است:
1- ابتدا تمامي کد‌هاي اضافي از جمله تعريف متغيرها و ثابت‌ها، توضيحات اضافي، دستورات مربوط به ورودي، خروجي و نمايش اطلاعات، تمامي دستورات مربوط به کنترل حلقه‌ها و شروط در صورتي که تغييري در شرايط اجراي الگوريتم ايجاد نکنند و ساير کد‌هايي که در فرآيند خوشه‌بندي داده نقشي ندارند را حذف مي‌کنيم. براي مثال در صورتي که پياده‌سازي تابعي خاص که در کد اصلي از آن استفاده شده است همانند معيار‌هاي ارزيابي همچون NMI و يا APMM و غيره در کد اصلي وجود داشته باشد پياده‌سازي آن را حذف مي‌کنيم چون در نماد گزاري به راحتي مي‌توان کل آن را با يک نماد توافقي نشان داد.
2- چون بخش منطقي عملگر‌هاي شرطي و حلقه‌ها تأثيري در شکل گراف نمي‌گذارند آن‌ها را حذف مي‌کنيم.
3- با حذف بخش منطقي عملگر‌هاي شرطي و حلقه‌ها استفاده از انواع عملگر شرطي‌ (همانند If، elsif، case و غيره) و همچنين به‌کارگيري انواع عملگر حلقه (همانند حلقه‌هاي for، while و غيره) نياز نيست. قابل به ذکر است که کليه اين دستورات براي تسريع سرعت پياده‌سازي کد الگوريتم توسط برنامه‌نويس به کار مي‌روند ولي در نهايت همگي آن‌ها جزئي از دو گروه عملگر‌هاي شرطي و حلقه‌ها مي‌باشند. چون در مدل‌سازي الگوريتم فرآيند کار الگوريتم مدل‌ مي‌شود و نه نحوه پياده‌سازي تک‌تک کدها، از اين روي دستور بکار رفته در کد اهميتي ندارند بلکه فقط و فقط ماهيت آن‌ها مهم مي‌‌باشد. در نتيجه اين تحقيق پيشنهاد مي‌کند براي سادگي مدل تنها از يک دستور قراردادي به عنوان عملگر شرط و يک دستور قراردادي براي عملگر حلقه استفاده کنيم. اين تحقيق براي هر نوع شرطي از نماد‌هاي If Else End و براي هر نوع حلقه‌اي‌ از نماد‌هاي While Break End استفاده مي‌کند.
4- به منظور سادگي و همگن کردن کد‌ها و همچنين تسريع در عمل مقايسه و ارزيابي آن‌ها در اين تحقيق از جدولي قراردادي براي تبديل کد‌هاي اصلي به کد‌هاي استاندارد استفاده مي‌شود. اين جدول که ما آن را با عنوان “جدول نگاشت استاندارد کد175” و يا مي‌شناسيم مي‌تواند با حفظ قالب اصلي خود متناسب باهر پياده‌سازي‌ تهيه شود. در ادامه چند قانون قراردادي را براي توليد اين جدول بيان مي‌کنيم.
5- جهت وضوح بيشتر کد تهيه‌شده ابتداي آن با کلمه Begin و انتهاي آن با کلمه End معين مي‌شود.
به منظور سهولت در انتخاب نماد در جدول نگاشت استاندارد کد، پيشنهاد مي‌شود تا دستورات ابتدا گروه‌بندي شده و براي هر دستور در گروه منحصربه‌فرد آن يک برچسب عددي در نظر گرفته شود. در اينجا گروه‌ها با حروف انگليسي و برچسب‌ها در مقابل آَن داخل پرانتز نوشته خواهد شد. اين گروه‌بندي و برچسب‌گذاري مي‌تواند به هر صورت دلخواهي انجام شود ولي حتماً بايد براي حل يک مسئله خاص برچسب‌گذاري و گروه‌بندي تمامي الگوريتم‌ها يکتا باشند. براي مثال مي‌توان گروه مولد اعداد تصادفي را با R، گروه روابط رياضي را با M، روابط مکاشفه‌اي را با H و گروه تخصيص برچسب خوشه به داده‌ را با G نشان داد. در جدول 3-2 مثالي از يک نمونه بسيار ساده از جدول نگاشت استاندارد کد به تصوير کشيده شده است.
جدول3-2. يک نمونه از جدول نگاشت استاندارد کد
کد برنامه
نماد
Y= RandomNumber()
R(0)
Y = RandomNumbers(k)
R(1)
Y = Sin(X)
M(1)
Z = EuclideanDistance(X, Y)
M(2)
Z = ManhatanDistance(X,Y)
M(3)
Z = NMI(A,B)
H(1)
Z = A3(A,B)
H(2)
Assign data point to cluster with nearest center
G(1)
Connect data point to nested with max center
G(2)
بر اساس برخي از نماد‌هاي جدول 3-2 و شبه کد شکل 2-10 براي الگوريتم کدي با قالب استاندارد زبان استقلال الگوريتم‌ خوشه‌بندي در شکل 3-6 به تصوير کشيده شده است.
Begin
R(2)
While

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