Інформаційний пошук

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Інформаці́йний по́шук (ІП) (англ. Information retrieval) — наука про пошук неструктурованої документальної інформації. Особливо це відноситься до пошуку інформації в документах, пошук самих документів, добуття метаданих з документів, пошуку тексту, зображень, відео та звуку у локальних реляційних базах даних, у гіпертекстових базах даних таких, як Інтернет та локальні інтранет. Інформаційний пошук — велика міждисциплінарна область науки, яка стоїть на перетині когнітивної психології, інформатики, інформаційного дизайну, лінгвістики, семіотики, бібліотечної справи, та статистики.

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

Об'єктом інформаційного пошуку є текстова інформація, зображення, аудіо, відео інформація.

З інформаційним пошуком змикаються проблеми:

  • розсилки інформації (information routing);
  • сортування інформації (information filtering);
  • упорядкування (класифікація) інформації (information categorization);
  • відбір інформації (information extraction).

Для інформаційного пошуку розробляють:

  • алгоритми інформаційного пошуку (retrieval algorithms);
  • підходи інформаційного пошуку(retrieval approaches);
  • стратегії інформаційного пошуку (retrieval strategies).

Для його здійснення створюють:

  • методи інформаційного пошуку (retrieval utilities);
  • засоби інформаційного пошуку (information retrieval systems);
  • комп'ютерні пошукові програми (search engines).

До проблем інформаційного пошуку належать питання:

  • представлення даних, інформації, знань (data, information, knowledge);
  • представлення інформації в сучасних інформаційних сховищах (representation of information);
  • багатомовний інформаційний пошук (cross-language information retrieval);
  • одночасний інформаційний пошук (parallel information retrieval);
  • розподілений інформаційний пошук (distributed information retrieval);
  • суспільний інформаційний пошук (social information retrieval)

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

  • застосовної (прикладної) лінгвістики (applied linguistics);
  • обробки природної мови (natural language processing);

Завданням інформаційного пошуку є знаходження відповідних (до пошукового запиту) інформаційних об'єктів, або документів серед доступного для пошуку матеріалу. Завдання для інформаційного пошуку задається у вигляді інформаційного запиту (query), який може містити слова, фрази чи речення або комбінацію їх. Переважна більшість пошукових систем орієнтована на роботу з пошуковими термінами — словами або словосполученнями, які пошукова система розпізнає як одне ціле. Для здійснення інформаційного пошуку потрібно мати збірку інформаційних об'єктів (бібліотека, комп'ютерні файли) і систему (алгоритм або програму) яка здійснює пошук. Для здійснення інформаційного пошуку користувач (людина або інформаційна система) формує інформаційний запит (information query). Результатом пошукової роботи є список документів який укладається згідно з певним принципом. Такий список називають впорядкованим (ranked list, ranked results).

Пошукова система переглядає всі доступні інформаційні одиниці (документи) зі збірки і відбирає документи відповідні до інформаційного запиту. Оскільки реальні пошукові системи знаходять не всі відповідні документи, говорять про точність пошукових систем (system accuracy). Результатом роботи пошукової системи є список відібраних документів (retrieved documents list), серед яких є відповідні до запиту документи (relevant documents). Для ідеальної пошукової системи список відібраних документів та відповідних документів повинні збігатися. В реальних пошукових системах в списках відібраних документів знаходяться і невідповідні до запиту документи. Тому говорять про ефективність пошукових систем. Ефективність пошукових систем оцінюється двома параметрами: пошукова відповідність (precision) та пошукова якість (recall). Пошукова відповідність визначає частку відповідних документів серед відібраних на запит. Пошукова відповідність визначає якість отриманого результату інформаційного пошуку. Пошукова якість визначає частку отриманих системою відповідних до запиту документів серед загального числа відповідних до запиту документів у збірці. Загальне число відповідних до запиту документів завжди є невідомим і може бути встановлене лише при повному перегляді збірки людиною. Крім того роботу пошукових систем оцінюють швидкодією — часом, за який отримують список відповідних до запиту документів.

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

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

Стратегії інформаційного пошуку[ред.ред. код]

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

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

Стратегія інформаційного пошуку це алгоритм, який, переглядаючи набір документів (Д1, ..., Дn), встановлює їх відповідність до пошукового запиту (ПЗ). Оскільки пошуковий термін зустрічається в документах різну кількість раз, можна говорити про різну ступінь відповідності до пошукового запиту. Цей алгоритм обчислює коефіцієнт відповідності (similarity coefficient) (КВ) для кожного документу КВ(ПЗ, Дi), де 1 ≤ i ≤ n.

Існують такі стратегії інформаційного пошуку: - з використанням векторно-просторового представлення (vector space model); пошук імовірності появи пошукового терміну в документі (probabilistic retrieval); - з побудовою мовної моделі для кожного документу (language models); - з побудовою мережі припущень, яка використовується для встановлення відповідності документу до пошукового запиту (inference network); - з Булевим індексуванням, коли кожному пошуковому терміну присвоюється своя «вага», що потім враховується при побудові впорядкованих списків документів (Boolean indexing); - з використанням не проявленого семантичного індексування (latent semantic indexing); - з побудовою нейромереж (neural networks); - з використанням продуктивних алгоритмів, коли початковий пошуковий запит «еволюційно» видозмінюється (genetic algorithms); - з використанням нечітких множин, коли документу ставиться у відповідність нечітка множина (fuzzy set retrieval).

Інформаційний пошук за допомогою векторно-просторового представлення[ред.ред. код]

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

G. Salton, A. Wong, and C. S. Yang (1975), A vector space model for automatic indexing "Communications of the ACM", vol. 18, nr. 11, pages 613–620. "(The article in which the vector space model was first presented)"


Імовірнісний пошук[ред.ред. код]

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

Maron, M. E., & Kuhns, J. L. (1960). On relevance, probabilistic indexing and information retrieval. Journal of the ACM, 7(3), 216-244.


Пошук з використанням мовних моделей[ред.ред. код]

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

Ponte, Jay M., and Croft, W. Bruce. A language modeling approach to information retrieval. In Proc. SIGIR, 1998.- pp. 275-281. ACM Press.


Алгоритми прийняття рішень[ред.ред. код]

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

Greiff Warren R., Croft B., Turtle H. PIC matrices: a computationally tractable class of probabilistic query operators. ACM Transactions on Information Systems (TOIS) Volume 17 , Issue 4 (October 1999) p. 367 - 405


Розширений Булевий пошук[ред.ред. код]

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

Fox Edward A., Salton G., Wu H. Extended Boolean information retrieval. Commun. of the ACM, Volume 26 , Issue 11 (November 1983) р. 1022 - 1036


Пошук з прихованим семантичним індексуванням[ред.ред. код]

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

Scott Deerwester, Susan T. Dumais, George W. Furnas, Thomas K. Landauer, Richard Harshman. Indexing by latent semantic analysis. Journal of the American Society for Information Science (1990)


Пошук з використанням нейро-мереж[ред.ред. код]

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

Kwok K. L. A neural network for probabilistic information retrieval. ACM SIGIR Forum, Volume 23 , (June 1989)


Пошук з використанням алгоритмів розвитку[ред.ред. код]

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

Hsinchun Chen Machine learning for information retrieval: Neural networks, symbolic learning, and genetic algorithms. Journal of the American Society for Information Science. Volume 46 Issue 3, Pages 194 - 216


Пошук з використанням нечітких множин[ред.ред. код]

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

Див. також[ред.ред. код]

Література[ред.ред. код]

  • F. Crestani and G. Pasi. Soft Information Retrieval: Applications of Fuzzy Set Theory and Neural Networks. in "Neuro-fuzzy Techniques for Intelligent Information Systems", N.Kasabov and Robert Kozma Editors, Physica-Verlag , Springer-Verlag Group , 287-313, 1999.
  • Ландэ Д.В., Снарский А.А., Безсуднов И.В. Интернетика: Навигация в сложных сетях: модели и алгоритмы. — M.: Либроком (Editorial URSS), 2009. — 264 с. ISBN 978-5-397-00497-8.