Data Similarity and Distance를 측정하는 measure

소개글

Text Similarity Measures, Temporal Similarity Measures, Graph Similarity Measures, Supervised Similarity Functions에 대한 설명입니다.

목차

1. Text Similarity Measures
2. Temporal Similarity Measures
3. Graph Similarity Measures
4. Supervised Similarity Functions

본문내용

- Similarity between Two Graphs
그래프간 유사도 계산에서 어려운 요인은 많은 node들이 같은 레이블을 가지고 있는 것이다. 이 문 제는 하나의 분자에 같은 원소가 존재하는 화학분야 같은 곳에서 발생한다. 이것을 NP-hard라고 알 려진 graph isomorphim problem(동형이질: 모양은 같은데 성질은 다른 것)이라고 부른다. 따라 서 다양한 알고리즘들이 제안되었다.

-Maximum common subgraph distance: 두 그래프가 큰 subgraph를 가질 때 유사하다고 고려한다.
-Substructure-based similarity: 공통의 substructures의 수를 세어서 유사도를 측정한다.
-Graph-edit distance: string-edit distance와 비슷한 방식으로 하나의 그래프를 목표로 하는 그래프에 일치시키기 위해서 얼마나 많이 edit을 해야하는지에 따라서 유사도가 결정된 다. 하지만 규모가 큰 그래프에서는 적용시키기가 어렵다.
-Graph kernels: 비슷한건 비슷하게, 다른 것은 더 다르게 만드는 kernel function을 통해서 유사도를 측정한다.

4. Supervised Similarity Functions
분류문제에 적용하는 function으로 높은 value를 가질수록 비유사성이 커지므로 distance function 이다. 특징은 이전의 measure들은 사용자의 도움이 없이 유사도를 측정했지만, 이것은 특성의 관련 성 또는 distance function을 결정할 때 도메인 지식에 크게 의존한다. 도메인 지식에 따른 feedback은 아래와 같이 표현된다.

각 feature마다 feedback을 바탕으로 결정된가중치..

<중 략>

참고 자료

없음