Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Аппроксимация степенной функцией

175 views
Skip to first unread message

Kalachihin Vladimir

unread,
Mar 13, 2012, 7:20:00 AM3/13/12
to
Приветствую тебя, All!

Как-то я сходу не нашёл, как сделать:

Имеются экспериментальные данные, имеющие степенное (aka Парето) распределение.
Hужно найти апроксимирующую функцию, причём степенную (т.е., линеаризацию не
применять)
Как?



Калачихин Владимир.

Интересно, тут вообще кто-нибудь есть?

Nickita A Startcev

unread,
Mar 13, 2012, 2:48:42 PM3/13/12
to
Привет, Kalachihin !


13 Mar 12 , 15:20 Kalachihin Vladimir писал к All:

KV> Как-то я сходу не нашёл, как сделать:

KV> Имеются экспериментальные данные, имеющие степенное (aka Парето)
KV> распределение. Hужно найти апроксимирующую функцию, причём степенную
KV> (т.е., линеаризацию не применять) Как?

Прологарифмировать данные и свести задачу к линейной?

y = a x^b
log(y) = a + b * log(x)
очевидно что второе выражение линейно относительно log(x) и log(y)

. С уважением, Hикита.
icq:240059686, lj-user:nicka_startcev
... если у радиста инкрементировать первую букву..

Evgenij Litvjak

unread,
Mar 13, 2012, 1:16:34 PM3/13/12
to
Здpавствуй, Kalachihin!

Вторник 13 Марта 2012 15:20, ты писал(а) All, в сообщении по ссылке
area://ru.algorithms?msgid=2:5095/1.39+4f5f668e:

KV> Как-то я сходу не нашёл, как сделать:

KV> Имеются экспериментальные данные, имеющие степенное (aka Парето)
KV> распределение. Hужно найти апроксимирующую функцию, причём степенную
KV> (т.е., линеаризацию не применять) Как?

Hе разбираюсь в предмете. Всё чем могу помочь - попробывать погуглить (:
Запрос: "Аппроксимирующая функция степени -линеаризация"

www.efmnp.ru/soder_01.php
"Метод наименьших квадратов
Задачи по определению значений параметров аппроксимирующих функций возникают
при сглаживании экспериментальных зависимостей. ..."

Запрос: Аппроксимирующая функция степени Парето -линеаризация -линейная"

http://www.mathnet.ru/php/getFT.phtml?jrnid=zvmmf&paperid=4351&what=fullt&opti
on_lang=rus
"В. H. Hефедов
Об аппроксимации множества Парето
Исследуются некоторые подходы к аппроксимации множества Парето конечным
множеством элементов. Предлагаются простые практически реализуемые способы
согласования величин погрешностей с параметрами регуляризации, обеспечивающие
сходимость аппроксимирующего множества к множеству Парето в метрике
Хаусдорфа."

KV> Интересно, тут вообще кто-нибудь есть?
Hе знаю, я в фидо недавно, твоё сообщение первое, что я читаю в этой эхе.
С уважением - Evgenij

Kalachihin Vladimir

unread,
Mar 14, 2012, 3:41:06 AM3/14/12
to
Приветствую тебя, Nickita!

Replying to a message of Nickita A Startcev to Kalachihin Vladimir:

NAS> Прологарифмировать данные и свести задачу к линейной?

Я же сказал - без линеаризации.

Меня, натурально, интересует не сама кривая, а отклонения от неё. А при
линеаризации отклонения нивелируются.
Hаверно...
Hадо посмотреть.



Калачихин Владимир.

Kalachihin Vladimir

unread,
Mar 14, 2012, 3:57:52 AM3/14/12
to
Приветствую тебя, Evgenij!

Replying to a message of Evgenij Litvjak to Kalachihin Vladimir:

EL> Hе разбираюсь в предмете. Всё чем могу помочь - попробывать погуглить

О! У тебя другой Google!
Вот этого я не видел:

EL> http://www.mathnet.ru/php/getFT.phtml?jrnid=zvmmf&paperid=4351&what=f
EL> ullt&opti on_lang=rus "В. H. Hефедов Об аппроксимации множества
EL> Парето

Здорово! Правда, я, в общем, ничего не понял...

Другое дело, что "множества Парето" - это совсем из другой оперы.


Калачихин Владимир.

Nickita A Startcev

unread,
Mar 14, 2012, 2:22:32 PM3/14/12
to
Привет, Kalachihin !


14 Mar 12 , 11:41 Kalachihin Vladimir писал к Nickita A Startcev:


NAS>> Прологарифмировать данные и свести задачу к линейной?

KV> Я же сказал - без линеаризации.

KV> Меня, натурально, интересует не сама кривая, а отклонения от неё. А
KV> при линеаризации отклонения нивелируются. Hаверно... Hадо посмотреть.

Линеаризировать, найти лучшее приближение, посчитать отклонение от приближения,
пересчитать обратно.
хотя, не. Пересчитывать даже не надо, и так вылезут погрешности в
коэффицентиках.

. С уважением, Hикита.
icq:240059686, lj-user:nicka_startcev
... Сектка фидомасонов

Ivan Shmakov

unread,
Mar 15, 2012, 12:51:02 AM3/15/12
to
>>>>> "KV" == Kalachihin Vladimir writes:

KV> Как-то я сходу не нашёл, как сделать:

KV> Имеются экспериментальные данные, имеющие степенное (aka Парето)
KV> распределение. Hужно найти апроксимирующую функцию, причём
KV> степенную (т. е., линеаризацию не применять)

Функцию, аппроксимирующую /распределение/?

KV> Как?

Алгоритм Левенберга--Марквардта?

Среди реализаций (см., e. g., [1]) особо отмечу Gnuplot [2].

[1] http://en.wikipedia.org/wiki/Levenberg-Marquardt#Implementations
[2] http://gnuplot.info/

KV> Интересно, тут вообще кто-нибудь есть?

ет.

--
FSF associate member #7257

Kalachihin Vladimir

unread,
Mar 15, 2012, 6:03:08 AM3/15/12
to
Приветствую тебя, Ivan!

Replying to a message of Ivan Shmakov to Kalachihin Vladimir:

IS> Функцию, аппроксимирующую /распределение/?

aka регрессионную модель. А что?

KV>> Как?

IS> Алгоритм Левенберга--Марквардта?

Эээээ... Hасколько я понял, во-первых, апроксимирующая функция уже должна
быть, а во-вторых, нужна эталонная выборка.

Hу и в третьих, мне пофигу, насколько точная получилась аппроксимация.

Т.е., алгоритм Левенберга - Марквардта не при чем. Или я что-то не понял?




Калачихин Владимир.

Ivan Shmakov

unread,
Mar 15, 2012, 11:47:08 PM3/15/12
to
>>>>> "KV" == Kalachihin Vladimir writes:

[...]

IS> Алгоритм Левенберга--Марквардта?

KV> Эээээ... Hасколько я понял, во-первых, апроксимирующая функция уже
KV> должна быть,

Под аппроксимацией всегда понимал восстановление параметров
функции, заданной в общем виде, по заданной выборке. E. g.,
даны функция f (x) = k x + b и выборка (1, 2), (2, 5), (3, 8).
Получаем аппроксимирующую функцию f (x) = 3 x - 1.

Алгоритм Левенберга--Марквардта позволяет выполнить
аппроксимацию в случае, если функция нелинейна по параметрам.
IOW, в то время как линейный МHК позволяет аппроксимировать
функциями вида (1), данный алгоритм допускает более общий вид
(2).

(1) f (x) = \sum _i {a _i h _i (x)} ;

(2) f (x) = \sum _i {g _i (a _i) h _i (x)} .

Впрочем, может требоваться подбор начальных значений для a _i, в
особенности если g _i имеют особые точки.

KV> а во-вторых, нужна эталонная выборка.

?

KV> Hу и в третьих, мне пофигу, насколько точная получилась
KV> аппроксимация.

I. e., функция f (x) = 2 x + 1 для выборки выше была бы
допустима?

KV> Т. е., алгоритм Левенберга - Марквардта не при чем. Или я что-то
KV> не понял?

AIUI, речь идет об аппроксимирующей функции вида (2) с
параметрами m, \alpha? Пока не вижу проблемы.

f (x) = \begin {cases}
\alpha \frac {m ^\alpha} {x ^{\alpha + 1}},
x > m,
0, x < m
\end {cases}

Пример выборки?

Kalachihin Vladimir

unread,
Mar 17, 2012, 3:39:50 AM3/17/12
to
����������� ����, Ivan!

Replying to a message of Ivan Shmakov to Kalachihin Vladimir:

IS> ��� �������������� ������ ������� �������������� ����������
IS> �������, �������� � ����� ����, �� �������� �������.

Ok.

IS> (2) f (x) = \sum _i {g _i (a _i) h _i (x)} .

IS> I. e., ������� f (x) = 2 x + 1 ��� ������� ���� ���� ��
IS> ���������?

H� �� ������� �ӣ �������� ������ ���������...

IS> AIUI, ���� ���� �� ���������������� ������� ���� (2) �
IS> ����������� m, \alpha? ���� �� ���� ��������.

IS> f (x) = \begin {cases}
IS> \alpha \frac {m ^\alpha} {x ^{\alpha + 1}},
IS> x > m,
IS> 0, x < m
IS> \end {cases}

��, ���.

IS> ������ �������?

� ���� ������.... ������� ����� �������� ������ ��������, � ����� �������
��������� ��������� ����� �����.



��������� ��������.

Ivan Shmakov

unread,
Mar 19, 2012, 12:20:43 PM3/19/12
to
>>>>> "KV" == Kalachihin Vladimir writes:
>>>>> Replying to a message of Ivan Shmakov to Kalachihin Vladimir:

[...]

KV> Hу и в третьих, мне пофигу, насколько точная получилась
KV> аппроксимация.

IS> I. e., функция f (x) = 2 x + 1 для выборки выше была бы допустима?

KV> Hу не следует всё понимать совсем буквально...

IOW, речь все же идет о минимизации ошибки.

[...]

IS> Пример выборки?

KV> С этим сложно.... Выборка имеет примерно тысячу значений,

И что в этом сложного? С учетом наличия, e. g.,
http://pastebin.com/ и подобных.

KV> и таких выборок ожидается несколько сотен тысяч.

Думаю, я могу провести <<контрольную обработку>> одной выборки
(и привести результаты, разумеется), если с использованием
Gnuplot возникают сложности.

Kalachihin Vladimir

unread,
Mar 19, 2012, 2:34:30 PM3/19/12
to
Приветствую тебя, Ivan!

Replying to a message of Ivan Shmakov to Kalachihin Vladimir:

IS> Думаю, я могу провести <<контрольную обработку>> одной выборки
IS> (и привести результаты, разумеется), если с использованием
IS> Gnuplot возникают сложности.

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



Калачихин Владимир.

Kalachihin Vladimir

unread,
Mar 20, 2012, 11:13:38 AM3/20/12
to
Приветствую тебя, Ivan!

Replying to a message of Ivan Shmakov to Kalachihin Vladimir:

IS> Думаю, я могу провести <<контрольную обработку>> одной выборки
IS> (и привести результаты, разумеется)

Спасибо, однако я пока сосредоточусь на подходе с линеаризацией.

Hеожиданно, после логарифмирования на графике обнаружился эффект, обещающий
очень интересный результат :-)



Калачихин Владимир.

Nickita A Startcev

unread,
Mar 20, 2012, 7:44:58 PM3/20/12
to
Привет, Kalachihin !


20 Mar 12 , 19:13 Kalachihin Vladimir писал к Ivan Shmakov:

IS>> Думаю, я могу провести <<контрольную обработку>> одной выборки
IS>> (и привести результаты, разумеется)

KV> Спасибо, однако я пока сосредоточусь на подходе с линеаризацией.

KV> Hеожиданно, после логарифмирования на графике обнаружился эффект,
KV> обещающий очень интересный результат :-)

что, эксперимент распался на несколько разных явных линий? :)

. С уважением, Hикита.
icq:240059686, lj-user:nicka_startcev
... Hеиллюзорная Черная машина localhost'а

Kalachihin Vladimir

unread,
Mar 21, 2012, 7:00:32 AM3/21/12
to
Приветствую тебя, Nickita!

Replying to a message of Nickita A Startcev to Kalachihin Vladimir:

NAS> что, эксперимент распался на несколько разных явных линий? :)

Hет, целью был анализ отклонений от аппроксимации, и обнаружилось ранее
упущенное отклонение, которое, вроде бы, имеет объяснение в реальном мире, к
тому же - полезное.

А линия там одна просто по построению :-)



Калачихин Владимир.

Kalachihin Vladimir

unread,
Apr 7, 2012, 4:22:44 PM4/7/12
to
Приветствую тебя, Kalachihin!

Replying to a message of Kalachihin Vladimir to Nickita A Startcev:

KV> А линия там одна просто по построению :-)

"Читайте доки, они рулез".
Читал, узнал много интересного. Многие считают, что в том экспеперименте аж три
линии. Я им не верю.
Правда, те, кто считают, что одна - утверждают, что не экспонента...

Hо это фигня. Чтоб subj не менять - кто-нибудь знает готовую быструю программу,
случайным образом переставляющую слова в тексте? Hатурально, консольную, под
Lin. Желательно воспринимающую текст размером больше оперативной памяти.



Калачихин Владимир.

Nickita A Startcev

unread,
Apr 8, 2012, 6:00:58 AM4/8/12
to
Привет, Kalachihin !


08 Apr 12 , 00:22 Kalachihin Vladimir писал к Kalachihin Vladimir:

KV> Hо это фигня. Чтоб subj не менять - кто-нибудь знает готовую быструю
KV> программу, случайным образом переставляющую слова в тексте?
KV> Hатурально, консольную, под Lin. Желательно воспринимающую текст
KV> размером больше оперативной памяти.

Если устроит 'перестановка в пределах абзаца', то на баше пишется строчек в
двадцать

Функция в цикле читает строки и передает их на вход другой функции, которая в
зависимости от рандома клеит строки так или иначе.
(вариант - форкает процессы, которые выводят результат с случайными
задержками).


. С уважением, Hикита.
icq:240059686, lj-user:nicka_startcev
... Шапка + Еда = дерево

Kalachihin Vladimir

unread,
Apr 8, 2012, 8:39:14 AM4/8/12
to
Приветствую тебя, Nickita!

Replying to a message of Nickita A Startcev to Kalachihin Vladimir:

NAS> Если устроит 'перестановка в пределах абзаца', то на баше пишется
NAS> строчек в двадцать

В пределах абзаца на PHP пришется строчек в семь. Hо в пределах абзаца не
устроит.

Я написал, конечно, на PHP + MySQL, соответственно, размер файла не критичен,
но медленно работает... 82 000 слов переставляются за 7 сек. на ноутбуке с
целероном. А я хочу - за одну. Hу, за две.
С другой стороны - быстрей будет только если весь текст пихать в память.



Калачихин Владимир.

Valentin Davydov

unread,
May 29, 2012, 7:55:33 AM5/29/12
to
> From: Kalachihin Vladimir
> <Kalachihi...@p39.f1.n5095.z2.fidonet.org>
> Date: Sun, 08 Apr 2012 16:39:14 +0400
>
> NAS> Если устроит 'перестановка в пределах абзаца', то на баше пишется
> NAS> строчек в двадцать
>
>В пределах абзаца на PHP пришется строчек в семь. Hо в пределах абзаца не
>устроит.
>
>Я написал, конечно, на PHP + MySQL, соответственно, размер файла не критичен,
>но медленно работает... 82 000 слов переставляются за 7 сек. на ноутбуке с
>целероном. А я хочу - за одну. Hу, за две.

Hу, 7 секунд или 2 - разница небольшая. Может, если взять заду банных
побыстрее, то и получится:

$ cat words.sql
create table t(w);
create index i on t(w);
.import /usr/share/dict/words t
select * from t order by random();
$ rm -f words.db
$ time sqlite3 words.db < words.sql | wc
235882 235882 2493082

real 0m4.225s
user 0m3.988s
sys 0m0.109s

Вал. Дав.

Valentin Davydov

unread,
May 29, 2012, 8:02:35 AM5/29/12
to
> From: Valentin Davydov <s...@m.davydov.spb.su>
> Date: Tue, 29 May 2012 11:55:33 +0000 (UTC)
>>
>> NAS> ���� ������� '������������ � �������� ������', �� �� ���� �������
>> NAS> ������� � ��������
>>
>>� �������� ������ �� PHP �������� ������� � ����. H� � �������� ������ ��
>>�������.
>>
>>� �������, �������, �� PHP + MySQL, ��������������, ������ ����� �� ��������,
>>�� �������� ��������... 82 000 ���� �������������� �� 7 ���. �� �������� �
>>���������. � � ���� - �� ����. H�, �� ���.
>
>H�, 7 ������ ��� 2 - ������� ���������. �����, ���� ����� ���� ������
>���������, �� � ���������:
>
>$ cat words.sql
>create table t(w);
>create index i on t(w);
>.import /usr/share/dict/words t
>select * from t order by random();
>$ rm -f words.db
>$ time sqlite3 words.db < words.sql | wc
> 235882 235882 2493082
>
>real 0m4.225s
>user 0m3.988s
>sys 0m0.109s

� ��� ������� �ݣ ����� ����� �������.

���. ���.

Kalachihin Vladimir

unread,
Jun 1, 2012, 5:32:12 AM6/1/12
to
Приветствую тебя, Valentin!

Replying to a message of Valentin Davydov to Valentin Davydov:

VD> А без индекса ещё почти вдвое быстрее.

Hу дык всё павно в памяти. Я MySQL'ю сказал - в памяти, оно тоже быстро стало.
Только память скоро кончилась :-(




Калачихин Владимир.

Valentin Davydov

unread,
Jun 4, 2012, 1:27:54 AM6/4/12
to
> From: Kalachihin Vladimir <Kalachihi...@p39.f1.n5095.z2.fidonet.org>
> Date: Fri, 01 Jun 2012 13:32:12 +0400
>
> VD> А без индекса ещё почти вдвое быстрее.
>
>Hу дык всё павно в памяти. Я MySQL'ю сказал - в памяти, оно тоже быстро стало.
>Только память скоро кончилась :-(

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

Вал. Дав.

Kalachihin Vladimir

unread,
Jun 7, 2012, 4:25:34 AM6/7/12
to
Приветствую тебя, Valentin!

Replying to a message of Valentin Davydov to Kalachihin Vladimir:

VD> Значит, надо попробовать наоборот - запихивать в базу случайным
VD> образом

Хммм... Запихивать случайным образом - это сразу присваивать случайный ключ?

Выигрыша в смысле скорости чтения, натурально, не будет, но минус одна
операция...



Калачихин Владимир.

Valentin Davydov

unread,
Jun 9, 2012, 7:13:48 AM6/9/12
to
> From: Kalachihin Vladimir <Kalachihi...@p39.f1.n5095.z2.fidonet.org>
> Date: Thu, 07 Jun 2012 12:25:34 +0400
>
> VD> Значит, надо попробовать наоборот - запихивать в базу случайным
> VD> образом
>
>Хммм... Запихивать случайным образом - это сразу присваивать случайный ключ?

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

>Выигрыша в смысле скорости чтения, натурально, не будет, но минус одна
>операция...

Выигрыш в скорости чтения будет: сплошное подряд чтение с диска на порядок
быстрее рандомного.

Вал. Дав.

Kalachihin Vladimir

unread,
Jun 13, 2012, 9:18:24 AM6/13/12
to
����������� ����, Valentin!

Replying to a message of Valentin Davydov to Kalachihin Vladimir:

VD> ������� � �������� ������ �����: �������� ������ ������ � ����� ��
VD> ������� ������� ����������.

H� ����, ��� �������� MySQL, �� �ӣ ��������� ��������:

������� � ������ ����:

ID INT, �������� CHAR

ID �� �������� ������� ���ޣ�, � ���, �������, �� �����, �������� �� ��
����������.

��� ���, ���� ������ � ���� � ID ������ (����� ��������), ����� ����������
MySQL ��������� ID ��������� �������� � ��������� ��������� (���� ������), �
����� ������ � ������� ID (���� ������) - �� ��� ������� �� ����� ��� �� 10%,
��� ���� ������ �� ��������� ID, � ����� ������ � ������� ID.

���� ������������, ��� ��� ���������������� MySQL ���-�� ����� ��������
�������, ��� ��� ����������� ������ ���������� ����� ������. H� �� �����
��������� ��� ����� �� ����������� - ���������� ���������, ��� ������� �������
�� ���������. H�������, ���������� ������� ��� ID ����� ������� �ݣ ���������
�� 10 ���������.



��������� ��������.

Valentin Davydov

unread,
Jun 14, 2012, 5:15:58 AM6/14/12
to
> From: Kalachihin Vladimir <Kalachihi...@p39.f1.n5095.z2.fidonet.org>
> Date: Wed, 13 Jun 2012 17:18:24 +0400
>
> VD> ������� � �������� ������ �����: �������� ������ ������ � ����� ��
> VD> ������� ������� ����������.
>
>H� ����, ��� �������� MySQL, �� �ӣ ��������� ��������:
>
>������� � ������ ����:
>
>ID INT, �������� CHAR
>
>ID �� �������� ������� ���ޣ�, � ���, �������, �� �����, �������� �� ��
>����������.
>
>��� ���, ���� ������ � ���� � ID ������ (����� ��������), ����� ����������
>MySQL ��������� ID ��������� �������� � ��������� ��������� (���� ������), �
>����� ������ � ������� ID (���� ������) - �� ��� ������� �� ����� ��� �� 10%,
>��� ���� ������ �� ��������� ID, � ����� ������ � ������� ID.
>
>���� ������������, ��� ��� ���������������� MySQL ���-�� ����� ��������
>�������, ��� ��� ����������� ������ ���������� ����� ������. H� �� �����
>��������� ��� ����� �� ����������� - ���������� ���������, ��� ������� �������
>�� ���������. H�������, ���������� ������� ��� ID ����� ������� �ݣ ���������
>�� 10 ���������.

� �� �ӣ-���� ������ ������� ������, ����� � ������ �� �����. � �� sqlite
�������� - ���� ���� �������, ��� ��������� _������_ ���������� �� �������
��������� ������ ������, ��� ������ ������ ��������� ������� � ���, � �������
�������� ����������� �� ����� (���, � �����, �������). ��� ���������, �������
������.

���. ���.

Kalachihin Vladimir

unread,
Jun 15, 2012, 8:09:14 AM6/15/12
to
Приветствую тебя, Valentin!

Replying to a message of Valentin Davydov to Kalachihin Vladimir:

VD> А ты всё-таки возьми столько данных, чтобы в память не лезло.

Да там фигня какая-то... В общем, до какого-то момента временные таблицы в
MySQL у меня работали нормально - всё быстро записывалось-читалось, и как оно
было организовано, меня не волновало. Hо после обновления Ubuntu наступил абзац
- запись в таблицу стала происходить в сотни раз медленней. Т.е., вместо секунд
- около 40 минут. Пришлось сказать ENGINE MEMORY.

Что где сломалось - непонятно :-(




Калачихин Владимир.

0 new messages