階層型クラスタリングと非階層型クラスタリングの考察

今回はPythonで階層型クラスタリングと非階層型クラスタリングをアルゴリズムから実装し、両者の違いについて考察します。

階層型クラスタリングとは
概念
似ているものどうしを同じクラスタに、似てないものを別のクラスタにグルーピングします。

アルゴリズム
一番近い要素またはサブクラスタ間を繋ぎ、また距離を計算する、ということを繰り返し行います。得られたデンドログラムと指定した基準値から、データのクラスタリングが出来ます。

非階層クラスタリングとは
概念
クラスタの平均を用いることで、与えられたクラスタ数にデータを分類します。

アルゴリズム
各データに対してランダムにクラスタを割り振ります。
割り振ったデータをもとに各クラスタの中心 を計算します。計算は通常割り当てられたデータの各要素の算術平均が使用されます。
各データと各クラスタの中心との距離を求め、各データを最も近い中心のクラスタに割り当て直し、上記の処理で全てのデータに対しクラスタの割り当てが変化しなかった場合、あるいは変化量が事前に設定した一定の閾値を下回った場合に、収束したと判断して処理を終了します。そうでない場合は新しく割り振られたクラスタからクラスタの中心を再計算して上記の処理を繰り返します。

用いたデータはR言語kernlab付属のデータセットであるirisです。
３種類のアヤメの花の特徴量(sepal length, sepal width, petal length, petal width)をもとにしてクラスタリングを行います。

まず、階層型クラスタリングの実装ですが、今回は最短距離法を用いました。

#coding:utf-8

import csv
import math

f = open('iris.csv','rb')
data = []
c = csv.reader(f)
for row in c:
    data.append(row)
f.close()

vector = [] #データをベクトルに入れる
num  = len(data)
for i in range(1,num):
    vector.append(data[i])
    data[i].pop(0)

vector_num = len(vector) #類似度の行列を作る
mat = []
dist = 0

def make_mat(vector):
    sub_mat = []
    for i in range(1,len(vector)):
        for j in range(i):  # ユークリッド距離の計算
            dist = math.sqrt((float(vector[i][0])-float(vector[j][0]))**2+(float(vector[i][1])-float(vector[j][1]))**2+(float(vector[i][2])-float(vector[j][2]))**2+(float(vector[i][3])-float(vector[j][3]))**2)
            sub_mat.append(dist)
            dist = 0
        mat.append(sub_mat)
        sub_mat = []
    return mat

def dd(list1,list2):
    dist = math.sqrt((float(list1[0])-float(list2[0]))**2+(float(list1[1])-float(list2[1]))**2+(float(list1[2])-float(list2[2]))**2+(float(list1[3])-float(list2[3]))**2)
    return dist

def min(list):  #最小値検索をする関数
    min = list[0]
    for i in range(len(list)):
        if min >= list[i]:
            min = list[i]
    return min

def min_num(list):  #最小値検索をする関数
    min_number = 0
    min = list[0]
    for i in range(len(list)-1):
        if min >= list[i]:
            min_number = i
            min = list[i]
    return min_number

def mat_min(matrix):
    m = matrix[0][0]
    row = 0
    for i in range(len(matrix)):
        if m > min(matrix[i]):
            m = min(matrix[i])
            row = i
    col = min_num(matrix[row])
    return m,row,row+1,col #データに対応するのはrow+1,colである。

def mean(list1,list2):   #データの平均値リストを返す
    mm = [(float(list1[0])+float(list2[0]))*1.0/2,(float(list1[1])+float(list2[1]))*1.0/2,(float(list1[2])+float(list2[2]))*1.0/2,(float(list1[3])+float(list2[3]))*1.0/2,list1[4]+"/"+list2[4]]
    return mm

def large(a,b):
    if a > b:
        return [b,a]
    if b > a:
        return [a,b]

def re_mat(mat,vector,num): #最小値をグルーピングをし、再構成を行う関数
    row = num[2]
    col = num[3]
    dist = mat_min(mat)[0]
    ll = large(row,col)
    del mat[ll[0]]
    del mat[ll[1]-1]
    mat.append(vector)
    store = [row,col,dist]
    return mat,store

for i in range(len(vector)-3):
    mat = []
    mat = make_mat(vector)
    mmmat = mat_min(mat)
    ave = mean(vector[mmmat[2]],vector[mmmat[3]])
    rr = re_mat(vector,ave,mmmat)
    print rr
    #    print len(rr[0])
    mat = rr
print "*************"
print rr[0][0][4]
print "*************"
print rr[0][1][4]
print "*************"
print rr[0][2][4]
print "*************"

実行結果
*************
virginica/virginica/virginica/virginica/virginica/virginica/virginica/virginica/virginica/virginica/virginica/virginica/virginica/virginica/virginica/virginica/virginica/virginica/virginica/virginica/virginica/virginica/virginica/virginica/virginica/virginica/virginica/virginica/virginica/virginica/virginica/virginica/virginica/virginica/virginica/virginica/virginica
*************
setosa/setosa/setosa/setosa/setosa/setosa/setosa/setosa/setosa/setosa/setosa/setosa/setosa/setosa/setosa/setosa/setosa/setosa/setosa/setosa/setosa/setosa/setosa/setosa/setosa/setosa/setosa/setosa/setosa/setosa/setosa/setosa/setosa/setosa/setosa/setosa/setosa/setosa/setosa/setosa/setosa/setosa/setosa/setosa/setosa/setosa/setosa/setosa/setosa/setosa
*************
versicolor/versicolor/versicolor/versicolor/versicolor/versicolor/versicolor/versicolor/versicolor/versicolor/versicolor/versicolor/versicolor/versicolor/versicolor/versicolor/versicolor/versicolor/versicolor/versicolor/versicolor/versicolor/versicolor/versicolor/versicolor/versicolor/versicolor/versicolor/versicolor/versicolor/versicolor/versicolor/versicolor/versicolor/versicolor/versicolor/virginica/virginica/virginica/virginica/virginica/virginica/virginica/versicolor/virginica/virginica/versicolor/versicolor/virginica/virginica/virginica/virginica/versicolor/versicolor/versicolor/versicolor/versicolor/versicolor/versicolor/versicolor/versicolor/versicolor/versicolor
*************

次に、非階層型クラスタリングですが、K-Means法を用いました。

#coding:utf-8

import csv
import math
import random

f = open('iris.csv','rb')
data = []
c = csv.reader(f)
for row in c:
    data.append(row)
f.close()

vector = []
num  = len(data)
for i in range(1,num):
    vector.append(data[i])
    data[i].pop(0)

num_vector = len(vector)

for i in range(num_vector):
    vector[i].append(random.randint(1,3))

def make_list(mat,num):
    ll = []
    for i in range(len(mat)):
        ll.append(mat[i][num])
    return ll

def z_score(list):
    sum = 0
    num = len(list)
    for i in range(num):
        sum += float(list[i])
    ave = sum*1.0/num

    sum_1 = 0
    for i in range(num):
        sum_1 += (float(list[i])-ave)**2
    sd = math.sqrt(sum_1*1.0/num)

    out = []
    for i in range(num):
        out.append((float(list[i])-ave)*1.0/sd)
    return out

l0 = make_list(vector,0)
l1 = make_list(vector,1)
l2 = make_list(vector,2)
l3 = make_list(vector,3)

z0 = z_score(l0)
z1 = z_score(l1)
z2 = z_score(l2)
z3 = z_score(l3)

vector_1 = []
for i in range(len(vector)):
    vector_1.append([z0[i],z1[i],z2[i],z3[i],vector[i][4],vector[i][5]])


def dist(list_1,list_2):  #距離を求める関数
    num = math.sqrt((float(list_1[0])-float(list_2[0]))**2+(float(list_1[1])-float(list_2[1]))**2+(float(list_1[2])-float(list_2[2]))**2+(float(list_1[3])-float(list_2[3]))**2)
    return num

def min(list):  #最小値検索をする関数
    min = list[0]
    for i in range(len(list)):
        if min >= list[i]:
            min = list[i]
    return min

def gravity(list):  #グループ内の重心を計算する関数
    num = len(list)
    sum1 = 0
    sum2 = 0
    sum3 = 0
    sum4 = 0
    for i in range(len(list)):
        sum1 = sum1 + float(list[i][0])
        sum2 = sum2 + float(list[i][1])
        sum3 = sum3 + float(list[i][2])
        sum4 = sum4 + float(list[i][3])
    gra = [sum1*1.0/num,sum2*1.0/num,sum3*1.0/num,sum4*1.0/num]
    return gra

def group(list): # グルーピングを行う関数
    group_1 = []
    group_2 = []
    group_3 = []
    for i in range(len(list)):
        if list[i][5] == 1:
            group_1.append(list[i])
        elif list[i][5] == 2:
            group_2.append(list[i])
        else:
            group_3.append(list[i])
    return group_1,group_2,group_3

def re_group(list,g1,g2,g3): #グループ再構成を行う関数

    group_1 = []
    group_2 = []
    group_3 = []
    for i in range(len(list)):
        m1 = dist(list[i],g1)
        m2 = dist(list[i],g2)
        m3 = dist(list[i],g3)
        if min([m1,m2,m3]) == m1:
            group_1.append(list[i])
        elif min([m1,m2,m3]) == m2:
            group_2.append(list[i])
        else:
            group_3.append(list[i])
    return group_1,group_2,group_3

g = group(vector_1)

for i in range(2):
    g1 = gravity(g[0])
    g2 = gravity(g[1])
    g3 = gravity(g[2])
    store = re_group(vector_1,g1,g2,g3)
    g1 = store[0]
    g2 = store[1]
    g3 = store[2]

for i in range(len(g1)):
    print g1[i][4]
print "********************************"
for i in range(len(g2)):
    print g2[i][4]
print "********************************"
for i in range(len(g3)):
    print g3[i][4]

実行結果
versicolor,versicolor,versicolor,versicolor,versicolor,versicolor,versicolor,versicolor,versicolor,versicolor,versicolor,versicolor,virginica,virginica,virginica,virginica,virginica,virginica,virginica,virginica,virginica,virginica,virginica,virginica,virginica,virginica,virginica,virginica,virginica,virginica,virginica,virginica,
********************************
setosa,setosa,setosa,setosa,setosa,setosa,setosa,setosa,setosa,setosa,setosa,setosa,setosa,setosa,setosa,setosa,setosa,setosa,setosa,setosa,setosa,setosa,setosa,setosa,setosa,setosa,setosa,setosa,setosa,setosa,setosa,setosa,setosa,setosa,setosa,setosa,setosa,setosa,setosa,setosa,setosa,setosa,setosa,setosa,setosa,setosa,setosa,setosa,setosa,setosa,versicolor
********************************
versicolor,versicolor,versicolor,versicolor,versicolor,versicolor,versicolor,versicolor,versicolor,versicolor,versicolor,versicolor,versicolor,versicolor,versicolor,versicolor,versicolor,versicolor,versicolor,versicolor,versicolor,versicolor,versicolor,versicolor,versicolor,versicolor,versicolor,versicolor,versicolor,versicolor,versicolor,versicolor,versicolor,versicolor,versicolor,versicolor,versicolor,virginica,virginica,virginica,virginica,virginica,virginica,virginica,virginica,virginica,virginica,virginica,virginica,virginica,virginica,virginica,virginica,virginica,virginica,virginica,virginica,virginica,virginica,virginica,virginica,virginica,virginica,virginica,virginica,virginica,virginica

考察
非階層型クラスタリングのK-means法では初期設定において、データに対してランダムにクラスタを割り当てるため、実行結果が毎回異なりました。今回は階層型クラスタリングの方が精度が良かったですが、K-means法の方が実行時間が短くなりました。K-means++法という初期値の選択法を改良したクラスタリング法が考案されているそうです。