Category: цветы

Category was added automatically. Read all entries about "цветы".

wall

Верхний пост

Всем привет.

Я мало френжу, простите.
У меня есть привычка читать всю ленту и ввязываться в дискуссии, из-за этого приходится держать количество друзей (особенно, активно пишуших друзей) в разумных пределах.

Я не пишу под замок. Сейчас "под глазиком" лежит n штук недописанных постов, под замком один пост с оффлайновыми контактами. И может быть ещё что-то случайное из давней древности.

Если хочется сказать что-то не по теме, это можно сделать тут.
Если что, писать можно на толстый-крокодил@yandex.ru -- как название журнала, но не подчёркивание а дефис.
wall

Ж

Год назад писал про R-деревья. Там, помимо пересказа общеизвестного, содержалось оригинальное исследование, как сказали бы в википедии. Предположение о том, что R-деревья можно обобщить на произвольное метрическое пространство, не обязательно чтобы была система координат. В качестве примера там приводились слова с расстоянием Левенштейна в качестве метрики.

Ну, в общем, всё оказалось несколько сложнее. Не выходит что-то каменный цветок.

Есть такая штука -- индекс Жаккарда (Jaccard). Это мера похожести двух конечных множеств, считается так:



Т.е. количество общих элементов поделить на количество элементов в них всего. Для одного и того же множества индекс равен 1, для не пересекающихся 0, для остальных где-то между. Для чистоты нужно ещё дооопределить .

Можно, кстати, перетащить это на измеримые множества точек прямой/плоскости/и т.п., если брать не мощность, а меру. Уж не знаю, будет ли какой-нибудь интересный смысл.

Интересно, что d(A,B) = 1 - J(A, B) это честное расстояние.
  • очевидно, что d(a,a) = 0

  • очевидно, что d(a, b) > 0, если a != b

  • очевидно, что d(a, b) = d(b, a)

  • выполняется правило треугольника, хотя это и не очевидно. Можно доказать, выписав все конституенты для трёх множеств, всё умножить, сложить и вычесть. После этого останутся только положительные члены. Несложно, но ужасно муторно если делать руками, зато довольно легко автоматизируется. Более вменяемого доказательства я не знаю :(

Посмотрим, что за пространство у нас получилось. Напомню, точки -- элементы пространства -- конечные множества.
  • максимальное возможное расстояние -- 1

  • точка "пустое множество" находится от всех других точек на расстоянии 1

  • рассмотрим одноэлементное множество {a}. Ближе всего к нему, на расстоянии 1/2 лежат множества вида {a, b} для любых возможных b. Подальше, на расстоянии 2/3 -- все множества вида {a, b, c}. Потом 3/4 и т.п.

В общем, занятное пространство.

Collapse )

Но это только присказка. С двумя точками ситуация понятная. Сказка начинается, когда у нас n точек и нужно построить вокруг них не слишком большой шарик. А зачем нам это? А это шаг в построении R-дерева: разбиваем разросшийся узел и строим из него два маленьких. Побившись полночи головой об пол я так и не придумал, как найти шарику центр. Ну то есть можно добавляя по одному перемещать центр, стараясь угодить новому пришедшему, но там каждый раз случайный выбор -- что именно из него выбрать, чтобы пододвинуть к нему центр, с точки зрения метрики разницы нет. И что-то никаких оценок, почему такие выборы не будут слишком плохими слишком часто не придумывается.