SYSTEM INFORMACYJNY jest określany jako S = < X, A, V, ρ > gdzie:

• X = { X₁ , X₂ , .... X_n } - skończony zbiór obiektów systemowych. Obiektem jest każdy byt dla którego tworzony jest system.

• A = { A₁ , A₂ , .... A_n } - skończony zbiór atrybutów systemu. Atrybut - cecha, którą opisujemy obiekty np. autor książki, tytuł, wydawca itp. (zbiór cech, którymi są opisane obiekty).

• suma logiczna wartości atrybutów dla każdego atrybutu V_ai = { V_Ai , ...... V_An } np. kolor oczu {niebieskie, brązowe piwne itp. }

• ρ_i - funkcja informacji X × A → V ρ (X, a) = V gdzie X obiekt (element), a - atrybut, v - nazwa Funkcja ρ parze obiekt element - atrybut przyporządkowuje nazwę i nosi nazwę FUNKCJI INFORMACJI. Funkcja informacji pozwala opisać każdy obiekt poprzez ciąg przyjętych atrybutów - podaje pełną informację o obiekcie. Informacja jest pełna jeżeli dla każdego atrybutu możemy przypisać wartość

Dwa elementy są nierozróżnialne ze względu na atrybut A wtedy i tylko wtedy, gy funkcja na tym argumencie jest taka sama.

x ~_a y ⇔ ρ_X (a) = ρ_Y (a)

x i y są równoważne, ze względu na atrybut a

x₂ ~_{rok wydania} x₄ ; x₁ ~_wydawca x₃ ; x₁ ~_dziedzina x₂

RÓWNOWAŻNOŚĆ W SYSTEMIE

Dwa obiekty są równoważne w systemie S jeżeli dla każdego atrybutu A zachodzi zależność

x ~_S y ⇔ ∧_a∈A ρ_X (a) = ρ_Y (a)

x₂ ~_{rok wydania} x₄ ; x₂ ~_wydawca x₄ ; x₂ ~_dziedzina x₄ ; x₂ ~_S x₄

Obiekty nierożróżnialne w systemie należą do tej samej klasy równoważności.

KLASA RÓWNOWAŻNOŚCI

1. Klasą równoważności nazywamy najmniejszy zbiór atrybutów opisywalny w systemie, także która da się opisać przez atrybuty sytemu.

1. Klasa równoważności - zbiór obiektów nierozróżnialnych w systemie.

Każdy atrybut dzieli system na KLASY OBIEKTÓW

~ _{Rok Wydania} = { x₁ , x₃ } ∪ { x₂ , x₄ }

~ _Wydawca = { x₁ , x₃ } ∪ { x₂ , x₄ }

~ _Dziedzina = { x₁ , x₂ , x₄ } ∪ { x₃ }

~ _S = { x₂ , x₄ } ∪ { x₁ } ∪ { x₃ }

Parę atrybut - wartość (a, v) gdzie a∈A , v∈V_a nazywamy DESKRYPTOREM.

JĘZYKIEM DESKRYPTOROWYM L_S nazywamy język systemowy, który jest językiem opisu w kartotece wyszukiwawczej, równocześnie język pytań i odpowiedzi w systemie.

L_S = <A, G> gdzie L_S - język deskryptorowy; A - alfabet; G - gramatyka dwustopniowa (składa się z symantyki i syntaktyki).

Definicja języka jest adaptowana do zadanego systemu informacyjnego.

ALFABET

1. 0,1 ∈ A

1. A , V ∈ A gdzie A - zbiór wartości nazw atrybutów; V - zbiór wartości;

1. ( , ) ∈ A

1. +, ⋅ , ~ ∈ A gdzie ~ - negacja (NEG)

GRAMATYKA

SYNTAKTYKA - określa zasady tworzenia słów w danym języku

TERMY - słowa w języku deskryptorowym

T - zbiór termów - zbiór słów w języku deskryptorowym

1. 0,1 ∈ T

1. (a , v) ∈ T - deskryptor jest słowem w tym języku

1. t , t' ∈ T - jeżeli należą do języka to słowami języka są również:

~ t ∈ T

t + t' ∈ T

t ⋅ t' ∈ T + - „lub” ⋅ - „i”

(Wydawnictwo, PWN) ∈ T - Słowo w języku deskryptorowym

(Rok Wydania, 1990) + (Dziedzina, Informatyka) ∈ T

(Rok Wydania, 1990) ⋅ (Wydawnictwo, PWN) ∈ T

~ (Wydawnictwo, PWN) + (Rok Wydania, 1990) ⋅ (Dziedzina, Informatyka) + (Dziedzina, Elektronika) ∈ T

SEMANTYKA - określa znaczenie słów. Semantyka w języku deskryptorowym je określona jako: σ : T → X σ - odwzorowuje zbiór term w zbiór obiektów.

1. σ (0) = ∅ σ (1) = X (pełny zbiór obiektów;

1. σ (a, v) = { x ∈ X , ρ_X (a) = V }

1. σ (~t) = X \ σ (t)

σ (t + t') = σ (t) ∪ σ (t')

σ (t ⋅ t') = σ (t) ∩ σ (t')

Term T nazywamy termem elementarnym jeżeli jest on iloczynem wartości ze wszystkich atrybutów systemu. Term elementarny jest iloczynem deskryptorów po wszystkich atrybutach systemu.

t = (a₁ , V₁) ⋅ (a₂ , V₂) ⋅ . . . ⋅ (a_n , V_n)

t_E = d₁ ⋅ d₂ ⋅ . . . ⋅ d_n d - deskryptory

Własności termów elementarnych:

1. Wartości termów elementrnych są rozłączne (zbiór termów elementarnych w systemie są zbiorami elementarnymi).

σ(t₁) ∩ σ(t₂) = φ t₁ , t₂ ∈ T_E σ - z semantyki - znaczenie termu → wartość termu.

2. Suma logiczna sumy wartości termów odpowiadająca wszystkim termom elementarnym daje pełny zbiór obiektów w systemie.

Term T nazywamy termem normalnym jeżeli term ten jest sumą termów elementarnych.

t = t₁ + t₂ + . . . + t_n t₁ , t₂ , . . . , t_n ∈ T_E

Term T nazywamy termem składowym jeżeli jest on iloczynem deskryptorów nie po wszystkich atrybutach systemu.

t = (a₁ , V₁) ⋅ (a₂ , V₂) ⋅ . . . ⋅ (a_k , V_k) k<n

t_E = d₁ ⋅ d₂ ⋅ . . . ⋅ d_k k<n d - deskryptory

W systemie częściej opisuje się term składowy niż elementarny choć term elementarny jest szczególnym przypadkiem termu składowego.

Sumę termów składowych, nie konieczne elementarny nazywać będziemy termem składowym.

Powiemy, że termy t₁ i t₂ są równe w systemie t₁ = t₂ wtedy i tylko wtedy gdy wartości tych termów są równe

t₁ = t₂ ⇔ σ(t₁) = σ(t₂)

Powiemy, że term t₁ jest zawarty w termie t₂ w systemie S wtedy i tylko wtedy gdy zbiór wartości obiektów odpowiadających termowi t₂ jest zbiorem węższym niż zbiór odpowiadający termowi t₁.

t₁ ≤ t₂ ⇔ σ(t₁) ⊆ σ(t₂)

metoda list inwersyjnych

Algorytm wyszukiwania :

1) pobierz pierwszy deskryptor pierwszego termu składowego

2) wygeneruj listę obiektów relewantnych do tego deskryptora

3) jeśli nie ma już następnych deskryptorów w tym termie składowym to przejdź do pkt. 8

4) pobierz następny deskryptor pytania

5) wygeneruj listę obiektów relewantnych do tego deskryptora

6) dokonaj przecięcia na dotychczas wygenerowanych listach

7) przejdź do 3

8) zapamiętaj wygenerowaną listę

9) jeśli nie ma już następnych termów składowych to przejdź do 17

10) pobierz pierwszy deskryptor następnego temu składowego

11) wygeneruj listę obiektów relewantnych do tego deskryptora

12) jeśli nie ma już następnych dekryptorów w tym termie składowym to przejdź do pkt 8.

13) pobierz następny deskryptor pytania

14) wygeneruj listę obiektów relewantnych do tego deskryptora

15) dokonaj przecięcia na dotychczas wygenerowanych dla tego termu składowego listach

16) przejdź do 12

17) Podaj na wyjście sumę zapamiętanych list

OPIS METODY WYSZUKIWANIA (tworzenie kartoteki wyszukiwawczej, proces wyszukiwania)

System wyszukiwania informacji zadany jest jak w innych systemach, poprzez określenie zbioru X, zbioru atrybutów A, zbioru wartości V oraz funkcji informacji ρ - S = < X, A, V, ρ > . W systemie Saltona zbiorem obiektów X jest zbiór dokumentów w języku naturalnym. Funkcja informacji ρ określa opis danego dokumentu.

W metodzie Saltona wszystkie obiekty (dokumenty) dzieli się na podgrupy X_i (i = 1 . . . m), przy czym te podgrupy stanowią pewne grupy dokumentów podobnych.

Każda utowrzona grupa X_i składa się z reprezentanta C_i , który jest nazywany centroidem i ze zbioru obiektów (dokumentów) należących do tej grupy. W miejsce centoida (C_i) może występwać profil grupy P_i.

X_i = (C_i, {t_Xi}).

Centroid jest pewnym zbiorem pojęć (wykorzystywany w algorytmie Rocchia), a profil jest jego odpowiednikiem (kodem) numerycznym (ewentualnie numerem grupy), tworzonym w grupowaniu algorytmem Doyle'a.

Istnieje wiele algorytmów grupowania, przy czym najbardziej popularne i najczęściej używane są dwa: algorytm Rocchia i algorytm Doyle'a. W algorytmie Rocchia (jak już wcześniej wspomniano) reprezentatem grupy jest centroid, zaś w algorytmie Doyle'a reprezentatem grupy jest profil.

Proces zakładania kartoteki wyszukiwawczej polega na przeprowadzeniu algorytmu grupowania dokumentów jedną z dwóch powyższych metod. Po założeniu kartoteki wyszukiwawczej proces wyszukiwania może być przeprowadzony metodą sekwencyjną lub metodą strukturalną. Metoda strukturalna jest orginalną metodą Saltona (metoda wyszukiwania Saltona).

ZAKŁADANIE KARTOTEKI WYSZUKIWAWCZEJ

Algorytm Rocchia (algorytm wiązania dokumentów w grupy)

1. Spośród wszystki dokumentów niezwiązanych wybieramy dokument, ktory stanowi przypuszczalne centrum grupy i obliczamy współczynnik korelacji tego dokumentu ze wszystkimi dokumentami tego zbioru.

2. Wybrany dokument poddajemy testowi gęstości. Test ten mówi, że co najmniej N₁ dokumentów musi mieć współczynnik korelacji z wybranym dokumentem większy bądź równy od założonego parametru p₁ i co najmniej N₂ dokumentów musi mieć współczynnik korelacji z wybranym dokumentem większy bądź równy od założonego parametru p₂, gdzie spełnione są następujące warunki: N₁ ≥ p₁ N₂ ≥ p₂ p₂ > p₁ N₂ < N₁ . Test ten gwarantuje, że dokumenty z brzegu grup nie będą wybrane jako centrum.

3. Jeżeli wybrany dokument przeszedł test gęstości - został uznany jako centrum grupy, to na podstawie rozpiętości granic grupy i rozkładów współczynnika korelacji określa się wartość progową współczynnika korelacji p_min. p_min będzie równe p₁ (p_min = p₁) jeśli mniej dokumentów niż wynosi minimalny rozmiar grupy ma współczynnik korelacji większy od p₁. W każdym innym przypadku p_min wybiera się jako współczynnik korelacji dokumentu, przy ktorym nastąpiła największa różnica pomiędzy kolejnymi współczynnikami korelacji dokumentów sąsiadujących z grupą maksymalną. Liczba dokumentów w grupie minimalnej jest określana jako M₁, zaś grupy maksymalnej jako M₂.

4. Tworzymy wektor centroidalny, czyli centroid z terminów czy pojęć tych dokumentów, które należą do grupy minimalnej.

Definicje SA.:

1. S.A. nazywamy zbiór X_E∈X, taki że σ(t_E) = X_E, t_E∈T_E

2. S.A. jest zbiorem będącym odpowiedzią na term elementarny

3. S.A. jest to najmniejsza klasa równoważności w systemie

4. Podzbiór obiektów nierozróżnialnych w systemie związanych z danym termem elementarnym

5. Najmniejszy rozróżnialny zbiór obiektów w systemie.

6. S.A. - zbiór obiektów o takim samym opisie, o takiej samej informacji o obiekcie (funkcji ρ_X)

7. Relacja równoważności ze względu na cały zbiór atrybutów systemu dzieli zbiór obiektów X na klasy abstrakcji będące zbiorami elementarnymi, czyli składowymi atomowymi:

B(x),B(y) - klasy abstrakcji

Klasy równoważności:

1. Zbiór obiektów nierozróżnialnych ze względu na atrybut

2. Zbiór obiektów dla których funkcja informacji zwraca tą samą wartość

Językiem deskryptorowym L_S nazywamy język systemowy, który jest językiem opisu w kartotece wyszukiwawczej, równocześnie język pytań i odpowiedzi w systemie; jest szczególnym przypadkiem języka informacyjnego; jest definiowany jako para: L_S = <A, G> gdzie A - alfabet; G - gramatyka dwustopniowa (składa się z semantyki i syntaktyki). Definicja języka jest adaptowana do zadanego systemu informacyjnego.

ALFABET - określa wszystkie symbole, które występują w języku

1. 0,1 ∈ A - wartości typu logicznego służą do oznaczania zbioru pełnego i pustego;

1. A , V ∈ A gdzie A - zbiór wartości nazw atrybutów; V - zbiór wartości;

2. ( , ) ∈ A

3. +, ⋅ , ~ ∈ A gdzie ~ - negacja (NEG)

GRAMATYKA jest definiowana dwustopniowo:

SYNTAKTYKA - określa zasady tworzenia słów w danym języku (TERMY - słowa w języku deskryptorowym, T - zbiór termów - zbiór słów w języku deskryptorowym)

1. 0,1 ∈ T

1. (a , v) ∈ T - deskryptor jest słowem w tym języku

1. t , t' ∈ T - jeżeli należą do języka to słowami języka są również: ~ t ∈ T ; t + t' ∈ T ; t ⋅ t' ∈ T + - „lub” ⋅ - „i”

2. Pytanie do systemu jest również termem

SEMANTYKA - określa znaczenie słów (znaczeniem słów są obiekty). Semantyka w języku deskryptorowym je określona jako: σ : T → X σ - odwzorowuje zbiór term w zbiór obiektów. Jeżeli obiekty będą opisane termami to pytanie kierowane do systemu jest termem, a znalezienie odpowiedzi na pytanie jest nadaniem znaczenia termom tego pytania.

1. σ (0) = ∅ σ (1) = X (pełny zbiór obiektów);

1. σ (a, v) = { x ∈ X , ρ_X (a) = V }

1. σ (~t) = X \ σ (t) ; σ (t + t') = σ (t) ∪ σ (t') ; σ (t ⋅ t') = σ (t) ∩ σ (t')

---