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

مقدمه

مجموعه اشیایی که ویژگی های یکسان دارند در گروه هایی دسته بندی میشوند و خوشه های این اشیا به اسم خوشه بندی داده ها شناخته شده اند. این تکنیک یادگیری بدون نظارت برای دسته بندی داده هاست. الگوریتم k-meansبه طور گسترده ای مورد استفاده قرار میگیرد و الگوریتم مشهوری برای آنالیز خوشه ها به حساب می آید. در این الگوریتم ، تعداد n نقطه داده بر اساس برخی معیارهای اندازه گیری شده مشابه ، به k خوشه دسته بندی می شوند. الگوریتم k-mean سرعت خیلی بالایی دارد و بنابراین به طور معمول به عنوان الگوریتم خوشه بندی استفاده می شود.  

 

 کوانتیزاسیون-چندی سازی برداری، تحلیل خوشه ای،یادگیری ویژگی برخی از کاربردهای k-means  است. اما نتایج بدست آمده اصلی از این الگوریتم وابسته به انتخاب مرکز خوشه دارد. خلاصه اصلی این الگوریتم این است که تعداد مناسب خوشه ها را ارائه دهیم. فراهم کردن تعداد خوشه ها قبل از اعمال الگوریتم غیر عملی است و نیاز به دانش عمیق در زمینه خوشه بندی دارد. در این پروژه ما قصد داریم که الگوریتمی بیابیم که انتخاب مراکز خوشه های الگوریتم k-meansرا بهبود بخشیم . ما قصد داریم بر روی مجموعه داده های عددی همراه با مجموعه داده های دسته بندی با ابعاد n کار کنیم. ما قصد داریم فاصله منهتن، فاصله تاس و فاصله کوزین ( کوسینیوسی شاید) را برای اندازه گیری شباهت ها در نظر بگیریم. نتایج بدست آمده از این الگوریتم پیشنهادی با الگوریتم اصلی k-means مقایسه خواهد شد. همچنین کیفیت و پیچیدگی الگوریتم پیشنهادی با الگوریتم موجود بررسی می شود.

کلمات کلیدی :خوشه بندی داده ها - k-means– یادگیری بدون نظارت – مرکزی.

1.  

مقدمه

آنالیز داده ها زمینه بسیاری از برنامه های محاسباتی ( کامپیوتری)، یا به عنوان بخشی از عملیات آنلاین آنها یا در یک مرحله طراحی، هستند. پروسه های آنالیز داده ها می توانند یا به صورت تاییدی و یا اکتشافی بر اساس در دسترس بودن مدل های مناسب برای منبع داده تقسیم بندی شوند، اما یک عنصر اصلی در هر دو نوع پروسه (چه برای تشکیل فرضیه و چه تصمیم گیری ) در حال دسته بندی است که یا طبقه بندی برحسب میزان متناسب بودن با یک مدل پیش فرض (i) و یا  گروه بندی های طبیعی ( خوشه بندی) از طریق تجزیه و تحلیل (ii) را نشان می دهد.

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

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

یک مورد اندازه گیری بسیار ساده ، فاصلۀ درون خوشه ای است که در الگوریتم k-means برای بدست آوردن خوشه بندی بهتر ، کمترین فاصله را باید در نظر گرفت. اصطلاح خوشه بندی در چندین گروه تحقیقاتی برای توصیف روش های گروه بندی داده های بدون برچسب یا داده های بدون لیبل (داده های بدون تگ و بدون لیبل) به کار می رود.

این گروه های تحقیقاتی دارای اصطلاحات و مفاهیم مختلف برای اجزای فرایند خوشه بندی و زمینه ای که در آن خوشه بندی انجام می شود، هستند. تولید یک بررسی کاملا جامع  با توجه به حجمی از موارد مربوط به خوشه بندی، یک وظیفه مهم خواهد بود. دسترسی به این بررسی ممکن است سوال برانگیز باشد که نیاز به هماهنگی واژگانو مفروضات متفاوت خوشه بندی در موارد مختلف باشد. ( به طور کلی منظور این است که برای این نظرسنجی ها مفروضات متفاوت و سوال برانگیزی برای خوشه بندی ها وجود دارد که نیازمند هماهنگی هستند).

فعالیت الگوی خوشه بندی به شکل زیر است :

نمایندگی نقاط داده ها (تعیین نقاطی به عنوان نماینده)

اندازه گیری شباهت نقاط داده ها

خوشه بندی یا گروه بندی

انتزاع داده (در صورت نیاز)

ارزیابی خروجی

مراحل :

انتخاب  یک شماره (K)بعنوان مرکز خوشه

تمامی نقاط داده ها (به عنوان مثال ژن) را به نزدیک ترین مرکز خوشۀ خودش اختصاص بده

هر مرکز خوشه را به میانگین نقاط دادۀ اختصاص داده شده ببر ( مثل ژن ها)

مراحل 2 تا 3 را تا زمانی که همگرایی ایجاد شود انجام بده

محاسبۀ فاصله نقاط داده ها از مراکز (centroids) با استفاده از :

II) k-means سنتی

در این الگوریتم، تعداد n، نقطۀ داده بر اساس معیارهای شباهت اندازه گیری شده به k خوشه تقسیم بندی می شوند. الگوریتم k-mean سرعت بالایی دارد و بنابراین معمولاً به عنوان الگوریتم خوشه بندی استفاده می شود. چندی سازی برداری، آنالیز خوشه یادگیری ویژگی برخی از کاربردهای k-means هستند. 

مراحل :

انتخاب  یک شماره (K)بعنوان مرکز خوشه

تمامی نقاط داده ها (به عنوان مثال ژن) را به نزدیک ترین مرکز خوشۀ خودش اختصاص بده

هر مرکز خوشه را به میانگین نقاط دادۀ اختصاص داده شده ببر ( مثل ژن ها)

مراحل 2 تا 3 را تا زمانی که همگرایی ایجاد شود انجام بده

محاسبۀ فاصله نقاط داده ها از مراکز (centroids) با استفاده از :

در اینجا Xp نشاندهندۀ p امین بردار داده ، j  بردار مرکزی (centroids) خوشۀ j و d تعداد ویژگی های هر بردار centroidرا نشان می دهد.

محاسبۀ دوبارۀ centroid جدید از خوشه های تولید شده با استفاده از : 

A   _ یچیدگی زمانی

مسئله یافتن هدف بهینه ، NP-Hard است.

پیچیدگی زمانی O(n*k*i) است.

که n = جمع عناصر

K = تعداد تکرار خوشه

i = تکرارها

A  - مدل ریاضی

S را به عنوان سیستم در نظر بگیرید،

S = I, Fn, C, S, F

که ،

I = مجموعۀ ورودی M  و Fe

M = ماتریس رشته های یک سند (term-document matrix)n*m

n= تعداد نقاط داده ها

m= تعداد ویژگی ها

Fe = مجموعه اولیۀ مراکز c1، C2، Ck

K = تعداد مراکز

Fn = f(D1), f(D2), f(D3)

D1= چک کردن اینکه آیا نقطه داده در خوشه C1 هست یا نه

D2 = چک کردن اینکه آیا نقطه داده در خوشه C2 هست یا نه

D3 = چک کردن اینکه آیا نقطه داده در خوشه C3 هست یا نه

که C1, C2  و C3 تعداد خوشه ها هستند.

D1, D2 و D3 ، فواصل محاسبه شده از هر نقطه داده از مرکز اولیه.

محدودیت های c = داده ها باید عددی باشند.

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

شکست F = نرخ خطا مثلا مجموعه داده های اصلی و خوشه ها بعد از خوشه بندی تفاوت زیادی را در فاصلۀ خوشۀ درونی (intracluster)  را نشان می دهد که خیلی زیاد است . 

A.     دیاگرام گردشی

الگوریتم

1) دو مرکز را از مجموعه داده ها انتخاب کنید، مثلاً پایین ترین نقطه مرکزی و بالاترین نقطه مرکزی.

2) بعد از انتخاب مراکز ، دو خوشه با اعضایی که با یکدیگر متفاوتند ایجاد می کنیم .

ورودی :

 T  : مجموعه نقاط داده با ویژگی های T1، T2، Tn که n = تعداد ویژگی ها است.

تمام ویژگی ها عددی هستند.

خروجی:

 تعداد مناسب خوشه هایی با n  داده که به درستی توزیع شده اند.

مراحل :

a)     مجموع مقادیر ویژگی های هر نقاط داده را محاسبه کنید. (پیدا کردن نقاط در مجموعه داده ها که در دورترین قسمت هستند)

b)     نقاط داده ها را با جمع کمترین و بالاترین مقادیر به عنوان مراکز اولیه بدست آورید.

c)      ایجاد پارتیشن های اولیه ( خوشه ها) با استفاده از اندازه گیری کوزین ( کسینوس)، Sorensen-Dice و فاصله منهتن بین هر نقطه داده و مراکز اولیه.

d)     محاسبه فاصله هر نقطه داده را از مرکز در هر دو پارتیشن اولیه .L= کمترین فاصله از مجموعه فاصله های بدست آمده.

e)     مراکز جدید برای پارتیشن های ایجاد شده در مرحله c را بیابید.

f)       فاصله هر نقطه داده از مرکز خوشه جدید را مقایسه کنید و خروجی های خارج از محدوده (outliers) را بسته به توابع هدف ذیل بیابید :

g)     اگر فاصله هر نقطه داده از میانگین خوشه 1 باشد ، بنابراین یک outlier نیست.

h)     مراکز جدید را با خوشه ها مقایسه کنید

i)        فاصله هر outlier را از مراکز جدید خوشه ها محاسبه کنید و outlier هایی را که در مرحله f رضایت بخش نبودند را بیابید.

j)       O=OL1,OL2,.,OLp را به عنوان مجموعه outlier های بدست آمده در مرحله h (مقدار k وابسته به تعداد outlier ها است ) در نظر بگیرید.

k)     تا زمانیکه (A==NULL) تکرار کنید.

·        یک خوشه جدید را با در نظر گرفتن میانگین مقدار اعضای آن به عنوان مرکز، برای مجموعه B ایجاد کنید

·        Outlier های این خوشه را بسته به تابع هدف در مرحلۀ 6 بدست آورید.

·        اگر تعداد outlier ها = n باشد ، سپس یک خوشه جدید با یکی از outlierها به عنوان اعضای آن ایجاد کنید و هر outlier دیگر را برای تابع هدف در مرحله f تست کنید .

·        Outlier ها را اگر وجود دارند بیابید.

·        فاصله هر outlier را از مرکز خوشه مورد نظر محاسبه کنید و  outlier هایی را تنظیم کنید که در تابع هدف در مرحله f رضایت بخش باشند.

·        A=O1,O2.Oq ، مجموعه جدید outlier ها است . (مقدار q بستگی به تعداد  outlier ها دارد).

l)        اگر مرکز خوشه جدید تولید شده خیلی نزدیک تر باشد ، مقدار l را به طور دستی  تنظیم کنید تا زمانی که خوشه های جدا شدۀ بیشتری بدست آورید.

IV. نتیجه

برای استفاده از الگوریتم k means سنتی ، ما نیاز به فراهم کردن تعداد خوشه های اولیه داریم. این نیازمند دانش عمیق در زمینه مجموعه داده هاست. و اگر ورودی به صورت نادرست داده شود بر نتیجه تاثیر خواهد داشت و ممکن است نتیجۀ دقیقی ندهد. بنابراین یک سیستم با استفاده از الگوریتم k-means بهبود یافته برای حذف اشکالات k- means موجود پیشنهاد می شود، مثلاً ارائه تعدادی از خوشه ها قبل از کاربرد. ما نتایج الگوریتم k- means موجود را با الگوریتم k- means پیشنهادی را همراه با کیفیت خوشه ها و پیچیدگی الگوریتم مقایسه خواهیم کرد.

منبع:

https://ieeexplore.ieee.org/document/7155869/authors