Содержание к диссертации
Введение
Глава 1. Принципы сбора и обработки больших объемов данных в социальных медиа 8
1.1. Модели информационных процессов в социальных медиа 8
1.2. Принципы сбора данных в Интернет 12
1.3. Обзор существующих систем сбора данных 19
1.4. Классификация задач сбора и обработки данных в социальных медиа 22
Выводы по главе 1 23
Глава 2. Математическое обеспечение сбора данных 25
2.1. Адаптивная процедура сбора данных 25
2.2. Тематический сбор данных в социальных медиа 27
2.3. Мониторинг социальных медиа 33
2.4. Репрезентативные выборки из графовых структур 50
Выводы по главе 2 58
Глава 3. Программное обеспечение сбора данных 60
3.1. Общая архитектура системы 60
3.2. Интеграция с платформой облачных вычислений CLAVIRE 66
3.3. Программная реализация системы сбора данных 71
Выводы по главе 3 79
Глава 4. Применение к исследованиям социальных медиа 80
4.1. Психологический портрет пользователей, вовлеченных в пропаганду наркотиков в социальных медиа 80
4.2. Анализ соответствия реальных и виртуальных связей пользователей сети Vkontakte 90
4.3. Исследование процессов формирования пользовательских сообществ на основе общих интересов з
4.4. Внедрение системы сбора данных в производственно-исследовательский веб центр «Социодинамика» 106
Выводы по главе 4 115
Заключение 117
Список использованных источников
- Принципы сбора данных в Интернет
- Тематический сбор данных в социальных медиа
- Программная реализация системы сбора данных
- Исследование процессов формирования пользовательских сообществ на основе общих интересов
Введение к работе
Актуальность темы. В настоящее время социальные медиа (СМ) - социальные сети, блоги и микроблоги, геосоциальные сервисы, фотохостинги и видеохостинги, сайты отзывов, сайты знакомств - являются динамическими источниками разнородной информации, отражающей различные процессы, пртекающие в реальном обществе. Для их количественного анализа применяются специальные технологии, ориентированные на сбор и обработку огромных объемов неструктурированных данных (Big Data). Особенности адаптации технологий BigData к СМ связаны с необходимостью учета топологической структуры виртуального общества пользователей (ВОП), поскольку СМ помимо коллаборативного хранилища данных образуют самоорганизующуюся транспортную среду для обмена информацией между пользователями. В целом это определяет динамические свойства СМ, учет которых требует развития отдельного класса математического и программного обеспечения BigData.
Специфика практической работы с СМ посредством внешних инструментов сбора данных (краулеров) состоит в том, что получение актуальной и исчерпывающей информации невозможно в силу перманентной активности пользователей, редактирующих и дополняющих свои страницы. Кроме того, экспериментальное обнаружение в СМ информационных процессов (ИП), таких как распространение информации заданного содержания, установление новых или разрыв существующих связей, осложняется квотированием числа обращений1 и разветвленной структурой связей между отдельными документами, предполагающей множественность политик обхода. Как следствие, это затрудняет решение задачи мониторинга коллективной активности пользователей СМ, отражающей их влияние друг на друга. Потому необходимо повышать эффективность процессов сбора и обработки данных в СМ за счет использования знаний о свойствах информационных процессов и топологической структуре ВОП. Ключевой проблемой в данном случае является самоорганизация и самомодерация среды СМ, это не позволяет использовать априорные знания и требует создания адаптивных механизмов, настраиваемых непосредственно в ходе процесса сбора данных, с учетом ранее накопленной информации.
Предметом исследования являются методы повышения эффективности систем сбора и обработки больших объемов данных из СМ.
Целью работы является разработка и исследование адаптивных методов учета свойств ИП и структуры ВОП для повышения эффективности сбора и обработки больших объемов полуструктурированных данных из СМ, и реализация соответствующего математического и программного обеспечения.
Задачи исследования:
Устанавливается оператором СМ.
обоснование требований к математическому и программному обеспечению сбора и обработки данных СМ на основе результатов аналитического обзора предметной области;
разработка и исследование адаптивных методов повышения скорости обнаружения новых событий в СМ и построения репрезентативных выборок с учетом топологии связей ВОП;
проектирование и программная реализация архитектуры распределенной программной среды для сбора и анализа данных из разнотипных СМ на основе концепции BigData;
экспериментальные исследования и апробация разработанных положений на примере изучения активности пользователей СМ.
Методы исследования включают в себя методы теории графов и комплексных сетей, теории вероятности и математической статистики, методы машинного обучения, интеллектуального анализа данных, а также инженерии программного обеспечения, анализа алгоритмов и программ.
Научная новизна заключается в использовании облачной модели AaaS для реализации адаптивной процедуры сбора и обработки данных СМ путем гибкой интеграции технологий краулинга неструктурированной информации, ее обработки и хранения в рамках концепции BigData, эффективного планирования сбора данных, а также композитных приложений, реализующих прикладные задачи исследования СМ. В совокупности это позволяет обеспечить универсальность разработанных методов, технологий и программных средств для СМ с различной топологией и назначением.
Практическую ценность работы составляют:
программная платформа для сбора данных из CM Livejournal, ВКонтакте, Twitter, с учетом актуального состояния их топологической структуры;
набор композитных приложений для анализа ИП в СМ, доступный в облачной среде CLAVIRE ();
система тематического сбора данных СМ в составе веб-ориентированного производственно-исследовательского центра «Социодинамика» (socio.).
На защиту выносятся:
адаптивная процедура эффективного сбора данных в СМ на основе методов предсказания времени возникновения новых событий в СМ и построения репрезентативных выборок с учетом топологии связей ВОП;
архитектура программной платформы для эффективного сбора и анализа данных большого объема СМ на основе модели AaaS облачных вычислений второго поколения.
Достоверность научных результатов и выводов обеспечивается обоснованностью применения математического аппарата, результатами тестирования алгоритмов и программного обеспечения, экспериментальными
2 AaaS - Application as a Service, приложение как сервис
исследованиями на реальных приложениях, а также практическим внедрением (опытной эксплуатацией) разработанных программных средств.
Внедрение результатов работы. Результаты работы использованы при выполнении следующих НИОКР: «Создание высокотехнологичного производства комплексных решений в области предметно-ориентированных облачных вычислений для нужд науки, промышленности, бизнеса и социальной сферы» в рамках реализации постановления Правительства РФ № 218, «Распределенные экстренные вычисления для поддержки принятия решений в критических ситуациях» в рамках реализации постановления Правительства РФ № 220, «Разработка веб-ориентированного производственно-исследовательского центра в области социодинамики и ее приложений» в рамках ФЦП «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2007-2013 гг.».
Апробация работы. Полученные результаты обсуждались на международных и всероссийских научных конференциях, семинарах и совещаниях, включая XIV Всероссийскую объединенную научную конференцию «Интернет и современное общество» (Санкт-Петербург, 2011), XI Всероссийскую конференцию «Высокопроизводительные параллельные вычисления на кластерных системах» (Нижний Новгород, 2011), Международную научно-практическую конференцию молодых ученых и специалистов «Технологии высокопроизводительных вычислений и компьютерного моделирования» (Амстердам, 2012), Международную научно-практическую конференцию молодых ученых и специалистов «International School of Computational Science» (Барселона, 2013), XX Всероссийскую научно-методическую конференцию «Телематика'2013» (Санкт-Петербург, 2013), XVI Всероссийскую объединенную научную конференцию «Интернет и современное общество» (Санкт-Петербург, 2013), Международную конференцию «Инженерия Знаний и Семантического Веба "KESW-2013"» (Санкт-Петербург, 2013).
Публикации. По материалам диссертации опубликовано 12 печатных работ, в том числе 7 - в изданиях из перечня ВАК, а также 1 свидетельство о регистрации программы для ЭВМ.
Личный вклад диссертанта заключается в участии в постановке задачи, разработке теоретических основ повышения эффективности системы сбора данных СМ, разработке алгоритмов и программной реализации платформы распределенного краулера, проведении экспериментальных исследований, а также в интерпретации результатов.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы (100 наименований) и 1 приложения; содержит 125 страниц текста, включая 33 рисунка и 5 таблиц.
Принципы сбора данных в Интернет
К основным требованиям, предъявляемым к краулерам можно отнести следующие: 1) Вежливость. Требуется соблюдать накладываемые сервером правила, регулирующие частоту обращения и запрашиваемые ресурсы. 2) Распределенность и Масштабируемость. Для обработки больших объемов данных требуется возможность функционирования краулера на нескольких машинах. При этом требуется способность увеличения рабочей нагрузки, путем добавления новых машин или увеличения пропускной способности. 3) Расширяемость. Требуется «легкость» добавления или изменения компонентов краулера. Например, изменение алгоритма влияющего на работу системы, поддержка нового формата данных или сетевого протокола передачи данных. 4) Устойчивость. Система должна стабильно обрабатывать разного рода сетевые ошибки, неизбежно возникающие при обмене данных с серверами. При остановке работы, краулер должен поддерживать восстановление работы с последней точки. 5) Производительность. Работа с большими объемами данных требует эффективного использования всех ресурсов машины. 6) Качество. Собранная краулером база данных документов должна удовлетворять требованиям клиентов системы. Например, при решении задач мониторинга сети, база данных должна содержать свежие копии страниц.
Конкретные требования к системе зависят от специфики решаемой задачи. Однако при работе с сайтами, можно выделить два главных требования ко всем системам сбора данных: вежливость и устойчивость. Сайты накладывают явные и неявные ограничения на число обращений к ним. Большинство сайтов не рекомендуют устанавливать больше чем одно соединение с ними, при этом между двумя последовательными соединениями должен быть выдержан временной интервал, достаточный для того чтобы не создавать сайту проблем. Эти ограничения требуют эффективного использования доступного числа обращений к сайтам, чтобы качество получаемой базы было как можно выше.
Сбор данных с миллиардов сайтов требует реализации распределенной системы сбора данных, при которой ресурсы каждой отдельной машины будут использоваться максимально эффективно и сами машины эффективно обмениваются данными друг с другом. Однако если специфика решаемой краулером задачи требует сбора данных небольшого объема с небольшого числа сайтов, то реализация распределенной системы не является обязательной.
Проведение систем сбора данных регулируется рядом алгоритмов, называемых политиками обхода краулера. Можно выделить несколько типов политик краулеров [12]: политика выбора данных, политика повторного посещения узлов, а так же политика вежливости, определяющая интенсивность сбора данных с одного узла и политика параллелизации. Последние две политики больше относятся к особенностям построения архитектуры краулера, в то время как две первые влияют на выбор и порядок обхода узлов сети.
Политики выбора данных ранжируют URL исходя из их важности для целей краулера. При этом URL могут быть отфильтрованы, так как не представляют интереса для краулера. Например, в сети Интернет содержится огромное количество дублирующих друг друга данных, политика выбора может определять такие данные исходя из ряда эвристик, и исключать дубликаты. Могут быть предложены различные метрики для оценки важности или качества страницы, как исходя из топологических признаков страницы, так и исходя из свойств URL. Примером топологического признака может быть знаменитая метрика оценки важности PageRank, предложенная создателями поисковой компании Google [13], которая оценивает предельную вероятность оказаться в заданной странице при случайных блужданиях. В современных промышленных поисковых системах и краулерах для реализации политик выбора узла используются методы машинного обучения, которые на базе признакового описания URL определяют его важность таким образом, чтобы общее качество получаемой базы данных было максимальным.
Сайты в сети Интернет имеют динамическую природу и в общем случае изменяются в случайные моменты времени. Одно из важных требований к базе данных веб-страниц является требование «свежести», заключающееся в том, чтобы сохраненные копии документов совпадали с текущими версиями в на сайтах. Политики повторного посещения определяют страницы и момент времени, в которых их требуется повторно посетить, чтобы свежесть базы данных была максимальной. Понятие свежести базы данных может быть математически формализовано несколькими способами. Наиболее распространенными в литературе являются метрика свежести, возраста и задержки [14]. При сборе данных из сети интернет предпочтительней использовать метрику свежести, показывающей долю страниц в базе данных в последней версии. А при сборе данных из новостных сайтов предпочтительней использовать метрику задержки, показывающей время между моментом изменения страница и моментом ее обнаружения. Эффективная реализация политики повторного посещения страниц особенно важна при реализации мониторинга данных.
Тематический сбор данных в социальных медиа
Для построения эффективных политик мониторинга могут быть использованы математические модели, описывающие появление новых событий в социальных медиа. События имеют случайную природу, поскольку заранее неизвестно время, когда оно произойдет. Поэтому используются вероятностные математические модели, которые оценивают вероятность появления нового события в тот или иной промежуток времени. Для определения оптимальных значений параметров модели, она «обучается» на основании истории обновления элементов сети. Оптимальные значения параметров модели, подстраивают ее под обучающее множество таким образом, чтобы модель на них предсказывала появление новых событий наиболее точно. Таким образом, процесс создания модели относится к методам машинного обучения с учителем.
На основании модели, описывающей появление новых событий, создается политика мониторинга, которая при условии справедливости модели, определяет квоты элементов и время обращения к ним таким образом, чтобы минимизировать ожидаемое значение функции задержки. Поскольку события имеют случайный характер, то оптимизируются именно ожидаемые значения.
Многочисленные исследования показали, что изменение различных объектов в Интернете, например сайтов, может быть описано посредством Пуассоновского распределения [41,42]. Свидетельством этого может быть тот факт, что временные интервалы между двумя последовательными событиями имеет экспоненциальное распределение. Хотя практические исследования показали, что временные интервалы между двумя последовательными изменениями страниц и не точно повторяют экспоненциальное распределение, оно может быть использовано. Помимо экспоненциального распределения так же может быть использовано гамма распределение, чьим частным случаем является первое распределение. Большинство методов может быть использовано без изменений и для гамма распределения [40]. Помимо описания сайтов в интернете Пуассоновское распределение так же подходит и для описания других элементов: новостных сайтов, отдельных страниц, данных из социальных медиа.
Была проанализирована частота обновления блогов в Livejournal, а именно имеют ли временные интервалы между появлением двух событий экспоненциальное распределение. В случае истинности этого утверждения, для описания изменения блогов может быть использована Пуассоновская модель. Функция плотности экспоненциального распределения с параметром Л имеет следующий вид: /(т,Я) = Я е"Ят (2.2.4) , где т продолжительность временного интервала. Тогда вероятность наблюдать к событий на временном интервале т имеет Пуассоновское распределение: Р(т,к)=е- (2.2.5)
Если построить график функции плотности экспоненциального распределения (так же как и функцию экспоненциального распределения) на логарифмических осях, то он должен иметь форму прямой. Для анализа было выбрано 100000 случайных блогов из русского сегмента Livejournal, для каждого блога было получено 25 последних записей. Гистограмма временных интервалов между записями для всех блогов представлена на рисунке 2.5, из которого видно, что распределение отлично от экспоненциального, поскольку форма линии гистограммы отлична от прямой линии. График обладает очень большим хвостом, который мы не отсекаем, оставляя только значения временные интервалы, с частотой появления больше 10_3.
Из рисунка 2.5 следует достаточно очевидное, но важное заключение, а именно, что изменение всех блогов не может быть описано посредством единого экспоненциального распределения. Каждый блог должен быть описан посредством своей собственной моделью, которая имеет индивидуальные параметры. Так же было протестировано, подчиняется ли изменение каждого индивидуального блога экспоненциальному распределению. Для каждого блога, анализируя его последние 25 записей, было вычислено количество секунд между появлением двух последовательных записей - временные интервалы. В результате каждый блог описывался 24 значениями временных интервалов, для которых было проверено имеют ли они экспоненциальное распределение. Был использован равномерно наиболее мощный критерий для проверки экспоненциального распределения [43], который показал что с 95% оно не экспоненциальное. 10 ,— ,—,— I ,—,—.——, 1—I— j о ooocxrrn " " X W1CL L 10? ! і, , і ... .Л 10 10 10/ 10J 10" x - time gap between posts, hours Рисунок 2.5. Гистограмма временных интервалов между появлением двух записей во всех блогах Livejournal
Статистический тест показал, что в случае измерения в секундах временных интервалов между сообщениями, изменения блогов не подчиняются экспоненциальному распределению. Однако если измерять временные интервалы в целом количестве дней, то для многих блогов распределение будет экспоненциальным. Это является следствием того, что на различных разрешениях один и тот же процесс может описываться различными законами.
Исследования показали, что среднее количество сообщений А создаваемых в блоге Ei за один день, не сильно варьируется изо дня в день. Оно меняется во времени достаточно медленно и может быть подсчитано на основании истории последней активности пользователей. Для новостных сайтов, которые очень интенсивно обновляются, достаточно истории за последние две недели [14]. Среднее количество сообщений создаваемых в блоге Xt будем так же называть интенсивностью обновления. Благодаря тому, что интенсивность обновления не сильно меняется изо дня в день, для описания изменений блога может быть использован однородный Пуассоновский процесс.
Пуассоновский процесс является непрерывным процессом, подсчитывающим количество событий произошедших за определенный интервал времени, и который обладает свойствами отсутствия памяти, и независимости от момента времени. Пуассоновский процесс так же моделирует время появления следующего события, вернее его вероятность. Однородный Пуассоновский процесс использует предположение, что новые события возникают с интенсивностью А в любой момент времени. В однородном Пуассоновском процессе временные интервалы между двумя событиями имеют экспоненциальное распределение описываемое формулой (2.2.4), а вероятность наблюдать к событий на протяжении временного интервала т имеет Пуассоновское распределение (2.2.5). Данная модель подходит не только для описания появления новых сообщений в блогах, но и для произвольных типов событий происходящих в сети, однако для упрощения изложения в тексте будет использован пример с новыми сообщениями в блогах.
Программная реализация системы сбора данных
Методы обхода графов сравниваются исходя из статистических свойств получаемых выборок. Выборка называется репрезентативной, если ее характеристики или статистические свойства совпадают с характеристиками всего графа. Если статистические свойства выборки и графа отличаются, то данная выборка является смещенной. Например, смещение в свойствах выборок может быть вызвано тенденцией алгоритма обхода графа посещать вершины с высокой степенью.
Сбор данных может совершаться для различных целей, которые влияют на требования, предъявляемые к выборкам. Например: получение репрезентативной выборки с точки зрения определенного свойства или же поиск топологического сообщества, в котором состоят данные пользователи. В зависимости от решаемой задачи к свойствам выборок предъявляются различные требования. Так в первом примере необходимо получение репрезентативной выборки, а во втором - наоборот, смещенной выборки, в которой вершины графа находятся в одном топологическом сообществе.
Репрезентативность выборок определяется исходя из совпадения ее статистических свойств со свойствами всего графа. Анализируемое статистическое свойство мы будем называть критерием. Однако существует масса различных критериев, по которым могут быть оценены выборки, и выбор конкретного критерия зачастую неочевиден [56]. Для решения практических задач, для которых осуществляется сбор данных, можно выделить следующие основные группы критериев [50]: 1. степенные критерии; 2. критерии, связанные с кластеризацией; 3. критерии, связанные с покрытием сети. Для каждого фиксированного критерия методы обхода сравниваются исходя из статистических свойств значений данного критерия в выборке и во всей сети. Анализируемые в работе критерии позволяют получить численную характеристику для каждого элемента в выборке. Поскольку значения критерия для разных элементов выборки различны, то вся совокупность элементов характеризуется распределением значений анализируемого критерия. Например, каждая вершина графа обладает своей степенью, и весь граф характеризуется распределением степеней вершин - для каждого значения степени определяется доля вершин, обладающих такой степенью.
Для измерения репрезентативности выборок используется расстояние Кульбака-Лейблера [57], которое является несимметричной мерой удаленности друг от друга двух вероятностных распределений. Мера Кульбака-Лейблера используется для двух распределений, одно из которых р является «истинным», а другое q является «предполагаемым», и обычно являющимся приближением истинного распределения. Данная мера информации может быть интерпретирована как величина потерь информации при замене истинного распределения р на распределение q. Для двух дискретных величин р и q расстояние Кульбака-Лейблера может быть посчитано по формуле: DKb(.P,q) = Z «P( )lnjg (2.3.2) Большинство используемых методов обхода являются недетерминированными -при одинаковых входных параметрах они выдают различные выборки с отличающимися статистическими свойствами. Так же большинство графов, описывающих реальные социальные сети, являются гетерогенными - в них присутствуют различные по статистическим свойствам участки, поэтому методы обхода зависят и от значения начальной вершины, с которой начинается обход графа. Для получения более достоверных характеристик методов обхода графов, каждый метод был использован для генерации 20 независимых выборок, при этом начальная вершина обхода так же выбиралась случайным образом. Статистические свойства 20 выборок затем усредняются для получения характеристик метода обхода.
Для каждого критерия сравнения методов обхода приводится два типа графиков. Первый тип графиков показывает, как уменьшается расстояние Кульбака-Лейблера в зависимости от размера получаемой выборки. По мере увеличения размера выборки ее свойства должны становиться все более и более похожими на свойства всего графа. Второй тип графиков показывает различия методов обхода для фиксированного размера выборки. Каждая точка графиков является средним значением, посчитанным по 20 различным случайным выборкам, полученным каждым методом обхода. В качестве анализа использовался граф дружбы первых 100000 пользователей социальной сети Вконтакте. Анализировались только ребра находящиеся внутри этого множества узлов.
Методы обхода графов сравниваются на трех различных группах критериев, которые имеют отношение к задачам, решаемым для практических исследований системами сбора данных.
Степенные критерии. Одним из главных свойств выборки, при исследовании топологических свойств комплексной сети, является распределение степеней вершин сети. Анализ показал, что большинство методов обхода графа выдают смещенную выборку, в которой преобладают узлы с высокой степенью. Широко известные методы обхода графов: обход в ширину (BFS) и случайные блуждания (RandomWalk) дают выборки смещенные в сторону вершин с большой степенью. Исследования показали, что на основе алгоритма Метрополиса-Гастингса (MHRW) возможно получить выборку из графа с несмещенным распределением степеней вершин. На рисунке 2.13 представлено сравнение различных способов обхода сети Vkontakte. Отметим, что алгоритм MHRW позволяют получить несмещенные выборки и в случае наличия стратификации данных.
Исследование процессов формирования пользовательских сообществ на основе общих интересов
Реализация всех операций в рамках фреймворка Hadoop позволяет решить типичные проблемы для распределенных систем. Однако вынесение ряда операций за рамки кластера Hadoop, хоть и позволяет создать более гибкую и эффективную систему, но ставит задачу синхронизации между вычислительными ресурсами и кластером Hadoop. Эта задача решается посредством использования библиотеки ZooKeeper [62]. Zookeeper реализует распределенное иерархическое key/value хранилище, обладающее возможностями: - Двунаправленная связь между клиентом и сервером, благодаря которой клиент может «подписываться» на изменения в каком-то из узлов. - Возможность создания «временной» пары key/value, которая существует пока клиент к подключен серверу. - Устойчивость к выходу из строя нескольких машин кластера. Для выполняемых операций гарантия выполнения запросов FIFO и линеаризуемость всех запросов, которые изменяют состояние системы. Описанные свойства позволяют использовать ZooKeeper для осуществления различных координации в системах распределенных вычислений: рассылка сообщений между вычислительными узлами, реализация распределенной памяти, сервис распределенных блокировок, и т.д.
Тематический сбор данных основан на использовании описания темы, которое может состоять из ключевых слов или фраз. Описание темы может состоять из десятков и сотен ключевых слов и фраз, поэтому возникает задача их быстрого поиска в текстах. Поиск ключевых слов и фраз происходит в режиме реального времени и осуществляется для всех новых текстов, которые были загружены на последней итерации работы системы. Так же процесс поиска ключевых слов в документе усложняет наличие «паттернов» слов (см. раздел 2.1.), которые стремятся учесть различные словоформы слов. Отметим, что под фразами может пониматься как набор слов, встречающихся последовательно друг за другом в тексте, так и последовательность слов, которые находятся на некотором расстоянии друг от друга, а так же слова неупорядоченные друг относительно друга. Данное обобщенное понятие фразы так же усложняет процесс их поиска в тексте.
Необходимость осуществлять поиск ключевых слов в режиме реального времени не позволяет осуществить «индексацию» документов - процедуру, при которой будет возможно организовать быстрый поиск по слову списка всех документов, которые его содержат.
Одним из подходов, который мог бы быть использован для решения обозначенной задачи, является использование регулярных выражений. На основании списка ключевых слов может быть автоматически составлено большое регулярное выражение, которое производит поиск этих слов в тексте. При этом могут быть автоматически учтены различные словоформы ключевых слов. Однако на практике данный подход оказался не эффективным, поскольку время работы алгоритма увеличивается не линейно в зависимости от числа ключевых слов. На темах описываемых десятками ключевых слов, время работы данного алгоритма значительно увеличивалось.
Поэтому для поиска ключевых слов был использован подход, основанный на построении префиксного дерева, реализующего поиск множества подстрок из словаря в данной строке [63]. На основании ключевых слов, описывающих тему, строится префиксное дерево и реализуется алгоритм Ахо-Корасика для поиска подстрок в подаваемой на вход строке. Алгоритм позволяет найти все вхождения в текст всех ключевых слов, описывающих тему. Поскольку ключевые слова имеют множество словоформ, то префиксное дерево строится исходя из корневых форм слов. Затем на основании информации о положении в тексте этой корневой формы, проверяется, что в тексте действительно содержится указанное в словаре ключевое слово. Таким образом данный алгоритм позволяет осуществлять быстрый поиск ключевых слов во множестве текстов.
Поиск фраз осуществляется на основе найденных в тексте ключевых слов. В общем случае под фразой понимается модель «мешка слов» (bag of words) [64], при которой не фиксируется ни последовательность слов, ни расстояние между ними, хотя эти ограничения так же могут быть учтены. Например, в рамках модели мешка слов, наличие в тексте фразы «купить машину» означает, что в тексте содержатся два ключевых слова: «купить» и «машина». Отметим, что порядок следования слов и расстояния между ними так же могут быть учтены описываемым алгоритмом поиска фраз.
В рамках модели мешка слов, каждая фраза описывается неупорядоченным множеством ключевых слов. Тексты так же описываются неупорядоченными множествами слов. Для проверки наличия ключевой фразы в тексте необходимо проверить, что множество всех ключевых слов фразы содержится во множестве слов текста. Поскольку описание темы может состоять из большого количества фраз, данную процедуру необходимо проводить большое количество раз.
Для быстрого поиска всех ключевых фраз в тексте используются следующий алгоритм. Все ключевые слова ранжируются исходя из частоты их появления в ключевых фразах. Слово, встречающееся во множестве ключевых фраз чаще всего, обладает минимальным рангом. Для описания фразы - входящие в нее слова сортируются исходя из значения своего ранга. Слова сортируются для того, чтобы можно было производить поиск подмножества в множестве за линейное время. Затем для каждой фразы выбирается слово представитель - слово, которое содержится во фразе и обладает максимальным рангом. На основе этих данных создается ассоциативный массив, который по слову позволяет получить список всех фраз, которые оно является словом представителем.
Похожие диссертации на Математическое и программное обеспечение распределенной обработки больших объемов данных из социальных медиа
