Современные информационные технологии/3.Программное обеспечение

Гранік М. О., к.т.н. Месюра В. І.

Вінницький національний технічний університет, Україна

Аналіз методів визначення схожості новинних текстів

Вступ

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

Аналіз існуючих методів визначення схожості новинних текстів

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

Одним із таких шляхів є визначення косинусного коефіцієнта [1]. Для визначення цього коефіцієнта по кожному із текстів будується відповідний вектор, що містить інформацію про входження слів у кожен із цих текстів (наприклад, кількість цих входжень). Існує можливість порахувати скалярний добуток цих векторів двома способами (шляхом обрахунку суми добутку відповідних координат векторів, а також добутку довжин векторів на косинус кута між ними), і відповідним чином знайти косинус кута між ними. Так як описані вище вектори містять лише невід’ємні елементи, значення косинусу знаходиться у межах [0; 1]. Чим ближчим є отримане значення до 0, тим більш схожими є вектори і відповідні ним тексти.

Ще один шлях визначення схожості текстів – обрахування коефіцієнту Жаккара [2]. У відповідність кожному із текстів ставиться множина слів даного тексту. Коефіцієнт Жаккара визначається як частка від ділення потужності множини перетину двох отриманих множин на потужність множини об’єднання даних множин. Чим ближчим до одиниці є значення коефіцієнту Жаккара, тим більш схожими вважаються тексти.

Доволі схожим чином обраховується коефіцієнт Соренсена [2]. Аналогічно до методу Жакара, у відповідність кожному із текстів ставиться множина слів даного тексту. Значення коефіцієнту Соренсена рівне частці від ділення перетину двох отриманих множин на потужність мультимножини, що складається з двох даних множин (таким чином, при об’єднанні множин слів текстів кожне слово входить у мультимножину стільки раз, скільки воно зустрілось в обох множинах).

Також для обрахунку схожості двох текстів можуть бути застосовані коефіцієнт Сімпсона, коефіцієнт Браун-Бланке, коефіцієнт Кульчинського [2].

Статистична міра tf-idf, на відміну від описаних вище методів, працює із набором (далі – корпусом) текстів [3]. Для того, щоб визначити, наскільки схожим є один із текстів на решту текстів із корпусу, для кожної пари «слово поточного тексту – текст, із яким відбувається порівняння» рахується частота входження слова у даний текст (term frequency, далі – tf). Також для кожного слова поточного тексту обраховується так звана зворотна частота документу (inverse document frequency, далі – idf). Формули для обрахунку цих двох величин виглядають наступним чином:

(1)

(2)

де – поточне слово, – поточний документ, – кількість входжень поточного слова у поточний документ, – корпус документів.

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

На основі обрахованих значень можна провести кластеризацію текстів і таким чином визначити тексти, що відповідають спільній тематиці.

Висновки

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

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

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

Література:

1. Modern Information Retrieval: A Brief Overview / Singhal Amit //  Bulletin of the IEEE Computer Society Technical Committee on Data Engineering 24 (4) / P. 35 – 43

2. Матеріали курсу Data Mining, що викладався у University of Utah [Електронний ресурс] / Режим доступу до матеріалів: http://www.cs.utah.edu/~jeffp/teaching/cs5955/L4-Jaccard+Shingle.pdf

3.  A statistical interpretation of term specificity and its application in retrieval / Karen Spärck Jones // Journal of Documentation, V 60 / P. 493-502.