문서 클러스터링 일본언어문화학과 03703018 서동진.

Presentation on theme: "문서 클러스터링 일본언어문화학과 03703018 서동진."— Presentation transcript:

1 문서 클러스터링 일본언어문화학과 서동진

2 목차 문서 클러스터링 기술 엔진 알고리즘 계층적 클러스터링 / 할당식 클러스터링

3 문서 클러스터링 클러스터링 주어진 데이터를 의미 있는 그룹으로 분류하는 방법 문서 클러스터링
대용량의 문서를 주제에 따라 분류하는 것 문서 클러스터링의 이점 검색효율 향상 / 탐색시간 절약 색인 불용어 제거 등의 과정을 거쳐 대상 문서들을 문서-색인어 행렬 만들어서 클러스터링을 진행 bag-of-word 접근법 단어의 의미, 순서 등을 고려하지 않음 같은 주제는 비슷한 단어들의 출현 패턴을 보인다

4 문서 클러스터링 기술 여러 가지 주제를 포함하고 있는 한 문서 내에 있는 내용들을 동일한 주제에 따라 분류하여 주는 기술이다. 이 기술을 이용함으로써 문서 내에 뒤섞여있는 내용을 정리하여 사용자들에게 보여주게 된다. 따라서 전체 문서의 내용을 쉽게 분석할 수 있고 부분적으로 필요한 내용을 선택하여 쓸 수 있다.

5 문서 클러스터링 엔진 문서클러스터링 엔진은 문서를 구성하는 색인어들로부터 문서에 대한 특성벡터를 추출하고, 모든 문서쌍에 대하여 특성벡터를 이용한 유사도를 측정하여, 가장 유사도가 높은 문서쌍을 클러스터링하는 엔진이다. 문서 클러스터링 기법으로는 Graph Theoretic Methods, Fast Partition Methods, Nearest Neighbor Clusters 등이 이용되고 있다.

6 문서 클러스터링 엔진 Graph Theoretic Methods는 어떤 한계치 이상의 유사도를 지니는 객체를 그래프 형식으로 표현하는 기법이다. Fast Partition Methods는 문서간 클러스터링의 속도를 높이기 위한 기법으로 동일한 클러스터 내의 특정 문서를 대표 문서화함으로써 각 클러스터간에 대표문서를 비교하여 유사도를 계산하는 방식과 특정 클러스터의 대표문서를 추출하고 클러스터링하고자 하는 문서를 가장 유사한 대표문서가 있는 클러스터에 포함시키는 방식이 있다. Nearest Neighbor Clusters는 가장 근접한 문서들을 클러스터링하는 기법이다.

7 문서 클러스터링 알고리즘 (계층적 클러스터링)
트리 구조를 형성하여 클러스터링을 하는 모델 그림은 D1~D6문서들을 계층적 클러스터링한 예.

8 문서 클러스터링 알고리즘 (계층적 클러스터링)
장점 : 문서 간의 계층 제공 단점 : 클러스터링 시간이 할당식 클러스터링에 비해 오래 걸림 병합식 클러스터링 첫 단계에서 각 문서가 각각의 클러스터를 형성한다고 가정 알고리즘이 진행 될수록 가장 가까운 문서끼리 병합 새로운 클러스터를 형성 분할식 모든 문서가 하나의 클러스터에 속한다고 가정 알고리즘 진행 매 단계별 유사도가 가장 작은 문서의 집합끼리 분할

9 문서 클러스터링 알고리즘 (계층적 클러스터링)
단순한 병합식 클러스터링 알고리즘 문서의 개수만큼 클러스터를 생성하여 각 문서가 각 클러스터로 각각 할당되도록 한다. 각 클러스터의 중심은 자신이 포함하고 있는 문서가 된다. = 모든 클러스터 간의 유사도를 계산한다 = 가장 가까운 두 클러스터를 하나로 병합 = 병합된 두 클러스터를 유사도 행렬에서 제외하고 새로 만들어진 클러스터와 다른 클러스터와의 유사도를 계산하여 유사도 행렬을 갱신한다. 클러스터의 중심 벡터의 클러스터에 포함된 문서의 평균 벡터이다

10 문서 클러스터링 알고리즘 (할당식 클러스터링)
클러스터의 계층을 고려하지 않고 각 문서를 평면적으로 클러스터링하는 방법 미리 나누어질 클러스터의 개수를 예상하고 클러스터를 제공 문서 클러스터링에는 K-means 알고리즘을 많이 사용 기본적인 K-means 알고리즘 K개의 문서를 임의로 선택하여 초기 클러스터의 중심으로 할당. K개의 클러스터의 중심이 바뀌지 않을 때까지 다음과정 반복 = 나머지 모든 문서들을 가장 유사도가 높은 중심에 해당하는 클러스터로 할당 = 각 클러스터의 중심을 다시 계산