کاربرد خوشه بندی k-means در پردازش تصویر

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

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

در چندین پست قبل در موردالگوریتم خوشه بندی k-means  به طور کامل بحث شد. اصطلاح k-means  برای اولین بار توسط جیمز مک کوئین در سال 1967 مورد استفاده قرار گرفت، هرچند این ایده به هوگو در سال 1957 برمیگردد. الگوریتم استاندارد ابتدا توسط استوارت لوئید در سال 1957 به عنوان یک تکنیک برای مدل کد-پالس پیشنهاد شد.

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

در زیر چند نمونه از کاربردها در پزشکی و کشاورزی را شرح می دهیم:

فلورسنس (خاصیتی فیزیکی است که برخی مواد شیمیایی آنرا دارند) چندگانه یا چندرنگی در محل هیبریداسیون (M-FISH) یک تکنیک جدید برای برچسب زدن سیتوژنیک است که می تواند برای تشخیص اختلالات کروموزومی برای سرطان و اختلالات ژنتیکی استفاده شود.

برای شناسایی ناهنجاری های کروموزومی الگوریتم خوشه بندی بهبود یافته c-means برای تقسیم بندی و طبقه بندی تصاویر M-FISH توسعه یافته است. اما الگوریتم مورد بحث در این مثال الگوریتم k-means  است که سریعتر از c-means عمل می کند.

اخیرا یک تکنیک برچسب زنی ترکیبی( M-FISH ) ایجاد شده است که در آن هر کلاس از کروموزوم ها با ترکیب متفاوتی از فلوروفورها که برای تجزیه و تحلیل کوروموزوم های انسان استفاده می شود، جذب می شود.

ایده ی مرکزی M-FISH  این است که هر کروموزوم با ترکیبی منحصر به فرد از 5 فلوراید برچسب گذاری شود. همچنین با استفاده از خوشه بندی k-means  برای انهدام می توان از یک فیلتر استفاده کرد. کارآیی و خروجی ساده از ویژگی های اساسی روش خوشه بندی k-means است.بسیاری از رویکردهای تقسیم بندی تصویر در طول سالها پیشنهاد شده است از این روش های مختلف خوشه بندی یکی از ساده ترین هاست و به طور گسترده ای در تقسیم بندی تصاویر خاکستری استفاده شده است.

جداسازی تصویر M-FISH با استفاده از الگوریتم خوشه بندی k-means نتیجه های بهتر تقسیم بندی را نسبت به سایر روش های مبتنی بر فازی ارائه می دهد. خروجی تقسیم بندی با استفاده از الگوریتم خوشه بندی k-means در شکل زیر نشان داده شده است.

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

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

 دو مرحله برای انجام خوشه بندی به روش K-MEANS وجود دارد، فاز با ایجاد دستگاه های مستقل تحول ساختار رنگ شروع میشود. در یک دستگاه مستقل فضای رنگی، برای تعیین رنگ بدون در نظر گرفتن دستگاهی که ان را رسم کرده از مختصات استفاده میشود. بنابراین ما ساختار تبدیل رنگی ایجاد میکنیم که فضای رنگی را تعریف کند. سپس دستگاه مستقل تبدیل رنگ که ارزش رنگ مشخص شده در تصویر را به فضای رنگی مشخص شده در ساختار تبدیل تغییر میدهد را اجرا میکنیم.
ساختار تبدیل رنگ مشخص میکند پارامتر های مختلف تبدیل را .فضای رنگ وابسته به دستگاه که در ان رنگ حاصل به تجهیزات مورد استفاده برای تولید ان بستگی دارد. برای مثال: رنگ تولید شده با استفاده از پیکسل با مقادیر RGB تغییر میکند با روشنایی و کنتراست دستگاهی که از ان استفاده میکنیم. الگوریتم خوشه بندی K-MEANS برای طبقه بندی اشیا ) پیکسل در این مورد( استفاده میشود، بر اساس مجموعه ای از ویژگی ها و تعداد طبقه ها ، طبقه بندی با به حد اقل رساندن مجموعه ی مربعات فواصل بین اشیاء و خوشه ی مربوطه یا مرکز جسم انجام شده است.  تصویر خوشه ی الوده با تاول زدن زود هنگام و خوشه ی اول ان  در شکل زیر نشان داده شده است.

نمونه ای از خوشه بندی K-MEANS برای یک برگ الوده ی مبتلا به بیماری تاول زدن  در شکل زیر نشان داده شده است.

تصاویر دیگری در مورد خوشه بندی k-means در پردازش تصویر را در زیر مشاهده می کنید.

منبع:

دانلود مفاهیم خوشه بندی

دانلود مقاله قطعه بندی کروموزوم

دانلود مقاله پردازش تصویر در آفت شناسی

دانلود مقاله Image Segmentation using K-Means

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

1) روش پایین به بالا (تجمعی Agglomerative):

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

فلوچارت این روش :

مثال 1)

گام های این روش را با ذکر یک مثال بیان می کنیم:(_خوشه بندی با روش پیوند مینگین انجام شده)

شباهت بین دو خوشه در روش Average-Link برابر است با میانگین فاصلة بین داده‌های دو خوشه.

گام اول:

الگوریتم، تعداد N خوشه (به تعداد مشاهدات) را در نظر می گیرد و برای تمام N خوشه ماتریس فاصله را حساب می کند.

مثال: 5 مشاهده= 5 خوشه داریم

ماتریس فاصله( هر درایه:میزان عدم تشابه یعنی فاصله ی مشاهدات)

گام دوم:

 در ماتریس فاصله به دنبال کمترین مقدار فاصله ها بین خوشه ها هستیم پس دو مشاهده ای که کمترین میزان فاصله را داراست باهم ادغام شده و تشکیل خوشه ای جدید را میدهند در این مثال دو مشاهده a و b تشکیل خوشه می دهند.

پس خوشه های پایان گام اول : {aوb} ، {c} ،{d} ، {e} می باشند.

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

هر درایه= مقادیر میزان عدم تشابه (  فاصله) خوشه ها

گام سوم:

کمترین فاصله مربوط به دو خوشه {d}و {e} می باشد پس خوشه جدید {d،e}.

متوسط میزان فاصله خوشه ها:

گام چهارم:

گامهای 2 و 3 تا زمانی که تنها یک خوشه که شامل تمامی مشاهدات است به همین منوال ادامه پیدا می کند.

برای نمایش بهتر اطلاعات از نمودار کمک میگیریم.

مثال 2)

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

شباهت بین دو خوشه در روش Single-Link برابر است با کمترین فاصلة بین داده‌های دو خوشه.

در این مثال 6 نمونه داده و ماتریس فاصله ی آنها در جدول 1 نشان داده شده است:

در ابتدا هر داده به عنوان یک خوشه در نظر گرفته می شود و یافتن نزدیکترین خوشه در واقع یافتن کمترین فاصله بین داده های بالا خواهد بود، با توجه جدول 1 مشخص است که داده های ۳ و ۵ کمترین فاصله را دارا هستند و در نتیجه آنها را باهم ترکیب کرده و خوشه ی جدیدی حاصل می شود که فاصله آن از سایر خوشه‌ها برابر است با کمترین فاصلة بین ۳ و یا ۵ از سایر خوشه‌ها. نتیجه در جدول ۲ نشان ‌داده شده است.

با توجه به جدول ۲ مشخص است که داده‌های ۱ و ۲ کمترین فاصله را دارا هستند. و در نتیجه آنها را با هم ترکیب کرده و خوشة جدیدی حاصل می‌شود که فاصلة آن از سایر خوشه‌ها برابر است با کمترین فاصلة بین ۱ و یا ۲ از سایر خوشه‌ها. نتیجه در جدول ۳ نشان ‌داده شده است.

با توجه به جدول ۳ مشخص است که خوشه‌های (۳ و ۵) و ۴ کمترین فاصله را دارا هستند. و در نتیجه آنها را با هم ترکیب کرده و خوشة جدیدی حاصل می‌شود که فاصلة آن از سایر خوشه‌ها برابر است با کمترین فاصلة بین (۳ و ۵) و یا ۴ از سایر خوشه‌ها. نتیجه در جدول ۴ نشان ‌داده شده است.

با توجه به جدول ۴ مشخص است که خوشه‌های (۱ و ۲) و ۶ کمترین فاصله را دارا هستند. و در نتیجه آنها را با هم ترکیب کرده و خوشة جدیدی حاصل می‌شود که فاصلة آن از سایر خوشه‌ها برابر است با کمترین فاصلة بین (۱ و ۲) و یا ۶ از سایر خوشه‌ها. نتیجه در جدول ۵ نشان ‌داده شده است.

در نهایت این دو خو‌شة حاصل ا هم ترکیب می‌شوند. نتیجه در دندوگرام  نشان داده شده است.

مثال 3)

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

شباهت بین دو خوشه در روش Complete-Link برابر است با بیشترین فاصلة بین داده‌های دو خوشه.

در این قسمت سعی شده است تا در مثالی با فرض داشتن ۶ نمونه داده و ماتریس فاصلة بین آنها که در جدول ۶ نشان ‌داده شده است، نحوة اعمال روش خوشه‌بندی Complete-Link بهتر تشریح شود.

در ابتدا هر داده به عنوان یک خوشه در نظر گرفته می‌شود و یافتن نزدیکترین خوشه در واقع یافتن کمترین فاصلة بین داده‌های بالا خواهد بود. با توجه به جدول ۶ مشخص است که داده‌های ۳ و ۵ کمترین فاصله را دارا هستند. و در نتیجه آنها را با هم ترکیب کرده و خوشة جدیدی حاصل می‌شود که فاصلة آن از سایر خوشه‌ها برابر است با بیشترین فاصلة بین ۳ و یا ۵ از سایر خوشه‌ها. نتیجه در جدول ۷ نشان ‌داده شده است.

با توجه به جدول ۷ مشخص است که داده‌های ۱ و ۲ کمترین فاصله را دارا هستند. و در نتیجه آنها را با هم ترکیب کرده و خوشة جدیدی حاصل می‌شود که فاصلة آن از سایر خوشه‌ها برابر است با بیشترین فاصلة بین ۱ و یا ۲ از سایر خوشه‌ها. نتیجه در جدول ۸ نشان ‌داده شده است.

با توجه به جدول ۸ مشخص است که خوشه‌های (۳ و ۵) و ۴ کمترین فاصله را دارا هستند. و در نتیجه آنها را با هم ترکیب کرده و خوشة جدیدی حاصل می‌شود که فاصلة آن از سایر خوشه‌ها برابر است با بیشترین فاصلة بین (۳ و ۵) و یا ۴ از سایر خوشه‌ها. نتیجه در جدول ۹ نشان ‌داده شده است.

با توجه به جدول ۹ مشخص است که خوشه‌های (۱ و ۲) و ۶ کمترین فاصله را دارا هستند. و در نتیجه آنها را با هم ترکیب کرده و خوشة جدیدی حاصل می‌شود که فاصلة آن از سایر خوشه‌ها برابر است با بیشترین فاصلة بین (۱ و ۲) و یا ۶ از سایر خوشه‌ها. نتیجه در جدول ۱۰ نشان ‌داده شده است.

در نهایت این دو خو‌شة حاصل با هم ترکیب می‌شوند. نتیجه در دندوگرام نشان داده شده است.

2) روش بالا به پایین (تقسیم کننده Divisive):

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

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

عیب این روش:

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

یکی از الگوریتم های معروفDIANA(Divisive Analysis) .

فلوچارت این روش:

نمودار مثال 1 برای این روش به این صورت است:

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

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

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

منبع:

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

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

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

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

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

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

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

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

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

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

خوشه بندی سلسله مراتبی در داد  با بُعد بالا، به دلیل زمان زیادی که صرف محاسبات می نماید، مقرون به صرفه و گاهی نیز قابل محاسبه نیست. البته این مشکل را با خوشه بندی K-MEANS رفع می کنند.

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

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

منبع:

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

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

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

خوشه بندی k-means

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

این روش روشی انحصاری و مسطح محسوب می شود.

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

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

 

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

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

منبع:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

-نقاط قوت:

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

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

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

-نقاط ضعف:

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

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

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

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

گام اول:

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

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

گام دوم:

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

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

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

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

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

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

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

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

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

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

منبع

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

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

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