Автореферат (Модели, алгоритмы и программные средства бикластеризации на основе замкнутых множеств), страница 3

Бикластер есть подматрица матрицы10 вида = (, ), такая, что ее строки проявляют “сходное поведение” настолбцах, а столбцы – на признаках.В рамках представленных в работе моделей требования, предъявляемыек понятию бикластера, различаются, а потому формальные определения даются нами только для конкретных случаев. Задача, которую решает алгоритмбикластеризации, заключается в нахождении такого множества бикластеровℬ = { = ( , )}, которое удовлетворяет некоторым формально определенным требованиям однородности. Словосочетания “сходное поведение” и“требования однородности” раскрываются в разделе, дающем определения типов бикластеров.Приведем основные определения АФП.

Пусть и суть множества,называемые соответственно множествами объектов и признаков, а ⊆ ×— отношение. Для ∈ , ∈ имеет место если объект обладаетпризнаком . Тройка K = (, , ) называется формальным контекстом.Для произвольных ⊆ и ⊆ соответствие Галуа определяется следующей парой отображений:′ := { ∈ | для всех ∈ }, ′ := { ∈ | для всех ∈ }.Пара множеств (, ) таких, что ⊆ , ⊆ , ′ = и ′ = называется формальным понятием контекста с (формальным) объёмом и (формальным) содержанием .Множество всех понятий формального контекста образует решётку(обозначаемую через B()) со следующими операциями:⋀︁⋂︁⋂︁⋁︁⋂︁⋂︁′′( , ) = ( , ( ) ),( , ) = (( ) , ).∈∈∈∈∈∈По основной теореме АФП любая полная решётка изоморфна решёткепонятий некоторого формального контекста. В качестве объектов этого контекста можно, например, выбрать ∧-неразложимые элементы, а в качествепризнаков — ∨-неразложимые элементы исходной решётки.Многозначный формальный контекст есть четвёрка (, , , ), где, , — множества (объектов, признаков и значений признаков, соответственно), а — тернарное отношение ⊆ × × , задающее значение признака , причём:(, , ) ∈ и (, , ) ∈ влечёт = Процедура сведения многозначных контекстов к однозначным называется шкалированием (scaling).

Для шкалирования каждый признак многозначного контекста представляется формальным контекстом, называемым шкалой.В этой же главе описываются типы бикластеров, их структура. Приводится классификация методов бикластеризации, предложенная в работеS. Madeira, по которой автором строится их решеточная таксономия и предлагается ее пополнение методами, основанными на идее применения замкнутыхмножеств.11Задача поиска частых множеств признаков (frequent itemsets mining) является одной из центральных тем в Data Mining. Первоначально, необходимость поиска частых множеств признаков возникла при выявлении часто покупаемых вместе товаров.

Среди частых множеств признаков выделяют такназываемые частые замкнутые множества признаков, которые полезны дляих более компактного представления. Такое представление осуществляетсябез потерь информации о поддержке собственных частых подмножеств данных частых замкнутых множеств признаков. Хорошо известным фактом дляспециалистов по разработке данных является то, что все замкнутые частыемножества признаков (т.е. при = 0) образуют решетку, эта решетка изоморфна решетке понятий контекста для соответствующей базы данных(см., например, работы M.

Zaki).Пусть дан формальный контекст K = (, , ). Множество признаков ⊆ называется частым множеством признаков, если | ′ | ≥ , где — заданный числовой порог ≥ 0. Ключевым понятием для данной задачи являетсяподдержка. Поддержкой множества признаков ⊆ называется величина′|() = ||| . Значение () показывает, какая доля объектов содержит . Часто поддержку выражают в %. Если задано значение минимальнойподдержки _, то определение частого множества признаков можнопереписать следующим образом.

Множество признаков ⊆ называетсячастым множеством признаков если ( ) ≥ _. Для контекстаK = (, , ) частое множество признаков ⊆ называется частым замкнутым множеством признаков, если не существует , такого что ⊃ и ( ) = ( ). Используя оператор замыкания, можно дать следующее эквивалентное определение. Множество признаков ⊆ называетсячастым замкнутым множеством признаков, если ( ) ≥ _ и ′′ = .

Частое множество признаков ⊆ называется максимальным частым множеством признаков, если не существует частого множествапризнаков , такого что ⊃ . Пусть — множество всех частых множеств признаков, — множество всех частых замкнутых множеств признаков, а — множество всех максимальных частых множеств признаков.Тогда, очевидно, выполнено следующее соотношение ⊆ ⊆ .Максимальные множества признаков хотя и не позволяют вычислитьподдержку всех частых множеств признаков, но являются более компактнымпредставлением чем FCI и FI. Применение MFI оправдано для плотных контекстов, в то время как поиск всех частых множеств признаков оказываетсяневозможным.В данной главе приводятся примеры основных задач, которые успешно решаются с помощью бикластеризации, и дается обзор соответствующихпрограммных средств, большая часть которых создана учеными и находитсяв свободном доступе в сети Интернет.Традиционные методы кластеризации предлагают разнообразный наборсредств для решения задач группировки объектов с учетом их сходства в самых разных предметных областях.

Однако эти методы имеют ряд недостатков.Например, метод K-means требует знания количества кластеров в качестве па-12раметра, адекватный выбор которого – задача аналитика. Результаты работынекоторых методов кластеризации зависят от порядка рассмотрения объектовисходной выборки.

Как правило, методы кластеризации разбивают объектына группы, но не отвечают на вопрос, в чем заключается сходство сгруппированных в один кластер объектов. Если исходные данные представлены ввиде объектно-признаковой таблицы, то под кластером понимается множество строк (столбцов) такой таблицы, при этом сходство рассчитывается повсем значениям, записанным в такой строке или столбце, хотя реально у таких строк (столбцов) могут быть похожими только некоторые подмножествапризнаков (объектов). Отметим тот факт, что идея бикластеризации хорошовписывается в парадигму кластер-анализа, являясь естественным расширением идей кластеризации по подпространству (только по части признаков висходной объектно-признаковой таблице), описанных в работах R.

Agrawal’я исовместной кластеризации по строкам и столбцам, предложенной I. Dhillon’ом.Говоря о бикластеризации стоит заметить, что в данной работе мы имеем дело в основном с бинарными данными {0, 1}-типа и не рассматриваютсяметоды бикластеризации, работающие на данных с вещественными значениями (такими как интервалы), на графовых моделях в качестве признаков илиописаний.

Тем не менее, нами приводится классификация (таксономия) такихметодов.Во второй главе рассматриваются три прикладные задачи, успешно решенные автором с помощью предложенных им математических моделей наоснове бикластеризации с применением замкнутых множеств признаков, АФПи ассоциативных правил.Поиск сходства текстовых документов с помощью частых замкнутыхОгромное число документов (по некоторым источникамдо 30 %) в Интернете имеют дубликаты, в связи с чем поисковые машиныдолжны обладать эффективными средствами вычисления кластеров дубликатов. Наличие таких средств позволяет существенно сократить объем необходимых для решения задачи вычислительных и аппаратных ресурсов предприятия. Происхождение дубликатов может быть разным – от дублированиякомпаниями собственной информации на разных серверах (создание зеркал)до злонамеренных – обмана программ индексаторов веб-сайтов, незаконного копирования и спамерских рассылок. В данной работе мы рассматриваемсходство не как отношение на множестве документов, а как операцию, сопоставляющую двум документам множество общих элементов их сокращенныхописаний, в виде синтаксических единиц.

Кластер дубликатов определяетсякак множество документов, у которых число общих элементов описания превышает определенный порог. Одной из задач проекта было связать вычисление попарного сходства образов документов с построением кластеров документов, так чтобы, с одной стороны, получаемые кластеры были бы независимыот порядка рассмотрения документов (в отличие от методов кластерного анализа), а с другой стороны гарантировали бы наличие реального попарногосходства всех образов документов в кластере. В рамках синтаксического под-множеств признаков.13хода была реализована схема шинглирования и составление краткого образа(скетча) документов на основе методов “n минимальных элементов в перестановке” и “минимальные элементы в n перестановках”, описание которогоможно найти, например, в [A.

Broder, 1998, 2000]. Шинглирование осуществляется с двумя параметрами ℎ и и позволяет порождать для каждого текста набор последовательностей слов или символов (шинглов) длиныlength, так что отступ от начала одной последовательности до начала другойпоследовательности в тексте имеет размер .

Полученное таким образоммножество последовательностей хэшируется, так что каждая последовательность получает свой хэш-код. Далее из множества хэш-кодов, соответствующему документу, выбирается подмножество фиксированного (с помощью параметра) размера с использованием случайных перестановок, описанных вработах [A. Broder, 1997, 1998, 2000]. При этом вероятность того, что минимальные элементы в перестановках хэш-кодов на множествах шинглов документов и (эти множества обозначаются через и , соответственно)совпадут, равна мере сходства этих документов (, ): [{( )} = {( )}] =| ∩ |= (, )| ∪ |Опишем предлагаемую нами модель.

Мы рассматриваем формальныйконтекст K = (, , ), где – множество документов, а – множествохеш-кодов (fingerprins), отношение показывает, что некий объект обладает признаком в том и только том случае, когда . Для множествадокументов ⊆ множество их общих признаков ′ служит описанием ихсходства, а замкнутое множество ′′ является кластером сходных объектов(с множеством общих признаков ′ ). Для произвольного ⊆ величина| ′ | = |{ ∈ |∀ ∈ ()}| является поддержкой и обозначается(). Нетрудно видеть, что множество замкнуто тогда и только тогда,когда для любого ⊃ имеет место () < ().