فهرست مطالب :

مقدمه

فصل اول- الگوریتم های خوشه بندی چند مرحله ای و پربازده

۱- کلاستر چیست؟

۱-۱ انواع کلاسترها

۱-۲ خوشه‌بندی در مقابل طبقه‌‌بندی

۱-۳ یادگیری با نظارت در مقابل یادگیری بدون‌نظارت

۱-۴ کاربردها

۱-۵ مسائل درگیر با روش‌های خوشه‌بندی موجود

۱-۶ خوشه‌بندی در مقابل چندی‌سازی برداری

۱-۷ ویژگی های الگوریتم های خوشه بندی

۱-۸ روش‌های خوشه‌بندی

۱-۸-۱ خوشه‌بندی انحصاری و خوشه‌بندی با هم‌پوشی

۱-۸-۱-۱ خوشه بندی فازی

۱-۸-۲ خوشه‌بندی سلسله مراتبی و خوشه‌بندی مسطح

۱-۸-۳ روشهای خوشه‌بندی سلسله مراتبی

۱-۸-۳-۱ خوشه‌بندی با روش Single-Link

۱-۸-۳-۲ خوشه‌بندی با روش Complete-Link

۱-۸-۳-۳ خوشه‌بندی با روش Average-Link

۱-۸-۳-۴ خوشه‌بندی با روش Group Average Link

۱-۸-۳-۵ خوشه‌بندی با روش Median Distance

۱-۸-۳-۶ خوشه‌بندی با روش Ward

۱-۸-۳-۷ الگوریتم خوشه‌بندی پایین به بالای عمومی

۱-۸-۴ روش خوشه‌بندی K-Means (C-Means یا C-Centeriod)

۱-۸-۴-۱ مشکلات روش خوشه‌بندی K-Means

۱-۸-۴-۲ مزایای روش خوشه بندی K-Means

۱-۸-۵ الگوریتم خوشه‌بندی LBG

۱-۸-۶ خوشه‌بندی بر اساس چگالی

۱-۸-۶-۲ الگوریتم سلسله مراتبی خوشه‌بندی براساس چگالی OPTICS

۱-۸-۷ مزایای خوشه‌بندی بر اساس چگالی

۱-۸-۸ بررسی تکنیکهای اندازه‌گیری اعتبار خوشه‌ها

۱-۹ خوشه بندی متن

۱-۹-۱ الگوریتم خوشه بندی Bi-Section-K Means

۱-۹-۲ خوشه بندی مستندات متنی به کمک انتولوژی

۱-۹-۳ کامپایل کردن دانش پس زمینه درون متن

۱-۹-۴ استراتژی های استفاده از کلمه در مقابل مفهوم

۱-۱۰ خوشه بندی جریانهای داده

۱-۱۰-۱ الگوریتم های خوشه بندی جریان داده

۱-۱۰-۲ مقایسه الگوریتم های خوشه بندی جریان داده

فصل دوم- الگوریتم های خوشه بندی – شبکه های حسگر بیسیم

۲-شبکه حسگر چیست؟

۲-۱ ساختار کلی شبکه حسگر بی سیم

۲-۲ ساختمان گره

۲-۳ نمونه ی پیاده سازی شده شبکه حسگر

۲-۴ شبیه ساز OMNeT++

۲-۵ مدل سازی شبکه های بی سیم

۲-۶ ساختار یک مدل پیش ساخته

۲-۷ قابلیت های مدل سازی

فصل سوم- الگوریتم های خوشه بندی – آتاماتای یادگیری

۳- اتوماتای هوشمند (اتوماتای یادگیر)

۳-۱ یادگیری

۳-۲ تاریخچه اتوماتای یادگیر

۳-۳ اتوماتای یادگیر تصادفی

۳-۳-۱ اتوماتای تصادفی

۳-۴ معیار‌های رفتار اتوماتای یادگیر

نتیجه گیری و پیشنهادات

پیوست

فهرست منابع

چکیده :

یکی از چالش های اصلی در شبکه های حسگر بیسیم ، محدودیت انرژی گره های حسگر است که باید دقیقا موقعی به آن توجه شود که الگوریتم برای چنین شبکه هایی طراحی می شود. خوشه بندی (دسته بندی) بعنوان یکی از رویکردهای شناخته شده است که می توان از آن برای بیان این چالش استفاده کرد . در این مقاله ، روش پربازده برای دسته بندی شبکه های حسگر بیسیم، روش یادگیری سلولی ماشینی است که مطرح گردید . روش پیشنهادی، سرخوشه(CHS) را در چندین مرحله انتخاب می کند. در هر کدام به یک پارامتر توجه دارد، پارامتری که روی عملکرد کلی دسته بندی اثر می گذارد . پارامتر مورد توجه در مراحل گوناگون الگوریتم مطرح شده برابر سطح انرژی گره های حسگر تعداد مجاورهای هر گره، اتصال شبکه، تشکیل خوشه های متوازن است. برای ارزیابی عملکرد روش مطرح شده، چندین آزمایش با استفاده از شبیه ساز J-Sim انجام شد و روش مطرح شده با برخی از بهترین الگوریتم های دسته بندی گزارش شده در این نوشته علمی مقایسه شد. نتایج شبیه سازی نشان داد که الگوریتم پیشنهادی می تواند زیر ساخت دسته بندی را با کیفیت عالی تر از الگوریتم های موجود فراهم سازد به ویژه در متوازن ساختن تعدادی از گره های حسگر در خوشه های مختلف و انتخاب CHS با سطح انرژی بیشتر.

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

الگوریتم های خوشه بندی چند مرحله ای و پربازده

۱- کلاستر چیست؟

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

۱-۱ انواع کلاسترها

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

• کلاسترهای بخوبی جدا شده

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

• کلاسترهای مبتنی به مرکز:

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

• کلاسترهای مبتنی بر مجاورت و نزدیکی:

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

۱-۲ خوشه‌بندی در مقابل طبقه‌‌بندی[۱]

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

۱-۳ یادگیری با نظارت[۲] در مقابل یادگیری بدون‌نظارت[۳]

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

۱-۴ کاربردها

یک جستجوی ساده در وب یا حتی در پایگاه داده ی یک کتابخانه، کاربرد شگفت انگیز خوشه بندی را برای ما اشکار می سازد. از انجا که خوشه‌بندی یک روش یادگیری بدون نظارت محسوب می‌گردد، در موارد بسیاری می‌تواند کاربرد داشته‌ باشد.

• در بازاریابی:دسته‌‌بندی مشتری‌ها به دسته‌هایی بر حسب رفتارها و نیازهای انها از طریق مجموعه زیادی از ویژگی‌ها و اخرین خرید‌های انها.
• زیست‌‌‌شناسی:دسته‌بندی حیوانات و گیاهان از روی ویژگی‌های انها
• کتابداری :دسته‌بندی کتابها
• نقشه‌برداری شهری: دسته‌بندی خانه‌ها بر اساس نوع و موقعیت جغرافیایی انها.
• مطالعات زلزله‌نگاری:تشخیص مناطق حادثه‌خیز بر اساس مشاهدات قبلی.
• وب: دسته‌بندی اسناد، دسته‌بندی مشتریان مراجعه کننده به سایتها و ….
• داده کاوی[۴]:کشف اطلاعات و ساختار جدید از داده‌های موجود
• در تشخیص گفتار[۵]:در ساخت کتابِ کد از بردارهای ویژگی، در تقسیم کردن گفتار بر حسب گویندگان ان و یا فشرده‌سازی گفتار
• در تقسیم‌بندی تصاویر[۶]:تقسیم‌بندی تصاویر پزشکی و یا ماهواره‌ای
• بیمه:تشخیص افراد متقلب، تشخیص افرادی که بیمه موتور دارند و بیشترین میزان درخواست از بیمه را نیز در سال مشخصی داشته اند.

۱-۵ مسائل درگیر با روش‌های خوشه‌بندی موجود

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

به دلیل پیچیدگی‌ محاسباتی زیاد در برخورد با مجموعه داده‌های بزرگ (تعداد داده ‌زیاد  وتعداد ویژگی‌های زیاد برای هر داده) عملی نیستند.

به دلیل وابستگی‌ شدید به تعریف معیار شباهت بین داده‌ها در مسائلی که تعریف معیار شباهت مشکل باشد نتایج مطلوبی تولید نمی‌کنند.(در داده‌ها با تعداد ویژگی‌ زیاد)

برای نتایج انها می‌توان تفسیرهای مختلفی بیان کرد

۱-۶ خوشه‌بندی در مقابل چندی‌سازی برداری[۷]

همان‌گونه که بحث شد، خوشه‌بندی نوعی سازماندهی داده‌ها است، بر اساس شباهتی که بین انها تعریف می‌شود به گونه‌ای که شباهت بین داده‌هایی که درون یک خوشه قرار می‌گیرند نسبت به داده‌هایی که درون خوشه‌های متفاوت قرار می‌گیرند، بیشتر باشد.

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

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

۱-۷ ویژگی های الگوریتم های خوشه بندی

الگوریتم های خوشه بندی باید دارای خصوصیات زیر باشند:

• مقیاس پذیری
• امکان کار کردن باattributeهای مختلف
• یافتن خوشه ها با شکل های قراردادى
• دارا بودن حداقل دانش محیط کامپیوتر برای تشخیص پارامترهای ورودی
• دسته پنجه نرم کردن با نویز و برون نهشت ها
• ترتیب داده های ورودی بر روی ان تأثیری نداشته باشد
• دارای ابعاد مختلف و بالا
• قابلیت تغییر و امکان استفاده ی اسان

۱-۸ روش‌های خوشه‌بندی

روش‌های خوشه‌بندی را می‌توان از چندین جنبه تقسیم‌بندی کرد:

۱-۸-۱ خوشه‌بندی انحصاری[۱۰] و خوشه‌بندی با هم‌پوشی[۱۱]

در روش خوشه‌بندی انحصاری پس از خوشه‌بندی هر داده دقیقا به یک خوشه تعلق می‌گیرد مانند روش خوشه‌بندی K-Means. ولی در خوشه‌بندی با همپوشی پس از خوشه‌بندی به هر داده یک درجه تعلق بازاء هر خوشه نسبت داده می‌شود. به عبارتی یک داده می‌تواند به مقادیر متفاوتی به چندین خوشه تعلق داشته باشد. نمونه‌ای از ان خوشه‌بندی فازی است

۱-۸-۱-۱ خوشه بندی فازی

در خوشه بندی کلاسیک، هر نمونه ورودی متعلق به یک و فقط یک خوشه است و نمی تواند عضو دو خوشه و یا بیشتر باشد. به عبارتی خوشه ها همپوشانی ندارند، در حالی که در خوشه بندی فازی یک نمونه می تواند متعلق به بیش از یک خوشه باشد. خوشه بندی فازی به کشف مدل های فازی از داده ها می پردازد.

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

یکی تحلیل داده های فازی و دیگری تحلیل داده های قطعی با استفاده از تکنیک های فازی.

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

برای روشن شدن مطلب شکل زیر را در نظر بگیرید:

شکل ۱-۳  مجموعه داده پروانه ای

اگر نمونه های ورودی مطابق شکل فوق باشند مشخص است که می توان داده ها را به دو خوشه تقسیم کرد اما مشکلی که پیش می اید این است که داده مشخص شده در وسط می تواند عضو هر دو خوشه باشد بنابراین باید تصمیم گرفت که داده مورد نظر متعلق به کدام خوشه است، خوشه سمت راست یا خوشه سمت چپ. اما اگر از خوشه بندی فازی استفاده کنیم داده مورد نظر با تعلق ۰٫۵ عضو خوشه سمت راست و با تعلق مشابه عضو خوشه سمت چپ است.

از الگوریتم های پایه ای خوشه بندی فازی می توان الگوریتم های Fuzzy C-MeansوPossibilistic C-Means  را نام برد.

۱-۸-۲ خوشه‌بندی سلسله مراتبی[۱۲] و خوشه‌بندی مسطح[۱۳]

در روش خوشه بندی سلسله مراتبی، به خوشه‌های نهایی بر اساس میزان عمومیت انها  ساختاری سلسله‌ مراتبی نسبت داده می‌شود. مانند روش Single Link. ولی در خوشه‌بندی مسطح تمامی خوشه‌های نهایی دارای یک میزان عمومیت هستند مانند K-Means. به ساختار سلسله مراتبی حاصل از روشهای خوشه‌بندی سلسله مراتبی دندوگرام[۱۴]  گفته می‌شود.

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

۱-۸-۳ روشهای خوشه‌بندی سلسله مراتبی

همان گونه که بیان شد، در روش خوشه بندی سلسله مراتبی، به خوشه‌های نهایی بر اساس میزان عمومیت انها  ساختاری سلسله‌ مراتبی، معمولا به صورت درختی نسبت داده می‌شود. به این درخت سلسله مراتبی دندوگرام می‌گویند. روش کار تکنیکهای خوشه‌بندی سلسله‌مراتبی معمولا بر اساس الگوریتمهای حریصانه[۱۵]  و بهینگی مرحله‌ای[۱۶] است. روشهای خوشه‌بندی بر اساس ساختار سلسله مراتبی تولیدی توسط انها معمولا به دو دسته زیر تقسیم می‌شوند:

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

گرفته می‌شود و در طی فرایندی تکراری در هر مرحله خوشه‌هایی که شباهت بیشتری با یکدیگر دارند با هم ترکیب می‌شوند تا در نهایت یک خوشه و یا تعداد مشخصی خوشه حاصل شود. از انواع الگوریتمهای خوشه‌بندی سلسله مراتبی متراکم شونده رایج می‌توان از الگوریتمهای Single-Link، Average-Linkو Complete-Linkنام برد. تفاوت اصلی در بین تمام این روشها به نحوه محاسبه شباهت بین خوشه‌ها مربوط می‌شود. که در بخشهای بعد به تشریح هر یک پرداخته خواهد شد.

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

[۱] Classification

[۲] Supervised Learning

[۳] Unsupervised Learning

[۴] Data Mining

[۵] Speech Recognition

[۶] Image Segmentation

[۷] Vector Quantization

[۸] CodeWord

[۹] CodeBook

[۱۰] Exclusive or Hard Clustering

[۱۱] Overlapping or Soft Clustering

[۱۲] Hierarchical

[۱۳] Flat

[۱۴] Dendogram

[۱۵] Greedy Algorithms

[۱۶] stepwise optimal

(فایل کامل این پروژه ۱۲۵(صد و بیست و پنج) صفحه word همراه با منابع و ماخذ می باشد.)

در تمامی ساعات شبانه روز >> پرداخت آنلاین و دانلود آنی فایل پس از پرداخت.