автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Математическое и программное обеспечение методов схожести WEB-документов и выделение первичного документа из кластера дублей

На правах рукописи

НЕЕЛОВА Наталия Валериевна

МАТЕМАТИЧЕСКОЕ И ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ МЕТОДОВ СХОЖЕСТИ \VEB-ДОКУМЕНТОВ И ВЫДЕЛЕНИЕ ПЕРВИЧНОГО ДОКУМЕНТА ИЗ КЛАСТЕРА ДУБЛЕЙ

Специальность 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

1 7 КОЯ 2011

Тула 2011

005001164

Работа выполнена в ФГБОУ ВПО «Тульский государственный университет»

Научный руководитель

- кандидат технических наук, доцент СЫЧУГОВ Алексей Алексеевич

Официальные оппоненты

- доктор технических наук, профессор ИЗОТОВ Виктор Николаевич

- кандидат технических наук, СОКОЛОВ Василий Алексеевич

ФГБОУ ВПО «Юго-Западный

Ведущая организация

^ г государственный университет»,

г. Курск

Защита состоится « декабря 2011 г. в часов на заседании диссертационного совета Д 212.271.07 при ФГБОУ ВПО «Тульский государственный университет» (300012, г. Тула, проспект Ленина, 92,9-101).

С диссертацией можно ознакомиться в библиотеке ФГБОУ ВПО «Тульский государственный университет» (300012, г. Тула, проспект Ленина, 92).

У/

Автореферат разослан «__» ноября 2011 г.

Ученый секретарь диссертационного совета

Ф.А. Данилкин

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

Объектом исследования диссертационной работы является процесс определения web-дублей и выделения первичного web-документа из кластера дублей.

Предметом исследования диссертационной работы являются методы определения дублей при ранжировании и индексировании web-документов и выделения первичного документа из кластера web-дублей.

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

Задачи исследования:

1. Анализ источников схожих web-документов.

2. Анализ существующих алгоритмов и методов определения схожих шеЬ-документов и выделение из кластера дублей первичного документа.

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

4. Создание методики выделения первичного документа из кластера web-дублей, позволяющей агрегировать различные аспекты выбора первичного документа (авторство, тематическая полнота, цитируемость и т.д.).

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

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

Научная новизна работы заключается в следующем:

1. Разработана методика online фильтрации дублей, основанная на введении порога фильтрации (фиксированное значение схожести, при котором документы считаются дублями) для каждого типа запроса при ранжировании документов, и методика offline фильтрации дублей, представляющая собой каскад фильтров, применяемый при индексировании документов и учитывающий современные способы генерации дублированного текста.

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

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

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

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

Достоверность полученных результатов подтверждается использованием предлагаемых методик при разработке программного обеспечения методов оценки схожести web-документов при индексировании и ранжировании документов, а также методов определения первичного документа в кластере web-дублей.

Положения, выносимые на защиту:

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

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

различных авторов.

3. Выражение определения первичного документа в кластере web-дублей и методики оценки авторства рассматриваемого текста, тематической полноты

ресурса и его популярности.

Реализация и внедрение результатов. Предложенные в работе методики детектирования дублей и определения первичного документа были успешно использованы автором для совершенствования системы управления и работы с корпоративными документами ООО «Рекламные технологии в Интернете», для разработки и поддержания систем поиска в ООО «СЕО НЬЮЗ», а также в качестве рекомендаций повышения эффективности документооборота в ЗАО «Ин-гейт Девелопмент». Результаты проведенных исследований реализованы в учебный процесс кафедры ЭВМ при преподавании дисциплин: «Безопасность систем баз данных», «Компьютерные технологии документооборота».

Апробация работы. Основные положения диссертационной работы легли в основу докладов на следующих конференциях: 1. Международная молодежная научная конференция «Гагаринские чтения» (Москва, МАТИ, 2009, 2010, 2011 гг.). 2. Всероссийская научно-техническая конференция «Интеллектуальные и информационные системы» (Тула, ТулГУ, 2009, 2011). 3. Всероссийская конференция с международным участием «Знания - Онтологии - Теории» (Новосибирск, ИМ им. С .Л.Соболева СО РАН, 2009). 4. Международная научно-практическая Интернет-конференция «Инновационные подходы к применению информационных технологий в профессиональной деятельности» (Белгород, Белгородский филиал НАЧОУ ВПО СГА, 2009). 5. Всероссийской научно-практической конференции с международным участием «Информационные технологии в профессиональной деятельности и научной работе» (Иош-кар-Ола, МГТУ, 2009). 6. VI региональная научно-практическая конференция аспирантов, соискателей и молодых ученых «Исследовательский потенциал молодых ученых: взгляд в будущее» (Тула, ТГПУ, 2010). 7. VI Международная научно-практическая конференция «Электронные средства и системы управления» (Томск, ТУСУР, 2010). 8. П Всероссийская научная конференция «Научное творчество XXI века» с международным участием (Красноярск, Научно-инновационный центр, 2010). 9. IX Всероссийская научно-техническая конференция «Техника XXI века глазами молодых ученых и специалистов» (Тула, ТулГУ, 2010). 10. 5-ая Всероссийская научно-практическая конференция «Системы управления электротехническими объектами» (Тула, ТулГУ, 2010).

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

Структура и объем диссертации. Диссертационная работа изложена на 168 страницах, включает И таблиц и 44 рисунка. Состоит из введения, четырех глав и заключения, списка литературы из 116 наименований и 7 приложений.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

обоснована их новизна.

В первой главе исследуется проблема нахождения схожих web-документов и существующие методы ее решения. Определяется понятие «схожести», под которым понимается оценка сопоставления документов на предмет дублированного содержания. Анализируются источники схожих web-документов. Рассматриваются основные методы определения дублей, предложенные A. Broder, U.Manber, В.И. Левенштейном, С. Ильинский и др., метрики оценки эффективности этих методов. Указываются их недостатки и невозможность определять схожесть документов, сгенерированных одним из современных способов дублирования текстов.

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

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

Отмечено, что разбиение документа на структурно-семантические блоки (вспомогательная и основная текстовая часть) при индексировании, предложенное Косиновым Д.И., положительно влияет на качество распознавания web-дублей. Обозначено, что разрабатываемые методики оценивают схожесть web-документов по их основным частям.

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

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

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

косвенные показатели.

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

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

Для определения типа запроса, вводимого пользователем в поисковую систему, была построена модель классификатора, представленная следующей алгебраической системой:

R=<Q,C,F,Rc/>, (!)

где О - множество запросов, подлежащих классификации; С - множество классов; F-множество описаний; Rc - отношение на С х F;f- операция классификации вида Q -> С. Отношение Rc имеет свойство:

то есть классу соответствует единственное описание. Обратное требование необязательно. Отображение/не имеет никаких ограничений, так что возможны ситуации, когда запрос может быть отнесен к нескольким классам:

3qeQ:f(g)^CqaCA\Cg\>l. (3)

Кроме сформулированной задачи классификации, определена задача разработки алгоритма обучения классификатора, под которой подразумевается частичное или полное формирование С, F, Rc и/на основе некоторых априорных данных. К разрабатываемому алгоритму предъявляются требования однозначности определения класса запросу, универсальности описания классов, и

полнота выделения характеристик запроса.

После формирования классов запросов каждому из них была поставлена в соответствие степень жесткости online фильтрации дублей, под которой понимается пороговое значение схожести документов: Vq e C3G, е G = Sj(di), где С - множество классов, G- множество степеней жесткости, Sj(d;) - схожесть

i-ro документа. „

Для определения степени жесткости online фильтрации дублей для разных типов запросов использовался метод экспертных оценок и в качестве модели был выбран метод парных сравнений. Для анализа согласованности оценок использовалась мера разброса, определяемая сравнением дисперсии суммарной матрицы экспертов с максимально возможной ее величиной. По оценкам объектов вычислялись интервалы жесткости для разных классов запросов.

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

Sj(xi,xj) —

IX; ГЛХ)\+\у}]\

\Xi^>Xj\

(4)

где х{ и X] - множество сравниваемых объектов, уч - множество синонимических замен во множествах X; и х]-.

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

Полные дубли Рис. 1. Схема определения схожести строк

Offline фильтрация производится на этапе индексирования документов с целью выявления дублей и сокращения индексных баз поисковых систем. Разработанная offline фильтрация должна определять тексты полученные неестественным способом:

— заменой русских букв английскими;

— генерацией контента;

— заменой слов их синонимами;

— изменением порядка абзацев, предложений, слов;

— сочетанием текстов разных источников.

Для выявления созданных одним из вышеперечисленных способов текстов было предложено использовать каскад соответствующих фильтров.

Для определения текстов с заменой русских букв на соответствующую ей латиницу каждому элементу текстового узла W = {wl,w2,...wi} ставилось в соответствие значение Н = {/г1,А2,...,hi} с помощью функции /н-

/А(w() = //,-, где ^ б Я. (5)

Далее производился подсчет Нр процента слов, чья характеристика /¡, превышает установленную эмпирическим путем критическую величину Нкрит :

%\1Ч>Нк?т] ioo%_ |W|

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

Предложена модель определения класса неестественных текстов, порожденных с помощью различных генераторов, например, на основе цепей Маркова. Подобные компьютерные программы способны создавать правильные тексты с точки зрения языковых норм, но лишённые смысла. Вся текстовая составляющая В документа!) имеет ряд признаков Р = {px,p2,-Pi}> трудно контролируемых автором. Для построения автоматического классификатора неестественных текстов используются выделенные признаки в машинном обучении. В качестве разрабатываемого подхода лежит алгоритм на основе деревьев решений С4.5.

Для обнаружения документа с контентом, образованным путем синонимических замен, предложено рассматривать его содержимое как информационную последовательность косвенных признаков слов, закодированную двоичным кодом, который образует отпечаток документа. Для более наглядного представления отпечатка предлагается использовать RGB кодирование (аддитивная цветовая модель). Формирование отпечатков 5, и Sj обоих текстов двух документов d, и dj происходит посредством функции^:

fs-.d-*S = {Sl,S2,...,sn},n>0. (7)

Получение информационного нечеткого образа i = /(w) с заданной погрешностью г осуществляется с помощью функции^:

fr.P(w)-*[i±r]£I (8)

где слово wiefv = {w[,w2,...,wi} имеет ряд косвенных признаков p = {pl,p2,-,pm}>а ie / = {г1,/2,...,1/}- информационная структура.

В качестве косвенных признаков предложено рассматривать морфологические особенности каждого слова текста. Косвенные признаки Р = {рьр2,--;рт}, участвующие в создании отпечатка документа 5, равны для синонимов, имеющих одинаковое значение, но разное написание: "(3w, е W^wj е Wj)Piw„Wj | wf * Wj) ■ (Hi; е да,. € Ij)P{iJj I t, = ij) ■ (9)

Pi^Pj

Для получения информационного отпечатка S каждый признак pi подвергается кодированию fc:

fe:Tp-*S. (10)

Указанная функция fc каждому слову ставит в соответствие RGB код. По умолчанию, все отглагольные формы получили зеленые отгенки,

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

Для сравнения полученных отпечатков 5,- ={sil,si2,:.,sin} и Sj ={Sjl,Sj2,.-,sjrt}, представляющих собой пиксельное изображение в системе RGB, построенное функцией^, и определения схожести документов d, и dj используется метод когерентных цветовых векторов:

) - /ь, (sjk ))| + |(Льг ) - Ль* ))|) . (П)

¿=1

гДе /ь*> /.ь.г ~ функции, определяющие соответственно когерентность и

некогерентность пикселя, п - количество пикселей в отпечатке s.

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

Разработан подход по определению количества источников текста в одном документе. Подход основывается на частотных характеристиках каждого абзаца. Было предложено использовать гипергеометрический критерий для сравнения частот значений признаков:

minfabi)

Р0= (12)

j=max(0,j пг)

где s — /Wj +тг,пц и т2 - количество появлений признака в первом и втором тексте, щ и п2 - объемы текстов в разрезе рассматриваемого признака, х = max(0, j - пг),тт(я,,i), /г(4?, л,,«2) - гипергеометрическое распределение: h(^,nun2) = cxnic^icsni+ni. (13)

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

Алгоритм определения вероятности авторства описан ниже:

1. На сайте At каждого документа D, отбирается I страниц с текстовой составляющей, которые объединяются в один текст Bi = Вп UBi2 U... UВп.

2. Объединяются тексты с сайта и рассматриваемый текст: В,В' = 2?, U В .

3. Рассчитывается длина сжатых текстов В ¡В' и В, с помощью функции

сжатия fr =

4. Для каждого документа D, определяется разность между длинами рассчитанных сжатых текстов: fa (В, Ц) = | fr {В¡В )| -1 fr (5,)|

5. Чем меньше рассчитанная разность, тем больше вероятность, что на странице D, располагается авторский текст В .

Для расчета полноты тематики ресурса строятся векторы тематичности на основе наиболее частотных слов и их веса рассматриваемого документами группы документов сайта. С помощью (14) определяется близость векторов Тц

и ТА. Чем ближе векторы, тем тематическая полнота ресурса, содержащего документ Vi, больше:

<14)

В качестве оценки удобства использования ресурса предложены поведенческие показатели: средняя посещаемость сайта GA и страницы GD, среднее время пребывания посетителя на сайте ТЛ и на странице TD, средний показатель отказа сайта FD, а также возраст страницы Fa. Для оценки удобства использования ресурса вводится функция: fu(Fa ,GA,GD,TA,TD,FD) = U(Af,Д).

В качестве дополнительных параметров выделения первичного документа выступают: индекс цитируемости (PRa ), рассчитывающийся на основе ссылочного графа документа; метка чистоты (/>,), показывающая сколько раз данный ресурс был замечен в плагиате; метка авторства (М ), указывающая, сколько копий ссылается на документ Д ; возраст создания страницы (Fa).

Предлагается определять первичный документ в кластере web-дублей с помощью рассмотренных выше показателей следующим образом:

F!(Di) = (kl~ + k2-FJl + kyPRJ-k* -ku5 ■ р^ (15)

J a

Для оценки эффективности разработанных подходов использовались стандартные метрики: точность (16), полнота (17) и F-мера (18).

Рг~, (16)

а + о

а + с 2-Рг • R.

(18)

где а - количество найденных пар дубликатов, совпадающих с «релевантными» парами; Ъ - количество найденных пар дубликатов, не совпадающих с «релевантными» парам; с - количество ненайденных пар дубликатов, совпадающих с «релевантными» парами.

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

В ходе работы было выделено 11 классов запросов. Был разработан алгоритм, позволяющий определять класс любого запроса. В качестве степеней же-

11

сткости предложено оперировать 5-ю классами. Увеличивать количество классов не следует из-за большой естественной размытости границ. С помощью экспертных оценок были сопоставлены классы запросов и классы фильтрации (Табл. 1) с высоким показателем согласованности.

Название класса Фильтрация Согласованность

1 Информационный запрос на естественном языке 70-90% 0,0832

? Информационный запрос в телеграфном стиле 30-90% 0,0544

3 Навигационный запрос на естественном языке 90-100% 0,1024

4 Навигационный запрос в телеграфном стиле 70-100% 0,088

5 Транзакционный запрос на естественном языке 10-30% 0,0776

6 Тпаязакниошшй запрос в телеграфном стиле 0-30% 0,0752

7 Общий запрос на естественном языке 30-70% 0,0688

8 Общий запрос в телеграфном стиле 30-70% 0,0232

0 Мультимедийные запросы 0-10% 0,0696

1П Служебный запрос 0-10% 0,0792

11 Запрос в кавычках или точная фраза 0-10% 0,0408

Г а^ЧСI иХСИСПИ шшишци" ------------

нию стандартного метода, основанного на коэффициенте Джаккарда. Если полученное значение оказывалось критическим, то производилось повторное сравнение с помощью модифицированного метода, учитывающего синонимические замены. Описанный алгоритм представлен на рис. 2.

Пересчет коэффициента ' с учетом предварительной обработки

Рис. 2. Алгоритм определения схожести аннотаций Разработанный алгоритм определения схожести аннотаций с обработкой на синонимические замены дал хороший результат по выявлению дублей, но показал плохое время. Для оптимизации алгоритма был распараллелен процесс поиска синонимов и введено удаление стоп-слов. Все вышеперечисленное позволило сократить временные затраты в 3065 раз.

При offline фильтрации для детектирования текстов, образованных заменой русских букв латинскими аналогами, было использовано выражение:

(19)

где Сj - число вхождений леммы в рассматриваемом тексте, Т, - общее число вхождений всех лемм во множестве.

12

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

Алгоритм определения дублей по косвенным признакам строился на представлении текста в виде цепочки RGB кода (рис.3.). Первоначально текст подвергался лемматизации. После в соответствие каждой граммеме ставился RGB код. В качестве системы координат была выбрана система: количество слов в предложении на количество предложений в тексте (рис.4.). Далее полученные отпечатки текстов в виде графических интерпретаций сравнивались между собой.

^ Начало ^

Сравниваемые Получение Сравнение отпечатком

документы Лемматизация RGB

отпечатков

Принятие решения о схожести

^ Конец ^

Рис. 3. Алгоритм определения синонимизированных текстов Таким образом, рассматривая текст как закодированную последовательность косвенных признаков, определяющих смысловые значения слов и представленных в виде RGB кода, и используя современные методы оценки схожести изображений, можно решить проблему определения дублей, образованных с помощью синонимических замен.

___■□■□СМ

□ggOOEB

ЩГ3

□□□□bbbdbqbi

■истин!

□□нваввсш

□оиЬвовавсзвпввввви □ашввввшшвав

ИВВО!

шававвшшавв ВВпвв"

ВШВГ—

gИОНОВ® ■SBQMi

■BDBOBDCDi □□□BBDBBEM ОИВ0В® SBBBBBSBB

сяш

ШВВВВЯО!

■■■■blbobcb ■ШВвшшрваввв

швиеевпввв ввашвщвававв

QDDDBOBQBB _

ивваЛвввшвшИ

ЕзвиаввдаЭаэаов! CUBODBLIBBB

пав

mat

□ППЗВВВООПВВИВ ■BBBBrjBBDBGCBB

□вввопвввв

вавввввВиваога

иввиивавввивщвшиввввв

—МИТВИГГТ"

га

(1) Оригинал

(2) Нечеткий дубль

В.

шошаааоаса

□S0QBBBB

(3) Оригинал

■@аааавв

Рис. 4. Представление текста в RGB коде.

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

Л Начало 1-у

Текст документа

3

Разбиение текста на I абзацев b,»... Ьа|... Ьа,

сЯ - С^ГПЗЗ

Представление блока Ь, вектором {х,..хг.....х„)

X,,,...,*„<) ■-f-lxi,.....x„i) {

__ж--, Построение Ма Нормирование М'„ ----

I

Построение и нормирование М, Расчет общей рассогласованности ---т

Рис 5. Схема определения качества контента Алгоритм определения вероятности авторства состоит из следующих шаГОВ"

1. ' Отбор «-количества текстов на ресурсе, где п определяется исходя из требуемого объема обучающей выборки - более 100 тыс. букв.

2 Предварительная обработка рассматриваемого и отобранных текстов, представляющая собой удаление переносов, приведение всех слов к нижнему регистру и расстановка знаков переноса строк после каждого слова. 3. Расчет длины сжатых текстов ВВ' и В, с помощью программы в

которой используется алгоритм \JL11 и Хаффмана

4 Расчет модуля разности соответствующих длин. Контрольный текст в относится к автору рассматриваемого сайта -А, с наименьшим значением этой

нормированной разности.

В результате эксперимента и проверки правильности определения авторства была получена точность в 56%. Данный процент невысокий, что объясняется работой с малыми объемами контента на странице. Однако полученное значение вполне удовлетворяет требованиям текущей задачи, т.к. входит в оо-

щую формулу определения первичного документа (15), позволяющей скорректировать принятие решения об авторстве.

В виду того, что авторский контент чаще всего располагается на сайте, раскрывающем более полно тематику рассматриваемого документа, то в качестве одного из параметров первичного документа был введен показатель тематической полноты ресурса. Описанный выше алгоритм расчета полноты тематики (14) показал 100%-ное отсутствие ошибок на действительно разных тематиках. Проверяемые документы, расположенные на сайтах с более полно раскрывающейся тематикой, на практике имели более высокие показатели. При уменьшении степени близости тематики уменьшался и рассчитываемый показатель (Табл. 2).

Таблица 2. Результаты проверки тематической полноты ресурса

Процент полноты Процент ошибок

Одинаковая тематика 44% 28%

Близкая тематика 25% 50%

Разная тематика 2% 0

Для оценки удобства использования ресурса строилась линейная формула, коэффициенты которой подбирались с помощью регрессионного анализа:

/.(^,еЛ,еи,ГЛ,7'и^и) = 15.747 + 2.58.^ + 0.803-+ +1.311 ■■ Ты + 0.158 • вЛ1 + 3.887 • Тм - 46.36 • Ра, где /V - возраст рассматриваемой страницы;

- средняя посещаемость рассматриваемой страницы; Та - среднее время на рассматриваемой странице;

бг/!1. - средняя посещаемость всего сайта; ТА< - среднее время нахождения на всем сайте;

- показатель отказа сайта.

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

Г. (Д) = (0,021----+0,043 • Р'а + 0,001 • V) ■ (1 + 0,305 ■ РЯа) •

Л+0,113 (21)

• -(1,007)и+0'044 ■(1,002)'М)'079 • ехр(1,057 •/>,)- 0,069,

где fa - показатель авторства документа Д, - возрастной нормированный показатель документа Д, РКа - показатель цитируемости документа А, V - тематическая ценность документа Д-, V - показатель удобства использования ресурса А, | Д е Д., М' - маркер источника документа Д-, р, - «метка чистоты» документа Д.

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

стандартную установку .NET Framework. Программный модуль состоит из трех подмодулей - online фильтрация, offline фильтрация и выделение первичного документа из кластера дублей. Каждый подмодуль позволяет проводить эксперименты по соответствующим направлениям.

Для проверки online фильтрации были подготовлены два вида результатов ответа поисковой системы на запрос пользователя. Первая группа поисковой выдачи представляла собой стандартную с фильтрацией дублей без учета типа запроса, вторая - результат фильтрации с учетом типа запроса. Эксперты проводили сравнение двух выдач, на основании их оценок был определен коэффициент вариации (22), равный 8%, что соответствует высокой степени согласованности и говорит о высоком качестве предложенного online метода фильтрации с учетом типа запроса.

v = -

пы

(22)

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

Оценка качества модифицированного метода на основе коэффициента Джаккарда проводилась в сравнении с результатами методов Джаккарда и шинглов. Разработанный метод, учитывающий синонимические замены, дает прирост точности в среднем на 5-10% (относительно альтернативных методов) и более значительный прирост полноты в среднем на 15-20% на интервале определения нечетких дублей (рис.6).

U

1

03

8

« I 0,6

0,4

0,2

0

—±sT7 'S

20

до

60

80

100

Пор«

-Джакиардссинонимамм

--Джаккард

Шинглы(З)

Рис. 6. График F-меры при разных порогах фильтрации Offline фильтрация состоит из пяти этапов проверки множества документов. Каждый метод подвергался экспериментальной проверки. Для каждого была составлена своя проверочная масса текстовых коллекций.

Метод определения сгенерированных текстов показал результат в 67/о точности и 100% полноты при пороге фильтрации 48,5%. Фильтрация сгенерированных текстов показала 94 % полноты и 92% точности.

Для оценки метода фильтрации текстов, образованных путем синонимических замен, была подготовлена база из 300 текстов, из которых одна треть -

16

естественные тексты, остальные получены путем синонимизации в автоматическом или ручном режиме. Результаты детектирования сравнивались с результа-

Рис. 7. График результатов поиска синонимизированных текстов при разных

порогах фильтрации Как видно из рис.7, оптимальный порог фильтрации соответствует 10%. При такой границе получаем наилучшую точность, которая составляет 98,6%, и полноту, имеющую значение 94,7%. Показатель Е-меры равен 96,6%, что на 20% больше, чем при использовании метода шинглов. В диссертации отмечено, что на средних порогах чаще всего находятся пары с автоматической синонимической заменой, и предложенный метод распознает их на 50% лучше.

Последний уровень фильтрации - определение текстов с составным контентом. Для оценки качества данного фильтра было подготовлено порядка 100 текстов, представляющих разное сочетание количества авторов. Показатели получились достаточно высокими. Оптимальным порогом можно считать 60% при полноте 92 % и точности 90%. Р-мера составила 91%.

Если говорить об общей оценке методики ой1ше фильтрации, то в результате экспериментов была получена точность в 92,2% и полнота в 88,7%, Р-мера составила 90,5%. При проведении аналогичного эксперимента, но с использованием метода шинглов при оптимальном пороге фильтрации 58,3%, результат получился меньше - полнота на 37,8%, точность на 1%, а Р-мера на 25,1%. Указанные цифры говорят об эффективности разработанного подхода.

Для оценки алгоритма определения первичного документа в кластере дублей было подготовлено 10 групп по 15 текстов, в каждой из которых был свой уникальный контент, но каждый текст в группе обладал разными параметрами. Было предложено использовать мнение экспертов по ранжированию текстов внутри одной группы. По созданному таким образом эталону проводилось сравнение с полученными результатами эксперимента (рис. 8).

о 20 40 60 80 100

Порог

« средний процент количество совпанений

Рис. 8. Качество поиска авторского текста при разных порогах Оптимальный результат по количеству совпадений в 70% при среднем проценте совпадений со шкалой рангов 67,3% наблюдается при пороге 40%, что можно назвать приемлемым для определения первичного документа.

В заключении диссертационной работы сформулированы основные результаты и перспективы в развитии исследований.

Основные результаты работы

Проведенные в рамках диссертации исследования позволили получить следующие результаты, имеющие практическое и научное значение:

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

2. Разработана методика offline фильтрации дублей, представляющая собой каскад фильтров, применяемый при индексировании документов, что позволяет сокращать индексные базы поисковым систем.

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

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

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

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

7. Проведена экспериментальная проверка предложенных алгоритмов и методов, реализованных в программном обеспечении. Результаты проведенных экспериментов позволили подтвердить качество разработанных подходов и обратить внимание на их возможное использование при создании соответствующих программных продуктов.

По теме диссертации опубликовано 18 работ, основными из которых являются:

1. Неелова Н.В. Предварительная обработка строк при критическом коэффициенте Джаккарда для улучшения вычисления схожести веб-документа // Материалы П Всероссийской конференции с международным участием «ЗНАНИЯ - ОНТОЛОГИИ - ТЕОРИИ» (30HT-09) 22-24 октября 2009 г. - Новосибирск: Институт математики им. C.J1. Соболева СО РАН Российский Фонд Фундаментальных Исследований Российская Ассоциация Распознавания Образов и Анализа Изображений, 2009. - Т.2, с. 20-27.

2. Неелова Н.В. Вычисление нечетких дублей по формуле Джаккарда с учетом синонимических замен и стоповых слов / Н.В. Неелова, A.A. Сычугов // Известия Тульского государственного университета. Серия: Технические науки. - Тула: Тульский государственный университет, 2009. - Вып.4,4.1, с. 209-218.

3. Неелова Н.В. Исследование влияния стоп слов на вычисление нечетких дублей лексическим методом Джаккарда // Вычислительная техника и информационные технологии. Сборник научных статей. Вып. 1. - Тула: Изд-во ТулГУ, 2009. - с. 117-129.

4. Неелова Н.В. Методы кластеризации веб-документов как инструмент повышения качества ответа поисковых систем // Инновационные подходы к применению информационных технологий в профессиональной деятельности: сборник трудов междунар. науч.-практ. Интернет-конф. - Белгородский филиал НАЧОУ ВПО СГА. - Белгород: ГиК, 2009. - с. 301-309.

5. Неелова Н.В. Исследование лексического метода вычисления схожести строк с учетом предварительной обработки. // Известия Тульского государственного университета. Серия: Технические науки. Вып.2. - Тула: Изд-во ТулГУ, 2009. - 4.2 с. 202-212.

6. Неелова Н.В. Исследование влияния косвенных признаков текста на детектирование нечетких дублей / Н.В. Неелова, A.A. Сычугов // Сборник материалов VI региональной научно-практической конференции аспирантов, соискателей и молодых ученых «Исследовательский потенциал молодых ученых: взгляд в будущее» - Тула: Изд-во ТГПУ им. Л.Н.Толстого, 2009. - С.249-258.

7. Неелова Н.В. Сравнение результатов детектирования дублей методом шинглов и методом Джаккарда / Н.В. Неелова, A.A. Сычугов //

I ; " i

Вестник РГРТУ. - Рязань: 2010. - № 4 (выпуск 34), с.72-78.

8. Неелова Н.В. Моделирование процесса обнаружения схожих web-документов на основе косвенных признаков / Н.В. Неелова, A.A. Сычугов // Техника XXI века глазами молодых ученых и специалистов: материалы докл. IX Всерос. науч.-техн. конф. студентов, магистрантов, аспирантов и молодых ученых. - Тула: Изд-во ТулГУ, 2010. - С. 320-325.

9. Неелова Н.В. Детектирование текстовых нечетких дублей по отпечаткам в виде RGB цепочек // Научное творчество XXI века: материалы П Всероссийской научной конференции с международным участием (г.Красноярск, март 2010 г.) - Красноярск: Научно-инновационный центр, 2010. -№4(10). -4.11., с. 109-110.

10. Неелова Н,В. Модель определения авторитетной копии среди множества схожих web-документов // Научно-технические ведомости СПбГПУ. Раздел: Проблемы передачи и обработки информации. -СПбГПУ, 2011. - Вып.5, с. 13-17.

11. Неелова Н.В. Определение схожести web-документов при помощи RGB преобразования // Электронные средства и системы управления: Материалы докладов VI Международная научно-практическая конференция (13-16 октября 2010 г., ТУСУР). - Томск: В-Спектр, 2011: В

2ч.-Ч.1, с. 106-108.

12. Неелова Н.В. Программная реализация методов фильтрации дублей и определения первичного web-документа / Н.В. Неелова, A.A. Сычугов // Интеллектуальные и информационные системы: Материалы Всероссийской научно-технической конференции. - Тула: Изд-во ТулГУ, 2011. - С. 28-30.

Изд. лиц. ЛР №020300от 12.02.97. Подписано в печать 8.11 2011 г. Формат бумаги 60x84 ]/16 .Бумага офсетная. Усл. печл. 1,1 Уч.-издл. 1,0 Тираж 100 экз. Заказ 044 Тулбский государственный университет 300012, г. Тула, пр. Ленина, 92 Отпечатано в Издательстве ТулГУ 300012, г. Тула, пр. Ленина, 95

Введение.

Глава 1. Проблема обнаружения и определения авторства схожих web-документов.

1.1 Информационный поиск и задача распознавания дублей.

1.2 Задача распознавания схожих документов.

1.3 Определение понятия схожих документов.

1.4 Источники схожих web-документов.

1.5 Основные метрики подобия web-документов.

1.6 Методы обнаружения схожих документов.

1.7 Предварительная обработка документов.

1.8 Варианты классификации поисковых запросов.

1.9 Кластеризация и классификация документов.

1.10 Структурно-семантическое разбиение.

1.11 Борьба с плагиатом.

1.12 Постановка задачи обнаружения дублей и выделения первичного web-документа.

1.13 Выводы.

Глава 2. Разработка модели оценки схожести документов и определения первичного документа в кластере дублей.

2.1 Модель представления web-документов блоками.

2.2 Модель классификации запросов и степень фильтрации дублей.

2.3 Метод экспертных оценок для градации online фильтрации дублей

2.4 Метод определения дублей при online фильтрации.

2.5 Методы offline фильтрации дублей.

2.6 Структурная схема модели определения дублей.

2.7 Методы оценки эффективности алгоритмов поиска дубликатов.

2.8 Определение первичного документа в кластере web-дублей.

2.9 Выводы.

Глава 3. Алгоритмизация процессов детектирования web-дублей и определения первичного документа.

3.1 Алгоритмы разбиения web-страниц на семантические блоки.

3.2 Классификация запросов.

3.3 Алгоритм градации при online фильтрации.

3.4 Алгоритм определения дублей при online фильтрации.

3.5 Алгоритмы для offline фильтрации.

3.6 Алгоритмы определения первичного документа.

3.7 Выводы.

Глава 4. Программная реализация методов фильтрации дублей и определения первичного web-документа.

4.1 Структура программного обеспечения.

4.2 Программная реализация.

4.3 Графический интерфейс.

4.4 Последовательность работы с программой.

4.5 Результаты практической апробации разработанных подходов.

4.6 Выводы.

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

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

Нерешенная проблема дублирования информации на государственном уровне несет более глобальные последствия. Согласно данным РАН1 с 1995 года число диссертаций, утвержденных Высшей аттестационной комиссией (ВАК) растет: увеличение за 15 лет составило 230% от первоначальной цифры. Подготовка части таких диссертаций заключается в присвоении ранее написанных работ либо в компилировании из нескольких диссертаций. Следствие данной проблемы - отсутствие развития научных направлений, многочисленные выплаты стипендий, развитие «серого» рынка заказных диссертаций.

Главным распространителем дублированной информации как в случае с дублированной информацией на персональной технике, так и при написании курсовых, дипломных, диссертационных работ является Интернет. Более 30-40% документов в Интернете имеют дубликаты [23, 81], различного происхождения и степени схожести. Актуальность проблемы дублирования для поисковых систем определяется:

- распространением плагиата не только в сети Интернет, но и в общественной жизни (написание курсовых работ, рефератов, дипломных работ);

1 http://www.ras.ru/

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

- распространением спама в электронном виде через почтовые сервисы;

- осложнением вычислений при объединении новостных сообщений в сюжеты;

- разработкой функции поиска документов по заданному шаблонному содержанию и документов, использующих цитирование;

- порождением необходимости определения первоисточника в кластере схожих документов.

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

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

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

Объектом исследования диссертационной работы является процесс определения web-дублей и выделения первичного web-документа из кластера дублей.

Предметом исследования диссертационной работы являются методы определения дублей при ранжировании и индексировании web-документов и выделения первичного документа из кластера web-дублей.

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

Задачи исследования:

1. Анализ источников схожих web-документов.

2. Анализ существующих алгоритмов и методов определения схожих web-документов и выделение из кластера дублей первичного документа.

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

4. Создание методики выделения первичного документа из кластера web-дублей, позволяющей агрегировать различные аспекты выбора первичного документа (авторство, тематическая полнота, цитируемость и т.д.).

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

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

Научная новизна работы заключается в следующем:

1. Разработана методика online фильтрации дублей, основанная на введении порога фильтрации (фиксированное значение схожести, при котором документы считаются дублями) для каждого типа запроса при ранжировании документов, и методика offline фильтрации дублей, представляющая собой каскад фильтров, применяемый при индексировании документов и учитывающий современные способы генерации дублированного текста.

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

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

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

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

Достоверность полученных результатов подтверждается использованием предлагаемых методик при разработке программного обеспечения методов оценки схожести web-документов при индексировании и ранжировании документов, а также методов определения первичного документа в кластере web-дублей.

Положения, выносимые на защиту:

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

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

3. Выражение определения первичного документа в кластере web-дублей и методики оценки авторства рассматриваемого текста, тематической полноты ресурса и его популярности.

Реализация и внедрение результатов. Предложенные в работе методики детектирования дублей и определения первичного документа были успешно использованы автором для усовершенствования системы управления и работы с корпоративными документами ООО «Рекламные технологии в Интернете», для разработки и поддержания систем поиска в ООО «СЕО НЬЮЗ», а также в качестве рекомендаций повышения эффективности документооборота в ЗАО «Ингейт Девелопмент». Результаты проведенных исследований реализованы в учебный процесс кафедры ЭВМ при преподавании дисциплин: «Безопасность систем баз данных», «Компьютерные технологии документооборота».

Апробация работы. Основные положения диссертационной работы легли в основу докладов на следующих конференциях: 1. Международная молодежная научная конференция «Гагаринские чтения» (Москва, МАТИ, 2009, 2010, 2011 гг.). 2. Всероссийская научно-техническая конференция «Интеллектуальные и информационные системы» (Тула, ТулГУ, 2009, 2011). 3. Всероссийская конференция с международным участием «Знания - Онтологии - Теории» (Новосибирск, ИМ им. С.Л.Соболева СО РАН, 2009). 4. Международная научно-практическая Интернет-конференция «Инновационные подходы к применению информационных технологий в профессиональной деятельности» (Белгород, Белгородский филиал НАЧОУ ВПО СГА, 2009). 5. Всероссийской научно-практической конференции с международным участием «Информационные технологии в профессиональной деятельности и научной работе» (Йошкар-Ола, МГТУ, 2009). 6. VI региональная научно-практическая конференция аспирантов, соискателей и молодых ученых «Исследовательский потенциал молодых ученых: взгляд в будущее» (Тула, ТГПУ, 2010). 7. VI Международная научно-практическая конференция «Электронные средства и системы управления» (Томск, ТУ СУР, 2010). 8. II Всероссийская научная конференция «Научное творчество XXI века» с международным участием (Красноярск, Научно-инновационный центр, 2010). 9. IX Всероссийская научно-техническая конференция «Техника XXI века глазами молодых ученых и специалистов» (Тула, ТулГУ, 2010). 10. 5-ая Всероссийская научно-практическая конференция «Системы управления электротехническими объектами» (Тула, ТулГУ, 2010).

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

В работах, опубликованных в соавторстве, лично соискателю принадлежат: разработка алгоритма вычисления нечетких дублей по формуле Джак-карда с учетом синонимических замен и стоповых слов [27], сравнительный анализ эффективности метода шинглов и метода Джаккарда с предварительной обработкой [43], использование в качестве критерия схожести документов косвенные признаки [30], построение математической модели детектирования нечетких дублей с помощью косвенных признаков [35], представление косвенных признаков слов текста в виде цепочки RGB кода [29], разработка программного обеспечения определения авторства [42].

Структура и объем диссертации. Диссертационная работа изложена на 168 страницах, включает 11 таблиц и 44 рисунка. Состоит из введения, четырех глав и заключения, списка литературы из 116 наименований и 7 приложений.

Заключение

Проведенные в рамках диссертации теоретические исследования позволили получить результаты, имеющие практическое и научное значение:

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

2. Разработана методика offline фильтрации дублей, представляющая собой каскад фильтров, применяемый при индексировании документов, что позволяет сокращать индексные базы поисковым систем.

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

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

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

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

7. Проведена экспериментальная проверка предложенных алгоритмов и методов, реализованных в программном обеспечении. Результаты проведенных экспериментов позволили подтвердить качество разработанных подходов и обратить внимание на их возможное использование при создании соответствующих программных продуктов.

1. Агеев М. Извлечение значимой информации из web-страниц для задач информационного поиска / М. Агеев, И. Вершинников, Б. Добров // Материалы конференции Интернет-Математика 2005. - М.: Яндекс, 2005. -С. 283-301.

2. Ашманов И. Оптимизация и продвижение сайтов в поисковых системах. / И. Ашманов, А. Иванов. СПб.: Питер, 2008. - 400 е.: ил.

3. Байгарова Н.С. Методы индексирования и поиска визуальных данных / Н.С. Байгарова, Ю.А. Бухштаб, A.A. Горный // Препринт Института прикладной математики им. М.В. Келдыша РАН. М.: ИПМ им. М. В. Келдыша РАН, 2000. - №7,18 с.

4. Гасфилд Д. Строки, деревья и последовательности в алгоритмах // Информатика и вычислительная биология. СПб.: БХВ-Петербург, 2003. -654 е.: ил.

5. Громова Н.М., Громова Н.И. Основы экономического прогнозирования: Учебное пособие. М.: Академия Естествознания, 2006. - URL: http://www.monographies.ru/10 (дата обращения: 15.07.2011)

6. Евланов Л.Г., Кутузов В.А. Экспертные оценки в управлении. М.: Экономика, 1978. - 133 с.

7. Кабанов Э. Классификация поисковых запросов Электронный ресурс] / В 3 частях. 2009. - URL:http://kabanov.biz/reklama-v-internete-2/klassifikaciya-poiskovyx-zaprosov-chast-l.html (дата обращения: 18.07.2011)

8. Кириченко K.M. Обзор методов кластеризации текстовых документов / К. М. Кириченко, М. Б. Герасимов // Компьютерная лингвистика и интеллектуальные технологии. Сб. научных статей. Под ред. A.C. Наринь-яни. М.: Наука, 2001. - Т. 2., с. 161-165.

9. Кнут Д. Э. Искусство программирования: учеб. пособие: в 3 т. М.: Вильяме, 2008 - Т. 1: Основные алгоритмы / С. Г. Тригуб. - 3-е изд. -2008. - 720 с.

10. Колмогоров А.Н. Основные понятия теории вероятностей / Теория вероятностей и математическая статистика. 2-е изд. М.: Наука, 1974. - 119 с.

11. Кондратьев М.Е. Анализ методов кластеризации новостного потока Электронный ресурс] // Материал конференции RCDL'2006. М.: 2006. - URL: http://rcdl.ru/doc/2006/paper92vl.pdf (дата обращения: 04.05.2010)

12. Контент Рунета Электронный ресурс]: информационный бюллетень по данным поиска Яндекса на лето осень 2009. Систем, требования: Adobe Acrobat Reader. - URL: http:// download.yandex.ru/company/yandexoncontentautumn2009.pdf (дата обращения: 10.01.2010)

13. Косинов Д. И. Разработка математического обеспечения оценки схожести web-документа на основе структурно-семантического разбиения : дис. . канд. техн. наук : 05.13.11 : защищена 25.12.08. Воронеж, 2008. - 146 с. - Библиогр.: с. 116-126 - 04200901970.

14. Кукушкина О. В. Определение авторства текста с использованием буквенной и грамматической информации Текст] / О. В. Кукушкина, А. А. Поликарпов, Д. В. Хмелев // Проблемы передачи информации. М., 2001.-Т. 37, №2, С. 96-108.

15. Левенштейн В. И. Двоичные коды с исправлением выпадений, вставок и замещений символов // Доклады Академий Наук СССР. М.: 1965. - Т. 4, с. 845-848.

16. Максимов Ю.А. Алгоритмы решения задач нелинейного программирования / Е.А Филлиповская, Ю.А. Максимов М.: МИФИ, 1982. - 421 с.

17. Неелова Н.В. Исследование влияния стоп слов на вычисление нечетких дублей лексическим методом Джаккарда // Вычислительная техника и информационные технологии. Сборник научных статей. Вып. 1. Тула: Изд-во ТулГУ, 2009. - С. 117-129.

18. Неелова Н.В. Исследование лексического метода вычисления схожести строк с учетом предварительной обработки // Известия Тульского государственного университета. Серия: Технические науки. Тула: Изд-во ТулГУ, 2009. - Вып.2, ч.2 с. 202-212.

19. Белгородский филиал НАЧОУ ВПО СГА. Белгород: ГиК, 2009. - с. 301-309.

20. Неелова Н.В. Модель определения авторитетной копии среди множества схожих web-документов // Научно-технические ведомости СПбГПУ. Раздел: Проблемы передачи и обработки информации. СПбГПУ, 2011.- Вып.5, с. 13-17.

21. Неелова Н.В. Модель определения авторства среди web-дублей // XXXVII Гагаринские чтения. Научные труды Международной молодежной научной конференции в 8 томах. Москва, 5-8 апреля 2011 г. -М.: МАТИ, 2011. Т.4., с. 20-21.

22. Неелова Н.В. Определение нечетких дублей по косвенным признакам текста // XXXVI Гагаринские чтения. Научные труды Международной молодежной научной конференции в 8 томах. Москва, 6-10 апреля 2010 г. М.: МАТИ, 2010. - Т.4, с. 33-35.

23. СО РАН Российский Фонд Фундаментальных Исследований Российская Ассоциация Распознавания Образов и Анализа Изображений, 2009. -Т.2, с. 20-27.

24. Неелова Н.В. Сравнение результатов детектирования дублей методом шинглов и методом Джаккарда / Н.В. Неелова, A.A. Сычугов // Вестник РГРТУ. Рязань: 2010. - № 4 (выпуск 34), с. 72-78.

25. Неелова Н.В. Функция удаления нейтральных слов при вычислении нечетких дублей лексическим методом Джаккарда // Интеллектуальные и информационные системы: Материалы Всероссийской научно-технической конференции. Тула: Изд-во ТулГУ, 2009. - С. 149-151.

26. Некрестьянов И. Обнаружение структурного подобия html-документов / И. Некрестьянов, Е. Павлов // Труды четвертой всероссийской конференции RCDL'2002. Дубна, Россия: 2002. - Т. 2, с. 38-54.

27. Некрестьянов И.С. Тематико-ориентированные методы информационного поиска: Дис. канд. физ-мат. наук: 05.13.11 / С-Пб. гос. унив. Санкт-Петербург, 2000. - 80 с.

28. Никконен А.Ю. Устранение избыточности и дублирования сюжетов новостных сообщений // Интернет-Математика. Сборник работ участниковконкурса / отв. ред. П. И. Браславский. Екатеринбург: Изд-во Урал, ун-та, 2007.-С. 157-167.

29. Справочник по прикладной статистике / Под ред. Э. Ллойда, У. Ледер-мана. -М.: Финансы и статистика, 1989. Т. 1., 512 с.

30. Троелсен Э. Язык программирования С# 2010 и платформа .NET 4 пер. с англ.]. М.: Вильяме, 2011. - 1392 с.

31. Хмелёв Д.В. Алгоритмы сжатия в определении авторства Электронный ресурс]. М.: МГУ, 2001. - URL: http://old.philol.msu.ru/~lex/articles/complex.htm

32. Хмелев Д.В. Распознавание автора текста с использованием цепей A.A. Маркова // Вестн. МГУ. Сер. 9: филология. М.: 2000. - №2, 115-126 с.

33. Хмелев Д.В. Сложностной подход к задаче определения авторства текста // I Международный конгресс исследователей русского языка "Русский язык: исторические судьбы и современность". Сборник тезисов. -М.: МГУ, 2001. с. 426-427.

34. Цыганов Н.Л. Исследование методов поиска дубликатов веб-документов с учетом запроса пользователя / Н.Л. Цыганов, М.А. Циканин // Интернет-математика 2007: Сб. работ участников конкурса. Екатеренбург: Изд-во Урал, ун-та, 2007. - с. 211-222.

35. Шахиди А. Деревья решений С4.5 математический аппарат Электронный ресурс]: Часть 2. - M.:BaseGroup Labs. - URL: http://www.basegroup.ru/library/analysis/tree/mathc45part2/

36. Ardizzone E. Motion and Color-Based Video Indexing and Retrieval / E. Ard-izzone, M. La Cascia, D. Molinelli // 13th International Conference on Pattern Recognition (ICPR'96). IEEE Computer Society Washington, DC. 1996. -Vol.3, 135 p.

37. Arthur D. How Slow is the k-means Method? / D. Arthur , S. Vassilvitskii. // Proceedings 22nd ACM Symposium on Computational Geometry (SoCG). -New York, NY, USA: ACM, 2006. 144-153 pp.

38. Baeza-Yates R. A., Ribeiro-Neto B. A. Modern Information Retrieval. New York: ACM Press and Harlow, England: Addison Wesley Longman Ltd., 1999.-513 pp.

39. Bar-Yossef Z. Template detection via data mining and its applications / Z. Bar-Yossef, S. Rajagopalan // WWW'02: Proceedings of the 11th international conference on World Wide Web. New York, NY, USA: ACM, 2002. -580-591 p.

40. Bayardo R.J. Scaling up all pairs similarity search / R.J. Bayardo, Y. Ma, R. Srikant //, Proceedings of the 16th international conference on World Wide Web. Banff, Alberta, Canada: ACM, 2007. - 131-140 pp.

41. Benczur A.Web spam detection via commercial intent analysis / A. Benczur, I. Biro, K. Csalogany, T. Sarlos // Proceedings of AIRWeb 2007. New York, NY, USA: ACM, 2007. - 89-92 pp.

42. Brin S. Copy detection mechanisms for digital documents / S. Brin, J. Davis, H. Garcia-Molina // SIGMOD '95: Proceeding of the 1995 ACM SIGMOD international conference on Management of data. New York, NY, USA; ACM Press, 1995. - 398-409 pp.

43. Brin S. The PageRank Citation Ranking: Bringing Order to the Web / L. Page, S. Brin, R. Motwani, T. Winograd // Technical report. Stanford Digital Library Technologies Project. Stanford, CA, 1998.

44. Broder A. A taxonomy of web search I I ACM SIGIR Forum. New York, NY, USA: ACM, September 2002. - Vol. 36(2), 3-10 pp.

45. Broder A. Min-wise independent permutations / A. Broder, M. Charikar, A. M. Frieze, M. Mitzenmacher // Proceedings of the thirtieth annual ACM symposium on Theory of computing. New York, NY, USA: ACM Press, 1998. - 327-336 pp.

46. Broder A. On the resemblance and containment of documents // SEQUENCES'97: Proceedings of the Compression and Complexity of Sequences 1997. Washington, DC, USA: IEEE Computer Society, 1997. - 2129 pp.

47. Broder A. Syntactic clustering of the Web / A. Broder, S. Glassman, M. Ma-nasse, G. Zweig // Proceedings of the 6th International World Wide Web Conference. Essex, UK: Elsevier Science Publishers Ltd., 1997. - 11571166 pp.

48. Broder A. Algorithms for duplicate documents Электронный ресурс] / IBM Research. 2005. Системные требования: Adobe Acrobat Reader. URL: http://www.cs.princeton.edu/courses/archive/spr05/cos598E/bib/Princeton.pdf (дата обращения: 17.03.2011)

49. Chowdhury A. Collection Statistics for Fast Duplicate Document Detection. / A. Chowdhury, O. Frieder, D. Grossman, M. C. McCabe // Proceedings of ACM Trans. Inf. Syst. New York, NY, USA: ACM, 2002. - Vol. 20, №2, 171-191 pp.

50. Dumains S. T. Indexing by Latent Semantic Analysis / S. T. Dumains, G. W. Furnas, T. KXandauer // Journal of the American Society for Information Science JASIS. New York, NY, USA: ASIS&T, 1990. - Vol. 41, №6, 391407 pp.

51. Gomes D. Managing duplicates in a web archive / D. Gomes, A.L. Santos, M.J. Silva // SAC '06 Proceedings of the 2006 ACM symposium on Applied computing. New York, NY, USA: ACM, 2006. - 818-825 pp.

52. Gozde C. Efficient computational methods for sequence analysis of small RNAs. Canada: Simon Fraser University, 2007. - 66 pp.

53. Graves S. Automatic extraction of generic web page components: Master's thesis in computational linguistics. Uppsala, Sweden: Uppsala University, 2004. - URL: http://stp.ling.uu.se/exarb/arch/2004graves.pdf (дата обращения: 13.06.2011)

54. Greg P. Comparing images using color coherence vectors / P. Greg, R. Zabih, J. Miller // MULTIMEDIA '96: Proceedings of the fourth ACM international conference on Multimedia. New York, NY, USA: ATM, 1996. - 65-73 pp.

55. Gupta S. Context-based content extraction of html documents: Ph. D. thesis. -New York, NY, USA: Columbia University, 2006.

56. Heintze N. Scalable document fingerprinting // Proceedings of the 2nd USENIX Workshop on Electronic Commerce. 18-21 November 1996, Oakland, California. Berkeley, CA: USENIX, 1996. - 191-200 pp.

57. Hoad T.Methods for identifying versioned and plagiarised documents / T. Hoad, J. Zobel // Journal of the American Society of Information Science and Technology. New York, NY, USA: ASIS&T, 2003. - Vol. 54, №3, 203215 pp.

58. James P. L. Computer programs for detecting and correcting spelling errors // Magazine "Communications of the ACM" (December 1980). New York, NY, USA: ACM, 1980. - Vol. 23, №12, 676 - 687 pp.

59. Li W. Random texts exhibit Zipfs-law-like word frequency distribution // IEEE Transactions on Information Theory. Canada, USA: IEEE Transactions, 1992. - Vol. 38, №6,1842-1845 pp.

60. Lin D. An information-theoretic definition of similarity // ICML '98: Proceedings of the Fifteenth International Conference on Machine Learning.

61. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 1998. 296304 pp.

62. MacKenzie. D. Comparing and Merging Files with GNU Diff and Patch / D. MacKenzie, R. Stallman, P. Eggert. UK: Network Theory Ltd., 1997. - 120 pp.

63. Manber U. Finding similar files in a large file system // WTEC94: Proceedings of the USENIX Winter 1994 Technical Conference. Berkeley, CA, USA: USENIX Association, 1994. - 2-3 pp.

64. Manku G.S. Detecting near-duplicates for web crawling / G.S.Manku, A. Jain, A.D. Sarma // WWW '07 Proceedings of the 16th international conference on World Wide Web, Banff, Alberta, Canada, May 2007. New York, NY, USA: ATM, 2007. - 141-150 pp.

65. Manning C. D., Schütze H. Foundations of statistical natural language processing. Cambridge, MA, USA: MIT Press, 1999. - 620 pp.

66. Mooers C.N. Application of Random Codes to the Gathering of Statistical Information: Ph. D. thesis. Cambridge, USA: MIT Press, 1948. 76 pp.

67. Porter M. F. An algorithm for suffix stripping // Program: Electronic Library and Information Systems. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 1997. - Vol. 40, №3,211-218 p.

68. Pugh W.M. H. Detecting duplicate and near-duplicate files // United States Patent 6658423 (December 2, 2003). -2003.

69. Quinlan J. R. C4.5: Programs for Machine Learning. San Francisco, С A, USA: Morgan Kaufmann Publishers Inc., 1993.

70. Salton G. A vector space model for automatic indexing: Technical Report / G. Salton, A.Wong, C.S.Yang // Communications of the ACM. Ithaca, NY, USA: Cornell University, 1975. - Vol. 18, №11, 613-620 pp.

71. Segalovich I. A fast morphological algorithm with unknown word guessing induced by a dictionary for a web search engine Электронный ресурс]. -MLMTA, 2003. URL: http://yandex.ru/articles/iseg-las-vegas.xml (дата обращения 09.07.2011)

72. Sibson R. SLINK: An optimally efficient algorithm for the single-link cluster method // The Computer Journal. King's College Research Center. -King's College, Cambridge: Cambridge University Statistical Laboratory, 1973.-30-34 pp.

73. Singhal A. Pivoted document length normalization: Technical Report / A. Singhal, C. Buckley, M. Mitra, G. Salton. Ithaca, NY, USA: Cornell University, 1995.-21-29 pp.

74. Smith J.R. Tools and Techniques for Color Image Retrieval / J.R. Smith, S.-F. Chang. // Proceedings SPIE Conference on Storage and Retrieval for Image and Video Database IV (February 1996). San Jose, CA: 1996. - 426437 pp.

75. Willett P.The Porter stemming algorithm: then and now // Program: Electronic Library and Information Systems. London: ASLIB Publications, 2006. - Vol. 40, №3, 219-223 pp.

76. Zamir O. E. A Phrase-Based Method for Grouping Search Engine Results: PhD Thesis, University of Washington, Department of Science & Engineering. Washington, USA: Unviersity of Washington, 1999.

77. Zobel J. The case of the duplicate documents: Measurement, search and science / J. Zobel, Y. Bernstein // Proceedings of the APWeb Asia Pacific Web Conference China: Springer, 2006. - 26-39 pp.

78. Уязвимости Скорость (220 байт/с) Вх. данные Размер хэша Стандарт о 3=1 Название

79. Были найдены коллизии для функции сжатия МЕ)5 2) Хэш-функция подвержена атакам "грубой силы" 100.738 512 бит 128 бит ИБС 1321 1992 Мй5

80. На текущий момент не обнаружено 48.462 512 бит 160 бит ИРБ рив 180-1 1995 8НА-1

81. На текущий момент не обнаружено 8.246 1024 бит 512 бит ИРБ рив 180-2 2000 БНЛ-512

82. На текущий момент не обнаружено 9.977 256 бит 256 бит ГОСТ Р34.11-94 1994 ГОСТ Р34.11-94о