img

الگوریتم های خوشه بندی سلسله مراتبی

/
/
/

در الگوریتم های سلسله مراتبی بر خلاف الگوریتم های partitional که خوشه بندی در یک مرحله انجام میشود و داده ها در یک state به یک خوشه تبدیل می شوند، داده ها  به تدریج شکسته می شوند یا از پایین به بالا ترکیب می شوند. به این روش خوشه بندی که در آن ابتدا هر داده‌ به عنوان خوشه‌ مجزا در نظر گرفته مي‌شود و در طي فرايندي تکراري در هر مرحله خوشه‌هايي که شباهت بيشتري با يکديگر دارند ترکيب مي‌شوند تا در نهايت يک خوشه و يا تعداد مشخصي خوشه حاصل شود می گویند روش متراکم شونده یا agglomerative. از انواع الگوريتم هاي خوشه‌بندي سلسله مراتبي متراکم شونده رايج مي‌توان از الگوريتمهاي Single-Link، Average-Link و Complete-Link نام برد. هدف ما در این مقاله ارائه توضیحاتی درباره الگوریتم های single linkage و complete linkage و اجرای کد MATLAB برای این الگوریتم ها و توضیح چند نمونه اجرا می باشد.

single linkage
الگوریتم singlelinkage یک الگوریتم سلسله مراتبی است. در الگوریتم های خوشه بندی سلسله مراتبی مثل single linkage complete / پیچیدگی محاسباتی بسیار بالاست و بر خلاف kmeans برای داده های بزرگ خیلی مناسب نیستند.

استفاده از الگوریتم single linkage برای خوش بندی داده های مصنوعی تولید شده توسط تابع getpts() در متلب:

clear all
%close all
clc

fig=figure(2);
axis([-10 10 -10 10]);
[x, y] = getpts(fig);

data=[x, y];
Y=pdist(data,›euclid›);
Z=linkage(Y,›single›);
T=cluster(Z,›maxclust›,۴);
find(T==4)

T_size = size(T)

group_1_number=0;
group_2_number=0;
group_3_number=0;
group_4_number=0;

for nn=1:T_size(1)
if(T(nn)==1)
group_1_number=group_1_number+1;
group_1_x(group_1_number)=x(nn);
group_1_y(group_1_number)=y(nn);
elseif(T(nn)==2)
group_2_number=group_2_number+1;
group_2_x(group_2_number)=x(nn);
group_2_y(group_2_number)=y(nn);
elseif(T(nn)==3)
group_3_number=group_3_number+1;
group_3_x(group_3_number)=x(nn);
group_3_y(group_3_number)=y(nn);
elseif(T(nn)==4)
group_4_number=group_4_number+1;
group_4_x(group_4_number)=x(nn);
group_4_y(group_4_number)=y(nn);
end
end
hold on

plot(group_1_x,group_1_y,›r*›);
plot(group_2_x,group_2_y,›gd›);
plot(group_3_x,group_3_y,›bo›);
plot(group_4_x,group_4_y,›yd›);
برای اینکه ببینیم کدام روش خوشه بندی برای خوشه بندی داده های مورد نظر ما بهتر است باید ابتدا مسئله را بشناسیم. و ببینیم که سرعت برای ما مهم است یا خیر و یا اینکه میزان حافظه ای که در اختیاد داریم چقدر است. الگوریتم های سلسله مراتبی حافظه زیادی مصرف می کنند.
در linkage Single در ابتدای کار هر داده یک خوشه محسوب می شود. در هر مرحله دو خوشه ای که کم ترین فاصله را با هم دارند ادغام می شوند . تعریف این کمترین فاصله در واقع همان تفاوت میان خوشه بندی های سلسله مراتبی است. در هر مرحله دو کلاستری که دو تا از نزدیک ترین اعضای آنها کمترین فاصله را دارند ادغام می شوند. در واقع به این روش خوشه بندی نزدیک ترین همسایه هم می گویند.
الگوریتم خوشه بندی Single روی داده هایی خوب عمل خوشه بندی را انجام می دهد که هم مراکز تفکیک شده ای داشته باشند (مراکز آنها به خوبی مشخص باشد) و هم داده های هم مرکز٫  در صورتی که الگوریتم kmeans که در مقاله ای جداگانه توضیح داده شده، فقط برای داده هایی که مراکز آنها به خوبی تفکیک شده است و داده های متراکم، می تواند به خوبی خوشه بندی انجام دهد. از طرف دیگر پیچیدگی زمانی و حافظه مصرفی الگوریتم های پارتیشنال مانند kmeans معمولا کمتر از الگوریتم های سلسله مراتبی است.linkage  single برای داده هایی که به شکل زنجیر به هم متصل هستند (chain-like) خوب عمل می کند ولی به نویز بین دسته های داده شدیدا حساس است ولی همان طور که در ادامه خواهیم دید الگوریتم linkage complete این مشکل را ندارد.
دو شکل زیر نتایج اعمال الگوریتمlinkage  single روی داده های زنجیری  را نمایش می دهد.
همان طور که مشاهده می شود در اشکال بالا خوشه ها به خوبی تفکیک نشده اند.
خروجی الگوریتم single linkage برای چهار خوشه داده مجزا:
به منظور مقایسه بهتر سعی شده است از شکل های نسبتا مشابهی برای الگوریتم های kmeans،linkage Single وlinkage  complete استفاده شود. البته لازم به ذکر است که در این الگوریتم ها از تابع getpts نرم افزار MATLAB استفاده شده که پس از اجرا نقاط داده توسط کاربر وارد می شود و پس از اتمام ورود داده ها با کلیک راست ماوس یا دابل کلیک خاتمه وارد نمودن نقاط را به الگوریتم اعلام می کنیم که پس از آن روی داده های وارد شده خوشه بندی مورد نظر اعمال می شود. لذا به دلیل امکان وجود خطای کاربری در وارد نمودن نقاط ممکن است اشکال کاملا مشابه نباشند ولی سعی شده که شباهت به اندازه کافی رعایت شود.

خروجی الگوریتم single linkage برای دو خوشه داده مجزا:
خروجی الگوریتم single linkage برای داده های هم مرکز:
خروجی الگوریتم single linkage برای داده های حلزونی:
خروجی الگوریتم single linkage برای داده های هم مرکز و دو outlier:
همان طور که ملاحظه می شود این الگوریتم به درستی دو داده outlier را در خوشه های مربوط به آنها قرار داده است. و برای داده های هم مرکز و مارپیچ نیز خوشه بندی خوبی ارائه کرده است.
linkage single  از این ایده ساده استفاده می کند که نقاطی از هر خوشه را که با خوشه همسایه کمترین فاصله را دارد انتخاب می کند و این ها را یک خوشه فرض می کند و مجددا با خوشه همسایه بعدی هم همین کار را انجام می دهد و این خوشه ها را کنار هم می گذارد تا نهایتا تبدیل به یک خوشه شوند. با استفاده از همین خاصیت است که داده های هم مرکز را که مرکز فشرده و متراکمی دارند خوب کلاستر می کند ولی مثلا شکل خرگوش را که در ادامه آمده کلا یک خوشه در نظر گرفته و فقط چشم آن را یک خوشه جدا در نظر گرفته است. ولی اینکه چنین زنجیره ای از داده ها در single linkage ایجاد می شود مورد پسند ما هست یا خیر بستگی به دامینی که در آن کار می کنیم دارد. مثلا در مورد خرگوش اینکه کلا یک کلاستر شده و چشمش یک کلاستر جدا و مثل اجرای همین مثال در الگوریتم complete آن را از وسط دو نیم نکرده است خوشه بندی بهتری به نظر می رسد. بنابراین single linkage  زنجیره های بلندی از نقاط ایجاد می کند.
یکی از معایبی که الگوریتم Single linkage  دارد با عنوان chaining effect شناخته می شود. به این معنی که چند نقطه داده که پلی میان دو کلاستر ایجاد کنند، باعث می شوند single linkage این دو خوشه را یکی دانسته و به عنوان یک خوشه نشان دهد ولی در complete linkage این اشکال وجود ندارد.

خروجی الگوریتم Single linkage برای داده های هم مرکز در چهار کلاستر:
در تصاویری که با اعداد ۱ ، ۲ و ۳ مشخص شده می توانید خاصیت chaining effect را ببینید.
در اینجا خوشه هایی که به شکل لوزی هستند را تفکیک نکرده و همه را یک خوشه در نظر گرفته است. در شکل خرگوش که در زیر آورده شده مشاهده می کنید که قبلا در حالت دو کلاسه کل بدن خرگوش یک خوشه و چشم ها یک خوشه دیگر  در نظر گرفته شده بود. در ادامه حالت مربوط به چهار خوشه آورده شده است.
خرگوش در ۴ خوشه:
مقایسه اجرای الگوریتم های دو کلاستر و چهار کلاستر single linkage:
در حالت دو خوشه جداسازی داده های مارپیچ یا حلزونی خیلی خوب است. در حالت چهار خوشه نیز نسبت به الگوریتم kmeans که داده های مارپیچ را به چهار قسمت تقسیم می کرد بهتر خوشه بندی کرده و دو مارپیچ را با هم ادغام نکرده است ولی به هر حال دقتlinkage  single تنظیم شده برای دو خوشه روی دو مارپیچ بهتر است.

الگوریتم complete linkage:
به الگوریتم complete،  روش ماکزیمم، قطر یا دورترین همسایه هم می گویند. این روش مسافت بین دو کلاستر را مساوی با دورترین مسافت هر یک از اعضای یک کلاستر با هریک از اعضای کلاستر دیگر در نظر می گیرد. این الگوریتم مانند single linkage است فقط زمانی که می خواهد distance بگیرد فاصله دورتین نقطه از یک خوشه را تا دورترین نقطه از خوشه دیگر را در نظر می گیرد.
همان طور که گفته شد Single داده هایی را که با زنجیره ای از نویز به هم متصل هستند خراب می کند ولی  complete این مشکل را ندارد زیرا به نویز های اینچنینی حساسیت کمتری دارد و چون max می گیرد مشکل single را حل می کند.

شکل فوق مربوط به خوشه بندی الگوریتم complete برای دو دسته داده است که توسط نویز به هم متصل شده اند. در ابتدای همین مقاله نتیجه خوشه بندی همین داده های نویزی را برای الگوریتم single نیز مطرح کردیم و مشاهده شد که نتیجه خوشه بندی خوبی به دنبال نداشت.

استفاده از الگوریتم complete linkage برای خوش بندی داده های مصنوعی تولید شده توسط تابع getpts() در متلب:
clear all
close all
clc

fig=figure(2);
axis([-10 10 -10 10]);
[x, y] = getpts(fig);

data=[x, y];
Y=pdist(data,›euclid›);
Z=linkage(Y,›complete›);
T=cluster(Z,›maxclust›,۴);
find(T==4)
T_size = size(T)

group_1_number=0;
group_2_number=0;
group_3_number=0;
group_4_number=0;
for nn=1:T_size(1)
if(T(nn)==1)
group_1_number=group_1_number+1;
group_1_x(group_1_number)=x(nn);
group_1_y(group_1_number)=y(nn);
elseif(T(nn)==2)
group_2_number=group_2_number+1;
group_2_x(group_2_number)=x(nn);
group_2_y(group_2_number)=y(nn);
elseif(T(nn)==3)
group_3_number=group_3_number+1;
group_3_x(group_3_number)=x(nn);
group_3_y(group_3_number)=y(nn);
elseif(T(nn)==4)
group_4_number=group_4_number+1;
group_4_x(group_4_number)=x(nn);
group_4_y(group_4_number)=y(nn);
end
end

hold on
plot(group_1_x,group_1_y,›r*›);
plot(group_2_x,group_2_y,›gd›);
plot(group_3_x,group_3_y,›bo›);
plot(group_4_x,group_4_y,›yd›);

خروجی الگوریتم complete linkage برای داده های هم مرکز (دو خوشه):
خروجی الگوریتم complete linkage برای داده های هم مرکز (۴ خوشه):
خروجی الگوریتم complete linkage برای داده های حلزونی (دو خوشه):
خروجی الگوریتم complete linkage برای داده های حلزونی (۴ خوشه):
همان طور که مشاهده می شود در الگوریتم complete linkage خوشه های فشرده و کروی شکل ایجاد می شود و نتیجه با خوشه بندی linkage single که سعی می کند هر یک خط های مارپیچ را جدا در نظر بگیرد متفاوت است.
نمونه های بیشتر:
در تصاویر فوق مشاهده می شود که الگوریتم complete link با محاسبه دورترین نقطه که در ادامه توضیح داده شده و همچنین با سعی در ایجاد کلاسترهای متراکم تر تصاویر را بصورت فوق خوشه بندی کرده در صورتی که در single در همین تصاویر هر یک از اجزا جداگانه کلاستر شده بودند.
Complete کلاسترهای متراکم تری نسبت به single ایجاد میکند. در واقع complete سعی میکند کلاسترهایی ایجاد کند که کروی هستند یعنی می خواهد همه نقاط داخل کلاستر به طور معقولی به هم نزدیک باشند ولی single فقط می خواهد نقطه ای از کلاستر به نقطه مورد نظر در کلاستر دیگر نزدیک باشند. Complete می خواهد همه نقاط هر دو کلاستر با یک آستانه مشخصی به هم نزدیک باشند بدین ترتیب شکل کروی می شود ولی در single کلاسترها شبیه زنجیر میشوند. در complete linkage ماکزیمم داریم ولی در Single ، مینیمم فاصله محاسبه می شود. Complete فاصله دو تا از دورترین نقاط از دو خوشه را پیدا می کند یعنی فاصله دورترین نقاط تک تک خوشه ها نسبت به هم را پیدا می نماید ولی این خوشه ها را merge نمی کند بلکه بین آنها به دنبال مینیمم می گردد. به این معنی که دو کلاستری را پیدا می کند که به هم نزدیک تر هستند و آنها را ادغام می کند. بدین تریب خوشه بندی هایی که complete  ارائه می دهد کروی شکل هستند. مثل اجرای الگوریتم complete دو کلاستری روی شکل خرگوش که دو خوشه تقریبا گرد ساخته شده است.
بزرگترین ایراد الگوریتم های سلسله مراتبی این است که حداقل از مرتبه اجرای o(n2) هستند (n تعداد کل نمونه هاست) که غیر خطی است. کلاسترینگ داده های بزرگ با این روش بسیار هزینه بر است. ضمنا روش های سلسله مراتبی نمی توانند آنچه را که قبلا انجام شده undo کنند یا به اصطلاح قابلیت back tracking ندارند.

——————–

برگردان : هدی ابیضی

1 نظرات

نظر بدهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

It is main inner container footer text