트리 커널: 트리 구조 데이터 간의 유사성 정량화

네트워크 또는 그래프 는 노드 형태의 구조화된 데이터 유형으로, 노드 간의 관계는 링크 또는 에지 로 설명됩니다. 그래프의 노드와 간선에는 수치적이거나 범주적이거나 훨씬 더 복잡한 여러 속성이 있을 수 있습니다.

오늘날 엄청난 양의 데이터가 네트워크나 그래프의 형태로 제공됩니다. 예를 들어, 웹 페이지와 하이퍼링크가 있는 World Wide Web, 소셜 네트워크, 의미 네트워크, 생물학적 네트워크, 과학 문헌에 대한 인용 네트워크 등이 있습니다.

트리는 특수한 유형의 그래프이며 자연스럽게 많은 유형의 데이터를 나타내는 데 적합합니다. 나무 분석은 컴퓨터 및 데이터 과학에서 중요한 분야입니다. 이 기사에서는 트리의 링크 구조 분석을 살펴보겠습니다. 특히, 우리는 트리 그래프를 서로 비교하는 방법인 트리 커널에 초점을 맞춰 유사점이나 차이점을 수량화할 수 있는 측정값을 얻을 수 있습니다. 이는 분류 및 데이터 분석과 같은 많은 최신 애플리케이션에서 중요한 프로세스입니다.

구조화된 데이터의 감독되지 않은 분류

분류 는 중요한 구성 요소 기계 학습 및 데이터 분석입니다. 일반적으로 분류는 감독 되거나 감독되지 않을 수 있습니다. 지도 분류에서 클래스는 이미 알려져 있으며, 분류 모델은 올바른 클래스가 이미 제공된 학습 데이터로 구성됩니다. 대조적으로, 감독되지 않은 분류는 알려진 것이 없는 클래스를 식별하려고 시도하고 데이터를 유사성의 일부 측정을 기반으로 범주로 그룹화합니다.

비지도 분류는 그래프 이론과 결합하여 유사한 트리 네트워크 그룹을 식별할 수 있습니다. 트리 데이터 구조는 여러 도메인의 개체를 모델링하는 데 사용됩니다. 예를 들어 자연어 처리(NLP)에서 구문 분석 트리는 정렬되고 레이블이 지정된 트리로 모델링됩니다. 자동화된 추론에서 많은 문제는 검색을 통해 해결됩니다. 여기서 검색 공간은 정점이 검색 상태와 연결된 트리로 표시되고 모서리는 추론 단계를 나타냅니다. 또한 HTML 및 XML 문서와 같은 반구조화된 데이터는 정렬되고 레이블이 지정된 트리로 모델링될 수 있습니다.

이러한 영역은 비지도 분류 기술을 통해 유용하게 분석될 수 있습니다. NLP에서 분류는 일련의 문장을 질문, 명령 및 문장으로 자동 그룹화하는 데 사용할 수 있습니다. 마찬가지로 HTML 소스에 분류 방법을 적용하여 유사한 웹 사이트 그룹을 식별할 수 있습니다. 이러한 각각의 경우에 필요한 것은 두 나무가 서로 얼마나 "유사한"지를 측정하는 방법뿐입니다.

차원의 저주

대부분의 분류 알고리즘은 데이터가 특징 공간 에서 데이터의 특징 값을 나타내는 벡터화된 형식으로 변환되어야 데이터가 특징 공간에서 선형 대수를 사용하여 분석될 수 있습니다. 나무와 같은 구조화된 데이터 또는 반구조화된 데이터에서 결과 벡터의 차원(즉, 특징 공간의 특징 수)은 매우 높을 수 있습니다. 특징 공간은 구조에 대한 정보를 보존해야 하기 때문입니다.

이는 많은 분류 기술이 입력의 차원에 따라 효과적으로 확장할 수 없다는 점을 고려할 때 심각한 단점이 될 수 있습니다. 즉, 입력의 차원이 증가할수록 분류력이 감소합니다. 이 문제는 차원의 저주로 알려져 있습니다.

이러한 성능 저하의 원인에 대한 아이디어를 얻으려면 차원 d 의 공간 X 를 고려하십시오. X 에 균일하게 분포된 점 집합이 포함되어 있다고 가정합니다. X 의 차원 수가 증가하면 동일한 밀도를 유지하는 데 필요한 점의 수가 기하급수적으로 증가해야 합니다. 즉, 입력의 차원이 클수록 해당 데이터가 희소할 가능성이 높아집니다. 일반적으로 희소 데이터 세트는 데이터 요소 간의 상관 관계가 알고리즘이 감지하기에는 너무 약하기 때문에 좋은 분류기를 만들기에 충분한 정보를 제공하지 않습니다.

위의 각 기능 공간에는 8개의 데이터 포인트가 있습니다. 1차원 공간에서는 왼쪽에 5개 점, 오른쪽에 3개 점의 그룹을 쉽게 식별할 수 있습니다. 더 많은 수의 피쳐(즉, 차원)에 걸쳐 이러한 점을 확장하면 이러한 그룹을 찾기가 더 어려워집니다. 실제 응용 프로그램에서 피쳐 공간은 수백 개의 차원을 쉽게 가질 수 있습니다.

구조화된 데이터에 대한 벡터화된 표현은 관리 가능한 기능 집합을 선택하는 데 도메인에 대한 정보를 효과적으로 사용할 수 있는 경우 적합합니다. 이러한 정보를 사용할 수 없는 경우 벡터 공간에서 작업을 수행하지 않고 구조화된 데이터를 직접 처리할 수 있는 기술을 사용하는 것이 바람직합니다.

커널 방법

커널 방법은 데이터를 벡터 형식으로 변환할 필요가 없습니다. 그들이 필요로 하는 유일한 정보는 데이터 세트에 있는 각 항목 쌍의 유사성을 측정하는 것입니다. 이 측정값을 커널 이라고 하며 이를 판별하는 기능을 커널 함수 라고 합니다. 커널 방법은 피쳐 공간에서 선형 관계를 찾습니다. 기능적으로는 기능 공간에서 두 데이터 포인트의 내적을 취하는 것과 동일하며 실제로 기능 설계는 여전히 커널 기능 설계에서 유용한 단계일 수 있습니다. 그러나 커널 방법 방법은 커널 함수가 데이터를 입력으로 사용할 수 있는 대칭적이고 양의 반정부 함수인 한 내적을 커널 함수로 대체하는 것이 가능하다는 것을 보여줄 수 있기 때문에 기능 공간에서 직접 작동하는 것을 피합니다. 원래 공간에서.

따라서 커널 기능을 사용하는 이점은 기능 공간의 크기에 의존하지 않고 커널 함수의 복잡성에 의존하는 계산 복잡성으로 거대한 기능 공간을 분석할 수 있다는 것입니다. 즉, 커널 방법은 저주를 겪지 않습니다. 차원의.

n개의 예제로 구성된 유한 데이터 세트를 고려하면 크기가 항상 n × n 인 커널 행렬 을 생성하여 데이터 내의 유사성을 완벽하게 표현할 수 있습니다. 이 행렬은 각 개별 예의 크기와 무관합니다. 이 속성은 특징 공간이 큰 예제의 작은 데이터 집합을 분석할 때 유용합니다.

일반적으로 커널 방법은 데이터 표현에 대한 질문에 대한 다른 대답을 기반으로 합니다. 입력 포인트를 기능 공간에 매핑하는 대신 데이터는 커널 행렬 K 의 쌍별 비교를 통해 표현되며 모든 관련 분석은 커널 행렬에 대해 수행될 수 있습니다.

많은 데이터 마이닝 방법을 커널화할 수 있습니다. 지원 벡터 머신과 같은 커널 방법을 사용하여 트리 구조 데이터 인스턴스를 분류하려면 유효한(양의 정부호 대칭) 커널 함수 k : T × T → R , 트리 커널 이라고도 하는 정의로 충분합니다. 실질적으로 유용한 트리 커널을 설계할 때 트리 크기에 대해 다항식 시간으로 계산할 수 있어야 하고 동형 그래프를 감지할 수 있어야 합니다. 이러한 트리 커널을 완전한 트리 커널이라고 합니다.

트리 커널

이제 나무의 유사성을 측정하는 데 유용한 몇 가지 나무 커널을 소개하겠습니다. 주요 아이디어는 커널 매트릭스를 구축하기 위해 데이터 세트의 각 트리 쌍에 대한 커널을 계산한 다음 트리 세트를 분류하는 데 사용할 수 있다는 것입니다.

문자열 커널

먼저, 트리를 문자열로 변환하는 데 기반을 둔 또 다른 커널 방법을 소개하는 데 도움이 될 문자열 커널에 대한 간략한 소개로 시작하겠습니다.

| _ _ _ 에 | 문자열의 길이를 나타냅니다. 여기서 설명할 문자열 커널은 다음과 같이 정의됩니다.

K 스트링 (S 1 , S 2 ) = Σ s∈F num s (S 1 ) num s (S 2 )w s

여기서 F 는 S 1 과 S 2 모두에서 발생하는 부분 문자열의 집합이고 매개변수 w s 는 가중치 매개변수 역할을 합니다(예: 중요한 부분 문자열을 강조하기 위해). 우리가 볼 수 있듯이 이 커널은 많은 공통 부분 문자열을 공유할 때 문자열 쌍에 더 높은 가치를 부여합니다.

트리를 문자열로 변환하는 트리 커널

이 문자열 커널을 사용하여 트리 커널을 만들 수 있습니다. 이 커널의 이면에 있는 아이디어는 트리 구조를 인코딩하는 체계적인 방식으로 두 개의 트리를 두 개의 문자열로 변환한 다음 위의 문자열 커널을 적용하는 것입니다.

두 트리를 다음과 같이 두 개의 문자열로 변환합니다.

T 가 대상 트리 중 하나를 나타내고 label(ns ) T 에 있는 노드 ns 의 문자열 레이블을 나타냅니다. tag(ns ) 는 ns 에 뿌리를 둔 T 의 하위 트리에 대한 문자열 표현을 나타냅니다. 따라서 n root 가 T 의 루트 노드인 경우 tag(n root ) 는 전체 트리 T 의 문자열 표현입니다.

다음으로 string(T) = tag(n root ) T 의 문자열 표현을 나타내도록 하십시오. 다음 단계를 상향식으로 재귀적으로 적용하여 string(T) 를 얻습니다.

• 노드 ns 가 리프이면 tag (ns ) = "[" + label(ns ) + "] " 로 설정합니다(여기서 + 는 문자열 연결 연산자입니다).
• 노드 ns 가 리프가 아니고 c 자식이 있는 경우 n 1 , n 2 , … , n c , tag(n 1 ), tag(n 2 ), … , tag(n c ) 를 사전순으로 정렬하여 태그 를 얻습니다. (n 1* ), tag(n 2* ), … , tag(n c* ) 및 let tag (ns ) = "[" + label(ns ) + tag( n 1* ) + tag(n 2* ) + … + 태그(n c* ) + “]” .

아래 그림은 이 트리에서 문자열로의 변환의 예를 보여줍니다. 결과는 "["와 같은 여는 구분 기호로 시작하여 닫는 구분 기호 "]"로 끝나는 문자열이며, 각 중첩 구분 기호 쌍은 특정 노드에 뿌리를 둔 하위 트리에 해당합니다.

이제 위의 변환을 두 개의 트리 T 1 및 T 2 에 적용하여 두 개의 문자열 S 1 및 S 2 를 얻을 수 있습니다. 거기에서 위에서 설명한 문자열 커널을 간단히 적용할 수 있습니다.

두 개의 스트링 S 1 과 S 2 를 통한 T 1 과 T 2 사이의 트리 커널은 이제 다음과 같이 주어질 수 있습니다:

K 트리 (T 1 , T 2 ) = K 스트링 ( string(T 1 ), string(T 2 ) ) = K 스트링 (S 1 , S 2 ) = Σ s∈F num s (S 1 )num s (S 2 ) 주

대부분의 응용 프로그램에서 가중치 매개변수는 w | 에 | , 길이에 따라 부분 문자열에 가중치 부여 | 에 | . w에 대한 일반적인 가중 방법 | 에 | 이다:

• 일정한 가중치( w | s | = 1 )
• k -스펙트럼 가중치( w | s | = k 이면 w | s | = 1, 그렇지 않으면 w | s | = 0 )
• 지수 가중치( w | s | = λ | s | 여기서 0 ≤ λ ≤ 1 은 감쇠율)

커널을 계산하려면 모든 공통 부분 문자열 F 를 결정하고 S 1 과 S 2 에서 발생하는 횟수를 계산하는 것으로 충분합니다. 공통 부분 문자열을 찾는 이 추가 단계는 잘 연구된 문제이며 접미사 트리 또는 접미사 배열을 사용하여 O( | S 1 | + | S 2 | ) 에서 수행할 수 있습니다. 노드의 레이블을 설명하는 데 필요한 최대 문자 수(예: 비트, 바이트 또는 문자)가 일정하다고 가정하면 변환된 문자열의 길이는 | 에스 1 | = O( | T 1 | ) 및 | 에스 2 | = 오( | T 2 | ) . 따라서 커널 함수를 계산하는 계산 복잡도는 선형인 O( | T 1 | + | T 2 | ) 입니다.

하위 경로 기반 트리 커널

위의 트리 커널은 트리를 문자열로 변환하기 위해 수평 또는 너비 우선 접근 방식을 사용했습니다. 이 접근 방식은 매우 간단하지만 이 변환은 원래 형태로 직접 나무에서 작동할 수 없음을 의미합니다.

이 섹션에서는 트리의 수직 구조에서 작동하는 트리 커널을 정의하여 커널이 트리에서 직접 작동할 수 있도록 합니다.

루트에서 잎 중 하나로 경로의 하위 섹션을 하위 경로 라고 하며 하위 경로 집합 은 트리에 포함된 모든 하위 경로의 집합입니다.

두 트리 T 1 과 T 2 사이에 트리 커널 K(T 1 , T 2 ) 를 정의한다고 가정해 봅시다. 하위 경로 세트를 사용하여 이 트리 커널을 다음과 같이 정의할 수 있습니다.

K(T 1 , T 2 ) = Σ p∈P num p (T 1 )num p (T 2 )w | 피 |

여기서 num p (T) 는 하위 경로 p 가 트리 T 에서 발생하는 횟수입니다. | 피 | 는 하위 경로 p 의 노드 수이고 P 는 T 1 및 T 2 의 모든 하위 경로 집합입니다. 여 | 피 | 이전 섹션에서 소개한 것과 유사한 무게입니다.

여기에서는 깊이 우선 검색을 사용하여 이 커널의 간단한 구현을 제시합니다. 이 알고리즘은 2차 시간으로 실행되지만 평균적으로 선형 시간( O( | T 1 | log | T 2 | ) )을 달성할 수 있는 접미사 트리 또는 접미사 배열 또는 다중 키 퀵소트 알고리즘의 확장을 사용하는 보다 효율적인 알고리즘이 있습니다.

 subpath_track = {} def generate_subpaths(path, l): if l == len(path): if tuple(path) not in subpath_track: subpath_track[tuple(path)] = 1 else: subpath_track[tuple(path)] += 1 else: index = 0 while l+index-1 < len(path): if tuple(path[index: l+index]) not in subpath_track: subpath_track[tuple(path[index: l+index])] = 1 else: subpath_track[tuple(path[index: l+index])] += 1 index += 1 generate_subpaths(path, l+1) def get_subpaths(graph, root, track, path): track[root] = True if graph.degree(root) == 1: generate_subpaths(path, 1) else: for node in graph.neighbors(root): if node not in track: get_subpaths(graph, node, track, path + [node, ]) def kernel_subpath(t1, t2, common_track): kernel_v = 0 for p in subpath_track: kernel_v += common_track[t1][p]*common_track[t2][p] return kernel_v

이 예에서는 가중치 매개변수 w | 에 | 여 | 피 | = 1 . 이것은 모든 하위 경로에 동일한 가중치를 부여합니다. 그러나 k- 스펙트럼 가중치 또는 일부 동적으로 할당된 가중치 값을 사용하는 것이 적절한 경우가 많습니다.

마이닝 웹사이트

마무리하기 전에 트리 분류의 실제 응용 프로그램인 웹 사이트 분류에 대해 간단히 살펴보겠습니다. 많은 데이터 마이닝 컨텍스트에서 일부 데이터가 어떤 "유형" 웹 사이트에서 오는지 아는 것이 좋습니다. 다른 웹 사이트의 페이지는 유사한 서비스에 대한 웹 페이지가 구조화되는 방식의 유사성으로 인해 트리를 사용하여 매우 효과적으로 분류할 수 있습니다.

어떻게 합니까? HTML 문서는 나무와 매우 유사한 논리적 중첩 구조를 가지고 있습니다. 각 문서는 내부에 중첩된 추가 요소와 함께 하나의 루트 요소를 포함합니다. HTML 태그의 중첩 요소는 논리적으로 해당 태그의 자식 노드와 동일합니다.

HTML 문서를 트리로 변환할 수 있는 몇 가지 코드를 살펴보겠습니다.

 def html_to_dom_tree(root): node_id = 1 q = deque() graph = nx.Graph() q.appendleft({'element': root, "root_id": node_id}) while len(q): node = q.pop() if node and node['element'].name == "body": graph.add_node(node_id, element=node['element'].name) node_id += 1 root_id = node['root_id'] labels[root_id] = node['element'].name for t in node['element'].contents: if t and t.name: graph.add_node(node_id, element=t.name) graph.add_edge(root_id, node_id) q.appendleft({"element": t, "root_id": node_id}) node_id += 1 return graph

이렇게 하면 다음과 같은 트리 데이터 구조가 생성됩니다.

위의 구현은 몇 가지 유용한 Python 라이브러리를 사용합니다. 복잡한 그래프 구조로 작업하기 위한 NetworkX와 웹에서 데이터를 가져오고 문서를 조작하기 위한 Beautiful Soup입니다.

html_to_dom_tree(soup.find("body")) 를 호출하면 웹 페이지의 <body> 요소에 뿌리를 둔 NetworkX 그래프 객체가 반환됩니다.

1,000개의 웹사이트 홈페이지 집합에서 그룹을 찾고 싶다고 가정해 보겠습니다. 이와 같이 각 홈페이지를 트리로 변환함으로써, 예를 들어 이전 섹션에서 제공된 하위 경로 트리 커널을 사용하여 각각을 비교할 수 있습니다. 이러한 유사성 측정을 통해 예를 들어 전자 상거래 사이트, 뉴스 사이트, 블로그 및 교육 사이트를 서로 유사성으로 쉽게 식별할 수 있음을 알 수 있습니다.

결론

이 기사에서 우리는 트리 구조의 데이터 요소를 서로 비교하는 방법을 소개하고 커널 방법을 트리에 적용하여 유사성을 수량화할 수 있는 측정값을 얻는 방법을 보여주었습니다. 커널 방법은 트리 구조로 작업할 때 일반적인 상황인 고차원 공간에서 작업할 때 탁월한 선택으로 입증되었습니다. 이러한 기술은 커널 매트릭스에서 작동하는 잘 연구된 방법을 사용하여 대규모 트리 집합에 대한 추가 분석을 위한 단계를 설정합니다.

트리 구조는 XML 및 HTML 문서, 화합물, 자연어 처리 또는 특정 유형의 사용자 행동과 같은 많은 실제 영역에서 접하게 됩니다. HTML에서 트리를 구성하는 예에서 보여주듯이 이러한 기술을 통해 이러한 도메인에서 의미 있는 분석을 수행할 수 있습니다.