چکیده

بررسی ومطالعه ی کامل داده کاوی و داده کاوی با SQL SERVER2005

پیاده سازی آن روی بانک اطلاعاتی دانشگاه آزاد قوچان

امروزه با گسترش سیستم های پایگاهی و حجم بالای داده ها ی ذخیره شده در این سیستم ها ، نیاز به ابزاری است تا بتوان داده های ذخیره شده را پردازش کرد و اطلاعات حاصل از این پردازش را در اختیار کاربران قرار داد.

داده کاوی یکی از مهمترین روش ها ی کشف دانش است که به وسیله آن الگوهای مفید در داده ها با حداقل دخالت کاربران شناخته می شوند و اطلاعاتی را در اختیار کاربران و تحلیل گران قرار می دهند تا براساس آنها تصمیمات مهم و حیاتی در سازمانها اتخاذ شوند.داده کاوی را تحلیل گران با اهداف گوناگونی از قبیل کلاس بندی, پیش بینی, خوشه بندی ,تخمین انجام می دهند. برای کلاس بندی, مدل هاو الگوریتم هایی مانند قاعده ی بیز, درخت تصمیم, شبکه ی عصبی, الگوریتم ژنتیک مطرح شده است.برای پیش بینی مدل رگرسیون خطی ومنطقی و برای خوشه بندی الگوریتم های سلسله مراتبی و تفکیکی, وبرای تخمین مدل های درخت تصمیم و شبکه ی عصبی مطرح می شود. در فصل دوم و سوم با الگوریتم ژنتیک که یکی از الگوریتم های داده کاوی و با شبکه ی عصبی که یکی از مدل های داده کاوی هستند آشنا می شویم .درفصل چهارم به محاسبات نرم و برخی از اجزای اصلی ان و نقش آنها در داده کاوی می پردازیم.

در فصل پنجم با ابزارهای داده کاوی آشنا می شویم . برای داده کاوی ابزارهای متنوعی وجود دارد. می توان ابزارداده کاوی را با تطبیق آن ابزار با داده های مسئله و با توجه به محیط داده ای که می خواهید از آن استفاده کنید، و امکاناتی که آن ابزار دارد انتخاب کنید.وسپس به داده کاوی با SQLSERVER2005 می پردازیم .ودرفصل ششم به داده کاوی با SQL SERVER2005 روی بانک اطلاعاتی دانشگاه آزاد قوچان پرداختیم.

کلمات کلیدی ،کلاس بندی ، خوشه بندی ، پیش بینی ، تخمین

فصــل اول

مقدمه ای بر داده کاوی ^[1]

1-1-مقدمه

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

داده کاوی^[3] یکی از مهمترین این روش ها است که به وسیله آن الگوهای مفید در داده ها با حداقل دخالت کاربران شناخته می شوند و اطلاعاتی را در اختیار کاربران و تحلیل گران قرار می دهند تا براساس آنها تصمیمات مهم و حیاتی در سازمانها اتخاذ شوند .

1-2-عامل مسبب پیدایش داده کاوی

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

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

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

ابزارهای داده کاوی داده ها را آنالیز می کنند و الگوهای داده ها را کشف می کنند که می توان از آن در کاربردهایی نظیر تعیین استراتژی برای کسب و کار، پایگاه دانش^[4] و تحقیقات علمی و پزشکی، استفاده کرد. شکاف موجود بین داده ها و اطلاعات سبب ایجاد نیاز برای ابزارهای داده کاوی شده است تا داده های بی ارزش را به دانشی ارزشمند تبدیل کنیم .

1-3-داده کاوی و مفهوم اکتشاف دانش (K.D.D)

با حجم عظیم داده های ذخیره شده در فایلها، بانکهای اطلاعاتی و سایر بانک های داده ای، توسعه ی ابزارهایی برای تحلیل و شاید تفسیر چنین داده هایی و برای استخراج علوم شگفت انگیزی که می توانند در تصمیم گیری مفید باشند، امری بسیار مهم و ضروری است. داده کاوی با عنوان کشف دانش در پایگاه های داده (KDD) شناخته می‌شود. کشف علومی که قبلا ناشناخته بوده‌اند و اطلاعاتی که در بانکهای اطلاعاتی موجود بوده و ذاتا بالقوه و مفید هستند.

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

1- پاکسازی داده ها : در این فاز داده های اضافی و نامربوط از مجموعه داده ها حذف می شوند.(داده های ناکامل) [2]

2-یکپارچه سازی داده ها^[5] : چندین منبع داده ترکیب می شوند،

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

4-تبدیل داده ها : هنگامی که داده های مورد نیاز انتخاب شدند و داده های مورد کاوش مشخص گردیدند، معمولا به تبدیلات خاصی روی داده ها نیاز است. نوع تبدیل به عملیات و تکنیک داده کاوی مورد استفاده بستگی دارد، تبدیلاتی ساده همچون تبدیل نوع داده ای به نوع دیگر تا تبدیلات پیچیده تر همچون تعریف صفات جدید با انجام عملیاتهای ریاضی و منطقی روی صفات موجود.

5-داده کاوی : بخش اصلی فرایند ، که در آن با استفاده از روش ها و تکنیک های خاص ، استخراج الگو های مفید ، دانش استخراج می شود.

6-زیابی الگو^[6] : مشخص کردن الگوهای صحیح و مورد نظر به وسیله معیارهای اندازه گیری.

7-زنمایی دانش : در این بخش به منظور ارائه دانش استخراج شده به کاربر ، از یک سری ابزارهای بصری سازی استفاده می گردد.

1-3-1-تعریف داده کاوی

در متون آکادمیک تعاریف گوناگونی برای داده کاوی ارائه شده اند . در برخی از این تعاریف داده کاوی در حد ابزاری که کاربران را قادر به ارتباط مستقیم با حجم عظیم داده ها می سازد معرفی گردیده است و در برخی دیگر ، تعاریف دقیقتر که درآنها به کاوش در داده ها توجه می شود. برخی از این تعاریف عبارتند از :

• داده کاوی عبارت است از فرایند استخراج اطلاعات معتبر ، از پیش ناشناخته قابل فهم و قابل اعتماد از پایگاه داده های بزرگ که شامل بهره گیری از بزارهای آنالیز داده ها، برای کشف الگوهای موجود و روابط ناشناخته‌ی میان داده ها در حجمی وسیع می باشد. و استفاده از آن درتصمیم گیری فعالیتهای تجاری مهم.
• اصطلاح داده کاوی به فرایند نیم خودکار تجزیه و تحلیل پایگاه داده های بزرگ به منظور یافتن الگوهای مفید اطلاق می شود [3].
• داده کاوی یعنی جستجو در یک پایگاه داده ها برای یافتن الگوهایی میان داده ها [4].
• داده کاوی یعنی استخراج دانش کلان ، قابل استناد و جدید از پایگاه داده ها ی بزرگ .
• داده کاوی یعنی تجزیه و تحلیل مجموعه داده های قابل مشاهده برای یافتن روابط مطمئن بین داده ها .

همانگونه که در تعاریف گوناگون داده کاوی مشاهده می شود ، تقریبا در تمامی تعاریف به مفاهیمی چون استخراج دانش ، تحلیل و یافتن الگوی بین داده ها اشاره شده است .

1-3-2- فرآیند داده‌کاوی

می‌توان فرآیند داده‌کاوی را طی مراحل زیر به صورت نمودار نشان داد.

استخراج، ترجمه

و فراخوانی

مهیا کردن داده‌ها

کشف الگو

شکل 1-1فرآیند داده‌کاوی

در فرآیند بالا، داده‌های خام از منابع مختلفی جمع‌آوری می‌شوند و ازطریق استخراج، ترجمه و فرآیندهای بازخوانی به انبار داده‌ها وارد می‌شوند. بخش مهیاسازی، داده‌ها از انبار خارج شده و به صورت یک فرمت مناسب برای داده‌کاوی درمی‌آیند. در بخش کشف الگو از روش‌ها والگوریتم‌های داده‌کاوی، برای ساخت الگو استفاده می‌شود.

1-3-3- قابلیت های داده کاوی

باید توجه داشته باشید که داده کاوی یک ابزار جادویی نیست که بتواند در پایگاه داده شما به دنبال الگوهای جالب بگردد و اگر به الگویی جدیدی برخورد کرد آن را به شما اعلام کند بله صرفا الگوها و روابط بین داده ها را به شما اعلام می کند بدون توجه به ارزش آنها. بنابراین الگوهایی که به این وسیله کشف می شوند باید با جهان واقع تطابق داشته باشند.[5]

1-3-4-چه نوع داده‌هایی مورد کاوش قرار می گیرند؟

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

• · فایلهای ساده (FLAT FILES):

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

• · پایگاههای داده ای رابطه ای(RDBMS):

مختصرا، یک پایگاه داده ی رابطه ای متشکل از مجموعه‌ای از جداول است که در بر گیرنده‌ی مقادیری برای صفات موجودیت ها و یا مقادیری از روابط بین موجودیت ها می‌باشد. هر جدول دارای چندین سطر و ستون می‌باشد که ستونها ارائه کننده‌ی صفات خاصه و سطرها ارائه کننده‌ی رکوردهای اطلاعاتی می‌باشند. یک رکورد اطلاعاتی در بر گیرنده‌ی صفات خاصه‌ی یک شئ یا روایط بین اشیا است که با یک کلید غیر تکراری تعریف می‌شود. الگوریتم های داده‌کاوی برای پایگاه‌های داده‌ای رابطه‌ای بسیار فراگیرتر و سریعتر از الگوریتم های داده‌کاوی روی فایل‌های ساده هستند.

· انبارهای داده ای[7]

وجود اطلاعات صحیح و منسجم یکی از ملزوماتی است که در داده کاوی به آن نیازمندیم. اشتباه و عدم وجود اطلاعات صحیح باعث نتیجه گیری غلط و در نتیجه اخذ تصمیمات ناصحیح در سازمانها می گردد و منتج به نتایج خطرناکی خواهد گردید که نمونه های آن کم نیستند .

اکثر سازمانها دچار یک شکاف اطلاعاتی^[8] هستند. در اینگونه سازمان ها معمولا سیستم های اطلاعاتی در طول زمان و با معماری و مدیریت های گوناگون ساخته شده اند ، به طوری که درسازمان، اطلاعاتی یکپارچه و مشخصی مشاهده نمی گردد . علاوه بر این برای فرایند داده کاوی به اطلاعات خلاصه و مهم در زمینه تصمیم گیری های حیاتی نیازمندیم .

هدف از فرایند انبارش داده ها فراهم کردن یک محیط یکپارچه جهت پردازش اطلاعات است . در این فرایند ، اطلاعات تحلیلی و موجز در دوره های مناسب زمانی سازماندهی و ذخیره می شود تا بتوان از آنها در فرایند های تصمیم گیری که از ملزومات آن داده کاوی است ، استفاده شود . به طور کلی تعریف زیر برای انبار داده ها ارائه می گردد : انبار داده ها ، مجموعه ای است موضوعی^[9] ، مجتمع^[10] ، متغیر در زمان^[11] و پایدار^[12] از داده ها که به منظور پشتیبانی از فرایند مدیریت تصمیم گیری مورد استفاده قرار می گیرد.

1-4- وظایف داده کاوی

وظایف داده کاوی معمولا بشرح زیر است:

• کلاس بندی[13]
• پیش بینی[14]
• خوشه سازی[15]
• تخمین[16]

1-1-4-کلاس بندی

هدف کلاس‌بندی داده‌ها، سازماندهی و تخصیص داده‌ها به کلاس‌های مجزا می‌باشد. در این فرآیند بر اساس داده‌های توزیع شده، مدل اولیه‌ای ایجاد می‌گردد. سپس این مدل برای طبقه‌بندی داده‌های جدید مورد استفاده قرار می‌گیرد، به این ترتیب با بکارگیری مدل بدست آمده، تعلق داده‌های جدید به کلاس معین قابل تعیین می‌باشد. کلاس‌بندی در مورد مقادیر گسسته و پیشگویی به‌کار می‌رود. [6]

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

در کلاس‌بندی، مدل ایجاد شده بر پایه‌ی یک‌سری داده‌های آموزشی، (اشیا داده‌هایی که بر چسب کلاس آنها مشخص و شناخته شده است) حاصل می آید. مدل بدست آمده در اشکال گوناگون مانند قوانین کلاس‌بندی (If-Then)، درخت‌های تصمیم، فرمول‌های ریاضی و شبکه‌های عصبی قابل نمایش می‌باشد.

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

از کاربردهای کلاس‌بندی می توان بازاریابی، تشخیص بیماری، تحلیل اثرات معالجه، تشخیص خرابی در صنعت و تعیین اعتبار را نام برد. [6]

1-4-2- مراحل یک الگوریتم کلاس‌بندی

الگوی عمومی‌ برای الگوریتم‌های آموزش از طریق مثال با فرایند کلاس‌بندی به سه مرحله تقسیم می‌‌شوند:[2]

• پیش‌پردازش داده‌ها
• ساخت و ارزیابی قوانین کلاس‌بندی و هرس کردن قوانین اضافی که هدف ما می‌باشد.
• کلاس‌بندی نمونه‌های جدید

1-4-3- انواع روش‌های کلاس‌بندی

کلاس‌بندی به روش‌های زیر انجام‌پذیر است:

· طبقه‌بندی بیز

· درخت تصمیم

· K-Nearest Neibour

· الگوریتم‌های ژنتیک

· شبکه‌های عصبی

1-4-3-1- درخت تصمیم

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

شکل1-2: نمونه یک درخت تصمیم

1-احتمال اینکه یک داده معلوم و معین متعلق به کدام دسته، را محاسبه می کند.

2-با اختصاص دادن آنها به دسته ای که احتمالش بیشتر است، رکوردها را دسته بندی می کند.

درخت تصمیم، براساس الگوریتم، ممکن است دو یا تعداد بیشتری شاخه داشته باشد. برای مثال، CART درختانی فقط با دو شاخه در هر نود ایجاد می­کند. هر شاخه منجر به نود تصمیم دیگر یا یک نود برگ می­شود. با پیمایش یک درخت تصمیم از ریشه به پایین به یک نمونه یک طبقه یا مقدار نسبت می­دهیم. هر نود از ویژگی های یک نمونه برای تصمیم­گیری درباره آن انشعاب استفاده می­کند.

درخت­های تصمیمی که برای پیش­بینی متغیرهای دسته­ای استفاده می­شوند، درخت­های classification نامیده می­شوند زیرا نمونه­ها را در دسته­ها یارده­ها یا کلاس ها قرار می­دهند. درخت­های تصمیمی که برای پیش­بینی متغیرهای پیوسته استفاده می­شوند درخت­های regression نامیده می­شوند.

1-4-3-1-1- کشف تقسیمات [17]

هدف از ساختن درخت این است که دستهای را برای یک رکورد برمبنای فیلد هدف تعیین کنیم. درخت بوسیله ی تقسیمات رکوردها بر اساس فیلد ورودی ایجاد می شود. در هر نود تقسیمات (انشعاب) رکوردها بر اساس فیلد ورودی انجام می شود.

اولین کار برای این منظور این است که تعیین کنیم که کدام فیلد ورودی تقسیم بهتری را می سازد. بهترین تقسیم در نتیجه ی یک جداسازی خوب رکوردها به گروه هایی که در این جا یک دسته این گروه ها را در بر می گیرد, کشف می شود.

یک معیار در ارزیابی تقسیم ، خلوص[18] است. یک متد با خلوص بالا، به این معنی است که اعضای آن دسته عالی و ممتازاند.

شکل 1-3: یک تقسیم بندی خوب ، درجه خلوص را برای فرزندان افزایش می دهد.

یک مجموعه از شکل های مثلث و دایره داریم (هدف جداسازی دایره ها از مثلث هاست)اولین تقسیم به دلیل اینکه افزایشی در خلوص نداریم نامرغوب است. (شکل سمت چپ) دومین تقسیم همچنان نامرغوب, چون خلوص کمی افزایش یافته است. سومین تقسیم خوب, چون به فرزندانی با اندازه ی یکسان منجر شده است و (تعداد مثلث و دایره با هم برابر است) خلوص از پدر نسبت به فیلد مورد نظر افزایش یافته است.

درخت تقسیم با دریافت متغیر ورودی (فیلد ورودی) ساخته می شود . معیار خلوص برای آن است که نتیجه ی هر تقسیم بوسیله ی آن متغیر (فیلد) بیان شود بعد از تست متغیرهای ورودی (فیلدها) آن متغیریی که بهترین تقسیم را تولید می کند برای تقسیم اصلی استفاده می شود.

1-4-3-1-2- دسته بندی با درخت تصمیم

هر کس که به بازی بیست سؤالی آشنا باشد براحتی متوجه می شود که درخت تصمیم چگونه رکوردها را دسته بندی می کند. در بازی بیست سؤالی شرکت کننده اول به یک چیز خاص فکر می کند و شرکت کننده دوم باید آن را تشخیص دهد . شرکت کننده اول هیچ راهنمایی را برای تشخیص آن چیز خاص ارائه نمی دهد و شرکت کننده دوم بوسیله یک سری سؤال های بله، خیر سعی می کند که آن چیز را کشف کند.

درخت تصمیم این طوری یک سری از سؤال ها را جواب می دهد . اگر سوال ها مناسب انتخاب شوند یک مجموعه ی کوچک از سؤال ها کافی است تا رکوردها را به دسته های مورد نظر وارد کنیم بازی بیست سؤالی فرایند استفاده از درخت برای افزودن یک رکورد به دسته مربوطه را روشن می کند. هنگامی که یک رکورد وارد ریشه درخت می شود گره ریشه از یک تست استفاده می کند برای این که تعیین کند که کدام فرزندان با آن برخورد کند همه ی گره های میانی به همین طریق عمل می کنند.

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

یک درخت تصمیم یک ساختار سلسله مراتبی می‌باشدکه در آن، گره‌های میانی برای تست یک خصیصه[19] به کار می روند. شاخه‌ها نشانگر خروجی تست بوده، برگ‌ها برچسب کلاس[20] و یا همان طبقه را مشخص می‌نمایند. نکات اساسی برای هر درخت تصمیم به شرح زیر هستند: [10]

• ملاک استفاده شده برای ساخت درخت چه عواملی هستند؟ یعنی کدام متغیر باید برای شکستن انتخاب گردد و این متغیر چگونه باید شکسته شود؟
• ملاک برای متوقف کردن رشد درخت کدام‌ها هستند؟ یعنی چه موقعی باید عمل شاخه شاخه شدن یک نود باید متوقف شود؟
• چگونه باید شاخه‌های درخت بدست آمده هرس شوند تا بیشترین کارایی را در کلاسه‌‌بندی داشته باشیم؟

1-4-3-1-3- انواع درخت‌های تصمیم

درخت‌های تصمیم بر دو نوعند:

• درختان تصمیم دودویی که در هر نود، فقط دو شاخه‌ی انشعابی از آن را داریم، مانند CART.
• درختان تصمیم خطی[21]، که هر نود می‌‌تواند به چند شاخه منشعب شود، مثل CHAID. که اگر ضریب انشعاب دو باشد به درخت تصمیم دودویی تبدیل می‌شود.

1-4-3-1-4- نحوه‌ی هرس کردن درخت

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

تابع g(t) (تابع Strength) رابرای هر نود غیر برگ حساب می‌‌کنیم. سپس می‌‌توان زیر درختی را که دارای کمترین g(t) می‌‌باشد از درخت هرس کرد.

(2.1)

که در آن:

تعداد گره‌های برگ در زیر درخت با ریشه‌ی T = T'

1-4-3-2- نزدیکترین همسایگی_ K [22]

هنگام تلاش برای حل مسائل جدید، افراد معمولا به راه­حل های مسائل مشابه که قبلا حل شده­اند مراجعه می­کنند (K_NN) یک تکنیک دسته­بندی است که از نسخه­ای از این متد استفاده می­کند. در این روش تصمیم­گیری اینکه یک مورد جدید در کدام دسته قرار گیرد با بررسی تعدادی(k) از شبیه­ترین موارد یا همسایه­ها انجام می­شود. تعداد موارد برای هر کلاس یا طبقه شمرده می­شوند، و نمونه یا موارد جدید به دسته­ای که تعداد بیشتری از همسایه­ها به آن تعلق دارند نسبت داده می­شود .

شکل 1-4: محدوده همسایگی (بیستر همسایه ها در دسته X قرار گرفته اند)

اولین مورد برای بکاربردن (K_NN) یافتن معیاری برای فاصله بین صفات در داده­ها و محاسبه آن است. در حالیکه این عمل برای داده­های عددی آسان است، متغیرهای دسته­ای نیاز به برخورد خاصی دارند. هنگامیکه فاصله بین موارد مختلف را توانستیم اندازه گیریم، می­توانیم از مجموعه مواردی که قبلا دسته­بندی شده­اند را بعنوان پایه دسته­بندی موارد جدید استفاده کنیم، فاصله همسایگی را تعیین کنیم، و تعیین کنیم که خود همسایه­ها را چگونه بشماریم.

(K_NN) بار محاسباتی زیادی را روی کامپیوتر قرار می­دهد زیرا زمان محاسبه بصورت فاکتوریلی از تمام نقاط افزایش می­یابد. درحالیکه بکاربردن درخت تصمیم یا شبکه عصبی برای یک مورد جدید فرایند سریعی است، (K_NN) نیاز به محاسبه جدیدی برای هر مورد جدید دارد. برای افزایش سرعت (K_NN)معمولا تمام داده­ها در حافظه نگهداری می­شوند.

فهم مدل های (K_NN) هنگامیکه تعداد متغیرهای پیش­بینی کننده کم است بسیار ساده است. آنها همچنین برای ساخت مدلهای شامل انواع داده غیر استاندارد هستند، مانند متن بسیار مفیدند. تنها نیاز برای انواع داده جدید وجود معیار مناسب است.[5]

1-4-3-3-بیزی

اهمیت استدلال بیزی داده کاوی را می‌توان به دو دلیل عمده نسبت داد. اول اینکه ، الگوریتم‌های یادگیری بیزی که به طور صریح بر روی احتمالات فرض‌های مختلف کار می‌کنند‌، مانند naive Bayes classifier که از جمله کاراترین وعملی‌ترین الگوریتم‌های ممکن برای برخی مسائل یادگیری می‌باشد. به عنوان مثال Michie (1994) مقایسه کاملی بین این الگوریتم و سایر الگوریتم‌ها مانند درخت تصمیم و شبکه عصبی انجام داده است . این محقق نشان می‌دهد که الگوریتم naive Bayes classifier قابل رقابت با سایر الگوریتم‌ها و در برخی موارد بهتر از آنها عمل می‌کند.

دلیل دوم این است که روش‌های استدلال بیزی چشم انداز مفیدی برای درک عملکرد الگوریتم‌هایی که مستقیماً برروی احتمالات عمل نمی‌کنند ایجاد می‌کند.

از ویژگیهای یادگیری بیز می‌توان موارد زیر را نام برد :

• هر نمونه آموزشی جدید که مشاهده می‌شود می‌تواند احتمال درستی یک فرض را افزایش یا کاهش دهد . به این خاطر از روش‌هایی که بدلیل ناسازگاری یک نمونه فرض را کلاً حذف می کنند منعطف‌تر می‌باشد .

• دانش پیشین به وسیله (1 در نظر گرفتن احتمال هر فرض و (2 انتساب یک توزیع احتمال برای مشاهدات ، ساخته می‌شود . دانش پیشین می‌تواند با مشاهدات ترکیب شده تا دانش جدید یا به عبارت دیگر احتمال درستی فرضیات را به وجود آورد.

• روش‌های بیزی می‌توانند از فرض‌هایی که احتمال را پیش بینی می‌کنند بهره گیرند (به عنوان مثال « این مریض به احتمال 93% شانس بهبودی کامل را دارد »)

• نمونه‌های جدید می‌تواند با استفاده از ترکیب وزنی نمونه‌های قبل متناسب با احتمال آنها تولید شوند .

• حتی در مواردی که روش‌های بیزی از لحاظ پیچیدگی محاسبات غیر قابل استفاده باشند می‌توان ازآنها به عنوان بهترین روش (gold standard) برای مقایسه سایر روش ها استفاده کرد.

یک مشکل عملی در استفاده از روش‌های بیزی این است که آنها عموماً نیاز به دانستن احتمالات پیشین بسیاری دارند . وقتی این احتمالات از قبل معلوم نباشد آنها بر اساس داده‌های موجود ، توزیع احتمالی که بر روی فرض‌ها وجود دارد تخمین زده می‌شود. یک مشکل دیگر که در عمل به وجود می‌آید، هزینه محاسباتی زیاد هنگام محاسبه بهترین فرض بیزی در حالت عمومی است (هزینه محاسبات به طور خطی با تعداد فرض‌ها افزایش می‌یابد، یا به طور نمایی با تعداد متغیرها) . در موارد خاص این هزینه محاسبات می‌تواند به شدت کاهش یابد .

1-4-3-3-1 تئوری بیز

در بسیاری از موارد به دنبال پیدا کردن بهترین فرض در فضای مفروضات H، با در اختیار داشتن داده‌های آموزشی D هستیم . یک روش برای بیان بهترین فرض این است که بگوییم ما به دنبال محتمل‌ترین فرض، با داشتن داده D به علاوه دانش اولیه در مورد احتمالات پیشین فرض‌های H، هستیم. قضیه بیز روش مستقیمی برای محاسبه این احتمالات فراهم می‌آورد.برای تعریف قضیه بیز ابتدا کمی نماد گذاری لازم است.

ما از P(h) برای بیان احتمال اولیه‌ای که فرض h درست است استفاده می‌کنیم، پیش از آنکه داده‌های آموزشی را دیده باشیم. P(h) را عموماً احتمال پیشین می‌نامند و بیانگر هر دانش پیشینی می‌باشد که در مورد شانس درستی فرض h سخن می‌گوید . اگر هیچ دانش اولیه‌ای از مفروضات نداشته باشیم می‌توانیم یک احتمال یکسان به کل فضای مفروضات H اختصاص دهیم . به طور مشابه از P(D) برای بیان احتمال پیشین که داده‌های D مشاهده می‌شوند استفاده می‌کنیم. همچنین از P(D|h) برای بیان احتمال D در دنیایی که فرض h صادق است استفاده می‌کنیم . در یادگیری ماشین ما به دنبال P(h|D) هستیم ، یعنی احتمال درستی فرض h به شرط مشاهده داده‌های آموزشی D . P(h|D) احتمال پسین h نام دارد ، بدین علت که بیانگر اطمینان ما از فرض h پس از مشاهده داده‌های D می‌باشد .

قضیه بیز اصلی‌ترین سنگ بنای یادگیری بیزی می‌باشد، زیرا روشی برای محاسبه احتمال پسین P(h|D) را از احتمال پیشین P(h) به همراه P(D) و P(D|h) فراهم می‌آورد.

همانطور که انتظار می‌رود ، می‌توان مشاهده کرد که P(h|D) با افزایش P(h) و همچنین P(D|h) افزایش می‌یابد . به همین ترتیب منطقی به نظر می‌رسد که P(D|h) با افزایش P(D) کاهش یابد ، زیرا با افزایش احتمال وقوع P(D) که مستقل از h می‌باشد ، شواهد کمتری در D برای پشتیبانی از h وجود خواهد داشت .

در بسیاری از سناریوهای یادگیری، یادگیرنده مجموعه‌ای از فرض‌ها H را در نظر می‌گیرد وعلاقمند به یافتن فرضی می‌باشد که محتمل‌ترین باشد (یا حداقل یکی از محتمل‌ترین مفروضات اگر چندتا وجود داشته باشد) . هر فرضی که دارای این خصوصیت باشد به فرض (MAP) Maximum a posteriori نام دارد. می‌توان فرض MAP را با استفاده از قضیه بیز برای محاسبه احتمال پسین هر کاندیدا بیابیم .

توجه کنید که در مرحله آخر بالا P(D) را حذف کردیم زیرا محاسبه آن مستقل از h می‌باشد و همیشه یک عدد ثابت است. در برخی موارد، فرض می‌کنیم که تمام مفروضات احتمال وقوع یکسانی دارند (یعنی ). دراین صورت یک ساده سازی دیگر نیز در فرمول (4.1) می‌توان انجام داد . به عبارت دیگر می‌توان فرضی را که P(D|h) را ماکزیمم می‌کند در نظر گرفت (Maximum Likelihood) .

در اینجا، از داده‌های D به عنوان نمونه‌های آموزشی برای یک تابع هدف و از H به عنوان مجموعه‌ای از توابع هدف ممکن یاد می‌کنیم. اما در حقیقت قضیه بیز کلی‌تر از این بحث است . یعنی می‌توان آن را به گونه‌ای مشابه برای مجموعه‌ای از هر نوع مفروضات دو به دو مستقل از هم که مجموع احتمالات آنها یک می‌شود استفاده کرد.

1-4-3-3-2 -دسته بندی ساده بیزی

یک روش یادگیری بیزی، روش یادگیرنده ساده بیزی می‌باشد که عموماً روش طبقه‌بندی ساده بیزی نامیده می‌شود. در برخی زمینه‌ها نشان داده شده است که کارایی آن قابل قیاس با کارایی روش‌هایی مانند شبکه عصبی و درخت تصمیم می‌باشد. این بخش، روش طبقه بندی ساده بیزی را معرفی می‌کند .

طبقه‌بندی ساده بیزی برای مسائلی که هر نمونه x درآن توسط مجموعه‌ای از مقادیر صفات و تابع هدف f(x) از مجموعه‌ای مانند V انتخاب می‌گردد کاربرد دارد . مجموعه‌ای از داده‌های آموزشی و خروجی تابع هدف و یا طبقه‌ای که نمونه جدید به آن تعلق دارد مورد نظر است. روش بیزی برای طبقه‌بندی نمونه جدید این است که محتمل‌ترین طبقه یا مقدار هدف v_MAP را با داشتن مقادیر صفات که توصیف کننده نمونه جدید است شناسایی کند

با استفاده از قضیه بیز می‌توان عبارت (5.1) را به صورت زیر بازنویسی کرد،

حال با استفاده از داده‌های آموزشی سعی می‌کنیم دو جمله معادله (6.1)را تخمین بزنیم . محاسبه از روی داده‌های آموزشی به این صورت که میزان تکرار v_j در داده‌ها چقدر است، آسان می‌باشد. اما محاسبه جملات مختلف به این صورت قابل قبول نخواهد بود مگر اینکه حجم بسیار بسیار زیادی از داده‌های آموزشی در اختیار داشته باشیم . مشکل اینجاست که تعداد این جملات برابر تعداد نمونه‌های ممکن ضرب در تعداد مقادیر تابع هدف می‌باشد. بنابراین باید هر نمونه را چندین بار مشاهده کنیم تا تخمین مناسبی از آن بدست آید . فرض روش طبقه‌بندی ساده بیزی بر اساس این ساده سازی است که مقادیر صفات با داشتن مقادیر تابع هدف از یکدیگر مستقل شرطی می‌باشند. به عبارت دیگر، این فرض بیانگر این است که به شرط مشاهده خروجی تابع هدف احتمال مشاهده صفات برابر ضرب احتمالات هر صفت به طور جداگانه می‌باشد اگر این را جایگزین معادله (6.1) کنیم روش طبقه‌بندی ساده بیزی را نتیجه می‌دهد،

دستیابی به کیفیت سرویس در شبکه های حسگر بیسیم با استفاده از آتوماتاهای یادگیر سلولی

فهرست مطالب:

چکیده 8

1- مقدمه 9

1-1- شبکه های حسگر بی سیم. 9

1-1-1- مسائل مطرح در شبکه های حسگر بی سیم. 12

1-1-2- پوشش محیط در شبکه های حسگر بی سیم. 14

1-1-3- خوشه بندی در شبکه های حسگر بی سیم. 15

1-1-4- تجمیع داده ها در شبکه های حسگر. 16

1-2- کیفیت سرویس در شبکه های حسگر بی سیم. 17

1-2-1- کیفیت سرویس در شبکه های داده ای سنتی.. 19

1-2-2- کیفیت سرویس در شبکه های حسگر بی سیم. 21

1-3- آتوماتای یادگیر. 24

1-3-1- آتوماتای یادگیر. 26

1-3-2- معیار‌های رفتار اتوماتای یادگیر. 29

1-3-3- الگوریتمهای یادگیری.. 30

1-3-4- آتوماتای یادگیر با عملهای متغیر. 34

1-4- آتوماتای یادگیر سلولی.. 35

1-4-1- آتوماتای سلولی 35

1-4-2- آتوماتای یادگیر سلولی (CLA) 39

1-5- اهداف پایان نامه و ساختار آن. 42

2- پوشش محیط در شبکه های حسگر بی سیم با استفاده از آتوماتاهای یادگیرسلولی 44

2-1- مقدمه 44

2-1-1- اشکال مختلف طراحی.. 45

2-2- دسته بندی مسائل پوشش در شبکه های حسگر. 46

2-2-1- پوشش ناحیه ای 47

2-2-2- پوشش نقطه ای 50

2-2-3- پوشش مرزی 51

2-3- روش پوشش CCP. 53

2-3-1- فرضیات مسئله 53

2-3-2- تشریح روش 53

2-4- حل مسئله پوشش(k-پوششی ) با استفاده از آتوماتاهای یادگیر. 55

2-4-1- فرضیات و مدل مسئله. 57

2-4-2- روش تشخیص افزونه بودن نود حسگر. 58

2-4-3- شبیه سازی 68

2-5- جمع بندی 75

3- خوشه بندی در شبکه های حسگر بی سیم با استفاده از آتوماتاهای یادگیر سلولی 76

3-1- مقدمه 76

3-2- کارهای انجام شده 80

3-2-1- پروتکل خوشه بندی LEACH.. 81

3-2-2- پروتکل خوشه بندی HEED.. 84

3-3- خوشه بندی در شبکه های حسگر بی سیم با استفاده از آتوماتاهای یادگیر. 89

3-3-1- روش خوشه بندی پیشنهادی.. 90

3-3-2- شبیه سازی 98

3-4- جمع بندی 103

4- تجمیع داده ها در شبکه های حسگر با استفاده از آتوماتاهای یادگیر سلولی 104

4-1- مقدمه 104

4-2- کارهای انجام گرفته. 105

4-3- تجمیع داده ها در شبکه های حسگر با استفاده از اتوماتاهای یادگیر. 108

4-3-1- بیان مسئله و مفروضات آن. 109

4-3-2- تشریح روش پیشنهادی.. 111

4-4- شبیه سازی 115

4-4-1- ازمایش اول 118

4-4-2- ازمایش دوم 118

4-5- جمع بندی 119

5- نتیجه گیری.. 120

6- پیوست الف: شبکه های حسگر بی سیم. 121

6-1- تاریخچه شبکه های حسگر. 121

6-2- ساختار هر گره حسگر. 122

6-2-1- اجزاء درونی یک گره حسگر. 122

6-2-2- محدودیتهای سخت افزاری یک گره حسگر. 124

6-3- پشته پروتکلی 125

6-4- مزایای شبکه های حسگر بیسیم. 126

6-5- کاربردهای شبکه های حسگر بیسیم. 128

7- پیوست ب:آتوماتای یادگیرسلولی.. 132

7-1- تاریخچه آتوماتای یادگیر. 132

7-2- معیار‌های رفتار اتوماتای یادگیر. 133

7-3- آتوماتای یادگیر با عملهای متغیر. 135

7-4- آتوماتای یادگیر تعقیبی.. 136

7-5- آتوماتای یادگیر سلولی (CLA) 145

7-6- آتوماتای یادگیر سلولی باز(OCLA) 148

7-7- آتوماتای یادگیر سلولی ناهمگام (ACLA) 149

8- پیوست ج: شرح نرم افزار jsim و پیاده سازی الگوریتمهای پیشنهادی با آن 151

8-1- مقدمه 151

8-2- شبیه ساز jsim 152

8-3- پیاده سازی الگوریتم خوشه بندی پیشنهادی.. 153

8-4- پیاده سازی الگوریتم پوشش پیشنهادی.. 175

مراجع. 180

فهرست شکلها:

شکل ‏3‑1) یک مدل ساده از QoS. 18

شکل ‏2‑1) اتوماتای یادگیر تصادفی.. 28

شکل ‏2‑9) (الف) همسایگی مور – (ب) همسایگی ون نیومن برای اتوماتای سلولی.. 37

شکل ‏2‑10) قانون 54. 42

شکل ‏4‑1) پوشش ناحیه ای.. 48

شکل ‏4‑2)پوشش نقطه ای.. 51

شکل ‏4‑3) پوشش مرزی.. 52

شکل ‏4‑4) نود حسگر موقعیت خود و همسایگانش را می داند. 59

شکل ‏4‑5) مربع گریدی دربرگیرنده دیسک حسگری نود حسگر. 59

شکل ‏4‑7) تعدادی از نقاط مربع گریدی افزونه بوده و درون دیسک حسگری قرار نمی گیرند. 61

شکل ‏4‑8) انتخاب شکل گرید به صورت شعاعی و بر روی دوایر متحدالمرکز. 61

شکل ‏4‑9) محاسبه مکان نقاط گرید بر روی دیسک حسگری با تغییر زاویه و شعاع. 62

شکل ‏4‑10) انتخاب نقاط گرید با فواصل یکسان و بدون افزونگی.. 62

شکل ‏4‑11) ترتیب بررسی نقاط گرید در یک مثال نمونه با f =3. 63

شکل ‏4‑12) تعیین اندازه گرید به صورت مناسب... 65

شکل ‏5‑1) ارتباطات تک گامی و چندگامی بدون خوشه بندی.. 77

شکل ‏5‑2)ارتباطات تک گامی و چندگامی با استفاده از خوشه بندی.. 78

شکل ‏5‑3) شبه کد الگوریتم HEED.. 89

شکل ‏2‑2) پارامترهای الگوریتم تعقیبی پیوسته CP_RP 138

شکل ‏2‑3) الگوریتم تعقیبی پیوسته CP_RP 139

شکل ‏2‑4) پارامترهای الگوریتم تعقیبی گسسته DP_RI 140

شکل ‏2‑5) الگوریتم تعقیبی گسسته DP_RI 141

شکل ‏2‑6) پارامترهای الگوریتم تعقیبی پیوسته CP_RI 142

شکل ‏2‑7) الگوریتم تعقیبی پیوسته CP_RI 143

شکل ‏2‑8) الگوریتم تعقیبی گسسته DP_RP 144

شکل ‏2‑10) قانون 54. 148

شکل ‏2‑11) اتصال یک سلول نوعی با انواع محیطها و OCLA.. 148

چکیده:

یک شبکه حسگر بی سیم از تعداد زیادی از نودهای حسگر در یک ناحیه خاص تشکیل شده است که هر یک از آنها توانایی جمع آوری اطلاعات ازمحیط را دارا می باشد و داده های جمع آوری شده را به نود سینک ارسال می کند. هر چند که به طور کلی راجع به شبکه های حسگر بی سیم تحقیقات زیادی صورت گرفته است، در مورد کیفیت سرویس در این شبکه ها هنوز به اندازه کافی کار نشده است. کیفیت سرویس در شبکه های حسگر بی سیم نسبت به شبکه های سنتی بسیار متفاوت است. از آنجایی که زمینه کاربرد این شبکه ها بسیار وسیع می باشد، پارامترهای کیفیت سرویس درآنها متفاوت است. بعضی از پارامترهایی که در ارزیابی کیفیت سرویس مورد استفاده قرار می گیرند عبارتند از: پوشش شبکه, تعداد بهینه نودهای فعال در شبکه, طول عمر شبکه و میزان مصرف انرژی.

تکنیکی که ما جهت بهبود پارامترهای کیفیت سرویس در شبکه ها ی حسگر مورد استفاده قرار داده ایم, روش هوشمند اتوماتاهای یادگیر سلولی(CLA) می باشد. اتوماتای یادگیر سلولی یک رهیافت مکاشفه‌ای برای حل مسایل بهینه‌سازی پیچیده می‌باشد که بررسی‌های اخیر برروی آن، کارایی مناسب آن را به عنوان تکنیکی برای حل این‌گونه مسائل نشان داده است.

در این پروژه تعدادی از مسائل اساسی شبکه ها ی حسگر بی سیم مطرح گردیده و با هدف بهبود پارامترهای کیفیت سرویس این مسائل با استفاده از آتوماتاهای یادگیرسلولی حل گردیده اند.

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

یک شبکه حسگر بی سیم از تعداد زیادی از نودهای حسگر در یک ناحیه خاص تشکیل شده است که هر یک از آنها توانایی جمع آوری اطلاعات ازمحیط را دارا می باشد و داده های جمع آوری شده را به نود سینک ارسال می کند. هر چند که به طور کلی راجع به شبکه های حسگر بی سیم تحقیقات زیادی صورت گرفته است، در مورد کیفیت سرویس در این شبکه ها هنوز به اندازه کافی کار نشده است. کیفیت سرویس در شبکه های حسگر بی سیم نسبت به شبکه های سنتی بسیار متفاوت است. از آنجایی که زمینه کاربرد این شبکه ها بسیار وسیع می باشد، پارامترهای کیفیت سرویس درآنها متفاوت است. بعضی از پارامترهایی که در ارزیابی کیفیت سرویس مورد استفاده قرار می گیرند عبارتند از: پوشش شبکه, تعداد بهینه نودهای فعال در شبکه, طول عمر شبکه و میزان مصرف انرژی.

تکنیکی که ما جهت بهبود پارامترهای کیفیت سرویس در شبکه ها ی حسگر مورد استفاده قرار داده ایم, روش هوشمند اتوماتاهای یادگیر سلولی(CLA) می باشد. اتوماتای یادگیر سلولی یک رهیافت مکاشفه‌ای برای حل مسایل بهینه‌سازی پیچیده می‌باشد که بررسی‌های اخیر برروی آن، کارایی مناسب آن را به عنوان تکنیکی برای حل این‌گونه مسائل نشان داده است.

در این پایان نامه تعدادی از مسائل اساسی شبکه ها ی حسگر بی سیم مطرح گردیده و با هدف بهبود پارامترهای کیفیت سرویس این مسائل با استفاده از آتوماتاهای یادگیرسلولی حل گردیده اند.

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

کلمات کلیدی: کیفیت سرویس، شبکه های حسگر بی سیم، پوشش، خوشه بندی، تجمیع داده ها، آتوماتای یادگیر

فهرست مطالب

چکیده 8

1- مقدمه 9

1-1- شبکه های حسگر بی سیم 9

1-1-1- مسائل مطرح در شبکه های حسگر بی سیم 12

1-1-2- پوشش محیط در شبکه های حسگر بی سیم 14

1-1-3- خوشه بندی در شبکه های حسگر بی سیم 15

1-1-4- تجمیع داده ها در شبکه های حسگر 16

1-2- کیفیت سرویس در شبکه های حسگر بی سیم 17

1-2-1- کیفیت سرویس در شبکه های داده ای سنتی 19

1-2-2- کیفیت سرویس در شبکه های حسگر بی سیم 21

1-3- آتوماتای یادگیر 24

1-3-1- آتوماتای یادگیر 26

1-3-2- معیار‌های رفتار اتوماتای یادگیر 29

1-3-3- الگوریتمهای یادگیری 30

1-3-4- آتوماتای یادگیر با عملهای متغیر 34

1-4- آتوماتای یادگیر سلولی 35

1-4-1- آتوماتای سلولی 35

1-4-2- آتوماتای یادگیر سلولی (CLA) 39

1-5- اهداف پایان نامه و ساختار آن 42

2- پوشش محیط در شبکه های حسگر بی سیم با استفاده از آتوماتاهای یادگیرسلولی 44

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

2-1-1- اشکال مختلف طراحی 45

2-2- دسته بندی مسائل پوشش در شبکه های حسگر 46

2-2-1- پوشش ناحیه ای 47

2-2-2- پوشش نقطه ای 50

2-2-3- پوشش مرزی................................ ................................ 51

2-3- روش پوشش CCP 53

2-3-1- فرضیات مسئله 53

2-3-2- تشریح روش................................ ................................ 53

2-4- حل مسئله پوشش(k-پوششی ) با استفاده از آتوماتاهای یادگیر 55

2-4-1- فرضیات و مدل مسئله 57

2-4-2- روش تشخیص افزونه بودن نود حسگر 58

2-4-3- شبیه سازی................................ ................................ 68

2-5- جمع بندی............................... ............................... 75

3- خوشه بندی در شبکه های حسگر بی سیم با استفاده از آتوماتاهای یادگیر سلولی 76

3-1- مقدمه.................................. .................................. 76

3-2- کارهای انجام شده 80

3-2-1- پروتکل خوشه بندی LEACH 81

3-2-2- پروتکل خوشه بندی HEED 84

3-3- خوشه بندی در شبکه های حسگر بی سیم با استفاده از آتوماتاهای یادگیر 89

3-3-1- روش خوشه بندی پیشنهادی 90

3-3-2- شبیه سازی................................ ................................ 98

3-4- جمع بندی............................... ............................... 103

4- تجمیع داده ها در شبکه های حسگر با استفاده از آتوماتاهای یادگیر سلولی................... ................... 104

4-1- مقدمه.................................. .................................. 104

4-2- کارهای انجام گرفته 105

4-3- تجمیع داده ها در شبکه های حسگر با استفاده از اتوماتاهای یادگیر 108

4-3-1- بیان مسئله و مفروضات آن 109

4-3-2- تشریح روش پیشنهادی 111

4-4- شبیه سازی.............................. .............................. 115

4-4-1- ازمایش اول............................... ............................... 118

4-4-2- ازمایش دوم............................... ............................... 118

4-5- جمع بندی............................... ............................... 119

5- نتیجه گیری 120

6- پیوست الف: شبکه های حسگر بی سیم 121

6-1- تاریخچه شبکه های حسگر 121

6-2- ساختار هر گره حسگر 122

6-2-1- اجزاء درونی یک گره حسگر 122

6-2-2- محدودیتهای سخت افزاری یک گره حسگر 124

6-3- پشته پروتکلی 125

6-4- مزایای شبکه های حسگر بیسیم 126

6-5- کاربردهای شبکه های حسگر بیسیم 128

7- پیوست ب:آتوماتای یادگیرسلولی 132

7-1- تاریخچه آتوماتای یادگیر 132

7-2- معیار‌های رفتار اتوماتای یادگیر 133

7-3- آتوماتای یادگیر با عملهای متغیر 135

7-4- آتوماتای یادگیر تعقیبی 136

7-5- آتوماتای یادگیر سلولی (CLA) 145

7-6- آتوماتای یادگیر سلولی باز(OCLA) 148

7-7- آتوماتای یادگیر سلولی ناهمگام (ACLA) 149

8- پیوست ج: شرح نرم افزار jsim و پیاده سازی الگوریتمهای پیشنهادی با آن 151

8-1- مقدمه.................................. .................................. 151

8-2- شبیه ساز jsim 152

8-3- پیاده سازی الگوریتم خوشه بندی پیشنهادی 153

8-4- پیاده سازی الگوریتم پوشش پیشنهادی 175

مراجع 180

فهرست شکلها

شکل ‏3‑1) یک مدل ساده از QoS 18

شکل ‏2‑1) اتوماتای یادگیر تصادفی 28

شکل ‏2‑9) (الف) همسایگی مور – (ب) همسایگی ون نیومن برای اتوماتای سلولی 37

شکل ‏2‑10) قانون 54 42

شکل ‏4‑1) پوشش ناحیه ای 48

شکل ‏4‑2)پوشش نقطه ای 51

شکل ‏4‑3) پوشش مرزی 52

شکل ‏4‑4) نود حسگر موقعیت خود و همسایگانش را می داند 59

شکل ‏4‑5) مربع گریدی دربرگیرنده دیسک حسگری نود حسگر 59

شکل ‏4‑7) تعدادی از نقاط مربع گریدی افزونه بوده و درون دیسک حسگری قرار نمی گیرند 61

شکل ‏4‑8) انتخاب شکل گرید به صورت شعاعی و بر روی دوایر متحدالمرکز 61

شکل ‏4‑9) محاسبه مکان نقاط گرید بر روی دیسک حسگری با تغییر زاویه و شعاع 62

شکل ‏4‑10) انتخاب نقاط گرید با فواصل یکسان و بدون افزونگی 62

شکل ‏4‑11) ترتیب بررسی نقاط گرید در یک مثال نمونه با f =3 63

شکل ‏4‑12) تعیین اندازه گرید به صورت مناسب 65

شکل ‏5‑1) ارتباطات تک گامی و چندگامی بدون خوشه بندی 77

شکل ‏5‑2)ارتباطات تک گامی و چندگامی با استفاده از خوشه بندی 78

شکل ‏5‑3) شبه کد الگوریتم HEED 89

شکل ‏2‑2) پارامترهای الگوریتم تعقیبی پیوسته CP_RP 138

شکل ‏2‑3) الگوریتم تعقیبی پیوسته CP_RP 139

شکل ‏2‑4) پارامترهای الگوریتم تعقیبی گسسته DP_RI 140

شکل ‏2‑5) الگوریتم تعقیبی گسسته DP_RI 141

شکل ‏2‑6) پارامترهای الگوریتم تعقیبی پیوسته CP_RI 142

شکل ‏2‑7) الگوریتم تعقیبی پیوسته CP_RI 143

شکل ‏2‑8) الگوریتم تعقیبی گسسته DP_RP 144

شکل ‏2‑10) قانون 54 148

شکل ‏2‑11) اتصال یک سلول نوعی با انواع محیطها و OCLA 148