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

Коротко:

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

Це продовження першої частини.

4 Опис методів і алгоритмів

Для практичного дослідження були обрані методи і алгоритми визначення нечітких дублікатів, перераховані в Табл.1.

ім'я Назва
A0 MD5
A1 TF
A2 TF*IDF
A3 TF*RIDF
A4 Long Sent
A5 Heavy Sent
A6 Megashingles
A7 Lex Rand
A8 Log Shingles
A9 Descr Words
A10 Opt Freq

Таблиця 1. Методи та алгоритми визначення нечітких дублікатів.

Нижче наводяться короткі описи алгоритмів, які досліджуються, в яких використовуються наступні позначення:

N — кількість документів в колекції;

tf — частота слова в документі;

tf_max — максимальна частота слова в документі;

df — число документів у колекції, містять дане слово;

cf — сумарна частота слова в колекції;

dl — довжина документа;

dl_avg — середня довжина документа в колекції.

4.1 A0 — MD5

Даний алгоритм насправді знаходить “точні” дублікати і включений в список з метою порівняння підсумкових статистик для повних та нечітких дублікатів. Як сигнатури документа використовується хеш-функція MD5 [19], обчислена для всього документа.

4.2 А1 — TF

Ідея цього і ряду наступних алгоритмів (А1-А5) доволі очевидна, в якості аналога приведемо роботу [18], в якій аналізується сімейство схожих алгоритмів для задач знаходження переміщених документів у вебі. У відповідності до цієї роботи назвемо “локальними” алгоритми, які не використовують загальну статистику колекції (А1, А4) і “глобальними” ті, які опираються на частотні характеристики по всій колекції (А2, А3, А5).

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

4.3 А2 — TF*IDF

По всій колекції будується словник, ставлячи кожному слову число документів, в яких воно зустрічається хоча б один раз (df) і визначається середня довжина документу (dl_avg). Потім будується частотний словник документу і для кожного слова вираховується його “вага” wt по формулі Okapi BM25 з параметрами k=2 і b=0.75 [14]:

wt = TF*IDF, де

TF = tf/[2*(0.25+0.75(dl/dl_avg))+tf]

IDF = log[(N-df+0.5)/(df+0.5)]

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

4.4 А3 — FT*RIDF

Коротко теорія. Основна ідея RIDF (Residual IDF) [15] полягає в порівнянні двох способів підрахунку кількості інформації (в сенсі визначення К. Шеннона), що міститься в повідомленні про те, що дане слово входить у деякий документ (щонайменше один раз). Перший спосіб, статистичний, це звичайний IDF=-Log (df/N). Другий спосіб, теоретичний, оснований на моделі розподілу Пуассона, яка передбачає, що слова в колекції документів розподіляються випадковим і незалежним чином, рівномірно розсіюючись з деякої середньої щільністю. У цьому випадку відповідна кількість інформації дорівнює P_IDF =-log(1-exp(-cf/N)). Тоді,

RIDF=IDF — P_IDF = — log(df/N) + log(1 — exp(-cf/N))

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

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

wf=TF*RIDF, де

TF=0.5+0.5*tf/tf_max

RIDF=-log(df/N)+log(1-exp(-cf/N))

Потім вибираються і зчіплюються в алфавітному порядку в рядок 6 слів з найбільшими значеннями wt. Як сигнатури документа обчислюється контрольна сума CRC32 отриманого рядка.

4.5 А4 — Long Sent

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

4.6 А5 — Heavy Sent

Документ розбивається на речення. Для кожного речення підраховується його «вага» ws рівний сумі ваг wt всіх слів, які в нього входять. Ваги wt підраховуються за формулами алгоритму A2. Потім вибираються і зчіплюються у рядок в алфавітному порядку 2 самих «Важких» речення. Як сигнатура документа обчислюється контрольна сума CRC32 отриманого рядка.

4.7 А6 — Megashingles

Алгоритм реалізований за принципами, викладеними в [9].

Спочатку обчислюється безліч всіх 5-слівних шинглів. Так як схожість 0.95 здається нам занадто сильною, ми брали схожість 0.75. Пряма схема Fetterly (з 84 функціями і 14 шинглами в 1-м мегашінгл) давала повноту практично 0.00. Тому ми зупинилися на 36 функціях, побудованих за допомогою випадкових поліномів і реалізують дактілограмми Карпа-Рабіна [4]. Вибираються 36 шингл, мінімізують значення відповідних функцій.

Далі 36 шингли розбиваються на 6 груп по 6 і визначаються 6 «супершінглів», з яких складаються всеможливі парні сполучення, які називаються «мегашінглом». Число таких сполучень з 6 по 2 дорівнює 15. Всі ці 15 мегашінглів складають сигнатуру документа, які давали повноту 33% для пороговогї відмінності 0.75, 42% для 0.80 і 50% для 0.85.

(p6~0.806~0.26 (26%); 1-(1-0.26)6-6*0.26*(1-0.26)5~0.42 (42%)).

4.8 А7 — Lex Rand

Алгоритм реалізований за принципами, викладеними в [12]. Спочатку по всій колекції будується словник, аналогічний використаному в алгоритмі A2 з якого видаляються слова з найбільшими і найменшими значеннями IDF. Потім на основі цього словника генеруються 10 додаткових словників, які містять приблизно на 30% менше слів, ніж у вихідному. Слова видаляються випадковим чином.

Для кожного документа будується 11 I-Match сигнатур (див. вище оглядову частину статті). Дублікатами вважаються документи хоча б з одною співпавшою сигнатурою. Виявляється, що такий підхід вельми істотно, в порівнянні з A2 (більш ніж у 2 рази) підвищує повноту виявлення дублікатів при зниженні відносної точності всього на 14%.

4.9 А8 — Log Shingles

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

Спочатку обчислюється безліч всіх 5-слівних шинглів (слова в кінці документу “завертаються” на початок). Потім з цієї множини відбираються шингли, що діляться на ступеня числа 2. Вони й складають точну сигнатуру документа.

4.10 А-9 — Descr Words

Алгоритм реалізований за принципами, викладеними в [13] і технікою, описаної вище. Спочатку по всій колекції будується словник «опорних» слів і обчислюються виконавчі векторні сигнатури документів, які потім кластеризуються в групи нечітких дублікатів на основі ознаки збігу сигнатур.

4.11 А-10 — Opt Freq

Коротке пояснення. Алгоритм реалізує метод «оптимальної пошукової частоти», запропонований М. Масловим (Яндекс [17]), і використовується для пошуку схожих документів у широкому спектрі додатків, від веб-пошуку до кластеризації новин. Суть його полягає в наступному. Замість класичної метрики TF*IDF (див. алгоритм A2) пропонується її модифікований варіант. Вводиться евристичне поняття «оптимальної частоти» для слова рівне — ln(10/1000000)=11.5, тобто «оптимальним» вважається входження слова в 10 документів з 1000000. Якщо реальне значення IDF менше «оптимального», то

воно трохи (за законом параболи) підвищується до IDF_opt = SQRT(IDF/11.5), а якщо більше, то істотно (як гіпербола) знижується до IDF_opt = 11.5/IDF.

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

wt = TF*IDF_opt, де

TF = 0.5 + 0.5*tf/tf_max

IDF = -log(df/N)

IDF_opt = SQRT(IDF/11.5), якщо IDF менше за 11.5, а інакше

IDF_opt = 11.5/IDF

Потім вибираються і зчіплюються в алфавітному порядку в рядок 6 слів з найбільшими значеннями wt. Як сигнатури документа обчислюється контрольна сума CRC32 отриманого рядка.

5 Результати проведених експерементів

Для проведення експериментальних досліджень алгоритмів A0-A10 було використано наступна колекція документів:

  • набір повних веб-сайтів РОМІП. Обсяг ~ 500000 документів;

Як еталон 100%-вої повноти для даної колекції використовувалося об'єднання дублікатів, знайдених всіма алгоритмами. У якості еталону 100%-вої точності використовувалися результати, отримані за допомогою функції Perl String:: Similarity з порогом схожості 80%.

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

У нижченаведених таблицях наведені результати обробки алгоритмами A1-A10 веб-колекції РОМІП.

Колекція веб-сайтів РОМІП

Обсяг колекції ~ 500 000 документів.

Кількість пар дублів, виявлених усіма алгоритмами — 17471200, тільки 68% з яких верифікувалися за результатами текстуального порівняння.

Ім'я Повнота Точність F-міра
А4 0.84 0.80 0.82
А1 0.60 0.94 0.73
А10 0.59 0.94 0.73
А3 0.59 0.95 0.73
А5 0.62 0.86 0.72
А2 0.54 0.96 0.69
А7 0.50 0.97 0.66
А9 0.44 0.77 0.56
А8 0.39 0.97 0.56
А6 0.36 0.91 0.51
А0 0.23 1.00 0.38

Таблиця2. Ефективність алгоритмів визначення нечітких дублікатів (результати порядний за спаданням F-заходи)

Ім'я Кількість дублів
А0 2791226
А1 7540460
А2 6745096
А3 7373208
А4 12635770
А5 8544468
А6 4696699
А7 6124207
А8 4791883
А9 6927589
А10 7531378

Таблиця3. Кількість пар дублів, знайдених окремим алгоритмом

А1 А2 А3 А4 А5 А6 А7 А9
А1 - 0.83 0.79 0.40 0.68 0.54 0.90 0.65
А2 - 0.75 0.38 0.76 0.60 0.88 0.71
А3 - 0.32 0.60 0.48 0.82 0.59
А4 - 0.76 0.54 0.54 0.55
А5 - 0.59 0.69 0.68
А6 - 0.56 0.53
А7 - 0.66
А9 -

Таблиця4. Матриця спільних кореляцій деяких алгоритмів (у сенсі Dice-коефіцієнта)

Dice-коефіцієнт для двух множин A і B вираховується за формулою:

Dice(A,B) = 2*A*B / (A+B)

6 Експериментальні алгоритми визначення нечітких дубікатов

Основне завдання, яке ставили перед собою автори при розробці нових алгоритмів виявлення нечітких дублікатів — існування (в 2-4 рази) збільшення показника «повноти» порівняно з існуючими алгоритмами, при збереженні максимально можливого показника «точності».

6.1 Метод «декомпозиції» (A11)

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

Робота алгоритму полягає в наступному:

  • Для кожного документу вираховуємо шингли, які не повторюються (можна не всі, а вибірково) і зберігаємо в файлі в форматі <shingle, doc_id, doc_len>.
  • Для однакових шинглів будуємо в ланюг у форматі <doc_id1, doc_len1> <doc_id2, doc_len2> ..., упорядковані по зростанню doc_len.
  • Розділяємо ланцюг на більш мілкі, якщо у сусідніх довжин відношення більшої довжини до меншої перевищує деякий поріг, який визначається мінімальним рівнем подібності для дублікатів (наприклад, для рівня подібності 0.85 можна практично без втрати повноти використовувати рогір 1.15).
  • Видаляємо дублі ланцюгів і ланцюги, які повністю входять в інші. У результаті число ланцюгів скорочується в сотні разів, а ланцюги, які залишилися у переважній більшості є достатньо короткими (2-10 елементів).
  • Документивсередині ланцюга порівнюємо попарно (наприклад, шляхом використання функції Perl Similarity або, ще простіше за допомогою якихось додаткових числових характеристик документу). До того ж порівняння іде не по всьому ланцюгу, а тільки в межах невеликої локальної області, яка визначається тим же порогом відношення довжин. Тому загальне число реальних порівнянь маленьке.
  • Для виключення діблів перевірок в різних ланцюжках, списки уже опрацьованих пар зберігаються в хеше.

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

Експериментальна перевірка

Алгоритм показав практично 100% повноту і точність на текстовій колекції при досить прийнятній родуктивності.

6.2 Метод “3+5” (А12)

Підбираючи параметри цього методу, ми експериментували з ознаками, які вимагають мінімальних обчислювальних ресурсів, у тому числі, ми не визначали контрольні суми всіх підрядків тексту. Крім того, ми намагалися спиратися тільки на «локальні» властивості текстів, тобто не використовували глобальні параметри колекції.

Робота алгоритму полягає в наступному.

  • Для кожного документа колекції формується не більше трьох записів наступного виду:<ss1,id,len,num,ss1,ss2,ss3,<ws1..5>><ss2,id,len,num,ss1,ss2,ss3,<ws1..5>><ss3,id,len,num,ss1,ss2,ss3,<ws1..5>> де<ss1,ss2,ss3> — сигнадути трьох самих довгих речень документу, впорядкованих за зменшенням довжини речення (по при рівності — по сигнатувам),<id> — індентифікатор документу,<len > — довжина документу (кількість слів довжиної 3 і більше літер),<num> — число речень в документі.

<ws1..5> = <ws1, ws2, ws3, ws4, ws5> — сигнатури п'яти самих довгих слів документу, впорядкованих за зменщенням довжини слів (а при рівності — за довжиною сигнатур).

  • Для коротких документів, які складаються з одного чи двух речень, створюється створюються одна або два записи виду:<ss1,id,len,num,ss1,0,0,<ws1..5>>, або<ss1,id,len,num,ss1,ss2,0,<ws1..5>><ss1,id,len,num,ss1,ss2,0,<ws1..5>> відповідно.
  • Отриманий файл сигнатур сортується і для записів у яких співпало перше поле формується ланцюжок виду (саме перше поле відсіюється):<id1,len1,num1,ss11,ss21,ss31,<ws11..51>> <id2,len2,num2,ss12,ss22,ss32,<ws12..52>> ..., впорядковані за зростанням поля <len> — довжини докунту (а при рівних довжинах по) <id>. При цьому відношення двох сусідніх елементів ланцюга не мають перевишювати деякого порогу, визначиним заданим мінімальним коефіцієнтом схожості документів (наприклад, для коефіцієнту 0.85, опимальне значення порогу рівне 1.15).

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

  • Файл ланцюжків сортується, і з нього виключаються дублі та ланцюжки, які цілком входять в інші, довші. У результаті такої нормалізації виходить файл ланцюжків невеликого розміру, в якому коефіцієнт надмірності (входження елементів у різні ланцюжки) становить не більше 10%.

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

  • Переглядаємо файл ланцюжнів і для кожного елемента ланцюжка знаходимо дублікати за наспуними правилами:

  • шукаємо тільки в межах локального околу;

  • порівнюємо пари, тільки якщо відноження числа речень в них не перевишює деякого порогу (1.20) і з пяти сигнатур слів <ws1..5> співпадає не менше двух, неважливо в якому пярдку;

  • два документи вважаємо дублікатами, якщо у них співпадають сигнатури самих довгих речень <ss1> або (для документів, які містять більше 5 речень, а таких більшість) з трьох сигнатур <ss1, ss2, ss3> співпадають дві, не важливо в якому порядку.

Ексерементальна перевірка

Імя Повнота Точність F-міра
А12 0.96 0.95 0.95

Таблиця 7 — характиристика алгоритму А12 на колекції РОМІП

Як видно, на колекції РОМІП алгоритм виявляє нечіткі дублікати з показником повноти близько 96%, що в 2-3 рази перевищує повноти всіх інших відомих алгоритмів.

Точність алгоритму складає близько 95%.

7. Висновки та обговорення результатів

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

  • всі методи, описані на частоту слів у середині документу, показали точність (TF*IDF, TF*RIDF, OptFreq, FT), однак не змогли наблизитися до істотно крашій по числу слів, які входять в лексичну сигнатуру документу LexRand. В цьому сімействі методів краші показники повноти у методів TF, OptFreq, TF*RIDF, які не включають рідкі слова в сигнатуру.
  • Метод LexRand хоч і є чемпіоном по точноті, має не найкрашу повноту, можливо через те, що вимагає точного співпадіння надто великої підмножини словника документів.
  • З синтакчисних (які використовують послідовність слів) методів Log_Shiligle стоїть осторонь від інших і наближається до MD5 — сама висока точність та сама маленька повнота. Метод Megashingle показав близький до заявленого результату (36% проти заявленого 0.42).
  • Дуже гарну повноту (крашу в прогоні) показав метод довгого речення LongSent. При цьому точність обох методів, основаних на виокремленні найкращого речення, передбачуванно сама низька.
  • Метод DescrWords показав низькі результати, можливо через технічні помилки.

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

З урашуванням више сказаного, авторами були запропановані нові алгоритми (А11, А12), які певною мірою реалізують цю схему і на текстових колекціях мають гарні результати.

Література

[1] A. Broder, S. Glassman, M. Manasse and G. Zweig. Syntactic clustering of the Web. Proc. of the 6th International World Wide Web Conference, April 1997.

[2] U. Manber. Finding Similar Files in a Large File System. Winter USENIX Technical Conference, 1994.

[3] N. Heintze. Scalable document fingerprinting. In Proc. of the 2nd USENIX Workshop on Electronic Commerce, Nov. 1996.

[4] Д. Гасфилд. Строки, деревья и последовательности в алгоритмах. Спб.: Невский диалект, 2003.

[5] A. Broder. On the resemblance and containment of documents. Compression and Complexity of Sequences (SEQUENCES'97), pages 21-29. IEEE Computer Society, 1998. ftp.digital.com/pub/Digital/SRC/publications/ broder/positano-final-wpnums.pdf

[6] A. Broder. Algorithms for duplicate documents. www.cs.princeton.edu/courses/archive/spr05/cos598E/bib/Princeton.pdf

[7] И. Сегалович, Д. Тейблюм, А. Дилевский. Принципы и технические методы работы с незапрашиваемой корреспонденцией. company.yandex.ru/articles/spamooborona.ht ml

[8] W. Pugh. Detecting duplicate and near — duplicate files. www.cs.umd.edu/~pugh/google/Duplicates.p df

[9] D. Fetterly, M. Manasse, M. Najork. A Large-Scale Study of the Evolution of Web Pages, WWW2003, May 20-24, 2003, Budapest, Hungary.

[10] A. Chowdhury, O. Frieder, D. Grossman, M. McCabe. Collection statistics for fast duplicate document detection. ACM Transactions on Information Systems (TOIS), Vol. 20, Issue 2 (April 2002). ir.iit.edu/~dagr/2002collectionstatisticsfor.pdf

[11] A. Chowdhury. Duplicate Data Detection. ir.iit.edu/~abdur/Research/Duplicate.html

[12] A. Kolcz, A. Chowdhury, J. Alspector. Improved Robustness of Signature-Based Near-Replica Detection via Lexicon Randomization. KDD 2004. ir.iit.edu/~abdur/publications/470-kolcz.pdf

[13] S. Ilyinsky, M. Kuzmin, A. Melkov, I. Segalovich. An efficient method to detect duplicates of Web documents with the use of inverted index. WWW Conference 2002. www2002.org/CDROM/poster/187/

[14] S. Robertson, S. Walker, S. Jones, M. Hancock- Beaulieu, M. Gatford. Okapi at trec-3. The Third Text REtrieval Conference (TREC-3), 1995.

[15] K. Church, W. Gale. Poisson mixtures. Natural Language Engineering, 1995, 1(2):163–190.

[16] A. Broder, M. Charikar et al. Min-wise independent permutations, Proceedings of the thirtieth annual ACM symposium on Theory of computing, 1998.

[17] Яндекс. www.yandex.ru

[18] S.-T. Park, D. Pennock, C. Lee Giles, R. Krovetz, Analysis of Lexical Signatures for Finding Lost or Related Documents, SIGIR’02, August 11-15, 2002, Tampere, Finland

[19] Berson, Thomas A. (1992). «Differential Cryptanalysis Mod 232 with Applications to MD5». EUROCRYPT

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

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

Коментарі 2

lemon - 26 жовтня 2010, 12:09

цікава стаття

на проекті використовували шінгли для пошуку дублікатів в дуже великій базі (~10m records) — допомагало :)

ви часом також не займаєтесь NLP?

odevyatkov - 26 жовтня 2010, 12:36

дякую.

нажаль не займаюся, я для себе цікавився цією темою (хотів реалізувати одну ідею...)

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