Тарануха В. Ю. Інтелектуальна обробка текстів



Pdf просмотр
Сторінка2/6
Дата конвертації05.01.2017
Розмір0.71 Mb.
1   2   3   4   5   6
Алгоритм TextTilling
Задати розмір n вікна в словах - w
1
....w
n
Пересуваючи вікно по тексту, створити з с(w
i
)
j
вектори, що відповідають двом сусіднім вікнам;
Порахувати відстані між кожними двома сусідніми вікнами w
i
....w
n+i
; w
n+i+1
....w
i+2n
;
Якщо cos Θ > Th - розрив.
Встановити маркер «Розрив»
Оцінка складності роботи алгоритму:
О
(N*w
2
), де N – довжина тексту в словах, w – довжина вікна у словах.
1.3.5 ВИКОРИСТАННЯ РЕЗУЛЬТАТІВ ІНДЕКСАЦІЇ
Результати індексації, а саме побудовані лексичні ланцюжки, необхідні для двох задач:
- побудови оцінки важливості тих чи інших елементів у рефераті;
- побудови оцінки близькості фрагментів тексту з метою вилучення дублів.
Ані частотний підхід, ані зважування окремих елементів семантичного представлення (концептів) не працює коректно, якщо в тексті(текстах), що реферуються, спостерігається велика кількість повторів або запозичень.
Також треба враховувати, що задача оцінювання імовірних запозичень має високу обчислювальну складність, якщо її виконувати на всьому наборі вхідних текстів. Можливість розбиття тексту на фрагменти та вилучення очевидних дублів значно прискорює роботу системи реферування.
1.4. ВИЗНАЧЕННЯ МОЖЛИВИХ ЗАПОЗИЧЕНЬ У ТЕКСТАХ
При визначенні запозичень потрібно враховувати, за яких обставин відбулось запозичення. Якщо людина вдається до плагіату, швидше за все, вона внесе до тексту зміни, для того щоб приховати факт неправомірних

17 запозичень. При цьому потрібно добитися мінімізації випадків помилкового спрацьовування. Якщо газета передруковує новину, то нормальним є зазначення посилання на джерело, при, можливо, новій інтерпретації та переписуванні тексту.
У досліджуваному тексті для підозрілого фрагмента можливі такі спотворення:
- Межі підозрілого фрагмента не обов'язково збігаються з межами абзацу або пропозиції;
- У підозрілий фрагмент могли бути внесені зміни, як шляхом вставки, так і шляхом викидання елементів;
- У підозрілому фрагменті можуть бути переставлені елементи;
- У підозрілому фрагменті можливі синтаксичні зміни, виражені у зміні граматичних форм слів;
- У підозрілому фрагменті можливі стилістичні зміни, виражені в заміні слів на синоніми;
- Межі пропозицій в підозрілому фрагменті можуть не збігатися з вихідними.
У загальному випадку текст є особливою формою представлення знань про зовнішню тексту дійсність. Текст повинен мати властивості: членимості, смислової цілісності та зв'язності. При цьому треба пам'ятати, що різні спостерігачі (читачі), в одному і тому ж наборі символів побачать різний текст.
Членимість тексту має на увазі, що текст ділиться на абзаци, службові угруповання однорідних одиниць викладу за сюжетом або темою.
Послідовність абзаців формує порядок виведення однієї одиниці з іншої або
інших. Це в свою чергу формує ті висновки, які хотів донести до читача автор. Абзац у свою чергу ділиться на пропозиції - сукупності декількох пов'язаних слів, що виражають певний сенс. Пропозиції складаються зі слів і словосполучень, які відображають смисли і відносини між ними.
Смислова цілісність виникає, якщо читач може узагальнити текст і дати йому назву.

18
Зв'язність тексту визначається наявністю у ньому зв'язок, забезпечених смисловими або синтаксичними засобами. До смислових відноситься згадка раніше описаного, не обов'язково у вигляді повторення слова. Це може бути згадка аспекту або якості. Таке згадка породжує відношення «нове-старе» між елементами пропозиції. Синтаксичні засоби складаються у застосуванні слів або навіть синтаксичних конструкцій, які не мають власного сенсу, але вказують на раніше згадану сутність. Будемо називати їх мовними вказівниками.
1.4.1 МОДЕЛЬ СТРУКТУРИ ТЕКСТУ
Текст можна вважати послідовністю тематичних або сюжетних елементів, при цьому кожний наступний набирає відношення слідування до всіх попередніх. Не обмежуючи загальності, вважаємо, що слова в тексті приведено до нормальних форм, - це значно спрощує роботу.
T
k
= T
k
(A(T), R(T)), де T
k
– окремий текст,
A(T) - множина абзаців,
R(T)– відношення слідування, визначене на абзацах, і залежить від того, як і яку думку хотів донести до читача автор.
Абзац розбивається на сукупність речень, кожне з яких вводить, уточнює або зв’язує певні сенси.
a = a
i
(S(a
i
), R(a
i
)) де a
i
– i-й абзац,
S(a
i
) – множина речень в абзаці,
R(a
i
) – відношення слідування визначене на реченнях, і залежить від того, як і яку думку хотів донести до читача автор. При цьому між реченнями одного абзацу діють змістовні зв’язки та мовні вказівники.
Додатково вводиться структура для речення, щоб можна було оперувати словами, а не окремими реченнями.
s
i,j
= s
j
(W(s
j
), R(s
j
))

19 де s
j
– j-е речення, i-го абзацу,
W(s
j
) – множина слів в абзаці,
R(s
j
) – множина синтаксичних відношень між словами.
Можлива ситуація, коли між елементами тексту (наприклад, абзацами) відсутня змістовна зв’язність. Це подається у вигляді
T

= U T
k,
Тоді текст, представлений для аналізу, виступає як сукупність окремих текстів, кожен з яких має свій зміст.
Зауважимо, що в задачі мультиреферування ситуація, коли текст насправді являє собою мультитекст – звичайне явище.
1.4.2 ЗАПОЗИЧЕННЯ В ПОДРОБИЦЯХ
Запозичення можуть бути двох типів: легальні, оформлені у вигляді цитат, можливо, без лапок, і приховувані, можливо з додатковими спотвореннями.
Позначимо G - вихідний текст, з якого щось запозичалося, D - текст- мета, текст до якого щось було запозичене.
Виявлення запозичень першого типу не являє собою особливої проблеми для читача, тому що автор тексту сам робить все необхідне, щоб читач впізнав запозичення. Можна вважати, що в межах такого запозичення більшість відносин визначених у G буде існувати і в D, на всіх рівнях ієрархії керуючого простору тексту [1], незалежно від того, як ми їх визначимо.
Проте це лишається досить складною задачею для автоматичного аналізу.
Успішність виявлення запозичень другого типу залежить від:
- Успіху розбиття тексту на блоки по смислової цілісності,
- Структури відношення R (T),
- Структури відношення R (a (T)),
- Структури відношення R (s (a (T))).
Для розбиття тексту D на блоки за смисловою цілісністю у загальному випадку потрібен апарат, порівнянний з штучним інтелектом. Оскільки поки

20 що його немає, то для розбиття пропонується використовувати метод, що спирається на ознаку більш низького рівня: на наявність зв'язок, забезпечуваних смисловими або анафоричними засобами. Розрив такої структури будемо вважати кінцем блоку.
У системі, яку ми розглядаємо, кінець блоку визначається за результатами, отриманими у процесі індексації. А саме, розриви за
TextTilling та розриви лексичних ланцюжків вказують на межі блоків.
Відношення R (T) можна апроксимувати відношенням порядку. Таким чином, щоб абзац в D приводив до того ж висновку, потрібно, щоб він перебував після тих самих вихідних положень, що і в G.
Позначимо N (a, T) - функцію, яка повертає номер абзацу в тексті. Нехай виконуються умови: a
1
,a
2
є D, a
1
,a
2
є G, N(a
1
, D)> N(a
2
D) & N(a
1
, G)> N(a
2
G)
=> a
1
R(D) a
2
& a
1
R(G) a
2

Відношення R(a
i
) задається подібно до відношення R(T). Позначимо
a(G) – абзац з тексту G, a(D) – абзац з тексту D. Позначимо N(s,a) – функцію, що повертає номер речення в абзаці.
Тоді слабке відношення задається так:
s
1
,s
2
є a(D), s
1
,s
2
є a(G), N(s
1
, a(D))> N(s
2
a(D)) & N(s
1
, a(G))> N(s
2
,a(G)) => s
1

R(a(D)) s
2
& s
1
R(a(G)) s
2

Сильне відношення задається з урахуванням збереження змістовних зв’язків і мовних вказівників. Позначимо P(s,a) – функцію, котра повертає речення, на які є вказівники. Позначимо Q(s,a) – функцію, котра повертає речення, з якими є змістовні зв’язки.
Тоді сильне відношення задається так:
s
1
,s
2
є a(D), s
1
,s
2
є a(G), P(s
1
, a(D)) U Q(s
1
, a(D)) = P(s
1
, a(G)) U Q(s
1
, a(G)) &
P(s
2
, a(D)) U Q(s
2
, a(D)) = P(s
2
, a(G)) U Q(s
2
, a(G)) => s
1
R(a(D))s
2
& s
1

R(a(G)) s
2

Відношення R(s
j
) задається так. Позначимо s(a) – речення абзацу.
Позначимо V(w,s) – функцію, яка повертає слова, зв’язані с даним словом у реченні.

21
w
1
, w
2
є s(a(D)), w
1
, w
2
є s(a(G)), V(w
1
,s(a(D)))= V(w
1
,s(a(G))) & V(w
2
,s(a(D)))=
V(w
2
,s(a(G))) =>w
1
R(s(a(D))) w
2
& w
1
R(s(a(G))) w
2
Бажано задавати зв’язок виключно за допомогою синтаксичних зв’язків слів речення, наскільки це дозволяє якість синтаксичного аналізатора. Такий підхід дозволяє гарантовано опрацювати все можливі коректні перестановки слів у реченні. За відсутності хорошого аналізатора V(w,s) задається як
індикаторна функція для слів по реченню.
Побудовані вищеописаним чином відношення R(a), R(s), R(w)
гарантують, що запозичені елементи будуть відзначені, але власний текст буде проігноровано. Тоді можна визначити оцінку запозичення тексту.
F
1
= |{ (a
1
, a
2
): a
1
, a
2
є D, a
1
R(D) a
2
& a
1
R(G) a
2
}|, якщо |D(a)|>1, інакше 1.
F
2
= |{ (s
1
, s
2
): s
1
R(a(D))s
2
& s
1
R(a(G)) s
2
}|, якщо |D(s)|>1, інакше 1.
F
3
= |{ (w
1
, w
2
): w
1
R(s(a(D))) w
2
& w
1
R(s(a(G))) w
2
}|,

F (D,G)= F
1
*F
2
*

F
3
/ (|D(a)|^2*| D(s)| ^2* |D(w) |^2), (1)
де |D(a)|, |D(s)|, |D(w)| – кількість абзаців, речень і слів у тексті.
Властивості оцінки:
1)
F (D,G) ≥ 0, для довільних D,G.
2)
F (G
1
,G
2
) ≠ F (G
2
,G
1
)
З практичних міркувань у мультиреферуванні більш корисною є така сама оцінка але для блоків, що визначаються на основі індексації текстів.
Альтернативним способом побудови оцінки запозичень є застосування моделі на n-грамах [*7*]. Послідовність слів мови w
1
…w
n
називається n- грамою порядку n, якщо вони розташовані в тексті одне за одним.
Позначається w
1
n
Зафіксуємо Th – як рівень допуску для збіжності.
Алгоритм побудови оцінки запозичень на n-грамах
Для кожного тексту T є {T}
l
Створити порожній словник D n-грам, де ключем буде w
1
n
, значенням – її частота
Для всіх w
i
є T: сформувати w
i
n+i-1
, до яких вони входять,

22 внести w
i
n+i-1
в D, відповідно збільшуючи лічильники частот
Створити квадратну матрицю збіжностей текстів A={a
lm
},
Для всіх D
l
:
Для всіхw
i
n+i-1
у D
k
, l<>k
За кожну знайдену w
i
n+i-1
в D
k
збільшувати a
lk
Для всіх a
lm
> Th,
Для T
l
і T
k
:
Вказати збіжні елементи.
Такий алгоритм працює швидше, проте не стійкий до складних запозичень.
1.5. КЛАСТЕРИЗАЦІЯ
Важливим етапом мультиреферування є кластеризація фрагментів текстів, для того, щоб прибрати дублі та зібрати подібні тексти в групи.
Якщо замість набору текстів є огляд, то зникає потреба в першому етапі кластеризації, а саме в кластеризації за результатами індексації.
1.5.1 МІРИ ЯКОСТІ КЛАСТЕРІВ ТА КЛАСТЕРНОГО РОЗБИТТЯ
Важливою проблемою кластерного аналізу є вибір методології визначення якості одержаних кластерів та визначення цільової функції кластерного аналізу. Найбільш ефективні результати досліджень одержані при використанні так званих зовнішніх мір, тобто при порівнянні результатів автоматичного аналізу з ручним.
Критерії якості кластеризації, як правило, ґрунтуються на наступних вимогах:
- усередині груп об’єкти повинні бути тісно пов’язані між собою;
- значення відстані між об’єктами різних груп повинне бути достатньо великим;
- при інших рівних умовах розподіл об’єктів по групам повинен бути рівномірним.

23
Міри якості кластерного розбиття поділяються на два класи. До першого класу відносяться міри, які базуються на оцінках експертів, так звані зовнішні міри якості, наприклад F-міра. До другого класу, відповідно, відносяться міри, які не використовують додаткову інформацію – внутрішні міри якості, наприклад – загальна внутрішня подібність.
У задачі мультиреферування порушуються всі такі вимоги. У той же час,
існує хороша оцінка загальної внутрішньої подібності, за рахунок можливості обчислити ступінь запозичення одного тексту відносно іншого.
Це, у свою чергу, підштовхує до застосування кластеризації на графах, про яку буде йтися нижче.
Міра близькості, заснована на визначенні запозичень, добре спрацьовує, коли тексти документів є запозиченнями одне з одного. Це, зазвичай є нормою в текстах новин, опублікованих в Інтернеті, коли новину передруковують, лише додавши посилання на джерело. Проте для повноцінного аналізу такої міри близькості не досить.
Альтернативою виступає метод оцінки за словниками текстів. Два тексти будуть тематично близькими, якщо набори сутностей, згаданих у них, збігаються. Що більша збіжність, то більша подібність тематичного наповнення.
Для оцінювання такої близькості використовується косинусна міра. cos Θ = (A,B)/ ( |A||B| ) де A,B – частотні словники текстів, представлені як вектори.
Подібність, обчислена таким чином, досить добре описує тематичне наповнення текстів, за умови, що коректно виділені основні термінологічні одиниці.
Оцінка складності швидкість порівняння текстів за такою мірою
O(оцінки подібності) = O(N)

24 1.5.2. КЛАСТЕРНИЙ АНАЛІЗ НА ЗВАЖЕНИХ ГРАФАХ
Методи кластеризації, які базуються на використанні зважених графів, об'єктам вибірки ставлять у відповідність деякий набір вершин V. Дві вершини
a
v
та
b
v
, що відповідають векторам ознак
a
x
та
b
x
об'єктів A та B, можуть бути з’єднані ненаправленим ребром
ab
E
з додатковою вагою
)
;
(
b
a
x
x
S
, що являє собою міру близькості між векторами. Кількість ребер графа E дорівнює кількості ненульових значень близькості між усіма парами точок. Набір ребер, видалення яких розбиває граф
)
,
(
E
V
G

на k підграфів, що не перетинаються, називається роздільником ребер. Отже, метод кластерного аналізу з використанням зважених графів полягає в знаходженні роздільника ребер з мінімальною сумою належних йому ребер.
При цьому часто накладається додаткова умова – отримання приблизно рівної кількості об'єктів (вузлів) у кожному кластері (підграфі).
Відповідно до розглянутого методу загальна складність алгоритму кластеризації складе O(N
2
)* O(оцінки запозичень).
Треба врахувати, що сама по собі формула (1) вказує на складність принаймні
O(оцінки запозичень) = O(N
4
), де N - кількість слів у тексті.
Таким чином, оптимальною виглядає попередня кластеризація за результатами індексації або якимось іншим способом, з подальшою додатковою кластеризацією за мірою запозичення.
1.6. ВИДІЛЕННЯ ТЕРМІНОЛОГІЧНИХ ОДИНИЦЬ
Задача виділення термінологічних одиниць виникає, коли в тексті зустрічаються терміни, які не відомі базі знань (WordNet). Особливо це важливо, коли терміни складаються з декількох слів.
Звичайно використовують такі методи: підрахунок кількості пар, t- критерій Стьюдента, критерій узгодженості Пірсона. Методи простого

25 частотного підрахунку та t-критерій також є досить ефективними і можуть бути використані для складання списку термінів-кандидатів у системах напівавтоматичного формування термінів. Основний тип помилок обох методів – виділення стійких загальновживаних словосполучень, які задовольняють шаблонам-обмеженням.
Найбільша проблема всіх частотних методів наступна: при збільшенні довжини терміна падає його частота, навіть у спеціалізованому корпусі термін може зустрічатися один-два рази.
Звичайними методами, які дозволяють обійти такі обмеження, є метод максимальної довжини та метод контролю у вікні.
Метод максимальної довжини. Виділення максимальних ланцюжків, які містять терміни. Ці ланцюжки визначаються через негативний відбір: складається список слів і знаків, які не можуть входити в термін. У нашій реалізації в якості таких роздільників ми розглядаємо розділові знаки, стоп- слова, дієслова, дієприслівники; послідовності слів між цими роздільниками розглядаються як кандидати в терміни.
Метод контролю у вікні. До частоти сумісного входження включається також частот входжень слів в одне вікно певного розміру (8 слів). Вважається, що якщо пари елементів зустрічаються як безпосередні сусіди більш ніж у половині випадків їх появи в тому самому текстовому вікні, те ця пара являє собою термін або фрагмент терміна. Відбувається склейка пари у єдиний елемент, таблиці перераховуються так, ніби цей елемент був відомий із самого початку, до початку обробки тексту, що дає можливість і далі нарощувати термін.
За результатами перехресної перевірки частина слів об’єднуються в багатослівні терміни.
1.7. РЕФЕРУВАННЯ
Базується на результатах індексації, тематичного аналізу, аналізу запозичень та результати кластеризації.

26 1.7.1 ВИЗНАЧЕННЯ ВАЖЛИВОСТІ ЕЛЕМЕНТІВ ТЕКСТУ
Важливість елементів тексту визначаться відповідно до того, наскільки вони цікавлять користувача та наскільки вони важливі для представлення змісту тексту. Є декілька підходів до визначення важливості елементів.
Частотні критерії: частота вживання терміну, та TF*IDF.
Частота – кількість випадків вживання терміну у тексті F(w
i
), w
i
є T.
TF*IDF – спирається на роздільну силу терміну. Що термін частотніший, то більш він важливий. Проте, чим до більшої кількості речень чи текстів він входить, то слабкіше їх розрізняє.
В TF*IDF, TF – частота терміну, IDF – інверсна частота документу. де, n
i
є число входжень терміну в документ, а в знаменнику — сума частот термінів у даному документі.
, де |D| — кількість документів в корпусі;
- кількість документів, у яких зустрічається t
i
(коли n
i більше нуля).
З указаних елементів збирається статистична оцінка (StatTerm) для термінів, і за потреби - як сума ваг для блоку з T
b
Конекціоністські критерії: зв’язність у графі, утвореному з w
i
є T,
входження у відповідні лексичні ланцюжки та TextRank (Connect).
Зв’язність у графі – кількість вершин, які пов’язані з вершиною, що відповідає w
i
є T.
Якщо використовуються лексичні ланцюжки, то кожен з них може мати власну вагу, і тим самим модифікує вагу w
i.
TextRank – аналог міри PageRank, що вживається для визначення.
Критерії за структурними ознаками тексту: розташування w
i
,
наявність поблизу спеціальних слів або фраз маркерів.

27
Ознака розташування (Location) залежить від того, де у всьому тексті або в окремо взятому параграфі з'являється фрагмент, що містить w
i
- на початку, всередині або в кінці, а також чи використовується w
i
в ключових розділах, наприклад, вступній частині або у висновках. Важливим критерієм
є і те, чи з'являється w
i
також у заголовку, у колонтитулі, першому параграфі.
Ключова фраза (CuePhrase) представляє собою лексичні або фразові конструкції, такі як: „на закінчення”, „у даній статті”, „згідно з результатами аналізу” і так далі. Ваговий коефіцієнт ключової фрази може залежати також
і від прийнятого в даній предметній області оцінного терміна, типу
„відмінний” (найвищий коефіцієнт) або „малозначне” (значно менший коефіцієнт).
Машинно вивчені критерії: для їх побудови вживається алгоритм машинного навчання того чи іншого виду над множиною текстів та множиною відповідних рефератів. У межах цього посібника вони не розглядаються.
Задані користувачем: наявність w
i
профілі визначеному користувачем системи (AddTerm). Виділення пріоритетних термінів, що найбільш точно відображають інтереси користувача, - це один із шляхів налаштувати реферат або анотацію на конкретну людину або групу.
Спеціалізовані критерії: у випадку мультиреферування замість важливості, яку визначає користувач, використовується індекс цитування новини як зовнішня експертна оцінка її важливості. (Special)
Використання лише якогось одного типу критеріїв не є оптимальним.
Наприклад, за частотним принципом: чим частотніше слово/поняття у тексті,тим воно важливіше. Проте, може мати місце випадок, коли група слів/понять разом важлива для тексту, хоча кожне з них зустрічається не досить часто, щоб частотний критерій розпізнав їх як важливі.
При цьому застосовується модель лінійних вагових коефіцієнтів.
Основу аналітичного етапу в цій моделі складає процедура призначення

28 вагових коефіцієнтів для кожного блоку тексту відповідно з вказаними вище характеристиками.
Сума індивідуальних ваг визначається після додаткової модифікації у відповідності з параметрами налаштування і дає загальну вагу всього блоку тексту T
b
:
Weight(T
b
) := Location(T
b
) + CuePhrase(T
b
) + StatTerm(T
b
) + Connect (T
b
)+
AddTerm(T
b
)+ Special(T
b
)
1.7.2 ПЕРЕДОБРОБКА
Перш за все, після визначення важливості кожного повнозначного слова, необхідно визначити межі тематичних областей в тексті. Це робиться простим проходом по тексту з розстановкою маркерів. Після чого проводиться розстановка обмежувачів, які чітко визначають, де певна тема скінчилася або почалася. Позначимо s є T – речення тексту. Повнозначне слово, як завжди, – w
i.,
с(w
i
)
j
– сенс слова w
i
, {с(w
i
)
j
}
k
– ланцюжок, що містить відповідний сенс слова.


Поділіться з Вашими друзьями:
1   2   3   4   5   6


База даних захищена авторським правом ©divovo.in.ua 2017
звернутися до адміністрації

войти | регистрация
    Головна сторінка


загрузить материал