kmeansクラスタリングをpythonとmatplotlibで試してみました。
kmeansクラスタリングとは、教師なしデータ分類手法の一つ。
始めに、ランダムにk個の重心を配置し、
# ranges: dataの各次元の最小値[i][0]と最大値[i][1] ranges = [ (min([ d[i] for d in data ]), \ max([ d[i] for d in data])) for i in range(len(data[0])) ] # k random centroids # 各次元毎に最小値から最大値までの値として生成 centroids = [ [ random.random()*(ranges[i][1] - ranges[i][0])+ranges[i][0] \ for i in range(len(data[0])) ] for j in range(k) ]
全データ点を、最も近い重心に割り当てていきます。ここでは、dataのリストのインデックスを、
クラスタ毎にbestmachesに追加することで、これを実現します。
# Find which centroid(centroids[i]) is the closest for each data for j in range(len(data)): dj = data[j] bestmatch = 0 for i in range(k): d = self.distance(centroids[i], dj) if d < self.distance(centroids[bestmatch], dj): # closest cluster number bestmatch = i # append index j to i(bestmatch) th cluster bestmatches[bestmatch].append(j)
クラスタに属する点の平均(mean)を新たにクラスタの重心として、
# move the centroids(centroids[i]) to the mean of their members for i in range(k): mean = [0.0] * len(data[0]) if len(bestmatches[i]) > 0: for data_id in bestmatches[i]: for dim in range(len(data[data_id])): mean[dim] += data[data_id][dim] for j in range(len(mean)): mean[j] /= len(bestmatches[i]) centroids[i] = mean
割り当てに変更が生じなくなるか、一定回数以上となるまでこのプロセスを繰り返します。
一番最初の図は、データ点数が100、クラスタk=5の場合の結果の一例です。
今回試したコード全体は以下のようになってます。