728x90

그래프 탐색

- 문제에 대한 상대공간이 있으면, 해는 초기 상태에서 목표상태까지 연산을 반복하여 얻을 수 있음.

 

 

탐색 종류

- 맹목적 탐색 blind search : 목표 노드 위치와 무관한 순서대로 노드 확장. 소모적

- 경험적 탐색 heuristic search : 목표 노드와 관련된 정보나 경험적 정보를 이용한 탐색

  * 경험적 정보 heuristic information : 항상 옳지는 않지만 대부분 잘 맞는 정보

  임의경로 탐색 최적경로 탐색
맹목적 탐색 깊이우선 탐색
너비우선 탐색
균일비용 탐색
경험적 탐색 언덕오르기 탐색
최적우선 탐색
A* 알고리즘

 

깊이 우선 탐색 depth first search; dfs

- 해가 존재할 가능성이 있는한 앞으로 계속 전진하는 탐색

- 더 진행할수 없으면 다른 경로를 선택가능한 노드로 복귀하여 탐색 계속 =>백트래킹

 

 

너비 우선 탐색 breadth-first search, bfs

- 생성 순서에 따라 노드를 확장하는 방법

- 출발 노드에서 목표노드까지 최단길이 보장 -> 경로가 긴경우 탐색 가지가 매우 증가

 

 

균일 비용 탐색 uniform cost search

- 출발 노드서 경로비용이 최소인 노드를 확장시켜나가는 방식

 

 

 

 

경험적 탐색방법 heuristic search method

- 맹목적 탐색 방법의 한계 : 경로 찾는데 너무 많은이 노드 확장

- 경험적 정보로 보다 빠르게 탐색 진행하는 방법

- 바람직한 노드를 선택하기 위해 평가 함수 evaluation function 사용

 

 

언덕 오르기 탐색 hill climbing search

- 목표까지 경로비용 h(n)을 기준으로 노드 선택.

- 실제 h(n)을 구할수 없으니 예측치 hat{h}(n) 이용

   * hat{h}(n) 은 경험적 정보를 이용한 h(n) 예측치

 - 경로 비용이 작은 노드만 선택하여 지역적 최대치에 도달하나 전역적 최대치인지는 보장못함.

 

 

모의 담금질 simulated annealing

- 언덕 오르기 탐색이 지역 최대치에서 멈출수 있는 문제를 개선하기 위한 방법

- 가열하면 원자들이 움직이며 식으면서 더 낮은 에너지를 찾을 가능성이 높아지므로 모의 담금질이라 부름.

 

최적 우선 탐색

- 임의의 노드에 대한 평가함수 사용. 목표 노드까지 비용 예측치.(언덕 오르기 탐색과 동일)

- 언덕 오르기 탐색은 진행 방향의 후계 노드 중에서 가장 적합한 노드 선택

- 최적 우선 탐색은 전체 노드 대상으로 선택

 

 

A* 알고리즘

- 언덕오르기, 모의담금질과는 달리 출발 노드서 도착 노드까지 비용을 평가 함수로 고려

 ->  평가 함수 f(n) = g(n) + h(n)

    * g(n) : 출발노드서 n노드까지 비용

    * h(n) : 노드 n에서 목표노드 n까지 비용

- h(n)은 아직 탐색하지 못했으므로 계산하기 어렵거나 알 수 없음.

     -> 경험적 정보에 의한 예측 평가 함수

        hat{f}(n) = g(n) + hat{h)(n)

        * g(n) : 출발노드서 n노드까지 비용

        * hat{h}(n) : 노드 n에서 목표노드 n까지 비용

- hat{h}(n)이  잘 예측되어야 f(n)에 가까워져 효율적 탐색 수행.

 

300x250

'인공지능' 카테고리의 다른 글

패턴인식이론 - 1. 간단  (0) 2020.11.18
인공지능 - 7. 게임 트리  (0) 2020.11.11
인공지능 - 5. 퍼지이론  (0) 2020.11.11
인공지능 - 4. 논리기반 지식표현  (0) 2020.11.11
인공지능 - 3. 지식  (0) 2020.11.11
728x90

 퍼지 이론의 필요성

- 사람은 모호한 표현과 지식을 사용하나 컴퓨터는 정확한 수를 주어야하는 문제가 있음

- 인간의 모호한 표현을 처리하는 이론을 제공

 

 

 

퍼지 이론

- 1965년 로프티 자데가 소개.

- 모호하게 표현된 자료를 유용한 자료로 만들기 위해 퍼지집합, 퍼지논리, 퍼지수 개념과 계산방법이 개발

   ex. 내일 비가 올 확률은 70% X ,    내일 비가 올 가능성이 크다. O

 

 

퍼지 집합

- 사과 두어개를 사오라고 심부름 시키는 경우.

- "두어개" 2, 3개를 의미하나 2개가 더 강조됨.

- 퍼지 집합 : 원소 포함 여부가 참거짓이 아닌 포함 가능성으로 표현되는 집합

  ex. "두어" = {(2, 1.0), (3, 0.5)}

      "2 or 3" = {(2, 1.0), (3, 0.5)}

 

 

퍼지 집합과 소속 함수

- 퍼지 이론에선 불확실한 상황을 다룰때 숫자보다 자연여 구문 표현을 많이 사용.

 ex. "철수는 젊다"

- 이 예시의 경우 "젊다"라는 구문 표현이 있지만 어느 정도인지 "젊다"를 정의해야함.

- 아래의 곡선은 퍼지 집합의 소속 함수(membership function)으로 각 나이 값이 퍼지 집합에 포함될 가능성을 의미.

 

퍼지 집합의 정의

- 소속함수 mu_A(x) : 원소 x가 집합 A에 소속될 가능성을 나타내는 함수

  -> 원소 x가 집합 A에 포함시 -> mu_A(x) = 1, 포함 안될시 -> mu_A(x) = 0

  => 이경우 고전 집합에서 소속함수 mu_A는 전체 집합 U의 모든 원소를 집합 {0, 1}에 대응, 한정한다.

- 소속 함수의 값이 0, 1사이 임의의 값을 가지는 경우 소속함수 mu_A는 각 원소를 집합 [0, 1]에 대응.

 

- 앞의 "두어개'에 대한 소속함수들은 좌측과 같고, 퍼지집합을 표현하면 우측과 같다.

 

- 고전 집합과 퍼지 집합의 비교

 

퍼지 연산

(생략)

 

 

퍼지 추론 현황

- 산업체 제어 프로세스, 시스템 모델링, 퍼지 지식 기반시스템 개발 등에 활용

1. 퍼지 규칙 조건부와 결론부는 언어적 변수 포함

2. 퍼지 규칙을 이용한 추론 절차는 일반적 규칙과 다름

 

 

언여적 변수를 사용한 퍼지 추론

- 1975년 자데 교수가 도입 -> 상업적 응용에 큰 역활

- 특정 변수를 수치 뿐만이 아니라 언어적 값도 사용가능하게 함.

 ex. "키"는 보통 수치로 값을 사용. 언어적 변수를 사용시 "작다", "크다", "보통"이다. 값도 사용가능

 

탱크 수위 조절 제어 시스템에서의 예시

- "탱크 수위가 높으면 배수 밸브를 연다"라는 지식이 있다.

   퍼지규칙 :  IF 수위가 높으면 THEN 밸브를 연다.

- 3m가 높다고 가정시 다음과 같이 퍼지 집합으로 해석

   HIGH = 0.1/2.0m + 0.1/2.2m + 0.3/2.3m + 0.3/2.4m +

              0.5/2.5m + 0.7/2.6m + 0.7/2.7m + 0.9/2,8m +

              0.9/2.9m + 1.0/3.0m + 1.0/3.1m + ...

 

- 밸브의 개방 정도도 퍼지 집합으로 표현 가능

 1. 대략적 값을 정함

 2. 현장 실무자 작업을 관찰하여 정함.

 3. 시뮬레이션으로 양호한 결과를 내도록 함수값 조정

 

 

 

퍼지 추론

- 퍼지 규칙을 이용한 추론은 근사적이므로 근사 추론 approximate reasoning, 퍼지 추론 fuzzy reasoning이라고 함.

- 아래의 규칙이 존재하는 경우(긍정 논법)

      IF x is A TEHN y is B

ex. 현재 수위가 "조금 높다"로 관측. "조금 높다"에 대한 소속함수가 정의됨. 규칙과 관측 결과가 주어질때, 추론 가능

   규칙 : IF 수위가 높다 THEN 벨브를 연다.

   사실 : 수위가 조금 높다.

   추론 결과 :         벨브를 조금 연다.

* 이진 논리를 사용한다면 규칙 조건(수위 높다)과 사실(조금 높다)가 일치하지 않아 추론 불가

 

 

 

 

수위 조절 벨브 시스템에서 퍼지 추론

- 제시된 규칙과 사실

- 추론 과정이 더있으나 생략

 

 

300x250

'인공지능' 카테고리의 다른 글

인공지능 - 7. 게임 트리  (0) 2020.11.11
인공지능 - 6. 탐색 과정  (0) 2020.11.11
인공지능 - 4. 논리기반 지식표현  (0) 2020.11.11
인공지능 - 3. 지식  (0) 2020.11.11
인공지능 - 1. 개요 ~ 탐색  (0) 2020.10.15
728x90

논리의 의미

- 사고 과정

 

 

논리학의 두종류

- 인식론적 논리학 : 인식의 본질, 과정 연구 -> 철학, 언어, 인지심리학 으로 발전

- 형식논리학 :  삼단논법 기반 사고, 정확한 전제(명제)가 주어질때 정확한 결론을 얻을 수 있음. 

       -> 형식적 연역을 기호로 표현하여 기호논리학으로 발전. 논리 연산자와 부울대수가 만들어짐.

 

 

퍼지 논리의 시작

- 명제논리와 술어논리를 많이 사용. 자연언어를 기호화하여 형식적으로 처리하는 목적임. 표현력에 제한

  -> 논리 연산자가 제한됨. 표현(명제)가 정확여부를 참/거짓 2개의 진리값으로 취급하기 때문.

- T/F 2개의 진리값 이외의 모호함을 취급하는 퍼지논리가 연구됨.

 

 

 

이진 논리

- 기호 논리학에서의 명제 : 한 판단을 포함한 문장/정보

- 기본 명제 : 분해 불가한 최소 단위 명제.  p, q, r(이 기호는 명제 상수, 원소식)

   ex. p = 철수는 한국인이다. , q = 닉은 미국인이다.

- 합성명제 : 기본 명제를 결합한 명제

  ex. a = 철수는 한국인이고, 닉은 미국인이다.

 

 

 

조건 명제

- 기호 논리학에서의 논리 기호 : 3가지 - 선언(또는, v) 연언(그리고, ∧), 부정(아니다, ~)

- 조건명제기호 : 논리 기호 이외의 결합 기호. -> (if then)

- 조건 명제 예시

  p : 비가 온다.

  q : 소풍 취소한다.

  p -> q : 비가 오면 소풍 취소.

 

 

명제 논리식 정의

- 아래는 기본 명제와 논리 기호로 명제 논리 정형식을 만드는 규칙

 1. 기본 명제 p, q, r은 논리식

 2. p가 논리식 일때, ~p도 논리식

 3. p, q가 논리식 일떄 p -> q도 논리식

 4. 1 ~ 3으로 얻는 식만 논리식

 

 

항진식

- 항상 참이 되는 논리식

ex. H = p v ~p

 p = 나는 부자다. ~p = 나는 부자가 아니다.

 -> H = 나는 부자거나 부자가 아니다. 

 => H는 항진식

 

 

연역

- 알고있는 전제로 결론을 구하는 과정

ex. alpha와 alpha -> beta가 성립되면 beta가 성립된다.(긍정논법)

 

 

 

 

 

 

 

 

명제 논리의 과정과 한계

1. 명제 논리는 형식 논리학에 기반

2. 명제 논리는 복잡한 문장, 합성 명제를 기본 명제로 분할

3. 삼단 논법으로 새로운 지식 추론.

- 명제 논리 한계 예시

    p : 소크라테스는 사람

    q : 플라톤은 사람

   -> 명제 p, q만으로 모두 사람이라는 공통점을 찾을수가 없다.

     r : 모든 사람은 죽는다

    -> p, q, r로 소크라테스와 플라톤은 죽는다는 사실 유도 불가

 

 

술어 논리

- 명제를 서술하는 술어와 수식 받는 객체로 구성. 술어(객체) 형태

- 술어 논리 예시

  1. 소크라테스는 사람 -> man(SOCRATES)

  2. 플라톤은 사람 -> man(PLATO)

  3. 모든 사람 죽음 -> ∀x(man(x) -> mortal(x))

 => 이 경우 소크라테스와 플라톤은 사람이므로 죽는다는 사실을 유도할 수 있다.

 

술어 논리 기호

- ∀ 천칭기호 universal quantifier : ∀x시, 모든x에대하여

- ∃ 존재기호 existential quantifier : ∃x시,적어도하나x가존재함

* quantifier 한정자 : 범위를 한정하는 연산자

- 1차 논리 : 한정 기호를 사용하는 술어 논리

 

 

 

 

300x250

'인공지능' 카테고리의 다른 글

인공지능 - 6. 탐색 과정  (0) 2020.11.11
인공지능 - 5. 퍼지이론  (0) 2020.11.11
인공지능 - 3. 지식  (0) 2020.11.11
인공지능 - 1. 개요 ~ 탐색  (0) 2020.10.15
패턴인식 - 9. 선형 판별 분석  (0) 2020.08.06
728x90

데이터, 정보, 지식, 진리의 차이

- 데이터 : 관측 센서로 취득한 값

- 정보 : 잡음과 불필요한 데이터를 제거한 데이터

- 지식 : 정보의 개념, 체계화

- 진리, 정의 : 지식을 보편/이론화 한 결과물

 

지식기반 시스템

- 인공지능 시스템의 문제 풀이 : 지식의 표현/활용이 중요

   <-> 일반 프로그램 : 데이터와 처리 규칙(프로그램)

- 문제 영역 관련 지식(지식 베이스) + 지식 기반 문제 풀이 기능(추론 기관)으로 구성

  

 

지식의 표현

- 문제 해결을 위한 문제 기술

- 컴퓨터에서 실행가능한 형태

 

인공지능 프로그램

- 일반 프로그램과 달리 상황에 대해 어느 지식을 사용할 지 동적으로 제어

 -> 컴퓨터 내부서 지식 저장, 처리 메커니즘이 핵심

- 모든 문제에 통일적으로 표현할 수 있는 방버은 존재 하지 않음. 

 -> 문제의 논리 구조를 분석하여 표현방법을 고려함

 

 

 

지식 사상

- 인공지능 기법으로 문제 해결 -> 많은 지식 + 해를 얻기위해 지식 처리 메커니즘 필요

- 사람이 사용하는 지식을 컴퓨터에서 처리하기 위해 컴퓨터 내부 표현 형태로 사상

- 추론 결과를 역사상하여 결론을 얻을 수 있음.

 => 지식 표현 시스템이 사상과 역사상을 명확히 하느냐에 따라 표현에서 중요한 요소

 

지식 사상의 예시

- 논리를 이용한 사실 표현

 -> 철수는 사람이다. ( 초기사실)

 -> man(철수) (초기 사실 내부 표현)

 -> 모든 사람은 생각한다 (추론 매커니즘)

 -> think(철수)  (추론 사실 내부 표현)

 -> 철수는 생각한다. (추론 사실)

 

 

지식 분류하기

- 문제에 대한 지식 : 문제 관련 사실로 얻는 지식

- 대상 세계에 성립하는 규칙, 법칙 : 지식 베이스의 지식을 맹목적 사용시 탐색 가지가 크게 증가하게됨

   => 효율적 탐색을 위해 성립 규칙과 법칙 이용

 - 메타 지식 : 지식에 관한 지식으로 문제 해결시 지식을 아떻게 활용할 것인가를 말함.

    => 수집 지식으로 추론 방법 제어시 사용

 

 

 

 

지식 표현 조건

- 특정 분야의 복잡한 정보를 구조화 하여 지식으로 나타내기 위해 다음 조건이 요구됨

- 표현 방법의 적합성 : 모든 지식 정확히 표현

- 추론 정합성 : 표현 구조를 처리하여 새 지식을 유도하기에 용이해야함

- 추론 효율성 : 부가 정보를 지식표현 구조에 적절히 포함시킬 능력 필요

- 지식 획득 능력 : 지식을 쉽게 획득할 수 있는 능력 필요. 지식 베이스에 새 지식 삽입, 프로그램이 스스로 지식 취득

 

 

 

 

지식 표현 유형

1. 절차적 지식 procedural knowledge 표현방법

 - LISP(list processing) 같은 프로그램 언어로 명령어 집합 표현

 - 지식 사용 = 프로그램 실행 -> 지식 제어 정보가 지식에 포함 -> 효율적이지 못함

2. 선언적 지식 declarative knowledge 표현방법 

 - 독립적 지식으로 구성, 지식 운용 목적 프로그램으로 추론에 사용

- 지식은 나열, 사용방법은 제공안됨 ->  지식 이용 방법을 가진 프로그램이 필요

 

 

 

논리를 이용한 지식 표현

1. 명제 논리 proportional logic

- 명제를 기호 형태로 표현.

 *명제 proposition : 참, 거짓을 판단할수 있는 문장

- 예시

  이것은 유리이다. = GLASS

  유리라면 잘 잘린다. = GLASS -> FRAGILE

- 논리 연산자

- 긍정 논법 nodus ponens : X, X -> Y 두 명제로 결론 Y라는 명제를 얻는 과정

 

2, 술어 논리 predicate logic

- 명제 논리를 확장. 술어 + 객체 = 한 문장

 ex. 명제 "강아지는 포유류이다."가 있을떼, "강아지(DOG)"이라는 객체가 "포유류(mammal)" 술어 수식받음.

 => mammal(DOG) 과 같이 표현 가능

- 변수와 함수 사용 -> 문장은 참조하는 변수값에 따라 참/거짓이 됨.

- 한정자 quantifier: 변수 범위 지정

=> 술어, 상수, 변수, 한정자, 논리연산자를 문법에 맞게 만든 문장을 정형식 well-formed formulas:wff

 

 

 

논리 표현 지식 이용

- 지식 베이스에서 단위 지식 검색 : 매칭이나 해식 사용

- 함축된 지식의 경우 : 명확하게 기술되지 않은 정리 증명의 경우 탐색 가지가 크게 증가

- 논리 기반 추론은 명확한 추론 규칙 이용 -> 결과는 항상 참, 저장 지식은 독립, 새 사실이 발견시 지식 양은 증가

 

 

 

규칙을 이용한 지식표현(생략)

 

 

시맨틱 넷 기반 지식 표현

1. 시맨틱 넷 semantic net

- 규칙 기반 지식 표현법의 문제점 : 융통성 적고, 구조화 되지 않음 -> 모형화나 특정지식 표현 힘듬

- 시맨틱 넷 : 지식 사이 관계(순서) 표현. 네트워크 기반 지식 표현 법, 노드 집합과 노드를 연결하는 아크 집합으로 구성

- 노드 : 객체 , 개념, 사건

- 아크 : 노드 사이 관계 (isa - is a, ako - a kind of, has-part 등)

 * isa는 하나의 인스턴스, ako는 어느 부류의 한 종류, has-part 객체의 구성 일부

2. 속성 상속 property inheritance

- 위 예시에서 "꼬리"는 "개" 객체의 속성인데 하위인 "복슬이"가 받음

- 속성 상속 : 상위 노드의 속성을 하위 노드가 따르는 것

 

3. 중앙 집중 지식 장점

- 지식 구성이 쉬움

- 표현 지식이 잘못된경우 쉽게 수정

- 시간 흐름에 따라 최신 지식 유지 쉬움

- 지식 분배가 자동적으로 수행

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

전문가 시스템 시작

- 1960년대 인공지능 학자들이 일반 문제 해결을 위한 일반 문제 풀이기 GPS general problem solver를 만들고자 함.

  -> 인간 사고 과정을 시뮬레이션하려 하였으나 일반 해를 구하기가 어려웟음.

- 특정 분야 문제를 해결할수 있는 구체적인 프로그램 만드는 방법 연구

- 1970년대 : 문제 정형화 표현 기술, 기억 용량 사용시간을 줄이며 문제 해결하는 탐색 방법 연구

 -> 문제 정형화, 추론과정 보다 응용 분야의 지식 표형 방법이 중요함을 찾음.

- 전문가 시스템 expert system : 전문가의 지식, 전략을 시뮬레이션하여 의사결정 지원하는 시스템

- 지식 공학 : 전문가 시스템을 만드는 분야

- 지식 공학자 : 전문가 시스템을 만드는 사람. 해당 분야의 전문가로 지식, 문제 해결전략을 체계적 표현함.

 

 

자료처리 프로그램과 전문가시스템 차이

자료처리 프로그램 전문가 시스템
자료 표현과 이용
알고르짐
반복 처리
다량 자료를 효율적 처리
지식 표현, 이용
경험적 지식
추론적 지식
다량의 지식 베이스를 효율적 처리

 

전문가 시스템 기능

- 해석 : 입력 자료로 상황 추론

- 예측 : 상황으로 발생 가능 결과 예측

- 진단 : 관측 자료로 이상상태진단

- 설계 : 제약조건내 가능한 설계 구상

- 그외 계획, 모니터링, 디버깅, 교육, 제어 등

 

 

전문가 시스템 구성

- 지식 베이스와 추론기관 그리고 사용자 인터페이스로 구성

- 지식 베이스 : 문제 영역 관련 지식

- 추론 기관 : 문제 해결 목적 지식, 프로그램 제어 + 규칙 해석기(새로운 지식 추론을 위해 규칙 적용 결정) + 스케줄러

 

 

전문가 시스템 개발

1. 문제 정의 : 개발 목적, 문제 특성.

  ex. 문제 유형/범위, 참여 인력, 전문가, 소요 시간, 컴퓨터 성능

2. 개념 설정 : 기본 개념 정의, 해법

  ex. 세부작업, 전략, 제약조건

3. 정형화 : 지식 수집 및 지식 표현

  ex. 지식 표현 방법 설정, 적합한 개발도구 사용

4. 구현 : 프로그래밍

  ex. 자료구조, 추론과정, 프로그램 제어, 하부 시스템 통합 고려

5. 검증 ; 요구사항 만족 여부 검증

  ex. 개발자에게 개선방향 제시 필요

 

지식 공학자의 역활

 

300x250

'인공지능' 카테고리의 다른 글

인공지능 - 5. 퍼지이론  (0) 2020.11.11
인공지능 - 4. 논리기반 지식표현  (0) 2020.11.11
인공지능 - 1. 개요 ~ 탐색  (0) 2020.10.15
패턴인식 - 9. 선형 판별 분석  (0) 2020.08.06
패턴인식 - 8. 주성분분석  (0) 2020.08.05
728x90

300x250
728x90

선형 판별 분석 LDA

- 선형 반별 분석 Linear Discriminant Analysis LDA는 주성분 분석 Principal Component Analysis같은 차원 축소법

- 클래스간 분산을 최대화 하고, 클래스내 분산을 최소화 하는 방법

 

 

 

LDA 수행 결과

- 클래스 분할을  최대화하는 주축으로 사상하여, 선형 부공간으로 차원 축소

- 아래의 경우 2차원 샘플 데이터에 LDA를 수행한 결과

 => 좌측의 1차원 부공간은 최악의 선형 부공간

 => 우측의 1차원 부공간은 최적의 선형 부공간으로 모든 2차원 샘플데이터가 분류하기 적합하게 분포됨.

 

https://funnypr.tistory.com/entry/Linear-Discriminant-AnalysisLDA

 

 

 

 

LDA와 PCA의 차이

- 아래의 그림은 PCA와 LDA의 차이를 보여줌

 => PCA는 분산을 최대화하는 주축을 찾음. -> 데이터의 표현을 남기도록 축소

 => LDA는 데이터 분할에 적합하도록 최대화하는 주축을 찾음. -> 데이터 최적 분류로 축소

https://rpubs.com/markloessi/505575

 

 

 

LDA의 의미

1. 클래스 omega_1에 속하는 N_1개의 샘플과 클래스 omega_2에 속하는 N_2개의 샘플 데이터들

 d차원 표본들의 집합 x = {x1, ..., x_n}이 있을때, 1차원 직선상의 사영을 다음의 선형 변환 식으로 표현

2. omega_1과 omega_2에 속하는 샘플들. 클래스 내부의 샘플들은 분산을 줄이고, 클래스 간의 분산을 키우도록 수행

=> 주성분 분석 PCA가 데이터를 잘 표현하는 D차원에서 A차원으로 변환했다면

=> LDA는 클래스간 분산이 최대화 되도록 D차원에서 1차원으로 변환.

 

 

300x250

'인공지능' 카테고리의 다른 글

인공지능 - 3. 지식  (0) 2020.11.11
인공지능 - 1. 개요 ~ 탐색  (0) 2020.10.15
패턴인식 - 8. 주성분분석  (0) 2020.08.05
패턴인식 - 7. 비모수 밀도 추정  (0) 2020.08.04
패턴인식 - 6. 가우시안 혼합 모델  (0) 2020.08.04
728x90

1. 차원이 너무 클때의 문제와 개선법

차원을 줄여야 하는 이유

- 패턴 인식에서 다차원의 특징 벡터를 사용하는데 어떤 벡터를 사용할까?

- 어떤 벡터를 사용할지와 특징 개수에 따라서 패턴 인식기의 성능이 크게 좌우됨.

 

차원의 저주 curse of dimensionality : 차원이 큰 경우의 문제점

- 잡음들도 포함되어 분류에 에러가 심해짐

- 패턴 분류기의 학습과 분류 속도가 느려짐

- 모델링해야할 집합이 너무 큼

 

주성분분석 principal component analysis

- 고차원 특징 벡터를 중요한 특징들을 추출하여 저차원의 특징벡터로 만드는 방법

 

주성분 분석의 사용 예시

- 데이터 시각화 : 고차원 데이터를 시각화 하기 위해서 2차원이나 3차원으로 축소함

- 특징 추출 : 고차원 데이터 집합에 강건한 분류기를 만들려하나 샘플이 부족

               -> PCA로 차원 축소하여 설계시 적은 샘플로 좋은 성능 보임

 

 

 

 

 

 

 

 

2. 고유 벡터와 고유치

고유벡터와 고유치 개요

- 행렬 A가 주어질때 다음의 정의를 만족하는 값 lamdba를 고유치 eigen value 와 벡터 v를 고유 벡터 eigen vector

고유벡터의 의미

- 행렬 곱셈의 특별한 경우

- 다음의 예시를 보자

- 위의 곱은 원래 백터의 스칼라 곱으로 결과가 안나오지만, 아래의 곱샘 결과는 원래의 벡터에 스칼라 곱이 나옴

- 이유 

     1. 벡터 (3; 2)는 2차원 점으로 원점 (0,0)에서 (3, 2)를 가리킴.

     2. 좌측의 정방 행렬은 벡터의 왼쪽에서 곱하여 벡터를 다른 위치로 만든는 변환 행렬

     3. 정방 행렬이 벡터를 직선 y = x에 대칭하게 만드는 행렬의 경우, 벡터는 변환 행렬을 곱해도 자기자신이 됨

     4. 이 때 벡터 (3; 2)는 변환 행렬의 고유 벡터

- 특징

     1.고유 벡터는 정방 행렬에서만 존재하나 모든 정방 행렬은 고유 벡터를 갖고 있지 않음.

     2. 정방 행렬이 n x n 인 경우 고유 벡터는 n 개

     3. 고유 벡터는 곱하기 전에 스케일링을 해도 여전히 동일한 스칼라 곱의 결과가 나옴

        => 스칼라 값은 고유벡터의 길이를 늘리거나 줄이기 밖에 못함

     4. 고유벡터들은 서로 직교 orthogonal함

        => 셈플 데이터들을 x-y축이 아닌 직교 고유 벡터를 기저로하여 표현 가능

 

 

고유 값의 의미

- 이미 고유 벡터에서 설명.

- 고유 벡터의 스칼라 곱이 고유값 -> 위 예시에서 4가 고유벡터의 고유치

 

 

* 고유값과 고유벡터가 중요한 이유 !!!!

-> 특이값 분해 SVD, 선형 연립방정식의 해, 주성분 분석 PCA 등 많이 사용됨

 

 

 

 

 

 

 

3. 주성분 분석법

다변량 분석 multivariate analysis

- 각 차원간에 상관 관계를 가지는 변수 데이터들을 다루게 됨.

 

주성분 분석 PCA Principal Component Analysis

- 다차원 특징 벡터로 이루어진 데이터의 정보들은 유지시키면서 낮은 차원으로 축소시키는 다변량 처리 방법 중 하나

 

주성분 분석에서의 차원

- 특징 데이터는 특징 벡터의 차원수 만큼의 축을 기준으로 표현

 => ex. 2차원 특징 데이터는 2개의 기준 축으로 표현

- 차원 축소 -> 기준 축을 줄여나간다 

 => 10차원 데이터를 4차원으로 줄인다 -> 10개의 기준축을 4개로 축소함

 

주성분 분석의 과정

1. 다변량 데이터의 주성분인 주축을 통계적 방법으로 구함

2. 주축 principal axis 방향으로 특징 벡터 x를 사영 projection하여 차원 축소.

=> 상관 관계있는 변수들을 상관 없는 변수들의 집합으로 기준축 중심으로 변환하는 것

=> Karthunen-Loeve 변환 KL 변환이라고도 부름

 

차원 수를 축소하는 이유

- 차원의 저주 문제를 개선하기 위해 줄이며, PCA로 낮은 차원에서 최적의 특징 벡터를 효과적으로 다룰 수 있음

 

주성분 분석의 주축에 따른 변화

- 주축을 어떻게 설정하느냐에 따라서 변량의 분산이 달라짐

 => 가장 유용한 성분은 가장 큰 분산값을 가질떄의 성분들

 

 

 

 

 

 

 

4. 고유치, 고유벡터 실습

4.1 균일 분포 샘플 띄우기

 균일 분포로 차원이 2인 벡터 1000개 생성 후 플로팅

clc;
clear all;


R1 = rand(1000, 2);
figure;
plot(R1(:,1), R1(:,2), "r*");

grid
axis("square");
title("uniform distributed random vectors");
xlabel('x');
ylabel("y");

 

4.2 원점 조정

- 샘플 데이터의 중심이 0이 되도록 수정

clc;
clear all;


R1 = rand(1000, 2);


R1_mean = [mean(R1(:,1)), mean(R1(:,2))];
Rctr = [R1(:, 1) - R1_mean(:, 1) , R1(:,2) - R1_mean(:,2)];
figure;
plot(Rctr(:,1), Rctr(:,2), "r*");


grid
axis("square");
title("uniform distributed random vectors의 원점을 0으로");
xlabel('x');
ylabel("y");

 

4.3 샘플 데이터를 원으로 만들기

- 반경 0.5 넘어가는 샘플들은 제거

clc;
clear all;


R1 = rand(1000, 2);


R1_mean = [mean(R1(:,1)), mean(R1(:,2))];
Rctr = [R1(:, 1) - R1_mean(:, 1) , R1(:,2) - R1_mean(:,2)];

for i = 1:1000
    
    if ((sqrt(Rctr(i, 1)^2 + Rctr(i, 2)^2)) > 0.5)
        for j = 1 : 2
            Rcirc(i, j ) =0;
        end
    else
        for j = 1 : 2
            Rcirc(i, j) = Rctr(i, j);
        end
    end
end

plot(Rcirc(:,1), Rcirc(:,2), "r*");

grid
axis("square");
title("uniform distributed random vectors의 원점을 0으로");
xlabel('x');
ylabel("y");

 

 

 

4.4 공분산 행렬과 고유벡터, 고유치 구하기

- 방금 구한 원의 데이터들로 공분산 행렬 계산

clc;
clear all;


R1 = rand(1000, 2);


R1_mean = [mean(R1(:,1)), mean(R1(:,2))];
Rctr = [R1(:, 1) - R1_mean(:, 1) , R1(:,2) - R1_mean(:,2)];

for i = 1:1000
    
    if ((sqrt(Rctr(i, 1)^2 + Rctr(i, 2)^2)) > 0.5)
        for j = 1 : 2
            Rcirc(i, j ) =0;
        end
    else
        for j = 1 : 2
            Rcirc(i, j) = Rctr(i, j);
        end
    end
end



N = 1000
a = 0;
for i = 1 : N
    a = a + Rcirc(i, 1)^2;
end
a = a /N;

b = 0;
for i = 1 : N
    b = b + Rcirc(i, 1) * Rcirc(i, 2);
end
b = b /N;

c = 0;
for i = 1 : N
    c = c + Rcirc(i, 2)^2;
end

c = c / N;
C = [a b;b c]

[EigenVector, EigenValue] = eig(C)

 

 

 

5. 주성분 분석실습

- 방금 구한 2차원 데이터를 1차원으로 축소시키자

5.1 데이터 준비하기

 균일 분포로 차원이 2인 벡터 1000개 생성

- 방금 구한 2차원 데이터를 1차원으로 축소시키자

clear all;
close all;
clc;

% 정규 분포를 따르는 2차원 데이터 생성
x(1, :) = randn(1, 100);
x(2, :) = randn(1, 100) *3;

% 타원 모양 분포를 약간 회전시키자
% 카티지안 좌표계를 극좌표계로 변환후 pi/3회전 후 다시 카티지안으로변환
[p(1, :), p(2,:) ] = cart2pol(x(1, :), x(2, :));
p(1, :) = p(1, :) - pi/3;
[x(1, :), x(2,:)] = pol2cart(p(1,:), p(2,:));

% 데이터 플로팅
scatter(x(1,:), x(2,:));
axis equal;

 

5.2 주성분 찾기

- pacov : 공분산 행렬로 주성분을 바로 구하여 고유값 크기순으로 정렬해주는 함수

 * 주성분 : 고유 벡터를 기저로하고, 고유치만큼 길이를 갖는 데이터를 가장 잘나타내는 축?

=> 붉은 선이 제1 주성분으로 최대 변동 축

=> 녹색 선이 제 2 주성분 , 제1주성분과 수직

clear all;
close all;
clc;

% 정규 분포를 따르는 2차원 데이터 생성
x(1, :) = randn(1, 100);
x(2, :) = randn(1, 100) *3;

% 타원 모양 분포를 약간 회전시키자
% 카티지안 좌표계를 극좌표계로 변환후 pi/3회전 후 다시 카티지안으로변환
[p(1, :), p(2,:) ] = cart2pol(x(1, :), x(2, :));
p(1, :) = p(1, :) - pi/3;
[x(1, :), x(2,:)] = pol2cart(p(1,:), p(2,:));


% 데이터 플로팅
scatter(x(1,:), x(2,:));
axis equal;

% 주성분 PC 찾기
[pc, latent, explained] = pcacov(cov(x'));

% 데이터 상에 주성분 그림
hold on;
plot([-4 4] * pc(1,1), [-4 4] *pc(2, 1), 'r-');
plot([-2 2] * pc(1,2), [-2 2] *pc(2, 2), 'g-');

 

 

5.3 데이터들이 주성분을 주축으로 하도록 회전

-원 데이터 집합과 주성분을 곱하면 데이터들이 주성분이 주축이 되도록 회전됨

clear all;
close all;
clc;

% 정규 분포를 따르는 2차원 데이터 생성
x(1, :) = randn(1, 100);
x(2, :) = randn(1, 100) *3;

% 타원 모양 분포를 약간 회전시키자
% 카티지안 좌표계를 극좌표계로 변환후 pi/3회전 후 다시 카티지안으로변환
[p(1, :), p(2,:) ] = cart2pol(x(1, :), x(2, :));
p(1, :) = p(1, :) - pi/3;
[x(1, :), x(2,:)] = pol2cart(p(1,:), p(2,:));


% 주성분 PC 찾기
[pc, latent, explained] = pcacov(cov(x'));

% 주성분을 축으로 데이터를 회전
y = (x' * pc)';

% 데이터 플로팅
figure;
scatter(y(1, :), y(2, :));
axis equal;

 

 

 

 

5.4 축 상으로 주성분이 놓여졌는지 확인하기

clear all;
close all;
clc;

% 정규 분포를 따르는 2차원 데이터 생성
x(1, :) = randn(1, 100);
x(2, :) = randn(1, 100) *3;

% 타원 모양 분포를 약간 회전시키자
% 카티지안 좌표계를 극좌표계로 변환후 pi/3회전 후 다시 카티지안으로변환
[p(1, :), p(2,:) ] = cart2pol(x(1, :), x(2, :));
p(1, :) = p(1, :) - pi/3;
[x(1, :), x(2,:)] = pol2cart(p(1,:), p(2,:));


% 주성분 PC 찾기
[pc, latent, explained] = pcacov(cov(x'));

% 주성분을 축으로 데이터를 회전
y = (x' * pc)';

% 데이터 플로팅
figure;
scatter(y(1, :), y(2, :));
axis equal;

% 주성분 PC 찾기
[pc2, latent, explained] = pcacov(cov(y'));
% 데이터 상에 주성분 그림
hold on;
plot([-4 4] * pc2(1,1), [-4 4]*pc2(2,1), 'r-');
plot([-2 2]* pc2(1, 2), [-2 2] *pc(2, 2), 'g-');

 

 

5.5 주성분 분석

-원 데이터와 주성분을 내적하면 데이터들이 주성분 축으로 사상되어 1차원 데이터로 축소됨

clear all;
close all;
clc;

% 정규 분포를 따르는 2차원 데이터 생성
x(1, :) = randn(1, 100);
x(2, :) = randn(1, 100) *3;

% 타원 모양 분포를 약간 회전시키자
% 카티지안 좌표계를 극좌표계로 변환후 pi/3회전 후 다시 카티지안으로변환
[p(1, :), p(2,:) ] = cart2pol(x(1, :), x(2, :));
p(1, :) = p(1, :) - pi/3;
[x(1, :), x(2,:)] = pol2cart(p(1,:), p(2,:));


% 주성분 PC 찾기
[pc, latent, explained] = pcacov(cov(x'));

% 주성분을 축으로 데이터를 회전
y = (x' * pc)';

% 1차원으로 축소하기 위해 두번째 성분을 0으로 설정.
y(2,:)=0;

%원 데이터 역변환
x = (y' * inv(pc)');

% 데이터 플로팅
figure;
scatter(y(1, :), y(2, :));
axis equal;

300x250
728x90

1. 비모수적 밀도 추정 예시

모수적 밀도 추정

- 그동안 모수적인 방법으로 샘플데이터가 가우시안 분포를 따른다고 가정 

  -> 확률 밀도함수 모델링 -> 로그 우도 최대화하는 파라미터 찾음

 * 대부분의 데이터 분포는 유니모달이 아니라 멀티 모달

- 멀티 모달을 다루는 GMM을 살펴봄. 

 => 모수적인 밀도 추정 방법은 어느 확률 밀도 함수를 가정하고 샘플 데이터로부터 적절한 파라미터를 추정하는 방법

- 아래의 그림은 샘플 데이터들이 주어질때 이를 가장 잘 나타내는 확률 밀도 함수 추정 예시들을 보여줌

https://en.wikipedia.org/wiki/Density_estimation

 

비모수적 밀도 추정

- 파라미터 추정없이 표본 데이터로부터 밀도 함수를 추정하는 방법.

- 종류 : 히스토그램을 만드는 방법, 커널 밀도 추정 등

 

 

 

 

2. 히스토그램 방법

히스토그램을 이용한 밀도 표현

- 히스토그램을 이용하면 데이터 밀도를 간단하게 표현 가능

- 데이터를 연속된 간격으로 나누고 각 관측 되는 표본 빈도를 카운트 -> 막대 높이로 밀도 표현

- 히스토그램의 확률 함수 

- 아래의 그림은 샘플 데이터가 주어질때 히스토그램으로 밀도를 추정한 예시

http://doingdatascience.com/?tag=kernel

 

 

 

 

3. 커널 밀도 추정

미지의 확률밀도도 함수 추정

- 특징 벡터 x가 표본 공간 영역 R에 존재할때 P(x)를 정의

 -> 특징 벡터 x가 p(x)로부터 발생을 가정 => 표본 공간 R에 속할 확률 P(x)는 아래의 적분으로 정의

- N개의 벡터 집합이 p(x)로 생성된 경우, N개중 k개가 R영역에 속할 확률 P(k)는 (이항분포로)다음과 같이 정의

- 이항 pmf의 성질로 평균과 분산은 다음과 같이 구할수 있음.

- 여기서 n이 무한대일때 P(x)는 다음과 같이 추정됨

 

 

 

 

 

 

300x250
728x90

1.가우시안 혼합모델

가우시안 혼합모델의 필요성

- 확뮬 밀도 함수를 추정하기 위해서, 샘플 데이터들이 특정한 분포(대표적으로 가우시안)을 따른다고 가정

 => 우도를 최대화하는 최우 추정법 MLE Maximization Likelihood Estimation 사용

- but. 특정한 분포를 모르는 경우 비모수적 방법인 파젠창이 있음.

 

 

가우시안 혼합 모델 Gaussian Mixture Model

- 표본 데이터 집합의 분포를 하나의 확률 밀도 함수가 아닌 여러개의 가우시안 확률 밀도함수로 데이터 분포 모델링

  => 가우시안 혼합 모델은 준 모수적 방법 semi-parametric

  => 개별 밀도 함수를 전체 확률 밀도 함수 성분 커널로 간주

- 아래의 그림은 2차원 샘플 데이터에 대한 GMM 데모델링

 * 가우시안 분포가 아니라 다른 분포도 상관없음

https://gfycat.com/ko/smugchiefhummingbird

 

 

 

 

 

 

 

 

 

 

2.가우시안 혼합모델 표현과 장점

가우시안 혼합 모델의 모델링

- 전체 확률밀도 함수는 M개의 가우시안 확률 밀도 함수의 선형 결합.

 => oemga_i번째 theta_i 파라미터를 가진 확률 밀도 함수들의 가중치를 반영한 합이 가우시안 혼합 모델

 

혼합 가중치 성분

- P(omega_i)는 혼합 가중치 성분으로 M까지 다합하면 1이됨

 

파라미터 집합의 형태

- i번째 파라미터 집합 theta_i는 다음과 같이 구성됨

- 여기서 가우시안 모델의 공분산 형태는 완전, 대각, 원형이 될수 있음.

- 혼합 성분 개수는 데이터 집합 크기에 따라 조절 가능

 

 

가우시안 혼합 모델의 장점

- 혼합 성분 개수와 파라미터 값들이 적절히 제공하면 모든 분포에대해 완벽히 모델링 가능

- 비대칭성과 다중 봉우리?(멀티모달) 특성을 가짐

 => 단일 가우시안 확률밀도함수보다 강인한 밀도 추정 가능

 

 

 

 

 

3. EM을 이용하여 GMM 모델링

GMM의 목표

- 샘플 데이터 집합 x가 주어질때 로그 우도를 최대화 하는 혼합 가우시안들의 파라미터를 추정

- K-means와 마찬가지로 EM 알고리즘으로 최적 모델 추정

 

 

GMM 관련 정의

- 샘플 데이터 집합이 x라면, 학습할 데이터 셋을 아래와 같이 x_n으로 정의

- M개의 가우시안 모델들 중 j번째 모델의 파라미터를 다음과 같이 정의

- j번쨰 개별 가우시안 확률 밀도 함수를 아래와 같이 정리

 

 

- 전체 확률 밀도 함수를 M개의 개별 확률 밀도 함수들의 선형 결합으로 정리면 

* 수식 정리하려고하는데 너무 길어진다.

GMM의 특징과 확률 밀도 함수를 추정하는 과정은 대강 이해했으니 넘어가자.

 

 

GMM 정리

- 개별 가우시안 모델들을 혼합하여 다양한 샘플데이터에도 강인하게 만든 모델

 * 여기서 분포는 가우시안 확률 분포에 한정하지 않음

- 전체 확률 분포는 M 개의 개별 확률 분포들와 가중치들의 곱 합과 같음.

- GMM의 파라미터 집합은 M개의 원소의 평균, 분산, 가중치들로 이루어짐.

- EM 알고리즘을 통해 로그 우도가 최대가 되는 지점을 찾아 해당 파라미터 hat{theta}가 최적의 가우시안 혼합 모델의파라미터 집합 

 

 

 

 

 

 

 

 

 

300x250
728x90

1. 데이터 마이닝 개요

데이터 마이닝

- 데이터로부터 의미있는 정보를 추출하는 학문

- ex. 벡터 양자화, 클러스터링

 

 

 

 

패턴인식 시스템의 학습 과정

- 지도 학습 supervised learning이나 비지도학습 unsupervised learning으로 수행함.

- 지도 학습 : 특징벡터 x와 클래스 omega가 같이 주어진 상황에서의 학습

- 비지도학습 : 특징 벡터 x = {x1, ..., xn}만으로 이루어진 데이터로 수행한 학습

- 클러스터링 : 정답(클래스)가 정해지지 않은 데이터들을 적절하게 분류하여 모아주는 방법

 

 

 

비지도 학습의 장점

- 표본이 너무 많아서 라벨링 하기 힘든 경우

- 특징 벡터에 클래스 라벨이 주어지지 않았을 때

- 표본들이 작은 프로토타입 원형들로 분류될수 잇을때

 

 

 

 

 

 

 

 

2. 비지도 학습에 관하여

비지도 학습의 방법들

- 모수적 혼합 모델 구축하는 방법과 비모수적 방법 2가지가 존재

 

 

모수적 혼합 모델 구축을 통한 비지도 학습

- 여러개의 확률 밀도 함수로 주어진 클래스 데이터를 모델링

- 아래의 식과 같이 수학적 모델링 수행하며 혼합 모델이라 부름

 

비모수적 방법

- 데이터가 어느 확률 밀도 함수를 따른다는 가정 없이, 즉 파라미터 없이 정해진 클래스 수 만큼 데이터를 나누는 과정

- 대표적으로 k-means 클러스터링 알고리즘이 존재 => 최적화 기법으로 EM 알고리즘 사용.

 

 

 

 

 

 

 

 

 

 

3. 벡터 양자화

벡터 양자화 vector quantization와 클러스터링 clustering의 의미

- 벡터 양자화 = 클러스터링. 둘이 동일한 뜻

- 벡터 양자화 : 특징벡터 집합 x = [x1, ..., xn]를 K개의 특징 백터 집합 y = [y1, ... yk]로 사상

   => 사상 함수 y_i = c(x_i)가 정의됨.   

       * c( )는 양자화 연산자

      * y_i는 코드 벡터, 코드 워드, 클러스터라 부름

      * y는 코드 워드(클러스터)들의 모임인 코드북이라 함.

 - 클러스터의 갯수 : 코드북의 크기

     => n개의 특징 벡터 데이터들을 K개의 클러스터로 분류하는것이 벡터 양자화(클러스터링)

- 클러스터 중심점 센트로이드 centroid : 특정 클러스터에 소속한 특징 벡터들의 중심점

- 코드 북의 크기 K는 미리 정해져 있어야함

- 아래으 그림은 kmeans 클러스터링 예시

https://dashee87.github.io/data%20science/general/Clustering-with-Scikit-with-GIFs/

 

 

 

 

 

 

 

 

4. 최적화의 필요성

양자화 오차의 발생

- 특징 벡터 집합 x를 새 클러스터 집합 y로 양자화 하는 중 오차 발생

- 벡터 양자화는 특징벡터들 간의 거리 척도가 많이 사용됨. 특징 공간에 맞는 척도 사용 필요

  => 대표적으로 유클리디안 거리가 가장 많의 사용

- x, y 사이의 유클리디안 거리를 다음과 같이 정의

최적화 방향

- 특징 벡터 하나 xn와 중심점 centroid c(x) 사이의 거리가 최소가 되도록 최적화 수행 필요

- 중심점의 좌표는 해당 클러스터에 속하는 모든 특징 벡터들의 평균

평균 왜곡 mean distortion

- 유클리디안 거리로 구한 오차들의 총합 . 평균 왜곡은 아래와 같다.

코드 벡터 집합 구하기의 문제

- 평균 왜곡을 최소화 하는 코드 벡터 집합 y를 어떻게 구할것인지 최적화 과정을 사용 필요

 

벡터 양자화의 문제와 제안된 알고리즘

  1. 코드북 설계 : 주어진 데이터 집합에 최적의 코드북 찾기        => Kmeans 알고리즘            

  2. 양자화 : 주어진 데이터에 가장 가까운 코드벡터 찾아야함      => 비균일 이진 분할

  3. 코드 워드 거리 : 주어진 벡터에 가장 가까운 워드 찾기          => kmenas 알고리즘에 따르는 이진분할 알고리즘

 

 

 

 

 

 

 

 

 

 

5. k-means, EM 알고리즘

EM 알고리즘 Expectation Maximization

- 숨겨진 정보를 가진 문제로부터 최적해를 찾는 유용한 알고리즘

  => 최적의 코드 벡터들 centroids가 클러스터들의 중심이 될 것

- 숨겨진 정보를 추정 expectation하고, maximization을 반복하여 최적해를 찾아내가는 과정

 => 대표적인 EM 최적화 알고리즘이 K-menas

 

 

 

EM 알고리즘과 K-means 알고리즘의 차이

- EM 알고리즘 : 초기값 선택이 지역적 최적해를 찾는데 가장 중요한 요소

- K-means : 아무 초기값에서 E-M 과정을 수렴할떄까지 반복

  => 임의의 중심점들에 속하는 클러스터들을 선정(E) -> 크러스터들로부터 중심점 결정(M) 반복

 

 

 

K-menas 알고리즘

1. 데이터 집합 x = [x1, ... , xn]이 주어지고, k개의 초기 중심 집합(코드 벡터 집합) y = [y1, ..., yk] 생성

2. Expectation : y_i에 가까운 클러스터들을 선정 => x의 모든 원소들은 y의 원소중 하나에 속하게 됨.

3. Maximization : 새로운 중심점 갱신

4. 총 평균 왜곡 계산

 

5. 총 평균 왜곡이 지정안 오차나 반복횟수가 될때 까지 2 ~ 4 반복

300x250

+ Recent posts