Metody odkrywania wiedzy: wykład 8 Dyskretyzacja atrybutów ciągłych














Metody odkrywania wiedzy: wykład 8
Dyskretyzacja atrybutów ciągłych
Paweł Cichosz
Date: 2001/2002



Wykład jest poświęcony najbardziej podstawowemu przekształceniu
przestrzeni atrybutów: dyskretyzacji atrybutów ciągłych (a przy okazji
również agregacji atrybutów porządkowych). Przedstawione będą typowe
metody dyskretyzacji stosowanej jako wstępne przetwarzanie danych do
uczenia się klasyfikacji.




Motywacja



Podczas gdy atrybuty ciagłe występują dość często w realnych
dziedzinach, w których zastosowanie metod odkrywania wiedzy mogłoby
być bardzo obiecujące, niektóre popularne algorytmy uczenia się pojęć
nie mogą być wówczas wykorzystane lub ich wykorzystanie wiąże się z
pewnymi trudnościami. Tak jest chociażby w przypadku algorytmów
uczenia się reguł, kiedy można wprawdzie wprowadzić selektory
przedziałowe i nierównościowe dla atrybutów ciągłych, lecz związane z
tym komplikacje utrudniają zachowanie wszystkich właściwości, jakie
algorytm ma dla atrybutów nominalnych. Istnieją też inne algorytmy,
takie jak omawiane w algorytmy indukcji drzew decyzyjnych, które ze
swej istoty potrafią sobie radzić również z atrybutami ciągłymi bez
dodatkowych rozszerzeń, lecz na ogół występowanie takich atrybutów
powoduje znaczne zwiększenie obliczeniowego kosztu uczenia się i
złożoności uzyskiwanych hipotez.


Dyskretyzacja atrybutów ciągłych polega na zastąpieniu każdego z nich
atrybutem o wartościach dyskretnych, odpowiadających pewnym
przedziałom ciągłych wartości oryginalnego atrybutu. Oczywiście
przedziały takie są uporządkowane, więc w wyniku dyskretyzacji
otrzymujemy zamiast atrybutu ciągłego atrybut porządkowy o skończonej
liczbie wartości -- niezbyt wielkiej i dobieranej zwykle tak, aby
stanowiła dobry kompromis między dokładnością reprezentowania
informacji zawartej w wartościach oryginalnego atrybutu a złożonością
procesu uczenia się i uzyskiwanych hipotez.


Dla algorytmów, które nie mają mechanizmów przetwarzania atrybutów
ciągłych, dyskretyzacja jest nieodzownym warunkiem stosowalności do
dziedzin, w których atrybuty takie występują. Ponieważ dla
algorytmów, które takie mechanizmy mają, są one często okupione
pewnymi istotnymi niedogodnościami, dyskretyzacja również dla nich
może być bardzo pożyteczna. Można wskazać następujące argumenty na
poparcie tej tezy:


poprawa efektywności obliczeniowej procesu uczenia się:
zastąpienie wielu wartości atrybutu ciągłego niewielką liczbą
wartości zdyskretyzowanych może znacznie obniżyć nakłady obliczeń,

zwiększenie prostoty i czytelności hipotez: hipotezy
bezpośrednio wykorzystujące atrybuty ciągłe mogą być złożone
i nieczytelne, dyskretyzacja zaś może prowadzić do hipotez
prostszych i łatwiejszych do interpretacji,

poprawa dokładności hipotez: dyskretyzacja atrybutów ciągłych
może korzystnie wpływać na dokładność generowanych hipotez,
zwłaszcza w przypadku nie w pełni poprawnych danych trenujących,
ponieważ jest pewnym sposobem zapobiegania nadmiernemu dopasowaniu.






Dyskretyzacja a agregacja



Niemal wszystko, co będzie tu powiedziane o dyskretyzacji atrybutów
ciągłych, można odnieść także do agregacji atrybutów porządkowych.
Polega ona na zastąpieniu takiego atrybutu innym atrybutem porządkowym
o mniejszej liczbie wartości w taki sposób, że wszystkie wartości
nowego atrybutu odpowiadają parami rozłącznym podzbiorom
przeciwdziedziny oryginalnego atrybutu, przy czym każdy taki podzbiór
zawiera kolejne wartości z tej przeciwdziedziny według określonej na
niej relacji porządku. Umożliwia to nazywanie takiego podzbioru
przedziałem, którego końcami są ,,najmniejsza'' i ,,największa''
według tej relacji należąca do niego wartość. Wówczas należą do niego
także wszystkie wartości pośrednie. Skoro dyskusja poświęcona
dyskretyzacji będzie się koncentrować, jak zobaczymy, wokół zasad
wyznaczania podziału przeciwdziedzin atrybutów na przedziały, przy
odpowiednio zmodyfikowanym rozumieniu przedziałów dotyczy także
agregacji atrybutów porządkowych.




Rodzaje dyskretyzacji



Znane metody dyskretyzacji można podzielić na kilka rodzajów.
Najbardziej oczywisty jest podział na metody prymitywne albo naiwne,
które przy dyskretyzacji nie uwzględniają rozkładu wartości atrybutów
i kategorii w danych (dzielą zakres wartości atrybutu na ustaloną w
pewien arbitralny sposób liczbę równych podprzedziałów), i na metody
zaawansowane, które dopasowują sposób dyskretyzacji do zbioru
trenującego. Wśród bardziej interesujących metod zaawansowanych można
dalej wprowadzić podział:


na metody lokalne i globalne,

na metody bez nadzoru i z nadzorem,

na metody zstępujące i wstępujące.






Dyskretyzacja lokalna i globalna



Metody globalne bezpośrednio odpowiadają nieformalnemu określeniu
dyskretyzacji, jakie zostało podane wyżej: każdy atrybut ciągły,
niezależnie od innych atrybutów, jest zastępowany przez odpowiedni
atrybut porządkowy, którego wartości odpowiadają przedziałom wartości
atrybutu ciągłego. Zależność zdyskretyzowanego atrybutu od atrybutu
oryginalnego jest jednoznacznie wyznaczona przez przedziały
dyskretyzacji, które są globalne, czyli takie same dla wszystkich
przykładów dziedziny. W przypadku metod lokalnych zakres wartości
atrybutu ciągłego może być dzielony na przedziały na różne sposoby w
różnych obszarach dziedziny, wyznaczonych przez wartości innych
atrybutów. Zatem nowy, zdyskretyzowany atrybut zależy funkcyjnie nie
tylko od oryginalnego atrybutu ciągłego, lecz także od niektórych lub
wszystkich pozostałych atrybutów. Wówczas wartość dyskretną
odpowiednią dla danej wartości atrybutu ciągłego pewnego przykładu
można znaleźć tylko uwzględniając wartości pozostałych atrybutów dla
tego przykładu, gdyż to one wyznaczają lokalny zbiór przedziałów
dyskretyzacji. Dalej interesować nas będzie bardziej uniwersalna i
prostsza w realizacji dyskretyzacja globalna.




Dyskretyzacja z nadzorem i bez nadzoru



W przypadku dyskretyzacji z nadzorem są znane etykiety kategorii
przykładów i są one uwzględniane podczas dyskretyzacji. Pozwala to
tak dobrać przedziały dyskretyzacji, aby było możliwe jak najlepsze
reprezentowanie pojęcia docelowego za pomocą nowego zestawu atrybutów.
Metody bez nadzoru nie uwzględniają informacji o kategoriach
przykładów i wskutek tego tracą szansę na zoptymalizowanie podziału
zakresów wartości atrybutów ciągłych na przedziały dyskretyzacji ze
względu na pojęcie, do którego reprezentowania te atrybuty mają być
używane. Dalej skoncentrujemy się na metodach dyskretyzacji z
nadzorem.




Dyskretyzacja zstępująca i wstępująca



Podział na dyskretyzację zstępującą i wstępującą ma bardziej
techniczny charakter. Nie ma on związku z rodzajem informacji, jakie
są brane pod uwagę przy dyskretyzacji, lecz ze sposobem działania
algorytmów dokonujących dyskretyzacji. Dyskretyzacja zstępująca polega
na tym, że cała przeciwdziedzina dyskretyzowanego atrybutu --
tworząca początkowo jeden przedział -- jest dzielona na podprzedziały
za pomocą wybieranych kolejno wartości progowych. W przypadku
dyskretyzacji wstępujące rozpoczynamy od podziału przeciwdziedziny
atrybutu na wiele małych przedziałów, z których każda zawiera jedną
wartość tego atrybutu, a następnie wybrane przedziały są łączone w
większe.




Notacja



Wygodnie będzie prezentować w szczegółach metody dyskretyzacji
posługując się pewną systematyczną notacją do oznaczania przedziałów
dyskretyzacji i ich końców. Rozważmy dowolny atrybut ciągły

. Przeciwdziedzina może być zbiorem liczb
rzeczywistych bądź pewnym zawartym w nim przedziałem. Na ogół
nie będzie potrzeby tych dwóch przypadków w jawny sposób rozróżniać,
chociaż należy zapewnić możliwość uwzględnienia obydwu tak w prostej
notacji, jaką tu wprowadzimy, jak i przede wszystkim w opisywanych za
jej pomocą metodach dyskretyzacji.


Interesuje nas podział zbioru na skończoną liczbę przedziałów,
których zbiór oznaczymy przez
. Przedziały wchodzące w
skład tego zbioru muszą spełniać następujące naturalne warunki:




,

(1)


,

(2)


czyli muszą pokrywać całą przeciwdziedzinę atrybutu i być parami
rozłączne. Przyjmiemy ponadto, że każdy przedział
,
którego oba końce są skończone, ma postać




,

(3)


czyli będziemy zakładać, że przedziały są prawostronnie domknięte.
Jest to tylko przyjęta dla wygody konwencja, która sama w sobie nie ma
zasadniczego znaczenia. Jeśli przeciwdziedzina jest nieograniczona
z lewej strony, to do zbioru
musi należeć dokładnie
jeden przedział
. Aby takiego przypadku nie
traktować w specjalny sposób, przyjmiemy wówczas
.
Podobnie, jeśli zbiór nie jest ograniczony z prawej strony, to do

należy dokładnie jeden przedział

. Również w tym przypadku możemy przyjąć

i umówić się, że przedział

jest wówczas traktowany tak jak przedział

.


W podobny sposób możemy oznaczyć końce przedziału, którym jest
przeciwdziedzina , przyjmując
i
dopuszczając w razie potrzeby
lub

. Założenie o tym, że zbiór , o ile jest
ograniczony z obu stron, jest przedziałem domkniętym prawostronnie, ma
znaczenie wyłącznie techniczne -- umożliwia utrzymanie formalnej
poprawności niektórych dalszych wywodów bez rozważania wyjątków.


Dla dowolnego zbioru przykładów
, atrybutu
i przedziału
przydadzą się nam następujące
oznaczenia:




,

(4)


,

(5)


przy czym drugie oznaczenie ma sens, jeśli jest ustalone
pewne pojęcie docelowe
i .


Niekiedy -- przede wszystkim w przypadku metod dyskretyzacji
zstępującej -- zamiast odwoływać się do przedziałów, wygodniej jest
mówić bezpośrednio o ich końcach, czyli o wartościach progowych, za
pomocą których jest podzielona przeciwdziedzina atrybutu . Zbiór
przedziałów
może być reprezentowany za pomocą zbioru
wartości progowych:




.

(6)


Jak widać, zawiera wszystkie końce przedziałów z

poza tymi, które bezpośrednio ograniczają zbiór . W
szczególności mogą to być i , co zapewnia, że w
każdym przypadku wszystkie elementy zbioru są wartościami
skończonymi, z których każda należy do przeciwdziedziny atrybutu. Dla
atrybutu
i zbioru wartości progowych

wprowadzimy oznaczenia:




,

(7)


,

(8)


,

(9)


,

(10)


przy czym ponownie dwa ostatnie zakładają, że jest określone pewne
ustalone pojęcie docelowe
i .




Prymitywne metody dyskretyzacji



Prymitywne metody dyskretyzacji, mimo ich słabości, są wciąż często
stosowane, a do niedawna stanowiły wręcz dominujące podejście. Są one
bardzo proste, łatwe do implementacji i obliczeniowo tanie. Dwie
podstawowe metody prymitywne to dyskretyzacja według równej szerokości
i dyskretyzacja według równej częstości. Są to metody globalne bez
nadzoru.




Dyskretyzacja według równej szerokości



Jest to najprostsza metoda dyskretyzacji. Zakres wartości
dyskretyzowanego atrybutu ciągłego jest dzielony na ustaloną liczbę
przedziałów o jednakowej szerokości. Każdemu przedziałowi odpowiada
następnie jedna wartość dyskretna. Jeśli przeciwdziedzina
dyskretyzowanego atrybutu jest ograniczonym obustronnie
przedziałem
, to w wyniku dyskretyzacji
według równej szerokości na podprzedziałów powstaną wartości
porządkowe, odpowiadające przedziałom

dla
,
przy czym
jest szerokością
przedziału. Powstaje zatem zbiór przedziałów

taki, że:




,

(11)




(12)


dla każdego
.


Sytuacja tylko nieznacznie się komplikuje, gdy przeciwdziedzina
jest nieograniczona z jednej lub obu stron, czyli gdy

lub
. Czasem przeciwdziedzina
atrybutu nie jest znana i nie ma innego wyjścia, niż przyjąć, że jest
nią cały zbiór . Wówczas należy przyjąć z jednej lub z obu stron
skończone ograniczenie tej przeciwdziedziny na podstawie wartości
atrybutu występujących w zbiorze trenującym. Możemy więc ustalić:






(13)




(14)


i utworzyć zbiór przedziałów
tak, jakby
przeciwdziedziną atrybutu był przedział

. Następnie ten zbiór można uzupełnić o
przedział
, jeśli
, i o
przedział
, jeśli
, w celu
uwzględnienia możliwości, że w dziedzinie są przykłady o wartościach
atrybutu mniejszych lub większych niż odpowiednio minimalna i
maksymalna jego wartość występująca w zbiorze trenującym. Może więc
powstać lub zamiast przedziałów.




Dyskretyzacja według równej częstości



Podobną do poprzedniej, lecz w większym stopniu uwzględniającą
charakter zbioru danych metodą dyskretyzacji jest dyskretyzacja według
równej częstości. Również tym razem zakres wartości atrybutu ciągłego
jest dzielony na ustaloną z góry liczbę przedziałów, jednak obecnie
nie są to przedziały o równej szerokości. Ich końce dobiera się w ten
sposób, aby każdemu z nich odpowiadała (możliwie) taka sama liczba
przykładów trenujących. Jeśli więc zbiór trenujący liczy
przykładów, to dyskretyzacja według równej częstości na
podprzedziałów doprowadzi do przyporządkowania wartości dyskretnych
przedziałom o końcach dobranych tak, aby w każdym z nich znalazły się
wartości dyskretyzowanego atrybutu dla (średnio)

przykładów. W przypadku idealnym powinniśmy w ten sposób uzyskać zbiór
przedziałów
taki, że dla każdego

zbiór zawiera dokładnie
przykładów,
lecz nie zawsze będzie to możliwe, gdyż niektóre wartości atrybutu
mogą występować dla wielu przykładów.


W celu dokonania dyskretyzacji tą metodą zbiór trenujący należy
podzielić na możliwie równolicznych podzbiorów

, zachowując uporządkowanie wartości atrybutu ,
czyli w taki sposób, aby dla dowolnych wartości
był
spełniony warunek




.

(15)


Następnie pozostaje dobrać końce przedziałów dyskretyzacji w ten
sposób, aby każdy z nich zawierał wartości atrybutu w miarę
możliwości z tylko jednego spośród tych podzbiorów. Powinien wobec
tego powstać zbiór przedziałów

taki, że
, przy czym zgodnie z wcześniejszą uwagą
uzyskanie takiej równości dla każdego podzbioru nie zawsze będzie
możliwe. Jako wartości progowe, wyznaczające przedziały jak zwykle
najrozsądniej jest brać pod uwagę środki przedziałów między kolejnymi
występującymi w zbiorze trenującym wartościami dyskretyzowanego
atrybutu. Zauważmy, że tym razem nie ma znaczenia, czy wartości

i
są skończone, czy nie. Tak czy inaczej
w 
znajdzie się jeden przedział, którego lewym końcem
jest
, i jeden przedział, którego prawym końcem jest

.




Dyskretyzacja zstępująca



Podejście zstępujące często stosowane do dyskretyzacji z nadzorem,
przypomina sposób postępowania z atrybutami ciągłymi przy zstępującej
konstrukcji drzew decyzyjnych, lecz tu zostanie przedstawione jako
metoda globalna. Polega ona na podziale przeciwdziedziny
dyskretyzowanego atrybutu na podprzedziały za pomocą wartości
progowych. Zgodnie z istotą podejścia zstępującego początkowo
przyjmuje się cały zakres wartości jako jedyny przedział.
Umieszczenie pierwszej wartości progowej dzieli go na dwa
podprzedziały, z których każdy może być następnie podzielony na
kolejne dwa podprzedziały itd.




Schemat dyskretyzacji zstępującej



Nie będziemy, przedstawiając schemat dyskretyzacji zstępującej w
ogólnej postaci, zakładać, czy dotyczy on dyskretyzacji z nadzorem,
czy bez nadzoru, a więc czy dostępne i używane są etykiety przykładów,
czy też nie. Przyjmiemy, że algorytm otrzymuje zbiór trenujący ,
przy czym mogą także (lecz nie muszą) być znane etykiety przykładów
tego zbioru dla pewnego pojęcia docelowego , i ma za zadanie
dokonać dyskretyzacji wskazanego ciągłego atrybutu . Podział
zakresu jego wartości na przedziały będzie reprezentowany przez zbiór
wartości progowych wyznaczających ten podział. Na każdym poziomie
rekurencji następuje wybór jednej nowej wartości progowej, pewien
przedział na dwa podprzedziały, a następnie ten sam algorytm zostanie
rekurencyjne wywołany dla każdego z nich. Za każdym razem zbiór
przykładów branych pod uwagę zawiera tylko te przykłady, dla których
wartość dyskretyzowanego atrybutu należy do przedziału, który ma być
obecnie podzielony. W szczegółowej postaci schemat dyskretyzacji
zstępującej przedstawia poniższy algorytm:







Parametrami funkcji
są zbiór
przykładów oraz atrybut, którego wartości występujące w tym zbiorze są
poddawane dyskretyzacji. Przy pierwszym wywołaniu zbiorem tym jest
cały zbiór trenujący . Wynikiem funkcji jest zbiór wartości
progowych, które wyznaczają podział przeciwdziedziny atrybutu na
podprzedziały. Konkretyzacja przedstawionego schematu może nastąpić
przez zdefiniowanie dwóch podstawowych operacji, do których się on
odwołuje: podjęcia decyzji o zakończeniu dalszego podziału przedziałów
na podprzedziały, za co odpowiada funkcja
,
oraz o wyborze wartości progowej do podziału, czym zajmuje się funkcja

. Jeśli pierwsza z nich da wynik negatywny,
czyli dzielenie przedziałów nie zostanie zatrzymane, a w wyniku
drugiej zostanie wybrana wartość progowa , to następują dwa
wywołania rekurencyjne algorytmu, mające na celu dokonanie ewentualnych
dalszych podziałów dla dwóch podprzedziałów wyznaczonych przez
. W tym celu zbiór przykładów jest dzielony na
dwa podzbiory przekazywane do tych wywołań, składające się odpowiednio
z tych przykładów z , dla których wartość dyskretyzowanego atrybutu
znajduje się poniżej oraz powyżej wartości progowej (lub
jest jej równa). Obecnie pozostaje omówić sposoby konkretyzacji
kryterium stopu i wyboru progu, które przekształcają schemat
zstępującej dyskretyzacji w konkretne algorytmy.




Wybór wartości progowej



Można przyjąć, że pożądana dyskretyzacja
powinna charakteryzować się możliwie małą liczbą przedziałów, gdyż
atrybuty o niewielkiej liczbie wartości są z punktu widzenia
algorytmów uczenia się najdogodniejsze, ale powinna przy tym umożliwiać
rozróżnianie przykładów, które powinny być rozróżniane w procesie
uczenia się. W przypadku dyskretyzacji z nadzorem z całą pewnością
powinny być rozróżniane przykłady różnych kategorii. Oczywiście
trywialna dyskretyzacja, tworząca po jednym przedziale dla każdej
wartości atrybutu ciągłego, jest nie do prześcignięcia pod względem
właściwości dyskryminujących, czyli rozróżnialności przykładów. Jeśli
jednak przedziałów ma być możliwie niewiele, należy dążyć do tego, aby
kryterium stopu zostało spełnione możliwie wcześnie, czyli dla
możliwie dużych przedziałów. Aby do tego doprowadzić, można przy
wyborze wartości progowych kierować się równomiernością rozkładu
kategorii przykładów o wartościach dyskretyzowanego atrybutu w
poszczególnych przedziałach. Jeśli jest to rozkład stosunkowo
równomierny, czyli przykłady różnych kategorii występują w
przedziałach w zbliżonej liczbie, to przypisane następnie tym
przedziałom wartości dyskretne będą miały słabe właściwości
dyskryminujące. Zależy nam raczej na tym, aby w zbiorach tych pewne
kategorie wyraźnie dominowały, gdyż wówczas odpowiednie wartości
dyskretne będą bardziej użyteczne do reprezentowania pojęcia
docelowego.


Z tej dyskusji wynika, że do wyboru wartości progowej mogą być
wykorzystywane miary nierównomierności rozkładu, takie jak entropia.
Przyjmiemy, że wybierana jest wartość progowa minimalizująca ważoną
entropię zbioru przykładów ze względu na podział zakresu wartości
atrybutu za pomocą wartości progowej , która jest
zdefiniowana następująco:




,

(16)


przy czym
i
oznaczają entropię
przykładów z , dla których atrybut ma wartość odpowiednio
poniżej i powyżej wartości progowej . Entropie te są określone
w następujący sposób:






(17)


dla
. Są to, jak łatwo się przekonać, wartości
tym większe, im w zbiorach
kategorie przykładów są
rozłożone bardziej równomiernie, a tym mniejsze, im wyraźniej w tych
zbiorach jedna lub kilka kategorii dominuje nad innymi.


Oczywiście wystarczy rozważać po jednej wartości znajdującej
się między każdymi dwiema kolejnymi (po uporządkowaniu) wartościami
atrybutu , jakie występują w zbiorze trenującym, gdyż tylko dla
takich wartości entropia może się różnić. Przyjmiemy zatem, tak jak w
przypadku testów nierównościowych dla drzew decyzyjnych, że jako
możliwe wartości progowe brane są pod uwagę środki przedziałów
wyznaczonych przez uporządkowane wartości atrybutu występujące
w zbiorze przykładów .




Kryterium stopu



Typowe podejście do ustalenia kryterium stopu przy dyskretyzacji
zstępującej polega na uwzględnieniu dwóch czynników:


jakości najlepszej wartości progowej, jaką można wybrać,

liczby utworzonych przedziałów.






Próg przyrostu informacji



Pierwszy z podanych czynników wpływających na kryterium stopu oznacza
zatrzymanie rekurencyjnego procesu dyskretyzacji, jeśli dalsze
dzielenie przedziałów przestaje poprawiać (w wystarczająco dużym
stopniu) ich informacyjną zawartość, czyli powiększać nierównomierność
rozkładu kategorii. Jeśli określimy przyrost informacji wynikający z
podziału wartości atrybutu na zbiorze za pomocą progu
następująco:




.

(18)


Podział taki daje ,,poprawę'' tylko wtedy, kiedy
.
Jeśli zatem dla wartości progowej minimalizującej entropię i tym samym
maksymalizującej przyrost informacji nie jest on dodatni, to
wprowadzanie dalszego podziału jest nieuzasadnione. Można także
,,zaostrzyć'' takie kryterium stopu żądając, aby dla kontynuacji
rekurencyjnych podziałów możliwy do uzyskania przyrost informacji
przekraczał pewne dodatnie minimum.




Przyrost długości kodu



Korzystając z zasady minimalnej długości kodu można wprowadzić
bardziej wyrafinowane kryterium stopu, polegające na ocenie, czy
przyrost informacji wynikający z dodania kolejnej wartości progowej
jest wystarczający do zrównoważenia związanego z tym wzrostu
złożoności dyskretyzacji. Aby zastosować zasadę minimalnej długości
kodu, określamy liczbę bitów niezbędną do zapisania informacji o
dyskretyzacji oraz informacji o pomyłkach, jakie popełnia taka
dyskretyzacja -- traktowana jako hipoteza. Wówczas kryterium stopu
można sformułować jako warunek, że najmniejsza z możliwych do
uzyskania łącznych długości kodu jest większa, niż długość kodu dla
dotychczasowej dyskretyzacji, a więc nie poprawia stopnia kompresji
danych trenujących.


Podział na przedziały przeciwdziedziny atrybutu

reprezentowany przez zbiór
można potraktować jako
hipotezę do uczenia się pojęć w
bardzo naturalny sposób. Wystarczy w tym celu każdemu przedziałowi
dyskretyzacji
przypisać większościową kategorię w
zbiorze , czyli wśród przykładów trenujących, dla których
wartość atrybutu należy do tego przedziału. Taka hipoteza może być
stosowana do klasyfikowania dowolnego przykładu z dziedziny, dla którego
należy znaleźć przedział zawierający wartość atrybutu i zwrócić
związaną z tym przedziałem etykietę kategorii.


W celu zakodowania zbioru przedziałów nie ma potrzeby, jak mogłoby się
wydawać, kodowania ich końców jako liczb rzeczywistych. Wystarczy
przyjąć, że jest ustalony, skończony zbiór możliwych wartości
progowych wyznaczających przedziały, i należy tylko wskazać, które z
nich są używane. Założenie to jest do przyjęcia, gdyż omawiając
dyskretyzacje zstępującą i wstępującą przyjmowaliśmy, że jako wartości
progowe są brane pod uwagę zawsze środki przedziałów wyznaczonych
przez kolejne wartości dyskretyzowanego atrybutu, występujące w
zbiorze trenującym. Jeśli zbiór wszystkich takich potencjalnych
wartości progowych dla zbioru trenującego oznaczymy przez
, a zbiór tych z nich, które są faktycznie używane do
dyskretyzacji, przez
, to długość kodu niezbędna
do zakodowania hipotezy reprezentowanej przez taką dyskretyzację
wynosi




.

(19)




Skoro sposób dyskretyzacji można traktować jako hipotezę, można
określić liczbę pomyłek, jakie popełnia ona dla danych trenujących i
wyznaczyć długość kodu niezbędnego do ich skorygowania. Zgodnie z nim
dla każdego przykładu trenującego, który jest przez hipotezę
klasyfikowany niepoprawnie (co w tym przypadku oznacza, że przykład
należy do kategorii innej niż większość przykładów, dla których
wartość atrybutu należy do tego samego przedziału), należy
zakodować informację korygującą: wskazac błędnie klasyfikowany
przykład i podac prawidłowa kategorie. Jeśli takich pomyłek jest ,
to trzeba w tym celu kodu o długości




.

(20)




Powyższe rozważania tylko w uproszczony sposób ilustrują, jak można
próbować określać kryterium stopu dla dyskretyzacji na podstawie
zasady minimalnej długości kodu. W istocie potrzebna była znacznie
głębsza analiza (w tym staranne określenie nieredundancyjnego
kodowania), aby wyprowadzić kryterium stopu uważane obecnie za jedno z
najlepszych dla dyskretyzacji zstępującej:




,

(21)


gdzie






(22)


a dla dowolnego zbioru przykładów






(23)


składa się z wszystkich etykiet przyporządkowanych przykładom z
przez pojęcie docelowe.




Liczba przedziałów



Kryterium liczby utworzonych przedziałów, po osiągnięciu której
dyskretyzacja ma być zakończona, najłatwiej zrealizować odstępując od
rekurencyjnego zapisu procesu dyskretyzacji zstępującej,
odpowiadającego strategii w głąb, na rzecz strategii
wszerz, a najlepiej -- strategii najpierw najlepszy,
podobnie jak to było dyskutowane dla drzew decyzyjnych. Takie proste
kryterium jest bardzo wygodne do określenia w praktyce, a połączenie
go z prowadzeniem dyskretyzacji zgodnie ze strategią najpierw
najlepszy zapewnia uzyskanie najlepszej (ze względu na wartość
entropii poszczególnych przedziałów) dyskretyzacji przy zadanej
liczbie przedziałów.




Dyskretyzacja wstępująca



Do najczęściej stosowanych wstępujących metod dyskretyzacji należy
algorytm ChiMerge. W jego nazwie są odzwierciedlone dwie jego
właściwości: wykorzystanie statystyki oraz przeprowadzanie
dyskretyzacji przez łączenie przedziałów, czyli w sposób
wstępujący. Rozpoczynając od minimalnych przedziałów pokrywających
zakres dyskretyzowanego atrybutu, po jednym dla każdej jego wartości
występującej w zbiorze trenującym, algorytm wielokrotnie powtarza
podstawowy cykl, w którym rozważa połączenie każdej pary przyległych
przedziałów (lub w ogólniejszym wariancie ich pewnej liczby ) i
dokonuje połączenia tych, dla których da to według stosowanej
heurystyki najlepsze efekty. W algorytmie ChiMerge funkcję tej
heurystyki pełni właśnie statystyka .




Schemat dyskretyzacji wstępującej



O ile podstawową operacją podczas dyskretyzacji zstępującej,
niezależnie od jej wariantu, jest zawsze podział przedziału na
podprzedziały za pomocą pewnej wartości progowej, o tyle w przypadku
dyskretyzacji wstępującej funkcję równie kluczową pełni operacja
odwrotna, łącząca przyległe przedziały w jeden większy przedział.
Jeśli łączone przedziały oznaczymy przez i , to przedział
powstający z ich połączenia możemy
zapisać po prostu jako ich teoriomnogościową sumę
. Dla
przedziałów i musi być przy tym spełniony warunek
przyległości
. Wystarcza to do
zapisania bardzo prostego schematu dyskretyzacji wstępującej
przedstawionego jako poniższy algorytm.







Funkcja
przyjmuje jako argumenty
zbiór przykładów i atrybut , jako wynik zaś zwraca zbiór
przedziałów, na które jest dzielona przeciwdziedzina dyskretyzowanego
atrybutu, a ściślej ta jej część, która jest reprezentowana w zbiorze
. Jest to zazwyczaj cały zbiór trenujący . Zbiór przedziałów

jest inicjowany jako zbiór przyległych przedziałów,
pokrywających zakres wartości atrybutu występujących w w taki
sposób, że każda z tych wartości znajduje się w oddzielnym przedziale.
Dalsze postępowanie zależy od dwóch operacji, których określenie
umożliwia konkretyzację schematu:

i 
. Dopóki pierwsza z nich daje wynik
negatywny, dopóty za pomocą drugiej są wybierane i następnie łączone
pewne dwa przyległe przedziały ze zbioru
.




Statystyka dla przedziałów



Zarówno kryterium stopu, jaki i kryterium wyboru przedziałów do
łączenia, można określić wykorzystując statystykę dla
przedziałów. Cechami, których zależność jest w tym przypadku mierzona
przez tę statystykę, są kategoria pojęcia docelowego oraz
przynależność przedziału. Wartości dla
reprezentują wówczas faktyczny rozkład częstości kategorii w zbiorze
tych przykładów z , dla których wartość atrybutu znajduje się w
przedziale . Będzie nam jeszcze potrzebny oczekiwany rozkład
częstości kategorii w zbiorze przykładów
tak samo licznym jak , lecz wybranych ze zbioru losowo,
czyli wartości

, dla każdej kategorii określające oczekiwaną
liczbę należących do tej kategorii przykładów z , dla których
wartość atrybutu jest w przedziale , przy założeniu, że rozkład
przykładów między kategorie jest taki sam jak w całym zbiorze .
Wartość
można obliczyć w zwykły sposób:




.

(24)




Statystykę określać będziemy dla pary przyległych przedziałów
, , gdyż właśnie takie pary przedziałów są rozważane w
dyskretyacji wstępującej (uogólnienie na większą liczbę sąsiednich
przedziałów jest oczywiste). Skorzystamy w tym celu z wartości

oraz
, oznaczających oczekiwaną liczbę przykładów o kategorii ,
dla których wartość atrybutu znajduje się odpowiednio w
przedziałach i , przy założeniu, że rozkład przykładów jest
taki jak w przedziale uzyskiwanym z połączenia tych przedziałów.
Statystyka mierzy odległość między każdym z tych dwóch
rozkładów oczekiwanych a odpowiednim rozkładem faktycznym. Podczas gdy
rozkłady faktyczne opisują właściwości każdego z dwóch przedziałów z
osobna, rozkłady oczekiwane opisują właściwości przedziałów
połączonych. Miara odległości rozkładów faktycznych od oczekiwanych
jest więc także miarą różnicy między obydwoma kandydującymi do
połączenia przedziałami ze względu na występujący w nich rozkład
kategorii. Wartość statystyki dla dwóch przedziałów

, określającą, na ile rozkład kategorii
przykładów w każdym z tych przedziałów jest w sposób statystycznie
istotny różny, można obliczyć zgodnie z następującą
formułą:






(25)


Im wartość ta jest większa, tym większa jest różnica między
przedziałami i  ze względu na rozkład kategorii przykładów
o wartościach dyskretyzowanego atrybutu należących do tych
przedziałów. Statystyka ta ma w przybliżeniu rozkład o
stopniach swobody.




Kryterium stopu



Kryterium stopu dla dyskretyzacji wstępującej określa, kiedy powinno
zostać zakończone dalsze łączenie przedziałów. W skrajnym przypadku
musi to nastąpić, kiedy pozostanie tylko jeden przedział, którego już
nie można połączyć z innym, lecz uzyskana w ten sposób dyskretyzacja,
zastępująca wszystkie wartości ciągłe jedną, tą sama wartością
dyskretną, będzie równoznaczna z wyeliminowaniem dyskretyzowanego
atrybutu. Bardziej rozsądne jest przyjęcie pewnej minimalnej, większej
od liczby przedziałów, jaka musi pozostać, i zaprzestawanie
łączenia przedziałów, jeśli zostanie ona osiągnięta.


Drugim elementem kryterium stopu jest warunek nakładany nie na liczbę,
lecz na pewne właściwości uzyskanych dotychczas przedziałów. Dość
naturalne jest przyjęcie, że właściwości, jakie powinny być tu brane
pod uwagę, to podobieństwo, czy raczej odwrotnie, zróżnicowanie
przedziałów. Możemy postanowić, że dalszego łączenia przedziałów
należy zaprzestać przed osiągnięciem ich z góry ustalonej minimalnej
liczby, jeśli przedziały te za bardzo się od siebie różnią. Warunek
taki można sformułować korzystając z określonej wyżej statystyki
jako miary zróżnicowania. Zatrzymanie dyskretyzacji
następowałoby wtedy, gdy minimalna wartość
dla
wszystkich par przyległych przedziałów , okaże się większa,
niż pewien przyjęty próg -- zazwyczaj określany pośrednio przez
podanie maksymalnego poziom istotności różnicy między przedziałami
(zazwyczaj z zakresu
).




Wybór przedziałów do połączenia



Z oczywistych względów powinny być łączone przedziały najbardziej do
siebie podobne pod względem rozkładu częstości kategorii przykładów.
Oznacza to wybór dwóch przyległych przedziałów, dla których wartość
statystyki jest najmniejsza.




Dyskretyzacja bez nadzoru



Prymitywne metody dyskretyzacji, takie jak dyskretyzacja według równej
szerokości i według równej częstości, pomijają rozkład kategorii w
zbiorze trenującym, są więc metodami dyskretyzacji bez nadzoru.
Powstaje jednak pytanie o bardziej zaawansowane metody dyskretyzacji
bez nadzoru, które, nie wykorzystując kategorii przykładów,
uzależniałyby jednak sposób dyskretyzacji od rozkładu wartości
atrybutów.


Podstawowe schematy dyskretyzacji zstępującej i wstępującej w żaden
jawny sposób nie zakładają, czy przeprowadzana jest za ich pomocą
dyskretyzacja z nadzorem, czy bez. Zależność od dostępności kategorii
przykładów kryje się jednak w konkretyzujących te schematy kryteriach
wyboru wartości progowych lub przedziałów do połączenia oraz
odpowiednich kryteriach stopu. Aby uzyskać algorytm zstępującej lub
wstępującej dyskretyzacji bez nadzoru, takie kryteria należy
sformułować w inny sposób, niezależny od niedostępnych etykiet
kategorii pojęcia docelowego.


O ile dyskretyzacja z nadzorem jest przekształceniem przestrzeni
atrybutów poprzedzającym ich użycie do uczenia się pojęć, o tyle
dyskretyzacja bez nadzoru powinna -- w razie potrzeby -- poprzedzać
tworzenie pojęć, czyli grupowanie. Oznacza to, że należy w jej trakcie
dążyć do uzyskania takiego podziału przeciwdziedziny każdego atrybutu
ciągłego, który sprzyja uzyskaniu grupowania o odpowiednio wysokiej
jakości. Sugeruje to, aby podział na przedziały przy dyskretyzacji bez
nadzoru oceniać podobnie jak grupowanie -- ze względu na podobieństwo
przykładów, dla których wartości dyskretyzowanego atrybutu znajdują
się w tym samym przedziale. Oznacza to w istocie potraktowanie każdego
zbioru dla
jako grupy przykładów.


Do oceny grupowania reprezentowanego przez przedziały dyskretyzacji
można stosować różne proste miary podobieństwa, zwłaszcza jeśli
wszystkie atrybuty określone na dziedzinie są ciągłe, kiedy do tego
celu może posłużyć odpowiednio zdefiniowana odległość. Przy
dyskretyzacji zstępującej należałoby dążyć do wyboru wartości progowej
w ten sposób, aby grupy przykładów reprezentowane przez oba powstałe
po jej użyciu przedziały jak najbardziej się od siebie różniły. Przy
dyskretyzacji wstępującej do połączenia należy wybrać takie dwa
przyległe przedziały, dla których odpowiednie grupy różnią się od
siebie w najmniejszym stopniu. Szczególnie atrakcyjne jest jednak
wykorzystanie funkcji jakości stosowanej przez system COBWEB, która
umożliwia jednoczesne uwzględnienie atrybutów ciągłych i dyskretnych.
Jej drugą ważną zaletą jest to, że ocenia nie po prostu podobieństwo
wewnątrz jednej grupy lub zróżnicowanie między dwiema grupami, lecz
grupowanie jako całość. W związku z tym, niezależnie od tego, czy
mamy do czynienia z dyskretyzacją zstępującą czy wstępującą, wystarczy
zawsze podejmować taką decyzję, która prowadzi do największej wartości
tej funkcji dla grupowania reprezentowanego przez podział na
przedziały wynikający z tej decyzji. Naturalnym kryterium stopu jest
wtedy warunek, że najlepsza znaleziona w ten sposób decyzja (o
podziale przedziału albo o połączeniu przedziałów, zależnie od metody
dyskretyzacji) daje oceną gorszą od oceny aktualnego zbioru
przedziałów.




Zagadnienia praktyczne





Wybór metody dyskretyzacji



Prymitywne metody dyskretyzacji, chociaż atrakcyjne przez prostotę
(także obliczeniową, co w praktyce może być bardzo istotne),
w zasadzie nie powinny być stosowane, jeśli dostępna moc obliczeniowa
umożliwia stosowanie jakiejkolwiek zaawansowanej metody dyskretyzacji
z nadzorem. Pomijając to, że nie uwzględniają one rozkładu kategorii,
są czułe na występujące w zbiorze trenującym wartości izolowane
dyskretyzowanego atrybutu -- nieliczne wartości znacznie oddalone od
zakresu, w którym znajduje się większość wartości -- które mogą,
chociaż nie muszą, wynikać z przekłamań. Dyskretyzując zarówno według
równej szerokości, jak i według równej częstości, możemy spodziewać
się niekorzystnego wpływu wartości izolowanych. W pierwszym przypadku,
,,rozciągając'' zakres wartości obserwowanych w zbiorze trenującym,
prowadzą przy ustalonej liczbie przedziałów do ich nadmiernej
szerokości. W drugim przypadku rzadko występujące wartości izolowane
mogą znaleźć się w jednym szerokim przedziale z innymi wartościami,
bardzo od nich odległymi. Stosując prymitywne metody dyskretyzacji
dobrze jest więc wstępnie eliminować wartości izolowane.


Wśród zaawansowanych metod dyskretyzacji z nadzorem żadna nie jest
wyraźnie lepsza od pozostałych i wybór jest mniej istotny. Względy
efektywności obliczeniowej przemawiają raczej na rzecz metod
zstępujących, chociaż odpowiednio staranna implementacja metod
wstępujących może oddalić ten argument. Bardziej istotne od wyboru
algorytmu jest odpowiednie dobranie jego parametrów, a zwłaszcza
określenie kryterium stopu i liczby tworzonych przedziałów.




Liczba przedziałów dyskretyzacji



Mankamentem dyskretyzacji według równej szerokości lub częstości jest
także to, że odpowiedzialność za wyznaczenie liczby przedziałów spada
w całości na eksperymentatora. Metody zaawansowane umożliwiają jej
określenie w zautomatyzowanych sposób na podstawie danych trenujących.
Wymagają one jednak określenia parametrów wpływających na kryterium
stopu, co także może być niekiedy kłopotliwe. W szczególności algorytm
ChiMerge ma tendecję do tworzenia większej liczby przedziałów dla
dużych zbiorów trenujących. Można to tłumaczyć tym, że częściej się
wtedy zdarzają przypadkowo zróżnicowane rozkłady kategorii
w przyległych przedziałach, które w konsekwencji nie zostaną
połączone. Aby zapobiec uzyskaniu zbyt wielu przedziałów, należy wobec
tego używać wyższych poziomów istotności dla większych zbiorów danych,
co jest pewną praktyczną niedogodnością.




Literatura





Cichosz, P. Systemy uczące się. WNT, 2000. (Podrozdział
7.2).

Witten, I. A., Frank, E. Data Mining. Morgan Kaufmann,
2000. (Podrozdział 7.2).








About this document ...

Metody odkrywania wiedzy: wykład 8
Dyskretyzacja atrybutów ciągłych
This document was generated using the
LaTeX2HTML translator Version 2K.1beta (1.48)

Copyright © 1993, 1994, 1995, 1996,
Nikos Drakos,
Computer Based Learning Unit, University of Leeds.

Copyright © 1997, 1998, 1999,
Ross Moore,
Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split 0 -no_navigation mow-w8.tex

The translation was initiated by Pawel Cichosz on 2004-02-12


Pawel Cichosz
2004-02-12