Miary probabilistyczne, sieci neuronowe, zmienne symboliczne



Pobieranie 6,83 Mb.
Strona1/28
Data02.11.2017
Rozmiar6,83 Mb.
  1   2   3   4   5   6   7   8   9   ...   28

Grzegorz Stawski




Probabilistyczne miary odległości, sieci neuronowe i cechy symboliczne.

Praca magisterska



wykonana pod kierunkiem Prof. Włodzisława Ducha

Katedra Metod Komputerowych

Uniwersytetu Mikołaja Kopernika

Toruń 2000



Spis treści.
1. Wstęp ..3

2. Podstawowe pojęcia ..4

3. Klasyczne algorytmy klasyfikacyjne. ..7

3.1 Odróżnianie obiektów ..7

3.2 Grupowanie obiektów ..9

3.4 Wady i ograniczenia klasycznych metod klasyfikacyjnych ..10

3.5 Nowe typy miar i algorytmów ..11

3.6 Klasyczna analiza dyskryminacyjna ..15

4. Algorytmy klasyfikacyjne taksonomii symbolicznej (algorytmy nieklasyczne) ..20

4.0 Przykłady symbolicznych algorytmów klasyfikacyjnych ..22

4.1 Metody podziałowe. Algorytm CLUSTER. ..22

4.2 Metody hierarchiczne. ..26

4.2.1 Algorytm COWEB. ..28

4.2.2 Wady algorytmu COWEB. ..31

4.3 Metody tworzące skupienia nierozłączne. ..32

4.3.1 Algorytm UNIMEM. ..32

4.3.2 Wady algorytmu UNIMEM. ..33

4.3 Drzewa klasyfikacyjne. ..34

4.4.1 Metody tworzące drzewa klasyfikacyjne. ..36

4.4.2 Proces tworzenia drzewa klasyfikacyjnego. ..37

4.4.3 Miary jakości podziału. ..38

4.4.4 Porządkowanie drzewa. ..40

4.4.5 Przykłady algorytmów: ID3 oraz C4. ..42

4.4.6 Kryterium SSV. 43

5. Zamiana symboli wartościami numerycznymi. ..45

5.1 Bazy danych użyte do testów. ..46

5.2 Test 1. ..47

5.3 Test 2. ..49

5.4 Test procedury PCA. ..50

6. Podsumowanie 54

7. Literatura. ..55

1.Wstęp.

Proces klasyfikacji jest podstawową czynnością poznawczą wykonywaną przez człowieka. Polega on na podziale obiektów na grupy i kategorie. Klasyfikację można traktować jako wstęp do myślenia, uczenia się i podejmowania decyzji. Można powiedzieć, że dzięki procesowi klasyfikacji dokonujemy odkryć naukowych, konstruujemy teorie naukowe i hipotezy.


Obecnie proste komputery o stosunkowo małej mocy obliczeniowej są używane do sterowania różnymi urządzeniami (lodówka, silnik samochodu, kuchenka mikrofalowa itp.). Do takiego sterowania wystarczy kilka prostych reguł, jednakże od komputerów sterujących przyszłych generacji (np. komputer kierowca samochodu) będziemy wymagali „pseudo myślenia”, tj. odpowiedniej reakcji na różne sytuacje, w których może znaleźć się urządzenie sterowane przez nasz komputer. W oprogramowaniu tego typu komputerów będą musiały się znaleźć wysoko wydajne algorytmy klasyfikacyjne.
Jednym z problemów, jaki stoi przed zastosowaniem sprawnych klasyfikatorów wywodzących się ze statystyki, sieci neuronowych czy uczenia maszynowego jest konieczność podawania danych w postaci numerycznej. Wady tej nie mają oparte na podobieństwie klasyfikatory typu najbliższych sąsiadów. Można w nich używać cech symbolicznych w sposób bezpośredni, korzystając z probabilistycznie określonych miar odległości.
Głównym celem tej pracy jest zbadanie możliwości zastosowania takich miar odległości dla dowolnych klasyfikatorów. Wymaga to określenia takich wartości numerycznych cech, które dają odległości obliczane za pomocą miary Euklidesowej identyczne jak odległości obliczane za pomocą miar probabilistycznych. Opracowano program komputerowy zamieniający symboliczne wartości atrybutów na wartości numeryczne i przetestowano go na szeregu bazach danych. Wstępne wyniki opublikowane zostały w pracy [1]
W poniższej pracy przedstawimy różne typy algorytmów klasyfikacyjnych, ich zalety oraz wady. W pierwszej części zaprezentowane zostaną klasyczne algorytmy klasyfikacyjne oraz próby usprawnienia tych algorytmów tak, aby mogły pracować ze zmiennymi opisanymi przy pomocy symboli. Kolejna część pracy poświęcona została różnym typom algorytmów nieklasycznych, potrafiących „obsługiwać” cechy symboliczne. W ostatniej części poniższej pracy zajmiemy się problemem przygotowania danych dla algorytmów klasyfikacyjnych, które mogą działać tylko na bazach danych, w których obiekty są opisane wartościami numerycznymi.

2. Podstawowe pojęcia.

Pojęcie klasyfikacji zostało po raz pierwszy wprowadzone przez biologów dla potrzeb semantyki roślin i zwierząt (pierwszą systematykę opracował Linneusz). Obecnie mówi się o całej dziedzinie nazwanej taksonomią, która zajmuje się zagadnieniami klasyfikacyjnymi. Termin taksonomia pochodzi od greckich słów: taksis (porządek) oraz nomos (prawo, zasada). Dziś metody klasyfikacyjne stosuje się w zupełnie innych dziedzinach niż biologia takich jak między innymi: nauki techniczne, fizyka, chemia, ekonomia, antropologia, psychologia, socjologia, lingwistyka i wiele innych.


Początkowo klasyfikacja opierała się na opisie cech przedstawicieli roślin i zwierząt i miała ona charakter wyłącznie opisowy (obiekty odróżniało się na podstawie ich jakościowego opisu). Obecnie algorytmy klasyfikacyjne są oparte wyłącznie na metodach ilościowych rozróżniania obiektów.
Jakie mamy rodzaje algorytmów klasyfikacyjnych? Są dwa rodzaje metod: metody tzw. klasyczne (ilościowe), oparte na statystyce oraz tzw. metody symboliczne (jakościowe). Są to zupełnie nowe metody, większość algorytmów tego typu powstała w ciągu ostatnich 10 lat i jest obecnie przedmiotem intensywnych badań. Następuje dalszy burzliwy rozwój znanych już metod jakościowych i dalsze poszukiwania nowych bardziej wydajnych metod.
W ramach samej klasyfikacji możemy w zależności od dostępności informacji wyróżnić dwa zagadnienia:
a) Klasyfikację wykorzystującą znane wzorce, nazywaną w statystyce analizą dyskryminacyjną – w tym przypadku znamy klasy, do których chcemy przydzielać obiekty z bazy treningowej. W terminologii cybernetycznej zagadnienie to nazywane jest rozpoznawaniem z nauczycielem. Algorytmowi klasyfikacyjnemu w procesie „uczenia” podawane są przykłady obiektów z jednoczesnym podaniem informacji, do której klasy należy dany obiekt przydzielić.
b) Klasyfikację bezwzorcową (zwaną w statystyce analizą skupień) – nic nie wiemy o strukturze klas i chcemy ją dopiero odkryć. Algorytm nie dysponuje żadnymi informacjami o klasach, do których należy przydzielić obiekty. Przydatne klasy muszą zostać przez algorytm dopiero skonstruowane.
W zależności od sposobu grupowania obiektów algorytmy klasyfikacyjne dzielimy na (podany poniżej podział jest prawdziwy zarówno do metod klasycznych jak i nieklasycznych):
a) Optymalizacyjno-iteracyjne, w których iteracyjnie dzieli się zbiór obiektów na grupy, przenosi się obiekty z jednej grupy do drugiej aż do uzyskania optymalnego podziału.
b) Hierarchiczne, w ramach których skupienia tworzą binarne drzewa, gdzie liście reprezentują poszczególne obiekty, a węzły - ich grupy. Skupienia wyższego poziomu zawierają w sobie skupienia niższego poziomu. Ta metoda jest bardzo często stosowana w algorytmach symbolicznych. Wśród hierarchicznych metod wyróżnia się dodatkowo:

- Metody aglomeracyjne, polegające na sukcesywnym łączeniu skupień (zakłada się, że początkowo każdy obiekt tworzy oddzielną klasę).


- Metody podziałowe, w ramach których początkowy zbiór obiektów (jedno skupienie) jest dzielony kolejno na dwie części aż do momentu, gdy każdy obiekt znajdzie się w oddzielnej klasie.
-Drzewa klasyfikacyjne budowane przez symboliczne algorytmy klasyfikacji wzorcowej.
c) Tworzące skupienia nierozłączne – w przypadku niektórych baz danych obiekty mogą należeć do więcej niż jednej grupy (klasy). Metoda ta jest stosowana przeważnie przez algorytmy symboliczne do problemów lingwistycznych (algorytmy do rozpoznawania tekstów i mowy).
Co uzyskujemy dzięki zastosowaniu algorytmów klasyfikacyjnych do baz danych? Algorytmy tego typu pozwalają odkryć „strukturę” baz danych. Wykryć zależności i korelacje występujące pomiędzy obiektami oraz cechami opisującymi te obiekty. Po wykonaniu takiej wstępnej analizy, dane są łatwe do interpretacji przez człowieka, łatwo zapisać prawa rządzące danymi w postaci prostej reguły lub wzoru np.. Algorytmy tego typu dają nam także możliwość łatwego i szybkiego budowania systemów eksperckich. Na podstawie już zebranych danych np. o klientach banku algorytmy klasyfikacyjne są w stanie odpowiedzieć na pytanie czy danemu klientowi warto udzielać pożyczki czy też nie.
Co jest przyczyną odchodzenia od metod klasycznych? Metody klasyczne dają dobre wyniki o ile operują wyłącznie na zmiennych określonych przy pomocy tzw. skal mocnych a większość baz danych, z jakimi mamy do czynienia w realnych przypadkach, zawiera dane różnych typów tzn. określonych przy pomocy różnych skal. Niektóre cechy opisujące obiekty mają charakter ciągły opisany przy pomocy liczb rzeczywistych (skala mocna, zmienna ilościowa) np. dla samochodów zużycie paliwa, przyspieszenie, itp. Inne z kolei będą opisywane za pomocą tzw. symboli (skala słaba, zmienna jakościowa) takich jak kolor, kształt itp. Użyta skala pomiarowa ma wpływ na ilość informacji dostarczaną przez zmienną. Dokładniejszy podział skal pomiarowych to:

-skale słabe:(a) nominalna, (b) porządkowa,



-skale mocne: (c) przedziałowa, (d) ilorazowa.
(a) Skala ta pozwala na najprostszy sposób rozróżniania obiektów. Do zmiennych wyrażonych w tej skali możemy stosować wyłącznie operatory , czyli możemy stwierdzać czy dwa obiekty są sobie równe czy też nie. Zmienne nominalne pozwalają jedynie na zaliczenie poszczególnych obiektów (jednostek, osobników itd.) do jednej z rozróżnialnych kategorii, których nie możemy uporządkować. Typowymi przykładami zmiennych nominalnych są płeć, rasa, kolor itp. Zmienne tego typu są zapisywane najczęściej przy pomocy symboli.
(b) Zmienne porządkowe pozwalają na rangowanie (ustawianie w określonym porządku dzięki operatorom < , >) elementów, które mierzymy. Element z wyższą rangą posiada cechę reprezentowaną przez mierzoną zmienną w większym stopniu, lecz ciągle nie można powiedzieć o ile większym.
(c) Zmienne przedziałowe z kolei pozwalają nie tylko szeregować (rangować) mierzone elementy, lecz również mierzyć różnice wielkości pomiędzy nimi. Na przykład temperatura mierzona w stopniach Celsjusza jest zmienną przedziałową. Możemy powiedzieć, że temperatura 40 stopni jest wyższa niż temperatura 30 stopni a wzrost temperatury od 20 do 40 stopni jest dwa razy większy niż od 30 do 40 stopni.
(d) Zmienne ilorazowe są podobne do zmiennych przedziałowych, lecz oprócz wszystkich cech skali przedziałowej, charakteryzuje je istnienie punktu absolutnego zera skali, dzięki czemu prawdziwe są stwierdzenia typu x jest dwa razy większe niż y. Typowymi przykładami skal ilorazowych są skale przestrzeni i czasu, również skala Kelvina pomiaru temperatury jest skalą ilorazową.
W przypadku danych mieszanych (różne skale pomiarowe, zmienne wyrażone przy pomocy symboli i liczb), aby móc zastosować klasyczny algorytm musimy dokonać ujednolicenia danych, wykonać zamianę symboli (skala słaba) na wartości numeryczne. W tym momencie pojawia się następujący problem. W jaki sposób dokonać takiej zamiany, aby wynik klasyfikacji był jak najlepszy? Dokonując zastąpienia symboli cyframi możemy zniszczyć związki występujące pomiędzy cechami opisującymi dane, przez co uzyskany wynik klasyfikacji może być błędny. Metody klasyczne są rozwijane od wielu lat, algorytmy opracowane w ramach tych metod są stosunkowo wydajne i stabilne. Na przeszkodzie stosowania tych metod stoją cechy opisane za pomocą symboli, które występują w większości obecnie gromadzonych baz danych.
Zamiana danych symbolicznych powinna uwzględniać globalne własności zbioru i korelacje występujące pomiędzy cechami opisującymi obiekty. Większość algorytmów klasycznych do odróżniana obiektów stosuje odległościowe miary podobieństwa obiektów, tak więc w przypadku nie uwzględnienia dwóch powyższych czynników otrzymujemy fałszywe odległości obiektów a co za tym idzie błędną klasyfikację lub słaby jej wynik. Metody klasyfikacji symbolicznej nie mają problemu z zmiennymi symbolicznymi, ponadto większość algorytmów tego typu dopuszcza nieznajomość wartości części atrybutów. Brak znajomości wartości niektórych atrybutów jest stosunkowo częstym zjawiskiem w rzeczywistych bazach danych (np. różne dane medyczne i psychiatryczne).



  1   2   3   4   5   6   7   8   9   ...   28


©operacji.org 2019
wyślij wiadomość

    Strona główna