Диссертация (1137259), страница 5

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

Одним из первых методов по поиску частых подграфов является WARMR [62], основанный на индуктивном логическом программировании. За счёт большого числаскрытых проверок изоморфизма подграфов, данные метод являетсянеэффективным и на практике редко используется. Наиболее частоиспользуемыми методами являются FSG [67], MoFa [17], gSpan [128]и GASTON [90]. На различных выборках графовых данных было показано, что gSpan и GASTON, основанные на каноническом порождении следующего подграфа, являются наиболее эффективными, новыделить явного победителя среди них нельзя, и их производительность существенно зависит от выборки графов [125].gSpan начинают свою работу с одной вершины и затем последовательно расширяет уже найденные подграфы рёбрами, полагаясь наканонический код получаемых графов.

GASTON также используетканонический код подграфов при проверке допустимости расширения, но он состоит из трёх стадий. Задачей первой стадии являетсяпоиск всех частых путей выборки графов, на второй стадии находятся все частые деревья и, наконец на третей – все частые подграфы,содержащие циклы.Как правило, существует большое количество частых подграфов. Поэтому разработан ряд подходов, переформулирующих задачудля уменьшения множества получаемых закономерностей. Алгоритм25CloseGraph [127] является расширением gSpan.

Этот подход ищеттолько замкнутые графы, то есть такие графы, к которым невозможнодобавить ребро или вершины без изменения поддержки этого графав выборке. Подход FOGGER [137] является антиподом CloseGraph иищет минимальные генераторы – подграфы из которых нельзя убратьребро или вершину без изменения поддержки.Другим возможным путём для ограничения множества результатов являются подходы по поиску максимальных подграфов, то естьтаких подграфов, любое расширение которых не является частыми.Примерами являются MARGIN [112] и SPIN [51].Существует другая возможность уменьшить множество результирующих закономерностей, тем самым увеличив производительность системы и, возможно, снизив число ненужных закономерностей.

Пользователю можно предоставить возможность выбора ограничений, которые могут быть найдены методом. Несколько подходовбыли разработаны для того, чтобы напрямую вводить такие ограничения в процесс вычислений, а также для того, чтобы упроститьпользователю саму процедуру подбора этих ограничений [94; 139].Из-за большой вычислительной сложности подходов, получающих полный список всех частых подграфов даже с дополнительными ограничениями, возникло множество методов, получающих либо приблизительный результат, либо, так называемый, представительный результат, то есть некоторое подмножество всех возможныхзакономерностей, дающих общую картину возможных подграфов.Так один из первых подходов к анализу данных был именно таким(SUBDUE [26]). В нём авторы используют принцип минимальнойдлины описания и приблизительной проверкой изоморфизма подграфов.

Это даёт существенный вычислительный выигрыш, но тем неменее авторы утверждают, что подграфы получаемые таким образом,являются важными для исследуемых предметных областей.Другим эвристическим методом является подход LeapSearch [130], в котором авторы используют эвристическое отсечение ветвей пространства поиска.26Другим возможным подходом к уменьшению множества закономерностей является поиск представительного множества.

Так в работе [49] описывается подход, в которым получаются все подграфы, удовлетворяющие некоторому критерию. В частности, требуется,чтобы они были частыми и чтобы они были достаточно различными.Авторы предлагают метод случайных блужданий для решения этойзадачи. В своих следующих работах они делают равномерной вероятность получения подграфов различного вида [47; 48] на основемарковских цепей.Ещё одним интересным неполным методом, является алгоритмGAIA [56], основанный на генетических алгоритмах. Алгоритм выделяет определённое количество мест под результирующие подграфы. И затем задаёт функцию выживаемости подграфов от их классифицирующей способности. Это позволяет найти достаточно большиеподграфы, классифицирующие данную выборку.Общим недостатком всех методов анализа графов является ихнизкая производительность, что связано с необходимостью решения#P-полной задачи проверки изоморфизма графа подграфу.

Даже прииспользовании приближённых методов вычисления, подходы к анализу графов имеют высокую вычислительную сложность, и не могутбыть использованы для процессов с состояниями сложной структуры.1.6Методы оценки качества моделейКак мы увидели, графовые модели и модели последовательностейпорождают множество элементарных моделей, каждая из которых отражает только небольшую часть характеристик всего процесса, многие из них являются артефактами имеющихся данных и поэтомумножество элементарных моделей должно быть отфильтровано.

Длямоделей процессов такие критерии отбора развиты достаточно слабо.Даже для моделей бинарных признаков существует лишь несколькотаких подходов. В работе [140] приводится обзор подобных мер ка27чества. Часть этих мер относится к поиску ассоциативных правил.Такие меры не могут быть обобщены на последовательности, потому как в этом случае последовательность требуется представить какмножество независимых атрибутов. Другая группа критериев такжеосновывается на признаковом представлении закономерностей.

Онисмотрят распределение разбиений, получаемых при рассмотренииотдельных признаков. Другой подход приводится в работе [117], вкоторой авторы приводят меру качества рычага. Эта мера также опирается на признаковое представление, но является одним из лучшихдля определения важных элементарных моделей.Другая группа подходов приходит из анализа формальных понятий, где размер решётки формальных понятий может быть экспоненциальным по отношению к размеру контекста или узорной структуры.

Таким образом, появляется проблема выбора релевантных илинаиболее важных понятий. Для этого могут быть использованы различные меры качества понятий. В работе [13] авторы рассматривают несколько таких мер, основанных на предполагаемых механизмах функционирования человеческого мозга. Другой мерой являетсяустойчивость формального понятия, введённая в работе [75] и позжепересмотренная в работах [74; 77; 103]. Исследование устойчивости формального понятия и других мер качества проведены в работе [63].

Авторы данной работы экспериментально на случайных контекстах показали, что устойчивость более надёжна для зашумлённыхданных, чем вероятность и независимость – ещё две меры качества,исследуемых в [63].В этой работе мы полагаемся на устойчивость, которая в отличииот многих других сходных подходов может быть обобщена на случай процессов и других структурных данных. Тем не менее сравнение этой меры качества с другими методами для случая признаковыхмоделей представляется необходимым, для проверки её пригодностив задаче выделения важных закономерностей, которые будут составлять итоговую иерархическую модель.281.7ЗаключениеВ этой главе были рассмотрены различные модели, которые могут быть использованы для анализа процессов.

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

Наиболее близкимиподходами к моделирование требуемых процессов являются модели последовательностей. Действительно, некоторые модели последовательностей, могут быть адаптированы для наших данных, однакоих эффективность или качество не может удовлетворить требованиюпостроения модели за приемлемое время, тем не менее эти подходыследует иметь ввиду при разработке модели процессов с состояниями сложной структуры.В этой главе мы также увидели, что существует лишь несколькокритериев качества, позволяющие выделить важные элементарныемодели для построения небольшой, но значимой иерархической модели таких процессов.

Устойчивость – единственный критерий качества, который может быть применён к анализу последовательностейсо сложной структурой, который однако требуется сравнить с подходами для выделения закономерностей другого рода.29Глава 2Модель процессов с состояниями сложнойструктуры на основе узорных структур2.1ВведениеВ данной главе создаётся иерархическая модель процессов с состояниями сложной структуры на основе узорных структур и их проекций. Узорные структуры относятся к прикладной теории решёток.Решётки могут быть представлены как дискретный аналог численных значений: для любых двух элементов решётки можно найтиединственный минимальный элемент решётки больший двух данныхи единственный максимальный элемент, который меньше обоих элементов.Узорные структуры являются удобным подходом к моделирования сложных явлений, так как этот подход требует только того, чтобыэти явления можно было описать в рамках решётки.

Характеристики

Список файлов диссертации