Sieć Pathfindera

Pathfinder Network to psychometryczna metoda skalowania oparta na teorii grafów i stosowana w badaniach ekspertyz, pozyskiwaniu wiedzy , inżynierii wiedzy , wzorcach cytowań naukowych , wyszukiwaniu informacji i wizualizacji danych . Sieci Pathfinder mają potencjalne zastosowanie do każdego problemu, którym zajmuje się teoria sieci .

Przegląd

Kilka psychometrycznych metod skalowania zaczyna się od danych zbliżeniowych i struktur ujawniających podstawową organizację danych. Grupowanie danych i skalowanie wielowymiarowe to dwie takie metody. Skalowanie sieci to kolejna metoda oparta na teorii grafów . Sieci Pathfinder są wyprowadzane z bliskości par jednostek.

Bliskość można uzyskać na podstawie podobieństw, korelacji, odległości, prawdopodobieństw warunkowych lub dowolnej innej miary relacji między jednostkami. Jednostki są często pewnego rodzaju koncepcjami, ale mogą to być dowolne elementy ze wzorcem relacji.

W sieci pathfinder jednostki odpowiadają węzłom generowanej sieci, a łącza w sieci są określane przez wzorce bliskości. Na przykład, jeśli bliskości są podobieństwami, łącza będą generalnie łączyć węzły o wysokim podobieństwie. Powiązania w sieci będą niekierowane, jeśli odległości są symetryczne dla każdej pary podmiotów. Symetryczne bliskości oznaczają, że kolejność bytów nie ma znaczenia, więc bliskość i oraz j jest taka sama jak bliskość j oraz i dla wszystkich par i,j . Jeśli odległości nie są symetryczne dla każdej pary, połączenia będą skierowane.

Przykład

Oto przykład niekierowanej sieci tropicieli wywodzącej się ze średnich ocen podobieństwa grupy studentów biologii. Uczniowie ocenili pokrewieństwo wszystkich par pokazanych terminów i obliczono średnią ocenę dla każdej pary. Przedstawiona sieć to PFnet(2, ∞).

Algorytm

Algorytm pathfinder wykorzystuje dwa parametry.

Parametr q ogranicza liczbę pośrednich bliskości badanych podczas generowania sieci. Parametr q jest liczbą całkowitą z przedziału od 2 do n - 1 włącznie, gdzie n jest liczbą węzłów lub elementów.
Parametr r określa metrykę używaną do obliczania odległości ścieżek (por. odległość Minkowskiego ). Parametr r jest liczbą rzeczywistą z przedziału od 1 do nieskończoności włącznie.

Sieć wygenerowana z określonymi wartościami q i r jest nazywana PFnet( q , r ). Oba parametry powodują zmniejszenie liczby łączy w sieci w miarę zwiększania ich wartości. Sieć o minimalnej liczbie łączy otrzymujemy, gdy q = n − 1 i r = ∞, czyli PFnet( n − 1, ∞).

W przypadku danych w skali porządkowej (patrz poziom pomiaru ) parametr r powinien wynosić nieskończoność, ponieważ ten sam PFnet wynikałby z każdej dodatniej transformacji monotonicznej danych dotyczących bliskości. Inne wartości r wymagają danych mierzonych na skali ilorazowej. Parametr q można zmieniać, aby uzyskać żądaną liczbę łączy w sieci.

Zasadniczo sieci wyszukiwania ścieżek zachowują najkrótsze możliwe ścieżki danych, więc łącza są eliminowane, gdy nie znajdują się na najkrótszych ścieżkach. PFnet( n − 1, ∞) będzie minimalnym drzewem rozpinającym dla łączy zdefiniowanych przez dane bliskości, jeśli istnieje unikalne minimalne drzewo rozpinające. Ogólnie rzecz biorąc, PFnet( n − 1, ∞) zawiera wszystkie łącza w każdym minimalnym drzewie rozpinającym.

Więcej informacji na temat sieci pathfinder i kilka przykładów zastosowania sieci PF do różnych problemów można znaleźć w:

Schvaneveldt , RW (red.) (1990) Pathfinder Associative Networks: Studies in Knowledge Organization. Norwood, NJ: Ablex. Książka jest wyczerpana. Spakowaną kopię rozdziałów w formacie pdf można pobrać: zip

Krótszy artykuł podsumowujący sieci pathfinder:

Schvaneveldt, RW, Durso, FT i Dearholt, DW (1989). Struktury sieciowe w danych zbliżeniowych. W G. Bower (red.), Psychologia uczenia się i motywacji: postępy w badaniach i teorii , tom. 24 (s. 249–284). Nowy Jork: prasa akademicka. pdf

Trzy artykuły opisujące szybkie implementacje sieci pathfinder:

Guerrero-Bote, V.; Zapico-Alonso, F.; Esinosa-Calvo, M.; Gomez-Crisostomo, R.; Moya-Anegon, F. (2006). „Binary pathfinder: ulepszenie algorytmu pathfinder”. Przetwarzanie i zarządzanie informacją . 42 (6): 1484-1490. CiteSeerX 10.1.1.378.5375 . doi : 10.1016/j.ipm.2006.03.015 .
Quirin, A; Cordon, O; Santamaría, J; Vargas-Quesada, B; Moya-Anegon, F (2008). „Nowy wariant algorytmu Pathfinder do generowania dużych wizualnych map naukowych w czasie sześciennym”. Przetwarzanie i zarządzanie informacją . 44 (4): 1611–1623. doi : 10.1016/j.ipm.2007.09.005 .
Quirin, A.; Cordon, O.; Guerrero-Bote, wiceprezes; Vargas-Quesada, B.; Moya-Anegon, F. (2008). „Szybki algorytm oparty na MST do uzyskiwania sieci Pathfinder” . Journal of American Society for Information Science and Technology . 59 (12): 1912–1924. CiteSeerX 10.1.1.331.1548 . doi : 10.1002/asi.20904 .

(Dwa warianty Quirina i wsp. Są znacznie szybsze. Podczas gdy pierwszy można zastosować z q = 2 lub q = n - 1 i dowolną wartością dla r , drugi można zastosować tylko w przypadkach, gdy q = n - 1 i r = ∞.)

Linki zewnętrzne