Вычисление частых замкнутых множеств признаков

Множество

называется

-частым, если

(то есть множество признаков B встречается в более чем

объектах), где

— параметр.

Вычисление частых замкнутых множеств признаков (содержаний) приобрело важность в Data Mining благодаря тому, что по этим множествам эффективно вычисляются множества всех ассоциативных правил [59]. Фактически, мы будем вычислять частные замкнутые множества признаков для контекста, дуального к

, т.е. находить такие множества документов-признаков контекста

, для которых размер множества их общих шинглов превышает заданный порог сходства.

Хотя теоретически размер множества всех замкнутых множеств признаков (содержаний) может быть экспоненциальным относительно числа признаков, на практике таблицы данных сильно "разрежены" (то есть среднее число признаков на один объект весьма мало), и число замкнутых множеств невелико. Для таких случаев существуют весьма эффективные алгоритмы построения всех наиболее частых замкнутых множеств признаков (см. также обзор по алгоритмам построения всех замкнутых множеств [47]).

В последние годы проводился ряд соревнований по быстродействию таких алгоритмов на серии международных семинаров под общим названием FIMI (Frequent Itemset Mining Implementations). Пока лидером по быстродействию считается алгоритм FPmax* [35], показавший наилучшие результаты по быстродействию в соревновании 2003 года. Мы использовали этот алгоритм для построения сходства документов и кластеров сходных документов. При этом в роли объектов выступали элементы описания (шинглы или слова), а в роли признаков — документы. Для такого представления «частыми замкнутыми множествами» являются замкнутые множества документов, для которых число общих единиц описания в образах документов превышает заданный порог.

Программная реализация и компьютерные эксперименты

Программные средства для проведения экспериментов в случае синтаксических методов включали следующие блоки:

парсер формата XML для коллекции ROMIP;

снятие html-разметки;

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

Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий