خوشهیابی یا کلاسترینگ (Clustering) یکی از روشهای یادگیری بدون نظارت (Unsupervised Learning) است که با توجه به نظم موجود در دادگان، هر داده به یک خوشه یا کلاستر تخصیص داده میشود. یکی از چالشهای اصلی روشهای کلاسترینگ، یافتن تعداد مناسب کلاستر است. در بسیاری از الگوریتمها، خوشهیابی با تعداد مختلف کلاستر انجام میشود و سپس با استفاده از معیارهای مختلف، تعداد مناسب کلاستر تعیین میگردد. روشهای خوشهیابی را میتوان به دو دسته کلی کریسپ (Crisp) و فازی (Fuzzy) طبقهبندی کرد. در ادامه پس از بررسی خوشهیابی کریسپ و فازی، روش خوشهیابی فازی C-means مورد بررسی قرار میگیرد.
فهرست مطالب
خوشهیابی کریسپ (Crisp Clustering)
در بسیاری از روشها و الگوریتمهای کلاسترینگ، مانند الگوریتم k-means یا الگوریتمهای ترتیبی و سلسله مراتبی، هر داده به صورت قطعی به یک کلاستر تخصیص داده میشود. در واقع تابع عضویت تنها دو مقدار 0 و 1 دارد. اگر مقدار تابع عضویت 0 باشد یعنی داده در آن کلاستر قرار ندارد و اگر 1 باشد یعنی داده در آن کلاستر قرار میگیرد. شکل 1 ده داده دو بُعدی را در صفحه نمایش میدهد که به صورت کریسپ به دو کلاستر تقسیم شدهاست. همانطور که در شکل 1 نمایش داده شدهاست، هر داده به صورت قطعی به یک کلاستر تخصیص داده شده است. ماتریس U مقادیر تابع عضویت هر داده را نمایش میدهد که 0 یا 1 است. سطر بالا در ماتریس U مقدار تابع عضویت دادگان در کلاستر نارنجی و سطر پایین این مقدار در کلاستر سبز است.
شکل 1 - خوشهیابی کریسپ (Crisp) و مقادیر تابع عضویت دادگان
خوشهیابی فازی (Fuzzy Clustering)
در خوشهیابی فازی برخلاف حالت کریسپ، مقادیر تابع عضویت هر داده مقداری بین 0 تا 1 است. در واقع هر داده به یک مقدار در هر کلاستر عضویت دارد و به صورت صد درصدی نمیتوان دادگان را به کلاسترها تخصیص داد. شکل 2 همان دادگان شکل 1 را در حالت خوشهیابی فازی نمایش میدهد. همانطور که مشاهده میشود مقادیر تابع عضویت بین 0 تا 1 قرار دارند.
شکل 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 Dataclear; 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 Clusteringclear; 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 خروجی کد بالا را نمایش میدهد.
شکل 5 - تقسیم دادگان به 2 کلاستر
همانطور که در شکل 5 مشاهده میشود، دو دایره تقریبا با یک خط افقی از یکدیگر تفکیک شدهاند و در این روش دادگانی که همپوشانی داشتهاند قابل تشخیص نخواهند بود. به سادگی میتوان تعداد کلاسترهای دیگری را نیز بررسی کرد. به عنوان مثال برای 3 کلاستر کد زیر نوشته میشود.
%Fuzzy C-means Clusteringclear; 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 است.
شکل 6 - تقسیم دادگان به 3 کلاستر
در این روش خوشهیابی، تعداد کلاسترها از قبل مفروض است. در حالت کلی برای یافتن تعداد کلاستر مناسب، الگوریتم به ازای مقادیر مختلف کلاستر اجرا شده و با توجه به معیارهایی مانند Partition Coefficient، Partition Entropy و یا Separation Index تعداد مناسب کلاستر انتخاب میشود.
دیدگاه بگذارید