О сервисе WebGround

Ваша тема


Новости сайта

Литература

обложка книгиИнтернетика. Навигация в сложных сетях: модели и алгоритмы
Большакова Е.И., Клышинский Э.С., Ландэ Д.В., Носков А.А., Пескова О.В., Ягунова Е.В. Автоматическая обработка текстов на естественном языке и компьютерная лингвистикаАвтоматическая обработка текстов на естественном языке и компьютерная лингвистика (pdf)
Ягунова Е.В., Макарова О.Е., Антонова А.Ю., Соловьев А.Н. Разные методы компрессии в исследовании понимания новостного текстаРазные методы компрессии в исследовании понимания новостного текста (pdf)
Крылова И.В, Пивоварова Л.М., Савина А.В., Ягунова Е.В. Исследование новостных сегментов российской «снежной революции»: вычислительный эксперимент и интуиция лингвистовИсследование новостных сегментов российской «снежной революции»: вычислительный эксперимент и интуиция лингвистов (pdf)
Ягунова Е.В. Исследование перцептивной устойчивости фонем как элементов речевой цепиИсследование перцептивной устойчивости фонем как элементов речевой цепи (pdf)
Ягунова Е.В. Вариативность структуры нарратива и разнообразие стратегий пониманияВариативность структуры нарратива и разнообразие стратегий понимания (pdf)
Ягунова Е.В., Пивоварова Л.М. Экспериментально-вычислительные исследования художественной прозы Н.В. ГоголяЭкспериментально-вычислительные исследования художественной прозы Н.В. Гоголя (pdf)
Ягунова Е.В. Вариативность стратегий восприятия звучащего текстаВариативность стратегий восприятия звучащего текста (pdf)
Ягунова Е.В. Спонтанный нарратив у детей и у взрослыхСпонтанный нарратив у детей и у взрослых (pdf)
Ягунова Е.В. Исследование избыточности русского звучащего текстаИсследование избыточности русского звучащего текста (pdf)
Ягунова Е.В. Фонетические признаки опорных сегментов и восприятие русского текстаФонетические признаки опорных сегментов и восприятие русского текста (pdf)
Ягунова Е.В. Коммуникативная и смысловая структура текста и его восприятиеКоммуникативная и смысловая структура текста и его восприятие (pdf)
Ягунова Е.В. Где скрывается смысл бессмысленного текста?Где скрывается смысл бессмысленного текста? (pdf)
Ягунова Е.В. Эксперимент в психолингвистике: Конспекты лекций и методические рекомендацииЭксперимент в психолингвистике: Конспекты лекций и методические рекомендации (pdf)
Ягунова Е.В. Теория речевой коммуникацииТеория речевой коммуникации (pdf)
Антонова А.Ю., Клышинский Э.С., Ягунова Е.В. Определение стилевых и жанровых характеристик коллекций текстов на основе частеречной сочетаемостиОпределение стилевых и жанровых характеристик коллекций текстов на основе частеречной сочетаемости (pdf)
Ягунова Е.В. Эксперимент и вычисления в анализе ключевых слов художественного текстаЭксперимент и вычисления в анализе ключевых слов художественного текста (pdf)
Ягунова Е.В. Ключевые слова в исследовании текстов Н.В. ГоголяКлючевые слова в исследовании текстов Н.В. Гоголя (pdf)
Пивоварова Л.М., Ягунова Е.В. Информационная структура научного текста. Текст в контексте коллекцииИнформационная структура научного текста. Текст в контексте коллекции (pdf)
Савина А.Н., Ягунова Е.В. Исследование коллокаций с помощью экспериментов с информантамиИсследование коллокаций с помощью экспериментов с информантами (pdf)
Ягунова Е.В., Пивоварова Л.М. От коллокаций к конструкциямОт коллокаций к конструкциям (pdf)
Пивоварова Л.М., Ягунова Е.В. Извлечение и классификация терминологических коллокаций на материале лингвистических научных текстовИзвлечение и классификация терминологических коллокаций на материале лингвистических научных текстов (pdf)
Julia Kiseleva. Grouping Web Users based on Query LogGrouping Web Users based on Query Log (pdf)
Julia_Kiseleva_Unsupervised_Query_Segmentation_Using_Click_Data_and_Dictionaries_Information.pdfUnsupervised Query Segmentation Using Click Data and Dictionaries Information (pdf)
Четыре лекции о методе
Начала предметного анализа методов (на примере метода Ф.Бэкона)
Вариативность стратегий восприятия звучащего текста
Извлечение и классификация коллокаций на материале научных текстов. Предварительные наблюдения
Природа коллокаций в русском языке. Опыт автоматического извлечения и классификации на материале новостных текстов
Войтишек А. Повторы. Лирические рефреныПовторы. Лирические рефрены (pdf)
Войтишек А. Новое. Лирические рефреныНовое. Лирические рефрены (pdf)
Войтишек А. Всё об одном и том жеВсё об одном и том же. 500 лирических рефренов к 50-летию (pdf)
Войтишек А. Тысяча-часть-1Тысяча-часть-1 (pdf)
Войтишек А. Тысяча-часть-2Тысяча-часть-2 (pdf)
Войтишек А. АлфавитАлфавит (pdf)

5.6.3. Алгоритм Salsa

 

Алгоритм ранжирования Salsa (Stochastic Approach for Link-Structure Analysis - Стохастический Алгоритм  Анализа Структуры Связей) [108] был предложен Ш. Мораном (Sh. Moran) и Р. Лемпелем (R. Lempel) как некоторый симбиоз  алгоритмов PageRank и HITS, позволяющий сократить последствия образования TKC – «тесно связанных сообществ» документов.

Как и в методе PageRank в случае Salsa предполагается модель случайного блуждания пользователя по веб-графу, однако предполагается наличие двухстороннего «серфинга». В соответствии с алгоритмом Salsa:

1. Из произвольного узла , пользователь случайным образом возвращается к узлу , который ссылается на . Выбор  делается случайно, при условии, что  узлы и  принадлежат  веб-графу.

2. Из  пользователь наугад переходит к узлу , если существует связь .

Веб-граф  (рис. 24 а) может быть преобразован в двудольный ненаправленный граф , (рис.  24 б) и определен как совокупность  , где  обозначает посредников,  - совокупность узлов-посредников (тех, из которых исходят ссылки),  - авторов,  - совокупность узлов-авторов (тех, на которые ведут ссылки). Необходимо отметить, что одни и те же узлы могут быть одновременно и авторами и посредниками.

  Каждая неизолированная страница  представлена в  одним или двумя узлами  и .  В этом двудольном графе Salsa реализует два разных  случайных перехода. При  каждом переходе  возможно «посещение» узлов только из одной из двух долей графа . 

ris21-1

а)                                              б)

Рис. 24: Salsa: конструкция двудольного графа

Каждый путь длины два в  представляет собой обход одной гиперсвязи (при прохождении от доли посредников к доле авторов в ), и отход вдоль гиперсвязи (при прохождении в обратном направлении). Это движение в обратном направлении напоминает танец сальса, который ассоциируется с названием данного алгоритма.

Так как посредники и авторы, относящиеся к теме  должны быть явно выражены в   (доступны из многих узлов благодаря прямым ссылкам или коротким путям), предполагается  что авторы из  и посредники из , относящиеся к теме , будут наиболее часто посещаемыми при случайных «блужданиях» пользователей.

В алгоритме Salsa исследуются две различных цепи Маркова, которые ассоциируются с этими случайными блужданиями: цепь на стороне авторов  (цепь авторов), и цепь на стороне посредников .

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

В [108] показано что, сходящиеся в процессе итерационного процесса вероятность перехода к узлу  как к автору,  имеет очень простую форму:

,

а вероятность возврата к узлу  как  к посреднику:

,

где  и  - некоторые константы, а и  - это количество исходящих и входящих ссылок, соответственно.

Р. Лемпель и С. Моран продемонстрировали, что алгоритм Salsa менее чувствителен к эффекту тесно связанных сообществ, чем HITS, но при условиях, что вручную в документах удаляются ссылки, не относящиеся к исследуемой теме.  Это требование на практике ведет к  большим издержкам, в результате чего  авторам пока не известно случаев использования этого алгоритма ранжирования в реально работающих системах.