Содержание к диссертации
Введение
Глава 1. Проблема обнаружения и определения авторства схожих web-документов 14
1.1 Информационный поиск и задача распознавания дублей 14
1.2 Задача распознавания схожих документов 15
1.3 Определение понятия схожих документов 17
1.4 Источники схожих web-документов 18
1.5 Основные метрики подобия web-документов 20
1.6 Методы обнаружения схожих документов 22
1.7 Предварительная обработка документов 29
1.8 Варианты классификации поисковых запросов 30
1.9 Кластеризация и классификация документов 32
1.10 Структурно-семантическое разбиение 33
1.11 Борьба с плагиатом 34
1.12 Постановка задачи обнаружения дублей и выделения первичного web-документа 37
1.13 Выводы 38
Глава 2. Разработка модели оценки схожести документов и определения первичного документа в кластере дублей 40
2.1 Модель представления web-документов блоками 40
2.2 Модель классификации запросов и степень фильтрации дублей 43
2.3 Метод экспертных оценок для градации online фильтрации дублей 45
2.4 Метод определения дублей при online фильтрации 47
2.5 Методы offline фильтрации дублей 50
2.6 Структурная схема модели определения дублей 59
2.7 Методы оценки эффективности алгоритмов поиска дубликатов 60
2.8 Определение первичного документа в кластере web-дублей 61
2.9 Выводы 67
Глава 3. Алгоритмизация процессов детектирования web-дублей и определения первичного документа 68
3.1 Алгоритмы разбиения web-страниц на семантические блоки 68
3.2 Классификация запросов 71
3.3 Алгоритм градации при online фильтрации 77
3.4 Алгоритм определения дублей при online фильтрации 81
3.5 Алгоритмы для offline фильтрации 85
3.6 Алгоритмы определения первичного документа 98
3.7 Выводы 108
Глава 4. Программная реализация методов фильтрации дублей и определения первичного web-документа 110
4.1 Структура программного обеспечения 110
4.2 Программная реализация 112
4.3 Графический интерфейс 116
4.4 Последовательность работы с программой 123
4.5 Результаты практической апробации разработанных подходов 125
4.6 Выводы 136
Заключение 138
Литература 139
Приложение 1 155
- Основные метрики подобия web-документов
- Метод экспертных оценок для градации online фильтрации дублей
- Алгоритм определения дублей при online фильтрации
- Результаты практической апробации разработанных подходов
Введение к работе
Актуальность темы. Всевозрастающее количество неуникальных документов в Интернете снижает эффективность поиска релевантной информации пользователем и создает трудности для поисковых систем, обусловленные увеличением индексных баз за счет избыточной информации, что, в свою очередь, приводит к росту затрат на обслуживание и хранение данных, а также требует большей ресурсной подготовки.
Сопутствующей проблемой определения дублированной информации является выделение единственного документа в сформированном множестве дублей, так называемого первичного документа, который будет участвовать в ранжировании результатов поиска. Ошибки при его определении влекут за собой некорректное формирование результатов поиска.
Существующие методы определения дублей и первичного документа не обеспечивают, с учетом современных способов их получения, достаточной точности (отношение числа действительных дублей, к общему числу найденных дублей) и полноты (отношение числа найденных дублей к общему числу дублей в базе) при ранжировании результатов поиска и индексировании Интернет-ресурсов.
Методы описательных слов, контрольных сумм, расчета схожести по коэффициенту Джаккарда и другие показывают высокие значения полноты и точности при определении полных дублей. Однако они не позволяют определять дубли, образованные одним из следующих способов, широко используемых для генерации текстов с целью влияния на ответ поисковых систем: замена русских букв аналогичными английскими; генерация и синонимизация текстов; изменение порядка абзацев, предложений, слов; сочетание текстов разных источников; комбинация различных способов.
Исходя из вышесказанного, для поисковых систем актуальной является задача разработки новых и усовершенствование существующих методов определения дублей и выделения первичного web-документа из кластера дублей.
Объектом исследования диссертационной работы является процесс определения web-дублей и выделения первичного web-документа из кластера дублей.
Предметом исследования диссертационной работы являются методы определения дублей при ранжировании и индексировании web-документов и выделения первичного документа из кластера web-дублей.
Цель диссертационной работы состоит в повышении эффективности процесса определения схожих web-документов и выделения первичного документа из кластера дублей путем разработки методик и алгоритмов, учитывающих современные способы генерации дублированного текста.
Задачи исследования:
-
Анализ источников схожих web-документов.
-
Анализ существующих алгоритмов и методов определения схожих web-документов и выделение из кластера дублей первичного документа.
-
Создание методик и алгоритмов определения дублей web-документов при ранжировании (online фильтрация) и при индексировании документов (offline фильтрации), учитывающих современные способы генерации дублированного текста.
-
Создание методики выделения первичного документа из кластера web-дублей, позволяющей агрегировать различные аспекты выбора первичного документа (авторство, тематическая полнота, цитируемость и т.д.).
-
Разработка программного обеспечения, позволяющего выявить эффективность разработанных методик по оценке схожести web-документов при offline и online фильтрации, а также по определению первичного документа в кластере дублей.
Методы исследования. Методы исследования основаны на использовании теории графов, теории нечетких множеств, теории вероятностей, математической статистики, экспертных оценок.
Научная новизна работы заключается в следующем:
-
Разработана методика online фильтрации дублей, основанная на введении порога фильтрации (фиксированное значение схожести, при котором документы считаются дублями) для каждого типа запроса при ранжировании документов, и методика offline фильтрации дублей, представляющая собой каскад фильтров, применяемый при индексировании документов и учитывающий современные способы генерации дублированного текста.
-
Предложен метод определения схожести аннотаций на основе коэффициента Джаккарда, учитывающий синонимические замены, и методы определения дублей, созданных путем генерации, синонимизации, перестановкой слов, предложений, абзацев, сочетанием абзацев разных авторов, заменой русских букв на латинские.
-
Выведено выражение, позволяющее выделять из кластера web-дублей первичный документ, агрегирующее различные аспекты его выбора, и разработаны методы оценки вероятности авторства текста, полноты тематики и удобства использования ресурса.
Практическая ценность работы состоит в том, что предложенные методы позволяют повысить эффективность распознавания документов, содержащих намеренно искаженный текст первоисточника, более чем на 20% и, соответственно, улучшить качество поисковой выдачи - результат ранжирования ссылок на страницы Интернета, отвечающие на запрос пользователя.
Полученные в диссертации результаты могут быть использованы для дальнейшего решения теоретических и практических задач в области определения схожих документов с учетом типа запросов и применения различных усовершенствованных подходов, учитывающих современные способы создания дублей.
Достоверность полученных результатов подтверждается использованием предлагаемых методик при разработке программного обеспечения методов оценки схожести web-документов при индексировании и ранжировании документов, а также методов определения первичного документа в кластере web-дублей.
Положения, выносимые на защиту:
-
Методика online фильтрации, в которой каждому типу запроса при ранжировании документов ставится определенная с помощью экспертных оценок степень фильтрации, соответствующая вероятности схожести документов, и методика offline фильтрации документов, представляющая собой каскад фильтров, определяющих современные способы генерации текстовых дублей.
-
Метод определения схожести аннотаций документов на основе коэффициента Джаккарда, учитывающий синонимические замены; методы определения дублей синонимизированных документов, сгенерированных, созданных путем изменения русских букв на латинские или с помощью сочетания абзацев различных авторов.
-
Выражение определения первичного документа в кластере web-дублей и методики оценки авторства рассматриваемого текста, тематической полноты ресурса и его популярности.
Реализация и внедрение результатов. Предложенные в работе методики детектирования дублей и определения первичного документа были успешно использованы автором для совершенствования системы управления и работы с корпоративными документами ООО «Рекламные технологии в Интернете», для разработки и поддержания систем поиска в 000 «СЕО НЬЮЗ», а также в качестве рекомендаций повышения эффективности документооборота в ЗАО «Ин-гейт Девелопмент». Результаты проведенных исследований реализованы в учебный процесс кафедры ЭВМ при преподавании дисциплин: «Безопасность систем баз данных», «Компьютерные технологии документооборота».
Апробация работы. Основные положения диссертационной работы легли в основу докладов на следующих конференциях: 1. Международная молодежная научная конференция «Гагаринские чтения» (Москва, МАТИ, 2009, 2010, 2011 гг.). 2. Всероссийская научно-техническая конференция «Интеллектуальные и информационные системы» (Тула, ТулГУ, 2009, 2011). 3. Всероссийская конференция с международным участием «Знания - Онтологии - Теории» (Новосибирск, ИМ им. СЛ.Соболева СО РАН, 2009). 4. Международная научно-практическая Интернет-конференция «Инновационные подходы к применению информационных технологий в профессиональной деятельности» (Белгород, Белгородский филиал НАЧОУ ВПО СГА, 2009). 5. Всероссийской научно-практической конференции с международным участием «Информационные технологии в профессиональной деятельности и научной работе» (Йошкар-Ола, МГТУ, 2009). 6. VI региональная научно-практическая конференция аспирантов, соискателей и молодых ученых «Исследовательский потенциал молодых ученых: взгляд в будущее» (Тула, ТГПУ, 2010). 7. VI Международная научно-практическая конференция «Электронные средства и системы управления» (Томск, ТУСУР, 2010). 8. П Всероссийская научная конференция «Научное творчество XXI века» с международным участием (Красноярск, Научно-инновационный центр, 2010). 9. ГХ Всероссийская научно-техническая конференция «Техника XXI века глазами молодых ученых и специалистов» (Тула, ТулГУ, 2010). 10. 5-ая Всероссийская научно-практическая конференция «Системы управления электротехническими объектами» (Тула, ТулГУ, 2010).
Публикации. По материалом диссертации опубликовано 18 научных работ, в том числе 4 в изданиях, рекомендованных ВАК РФ.
Структура и объем диссертации. Диссертационная работа изложена на 168 страницах, включает 11 таблиц и 44 рисунка. Состоит из введения, четырех глав и заключения, списка литературы из 116 наименований и 7 приложений.
Основные метрики подобия web-документов
Интернет стал неотъемлемой частью повседневной жизни. Количество Интернет пользователей неуклонно растет [92]. Использование Интернета условно можно разделить на две категории - источник получения информации и средство общения. Первое направление в настоящий момент превалирует над вторым и непосредственно связано с информационным поиском.
Термин «информационный поиск» был впервые введен в 1948 году Кельвином Муром [102]. На сегодняшний день информационный поиск -большая междисциплинарная область науки, стоящая на пересечении когнитивной психологии, информатики, информационного дизайна, лингвистики, семиотики, и библиотечного дела. Популярность развития данной науки обусловлено в первую очередь экспоненциальным ростом объемов информации, в частности в сети Интернет [20]. С развитием науки расширяется список выполняемых задач и усложняется их уровень. Если классическая задача информационного поиска формулируется как поиск документов, удовлетворяющих запросу, в рамках некоторой статической коллекции документов, то сегодня список задач включает вопросы моделирования, классификации, фильтрации и кластеризации документов, проектирования архитектур поисковых систем и пользовательских интерфейсов, развития языка запросов и механизмов извлечения информации [100]. Также расширился список видов поиска: поиск документов, поиск звука и видео, поиск в гипертекстовых базах данных [65].
Расширение списка задач связано с обозначением все новых проблем в информационном поиске. Для осуществления процесса поиска были разработаны поисковые системы, имеющие трехуровневую архитектуру [65]. На каждом этапе обработки информации поисковыми машинами используется множество специфических алгоритмов из области интеллектуального анализа данных (data mining), от особенностей выделения значащих элементов web-страниц до ранжирования документов в поисковой выдаче (список ответов на запрос пользователя). С увеличением объема данных приходится наращивать вычислительные мощности, организовывать сжатое, но полное хранение информации, усовершенствовать качество поиска.
Одним из наиболее важных направлений повышения качества поиска в Интернете, как основной площадке информационного поиска, а также одной из наиболее важных и трудных задач анализа web-данных является обнаружение дублей [20], что порождает дополнительную задачу выделения первичного документа из кластера дублей. С ростом объемов электронных документов, усложнением информационных технологий и появлением новых знаний существующие механизмы обнаружения дублей [13] и выделения первичного документа [24] требуют дальнейшего развития и доработки, а также разработки новых подходов и методов. 1.2 Задача распознавания схожих документов
Более 30-40% документов в Интернете имеют дубликаты, различного происхождения и степени схожести [23, 81]. Для поисковых систем дублирование информации порождает распространение плагиата, увеличение индексных баз за счет избыточной информации, что ухудшает качество ответа на запрос пользователя. Это подтверждает актуальность исследований по выявлению дублей и разработок соответствующих алгоритмов для поисковых машин.
От качества определения схожих документов зависят многие направления информационного поиска в сети Интернет [8]: - сканирование (crawling) документа в сети. Качество сканирования значительно увеличивается, при предварительном определении является ли сканируемая страница дублем какой-либо ранее просканированной страницы [80, 98]. - ранжирование (ranking) документов, отвечающих запросу пользователя. Осуществляя предварительную обработку полученного релевантного списка на предмет обнаружения web-копий, можно значительно увеличить качество выдачи и повысить информативность поиска для пользователя [113]. - кластеризация (clustering) или классификация документов. При выявлении записей-дублей можно строить более простую систему навигации по ранжируемой базе и объединять схожие документы в группы, тем самым положительно влияя на качество поисковой выдачи. С другой стороны, процесс кластеризации может влиять на корректное определение схожих документов (например, режим обучения алгоритма) [82]. - создание архивов (archiving) или сжатие данных. За счет удаления избыточной информации в виде дублирующихся документов можно значительно уменьшить размер массивов данных, что влечет за собой увеличение скорости обработки индексных баз [83]. - кеширование (caching) документов для хранения в индексных базах. Алгоритмы поиска дублированного контента помогают определить необходимость обновления кеша документа. Подобная проверка позволяет сократить количество обращений к ресурсам поисковых машин, вследствие чего ускоряется обработка данных. Помимо перечисленных процессов информационного поиска, на которые влияет корректное определение схожих документов в массиве данных, можно выделить следующие, напрямую связанные с распознаванием дублей: - фильтрация спама [54]. Фактически содержание и структура почтовых рассылок является дублированной информацией. Детектирование таких писем происходит с помощью алгоритмов определения дублей. - получение похожих документов по содержанию. В большинстве случаев пользователь не формулирует полный запрос для получения наиболее точного ответа. Для этих целей служит функция нахождения подобных документов, где пользователь указывает поисковой системе документ, наиболее четко отвечающий его запросу (пример, программа Searchlnform или поис-ковые системы, например Google ). - борьба с плагиатом. В поисковые системы встроены алгоритмы определения оригинала, однако они несовершенны в настоящий момент. - работа с новостными потоками [19]. Большое количество источников новостной информации, резко возросший объем новостных данных и необходимость их быстрой обработки вызвали потребность в создании систем автоматизированного анализа новостного потока с функцией объединения новостных сообщений в сюжеты на основе сходства этих сообщений по содержанию. С развитием систем информационного поиска расширяется и сфера влияния возможности определения схожих документов. 1.3 Определение понятия схожих документов Из-за неоднозначности понятия «схожие документы», разными авторами оно трактуется по-разному. Одни вкладывают в это понятие абсолютную идентичность, другие рассматривают такие документы через призму одинакового контента, третьи понимают под «схожими документами» - web-страницы, имеющие большую семантическую схожесть. В связи с расхождением понятий возникает «парадокс измерений» [116], при котором на объективную оценку накладываются субъективные допущения. Отсюда вытекает сложность в определении понятия «схожие документы» - отсутствие единой меры измерения схожести. Существует немало разработанных мер схожести, которые отличаются зачастую друг от друга кардинально [95], а методика оценки качества определения степени подобия документов отсутствует [76].
Метод экспертных оценок для градации online фильтрации дублей
На основе глобальной статистики IDF строится I-Match лексикон, 1. определяющий представительные слова и который будет использоваться в генерации сигнатуры. 2. Для каждого документа, идентифицируется набор уникальных терминов U, содержащихся в самом документе. 3. I-Match сигнатура определяется как хэшированное представление пересечения S = (L П U), где сигнатура отклоняется, если S ниже определенного пользователем порога.
I-Match может привести к ложноположительным совпадениям, если использовать единую сигнатуру документа. Для повышения устойчивости алгоритма создается дополнительный набор из К сигнатур, каждая из которых получается удалением части термов из исходной сигнатуры [77]. Таким образом, два документа будут считаться схожими, если их наборы из К+1 сигнатур имеют пересечения, хотя бы по части из них.
I-Match показывает хорошие результаты на коротких документах. Однако среднее число слов на web-странице [20] - 650, что нельзя назвать коротким документом. Предложенный метод «описательных слов» с инвертированным индексом [14] более быстрый и результативный на больших документах. Его очень легко заменить инкрементной версией, т.к. база данных не требует перекластеризации при каждом возрастающем просмотре. При практически одинаковой точности алгоритмов этот метод более эффективен при наличии инвертированного индекса. 1.6.3 Статистические методы определения дублей
Основной критерий определения нечетких дублей статистическим методом - чем больше схожих элементов у документов, тем выше показатель их схожести. В качестве усовершенствования используются весовые коэффициенты значимости слов. В зависимости от метода их определения выделяют локальные и глобальные статистические алгоритмы [13].
Среди локальных алгоритмов можно назвать TF и Long Send. В первом алгоритме строится словарь частотных слов, упорядоченный по убыванию частоты, а затем выбираются и сцепляются в алфавитном порядке в строку 6 слов с наибольшими значениями tf— частота слова в документе. Во втором алгоритме строится подобный словарь, но из предложений документа, а затем выбираются и сцепляются в строку 2 самых длинных предложения.
«Глобальными» алгоритмами, которые опираются на частотные характеристики по всей коллекции, можно назвать TF IDF, TF RIDF, Heavy Sent. В алгоритме Heavy Sent документ разбивается на предложения. Для каждого предложения подсчитывается его «вес», равный сумме весов всех входящих в него слов. Затем выбираются и сцепляются в строку в алфавитном порядке 2 самых «тяжелых» предложения, которые подвергаются анализу.
Еще один метод определения нечетких дублей выведен из расстояния редактирования - расстояние Левенштейна. Изначально Левенштейн [25] определил расстояние редактирования для двух текстовых строк как количество перестановок и вставок, которые необходимо произвести для правки первой строки до второй. Впоследствии, этот подход был распространен и на тексты, представляя абзацы или предложения как слова, а слова как символы. Разработаны различные реализации алгоритмов, которые используются для построения систем проверки орфографии (spell chesker) [93], для сравнения текстовых файлов утилитой diff [96], для сравнения генов, хромосом и белков в биоинформатике [84], но все они могут быть адаптированы для определения схожести текстов.
Однако метод определения расстояния между текстовыми полями по Левенштейну обладает следующими недостатками: 1. При перестановке местами слов или частей слов получаются сравнительно большие расстояния; 2. Расстояния между совершенно разными короткими словами оказываются небольшими, в то время как расстояния между очень похожими длинными словами оказываются значительными. Существует ряд методов определения схожих документов, основанных на анализе тех или иных данных, например, латентно-семантический анализ или лингвистический метод. Латентно-семантический анализ (LSA) - метод обработки информации на естественном языке, анализирующий взаимосвязь между коллекцией документов и терминами, в них встречающимися. Основная идея латентно-семантического анализа [46] состоит в том, чтобы по матрице «термы-на-документы», получить матрицу, содержащую только к первых линейно независимых компонент, которая отражает основную структуру ассоциативных зависимостей, присутствующих в исходной матрице, и в то же время не содержит шума. Таким образом, каждый терм и документ представляются при помощи векторов в общем пространстве размерности к. Близость между любой комбинацией термов и/или документов может быть легко вычислена при помощи скалярного произведения векторов. Недостаток лингвистических методов - необходимость в больших математических и вычислительных ресурсах. Однако самые многообещающие методики обработки текстов имеют лингвистические методы [47]. Как показывает практика, существующие алгоритмы обработки текстов, частично использующие лингвистические методы, работают намного эффективнее методов без лингвистической составляющей.
Алгоритм определения дублей при online фильтрации
Далее оценивается объем текста в оставшемся дереве. Если больше минимального порога т - необходимо пересчитать вес нового поддерева. Последний шаг - выделение оставшихся узлов дерева в последний структурный блок.
Результатом выполнения алгоритма является набор выделенных из заданной web-страницы структурных блоков. Несмотря на использование не только табличного разбиения (TABLE, TR, TD), но и каскадных таблиц стилей CSS (используются теги DIV) при разработке web-сайтов, предлагаемый алгоритм работает, обеспечивая более качественное выделение блоков, хотя в ряде случаев теряется возможность дополнительной детализации страницы, которая была бы возможна при описании той же структуры табличными тегами. 3.2 Классификация запросов
Систематизируют и классифицируют поисковые запросы, основываясь на разных критериях [ПО - 112]: частота, длина запроса, конкурентоспособность, цели, география и т.д. От выбранной классификации, на базе которой будет строиться фильтрация дублей, зависит качество поисковой выдачи. 3.2.1 Принципы классификации по целям и синтаксису
В п. 1.8 предложена классификация поисковых запросов по 10 кассам. Однако в данной работе используется всего две классификации: по целям и по синтаксису. Все остальные классификации, во-первых, косвенно отражаются в этих двух, во-вторых, не несут значимости при выделении дублей. Рассмотрим каждый из видов запросов по целям и синтаксису более подробно, выделив отличительные характеристики, на основе которых будет строиться алгоритм определения типа запроса. В Приложении 4 представлена обобщенная информация по выделенным классификациям.
Классификация по целям включает следующие группы: 1. Навигационные запросы, с помощью которых пользователь пытается попасть на определенный сайт. Это могут быть бренд запросы, или названия конкретных сайтов. Отличительные характеристики: использование доменных имен; наличие в запросе доменной зоны; на данный запрос, как правило, имеется лишь один точный ответ - витальный сайт (по шкале асессорской оценки в Яндексе); данный запрос набирается пользователями как в английском варианте, так и на русском языке; запрос входит в список брендов, организаций; присутствуют слова-маркеры, такие как «сайт» или «страница». 2. Информационные запросы, целью которых найти требуемую информацию на одном или нескольких сайтах. Информационными поисковыми запросами являются такие, что содержат в себе вопросительные слова или подразумевающие их наличие. Кроме того, информационные запросы могут включать в себя слова «инструкция», «комментарии», «советы» и подобные. Дополнительными отличиями является углубление в тематику. Такие запросы часто многословны и набираются при уточнении высокочастотного запроса (определяется путем обработки статистики по уточнению запросов). 3. Транзакционные запросы требуют немедленного выполнения какого-нибудь действия доступного в сети - покупки, заказа, скачивания файла. Характерным для группы является высокий уровень конкуренции и частоты; наличие слов маркеров: купить, цена, скачать, сравнить, подписаться и т.п.; использование топономии; присутствие в запросе имен расширений файлов. 4. Общие запросы сложно отнести к каким-либо другим видам. Они могут быть как информационными, так и транзакционными, мотив пользователя по ним определить сложно. Часто общими являются однословные запросы без уточняющих фраз, сами запросы ВЧ/ВК. Дополнительной характеристикой может служить тот факт, что после такого запроса большинство пользователей производят уточнение запроса. 5. Мультимедийный тип запроса. Основной отличительной характеристикой является наличие слов-маркеров, таких как «фото», «музыка», «клип», «видео», «фотография» и т.п. 6. Служебные запросы также определяются лишь по маркерам — служебным операторам, которые предоставляет каждая поисковая система для профессионалов в области информационного поиска. Классификация по синтаксису имеет 4 класса: 1. Запросы с использованием поисковых операторов. Соответствует классу «Служебные запросы». 2. Поиск по цитате. Такие запросы обычно ищутся в кавычках или целыми предложениями. 3. Запросы на естественном языке. Выглядят так, будто бы вопрос задается живому человеку с предлогами, с логически связанными оборотами. 4. Запросы телеграфного стиля. В таких запросах опускаются предлоги и союзы, слова часто стоят в начальной форме. На рис. 3.2. представлена блок-схема алгоритма классификации запроса. Первоначально полученный запрос проверяется на присутствие кавычек или длинных предложений, служебные и «медийные» слова-маркеры. Данные виды запросов определить легко. Наиболее точно определить иные группы запросов можно также с помощью слов-маркеров, но с дополнительной проверкой (достаточно 1-2 признака того или иного вида). Если маркер отсутствует, тогда количество признаков, определяющих вид запроса должно быть от 3. Если после проверки на все виды получен отрицательный ответ и предвидится повторная проверка - запрос признается «общим». Алгоритм проверки запроса на принадлежность к классу «Навигационные запросы» можно представить следующей последовательностью действий: 1. Проверяем запрос - это название бренда или организации? Если да -переходим на шаг 2. Если нет - на шаг 3. 2. Если ответом на данный запрос служит лишь один витальный сайт, то запрос считаем навигационным. Если нет, то запрос либо общий, либо информационный. 3. Проверяем запрос - это название домена или присутствует доменная зона? Если да - запрос навигационный. Если нет, переходим на 4 шаг. 4. Запрос задается и на русском и на английском? Если да, и есть маркер - запрос навигационный. Если да, но маркера нет, переходим на шаг 1. Если ответ - нет и маркера нет — проверяет запрос на класс информационный и общий. Алгоритм проверки запроса на принадлежность к классу «Информационный запрос» можно представить следующей последовательностью действий:
Результаты практической апробации разработанных подходов
Как видно из рисунка, оптимальный порог фильтрации соответствует 48,5%. При таком границе получаем наилучшую точность, которая составляет 67%, и полноту, имеющую значение 100%, вычисления «неестественных» текстов. Также хочется отметить, что чем меньше замен производится, тем точность уменьшается - на процент точности повлияли данные по 1 группе, где замена производилась только 1 малочастотной буквы.
Следующий этап фильтрации - отсеивание сгенерированных текстов. Для качественной оценки разработанного подхода было подготовлено дерево решений на основе анализа 4000 текстов, 50% из которых были естественные, 50% - сгенерировано существующими генераторами, либо путем перевода с английского на русский, либо путем синонимизации документов образцов. Исходной коллекцией стала коллекция ROMIP By. Web16. Инструменты генерации и синонимизации были найдены в интернете (TextoGEN, Generating The Web 2.2, SeoGenerator и другие).
В целях сокращения временных ресурсов для генерации дополнительных массивов контента проверка метода детектирования сгенерированных текстов с помощью дерева решений проводилась на том же множестве, по которому стоилось дерево решений. В результате показатель полноты составил - 94 %, а показатель точности - 92%.
Для оценки метода фильтрации текстов, образованных путем синонимических замен была подготовлена база из 300 текстов, из которых одна треть — естественные тексты, остальные получены путем синонимизации в автоматическом или ручном режиме. В исследовании использовался словарь синонимов на 14 тыс. слов. В качестве синонимайзера (программа размножающая статьи при помощи синонимичных рядов), к которому подключался словарь синонимов, использовалась программа Night ArticleGen. В ручном режиме текст перефразировался с сохранением позиций основных ключевых слов. Результат проверки дал следующие результаты полноты и точности при разных порогах фильтрации (рис. 4.15).
График точности и полноты поиска синонимизированных текстов при разных порогах фильтрации Как видно из рисунка, оптимальный порог фильтрации соответствует 10%. При таком границе получаем наилучшую точность, которая составляет 98,6%, и полноту, имеющую значение 94,7%. Показатель F-меры равен 96,6%, что на 20% больше, чем при использовании метода шинглов. Так же стоит заменить, что на средних порогах чаще всего находятся пары с автоматическои синонимической заменой и предложенный метод распознает из на 50% лучше.
Последний уровень фильтрации - определение текстов с составным контентом. Для оценки качества данного фильтра было подготовлено порядка 100 текстов, где: - 30 текстов с 2 абзацами 1 автора, - 10 текстов с 3 абзацами 1 автора, - 30 текстов с 2 абзацами 2 авторов, - 10 текстов с 3 абзацами 3 авторов, - 20 текстов с 3 абзацами 2 авторов, Результат оценки работы фильтра представлен на рис. 4.16. Показатели получились достаточно высокими. Оптимальным порогом можно считать 60% при полноте 92 % и точности 90%. F-мера составила 91%. График точности и полноты поиска текстов с составным контентом при разных порогах фильтрации Данный результат сравнивать не с чем, т.к. подобные исследования ранее не проводились. Однако полученные точность и полнота выше на 20-30%, чем [52]. Если говорить об общей оценки методики offline фильтрации, то она проводилась на всех вышеописанных данных. В результате была получена 92,2% точности и 88,7% полноты, F-мера составила 90,5%. Если проводить аналогичную фильтрацию на основе шинглирования при оптимальном пороге фильтрации 58,3%, то результат будет меньше - полнота на 37,8%, точность на 1%, а F-мера на 25,1%. Полученные цифры говорят об эффективности разработанного подхода. 4.5.3 Экспериментальная проверка алгоритма определения первичного документа в кластере web-дублей В качестве тестовой коллекции было подготовлено 10 групп по 15 текстов, в каждой из которых был свой уникальный контент, но каждый текст в группе обладал соответствующими параметрами: 1) Тексты с других страниц с того же сайта, что и рассматриваемый текст, все остальные показатели средние 2) Тексты с другого сайта такой же тематике, все остальные показатели средние 3) Тексты с другого сайта другой тематики, все остальные показатели средние 4) Тексты с других страниц с того же сайта, что и рассматриваемый текст, показатели посещаемости высокие, возраст средний 5) Тексты с другого сайта такой же тематики, показатели посещаемости высокие, возраст средний 6) Тексты с другого сайта другой тематики, показатели посещаемости высокие, возраст средний 7) Тексты с других страниц с того же сайта, что и рассматриваемый текст, показатели посещаемости низкие, возраст средний 8) Тексты с другого сайта такой же тематики, показатели посещаемости низкие, возраст средний 9) Тексты с другого сайта другой тематики, показатели посещаемости низкие, возраст средний 10) Тексты с других страниц с того же сайта, что и рассматриваемый текст, показатели посещаемости средние, возраст большой 11) Тексты с другого сайта такой же тематике, показатели посещаемости средние, возраст большой 12) Тексты с другого сайта другой тематики, показатели посещаемости средние, возраст большой 13) Тексты с других страниц с того же сайта, что и рассматриваемый текст, показатели посещаемости средние, возраст маленький 14) Тексты с другого сайта такой же тематике, показатели посещаемости средние, возраст маленький 15) Тексты с другого сайта другой тематики, показатели посещаемости средние, возраст маленький Таким образом, рассмотрение разработанной методики можно производить как на горизонтальном уровне (сравнение результатов различных текстов между собой), так и на вертикальном уровне (сравнение результатов внутри одной группы). Т.к. определить с вероятность 100% документ, который должен являться первичным нельзя, было предложено оценивать качество работы разработанного алгоритма путем сопоставления результатов ранжирования по формуле (3.16) и результатов ранжирования всех рассматриваемых текстов в каждой группе с помощью шкалы рангов, построенной по экспертным оценкам.
Результат экспертных оценок (таблица 4.2) показал, что можно выделить общую закономерность в определении наиболее вероятного источника текста в кластере дублей. С большей вероятностью тот документ является первичным, на котором не только тексты одного автора, но и хорошая юза-билити и возраст, имеет высокий ранг. Ранг между тематичностью и авторством немного размытый, что объясняется малыми объемами проверяемой информации на странице. Однако общая тенденция прослеживается. В качестве проверочной шкалы была выбрана шкала, представленная в соответствующей строке таблицы 4.2.
