2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Задача о нахождении мин подмножеств термов в документе
Сообщение26.04.2011, 10:45 


30/03/11
5
Собственно условие задачи такое : есть словарь термов и есть набор документов, состоящих из этих термов. Предлагается составить такой список документов, в котором каждый документ состоит из минимального количества термов исходного документа и чтобы он однозначно идентифицировался в исходном множестве документов. То есть смысл задачи получается убрать из документов так называемый шум. Оговоримся, что нет таких двух документов один из которых являлся подмножеством другого( нет таких докуентов как A B и A B C D ).

Пример :

A B C D
B C E H
A B C G E

Результат должен быть
A D
H
G

Вот пока до чего я додумался :

1) Убираем стоп слова ( предлоги etc )
2) Переходим в векторную модель, преобразуем документы в матрицу термы-документы с мерой tf idf ( http://ru.wikipedia.org/wiki/TF-IDF )

дальше не совсем понятно, что с этой матрицей делать. Все вектор-столбцы нашей матрицы ( определяющие документ в нашем пространстве термов ) должны быть линейно-независимыми.

В какую сторону смотреть дальше?

 Профиль  
                  
 
 Re: Задача о нахождении мин подмножеств термов в документе
Сообщение27.04.2011, 12:39 
Аватара пользователя


14/05/05
224
Баку
DoTheTwist в сообщении #438766 писал(а):
Пример :

A B C D
B C E H
A B C G E

Результат должен быть
A D
H
G

А мне кажется, что результат должен быть:
D
H
G
Или я не так понял?

Если так, то из контекста получается пересечение всех множеств. А это - тривиальный алгоритм.

 Профиль  
                  
 
 Re: Задача о нахождении мин подмножеств термов в документе
Сообщение27.04.2011, 14:12 


30/03/11
5
Да, я ошибся : должно быть D.

Пересечение каких множеств?

 Профиль  
                  
 
 Re: Задача о нахождении мин подмножеств термов в документе
Сообщение27.04.2011, 15:33 
Аватара пользователя


14/05/05
224
Баку
Пардон, я не верно выразился в предыдущем посте. Не пересечение...

DoTheTwist в сообщении #439133 писал(а):
Пересечение каких множеств?

Ваши документы можно представить как множества терм:
$D_1 = \{A, B, C, D\}$
$D_2 = \{B, C, E, H\}$
$D_3 = \{A, B, C, G, E\}$

Результат работы алгоритма должен представлять из себя множество:
$E = \{D, H, G\}$

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

$E = \bigcup\limits_{i = 1}^n \{D_i - \bigcup\limits_{k =1, k \neq i}^n D_k\}$

где $n = 3$ в данном примере.

 Профиль  
                  
 
 Re: Задача о нахождении мин подмножеств термов в документе
Сообщение29.04.2011, 04:14 
Заслуженный участник


26/07/09
1559
Алматы
2Ринат
Учитывая, что
DoTheTwist писал(а):
составить такой список документов, в котором каждый документ состоит из минимального количества термов исходного документа

лучше просто определить $$E_i=D_i\setminus\bigcup_{k\neq i}D_k.$$

-- Пт апр 29, 2011 07:27:56 --

2DoTheTwist
Цитата:
дальше не совсем понятно, что с этой матрицей делать

Наверное, что-нибудь такое. Пример для $(0,\ 1)$-матрицы, в которой документы соответствуют строкам, а столбцы -- термам: просматриваем все столбцы (цикл по всем термам) и если в столбце больше одной единицы, то заполняем этот столбец нулями. Вот и всё.

А вообще, я пока вас не очень понял и боюсь ошибиться. :) Над tf-idf надо подумать.

 Профиль  
                  
 
 Re: Задача о нахождении мин подмножеств термов в документе
Сообщение29.04.2011, 18:38 
Аватара пользователя


17/04/11
658
Ukraine
Цитата:
$E = \bigcup\limits_{i = 1}^n \{D_i - \bigcup\limits_{k =1, k \neq i}^n D_k\}$

Перепишу это по-своему:
$D'_i = D_i - \bigcup\limits_{j\in I - \{i\}} D_j, D''_i\subseteq D'_i \land singleton(D''_i)$
$D''_i$ — это конечный результат. Я оставляю в $D'_i$ только один элемент. Меньше одного нельзя, поэтому это решение оптимальное. Доказательство правильности решения. Возьмём любой $i\in I, x\in D''_i$. Тогда
$x\in D'_i$
$\lnot (x\in \bigcup\limits_{j\in I - \{i\}} D_j)$
$\forall j\in I - \{i\}. \lnot (x\in D_j)$
$\forall j\in I - \{i\}. \lnot (D''_i\subseteq D_j)$
$D''_i$ однозначно идентифицирует $D_i$.

 Профиль  
                  
 
 Re: Задача о нахождении мин подмножеств термов в документе
Сообщение29.04.2011, 21:10 


28/04/11
6
Вы решаете для случая, когда в каждом документе обязательно найдется уникальный терм, но этого я не нашел в условии.

 Профиль  
                  
 
 Re: Задача о нахождении мин подмножеств термов в документе
Сообщение03.05.2011, 19:50 
Аватара пользователя


17/04/11
658
Ukraine
IgorVital в сообщении #440101 писал(а):
Вы решаете для случая, когда в каждом документе обязательно найдется уникальный терм, но этого я не нашел в условии.

В общем да, $D'_i$ может быть пустым.

 Профиль  
                  
 
 Re: Задача о нахождении мин подмножеств термов в документе
Сообщение03.05.2011, 21:57 
Аватара пользователя


17/04/11
658
Ukraine
Тогда такой вариант. $T$ — множество термов. Строим функцию $dm:T\to P(I)$, $dm(t)$ — множество индексов документов, которые содержат $t$. $\forall i\in I. C_i:=dm(D_i)$, каждый элемент $c\in C_i$ заменяем на какой-нибудь элемент $dm^{-1}(c)$ и получаем $D^A_i$, которое есть идентификатор документа с индексом $i$. Далее можно попытаться уменьшить $D^A_i$, просто перебирая подмножества и проверяя их на корректность.

Критерий, который задаёт корректное решение для документа с некоторым индексом $i\in I$, не зависит от решений для других документов, поэтому оптимальное решение для каждого $i\in I$ ищется независимо.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 9 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group