Geometric median
জ্যামিতিতে, ইউক্লিডীয় স্থানে নমুনা বিন্দুর একটি পৃথক সেটের জ্যামিতিক মধ্যমা হল সেই বিন্দু যা নমুনা বিন্দুর দূরত্বের যোগফলকে ন্যূনতম করে। এটি মধ্যমাটিকে সাধারণীকরণ করে, যার এক-মাত্রিক তথ্যের জন্য দূরত্বের সমষ্টি হ্রাস করার বৈশিষ্ট্য রয়েছে এবং উচ্চতর মাত্রায় একটি কেন্দ্রীয় প্রবণতা প্রদান করে। এটি 1-মিডিয়ান, স্পেসিয়াল মিডিয়ান, ইউক্লিডিয়ান মিনিসাম পয়েন্ট বা টরিসেলি পয়েন্ট নামেও পরিচিত। জ্যামিতিক মধ্যমা পরিসংখ্যানে অবস্থানের একটি গুরুত্বপূর্ণ প্রাক্কলনকারী, যেখানে এটি এল 1 প্রাক্কলনকারী হিসাবেও পরিচিত (এল 1 আদর্শের পরে)। এটি সুবিধার অবস্থানের ক্ষেত্রেও একটি সাধারণ সমস্যা, যেখানে এটি পরিবহণের ব্যয় হ্রাস করার জন্য একটি সুবিধা খুঁজে বের করার সমস্যার মডেল তৈরি করে। আরও সাধারণ কে-মিডিয়ান সমস্যাটি প্রতিটি নমুনা বিন্দু থেকে তার নিকটতম কেন্দ্রে দূরত্বের যোগফলকে ন্যূনতম করে কে ক্লাস্টার কেন্দ্রগুলির অবস্থান জিজ্ঞাসা করে। যদি বিন্দুটিকে একটি রেখা বা বক্ররেখায় সাধারণীকরণ করা হয়, তবে সর্বনিম্ন পরম বিচ্যুতির মাধ্যমে সর্বোত্তম উপযুক্ত সমাধান পাওয়া যায়। সমতলে তিনটি বিন্দুর জন্য সমস্যার বিশেষ ক্ষেত্রে (অর্থাৎ, নীচের সংজ্ঞায় = 3 এবং = 2) কখনও কখনও ফার্ম্যাটের সমস্যা হিসাবেও পরিচিত; এটি ন্যূনতম স্টেইনার গাছ নির্মাণের ক্ষেত্রে উদ্ভূত হয় এবং মূলত পিয়েরে ডি ফার্ম্যাট দ্বারা একটি সমস্যা হিসাবে উত্থাপিত হয়েছিল এবং ইভানজেলিস্টা টরিসেলি দ্বারা সমাধান করা হয়েছিল। এর সমাধানটি এখন তিনটি নমুনা বিন্দু দ্বারা গঠিত ত্রিভুজের ফার্মাট বিন্দু হিসাবে পরিচিত। জ্যামিতিক মধ্যমাটি ওজনযুক্ত দূরত্বের সমষ্টি হ্রাস করার সমস্যায় সাধারণীকরণ করা যেতে পারে, যা আলফ্রেড ওয়েবারের 1909 সালের সুবিধার অবস্থান সম্পর্কিত বইয়ে সমস্যাটি নিয়ে আলোচনার পরে ওয়েবার সমস্যা হিসাবে পরিচিত। কিছু সূত্র পরিবর্তে ওয়েবারের সমস্যাকে ফার্মাট-ওয়েবার সমস্যা বলে অভিহিত করে, তবে অন্যরা এই নামটি ওজনহীন জ্যামিতিক মধ্যমা সমস্যার জন্য ব্যবহার করে। জ্যামিতিক মধ্যমা সমস্যার একটি সমীক্ষা প্রদান করে। অ-বিচ্ছিন্ন বিন্দু সেটগুলিতে সমস্যার সাধারণীকরণের জন্য দেখুন। সংজ্ঞা আনুষ্ঠানিকভাবে, প্রতিটি সহ m পয়েন্টের একটি প্রদত্ত সেটের জন্য, জ্যামিতিক মধ্যমা হিসাবে সংজ্ঞায়িত করা হয় এখানে, আর্গ মিন মানে যুক্তির মান যা যোগফলকে ন্যূনতম করে। এই ক্ষেত্রে, এটি n মাত্রিক ইউক্লিডীয় স্থানের সেই বিন্দু যেখান থেকে সমস্ত ইউক্লিডীয় দূরত্বের যোগফল সর্বনিম্ন। বৈশিষ্ট্য 1-মাত্রিক ক্ষেত্রে, জ্যামিতিক মধ্যমা মধ্যমাটির সাথে মিলে যায়। এর কারণ হল অভিন্ন মধ্যমা বিন্দু থেকে দূরত্বের যোগফলকেও কমিয়ে দেয়। (আরও সুনির্দিষ্টভাবে, যদি বিন্দুগুলি p1,., pn হয়, সেই ক্রমে, জ্যামিতিক মধ্যমা হল মধ্যবিন্দু যদি n বিজোড় হয়, তবে n জোড় হয় কিনা তা অনন্যভাবে নির্ধারিত হয় না, যখন এটি দুটি মধ্যবিন্দু এবং এর মধ্যে রেখা বিভাগের যে কোনও বিন্দু হতে পারে।) জ্যামিতিক মধ্যমা অনন্য হয় যখনই বিন্দুগুলি সমান্তরাল হয় না। অনুবাদ এবং ঘূর্ণন সহ ইউক্লিডীয় সাদৃশ্য রূপান্তরের জন্য জ্যামিতিক মধ্যমা সমতুল্য। এর অর্থ হল জ্যামিতিক মধ্যমা রূপান্তরিত করে, অথবা নমুনা উপাত্তে একই রূপান্তর প্রয়োগ করে এবং রূপান্তরিত উপাত্তের জ্যামিতিক মধ্যমা খুঁজে বের করে একই ফলাফল পাওয়া যাবে। এই বৈশিষ্ট্যটি এই সত্য থেকে অনুসরণ করা হয় যে জ্যামিতিক মধ্যমা শুধুমাত্র জোড়া দূরত্ব থেকে সংজ্ঞায়িত করা হয়, এবং অর্থোগোনাল কার্টেসিয়ান স্থানাঙ্কের পদ্ধতির উপর নির্ভর করে না যার দ্বারা নমুনা তথ্য প্রতিনিধিত্ব করা হয়। বিপরীতে, একটি মাল্টিভ্যারিয়েট ডেটা সেটের জন্য উপাদান-ভিত্তিক মধ্যমা সাধারণ ঘূর্ণন অপরিবর্তনীয় নয়, এবং এটি স্থানাঙ্কের পছন্দ থেকে স্বাধীনও নয়। জ্যামিতিক মধ্যকের একটি ভাঙ্গন বিন্দু 0.5। অর্থাৎ, নমুনা তথ্যের অর্ধেক পর্যন্ত নির্বিচারে দূষিত হতে পারে এবং নমুনাগুলির মধ্যমা এখনও দুর্নীতিহীন তথ্যের অবস্থানের জন্য একটি শক্তিশালী প্রাক্কলনকারী প্রদান করবে। বিশেষ ক্ষেত্রে 3টি (অ-সমরেখীয) বিন্দুর জন্য, যদি সেই বিন্দুগুলি দ্বারা গঠিত ত্রিভুজের কোনও কোণ 120° বা তার বেশি হয়, তবে জ্যামিতিক মধ্যমা হল সেই কোণের শীর্ষে অবস্থিত বিন্দু। যদি সমস্ত কোণ 120°-এর কম হয়, তবে জ্যামিতিক মধ্যমা হল ত্রিভুজের অভ্যন্তরের বিন্দু যা ত্রিভুজের প্রতিটি তিন জোড়া শীর্ষে 120° কোণ প্রসারিত করে। এটি তিনটি শীর্ষ দ্বারা গঠিত ত্রিভুজের ফার্মাট বিন্দু হিসাবেও পরিচিত। (যদি তিনটি বিন্দু সমরেখার হয় তবে জ্যামিতিক মধ্যমা হল অন্য দুটি বিন্দুর মধ্যবর্তী বিন্দু, যেমন একটি এক-মাত্রিক মধ্যমা ক্ষেত্রে হয়।) 4টি সহ-সমতলীয় বিন্দুর জন্য, যদি চারটি বিন্দুর মধ্যে একটি অন্য তিনটি বিন্দু দ্বারা গঠিত ত্রিভুজের ভিতরে থাকে, তবে জ্যামিতিক মধ্যমা হল সেই বিন্দু। অন্যথায়, চারটি বিন্দু একটি উত্তল চতুর্ভুজ গঠন করে এবং জ্যামিতিক মধ্যমা চতুর্ভুজের তির্যকগুলির ক্রসিং পয়েন্ট। চারটি কোপ্ল্যানার বিন্দুর জ্যামিতিক মধ্যমা চারটি বিন্দুর অনন্য রেডন বিন্দুর সমান। গাণিতিক মধ্যমা একটি সহজে বোঝা যায় এমন ধারণা হওয়া সত্ত্বেও, এটি গণনা করা একটি চ্যালেঞ্জ হয়ে দাঁড়িয়েছে। কেন্দ্রবিন্দু বা ভরের কেন্দ্র, জ্যামিতিক মধ্যকের অনুরূপ প্রতিটি বিন্দুর দূরত্বের বর্গের যোগফলকে ন্যূনতম হিসাবে সংজ্ঞায়িত করা হয়, একটি সহজ সূত্র দ্বারা পাওয়া যেতে পারে-এর স্থানাঙ্কগুলি বিন্দুর স্থানাঙ্কের গড়-তবে এটি দেখানো হয়েছে যে কোনও স্পষ্ট সূত্র, বা কেবল গাণিতিক ক্রিয়াকলাপ এবং kth মূলের সাথে জড়িত কোনও সঠিক অ্যালগরিদম জ্যামিতিক মধ্যকের জন্য সাধারণভাবে বিদ্যমান থাকতে পারে না। অতএব, গণনার এই মডেলের অধীনে এই সমস্যার সমাধানের জন্য শুধুমাত্র সংখ্যাসূচক বা প্রতীকী অনুমান সম্ভব। যাইহোক, একটি পুনরাবৃত্তিমূলক পদ্ধতি ব্যবহার করে জ্যামিতিক মধ্যকের একটি আনুমানিক হিসাব করা সোজা, যেখানে প্রতিটি ধাপ আরও সঠিক আনুমানিক হিসাব তৈরি করে। এই ধরনের পদ্ধতিগুলি এই সত্য থেকে উদ্ভূত হতে পারে যে নমুনা বিন্দুর দূরত্বের যোগফল একটি উত্তল ফাংশন, কারণ প্রতিটি নমুনা বিন্দুর দূরত্ব উত্তল এবং উত্তল ফাংশনের যোগফল উত্তল থাকে। অতএব, যে পদ্ধতিগুলি প্রতিটি পদক্ষেপে দূরত্বের যোগফল হ্রাস করে সেগুলি স্থানীয় সর্বোত্তমের মধ্যে আটকে যেতে পারে না। এই ধরনের একটি সাধারণ পদ্ধতি, যাকে এন্ড্রে ওয়েজফেল্ডের কাজের পরে ওয়েজফেল্ডের অ্যালগরিদম বলা হয়, এটি পুনরাবৃত্তিমূলকভাবে পুনরায় ওজনযুক্ত সর্বনিম্ন বর্গক্ষেত্রের একটি রূপ। এই অ্যালগরিদম ওজনের একটি সেটকে সংজ্ঞায়িত করে যা বর্তমান অনুমান থেকে নমুনা পয়েন্টের দূরত্বের বিপরীত আনুপাতিক এবং একটি নতুন অনুমান তৈরি করে যা এই ওজন অনুযায়ী নমুনার ওজনযুক্ত গড়। অর্থাৎ, এই পদ্ধতিটি প্রায় সমস্ত প্রাথমিক অবস্থানের জন্য একত্রিত হয়, কিন্তু যখন তার একটি অনুমান প্রদত্ত বিন্দুর একটির উপর পড়ে তখন এটি একত্রিত হতে ব্যর্থ হতে পারে। এই কেসগুলি পরিচালনা করার জন্য এটি সংশোধন করা যেতে পারে যাতে এটি সমস্ত প্রাথমিক পয়েন্টের জন্য একত্রিত হয়। এই সমস্যার প্রায় সর্বোত্তম সমাধান খুঁজে বের করার জন্য আরও পরিশীলিত জ্যামিতিক অপ্টিমাইজেশান পদ্ধতি বর্ণনা করুন। দেখান কিভাবে প্রায় রৈখিক সময়ে জ্যামিতিক মধ্যমা থেকে নির্বিচারে নির্ভুলতা গণনা করা যায়। এছাড়াও লক্ষ্য করুন যে সমস্যাটি দ্বিতীয় ক্রমের শঙ্কু প্রোগ্রাম হিসাবে প্রণয়ন করা যেতে পারে যা সাধারণ অপ্টিমাইজেশন সমাধানকারী ব্যবহার করে বহুপদী সময়ে সমাধান করা যেতে পারে। যদি y সমস্ত প্রদত্ত বিন্দু xi থেকে পৃথক হয়, তবে y হল জ্যামিতিক মধ্যমা যদি এবং শুধুমাত্র যদি এটি সন্তুষ্ট হয়ঃ এটি সমতুল্যঃ যা ওয়েজফেল্ডের অ্যালগরিদমের সাথে ঘনিষ্ঠভাবে সম্পর্কিত। সাধারণভাবে, y হল জ্যামিতিক মধ্যমা যদি এবং শুধুমাত্র যদি এমন ভেক্টর থাকে যেঃ যেখানে xi ষ্ণ y-এর জন্য, এবং xi = y-এর জন্য, এই অবস্থার একটি সমতুল্য সূত্র হল এটি মধ্যমা বৈশিষ্ট্যের সাধারণীকরণ হিসাবে দেখা যেতে পারে, এই অর্থে যে বিন্দুর যে কোনও বিভাজন, বিশেষত y-এর মাধ্যমে কোনও হাইপারপ্লেন দ্বারা প্ররোচিত হিসাবে, প্রতিটি পাশে y থেকে ধনাত্মক দিকের একই এবং বিপরীত যোগফল থাকে। এক মাত্রিক ক্ষেত্রে, হাইপারপ্লেন হল বিন্দু y নিজেই, এবং দিকগুলির যোগফল (নির্দেশিত) গণনা পরিমাপে সহজতর হয়। সাধারণীকরণ জ্যামিতিক মধ্যমা ইউক্লিডীয় স্থান থেকে সাধারণ রিম্যানিয়ান ম্যানিফোল্ড (এবং এমনকি মেট্রিক স্থান) পর্যন্ত একই ধারণা ব্যবহার করে সাধারণীকরণ করা যেতে পারে যা রিম্যানিয়ান ম্যানিফোল্ডের উপর ফ্রেচেট গড় সংজ্ঞায়িত করতে ব্যবহৃত হয়। ধরা যাক সংশ্লিষ্ট দূরত্ব ফাংশন সহ একটি রিমানিয়ান ম্যানিফোল্ড, ধরা যাক 1-এর যোগফলের ওজন, এবং থেকে পর্যবেক্ষণ করা যাক। তারপর আমরা ডেটা পয়েন্টগুলির ওজনযুক্ত জ্যামিতিক মধ্যমা (বা ওজনযুক্ত ফ্রেচেট মধ্যমা) হিসাবে সংজ্ঞায়িত করি। যদি সমস্ত ওজন সমান হয়, আমরা কেবল বলি যে এটি জ্যামিতিক মধ্যমা। আরও দেখুন মেডয়েড জ্যামিতিক মধ্যমা পরম বিচ্যুতি নোটস রেফারেন্স। ইংরেজিতে অনুবাদ করা হয়েছে মানে মাল্টিভ্যারিয়েট পরিসংখ্যান ননপ্যারামেট্রিক পরিসংখ্যান গাণিতিক অপ্টিমাইজেশন জ্যামিতিক অ্যালগরিদম বর্ণনামূলক পরিসংখ্যান