Politechnika Łódzka



Pobieranie 6.5 Mb.
Strona37/54
Data29.10.2017
Rozmiar6.5 Mb.
1   ...   33   34   35   36   37   38   39   40   ...   54
Kompromis

Istnieje prosty kompromis pomiędzy kosztami wstępnej obróbki a szybkością szukania NS. Sortujemy zbiór P d-krotnie, kolejno według każdej z d współrzędnych, a następnie zamiast „pełnej” dekompozycji przestrzeni, przeprowadzamy hiperpo­wierzchnie jedynie przez co k-ty punkt ze zbioru P, w sensie opisanego porządku. Różnica polega na tym, że obecnie musimy dodatkowo policzyć odległości do k–1 dodatkowych punktów dla każdego z d wymiarów (zacienione pasy na Rys. 5.1 nie są już w kompromisowym rozwiązaniu puste). Koszt szukania wynosi zatem , jednak koszt pamięciowy wstępnego przetwarzania maleje do . Odpowiednio maleje też czas wstępnego przetwarzania.
5.4. Wyniki eksperymentów i dyskusja

Opisany algorytm został zaimplementowany w języku C++ przy użyciu kompilatora g++ 2.95.3. Komputer, na którym wykonane zostały testy, to PC z dwoma procesorami Celeron 533 (wykorzystywany był jednak tylko jeden procesor), wyposażony w 384 MB pamięci i uruchomiony pod systemem Linux 2.4.

Tab. 5.2–5.14 przedstawiają wyniki testów na zbiorach danych o różnej liczności i dla różnych wartości współczynnika kompromisu k. Wartości k zostały dobrane tak, aby wystarczyło pamięci, a czas przetwarzania wstępnego był „rozsądnie” krótki. Zbiory danych w Tab. 5.2–5.13 zostały wygenerowane losowo z rozkładem jednostaj­nym na hiperkwadracie. Liczności zbiorów odniesienia są podane przy każdej tabeli, natomiast zbiory testowe liczyły zawsze po 100000 próbek (wygenerowanych w analogiczny sposób). W Tab. 5.14 podano wyniki na zbiorze odniesienia Iris, jednak i tu zbiór testowy stanowiło 100000 losowych próbek.

Kolejne wiersze w Tab. 5.2–5.14 podają odpowiednio: ilość pamięci zajmowa­nej przez struktury danych, czas alokacji tych struktur, czas zasadniczego wstępnego przetwarzania, czas szukania NS dla wszystkich próbek zbioru testowego przy użyciu zaprezentowanego algorytmu oraz czas szukania siłowego („naiwnego”) (brute force).


Tabela 5.2: Porównanie proponowanego algorytmu szukania NS z szukaniem siłowym.
Zbiór odniesienia 2-wymiarowy liczący 500 próbek.




k=4

k=5

k=10

k=20

k=50

pamięć [MB]

0,24

0,16

0,04

0,01

0,01

alokacja [s]

0,03

0,01

< 0,01

< 0,01

< 0,01

preprocess [s]

0,74

0,48

0,11

0,03

0,01

szukanie [s]

0,82

0,75

0,65

0,65

1,09

brute-force [s]

3,17

Tabela 5.3: Porównanie proponowanego algorytmu szukania NS z szukaniem siłowym.


Zbiór odniesienia 2-wymiarowy liczący 1000 próbek.




k=10

k=15

k=20

k=30

k=40

pamięć [MB]

0,16

0,08

0,05

0,03

0,02

alokacja [s]

0,03

0,01

0,01

< 0,01

< 0,01

preprocess [s]

0,87

0,39

0,22

0,10

0,06

szukanie [s]

0,83

0,84

0,87

0,91

1,07

brute-force [s]

6,93

Tabela 5.4: Porównanie proponowanego algorytmu szukania NS z szukaniem siłowym.


Zbiór odniesienia 2-wymiarowy liczący 10000 próbek.




k=30

k=40

k=50

k=100

pamięć [MB]

1,78

1,03

0,69

0,23

alokacja [s]

0,17

0,13

0,05

0,03

preprocess [s]

237,82

140,17

87,14

20,64

szukanie [s]

4,29

4,46

4,97

8,21

brute-force [s]

197,40

Tabela 5.5: Porównanie proponowanego algorytmu szukania NS z szukaniem siłowym.


Zbiór odniesienia 3-wymiarowy liczący 100 próbek.




k=4

k=5

k=10

k=20

k=50

pamięć [MB]

0,48

0,25

0,03

< 0,01

< 0,01

alokacja [s]

0,05

0,02

< 0,01

< 0,01

< 0,01

preprocess [s]

0,24

0,14

0,02

< 0,01

< 0,01

szukanie [s]

0,60

0,59

0,70

0,94

1,64

brute-force [s]

0,89

Tabela 5.6: Porównanie proponowanego algorytmu szukania NS z szukaniem siłowym.


Zbiór odniesienia 3-wymiarowy liczący 500 próbek.




k=3

k=5

k=10

k=20

k=50

pamięć [MB]

142,14

30,52

3,82

0,48

0,04

alokacja [s]

8,48

2,02

0,29

0,05

< 0,01

preprocess [s]

274,10

56,80

6,36

0,79

0,06

szukanie [s]

1,55

1,23

1,02

1,12

1,80

brute-force [s]

3,69

Tabela 5.7: Porównanie proponowanego algorytmu szukania NS z szukaniem siłowym.


Zbiór odniesienia 3-wymiarowy liczący 1000 próbek.




k=6

k=10

k=20

k=30

k=40

k=50

k=100

pamięć [MB]

142,14

30,53

3,83

1,21

0,49

0,26

0,04

alokacja [s]

8,72

1,90

0,23

0,09

0,03

0,01

< 0,01

preprocess [s]

480,96

99,11

12,30

3,92

1,60

0,83

0,12

szukanie [s]

1,66

1,31

1,36

1,54

1,77

2,16

3,40

brute-force [s]

7,79

Tabela 5.8: Porównanie proponowanego algorytmu szukania NS z szukaniem siłowym.


Zbiór odniesienia 3-wymiarowy liczący 10000 próbek.




k=130

k=150

k=250

k=500

pamięć [MB]

14,05

9,29

2,07

0,36

alokacja [s]

0,90

0,57

0,10

0,02

preprocess [s]

1001,62

691,67

150,54

19,50

szukanie [s]

16,24

18,16

29,51

58,18

brute-force [s]

207,99

Tabela 5.9: Porównanie proponowanego algorytmu szukania NS z szukaniem siłowym.


Zbiór odniesienia 4-wymiarowy liczący 500 próbek.




k=15

k=20

k=50

k=80

pamięć [MB]

81,57

23,85

0,62

0,15

alokacja [s]

2,75

0,82

< 0,01

< 0,01

preprocess [s]

92,09

27,88

0,85

0,25

szukanie [s]

1,68

1,71

2,97

4,19

brute-force [s]

4,65

Tabela 5.10: Porównanie proponowanego algorytmu szukania NS z szukaniem siłowym.

Zbiór odniesienia 4-wymiarowy liczący 1000 próbek.





k=24

k=30

k=50

k=100

pamięć [MB]

189,94

81,58

9,78

0,63

alokacja [s]

6,76

2,88

0,30

0,02

preprocess [s]

387,30

168,91

21,90

1,60

szukanie [s]

2,20

2,45

3,62

5,66

brute-force [s]

9,63

Tabela 5.11: Porównanie proponowanego algorytmu szukania NS z szukaniem siłowym.


Zbiór odniesienia 4-wymiarowy liczący 10000 próbek.




k=450

k=500

k=800

pamięć [MB]

17,24

9,92

1,90

alokacja [s]

0,57

0,33

0,06

preprocess [s]

911,20

525,26

126,67

szukanie [s]

83,37

93,43

171,66

brute-force [s]

262,96

Tabela 5.12: Porównanie proponowanego algorytmu szukania NS z szukaniem siłowym.

Zbiór odniesienia 5-wymiarowy liczący 500 próbek.





k=30

k=50

k=80

pamięć [MB]

173,33

12,22

2,06

alokacja [s]

3,74

0,27

0,04

preprocess [s]

138,35

11,36

2,25

szukanie [s]

3,25

4,63

6,34

brute-force [s]

5,58

Tabela 5.13: Porównanie proponowanego algorytmu szukania NS z szukaniem siłowym.

Zbiór odniesienia 5-wymiarowy liczący 1000 próbek.





k=60

k=70

k=100

k=200

k=400

pamięć [MB]

173,34

92,72

12,23

0,40

0,05

alokacja [s]

4,18

2,11

0,28

0,01

< 0,01

preprocess [s]

257,81

140,76

21,40

1,01

0,14

szukanie [s]

5,91

6,41

8,72

16,11

27,82

brute-force [s]

11,38

Tabela 5.14: Porównanie proponowanego algorytmu szukania NS z szukaniem siłowym.


Zbiór odniesienia Iris: 4 wymiary, 150 próbek.




k=4

k=5

k=10

k=15

k=20

k=25

k=30

k=40

k=50

pamięć [MB]

127,27

49,44

3,09

0,61

0,25

0,08

0,04

0,02

0,01

alokacja [s]

4,58

1,68

0,13

0,03

0,01

0,01

< 0,01

< 0,01

< 0,01

preprocess [s]

55,92

21,64

1,42

0,30

0,14

0,05

0,02

0,01

< 0,01

szukanie [s]

0,83

0,83

0,98

1,16

1,27

1,53

1,77

2,07

2,55

brute-force [s]

1,43

Rys. 5.3–5.5 prezentują graficzne porównanie czasów szukania proponowanego algorytmu i podejścia siłowego dla wybranych zbiorów odniesienia.


Rys. 5.3. Zależność czasu szukania od współczynnika kompromisu k.


Zbiór odniesienia 3-wymiarowy liczący 1000 próbek.

Rys. 5.4. Zależność czasu szukania od współczynnika kompromisu k.


Zbiór odniesienia 4-wymiarowy liczący 10000 próbek.

Rys. 5.5. Zależność czasu szukania od współczynnika kompromisu k.


Zbiór odniesienia 5-wymiarowy liczący 1000 próbek.
Jak widać, zwiększenie k powoduje zmniejszenie obciążenia pamięciowego oraz skrócenie przetwarzania wstępnego za cenę wolniejszego szukania. Tym niemniej, w wielu przypadkach (p. np. Tab. 5.2 lub 5.5) zaobserwowano dziwny efekt skracania do pewnego momentu czasu szukania wraz ze wzrostem k (przy odpowiednio dużych wartościach k efekt ten znika i czas szukania zgodnie z teorią rośnie). Przypuszczalnie jest to spowodowane cache’m procesora: przy małych wartościach k posortowane tablice wartości poszczególnych cech mogą nie mieścić się w całości w cache’u, a zatem dostęp do nich jest stosunkowo wolny. Warto zauważyć, że zjawisko to nie zostało odnotowane dla przypadków w wyższych wymiarach (4–5), co zapewne wiąże się z faktem, iż dla tych zbiorów testowanie algorytmu z niskimi wartościami k było niemożliwe z uwagi na ogromne koszta obróbki wstępnej.

Warto zwrócić uwagę, że przedstawiony algorytm przy odpowiednio niskim wymiarze (2–3) nadaje się także do zastosowań on-line, gdy celem jest minimalizacja sumy czasu wstępnego przetwarzania i zasadniczego szukania. Zauważmy, że jeśli (z grubsza mówiąc) , to czas generacji struktury danych jest krótszy od czasu znalezienia NS dla każdej próbki zbioru odniesienia metodą brute-force. Obrazuje to np. przypadek w Tab. 5.3; czas wstępnego przetwarzania wynosi 0,060 s, nato­miast szukanie NS metodą brute-force dla 1000 próbek trwa nieco dłużej, bo ok. 0,069 s. W wielu przypadkach niskowymiarowych istnieją jeszcze większe wartości k takie, iż suma czasu wstępnej obróbki i czasu szukania NS dla wszystkich próbek zbioru odniesienia będzie niższa od czasu szukania najbliższego sąsiada dla wszystkich próbek metodą brute-force.

Jakie może być konkretne zastosowanie tej właściwości algorytmu? W pracy (Strzecha, 2001) przedstawiono metodę segmentacji obrazu dla potrzeb wysokotempe­raturowych pomiarów pewnych własności fizykochemicznych wybranych materiałów; algorytm Strzechy wykorzystuje regułę k-NN dla próbek w przestrzeni zaledwie dwóch cech. W przypadku, gdy liczba sąsiadów wynosi 1, można łatwo wykorzystać w tym zastosowaniu zaproponowaną metodę.

Przedstawiony algorytm można użyć także do szybkiego szukania k scentro­wanych sąsiadów (p. Rozdz. 7) w metryce miejskiej. W klasyfikatorze k-NCN dla każdego z kolejno szukanych sąsiadów możliwe jest ustalenie jego optymalnego położenia, tj. takiego, dla którego środek ciężkości układu sąsiadów pokrywałby się z zadaną próbką testową. Dzięki temu, i-ty sąsiad scentrowany może być pojmowany jako najbliższy sąsiad punktu będącego „przeciwwagą” środka ciężkości sąsiadów o indeksach 1, ..., i–1, co umożliwia bezpośrednie zastosowanie zaproponowanego algorytmu.



Pobieranie 6.5 Mb.

Share with your friends:
1   ...   33   34   35   36   37   38   39   40   ...   54




©operacji.org 2020
wyślij wiadomość

    Strona główna