پروژه بررسی الگو ریتم های خوشه بندی تجمیعی

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

پروژه بصورت فایل قابل ویرایش ورد(WORD) در 69 صفحه برای رشته کامپیوتر در پایین همین صفحه قابل دانلود میباشد. شایسته یادآوری است که پروژه از ابتدا تا آخر ویرایش وتنظیم , سکشن بندی (section) ، نوشتن پاورقی (Footnote) و فهرست گذاری کامل شده وآماده تحویل است.

چکیده

ازخوشه بندی درحوزه داده کاوی برای تحلیل ، گروه بندی یا طبقه بندی داده ها درخوشه هایی که اعضای ان ها خواص کمابیش یکسانی دارند ، استفاده می شود . خوشه بندی کاربردهای متعددی از تشخیص الگو ، روان شناﺴﻰ ، اقتصاد تا طبقه بندی ژنی ، پردازش تصویر و ... دارد . دراین پروژه چند الگوریتم خوشه بندی نسبتاً ساده ، کارامد و متداول که درخوشه بندی داده ها به کار می روند مورد بررسی قرارمی گیرند . فصل اول به مفاهیم و کلیات داده کاوی و خوشه بندی اختصاص دارد . در فصل دوم ابتدا مختصری در مورد خوشه بندی سلسله مراتبی و در ادامه انواع الگوریتم های خوشه بندی سلسله مراتبی تجمیعی توضیح داده شده است ( با این وصف که معادلات ومبحث های ریاضی الگوریتم ها مطرح نشده وصرفاً روی خود الگوریتم ها تأکید شده ) . درفصل اخرهم توضیحی کوتاه درباره نرم افزارMat lab داده شده و یک نمونه ازالگوریتم های فصل دوم با زبان برنامه نویسی Mat lab شبیه سازی شده است

واژه های کلیدی: 

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

فهرست مطالب

مقدمه. 1

فصل اول

کلیات

1-1 داده کاوی.. 4

1-1-1 تاریخچه داده کاوی.. 5

1-1-2 داده کاوی چیست ؟. 5

3-1-1 فرایند داده ‌کاوی.. 7

1-1-4 ویژگی های داده کاوی.. 8

1-1-5 مزایای داده کاوی.. 8

1-1-6 مراحل داده کاوی.. 9

1-1-7 روش های داده کاوی.. 10

1-1-8 الگوریتم های داده کاوی.. 11

1-1-9 ابزارهای داده کاوی.. 12

1-1- 9-1 قابلیت‌های ابزار‌های داده کاوی.. 12

1-1-9-2 نرم افزارهای داده کاوی.. 15

1-1-10 کاربردهای داده کاوی.. 16

1-1-11 شاخه های مرتبط با داده کاوی.. 16

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

1-2-1 تاریخچه خوشه بندی.. 21

1-2-2 تعریف خوشه بندی.. 22

1-2-3 تحلیل خوشه بندی.. 23

1-2-4 مراحل خوشه بندی.. 28

1-2-5 فرایندهای خوشه بندی.. 29

1-2-6 کاربردهای خوشه بندی.. 31

1-2-7 مطالعه تکنیک های خوشه بندی.. 34 

فصل دوم

الگوریتم های خوشه بندی سلسله مراتبی – تجمیعی

2-1 خوشه بندی سلسله مراتبی.. 37

2-2 خوشه بندی سلسله مراتبی تجمیعی.. 38

2-2-1 پیوند خوشه بندی.. 40

2-2-3 الگوریتم پیوند کامل.. 41

2-2-4 الگوریتم پیوند میانگین گروهی.. 41

2-2-5 الگوریتم پیوند میانگین وزن دار. 41

2-2-6 الگوریتم پیوند مرکزی.. 41

2-2-7 الگوریتم پیوند میانی.. 42

2-2-8 روش وارد. 42

2-3 پیشرفت اخیر. 42

2-3-1 الگوریتم BIRCH.. 43

2-3-2 الگوریتم CURE.. 46

2-3-3 الگوریتم ROCK.. 48

2-3-4 الگوریتم CHAMELEON.. 49

2-3-5 الگوریتم SLINK.. 50

2-3-6 الگوریتم های پیوند تک مبتنی بردرختان پوشای مینیمم.. 51

2-3-7 الگوریتم CLINK.. 52

2-4 روش های دیگر خوشه بندی سلسله مراتبی.. 52

فصل سوم

شبیه سازی و اجرای یک نمونه الگوریتم کاربردی

3-1 نرم افزار MATLAB.. 54

3-2 اجرای برنامه کاربردی با Matlab. 55

3-2-1 تحلیل برنامه CLINK.. 55

3-3 خلاصه و نتیجه گیری.. 56

منابع و ماخذ. 61

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

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

شکل 1-2 مراحل داده کاوی.. 9

شکل 1-3 وظایف داده کاوی.. 19

شکل 1-4 رویه خوشه بندی.. 23

شکل 1-5 فلوچارت نمونه اعتبار برای ساختارهای خوشه بندی.. 28

شکل 1-6 فرایندهای خوشه بندی داده. 30

شکل 1-7 نمودار الگوریتم های خوشه بندی.. 30

شکل 2-1 نمونه ای از نموداردرختی خوشه بندی سلسله مراتبی.. 38

شکل 2-2 رایج ترین روش های سلسله مراتبی.. 39

شکل 2-3 فلوچارت الگوریتم خوشه بندی سلسله مراتبی تجمیعی.. 39

شکل 2-4 فلوچارت الگوریتم BIRCH.. 45

شکل 2-5 فلوچارت الگوریتم CURE.. 47

شکل 2-6 فلوچارت الگوریتم Chameleon. 50

جدول 1-3 دستورات مدیریت فایل.. 54

جدول 2-3 دستورات مدیریت فضای کاری.. 55

پروژه مطالعه الگوریتم های خوشه بندی شبکه های حسگر بی سیم

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

پروژه بصورت فایل قابل ویرایش ورد(WORD) در 75 صفحه برای رشته کامپیوتر و IT در پایین همین صفحه قابل دانلود میباشد. شایسته یادآوری است که پروژه از ابتدا تا پایان ویرایش وتنظیم , سکشن بندی (section) ، نوشتن پاورقی (Footnote) و فهرست گذاری اتوماتیک کامل شده وآماده تحویل یا کپی برداری از مطالب مفید آن است.

چکیده

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

واژه های کلیدی: شبکه‌های حسگر بی‌سیم، خوشه‌بندی، سرخوشه، تعادل انرژی، عمرشبکه ، طراحی الگوریتم ، شبکه

فهرست مطالب

فصل اول  مقدمه

1-1 مقدمه. 2

1-2 تاریخچه. 2

1-3 انگیزه و تعریف مساله. 3

فصل دوم  شبکه‌های حسگر بی‌سیم

2-1 مقدمه. 6

2-2 کاربرد شبکه‌های حسگر بی‌سیم.. 6

2-3 ساختار گره حسگر بی‌سیم.. 7

2-4 ساختار شبکه‌های حسگر بی‌سیم.. 8

2-5 چالش‌های پیش رو در شبکه‌های حسگر بی‌سیم.. 9

2-6 روشها و عوامل موثر در کاهش مصرف انرژی.. 10

2-6-1انواع روشهای کاهش مصرف انرژی.. 10

2-7 موضوعات موثر در عملکرد شبکه‌های حسگر بی‌سیم.. 11

2-7-1پویایی شبکه. 11

2-7-2توسعه گره. 12

2-7-3 ملاحظات انرژی.. 12

2-7-4مدلهای تحویل داده. 12

2-7-5توانمندی های گره. 12

2-7-6تجمیع / ترکیب داده. 13

2-7-7 ناهمگن بودن گره / لینک... 13

2-7-8تحمل پذیری خطا13

2-7-9درجه اتصال.. 13

2-7-10پوشش.... 14

2-7-10-1 تقسیم بندی اول.. 14

2-7-10-1-1تقسیم بندی دوم. 15

2-7-11کیفیت سرویس.... 17

2-7-12هزینه تولید. 17

2-7-13محدودیتهای سخت افزاری.. 17

2-8 پروتکل های ارتباطی در شبکه‌های حسگر بی سیم.. 17

2-9مسیریابی.. 19

فصل سوم  مروری بر کارهای مرتبط و پیشرفت‌های اخیر

3-1مقدمه. 25

3-2شبکه‌های مسطح.. 25

3-2-2کنترل تعداد همسایگان.. 26

3-2-3چند پروتکل معروف در شبکه‌های مسطح.. 27

3-2-3-1گراف همسایگی نسبی.. 27

3-2-3-2 گراف گابریل.. 27

3-2-3-3ﻣﺜﻠﺚ ﺑﻨﺪﯼ ﺩﻻﻧﯽ.. 28

3-2-3-4کوچکترین درخت فراگیر محلی 29

3-2-3-5الگوریتم ناحیه رله و دربرگیری.. 30

3-2-4الگوریتم کنترل توپولوژی مبتنی بر مخروط 31

3-2-4-1-1 پروتکل KNEIGH.. 32

3-3شبکه‌های سلسله مراتبی با مجموعه‌های غالب... 32

3-3-1چند الگوریتم از مدلهای ارائه شده در الگوریتم‌های متمرکز. 33

3-3-1-1-1 ساخت مجموعه غالب با استفاده از درخت پوشا33

3-3-1-2 متصل کردن مولفه‌های جدا - یافتن مجموعه غالب غیر متصل.. 35

3-3-1-3 اطمینان از متصل شدن با استفاده از درخت اشتاینر. 36

3-3-1-4متصل کردن یک مجموعه غالب... 36

3-3-1-5دو ابتکار کوچک سازی مجموعه‌های غالب... 37

3-3-1-6ابتکار حذف شاخ وبرگ اضافی مبتنی بر موقعیت و درجه. 38

3-3-1-7 Span. 38

3-3-1-3خود سازماندهی سلسله مراتبی مبتنی بر نقش.... 39

3-4 شبکه‌های سلسله مراتبی خوشه‌ای.. 39

3-4-1 قانون کلی در ایجاد خوشه‌های مستقل.. 44

3-4-2ملاحظات عملکردی در مورد خوشه‌بندی.. 46

3-4-3وصل کردن خوشه‌ها به یکدیگر. 46

3-4-4چند پروتکل معروف در شبکه‌های سلسله مراتبی خوشه‌ایی.. 47

3-4-5پروتکل LEACH.. 47

3-4-5-1الگوریتم پدیدار شونده در تشکیل خوشه. 50

3-4-6خوشه‌های چند گامی.. 51

3-4-7تثبیت اندازه خوشه‌ها با بودجه رشد. 51

3-4-8لایه‌های مختلف خوشه‌بندی.. 52

3-4-9خوشه‌بندی غیر فعال.. 53

3-4-10سایر موارد مربوط به خوشه‌بندی.. 55

3-5روشها های برید(ترکیب توپولوژی سلسله مراتبی و کنترل توان)55

3-5-1 کنترل توان مبتنی بر Pilot55

3-5-2پروتکل کلاسترپا55

3-5-3روشهای دیگر صرفه جویی مصرف انرژی.. 56

3-5-3-1 GAF. 56

3-5-3-2 ASCENT. 57

فصل چهارم  نتیجه گیری

منابع.. 62

فهرست شکل ها

شکل 1 شبکه های حسگر. 2

شکل 2کاربرد شبکه های حسگری بیسیم.. 6

شکل 3ساختار سیستمی از یک حسگر گره‌ بی‌سیم.. 7

شکل 4 RNG.. 27

شکل 5 (a)گراف همسایگی نسبی (b)گراف گابریل.. 28

شکل 6 نمودار ورونوی (خطوط نقطه‌چین) و ﻣﺜﻠﺚ ﺑﻨﺪﯼ ﺩﻻﻧﯽ (خطوط صاف) مربوط به 5 گره. 29

شکل 7 نمایش ناحیه رله گره I با گره r بعنوان رله ممکن.. 30

شکل 8 نحوه ساختن همسایه برای گره i خارج از ناحیه رله با سایر همسایگان.. 31

شکل 9 گره‌های سفید هنوز پردازش نشده‌اند و گره‌های سیاه عضو مجموعه غالب و گره‌های خاکستری گره‌های تحت سلطه‌هستند خطوط کلفت لبه‌های درخت هستند.34

شکل 10 گراف نمونه که در ان ابتکار حریص یک گامی مبتنی بر عملکرد شکست می‌خورد. 34

شکل11 گراف.. 37

شکل12 Span. 39

شکل 13 گراف نمونه با حداکثر مجموعه مستقل.. 42

شکل 14 مجموعه حداکثر مستقل با هم‌پوشانی و بدون هم‌پوشانی.. 43

شکل 15 دو خوشه از طریق دو دروازه توزیع شده به یکدیگر متصل شده‌اند. 43

شکل 16 یک الگوریتم ابتدایی توزیع شده برای تعیین خوشه‌های مستقل با استفاده از شناسه گره بعنوان معیار رتبه بندی 45

شکل17 سرخوشه ها50

شکل 18 رابطه بین حداکثر برد رادیویی Rو طول مربع rدر پروتکل GAF. 57

شکل 19 پرتکل ASCENT. 57