학교 과제로 비지도학습에 대하여 조금 알아보았습니다.

 

기계 학습

 

(1) 새로운 정보를 학습하고, 습득한 정보를 효율적으로 사용할 수 있는 능력과 결부시키는 지식 습득.

(2) 작업을 반복적으로 수행함으로써 결과를 얻어내는 기술의 개선 과정

(3) 학습 방식에 따라 지도 학습, 준지도 학습, 비지도 학습, 강화 학습으로 분류

 

 

 

비지도 학습 = 기계 학습 중 하나

 

비지도 학습의 종류

1)K means 알고리즘

-군집 알고리즘

-클러스터 내부에 속한 데이터들이 서로 '가깝다'라고 정의, '가장 가까운' 내부 거리를 가지는 클러스터를 고르는 알고리즘

(출처:http://jinquixote.tistory.com/124)

 

2)Kernel Density estimation 알고리즘\

-non-parametric 방법 중 하나(*non-parametric : 사전 정보나 지식 없이 순수하게 관측된 데이터만으로 확률밀도함수를 측정) 

-커널 함수란 것을 이용한 방법

(출처:http://darkpgmr.tistory.com/147)

 

3)Expectation maximization 알고리즘

-관측되지 않는 잠재변수에 의존하는 확률 모델에서 최대가능도(maximum likelihood)나 최대사후확률(maximum a posteriori, 약자 MAP)을 갖는 매개변수를 찾는 반복적인 알고리즘

(출처: https://goo.gl/7Q1sk5)

 

 

4)DBSCAN 알고리즘

-Density model들중 하나

-K-means와 유사. 하지만 군집이 아닌 데이터들의 밀도를 이용한다.

 

 

(출처:http://gentlej90.tistory.com/29)

 

 

 ◆파이썬을 활용한 K-means

 

파이썬 3.x 버전입니다.

 

K-means 3.x.zip

 

 

 

 

 

 

 

'Programming > Python' 카테고리의 다른 글

비지도학습이란?  (2) 2017.10.28
파이썬 처음 시작  (2) 2017.08.31
파이썬 설치하기  (0) 2017.08.29
  1. 2017.10.29 09:33

    비밀댓글입니다

  2. 2017.10.30 10:36

    비밀댓글입니다

그리디 알고리즘 : 최적화 문제(가능한 해들 중 가장 좋은 해를 고르는)를 해결하는 알고리즘

 

◆그리디 알고리즘의 특징

 

1)데이터 간의 관계를 고려하지 않고 부분적인 최적해를 찾고, 이들을 모아서 문제의 최적해를 얻는다.

 

2)일단 한번 선택하면 그 데이터를 버리고 다른 것을 취하지 않는다.

 

 

 

◆그리디 알고리즘으로 해결 가능한 대표적인 문제들

 

1)동전 거스름돈

:거스름돈을 받을 때 가장 적은 수의 동전으로 주는 문제

 

#유사코드

 

 

#파이썬 소스

 

 

 

2)최소 신장 트리

:주어진 가중치 그래프에서 사이클이 없이 모든 점들을 연결시킨 트리들 중 선분들의 가중치 합이 최소인 트리

 

최소 신장 트리를 찾는 대표적인 그리디 알고리즘으로는 크러스컬프림 알고리즘이 있음.

 

#크루스컬 유사코드

 

 

#프림 유사코드

 

 

#파이썬 소스

 

*크러스컬과 프림 둘 다 제 파이썬 숙련도로는 무리인 것 같습니다 지송합니다 ㅠㅠ

3)선택 문제 알고리즘

 

k번째 작은 수를 찾는 문제로서, 입력에서 퀵 정렬에서와 같이 피봇을 선택하여 피봇보다 작은 부분과 큰 부분으로 분할한 후에 k 번째 작은 수가 들어있는 부분을 재귀적으로 탐색한다. 평균 경우 시간복잡도는 O(n)이다.

 


#유사코드

 

 

#파이썬 소스

 

*퀵 정렬 참고해서 작성해주시기 바랍니다!!

주의 : 피봇을 왼쪽으로 옮겼다가 중앙으로 옮길 때 (1~p)인덱스를 하나씩 앞으로 땡겨주고 p자리에 피봇을 넣어줘야 합니다

 

 

 

4)최근접 점의 쌍 문제

 

n개의 점들을 1/2로 분할하여 각각의 부분 문제에서 최근접 점의 쌍을 찾고, 2개의 부분해 중에서 짧은 거리를 가진 점의 쌍을 일단 찾는다. 그리고 2개의 부분해를 취합할 때, 반드시 중간 영역 안에 있는 점들 중에 최근접 점의 쌍이 있는지도 확인해보아야 한다. 시간복잡도는 O(nlogn)이다.

 

 

#유사코드

 

 

#파이썬 소스

 

이건 파이썬 2차원 배열 좀더 배우고 올리겠습니다 스미마셍...

 

알고리즘 = 문제를 해결하는 단계적 절차 또는 방법


◆알고리즘의 특성


-정확성 : 알고리즘은 주어진 입력에 대해 올바른 해를 주어야 한다.

-수행성 : 알고리즘의 각 단계는 컴퓨터에서 수행이 가능하여야 한다.

-유한성 : 알고리즘은 일정한 시간 내에 종료되어야 한다.

-효율성 : 알고리즘은 효율적일수록 그 가치가 높아진다.



알고리즘의 표현 방법 


말로 표현 :

ex)첫 카드의 숫자를 읽고...

다음 카드의 


의사 코드 : 프로그래밍 언어와 유사

ex)



여러가지 알고리즘

#해결방식에 의한 알고리즘 분류
-분할 정복 알고리즘
-그리디 알고리즘
-동적 계획 알고리즘
-근사 알고리즘
-백트래킹 기법
-분기 한정 기법
-기타 등등



문제를 해결하는 방식은 문제의 속성과 밀접한 관계가 있으므로, 문제에 따라 알고리즘을 사용해야함


#문제에 기반한 알고리즘

-정렬 알고리즘

-그래프 알고리즘

-기하 알고리즘

-기타 등등


알고리즘의 효율성 표현


#시간복잡도와 공간복잡도 → 주로 시간복잡도가 사용됨.


시간을 측정하기 위해 컴퓨터를 사용할 수가 없음(측정하는 컴퓨터의 모든 조건이 같아야 하므로 평가가 어려움)

때문에 → 알고리즘이 수행하는 기본적인 연산 횟수를 입력 크기에 대한 함수로 표현.


#복잡도를 표현하는 세가지 방법

-최악의 경우 

-평균의 경우

-최선의 경우


#복잡도의 점근적 표기


위에서 말했듯이 연산 횟수를 입력 크기에 대한 함수로 표현하는데 이를 단순하게 표현하기 위해 점근적 표기법을 사용한다.


점근적 표기의 세가지

-빅오 표기법

-빅 오메가 표기법

-빅 세타 표기법


※ 점근적 표기법은 따로 책을 보시면서 공부하는게 도움이 될듯 싶습니다.


+ Recent posts