Ciekawostki data mining: RSCTC 2010

W zeszłym tygodniu w Warszawie miała miejsce znakomita konferencja data mining’owa, Rough Sets and Current Trends in Computing (RSCTC). Kilka miesięcy temu TunedIT zorganizowało w ramach RSCTC konkurs Discovery Challenge: Analiza danych genetycznych dla celów medycznych. Teraz odbyła się sesja konkursowa, na której zwycięzcy zaprezentowali publicznie swoje rozwiązania. Audytorium słuchało z uwagą, a po skończonych prezentacja posypały się pytania, więc zwycięzcy nie mieli innego wyjścia jak uchylić rąbka swoich tajemnic. Jeśli ktoś chciałby dowiedzieć się więcej na temat ich rozwiązań, polecam zajrzeć do raportu z konkursu lub do materiałów pokonferencyjnych (str. 4-19). Wkrótce zamieścimy także wywiad z jednym ze zwycięzców, więc śledźcie uważnie naszego bloga!

Konferencja przyniosła również wiele innych ciekawych prezentacji, poza sesją konkursową. Przede wszystkim, odbyły się cztery otwarte wykłady wygłoszone przez światowej klasy naukowców, profesorów: Romana Słowińskiego, Sankara Pala, Rakesha Agrawala i Katię Sycara.

Rakesh Agrawal jest szefem laboratoriów Microsoft Search Labs, odpowiedzialnych za rozwój silnika microsoftowej wyszukiwarki Bing. W swojej prezentacji, Search and Data: The Virtuous Cycle (Wyszukiwanie i dane: sprzężenie zwrotne), Agrawal przedstawił problemy jakie napotyka jego zespół próbując uczynić wyszukiwarkę Bing bardziej “inteligentną”, tak aby wyniki wyszukiwania zawierały dokładnie te strony których użytkownik szuka. Okazuje się, że jednym z najtrudniejszych problemów jest odkrycie faktycznych intencji użytkownika. Silnik wyszukiwania zna tylko zapytanie, zazwyczaj bardzo krótkie (1-2 słowa, często z błędami), np.  “Ireland”, i musi odgadnąć czego użytkownik oczekuje: przewodnika turystycznego, bo wybiera się do Irlandii na wakacje, czy danych geograficznych na temat państwa, bo właśnie pisze pracę magisterską na ten temat? Innym problemem jest to, że wiele słów ma kilka znaczeń: jeśli użytkownik wpisze “polish”, czy oznacza to czasownik, “polerować”, czy przymiotnik, “polski”? Jest też inny problem: jak umiejętnie postępować z liczbami? Zapytanie “$200 camera” daje niewiele sensownych wyników – lepiej spróbuj “$199 camera”🙂

Rakesh Agrawal na RSCTC

Jeszcze wiele podobnych problemów czeka na rozwiązanie. Dodajmy do tego, że algorytm musi umieć przekopać się przez petabajty danych w ułamku sekundy, a już nikt nie będzie miał wątpliwości, że chłopaki z Microsoft Search Labs nie narzekają na nudne zadania. Przy okazji mogę potwierdzić na podstawie własnego doświadczenia, że rozmiar danych i wymagania wydajnościowe są kluczowymi czynnikami, dzięki którym data mining staje się prawdziwym wyzwaniem. Przy małej ilości danych i braku problemów z wydajnością, opracowywanie algorytmów data mining jest po prostu interesującym zajęciem. Ale kiedy wydajność zaczyna odgrywać rolę, odkrywasz, że 95% twoich fantastycznych agorytmów “wysiada” i musisz wszystkie pomysły (oraz kod źródłowy) odwrócić do góry nogami… robi się ciekawie.

Katia Sycara na RSCTCInny wykład, którego wysłuchałem z prawdziwą przyjemnością, to Emergent Dynamics of Information Propagation in Large Networks (Dynamika propagacji informacji w dużych sieciach) przygotowany przez Katię Sycara z Uniwersytetu Carnegie Mellon. To pasjonujące obserwować jak w wielkich sieciach połączonych jednostek (“agentów”), na przykład ludzi, następuje przekaz pewnej informacji “z ust do ust”, jakby przez plotkowanie, i jak w pewnym momencie informacja wypełnia całą sieć lub – odwrotnie – nagle zanika. Ważne jest, abyśmy potrafili przewidzieć ewolucję takich procesów, ponieważ w rzeczywistym świecie tą “informacją” może być groźna choroba, której rozprzestrzenianie się trzeba jak najszybciej powstrzymać; lub żądanie operatora, które trzeba przekazać w jak najkrótszym czasie do wszystkich komputerów dużej rozproszonej sieci.

To jaki wynik zostanie zaobserwowany zależy od różnych parametrów sieci: ile jest połączeń między jednostkami,  jaka jest jej topologia (połączenia rozłożone równomiernie? lub zgrupowane w oddzielnych klastrach?) i na ile pojedynczy agent jest skłonny przekazać plotkę dalej. Najciekawsze jest jednak to, że żadna konfiguracja parametrów nie gwarantuje osiągnięcia pożądanego rezultatu ze 100% prawdopodobieństwem.  Chaos, czysty przypadek, odgrywa bardzo dużą rolę i sprawia, że nawet te same parametry mogą prowadzić do różnych wyników przy ponownym starcie symulacji. Na szczęście istnieje rozwiązanie, odkryte przez zespół Sycary: wykorzystując metody data mining i modelowania statystycznego, zaprojektowali oni inteligentny, samo-adaptujący się algorytm, który dopasowuje parametry sieci na bieżąco, w trakcie ewolucji procesu, poprzez monitorowanie i reagowanie na lokalne zachowanie jednostek – i w ten sposób uzyskuje pożądany wynik za każdym razem.

Jak widać, wykłady otwarte były bardzo inspirujące. Pozostałe prezentacje nie zostawały w tyle – ich autorzy zaprojektowali wiele znakomitych algorytmów, które w sprytny sposób analizują zbiory danych i wyłuskują z nich użyteczne informacje dla celów automatycznego prognozowania i rozpoznawania. Poniżej znajduje się lista prezentacji, które szczególnie przykuły moją uwagę.

Vehicle Classification Based on Soft Computing Algorithms
Piotr Dalka, Andrzej Czyżewski (s. 70)

W większych miastach możecie zaobserwować kamery zainstalowane nad skrzyżowaniami. Rejestrują one ruch uliczny i przesyłają nagranie do centrum monitoringu, gdzie sygnał jest przechowywany i analizowany w celu wykrycia różnego typu zdarzeń (wypadków, korków, kradzieży) lub w celu obliczania statystyk ruchu. Ilość danych przychodzących z miasta jest tak ogromna, że ich ręczne przetworzenie byłoby niezwykle kosztowne. Dlatego konieczne jest stosowanie algorytmów data mining i rozpoznawania obrazów: w celu automatycznego analizowania tego strumienia danych wideo. Jednym z podproblemów jest rozpoznawanie rodzajów pojazdów: ciężarówek, autobusów, samochodów itp. – algorytm, który potrafi to zrobić z 95% dokładnością został zaprojektowany przez autorów niniejszej prezentacji. Muszę dodać, że prezentacja ta jest w pewnym stopniu powiązana tematycznie z konkursem ICDM 2010 organizowanym obecnie w TunedIT, poprzez podobną dziedzinę zastosowań.

Content-Based Scene Detection and Analysis Method for Automatic Classification of TV Sports News
Kazimierz Choroś, Piotr Pawlaczyk (s. 120)

Algorytmy rozpoznawania obrazów po raz kolejny, tym razem w zastosowaniu do strumienia sygnału telewizyjnego. Celem jest automatyczne rozpoznawanie dyscyplin sportowych pokazywanych w wiadomościach telewizyjnych. Dla nas, ludzi, zadanie to jest trywialnie proste (szczególnie w trakcie Piłkarskich Mistrzostw Świata – nawet bez patrzenia), ale dla komputerów jest ono niezwykle trudne, chyba że do jego rozwiązania wykorzysta się algorytmy inteligentne. Nawiasem mówiąc, to zastanawiające jak dużo jest praktycznych problemów dotyczących rozpoznawania obrazów, a jak niewiele z nich potrafi być  obecnie rozwiązanych automatycznie przez komputery, z zadowalającą skutecznością. Wciąż dużo pracy do wykonania i ogromne pole do zastosowań dla technik data mining i uczenia maszynowego.

Gene-Pair Representation and Incorporation of GO-based Semantic Similarity into Classification of Gene Expression
Torsten Schön, Alexey Tsymbal, Martin Huber (s. 217)

Alexey wraz z kolegami odkrył interesujący właściwość mikromacierzy DNA używanych m.in. w diagnostyce medycznej: znacznie lepiej jest analizować różnice pomiędzy wartościami dwóch wybranych genów, niż każdego genu z osobna – współczynnik błędu diagnozy może spaść w niektórych przypadkach nawet o 1/4. Jak dobrać najlepszą parę genów? Poprzez zastosowanie zewnętrznej wiedzy biologicznej na temat interakcji genów i podobieństw między nimi. Warte podkreślenia jest to, że Alexey brał udział w RSCTC 2010 Data Mining Challenge, który również dotyczył analizy danych genetycznych.

Learning Age and Gender Using Co-occurrence of Non-dictionary Words from Stylistic Variations
Rajendra Prasath
(s. 544)

Prezentacja Rajendry była naprawdę perfekcyjna. Zarówno w sensie metodologii naukowej, jak i praktycznego znaczenia wyników. Nie powiem w tej chwili nic więcej, ponieważ planujemy opublikować wkrótce dłuższy opis tego artykułu…

Random Musical Bands Playing in Random Forests
Miron B. Kursa, Elżbieta Kubera, Witold R. Rudnicki, Alicja A. Wieczorkowska
(s. 580)
i
Blind Music Timbre Source Isolation by Multi-resolution Comparison of Spectrum Signatures
Xin Zhang, Wenxin Jiang, Zbigniew W. Raś, Rory Lewis
(s. 610)

Obydwa artykuły badają problem dzielenia ścieżki dźwiękowej na poszczególne instrumenty i rozpoznawania jakie instrumenty grają w danym momencie – takie oprogramowanie byłoby bardzo pomocne przy katalogowaniu i przeszukiwaniu wielkich baz danych multimedialnych, takich jak YouTube, które pojawiły się w ostatnich latach wraz ze wzrostem możliwości technicznych przechowywania i przesyłania danych. Zadanie to jest skomplikowane i wymaga użycia algorytmów inteligentnych, które uczą się na przykładach jak brzmi każdy z instrumentów i jak ten dźwięk “wygląda” cyfrowo, w ciągu zer i jedynek, z którego składa się nagranie. Jedną z ciekawych obserwacji poczynionych przez autorów jest to, że często dwa instrumenty grające razem brzmią jak jeszcze inny, trzeci instrument, co utrudnia zadanie rozpoznawania. Autorzy próbowali wielu rozmaitych algorytmów i ich kombinacji: lasów losowych (random forests), k-najbliższych sąsiadów (k-nearest neighbor), teorii zbiorów przybliżonych (rough sets), drzew decyzyjnych, transformaty Fouriera, deskryptorów MPEG-7, cech widmowych i cepstralnych. Najlepszy osiągnięty poziom trafności rozpoznania był na poziomie 83%, co jest wystarczające dla wielu praktycznych zastosowań.

Wszystkie opisane artykuły można znaleźć w materiałach pokonferencyjnych. Numery stron w nawiasach. Miłej lektury!

This post in English, po angielsku: Data mining curiosities: RSCTC 2010 write-up

Add to FacebookAdd to DiggAdd to Del.icio.usAdd to StumbleuponAdd to RedditAdd to BlinklistAdd to TwitterAdd to TechnoratiAdd to Yahoo BuzzAdd to Newsvine

About Marcin Wojnarski
Data Scientist. Algorithm Designer. Advocate for Open Access and Open Science. Founder & CEO at Paperity: http://paperity.org

One Response to Ciekawostki data mining: RSCTC 2010

  1. Pingback: Data mining curiosities: RSCTC 2010 write-up « TunedIT data mining blog

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: