数据挖掘基础:K-Means算法的原理与Python实现

数据挖掘基础:K-Means算法的原理与Python实现原理 K-Means是一种基于样本间相似度量的间接聚类方法，属于非监督学习方法。K-Means接受参数k，将n个数据对象划分为k个聚类。计算每一个数据对象的依据为对象与k个聚类的相似度（或者距离），选择相似度最高的聚类，将这个数据对象划入这个聚类。同时，也需要更新这个聚类的中心点。输入:k个聚类的中心点

JairusChan

15813人浏览 · 2012-04-27 11:53:40

JairusChan · 2012-04-27 11:53:40 发布

数据挖掘基础:K-Means算法的原理与Python实现

原理

K-Means是一种基于样本间相似度量的间接聚类方法，属于非监督学习方法。K-Means接受参数k，将n个数据对象划分为k个聚类。计算每一个数据对象的依据为对象与k个聚类的相似度（或者距离），选择相似度最高的聚类，将这个数据对象划入这个聚类。同时，也需要更新这个聚类的中心点。

输入:

k个聚类的中心点的位置；
n个数据对象的位置；

输出:

将这n个数据对象划入这k个聚类中，即计算出这k个聚类所属的聚类。

计算过程:

1. 计算点p与这k个聚类的距离l1,l2,...,lk，并得到l1,l2,…,lk的最大值lm（设点p与聚类m的距离最近，值为lm）。

如下图所示，共有3个聚类，每一个聚类的中心位置为黑色粗边框的点。现在需要计算点p，也即图中灰色点所属的聚类。计算得到点p与红色聚类的距离为1.2，与蓝色

聚类的距离为2.5，与绿色聚类的距离为3.1。因而，点p应当属于红色聚类。如下图所示：

2. 将点p划入到聚类m，并重新计算聚类m的中心点位置。

继续上述示例，点p被划入了红点聚类。从而，红色聚类的中心也发生了变化。如下图所示:

3. 重复以上步骤，直到n个数据对象全部计算完成。

实现

运行前提:

Python运行环境与编辑环境；
Matplotlib.pyplot图形库，可用于快速绘制2D图表，与matlab中的plot命令类似，而且用法也基本相同。

代码:

# coding=utf-8

'''
作者:Jairus Chan
程序:kmeans算法
'''

import matplotlib.pyplot as plt
import math
import numpy
import random

#dotOringalNum为各个分类最初的大小
dotOringalNum=100
#dotAddNum最后测试点的数目
dotAddNum=1000

fig = plt.figure()
ax = fig.add_subplot(111)

sets=[]
colors=['b','g','r','y']

#第一个分类，颜色为蓝色，在左下角
a=[]
txx=0.0
tyy=0.0
for i in range(0,dotOringalNum):
	tx=float(random.randint(1000,3000))/100
	ty=float(random.randint(1000,3000))/100
	a.append([tx,ty])
	txx+=tx
	tyy+=ty
	#ax.plot([tx],[ty],color=colors[0],linestyle='',marker='.')
#a的第一个元素为a的各个元素xy值之合
a.insert(0,[txx,tyy])
sets.append(a)

#第二个分类，颜色为绿色，在右上角
b=[]
txx=0.0
tyy=0.0
for i in range(0,dotOringalNum):
	tx=float(random.randint(4000,6000))/100
	ty=float(random.randint(4000,6000))/100
	b.append([tx,ty])
	txx+=tx
	tyy+=ty
	#ax.plot([tx],[ty],color=colors[1],linestyle='',marker='.')
b.insert(0,[txx,tyy])
sets.append(b)

#第三个分类，颜色为红色，在左上角
c=[]
txx=0.0
tyy=0.0
for i in range(0,dotOringalNum):
	tx=float(random.randint(1000,3000))/100
	ty=float(random.randint(4000,6000))/100
	c.append([tx,ty])
	txx+=tx
	tyy+=ty
	#ax.plot([tx],[ty],color=colors[2],linestyle='',marker='.')
c.insert(0,[txx,tyy])
sets.append(c)


#第四个分类，颜色为黄色，在右下角
d=[]
txx=0
tyy=0
for i in range(0,dotOringalNum):
	tx=float(random.randint(4000,6000))/100
	ty=float(random.randint(1000,3000))/100
	d.append([tx,ty])
	txx+=tx
	tyy+=ty
	#ax.plot([tx],[ty],color=colors[3],linestyle='',marker='.')
d.insert(0,[txx,tyy])
sets.append(d)


#测试
for i in range(0,dotAddNum):
	tx=float(random.randint(0,7000))/100
	ty=float(random.randint(0,7000))/100
	dist=9000.0
	setBelong=0
	for j in range(0,4):
		length=len(sets[j])-1

		centX=sets[j][0][0]/length
		centY=sets[j][0][1]/length

		if (centX-tx)*(centX-tx)+(centY-ty)*(centY-ty)<dist:
			setBelong=j
			dist=(centX-tx)*(centX-tx)+(centY-ty)*(centY-ty)
   
	#ax.plot([tx],[ty],color=colors[setBelong],linestyle='',marker='.')
	sets[setBelong][0][0]+=tx
	sets[setBelong][0][1]+=ty
	sets[setBelong].append([tx,ty])

#输出所有的点
for i in range(0,4):
	tx=[]
	ty=[]
	for j in range(1,len(sets[i])):
		tx.append(sets[i][j][0])
		ty.append(sets[i][j][1])
	ax.plot(tx,ty,color=colors[i],linestyle='',marker='.')


plt.show()