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

یادگیرنده است که باید درون دادهها به دنبال ساختاری خاص بگردد. خوشهبندی را میتوان بهعنوان مهمترین مسأله در یادگیری بدون نظارت درنظر گرفت. شکل2-1(الف)، خوشهبندی اطلاعات بر اساس معیار شباهت بین دادهها و شکل2-1 (ب)، طبقهبندی اطلاعات بر اساس تعداد کلاس معین از قبل تعیین شده را نشان میدهد.
شکل 21 تفاوت خوشه بندی و طبقه بندی.
خوشه‌بندی همانگونه که بیان شد، بدون دانش قبلی، درون مجموعهای از دادهها به کشف گروههای مشابه میپردازد. در واقع، الگوریتمهای خوشهبندی اغلب بدینگونهاند که یک سری نماینده اولیه برای نمونههای ورودی در نظر میگیرند سپس با توجه به میزان تشابه نمونهها با این نمایندهها، مشخص میشود که نمونه به کدام خوشه تعلق دارد و بعد از این مرحله نمایندههای جدید برای هر خوشه محاسبه میشود و دوباره نمونهها با این نمایندهها مقایسه میشوند تا مشخص شود که به کدام خوشه تعلق دارند و این کار آنقدر تکرار میشود تا زمانیکه نمایندههای خوشهها تغییری نکنند.
انواعی از روشهای خوشهبندی تاکنون ارائه شدهاند که وابسته به کاربرد میتوان از آنها استفاده کرد. با این حال، با وجود گوناگونی روش‌های خوشه‌بندی، هنوز روش یکتایی وجود ندارد که بتواند انواع خوشه‌ها را به خوبی شناسایی کند؛ از این رو، این کاربر است که باید با توجه به نیاز‌هایش روش مناسب را بر‌گزیند.‌
2-2-1- تفاوت خوشهبندی و طبقهبندی
در طبقهبندی هر داده به یک کلاس از پیش تعیین شده ، تخصیص مییابد. در واقع، سیستمهایی که بر اساس طبقهبندی کار میکنند دو مجموعه ورودی دارند. مجموعهی آموزشی، که در آن دادههایی که به طور پیش فرض در دسته های مختلفی قرار دارند، همراه با ساختار دسته بندی خود وارد سیستم میشوند و سیستم بر اساس آنها آموزش می بیند یا به عبارتی، پارامترهای دسته بندی را برای خود مهیا میکند. گروه دیگر، ورودیهایی هستند که پس از مرحله آموزش و برای تعیین دسته وارد سیستم می شوند.
خوشهبندی با طبقهبندی11 متفاوت است. در طبقه بندی نمونههای ورودی برچسب گذاری شدهاند ولی در خوشهبندی نمونههای ورودی دارای بر چسب اولیه نمیباشند و در واقع با استفاده از روشهای خوشهبندی است که دادههای مشابه مشخص و بهطور ضمنی برچسبگذاری میشوند. در واقع میتوان قبل از عملیات طبقهبندی دادهها یک خوشهبندی روی نمونهها انجام داد و سپس مراکز خوشههای حاصل را محاسبه کرد و یک بر چسب به مراکز خوشهها نسبت داد و سپس عملیات طبقه بندی را برای نمونههای ورودی جدید انجام داد.
2-2-2-کاربردهای خوشهبندی
در بسیاری از موارد با کمبود اطلاعات در مورد دادهها مواجه میباشیم و تصمیم گیرنده میبایست تا آنجا که ممکن است فرضیاتی را در مورد داده متصور شود . تحت این محدودیت است که متدلوژی کلاسترینگ بهعنوان یک راهکار مناسب برای کشف ارتباطهای معنائی میان دادهها به شمار میرود و میتوان از آن به عنوان یک دانش اولیه12 از دادهها یاد کرد. در حال حاضرخوشهبندی در زمینههای متنوعی به کارگرفته شده است که به عنوان نمونه میتوان موارد زیر را برشمرد:
1- مهندسی: بینش محاسباتی، یادگیری ماشین، تشخیص الگو، مهندسی مکانیک ، مهندسی برق. کاربردهای موضوعی خوشهبندی درمحدودهی مهندسی از شناسایی بیومتریک و شناسایی گفتار تا تحلیل سیگنال رادار، خلاصه کردن اطلاعات و رفع پارازیت می باشد .
2 – علوم کامپیوتر: کاربردهای  خیلی  زیادی از خوشه بندی در وب کاوی ( دسته‌ بندی اسناد و یا دسته ‌بندی مشتریان به سایتها )، تحلیل پایگاه داده فضایی ، بازیابی اطلاعات ، گردآوری مستندات متنی وپردازش تصویر ( تقسیم بندی تصاویر پزشکی و یا ماهواره‌ای) مشاهده کردهایم .
3 – علوم پزشکی و زندگی: ژنتیک ، زیست شناسی ( دسته ‌بندی حیوانات و گیاهان از روی ویژگی‌های آنها )، میکروب شناسی، دیرین شناسی، روانپزشکی، تکامل نژادی، آسیب شناسی. این حوزهها، در وهلهی اول شامل کاربردهای عمدهی خوشهبندی هستند و تا یکی از زمینه های اصلی الگوریتمهای خوشهبندی گردند؛ ادامه پیدا میکنند. کاربردهای مهم شامل تعریف طبقه بندی، شناسایی کارکرد پروتئین و ژن ، تشخیص و درمان بیماری و … میباشند.
4 – علوم زمین و ستاره شناسی: جغرافیا، زمین شناسی، دریافت متحرک. خوشه بندی میتواند برای طبقهبندی کردن ستارهها و سیارات، تحقیق درمورد ساختار زمین، تفکیک کردن مناطق و شهرها (دسته‌بندی خانه‌ها براساس نوع و موقعیت جغرافیایی آنها)، مطالعهی رودخانه و کوهها، مطالعات زلزلهنگاری ( تشخیص مناطق حادثه‌ خیز بر اساس مشاهدات قبلی ) به کار رود .
5 – علوم اجتماعی: جامعه شناسی، روان شناسی، انسان شناسی، کتابداری ( دسته ‌بندی کتابها)، آموزش و پرورش. همچنین، کاربردهای جالب توجهای میتواند در تحلیل الگوی رفتاری، ساختار تاریخ تکاملی زبانها، تحلیل شبکههای اجتماعی، تشخیص باستان شناسی، طبقه بندی مصنوعی و مطالعه روان شناسی جنایی یافت شود.
6 – اقتصاد: بازاریابی، تجارت. کاربردهایی نظیر شناسایی الگوی خرید، گروه بندی شرکتها و تحلیل روند  ذخیرهسازی، همه از تحلیل خوشه بندی سودمند میگردند.
2-2-3- انواع خوشهها
خوشههای بهخوبی جدا شده: مجموعه نقاط داخل این خوشه نسبت به نقاط خارج آن به یکدیگر شباهت بیشتری دارند.
خوشههای مبتنی به مرکز: مجموعه نقاط داخل این خوشه به مرکز خوشه نسبت به مراکز خوشههای دیگر بسیار نزدیکترهستند.
خوشههای مبتنی بر مجاورت و نزدیکی: مجموعه نقاط داخل این خوشه به یک یا تعداد بیشتری از نقاط داخل خوشه نسبت به نقاط خارج آن شبیه میباشند.
2-2-4- مراحل خوشهبندی
خوشهبندی دارای چهارمرحلهی اساسی به شرح زیر است :
انتخاب یا استخراج ویژگی: ویژگیها باید به طور مناسبی انتخاب شوند تا اکثر دادهها کدگذاری گردند. در صورتی که در این مرحله، ویژگیهای انتخابی به طور نامناسب در نظر گرفته شوند، جواب نهایی هدف مورد نظر را نتیجه نخواهد داد. لذا، این بخش نقش اساسی را در روند خوشهبندی ایفا خواهد کرد [19]. برای بهدست آوردن مجموعهی مناسبی از ویژگیها در امر کلاسترینگ، از دو تکنیک استفاده می شود: گزینش ویژگی و استخراج ویژگی. گزینش ویژگی13 فرآیندی است که برای شناسائی مؤثرترین زیر مجموعه از ویژگیهای اولیه برای کلاسترینگ استفاده میشود و استخراج ویژگی14 استفاده از یک یا چند مرحله تبدیل ویژگیهای ورودی به منظور به دست آوردن ویژگیهای برجسته جدید میباشد .
مقیاس نزدیکی: معیاری است که میزان شباهت و یا عدم شباهت دو بردار خصوصیت را مشخص میکند. تمام خصوصیات انتخاب شده باید در محاسبه این معیار شرکت کنند و هیچ خصوصیتی نباید بر بقیه غلبه کند. سادهترین معیار برای مسافت، فاصله اقلیدسی است که بیانگر افتراق15 بین دو نمونه میباشد . این در حالی است که معیارهای تشابه هم میتوانند برای تشخیص تشابهات معنائی در میان نمونهها استفاده شوند. همین که، یک مقیاس نزدیکی تعیین میشود، خوشهبندی میتواند به عنوان یک مسألهی بهینه سازی با یک تابع معیار خاص استنباط گردد. پس خوشههای به دست آمده وابسته به انتخاب تابع معیار میباشند.
الگوریتم خوشهبندی: پس از اینکه مقیاس نزدیکی انتخاب شدند، یک الگوریتم خاص جهت روشن کردن ساختار دستهبندی مجموعه دادهها انتخاب میگردد. بهعنوان نمونه خروجی خوشهبندی میتواند گروههای سخت16 و یا نرم 17باشد که هر روش دارای درجه عضویت متفاوتی بوده و درجه عضویت، میزان تعلق هر داده به خوشه است.
اعتبار سنجی نتایج: شاخص های اعتبار سنجی برای سنجش میزان صحت نتایج خوشهبندی به منظور مقایسه بین روشهای مختلف یا مقایسهی نتایج حاصل از یک روش با پارامترهای مختلف مورد استفاده قرار می گیرد؛ زیرا نتایج حاصل از اعمال الگوریتمهای خوشهبندی روی یک مجموعه داده با توجه به مقادیر انتخابی برای پارامترهای هر الگوریتم میتواند بسیار متفاوت از یکدیگر باشد. هدف از اعتبارسنجی، یافتن خوشههایی است که بهترین تناسب را با دادههای مورد نظر داشته باشند.
دو معیار پایه اندازهگیری برای ارزیابی و انتخاب خوشههای بهینه عبارتند از:
• تراکم18 : دادههای متعلق به یک خوشه بایستی تا حد ممکن به یکدیگر نزدیک باشند. معیار رایج برای تعیین میزان تراکم دادهها واریانس دادهها است.
• جدایی 19: خوشهها خود بایستی به اندازه کافی از هم جدا باشند. سه راه برای سنجش میزان جدایی خوشه ها مورد استفاده قرار می گیرد:
* فاصله بین نزدیکترین دادهها از دو خوشه
* فاصله بین دورترین دادهها از دو خوشه
* فاصله بین مراکز خوشهها
همچنین، روشهای ارزیابی خوشههای حاصل از خوشهبندی را به سه دسته تقسیم می کنند: شاخصهای خارجی، شاخصهای داخلی و شاخصهای نسبی.
شاخصهای خارجی: شاخصهای خارجی مبتنی بر بعضی ساختارهای از پیش تعیین شده اند که بازیاب اطلاعات قبلی درمورد داده ها بوده و به عنوان استانداردی برای اعتبار راهحلهای خوشهبندی استفاده میشوند.
شاخصهای داخلی: تست داخلی به اطلاعات خارجی(دانش پیشین) وابستگی ندارد. آنها مستقیماً ساختار خوشهبندی را از روی دادههای اصلی، آزمایش مینمایند. از روشهای ساده و معروف در این زمینه T-test میباشد.
شاخصهای نسبی: معیارهای نسبی بر تفاوت ساختـــارهای خوشهبندی تأکید مینماید، بهطوری که به عنوان مرجعی میتواند شایستگی خوشهها را آشکار نماید.
2-2-5- انواع روشهای خوشهبندی
روشهای کلاسترینگ به انواع مختلف و در طبقه بندیهای مختلف معرفی میشوند. این روشها را می توان از چندین جنبه تقسیمبندی کرد[20]:
1. خوشهبندی انحصاری20 و خوشهبندی با همپوشی21
در روش انحصاری پس از خوشهبندی، هر داده دقیقاً به یک خوشه تعلق می گیرد مانند روش خوشه بندی k-means . ولی در خوشهبندی با روش همپوشی پس از خوشهبندی، به هر داده یک درجهی تعلق به ازاء هر خوشه نسبت داده میشود یعنی یک داده میتواند با نسبتهای متفاوتی به چندین خوشه تعلق داشته باشد. نمونهای از این روش، خوشهبندی فازی است.
2. خوشهبندی سلسله مراتبی22 و خوشهبندی مسطح23
در روش سلسله مراتبی، به خوشههای نهایی بر اساس میزان عمومیت آنها، ساختاری سلسله مراتبی نسبت داده میشود مانند روش اتصال منفرد. در روش مسطح تمام خوشههای نهایی دارای یک میزان عمومیت هستند مانند k-means.
با توجه به اینکه روشهای خوشهبندی سلسله مراتبی اطلاعات بیشتر و دقیق تری تولید میکنند برای تحلیل دادههای با جزئیات پیشنهاد میشوند، ولی از آن جایی که پیچیدگی محاسباتی بالایی دارند، برای مجموعه دادههای بزرگ روش خوشهبندی مسطح پیشنهاد میشود.
2-2-6- خوشهبندی سلسله مراتبی
همانگونه که بیان شد، در روش خوشهبندی سلسله مراتبی به خوشههای نهایی بر اساس میزان عمومیت آنها، ساختاری سلسله مراتبی، معمولاً به صورت درختی نسبت داده میشود. به این درخت سلسله مراتبی دندوگرام24 میگویند. گره ریشهی نمودار درختی، تمام مجموعه داده را نشان میدهد و هرگره برگ، به عنوان یک نقطه داده در نظرگرفته میشود. بنابراین، گرههای میانی حوزهی اشیایی که به هم  نزدیک هستند؛ را توصیف می کنند و ارتفاع نمودار درختی معمولاً فاصلهی بین یک نقطه داده و یک خوشه را بیان میکند. نتایج نهایی خوشه بندی میتواند با برش نمودار درختی در سطوح مختلف به دست آید. این نمودار توصیفات آموزندهای از ساختار خوشه بندی داده را فراهم میکند، مخصوصاً وقتی ارتباطات سلسله مراتبی حقیقی در دادهها وجود داشته باشد. این روش خوشهبندی بر اساس ساختار سلسله مراتبی تولیدی توسط آنها به دو دسته تقسیم می شود[21]: بالا به پایین یا تقسیم شونده25 و پایین به بالا یا متراکم شونده26.
2-2-6-1- خوشه بندی سلسله مراتبی تقسیم شونده
در این روش

مطلب مرتبط :   مقاله رایگان درموردوجوه نقد، ارزیابی عملکرد، اطلاعات مربوط، سرمایه گذاران

دیدگاهتان را بنویسید