اسپریڈشیٹ میں ہاتھی کو کیسے فٹ کریں۔

لنکس کی میز

خلاصہ اور 1 تعارف

2 ابتدائی اور متعلقہ کام

2.1 نمونے لینے کی حکمت عملیوں پر

2.2 دیگر Coreset حکمت عملی

ڈیٹا بیس ایپلی کیشنز کے لیے 2.3 کور سیٹس

2.4 کواڈٹری ایمبیڈنگز

3 فاسٹ کورسیٹس

4 پھیلاؤ کے اثرات کو کم کرنا

4.1 خام اوپری باؤنڈ کا حساب لگانا

4.2 تخمینی حل سے کم پھیلاؤ تک

5 پریکٹس میں تیز کمپریشن

5.1 تجرباتی تجزیہ کا ہدف اور دائرہ کار

5.2 تجرباتی سیٹ اپ

5.3 نمونے لینے کی حکمت عملیوں کا جائزہ لینا

5.4 سٹریمنگ سیٹنگ اور 5.5 ٹیک ویز

6 نتیجہ

7 اعترافات

8 ثبوت، سیوڈو کوڈ، اور ایکسٹینشنز اور 8.1 ثبوت 3.2

8.2 کے-میینز کو کے-میڈین میں کمی

8.3 ایک درخت میں زیادہ سے زیادہ لاگت کا تخمینہ

8.4 الگورتھم 1 میں توسیع

حوالہ جات

خلاصہ

ہم بڑے ڈیٹاسیٹس پر کے-مینز اور کے-میڈین کلسٹرنگ کی نظریاتی اور عملی رن ٹائم حدود کا مطالعہ کرتے ہیں۔ چونکہ مؤثر طریقے سے کلسٹرنگ کے تمام طریقے ڈیٹاسیٹ کو پڑھنے میں لگنے والے وقت سے سست ہیں، اس لیے تیز ترین طریقہ یہ ہے کہ ڈیٹا کو تیزی سے کمپریس کیا جائے اور کمپریسڈ نمائندگی پر کلسٹرنگ کو انجام دیا جائے۔ بدقسمتی سے، پوائنٹس کی تعداد کو کم کرنے کے لیے کوئی آفاقی بہترین انتخاب نہیں ہے - جب کہ بے ترتیب نمونے لینے سے سب لائنر ٹائم میں چلتا ہے اور کورسیٹس نظریاتی ضمانتیں فراہم کرتے ہیں، سابقہ درستگی کو نافذ نہیں کرتا ہے جب کہ پوائنٹس اور کلسٹرز کی تعداد بڑھنے کے ساتھ ساتھ مؤخر الذکر بہت سست ہے۔ درحقیقت، یہ اندازہ لگایا گیا ہے کہ کسی بھی حساسیت پر مبنی کورسیٹ کی تعمیر کے لیے ڈیٹاسیٹ کے سائز میں انتہائی لکیری وقت کی ضرورت ہوتی ہے۔

ہم اس تعلق کی جانچ پہلے یہ دکھا کر کرتے ہیں کہ ایک الگورتھم موجود ہے جو حساسیت کے نمونے لینے کے ذریعے مؤثر طریقے سے لکیری وقت میں کور سیٹس حاصل کرتا ہے - ڈیٹا کو پڑھنے میں لگنے والے وقت کے لاگ فیکٹرز کے اندر۔ کوئی بھی نقطہ نظر جو اس میں نمایاں طور پر بہتر ہوتا ہے اس کے بعد عملی تحقیق کا سہارا لینا چاہیے، جس سے ہمیں جامد اور سلسلہ بندی کی ترتیبات میں حقیقی اور مصنوعی ڈیٹاسیٹس دونوں میں نمونے لینے کی حکمت عملیوں پر غور کرنا چاہیے۔ اس کے ذریعے، ہم وہ حالات دکھاتے ہیں جن میں کلسٹر کی درستگی کو برقرار رکھنے کے لیے کور سیٹس ضروری ہیں اور ساتھ ہی وہ سیٹنگز جن میں تیز تر، کرڈر سیمپلنگ کی حکمت عملی کافی ہے۔ نتیجے کے طور پر، ہم ڈیٹا کے سائز سے قطع نظر مؤثر کلسٹرنگ کے لیے ایک جامع نظریاتی اور عملی خاکہ فراہم کرتے ہیں۔ ہمارا کوڈ عوامی طور پر ماخذ پر دستیاب ہے اور اس میں تجربات کو دوبارہ بنانے کے لیے اسکرپٹ ہیں۔

1 تعارف

جدید ڈیٹا تجزیہ کار کے پاس انتخاب کرنے کے لیے کلسٹرنگ الگورتھم کی کوئی کمی نہیں ہے لیکن، متعلقہ ڈیٹاسیٹس کے بڑھتے ہوئے سائز کو دیکھتے ہوئے، بہت سے اکثر عملی طور پر مفید ہونے کے لیے بہت سست ہوتے ہیں۔ یہ خاص طور پر بگ ڈیٹا پائپ لائنز کے لیے متعلقہ ہے، جہاں کلسٹرنگ الگورتھم عام طور پر کمپریشن کے لیے استعمال ہوتے ہیں۔ اس کا مقصد یہ ہے کہ ایک بہت بڑے ڈیٹاسیٹ کو ایک چھوٹے، زیادہ قابل انتظام ڈیٹا سیٹ سے بدلنا ہے، اس امید کے ساتھ کہ یہ اصل ان پٹ کی اچھی طرح نمائندگی کرتا ہے۔ لائیڈ کا الگورتھم [49] بالکل اسی وجہ سے متعارف کرایا گیا تھا اور کوانٹائزیشن کی خرابی کو کم کرتا ہے – کمپریسڈ ڈیٹاسیٹ میں ہر ان پٹ پوائنٹ سے اس کے نمائندے تک مربع فاصلے کا مجموعہ۔ واضح طور پر سب سے زیادہ مقبول کلسٹرنگ الگورتھم، Lloyd's ایک سے زیادہ تکرار کے لیے چلتا ہے جب تک کہ O(ndk) وقت کی ضرورت ہوتی ہے ہر تکرار کے ساتھ ہم آہنگی نہیں ہوتی، جہاں n پوائنٹس کی تعداد ہے، d خصوصیات کی تعداد ہے اور k کلسٹرز کی تعداد ہے – یا ہدف شدہ کمپریشن کا سائز۔ اس طرح کے ایپلی کیشنز کے لیے، پوائنٹس کی تعداد آسانی سے لاکھوں میں ہوسکتی ہے اور، چونکہ کمپریشن کا معیار k کے ساتھ بڑھتا ہے، اس لیے معیاری مقاصد میں k ہزاروں میں ہو سکتے ہیں [41, 4]۔ ایسی ترتیبات میں، کوئی بھی O(ndk) الگورتھم ممنوعہ طور پر سست ہے۔

اس طرح کی مثالوں نے بڑے ڈیٹا الگورتھم کو جنم دیا ہے جو رن ٹائم میں نظریاتی اور عملی دونوں طرح کی بہتری فراہم کرتے ہیں۔ نظریاتی درستگی اور عملی افادیت کے نقطہ نظر، تاہم، اکثر ایک دوسرے سے متصادم ہوتے ہیں۔ ایک طرف، نظریاتی ضمانتیں اس بات کی یقین دہانی فراہم کرتی ہیں کہ الگورتھم کام کرے گا قطع نظر اس کے کہ اسے جو بھی بدقسمت ان پٹ ملے۔ دوسری طرف، نظریاتی طور پر بہترین الگورتھم کو لاگو کرنے کے لیے اپنے آپ کو قائل کرنا مشکل ہو سکتا ہے جب ایسے کروڈ طریقے ہوں جو چلانے کے لیے تیز تر ہوتے ہیں اور عملی طور پر اچھی کارکردگی کا مظاہرہ کرتے ہیں۔

چونکہ ڈیٹا سیٹس پوائنٹس کی تعداد اور/یا خصوصیات d کی تعداد میں بڑے ہو سکتے ہیں، بڑے ڈیٹا کے طریقوں کو دونوں کے اثرات کو کم کرنا چاہیے۔ خصوصیت کی جگہ کے حوالے سے، سوال کو مؤثر طریقے سے بند کر دیا گیا ہے کیونکہ بے ترتیب تخمینے تیز ہیں (مؤثر طریقے سے لکیری وقت میں چل رہے ہیں)، لاگو کرنے کے لیے عملی ہیں [50]، اور سرایت کے سائز اور معیار پر سخت ضمانتیں فراہم کرتے ہیں۔ پوائنٹس n کی تعداد کو کم کرتے وقت نقطہ نظر کم واضح ہوتا ہے، اور دو الگ الگ پیراڈائمز ہیں جن میں سے ہر ایک الگ الگ فوائد فراہم کرتا ہے۔ ایک طرف، ہمارے پاس یکساں نمونے لینے ہیں، جو ذیلی خطی وقت میں چلتے ہیں لیکن ڈیٹا کے اہم ذیلی سیٹوں سے محروم ہو سکتے ہیں اور اس لیے ڈیٹا پر کچھ مضبوط مفروضوں کے تحت ہی درستگی کی ضمانت دے سکتے ہیں [45]۔ دوسری طرف، سب سے درست نمونے لینے کی حکمت عملی مضبوط کورسیٹ گارنٹی فراہم کرتی ہے، جس میں کمپریسڈ ڈیٹا پر کسی بھی حل کی قیمت اصل ڈیٹاسیٹ پر اس محلول کی لاگت کے ε فیکٹر کے اندر ہوتی ہے [25]۔

ہماری شراکتیں ہم ایک کلاسک مسئلہ کے حوالے سے دونوں تمثیلوں (یکساں نمونے لینے اور مضبوط کورسیٹس) کا مطالعہ کرتے ہیں - کے-مینز اور کے-میڈین مقاصد کے لیے کمپریشن۔ جبکہ یکساں نمونے لینے سے زیادہ سے زیادہ رفتار ملتی ہے لیکن کسی بھی خراب صورت میں درستگی کی کوئی گارنٹی نہیں، تمام دستیاب کور سیٹ تعمیرات میں کم از کم Ω˜(nd + nk) کا وقت ہوتا ہے جب درست کمپریشن کے لیے درکار نمونوں کی کم از کم تعداد پر سخت حدود حاصل ہوتی ہیں۔

یہ دکھانا آسان ہے کہ کوئی بھی الگورتھم جو کمپریشن گارنٹی حاصل کرتا ہے اسے پورا ڈیٹاسیٹ پڑھنا چاہیے[1]۔ اس طرح ایک واضح کھلا سوال یہ ہے کہ لکیری یا تقریبا لکیری وقت میں کیا ضمانتیں حاصل کی جاسکتی ہیں۔ درحقیقت، کلسٹرنگ [6، 5] کے لیے فی الحال دستیاب تیز نمونے لینے والے الگورتھم مضبوط کور سیٹ کی ضمانتیں حاصل نہیں کر سکتے۔ حال ہی میں، [31] نے مضبوط کورسیٹس کے لیے ایک طریقہ تجویز کیا جو وقت کے ساتھ چلتا ہے O˜(nd + nk) اور اسے k-میڈین اور k-مینز کے لیے بہترین ہونے کا اندازہ لگایا۔

اگرچہ یہ پابند k کی چھوٹی قدروں کے لیے مؤثر طریقے سے بہترین ہے، وہاں بہت سی ایپلی کیشنز ہیں جیسے کمپیوٹر وژن [34] یا الگورتھمک فیئرنس [18] جہاں کلسٹرز کی تعداد خصوصیات کی تعداد سے بڑی ہو سکتی ہے۔ اس طرح کی ترتیبات میں، وقت کے لحاظ سے بہترین کورسیٹس کا سوال کھلا رہتا ہے۔ چونکہ زیادہ سے زیادہ سائز کے کورسیٹ کا تعین کرنے کا مسئلہ حال ہی میں بند کر دیا گیا ہے [25, 28, 44]، یہ مرکز پر مبنی کلسٹرنگ کے لیے coreset تحقیق میں بنیادی کھلا مسئلہ ہے۔ ہم اسے یہ دکھا کر حل کرتے ہیں کہ لاگو کرنے میں آسان الگورتھم موجود ہے جو O˜(nd) وقت میں کور سیٹس بناتا ہے – ڈیٹا سیٹ میں پڑھنے میں لگنے والے وقت سے صرف لوگاریتھمک عوامل دور ہیں۔

بہر حال، یہ عملی طور پر کلسٹرنگ کے لیے نمونے لینے والے الگورتھم کے درمیان زمین کی تزئین کو مکمل طور پر روشن نہیں کرتا ہے۔ اگرچہ ہمارا الگورتھم ایک بہترین رن ٹائم اور ایک بہترین کمپریشن دونوں کو حاصل کرتا ہے، لیکن یہ یقینی طور پر ممکن ہے کہ دیگر، کروڈر طریقے تمام عملی مقاصد کے لیے اتنے ہی قابل عمل ہوں۔ ہم اسے باضابطہ طور پر درج ذیل سوال میں بیان کرتے ہیں: بہترین k-means اور k-median coresets کب ضروری ہیں اور coreset کی رفتار اور درستگی کے درمیان عملی تجارت کیا ہے؟

o اس کا جواب دیتے ہیں، ہم نمونے لینے والے الگورتھم کے پورے دورانیے میں ایک مکمل موازنہ کرتے ہیں جو ہمارے تجویز کردہ طریقہ سے زیادہ تیز ہیں۔ اس کے ذریعے ہم تصدیق کرتے ہیں کہ، اگرچہ یہ تیز تر طریقے بہت سے حقیقی دنیا کے ڈیٹاسیٹس پر کافی حد تک درست ہیں، وہاں ڈیٹا کی تقسیم موجود ہے جو ان میں سے ہر ایک کے لیے تباہ کن ناکامی کا سبب بنتی ہے۔ درحقیقت، ان معاملات سے صرف ایک مضبوط کوریسیٹ طریقہ سے بچا جا سکتا ہے۔ اس طرح، اگرچہ بہت سے عملی ترتیبات کو مکمل کور سیٹ کی ضمانت کی ضرورت نہیں ہوتی ہے، لیکن اگر کوئی اپنے کمپریشن میں پراعتماد رہنا چاہتا ہے تو کوئی کونے نہیں کاٹ سکتا۔ ہم تصدیق کرتے ہیں کہ یہ سلسلہ بندی کے پیراڈائم تک پھیلا ہوا ہے اور نیچے دھارے کے کلسٹرنگ کے طریقوں پر لاگو ہوتا ہے۔

خلاصہ یہ کہ ہماری شراکتیں درج ذیل ہیں:

• ہم یہ ظاہر کرتے ہیں کہ کوئی O˜(nd) وقت میں k-مینز اور k-میڈین کے لیے مضبوط کور سیٹ حاصل کر سکتا ہے۔ یہ k-means coresets کے لیے ضروری رن ٹائم پر ایک قیاس کو حل کرتا ہے [31] اور نظریاتی طور پر لاگ فیکٹرز تک بہترین ہے۔

• ڈیٹاسیٹس، کاموں، اور سٹریمنگ/نان سٹریمنگ پیراڈائمز پر ایک جامع تجزیہ کے ذریعے، ہم تصدیق کرتے ہیں کہ لکیری اور سب لائنر ٹائم نمونے لینے کے طریقوں کے درمیان رفتار اور درستگی کے درمیان ایک ضروری تجارت ہے۔ یہ کلسٹرنگ پریکٹیشنر کو ایک بلیو پرنٹ فراہم کرتا ہے کہ ہر کمپریشن الگورتھم کو کب استعمال کرنا ہے تاکہ تیز ترین ممکنہ وقت میں کلسٹرنگ کے مؤثر نتائج حاصل ہوں۔