Lab2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Szybka transformata Fouriera\n",
    "\n",
    "### Źródła\n",
    "\n",
    "Najlepszym źródłem, jakie znalazłem jest to: https://jakevdp.github.io/blog/2013/08/28/understanding-the-fft/\n",
    "W fajny sposób tłumaczy dyskretną transformatę Fouriera i sposób, w jaki zmniejsza się jej złożoność z O(n^2) do O(n*log(n)). Na egzaminie wymagany jset przykład 8-punktowy -- opisany jest [tutaj](http://sip.cua.edu/res/docs/courses/ee515/chapter08/ch8-2.pdf), choć slajdy są tyleż brzydkie, co mało czytelne.  \n",
    "\n",
    "Polska Wikipedia nie posiada fajnych artykułów o transformacie Fouriera (ani o DFT, ani o FFT). Angielska natomiast zawiera całkiem fajne informacje. Jak zawsze oczywiście Kincaid i Cheney jest dobrym źródłem informacji :)\n",
    "\n",
    "### Transformata Fouriera\n",
    "\n",
    "Ogólnie rzecz biorąc, transformata Fouriera przenosi funkcję z dziedziny czasu do dziedziny częstotliwości. Wzór wygląda tak:\n",
    "\n",
    "<img src=\"images/fourier-transform.svg\">\n",
    "\n",
    "Jeśli nie jest oczywiste, co to oznacza, przetłumaczmy to na polski:\n",
    "* \"funkcja w dziedzinie czasu\" to po prostu funkcja typu `f :: Czas -> Cokolwiek<zapewne liczba>`, czyli na przykład zmiana temperatury w ciągu dnia (każdemu momentowi możemy przyporządkować jakąś konkretną wartość). Wykres takiej funkcji mógłby wyglądać tak:\n",
    "\n",
    "<img src=\"images/trends.png\">\n",
    "\n",
    "* \"funkcja w dziedzinie częstotliwości\" to, w pewnym uproszczeniu, funkcja, której podajemy jakąś częstotliwość, a ona mówi nam ile tej częstotliwości jest widoczne w funkcji, którą transformujemy. Wracając do przykładu z temperaturą: jeśli temperatura zmienia się w dobowych cyklach, to po transformacie Fouriera dowiemy się, że funkcja w domenie częstotliwości ma \"peak\" w okolicach częstotliwości 1/24h.\n",
    "\n",
    "Transformata Fouriera ogólnie zasadza się na idei, że skomplikowaną, ale okresową funkcję możemy rozłożyć na sumę podstawowych funkcji trygonometrycznych. Wtedy faktycznie możemy łatwo odpowiedzieć sobie na pytanie jakie częstotliwości są najbardziej w takiej funkcji widoczne.\n",
    "\n",
    "Podstawowe pytanie, jakie można by zadać: po co się to robi? Można to stosować na przykład:\n",
    "* do analizy danych (żeby odpowiedzieć sobie na pytanie czy jakaś wartość zmienia się raczej z dnia na dzień, czy może z minuty na minutę -- wtedy dużo łatwiej stosować pozostałe metody statystyczne i analityczne)\n",
    "* do cyfrowego przetwarzania sygnałów (\"Gdybym mógł, to nawet na tym tekście bym zrobił FFT\" -- kolega z inżynierii akustycznej)\n",
    "* do kompresji\n",
    "* wiele więcej\n",
    "\n",
    "Drugie pytanie: skąd tam się bierze liczba Eulera we wszystkich wzorach?\n",
    "Odpowiedź, raczej dla intuicji niż ścisła: bo robimy transformację ze \"zwykłych\" liczb na jakąś sumę funkcji trygonometrycznych, czyli dokładnie tak, jak we wzorze Eulera:\n",
    "<img src=\"images/euler.png\">\n",
    "\n",
    "\n",
    "### Dyskretna transformacja Fouriera\n",
    "\n",
    "W praktyce jednak nie mamy do czynienia z ciągłymi funkcjami (choćby dlatego, że na komputerze możemy reprezentować tylko skończoną ilość wartości). W takim razie operujemy raczej na ciągach `(czas, wartość)`. Powoduje to jednak, że  transformatę jest nieco łatwiej zrobić. Intuicyjnie: całkowanie to sumowanie, tylko bardzo \"gęste\". W takim razie Taki wzór, jak powyżej, możemy zamienić sobie na jakiś rodzaj (dyskretnego) sumowania. Tak się składa, że z pomocą przychodzą operacje na macierzach i wzór wyraża się dość prosto:\n",
    "\n",
    "<img src=\"images/dft.png\">\n",
    "\n",
    "Tak naprawdę w tym wzorze nie ma żadnej magii (jeśli zna się ten na ciągłą transformatę) -- to po prostu to, co powyżej, tylko całkowanie zamienione jest na sumowanie. Na Wikipedii można nawet znaleźć [prosty przykład dla 4 elementów](https://en.wikipedia.org/wiki/Discrete_Fourier_transform#Example). Zerknijmy, jak to wygląda z perspektywy użytkownika:\n",
    "\n",
    "#### Praktyczny przykład\n",
    "\n",
    "Mamy dane o ruchu na stronie www, tzn. dla każdej minuty mamy liczbę odsłon strony w tej minucie. Wykres (fragment) wygląda tak:\n",
    "<img src=\"images/timeseries.png\">\n",
    "\n",
    "Robimy dyskretną transformatę Fouriera takiego szeregu czasowego, żeby dowiedzieć się, jaka jest sezonowość danych. Poniższy wykres przedstawia udział poszczególnych częstotliwości w analizowanym szeregu:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt # do wykresów\n",
    "import numpy as np              # do macierzy\n",
    "from scipy import fftpack       # do FFT\n",
    "\n",
    "X = fftpack.fft(dataset)\n",
    "f_s = 1  # godzinowo\n",
    "freqs = fftpack.fftfreq(len(dataset)) * f_s # czętotliwości\n",
    "fig, ax = plt.subplots()\n",
    "\n",
    "ax.stem(freqs[:40], np.abs(X)[:40])\n",
    "ax.set_xlabel('Frequency in hits/hour')\n",
    "ax.set_ylabel('Frequency Domain (Spectrum) Magnitude')\n",
    "ax.set_ylim(-1, 200)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ważny jest parametr `f_s`: mówi nam, jaka jest jednostka czasu -- wybraliśmy jedną godzinę, czyli częstotliwości będą podane z jednostką 1/h.\n",
    "Nie mamy dostępnych danych, na których była prowadzona ta analiza, więc musimy zadowolić się rezultatem dołączonym statycznie:\n",
    "<img src=\"images/fourier.png\">\n",
    "\n",
    "Dominującą częstotliwością jest 0.006/h (czyli mniej więcej raz na tydzień) -- oznacza to, że nasze dane mają wzorce powtarzające się z tygodniową częstotliwością.\n",
    "\n",
    "### Szybka transformata Fouriera (FFT)\n",
    "\n",
    "Ciężko o lepsze wyjaśnienie, niż w linku, który już przytaczaliśmy: https://jakevdp.github.io/blog/2013/08/28/understanding-the-fft/.\n",
    "\n",
    "### Zadanie 1.\n",
    "\n",
    "Napisz w dowolnym języku zwyczajną (wolną) dyskretną transformatę Fouriera.\n",
    "\n",
    "### Zadanie 2.\n",
    "\n",
    "Wykorzystaj implementację z zadania 1. do napisania szybkiej wersji transformaty (używając pomysłu z algorytmu Cooleya-Tukeya).\n",
    "\n",
    "### Zadanie 3.\n",
    "\n",
    "Przetestuj implementację z zadania 2. do wykonania analizy szeregu czasowego:\n",
    "1. Znajdź dane przedstawiające jakiś szereg czasowy.\n",
    "2. Załaduj je do programu (polecany: Python + Pandas, ale dowolna metoda jest okej, w tym języki R oraz Julia).\n",
    "3. Zobacz, czy wykonanie analizy Fouriera na tych danych ma sens -- być może trzeba pogrupować je w równe odstępy (zob: funkcja [resample w pakiecie Pandas](https://pandas.pydata.org/pandas-docs/stable/generated/pandas.DataFrame.resample.html)).\n",
    "4. Narysuj wykres częstotliwości i postaraj się opisać jaka jest główna składowa.\n",
    "\n",
    "### Pytanie otwarte\n",
    "\n",
    "Czy transformata Fouriera może zostać wykorzystana do przewidywania szeregów czasowych:?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}