تکنیک خوشه بندی

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

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

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

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

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

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

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

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

• هر گروه یا خوشه  با توجه به یک خصوصیت  ویژه همگن است.
• هر گروه یا خوشه با توجه به همان خصوصیت با گروه هی دیگر متفاوت است.

آلدندرفر و بلشفید در سال 1984 اهداف به کارگیری خوشه بندی را به طور خلاصه اینگونه بیان کردند:

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

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

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

خوشه بندی هم مانند هر روشی دارای نقاط قوت و ضعف است:

-نقاط قوت:

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

• خوشه بندی را می توان برای داده های گوناگون استفاده نمود: با انتخاب درست اندازه فاصله های گوناگون خوشه بندی را می توان برای بیشتر  انواع داده ها استفاده نمود.

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

-نقاط ضعف:

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

به طور کل برای همه  ی روش های خوشه بندی دو گام اساسی وجود دارد:

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

گام دوم: چگونگی ادغام داده ها بر اساس میزان شباهتشان

گام اول:

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

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

گام دوم:

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

پیوند تکی، پیوند کامل، پیوند میانگین، پیوند میانگین وزنی، پیوند مرکز ثقل، پیوند میانه، پیوند وارد.

• پیوند تکی ( کمترین فاصله یا نزدیکترین همسایه):

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

این پیوند در  شکل زیر مشخص شده است:

• پیوند کامل ( بیشترین فاصله یا دورترین همسایه):

               فاصله ی بین دو خوشه= بیشترین فاصله بین یک داده از یک خوشه با یک داده از خوشه ی دیگر

پیوند کامل در مقابل پیوند تکی کمتر در معرض اثر خطا قرار می گیرد.

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

خوشه بندی روش های مختلفی دارد اما روش های مورد بحث ما روش K-means و روش سلسله مراتبی است که در پستهای بعدی به توضیحات آن می پردازیم.

منبع

دانلود خوشه بندی و روش های آن

دانلود خوشه بندی K-means  و سلسله در نرم افزارها

دانلود تحلیل خوشه بندی(ppt)