Algorytm Rochio’a polega na podzieleniu obiektów (dokumentów) danego zbioru na pewne grupy – w ramach których znajdować się będą dokumenty podobne do siebie opisem.
Przykład
Wykorzystując opis (poniżej) algorytmu Rocchia przeprowadź grupowanie 10 obiektów o następujących opisach:
x1=a1 b1 c1 d1 e1
x2=a1 b1 c1 d1 e2
x3=a1 b1 c2 d1 e3
x4=a1 b1 c3 d1 e1
x5=a1 b1 c1 d1 e3
x6=a2 b1 c2 d1 e2
x7=a2 b1 c3 d1 e3
x8=a2 b2 c3 d3 e3
x9=a3 b3 c2 d2 e2
x10=a3 b3 c2 d3 e2
Dla podanego wyżej zbioru obiektów dane są następujące parametry:
a) Dla centrum grupy: N1=5, N2=3, p1=0,2, p2=0,3
b) Dla centroidu: N1c=5, N2c=3, p1c=0,25, p2c=0,35
Krok 1. Wybór potencjalnego centrum grupy xc
Jako potencjalne centrum grupy 1 przyjmij obiekt – x1. Krok 2. Wybór miary podobieństwa (korelacji) każdego dokumentu z centrum grupy xc Dla obliczania współczynnika korelacji zastosuj wzór: Krok 0. Pobranie opisów obiektów
Krok 4. Ustalenie parametrów: p1,p2,N1,N2 - dla centrum grupy, p1c,p2c,N1c,N2c - dla centroidu.
Gdzie: p1, p2 to zakładane współczynniki korelacji, przy czym spełniona musi być zależność, że p1 p2
p1,p2 (0;1) N1, N2 to zakładane liczby dokumentów mających z wybranym centrum grupy współczynniki korelacji większe lub równe zakładanym współczynnikom p1 i p2. N1 dokumentów musi mieć współczynnik korelacji p p1
oraz
N2 dokumentów musi mieć współczynnik korelacji p p2
1. Przeprowadzamy test gęstości dla centrum grupy (xc).
Test ten mówi, że co najmniej N1 dokumentów ma współczynnik większy bądź równy od P1, a N2 dokumentów ma współczynnik większy bądź równy P2.
A) Jeżeli założenia są spełnione przechodzimy do kroku 6.
B) Jeżeli nie – to wybieramy inny obiekt jako centrum grupy.
W tym celu obliczamy współczynniki korelacji (podobieństwa każdego dokumentu z wybranym centrum grupy xc) stosując wybraną wcześniej miarę korelacji. Gdy mamy 10 dokumentów w systemie to po kolei dla każdego dokumentu wyliczamy taki współczynnik:
p(x1,xc)= ?
...
p(x10,xc)= ?
W liczniku podajemy liczbę pojęć wspólnym danego dokumentu z centrum grupy xc
W mianowniku podajemy sumę pojęć, którymi są opisane obydwa dokumenty: dany dokument xi i dokument stanowiący centrum grupy. Zatem: Aby obliczyć współczynnik korelacji obiektu 1 z centrum grupy....:) – który jest jednocześnie obiektem 1 wykonujemy następujące czynności.
W tym celu porządkujemy dokumenty malejąco według obliczonych w kroku 5 współczynników korelacji i nadajemy tak ułożonym wartościom rangi od 1 do n. P(x1,xc)=1.0
P(x2,xc)=0.67
P(x3,xc)=0.43
P(x4,xc)=0.67
P(x5,xc)=0.67
P(x6,xc)=0.25
P(x7,xc)=0.25
P(x8,xc)=0.0
P(x9,xc)=0.0
P(x10,xc)=0.0 Ranga 1 p(x1,xc)=1.0
Ranga 2 p(x2,xc)=0.67
Ranga 3 p(x4,xc)=0.67
Ranga 4 p(x5,xc)=0.67
Ranga 5 p(x3,xc)=0.43
Ranga 6 p(x6,xc)=0.25
Ranga 7 p(x7,xc)=0.25
Ranga 8 p(x8,xc)=0.0
Ranga 9 p(x9,xc)=0.0
Ranga 10 p(x10,xc)=0.0 Krok 6a. Przeprowadzamy test gęstości
– czyli sprawdzamy, czy na pewno:
N1 dokumentów ma p>= p1 i
N2 dokumentów ma współczynnik p>=p2
Jeśli tak to znaczy, że wybrane centrum grupy przeszedł test gęstości.
Krok 7. Obliczamy faktyczne rozmiary grupy 1
Wyznaczamy M1 (liczebność zbioru obiektów dla których elementy są większe bądź równe P2) , M2 (liczebność zbioru obiektów dla których elementy są większe bądź równe P1). Ranga 1 p(x1,xc)=1.0
Ranga 2 p(x2,xc)=0.67
Ranga 3 p(x4,xc)=0.67
Ranga 4 p(x5,xc)=0.67
Ranga 5 p(x3,xc)=0.43
Ranga 6 p(x6,xc)=0.25
Ranga 7 p(x7,xc)=0.25
Ranga 8 p(x8,xc)=0.0
Ranga 9 p(x9,xc)=0.0
Ranga 10 p(x10,xc)=0.0
M1=5 M2=7
Krok 8. Obliczamy minimalny współczynnik korelacji p min
Jeśli M1=M2 to:
to Pmin równa się najmniejszemu współczynnikowi korelacji obiektu należącego do M1
Jeśli M1 < M2 to:
Obliczamy różnicę pomiędzy współczynnikami korelacji obiektów sąsiednich w grupie maksymalnej M2,bez obiektów grupy minimalnej M1.
Określamy największą różnicę.
Minimalny współczynnik korelacji Pmin jest równy odjemnej z największej różnicy.
A) Jeśli największa różnica powtarza się to za Pmin przyjmujemy odjemną o większej wartości.
Krok 8a. Obliczamy minimalny współczynnik korelacji p min
M1 = 5
M2 = 7
Zatem aby obliczyć współczynnik korelacji p min obliczam różnicę między dokumentami na granicy tych grup. 5
0,43 – 0,25 = 0, 18
6
6
0,25 – 0,25 = 0
7
7
0,25 – 0 = 0,25
8 Minimalny współczynnik korelacji Pmin jest równy odjemnej z największej różnicy.
P min = p7(x7) = 0,25
Krok 9. Wyznaczamy grupę wstępną X w1 Do grupy wstępnej będą należały wszystkie te dokumenty, które miały wyliczony współczynnik korelacji większy lub równy p min.
Są to wszystkie obiekty grupy maksymalnej M2:
X1, x2, x3, x4, x5, x6 i x7. Krok 10. Wyznaczamy wstępnego reprezentanta grupy X1 – czyli centroid Centroid to zbiór wszystkich pojęć, którymi są opisane dokumenty grupy minimalnej M1, czyli...
Cw1 = {a1, a2, b1, c1, c2, c3, d1, e1, e2, e3}
Krok 10. Generujemy grupę poprawioną Aby upewnić się, że na pewno wszystkie te dokumenty powinny się znaleźć w tej grupie W tym celu powtarzamy raz jeszcze cały algorytm, z tym,
że teraz Nasze centrum grupy stanowi CENTROID c1...
a test gęstości przeprowadzamy tylko dla dokumentów grupy maksymalnej M2 Krok 11. Centrum grupy to centroid C1 C1= {a1, a2, b1, c1, c2, c3, d1, e1, e2, e3} Krok 12. Ustalenie parametrów: dla centroidu: p1c = 0,25 p2c = 0,35 N1c = 5 N2c = 3
Krok 15. Obliczamy faktyczne rozmiary grupy poprawionej
Krok 14a. Przeprowadzamy test gęstości
– czyli sprawdzamy, czy na pewno:
N1c dokumentów ma p>= p1c i
N2c dokumentów ma współczynnik p>=p2c
Jeśli tak to znaczy, że wybrane centrum grupy przeszedł test gęstości. Wyznaczamy M1 (liczebność zbioru obiektów dla których elementy są większe bądź równe P2) , M2 (liczebność zbioru obiektów dla których elementy są większe bądź równe P1). Ranga 1 p(x1,xc)=0.5
Ranga 2 p(x2,xc)= 0.5
Ranga 3 p(x4,xc)=0.5
Ranga 4 p(x5,xc)=0.5
Ranga 5 p(x3,xc)=0.5
Ranga 6 p(x6,xc)=0.5
Ranga 7 p(x7,xc)=0.5
M1 = M2=7 Jeśli M1=M2 to:
to Pmin równa się najmniejszemu współczynnikowi korelacji obiektu należącego do M1 czyli p min = p7(x7) = 0,5
Krok 16. Wyznaczamy grupę poprawioną X1 Do tej grupy będą należały wszystkie te dokumenty, które miały wyliczony współczynnik korelacji większy lub równy p min.
Są to wszystkie obiekty grupy maksymalnej M2:
X1= {x1, x2, x3, x4, x5, x6 i x7} Krok 10. Wyznaczamy reprezentanta grupy X1 – czyli centroid Centroid to zbiór wszystkich pojęć, którymi są opisane wszystkie dokumenty grupy X1, czyli...
Cw1 = {a1, a2, b1, c1, c2, c3, d1, e1, e2, e3}
Comments