2014 dxdy logo

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

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




 
 Задача о нахождении мин подмножеств термов в документе
Сообщение26.04.2011, 10:45 
Собственно условие задачи такое : есть словарь термов и есть набор документов, состоящих из этих термов. Предлагается составить такой список документов, в котором каждый документ состоит из минимального количества термов исходного документа и чтобы он однозначно идентифицировался в исходном множестве документов. То есть смысл задачи получается убрать из документов так называемый шум. Оговоримся, что нет таких двух документов один из которых являлся подмножеством другого( нет таких докуентов как 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 
Аватара пользователя
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 
Да, я ошибся : должно быть D.

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

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

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 
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 
Аватара пользователя
Цитата:
$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 
Вы решаете для случая, когда в каждом документе обязательно найдется уникальный терм, но этого я не нашел в условии.

 
 
 
 Re: Задача о нахождении мин подмножеств термов в документе
Сообщение03.05.2011, 19:50 
Аватара пользователя
IgorVital в сообщении #440101 писал(а):
Вы решаете для случая, когда в каждом документе обязательно найдется уникальный терм, но этого я не нашел в условии.

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

 
 
 
 Re: Задача о нахождении мин подмножеств термов в документе
Сообщение03.05.2011, 21:57 
Аватара пользователя
Тогда такой вариант. $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 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group