Каков правильный алгоритм для логарифмической кривой распределения между двумя точками?
https://stackoverflow.com/questions/604953
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я прочитал кучу руководств о правильном способе генерации логарифмического распределения весов 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).
Алгоритм хорошо аппроксимирует кривую между двумя точками, но имеет один недостаток.Минимальное значение является частным случаем, и его логарифм дает ноль.Это означает, что размер минимального значения будет меньше минимального размера.Я пробовал составлять числа, чтобы попытаться решить этот особый случай, но, похоже, у меня ничего не получается.В настоящее время я просто рассматриваю минимальное количество как особый случай и добавляю "or 1- к строке подсчета логов.
Есть ли более правильный алгоритм для рисования кривой между двумя точками?
Обновление от 3 марта:Если я не ошибаюсь, я беру логарифм подсчета, а затем включаю его в линейное уравнение.Чтобы описать частный случай другими словами, в y = lnx при x = 1, y = 0.Это то, что происходит при минимальном количестве.Но минимальное значение не может быть равно нулю, тег не использовался 0 раз.
Попробуйте код и подключите свои собственные номера для тестирования.Меня устраивает отношение к минимальному количеству как к особому случаю, у меня такое чувство, что это было бы проще, чем любое реальное решение этой проблемы.Я просто чувствую себя там должен быть решением этого и что кто-то, вероятно, уже придумал решение.
ОБНОВЛЕНИЕ от 6 апреля:Простой Google поиск выдает множество руководств, которые я прочитал, но это вероятно, это наиболее полный пример ступенчатых облаков тегов.
ОБНОВЛЕНИЕ от 28 апреля:В ответ на решение antti.huima:При построении графика кривая, создаваемая вашим алгоритмом, лежит ниже линии между двумя точками.Я пытался жонглировать цифрами, но, похоже, все еще не могу придумать способ перевернуть эту кривую на другую сторону линии.Я предполагаю, что если бы функция была изменена на какую-то форму логарифма вместо показателя степени, она делала бы именно то, что мне нужно.Это правильно?Если да, то кто-нибудь может объяснить, как этого добиться?
Решение
Благодаря помощи 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, мы получаем:
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
Другие советы
Давайте начнем с вашего сопоставления от зарегистрированного количества до размера.Это линейное отображение, о котором вы упоминали:
size
|
max |_____
| /
| /|
| / |
min |/ |
| |
/| |
0 /_|___|____
0 a
где min и max - это минимальные и максимальные значения размеры, и a=log(максимальное количество)-b.Строка имеет вид y=mx + c, где x=log(количество)-b
Из графика мы можем видеть, что градиент, m, равен (maxsize-minsize)/a.
Нам нужно x= 0 при y = minsize, поэтому log(минимальное количество)-b=0 -> b=log(минимальное количество)
Это оставляет нас со следующим python:
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 к списку подсчета перед выполнением min.То же самое касается того, чтобы убедиться, что максимальное количество всегда равно как минимум 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
что у вас есть, так это то, что у вас есть теги, количество которых варьируется от МИНИМАЛЬНОГО до МАКСИМАЛЬНОГО;проблему порога здесь можно проигнорировать, поскольку она сводится к установке каждого значения ниже порога на пороговое значение и только после этого принимает минимальное и максимальное значения.
Вы хотите сопоставить количество тегов с "весами", но "логарифмическим способом", что в основном означает (насколько я понимаю) следующее.Во-первых, теги с максимальным количеством получают вес max_weight (в вашем примере 1,75).:
weight(MAX) = max_weight
Во-вторых, теги с числом MIN получают вес min_weight (в вашем примере 0,75).:
weight(MIN) = min_weight
Наконец, он утверждает, что когда ваше количество уменьшается на 1, вес умножается на константу K < 1, что указывает на крутизну кривой:
weight(x) = weight(x + 1) * K
Решая это, мы получаем:
weight(x) = weight_max * (K ^ (MAX - x))
Обратите внимание, что при x = MAX показатель степени равен нулю, а множитель справа равен 1.
Теперь у нас есть дополнительное требование, что weight(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
т. е.
ln K = (ln weight_min - ln weight_max) / (MAX - MIN)
Правая сторона отрицательна по желанию, потому что K < 1.Тогда
K = exp((ln weight_min - ln weight_max) / (MAX - MIN))
Итак, теперь у вас есть формула для вычисления K.После этого вы просто подаете заявку на любое количество x между MIN и MAX:
weight(x) = max_weight * (K ^ (MAX - x))
И с вами покончено.
В логарифмическом масштабе вы просто строите логарифм чисел линейно (другими словами, представьте, что вы строите линейно, но сначала возьмите логарифм чисел, которые нужно построить).
Проблема с нулем не может быть решена аналитически - вы должны выбрать минимальный порядок величины для вашей шкалы, и, несмотря ни на что, вы никогда не сможете достичь нуля.Если вы хотите построить что-то с нулевым значением, ваш выбор - произвольно присвоить ему минимальный порядок величины шкалы или опустить его.
У меня нет точного ответа, но я думаю, вы хотите посмотреть линеаризацию экспоненциальных данных.Начните с вычисления уравнения прямой, проходящей через точки, и возьмите логарифм обеих сторон этого уравнения.
