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

{{یادگیری ماشین}}
'''خوشه‌بندی کی-میانگین''' {{به انگلیسی|k-means clustering}} روشی در کمی‌سازی بردارهاست که در اصل از [[پردازش سیگنال]] گرفته شده و برای [[خوشه‌بندی|آنالیز خوشه‌بندی]] در [[داده‌کاوی]] محبوب است. ''کی-میانگین'' خوشه‌بندی با هدف [[افراز مجموعه|تجزیه]] ''<math>n </math>'' مشاهدات به ''<math>k </math>'' خوشه است که در آن هر یک از مشاهدات متعلق به [[خوشه‌بندی|خوشه]]<nowiki/>ای با نزدیکترین میانگین آن است، این میانگین به عنوان پیش‌نمونه استفاده می‌شود. این به پارتیشن‌بندی داده‌های به یک [[دیاگرام ورونوی]] تبدیل می‌شود.












== تاریخچه الگوریتم ==
اصطلاح کی-میانگین {{به انگلیسی|K-Means Clustering}} برای اولین بار توسط جیمز بی مک‌کوین (استاد دانشگاه کالیفرنیا) در سال ۱۹۶۷ مورد استفاده قرار گرفت،<ref name="macqueen19672">{{cite conference|last=MacQueen|first=J. B.|year=1967|title=Some Methods for classification and Analysis of Multivariate Observations|url=http://projecteuclid.org/euclid.bsmsp/1200512992|conference=Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability|publisher=University of California Press|volume=1|pages=281&ndash;297|mr=0214227|zbl=0214.46201|accessdate=2009-04-07}}</ref> هرچند این ایده به [[هوگو استین‌هاوس]] در سال ۱۹۵۷ باز می‌گردد.<ref>{{cite journal|last=Steinhaus|first=H.|authorlink=Hugo Steinhaus|year=1957|title=Sur la division des corps matériels en parties|journal=Bull. Acad. Polon. Sci.|language=French|volume=4|issue=12|pages=801&ndash;804|mr=0090073|zbl=0079.16403}}</ref> این الگوریتم ابتدا توسط استوارت لویید در سال ۱۹۵۷ به عنوان یک تکنیک برای [[مدولاسیون کد پالس]] پیشنهاد شد و تا سال ۱۹۸۲ خارج از [[آزمایشگاه‌های بل]] به انتشار نرسید.<ref name="lloyd19572">{{cite journal|last=Lloyd|first=S. P.|year=1957|title=Least square quantization in PCM|journal=Bell Telephone Laboratories Paper}} Published in journal much later: {{cite journal|last=Lloyd.|first=S. P.|year=1982|title=Least squares quantization in PCM|url=http://www.cs.toronto.edu/~roweis/csc2515-2006/readings/lloyd57.pdf|journal=[[IEEE Transactions on Information Theory]]|volume=28|issue=2|pages=129&ndash;137|doi=10.1109/TIT.1982.1056489|accessdate=2009-04-15}}</ref> [[ادوارد دبلیو فورجی|فورجی]] در سال ۱۹۶۵ الگوریتمی مشابه را منتشر کرد، به همین دلیل این الگوریتم، '''الگوریتم لویید-فورجی''' نیز نامیده می‌شود.<ref name="forgy652">{{Cite journal|author=E.W. Forgy|year=1965|title=Cluster analysis of multivariate data: efficiency versus interpretability of classifications|url=https://archive.org/details/sim_biometrics_1965-09_21_3/page/768|journal=Biometrics|volume=21|pages=768–769|jstor=2528559}}</ref>

== توضیحات ==
با توجه به مجموعه‌ای از مشاهدات <math>(x_1, x_2, \cdots, x_n) </math> که در آن هر یک از مشاهدات یک بردار حقیقی ''<math>d </math>''-بعدی است. خوشه‌بندی کی-میانگین با هدف پارتیشن‌بندی ''<math>n </math>'' مشاهدات به <math>k\leq n </math> مجموعه <math>S = \{S_1, S_2, \cdots, S_k\} </math> است به طوری که مجموع مربع اختلاف از میانگین (یعنی [[واریانس]]) برای هر خوشه حداقل شود. تعریف دقیق ریاضی آن به این شکل است:
<center><math>\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) </math></center>
که در آن ''<math>\mu_i </math>'' میانگین نقاط در ''<math>S_i </math>'' است. این معادل است با به حداقل رساندن دو به دو مربع انحراف از نقاط در همان خوشه:
<center><math>\sum_{\text{Cluster }C_i} \,\sum_{\text{Dimension }d} \,\sum_{x,y\,\in\, C_i} (x_d-y_d)^2</math></center>
چون کل واریانس ثابت است، از [[قانون واریانس کلی]] می‌توان نتیجه گرفت که این معادله برابر است با بیشینه کردن مربع انحرافات بین نقاط خوشه‌های مختلف (BCSS).<ref name=":12">{{cite journal|last1=Kriegel|first1=Hans-Peter|authorlink=Hans-Peter Kriegel|last2=Schubert|first2=Erich|last3=Zimek|first3=Arthur|authorlink3=Arthur Zimek|year=2016|title=The (black) art of runtime evaluation: Are we comparing algorithms or implementations?|journal=Knowledge and Information Systems|volume=52|pages=341–378|doi=10.1007/s10115-016-1004-2|issn=0219-1377}}</ref> 

== الگوریتم ==
=== الگوریتم استاندارد ===
رایج‌ترین الگوریتم کی-میانگین با استفاده از یک تکرار شونده پالایش کار می‌کند. این الگوریتم به طور معمول با نام ''الگوریتم کی-''میانگین شناخته می‌شود،‌ اما در میان جامعه علوم کامپیوتر،‌ اغلب آن را با عنوان [[:en:Lloyd's_algorithm|الگوریتم لوید]] می‌شناسند.

الگوریتم به این شکل عمل می‌کند:<ref>{{Cite book|url=http://www.inference.phy.cam.ac.uk/mackay/itila/book.html|title=Information Theory, Inference and Learning Algorithms|last=MacKay|first=David|authorlink=David MacKay (scientist)|publisher=Cambridge University Press|year=2003|isbn=0-521-64298-1|pages=284&ndash;292|chapter=Chapter 20. An Example Inference Task: Clustering|chapterurl=http://www.inference.phy.cam.ac.uk/mackay/itprnn/ps/284.292.pdf|mr=2012999|ref=mackay2003}}</ref>

# ابتدا ''<math>k </math>'' میانگین یعنی <math>\left(\mu_1^{(0)}, \mu_2^{(0)}, \cdots, \mu_k^{(0)}\right) </math> را که نماینده خوشه‌ها هستند، به‌صورت تصادفی مقداردهی می‌کنیم.
# سپس، این دو مرحله پایین را به تناوب چندین بار اجرا می‌کنیم تا میانگین‌ها به یک ثبات کافی برسند و یا مجموع واریانس‌های خوشه‌ها تغییر چندانی نکنند:
#* از میانگین‌ها ''<math>k </math>''خوشه می‌سازیم، خوشه <math>i</math>ام در زمان <math>t</math> تمام داده‌هایی هستند که از لحاظ اقلیدسی کمترین فاصله را با میانگین <math>\mu^{(t)}_i</math> یعنی میانگین <math>i</math>ام در زمان <math>t</math> دارند<ref>Since the square root is a monotone function, this also is the minimum Euclidean distance assignment.</ref>. به زبان ریاضی خوشه <math>i</math>ام در زمان <math>t</math> برابر خواهد بود با:
#*<math>S_i^{(t)} = \big \{ x_p : \big \| x_p - \mu^{(t)}_i \big \|^2 \le \big \| x_p - \mu^{(t)}_j \big \|^2 \ \forall j, 1 \le j \le k \big\}</math>
# حال میانگین‌ها را بر اساس این خوشه های جدید به این شکل بروز می‌کنیم:<ref name="hartigan19792">{{Cite journal|last1=Hartigan|first1=J. A.|last2=Wong|first2=M. A.|year=1979|title=Algorithm AS 136: A ''k''-Means Clustering Algorithm|journal=[[Journal of the Royal Statistical Society, Series C]]|volume=28|issue=1|pages=100&ndash;108|jstor=2346830}}</ref>
#*<math>\mu^{(t+1)}_i = \frac{1}{|S^{(t)}_i|} \sum_{x_j \in S^{(t)}_i} x_j </math>
# در نهایت میانگین‌های مرحله آخر (در زمان ''<math>T </math>'') یعنی <math>\left(\mu_1^{(T)}, \mu_2^{(T)}, \cdots, \mu_k^{(T)}\right) </math> خوشه‌ها را نمایندگی خواهند کرد.

الگوریتم کی-میانگین را می‌توان با پویانمایی پایین برای <math>k=3 </math> به تصویر کشید.
[[پرونده:K-means_convergence.gif|پیوند=https://en.wikipedia.org/wiki/File:K-means_convergence.gif|جایگزین=همگرایی کی-میانگین|بندانگشتی|همگرایی کی-میانگین]]
<br />

<br />



== کاربردها ==
خوشه‌بندی کی‌میانگین خوشه‌بندی حتی برای مجموعه داده‌های بزرگ به‌ویژه هنگام استفاده از روش‌های اکتشافی مانند [[:en:Lloyd's_algorithm|Lloyd's algorithm]] بسیار آسان است. این با موفقیت در [[تقسیم‌بندی بازار|تقسیم‌بندی بازار]]، [[بینایی رایانه‌ای]] و [[نجوم]] در میان بسیاری از حوزه‌های دیگر مورد استفاده قرار گرفته است. اغلب به عنوان یک مرحله پیش پردازش برای الگوریتم های دیگر استفاده می شود، به عنوان مثال برای پیدا کردن یک پیکربندی شروع.

=== کمیت‌سازی برداری ===
{{Main|کمیت‌سازی برداری}}
[[File:Rosa_Gold_Glow_2_small_noblue.png|left|frame| (تصویر رنگی دو کاناله (برای اهداف تصویری - فقط کانال های قرمز و سبز).]]
[[File:Rosa_Gold_Glow_2_small_noblue_color_space.png|left|thumb|250x250px|کمی سازی برداری رنگ های موجود در تصویر بالا به سلول های ورونوی با استفاده از خوشه‌بندی کی‌میانگین]]
خوشه‌بندی کی‌میانگین از پردازش سیگنال سرچشمه می گیرد و هنوز در این حوزه کاربرد دارد. به عنوان مثال، در [[گرافیک کامپیوتری]]، [[رنگ‌سنجی]] وظیفه کاهش [[پالت (محاسبات)| پالت رنگ]] یک تصویر به تعداد ثابتی ''k'' از رنگ‌ها است. الگوریتم کی‌میانگین به راحتی می تواند برای این کار استفاده شود و نتایج قابل رقابتی ایجاد کند. یک مورد استفاده برای این رویکرد [[بخش‌بندی تصویر]] است. کاربردهای دیگر کمیت‌سازی برداری عبارتند از [[نمونه‌گیری (آمار)|نمونه‌گیری غیرتصادفی]]، زیرا کی‌میانگین به راحتی می‌تواند برای انتخاب ''k'' نمونه متفاوت اما مقدماتی از یک [[مجموعه داده]] بزرگ برای آنالیزهای بیشتر استفاده شود.


=== تحلیل خوشه‌ای ===
{{Main|خوشه‌بندی}}

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



=== یادگیری ویژگی ===
خوشه‌بندی کی‌میانگین به عنوان یک مرحله [[یادگیری ویژگی]] (یا [[یادگیری دیکشنری]]) در ([[یادگیری نیمه نظارتی]] یا [[یادگیری خودران (خودسازمانده)]] استفاده شده است.
<ref name="Coates20122">{{cite book |year=2012 |chapter=Learning feature representations with ''k''-means |title=Neural Networks: Tricks of the Trade |publisher=Springer |chapter-url=https://cs.stanford.edu/~acoates/papers/coatesng_nntot2012.pdf |last2=Ng |first2=Andrew Y. |last1=Coates |first1=Adam |editor=Montavon, G. |editor2=Orr, G. B. |editor3=Müller, K.-R. |editor3-link=Klaus-Robert Müller}}</ref>

رویکرد اصلی ابتدا آموزش به وسیله الگوریتم خوشه‌بندی کی‌میانگین با استفاده از داده‌های آموزشی ورودی (که نیازی به برچسب گذاری ندارند) است. سپس تصویر کردن هر داده ورودی در فضای ویژگی جدید، و یک تابع «رمزگذاری» مانند مبنای ضرب ماتریس داده‌ها با مکان‌های مرکز داده‌ها، که فاصله هر نمونه را تا مرکز آن محاسبه می کند، یا به سادگی یک تابع نشانگر برای نزدیکترین مرکز،<ref name="Coates20122" /><ref>{{cite conference |last1=Csurka |first1=Gabriella |last2=Dance |first2=Christopher C. |last3=Fan |first3=Lixin |last4=Willamowski |first4=Jutta |last5=Bray |first5=Cédric |year=2004 |title=Visual categorization with bags of keypoints |url=https://www.cs.cmu.edu/~efros/courses/LBMV07/Papers/csurka-eccv-04.pdf |conference=ECCV Workshop on Statistical Learning in Computer Vision }}</ref>
و یا تبدیل هموار فاصله‌ها.
.<ref name="coates20112">{{cite conference |last1=Coates |first1=Adam |last2=Lee |first2=Honglak |last3=Ng |first3=Andrew Y. |year=2011 |title=An analysis of single-layer networks in unsupervised feature learning |url=http://www.stanford.edu/~acoates/papers/coatesleeng_aistats_2011.pdf |url-status=dead |conference=International Conference on Artificial Intelligence and Statistics (AISTATS) |archive-url=https://web.archive.org/web/20130510120705/http://www.stanford.edu/~acoates/papers/coatesleeng_aistats_2011.pdf |archive-date=2013-05-10 }}</ref>

روش دیگر، تبدیل فاصله نمونه-خوشه از طریق یک [[مدل ترکیبی|تابع پایه شعاعی گاوسی]] می‌باشد که لایه پنهان یک [[:en:Radial_basis_function_network|شبکه تابع پایه شعاعی]] را به دست می‌آورد.<ref name="schwenker2">{{cite journal |last1=Schwenker |first1=Friedhelm |last2=Kestler |first2=Hans A. |last3=Palm |first3=Günther |year=2001 |title=Three learning phases for radial-basis-function networks |journal=Neural Networks |volume=14 |issue=4–5 |pages=439–458 |citeseerx=10.1.1.109.312 |doi=10.1016/s0893-6080(01)00027-2 |pmid=11411631 }}</ref> این استفاده از کی‌میانگین به طور موفقیت آمیزی با [[طبقه بندی خطی|طبقه‌بندی خطی]] های ساده برای یادگیری نیمه نظارتی در [[پردازش زبان طبیعی|پردازش زبان طبیعی (NLP)]] (به ویژه برای [[:en:Named-entity_recognition|دسته‌بندی موجودیت‌های نام‌دار]]) ترکیب شده است.<ref>{{cite conference |last1=Lin |first1=Dekang |last2=Wu |first2=Xiaoyun |year=2009 |title=Phrase clustering for discriminative learning |url=http://www.aclweb.org/anthology/P/P09/P09-1116.pdf |conference=Annual Meeting of the [[Association for Computational Linguistics|ACL]] and IJCNLP |pages=1030–1038 }}</ref> در [[بینایی رایانه‌ای]]. در یک کار تشخیص شی مشخص شد که عملکرد قابل مقایسه‌ای با رویکردهای یادگیری ویژگی پیچیده‌تری مانند [[خودرمزگذار]] و [[ماشین بولتزمن محدود شده]]<ref name="coates20112" /> ارائه می‌دهد. با این حال، معمولاً برای عملکرد معادل به داده‌های بیشتری نیاز دارد، زیرا هر نقطه داده تنها به یک "ویژگی" کمک می‌کند.<ref name="Coates20122" />








== نگارخانه ==
<gallery>
File:K-means convergence.gif|همگرایی کی-میانگین
Image:K Means Example Step 1.svg|<!--1. ''k'' initial "means" (in this case ''k''=3) are randomly generated within the data domain (shown in color).-->
Image:K Means Example Step 2.svg|<!--2. ''k'' clusters are created by associating every observation with the nearest mean. The partitions here represent the [[دیاگرام ورونوی]] generated by the means.-->
Image:K Means Example Step 3.svg|<!--3. The [[مرکزوار]] of each of the ''k'' clusters becomes the new mean.-->
Image:K Means Example Step 4.svg|<!--4. Steps 2 and 3 are repeated until convergence has been reached.-->
</gallery>

== منابع ==
{{پانویس|۲}}

[[رده:الگوریتم‌های آماری]]
[[رده:روش‌های خوشه‌بندی]]