Конспект лекций для специальности «Прикладная информатика в экономике»

Вид материала

Конспект

Содержание 4.3. Кластеризация текстов 4.4. Поиск релевантных текстов 4.4.1. Поиск в инвертированных файлах 4.5.2. Поиск при кластерной организации хранения 4.5. Методы расширенного поиска 4.5.1. Построение словаря синонимов Синонимы Syn 4.5.2. Ассоциативное индексирование терминов 4.5.3. Вероятностное индексирование терминов

Подобный материал:

• Учебно-методический комплекс для студентов заочного обучения специальности Прикладная, 81.9kb.
• Конспект лекций для специальности «Прикладная информатика в экономике», 535.22kb.
• Конспект лекций для студентов специальности Прикладная информатика (в экономике), 3204.37kb.
• Учебно-методический комплекс для студентов заочного обучения специальности Прикладная, 172.73kb.
• Рабочая учебная программа по Правоведению Для специальности- «Прикладная информатика, 388.83kb.
• Учебно-методический комплекс для студентов заочного обучения специальности Прикладная, 88.44kb.
• Программа по курсу "Математика. Алгебра и геометрия" для специальности 080801 (351400), 143.45kb.
• Учебно-методический комплекс Для специальности 080801 Прикладная информатика (в экономике), 296.07kb.
• Учебно-методический комплекс Для специальности 080801 Прикладная информатика (в экономике), 610.8kb.
• Рабочая программа по дисциплине «Исследование операций в экономике» для специальности, 137.37kb.

4.3. Кластеризация текстов

Для организации хранения кластерных файлов требуется их разбиение на кластеры.

Методы кластеризации основаны на построении полной матрицы подобия текстов заданного пространства, в которой для каждой пары текстов D_i, D_j приводится коэффициент подобия S(D_i,D_j). Затем вводится некоторое пороговое значение коэффициента подобия Ŝ: если S(D_i,D_j)> Ŝ, тексты D_i, D_j включаются в кластер, иначе – не включаются.

4.4. Поиск релевантных текстов

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

4.4.1. Поиск в инвертированных файлах

Пусть есть пространство текстов размером n, каждый из которых характеризуется вектором V_i = {(t^k; w^k_i)}. Пусть запрос содержит множество ключевых слов (терминов): q = ({t^k_q}). Определим формально текст, релевантный запросу q, как такой текст ТБД, для которого коэффициент подобия с запросом отличен от нуля.

Для расчета коэффициента подобия запроса и текстов ТБД применяются вектора текстов и запроса. Определим вектор запроса V_q:

V_q = {(t^k_q; w^k_q)},

где t^k_q – термин запроса;

w^k_q - вес этого термина.

Тексты D_i характеризуются векторами V_i:

V_i = {(t^k; w^k_i)},

где t^k – термин вектора текста – индексационный термин;

w^k_i - вес этого термина:



Тогда при поиске релевантного текста (текстов) по запросу q рассчитываются коэффициенты подобия запроса и каждого из текстов ТБД:



После определения релевантных текстов возможны два подхода:

1. тексты упорядочиваются по убыванию релевантности, т.е. коэффициента подобия запросу, и предоставляются пользователю в таком упорядоченном виде;
   
2. вводится пороговый коэффициент подобия Ŝ: пользователю выдаются только те тексты ТБД, для которых подобие с запросом превышает пороговое значение.
   

4.5.2. Поиск при кластерной организации хранения

Пусть пространство текстов разбито на множество кластеров {C_l}, каждый из которых есть своё подпространство размером n_l текстов исходного пространства размером n текстов. При этом каждый кластер характеризуется профилем П_l и вектором V_l вида:

V_l = {(t_l^k, f_l^k)},

где {t_l^k} = , т.е. множество {t_l^k} индексационных терминов есть объединение индексационных терминов текстов кластера С_l,

, т.е. частоты терминов есть усредненные частоты терминов по текстам кластера.

Рассчитываются коэффициенты подобия S(q, C_l) запроса и кластера, представленного своим вектором:



где w_l^k – вес термина t^k в профиле кластера C_l;

Т_l – число индексационных терминов в профиле кластера С_l.

После определения релевантного кластера (его подобие с запросом отлично от нуля) поиск релевантного текста (текстов) выполняется внутри кластера.

4.5. Методы расширенного поиска

Часто при поиске в ТБД необходимо увеличить число релевантных текстов (в поисковых системах Интернет это называется расширенным поиском). Пространство релевантности увеличивается за счет дополнительных совпадений терминов запроса и индексационных терминов.

Для увеличения числа совпадений используются методы:

1. применение словаря синонимов (тезауруса), в котором термины сгруппированы в классы синонимии, или эквивалентности. Для построения тезауруса используют методы кластеризации элементов, в которых в качестве элементов выступают индексационные термины;
   
2. исключение из рассмотрения префиксной и постфиксной частей терминов и выделение их основ путем проведения морфологического анализа;
   
3. использование ассоциативного индексирования для приписывания терминам дополнительных терминов, которые ассоциируются с исходными;
   
4. вероятностное индексирование.
   

4.5.1. Построение словаря синонимов

Смысл этого метода сводится к тому, что с каждым термином t^k связывается множество его синонимов Syn^k. Образуется тезаурус. Тогда вектор запроса пополняется терминами из тезауруса, что расширяет число текстов, релевантных запросу.

Связь термина t^k с множеством Syn^k может быть представлена дополнительной графой справочника, в которой множество синонимов задано либо явно, либо списком номеров синонимичных терминов из того же справочника, например:

Термин tk	Синонимы Synk	Текст
		Ф1	Ф2	Ф3	Ф4
К1	К4	wФ1К1	wФ2К1	wФ3К1	wФ4К1
К2	-	wФ1К2	wФ2К2	wФ3К2	wФ4К2
К3	-	wФ1К3	wФ2К3	wФ3К3	wФ4К3
К4	К1	wФ1К4	wФ2К4	wФ3К4	wФ4К4

Тогда, например, если в запросе участвует термин К1, а его синонимом является термин К4, то запросу релевантны тексты, характеризующиеся как термином К1, т.е. Ф1, так и К4, т.е. Ф4.

При формировании тезауруса применяются рассмотренные выше для текстов методы кластеризации. Для этого каждый термин t^k представляется вектором V^k вида:

V^k = {(D_i, f_i^k)} или V^k = {(D_i, w_i^k)}.

Тогда для терминов t^k и t^r коэффициент подобия S(t^k,t^r) рассчитывается по формуле:



где p_i^r – параметр (частота или вес), характеризующий термин t^r в тексте D_i,

n – число текстов в наборе.

4.5.2. Ассоциативное индексирование терминов

Для каждого термина t^k находятся дополнительные термины, которые ассоциируются с исходным, - Ass^k. Тогда вектор запроса, аналогично предыдущему методу, пополняется дополнительными терминами. Это, очевидно, расширяет число релевантных запросу текстов. Связь термина t^k с множеством Ass^k может быть также представлена дополнительной графой справочника.

Для выявления ассоциируемых терминов строится матрица ассоциируемости, задающая для каждой пары терминов (t^k, t^r) показатель ассоциируемости a(k, r):



где f_i^k, f_i^r – частоты терминов t^k, t^r в тексте D_i.

Этот показатель принимает значения от 1 до 0: если он равен 1, то термины полностью ассоциируются, если равен 0, то никакой ассоциации между ними не существует. На практике для определения ассоциируемости вводится некоторое пороговое значение показателя â. Тогда термины ассоциируются, если для них показатель ассоциируемости превышает это пороговое значение.

4.5.3. Вероятностное индексирование терминов

Этот метод применяется при кластерной организации файлов, причем кластеры не должны пересекаться.

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

Вероятность p рассчитывается следующим образом:

p(t¹, t³,..., t^T’, C_l) = в*p(C_l)*p(C_l, t¹)*p(C_l, t³)*...*p(C_l, t^T’),

где р(C_l) - вероятность кластера C_l:

,

|D_i^Cl| - число текстов в кластере C_l,

n - число текстов во всех кластерах,

р(C_l, t^k) - вероятность того, что каждый текст из кластера C_l содержит термин t^k:

p(C_l, t^k) =

F_Cl^k – общее число терминов t^k в текстах кластера C_l,

F_Cl – общее число терминов в текстах кластера C_l,

Т’ - число терминов с ненулевым весом в векторе запроса,

в – константа, значение которой выбирается таким образом, чтобы выполнялось условие:

,

где С – общее число кластеров.