طريقة وارد

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

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

يقلل معيار وارد للحد الأدنى من التباين من إجمالي التباين داخل المجموعات. لتطبيق هذه الطريقة، في كل خطوة، ابحث عن زوج المجموعات الذي يؤدي إلى أقل زيادة في إجمالي التباين داخل المجموعات بعد الدمج. هذه الزيادة هي المسافة التربيعية المرجحة بين مراكز المجموعات. في الخطوة الأولى، تكون جميع المجموعات أحادية (مجموعات تحتوي على نقطة واحدة). لتطبيق خوارزمية تكرارية في ظل دالة الهدف هذه ، يجب أن تكون المسافة الأولية بين العناصر الفردية متناسبة مع مربع المسافة الإقليدية .

وبالتالي، تُعرَّف مسافات التجميع الأولية في طريقة وارد للحد الأدنى من التباين بأنها مربع المسافة الإقليدية بين النقاط:

${\displaystyle d_{ij}=d(\{X_{i}\},\{X_{j}\})={\|X_{i}-X_{j}\|^{2}}.}$

ملاحظة: في البرامج التي تطبق طريقة وارد، من المهم التحقق مما إذا كان ينبغي أن تحدد وسائط الدالة المسافات الإقليدية أو المسافات الإقليدية المربعة.

يمكن تعريف طريقة وارد للحد الأدنى من التباين وتطبيقها بشكل تكراري باستخدام خوارزمية لانس-ويليامز. تُعد خوارزميات لانس-ويليامز عائلة لانهائية من خوارزميات التجميع الهرمي التراكمي، والتي تُمثل بصيغة تكرارية لتحديث مسافات المجموعات في كل خطوة (في كل مرة يتم فيها دمج زوج من المجموعات). في كل خطوة، من الضروري تحسين دالة الهدف (إيجاد الزوج الأمثل من المجموعات المراد دمجها). تُسهّل الصيغة التكرارية عملية إيجاد الزوج الأمثل.

لنفترض أن المجموعات${\displaystyle C_{i}}$و${\displaystyle C_{j}}$ were next to be merged. At this point all of the current pairwise cluster distances are known. The recursive formula gives the updated cluster distances following the pending merge of clusters ${\displaystyle C_{i}}$ and ${\displaystyle C_{j}}$. Let

• ${\displaystyle d_{ij}}$, ${\displaystyle d_{ik}}$, and ${\displaystyle d_{jk}}$ be the pairwise distances between clusters ${\displaystyle C_{i}}$, ${\displaystyle C_{j}}$, and ${\displaystyle C_{k}}$, respectively,
• ${\displaystyle d_{(ij)k}}$ be the distance between the new cluster ${\displaystyle C_{i}\cup C_{j}}$ and ${\displaystyle C_{k}}$.

An algorithm belongs to the Lance-Williams family if the updated cluster distance ${\displaystyle d_{(ij)k}}$ can be computed recursively by

${\displaystyle d_{(ij)k}=\alpha _{i}d_{ik}+\alpha _{j}d_{jk}+\beta d_{ij}+\gamma |d_{ik}-d_{jk}|,}$

where ${\displaystyle \alpha _{i},\alpha _{j},\beta ,}$ and ${\displaystyle \gamma }$ are parameters, which may depend on cluster sizes, that together with the cluster distance function ${\displaystyle d_{ij}}$ determine the clustering algorithm. Several standard clustering algorithms such as single linkage, complete linkage, and group average method have a recursive formula of the above type. A table of parameters for standard methods is given by several authors.^[2][3][4]

Ward's minimum variance method can be implemented by the Lance–Williams formula. For disjoint clusters ${\displaystyle C_{i},C_{j},}$ and ${\displaystyle C_{k}}$ with sizes ${\displaystyle n_{i},n_{j},}$ and ${\displaystyle n_{k}}$ respectively:

${\displaystyle d(C_{i}\cup C_{j},C_{k})={\frac {n_{i}+n_{k}}{n_{i}+n_{j}+n_{k}}}\;d(C_{i},C_{k})+{\frac {n_{j}+n_{k}}{n_{i}+n_{j}+n_{k}}}\;d(C_{j},C_{k})-{\frac {n_{k}}{n_{i}+n_{j}+n_{k}}}\;d(C_{i},C_{j}).}$

Hence Ward's method can be implemented as a Lance–Williams algorithm with

${\displaystyle \alpha _{i}={\frac {n_{i}+n_{k}}{n_{i}+n_{j}+n_{k}}},\qquad \alpha _{j}={\frac {n_{j}+n_{k}}{n_{i}+n_{j}+n_{k}}},\qquad \beta ={\frac {-n_ {ك}} {n_ {i} + n_ {j} + n_ {ك}}}، \ qquad \ gamma =0.}$

The popularity of the Ward's method has led to variations of it. For instance, Ward_p introduces the use of cluster specific feature weights, following the intuitive idea that features could have different degrees of relevance at different clusters.^[5]

• Everitt, B. S., Landau, S. and Leese, M. (2001), Cluster Analysis, 4th Edition, Oxford University Press, Inc., New York; Arnold, London. ISBN 0340761199
• Hartigan, J. A. (1975), Clustering Algorithms, New York: Wiley.
• جاين، أ.ك. ودوبس، ر.س. (1988)، خوارزميات لتجميع البيانات ، نيو جيرسي: برنتيس هول.
• Kaufman, L. and Rousseeuw, PJ (1990), Finding Groups in Data: An Introduction to Cluster Analysis , New York: Wiley.