반응형
Clustering 의 문제 정의, 문제 해결방향? 은 pdf에 설명되어있다.
(
우리 학과 전교수님 출처
)
-
Clustering 이란 데이터를 분류하는 방법이다.
-
Clustering 구현 방법
방법 1. 임의의 점 하나(x1)를 첫 번째 cluster head로 지정하고,
x1과의 거리가 가장 먼 것(x2)을 두 번째 cluster head,
x1, x2와 거리가 가장 먼 것(x3)을 세 번째 cluster head로 지정한다.
...(반복)
그리고 cluster head를 제외한 나머지 점들은 cluster head들과 거리를 비교하며 가장 가까운 cluster head에 속하는 그룹이 된다.
(cluster head란 그룹의 대표임.)
-수도코드
(첫 번째 cluster head외의 나머지 cluster head를 뽑는 법)
모든 데이터점을 각각 cluster heads와의 거리를 계산한다.
그 중 가장 짧은 값을 가지고 있는다.
데이터 별로 모든 cluster head와 비교하였을 때, 가장 짧은 distance를 저장하고 있고
그 distance를 비교하여 가장 큰 값을 가지고 있는 데이터를 새로운 cluster head로 정한다.
(최소중 최대를 고르기)
- 나아가기 1
Q. Clustering 몇 개의 그룹으로 나누는게 효율적인가?
즉, clustering에서 head의 개수가 몇 개일 때 가장 최적인지 알 수 있는 방법은?
=> head와 데이터의 거리의 평균이 가장 작을 때, 가장 최적의 그룹의 개수이다.
Q. 그렇다면 언제 가장 평균 거리가 짧을까?
=> n개의 데이터가 있을 때, n개의 그룹으로 나눌 때 평균거리가 가장 짧다.
(데이터와 cluster head와의 거리가 0이니까)
결과적으로, cluster별 평균 거리의 감소폭이 둔화되는 시점이 최적의 k개수이다.
-
나아가기 2
방법 1 의 단점 : 첫 번째 cluster head를 우리가 임의로 지정해주고, 그걸 기준으로 나머지 cluster head들을 뽑는다.
-> 이럴 경우, 최악의 조건이 걸릴 수 있다. 왜냐하면 처음 지정한 cluster head가 전체 데이터들의 가장 가운데 값을 고를 수도 있기 때문이다.
(합리적인 분류가 불가능)
해결법 (방법2) : "K-means Clustering"
Cluster별로 평균 거리를 계산해나가며, 새로운 cluster head를 뽑는다.
-수도코드
(1) 랜덤하게 k개의 cluster head 2차원 값을 정한다.
(데이터에 없는 값이라도 상관없다.)
(2) 각 데이터를 가까운 cluster head에 배정한다.
(3) cluster별로, 평균값을 구해서 새로운 cluster head로 삼는다.
(위 2번과 3번 과정을 반복한다. )
-> Q. 언제 이 반복을 멈춰야 할까?
--> 새로 뽑힌 cluster head가 이전 cluster head와의 차이값이 thresh hold(내가 정해놓은 값)보다 작으면 break;
-
K-Means Clustering의 사용 예시
-> 머신러닝의 기초가 된다.
(1) 문자열이 있을 때, 문자마다 자르는 방법
ex) 가나초콜릿 -> 가. 나. 초. 콜. 릿
(2) 자동차 운전자 성향 그룹화
(3) 한국 사람 100개의 이미지를 이용해 평균 얼굴 이미지
-
k-means clustering 단점
: k(몇 개의 그룹으로 나눌지)를 우리가 가정해서 풀어야한다.
-
C언어 구현 코드
방법1
// Clustering - 2차원 데이터
#include < stdio.h >
#include < stdlib.h >
#define SZ 100
// ------------ 기본 점 구조체
struct point {
int x;
int y;
};
struct point points[SZ];
int idx = 0; // 점의 개수
// ------------ cluster head 구조체
int firstClusterHead; // 첫번째 cluster head
struct idxNode {
int nodeNum;
struct idxNode *next;
};
struct idxNode *head = 0; // cluster head들을 SLL로 저장할 것임.
// -------------------------함수들
void initData(); // forward declaration
// 점들을 points[] array에 저장한다.
// idx : 점의 개수-1
void addPoint(int x, int y) {
points[idx].x = x;
points[idx].y = y;
idx++;
}
// (x1,y1) (x2,y2) 의 거리를 계산하는 함수
int calcDistance(int x1, int y1, int x2, int y2) {
return (x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2);
}
// SLL에 cluster head의 index를 저장한다.
void addToSLL(int _idx) {
// 새로운 node 할당, idx로 nodeNum 설정
struct idxNode *new_one = (struct idxNode*)malloc(sizeof(struct idxNode));
new_one->nodeNum = _idx;
new_one->next = 0;
// SLL에 붙이기
if (head == 0) {
head = new_one;
}
else {
struct idxNode *temp = head;
while (temp->next != 0) {
temp = temp->next;
}
temp->next = new_one;
}
}
// idx가 이미 cluster head인지 검사
// 만약 cluster head이면 return 1
// 아니면 return 0
int amIClusterHead(int idx) {
// SLL을 뒤지면서 idx와 일치하는 것이 있는지를 판단
struct idxNode *temp = head;
while (temp != 0) {
if (temp->nodeNum == idx) {
return 1;
}
temp = temp->next;
}
return 0;
}
// SLL의 cluster head들과의 거리들 중에서
// 최소인 것을 찾아서 그 거리를 반환한다.
int findNearestDistancetoClusterHead(int _i) {
struct idxNode *temp = head;
int distance = INT_MAX;
while (temp != 0) { // cluster head SLL
// 가장 짧은 거리 계산
int d = calcDistance(points[_i].x, points[_i].y, // _i 점과 cluster head의 거리 계산
points[temp->nodeNum].x, points[temp->nodeNum].y);
if (distance > d) { // distance를 가장 작은 값으로 update
distance = d;
}
temp = temp->next;
}
return distance;
}
// cluster head를 찾는 함수
void findNewClusterHead() {
int maxDistance = 0;
int maxDistanceId = -1;
for (int i = 0; i < SZ; i++) { // 모든 점에 대해서...
// 이미 cluster head라면 pass
if (amIClusterHead(i) == 1) {
continue;
}
// 거리 비교 - 최대를 찾기
int d = findNearestDistancetoClusterHead(i);
if (d > maxDistance) { // maxDistance를 큰 값으로 update
maxDistance = d;
maxDistanceId = i;
}
}
// 모든 점을 다 확인 해봤을 때,
// 모든 cluster head와 가장 먼 거리에 있는 점(maxDistanceId)이
// 또 다른 그룹의 cluster head가 된다.
addToSLL(maxDistanceId); // cluster head SLL에 추가
}
// points[i]와 가장 가까운 cluster head의 인덱스와
// 거기까지의 거리를 구한다.
// i : 비교하려는 점의 인덱스
// dist : 가장 가까운 클러스터와의 거리
// cidx : 가장 가까운 클러스터의 idx
void findNearestClusterIndexAndDistance(int i, int *_dist, int *_cidx) {
struct idxNode *temp = head;
int distance = INT_MAX;
int cidx = -1;
while (temp != 0) { // 모든 cluster head와 다 비교한다.
// 가장 짧은 거리 계산
int d = calcDistance(points[i].x, points[i].y, // i 점과 cluster head와의 거리를 계산한다.
points[temp->nodeNum].x, points[temp->nodeNum].y);
if (distance > d) { // distance를 작은 값으로 update
distance = d;
cidx = temp->nodeNum;
}
temp = temp->next;
}
// return값이 여러 개 있을 때는 struct 를 만들어서 넘겨줄 수도 있지만,
// 포인터를 사용해서 주소값을 넘겨줄 수 있다.
*_dist = distance;
*_cidx = cidx;
}
int main() {
initData(); // 100개의 점 생성
firstClusterHead = 27; // index=27번째 점을 첫번째 cluster head로
addToSLL(firstClusterHead); // cluster head의 index들을 SLL에 저장한다.
int num_of_clusters = 4;
for (int i = 0; i < num_of_clusters - 1; i++) { // fisrt cluster는 지정하고 시작하므로, 3개만 구하면 된다.
findNewClusterHead();
}
// show cluster heads
struct idxNode *temp = head;
while (temp != 0) {
printf("Cluster head (%d,%d)\n", points[temp->nodeNum].x, points[temp->nodeNum].y);
temp = temp->next;
}
// 모든 점들을 하나씩 점검해서 어느 클러스터에 속하는지를 출력한다.
//
for (int i = 0; i < SZ; i++) {
// 1. points[i]가 클러스터 헤더인지 확인
if (amIClusterHead(i) == 1) {
continue;
}
// 2. 클러스터 헤더들 중에서 가장 가까운 클러스터를 찾아서 출력한다.
int cidx;
int distance;
findNearestClusterIndexAndDistance(i, &distance, &cidx);
printf("printf (%d,%d) ------> cluster %d (%d,%d) dist : %d\n", points[i].x, points[i].y,
cidx, points[cidx].x, points[cidx].y, distance);
}
return 0;
}
void initData() {
addPoint(117, 637);
addPoint(105, 79);
addPoint(427, 239);
addPoint(727, 598);
addPoint(543, 638);
addPoint(591, 855);
addPoint(135, 175);
addPoint(718, 108);
addPoint(258, 180);
addPoint(65, 574);
addPoint(548, 937);
addPoint(568, 313);
addPoint(761, 284);
addPoint(268, 772);
addPoint(193, 809);
addPoint(983, 896);
addPoint(476, 158);
addPoint(186, 901);
addPoint(120, 794);
addPoint(851, 749);
addPoint(976, 109);
addPoint(675, 651);
addPoint(970, 192);
addPoint(726, 387);
addPoint(358, 493);
addPoint(117, 789);
addPoint(675, 25);
addPoint(571, 85);
addPoint(818, 56);
addPoint(258, 823);
addPoint(825, 508);
addPoint(80, 930);
addPoint(939, 235);
addPoint(334, 477);
addPoint(456, 481);
addPoint(186, 751);
addPoint(25, 800);
addPoint(735, 935);
addPoint(908, 668);
addPoint(567, 753);
addPoint(305, 950);
addPoint(654, 125);
addPoint(545, 879);
addPoint(982, 333);
addPoint(313, 85);
addPoint(180, 748);
addPoint(244, 25);
addPoint(485, 766);
addPoint(440, 757);
addPoint(836, 381);
addPoint(344, 410);
addPoint(325, 637);
addPoint(703, 148);
addPoint(188, 429);
addPoint(654, 662);
addPoint(865, 305);
addPoint(921, 500);
addPoint(58, 839);
addPoint(789, 162);
addPoint(724, 222);
addPoint(463, 836);
addPoint(295, 938);
addPoint(773, 166);
addPoint(550, 347);
addPoint(567, 677);
addPoint(113, 746);
addPoint(297, 352);
addPoint(487, 22);
addPoint(286, 488);
addPoint(635, 723);
addPoint(506, 230);
addPoint(887, 847);
addPoint(387, 871);
addPoint(507, 555);
addPoint(664, 577);
addPoint(853, 809);
addPoint(862, 643);
addPoint(967, 341);
addPoint(205, 487);
addPoint(489, 813);
addPoint(238, 695);
addPoint(880, 277);
addPoint(378, 516);
addPoint(121, 95);
addPoint(795, 93);
addPoint(605, 129);
addPoint(418, 587);
addPoint(983, 536);
addPoint(637, 962);
addPoint(884, 798);
addPoint(881, 255);
addPoint(88, 335);
addPoint(517, 763);
addPoint(535, 942);
addPoint(859, 138);
addPoint(363, 56);
addPoint(427, 969);
addPoint(18, 421);
addPoint(699, 632);
addPoint(389, 427);
}
-
실행결과
-
C언어 구현 코드
방법1 + 점들과 cluster head와의 평균 거리 계산
// Clustering - 2차원 데이터
#include < stdio.h >
#include < stdlib.h >
#define SZ 100
// ------------ 기본 점 구조체
struct point {
int x;
int y;
};
struct point points[SZ];
int idx = 0; // 점의 개수
// ------------ cluster head 구조체
int firstClusterHead; // 첫번째 cluster head
struct idxNode {
int nodeNum;
struct idxNode *next;
};
struct idxNode *head = 0; // cluster head들을 SLL로 저장할 것임.
// -------------------------함수들
void initData(); // forward declaration
// 점들을 points[] array에 저장한다.
// idx : 점의 개수-1
void addPoint(int x, int y) {
points[idx].x = x;
points[idx].y = y;
idx++;
}
// (x1,y1) (x2,y2) 의 거리를 계산하는 함수
int calcDistance(int x1, int y1, int x2, int y2) {
return (x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2);
}
// SLL에 cluster head의 index를 저장한다.
void addToSLL(int _idx) {
// 새로운 node 할당, idx로 nodeNum 설정
struct idxNode *new_one = (struct idxNode*)malloc(sizeof(struct idxNode));
new_one->nodeNum = _idx;
new_one->next = 0;
// SLL에 붙이기
if (head == 0) {
head = new_one;
}
else {
struct idxNode *temp = head;
while (temp->next != 0) {
temp = temp->next;
}
temp->next = new_one;
}
}
// idx가 이미 cluster head인지 검사
// 만약 cluster head이면 return 1
// 아니면 return 0
int amIClusterHead(int idx) {
// SLL을 뒤지면서 idx와 일치하는 것이 있는지를 판단
struct idxNode *temp = head;
while (temp != 0) {
if (temp->nodeNum == idx) {
return 1;
}
temp = temp->next;
}
return 0;
}
// SLL의 cluster head들과의 거리들 중에서
// 최소인 것을 찾아서 그 거리를 반환한다.
int findNearestDistancetoClusterHead(int _i) {
struct idxNode *temp = head;
int distance = INT_MAX;
while (temp != 0) { // cluster head SLL
// 가장 짧은 거리 계산
int d = calcDistance(points[_i].x, points[_i].y, // _i 점과 cluster head의 거리 계산
points[temp->nodeNum].x, points[temp->nodeNum].y);
if (distance > d) { // distance를 가장 작은 값으로 update
distance = d;
}
temp = temp->next;
}
return distance;
}
// cluster head를 찾는 함수
void findNewClusterHead() {
int maxDistance = 0;
int maxDistanceId = -1;
for (int i = 0; i < SZ; i++) { // 모든 점에 대해서...
// 이미 cluster head라면 pass
if (amIClusterHead(i) == 1) {
continue;
}
// 거리 비교 - 최대를 찾기
int d = findNearestDistancetoClusterHead(i);
if (d > maxDistance) { // maxDistance를 큰 값으로 update
maxDistance = d;
maxDistanceId = i;
}
}
// 모든 점을 다 확인 해봤을 때,
// 모든 cluster head와 가장 먼 거리에 있는 점(maxDistanceId)이
// 또 다른 그룹의 cluster head가 된다.
addToSLL(maxDistanceId); // cluster head SLL에 추가
}
// points[i]와 가장 가까운 cluster head의 인덱스와
// 거기까지의 거리를 구한다.
// i : 비교하려는 점의 인덱스
// dist : 가장 가까운 클러스터와의 거리
// cidx : 가장 가까운 클러스터의 idx
void findNearestClusterIndexAndDistance(int i, int *_dist, int *_cidx) {
struct idxNode *temp = head;
int distance = INT_MAX;
int cidx = -1;
while (temp != 0) { // 모든 cluster head와 다 비교한다.
// 가장 짧은 거리 계산
int d = calcDistance(points[i].x, points[i].y, // i 점과 cluster head와의 거리를 계산한다.
points[temp->nodeNum].x, points[temp->nodeNum].y);
if (distance > d) { // distance를 작은 값으로 update
distance = d;
cidx = temp->nodeNum;
}
temp = temp->next;
}
// return값이 여러 개 있을 때는 struct 를 만들어서 넘겨줄 수도 있지만,
// 포인터를 사용해서 주소값을 넘겨줄 수 있다.
*_dist = distance;
*_cidx = cidx;
}
int main() {
initData(); // 100개의 점 생성
firstClusterHead = 27; // index=27번째 점을 첫번째 cluster head로
addToSLL(firstClusterHead); // cluster head의 index들을 SLL에 저장한다.
int num_of_clusters = 8;
for (int i = 0; i < num_of_clusters - 1; i++) { // fisrt cluster는 지정하고 시작하므로, 3개만 구하면 된다.
findNewClusterHead();
}
// show cluster heads
struct idxNode *temp = head;
while (temp != 0) {
printf("Cluster head (%d,%d)\n", points[temp->nodeNum].x, points[temp->nodeNum].y);
temp = temp->next;
}
// 모든 데이터와 클러스터 헤드와의 평균 거리를 구하기 위해
unsigned int totalsum = 0;
// (참고) int는 20억 -> unsigned int 40억
// 만약 unsigned int 크기를 넘어선다면, 임의의 큰 숫자 백만을 나누고
// 나중에 평균 계산할 때 백만을 곱해서 계산하면 된다.
// 아니면 백만을 생략한 것으로 가정하고 계산하면 된다.
// 모든 점들을 하나씩 점검해서 어느 클러스터에 속하는지를 출력한다.
for (int i = 0; i < SZ; i++) {
// 1. points[i]가 클러스터 헤더인지 확인
if (amIClusterHead(i) == 1) {
continue;
}
// 2. 클러스터 헤더들 중에서 가장 가까운 클러스터를 찾아서 출력한다.
int cidx;
int distance;
findNearestClusterIndexAndDistance(i, &distance, &cidx);
//printf("printf (%d,%d) ------> cluster %d (%d,%d) dist : %d\n", points[i].x, points[i].y,
// cidx, points[cidx].x, points[cidx].y, distance);
totalsum += distance;
}
printf("Cluster head의 개수가 %d 일때 : 평균거리 %d\n", num_of_clusters, totalsum/(SZ- num_of_clusters));
return 0;
}
void initData() {
addPoint(117, 637);
addPoint(105, 79);
addPoint(427, 239);
addPoint(727, 598);
addPoint(543, 638);
addPoint(591, 855);
addPoint(135, 175);
addPoint(718, 108);
addPoint(258, 180);
addPoint(65, 574);
addPoint(548, 937);
addPoint(568, 313);
addPoint(761, 284);
addPoint(268, 772);
addPoint(193, 809);
addPoint(983, 896);
addPoint(476, 158);
addPoint(186, 901);
addPoint(120, 794);
addPoint(851, 749);
addPoint(976, 109);
addPoint(675, 651);
addPoint(970, 192);
addPoint(726, 387);
addPoint(358, 493);
addPoint(117, 789);
addPoint(675, 25);
addPoint(571, 85);
addPoint(818, 56);
addPoint(258, 823);
addPoint(825, 508);
addPoint(80, 930);
addPoint(939, 235);
addPoint(334, 477);
addPoint(456, 481);
addPoint(186, 751);
addPoint(25, 800);
addPoint(735, 935);
addPoint(908, 668);
addPoint(567, 753);
addPoint(305, 950);
addPoint(654, 125);
addPoint(545, 879);
addPoint(982, 333);
addPoint(313, 85);
addPoint(180, 748);
addPoint(244, 25);
addPoint(485, 766);
addPoint(440, 757);
addPoint(836, 381);
addPoint(344, 410);
addPoint(325, 637);
addPoint(703, 148);
addPoint(188, 429);
addPoint(654, 662);
addPoint(865, 305);
addPoint(921, 500);
addPoint(58, 839);
addPoint(789, 162);
addPoint(724, 222);
addPoint(463, 836);
addPoint(295, 938);
addPoint(773, 166);
addPoint(550, 347);
addPoint(567, 677);
addPoint(113, 746);
addPoint(297, 352);
addPoint(487, 22);
addPoint(286, 488);
addPoint(635, 723);
addPoint(506, 230);
addPoint(887, 847);
addPoint(387, 871);
addPoint(507, 555);
addPoint(664, 577);
addPoint(853, 809);
addPoint(862, 643);
addPoint(967, 341);
addPoint(205, 487);
addPoint(489, 813);
addPoint(238, 695);
addPoint(880, 277);
addPoint(378, 516);
addPoint(121, 95);
addPoint(795, 93);
addPoint(605, 129);
addPoint(418, 587);
addPoint(983, 536);
addPoint(637, 962);
addPoint(884, 798);
addPoint(881, 255);
addPoint(88, 335);
addPoint(517, 763);
addPoint(535, 942);
addPoint(859, 138);
addPoint(363, 56);
addPoint(427, 969);
addPoint(18, 421);
addPoint(699, 632);
addPoint(389, 427);
}
-
실행결과
=> k를 하나씩 늘려가며 실행해보았다.
직관적으로 봤을 때 기하급수적으로 줄어드는 구간은 k=5일 때로 보인다.
따라서 최적의 k개수는 5라고 생각한다.
-
C언어 구현 코드
방법2 (k-means clustering)
- 방법1의 코드에서 변경된 부분은 cluster head를 저장하는 struct SLL 구조를 struct Array에 저장하는 구조로 변경하였다.
그리고 2차원 데이터를 저장하는 point 구조체에 ch라는 변수를 추가하여, 어느 그룹에 소속하는지 저장하도록 하였다.
// Clustering - 2차원 데이터
#include < stdio.h >
#include < stdlib.h >
#define SZ 100
// ------------ 기본 점 구조체
struct point {
int x;
int y;
int ch; // cluster head ( 어느 그룹에 속하는지 )
};
struct point points[SZ];
int idx = 0; // 점의 개수
// ------------ cluster head 를 저장하는 공간
// struct SLL -> struct Array 로 변경
int firstClusterHead; // 첫번째 cluster head
struct point clusterhead[3]; // 클러스터 3개 생성
// -------------------------함수들
void initData(); // forward declaration
// 점들을 points[] array에 저장한다.
// idx : 점의 개수-1
void addPoint(int x, int y) {
points[idx].x = x;
points[idx].y = y;
points[idx].ch = -1; // 어느 그룹에 속하는지
idx++;
}
// (x1,y1) (x2,y2) 의 거리를 계산하는 함수
int calcDistance(int x1, int y1, int x2, int y2) {
return (x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2);
}
// Array에 cluster head를 저장한다.
void setClusterHead(int _idx, int _x, int _y) {
clusterhead[_idx].x = _x;
clusterhead[_idx].y = _y;
}
// 데이터 (x,y) 가 어느 그룹에 속하는지 계산하는 함수
// 모든 cluster head와 거리를 계산하여, 가장 작은 거리값을 가진 클러스터헤드의 소속으로,,,,
int findNearestClusterHeadIndex(int _x, int _y) {
int nearestIdx = 0;
int nearestDistance = calcDistance(_x, _y, clusterhead[0].x, clusterhead[0].y); // 첫번째 클러스터 헤드와의 거리 계산
for (int i = 1; i < 3; i++) { // 나머지 클러스터 헤드와의 거리도 계산하여, 가장 작은 거리값을 가진 클러스터 헤드의 소속으로,,,,
int _d = calcDistance(_x, _y, clusterhead[i].x, clusterhead[i].y);
if (nearestDistance > _d) { // 작은값으로 update
nearestDistance = _d;
nearestIdx = i;
}
}
return nearestIdx;
}
// 100개의 데이터 각각이 어느 그룹에 속하는지 분류하는 함수
void classifyPoints() {
// 모든 점들에 대해서 가장 가까운 cluster head를 찾아서
// 그 헤드의 인덱스를 저장
for (int i = 0; i < SZ; i++) {
int cidx = findNearestClusterHeadIndex(points[i].x, points[i].y);
points[i].ch = cidx;
}
}
// 각 그룹별로 (x,y)의 평균값을 계산하여 새로운 cluster head (x,y) 뽑는다.
// return : 새로 뽑힌 cluster head와 이전 cluster head와의 차이값을 반환한다.
int electNewClusterHead() {
int moveDistance = 0;
for (int ch = 0; ch < 3; ch++) { // 각 cluster head
int cnt = 0; // 갯수
int temp_x = 0;
int temp_y = 0;
for (int j = 0; j < SZ; j++) { // 모든 점(데이터) 확인
// 그룹 별로 갯수, (x,y) 합 구하기
if (points[j].ch == ch) {
cnt++;
temp_x += points[j].x;
temp_y += points[j].y;
}
}
// 새로운 cluster로 지정
if (cnt == 0) {
cnt = 1;
}
else {
// 새로운 cluster x,y = 평균값 = 합/갯수
int new_clusterhead_x = temp_x / cnt;
int new_clusterhead_y = temp_y / cnt;
// moveDistance : 새로 뽑힌 cluster head와 이전 cluster head와의 차이값
// 나중에 thresh hold 와 값을 비교하여, 큰 차이가 없을 경우
// 새로운 cluster head를 뽑는 (반복) 동작을 멈추기 위해 사용된다.
moveDistance += (new_clusterhead_x - clusterhead[ch].x)*(new_clusterhead_x - clusterhead[ch].x) + (new_clusterhead_y - clusterhead[ch].y)*(new_clusterhead_y - clusterhead[ch].y);
clusterhead[ch].x = new_clusterhead_x;
clusterhead[ch].y = new_clusterhead_y;
}
}
return moveDistance;
}
void showClusterHead() {
for (int i = 0; i < 3; i++) {
printf("number %d cluster head (%d,%d)\n",i,clusterhead[i].x, clusterhead[i].y);
}
printf("\n");
}
int main() {
initData(); // 100개의 점 생성 - points[] 배열에 (x,y) 데이터들 저장
// random 3개의 cluster head를 정함
setClusterHead(0, 100, 100); // (100,100)을 첫번째 클러스터
setClusterHead(1, 400, 400);
setClusterHead(2, 800, 800);
// *** 반복
int threshold = 100;
for (int i = 0; i < 200; i++) {
// 100개의 데이터 각각이 어느 그룹에 속하는지
// point들을 cluster head와의 거리에 따라서 분류한다.
classifyPoints();
// cluster별로 새로운 cluster head를 뽑는다.
int moveDistance = electNewClusterHead();
if (moveDistance < threshold) {
break;
}
// 새로운 cluster를 한 번 출력하기
printf("%d번째 구하는중\n",i+1);
showClusterHead();
}
// *** 반복
return 0;
}
void initData() {
addPoint(117, 637);
addPoint(105, 79);
addPoint(427, 239);
addPoint(727, 598);
addPoint(543, 638);
addPoint(591, 855);
addPoint(135, 175);
addPoint(718, 108);
addPoint(258, 180);
addPoint(65, 574);
addPoint(548, 937);
addPoint(568, 313);
addPoint(761, 284);
addPoint(268, 772);
addPoint(193, 809);
addPoint(983, 896);
addPoint(476, 158);
addPoint(186, 901);
addPoint(120, 794);
addPoint(851, 749);
addPoint(976, 109);
addPoint(675, 651);
addPoint(970, 192);
addPoint(726, 387);
addPoint(358, 493);
addPoint(117, 789);
addPoint(675, 25);
addPoint(571, 85);
addPoint(818, 56);
addPoint(258, 823);
addPoint(825, 508);
addPoint(80, 930);
addPoint(939, 235);
addPoint(334, 477);
addPoint(456, 481);
addPoint(186, 751);
addPoint(25, 800);
addPoint(735, 935);
addPoint(908, 668);
addPoint(567, 753);
addPoint(305, 950);
addPoint(654, 125);
addPoint(545, 879);
addPoint(982, 333);
addPoint(313, 85);
addPoint(180, 748);
addPoint(244, 25);
addPoint(485, 766);
addPoint(440, 757);
addPoint(836, 381);
addPoint(344, 410);
addPoint(325, 637);
addPoint(703, 148);
addPoint(188, 429);
addPoint(654, 662);
addPoint(865, 305);
addPoint(921, 500);
addPoint(58, 839);
addPoint(789, 162);
addPoint(724, 222);
addPoint(463, 836);
addPoint(295, 938);
addPoint(773, 166);
addPoint(550, 347);
addPoint(567, 677);
addPoint(113, 746);
addPoint(297, 352);
addPoint(487, 22);
addPoint(286, 488);
addPoint(635, 723);
addPoint(506, 230);
addPoint(887, 847);
addPoint(387, 871);
addPoint(507, 555);
addPoint(664, 577);
addPoint(853, 809);
addPoint(862, 643);
addPoint(967, 341);
addPoint(205, 487);
addPoint(489, 813);
addPoint(238, 695);
addPoint(880, 277);
addPoint(378, 516);
addPoint(121, 95);
addPoint(795, 93);
addPoint(605, 129);
addPoint(418, 587);
addPoint(983, 536);
addPoint(637, 962);
addPoint(884, 798);
addPoint(881, 255);
addPoint(88, 335);
addPoint(517, 763);
addPoint(535, 942);
addPoint(859, 138);
addPoint(363, 56);
addPoint(427, 969);
addPoint(18, 421);
addPoint(699, 632);
addPoint(389, 427);
}
-
실행결과
threshold = 100,
클러스터 헤드를 다음과 같이 설정하였을 때,
(100,100)
(101,101)
(102,102)
실행결과 이미지.
threshold = 100,
클러스터 헤드를 다음과 같이 설정하였을 때,
(100,100)
(400,400)
(800,800)
실행결과 이미지.
=> 결론. k-means clustering 방법은 더 적절한 cluster head를 찾아서 이동한다고 하지만,
결국에는 이것도 내가 처음에 random 으로 cluster head를 어떻게 정해주는지에 따라
분류하는게 달라지지 않나? 그러면 성능도 달라지는 거고!
(결국에는 처음에 분류화된 그룹내에서 최적의 center를 찾느거니까)
=> 틀렸음!
왜냐면 cluster 그룹 내에서 적절한 cluster head를 뽑은다음에
새로 뽑은 cluster head를 기준으로 새로 분류화하니까
다음 반복때는 새로운 그룹에서의 또 최적의 cluster head를 뽑으니까!!
그래서 결국엔 처음에 내가 지정해준 랜덤의 cluster head와 상관없이 똑같은 결과가 보여지게 됌.
반응형
