Частый майнинг поддеревьев

В информатике — это проблема поиска всех шаблонов в данной базе данных , частый анализ поддеревьев поддержка которых (метрика, связанная с количеством вхождений в другие поддеревья) превышает заданный порог. ^[1] Это более общая форма задачи о поддереве максимального согласия . ^[2]

Определение

Частый анализ поддеревьев — это проблема поиска всех шаблонов, «поддержка» которых превышает определенный уровень, указанный пользователем, где «поддержка» рассчитывается как количество деревьев в базе данных, которые имеют хотя бы одно поддерево изоморфное , заданный образец. ^[3]

Формальное определение

Проблема частого поиска поддеревьев была формально определена как: ^[1]

Учитывая пороговое значение minfreq , класс деревьев

{\mathcal {C}}

, транзитивное отношение поддерева

P\preceq T

между деревьями

P,T\in {\mathcal {C}}

, конечное множество деревьев

{\mathcal {D}}\subseteq {\mathcal {C}}

, частая проблема поиска поддеревьев — это проблема поиска всех деревьев

{\mathcal {P}}\subset {\mathcal {C}}

такое, что нет двух деревьев в

{\mathcal {P}}

изоморфны и

\forall P\in {\mathcal {P}}:\quad \mathrm {freq} (P,{\mathcal {D}})=\sum \nolimits _{T\in {\mathcal {D}}}d(P,T)\geq \mathrm {minfreq} ,

где

d

— антимонотонная функция такая, что если

P'\preceq P

затем

\forall T\in {\mathcal {C}}:\quad d(P',T)\geq d(P,T).

ДеревоМайнер

В 2002 году Мохаммед Дж. Заки представил TreeMiner, эффективный алгоритм для решения частых задач поиска поддеревьев, который использовал «список областей» для представления узлов дерева и который контрастировал с PatternMatcher, алгоритмом, основанным на сопоставлении с образцом. ^[4]

Определения

Индуцированные поддеревья

Поддерево $S=(V_{s},E_{s})$ является индуцированным поддеревом $T=(V,E)$ тогда и только тогда, когда $V_{s}\subseteq V$ и $E_{s}\subseteq E$ . Другими словами, любые два узла в S, которые напрямую соединены ребром, также напрямую соединены в T. Для любых узлов A и B в S, если узел A является родительским узлом B в S, то узел A также должен быть родитель узла B в T.

Встроенные поддеревья

Поддерево $S=(V_{s},E_{s})$ представляет собой встроенное поддерево $T=(V,E)$ тогда и только тогда, когда $V_{s}\subseteq V$ и два конечных узла любого ребра в S находятся на одном и том же пути от корня до листового узла в T. Другими словами, для любых узлов A и B в S, если узел A является родительским узлом B в S, то узел A должен быть предком узла B в T. Любые индуцированные поддеревья также являются вложенными поддеревьями, и, таким образом, концепция вложенных поддеревьев является обобщением индуцированных поддеревьев. Таким образом, встроенные поддеревья характеризуют скрытые закономерности в дереве, которые отсутствуют при традиционном индуцированном анализе поддеревьев. Поддерево размера k часто называют k-поддеревом.

Поддерживать

Поддержка поддерева — это количество деревьев в базе данных, содержащих это поддерево. Поддерево считается частым, если его поддержка не меньше заданного пользователем порога (часто обозначается как minsup). Цель TreeMiner — найти все встроенные поддеревья, имеющие хотя бы минимальную поддержку.

Строковое представление деревьев

Существует несколько различных способов кодирования древовидной структуры. TreeMiner использует строковые представления деревьев для эффективного манипулирования деревьями и поддержки подсчета. Изначально строка имеет значение $\varnothing$ . Начиная с корня дерева, метки узлов добавляются к строке в порядке поиска в глубину. -1 добавляется к строке всякий раз, когда процесс поиска возвращается от дочернего процесса к его родительскому. Например, простое двоичное дерево с корнем, обозначенным A, левым дочерним элементом, обозначенным B, и правым дочерним элементом, обозначенным C, может быть представлено строкой AB -1 C -1.

Класс эквивалентности префиксов

Говорят, что два k-поддерева принадлежат к одному и тому же классу префиксной эквивалентности, если их строковое представление идентично до (k-1)-го узла. Другими словами, все элементы в классе префиксной эквивалентности отличаются только последним узлом. Например, два дерева со строковым представлением AB-1 C-1 и AB-1 D-1 находятся в префиксном классе эквивалентности AB с элементами (C, 0) и (D,0). Элемент класса префикса определяется меткой узла в паре с индексом глубины, отсчитываемым от 0, узла, к которому он прикреплен. В этом примере оба элемента префиксного класса AB присоединяются к корню, имеющему индекс 0.

Объем

Область действия узла A задается парой чисел $[l,r]$ где l и r — минимальный и максимальный индекс узла в поддереве с корнем в A. Другими словами, l — индекс A, а r — индекс самого правого листа среди потомков A. Таким образом, индекс любого потомка A должен лежать в области видимости A, что будет очень полезным свойством при подсчете поддержки поддеревьев.

Алгоритм

Поколение кандидатов

Часто встречающиеся шаблоны поддеревьев обладают антимонотонным свойством. Другими словами, поддержка k-поддерева меньше или равна поддержке его (k-1)-поддеревьев. Только суперпаттерны известных частых паттернов могут быть частыми. Используя это свойство, кандидаты в k-поддеревья могут быть сгенерированы на основе частых (k-1)-поддеревьев посредством расширения класса префикса. Пусть C — класс префиксной эквивалентности с двумя элементами (x,i) и (y,j). Пусть C' будет классом, представляющим расширение элемента (x,i). Элементы C' добавляются путем выполнения операции соединения двух (k-1)-поддеревьев в C. Операция соединения (x,i) и (y,j) определяется следующим образом.

Если $i>j$ , затем добавьте (y,j) к C'.
Если $i=j$ , затем добавьте (y,j) и (y, ni) к C', где ni — индекс x в глубину в C
Если $i<j$ , ни один возможный элемент не может быть добавлен к C'

Эта операция повторяется для любых двух упорядоченных, но не обязательно различных элементов в C, чтобы создать расширенные префиксные классы k-поддеревьев.

Представление списка областей действия

TreeMiner выполняет генерацию кандидатов в глубину, используя представление поддеревьев в виде списка областей, чтобы ускорить подсчет поддержки. K-поддерево S может быть представлено тройкой (t,m,s), где t — идентификатор дерева, из которого происходит поддерево, m — метка соответствия префикса, а s — область действия последнего узла в S. В зависимости от того, как S встречается в разных деревьях базы данных, S может иметь различное представление в виде списка областей. TreeMiner определяет соединение списка областей , которое выполняет расширение класса для представления поддеревьев в виде списка областей. Два элемента (x,i) и (y,j) можно соединить, если существует два поддерева. $(t_{x},m_{x},s_{x})$ и $(t_{y},m_{y},s_{y})$ которые удовлетворяют любому из следующих условий.

Входящий тест: $t_{x}=t_{y},m_{x}=m_{y},s_{y}\subset s_{x}$ , что соответствует случаю, когда $i=j$ .
Выездной тест: $t_{x}=t_{y},m_{x}=m_{y},s_{y}>s_{x}$ , что соответствует случаю, когда $i>j$ .

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

Приложения

Домены, в которых полезен частый анализ поддеревьев, как правило, включают сложные отношения между объектами данных: например, анализ документов XML часто требует частого анализа поддеревьев. ^[1] Другой областью, где это полезно, является проблема анализа использования Интернета: поскольку действия, предпринимаемые пользователями при посещении веб-сайта, могут быть записаны и классифицированы разными способами, сложные базы данных деревьев необходимо анализировать с частым анализом поддеревьев. ^[4] Другие области, в которых полезен частый анализ поддеревьев, включают вычислительную биологию , ^[5]^[6] анализ структуры РНК, ^[6] распознавание образов, ^[7] биоинформатика, ^[8] и анализ базы данных KEGG GLYCAN. ^[9]

Проблемы

Проверка того, поддерживает ли шаблон (или транзакция) данный подграф, является NP-полной проблемой, поскольку это NP-полный экземпляр проблемы изоморфизма подграфа . ^[7] Более того, из-за комбинаторного взрыва , по словам Лей и др., «извлечение всех часто встречающихся шаблонов поддеревьев становится невозможным для большой и плотной базы данных деревьев». ^[10]

Ссылки

^ Jump up to: ^а ^б ^с Чи, Юн; Мунц, Ричард Р.; Нейссен, Зигфрид; Кок, Йост Н. (28 июня 2005 г.). «Частой анализ поддеревьев — обзор». Фундамента информатики . 66 : 161–198. S2CID 14827585 .
^ Дипак, Акшай; Фернандес-Бака, Давид; Тиртхапура, Шриканта; Сандерсон, Майкл Дж.; МакМахон, Мишель М. (июль 2013 г.). «EvoMiner: частый анализ поддеревьев в филогенетических базах данных» . Знания и информационные системы . 41 (3): 559–590. дои : 10.1007/s10115-013-0676-0 . S2CID 254145982 .
^ Дай, Х., Срикант, Р. и Чжан, К. (2004). « Достижения в области обнаружения знаний и интеллектуального анализа данных » . 8-я Тихоокеанско-Азиатская конференция, PAKDD 2004, Сидней, Австралия, 26–28 мая 2004 г., Материалы . 1-е изд. п. 65.
^ Jump up to: ^а ^б Заки, Мохаммед Дж. (2002). «Эффективная добыча частых деревьев в лесу» . Материалы восьмой международной конференции ACM SIGKDD по обнаружению знаний и интеллектуальному анализу данных . стр. 71–80. дои : 10.1145/775047.775058 . ISBN 978-1581135671 . S2CID 1649653 . Проверено 16 июня 2014 г.
^ Дипак, Акшай, Дэвид Фернандес-Бака, Шриканта Тиртхапура, Майкл Дж. Сандерсон и Мишель М. МакМахон. « EvoMiner: частый анализ поддеревьев в филогенетических базах данных ». Знания и информационные системы (2011): 1-32.
^ Jump up to: ^а ^б Чи, Юн, Йиронг Ян и Ричард Р. Мунц. « Канонические формы для помеченных деревьев и их применение при частом поиске поддеревьев ». Знания и информационные системы 8, вып. 2 (2005): 203–234.
^ Jump up to: ^а ^б Чи, Юн; Ян, Йиронг; Мунц, Ричард Р. (2004). «Извлечение деревьев с частыми корнями и свободных деревьев с использованием канонических форм» (PDF) . Знания и информационные системы . Проверено 16 июня 2014 г.
^ Сяо, Юнцяо; Яо, Дженк-Фунг; Ли, Чжиган; Данэм, Маргарет Х. (2003). «Эффективный интеллектуальный анализ данных для максимально частых поддеревьев». Третья международная конференция IEEE по интеллектуальному анализу данных . ICDM 2003. стр. 379–386. дои : 10.1109/ICDM.2003.1250943 .
^ Аоки-Киношита, Киёко Ф. (2009). Гликомная информатика: методы и приложения . ЦРК Пресс. п. 141. ИСБН 9781420083347 .
^ Цзоу, Лей; Лу, Яншэн; Чжан, Хуамин; Ху, Ронг (2006). «Анализ часто индуцированных шаблонов поддеревьев с ограничением поддерева». Шестая международная конференция IEEE по интеллектуальному анализу данных . Семинары ICDM, 2006 г., стр. 3–7. дои : 10.1109/ICDMW.2006.112 .

[Chi01-1] Jump up to: ^а ^б ^с Чи, Юн; Мунц, Ричард Р.; Нейссен, Зигфрид; Кок, Йост Н. (28 июня 2005 г.). «Частой анализ поддеревьев — обзор». Фундамента информатики . 66 : 161–198. S2CID 14827585 .

[2] Дипак, Акшай; Фернандес-Бака, Давид; Тиртхапура, Шриканта; Сандерсон, Майкл Дж.; МакМахон, Мишель М. (июль 2013 г.). «EvoMiner: частый анализ поддеревьев в филогенетических базах данных» . Знания и информационные системы . 41 (3): 559–590. дои : 10.1007/s10115-013-0676-0 . S2CID 254145982 .

[3] Дай, Х., Срикант, Р. и Чжан, К. (2004). « Достижения в области обнаружения знаний и интеллектуального анализа данных » . 8-я Тихоокеанско-Азиатская конференция, PAKDD 2004, Сидней, Австралия, 26–28 мая 2004 г., Материалы . 1-е изд. п. 65.

[:0-4] Jump up to: ^а ^б Заки, Мохаммед Дж. (2002). «Эффективная добыча частых деревьев в лесу» . Материалы восьмой международной конференции ACM SIGKDD по обнаружению знаний и интеллектуальному анализу данных . стр. 71–80. дои : 10.1145/775047.775058 . ISBN 978-1581135671 . S2CID 1649653 . Проверено 16 июня 2014 г.

[Dee13-5] Дипак, Акшай, Дэвид Фернандес-Бака, Шриканта Тиртхапура, Майкл Дж. Сандерсон и Мишель М. МакМахон. « EvoMiner: частый анализ поддеревьев в филогенетических базах данных ». Знания и информационные системы (2011): 1-32.

[Yun05-6] Jump up to: ^а ^б Чи, Юн, Йиронг Ян и Ричард Р. Мунц. « Канонические формы для помеченных деревьев и их применение при частом поиске поддеревьев ». Знания и информационные системы 8, вып. 2 (2005): 203–234.

[Chi04-7] Jump up to: ^а ^б Чи, Юн; Ян, Йиронг; Мунц, Ричард Р. (2004). «Извлечение деревьев с частыми корнями и свободных деревьев с использованием канонических форм» (PDF) . Знания и информационные системы . Проверено 16 июня 2014 г.

[Xia03-8] Сяо, Юнцяо; Яо, Дженк-Фунг; Ли, Чжиган; Данэм, Маргарет Х. (2003). «Эффективный интеллектуальный анализ данных для максимально частых поддеревьев». Третья международная конференция IEEE по интеллектуальному анализу данных . ICDM 2003. стр. 379–386. дои : 10.1109/ICDM.2003.1250943 .

[9] Аоки-Киношита, Киёко Ф. (2009). Гликомная информатика: методы и приложения . ЦРК Пресс. п. 141. ИСБН 9781420083347 .

[Zou06-10] Цзоу, Лей; Лу, Яншэн; Чжан, Хуамин; Ху, Ронг (2006). «Анализ часто индуцированных шаблонов поддеревьев с ограничением поддерева». Шестая международная конференция IEEE по интеллектуальному анализу данных . Семинары ICDM, 2006 г., стр. 3–7. дои : 10.1109/ICDMW.2006.112 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]