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

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


Вычисление одинаковых страниц.

Под одинаковыми я понимаю страницы, текстовая версия которых (приведенная к канонической форме) обладает одинаковой контрольной суммой. Контрольная сумма – уникальное число, поставленное в соответствие некоторой текстовой единице. В данном случае речь идет о всем документе. Контрольная сумма вычисляется с помощью алгоритма CRC32.

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

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

Проблема дублирования информации возникает двумя путями. Первый - документы расположенные в разных местах в одинаковой форме:
• Документы тиражируемые на сайтах (статьи, рефераты и пр.)
• Учебники и онлайн документация (программ, приборов, языков программирования и пр.)
• FAQ (Frequently Asked Questions) или ЧАВО (Часто Задаваемые ВОпросы)
• Страницы хранящиеся на нескольких сайтах-дубликатах
• Юридические документы
• Описание сайтов, фирм, услуг в разных каталогах

Второй – документы, фактически представляющие из себя один и тот же документ, но имеющие незначительные отличия, такие как:
• Это различные версии одного и того же документа
• Это один и тот же документ, но с разным форматированием
• Это один и тот же документ, но с различными исходящими ссылками на странице
• Это один и тот же документ, но оформленный в соответствии с требованием заказчика
• Это один и тот же документ, но с расположенной на странице контактной информацией
• Это один и тот же документ, но с различными графическими элементами и подписями к ним (например каталог товаров или работ)
• Объединенный с информацией с другого сайта документ большего объема
• Усеченный в меньший формат документ

Для решения поставленной задачи я воспользовался методом Андрея Бродера (Andrei Broder) в 1997 [6]. Он разработал алгоритм, использующий для анализа схожести двух документов пересекающиеся куски текста или «шинглы» (от слова shingles, «черепички, чешуйки»). Контрольной суммой шингла мы будем называть его числовое значение.

Метод «шинглов».

Будем называть сходством двух документов A и B число между 0 и 1, такое, что если сходство близко к 1, то это означает, что два документа «приблизительно похожи».
Подобно этому, под вложенностью A в B будем понимать число, между 0 и 1, такое, что если вложенность близка к 1, то это означает, что A почти целиком содержится в B.

Пусть D – совокупность слов некоторого документа. Перекрывающие друг друга последовательности, содержащиеся в D, будем называть шинглами. Определим S(D,w), как совокупность всех уникальных шинглов размера w содержащихся в документе D.

Например, строка разбитая с помощью пятисловных шинглов (w=5)

(astronomers have found over a hundred planets orbiting alien suns)

будет выглядеть так:

{(astronomers have found over a), (have found over a hundred), (found over a hundred planets), (over a hundred planets orbiting), (a hundred planets orbiting alien), (hundred planets orbiting alien suns)}

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

Для шинглов одинакового размера сходство двух документов A и B определяется как отношение числа одинаковых для обеих страниц шинглов к общему количеству различных шинглов.

Подобно этому вложенность A в B определяется отношением числа одинаковых для обеих страниц шинглов к числу шинглов страницы A.

Отсюда вытекает, что сходство это число между 0 и 1, и всегда верно равенство r(A,A)=1, что означает, что документ похож на 100% или, другими словами, это два идентичных документа. Таким образом, чем больше значение r(A,B), тем больше сходство двух документов. Подобно этому, вложенность принимает значение между 0 и 1, и если , тогда c(A,B)=1 и значит A полностью (на 100%) включено в B.

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

Как мы увидели раньше, можно рассчитать значения шинглов для документа D, сохранить результаты для каждой страницы, а затем, поочередно сравнивая их, получить значения схожести для всех пар документов. Но подобное воплощение алгоритма в жизнь не вполне практично. Дело в том, что размер обучающей выборки составляет более 10 000 000 HTML документов преобразованных в текстовый формат, что накладывает серьезные ограничения на быстродействие системы и, соответственно, устанавливает жесткие требования к разрабатываемую алгоритму. Частично проблема снимается тем, что отыскание похожих страниц мы проводим в пределах одной рубрики, не проводя таким образом сравнения с документами из других тем. Но, тем не менее, сравнение всех шинглов одного документа со всеми шинглами другого документа займет слишком много времени (ведь в документе, как не трудно подсчитать, количество шинглов лишь на w-1 меньше чем слов).

Решением проблемы в классическом алгоритме Бродера является использование шинглов кратных какому-нибудь небольшому числу (10-30). Критерий выборки, в данном случае, получается не привязанным к особенностям текста, так как значения контрольных сумм для разных документов распределены равномерно. Преимущества такого подхода очевидны, так как существенно сокращается количество сравниваемых величин без значительного ухудшения качества работы алгоритма.

Пусть V(D) - совокупность всех шинглов кратных m, где m - кратность шинглов используемых для анализа сходства.

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

Для выбора значения m в зависимости от размера документа я использовал классификацию страниц по объему текста, присваивая им следующие ранги:
• ранг 1 – страница имеет длину от 0 до 99 слов
• ранг 2 – страница имеет длину от 100 до 999 слов
• ранг 3 – страница имеет длину не менее 1000 слов

Значение m в зависимости от ранга выбирается следующее:
• m=10 для документов ранга 1
• m=20 для документов ранга 2
• m=40 для документов ранга 3

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

Итак, метод шинглов для определения схожести документов реализуем следующим образом:
• приводим извлеченные из HTML текстовые страницы к каноническому виду (удаляя «лишние» пробелы, удаляя символы перевода строк и приводя буквы к нижнему регистру)
• выбираем размер шингла w=10
• в зависимости от ранга документа выбираем одно из трех значений m. m1=10, m2=20, m3=40
• выбираем порог сходства двух документов равным sim=0.8
• сравниваем документы на схожесть (для документов одного ранга) и на включенность

Алгоритм метода шинглов

Теоретически, применить метод для отыскания похожих страниц в выборке не составляет труда:
• находим документ в выборке
• считаем контрольные суммы шинглов
• выбираем шинглы, контрольные суммы которых кратны m
• сравниваем шинглы каждой пары документов и смотрим, переходит ли значение порог сходства, тем самым признавая два документа «приблизительно похожими»
• объединяя пары «приблизительно похожих» документов создаем кластеры подобных документов

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

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

На третьем этапе создаем список всех пар документов, которые содержат какие либо общие шинглы, вместе с общим количеством одинаковых шинглов. Для этого берем отсортированную по парам [контрольная сумма, ID документа] таблицу и расширяем ее до таблицы с полями [ID документа A, ID документа B, число общих шинглов], отсортированную по ID документа A.

На последнем этапе делаем полную кластеризацию. Проверяем каждую тройку [ID документа A, ID документа B, число общих шинглов] и решаем, переходит ли каждая пара установленный нами порог для схожести. Если да, то добавляем ссылку между этими страницами в результирующую таблицу с полями [ID документа A, ID документа B, значение схожести], содержащую ID похожих между собой документов и значение их схожести. Эта фаза потребует большого количества постоянной памяти, так как нам придется хранить полную структуру данных похожих страниц.



Список литературы:


[6] «Syntactic Clustering of the Web» Andrei Z. Broder, Steven C. Glassman, Mark S. Manasse
WWW, 1997 Адрес в Интернет: