خوشه بندی k-means
خوشه‌بندي یکی از مهمترین ابزار کشف داده‌ها است که در کشف هاي تصادفی به کار گرفته می‌شود. در حال حاضر، اخذ دانش یک گلوگاه عمده در فرآیند مهندسی دانش محسوب می‌شود. الگوریتم‌هاي یادگیري ماشین و داده‌کاوي با هدف استخراج دانش از داده‌ها، به عنوان روشی براي حل این مشکل مطرح می‌باشند. یک رهیافت متداول در این زمینه روش خوشه‌بندي است که براي تصمیم‌گیري یا دسته‌بندي یا کلاس‌بندي می‌تواند تصمیمات نمادینی را به نمونه‌هاي جدید با استفاده از نمونه‌هاي موجود منتسب کنند. روش‌هاي خوشه‌بندي به واسطه قابلیت درکی که در خود نهفته دارند، از اقبال خوبی برخوردار شده‌اند. وجود قابلیت درك از جهات گوناگونی حائز اهمیت می باشد. فهم قلمرو، درك قابلیت‌هاي کلاس‌بندي، توجیه تصمیم و بالاخره وجود قوانین نمادینی که می‌توانند از روي خوشه‌هاي استخراج شده و سپس در یک سیستم تصمیم‌گیري مبنی بر قوانین به کار گرفته شوند.
خوشه‌بندي در واقع یک عملیات غیر‌نظارتی می باشد. این عملیات هنگامی استفاده می‌شود که ما به دنبال یافتن گروه‌هایی از داده‌هاي مشابه می‌باشیم بدون این‌که از قبل پیش‌بینی در مورد شباهت‌هاي موجود داشته باشیم. خوشه‌بندي معمولاً هنگامی استفاده می‌شود که به دنبال یافتن گروه‌هایی از مشتریان هستیم که قبلا شناخته نشده‌اند. براي مثال می‌توان شباهت‌هاي مشتریان در استفاده از تلفن‌همراه را به منظور گروه‌بندي مشتریان و تشخیص خدمت جدیدي جستجو نمود.
خوشه‌بندي براي اکثر روش‌هاي داده‌کاوي مثل درخت‌تصمیم‌گیري و شبکه‌هاي‌عصبی، با یک مجموعه آموزشی شروع کرده و به کمک این مجموعه سعی می‌شود یک مدل براي بخش‌بندي داده‌ها، ایجاد گردد. سپس از آن مدل براي پیش‌بینی داده‌هاي جدید استفاده شود.
ورود به نرم افزار آنلاین k-means
خوشه‌بندی k- میانگین (K-means)
الگوریتم k-میانگین یکی از پرکاربردترین الگوریتم‌های خوشه‌بندی می‌باشد. حرف k که در این الگوریتم وجود دارد به این واقعیت برمی‌گردد که این الگوریتم به دنبال تعداد ثابتی از خوشه‌هاست که بر اساس نزدیکی نقاط داده‌ای به هم تعریف شده‌اند. این الگوریتم ابتدا در سال 1987توسط جی.بی مک کوئین[2] به وجود آمد. برای درک ساده‌تر این الگوریتم یک مثال ساده دو بعدی زده می‌شود( x1 و x2) ولی روند کار برای بیش از دو متغیر) (x1,x2,…. , نیز همین‌گونه است.
مراحل k- میانگین (K-means)
- مرحله یک
در اولین مرحله ، الگوریتم به طور تصادفی k نقطه داده‌ای را انتخاب می‌کند تا مثل هسته[3] روی آ‌ن‌ها کار شود. در این مرحله هرکدام از هسته‌ها یک خوشه نارس هستند.
- مرحله دوم
در این مرحله هر داده را به نزدیک ترین هسته اختصاص می‌دهد. یک راه برای این‌کار یافتن مرز بین خوشه‌هاست. همانطور که در شکل 1 می‌بینید، مرز بین دو خوشه به نقاطی گفته می‌شود که با هر خوشه فاصله یکسانی داشته باشند. (یادآوری: دو نقطه A و B را در نظر بگیرید، همه نقاطی که دارای فاصله مساوی با دو نقطه A و B باشند، بر روی یک خط قرار می‌گیرند که این عمود منصفِ خط واصل A و B می‌باشد.) در شکل1 هسته‌های اولیه با خطوط منقطع به هم مرتبط شده‌اند؛ مرز خوشه‌های حاصل هم با خط‌های پررنگ‌تر نشان داده شده است که با خطوط منقطع، زاویه قائمه دارند. اگر از این خطوط به عنوان راهنما استفاده شود مشخص است که کدام اطلاعات به کدام هسته‌ها نزدیک‌تر هستند. در سه بعد این مرزها صفحات صاف خواهند بود و در n بُعد، صفحات مرزی n-1 بُعدی هستند. خوشبختانه، الگوریتم‌های کامپیوتری به راحتی می‌توانند مسائل چند بُعدی را حل کنند. در شکل 3-9 به داده‌ای که دور آن مربع کشیده شده است توجه کنید؛ بر اساس هسته‌های اولیه، این داده به خوشه‌ای که توسط هسته شماره2 کنترل می‌شود اختصاص یافته است، چرا که به آن هسته بیش از دو هسته دیگر نزدیک‌تر است. از لحاظ فرمولی فاصله هر داده تا مرکز خوشه از فرمول زیر به‌دست می‌آید. 
در این فرمول k تعداد هر خوشه،n تعداد داده‌ها، cjمرکز هر خوشه و xi داده‌های هر خوشه (به غیر از مرکز) می‌باشد.
شکل 1: هسته‌های اولیه مرزهای خوشه‌های اولیه را تعیین می‌کند
- مرحله سه
در این مرحله مرکز ثقل هر خوشه محاسبه می‌شود. این مراکز ثقل بهتر از هسته‌های اولیه برای مشخص کردن خوشه‌ها، عمل می‌کنند. یافتن مرکز ثقل تنها با به‌دست آوردن میانگین اندازه هر بُعد برای همه اطلاعات در خوشه انجام می‌شود. در شکل 2، مرکز های جدید با لوزی نشان داده شده است. پیکان هم نشان‌دهنده حرکت هسته‌های اصلی به مرکز جدید خوشه‌هاست.
شکل2- مراکز ثقل نقاطی که به هر خوشه اختصاص یافته‌اند محاسبه می‌شود.
حال این مراکز برای تکرار بعدی الگوریتم، نقش هسته را بازی می‌کنند. مرحله دوم تکرار می‌شود و هر نقطه بار دیگر به یک خوشه با نزدیک‌ترین مرکز، اختصاص می‌یابد. این حلقه همین‌طور ادامه پیدا می‌کند تا دیگر هیچ تغییری در خوشه‌ها ایجاد نشود. شکل 3، مرزهای خوشه‌های جدید را نشان می‌دهد که مانند قبل، با کشیدن عمود منصف‌ها بین هر مرکز، شکل گرفته‌اند.
شکل3- در طی هر تکرار، همه تخصیص‌های خوشه‌ها دوباره ارزیابی می‌شوند
ورود به نرم افزار آنلاین k-means
[1] K-means
[2] J.B.MacQueen
[3] Seed