Logo Море(!) аналитической информации!
IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware
Обучение от Mail.Ru Group.
Онлайн-университет
для программистов с
гарантией трудоустройства.
Набор открыт!
2008 г.

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

Дмитрий Игнатов,
кафедра анализа данных и искусственного интеллекта ГУ-ВШЭ

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

2.3.2. Алгоритм DR-miner

Все семейство бимножеств, упорядоченное по отношению , образует решетку с нижним элементом и верхним элементом . Обозначим через множество подрешеток из , , такие что и , где первая компонента бимножество являющееся нижним элементом, а вторая — верхним элементом. Алгоритм DR-miner использует такие решетки в качестве поискового пространства; основными этапами такого поиска являются перечисление (enumeration), отсечение (pruning) и распространение (propagation).

Алгоритм DR-miner начинает работу с полной решетки и затем рекурсивно распространяет ограничения, используя функцию Prop. Далее проверяется соответсвие полученной подрешетки введенным ограничениям посредством функции Prune, и порождаются две новых подрешетки, благодаря функции Enum (см. Алгоритм 2.3.1).

Процедура Enumeration. Пусть таким образом, где или . Пусть функция возвращает один элемент , содержащий наибольшее число нулей на , если , или на , если . Благодаря этой функции достигается увеличение эффективности распространения ограничений посредством уменьшения пространства поиска (в том случае, если это возможно).

Процедура Pruning. Подрешетка более не рассматривается, если среди ее бимножеств нет удовлетворяющих ограничениям. Пусть функция возвращает тогда и только тогда, когда монотонному ограничению (по отношению ) удовлетворяет верхний элемент подрешетки: .

Пусть функция возвращает тогда и только тогда, когда aнтимонотонному ограничению (по отношению ) удовлетворяет нижний элемент подрешетки: .

Антимонотонное ограничение используется в качестве . Однако не является ни монотонным, ни антимонотонным ограничением. применяется для того, чтобы элементы, не принадлежащие подрешетке (т.е., те элементы, которые могут быть включены в бимножества), могли содержать больше нулей на верхнем элементе, чем внутренние, принадлежащие нижнему элементу (элементы принадлежащие каждому бимножеству). Пусть функция определяется следующим образом:

   

В алгоритме DR-Miner используется функция , определённая так.

Процедура Propagation. и могут быть использованы для уменьшения размера подрешетки посредством перемещения объектов из в или вне . Для этого используются функции и :

   

, определяемая как , рекурсивно применяется к подрешетке до тех пор, пока результат не перестанет изменяться. Подрешетка называется листом, когда она содержит только одно бимножество, т.е. . DR-бимножества являются такими максимальными бимножествами. В статье [19] доказывается корректность и полнота алгоритма.

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

Новости мира IT:

Архив новостей

Последние комментарии:

Релиз ядра Linux 4.14  (6)
Пятница 17.11, 16:12
Apple запустила Pay Cash (2)
Четверг 09.11, 21:15
Loading

IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware

Информация для рекламодателей PR-акции, размещение рекламы — adv@citforum.ru,
тел. +7 985 1945361
Пресс-релизы — pr@citforum.ru
Обратная связь
Информация для авторов
Rambler's Top100 TopList liveinternet.ru: показано число просмотров за 24 часа, посетителей за 24 часа и за сегодня This Web server launched on February 24, 1997
Copyright © 1997-2000 CIT, © 2001-2015 CIT Forum
Внимание! Любой из материалов, опубликованных на этом сервере, не может быть воспроизведен в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Подробнее...