POLITECHNIKA ŚLĄSKA WYDZIAŁ INŻYNIERII MATERIAŁOWEJ I METALURGII
Kierunek: Edukacja techniczno-informatyczna
Specjalność: -	Rodzaj studiów: zaoczne
praca inżynierska
Magdalena KRUPKA
Porównanie algorytmów dyskretyzacji cech jako proces wstępnego przetwarzania danych w problemach inteligencji obliczeniowej.
Kierujący pracą: doktor, Marcin BLACHNIK
Katowice, miesiąc wydania pracy, 2010 r.

Spis treści

1. Wprowadzenie

2. Omówienie zbioru danych

1. Obróbka pozapiecowa stali w pieco-kadzi podgrzewanej łukowo

3. Wstępne przetwarzanie danych

1. Selekcja cech

3.1.1 Metody selekcji cech

2. Normalizacja

3. Standaryzacja

4. Dyskretyzacja cech

1. Podział metod dyskretyzacji

1. Metody lokalne i globalne

2. Metody prymitywne i zaawansowane

3. Metody statyczne i dynamiczne

4. Metody kontrolowane i niekontrolowane

5. Metody łączące i dzielące

2. Struktura dyskretyzacji

5. Omówienie procesu dyskretyzacji

1. Podstawowe terminy

2. Przebieg procesu dyskretyzacji z jedną zmienną

6. Szczegółowe omówienie metod

1. Metody prymitywne : metoda równej częstości i równej szerokości

7. Algorytmy

1. Naive-Bayes

8. Wykonane badania

1. Wykorzystana sieć neuronowa

2. Wyniki

3. Wnioski

9. Podsumowanie

Literatura

Spis Tabel

1. --> Wprowadzenie [Author:M]

Wartości dyskretne odgrywają dużą rolę zarówno w wydobywaniu danych jak również są ważnym elementem w procesie odkrywania nowych dziedzin nauki operujących na zbiorach danych. Ogromną zaletą jest fakt, że z ich pomocą możemy w łatwy sposób zamienić wartości ciągłe w wartości porządkowe. Wiele nauk pokazuje nam jakie korzyści mogą płynąć z dyskretyzacji.[Author ID1: at Fri Sep 3 11:46:00 2010 ] Biorąc więc pod uwagę wszystkie wymienione wyżej korzyści, uważam, że przyszedł czas by zastanowić się i zbadać poszczególne metody dyskretyzacji aby dowiedzieć się czym one tak naprawdę się różnią, jakie są kluczowe elementy tego procesu oraz czy istnieje możliwość poprawy obecnego poziomu badań w tej dziedzinie.

Dane zazwyczaj przedstawione są w formacie mieszanym w skład którego wchodzą dane : nominalne, dyskretne lub ciągłe. Dane dyskretne oraz ciągłe są danymi porządkowymi natomiast dane nominalne - nie. Różnica pomiędzy danymi ciągłymi a dyskretnymi polega na tym, że dane dyskretne są ograniczone i ich liczba jest skończona, natomiast danych ciągłych może być nieskończenie wiele. Szczególnie różnicę tą możemy zauważyć podczas korzystania z klasyfikatora opartego na regułach/drzewach decyzji. Drzewa powstałe z wartości ciągłych są bardziej rozbudowane i czasami ciężko jest wybrać odpowiedni podział do poszczególnych węzłów. Dzięki wykorzystaniu dyskretyzacji otrzymane wyniki są dokładniejsze. To tylko jeden z przykładów dominacji danych dyskretnych nad danymi ciągłymi.

Jeśli w jednym zdaniu mielibyśmy przedstawić zalety dyskretyzacji cech z pewnością mówiłoby ono, że dyskretyzacja czyni naukę dokładniejszą oraz szybszą i jest ona kwantyzacją atrybutów ciągłych.

Celem pracy jest przeanalizowanie istniejących metod dyskretyzacji, standaryzacji tego procesu oraz porównanie znanych metody dyskretyzacji. Otrzymane dane z procesów dyskretyzacji zostaną zastosowane dla następujących klasyfikatorów : NaiwnyBayes oraz ID3.

Do badań wykorzystano ogólnodostępne dane z konkursu : ICAISC'08 [1].

Wyniki badań przedstawiono w postaci histogramów oraz tabel.

2. Omówienie zbioru danych

Zbiór danych pochodzi z konkursu ICAISC 2008. Znajdują się w nim takie informacje jak : ilość danego pierwiastka w stopniu % w danej stali podczas dwóch faz procesu metalurgicznego, temperatura, rodzaj stali, ilość dodawanego pierwiastka do danej stali.

1. Obróbka pozapiecowa stali w pieco-kadzi podgrzewanej łukowo

Najprostsza definicja stali mówi, że jest to plastycznie i cieplnie obrabiany stop żelaza z węglem (do ok. 2%) i innymi pierwiastkami, otrzymywany w procesach stalowniczych ze stanu ciekłego

--> Proces wytwarzania stali przebiega w czterech podstawowych etapach : [Author:M]

• --> Proces wielkopiecowy [Author:M] - do którego --> zaliczamy : [Author:M] roztopienie wsadu, odfosforowanie oraz świeżenie stali (redukcja zawartości - węgla, krzemu, manganu, fosforu i siarki).

• Wykańczanie stali (rafinacja) - proces ten ma na celu maksymalne obniżenie zawartości siarki, wstępne odlanie stali oraz uzyskanie zaplanowanego składu chemicznego.

• Odlewanie stali

Rysunek 1. Przebieg procesu wytwarzania stali.

Jedną z możliwości wytapiania stali jest wytapianie prowadzone w elektrycznym piecu łukowym. W piecu tym wsad nagrzewa się łukiem elektrycznym do temperatury z przedziału 1400 - 2000 C. Jak sugeruje wyżej opisany przebieg procesu wytapiania stali piec ten odpowiedzialny jest tylko za --> proces wielkopiecowy[Author:M] . Rafinacja oraz wykańczanie stali odbywa się poza piecem w tak zwanych procesach pozapiecowych.

Obróbkę kadziową realizuje się najczęściej w urządzeniu zwanym piecem kadziowym. Składa się on z kadzi ustawionej na wozie, pokryty z elektrodami, automatycznego systemu dozowania dodatków stopowych i maszyny do wprowadzania drutów rdzeniowych. dozowania dodatków stopowych. Piece kadziowe zajmują się również mieszaniem kąpieli gazem obojętnym,[Author ID2: at Thu Sep 2 23:40:00 2010 ] który przedmuchiwany jest przez korki gazo przepuszczalne umieszczone na dnie kadzi.

3. Wstępne przetwarzanie danych

1. Selekcja cech

Selekcja cech ma na celu rozwiązanie wszystkich problemów związanych z obszernymi bazami danych. Pomaga nam również wybrać podzbiór danych dzięki któremu otrzymane wyniki będą zbliżone do tych otrzymanych na oryginalnym zbiorze. Stwierdzono również, że wydajność większości algorytmów znacznie obniża się jeśli w zbiorze danych znajdują się niepotrzebne informacje, więc selekcja w tym przypadku jest również niezbędna.

1. Metody selekcji cech

Istnieje wiele metod selekcji cech, które można podzielić na:[Author ID2: at Thu Sep 2 23:42:00 2010 ] jedną z nich jest podział ze względu na przydatność wybranych cech: [Author ID2: at Thu Sep 2 23:42:00 2010 ]

• Metoda powłoki [Author ID2: at Thu Sep 2 23:41:00 2010 ]opakowana [Author ID2: at Thu Sep 2 23:41:00 2010 ]- metoda ta charakteryzuje się tym, że w procesie wyszukiwania cech bierze udział klasyfikator, oceniający przydatność danego podzbioru. Do głównych zalet tej metody możemy zaliczyć dokładność wyników. Wadą natomiast jest większa złożoność obliczeniowa --> . [Author:M]

• Metoda filtra - w odróżnieniu od metody powłoki, filtry działają niezależnie od klasyfikatora który w późniejszym etapie ma zostać użyty. Filtry podzielić możemy na te : działające w oparciu o cechy (przeprowadzają ważenie cech, wyszukują związek cech z klasą), filtrujące w oparciu o przypadek (wyszukują zarówno w przestrzeni cech jak i w przestrzeni przypadku)

• Metoda zagnieżdżona [Author ID2: at Thu Sep 2 23:44:00 2010 ]wbudowana [Author ID2: at Thu Sep 2 23:44:00 2010 ]- metoda ta charakteryzuje się tym, że proces selekcji zagnieżdżony zostaje wewnątrz modelu klasyfikującego.

1. Normalizacja

Przez pojęcie normalizacji rozumiemy przekształcenie wartości wejściowych, w taki sposób, że wartość uzyskana na wyjściu x_i', zawiera się w przedziale (0,1). Proces ten najczęściej wykorzystywany jest w uczeniu sieci neuronowych[Author ID2: at Thu Sep 2 23:45:00 2010 ]powinien być standardowa procedurę podczas realizacji procesu uczenia modeli regresji i klasyfikacji [Author ID2: at Thu Sep 2 23:45:00 2010 ]operujących na cechach ciągłych[Author ID2: at Thu Sep 2 23:46:00 2010 ].

Przekształcenie to określa się wzorem :

gdzie :

- średnia wartość cech x_i

x_max - wartość maksymalna spośród przypadków x_i

2. Standaryzacja

Przez pojęcie standaryzacji, rozumiemy proces obróbki danych wejściowych, uwzględniający rozkład wartości poszczególnych cech, --> sprowadzający dany[Author ID2: at Thu Sep 2 23:49:00 2010 ] zbiór danych[Author:M] do rozkładu Gaussowskiego N(0,1) charakteryzującego się [Author ID2: at Thu Sep 2 23:50:00 2010 ]-[Author ID2: at Thu Sep 2 23:49:00 2010 ] 0 jest [Author ID2: at Thu Sep 2 23:50:00 2010 ]wartością średnią równą 0 oraz [Author ID2: at Thu Sep 2 23:50:00 2010 ]a 1 to wartość[Author ID2: at Thu Sep 2 23:50:00 2010 ] odchyleniem[Author ID2: at Thu Sep 2 23:50:00 2010 ]a[Author ID2: at Thu Sep 2 23:50:00 2010 ] standardowym równym 1[Author ID2: at Thu Sep 2 23:50:00 2010 ]ego[Author ID2: at Thu Sep 2 23:50:00 2010 ]. Przekształcenie to określa się wzorem :

- średnia wartość cech x_i

- odchylenie standardowe cechy x_i

4. Dyskretyzacja cech

1. Podział metod dyskretyzacji

W początkowych pracach nad zagadnieniem dyskretyzacji stosowano takie motody podziału jak : equal-width (równej szerokości) oraz equal-frequency (równej częstości). Wraz z rozwojem technologii i potrzeby dokładniejszych oraz skuteczniejszych klasyfikacji powstały nowe, bardziej rozbudowane metody przeprowadzania tego procesu. W chwili obecnej wyróżniamy następujące metody podziału procesu dyskretyzacji : metody lokalne i globalne, metody prymitywne i zaawansowane, metody statyczne i dynamiczne, metody kontrolowane i niekontrolowane oraz[Author ID2: at Thu Sep 2 23:52:00 2010 ],[Author ID2: at Thu Sep 2 23:52:00 2010 ] metody łączące i dzielące.

1. Metody lokalne i globalne

Metody lokalne - wykonują dyskretyzację w zlokalizowanym obszarze przestrzeni przykładu (podzespół przykładów).

Metody globalne - używa całej dostępnej przestrzeni przykładu do procesu dyskretyzacji.

2. Metody prymitywne i zbalansowane

Metody prymitywne (proste) - nie uwzględniają rozkładu wartości klas ani atrybutów, ale przeprowadzają podział wartości atrybutów na ustaloną z góry liczbę przedziałów (equal-width, equal-fraquency).

Metody zbalansowane - są to metody które dopasowują sposób dyskretyzacji do konkretnego zbioru danych.

3. Metody statyczne i dynamiczne

Metody statyczne - są to algorytmy które dla każdego atrybutu określają maksymalna liczbę przedziałów, proces ten jest niezależny od innych atrybutów.

Metody dynamiczne - różnią się od metod statycznych tym, że biorą pod uwagę zależności pomiędzy poszczególnymi atrybutami. Szukają więc możliwych liczb przedziałów dla wszystkich atrybutów jednocześnie.

4. Metody kontrolowane i niekontrolowane

Metody kontrolowane - biorą one pod uwagę klasę, którą wykorzystują do znalezienia właściwych przedziałów (które powstały przez punkt odcięcia).

Metody niekontrolowane - metoda ta zauważalna jest w takich procesach dyskretyzacji jak metody prymitywne, equal width i equal fraquency. W metodach tych odbywa się podział na określone przedziały. Minusem tej metody jest fakt, że w przypadku różnorodnych wartości ciągłych wyniki nie są zadowalające.

5. Metody dzielące i łączące

Metody dzielące - inaczej zwane zstępującymi, działają w taki sposób, że rozpoczynają swoje działanie od danego przedziału i obejmują całą przestrzeń danego atrybutu, dokonują również jej kolejnych podziałów wraz z postępem procesu dyskretyzacji.

Metody łączące - inaczej zwane wstępującymi - swoje działanie zaczynają od przedziałów jednoelementowych, które odpowiadają konkretnym wartościom atrybutu. Następnie łączą one wybrane sąsiednie przedziały.

2. Struktura dyskretyzacji

Na niżej przedstawionym rysunku (rys.2) widać wyraźne różnice pomiędzy metodami dyskretyzacji. Szczególnie jeśli chodzi o wykorzystywanie problemu klas.

--> Początkowo dokonujemy podziału czy dana metoda jest łącząca czy dzieląca.

Później w obu tych grupach robimy podział na metody kontrolowane i niekontrolowane. Następnie grupujemy razem metody wg takich czynników jak sortowanie, zależność, entropia czy dokładność. [Author:M]

W tabeli 1 przedstawiono natomiast użycie różnych miar w różnych metodach dyskretyzacji. ( - oznacza, że w danej kategorii konkretna miara nie jest dostępna)

Rysunek 2. Hierarchiczna struktura dyskretyzacji

Tabela 1. Użycie odpowiednich miar dla różnych metod

Dzielenie	Łączenie
Entropia	-
Sortowanie	-
Dokładność	-
Zależność	zależność

5. Omówienie procesu dyskretyzacji

1. Podstawowe terminy

Atrybut - (zmienna, cecha) - mianem tym określamy pojedynczą kolumnę danego zbioru danych. Mogą przybierać wartości dyskretne, ciągłe lub nominalne.

Przypadek - (przykład, wiersz, punkt danych) - termin ten odnosi się do pojedynczego wiersza w zbiorze danych, uwzględniając wszystkie atrybuty.

Punkt odcięcia - (cut point) - mianem tym określamy wszystkie wartości rzeczywiste w przestrzeni ciągłych wartości, które dzielą zakres danych na przedziały.

2. Przebieg procesu dyskretyzacji z jedną zmienną.

-->
[Author:M]

Rysunek 3. Proces dyskretyzacji

Proces dyskrtyzacji składa się z czterech głownych etapów, w skład których wchodzą :

• Sortowanie - malejąco lub rosnąco

• Ocana (Szacowanie) - wybór Cut-Point'ów, przedziałów sąsiadujących; oszacowanie miary; miara zadowalająca.

• Dzielenie/Łączenie - dzielenie lub łączenie przedziałów

• Zatrzymanie - określa kiedy proces dyskretyzacji zostanie zatrzymany

6. Szczegółowe omówienie metod

1. Metody prymitywne : equal-width and equal-frequency

Metody równej szerokości i równej częstości są to stosunkowo proste i łatwe do zaimplementowania metody.

Muszą jednak zostać spełnione odpowiednie warunki. Między innymi --> atrybut k[Author:M] , musi być ustalony odgórnie. Jest to problematycznie głównie z tego względu, że nie wiemy jaki powinien on być - to też zazwyczaj ustalenie go przebiega metodą prób i błędów lub też wybieramy go losowo. Kolejnym minusem jest czułość na wartości odstające które mogą znacząco wpłynąc na przebieg procesu dyskretyzacji, np. prowadząc do niepotrzebnego rozciągnięcia się przedziałów. Dlatego w tym wypadku najlepiej jest odrzucić ze zbioru wszystkie takie wartości.

Wracając jednak do szegółowego opisu wyżej wymienionych metod jak już wspomniałam zakres atrybutów ciągłych musi zostać podzielony na określoną liczbę przedziałów (k) o równej szerokości (w przypadku metody równej szerokości). W wyniku czego każdemu uzyskanemu przedziałowi przypisana jest jedna wartość dyskretna. W przypadku metody równej częstości końcowe wartości przedziałów dobieramy w taki sposób by każdemu z nich odpowiadała możlwie taka sama liczba przykładów.

W przypadku obu tych metod za jedyne kryterium zatrzymania przyjmuje się liczbę przedziałów (k).

7. Algorytmy

7.1 Naive Bayes

Naiwny klasyfikator Bayes'a

Naiwny klasyfikator Bayes'a jest to jedna z metod uczenia maszynowego, którą stosujemy do rozwiązywania problemów sortowania.

Zadaniem tego klasyfikatora jest przyporządkowanie każdego nowego przypadku do jednej z istniejących klas decyzyjnych. Warunkiem jedynak jest to, że zbiór klas decyzyjnych musi być skończony i zdefiniowany z góry.

W tym przypadku każdy przykład uczący opisany jest za pomocą zbioru atrybutów warunkowych {Ai} oraz jednego atrybutu decyzyjnego D.

W odróżnieniu od innych technik, nie zakłada się z góry, że każdy przykład opisany jest przy pomocy tego samego zbioru {Ai}.

Według teorii Bayes'a, klasą najbardziej prawdopodobną, do której nowy obiekt (o n-atrybutów warunkowych Ajn=vjn) zostanie przypisany, jest klasa Di, czyli taka, która zmaksymalizuje prawdopodobieństwo warunkowe P (Di | vjn). Klasę tą oznaczamy jako dMAP (maximum a posterori).

gdzie :

• P(h) = prawdopodobieństwo zajścia hipotezy h

• P(D) = prawdopodobieństwo otrzymania zbioru treningowego D

• P(h|D) = prawdopodobieństwo h pod warunkiem, że D jest dany

• P(D|h) = prawdopodobieństwo D przy założeniu, że h zachodzi

Bibliografia

• Dr inż. Miroslaw Łomzik „kurs europejskiego inżyniera spawalnika (ewe) Instytut spawalniczy w gliwicach

• najlepsze dostępne techniki (bat) wytyczne dla produkcji stali stalownie elektryczne z odlewaniem stali ministerstwo środowiska

warszawa, luty 2005 r.

• John H.G. Kohavi R. Peger K. Irrelevant features and the subset selection

problem. International Conference on Machine Learning, pages 121{129, 1994.

• Blum A.I. Langley P. Selection of relevant features and examples in machine learning. Arti_cial Intelligence, pages 245{271, 1997.

• Discretization: An Enabling Technique HUAN LIU, FARHAD HUSSAIN, CHEW LIM TAN,MANORANJAN DASH

• A Hybrid FilterWrapper Approach of Feature Selection Using Information Theory - Sebban, Nock

• On Discretization as a Preprocessing Step For Supervised Learning Models Dan Ventura April 1995

Skrypt:

clc;

id = 1;

ux = unique(data(:,id));

clear wyn;

wyn = zeros(1,length(ux));

for i=1:length(ux)

wyn(i) = sum(data(:,id)==ux(i));

end;

disp([ux(:)'; wyn]);

max(wyn)

idd = data(:,1) == 65;

tdata=data(idd,:);

mn = tdata(:,74);

hist(mn,30);

ttdata = tdata;

ttdata(:,[1 2 72 73 75 : 82]) = [];

tttdata = ttdata;

tttdata(isnan(tttdata(:,2)),:) = [];

corr(tttdata(:,2),tttdata(:,end))

for i = [1 3:size(ttdata,2)-1]

cc(i) = abs(corr(ttdata(:,i),ttdata(:,end)));

end;

cc(:)'

Dr inż. Miroslaw Łomzik „kurs europejskiego inżyniera spawalnika (ewe) Instytut spawalniczy w gliwicach

http://www.zainstalujsie.pl/edukacja/produkcja-stali-%E2%80%93-historia-i-przeglad-cz-xii, 10.07.2010r

najlepsze dostępne techniki (bat) wytyczne dla produkcji stali stalownie elektryczne z odlewaniem stali ministerstwo środowiska

warszawa, luty 2005 r.

John H.G. Kohavi R. Peger K. Irrelevant features and the subset selection

problem. International Conference on Machine Learning, pages 121{129, 1994.

Blum A.I. Langley P. Selection of relevant features and examples in machine

learning. Arti_cial Intelligence, pages 245{271, 1997.

Discretization: An Enabling Technique HUAN LIU, FARHAD HUSSAIN, CHEW LIM TAN,MANORANJAN DASH

http://www.cs.put.poznan.pl/kkrawiec/snumlab/lab5teoria.htm 15.07.2010r

Tu gdzies przydałby się opis typów zmiennych/cech tzn że mamy zmienne ilościowe, rzeczywiste porządkowe, oraz jakościowe czyli bez porządku tylko zbiór symboli. To musiałoby być jasno i przejrzyście opisane

Tutaj przydałby się odnośnik do literatury

Proces wielkopiecowy to jedna z możliwości te dane dotyczą procesu roztapiania stali ze złomu i dotyczą pieca elektrołukowego a nie wielkopiecowego

Znaki interpunkcyjne zawsze łączy się z ostatnim wyrazem

?

Referencje umieszcza się na końcu pracy a nie jako przypis dolny

Nie zbiór danych tylko każdą z cech zbioru danych

To brzmi jakoś dziwnie

Co to jest dzielenia/łączenie atrybutów

Co to jest atrybut k

---