Kryteria stopu algorytmu grupowania reguł
a efektywność systemu wspomagania decyzji
Agnieszka Nowak Alicja Wakulicz-Deja
Zakład Systemów Informatycznych
Instytut Informatyki Uniwersytetu ÅšlÄ…skiego
Sosnowiec, ul. Będzińska 39, [phone]
Agnieszka Nowak, Alicja Wakulicz-Deja (Zakład Systemów Informatycznych Instytut Informatyki a efektywność systemuSosnowiec, ul. decyzji 39, +48 1 / 34 2
Kryteria stopu algorytmu grupowania regułUniwersytetu Śląskiego wspomagania Będzińska (0-32)
Plan referatu
1
Efektywność wnioskowania w klasycznych systemach wspomagania decyzji.
2
Motywacja tworzenia hierarchicznej bazy wiedzy.
3
Prawda o aglomeracyjnym algorytmie grupowania.
4
Efektywność osiągana różnymi drogami ?.
5
Podsumowanie.
Agnieszka Nowak, Alicja Wakulicz-Deja (Zakład Systemów Informatycznych Instytut Informatyki a efektywność systemuSosnowiec, ul. decyzji 39, +48 2 / 34 2
Kryteria stopu algorytmu grupowania regułUniwersytetu Śląskiego wspomagania Będzińska (0-32)
Zagadnienia...
Referat powinien udzielić satysfakcjonujących odpowiedzi na pytania:
1
Dlaczego potrzebna jest zmiana struktury bazy wiedzy ?
2
Dlaczego proponujemy hierarchiÄ™ ?
3
Dlaczego jako algorytm grupowania wybieramy akurat AHC ?
4
Jak zamierzamy zmodyfikować klasyczne podejścia ?
5
W jakim celu wprowadzamy swoje zmiany ?
6
Jak będziemy sprawdzać efektywność (jakość) zbudowanego systemu ?
7
Podsumowanie - odpowiedz
na pytanie: Jaka jest efektywność
proponowanego rozwiÄ…zania?
Agnieszka Nowak, Alicja Wakulicz-Deja (Zakład Systemów Informatycznych Instytut Informatyki a efektywność systemuSosnowiec, ul. decyzji 39, +48 3 / 34 2
Kryteria stopu algorytmu grupowania regułUniwersytetu Śląskiego wspomagania Będzińska (0-32)
Dlaczego potrzebna jest zmiana struktury bazy wiedzy ?
Efektywność wnioskowania w klasycznych systemach wspomagania decyzji takich
jak np MYCIN, EMYCIN etc. zależy od kilku czynników:
wybranej metody wnioskowania,
posiadanej w systemie wiedzy (liczby reguł w bazie wiedzy),
liczby obserwacji,
wybranej strategii sterowania wnioskowaniem.
Konkluzje:
trudna ocena takiego systemu,
wymagana kompletność bazy wiedzy,
czas wnioskowania rośnie gdy zwiększa się liczba reguł w bazie wiedzy,
optymalny system wspomagania decyzji, to taki system, który
dostarcza decyzji w jak najkrótszym czasie, angażując użytkownika
tylko w pewnym minimalnym zakresie.
Agnieszka Nowak, Alicja Wakulicz-Deja (Zakład Systemów Informatycznych Instytut Informatyki a efektywność systemuSosnowiec, ul. decyzji 39, +48 4 / 34 2
Kryteria stopu algorytmu grupowania regułUniwersytetu Śląskiego wspomagania Będzińska (0-32)
Dlaczego proponujemy hierarchiÄ™ ?
Wiedza każdego systemu może być reprezentowana na wiele różnych sposobów,
np. za pomocą rozkładów prawdopodobieństwa, współczynników pewnych funkcji,
struktur symbolicznych gramatyk formalnych, czy hierarchii podziałów. Poprzez
analizowanie przykładów, system ma odkryć nieznany podział (lub hierarchię
podziałów) dostarczonego mu zbioru, czyli dokonać grupowania tego zbioru.
Agnieszka Nowak, Alicja Wakulicz-Deja (Zakład Systemów Informatycznych Instytut Informatyki a efektywność systemuSosnowiec, ul. decyzji 39, +48 5 / 34 2
Kryteria stopu algorytmu grupowania regułUniwersytetu Śląskiego wspomagania Będzińska (0-32)
Motywacja tworzenia hierarchicznej bazy wiedzy
Optymalizacja czasu pracy systemu, jak i metody wnioskowania jest
skomplikowana.
Zadaniem interpretera reguł jest znalezienie i uaktywnienie reguł
odpowiednich do zaobserwowanych faktów. Oczywiste jest, że jeżeli rozmiar
bazy reguł wzrasta, to i czas szukania reguł przez interpreter się zwiększa.
Aby temu zapobiec proponujemy grupowanie reguł (aglomerację) w
bazach wiedzy i wnioskowanie na grupach (skupieniach) reguł.
Cel: Analiza skupień ma skrócić w sposób istotny czas wnioskowania.
Agnieszka Nowak, Alicja Wakulicz-Deja (Zakład Systemów Informatycznych Instytut Informatyki a efektywność systemuSosnowiec, ul. decyzji 39, +48 6 / 34 2
Kryteria stopu algorytmu grupowania regułUniwersytetu Śląskiego wspomagania Będzińska (0-32)
Dlaczego spośród wszystkich algorytmów grupowania wybieramy
akurat AHC ?
Liczba Stirlinga II-go rzędu
Moc (liczba możliwych kombinacji) grupowania metodą k-optymalizacyjną n
elementów na k grup (skupień) da się wyznaczyć z następującego wyrażenia:
n

1
M = ( )[ (k)(-1)k-i " in]]
i
k!
i=1
Wówczas mając zaledwie do pogrupowania 6 (n = 6) obiektów do 3 (k = 3) grup,
liczba możliwych kombinacji wynosi:
1
M = ( )[(3)(-1)2 " 16 + (3)(-1) " 26 + (3)(-1)0 " 36] = 90
1 2 3
3!
Algorytm hierarchicznego łączenia obiektów - rozwiązuje ten problem
poprzez samą ideę algorytmu, która zawsze nakazuje w każdym kroku
połączyć dwa najbardziej podobne obiekty.
Agnieszka Nowak, Alicja Wakulicz-Deja (Zakład Systemów Informatycznych Instytut Informatyki a efektywność systemuSosnowiec, ul. decyzji 39, +48 7 / 34 2
Kryteria stopu algorytmu grupowania regułUniwersytetu Śląskiego wspomagania Będzińska (0-32)
Klasyczne grupowanie hierarchiczne
Agnieszka Nowak, Alicja Wakulicz-Deja (Zakład Systemów Informatycznych Instytut Informatyki a efektywność systemuSosnowiec, ul. decyzji 39, +48 8 / 34 2
Kryteria stopu algorytmu grupowania regułUniwersytetu Śląskiego wspomagania Będzińska (0-32)
Klasyczne grupowanie hierarchiczne
krok 1: połączenie w grupę obiektów 1 i 2
Agnieszka Nowak, Alicja Wakulicz-Deja (Zakład Systemów Informatycznych Instytut Informatyki a efektywność systemuSosnowiec, ul. decyzji 39, +48 9 / 34 2
Kryteria stopu algorytmu grupowania regułUniwersytetu Śląskiego wspomagania Będzińska (0-32)
Klasyczne grupowanie hierarchiczne
krok 2: połączenie w grupę obiektów 3 i 4
Agnieszka Nowak, Alicja Wakulicz-Deja (Zakład Systemów Informatycznych Instytut Informatyki a efektywność systemuSosnowiec, ul. decyzji 39, +48 (0-32) 2
Kryteria stopu algorytmu grupowania regułUniwersytetu Śląskiego wspomagania Będzińska 10 / 34
Klasyczne grupowanie hierarchiczne
krok 3: połączenie w grupę obiektów 7 i 5
Agnieszka Nowak, Alicja Wakulicz-Deja (Zakład Systemów Informatycznych Instytut Informatyki a efektywność systemuSosnowiec, ul. decyzji 39, +48 (0-32) 2
Kryteria stopu algorytmu grupowania regułUniwersytetu Śląskiego wspomagania Będzińska 11 / 34
Klasyczne grupowanie hierarchiczne
krok 4: połączenie w grupę obiektów 6 i 8
Agnieszka Nowak, Alicja Wakulicz-Deja (Zakład Systemów Informatycznych Instytut Informatyki a efektywność systemuSosnowiec, ul. decyzji 39, +48 (0-32) 2
Kryteria stopu algorytmu grupowania regułUniwersytetu Śląskiego wspomagania Będzińska 12 / 34
Macierzowy algorytm aglomeracyjny - algorytm Johnson a
1
t=0 /*nr poziomu w hierarchii*/
2
utworzenie początkowego podziału
N
Podz0 (N) = {Gi = {xi }|i = 1, . . . , N}
3
utworzenie poczÄ…tkowej N × N macierzy niepodobieÅ„stwa P(t) :
P(i, j)(t) = D(Gi , Gj )i, j = 1, . . . , N
4
repeat a) - e):
a) wybranie spośród wszystkich par grup (Gi , Gj ) w podziale t najbliższej pary
(Gi , Gj ):
min
D(Gi , Gj ) = D(Gi , Gj )
r,s
b) t = t + 1
c) utworzenie nowej grupy Gq = Gi *" Gj
d) utworzenie nowego podziału:
N-1 N-t+1
Podzt (N) = {Podzt-1 (N) - {Gi , Gj }} *" {Gq}
e) aktualizacja macierzy niepodobieństwa P(t) dla kroku t na podstawie P(t - 1)
(kroki 1-2):
1.Usunięcie dwóch rzędów i dwóch kolumn z macierzy P(t - 1), które odpowiadają
Å‚Ä…czonym grupom.
2.Dodanie nowego rzędu i nowej kolumny dla nowo utworzonej grupy, które
zawierają obliczone odległości pomiędzy nowo utworzoną grupą i wszystkimi
grupami z kroku (t - 1), które nie zostały w tym kroku zmienione.
5
until (wszystkie wektory sÄ… w jednej grupie).
Agnieszka Nowak, Alicja Wakulicz-Deja (Zakład Systemów Informatycznych Instytut Informatyki a efektywność systemuSosnowiec, ul. decyzji 39, +48 (0-32) 2
Kryteria stopu algorytmu grupowania regułUniwersytetu Śląskiego wspomagania Będzińska 13 / 34
Sposoby aktualizacji macierzy - obliczania nowych odległości w
każdym kroku
Wg Jain i Dubes a:
1
Algorytm pojedynczego Å‚Ä…czenia (ang. single linkage algorithm)
D(Cq, Cs) = min{D(Ci , Cs), D(Cj, Cs)}
2
Algorytm pełnego łączenia (ang. complete linkage algorithm)
D(Cq, Cs) = max{D(Ci , Cs), D(Cj, Cs)}
3
Algorytm uśredniania par (ang. weighted average linkage)
1
D(Cq, Cs) = (D(Ci , Cs) + D(Cj, Cs))
2
Ponadto:
4
Average Linkage (UPGMA),Centroid (UPGMC), Median (WPGMC),
5
Algorytm Warda (ang. Increase in Sum of Squares).
Agnieszka Nowak, Alicja Wakulicz-Deja (Zakład Systemów Informatycznych Instytut Informatyki a efektywność systemuSosnowiec, ul. decyzji 39, +48 (0-32) 2
Kryteria stopu algorytmu grupowania regułUniwersytetu Śląskiego wspomagania Będzińska 14 / 34
Ważne aspekty grupowania hierarchicznego
Złożoność czasowa macierzowych algorytmów aglomeracyjnych wynosi
O(N2 lg N) natomiast pamięciowa O(N2). Ta ostatnia wynika z konieczności
pamiÄ™tania macierzy niepodobieÅ„stwa o wymiarach N × N.
Wynik algorytmu grupowania hierarchicznego można przedstawić w postaci
tzw. dendrogramu niepodobieństwa, w którym występuje oś skojarzona z
używaną miarą niepodobieństwa. Przecięcie poziome dendrogramu daje jeden
z możliwych podziałów.
Agnieszka Nowak, Alicja Wakulicz-Deja (Zakład Systemów Informatycznych Instytut Informatyki a efektywność systemuSosnowiec, ul. decyzji 39, +48 (0-32) 2
Kryteria stopu algorytmu grupowania regułUniwersytetu Śląskiego wspomagania Będzińska 15 / 34
Jak będziemy sprawdzać efektywność (jakość) zbudowanego systemu ?
[Jain A.K., Dubes R.C.,  Algorithms for clustering data , Prentice Hall, 1998]
Procedura grupowania to nie tylko samo grupowanie ? ProcedurÄ™ grupowania tworzÄ…
następujące zadania składowe:
1
utworzenie reprezentacji,
2
wybór miary podobieństwa,
3
ustalenie tendencji grupujÄ…cej,
4
grupowanie,
5
walidacja wyniku,
6
abstrakcja cech.
W zależności od użytej miary podobieństwa, rodzaju algorytmu grupowania oraz różnych
wartości jego parametrów, uzyskuje się różne wynikowe podziały danego zbioru obiektów.
Z tego względu konieczne jest stosowanie weryfikacji uzyskanego podziału zwanej
potocznie walidacją, która stanowi procedurę sprawdzającą  poprawność uzyskanego
podziału. Walidacji tej dokonuje się za pomocą weryfikacji hipotez statystycznych lub
odpowiednio skonstruowanych wskaz
ników (indeksów) walidacyjnych: np. indeks Dunn a
czy Xie - Beni.
Agnieszka Nowak, Alicja Wakulicz-Deja (Zakład Systemów Informatycznych Instytut Informatyki a efektywność systemuSosnowiec, ul. decyzji 39, +48 (0-32) 2
Kryteria stopu algorytmu grupowania regułUniwersytetu Śląskiego wspomagania Będzińska 16 / 34
Zdefiniowanie kryterium jakości
[K.Stąpor, Automatyczna klasyfikacja obiektów , EXIT, W-wa 2005]
W algorytmach iteracyjnej optymalizacji tj. k-means, k-medoids, najlepszy
podział zbioru jest wyznaczany przez iteracyjne polepszanie pewnych wskaz
ników
jakości, startując z początkowego podziału, najczęściej losowego. Wskaz
niki
jakości definiuje się w postaci funkcji kryterialnej, która jest zależna od zbioru
uczącego oraz wektora nieznanych parametrów określających daną grupę.
Funkcja kryterialna najczęściej jest konstruowana w postaci sumy kwadratów
odległości wektorów w grupach od prototypów tych grup. Stanowi więc miarę
rozproszenia wektorów w poszczególnych grupach.
Ocenie może podlegać:
uzyskany pojedynczy podział,
hierarchia podziałów,
pojedyncza grupa.
Spośród wszystkich możliwych podziałów uzyskanych jako wynik
działania danego algorytmu grupowania z różnymi wartościami
parametrów należy wybrać ten, który najlepiej opisuje strukturę zbioru.
Agnieszka Nowak, Alicja Wakulicz-Deja (Zakład Systemów Informatycznych Instytut Informatyki a efektywność systemuSosnowiec, ul. decyzji 39, +48 (0-32) 2
Kryteria stopu algorytmu grupowania regułUniwersytetu Śląskiego wspomagania Będzińska 17 / 34
Jak oceniać rezultaty k-means, k-medoids ?
Jeśli xc - centroid, średnia wartość z wszystkich obiektów nalezących do danej
grupy C . wówczas, można zdefiniować miarę dopasowania skupienia c:

TD(C ) = dist(p, xc)2
p"C
Dalej, całkowity koszt grupowania w danej iteracji mozna wyznaczyć jako:
k

TD = TD(Ci )
i=1
Agnieszka Nowak, Alicja Wakulicz-Deja (Zakład Systemów Informatycznych Instytut Informatyki a efektywność systemuSosnowiec, ul. decyzji 39, +48 (0-32) 2
Kryteria stopu algorytmu grupowania regułUniwersytetu Śląskiego wspomagania Będzińska 18 / 34
Jak oceniać rezultaty grupowania hierarchicznego ?
Problem wyboru optymalnego podziału rozwiązuje sama idea algorytmu. Jedynie,
w zależności od wybranej metody tworzenia centroidu (single linkage, complete
linkage, Ward, etc.), dwa najbardziej podobne obiekty mogą zostać łączone w
grupę w innym czasie (w innym kroku algorytmu, raz wcześniej, raz póz
niej).
Zatem, stosując techniki hierarchiczne, zwiększamy co prawda czas działania
algorytmu, ale usuwamy problem oceny otrzymanego rozwiÄ…zania.
Efektywność wnioskowania po grupowaniu reguł metodą analizy skupień
Kryteria oceny systemów wnioskujących można podzielić na dwie grupy:
kryteria związane ze złożonością obliczeniową algorytmu,
kryteria związane z jakością otrzymanego podziału,
kryteria związane z jakością generowanych wyników, np. trafność
rozpoznawania, dokładność lokalizacji obiektu, etc.[kompletność, dokładność].
Agnieszka Nowak, Alicja Wakulicz-Deja (Zakład Systemów Informatycznych Instytut Informatyki a efektywność systemuSosnowiec, ul. decyzji 39, +48 (0-32) 2
Kryteria stopu algorytmu grupowania regułUniwersytetu Śląskiego wspomagania Będzińska 19 / 34
Jak zamierzamy zmodyfikować klasyczne podejścia ?
Pożądane własności dobrego podziału:
możliwie najmniejsza liczba parametrów koniecznych do specyfikowania,
możliwie najmniejsza krotność analizy elementów zbioru U,
możliwość wykrywania grup o dowolnym kształcie, wielkości, gęstości,
niewrażliwość na obecność szumu (wektorów odstających) w zbiorze,
możliwość przetwarzania danych różnych typów (ciągłe, dyskretne), w szczególności ich
kombinacji,
niezależność wyniku od kolejności analizy obiektów zbioru U,
możliwie największe podobieństwo obiektów wewnątrz danej grupy oraz możliwie
najmniejsze podobieństwo grup do siebie.
Rzeczywistość jest inna - niepożądane własności podziału:
podobieństwo między obiektami w danej grupie spada poniżej pewnego ustalonego
poziomu minimum.
Różne są sposoby ustalania tego minimalnego współczynnika podobieństwa. W rozważaniach
podejmowanych przez nas wcześniej brane były pod uwagę dwie metody:
średnia z minimum i maksimum,
min(s(x, y)) + max(s(x, y))
T = ,
2
średnia ważona.
T = s (x, y).
gdzie:
s(x, y)- to pewna miara podobieństwa między obiektami x oraz y(np. miara Gowera).
Agnieszka Nowak, Alicja Wakulicz-Deja (Zakład Systemów Informatycznych Instytut Informatyki a efektywność systemuSosnowiec, ul. decyzji 39, +48 (0-32) 2
Kryteria stopu algorytmu grupowania regułUniwersytetu Śląskiego wspomagania Będzińska 20 / 34
Kryteria oceny jakości podziału
Jakość grupowania zależy od tego jak różnie obiekty są rozrzucone w węzłach
drzewa a to z kolei zależy od algorytmu jakim były łączone i od tego jakich
metryk używano do ich łączenia.
SÄ… 2 standardowe miary:
miara oceny (ang. FScore),
2RP
FScore =
R + P
gdzie:
R - kompletność (ang. Recall), P - dokładność (ang. Precision).
miara rozkładu - entropii (ang.Entropy).
q
i i

1 nr nr
Entropy(Sr ) = - lg
lg q nr nr
i=1
gdzie:
i
q - liczba klas, nr - liczba obiektów w i-tej klasie.
Entropia całego drzewa T wynosi:
t

1
Entropy(T ) = (Sr )
t
r=1
Agnieszka Nowak, Alicja Wakulicz-Deja (Zakład Systemów Informatycznych Instytut Informatyki a efektywność systemuSosnowiec, ul. decyzji 39, +48 (0-32) 2
Kryteria stopu algorytmu grupowania regułUniwersytetu Śląskiego wspomagania Będzińska 21 / 34
t - liczba węzłów w drzewie T .
Miara Theodoridis i Koutroumbas,1999
[S. Theodoridis, K. Koutroumbas,  Patern Recognition , Academic Press, 1999] Odpowiedni
poziom odcięcia to ten, dla którego spełniony jest warunek:
"G ,Gj Dmin(Gi , Gj) > max{h(Gi , Gj)}
i
gdzie:
h(Gi ) jest miarą samopodobieństwa grupy, tj. podobieństwa pomiędzy wektorami z danej grupy.
Miarę samopodobieństwa można zdefiniować np. jako maksymalną odległość wektorów w grupie:
h(G ) = max{d(x, y)|x,y"G }
lub też jako średnią wartość odległości między wektorami w grupie:

1
h(G ) = d(x, y)
2NG
x"G y"G
gdzie:
d(x, y) oznacza którąkolwiek z miar niepodobieństwa wektorów. Innymi słowy, w końcowym
podziale niepodobieństwo pomiędzy dowolną parą grup musi być większe niż samopodobieństwo
każdej z grup.
Agnieszka Nowak, Alicja Wakulicz-Deja (Zakład Systemów Informatycznych Instytut Informatyki a efektywność systemuSosnowiec, ul. decyzji 39, +48 (0-32) 2
Kryteria stopu algorytmu grupowania regułUniwersytetu Śląskiego wspomagania Będzińska 22 / 34
mAHC
Agnieszka Nowak, Alicja Wakulicz-Deja (Zakład Systemów Informatycznych Instytut Informatyki a efektywność systemuSosnowiec, ul. decyzji 39, +48 (0-32) 2
Kryteria stopu algorytmu grupowania regułUniwersytetu Śląskiego wspomagania Będzińska 23 / 34
mAHC
Agnieszka Nowak, Alicja Wakulicz-Deja (Zakład Systemów Informatycznych Instytut Informatyki a efektywność systemuSosnowiec, ul. decyzji 39, +48 (0-32) 2
Kryteria stopu algorytmu grupowania regułUniwersytetu Śląskiego wspomagania Będzińska 24 / 34
mAHC
Agnieszka Nowak, Alicja Wakulicz-Deja (Zakład Systemów Informatycznych Instytut Informatyki a efektywność systemuSosnowiec, ul. decyzji 39, +48 (0-32) 2
Kryteria stopu algorytmu grupowania regułUniwersytetu Śląskiego wspomagania Będzińska 25 / 34
mAHC
Agnieszka Nowak, Alicja Wakulicz-Deja (Zakład Systemów Informatycznych Instytut Informatyki a efektywność systemuSosnowiec, ul. decyzji 39, +48 (0-32) 2
Kryteria stopu algorytmu grupowania regułUniwersytetu Śląskiego wspomagania Będzińska 26 / 34
mAHC
Agnieszka Nowak, Alicja Wakulicz-Deja (Zakład Systemów Informatycznych Instytut Informatyki a efektywność systemuSosnowiec, ul. decyzji 39, +48 (0-32) 2
Kryteria stopu algorytmu grupowania regułUniwersytetu Śląskiego wspomagania Będzińska 27 / 34
AHC kontra mAHC
a b c d e f g
AHC [100] 5 30 4 0 4 0.09 99
mAHC [70] 1 22 4 9 13 0.13 85
mAHC [90] 3 27 5 5 10 0.03 39
mAHC [95] 4 28 5 0 5 0.04 52
mAHC - inne 4 25 3 8 11 0.13 85
a - poziom w drzewie
b - liczba pamietanych elementow
c - liczba porównań w drzewie
d - liczba porównań w innych drzewach
e - suma porównań
f - odchylenie
g - procent błędu
Agnieszka Nowak, Alicja Wakulicz-Deja (Zakład Systemów Informatycznych Instytut Informatyki a efektywność systemuSosnowiec, ul. decyzji 39, +48 (0-32) 2
Kryteria stopu algorytmu grupowania regułUniwersytetu Śląskiego wspomagania Będzińska 28 / 34
mAHC kontra AHC
Agnieszka Nowak, Alicja Wakulicz-Deja (Zakład Systemów Informatycznych Instytut Informatyki a efektywność systemuSosnowiec, ul. decyzji 39, +48 (0-32) 2
Kryteria stopu algorytmu grupowania regułUniwersytetu Śląskiego wspomagania Będzińska 29 / 34
mAHC kontra AHC
Agnieszka Nowak, Alicja Wakulicz-Deja (Zakład Systemów Informatycznych Instytut Informatyki a efektywność systemuSosnowiec, ul. decyzji 39, +48 (0-32) 2
Kryteria stopu algorytmu grupowania regułUniwersytetu Śląskiego wspomagania Będzińska 30 / 34
Miara efektywności van Rijsbergen a, 1979
Miara ta umożliwia ocenę obydwu parametrów: kompletności oraz dokładności
jednocześnie.
1 + b2
EHC = 1 -
b2 1
+
R P
gdzie odpowiednio:
b to współczynnik skalujący " [0..1],
R to to kompletność (ang. recall),
P to dokładność (ang. precision).
Idealna sytuacja
RHC = 1.0, PHC = 1.0
5
5/4
1
4
jeśli b = wówczas: EHC = 1 - = 1 - = 1 - 1 = 0
1
2 5/4
+1
4
Zależność jest taka, że im wartość EHC jest bliższa 0 tym większa jest efektywność
systemu, i odwrotnie.
Agnieszka Nowak, Alicja Wakulicz-Deja (Zakład Systemów Informatycznych Instytut Informatyki a efektywność systemuSosnowiec, ul. decyzji 39, +48 (0-32) 2
Kryteria stopu algorytmu grupowania regułUniwersytetu Śląskiego wspomagania Będzińska 31 / 34
Eksperymenty
Wyniki eksperymentów
a b c d e f
baza nr 1 16 31 5 16 10 62
baza nr 2 199 397 23 199 34 17
baza nr 3 480 959 27 480 36 7
baza nr 4 702 1403 30 702 38 5, 4
gdzie:
a - liczba reguł, b - liczba grup,c - liczba poziomow w drzewie (wysokość drzewa),
d - liczba porownań przy PZ, e - liczba porownań w AHC, f - procent BD
Agnieszka Nowak, Alicja Wakulicz-Deja (Zakład Systemów Informatycznych Instytut Informatyki a efektywność systemuSosnowiec, ul. decyzji 39, +48 (0-32) 2
Kryteria stopu algorytmu grupowania regułUniwersytetu Śląskiego wspomagania Będzińska 32 / 34
Podsumowanie - Wnioski
1
Hierarchiczne grupowanie reguł w bazach wiedzy przyspieszy procesy
wnioskowania poprzez kryterium podobieństwa - relewantności elementów
drzewa względem podanej nowej wiedzy.
2
Niekwestionowaną zaletą, drugą obok krótkiego czasu jest także fakt, iż
wnioskując w ten sposób system będzie generował tylko niezbędne nowe
fakty, nie obciążając w ten sposób systemu czy użytkownika nową wiedzą.
3
Dodatkowo - możemy zwiększyć jakość uzyskanego podziału poprzez
grupowanie obiektów z kontrolą bliskości - kryterium stopu algorytmu.
Agnieszka Nowak, Alicja Wakulicz-Deja (Zakład Systemów Informatycznych Instytut Informatyki a efektywność systemuSosnowiec, ul. decyzji 39, +48 (0-32) 2
Kryteria stopu algorytmu grupowania regułUniwersytetu Śląskiego wspomagania Będzińska 33 / 34
Literatura
1
Anderberg M.R., "Cluster analysis for applications", New York, Academic
Press, 1973.
2
Dubes R.C., Jain A.K., "Algorithms for clustering data", Prentice Hall,
1998.
3
Everitt B.S., "Cluster Analysis (3rd edition)", Edward Arnold / Halsted
Press, London, 1993.
4
Hand D., Mannila H., Smyth P., "Eksploracja danych", Wydawnictwa
Naukowo-Techniczne, Warszawa, 2005.
5
Kaufman L., Rousseeuw P.J., "Finding Groups in Data: An Introduction to
Cluster Analysis", John Wiley Sons, New York, 1990.
6
Nowak A., Wakulicz-Deja A. Bachliński S., "Optimization of Speech
Recognition by Clustering of Phones", Concurrency, Specification and
Concurrency 2005 - Ruciane-Nida, Poland, September 28-30, 2005
7
Nowak A., Wakulicz-Deja A. , "The concept of the hierarchical clustering
algorithms for rules based systems", Intelligent Information Systems 2005 -
New Trends in Intelligent Information Processing and Web Mining, Gdańsk,
Poland, June 13-16, 2005
8
Nowak A., Wakulicz-Deja A., "Aglomeracyjne metody tworzenia skupień reguł
dla optymalizacji procesów wnioskowania", Systemy Wspomagania Decyzji 2004,
Zakopane, Poland, Grudzień 7-9, 2004.
9
Stąpor K., "Automatyczna klasyfikacja obiektów", Akademicka Oficyna
Wydawnicza EXIT, Warszawa 2005.
10
Theodoridis S., Koutroumbas K., "Patern Recognition", Academic Press, 1999.
Agnieszka Nowak, Alicja Wakulicz-Deja (Zakład Systemów Informatycznych Instytut Informatyki a efektywność systemuSosnowiec, ul. decyzji 39, +48 (0-32) 2
Kryteria stopu algorytmu grupowania regułUniwersytetu Śląskiego wspomagania Będzińska 34 / 34