Порівняльний аналіз методів визначення нечітких дублікатів для Web-документів (частина 1)

Анотація

У роботі дається порівняльне експериментальне дослідження найбільш популярних сучасних методів виявлення нечітких дублікатів для текстових документів. Наводиться кількісна оцінка показників повноти, точності і F-міри. Набір текстів, використаний в експериментах — це веб-колекція РОМІП. Запропоновано два нових алгоритму, що мають високі показники якості.

1 Вступ

Проблема виявлення нечітких дублікатів є однією з найбільш важливих і важких задач аналізу веб-даних і пошуку інформації в інтернеті. Актуальність цієї проблеми визначається різноманітністю додатків, у яких необхідно враховувати «схожість», наприклад, текстових документів — це і поліпшення якості індексу і архівів пошукових систем за рахунок видалення надлишкової інформації, і об'єднання новин в сюжети на основі подібності цих повідомлень за змістом, і фільтрація спаму (як поштового, так і пошукового), та встановлення порушень авторських прав при незаконному копіюванні інформації (проблема плагіату або копірайту), та ряд інших.

Основним перешкодою для успішного рішення даної задачі є гігантський обсяг даних, що зберігаються в базах сучасних пошукових машин. Такий обсяг робить практично неможливим (в розумний час) її «пряме» рішення, шляхом попарного порівняння текстів документів. Тому останнім часом велика увага приділяється розробці методів зниження обчислювальної складності створюваних алгоритмів за рахунок вибору різних евристик (наприклад, хешування певного фіксованого набору «значущих» слів або речень документу, семплювання набору підрядків тексту, використання дактілограм та ін).

При застосуванні наближених підходів спостерігається зменшення (іноді вельми значне) показника повноти виявлення дублів.

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

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

2 Огляд ключових робіт з досліджуваної тематиці

Одними з перших досліджень в області знаходження нечітких дублікатів є роботи

U. Manber [2] і N. Heintze [3]. У цих роботах для побудови вибірки використовуються після-

послідовності сусідніх букв. Дактілограмма файлу ([2]) або документа ([3]) включає всі текстові підрядка фіксованої довжини. Чисельне значення дактілограмм обчислюється за допомогою алгоритму випадкових поліномів Карпа-Рабіна [4]. В якості запобіжного схожості двох документів використовується відношення числа загальних підрядка до

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

U. Manber використовував цей підхід для знаходження схожих файлів (утиліта sif), а N.

Heintze — для виявлення нечітких дублікатів документів (система Koala).

У 1997 році A. Broder et al. [1, 5, 6] запропонували новий, «синтаксичний» метод оцінки подібності між документами, заснований на представленні документа у вигляді безлічі всіляких послідовностей фіксованої довжини k, які складаються з сусідніх слів. Такі послідовності були названі «шинглі». Два документа вважалися схожими, якщо їх безлічі

шинглі істотно перетиналися. Оскільки число шинглі приблизно дорівнює довжині документа в словах, тобто є достатньо великим, авторами були запропоновані два методи семплювання для отримання репрезентативних підмножин.

Перший метод залишав тільки ті шинглі, чиї «Дактілограмми», які обчислюють за алгоритмом Карпа-Рабіна [4], ділилися без залишку на деяке число m. Основний недолік — залежність вибірки від довжини документа і тому документи невеликого розміру (у словах) представлялися або дуже короткими вибірками, або взагалі не мали таких. Другий метод відбирав тільки фіксоване число s шинглі з найменшими значеннями дактілограмм або залишав всі шинглі, якщо їх загальна кількість не перевищувало s.

Подальшим розвитком концепцій A. Broder et al. є дослідження D. Fetterly et al. [9], A. Broder et al. [16].

Для кожній ланцюжка обчислюються 84 дактілограмми за алгоритмом Карпа-Рабіна [4] з допомогою взаємно-однозначних і незалежних функцій, що використовують випадкові набори («min-wise independent ») простих поліномів. У результаті кожен документ можна представити як 84 шингли, які мінімізують значення відповідної функції.

Потім 84 шингли розбиваються на 6 груп по 14 (незалежних) шинглів у кожній. Ці групи називаються «супершінгламі». Якщо два документи мають схожість, наприклад, p~0.95 (95%), то 2 відповідних супершінгла в них збігаються з ймовірністю p14~0.9514~0.49 (49%).

Оскільки кожен документ представляється 6-тьма супершінглами, то ймовірність того, що у двох документів співпадуть не менше 2-х супершінглів, дорівнює: 1-(1-0.49)6-6*0.49*(1-0.49)5~0.90(90%). Для порівняння: якщо два документи мають схожість

тільки p~0.80(80%), то ймовірність збігу не менше двох супершінглів складає всього 0.026 (2.6%).

Таким чином, для ефективної перевірки збігу не менше 2-х супершінглов (і відповідно, підтвердження гіпотези про подібність змісту) кожний документ представляється всеможливими попарними поєднаннями з 6 супершінглів, які називаються «Мегашінгламі». Число таких мегашінглів рівно 15 (число сполучень з 6 по 2). Два документи подібні за змістом, якщо у них збігається хоча б один мегашінгл.

Ключова перевага даного алгоритму у порівнянні з дослідженнями A. Broder et al. в тому, що, по-перше, будь-який документ (у тому числі і дуже маленький) завжди представляється вектором фіксованої довжини, і, по-друге, схожість визначається простим порівнянням координат вектора і не вимагає (як у A. Broder) виконання теоретико-ножинних операцій.

Інший сигнатурний підхід, заснований вже не на синтаксичних, а на лексичних принципах, був запропонований A. Chowdhury et al. в 2002 і удосконалено в 2004 рр..[10, 11, 12].

Основна ідея такого підходу полягає в обчисленні дактілограмми I-Match для подання змісту документів. З цією метою спочатку для колекції документів будується словник L, який включає слова з середніми значеннями IDF, оскільки такі слова забезпечують, як правило, більш точні результати при виявленні нечітких дублікатів. Слова з великими і маленькими значеннями IDF відкидаються.

Потім для кожного документу формується безліч U різних слів, що входять до нього, і

визначається перетин U і словника L. Якщо розмір цього перетину більше деякого мінімального порогу (визначеного експериментально), то список слів, що входять до

перетин впорядковується, і для нього обчислюється I-Match сигнатура (хеш-функція SHA1).

Два документи вважаються схожими, якщо у них збігаються I-Match сигнатури (має місце колізія хеш-кодів). Алгоритм має високу обчислювальну ефективність, яка перевершує показники алгоритму A. Broder. Інша перевагою алгоритму (також, в порівнянні з A. Broder) є його висока ефективність при порівняно невеликих за розміром документів. Основний недолік — нестійкість до невеликих змін змісту документа.

Для подолання вказаного недоліку вихідний алгоритм був модифікований авторами, і в нього була запроваджена можливість багаторазового випадкового перемішування основного словника. Суть нових удосконалень полягає в наступному.

Додатково до основного словника L створюються K різних словників L1-LK, одержуваних шляхом випадкового видалення з початкового словника деякого невеликої фіксованої частини p слів, складової порядку 30% -35% від вихідного обсягу L.

Для кожного документу замість однієї обчіслюється (K +1) I-Match сигнатура за алгоритмом, описаним вище, тобто документ представляється в вігляді вектора розмірності (K+1), і два документи вважаються дублікатами, Якщо у них збігається хоча б одна з координат.

Якщо документ піддається невеликим змінам (порядку n слів), то ймовірність того, що принаймні одна з K додаткових сигнатур залишиться незмінною, дорівнює:

1-(1-pn)K (*)

Дійсно, ймовірність того, що зміни не торкнуться якого-небудь одного словника, дорівнює pn — ймовірності, що всі зміни потраплять у віддалену частину вихідного словника. Тоді (1-pn) — ймовірність, що сигнатура зміниться, а (1-pn)K — ймовірність, що всі сигнатури зміняться (оскільки додаткові словники формуються незалежно), отже, (*) — і є шукому ймовірність.

Ремомендовані значеннями параметрів, які добре показали себе на практиці є p=0.33 і K=10.

Алгоритм показав високі результати при використанні в різних додатках веб-пошуку і фільтрації спаму.

Схожий підхід описаний в патенті US Patent 6,658,423 W. Pugh [8] з Google. Автор пропонує повний словник документа розбити на фіксоване число списків слів за допомогою будь-якої функції хешування (наприклад, за допомогою залишку від ділення хеш-коду на число списків). Потім для кожного списку обчислюється дактілограмма і два документи вважаються подібними, якщо вони мають хоча б одну загальну дактілограмму. Автор наводить оцінки стійкості алгоритму до невеликих змін змісту вихідного документу. У роботі відсутні будь-які відомості про ефективність практичного застосування з міркувань

конфіденційності.

Ще одним сигнатурних підходом, також основаним на принципах лексичних (тобто використанні словника), є метод «опорних» слів, запропонованого С. Ільїнським та ін [13]. Суть алгоритму полягає в наступному.

Спочатку з індексу по деякому правилу (див. нижче) вибирається безліч з N слів (N — визначається експериментально), званих «Опорними». Потім кожен документ представляється N-мірним двійковим вектором, де i-а координата дорівнює 1, якщо i-ті «опорне» слово має в документі відносну частоту вище

певного порогу (встановлюваного окремо для кожного «опорного» слова), і дорівнює 0 у іншому випадку. Цей двійковий вектор називається сигнатурою документа. Два документи «Схожі», якщо у них збігаються сигнатури.

Загальні міркування для побудови безлічі «Опорних» слів такі:

  1. Безліч слів повинна охоплювати максимально можливе число документів

  2. «Якість» слова (див. нижче) повинно бути найвищим

  3. Кількість слів в наборі має бути мінімальним

Опишемо алгоритм побудови множини і вибору порогових частот.

Нехай «частота» це нормована частота слова в документа TF, що лежить в діапазоні 0...1, де 1 частота самого вживаного слова в документі.

Для кожного слова (одноразово) будується розподіл документів за такою «частотою» вживання в документі.

Проводимо кілька ітерацій, кожна з яких складається з двох фаз (1) і (2). В (1) максимізує покриття документів в індексі при фіксованій (обмеженій знизу) точності; в (2) максимізує точність при фіксованому

покритті.

Визначимо «точність» слова наступним чином: точність тим вище, чим менше зустрічальність слова в дельті-околиці даного значення відносної частоти (тобто чим менше документів з TF рівним TFthreshold±Δ). Частоту з найкращою точністю ми називаємо пороговою і запам'ятовуємо для подальшого використання в алгоритмі (див. Вище).

Після кожної ітерації відкидаємо самі «погані» слова. Після останньої ітерації залишаємо достатньо слів для хорошого покриття.

Цей метод, дозволяє, почавши з вибірки в сотні тисяч слів, залишити набір з 3-5 тисяч, розрахунок сигнатур по яким з застосуванням повнотекстового індексу здійснюється на мільярдному індексі кілька хвилин на пошуковому кластері Яндекса [17].

3 Ідея дослідження

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

обмеження існуючих підходів.

В якості основних показників якості роботи алгоритмів були обрані повнота, точність і F-міра. Передбачалося порівняти алгоритми по цих параметрах, а також визначити їх взаємну кореляцію і спільне покриття різними поєднаннями алгоритмів вхідної множини пар нечітких дублікатів.

Результати роботи кожного алгоритму (пари нечітких дублікатів) можуть бути агреговані так, що для будь-якої пари вихідних документів (docX, docY) вказувався список алгоритмів (A1, A2, ...), з точки зору яких ці документи були нечіткими дублікатами. Всі пари-кандидати, отримані хоча б одним алгоритмом, можна перевірити прямим текстовим порівнянням, що дозволить оцінити точність кожного алгоритму. Для порівняльної оцінки повноти алгоритмів можна використовувати ідею загального пулу, як максимальної

множини знайдених і верифікованих дублів.

переклад сатті:  Сравнительный анализ методов определения нечетких дубликатов для Web-документов Зеленков Ю.Г, Сегалович И.В. 2007

оригінал перекладу тут.

продовження на Розробці тут.

© 2009 - 2020, Розробка - соціальна ІТ спільнота.
Контакти: info@rozrobka.com
Правила користування