일단 대충 요약하자면 Heapsort는 O(nlogn)의 시간복잡도를 자랑한다. 근데 그전에 Heap이 뭔지는 설명해야 할거 아닌가? Heap데이터 구조인 Heap은 거의 CBT로 볼수있는 array object라고 할 수 있겠다. 위 사진에서 볼 수 있듯 어떤 노드의 요소는 배열의 어떤 요소에 대응될 수 있을 것이다. 대충 배열 이름을 A라고 해보면, 트리의 루트는 A[1]이 될 것이고 이런식으로 치면 아래와 같이 PARENT/LEFT/RIGHT NODE를 구할 수 있을 것이다. Parent : [ i/2 ]Left : 2iRight : 2i + 1when i is 0>=. 그리고 Binary한 Heap에는 두가지 종류가 있는데, 하나는 max-heap이고 다른 하나는 min-heap이 되..

아달린에서 여러개로 분신술을 펼친 것이 바로 MLP라고 할 수 있으며, 사실상 요즘 ML에서 가장 핫한놈이라고 할 수 있겠다. 이놈들은 대충 아래와 같은 과정을 통해서, 학습을 진행하고 출력한다고 할 수 있다.Input Layer에서 시작해서 정방향으로 훈련데이터의 패턴을 네트워크에 Propagate해 출력을 만든다.출력을 기반으로 비용 함수를 이용해 최소화 해야할 오차를 계산한다.네트워크에 있는 모든 가중치에 대한 도함수를 찾아 오차를 역전파하고 모델을 업데이트 한다.여기서 알 수 있듯이 MLP는 피드포워드 인공신경망이다. 이때 feed forward란 각 층에서 입력을 순환시키지 않고 다음층으로 전달한다는 의미다. (RNN과는 다르다는 소리다.) 다만 이의 Back Propagation과정은 상당히 ..

Ensemble Learning을 여러 분류기의 의견을 종합해서 결과를 도출하는 방식이다. 대표적으로 과반수 이상의 투표를 받았을 때 선출하는 과반수 투표 방식이 있을 것이다(물론 각 동등한 1표를 부여할 수도 있겠으나, 가중치가 적용된 다수결 투표 또한 가능하다.) 그리고 이는 이항 이론상 개별 분류기가 무작위 추측보다 성능이 좋다고 하면은, 앙상블의 에러 확률은 개별 분류기 보다 항상 좋다. BaggingBagging은 다수결 투표와 밀접하긴 하지만... 원본 훈륜 데이터셋에서 부트스트랩(중복허용 랜덤샘플)을 한다는게 특징이다. 이에 대해서 1994년 레오 브레이만이 Bagging을 사용하면 Overfit을 줄일 수 있다는 것을 보였다. 추가로, 배깅은 부트스트랩을 사용하기 때문에 여분의 샘플(OO..

LDA는 Regulation이 없는 모델에서 특성 추출의 기법으로 사용 가능하다. PCA와 목표는 비슷한데, 대걍 클래스를 최적으로 구분할 수 있는 특성 부분 공간을 찾고자 하는 것이다. 참고로 PCA는 비지도 학습, LDA는 지도 학습이 된다. 대충 LDA 수행에 필요한 주요 단계는 아래와 같다.d차원의 데이터 셋을 표준화 전처리 한다.각 클래스에 대해 d차원 마다 평균 벡터를 계산한다.클래스간의 산포행렬과 클래스 내부의 산포행렬을 구성한다.(클래스간 산포행렬 inversed) * 클래스내 산포행렬의 eigenvalue와 eigenvector를 계산한다.고윳값을 내림차순으로 정렬해서 순서를 매긴다.가장 큰 k개의 고유 벡터를 선택해서 d times k 차원의 변환행렬을 구성한다.변환행렬을 사용하여 샘플..

데이터의 차원 축소를 위한 방법에는 특성 선택 뿐만 아니라 특성 추출 또한 존재한다. 특히 비지도 데이터를 가지고 지지고 볶을 때 그냥 생으로 분석하면 머리가 아프고 가슴이 울럭거린다. 이때 Principal Component Analysis, 즉 다시 말해 주성분 분석은 도움이 된다. 이는 데이터에서 분산이 가장 큰 성분(== 설명력이 큰 성분)을 찾고 같거나 작은 차원으로 투영하는데 큰 도움을 준다. 일단 PCA 알고리즘은 다음과 같이 실행하게 된다.d차원 데이터셋을 표준화 전처리 한다. (스케일링은 필수다!)Covariance Matrix를 만든다.Covariance Matrix를 eigenvector(고유벡터)와 eigenvalue로 분해한다.Eigenvalue의 impact를 따져서 그에 맞는 ..

ML에서 연구자들이 SVM을 사랑하는 이유에는 비선형 데이터를 다룰 수 있다는 점에 있다. 물론 Kernel SVM에 한정한 얘기겠지만 말이다. Kernel SVM은 Linear하게 구분되지 않는데이터를 Projection을 통해 새로운 특성 공간으로 옮겨 구분하는것을 목적으로 둔다. 물론 아래와 같이 커널 함수는 좀 그지같이 생겼다. 이 비선형 데이터를 고차원 공간으로 옮겨서 내적 노가다를 해야 하는걸, 안 옮기고 내적값만 알 수 있게 해주는 함수라고 이해하면 편하다. 참고로 새로운 데이터가 어느 클래스일지 예측할때는 아래와 같은 함수를 사용하게 된다. 거 참 머리아프게 생겼지만, 결론은 커널 유사도 - 즉 서포트 벡터와 얼마나 같은지를 계산해서 가중합으로 더하는 것이라고 생각하면 된다.