Геометричний центр

Шаблон:Unibox Геометричний центр дискретної множини точок евклідового простору (говорячи статистичною мовою — вибірки) — точка, в якій мінімізується сума відстаней до точок множини. Геометричний центр у математичній статистиці узагальнює медіану, яка мінімізує відстань в одновимірній вибірці даних. Таким чином, геометричний центр відбиває центральну тенденцію в просторах високої розмірності. Поняття відоме також за назвами 1-медіана^[1], просторова медіанаШаблон:Sfn, або точка ТоррічелліШаблон:Sfn.

Геометричний центр є важливою оцінною функцією зсуву в статистиціШаблон:Sfn, в якій це поняття відоме як оцінка L₁Шаблон:Sfn. Пошук геометричного центра є також стандартною задачею при розміщенні об'єктів, де моделюється розташування об'єктів (виробництва чи споживання) з метою мінімізації транспортних витратШаблон:Sfn.

Окремий випадок задачі для трьох точок на площині (тобто m = 3 і n = 2 в термінах, описаних нижче) іноді називають задачею Ферма. Вона виникає при побудові мінімальних дерев Штейнера. Вперше як задачу її поставив П'єр Ферма, а розв'язав Еванджеліста Торрічеллі Шаблон:Sfn. Розв'язок цієї задачі нині відомий як точка Ферма трикутникаШаблон:Sfn. У свою чергу, пошук геометричного центра можна узагальнити до задачі мінімізації суми зважених відстаней. Ця задача відома як задача Вебера, оскільки Альфред Вебер обговорював її в книзі 1909 року з питань розміщення об'єктівШаблон:Sfn. У деяких джерелах використано назву задача Ферма — ВебераШаблон:Sfn, але деякі джерела використовують ту саму назву для незваженої задачіШаблон:Sfn.

ВесоловськийШаблон:Sfn дав огляд задачі геометричного центра. Обговорення узагальнення задачі для випадку недискретних множин див. у статті Фекете, Мічела та БоєраШаблон:Sfn.

Визначення

Формально, якщо дано множину, що містить m точок $x_{1}, x_{2}, \dots, x_{m}$ , де всі $x_{i} \in ℝ^{n}$ , геометричний центр визначають як: Геометричний центр $= \underset{y \in ℝ^{n}}{a r g m i n} \sum_{i = 1}^{m} {‖ x_{i} - y ‖}_{2}$

Зауважте, що тут arg min означає значення аргументу $y$ , за якого досягається мінімальна сума. Це точка $y$ , для якої сума всіх евклідових відстаней до $x_{i}$ , мінімальна.

Властивості

Для випадку одновимірного простору медіана є геометричним центром (якщо точок парне число, геометричний центр може бути не єдиним). Це тому, що одновимірна медіана мінімізує суму відстаней до точокШаблон:Sfn.
Геометричний центр є єдиним для всіх випадків, коли точки не колінеарні Шаблон:Sfn.
Геометричний центр Шаблон:Не перекладено для евклідового подібності, паралельного перенесення та обертання Шаблон:Sfn Шаблон:Sfn. Це означає, що той самий результат вийде, якщо знайти образ центра, побудованого до перетворення, або, застосувавши те саме перетворення до всіх точок вибірки, потім знайти геометричний центр. Ця властивість випливає з факту, що геометричний центр визначається лише з попарних відстаней і не залежить від системи ортогональних декартових координат. Разом з тим, покомпонентна медіана для багатовимірних даних при обертанні, в загальному випадку, не є інваріантом і залежить від вибору координатШаблон:Sfn.
Геометричний центр має Шаблон:Не перекладено 0,5Шаблон:Sfn. Тобто, до половини даних вибірки можуть бути ненадійними, але геометричний центр вибірки залишається стійкою оцінкою положення незіпсованих даних.

Окремі випадки

Для 3 (неколінеарних) точок, якщо якийсь із кутів трикутника з вершинами в цих точках становить 120° або більше, то геометричний центр — це вершина цього кута. Якщо всі кути менші ніж 120 °, геометричний центр — це точка всередині трикутника, яка становить кут 120 ° із кожною парою вершин трикутникаШаблон:Sfn. Ця точка відома як точка Ферма трикутника (якщо три точки колінеарні, то геометричний центр збігається з точкою, що лежить між двома іншими).
Для 4 компланарних точок, якщо одна з чотирьох точок лежить усередині трикутника, утвореного трьома іншими точками, геометричним місцем буде ця внутрішня точка. В іншому випадку чотири точки утворюють опуклий чотирикутник і геометричним центром слугу точка перетину діагоналей чотирикутника. Геометричний центр чотирьох копланарних точок — це те саме, що і єдина точка Радона для чотирьох точок^[2].

Обчислення

Попри простоту поняття геометричного центру для розуміння, його обчислення викликає труднощі. Центроїд трикутника (тобто його центр мас), що визначається аналогічно геометричному центру як мінімізація суми квадратів відстаней до кожної точки, можна отримати за допомогою простих формул — його координати є середнім арифметичним координат точок. Однак така проста формула для геометричного центру невідома. Навіть було показано, що не існує ні явної формули, ні точного алгоритму, який використовує лише арифметичні операції та операції добування коренів. Таким чином, існують лише апроксимації для розв'язання цієї задачі^[3].

Однак можна наближено обчислити геометричний центр, використовуючи ітеративну процедуру, в якій кожен крок дає точніше наближення. Процедури цього типу можна отримати з того факту, що сума відстаней до точок вибірки є опуклою функцією, оскільки відстань до кожної точки вибірки є опуклою функцією, а сума опуклих функцій також є опуклою функцією. Таким чином, процедура зменшення суми відстаней не може потрапити до локального оптимуму.

Один із підходів такого роду — алгоритм Вайсфельда (Шаблон:Не перекладено)Шаблон:Sfn Шаблон:Sfn Шаблон:Sfn є видом Шаблон:Не перекладено зі змінними вагами. Цей алгоритм задає множину ваг, які обернено пропорційні відстаням до поточного наближення, і обчислює нове наближення, що є середнім зваженим точок вибірки згідно з цими вагами. Тобто

y_{i + 1} = (\sum_{j = 1}^{m} \frac{x_{j}}{‖ x_{j} - y_{i} ‖}) / (\sum_{j = 1}^{m} \frac{1}{‖ x_{j} - y_{i} ‖}) .

Метод збігається майже з усіх початкових положень, але може завершитися невдачею, якщо наближення виявляється в одній із точок вибірки. Алгоритм можна модифікувати так, що він збігатиметься для всіх початкових точокШаблон:Sfn.

Бозе, Магешварі і МорінШаблон:Sfn описали витонченішу процедуру оптимізації для пошуку оптимального приблизного розв'язку цієї задачі. Як показали Не, Парріло і СтармфілсШаблон:Sfn, задачу можна подати як задачу Шаблон:Нп.

Коен, Лі, Міллер і ПачокиШаблон:Sfn показали, як обчислити геометричний центр із довільною точністю за майже лінійний час.

Опис геометричного центра

Якщо точка y відмінна від усіх заданих точок вибірки x_j, то y є геометричним центром тоді й лише тоді, коли

0 = \sum_{j = 1}^{m} \frac{x_{j} - y}{‖ x_{j} - y ‖} .

Це еквівалентно

y = (\sum_{j = 1}^{m} \frac{x_{j}}{‖ x_{j} - y ‖}) / (\sum_{j = 1}^{m} \frac{1}{‖ x_{j} - y ‖}),

що тісно пов'язане з алгоритмом Вайсфельда.

У загальному випадку y є геометричним центром тоді й лише тоді, коли існують вектори u_j такі, що

0 = \sum_{j = 1}^{m} u_{j}

де для x _j ≠ y,

u_{j} = \frac{x_{j} - y}{‖ x_{j} - y ‖}

а для x _j = y,

‖ u_{j} ‖ \leq 1 .

Еквівалентне формулювання цієї умови

\sum_{1 \leq j \leq m, x_{j} \neq y} \frac{x_{j} - y}{‖ x_{j} - y ‖} \leq | {j ∣ 1 \leq j \leq m, x_{j} = y} | .

Узагальнення

Геометричний центр можна узагальнити з евклідових просторів до загальних ріманових многовидів (і навіть метричних просторів), використовуючи ту ж іде, що використовується для визначення Шаблон:Не перекладено на ріманових многовидахШаблон:Sfn. Нехай $M$ — ріманів многовид із функцією відстані $d (\cdot, \cdot)$ , нехай $w_{1}, \dots, w_{n}$ — $n$ ваг, сума яких 1, і нехай $x_{1}, \dots, x_{n}$ — $n$ спостережень з $M$ . Тоді ми визначаємо зважений геометричний центр $m$ (або зважене середнє Фреше) точок даних

m = \underset{x \in M}{a r g m i n} \sum_{i = 1}^{n} w_{i} d (x, x_{i})

.

Якщо всі ваги рівні, ми говоримо, що $m$ є геометричним центром.

Примітки

Шаблон:Reflist

Література

Шаблон:Refbegin

Шаблон:Refend

Шаблон:Середні значення

↑ Загальніша задача про k-медіану задає питання про положення k центрів, що мінімізують суму відстаней від кожної точки множини до найближчого центра.
↑ Шаблон:Harvnb;Шаблон:Harvnb. Опуклий випадок першим довів Шаблон:Не перекладено.
↑ Шаблон:Harvnb; Шаблон:Harvnb. Раніше Кокейн і Мельцак Шаблон:Harvnb довели, що точку Штейнера для 5 точок на площині не можна побудувати за допомогою циркуля та лінійки.

[1] Загальніша задача про k-медіану задає питання про положення k центрів, що мінімізують суму відстаней від кожної точки множини до найближчого центра.

[2] Шаблон:Harvnb;Шаблон:Harvnb. Опуклий випадок першим довів Шаблон:Не перекладено.

[3] Шаблон:Harvnb; Шаблон:Harvnb. Раніше Кокейн і Мельцак Шаблон:Harvnb довели, що точку Штейнера для 5 точок на площині не можна побудувати за допомогою циркуля та лінійки.

[1]

[2]

[3]