Использование частотных мер в индексировании.

Вопросы по информатике

1. Понятие информационной технологии.

ИТ – средства, методы и системы сбора, передачи, обработки и представления информации пользователю.

Существуют 4 этапа эволюции:

Появление речи;

Появление письменности;

Появление средств ВТ (Современные и тд.).

В современном ИТ выделяют 3 составляющие:

Аппаратное обеспечение (средства ВТ и оргтехники – hardware);

Программное обеспечение (прикладное и системное ПО, методическое и информационное обеспечение – software);

Организационное обеспечение (включая человека в системы ИТ, взаимодействие человека с этими системами, системное использование технических и программных средств – orgware)

ИТ = новые ИТ = современные ИТ.

Новые ИТ – современная ИТ технология, использующая развитый (интеллектуальный) интерфейс с конечным пользователем.

ИТ как прикладная наука, изучает фундаментальные соотношения в больших информационных системах.

ИТ как практика – интеллектуальная деятельность по проектированию и созданию конкретных технологий обработки данных.

В ИТ выделяют 3 составляющие:

Базовые ИТ. Обеспечивают решение отдельных компонентов в той или иной задаче, служат для создания прикладных ИТ. Например: технологии программирования, СУБД, системы распознавания изображения и тд.

Прикладные ИТ. Формируются на основе базовых ИТ, предназначены для полной информатизации объекта.                                 Например: САПРы, АСУП, геоинформационные системы.

Обеспечивающие ИТ. Обеспечивают реализацию базовых и прикладных ИТ. На рынке представлены их отдельные компоненты. Например: современная микроэлектронная база средств ВТ, перспективные системы и комплексы (оптические и нейрокомпьютеры, транспьютеры).

3.Основные методы организации текстовых файлов.

Цепочечные файлы.

К самой БД добавляется справочник, который имеет следующую структуру:

Ключ – значимое слово, характеризующее тот или иной документ. Рядом пишется адресная ссылка на тот текстовый файл, который имеет данный ключ в качестве значимого термина. И к этой подстроке добавляются собственно текстовые файлы.

Цепочечная модель: сколько индексных терминов в тексте выделено столько и должно быть ссылок.

Преимущества:

Максимальная длина поиска определяется самой длинной цепочкой;

Новые записи (тексты) можно ставить в начало цепи, что упрощает её корректировку.

Недостатки:

Цепи могут быть длинными, если некоторые ключи используются довольно часто;

Необходимость выделения памяти для хранения адресных ссылок в самих текстах;

Если справочник очень велик, он значительно усложняет работу с текстами и требует организации дополнительного доступа к себе самому.

Вопрос 5(окончание).

термину k. Если S^k уменьшается, то k либо вообще не рассматривается как возможный индекс, либо ему присваивается отрицательный вес.

1.Параметры, основанные на динамической эффективности.       Всем терминам первоначально присваиваются одинаковый вес, затем пользователь формирует запрос, и выдаются документы и пользователь определяет релевантность, система сама уменьшает или увеличивает вес документа, в соответствии с потребностями пользователя, т.е. предусматривается некоторая программа обучения системы.

Мы рассмотрели статистические подходы (СП). Помимо СП используются такие подходы, которые предусматривают местоположение термина в тексте.

Подходы:

1. В индексационные термины включаются те, которые встречаются в названиях документов, названиях глав, разделов и т.д.

2. Составляются списки значимых для некоторой предметной области слов. Т.е. составляется глоссарий по некоторой предметной области.

Методы увеличения полноты. Часто бывает необходимо выдать наибольшее число релевантных документов из массива. В этом случае необходимо к используемым индексационным терминам добавить дополнительные, чтобы расширить область поиска.

1-й подход к решению этой задачи: использование терминов заместителей из словаря синонимов, который называют тезариусом, в котором термины сгруппированы в классы.

2) Метод ассоциативного индексирования. Основан на использовании матрицы ассоциируемости терминов, которая задаёт для каждой пары терминов показатель ассоциируемости. Абсолютная запись этого ПА между терминами j и k:

f ( j ; k ) = сумм ( i=1 – n ) f_i^j * f_j^k – частота совместного использования f ( j ; k ) = сумм ( i=1 – n ) f_i^j * f_j^k / (сумм ( i=1 – n ) f_i^{j ^} 2+ сумм ( i=1 – n ) f_j^{k ^} 2 – сумм ( i=1 – n ) f_i^j * f_j^k - для расчёта относительного значения этого показателя. f_i^j,k – частота появления термина j или k в i – м документе. 0 <= f ( j ; k ) <= 1. Если f ( j ; k ) = 0, то термины совсем не ассоциируются, если f ( j ; k ) = 1, то полностью ассоциируемы. 

Использование частотных мер в индексировании.

Частотный метод – по каждому термину, входящему в документ подсчитывается частота вхождения терминов в документ fik, i – номер документа, k – термин. Эта частота абсолютная. Затем документы упорядочиваются в соответствии с возрастанием или убыванием частоты.

Если термин имеет большую частоту, то это, скорее всего общеупотребительный термин, не раскрывающий конкретную предметную область (будет много документов).

Если термин имеет малую частоту, то он существенно отражает содержание, даже если его включить в дескрипторы (ключевые слова), то он , скорее всего будет использоваться в холостую. Поэтому эти 2 простейших документа исключают из списка.

Терминам с большей частотой присваивают меньший вес, с меньшей частотой – больший вес.

Инвертированные файлы.

Получаются из цепочечных файлов, когда в справочник включаются адресные ссылки на все тексты, имеющие соответствующий ключ в качестве индексационного термина.

Недостаток: переменное число адресов в справочнике.

Достоинство: быстрый поиск релевантных документов, так как их адреса находятся сразу в справочнике, обработку которого можно организовать в оперативной памяти.

Рассредоточенные файлы.

Весь массив документов разбивается на группы файлов, ключевые термины которых связаны некоторым математическим соотношением. Тогда поиск в справочнике заменяется вычислительной процедурой, которая называется хешированием, рандомизацией или перемешиванием. Здесь нет справочника, а существует вычислительная процедура, т.е. блок, называемый блоком рандомизации, который по ключу (поисковому термину) на основании вычислительной процедуры определяет адрес, по которому находится текст.

Ключ                            адрес        этот участок

{ключ}                                                  памяти

                                                             называется

                                                             бакетом

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

Преимущества:

Быстрый вычисляемый доступ;

Из-за отсутствия справочника экономится память.

Недостатки:

Сложность при выборе метода хеширования;

Применяется для коротких векторов запросов, когда в поиске участвует немного слов;

Изменения векторов документов порождает сложность в ведении файлов.

Кластерные файлы.

Документы разбиваются на родственные группы, которые называют кластерами или классами. Каждый класс описывается центроидом (профилем) и вектор запроса прежде всего сравнивается с центроидами класса.

Преимущества:

Возможен быстрый поиск, т.к. число классов, как правило, невелико;

Возможно интерактивное сужение (расширение) поиска за счёт исключения или добавления дополнительных кластеров.

Недостатки:

Необходимость формировать кластеры;

Необходимость введения файла центроидов;

Дополнительный расход памяти для файла центроидов или профилей.