부산대학교 인공지능연구실 김민호 (karma@pusan.ac.kr) Text Categorization 부산대학교 인공지능연구실 김민호 (karma@pusan.ac.kr)

Presentation on theme: "부산대학교 인공지능연구실 김민호 (karma@pusan.ac.kr) Text Categorization 부산대학교 인공지능연구실 김민호 (karma@pusan.ac.kr)"— Presentation transcript:

1 부산대학교 인공지능연구실 김민호 (karma@pusan.ac.kr)
Text Categorization 부산대학교 인공지능연구실 김민호

2 내용 문서 표현 (Document Representation) 유사도 측정 (Similarity Measure)
문서 클러스터링 (Document Clustering) 문서 범주화 (Text Categorization) 정보 필터링 (Information Filtering) 사건 탐색 (Topic Detection) 사건 추적 (Topic Tracking)

3 비 교 문서 클러스터링 vs 문서 범주화 문서 클러스터링 vs 주제 탐색 문서 범주화 vs 정보 필터링

4 문서 표현 Document Representation
어휘 추출 어휘의 가중치 계산

5 문서 공간 다차원 공간(multi-dimensional space)에 문서(document)를 벡터(vector)로 표현
각 문서를 하나의 점으로 표현 각 차원(dimension) 어휘(term)나 개념(concept) system retrieval information Doc2 Doc1 Doc6 Doc5 Doc3 Doc4 query

6 문서 표현 문서의 내용을 표현해 줄 수 있도록 가공 중요한 어휘들과 그것의 중요도로 표시 어휘들의 개념/의미적으로 표현
이 논문에서는 장식체를 위한 새로운 렌더링 (rendering)방법을 제안한다. More than 150 former officers of the overthrown South Vietnamese government have been released from a re-education camp after 13 years of detention, the official Vietnam News Agency reported Saturday.

7 어휘 추출 한국어 영어 형태소 해석 명사 등 중요 품사 어휘 추출 불용어 제거 불용어(stop word) 제거
학교/ncn + 에서/jca -> 학교 불용어 제거 명사 등 이외의 품사를 갖는 어휘들 영어 불용어(stop word) 제거 a, the, this, … 어간화(stemming) swimming, swims, swimmer –> swim flowers –> flower 프로그램 소스 [IR92,pp.151~160] William B. Frakes, Information Retrieval – Data Structures & Algorithms, Prentice-Hall, 1992.

8 어휘의 가중치 계산 문서에 포함된 각 어휘의 중요도를 측정 이 논문에서는 장식체를 위한 새로운 렌더링 문 서
(rendering)방법을 제안한다. 문 서 이/mmd 논문/ncn+에서/jca+는/jxc 장식체/ncn+를/jco 위하/pvg+ㄴ/etm 새롭/paa+ㄴ/etm 렌더링/ncn (/sl rendering/f )/sr 방법/ncn+을/jco 제안/ncpa+하/xsv+ㄴ다/ef ./sf 형태소 해석 논문 장식체 렌더링 render 방법 0.007 제안 문서 벡터 <단어, 가중치>

9 가중치 계산 어휘의 중요도를 반영하는 요소 어휘가 그 문서에 몇 번이나 나타났는가?
많이 나타날수록 문서에서의 중요도가 높다 단어 빈도수 어휘가 흔하게 사용되는 것인가?전문적인 것인가? 전문적으로 사용되는 어휘일수록 중요도가 높다 역 문서 빈도수 문서의 길이의 길고 짧은 것 짧은 문서에 2번 나타난 것과 긴 문서에 2번 나타난 것을 동일하게 취급? 문서 길이의 정규화

10 가중치 계산 기법 (weighting scheme)
가중치 계산 요소들 어휘 빈도수 (tf: term frequency) 역 문서 빈도수(idf: inverse document frequency) tfidf 가중치 기법 문서에 어휘 t 가 나타난 빈도수 N : 전체 문서의 개수 dft : 어휘 t 를 포함하는 문서의 개수

11 SMART 가중치 계산 기법 가중치 반영 요소 가중치 계산 기법 단어 빈도수 (term frequency) 문서 빈도수
(doc. frequency) 정규화 (normalization) 가중치 계산 기법 nnn nnc ntn ntc ann anc atn atc lnn lnc ltn ltc

12 실제 구현 - 문서 표현 문서 벡터 실제 문서 벡터 표현 N차원: 전체 어휘의 개수가 N개 문서에 나타난 어휘들로만 표현
d d2 논문 연구 주제 장식체 렌더링 render 방법 제시 제안 … 0.007 0.047 0.041 0.034 0.008 0.002 0.003 0.015 0.041 0.007 문서 벡터 N차원: 전체 어휘의 개수가 N개 표현: <가중치> 문서에 나타나는 어휘 수는 적음 대부분이 0의 값을 갖게 됨 실제 문서 벡터 표현 문서에 나타난 어휘들로만 표현 표현: <어휘, 가중치> 유사도 계산을 할 때 같은 차원의 어휘인가를 비교 d d2 논문 장식체 0.047 렌더링 0.041 render 0.034 방법 제안 연구 주제 장식체 0.015 렌더링 0.041 제시

13 실제 구현 - 문서 표현 문서 표현 과정 각 문서에 대해, 어휘의 빈도수 추출 전체 문서에 대해, 각 어휘의 df값 계산
어휘 추출 문서를 <어휘, 빈도수>벡터로 표현 전체 문서에 대해, 각 어휘의 df값 계산 문서에 나타났으면 +1 각 문서에 대해, 어휘의 가중치 계산 tfidf 가중치 계산 기법으로 문서를 <어휘, 가중치> 벡터로 표현 유사도 계산을 할 때, 같은 차원의 어휘가 문서에 있는지를 빠르게 비교하기 위해 어휘들을 정렬 d d2 < render0.034 논문 렌더링 방법 장식체 0.047 제안 렌더링 연구 장식체 제시 주제 문서 d1의 render는 문서 d2의 모든 어휘와 비교하지 않고도 존재하지 않는 어휘임을 알 수 있음

14 가중치 계산 기법의 영향 정보 검색에서 가중치 계산 기법을 다르게 적용 가중치 계산 기법은 정보 검색 성능에 영향 미침
질의에 대한 문서의 유사도가 변함 검색결과 제시에서 문서의 우선순위(rank)가 변함 가중치 계산 기법은 정보 검색 성능에 영향 미침 가중치 기법에 따른 성능의 변화 비교 [Lee, SIGIR 95] 다양한 가중치 기법을 적용해서 검색된 결과의 조합으로 성능 향상 [Lee, SIGIR 96]

15 유사도 측정 Similarity Measure

16 유사도 측정 방법 유사도 측정 유사도 측정 방법 (similarity measure) 두 문서 사이의 관련 정도를 계산
코사인 계수 (Cosine coefficient) 자카드 계수 (Jaccard coefficient) 다이스 계수 (Dice coefficient) 유클리디언 거리 (Euclidean distance) 벡터 내적 곱 (vector inner product)

17 유사도 측정 방법 코사인 계수 (Cosine coefficient) 유사도 값이 0~1 사이의 값을 가짐
1: 모든 어휘의 가중치가 동일한 문서 0: 두 문서에서 공유하는 어휘가 없는 문서 di 벡터 dj 벡터

18 유사도 측정 방법 자카드 계수 (Jaccard coefficient) 다이스 계수 (Dice coefficient)

19 유사도 측정 방법 내적의 곱 (inner product) 유클리디언 거리 (Euclidean distance)
정보검색에서 질의-문서 유사도 계산 그룹 평균 링크 기법의 클러스터링에서 이용 유클리디언 거리 (Euclidean distance) Ward 기법의 클러스터링에서 이용 거리 값이 작을수록 두 문서가 유사함

20 유사도 측정 방법 두 단어의 유사도 측정 코사인 계수 자카드 계수 다이스 계수

21 유사도 측정 방법 유사도 측정 방법과 클러스터링 클러스터링 기법에 따라 특정 유사도 측정 방법을 이용해야 하는 경우 있음
Ward 기법 유클리언 거리를 이용한 문서들의 거리 측정 그룹 평균 기법 내적의 곱으로 유사도 계산 클러스터링에 드는 시간을 줄이기 위해서 Voorhees 제시 유사도 측정 방법에 따라 클러스터에 속하는 멤버들이 달라질 수 있음

22 유사도 측정 방법의 영향 정보검색에서 클러스터링에서 유사도 측정 방법에 따라 성능의 변화 발생
공기정보를 이용해서 용어간 유사도를 측정하여 정보검색에서 질의 확장 [김명철, 1999] 유사도 측정 방법에 따라 성능 변화를 비교 자카드 계수, 다이스 계수, 코사인 계수, 평균 조건 확률, 상호 정보 등 클러스터링에서 유사도 측정 방법에 따라 유사도 값이 달라짐 클러스터에 속하는 멤버들이 달라질 수 있음 클러스터링 기법에 따라 특정 유사도 측정 방법을 요구하는 경우도 있음

23 문서 범주화 Text Categorization

24 문서 범주화 문서를 두개 이상의 이미 정해진 범주로 분류하는 작업 (Lewis 1992) ? 문서 분류기 … 경제 문서 정치
과학

25 문서 범주화 <id> 15219 <title> 유동식 流動食 <contents> 식품 영양
환자 음식의 한 가지. 흐름 음식이라고도 한다. 유동식은 음식을 삼키기 어려운 환자, 수술 후의 환자 또는 급성 고열 환자 등 영양소를 농축한 액체 음식이 필요할 때 쓰이며, 맑은 유동식과 전 유동식이 있다. ① 맑은 유동식 : 수술 후의 환자에게 수분 공급을 위한 음식물로서 탄수화물과 물로만 이루어져 짧은 기간만 이용한다. 종류에는 보리차, 탄산 음료, 과즙, 채소즙, 기름기가 없는 맑은 국류 등이 있다. ② 전 유동식 : 소화 기능이 극히 약한 환자나 음식을 삼키기 어려운 수술 후의 환자에게 주는 음식물이다. 전 유동식은 맑은 유동식과 연식의 중간으로 완전 영양을 유지하기가 어려우므로 보통 1주일 이내에 연식으로 바꾸어야 한다. 그 종류에는 우유, 크림, 죽, 젤리, 푸딩, 달걀찜 따위가 있다. 식품 영양 건강과 의학 … … …

26 문서 범주화 연구 자질 추출기 (feature extractor) 문서 분류기 (text classifier)
문서 분류의 근거가 되는 자질을 추출 문서 분류기 (text classifier) 자질에 근거해서 범주를 결정 자질 추출기 문서 분류기 범주 할당 정해진 범주 자질표현 범주1 범주2 범주n … 학습 추출된 자질

27 자질 추출 문서분류를 위한 좋은 자질의 특성 [Lewis 1992] 통계 기반 기계학습을 위해서 이상적인 문서표현을 위해
자질의 수가 많지 않아야 한다 적절한 빈도수로 나타나야 한다 (자료희귀 문제) 중복이 적어야 한다 (동의어 인식) 이상적인 문서표현을 위해 할당될 범주와 의미적 관련이 있어야 한다 언어적 중의성이 없어야 한다

28 자질 추출 단일어 자질 [Fagan 1987] 자질 추출이 간단하다 비교적 좋은 성능을 보인다
문서는 그 안에 나타나는 단어들의 집합으로 표현될 수 있다는 가정에서 단일어를 문서의 자질로 표현 자질 추출이 간단하다 비교적 좋은 성능을 보인다 구문적, 의미적 관계 표현이 어렵다 언어적 중의성 발생 자료희귀 문제 발생 학습문서의 수가 작을 경우 단일어에 대한 범주추정이 어렵다

29 자질 추출 구문어구 자질 [Lewis 1992] 언어적 중의성이 적다 자료희귀 문제 발생 의미적 관계 표현이 어렵다
구문분석을 통해 문법적 어구를 문서의 자질로 표현함 언어적 중의성이 적다 ‘black market’, ‘유령 회사’ 자료희귀 문제 발생 출현 빈도수가 적어 학습이 어렵다 의미적 관계 표현이 어렵다

30 자질 추출 클러스터 자질 단어 클러스터링 [Li1997,Guthrie1994,Baker 1998]
단어의 분포에 따라 클러스터링 kick, goal, ball 여러 클러스터에 속할 수 있는지에 따라 구분 Hard clustering vs. Soft clustering 구문어구 클러스터링 [Lewis 1992, 장병규 1997] 구문어구, 연어의 분포에 따라 클러스터링 자료희귀 문제를 보완 단일어에 비해 높은 성능향상을 보이지 않음

31 wordnet: http://wordnet.princeton.edu/
자질 추출 시소러스를 이용한 문서분류 [강원석 1999] 자질표현: 의미 벡터 의미를 150개로 분류 일반 의미 87개 영역 의미 63개 단어 3,990개에 대해 의미 코드 부여 용어의 의미를 찾아 의미벡터를 이용 학습문서에 의해서 범주별 의미벡터 생성 문서-범주 의미벡터의 유사도에 따라 범주 할당 유사도 계산: 크로스 엔트로피 시소러스 구축이 힘들다 wordnet:

32 자질 차원의 크기 자질 공간은 높은 차원을 가진다 자질의 수가 많으면 자질의 선택
문서집합에서 발견되는 하나의 유일한 용어에 대해 하나의 차원이 존재 자질의 수가 많으면 보다 많은 정보를 제공한다 계산할 양이 너무 많아지므로 학습이 어려워진다 자질의 선택 자질의 차원을 감소한 후, 문서 분류기 이용

33 자질 차원의 축소 2 를 이용한 자질 순위화 [Devore 1995] 2 값이 클수록 두 사건이 관련 있다
두 사건의 독립성 여부를 판단하는 통계적인 방식 ‘어떤 문서가 범주에 관련이 있다’ ‘어떤 자질이 그 문서에 나타났다’ 두 사건이 독립적이면 그 자질은 범주화에 영향을 미치지 않는다고 판단한다 2 값이 클수록 두 사건이 관련 있다

34 자질 차원의 축소 2 계산을 위한 분할표 만들기 각 범주에 대해서 적합한 문서들 부적합 문서들
관련있다 관련없다 나타났다 a b 나타나지 않았다 c d 문서가 범주와 자질이 문서에 2 계산을 위한 분할표 만들기 각 범주에 대해서 적합한 문서들 각 문서에 나타난 각 용어들의 a값을 누적 부적합 문서들 각 문서에 나타난 각 용어들의 b값을 누적 a+c = 해당 범주에 속하는 적합 문서의 개수 (R) a+b = 해당 용어의 문서 빈도수 값 (df) a+b+c+d = 전체 학습문서의 개수 (N)

35 (a+c)(b+d)(a+b)(c+d)
자질 차원의 축소 2 를 이용한 자질 순위화 [Devore 1995] 분할표에 나타난 값을 이용 2 값이 가장 큰 몇 개의 자질을 실제로 이용 자질의 크기에 변화를 주었을 때, 성능 비교 연구 관련있다 관련없다 나타났다 a b 나타나지 않았다 c d 문서가 범주와 자질이 문서에 2 = (a+b+c+d) (ad-bc)2 (a+c)(b+d)(a+b)(c+d)

36 문서 분류기 최근접 이웃 분류기 (k-Nearest Neighbors)
문서-범주벡터 관련도 (Linear Text Classifiers) Rocchio 알고리즘 결정 트리(Decision Tree) 지지벡터기계 (Support Vector Machines) 베이지언 확률 (Bayesian classifier) 신경망 (Neural Network classifier) 수작업 분류 규칙 생성 사람이 직접 문서분류 규칙을 작성

37 최근접 이웃 분류기 K-최근접 이웃(k-Nearest Neighbors) Memory-Based Reasoning 방식
예제 기반 학습 방법 학습문서에 있는 문서들은 범주가 이미 결정되어 있음 <d1, C1>, <d2, Ck>,<d3, C1,C2>, … 새로운 문서 d 의 범주를 결정할 때 학습 문서들 중에서 새로운 문서 d 와 유사도가 가장 높은 순서인 k개의 문서(k-최근접 이웃)가 어떠한 범주에 속해 있는지에 기반해서 결정 최근접 이웃들이 속하는 범주로 할당

38 최근접 이웃 분류기 K-NN 분류 알고리즘 [1] 새로운 문서와 모든 학습문서와의 유사도 계산
새로운 문서의 범주로 결정 … 범주1 범주n 문서 d 학습 문서

39 최근접 이웃 분류기 성능 변화 k의 값에 따라 성능이 달라짐 학습문서의 개수 k의 변화에 따른 비교 실험
학습문서 수가 많을수록 분류의 정확성은 높아짐 문서 범주화를 위한 시간은 길어진다

40 Liner Text Classifiers
문서-범주 벡터 관련도 기반 분류기 Liner Text Classifiers 벡터 유사도 계산에 의한 분류 각 범주에 대해 범주 벡터를 생성 문서 벡터-범주 벡터의 유사도 계산 가장 관련도가 높은 범주를 문서의 범주로 결정 임계치를 기준으로 해서 범주 할당 … 범주1 범주n 문서

41 문서-범주 벡터 관련도 기반 분류기 범주 벡터 생성 정확한 임계치 선택 범주 벡터의 가중치에 영향을 받음
가중치 벡터 학습 [Lewis 1996] Rocchio algorithm Widrow-Hoff algorithm EG(Exponentiated-gradient) algorithm 정확한 임계치 선택

42 Rocchio 알고리즘 적합성 피드백에 의한 질의 생성 알고리즘 최적의 질의 벡터 생성
아주 성공적인 프로파일 학습 알고리즘의 하나 최적의 질의 벡터 생성 적합한 문서에 대해서는 질의-문서 유사도를 최대화 시킴 부적한 문서에 대해서는 질의-문서 유사도를 최소화 시킴 R: 적합한 문서들의 개수 N: 전체 문서의 개수

43 Rocchio 알고리즘 벡터공간 관점에서는, 질의 벡터를 개선된 Rocchio 알고리즘 부적합 벡터들로부터는 멀리
적합 벡터들과는 더 가깝게 이동 시킴 개선된 Rocchio 알고리즘 원래 질의의 관점을 유지하기 위해서 원래 질의 벡터를 반영 , ,  값에 따라 성능 비교

44 결정 트리 [Decision Tree] 분류기
C4.5 [Quinlan 1993] 결정 트리는 학습결과의 해독 가능하다 학습결과를 이용해 규칙생성 가능 어떤 자질이 어떤 효과를 발휘하는지 분석 용이 과잉학습을 방지하기 위해 가지치기(pruning) 수행가능 이진 분류기 문서가 이 범주에 속하는지/속하지 않는지 결정 하나의 범주에 하나의 결정 트리 학습 결정 트리의 각 노드 특정 자질이 문서에 나타나는지의 여부 또는 빈도

45 결정 트리 학습 방식 예 골프를 치러갈 것인지를 결정 클래스: Play, Don't Play. 학습 문서: 속성과 값
outlook: sunny, overcast, rain. temperature: continuous. humidity: continuous. windy: true, false. 학습 문서: sunny, 85, 85, false, Don't Play sunny, 80, 90, true, Don't Play overcast, 83, 78, false, Play rain, 70, 96, false, Play rain, 68, 80, false, Play rain, 65, 70, true, Don't Play overcast, 64, 65, true, Play sunny, 72, 95, false, Don't Play sunny, 69, 70, false, Play rain, 75, 80, false, Play sunny, 75, 70, true, Play overcast, 72, 90, true, Play overcast, 81, 75, false, Play rain, 71, 80, true, Don't Play Decision Tree: outlook = overcast: Play outlook = sunny: | humidity <= 75 : Play | humidity > 75 : Don't Play outlook = rain: | windy = true: Don't Play | windy = false: Play

46 문서 분류 시스템 - 공개용 지지벡터기계(Support Vector Machines)
학습문서가 나타내는 패턴에서 자동으로 지지벡터(SV)를 생성, 지지벡터를 이용하여 최적의 경계를 결정 SVMlight C로 구현, 개발팀: University of Dortmund, Informatik, AI-Unit Collaborative Research Center on 'Complexity Reduction in Multivariate Data' (SFB475) svm_learn 학습문서의 패턴을 파악하여 자동으로 지지벡터를 생성 svm_classify 새로운 문서에 대해서 지지벡터를 이용하여 범주에 속하는지/아닌지 +1/-1로 결정

47 문서 분류 시스템 - 공개용 Rainbow 시스템 통계적 텍스트 분류 프로그램 Andrew McCallum [CMU]
Naive Bayes k-nearest neighbor Rocchio Maximum Entropy Andrew McCallum [CMU]

48 한국어 – 문서 범주화 실험 집합 계몽 문서분류 실험 집합 문서 개수 23,113개, 대분류 12개, 소분류 76개 범주 12
0100. 철학 0200. 종교 0300. 사회 0400. 과학 0500. 생물 0600. 산업 0700. 예술 0800. 어학 0900. 문학 1000. 지리 1100. 역사 1200. 스포츠.레저 0401. 과학 일반 0402. 수학 0403. 물리학 0404. 화학 0405. 천문·우주 과학 ... 범주 76 0601. 산업 일반 0602. 기술·가전 0603. 건강과 의학·인체 농업 0605. 조선·수산업 0606. 임업·목축업 0607. 광업 0608. 공업 0609. 토목·건설 교통 ...

49 사건 탐색 Topic Detection

50 TDT Evaluation Project
TDT(Topic Detection & Tracking) 주제적으로 관련있는 문서들을 발견, 새로운 주제를 찾아내고, 관심있는 사건의 문서를 분류, 방송뉴스를 분리하는 것 DARPA지원, TIDES(Translingual Information Detection, Extraction, and Summarization) 프로그램 TDT1에는 3개 연구그룹 참여( CMU, Umass, Dragon systems), TDT4에는 다수의 연구그룹이 참여 매일 연속적으로 나오는 신문기사와 방송뉴스를 처리 영어와 표준 중국어 1999년에 처음 시작되어, 2004년까지 평가 개최

51 TDT Evaluation Project
5개 응용 분야 Story Segmentation - Detect changes between topically cohesive sections Topic Tracking - Keep track of stories similar to a set of example stories Topic Detection - Build clusters of stories that discuss the same topic First Story Detection - Detect if a story is the first story of a new, unknown topic Link Detection - Detect whether or not two stories are topically linked

52 주제 (topic) 사건 (event)의 의미에 가까움 기존의 정보검색에서의 주제와는 다름
어떤 장소에서, 어떤 시간에 발생한 구체적인 것 ‘USAir-427 추락’ : 사건 ‘비행기 사고’ : 사건 아님

53 정보 검색 vs 사건 탐색 정보 검색 사건 탐색 사용자가 질의(query)를 직접 생성해야 함
어떤 새로운 일이 발생했는지를 모를 때는 질의 생성 못함 사건 탐색 새로운 사건의 발생을 탐색, 유사한 사건을 묶어서 제시 어떤 새로운 일이 벌어졌는지? 예전에 발생했던 것과 유사한 일이 일어났는지? 사용자가 생각하지 못한 주제에 대한 사건을 알 수 있게 됨 정보 이용자들에게 기존의 정보검색과는 달리 새로운 측면에서의 정보획득을 가능하게 한다

54 사건 탐색 vs 사건 추적 사건 탐색 사건 추적 특정 주제를 미리 정하지 않음 학습 문서가 없음 특정 주제를 미리 정함
학습 문서가 있음

55 사건 탐색 vs 새로운 사건 탐색 사건 탐색 새로운 사건 탐색 문서들의 사건을 탐색하는 것
문서가 새로운 사건의 시작인지/아닌지 탐색

56 문서 클러스터링 vs 사건 탐색 문서 클러스터링 사건 탐색 전체 문서 집합에 대한 모든 유사도를 고려
임의의 클러스터 생성, 학습문서가 필요하지 않음 문서 클러스터링 전체 문서 집합에 대한 모든 유사도를 고려 사건 탐색 동적으로 변하는 사건을 탐색 전체 문서 집합에 대한 모든 유사도를 고려 않음 현재까지 클러스터 생성에 참여한 문서들만 고려 점진적 클러스터링

57 사건 탐색 알고리즘 점진적 클러스터링 T1 T1 T1 T1 T1 T2 … 첫번째 문서로 하나의 클러스터 형성
d1 d … dN … T1 d1 첫번째 문서로 하나의 클러스터 형성 T1 T1 T1 d2 T1 T2 문서와 클러스터 유사도가 임계치 이하인 경우 문서와 클러스터 유사도가 임계치 이상인 경우

58 사건 탐색 알고리즘 클러스터 멤버로 포함시킬 기준 선택 임계치(threshold) 이상인 클러스터들에 대해
모든 클러스터의 멤버로 결정 ? 가장 높은 유사도를 갖는 클러스터의 멤버로 결정 ? … T1 T2 T3 Tm di … T1 T2 T3 Tm di 모든 클러스터 가장 높은 유사도를 갖는 클러스터

59 점진적 클러스터링 알고리즘 입력 순서: d1, d2, …, dN 첫번째 문서로 첫 클러스터를 형성 (d1  T1)
입력 문서 2~N까지 문서에 대해서 (d2, …, dN) 이미 형성된 각 클러스터에 대해서 (T1, T2, … Tk) 클러스터 벡터와 현재 문서 벡터의 유사도 계산 임계치 이하이면, 새로운 클러스터 생성 현재 문서 하나로 된 새로운 클러스터 Tk+1 생성 임계치 이상이면, 기존의 클러스터에 포함시킴 가장 유사도가 높은 클러스터의 멤버로 포함 또는, 모든 클러스터의 멤버로 포함 새로 생성/변경된 클러스터의 중심 벡터를 생성/변경

60 결 론

61 비 교 문서 클러스터링 vs 문서 범주화 문서 클러스터링 vs 사건 탐색 문서 클러스터링: 임의의 클러스터를 생성함
문서 범주화: 범주를 미리 결정, 학습문서 필요 문서 클러스터링 vs 사건 탐색 임의의 클러스터 생성 사건 탐색은 동적으로 변하는 사건을 탐색 사건 탐색은 점진적 클러스터링 문서 클리스터링: 전체 문서집합의 유사도를 고려

62 비 교 문서 범주화 vs 정보 필터링 문서 범주화 vs 사건 추적 범주 또는 사용자 관심 미리 결정(학습문서 필요)
정보 필터링: 사용자의 프로파일이 범주가 됨 문서 범주화 vs 사건 추적 범주 또는 사건을 미리 정해둠 (학습문서 필요) 사건 추적은 동적으로 변하는 사건을 추적