در سازمان‌ها و سامانه‌های بزرگ مقیاس و پیچیده، جهت تعیین نیازمندی‌های عملیاتی و غیر عملیاتی در گستره‌ای که ممکن است هزاران ذینفع را در بر گیرد، دانشی جهت استخراج نیازمندی‌ها احساس می‌گردد. با توجه به اینکه سازمان‌ها، داده‌ها و اطلاعات بسیاری در تصرف خود دارند و با فلج ساختن اطلاعات یک چالش کلیدی در تصمیم گیری تشکیلات سازمانی ایجاد می‌نمایند، فرایند کشف دانش از پایگاه داده سازمان مطرح گردیده که یک فرایند علمی برای شناسایی الگوهای معتبر، بالقوه مفید و قابل فهم از داده‌ها می‌باشد.در این تحقیق قصد داریم با بکار گیری داده کاوی به عنوان مرحله‌ای از فرایند کشف دانش به ارائه‌ چارچوبی جهت استخراج و اولویت بندی نیازمندی‌ها در سازمان‌های بزرگ مقیاس پرداخته که در نتیجه کار خود، افزایش رضایتمندی را به همراه می‌آورد. بدین صورت که ابتدا با توجه به فرکانس تکرار و درجه اهمیت، نیازمندی‌ها را با بهره گرفتن از الگوریتم K-Means خوشه بندی کرده سپس با روشی به نام رتبه بندی و بهره گیری از ماتریس ارزش محور به اولویت بندی نیازمندی‌ها می‌پردازیم. مطالعه موردی چارچوب پیشنهادی، پایگاه داده سامانه مدیریت شهری 137 شهرداری تهران می‌باشد.بر اساس نتایج بدست آمده می‌توان خوشه‌های متفاوت از نیازها با اولویت اقدام متفاوت را معرفی نمود.

 

کلمات کلیدی: مهندسی نیازمندی‌ها، استخراج نیازمندی‌ها،سازمان‌ها و یا سامانه‌های بزرگ مقیاس،داده کاوی، اولویت بندی نیازها، رضایتمندی

 

 

 

فهرست مطالب

 

فصل اول (مقدمه و کلیات تحقیق). 2

1-1 مقدمه. 2

1-2 مهندسی نیازمندی‌ها. 2

1-3 استخراج نیازمندی‌ها. 3

1-4  سازمان‌های بزرگ مقیاس. 4

1-5 ویژگی‌های سازمان‌ها و سامانه‌های بزرگ مقیاس. 5

1-6 چالش‌های سازمان‌های بزرگ مقیاس. 8

1-7 انگیزه. 8

1-8 تعریف مسئله. 9

1-9 فرضیه. 9

1-10 اهداف تحقیق. 10

فصل دوم (ادبیات و پیشینه تحقیق). 12

2-1 مقدمه. 12

2-2 انگیزه‌های کاوش داده. 13

2-2-1 انگیزه‌های تجاری. 13

2-2-2 انگیزه‌های علمی. 15

2-3 چالش‌های داده کاوی. 16

2-3-1 چالش‌های اولیه. 17

2-3-2 چالش‌های ثانویه. 18

بر کشف دانش و داده کاوی. 19

2-5 مراحل داده کاوی. 21

2-6 دلایل وجود و ضرورت داده کاوی. 29

 

2-7 داده کاوی سازمانی. 30

2-8 نقش داده کاوی سازمانی در معرفت سازمانی. 31

2-9 معیارهای تعریف نیازمندی‌های سیستم. 31

2-10 نتایج نیازمندی‌های نادرست. 32

2-11 پیشینه تحقیق. 32

2-11-1 روش‌های سنتی. 33

2-11-1-1 مقایسه روش‌های سنتی. 35

2-11-2 استفاده از ابزارها. 37

2-11-3 روش‌های نوین. 38

2-11-3-1 مقایسه روش‌های نوین. 46

2-12 تکنیک‌هایی در افزایش سطح بهبود رضایت ذینفعان در فاز استخراج نیازمندی‌ها  47

2-13 نتیجه گیری. 49

فصل سوم (روش تحقیق). 53

3-1 مقدمه. 53

3-2 راهکار پیشنهادی. 53

3-2-1 آماده سازی و پیش پردازش داده. 54

3-2-1-1 جمع آوری و بارگذاری داده‌های استخراج شده. 54

3-2-1-2 پاک سازی داده. 54

3-2-1-3 انتخاب زیر مجموعه‌ای از ویژگی‌ها. 55

3-2-1-4 فیلترینگ نمونه‌ها. 55

3-2-1-5 تبدیل داده. 55

3-2-1-6 خلق ویژگی. 55

3-2-1-7 نمونه برداری. 56

3-2-2 یادگیری مدل. 56

3-2-2-1 خوشه بندی. 56

3-2-2-2 خوشه بندی K-Means. 56

3-2-2-3 خوشه بندی با بهره گرفتن از الگوریتم K-Means با توجه به فرکانس تکرار و درجه اهمیت درخواست‌ها و نیازمندی‌ها. 57

3-2-3 ارزیابی و تفسیر مدل. 58

3-2-4 دسته بندی جدید و اولویت بندی نیازمندی‌های استخراج شده با بهره گرفتن از تکنیک رتبه بندی. 58

3-2-4-1 روش رتبه بندی. 60

3-2-4-2 شاخص‌های رتبه بندی. 60

3-2-4-3 ضرایب یا وزن شاخص‌ها. 61

فصل چهارم (محاسبات و یافته‌های تحقیق). 65

4-1 مطالعه موردی: سامانه مدیریت شهری 137 شهرداری تهران. 65

4-2 معرفی ابزار برتر داده کاوی RapidMiner 66

4-3 پیاده سازی روش پیشنهادی. 68

4-4 ارزیابی و تفسیر خوشه‌ها. 69

فصل پنجم (نتیجه گیری و پیشنهادات). 72

5-1 نتیجه گیری. 72

5-2 مشکلات و نقاط ضعف کارهای مرتبط. 72

5-3 مزایا و ویژگی‌های روش پیشنهادی. 73

5-4 کارهای آینده. 74

پیوست – منابع و مآخذ. 75

Abstract 76

فهرست جداول

جدول2-1: مقایسه روش‌های سنتی استخراج نیازمندی‌ها…………….. 36

جدول2-2: مسائلی در ارتباط با نیازمندی‌های تطبیق شده…………. 47

جدول3-1: معیارهای SSEو ASC……………………………….. 57

جدول3-2: بررسی برخی روش‌های اولویت بندی……………………. 59

جدول3-3: تعیین ضریب شاخص (درجه اهمیت)…………………….. 62

جدول3-4: تعیین درجه اهمیت نیازمندی……………………….. 62

جدول3-5: تعیین ضریب شاخص………………………………… 63

جدول4-1: جدول پیام……………………………………… 65

جدول4-2: نتیجه خوشه بندی و اولویت بندی نیازمندی‌ها………….. 69

فهرست شکل‌ها

شکل2-1: فرایند داده کاوی و کشف دانش………………………. 20

شکل2-2: استفاده از داده کاوی در استخراج نیازمندی‌ها…………. 40

شکل2-3: شبکه اجتماعی……………………………………. 43

شکل2-4: روش مبتنی بر سناریو……………………………… 44

شکل2-5: مدل تکرار پذیر استخراج نیازمندی‌های جامع……………. 46

شکل3-1: مراحل اصلی راهکار پیشنهادی……………………….. 53

شکل3-2: گام‌های مرحله آماده سازی و پیش پردازش داده………….. 54

شکل3-3: تعیین اولویت……………………………………. 61

چكیده

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

كلمات كلیدی: اشتراک پذیری، شرکت گاز، فناوری اطلاعات، فروش الکترونیکی، مهندسی مجدد

 

 

 

د

فهرست

عنوان                                                                                                           صفحه

فصل اول : مقدمه                                                                                            2

1-1 بر قوانین بکارگیری خدمات الکترونیک در سازمان‌ها                      4

1-2 لزوم بکار گیری فناوری اطلاعات در شرکت گاز                                    5

 

فصل دوم: پیشینه تحقیق و استخراج ویژگی ها                                    10

2-1 بررسی نمونه کارهای مرتبط در ایران                                                         11

2-2 بررسی چند نمونه در شرکت های گاز در کشور‌های دیگر                         15

2-2-1 شرکت گاز کالیفرنیای آمریکا                                                      16

2-2-2 شرکت گاز استرالیا                                                                 17

2-2-3 شرکت گاز انگلستان                                                               18

 

فصل سوم: نکات طراحی وب سایت                                                    21

 

فصل چهارم: مفاهیم پیاده سازی فناوری اطلاعات                                  31

4-1 مدل تجاری G2C- خدمات دولت به مشتری منفرد                               32

4-2 مهندسی مجدد                                                                        35

4-3 بررسی پیاده سازی فناوری اطلاعات در شرکت گاز                                37

 

فصل پنجم: بررسی روش فعلی و معرفی روشی جدید                              41

5-1 مهندسی مجدد اشتراک پذیری در شرکت گاز                                               42

5-2 اشتراک پذیری                                                                         44

ه

5-2-1 فرایند اشتراک پذیری                                                             49

5-2-2 روش پیشنهادی برای فرایند اشتراک پذیری                                    52

5-2-2-1 دفاتر پیش‌خوان دولت                                                                   53

5-2-2-2 دسترسی به نقشه تایید شده نظام مهندسی و تسویه حساب نفت                   54

5-2-3 روند کار سیستم پیشنهادی                                                       55

5-3 فروش الکترونیکی گاز                                                                 57

 

5-3-1 فرایند فروش الکترونیکی گاز                                                      58

5-3-2 روش پیشنهادی برای فرایندهای فروش گاز                                               60

 

فصل ششم: معرفی ابزار و مشخصات فنی سیستم                                  64

6-1 معماری و تکنولوژی پیشنهادی                                                       64

6-1-1 معماری سرویس گرا                                                               64

6-1-2 تکنولوژی J2EE                                                                                     66

6-2 واسط کاربر                                                                                      67

6-3 ارتباط                                                                                   68

6-3-1 شبکه خصوصی مجازی                                                            68

6-4 پایگاه داده                                                                              69

6-4-1 فضای درخواستی                                                                            70

6-4-2 تکنولوژی RAID                                                                                               71

6-5 تعیین مشخصات سخت افزاری                                                       71

6-5-1 مشخصات سخت افزاری سرور پیشنهادی                                        73

6-5-2 استفاده از مراکز داده‌ها                                                            73

6-6 بررسی قسمت های اصلی نرم‌افزار پیشنهادی                                                74

6-7 نحوه ارتباط موثر با مشتری                                                           83

6-7-1 بررسی فاکتورهای انسانی                                                                   84

و

6-7-2 بررسی راه‌های ارتباط با مشتری                                                  84

فصل هفتم: ارزیابی                                                                        87

7-1 ارزیابی هزینه                                                                          89

7-2 ارزیابی سرعت عمل                                                                             90

7-3 ارزیابی سادگی و راحتی                                                              91

7-4 ارزیابی امنیت و کیفیت                                                               91

7-5 مزایای حاصله از سیستم پیشنهادی                                                 92

 

فصل هشتم: نتیجه گیری و پیشنهادات                                              93

 

منابع                                                                                         95

 

 

فهرست جدول‌ها

 

عنوان                                                                                                              صفحه

جدول شماره 1 – ویژگی‌های یک وب سایت مناسب                                    27

جدول شماره 2 – کد و نام جدول شهرها                                                79

جدول شماره 3 – کد و نوع مصرف                                                       80

جدول شماره 4 – تحلیل SWOT                                                                                    88

 

 

 فهرست شکل‌ها

 

عنوان                                                                                                              صفحه

شکل  شماره 1 – صفحه اول سایت مخابرات                                             12

شکل  شماره 2 – صفحه خدمات سایت مخابرات                                        14

شکل  شماره 3 – صفحه خدمات سایت مخابرات                                        14

شکل  شماره 4 – صفحه ثبت نام اینترنتی تلفن                                         15

شکل  شماره 5 – صفحه پرداخت ثبت نام اینترنتی تلفن                               15

شکل  شماره 6 – صفحه اول سایت شرکت گاز کالیفرنیای آمریکا                      17

شکل  شماره 7 – صفحه اول سایت شرکت گاز استرالیا                                 18

شکل  شماره 8 – صفحه اول سایت شرکت گاز انگلستان                               19

شکل  شماره 9 – روند اشتراک پذیری در شرکت گاز                                   45

شکل  شماره 10 – روند تایید نقشه نظام مهندسی                                               46

شکل  شماره 11 – روند تسویه حساب نفت                                             47

شکل  شماره 12 – نامه تسویه حساب نفت                                              48

شکل  شماره 13 – روش پیشنهادی                                                      56

شکل  شماره 14 – روابط زیر سیستم‌ها                                                  60

شکل  شماره 15 – صفحه اول دموی سیستم پیشنهادی                               76

شکل  شماره 16 – صفحه اشتراک پذیری دموی سیستم پیشنهادی                           77

مقدمه

در دنیای امروز، اطلاعات نه تنها بعنوان یكی از منابع و دارایی های اصلی سازمانها شناخته می شود، بلكه در حكم وسیله و ابزاری برای مدیریت موثر سایر منابع و دارایی‌های سازمان (منابع مالی، نیروی انسانی و غیره) نیز محسوب شده و لذا از اهمیت و ارزش ویژه‌ای در سازمان‌ها برخوردار گشته است. اما این ارزش تنها در صورتی محقق و دست یافتنی خواهد شد كه اطلاعات بتواند در زمان مناسب، در اختیار افراد مناسب قرار گیرد و ارتباطات بصورت مطلوب و بهینه در سازمان برقرار گردد. و از این رو است كه، فناوری اطلاعات كه زمینه سازی برای انتقال، جابجایی، بكارگیری و مدیریت موثر اطلاعات در سازمان می‌باشد از اهمیتی حیاتی برخوردار گشته است (Al-Kibsi، 2007).

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

 

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

1. رشد فناوری‌های جدید و به ویژه فناوری اطلاعات: امروزه، فناوری با نرخ فزاینده و به صورت تصاعدی درحال رشد است.
2. رشد اینترنت و فراگیری عمومی استفاده از آن
3. تغییر انتظارات شهروندان و بنگاه‌های اقتصادی: انتظارات مردم درمورد خدمات، محصولات و نیز نحوه و كیفیت ارائه آن به طور روزافزون درحال تغییر است و سازمان‌های دولتی نیز باید بتوانند پاسخگوی این نیازها باشند.

 

 

چکیده

درحال حاضر معماری سازمانی یكی ازعوامل مهم و كلیدی درانجام ماموریت های سازمان ها  محسوب می شود هدف معماری سازمانی این است كه فناوری اطلاعات را از حالت یک ابزار خارج كرده و به یكی از منابع سازمان در كنار سایر منابع تبدیل نماید، بطوری كه در خدمت مامو ریت های سازمان باشد . در حال حاضرسازمان های مختلف به ویژه سازمان های پرتلاطم برای اجرای فرایند معماری سازمانی وبه خصوص برنامه ریزی معماری سازمانی دچارمشكلاتی هستند. فرایند برنامه ریزی و اجرای معماری سازمانی بسیار لخت، كند و فرسایشی بوده ودر نتیجه یا به درس تی اجرا نشده و یا به شكست منجر می شود . این مشكل ناشی از وجود تغییرات زیاد و گسترده و پیچیدگی در كسب و كار سازمان‌هاست. برای حل این مشكل راه حل های مختلفی ارائه شده است . هنگامی كه در مساله ای آشفتگی و تلاطم وجود داشته باشد چابكی یكی از كلید های حل مساله است. چابكی به توانایی برای ایجاد و پاسخگویی به تغییرات محیط متلاطم كسب و كار گفته می شود . چابكی به مفهوم تندی، سرعت، سبكی و زیركی بوده و به خلاقیت، ابتكار و نوآوری نیاز دارد .متدولوژی ها و روش های چابك تطبیق پذیر هستند و خودشان را با تغییرات تطبیق می دهند. معماری سازمانی چابك دارای روش ها و راه حل های مختلفی برای برنامه ریزی و مدلسازی است. در این تحقیق سعی بر این است تا چارچوب C4ISR را با کمک متدولوژی چابک و تجارب عملی چابك ، چابک سازی نماییم .با بكارگیری تجارب عملی چابك مدل های چارچوب كم حجم تر و سریع تر تدوین گردیده و امكان پاسخگویی به تغییرات گسترده كسب و كار سازمانی فراهم می آید.مممممممممممم[1-14]

كلید واژه- چابكی، معماری سازمانی چابك، روش های چابك، مدلسازی چابك، چارچوب چابك، فرایند چابك ، چارچوب C4ISR

 

 

 

فهرست مطالب

1-  فصل اول: کلیات تحقیق    1

1-1- مقدمه    2

1-2- تعریف مساله. 3

1-3- اهداف تحقیق.. 4

1-4- تحقیقات مرتبط… 4

1-5- ساختار پایان نامه. 5

2-  فصل دوم:ادبیات تحقیق    6

2-1- تعریف معماری سازمانی.. 7

2-2- انواع معماری سازمانی.. 8

2-3- فرایند معماری سازمانی.. 8

2-4- تفاوت محصولات معماری سازمانی با روش‌های دیگر. 9

2-5- کاربرد معماری سازمانی.. 10

2-6- جایگاه معماری سازمانی.. 11

2-7- آشنائی با چارچوب‌های معماری سازمانی.. 12

2-7-1- چارچوب معماریِ زكمن.. 15

2-7-2- چارچوب معماریِ سازمانی فدرال.. 16

2-7-3-  چارچوب سازمان خزانه داری.. 19

2-7-4- چارچوب معماری C4ISR.. 20

2-8- چالش‌های روش‌های كلاسیک معماری سازمانی.. 27

2-9-  چابکی در معماری سازمانی.. 31

2-10- اصول حاكم بر معماری سازمانی چابك…. 33

2-11-  اهداف معماری سازمانی چابك…. 34

2-12- به‌کارگیری تجارب عملی چابك در معماری سازمانی.. 35

3-  فصل سوم :روش پیشنهادی    39

3-1- مقدمه    40

3-2- متدلوژی‌های چابک…. 40

3-2-1- متدولوژیDSDM… 42

3-3- چابک‌سازی چارچوب معماری C4ISR.. 44

 

3-3-1- برنامه ریزی ترخیص (تعیین وضعیت موجود). 46

3-3-2-  برنامه ریزی تكرار (تعیین وضعیت مطلوب). 50

3-3-3- برنامه ریزی روزانه (طرح گذار). 54

3-4- بررسی و ارزیابی راه حل چابك پیشنهادی.. 58

4-  فصل چهارم: مطالعه موردی… 60

4-1- مقدمه    61

4-2- محصولات معماری C4isr. 63

4-2-1- محصول معماری AV -1. 63

4-3- رویکرد بررسی،دیدگاه‌ها و محصولات معماری ارائه شده. 64

4-4- محصول معماری OV-1. 65

4-5- محصول معماری OV-5. 66

4-6- محصول معماری OV-6c. 67

4-7- محصول معماری  OV-2. 67

4-8- محصول معماری OV-6b. 69

4-9- محصول معماری OV-7. 71

4-10-  نتیجه گیری.. 72

5-  نتیجه‌گیری و پیشنهادات… 74

5-1- خلاصه تحقیق.. 75

5-2- محدودیت های تحقیق.. 75

5-3- نتایج تحقیق.. 75

5-4- پیشنهادات و کارهای آتی.. 76

مراجع.. 78

 

 

 

فهرست جداول

جدول ‏2‑1-  ماتریس چارچوب سازمان  خزانه داری.. 20

جدول ‏2‑2-  محصولات معماری در چارچوب C4ISR 26

جدول ‏2‑3- تفاوت‌های معماری سازمانی چابك با معماری سازمانی كلاسیك… 34

 

 

 

فهرست شکل‌ها

شکل ‏2‑1- جایگاه معماری سازمانی و ارتباط آن با سایر حوزه‌های سازمان. 11

شکل ‏2‑2- وجه‌ها و دیدگاه‌های مختلف چارچوب معماری زكمن.. 16

شکل ‏2‑3- مؤلفه‌های چارچوب معماری سازمانی فدرال. 17

شکل ‏2‑4- دیدگاه‌های چارچوب معماری c4isr 21

شکل ‏2‑5- تعاملات دیدگاه‌های مختلف چارچوبC4ISR     24

شکل ‏2‑6- پشته مدیریت چابك نیازمندی‌های كاربران. 36

شکل ‏3‑1: فرایند متدلوژی DSDM 43

شکل ‏3‑2-چرخه حیات DSDM… 45

شکل ‏3‑3- دیدگاه‌های چارچوب C4ISR.. 46

شکل ‏3‑4- برنامه ریزی ترخیص… 47

شکل ‏3‑5- یک داستان كاربری ساده و اولیه. 48

شکل ‏3‑6- برنامه ریزی تكرار 51

شکل ‏3‑7-نمونه‌ای از كارت CRC.. 52

شکل ‏3‑8-مدل چابک چارچوب C4ISR.. 56

شکل ‏4‑1-  محصول معماری OV-1 از دید سطح بالا. 65

شکل ‏4‑2- محصول معماری OV-1 از دید سناریوی AV- 1. 65

شکل ‏4‑3- فلوچارت حمله به هدف در قالب محصول معماری OV- 5. 66

شکل ‏4‑4-نمودار توالی فازها در محصول معماری OV-6c. 68

شکل ‏4‑5- نمودار کلاس نودهای شرکت کننده در عملیات ارزیابی و اجرای حمله مطابق با محصول معماری      OV- 2     69

شکل ‏4‑6- نمودار ماشین حالت مطابق با محصول معماری OV-6b. 71

شکل ‏4‑7- مدل منطقی داده مطابق با محصول معماری OV-7. 72

1-1- مقدمه

یكی از مهمترین دلایل كندی و فرسایشی بودن فرایند معماری سازمانی تغییرات مداوم در حوزه فناوری و یا ماموریت های یک سازمان است. یكی از پارادایم های مطرح شده در حوزه معماری سازمانی پارادایم چابكی است. چابكی به معنی تطبیق پذیر بودن در مقابل تغییرات مداوم كسب و كار است.

نیروهای مسلح جمهوری اسلامی ایران، در راستای انجام ماموریتهای خود، نیازمند سیستمهائی یكپارچه و تعامل پذیر هستند. به منظور رسیدن به سیستمهای مطلوب ابتدا لازم است تا آنها را بصورتی علمی توصیف نمائیم. بهترین راه حل برای ایجاد توصیف های یكدست،‌ یكپارچه، و تعامل پذیر، استفاده از یک چارچوب معماری مناسب است. در صورتیكه هر سازمان، اقدام به توصیف سیستمهای خود نماید، به توصیفهائی ناسازگار و فاقد یكپاچگی و تعامل پذیری خواهیم رسید. با وجود اینكه در اكثر متون به چارچوب زكمن به عنوان اولین چارچوب معماری سامانه های اطلاعاتی اشاره می‌شود، ولی باید گفت كه تلاشی كه در وزارت دفاع آمریكا در جهت معماری سامانه های اطلاعاتی و ارتباطی صورت گرفت، مستقل از چارچوب زكمن و مسائل مطرح شده در آن بود. C4ISR كه در ابتدا برای معماری سامانه های ارتباطی و اطلاعاتی در صحنة عملیات نظامی‌ تدوین شده بود، رفته رفته جای خود را به عنوان یک راه حل ممتاز برای پرداختن به معماری در حوزه های دیگر نیز باز كرد. چارچوب C4ISR بر خلاف زكمن كه شامل شش دیدگاه می‌شد از سه دیدگاه تشكیل شده كه با هم تفاوت عمده دارند، این سه دیدگاه عبارتند از :

دیدگاه عملیاتی(Operational View) : این دیدگاه توصیف كننده وظایف و عملكردهای گره های عملیاتی و گردش اطلاعات بین این گره ها در جهت انجام عملیات ‌است. با بهره گرفتن از نمادهای گرافیكی می‌توان گره ها و عناصر عملیاتی، چگونگی انجام و پشتیبانی عملیات، نحوه گردش و تبادل اطلاعات بین گره ها را مشخص نمود.

دیدگاه سیستمی(System View) : این دیدگاه توصیف كننده سیستمهای اطلاعاتی و چگونگی ارتباط بین آنها در جهت انجام یا پشتیبانی عملیات ‌است. آنچه كه نشان دهنده نقش فناوری در كمك به انجام بهتر ماموریتهای سازمانی بوده، در اینجا توصیف می‌شود. از دیدگاه عملیاتی كه به دیدگاه سیستمی ‌وارد شویم، گره های عملیاتی با سیستم های اطلاعاتی و فواصل با خطوط انتقال اطلاعات جایگزین می‌شوند.

دیدگاه تكنیكی(Technical View) : این دیدگاه توصیف كننده قوانین، مشخصات و ملزومات تعیین شده برای هر سیستم در جهت نیل به اهداف و وظایف تعریف شده آن است. در حقیقت هدف از این دیدگاه، تضمین تطابق در عملكرد سیستم ها با انتظارات خواسته شده از آنهاست

 

هدف نهایی چارچوب معماری C4ISR، افزایش میزان تعامل در سطح سازمان می‌باشد. با توجه به سایر چارچوب های معماری، در چارچوب معماریC4ISR  “استاندارد سازی” بطور کامل مورد توجه قرار می گیرد. یکی از مهمترین اهداف اصلی معماری عملیاتی در چارچوب C4ISR تعریف ملزومات تبادل اطلاعات می‌باشد.

از جمله ویژگی های چارچوب معماری C4ISR می‌توان به موارد زیر اشاره کرد:

• محصول گرا
• نمایش اطلاعات و تعامل پذیری

چکیده

سیستمهای چند عامله سیستمهای محاسباتی هستند که در آن چندین عامل جهت رسیدن به یک هدف خاص با هم در تعامل هستند و با هم کار می کنند. دلیل پیدایش اینگونه سیستمها وجود موقعیتهایی است که در آن یک مسأله بایستی در یک مد توزیع شده حل شود. به عنوان مثال در شرایطی که استفاده از یک کنترل کننده مرکزی ممکن نیست و یا اینکه می­خواهیم استفاده مناسبی از منابع توزیع شده و یا امکانات محاسباتی داشته باشیم. با اینکه زمان زیادی از معرفی این گونه سیستم‌ها نمی‌گذرد ولی استفاده از روش‌های طراحی بر اساس عامل یکی از موفق‌ترین راه ‌حل ‌های موجود بوده و حاصل این شیوه طراحی یعنی سیستم‌ حل مسائل به صورت توزیع‌شده از بهترین سیستم‌ها به شمار می‌آید و به عنوان ابزار جدیدی برای حل انواع فرایندهای انسانی شناخته می‌شود. مسأله ارضاء محدودیت توزیع شده سالهاست که در حوزه تحقیق سیستمهای چند عامله مورد توجه زیادی قرار گرفته است. و این مسأله بدان علت است که بسیاری از مسائل اعم از مسائل کلاسیکی همانند مسأله n-وزیر و رنگ آمیزی گراف گرفته و تا مسائل کاربردی بزرگ دنیای واقعی همچون زمانبندی و برنامه ریزی و تخصیص منابع می­توانند برای حل شدن به عنوان یک مسأله مسأله ارضاء محدودیت توزیع شده فرموله شوند. بنابراین ارائه یک شیوه جدید و یا اصلاح شیوه های فعلی تاثیر زیادی بر دامنه تحقیقاتی این فیلد می­گذارد. آنچه در این پایان نامه ارائه می­ شود ارائه تکنیکی جدید برای حل مسائل ارضاء محدودیت توزیع شده است. این تکنیک جدید محدودیتها را در یک سیستم که ترکیبی از سیستمهای توزیع شده و متمرکز است اداره و کنترل می­ کند که با بهره گیری از یک سری ویژگیهای خاص تعریف شده از سیستمهای ترکیبی دیگر موجود متمایز می­ شود. نتایج حاصله نشان می دهد که این الگوریتم در مسائل با مقیاس بزرگ کارایی خوبی خواهد داشت و تقریبا یک پیچیدگی زمانی خطی را با افزایش مقیاس مسأله به دست می­آورد. همچنین مقایسه این روش با چند روش دیگر بهبود عملکرد این روش را در پارامترهای مختلف نسبت به دیگر روشها نشان می­دهد.

 

 

فهرست مطالب

 

عنوان                                                                                                                                        صفحه

فصل اول: مقدمه

• مسئله ارضاء محدودیت(CSP: Constraint Satisfaction Problem) …………………………………….. 3

  • تعریف مسئله ارضاء محدودیت(CSP: Constraint Satisfaction Problem):……………………………………….. 3
  • الگوریتمهای کلاسیک مسائل ارضاء محدودیت…………………………………………………………………………………………………….. 5
  • CSP به عنوان یک مسئله جستجو……………………………………………………………………………………………………………………..  7
  • بهبود کارآیی الگوریتمهای جستجوتوسط توابع اکتشافی یا به عبارتی هیوریستیک ها………………………………………. 8
  • محدودیتهای ویژه………………………………………………………………………………………………………………………………………………… 12
  • کاربرد جستجوهای محلی در حل مسائل ارضاء محدودیت……………………………………………………………………………….. 12
  • ساختار مسئله………………………………………………………………………………………………………………………………………………………. 12
• سیستمهای چند عامله………………………………………………………………………………………………………………………….. 14
• حل مسائل CSP توسط سیستمهای چند عامله؛(DCSP)………………………………………………………………. 16

 

فصل دوم: بر تحقیقات پیشین

• مرور کلی………………………………………………………………………………………………………………………………………………. 19

• الگوریتمهای هرس دامنه……………………………………………………………………………………………………………………… 22

  • الگوریتم تصفیه…………………………………………………………………………………………………………………………………………………… 22
  • الگوریتم فرا استدلال………………………………………………………………………………………………………………………………………….. 25

• الگوریتمهای اکتشافی…………………………………………………………………………………………………………………………… 27

  • الگوریتم عقبگرد نامتقارن………………………………………………………………………………………………………………………………………. 28
  • الگوریتم الزام ضعیف نامتقارن…………………………………………………………………………………………………………………………………. 32
  
  

• الگوریتمهایی که از ترکیب روش های متمرکز و توزیع شده استفاده می کنند…………………………………….. 33

  • الگوریتم APO……………………………………………………………………………………………………………………………………………………….. 33
  
  

• الگوریتمهای ناقص……………………………………………………………………………………………………………………………….. 37

  • الگوریتم DBA ……………………………………………………………………………………………………………………………………………………  37
  • الگوریتمهای مبتنی بر کلونی مورچه ها در حل مسائل ارضاء محدودیت توزیع شده…………………………………………. 37
  
  

 

فصل سوم: طراحی و پیاده سازی روش های پیشنهادی برای مسائل DCSP و بررسی نتایج حاصله

• معیارهای ارزیابی کیفیت روش های حل مسائل ارضاء محدودیت توزیع شده…………………………………. 44

3-1-1- میانگین زمان اجرای الگوریتم با افزایش مقیاس مسأله……………………………………………………………………………………….  45

3-1-2- میانگین تعداد چرخه های اجرا شده تا رسیدن به یک راه حل …………………………………………………………………………..  45

3-1-3- تعداد پیام های ارسال و دریافت شده…………………………………………………………………………………………………………………….  45

3-1-4- NCCC ……………………………………………………………………………………………………………………………………  45

3-1-5- قانونی و کامل بودن………………………………………………………………………………………………………………………………………………… 46

• محکها و مجموعه داده ای مورد استفاده برای آزمایشات………………………………………………………………. 45

3-2-1- مسأله n-وزیر ………………………………………………………………………………………………………………………………………………………..  46

3-2-2- مسأله رنگ­آمیزی گراف ………………………………………………………………………………………………………………………………………..  47

3-2-3- مسائل زمانبندی ……………………………………………………………………………………………………………………………………………………  48

3-2-4- مسائل ارضاء محدودیت باینری

 …………………………………………………………………………………………………………………………….  51

3-3- طراحی و پیاده سازی روش های پیشنهادی و نتایج حاصله از آنها………………………………………………………. 52

3-3-1- استفاده از ترکیب الگوریتمهای تکاملی و سیستمهای چندعامله برای حل مسائل ارضاء محدودیت ………………  52

3-3-2- قدرت مورچه ها در حل مسائل ارضاء محدودیت توزیع شده………………………………………………………………………………  60

 

فصل چهارم: روش جدید ارائه شده

4-1- بر مفاهیم و موضوعات مورد بحث دراین روش پیشنهادی…………………………………………………….. 69

• توصیف مسائل ارضاء محدودیت توزیع شده؛(DCSP) ………………………………………………………………………………..  69
• تعریف محدودیت Alldiff یا Alldifferent ………………………………………………………………………………………………. 70
• توابع اکتشافی …………………………………………………………………………………………………………………………………………………… 70

• تقسیم بندی الگوریتم های مطرح شده برای مسائل DCSP ……………………………………………………………. 71

4-3- توصیف روش جدید ارائه شده و جزئیات پیاده سازی آن…………………………………………………………………… 73

4-4- حل یک مثال با بهره گرفتن از این الگوریتم…………………………………………………………………………………………….. 80

4-5- ارزیابی و مقایسه الگوریتم ما با دیگر روشها……………………………………………………………………………………….  82

4-6- نتیجه گیری و برشمردن مزایا و معایب این روش……………………………………………………………………………..  84

 

 

 

فصل پنجم: نتیجه گیری

5-1- نتیجه گیری………………………………………………………………………………………………………………………………………  87

5-2- پیشنهادات و کارهای آینده……………………………………………………………………………………………………………….  89

فهرست منابع………………………………………………………………………………………………………………………..  90

 

 

 فهرست تصاویر

 

عنوان                                                                                                                                        صفحه

شکل 1-1  مثالی از مساله CSP [4] …………………………………………………………………………………………………………………. 4

شکل 1-2  یک طرح جامع از به کار بردن تکنیکهای ارضاء محدودیت برای حل مسائل [54] ……………………….. 5

شکل 1-3 (الف) نواحی استرالیا (ب) عملکرد توابع اکتشافی مختلف بر روی این نقشه [2] …………………………………………… 11 شکل 1-4 زیرمسأله های مستقل در گراف محدودیت [2] ……………………………………………………………………………… 13

شکل 1-5  کاهش گراف محدودیت به درخت توسط حذف گرهها [2] ………………………………………………………….. 13

شکل 1-6 کاهش گراف محدودیت به درخت توسط تجزیه گراف [2] ……………………………………………………………. 14

شکل 1-7 یک شبکه حسگر واقعی برای مانیتور کردن محیط داخلی یک ساختمان[4] ………………………………. 15

شکل 2-1 یک طبقه بندی از الگوریتمهای مطرح در حل مسائل DCSP ………………………………………………………. 20

شکل 2-2 چهار حالت مختلف از مسئله کلاسیک رنگ آمیزی گراف و نتیجه پیاده سازی الگوریتم تصفیه برای هر یک از این مسائل[4] ……………………………………………………………………………………………………………………………………. 24

شکل 2-3 سیکل 1 الگوریتم ABT بر روی مسئله 4 وزیر[4] ………………………………………………………………………… 29

شکل 2-4 سیکل 2 از الگوریتم ABT بر روی مسئله 4وزیر[4] ……………………………………………………………………… 29

شکل 2-5 سیکل 3 از الگوریتم ABT بر روی مسئله 4 وزیر[4] …………………………………………………………………….. 30

شکل 2-6 سیکل 4 و 5  از الگوریتم ABT بر روی مسئله 4وزیر[4] ……………………………………………………………… 30

شکل 2-7 سیکل 6 از الگوریتم ABT بر روی مسئله 4وزیر[4] ……………………………………………………………………… 31

شکل 2-8  سیکل 7  و 8  از الگوریتم ABT بر روی مسئله 4وزیر[4] ………………………………………………………….. 31

شکل 2-9 سیکل 9 از الگوریتم ABT بر روی مسئله 4وزیر[4] ……………………………………………………………………… 31

شکل 2-10 سیکل 10  از الگوریتم ABT بر روی مسئله 4وزیر [4] ……………………………………………………………… 32

شکل 2-11 الگوریتم APO  [22] ……………………………………………………………………………………………………………………. 35

شکل 2-12 مثالی از گراف ساختار [44] …………………………………………………………………………………………………………. 39

شکل 2-13 ساختن یک گراف برای یک مسأله با سه متغیر …………………………………………………………………………… 40

شکل 3-1 جهت حرکات ممکن یک مهره وزیر در یک صفحه شطرنج ……………………………………………………………. 46

شکل 3-2 یک جواب برای مسأله 8-وزیر …………………………………………………………………………………………………………. 47

شکل 3-3 مثالی از رنگ آمیزی گراف(یک رنگ آمیزی از گراف معروف پترسن) …………………………………………… 48

شکل 3-4 مثالی از مساله CSP [4] …………………………………………………………………………………………………………………. 52

شکل 3-5 مدل فرض شده از محیط شبکه مانند عاملها[3] ……………………………………………………………………………. 53

شکل 3-6 میانگین زمان اجرای الگوریتم MAEA-CSPs در حل مسأله n-وزیر [3] ……………………………………. 58

شکل 3-7 مقایسه الگوریتم MAEA-CSPs با 4 الگوریتم دیگر با معیارهای SR، ME و AES [4] ……………. 59

شکل 3-8 مقایسه دو الگوریتم DBA و ABT با الگوریتم پیشنهادی مورچه ها بر روی مساله رنگ آمیزی گرافی با تراکم 2 ، بر اساس نسبت تغییر سایز مسأله به تعداد پیامها ………………………………………………………………………… 63

شکل 3-9 مقایسه دو الگوریتم DBA و ABT با الگوریتم پیشنهادی مورچه ها بر روی مساله رنگ آمیزی گرافی با تراکم 2 ، بر اساس نسبت تغییر سایز مسأله به معیار مقایسه NCCC ………………………………………………………… 63

شکل 3-10 مقایسه دو الگوریتم DBA و ABT با الگوریتم پیشنهادی مورچه ها بر روی مساله رنگ آمیزی گرافی با تراکم .32 ، بر اساس نسبت تغییر سایز مسأله به تعداد پیامها …………………………………………………………. 63

شکل 3-11 مقایسه دو الگوریتم DBA و ABT با الگوریتم پیشنهادی مورچه ها بر روی مساله رنگ آمیزی گرافی با تراکم 2.3 ، بر اساس نسبت تغییر سایز مسأله به معیار مقایسه NCCC ………………………………………….. 64

شکل 3-12 مقایسه دو الگوریتم DBA و ABT با الگوریتم پیشنهادی مورچه ها بر روی مساله رنگ آمیزی گرافی با تراکم .72 ، بر اساس نسبت تغییر سایز مسأله به تعداد پیامها …………………………………………………………. 64

شکل 3-13 مقایسه دو الگوریتم DBA و ABT با الگوریتم پیشنهادی مورچه ها بر روی مساله رنگ آمیزی گرافی با تراکم 2.7 ، بر اساس نسبت تغییر سایز مسأله به معیار مقایسه NCCC ………………………………………….. 65

شکل 4-1 یک طبقه بندی از الگوریتمهای مطرح در حل مسائل DCSP ………………………………………………………. 72

شکل 4-2 مرحله 1 تا 4 از الگوریتم DACA ………………………………………………………………………………………………….. 80

شکل 4-3 مرحله 5 از الگوریتم DACA ………………………………………………………………………………………………………….. 81

شکل 4-4 مرحله پایانی الگوریتم DACA ……………………………………………………………………………………………………….. 82

شکل 4-5 میانگین زمان اجرای الگوریتم DACA در اجرای مسأله n-وزیر با افزایش n از 4 تا 104 در گامهای 50 تایی ………………………………………………………………………………………………………………………………………………………………. 82

 

 

 

 

فهرست جداول

 

عنوان                                                                                                                                        صفحه

جدول 3-1 نتایج بدست آمده از آزمایش MAEA-CSPs بر روی مسائل ارضاء محدودیت باینری …………… 59

جدول 3-2 مقادیر متفاوت از تعداد مورچه ها برای سایزها و تراکم­های متفاوت …………………………………………….60

جدول4-1 مقایسه الگوریتم پیشنهادی ما با دو روش دیگر از لحاظ تعداد سیکلهای مورد نیاز برای حل ……… 82

جدول4-2 مقایسه روش پیشنهادی ما با روش ERA از لحاظ میانگین زمان اجرا ……………………………………….. 82

مقدمه

از سال 1974، مسائل ارضاء محدویت (CSP[1]) در مسأله پردازش تصویر پیشنهاد شد. پس از آن CSP به طور گسترده در بسیاری از حوزه های هوش مصنوعی و علوم کامپیوتر به عنوان یک روش حل مهم مورد استفاده قرار گرفته است. از مسأله چند وزیر و رنگ آمیزی گراف گرفته و دیگر مسائل کلاسیک گرفته تا زمانبندی و تخصیص منابع و دیگر مسائل کاربردی بزرگ می­توانند برای حل شدن به عنوان یک مسأله CSP فرموله شوند. بعد از سال 1990 با جایگزین شدن زبان برنامه نویسی عمومی به جای زبان برنامه نویسی منطقی مسأله ارضاء محدودیت کاربرد CSP برای حل مسائل بسیار بهبود یافت [1]. یک CSP، با یک مجموعه از متغیرها، دامنه ای برای هر یک از آنها و محدودیتهایی در مقادیری که متغیرها ممکن است به صورت همزمان به خودشان بگیرند، تعریف می­شوند. نقش الگوریتمهای ارضاء محدودیت، نسبت دادن مقادیری به متغیرهاست به نحوی که با تمام محدودیتها سازگاری داشته باشد یا مشخص کند که هیچ انتسابی امکان پذیر نیست. امروزه تکنیکهای ارضاء محدودیت در حوزه های مختلفی از جمله بینایی ماشین، پردازش زبانهای طبیعی، اثبات قضایا، زمانبندی و… به کار می­روند [4].

از طرف دیگر موقعیتهایی وجود دارد که در آن یک مسأله بایستی در یک مد توزیع شده حل شود به عنوان مثال در شرایطی که استفاده از یک کنترل کننده مرکزی ممکن نیست و یا اینکه می­خواهیم استفاده مناسبی از منابع توزیع شده و یا امکانات محاسباتی داشته باشیم. در چنین مواقعی عاملها برای رسیدن به یک هدف مشترک تلاش می­ کنند. هر سیستم چند عامله یک سیستم محاسباتی است که در آن چندین عامل جهت رسیدن به یک هدف خاص با هم در تعامل هستند و با هم کار می­ کنند [4].

مسأله ارضاء محدودیت توزیع شده (DCSP[8]) در واقع حالت توزیع شده­ی مسأله­ ارضاء محدودیت کلاسیک است که در آن متغیرها بین عاملهای مستقل توزیع شده ­اند. این محیط توزیع شده شامل تعدادی عامل هوشمند است که هر کدام، یک یا چند متغیر را مالک می­شوند و مقدار آن را کنترل می­ کنند. همه این عامل ها در تلاشند تا با حفظ استقلالشان به هدف مشترک دست یابند. هدف هنوز یافتن یک انتساب برای متغیرهاست که محدودیتها را هم در نظر داشته باشد اما هر عامل، برای مقدار متغیر مالکش با خودمختاری نسبی تصمیم می­گیرد. هر چند عاملها یک دید عمومی ندارند اما هر یک از آنها می ­تواند با همسایه اش در گراف محدودیت ارتباط برقرار کند. هر عامل سعی می­ کند نه تنها با ارضاء محدودیتهای محلی خود بلکه با برقرای ارتباط با سایر عاملها به منظور حل محدودیتهای خارجی به این هدف نزدیک و نزدیکتر شود. به طور کلی تمام مسائلی که در آنها هدف یافتن مقادیر مناسب برای انتساب به متغیرهای توزیع شده است را می­توان جزء مسائل ارضاء محدودیت توزیع شده به حساب آورد. در یک سیستم چند عاملی به هر عامل یک یا چند متغیر از میان متغیرهای توزیع شده منتسب می­ شود. وظیفه این عامل خودمختار کنترل و مدیریت مقدار این متغیر می­باشد [4] و [22]. این مسأله عمومی کاربردهای زیادی در زندگی واقعی دارد. مثلا در بسیاری از مسائل تخصیص منابع: در شبکه های حس گر بی سیم، کنترل علائم راهنمایی شهری، شبکه های حس گر توزیع شده، مسائل نجات یافتن از فاجعه و بسیاری از مسائل مربوط به زمان بندی مثلا برای قطارها و دانشگاه ها. هدف معمول در حل همه این مسائل یافتن مقادیر مناسب برای تخصیص دادن به متغیر های توزیع شده است. به عبارت دیگر هر مسأله ای که هدف آن یافتن مقدار مناسبی برای تخصیص به متغیرهای توزیع شده است می ­تواند به عنوان DCSP طرح ریزی شود.

در این تحقیق به مسائل ارضاء محدودیت توزیع شده پرداخته می­ شود که در آن عاملها در یک مد توزیع شده برای یافتن یک راه حل ممکن برای مسأله تلاش می­ کنند.

[1] Constraint Satisfaction Problem

[2] image processing

امروزه با گسترش و رشد روز افزون اطلاعات در فضای مجازی و وجود انبوهی از کالا یا خدماتی که در وب سایتهای تجاری و خدماتی ارائه می­گردند کاربران را با این مشکل مواجه نموده است که چگونه کالا یا خدمت مورد  نظر خود را به راحتی و با صرف کمترین زمان ممکن بیابند. در این میان سیستمهای توصیه­گر با هدف تسهیل و یاری رساندن به کاربران در زمینه انتخاب و یافتن کالای مورد نیاز ایشان با بهره گرفتن از علوم و روش های مبتنی بر داده کاوی اطلاعات، ایجاد و توسعه یافته­اند. همچنین در سالهای اخیر ظهور و گسترش شبکه­ های اجتماعی و شبکه­ های مبتنی بر رابطه اعتماد میان کاربران، باعث گشوده شدن افق جدیدی در ارائه سیستمهای توصیه­گر و توسعه نسل جدیدی از اینگونه سیستمها گردیده است و آنرا به یکی از موضوعات جذاب و مورد توجه محققان تبدیل نموده است.

از میان روشها و مدل­های موجود در زمینه سیستمهای توصیه­گر روش پالایش گروهی به لحاظ سادگی پیاده­سازی از محبوبیت قابل ملاحظه­ای برخوردار است اما این روش در ارائه پیشنهادات مناسب و قابل قبول به کاربران تازه وارد دارای ضعف­های جدی می­باشد. سیستمهای توصیه­گر مبتنی بر اعتماد، با بهره­ گیری از رابطه اعتماد میان کاربران، در جهت رفع نقاط ضعف بیان شده و خصوصا ارائه پیشنهادات مناسب به کاربران تازه وارد گامهای موثری برداشته اند. در این تحقیق سعی شده است تا از تلفیق و ترکیب روش­های موجود در زمینه پالایش گروهی و همچنین مدلهای مبتنی بر اعتماد و بررسی نقاط ضعف و قوت آنها مدلی نوین و توسعه یافته ارائه گردد که در آن نتایج از خطای کمتر و دقت بالاتری برخوردار بوده و با افزایش معیار پوشش  بتوان به درصد بیشتری از کاربران پاسخ مناسب ارائه نمود. برای این منظور در میان انواع روش های پالایش گروهی، روش مبتنی بر آیتم و برای پیمایش شبکه اعتماد میان کاربران نیز از روش پیمایش تصادفی بهره گرفته شده است، همچنین با تفسیر و تعدیل نظرات کاربران و اتخاذ شیوه­ای مناسب جهت محاسبه مقدار دقیق اعتماد میان کاربران و تغییر در نحوه پیمایش شبکه اعتماد میان ایشان سعی در بهبود و کاهش خطاهای نتایج گردیده است. در نهایت، جهت ارزیابی و برآورد مدل ترکیبی ارائه شده، نتایج و آمارهای حاصل از اجرای مدل پیشنهادی بر روی مجموعه داده های Epinions و Movielens و مقایسه آنها با نتایج مدل پایه TrustWalkerبه عنوان یکی از بهترین مدلهای ترکیبی ارائه شده در زمینه سیستمهای توصیه گر مبتنی بر اعتماد، ارائه می­گردد.

 

واژه­های کلیدی: داده ­کاوی[1]، شبکه­ های اجتماعی[2]، شبکه­ های مبتنی بر اعتماد[3]، سیستمهای توصیه­گر[4]، پالایش گروهی[5]، اعتماد[6]، پیمایش تصادفی[7]، ترکیب سازی[8]

 

 

فهرست مطالب

 

عنوان…………………………………………………………………………………………………………….صفحه

 

فصل اول : مقدمه­ای بر انواع سیستم توصیه­گر…………………………………………………1

       1-1- مقدمه…………………………………………………………………………………………………………………..2

1-2- سیستمهای توصیه­گر…………………………………………………………………………………………..3

1-3- انواع سیستمهای توصیه­گر از لحاظ عملکردی……………………………………………………4

1-4- مزایا و اهمیت یک سیستم توصیه­گر کارآمد………………………………………………………5

1-5- معایب و مشکلات کلی سیستمهای توصیه­گر……………………………………………………..6

1-6- انواع رویکردها و مدلهای موجود در زمینه پیاده­سازی سیستمهای توصیه­گر…….7

1-7- تشریح و بیان مسئله………………………………………………………………………………………….11

1-8- اهداف تحقیق…………………………………………………………………………………………………….12

1-9- سوالات و فرضیه ­های تحقیق…………………………………………………………………………….13

1-10- مراحل تحقیق…………………………………………………………………………………………………14

1-11- فصول پایان نامه……………………………………………………………………………………………..15

 

فصل دوم : بر ادبیات تحقیق و مبانی نظری تحقیق………………………………17

       2-1- مقدمه ……………………………………………………………………………………………………………….18

2-2- پالایش گروهی (Collaborative Filtering)…………………………………………….19

2-2-1- پالایش گروهی مبتنی بر حافظه(Memory Based)……………………………..20

2-2-1-1- روش پالایش گروهی مبتنی بر آیتم ………………………………………………………22

2-2-1-2- امتیازدهی به صورت پیش فرض……………………………………………………………..24

2-2-1-3- تشدید حالت(Case Amplification)……………………………………………….24

2-2-2- پالایش گروهی مبتنی بر مدل(Model Based)……………………………………..25

2-3- پالایش محتوایی (Content Based Filtering) ………………………………………26

2-4- تکنیکهای ترکیبی……………………………………………………………………………………………..27

2-5- سیستمهای توصیه­گر مبتنی بر رابطه اعتماد میان کاربران……………………………..28

2-5-1- چگونگی کارکرد سیستم توصیه­گر مبتنی بر اعتماد……………………………………30

2-5-2- مزایا و معایب………………………………………………………………………………………………..31

2-5-3- انتشار اعتماد و تجمیع اعتماد………………………………………………………………………33

2-6- چالش ها و محدودیتهای موجود………………………………………………………………………33

2-6-1- نقصان و کاستی اطلاعات……………………………………………………………………………..34

2-6-2- مشکل کاربران تازه وارد………………………………………………………………………………..34

2-6-3- کلاهبرداری و تقلب………………………………………………………………………………………35

2-6-4- پیچیدگیهای محاسباتی و زمانی…………………………………………………………………..36

2-7- معیارهای ارزیابی سیستمهای توصیه­گر……………………………………………………………37

2-7-1- خطای جذر میانگین مربعات (RMSE)…………………………………………………….37

2-7-2- معیار درصد پوشش………………………………………………………………………………………38

2-7-3- معیار دقت…………………………………………………………………………………………………….39

2-7-4- معیار F-Measure…………………………………………………………………………………….39

 

فصل سوم : بر مطالعات و تحقیقات پیشین…………………………………………..41

       3-1- مقدمه………………………………………………………………………………………………………………..42

3-2- مرور کارهای گذشته………………………………………………………………………………………….42

3-2-1- مدل MoleTrust………………………………………………………………………………………45

3-2-2- مدل TidalTrust………………………………………………………………………………………47

3-2-3- مدل دانه سیب……………………………………………………………………………………………..48

3-2-4- مدل ارائه شده توسط  Anderson……………………………………………………………48

3-2-5- مدل ارائه شده توسط  O’Donovan………………………………………………………..49

3-2-6- مدل TrustWalker………………………………………………………………………………….50

3-2-6-1- ساختار مدل TrustWalker…………………………………………………………………51

3-2-6-2- تشابه آیتم ها……………………………………………………………………………………………51

3-2-6-3- خصوصیات ویژه مدل TrustWalker…………………………………………………..52

3-2-6-3-1- فراگیری و عمومیت مدل…………………………………………………………………….52

3-2-6-3-2- اطمینان به نتایج حاصل………………………………………………………………………53

3-2-6-3-3- تفسیرپذیری و قابل توضیح بودن نتایج………………………………………………54

3-2-6-4- نمایش ماتریسی مدل TrustWalker………………………………………………….54

3-2-6-5- نتیجه گیری در خصوص مدل TrustWalker…………………………………….55

 

 

فصل چهارم : تشریح مدل ترکیبی پیشنهادی و چگونگی توسعه و بهبود مدل پایه.56

       4-1- مقدمه………………………………………………………………………………………………………………..57

4-2- تشریح مدل کلی TrustWalker…………………………………………………………………..57

4-2-1- علائم نشانه گذاری و متغیرهای مدل…………………………………………………………..57

4-2-2- روند یک پیمایش تصادفی در شبکه…………………………………………………………….58

4-2-3- انتخاب تصادفی یک کاربر …………………………………………………………………………..59

4-2-4- انتخاب یک آیتم مشابه…………………………………………………………………………………59

4-2-5- تشابه آیتم ها…………………………………………………………………………………………………60

4-2-6- محاسبه احتمال ماندن در یک گره شبکه اعتماد ( )………………………..61

4-2-7- چگونگی انجام پیش ­بینی امتیاز……………………………………………………………………62

4-2-8- چگونگی محاسبه احتمال ………………………………………….63

4-2-9- چگونگی محاسبه عملی ……………………………………………………………………….64

4-2-10- شرط اتمام کلی مدل………………………………………………………………………………….64

4-3- بهبود و توسعه مدل TrustWalker………………………………………………………………65

4-3-1- استفاده از فرمول jaccard جهت محاسبه تشابه آیتمها…………………………….66

4-3-2- حذف میانگین از فرمول پیرسون………………………………………………………………….67

4-3-3- استفاده از تکنیک مبتنی بر آیتم خالص………………………………………………………67

4-3-4- تعدیل و تفسیر نظرات کاربران……………………………………………………………………..68

4-3-5- محاسبه دقیق مقدار اعتماد یا امتیاز رابطه میان دو کاربر…………………………..71

4-3-6- محاسبه ترکیبی امتیاز رابطه میان کاربران………………………………………………….73

 

فصل پنجم :  تشریح روند انجام آزمایشات و نتایج حاصل………………………………76

5-1- مقدمه………………………………………………………………………………………………………………..77

5-2- معرفی مجموعه داده epinions……………………………………………………………………..77

5-2-1- ویژگیهای مجموعه داده epinions……………………………………………………………79

5-2-2- آماده سازی و نحوه پالایش داده ­ها……………………………………………………………….81

5-2-3- ایجاد مجموعه داده نمونه……………………………………………………………………………..83

5-3- مجموعه داده movielens……………………………………………………………………………..84

5-3-1- ویژگیهای مجموعه داده movielens………………………………………………………..84

5-4- نیازمندیهای نرم افزاری…………………………………………………………………………………….85

5-5- نیازمندیهای سخت افزاری………………………………………………………………………………..85

5-6- متدولوژی نرم افزاری…………………………………………………………………………………………86

5-7- پارامترهای پیش فرض انجام آزمایشات…………………………………………………………….86

5-8- نتایج اجرای آزمایشات با مجموعه داده epinions و movielens……………..87

5-8-1- بررسی تاثیر عمق پیمایش بر روی نتایج حاصل در خصوص کاربران تازه وارد……………………………………………………………………………………………………………………………….87

5-8-2- بررسی تاثیر تاریخ اعلام نظرات توسط کاربران……………………………………………88

5-8-3- بررسی تاثیر تغییر فرمول محاسبه تشابه آیتمها………………………………………….89

5-8-4- بررسی تاثیر بکارگیری مکانیزم تفسیر و تعدیل نظرات کاربران………………….90

5-8-5- بررسی تاثیر بکارگیری انواع روش های ترکیبی برای انتخاب کاربران و پیمایش شبکه…………………………………………………………………………………………………………………………….93

5-8-5-1- نحوه محاسبه امتیاز رابطه موجود میان کاربران……………………………………..93

5-8-5-2- بررسی تاثیر بکارگیری روش های ترکیبی در عملکرد سیستم برای تمامی کاربران………………………………………………………………………………………………………………………….94

5-8-5-3- بررسی تاثیر بکارگیری روش های ترکیبی در عملکرد سیستم برای کاربران تازه وارد ………………………………………………………………………………………………………………………99

5-8-6- بررسی تاثیر بکارگیری توام مکانیزم تفسیر امتیازات کاربران به همراه استفاده از روش های ترکیبی انتخاب کاربران و پیمایش شبکه اعتماد……………………………………101

5-9- انجام آزمایشات با مجموعه داده movielens……………………………………………..107

5-9-1- نتایج حاصل از اجرای روش های ترکیبی مورد استفاده در مدل توسعه یافته…………………………………………………………………………………………………………………………..107

 

فصل ششم : نتیجه گیری نهایی و کارهای آینده…………………………………………….110

6-1- مقدمه………………………………………………………………………………………………………………111

6-2- عملکرد مدل توسعه یافته……………………………………………………………………………….112

6-2-1- عملکرد مدل توسعه یافته در خصوص تمامی کاربران………………………………112

6-2-2- عملکرد مدل توسعه یافته در خصوص کاربران تازه وارد…………………………..114

6-3- نتیجه گیری نهایی …………………………………………………………………………………………115

6-3-1- تحلیل نهایی نتایج حاصل از انجام آزمایشات بر روی مجموعه داده epinions………………………………………………………………………………………………………………..116

6-3-2- تحلیل نهایی نتایج حاصل از انجام آزمایشات بر روی مجموعه داده movielens…………………………………………………………………………………………………………….118

6-4- پیشنهادات کارهای آینده……………………………………………………………………………….118

 

اختصارات…………………………………………………………………………………………………..120

فهرست منابع……………………………………………………………………………………………..121

فهرست جداول

 

عنوان………………………………………………………………………………………………………………….صفحه

 

جدول 3-1 : دسته­بندی مدلهای اعتماد……………………­……………………………………………………………..44

جدول 4-1 : ماتریس پراکندگی نحوه امتیازدهی دو کاربر  و ……………………………………­70

جدول 4-2 : تفسیر نظرات کاربر ……………………………………………………………………………………..70

جدول 5-1 : ساختار جدول reviews………………………………………………………………………­……………81

جدول 5-2 : ساختار جدول WOT………………………………………………………………………………­…………82

جدول 5-3 : ساختار جدول  cold_start_users…………………..­……………………………………………82

جدول 5-4 : ساختار جدول ratings­………………………………………………………………………………………83

جدول 5-5 : مقادیر پیش فرض پارامترها و متغیرهای مورد استفاده در مدل پیشنهادی­………86

جدول 5-6 : نتایج بررسی تاثیر عمق پیمایش در خصوص کاربران تازه وارد­………………………….88

جدول 5-7 : نتایج حاصل از بررسی تاثیر تاریخ اعلام نظرات کاربران­……………………………………..89

جدول 5-8 : نتایج حاصل از تغییر فرمول محاسبه تشابه آیتمها­…………………………………………….90

جدول 5-9 : نتایج حاصل از بکارگیری مکانیزم تعدیل و تفسیر نظرات کاربران­…………………….91

جدول 5-10 : نتایج حاصل از بکارگیری مکانیزم تعدیل و تفسیر نظرات کاربران در خصوص کاربران تازه وارد­…………………………………………………………………………………………………………………………91

جدول 5-11 : نتایج حاصل از اجرای روش های ترکیبی در مقابل روش مورد استفاده در مدل پایه­……………………………………………………………………………………………………………………………………………..96

جدول 5-12 : نتایج حاصل از اجرای روش های ترکیبی در مقابل روش مورد استفاده در مدل پایه برای کاربران تازه وارد­…………………………………………………………………………………………………………99

جدول 5-13 : نتایج حاصل از اجرای توام مکانیزم تعدیل و تفسیر نظر کاربران و استفاده از روش های ترکیبی پیمایش شبکه در مقابل روش مورد استفاده در مدل پایه­…………………………102

جدول 5-14 : نتایج حاصل از اجرای توام مکانیزم تعدیل و تفسیر نظر کاربران و استفاده از روش های ترکیبی پیمایش شبکه در مقابل روش مورد استفاده در مدل پایه برای کاربران تازه وارد­…………………………………………………………………………………………………………………………………………..104

جدول 5-15 : نتایج حاصل از اجرای روش های ترکیبی انتخاب کاربران و پیمایش شبکه……107

جدول 5-16 : نتایج حاصل از اجرا و بکارگیری مکانیزم تعدیل و تفسیر نظرات کاربران بر روی روش های ترکیبی انتخاب کاربران و پیمایش شبکه…………………………………………………………………108

جدول 6-1 : نتایج حاصل از مقایسه معیارهای ارزیابی مدل توسعه یافته در مقابل مدل پایه  …………………………………………………………………………………………………………………………………………………113

جدول 6-2 : نتایج حاصل از مقایسه معیارهای ارزیابی مدل توسعه یافته در مقابل مدل پایه در خصوص کاربران تازه وارد………………………………………………………………………………………………………..114

 

 

فهرست اشکال و نمودارها

 

عنوان………………………………………………………………………………………………………………….صفحه

 

شکل 2-1 : چگونگی کارکرد روش پالایش گروهی (Collaborative Filtering)……………20

شکل 2-2 : نمایش یک شبکه اعتماد به همراه امتیازات بیان شده توسط کاربران در خصوص آیتمهای مختلف…………………………………………………………………………………………………………………………31

شکل 3-1 : معماری مدل MoleTrust ارائه شده توسط Massa……………………………………….46

شکل 5-1 : بنر صفحه اصلی سایت epinions………………………………………………………………………78

نمودار 5-1 : مقایسه نتایج خطای RMSE و درصد پوشش مدل پایه و مدل توسعه یافته در خصوص کاربران تازه وارد و تمامی کاربران با بکارگیری مکانیزم تعدیل و تفسیر نظرات کاربران   ……………………………………………………………………………………………………………………………………………………92

نمودار 5-2 : مقایسه نتایج معیارF-measure مدل پایه و مدل توسعه یافته در خصوص کاربران تازه وارد و تمامی کاربران با بکارگیری مکانیزم تعدیل و تفسیر نظرات کاربران…………93

نمودار 5-3 : مقایسه نتایج معیاردرصد پوششحاصل از اجرای روش های ترکیبی در مقابل روش مورد استفاده در مدل پایه…………………………………………………………………………………………………………97

نمودار 5-4 : مقایسه نتایج  خطای RMSEحاصل از اجرای روش های ترکیبی در مقابل روش مورد استفاده در مدل پایه…………………………………………………………………………………………………………98

نمودار 5-5 : مقایسه نتایج معیار F-measureحاصل از اجرای روش های ترکیبی در مقابل روش مورد استفاده در مدل پایه……………………………………………………………………………………………….98

نمودار 5-6 : مقایسه نتایج معیار درصد پوشش حاصل از اجرای روش های ترکیبی در مقابل روش مورد استفاده در مدل پایه برای کاربران تازه وارد………………………………………………………..100

نمودار 5-7 : مقایسه نتایج خطای RMSE حاصل از اجرای روش های ترکیبی در مقابل روش مورد استفاده در مدل پایه برای کاربران تازه وارد………………………………………………………………….100

نمودار 5-8 : مقایسه نتایج معیار F-measureحاصل از اجرای روش های ترکیبی در مقابل روش مورد استفاده در مدل پایه برای کاربران تازه وارد………………………………………………………..101

نمودار 5-9 : مقایسه نتایج معیار درصد پوشش حاصل از اجرای توام مکانیزم تعدیل و تفسیر نظر کاربران و استفاده از روش های ترکیبی پیمایش شبکه در مقابل روش مورد استفاده در مدل پایه…………………………………………………………………………………………………………………………………………..103

نمودار 5-10 : مقایسه نتایج خطای RMSE حاصل از اجرای توام مکانیزم تعدیل و تفسیر نظر کاربران و استفاده از روش های ترکیبی پیمایش شبکه در مقابل روش مورد استفاده در مدل پایه  …………………………………………………………………………………………………………………………………………………103

نمودار 5-11 : مقایسه نتایج معیار F-measure حاصل از اجرای توام مکانیزم تعدیل و تفسیر نظر کاربران و استفاده از روش های ترکیبی پیمایش شبکه در مقابل روش مورد استفاده در مدل پایه…………………………………………………………………………………………………………………………………………..104

نمودار 5-12 : مقایسه نتایج معیار درصد پوشش حاصل از اجرای توام مکانیزم تعدیل و تفسیر نظر کاربران و استفاده از روش های ترکیبی پیمایش شبکه در مقابل روش مورد استفاده در مدل پایه برای کاربران تازه وارد………………………………………………………………………………………………………105

نمودار 5-13 : مقایسه نتایج خطای RMSE حاصل از اجرای توام مکانیزم تعدیل و تفسیر نظر کاربران و استفاده از روش های ترکیبی پیمایش شبکه در مقابل روش مورد استفاده در مدل پایه برای کاربران تازه وارد……………………………………………………………………………………………………………..106

نمودار 5-14 : مقایسه نتایج معیار F-measure حاصل از اجرای توام مکانیزم تعدیل و تفسیر نظر کاربران و استفاده از روش های ترکیبی پیمایش شبکه در مقابل روش مورد استفاده در مدل پایه برای کاربران تازه وارد………………………………………………………………………………………………………106

نمودار 5-15 : مقایسه نتایج خطای RMSE حاصل از اجرا و بکارگیری مکانیزم تعدیل و تفسیر نظرات کاربران بر روی روش های ترکیبی انتخاب کاربران و پیمایش شبکه………………..109

نمودار 6-1 : مقایسه عملکرد کلی مدل توسعه یافته در مقابل مدل پایه از نظر تمام معیارهای ارزیابی……………………………………………………………………………………………………………………………………..113

نمودار 6-2 : مقایسه عملکرد کلی مدل توسعه یافته در مقابل مدل پایه برای کاربران تازه وارد از نظر تمام معیارهای ارزیابی………………………………………………………………………………………………….115

 

[1] Data Mining

[2] Social Networks

[3] Trust Networks

[4] Recommender Systems

[5] Collaborative Filtering(CF)

[6] Trust

[7] Random Walk

[8] Hybridization

مقدمه

 

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

در این میان، ایجاد و گسترش شبکه­ های اجتماعی، شبکه­ های اعتماد و وجود انواع روابط میان کاربران این شبکه­ ها افق جدیدی را برروی محققان و توسعه دهندگان سیستمهای توصیه­گر گشوده است تا با بهره­ گیری از علوم اجتماعی و علوم روان شناختی حاکم در این شبکه­ ها و خصوصا وجود رابطه اعتماد میان کاربران بتوانند نسل جدیدی از سیستمهای توصیه­گر را تحت عنوان “سیستمهای توصیه­گر مبتنی بر اعتماد[1]”معرفی و عرضه نمایند. این سیستمها قادر هستند تا به درصد بیشتری از کاربران پاسخ مناسب را ارائه دهند و همچنین نتایج آنها از دقت بالاتری برخوردار می­باشد.

با توجه به کثرت کاربران و افراد عضو شبکه­ های مبتنی بر اعتماد و شبکه­ های اجتماعی، همچنین تنوع رفتار و ویژگی­های ایشان، تنها یک شیوه یا یک مدل قادر به پاسخگویی و ارائه پیشنهادات دقیق و قابل قبول نمی ­باشد که این امر باعث ظهور سیستمهای توصیه­گر ترکیبی[2]گردیده است. در این سیستمها سعی شده است تا با ترکیب انواع مختلفی از سیستمهای توصیه­گر بتوان سیستمی تولید نمود که دارای مزایای حداکثری و معایب حداقلی باشد.