Описание вычислительной модели
Оператор '' (двукратное применение оператора ') является оператором замыкания: он идемпотентен (A'''' = A''), монотонен (A B влечет A'' B'') и экстенсивен (A A ''). Множество объектов A G, такое, что A'' = A, называется замкнутым. Аналогично для замкнутых множеств признаков — подмножеств множества M. Пара множеств (A, B), таких, что A G, B M, A' = B и B' = A, называется формальным понятием… Читать ещё >
Описание вычислительной модели (реферат, курсовая, диплом, контрольная)
В качестве методов представления документов (создания образа документа) мы использовали стандартные синтаксические и лексические подходы с разными параметрами.
В рамках синтаксического подхода была реализована схема шинглирования и составление краткого образа (скетча) документов на основе методов «n минимальных элементов в перестановке» и «минимальные элементы в n перестановках», описание, которое можно найти, например, в [Broder et al 1998, Broder 2000]. Программа shingle с двумя параметрами length и offset порождает для каждого текста набор последовательностей слов (шинглов) длины length, так что отступ от начала одной последовательности до начала другой последовательности в тексте имеет размер offset. Полученное таким образом множество последовательностей хэшируется, так что каждая последовательность получает свой хэш-код.
Далее из множества хэш-кодов, соответствующему документу, выбирается подмножество фиксированного (с помощью параметра) размера с использованием случайных перестановок, описанных в работах [Broder 1997, Broder et al 1998, Broder 2000]. При этом вероятность того, что минимальные элементы в перестановках хэш-кодов на множествах шинглов документов A и B (эти множества обозначаются через и, соответственно) совпадут, равна мере сходства этих документов sim (A, B):
Основные определения, связанные с частыми замкнутыми множествами, естественно даются в терминах анализа формальных понятий (АФП) [Ganter et al, 1999]. Контекстом в АФП называют тройку K = (G, M, I), где G — множество объектов, M — множество признаков, а отношение I G M говорит о том, какие объекты какими признаками обладают. Для произвольных A G и B M определены операторы Галуа:
A' = {m M | g A (g I m)};
B' = {g G | m B (g I m)}.
Оператор '' (двукратное применение оператора ') является оператором замыкания: он идемпотентен (A'''' = A''), монотонен (A B влечет A'' B'') и экстенсивен (A A ''). Множество объектов A G, такое, что A'' = A, называется замкнутым. Аналогично для замкнутых множеств признаков — подмножеств множества M. Пара множеств (A, B), таких, что A G, B M, A' = B и B' = A, называется формальным понятием контекста K. Множества A и B замкнуты и называются объемом и содержанием формального понятия (A, B) соответственно. Для множества объектов A множество их общих признаков A' служит описанием сходства объектов из множества A, а замкнутое множество A'' является кластером сходных объектов (с множеством общих признаков A'). Для произвольного B M величина |B'| = |{g G | m B (g I m)}| называется поддержкой (support) B и обозначается sup (B). Нетрудно видеть, что множество B замкнуто тогда и только тогда когда для любого D B имеет место sup (D) k (то есть множество признаков B встречается в более чем k объектах), где k — параметр. Вычисление частых замкнутых множеств признаков (содержаний) приобрело важность в Data Mining благодаря тому, что по этим множествам эффективно вычисляются множества всех ассоциативных правил [Pasquier et al, 1999].
Хотя теоретически размер множества всех замкнутых множеств признаков (содержаний) может быть экспоненциальным относительно числа признаков, на практике, таблицы данных сильно «разрежены» (то есть среднее число признаков на один объект весьма мало) и число замкнутых множеств невелико. Для таких случаев существуют весьма эффективные алгоритмы построения всех наиболее частых замкнутых множеств признаков (см. также наш обзор по алгоритмам построения всех замкнутых множеств [Kuznetsov et al, 2002]). В последние годы проводился ряд соревнований по быстродействию таких алгоритмов на серии международных семинаров под общим названием FIMI (Frequent Itemset Mining Implementations). Пока лидером по быстродействию считается алгоритм FPmax* [Grahne, 2003], показавший наилучшие результаты по быстродействию в соревновании 2003 года. Мы использовали этот алгоритм для построения сходства документов и кластеров сходных документов. При этом в роли объектов выступали элементы описания (шинглы или слова), а в роли признаков — документы. Для такого представления «частыми замкнутыми множествами» являются замкнутые множества документов, для которых число общих единиц описания в образах документов превышает заданный порог.