الوسيط الهندسي

في الهندسة ، يُعرف الوسيط الهندسي لمجموعة نقاط منفصلة في الفضاء الإقليدي بأنه النقطة التي تُقلل مجموع المسافات إلى نقاط العينة. وهذا تعميم للوسيط ، الذي يتميز بخاصية تقليل مجموع المسافات أو الفروق المطلقة للبيانات أحادية البعد. ويُعرف أيضًا بالوسيط المكاني ، ^{[ 1 ]} أو نقطة المجموع الأدنى الإقليدية ، ^{[ 1 ]} أو نقطة توريتشيلي ، ^{[ 2 ]} أو الوسيط-1 . وهو يوفر مقياسًا للنزعة المركزية في الأبعاد الأعلى، ويُعد مسألة أساسية في تحديد مواقع المنشآت ، أي تحديد موقع منشأة لتقليل تكلفة النقل. ^{[ 3 ]}

يُعدّ الوسيط الهندسي مُقدِّرًا هامًا للموقع في الإحصاء، _[ ^{4 ] لأنه} يُقلِّل مجموع المسافات L² بين العينات. ^{[ 5 ]} ويُقارن بالمتوسط، الذي يُقلِّل مجموع مربعات المسافات _L² ؛ وبالوسيط الإحداثي الذي يُقلِّل مجموع المسافات L¹ . أما مسألة الوسيط k الأكثر عمومية، _{فتُطالب} بتحديد مواقع k مركزًا للمجموعات بحيث تُقلِّل مجموع _{المسافات} L² من كل نقطة عينة إلى أقرب مركز لها.

تُعرف الحالة الخاصة لمسألة النقاط الثلاث في المستوى (أي m = 3 و n = 2 في التعريف أدناه) أحيانًا باسم مسألة فيرما ؛ وهي تنشأ عند بناء أشجار شتاينر الدنيا ، وقد طرحها بيير دي فيرما في الأصل وحلها إيفانجيليستا توريتشيلي . ^{[ 6 ]} يُعرف حلها الآن باسم نقطة فيرما للمثلث المُشكّل من النقاط الثلاث. ^{[ 7 ]} يمكن تعميم الوسيط الهندسي بدوره إلى مسألة تقليل مجموع المسافات الموزونة ، والمعروفة باسم مسألة ويبر نسبةً إلى مناقشة ألفريد ويبر للمسألة في كتابه الصادر عام 1909 حول تحديد مواقع المنشآت. ^{[ 1 ]} تُطلق بعض المصادر على مسألة ويبر اسم مسألة فيرما-ويبر ، ^{[ 8 ]} بينما تستخدم مصادر أخرى هذا الاسم لمسألة الوسيط الهندسي غير الموزون. ^{[ 9 ]}

يقدم ويسولوسكي (1993) دراسة شاملة لمسألة الوسيط الهندسي. انظر فيكيت، ميتشل، وبيورر (2005) للاطلاع على تعميمات المسألة لمجموعات النقاط غير المنفصلة.

بصورة رسمية، بالنسبة لمجموعة معينة من m نقطة${\displaystyle \mathbb {X} ^{m}=x_{1},x_{2},\dots ,x_{m}\,}$مع كل${\displaystyle x_{i}\in \mathbb {R} ^{n}}$، يُعرَّف الوسيط الهندسي بأنه القيمة التي تُقلل مجموع المسافات L ₂ :

${\displaystyle {\underset {y\in \mathbb {R} ^{n}}{\operatorname {arg\,min} }}\sum _{i=1}^{m}\left\|x_{i}-y\right\|_{2}\,.}$

هنا، تعني arg min قيمة الوسيط.${\displaystyle y}$والتي تُقلل المجموع. في هذه الحالة، هي النقطة${\displaystyle y}$في الفضاء الإقليدي ذي الأبعاد n، حيث مجموع جميع المسافات الإقليدية إلى${\displaystyle x_{i}}$'s هو الحد الأدنى.

• في الحالة أحادية البعد، يتطابق الوسيط الهندسي مع الوسيط . وذلك لأن الوسيط أحادي المتغير يقلل أيضًا من مجموع المسافات من النقاط. (بتعبير أدق، إذا كانت النقاط هي p1 _، ...، pn _، بهذا الترتيب، فإن الوسيط الهندسي هو النقطة الوسطى).${\displaystyle p_{(n+1)/2}}$إذا كان n فرديًا، ولكن لا يتم تحديده بشكل فريد إذا كان n زوجيًا، حيث يمكن أن يكون أي نقطة في القطعة المستقيمة بين النقطتين الوسطيتين${\displaystyle p_{n/2}}$و${\displaystyle p_{(n/2)+1}}$.) ^{[ 10 ] [ 11 ]}
• يكون الوسيط الهندسي فريدًا عندما لا تكون النقاط على خط مستقيم واحد . ^{[ 12 ]}
• الوسيط الهندسي متغيرٌ مع تحويلات التشابه الإقليدية ، بما في ذلك الإزاحة والدوران . ^{[ 13 ] [ 10} ] وهذا يعني أنه يمكن الحصول على النتيجة نفسها إما بتحويل الوسيط الهندسي ^، أو بتطبيق التحويل نفسه على بيانات العينة وإيجاد الوسيط الهندسي للبيانات المُحوَّلة. وتنتج هذه الخاصية من حقيقة أن الوسيط الهندسي يُعرَّف فقط من المسافات الثنائية، ولا يعتمد على نظام الإحداثيات الديكارتية المتعامدة الذي تُمثَّل به بيانات العينة. في المقابل، فإن الوسيط المكون لمجموعة بيانات متعددة المتغيرات ليس ثابتًا مع الدوران بشكل عام، كما أنه ليس مستقلًا عن اختيار الإحداثيات. ^{[ 13 ]}
• يحتوي الوسيط الهندسي على نقطة انهيار تبلغ 0.5. ^{[ 13 ]} أي أن ما يصل إلى نصف بيانات العينة قد يكون تالفًا بشكل تعسفي، وسيظل وسيط العينات يوفر مقدرًا قويًا لموقع البيانات غير التالفة.

• بالنسبة لثلاث نقاط (غير واقعة على استقامة واحدة )، إذا كانت أي زاوية من زوايا المثلث المُشكَّل من هذه النقاط تساوي 120° أو أكثر، فإن الوسيط الهندسي هو النقطة التي تقع عند رأس تلك الزاوية. أما إذا كانت جميع الزوايا أقل من 120°، فإن الوسيط الهندسي هو النقطة داخل المثلث التي تُقابل زاوية مقدارها 120° مع كل زوج من رؤوس المثلث الثلاثة. ^{[ 10 ]} تُعرف هذه النقطة أيضًا بنقطة فيرما للمثلث المُشكَّل من الرؤوس الثلاثة. (أما إذا كانت النقاط الثلاث تقع على استقامة واحدة، فإن الوسيط الهندسي هو النقطة الواقعة بين النقطتين الأخريين، كما هو الحال مع الوسيط أحادي البُعد).
• بالنسبة لأربع نقاط تقع في مستوى واحد ، إذا كانت إحدى هذه النقاط الأربع داخل المثلث المُشكّل من النقاط الثلاث الأخرى، فإن الوسيط الهندسي هو تلك النقطة. وإلا، فإن النقاط الأربع تُشكّل شكلاً رباعياً محدباً ، ويكون الوسيط الهندسي هو نقطة تقاطع قطري الشكل الرباعي. الوسيط الهندسي لأربع نقاط تقع في مستوى واحد هو نفسه نقطة رادون الفريدة لهذه النقاط الأربع. ^{[ 14 ]}

على الرغم من سهولة فهم مفهوم الوسيط الهندسي، إلا أن حسابه يمثل تحديًا. يمكن إيجاد مركز الكتلة ، الذي يُعرَّف بشكل مشابه للوسيط الهندسي بأنه تقليل مجموع مربعات المسافات إلى كل نقطة، باستخدام صيغة بسيطة - إحداثياته ​​هي متوسطات إحداثيات النقاط - ولكن ثبت أنه لا توجد صيغة صريحة ، ولا خوارزمية دقيقة تتضمن فقط العمليات الحسابية والجذور من الرتبة k ، بشكل عام للوسيط الهندسي. لذلك، لا يمكن إيجاد حل لهذه المشكلة إلا باستخدام تقريبات عددية أو رمزية في ظل هذا النموذج الحسابي . ^{[ 15 ]}

مع ذلك، من السهل حساب تقريب للوسيط الهندسي باستخدام إجراء تكراري، حيث تُنتج كل خطوة تقريبًا أكثر دقة. يمكن اشتقاق هذه الإجراءات من حقيقة أن مجموع المسافات إلى نقاط العينة دالة محدبة ، لأن المسافة إلى كل نقطة عينة محدبة، ومجموع الدوال المحدبة يبقى محدبًا. لذلك، لا يمكن للإجراءات التي تُقلل مجموع المسافات في كل خطوة أن تقع في الحل الأمثل المحلي .

أحد الأساليب الشائعة من هذا النوع، والذي يُسمى خوارزمية فايزفيلد نسبةً إلى عمل إندري فايزفيلد ، ^{[ 16 ]} هو شكل من أشكال المربعات الصغرى المُعاد ترجيحها بشكل متكرر . تُحدد هذه الخوارزمية مجموعة من الأوزان التي تتناسب عكسيًا مع المسافات من التقدير الحالي إلى نقاط العينة، وتُنشئ تقديرًا جديدًا يُمثل المتوسط ​​المرجح للعينة وفقًا لهذه الأوزان. أي،

${\displaystyle \left.y_{k+1}=\left({}\sum _{i=1}^{m}{\frac {x_{i}}{\|x_{i}-y_{k}\|}}\right)\right/\left({}\sum _{i=1}^{m}{\frac {1}{\|x_{i}-y_{k}\|}}\right).}$

تتقارب هذه الطريقة في جميع المواضع الأولية تقريبًا، ولكنها قد تفشل في التقارب عندما يقع أحد تقديراتها على إحدى النقاط المعطاة. ويمكن تعديلها لمعالجة هذه الحالات بحيث تتقارب في جميع النقاط الأولية. ^{[ 12 ]}

يصف كلٌّ من بوز، ماهيشواري، ومورين (2003) إجراءاتٍ أكثر تطورًا لتحسين الهندسة لإيجاد حلولٍ تقريبيةٍ مثلى لهذه المسألة. ويُبيّن كوهين وآخرون (2016) كيفية حساب الوسيط الهندسي بدقةٍ اختياريةٍ في زمنٍ خطيٍّ تقريبًا . تجدر الإشارة أيضًا إلى أنه يُمكن صياغة المسألة كبرنامج مخروطي من الدرجة الثانية.

${\displaystyle {\underset {y\in \mathbb {R} ^{n},\ s\in \mathbb {R} ^{m}}{\min }}\ \sum _{i=1}^{m}s_{i}{\text{ subject to }}s_{i}\geq \left\|x_{i}-y\right\|_{2}{\text{ for }}i=1,\ldots ,m,}$

والتي يمكن حلها في وقت متعدد الحدود باستخدام برامج حل التحسين الشائعة .

إطار فارينيون هو جهاز حاسوب تناظري يمكنه (مع تجاهل مشاكل العالم الحقيقي مثل الاحتكاك) إيجاد الوسيط الهندسي. ^{[ 17 ]}

إذا كانت النقطة y مختلفة عن جميع النقاط المعطاة x _i ، فإن y هي الوسيط الهندسي إذا وفقط إذا كانت تحقق ما يلي:

${\displaystyle 0=\sum _{i=1}^{m}{\frac {x_{i}-y}{\left\|x_{i}-y\right\|}}.}$

هذا يعادل:

${\displaystyle \left.y=\left({}\sum _{i=1}^{m}{\frac {x_{i}}{\|x_{i}-y\|}}\right)\right/\left({}\sum _{i=1}^{m}{\frac {1}{\|x_{i}-y\|}}\right),}$

وهو ما يرتبط ارتباطًا وثيقًا بخوارزمية وايزفيلد.

بشكل عام، يكون y هو الوسيط الهندسي إذا وفقط إذا كانت هناك متجهات u و _i بحيث:

${\displaystyle 0=\sum _{i=1}^{m}u_{i}}$

حيث أن x _i ≠ y ،

${\displaystyle u_{i}={\frac {x_{i}-y}{\left\|x_{i}-y\right\|}}}$

وبالنسبة لـ x _i = y ،

${\displaystyle \|u_{i}\|\leq 1.}$

الصيغة المكافئة لهذا الشرط هي

${\displaystyle \sum _{1\leq i\leq m,x_{i}\neq y}{\frac {x_{i}-y}{\left\|x_{i}-y\right\|}}\leq \left|\{\,i\mid 1\leq i\leq m,x_{i}=y\,\}\right|.}$

يمكن اعتبار ذلك تعميمًا لخاصية الوسيط، بمعنى أن أي تقسيم للنقاط، وخاصةً التقسيم الناتج عن أي مستوى فائق يمر بالنقطة y ، يكون له نفس مجموع الاتجاهات الموجبة المتعاكسة من y على كل جانب. في الحالة أحادية البعد، يكون المستوى الفائق هو النقطة y نفسها، ويتبسط مجموع الاتجاهات إلى مقياس العد (الموجه).

يمكن تعميم الوسيط الهندسي من الفضاءات الإقليدية إلى مشعبات ريمانية عامة (وحتى الفضاءات المترية ) باستخدام نفس الفكرة المستخدمة لتعريف متوسط ​​فريشيه على مشعب ريماني. ^{[ 18 ] [ 19 ]} ليكن${\displaystyle M}$لتكن متعددة شعب ريمانية ذات دالة مسافة مقابلة${\displaystyle d(\cdot ,\cdot )}$، يترك${\displaystyle w_{1},\ldots ,w_{n}}$يكون${\displaystyle n}$الأوزان غير السالبة، ولتكن${\displaystyle x_{1},\ldots ,x_{n}}$ يكون${\displaystyle n}$ملاحظات من${\displaystyle M}$ثم نُعرّف الوسيط الهندسي الموزون${\displaystyle m}$(أو الوسيط المرجح لفريشيه) لنقاط البيانات كأي حل لـ

${\displaystyle m={\underset {x\in M}{\operatorname {arg\,min} }}\sum _{i=1}^{n}w_{i}d(x,x_{i})}$.

إذا كانت جميع الأوزان متساوية، نقول ببساطة أن${\displaystyle m}$هو الوسيط الهندسي.

• ميدويد
• الانحراف المطلق للوسيط الهندسي
• نقطة فيرما-توريتشيلي
• نقطة المركز (مثل متوسط ​​توكي)