Семантичний морфологічний аналіз тексту онлайн методи LSA для пошуку схожих документів

І знов наш аналітичний відділ підготував матеріал для читачів блогу Netpeak. Передаю привіт Кирилові Левенцю — він зробив титанічний працю, щоб викласти зрозумілою мовою не найпростіші речі.

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

Про один із методів, який застосовується для рекомендаційних систем (колаборативна фільтрація), інформаційного семантичного пошуку, поділу текстів за тематиками без навчання та багатьох інших і йтиметься далі. Цей метод називається латентно-семантичним аналізом (LSA — Latent semantic analysis). Можна сміливо сказати, що це просунутий SEO аналіз тексту.

Розглянемо докладніше, що це за метод і як він працює

Вже з назви можна зробити висновок про те, що він повинен робити, а саме знаходити приховані смислові взаємозв'язки між об'єктами (чи слова в тексті або товари в магазині). Для текстів природними мовами такою прихованою закономірністю може бути, наприклад, наявність певного набору слів у певній темі. Уявімо таке завдання: у нас є колекція документів і ми хочемо навчитися відповідати на запитання: чи два документи близькі за тематикою чи ні. Висновок про схожість можна зробити, ґрунтуючись на тому, які слова та в яких пропорціях входять до кожного з документів.

Щоб підготувати дані до цього завдання, використовують підхід, який називається «мішок слів».

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

Грунтуючись лише з цієї інформації, будується таблиця «слово-документ». Де рядки відповідають словам (а точніше, їхнім лемам), а стовпці – документам. У кожному осередку зберігається 1, якщо слово є у документі, і 0 - якщо немає. Хоча такий варіант і найпростіший, але не найкращий. Замість 0 і 1 можна використовувати, наприклад, частоту слова в документі або слова tf-idf. Такий спосіб представлення текстів як таблиці (або матриці) називається векторної моделлю тексту. Тепер, щоб порівняти два документи, потрібно визначити міру схожості двох стовпців таблиці.

Зробити це можна по-різному:

скалярний добуток векторів - стовпців таблиці;
косинусна відстань (мабуть найадекватніша);
евклідовою відстанню;
манхеттенською відстанню.

Щоб краще зрозуміти все сказане вище, зобразимо це графічно на простому прикладі двох невеликих текстів. Один текст для писемності, інший для невизначеності Гейзенберга. Стоп-слова видалені, а інші наведені до основної форми (без закінчення). Кожна точка на графіці – слово. На осях відкладено, скільки разів слово зустрілося у кожному документі. Тобто. якщо слово зустрілося у тексті про невизначеність 3 разу, а тексті про писемність 2 разу, то малюнку це слово зобразимо точкою з координатами (3,2).

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

Для порівняння документів можна підрахувати суму векторів-слів, які входять і знову ж таки оцінити відстань між ними. У розглянутому прикладі слова розподілилися добре, оскільки тематики суттєво різні. А якщо тематики схожі, то може вийти така картина:

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

Але в житті виявляється, що документів і слів дуже багато (набагато більше ніж тим) і виникають такі проблеми:

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

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

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

Числа в таблицях у випадку не обов'язково будуть саме 0 і 1. Маючи таке уявлення, ми можемо окрім оцінки близькості слів і документів, також визначати важливі слова кожної тематики.

Обмеження LSA:

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

LSA включає наступні етапи:

Видалення стоп-слів, стемінг або лематизація слів у документах;
Виняток слів, що зустрічаються в єдиному екземплярі;
Побудова матриці слово-документ (бінарну є/ні слова, число входжень або tf- >У результаті виходить щось таке:

Приклад із невеликими документами

[Взято зі статті Indexing by Latent Semantic Analysis, Scott Deerwester, Susan T. Dumais, George W. Furnas, та Thomas K. Landauer, Richard Harshman]

Нехай є наступний набірзаголовків-документів:

c1: Human machine interface for ABC computer applications
c2: A survey of user opinion of computer system response time
c3: EPS user interface management system
c4: System and human system Engineering Testing of EPS
c5: Relation of user perceived response time to error measurement
m1: generation of random, binary, ordered trees
m2: Intersection graph of paths in trees
m3: Graph minors IV: Widths of trees and well-quasi-ordering
m4: Graph minors: A survey

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

Застосовуємо сингулярне розкладання до цієї матриці та отримуємо три матриці (U, V, W T ).

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

Розглянемо відстань між кожною парою слів. Було (жовтим кольором виділено значення вище 0):

Стало після зниження розмірності (зеленим кольором виділено значення більше 0,8):

Як і по картинці, так і по таблиці видно, що терміни утворили 2 групи (досить умовно) і порівняно з вихідною матрицею зв'язку значно посилені (як зміцнилися вихідні, так і з'явилися нові):

[human, interface, computer, user, EPS, response, time],
[Survey, trees, graph, minors].

Між кожною парою документів.

Відношення терміну документ.

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

Видно, що тема "комп'ютер" добре відокремилася від двох інших. А ось "спорт" та "авто" досить близькі один одному. Для кожної теми з'явилися свої ключові слова. Зеленим на малюнку зображено запит "автомобіль коліс". Його релевантність до документів має такий вигляд:

'sport.txt' - 0.99990845
'auto.txt' - 0.99987185
'computer.txt' - 0.031289458

Через близькість тем "спорт" та "авто" досить складно точно визначити, до якої теми він належить. Але точно не до "комп'ютерів". Якщо в системі, навченій на цих документах, спробувати визначити релевантність до тем, що утворилися, слова "ринок", то у відповідь ми отримаємо 0 (т.к. це слово в документах не зустрічалося жодного разу). Додамо до системи документ на тему "фінанси". Знову шукатимемо слово "ринок".

Отримаємо таку картинку:

Релевантність до тем буде такою:

'finance.txt' - 0.99948204
'sport.txt' - 0.97155833
'auto.txt' - 0.23889101
'computer.txt' - -0.24506855

Отже підіб'ємо підсумок:

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

Виявили помилку? Виділіть її та натисніть Ctrl+Enter.