Artykuły na temat Eksploracji danych, czyli Data Miningu

We współczesnym świecie mamy do czynienia z bardzo dużymi ilościami informacji. Wciąż powstają ogromne bazy danych i magazyny danych, w których przechowuje się informacje o często strategicznym znaczeniu dla firmy lub innego podmioty, którego te informacje dotyczą. Mogą to być np. dane na temat sprzedaży produktów w sieci sklepów, dane o preferencjach klientów, dane meteorologiczne. Często gromadzi się ich bardzo dużo. Sieć sprzedaży Wal-Mart gromadzi dziennie dane o ponad 20 milionach przeprowadzonych transakcji. Łatwo można przeliczyć, ile danych gromadzi w ciągu roku, dziesięciu lat itd. Koncern Mobil Oil rozbudowuje magazyn danych mogący pomieścić ponad 100 terabajtów danych o wydobyciu ropy naftowej, system satelitarnej obserwacji EOS zbudowany przez NASA, w każdej godzinie pracy generuje dziesiątki gigabajtów danych, niewielkie supermarkety rejestrują dziennie dziesiątki tysięcy sprzedaży.

Jak widać praktycznie na każdym kroku powstają ogromne skarbnice danych – wystarczy tylko do nich sięgnąć i możemy uzyskać cenną wiedzę. Informacje o dotychczasowej działalności przedsiębiorstwa, poziomie i strukturze sprzedaży mogą posłużyć do wspomagania podejmowania decyzji. Z pomocą przychodzą nam różnego rodzaju systemy wspomagające podejmowanie decyzji. Wykorzystują one szereg algorytmów wyszukujących wiedzę w zbiorach danych. Oczywiście, im większa jest taka baza danych, tym trafniejsze decyzje możemy na jej podstawie podejmować. I tu napotykamy na bardzo poważny problem, bowiem koszt przeanalizowania zbioru danych (najczęściej kosztem jest czas potrzebny na wykonanie analizy) zależy co najmniej liniowo od objętości analizowanych danych. Jeżeli ilość rekordów w bazie danych sięga kilku-kilkunastu milionów, co w przypadku współczesnych baz danych nie jest rzadkością, koszt ten może znacznie przekroczyć granice akceptowalności, nawet wielokrotnie! Po co nam algorytm, który da bardzo dobre i wysoce prawdopodobne wyniki po kilku miesiącach lub kilku latach pracy, skoro potrzebne są nam w ciągu najwyżej kilku sekund, minut lub godzin, w zależności od rodzaju problemu.

Aby zredukować ten problem, stworzono kilka strategii radzących sobie z nim. Oto najpopularniejsze z nich.

1. Okienkowanie

Najbardziej powszechną strategią uczenia się na podstawie dużych zbiorów danych jest technika okienkowania, czyli uczenia się na podstawie tylko niewielkiego fragmentu zbioru trenującego i w miarę potrzeby rozszerzania go. Wybierane “okienko” całego zbioru trenującego nazywane jest zbiorem roboczym. Cały pomysł tej strategii jest bardzo prosty. Najpierw algorytm wybiera losowo jakiś niewielki zbiór roboczy z całego zbioru trenującego i na jego podstawie uczy się hipotezy. Następnie hipoteza ta jest testowana na pozostałych przykładach całego zbioru trenującego, a początkowo wybrany zbiór roboczy jest uzupełniany o losowo wybrane przykłady, które są klasyfikowane przez tą hipotezę niepoprawnie. Następnie, po uzyskaniu nowego zbioru roboczego, algorytm uczy się nowej hipotezy na jego podstawie. Cały proces jest powtarzany tak długo, jak długo nowa hipoteza jest lepsza od poprzedniej (ma mniejszy błąd próbki lub uzyskany błąd próbki spadł poniżej wymaganego poziomu). Ponieważ uzyskane wyniki mogą w dużym stopniu zależeć od wyboru pierwszego zbioru roboczego, zaleca się powtórzyć cały proces kilka razy i wybrać najlepszy wynik ze wszystkich uzyskanych. W przypadki zbiorów trenujących o liczebnościach od kilku do kilkuset tysięcy przykładów zaleca się wybór pierwszego zbioru roboczego, który jest 10% częścią całego zbioru trenującego. Taki wybór prowadzi zwykle do uzyskiwania zadowalających hipotez już po kilku iteracjach.

2. Redukcja liczby przykładów

Jeżeli z jakiś względów technika okienkowania nie daje zadowalających rezultatów, bądź wymaga bardzo wielu iteracji, można przeprowadzić z pozoru drastyczną i samobójczą operację redukcji liczby przykładów w zbiorze trenującym. Oczywiście, aby nie była to w istocie samobójcza operacja, należy przeprowadzić ją ostrożnie, w taki sposób, aby pozostawić w zbiorze trenującym interesujące nas zależności. Redukcja taka może mieć dwojaką postać. Możemy przeprowadzić we wstępnej fazie przygotowania zbioru trenującego do analizy grupowanie pojęciowe. Oczywiście należy pamiętać, aby odpowiednio dobrać ziarnistość grup, tak, aby uzyskana liczba przykładów była równa porządanej skali redukcji przykładów. Inne podejście polega na bezpośrednim wyborze przykładów do nowego zbioru trenującego, które będą najbardziej reprezentatywne dla całego zbioru trenującego. Można użyć wielu różnych heurystyk, które umożliwią nam ten wybór.

3. Próbkowanie wewnętrzne

Zarówno okienkowanie jak i redukcja liczby przykładów prowadzi do zmniejszenia kosztów obliczeń poprzez prowadzenie ich na podstawie pewnego podzbioru całego zbioru trenującego. Istnieje jednak strategia, która nie prowadzi do skazywania niektórych przykładów z góry na wykluczenie. Metoda ta nazywana jest próbkowaniem wewnętrznym. Polega na tym, że tylko do najbardziej złożonych i wymagających długiego czasu obliczeń stosuje się podzbiory całego zbioru trenującego, a wszystkie pozostałe obliczenia prowadzone są bezpośrednio na całym zbiorze trenującym. Często takie podejście daje lepsze efekty niż okienkowanie i redukcja liczby przykładów właśnie dzięki temu, że możemy dla każdego obliczenia, którego koszt jest w dużej mierze zależny od ilości analizowanych przykładów, dobierać taką ilość przykładów, aby uzyskać porządany efekt przy najmniejszym koszcie.

W przypadku reguł indukcyjnych, od ilości przykładów zależy przede wszystkim ocena jakości kompleksów, do którego wymagane jest podanie liczby przykładów pokrywających kompleks z pewnego podzbioru przykładów. Jeżeli taki zbiór jest liczny, obliczenia możemy wykonać na jego losowym podzbiorze, co w efekcie da znaczną redukcję kosztów wykonania algorytmu.

4. Dekompozycja zbioru trenującego

Koszt obliczeniowy nie jest jedynym problemem, występującym podczas analizy dużych zbiorów danych rzeczywistych. Często zależności opisujące taki zbiór są tak wysoki stopień złożenia, że stworzone na ich podstawie hipotezy stają się nadmiernie skomplikowane i niemożliwe do interpretacji. Jeżeli więc uzyskana złożoność hipotez jest nie akceptowalna z punktu widzenia dalszego ich wykorzystania do klasyfikacji nowych przykładów, stosuje się dekompozycję zbioru trenującego na mniejsze podzbiory i uzyskuje się kilka mniej złożonych hipotez dla każdego z tych podzbiorów. Ze względu na to, że nowe hipotezy zostały uzyskane na podstawie podzbiorów całego zbioru trenującego, mają ograniczony zakres stosowania. Aby ułatwić rozróżnienie tego zakresu, należy dokonać dekompozycji zbioru trenującego ze względu na wartości atrybutów, a nie losowo. W ten sposób mamy ścisły podział zakresów stosowania każdej z uzyskanych hipotez do warunków jej stosowania, określonych przez wartości atrybutów wybranych do dekompozycji.