UPGMA

• التجميع الأولي

لنفترض أن لدينا خمسة عناصر${\displaystyle (a,b,c,d,e)}$والمصفوفة التالية${\displaystyle D_{1}}$المسافات الزوجية بينهما  :

في هذا المثال،${\displaystyle D_{1}(a,b)=17}$هي أصغر قيمة لـ${\displaystyle D_{1}}$لذلك نقوم بضم العناصر${\displaystyle a}$و${\displaystyle b}$.

• تقدير طول الفرع الأول

يترك${\displaystyle u}$يشير إلى العقدة التي${\displaystyle a}$و${\displaystyle b}$تم الاتصال الآن. الإعداد ${\displaystyle \delta (a,u)=\delta (b,u)=D_{1}(a,b)/2}$ يضمن أن العناصر${\displaystyle a}$و${\displaystyle b}$متساوية البعد عن${\displaystyle u}$يتوافق هذا مع توقعات فرضية القياس الفائق . الفروع المتصلة${\displaystyle a}$و${\displaystyle b}$ل${\displaystyle u}$ثم تكون لها أطوال ${\displaystyle \delta (a,u)=\delta (b,u)=17/2=8.5}$( انظر إلى مخطط التفرع النهائي )

• تحديث مصفوفة المسافة الأولى

ثم ننتقل إلى تحديث مصفوفة المسافة الأولية${\displaystyle D_{1}}$إلى مصفوفة مسافة جديدة${\displaystyle D_{2}}$(انظر أدناه)، تم تقليص حجمها بمقدار صف واحد وعمود واحد بسبب تجميع${\displaystyle a}$مع${\displaystyle b}$القيم المكتوبة بخط غامق في${\displaystyle D_{2}}$تتوافق مع المسافات الجديدة، المحسوبة عن طريق حساب متوسط ​​المسافات بين كل عنصر من عناصر المجموعة الأولى${\displaystyle (a,b)}$وكل عنصر من العناصر المتبقية:

${\displaystyle D_{2}((a,b),c)=(D_{1}(a,c)\times 1+D_{1}(b,c)\times 1)/(1+1)=(21+30)/2=25.5}$

${\displaystyle D_{2}((a,b),d)=(D_{1}(a,d)+D_{1}(b,d))/2=(31+34)/2=32.5}$

${\displaystyle D_{2}((a,b),e)=(D_{1}(a,e)+D_{1}(b,e))/2=(23+21)/2=22}$

القيم المائلة في${\displaystyle D_{2}}$لا تتأثر بتحديث المصفوفة لأنها تتوافق مع المسافات بين العناصر غير المشاركة في المجموعة الأولى.

• التجميع الثاني

نكرر الآن الخطوات الثلاث السابقة، بدءًا من مصفوفة المسافة الجديدة${\displaystyle D_{2}}$

هنا،${\displaystyle D_{2}((a,b),e)=22}$هي أصغر قيمة لـ${\displaystyle D_{2}}$لذلك ننضم إلى المجموعة${\displaystyle (a,b)}$وعنصر${\displaystyle e}$.

• تقدير طول الفرع الثاني

يترك${\displaystyle v}$يشير إلى العقدة التي${\displaystyle (a,b)}$و${\displaystyle e}$أصبحت الآن متصلة. وبسبب قيد القياس الفائق، فإن الفروع المتصلة${\displaystyle a}$أو${\displaystyle b}$ل${\displaystyle v}$، و${\displaystyle e}$ل${\displaystyle v}$متساوية ولها الأطوال التالية: ${\displaystyle \delta (a,v)=\delta (b,v)=\delta (e,v)=22/2=11}$

نستنتج طول الفرع المفقود: ${\displaystyle \delta (u,v)=\delta (e,v)-\delta (a,u)=\delta (e,v)-\delta (b,u)=11-8.5=2.5}$ ( انظر إلى مخطط التفرع النهائي )

• تحديث مصفوفة المسافة الثانية

ثم ننتقل إلى التحديث${\displaystyle D_{2}}$إلى مصفوفة مسافة جديدة${\displaystyle D_{3}}$(انظر أدناه)، تم تقليص حجمها بمقدار صف واحد وعمود واحد بسبب تجميع${\displaystyle (a,b)}$مع${\displaystyle e}$القيم المكتوبة بخط غامق في${\displaystyle D_{3}}$تتوافق مع المسافات الجديدة، المحسوبة عن طريق المتوسط ​​النسبي :

${\displaystyle D_{3}(((a,b),e),c)=(D_{2}((a,b),c)\times 2+D_{2}(e,c)\times 1)/(2+1)=(25.5\times 2+39\times 1)/3=30}$

بفضل هذا المتوسط ​​النسبي، يأخذ حساب هذه المسافة الجديدة في الاعتبار الحجم الأكبر لـ${\displaystyle (a,b)}$مجموعة (عنصران) فيما يتعلق بـ${\displaystyle e}$(عنصر واحد). وبالمثل:

${\displaystyle D_{3}(((a,b),e),d)=(D_{2}((a,b),d)\times 2+D_{2}(e,d)\times 1)/(2+1)=(32.5\times 2+43\times 1)/3=36}$

وبالتالي، فإن المتوسط ​​النسبي يعطي وزناً متساوياً للمسافات الأولية للمصفوفة${\displaystyle D_{1}}$وهذا هو السبب في أن الطريقة غير موزونة ، ليس فيما يتعلق بالإجراء الرياضي ولكن فيما يتعلق بالمسافات الأولية.

• التجميع الثالث

نكرر مرة أخرى الخطوات الثلاث السابقة، بدءًا من مصفوفة المسافة المحدثة${\displaystyle D_{3}}$.

هنا،${\displaystyle D_{3}(c,d)=28}$هي أصغر قيمة لـ${\displaystyle D_{3}}$لذلك نقوم بضم العناصر${\displaystyle c}$و${\displaystyle d}$.

• تقدير طول الفرع الثالث

يترك${\displaystyle w}$يشير إلى العقدة التي${\displaystyle c}$و${\displaystyle d}$أصبحت الفروع متصلة الآن.${\displaystyle c}$و${\displaystyle d}$ل${\displaystyle w}$ثم تكون لها أطوال ${\displaystyle \delta (c,w)=\delta (d,w)=28/2=14}$( انظر إلى مخطط التفرع النهائي )

• تحديث مصفوفة المسافة الثالثة

يوجد إدخال واحد للتحديث، مع الأخذ في الاعتبار أن العنصرين${\displaystyle c}$و${\displaystyle d}$لكل منهم مساهمة قدرها${\displaystyle 1}$في الحساب المتوسط :

${\displaystyle D_{4}((c,d),((a,b),e))=(D_{3}(c,((a,b),e))\times 1+D_{3}(d,((a,b),e))\times 1)/(1+1)=(30\times 1+36\times 1)/2=33}$

النهائي${\displaystyle D_{4}}$المصفوفة هي:

لذلك ننضم إلى المجموعات${\displaystyle ((a,b),e)}$و${\displaystyle (c,d)}$.

يترك${\displaystyle r}$يشير إلى العقدة (الجذرية) التي${\displaystyle ((a,b),e)}$و${\displaystyle (c,d)}$أصبحت الفروع متصلة الآن.${\displaystyle ((a,b),e)}$و${\displaystyle (c,d)}$ل${\displaystyle r}$ثم تكون لها أطوال:

${\displaystyle \delta (((a,b),e),r)=\delta ((c,d),r)=33/2=16.5}$

نستنتج طول الفرعين المتبقيين:

${\displaystyle \delta (v,r)=\delta (((a,b),e),r)-\delta (e,v)=16.5-11=5.5}$

${\displaystyle \delta (w,r)=\delta ((c,d),r)-\delta (c,w)=16.5-14=2.5}$

اكتمل الآن مخطط التفرع. ^{[ 5 ]} وهو مخطط فائق القياس لأن جميع الأطراف (${\displaystyle a}$ل${\displaystyle e}$) متساوية البعد عن${\displaystyle r}$ :

${\displaystyle \delta (a,r)=\delta (b,r)=\delta (e,r)=\delta (c,r)=\delta (d,r)=16.5}$

وبالتالي، فإن مخطط التفرع يتم تجذيره بواسطة${\displaystyle r}$، أعمق عقدة فيها.

تشمل مخططات الربط البديلة التجميع بالربط الأحادي ، والتجميع بالربط الكامل ، والتجميع بالربط المتوسط ​​WPGMA . ويكمن تطبيق ربط مختلف في استخدام صيغة مختلفة لحساب المسافات بين المجموعات خلال خطوات تحديث مصفوفة المسافة في الخوارزمية المذكورة أعلاه. يتجنب التجميع بالربط الكامل عيبًا في طريقة التجميع بالربط الأحادي البديلة، ألا وهو ما يُعرف بظاهرة الترابط ، حيث قد تُجبر المجموعات المُشكّلة عبر التجميع بالربط الأحادي على التجمع معًا بسبب تقارب بعض العناصر، حتى وإن كانت العديد من العناصر في كل مجموعة متباعدة جدًا. يميل التجميع بالربط الكامل إلى إيجاد مجموعات متراصة ذات أقطار متساوية تقريبًا. ^{[ 6 ]}

مقارنة بين مخططات التفرع التي تم الحصول عليها باستخدام طرق تجميع مختلفة من نفس مصفوفة المسافة .

التجميع أحادي الارتباط	التجميع بالارتباط الكامل	التجميع بالارتباط المتوسط: WPGMA	التجميع بالارتباط المتوسط: UPGMA.