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

خوشه بندی، سازمان دهی مجموعه ای از الگوها[1] بر اساس شباهت در خوشه ها است. به نحوی که الگوهای داخل یک خوشه شبیه به هم بوده و دارای بیشترین تفاوت با الگوهای خوشه های دیگر باشند. بطور کلی، فرآیند خوشه بندی بصورت یک دسته بندی بدون سرپرست، تعریف می شود که هیچ اطلاع قبلی در مورد کلاس ها و یا تعداد آنها موجود نیست. از طرفی باید به تفاوت میان دسته بندی و خوشه بندی توجه داشت. شکل(4-1) در دسته بندی با سرپرست، مجموعه ای از الگوهای برچسب دار (دسته بندی شده) موجود است و مسئله، برچسب زدن به داده جدید است. این الگوهای برچسب دار، کلاس ها را توصیف می کنند که این کلاس ها برای برچسب زنی الگوی جدید بکار می روند. ولی در خوشه بندی که نوعی دسته بندی بدون سرپرست است، هیچ اطلاع قبلی راجع به کلاس ها یا تعداد آنها موجود نیست و مسئله دسته بندی مجموعه ای از الگوهای بدون برچسب در خوشه های ممکن است و به هر خوشه نیز یک برچسب اختصاص می یابد. ولی این برچسب ها از خود داده ها ناشی می شوند.

شکل (4-1): انواع خوشه بندی

1.Pattern

از جمله کاربردهای خوشه بندی به بازیابی اطلاعات، پردازش تصاویر، شناسایی الگو، سنجش از راه دور، داده کاوی و … میتوان اشاره نمود . برای پیاده سازی الگوریتم های مختلفی بکار گرفته شده اند. این الگوریتم ها را در دو دسته سلسله مراتبی و افرازی [1] تقسیم بندی می نمایند. شکل (4-3). روش های سلسله مراتبی شامل دو دسته کلی تجمعی و تقسیمی می باشند. از روش های خوشه بندی افرازی میتوان الگوریتم K-Means و EM[2] را نام برد.

شکل (4-3): روش های خوشه بندی

4-3-1-روش های خوشه بندی سلسله مراتبی[3]

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

• روش های خوشه بندی بالارونده
• روش های خوشه بندی پایین رونده

در سیستم هایی که بصورت برون خط کار می کنند و در جاهایی که بخش های  گفتار مشخص هستند، عمل ادغام[4] تا جایی ادامه می یابد تا به تعداد بهینه از گویندگان دست یابیم. روش های خوشه بندی سلسله مراتبی بیشتر بر اساس تئوری گراف استوار است. ساختار این روش را بصورت گرافیکی میتوان با نمودار درختی[5]  نمایش داد. روش غالب خوشه بندی مورد استفاده در سیستم ها، خوشه بندی تجمعی سلسله مراتبی[6] است که از یک معیار توقف برای پایان خوشه بندی استفاده می کند. مراحل به شرح زیر است:

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

شکل) 4-4 ):روش های خوشه بندی بالا و پایین رونده[1]

4-3-1-1-روش های خوشه بندی بالارونده[7] :با توجه به مطالب فوق، در این روش هر داده را بطور مستقل به عنوان یک خوشه در نظر می گیریم و با تعریف معیار شباهت، دو یا چند خوشه، خود تشکیل یک خوشه بزرگتر می دهند و این روند ادامه می یابد تا شرط پایانی الگوریتم که معمولا تعداد خوشه ها است، تحقق پذیرد. بعبارت دیگر با تعداد زیادی از بخش ها کار خود را شروع می نماید و با استفاده از تکنیک های ادغام، به یک اندازه بهینه از کلاس ها دست می یابد.[1] این تکنیک سالهای زیادی در دسته بندی آماری برای دسته- بندی مورد استفاده قرار گرفته است. معمولا یک ماتریس فاصله بین همه خوشه ها تعریف می شود و هر دو خوشه نزدیک به هم ادغام می شوند تا کار خاتمه یابد. برای توقف می توانیم از فرمول زیر استفاده نماییم:

(4-1)

K : تعداد خوشه های موجود است.  N_K تعداد بخش های آکوستیکی و  کواریانس ماتریس خوشه k.

در سال 2006 توسط راجی فاصله میان دو مدل مبتنی بر مدل مخلوط گوسی از طریق محاسبه به وسیله فاصله KL مطرح شد. دو مدل M₁ , M₂ هر کدام با K₁ , K₂  ترکیب گوسی و وزن های گوسی  مفروضند.

فاصله  دو مدل M₁ , M₂ از فرمول زیر محاسبه می شود:

(4-2)

حال اگر از KL2 برای محاسبه فاصله استفاده نماییم داریم:[1]

(4-3)

4-3-1-2-روش های خوشه بندی پایین رونده[8]: روش سلسله مراتبی تقسیمی برخلاف روش تجمعی، همه اشیا را یک خوشه در نظر می گیرد و بطور تکراری هر خوشه را به خوشه های کوچکتر تا زمان ارضای شرط پایانی، تقسیم می کند. بعبارت دیگر معمولا با تعداد کلاس های کمی شروع به کار می کند و با تقسیم به بخش های کوچکتر تا رسیدن به مقدار بهینه تقسیمات را ادامه می دهد.

این الگوریتم در ابتدا با تقسیم شدن به قسمت های کوچکتر، سرانجام به تعداد بهینه خوشه تقسیم و در نهایت متوقف می شود. شکل (4-5) این روش را بخوبی نشان می دهد:

شکل (4-5): مثال ساده ای از خوشه بندی سلسله مراتبی[80]

در الگوریتم های خوشه بندی سلسله مراتبی، میزان مشابهت بین دو خوشه که هر کدام از آنها فقط حاوی یک کلاس است، برابر با میزان مشابهت بین دو کلاس خواهد بود. در غیر این صورت مشابهت بین دو خوشه به سه روش زیر محاسبه می شود:[71]

• پیوند تکی[9]: مشابهت بین دو خوشه، برابر با میزان مشابهت زوجی از اعضای دو خوشه خواهد بود که نسبت به مشابهت سایر زوج های ممکن بین دو خوشه، کمترین مقدار را داشته باشد.

(4-4)

• پیوند کامل[10]: مشابهت بین دو خوشه برابر با میزان مشابهت زوجی از اعضای دو خوشه خواهد بود که نسبت به مشابهت سایر زوج های ممکن بین دو خوشه، بیشترین مقدار را داشته باشد.

(4-5)

• پیوند میانگین گروهی[11]: مشابهت بین دو خوشه برابر با میانگین میزان مشابهت همه زوج های ممکن بین اعضای دو خوشه خواهد بود.

(4-6)

4-3-2-روش های خوشه بندی افرازی

روش های افرازی، داده ها را بر اساس معیار تشابه به تعداد خاص خوشه ها تقسیم بندی می کنند. در این روش تمام تکنیک ها بر این فرض استوار است که هر داده تنها متعلق به یک خوشه می باشد. روش های افرازی در مواردی که مجموعه داده بزرگی در اختیار است و تشکیل نمودار درختی از نظر محاسباتی مقرون به صرفه نیست، از نظر کاربرد مزیت دارند. معروفترین الگوریتم در این گروه الگوریتم K-means  می باشد که داده ها را به k  خوشه مستقل تقسیم بندی می کند. از دیگر الگوریتم های این دسته، میتوان به الگوریتم های خوشه- بندی فازی[12] و روش های مبتنی بر شبکه های عصبی (ANN) ، مثل SOM[13] را نام برد.[76]

1.Partitional

2. Expectation Maximization

[3].Hierarchical Clustering Techniques

[4].Merge

[5].Dendrogram

4.Hiererchical Agglomerative Clustering

[7].Bottom-up Clustering Techniques

[8].Top-down Clustering Techniques

2.Single Link

1.Complete Link

2.Group Average Link

3.Fuzzy

4.Self-organizing map