Методы бикластеризации для анализа интернет-данных


Поиск сходства Интернет-документов с помощью частых замкнутых множеств признаков. - часть 3


Описание вычислительной модели

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

В рамках синтаксического подхода была реализована схема шинглирования и составление краткого образа (скетча) документов на основе методов «n минимальных элементов в перестановке» и «минимальные элементы в n перестановках», описание которых можно найти, например, в [21, 22].

Программа shingle с двумя параметрами length и offset порождает для каждого текста набор последовательностей слов (шинглов) длины length, так что отступ от начала одной последовательности до начала другой последовательности в тексте имеет размер offset. Полученное таким образом множество последовательностей хэшируется, так что каждая последовательность получает свой хэш-код.

Далее из множества хэш-кодов, соответствующему документу, выбирается подмножество фиксированного (с помощью параметра) размера с использованием случайных перестановок, описанных в работах [20, 21, 22]. При этом вероятность того, что минимальные элементы в перестановках хэш-кодов на множествах шинглов документов A и B (эти множества обозначаются через

и

соответственно) совпадут, равна мере сходства этих документов sim(A,B):

Основные определения, связанные с частыми замкнутыми множествами, естественно, даются в терминах анализа формальных понятий (ФАП) [33]. Мы рассматриваем формальный контекст

, где D — множество документов, а F — множество хеш-кодов (fingerprins), отношение

показывает, что некий объект

обладает признаком

в том и только том случае, когда

. Для множества документов

множество их общих признаков

служит описанием их сходства, а замкнутое множество

является кластером сходных объектов (с множеством общих признаков

). Для произвольного

величина

является поддержкой B и обозначается supp(B).

Нетрудно видеть, что множество

замкнуто тогда и только тогда, когда для любого

имеет место

. Именно это свойство используется для определения замкнутости в методах Data Mining.




Начало  Назад  Вперед



Книжный магазин