خوشه بندی کامل پیوند یکی از روش های مختلف خوشه بندی سلسله مراتبی است. در ابتدای فرایند، هر عنصر در خوشه ای از خود قرار دارد. سپس خوشه ها به صورت گروهی به گروه های بزرگتر تقسیم می شوند تا زمانی که تمام عناصر در خوشه قرار گیرند. این روش همچنین به عنوان دورترین خوشه همسایه نیز شناخته می شود. نتیجه خوشه بندی را می توان به عنوان یک دندروگرام تجسم کرد، که نشان می دهد که توالی خوشه های همجوشی و فاصله ای که در هر همجوشی اتفاق می افتد. [ ۱] [ ۲] [ ۳]
در هر مرحله، دو خوشه ای که توسط کوتاه ترین فاصله جدا می شوند ترکیب می شوند. تعریف «کوتاهترین فاصله» چیزی است که بین روشهای مختلف خوشه بندی زنجیرهای متفاوت است. در خوشه بندی پیوندی کامل، پیوند میان دو خوشه شامل تمام جفت های عنصر است و فاصله بین خوشه ها برابر فاصله بین دو عنصر ( یکی در هر خوشه ) است که دورتر از یکدیگر هستند. کوتاهترین این پیوندها که در هر مرحله باقی می مانند، موجب همپوشانی دو خوشه می شود که عناصر آن درگیر هستند. از نظر ریاضی تابع پیوند کامل — فاصله ( D ( X, Y بین خوشه X و Y — توسط عبارت روبه رو شرح داده شده است: D ( X , Y ) = max x ∈ X , y ∈ Y d ( x , y )
( d ( x, y فاصله بین عناصر x عضو X و y عضو Y است.
X و Y دو مجموعه از عناصر ( خوشه ها ) هستند.
الگوریتم زیر یک تابع agglomerative است که ردیف ها و ستون ها را در یک ماتریس مجاورت پاک می کند و به عنوان خوشه های قدیمی به صورت های جدید ادغام می شوند. D ماتریس نزدیکی N در N، شامل تمام فاصله های ( d ( i, j. خوشه ها به شماره متوالی ۱، ۲، …، n اختصاص داده می شوند و ( L ( k، سطح kام خوشه بندی هست. یک خوشه با شماره متوالی m مشخص شده است و نزدیکی بین خوشه های ( r ) و ( s ) با [ ( d[ ( r ) , ( s مشخص می شود.
الگوریتم از مراحل زیر تشکیل شده است:
۱. شروع خوشه بندی با در نظر گرفتن سطح L ( 0 ) = ۰ و شماره های متوالی m = ۰.
۲. یافتن جفت خوشه ای مشابه در خوشه بندی فعلی، مانند جفت های ( r ) و ( s ) که طبق اینکه [ ( d[ ( r ) , ( s برابر [ ( max d[ ( i ) , ( j است در جایی که بیش از همه جفت خوشه در خوشه فعلی است.
۳. افزایش شماره متوالی: m = m + 1 و خوشه های ( r ) و ( s ) را به یک خوشه واحد برای تشکیل خوشه بندی بعدی m بپیوندانید. سطح این خوشه بندی را به [ ( L ( m ) = d[ ( r ) , ( s تنظیم کنید.
۴. به روز رسانی ماتریس مجاورت D، با حذف سطر و ستون مربوط به خوشه ( r ) و ( s ) و با اضافه کردن یک سطر و ستون مربوط به خوشه تازه شکل گرفته انجام می شود. نزدیکی بین خوشه جدید، نشان داده شده با ( r, s ) و خوشه قدیمی با ( k ) به عنوان = max d, d[ ( k ) , ( s است.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفدر هر مرحله، دو خوشه ای که توسط کوتاه ترین فاصله جدا می شوند ترکیب می شوند. تعریف «کوتاهترین فاصله» چیزی است که بین روشهای مختلف خوشه بندی زنجیرهای متفاوت است. در خوشه بندی پیوندی کامل، پیوند میان دو خوشه شامل تمام جفت های عنصر است و فاصله بین خوشه ها برابر فاصله بین دو عنصر ( یکی در هر خوشه ) است که دورتر از یکدیگر هستند. کوتاهترین این پیوندها که در هر مرحله باقی می مانند، موجب همپوشانی دو خوشه می شود که عناصر آن درگیر هستند. از نظر ریاضی تابع پیوند کامل — فاصله ( D ( X, Y بین خوشه X و Y — توسط عبارت روبه رو شرح داده شده است: D ( X , Y ) = max x ∈ X , y ∈ Y d ( x , y )
( d ( x, y فاصله بین عناصر x عضو X و y عضو Y است.
X و Y دو مجموعه از عناصر ( خوشه ها ) هستند.
الگوریتم زیر یک تابع agglomerative است که ردیف ها و ستون ها را در یک ماتریس مجاورت پاک می کند و به عنوان خوشه های قدیمی به صورت های جدید ادغام می شوند. D ماتریس نزدیکی N در N، شامل تمام فاصله های ( d ( i, j. خوشه ها به شماره متوالی ۱، ۲، …، n اختصاص داده می شوند و ( L ( k، سطح kام خوشه بندی هست. یک خوشه با شماره متوالی m مشخص شده است و نزدیکی بین خوشه های ( r ) و ( s ) با [ ( d[ ( r ) , ( s مشخص می شود.
الگوریتم از مراحل زیر تشکیل شده است:
۱. شروع خوشه بندی با در نظر گرفتن سطح L ( 0 ) = ۰ و شماره های متوالی m = ۰.
۲. یافتن جفت خوشه ای مشابه در خوشه بندی فعلی، مانند جفت های ( r ) و ( s ) که طبق اینکه [ ( d[ ( r ) , ( s برابر [ ( max d[ ( i ) , ( j است در جایی که بیش از همه جفت خوشه در خوشه فعلی است.
۳. افزایش شماره متوالی: m = m + 1 و خوشه های ( r ) و ( s ) را به یک خوشه واحد برای تشکیل خوشه بندی بعدی m بپیوندانید. سطح این خوشه بندی را به [ ( L ( m ) = d[ ( r ) , ( s تنظیم کنید.
۴. به روز رسانی ماتریس مجاورت D، با حذف سطر و ستون مربوط به خوشه ( r ) و ( s ) و با اضافه کردن یک سطر و ستون مربوط به خوشه تازه شکل گرفته انجام می شود. نزدیکی بین خوشه جدید، نشان داده شده با ( r, s ) و خوشه قدیمی با ( k ) به عنوان = max d, d[ ( k ) , ( s است.
wiki: خوشه بندی کامل پیوند