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


         

В качестве методов представления документов


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

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

В рамках синтаксического подхода была реализована схема шинглирования и составление краткого образа (скетча) документов на основе методов «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.


Содержание  Назад  Вперед