빈번한 서브트리 마이닝

컴퓨터 과학에서 빈번한 서브트리 마이닝은 지원(다른 서브트리에서의 발생 횟수와 관련된 메트릭)이 지정된 ^[1]임계값을 초과하는 데이터베이스 내의 모든 패턴을 찾는 문제입니다.이것은 최대 합의 하위 트리 ^[2]문제의 보다 일반적인 형태입니다.

정의.

빈번한 서브트리 마이닝은 "지원"이 특정 사용자 지정 수준을 초과하는 모든 패턴을 찾는 문제입니다. 여기서 "지원"은 주어진 ^[3]패턴과 적어도1개의 서브트리가 동형인 데이터베이스 내의 트리 수로 계산됩니다.

형식적 정의

빈번한 서브트리 마이닝 문제는 공식적으로 다음과 ^[1]같이 정의되었습니다.

임계값 minfreq,

{\mathcal {C}}

클래스 C

P\preceq T

displaystyle\mathcal {C

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

P(\

displaystyle

P

\

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

T

),

트리

P(\

displaystyle

P\displaystyle P

,T

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

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

트리

세트

D

(\

mathcal

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

{

C

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

C(\cal

{

C})

P\preceq T

의 전이적

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

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

트리

클래스

C(\displaystyle)가 지정됩니다

.

Ubtree 채굴 문제는 P

(\

에서

{\mathcal {P}}

두 개의 트리가 동형화되지 않도록 모든

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

P(\

displaystyle\mathcal

{P

})

를

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

찾는 문제입니다.

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

여기

서 d는 안티 모노톤 함수입니다.P

P'\preceq P

P'\preceq P

\

displaystyle

P ' \

preceq

P

P'\preceq P

。

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

트리마이너

2002년 Mohammed J. Zaki는 빈번한 서브트리 마이닝 문제를 해결하기 위한 효율적인 알고리즘인 TreeMiner를 도입했다.이 알고리즘은 트리 노드를 나타내기 위해 "스코프 리스트"를 사용하고 패턴 ^[4]매칭에 기초한 알고리즘인 PatternMatcher와 대조되었다.

정의들

유도 서브트리

하위 $S=(V_{s},E_{s})$ S $S=(V_{s},E_{s})$ ( $S=(V_{s},E_{s})$ s , $S=(V_{s},E_{s})$ ) { $displaystyle$ S $=$ ( V $_$ { $s$ , $E$ _ { $s$ ) $T=(V,E)$ is $S=(V_{s},E_{s})$ $V_{s}\subseteq V$ ⊆ $V_{s}\subseteq V$ $V_{s}\subseteq V$ \ $displaystyle$ $T$ $=$ ( $V$ , E )의 $T=(V,E)$ $V_{s}\subseteq V$ 유도 하위 $트리$ 입니다 $.$ 는 T에서도 직접 접속됩니다.S의 임의의 노드A 및 B에 대해 노드A가 S의 노드B의 부모일 경우 노드A도 T의 노드B의 부모여야 합니다.

임베디드 서브트리

하위 $S=(V_{s},E_{s})$ S $S=(V_{s},E_{s})$ ( $S=(V_{s},E_{s})$ s , $S=(V_{s},E_{s})$ s $S=(V_{s},E_{s})$ ) { $displaystyle$ S $T=(V,E)$ ( V $_$ { $s$ , $T=(V,E)$ $S=(V_{s},E_{s})$ _ { $s$ $S=(V_{s},E_{s})$ $}$ )는 $S=(V_{s},E_{s})$ $V_{s}\subseteq V$ $T=(V,E)$ V $V_{s}\subseteq V$ ⊆ $V_{s}\subseteq V$ $V_{s}\subseteq V$ \ $displaystyle T =$ ( $V$ , $E$ )의 $T=(V,E)$ $T=(V,E)$ 하위 트리입니다.즉, S의 임의의 노드A 및 B에 대해 노드A가 S의 노드B의 부모일 경우 노드A는 T의 노드B의 상위 노드A여야 합니다.유도 하위 트리도 포함 하위 트리이며, 따라서 포함 하위 트리의 개념은 유도 하위 트리의 일반화이다.이러한 임베디드 서브 트리는 전통적인 유도 서브 트리 마이닝에서 누락된 트리의 숨겨진 패턴을 특징짓습니다.크기가 k인 서브트리는 종종 k-서브 트리라고 불립니다.

지지하다

서브트리의 지원은 서브트리를 포함하는 데이터베이스 내의 트리 수입니다.서브트리의 지원이 사용자 지정 임계값(대부분 minsup으로 표시됨) 이상일 경우 서브트리는 자주 발생합니다.TreeMiner의 목표는 최소한의 지원을 제공하는 모든 임베디드 서브트리를 찾는 것입니다.

트리의 문자열 표현

트리 구조를 인코딩하는 방법은 여러 가지가 있습니다.TreeMiner는 트리를 효율적으로 조작하고 카운트를 지원하기 위해 트리의 문자열 표현을 사용합니다.처음에 문자열은 $\varnothing$ \ $display \varnothing$ 으로 $\varnothing$ 설정되어 있습니다.트리의 루트부터 노드라벨이 깊이 우선 검색 순서로 문자열에 추가됩니다.검색 프로세스가 하위에서 상위로 역추적될 때마다 -1이 문자열에 추가됩니다.예를 들어 루트 라벨이 A, 좌측 라벨이 B, 우측 라벨이 C인 단순한 바이너리 트리는 문자열 A B - 1 C - 1로 나타낼 수 있습니다.

프리픽스 등가 클래스

2개의 k-sub-tree 문자열 표현이 (k-1)번째 노드까지 동일할 경우 2개의 k-sub-tree가 같은 프리픽스 동등성 클래스에 있다고 간주됩니다.즉, 프리픽스 등가 클래스의 모든 요소는 마지막 노드에 의해서만 다릅니다.예를 들어 문자열 표현A B - 1 C - 1 및A B - 1 D - 1 의 2 개의 트리는, 요소(C, 0) 및 (D, 0)를 가지는 프리픽스 등가 클래스 A 에 있습니다.프리픽스 클래스의 요소는, 그 요소가 접속되어 있는 노드의 0 베이스의 깊이 우선 인덱스와 짝을 이룬 노드 라벨에 의해서 지정된다.이 예에서는 프레픽스클래스 A의 양쪽 요소가 루트에 부가되어 있으며, 루트의 인덱스는 0입니다.

범위

노드 A의 스코프는 숫자 $[l,r]$ 쌍[ $[l,r]$ , $]$ { displaystyle [ l , r ]{ $displaystyle$ [ $[l,r]$ l , r $[l,r]$ ]}으로 $[l,r]$ 지정됩니다.여기서 l과 r은 A에 루트된 서브트리의 최소 및 최대 노드인덱스입니다.즉, l은 A의 지표, r은 A의 후손 중 가장 오른쪽 잎의 지표이다.따라서 A의 하위 항목의 지수는 A의 범위에 속해야 하며, 이는 하위 트리의 지원을 계산할 때 매우 유용한 속성이 될 것이다.

알고리즘.

후보생성

빈번한 서브트리 패턴은 안티모노톤 속성을 따릅니다.즉, k-sub-tree의 지원은 그 (k-1)-sub-tree의 지원 이하입니다.빈도가 높은 것으로 알려진 패턴의 슈퍼 패턴만 빈도가 높을 수 있습니다.이 속성을 사용하면 프리픽스클래스 확장을 통해 빈번한 (k-1) 서브트리에 따라 k 서브트리의 후보를 생성할 수 있습니다.C를 2개의 요소(x,i)와 (y,j)를 가진 프리픽스 동등성 클래스로 합니다.C'를 요소 확장(x,i)을 나타내는 클래스라고 하자.C'의 요소는 C의 2개의 (k-1)-서브 트리에 대해 결합 연산을 실행함으로써 추가됩니다.(x,i) 및 (y,j)에서의 결합 연산은 다음과 같이 정의됩니다.

i $i>j$ > $i>j$ { $displaystyle$ i $> j$ $i>j$ 인 경우 (y,j)를 C'에 추가합니다.
i $i=j$ {\ $displaystyle i=$ j $i=j$ 이면 C'에 (y,j) 및 (y,ni)를 더합니다. 여기서 ni는 C의 x 깊이 우선 지수입니다.
i $i<j$ < $i<j$ \ $displaystyle$ i < $i<j$ j $i<j$ 의 경우 가능한 요소를 C'에 추가할 수 없습니다.

이 조작은 순서부여된2개의 임의의 요소에 대해 반복되지만 K-sub-tree의 확장 프레픽스클래스를 구축하기 위해 C에서 반드시 구별되는 것은 아닙니다.

스코프 리스트 표시

TreeMiner는 서브트리의 스코프 리스트 표현을 사용하여 깊이 우선 후보 생성을 수행하여 지원 카운트를 고속화합니다.k-sub-tree S는 트리플렛(t,m,s)으로 나타낼 수 있습니다.여기서 t는 서브트리의 발신원 트리 ID, m은 프리픽스 일치 라벨, s는 마지막 노드의 범위입니다.데이터베이스 내의 다양한 트리에서 S가 어떻게 발생하느냐에 따라 S는 다른 스코프 리스트 표현을 가질 수 있습니다.TreeMiner는 서브트리의 스코프 리스트 표현에 대해 클래스 확장을 실행하는 스코프 리스트 조인을 정의합니다.다음 조건 중 하나를 충족하는 2개의 서브트리 $(t_{x},m_{x},s_{x})$ x $(t_{x},m_{x},s_{x})$ $(t_{x},m_{x},s_{x})$ , $(t_{x},m_{x},s_{x})$ x $(t_{x},m_{x},s_{x})$ )({ $style$ ( $t_{x}, m_{x$ }, $s_{x})$ 와 $(t_{x},m_{x},s_{x})$ $(t_{y},m_{y},s_{y})$ y $(t_{y},m_{y},s_{y})$ $(t_{y},m_{y},s_{y})$ , $){displaystyle (t_y,m_y},s_{y})$ 가 $(t_{y},m_{y},s_{y})$ 존재하는 경우 2개의 요소(x,i)와 (y,j)를 결합할 수 있습니다.

범위 내 테스트: $t_{x}=t_{y},m_{x}=m_{y},s_{y}\subset s_{x}$ $t_{x}=t_{y},m_{x}=m_{y},s_{y}\subset s_{x}$ $t_{x}=t_{y},m_{x}=m_{y},s_{y}\subset s_{x}$ $t_{x}=t_{y},m_{x}=m_{y},s_{y}\subset s_{x}$ $t_{x}=t_{y},m_{x}=m_{y},s_{y}\subset s_{x}$ $t_{x}=t_{y},m_{x}=m_{y},s_{y}\subset s_{x}$ x $=$ $t_{x}=t_{y},m_{x}=m_{y},s_{y}\subset s_{x}$ , $t_{x}=t_{y},m_{x}=m_{y},s_{y}\subset s_{x}$ $t_{x}=t_{y},m_{x}=m_{y},s_{y}\subset s_{x}$ $t_{x}=t_{y},m_{x}=m_{y},s_{y}\subset s_{x}$ x $t_{x}=t_{y},m_{x}=m_{y},s_{y}\subset s_{x}$ { $display t _$ { $x$ } 、 $m$ _ { x } = $t_{x}=t_{y},m_{x}=m_{y},s_{y}\subset s_{x}$ m $t_{x}=t_{y},m_{x}=m_{y},s_{y}\subset s_{x}$ _ { $y$ } $t_{x}=t_{y},m_{x}=m_{y},s_{y}\subset s_{x}$ = j $i=j$ $i=j$ _ { y } \ $display style$ $i$ $i=j$ j 의 $i=j$ 에 대응합니다.
$t_{x}=t_{y},m_{x}=m_{y},s_{y}>s_{x}$ 외 테스트: t x $t_{x}=t_{y},m_{x}=m_{y},s_{y}>s_{x}$ $t_{x}=t_{y},m_{x}=m_{y},s_{y}>s_{x}$ y $t_{x}=t_{y},m_{x}=m_{y},s_{y}>s_{x}$ $t_{x}=t_{y},m_{x}=m_{y},s_{y}>s_{x}$ x $=$ $t_{x}=t_{y},m_{x}=m_{y},s_{y}>s_{x}$ $t_{x}=t_{y},m_{x}=m_{y},s_{y}>s_{x}$ $t_{x}=t_{y},m_{x}=m_{y},s_{y}>s_{x}$ $t_{x}=t_{y},m_{x}=m_{y},s_{y}>s_{x}$ > $t_{x}=t_{y},m_{x}=m_{y},s_{y}>s_{x}$ { $displaystyle t _$ ${$ x } = $t$ _ { y } = $t_{x}=t_{y},m_{x}=m_{y},s_{y}>s_{x}$ m _ { y } = m _ { $y$ } 、 s _ { y $t_{x}=t_{y},m_{x}=m_{y},s_{y}>s_{x}$ } > s _ { $x$ } 。i $i>j$ > j \ $displaystyle$ i $i>j$ j $t_{x}=t_{y},m_{x}=m_{y},s_{y}>s_{x}$ $i$ i i i i i i i i i i i i 。

스코프 리스트테스트에서 사용되는 개별 트리 ID를 추적함으로써 서브트리의 지원을 효율적으로 계산할 수 있습니다.

적용들

빈번한 서브트리 마이닝이 유용한 도메인은 데이터 엔티티 간의 복잡한 관계를 수반하는 경향이 있습니다.예를 들어 XML 문서 분석에는 빈번한 서브트리 ^[1]마이닝이 필요합니다.이것이 유용한 또 다른 도메인은 웹 사용 마이닝 문제입니다. 사용자가 웹 사이트를 방문할 때 취한 액션은 다양한 방법으로 기록되고 분류될 수 있기 때문에 복잡한 트리 데이터베이스를 자주 하위 트리 ^[4]마이닝으로 분석해야 합니다.빈번한 서브트리 채굴이 유용한 다른 분야에는 계산 생물학,^[5]^[6] RNA 구조 분석,^[6] 패턴 인식,^[7] 생물 정보학 ^[8]및 KEGG GLICAN 데이터베이스의 ^[9]분석이 포함된다.

과제들

패턴(또는 트랜잭션)이 특정 서브그래프를 지원하는지 확인하는 것은 서브그래프 동형 문제의 ^[7]NP-완전 인스턴스이기 때문에 NP-완전 문제입니다.게다가 조합의 폭발에 의해, 「모든 빈번한 서브 트리 패턴의 마이닝은, 크고 조밀한 트리 ^[10]데이타베이스에서는 실현 불가능하게 된다」라고 Lei 등은 말하고 있다.

레퍼런스

^ ^a ^b ^c Chi, Yun; Muntz, Richard R.; Nijssen, Siegfried; Kok, Joost N. (28 June 2005). "Frequent Subtree Mining - An Overview". Fundamenta Informaticae. 66: 161–198. S2CID 14827585.
^ Deepak, Akshay; Fernández-Baca, David; Tirthapura, Srikanta; Sanderson, Michael J.; McMahon, Michelle M. (July 2013). "EvoMiner: frequent subtree mining in phylogenetic databases". Knowledge and Information Systems. 41 (3): 559–590. doi:10.1007/s10115-013-0676-0.
^ Dai, H., Srikant, R. 및 Zhang, C.(2004)「지식 발견과 데이터 마이닝에 관한 어드밴스」제8회 태평양 아시아 회의, PAKDD 2004, 호주 시드니, 2004년 5월 26일~28일, Proceedings.제1판 65쪽
^ ^a ^b Zaki, Mohammed J. (2002). Efficiently mining frequent trees in a forest. Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. pp. 71–80. doi:10.1145/775047.775058. ISBN 978-1581135671. Retrieved 16 June 2014.
^ 디팍, 악셰이, 데이비드 페르난데스-바카, 스리칸타 티르타푸라, 마이클 J. 샌더슨, 미셸 M.맥마흔."EvoMiner: 계통발생 데이터베이스의 서브트리 마이닝이 빈번하게 이루어집니다."Knowledge and Information Systems (2011): 1 ~32 。
^ ^a ^b 치, 윤, 양이롱, 리처드 R.먼츠. "자주 서브트리 채굴에 사용되는 라벨이 붙은 나무와 그 응용 프로그램의 표준 형태"Knowledge and Information Systems 8, No.2 (2005) : 203 ~234 。
^ ^a ^b Chi, Yun; Yang, Yirong; Muntz, Richard R. (2004). "Mining Frequent Rooted Trees and Free Trees Using Canonical Forms" (PDF). Knowledge and Information Systems. Retrieved 16 June 2014.
^ Xiao, Yongqiao; Yao, Jenq-Foung; Li, Zhigang; Dunham, Margaret H. (2003). "Efficient data mining for maximal frequent subtrees". Third IEEE International Conference on Data Mining. ICDM 2003. pp. 379–386. doi:10.1109/ICDM.2003.1250943.
^ Aoki-Kinoshita, Kiyoko F. (2009). Glycome Informatics: Methods and Applications. CRC Press. p. 141. ISBN 9781420083347.
^ 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.

[Chi01-1] Chi, Yun; Muntz, Richard R.; Nijssen, Siegfried; Kok, Joost N. (28 June 2005). "Frequent Subtree Mining - An Overview". Fundamenta Informaticae. 66: 161–198. S2CID 14827585.

[2] Deepak, Akshay; Fernández-Baca, David; Tirthapura, Srikanta; Sanderson, Michael J.; McMahon, Michelle M. (July 2013). "EvoMiner: frequent subtree mining in phylogenetic databases". Knowledge and Information Systems. 41 (3): 559–590. doi:10.1007/s10115-013-0676-0.

[3] Dai, H., Srikant, R. 및 Zhang, C.(2004)「지식 발견과 데이터 마이닝에 관한 어드밴스」제8회 태평양 아시아 회의, PAKDD 2004, 호주 시드니, 2004년 5월 26일~28일, Proceedings.제1판 65쪽

[:0-4] Zaki, Mohammed J. (2002). Efficiently mining frequent trees in a forest. Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. pp. 71–80. doi:10.1145/775047.775058. ISBN 978-1581135671. Retrieved 16 June 2014.

[Dee13-5] 디팍, 악셰이, 데이비드 페르난데스-바카, 스리칸타 티르타푸라, 마이클 J. 샌더슨, 미셸 M.맥마흔."EvoMiner: 계통발생 데이터베이스의 서브트리 마이닝이 빈번하게 이루어집니다."Knowledge and Information Systems (2011): 1 ~32 。

[Yun05-6] 치, 윤, 양이롱, 리처드 R.먼츠. "자주 서브트리 채굴에 사용되는 라벨이 붙은 나무와 그 응용 프로그램의 표준 형태"Knowledge and Information Systems 8, No.2 (2005) : 203 ~234 。

[Chi04-7] Chi, Yun; Yang, Yirong; Muntz, Richard R. (2004). "Mining Frequent Rooted Trees and Free Trees Using Canonical Forms" (PDF). Knowledge and Information Systems. Retrieved 16 June 2014.

[Xia03-8] Xiao, Yongqiao; Yao, Jenq-Foung; Li, Zhigang; Dunham, Margaret H. (2003). "Efficient data mining for maximal frequent subtrees". Third IEEE International Conference on Data Mining. ICDM 2003. pp. 379–386. doi:10.1109/ICDM.2003.1250943.

[9] Aoki-Kinoshita, Kiyoko F. (2009). Glycome Informatics: Methods and Applications. CRC Press. p. 141. ISBN 9781420083347.

[Zou06-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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

Search