Частая добыча поддерева - Frequent subtree mining - Wikipedia

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

Определение

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

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

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

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

{ Displaystyle { mathcal {C}}}

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

{ Displaystyle P prevq T}

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

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

, конечный набор деревьев

{ Displaystyle { mathcal {D}} substeq { mathcal {C}}}

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

{ Displaystyle { mathcal {P}} subset { mathcal {C}}}

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

{ displaystyle { mathcal {P}}}

изоморфны и

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

куда

d

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

{ Displaystyle P ' prevq P}

тогда

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

TreeMiner

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

Определения

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

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

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

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

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

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

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

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

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

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

Объем

Объем узла A задается парой чисел ${ Displaystyle [л, г]}$ где 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) определяется следующим образом.

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

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

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

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

Тест в объеме: ${ displaystyle t_ {x} = t_ {y}, m_ {x} = m_ {y}, s_ {y} subset s_ {x}}$ , что соответствует случаю, когда ${ displaystyle i = j}$ .
Тест вне объема: ${ displaystyle t_ {x} = t_ {y}, m_ {x} = m_ {y}, s_ {y}> s_ {x}}$ , которые соответствуют случаю, когда ${ displaystyle i> j}$ .

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

Приложения

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

Вызовы

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

Рекомендации

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

[Chi01-1] а ^б ^c Чи, Юнь; Muntz, Ричард Р .; Нейссен, Зигфрид; Кок, Йост Н. (28 июня 2005 г.). «Частая добыча поддерева - обзор». Fundamenta Informaticae. 66: 161–198. S2CID 14827585.

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

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

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

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

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

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

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

[9] Аоки-Киношита, Киёко Ф. (2009). Glycome Informatics: методы и приложения. CRC Press. п. 141. ISBN 9781420083347.

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]