Single-linkage clustering
اعداد و شمار میں، سنگل لنکیج کلسٹرنگ درجہ بندی کلسٹرنگ کے کئی طریقوں میں سے ایک ہے۔ یہ باٹم اپ فیشن (ایگمولیریٹو کلسٹرنگ) میں گروپنگ کلسٹرز پر مبنی ہے، ہر مرحلے پر دو کلسٹرز کو جوڑتا ہے جس میں عناصر کی قریب ترین جوڑی ہوتی ہے جو ابھی تک ایک دوسرے کے طور پر ایک ہی کلسٹر سے تعلق نہیں رکھتی ہے۔ یہ طریقہ طویل پتلے کلسٹرز پیدا کرنے کا رجحان رکھتا ہے جس میں ایک ہی کلسٹر کے قریبی عناصر کا فاصلہ کم ہوتا ہے، لیکن کلسٹر کے مخالف سروں پر موجود عناصر دوسرے کلسٹرز کے دو عناصر کے مقابلے میں ایک دوسرے سے بہت زیادہ دور ہو سکتے ہیں۔ ڈیٹا کی کچھ کلاسوں کے لیے، یہ کلاسوں کی وضاحت کرنے میں مشکلات کا باعث بن سکتا ہے جو ڈیٹا کو مفید طور پر ذیلی تقسیم کر سکتے ہیں۔ تاہم، یہ فلکیات میں کہکشاں کے جھنڈوں کا تجزیہ کرنے کے لیے مقبول ہے، جس میں اکثر مادے کے لمبے تار شامل ہو سکتے ہیں۔ اس ایپلی کیشن میں، اسے فرینڈز آف فرینڈز الگورتھم کے نام سے بھی جانا جاتا ہے۔ جمع کرنے والے کلسٹرنگ کے طریقوں کا جائزہ جمع کرنے والے کلسٹرنگ کے عمل کے آغاز میں، ہر عنصر اپنے ایک کلسٹر میں ہوتا ہے۔ اس کے بعد کلسٹرز کو ترتیب وار بڑے کلسٹرز میں ملایا جاتا ہے، یہاں تک کہ تمام عناصر ایک ہی کلسٹر میں ختم ہو جاتے ہیں۔ ہر مرحلے پر، مختصر ترین فاصلے سے الگ ہونے والے دو کلسٹرز کو ملایا جاتا ہے۔ دو کلسٹروں کے درمیان فاصلے کا تعین کرنے کے لیے استعمال ہونے والا فنکشن، جسے لنکیج فنکشن کہا جاتا ہے، وہی ہے جو مجموعی کلسٹرنگ کے طریقوں میں فرق کرتا ہے۔ سنگل لنکیج کلسٹرنگ میں، دو کلسٹرز کے درمیان فاصلے کا تعین عناصر کی ایک جوڑی سے ہوتا ہے: وہ دو عناصر (ہر کلسٹر میں سے ایک) جو ایک دوسرے کے قریب ہیں۔ ان جوڑی کے لحاظ سے فاصلے میں سے سب سے چھوٹا فاصلہ جو کسی بھی مرحلے پر باقی رہتا ہے ان دو کلسٹرز کا سبب بنتا ہے جن کے عناصر شامل ہوتے ہیں۔ اس طریقہ کو قریبی پڑوسی کلسٹرنگ کے نام سے بھی جانا جاتا ہے۔ کلسٹرنگ کے نتیجے کو ڈینڈروگرام کے طور پر دیکھا جا سکتا ہے، جو اس ترتیب کو ظاہر کرتا ہے جس میں کلسٹرز کو ضم کیا گیا تھا اور جس فاصلے پر ہر ایک ضم ہوا تھا۔ ریاضیاتی طور پر، لنکیج فنکشن-کلسٹرز X اور Y کے درمیان فاصلہ D (X، Y)-اس اظہار سے بیان کیا جاتا ہے جہاں X اور Y عناصر کے کوئی بھی دو سیٹ ہیں جنہیں کلسٹر سمجھا جاتا ہے، اور d (x، y) دو عناصر x اور y کے درمیان فاصلے کو ظاہر کرتا ہے۔ نییو الگورتھم مندرجہ ذیل الگورتھم ایک مجموعی اسکیم ہے جو قربت میٹرکس میں قطاروں اور کالموں کو مٹا دیتی ہے کیونکہ پرانے کلسٹرز کو نئے میں ضم کر دیا جاتا ہے۔ قربت میٹرکس تمام فاصلے پر مشتمل ہے۔ کلسٹرنگ کو ترتیب نمبر تفویض کیے جاتے ہیں اور یہ-th کلسٹرنگ کی سطح ہے۔ ترتیب نمبر m والے کلسٹر کو (m) سے ظاہر کیا جاتا ہے اور کلسٹرز کے درمیان قربت کو ظاہر کیا جاتا ہے۔ سنگل لنکیج الگورتھم مندرجہ ذیل مراحل پر مشتمل ہے: سطح اور ترتیب نمبر والے جداگانہ کلسٹرنگ سے شروع کریں۔ موجودہ کلسٹرنگ میں کلسٹرز کی سب سے زیادہ مماثل جوڑی تلاش کریں، جیسے کہ جوڑی، اس کے مطابق جہاں موجودہ کلسٹرنگ میں کلسٹرز کے تمام جوڑوں پر کم از کم ہے۔ ترتیب نمبر میں اضافہ کریں: اگلی کلسٹرنگ بنانے کے لیے کلسٹرز کو ضم کریں اور ایک ہی کلسٹر میں ڈالیں۔ قربت میٹرکس کو اپ ڈیٹ کرنے کے لیے اس کلسٹرنگ کی سطح مقرر کریں، کلسٹرز سے متعلق قطاروں اور کالموں کو حذف کر کے اور نو تشکیل شدہ کلسٹر کے مطابق ایک قطار اور کالم شامل کر کے۔ نئے کلسٹر، جس کی نشاندہی کی گئی ہے اور ایک پرانے کلسٹر کے درمیان قربت کی تعریف اس طرح کی گئی ہے۔ اگر تمام اشیاء ایک کلسٹر میں ہیں، تو رک جائیں۔ ورنہ مرحلہ 2 پر جائیں۔ کام کرنے والی مثال یہ کام کرنے والی مثال جے سی 69 جینیاتی فاصلاتی میٹرکس پر مبنی ہے جو پانچ بیکٹیریا کے 5 ایس رائبوسومل آر این اے ترتیب کی صف بندی سے شمار کی گئی ہے: بیسیلس سبٹیلس ()، بیسیلس اسٹیروتھرموفیلس ()، لییکٹوباسیلس وائریڈسینس ()، ایکولپلاسما موڈیکم ()، اور مائیکروکوکس لیوٹیس ()۔ پہلا قدم پہلا کلسٹرنگ آئیے فرض کریں کہ ہمارے پاس پانچ عناصر ہیں اور ان کے درمیان جوڑی کے لحاظ سے فاصلے کے درج ذیل میٹرکس ہیں: اس مثال میں، کی سب سے کم قیمت ہے، لہذا ہم عناصر کو کلسٹر کرتے ہیں اور۔ پہلی شاخ کی لمبائی کا تخمینہ آئیے اس نوڈ کی نشاندہی کریں جس سے اور اب جڑے ہوئے ہیں۔ ترتیب اس بات کو یقینی بناتی ہے کہ عناصر اور ان سے مساوی فاصلے پر ہوں۔ یہ الٹرا میٹرک مفروضے کی توقع سے مطابقت رکھتا ہے۔ شاخیں شامل ہوتی ہیں اور پھر لمبائی ہوتی ہے (حتمی ڈینڈروگرام دیکھیں) پہلا فاصلہ میٹرکس اپ ڈیٹ ہم پھر ابتدائی قربت میٹرکس کو ایک نئے قربت میٹرکس میں اپ ڈیٹ کرنے کے لیے آگے بڑھتے ہیں (نیچے دیکھیں)، جس کے ساتھ کلسٹرنگ کی وجہ سے سائز میں ایک قطار اور ایک کالم کم ہو جاتا ہے۔ بولڈ ویلیوز نئے فاصلے سے مطابقت رکھتی ہیں، جس کا حساب پہلے کلسٹر کے ہر عنصر اور باقی عناصر میں سے ہر ایک کے درمیان کم سے کم فاصلے کو برقرار رکھتے ہوئے کیا جاتا ہے: اٹالیسائزڈ ویلیوز میٹرکس اپ ڈیٹ سے متاثر نہیں ہوتی ہیں کیونکہ وہ پہلے کلسٹر میں شامل عناصر کے درمیان فاصلے سے مطابقت رکھتی ہیں۔ دوسرا مرحلہ دوسرا کلسٹرنگ اب ہم پچھلے تین اعمال کا اعادہ کرتے ہیں، جو نئے فاصلاتی میٹرکس سے شروع ہوتے ہیں: یہاں، اور سب سے کم اقدار ہیں، لہذا ہم عنصر کے ساتھ اور عنصر کے ساتھ کلسٹر میں شامل ہوتے ہیں۔ دوسری شاخ کی لمبائی کا تخمینہ آئیے اس نوڈ کی نشاندہی کریں جس سے، اور اب جڑے ہوئے ہیں۔ الٹرا میٹرک رکاوٹ کی وجہ سے، شاخیں یا سے، اور سے، اور برابر ہونے کے لیے بھی برابر ہوتی ہیں اور ان کی کل لمبائی درج ذیل ہوتی ہے: ہم گمشدہ شاخ کی لمبائی کا اندازہ لگاتے ہیں: (حتمی ڈینڈروگرام دیکھیں) دوسرا فاصلہ میٹرکس اپ ڈیٹ ہم پھر میٹرکس کو ایک نئے فاصلہ میٹرکس میں اپ ڈیٹ کرنے کے لیے آگے بڑھتے ہیں (نیچے دیکھیں)، جس کے ساتھ اور ساتھ کلسٹرنگ کی وجہ سے سائز میں دو قطاریں اور دو کالم کم ہو جاتے ہیں: حتمی مرحلہ حتمی میٹرکس یہ ہے: لہذا ہم کلسٹرز میں شامل ہوتے ہیں اور۔ آئیے اس (جڑ) نوڈ کی نشاندہی کریں جس سے اور اب جڑے ہوئے ہیں۔ شاخیں جوڑی جاتی ہیں اور پھر ان کی لمبائی ہوتی ہے: ہم باقی شاخ کی لمبائی کا اندازہ لگاتے ہیں: سنگل لنکج ڈینڈروگرام اب ڈینڈروگرام مکمل ہو چکا ہے۔ یہ الٹرا میٹرک ہے کیونکہ تمام ٹپس (،،،، اور) اس سے مساوی فاصلے پر ہیں: اس لیے ڈینڈروگرام اس کے گہرے نوڈ سے جڑا ہوا ہے۔ دیگر روابط سنگل لنکیج کلسٹرنگ کے لیے سادہ الگورتھم بنیادی طور پر کم سے کم پھیلے ہوئے درختوں کے لیے کرسکال کے الگورتھم کی طرح ہے۔ تاہم، سنگل لنکیج کلسٹرنگ میں، جس ترتیب میں کلسٹرز بنتے ہیں وہ اہم ہے، جبکہ کم سے کم پھیلے ہوئے درختوں کے لیے جو چیز اہم ہے وہ پوائنٹس کے جوڑوں کا مجموعہ ہے جو الگورتھم کے ذریعے منتخب کردہ فاصلے بناتے ہیں۔ متبادل لنکج اسکیموں میں مکمل لنکج کلسٹرنگ، اوسط لنکج کلسٹرنگ (یو پی جی ایم اے اور ڈبلیو پی جی ایم اے)، اور وارڈ کا طریقہ شامل ہیں۔ مجموعی کلسٹرنگ کے لیے سادہ الگورتھم میں، الگورتھم میں انٹر کلسٹر کے فاصلے کا حساب لگانے کے لیے صرف ایک مختلف فارمولے کا استعمال کرکے ایک مختلف لنکج اسکیم کو نافذ کیا جا سکتا ہے۔ جس فارمولے کو ایڈجسٹ کیا جانا چاہیے اسے مندرجہ بالا الگورتھم کی تفصیل میں بولڈ ٹیکسٹ کا استعمال کرتے ہوئے نمایاں کیا گیا ہے۔ تاہم، زیادہ موثر الگورتھم جیسے کہ ذیل میں بیان کردہ الگورتھم تمام لنکیج اسکیموں کو اسی طرح عام نہیں کرتے ہیں۔ تیز تر الگورتھم سنگل لنکیج کلسٹرنگ کے لیے بے وقوف الگورتھم کو سمجھنا آسان ہے لیکن وقت کی پیچیدگی کے ساتھ سست ہے۔ 1973 میں، آر سیبسن نے وقت کی پیچیدگی اور خلائی پیچیدگی (دونوں بہترین) کے ساتھ ایک الگورتھم کی تجویز پیش کی جسے SLINK کہا جاتا ہے۔ سلینک الگورتھم دو افعال کے ذریعہ نمبر شدہ آئٹمز کے سیٹ پر کلسٹرنگ کی نمائندگی کرتا ہے۔ ان افعال کا تعین سب سے چھوٹے کلسٹر کو تلاش کرکے کیا جاتا ہے جس میں آئٹم اور کم از کم ایک بڑی تعداد والی آئٹم دونوں شامل ہوتی ہیں۔ پہلا فنکشن، کلسٹر میں سب سے بڑی نمبر والی آئٹم سے آئٹم کا نقشہ بناتا ہے۔ دوسرا فنکشن، کلسٹر کی تخلیق سے وابستہ فاصلے پر آئٹم کا نقشہ بناتا ہے۔ ان افعال کو دو صفوں میں محفوظ کرنا جو ہر آئٹم نمبر کو اس کی فنکشن ویلیو سے جوڑتا ہے، جگہ لیتا ہے، اور یہ معلومات کلسٹرنگ کا تعین کرنے کے لیے کافی ہے۔ جیسا کہ سیبسن دکھاتا ہے، جب آئٹمز کے سیٹ میں کوئی نئی آئٹم شامل کی جاتی ہے، تو آگمینٹڈ سیٹ کے لیے نئے سنگل لنکیج کلسٹرنگ کی نمائندگی کرنے والے اپ ڈیٹ شدہ افعال، جو اسی طرح نمائندگی کرتے ہیں، کو وقت پر پرانے کلسٹرنگ سے بنایا جا سکتا ہے۔ اس کے بعد SLINK الگورتھم آئٹمز پر ایک ایک کر کے لوپ کرتا ہے، اور انہیں کلسٹرنگ کی نمائندگی میں شامل کرتا ہے۔ ایک متبادل الگورتھم، جو ایک ہی زیادہ سے زیادہ وقت اور جگہ کی حدود میں چلتا ہے، سادہ الگورتھم اور کم سے کم پھیلے ہوئے درختوں کے لیے کرسکال کے الگورتھم کے درمیان مساوات پر مبنی ہے۔ کرسکال کے الگورتھم کو استعمال کرنے کے بجائے، کوئی بھی پرائم کے الگورتھم کو استعمال کر سکتا ہے، بائنری ڈھیروں کے بغیر ایک تغیر میں جو دی گئی اشیاء اور فاصلے کے کم سے کم پھیلے ہوئے درخت (لیکن کلسٹرنگ نہیں) کی تعمیر میں وقت اور جگہ لیتا ہے۔ پھر، کرسکال کے الگورتھم کو کم سے کم پھیلے ہوئے درخت کے کناروں سے بنے غیر معمولی گراف پر لاگو کرنا ایک اضافی وقت اور جگہ میں کلسٹرنگ خود پیدا کرتا ہے۔ کلسٹر تجزیہ بھی دیکھیں مکمل لنکج کلسٹرنگ درجہ بندی کلسٹرنگ سالماتی گھڑی پڑوسی سے منسلک یو پی جی ایم اے ڈبلیو پی جی ایم اے حوالہ جات بیرونی لنکس لنک جو میٹ لیب کلسٹر تجزیہ الگورتھم میں استعمال ہوتے ہیں۔