متد جفت گروه وزن‌دار با میانگین حسابی

متد جفت گروه وزن‌دار با میانگین حسابی (به اختصار: مجگوم) (به انگلیسی: Weighted Pair Group Method with Arithmetic Mean (WPGMA)) یک متد ساده خوشه‌بندی سلسله مراتبی تجمعی (از پایین به بالا) می‌باشد که هدف آن، ایجاد یک درخت ریشه‌دار (که به آن دندروگرام می‌گویند) می‌باشد که ساختار موجود در یک ماتریس زوج‌فاصله را نشان می‌دهد. این متد را به رابرت آر. سوکال و چارلز دانکن میشنر نسبت می‌دهند.

متد جفت گروه وزن‌دار با میانگین حسابی، شبیه به نوع بی‌وزن آن، یعنی متد جفت گروه بدون وزن با میانگین حسابی است که به‌طور عمده بر مبنای توده کردن داده‌ها یا خوشه‌بندی سلسله مراتبی مخصوصاً برای ساخت درخت فیلوژنتیک در بیوانفورماتیک به کار می‌رود.

الگوریتم

همان‌طور که در ابتدای کار ذکر شد، الگوریتم جفت گروه وزن‌دار با میانگین حسابی، با استفاده از یک درخت ریشه دار به نام دندوگرام، ساختار موجود در یک ماتریس زوج‌فاصله را نشان می‌دهد. اگر این ماتریس، یک ماتریس ${\displaystyle n*n}$ باشد، این الگوریتم شامل ${\displaystyle n-1}$ گام می‌باشد؛ در هر گام، نزدیک‌ترین دو خوشه، در اینجا فرض کنید ${\displaystyle a_{i}}$ و ${\displaystyle a_{j}}$ ، به یک خوشه سطح بالاتر ترکیب‌می‌شوند. سپس فاصلهٔ آن با یک خوشهٔ دیگر فرضی به نام ${\displaystyle a_{l}}$، از طریق میانگین حسابی فاصلهٔ بین ${\displaystyle a_{i}}$، ${\displaystyle a_{l}}$ و ${\displaystyle a_{j}}$، ${\displaystyle a_{l}}$ حساب می‌شود:

${\displaystyle Dist_{(a_{i}\cup a_{j}),a_{k}}={\frac {Dist_{a_{i},a_{k}}+Dist_{a_{j},a_{k}}}{2}}}$

مثال

اگر فرض کنیم متد جفت گروه وزن‌دار با میانگین حسابی، روی یک ماتریس ${\displaystyle n*n}$ کار می‌کند، در نتیجه شامل ${\displaystyle n-1}$ گام می‌باشد که در مثال زیر، یک ماتریس ۴ * ۴ داده‌شده، بررسی می‌شود.

گام اول

فرض کنید ۴ المان ${\displaystyle (a_{1},a_{2},a_{3},a_{4})}$ داریم و ماتریس زیر به نام Dist (مخفف فاصله) که نشان‌دهندهٔ فاصلهٔ بین هردو المان را نشان می‌دهد و همچنین ${\displaystyle \phi }$ نشان‌دهندهٔ فاصلهٔ بین ۲ گره در درخت دندوگرام باشد:

در این جدول، کوتاه‌ترین فاصله بین ۲ المان مختلف, متعلق بین ${\displaystyle a_{1}}$ و ${\displaystyle a_{2}}$ و برابر با ۱۵ می‌باشد${\displaystyle (Dist(a_{1},a_{2})=15)}$.

بروزرسانی درخت دندوگرام

حال فرض کنید گره‌ای که ${\displaystyle a_{1}}$ و ${\displaystyle a_{2}}$ را به‌هم متصل‌می‌کند، ${\displaystyle c_{1}}$ نام دارد. در نتیجه به درخت دندوگرام، گره ${\displaystyle c_{1}}$ را اضافه می‌کنیم که فاصله این گره با ${\displaystyle a_{1}}$ و ${\displaystyle a_{2}}$ از راه زیر محاسبه می‌شود: ${\displaystyle \phi (a_{1},c_{1})=\phi (a_{2},c_{1})=Dist(a_{1},a_{2})/2=7.5}$

بروزرسانی ماتریس

با متصل کردن ${\displaystyle a_{1}}$ و ${\displaystyle a_{2}}$، تعداد سطر و ستون ماتریس اولیه یک واحد کاهش می‌یابد و همچنین مقادیر المان‌های ماتریس با تغییراتی مواجه می‌شود که در ذیل توضیح داده‌شده‌است:

${\displaystyle Dist((a_{1},a_{2}),a_{3})=Dist(a_{1},a_{3})/2+Dist(a_{2},a_{3})/2=23.5}$

${\displaystyle Dist((a_{1},a_{2}),a_{4})=Dist(a_{1},a_{4})/2+Dist(a_{2},a_{4})/2=30.5}$

که ماتریس بروزرسانی‌شده و ادامهٔ روند در قسمت بعدی مشخص شده‌است

گام دوم

در گام دوم، نتیجه حاصل از گام اول را ادامه می‌دهیم:

در این جدول، کوتاه‌ترین فاصله بین ۲ المان مختلف, متعلق بین ${\displaystyle (a_{1},a_{2})}$ و ${\displaystyle a_{3}}$ و برابر با ۲۳٫۵ می‌باشد${\displaystyle (Dist((a_{1},a_{2}),a_{3})=23.5)}$ که در درخت دندوگرام، منظور از ${\displaystyle (a_{1},a_{2})}$، گره ${\displaystyle c_{1}}$ می‌باشد.

بروزرسانی درخت دندوگرام

حال فرض کنید گره‌ای که ${\displaystyle c_{1}}$ و ${\displaystyle a_{3}}$ را به‌هم متصل‌می‌کند، ${\displaystyle c_{2}}$ نام دارد. در نتیجه به درخت دندوگرام، گره ${\displaystyle c_{2}}$ را اضافه می‌کنیم که فاصله این گره با ${\displaystyle a_{1}}$، ${\displaystyle a_{2}}$ و ${\displaystyle a_{3}}$ از راه زیر محاسبه می‌شود: ${\displaystyle \phi (a_{1},c_{2})=\phi (a_{2},c_{2})=\phi (a_{3},c_{2})=Dist((a_{1},a_{2}),a_{3})/2=11.75}$

و فاصلهٔ بین ${\displaystyle c_{1}}$ و ${\displaystyle c_{2}}$ برابر است با: ${\displaystyle \phi (c_{1},c_{2})=\phi (a_{1},c_{2})-\phi (a_{1},c_{1})=\phi (a_{2},c_{2})-\phi (a_{2},c_{1})=11.75-7.5=4.25}$

بروزرسانی ماتریس

با متصل کردن ${\displaystyle (a_{1},a_{2})}$ و ${\displaystyle a_{3}}$ , تعداد سطر و ستون ماتریس اولیه یک واحد کاهش می‌یابد و همچنین مقادیر المان‌های ماتریس با تغییراتی مواجه می‌شود که در ذیل توضیح داده‌شده‌است: ${\displaystyle Dist(((a_{1},a_{2}),a_{3}),a_{4})=Dist((a_{1},a_{2}),a_{4})/2+Dist(a_{3},a_{4})/2=28.25}$

گام سوم

در گام سوم، نتیجه حاصل از گام دوم را ادامه می‌دهیم:

در این جدول، کوتاه‌ترین فاصله بین ۲ المان مختلف, متعلق بین ${\displaystyle ((a_{1},a_{2}),a_{3})}$ و ${\displaystyle a_{4}}$ و برابر با ۲۸٫۵ می‌باشد${\displaystyle (Dist(((a_{1},a_{2}),a_{3}),a_{4})=28.5)}$ که در درخت دندوگرام، منظور از ${\displaystyle ((a_{1},a_{2}),a_{3})}$، گره ${\displaystyle c_{2}}$ می‌باشد.

بروزرسانی درخت دندوگرام

حال فرض کنید گره‌ای که ${\displaystyle c_{2}}$ و ${\displaystyle a_{4}}$ را به‌هم متصل‌می‌کند، ${\displaystyle c_{3}}$ نام دارد. در نتیجه به درخت دندوگرام، گره ${\displaystyle c_{3}}$ را اضافه می‌کنیم که فاصله این گره با ${\displaystyle a_{1}}$، ${\displaystyle a_{2}}$، ${\displaystyle a_{3}}$ و ${\displaystyle a_{4}}$ از راه زیر محاسبه می‌شود: ${\displaystyle \phi (a_{1},c_{3})=\phi (a_{2},c_{3})=\phi (a_{3},c_{3})=\phi (a_{4},c_{3})=Dist(((a_{1},a_{2}),a_{3}),a_{4})/2=14.25}$

و فاصلهٔ بین ${\displaystyle c_{2}}$ و ${\displaystyle c_{3}}$ برابر است با: ${\displaystyle \phi (c_{2},c_{3})=\phi (a_{1},c_{3})-\phi (a_{1},c_{2})=\phi (a_{2},c_{3})-\phi (a_{2},c_{2})=\phi (a_{3},c_{3})-\phi (a_{3},c_{2})=14.25-11.75=2.5}$

بروزرسانی ماتریس

با متصل کردن ${\displaystyle ((a_{1},a_{2}),a_{3})}$ و ${\displaystyle a_{4}}$ , تعداد سطر و ستون ماتریس اولیه یک واحد کاهش می‌یابد و تبدیل به یک ماتریس ${\displaystyle 1*1}$ می‌شود که دارای مقدار صفر است.

دندوگرام حاصل

در شکل زیر، دندوگرام حاصل از مثال مطرح‌شده را مشاهده می‌کنید.

جستارهای وابسته

• بیوانفورماتیک
• اتصال-همسایگی
• خوشه‌بندی
• خوشه‌بندی کامل پیوند
• خوشه‌بندی سلسله‌مراتبی