클래스로 짰습니다. 짜요 어머니(속닥속닥)
전체코드
import math
import random
class k_means:
def __init__(self, table, k=2):
self.table=table # 테이블
self.k=k # 클러스터, 집단 개수
# 좌표 내 랜덤으로 중점 구하기
def random_mid_point(self):
num=set() # 중복 제거
for tb in self.table: # 테이블을 순회하면서 좌표 값의 범위 파악
for t in tb: num.add(t)
num = list(num) # 집합을 리스트로 변경
mid_point = list();
for i in range(self.k): # k개로 나눠야 하므로 중점도 k개
m = list()
for j in range(2): # 좌표 값 (x,y)
m.append(random.randrange(min(num), max(num)+1)) # 좌표 범위 내에서 랜덤으로 중점 선정
mid_point.append(m)
return mid_point # 랜덤으로 뽑은 중점 리턴
# 테이블의 한 행(한 좌표)와 중점(두 개의 좌표) 사이의 유클라디안 거리 계산
def euclidean_distance(self, point, mid_point):
d_list=[] # 중점이 두 개 이므로, 나오는 유클라디안 거리도 2개. 최솟값을 찾기 위해 리스트로 선언
for mp in mid_point: # 중점(2행 2열) 순회
d=0 # 거리 초기화
for i in range(2): # 좌표 값은 x,y 총 2개
d+=pow(point[i]-mp[i], 2)
d_list.append(math.sqrt(d))
idx=d_list.index(min(d_list)) # 가장 작은 distance를 가진 값의 클러스터(인덱스, 0 or 1)를 추가
return idx # 클러스터 집단 리턴(0 or 1)
# 클러스터 생성
def create_cluster(self, mid_point):
cluster=[[] for _ in range(2)] # 빈 클러스터 생성
for i in range(len(self.table)): # 테이블 순회
idx = self.euclidean_distance(self.table[i], mid_point) # 유클라디안 거리 계산
cluster[idx].append(i) # 적절한 클러스터(0, 1)에 해당하는 값을 넣음
return cluster # 클러스터 리턴
# 새로운 중점 찾기, k-means
def new_mid_point(self, cluster):
total = [[] for _ in range(self.k)] # k 크기 만큼, 새로운 좌표 구하는 거니까!!!
avg = [[] for _ in range(self.k)] # 평균 값이자, 새로운 중점
for i in range(self.k): # k번 반복
x=0; y=0
for c in cluster[i]:
x+=self.table[c][0] # 테이블 좌표 값을 각각 저장
y+=self.table[c][1]
total[i].append(x); total[i].append(y) # total에 x좌표 y좌표 총합을 넣음
for i in range(self.k): # 클러스터 개수
for j in range(2): # 좌표 값
try: # 한 집단만 있을 경우 error 발생
avg[i].append(round(total[i][j] / len(cluster[i]), 2)) # ZeroDivisionError
except Exception as e:
return False # error 발생 시 False 리턴해서 다시 new_mid_point() 호출
return avg # 새로운 중점-평균- 리턴
def run(self):
mid_point = self.random_mid_point() # k개의 중점을 임의로 선택
cluster = self.create_cluster(mid_point) # 랜덤으로 선택한 중점을 기준으로 한 클러스터 생성
print("__________iteration = 0 __________")
for i in range(len(mid_point)): print("k = {}\t {}".format(i, mid_point[i]))
print("cluster\t", cluster)
new_mid_point = False # 아직 새로운 중점을 찾지 않았으므로 False로 설정
for i in range(1, 10): # n번 반복 후 강제 종료
if mid_point == new_mid_point: break # 이전 중점과 새 중점의 차이가 없으면 종료
# 기존의 중점과 클러스터, 1회전 이후에 업데이트
if i>=2:
mid_point = new_mid_point
cluster = new_cluster
# 새로운 중점과 클러스스터
while True: # 적절한 중점이 리턴될 때까지 반복
new_mid_point = self.new_mid_point(cluster)
if new_mid_point: break # error가 뜨지 않아서 false가 아닌 값이 날아올 경우 종료
new_cluster = self.create_cluster(new_mid_point) # 새로운 클러스터 생성
print("\n__________ iteration = {} __________".format(i)) # 새로 생성된 중점과 클러스터 출력
for i in range(len(mid_point)): print("k = {}번째 집단의 중점 \t {}".format(i, mid_point[i]))
print("cluster\t", new_cluster)if __name__ == '__main__':
table = [[1,1],[2,1],[1,2],[5,5],[6,5],[5,6],[7,7]]
test=k_means(table) # 객체 생성
test.run() # 실행
클러스터링 기본 개념
- 클러스터링? 입력 데이터를 그룹핑하는 것
왜 클러스터링을 해야 하는가? 이것은 비지도 학습 개념과 관련이 있다. 비지도 학습이란 라벨링이 없는 상태의 데이터를 가지고 하는 학습을 의미한다.
다음과 같은 관계형 테이블이 있고 우리는 지금부터 결혼 정보 업체 직원이다.(실제 데이터는 저렇게 생기지 않았다. 개념 이해로만 보자.)
| 외모 | 재력 | 결혼(라벨) |
| 공주 | 부자 | 가능 |
| 여신 | 거지 | 가능 |
그렇다면 기존의 데이터를 토대로 다음과 같은 사람이 결혼 정보 업체 회원으로 들어왔다고 가정하자.
| 요정 | 중산층 | ? |
지도 학습의 경우 위 표를 토대로 결혼 가능 확률을 측정할 수 있겠지만 비지도 학습은 라벨링이 없다. 이처럼 클러스터링은 라벨이 없는 데이터들을 그룹핑하기 위해 필요하다.
- 클러스터링이 필요한 이유?
- 입력 데이터의 특성이나 성질을 알기 위해 수행
- 클러스터링에서 학습 데이터는 필요하지 않음
k-means
- k-means? 클러스터링의 한 종류
- 알고리즘
- k개의 중점(x, y 좌표)을 랜덤으로 선택
- 각 점(입력 테이블의 한 행에 해당)과 중점들 간의 Euclidean Distance 계산(가장 작은 거리 찾아야 함)
- 각 클러스터에 있는 점들(x,y)의 평균 값을 그 클러스터의 새로운 중점으로 선택
- 종료 조건에 맞을 때 까지 2~3번 반복(n번 반복, 이전 중점과 새 중점 과 차이가 없을 때)
코드 분석
< 메인문 >
if __name__ == '__main__':
table = [[1,1],[2,1],[1,2],[5,5],[6,5],[5,6],[7,7]]
test=k_means(table) # 객체 생성
test.run() # 실행
테이블은 좌표 값이다. 어렵다면 직접 좌표 값을 그려보는 것도 좋다. (x축은 외모, y축은 재력!) 클래스로 짰으므로 객체 생성해주고 실행을 한다.
def __init__(self, table, k=2):
self.table=table # 테이블
self.k=k # 클러스터, 집단 개수
참고로 초기화는 위와 같다. 테이블과 클러스터 즉, 집단의 개수를 인스턴스로 선언해준다.
< run (1/2) >
def run(self):
mid_point = self.random_mid_point() # k개의 중점을 임의로 선택
cluster = self.create_cluster(mid_point) # 랜덤으로 선택한 중점을 기준으로 한 클러스터 생성
print("__________iteration = 0 __________")
for i in range(len(mid_point)): print("k = {}\t {}".format(i, mid_point[i]))
print("cluster\t", cluster)
먼저 알고리즘대로 랜덤으로 중점 하나를 골라준다..
< random_mid_point() >
def random_mid_point(self):
num=set() # 중복 제거
for tb in self.table: # 테이블을 순회하면서 좌표 값의 범위 파악
for t in tb: num.add(t)
num = list(num) # 집합을 리스트로 변경
mid_point = list();
for i in range(self.k): # k개로 나눠야 하므로 중점도 k개
m = list()
for j in range(2): # 좌표 값 (x,y)
m.append(random.randrange(min(num), max(num)+1)) # 좌표 범위 내에서 랜덤으로 중점 선정
mid_point.append(m)
return mid_point # 랜덤으로 뽑은 중점 리턴
random_mid_point()는 좌표 값들을 모두 불러와서 좌표 값들의 범위를 파악 한다. 그리고 그 범위 내에서 랜덤으로 좌표 값을 찾아 리턴하는 함수이다.
< create_cluster() >
def create_cluster(self, mid_point):
cluster=[[] for _ in range(2)] # 빈 클러스터 생성
for i in range(len(self.table)): # 테이블 순회
idx = self.euclidean_distance(self.table[i], mid_point) # 유클라디안 거리 계산
cluster[idx].append(i) # 적절한 클러스터(0, 1)에 해당하는 값을 넣음
return cluster # 클러스터 리턴
이후 이렇게 리턴받은 중점을 바탕으로 새로운 클러스터를 생성한다. 클러스터의 크기(행)는 k다. 왜냐면 집단을 k개로 나눠야 하기 때문이다. 열은 좌표 값이 들어가므로 2이다.
위 메소드에서는 테이블을 순회하며 현 중점과 각 테이블 행(x,y 좌표값) 간의 유클라디안 거리를 계산한다. 여기서 잠깐 유클라디안 거리 메소드로 가보겠다.
< eunclidean_distance() >
def euclidean_distance(self, point, mid_point):
d_list=[] # 중점이 두 개 이므로, 나오는 유클라디안 거리도 2개. 최솟값을 찾기 위해 리스트로 선언
for mp in mid_point: # 중점(2행 2열) 순회
d=0 # 거리 초기화
for i in range(2): # 좌표 값은 x,y 총 2개
d+=pow(point[i]-mp[i], 2)
d_list.append(math.sqrt(d))
idx=d_list.index(min(d_list)) # 가장 작은 distance를 가진 값의 클러스터(인덱스, 0 or 1)를 추가
return idx # 클러스터 집단 리턴(0 or 1)위 메소드에서는 중점이 2개 이므로 유클라디안 거리는 2개가 나오는데 둘 중에 가장 작은 값의 인덱스 번호를 리턴한다. 이때 인덱스 번호는 0 또는 1로, 2개의 집단(현재 k가 2이므로)으로 나눠질 수 있다. 다시 create_cluster()로 돌아가자.
< create_cluster() >
def create_cluster(self, mid_point):
cluster=[[] for _ in range(2)] # 빈 클러스터 생성
for i in range(len(self.table)): # 테이블 순회
idx = self.euclidean_distance(self.table[i], mid_point) # 유클라디안 거리 계산
cluster[idx].append(i) # 적절한 클러스터(0, 1)에 해당하는 값을 넣음
return cluster # 클러스터 리턴이렇게 리턴된 인덱스 값에 테이블의 인덱스 값을 집어넣는다. 왜 인덱스 값을 넣냐면, 좌표를 찍으면 그건 한 점이기 때문이다. 이렇게 만들어진 클러스터를 리턴해준다.
여기 까지하면 출력은 다음과 같이 나온다.
k=0, k=1은 랜덤으로 선택한 중점(x,y좌표)이다. 클러스터는 저 중점들을 기준으로 나눈 k개의 집단을 의미한다.
< run (2/2) >
new_mid_point = False # 아직 새로운 중점을 찾지 않았으므로 False로 설정
for i in range(1, 10): # n번 반복 후 강제 종료
if mid_point == new_mid_point: break # 이전 중점과 새 중점의 차이가 없으면 종료
# 기존의 중점과 클러스터, 1회전 이후에 업데이트
if i>=2:
mid_point = new_mid_point
cluster = new_cluster
# 새로운 중점과 클러스스터
while True: # 적절한 중점이 리턴될 때까지 반복
new_mid_point = self.new_mid_point(cluster)
if new_mid_point: break # error가 뜨지 않아서 false가 아닌 값이 날아올 경우 종료
new_cluster = self.create_cluster(new_mid_point) # 새로운 클러스터 생성
print("\n__________ iteration = {} __________".format(i)) # 새로 생성된 중점과 클러스터 출력
for i in range(len(mid_point)): print("k = {}번째 집단의 중점 \t {}".format(i, mid_point[i]))
print("cluster\t", new_cluster)나머지 코드도 위 과정을 거치면 되지만 살짝 다르므로 다른 부분만 짚고 넘어 가겠다.
처음에 종료 조건이 n번 반복 후 강제 종료하거나 이전 중점과 새로운 중점과 동일할 때 멈춘다고 했다. 그런 점을 코드로 구현하였으므로 잘 봐두길 바란다.
새로운 중점을 만드는 new_mid_point()는 무한 반복문 안에 두었는데 왜 그런지는 함수를 자세히 보도록 하겠다.
< new_mid_point >
# 새로운 중점 찾기, k-means
def new_mid_point(self, cluster):
total = [[] for _ in range(self.k)] # k 크기 만큼, 새로운 좌표 구하는 거니까!!!
avg = [[] for _ in range(self.k)] # 평균 값이자, 새로운 중점
for i in range(self.k): # k번 반복
x=0; y=0
for c in cluster[i]:
x+=self.table[c][0] # 테이블 좌표 값을 각각 저장
y+=self.table[c][1]
total[i].append(x); total[i].append(y) # total에 x좌표 y좌표 총합을 넣음
for i in range(self.k): # 클러스터 개수
for j in range(2): # 좌표 값
try: # 한 집단만 있을 경우 error 발생
avg[i].append(round(total[i][j] / len(cluster[i]), 2)) # ZeroDivisionError
except Exception as e:
return False # error 발생 시 False 리턴해서 다시 new_mid_point() 호출새로운 클러스터를 만들기 위해서는 새로운 중점을 찾아야 한다. 이때 각 좌표 값의 평균을 통해서 새로운 중점을 만들 거다. 아까 클러스터에 각 좌표들의 인덱스 값이 들어간 것을 기억하시나요??
클러스터에 들어있는 인덱스 값을 통해 두 개의 클러스터로 나뉜 값들의 각 x와 y에 대한 평균을 구하는 것이 위 코드 내용이다. 무슨 소린지 잘 이해가 안 될 것 같아서(는 미래의 나에게 하는 말) 그림을 준비했다.
위 그림처럼 클러스터에는 테이블의 인덱스 값이 들어 있고, 테이블에는 좌표 값이 들어 있다. 각 색별로 x(0)와 y(1)값들의 평균을 구하면 된다.
이렇게 새로운 중점을 구했다면 다시 클러스터를 구한다. 이 과정을 종료 조건이 맞을 때까지 반복하면 된다.
출력
이거 개념이 이해 안 돼서 교수님 코드 분석하는데 3시간 걸린 거 같다. 개념 이해하는데 1시간. 직접 짜는데 2시간. 총합 6시간 걸리고. 수업 시간에 에러 나서 고치고 주석 다는데 대략 1시간 걸렸다. 도합 7시간 짜리 코드^^
밤 새서 코드를 짜서 그런지 몰골은 초췌하지만.. 아무래도 공주니까.. ^_^ 품위는 잃지 않으려고 한다 ᕕ༼✿•̀︿•́༽ᕗ
진짜 안뇽! ᕕ༼✿•̀︿•́༽ᕗ
'python' 카테고리의 다른 글
| 판다스 한글 글자 깨짐 (0) | 2022.09.02 |
|---|---|
| [코딩] 쉼표 넣는 코드 (0) | 2022.04.17 |
| [코딩] 제로부터 시작하는 selenium- 넷플릭스 크롤링 (python) (1) | 2022.03.27 |
| [코딩] 여러 파일에서 특정 키워드를 포함하는 파일 찾기(python) (0) | 2022.03.05 |
| [코딩] 넘파이 모듈을 사용하지 않고 행렬곱 코드 짜기(python) (0) | 2022.03.05 |
