دانلود مقاله مروری بر روشهای انتخاب نقاط اولیه در الگوریتم k - means

بخشی از مقاله

چکیده

یکی از تکنیکهای کشف دانش برای آشکار ساختن ساختارها در دادهها، خوشهبندی است که به طـور گسـتردهای مـورد اسـتفاده قرار میگیرد. در الگوریتمهای خوشهبندی، انتخاب یک روش مناسب برای انتخاب مراکز خوشههای اولیه بسیار مهم است و تاثیر مستقیم در شکل گیری خوشههای نهایی دارد. از آنجا که خوشهها در گروههایی با فضای ویژگی از هم جدا هستند، مطلوب است

مراکز اولیه به گونهای انتخاب شوند که کاملا از هم یکدیگر مستقل باشند. در این مقاله، به بررسی روشهایی کـه بـرای محاسـبه
مراکز خوشه اولیه در الگوریتم k-means پیشنهاد شدهاست، میپردازیم.

کلید واژه: نقاط آغازین در k-means، نقاط خوشهبندی، الگوریتم .k-means

-1 مقدمه

خوشهبندی ابزاری مهم برای انواع برنامههای کاربردی از جمله داده کاوی، تجزیه و تحلیل آماری دادهها، فشـرده سـازی

دادهها، و...است. هدف از خوشهبندی گروهبندی دادهها به نحوی است که شباهت میـان اعضـای دادههـا در داخـل همـان خوشـه

حداکثر باشد در حالی که شباهت میان اعضای داده ،که از خوشههای متفاوت هستند بسیار کم اسـت. الگـوریتم )k-meansمـک کویین، (1681 شناخته شدهترین و سریعترین روش در الگوریتمهای خوشهای غیر سلسله مراتبی است. به دلیل سادگی الگوریتم k-means، این الگوریتم در زمینههای مختلف مورد استفاده قرار میگیرد. الگوریتم k-means روش خوشهبنـدی بـرای جـدا-سازی دادهها به K گروه کاملا مجزا است(.(1
پیاده سازی الگوریتم :(2) k-means

.1 ایجاد مراکز اولیه خوشهها از بین کلیه نقاط داده.

.2 محاسبه فاصله هر یک از نقاط دادهای تاهر یک از مراکز خوشه که در مرحله 1 تعیین شدهاند. .3 تخصیص همهی نقاط به یک مرکز خوشه.

.4 بهینهسازی مراکز اولیه در هر خوشه.
.5 بازگشت به مرحله .2

با این حال، الگوریتم k-means به نقاط ابتدایی، به عنوان مراکز خوشه بسیار حساس است . k-means خوشهبندی منحصـر بـه فرد را تضمین نمیکند چرا که ما به نتایج متفاوتی با انتخاب مراکز خوشههای اولیه که به صورت تصادفی انتخاب میشوند ، مـی-

رسیم. روش بازگشتی برای مقدار دهی اولیه توسط دودا و هارت ، در سال 1613 مورد بحث قرار گرفته است. به این صورت که

اجرای مسئلهی خوشهبندی را K بار تکرار میکند(.(2 یک نوع از این روش به این صورت است: کل دادهها را بـه صـورت یـک مجموعه در نظر میگیرد و پس از آن به طور تصادفی K بار روی آنها عمل خوشهبندی را انجام مـیدهـد. مرکـز خوشـه اولیـه، جین ودابِس که در سال 1699 ارائه شد، به اینصورت عمل می کند :(3) الگـوریتم k-means را چنـدین بـار بـا مقـادیر اولیـه
تصادفی برای یافتن مراکز اولیه اجرا میکند، سپس میانگین مقادیر اولیه انتخاب شده از این مراکز بـه عنـوان مراکـز خوشـه نهـایی

انتخاب میشوند. ایکاس و همکارانش در سال 2113 ، پیشنهاد الگوریتم global k-means، کـه یـک روش تـدریجی بـرای

خوشهبندی است را دادند؛ در این الگوریتم، در هر مرحله به صورت پویا یک مرکـز خوشـه در یـک زمـان از طریـق یـک روش قطعی جستجوی جهانی که شامل N) N اندازه مجموعه داده) تکرار الگوریتم k-means میباشـد، مـیافزایـد و نقـاط مناسـب

اولیه را به دست میآورد(.(4 خان و احمد در 2114 پیشنهاد الگوریتم مرکز خوشه اولیه CCIA را برای حل مسئله مقداردهی

اولیه در خوشهبندی دادند. CCIA براین اساس است که برخی از الگوها بسیار شبیه به یکدیگر هسـتند. ایـن روش بـا محاسـبه
میانگین و انحراف معیار برای هر ویژگی داده شروع میشود و سپس دادهها را با منحنی نرمال در پارتیشن خـاص جـدا مـیکنـد.
CCIA با استفاده از k-means و تراکم دادههای چند مقیاسی به مشاهده شباهت الگوهای دادهای، قبل از پیدا کردن خوشـه هـای
اولیه نهایی میپردازد. نتایج آزمایش CCIA اثربخشی این روش را برای حل مشکلات خوشهبندی نشان میدهـد(Deelers .(5 و Auwatanamongkol در سال 2111 پیشنهاد یک الگوریتم برای محاسبه مراکز خوشه اولیه برایk-means را دادنـد. آنهـا

دادهها را در یک سلول با استفاده از یک نقشه برش تقسیم کردند، که خود سلول شامل دو سلول کوچکتر است. نقشه عمود بر

محور دادهها با بالاترین واریانس و طوری طراحی شده که مجموع مربعات دو سلول تا آنجا که ممکن است کاهش یابد، در حالی
که در آن واحد این دو سلول تا جائیکه ممکن است، دور از هم نگه داشته اند. تقسیم یک سلول تا زمانیکه تعـداد سـلولهـا بـه

تعداد از پیش تعریف شدهای از خوشهها، برابرk است، برسد ادامه مییابد .(8)

-2 روش بهبود نقاط اولیه

ابتدا با استفاده از یکی از روشهای قبلا مطالعه شده ، تعداد خوشهها k را تعیین میکنیم. (1) استفاده از الگوریتم کلونی مورچه را برای تعیین تعداد خوشه و مراکز آنها به صورت پویا توصیه میکند. (9) از طریق کـاهش تـراکم و بـا اسـتفاده از مرکـز

توزیع از جستجوی اولیه و روشهای دیگر برای بهبود نقاط اولیه در الگوریتم k-means استفاده میکند. در اینجا تعداد خوشهها
را با این فرمول محاسبه میکنیم: .(N تعداد نقاط داده است.) سپس نقاط داده را نرمالایز میکنیم. هر نقطه دارای یکسـری

ویژگیهای خاص است. نقاط با توجه به ویژگیها در گروههای خاصی قرار میگیرند. حداکثر N گروه میتوان به طور کلی بـرای اولین بار تولید کرد. برای هر کدام از این گروهها یک مرکز جرم تعیین میکنیم، اینها مراکز اولیه خوشهها هستند.

ادغام: در تجزیه بالا ، ممکن است جداسازی گروهها تا جائیکه هر گروه شامل یک عضو باشد ادامه یابد برای قرار دادن بعضی از نقاط داده در یک گروه، باید عملیات ادغام انجام گیرد. به این صورت که بسته به ویژگیهای هر گروه، بـرای قـرار گیـری نقـاطی خاص با یکسری ویژگیهای مشابه بعضی از ویژگیها با یکدیگر ادغام میشوند. با این روش میتوان به یـک خوشـهبنـدی نهـایی مطلوب همگرا شد. در (6) این روش پیشنهاد شدهاست: اگر اولین کلاس گروهبندی، از N داده (که هر داده به عنوان یـک نمونـه در نظر گرفته میشود)، تشکیل شدهباشد و فاصله بین اولین مرکز جرم کلاس iام و سایر مراکـز جـرم کـلاس iام بیشـتر از مراکـز جرم تمام نمونهها در دستهای دیگر که کمترین فاصله اقلیدسی را با هم دارند باشـد آنگـاه آن دسـته و دسـته iام را مـیتـوان بـا

یکدیگر ادغام کرد.

-1 .2 مقداردهی اولیه الگوریتم K-Means با استفاده از اطلاعات آماری

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

قضیه :1 تئوری حد مرکزی مجموعه شامل n نمونه که مستقل و یکسان توزیع شدهاند، است و هر
نمونه توزیع خاص خود را دارد، قضیه حد مرکزی ادعا میکند که برای n های بزرگ، توزیع با میـانگین µ و واریـانس
تقریبا نرمال است.

هدف از بیان این قضیه اینست که را یک توزیع تقریبا نرمال از توزیعهای منفرد ها در نظر بگیریم. ما میتوانیم از این نماد، با در نظر گرفتن مجموعه دادههایی که شامل چندین خوشه و هر خوشه دارای توزیع خاص خود است، استفاده کنیم. با استفاده از

تئوری حد مرکزی میتوان ادعا کرد که مجموع هر یک از خوشهها یک توزیع نرمال دارد. حال بهترین مقداردهی اولیـه از نمونـه-

های اولیه "در اطراف" میانگین این توزیع است. بنابراین ما نیاز به برآورد میانگین مجموعه دادهها داریم. یکی از شناخته شدهترین

تخمینهای برآورد، احتمال حداکثر((12 است، که بیان میکند ما باید به دنبال ارزش بردار پارامتر θ که هـدف آن حـداکثر کـردن
تابع احتمال است، هستیم. پارامترهای یک توزیع گاوسی میانگین μ و واریانس است. به عبارت دیگر .