آموزش کلاسترینگ Fuzzy C-means با استفاده از تابع fcm در نرم‌افزار متلب (MATLAB)

آموزش کلاسترینگ Fuzzy C-means با استفاده از تابع fcm در نرم‌افزار متلب (MATLAB)

نویسنده: لرنیکس
آخرین بروزرسانی: ۱۳۹۹/۰۶/۲۷
بازدیدها: ۲,۷۵۰

خوشه‌یابی یا کلاسترینگ (Clustering) یکی از روش‌های یادگیری بدون نظارت (Unsupervised Learning) است که با توجه به نظم موجود در دادگان، هر داده به یک خوشه یا کلاستر تخصیص داده می‌شود. یکی از چالش‌های اصلی روش‌های کلاسترینگ، یافتن تعداد مناسب کلاستر است. در بسیاری از الگوریتم‌ها، خوشه‌یابی با تعداد مختلف کلاستر انجام می‌شود و سپس با استفاده از معیارهای مختلف، تعداد مناسب کلاستر تعیین می‌گردد. روش‌های خوشه‌یابی را می‌توان به دو دسته کلی کریسپ (Crisp) و فازی (Fuzzy) طبقه‌بندی کرد. در ادامه پس از بررسی خوشه‌یابی کریسپ و فازی، روش خوشه‌یابی فازی C-means مورد بررسی قرار می‌گیرد.

 

خوشه‌یابی کریسپ (Crisp Clustering)

در بسیاری از روش‌ها و الگوریتم‌های کلاسترینگ، مانند الگوریتم k-means یا الگوریتم‌های ترتیبی و سلسله مراتبی، هر داده به صورت قطعی به یک کلاستر تخصیص داده می‌شود. در واقع تابع عضویت تنها دو مقدار 0 و 1 دارد. اگر مقدار تابع عضویت 0 باشد یعنی داده در آن کلاستر قرار ندارد و اگر 1 باشد یعنی داده در آن کلاستر قرار می‌گیرد. شکل 1 ده داده دو بُعدی را در صفحه نمایش می‌دهد که به صورت کریسپ به دو کلاستر تقسیم شده‌است. همانطور که در شکل 1 نمایش داده شده‌است، هر داده به صورت قطعی به یک کلاستر تخصیص داده شده است. ماتریس U مقادیر تابع عضویت هر داده را نمایش می‌دهد که 0 یا 1 است. سطر بالا در ماتریس U مقدار تابع عضویت دادگان در کلاستر نارنجی و سطر پایین این مقدار در کلاستر سبز است.

خوشه‌یابی کریسپ (Crisp)

شکل 1 - خوشه‌یابی کریسپ (Crisp) و مقادیر تابع عضویت دادگان

 

خوشه‌یابی فازی (Fuzzy Clustering)

در خوشه‌یابی فازی برخلاف حالت کریسپ، مقادیر تابع عضویت هر داده مقداری بین 0 تا 1 است. در واقع هر داده به یک مقدار در هر کلاستر عضویت دارد و به صورت صد درصدی نمی‌توان دادگان را به کلاسترها تخصیص داد. شکل 2 همان دادگان شکل 1 را در حالت خوشه‌یابی فازی نمایش می‌دهد. همانطور که مشاهده می‌شود مقادیر تابع عضویت بین 0 تا 1 قرار دارند.

خوشه‌یابی فازی (Fuzzy)

شکل 2 - خوشه‌یابی فازی (Fuzzy) و مقادیر تابع عضویت دادگان

 

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

روش‌ها و الگوریتم‌های متنوعی برای خوشه‌یابی فازی گسترش یافته‌است. از مهمترین الگوریتم‌ها می‌توان به الگوریتم فازی سی-مینز (Fuzzy C-means) اشاره کرد. با توجه به اینکه در الگوریتم C-means از فاصله اقلیدسی استفاده می‌شود، کلاسترها به صورت اَبَرکره (Hypersphere) و با سایز نسبتا برابر ایجاد می‌شوند. بنابراین این الگوریتم برای دادگانی مناسب است که متمرکز (Mass) بوده و به صورت اَبَرکره و با سایز نسبتا برابر قابل خوشه‌بندی باشند. برای رفع محدودیت شکل کلاسترها از روش Gustafson Kessel و برای رفع محدودیت سایز کلاسترها از روش Gath-Geva استفاده می‌شود.

از جمله کاربردهای کلاسترینگ فازی، می‌توان به تقسیم‌بندی تصویر به نواحی مختلف (Image Segmentation) اشاره کرد. در شکل 3، تصویر سمت چپ با استفاده از الگوریتم Fast Fuzzy C-means به سه ناحیه تقسیم شده‌است.

تقسیم تصویر به نواحی مختلف

شکل 3 - تقسیم تصویر به نواحی مختلف با استفاده از الگوریتم Fast Fuzzy C-means

 

در نرم‌افزار متلب (MATLAB) برای پیاده‌سازی الگوریتم Fuzzy C-means می‌توان از تابع fcm استفاده کرد. در ادامه مثالی برای خوشه‌یابی فازی با استفاده از تابع fcm برسی می‌شود.

 

تولید مجموعه دادگان دلخواه برای کلاسترینگ

ابتدا با استفاده از نرم‌افزار متلب، مجموعه دادگان دو بُعدی به گونه‌ای تولید می‌شود که بتوان آن‌ها را با دو کلاستر تفکیک کرد. دادگان به صورت دو دایره که کمی همپوشانی دارند با استفاده از کد زیر تولید می‌شوند.

%Create Data

clear; clc;

N1=500; %Number of Data for Cluster 1

N2=500; %Number of Data for Cluster 2

nu=4;

Data1=zeros(N1,2); %Data1=[Radius (r), Angle (theta)]

Data2=zeros(N2,2); %Data2=[Radius (r), Angle (theta)]

%Create Data in Polar Coordinates

for i=1:1:N1 %Create Data for Cluster 1

    r=nu*rand(1,1);

    Data1(i,:)=[r,2*pi*rand(1,1)];

end

for i=1:1:N2 %Create Data for Cluster 2

    r=nu*rand(1,1);

    Data2(i,:)=[r,2*pi*rand(1,1)];

end

%Data in Cartesian Coordinates

Data1c=zeros(N1,2); %Data1c=[x,y]

Data2c=zeros(N2,2); %Data2c=[x,y]

%x=r*cos(theta), y=r*sin(theta)

for i=1:1:N1 %Data in Cluster 1

    Data1c(i,:)=[Data1(i,1)*cos(Data1(i,2)),Data1(i,1)*sin(Data1(i,2))];

end

for i=1:1:N2 %Data in Cluster 2

    Data2c(i,:)=[Data2(i,1)*cos(Data2(i,2)),Data2(i,1)*sin(Data2(i,2))];

end

%Shift Data in Cluster 1

Data1c(:,2)=Data1c(:,2)+6;

%Plot Data

scatter(Data1c(:,1),Data1c(:,2),'ro','MarkerFaceColor','r');

hold on;

scatter(Data2c(:,1),Data2c(:,2),'bo','MarkerFaceColor','b');

axis equal;

xlabel('x');

ylabel('y');

legend('Data for Cluster 1','Data for Cluster 2');

%Save Data

AllData=[Data1c;Data2c]; %All Data

dlmwrite('Data.txt',AllData);

در کد بالا، 500 داده برای کلاستر اول و 500 داده برای کلاستر دوم در مختصات قطبی به صورت تصادفی تولید می‌شود. پس از انتقال دادگان به مختصات کارتزین، دادگان یک کلاستر در جهت محور y به مقدار 6 واحد انتقال داده می‌شود. سپس با استفاده از تابع scatter دادگان تولید شده رسم شده و با دو رنگ آبی و قرمز نمایش داده می‌شوند. در انتها نیز دادگان تولید شده ذخیره می‌شوند تا مجددا بتوان از آن‌ها استفاده نمود. شکل 4 دادگان تولید شده را نمایش می‌دهد.

دادگان تولید شده

شکل 4 - دادگان تولید شده برای خوشه‌یابی

 

کلاسترینگ Fuzzy C-means

در نرم‌افزار متلب به سادگی می‌توان با استفاده از تابع fcm خوشه‌یابی فازی C-means را پیاده‌سازی کرد. با استفاده از کد زیر، خوشه‌یابی فازی C-means برای دادگان تولید شده صورت می‌پذیرد.

%Fuzzy C-means Clustering

clear; clc;

load('Data.txt'); %Path of Data File

X=Data;

[centers,U] = fcm(X,2); % 2 Clusters

maxU=max(U);

index1=find(U(1,:)==maxU);

index2=find(U(2,:)==maxU);

%Plot Clusters

plot(X(index1,1),X(index1,2),'ob','MarkerFaceColor','b')

hold on

plot(X(index2,1),X(index2,2),'or','MarkerFaceColor','r')

plot(centers(1,1),centers(1,2),'xk','MarkerSize',15,'LineWidth',3)

plot(centers(2,1),centers(2,2),'xk','MarkerSize',15,'LineWidth',3)

xlabel('x');

ylabel('y');

legend('Cluster 1','Cluster 2','Center of Clusters');

axis equal;

hold off

در کد بالا ابتدا دادگان لود شده و سپس الگوریتم Fuzzy C-means اجرا می‌شود. در اینجا تابع fcm دو ورودی و دو خروجی دارد. ورودی‌های تابع fcm عبارت است از X که همان دادگان هستند و عدد 2 که مشخص کننده تعداد کلاستر است. می‌توان تعداد کلاستر متفاوتی در نظر گرفت، اما دادگان ما به گونه‌ای تولید شدند که با استفاده از دو کلاستر قابل تفکیک باشند. خروجی centers مشخص کننده مراکز کلاسترها است. ماتریس U مقادیر تابع عضویت دادگان در هر کلاستر را شامل می‌شود. تعداد سطرهای ماتریس U برابر با تعداد کلاسترها و تعداد ستون‌ها برابر با تعداد دادگان است. (مطابق شکل 2)

پس از اجرای تابع fcm، بزرگترین مقدار تابع عضویت برای هر داده در بردار maxU ذخیره می‌شود. با استفاده از بردار maxU، شماره دادگانی که در کلاستر اول قرار می‌گیرند در بردار index1 و شماره دادگانی که در کلاستر دوم قرار می‌گیرند در بردار index2 ذخیره می‌شود. بدین ترتیب هر داده به کلاستری تخصیص داده می‌شود که بزرگترین مقدار تابع عضویت را دارد. در نهایت کلاسترها با رنگ‌های آبی و قرمز رسم شده و مراکز کلاسترها با علامت ضربدر مشکی مشخص می‌شود. شکل 5 خروجی کد بالا را نمایش می‌دهد.

تقسیم دادگان به 2 کلاستر

شکل 5 - تقسیم دادگان به 2 کلاستر

 

همانطور که در شکل 5 مشاهده می‌شود، دو دایره تقریبا با یک خط افقی از یکدیگر تفکیک شده‌اند و در این روش دادگانی که همپوشانی داشته‌اند قابل تشخیص نخواهند بود. به سادگی می‌توان تعداد کلاسترهای دیگری را نیز بررسی کرد. به عنوان مثال برای 3 کلاستر کد زیر نوشته می‌شود.

%Fuzzy C-means Clustering

clear; clc;

load('Data.txt'); %Path of Data File

X=Data;

[centers,U] = fcm(X,3); % 3 Clusters

maxU=max(U);

index1=find(U(1,:)==maxU);

index2=find(U(2,:)==maxU);

index3=find(U(3,:)==maxU);

%Plot Clusters

plot(X(index1,1),X(index1,2),'ob','MarkerFaceColor','b')

hold on

plot(X(index2,1),X(index2,2),'or','MarkerFaceColor','r')

plot(X(index3,1),X(index3,2),'og','MarkerFaceColor','g')

plot(centers(1,1),centers(1,2),'xk','MarkerSize',15,'LineWidth',3)

plot(centers(2,1),centers(2,2),'xk','MarkerSize',15,'LineWidth',3)

plot(centers(3,1),centers(3,2),'xk','MarkerSize',15,'LineWidth',3)

xlabel('x');

ylabel('y');

legend('Cluster 1','Cluster 2','Cluster 3','Center of Clusters');

axis equal;

hold off

شکل 6 خروجی کد بالا را نمایش می‌دهد. همانطور که مشاهده می‌شود سه کلاستر به رنگ‌های آبی، قرمز و سبز به همراه مراکز کلاسترها رسم شده‌است. به صورت شهودی تعداد مناسب کلاستر همان 2 است.

تقسیم دادگان به 3 کلاستر

شکل 6 - تقسیم دادگان به 3 کلاستر

 

در این روش خوشه‌یابی، تعداد کلاسترها از قبل مفروض است. در حالت کلی برای یافتن تعداد کلاستر مناسب، الگوریتم به ازای مقادیر مختلف کلاستر اجرا شده و با توجه به معیارهایی مانند Partition Coefficient، Partition Entropy و یا Separation Index تعداد مناسب کلاستر انتخاب می‌شود.

امتیاز :

دیدگاه بگذارید

avatar