집단지성 프로그래밍 4(Hierarchical Clustering)

이 글은 토비 세가란 저, 윤종완 역의 집단지성 프로그래밍 책을 읽으며 개인적으로 공부하며 정리한 내용이다.

이전 글 목록

• 집단지성 프로그래밍 1(Machine Learning, Euclidean Distance, Pearson Correlation Coefficient)
• 집단지성 프로그래밍 2(Recommendations)
• 집단지성 프로그래밍 3(Term Vector)

Hierarchical Clustering

계층적 군집화(hierarchical clustering) 알고리즘은 가장 유사한 두 그룹을 계속 병합하는 방식으로 그룹 계청을 만든다. 이 그룹들은 한 개 항목으로 시작되고 매 반복마다 이 함수는 모든 그룹 쌍 간의 거리를 계산하고 함께 병합하여 새로운 그룹을 생성한다. 이러한 과정을 한 개 그룹만 남을 때까지 반복한다.

이제 이전 글에서 모았던 블로그의 단어 벡터들을 이용해서, 실제로 euclidean distance, pearson correlation coefficient등을 구해보고 군집화를 해보려고 한다.

먼저, blogdata.csv에 저장했던 데이터를 불러와 사용할 수 있는 dict 형태로 만들어야 한다. 아래의 코드를 clusters.py에 추가한다.

위 코드를 통해, 이제 생성했던 단위벡터 데이터들을 불러 올 수 있게 되었다. 이를 이용해 지난 시간에 만들었던 recommendations.py를 실험해보면 아래와 같은 결과를 얻을 수 있다. 아래 결과를 보면 '울지않는벌새'라는 블로그는 '팩토리아이언'이라는 블로그와 0.50의 유사도를 갖고 있다고 판단된다. 하지만 실제로 블로그들을 찾아가보면, 사람이 판단했을 때 유사한지 안한지에 대한 판단을 아직 내릴 수 없었다.(단순 과학과 관련되어 있다는 정도...) 추출된 키워드가 정확하지 않고, 아직 표본의 숫자가 많지 않아 발생하는 오류라 생각된다.

>>> import clusters as cl
>>> import recommendations as re
>>> prefs = cl.readfile("blogdata.csv")
>>> transformed = re.transform_prefs(prefs)
>>> keys = transformed.keys()
>>> print keys[1], "와의 유사도"
울지않는벌새 : Security, Movie & Society 와의 유사도
>>> for count, person in re.top_matches(transformed, keys[1]):
...     print person, count
...
팩토리아이언 : Factory_IRON 0.506419698464
Back to the Mac 0.388985375403
알약 공식 블로그 0.373288154832
SK텔레콤 블로그 0.349266886482
삼성반도체이야기 0.324907452595

두 번째로, 군집화를 하기 위한 피어슨 상관계수를 구하는 함수를 조금 수정하여야한다. 이전 코드에서는 유사도가 클 수록 점수가 높아지는 형태로 하였지만, 이번에는 군집화를 하여야 하기 때문에 유사도가 높을 수록 점수가 작아지는 형태, 즉 거리가 가까워지는 형태를 취하여야 한다. 이를 위해 clusters.py에 아래의 코드를 추가한다.

세 번째로, 계층적 군집화 알고리즘 내의 각 군집은 두 개의 브랜치를 갖는 트리 내의 한 점이거나 데이터 세트에서 실제 가로줄과 연계된 종점이다. 각 군집은 위치 데이터를 가지고 위치 데이터는 종점인 가로줄 데이터 혹은 다른 노드 유형의 두 브랜치에서 병함된 데이터 중 하나이다. 아래 이러한 하나의 군집을 의미하는 biclass를 만들고, blogdata.csv에서 각각의 최소 distance를 구하여 병합하는 hcluster 함수를 만든다.

위의 코드에 대해서 자세히 설명하자면, 첫 번째로 biclass는 하나의 군집을 의미한다. 초기에는 blogdata.csv에서 가져온 각각의 블로그 데이터를 하나의 군집으로 보고 초기화를 하지만, 아래 hcluster(rows, diatnace=pearson) 함수를 수행하며, 가장 유사한 블로그끼리 점점 병합하여 최종적으로는 하나의 군집을 만든다. 이 때 biclass의 left와 right는 하나로 병합된 블로그 혹은 biclass들을 의미하고, vec은 병합된 블로그들 혹은 biclass의 평균 단어벡터 값이다.(블로그에 나오는 단어들의 개수가 하나의 row이다) distance는 병합된 블로그들간의 거리, 즉 유사도이다.

위 코드 설명의 두 번째로, hcluster는 초기에 모든 블로그들을 하나의 biclass로 만들고, 각각의 biclass간의 가장 유사도가 높은 class들을 찾아 병합을 진행하면 최종적으로 단 1개의 biclass를 만드는 함수이다.

14 라인은 파라미터로 들어온 각각의 블로그 단어벡터들을 biclass로 초기화 하는 작업이다.

17 ~ 18 라인은 while 문을 돌며 일단 0번째와 1번째들이 가장 가깝다고 설정하는 코드이다. 이후 (0,2), (0,3) ... (0,n), (1,2), (1,3) ... (1,n) ... (n-1, n) 까지의 유사도를 전부 구해 가장 유사도가 높은 것을 선택한다.

21 ~ 30 라인은 모든 블로그들을 \(n^2\)번을 순회하며 가장 유사도가 높은 두 개의 블로그들을 찾는다. 이 때 유사도를 찾는 방식은 파라미터로 들어온 distance=pearson을 따른다.

32 ~ 35 라인은 위에서 찾은 가장 유사도가 높은 블로그 두개의 vec(단어벡터의 값)의 평균 값을 구해 새로운 biclass의 vec으로 하고, 두 개의 블로그를 각각 새로운 biclass의 left와 right로 지정한다.

38 ~ 41 라인은 선택된 2개의 블로그를 기존 clust 리스트에서 제거하고, 새로 생성된 biclass에 id 값을 -1 하여 clust 리스트에 새로 추가한다.(기존 초기화된 biclass의 id들은 양수 값을 갖고, 새로 병합된 biclass의 id들은 음수 값을 가지게 하여 구분한다)

이제 위의 코드를 이용해 아래와 같이 군집화를 진행해 본다.

>>> import recommendations as re
>>> import clusters as cl
>>> big_data = re.transform_prefs(cl.readfile("blogdata.csv")) # blogdata.csv를 불러오고, 블로그 이름을 기준으로 변형
>>> blognames = big_data.keys() # 블로그 이름을 리스트로 변환
>>> data = [big_data[blog_name].values() for blog_name in blognames] # 각 블로그에 대한 단어벡터 정보를 2차원 배열 형태로 저장
>>> clust = cl.hcluster(data) # 군집화 실행

하지만, 단순 위의 코드를 통해서 실제 군집화가 실행되었는지 안되었는지 확인할 길이 없다. 이를 트리 형태로 출력해 제대로 되었는지 판단하기 위해 아래의 코드를 clusters.py에 추가한다

이제 위의 hcluster(data)코드에 이어 아래의 코드를 실행 시키면, 아래의 사진과 같은 결과를 얻을 수 있다

>>> cl.printclust(clust, labels=blognames)

여전히 위의 결과를 통해 아직 의미를 찾을 수 없다. 단순히 현재 쓰는 글은 이러한 방식을 통해서 블로그들의 단어벡터를 계산하고, 유사도를 계산해 군집화 할 수 있다는 것만 보여줄 뿐이고, 더욱 정확한 결과를 얻고 싶다면, 키워드 추출기를 만들고 feedlist.txt를 최대한 많이 한다면 가능할 것으로 생각된다.

또한 위의 printclust(clust, labels=blognames) 함수의 경우에는 직접 실행시켜봤을 때, 의미를 명확하게 알 수 없었다. blognames에는 빈 이름이 없지만 중간중간 보면 빈 공간도 보이는 것이 정확하지 않다고 볼 수 있다. 이 부분에 대해서는 조금 더 생각을 해서 자체적으로 의미를 명확히 보여줄 수 있는 것을 만들어야겠다.

계통도 그리기

위 글에서 printclust(clust, labels=blognames) 함수를 이용해 간단하게 텍스트로 군집들을 그려보았다. 하지만 이것을 통해서는 제대로 파악할 수 없었기 때문에 이 글에서는 python의 PIL(Python Image Library)를 이용해 직접 그려보도록 한다.

먼저 PIL을 사용하기 위해 pip을 이용해 라이브러리를 설치하도록 한다.

pip install pillow

이제 아래의 코드를 clusters.py에 추가한다.(코드 설명은 생략)

코드를 추가한 후 clusters.py를 터미널에서 실행시키면, blogclust.jpg 파일이 생성되고 결과는 아래와 같다

그리고, 맥에서 실행할 것이라면 위의 코드를 그대로 사용해도 좋지만, 윈도우에서 사용하면 3번 라인을 주석처리하고, 4번 라인의 주석을 해제하면 된다. PIL에 한글을 입력하기 위한 코드이다.