Задача о нахождении мин подмножеств термов в документе

[DoTheTwist]

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

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

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

[Ринат]

DoTheTwist в сообщении #438766 писал(а):

Пример :

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

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

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

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

[DoTheTwist]

Да, я ошибся : должно быть D.

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

[Ринат]

Пардон, я не верно выразился в предыдущем посте. Не пересечение...

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$ в данном примере.

[Circiter]

2Ринат
Учитывая, что

DoTheTwist писал(а):

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

лучше просто определить

$$E_i=D_i\setminus\bigcup_{k\neq i}D_k.$$

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

2DoTheTwist

Цитата:

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

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

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

[beroal]

Цитата:

$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$.

[IgorVital]

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

[beroal]

IgorVital в сообщении #440101 писал(а):

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

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

[beroal]

Тогда такой вариант. $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$ ищется независимо.