分類してみよう！1

今日やる。

課題

1. 入力された点の集合に対し、kmeansによるクラスタリングで2つの集合に分類する。
2. (追加)新たに入力された点が2つのうちどちらに含まれるか

やってることは「集合知プログラミング」の3.6の車輪の再開発みたいなもんだな。

実装(10:05ソース修正)

車輪再開発途中。@tkfのコメントにあったnumpy.arrayあたり検討する。
整数で除算してるせいか重心の点がかぶるなぁ。

#!/usr/bin/env python
#-*- coding:utf-8 -*-
from pylab import *
import random

points = [ [1,2],[2,3],[3,1],[-2,-1],[-3,-3],[-2,-4] ]
def kcluster(points, k=2):
	# 点の範囲を調べる
	ranges = [ ( min([p[i] for p in points]),\
				 max([p[i] for p in points]) )\
				 for i in range(len(points[0])) ]
	# 重心を適当に置く
	centers = [ [random.randint(ranges[0][0],ranges[0][1]),random.randint(ranges[1][0],ranges[1][1])] for i in range(k) ]

	results = []
	# クラスタごとに割り当てられる点(indexで保持？)
	while True:
		print "center ", centers
		tmpResults = [ [] for i in range(k) ]
		# もっとも近い重心に点を割り当てる
		for j in range(len(points)):
			minCenter = calcDistance(points[j],centers,ranges)
			if minCenter == -1:
				import sys
				sys.exit()
			tmpResults[minCenter].append(j)

		if results == tmpResults: break
		results = tmpResults[:]
		# 各重心を点の中心に持っていく
		for a in range(len(tmpResults)):
			r = tmpResults[a]
			rlen = len(r)
			cx = 0; cy = 0
			for r2 in r:
				p = points[r2]
				cx += p[0]; cy += p[1]
			if rlen > 0:
				cx /= rlen; cy /= rlen;
				centers[a] = [cx,cy]
				
	return results,ranges,centers

def calcDistance(point,centers,ranges):
	(x,y) = point
	print "x,y ",x,y
	mins = (ranges[0][0]-ranges[0][1])**2+(ranges[1][0]-ranges[1][1])**2
	minCenter = -1
	for n in range(len(centers)):
		(cx,cy) = centers[n]
		print " cx,cy:",cx,cy,
		distance = (cx - x)**2 + (cy - y)**2
		print " distance:",distance,
		if distance < mins:
			minCenter = n
			mins = distance
			print "minCenter:",n,
		print ""

	if minCenter == -1: # 通常ありえない
		print "error: k == -1"
	return minCenter

results,ranges,centers = kcluster(points)

newPoint = (0,3)
c = calcDistance(newPoint,centers,ranges)

for a in range(len(results)):
	r = results[a]
	pr = []
	for r2 in r:
		p = points[r2]
		pr.append(p)
	pr.append(centers[a])
	if c == a:
		pr.append(newPoint)
	x,y = zip(*pr)
	plot(x,y,".")

axis([ranges[0][0]-1,ranges[0][1]+1,ranges[1][0]-1,ranges[0][1]+1])
show()

実行結果。


赤で塗ったのが新しく追加した点(newPoint)。灰色で塗られてるのが各クラスタの中心点。新しく追加した点は緑側のクラスタに属していることがわかる。

今回、kmeansで訓練データ(points)を二つのクラスタに分けて、newPointを学習データとして入れた。newPointの分類方法はクラスタの中心から近い方で選んだ。次はあらかじめクラスタ分けされてる訓練データに対してk近傍での分類を行ってみたい。