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

خوشه‌بندی کی-میانگین (به انگلیسی: k-means clustering) روشی در کمی‌سازی بردارهاست که در اصل از پردازش سیگنال گرفته شده و برای آنالیز خوشه‌بندی در داده‌کاوی محبوب است. کی-میانگین خوشه‌بندی با هدف تجزیه $n$

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

تاریخچه الگوریتم

اصطلاح کی-میانگین (به انگلیسی: k-means clustering) برای اولین بار توسط جیمز مک‌کوین در سال ۱۹۶۷ مورد استفاده قرار گرفت، هرچند این ایده به هوگو استینگز در سال ۱۹۵۷ باز می‌گردد. این الگوریتم ابتدا توسط استوارت لویید در سال ۱۹۵۷ به عنوان یک تکنیک برای مدولاسیون کد پالس پیشنهاد شد و تا سال ۱۹۸۲ خارج از آزمایشگاه‌های بل به انتشار نرسید. فورجی در سال ۱۹۶۵ الگوریتمی مشابه را منتشر کرد، به همین دلیل است که بعضی اوقات این الگوریتم، لویید فورجی هم نامیده می‌شود.

توضیحات

با توجه به مجموعه‌ای از مشاهدات $(x_{1},x_{2},\cdots ,x_{n})$

که در آن هر یک از مشاهدات یک بردار حقیقی $d$ -بعدی است. خوشه‌بندی کی-میانگین با هدف پارتیشن‌بندی $n$ مشاهدات به

k\leq n

مجموعه

S=\{S_{1},S_{2},\cdots ,S_{k}\}

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

{\underset {\mathbf {S} }{\operatorname {arg\,min} }}\sum _{i=1}^{k}\sum _{\mathbf {x} \in S_{i}}\left\|\mathbf {x} -{\boldsymbol {\mu }}_{i}\right\|^{2}={\underset {\mathbf {S} }{\operatorname {arg\,min} }}\sum _{i=1}^{k}|S_{i}|\operatorname {Var} (S_{i})

که در آن $\mu _{i}$

میانگین نقاط در $S_{i}$ است. این معادل است با به حداقل رساندن دو به دو مربع انحراف از نقاط در همان خوشه:

\sum _{{\text{Cluster }}C_{i}}\,\sum _{{\text{Dimension }}d}\,\sum _{x,y\,\in \,C_{i}}(x_{d}-y_{d})^{2}

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

الگوریتم

الگوریتم استاندارد

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

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

ابتدا $k$ میانگین یعنی $\left(\mu _{1}^{(0)},\mu _{2}^{(0)},\cdots ,\mu _{k}^{(0)}\right)$ را که نماینده خوشه‌ها هستند، بصورت تصادفی مقداردهی می‌کنیم.
سپس، این دو مرحله پایین را به تناوب چندین بار اجرا می‌کنیم تا میانگین‌ها به یک ثبات کافی برسند و یا مجموع واریانس‌های خوشه‌ها تغییر چندانی نکنند:
- از میانگین‌ها $k$ خوشه می‌سازیم، خوشه $i$ ام در زمان $t$ تمام داده‌هایی هستند که از لحاظ اقلیدسی کمترین فاصله را با میانگین $\mu _{i}^{(t)}$ یعنی میانگین $i$ ام در زمان $t$ دارند. به زبان ریاضی خوشه $i$ ام در زمان $t$ برابر خواهد بود با:
- $S_{i}^{(t)}={\big \{}x_{p}:{\big \|}x_{p}-\mu _{i}^{(t)}{\big \|}^{2}\leq {\big \|}x_{p}-\mu _{j}^{(t)}{\big \|}^{2}\ \forall j,1\leq j\leq k{\big \}}$
حال میانگین‌ها را بر اساس این خوشه های جدید به این شکل بروز می‌کنیم:
- $\mu _{i}^{(t+1)}={\frac {1}{|S_{i}^{(t)}|}}\sum _{x_{j}\in S_{i}^{(t)}}x_{j}$
در نهایت میانگین‌های مرحله آخر (در زمان $T$ ) یعنی $\left(\mu _{1}^{(T)},\mu _{2}^{(T)},\cdots ,\mu _{k}^{(T)}\right)$ خوشه‌ها را نمایندگی خواهند کرد.

الگوریتم کی-میانگین را می‌توان با پویانمایی پایین برای $k=3$

به تصویر کشید.

همگرایی کی-میانگین

نگارخانه

همگرایی کی-میانگین

منابع

↑ MacQueen, J. B. (1967). Some Methods for classification and Analysis of Multivariate Observations. Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability. Vol. 1. University of California Press. pp. 281–297. MR 0214227. Zbl 0214.46201. Retrieved 2009-04-07.
↑ Steinhaus, H. (1957). "Sur la division des corps matériels en parties". Bull. Acad. Polon. Sci. (به فرانسوی). 4 (12): 801–804. MR 0090073. Zbl 0079.16403.
↑ Lloyd, S. P. (1957). "Least square quantization in PCM". Bell Telephone Laboratories Paper. Published in journal much later: Lloyd., S. P. (1982). "Least squares quantization in PCM" (PDF). IEEE Transactions on Information Theory. 28 (2): 129–137. doi:10.1109/TIT.1982.1056489. Retrieved 2009-04-15.
↑ E.W. Forgy (1965). "Cluster analysis of multivariate data: efficiency versus interpretability of classifications". Biometrics. 21: 768–769. JSTOR 2528559.
↑ Kriegel, Hans-Peter; Schubert, Erich; Zimek, Arthur (2016). "The (black) art of runtime evaluation: Are we comparing algorithms or implementations?". Knowledge and Information Systems. 52: 341–378. doi:10.1007/s10115-016-1004-2. ISSN 0219-1377.
↑ MacKay, David (2003). "Chapter 20. An Example Inference Task: Clustering" (PDF). Information Theory, Inference and Learning Algorithms. Cambridge University Press. pp. 284–292. ISBN 0-521-64298-1. MR 2012999.
↑ Since the square root is a monotone function, this also is the minimum Euclidean distance assignment.
↑ Hartigan, J. A.; Wong, M. A. (1979). "Algorithm AS 136: A k-Means Clustering Algorithm". Journal of the Royal Statistical Society, Series C. 28 (1): 100–108. JSTOR 2346830.

[macqueen19672-1] MacQueen, J. B. (1967). Some Methods for classification and Analysis of Multivariate Observations. Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability. Vol. 1. University of California Press. pp. 281–297. MR 0214227. Zbl 0214.46201. Retrieved 2009-04-07.

[2] Steinhaus, H. (1957). "Sur la division des corps matériels en parties". Bull. Acad. Polon. Sci. (به فرانسوی). 4 (12): 801–804. MR 0090073. Zbl 0079.16403.

[lloyd19572-3] Lloyd, S. P. (1957). "Least square quantization in PCM". Bell Telephone Laboratories Paper. Published in journal much later: Lloyd., S. P. (1982). "Least squares quantization in PCM" (PDF). IEEE Transactions on Information Theory. 28 (2): 129–137. doi:10.1109/TIT.1982.1056489. Retrieved 2009-04-15.

[forgy652-4] E.W. Forgy (1965). "Cluster analysis of multivariate data: efficiency versus interpretability of classifications". Biometrics. 21: 768–769. JSTOR 2528559.

[:12-5] Kriegel, Hans-Peter; Schubert, Erich; Zimek, Arthur (2016). "The (black) art of runtime evaluation: Are we comparing algorithms or implementations?". Knowledge and Information Systems. 52: 341–378. doi:10.1007/s10115-016-1004-2. ISSN 0219-1377.

[6] MacKay, David (2003). "Chapter 20. An Example Inference Task: Clustering" (PDF). Information Theory, Inference and Learning Algorithms. Cambridge University Press. pp. 284–292. ISBN 0-521-64298-1. MR 2012999.

[7] Since the square root is a monotone function, this also is the minimum Euclidean distance assignment.

[hartigan19792-8] Hartigan, J. A.; Wong, M. A. (1979). "Algorithm AS 136: A k-Means Clustering Algorithm". Journal of the Royal Statistical Society, Series C. 28 (1): 100–108. JSTOR 2346830.