Algorytmy eksploracji i przetwarzania masywnych zbiorów danych
Informacje ogólne
Kod przedmiotu: | 1000-I2AlgEkspMZD |
Kod Erasmus / ISCED: |
(brak danych)
/
(0613) Tworzenie i analiza oprogramowania i aplikacji
|
Nazwa przedmiotu: | Algorytmy eksploracji i przetwarzania masywnych zbiorów danych |
Jednostka: | Wydział Matematyki i Informatyki |
Grupy: |
Inf., II st, stacjonarne, przedmioty do wyboru |
Punkty ECTS i inne: |
(brak)
|
Język prowadzenia: | polski |
Wymagania wstępne: | Aby w pełni docenić materiał w tego wykładu, zalecamy następujące wymagania: 1. Podstawowe wiadomości z zakresu informatyki obejmujące bazy danych i programowanie współbieżne oraz systemy operacyjne. 2. Algorytmy oraz struktury danych i matematyka dyskretna. 3. Eksploracja danych oraz metody uczenia maszynowego. 4. Algorytmy i metody skalowanego przetwarzania danych. 5. Inżynieria oprogramowania i języków programowania. Wymagana jest praktyczna znajomość współczesnego języka programowania (Java, Python, C, C++, C# itp), oraz zasad programowania obiektowego. |
Całkowity nakład pracy studenta: | 30 godz. wykład 30 godz. laboratoria 3 godz. egzamin 3 godz. prezentacja zadań laboratoria 40 godz. praca własna: przygotowanie zadań 40 godz. bieżące przygotowania do zajęć, studiowanie literatury 40 godz. praca własna: przygotowanie do egzaminu |
Efekty uczenia się - wiedza: | M_W01 - zna zaawansowane metody projektowania i analizowania złożoności obliczeniowej algorytmów i programów sekwencyjnych, równoległych i rozproszonych K_W04. M_W02 - zna metody statystycznej analizy danych, w tym zagadnienia estymacji, testowania hipotez i redukcji wymiaru danych K_W08. M_W03 - zna metody algorytmicznego rozwiązywania problemów obliczeniowo trudnych (aproksymacja, FFT, szybkie algorytmy wykładnicze, heurystyki, metody Monte Carlo, algorytm Metropolisa, symulowane wyżarzanie, algorytmy genetyczne) K_W09. M_W04 - zna biegle co najmniej jeden język programowania oraz biblioteki algorytmów i struktur danych; ma wiedzę na temat praktycznych uwarunkowań wydajnych implementacji algorytmów K_W10. |
Efekty uczenia się - umiejętności: | M_U01 - potrafi opisywać algorytmy i struktury danych w sposób zrozumiały dla nie informatyków K_U02. M_U02 - projektuje i analizuje algorytmy rozproszone; potrafi uzasadnić ich poprawność i przeanalizować złożoności K_U04. M_U03 - posługuje się bibliotekami algorytmów i struktur danych, w tym bibliotekami algorytmów numerycznych K_U05. M_U04 - potrafi posługiwać się podstawowymi narzędziami informatycznymi wspomagającymi tworzenie oprogramowania i jego utrzymanie K_U07. M_U05 - umie znajdować niezbędne informacje w literaturze fachowej, bazach danych i innych źródłach, zna podstawowe czasopisma i konferencje naukowe w swojej specjalności K_U13. |
Efekty uczenia się - kompetencje społeczne: | M_K01 - Kreatywność: Myśli twórczo w celu udoskonalenia istniejących bądź stworzenia nowych rozwiązań K_K02. M_K02 - Analityczne myślenie: Samodzielnie i efektywnie pracuje z dużą ilością danych, dostrzega zależności i poprawnie wyciąga wnioski posługując się zasadami logiki K_K03. M_K03 - Sumienność i dokładność: Jest nastawiony na jak najlepsze wykonanie zadania; dba o szczegół; jest systematyczny K_K04. M_K04 - Komunikatywność: Skutecznie przekazuje innym swoje myśli w zrozumiały sposób; właściwie posługuje się terminologią fachową; potrafi nawiązać kontakt w obrębie swojej dziedziny i z osobą reprezentującą inną dziedzinę K_K05. M_K05 - Wytrwałość i konsekwencja: Pracuje systematycznie i posiada umiejętność pozytywnego podejścia do trudności stojących na drodze do realizacji założonego celu; dotrzymuje terminów K_K08. |
Metody dydaktyczne: | Metody dydaktyczne podające: * wykład informacyjny (konwencjonalny). Metody dydaktyczne poszukujące: * ćwiczeniowa, * laboratoryjna, * klasyczna metoda problemowa. |
Metody dydaktyczne eksponujące: | - pokaz |
Metody dydaktyczne podające: | - wykład informacyjny (konwencjonalny) |
Metody dydaktyczne poszukujące: | - ćwiczeniowa |
Skrócony opis: |
Dynamiczne pojawienie się dużych zbiorów danych w internecie spowodowała konieczność ich szybkiego przetwarzania, a umiejętność ta powoli staje się jednym z podstawowych wymogów pracy w wielu dużych firmach. Zagadnienie to jest wymagające i pozwala na praktyczne wykorzystanie wiedzy zdobytej z takich dziedzin jak algorytmika, przetwarzanie danych, eksploracja danych itp. Ponadto, ze względu na specyfikę problemu, istotnym elementem zagadnienia stała się nauka optymalizacji kodu eksplorującego dane z wykorzystaniem dostępnych narzędzi w rożnych kontekstach: obliczeń, zużycia energii, ograniczeniami związanymi z przesyłem i składowaniem danych. Wykład ten przedstawi pojawiające się w tej dziedzinie problemy oraz paradygmaty pozwalające na ich rozwiązanie. |
Pełny opis: |
Popularność sieci Web i biznesu w internecie (tzw. e-commerce) spowodowała powstanie wielu zbiorów danych, z których informacje mogą być pozyskiwane za pomocą metod eksploracji danych. Tym co odróżnia ten wykład od innych o podobnej tematyce jest to, że skupia się on na eksploracji danych ze zbiorów o bardzo dużej wielkości, czyli danych tak dużych, że nie mieszczą się swobodnie w pamięci operacyjnej czy wręcz dysku pojedynczego węzła obliczeniowego. Opiszemy i podamy motywacje technik w eksploracji dużych zbiorów danych. Skoncentrujemy się na praktycznych aspektach algorytmów, które zostały wykorzystane w celu rozwiązania kluczowych problemów w eksploracji danych, a które mogą być wykorzystane na nawet największych zbiorach danych. Dział ten w literaturze był dotąd potraktowany tylko powierzchownie i nie ma jeszcze kompleksowego przeglądu istniejących metod. Co ważne, w tym wykładzie będziemy mówić o tym jak rozwiązać konkretne problemy eksploracji danych w kontekście ogromnego rozmiaru danych. Ponadto, celem tego wykładu jest także wyrobienie intuicji programistycznych dotyczących rozwiązywania standardowych problemów związanych z przetwarzaniem danych typu "big data". Wykład zaczyna się od przypomnienia podstawowych zagadnień eksploracji danych, następnie krótkiej dyskusji na temat Map Reduce’a, który jest ważnym modelem skalowalnego przetwarzania danych. Dalej wyjaśnimy tajniki poszukiwania podobnych obiektów z szczególnym uwzględnieniem technik hashwania. Następnie zajmiemy się algorytmami eksploracji i przetwarzania strumieni danych, które pojawiają się zbyt szybko i jest ich zbyt dużo by dokonać wyczerpującej analizy. Kolejnym z omówionych tematów będą metody analizy połączeń w sieci Web, pojawi się idea Page Ranku oraz inne metody. Pozostałe tematy dotyczą problemów ze znalezieniem zbiorów częstych i klastrowania. Ponadto rozpatrzymy dwa zastosowania: systemy rekomendacyjne oraz reklamę internetową, obydwie niezbędne w ebiznesie. Wykład z założenia zamierza być interesujący zarówno dla teoretyków jak i praktyków. Przedmiot będzie zrealizowany w dwóch częściach: wykład oraz laboratorium. Wykład będzie obejmował teoretyczne i praktyczne aspekty przetwarzania i eksploracji dużych zbiorów danych. W ramach wykładu zamierzamy przedstawić modele eksploracji danych w paradygmacie rozproszonym. Materiały wykładu zostaną udostępnione w formie slajdów. Praca w laboratorium będzie polegać przede wszystkim na samodzielnym wykonaniu przez studentów zadań związanych z prezentowanymi na wykładzie zagadnieniami. Ćwiczenia będą prowadzone w formie zachęcającej uczestników do intensywnej pracy w trakcie zajęć, jak i samodzielnej pracy domowej. W ramach laboratorium przewidujemy implementację i eksperymentowanie z otwartymi implementacjami przedstawionych algorytmów. Treści zadań (wraz z opisem ich realizacji) będą udostępnione w formie materiałów z laboratorium publikowanych w systemie Modle. Program ramowy kursu: 1. Rozproszone systemy plików i Map Reduce jako wygodny model do tworzenia skalowalnych algorytmów przetwarzania danych, 2. Wyszukiwanie podobieństwa, w tym rożne metody hashujące. 3. Przetwarzanie strumieni danych, w których dane trzeba przeanalizować szybko lub będą nieprzydatne ("przeanalizuj albo wyrzuć"). 4. Analiza połączeń w sieci Web: w tym Google s Page Rank, wykrywanie linkspam, podejście "hubs-and-authorities". 5. Wyszukiwanie elementów częstych, w tym reguły asocjacyjne, metoda koszykowa, algorytmy typu apriori. 6. Algorytmy grupowania dużych zbiorów danych oraz zbiorów danych w wysokich wymiarach. 7. Problemy w aplikacjach internetowych: zarządzanie reklamami i systemy rekomendujące. 8. Algorytmy analizy i eksploracji bardzo dużych grafów, zwłaszcza tych występujących na serwisach społecznościowych. 9. Redukcja wymiarowości, w tym rozkład według wartości osobliwych, indeksowanie semantyczne. 10. Algorytmy uczenia maszynowego, które mogą być stosowane do bardzo dużych zbiorów danych, np.: perceptron, SVM, algorytm spadku gradientowego itd. |
Literatura: |
Jure Leskovec, Anand Rajaraman, and Jeffrey David Ullman. Mining of massive datasets. Cambridge University Press, 2014. (http://www.mmds.org/) Jiawei Han, Micheline Kamber. Data Mining: Concepts and Techniques. The Morgan Kaufmann Series in Data Management Systems, 2000. Tadeusz Morzy. Eksploracja danych Metody i algorytmy. PWN, 2013. |
Metody i kryteria oceniania: |
Zaliczenie laboratorium odbywa się na podstawie 4/5 projektów zaliczeniowych wykonywanych częściowo w trakcie laboratoriów i częściowo samodzielnie. Zaliczenie wykładu na podstawie oceny z ćwiczeń i indywidualnego projektu (prezentacja + pytania do projektu). |
Właścicielem praw autorskich jest Uniwersytet Mikołaja Kopernika w Toruniu.