728x90 Algorithm/Common2 K-means, Approx_k Clustering(의사코드, 근사비율) □ K-means 알고리즘 - k평균 클러스터링 알고리즘은 클러스터링 방법 중 분할법에 속한다. ex) N개의 데이터 오브젝트를 입력 받았다면, 분할법은 N보다 작거나 같은 K개의 그룹으로 나누는데, 이 때 각 군집은 클러스터를 형성하게 된다. (1개 이상의 데이터 오브젝트로 구성된 k개의 그룹으로 나누는것) 이 때 군집을 나누는 과정에서 같은 그룹 내 데이터 오브젝트 끼리 유사도는 증가 다른 그룹에 있는 데이터 오브젝트와의 유사도는 감소. - 최초에는 무작위 k개의 중심 1)데이터를 선정하고, 해당 데이터로부터 각 2)데이터의 거리(유클리디언, 맨하탄 등)을 계산한다. 그 거리의 평균이 작은 곳으로 3)중심점을 변경하고, 4)다시 거리를 계산하는 것을 반복하여 최적의 군집을 찾을 수 있다. (유클리디언.. 2016. 11. 16. 크러스컬 알고리즘(KruskalMST) □ 크러스컬 알고리즘은 최소비용 생성나무(spanning tree 스패닝 트리)를 찾는 알고리즘이다. (생성나무란 그래프 이론에서 모든 꼭짓점을 포함하는 부분 나무이다.) 크러스컬의 알고리즘은 최소 비용 신장 트리가 최소 비용의 간선으로 구성됨과 동시에 사이클(cycle)을 포함하지 않는다는 조건에 근거하여, 각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택. □ 크러스컬 알고리즘의 순서 - 먼저, 그래프의 각 간선(edge)들을 가중치의 오름차순으로 정렬. - 정렬된 간선들의 리스트에서 싸이클을 형성하지 않는 간선을 찾아 최소비용신장 트리(MST)의 집합에 추가 - 만약 사이클을 형성하면 그 간선은 버린다. □ 시간 복잡도KruskalMST(G)입력 : 가중치 그래프 G=(V,E), |V|=n,.. 2016. 9. 29. 이전 1 다음 728x90
