Каков правильный алгоритм для логарифмической кривой распределения между двумя точками?

Question

Я прочитал кучу уроков о том, как правильно сгенерировать логарифмическое распределение весов tagcloud. Большинство из них группируют теги по шагам. Это кажется мне несколько глупым, поэтому я разработал свой собственный алгоритм, основанный на том, что я прочитал, чтобы он динамически распределял количество тегов по логартмической кривой между порогом и максимумом. Вот суть этого в Python:

from math import log
count = [1, 3, 5, 4, 7, 5, 10, 6]
def logdist(count, threshold=0, maxsize=1.75, minsize=.75):
    countdist = []
    # mincount is either the threshold or the minimum if it's over the threshold
    mincount = threshold<min(count) and min(count) or threshold
    maxcount = max(count)
    spread = maxcount - mincount
    # the slope of the line (rise over run) between (mincount, minsize) and ( maxcount, maxsize)
    delta = (maxsize - minsize) / float(spread)
    for c in count:
        logcount = log(c - (mincount - 1)) * (spread + 1) / log(spread + 1)
        size = delta * logcount - (delta - minsize)
        countdist.append({'count': c, 'size': round(size, 3)})
    return countdist

По сути, без логарифмического расчета отдельного счета, он будет генерировать прямую линию между точками (mincount, minsize) и (maxcount, maxsize).

Алгоритм хорошо аппроксимирует кривую между двумя точками, но имеет один недостаток. Mincount является особым случаем, и его логарифм дает ноль. Это означает, что размер mincount будет меньше, чем minsize. Я пытался придумать числа, чтобы попытаться раскрыть этот особый случай, но, похоже, не могу понять, что это правильно. В настоящее время я рассматриваю mincount как особый случай и добавляю "or 1" в строку logcount.

Есть ли более правильный алгоритм для рисования кривой между двумя точками?

Обновление 3 марта : Если я не ошибаюсь, я беру журнал счета и затем включаю его в линейное уравнение. Чтобы поместить описание частного случая другими словами, в y = lnx при x = 1, y = 0. Это то, что происходит на mincount. Но mincount не может быть нулем, тэг не использовался 0 раз.

Попробуйте проверить код и введите свои номера. Я прекрасно отношусь к mincount как к особому случаю, я чувствую, что это будет проще, чем какое-либо реальное решение этой проблемы. Я просто чувствую, что должно быть решением этого вопроса и что кто-то, вероятно, придумал решение.

ОБНОВЛЕНИЕ Апр 6 : простой поиск google приводит ко многим прочитанным мною учебникам, но этот , возможно, является наиболее полным примером ступенчатые облака тегов.

ОБНОВЛЕНИЕ 28 апреля : В ответ на решение antti.huima: при построении графика кривая, которую создает ваш алгоритм, лежит ниже линии между двумя точками. Я пытался совмещать числа вокруг, но все еще не могу найти способ перевернуть эту кривую на другую сторону линии. Я предполагаю, что если бы функция была изменена на некоторую форму логарифма вместо экспоненты, она бы сделала именно то, что мне нужно. Это верно? Если да, может кто-нибудь объяснить, как этого добиться?

Answer 1

Благодаря помощи antti.huima я переосмыслил то, что пытался сделать.

Взяв его метод решения задачи, я хочу уравнение, в котором логарифм минимального счета равен линейному уравнению между двумя точками.

weight(MIN) = ln(MIN-(MIN-1)) + min_weight
min_weight = ln(1) + min_weight

Хотя это дает мне хорошую отправную точку, мне нужно, чтобы она прошла через эту точку (MAX, max_weight). Потребуется постоянная:

weight(x) = ln(x-(MIN-1))/K + min_weight

Решая для К получим:

K = ln(MAX-(MIN-1))/(max_weight - min_weight)

Итак, чтобы поместить все это обратно в некоторый код Python:

from math import log
count = [1, 3, 5, 4, 7, 5, 10, 6]
def logdist(count, threshold=0, maxsize=1.75, minsize=.75):
    countdist = []
    # mincount is either the threshold or the minimum if it's over the threshold
    mincount = threshold<min(count) and min(count) or threshold
    maxcount = max(count)
    constant = log(maxcount - (mincount - 1)) / (maxsize - minsize)
    for c in count:
        size = log(c - (mincount - 1)) / constant + minsize
        countdist.append({'count': c, 'size': round(size, 3)})
    return countdist

Answer 2

у вас есть теги с количеством от MIN до MAX; пороговую проблему здесь можно игнорировать, поскольку она сводится к установке каждого счетчика ниже порогового значения на пороговое значение и принятию минимального и максимального только после этого.

Вы хотите отобразить количество тегов на «веса», но «логарифмически», что в основном означает (насколько я понимаю) следующее. Во-первых, теги с количеством MAX получают максимальный вес (в вашем примере 1,75):

weight(MAX) = max_weight

Во-вторых, теги с числом MIN получают min_weight weight (в вашем примере 0,75):

weight(MIN) = min_weight

Наконец, считается, что когда ваш счет уменьшается на 1, вес умножается на постоянную K <1, что указывает на крутизну кривой: </p>

weight(x) = weight(x + 1) * K

Решив это, мы получим:

weight(x) = weight_max * (K ^ (MAX - x))

Обратите внимание, что при x = MAX показатель степени равен нулю, а мультипликатор справа становится 1.

Теперь у нас есть дополнительное требование, чтобы вес (MIN) = min_weight, и мы можем решить:

weight_min = weight_max * (K ^ (MAX - MIN))

из которых мы получаем

K ^ (MAX - MIN) = weight_min / weight_max

и логарифм с обеих сторон

(MAX - MIN) ln K = ln weight_min - ln weight_max

* * +1025 т.е. * * 1 026

ln K = (ln weight_min - ln weight_max) / (MAX - MIN)

Правая часть отрицательна по желанию, потому что K <1. Тогда </p>

K = exp((ln weight_min - ln weight_max) / (MAX - MIN))

Итак, теперь у вас есть формула для расчета K. После этого вы просто подаете заявку на любой отсчет x между MIN и MAX:

weight(x) = max_weight * (K ^ (MAX - x))

И все готово.

Answer 3

Давайте начнем с вашего сопоставления от зарегистрированного количества до размера. Это линейное отображение, которое вы упомянули:

   size
    |
max |_____
    |   /
    |  /|
    | / |
min |/  |
    |   |
   /|   |
0 /_|___|____
    0   a

, где min и max - это минимальные и максимальные размеры , а a = log (maxcount) -b. Линия имеет вид y = mx + c, где x = log (count) -b

Из графика видно, что градиент m равен (maxsize-minsize) /a.

Нам нужно x = 0 при y = минимальном размере, поэтому log (mincount) -b = 0 -> b = log (mincount)

Это оставляет нам следующий питон:

mincount = min(count)
maxcount = max(count)
xoffset = log(mincount)
gradient = (maxsize-minsize)/(log(maxcount)-log(mincount))
for c in count:
    x = log(c)-xoffset
    size = gradient * x + minsize

Если вы хотите убедиться, что минимальное число всегда равно 1, замените первую строку на:

mincount = min(count+[1])

, который добавляет 1 к списку счетчиков перед выполнением мин. То же самое относится и к тому, чтобы maxcount всегда был как минимум 1. Таким образом, ваш окончательный код, приведенный выше:

from math import log
count = [1, 3, 5, 4, 7, 5, 10, 6]
def logdist(count, maxsize=1.75, minsize=.75):
    countdist = []
    mincount = min(count+[1])
    maxcount = max(count+[1])
    xoffset = log(mincount)
    gradient = (maxsize-minsize)/(log(maxcount)-log(mincount))
    for c in count:
        x = log(c)-xoffset
        size = gradient * x + minsize
        countdist.append({'count': c, 'size': round(size, 3)})
    return countdist

Answer 4

У меня нет точного ответа, но я думаю, что вы хотите посмотреть Линеаризацию экспоненциальных данных. Начните с вычисления уравнения линии, проходящей через точки, и возьмите логарифм обеих сторон этого уравнения.

Answer 5

В логарифмическом масштабе вы просто строите журнал чисел линейно (другими словами, представьте, что вы строите график линейно, но сначала берете журнал чисел, которые должны быть нанесены).

Нулевая проблема не может быть решена аналитически - вы должны выбрать минимальный порядок величины для вашей шкалы, и независимо от того, что вы никогда не достигнете нуля. Если вы хотите построить что-то в нуле, вы можете произвольно задать минимальный порядок масштаба или опустить его.