비지도학습 (Unsupervised Machine Learning) 1. 비지도학습이란비지도학습이란머신러닝 1) 알고리즘중한방법론에속하며데이터에대한명시적인답을주지않고컴퓨터를학습시키는알고리즘이다. 즉데이터형태로학습을진행하는방법이다. 대표적인예로는데이터가무작위로분포되어있을때이데이터를비슷한특성을가진세가지부류로묶는클러스터링 (K-means) 알고리즘이다. 비지도학습은데이터의숨겨진특징이나구조를발견하는데사용된다. [ 그림 1] 군집화알고리즘 (http://solarisailab.com/archives/1785) 비지도학습알고리즘종류에는대표적인 K-means 알고리즘 ( 군집알고리즘 ), Kernel Density estimation 알고리즘, K- 최근접이웃추정 (K-Nearest Neighbors Estimation), 차원 축소 (Dimension Reduction), Exception maximization 알고리즘등이있다. 2. 비지도학습의알고리즘 (1) K-means 알고리즘 K-means 알고리즘은클러스터내부에속한데이터들이서로 가깝다 라고정의하고 가장가까운 내부거리를가지는클러스터를고르는알고리즘이다. 또다른설명으로는각클러스터마다 중심 과각각의데이터가 얼마나가까운가 를 cost로정의하여, 가장적은 cost를갖는클러스터를찾는알고리즘이라고도한다. [ 그림 2] K-means 알고리즘 ( 출처 :http://jinquixote.tistory.com/124) 1) 이용해서컴퓨터를학습시키는방법론 ( 방법에따라지도학습, 비지도학습, 강화학습, 준지도학습이있다.) - 1 -
[ 그림2] 를참조하여이알고리즘의프로세스를순서대로생각해보면첫번째는최초중심값을랜덤하게선택한다. 두번째는 k개의중심값과각개별데이터간의거리를측정하고, 가장가까운클러스터를할당한다. 세번째는각클러스터마다새로운중심값을계산하고마지막엔새로선택된중심값이변화가없다면멈추고, 변화가있다면첫번째부터다시반복을하고마친다. [ 그림 3] K-means 알고리즘의 pseudo-code( 출처 : http://stanford.edu/~cpiech/cs221/handouts/kmeans.html) (2) Kernel Density estimation( 커널밀도추정 ) 알고리즘일단밀도추정은통계학에서다루는용어로데이터와변수의관계를파악하는방법이다. 간단한예시를들어설명하면우리의목표를수능을보는학생이어떤성적을받을지예측하는것이라고가정해보면변수는수능시험성적이고데이터는실제로변수에관측된값이다. (0점 ~ 400점 ) 우리는데이터들을통해수능시험성적 ( 변수 ) 가얼마가나올지예측할수있다. 즉, 밀도추정은데이터로부터변수가가질수있는모든값의밀도 ( 확률 ) 을추정하는것이다. 밀도추정방법은크게 parametric방법과 non-parametric방법으로구분할수있다. parametric방법은우리가알고있는정규분포표와같다. 좌우대칭의아주깔끔한분포가나온다. 반면에 non-parametric방법은히스토그램과같다. [ 그림 4] 성적히스토그램 ( 출처 :http://support.minitab.com/ko-kr/minitab/17/topic-library) 그러나이러한밀도추정은기하급수적으로커질때문제가생긴다. 이를해결하기위해나 타난것이커널밀도추정 (KDE) 알고리즘이다. 이알고리즘은커널함수라는것을사용한 다. 커널함수는원점을중심으로대칭하며적분값이 1 인양의함수로정의할수있다. 다 - 2 -
양한커널함수들이존재하고 KDE 는이들을사용하여주어진데이터의분포를반영하는새 로운분포를만드는것이다. [ 그림 5] 히스토그램과 Gaussian 분포를이용한커널밀도추정 ( 출처 :https://en.wikipedia.org/wiki/kernel_density_estimation) 왼쪽과같은분포가있다고할때 Gaussian 분포를커널함수로사용하면오른쪽과같이밀도추정을얻을수있다. 오른쪽그래프는왼쪽의히스토그램을 Smoothing하여지속적으로그린그래프로바꾸었다고볼수있다. 이것으로인해매끄러운그래프를얻기는했지만고차원이되었을때의문제에서는여전히자유롭지못하다. 그래서나온것이 K-최근접이웃추정알고리즘이라고한다. (3) K- 최근접이웃추정알고리즘 인접한 K 개의점을찾는것은같으나그것이포함되는영역의크기에따라서확률밀도를 나타내는것이다. [ 그림 6] K- 최근접이웃추정 ( 출처 : 서적 패턴인식 - 오일석 ) 이렇게 x 라는점을기준으로 2 개의최근접점을찾을때영역의너비 h 가넓으면확률이 작은것으로, 너비 h 가넓으면확률이큰것으로인식한다. 3. K-means 알고리즘의파이썬코드 입력출력 sample file, KM/LBG, Number of codeword total distortion at each iteration - 3 -
출력화면 # -*- coding: euc-kr -*- import cmath, time, random #VQ 클래스생성 class VQ(object): 파이썬코드 def init (self, filename, method, size_of_codeword): self.datalist = [] self.codewords = [] self.num_of_iter = 0 self.total_avg_dist = 0 self.prev_total_avg_dist = 0 self.method = method self.size_of_codeword = size_of_codeword self.classifications = [] self.dim = 0 self.end = 10**(-4) self.loaddatafile(filename) self.logfile = open("log_"+ method + "_" + str(size_of_codeword) +".txt",'w') def loaddatafile(self, filename): """ 데이터파일을로딩하여리스트객체에저장 """ fp = open(filename, 'r') for line in fp: datalist = [] for data in line.split(" "): if data == "\n": break else: datalist.append(float(data)) self.datalist.append(datalist) fp.close() self.starttime = time.time() self.dim = len(self.datalist[0]) # 초기에는하나의코드워드에속한다고정함 self.classifications.append(self.datalist) - 4 -
#k-means step1 def kminit(self): """ data중에서임의의 k개를선택하여초기중심집합을만든다 """ self.codewords = random.sample(self.datalist, self.size_of_codeword) #initial avg Distance를구해야한다. self.total_avg_dist = self.get_avg_distance() #k-means step2 코드북갯수만큼의클러스터로나눈다. def NNclassify(self): self.classifications = [[] for i in range(len(self.codewords))] for data in self.datalist: euclidian_distances = [] for codeword in self.codewords: euclidian_distances.append(self.euclid_dist(data, codeword)) index_num = euclidian_distances.index(min(euclidian_distances)) self.classifications[index_num].append(data) self.num_of_iter += 1 # 두벡터사이의유클리드언거리를구하는함수 def euclid_dist(self, vector, codeword): dist = 0 size = len(vector) for i in range(size): dist += (vector[i] - codeword[i])**2 return cmath.sqrt(dist).real # 평균왜곡값을구하는함수 def get_avg_distance(self): """ 왜곡값을구한다.""" size = len(self.classifications) means = [0 for j in range(size)] for i in range(size): training_vector = self.classifications[i] total = 0 for data in training_vector: total += self.euclid_dist(self.codewords[i], data) means[i] = total/len(training_vector) means_total = 0 for mean in means: means_total += mean return means_total/size # 이터레이션결과를프린트해준다. - 5 -
def printoutputs(self): self.total_avg_dist = self.get_avg_distance() print ("Iteration %d : total avg distance : %f"%(self.num_of_iter, self.total_avg_dist)) self.logfile.writelines("iteration : " + str(self.num_of_iter) + " total avg distance : " + str(self.total_avg_dist) +"\n") #k-means step3 def CodeBookupdate(self): """ 새로운클러스터에서중심값을구해코드북을업데이트한다 """ size = len(self.classifications) new_codewords = [] for i in range(size): training_vector = self.classifications[i] mean = [0 for dimmean in range(self.dim)] total = [0 for dimtotal in range(self.dim)] for data in training_vector: data_size = len(data) for k in range(data_size): total[k] += data[k] for j in range(len(total)): mean[j] += total[j] / len(training_vector) new_codewords.append(mean) self.codewords = new_codewords #print "new codeword : " + str(self.codewords) self.printoutputs() #k-means step4 def Iteration(self): """ < 종료조건 > 주석부분 : 가장짧은코드북과의개별벡터간의거리의평균이이전 iteration 과같으면 k-means 종료실제실행부분 : 상대적인변량을계산함 """ if self.num_of_iter == 0 : self.prev_total_avg_dist = self.total_avg_dist self.total_avg_dist = 0 return True #elif (self.total_avg_dist - self.prev_total_avg_dist) == 0: elif ((self.prev_total_avg_dist - self.total_avg_dist)/self.prev_total_avg_dist) <= self.end: if self.method == "k-means": self.logfile.writelines("\ntotal elapse time : " + str(time.time() - self.starttime) + " Sec\n") self.logfile.close() return False else: self.prev_total_avg_dist = self.total_avg_dist self.total_avg_dist = 0-6 -
return True #LBG step1 #modified k-means 방법과초기화방법이같다 def LBGInit(self): """ 백터의평균을구해서중간값으로 initial한다.""" mean_list = [] total_list = [0 for i in range(self.dim)] size = len(self.datalist) for i in self.datalist: k = 0 for j in i: total_list[k] += j k += 1 for total in total_list: mean_list.append(total/size) self.codewords.append(mean_list) self.total_avg_dist = self.get_avg_distance() #LBG step2 def LBGSplitting(self): """ 약정된 Split 함수로코드북을분2M개로분할한다.""" splits = [1.05, 0.95] codewords = self.codewords self.codewords = [] for codeword in codewords: new_codeword1 = [] new_codeword2 = [] for dim in codeword: new_codeword1.append(dim*splits[0]) new_codeword2.append(dim*splits[1]) self.codewords.append(new_codeword1) self.codewords.append(new_codeword2) self.num_of_iter = 0 print ("\n\n----- Number of CodeWord : %d -----\n\n" %(len(self.codewords))) self.logfile.writelines("\n\n----- Number of CodeWord : " + str(len(self.codewords)) + "-----\n") #modified k-means step2 def MKMSplitting(self): """total avg distance가가장큰코드워드를 2개로분할한다 """ splits = [1.05, 0.95] codewords = self.codewords size_of_codebook = len(codewords) # 각셀마다평균거리를구한다 avg_distance = [0 for i in range(size_of_codebook)] codeword_index = 0 for classify in self.classifications: total_dist = 0-7 -
for element in classify: dist = self.euclid_dist(element, codewords[codeword_index]) total_dist += dist class_size = len(classify) dist_mean = total_dist/class_size avg_distance[codeword_index] += dist_mean codeword_index += 1 # 평균거리를구한리스트객체에서가장큰코드워드를구한다. max_value_index = avg_distance.index(max(avg_distance)) avg_max_codeword = codewords.pop(max_value_index) # 코드워드를 2개로분할한다. for split in splits: new_codeword = [0 for code in range(self.dim)] code_index = 0 for code in avg_max_codeword: new_codeword[code_index] = code * split code_index += 1 codewords.insert(max_value_index, new_codeword) # 클래스변수로코드워드복사 self.codewords = codewords self.num_of_iter = 0 print ("\n\n----- Number of CodeWord : %d -----\n\n" %(len(self.codewords))) self.logfile.writelines("\n\n----- Number of CodeWord : " + str(len(self.codewords)) + "-----\n") def LBGTermination(self): """ 현재코드북이처음입력된코드북의갯수보다많거나같을때 LBG알고리즘을마치게된다.""" if self.size_of_codeword <= len(self.codewords): self.logfile.writelines("\ntotal elapse time : " + str(time.time() - self.starttime) + " Sec\n") self.logfile.close() return True else: return False # 클래스끝 # 아래부분은 main 실행부분입니다. if name == " main ": method = int(input("input Method Num(1:KM, 2:MKM, 3:LBG) :" )) num_codeword = int(input("number of codeword : ")) data_path = "traindata.txt" if method == 3: LBG = VQ(data_path, "LBG", num_codeword) LBG.LBGInit() while not LBG.LBGTermination(): LBG.LBGSplitting() - 8 -
while LBG.Iteration(): LBG.NNclassify() LBG.CodeBookupdate() elif method == 1: kmeans = VQ(data_path, "k-means", num_codeword) kmeans.kminit() while kmeans.iteration(): kmeans.nnclassify() kmeans.codebookupdate() elif method == 2: m_kmeans = VQ(data_path, "m-k-means", num_codeword) m_kmeans.lbginit() while not m_kmeans.lbgtermination(): m_kmeans.mkmsplitting() while m_kmeans.iteration(): m_kmeans.nnclassify() m_kmeans.codebookupdate() - 9 -
출처 1. https://medium.com/mathpresso/mathpresso 2. http://darkpgmr.tistory.com/147 3. http://monny.tistory.com/ 4. http://stanford.edu/~cpiech/cs221/handouts/kmeans.html 5. https://en.wikipedia.org/wiki/kernel_density_estimation 6. 서적 패턴분석 - 오일석