Сеть следопытов

Метод обрезки плотных сетей для выделения ключевых связей.

Обоснование [ править ]

Отношения между набором элементов часто представляются в виде квадратной матрицы, записи которой представляют отношения между всеми парами элементов. Такие отношения, как расстояния, несходства, сходства, родство, корреляции, совпадения, условные вероятности и т. д., могут быть представлены такими матрицами. Такие данные также можно представить в виде сетей с взвешенными связями между элементами. Такие матрицы и сети чрезвычайно плотны, и их нелегко понять без какой-либо формы сокращения или сокращения данных.

Сеть поиска путей получается в результате применения метода обрезки, который удаляет более слабые звенья из (обычно плотной) сети в соответствии с длинами альтернативных путей (см. ниже). ^[1]^[2]^[3] Он используется в качестве метода психометрического масштабирования, основанного на теории графов , и применяется при изучении знаний, образования, ^[4] приобретение знаний , ментальные модели , ^[5] и инженерия знаний . Он также используется в создании сетей связи, ^[6] отладка программного обеспечения, ^[7] визуализация закономерностей научного цитирования , ^[8] поиск информации и другие формы визуализации данных . ^[9] Сети следопытов потенциально применимы к любой проблеме, решаемой теорией сетей .

Обзор [ править ]

Целью сокращения сети является выделение наиболее важных связей между элементами, представленными в сети. Это помогает упростить сбор задействованных связей, что ценно для визуализации данных и понимания основных отношений между элементами, представленными в сети.

Некоторые методы психометрического масштабирования начинаются с парных данных и дают структуры, раскрывающие основную организацию данных. Кластеризация данных и многомерное масштабирование — два таких метода. Масштабирование сети представляет собой еще один метод, основанный на теории графов . Сети Pathfinder создаются на основе матриц данных для пар объектов. Поскольку алгоритм использует расстояния, данные сходства инвертируются, чтобы получить различия для вычислений.

В сети поиска объектов объекты соответствуют узлам сгенерированной сети, а связи в сети определяются шаблонами близости. Например, если близость является сходством, ссылки обычно соединяют узлы с высоким сходством. Когда близость является расстоянием или несходством, связи будут соединять более короткие расстояния. Ссылки в сети будут ненаправленными, если близости симметричны для каждой пары объектов. Симметричная близость означает, что порядок объектов не важен, поэтому близость i и j такая же, как близость j и i для всех пар i,j . Если близости не симметричны для каждой пары, связи будут направленными.

Алгоритм [ править ]

Алгоритм поиска пути использует два параметра.

The $q$ Параметр ограничивает количество косвенных близостей, рассматриваемых при создании сети. $q$ является целым числом между $2$ и $n-1$ , включительно где $n$ количество узлов или элементов. Кратчайшие пути могут иметь не более $q$ ссылки. Когда $q=n-1$ , включены все возможные пути.
The $r$ Параметр определяет метрику, используемую для вычисления расстояния путей (см. расстояние Минковского ). $r$ действительное число между $1$ и $\infty$ , включительно.

Расстояние пути $d_{p}$ рассчитывается как: $d_{p}=(\sum _{i=1}^{k}l_{i}^{r})^{1/r}$ , где $l_{i}$ это расстояние $ith$ ссылка в пути и $2\leq k\leq q$ . Для $r=1$ , $d_{p}$ это просто сумма расстояний звеньев пути. Для $r=\infty$ , $d_{p}$ — максимальное из расстояний звеньев пути, поскольку $\lim _{r\rightarrow \infty }d_{p}=\max _{i=1}^{k}l_{i}$ . Ссылка обрезается, если ее расстояние больше минимального расстояния путей между узлами, соединенными ссылкой. К эффективным методам поиска минимальных расстояний относится алгоритм Флойда–Уоршалла (для $q=n-1$ ) и алгоритм Дейкстры (для любого значения $q$ ).

Сеть, созданная с определенными значениями $q$ и $r$ называется $PFNet(q,r)$ . Оба параметра приводят к уменьшению количества связей в сети по мере увеличения их значений. Сеть с минимальным числом связей получается, если $q=n-1$ и $r=\infty$ , то есть, $PFNet(n-1,\infty )$ .

При использовании данных порядковой шкалы (см. уровень измерения ) $r$ параметр должен быть $\infty$ потому что то же самое $PFNet$ будет результатом любого положительного монотонного преобразования данных о близости. Другие значения $r$ требуют данных, измеренных по шкале отношений. $q$ Параметр можно варьировать, чтобы получить желаемое количество связей в сети или сосредоточиться на большем количестве локальных связей с меньшими значениями $q$ .

По сути, сети поиска путей сохраняют кратчайшие возможные пути с учетом данных. Следовательно, ссылки удаляются, если они не находятся на кратчайших путях. $PFNet(n-1,\infty )$ будет минимальным связующим деревом для ссылок, определенных данными о близости, если существует уникальное минимальное связующее дерево. В целом, $PFNet(n-1,\infty )$ включает все ссылки в любом минимальном связующем дереве.

Пример [ править ]

Вот пример ненаправленной сети поиска путей, полученной на основе средних оценок группы аспирантов-биологов. Студенты оценивали родственность всех пар показанных терминов и вычисляли средний рейтинг для каждой пары. Сплошные синие ссылки — это $PFNet(n-1,\infty )$ (на рисунке отмечено «оба»). Пунктирные красные ссылки добавлены в $PFNet(2,\infty )$ . Для добавленных ссылок не существует путей из двух ссылок короче, чем расстояние ссылки, но есть по крайней мере один более короткий путь с более чем двумя ссылками в данных. Минимальное связующее дерево будет иметь 24 ссылки, поэтому 26 ссылок в $PFNet(n-1,\infty )$ подразумевает, что существует более одного минимального остовного дерева. Имеются два цикла, поэтому в наборе звеньев цикла есть связанные расстояния. Разрыв каждого цикла потребует удаления одного из связанных звеньев в каждом цикле.

Ссылки [ править ]

^ Шваневельдт, RW , изд. (1990). Ассоциативные сети Pathfinder: Исследования по организации знаний . Норвуд, Нью-Джерси: Алекс. ISBN 978-0893916244 .
^ Шваневельдт, RW ; Дюрсо, штат Форт; Дирхолт, Д.В. (1989). «Сетевые структуры в данных о близости». В Бауэре, Г. (ред.). Психология обучения и мотивации: достижения исследований и теории (PDF) . Том. 24. Нью-Йорк: Академик Пресс. стр. 249–284.
^ Шваневельдт, RW ; Дирхолт, Д.В.; Дюрсо, FT (1989). «Теоретико-графовые основы Pathfinder Networks» (PDF) . Компьютеры и математика с приложениями . 15 : 337–345.
^ Голдсмит, Т.; Джонсон, П.; Эктон, В. (1991). «Оценка структурных знаний». Журнал педагогической психологии . 83 (4): 88–96.
^ Кудикьяла, Великобритания; Вон, РБ (2005). «Понимание требований к программному обеспечению с использованием сетей Pathfinder: обнаружение и оценка ментальных моделей» . Журнал системного программного обеспечения . 74 (1): 101–108. дои : 10.1016/j.jss.2003.09.028 .
^ Шопе, СМ; ДеДжуд, Дж.А.; Кук, Нью-Джерси; Педерсен, Х. (2004). «Использование Pathfinder для создания коммуникационных сетей при когнитивном анализе задач» . Материалы ежегодного собрания Общества человеческого фактора и эргономики . 48 (3): 678–682. дои : 10.1177/154193120404800386 .
^ Серрано, Э.; Куинн, А.; Ботиа, Дж.А.; Кордон, О. (2010). «Отладка сложных программных систем с помощью сетей поиска». Информатика . 180 (5): 561–583.
^ Чен, К.; Песня (2017). «Инструменты и приложения для картирования науки». Представление научных знаний . Спрингер. стр. 57–137.
^ Криббин, Т. (2010). «Визуализация структуры результатов поиска документов: сравнение подходов теории графов». Визуализация информации . 9 (2): 83–97.

Другая информация [ править ]

Дополнительную информацию о сетях поиска путей и несколько примеров применения PFnet для решения различных задач можно найти в ссылках.

Книга 1990 года больше не издается. архивную копию глав в формате PDF Можно скачать .

Глава книги Бауэра 1989 года представляет собой статью, в которой кратко описываются сети поиска путей и некоторые приложения. PDF

Три статьи, описывающие быстрые реализации сетей поиска путей:

Герреро-Боте, В.; Сапико-Алонсо, Ф.; Эсиноса-Кальво, М.; Гомес-Кризостомо, Р.; Моя-Анегон, Ф. (2006). «Двоичный поиск пути: улучшение алгоритма поиска пути». Обработка информации и управление . 42 (6): 1484–1490. CiteSeerX 10.1.1.378.5375 . дои : 10.1016/j.ipm.2006.03.015 .
Кирин, А; Кордон, О; Сантамария, Дж; Варгас-Кесада, Б; Моя-Анегон, Ф (2008). «Новый вариант алгоритма Pathfinder для создания больших визуальных научных карт в кубическом времени». Обработка информации и управление . 44 (4): 1611–1623. дои : 10.1016/j.ipm.2007.09.005 .
Кирин, А.; Кордон, О.; Герреро-Боте, вице-президент; Варгас-Кесада, Б.; Моя-Анегон, Ф. (2008). «Быстрый алгоритм на основе MST для получения сетей следопытов». Журнал Американского общества информатики и технологий . 59 (12): 1912–1924. CiteSeerX 10.1.1.331.1548 . дои : 10.1002/asi.20904 .

(Два варианта Квирина и др. значительно быстрее. Хотя первый можно применять с $q=2$ или $q=n-1$ и любое значение для $r$ , последнее может быть применено только в тех случаях, когда $q=n-1$ и $r=\infty$ .)

Внешние ссылки [ править ]

[1] Шваневельдт, RW , изд. (1990). Ассоциативные сети Pathfinder: Исследования по организации знаний . Норвуд, Нью-Джерси: Алекс. ISBN 978-0893916244 .

[2] Шваневельдт, RW ; Дюрсо, штат Форт; Дирхолт, Д.В. (1989). «Сетевые структуры в данных о близости». В Бауэре, Г. (ред.). Психология обучения и мотивации: достижения исследований и теории (PDF) . Том. 24. Нью-Йорк: Академик Пресс. стр. 249–284.

[3] Шваневельдт, RW ; Дирхолт, Д.В.; Дюрсо, FT (1989). «Теоретико-графовые основы Pathfinder Networks» (PDF) . Компьютеры и математика с приложениями . 15 : 337–345.

[4] Голдсмит, Т.; Джонсон, П.; Эктон, В. (1991). «Оценка структурных знаний». Журнал педагогической психологии . 83 (4): 88–96.

[5] Кудикьяла, Великобритания; Вон, РБ (2005). «Понимание требований к программному обеспечению с использованием сетей Pathfinder: обнаружение и оценка ментальных моделей» . Журнал системного программного обеспечения . 74 (1): 101–108. дои : 10.1016/j.jss.2003.09.028 .

[6] Шопе, СМ; ДеДжуд, Дж.А.; Кук, Нью-Джерси; Педерсен, Х. (2004). «Использование Pathfinder для создания коммуникационных сетей при когнитивном анализе задач» . Материалы ежегодного собрания Общества человеческого фактора и эргономики . 48 (3): 678–682. дои : 10.1177/154193120404800386 .

[7] Серрано, Э.; Куинн, А.; Ботиа, Дж.А.; Кордон, О. (2010). «Отладка сложных программных систем с помощью сетей поиска». Информатика . 180 (5): 561–583.

[8] Чен, К.; Песня (2017). «Инструменты и приложения для картирования науки». Представление научных знаний . Спрингер. стр. 57–137.

[9] Криббин, Т. (2010). «Визуализация структуры результатов поиска документов: сравнение подходов теории графов». Визуализация информации . 9 (2): 83–97.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]