Ward's method
اعداد و شمار میں، وارڈ کا طریقہ ایک معیار ہے جس کا اطلاق درجہ بندی کے کلسٹر تجزیہ میں ہوتا ہے۔ وارڈ کا کم از کم تغیر کا طریقہ معروضی فنکشن کے نقطہ نظر کا ایک خاص معاملہ ہے جو اصل میں جو ایچ وارڈ، جونیئر وارڈ نے پیش کیا تھا۔ وارڈ نے ایک عمومی مجموعی درجہ بندی کلسٹرنگ طریقہ کار تجویز کیا، جہاں ہر مرحلے پر ضم ہونے کے لیے کلسٹرز کے جوڑے کو منتخب کرنے کا معیار ایک معروضی فنکشن کی زیادہ سے زیادہ قیمت پر مبنی ہوتا ہے۔ یہ معروضی فنکشن "کوئی بھی فنکشن ہو سکتا ہے جو تفتیش کار کے مقصد کی عکاسی کرتا ہے"۔ بہت سے معیاری کلسٹرنگ کے طریقہ کار اس بہت ہی عام کلاس میں موجود ہیں۔ طریقہ کار کی وضاحت کے لیے، وارڈ نے اس مثال کا استعمال کیا جہاں آبجیکٹیو فنکشن مربعوں کی غلطی کا مجموعہ ہے، اور اس مثال کو وارڈ کا طریقہ یا زیادہ واضح طور پر وارڈ کا کم از کم تغیر کا طریقہ کہا جاتا ہے۔ قریب ترین پڑوسی سلسلہ الگورتھم کو وارڈ کے طریقہ کار کے ذریعہ بیان کردہ اسی کلسٹرنگ کو تلاش کرنے کے لیے استعمال کیا جا سکتا ہے، جو کلسٹر کیے جانے والے پوائنٹس کی تعداد میں ان پٹ ڈسٹنس میٹرکس اور اسپیس لینیر کے سائز کے متناسب ہے۔ کم از کم تغیر کا معیار وارڈ کا کم از کم تغیر کا معیار کل کلسٹر کے اندر کے تغیر کو کم کرتا ہے۔ اس طریقہ کار کو نافذ کرنے کے لیے، ہر مرحلے پر کلسٹرز کی جوڑی تلاش کریں جو ضم ہونے کے بعد کل اندر کلسٹر کے تغیر میں کم سے کم اضافے کا باعث بنتی ہے۔ یہ اضافہ کلسٹر مراکز کے درمیان ایک وزنی مربع فاصلہ ہے۔ ابتدائی مرحلے میں، تمام کلسٹرز سنگلٹن ہوتے ہیں (کلسٹرز جن میں ایک نقطہ ہوتا ہے)۔ اس آبجیکٹیو فنکشن کے تحت ایک ریکرسو الگورتھم کو لاگو کرنے کے لیے، انفرادی اشیاء کے درمیان ابتدائی فاصلہ اسکوائرڈ یوکلڈین فاصلے (متناسب) ہونا چاہیے۔ لہذا وارڈ کے کم از کم تغیر کے طریقہ کار میں ابتدائی کلسٹر فاصلے کو پوائنٹس کے درمیان مربع یوکلڈین فاصلے کے طور پر بیان کیا گیا ہے: نوٹ: سافٹ ویئر میں جو وارڈ کے طریقہ کار کو لاگو کرتا ہے، یہ چیک کرنا ضروری ہے کہ آیا فنکشن کے دلائل کو یوکلڈین فاصلے یا مربع یوکلڈین فاصلے کی وضاحت کرنی چاہیے۔ لانس ولیمز الگورتھم وارڈ کے کم از کم تغیر کے طریقہ کار کو لانس ولیمز الگورتھم کے ذریعے بار بار بیان اور نافذ کیا جا سکتا ہے۔ لانس ولیمز الگورتھم مجموعی درجہ بندی کلسٹرنگ الگورتھم کا ایک لامحدود خاندان ہے جس کی نمائندگی ہر مرحلے پر کلسٹر کے فاصلے کو اپ ڈیٹ کرنے کے لیے ایک تکراری فارمولے کے ذریعے کی جاتی ہے (ہر بار جب کلسٹرز کا ایک جوڑا ضم ہوتا ہے)۔ ہر مرحلے پر، معروضی فنکشن کو بہتر بنانا ضروری ہے (ضم کرنے کے لیے کلسٹرز کی بہترین جوڑی تلاش کریں)۔ تکراری فارمولا زیادہ سے زیادہ جوڑی تلاش کرنے کو آسان بناتا ہے۔ فرض کریں کہ کلسٹرز اور ضم ہونے کے بعد تھے۔ اس مقام پر موجودہ جوڑی کے لحاظ سے کلسٹر کے تمام فاصلے معلوم ہیں۔ تکراری فارمولا کلسٹرز اور کے زیر التواء انضمام کے بعد تازہ ترین کلسٹر فاصلے دیتا ہے۔ چلو، اور کلسٹرز کے درمیان جوڑی کے لحاظ سے فاصلے، اور، بالترتیب، نئے کلسٹر اور کے درمیان کا فاصلہ ہو۔ ایک الگورتھم کا تعلق لانس ولیمز خاندان سے ہے اگر تازہ ترین کلسٹر فاصلے کا حساب بار بار کہاں اور کہاں کے پیرامیٹرز کے ذریعے کیا جا سکتا ہے، جو کلسٹر سائز پر منحصر ہو سکتے ہیں، جو کلسٹر ڈسٹنس فنکشن کے ساتھ مل کر کلسٹرنگ الگورتھم کا تعین کرتے ہیں۔ کئی معیاری کلسٹرنگ الگورتھم جیسے سنگل لنکج، مکمل لنکج، اور گروپ اوسط طریقہ کار میں مندرجہ بالا قسم کا ریکرسو فارمولا ہوتا ہے۔ معیاری طریقوں کے لیے پیرامیٹرز کی ایک ٹیبل کئی مصنفین کی طرف سے دی گئی ہے۔ کارمیک، آر ایم (1971)، "اے ریویو آف کلاسیفیکیشن"، جرنل آف دی رائل شماریاتی سوسائٹی، سیریز اے، 134 (3)، 321-367۔ ملیگن، جی ڈبلیو (1979)، "الٹرا میٹرک ہائیرارکیکل کلسٹرنگ الگورتھمز"، سائیکومیٹریکا، 44 (3)، 343-346۔ وارڈ کا کم از کم تغیر کا طریقہ لانس ولیمز فارمولے کے ذریعے نافذ کیا جا سکتا ہے۔ جداگانہ کلسٹروں کے لیے اور سائز کے ساتھ اور بالترتیب: اس لیے وارڈ کے طریقہ کار کو تغیرات کے ساتھ لانس ولیمز الگورتھم کے طور پر لاگو کیا جا سکتا ہے۔ وارڈ کے طریقہ کار کی مقبولیت اس میں تغیرات کا باعث بنی ہے۔ مثال کے طور پر، وارڈپ کلسٹر مخصوص خصوصیت کے وزن کے استعمال کو متعارف کراتا ہے، اس بدیہی خیال پر عمل کرتے ہوئے کہ خصوصیات مختلف کلسٹرز پر مختلف درجے کی مطابقت رکھ سکتی ہیں۔ حوالہ جات مزید پڑھنے کے لیے ایوریٹ، بی ایس، لینڈو، ایس اینڈ لیز، ایم۔ (2001)، کلسٹر تجزیہ، چوتھا ایڈیشن، آکسفورڈ یونیورسٹی پریس، انکارپوریٹڈ، نیویارک ؛ آرنلڈ، لندن۔ ہارٹیگن، جے۔ اے۔ (1975)، کلسٹرنگ الگورتھم، نیویارک: ولی۔ جین، اے۔ کے۔ اور ڈوبس، آر۔ سی۔ (1988)، الگورتھم فار کلسٹرنگ ڈیٹا، نیو جرسی: پرینٹس ہال۔ کافمین، ایل۔ اور روسییو، پی جے۔ (1990)، ڈیٹا میں گروپس تلاش کرنا: کلسٹر تجزیہ کا تعارف، "نیویارک: ولی۔ کلسٹر تجزیہ الگورتھم