Критерії ефективності для моделей інформаційного пошуку

Главная » Каталог статей » Статьи на украинском » Моделювання » Критерії ефективності для моделей інформаційного пошуку

Завдання інформаційного пошуку

asdsdsd

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

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

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

· Кластеризація документів

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

Класифікація документів

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

Окремим випадком завдання класифікації є завдання тематичної класифікації. Тут кожна категорія — це деяка тематика, а мета класифікації — визначити тематику документа.

Фільтрація документів

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

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

Моделі інформаційного пошуку

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

Формально, опис будь-якої моделі інформаційного пошуку складається з 4 частин:

  • clip_image001- безліч використовуваних типів представлень документів
  • clip_image002- безліч використовуваних типів описів інформаційних потреб користувача, тобто запитів
  • clip_image003- загальний каркас, в рамках якого відбувається моделювання описів документів і запитів, а також опис взаємозв’язків між ними
  • clip_image004- функція ранжирування, яка парі документ/запит зіставляє деяке дійсне число

Моделі інформаційного пошуку діляться на три класи:

Теоретико-множинні моделі

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

Імовірнісна модель

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

Модель алгебри

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

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

Векторна модель

Векторна модель є класичним представником класу алгебраїчних моделей. В рамках цієї моделі кожному термуclip_image005в документі clip_image006(і запитіclip_image007) зіставляється деяка ненегативна вага clip_image008(clip_image009 для запиту). Таким чином, кожен документ і запит може бути представлений у виглядіclip_image010- вектора

clip_image011

де clip_image010[1]- загальна кількість різних термів у всіх документах.

Згідно векторної моделі, близькість документа clip_image012до запиту clip_image007[1] оцінюється як кореляція між векторами їх описів. Ця кореляція може бути обчислена, наприклад, як скалярна сума відповідних векторів описів. Ваги термів можна обчислювати безліччю різних способів. Один з можливих підходів — використовувати як вагу терма clip_image008[1]в документі clip_image012[1]нормалізовану частоту його використання clip_image013в рамках даного документа, тобто :

clip_image014

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

clip_image015

де clip_image016означає число документів в котрих використовується терм clip_image017, а clip_image018- загальне число документів в колекції.

Латентно-семантичний аналіз

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

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

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

Найбільш поширений варіант LSA заснований на використанні розкладання матриці по сингулярних значеннях (SVD). Використовуючи SVD, величезна початкова матриця розкладається в множину з clip_image010[2], зазвичай від 70 до 200, ортогональних матриць, лінійна комбінація яких є непоганим наближенням початкової матриці.

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

clip_image020

таких, що матриці clip_image021та clip_image022- ортогональні, а clip_image023- діагональна матриця, значення на діогоналі якої називаются сингулярними значенями матриці clip_image019[1].

Таке розкладання володіє чудовою особливістю: якщо в clip_image023[1]лишити тільки clip_image010[3]наибільших сингулярних значень, а в матрицях clip_image021[1]і clip_image022[1]тільки відповідне цим значенням стовбців, то добуток отриманих матриць clip_image024, clip_image025іclip_image026буде найкращим наближенням початкової матриці clip_image019[2]матрицею ранга clip_image010[4]:

clip_image027

Основна ідея латентно-семантичного аналізу полягає в тому, що якщо в якості clip_image019[3] використовувалася матриця терми-на-документи, то матриця clip_image028, що містить тільки clip_image010[5] перших лінійно незалежних компонентівclip_image019[4], відображає основну структуру асоціативних залежностей, присутніх в початковій матриці, і в той же час не містить шуму.

Таким чином, кожен терм і документ представляються за допомогою векторів в загальному просторі розмірності clip_image010[6](так званому просторі гіпотез). Близькість між будь-якою комбінацією термів і/або документів може бути легко обчислена за допомогою скалярного добутку векторів.

Вибір якнайкращої розмірності clip_image010[7] для LSA — відкрита дослідницька проблема.

У ідеаліclip_image010[8] повинно бути достатньо велике для відображення всієї реально існуючої структури даних, але в той же час достатній мало, щоб не захопити випадкові і маловажливі залежності. Якщо вибране clip_image010[9]дуже велике, то метод втрачає свою потужність і наближається по характеристиках до стандартних векторних методів. Дуже маленьке clip_image010[10] не дозволяє уловлювати відмінності між схожими словами або документами. Дослідження показують, що із зростанням clip_image010[11] якість спочатку зростає, а потім починає падати.

Критерії оцінки ефективності

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

clip_image029
Малюнок: Точність и повнота відповіді clip_image030на запит при пошуку в колекції документів clip_image031. Тут clip_image032 позначає множину «істинно» релевантних документів.

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

clip_image033

clip_image034

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

clip_image035

Экспериментальні результати

Тестування тематичного фільтру

Для експериментів з тематичним фільтром за допомогою робота ми побудували англомовні тестові колекції, що складаються з HTML сторінок, причому приналежність сторінок тематиці колекції перевірялася вручну. Було створено одинадцять колекцій з наступними темами: Автомобілі, Монітори, Музеї, Методи пошуку інформації, Подорожі, Наукові проекти, Linux, Програмування, Карткові ігри, Фізика, Методи вимірювання продуктивності. У кожній з колекцій було приблизне по 150 документів.

clip_image037

Автоматична побудова тематичного фільтру для колекції

Для того, щоб побудувати тематичні фільтри, з кожної колекції було випадковим чином вибрана підмножина з 50 документів. Ці підмножиниclip_image038, використовувалися для автоматичної побудови відповідних тематичних фільтрів. Для кожного документа clip_image039 обчислювалася частота використання терма clip_image040в даному документі clip_image041. Для всіх термів clip_image040[1]з колекції clip_image038[1], вираховувалась средня частота використання

clip_image042

де clip_image043- кількість документів clip_image038[2]. Всі терми, средня частота використання яких в clip_image038[3]перевищувала средню частоту в clip_image044( clip_image045), включалися в тематичний фільтр для i-тої колекції із значущістю clip_image046


Вимірювання ефективності тематичного фільтру

Як було пояснено в розділі, основними критеріями якості для використовуваного роботом методу фільтрування є повнота і частка відфільтрованого сміття (ДОМ), а точність не грає істотної ролі.

Для кожного з побудованих тематичних фільтрів ми зміряли його ефективність на загальній безлічі документів з тестових колекцій. Поріг рекомендації clip_image047 вибирався так, щоб при застосуванні фільтру до множини використаних для його створення документах досягалося задане значення повноти clip_image032[1].

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

Експерименти із стратегією обходу

clip_image050
Малюнок: Залежність кількості релевантних документів від числа відвіданих для порівнюваних стратегій (T=0.000199)
clip_image051
Малюнок: Залежність кількості релевантних документів від числа відвіданих для порівнюваних стратегій (T=0.000042)

Метою цих експериментів був аналіз практичної ефективності запропонованої стратегії обходу Інтернет-ресурсів.

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

1. Нетематичний обхід

Як стратегія, що не враховує інформацію про тематику відвідуваних документів, використовувалася стратегія «обхода в ширину» (breadth-first).

2. Тематичний обхід

Стратегія обходу з використанням тематичного фільтру, побудованого згідно алгоритму.

3. Тематичний обхід з уточненим фільтром

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

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

На малюнках для кожної з трьох даних стратегій на прикладі тематики «Подорожі» приведені залежності кількості виявлених тематично релевантних сторінок від числа відвіданих сторінок. Малюнки відповідають двом різним значенням (clip_image052та clip_image053) порогу тематичного фільтру, який використовувався тільки для підсумкової оцінки отриманих результатів.

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

При використанні грубої оцінки результатів, тобто вищого порогу тематичного фільтру, різниця складає 20-25% на 5000 документів, а при використанні жорсткішого критерію перевага досягає 90%.

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

Список використаної літератури :

1. Е.В. Романова, М.В. Романів, И.С. Некрестьянов.

Використання інтелектуальних мережевих роботів для побудови тематичних колекцій.

Програмування, 3:63-71, 2000.

2. Дж. Голуб, Ч. Ван Лоун.

Матричні обчислення.

Видавництво «Мир», Москва, 1999.

3. Ілан Грінберг Чи, Гарбер.

Розробка нових технологій інформаційного пошуку.

Відкриті Системи, 10, 1999.

4. И.Е. Кураленок, И.С. Некрестьянов.

Автоматична класифікація документів з використанням семантичного аналізу.Програмування, 4:31-41, 2000.

Оставьте комментарий к статье