Диссертация (1137259), страница 4
Текст из файла (страница 4)
Данный способ, является классическим способом представления данных и берёт своё начало из анализа объектно-признаковыхтранзакций [8].Другим форматом хранения последовательностей является вертикальное представление – способ представления данных о последовательностях, в котором для каждого или некоторых структурных элементов в данных задаётся список тех объектов, описание которыхвключает данный структурный элемент. При таком способе представления данных требуется лишь однократный проход по выборке19данных, после чего их представление в памяти больше не требуетобращения к выборке. Авторы многих работ показывают, что такоепредставления является более эффективным, чем горизонтальное, ипозволяет быстрее рассчитывать поддержку найденных закономерностей [25; 88; 132; 135].Например, для вертикального представления выборки последовательностей, в которых каждый элемент (каждое состояние) являетсяподмножеством множества базовых элементов, для каждого базового элемента сохраняются все объекты и все позиции, в которых этотэлемент встречается [135].Одним из первых алгоритмов с вертикальным представлениемпоследовательностей является SPADE и его модификации [133–135].Так cSPADE позволяет вводить пользовательские ограничения в процесс поиска.
Основным отличием таких подходов от горизонтальныхметодов (помимо представления данных) является обход пространства поиска в глубину. Что позволяет существенно снизить требования к ресурсам вычислительной системы. Подход CCSM [93] улучшает SPADE путём добавления в него механизма кэширования, чтосущественно повышает его быстродействие.Алгоритмы схожие с принципом работы с Apriori имеют одинсущественный недостаток – они должны порождать большое количество кандидатов для перехода на следующий уровень.
В связи сэтим также разрабатывались алгоритмы, порождающие новых кандидатов в закономерности монотонным расширением имеющихся закономерностей. В этом случае нет необходимости хранить все закономерностей какого-либо уровня, что также уменьшает требования ксистеме. FP-Growth [44] стал первым из таких подходов. Расширениями этого подхода стали алгоритмы FreeSpan [45] и PrefxSpan [96], вкоторых процесс порождения и хранения последовательностей основан на суффиксных деревьях, что существенно повышает производительность системы.
Продолжением этих подходов стал алгоритмCloSpan [129]. Этот алгоритм существенно повышает производительность всех предыдущих подходов и является одним из самых эф20фективных на сегодняшний день. Это достигается тем, что авторыподхода ищут только замкнутые закономерности, что существенноуменьшает пространства поиска и результата без потери качества.Основным недостатком всех рассмотренных до сих пор подходов является ограниченность языка последовательностей.
В основным подходы описывают одно состоянии или один элемент последовательности множеством атрибутов, что усложняет моделированиепроцессов с состояниями сложной структуры. Для работы с болеесложными языками последовательностей последовательно разрабатываются подходы [33; 100; 99]. Рассмотрим эти подходы подробнее, так как они одни из немногих подходов, которые могут быть использованы при моделировании процессов с состояниями сложнойструктуры.Работа [99] усовершенствует предыдущую работу авторов [100].В этом подходе закономерности задаются языком последовательности, в которых каждое состояние описывается несколькими компонентами. При этом для каждой компоненты могут быть заданы таксономии. Основная идея подхода состоит в том, чтобы переписатьданные в формате пригодном для классических методов анализа последовательностей, таких как CloSpan [129].
Это делается в два этапа. На первом этапе авторы находят частые состояния. Пусть естьсостояние (1 , 2 , · · · , ), где – это элемент таксономии . Из множества всех возможных состояний 1 × · · · × выделяются максимальные частые состояния, то есть такие состояния, что любая ихспецификация не частая, но при этом сами они являются частыми поотношении к некоторому порогу по поддержке. Таким образом, этомножество максимальных частых состояний сильно зависит от порога по поддержке, что затрудняет использование этого метода, так кактребует очень тщательного подбора этого порога.
Затем каждая последовательность перекодируется таким образом, что каждое состояние в ней заменяется на множество максимальных частых состояний,являющихся обобщением этого состояния согласно таксономиям. Вэтом случае мы получили последовательность, в которой каждое со21стояние задаётся множеством признаков, что позволяет применятьстандартные алгоритмы анализа последовательностей.Дальнейшим расширением этого метода является подход [33], вкотором авторы добавляют возможность использования множествапризнаков в нескольких компонентах состояния.
В этом случае вдекартово произведение состояний добавляется также и множествопризнаков, что не сильно меняет основную идею подхода. В статьеавторы также пытаются уйти от максимальных частых состояний, ипоказывают, что это может быть сделано в некоторых случаях, но чтосущественно усложняет вычисления.
Эти подходы могут быть применены для анализа процессов с состояниями сложной структуры,но как мы увидим в последствии могут обработать лишь некоторыечастные случаи таких процессов. В общем виде для таких процессовэти подходы не всегда могут закончить вычисления.Анализ временных рядовРассмотрим отдельно некоторые подходы к анализу временныхрядов. Эта задача была впервые сформулирована Манила [83].
В этойработе авторы вводят алгоритм WINEPI. Позднее они разрабатываюталгоритм MINEPI [82]. В своих работах авторы обрабатывают потокданных, выделяя в нём частые эпизоды – последовательности ограниченной длины. Позднее в работе [52] этот подход усовершенствуется и вводятся дополнительные ограничения на получаемые эпизоды.Среди такого рода эпизодов часто встречаются неинтересные, поэтому далее разрабатывается подход к поиску только тех эпизодов,которые приводят к определённым событиям [110]. Недавно появился подход для анализа временных рядов посредством обучения декларативных языков [5]. Все подходы анализа временных рядов рассматривают только относительно простые последовательности, ключевым моментом которых является поиск эпизодов в одной большойпоследовательности, поэтому они не могут быть использованы дляанализа процессов с состояниями сложной структуры.221.5Графовые моделиВ данном подразделе будут описаны методы анализа структурныхданных, представленных графами, которые могут быть использованы для представления процессов с состояниями сложной структуры.Полные обзоры таких методов могут быть найдены в [19; 29; 54;65].
В таких подходах элементарными моделями структурного объекта, описываемого этими данными, или закономерностями являются множества подграфов. В частности таким структурным объектомможет быть процесс с состояниями сложной структуры.Большинство из методов анализа данных, представленных графами, используют горизонтальное представление данных. Это связано с тем, что вертикальное представление требует возможности упорядочить определённые элементы, из которых можно будет собрать любые допустимые графы.
Здесь мы отметим теструктуры данных, которые используются в отдельных подходахи играют важную роль для эффективности алгоритма. Алгоритмы SUBDUE [26], HSIGRAM [68] и FFSM [50] используют матрицу смежности. WARMR [62] основан на формулах пролога.Kuramochi [67], gSpan [128] и CloseGraph [127] полагаются всвоей работе на список рёбер, также используются хеш-таблицы(Gaston [90]) и сито (FARMER [91]). Некоторые алгоритмы, например GREW [69], могут работать с различными представлениями графов в зависимости от предпочтений пользователя.Следующая важная особенность алгоритмов анализа графовыхданных определяется языком закономерностей, который задаёт всёмножество возможных закономерностей, которые могут быть найдены в любой выборке данных определённого типа. Например, мы можем ограничить ищем ли мы все подграфы, либо только подграфы сопределённым числом вершин, либо подграфы определённого типа,например, только пути или только деревья.
Ряд методов, анализирующие графовые данные, могут возвращать множество подграфоввместо одного. Например, при исследовании множества молекул, за23кономерностью может быть множество встречающихся в них функцилнальных групп.Ограничения закономерностей задают множество допустимых закономерностей из всего множества задаваемых языком закономерностей. Основное отличие ограничений от языка закономерностейсостоит в том, что язык не зависит от конкретной выборки данных, и таким образом, является более общей характеристикой тогоили иного метода, чем ограничения.
Ограничениями может являтьсяподдержка закономерности, то есть количество объектов, в которыхвстречается та или иная закономерность в данной выборке. Здесь вкачестве ограничений мы рассматриваем только ограничения, которые позволяют ускорить вычисления. Все другие ограничения относятся к фильтрации результата путём поиска “важных” закономерностей, что будет описано в разделе 1.6.Язык закономерностей и ограничения задают то множество закономерностей, которое должно быть получено тем или иным методоманализа сложноструктурированных данных.С точки зрения языка получаемых закономерностей прежде всеговыделяются закономерности, состоящие из одного, двух или нескольких подграфов, что уже было отмечено выше. Также существует рядособых языков, представленных далее:∙ Всевозможные одиночные подграфы [17; 18; 49; 47; 48; 56; 62;67; 90; 94; 98; 97; 101; 107; 112; 130; 127; 128; 139];∙ Множества всех возможных подграфов [40; 57; 71; 72; 76; 80;106];∙ Разнообразные проекции (в терминах работы [40]):– Подграфы с не более чем k вершинами [72];– Внешне-планарные графы [105].
Такой подход позволилавторам работы понизить сложность операции изоморфизма графов до полиномиального;24С точки зрения дополнительных ограничений часто используетсяособое поведение закономерностей для задач классификации, то естьтакие закономерности, которые могут быть использованы для отличия положительной от отрицательной выборок [15; 29; 40; 47; 57;72; 76; 78; 80; 86; 98; 101]. Также часто накладывается ограничениязамкнутости подграфов [40; 55; 71; 72; 76; 127; 136] или его максимальности [51; 112]. Особый интерес представляют подходы длязаданий ограничений, определяемых пользователем [94; 107; 108].Большинство методов по анализу данных, представленных графами, решают задачу поиска частых подграфов или их множеств (тоесть подграфов с ограничением по поддержке) с дополнительнымиограничениями на тип подграфов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
