Частая добыча поддеревьев

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

Определение

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

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

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

При наличии порогового значения minfreq , класса деревьев , транзитивного отношения поддерева между деревьями , конечного множества деревьев задача извлечения частых поддеревьев представляет собой задачу нахождения всех деревьев, таких, что никакие два дерева не являются изоморфными и С {\displaystyle {\mathcal {C}}} П ⪯ Т {\displaystyle P\preceq T} П , Т ∈ С {\displaystyle P,T\in {\mathcal {C}}} Д ⊆ С {\displaystyle {\mathcal {D}}\subseteq {\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 — антимонотонная функция, такая что если то P ′ ⪯ P {\displaystyle P'\preceq P}
∀ T ∈ C : d ( P ′ , T ) ≥ d ( P , T ) . {\displaystyle \forall T\in {\mathcal {C}}:\quad d(P',T)\geq d(P,T).}

TreeMiner

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

Определения

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

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

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

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

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

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

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

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

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

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

Объем

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

Алгоритм

Генерация кандидатов

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

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

Эта операция повторяется для любых двух упорядоченных, но не обязательно различных элементов в 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 ) {\displaystyle (t_{x},m_{x},s_{x})} ( t y , m y , s y ) {\displaystyle (t_{y},m_{y},s_{y})}

  • Тест в рамках области применения: , что соответствует случаю, когда . t x = t y , m x = m y , s y ⊂ s x {\displaystyle t_{x}=t_{y},m_{x}=m_{y},s_{y}\subset s_{x}} i = j {\displaystyle i=j}
  • Тест вне области действия: , что соответствует случаю, когда . t x = t y , m x = m y , s y > s x {\displaystyle t_{x}=t_{y},m_{x}=m_{y},s_{y}>s_{x}} i > j {\displaystyle i>j}

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

Приложения

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

Вызовы

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

Ссылки

  1. ^ abc Чи, Юн; Мунц, Ричард Р.; Нейссен, Зигфрид; Кок, Йост Н. (28 июня 2005 г.). «Частой анализ поддеревьев — обзор». Фундамента информатики . 66 : 161–198 . S2CID  14827585.
  2. ^ Дипак, Акшай; Фернандес-Бака, Дэвид; Тиртхапура, Шриканта; Сандерсон, Майкл Дж.; Макмахон, Мишель М. (июль 2013 г.). «EvoMiner: частый анализ поддеревьев в филогенетических базах данных». Системы знаний и информации . 41 (3): 559– 590. doi :10.1007/s10115-013-0676-0. S2CID  254145982.
  3. ^ Дай, Х., Шрикант, Р. и Чжан, К. (2004). «Достижения в области обнаружения знаний и добычи данных». 8-я Тихоокеанско-Азиатская конференция, PAKDD 2004, Сидней, Австралия, 26–28 мая 2004 г., Труды . 1-е изд., стр. 65.
  4. ^ ab Zaki, Mohammed J. (2002). "Эффективная добыча частых деревьев в лесу". Труды восьмой международной конференции ACM SIGKDD по обнаружению знаний и добыче данных . стр.  71–80 . doi :10.1145/775047.775058. ISBN 978-1581135671. S2CID  1649653 . Получено 16 июня 2014 г. .
  5. ^ Дипак, Акшай, Дэвид Фернандес-Бака, Шриканта Тиртхапура, Майкл Дж. Сандерсон и Мишель М. Макмахон. «EvoMiner: частый анализ поддеревьев в филогенетических базах данных». Системы знаний и информации (2011): 1-32.
  6. ^ ab Chi, Yun, Yirong Yang и Richard R. Muntz. «Канонические формы для помеченных деревьев и их применение в частом извлечении поддеревьев». Knowledge and Information Systems 8, № 2 (2005): 203–234.
  7. ^ ab Chi, Yun; Yang, Yirong; Muntz, Richard R. (2004). "Mining Frequent Rooted Trees and Free Trees Using Canonical Forms" (PDF) . Системы знаний и информации . Получено 16 июня 2014 г. .
  8. ^ Сяо, Юнцяо; Яо, Дженк-Фунг; Ли, Чжиган; Данхэм, Маргарет Х. (2003). «Эффективный анализ данных для максимально частых поддеревьев». Третья международная конференция IEEE по анализу данных . ICDM 2003. стр.  379–386 . doi :10.1109/ICDM.2003.1250943.
  9. ^ Аоки-Киношита, Киёко Ф. (2009). Гликомная информатика: методы и приложения . CRC Press. стр. 141. ISBN 9781420083347.
  10. ^ Zou, Lei; Lu, Yansheng; Zhang, Huaming; Hu, Rong (2006). "Mining Frequent Induced Subtree Patterns with Subtree-Constraint". Sixth IEEE International Conference on Data Mining Workshops . ICDM Workshops 2006. pp.  3–7 . doi :10.1109/ICDMW.2006.112.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Frequent_subtree_mining&oldid=1212808351"