Semantic WebAnalyzer
wyszukiwarka semantycznych słów kluczowych

Zasada działania systemu indeksowania Google, cz.2 - Tworzenie klastrów fraz powiązanych

Po pierwszej części indeksacji, w trakcie której na podstawie analizy milionów dokumentów nastąpiła identyfikacja fraz semantycznie znaczących, system indeksowania Google kontynuuje proces poprzez identyfikację fraz powiązanych o wysokim przyroście informacji oraz tworzenie klastrów tych fraz.

Część 2. - Tworzenie klastrów fraz powiązanych

Proces ten obejmuje następujące etapy i operacje funkcjonalne:

Etap 1: Identyfikacja fraz powiązanych o wysokim przyroście informacji

Przypomnijmy, że system dysponuje macierzą współwystępowania, która zawiera dobre frazy, z których każda przewiduje co najmniej jedną dobrą frazę. Teraz zostanie przeprowadzony proces identyfikacji takich fraz powiązanych, dla których zysk informacyjny znacznie przekracza próg przyjęty do wcześniejszej identyfikacji powiązań.

• Porównanie przyrostu informacji: Dla każdej pary dobrych fraz system sprawdza, czy wartość przyrostu informacji przekracza wysoko ustalony próg, np. 100. Taki próg oznacza, że frazy współwystępują 100 razy częściej, niż by to wynikało z ich przypadkowej wspólnej obecności w grupie losowych dokumentów.

• Filtrowanie fraz: Wszelkie pary fraz, dla których przyrost informacji jest mniejszy od progu wysokiej wartości informacyjnej są ostatecznie uznawane za niepowiązane i ich bit w macierzy współwystępowania jest zerowany.

Etap 2: Identyfikacja klastrów fraz powiązanych

Klaster to zbiór fraz powiązanych, w którym każda fraza ma wysoki zysk informacyjny w stosunku do co najmniej jednej frazy znajdującej się w tym klastrze.

• Proces tworzenia klastrów:

  • Każdy wiersz macierzy współwystępowania będzie zawierać przynajmniej jedną frazę powiązaną z frazą, która jest kluczem tego wiersza. Czyli dla każdej dobrej frazy zostaje wyodrębniony zbiór fraz z nią powiązanych.
  • Teraz dla każdej pary fraz znajdujących się wewnątrz tego zbioru system sprawdza, czy są powiązane (mają bit niezerowy). Jeśli tak, są częścią tego samego klastra.
  • W efekcie zostaje utworzony zbiór fraz, które są powiązane nie tylko z tą samą frazą kluczową, ale też przynajmniej z jedną inną frazą w tym zbiorze. Jest to klaster tematyczny.

Etap 3: Przechowywanie informacji o klastrach

Każdy klaster otrzymuje swój unikalny numer ID. Dzięki temu każda dobra fraza również otrzymuje unikalny numer ID, ponieważ jest frazą kluczową dla jakiegoś klastra.

• Wektory bitowe klastrów: Informacje o klastrach są przechowywane za pomocą wektorów bitowych, gdzie:

  • Długość wektora: Odpowiada liczbie wszystkich fraz w macierzy współwystępowania.
  • Bity w wektorze: Każda pozycja bitowa odpowiada kolejnej frazie w macierzy współwystępowania, a ich wzajemna relacja jest określona wartością 0 lub 1.

• ID klastrów: Każdemu klastrowi przypisywany jest unikalny numer identyfikacyjny, który jest wartością binarną jego wektora bitowego.

Załóżmy, że frazy A, B i C są ze sobą powiązane. Dodatkowo fraza C jest powiązana z frazą D. Wówczas macierz współwystępowania przyjmuje postać:

	A	B	C	D	ID Klastra
A	1	1	1	0	14
B	1	1	0	0	12
C	1	0	1	1	11
D	0	0	1	1	3

Wektory bitowe klastrów:

A ma wektor [1, 1, 1, 0], co daje ID klastra 14 - wektor niesie informację, że frazy A, B, C należą do klastra ID 14

B ma wektor [1, 1, 0, 0], co daje ID klastra 12 - wektor niesie informację, że frazy A, B należą do klastra ID 12

C ma wektor [1, 0, 1, 1], co daje ID klastra 11 - wektor niesie informację, że frazy A, C, D należą do klastra 11

D ma wektor [0, 0, 1, 1], co daje ID klastra 3 - wektor niesie informację, że frazy C, D należą do klastra ID 3

Ta sama fraza może należeć do różnych klastrów, a te niosą informacje o różnych powiązaniach między frazami.

Informacje o klastrach mogą być przechowywane w macierzy współwystępowania, w której dla każdej pary fraz A => B znajdą się dane:

wartość przyrostu informacji A=>B,
numer ID A,
wektor bitowy A.

Alternatywnie można je przechowywać bezpośrednio na liście dobrych fraz, w której każdy wiersz dotyczy jednej frazy kluczowej, np. dla A:

A = [numer ID A, wektor bitowy A, (lista powiązanych fraz (B, ..., D)), (wartości przyrostów informacji (A=>B, ..., A=>D))]

Dodatkowo lista fraz powiązanych z frazą kluczową może zostać uporządkowana zgodnie z ich przyrostem informacji od wartosci najwyższej do najniższej, co samo w sobie również stanowi użyteczną informację.

Rezultat procesu tworzenia klastrów fraz powiązanych

Dla każdej frazy kluczowej zostaje zidentyfikowany klaster, w którym zebrana jest uszeregowana w kolejności zysku informacyjnego lista fraz powiązanych z tą frazą i przynajmniej jedną inną frazą w klastrze. Zostaje utworzony wektor bitowy klastra zawierający informacje o relacji frazy kluczowej z wszystkimi zidentyfikowanymi przez system dobrymi frazami (0: brak powiązania lub 1: istniejące powiązanie). Wartość klastra jest jednocześnie jego unikalnym numerem ID, który zostaje przypisany do frazy kluczowej.

Takie podejście zapewnia nie tylko użyteczną organizację informacji, ale też uwzględnia, że frazy tworzą złożony graf relacji, w którym niektóre są powiązane z wieloma innymi frazami, a inne mają bardziej ograniczony zakres. Ich relacje mogą być wzajemne (każda fraza przewiduje drugą) lub jednokierunkowe (jedna fraza przewiduje drugą, ale nie na odwrót), a powiązania te mogą być bezpośrednie lub pośrednie przez inną frazę. W efekcie niektóre klastry mogą być unikalne względem jakiejś frazy, a niektóre mogą na siebie nachodzić, mając jedną lub więcej wspólnych fraz powiązanych.

Proces zapewnia bardzo skuteczny sposób identyfikacji powiązań semantycznych występujących w zbiorze dokumentów, a także parametryzuje je i sprowadza do postaci zoptymalizowanej pod kątem objętości danych, szybkości dostępu i łatwości wykorzystania w dalszych elementach wyszukiwarki.

© 2024 - 2025 semanticwebanalyzer.pl