الگوریتم خوشه‌بندی کا مین

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

حالا به زبان خودم

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

به طور خلاصه کا مین از مراحل زیر تشکیل شده‌ است

۱: برای تنظیم افراز اولیه دیتاست، به صورت تصادفی بردارهای مراکز خوشه انتخاب می‌شوند

۲: هر بردار سند که به نزدیکترین مرکز قرار دارند در آن خوشه قرار می‌گیرد

۳: با استفاده از معادله ۴ بردارهای مراکز خوشه‌ها باز محاسبه می‌شوند

https://screenshots.firefoxusercontent.com/images/5009065b-95c3-4839-9022-b4cb7936da26.png

۴: گام ۲ و ۳ ادامه می‌یابد تا به شرط کانورج برسیم.

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

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

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

داره می‌گه کامین کارش محلی نه جهانی

لوکال نه گلوبال

الگوریتم خوشه‌بندی کا-مینز

کا مین یکی مشهورترین الگوریتم‌های سنتی خوشه‌بندی افرازی برای اسناد متنی است. در بیشتر موارد هدف یافتن مینیمایز فاصله اقلیدسی میانگین در معادله (۱) (استفاده شده به عنوان سنجه شباهت) سنجه اسناد از مراکز خوشه که یک مرکز خوشه به عنوان مین یا سنتروید میکروی اسناد در یک کلاستر اکسپلون تعریف می‌شود.

K-means is the most popular traditional partitioning clustering algorithm for text documents. In most cases the objective is to minimize the average squared Euclidean distance given above in equation (1) (used as similarity measure) measure of documents from their cluster centers where a cluster center is defined as the mean or centroid μ of the documents in a cluster ω.
الگوریتم کا مین به وسیله انتخاب تصادفی کا در فضای جستجوی اسناد شروع می‌شود. این نقاط کا به سنتروید خوشه‌های اولیه کا ارزیابی می‌شوند. این الگوریتم سپس فاصله (یا شباهت) هر سند از همه نقاط کا را محاسبه می‌کند. این مقادیر فاصله برای تعیین هر سند به یک خوشه از کا استفاده میؤود. یک سند به یک خوشه‌ای تعیین میؤود که نزدیکتر به آن باشد. برای مثال خوشه‌ای که سنتروید فاصله‌ای کمتری از این سند، نسبت به همه سنترویدهای کا دیگر دارد در آن خوشه قرار می‌گیرد. زمانی که همه اسناد به یکی از خوشه‌ها اختصاص داده شدند.، سنتروید‌های همه کا کلاستر باز محاسبه میؤود. این فرایند با مراکز خوشه‌ای جدید که ارائه شدند تکرار می‌شود تا زمانی که ارزیابی خوشه همگرا شود یا تعداد ثابتی از تکرارها اغنا شود. کا مین بی ثبات است و کاملا به کمیت برای انتخاب جسجوهای اولیه حساس است، بنابراین همیشه یک مینمم کلی را تضمین نمی کند. به این دلیل است که از رهیافت ترکیبی با تکنیک پی.اس.اُ برای تولید یک راه حل جهانی استفاده می‌کنیم.
The K-means algorithm begins by initially selecting K random seeds in the document search space. These K points
are assumed to represent centroid of the K initial clusters. The algorithm then calculates the distance (or similarity) of
each document from all the K points. These distance values are used to assign every document to one of the K clusters.
A document is assigned to a cluster which is closest to it i.e. the cluster whose centroid has the smallest distance from
the documents, out of all such K centroids. Once all documents are assigned to one of the K clusters, the centroids of all
the K clusters is recomputed. The process is iterated with the new centroids as new cluster centers which is repeated
until cluster assignment converges or until a fixed number of iterations has been reached.
K-Means is unstable and quite sensitive to the selection of initial seeds and thus does not always guarantee a global
minimum [19]. That is why we have adopted hybridized approach with PSO technique to produce a global solution.

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