خوشه بندی و روش های رایج پیاده سازی آن( قسمت اول)

خوشه‌بندی یا آنالیز خوشه (به انگلیسی: Clustering) در آمار و یادگیری ماشینی، یکی از شاخه های یادگیری بی‌نظارت می‌باشد و فرآیندی است که در طی آن، نمونه‌ها به دسته‌هایی که اعضای آن مشابه یکدیگر می‌باشند تقسیم می‌شوند که به این دسته ها خوشه گفته میشود. بنابراین خوشه مجموعه ای از اشیاء می‌باشد که در آن اشیاء با یکدیگر مشابه بوده و با اشیاء موجود در خوشه‌های دیگر غیر مشابه می‌باشند.۱٫ روش خوشه یابی K-Means
K-Means یکی از محبوب ترین روش های خوشه بندی است. الگوریتم ۱ رویه خوشه بندی K-Means را نشان می دهد. خوشه های اولیه که احتمالا بهینه نیز نیستند داده شده اند. هر نقطه را به نزدیک ترین مرکز تخصیص می دهیم و مراکز خوشه را با محاسبه میانگین نقاط عضو مجددا محاسبه می کنیم. مراحل تخصیص نقاط به خوشه ها و به هنگام سازی مراکز را تا رسیدن به ملاک همگرایی (مانند تعداد تکرار از پیش تعریف شده و یا تفاوت مقدار تابع تحریف) ادامه می دهیم.
وظیفه مقدار دهی اولیه، تشکیل K خوشه‏ی اولیه است. تکنیک های بسیاری برای مقداردهی ارائه شده است. از تکنیک های ساده ای مثل انتخاب K نقطه‏ی اول، مقداردهی اولیه Frogy (انتخاب تصادفی K نقطه در مجموعه داده) و تقسیم بندی تصادفی (تقسیم بندی نقاط به صورت تصادفی به K زیر مجموعه) گرفته تا شیوه های پیچیده تر مانند مقدار دهی مبتنی بر تراکم، مقدار دهی اولیه هوشمند، مقدار دهی اولیه دورترین اولین (Furthest First) ( FF(به طور مختصر) ، اولین نقطه را به صورت تصادفی انتخاب می کند، سپس مرکز بعدی را نقطه ای انتخاب می کند که از مرکز فعلی بیشترین فاصله را داشته باشد) و مقدار دهی اولیه دورترین اولین زیر مجموعه (SFF). برای جزئیات بیشتر به مقاله Steinly و Brusco (2007) مراجعه شود. این مقاله مرور و مقایسه ای بین ۱۲ روش مقدار دهی اولیه ارائه داده است.
شکل ۱٫یک مثال از خوشه بندی K-Means روی یک مجموعه از نقاط با K=2 را نشان داده است. این خوشه ها با انتخاب دو نقطه به عنوان مرکز مقدار دهی اولیه شده اند.
تحلیل پیچیدگی: N را تعداد نقاط، D را تعداد ابعاد و K را تعداد مراکز خوشه ها در نظر بگیرید. فر ض کنید الگوریتم I بار تکرار می شود تا همگرا شود. پیچیدگی مکانی خوشه بندی K-Means برابر است با O(N(D+K)). پیچیدگی زمانی K-Means، بر اساس تعداد محاسبات فاصله برابر است با O(NKI).

خوشه بندی K-Means. شکل ۱٫ مثالی از خوشه بندی K-Means با K=2. مرکز هر خوشه با علامت “”X مشخص شده است.

الگوریتم ۱٫ الگوریتم خوشه بندی K-Means

۲٫ الگوریتم خوشه‌بندی LBG
الگوریتم خوشه‌بندی K-Means به انتخاب اولیه ی خوشه‌ها بستگی دارد و این باعث می‌شود که نتایج خوشه‌بندی در تکرارهای مختلف از الگوریتم متفاوت شود که این در بسیاری از کاربردها قابل نیست. برای رفع این مشکل الگوریتم خوشه‌بندی LBG پیشنهاد شد که قادر است به مقدار قابل قبولی بر این مشکل غلبه کند. در این روش ابتدا الگوریتم تمام داده‌ها را به صورت یک خوشه‌ در نظر می‌گیرد و سپس برای این خوشه یک بردار مرکز محاسبه می‌کند.(اجرای الگوریتم K-Meansبا تعداد خوشه ۱K=). سپس این بردار را به ۲ بردار می ‌شکند و داده‌ها را با توجه به این دو بردار خوشه‌بندی می‌کند (اجرای الگوریتم K-Means با تعداد خوشه K=2 که مراکز اولیه خوشه‌ها همان دو بردار هستند). در مرحله بعد این دو نقطه به چهار نقطه شکسته می‌شوند و الگوریتم ادامه پیدا می‌کند تا تعداد خوشه مورد نظر تولید شوند.

الگوریتم زیر را می‌توان برای این روش خوشه‌بندی در نظر گرفت:
۱٫ شروع: مقدار M(تعداد خوشه‌ها) با عدد ۱ مقدار دهی اولیه می‌شود. سپس برای تمام داده‌ها بردار مرکز محاسبه می‌شود.
۲٫ شکست: هر یک از M بردار مرکز به ۲ بردار جدید شکسته می‌شوند تا۲M بردار مرکز تولید شود. هر بردار جدید بایستی درون همان خوشه قرار داشته باشد و به اندازه کافی از هم دور باشند.
۳٫ K-Means: با اجرای الگوریتم K-Means با تعداد خوشه ۲M و مراکز اولیه خوشه‌های محاسبه شده در مرحله ii خوشه‌های جدیدی با مراکز جدید تولید می‌شود.
۴٫ شرط خاتمه: در صورتی که M برابر تعداد خوشه مورد نظر الگوریتمLBG بود الگوریتم خاتمه می‌یابد و در غیر این صورت به مرحله ii رفته و الگوریتم تکرار می‌شود.