Разработка специального математического и программного обеспечения выявления веб-сообществ в информационно-поисковых системах

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

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

Существует ряд авторитетных международных конференций по информационному поиску, посвященных, в том числе, обсуждению вопросов информационного поиска в сети Интернет. Это такие известные конференции как TREC (http://trec.nist.gov), SIGIR (http://www.sigir.org), WWW Conference (http://www2006.org) и некоторые другие: CIKM (http://www.cikm.org), SIGMOD (http://www.sigmod.org), KDD (http://www.acm.org/sigs/sigkdd/). Высокий авторитет конференций TREC, SIGIR, WWW и участие в них ведущих исследовательских коллективов и разработчиков технологий информационного поиска во многом определяет приоритетные направления исследований и задает общие принципы развития поисковых систем.

Кроме того, существует три российские конференции, заслуживающие внимания: DIALOG-21 (http://www.dialog-21.ru), RCDL http://www.rcdl2006.uniyar.ac.ru) и РОМИП (http://romip.narod.ru).

Последние крупные исследования по оценке мировых информационных ресурсов и в том числе ресурсов сети Интернет проводились в 2000 и 2003 годах [72,73] и ожидаются в 2007. По данным за 2003 год суммарный объём веб-ресурсов составлял 92 017 терабайт, из них 167 терабайт принадлежало так называемому, «поверхностному» Интернет (surface Web) и 91 850 терабайт — «глубинному» Интернет (deep Web). Под «поверхностным» Интернет понимаются ресурсы, в основном в виде статичных страниц HTML, а под «глубинным» — те ресурсы которые, генерируются по запросу — т. е. это сайты, управляемые базами данных и активными языками разметки типа РНР и ASP. К этому гигантскому объёму информации в 2003 году имело доступ порядка 600 млн. человек [73].

По сравнению с подобными крупномасштабными исследованиями, выполненными в 2000 году [72], объём данных вырос с 20 — 50 до 167 терабайт для «поверхностного» Web. А если учесть, что «глубинный» Web по некоторым оценкам [73] обычно больше в 400−450 раз, то и его объём за 3 года увеличился в 3 раза. Если предположить сохранение подобной динамики, то в 2006 году объём накопленной информации составил порядка 270 ООО терабайт.

Не стоит также забывать и о многократном росте количества пользователей Сети, особенно за счёт появления в их рядах людей, не имеющих компьютеров, но пользующихся Мобильным Интернетом (МИ). Их потенциальное число сегодня составляет более 2 млрд. человек, и есть уверенность, что это наложит свой отпечаток на дальнейшее развитие всемирной Сети.

Одной из задач, призванных решить проблему доступа к необходимой информации при такой скорости роста Сети, является изучение закономерностей в системе её гиперсвязей. Принято считать, что Сеть — это распределенный гипертекст. Однако это не совсем так. Гипертекст обычно подразумевает наличие концептуальной модели, которая накладывает ограничения согласованности на данные и гиперсвязи. В Сети подобной модели обычно не существует даже для тех её частей, которые находятся под единым административным контролем.

Как показали многие исследования [79,84,86], структура гипертекстовых ссылок в Сети подчиняется степенному закону и законам Зипфа [82], что характерно для многих других структур, созданных человеком. При этом другие классические распределения, например распределение Пуассона, используемые для описания случайных сетей и графов, в данном случае не наблюдаются.

В современных информационно-поисковых системах (далее ИПС) Интернет данные закономерности не используются в достаточной мере, несмотря на то, что в ряде работ [78,79,83,87 и др.] исследуется возможность применения в информационном поиске уникальных свойств сети Интернет, не присущих другим коллекциям данных, для которых разрабатывалась и на которых апробировалась классическая теория поиска. Ключевым в подобных исследованиях является то, что Интернет есть не только «склад информации», но и динамически изменяющаяся неоднородная Сеть, в которой всё более явно проявляются процессы самоорганизации. Тем сложнее становится её анализ не только в качественном, но и в количественном отношении — число гиперссылок во много раз превышает число самих веб-ресурсов, количество которых, как было показано выше, уже измеряется миллиардами. Феномен самоорганизации в сети Интернет приводит к формированию всё более сложных структур — веб-сообществ, анализ которых потенциально может существенно улучшить эффективность классического поиска. Подобные самоорганизованные структуры и являются предметом исследования данной работы.

В литературе [70] даётся следующее неформализованное и наиболее общее определение понятия веб-сообщество: веб-сообщество — это множество веб-ресурсов, связанных общей тематикой. Соответственно, задача идентификации веб-сообществ представляет собой задачу выделения множества веб-ресурсов, связанных общей тематикой. В зависимости от конкретных требований к веб-сообществам (например, степень ссылочной связанности входящих в них веб-ресурсов) способы идентификации веб-сообществ могут существенно отличаться. В данной работе в основном рассматривается идентификация веб-сообществ на основе анализа ссылочной связанности веб-графа, что сводит задачу идентификации веб-сообществ к задаче нахождения веб-подграфа (часто с последующей обработкой). Решение задачи идентификации веб-сообществ имеет ряд важных практических приложений и может использоваться при разработке автоматических веб-порталов и рубрикаторов, поисковых систем направленного действия (так называемый вертикальный поиск), а также для расширения возможностей поисковых систем, основанных на текстовом поиске.

Первая модель идентификации веб-сообществ была предложена в работе 1998 г. Гибсона (D. Gibson), Клейнберга (J. Kleinberg) и Рахавана (Р. Raghavan) [70]. Она была основана на извлечении веб-сообществ с помощью алгоритма ранжирования в поисковых системах, получившего название HITS (Hyperlink-Induced Topic Search) [78]. Далее в 1999;2000 гг. несколько исследователей и, прежде всего, Рахаван обобщили полученные закономерности, наблюдаемые при самоорганизации в Сети, и предложили ряд моделей, описывающих структуру Интернет [59,80], в том числе и веб-сообщества. Первые работы, развивающие идею идентификации веб-сообществ как отдельное направление и использующие альтернативные подходы (т.е. не основанные на HITS и т. п.), были опубликованы в 2000;2002 гг. Флэйком (G. Flake), Лоуренсом (S. Lawrence) и Гайлсом (С. L. Giles) [65,67]. Позже, в 2002;2004 гг. японские исследователи Ямафуджи (N. Imafuji) и Китсурегава (М. Kitsuregawa) провели подробный анализ работ Флэйка и других, выявив их недостатки и предложив улучшенные методы по идентификации веб-сообществ [74−76].

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

Анализ существующих работ Флейка, Лоуренса, Гайлса, Ямафуджи и Китсурегава, посвященных процессам самоорганизации в Интернет и идентификации веб-сообществ в интересах информационного поиска, выявил незначительное число проведённых исследований. При этом готовых и апробированных решений (способных непосредственно интегрироваться в существующие информационно-поисковые системы) ещё практически не существует, что во многом связано с отсутствием достаточно проработанной теории и практики решения задач идентификации веб-сообществ и масштабностью требуемых исследований. В тоже время учёт подобных факторов, как показывает анализ, выполненный в работах Д. Д. Козлова и А. А. Беловой [29], позволяет существенно повысить как эффективность функционирования информационно-поисковых систем, так и сформировать соответствующие рекомендации для их пользователей.

В имеющихся публикациях, рассматривающих вопросы идентификации самоорганизованных веб-сообществ в сети Интернет, не учитываются многие реалии современной Сети и, прежде всего: существование «ложных» гиперссылочных связей, не характеризующих тематику веб-сообщества, но внешне удовлетворяющих всем предъявляемым критериям. Подобные факторы вызывают появление так называемых страниц-шумов, фактически не соответствующих тематике. Кроме того, имеет место постепенное вытеснение поверхностного Web динамическими ресурсами, что приводит к неадекватности результатов, полученных на основе реконструкций веб-графов, не учитывающих глубинный Web (т.е. ресурсы, генерируемые по запросу с помощью различных технологий с применением баз данных).

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

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

В соответствии с указанной целью в работе поставлены и решены следующие основные задачи:

1. Анализ современных подходов к исследованию процессов самоорганизации в сети Интернет и идентификации самоорганизованных веб-сообществ.

2. Математическое моделирование веб-графов в интересах понимания процессов самоорганизации в Сети и анализа алгоритмов идентификации веб-сообществ.

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

4. Разработка программного обеспечения для проведения анализа структуры Сети, идентификации и оценки веб-сообществ.

5. Проведение экспериментальных исследований для проверки разработанных алгоритмов и моделей с выработкой рекомендаций по их практическому применению в информационно-поисковых системах.

Научная новизна. К основным результатам работы, отличающимся научной новизной, относятся:

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

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

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

4. Структура и способы организации данных программного обеспечения, реализующего полный цикл решения задач идентификации, анализа и оценки качества самоорганизованных веб-сообществ и отличающегося применением разработанных моделей и алгоритмов, ориентированных на работу с веб-графами с учётом выявленных закономерностей в структуре Сети.

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

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

Реализация и внедрение результатов работы. Основные теоретические и практические результаты диссертационной работы реализованы в виде специальной информационной системы исследования процессов самоорганизации в Сети. Система была использована для анализа процессов самоорганизации воронежского сегмента Интернет, сети Воронежского госуниверситета и российской части Мобильного Интернета, а также в учебном процессе Воронежского госуниверситета при разработке учебных курсов «Информационно-поисковые системы» и «Корпоративные информационные системы», что подтверждается соответствующими актами внедрения. Результаты работы были использованы при выполнении гранта ООО «Яндекс» № 67−05/07.

Апробация работы. Основные положения и результаты работы обсуждались и получили одобрение на Международной научно-технической конференции «Кибернетика и технологии XXI века» (Воронеж, 2004, 2006) — Всероссийской научной конференции «Научный сервис в сети Интернет» (Новороссийск, 2003, 2004, 2005) — Региональной научно-методической конференции «Информатика: проблемы, методология, технологии» (Воронеж, 2004, 2005, 2006) — Всероссийской научно-методической конференции «Телематика» (Санкт-Петербург, 2004, 2006) — Всероссийской научной конференции «Электронные библиотеки» (Переславль-Залесский, 2007).

Публикации. Основные результаты диссертации опубликованы в 15 научных работах, из них 2 — в изданиях, рекомендованных ВАК РФ.

Объём и структура диссертационной работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы, включающего в себя 97 наименований, и одного приложения. Основная часть работы изложена на 166 страницах, содержит 13 таблиц и 52 рисунка.

Выводы по главе.

1. Проведено обобщение и уточнение известных результатов в части экспериментальных исследований поведения потоковых методов идентификации веб-сообществ на различных типах веб-графов, к которым приводят разные стратегии их реконструкции. Из полученных результатов следует, что на полных веб-графах коэффициент ёмкости пропускных способностей рёбер не влияет на количество идентифицируемых членов веб-сообщества для алгоритмов, реализованных на основе метода FLG. На частичных веб-графах такая зависимость присутствует и имеет скачкообразный характер, что подтверждает результаты в ряде известных работ. Это позволяет сделать вывод о том, что эти эксперименты проводились авторами на частичных веб-графах.

2. Анализ полученных результатов по использованию известного метода FLG для идентификации веб-сообществ показал, что ядро реализующего его алгоритма — алгоритм поиска максимального потока минимальной стоимости, имеет существенные ограничения по масштабируемости как в направлении увеличения локального веб-графа, так и при больших пропускных способностях рёбер. Это, наряду с уменьшающейся актуальностью такого подхода в целом из-за существенного влияния «ложных» и информационных гиперссылок, ограничивает его использование для идентификации реальных веб-сообществ.

3. Результаты экспериментов по идентификации самоорганизованных веб-сообществ на основе разработанной многоэтапной процедуры, учитывающей как ссылочную структуру, так и содержимое документов, показали достаточно высокую эффективность этого подхода, показав точность около 77% при 97% полноты поиска. Проведена оценка зависимости качества идентификации веб-сообществ от выбираемого числа ключевых слов, отображающих тематику веб-сообщества. Даны возможные объяснения закономерности ухудшения качества идентифицированных веб-сообществ при росте числа ключевых слов, вытекающие из законов Зипфа.

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

5. Выполнено исследование Мобильного Интернета и дана оценка динамики его роста за период исследований. Показана схожесть основных закономерностей формирования МИ с большим Интернет и проведён ряд экспериментов по идентификации веб-сообществ на веб-графе МИ. Сделан вывод о неразвитости МИ и дан прогноз его будущего развития в виде быстрого слияния с большим Интернетом.

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

Заключение

.

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

На основе проведенных исследований можно сделать следующие выводы:

1. Проведено обобщение известных результатов и дальнейшее их развитие в части исследования поведения потоковых методов идентификации веб-сообществ на различных типах графов, к которым приводят разные стратегии реконструкции веб-графа. Из полученных результатов следует, что на полных веб-графах коэффициент ёмкости пропускных способностей рёбер не влияет на количество идентифицируемых членов веб-сообщества для метода FLG и производных от него потоковых подходов. На частичных веб-графах такая зависимость присутствует и имеет скачкообразный характер. На основе этих данных введена типизация веб-графов.

2. Предложена концептуальная модель эволюции веб-графа, модель имитации веб-графа и алгоритм генерации искусственных веб-графов с контролируемыми параметрами. Предложенная модель имитации веб-графа позволила объяснить различие зависимостей ранг-частота для разных тематических веб-графов. Показано, что степень выпуклости на графиках зависит от параметра dM предложенной модели, определяющего долю рёбер со старых вершин на новую. Доказано утверждение, позволяющее вычислить вероятность достижимости двух случайно выбранных узлов в веб-графе. Из него следует, что в реальной Сети такие узлы достижимы не менее чем в 13% случаев.

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

4. Разработан алгоритм автоматической численной оценки качества идентифицированных веб-сообществ для любого метода идентификации, имеющего несколько членов со 100%-й принадлежностью к веб-сообществу. Алгоритм показал достаточно хорошие результаты в сравнении с экспертной оценкой при определении качества веб-сообществ. Разработанный в контексте этого алгоритма подход по нормализации словоформ показал удовлетворительные результаты в экспериментах, несмотря на принципиальное отсутствие учёта семантики и словообразования. В целом алгоритм может рассматриваться как альтернатива экспертной оценки при обработке большого количества оцениваемых веб-сообществ, а также для оценки уже существующих тематических каталогов на соответствие документов выбранной тематике.

5. В рамках проведённых исследований реализован программный комплекс, предназначенный для идентификации, анализа и оценки качества самоорганизованных веб-сообществ. Любой эксперимент, реализующий разработанные подходы, можно представить UML диаграммой последовательностей действий из цепочки модулей программного комплекса. Описаны особенности реализованных алгоритмов комплекса и использованных структур данных. Получена оценка наиболее ресурсоёмких элементов программного комплекса на эффективность и масштабируемость. Обеспеченный уровень масштабируемости позволил работать с реальными данными из Сети. Кроме того, использовалась унификация данных, позволяющая выходные данные одного модуля использовать как входные для другого. При этом все данные хранятся в открытых форматах, что повышает их переносимость и позволяет использовать стандартные средства для постобработки.

6. Исследован Мобильный Интернет и дана оценка динамики его роста за период исследований. Показана схожесть МИ с большим Интернет и проведён ряд экспериментов по идентификации веб-сообществ на веб-графе МИ. Экспериментальные исследования по идентификации самоорганизованных веб-сообществ в МИ показали, что с одной стороны такие сообщества в МИ есть, с другой — они мало организованны (но не малочисленны) и относятся к специфическим для МИ тематикам (сообщества любителей какой-либо модели или производителя телефона, сообщества бесплатного мобильного контента и т. п.). Из общих тематик пока более всего развиты новостные сообщества и информационные сервисы о погоде, курсах валют и акций. Таким образом сделано заключение о слабой развитости МИ и дан прогноз его развития в виде быстрого слияния с большим Интернетом.

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