Una red Pathfinder es un psicométrica método de escala basada en la teoría de grafos y se utiliza en el estudio de los conocimientos, la adquisición de conocimientos , la ingeniería del conocimiento , científicos de citación patrones, la recuperación de información y visualización de datos . Las redes de Pathfinder son potencialmente aplicables a cualquier problema abordado por la teoría de redes .
Descripción general
Varios métodos de escalado psicométrico parten de datos de proximidad y producen estructuras que revelan la organización subyacente de los datos. La agrupación de datos y el escalado multidimensional son dos de esos métodos. El escalado de la red representa otro método basado en la teoría de grafos . Las redes de Pathfinder se derivan de proximidades para pares de entidades.
Las proximidades se pueden obtener a partir de similitudes, correlaciones, distancias, probabilidades condicionales o cualquier otra medida de las relaciones entre entidades. Las entidades son a menudo conceptos de algún tipo, pero pueden ser cualquier cosa con un patrón de relaciones.
En la red de Pathfinder, las entidades corresponden a los nodos de la red generada, y los enlaces en la red están determinados por los patrones de proximidades. Por ejemplo, si las proximidades son similitudes, los enlaces generalmente conectarán nodos de alta similitud. Los enlaces en la red no estarán dirigidos si las proximidades son simétricas para cada par de entidades. Las proximidades simétricas significan que el orden de las entidades no es importante, por lo que la proximidad de i y j es la misma que la proximidad de j e i para todos los pares i, j . Si las proximidades no son simétricas para cada par, los enlaces serán dirigidos.
Ejemplo
A continuación se muestra un ejemplo de una red de exploradores no dirigida derivada de las calificaciones promedio de similitud de un grupo de estudiantes graduados de biología. Los estudiantes calificaron la relación de todos los pares de términos mostrados y se calculó la calificación media para cada par. La red que se muestra es la PFnet (2, ∞).
Algoritmo
El algoritmo de Pathfinder utiliza dos parámetros.
- El parámetro q restringe el número de proximidades indirectas examinadas al generar la red. El parámetro q es un valor entero entre 2 y n - 1, inclusive donde n es el número de nodos o elementos.
- El parámetro r define la métrica utilizada para calcular la distancia de caminos (cf. la distancia de Minkowski ). El parámetro r es un número real entre 1 e infinito , inclusive.
Una red generado con valores particulares de q y r se llama un PFnet ( q , r ). Ambos parámetros tienen el efecto de disminuir el número de enlaces en la red a medida que aumentan sus valores. La red con el número mínimo de enlaces se obtiene cuando q = n - 1 y r = ∞, es decir, PFnet ( n - 1, ∞).
Con datos de escala ordinal (ver nivel de medición ), el parámetro r debe ser infinito porque el mismo PFnet resultaría de cualquier transformación monótona positiva de los datos de proximidad. Otros valores de r requieren datos medidos en una escala de razón. El parámetro q se puede variar para producir el número deseado de enlaces en la red.
Esencialmente, las redes de Pathfinder conservan las rutas más cortas posibles dados los datos, de modo que los enlaces se eliminan cuando no están en las rutas más cortas. El PFnet ( n - 1, ∞) será el árbol de expansión mínimo para los enlaces definidos por los datos de proximidad si existe un árbol de expansión mínimo único. En general, PFnet ( n - 1, ∞) incluye todos los enlaces en cualquier árbol de expansión mínimo.
Referencias
Puede encontrar más información sobre las redes de pioneros y varios ejemplos de la aplicación de las redes PF a una variedad de problemas en:
- Schvaneveldt , RW (Ed.) (1990) Redes asociativas de Pathfinder: Estudios en organización del conocimiento. Norwood, Nueva Jersey: Ablex. El libro está agotado. Se puede descargar una copia comprimida de los capítulos en pdf: zip
Un artículo más breve que resume las redes de pioneros:
- Schvaneveldt, RW, Durso, FT y Dearholt, DW (1989). Estructuras de red en datos de proximidad. En G. Bower (Ed.), La psicología del aprendizaje y la motivación: avances en la investigación y la teoría , vol. 24 (págs. 249-284). Nueva York: Academic Press. pdf
Tres artículos que describen implementaciones rápidas de redes de pioneros:
- Guerrero-Bote, V .; Zapico-Alonso, F .; Esinosa-Calvo, M .; Gomez-Crisostomo, R .; Moya-Anegon, F. (2006). "Pathfinder binario: una mejora del algoritmo de Pathfinder". Tratamiento y Gestión de la Información . 42 (6): 1484-1490. CiteSeerX 10.1.1.378.5375 . doi : 10.1016 / j.ipm.2006.03.015 .
- Quirin, A; Cordón, O; Santamaría, J; Vargas-Quesada, B; Moya-Anegón, F (2008). "Una nueva variante del algoritmo Pathfinder para generar grandes mapas de ciencia visual en tiempo cúbico". Tratamiento y Gestión de la Información . 44 (4): 1611–1623. doi : 10.1016 / j.ipm.2007.09.005 .
- Quirin, A .; Cordón, O .; Guerrero-Bote, vicepresidente; Vargas-Quesada, B .; Moya-Anegón, F. (2008). "Un algoritmo rápido basado en MST para obtener redes Pathfinder". Revista de la Sociedad Estadounidense de Ciencia y Tecnología de la Información . 59 (12): 1912-1924. CiteSeerX 10.1.1.331.1548 . doi : 10.1002 / asi.20904 .
(Las dos variantes de Quirin et al. Son significativamente más rápidas. Mientras que la primera se puede aplicar con q = 2 o q = n - 1 y cualquier valor para r , la última solo se puede aplicar en los casos en que q = n - 1 y r = ∞.)