Geometric median
جیومیٹری میں، یوکلڈین اسپیس میں نمونے کے نکات کے مجرد سیٹ کا ہندسی میڈین وہ نقطہ ہے جو نمونے کے نکات تک فاصلے کے مجموعے کو کم کرتا ہے۔ یہ میڈین کو عام کرتا ہے، جس میں ایک جہتی ڈیٹا کے لیے فاصلے کے مجموعے کو کم کرنے کی خاصیت ہوتی ہے، اور اعلی جہتوں میں مرکزی رجحان فراہم کرتا ہے۔ اسے 1-میڈین، مقامی میڈین، یوکلڈین منیسم پوائنٹ، یا ٹوریسیلی پوائنٹ کے نام سے بھی جانا جاتا ہے۔ ہندسی میڈین اعداد و شمار میں مقام کا ایک اہم تخمینہ لگانے والا ہے، جہاں اسے ایل 1 تخمینہ لگانے والے کے نام سے بھی جانا جاتا ہے (ایل 1 معیار کے بعد)۔ یہ سہولت کے مقام میں بھی ایک معیاری مسئلہ ہے، جہاں یہ نقل و حمل کی لاگت کو کم کرنے کے لیے کسی سہولت کا پتہ لگانے کے مسئلے کا نمونہ بناتا ہے۔ زیادہ عام کے-میڈین مسئلہ کے کلسٹر مراکز کے مقام کے بارے میں پوچھتا ہے جس میں ہر نمونے کے نقطہ سے اس کے قریب ترین مرکز تک کے فاصلے کو کم سے کم کیا جاتا ہے۔ اگر نقطہ کو کسی لکیر یا منحنی خطوط میں عام کیا جاتا ہے، تو بہترین فٹنگ حل کم از کم مطلق انحراف کے ذریعے پایا جاتا ہے۔ طیارہ میں تین نکات کے لیے مسئلہ کا خاص معاملہ (یعنی نیچے دی گئی تعریف میں = 3 اور = 2) بعض اوقات فرمیٹس مسئلہ کے نام سے بھی جانا جاتا ہے۔ یہ کم سے کم اسٹینر درختوں کی تعمیر میں پیدا ہوتا ہے، اور اسے اصل میں پیئر ڈی فرمیٹ نے ایک مسئلہ کے طور پر پیش کیا تھا اور اسے ایوینجلیسٹا ٹوریسیلی نے حل کیا تھا۔ اس کا حل اب تین نمونے والے نکات سے بنے مثلث کے فرمیٹ پوائنٹ کے نام سے جانا جاتا ہے۔ جیومیٹرک میڈین کو بدلے میں وزن والے فاصلے کے مجموعے کو کم کرنے کے مسئلے کے لیے عام کیا جا سکتا ہے، جسے الفریڈ ویبر کی اپنی 1909 کی کتاب آن فیسلٹی لوکیشن میں اس مسئلے پر بحث کے بعد ویبر مسئلہ کہا جاتا ہے۔ کچھ ذرائع اس کے بجائے ویبر کے مسئلے کو فرمیٹ-ویبر مسئلہ کہتے ہیں، لیکن دوسرے اس نام کو غیر وزن والے ہندسی میڈین مسئلے کے لیے استعمال کرتے ہیں۔ ہندسی درمیانی مسئلے کا ایک سروے فراہم کرتا ہے۔ غیر مجرد پوائنٹ سیٹوں میں مسئلہ کی عمومی شکل کے لیے دیکھیں۔ تعریف رسمی طور پر، ہر ایک کے ساتھ m پوائنٹس کے دیئے گئے سیٹ کے لیے، ہندسی میڈین کی تعریف اس طرح کی جاتی ہے۔ اس صورت میں، یہ n جہتی یوکلڈین خلا میں وہ نقطہ ہے جہاں سے تمام یوکلڈین فاصلوں کا مجموعہ s تک کم سے کم ہے۔ 1 جہتی معاملے کے لیے، ہندسی میڈین میڈین کے ساتھ موافق ہوتا ہے۔ اس کی وجہ یہ ہے کہ غیر متغیر میڈین پوائنٹس سے فاصلے کے مجموعے کو بھی کم کرتا ہے۔ (مزید واضح طور پر، اگر پوائنٹس p1،.، pn ہیں، تو اس ترتیب میں، ہندسی میڈین درمیانی نقطہ ہے اگر n عجیب ہے، لیکن اس کا منفرد طور پر تعین نہیں کیا جاتا ہے اگر n یکساں ہے، جب یہ دو درمیانی پوائنٹس اور کے درمیان لائن سیگمنٹ میں کوئی نقطہ ہو سکتا ہے۔) جب بھی پوائنٹس کالینیئر نہ ہوں تو ہندسی میڈین منفرد ہوتا ہے۔ جیومیٹرک میڈین ترجمہ اور گردش سمیت یوکلڈین مماثلت کی تبدیلیوں کے لیے مساوی ہے۔ اس کا مطلب یہ ہے کہ کوئی بھی جیومیٹرک میڈین کو تبدیل کرکے، یا نمونے کے ڈیٹا میں اسی تبدیلی کو لاگو کرکے اور تبدیل شدہ ڈیٹا کے جیومیٹرک میڈین کو تلاش کرکے ایک ہی نتیجہ حاصل کرے گا۔ یہ خاصیت اس حقیقت سے ملتی ہے کہ ہندسی میڈین کی تعریف صرف جوڑی کے لحاظ سے فاصلے سے کی جاتی ہے، اور یہ آرتھوگنل کارٹیزین نقاط کے نظام پر منحصر نہیں ہے جس کے ذریعے نمونے کے ڈیٹا کی نمائندگی کی جاتی ہے۔ اس کے برعکس، ملٹی ویریٹ ڈیٹا سیٹ کے لیے جزو کے لحاظ سے میڈین عام گردش میں غیر متغیر نہیں ہے، اور نہ ہی یہ نقاط کے انتخاب سے آزاد ہے۔ ہندسی میڈین کا بریک ڈاؤن پوائنٹ 0.0 ہے۔ یعنی نمونے کے اعداد و شمار کا نصف تک من مانی طور پر خراب ہو سکتا ہے، اور نمونوں کا میڈین پھر بھی غیر بدعنوان اعداد و شمار کے مقام کے لیے ایک مضبوط تخمینہ فراہم کرے گا۔ 3 (غیر کالینیئر) پوائنٹس کے لیے، اگر ان پوائنٹس سے بنے مثلث کا کوئی زاویہ 120° یا اس سے زیادہ ہے، تو جیومیٹرک میڈین اس زاویہ کے سرے پر موجود نقطہ ہے۔ اگر تمام زاویہ 120° سے کم ہیں، تو ہندسی میڈین مثلث کے اندر کا نقطہ ہے جو مثلث عمودی کے ہر تین جوڑوں پر 120° کا زاویہ ڈالتا ہے۔ اسے تین چوٹیوں سے بنے مثلث کا فرمیٹ پوائنٹ بھی کہا جاتا ہے۔ (اگر تینوں نکات کالینیئر ہیں تو ہندسی میڈین دو دیگر نکات کے درمیان کا نقطہ ہے، جیسا کہ ایک جہتی میڈین کے معاملے میں ہوتا ہے۔) 4 کوپلانار پوائنٹس کے لیے، اگر چار پوائنٹس میں سے ایک دوسرے تین پوائنٹس سے بنے مثلث کے اندر ہے، تو جیومیٹرک میڈین وہ پوائنٹ ہے۔ بصورت دیگر، چار نکات ایک کنویکس کواڈریلیٹرل بناتے ہیں اور جیومیٹرک میڈین کواڈریلیٹرل کے ڈائیگنلز کا کراسنگ پوائنٹ ہوتا ہے۔ چار کوپلانار پوائنٹس کا ہندسی میڈین چار پوائنٹس کے منفرد ریڈان پوائنٹ کے برابر ہے۔ جیومیٹرک میڈین کے سمجھنے میں آسان تصور ہونے کے باوجود، اس کا حساب لگانا ایک چیلنج ہے۔ مرکز یا کمیت کا مرکز، جس کی تعریف ہندسی میڈین کی طرح ہر نقطہ تک کے فاصلے کے مربعوں کے مجموعے کو کم سے کم کرنے کے طور پر کی گئی ہے، ایک سادہ فارمولے سے پایا جا سکتا ہے-اس کے نقاط پوائنٹس کے نقاط کی اوسط ہیں-لیکن یہ دکھایا گیا ہے کہ کوئی واضح فارمولا، نہ ہی کوئی عین مطابق الگورتھم جس میں صرف ریاضی کی کارروائیاں اور kth جڑیں شامل ہیں، عام طور پر ہندسی میڈین کے لیے موجود نہیں ہو سکتا۔ لہذا، حساب کے اس ماڈل کے تحت اس مسئلے کے حل کے لیے صرف عددی یا علامتی تخمینے ممکن ہیں۔ تاہم، ایک تکراری طریقہ کار کا استعمال کرتے ہوئے ہندسی میڈین کے قریب تخمینہ لگانا سیدھا ہے جس میں ہر قدم زیادہ درست تخمینہ پیدا کرتا ہے۔ اس قسم کے طریقہ کار اس حقیقت سے اخذ کیے جا سکتے ہیں کہ نمونے کے نکات تک کے فاصلے کا مجموعہ ایک کنویکس فنکشن ہے، کیونکہ ہر نمونے کے نقطہ تک کا فاصلہ کنویکس ہوتا ہے اور کنویکس افعال کا مجموعہ کنویکس رہتا ہے۔ لہذا، ہر قدم پر فاصلے کے مجموعے کو کم کرنے والے طریقہ کار مقامی زیادہ سے زیادہ حد میں پھنس نہیں سکتے۔ اس قسم کا ایک عام نقطہ نظر، جسے اینڈری ویزفیلڈ کے کام کے بعد ویزفیلڈ کا الگورتھم کہا جاتا ہے، بار بار دوبارہ وزن والے کم سے کم مربعوں کی ایک شکل ہے۔ یہ الگورتھم وزن کے ایک سیٹ کی وضاحت کرتا ہے جو موجودہ تخمینہ سے لے کر نمونے کے نکات تک کے فاصلے کے الٹا متناسب ہوتے ہیں، اور ایک نیا تخمینہ بناتا ہے جو ان وزنوں کے مطابق نمونے کی وزن اوسط ہے۔ یعنی یہ طریقہ تقریبا تمام ابتدائی پوزیشنوں کے لیے یکجا ہوتا ہے، لیکن جب اس کا ایک تخمینہ دیئے گئے نکات میں سے کسی ایک پر آتا ہے تو وہ یکجا ہونے میں ناکام ہو سکتا ہے۔ ان معاملات کو سنبھالنے کے لیے اس میں ترمیم کی جا سکتی ہے تاکہ یہ تمام ابتدائی نکات کے لیے یکجا ہو جائے۔ اس مسئلے کے تقریبا بہترین حل تلاش کرنے کے لیے زیادہ نفیس ہندسی اصلاح کے طریقہ کار بیان کریں۔ دکھائیں کہ تقریبا لکیری وقت میں ہندسی میڈین کو صوابدیدی درستگی تک کیسے شمار کیا جائے۔ یہ بھی نوٹ کریں کہ اس مسئلے کو سیکنڈ آرڈر کون پروگرام کے طور پر وضع کیا جا سکتا ہے جسے عام اصلاح حل کرنے والوں کا استعمال کرتے ہوئے کثیر الجہتی وقت میں حل کیا جا سکتا ہے۔ ہندسی میڈین کی خصوصیت اگر y تمام دیئے گئے نکات xi سے الگ ہے، تو y ہندسی میڈین ہے اگر اور صرف اس صورت میں جب یہ مطمئن ہو: یہ اس کے مساوی ہے: جس کا ویزفیلڈ کے الگورتھم سے گہرا تعلق ہے۔ عام طور پر، y جیومیٹرک میڈین ہے اگر اور صرف اس صورت میں جب ویکٹر ui ایسے ہوں کہ: جہاں xi  ऒत्त y کے لیے، اور xi = y کے لیے، اس شرط کی ایک مساوی تشکیل یہ ہے کہ اسے میڈین پراپرٹی کی عمومی شکل کے طور پر دیکھا جا سکتا ہے، اس معنی میں کہ پوائنٹس کی کوئی بھی تقسیم، خاص طور پر y کے ذریعے کسی ہائپرپلین کے ذریعے متاثر ہونے پر، ہر طرف y سے مثبت سمتوں کا ایک ہی اور مخالف مجموعہ ہوتا ہے۔ یک جہتی معاملے میں، ہائپرپلین خود نقطہ y ہے، اور سمتوں کا مجموعہ (ہدایت شدہ) گنتی کی پیمائش کو آسان بناتا ہے۔ عامیاں ہندسی میڈین کو یوکلیڈین خالی جگہوں سے لے کر عام ریمینیئن کئی گنا (اور یہاں تک کہ میٹرک خالی جگہوں) تک اسی خیال کا استعمال کرتے ہوئے عام کیا جا سکتا ہے جو ریمینیئن کئی گنا پر فریچیٹ کے معنی کی وضاحت کے لیے استعمال ہوتا ہے۔ آئیے متعلقہ ڈسٹنس فنکشن کے ساتھ ایک ریمینیئن کئی گنا ہوں، آئیے وزن کا مجموعہ 1 ہو، اور اس سے مشاہدات ہونے دیں۔ پھر ہم ڈیٹا پوائنٹس کے وزن والے ہندسی میڈین (یا وزن والے فریشیٹ میڈین) کی وضاحت اس طرح کرتے ہیں۔ اگر تمام وزن برابر ہیں، تو ہم صرف یہ کہتے ہیں کہ یہ ہندسی میڈین ہے۔ میڈوئڈ جیومیٹرک میڈین مطلق انحراف نوٹ حوالہ جات بھی دیکھیں۔ انگریزی میں ترجمہ کیا گیا معنی کثیر الجہتی شماریات غیر پیرامیٹرک شماریات ریاضیاتی اصلاح ہندسی الگورتھم وضاحتی شماریات