خوشه بندی سخت چیست ؟
در خوشه بندی سخت، هر نقطه داده به یک خوشه خوشه یا گروه بندی می شود. برای هر نقطه داده، ممکن است کاملاً متعلق به یک خوشه باشد یا نباشد. همانطور که در نمودار بالا مشاهده می شود، نقاط داده به دو خوشه تقسیم می شوند که هر نقطه متعلق به یکی از دو خوشه است.
خوشه بندی K-means یک الگوریتم خوشه بندی سخت است. نقاط داده را در خوشه های k خوشه بندی می کند.
خوشه بندی نرم چیست ؟
در خوشه بندی نرم، به جای قرار دادن هر نقطه داده در خوشه های جداگانه، احتمال آن نقطه به خوشه های احتمالی اختصاص داده می شود. در خوشه‌بندی نرم یا خوشه‌بندی فازی، هر نقطه داده می‌تواند به خوشه‌های متعدد به همراه امتیاز احتمال یا احتمال آن تعلق داشته باشد.
یکی از الگوریتم های خوشه بندی نرم که به طور گسترده مورد استفاده قرار می گیرد، الگوریتم فازی c-means clustering (FCM) است.
اجازه دهید این دو الگوریتم قدرتمند را با هم مقایسه کنیم تا ایده روشنی از جایی که الگوریتم c-means فازی در آن قرار می گیرد به دست آوریم.
- انتساب به یک خوشه: در خوشه بندی فازی، هر نقطه احتمال تعلق به هر خوشه را دارد، نه اینکه به طور کامل فقط به یک خوشه تعلق داشته باشد، همانطور که در k-means سنتی وجود دارد. در خوشه‌بندی Fuzzy-C Means، هر نقطه دارای وزنی است که با یک خوشه خاص مرتبط است، بنابراین یک نقطه به اندازه ارتباط ضعیف یا قوی با خوشه که با فاصله معکوس تعیین می‌شود، «در یک خوشه» قرار نمی‌گیرد. به مرکز خوشه.
- سرعت: میانگین C فازی نسبت به میانگین K کندتر عمل می کند، زیرا در واقع کار بیشتری انجام می دهد. هر نقطه با هر خوشه ارزیابی می شود و عملیات بیشتری در هر ارزیابی درگیر می شود. K-Means فقط باید یک محاسبه فاصله انجام دهد، در حالی که میانگین c فازی باید یک وزن دهی کامل با فاصله معکوس انجام دهد.
- نظر شخصی: FCM/Soft-K-Means نسبت به Hard-K-Means «کمتر احمقانه» است که به خوشه های کشیده می رسد (زمانی که نقاطی که در ابعاد دیگر ثابت هستند تمایل دارند در طول یک یا دو بعد خاص پراکنده شوند).
ما باید متوجه باشیم که c-means فازی یک مورد خاص از K-means است وقتی که تابع احتمال مورد استفاده به سادگی 1 است اگر نقطه داده به یک مرکز نزدیکتر باشد و 0 در غیر این صورت.
الگوریتم خوشه‌بندی k-means بدون نظارت، مقادیر هر نقطه در یک خوشه خاص را 0 یا 1 می‌دهد، یعنی درست یا نادرست. اما منطق فازی مقادیر فازی هر نقطه داده خاص را در هر یک از خوشه ها می دهد. در اینجا، در خوشه بندی c-means فازی، مرکز نقاط داده را می یابیم و سپس فاصله هر نقطه داده از مرکز داده شده را تا زمانی که خوشه های تشکیل شده ثابت شوند، محاسبه می کنیم.
فرض کنید نقاط داده داده شده {(1، 3)، (2، 5)، (6، 8)، (7، 9)} هستند.
خوشه‌بندی فازی نوعی الگوریتم خوشه‌بندی در یادگیری ماشینی است که به یک نقطه داده اجازه می‌دهد به بیش از یک خوشه با درجات مختلف عضویت تعلق داشته باشد. برخلاف الگوریتم‌های خوشه‌بندی سنتی، مانند k-means یا خوشه‌بندی سلسله مراتبی، که هر نقطه داده را به یک خوشه اختصاص می‌دهد، خوشه‌بندی فازی یک درجه عضویت بین 0 تا 1 را برای هر نقطه داده برای هر خوشه اختصاص می‌دهد.
کاربرد در چندین زمینه خوشه بندی فازی:
- تقسیم‌بندی تصویر: خوشه‌بندی فازی را می‌توان برای تقسیم‌بندی تصاویر با گروه‌بندی پیکسل‌هایی با ویژگی‌های مشابه، مانند رنگ یا بافت، استفاده کرد.
- تشخیص الگو: خوشه بندی فازی را می توان برای شناسایی الگوها در مجموعه داده های بزرگ با گروه بندی نقاط داده مشابه با هم استفاده کرد.
- بازاریابی: از خوشه بندی فازی می توان برای تقسیم بندی مشتریان بر اساس ترجیحات و رفتار خرید آنها استفاده کرد و به کمپین های بازاریابی هدفمندتری اجازه داد.
- تشخیص پزشکی: خوشه بندی فازی می تواند برای تشخیص بیماری ها با گروه بندی بیماران با علائم مشابه در کنار هم استفاده شود.
- پایش محیطی: خوشه بندی فازی را می توان برای شناسایی مناطق مورد توجه زیست محیطی با گروه بندی مناطق با سطوح آلودگی مشابه یا سایر شاخص های زیست محیطی استفاده کرد.
- تجزیه و تحلیل جریان ترافیک: خوشه بندی فازی را می توان برای تجزیه و تحلیل الگوهای جریان ترافیک با گروه بندی الگوهای ترافیکی مشابه با هم استفاده کرد که امکان مدیریت و برنامه ریزی ترافیک بهتر را فراهم می کند.
- ارزیابی ریسک: خوشه بندی فازی را می توان برای شناسایی و تعیین کمیت ریسک ها در زمینه های مختلف مانند مالی، بیمه و مهندسی استفاده کرد.
- بیوانفورماتیک: در زمینه بیوانفورماتیک، خوشه بندی برای تعدادی از کاربردها استفاده می شود. یکی از موارد استفاده به عنوان یک تکنیک تشخیص الگو برای تجزیه و تحلیل داده های بیان ژن از داده های توالی یابی RNA یا سایر فناوری ها است. در این مورد، ژن‌هایی با الگوهای بیان مشابه در یک خوشه گروه‌بندی می‌شوند و خوشه‌های مختلف الگوهای بیانی متمایز و کاملاً جدا شده را نشان می‌دهند. استفاده از خوشه‌بندی می‌تواند بینشی در مورد عملکرد و تنظیم ژن ارائه دهد. از آنجایی که خوشه‌بندی فازی به ژن‌ها اجازه می‌دهد به بیش از یک خوشه تعلق داشته باشند، امکان شناسایی ژن‌هایی را فراهم می‌کند که به طور مشروط تنظیم‌شده یا هم‌بیان می‌شوند. برای مثال، یک ژن ممکن است بیش از یک فاکتور رونویسی روی آن تأثیر می گذارد و یک ژن ممکن است پروتئینی را رمزگذاری کند که بیش از یک عملکرد دارد. بنابراین، خوشه بندی فازی مناسب تر از خوشه بندی سخت است.
مزایای خوشه بندی فازی:
- انعطاف‌پذیری: خوشه‌بندی فازی امکان همپوشانی خوشه‌ها را فراهم می‌کند، که می‌تواند زمانی مفید باشد که داده‌ها ساختار پیچیده‌ای دارند یا زمانی که مرزهای کلاس مبهم یا همپوشانی وجود دارد.
- استحکام: خوشه بندی فازی می تواند نسبت به نقاط پرت و نویز در داده ها قوی تر باشد، زیرا امکان انتقال تدریجی از یک خوشه به خوشه دیگر را فراهم می کند.
- قابلیت تفسیر: خوشه بندی فازی درک دقیق تری از ساختار داده ها را فراهم می کند، زیرا امکان نمایش دقیق تری از روابط بین نقاط داده و خوشه ها را فراهم می کند.
معایب خوشه بندی فازی:
- پیچیدگی: الگوریتم‌های خوشه‌بندی فازی می‌توانند از نظر محاسباتی گران‌تر از الگوریتم‌های خوشه‌بندی سنتی باشند، زیرا به بهینه‌سازی بیش از چندین درجه عضویت نیاز دارند.
- انتخاب مدل: انتخاب تعداد مناسب خوشه ها و توابع عضویت می تواند چالش برانگیز باشد و ممکن است به دانش تخصصی یا آزمون و خطا نیاز داشته باشد.
خوشه بندی c-means فازی را می توان الگوریتم بهتری در مقایسه با الگوریتم k-means در نظر گرفت. بر خلاف الگوریتم k-means، که در آن نقاط داده منحصراً به یک خوشه تعلق دارند، نقاط داده در الگوریتم c-means فازی می توانند به بیش از یک خوشه با احتمال تعلق داشته باشند. در نتیجه، خوشه بندی c-means فازی نتایج نسبتاً بهتری را برای مجموعه داده های همپوشانی ارائه می دهد.
مراحل پیاده سازی الگوریتم :
مرحله 1: نقاط داده را به تعداد دلخواه خوشه به صورت تصادفی مقداردهی کنید.
فرض کنید 2 خوشه وجود دارد که داده ها باید در آنها تقسیم شوند و نقطه داده را به طور تصادفی مقدار دهی اولیه می کنند. هر نقطه داده در هر دو خوشه با مقداری عضویت قرار دارد که می توان هر چیزی را در حالت اولیه فرض کرد.
جدول زیر مقادیر نقاط داده را به همراه عضویت آنها (گاما) در هر خوشه نشان می دهد.
مرحله 2: مرکز را پیدا کنید.
فرمول برای یافتن مرکز (V) به صورت زیر است:
در جایی که μ مقدار عضویت فازی نقطه داده است، m پارامتر فازی است (به طور کلی 2 گرفته می شود)، و xk نقطه داده است.
اینجا،
مرحله 3: فاصله هر نقطه از مرکز را پیدا کنید.
به طور مشابه، فاصله تمام نقاط دیگر از هر دو مرکز محاسبه می شود.
مرحله 4: به روز رسانی مقادیر عضویت.
برای نقطه 1 مقادیر عضویت جدید عبارتند از:
[{ [(1.2)2 / (1.2)2] + [(1.2)2 / (6.79)2]} ^ {(1 / (2 – 1))} ] -1 = 0.96
[{ [(6.79)2 / (6.79)2] + [(6.79)2 / (1.2)2]} ^ {(1 / (2 – 1))} ] -1 = 0.04
از سوی دیگر،
به طور مشابه، تمام مقادیر عضویت دیگر را محاسبه کرده و ماتریس را به روز کنید.
مرحله 5: مراحل (2-4) را تکرار کنید تا مقادیر ثابت برای مقادیر عضویت به دست آید یا تفاوت کمتر از مقدار تلورانس باشد (مقدار کوچکی که تا آن تفاوت در مقادیر دو به‌روزرسانی متوالی پذیرفته می‌شود).
مرحله 6: مقادیر عضویت به دست آمده را غیرفازی کنید.
نحوه کار الگوریتم FCM (ریاضی) :
این الگوریتم با اختصاص عضویت به هر نقطه داده مربوط به هر مرکز خوشه بر اساس کار می کند
فاصله بین مرکز خوشه و نقطه داده. بیشتر داده ها به مرکز خوشه نزدیک است
عضویت در مرکز خوشه خاص واضح است که جمع عضویت هر نقطه داده باید باشد
برابر با یک پس از هر تکرار، عضویت و مراکز خوشه طبق فرمول به روز می شوند:
جایی که،
‘n’ تعداد نقاط داده است. ‘vj’ نشان دهنده مرکز خوشه j ام است. ‘m’ شاخص فازی m € [1, ∞] است. ‘c’ نشان دهنده تعداد مرکز خوشه است. ‘µij’ نشان دهنده عضویت داده های ith در مرکز خوشه j ام است. ‘dij’ نشان دهنده فاصله اقلیدسی بین داده ith و مرکز خوشه j است.
هدف اصلی الگوریتم c-means فازی این است که:
جایی که،
‘||xi – vj||’ فاصله اقلیدسی بین داده ith و مرکز خوشه j است.
مراحل الگوریتمی برای فازی c-به معنی خوشه بندی
اجازه دهید X = {x1, x2, x3 …, xn} مجموعه نقاط داده و V = {v1, v2, v3 …, vc} مجموعه مراکز باشد.
1) به طور تصادفی مراکز خوشه “c” را انتخاب کنید.
2) عضویت فازی ‘µij’ را با استفاده از:
3) مراکز فازی ‘vj’ را با استفاده از:
4) مرحله 2) و 3) را تکرار کنید تا حداقل مقدار ‘J’ به دست آید یا ||U(k+1) – U(k)|| < β.
جایی که،
“k” مرحله تکرار است.
‘β’ معیار خاتمه بین [0، 1] است.
“U = (µij)n*c” ماتریس عضویت فازی است.
“J” تابع هدف است.
مثال
برای درک بهتر این اصل، یک مثال کلاسیک از داده های تک بعدی در زیر در محور x آورده شده است.
این مجموعه داده را می توان به طور سنتی به دو خوشه گروه بندی کرد. با انتخاب یک آستانه در محور x، داده ها به دو خوشه تقسیم می شوند. همانطور که در تصویر زیر مشاهده می شود، خوشه های به دست آمده با ‘A’ و ‘B’ برچسب گذاری شده اند. بنابراین هر نقطه متعلق به مجموعه داده دارای ضریب عضویت 1 یا 0 خواهد بود. این ضریب عضویت هر نقطه داده مربوطه با گنجاندن محور y نشان داده می شود.
در خوشه بندی فازی، هر نقطه داده می تواند عضویت در خوشه های متعدد داشته باشد. با کاهش تعریف ضرایب عضویت از 1 یا 0، این مقادیر می توانند از هر مقداری از 1 تا 0 متغیر باشند. تصویر زیر مجموعه داده های خوشه بندی قبلی را نشان می دهد، اما اکنون خوشه بندی c-means فازی اعمال شده است. ابتدا، ممکن است یک مقدار آستانه جدید که دو خوشه را تعریف می کند، تولید شود. در مرحله بعد، ضرایب عضویت جدید برای هر نقطه داده بر اساس مرکز خوشه ها و همچنین فاصله از هر مرکز خوشه ایجاد می شود.
