EMD

Вступ

Це реалізація віддаленості від Землі, як описано в [1]. EMD обчислює відстань між двома розподілами, які представлені сигнатурами. Сигнатури — це набори зважених функцій, які фіксують розподіли. Функції можуть бути будь-якого типу і в будь-якій кількості вимірів, і визначаються користувачем.

EMD визначається як мінімальний об’єм роботи, що необхідний для зміни однієї сигнатури в іншу. Поняття «робота» базується на встановленій самим користувачем відстані, що являє собою дистанцію між двома функціями. Розмір двох сигнатур може бути різним. Також сума ваги однієї сигнатури може відрізнятися від сума ваги іншої (частковий збіг). Через це EMD нормалізується меншою сумою.

Код реалізований у С, і базується на вирішенні транспортної проблеми, як описано в [2]

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

Використання

Для того, щоб використати цей код, виконайте наступні кроки:

1. Скачайте файли emd.h і emd.c (перевірте log of changes для останніх змін).

2. У emd.h, змініть рядок

3. typedef int feature_t;
   відобразіть тип даних об’єкта. Структури також можуть бути використані, наприклад typedef struct {
      int X,Y,Z;
   } feature_t;
   
   

4. Щоб обчислити EMD, наберіть:

5. float emd(signature_t *Signature1, signature_t *Signature2,

6.  float (*func)(feature_t *, feature_t *),

7.  flow_t *Flow, int *FlowSize);

де

Signature1, Signature2:

Вказівки на дві сигнатури, чию відстань ми хочемо обчислити.

Dist:

Вказівник на функцію основної відстані, тобто функцію, яка вимірює відстань між двома сигнатурами.

Flow:

(Необов’язково) Вказівник на вектор flow_t (визначений у emd.h) де отриманий потік буде збережений. Потік повинен мати n1+n2-1 елементи, де n1 і n2 є розмірами двох сигнатур відповідно. У NULL, потік не повертається.

FlowSize:

(Необов’язково) У випадку, коли Flow не NULL, FlowSize повинен вказувати на ціле число, в якому буде записано кількість елементів потоку (завжди менше або рівно n1+n2-1).

• 8. Скомпілюйте emd.c і приєднайте його до свого коду

Тип сигнатури signature_t визначається у emd.h as:

typedef struct

{
 int n;                /* Кількість текстів у дистрибутиві*/
 feature_t *Features;  /* Вказівка на вектор функції*/
 float *Weights;       /* Показник об’єму характеристик*/
} signature_t;

Тип даних фукнції feature_t визначається у emd.h і має бути змінений користувачем для відображення його типу функцій.

В особливих випадках, користувач може захотіти змінити деякі значення дефініцій у emd.h:

#define MAX_SIG_SIZE 100

Максимально допустима кількість ознак в сигнатурі.

#define MAX_ITERATIONS 100

Максимальна кількість ітерацій. Для звичайних проблем, 100 це більше, ніж достатня кількість.

#define INFINITY 1e20

INFINITY має бути набагато більшим ніж будь-яке інше значення в проблемі

#define EPSILON 1e-6

EPSILON визначає точність рішення.

ПРИКЛАДИ

1. example1.c
   У цьому прикладі функції знаходяться у трьохвимірному просторі, а основна відстань – Евклідова.
   Щоб спробувати цей приклад, вам потрібно модифікувати feature_t у emd.h щоб отримати:   typedef struct { int X,Y,Z; } feature_t;
2.  example2.c
   Тут, замість надання функції для обчислення основних відстаней, вони  подаються в заздалегідь визначеній матриці. Це робиться визначенням   feature_t як int (по бажанню), і встановленням функцій в кожній сигнатурі, що мають послідовні числа. Функція основної дистанції     використовує три числа як індекси для матриці визначених витрат.

Отриманий потік повертається з emd функції, передаючи в якості останніх параметрів вектор flow_t, і вказівку на int , де буде вказана фактична кількість елементів потоку.

Крім того, у цьому  прикладі сумарна вага двох сигнатур є різною. Перша сигнатура має загальну вагу 1, тоді як друга сигнатура має загальну вагу 0,9.