Andrzej Pastusiak

Przygotowanie wykładu z demonstracją na temat systemu MineSet, firmy Silicon Graphics, do zadań data minning (odkrywanie wiedzy). Informacje i wersja demo dostępna pod adresem http://www.sgi.com/software/mineset/).

Statistic visualizer umożliwia zbadanie podstawowych parametrów statystycznych kolumn bazy danych. Umożliwia wydobywanie danych statystycznych zarówno z pól numerycznych jak i zawierających wartości dyskretne.

Jest to narzędzie bardzo podobne do statistic visualizera. Różnica tkwi w tym, że obok danych statystycznych dla całej populacji (tak jak w statistic visualizerze) podawane są dane dla każdego z klastrów, na które zostały podzielone dane za pomocą wbudowanych narzędzi podziału.

Map visualizer jest narzędziem wspierającym wizualizację danych geograficznych. Wraz z pakietem otrzymujemy wiele gotowych map geograficznych. Niestety nie ma map Polski z podziałem na stare jak i nowe województwa. J

Podobnie jak we wszystkich narzędziach mnogość informacji, jakie możemy przekazać pojedynczym elementem wykresu jest duża, włączając możliwość animowania mapy (podobnie jak w splat i scatter visualizerze), gdzie pod oś czasu możemy podstawić jeden z parametrów tabeli lub kombinację dwóch.

Trzy pierwsze wymiary to osie wykresu. Czwarty piąty i szósty określają rozmiar, kolor i etykiety obiektów umieszczanych w przestrzeni trójwymiarowej. Kolor może reprezentować np. klaster do jakiego została zakwalifikowany dany wiersz, wielkość - błąd decyzji lub liczbę wierszy reprezentowanych przez obiekt.

Kliknięcie na wykresie 2D przenosi wizualizację w głównym oknie scatter visualizera do wskazanego wycinka hiperprzestrzeni. Dość nowatorskim rozwiązaniem będącym silną stroną tego pakietu, jest możliwość naszkicowania na wykresie 2D trajektorii, określającej drogę po jakiej chcielibyśmy się "przejść" we wskazanych wymiarach. Naciśnięcie klawisza "play" powoduje, że w głównym oknie obiekty zaczynają się płynnie transformować (animować) w zależności od wymiarów ustalonych w danej chwili na wykresie 2D. Tak stworzoną animację można dowolnie odtwarzać i zapętlić.

Należy podkreślić, że wszystkim 8 zmiennym przyporządkowywać można zarówno wartości dyskretne jak i ciągłe. Istnieje wiele sposobów na określenie, jak wartość numeryczna jest przekształcana na kolor lub wielkość obiektu. Płynne obracanie, poruszanie i skalowanie wykresu. jest wielką zaletą, gdyż "łapiąc" myszką wykres 3D możemy wprowadzić niewielką paralaksę ruchu, co umożliwia dużo lepszą percepcję prezentowanych danych. Możliwość animacji początkowo wydająca się niepotrzebnym gadżetem, dobrze wykorzystana może znacznie przyśpieszyć czas wydobywania istotnych danych z eksperymentów, jak i mocno zwiększyć możliwości interpretacji danych.

Jest narzędziem zbliżonym do scatter visualizera. Różnica tkwi głównie w tym, że pojedyncze lub zagregowane wiersze bazy danych są reprezentowane nie za pomocą różnokolorowych obiektów lecz częściowo przeźroczystych chmurek. Podobnie jak Scatter Visualizer, istnieje możliwość podania dodatkowo trzech wymiarów (Slider1, Slider2, Summary), które są obrazowane obok na wykresie 2D i umożliwiają zaplanowanie animacji w głównym oknie.

Tree visualizer umożliwia ogólnie ujmując przedstawianie zależności drzewiastych w zbiorze danych. Jak w większości narzędzi, możliwości tree visualizera są szerokie. Do dyspozycji mamy trzy elementy, za pomocą których można przedstawiać różnorakie wartości. Podstawowymi elementami są słupki stojące na kostce. Nad każdym słupkiem może być narysowany dysk. Wysokość na jakiej jest umieszczany może być także funkcją zbioru danych. Dodatkowo każdemu z elementów można przypisać kolor reprezentujący wartość któregoś z atrybutów zbioru danych. Kolory mogą reprezentować zarówno przedziały wartości jak i wartości dyskretne. Na poniższym rysunku widać, iż istnieje możliwość jednoczesnej wizualizacji do ośmiu atrybutów w każdym węźle.

Nie istnieją żadne ograniczenia na wysokość budowanego drzewa. Jako kryterium podziału na poddrzewa można podać jedną z dyskretnych kolumn tabeli lub za pomocą narzędzi do obróbki danych można określić kryterium podziału węzłów każdego poziomu na podwęzły. Oczywiście najbardziej naturalnym sposobem budowy drzew jest zastosowanie algorytmów do generacji drzew decyzyjnych. Przy takim podejściu nie musimy określać, jakie wartości zostaną przypisane do odpowiednich elementów wykresu 3D.

Po drzewie można się płynnie poruszać i obserwować zmiany wizualizowanych wartości w różnych gałęziach. W trakcie przesuwania się między węzłami całe drzewo jest animowane na ekranie, dzięki czemu użytkownik dość dobrze "czuje", w którym kierunku się porusza. Klikając na pojedynczy słupek, można otrzymać informacje o wartościach liczbowych reprezentowanych przez postać graficzną.

Funkcjonalnie nie różni się wiele od tree visualizera. Jego funkcją jest prezentacja modelu wytworzonego przez Option tree inducer. Różnica między drzewem decyzyjnym a drzewem opcji polega na tym, że w każdym z węzłów mamy do wyboru wiele możliwych dróg. Decision tree na każdym poziomie wyróżnia jeden atrybut, na podstawie którego przesuwamy się po drzewie klasyfikując wzorzec. Option Tree umożliwia nam wybór wielu możliwych dróg. W każdym węźle decyzyjnym można wybrać atrybut, który będzie wyznaczał kryterium podziału drzewa. Złożoność takiego drzewa jest nieporównywalnie większa niż zwykłego drzewa decyzyjnego, dlatego czas potrzebny na jego generację może wielokrotnie przekraczać czas potrzebny dla zwykłej odmiany drzewa. Jest on mocno zależny od ilości atrybutów oraz maksymalnej ilości opcji na każdym z poziomów. Drzewo opcji może okazać się niezastąpione, gdy wartości atrybutów klasyfikowanego wzorca są niepewne. Możliwe jest także potraktowanie opcji na każdym z węzłów jako ekspertów i wybranie odpowiedzi najczęstszej lub obarczonej najmniejszym błędem .

Decision table visualizer jest kolejnym sposobem wizualizacji drzewa decyzyjnego. Jednakże kolejne podziały nie są reprezentowane za pomocą węzłów drzewa lecz słupków umieszczonych w rzędach i kolumnach tabeli. Zarówno z rzędem jak i kolumną związany jest atrybut, który jest dyskretny, bądź automatycznie dzielony jest na przedziały. Każdy ze słupków reprezentuje rozkład jakiejś cechy pod warunkiem że pewne atrybuty przyjmują określoną wartość opisaną na wykresie. Klikając na jednym ze słupków możemy, go rozwinąć widząc następne kryterium podziału. (na rysunku international plan oraz voice mail plan) tworząc rekurencyjnie tabelę decyzyjną wewnątrz tabeli. Wysokość słupków reprezentuje wagę, jaką mają obrazowane przez nią rekordy. Zazwyczaj każdy rekord ma wagę jednostkową, a zatem wysokość określa ilość reprezentowanych rekordów.

Evidence visualizer jest narzędziem, które może być tylko wywoływane w połączeniu z narzędziami do klasyfikacji i estymacji błędów. Dzieje się tak, gdyż obrazowane są różnego rodzaju prawdopodobieństwa warunkowe, wyliczone na podstawie zbioru danych dla klasyfikacji jednej dyskretnej wartości. Przykładem może być klasyfikacja grzybów na jadalne i niejadalne na podstawie takich wielkości jak kolor, wielkość kapelusza itp.

Panel po prawej stronie przedstawia prawdopodobieństwa przynależności obiektu do danej klasy na podstawie całego zbioru uczącego, czyli stosunek wystąpień rekordów danej klasy do liczby wszystkich rekordów. Po lewej stronie dla każdego z atrybutów zbioru uczącego rysowane są rzędy słupków lub walców podzielonych na sektory. Jeżeli atrybut jest dyskretny, dla każdej jego wartości rysowany jest jeden element. Jeżeli jest ciągły, dokonywana jest automatyczna dyskretyzacja na takie przedziały, które dają możliwie największe różnice w wizualizowanych prawdopodobieństwach warunkowych. Reprezentowane prawdopodobieństwa warunkowe opierają się na prostym klasyfikatorze bayesowskim.

P(A_j|C_i) , gdzie

C_i - kolejne klasy do jakich staramy się klasyfikować prezentowane wzorce
A_j - kolejne przedziały dla wartości ciągłych lub kolejne wartości atrybutów dyskretnych.
Każdemu C_i (klasie) odpowiada jeden kolor opisany w legendzie po prawej stronie.

Jest to model multiplikatywny i aby sklasyfikować wzorzec X=<A₁,A₂,...A_n>, czyli policzyć P(C_i|X), należy wymnażać przez siebie odpowiednie prawdopodobieństwa warunkowe P(A_j|C_i).

Drugim modelem jest wykres słupkowy, gdzie wizualizowane prawdopodobieństwa mają charakter addytywny, dlatego są prostsze w odbiorze. Wielkość podziału słupków w formie ciastek (cake bars) określa addytywną postać prawdopodobieństwa za tym że obiekt należy do danej klasy lub przeciw temu. Udział kawałka o kolorze odpowiadającemu klasie C_i w całym ciastku jest proporcjonalny do: -log(P(A_j|C_i)). przy prawdopodobieństwie przeciw i -log(1-P(A_j|C_i)) przy prawdopodobieństwie za, które jest bardziej intuicyjne w odczycie.

Szczegółowe omówienie matematycznej reprezentacji wyjaśnione jest przy opisie algorytmów klasyfikacji. Istotne jest, iż za pomocą evidence visualizera, można dość łatwo dostrzec atrybuty, które determinują przynależność do poszczególnych klas, i takie, które są nieistotne. Te kawałki "ciastek", które są nierówno podzielone, niosą istotną informację o przynależności do klas. Atrybuty te są wymienione na liście w pierwszej kolejności. Poza wyodrębnieniem samych istotnych atrybutów dostrzec można tendencje i ich zakresy, warunkujące przynależność do jednej lub inne klasy.

Możliwe jest interaktywne testowanie modelu. Zaznaczając po jednym ze słupków w wybranych rzędach można przetestować, jak model sklasyfikuje rekord o znanych atrybutach. Słupek, który zaznaczymy odpowiada przedziałowi lub wartości atrybutu. Informacja o względnym prawdopodobieństwie sklasyfikowania wzorca do każdej z klas, pojawia się w okienku po lewej stronie na wykresie kołowym.

• Prevalence (support)- częstość występowania reguł takich, że prawdziwe jest zarówno X i Y - P(XÇY).
• Predictibility (confidence) -przewidywalność - P(Y|X)=P(XÇY)/P(X)
• Expected predictibilty (expected confidence)- oczekiwana przewidywalność - P(Y)
• Lift - predictibility / expected predictibility - P(Y|X)/P(Y)=P(XÇY)/P(X)/P(Y)

Za algorytmy z pozyskiwaniem wiedzy odpowiada moduł Mineset Server. Oparty jest on głównie na bibliotece MLC++ [2]. Większość zastosowanych algorytmów została słabo lub w sposób zdawkowy opisana w dokumentacji. Zostaną przedstawione tylko te algorytmy, które zostały opisane w sposób wyczerpujący. Być może ta niedogodność zostanie usunięta w kolejnych wersjach pakietu.

Możliwe są dwa sposoby na klastry. Pierwszy Single k-Means, gdzie z góry zakładamy liczbę klastrów na jakie ma być podzielony zbiór danych oraz Iteratice k-means, gdzie podajemy tylko zakres liczby oczekiwanych klastrów.

Jest jedną z najprostszych sposobów klasyfikacji, jednakże dla małych zbiorów danych jest stosunkowo dobra. Wraz ze wzrostem liczby wzorców, staje się mniej dokładna. Naturalnym narzędziem do obrazowania wyników tej klasyfikacji jest evidence visualizer. Budowany model stara się określić prawdopodobieństwo przynależności do jednej z klas C_i znając część atrybutów wzorca X=<A₁,A₂,...A_n>. Korzystając z rachunku prawdopdobieństwa:

Ponieważ P(X) jest stałe dla klasyfikowanego wzorca, P(C_i|X) jest proporcjonalne do wyrażenia w liczniku. Budując model wylicza się wszystkie prawdopodobieństwa warunkowe P(A_j=a_jk|C_i) oraz P(C_i). Jeżeli atrybuty mają charakter ciągły, należy je zdyskretyzować. Obliczamy wyrażenie w liczniku dla każdej z klas oraz normalizujemy tak, aby w sumie dawały jeden. To z wyrażeń które, jest największe reprezentuje klasę, do której zostanie zaklasyfikowany wzorzec. Znormalizowane prawdopodobieństwa warunkowe wyświetlane są w postaci wykresów kołowych w evidence visualizerze.

W przypadku, gdy atrybut ma wartość nieokreśloną (NULL), jest on ignorowany, tzn. przy obliczaniu prawdopodobieństw warunkowych dla atrybutu A_j jest on pomijany w ciągu uczącym.

,gdzie

n_i - liczba wzorców uczących należących do klasy C_i,

n_ijk – liczba wzorców uczących należących do klasy C_i i z atrybutem A_j równym a_jk.

gdzie k_j to liczba wartości jakie może przyjąć atrybut A_j. f jest współczynnikiem korekcji. W pracy [4] wykazano, że najlepsze rezultaty daje f=1/n gdzie n to liczność całego ciągu uczącego.

Ciekawą innowację wprowadza wizualizacja. Wizualizacja znormalizowanych prawdopodobieństw warunkowych P(A_j=a_jk|C_i) dla każdego atrybutu i każdej jego wartości jest mało czytelna, gdyż prawdopodobieństwa przynależności trzeba ze sobą wymnażać

Przy takim podejściu "wygrywa" ta klasa, dla której wartość powyższego wyrażenia jest najmniejsza. Takie wyrażenie przedstawia raczej prawdopodobieństwo przeciw danej klasie. Bardziej intuicyjna dla użytkowników wydaje się jednak reprezentacja w postaci wykresów słupkowych, gdzie przedstawiane jest addytywna forma prawdopodobieństwa przeciw wszystkim innym i wysokość słupków jest proporcjonalna do a bazy do . Użytkownik interaktywnie wybierając pewne wartości atrybutów może obserwować, jak zmienia się prawdopodobieństwo zaklasyfikowania wzorca do jednej lub drugiej klasy. Intuicyjnie przypomina to dolewanie cieczy do fiolek. Ta fiolka (klasa) "wygra", gdzie będzie więcej cieczy. Dodawanie prawdopodobieństw "słupków" w takiej postaci jest bardziej intuicyjne niż ich wymnażanie.

Trudno określić, jaki konkretny algorytm wykorzystywany jest w pakiecie. W dokumentacji brak jasnych i klarownych informacji, natomiast znajdują się odnośniki do algorytmów ID3 oraz C4.5. Jednakże trudno mieć pewność, że właśnie te algorytmy są wykorzystywane do budowy modeli klasyfikatorów. Wydaje się, że używana jest jedna z modyfikacji tych algorytmów. Budowany jest taki model, dla którego estymowany błąd klasyfikacji jest najmniejszy. Możliwe są dwa podejścia. Pierwsze, nazwane holdout, dzieli zbiór uczący według zadanych proporcji na dwie części. Na podstawie pierwszej budowany jest model, natomiast druga służy do określenia błędu klasyfikacji. Drugą bardziej dokładną lecz, także bardziej czasochłonną jest metoda cross-validation dzieląca zbiór na k części. Klasyfikator jest uczony k razy, za każdym razem na zbiorze k-1 podzbiorów. Pozostały podzbiór służy do wyznaczenia błędu. Ostateczny błąd klasyfikacji jest średnią z k kroków. Możliwe jest iteracyjne powtarzanie tego procesu wiele razy.

Algorytm umożliwia wybranie atrybutów (kolumn), które najlepiej wyznaczają jeden z atrybutów. Można określić liczbę takich atrybutów oraz takie, o których wiemy, że są istotne i wyszukać następne. Jakość wybranych atrybutów mierzy się współczynnikiem czystości – purity. Wybrane kolumny podzielą rekordy na podzbiory. Jeżeli każdy z takich podzbiorów zawiera rekordy przynależne tylko do jednej klasy, to ten podzbiór ma czystość 100. Czystość podzbioru jest 0, jeżeli wszystkie klasy mają równą reprezentację. Całkowita czystość podziału jest w jakiś sposób proporcjonalna do czystości podzbiorów (średnia?, średnia ważona?).

Użycie tego algorytmu jest szczególnie przydatne przy wybraniu głównych osi do wizualizacji za pomocą scatter i splat visualizera lub do konstrukcji drzew decyzyjnych.

Pakiet MineSet umożliwia proste operacje na danych poddawanych wizualizacji bądź algorytmom wydobywania wiedzy. Większość z nich to proste operacje mające na celu poprawę wydajności narzędzi. Do bardziej skomplikowanych można posłużyć się zapytaniami SQL kierowanymi do serwera baz danych. Możliwe jest przechowywanie i zapisywanie wielu zestawów w różny sposób przetworzonych rekordów tak, że do różnych celów pozyskiwania wiedzy można przygotować różne zestawy danych.

Umożliwia przekształcenie wartości ciągłych w kolumnie lub kolumnach na wartości dyskretne. Użytkownik określa sam wartości graniczne przedziałów lub umożliwia dobór automatyczny. Przykładem może być podział wartości liczbowej 'wiek'. Podanie takich danych do algorytmu wyszukującego reguły prowadziłoby do nieefektywnych reguł. Dużo lepiej zamienić kolumnę wiek, na taką gdzie przechowywany jest przedział wiekowy. Wtedy algorytm generacji reguł wyprodukuje bardziej ogólne reguły dotyczące ludzi młodych, w średnim lub podeszłym wieku . Możliwe jest podawanie ręcznie przedziałów lub automatyczny podział na podaną lub dobraną automatycznie liczbę przedziałów. Przy automatycznym doborze ich liczba zależna jest od logarytmu z liczby różnych wartości w zbiorze. Możliwe jest określenie procentowej liczby skrajnych wartości (na początku i końcu zbioru dzielonych wartości), które będą odrzucane przy automatycznych algorytmach, tak aby skrajne wartości nie wpływały na wynik. Algorytm podziału dąży, aby w każdym z przedziałów znalazła się możliwie równa liczba różnych wartości. Jednakże można wyspecyfikować kolumnę, która będzie określać wagę każdej wartości (domyślnie każda wartość ma wagę 1). W takim wypadku w każdym z przedziałów suma wag rekordów przynależnych do przedziału będzie podobna.

Dodaje rekordy w bazie danych wykonując na ich polach proste operacje jak znalezienie sumy, maksimum, minimum, liczby agregowanych rekordów. Przydatne do usuwania danych nadmiarowych. Przykładem może być baza danych firmy telekomunikacyjnej działającej w wielu krajach. Gdy nie interesują nas zależności między konkretnymi klientami tylko krajami, korzystne może być połączenie wszystkich rekordów z każdego państwa w jeden reprezentujący "średniego klienta" w każdym z państw lub zsumowanie wpływów z oddziałów w każdym państwie oraz liczby klientów w jeden rekord reprezentujący to państwo.

Pozwala na sprawdzenie (zastosowanie) reguł wygenerowanych na innym zbiorze danych do nowego zestawu. Szczególnie przydatne przy sprawdzaniu wygenerowanych reguł klasyfikacji lub estymacji na danych testowych. Umożliwia dodanie kolumny będącej wynikiem działania jednego z algorytmów klasyfikacji. Możliwe jest także dołączenie nowego zbioru danych do już istniejącego modelu tak, aby zwiększyć jego poprawność.

Pozwala wybrać ze zbioru rekordów (danych) przypadkowy podzbiór. Szczególnie przydatne przy dużych zestawach danych lub przy podziale danych na zbiór uczący i zbiór testowy.

Pakiet MineSet dzięki swym szerokim możliwościom wizualizacji danych ukazuje, jak potężnym narzędziem mogą być algorytmy automatycznego pozyskiwania wiedzy. Wydaje się, iż wykorzystywanie samych algorytmów pozyskiwania wiedzy bez możliwości interaktywnego stałego podglądania wyników pracy może być mocno nieproduktywne i nieporęczne. Dzięki zapoznaniu się z pakietem autor przekonał się, jak wielka siła drzemie w odpowiednim jego zastosowaniu. Naukowcy mogą stosować tego typu narzędzia do obróbki danych z eksperymentów naukowych, statystycy do wyławiania trudno dostrzegalnych na pierwszy rzut oka zależności w danych demograficznych i statystycznych, specjaliści od marketingu mogą poznać lepiej gusta swoich klientów.

Pakiet ma zaimplementowany stosunkowo wiele algorytmów, które jednocześnie nie przytłaczają komplikacją parametrów. Obsługa jest intuicyjna i prosta i nawet osobie nieobytej z tego typu programami nie powinna przysparzać trudności. Mimo prostoty obsługi istnieje zawsze możliwość określenia wielu parametrów, kryteriów i zależności, jakie są rozpatrywane przez poszczególne algorytmy, a użytkownik wraz ze zdobywanym doświadczeniem może stosować coraz bardziej wyszukane sposoby wydobywania wiedzy. Realnym udogodnieniem może być możliwość obrabiania danych z wykorzystaniem serwerów bazodanowych. Współpraca z produktami firm Oracle, Sybase i Informix powinna przebiegać bezproblemowo.

Wydaje się, że w ramach prowadzonych zajęć z "Automatycznego pozyskiwania wiedzy" celowe może być prezentowanie studentom na początku cyklu wykładów pakietów o podobnych możliwościach wizualizacji. Może to mocno zachęcić studentów do zgłębiania tego przedmiotu, oraz unaocznić im jak wiele można osiągnąć takimi narzędziami, gdzie uzyskanie tych samych wyników wykorzystując jedynie swą intuicję może być wprost niemożliwe. Pakiet MineSet umożliwia "dotknięcie" algorytmów pozyskiwania wiedzy, które przestają być tylko złożonymi pomysłami popartymi wzorami o wysokim stopniu abstrakcji, a stają się czymś namacalnym i realnym.

Osoba, która chciałaby odpowiedzieć sobie na pytanie "co to jest pozyskiwanie wiedzy", może zacząć właśnie od tego pakietu. Wersja MineSet Client 2.6 (moduły wizualizacji) dostępna jest za darmo dla ośrodków uniwersyteckich. MineSet Server 2.6 (moduł pozyskiwania wiedzy) można testować za darmo przez 30 dni. Niestety wersja 2.6 jest dostępna tylko na platformy Silicon Graphics (SGI). Zapowiadana jest wersja 3.0, która ma działać także na platformie Windows NT i będzie dostępna w drugiej połowie roku 1999.

1. Strona domowa programu MineSet http://www.sgi.com/software/mineset/
2. Machine Learning Library in C++ http://www.sgi.com/Technology/mlc/
3. Barry Becker, Ron Kohavi, Dan Sommerfield "Visualizing the Simple Bayesian Classifer" http://www.sgi.com/software/mineset/tech_info/vizNB.ps.gz
4. Ron Kohavi, Barry Becker, Dan Sommerfield, "Improving simple bayes" http://www.sgi.com/software/mineset/tech_info/impSBC.ps.gz
5. Pedro Domingos, Michael Pazzani "On the Optimality of the Simple Bayesian Classifier under Zero-One Loss" http://www.ics.uci.edu/~pedrod/mlj97.ps.gz