Задача такова:

1. Есть дискретная случайная переменная x \in X

2. Есть функция similarity x,y \in X : I(x; y) (mutual information)

Нужно построить бинарное дерево, объединяя наиболее близкие значения x.

При этом очень желательно использовать свойства I(x; y), иначе будет медленно -- O(|X|^5).

 

Собственно, алгоритм известен и довольно прост, но не хотелось бы тратить время на реализацию, если таковая уже имеется.

Кому-нибудь попадалось? Желательно на Java.

 

PS. про гугл слышал.

А можно для тупых пояснить синтаксис деклараций?

Особенно 2

Ну и идею алгоритма на пальцах... :shy:

Действительно, не очень внятно получилось.

Есть две переменные x & y из домена X

 

Алгоритм прост:

- каждое значение x помещается в отдельную корзину,

- выбираем две самые "похожие" корзины (после объединения которых I(x';y') максимальна, x', y' \in X' (домен с объединенными корзинами)) и объединяем.

- Повторяем пока не не останется одна корзина (корень дерева).

 

Есть некоторые тонкости, чтобы не вычислять I(x;y) каждый раз с нуля.

Тут не ясно как считать расстояние между корзинами где элементов больше 1го.

Приходит в голову несколько возможностей:

1) Для каждой корзины выбирается "представитель" из существующих элементов и расстояние между корзинами считается как расстояние между их "представителями".

2) Для каждой корзины вычисляется "представитель" (например, если элементы точки, можно вычислить центр тяжести). Расстояние считается между "представителями".

3) Расстояние между корзинами вычисляется на основе суперпозиции расстояний между элементами (например минимум расстояний между элементами корзин)

 

Ну, вроде как понятно, что надо сначала вычислить все расстояния между элементами.

Далее всё зависит от способа вычисления расстояний. Наименее трудоёмкий естественно 1 вариант.

 

P.S. Наткнулся тут на обсуждение в RSDN-е: http://rsdn.ru/Forum/Message.aspx?mid=2793611&only=1 вроде по теме?

Оригинальное описание алгоритма предлагает объединять элементы корзины в один (т.е. изменять фактически домен), это разумно, т.к. элементы домена слова, части речи, и т.п.

Собственно, с самим алгоритмом проблем нет, просто хотелос найти готовую реализацию и не тратить лишее время.

 

PS. Проблема по вашей ссылке не совсем близкая: там расстояние фиксировано, а тут оно (изменение mutual information) будет меняться после каждой итерации.