10장. 군집화 오일석, 패턴인식, 교보문고, 2008. © 오일석, 전북대학교 컴퓨터공학.

Slides:



Advertisements
Similar presentations
목성에 대해서 서동우 박민수. 목성 목성은 태양계의 5 번째 궤도를 돌고 있습니다. 또 한 태양계에서 가장 큰 행성으로 지구의 약 11 배 크기이며, 지름이 약 14 만 3,000km 이다. 목성은 태양계의 5 번째 궤도를 돌고 있습니다. 또 한.
Advertisements

2. 속력이 일정하게 증가하는 운동 Ⅲ.힘과 운동 2.여러 가지 운동. 도입 Ⅲ.힘과 운동 2. 여러 가지 운동 2. 속력이 일정하게 증가하는 운동.
1. 도형의 연결 상태 2. 꼭지점과 변으로 이루어진 도형 Ⅷ. 도형의 관찰 도형의 연결상태 연결상태가 같은 도형 단일폐곡선의 성질 연결상태가 같은 입체도형 뫼비우스의 띠.
1.3.1 원의 방정식. 생각해봅시다. SK 텔레콤에서는 중화동에 기지국을 세우려고 한다. 이 기지국은 중화고, 중화우체국, 뚝방에 모두 전파를 보내야 한다. 기지국은 어디에 세워야 할까 ? 중화동의 지도는 다음과 같다 원의 방정식.
알고리즘 기본 개념 정렬 알고리즘 탐색 알고리즘 알고리즘 복잡도.
4장 배열과 함수 한빛미디어(주).
컴퓨터와 인터넷.
재료수치해석 HW # 박재혁.
의사 결정 트리(decision tree)
• 수학 • 6학년 나단계 • 7. 연비>1/9 홈 두 수의 대응 관계를 , 를 사용한 식으로 나타내기 수업활동 수업계획.
제2장 주파수 영역에서의 모델링.
패턴인식 개론 Ch.8 클러스터링.
Entity Relationship Diagram
11장. 최적화 알고리즘 오일석, 패턴인식, 교보문고, © 오일석, 전북대학교 컴퓨터공학.
Report #2 - Solution 문제 #1: 다음과 같이 프로그램을 작성하라.
10장 랜덤 디지털 신호처리 1.
NLP Lab. 세미나 발표자:이주호 2007년 7월 18일 수요일
실험 3 - 비선형 연산 증폭기 회로와 능동 필터 전자전기컴퓨터공학부 방 기 영.
오브젝트 조합 회로 IT CookBook, VHDL을 이용한 디지털 회로 입문.
Chapter 02 순환 (Recursion).
디지털영상처리 및 실습 대구보건대학 방사선과.
오일석, C와 ALPS, 장. C로 풍덩 © 오일석, 전북대학교 컴퓨터공학.
실험1. 연산 증폭기 특성 전자전기컴퓨터공학부 방기영.
11장. 포인터 01_ 포인터의 기본 02_ 포인터와 Const.
SqlParameter 클래스 선문 비트 18기 발표자 : 박성한.
Multimedia Programming 10: Point Processing 5
멀티미디어 시스템 (아날로그 이미지,신호를 디지털로 변환 방법) 이름 : 김대진 학번 :
C#.
9장. 특징 선택 오일석, 패턴인식, 교보문고, © 오일석, 전북대학교 컴퓨터공학.
빅데이터 연구회 6주차 발표 주제 : 서포트 벡터 머신 통계학과 서태석.
자바 5.0 프로그래밍.
프로그래밍 개요
어서와 C언어는 처음이지 제14장.
군집 분석.
자료구조: CHAP 7 트리 –review 순천향대학교 컴퓨터공학과 하 상 호.
3 장. 확률 분포 추정 오일석, 패턴인식, 교보문고,
컴퓨터 프로그래밍 기초 - 10th : 포인터 및 구조체 -
8장. spss statistics 20의 데이터 변환
밀도 (1) 부피가 같아도 질량은 달라요 ! 밀도의 측정 밀도의 특징.
Decision Tree & Ensemble methods
5 장. SVM 오일석, 패턴인식, 교보문고, © 오일석, 전북대학교 컴퓨터공학.
보고서 #7 (기한: 6/2) 2개의 스택, stk1, stk2를 이용하여 큐를 구현하라.
Clustering Algorithm KUT Youn-Hee Han.
수학10-나 1학년 2학기 Ⅰ. 도형의 방정식 2. 직선의 방정식 (9/24) 점과 직선 사이의 거리 수업계획 수업활동.
계산기.
VHDL를 이용한 DES 설계 정보통신컴퓨터공학부 5조 김인옥, 백미숙
알고리즘 알고리즘이란 무엇인가?.
클러스터 시스템에서 효과적인 미디어 트랜스코딩 부하분산 정책
에어 PHP 입문.
2. 누화와 케이블링 1. 서론 2. 용량성 누화 3. 유도성 누화 4. 복합적인 누화(누화의 일반적인 이해)
문서 클러스터링 일본언어문화학과 서동진.
4장. 데이터 표현 방식의 이해. 4장. 데이터 표현 방식의 이해 4-1 컴퓨터의 데이터 표현 진법에 대한 이해 n 진수 표현 방식 : n개의 문자를 이용해서 데이터를 표현 그림 4-1.
작도 작도 작도: 눈금 없는 자와 컴퍼스만을 사용하여 도형을 그리는 것
Homework #12 (1/2) 프로그램을 작성하고, 프로그램과 실행 결과를 프린트하여 제출한다.
쉽게 배우는 알고리즘 2장. 점화식과 점근적 복잡도 분석
3. 모듈 (5장. 모듈).
9 장 오류 검출 및 오류 정정 9.1 오류 종류 9.2 검출 9.3 오류 정정 9.4 요약.
9 브라우저 객체 모델.
컴퓨터공학과 손민정 Computer Graphics Lab 이승용 교수님
제 3장. Regular Languages 와 Regular Grammars
트리 (Logical) Data Structures Linear list Tree Graph Linear structures
2 장. 베이시언 결정 이론 오일석, 패턴인식, 교보문고,
3 장. 확률 분포 추정 오일석, 패턴인식, 교보문고,
전류의 세기와 거리에 따른 도선 주변 자기장 세기 변화에 대한 실험적 고찰
SEOUL NATIONAL UNIVERSITY OF SCIENCE & TECHNOLOGY
컴퓨터는 어떻게 덧셈, 뺄셈을 할까? 2011년 10월 5일 정동욱.
아날로그 신호를 디지털 신호로 변환하는 A/D 변환기 A/D 변환 시 고려하여 할 샘플링 주파수 D/A 변환기
C++ Espresso 제15장 STL 알고리즘.
7 생성자 함수.
6 객체.
Presentation transcript:

10장. 군집화 오일석, 패턴인식, 교보문고, 2008. © 오일석, 전북대학교 컴퓨터공학

군집화clustering 구현에는 두 가지 필요 들어가는 말 패턴인식 문제로 공식화 가능 고객이 샘플, 샘플은 특징 벡터 x=(x1,x2,…,xd)T로 표현 직업, 월평균 구매액 등이 특징이 됨 유사한 (거리가 가까운) 샘플 집합을 군집이라 함 군집화clustering 구현에는 두 가지 필요 1) 거리 척도, 2)유사한 샘플을 군집으로 만드는 알고리즘 2019-04-15

들어가는 말 지도 학습 과 비지도 학습 지도 학습supervised learning 2~7장에서 공부한 분류기 학습 (MLP, SVM, HMM 등) 각 샘플이 그가 속한 부류를 알고 있다. (훈련 집합 X={(x1,t1), (x2,t2), …, (xN,tN)}으로 표기) 비지도 학습 unsupervised learning 샘플은 부류 정보가 없다. (X={x1, x2, …, xN}으로 표기) 군집화는 비지도 학습에 해당 군집이 몇 개인지 모르는 경우도 많다. 군집화를 부류 발견 작업이라고도 부른다. 2019-04-15

들어가는 말 군집화의 특성 주관성: 군집화 결과의 품질은 응용이 처한 상황과 요구 사항에 따라 다름 2019-04-15

10.1 정의 2019-04-15

10.2 거리와 유사도 2019-04-15

10.2.1 특징 값의 종류 특징 값의 종류는 다양하다. (군집화를 공부하는데 이에 대한 이해가 필요하다.) 2019-04-15

고객 레코드 (샘플)을 12개의 특징으로 표현한다고 하자. 2019-04-15

10.2.2 거리와 유사도 측정 Hamming 거리 Minkowski 거리 (10.4) 두 점 xi=(xi1,…,xid)T와 xj=(xj1,…,xjd)T간의 거리 척도 p=2면 유클리디언 거리 (10.5), p=1이면 도시블록 거리 (10.6) Hamming 거리 이진 특징 벡터에 적용 가능 (서로 다른 비트의 개수) 예) (1,0,1,0,0,0,1,1)T과 (1,0,0,1,0,0,1,0)T의 해밍 거리는 3 2019-04-15

10.2.2 거리와 유사도 측정 이진 특징 벡터의 유사도 유사도와 거리는 쉽게 상호 변환할 수 있다. 코사인 유사도 문서 검색 응용에서 주로 사용 (단어가 특징, 출현 빈도가 특징 값) 이진 특징 벡터의 유사도 유사도와 거리는 쉽게 상호 변환할 수 있다. 2019-04-15

10.2.3 점 집합을 위한 거리 점과 군집 사이의 거리 (모든 샘플이 참여) 여기에서는 점과 점 집합 또는 두 점 집합 간의 거리 (10.2.2 절은 두 점간의 거리 정의) 점 xi와 군집 (점 집합) cj 간의 거리를 D(xi,cj)로 표기 두 군집 ci 와 cj 간의 거리는 D(ci,cj)로 표기 점과 군집 사이의 거리 (모든 샘플이 참여) dik는 xi와 yk는 간의 거리 (yk는 cj에 속한 샘플) Dmax와 Dmin은 외톨이에outlier 민감 2019-04-15

10.2.3 점 집합을 위한 거리 점과 군집 사이의 거리 (대표 샘플만 참여) 평균을 대표로 삼음 다른 것들과 가장 가까운 샘플을 대표로 삼음 2019-04-15

(rep=3이 됨) 2019-04-15

10.2.3 점 집합을 위한 거리 두 군집 사이의 거리 dkl는 xk와 yl 간의 거리 (xk는 ci, yl은 cj에 속한 샘플) 2019-04-15

10.2.4 동적 거리 샘플마다 특징 벡터의 크기가 다른 경우 예) 온라인 필기 인식, DNA 열 (6.3 절의) 교정 거리 활용 2019-04-15

10.3 군집화 알고리즘의 분류 매우 다양한 알고리즘 군집화 문제의 본질적인 성질에 기인 (주관이 많이 개입되는 성질) 2019-04-15

10.3 군집화 알고리즘의 분류 분류 체계 계층 군집화: 군집 결과를 계층을 나타내는 덴드로그램으로 표현 분할 군집화: 각 샘플을 군집에 배정하는 연산 사용 신경망: SOM, ART 통계적 탐색: 시뮬레이티드 어닐링, 유전 알고리즘 등 2019-04-15

10.4 계층 군집화 2019-04-15

샘플 각각이 군집이 되어 출발, 유사한 군집을 모으는 작업을 반복 10.4.1 응집 계층 알고리즘 샘플 각각이 군집이 되어 출발, 유사한 군집을 모으는 작업을 반복 출력은 군집화 결과를 트리로 표현한 덴드로그램 2019-04-15

일곱 개의 샘플이 주어진 상황 (라인 1의) 초기화에 의해, 2019-04-15

루프를 반복하면, (거리 척도는 유클리언 거리와 Dmin을 가정) 연필을 들고 직접 계산해 보자. 직접 해보는 것의 힘은 생각보다 크다. Dmin대신 Dmax를 사용하면 어떻게 될까? 2019-04-15

사용하는 거리 척도에 따라 다른 이름의 알고리즘 10.4.1 응집 계층 알고리즘 사용하는 거리 척도에 따라 다른 이름의 알고리즘 Dmin 사용하면 단일 연결single-linkage, Dmax 사용하면 완전 연결complete-linkage, Dave 사용하면 평균 연결average-linkage 알고리즘 세 알고리즘의 동작 특성 단일 연결은 긴 군집, 완전 연결은 둥근 군집을 선호 (평균 연결은 중간) 예) 그림 10.10 2019-04-15

10.4.1 응집 계층 알고리즘 세가지 부연 설명 군집의 개수를 어떻게 알아낼까? 모든 군집화 알고리즘이 안고 있는 문제임 사용자가 지정 또는 자동 결정 (자동 결정은 어렵다.) 단일 연결과 완전 연결은 외톨이에outlier 민감 평균 연결은 외톨이에 덜 민감 계산 복잡도 세제곱에 비례하므로 효율적인 구현 필요 CURE, ROCK, CHAMELEON, BIRCH 등 [Xu05] 2019-04-15

10.4.2 분열 계층 알고리즘 분열 계층은 하향 방식top-down 모든 샘플이 하나의 군집으로 출발, 군집을 나누는 작업을 반복 (앞 절의 응집 계층은 상향 방식bottom-up: 샘플 각각이 군집이 되어 출발, 유사한 군집을 모으는 작업을 반복) 지수적 복잡도 2019-04-15

10.5 분할 군집화partitional clustering 다양한 알고리즘 순차 알고리즘 k-means 알고리즘 MST알고리즘 GMM 알고리즘 … 2019-04-15

10.5.1 순차 알고리즘 특성 군집 개수를 찾아준다. (대신 임계값을 설정해주어야 한다.) 순서에 민감하다. 빠르다 (선형 시간). 2019-04-15

10.5.2 k-means 알고리즘 특성 가장 널리 쓰인다. (직관적 이해. 구현 간편) 군집 개수를 설정해주어야 한다. 2019-04-15

7개 샘플을 k=3개의 군집으로 만드는 상황 초기화에 의해 (그림 10.12(a)), 라인 5에 의해 (그림 10.12(b)), 2019-04-15

세 번째 루프는 그 이전과 결과가 같다. 따라서 멈춘다. 결국 출력은 두 번째 루프를 실행하면 (그림 10.12(c)), 세 번째 루프는 그 이전과 결과가 같다. 따라서 멈춘다. 결국 출력은 2019-04-15

10.5.2 k-means 알고리즘 이론적 배경 (10.23)을 비용 함수로 하는 내리막 경사법의 일종 항상 지역 최적점으로 수렴한다. (전역 최적점 보장 못함) 초기 군집 중심에 민감 빠르다. 외톨이에 민감하다. (k-medoids는 덜 민감) (진파랑은 k-medoids, 연파랑은 k-means) 2019-04-15

샘플로부터 가우시언을 추정하고 그 결과에 따라 군집 배정 10.5.3 모델 기반 알고리즘 샘플로부터 가우시언을 추정하고 그 결과에 따라 군집 배정 가우시언 추정은 EM 알고리즘을 사용할 수 있다. 2019-04-15

10.6 신경망 신경망 지도 학습: 퍼셉트론, 다층 퍼셉트론 (4 장) 비지도 학습 (군집화): SOM, ART (10 장) 2019-04-15

자기 조직화 맵self-organizing map (SOM) 10.6.1 자기 조직화 맵 자기 조직화 맵self-organizing map (SOM) 샘플들을 상호 비교하며 스스로 군집을 조직해 냄 경쟁 학습을 사용 하나의 샘플이 입력되면 여러 대표 벡터가 경쟁 가장 가까운 벡터가 승자가 되어 그것을 취함 (승자 독식 전략) 승자는 그 샘플에 적응하는 방향으로 벡터 값을 조금 변화시킴 2019-04-15

2019-04-15

10.6.1 자기 조직화 맵 SOM 학습 규칙 (10.25)에 의해 wnew는 wold보다 x에 가깝게 된다. 2019-04-15

2019-04-15

2019-04-15

2019-04-15

2019-04-15