Ефективність методів семантичної мережі для виявлення плагіату речень

Вступ

1. Дослідження стану питання дослідження плагіату

1.1 Основні поняття

1.2 Плагіат документів

1.3 Методи виявлення плагіату

1.3.1 Виявлення на основі стилометричного аналізу

1.3.2 Виявлення плагіату на основі порівняння документів

1.3.2.1 Семантичне виявлення

1.3.2.2 Синтаксичне виявлення

1.4 Існуючі веб-засоби виявлення плагіату

1.5 Семантичні мережі

1.6 Попередня обробка документу

1.6.1 Токенізація

1.6.2 Видалення стоп-слів

1.6.3 Виділення коренів слів

1.7 Представлення документів та міри схожості

1.7.1 Семантичне представлення

1.7.2 Синтаксичне представлення

1.7.2.1 Зняття відбитків пальців

1.7.2.2 Схема ваговимірювання термінів

1.7.2.3 N-грами

1.8 Алгоритм апроксимованої подібності

1.8.1 Алгоритми схеми підпису

1.8.2 Алгоритми на основі інвертованого індексу

1.9 Підведення підсумків

2. Методологія

2.1 Підготовка документа

2.2 Попередня обробка

2.3 Семантичний підхід порівняння

2.4 Підхід N-грам

2.5 Оцінка результатів

3. Побудова експериментальної моделі

3.1 Вступ

3.2 Порівняння речення до речення

3.2.1 Підхід N-грам

3.2.2 Семантичний підхід подібності

3.3 Результати аналізу Висновки

Вступ

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

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

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

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

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

Є два методи, щоб забезпечити доступ до великої кількості веб-документів. Перший метод індексування документів через веб-сканування, це має вроджені проблеми веб-документів, з якими стикаються будь-яка веб-пошукова система. Наприклад обсяг розміру, неоднорідність і дублювання [2], проте система може бути налаштована для пошукових цілей, наприклад, якщо метою є виявлення плагіату, система може бути використана для повернення найбільш синтаксично або семантично аналогічних документів на запит по документу. Інший метод є використовування джерел пошукових систем (таких як Google, Yahoo і Bing), оскільки вони надають доступ до своїх систем. Підозрюваний документ можна вважати як послідовність запитів до пошукової системи, а представлений результат потім порівнюється з вхідним документом.

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

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

Кожна міра повертає значення, що вказує ступінь подібності між парами об'єктів зазвичай між 0 і 1. Крім міри схожості, інший аспект документа (або речення) подання. Є багато представлень, які були розроблені в тому числі відбитки пальців документа [17], N-грами (послідовних слів довжини N).

Інше важливе представлення походить від семантичних мереж. Семантична мережа «є графічне позначення для представлення знання в структурі взаємопов'язаних вузлів і дуг» [50]. Поняття у семантичних мережах, як правило, організовані в ієрархічну структуру, як показано на малюнку 1.1

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

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

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

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

Для вирішення проблеми, описаних вище потрібне вирішення наступних задач

1. Яке N-грам представлення найкраще для винесення оцінки плагіату на основі представлення?

2. Які міри подібності є кращим для винесення оцінки плагіату?

3.Як семантична мережа може бути використана для покращення виявлення виявлення плагіату?

Основними цілями цієї роботи є:

1. Порівняння ефективності різних N-грам з різними мірами подібності для виявлення плагіату документів.

2. З’ясувати, чи може використання семантичних мереж поліпшити виявлення плагіат документів.

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

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

1. Дослідження стану питання дослідження плагіату

плагіат апроксимований семантичний токенізація

1.1 Основні поняття

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

Деякі терміни, буде часто використовуватися в іншій частині цієї доповіді і певні тут;

Документ: це тіло тексту, з якого можна буде вилучити структурну інформацію.

Збірник: це збір таких документів.

Токен: це будь-який рядок, буквено-цифровий текст, взятий з якого-небудь документу, наприклад, символів, слів, або речення.

Фрагмент: будь-який порядок токенів.

1.2 Плагіат документів

На відміну від інших типів у плагіаті (таких як музика, графіки і т.д.), плагіат документів поділяється на дві категорії: плагіат программного коду та плагіат вільного тексту.

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

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

· Copy-Paste: або дослівно (слово в слово). Плагіат, в якому текстовий вміст копіюється з одного або декількох джерел. Скопіюваний вміст можно бути дещо змінений.

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

· Відсутність належного використання лапок: нездатність визначити точно частини запозиченого змісту.

· Дезінформація посилань: додавання посилання на неправильні або не існуючих джерела.

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

1.3 Методи виявлення плагіату

Наступні методи виявлення плагіату Маурера і ін. в загальних рисах можна розділити на три основні категорії: перша категорія намагається виявити стиль автора тексту і знайти несумісні зміни у цьому стилі. Це відомо як стилометричний аналіз.

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

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

Малюнок 1.1 ілюструє систематику методів виявлення плагіату.

Малюнок 1.2 Систематика методів виявлення плагіату

1.3.1 Виявлення на основі стилометричного аналізу

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

Методи виявлення, які застосовуються до одного чи декількох документів, що належать того ж автора і без зовнішніх джерел, належать до так званих притаманних методів виявлення плагіату [3, 13]. Найбільш відомі методи є стилометричні.

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

Плагіат можуть бути визначений, наприклад, коли автор поперемінно використовує займенник «ми / наша». У залежності від розміру блоку і типу, велика частина стилометричних особливостей припадає на одну з наступних п’яти категорій [13]:

· статистики тексту: опрацювання на рівень символів;

· синтаксичні особливості: оцінка стилю письма на рівні речення;

· особливості частини мови: кількісне використання класів слів;

· використання однорідних слів: особливості слова;

· структурні особливості: які відображають організацію тексту.

1.3.2 Виявлення плагіату на основі порівняння документів

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

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

1.3.2.1 Семантичне виявлення

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

За допомогою тезауруса WordNet для вилучення синонімів проблема заміщення слів може бути вирішена, проте через те що значення слів неоднозначні, вибір правильного терміну часто нетривіальний. Для більш складних моделей плагіату, такі як зміни структури речення, потребує більш глибокого аналізу [36,37].

Каном і ін. була введена система PPChecker [36], який обчислює кількість даних, скопійованих з оригіналу документа на запит документів, на основі мовних моделей плагіата.

Так як вони використовували речення як порівняльна одиниця між документами, вони визначили п’ять моделей:

· точне копіювання речення

· вставка слова

· видалення слова

· заміщення слів між реченнями

· зміна структури речення

Ці шаблони визначені на основі трьох умов рішення:

· перекриття слів

· різниця слів

· розмір перекриття Для кожної моделі, вони визначили різні міри схожості і досягли вражаючих результатів для деяких синтаксичних систем. Тачефебібон та ін. запропонували новітній метод мовного аналізу для виявлення плагіату, використовуючи синтактико-семантичний аналіз. Синтаксичний аналіз проводився за допомогою аналізатора для визначення правил граматики у текстах і визначення структури текстів. Тоді, структури текстів порівнюються за правилами граматики. Їх система, а також PPChecker використовували WordNet для вилучення синонімів.

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

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

1.3.2.2 Синтаксичне виявлення

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

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

ABCDE AFCDE ABFCD ABCFD ABCDF

Підкреслені слова показують, що всі п’ять фрагментів місять чотири слова, що робить їх кандидатами на плагіат. Розглянемо тепер наступні функцію подібності:

Де x і y два набори слів і | x |є кількість слів у x.

Кожна пара документів в управлінні приклад j (x, y)=4 / 6, що вказує на x і y мають спільними чотири слова з п’яти. Попередня функція подібності - це схожість Джаккард. Такі методи для вимірювання подібностей між документами були отримані з інформаційного пошуку. Ці методи не дають «так» або «ні» відповідь на питання про те, чи документи мають відношення до запиту користувача, але впорядковує їх за оцінками ймовірної актуальності.

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

Шивакунар і ін ввів систему SCAM і відомої моделі відносної частоти, яка є модифікацією функції косинус. SCAM продемонструвала кращі результати, ніж запропонована систем відповідності речень COPS у багатьох випадках виявлення плагіату [19], однак вона зробила більше помилкових спрацьовувань (документи, які помітили, як плагіат, хоча вони такими не є), в деяких випадках SCAM повідомила про два різні документи як 100% рівні.

Також, оскільки SCAM вимірює глобальну подібність, вона не може ввести позиційну інформацію про вміст скопійованого.

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

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

1.4 Існуючі веб-засоби виявлення плагіату

У цьому розділі розглядаються деякі існуючі інструменти виявлення плагіату та висвітлюються деякі недоліки цих інструмекнтів на основі порівняльного дослідження по вибраним 10 документам з цифрової бібліотеки ACM і вручну зробили плагіат заміною синонімів.

Більшість веб-інструментів виявлення плагіату використовують API для пошуку. Прикладом такого інструменту є DocCop [48], який є одним з найпростіших і основних інструментів. Інструмент розбиває на фрагменти документ в N-грам (послідовних слів довжини N), а потім використовує грамів як запити. Потім він вимірює ступінь плагіаті відсоток запитів на непустому відповідь від пошукових систем, розділене на число всіх запитів.

Коли DocCop було перевірено 10 документів на плагіат, він не зміг отримати жодний документ.

Інший вільно доступний інструмент, який заснований на API пошукової системи є Plagium. Не ясно, яким чином Plagium використовується, проте він працює краще, ніж DocCop у виявленні плагіату документів і зміг отримати 2 з 10 документів. Інструмент повертає графічний малюнок, де показані вихідні документи і на скільки вони обмінюються інформацією із вхідним документом.

Деякі з веб-інструментів не залежать від пошукових систем API.

EVE2 є прикладом такого інструменту. EVE2 є комерційним інструментом, який дозволяє користувачу налаштування пошуку. EVE2 стверджує, що він виконує великий пошук і досягає будь-якого веб-документу. Під час тестування EVE2 з плагіатом 10 документів він завжди видавав повідомлення про те, що він не знайшов прикладів плагіату.

Було також випробування з повної копії документа з цифрових бібліотек, включаючи ACM та IEEE, а також з інших сайтів, включаючи Wikipedia, але EVE2 зазнав невдачу в отриманні первинних документів у всіх тестах.

Turnitin інший комерційний інструмент і, можливо, найвідоміший і найуспішніший. Turnitin використовує свій власний веб-індекс у пошуку плагіату документів. Вона не була перевірена в цій роботі.

Таблиця 1.1 показує, властивості деяких існуючих інструментів, заснованих на.

Таблиця 1.1 Властивості деяких існуючих інструментів виявлення плагіату на основі.

1.5 Семантичні мережі

Семантична мережу «є графічне позначення для представлення знань у структурі взаємопов'язаних вузлів і дуг «[50]. Найбільш впливовим прикладом таких мереж в обчислювальній лінгвістиці є WordNet. WordNet є лексичною базою даних для англійської мови, який організовує слова в множини синонімів (синсети), кожен з яких представляє різні концепції. Синсет містить синонім слова або словосполучень слів і надає коротке текстове представлення синсету. Приклад синсету показано на малюнку 1.2

Малюнок 1.3 Приклад синсету в WordNet

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

Таблиця 1.2 Деякі з відносин між поняттями в WordNet (N = іменник, V = дієслово, Adj = прикметник, Adv = прислівник)

WordNet розрізняє іменники, дієслова, прикметники та прислівники так вони мають різні граматичні правила. Таблиця 1.3 показує кількість слів кожної частини мови в WordNet 1.1.

Таблиця 1.3 Статистика по WordNet

Іменники та дієслова організовані в ієрархії на основі hypernym / hyponym зв’язок між синсетами. Прикметники і прислівники, однак, не дотримуються цього типу організації. Прикметники розташовані в кластери, які містять вершину синсету і супутникових синсетів. Кожен кластер будується навколо антонімічних пар (а іноді й антонімічної трійні). Більшість вершин синсетів матє один або декілька супутникових синсетів, кожен з яких представляє поняття, аналогічне за змістом концепції представленої вершини синсету. Малюнок 1.3 показує приклад біполярноїструктури прикметника.

Малюнок 1.4 Біполярна структура прикметника

Pertainyms є реляційними прикметниками і не слідують структурі, описаній вище. Pertainyms не мають антонімів; синсет для pertainym найчастіше містить тільки одне слово чи словосполучення і лексичний вказівник на іменник, до якого прикметник «стосується» .

Дієприслівникові прикметники мають лексичні покажчики на дієслова від яких вони є похідними.

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

1.6 Попередня обробка документу

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

1.6.1 Токенізація

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

1.6.2 Видалення стоп-слів

Стоп-слова, таки як «the», «of», «and» і т. д., вказують на структуру речення і відношення між представленими поняттями, але не мають ніякого сенсу і можуть бути безпечно видалені без здійснення впиливу на точність вимірювання аналогічності двох документів [16,32,33].

1.6.3 Виділення коренів слів

Багато слів в англійській мові мають кілька варіантів форм, і відрізняються суфіксом. Суфікси для кожного варіанту форми можуть бути видалені виділенням кореня слова. Виділенням кореня не є суттєвим кроком у виявленні копії, але може прискорити процес, так як кілька слів зводяться до одного терміну [16,33,34].

Процедура розбиття конкретного документа на більш дрібні одиниці (фрагменти) є процедурою фрагментування. Процедура розбиття тексту є важливим питанням у будь-якій системі виявлення плагіату, так як ця процедура буде впливати на точність системи, а також на її продуктивність [19,29].

Існують різні способи, як документ може бути фрагментований.

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

Блокове фрагментування: документ фрагментований на більш дрібні одиниці (фрагменти). Блок може бути символ, слово, речення або строка. У фрагметуванні речень документ розбитий на речення, а потім речення порівнюються між різними документами (Наприклад, COPS?? прототип [20]). Основна проблема тут у тому, як виявити межі речення. Один підхід полягає в прийняти всіх слів до крапки або знаку питання. Однак речення, які містять скорочення, такі як «наприклад» буде розбите на кілька речень зі знаками припинання у вигляді крапки і система може потерпіти невдачу, якщо нема припинаючих символів в даному документі. У фрагментуванні речень не страждає від цих обмежень, оскільки межі слів можуть бути визначені через символ «пробілу». Однак недоліком є більша кількість помилкових спрацьовувань, оскільки два документа містять деяки спільні слова не означає, що плагіат присутній.

Фрагментування на n-блоків, що не перекриваються: у цьому випадку документ розбитий на N послідовних фрагментів (наприклад, символів, слів і т.д.) з використанням ковзаючого вікна з нульовим перекриттям між фрагментами як видно на формі Малюнок 1.4.

Малюнок 1.4 Фрагментування на n-блоків, що не перекриваються

Цей метод має ту перевагу, мінімізації кандидатів, які повинні бути порівнянні зі значенням K, що може змінюватися в залежності від бажаного рівня порівняння. Однак вставка одного блоку викличе переміщення на ковзаючому вікні на один елемент, що впливає негативно на точність виявлення. При N = 1 цей метод зводиться до фрагменту всього документу.

N-блокове фрагментування з К-перекриттям: тут документ розбивається на К-блоків фрагменти, як і раніше, але фрагменти перекриваються на К, де 0 <�К

На малюнку 1.5 показаний цей метод з N = 5 і К = 2.

Малюнок 1.5 N-блокове фрагментування з К-перекриттям

N-грам фрагментування:

N-грам послідовності слідуючих один за одним блоків довжини N символьних або на основаних на словах. Це окремий випадок N-блокового фрагментування з К перекриття, коли K = N-1. Хоча N-грам фрагментування зазвичай використовується при введенні виявлення помилок і в базах даних системної інтеграції [39], на основі слів N-грам фрагментування є кращим у більшості систем виявлення плагіату через здатність охопленні зхожих фраз в N-грамах, так як важко змінити кілька слів для фрагментів малої довжини [31,32].

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

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

Наприклад 4-грама для «ABCABCAB» є:

{(A, B, C, A), (B, C, A, B); (C, A, B, C), (A, B, C, A), (B, C, A, B)}

і шингли: {(A, B, C, A), (B, C, A, B); (C, A, B, C)}

Фрагментування з запоминаючими зупинками: хоча останні дві стратегії спрощують проблему переміщення блоків, вони не є ефективними з точки зору обчислення і затрату часу. Булла введена інша стратегія [20], що скорочує набір кандидатів і приймає з урахуванням переміщення блоків, він працює в такий спосіб: хешується перший блок в документі, якщо хеш-значення за модулем К дорівнює нулю (для деякого обраного K), то даний блок є першим фрагментом в документі, якщо не вважати наступний блок, якщо його хеш-значення по модулю K дорівнює нулю, то перші два блоки є першим фрагментом, якщо ні, то повторити процес, поки умова не виконується, і це є зупинка. Тоді послідовність одиниць з попереднього блоку до даної зупинки, є фрагментом.

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

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

Лю і ін. використовували фрагментування речень для запитів в пошуковій системі для застосування в виявленні плагіата; фрагментування ж було використано для порівняння.

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

Шивакумар та Гарсіа-Моліна дають ретельне дослідження в порівнянні різних типів фрагметування примітивів і виклав щодо цього переваги цих примітивів з точки зору точності і продуктивності над 50.000 документів, в яких вони приходять до висновку, що основним фактором впливу на точність є середня довжина фрагмента. Коли довжина збільшується стає важко виявити часткове перекриття, так як перекривання послідовностей між двома документами може початися де завгодно в рамках блоку. З іншого боку, коли ця довжина зменшується, втрати в фрагментуючих послідовностях може призвести до помилкових результатів (пара документів, які визначені таким, що не мають перекриття, хоча вони є).

1.7 Представлення документів та міри схожості

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

Другий підхід використовує синтаксичну інформацію документа. Два підходи більш детально в наступних двох розділах.

1.7.1 Семантичне представлення

Автори роботи зробили великі дослідження за методами, які використовувалися в WordNet для виявлення подібностей між поняттями. Вони відрізняються між трьома поняттями: семантичного споріднення, семантична відстань, і схожість. У їх дослідженні вони стверджували, що подібність «окремий випадок семантичної спорідненості «.

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

Під час дослідженні виявили, в WordNet використовуються такі визначення і позначення [51]:

· довжина найкоротшого шляху в WordNet від синсету Ci до синсету Cj (вимірюється в ребрах або вузлах) позначається len(Ci, Cj).

· Глибина вузла — довжина шляху до вузла від глобальної вершини, тобто, depth(Ci) = len(вершина, Ci).

· Найнижча супер-ордината С1 і С2 позначається lso(C1, C2).

· Для будь-якої формули rel (C1, C2) для семантичного спорідненості між двома концепціями C1 і C2, спорідненості rel (w1, w2) між двома словами і може бути розрахована. Де s (wi) є набір понять в таксономії, які означають слова. Тобто, спорідненість двох слів те саме, що найбільш пов’язані пари понять, які вони позначають.

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

де С і k-постійні

(c1,c2) це число, яке показує скільки раз шлях між c1 і c2 змінює свій напрямок.

Другий підхід грунтується на спостереженні," що однорідні-концепції які в глибині щодо всього представлення, більш тісно пов’язані один з одним, ніж ті що лежать вище вгору. Кожен зв’язок має вагу або діапазон [minr, maxr] ваг пов’язані з ним. Вага кожного ребра типу R від деяких вузлів c1 зменшується на фактор, який залежить від числа ребер, того ж типу, залишивши С1″. Ця вага визначається за наступною формулою:

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

де r-зв'язок, що має місце між c1 і c2 та r' є його інверсією (тобто, відношення, що має місце між c2 і c1).

Нарешті, семантична відстань між двома довільнмим вузлами ci і cj є сумою відстаней між парами сусідніх вузлів по найкоротшому шляху між ними.

Третій підхід визначає концептуальні подібності між парою концепції c1 і c2 в ієрархії за такою формулою:

Четвертий підхід масштабує семантичні схожості між поняттями c1 і c2 у WordNet за такою формулою:

П’ятий підхід є підхід Резника [56], у якій він називає його інформаційним змістом заснованим на припущенні, що одним з критеріїв подібності між двома концепціями є об'єм спільної інформаціїї, якою вони обмінюються. Інформаційний зміст Резника визначається за наступною формулою:

де p© є ймовірність зустріти аналог концепції c.

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

Малюнок 1.6 Специфика сабсьюмерів у WordNet

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

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

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

Для будь-яких двох слів в даних двух реченнях обчислюються подібність, а на вихід подається максимальна подібність з вирахуваних. Ця максимальна подібність є елементом семантичного вектору, який формується з об'єднаної множини слів у парах речень. Елемент семантичного вектору si вираховується за наступними рівнянням:

де я I(wi) і I(w’i) є інформаційним наповненням (змістом) (підхід Рєзника) слова wi у об'єднаній множині і пов’язаний з нею w'i слів у реченні, відповідно, I визначається за наступною формулою:

де n-число появи слова w в корпусі Брауна [58],

N є загальна кількість слів у корпусі (корпус містить більше ніж мільйон слів).

Загальна семантична подібність Ss між двома реченнями вимірюється косинус коефіцієнтами між їх семантичних векторами:

де s1 і s2 є семантичні вектори двох пропозицій.

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

де r1 і r2 є порядкові вектори двох речень.

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

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

де вирішує внесок як семантичної (Ss) так і синтаксичної (Sr) подібності.

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

1.7.2 Синтаксичне представлення

У цьому розділі представлені три типи подання документа на основі синтаксичної інформації. Це представлення відбитків пальців, зважування термів, і N-грами.

1.7.2.1 Зняття відбитків пальців

Зняття відбитків пальців є процес створення компактних характеристик (відбитки пальців) з кожного документа в колекції [14,15,16,17]. Два документи визначені таким, що мають значне перекриття, якщо вони мають принаймні певну кількість відбитків пальців [15,16,18].

При розробці будь-якої системи при знятті відбитків пальців для вимірювання подібностей документів є чотири проблеми, які необхідно враховувати [16];

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

Деталізація: розмір входу в функція генерації відомий як деталізація відбитків пальців. Ця деталізація повинна бути обрана ретельно в залежності від того, як два документи повинні бути визначені як аналогічні або перекриваються [17,19,20]. Наприклад, якщо мета полягає у виявленні дублювання документів крупнодеталізований вибір може бути використаний в даному випадку, проте для виявлення документів, які перекриваються в реченнях або абзацах, така деталізація, як реченева деталізація, або К-слова деталізація для малих К повинен бути використано.

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

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

Вибір під строки: це стратегія для вибору підстроки, що буде розглядатися. Це стратегія залежить від розміру відбитків пальців. Якщо фіксований ромір, наприклад N, який береться для опрацювання, то N підстрока повинна бути вибрана.

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

Процес опрацювання документа методом відбитків пальців, а потім порівнюючи його з відбитками пальців інших документів виглядає наступним чином [44]:

1. Розділення кожного документа на суміжні фрагменти (деталізація відбитків пальців)

2. Береться відносно невелике число фрагментів (розмір відбитків пальців, вибір підстроки)

3. Перетворення кожного збережоного фрагмента у короткий байтову строку, кожна така строка називається відбитком пальців (покоління відбитків пальців)

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

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

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

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

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

1.7.2.2 Схема ваговимірювання термінів

З інформаційного пошуку (ІП) будь-який документ може бути представлений у вигляді вектора (S). Зміст вектор відрізняється від системи до системи. Найбільш відомим представленням є схема ваговимірювання термінів у векторній просторовій моделі. Варіації цієї схеми були також запропоновані для конкретних програм. Наприклад, в зроблено п’ять варіантів для виявлення плагіату документів. Перший варіант дозволяє використовувати різниці в частотах термінів між двома документами і визначається за наступним рівнянням:

де f_d позначає число строк у документі d

f_{d, t}, є частота строк t в документі d.

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

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

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

Четвертий варіант дуже схожий на варіацію двох і використовується для зменшення впливу зміни ваги терміну і дає наступне рівняння:

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

1.7.2.3 N-грами

Попередні представлення використовують вагу терміну в обчислювальні подібності між документами. Іншим представленнямє N-грами. Значення N може бути різноманітним. Проте відносно речення, це значення має бути низьким. У своєму недавньому дослідженні про виявлення плагіату речень, Баррон, а ін виявили, що кращі значення 2 і 3 (біграми і триграми, відповідно). У цьому представленні функція подібність використовується для визначення ступеня подібності між реченнями.

Лейн і ін. представив детектор текст-плагіату Ferret [21,22,23], де кожен документ представляється у вигляді триграм. Аналогічно, Бао та ін. використовуючи підхід Ferret при дослідженні текстового плагіату в академічних працях конференції і китайський документах. Загальні міри схожості показані в таблиці 1.5, відповідні бінарні версії представлені в таблиці 1.4.

Таблиця 1.4 Загальні міри схожості між бінарними векторами

Таблиця 1.5 Загальні міри схожості між множинами

1.8 Алгоритм апроксимованої подібності

Вродженою проблемою в обчислювальні більшості мір подібностей є довгий час для оцінки подібності між фрагментами.

Ця проблема відома з області баз даних, де вона відомий як проблема об'єднаної подібності [5, 6, 7, 8, 9, 49], в якій метою є знайти всі подібні пари записів у великих базах даних. Наївним підходом є порівняти кожну пару записів по одному від кожного відношення, що дуже неефективним, якщо розмір відносин дуже великий.

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

1.8.1 Алгоритми схеми підпису

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

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

Алгоритм працює в такий спосіб: Розглянемо дві колекції записів Малюнок 1.7 Алгоритм підпису

X = {x1, x2} і Y = {y1, y2, y3}, як на Малюнок 1.8, нехай функцію подібністю буде подібність перекриття (табл. 1.4), і поріг подібності бути 80%, так як всі записи мають той же розмір S = 5, подібність перекриття може бути записана як: sim (x, y)=|x? y|/5

Малюнок 1.8 Два документи представлені у вигляді записів Для будь-яких двох записів x, y, що x € X і y € Y, що задовольняють Overlap (x, y)>80%, перетинання між x і y повинно бути більше 3. Таким чином, замість вимірювання подібностей між кожною парою записів, записи можуть бути відсортовані і тільки перші дві позиції (префіксної довжини) повинні розглядатися як це видно на Малюнку 1.9.

Малюнок 1.9 Схема префікс-фільтрації

Як показано на малюнку 1.9, x2 не має співпадінь і не буде розглядатися, і x1 має два кандидати пар: y1 і y2. Однак, оцінюючи їх мірою подібності, y2 не задовольняє умови, а, отже, ігноруються в пост-фільтрації етап.

Такі ж заключення можна зробити і оцінивши інші міри подібності [49], такі як показані в таблиці 1.4.

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

PartEnum заснована на принципі голубиного гнізда і був введений для програм по очищенню данних та використовує відстань Хеммінга як міру подібності. Відстань Хеммінга між двома множинами — це розмір симетричної різниця між множинами. Для ілюстрації розглянемо наступні дві множини;

X = {A, B, C, D, E}, Y = {A, B, C, D, F}

Відстань Хеммінга Hd між х і у:

Hd (x, y)=|(x-y)(y-x)|=2

Таким же чином, відстань Хеммінга між двома векторами це число вимірів, в яких два вектори розрізняються. Прикладом є два бінарні вектори показані на Малюнку 1.10, що мають відстань Хеммінга = 4 (показані червоними крапками), оскільки є 4 виміри, в яких два вектори розрізняються.

Малюнок 1.10 Вектори що мають відстань Хемінга рівною 4

PartEnum заснований на двох ідеях підпису: розбиття і перерахування. Розбиття: розглядяється розбиття області {1, …, п} на K +1 рівноважного розміру розділів, де К поріг Хеммінга.