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

RCDL Проблема Каталог vis поиск по индексу? Каталог vis поиск по индексу? Пополнение каталога: в ручную или автоматическое? Пополнение каталога: в ручную или автоматическое? Где искать и как искать новые ресурсы? Где искать и как искать новые ресурсы? Какую информацию использовать: контент и/или связь между документами? Какую информацию использовать: контент и/или связь между документами?

RCDL Подход Учет связи между документами (анализ топологии локального веб-графа) Учет связи между документами (анализ топологии локального веб-графа) Ценность веб-ресурса проявляется в его авторитетности (входящие ссылки) или концентрированности (исходщие) ссылки Ценность веб-ресурса проявляется в его авторитетности (входящие ссылки) или концентрированности (исходщие) ссылки Не все гиперссылки являются релевантными Не все гиперссылки являются релевантными Поиск веб-сообществ. Согласуется с отдельными интуитивными представлениями о характере связности между релевантными ресурсами, но не является совершенным инструментом Поиск веб-сообществ. Согласуется с отдельными интуитивными представлениями о характере связности между релевантными ресурсами, но не является совершенным инструментом Дополнительная проверка по контенту Дополнительная проверка по контенту

RCDL Построение веб-графа

RCDL Выбираются зерновые ресурсы (множество N 0 ). 2. Строится список узлов, имеющих ссылки хотя бы на один из зерновых ресурсов (при помощи запросов к системе Yandex.XML) – множество N Добавляются к полученному на этапе 2 списку зерновые ресурсы и проводится построение веб- графа до глубины 2 (т.е. максимальная длина кратчайшего пути в таком графе будет равна двум). 4. Кроме того, N 1 – множество ресурсов, на которые ссылаются узлы множества (N 0 U N 0 ), а - N 2 множество ресурсов, на которые ссылаются узлы из N 1. Построение веб-графа

RCDL Поиск компонент сильной связности (КСС) Для разбиения веб-графа G(V,E) на связанные компоненты был использован алгоритм Тарьяна Для разбиения веб-графа G(V,E) на связанные компоненты был использован алгоритм Тарьяна

RCDL Фильтрация Фильтрация производилась на основе оценки качества документов из КСС Фильтрация производилась на основе оценки качества документов из КСС Из зерновых ресурсов выделялись ключевые слова, характеризующие их тематику, затем происходило объединение этих слов в список, представляющий собой тематику веб- сообщества в целом. Далее, ключевые слова каждого члена веб- сообщества сравнивались с ключевыми словами тематики, и по степени их соответствия делался вывод о принадлежности к тематике. Из зерновых ресурсов выделялись ключевые слова, характеризующие их тематику, затем происходило объединение этих слов в список, представляющий собой тематику веб- сообщества в целом. Далее, ключевые слова каждого члена веб- сообщества сравнивались с ключевыми словами тематики, и по степени их соответствия делался вывод о принадлежности к тематике. Значение параметра t в алгоритме (своего рода топ-рейтинг ключевых слов) стоит выбирать, руководствуясь законами Ципфа. Значение параметра t в алгоритме (своего рода топ-рейтинг ключевых слов) стоит выбирать, руководствуясь законами Ципфа. Принятие решения о смысловом соответствии словоформ при сравнении ключевых слов может быть реализовано различными способами – от простого посимвольного сравнения, до усовершенствованных вариантов метода TF*IDF. Принятие решения о смысловом соответствии словоформ при сравнении ключевых слов может быть реализовано различными способами – от простого посимвольного сравнения, до усовершенствованных вариантов метода TF*IDF.

RCDL Фильтрация

9 Исходные данные Экперимент проводился на базе каталога Яндекс ( В качестве зерновых ресурсов использовались сайты разделов каталога Экперимент проводился на базе каталога Яндекс ( В качестве зерновых ресурсов использовались сайты разделов каталога Учеба/Науки/Технические науки Учеба/Науки/Технические науки Учеба/Науки/Гуманитарные науки/История/История России Учеба/Науки/Гуманитарные науки/История/История России

RCDL РазделУчеба/Науки/Технические науки Авиация и космонавтика (A) Авиация и космонавтика (A) Высокие технологии (HT) Высокие технологии (HT) Вычислительная техника и электроника (CHE) Вычислительная техника и электроника (CHE) Информатика, информационные системы (CSIS) Информатика, информационные системы (CSIS) Прочее (O) Прочее (O) Универсальное (U) Универсальное (U)

RCDL РазделУчеба/Науки/Технические науки Рубрика Кол-во зерен, Вх. ссылок, R Доменов вх.ссылок, DR R / DR 1A ,92 2HT ,61 3CHE ,49 4CSIS ,50 5O ,88 6U ,42

RCDL Раздел Учеба/Науки/Гуманитарные науки/История/История России Раздел Учеба/Науки/Гуманитарные науки/История/История России Археология (Arc), Археология (Arc), Военная история ( WH ), Военная история ( WH ), Генеалогия ( G ), Генеалогия ( G ), Древний мир ( Anc ), Древний мир ( Anc ), Новая и новейшая история ( N ), Новая и новейшая история ( N ), Прочее ( O ), Прочее ( O ), Средние века ( M ), Средние века ( M ), Универсальное ( U ), Универсальное ( U ), Этнография и история народов ( E ) Этнография и история народов ( E )

RCDL РазделУчеба/Науки/Гуманитарные науки/История/История России РазделУчеба/Науки/Гуманитарные науки/История/История России Рубрика Кол-во зерен Вх. ссылок, R Доменов вх.ссылок, DR R / DR 1Arc ,40 2WH ,17 3G ,92 4Anc21291,33 5N ,74 6O ,92 7M ,02 8U ,59 9E ,87

RCDL Кэширование документов Для хранения скачанных документов и последующих экспериментов с ними на жестком диске был организован кэш, содержащий папки (соответствующие именам доменов) и сами документы (внутри папок-доменов). Для хранения скачанных документов и последующих экспериментов с ними на жестком диске был организован кэш, содержащий папки (соответствующие именам доменов) и сами документы (внутри папок-доменов). Подрубрика веб-каталога Общий размер, Мбайт Папок (доменов), тысяч Файлов, тысяч История России Технические науки

RCDL Характеристики веб-графов Рубрика Размер графа V, узлов Доменов VDV / VD 1Aн/д 2HT ,68 3CHE ,74 4CSIS ,92 5Oн/д 6U ,62 Учеба/Науки/Технические науки (без использования прореживания гиперссылок)

RCDL Характеристики веб-графов Учеба/Науки/Технические науки (с параметром прореживания, равным 2)Учеба/Науки/Технические науки (с параметром прореживания, равным 2) Рубрика Размер графа V, узлов Доменов VDV / VD 1A ,11 2HT ,02 3CHE ,07 4CSIS ,16 5O ,93 6U ,25

RCDL Характеристики веб-графов Учеба/Науки/Гуманитарные науки/История/История России (с параметром прореживания, равным 2)Учеба/Науки/Гуманитарные науки/История/История России (с параметром прореживания, равным 2) Рубрика Размер графа V, узлов Доменов VDV / VD 1Arc ,24 2WH ,12 3G ,64 4Anc432904,8 5N ,71 6O ,75 7M ,25 8U ,91 9EPH ,28

RCDL Пересечения рубрик по вх. ссылкам Учеба/Науки/Технические науки Учеба/Науки/Технические науки AHTCHECSISOUВсего%Max% A ,22981,3 HT ,21747,5 CHE ,52753,8 CSIS ,72982,2 O ,41991,8 U ,61035,4

RCDL Пересечения рубрик по вершинам веб-графа Учеба/Науки/Технические науки (с параметром прореживания, равным 2)Учеба/Науки/Технические науки (с параметром прореживания, равным 2) AHTCHECSISOUВсего%Max% A HT CHE CSIS O U

RCDL Распределение вх. гиперссылок по зернам в рубриках

RCDL Схема эксперимента

RCDL Результаты по подрубрикеУчеба/Науки/Технические науки Рубриказерен размер КСС Средн. качество КСС Распределение оценки качества по узлам КСС 10,80,750,670,60,50,40,330,250.20Зерновых A* , в процентах:0,883,150,000,0510,640,2122,200,210,1525,7636,761,42 HT , в процентах:0,611,830,00 7,010,0016,160,00 30,7943,602,09 CHE , в процентах:0,846,720,000,8412,610,0022,690,00 23,5332,775,56 CSIS , в процентах:1,035,280,120,0314,360,1622,010,170,0924,6032,150,70 O* , в процентах:0,231,140,000,239,150,9221,740,000,4633,1832,952,24 U , в процентах:0,19 0,00 3,010,1912,520,280,0931,8351,690,75

RCDL Распределение оценки качества для узлов КСС (для подрубрики каталога Учеба/Науки/Технические науки) Результаты по подрубрике Учеба/Науки/Технические науки

RCDL Выбор зерновых ресурсов Исследовалась зависимость результата идентификации веб-сообществ (с последующей оценкой качества) от: выбора единственного зернового ресурса из рубрики (веб-граф строился на основе одноэлементного зернового множества) – схема Singles; выбора единственного зернового ресурса из рубрики (веб-граф строился на основе одноэлементного зернового множества) – схема Singles; размера зернового множества (наращивание множества происходило за счет инкрементного добавления зерен в порядке убывания их ранга r) - схема Reduced. размера зернового множества (наращивание множества происходило за счет инкрементного добавления зерен в порядке убывания их ранга r) - схема Reduced.

RCDL Результат для рубрики Universal из подрубрикиУчеба/Науки/Технические науки (схема Singles) ЗерноInL N(G), узлов N(DG), узлов E(G), ребер E(DG), ребер Размер КССMQWW * MQ 1http:// 2http:// 3http:// 4http:// 5http:// 6http:// 7http:// 8http:// 9http://listlib.narod.ru ,000,010,009 10http:// 11http:// 12http:// 13http://aimatrix.nm.ru ,00- 14http://zntu.edu.ua/RIC ,00- 15http:// 16http:// 17http://eko.org.ua ,00- Всего:2201,00

RCDL Параметры : InL - ранг зерна InL - ранг зерна N(G) - количество узлов в построенном модулем WebCrawler веб-графе G N(G) - количество узлов в построенном модулем WebCrawler веб-графе G N(DG) - количество узлов веб-графе после доменного укрупнения (DG) N(DG) - количество узлов веб-графе после доменного укрупнения (DG) E(G) - количество реберв веб-графе G E(G) - количество реберв веб-графе G E(DG) - количество ребер в веб-графе DG E(DG) - количество ребер в веб-графе DG MQ - среднее качество членов КСС (исключая зерновые) MQ - среднее качество членов КСС (исключая зерновые) W - удельный размер КСС (вес) W - удельный размер КСС (вес) Наибольшую оценку получили зерна: (НТП ВИРАЖ-ЦЕНТР - издатель научно- технических журналов), (НТП ВИРАЖ-ЦЕНТР - издатель научно- технических журналов), (Горячая линия-Телеком) (Горячая линия-Телеком) (БГУ - Научно-Техническая Продукция) (БГУ - Научно-Техническая Продукция) Результат для рубрики Universal из подрубрикиУчеба/Науки/Технические науки (схема Singles)

RCDL Результат для рубрики Universal из подрубрикиУчеба/Науки/Технические науки (схема Reduced) Кол- во зерен Размер графа G Размер дом. графа DG Всего сообществ Размер КСС, узлов Средняя оценка качества КСС Прирост кол-ва вход.ссыл ок InL Общее кол-во вход ссылок УзловРеберУзловРебер , , , , , , , , , , , , , , ,

RCDL Зависимость результата выявления веб-сообществ из веб-графа от количества выбранных зерен (для рубрики каталога Учеба/Науки/Технические науки/Универсальное) Результат для рубрики Universal из подрубрикиУчеба/Науки/Технические науки (схема Reduced)

RCDL Экспертная оценка Расчет показателей полноты и точности при автоматической фильтрации основывался на экспертной оценке релевантности элементов данной КСС по отношению к тематике рубрики. Использовалась шкала: 1 – да, 0.66 – скорее да, скорее нет, 0 - нет. Порог релевантности П р был равен 0.5 Расчет показателей полноты и точности при автоматической фильтрации основывался на экспертной оценке релевантности элементов данной КСС по отношению к тематике рубрики. Использовалась шкала: 1 – да, 0.66 – скорее да, скорее нет, 0 - нет. Порог релевантности П р был равен 0.5

RCDL Прореживание Как показали эксперименты, существенную часть построенного модулем WebCrawler веб-графа G составляют узлы, используемые для навигации внутри домена и другие малорелевантные для тематики ресурсы. И хотя значительная их часть удаляется после работы модуля DomainGraph (результат – доменный граф DG), приходится затрачивать существенную часть машинных ресурсов на их обработку на этапе построения веб-графа G модулем WebCrawler. Как показали эксперименты, существенную часть построенного модулем WebCrawler веб-графа G составляют узлы, используемые для навигации внутри домена и другие малорелевантные для тематики ресурсы. И хотя значительная их часть удаляется после работы модуля DomainGraph (результат – доменный граф DG), приходится затрачивать существенную часть машинных ресурсов на их обработку на этапе построения веб-графа G модулем WebCrawler. Прореживание: Прореживание: Из каждой страницы берётся только lim_num + ln (реальное количество ссылок) ссылок из одного домена Из каждой страницы берётся только lim_num + ln (реальное количество ссылок) ссылок из одного домена Ссылки выбираются случайно и равновероятно Ссылки выбираются случайно и равновероятно

RCDL Зависимость времени обработки t документа d от размера графа |V| Прореживание

RCDL Прореживание

RCDL Прореживание

RCDL Исследование большего числа рубрик Исследование большего числа рубрик Разработка подхода к оценке полноты и точности всей методики в целом Разработка подхода к оценке полноты и точности всей методики в целом Возможно: исследование других веб- каталогов Возможно: исследование других веб- каталогов Отдельное направление: оценка веб-ресурсов на основе исследования корреляции между рубриками веб-каталога Отдельное направление: оценка веб-ресурсов на основе исследования корреляции между рубриками веб-каталога Направления дальнейшего исследования

RCDL Компании Яндекс за грантовую и техническую поддержку Благодарности

RCDL Вопросы

RCDL Спасибо за внимание!