خوشه‌بندی کی-میانگین

خوشه‌ بندی کی-میانگین ^[۱]^[۲] یک الگوریتم برای مقداردهی نقاط اولیه مرکزی در خوشه‌ها در الگوریتم خوشه‌بندی کی-میانگین می‌باشد زیرا این مقداردهی‌ها در حالت عادی به صورت تصادفی صورت می‌پذیرد که لزوما بهینه ترین حالت نیست؛ همینطور طبق آزمایش‌ها نشان داده شده استه که استفاده از این الگوریتم در هر دو بخش سرعت و دقت نسبت به الگوریتم خوشه‌بندی کی-میانگین بهتر است و استفاده از این روش باعث بهبود قابل توجهی در الگوریتم خوشه‌بندی کی-میانگین می‌شود.

علت معرفی

الگوریتم خوشه‌بندی کی-میانگین یک روش فراگیر در خوشه‌بندی است که به دنبال کمینه کردن میانگین مربعات فواصل بین نقاط در یک خوشه است. در این الگوریتم مقدار دهی اولیه به صورت تصادفی صورت می‌پذیرد. این روش به طور گسترده ای مورد استفاده قرار گرفته و می تواند جواب هایی با تقریب مناسب و سرعت مطلوب ارائه دهد.؛ دقت کنید که مسئله پیدا کردن جواب اصلی این روش ان‌پی سخت است برای همین جواب‌ها به طور تقریبی و با همگرا شدن الگوریتم به یک جواب از طریق یک مقدار‌دهی اولیه صورت می‌پذیرد.^[۳]

با این حال الگوریتم خوشه‌بندی کی میانگین حداقل دو ضعف اساسی از لحاظ تئوری ریاضی دارد:

از لحاظ محاسباتی زمان اجرای این الگوریتم نسبت به ورودی مسئله می‌تواند "ابر چندجمله‌ای" شود و این بسته به اندازه مقادیر ورودی می‌تواند مشکل زا باشد.^[۴]
جواب های تقریبی ارائه شده توسط این الگوریتم می‌تواند فاصله زیادی با جواب بهینه مسئله داشته باشد و اطمینانی از نزدیک بودن جواب تقریبی گرفته شده از این روش با جواب بهینه مسئله وجود ندارد.

این دو مشکل اساسی با استفاده از از روش خوشه‌بندی کی-میانگین تا حد قابل قبولی بهبود می‌یابد؛ زیرا این روش با ارائه دادن یه پروسه برای انتخاب نقاط اولیه مرکزی خوشه‌ها مشکل ارائه جواب تقریب نامناسب نسبت به جواب بهینه مسئله را بهبود می‌بخشد و همچنین این روش تضمین می‌کند که جواب مسئله در مرتبه زمانی بهتری ارائه شود.

شرح الگوریتم

فرض کنید که D(x) نشان دهنده کوتاه ترین فاصله یک نقطه تا نزدیک ترین مرکز خوشه ای که تا به حال انتخاب کرده‌ایم باشد. مراحل الگوریتم خوشه بندی کی-میانگین به شرح زیر است.(کل داده را با X نشان می‌دهیم):

یک مرکز خوشه به نام c1 را به شکل یونیفورم و تصادفی در X انتخاب می‌کنیم.
مرکز جدید ci را با انتخاب $x\in X$ با احتمال $D(x)^{2}/\textstyle \sum _{x\in X}\displaystyle D(x)^{2}$ برگزیده می شود.
مرحله ۲ را انقدر تکرار می‌کنیم تا k مرکز خوشه داشته باشیم.
نقاط مرکزی ابتدایی خوشه‌ها انتخاب شدند، پس ادامه الگوریتم را مانند الگوریتم خوشه‌بندی کی-میانگین ادامه می‌دهیم.

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

منابع

↑ Arthur, D.; Vassilvitskii, S. (2007). "k-means : the advantages of careful seeding" (PDF). Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics Philadelphia, PA, USA. pp. 1027–1035. Archived from the original (PDF) on 21 August 2017. Retrieved 23 December 2022.
↑ http://theory.stanford.edu/~sergei/slides/BATS-Means.pdf Slides for presentation of method by Arthur, D. and Vassilvitskii, S.
↑ Drineas, P.; Frieze, A.; Kannan, R.; Vempala, S.; Vinay, V. (2004). "Clustering Large Graphs via the Singular Value Decomposition". Machine Learning. 56 (1–3): 9–33. doi:10.1023/B:MACH.0000033113.59016.96.
↑ Arthur, D.; Vassilvitskii, S. (2006). "How slow is the k-means method?". Proceedings of the twenty-second annual symposium on Computational geometry. ACM New York, NY, USA. pp. 144–153.

[1] Arthur, D.; Vassilvitskii, S. (2007). "k-means : the advantages of careful seeding" (PDF). Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics Philadelphia, PA, USA. pp. 1027–1035. Archived from the original (PDF) on 21 August 2017. Retrieved 23 December 2022.

[2] ttp://theory.stanford.edu/~sergei/slides/BATS-Means.pdf Slides for presentation of method by Arthur, D. and Vassilvitskii, S.

[3] Drineas, P.; Frieze, A.; Kannan, R.; Vempala, S.; Vinay, V. (2004). "Clustering Large Graphs via the Singular Value Decomposition". Machine Learning. 56 (1–3): 9–33. doi:10.1023/B:MACH.0000033113.59016.96.

[4] Arthur, D.; Vassilvitskii, S. (2006). "How slow is the k-means method?". Proceedings of the twenty-second annual symposium on Computational geometry. ACM New York, NY, USA. pp. 144–153.

[۱]

[۲]

[۳]

[۴]