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

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

یادگیری ماشین و داده‌کاوی
موضوع‌ها طبقه‌بندی آماری خوشه‌بندی تحلیل رگرسیون روش تشخیص ناهنجاری یادگیری قانون وابستگی یادگیری تقویتی Structured prediction Feature engineering Feature learning یادگیری ماشین برخط یادگیری نیمه‌نظارتی یادگیری بی‌نظارت Learning to rank Grammar induction
یادگیری با نظارت (طبقه‌بندی آماری • تحلیل رگرسیون) یادگیری درخت تصمیم Ensembles (Bagging, بوستینگ، جنگل تصادفی) k-NN رگرسیون خطی دسته‌بندی کننده بیز ساده شبکه‌های عصبی مصنوعی رگرسیون لجستیک پرسپترون Relevance vector machine (RVM) ماشین بردار پشتیبانی
خوشه‌بندی BIRCH خوشه‌بندی سلسله‌مراتبی خوشه‌بندی کی-میانگین الگوریتم امید ریاضی–بیشینه کردن DBSCAN OPTICS انتقال میانگین
کاهش ابعاد تحلیل عاملی CCA تحلیل مؤلفه‌های مستقل آنالیز افتراقی خطی فاکتورگیری نامنفی ماتریس تحلیل مؤلفه‌های اصلی t-SNE
پیش‌بینی ساختاریافته مدل‌های گرافیکی (شبکه‌های بیزی، میدان تصادفی شرطی، مدل پنهان مارکف)
روش تشخیص ناهنجاری الگوریتم کی-نزدیکترین همسایه Local outlier factor
شبکه عصبی مصنوعی خودرمزگذار یادگیری عمیق پرسپترون چندلایه RNN Restricted Boltzmann machine SOM شبکه عصبی پیچشی
یادگیری تقویتی کیو-یادگیری SARSA یادگیری تفاوت زمانی
نظریه Bias-variance dilemma نظریه یادگیری محاسباتی Empirical risk minimization Occam learning یادگیری احتمالا تقریبا صحیح Statistical learning VC theory
حوزه‌های یادگیری ماشین NIPS ICML ML JMLR ArXiv:cs.LG

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

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

توضیحات

با توجه به مجموعه‌ای از مشاهدات ${\displaystyle (x_{1},x_{2},\cdots ,x_{n})}$ که در آن هر یک از مشاهدات یک بردار حقیقی ${\displaystyle d}$-بعدی است. خوشه بندی کی-میانگین با هدف پارتیشن‌بندی ${\displaystyle n}$ مشاهدات به ${\displaystyle k\leq n}$ مجموعه ${\displaystyle S=\{S_{1},S_{2},\cdots ,S_{k}\}}$ است به طوری که مجموع مربع اختلاف از میانگین (یعنی واریانس) برای هر خوشه حداقل شود. تعریف دقیق ریاضی آن به این شکل است:

${\displaystyle {\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})}$

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

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

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

الگوریتم

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

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

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

1. ابتدا ${\displaystyle k}$ میانگین یعنی ${\displaystyle \left(\mu _{1}^{(0)},\mu _{2}^{(0)},\cdots ,\mu _{k}^{(0)}\right)}$ را که نماینده خوشه‌ها هستند، بصورت تصادفی مقدار دهی می‌کنیم.
2. سپس، این دو مرحله پایین را به تناوب چندین بار اجرا می‌کنیم تا میانگین‌ها به یک ثبات کافی برسند و یا مجموع واریانس‌های خوشه‌ها تغییر چندانی نکنند:
   • از میانگین ها ${\displaystyle k}$خوشه می‌سازیم، خوشه ${\displaystyle i}$ام در زمان ${\displaystyle t}$ تمام داده‌هایی هستند که از لحاظ اقلیدسی کمترین فاصله را با میانگین ${\displaystyle \mu _{i}^{(t)}}$ یعنی میانگین ${\displaystyle i}$ام در زمان ${\displaystyle t}$ دارند[7]. به زبان ریاضی خوشه ${\displaystyle i}$ام در زمان ${\displaystyle t}$ برابر خواهد بود با:
   • ${\displaystyle 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 \}}}$
3. حال میانگین‌ها را بر اساس این خوشه های جدید به این شکل بروز می‌کنیم:[8]
   • ${\displaystyle \mu _{i}^{(t+1)}={\frac {1}{|S_{i}^{(t)}|}}\sum _{x_{j}\in S_{i}^{(t)}}x_{j}}$
4. در نهایت میانگین‌های مرحله آخر (در زمان ${\displaystyle T}$) یعنی ${\displaystyle \left(\mu _{1}^{(T)},\mu _{2}^{(T)},\cdots ,\mu _{k}^{(T)}\right)}$ خوشه‌ها را نمایندگی خواهند کرد.

الگوریتم کی-میانگین را می‌توان با پویانمایی پایین برای ${\displaystyle k=3}$ به تصویر کشید.

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

نگارخانه

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

منابع

1. MacQueen, J. B. (1967). Some Methods for classification and Analysis of Multivariate Observations. Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability. 1. University of California Press. pp. 281&ndash, 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. (به French). 4 (12): 801&ndash, 804. MR 0090073. Zbl 0079.16403.
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&ndash, 137. doi:10.1109/TIT.1982.1056489. Retrieved 2009-04-15.
4. E.W. Forgy (1965). "Cluster analysis of multivariate data: efficiency versus interpretability of classifications". Biometrics. 21: 768–769. JSTOR 2528559.
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&ndash, 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.
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&ndash, 108. JSTOR 2346830.