Doplňování posloupností

Algoritmy Matematické Doplňování posloupností

Vstupem do programu je soubor obsahující na každém řádku číselnou posloupnost. Program se pokusí uhádnout její pokračovaní a výstup uloží ve stejném formátu do souboru.

S volbou --debug vypisuje program do konzole posloupnost, její predikci a získané koeficienty spolu s celkovou chybou odhadu.

Algoritmus

Jako model se používá lineární regrese, vstupem jsou pouze předchozí členy posloupnosti. N-tý člen se predikuje na základě vzorce: a[n] = [1 a[n-1] ... a[n-k]] * w, kde w je vektor vah.

Hledání modelu začíná vztahem a[n] = w[0] + w[1]*a[n-1] a postupuje ke složitějším modelům, pokud stále můžeme získat lepší predikci.

Proč lineární model funguje?

V případě algebraických posloupností bývají následné členy lineární transformací členů předchozích. To platí dokonce i v případě nelineárních vztahů. Každý člen pak v sobě obsahuje "ozvěnu" informace získanou z předchozích členů. Výhodou lineárního modelu je, že dobře funguje s nízkou informační kapacitou i pro složitější vzory.

Příklad: pro posloupnost a[n] = n*n platí,

a[n+1] = (n+1)^2 = n*n + 2n + 1
a[n-1] = (n-1)^2 = n*n - 2n + 1

a[n+1] = 2*a[n] - a[n-1] + 2

Obvyklý postup by dále pokračoval hledáním modelů s polynomiálním nebo radiálním jádrem, což ovšem vyžaduje mnohem větší množství vstupních dat.

Požadavky

  • Python >= 3.5

Použití

python predict.py -h
usage: predict.py [-h] [--debug] input output

positional arguments:
  input       input file
  output      output file

optional arguments:
  -h, --help  show this help message and exit
  --debug     print debug info

Spuštění na přiloženém příkladu s debug výpisem

python predict.py in.txt out.txt --debug

Galerie

Program byl vytvořen v roce 2016.

 

Stáhnout

Staženo 4x (4.72 kB)
Aplikace je včetně zdrojových kódů

 

  Aktivity (2)

Program pro vás napsal coells
Avatar

Jak se ti líbí článek?
Celkem (3 hlasů) :
55555


 


Miniatura
Všechny články v sekci
Matematické algoritmy

 

 

Komentáře

Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zatím nikdo nevložil komentář - buď první!